sched: Implement BPF extensible scheduler class
Subsystems (13)
Tejun Heo
maintainerRFC PATCH 1/1 sched: Implement BPF extensible scheduler class
Overview
--------
This patch set proposes a new scheduler class called ‘ext_sched_class’, or sched_ext, which allows scheduling policies to be implemented as BPF programs.
More details will be provided on the overall architecture of sched_ext throughout the various patches in this set, as well as in the “How” section below. We realize that this patch set is a significant proposal, so we will be going into depth in the following “Motivation” section to explain why we think it’s justified. That section is laid out as follows, touching on three main axes where we believe that sched_ext provides significant value:
1. Ease of experimentation and exploration: Enabling rapid iteration of new scheduling policies.
2. Customization: Building application-specific schedulers which implement policies that are not applicable to general-purpose schedulers.
3. Rapid scheduler deployments: Non-disruptive swap outs of scheduling policies in production environments.
After the motivation section, we’ll provide a more detailed (but still high-level) overview of how sched_ext works.
Motivation
----------
1. Ease of experimentation and exploration
*Why is exploration important?*
Scheduling is a challenging problem space. Small changes in scheduling behavior can have a significant impact on various components of a system, with the corresponding effects varying widely across different platforms, architectures, and workloads.
While complexities have always existed in scheduling, they have increased dramatically over the past 10-15 years. In the mid-late 2000s, cores were typically homogeneous and further apart from each other, with the criteria for scheduling being roughly the same across the entire die.
Systems in the modern age are by comparison much more complex. Modern CPU designs, where the total power budget of all CPU cores often far exceeds the power budget of the socket, with dynamic frequency scaling, and with or without chiplets, have significantly expanded the scheduling problem space. Cache hierarchies have become less uniform, with Core Complex (CCX) designs such as recent AMD processors having multiple shared L3 caches within a single socket. Such topologies resemble NUMA sans persistent NUMA node stickiness.
Use-cases have become increasingly complex and diverse as well. Applications such as mobile and VR have strict latency requirements to avoid missing deadlines that impact user experience. Stacking workloads in servers is constantly pushing the demands on the scheduler in terms of workload isolation and resource distribution.
Experimentation and exploration are important for any non-trivial problem space. However, given the recent hardware and software developments, we believe that experimentation and exploration are not just important, but _critical_ in the scheduling problem space.
Indeed, other approaches in industry are already being explored. AMD has proposed an experimental patch set [0] which enables userspace to provide hints to the scheduler via “Userspace Hinting”. The approach adds a prctl() API which allows callers to set a numerical “hint” value on a struct task_struct. This hint is then optionally read by the scheduler to adjust the cost calculus for various scheduling decisions.
[0]: https://lore.kernel.org/lkml/[email protected]/
Huawei have also expressed interest [1] in enabling some form of programmable scheduling. While we’re unaware of any patch sets which have been sent to the upstream list for this proposal, it similarly illustrates the need for more flexibility in the scheduler.
[1]: https://lore.kernel.org/bpf/[email protected]/
Additionally, Google has developed ghOSt [2] with the goal of enabling custom, userspace driven scheduling policies. Prior presentations at LPC [3] have discussed ghOSt and how BPF can be used to accelerate scheduling.
[2]: https://dl.acm.org/doi/pdf/10.1145/3477132.3483542
[3]: https://lpc.events/event/16/contributions/1365/
*Why can’t we just explore directly with CFS?*
Experimenting with CFS directly or implementing a new sched_class from scratch is of course possible, but is often difficult and time consuming. Newcomers to the scheduler often require years to understand the codebase and become productive contributors. Even for seasoned kernel engineers, experimenting with and upstreaming features can take a very long time. The iteration process itself is also time consuming, as testing scheduler changes on real hardware requires reinstalling the kernel and rebooting the host.
Core scheduling is an example of a feature that took a significant amount of time and effort to integrate into the kernel. Part of the difficulty with core scheduling was the inherent mismatch in abstraction between the desire to perform core-wide scheduling, and the per-cpu design of the kernel scheduler. This caused issues, for example ensuring proper fairness between the independent runqueues of SMT siblings.
The high barrier to entry for working on the scheduler is an impediment to academia as well. Master’s/PhD candidates who are interested in improving the scheduler will spend years ramping-up, only to complete their degrees just as they’re finally ready to make significant changes. A lower entrance barrier would allow researchers to more quickly ramp up, test out hypotheses, and iterate on novel ideas. Research methodology is also severely hampered by the high barrier of entry to make modifications; for example, the Shenango [4] and Shinjuku scheduling policies used sched affinity to replicate the desired policy semantics, due to the difficulty of incorporating these policies into the kernel directly.
[4]: https://www.usenix.org/system/files/nsdi19-ousterhout.pdf
The iterative process itself also imposes a significant cost to working on the scheduler. Testing changes requires developers to recompile and reinstall the kernel, reboot their machines, rewarm their workloads, and then finally rerun their benchmarks. Though some of this overhead could potentially be mitigated by enabling schedulers to be implemented as kernel modules, a machine crash or subtle system state corruption is always only one innocuous mistake away. These problems are exacerbated when testing production workloads in a datacenter environment as well, where multiple hosts may be involved in an experiment; requiring a significantly longer ramp up time. Warming up memcache instances in the Meta production environment takes hours, for example.
*How does sched_ext help with exploration?*
sched_ext attempts to address all of the problems described above. In this section, we’ll describe the benefits to experimentation and exploration that are afforded by sched_ext, provide real-world examples of those benefits, and discuss some of the trade-offs and considerations in our design choices.
One of our main goals was to lower the barrier to entry for experimenting with the scheduler. sched_ext provides ergonomic callbacks and helpers to ease common operations such as managing idle CPUs, scheduling tasks on arbitrary CPUs, handling preemptions from other scheduling classes, and more. While sched_ext does require some ramp-up, the complexity is self-contained, and the learning curve gradual. Developers can ramp up by first implementing simple policies such as global FIFO in only tens of lines of code, and then continue to learn the APIs and building blocks available with sched_ext as they build more featureful and complex schedulers.
Another critical advantage provided by sched_ext is the use of BPF. BPF provides strong safety guarantees by statically analyzing programs at load time to ensure that they cannot corrupt or crash the system. sched_ext guarantees system integrity no matter what BPF scheduler is loaded, and provides mechanisms to safely disable the current BPF scheduler and migrate tasks back to a trusted scheduler. For example, we also implement in-kernel safety mechanisms to guarantee that a misbehaving scheduler cannot indefinitely starve tasks. BPF also enables sched_ext to significantly improve iteration speed for running experiments. Loading and unloading a BPF scheduler is simply a matter of running and terminating a sched_ext binary.
BPF also provides programs with a rich set of APIs, such as maps, kfuncs, and BPF helpers. In addition to providing useful building blocks to programs that run entirely in kernel space (such as many of our example schedulers), these APIs also allow programs to leverage user space in making scheduling decisions. Specifically, the Atropos sample scheduler has a relatively simple FIFO scheduling layer in BPF, paired with a load balancing component in userspace written in Rust. As described in more detail below, we also built a more general user-space scheduling framework called “rhone” by leveraging various BPF features.
On the other hand, BPF does have shortcomings, as can be plainly seen from the complexity in some of the example schedulers. scx_example_pair.bpf.c illustrates this point well. To start, it requires a good amount of code to emulate cgroup-local-storage. In the kernel proper, this would simply be a matter of adding another pointer to the struct cgroup, but in BPF, it requires a complex juggling of data amongst multiple different maps, a good amount of boilerplate code, and some unwieldy bpf_loop()‘s and atomics. The code is also littered with explicit and often unnecessary sanity checks to appease the verifier.
That being said, BPF is being rapidly improved. For example, Yonghong Song recently upstreamed a patch set [5] to add a cgroup local storage map type, allowing scx_example_pair.bpf.c to be simplified. There are plans to address other issues as well, such as providing statically-verified locking, and avoiding the need for unnecessary sanity checks. Addressing these shortcomings is a high priority for BPF, and as progress continues to be made, we expect most deficiencies to be addressed in the not-too-distant future.
[5]: https://lore.kernel.org/bpf/[email protected]/
Yet another exploration advantage of sched_ext is helping widening the scope of experiments. For example, sched_ext makes it easy to defer CPU assignment until a task starts executing, allowing schedulers to share scheduling queues at any granularity (hyper-twin, CCX and so on). Additionally, higher level frameworks can be built on top to further widen the scope. For example, the aforementioned “rhone” [6] library allows implementing scheduling policies in user-space by encapsulating the complexity around communicating scheduling decisions with the kernel. This allows taking advantage of a richer programming environment in user-space, enabling experimenting with, for instance, more complex mathematical models.
[6]: https://github.com/Decave/rhone
sched_ext also allows developers to leverage machine learning. At Meta, we experimented with using machine learning to predict whether a running task would soon yield its CPU. These predictions can be used to aid the scheduler in deciding whether to keep a runnable task on its current CPU rather than migrating it to an idle CPU, with the hope of avoiding unnecessary cache misses. Using a tiny neural net model with only one hidden layer of size 16, and a decaying count of 64 syscalls as a feature, we were able to achieve a 15% throughput improvement on an Nginx benchmark, with an 87% inference accuracy.
2. Customization
This section discusses how sched_ext can enable users to run workloads on application-specific schedulers.
*Why deploy custom schedulers rather than improving CFS?*
Implementing application-specific schedulers and improving CFS are not conflicting goals. Scheduling features explored with sched_ext which yield beneficial results, and which are sufficiently generalizable, can and should be integrated into CFS. However, CFS is fundamentally designed to be a general purpose scheduler, and thus is not conducive to being extended with some highly targeted application or hardware specific changes.
Targeted, bespoke scheduling has many potential use cases. For example, VM scheduling can make certain optimizations that are infeasible in CFS due to the constrained problem space (scheduling a static number of long-running VCPUs versus an arbitrary number of threads). Additionally, certain applications might want to make targeted policy decisions based on hints directly from the application (for example, a service that knows the different deadlines of incoming RPCs).
Google has also experimented with some promising, novel scheduling policies. One example is “central” scheduling, wherein a single CPU makes all scheduling decisions for the entire system. This allows most cores on the system to be fully dedicated to running workloads, and can have significant performance improvements for certain use cases. For example, central scheduling with VCPUs can avoid expensive vmexits and cache flushes, by instead delegating the responsibility of preemption checks from the tick to a single CPU. See scx_example_central.bpf.c for a simple example of a central scheduling policy built in sched_ext.
Some workloads also have non-generalizable constraints which enable optimizations in a scheduling policy which would otherwise not be feasible. For example,VM workloads at Google typically have a low overcommit ratio compared to the number of physical CPUs. This allows the scheduler to support bounded tail latencies, as well as longer blocks of uninterrupted time.
Yet another interesting use case is the scx_example_cgfifo[7] scheduler, which provides FIFO policies for individual workloads, and a flattened hierarchical vtree for cgroups. This scheduler does not account for thundering herd problems among cgroups, and therefore may not be suitable for inclusion in CFS. However, in a simple benchmark using wrk[8] on apache serving a CGI script calculating sha1sum of a small file, it outperformed CFS by ~3% with CPU controller disabled and by ~10% with two apache instances competing with 2:1 weight ratio nested four level deep.
Note that the scx_example_cgfifo[7] scheduler isn't included in this patchset because it depends on the BPF rbtree which is still being developed. The linked version is an earlier draft. We will forward-port and include it in the series once the BPF rbtree support is in place.
[7] https://github.com/htejun/sched_ext/commit/f2fcd3147fb6286e0a35fcbed33c3bac69546a96
[8] https://github.com/wg/wrk
Certain industries require specific scheduling behaviors that do not apply broadly. For example, ARINC 653 defines scheduling behavior that is widely used by avionic software, and some out-of-tree implementations
(https://ieeexplore.ieee.org/document/7005306) have been built. While the upstream community may decide to merge one such implementation in the future, it would also be entirely reasonable to not do so given the narrowness of use-case, and non-generalizable, strict requirements. Such cases can be well served by sched_ext in all stages of the software development lifecycle -- development, testing, deployment and maintenance.
There are also classes of policy exploration, such as machine learning, or responding in real-time to application hints, that are significantly harder (and not necessarily appropriate) to integrate within the kernel itself.
*Won’t this increase fragmentation?*
We acknowledge that to some degree, sched_ext does run the risk of increasing the fragmentation of scheduler implementations. As a result of exploration, however, we believe that enabling the larger ecosystem to innovate will ultimately accelerate the overall development and performance of Linux. Additionally, our licensing and API stability policies should incentivize users to upstream their schedulers.
BPF programs are required to be GPLv2, which is enforced by the verifier on program loads. With regards to API stability, just as with other semi-internal interfaces such as BPF kfuncs, we won’t be providing any API stability guarantees to BPF schedulers. While we intend to make an effort to provide compatibility when possible, we will not provide any explicit, strong guarantees as the kernel typically does with e.g. UAPI headers. For users who decide to keep their schedulers out-of-tree,the licensing and maintenance overheads will be fundamentally the same as for carrying out-of-tree patches.
With regards to the schedulers included in this patch set, and any other schedulers we implement in the future, both Meta and Google will open-source all of the schedulers we implement which have any relevance to the broader upstream community. We expect that some of these, such as the example schedulers and scx_example_cgfifo scheduler, will be upstreamed as part of the kernel tree. Distros will be able to package and release these schedulers with the kernel, allowing users to utilize these schedulers out-of-the-box without requiring any additional work or dependencies such as clang or building the scheduler programs themselves. Other schedulers and scheduling frameworks such as rhone may be open-sourced through separate per-project repos.
3. Rapid scheduler deployments
Rolling out kernel upgrades is a slow and iterative process. At a large scale it can take months to roll a new kernel out to a fleet of servers. While this latency is expected and inevitable for normal kernel upgrades, it can become highly problematic when kernel changes are required to fix bugs. Livepatch [9] is available to quickly roll out critical security fixes to large fleets, but the scope of changes that can be applied with livepatching is fairly limited, and would likely not be usable for patching scheduling policies. With sched_ext, new scheduling policies can be rapidly rolled out to production environments.
[9]: https://www.kernel.org/doc/html/latest/livepatch/livepatch.html
As an example, one of the variants of the L1 Terminal Fault (L1TF) [10] vulnerability allows a VCPU running a VM to read arbitrary host kernel memory for pages in L1 data cache. The solution was to implement core scheduling, which ensures that tasks running as hypertwins have the same “cookie”.
[10]: https://www.intel.com/content/www/us/en/architecture-and-technology/l1tf.html
While core scheduling works well, it took a long time to finalize and land upstream. This long rollout period was painful, and required organizations to make difficult choices amongst a bad set of options. Some companies such as Google chose to implement and use their own custom L1TF-safe scheduler, others chose to run without hyper-threading enabled, and yet others left hyper-threading enabled and crossed their fingers.
Once core scheduling was upstream, organizations had to upgrade the kernels on their entire fleets. As downtime is not an option for many, these upgrades had to be gradually rolled out, which can take a very long time for large fleets.
An example of an sched_ext scheduler that illustrates core scheduling semantics is scx_example_pair.bpf.c, which co-schedules pairs of tasks from the same cgroup, and is resilient to L1TF vulnerabilities. While this example scheduler is certainly not suitable for production in its current form, a similar scheduler that is more performant and featureful could be written and deployed if necessary.
Rapid scheduling deployments can similarly be useful to quickly roll-out new scheduling features without requiring kernel upgrades. At Google, for example, it was observed that some low-priority workloads were causing degraded performance for higher-priority workloads due to consuming a disproportionate share of memory bandwidth. While a temporary mitigation was to use sched affinity to limit the footprint of this low-priority workload to a small subset of CPUs, a preferable solution would be to implement a more featureful task-priority mechanism which automatically throttles lower-priority tasks which are causing memory contention for the rest of the system. Implementing this in CFS and rolling it out to the fleet could take a very long time.
sched_ext would directly address these gaps. If another hardware bug or resource contention issue comes in that requires scheduler support to mitigate, sched_ext can be used to experiment with and test different policies. Once a scheduler is available, it can quickly be rolled out to as many hosts as necessary, and function as a stop-gap solution until a longer-term mitigation is upstreamed.
How
-----
sched_ext is a new sched_class which allows scheduling policies to be implemented in BPF programs.
sched_ext leverages BPF’s struct_ops feature to define a structure which exports function callbacks and flags to BPF programs that wish to implement scheduling policies. The struct_ops structure exported by sched_ext is struct sched_ext_ops, and is conceptually similar to struct sched_class. The role of sched_ext is to map the complex sched_class callbacks to the more simple and ergonomic struct sched_ext_ops callbacks.
Unlike some other BPF program types which have ABI requirements due to exporting UAPIs, struct_ops has no ABI requirements whatsoever. This provides us with the flexibility to change the APIs provided to schedulers as necessary. BPF struct_ops is also already being used successfully in other subsystems, such as in support of TCP congestion control.
The only struct_ops field that is required to be specified by a scheduler is the ‘name’ field. Otherwise, sched_ext will provide sane default behavior, such as automatically choosing an idle CPU on the task wakeup path if .select_cpu() is missing.
*Dispatch queues*
To bridge the workflow imbalance between the scheduler core and sched_ext_ops callbacks, sched_ext uses simple FIFOs called dispatch queues (dsq's). By default, there is one global dsq (SCX_DSQ_GLOBAL), and one local per-CPU dsq (SCX_DSQ_LOCAL). SCX_DSQ_GLOBAL is provided for convenience and need not be used by a scheduler that doesn't require it. As described in more detail below, SCX_DSQ_LOCAL is the per-CPU FIFO that sched_ext pulls from when putting the next task on the CPU. The BPF scheduler can manage an arbitrary number of dsq's using scx_bpf_create_dsq() and scx_bpf_destroy_dsq().
*Scheduling cycle*
The following briefly shows a typical workflow for how a waking task is scheduled and executed.
1. When a task is waking up, .select_cpu() is the first operation invoked. This serves two purposes. It both allows a scheduler to optimize task placement by specifying a CPU where it expects the task to eventually be scheduled, and the latter is that the selected CPU will be woken if it’s idle.
2. Once the target CPU is selected, .enqueue() is invoked. It can make one of the following decisions:
- Immediately dispatch the task to either the global dsq (SCX_DSQ_GLOBAL) or the current CPU’s local dsq (SCX_DSQ_LOCAL).
- Immediately dispatch the task to a user-created dispatch queue.
- Queue the task on the BPF side, e.g. in an rbtree map for a vruntime scheduler, with the intention of dispatching it at a later time from .dispatch().
3. When a CPU is ready to schedule, it first looks at its local dsq. If empty, it invokes .consume() which should make one or more scx_bpf_consume() calls to consume tasks from dsq's. If a scx_bpf_consume() call succeeds, the CPU has the next task to run and .consume() can return. If .consume() is not defined, sched_ext will by-default consume from only the built-in SCX_DSQ_GLOBAL dsq.
4. If there's still no task to run, .dispatch() is invoked which should make one or more scx_bpf_dispatch() calls to dispatch tasks from the BPF scheduler to one of the dsq's. If more than one task has been dispatched, go back to the previous consumption step.
*Verifying callback behavior*
sched_ext always verifies that any value returned from a callback is valid, and will issue an error and unload the scheduler if it is not. For example, if .select_cpu() returns an invalid CPU, or if an attempt is made to invoke the scx_bpf_dispatch() with invalid enqueue flags. Furthermore, if a task remains runnable for too long without being scheduled, sched_ext will detect it and error-out the scheduler.
Closing Thoughts
----------------
Both Meta and Google have experimented quite a lot with schedulers in the last several years. Google has benchmarked various workloads using user space scheduling, and have achieved performance wins by trading off generality for application specific needs. At Meta, we have not yet deployed sched_ext on any production workloads, though our preliminary experiments indicate that sched_ext would provide significant performance wins when deployed at scale. If successfully upstreamed, we expect to leverage it extensively to run various experiments and develop customized schedulers for a number of critical workloads.
In closing, both Meta and Google believe that sched_ext will significantly evolve how the broader community explores the scheduling problem space, empowering continued improvement to the in-kernel scheduler, while also enabling targeted policies for custom applications. We’ll be able to experiment easier and faster, explore uncharted areas, and deploy emergency scheduler changes when necessary. The same applies to anyone who wants to work on the scheduler, including academia and specialized industries. sched_ext will push forward the state of the art when it comes to scheduling and performance in Linux.
Written By
----------
David Vernet <[email protected]>
Josh Don <[email protected]>
Tejun Heo <[email protected]>
Barret Rhoden <[email protected]>
Supported By
------------
Paul Turner <[email protected]>
Neel Natu <[email protected]>
Patrick Bellasi <[email protected]>
Hao Luo <[email protected]>
Dimitrios Skarlatos <[email protected]>
Patchset
--------
This patchset is on top of bpf/for-next as of 2022-11-14:
de763fbb2c5b ("Merge branch 'libbpf: Fixed various checkpatch issues'")
and contains the following patches:
NOTE: The doc added by 0028 contains a high-level overview and might be a
good place to start.
0001-rhashtable-Allow-rhashtable-to-be-used-from-irq-safe.patch 0002-cgroup-Implement-cgroup_show_cftypes.patch 0003-BPF-Add-prog-to-bpf_struct_ops-check_member.patch 0004-sched-Allow-sched_cgroup_fork-to-fail-and-introduce-.patch 0005-sched-Add-sched_class-reweight_task.patch 0006-sched-Add-sched_class-switching_to-and-expose-check_.patch 0007-sched-Factor-out-cgroup-weight-conversion-functions.patch 0008-sched-Expose-css_tg-and-__setscheduler_prio-in-kerne.patch 0009-sched-Enumerate-CPU-cgroup-file-types.patch 0010-sched-Add-reason-to-sched_class-rq_-on-off-line.patch 0011-sched-Add-reason-to-sched_move_task.patch 0012-sched-Add-normal_policy.patch 0013-sched_ext-Add-boilerplate-for-extensible-scheduler-c.patch 0014-sched_ext-Implement-BPF-extensible-scheduler-class.patch 0015-sched_ext-TEMPORARY-Add-temporary-workaround-kfunc-h.patch 0016-sched_ext-Add-scx_example_dummy-and-scx_example_qmap.patch 0017-sched_ext-Add-sysrq-S-which-disables-the-BPF-schedul.patch 0018-sched_ext-Implement-runnable-task-stall-watchdog.patch 0019-sched_ext-Allow-BPF-schedulers-to-disallow-specific-.patch 0020-sched_ext-Allow-BPF-schedulers-to-switch-all-eligibl.patch 0021-sched_ext-Implement-scx_bpf_kick_cpu-and-task-preemp.patch 0022-sched_ext-Add-task-state-tracking-operations.patch 0023-sched_ext-Implement-tickless-support.patch 0024-sched_ext-Add-cgroup-support.patch 0025-sched_ext-Implement-SCX_KICK_WAIT.patch 0026-sched_ext-Implement-sched_ext_ops.cpu_acquire-releas.patch 0027-sched_ext-Implement-sched_ext_ops.cpu_online-offline.patch 0028-sched_ext-Add-Documentation-scheduler-sched-ext.rst.patch 0029-sched_ext-Add-a-basic-userland-vruntime-scheduler.patch 0030-BPF-TEMPORARY-Nerf-BTF-scalar-value-check.patch 0031-sched_ext-Add-a-rust-userspace-hybrid-example-schedu.patch
0001-0003: Misc prep.
0004-0012: Scheduler prep.
0013-0016: sched_ext core implementation and a couple example BPF scheduler.
0017-0020: Utility features including safety mechanisms and switch-all.
0021-0023: Kicking and preempting other CPUs, task state transition tracking
and tickless support. Demonstrated with an example central scheduler which makes all scheduling decisions on one CPU.
0024-0026: cgroup support and the ability to wait for other CPUs after
kicking them. Demonstrated with an example pair scheduler which guarantees that a hyperthread pair always executes tasks from the same cgroup at any given time.
0027 : Add CPU hotplug callbacks.
0028 : Add documentation.
0029-0031: Add two example schedulers. One demonstrating deferring most
scheduling decisions to userland. The other demonstrating a hybrid approach where load balancing decisions are made by userspace written in rust.
0015 and 0030 are temporary patches to work around missing BPF features. 0014 and 0023 also contain such workarounds.
The patchset is also available in the following git branch:
https://github.com/htejun/sched_ext sched_ext
diffstat follows.
Documentation/scheduler/index.rst | 1 Documentation/scheduler/sched-ext.rst | 230 +++ drivers/tty/sysrq.c | 1 include/asm-generic/vmlinux.lds.h | 1 include/linux/bpf.h | 3 include/linux/cgroup-defs.h | 8 include/linux/cgroup.h | 1 include/linux/rhashtable.h | 51 include/linux/sched.h | 5 include/linux/sched/ext.h | 651 ++++++++ include/linux/sched/task.h | 3 include/uapi/linux/sched.h | 1 init/Kconfig | 5 init/init_task.c | 12 kernel/Kconfig.preempt | 4 kernel/bpf/bpf_struct_ops_types.h | 4 kernel/bpf/btf.c | 5 kernel/bpf/verifier.c | 2 kernel/cgroup/cgroup.c | 97 + kernel/fork.c | 17 kernel/sched/autogroup.c | 4 kernel/sched/build_policy.c | 5 kernel/sched/core.c | 298 +++- kernel/sched/deadline.c | 4 kernel/sched/debug.c | 6 kernel/sched/ext.c | 3710 ++++++++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/ext.h | 252 +++ kernel/sched/fair.c | 9 kernel/sched/idle.c | 2 kernel/sched/rt.c | 4 kernel/sched/sched.h | 127 + kernel/sched/topology.c | 4 lib/rhashtable.c | 16 net/ipv4/bpf_tcp_ca.c | 3 tools/sched_ext/.gitignore | 8 tools/sched_ext/Makefile | 211 ++ tools/sched_ext/atropos/.gitignore | 3 tools/sched_ext/atropos/Cargo.toml | 34 tools/sched_ext/atropos/build.rs | 70 tools/sched_ext/atropos/rustfmt.toml | 8 tools/sched_ext/atropos/src/bpf/atropos.bpf.c | 501 ++++++ tools/sched_ext/atropos/src/bpf/atropos.h | 38 tools/sched_ext/atropos/src/main.rs | 648 ++++++++ tools/sched_ext/atropos/src/oss/atropos_sys.rs | 10 tools/sched_ext/atropos/src/oss/mod.rs | 29 tools/sched_ext/atropos/src/util.rs | 24 tools/sched_ext/gnu/stubs.h | 1 tools/sched_ext/scx_common.bpf.h | 120 + tools/sched_ext/scx_example_central.bpf.c | 377 +++++ tools/sched_ext/scx_example_central.c | 92 + tools/sched_ext/scx_example_dummy.bpf.c | 67 tools/sched_ext/scx_example_dummy.c | 97 + tools/sched_ext/scx_example_pair.bpf.c | 645 ++++++++ tools/sched_ext/scx_example_pair.c | 143 + tools/sched_ext/scx_example_pair.h | 10 tools/sched_ext/scx_example_qmap.bpf.c | 288 +++ tools/sched_ext/scx_example_qmap.c | 101 + tools/sched_ext/scx_example_userland.bpf.c | 265 +++ tools/sched_ext/scx_example_userland.c | 403 +++++ tools/sched_ext/scx_example_userland_common.h | 19 tools/sched_ext/user_exit_info.h | 50 61 files changed, 9672 insertions(+), 136 deletions(-)
Thanks.
Tejun Heo
maintainerPATCH 1/31 rhashtable: Allow rhashtable to be used from irq-safe contexts
rhashtable currently only does bh-safe synchronization making it impossible to use from irq-safe contexts. Switch it to use irq-safe synchronization to remove the restriction.
--- include/linux/rhashtable.h | 51 ++++++++++++++++++++++---------------- lib/rhashtable.c | 16 +++++++----- 2 files changed, 39 insertions(+), 28 deletions(-)
include/linux/rhashtable.h +29 -22
@@ -324,28 +324,31 @@ static inline struct rhash_lock_head __rcu **rht_bucket_insert(*/ static inline void rht_lock (struct bucket_table *tbl, -struct rhash_lock_head __rcu **bkt) +struct rhash_lock_head __rcu **bkt, +unsigned long *flags) { -local_bh_disable (); +local_irq_save (*flags);bit_spin_lock (0 , (unsigned long *)bkt);lock_map_acquire (&tbl->dep_map); }static inline void rht_lock_nested (struct bucket_table *tbl,struct rhash_lock_head __rcu **bucket, -unsigned int subclass) +unsigned int subclass, +unsigned long *flags) { -local_bh_disable (); +local_irq_save (*flags);bit_spin_lock (0 , (unsigned long *)bucket);lock_acquire_exclusive (&tbl->dep_map, subclass,0 ,NULL , _THIS_IP_); }static inline void rht_unlock (struct bucket_table *tbl, -struct rhash_lock_head __rcu **bkt) +struct rhash_lock_head __rcu **bkt, +unsigned long *flags) {lock_map_release (&tbl->dep_map);bit_spin_unlock (0 , (unsigned long *)bkt); -local_bh_enable (); +local_irq_restore (*flags); } static inline struct rhash_head *__rht_ptr(
@@ -393,7 +396,8 @@ static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,static inline void rht_assign_unlock (struct bucket_table *tbl,struct rhash_lock_head __rcu **bkt, -struct rhash_head *obj) +struct rhash_head *obj, +unsigned long *flags) {if (rht_is_a_nulls (obj)) obj =NULL ;
@@ -401,7 +405,7 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,rcu_assign_pointer (*bkt, (void *)obj);preempt_enable ();__release (bitlock); -local_bh_enable (); +local_irq_restore (*flags); }/**
@@ -706,6 +710,7 @@ static inline void *__rhashtable_insert_fast(struct rhash_head __rcu **pprev;struct bucket_table *tbl;struct rhash_head *head; +unsigned long flags;unsigned int hash;int elasticity;void *data;
@@ -720,11 +725,11 @@ static inline void *__rhashtable_insert_fast(if (!bkt) goto out; pprev =NULL ; -rht_lock (tbl, bkt); +rht_lock (tbl, bkt, &flags);if (unlikely (rcu_access_pointer (tbl->future_tbl))) { slow_path: -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags);rcu_read_unlock ();return rhashtable_insert_slow (ht, key, obj); }
@@ -756,9 +761,9 @@ static inline void *__rhashtable_insert_fast(RCU_INIT_POINTER (list->rhead.next, head);if (pprev) {rcu_assign_pointer (*pprev, obj); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); }else -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, &flags); data =NULL ; goto out; }
@@ -785,7 +790,7 @@ static inline void *__rhashtable_insert_fast( }atomic_inc (&ht->nelems); -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, &flags);if (rht_grow_above_75 (ht, tbl))schedule_work (&ht->run_work);
@@ -797,7 +802,7 @@ static inline void *__rhashtable_insert_fast(return data; out_unlock: -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); goto out; }
@@ -991,6 +996,7 @@ static inline int __rhashtable_remove_fast_one(struct rhash_lock_head __rcu **bkt;struct rhash_head __rcu **pprev;struct rhash_head *he; +unsigned long flags;unsigned int hash;int err = -ENOENT ;
@@ -999,7 +1005,7 @@ static inline int __rhashtable_remove_fast_one(if (!bkt)return -ENOENT ; pprev =NULL ; -rht_lock (tbl, bkt); +rht_lock (tbl, bkt, &flags);rht_for_each_from (he,rht_ptr (bkt, tbl, hash), tbl, hash) {struct rhlist_head *list;
@@ -1043,14 +1049,14 @@ static inline int __rhashtable_remove_fast_one(if (pprev) {rcu_assign_pointer (*pprev, obj); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); }else { -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, &flags); } goto unlocked; } -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); unlocked:if (err >0 ) {atomic_dec (&ht->nelems);
@@ -1143,6 +1149,7 @@ static inline int __rhashtable_replace_fast(struct rhash_lock_head __rcu **bkt;struct rhash_head __rcu **pprev;struct rhash_head *he; +unsigned long flags;unsigned int hash;int err = -ENOENT ;
@@ -1158,7 +1165,7 @@ static inline int __rhashtable_replace_fast(return -ENOENT ; pprev =NULL ; -rht_lock (tbl, bkt); +rht_lock (tbl, bkt, &flags);rht_for_each_from (he,rht_ptr (bkt, tbl, hash), tbl, hash) {if (he != obj_old) {
@@ -1169,15 +1176,15 @@ static inline int __rhashtable_replace_fast(rcu_assign_pointer (obj_new->next, obj_old->next);if (pprev) {rcu_assign_pointer (*pprev, obj_new); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); }else { -rht_assign_unlock (tbl, bkt, obj_new); +rht_assign_unlock (tbl, bkt, obj_new, &flags); } err =0 ; goto unlocked; } -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); unlocked:return err;
lib/rhashtable.c +10 -6
@@ -231,6 +231,7 @@ static int rhashtable_rehash_one(struct rhashtable *ht,struct rhash_head *head, *next, *entry;struct rhash_head __rcu **pprev =NULL ;unsigned int new_hash; +unsigned long flags;if (new_tbl->nest) goto out;
@@ -253,13 +254,14 @@ static int rhashtable_rehash_one(struct rhashtable *ht, new_hash =head_hashfn (ht, new_tbl, entry); -rht_lock_nested (new_tbl, &new_tbl->buckets[new_hash],SINGLE_DEPTH_NESTING ); +rht_lock_nested (new_tbl, &new_tbl->buckets[new_hash], +SINGLE_DEPTH_NESTING , &flags); head =rht_ptr (new_tbl->buckets + new_hash, new_tbl, new_hash);RCU_INIT_POINTER (entry->next, head); -rht_assign_unlock (new_tbl, &new_tbl->buckets[new_hash], entry); +rht_assign_unlock (new_tbl, &new_tbl->buckets[new_hash], entry, &flags);if (pprev)rcu_assign_pointer (*pprev, next);
@@ -276,18 +278,19 @@ static int rhashtable_rehash_chain(struct rhashtable *ht, {struct bucket_table *old_tbl =rht_dereference (ht->tbl, ht);struct rhash_lock_head __rcu **bkt =rht_bucket_var (old_tbl, old_hash); +unsigned long flags;int err;if (!bkt)return 0 ; -rht_lock (old_tbl, bkt); +rht_lock (old_tbl, bkt, &flags);while (!(err =rhashtable_rehash_one (ht, bkt, old_hash))) ;if (err == -ENOENT ) err =0 ; -rht_unlock (old_tbl, bkt); +rht_unlock (old_tbl, bkt, &flags);return err; }
@@ -590,6 +593,7 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,struct bucket_table *new_tbl;struct bucket_table *tbl;struct rhash_lock_head __rcu **bkt; +unsigned long flags;unsigned int hash;void *data;
@@ -607,7 +611,7 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key, new_tbl =rht_dereference_rcu (tbl->future_tbl, ht); data =ERR_PTR (-EAGAIN ); }else { -rht_lock (tbl, bkt); +rht_lock (tbl, bkt, &flags); data =rhashtable_lookup_one (ht, bkt, tbl, hash, key, obj); new_tbl = rhashtable_insert_one(ht, bkt, tbl,
@@ -615,7 +619,7 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,if (PTR_ERR (new_tbl) != -EEXIST ) data =ERR_CAST (new_tbl); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, &flags); } }while (!IS_ERR_OR_NULL (new_tbl));
Signature · 1 line
2.38.1
Re: [PATCH 01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts
include/linux/rhashtable.h static inline struct rhash_lock_head __rcu **rht_bucket_insert( · line 328
Quoted 6 lines · Tejun Heo
static inline void rht_lock(struct
bucket_table*tbl,include/linux/rhashtable.h +2
-1- struct rhash_lock_head __rcu **bkt) +struct rhash_lock_head __rcu **bkt, + unsigned long *flags)
I guess it doesn't matter as long as this actually gets inlined, but wouldn't it be better to have
flags = rht_lock(..); ... rht_unlock(.., flags);
as the calling convention? Rather than passing a pointer to the stack around.
That's what the native _raw_spin_lock_irqsave() interface is (even if "spin_lock_irqsave()" itself for historical reasons uses that inline asm-like "pass argument by reference *without* using a pointer")
And gaah, we should have made 'flags' be a real type long ago, but I guess 'unsigned long' is too ingrained and traditional to change that now.
Linus
Tejun Heo
maintainerRe: [PATCH 01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts
Hello,
Quoted 8 lines · Linus Torvalds
include/linux/rhashtable.h static inline struct rhash_lock_head __rcu **rht_bucket_insert( · line 328
Quoted 6 lines · Tejun Heo
static inline void rht_lock(struct
bucket_table*tbl,include/linux/rhashtable.h +2
-1- struct rhash_lock_head __rcu **bkt) +struct rhash_lock_head __rcu **bkt, + unsigned long *flags)
Quoted 8 lines
I guess it doesn't matter as long as this actually gets inlined, but wouldn't it be better to have
flags = rht_lock(..); ... rht_unlock(.., flags);as the calling convention? Rather than passing a pointer to the stack around.
Sure thing.
Quoted 3 lines
That's what the native
_raw_spin_lock_irqsave()interface is (even if "spin_lock_irqsave()" itself for historical reasons uses that inline asm-like "pass argument by reference *without* using a pointer")
Yeah, it always feels kinda weird to wrap irqsave/restore due to the special reference passing.
Quoted 3 lines
And gaah, we should have made 'flags' be a real type long ago, but I guess 'unsigned long' is too ingrained and traditional to change that now.
Hahaha, that's gonna be an epic patchset.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH v2 1/31 rhashtable: Allow rhashtable to be used from irq-safe contexts
In reply to Tejun Heorhashtable currently only does bh-safe synchronization making it impossible to use from irq-safe contexts. Switch it to use irq-safe synchronization to remove the restriction.
v2: Update the lock functions to return the ulong flags value and unlock
functions to take the value directly instead of passing around the pointer. Suggested by Linus.
--- include/linux/rhashtable.h | 61 ++++++++++++++++++++++++++------------------- lib/rhashtable.c | 16 +++++++---- 2 files changed, 46 insertions(+), 31 deletions(-)
include/linux/rhashtable.h +36 -25
@@ -323,29 +323,36 @@ static inline struct rhash_lock_head __r* When we write to a bucket without unlocking, we use rht_assign_locked(). */ -static inline void rht_lock (struct bucket_table *tbl, -struct rhash_lock_head __rcu **bkt) +static inline unsigned long rht_lock (struct bucket_table *tbl, +struct rhash_lock_head __rcu **bkt) { -local_bh_disable (); +unsigned long flags; + +local_irq_save (flags);bit_spin_lock (0 , (unsigned long *)bkt);lock_map_acquire (&tbl->dep_map); +return flags; } -static inline void rht_lock_nested (struct bucket_table *tbl, -struct rhash_lock_head __rcu **bucket, -unsigned int subclass) +static inline unsigned long rht_lock_nested (struct bucket_table *tbl, +struct rhash_lock_head __rcu **bucket, +unsigned int subclass) { -local_bh_disable (); +unsigned long flags; + +local_irq_save (flags);bit_spin_lock (0 , (unsigned long *)bucket);lock_acquire_exclusive (&tbl->dep_map, subclass,0 ,NULL , _THIS_IP_); +return flags; }static inline void rht_unlock (struct bucket_table *tbl, -struct rhash_lock_head __rcu **bkt) +struct rhash_lock_head __rcu **bkt, +unsigned long flags) {lock_map_release (&tbl->dep_map);bit_spin_unlock (0 , (unsigned long *)bkt); -local_bh_enable (); +local_irq_restore (flags); } static inline struct rhash_head *__rht_ptr(
@@ -393,7 +400,8 @@ static inline void rht_assign_locked(strstatic inline void rht_assign_unlock (struct bucket_table *tbl,struct rhash_lock_head __rcu **bkt, -struct rhash_head *obj) +struct rhash_head *obj, +unsigned long flags) {if (rht_is_a_nulls (obj)) obj =NULL ;
@@ -401,7 +409,7 @@ static inline void rht_assign_unlock(strrcu_assign_pointer (*bkt, (void *)obj);preempt_enable ();__release (bitlock); -local_bh_enable (); +local_irq_restore (flags); }/**
@@ -706,6 +714,7 @@ static inline void *__rhashtable_insert_struct rhash_head __rcu **pprev;struct bucket_table *tbl;struct rhash_head *head; +unsigned long flags;unsigned int hash;int elasticity;void *data;
@@ -720,11 +729,11 @@ static inline void *__rhashtable_insert_if (!bkt) goto out; pprev =NULL ; -rht_lock (tbl, bkt); + flags =rht_lock (tbl, bkt);if (unlikely (rcu_access_pointer (tbl->future_tbl))) { slow_path: -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags);rcu_read_unlock ();return rhashtable_insert_slow (ht, key, obj); }
@@ -756,9 +765,9 @@ slow_path:RCU_INIT_POINTER (list->rhead.next, head);if (pprev) {rcu_assign_pointer (*pprev, obj); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); }else -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, flags); data =NULL ; goto out; }
@@ -785,7 +794,7 @@ slow_path: }atomic_inc (&ht->nelems); -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, flags);if (rht_grow_above_75 (ht, tbl))schedule_work (&ht->run_work);
@@ -797,7 +806,7 @@ out:return data; out_unlock: -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); goto out; }
@@ -991,6 +1000,7 @@ static inline int __rhashtable_remove_fastruct rhash_lock_head __rcu **bkt;struct rhash_head __rcu **pprev;struct rhash_head *he; +unsigned long flags;unsigned int hash;int err = -ENOENT ;
@@ -999,7 +1009,7 @@ static inline int __rhashtable_remove_faif (!bkt)return -ENOENT ; pprev =NULL ; -rht_lock (tbl, bkt); + flags =rht_lock (tbl, bkt);rht_for_each_from (he,rht_ptr (bkt, tbl, hash), tbl, hash) {struct rhlist_head *list;
@@ -1043,14 +1053,14 @@ static inline int __rhashtable_remove_faif (pprev) {rcu_assign_pointer (*pprev, obj); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); }else { -rht_assign_unlock (tbl, bkt, obj); +rht_assign_unlock (tbl, bkt, obj, flags); } goto unlocked; } -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); unlocked:if (err >0 ) {atomic_dec (&ht->nelems);
@@ -1143,6 +1153,7 @@ static inline int __rhashtable_replace_fstruct rhash_lock_head __rcu **bkt;struct rhash_head __rcu **pprev;struct rhash_head *he; +unsigned long flags;unsigned int hash;int err = -ENOENT ;
@@ -1158,7 +1169,7 @@ static inline int __rhashtable_replace_freturn -ENOENT ; pprev =NULL ; -rht_lock (tbl, bkt); + flags =rht_lock (tbl, bkt);rht_for_each_from (he,rht_ptr (bkt, tbl, hash), tbl, hash) {if (he != obj_old) {
@@ -1169,15 +1180,15 @@ static inline int __rhashtable_replace_frcu_assign_pointer (obj_new->next, obj_old->next);if (pprev) {rcu_assign_pointer (*pprev, obj_new); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); }else { -rht_assign_unlock (tbl, bkt, obj_new); +rht_assign_unlock (tbl, bkt, obj_new, flags); } err =0 ; goto unlocked; } -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); unlocked:return err;
lib/rhashtable.c +10 -6
@@ -231,6 +231,7 @@ static int rhashtable_rehash_one(structstruct rhash_head *head, *next, *entry;struct rhash_head __rcu **pprev =NULL ;unsigned int new_hash; +unsigned long flags;if (new_tbl->nest) goto out;
@@ -253,13 +254,14 @@ static int rhashtable_rehash_one(struct new_hash =head_hashfn (ht, new_tbl, entry); -rht_lock_nested (new_tbl, &new_tbl->buckets[new_hash],SINGLE_DEPTH_NESTING ); + flags =rht_lock_nested (new_tbl, &new_tbl->buckets[new_hash], +SINGLE_DEPTH_NESTING ); head =rht_ptr (new_tbl->buckets + new_hash, new_tbl, new_hash);RCU_INIT_POINTER (entry->next, head); -rht_assign_unlock (new_tbl, &new_tbl->buckets[new_hash], entry); +rht_assign_unlock (new_tbl, &new_tbl->buckets[new_hash], entry, flags);if (pprev)rcu_assign_pointer (*pprev, next);
@@ -276,18 +278,19 @@ static int rhashtable_rehash_chain(struc {struct bucket_table *old_tbl =rht_dereference (ht->tbl, ht);struct rhash_lock_head __rcu **bkt =rht_bucket_var (old_tbl, old_hash); +unsigned long flags;int err;if (!bkt)return 0 ; -rht_lock (old_tbl, bkt); + flags =rht_lock (old_tbl, bkt);while (!(err =rhashtable_rehash_one (ht, bkt, old_hash))) ;if (err == -ENOENT ) err =0 ; -rht_unlock (old_tbl, bkt); +rht_unlock (old_tbl, bkt, flags);return err; }
@@ -590,6 +593,7 @@ static void *rhashtable_try_insert(strucstruct bucket_table *new_tbl;struct bucket_table *tbl;struct rhash_lock_head __rcu **bkt; +unsigned long flags;unsigned int hash;void *data;
@@ -607,7 +611,7 @@ static void *rhashtable_try_insert(struc new_tbl =rht_dereference_rcu (tbl->future_tbl, ht); data =ERR_PTR (-EAGAIN ); }else { -rht_lock (tbl, bkt); + flags =rht_lock (tbl, bkt); data =rhashtable_lookup_one (ht, bkt, tbl, hash, key, obj); new_tbl = rhashtable_insert_one(ht, bkt, tbl,
@@ -615,7 +619,7 @@ static void *rhashtable_try_insert(strucif (PTR_ERR (new_tbl) != -EEXIST ) data =ERR_CAST (new_tbl); -rht_unlock (tbl, bkt); +rht_unlock (tbl, bkt, flags); } }while (!IS_ERR_OR_NULL (new_tbl));
Re: [PATCH v2 01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts
This patch was applied to netdev/net-next.git (master) by David S. Miller <[email protected]>:
Hello:
This patch was applied to netdev/net-next.git (master) by David S. Miller <[email protected]>:
Quoted 9 lines · On Tue, 6 Dec 2022 11:36:32 -1000 you wrote:
rhashtable currently only does bh-safe synchronization making it impossible to use from irq-safe contexts. Switch it to use irq-safe synchronization to remove the restriction.
v2: Update the lock functions to return the ulong flags value and unlock
functions to take the value directly instead of passing around the pointer. Suggested by Linus.[...]
Here is the summary with links:
- [v2,01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts
https://git.kernel.org/netdev/net-next/c/e47877c7aa82
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html
Tejun Heo
maintainerPATCH 2/31 cgroup: Implement cgroup_show_cftypes()
In reply to Tejun HeoImplement cgroup_show_cftypes() which shows and hides all cgroup files associated with the specified set of cgroup file types. CFTYPE_HIDDEN flag is added so that files can be created hidden from the get-go.
cgroup_show_cftypes() can be used whether the cftypes are added or not. It also combines with cgroup_show_file() so that a given file is visible iff both its cftype and cfile are visible.
This will be used by a new sched_class to selectively show and hide CPU controller interface files depending on whether they're supported.
--- include/linux/cgroup-defs.h | 8 +++ include/linux/cgroup.h | 1 + kernel/cgroup/cgroup.c | 97 ++++++++++++++++++++++++++++++++++--- 3 files changed, 99 insertions(+), 7 deletions(-)
include/linux/cgroup-defs.h +8 -0
@@ -127,12 +127,18 @@ enum {CFTYPE_WORLD_WRITABLE = (1 <<4 ),/* (DON'T USE FOR NEW FILES) S_IWUGO */ CFTYPE_DEBUG = (1 <<5 ),/* create when cgroup_debug */ +CFTYPE_HIDDEN = (1 <<6 ),/* file type hidden, see cgroup_show_cftypes() */ +/* internal flags, do not use outside cgroup core proper */ __CFTYPE_ONLY_ON_DFL = (1 <<16 ),/* only on default hierarchy */ __CFTYPE_NOT_ON_DFL = (1 <<17 ),/* not on default hierarchy */ __CFTYPE_ADDED = (1 << 18), }; +enum cfile_flags { +CFILE_HIDDEN = (1 <<0 ),/* file instance hidden */ +}; +/* * cgroup_file is the handle for a file instance created in a cgroup which * is used, for example, to generate file changed notifications. This can
@@ -140,7 +146,9 @@ enum {*/ struct cgroup_file {/* do not access any fields from outside cgroup core */ +struct cftype *cft;struct kernfs_node *kn; +unsigned int flags;unsigned long notified_at;struct timer_list notify_timer; };
include/linux/cgroup.h +1 -0
@@ -114,6 +114,7 @@ int cgroup_transfer_tasks(struct cgroup *to, struct cgroup *from);int cgroup_add_dfl_cftypes (struct cgroup_subsys *ss,struct cftype *cfts);int cgroup_add_legacy_cftypes (struct cgroup_subsys *ss,struct cftype *cfts);int cgroup_rm_cftypes (struct cftype *cfts); +void cgroup_show_cftype (struct cftype *cft,bool show);void cgroup_file_notify (struct cgroup_file *cfile);void cgroup_file_show (struct cgroup_file *cfile,bool show);
kernel/cgroup/cgroup.c +90 -7
127 lines not on this page · raw message
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 3/31 BPF: Add @prog to bpf_struct_ops->check_member()
In reply to Tejun HeoPass an extra @prog parameter to bpf_struct_ops->check_member(). This will be used in the future to verify @prog->aux->sleepable per-operation so that a subset of operations in a struct_ops can be sleepable.
--- include/linux/bpf.h | 3 ++- kernel/bpf/verifier.c | 2 +- net/ipv4/bpf_tcp_ca.c | 3 ++- 3 files changed, 5 insertions(+), 3 deletions(-)
include/linux/bpf.h +2 -1
@@ -1337,7 +1337,8 @@ struct bpf_struct_ops {const struct bpf_verifier_ops *verifier_ops;int (*init)(struct btf *btf);int (*check_member)(const struct btf_type *t, -const struct btf_member *member); +const struct btf_member *member, +struct bpf_prog *prog);int (*init_member)(const struct btf_type *t,const struct btf_member *member,void *kdata,const void *udata);
kernel/bpf/verifier.c +1 -1
@@ -14928,7 +14928,7 @@ static int check_struct_ops_btf_id(struct bpf_verifier_env *env) }if (st_ops->check_member) { -int err = st_ops->check_member (t, member); +int err = st_ops->check_member (t, member, prog);if (err) { verbose(env, "attach to unsupported member %s of struct %s\n",
net/ipv4/bpf_tcp_ca.c +2 -1
@@ -247,7 +247,8 @@ static int bpf_tcp_ca_init_member(const struct btf_type *t, }static int bpf_tcp_ca_check_member (const struct btf_type *t, -const struct btf_member *member) +const struct btf_member *member, +struct bpf_prog *prog) {if (is_unsupported (__btf_member_bit_offset (t, member) /8 ))return -ENOTSUPP ;
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 4/31 sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
In reply to Tejun HeoA new sched_clas needs a bit more control over forking. This patch makes the following changes:
* Add sched_cancel_fork() which is called if fork fails after sched_fork() succeeds so that the preparation can be undone.
* Allow sched_cgroup_fork() to fail.
Neither is used yet and this patch shouldn't cause any behavior changes.
--- include/linux/sched/task.h | 3 ++- kernel/fork.c | 15 ++++++++++----- kernel/sched/core.c | 8 +++++++- 3 files changed, 19 insertions(+), 7 deletions(-)
include/linux/sched/task.h +2 -1
@@ -58,7 +58,8 @@ extern asmlinkage void schedule_tail(struct task_struct *prev);extern void init_idle (struct task_struct *idle,int cpu);extern int sched_fork (unsigned long clone_flags,struct task_struct *p); -extern void sched_cgroup_fork (struct task_struct *p,struct kernel_clone_args *kargs); +extern int sched_cgroup_fork (struct task_struct *p,struct kernel_clone_args *kargs); +extern void sched_cancel_fork (struct task_struct *p);extern void sched_post_fork (struct task_struct *p);extern void sched_dead (struct task_struct *p);
kernel/fork.c +10 -5
@@ -2226,7 +2226,7 @@ static __latent_entropy struct task_struct *copy_process( retval =perf_event_init_task (p, clone_flags);if (retval) - goto bad_fork_cleanup_policy; + goto bad_fork_sched_cancel_fork; retval =audit_alloc (p);if (retval) goto bad_fork_cleanup_perf;
@@ -2367,7 +2367,9 @@ static __latent_entropy struct task_struct *copy_process(* cgroup specific, it unconditionally needs to place the task on a * runqueue. */ -sched_cgroup_fork (p, args); + retval =sched_cgroup_fork (p, args); +if (retval) + goto bad_fork_cancel_cgroup;/* * From this point on we must avoid any synchronous user-space
@@ -2419,13 +2421,13 @@ static __latent_entropy struct task_struct *copy_process(/* Don't start children in a dying pid namespace */ if (unlikely (!(ns_of_pid (pid)->pid_allocated &PIDNS_ADDING ))) { retval = -ENOMEM ; - goto bad_fork_cancel_cgroup; + goto bad_fork_core_free; }/* Let kill terminate clone/fork in the middle */ if (fatal_signal_pending (current)) { retval = -EINTR ; - goto bad_fork_cancel_cgroup; + goto bad_fork_core_free; }init_task_pid_links (p);
@@ -2492,10 +2494,11 @@ static __latent_entropy struct task_struct *copy_process(return p; -bad_fork_cancel_cgroup: +bad_fork_core_free:sched_core_free (p);spin_unlock (¤t->sighand->siglock);write_unlock_irq (&tasklist_lock); +bad_fork_cancel_cgroup:cgroup_cancel_fork (p, args); bad_fork_put_pidfd:if (clone_flags &CLONE_PIDFD ) {
@@ -2534,6 +2537,8 @@ static __latent_entropy struct task_struct *copy_process(audit_free (p); bad_fork_cleanup_perf:perf_event_free_task (p); +bad_fork_sched_cancel_fork: +sched_cancel_fork (p); bad_fork_cleanup_policy:lockdep_free_task (p);#ifdef CONFIG_NUMA
kernel/sched/core.c +7 -1
@@ -4604,7 +4604,7 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)return 0 ; } -void sched_cgroup_fork (struct task_struct *p,struct kernel_clone_args *kargs) +int sched_cgroup_fork (struct task_struct *p,struct kernel_clone_args *kargs) {unsigned long flags;
@@ -4631,6 +4631,12 @@ void sched_cgroup_fork(struct task_struct *p, struct kernel_clone_args *kargs)if (p->sched_class->task_fork) p->sched_class->task_fork (p);raw_spin_unlock_irqrestore (&p->pi_lock, flags); + +return 0 ; +} + +void sched_cancel_fork (struct task_struct *p) +{ }void sched_post_fork (struct task_struct *p)
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 04/31] sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
Quoted 1 line · Tejun Heo
A new
sched_clasneeds a bit more control over forking. This patch makes the
^
(insufficient s's)Quoted 8 lines
following changes:
* Add
sched_cancel_fork()which is called if fork fails aftersched_fork()succeeds so that the preparation can be undone.* Allow
sched_cgroup_fork()to fail.Neither is used yet and this patch shouldn't cause any behavior changes.
Fails to explain why this would be needed and why that would be a good thing. IOW, total lack of justification.
Tejun Heo
maintainerRe: [PATCH 04/31] sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
Quoted 4 lines · Peter Zijlstra
Quoted 1 line · Tejun Heo
A new
sched_clasneeds a bit more control over forking. This patch makes the^ (insufficient s's)
Will update.
Quoted 11 lines
Quoted 8 lines
following changes:
* Add
sched_cancel_fork()which is called if fork fails aftersched_fork()succeeds so that the preparation can be undone.* Allow
sched_cgroup_fork()to fail.Neither is used yet and this patch shouldn't cause any behavior changes.
Fails to explain why this would be needed and why that would be a good thing. IOW, total lack of justification.
This is because sched_ext calls out to BPF scheduler's prepare_enable() operation to prepare the task. The operation is allowed to fail (e.g. it might need to allocate something which can fail), so we need a way back back out of it.
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 04/31] sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
Quoted 17 lines · Tejun Heo
Quoted 4 lines · Peter Zijlstra
Quoted 1 line · Tejun Heo
A new
sched_clasneeds a bit more control over forking. This patch makes the^ (insufficient s's)Will update.
Quoted 9 lines
Quoted 8 lines
following changes:
* Add
sched_cancel_fork()which is called if fork fails aftersched_fork()succeeds so that the preparation can be undone.* Allow
sched_cgroup_fork()to fail.Neither is used yet and this patch shouldn't cause any behavior changes.
Quoted 7 lines
Quoted 2 lines
Fails to explain why this would be needed and why that would be a good thing. IOW, total lack of justification.
This is because
sched_extcalls out to BPF scheduler'sprepare_enable()operation to prepare the task. The operation is allowed to fail (e.g. it might need to allocate something which can fail), so we need a way back back out of it.
sched_fork() can already fail; why isn't that a suitable location to do what needs doing?
Tejun Heo
maintainerRe: [PATCH 04/31] sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Tejun Heo
Quoted 4 lines · Peter Zijlstra
Quoted 1 line · Tejun Heo
A new
sched_clasneeds a bit more control over forking. This patch makes the^ (insufficient s's)Will update.
Quoted 11 lines
Quoted 8 lines
following changes:
* Add
sched_cancel_fork()which is called if fork fails aftersched_fork()succeeds so that the preparation can be undone.* Allow
sched_cgroup_fork()to fail.Neither is used yet and this patch shouldn't cause any behavior changes.
Fails to explain why this would be needed and why that would be a good thing. IOW, total lack of justification.
Quoted 7 lines
Quoted 4 lines
This is because
sched_extcalls out to BPF scheduler'sprepare_enable()operation to prepare the task. The operation is allowed to fail (e.g. it might need to allocate something which can fail), so we need a way back back out of it.
sched_fork()can already fail; why isn't that a suitable location to do what needs doing?
Because SCX's ops.prepare_enable() wants the cgroup (p->sched_task_group) to be initialized in case the BPF scheduler wants to perform cgroup related initializations.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 5/31 sched: Add sched_class->reweight_task()
In reply to Tejun HeoCurrently, during a task weight change, sched core directly calls reweight_task() defined in fair.c if @p is on CFS. Let's make it a proper sched_class operation instead. CFS's reweight_task() is renamed to reweight_task_fair() and now called through sched_class.
While it turns a direct call into an indirect one, set_load_weight() isn't called from a hot path and this change shouldn't cause any noticeable difference. This will be used to implement reweight_task for other scheduler classes.
This will be used by a new sched_class to track weight changes.
--- kernel/sched/core.c | 4 ++-- kernel/sched/fair.c | 3 ++- kernel/sched/sched.h | 4 ++-- 3 files changed, 6 insertions(+), 5 deletions(-)
kernel/sched/core.c +2 -2
@@ -1275,8 +1275,8 @@ static void set_load_weight(struct task_struct *p, bool update_load)* SCHED_OTHER tasks have to update their load when changing their * weight */ -if (update_load && p->sched_class == &fair_sched_class) { -reweight_task (p, prio); +if (update_load && p->sched_class->reweight_task) { + p->sched_class->reweight_task (task_rq (p), p, prio); }else { load->weight =scale_load (sched_prio_to_weight[prio]); load->inv_weight = sched_prio_to_wmult[prio];
kernel/sched/fair.c +2 -1
@@ -3330,7 +3330,7 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, } -void reweight_task (struct task_struct *p,int prio) +static void reweight_task_fair (struct rq *rq,struct task_struct *p,int prio) {struct sched_entity *se = &p->se;struct cfs_rq *cfs_rq =cfs_rq_of (se);
@@ -12176,6 +12176,7 @@ DEFINE_SCHED_CLASS(fair) = { .task_tick = task_tick_fair, .task_fork = task_fork_fair, + .reweight_task = reweight_task_fair, .prio_changed = prio_changed_fair, .switched_from = switched_from_fair, .switched_to = switched_to_fair,
kernel/sched/sched.h +2 -2
@@ -2193,6 +2193,8 @@ struct sched_class {*/ void (*switched_from)(struct rq *this_rq,struct task_struct *task);void (*switched_to) (struct rq *this_rq,struct task_struct *task); +void (*reweight_task)(struct rq *this_rq,struct task_struct *task, +int newprio);void (*prio_changed) (struct rq *this_rq,struct task_struct *task,int oldprio);
@@ -2345,8 +2347,6 @@ extern void init_sched_dl_class(void);extern void init_sched_rt_class (void );extern void init_sched_fair_class (void ); -extern void reweight_task (struct task_struct *p,int prio); -extern void resched_curr (struct rq *rq);extern void resched_cpu (int cpu);
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 05/31] sched: Add sched_class->reweight_task()
kernel/sched/sched.h struct sched_class { · line 2199
Quoted 12 lines · Tejun Heo
kernel/sched/sched.h +2
-0@@ -2193,6 +2193,8 @@ struct sched_class {*/ void (*switched_from)(struct rq *this_rq,struct task_struct *task);void (*switched_to) (struct rq *this_rq,struct task_struct *task); +void (*reweight_task)(struct rq *this_rq,struct task_struct *task, +int newprio);void (*prio_changed) (struct rq *this_rq,struct task_struct *task,int oldprio);
Hurmph.. this further propagate the existing problem of thinking that 'prio' is a useful concept in general (it isn't).
Yeah, you're just following precedent here, but still :/
Tejun Heo
maintainerRe: [PATCH 05/31] sched: Add sched_class->reweight_task()
Hello,
Quoted 16 lines · Peter Zijlstra
kernel/sched/sched.h struct sched_class { · line 2199
Quoted 12 lines · Tejun Heo
kernel/sched/sched.h +2
-0@@ -2193,6 +2193,8 @@ struct sched_class {*/ void (*switched_from)(struct rq *this_rq,struct task_struct *task);void (*switched_to) (struct rq *this_rq,struct task_struct *task); +void (*reweight_task)(struct rq *this_rq,struct task_struct *task, +int newprio);void (*prio_changed) (struct rq *this_rq,struct task_struct *task,int oldprio);Hurmph.. this further propagate the existing problem of thinking that 'prio' is a useful concept in general (it isn't).
I'm not quite following. Can you please expand on why prio isn't a generally useful concept?
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 05/31] sched: Add sched_class->reweight_task()
Quoted 20 lines · Tejun Heo
Hello,
Quoted 16 lines · Peter Zijlstra
kernel/sched/sched.h struct sched_class { · line 2199
Quoted 12 lines · Tejun Heo
kernel/sched/sched.h +2
-0@@ -2193,6 +2193,8 @@ struct sched_class {*/ void (*switched_from)(struct rq *this_rq,struct task_struct *task);void (*switched_to) (struct rq *this_rq,struct task_struct *task); +void (*reweight_task)(struct rq *this_rq,struct task_struct *task, +int newprio);void (*prio_changed) (struct rq *this_rq,struct task_struct *task,int oldprio);Hurmph.. this further propagate the existing problem of thinking that 'prio' is a useful concept in general (it isn't).
Quoted 2 lines
I'm not quite following. Can you please expand on why prio isn't a generally useful concept?
The whole fixed vs dynamic priority scheduling thing. Specifically SCHED_DEADLINE implements a dynamic priority scheme using the sporadic task model which just doesn't map well to this single prio value (notably every SCHED_DEADLINE task has prio -1, making it impossible to order SCHED_DEADLINE tasks based on this).
Tejun Heo
maintainerRe: [PATCH 05/31] sched: Add sched_class->reweight_task()
Quoted 11 lines · Peter Zijlstra
Quoted 5 lines
Quoted 2 lines
Hurmph.. this further propagate the existing problem of thinking that 'prio' is a useful concept in general (it isn't).
I'm not quite following. Can you please expand on why prio isn't a generally useful concept?
The whole fixed vs dynamic priority scheduling thing. Specifically
SCHED_DEADLINEimplements a dynamic priority scheme using the sporadic task model which just doesn't map well to this single prio value (notably everySCHED_DEADLINEtask has prio -1, making it impossible to orderSCHED_DEADLINEtasks based on this).
I see, so the expressive power isn't sufficient to cover some use cases. Yeah, I mean, it's limited and we can add whatever that's necessary but given that there are many use cases that make use of priorities, I don't think SCX can skip supporting it.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 6/31 sched: Add sched_class->switching_to() and expose check_class_changing/changed()
In reply to Tejun HeoWhen a task switches to a new sched_class, the prev and new classes are notified through ->switched_from() and ->switched_to(), respectively, after the switching is done. However, a new sched_class needs to prepare the task state before it is enqueued on the new class for the first time.
This patch adds ->switching_to() which is called during sched_class switch through check_class_changing() before the task is restored and exposes check_class_changing/changed() in kernel/sched/sched.h.
This is a prep patch and doesn't cause any behavior changes. The new operation and exposed functions aren't used yet.
--- kernel/sched/core.c | 20 +++++++++++++++++--- kernel/sched/sched.h | 7 +++++++ 2 files changed, 24 insertions(+), 3 deletions(-)
kernel/sched/core.c +17 -3
@@ -2151,6 +2151,17 @@ inline int task_curr(const struct task_struct *p)return cpu_curr (task_cpu (p)) == p; } +/* +* ->switching_to() is called with the pi_lock and rq_lock held and must not +* mess with locking. +*/ +void check_class_changing (struct rq *rq,struct task_struct *p, +const struct sched_class *prev_class) +{ +if (prev_class != p->sched_class && p->sched_class->switching_to) + p->sched_class->switching_to (rq, p); +} +/* * switched_from, switched_to and prio_changed must _NOT_ drop rq->lock, * use the balance_callback list if you want balancing.
@@ -2158,9 +2169,9 @@ inline int task_curr(const struct task_struct *p)* this means any call to check_class_changed() must be followed by a call to * balance_callback(). */ -static inline void check_class_changed (struct rq *rq,struct task_struct *p, -const struct sched_class *prev_class, -int oldprio) +void check_class_changed (struct rq *rq,struct task_struct *p, +const struct sched_class *prev_class, +int oldprio) {if (prev_class != p->sched_class) {if (prev_class->switched_from)
@@ -6974,6 +6985,7 @@ void rt_mutex_setprio(struct task_struct *p, struct task_struct *pi_task) }__setscheduler_prio (p, prio); +check_class_changing (rq, p, prev_class);if (queued)enqueue_task (rq, p, queue_flag);
@@ -7603,6 +7615,8 @@ static int __sched_setscheduler(struct task_struct *p, }__setscheduler_uclamp (p, attr); +check_class_changing (rq, p, prev_class); +if (queued) {/* * We enqueue to tail when the priority of a task is
kernel/sched/sched.h +7 -0
@@ -2191,6 +2191,7 @@ struct sched_class {* cannot assume the switched_from/switched_to pair is serialized by * rq->lock. They are however serialized by p->pi_lock. */ +void (*switching_to) (struct rq *this_rq,struct task_struct *task);void (*switched_from)(struct rq *this_rq,struct task_struct *task);void (*switched_to) (struct rq *this_rq,struct task_struct *task); void (*reweight_task)(struct rq *this_rq, struct task_struct *task,
@@ -2427,6 +2428,12 @@ static inline void sub_nr_running(struct rq *rq, unsigned count)extern void activate_task (struct rq *rq,struct task_struct *p,int flags);extern void deactivate_task (struct rq *rq,struct task_struct *p,int flags); +extern void check_class_changing (struct rq *rq,struct task_struct *p, +const struct sched_class *prev_class); +extern void check_class_changed (struct rq *rq,struct task_struct *p, +const struct sched_class *prev_class, +int oldprio); +extern void check_preempt_curr (struct rq *rq,struct task_struct *p,int flags);#ifdef CONFIG_PREEMPT_RT
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 06/31] sched: Add sched_class->switching_to() and expose check_class_changing/changed()
Quoted 4 lines · Tejun Heo
When a task switches to a new
sched_class, the prev and new classes are notified through ->switched_from() and ->switched_to(), respectively, after the switching is done. However, a newsched_classneeds to prepare the task state before it is enqueued on the new class for the first time.
How and why isn't sched_fork() sufficient?
Tejun Heo
maintainerRe: [PATCH 06/31] sched: Add sched_class->switching_to() and expose check_class_changing/changed()
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Tejun Heo
When a task switches to a new
sched_class, the prev and new classes are notified through ->switched_from() and ->switched_to(), respectively, after the switching is done. However, a newsched_classneeds to prepare the task state before it is enqueued on the new class for the first time.How and why isn't
sched_fork()sufficient?
sched_ext has callbacks which allow the BPF scheduler to keep track of relevant task states (like priority and cpumask). Those callbacks aren't called while a task isn't on sched_ext. When a task comes back to SCX, we wanna tell the BPF scheduler the up-to-date state before the task gets enqueued, so the need for a hook which is called before the switching is committed.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 7/31 sched: Factor out cgroup weight conversion functions
In reply to Tejun HeoFactor out sched_weight_from/to_cgroup() which convert between scheduler shares and cgroup weight. No functional change. The factored out functions will be used by a new sched_class.
--- kernel/sched/core.c | 28 +++++++++++++--------------- kernel/sched/sched.h | 18 ++++++++++++++++++ 2 files changed, 31 insertions(+), 15 deletions(-)
kernel/sched/core.c +13 -15
@@ -10977,29 +10977,27 @@ static int cpu_extra_stat_show(struct seq_file *sf, }#ifdef CONFIG_FAIR_GROUP_SCHED + +static unsigned long tg_weight (struct task_group *tg) +{ +return scale_load_down (tg->shares); +} +static u64 cpu_weight_read_u64 (struct cgroup_subsys_state *css,struct cftype *cft) { -struct task_group *tg =css_tg (css); -u64 weight =scale_load_down (tg->shares); - -return DIV_ROUND_CLOSEST_ULL (weight *CGROUP_WEIGHT_DFL ,1024 ); +return sched_weight_to_cgroup (tg_weight (css_tg (css))); }static int cpu_weight_write_u64 (struct cgroup_subsys_state *css, -struct cftype *cft,u64 weight) +struct cftype *cft,u64 cgrp_weight) { -/* -* cgroup weight knobs should use the common MIN, DFL and MAX -* values which are 1, 100 and 10000 respectively. While it loses -* a bit of range on both ends, it maps pretty well onto the shares -* value used by scheduler and the round-trip conversions preserve -* the original value over the entire range. -*/ -if (weight <CGROUP_WEIGHT_MIN || weight >CGROUP_WEIGHT_MAX ) +unsigned long weight; + +if (cgrp_weight <CGROUP_WEIGHT_MIN || cgrp_weight >CGROUP_WEIGHT_MAX )return -ERANGE ; - weight =DIV_ROUND_CLOSEST_ULL (weight *1024 ,CGROUP_WEIGHT_DFL ); + weight =sched_weight_from_cgroup (cgrp_weight);return sched_group_set_shares (css_tg (css),scale_load (weight)); }
@@ -11007,7 +11005,7 @@ static int cpu_weight_write_u64(struct cgroup_subsys_state *css,static s64 cpu_weight_nice_read_s64 (struct cgroup_subsys_state *css,struct cftype *cft) { -unsigned long weight =scale_load_down (css_tg (css)->shares); +unsigned long weight =tg_weight (css_tg (css));int last_delta =INT_MAX ;int prio, delta;
kernel/sched/sched.h +18 -0
@@ -435,6 +435,24 @@ struct task_group {#define MAX_SHARES (1UL << 18)#endif +/* +* cgroup weight knobs should use the common MIN, DFL and MAX values which are +* 1, 100 and 10000 respectively. While it loses a bit of range on both ends, it +* maps pretty well onto the shares value used by scheduler and the round-trip +* conversions preserve the original value over the entire range. +*/ +static inline unsigned long sched_weight_from_cgroup (unsigned long cgrp_weight) +{ +return DIV_ROUND_CLOSEST_ULL (cgrp_weight *1024 ,CGROUP_WEIGHT_DFL ); +} + +static inline unsigned long sched_weight_to_cgroup (unsigned long weight) +{ + return clamp_t(unsigned long, +DIV_ROUND_CLOSEST_ULL (weight *CGROUP_WEIGHT_DFL ,1024 ), +CGROUP_WEIGHT_MIN ,CGROUP_WEIGHT_MAX ); +} +typedef int (*tg_visitor )(struct task_group *,void *); extern int walk_tg_tree_from(struct task_group *from,
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 8/31 sched: Expose css_tg() and __setscheduler_prio() in kernel/sched/sched.h
In reply to Tejun HeoThese will be used by a new sched_class.
--- kernel/sched/core.c | 7 +------ kernel/sched/sched.h | 7 +++++++ 2 files changed, 8 insertions(+), 6 deletions(-)
kernel/sched/core.c +1 -6
@@ -6845,7 +6845,7 @@ int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flag }EXPORT_SYMBOL (default_wake_function); -static void __setscheduler_prio (struct task_struct *p,int prio) +void __setscheduler_prio (struct task_struct *p,int prio) {if (dl_prio (prio)) p->sched_class = &dl_sched_class;
@@ -10245,11 +10245,6 @@ void sched_move_task(struct task_struct *tsk)task_rq_unlock (rq, tsk, &rf); } -static inline struct task_group *css_tg (struct cgroup_subsys_state *css) -{ - return css ? container_of(css, struct task_group, css) : NULL; -} -static struct cgroup_subsys_state *cpu_cgroup_css_alloc (struct cgroup_subsys_state *parent_css) {
kernel/sched/sched.h +7 -0
@@ -469,6 +469,11 @@ static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)return walk_tg_tree_from (&root_task_group, down, up, data); } +static inline struct task_group *css_tg (struct cgroup_subsys_state *css) +{ + return css ? container_of(css, struct task_group, css) : NULL; +} +extern int tg_nop (struct task_group *tg,void *data);extern void free_fair_sched_group (struct task_group *tg);
@@ -493,6 +498,8 @@ extern long sched_group_rt_runtime(struct task_group *tg);extern long sched_group_rt_period (struct task_group *tg);extern int sched_rt_can_attach (struct task_group *tg,struct task_struct *tsk); +extern void __setscheduler_prio (struct task_struct *p,int prio); +extern struct task_group *sched_create_group (struct task_group *parent);extern void sched_online_group (struct task_group *tg,struct task_group *parent);
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 08/31] sched: Expose css_tg() and __setscheduler_prio() in kernel/sched/sched.h
Quoted 1 line · Tejun Heo
These will be used by a new
sched_class.
Uhhh.. wtf does a policy need __setscheduler_prio() for?
Tejun Heo
maintainerRe: [PATCH 08/31] sched: Expose css_tg() and __setscheduler_prio() in kernel/sched/sched.h
Quoted 4 lines · Peter Zijlstra
Quoted 1 line · Tejun Heo
These will be used by a new
sched_class.Uhhh.. wtf does a policy need
__setscheduler_prio()for?
Whether a task is on sched_ext or not is determined by a few factors - the chosen sched class of the task, whether the BPF scheduler is loaded and whether it's using scx_bpf_switch_all(). That selection logic is implemented in __setscheduler_prio(). When the BPF scheduler gets initialized and exited, the selection changes and sched_ext needs to walk the tasks reapplying the selection logic, so the export.
This ties together with the sched_enq_and_set_task() that you replied to in another thread. Imma continue there.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 9/31 sched: Enumerate CPU cgroup file types
In reply to Tejun HeoRename cpu[_legacy]_files to cpu[_legacy]_cftypes for clarity and add cpu_cftype_id which enumerates every cgroup2 interface file type. This doesn't make any functional difference now. The enums will be used to access specific cftypes by a new sched_class to selectively show CPU controller interface files.
--- kernel/sched/core.c | 22 +++++++++++----------- kernel/sched/sched.h | 21 +++++++++++++++++++++ 2 files changed, 32 insertions(+), 11 deletions(-)
kernel/sched/core.c +11 -11
@@ -10882,7 +10882,7 @@ static int cpu_idle_write_s64(struct cgroup_subsys_state *css, }#endif -static struct cftype cpu_legacy_files[] = { +static struct cftype cpu_legacy_cftypes[] = {#ifdef CONFIG_FAIR_GROUP_SCHED { .name = "shares",
@@ -11089,21 +11089,21 @@ static ssize_t cpu_max_write(struct kernfs_open_file *of, }#endif -static struct cftype cpu_files[] = { +struct cftype cpu_cftypes[CPU_CFTYPE_CNT +1 ] = { #ifdef CONFIG_FAIR_GROUP_SCHED - { + [CPU_CFTYPE_WEIGHT] = { .name ="weight" , .flags =CFTYPE_NOT_ON_ROOT , .read_u64 = cpu_weight_read_u64, .write_u64 = cpu_weight_write_u64, }, - { + [CPU_CFTYPE_WEIGHT_NICE ] = { .name ="weight.nice" , .flags =CFTYPE_NOT_ON_ROOT , .read_s64 = cpu_weight_nice_read_s64, .write_s64 = cpu_weight_nice_write_s64, }, - { + [CPU_CFTYPE_IDLE ] = { .name ="idle" , .flags =CFTYPE_NOT_ON_ROOT , .read_s64 = cpu_idle_read_s64,
@@ -11111,13 +11111,13 @@ static struct cftype cpu_files[] = { },#endif #ifdef CONFIG_CFS_BANDWIDTH - { + [CPU_CFTYPE_MAX] = { .name = "max", .flags = CFTYPE_NOT_ON_ROOT, .seq_show = cpu_max_show, .write = cpu_max_write, }, - { + [CPU_CFTYPE_MAX_BURST] = { .name = "max.burst", .flags = CFTYPE_NOT_ON_ROOT, .read_u64 = cpu_cfs_burst_read_u64,
@@ -11125,13 +11125,13 @@ static struct cftype cpu_files[] = { },#endif #ifdef CONFIG_UCLAMP_TASK_GROUP - { + [CPU_CFTYPE_UCLAMP_MIN] = { .name = "uclamp.min", .flags = CFTYPE_NOT_ON_ROOT, .seq_show = cpu_uclamp_min_show, .write = cpu_uclamp_min_write, }, - { + [CPU_CFTYPE_UCLAMP_MAX] = { .name = "uclamp.max", .flags = CFTYPE_NOT_ON_ROOT, .seq_show = cpu_uclamp_max_show,
@@ -11151,8 +11151,8 @@ struct cgroup_subsys cpu_cgrp_subsys = { .can_attach = cpu_cgroup_can_attach, #endif .attach = cpu_cgroup_attach, - .legacy_cftypes = cpu_legacy_files, - .dfl_cftypes = cpu_files, + .legacy_cftypes = cpu_legacy_cftypes, + .dfl_cftypes = cpu_cftypes, .early_init = true, .threaded = true, };
kernel/sched/sched.h +21 -0
@@ -3215,4 +3215,25 @@ static inline void update_current_exec_runtime(struct task_struct *curr, cgroup_account_cputime(curr, delta_exec); } +#ifdef CONFIG_CGROUP_SCHED +enum cpu_cftype_id { +#ifdef CONFIG_FAIR_GROUP_SCHED +CPU_CFTYPE_WEIGHT , +CPU_CFTYPE_WEIGHT_NICE , +CPU_CFTYPE_IDLE , +#endif +#ifdef CONFIG_CFS_BANDWIDTH +CPU_CFTYPE_MAX , +CPU_CFTYPE_MAX_BURST , +#endif +#ifdef CONFIG_UCLAMP_TASK_GROUP +CPU_CFTYPE_UCLAMP_MIN , +CPU_CFTYPE_UCLAMP_MAX , +#endif +CPU_CFTYPE_CNT , +}; + +extern struct cftype cpu_cftypes[CPU_CFTYPE_CNT +1 ]; +#endif /* CONFIG_CGROUP_SCHED */ +#endif /* _KERNEL_SCHED_SCHED_H */
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 10/31 sched: Add @reason to sched_class->rq_{on|off}line()
In reply to Tejun Heo->rq_{on|off}line are called either during CPU hotplug or cpuset partition updates. Let's add an argument to distinguish the two cases. The argument will be used by a new sched_class to track CPU hotplug events.
--- kernel/sched/core.c | 12 ++++++------ kernel/sched/deadline.c | 4 ++-- kernel/sched/fair.c | 4 ++-- kernel/sched/rt.c | 4 ++-- kernel/sched/sched.h | 13 +++++++++---- kernel/sched/topology.c | 4 ++-- 6 files changed, 23 insertions(+), 18 deletions(-)
kernel/sched/core.c +6 -6
@@ -9286,7 +9286,7 @@ static inline void balance_hotplug_wait(void)#endif /* CONFIG_HOTPLUG_CPU */ -void set_rq_online (struct rq *rq) +void set_rq_online (struct rq *rq,enum rq_onoff_reason reason) {if (!rq->online) {const struct sched_class *class;
@@ -9296,19 +9296,19 @@ void set_rq_online(struct rq *rq)for_each_class (class) {if (class->rq_online) - class->rq_online (rq); + class->rq_online (rq, reason); } } } -void set_rq_offline (struct rq *rq) +void set_rq_offline (struct rq *rq,enum rq_onoff_reason reason) {if (rq->online) {const struct sched_class *class;for_each_class (class) {if (class->rq_offline) - class->rq_offline (rq); + class->rq_offline (rq, reason); }cpumask_clear_cpu (rq->cpu, rq->rd->online);
@@ -9404,7 +9404,7 @@ int sched_cpu_activate(unsigned int cpu)rq_lock_irqsave (rq, &rf);if (rq->rd) {BUG_ON (!cpumask_test_cpu (cpu, rq->rd->span)); -set_rq_online (rq); +set_rq_online (rq,RQ_ONOFF_HOTPLUG ); }rq_unlock_irqrestore (rq, &rf);
@@ -9449,7 +9449,7 @@ int sched_cpu_deactivate(unsigned int cpu)if (rq->rd) {update_rq_clock (rq);BUG_ON (!cpumask_test_cpu (cpu, rq->rd->span)); -set_rq_offline (rq); +set_rq_offline (rq,RQ_ONOFF_HOTPLUG ); }rq_unlock_irqrestore (rq, &rf);
kernel/sched/deadline.c +2 -2
@@ -2519,7 +2519,7 @@ static void set_cpus_allowed_dl(struct task_struct *p, }/* Assumes rq->lock is held */ -static void rq_online_dl (struct rq *rq) +static void rq_online_dl (struct rq *rq,enum rq_onoff_reason reason) {if (rq->dl.overloaded)dl_set_overload (rq);
@@ -2530,7 +2530,7 @@ static void rq_online_dl(struct rq *rq) }/* Assumes rq->lock is held */ -static void rq_offline_dl (struct rq *rq) +static void rq_offline_dl (struct rq *rq,enum rq_onoff_reason reason) {if (rq->dl.overloaded)dl_clear_overload (rq);
kernel/sched/fair.c +2 -2
@@ -11436,14 +11436,14 @@ void trigger_load_balance(struct rq *rq)nohz_balancer_kick (rq); } -static void rq_online_fair (struct rq *rq) +static void rq_online_fair (struct rq *rq,enum rq_onoff_reason reason) {update_sysctl ();update_runtime_enabled (rq); } -static void rq_offline_fair (struct rq *rq) +static void rq_offline_fair (struct rq *rq,enum rq_onoff_reason reason) {update_sysctl ();
kernel/sched/rt.c +2 -2
@@ -2470,7 +2470,7 @@ static void task_woken_rt(struct rq *rq, struct task_struct *p) }/* Assumes rq->lock is held */ -static void rq_online_rt (struct rq *rq) +static void rq_online_rt (struct rq *rq,enum rq_onoff_reason reason) {if (rq->rt.overloaded)rt_set_overload (rq);
@@ -2481,7 +2481,7 @@ static void rq_online_rt(struct rq *rq) }/* Assumes rq->lock is held */ -static void rq_offline_rt (struct rq *rq) +static void rq_offline_rt (struct rq *rq,enum rq_onoff_reason reason) {if (rq->rt.overloaded)rt_clear_overload (rq);
kernel/sched/sched.h +9 -4
@@ -2169,6 +2169,11 @@ extern const u32 sched_prio_to_wmult[40];#define RETRY_TASK ((void *)-1UL) +enum rq_onoff_reason { +RQ_ONOFF_HOTPLUG ,/* CPU is going on/offline */ +RQ_ONOFF_TOPOLOGY ,/* sched domain topology update */ +}; +struct sched_class {#ifdef CONFIG_UCLAMP_TASK
@@ -2201,8 +2206,8 @@ struct sched_class {const struct cpumask *newmask, u32 flags); -void (*rq_online)(struct rq *rq); -void (*rq_offline)(struct rq *rq); +void (*rq_online)(struct rq *rq,enum rq_onoff_reason reason); +void (*rq_offline)(struct rq *rq,enum rq_onoff_reason reason);struct rq *(*find_lock_rq)(struct task_struct *p,struct rq *rq);#endif
@@ -2726,8 +2731,8 @@ static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2) raw_spin_rq_unlock(rq1); } -extern void set_rq_online (struct rq *rq); -extern void set_rq_offline (struct rq *rq); +extern void set_rq_online (struct rq *rq,enum rq_onoff_reason reason); +extern void set_rq_offline (struct rq *rq,enum rq_onoff_reason reason);extern bool sched_smp_initialized;#else /* CONFIG_SMP */
kernel/sched/topology.c +2 -2
@@ -493,7 +493,7 @@ void rq_attach_root(struct rq *rq, struct root_domain *rd) old_rd = rq->rd;if (cpumask_test_cpu (rq->cpu, old_rd->online)) -set_rq_offline (rq); +set_rq_offline (rq,RQ_ONOFF_TOPOLOGY );cpumask_clear_cpu (rq->cpu, old_rd->span);
@@ -511,7 +511,7 @@ void rq_attach_root(struct rq *rq, struct root_domain *rd)cpumask_set_cpu (rq->cpu, rd->span);if (cpumask_test_cpu (rq->cpu, cpu_active_mask)) -set_rq_online (rq); +set_rq_online (rq,RQ_ONOFF_TOPOLOGY );raw_spin_rq_unlock_irqrestore (rq, flags);
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 10/31] sched: Add @reason to sched_class->rq_{on|off}line()
Quoted 3 lines · Tejun Heo
->rq_{on|off}line are called either during CPU hotplug or cpuset partition updates. Let's add an argument to distinguish the two cases. The argument will be used by a new
sched_classto track CPU hotplug events.
Again, utter lack of why.
Tejun Heo
maintainerRe: [PATCH 10/31] sched: Add @reason to sched_class->rq_{on|off}line()
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Tejun Heo
->rq_{on|off}line are called either during CPU hotplug or cpuset partition updates. Let's add an argument to distinguish the two cases. The argument will be used by a new
sched_classto track CPU hotplug events.Again, utter lack of why.
sched_ext wants to tell the BPF scheduler about CPU hotplugs in a way that's synchronized with rq state changes, so it needs to distinguish the two cases. Will update the description.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 11/31 sched: Add @reason to sched_move_task()
In reply to Tejun Heosched_move_task() can be called for both cgroup and autogroup moves. Add a parameter to distinguish the two cases. This will be used by a new sched_class to track cgroup migrations.
--- kernel/sched/autogroup.c | 4 ++-- kernel/sched/core.c | 4 ++-- kernel/sched/sched.h | 7 ++++++- 3 files changed, 10 insertions(+), 5 deletions(-)
kernel/sched/autogroup.c +2 -2
@@ -151,7 +151,7 @@ void sched_autogroup_exit_task(struct task_struct *p)* see this thread after that: we can no longer use signal->autogroup. * See the PF_EXITING check in task_wants_autogroup(). */ -sched_move_task (p); +sched_move_task (p,SCHED_MOVE_TASK_AUTOGROUP ); } static void
@@ -183,7 +183,7 @@ autogroup_move_group(struct task_struct *p, struct autogroup *ag)* sched_autogroup_exit_task(). */ for_each_thread (p, t) -sched_move_task (t); +sched_move_task (t,SCHED_MOVE_TASK_AUTOGROUP );unlock_task_sighand (p, &flags);autogroup_kref_put (prev);
kernel/sched/core.c +2 -2
@@ -10210,7 +10210,7 @@ static void sched_change_group(struct task_struct *tsk)* now. This function just updates tsk->se.cfs_rq and tsk->se.parent to reflect * its new group. */ -void sched_move_task (struct task_struct *tsk) +void sched_move_task (struct task_struct *tsk,enum sched_move_task_reason reason) {int queued, running, queue_flags =DEQUEUE_SAVE |DEQUEUE_MOVE |DEQUEUE_NOCLOCK ;
@@ -10321,7 +10321,7 @@ static void cpu_cgroup_attach(struct cgroup_taskset *tset)struct cgroup_subsys_state *css;cgroup_taskset_for_each (task, css, tset) -sched_move_task (task); +sched_move_task (task,SCHED_MOVE_TASK_CGROUP ); }#ifdef CONFIG_UCLAMP_TASK_GROUP
kernel/sched/sched.h +6 -1
@@ -506,7 +506,12 @@ extern void sched_online_group(struct task_group *tg,extern void sched_destroy_group (struct task_group *tg);extern void sched_release_group (struct task_group *tg); -extern void sched_move_task (struct task_struct *tsk); +enum sched_move_task_reason { +SCHED_MOVE_TASK_CGROUP , +SCHED_MOVE_TASK_AUTOGROUP , +}; +extern void sched_move_task (struct task_struct *tsk, +enum sched_move_task_reason reason);#ifdef CONFIG_FAIR_GROUP_SCHED extern int sched_group_set_shares (struct task_group *tg,unsigned long shares);
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 11/31] sched: Add @reason to sched_move_task()
Quoted 3 lines · Tejun Heo
sched_move_task()can be called for both cgroup and autogroup moves. Add a parameter to distinguish the two cases. This will be used by a newsched_classto track cgroup migrations.
This all seems pointless, you can trivially distinguish a cgroup/autogroup task_group if you so want (again for unspecified raisins).
Tejun Heo
maintainerRe: [PATCH 11/31] sched: Add @reason to sched_move_task()
Quoted 8 lines · Peter Zijlstra
Quoted 3 lines · Tejun Heo
sched_move_task()can be called for both cgroup and autogroup moves. Add a parameter to distinguish the two cases. This will be used by a newsched_classto track cgroup migrations.This all seems pointless, you can trivially distinguish a cgroup/autogroup
task_groupif you so want (again for unspecified raisins).
Lemme add better explanations on the patches. This one, sched_ext just wants to tell cgroup moves from autogroup ones to decide whether to invoke the BPF scheduler's cgroup migration callback. But, yeah, you're right. It should be able to tell that by looking at the task_group itself. Will try that.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 12/31 sched: Add normal_policy()
In reply to Tejun HeoAdd normal_policy() which wraps testing for %SCHED_NORMAL. Makes no behavior change. Will be used by a new sched_class to expand what's considered normal policy.
--- kernel/sched/fair.c | 2 +- kernel/sched/sched.h | 8 +++++++- 2 files changed, 8 insertions(+), 2 deletions(-)
kernel/sched/fair.c +1 -1
@@ -7441,7 +7441,7 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_* Batch and idle tasks do not preempt non-idle tasks (their preemption * is driven by the tick): */ -if (unlikely (p->policy !=SCHED_NORMAL ) || !sched_feat (WAKEUP_PREEMPTION )) +if (unlikely (!normal_policy (p->policy)) || !sched_feat (WAKEUP_PREEMPTION ))return ;find_matching_se (&se, &pse);
kernel/sched/sched.h +7 -1
@@ -182,9 +182,15 @@ static inline int idle_policy(int policy) {return policy ==SCHED_IDLE ; } + +static inline int normal_policy (int policy) +{ +return policy ==SCHED_NORMAL ; +} +static inline int fair_policy (int policy) { -return policy ==SCHED_NORMAL || policy ==SCHED_BATCH ; +return normal_policy (policy) || policy ==SCHED_BATCH ; }static inline int rt_policy (int policy)
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 13/31 sched_ext: Add boilerplate for extensible scheduler class
In reply to Tejun HeoThis adds dummy implementations of sched_ext interfaces which interact with the scheduler core and hook them in the correct places. As they're all dummies, this doesn't cause any behavior changes. This is split out to help reviewing.
--- include/linux/sched/ext.h | 12 ++++++++++++ kernel/fork.c | 2 ++ kernel/sched/core.c | 35 +++++++++++++++++++++++++++-------- kernel/sched/ext.h | 34 ++++++++++++++++++++++++++++++++++ kernel/sched/idle.c | 2 ++ kernel/sched/sched.h | 2 ++ 6 files changed, 79 insertions(+), 8 deletions(-) create mode 100644 include/linux/sched/ext.h create mode 100644 kernel/sched/ext.h
include/linux/sched/ext.h new file +12 -0
@@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_SCHED_EXT_H +#define _LINUX_SCHED_EXT_H + +#ifdef CONFIG_SCHED_CLASS_EXT +#error "NOT IMPLEMENTED YET" +#else /* !CONFIG_SCHED_CLASS_EXT */ + +static inline void sched_ext_free (struct task_struct *p) {} + +#endif /* CONFIG_SCHED_CLASS_EXT */ +#endif /* _LINUX_SCHED_EXT_H */
kernel/fork.c +2 -0
@@ -23,6 +23,7 @@#include <linux/sched/task.h> #include <linux/sched/task_stack.h> #include <linux/sched/cputime.h> +#include <linux/sched/ext.h> #include <linux/seq_file.h> #include <linux/rtmutex.h> #include <linux/init.h>
@@ -833,6 +834,7 @@ void __put_task_struct(struct task_struct *tsk)WARN_ON (refcount_read (&tsk->usage));WARN_ON (tsk == current); +sched_ext_free (tsk);io_uring_free (tsk);cgroup_free (tsk);task_numa_free (tsk, true);
kernel/sched/core.c +27 -8
@@ -4554,6 +4554,8 @@ late_initcall(sched_core_sysctl_init);*/ int sched_fork (unsigned long clone_flags,struct task_struct *p) { +int ret; +__sched_fork (clone_flags, p);/* * We mark the process as NEW here. This guarantees that
@@ -4590,12 +4592,16 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p) p->sched_reset_on_fork =0 ; } -if (dl_prio (p->prio)) -return -EAGAIN ; -else if (rt_prio (p->prio)) +scx_pre_fork (p); + +if (dl_prio (p->prio)) { + ret = -EAGAIN ; + goto out_cancel; + }else if (rt_prio (p->prio)) { p->sched_class = &rt_sched_class; -else + }else { p->sched_class = &fair_sched_class; + }init_entity_runnable_average (&p->se);
@@ -4613,6 +4619,10 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)RB_CLEAR_NODE (&p->pushable_dl_tasks);#endif return 0 ; + +out_cancel: +scx_cancel_fork (p); +return ret; }int sched_cgroup_fork (struct task_struct *p,struct kernel_clone_args *kargs)
@@ -4643,16 +4653,18 @@ int sched_cgroup_fork(struct task_struct *p, struct kernel_clone_args *kargs) p->sched_class->task_fork (p);raw_spin_unlock_irqrestore (&p->pi_lock, flags); -return 0 ; +return scx_fork (p); }void sched_cancel_fork (struct task_struct *p) { +scx_cancel_fork (p); }void sched_post_fork (struct task_struct *p) {uclamp_post_fork (p); +scx_post_fork (p); }unsigned long to_ratio (u64 period,u64 runtime)
@@ -5800,10 +5812,13 @@ static void put_prev_task_balance(struct rq *rq, struct task_struct *prev,* We can terminate the balance pass as soon as we know there is * a runnable task of @class priority or higher. */ - for_class_range(class, prev->sched_class, &idle_sched_class) { + for_balance_class_range(class, prev->sched_class, &idle_sched_class) {if (class->balance (rq, prev, rf))break ; } +#else +/* SCX needs the balance call even in UP, call it explicitly */ +balance_scx_on_up (rq, prev, rf);#endif put_prev_task (rq, prev);
@@ -5818,6 +5833,9 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)const struct sched_class *class;struct task_struct *p; +if (scx_enabled ()) + goto restart; +/* * Optimization: we know that if all tasks are in the fair class we can * call that function directly, but only if the @prev task wasn't of a
@@ -5843,7 +5861,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) restart:put_prev_task_balance (rq, prev, rf); -for_each_class (class) { +for_each_active_class (class) { p = class->pick_next_task (rq);if (p)return p;
@@ -5876,7 +5894,7 @@ static inline struct task_struct *pick_task(struct rq *rq)const struct sched_class *class;struct task_struct *p; -for_each_class (class) { +for_each_active_class (class) { p = class->pick_task (rq);if (p)return p;
@@ -9810,6 +9828,7 @@ void __init sched_init(void)balance_push_set (smp_processor_id (), false);#endif init_sched_fair_class (); +init_sched_ext_class ();psi_init ();
kernel/sched/ext.h new file +34 -0
@@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifdef CONFIG_SCHED_CLASS_EXT +#error "NOT IMPLEMENTED YET" +#else /* CONFIG_SCHED_CLASS_EXT */ + +#define scx_enabled () false + +static inline void scx_pre_fork (struct task_struct *p) {} +static inline int scx_fork (struct task_struct *p) {return 0 ; } +static inline void scx_post_fork (struct task_struct *p) {} +static inline void scx_cancel_fork (struct task_struct *p) {} +static inline int balance_scx (struct rq *rq,struct task_struct *prev, +struct rq_flags *rf) {return 0 ; } +static inline void init_sched_ext_class (void ) {} + +#define for_each_active_class for_each_class +#define for_balance_class_range for_class_range + +#endif /* CONFIG_SCHED_CLASS_EXT */ + +#ifndef CONFIG_SMP +static inline void balance_scx_on_up (struct rq *rq,struct task_struct *prev, +struct rq_flags *rf) +{ +balance_scx (rq, prev, rf); +} +#endif + +#if defined(CONFIG_SCHED_CLASS_EXT ) && defined(CONFIG_SMP ) +#error "NOT IMPLEMENTED YET" +#else +static inline void scx_update_idle (struct rq *rq,bool idle) {} +#endif
kernel/sched/idle.c +2 -0
@@ -428,11 +428,13 @@ static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p, int flstatic void put_prev_task_idle (struct rq *rq,struct task_struct *prev) { +scx_update_idle (rq, false); }static void set_next_task_idle (struct rq *rq,struct task_struct *next,bool first) {update_idle_core (rq); +scx_update_idle (rq, true);schedstat_inc (rq->sched_goidle); }
kernel/sched/sched.h +2 -0
@@ -3252,4 +3252,6 @@ enum cpu_cftype_id {extern struct cftype cpu_cftypes[CPU_CFTYPE_CNT +1 ];#endif /* CONFIG_CGROUP_SCHED */ +#include "ext.h" +#endif /* _KERNEL_SCHED_SCHED_H */
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 14/31 sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoImplement a new scheduler class sched_ext (SCX), which allows scheduling policies to be implemented as BPF programs to achieve the following:
1. Ease of experimentation and exploration: Enabling rapid iteration of new scheduling policies.
2. Customization: Building application-specific schedulers which implement policies that are not applicable to general-purpose schedulers.
3. Rapid scheduler deployments: Non-disruptive swap outs of scheduling policies in production environments.
sched_ext leverages BPF’s struct_ops feature to define a structure which exports function callbacks and flags to BPF programs that wish to implement scheduling policies. The struct_ops structure exported by sched_ext is struct sched_ext_ops, and is conceptually similar to struct sched_class. The role of sched_ext is to map the complex sched_class callbacks to the more simple and ergonomic struct sched_ext_ops callbacks.
For more detailed discussion on the motivations and overview, please refer to the cover letter.
Later patches will also add several example schedulers and documentation.
This patch implements the minimum core framework to enable implementation of BPF schedulers. Subsequent patches will gradually add functionalities including safety guarantee mechanisms, nohz and cgroup support.
include/linux/sched/ext.h defines struct sched_ext_ops. With the comment on top, each operation should be self-explanatory. The followings are worth noting:
* Both "sched_ext" and its shorthand "scx" are used. If the identifier already has "sched" in it, "ext" is used; otherwise, "scx".
* In sched_ext_ops, only .name is mandatory. Every operation is optional and if omitted a simple but functional default behavior is provided.
* A new policy constant SCHED_EXT is added and a task can select sched_ext by invoking sched_setscheduler(2) with the new policy constant. However, if the BPF scheduler is not loaded, SCHED_EXT is the same as SCHED_NORMAL and the task is scheduled by CFS. When the BPF scheduler is loaded, all tasks which have the SCHED_EXT policy are switched to sched_ext.
* To bridge the workflow imbalance between the scheduler core and sched_ext_ops callbacks, sched_ext uses simple FIFOs called dispatch queues (dsq's). By default, there is one global dsq (SCX_DSQ_GLOBAL), and one local per-CPU dsq (SCX_DSQ_LOCAL). SCX_DSQ_GLOBAL is provided for convenience and need not be used by a scheduler that doesn't require it. SCX_DSQ_LOCAL is the per-CPU FIFO that sched_ext pulls from when putting the next task on the CPU. The BPF scheduler can manage an arbitrary number of dsq's using scx_bpf_create_dsq() and scx_bpf_destroy_dsq().
* sched_ext guarantees system integrity no matter what the BPF scheduler does. To enable this, each task's ownership is tracked through p->scx.ops_state and all tasks are put on scx_tasks list. The disable path can always recover and revert all tasks back to CFS. See p->scx.ops_state and scx_tasks.
* A task is not tied to its rq while enqueued. This decouples CPU selection from queueing and allows sharing a scheduling queue across an arbitrary subset of CPUs. This adds some complexities as a task may need to be bounced between rq's right before it starts executing. See dispatch_to_local_dsq() and move_task_to_local_dsq().
* One complication that arises from the above weak association between task and rq is that synchronizing with dequeue() gets complicated as dequeue() may happen anytime while the task is enqueued and the dispatch path might need to release the rq lock to transfer the task. Solving this requires a bit of complexity. See the logic around p->scx.sticky_cpu and p->scx.ops_qseq.
* Both enable and disable paths are a bit complicated. The enable path switches all tasks without blocking to avoid issues which can arise from partially switched states (e.g. the switching task itself being starved). The disable path can't trust the BPF scheduler at all, so it also has to guarantee forward progress without blocking. See scx_ops_enable() and scx_ops_disable_workfn().
* When sched_ext is disabled, static_branches are used to shut down the entry points from hot paths.
--- include/asm-generic/vmlinux.lds.h | 1 + include/linux/sched.h | 5 + include/linux/sched/ext.h | 386 +++- include/uapi/linux/sched.h | 1 + init/init_task.c | 10 + kernel/Kconfig.preempt | 4 +- kernel/bpf/bpf_struct_ops_types.h | 4 + kernel/sched/build_policy.c | 4 + kernel/sched/core.c | 65 +- kernel/sched/debug.c | 6 + kernel/sched/ext.c | 2780 +++++++++++++++++++++++++++++ kernel/sched/ext.h | 109 +- kernel/sched/sched.h | 19 + 13 files changed, 3388 insertions(+), 6 deletions(-) create mode 100644 kernel/sched/ext.c
include/asm-generic/vmlinux.lds.h +1 -0
@@ -131,6 +131,7 @@ *(__dl_sched_class) \ *(__rt_sched_class) \ *(__fair_sched_class) \ + *(__ext_sched_class) \ *(__idle_sched_class ) \ __sched_class_lowest = .;
include/linux/sched.h +5 -0
@@ -70,6 +70,8 @@ struct signal_struct;struct task_delay_info ;struct task_group ; +#include <linux/sched/ext.h> +/* * Task state bitmask. NOTE! These bits are also * encoded in fs/proc/array.c: get_task_state().
@@ -788,6 +790,9 @@ struct task_struct {struct sched_entity se;struct sched_rt_entity rt;struct sched_dl_entity dl; +#ifdef CONFIG_SCHED_CLASS_EXT +struct sched_ext_entity scx; +#endif const struct sched_class *sched_class;#ifdef CONFIG_SCHED_CORE
include/linux/sched/ext.h +385 -1
394 lines not on this page · raw message
include/uapi/linux/sched.h +1 -0
@@ -118,6 +118,7 @@ struct clone_args {/* SCHED_ISO: reserved but not implemented yet */ #define SCHED_IDLE 5#define SCHED_DEADLINE 6 +#define SCHED_EXT 7/* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */ #define SCHED_RESET_ON_FORK 0x40000000
init/init_task.c +10 -0
@@ -6,6 +6,7 @@#include <linux/sched/sysctl.h> #include <linux/sched/rt.h> #include <linux/sched/task.h> +#include <linux/sched/ext.h> #include <linux/init.h> #include <linux/fs.h> #include <linux/mm.h>
@@ -101,6 +102,15 @@ struct task_struct init_task#endif #ifdef CONFIG_CGROUP_SCHED .sched_task_group = &root_task_group, +#endif +#ifdef CONFIG_SCHED_CLASS_EXT + .scx = { + .dsq_node = LIST_HEAD_INIT(init_task.scx.dsq_node), + .sticky_cpu = -1, + .holding_cpu = -1, + .ops_state = ATOMIC_INIT(0), + .slice = SCX_SLICE_DFL, + },#endif .ptraced = LIST_HEAD_INIT(init_task.ptraced), .ptrace_entry = LIST_HEAD_INIT(init_task.ptrace_entry),
kernel/Kconfig.preempt +3 -1
@@ -133,4 +133,6 @@ config SCHED_CORE which is the likely usage by Linux distributions, there should be no measurable impact on performance. - +config SCHED_CLASS_EXT + bool "Extensible Scheduling Class" + depends on BPF_SYSCALL && BPF_JIT
kernel/bpf/bpf_struct_ops_types.h +4 -0
@@ -9,4 +9,8 @@ BPF_STRUCT_OPS_TYPE(bpf_dummy_ops)#include <net/tcp.h> BPF_STRUCT_OPS_TYPE(tcp_congestion_ops)#endif +#ifdef CONFIG_SCHED_CLASS_EXT +#include <linux/sched/ext.h> +BPF_STRUCT_OPS_TYPE(sched_ext_ops) +#endif #endif
kernel/sched/build_policy.c +4 -0
@@ -28,6 +28,7 @@#include <linux/suspend.h> #include <linux/tsacct_kern.h> #include <linux/vtime.h> +#include <linux/percpu-rwsem.h> #include <uapi/linux/sched/types.h>
@@ -52,3 +53,6 @@#include "cputime.c" #include "deadline.c" +#ifdef CONFIG_SCHED_CLASS_EXT +# include "ext.c" +#endif
kernel/sched/core.c +63 -2
104 lines not on this page · raw message
kernel/sched/debug.c +6 -0
@@ -338,6 +338,9 @@ static __init int sched_init_debug(void)debugfs_create_file ("debug" ,0444 , debugfs_sched,NULL , &sched_debug_fops); +#ifdef CONFIG_SCHED_CLASS_EXT +debugfs_create_file ("ext" ,0444 , debugfs_sched,NULL , &sched_ext_fops); +#endif return 0 ; }late_initcall (sched_init_debug);
@@ -1047,6 +1050,9 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,P (dl.runtime);P (dl.deadline); } +#ifdef CONFIG_SCHED_CLASS_EXT +__PS ("ext.enabled" , p->sched_class == &ext_sched_class); +#endif #undef PN_SCHEDSTAT#undef P_SCHEDSTAT
kernel/sched/ext.c new file +2780 -0
2,403 lines not on this page · raw message
kernel/sched/ext.h +107 -2
109 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.38.1
Part of the diff is not shown here. View the raw message.
Re: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
hi -
On 11/30/22 03:22, Tejun Heo wrote:
[...]
Quoted 43 lines
kernel/sched/ext.c new file +43
-0+static bool consume_dispatch_q (struct rq *rq,struct rq_flags *rf, +struct scx_dispatch_q *dsq) +{ +struct scx_rq *scx_rq = &rq->scx; +struct task_struct *p; +struct rq *task_rq; +bool moved = false; +retry: +if (list_empty (&dsq->fifo)) +return false; + +raw_spin_lock (&dsq->lock); +list_for_each_entry (p, &dsq->fifo, scx.dsq_node) { + task_rq =task_rq (p); +if (rq == task_rq) + goto this_rq; +if (likely (rq->online) && !is_migration_disabled (p) && +cpumask_test_cpu (cpu_of (rq), p->cpus_ptr)) + goto remote_rq; + } +raw_spin_unlock (&dsq->lock); +return false; + +this_rq: +/* @dsq is locked and @p is on this rq */ +WARN_ON_ONCE (p->scx.holding_cpu >=0 ); +list_move_tail (&p->scx.dsq_node, &scx_rq->local_dsq.fifo); + dsq->nr--; + scx_rq->local_dsq.nr++; + p->scx.dsq = &scx_rq->local_dsq; +raw_spin_unlock (&dsq->lock); +return true; + +remote_rq: +#ifdef CONFIG_SMP +/* +* @dsq is locked and @p is on a remote rq. @p is currently protected by +* @dsq->lock. We want to pull @p to @rq but may deadlock if we grab +* @task_rq while holding @dsq and @rq locks. As dequeue can't drop the +* rq lock or fail, do a little dancing from our side. See +* move_task_to_local_dsq(). +*/ +WARN_ON_ONCE (p->scx.holding_cpu >=0 );
kernel/sched/ext.c line 866
Quoted 10 lines
kernel/sched/ext.c new file +10
-0+list_del_init (&p->scx.dsq_node); + dsq->nr--; + p->scx.holding_cpu =raw_smp_processor_id (); +raw_spin_unlock (&dsq->lock); + +rq_unpin_lock (rq, rf); +double_lock_balance (rq, task_rq); +rq_repin_lock (rq, rf); + + moved =move_task_to_local_dsq (rq, p);
you might be able to avoid the double_lock_balance() by using move_queued_task(), which internally hands off the old rq lock and returns with the new rq lock.
the pattern for consume_dispatch_q() would be something like:
- kfunc from bpf, with this_rq lock held
- notice p isn't on this_rq, goto remote_rq:
- do sched_ext accounting, like the this_rq->dsq->nr--
- unlock this_rq
- p_rq = task_rq_lock(p)
- double_check p->rq didn't change to this_rq during that unlock
- new_rq = move_queued_task(p_rq, rf, p, new_cpu)
- do sched_ext accounting like new_rq->dsq->nr++
- unlock new_rq
- relock the original this_rq
- return to bpf
you still end up grabbing both locks, but just not at the same time.
plus, task_rq_lock() takes the guesswork out of whether you're getting p's rq lock or not. it looks like you're using the holding_cpu to handle the race where p moves cpus after you read task_rq(p) but before you lock that task_rq. maybe you can drop the whole concept of the holding_cpu?
thanks,
barret
Quoted 7 lines
kernel/sched/ext.c new file +7
-0+ +double_unlock_balance (rq, task_rq); +#endif /* CONFIG_SMP */ +if (likely (moved)) +return true; + goto retry; +}
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello,
Quoted 18 lines · Barret Rhoden
you might be able to avoid the
double_lock_balance()by usingmove_queued_task(), which internally hands off the old rq lock and returns with the new rq lock.the pattern for
consume_dispatch_q()would be something like:- kfunc from bpf, with
this_rqlock held
- notice p isn't onthis_rq, gotoremote_rq:
- dosched_extaccounting, like the this_rq->dsq->nr--
- unlockthis_rq
-p_rq=task_rq_lock(p)
-double_checkp->rqdidn't change tothis_rqduring that unlock
-new_rq=move_queued_task(p_rq, rf, p, new_cpu)
- dosched_extaccounting like new_rq->dsq->nr++
- unlocknew_rq
- relock the originalthis_rq
- return to bpf
Quoted 1 line
you still end up grabbing both locks, but just not at the same time.
Yeah, this probably would look better than the current double lock dancing, especially in the finish_dispatch() path.
Quoted 4 lines
plus,
task_rq_lock()takes the guesswork out of whether you're getting p's rq lock or not. it looks like you're using theholding_cputo handle the race where p moves cpus after you readtask_rq(p)but before you lock thattask_rq. maybe you can drop the whole concept of theholding_cpu?
->holding_cpu is there to basically detect intervening dequeues, so if we lock them out with TASK_ON_RQ_MIGRATING, we might be able to drop it. I need to look into it more tho. Things get pretty subtle around there, so I could easily be missing something. I'll try this and let you know how it goes.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello, Barret.
Quoted 10 lines · Tejun Heo
Quoted 1 line
you still end up grabbing both locks, but just not at the same time.
Yeah, this probably would look better than the current double lock dancing, especially in the
finish_dispatch()path.Quoted 4 lines
plus,
task_rq_lock()takes the guesswork out of whether you're getting p's rq lock or not. it looks like you're using theholding_cputo handle the race where p moves cpus after you readtask_rq(p)but before you lock thattask_rq. maybe you can drop the whole concept of theholding_cpu?
Quoted 4 lines
->holding_cpu is there to basically detect intervening dequeues, so if we lock them out with
TASK_ON_RQ_MIGRATING, we might be able to drop it. I need to look into it more tho. Things get pretty subtle around there, so I could easily be missing something. I'll try this and let you know how it goes.
I tried both and I'm pretty ambivalent. The problem is that the finish_dispatch() path can't use TASK_ON_RQ_MIGRATING the way the consume path does because the dispatch path isn't starting with the task locked. The only claim it has to the task is through p->scx.ops_state.
It can be argued that getting rid of double locking is still nice but given that holding_cpu is needed anyway and can play the same role, I'm not sure how attractive it is. I suppose we can go either way.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoQuoted 28 lines · Tejun Heo
include/linux/sched/ext.h +28
-0+/** +* dispatch - Dispatch tasks from the BPF scheduler into dsq's +* @cpu: CPU to dispatch tasks for +* @prev: previous task being switched out +* +* Called when a CPU can't find a task to execute after ops.consume(). +* The operation should dispatch one or more tasks from the BPF +* scheduler to the dsq's using scx_bpf_dispatch(). The maximum number +* of tasks which can be dispatched in a single call is specified by the +* @dispatch_max_batch field of this struct. +*/ +void (*dispatch)(s32 cpu,struct task_struct *prev); + +/** +* consume - Consume tasks from the dsq's to the local dsq for execution +* @cpu: CPU to consume tasks for +* +* Called when a CPU's local dsq is empty. The operation should transfer +* one or more tasks from the dsq's to the CPU's local dsq using +* scx_bpf_consume(). If this function fails to fill the local dsq, +* ops.dispatch() will be called. +* +* This operation is unnecessary if the BPF scheduler always dispatches +* either to one of the local dsq's or the global dsq. If implemented, +* this operation is also responsible for consuming the global_dsq. +*/ +void (*consume)(s32 cpu); +
include/linux/sched/ext.h line 208
Quoted 10 lines
include/linux/sched/ext.h +10
-0+/** +* consume_final - Final consume call before going idle +* @cpu: CPU to consume tasks for +* +* After ops.consume() and .dispatch(), @cpu still doesn't have a task +* to execute and is about to go idle. This operation can be used to +* implement more aggressive consumption strategies. Otherwise +* equivalent to ops.consume(). +*/ +void (*consume_final)(s32 cpu);
Doesn't really change the big picture but I ended up merging ops.consume[_final]() into ops.dispatch() which should make the dispatch path both simpler and more flexible.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoQuoted 7 lines
kernel/sched/ext.c new file +1
-0@@ -0,0 +1,2780 @@ +/* SPDX-License-Identifier: GPL-2.0 */
kernel/sched/ext.c line 11
Quoted 10 lines
kernel/sched/ext.c new file +10
-0+/* +* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. +* Copyright (c) 2022 Tejun Heo <[email protected]> +* Copyright (c) 2022 David Vernet <[email protected]> +*/ +#define SCX_OP_IDX (op) (offsetof(struct sched_ext_ops, op) / sizeof(void (*)(void))) + +enum scx_internal_consts { +SCX_NR_ONLINE_OPS =SCX_OP_IDX (init), +SCX_DSP_DFL_MAX_BATCH =32 ,
This definition of SCX_DSP_DFL_MAX_BATCH makes the dispatch queue have size
32. The example central policy thus aborts if more than 32 tasks are woken up at once.
julia
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello, Julia.
Quoted 13 lines · Julia Lawall
Quoted 13 lines
kernel/sched/ext.c new file +7
-0@@ -0,0 +1,2780 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* +* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. +* Copyright (c) 2022 Tejun Heo <[email protected]> +* Copyright (c) 2022 David Vernet <[email protected]> +*/ +#define SCX_OP_IDX (op) (offsetof(struct sched_ext_ops, op) / sizeof(void (*)(void)))
Quoted 8 lines
kernel/sched/ext.c line 11
Quoted 4 lines
kernel/sched/ext.c new file +4
-0+ +enum scx_internal_consts { +SCX_NR_ONLINE_OPS =SCX_OP_IDX (init), +SCX_DSP_DFL_MAX_BATCH =32 ,This definition of
SCX_DSP_DFL_MAX_BATCHmakes the dispatch queue have size
32. The example central policy thus aborts if more than 32 tasks are woken up at once.
Yeah, scx_exampl_central needs to either set ops.dispatch_max_batch higher according to number of CPUs or flush and exit the loop and retry when scx_bpf_dispatch_nr_slots() reaches zero. Will update.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Quoted 25 lines · Tejun Heo
Hello, Julia.
Quoted 13 lines · Julia Lawall
Quoted 13 lines
kernel/sched/ext.c new file +7
-0@@ -0,0 +1,2780 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* +* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. +* Copyright (c) 2022 Tejun Heo <[email protected]> +* Copyright (c) 2022 David Vernet <[email protected]> +*/ +#define SCX_OP_IDX (op) (offsetof(struct sched_ext_ops, op) / sizeof(void (*)(void)))Quoted 8 lines
kernel/sched/ext.c line 11
Quoted 4 lines
kernel/sched/ext.c new file +4
-0+ +enum scx_internal_consts { +SCX_NR_ONLINE_OPS =SCX_OP_IDX (init), +SCX_DSP_DFL_MAX_BATCH =32 ,This definition of
SCX_DSP_DFL_MAX_BATCHmakes the dispatch queue have size
32. The example central policy thus aborts if more than 32 tasks are woken up at once.
Quoted 3 lines
Yeah,
scx_exampl_centralneeds to either set ops.dispatch_max_batch higher according to number of CPUs or flush and exit the loop and retry whenscx_bpf_dispatch_nr_slots()reaches zero. Will update.
Since there could be any number of waking threads, maybe some kind of flush and retry solution would be better?
julia
Quoted 6 lines
Thanks.
--
tejun
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Quoted 6 lines · Julia Lawall
Quoted 3 lines
Yeah,
scx_exampl_centralneeds to either set ops.dispatch_max_batch higher according to number of CPUs or flush and exit the loop and retry whenscx_bpf_dispatch_nr_slots()reaches zero. Will update.Since there could be any number of waking threads, maybe some kind of flush and retry solution would be better?
Yeah, cental is a bit unusual because it's scheudling for other CPUs too. In most cases, this doesn't matter that much because whether to retry or not can be determined by the kernel core code. There are a couple ways to go about it. When slots run out, it can explicitly queue another scheduling event on self, or use scx_bpf_consume() to flush the pending tasks. Either should work but neither is particularly pretty. I'm trying to see whether I can remove the static dispatch buffers altogether.
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoQuoted 29 lines · Tejun Heo
kernel/sched/core.c +25
-0@@ -11242,3 +11268,38 @@ void call_trace_sched_update_nr_running(struct rq *rq, int count) {trace_sched_update_nr_running_tp (rq, count); } + +#ifdef CONFIG_SCHED_CLASS_EXT +void sched_deq_and_put_task (struct task_struct *p,int queue_flags, +struct sched_enq_and_set_ctx *ctx) +{ +struct rq *rq =task_rq (p); + +lockdep_assert_rq_held (rq); + + *ctx = (struct sched_enq_and_set_ctx ){ + .p = p, + .queue_flags = queue_flags |DEQUEUE_NOCLOCK , + .queued =task_on_rq_queued (p), + .running =task_current (rq, p), + }; + +update_rq_clock (rq); +if (ctx->queued) +dequeue_task (rq, p, queue_flags); +if (ctx->running) +put_prev_task (rq, p); +} + +void sched_enq_and_set_task (struct sched_enq_and_set_ctx *ctx) +{
kernel/sched/core.c void call_trace_sched_update_nr_running(struct rq *rq, int count) · line 11305
Quoted 10 lines
kernel/sched/core.c +10
-0+struct rq *rq =task_rq (ctx->p); + +lockdep_assert_rq_held (rq); + +if (ctx->queued) +enqueue_task (rq, ctx->p, ctx->queue_flags); +if (ctx->running) + set_next_task(rq, ctx->p); +} +#endif /* CONFIG_SCHED_CLASS_EXT */
So no. Like the whole __setscheduler_prio() thing, this doesn't make sense outside of the core code, policy/class code should never need to do this.
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello,
Quoted 36 lines · Peter Zijlstra
Quoted 35 lines · Tejun Heo
kernel/sched/core.c +31
-0@@ -11242,3 +11268,38 @@ void call_trace_sched_update_nr_running(struct rq *rq, int count) {trace_sched_update_nr_running_tp (rq, count); } + +#ifdef CONFIG_SCHED_CLASS_EXT +void sched_deq_and_put_task (struct task_struct *p,int queue_flags, +struct sched_enq_and_set_ctx *ctx) +{ +struct rq *rq =task_rq (p); + +lockdep_assert_rq_held (rq); + + *ctx = (struct sched_enq_and_set_ctx ){ + .p = p, + .queue_flags = queue_flags |DEQUEUE_NOCLOCK , + .queued =task_on_rq_queued (p), + .running =task_current (rq, p), + }; + +update_rq_clock (rq); +if (ctx->queued) +dequeue_task (rq, p, queue_flags); +if (ctx->running) +put_prev_task (rq, p); +} + +void sched_enq_and_set_task (struct sched_enq_and_set_ctx *ctx) +{ +struct rq *rq =task_rq (ctx->p); + +lockdep_assert_rq_held (rq); + +if (ctx->queued) +enqueue_task (rq, ctx->p, ctx->queue_flags);
Quoted 8 lines
kernel/sched/core.c void call_trace_sched_update_nr_running(struct rq *rq, int count) · line 11305
Quoted 4 lines
kernel/sched/core.c +4
-0+if (ctx->running) + set_next_task(rq, ctx->p); +} +#endif /* CONFIG_SCHED_CLASS_EXT */ So no. Like the whole
__setscheduler_prio()thing, this doesn't make sense outside of the core code, policy/class code should never need to do this.
Continuing from the __setscheduler_prio() discussion, the need arises from the fact that whether a task is on SCX or CFS changes depending on whether the BPF scheduler is loaded or not - e.g. when the BPF scheduler gets disabled, all tasks that were on it need to be moved back into CFS. There are different ways to implement this but it needs to be solved somehow.
Quoted 1 line
Yeah, it'd be nice to encapsulate this sequence. The FOR_CHANGE_GUARD naming throws me off a bit tho as it's not really a loop. Wouldn't it be better to call it CHANGE_GUARD_BLOCK or sth?
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoQuoted 19 lines · Tejun Heo
include/asm-generic/vmlinux.lds.h +1
-2@@ -131,6 +131,7 @@ *(__dl_sched_class) \ *(__rt_sched_class) \ *(__fair_sched_class) \ + *(__ext_sched_class) \ *(__idle_sched_class ) \ __sched_class_lowest = .;@@ -9654,8 +9675,13 @@ void __init sched_init(void)int i;/* Make sure the linker didn't screw up */ - BUG_ON(&idle_sched_class != &fair_sched_class + 1 || - &fair_sched_class != &rt_sched_class + 1 ||
include/asm-generic/vmlinux.lds.h void __init sched_init(void) · line 9687
Quoted 10 lines
include/asm-generic/vmlinux.lds.h +7
-0+#ifdef CONFIG_SCHED_CLASS_EXT +BUG_ON (&idle_sched_class != &ext_sched_class +1 || + &ext_sched_class != &fair_sched_class +1 ); +#else +BUG_ON (&idle_sched_class != &fair_sched_class +1 ); +#endif +BUG_ON (&fair_sched_class != &rt_sched_class +1 || &rt_sched_class != &dl_sched_class +1 );#ifdef CONFIG_SMP BUG_ON (&dl_sched_class != &stop_sched_class +1 );
Perhaps the saner way to write this is:
#ifdef CONFIG_SMP BUG_ON(!sched_class_above(&stop_sched_class, &dl_sched_class)); #endif BUG_ON(!sched_class_above(&dl_sched_class, &rt_sched_class)); BUG_ON(!sched_class_above(&rt_sched_class, &fair_sched_class)); BUG_ON(!sched_class_above(&fair_sched_class, &idle_sched_class)); #ifdef CONFIG_... BUG_ON(!sched_class_above(&fair_sched_class, &ext_sched_class)); BUG_ON(!sched_class_above(&ext_sched_class, &idle_sched_class));
#endif
Quoted 12 lines
include/asm-generic/vmlinux.lds.h +12
-0+static inline const struct sched_class *next_active_class (const struct sched_class *class) +{ + class++; +if (!scx_enabled () && class == &ext_sched_class) + class++; +return class; +} + +#define for_active_class_range (class, _from, _to) \ + for (class = (_from); class != (_to); class = next_active_class(class)) + +#define for_each_active_class (class) \
include/asm-generic/vmlinux.lds.h
Quoted 10 lines
include/asm-generic/vmlinux.lds.h +10
-0+for_active_class_range (class, __sched_class_highest, __sched_class_lowest) + +/* +* SCX requires a balance() call before every pick_next_task() call including +* when waking up from idle. + */ +#define for_balance_class_range (class, prev_class, end_class) \ + for_active_class_range(class, (prev_class) > &ext_sched_class ? \ + &ext_sched_class : (prev_class), (end_class)) +
This seems quite insane; why not simply make the ext methods effective no-ops? Both balance and pick explicitly support that already, no?
include/asm-generic/vmlinux.lds.h static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, · line 5820
Quoted 11 lines
include/asm-generic/vmlinux.lds.h +3
-1@@ -5800,10 +5812,13 @@ static void put_prev_task_balance(struct rq *rq, struct task_struct *prev,* We can terminate the balance pass as soon as we know there is * a runnable task of @class priority or higher. */ - for_class_range(class, prev->sched_class, &idle_sched_class) { + for_balance_class_range(class, prev->sched_class, &idle_sched_class) {if (class->balance (rq, prev, rf))break ; } +#else +/* SCX needs the balance call even in UP, call it explicitly */
This, *WHY* !?!
Quoted 24 lines
include/asm-generic/vmlinux.lds.h +5
-1+balance_scx_on_up (rq, prev, rf);#endif put_prev_task (rq, prev);@@ -5818,6 +5833,9 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)const struct sched_class *class;struct task_struct *p; +if (scx_enabled ()) + goto restart; +/* * Optimization: we know that if all tasks are in the fair class we can * call that function directly, but only if the @prev task wasn't of a @@ -5843,7 +5861,7 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) restart:put_prev_task_balance (rq, prev, rf); -for_each_class (class) { +for_each_active_class (class) { p = class->pick_next_task (rq);if (p)return p;
include/asm-generic/vmlinux.lds.h static inline struct task_struct *pick_task(struct rq *rq) · line 5900
Quoted 8 lines
include/asm-generic/vmlinux.lds.h +1
-1@@ -5876,7 +5894,7 @@ static inline struct task_struct *pick_task(struct rq *rq)const struct sched_class *class;struct task_struct *p; -for_each_class (class) { +for_each_active_class (class) { p = class->pick_task (rq);if (p)return p;
But this.. afaict that means that:
- the whole EXT thing is incompatible with SCHED_CORE
- the whole EXT thing can be trivially starved by the presence of a single CFS/BATCH/IDLE task.
Both seems like deal breakers.
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello,
Quoted 11 lines · Peter Zijlstra
Perhaps the saner way to write this is:
#ifdef CONFIG_SMP BUG_ON(!sched_class_above(&stop_sched_class, &dl_sched_class)); #endif BUG_ON(!sched_class_above(&dl_sched_class, &rt_sched_class)); BUG_ON(!sched_class_above(&rt_sched_class, &fair_sched_class)); BUG_ON(!sched_class_above(&fair_sched_class, &idle_sched_class)); #ifdef CONFIG_... BUG_ON(!sched_class_above(&fair_sched_class, &ext_sched_class)); BUG_ON(!sched_class_above(&ext_sched_class, &idle_sched_class));
Quoted 1 line
#endif
Yeah, this looks way better. Will update.
Quoted 17 lines
Quoted 17 lines
kernel/sched/ext.h +17
-0+static inline const struct sched_class *next_active_class (const struct sched_class *class) +{ + class++; +if (!scx_enabled () && class == &ext_sched_class) + class++; +return class; +} + +#define for_active_class_range (class, _from, _to) \ + for (class = (_from); class != (_to); class = next_active_class(class)) + +#define for_each_active_class (class) \ + for_active_class_range(class, __sched_class_highest, __sched_class_lowest) + +/* +* SCX requires a balance() call before every pick_next_task() call including +* when waking up from idle.
Quoted 8 lines
kernel/sched/ext.h line 103
Quoted 5 lines
+ */
kernel/sched/ext.h +4
-0+#define for_balance_class_range (class, prev_class, end_class) \ + for_active_class_range(class, (prev_class) > &ext_sched_class ? \ + &ext_sched_class : (prev_class), (end_class)) +This seems quite insane; why not simply make the ext methods effective no-ops? Both balance and pick explicitly support that already, no?
Yeah, we can definitely do that. It's just nice to guarantee from the core code that we aren't calling into a sched class which isn't enabled at the moment. If you take a look at "[PATCH 20/31] sched_ext: Allow BPF schedulers to switch all eligible tasks into sched_ext", it's used the other way around too to elide calling into CFS when it knows that there are no tasks there. If the core code doesn't elide the calls, we might need some gating in CFS too.
Quoted 5 lines
Quoted 5 lines
(quoted diff) +0
-1@@ -5800,10 +5812,13 @@ static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, * We can terminate the balance pass as soon as we know there is * a runnable task of @class priority or higher. */ - for_class_range(class, prev->sched_class, &idle_sched_class) {
Quoted 8 lines
Review static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, · line 5820
Quoted 6 lines
(quoted diff) +3
-0+ for_balance_class_range(class, prev->sched_class, &idle_sched_class) { if (class->balance(rq, prev, rf)) break; } +#else + /* SCX needs the balance call even in UP, call it explicitly */This, *WHY* !?!
This comes from the fact that there are no strict rq boundaries and the BPF scheduler can share scheduling queues across any subset of CPUs however they see fit. So, task <-> rq association is flexible until the very last moment the task gets picked for execution. For the dispatch path to support this, it needs to be able to migrate tasks across rq's which requires unlocking the current rq which can only be done in ->balance(). So, sched_ext uses ->balance() to run the dispatch path and thus needs it called even on UP.
Given that UP doesn't need to transfer tasks across, it might be possible to move the whole dispatch operation into ->pick_next_task() but the current state would be different, so it's more complicated and will likely be more brittle.
Quoted 13 lines
Review static inline struct task_struct *pick_task(struct rq *rq) · line 5900
Quoted 9 lines
(quoted diff) +1
-1@@ -5876,7 +5894,7 @@ static inline struct task_struct *pick_task(struct rq *rq) const struct sched_class *class; struct task_struct *p; - for_each_class(class) { + for_each_active_class(class) { p = class->pick_task(rq); if (p) return p;But this.. afaict that means that:
Quoted 1 line
- the whole EXT thing is incompatible with
SCHED_CORE
Can you expand on why this would be? I didn't test against SCHED_CORE, so am sure things might be broken but can't think of a reason why it'd be fundamentally incompatible.
Quoted 2 lines
- the whole EXT thing can be trivially starved by the presence of a single CFS/BATCH/IDLE task.
It's a simliar situation w/ RT vs. CFS, which is resolved via RT having starvation avoidance. Here, the way it's handled is a bit different, SCX has a watchdog mechanism implemented in "[PATCH 18/31] sched_ext: Implement runnable task stall watchdog", so if SCX tasks hang for whatever reason including being starved by CFS, it will get aborted and all tasks will be handed back to CFS. IOW, it's treated like any other BPF scheduler errors that can lead to stalls and recovered the same way.
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Quoted 7 lines · Tejun Heo
Quoted 3 lines
But this.. afaict that means that:
- the whole EXT thing is incompatible with
SCHED_CORECan you expand on why this would be? I didn't test against
SCHED_CORE, so am sure things might be broken but can't think of a reason why it'd be fundamentally incompatible.
For starters, SCHED_CORE doesn't use __pick_next_task() (much). But I think you're going to have more trouble with prio_less() (which is the 3rd implementation of the scheduling function :/)
Quoted 5 lines
Quoted 2 lines
- the whole EXT thing can be trivially starved by the presence of a single CFS/BATCH/IDLE task.
It's a simliar situation w/ RT vs. CFS, which is resolved via RT having starvation avoidance.
That is a horrible situation as is, FIFO/RR are very crap scheduling policies for a number of reasons but we're stuck with them due to history and POSIX :-(, that is not something you should justify anything with.
In fact, it should be an example of what to avoid.
Specifically, FIFO/RR fail at the fundamentals of OS abstractions -- they provide neither resource distribution nor isolation.
Quoted 6 lines
Here, the way it's handled is a bit different, SCX has
a watchdog mechanism implemented in "[PATCH 18/31]sched_ext: Implement runnable task stall watchdog", so if SCX tasks hang for whatever reason including being starved by CFS, it will get aborted and all tasks will be handed back to CFS. IOW, it's treated like any other BPF scheduler errors that can lead to stalls and recovered the same way.
That all sounds quite terrible.. :/
When the scheduler isn't available it should be an error to switch a task to the policy, when there are tasks in the policy, it must not go away.
The policy itself should never cause policy changes.
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello,
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Tejun Heo
Quoted 3 lines
But this.. afaict that means that:
- the whole EXT thing is incompatible with
SCHED_CORECan you expand on why this would be? I didn't test against
SCHED_CORE, so am sure things might be broken but can't think of a reason why it'd be fundamentally incompatible.For starters,
SCHED_COREdoesn't use__pick_next_task()(much). But I
SCX implements ->pick_task() and the CORE selection path calls ->balance() and then ->pick_task(). That should work, right? Will test later.
Quoted 2 lines
think you're going to have more trouble with
prio_less()(which is the 3rd implementation of the scheduling function :/)
Can't it take the same approach as CFS? The BPF scheduler is gonna be the one defining the relative priorities among SCX tasks, so that's where the decision belongs.
Quoted 17 lines
Quoted 5 lines
Quoted 2 lines
- the whole EXT thing can be trivially starved by the presence of a single CFS/BATCH/IDLE task.
It's a simliar situation w/ RT vs. CFS, which is resolved via RT having starvation avoidance.
That is a horrible situation as is, FIFO/RR are very crap scheduling policies for a number of reasons but we're stuck with them due to history and POSIX :-(, that is not something you should justify anything with.
In fact, it should be an example of what to avoid.
Specifically, FIFO/RR fail at the fundamentals of OS abstractions -- they provide neither resource distribution nor isolation.
Quoted 8 lines
Quoted 6 lines
Here, the way it's handled is a bit different, SCX has
a watchdog mechanism implemented in "[PATCH 18/31]sched_ext: Implement runnable task stall watchdog", so if SCX tasks hang for whatever reason including being starved by CFS, it will get aborted and all tasks will be handed back to CFS. IOW, it's treated like any other BPF scheduler errors that can lead to stalls and recovered the same way.That all sounds quite terrible.. :/
The main source of difference is that we can't implicitly trust the BPF scheduler and if it malfunctions or on user request, the system should always be recoverable, so there are some extra things which are inherently necessary to support that.
Quoted 3 lines
When the scheduler isn't available it should be an error to switch a task to the policy, when there are tasks in the policy, it must not go away.
Yeah, this part is an interface design choice. Currently, when the BPF scheduler fails or is not present for any reason, SCX falls back to CFS because that seemed like the least invasive way to go about it, but it's trivial to just let SCX do dumb FIFO scheduling with the global DSQ instead, which in fact is already used during transition to guarantee forward progress.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Quoted 18 lines · Tejun Heo
Hello,
Quoted 13 lines · Peter Zijlstra
Quoted 10 lines · Tejun Heo
Here, the way it's handled is a bit different, SCX has a watchdog mechanism implemented in "[PATCH 18/31]
sched_ext:
Implement
runnable task stall watchdog", so if SCX tasks hang for whatever reason
including being starved by CFS, it will get aborted and all tasks will be
handed back to CFS. IOW, it's treated like any other BPF scheduler errors
that can lead to stalls and recovered the same way.Quoted 1 line
That all sounds quite terrible.. :/
Quoted 8 lines
The main source of difference is that we can't implicitly trust the BPF
scheduler and if it malfunctions or on user request, the system should
always be recoverable, so there are some extra things which are inherently
necessary to support that.
That makes me wonder whether loading an SCX policy should just have that policy take over all of the SCHED_OTHER tasks by default, and have a failure of the policy just return those tasks to CFS?
Having the two be operative at the same time seems to be a cause of hard to resolve issues, while simply running all non-RT tasks under the loadable policy could simplify both internal kernel interfaces, as well as externally visible effects?
Signature · 1 line
All Rights Reversed.
Re: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Quoted 33 lines · Rik van Riel
Quoted 18 lines · Tejun Heo
Hello,
Quoted 13 lines · Peter Zijlstra
Quoted 10 lines · Tejun Heo
Here, the way it's handled is a bit different, SCX has a watchdog mechanism implemented in "[PATCH 18/31]
sched_ext:
Implement
runnable task stall watchdog", so if SCX tasks hang for whatever reason
including being starved by CFS, it will get aborted and all tasks will be
handed back to CFS. IOW, it's treated like any other BPF scheduler errors
that can lead to stalls and recovered the same way.Quoted 1 line
That all sounds quite terrible.. :/
Quoted 8 lines
The main source of difference is that we can't implicitly trust the BPF
scheduler and if it malfunctions or on user request, the system should
always be recoverable, so there are some extra things which are inherently
necessary to support that.That makes me wonder whether loading an SCX policy should just have that policy take over all of the
SCHED_OTHERtasks by default, and have a failure of the policy just return those tasks to CFS?
Quoted 5 lines
Having the two be operative at the same time seems to be a cause of hard to resolve issues, while simply running all non-RT tasks under the loadable policy could simplify both internal kernel interfaces, as well as externally visible effects?
There are reasons to want to still have CFS available even when SCX is loaded. For example, on a partitioned shared tenant machine, moving one application to an SCX policy without needing to move everyone. Or, wanting to avoid scheduling things like kthreads under an SCX policy, since for example that makes an SCX policy writer need not only consider the needs of application threads, but also those of kernel threads.
Peter Zijlstra
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
In reply to Tejun HeoQuoted 14 lines · Tejun Heo
Quoted 5 lines
Quoted 5 lines
(quoted diff) +0
-1@@ -5800,10 +5812,13 @@ static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, * We can terminate the balance pass as soon as we know there is * a runnable task of @class priority or higher. */ - for_class_range(class, prev->sched_class, &idle_sched_class) {Quoted 8 lines
Review static void put_prev_task_balance(struct rq *rq, struct task_struct *prev, · line 5820
Quoted 6 lines
(quoted diff) +3
-0+ for_balance_class_range(class, prev->sched_class, &idle_sched_class) { if (class->balance(rq, prev, rf)) break; } +#else + /* SCX needs the balance call even in UP, call it explicitly */This, *WHY* !?!
Quoted 7 lines
This comes from the fact that there are no strict rq boundaries and the BPF scheduler can share scheduling queues across any subset of CPUs however they see fit. So, task <-> rq association is flexible until the very last moment the task gets picked for execution. For the dispatch path to support this, it needs to be able to migrate tasks across rq's which requires unlocking the current rq which can only be done in ->balance(). So,
sched_extuses ->balance() to run the dispatch path and thus needs it called even on UP.
Fundamentally none of that makes sense, on UP there is no placement, there is only the one CPU, very little choice to be had.
Quoted 4 lines
Given that UP doesn't need to transfer tasks across, it might be possible to move the whole dispatch operation into ->pick_next_task() but the current state would be different, so it's more complicated and will likely be more brittle.
That sounds like something is amiss, you fundamentally hold all the right locks, there is only one.
Tejun Heo
maintainerRe: [PATCH 14/31] sched_ext: Implement BPF extensible scheduler class
Hello,
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines
Given that UP doesn't need to transfer tasks across, it might be possible to move the whole dispatch operation into ->pick_next_task() but the current state would be different, so it's more complicated and will likely be more brittle.
That sounds like something is amiss, you fundamentally hold all the right locks, there is only one.
Yeah, locking is not the problem on UP. It's more that balance() is before put_prev_task() and pick_next_task() after, so the %current task state is different between the two points. I'll see if I can sqaure that from SCX side. I don't see a reason why it wouldn't be possible but it's likely more complicated than adding a call in the same spot for UP.
Thanks.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 15/31 sched_ext: [TEMPORARY] Add temporary workaround kfunc helpers
In reply to Tejun HeoTHIS IS A TEMPORARY WORKAROUND. WILL BE DROPPED.
These exist to work around till we have proper generic BPF helpers.
NOT_FOR_UPSTREAM
Cc: Alexei Starovoitov <[email protected]>
Cc: Dave Marchevsky <[email protected]>
--- kernel/sched/ext.c | 84 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 83 insertions(+), 1 deletion(-)
kernel/sched/ext.c +83 -1
@@ -2745,6 +2745,86 @@ static const struct btf_kfunc_id_set scx_kfunc_set_any = { .set = &scx_kfunc_ids_any, }; +/******************************************************************************** +* Temporary BPF helpers to be replaced by generic non-scx-specific BPF helpers +*/ + +struct cgroup *scx_bpf_task_cgroup (const struct task_struct *p) +{ +struct task_group *tg = p->sched_task_group; + +if (tg && tg->css.cgroup) +return tg->css.cgroup; +else +return &cgrp_dfl_root.cgrp; +} + +struct task_struct *scx_bpf_find_task_by_pid (s32 pid) +{ +return find_task_by_pid_ns (pid, &init_pid_ns); +} + +s32 scx_bpf_pick_idle_cpu_untyped (unsigned long cpus_allowed) +{ +return scx_bpf_pick_idle_cpu ((const struct cpumask *)cpus_allowed); +} + +bool scx_bpf_has_idle_cpus_among (const struct cpumask *cpus_allowed) +{ +if (!static_branch_likely (&scx_builtin_idle_enabled)) { +scx_ops_error ("built-in idle tracking is disabled" ); +return false; + } +#ifdef CONFIG_SMP +return cpumask_any_and (idle_masks.cpu, cpus_allowed) < nr_cpu_ids; +#else +return false; +#endif +} + +s32 scx_bpf_has_idle_cpus_among_untyped (unsigned long cpus_allowed) +{ +return scx_bpf_has_idle_cpus_among ((const struct cpumask *)cpus_allowed); +} + +s32 scx_bpf_cpumask_test_cpu (s32 cpu,const struct cpumask *cpumask) +{ +return cpumask_test_cpu (cpu, cpumask); +} + +s32 scx_bpf_cpumask_first (const struct cpumask *cpus_allowed) +{ +return cpumask_first (cpus_allowed); +} + +s32 scx_bpf_cpumask_first_untyped (unsigned long cpus_allowed) +{ +return cpumask_first ((const struct cpumask *)cpus_allowed); +} + +bool scx_bpf_cpumask_intersects (const struct cpumask *src1p, +const struct cpumask *src2p) +{ +return cpumask_intersects (src1p, src2p); +} + +BTF_SET8_START (scx_kfunc_ids_xxx) +BTF_ID_FLAGS (func ,scx_bpf_task_cgroup ) +BTF_ID_FLAGS (func, scx_bpf_find_task_by_pid,KF_RET_NULL ) +BTF_ID_FLAGS (func, scx_bpf_pick_idle_cpu_untyped) +BTF_ID_FLAGS (func, scx_bpf_has_idle_cpus_among) +BTF_ID_FLAGS (func, scx_bpf_has_idle_cpus_among_untyped) +BTF_ID_FLAGS (func, scx_bpf_cpumask_test_cpu) +BTF_ID_FLAGS (func, scx_bpf_cpumask_first) +BTF_ID_FLAGS (func, scx_bpf_cpumask_first_untyped) +BTF_ID_FLAGS (func, scx_bpf_cpumask_intersects) +BTF_SET8_END (scx_kfunc_ids_xxx) + +static const struct btf_kfunc_id_set scx_kfunc_set_xxx = { + .owner =THIS_MODULE , + .set = &scx_kfunc_ids_xxx, +}; +__diag_pop ();/*
@@ -2770,7 +2850,9 @@ static int __init register_ext_kfuncs(void) (ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_online)) || (ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, - &scx_kfunc_set_any))) { + &scx_kfunc_set_any)) || + (ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, + &scx_kfunc_set_xxx))) {pr_err ("sched_ext: failed to register kfunc sets (%d)\n" , ret);return ret; }
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 16/31 sched_ext: Add scx_example_dummy and scx_example_qmap example schedulers
In reply to Tejun HeoAdd two simple example BPF schedulers - dummy and qmap.
* dummy: In terms of scheduling, it behaves identical to not having any operation implemented at all. The two operations it implements are only to improve visibility and exit handling. On certain homogeneous configurations, this actually can perform pretty well.
* qmap: A fixed five level priority scheduler to demonstrate queueing PIDs on BPF maps for scheduling. While not very practical, this is useful as a simple example and will be used to demonstrate different features.
--- tools/sched_ext/.gitignore | 5 + tools/sched_ext/Makefile | 187 +++++++++++++++++++ tools/sched_ext/gnu/stubs.h | 1 + tools/sched_ext/scx_common.bpf.h | 117 ++++++++++++ tools/sched_ext/scx_example_dummy.bpf.c | 56 ++++++ tools/sched_ext/scx_example_dummy.c | 93 ++++++++++ tools/sched_ext/scx_example_qmap.bpf.c | 228 ++++++++++++++++++++++++ tools/sched_ext/scx_example_qmap.c | 84 +++++++++ tools/sched_ext/user_exit_info.h | 50 ++++++ 9 files changed, 821 insertions(+) create mode 100644 tools/sched_ext/.gitignore create mode 100644 tools/sched_ext/Makefile create mode 100644 tools/sched_ext/gnu/stubs.h create mode 100644 tools/sched_ext/scx_common.bpf.h create mode 100644 tools/sched_ext/scx_example_dummy.bpf.c create mode 100644 tools/sched_ext/scx_example_dummy.c create mode 100644 tools/sched_ext/scx_example_qmap.bpf.c create mode 100644 tools/sched_ext/scx_example_qmap.c create mode 100644 tools/sched_ext/user_exit_info.h
tools/sched_ext/.gitignore new file +5 -0
@@ -0,0 +1,5 @@ +scx_example_dummy +scx_example_qmap +*.skel.h +*.subskel.h +/tools/
tools/sched_ext/Makefile new file +187 -0
187 lines not on this page · raw message
tools/sched_ext/gnu/stubs.h new file +1 -0
@@ -0,0 +1 @@ +/* dummy .h to trick /usr/include/features.h to work with 'clang -target bpf' */
tools/sched_ext/scx_common.bpf.h new file +117 -0
117 lines not on this page · raw message
tools/sched_ext/scx_example_dummy.bpf.c new file +56 -0
56 lines not on this page · raw message
tools/sched_ext/scx_example_dummy.c new file +93 -0
93 lines not on this page · raw message
tools/sched_ext/scx_example_qmap.bpf.c new file +228 -0
228 lines not on this page · raw message
tools/sched_ext/scx_example_qmap.c new file +84 -0
84 lines not on this page · raw message
tools/sched_ext/user_exit_info.h new file +50 -0
50 lines not on this page · raw message
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 17/31 sched_ext: Add sysrq-S which disables the BPF scheduler
In reply to Tejun HeoThis enables the admin to abort the BPF scheduler and revert to CFS anytime.
--- drivers/tty/sysrq.c | 1 + include/linux/sched/ext.h | 1 + kernel/sched/build_policy.c | 1 + kernel/sched/ext.c | 20 ++++++++++++++++++++ 4 files changed, 23 insertions(+)
drivers/tty/sysrq.c +1 -0
@@ -520,6 +520,7 @@ static const struct sysrq_key_op *sysrq_key_table[62] = {NULL ,/* P */ NULL ,/* Q */ NULL ,/* R */ +/* S: May be registered by sched_ext for resetting */ NULL ,/* S */ NULL ,/* T */ NULL, /* U */
include/linux/sched/ext.h +1 -0
@@ -55,6 +55,7 @@ enum scx_exit_type {SCX_EXIT_DONE ,SCX_EXIT_UNREG =64 ,/* BPF unregistration */ +SCX_EXIT_SYSRQ ,/* requested by 'S' sysrq */ SCX_EXIT_ERROR =1024 ,/* runtime error, error msg contains details */ SCX_EXIT_ERROR_BPF, /* ERROR but triggered through scx_bpf_error() */
kernel/sched/build_policy.c +1 -0
@@ -28,6 +28,7 @@#include <linux/suspend.h> #include <linux/tsacct_kern.h> #include <linux/vtime.h> +#include <linux/sysrq.h> #include <linux/percpu-rwsem.h> #include <uapi/linux/sched/types.h>
kernel/sched/ext.c +20 -0
@@ -1771,6 +1771,9 @@ static void scx_ops_disable_workfn(struct kthread_work *work)case SCX_EXIT_UNREG : reason ="BPF scheduler unregistered" ;break ; +case SCX_EXIT_SYSRQ : + reason ="disabled by sysrq-S" ; +break ;case SCX_EXIT_ERROR : reason ="runtime error" ;break ;
@@ -2377,6 +2380,21 @@ struct bpf_struct_ops bpf_sched_ext_ops = { .name = "sched_ext_ops", }; +static void sysrq_handle_sched_ext_reset (int key) +{ +if (scx_ops_helper) +scx_ops_disable (SCX_EXIT_SYSRQ ); +else +pr_info ("sched_ext: BPF scheduler not yet used\n" ); +} + +static const struct sysrq_key_op sysrq_sched_ext_reset_op = { + .handler = sysrq_handle_sched_ext_reset, + .help_msg ="reset-sched-ext(S)" , + .action_msg ="Disable sched_ext and revert all tasks to CFS" , + .enable_mask =SYSRQ_ENABLE_RTNICE , +}; +void __init init_sched_ext_class (void ) {int cpu;
@@ -2400,6 +2418,8 @@ void __init init_sched_ext_class(void)init_dsq (&rq->scx.local_dsq,SCX_DSQ_LOCAL ); rq->scx.nr_running =0 ; } + +register_sysrq_key ('S' , &sysrq_sched_ext_reset_op); }
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 18/31 sched_ext: Implement runnable task stall watchdog
In reply to Tejun HeoFrom: David Vernet <[email protected]>
The most common and critical way that a BPF scheduler can misbehave is by failing to run runnable tasks for too long. This patch implements a watchdog.
* All tasks record when they become runnable.
* A watchdog work periodically scans all runnable tasks. If any task has stayed runnable for too long, the BPF scheduler is aborted.
* scheduler_tick() monitors whether the watchdog itself is stuck. If so, the BPF scheduler is aborted.
Because the watchdog only scans the tasks which are currently runnable and usually very infrequently, the overhead should be negligible. scx_example_qmap is updated so that it can be told to stall user and/or kernel tasks.
A detected task stall looks like the following:
sched_ext: BPF scheduler "qmap" errored, disabling
sched_ext: runnable task stall (dbus-daemon[953] failed to run for 6.478s)
scx_check_timeout_workfn+0x10e/0x1b0
process_one_work+0x287/0x560
worker_thread+0x234/0x420
kthread+0xe9/0x100
ret_from_fork+0x1f/0x30A detected watchdog stall:
sched_ext: BPF scheduler "qmap" errored, disabling
sched_ext: runnable task stall (watchdog failed to check in for 5.001s)
scheduler_tick+0x2eb/0x340
update_process_times+0x7a/0x90
tick_sched_timer+0xd8/0x130
__hrtimer_run_queues+0x178/0x3b0
hrtimer_interrupt+0xfc/0x390
__sysvec_apic_timer_interrupt+0xb7/0x2b0
sysvec_apic_timer_interrupt+0x90/0xb0
asm_sysvec_apic_timer_interrupt+0x1b/0x20
default_idle+0x14/0x20
arch_cpu_idle+0xf/0x20
default_idle_call+0x50/0x90
do_idle+0xe8/0x240
cpu_startup_entry+0x1d/0x20
kernel_init+0x0/0x190
start_kernel+0x0/0x392
start_kernel+0x324/0x392
x86_64_start_reservations+0x2a/0x2c
x86_64_start_kernel+0x104/0x109
secondary_startup_64_no_verify+0xce/0xdbNote that this patch exposes scx_ops_error[_type]() in kernel/sched/ext.h to inline scx_notify_sched_tick().
--- include/linux/sched/ext.h | 14 +++ init/init_task.c | 2 + kernel/sched/core.c | 3 + kernel/sched/ext.c | 133 +++++++++++++++++++++++-- kernel/sched/ext.h | 26 +++++ kernel/sched/sched.h | 1 + tools/sched_ext/scx_example_qmap.bpf.c | 12 +++ tools/sched_ext/scx_example_qmap.c | 14 ++- 8 files changed, 193 insertions(+), 12 deletions(-)
include/linux/sched/ext.h +14 -0
@@ -59,6 +59,7 @@ enum scx_exit_type {SCX_EXIT_ERROR =1024 ,/* runtime error, error msg contains details */ SCX_EXIT_ERROR_BPF ,/* ERROR but triggered through scx_bpf_error() */ + SCX_EXIT_ERROR_STALL, /* watchdog detected stalled runnable tasks */ };/*
@@ -323,6 +324,15 @@ struct sched_ext_ops {*/ u64 flags; +/** +* timeout_ms - The maximum amount of time, in milliseconds, that a +* runnable task should be able to wait before being scheduled. The +* maximum timeout may not exceed the default timeout of 30 seconds. +* +* Defaults to the maximum allowed timeout value of 30 seconds. +*/ +u32 timeout_ms; +/** * name - BPF scheduler's name *
@@ -357,6 +367,8 @@ enum scx_ent_flags {SCX_TASK_OPS_PREPPED =1 <<3 ,/* prepared for BPF scheduler enable */ SCX_TASK_OPS_ENABLED =1 <<4 ,/* task has BPF scheduler enabled */ +SCX_TASK_WATCHDOG_RESET =1 <<5 ,/* task watchdog counter should be reset */ + SCX_TASK_CURSOR = 1 << 6, /* iteration cursor, not a task */ };
@@ -367,11 +379,13 @@ enum scx_ent_flags {struct sched_ext_entity {struct scx_dispatch_q *dsq;struct list_head dsq_node; +struct list_head watchdog_node;u32 flags;/* protected by rq lock */ u32 weight;s32 sticky_cpu;s32 holding_cpu;atomic64_t ops_state; +unsigned long runnable_at;/* BPF scheduler modifiable fields */
init/init_task.c +2 -0
@@ -106,9 +106,11 @@ struct task_struct init_task#ifdef CONFIG_SCHED_CLASS_EXT .scx = { .dsq_node = LIST_HEAD_INIT(init_task.scx.dsq_node), + .watchdog_node = LIST_HEAD_INIT(init_task.scx.watchdog_node), .sticky_cpu = -1, .holding_cpu = -1, .ops_state = ATOMIC_INIT(0), + .runnable_at = INITIAL_JIFFIES, .slice = SCX_SLICE_DFL, },#endif
kernel/sched/core.c +3 -0
@@ -4366,11 +4366,13 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)#ifdef CONFIG_SCHED_CLASS_EXT p->scx.dsq =NULL ;INIT_LIST_HEAD (&p->scx.dsq_node); +INIT_LIST_HEAD (&p->scx.watchdog_node); p->scx.flags =0 ; p->scx.weight =0 ; p->scx.sticky_cpu =-1 ; p->scx.holding_cpu =-1 ;atomic64_set (&p->scx.ops_state,0 ); + p->scx.runnable_at =INITIAL_JIFFIES ; p->scx.slice =SCX_SLICE_DFL ;#endif
@@ -5514,6 +5516,7 @@ void scheduler_tick(void)if (sched_feat (LATENCY_WARN ) && resched_latency)resched_latency_warn (cpu, resched_latency); +scx_notify_sched_tick ();perf_event_task_tick ();#ifdef CONFIG_SMP
kernel/sched/ext.c +124 -9
241 lines not on this page · raw message
kernel/sched/ext.h +26 -0
@@ -67,6 +67,8 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx);extern const struct sched_class ext_sched_class;extern const struct bpf_verifier_ops bpf_sched_ext_verifier_ops;extern const struct file_operations sched_ext_fops; +extern unsigned long task_runnable_timeout_ms; +extern unsigned long last_timeout_check;DECLARE_STATIC_KEY_FALSE (__scx_ops_enabled);#define scx_enabled () static_branch_unlikely(&__scx_ops_enabled)
@@ -79,6 +81,29 @@ void scx_cancel_fork(struct task_struct *p);int balance_scx (struct rq *rq,struct task_struct *prev,struct rq_flags *rf);void init_sched_ext_class (void ); +__printf(2, 3) void scx_ops_error_type(enum scx_exit_type type, +const char *fmt, ...); +#define scx_ops_error(fmt, args...) \ + scx_ops_error_type(SCX_EXIT_ERROR, fmt, ##args) + +static inline void scx_notify_sched_tick (void ) +{ +unsigned long last_check, timeout; + +if (!scx_enabled ()) +return ; + + last_check = last_timeout_check; + timeout =msecs_to_jiffies (task_runnable_timeout_ms); +if (unlikely (time_after (jiffies, last_check + timeout))) { +u32 dur_ms =jiffies_to_msecs (jiffies - last_check); + +scx_ops_error_type (SCX_EXIT_ERROR_STALL , +"watchdog failed to check in for %u.%03us" , + dur_ms /1000 , dur_ms %1000 ); + } +} +static inline const struct sched_class *next_active_class (const struct sched_class *class) { class++;
@@ -112,6 +137,7 @@ static inline void scx_cancel_fork(struct task_struct *p) {}static inline int balance_scx (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) {return 0 ; }static inline void init_sched_ext_class (void ) {} +static inline void scx_notify_sched_tick (void ) {}#define for_each_active_class for_each_class#define for_balance_class_range for_class_range
kernel/sched/sched.h +1 -0
@@ -692,6 +692,7 @@ struct cfs_rq { #ifdef CONFIG_SCHED_CLASS_EXT struct scx_rq { struct scx_dispatch_q local_dsq; + struct list_head watchdog_list; u64 ops_qseq; u32 nr_running; #ifdef CONFIG_SMP
tools/sched_ext/scx_example_qmap.bpf.c +12 -0
@@ -22,6 +22,8 @@ char _license[] SEC("license") = "GPL";const volatile u64 slice_ns =SCX_SLICE_DFL ; +const volatile u32 stall_user_nth; +const volatile u32 stall_kernel_nth;u32 test_error_cnt;
@@ -106,6 +108,15 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)u32 pid = p->pid;int idx;void *ring; +static u32 user_cnt, kernel_cnt; + +if (p->flags &PF_KTHREAD ) { +if (stall_kernel_nth && !(++kernel_cnt % stall_kernel_nth)) +return ; + }else { +if (stall_user_nth && !(++user_cnt % stall_user_nth)) +return ; + }if (test_error_cnt && !--test_error_cnt)scx_bpf_error ("test triggering error" );
@@ -224,5 +235,6 @@ struct sched_ext_ops qmap_ops = { .dispatch = (void *)qmap_dispatch, .prep_enable = (void *)qmap_prep_enable, .exit = (void *)qmap_exit, + .timeout_ms = 5000U, .name = "qmap", };
tools/sched_ext/scx_example_qmap.c +11 -3
@@ -20,10 +20,12 @@ const char help_fmt[] ="\n" "See the top-level comment in .bpf.c for more details.\n" "\n" -"Usage: %s [-s SLICE_US] [-e COUNT]\n" +"Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT]\n" "\n" " -s SLICE_US Override slice duration\n" " -e COUNT Trigger scx_bpf_error() after COUNT enqueues\n" +" -t COUNT Stall every COUNT'th user thread\n" +" -T COUNT Stall every COUNT'th kernel thread\n" " -h Display this help and exit\n" ;static volatile int exit_req;
@@ -47,13 +49,19 @@ int main(int argc, char **argv) skel =scx_example_qmap__open ();assert (skel); -while ((opt =getopt (argc, argv,"hs:e:tTd:" )) !=-1 ) { +while ((opt =getopt (argc, argv,"hs:e:t:T:d:" )) !=-1 ) {switch (opt) {case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;break ;case 'e' : - skel->bss->test_error_cnt =strtoull (optarg,NULL ,0 ); + skel->bss->test_error_cnt =strtoul (optarg,NULL ,0 ); +break ; +case 't' : + skel->rodata->stall_user_nth =strtoul (optarg,NULL ,0 ); +break ; +case 'T' : + skel->rodata->stall_kernel_nth =strtoul (optarg,NULL ,0 );break ;default :fprintf (stderr, help_fmt,basename (argv[0 ]));
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 19/31 sched_ext: Allow BPF schedulers to disallow specific tasks from joining SCHED_EXT
In reply to Tejun HeoBPF schedulers might not want to schedule certain tasks - e.g. kernel threads. This patch adds p->scx.disallow which can be set by BPF schedulers in such cases. The field can be changed anytime and setting it in ops.prep_enable() guarantees that the task can never be scheduled by sched_ext.
scx_example_qmap is updated with the -d option to disallow a specific PID:
# echo $$ 1092 # egrep '(policy)|(ext\.enabled)' /proc/self/sched policy : 0 ext.enabled : 0 # ./set-scx 1092 # egrep '(policy)|(ext\.enabled)' /proc/self/sched policy : 7 ext.enabled : 0
Run "scx_example_qmap -d 1092" in another terminal.
# grep rejected /sys/kernel/debug/sched/ext nr_rejected : 1 # egrep '(policy)|(ext\.enabled)' /proc/self/sched policy : 0 ext.enabled : 0 # ./set-scx 1092 setparam failed for 1092 (Permission denied)
--- include/linux/sched/ext.h | 12 ++++++++ kernel/sched/core.c | 4 +++ kernel/sched/ext.c | 38 ++++++++++++++++++++++++++ kernel/sched/ext.h | 3 ++ tools/sched_ext/scx_example_qmap.bpf.c | 4 +++ tools/sched_ext/scx_example_qmap.c | 8 +++++- 6 files changed, 68 insertions(+), 1 deletion(-)
include/linux/sched/ext.h +12 -0
@@ -397,6 +397,18 @@ struct sched_ext_entity {*/ u64 slice; +/* +* If set, reject future sched_setscheduler(2) calls updating the policy +* to %SCHED_EXT with -%EACCES. +* +* If set from ops.prep_enable() and the task's policy is already +* %SCHED_EXT, which can happen while the BPF scheduler is being loaded +* or by inhering the parent's policy during fork, the task's policy is +* rejected and forcefully reverted to %SCHED_NORMAL. The number of such +* events are reported through /sys/kernel/debug/sched_ext::nr_rejected. +*/ +bool disallow;/* reject switching into SCX */ +/* cold fields */ struct list_head tasks_node; };
kernel/sched/core.c +4 -0
@@ -7552,6 +7552,10 @@ static int __sched_setscheduler(struct task_struct *p, goto unlock; } + retval =scx_check_setscheduler (p, policy); +if (retval) + goto unlock; +/* * If not changing anything there's no need to proceed further, * but store a possible modification of reset_on_fork.
kernel/sched/ext.c +38 -0
@@ -1509,6 +1509,8 @@ static int scx_ops_prepare_task(struct task_struct *p, struct task_group *tg)WARN_ON_ONCE (p->scx.flags &SCX_TASK_OPS_PREPPED ); + p->scx.disallow = false; +if (SCX_HAS_OP (prep_enable)) {struct scx_enable_args args = { };
@@ -1519,6 +1521,27 @@ static int scx_ops_prepare_task(struct task_struct *p, struct task_group *tg) } } +if (p->scx.disallow) { +struct rq *rq; +struct rq_flags rf; + + rq =task_rq_lock (p, &rf); + +/* +* We're either in fork or load path and @p->policy will be +* applied right after. Reverting @p->policy here and rejecting +* %SCHED_EXT transitions from scx_check_setscheduler() +* guarantees that if ops.prep_enable() sets @p->disallow, @p +* can never be in SCX. +*/ +if (p->policy ==SCHED_EXT ) { + p->policy =SCHED_NORMAL ; +atomic64_inc (&scx_nr_rejected); + } + +task_rq_unlock (rq, p, &rf); + } + p->scx.flags |= (SCX_TASK_OPS_PREPPED |SCX_TASK_WATCHDOG_RESET );return 0 ; }
@@ -1664,6 +1687,18 @@ static void switching_to_scx(struct rq *rq, struct task_struct *p)static void check_preempt_curr_scx (struct rq *rq,struct task_struct *p,int wake_flags) {}static void switched_to_scx (struct rq *rq,struct task_struct *p) {} +int scx_check_setscheduler (struct task_struct *p,int policy) +{ +lockdep_assert_rq_held (task_rq (p)); + +/* if disallow, reject transitioning into SCX */ +if (scx_enabled () &&READ_ONCE (p->scx.disallow) && + p->policy != policy && policy ==SCHED_EXT ) +return -EACCES ; + +return 0 ; +} +/* * Omitted operations: *
@@ -2367,6 +2402,9 @@ static int bpf_scx_btf_struct_access(struct bpf_verifier_log *log, if (off >= offsetof(struct task_struct, scx.slice) && off + size <= offsetofend(struct task_struct, scx.slice))return SCALAR_VALUE ; + if (off >= offsetof(struct task_struct, scx.disallow) && + off + size <= offsetofend(struct task_struct, scx.disallow)) +return SCALAR_VALUE ; }if (atype ==BPF_READ )
kernel/sched/ext.h +3 -0
@@ -79,6 +79,7 @@ int scx_fork(struct task_struct *p);void scx_post_fork (struct task_struct *p);void scx_cancel_fork (struct task_struct *p);int balance_scx (struct rq *rq,struct task_struct *prev,struct rq_flags *rf); +int scx_check_setscheduler (struct task_struct *p,int policy);void init_sched_ext_class (void ); __printf(2, 3) void scx_ops_error_type(enum scx_exit_type type,
@@ -136,6 +137,8 @@ static inline void scx_post_fork(struct task_struct *p) {}static inline void scx_cancel_fork (struct task_struct *p) {}static inline int balance_scx (struct rq *rq,struct task_struct *prev,struct rq_flags *rf) {return 0 ; } +static inline int scx_check_setscheduler (struct task_struct *p, +int policy) {return 0 ; }static inline void init_sched_ext_class (void ) {}static inline void scx_notify_sched_tick (void ) {}
tools/sched_ext/scx_example_qmap.bpf.c +4 -0
@@ -24,6 +24,7 @@ char _license[] SEC("license") = "GPL";const volatile u64 slice_ns =SCX_SLICE_DFL ;const volatile u32 stall_user_nth;const volatile u32 stall_kernel_nth; +const volatile s32 disallow_tgid;u32 test_error_cnt;
@@ -208,6 +209,9 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cpu, struct task_struct *prev)s32 BPF_STRUCT_OPS (qmap_prep_enable ,struct task_struct *p,struct scx_enable_args *args) { +if (p->tgid == disallow_tgid) + p->scx.disallow = true; +/* * @p is new. Let's ensure that its task_ctx is available. We can sleep * in this function and the following will automatically use GFP_KERNEL.
tools/sched_ext/scx_example_qmap.c +7 -1
@@ -20,12 +20,13 @@ const char help_fmt[] ="\n" "See the top-level comment in .bpf.c for more details.\n" "\n" -"Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT]\n" +"Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-d PID]\n" "\n" " -s SLICE_US Override slice duration\n" " -e COUNT Trigger scx_bpf_error() after COUNT enqueues\n" " -t COUNT Stall every COUNT'th user thread\n" " -T COUNT Stall every COUNT'th kernel thread\n" +" -d PID Disallow a process from switching into SCHED_EXT (-1 for self)\n" " -h Display this help and exit\n" ;static volatile int exit_req;
@@ -63,6 +64,11 @@ int main(int argc, char **argv)case 'T' : skel->rodata->stall_kernel_nth =strtoul (optarg,NULL ,0 );break ; +case 'd' : + skel->rodata->disallow_tgid =strtol (optarg,NULL ,0 ); +if (skel->rodata->disallow_tgid <0 ) + skel->rodata->disallow_tgid =getpid (); +break ;default :fprintf (stderr, help_fmt,basename (argv[0 ]));return opt !='h' ;
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 20/31 sched_ext: Allow BPF schedulers to switch all eligible tasks into sched_ext
In reply to Tejun HeoCurrently, to use sched_ext, each task has to be put into sched_ext using sched_setscheduler(2). However, some BPF schedulers and use cases might prefer to service all eligible tasks.
This patch adds a new kfunc helper, scx_bpf_switch_all(), that BPF schedulers can call from ops.init() to switch all SCHED_NORMAL, SCHED_BATCH and SCHED_IDLE tasks into sched_ext. This has the benefit that the scheduler swaps are transparent to the users and applications. As we know that CFS is not being used when scx_bpf_switch_all() is used, we can also disable hot path entry points with static_branches.
Both the dummy and qmap example schedulers are updated with the '-a' option which enables the switch_all behavior.
--- kernel/sched/core.c | 8 +++-- kernel/sched/ext.c | 42 +++++++++++++++++++++++++ kernel/sched/ext.h | 5 +++ tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_dummy.bpf.c | 11 +++++++ tools/sched_ext/scx_example_dummy.c | 8 +++-- tools/sched_ext/scx_example_qmap.bpf.c | 9 ++++++ tools/sched_ext/scx_example_qmap.c | 7 +++-- 8 files changed, 84 insertions(+), 7 deletions(-)
kernel/sched/core.c +5 -3
@@ -1204,7 +1204,7 @@ bool sched_can_stop_tick(struct rq *rq)* if there's more than one we need the tick for involuntary * preemption. */ -if (rq->nr_running >1 ) +if (!scx_switched_all () && rq->nr_running >1 )return false;return true;
@@ -5520,8 +5520,10 @@ void scheduler_tick(void)perf_event_task_tick ();#ifdef CONFIG_SMP - rq->idle_balance =idle_cpu (cpu); -trigger_load_balance (rq); +if (!scx_switched_all ()) { + rq->idle_balance =idle_cpu (cpu); +trigger_load_balance (rq); + }#endif }
kernel/sched/ext.c +42 -0
96 lines not on this page · raw message
kernel/sched/ext.h +5 -0
@@ -71,7 +71,9 @@ extern unsigned long task_runnable_timeout_ms;extern unsigned long last_timeout_check;DECLARE_STATIC_KEY_FALSE (__scx_ops_enabled); +DECLARE_STATIC_KEY_FALSE (__scx_switched_all);#define scx_enabled () static_branch_unlikely(&__scx_ops_enabled) +#define scx_switched_all () static_branch_unlikely(&__scx_switched_all)bool task_on_scx (struct task_struct *p);void scx_pre_fork (struct task_struct *p);
@@ -108,6 +110,8 @@ static inline void scx_notify_sched_tick(void)static inline const struct sched_class *next_active_class (const struct sched_class *class) { class++; +if (scx_switched_all () && class == &fair_sched_class) + class++;if (!scx_enabled () && class == &ext_sched_class) class++;return class;
@@ -130,6 +134,7 @@ static inline const struct sched_class *next_active_class(const struct sched_cla#else /* CONFIG_SCHED_CLASS_EXT */ #define scx_enabled () false +#define scx_switched_all () falsestatic inline void scx_pre_fork (struct task_struct *p) {}static inline int scx_fork (struct task_struct *p) {return 0 ; }
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -48,6 +48,7 @@ void ___scx_bpf_error_format_checker(const char *fmt, ...) {} ___scx_bpf_error_format_checker(fmt, ##args); \ }) +extern void scx_bpf_switch_all(void) __ksym; extern s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym; extern bool scx_bpf_consume(u64 dsq_id) __ksym; extern u32 scx_bpf_dispatch_nr_slots(void) __ksym;
tools/sched_ext/scx_example_dummy.bpf.c +11 -0
@@ -7,6 +7,7 @@* * - Statistics tracking how many are queued to local and global dsq's. * - Termination notification for userspace. +* - Support for switch_all. * * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]>
@@ -16,6 +17,8 @@ char _license[] SEC("license") = "GPL"; +const volatile bool switch_all; +struct user_exit_info uei;struct {
@@ -32,6 +35,13 @@ static void stat_inc(u32 idx) (*cnt_p)++; } +s32 BPF_STRUCT_OPS (dummy_init ) +{ +if (switch_all) +scx_bpf_switch_all (); +return 0 ; +} +void BPF_STRUCT_OPS (dummy_enqueue ,struct task_struct *p,u64 enq_flags) {if (enq_flags &SCX_ENQ_LOCAL ) {
@@ -51,6 +61,7 @@ void BPF_STRUCT_OPS(dummy_exit, struct scx_exit_info *ei) SEC(".struct_ops")struct sched_ext_ops dummy_ops = { .enqueue = (void *)dummy_enqueue, + .init = (void *)dummy_init, .exit = (void *)dummy_exit, .name ="dummy" , };
tools/sched_ext/scx_example_dummy.c +6 -2
@@ -19,8 +19,9 @@ const char help_fmt[] ="\n" "See the top-level comment in .bpf.c for more details.\n" "\n" -"Usage: %s\n" +"Usage: %s [-a]\n" "\n" +" -a Switch all tasks\n" " -h Display this help and exit\n" ;static volatile int exit_req;
@@ -64,8 +65,11 @@ int main(int argc, char **argv) skel =scx_example_dummy__open ();assert (skel); -while ((opt =getopt (argc, argv,"h" )) !=-1 ) { +while ((opt =getopt (argc, argv,"ah" )) !=-1 ) {switch (opt) { +case 'a' : + skel->rodata->switch_all = true; +break ;default :fprintf (stderr, help_fmt,basename (argv[0 ]));return opt !='h' ;
tools/sched_ext/scx_example_qmap.bpf.c +9 -0
@@ -22,6 +22,7 @@ char _license[] SEC("license") = "GPL";const volatile u64 slice_ns =SCX_SLICE_DFL ; +const volatile bool switch_all;const volatile u32 stall_user_nth;const volatile u32 stall_kernel_nth;const volatile s32 disallow_tgid;
@@ -223,6 +224,13 @@ s32 BPF_STRUCT_OPS(qmap_prep_enable, struct task_struct *p,return -ENOMEM ; } +s32 BPF_STRUCT_OPS (qmap_init ) +{ +if (switch_all) +scx_bpf_switch_all (); +return 0 ; +} +void BPF_STRUCT_OPS (qmap_exit ,struct scx_exit_info *ei) {uei_record (&uei, ei);
@@ -238,6 +246,7 @@ struct sched_ext_ops qmap_ops = {*/ .dispatch = (void *)qmap_dispatch, .prep_enable = (void *)qmap_prep_enable, + .init = (void *)qmap_init, .exit = (void *)qmap_exit, .timeout_ms = 5000U, .name = "qmap",
tools/sched_ext/scx_example_qmap.c +5 -2
@@ -20,7 +20,7 @@ const char help_fmt[] ="\n" "See the top-level comment in .bpf.c for more details.\n" "\n" -"Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-d PID]\n" +"Usage: %s [-a] [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-d PID]\n" "\n" " -s SLICE_US Override slice duration\n" " -e COUNT Trigger scx_bpf_error() after COUNT enqueues\n"
@@ -50,8 +50,11 @@ int main(int argc, char **argv) skel =scx_example_qmap__open ();assert (skel); -while ((opt =getopt (argc, argv,"hs:e:t:T:d:" )) !=-1 ) { +while ((opt =getopt (argc, argv,"ahs:e:t:T:d:" )) !=-1 ) {switch (opt) { +case 'a' : + skel->rodata->switch_all = true; +break ;case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;break ;
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 21/31 sched_ext: Implement scx_bpf_kick_cpu() and task preemption support
In reply to Tejun HeoIt's often useful to wake up and/or trigger reschedule on other CPUs. This patch adds scx_bpf_kick_cpu() kfunc helper that BPF scheduler can call to kick the target CPU into the scheduling path.
As a sched_ext task relinquishes its CPU only after its slice is depleted, this patch also adds SCX_KICK_PREEMPT and SCX_ENQ_PREEMPT which clears the slice of the target CPU's current task to guarantee that sched_ext's scheduling path runs on the CPU.
This patch also adds a new example scheduler, scx_example_central, which demonstrates central scheduling where one CPU is responsible for making all scheduling decisions in the system. The central CPU makes scheduling decisions for all CPUs in the system, queues tasks on the appropriate local dsq's and preempts the worker CPUs. The worker CPUs in turn preempt the central CPU when it needs tasks to run.
Currently, every CPU depends on its own tick to expire the current task. A follow-up patch implementing tickless support for sched_ext will allow the worker CPUs to go full tickless so that they can run completely undisturbed.
--- include/linux/sched/ext.h | 4 + kernel/sched/ext.c | 88 ++++++++- kernel/sched/ext.h | 12 ++ kernel/sched/sched.h | 1 + tools/sched_ext/.gitignore | 1 + tools/sched_ext/Makefile | 8 +- tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_central.bpf.c | 229 ++++++++++++++++++++++ tools/sched_ext/scx_example_central.c | 91 +++++++++ 9 files changed, 430 insertions(+), 5 deletions(-) create mode 100644 tools/sched_ext/scx_example_central.bpf.c create mode 100644 tools/sched_ext/scx_example_central.c
include/linux/sched/ext.h +4 -0
@@ -394,6 +394,10 @@ struct sched_ext_entity {* scx_bpf_dispatch() but can also be modified directly by the BPF * scheduler. Automatically decreased by SCX as the task executes. On * depletion, a scheduling event is triggered. +* +* This value is cleared to zero if the task is preempted by +* %SCX_KICK_PREEMPT and shouldn't be used to determine how long the +* task ran. Use p->se.sum_exec_runtime instead. */ u64 slice;
kernel/sched/ext.c +85 -3
131 lines not on this page · raw message
kernel/sched/ext.h +12 -0
@@ -19,6 +19,14 @@ enum scx_enq_flags {/* high 32bits are ext specific flags */ +/* +* Set the following to trigger preemption when calling +* scx_bpf_dispatch() with a local dsq as the target. The slice of the +* current task is cleared to zero and the CPU is kicked into the +* scheduling path. Implies %SCX_ENQ_HEAD. +*/ + SCX_ENQ_PREEMPT = 1LLU << 32, +/* * The task being enqueued is the only task available for the cpu. By * default, ext core keeps executing such tasks but when
@@ -51,6 +59,10 @@ enum scx_deq_flags { SCX_DEQ_SLEEP = DEQUEUE_SLEEP, }; +enum scx_kick_flags { +SCX_KICK_PREEMPT =1LLU <<0 ,/* force scheduling on the CPU */ +}; +#ifdef CONFIG_SCHED_CLASS_EXT struct sched_enq_and_set_ctx {
kernel/sched/sched.h +1 -0
@@ -698,6 +698,7 @@ struct scx_rq {#ifdef CONFIG_SMP cpumask_var_t cpus_to_kick;cpumask_var_t cpus_to_preempt; +struct irq_work kick_cpus_irq_work; #endif };#endif /* CONFIG_SCHED_CLASS_EXT */
tools/sched_ext/.gitignore +1 -0
@@ -1,5 +1,6 @@ scx_example_dummy scx_example_qmap +scx_example_central *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +6 -2
@@ -114,7 +114,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -Wno-compare-distinct-pointer-types \ -O2 -mcpu=v3 -all: scx_example_dummy scx_example_qmap +all: scx_example_dummy scx_example_qmap scx_example_central # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -173,10 +173,14 @@ scx_example_qmap: scx_example_qmap.c scx_example_qmap.skel.h user_exit_info.h $(CC) $(CFLAGS) -c $< -o [email protected] $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) +scx_example_central: scx_example_central.c scx_example_central.skel.h user_exit_info.h + $(CC) $(CFLAGS) -c $< -o [email protected] + $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) + clean: rm -rf $(SCRATCH_DIR) $(HOST_SCRATCH_DIR) rm -f *.o *.bpf.o *.skel.h *.subskel.h - rm -f scx_example_dummy scx_example_qmap + rm -f scx_example_dummy scx_example_qmap scx_example_central .PHONY: all clean
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -53,6 +53,7 @@ extern s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym; extern bool scx_bpf_consume(u64 dsq_id) __ksym; extern u32 scx_bpf_dispatch_nr_slots(void) __ksym; extern void scx_bpf_dispatch(struct task_struct *p, u64 dsq_id, u64 slice, u64 enq_flags) __ksym; +extern void scx_bpf_kick_cpu(s32 cpu, u64 flags) __ksym; extern s32 scx_bpf_dsq_nr_queued(u64 dsq_id) __ksym; extern bool scx_bpf_test_and_clear_cpu_idle(s32 cpu) __ksym; extern s32 scx_bpf_pick_idle_cpu(const cpumask_t *cpus_allowed) __ksym;
tools/sched_ext/scx_example_central.bpf.c new file +229 -0
229 lines not on this page · raw message
tools/sched_ext/scx_example_central.c new file +91 -0
91 lines not on this page · raw message
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 22/31 sched_ext: Add task state tracking operations
In reply to Tejun HeoBeing able to track the task runnable and running state transitions are useful for a variety of purposes including latency tracking and load factor calculation.
Currently, BPF schedulers don't have a good way of tracking these transitions. Becoming runnable can be determined from ops.enqueue() but becoming quiescent can only be inferred from the lack of subsequent enqueue. Also, as the local dsq can have multiple tasks and some events are handled in the sched_ext core, it's difficult to determine when a given task starts and stops executing.
This patch adds sched_ext_ops.runnable(), .running(), .stopping() and .quiescent() operations to track the task runnable and running state transitions. They're mostly self explanatory; however, we want to ensure that running <-> stopping transitions are always contained within runnable <-> quiescent transitions which is a bit different from how the scheduler core behaves. This adds a bit of complication. See the comment in dequeue_task_scx().
--- include/linux/sched/ext.h | 65 +++++++++++++++++++++++++++++++++++++++ kernel/sched/ext.c | 31 +++++++++++++++++++ 2 files changed, 96 insertions(+)
include/linux/sched/ext.h +65 -0
@@ -209,6 +209,71 @@ struct sched_ext_ops {*/ void (*consume_final)(s32 cpu); +/** +* runnable - A task is becoming runnable on its associated CPU +* @p: task becoming runnable +* @enq_flags: %SCX_ENQ_* +* +* This and the following three functions can be used to track a task's +* execution state transitions. A task becomes ->runnable() on a CPU, +* and then goes through one or more ->running() and ->stopping() pairs +* as it runs on the CPU, and eventually becomes ->quiescent() when it's +* done running on the CPU. +* +* @p is becoming runnable on the CPU because it's +* +* - waking up (%SCX_ENQ_WAKEUP) +* - being moved from another CPU +* - being restored after temporarily taken off the queue for an +* attribute change. +* +* This and ->enqueue() are related but not coupled. This operation +* notifies @p's state transition and may not be followed by ->enqueue() +* e.g. when @p is being dispatched to a remote CPU. Likewise, a task +* may be ->enqueue()'d without being preceded by this operation e.g. +* after exhausting its slice. +*/ +void (*runnable)(struct task_struct *p,u64 enq_flags); + +/** +* running - A task is starting to run on its associated CPU +* @p: task starting to run +* +* See ->runnable() for explanation on the task state notifiers. +*/ +void (*running)(struct task_struct *p); + +/** +* stopping - A task is stopping execution +* @p: task stopping to run +* @runnable: is task @p still runnable? +* +* See ->runnable() for explanation on the task state notifiers. If +* !@runnable, ->quiescent() will be invoked after this operation +* returns. +*/ +void (*stopping)(struct task_struct *p,bool runnable); + +/** +* quiescent - A task is becoming not runnable on its associated CPU +* @p: task becoming not runnable +* @deq_flags: %SCX_DEQ_* +* +* See ->runnable() for explanation on the task state notifiers. +* +* @p is becoming quiescent on the CPU because it's +* +* - sleeping (%SCX_DEQ_SLEEP) +* - being moved to another CPU +* - being temporarily taken off the queue for an attribute change +* (%SCX_DEQ_SAVE) +* +* This and ->dequeue() are related but not coupled. This operation +* notifies @p's state transition and may not be preceded by ->dequeue() +* e.g. when @p is being dispatched to a remote CPU. +*/ +void (*quiescent)(struct task_struct *p,u64 deq_flags); +/** * yield - Yield CPU * @from: yielding task
kernel/sched/ext.c +31 -0
@@ -670,6 +670,9 @@ static void enqueue_task_scx(struct rq *rq, struct task_struct *p, int enq_flags rq->scx.nr_running++;add_nr_running (rq,1 ); +if (SCX_HAS_OP (runnable)) + scx_ops.runnable (p, enq_flags); +do_enqueue_task (rq, p, enq_flags, sticky_cpu); }
@@ -716,6 +719,26 @@ static void dequeue_task_scx(struct rq *rq, struct task_struct *p, int deq_flagsbreak ; } +/* +* A currently running task which is going off @rq first gets dequeued +* and then stops running. As we want running <-> stopping transitions +* to be contained within runnable <-> quiescent transitions, trigger +* ->stopping() early here instead of in put_prev_task_scx(). +* +* @p may go through multiple stopping <-> running transitions between +* here and put_prev_task_scx() if task attribute changes occur while +* balance_scx() leaves @rq unlocked. However, they don't contain any +* information meaningful to the BPF scheduler and can be suppressed by +* skipping the callbacks if the task is !QUEUED. +*/ +if (SCX_HAS_OP (stopping) &&task_current (rq, p)) { +update_curr_scx (rq); + scx_ops.stopping (p, false); + } + +if (SCX_HAS_OP (quiescent)) + scx_ops.quiescent (p, deq_flags); + p->scx.flags &= ~SCX_TASK_QUEUED ; scx_rq->nr_running--;sub_nr_running (rq,1 );
@@ -1223,6 +1246,10 @@ static void set_next_task_scx(struct rq *rq, struct task_struct *p, bool first) p->se.exec_start =rq_clock_task (rq); +/* see dequeue_task_scx() on why we skip when !QUEUED */ +if (SCX_HAS_OP (running) && (p->scx.flags &SCX_TASK_QUEUED )) + scx_ops.running (p); +watchdog_unwatch_task (p, true); }
@@ -1230,6 +1257,10 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p) {update_curr_scx (rq); +/* see dequeue_task_scx() on why we skip when !QUEUED */ +if (SCX_HAS_OP (stopping) && (p->scx.flags &SCX_TASK_QUEUED )) + scx_ops.stopping (p, true); +/* * If we're being called from put_prev_task_balance(), balance_scx() may * have decided that @p should keep running.
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 23/31 sched_ext: Implement tickless support
In reply to Tejun HeoAllow BPF schedulers to indicate tickless operation by setting p->scx.slice to SCX_SLICE_INF. A CPU whose current task has infinte slice goes into tickless operation.
scx_example_central is updated to use tickless operations for all tasks and instead use a BPF timer to expire slices. This also uses the SCX_ENQ_PREEMPT and task state tracking added by the previous patches.
Currently, there is no way to pin the timer on the central CPU, so it may end up on one of the worker CPUs; however, outside of that, the worker CPUs can go tickless both while running sched_ext tasks and idling.
With schbench running, scx_example_central shows:
root@test ~# grep ^LOC /proc/interrupts; sleep 10; grep ^LOC /proc/interrupts
LOC: 142024 656 664 449 Local timer interrupts LOC: 161663 663 665 449 Local timer interrupts
Without it:
root@test ~ [SIGINT]# grep ^LOC /proc/interrupts; sleep 10; grep ^LOC /proc/interrupts
LOC: 188778 3142 3793 3993 Local timer interrupts LOC: 198993 5314 6323 6438 Local timer interrupts
While scx_example_central itself is too barebone to be useful as a production scheduler, a more featureful central scheduler can be built using the same approach. Google's experience shows that such an approach can have significant benefits for certain applications such as VM hosting.
--- include/linux/sched/ext.h | 1 + kernel/sched/core.c | 9 +- kernel/sched/ext.c | 43 +++++- kernel/sched/ext.h | 2 + kernel/sched/sched.h | 6 + tools/sched_ext/scx_example_central.bpf.c | 160 +++++++++++++++++++++- tools/sched_ext/scx_example_central.c | 3 +- 7 files changed, 212 insertions(+), 12 deletions(-)
include/linux/sched/ext.h +1 -0
@@ -19,6 +19,7 @@ enum scx_consts {SCX_EXIT_MSG_LEN =1024 ,SCX_SLICE_DFL =20 *NSEC_PER_MSEC , + SCX_SLICE_INF = U64_MAX, /* infinite, implies nohz */ };/*
kernel/sched/core.c +6 -3
@@ -1200,13 +1200,16 @@ bool sched_can_stop_tick(struct rq *rq)return true;/* -* If there are no DL,RR/FIFO tasks, there must only be CFS tasks left; -* if there's more than one we need the tick for involuntary -* preemption. +* If there are no DL,RR/FIFO tasks, there must only be CFS or SCX tasks +* left. For CFS, if there's more than one we need the tick for +* involuntary preemption. For SCX, ask. */ if (!scx_switched_all () && rq->nr_running >1 )return false; +if (scx_enabled () && !scx_can_stop_tick (rq)) +return false; + return true; }#endif /* CONFIG_NO_HZ_FULL */
kernel/sched/ext.c +41 -2
73 lines not on this page · raw message
kernel/sched/ext.h +2 -0
@@ -94,6 +94,7 @@ void scx_post_fork(struct task_struct *p);void scx_cancel_fork (struct task_struct *p);int balance_scx (struct rq *rq,struct task_struct *prev,struct rq_flags *rf);int scx_check_setscheduler (struct task_struct *p,int policy); +bool scx_can_stop_tick (struct rq *rq);void init_sched_ext_class (void ); __printf(2, 3) void scx_ops_error_type(enum scx_exit_type type,
@@ -156,6 +157,7 @@ static inline int balance_scx(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { return 0; }static inline int scx_check_setscheduler (struct task_struct *p,int policy) {return 0 ; } +static inline bool scx_can_stop_tick (struct rq *rq) {return true; }static inline void init_sched_ext_class (void ) {}static inline void scx_notify_sched_tick (void ) {}
kernel/sched/sched.h +6 -0
@@ -690,11 +690,17 @@ struct cfs_rq { }; #ifdef CONFIG_SCHED_CLASS_EXT +/* scx_rq->flags, protected by the rq lock */ +enum scx_rq_flags { + SCX_RQ_CAN_STOP_TICK = 1 << 0, +}; + struct scx_rq { struct scx_dispatch_q local_dsq; struct list_head watchdog_list; u64 ops_qseq; u32 nr_running; + u32 flags; #ifdef CONFIG_SMP cpumask_var_t cpus_to_kick; cpumask_var_t cpus_to_preempt;
tools/sched_ext/scx_example_central.bpf.c +154 -6
218 lines not on this page · raw message
tools/sched_ext/scx_example_central.c +2 -1
@@ -76,7 +76,8 @@ int main(int argc, char **argv) skel->bss->nr_locals, skel->bss->nr_queued, skel->bss->nr_lost_pids); -printf (" dispatch:%10lu mismatch:%10lu overflow:%10lu\n" , +printf ("timer:%10lu dispatch:%10lu mismatch:%10lu overflow:%10lu\n" , + skel->bss->nr_timers, skel->bss->nr_dispatches, skel->bss->nr_mismatches, skel->bss->nr_overflows);
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 24/31 sched_ext: Add cgroup support
In reply to Tejun HeoAdd sched_ext_ops operations to init/exit cgroups, and track task migrations and config changes. Because different BPF schedulers may implement different subsets of CPU control features, allow BPF schedulers to pick which cgroup interface files to enable using SCX_OPS_CGROUP_KNOB_* flags. For now, only the weight knobs are supported but adding more should be straightforward.
While a BPF scheduler is being enabled and disabled, relevant cgroup operations are locked out using scx_cgroup_rwsem. This avoids situations like task prep taking place while the task is being moved across cgroups, making things easier for BPF schedulers.
This patch also adds scx_example_pair which implements a variant of core scheduling where a hyperthread pair only run tasks from the same cgroup. The BPF scheduler achieves this by putting tasks into per-cgroup queues, time-slicing the cgroup to run for each pair first, and then scheduling within the cgroup. See the header comment in scx_example_pair.bpf.c for more details.
Note that scx_example_pair's cgroup-boundary guarantee breaks down for tasks running in higher priority scheduler classes. This will be addressed by a followup patch which implements a mechanism to track CPU preemption.
--- include/linux/sched/ext.h | 96 ++++- init/Kconfig | 5 + kernel/sched/core.c | 69 ++- kernel/sched/ext.c | 326 ++++++++++++++- kernel/sched/ext.h | 23 + kernel/sched/sched.h | 12 +- tools/sched_ext/.gitignore | 1 + tools/sched_ext/Makefile | 9 +- tools/sched_ext/scx_example_pair.bpf.c | 554 +++++++++++++++++++++++++ tools/sched_ext/scx_example_pair.c | 143 +++++++ tools/sched_ext/scx_example_pair.h | 10 + 11 files changed, 1226 insertions(+), 22 deletions(-) create mode 100644 tools/sched_ext/scx_example_pair.bpf.c create mode 100644 tools/sched_ext/scx_example_pair.c create mode 100644 tools/sched_ext/scx_example_pair.h
include/linux/sched/ext.h +93 -3
@@ -12,6 +12,8 @@#include <linux/rhashtable.h> #include <linux/llist.h> +struct cgroup ; +enum scx_consts {SCX_OPS_NAME_LEN =128 ,SCX_EXIT_REASON_LEN =128 ,
@@ -109,14 +111,27 @@ enum scx_ops_flags {*/ SCX_OPS_ENQ_EXITING =1LLU <<2 , +/* +* CPU cgroup knob enable flags +*/ +SCX_OPS_CGROUP_KNOB_WEIGHT =1LLU <<16 ,/* cpu.weight */ +SCX_OPS_ALL_FLAGS =SCX_OPS_KEEP_BUILTIN_IDLE |SCX_OPS_ENQ_LAST | - SCX_OPS_ENQ_EXITING, +SCX_OPS_ENQ_EXITING | + SCX_OPS_CGROUP_KNOB_WEIGHT, };/* argument container for ops.enable() and friends */ struct scx_enable_args { -/* empty for now */ +/* the cgroup the task is joining */ +struct cgroup *cgroup; +}; + +/* argument container for ops->cgroup_init() */ +struct scx_cgroup_init_args { +/* the weight of the cgroup [1..10000] */ +u32 weight; };/**
@@ -341,7 +356,8 @@ struct sched_ext_ops {* @p: task to enable BPF scheduling for * @args: enable arguments, see the struct definition * -* Enable @p for BPF scheduling. @p will start running soon. +* Enable @p for BPF scheduling. @p is now in the cgroup specified for +* the preceding prep_enable() and will start running soon. */ void (*enable)(struct task_struct *p,struct scx_enable_args *args);
@@ -365,6 +381,77 @@ struct sched_ext_ops {*/ void (*disable)(struct task_struct *p); +/** +* cgroup_init - Initialize a cgroup +* @cgrp: cgroup being initialized +* @args: init arguments, see the struct definition +* +* Either the BPF scheduler is being loaded or @cgrp created, initialize +* @cgrp for sched_ext. This operation may block. +* +* Return 0 for success, -errno for failure. An error return while +* loading will abort loading of the BPF scheduler. During cgroup +* creation, it will abort the specific cgroup creation. +*/ +s32 (*cgroup_init)(struct cgroup *cgrp, +struct scx_cgroup_init_args *args); + +/** +* cgroup_exit - Exit a cgroup +* @cgrp: cgroup being exited +* +* Either the BPF scheduler is being unloaded or @cgrp destroyed, exit +* @cgrp for sched_ext. This operation my block. +*/ +void (*cgroup_exit)(struct cgroup *cgrp); + +/** +* cgroup_prep_move - Prepare a task to be moved to a different cgroup +* @p: task being moved +* @from: cgroup @p is being moved from +* @to: cgroup @p is being moved to +* +* Prepare @p for move from cgroup @from to @to. This operation may +* block and can be used for allocations. +* +* Return 0 for success, -errno for failure. An error return aborts the +* migration. +*/ +s32 (*cgroup_prep_move)(struct task_struct *p, +struct cgroup *from,struct cgroup *to); + +/** +* cgroup_move - Commit cgroup move +* @p: task being moved +* @from: cgroup @p is being moved from +* @to: cgroup @p is being moved to +* +* Commit the move. @p is dequeued during this operation. +*/ +void (*cgroup_move)(struct task_struct *p, +struct cgroup *from,struct cgroup *to); + +/** +* cgroup_cancel_move - Cancel cgroup move +* @p: task whose cgroup move is being canceled +* @from: cgroup @p was being moved from +* @to: cgroup @p was being moved to +* +* @p was cgroup_prep_move()'d but failed before reaching cgroup_move(). +* Undo the preparation. +*/ +void (*cgroup_cancel_move)(struct task_struct *p, +struct cgroup *from,struct cgroup *to); + +/** +* cgroup_set_weight - A cgroup's weight is being changed +* @cgrp: cgroup whose weight is being updated +* @weight: new weight [1..10000] +* +* Update @tg's weight to @weight. +*/ +void (*cgroup_set_weight)(struct cgroup *cgrp,u32 weight); +/* * All online ops must come before ops.init(). */
@@ -481,6 +568,9 @@ struct sched_ext_entity {/* cold fields */ struct list_head tasks_node; +#ifdef CONFIG_EXT_GROUP_SCHED +struct cgroup *cgrp_moving_from; +#endif };void sched_ext_free (struct task_struct *p);
init/Kconfig +5 -0
@@ -1037,6 +1037,11 @@ config RT_GROUP_SCHED realtime bandwidth for them. See Documentation/scheduler/sched-rt-group.rst for more information. +config EXT_GROUP_SCHED + bool + depends on SCHED_CLASS_EXT && CGROUP_SCHED + default y + endif #CGROUP_SCHED config UCLAMP_TASK_GROUP
kernel/sched/core.c +60 -9
180 lines not on this page · raw message
kernel/sched/ext.c +319 -7
432 lines not on this page · raw message
kernel/sched/ext.h +23 -0
@@ -59,6 +59,11 @@ enum scx_deq_flags { SCX_DEQ_SLEEP = DEQUEUE_SLEEP, }; +enum scx_tg_flags { +SCX_TG_ONLINE =1U <<0 , +SCX_TG_INITED =1U <<1 , +}; +enum scx_kick_flags {SCX_KICK_PREEMPT =1LLU <<0 ,/* force scheduling on the CPU */ };
@@ -185,3 +190,21 @@ static inline void scx_update_idle(struct rq *rq, bool idle)#else static inline void scx_update_idle (struct rq *rq,bool idle) {}#endif + +#ifdef CONFIG_EXT_GROUP_SCHED +int scx_tg_online (struct task_group *tg); +void scx_tg_offline (struct task_group *tg); +int scx_cgroup_can_attach (struct cgroup_taskset *tset); +void scx_cgroup_move_task (struct task_struct *p); +void scx_cgroup_finish_attach (void ); +void scx_cgroup_cancel_attach (struct cgroup_taskset *tset); +void scx_group_set_weight (struct task_group *tg,unsigned long cgrp_weight); +#else /* CONFIG_EXT_GROUP_SCHED */ +static inline int scx_tg_online (struct task_group *tg) {return 0 ; } +static inline void scx_tg_offline (struct task_group *tg) {} +static inline int scx_cgroup_can_attach (struct cgroup_taskset *tset) {return 0 ; } +static inline void scx_cgroup_move_task (struct task_struct *p) {} +static inline void scx_cgroup_finish_attach (void ) {} +static inline void scx_cgroup_cancel_attach (struct cgroup_taskset *tset) {} +static inline void scx_group_set_weight (struct task_group *tg,unsigned long cgrp_weight) {} +#endif /* CONFIG_EXT_GROUP_SCHED */
kernel/sched/sched.h +11 -1
@@ -406,6 +406,11 @@ struct task_group {struct rt_bandwidth rt_bandwidth;#endif +#ifdef CONFIG_EXT_GROUP_SCHED +u32 scx_flags;/* SCX_TG_* */ +u32 scx_weight; +#endif +struct rcu_head rcu;struct list_head list;
@@ -535,6 +540,11 @@ extern void set_task_rq_fair(struct sched_entity *se,static inline void set_task_rq_fair (struct sched_entity *se,struct cfs_rq *prev,struct cfs_rq *next) { }#endif /* CONFIG_SMP */ +#else /* CONFIG_FAIR_GROUP_SCHED */ +static inline int sched_group_set_shares (struct task_group *tg,unsigned long shares) +{ +return 0 ; +}#endif /* CONFIG_FAIR_GROUP_SCHED */ #else /* CONFIG_CGROUP_SCHED */
@@ -3260,7 +3270,7 @@ static inline void update_current_exec_runtime(struct task_struct *curr, #ifdef CONFIG_CGROUP_SCHED enum cpu_cftype_id { -#ifdef CONFIG_FAIR_GROUP_SCHED +#if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_EXT_GROUP_SCHED) CPU_CFTYPE_WEIGHT, CPU_CFTYPE_WEIGHT_NICE, CPU_CFTYPE_IDLE,
tools/sched_ext/.gitignore +1 -0
@@ -1,6 +1,7 @@ scx_example_dummy scx_example_qmap scx_example_central +scx_example_pair *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +7 -2
@@ -114,7 +114,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -Wno-compare-distinct-pointer-types \ -O2 -mcpu=v3 -all: scx_example_dummy scx_example_qmap scx_example_central +all: scx_example_dummy scx_example_qmap scx_example_central scx_example_pair # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -177,10 +177,15 @@ scx_example_central: scx_example_central.c scx_example_central.skel.h user_exit_ $(CC) $(CFLAGS) -c $< -o [email protected] $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) +scx_example_pair: scx_example_pair.c scx_example_pair.skel.h user_exit_info.h + $(CC) $(CFLAGS) -c $< -o [email protected] + $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) + clean: rm -rf $(SCRATCH_DIR) $(HOST_SCRATCH_DIR) rm -f *.o *.bpf.o *.skel.h *.subskel.h - rm -f scx_example_dummy scx_example_qmap scx_example_central + rm -f scx_example_dummy scx_example_qmap scx_example_central \ + scx_example_pair .PHONY: all clean
tools/sched_ext/scx_example_pair.bpf.c new file +554 -0
554 lines not on this page · raw message
tools/sched_ext/scx_example_pair.c new file +143 -0
143 lines not on this page · raw message
tools/sched_ext/scx_example_pair.h new file +10 -0
@@ -0,0 +1,10 @@ +#ifndef __SCX_EXAMPLE_PAIR_H +#define __SCX_EXAMPLE_PAIR_H + +enum { +MAX_CPUS =4096 , +MAX_QUEUED =4096 , +MAX_CGRPS =4096 , +}; + +#endif /* __SCX_EXAMPLE_PAIR_H */
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 25/31 sched_ext: Implement SCX_KICK_WAIT
In reply to Tejun HeoFrom: David Vernet <[email protected]>
If set when calling scx_bpf_kick_cpu(), the invoking CPU will busy wait for the kicked cpu to enter the scheduler. This will be used to improve the exclusion guarantees in scx_example_pair.
--- kernel/sched/core.c | 4 +++- kernel/sched/ext.c | 36 ++++++++++++++++++++++++++++++++++-- kernel/sched/ext.h | 20 ++++++++++++++++++++ kernel/sched/sched.h | 2 ++ 4 files changed, 59 insertions(+), 3 deletions(-)
kernel/sched/core.c +3 -1
@@ -5886,8 +5886,10 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)for_each_active_class (class) { p = class->pick_next_task (rq); -if (p) +if (p) { +scx_notify_pick_next_task (rq, p, class);return p; + } }BUG ();/* The idle class should always have a runnable task. */
kernel/sched/ext.c +34 -2
@@ -109,8 +109,9 @@ unsigned long last_timeout_check = INITIAL_JIFFIES;static struct delayed_work check_timeout_work; -/* idle tracking */ #ifdef CONFIG_SMP + +/* idle tracking */ #ifdef CONFIG_CPUMASK_OFFSTACK #define CL_ALIGNED_IF_ONSTACK #else
@@ -123,7 +124,11 @@ static struct { } idle_masks CL_ALIGNED_IF_ONSTACK; static bool __cacheline_aligned_in_smp has_idle_cpus; -#endif + +/* for %SCX_KICK_WAIT */ +static u64 __percpu *kick_cpus_pnt_seqs; + +#endif /* CONFIG_SMP */ /* * Direct dispatch marker.
@@ -2959,6 +2964,7 @@ static const struct sysrq_key_op sysrq_sched_ext_reset_op = {static void kick_cpus_irq_workfn (struct irq_work *irq_work) {struct rq *this_rq =this_rq (); +u64 *pseqs =this_cpu_ptr (kick_cpus_pnt_seqs);int this_cpu =cpu_of (this_rq);int cpu;
@@ -2972,14 +2978,32 @@ static void kick_cpus_irq_workfn(struct irq_work *irq_work)if (cpumask_test_cpu (cpu, this_rq->scx.cpus_to_preempt) && rq->curr->sched_class == &ext_sched_class) rq->curr->scx.slice =0 ; + pseqs[cpu] = rq->scx.pnt_seq; resched_curr(rq); + }else { +cpumask_clear_cpu (cpu, this_rq->scx.cpus_to_wait); }raw_spin_rq_unlock_irqrestore (rq, flags); } +for_each_cpu_andnot (cpu, this_rq->scx.cpus_to_wait, +cpumask_of (this_cpu)) { +/* +* Pairs with smp_store_release() issued by this CPU in +* scx_notify_pick_next_task() on the resched path. +* +* We busy-wait here to guarantee that no other task can be +* scheduled on our core before the target CPU has entered the +* resched path. +*/ +while (smp_load_acquire (&cpu_rq (cpu)->scx.pnt_seq) == pseqs[cpu]) +cpu_relax (); + } +cpumask_clear (this_rq->scx.cpus_to_kick);cpumask_clear (this_rq->scx.cpus_to_preempt); +cpumask_clear (this_rq->scx.cpus_to_wait); }#endif
@@ -2999,6 +3023,11 @@ void __init init_sched_ext_class(void)#ifdef CONFIG_SMP BUG_ON (!alloc_cpumask_var (&idle_masks.cpu,GFP_KERNEL ));BUG_ON (!alloc_cpumask_var (&idle_masks.smt,GFP_KERNEL )); + + kick_cpus_pnt_seqs =__alloc_percpu (sizeof (kick_cpus_pnt_seqs[0 ]) * +num_possible_cpus (), + __alignof__(kick_cpus_pnt_seqs [0 ])); +BUG_ON (!kick_cpus_pnt_seqs);#endif for_each_possible_cpu (cpu) {struct rq *rq =cpu_rq (cpu);
@@ -3009,6 +3038,7 @@ void __init init_sched_ext_class(void)#ifdef CONFIG_SMP BUG_ON (!zalloc_cpumask_var (&rq->scx.cpus_to_kick,GFP_KERNEL ));BUG_ON (!zalloc_cpumask_var (&rq->scx.cpus_to_preempt,GFP_KERNEL )); +BUG_ON (!zalloc_cpumask_var (&rq->scx.cpus_to_wait,GFP_KERNEL ));init_irq_work (&rq->scx.kick_cpus_irq_work, kick_cpus_irq_workfn);#endif }
@@ -3228,6 +3258,8 @@ void scx_bpf_kick_cpu(s32 cpu, u64 flags)cpumask_set_cpu (cpu, rq->scx.cpus_to_kick);if (flags &SCX_KICK_PREEMPT )cpumask_set_cpu (cpu, rq->scx.cpus_to_preempt); +if (flags &SCX_KICK_WAIT ) +cpumask_set_cpu (cpu, rq->scx.cpus_to_wait);irq_work_queue (&rq->scx.kick_cpus_irq_work);preempt_enable ();
kernel/sched/ext.h +20 -0
@@ -66,6 +66,7 @@ enum scx_tg_flags {enum scx_kick_flags {SCX_KICK_PREEMPT =1LLU <<0 ,/* force scheduling on the CPU */ +SCX_KICK_WAIT =1LLU <<1 ,/* wait for the CPU to be rescheduled */ };#ifdef CONFIG_SCHED_CLASS_EXT
@@ -107,6 +108,22 @@ __printf(2, 3) void scx_ops_error_type(enum scx_exit_type type, #define scx_ops_error(fmt, args...) \ scx_ops_error_type(SCX_EXIT_ERROR, fmt, ##args) +static inline void scx_notify_pick_next_task (struct rq *rq, +const struct task_struct *p, +const struct sched_class *active) +{ +#ifdef CONFIG_SMP +if (!scx_enabled ()) +return ; +/* +* Pairs with the smp_load_acquire() issued by a CPU in +* kick_cpus_irq_workfn() who is waiting for this CPU to perform a +* resched. +*/ +smp_store_release (&rq->scx.pnt_seq, rq->scx.pnt_seq +1 ); +#endif +} +static inline void scx_notify_sched_tick (void ) {unsigned long last_check, timeout;
@@ -164,6 +181,9 @@ static inline int scx_check_setscheduler(struct task_struct *p, int policy) { return 0; }static inline bool scx_can_stop_tick (struct rq *rq) {return true; }static inline void init_sched_ext_class (void ) {} +static inline void scx_notify_pick_next_task (struct rq *rq, +const struct task_struct *p, +const struct sched_class *active) {}static inline void scx_notify_sched_tick (void ) {}#define for_each_active_class for_each_class
kernel/sched/sched.h +2 -0
@@ -714,6 +714,8 @@ struct scx_rq {#ifdef CONFIG_SMP cpumask_var_t cpus_to_kick;cpumask_var_t cpus_to_preempt; +cpumask_var_t cpus_to_wait; +u64 pnt_seq;struct irq_work kick_cpus_irq_work;#endif };
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 26/31 sched_ext: Implement sched_ext_ops.cpu_acquire/release()
In reply to Tejun HeoFrom: David Vernet <[email protected]>
Scheduler classes are strictly ordered and when a higher priority class has tasks to run, the lower priority ones lose access to the CPU. Being able to monitor and act on these events are necessary for use cases includling strict core-scheduling and latency management.
This patch adds two operations ops.cpu_acquire() and .cpu_release(). The former is invoked when a CPU becomes available to the BPF scheduler and the opposite for the latter. This patch also implements scx_bpf_reenqueue_local() which can be called from .cpu_release() to trigger requeueing of all tasks in the local dsq of the CPU so that the tasks can be reassigned to other available CPUs.
scx_example_pair is updated to use .cpu_acquire/release() along with %SCX_KICK_WAIT to make the pair scheduling guarantee strict even when a CPU is preempted by a higher priority scheduler class.
scx_example_qmap is updated to use .cpu_acquire/release() to empty the local dsq of a preempted CPU. A similar approach can be adopted by BPF schedulers that want to have a tight control over latency.
--- include/linux/sched/ext.h | 48 ++++++++++ kernel/sched/ext.c | 122 ++++++++++++++++++++++++- kernel/sched/ext.h | 22 ++++- kernel/sched/sched.h | 1 + tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_pair.bpf.c | 101 +++++++++++++++++++- tools/sched_ext/scx_example_qmap.bpf.c | 35 +++++++ 7 files changed, 323 insertions(+), 7 deletions(-)
include/linux/sched/ext.h +48 -0
@@ -134,6 +134,32 @@ struct scx_cgroup_init_args {u32 weight; }; +enum scx_cpu_preempt_reason { +/* next task is being scheduled by &sched_class_rt */ +SCX_CPU_PREEMPT_RT , +/* next task is being scheduled by &sched_class_dl */ +SCX_CPU_PREEMPT_DL , +/* next task is being scheduled by &sched_class_stop */ +SCX_CPU_PREEMPT_STOP , +/* unknown reason for SCX being preempted */ +SCX_CPU_PREEMPT_UNKNOWN , +}; + +/* +* Argument container for ops->cpu_acquire(). Currently empty, but may be +* expanded in the future. +*/ +struct scx_cpu_acquire_args {}; + +/* argument container for ops->cpu_release() */ +struct scx_cpu_release_args { +/* the reason the CPU was preempted */ +enum scx_cpu_preempt_reason reason; + +/* the task that's going to be scheduled on the CPU */ +const struct task_struct *task; +}; +/** * struct sched_ext_ops - Operation table for BPF scheduler implementation *
@@ -336,6 +362,28 @@ struct sched_ext_ops {*/ void (*update_idle)(s32 cpu,bool idle); +/** +* cpu_acquire - A CPU is becoming available to the BPF scheduler +* @cpu: The CPU being acquired by the BPF scheduler. +* @args: Acquire arguments, see the struct definition. +* +* A CPU that was previously released from the BPF scheduler is now once +* again under its control. +*/ +void (*cpu_acquire)(s32 cpu,struct scx_cpu_acquire_args *args); + +/** +* cpu_release - A CPU is taken away from the BPF scheduler +* @cpu: The CPU being released by the BPF scheduler. +* @args: Release arguments, see the struct definition. +* +* The specified CPU is no longer under the control of the BPF +* scheduler. This could be because it was preempted by a higher +* priority sched_class, though there may be other reasons as well. The +* caller should consult @args->reason to determine the cause. +*/ +void (*cpu_release)(s32 cpu,struct scx_cpu_release_args *args); +/** * prep_enable - Prepare to enable BPF scheduling for a task * @p: task to prepare BPF scheduling for
kernel/sched/ext.c +121 -1
176 lines not on this page · raw message
kernel/sched/ext.h +21 -1
@@ -27,6 +27,17 @@ enum scx_enq_flags {*/ SCX_ENQ_PREEMPT =1LLU <<32 , +/* +* The task being enqueued was previously enqueued on the current CPU's +* %SCX_DSQ_LOCAL, but was removed from it in a call to the +* bpf_scx_reenqueue_local() kfunc. If bpf_scx_reenqueue_local() was +* invoked in a ->cpu_release() callback, and the task is again +* dispatched back to %SCX_LOCAL_DSQ by this current ->enqueue(), the +* task will not be scheduled on the CPU until at least the next invocation +* of the ->cpu_acquire() callback. +*/ + SCX_ENQ_REENQ = 1LLU << 40, +/* * The task being enqueued is the only task available for the cpu. By * default, ext core keeps executing such tasks but when
@@ -93,6 +104,8 @@ DECLARE_STATIC_KEY_FALSE(__scx_switched_all);#define scx_enabled () static_branch_unlikely(&__scx_ops_enabled)#define scx_switched_all () static_branch_unlikely(&__scx_switched_all) +DECLARE_STATIC_KEY_FALSE (scx_ops_cpu_preempt); +bool task_on_scx (struct task_struct *p);void scx_pre_fork (struct task_struct *p);int scx_fork (struct task_struct *p);
@@ -108,13 +121,17 @@ __printf(2, 3) void scx_ops_error_type(enum scx_exit_type type, #define scx_ops_error(fmt, args...) \ scx_ops_error_type(SCX_EXIT_ERROR, fmt, ##args) +void __scx_notify_pick_next_task (struct rq *rq, +const struct task_struct *p, +const struct sched_class *active); +static inline void scx_notify_pick_next_task (struct rq *rq,const struct task_struct *p,const struct sched_class *active) { -#ifdef CONFIG_SMP if (!scx_enabled ())return ; +#ifdef CONFIG_SMP /* * Pairs with the smp_load_acquire() issued by a CPU in * kick_cpus_irq_workfn() who is waiting for this CPU to perform a
@@ -122,6 +139,9 @@ static inline void scx_notify_pick_next_task(struct rq *rq,*/ smp_store_release (&rq->scx.pnt_seq, rq->scx.pnt_seq +1 );#endif +if (!static_branch_unlikely (&scx_ops_cpu_preempt)) +return ; +__scx_notify_pick_next_task (rq, p, active); }static inline void scx_notify_sched_tick (void )
kernel/sched/sched.h +1 -0
@@ -711,6 +711,7 @@ struct scx_rq {u64 ops_qseq;u32 nr_running;u32 flags; +bool cpu_released;#ifdef CONFIG_SMP cpumask_var_t cpus_to_kick;cpumask_var_t cpus_to_preempt;
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -60,6 +60,7 @@ extern s32 scx_bpf_pick_idle_cpu(const cpumask_t *cpus_allowed) __ksym; extern void scx_bpf_destroy_dsq(u64 dsq_id) __ksym; extern bool scx_bpf_task_running(const struct task_struct *p) __ksym; extern s32 scx_bpf_task_cpu(const struct task_struct *p) __ksym; +extern u32 scx_bpf_reenqueue_local(void) __ksym;/* XXX - temporary ones to be replaced by generic BPF helpers */ extern struct cgroup *scx_bpf_task_cgroup (const struct task_struct *p) __ksym;
tools/sched_ext/scx_example_pair.bpf.c +96 -5
144 lines not on this page · raw message
tools/sched_ext/scx_example_qmap.bpf.c +35 -0
@@ -11,6 +11,8 @@* * - BPF-side queueing using PIDs. * - Sleepable per-task storage allocation using ops.prep_enable(). +* - Using ops.cpu_release() to handle a higher priority scheduling class taking +* the CPU away. * * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]>
@@ -136,6 +138,22 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)return ; } +/* +* If the task was re-enqueued due to the CPU being preempted by a +* higher priority scheduling class, just re-enqueue the task directly +* on the global DSQ. As we want another CPU to pick it up, find and +* kick an idle CPU. +*/ +if (enq_flags &SCX_ENQ_REENQ ) { +s32 cpu; + +scx_bpf_dispatch (p,SCX_DSQ_GLOBAL ,0 , enq_flags); + cpu =scx_bpf_pick_idle_cpu (p->cpus_ptr); +if (cpu >=0 ) +scx_bpf_kick_cpu (cpu,0 ); +return ; + } +/* Coarsely map the compount weight to a FIFO. */ if (p->scx.weight <=25 ) idx =0 ;
@@ -207,6 +225,22 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cpu, struct task_struct *prev) } } +void BPF_STRUCT_OPS (qmap_cpu_release ,s32 cpu,struct scx_cpu_release_args *args) +{ +u32 cnt; + +/* +* Called when @cpu is taken by a higher priority scheduling class. This +* makes @cpu no longer available for executing sched_ext tasks. As we +* don't want the tasks in @cpu's local dsq to sit there until @cpu +* becomes available again, re-enqueue them into the global dsq. See +* %SCX_ENQ_REENQ handling in qmap_enqueue(). +*/ + cnt =scx_bpf_reenqueue_local (); +if (cnt) +__sync_fetch_and_add (&nr_reenqueued, cnt); +} +s32 BPF_STRUCT_OPS (qmap_prep_enable ,struct task_struct *p,struct scx_enable_args *args) {
@@ -245,6 +279,7 @@ struct sched_ext_ops qmap_ops = {* spurious dispatches. Let's be lazy and not bother with dequeueing. */ .dispatch = (void *)qmap_dispatch, + .cpu_release = (void *)qmap_cpu_release, .prep_enable = (void *)qmap_prep_enable, .init = (void *)qmap_init, .exit = (void *)qmap_exit,
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 27/31 sched_ext: Implement sched_ext_ops.cpu_online/offline()
In reply to Tejun HeoAdd ops.cpu_online/offline() which are invoked when CPUs come online and offline respectively. As the enqueue path already automatically bypasses tasks to the local dsq on a deactivated CPU, BPF schedulers are guaranteed to see tasks only on CPUs which are between online() and offline().
--- include/linux/sched/ext.h | 18 ++++++++++++++++++ kernel/sched/ext.c | 15 +++++++++++++++ 2 files changed, 33 insertions(+)
include/linux/sched/ext.h +18 -0
@@ -384,6 +384,24 @@ struct sched_ext_ops {*/ void (*cpu_release)(s32 cpu,struct scx_cpu_release_args *args); +/** +* cpu_online - A CPU became online +* @cpu: CPU which just came up +* +* @cpu just came online. @cpu doesn't call ->enqueue() or consume tasks +* associated with other CPUs beforehand. +*/ +void (*cpu_online)(s32 cpu); + +/** +* cpu_offline - A CPU is going offline +* @cpu: CPU which is going offline +* +* @cpu is going offline. @cpu doesn't call ->enqueue() or consume tasks +* associated with other CPUs afterwards. +*/ +void (*cpu_offline)(s32 cpu); +/** * prep_enable - Prepare to enable BPF scheduling for a task * @p: task to prepare BPF scheduling for
kernel/sched/ext.c +15 -0
@@ -1574,6 +1574,18 @@ void __scx_update_idle(struct rq *rq, bool idle) } } +static void rq_online_scx (struct rq *rq,enum rq_onoff_reason reason) +{ +if (SCX_HAS_OP (cpu_online) && reason ==RQ_ONOFF_HOTPLUG ) + scx_ops.cpu_online (cpu_of (rq)); +} + +static void rq_offline_scx (struct rq *rq,enum rq_onoff_reason reason) +{ +if (SCX_HAS_OP (cpu_offline) && reason ==RQ_ONOFF_HOTPLUG ) + scx_ops.cpu_offline (cpu_of (rq)); +} +#else /* !CONFIG_SMP */ static bool test_and_clear_cpu_idle (int cpu) {return false; }
@@ -2049,6 +2061,9 @@ DEFINE_SCHED_CLASS(ext) = { .pick_task = pick_task_scx, .set_cpus_allowed = set_cpus_allowed_scx, + + .rq_online = rq_online_scx, + .rq_offline = rq_offline_scx, #endif .task_tick = task_tick_scx,
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 28/31 sched_ext: Add Documentation/scheduler/sched-ext.rst
In reply to Tejun Heo--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-ext.rst | 230 ++++++++++++++++++++++++++ include/linux/sched/ext.h | 2 + kernel/sched/ext.c | 2 + kernel/sched/ext.h | 2 + 5 files changed, 237 insertions(+) create mode 100644 Documentation/scheduler/sched-ext.rst
Documentation/scheduler/index.rst +1 -0
@@ -18,6 +18,7 @@ Linux Scheduler sched-nice-design sched-rt-group sched-stats + sched-ext sched-debug text_files
Documentation/scheduler/sched-ext.rst new file +230 -0
230 lines not on this page · raw message
include/linux/sched/ext.h +2 -0
@@ -1,5 +1,7 @@/* SPDX-License-Identifier: GPL-2.0 */ /* +* BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst +* * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]> * Copyright (c) 2022 David Vernet <[email protected]>
kernel/sched/ext.c +2 -0
@@ -1,5 +1,7 @@/* SPDX-License-Identifier: GPL-2.0 */ /* +* BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst +* * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]> * Copyright (c) 2022 David Vernet <[email protected]>
kernel/sched/ext.h +2 -0
@@ -1,5 +1,7 @@/* SPDX-License-Identifier: GPL-2.0 */ /* +* BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst +* * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]> * Copyright (c) 2022 David Vernet <[email protected]>
Signature · 1 line
2.38.1
Re: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
Quoted 5 lines · Tejun Heo
Signed-off-by Tejun Heo <[email protected]>Reviewed-by David Vernet <[email protected]>Acked-by Josh Don <[email protected]>Acked-by Hao Luo <[email protected]>Acked-by Barret Rhoden <[email protected]>
No patch description? Really? Please write one.
For patch subject, better write "Documentation: scheduler: document extensible scheduler class".
Review
Quoted 8 lines
(quoted diff) +4
-0+* The system integrity is maintained no matter what the BPF scheduler does. + The default scheduling behavior is restored anytime an error is detected, + a runnable task stalls, or on sysrq-S. +<snipped>...
(quoted diff) +3
-0+Terminating the sched_ext scheduler program, triggering sysrq-S, or +detection of any internal error including stalled runnable tasks aborts the +BPF scheduler and reverts all tasks back to CFS.
IMO the reference to SysRq key can be reworded:
---- >8 ----
Documentation/scheduler/sched-ext.rst +3 -2
@@ -15,7 +15,8 @@ programs - the BPF scheduler. * The system integrity is maintained no matter what the BPF scheduler does. The default scheduling behavior is restored anytime an error is detected, - a runnable task stalls, or on sysrq-S. + a runnable task stalls, or on invoking SysRq key sequence like + :kbd:`SysRq-s`. Switching to and from sched_ext ===============================
@@ -35,7 +36,7 @@ case, all ``SCHED_NORMAL``, ``SCHED_BATCH``, ``SCHED_IDLE`` and ``SCHED_EXT`` tasks are scheduled by sched_ext. In the example schedulers, this mode can be selected with the ``-a`` option. -Terminating the sched_ext scheduler program, triggering sysrq-S, or +Terminating the sched_ext scheduler program, triggering SysRq key, or detection of any internal error including stalled runnable tasks aborts the BPF scheduler and reverts all tasks back to CFS.
Review
Quoted 2 lines
(quoted diff) +2
-0+A task is always *dispatch*ed to a dsq for execution. The task starts +execution when a CPU *consume*s the task from the dsq.
Sphinx reported two warnings:
Documentation/scheduler/sched-ext.rst:117: WARNING: Inline emphasis start-string without end-string. Documentation/scheduler/sched-ext.rst:117: WARNING: Inline emphasis start-string without end-string.
I have to replace with quotes (since "dispatch" and "consume" have different meaning in this context):
---- >8 ----
Documentation/scheduler/sched-ext.rst +2 -2
@@ -114,8 +114,8 @@ there is one global FIFO (``SCX_DSQ_GLOBAL``), and one local dsq per CPU (``SCX_DSQ_LOCAL``). The BPF scheduler can manage an arbitrary number of dsq's using ``scx_bpf_create_dsq()`` and ``scx_bpf_destroy_dsq()``. -A task is always *dispatch*ed to a dsq for execution. The task starts -execution when a CPU *consume*s the task from the dsq. +A task is always "dispatched" to a dsq for execution. The task starts +execution when a CPU "consumes" the task from the dsq. Internally, a CPU only executes tasks which are running on its local dsq, and the ``.consume()`` operation is in fact a transfer of a task from a
Otherwise the doc LGTM.
Thanks.
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Tejun Heo
maintainerRe: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
Hello,
Quoted 8 lines · Bagas Sanjaya
Quoted 5 lines · Tejun Heo
Signed-off-by Tejun Heo <[email protected]>Reviewed-by David Vernet <[email protected]>Acked-by Josh Don <[email protected]>Acked-by Hao Luo <[email protected]>Acked-by Barret Rhoden <[email protected]>No patch description? Really? Please write one.
That's unnecessarily grating. I can add some blurb but here's an honest question. What pertinent information would the description contain that shouldn't be in the doc itself?
Quoted 2 lines
For patch subject, better write "Documentation: scheduler: document extensible scheduler class".
Sounds good.
Quoted 53 lines
---- >8 ----
Documentation/scheduler/sched-ext.rst +3
-2@@ -15,7 +15,8 @@ programs - the BPF scheduler. * The system integrity is maintained no matter what the BPF scheduler does. The default scheduling behavior is restored anytime an error is detected, - a runnable task stalls, or on sysrq-S. + a runnable task stalls, or on invoking SysRq key sequence like + :kbd:`SysRq-s`. Switching to and from sched_ext ===============================@@ -35,7 +36,7 @@ case, all ``SCHED_NORMAL``, ``SCHED_BATCH``, ``SCHED_IDLE`` and ``SCHED_EXT`` tasks are scheduled by sched_ext. In the example schedulers, this mode can be selected with the ``-a`` option. -Terminating the sched_ext scheduler program, triggering sysrq-S, or +Terminating the sched_ext scheduler program, triggering SysRq key, or detection of any internal error including stalled runnable tasks aborts the BPF scheduler and reverts all tasks back to CFS.Review
Quoted 3 lines
(quoted diff) +2
-0+A task is always *dispatch*ed to a dsq for execution. The task starts +execution when a CPU *consume*s the task from the dsq.Sphinx reported two warnings:
Documentation/scheduler/sched-ext.rst:117: WARNING: Inline emphasis start-string without end-string.Documentation/scheduler/sched-ext.rst:117: WARNING: Inline emphasis start-string without end-string.I have to replace with quotes (since "dispatch" and "consume" have different meaning in this context):
---- >8 ----
Documentation/scheduler/sched-ext.rst +2
-2@@ -114,8 +114,8 @@ there is one global FIFO (``SCX_DSQ_GLOBAL``), and one local dsq per CPU (``SCX_DSQ_LOCAL``). The BPF scheduler can manage an arbitrary number of dsq's using ``scx_bpf_create_dsq()`` and ``scx_bpf_destroy_dsq()``. -A task is always *dispatch*ed to a dsq for execution. The task starts -execution when a CPU *consume*s the task from the dsq. +A task is always "dispatched" to a dsq for execution. The task starts +execution when a CPU "consumes" the task from the dsq. Internally, a CPU only executes tasks which are running on its local dsq, and the ``.consume()`` operation is in fact a transfer of a task from a
Quoted 1 line
Otherwise the doc LGTM.
Will apply the suggested changes.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
Quoted 6 lines · Tejun Heo
Quoted 1 line
No patch description? Really? Please write one.
That's unnecessarily grating. I can add some blurb but here's an honest question. What pertinent information would the description contain that shouldn't be in the doc itself?
Sorry I don't know the answer, but the description should at least expand from the patch subject.
Thanks anyway.
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Tejun Heo
maintainerRe: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
Quoted 10 lines · Bagas Sanjaya
Quoted 6 lines · Tejun Heo
Quoted 1 line
No patch description? Really? Please write one.
That's unnecessarily grating. I can add some blurb but here's an honest question. What pertinent information would the description contain that shouldn't be in the doc itself?
Sorry I don't know the answer, but the description should at least expand from the patch subject.
Yeah, I can put some filler text. It just feels a bit silly. Not a big deal at all either way.
Thanks.
Signature · 1 line
tejun
Peter Zijlstra
maintainerRe: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
In reply to Tejun HeoOn Tue, Nov 29, 2022 at 10:23:10PM -1000, Tejun Heo wrote:
If you expect me to read this, please as to provide something readable, not markup gibberish.
Tejun Heo
maintainerRe: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst
Hello,
Quoted 4 lines · Peter Zijlstra
On Tue, Nov 29, 2022 at 10:23:10PM -1000, Tejun Heo wrote:
If you expect me to read this, please as to provide something readable, not markup gibberish.
Hmmm... Everything under Documentation/scheduler is in rst markup. I don't care about the file format. If plain text is preferable, that's fine but that'd look odd in that directory.
For your reading convenience, the following is the formatted output:
https://github.com/htejun/sched_ext/blob/sched_ext/Documentation/scheduler/sched-ext.rst
and the following is the plain text version with markups stripped out. FWIW, while the double-backtick quoting is a bit distracting, there aren't whole lot of markups to strip out.
==========================
Extensible Scheduler Class
==========================
sched_ext is a scheduler class whose behavior can be defined by a set of BPF programs - the BPF scheduler.
* sched_ext exports a full scheduling interface so that any scheduling algorithm can be implemented on top.
* The BPF scheduler can group CPUs however it sees fit and schedule them together, as tasks aren't tied to specific CPUs at the time of wakeup.
* The BPF scheduler can be turned on and off dynamically anytime.
* The system integrity is maintained no matter what the BPF scheduler does. The default scheduling behavior is restored anytime an error is detected, a runnable task stalls, or on invoking SysRq key sequence like SysRq-s.
Switching to and from sched_ext
===============================
CONFIG_SCHED_CLASS_EXT is the config option to enable sched_ext and tools/sched_ext contains the example schedulers.
sched_ext is used only when the BPF scheduler is loaded and running.
If a task explicitly sets its scheduling policy to SCHED_EXT, it will be treated as SCHED_NORMAL and scheduled by CFS until the BPF scheduler is loaded. On load, such tasks will be switched to and scheduled by sched_ext.
The BPF scheduler can choose to schedule all normal and lower class tasks by calling scx_bpf_switch_all() from its init() operation. In this case, all SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE and SCHED_EXT tasks are scheduled by sched_ext. In the example schedulers, this mode can be selected with the -a option.
Terminating the sched_ext scheduler program, triggering SysRq key, or detection of any internal error including stalled runnable tasks aborts the BPF scheduler and reverts all tasks back to CFS.
# make -j16 -C tools/sched_ext
# tools/sched_ext/scx_example_dummy -a
local=0 global=3
local=5 global=24
local=9 global=44
local=13 global=56
local=17 global=72
^CEXIT: BPF scheduler unregisteredIf CONFIG_SCHED_DEBUG is set, the current status of the BPF scheduler and whether a given task is on sched_ext can be determined as follows:
# cat /sys/kernel/debug/sched/ext
ops : dummy
enabled : 1
switching_all : 1
switched_all : 1
enable_state : enabled # grep ext /proc/self/sched
ext.enabled : 1The Basics
==========
Userspace can implement an arbitrary BPF scheduler by loading a set of BPF programs that implement struct sched_ext_ops. The only mandatory field is ops.name which must be a valid BPF object name. All operations are optional. The following modified excerpt is from tools/sched/scx_example_dummy.bpf.c showing a minimal global FIFO scheduler.
s32 BPF_STRUCT_OPS(dummy_init)
{
if (switch_all)
scx_bpf_switch_all();
return 0;
}
void BPF_STRUCT_OPS(dummy_enqueue, struct task_struct *p, u64 enq_flags)
{
if (enq_flags & SCX_ENQ_LOCAL)
scx_bpf_dispatch(p, SCX_DSQ_LOCAL, enq_flags);
else
scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, enq_flags);
}
void BPF_STRUCT_OPS(dummy_exit, struct scx_exit_info *ei)
{
exit_type = ei->type;
}
SEC(".struct_ops")
struct sched_ext_ops dummy_ops = {
.enqueue = (void *)dummy_enqueue,
.init = (void *)dummy_init,
.exit = (void *)dummy_exit,
.name = "dummy",
};Dispatch Queues
---------------
To match the impedance between the scheduler core and the BPF scheduler, sched_ext uses simple FIFOs called DSQs (dispatch queues). By default, there is one global FIFO (SCX_DSQ_GLOBAL), and one local dsq per CPU (SCX_DSQ_LOCAL). The BPF scheduler can manage an arbitrary number of dsq's using scx_bpf_create_dsq() and scx_bpf_destroy_dsq().
A CPU always executes a task from its local DSQ. A task is "dispatched" to a DSQ. A non-local DSQ is "consumed" to transfer a task to the consuming CPU's local DSQ.
When a CPU is looking for the next task to run, if the local DSQ is not empty, the first task is picked. Otherwise, the CPU tries to consume the global DSQ. If that doesn't yield a runnable task either, ops.dispatch() is invoked.
Scheduling Cycle
----------------
The following briefly shows how a waking task is scheduled and executed.
1. When a task is waking up, ops.select_cpu() is the first operation invoked. This serves two purposes. First, CPU selection optimization hint. Second, waking up the selected CPU if idle.
The CPU selected by ops.select_cpu() is an optimization hint and not binding. The actual decision is made at the last step of scheduling. However, there is a small performance gain if the CPU ops.select_cpu() returns matches the CPU the task eventually runs on.
A side-effect of selecting a CPU is waking it up from idle. While a BPF scheduler can wake up any cpu using the scx_bpf_kick_cpu() helper, using ops.select_cpu() judiciously can be simpler and more efficient.
Note that the scheduler core will ignore an invalid CPU selection, for example, if it's outside the allowed cpumask of the task.
2. Once the target CPU is selected, ops.enqueue() is invoked. It can make one of the following decisions:
* Immediately dispatch the task to either the global or local DSQ by calling scx_bpf_dispatch() with SCX_DSQ_GLOBAL or SCX_DSQ_LOCAL, respectively.
* Immediately dispatch the task to a custom DSQ by calling scx_bpf_dispatch() with a DSQ ID which is smaller than 2^63.
* Queue the task on the BPF side.
3. When a CPU is ready to schedule, it first looks at its local DSQ. If empty, it then looks at the global DSQ. If there still isn't a task to run, ops.dispatch() is invoked which can use the following two functions to populate the local DSQ.
* scx_bpf_dispatch() dispatches a task to a DSQ. Any target DSQ can be used - SCX_DSQ_LOCAL, SCX_DSQ_LOCAL_ON | cpu, SCX_DSQ_GLOBAL or a custom DSQ. While scx_bpf_dispatch() currently can't be called with BPF locks held, this is being worked on and will be supported. scx_bpf_dispatch() schedules dispatching rather than performing them immediately. There can be up to ops.dispatch_max_batch pending tasks.
* scx_bpf_consume() tranfers a task from the specified non-local DSQ to the dispatching DSQ. This function cannot be called with any BPF locks held. scx_bpf_consume() flushes the pending dispatched tasks before trying to consume the specified DSQ.
4. After ops.dispatch() returns, if there are tasks in the local DSQ, the CPU runs the first one. If empty, the following steps are taken:
* Try to consume the global DSQ. If successful, run the task.
* If ops.dispatch() has dispatched any tasks, retry #3.
* If the previous task is an SCX task and still runnable, keep executing it (see SCX_OPS_ENQ_LAST).
* Go idle.
Note that the BPF scheduler can always choose to dispatch tasks immediately in ops.enqueue() as illustrated in the above dummy example. If only the built-in DSQs are used, there is no need to implement ops.dispatch() as a task is never queued on the BPF scheduler and both the local and global DSQs are consumed automatically.
Where to Look
=============
* include/linux/sched/ext.h defines the core data structures, ops table and constants.
* kernel/sched/ext.c contains sched_ext core implementation and helpers. The functions prefixed with scx_bpf_ can be called from the BPF scheduler.
* tools/sched_ext/ hosts example BPF scheduler implementations.
* scx_example_dummy[.bpf].c: Minimal global FIFO scheduler example using a custom DSQ.
* scx_example_qmap[.bpf].c: A multi-level FIFO scheduler supporting five levels of priority implemented with BPF_MAP_TYPE_QUEUE.
ABI Instability
===============
The APIs provided by sched_ext to BPF schedulers programs have no stability guarantees. This includes the ops table callbacks and constants defined in include/linux/sched/ext.h, as well as the scx_bpf_ kfuncs defined in kernel/sched/ext.c.
While we will attempt to provide a relatively stable API surface when possible, they are subject to change without warning between kernel versions.
Caveats
=======
* The current implementation isn't safe in that the BPF scheduler can crash the kernel.
* Unsafe cpumask helpers should be replaced by proper generic BPF helpers.
* Currently, all kfunc helpers can be called by any operation as BPF doesn't yet support filtering kfunc calls per struct_ops operation. Some helpers are context sensitive as should be restricted accordingly.
* Timers used by the BPF scheduler should be shut down when aborting.
* There are a couple BPF hacks which are still needed even for sched_ext proper. They should be removed in the near future.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 29/31 sched_ext: Add a basic, userland vruntime scheduler
In reply to Tejun HeoFrom: David Vernet <[email protected]>
This patch adds a new scx_example_userland BPF scheduler that implements a fairly unsophisticated sorted-list vruntime scheduler in userland to demonstrate how most scheduling decisions can be delegated to userland. The scheduler doesn't implement load balancing, and treats all tasks as part of a single domain.
--- tools/sched_ext/.gitignore | 1 + tools/sched_ext/Makefile | 10 +- tools/sched_ext/scx_example_userland.bpf.c | 265 ++++++++++++ tools/sched_ext/scx_example_userland.c | 403 ++++++++++++++++++ tools/sched_ext/scx_example_userland_common.h | 19 + 5 files changed, 696 insertions(+), 2 deletions(-) create mode 100644 tools/sched_ext/scx_example_userland.bpf.c create mode 100644 tools/sched_ext/scx_example_userland.c create mode 100644 tools/sched_ext/scx_example_userland_common.h
tools/sched_ext/.gitignore +1 -0
@@ -2,6 +2,7 @@ scx_example_dummy scx_example_qmap scx_example_central scx_example_pair +scx_example_userland *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +8 -2
@@ -114,7 +114,8 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -Wno-compare-distinct-pointer-types \ -O2 -mcpu=v3 -all: scx_example_dummy scx_example_qmap scx_example_central scx_example_pair +all: scx_example_dummy scx_example_qmap scx_example_central scx_example_pair \ + scx_example_userland # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -181,11 +182,16 @@ scx_example_pair: scx_example_pair.c scx_example_pair.skel.h user_exit_info.h $(CC) $(CFLAGS) -c $< -o [email protected] $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) +scx_example_userland: scx_example_userland.c scx_example_userland.skel.h \ + scx_example_userland_common.h user_exit_info.h + $(CC) $(CFLAGS) -c $< -o [email protected] + $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) + clean: rm -rf $(SCRATCH_DIR) $(HOST_SCRATCH_DIR) rm -f *.o *.bpf.o *.skel.h *.subskel.h rm -f scx_example_dummy scx_example_qmap scx_example_central \ - scx_example_pair + scx_example_pair scx_example_userland .PHONY: all clean
tools/sched_ext/scx_example_userland.bpf.c new file +265 -0
265 lines not on this page · raw message
tools/sched_ext/scx_example_userland.c new file +403 -0
403 lines not on this page · raw message
tools/sched_ext/scx_example_userland_common.h new file +19 -0
@@ -0,0 +1,19 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta, Inc */ + +#ifndef __SCX_USERLAND_COMMON_H +#define __SCX_USERLAND_COMMON_H + +#define USERLAND_MAX_TASKS 8192 + +/* +* An instance of a task that has been enqueued by the kernel for consumption +* by a user space global scheduler thread. +*/ +struct scx_userland_enqueued_task { +__s32 pid; +u64 sum_exec_runtime; +u64 weight; +}; + +#endif // __SCX_USERLAND_COMMON_H
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 30/31 BPF: [TEMPORARY] Nerf BTF scalar value check
In reply to Tejun HeoTHIS IS A TEMPORARY WORKAROUND. WILL BE DROPPED.
This is needed for scx_example_atropos for now. This won't be needed once we have generic BPF bitmask / cpumask helpers.
NOT_SIGNED_OFF
Cc: Alexei Starovoitov <[email protected]>
Cc: Dave Marchevsky <[email protected]>
--- kernel/bpf/btf.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-)
kernel/bpf/btf.c +4 -1
@@ -6400,11 +6400,14 @@ static int btf_check_func_arg_match(struct bpf_verifier_env *env,return ret; } } - +#warning "btf argument scalar test nerfed" +/* if (reg->type == SCALAR_VALUE) continue; bpf_log(log, "R%d is not a scalar\n", regno); return -EINVAL; +*/ +continue ; }if (!btf_type_is_ptr (t)) {
Signature · 1 line
2.38.1
Tejun Heo
maintainerPATCH 31/31 sched_ext: Add a rust userspace hybrid example scheduler
In reply to Tejun HeoFrom: Dan Schatzberg <[email protected]>
Atropos is a multi-domain BPF / userspace hybrid scheduler where the BPF part does simple round robin in each domain and the userspace part calculates the load factor of each domain and tells the BPF part how to load balance the domains.
This scheduler demonstrates dividing scheduling logic between BPF and userspace and using rust to build the userspace part. An earlier variant of this scheduler was used to balance across six domains, each representing a chiplet in a six-chiplet AMD processor, and could match the performance of production setup using CFS.
--- tools/sched_ext/Makefile | 13 +- tools/sched_ext/atropos/.gitignore | 3 + tools/sched_ext/atropos/Cargo.toml | 34 + tools/sched_ext/atropos/build.rs | 70 ++ tools/sched_ext/atropos/rustfmt.toml | 8 + tools/sched_ext/atropos/src/bpf/atropos.bpf.c | 501 ++++++++++++++ tools/sched_ext/atropos/src/bpf/atropos.h | 38 + tools/sched_ext/atropos/src/main.rs | 648 ++++++++++++++++++ .../sched_ext/atropos/src/oss/atropos_sys.rs | 10 + tools/sched_ext/atropos/src/oss/mod.rs | 29 + tools/sched_ext/atropos/src/util.rs | 24 + 11 files changed, 1376 insertions(+), 2 deletions(-) create mode 100644 tools/sched_ext/atropos/.gitignore create mode 100644 tools/sched_ext/atropos/Cargo.toml create mode 100644 tools/sched_ext/atropos/build.rs create mode 100644 tools/sched_ext/atropos/rustfmt.toml create mode 100644 tools/sched_ext/atropos/src/bpf/atropos.bpf.c create mode 100644 tools/sched_ext/atropos/src/bpf/atropos.h create mode 100644 tools/sched_ext/atropos/src/main.rs create mode 100644 tools/sched_ext/atropos/src/oss/atropos_sys.rs create mode 100644 tools/sched_ext/atropos/src/oss/mod.rs create mode 100644 tools/sched_ext/atropos/src/util.rs
tools/sched_ext/Makefile +11 -2
@@ -84,6 +84,8 @@ CFLAGS += -g -O2 -rdynamic -pthread -Wall -Werror $(GENFLAGS) \ -I$(INCLUDE_DIR) -I$(GENDIR) -I$(LIBDIR) \ -I$(TOOLSINCDIR) -I$(APIDIR) +CARGOFLAGS := --release + # Silence some warnings when compiled with clang ifneq ($(LLVM),) CFLAGS += -Wno-unused-command-line-argument
@@ -115,7 +117,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -O2 -mcpu=v3 all: scx_example_dummy scx_example_qmap scx_example_central scx_example_pair \ - scx_example_userland + scx_example_userland atropos # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -187,13 +189,20 @@ scx_example_userland: scx_example_userland.c scx_example_userland.skel.h \ $(CC) $(CFLAGS) -c $< -o [email protected] $(CC) -o $@ [email protected] $(HOST_BPFOBJ) $(LDFLAGS) +atropos: export RUSTFLAGS = -C link-args=-lzstd +atropos: export ATROPOS_CLANG = $(CLANG) +atropos: export ATROPOS_BPF_CFLAGS = $(BPF_CFLAGS) +atropos: $(INCLUDE_DIR)/vmlinux.h + cargo build --manifest-path=atropos/Cargo.toml $(CARGOFLAGS) + clean: + cargo clean --manifest-path=atropos/Cargo.toml rm -rf $(SCRATCH_DIR) $(HOST_SCRATCH_DIR) rm -f *.o *.bpf.o *.skel.h *.subskel.h rm -f scx_example_dummy scx_example_qmap scx_example_central \ scx_example_pair scx_example_userland -.PHONY: all clean +.PHONY: all atropos clean # delete failed targets .DELETE_ON_ERROR:
tools/sched_ext/atropos/.gitignore new file +3 -0
@@ -0,0 +1,3 @@ +src/bpf/.output +Cargo.lock +target
tools/sched_ext/atropos/Cargo.toml new file +34 -0
@@ -0,0 +1,34 @@ +# @generated by autocargo + +[package] +name = "atropos-bin" +version = "0.5.0" +authors = ["Dan Schatzberg <[email protected]>", "Meta"] +edition = "2021" +description = "Userspace scheduling with BPF" +readme = "../README.md" +repository = "https://github.com/facebookincubator/atropos" +license = "Apache-2.0" + +[dependencies] +anyhow = "1.0.65" +bitvec = { version = "1.0", features = ["serde"] } +clap = { version = "3.2.17", features = ["derive", "env", "regex", "unicode", "wrap_help"] } +ctrlc = { version = "3.1", features = ["termination"] } +fb_procfs = { git = "https://github.com/facebookincubator/below.git", rev = "f305730"} +hex = "0.4.3" +libbpf-rs = "0.19.1" +libc = "0.2.137" +slog = { version = "2.7", features = ["max_level_trace", "nested-values"] } +slog-async = { version = "2.3", features = ["nested-values"] } +slog-term = "2.8" + +[build-dependencies] +bindgen = { version = "0.61.0", features = ["logging", "static"], default-features = false } +libbpf-cargo = "0.13.0" + +[features] +enable_backtrace = [] + +[patch.crates-io] +libbpf-sys = { git = "https://github.com/dschatzberg/libbpf-sys", rev = "0ef4011"}
tools/sched_ext/atropos/build.rs new file +70 -0
70 lines not on this page · raw message
tools/sched_ext/atropos/rustfmt.toml new file +8 -0
@@ -0,0 +1,8 @@ +# Get help on options with `rustfmt --help=config` +# Please keep these in alphabetical order. +edition = "2021" +group_imports = "StdExternalCrate" +imports_granularity = "Item" +merge_derives = false +use_field_init_shorthand = true +version = "Two"
tools/sched_ext/atropos/src/bpf/atropos.bpf.c new file +501 -0
501 lines not on this page · raw message
tools/sched_ext/atropos/src/bpf/atropos.h new file +38 -0
@@ -0,0 +1,38 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. + +// This software may be used and distributed according to the terms of the +// GNU General Public License version 2. +#ifndef __ATROPOS_H +#define __ATROPOS_H + +#include <stdbool.h> + +#define MAX_CPUS 512 +#define MAX_DOMS 64/* limited to avoid complex bitmask ops */ +#define CACHELINE_SIZE 64 + +/* Statistics */ +enum stat_idx { +ATROPOS_STAT_TASK_GET_ERR , +ATROPOS_STAT_TASK_GET_ERR_ENABLE , +ATROPOS_STAT_CPUMASK_ERR , +ATROPOS_STAT_WAKE_SYNC , +ATROPOS_STAT_PREV_IDLE , +ATROPOS_STAT_PINNED , +ATROPOS_STAT_DIRECT_DISPATCH , +ATROPOS_STAT_DSQ_DISPATCH , +ATROPOS_STAT_GREEDY , +ATROPOS_STAT_LOAD_BALANCE , +ATROPOS_STAT_LAST_TASK , +ATROPOS_NR_STATS , +}; + +struct task_ctx { +unsigned long long dom_mask;/* the domains this task can run on */ +unsigned long long cpumask[MAX_CPUS /64 ]; +unsigned int dom_id; +unsigned int weight; +bool dispatch_local; +}; + +#endif /* __ATROPOS_H */
tools/sched_ext/atropos/src/main.rs new file +648 -0
648 lines not on this page · raw message
tools/sched_ext/atropos/src/oss/atropos_sys.rs new file +10 -0
@@ -0,0 +1,10 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. + +// This software may be used and distributed according to the terms of the +// GNU General Public License version 2. +#![allow(non_upper_case_globals)] +#![allow(non_camel_case_types)] +#![allow(non_snake_case)] +#![allow(dead_code)] + +include! (concat! (env! ("OUT_DIR" ),"/atropos-sys.rs" ));
tools/sched_ext/atropos/src/oss/mod.rs new file +29 -0
@@ -0,0 +1,29 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. + +// This software may be used and distributed according to the terms of the +// GNU General Public License version 2. +#[path = "../bpf/.output/atropos.skel.rs" ] +mod atropos; +use std::str::FromStr ; + +use anyhow::bail; +pub use atropos::*; +use slog::o; +use slog::Drain ; +use slog::Level ; + +pub mod atropos_sys; + +pub fn setup_logger (level: &str ) -> anyhow::Result <slog::Logger > { +let log_level =match Level ::from_str (level) { +Ok (l) => l, +Err (()) =>bail! ("Failed to parse \"{}\" as a log level" , level), + }; +let decorator = slog_term::TermDecorator ::new ().build (); +let drain = slog_term::FullFormat ::new (decorator).build ().fuse (); +let drain = slog_async::Async ::new (drain) + .build () + .filter_level (log_level) + .fuse (); +Ok (slog::Logger ::root (drain,o! ())) +}
tools/sched_ext/atropos/src/util.rs new file +24 -0
@@ -0,0 +1,24 @@ +// Copyright (c) Meta Platforms, Inc. and affiliates. + +// This software may be used and distributed according to the terms of the +// GNU General Public License version 2. + +// Shim between facebook types and open source types. +// +// The type interfaces and module hierarchy should be identical on +// both "branches". And since we glob import, all the submodules in +// this crate will inherit our name bindings and can use generic paths, +// eg `crate::logging::setup(..)`. +#[macro_export] +macro_rules! oss_shim { + () => { +#[cfg(fbcode_build)] +mod facebook; +#[cfg(fbcode_build)] +use facebook::*; +#[cfg(not(fbcode_build))] +mod oss; +#[cfg(not(fbcode_build))] +use oss::*; + }; +}
Signature · 1 line
2.38.1
Peter Zijlstra
maintainerRe: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Quoted 9 lines · Tejun Heo
From: Dan Schatzberg <[email protected]>
Atropos is a multi-domain BPF / userspace hybrid scheduler where the BPF part does simple round robin in each domain and the userspace part calculates the load factor of each domain and tells the BPF part how to load balance the domains.
This scheduler demonstrates dividing scheduling logic between BPF and userspace and using rust to build the userspace part.
And here I am, speaking neither Rust nor BPF.
But really, having seen some of this I long for the UMCG patches -- that at least was somewhat sane and trivially composes, unlike all this madness.
Re: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Quoted 3 lines · Peter Zijlstra
I long for the UMCG patches -- that
at least was somewhat sane and trivially composes, unlike all this madness.
A surprise, to be sure, but a welcome one!
We are in the process of finalizing UMCG internally, and I plan to post the patches here once all reviews/testing and some preliminary rollouts are done.
Thanks,
Peter
Peter Zijlstra
maintainerRe: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Quoted 7 lines · Peter Oskolkov
Quoted 3 lines · Peter Zijlstra
I long for the UMCG patches -- that
at least was somewhat sane and trivially composes, unlike all this madness.A surprise, to be sure, but a welcome one!
Well, I did somewhat like it as I put significant effort into it. In fact I was >.< near to merging the lot when you changed your mind and went the syscall route.
At that point something happened (I fell ill or a holiday or something) but it basically got snowed under as I had already been ignoring the inbox while doing the UMCG thing and I just never managed to get back to it (like a 1000 other things :/ -- this maintainer thing really is like drinking from a firehose).
Re: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Quoted 8 lines · Peter Zijlstra
Quoted 6 lines · Peter Oskolkov
Quoted 3 lines · Peter Zijlstra
I long for the UMCG patches -- that
at least was somewhat sane and trivially composes, unlike all this madness.
Quoted 5 lines
Quoted 1 line
A surprise, to be sure, but a welcome one!
Well, I did somewhat like it as I put significant effort into it. In fact I was >.< near to merging the lot when you changed your mind and went the syscall route.
Yes, we are doing it via syscalls now, as managing pinned pages in the TLS approach seemed ... excessive? Complicated? Not sure how to describe it.
But if you believe the TLS approach is sound, feel free to merge it, and we will make it work on our side. :)
(Tejun, my apologies for hijacking your thread a bit...)
[...]
Tejun Heo
maintainerRe: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
In reply to Peter ZijlstraHello,
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Tejun Heo
From: Dan Schatzberg <[email protected]>
Atropos is a multi-domain BPF / userspace hybrid scheduler where the BPF part does simple round robin in each domain and the userspace part calculates the load factor of each domain and tells the BPF part how to load balance the domains.
Quoted 4 lines
Quoted 2 lines
This scheduler demonstrates dividing scheduling logic between BPF and userspace and using rust to build the userspace part.
And here I am, speaking neither Rust nor BPF.
I'm not super fluent in rust but do really enjoy whenever I get to do things in it. What the language pulls off is actually really neat. It does take some getting-used-to tho.
Quoted 3 lines
But really, having seen some of this I long for the UMCG patches -- that at least was somewhat sane and trivially composes, unlike all this madness.
Putting aside lack of familiarity, there are several things which make the examples including this one not very readable. e.g. how the loops have to be structured in BPF and the inability to seamlessly access the elements of certain BPF map types do hamper ergonomics and readability quite a bit. That said, there are a lot of new developments in BPF which should improve many of these areas, so hopefully things should keep getting better.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
In reply to Peter ZijlstraHey Peter,
Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Tejun Heo
From: Dan Schatzberg <[email protected]>
Atropos is a multi-domain BPF / userspace hybrid scheduler where the BPF part does simple round robin in each domain and the userspace part calculates the load factor of each domain and tells the BPF part how to load balance the domains.
Quoted 8 lines
Quoted 2 lines
This scheduler demonstrates dividing scheduling logic between BPF and userspace and using rust to build the userspace part.
And here I am, speaking neither Rust nor BPF.
But really, having seen some of this I long for the UMCG patches -- that at least was somewhat sane and trivially composes, unlike all this madness.
I wasn't sure if you were focusing specifically on how the BPF portion is implemented, or on UMCG vs sched_ext. For the latter, and ignoring the specifics of this example, the UMCG and sched_ext work are complementary, but not mutually exclusive. UMCG is about driving cooperative scheduling within a particular application. UMCG does not have control over or react to external preemption, nor does it make thread placement decisions. sched_ext is considering things more at the system level: arbitrating fairness and preemption between processes, deciding when and where threads run, etc., and also being able to take application-specific hints if desired.
Peter Zijlstra
maintainerRe: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Quoted 6 lines · Josh Don
Quoted 3 lines
But really, having seen some of this I long for the UMCG patches -- that at least was somewhat sane and trivially composes, unlike all this madness.
I wasn't sure if you were focusing specifically on how the BPF portion is implemented, or on UMCG vs
sched_ext. For the latter,
The latter, from where I'm sitting UMCG looks a *TON* saner than this BPF scheduler proposal. In fact, I'm >< close to just saying NAK to the whole thing and ignoring it henceforth, there's too many problems with the whole approach.
( Many were already noted by Linus when he NAK'ed loadable schedulers
previously. )
Quoted 5 lines
and ignoring
the specifics of this example, the UMCG andsched_extwork are complementary, but not mutually exclusive. UMCG is about driving cooperative scheduling within a particular application. UMCG does not have control over or react to external preemption,
It can control preemption inside the process, and if you have the degree of control you need to make the whole BPF thing work, you also have the degree of control to ensure you only run the one server task on a CPU and all that no longer matters because there's only the process and you control preemption inside that.
Quoted 1 line
nor does it make thread placement decisions.
It can do that just fine -- inside the process. UMCG has full control over which server task a worker task is associated with, then run a single server task per CPU and have them pinned and you get full placement control.
Quoted 4 lines
sched_extis considering things more at
the system level: arbitrating fairness and preemption between processes, deciding when and where threads run, etc., and also being able to take application-specific hints if desired.
sched_ext does fundamentally not compose, you cannot run two different schedulers for two different application stacks that happen to co-reside on the same machine.
While with UMCG that comes naturally.
sched_ext also sits at the very bottom of the class stack (it more or less has to) the result is that in order to use it at all, you have to have control over all runnable tasks in the system (a stray CFS task would interfere quite disastrously) but that is exactly the same constraint you need to make UMCG work.
Conversely, it is very hard to use the BPF thing to do what UMCG can do. Using UMCG I can have a SCHED_DEADLINE server implement a task based pipeline schedule (something that's fairly common and really hard to pull off with just SCHED_DEADLINE itself).
Additionally, UMCG naturally works with things like Proxy Execution, seeing how the server task *is* a proxy for the current active worker task.
Tejun Heo
maintainerRe: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
Hello,
Quoted 2 lines · Peter Zijlstra
( Many were already noted by Linus when he NAK'ed loadable schedulers
previously. )
Yeah, many of the points Linus raised still stand. However, that was 15 years ago and the situation including hardware reality has changed a lot. As stated in the cover letter, that makes us (and others) want to try out various ideas but the barrier has often been too high to do so at any scale, which BPF drasically improves. Given those, I think it'd be worthwhile to revisit that discussion.
Quoted 6 lines
sched_extalso sits at the very bottom of the class stack (it more or less has to) the result is that in order to use it at all, you have to have control over all runnable tasks in the system (a stray CFS taskwould interfere quite disastrously) but that is exactly the same constraint you need to make UMCG work.
One important distinction is that it's a lot easier to have control at the system level than at the application code level. Even for us with pretty good control over what runs in the fleet, it'd be practically impossible to effect that level of application change across the board. The situation is further complicated with containers which can be pretty opaque to the system. I have a hard time seeing co-operative application-driven scheduling working among mutiple applications across the whole system. If we get to non-fleet use-cases, it becomes even worse as you don't have enough resource on or control over the code base you're running.
There may be some overlapping areas between SCX and UMCG but they're very different things. After all, we can't let go of system level scheduling because some applications have better control over their own sequencing.
As for the CFS starvation issue, I obviously don't find the currently proposed behavior too bad - CFS is always the default scheduler and we fall back to it whenever the BPF scheduling isn't working out whether that's outright bugs in the BPF scheduler implementation or starvation through CFS. That said, this comes down to what kind of behavior we wanna show to userspace and we can implement whatever is appropriate and acceptable.
Thanks.
--
tejun
Re: [PATCH 31/31] sched_ext: Add a rust userspace hybrid example scheduler
In reply to Peter ZijlstraQuoted 11 lines
Quoted 5 lines
and ignoring
the specifics of this example, the UMCG andsched_extwork are complementary, but not mutually exclusive. UMCG is about driving cooperative scheduling within a particular application. UMCG does not have control over or react to external preemption,It can control preemption inside the process, and if you have the degree of control you need to make the whole BPF thing work, you also have the degree of control to ensure you only run the one server task on a CPU and all that no longer matters because there's only the process and you control preemption inside that.
To an extent yes, but this doesn't extend to the case where cpu is overcommitted. Even if not by other applications, then responding to preemption by, for example, kthreads (necessary for microsecond scale workloads). But in general the common case is interference from other applications, something which is handled by a system level scheduler like sched_ext. The application vs system level control is an important distinction here.
Quoted 6 lines
Quoted 1 line
nor does it make thread placement decisions.
It can do that just fine -- inside the process. UMCG has full control over which server task a worker task is associated with, then run a single server task per CPU and have them pinned and you get full placement control.
Again, this doesn't really scale past single server per cpu. It is not feasible to partition systems in this way due to the loss of efficiency.
Quoted 8 lines
Quoted 4 lines
sched_extis considering things more at
the system level: arbitrating fairness and preemption between processes, deciding when and where threads run, etc., and also being able to take application-specific hints if desired.
sched_extdoes fundamentally not compose, you cannot run two different schedulers for two different application stacks that happen to co-reside on the same machine.
We're actually already developing a framework (and plan to share) to support composing an arbitrary combination of schedulers. Essentially, a "scheduler of schedulers". This supports the case, for example, of a system that runs most tasks under some default SCX scheduler, but allows a particular application or group of applications to utilize a bespoke SCX scheduler of their own.
Quoted 5 lines
sched_extalso sits at the very bottom of the class stack (it more or less has to) the result is that in order to use it at all, you have to have control over all runnable tasks in the system (a stray CFS task would interfere quite disastrously) but that is exactly the same constraint you need to make UMCG work.
UMCG still works when mixed with other tasks. You're specifying which threads of your application you want running, but no guarantees are made that they'll run right now if the system has other work to do.
SCX vs CFS is a more interesting story. Yes it is true that a single CFS task could hog a cpu, but since SCX is managing things at a system level, we feel that this is something that should be handled by system administration. You shouldn't expect to mix cpu bound CFS tasks in the same partition as threads running under SCX with good results.
Quoted 4 lines
Conversely, it is very hard to use the BPF thing to do what UMCG can do. Using UMCG I can have a
SCHED_DEADLINEserver implement a task based pipeline schedule (something that's fairly common and really hard to pull off with justSCHED_DEADLINEitself).
UMCG and SCX are solving different problems though. An application can decide execution order or control internal preemption via UMCG, while SXC arbitrates allocation of system resources over time.
And, conversely, SCX can do things very difficult or impossible with UMCG. For example, implementing core scheduling. Guaranteeing microsecond scale tail latency. Applying a new scheduling algorithm across multiple independent applications.
Quoted 3 lines
Additionally, UMCG naturally works with things like Proxy Execution, seeing how the server task *is* a proxy for the current active worker task.
Proxy execution should also work with SCX; the enqueue/dequeue abstraction can still be used to allow the SCX scheduler to select the proxy.
Peter Zijlstra
maintainerQuoted 2 lines · Tejun Heo
Core scheduling is an example of a feature that took a significant amount of time and effort to integrate into the kernel.
Mostly because I dropped it on the floor once I heard about MDS. That made me lose interest entirely. The only reason it eventually happened was ChromeOS (Joel) pushing for it again.
Quoted 3 lines
Part of the difficulty with core
scheduling was the inherent mismatch in abstraction between the desire to perform core-wide scheduling, and the per-cpu design of the kernel scheduler.
Not really; the main difficultly was due to me wanting to do it outside of the scheduling classes so that it fundamentally covers all of them.
Doing it inside a class (say CFS) would've made it significantly simpler.
Quoted 2 lines
This caused issues, for example ensuring proper fairness between the independent runqueues of SMT siblings.
Inter-runqueue fairness is a known issue of CFS and quite independent of core scheduling.
Anyway, I hate all of this. Linus NAK'ed loadable schedulers a number of times in the past and this is just that again -- with the extra downside of the whole BPF thing on top :/
You look to be exposing a ton of stuff I've so far even refused tracepoints for :-(
Anyway, I'm just back from a heavy dose of Covid and still taking it easy, but I'll go read through the whole thing, hopefully I'll finish before vanishing again for the x-mas break.
Tejun Heo
maintainerHello,
Quoted 3 lines · Peter Zijlstra
Anyway, I hate all of this. Linus NAK'ed loadable schedulers a number of times in the past and this is just that again -- with the extra downside of the whole BPF thing on top :/
Yeah, the whole BPF thing is what made this interesting for me and while there still are frustrating shortcomings, BPF does make iteration and deployment drastically safer and faster and we can try out ideas which didn't seem feasible before with relative ease. Given the history, I suppose some of the decision is upto Linus.
Quoted 2 lines
You look to be exposing a ton of stuff I've so far even refused tracepoints for :-(
I tried to keep the exposure limited and am sure it can be much improved. If you have specific ideas, I'm all ears.
Quoted 3 lines
Anyway, I'm just back from a heavy dose of Covid and still taking it easy, but I'll go read through the whole thing, hopefully I'll finish before vanishing again for the x-mas break.
Mine wasn't too bad but it still sucked mightily. I wish a quick and full recovery and thanks for taking a look.
Signature · 1 line
tejun
Peter Zijlstra
maintainerQuoted 9 lines · Tejun Heo
Rolling out kernel upgrades is a slow and iterative process. At a large scale it can take months to roll a new kernel out to a fleet of servers. While this latency is expected and inevitable for normal kernel upgrades, it can become highly problematic when kernel changes are required to fix bugs. Livepatch [9] is available to quickly roll out critical security fixes to large fleets, but the scope of changes that can be applied with livepatching is fairly limited, and would likely not be usable for patching scheduling policies. With
sched_ext, new scheduling policies can be rapidly rolled out to production environments.
I don't think we can or should use this argument to push BPF into ever more places.
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Tejun Heo
Rolling out kernel upgrades is a slow and iterative process. At a large scale it can take months to roll a new kernel out to a fleet of servers. While this latency is expected and inevitable for normal kernel upgrades, it can become highly problematic when kernel changes are required to fix bugs. Livepatch [9] is available to quickly roll out critical security fixes to large fleets, but the scope of changes that can be applied with livepatching is fairly limited, and would likely not be usable for patching scheduling policies. With
sched_ext, new scheduling policies can be rapidly rolled out to production environments.
Quoted 2 lines
I don't think we can or should use this argument to push BPF into ever more places.
Improving scheduling performance requires rapid iteration to explore new policies and tune parameters, especially as hardware becomes more heterogeneous, and applications become more complex. Waiting months between evaluating scheduler policy changes is simply not scalable, but this is the reality with large fleets that require time for testing, qualification, and progressive rollout. The security angle should be clear from how involved it was to integrate core scheduling, for example.
Peter Zijlstra
maintainerQuoted 8 lines · Josh Don
Improving scheduling performance requires rapid iteration to explore new policies and tune parameters, especially as hardware becomes more heterogeneous, and applications become more complex. Waiting months between evaluating scheduler policy changes is simply not scalable, but this is the reality with large fleets that require time for testing, qualification, and progressive rollout. The security angle should be clear from how involved it was to integrate core scheduling, for example.
Surely you can evaluate stuff on a small subset of machines -- I'm fairly sure I've had google and facebook people tell me they do just that, roll out the test kernel on tens to hundreds of thousand of machines instead of the stupid number and see how it behaves there.
Statistics has something here I think, you can get a reliable representation of stuff without having to sample *everyone*.
I was given to believe this was a fairly rapid process.
Just because you guys have more machines than is reasonable, doesn't mean we have to put BPF everywhere.
Additionally, we don't merge and ship everybodies random debug patch either -- you're free to do whatever you need to iterate on your own and then send the patches that result from this experiment upstream. This is how development works, no?
Tejun Heo
maintainerHello,
Quoted 10 lines · Peter Zijlstra
Quoted 8 lines · Josh Don
Improving scheduling performance requires rapid iteration to explore new policies and tune parameters, especially as hardware becomes more heterogeneous, and applications become more complex. Waiting months between evaluating scheduler policy changes is simply not scalable, but this is the reality with large fleets that require time for testing, qualification, and progressive rollout. The security angle should be clear from how involved it was to integrate core scheduling, for example.
Quoted 7 lines
Surely you can evaluate stuff on a small subset of machines -- I'm fairly sure I've had google and facebook people tell me they do just that, roll out the test kernel on tens to hundreds of thousand of machines instead of the stupid number and see how it behaves there.
Statistics has something here I think, you can get a reliable representation of stuff without having to sample *everyone*.
Google guys probably have a lot to say here too and there may be many commonalties, but here's how things are on our end.
We (Meta) experiment and debug at multiple levels. For example, when qualifying a new kernel or feature, a common pattern we follow is two-phased. The first phase is testing it on several well-known and widely used workloads in a controlled experiment environment with fewer number of machines, usually some dozens but can go one or two orders of magnitude higher. Once that looks okay, the second phase is to gradually deploy while monitoring system-level behaviors (crashes, utilization, latency and pressure metrics and so on) and feedbacks from service owners.
We run tens of thousands of different workloads in the fleet and we try hard to do as much as possible in the first phase but many of the difficult and subtle problems are only detectable in the second phase. When we detect such problems in the second phase, we triage the problem and pull back deployment if necessary and then restart after fixing.
As the overused saying goes, quantity has a quality of its own. The workloads become largely opaque because there are so many of them doing so many different things for anyone from system side to examine each of them. In many cases, the best and sometimes only visibility we get is statistical
- comparing two chunks of the fleet which are large enough for the statistical signals to overcome the noise. That threshold can be pretty high. Multiple hundreds of thousands of machines being used for a test set isn't all that uncommon.
One complicating factor for the second phase is that we're deploying on production fleet running live production workloads. Besides the obvious fact that users become mightily unhappy when machines crash, there are complicating matters like limits on how many and which machines can be rebooted at any given time due to interactions with capacity and maintenance which severely restricts how fast kernels can be iterated. A full sweep through the fleet can easily take months.
Between a large number of opaque workloads and production constraints which limit the type and speed of kernel iterations, our ability to experiment with scheduling by modifying the kernel directly is severely limited. We can do small things but trying out big ideas can become logistically prohibitive.
Note that all these get even worse for public cloud operators. If we really need to, we can at least find the service owner and talk with them. For public cloud operators, the workloads are truly opaque.
There's yet another aspect which is caused by fleet dynamism. When we're hunting down a scheduling misbehavior and want to test out specific ideas, it can actually be pretty difficult to get back the same workload composition after a reboot or crash. The fleet management layer will kick in right away and the workloads get reallocated who-knows-where. This problem is likely shared by smaller scale operations too. There are just a lot of layers which are difficult to fixate across reboots and crashes. Even in the same workload, the load balancer or dispatcher might behave very differently for the machine after a reboot.
Quoted 1 line
I was given to believe this was a fairly rapid process.
Going back to the first phase where we're experimenting in a more controlled environment. Yes, that is a faster process but only in comparison to the second phase. Some controlled experiments, the faster ones, usually take several hours to obtain a meaningful result. It just takes a while for production workloads to start, jit-compile all the hot code paths, warm up caches and so on. Others, unfortunately, take a lot longer to ramp up to the degree whether it can be compared against production numbers. Some of the benchmarks stretch multiple days.
With SCX, we can keep just keep hotswapping and tuning the scheduler behavior getting results in tens of minutes instead of multiple hours and without worrying about crashing the test machines, which often have side-effects on the benchmark setup - the benchmarks are often performed with shadowed production traffic using the same production software and they get unhappy when a lot of machines crash. These problems can easily take hours to resolve.
Quoted 2 lines
Just because you guys have more machines than is reasonable, doesn't mean we have to put BPF everywhere.
There are some problems which are specific to large operators like us or google for sure, but many of these problems are shared by other use cases which need to test with real-world applications. Even on mobile devices, it's way easier and faster to have a running test environment setup and iterate through scheduling behavior changes without worrying about crashing the machine than having to cycle and re-setup test setup for each iteration.
The productivity gain extends to individual kernel developers and researchers. Just rebooting a server class hardware often takes upwards of ten minutes, so most of us try to iterate as much on VMs as possible which unfortunately doesn't work out too well for subtle performance issues. SCX can easily cut down iteration time by an order of magnitude or more.
Quoted 4 lines
Additionally, we don't merge and ship everybodies random debug patch either -- you're free to do whatever you need to iterate on your own and then send the patches that result from this experiment upstream. This is how development works, no?
We of course don't merge random debug patches which have limited usefulness to a small number of use cases. However, we absolutely do ship code to support debugging and development when the benefit outweights the cost, just to list several examples - lockdep, perf, tracing, all the memory debug options.
The argument is that given the current situation including hardware and software landscape, the benefit of having BPF extensible scheduling framework has enough benefits to justify the cost.
Thanks.
Signature · 1 line
tejun
Quoted 2 lines · Tejun Heo
Google guys probably have a lot to say here too and there may be many commonalties, but here's how things are on our end.
your email pretty much captures my experiences from the google side. in fact, i think i'll save it for the next time someone asks me to summarize the challenges with both kernel rollouts and testing changes on workloads. =)
Quoted 11 lines
Quoted 1 line
I was given to believe this was a fairly rapid process.
Going back to the first phase where we're experimenting in a more controlled environment. Yes, that is a faster process but only in comparison to the second phase. Some controlled experiments, the faster ones, usually take several hours to obtain a meaningful result. It just takes a while for production workloads to start, jit-compile all the hot code paths, warm up caches and so on. Others, unfortunately, take a lot longer to ramp up to the degree whether it can be compared against production numbers. Some of the benchmarks stretch multiple days.
Quoted 3 lines
With SCX, we can keep just keep hotswapping and tuning the scheduler behavior getting results in tens of minutes instead of multiple hours and without worrying about crashing the test machines
for testing sched policies on one of our bigger apps, the O(hours) kernel reboot vs O(minutes) reload of a BPF scheduler is a pain. but that's only for a single machine; it can be much worse on a full cluster.
full-cluster tests are a different beast. we are one of many groups that want to do testing, and we have to reserve a time on their cluster.
but to change the kernel, it actually took us weeks to coordinate an
kernel change on the app's large testing cluster - essentially since we were using an unqualified kernel, we 'blocked' all of the other testing.
Quoted 3 lines
it's way easier and faster to have a running test environment setup and iterate through scheduling behavior changes without worrying about crashing the machine than having to cycle and re-setup test setup for each iteration.
i'm a newcomer to BPF, but for me the "interaction with live machine" is a major BPF feature, both in SCX and also more broadly with the various tracing tools and other BPF uses. (not to mention the per-workload or per-machine customization that BPF enables, but that's a separate discussion).
thanks,
barret