sched: Implement BPF extensible scheduler class
Subsystems (9)
Tejun Heo
maintainerPATCH v3 1/1 sched: Implement BPF extensible scheduler class
Changes
-------
This is v3 of sched_ext (SCX) patchset. The followings are changes from v2
(http://lkml.kernel.org/r/[email protected]).
- ops.set_weight() added to allow BPF schedulers to track weight changes without polling p->scx.weight.
- scx_bpf_task_cgroup() kfunc added to allow BPF scheduler to reliably determine the current cpu cgroup under rq lock protection. This required improving the kf_mask SCX operation verification mechanism and adding 0023-sched_ext-Track-tasks-that-are-subjects-of-the-in-fl.patch.
- Updated to use the latest BPF improvements including KF_RCU and the inline iterator.
- scx_example_flatcg added to 0024-sched_ext-Add-cgroup-support.patch. It uses the new BPF RB tree support to implement flattened cgroup hierarchy.
- A DSQ now also contains an rbtree so that it can be used to implement vtime based scheduling among tasks sharing a DSQ conveniently and efficiently. For more details, see 0029-sched_ext-Add-vtime-ordered-priority-queue-to-dispat.patch. All eligible example schedulers are updated to default to weighted vtime scheduilng.
- atropos scheduler's userspace code is substantially restructred and rewritten. The binary is renamed to scx_atropos and can auto-config the domains according to the cache topology.
- Various other example scheduler updates including scx_example_dummy being renamed to scx_example_simple, the example schedulers defaulting to enabling switch_all and clarifying performance expectation of each example scheduler.
- A bunch of fixes and improvements. Please refer to each patch for details.
v1 (http://lkml.kernel.org/r/[email protected]) -> v2:
- Rebased on top of bpf/for-next - a5f6b9d577eb ("Merge branch 'Enable struct_ops programs to be sleepable'"). There were several missing features including generic cpumask helpers and sleepable struct_ops operation support that v1 was working around. The rebase gets rid of all SCX specific temporary helpers.
- Some kfunc helpers are context-sensitive and can only be called from specific operations. v1 didn't restrict kfunc accesses allowing them to be misused which can lead to crashes and other malfunctions. v2 makes more kfuncs safe to be called from anywhere and implements per-task mask based runtime access control for the rest. The longer-term plan is to make the BPF verifier enforce these restrictions. Combined with the above, sans mistakes and bugs, it shouldn't be possible to crash the machine through SCX and its helpers.
- Core-sched support. While v1 implemented the pick_task operation, there were multiple missing pieces for working core-sched support. v2 adds 0027-sched_ext-Implement-core-sched-support.patch. SCX by default implements global FIFO ordering and allows the BPF schedulers to implement custom ordering via scx_ops.core_sched_before(). scx_example_qmap is updated so that the five queues' relative priorities are correctly reflected when core-sched is enabled.
- Dropped balance_scx_on_up() which was called from put_prev_task_balance(). UP support is now contained in SCX proper.
- 0002-sched-Encapsulate-task-attribute-change-sequence-int.patch adds SCHED_CHANGE_BLOCK() which encapsulates the preparation and restoration sequences used for task attribute changes. For SCX, this replaces sched_deq_and_put_task() and sched_enq_and_set_task() from v1.
- 0011-sched-Add-reason-to-sched_move_task.patch dropped from v1. SCX now distinguishes cgroup and autogroup tg's using task_group_is_autogroup().
- Other misc changes including fixes for bugs that Julia Lawall noticed and patch descriptions updates with more details on how the introduced changes are going to be used.
- MAINTAINERS entries added.
The followings are discussion points which were raised but didn't result in code changes in this iteration.
- There were discussions around exposing __setscheduler_prio() and, in v2, SCHED_CHANGE_BLOCK() in kernel/sched/sched.h. Switching scheduler implementations is innate for SCX. At the very least, it needs to be able to turn on and off the BPF scheduler which requires something equivalent to SCHED_CHANGE_BLOCK(). The use of __setscheduler_prio() depends on the behavior we want to present to userspace. The current one of using CFS as the fallback when BPF scheduler is not available seems more friendly and less error-prone to other options.
- Another discussion point was around for_each_active_class() and friends which skip over CFS or SCX when it's known that the sched_class must be empty. I left it as-is for now as it seems to be cleaner and more robust than trying to plug each operation which may added unnecessary overheads.
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 weighted vtime scheduling 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 weighted vtime or 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_flatcg scheduler, which is in 0024-sched_ext-Add-cgroup-support.patch and provides 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.
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_flatcg 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 [8] 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.
[8]: https://www.kernel.org/doc/html/latest/livepatch/livepatch.html
As an example, one of the variants of the L1 Terminal Fault (L1TF) [9] 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”.
[9]: 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 2023-03-16:
b8a2e3f93d41 ("cgroup: Make current_cgns_cgroup_dfl() safe to call after exit_task_namespace()")
and contains the following patches:
NOTE: The doc added by 0030 contains a high-level overview and might be good
place to start.
0001-cgroup-Implement-cgroup_show_cftypes.patch 0002-sched-Encapsulate-task-attribute-change-sequence-int.patch 0003-sched-Restructure-sched_class-order-sanity-checks-in.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-__setscheduler_prio-and-SCHED_CH.patch 0009-sched-Enumerate-CPU-cgroup-file-types.patch 0010-sched-Add-reason-to-sched_class-rq_-on-off-line.patch 0011-sched-Add-normal_policy.patch 0012-sched_ext-Add-boilerplate-for-extensible-scheduler-c.patch 0013-sched_ext-Implement-BPF-extensible-scheduler-class.patch 0014-sched_ext-Add-scx_example_simple-and-scx_example_qma.patch 0015-sched_ext-Add-sysrq-S-which-disables-the-BPF-schedul.patch 0016-sched_ext-Implement-runnable-task-stall-watchdog.patch 0017-sched_ext-Allow-BPF-schedulers-to-disallow-specific-.patch 0018-sched_ext-Allow-BPF-schedulers-to-switch-all-eligibl.patch 0019-sched_ext-Implement-scx_bpf_kick_cpu-and-task-preemp.patch 0020-sched_ext-Make-watchdog-handle-ops.dispatch-looping-.patch 0021-sched_ext-Add-task-state-tracking-operations.patch 0022-sched_ext-Implement-tickless-support.patch 0023-sched_ext-Track-tasks-that-are-subjects-of-the-in-fl.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-Implement-core-sched-support.patch 0029-sched_ext-Add-vtime-ordered-priority-queue-to-dispat.patch 0030-sched_ext-Documentation-scheduler-Document-extensibl.patch 0031-sched_ext-Add-a-basic-userland-vruntime-scheduler.patch 0032-sched_ext-Add-a-rust-userspace-hybrid-example-schedu.patch
0001 : Cgroup prep.
0002-0011: Scheduler prep.
0012-0014: sched_ext core implementation and a couple example BPF scheduler.
0015-0018: Utility features including safety mechanisms and switch-all.
0019-0022: 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.
0023-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 core-sched support.
0029 : Add DSQ rbtree support.
0030 : Add documentation.
0031-0032: 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.
The patchset is also available in the following git branch:
https://github.com/htejun/sched_ext sched_ext-v3
diffstat follows.
Documentation/scheduler/index.rst | 1 Documentation/scheduler/sched-ext.rst | 230 + MAINTAINERS | 3 drivers/tty/sysrq.c | 1 include/asm-generic/vmlinux.lds.h | 1 include/linux/cgroup-defs.h | 8 include/linux/cgroup.h | 5 include/linux/sched.h | 5 include/linux/sched/ext.h | 709 ++++ include/linux/sched/task.h | 3 include/uapi/linux/sched.h | 1 init/Kconfig | 5 init/init_task.c | 12 kernel/Kconfig.preempt | 24 kernel/bpf/bpf_struct_ops_types.h | 4 kernel/cgroup/cgroup.c | 97 kernel/fork.c | 17 kernel/sched/build_policy.c | 5 kernel/sched/core.c | 496 +- kernel/sched/deadline.c | 4 kernel/sched/debug.c | 6 kernel/sched/ext.c | 4326 ++++++++++++++++++++++++++ kernel/sched/ext.h | 245 + kernel/sched/fair.c | 9 kernel/sched/idle.c | 2 kernel/sched/rt.c | 4 kernel/sched/sched.h | 158 kernel/sched/topology.c | 4 tools/sched_ext/.gitignore | 9 tools/sched_ext/Makefile | 216 + tools/sched_ext/atropos/.gitignore | 3 tools/sched_ext/atropos/Cargo.toml | 28 tools/sched_ext/atropos/build.rs | 70 tools/sched_ext/atropos/rustfmt.toml | 8 tools/sched_ext/atropos/src/atropos_sys.rs | 10 tools/sched_ext/atropos/src/bpf/atropos.bpf.c | 751 ++++ tools/sched_ext/atropos/src/bpf/atropos.h | 44 tools/sched_ext/atropos/src/main.rs | 942 +++++ tools/sched_ext/gnu/stubs.h | 1 tools/sched_ext/scx_common.bpf.h | 289 + tools/sched_ext/scx_example_central.bpf.c | 334 ++ tools/sched_ext/scx_example_central.c | 94 tools/sched_ext/scx_example_flatcg.bpf.c | 872 +++++ tools/sched_ext/scx_example_flatcg.c | 232 + tools/sched_ext/scx_example_flatcg.h | 49 tools/sched_ext/scx_example_pair.bpf.c | 627 +++ tools/sched_ext/scx_example_pair.c | 143 tools/sched_ext/scx_example_pair.h | 10 tools/sched_ext/scx_example_qmap.bpf.c | 401 ++ tools/sched_ext/scx_example_qmap.c | 107 tools/sched_ext/scx_example_simple.bpf.c | 128 tools/sched_ext/scx_example_simple.c | 101 tools/sched_ext/scx_example_userland.bpf.c | 269 + tools/sched_ext/scx_example_userland.c | 402 ++ tools/sched_ext/scx_example_userland_common.h | 19 tools/sched_ext/user_exit_info.h | 50 56 files changed, 12362 insertions(+), 232 deletions(-)
Thanks.
--
tejun
Tejun Heo
maintainerPATCH 1/32 cgroup: Implement cgroup_show_cftypes()
Implement 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
@@ -115,6 +115,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.39.2
Tejun Heo
maintainerPATCH 2/32 sched: Encapsulate task attribute change sequence into a helper macro
In reply to Tejun HeoA task needs to be dequeued and put before an attribute change and then restored afterwards. This is currently open-coded in multiple places. This patch encapsulates the preparation and restoration sequences into SCHED_CHANGE_BLOCK which allows the actual attribute changes to be put inside its nested block. While the conversions are generally straightforward, there are some subtleties:
* If a variable is specified for the flags argument, it can be modified from inside the block body to allow using a different flags value for re-enqueueing. This is used by rt_mutex_setprio() and __sched_setscheduler().
* __sched_setscheduler() used to only set ENQUEUE_HEAD if the task is queued. After the conversion, it sets the flag whether the task is queued or not. This doesn't cause any behavioral differences and is simpler than accessing the internal state of the helper.
* In a similar vein, sched_move_task() tests task_current() again after the change block instead of carrying over the test result from inside the change block.
This patch is adopted from Peter Zijlstra's draft patch linked below. The changes are:
* Call fini explicitly from for() instead of using the __cleanup__ attribute.
* Allow the queue flag variable to be modified directly so that the user doesn't have to poke into sched_change_guard struct. Also, in the original patch, rt_mutex_setprio() was incorrectly updating its queue_flag instead of cg.flags.
* Some cosmetic changes.
--- kernel/sched/core.c | 260 ++++++++++++++++++++++---------------------- 1 file changed, 130 insertions(+), 130 deletions(-)
kernel/sched/core.c +130 -130
@@ -2096,6 +2096,76 @@ void deactivate_task(struct rq *rq, struct task_struct *p, int flags)dequeue_task (rq, p, flags); } +struct sched_change_guard { +struct task_struct *p; +struct rq *rq; +bool queued; +bool running; +bool done; +}; + +static struct sched_change_guard +sched_change_guard_init (struct rq *rq,struct task_struct *p,int flags) +{ +struct sched_change_guard cg = { + .rq = rq, + .p = p, + .queued =task_on_rq_queued (p), + .running =task_current (rq, p), + }; + +if (cg.queued) { +/* +* __kthread_bind() may call this on blocked tasks without +* holding rq->lock through __do_set_cpus_allowed(). Assert @rq +* locked iff @p is queued. +*/ +lockdep_assert_rq_held (rq); +dequeue_task (rq, p, flags); + } +if (cg.running) +put_prev_task (rq, p); + +return cg; +} + +static void sched_change_guard_fini (struct sched_change_guard *cg,int flags) +{ +if (cg->queued) +enqueue_task (cg->rq, cg->p, flags |ENQUEUE_NOCLOCK ); +if (cg->running) +set_next_task (cg->rq, cg->p); + cg->done = true; +} + +/** +* SCHED_CHANGE_BLOCK - Nested block for task attribute updates +* @__rq: Runqueue the target task belongs to +* @__p: Target task +* @__flags: DEQUEUE/ENQUEUE_* flags +* +* A task may need to be dequeued and put_prev_task'd for attribute updates and +* set_next_task'd and re-enqueued afterwards. This helper defines a nested +* block which automatically handles these preparation and cleanup operations. +* +* SCHED_CHANGE_BLOCK(rq, p, DEQUEUE_SAVE | DEQUEUE_NOCLOCK) { +* update_attribute(p); +* ... +* } +* +* If @__flags is a variable, the variable may be updated in the block body and +* the updated value will be used when re-enqueueing @p. +* +* If %DEQUEUE_NOCLOCK is specified, the caller is responsible for calling +* update_rq_clock() beforehand. Otherwise, the rq clock is automatically +* updated iff the task needs to be dequeued and re-enqueued. Only the former +* case guarantees that the rq clock is up-to-date inside and after the block. +*/ +#define SCHED_CHANGE_BLOCK (__rq, __p, __flags) \ + for (struct sched_change_guard __cg = \ + sched_change_guard_init(__rq, __p, __flags); \ + !__cg.done; sched_change_guard_fini(&__cg, __flags)) +static inline int __normal_prio (int policy,int rt_prio,int nice) {int prio;
@@ -2554,7 +2624,6 @@ static void __do_set_cpus_allowed(struct task_struct *p, struct affinity_context *ctx) { struct rq *rq = task_rq(p); -bool queued, running;/* * This here violates the locking rules for affinity, since we're only
@@ -2573,26 +2642,9 @@ __do_set_cpus_allowed(struct task_struct *p, struct affinity_context *ctx)else lockdep_assert_held (&p->pi_lock); - queued =task_on_rq_queued (p); - running =task_current (rq, p); - -if (queued) { -/* -* Because __kthread_bind() calls this on blocked tasks without -* holding rq->lock. -*/ -lockdep_assert_rq_held (rq); -dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK ); + SCHED_CHANGE_BLOCK(rq, p, DEQUEUE_SAVE | DEQUEUE_NOCLOCK) { + p->sched_class->set_cpus_allowed (p, ctx); } -if (running) -put_prev_task (rq, p); - - p->sched_class->set_cpus_allowed (p, ctx); - -if (queued) -enqueue_task (rq, p,ENQUEUE_RESTORE |ENQUEUE_NOCLOCK ); -if (running) -set_next_task (rq, p); }/*
@@ -6989,7 +7041,7 @@ static inline int rt_effective_prio(struct task_struct *p, int prio)*/ void rt_mutex_setprio (struct task_struct *p,struct task_struct *pi_task) { -int prio, oldprio, queued, running, queue_flag = +int prio, oldprio, queue_flag =DEQUEUE_SAVE |DEQUEUE_MOVE |DEQUEUE_NOCLOCK ;const struct sched_class *prev_class;struct rq_flags rf;
@@ -7049,49 +7101,39 @@ void rt_mutex_setprio(struct task_struct *p, struct task_struct *pi_task) queue_flag &= ~DEQUEUE_MOVE ; prev_class = p->sched_class; - queued =task_on_rq_queued (p); - running =task_current (rq, p); -if (queued) -dequeue_task (rq, p, queue_flag); -if (running) -put_prev_task (rq, p); - -/* -* Boosting condition are: -* 1. -rt task is running and holds mutex A -* --> -dl task blocks on mutex A -* -* 2. -dl task is running and holds mutex A -* --> -dl task blocks on mutex A and could preempt the -* running task -*/ -if (dl_prio (prio)) { -if (!dl_prio (p->normal_prio) || - (pi_task &&dl_prio (pi_task->prio) && -dl_entity_preempt (&pi_task->dl, &p->dl))) { - p->dl.pi_se = pi_task->dl.pi_se; - queue_flag |=ENQUEUE_REPLENISH ; + SCHED_CHANGE_BLOCK(rq, p, queue_flag) { +/* +* Boosting condition are: +* 1. -rt task is running and holds mutex A +* --> -dl task blocks on mutex A +* +* 2. -dl task is running and holds mutex A +* --> -dl task blocks on mutex A and could preempt the +* running task +*/ +if (dl_prio (prio)) { +if (!dl_prio (p->normal_prio) || + (pi_task &&dl_prio (pi_task->prio) && +dl_entity_preempt (&pi_task->dl, &p->dl))) { + p->dl.pi_se = pi_task->dl.pi_se; + queue_flag |=ENQUEUE_REPLENISH ; + }else { + p->dl.pi_se = &p->dl; + } + }else if (rt_prio (prio)) { +if (dl_prio (oldprio)) + p->dl.pi_se = &p->dl; +if (oldprio < prio) + queue_flag |=ENQUEUE_HEAD ; }else { - p->dl.pi_se = &p->dl; +if (dl_prio (oldprio)) + p->dl.pi_se = &p->dl; +if (rt_prio (oldprio)) + p->rt.timeout =0 ; } - }else if (rt_prio (prio)) { -if (dl_prio (oldprio)) - p->dl.pi_se = &p->dl; -if (oldprio < prio) - queue_flag |=ENQUEUE_HEAD ; - }else { -if (dl_prio (oldprio)) - p->dl.pi_se = &p->dl; -if (rt_prio (oldprio)) - p->rt.timeout =0 ; - } - -__setscheduler_prio (p, prio); -if (queued) -enqueue_task (rq, p, queue_flag); -if (running) -set_next_task (rq, p); +__setscheduler_prio (p, prio); + }check_class_changed (rq, p, prev_class, oldprio); out_unlock:
@@ -7113,7 +7155,6 @@ static inline int rt_effective_prio(struct task_struct *p, int prio)void set_user_nice (struct task_struct *p,long nice) { -bool queued, running;int old_prio;struct rq_flags rf;struct rq *rq;
@@ -7137,22 +7178,13 @@ void set_user_nice(struct task_struct *p, long nice) p->static_prio =NICE_TO_PRIO (nice); goto out_unlock; } - queued =task_on_rq_queued (p); - running =task_current (rq, p); -if (queued) -dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK ); -if (running) -put_prev_task (rq, p); - - p->static_prio =NICE_TO_PRIO (nice); -set_load_weight (p, true); - old_prio = p->prio; - p->prio =effective_prio (p); -if (queued) -enqueue_task (rq, p,ENQUEUE_RESTORE |ENQUEUE_NOCLOCK ); -if (running) -set_next_task (rq, p); + SCHED_CHANGE_BLOCK(rq, p, DEQUEUE_SAVE | DEQUEUE_NOCLOCK) { + p->static_prio =NICE_TO_PRIO (nice); +set_load_weight (p, true); + old_prio = p->prio; + p->prio =effective_prio (p); + }/* * If the task increased its priority or is running and
@@ -7536,7 +7568,7 @@ static int __sched_setscheduler(struct task_struct *p, bool user, bool pi) { int oldpolicy = -1, policy = attr->sched_policy; -int retval, oldprio, newprio, queued, running; +int retval, oldprio, newprio;const struct sched_class *prev_class;struct balance_callback *head;struct rq_flags rf;
@@ -7701,33 +7733,22 @@ static int __sched_setscheduler(struct task_struct *p, queue_flags &= ~DEQUEUE_MOVE ; } - queued =task_on_rq_queued (p); - running =task_current (rq, p); -if (queued) -dequeue_task (rq, p, queue_flags); -if (running) -put_prev_task (rq, p); - - prev_class = p->sched_class; + SCHED_CHANGE_BLOCK(rq, p, queue_flags) { + prev_class = p->sched_class; -if (!(attr->sched_flags &SCHED_FLAG_KEEP_PARAMS )) { -__setscheduler_params (p, attr); -__setscheduler_prio (p, newprio); - } -__setscheduler_uclamp (p, attr); +if (!(attr->sched_flags &SCHED_FLAG_KEEP_PARAMS )) { +__setscheduler_params (p, attr); +__setscheduler_prio (p, newprio); + } +__setscheduler_uclamp (p, attr); -if (queued) {/* * We enqueue to tail when the priority of a task is * increased (user space view). */ if (oldprio < p->prio) queue_flags |=ENQUEUE_HEAD ; - -enqueue_task (rq, p, queue_flags); } -if (running) -set_next_task (rq, p);check_class_changed (rq, p, prev_class, oldprio);
@@ -9250,25 +9271,15 @@ int migrate_task_to(struct task_struct *p, int target_cpu)*/ void sched_setnuma (struct task_struct *p,int nid) { -bool queued, running;struct rq_flags rf;struct rq *rq; rq =task_rq_lock (p, &rf); - queued =task_on_rq_queued (p); - running =task_current (rq, p); -if (queued) -dequeue_task (rq, p,DEQUEUE_SAVE ); -if (running) -put_prev_task (rq, p); - - p->numa_preferred_nid = nid; + SCHED_CHANGE_BLOCK(rq, p, DEQUEUE_SAVE) { + p->numa_preferred_nid = nid; + } -if (queued) -enqueue_task (rq, p,ENQUEUE_RESTORE |ENQUEUE_NOCLOCK ); -if (running) -set_next_task (rq, p);task_rq_unlock (rq, p, &rf); }#endif /* CONFIG_NUMA_BALANCING */
@@ -10360,35 +10371,24 @@ static void sched_change_group(struct task_struct *tsk)*/ void sched_move_task (struct task_struct *tsk) { -int queued, running, queue_flags = -DEQUEUE_SAVE |DEQUEUE_MOVE |DEQUEUE_NOCLOCK ;struct rq_flags rf;struct rq *rq; rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); - queued =task_on_rq_queued (tsk); - -if (queued) -dequeue_task (rq, tsk, queue_flags); -if (running) -put_prev_task (rq, tsk); - -sched_change_group (tsk); +SCHED_CHANGE_BLOCK (rq, tsk, + DEQUEUE_SAVE | DEQUEUE_MOVE | DEQUEUE_NOCLOCK) { +sched_change_group (tsk); + } -if (queued) -enqueue_task (rq, tsk, queue_flags); -if (running) { -set_next_task (rq, tsk); -/* -* After changing group, the running task may have joined a -* throttled one but it's still the running task. Trigger a -* resched to make sure that task can still run. -*/ +/* +* After changing group, the running task may have joined a throttled +* one but it's still the running task. Trigger a resched to make sure +* that task can still run. +*/ +if (task_current (rq, tsk))resched_curr (rq); - }task_rq_unlock (rq, tsk, &rf); }
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 3/32 sched: Restructure sched_class order sanity checks in sched_init()
In reply to Tejun HeoCurrently, sched_init() checks that the sched_class'es are in the expected order by testing each adjacency which is a bit brittle and makes it cumbersome to add optional sched_class'es. Instead, let's verify whether they're in the expected order using sched_class_above() which is what matters.
--- kernel/sched/core.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/sched/core.c +4 -4
@@ -9794,12 +9794,12 @@ 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 || - &rt_sched_class != &dl_sched_class +1 );#ifdef CONFIG_SMP -BUG_ON (&dl_sched_class != &stop_sched_class +1 ); +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));wait_bit_init ();
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 4/32 sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork()
In reply to Tejun HeoA new BPF extensible sched_class will need more control over the forking process. It wants to be able to fail from sched_cgroup_fork() after the new task's sched_task_group is initialized so that the loaded BPF program can prepare the task with its cgroup association is established and reject fork if e.g. allocation fails.
Allow sched_cgroup_fork() to fail by making it return int instead of void and adding sched_cancel_fork() to undo sched_fork() in the error path.
sched_cgroup_fork() doesn't fail yet and this patch shouldn't cause any behavior changes.
v2: Patch description updated to detail the expected use.
--- 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
@@ -2242,7 +2242,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;
@@ -2383,7 +2383,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
@@ -2429,13 +2431,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; }/* No more failure paths after this point. */
@@ -2510,10 +2512,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 ) {
@@ -2552,6 +2555,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
@@ -4768,7 +4768,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;
@@ -4795,6 +4795,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.39.2
Tejun Heo
maintainerPATCH 5/32 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 a new BPF extensible sched_class so that it can keep its cached task weight up-to-date.
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
@@ -1277,8 +1277,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
@@ -3342,7 +3342,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);
@@ -12547,6 +12547,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
@@ -2213,6 +2213,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);
@@ -2365,8 +2367,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.39.2
Tejun Heo
maintainerPATCH 6/32 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.
A new BPF extensible sched_class will have callbacks that allow the BPF scheduler to keep track of relevant task states (like priority and cpumask). Those callbacks aren't called while a task is on a different sched_class. When a task comes back, we wanna tell the BPF progs the up-to-date state before the task gets enqueued, so we need a hook which is called before the switching is committed.
This patch adds ->switching_to() which is called during sched_class switch through check_class_changing() before the task is restored. Also, this patch exposes check_class_changing/changed() in kernel/sched/sched.h. They will be used by the new BPF extensible sched_class to implement implicit sched_class switching which is used e.g. when falling back to CFS when the BPF scheduler fails or unloads.
This is a prep patch and doesn't cause any behavior changes. The new operation and exposed functions aren't used yet.
v2: Improve patch description w/ details on planned use.
--- kernel/sched/core.c | 20 +++++++++++++++++--- kernel/sched/sched.h | 7 +++++++ 2 files changed, 24 insertions(+), 3 deletions(-)
kernel/sched/core.c +17 -3
@@ -2223,6 +2223,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.
@@ -2230,9 +2241,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)
@@ -7139,6 +7150,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); }check_class_changed (rq, p, prev_class, oldprio);
@@ -7748,6 +7760,8 @@ static int __sched_setscheduler(struct task_struct *p, }__setscheduler_uclamp (p, attr); +check_class_changing (rq, p, prev_class); +/* * We enqueue to tail when the priority of a task is * increased (user space view).
kernel/sched/sched.h +7 -0
@@ -2211,6 +2211,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,
@@ -2447,6 +2448,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.39.2
Tejun Heo
maintainerPATCH 7/32 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 BPF extensible sched_class so that the weights can be exposed to the BPF programs in a way which is consistent cgroup weights and easier to interpret.
The weight conversions will be used regardless of cgroup usage. It's just borrowing the cgroup weight range as it's more intuitive. CGROUP_WEIGHT_MIN/DFL/MAX constants are moved outside CONFIG_CGROUPS so that the conversion helpers can always be defined.
v2: The helpers are now defined regardless of COFNIG_CGROUPS.
--- include/linux/cgroup.h | 4 ++-- kernel/sched/core.c | 28 +++++++++++++--------------- kernel/sched/sched.h | 18 ++++++++++++++++++ 3 files changed, 33 insertions(+), 17 deletions(-)
include/linux/cgroup.h +2 -2
@@ -29,8 +29,6 @@struct kernel_clone_args ; -#ifdef CONFIG_CGROUPS -/* * All weight knobs on the default hierarchy should use the following min, * default and max values. The default value is the logarithmic center of
@@ -40,6 +38,8 @@ struct kernel_clone_args;#define CGROUP_WEIGHT_DFL 100#define CGROUP_WEIGHT_MAX 10000 +#ifdef CONFIG_CGROUPS +/* walk only threadgroup leaders */ #define CSS_TASK_ITER_PROCS (1U << 0)/* walk all threaded css_sets in the domain */
kernel/sched/core.c +13 -15
@@ -11145,29 +11145,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)); }
@@ -11175,7 +11173,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
@@ -232,6 +232,24 @@ static inline void update_avg(u64 *avg, u64 sample)#define shr_bound (val, shift) \ (val >> min_t(typeof(shift), shift, BITS_PER_TYPE(typeof(val)) - 1)) +/* +* 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 ); +} +/* * !! For sched_setattr_nocheck() (kernel) only !! *
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 8/32 sched: Expose css_tg(), __setscheduler_prio() and SCHED_CHANGE_BLOCK()
In reply to Tejun HeoThese will be used by a new BPF extensible sched_class.
css_tg() will be used in the init and exit paths to visit all task_groups by walking cgroups.
__setscheduler_prio() is used to pick the sched_class matching the current prio of the task. For the new BPF extensible sched_class, the mapping from the task configuration to sched_class isn't static and depends on a few factors - e.g. whether the BPF progs implementing the scheduler are loaded and in a serviceable state. That mapping logic will be added to __setscheduler_prio().
When the BPF scheduler progs get loaded and unloaded, the mapping changes and the new sched_class will walk the tasks applying the new mapping using SCHED_CHANGE_BLOCK() and __setscheduler_prio().
v2: Expose SCHED_CHANGE_BLOCK() too and update the description.
--- kernel/sched/core.c | 47 +++---------------------------------------- kernel/sched/sched.h | 48 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 51 insertions(+), 44 deletions(-)
kernel/sched/core.c +3 -44
@@ -2096,15 +2096,7 @@ void deactivate_task(struct rq *rq, struct task_struct *p, int flags)dequeue_task (rq, p, flags); } -struct sched_change_guard { -struct task_struct *p; -struct rq *rq; -bool queued; -bool running; -bool done; -}; - -static struct sched_change_guard +struct sched_change_guard sched_change_guard_init (struct rq *rq,struct task_struct *p,int flags) {struct sched_change_guard cg = {
@@ -2129,7 +2121,7 @@ sched_change_guard_init(struct rq *rq, struct task_struct *p, int flags)return cg; } -static void sched_change_guard_fini (struct sched_change_guard *cg,int flags) +void sched_change_guard_fini (struct sched_change_guard *cg,int flags) {if (cg->queued)enqueue_task (cg->rq, cg->p, flags |ENQUEUE_NOCLOCK );
@@ -2138,34 +2130,6 @@ static void sched_change_guard_fini(struct sched_change_guard *cg, int flags) cg->done = true; } -/** -* SCHED_CHANGE_BLOCK - Nested block for task attribute updates -* @__rq: Runqueue the target task belongs to -* @__p: Target task -* @__flags: DEQUEUE/ENQUEUE_* flags -* -* A task may need to be dequeued and put_prev_task'd for attribute updates and -* set_next_task'd and re-enqueued afterwards. This helper defines a nested -* block which automatically handles these preparation and cleanup operations. -* -* SCHED_CHANGE_BLOCK(rq, p, DEQUEUE_SAVE | DEQUEUE_NOCLOCK) { -* update_attribute(p); -* ... -* } -* -* If @__flags is a variable, the variable may be updated in the block body and -* the updated value will be used when re-enqueueing @p. -* -* If %DEQUEUE_NOCLOCK is specified, the caller is responsible for calling -* update_rq_clock() beforehand. Otherwise, the rq clock is automatically -* updated iff the task needs to be dequeued and re-enqueued. Only the former -* case guarantees that the rq clock is up-to-date inside and after the block. -*/ -#define SCHED_CHANGE_BLOCK (__rq, __p, __flags) \ - for (struct sched_change_guard __cg = \ - sched_change_guard_init(__rq, __p, __flags); \ - !__cg.done; sched_change_guard_fini(&__cg, __flags)) -static inline int __normal_prio (int policy,int rt_prio,int nice) {int prio;
@@ -7016,7 +6980,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;
@@ -10413,11 +10377,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 +48 -0
66 lines not on this page · raw message
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 9/32 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 BPF extensible sched_class to selectively show and hide CPU controller interface files depending on the capability of the currently loaded BPF scheduler progs.
--- kernel/sched/core.c | 22 +++++++++++----------- kernel/sched/sched.h | 21 +++++++++++++++++++++ 2 files changed, 32 insertions(+), 11 deletions(-)
kernel/sched/core.c +11 -11
@@ -11014,7 +11014,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",
@@ -11221,21 +11221,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,
@@ -11243,13 +11243,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,
@@ -11257,13 +11257,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,
@@ -11283,8 +11283,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
@@ -3379,4 +3379,25 @@ static inline void switch_mm_cid(struct task_struct *prev, struct task_struct *nstatic inline void switch_mm_cid (struct task_struct *prev,struct task_struct *next) { }#endif +#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.39.2
Tejun Heo
maintainerPATCH 10/32 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. A planned BPF extensible sched_class wants to tell the BPF scheduler progs about CPU hotplug events in a way that's synchronized with rq state changes.
As the BPF scheduler progs aren't necessarily affected by cpuset partition updates, we need a way to distinguish the two types of events. Let's add an argument to tell them apart.
v2: Patch description updated to detail the expected use.
--- 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
@@ -9428,7 +9428,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;
@@ -9438,19 +9438,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);
@@ -9546,7 +9546,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);
@@ -9591,7 +9591,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
@@ -2518,7 +2518,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);
@@ -2529,7 +2529,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
@@ -11805,14 +11805,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
@@ -2473,7 +2473,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);
@@ -2484,7 +2484,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
@@ -2183,6 +2183,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 affinity_context {const struct cpumask *new_mask;struct cpumask *user_mask;
@@ -2219,8 +2224,8 @@ struct sched_class {void (*set_cpus_allowed)(struct task_struct *p,struct affinity_context *ctx); -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
@@ -2787,8 +2792,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
@@ -495,7 +495,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);
@@ -513,7 +513,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.39.2
Tejun Heo
maintainerPATCH 11/32 sched: Add normal_policy()
In reply to Tejun HeoA new BPF extensible sched_class will need to dynamically change how a task picks its sched_class. For example, if the loaded BPF scheduler progs fail, the tasks will be forced back on CFS even if the task's policy is set to the new sched_class. To support such mapping, add normal_policy() which wraps testing for %SCHED_NORMAL. This doesn't cause any behavior changes.
v2: Update the description with more details on the expected use.
--- kernel/sched/fair.c | 2 +- kernel/sched/sched.h | 8 +++++++- 2 files changed, 8 insertions(+), 2 deletions(-)
kernel/sched/fair.c +1 -1
@@ -7806,7 +7806,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.39.2
Tejun Heo
maintainerPATCH 12/32 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.
v2: balance_scx_on_up() dropped. This will be handled in sched_ext proper.
--- include/linux/sched/ext.h | 12 ++++++++++++ kernel/fork.c | 2 ++ kernel/sched/core.c | 32 ++++++++++++++++++++++++-------- kernel/sched/ext.h | 24 ++++++++++++++++++++++++ kernel/sched/idle.c | 2 ++ kernel/sched/sched.h | 2 ++ 6 files changed, 66 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>
@@ -843,6 +844,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 +24 -8
@@ -4682,6 +4682,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
@@ -4718,12 +4720,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);
@@ -4741,6 +4747,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)
@@ -4771,16 +4781,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)
@@ -5935,7 +5947,7 @@ 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 ; }
@@ -5953,6 +5965,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
@@ -5978,7 +5993,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;
@@ -6011,7 +6026,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;
@@ -9953,6 +9968,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 +24 -0
@@ -0,0 +1,24 @@ +/* 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 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 */ + +#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
@@ -407,11 +407,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
@@ -3411,4 +3411,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.39.2
Tejun Heo
maintainerPATCH 13/32 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.
v3: * ops.set_weight() added to allow BPF schedulers to track weight changes
without polling p->scx.weight.
* move_task_to_local_dsq() was losing SCX-specific enq_flags when enqueueing the task on the target dsq because it goes through activate_task() which loses the upper 32bit of the flags. Carry the flags through rq->scx.extra_enq_flags.
* scx_bpf_dispatch(), scx_bpf_pick_idle_cpu(), scx_bpf_task_running() and scx_bpf_task_cpu() now use the new KF_RCU instead of KF_TRUSTED_ARGS to make it easier for BPF schedulers to call them.
* The kfunc helper access control mechanism implemented through sched_ext_entity.kf_mask is improved. Now SCX_CALL_OP*() is always used when invoking scx_ops operations.
v2: * balance_scx_on_up() is dropped. Instead, on UP, balance_scx() is
called from put_prev_taks_scx() and pick_next_task_scx() as necessary. To determine whether balance_scx() should be called from put_prev_task_scx(), SCX_TASK_DEQD_FOR_SLEEP flag is added. See the comment in put_prev_task_scx() for details.
* sched_deq_and_put_task() / sched_enq_and_set_task() sequences replaced with SCHED_CHANGE_BLOCK().
* Unused all_dsqs list removed. This was a left-over from previous iterations.
* p->scx.kf_mask is added to track and enforce which kfunc helpers are allowed. Also, init/exit sequences are updated to make some kfuncs always safe to call regardless of the current BPF scheduler state. Combined, this should make all the kfuncs safe.
* BPF now supports sleepable struct_ops operations. Hacky workaround removed and operations and kfunc helpers are tagged appropriately.
* BPF now supports bitmask / cpumask helpers. scx_bpf_get_idle_cpumask() and friends are added so that BPF schedulers can use the idle masks with the generic helpers. This replaces the hacky kfunc helpers added by a separate patch in V1.
* CONFIG_SCHED_CLASS_EXT can no longer be enabled if SCHED_CORE is enabled. This restriction will be removed by a later patch which adds core-sched support.
* Add MAINTAINERS entries and other misc changes.
--- MAINTAINERS | 3 + include/asm-generic/vmlinux.lds.h | 1 + include/linux/sched.h | 5 + include/linux/sched/ext.h | 401 +++- include/uapi/linux/sched.h | 1 + init/init_task.c | 10 + kernel/Kconfig.preempt | 22 +- kernel/bpf/bpf_struct_ops_types.h | 4 + kernel/sched/build_policy.c | 4 + kernel/sched/core.c | 26 + kernel/sched/debug.c | 6 + kernel/sched/ext.c | 3042 +++++++++++++++++++++++++++++ kernel/sched/ext.h | 97 +- kernel/sched/sched.h | 16 + 14 files changed, 3634 insertions(+), 4 deletions(-) create mode 100644 kernel/sched/ext.c
MAINTAINERS +3 -0
@@ -18605,6 +18605,8 @@ R: Ben Segall <[email protected]> (CONFIG_CFS_BANDWIDTH) R: Mel Gorman <[email protected]> (CONFIG_NUMA_BALANCING) R: Daniel Bristot de Oliveira <[email protected]> (SCHED_DEADLINE) R: Valentin Schneider <[email protected]> (TOPOLOGY) +R: Tejun Heo <[email protected]> (SCHED_EXT) +R: David Vernet <[email protected]> (SCHED_EXT) L: [email protected] S: Maintained T: git git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git sched/core
@@ -18613,6 +18615,7 @@ F: include/linux/sched.h F: include/linux/wait.h F: include/uapi/linux/sched.h F: kernel/sched/ +F: tools/sched_ext/ SCR24X CHIP CARD INTERFACE DRIVER M: Lubomir Rintel <[email protected]>
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 +400 -1
409 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 +21 -1
@@ -133,4 +133,24 @@ 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 && !SCHED_CORE + help + This option enables a new scheduler class sched_ext (SCX), which + allows scheduling policies to be implemented as BPF programs to + achieve the following: + + - Ease of experimentation and exploration: Enabling rapid + iteration of new scheduling policies. + - Customization: Building application-specific schedulers which + implement policies that are not applicable to general-purpose + schedulers. + - 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.
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 +26 -0
@@ -4480,6 +4480,18 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p) p->rt.on_rq =0 ; p->rt.on_list =0 ; +#ifdef CONFIG_SCHED_CLASS_EXT + p->scx.dsq =NULL ; +INIT_LIST_HEAD (&p->scx.dsq_node); + p->scx.flags =0 ; + p->scx.weight =0 ; + p->scx.sticky_cpu =-1 ; + p->scx.holding_cpu =-1 ; + p->scx.kf_mask =0 ; +atomic64_set (&p->scx.ops_state,0 ); + p->scx.slice =SCX_SLICE_DFL ; +#endif +#ifdef CONFIG_PREEMPT_NOTIFIERS INIT_HLIST_HEAD (&p->preempt_notifiers);#endif
@@ -4727,6 +4739,10 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p) goto out_cancel; }else if (rt_prio (p->prio)) { p->sched_class = &rt_sched_class; +#ifdef CONFIG_SCHED_CLASS_EXT + }else if (task_on_scx (p)) { + p->sched_class = &ext_sched_class; +#endif }else { p->sched_class = &fair_sched_class; }
@@ -7001,6 +7017,10 @@ void __setscheduler_prio(struct task_struct *p, int prio) p->sched_class = &dl_sched_class; else if (rt_prio(prio)) p->sched_class = &rt_sched_class; +#ifdef CONFIG_SCHED_CLASS_EXT + else if (task_on_scx(p)) + p->sched_class = &ext_sched_class; +#endif else p->sched_class = &fair_sched_class;
@@ -8927,6 +8947,7 @@ SYSCALL_DEFINE1(sched_get_priority_max, int, policy)case SCHED_NORMAL :case SCHED_BATCH :case SCHED_IDLE : +case SCHED_EXT : ret =0 ;break ; }
@@ -8954,6 +8975,7 @@ SYSCALL_DEFINE1(sched_get_priority_min, int, policy)case SCHED_NORMAL :case SCHED_BATCH :case SCHED_IDLE : +case SCHED_EXT : ret =0 ; }return ret;
@@ -9799,6 +9821,10 @@ void __init sched_init(void)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_SCHED_CLASS_EXT +BUG_ON (!sched_class_above (&fair_sched_class, &ext_sched_class)); +BUG_ON (!sched_class_above (&ext_sched_class, &idle_sched_class)); +#endif wait_bit_init ();
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 +3042 -0
2,397 lines not on this page · raw message
kernel/sched/ext.h +95 -2
97 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.39.2
Part of the diff is not shown here. View the raw message.
Tejun Heo
maintainerPATCH 14/32 sched_ext: Add scx_example_simple and scx_example_qmap example schedulers
In reply to Tejun HeoAdd two simple example BPF schedulers - simple and qmap.
* simple: 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.
v3: * Rename scx_example_dummy to scx_example_simple and restructure a bit
to ease later additions. Comment updates.
* Added declarations for BPF inline iterators. In the future, hopefully, these will be consolidated into a generic BPF header so that they don't need to be replicated here.
v2: * Updated with the generic BPF cpumask helpers.
--- tools/sched_ext/.gitignore | 5 + tools/sched_ext/Makefile | 188 +++++++++++++++ tools/sched_ext/gnu/stubs.h | 1 + tools/sched_ext/scx_common.bpf.h | 284 +++++++++++++++++++++++ tools/sched_ext/scx_example_qmap.bpf.c | 241 +++++++++++++++++++ tools/sched_ext/scx_example_qmap.c | 84 +++++++ tools/sched_ext/scx_example_simple.bpf.c | 56 +++++ tools/sched_ext/scx_example_simple.c | 93 ++++++++ tools/sched_ext/user_exit_info.h | 50 ++++ 9 files changed, 1002 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_qmap.bpf.c create mode 100644 tools/sched_ext/scx_example_qmap.c create mode 100644 tools/sched_ext/scx_example_simple.bpf.c create mode 100644 tools/sched_ext/scx_example_simple.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_simple +scx_example_qmap +*.skel.h +*.subskel.h +/tools/
tools/sched_ext/Makefile new file +188 -0
188 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 +284 -0
284 lines not on this page · raw message
tools/sched_ext/scx_example_qmap.bpf.c new file +241 -0
241 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/scx_example_simple.bpf.c new file +56 -0
56 lines not on this page · raw message
tools/sched_ext/scx_example_simple.c new file +93 -0
93 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.39.2
Tejun Heo
maintainerPATCH 15/32 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
@@ -1930,6 +1930,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 ;
@@ -2539,6 +2542,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;
@@ -2562,6 +2580,8 @@ void __init init_sched_ext_class(void)init_dsq (&rq->scx.local_dsq,SCX_DSQ_LOCAL ); } + +register_sysrq_key ('S' , &sysrq_sched_ext_reset_op); }
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 16/32 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().
v2: Julia Lawall noticed that the watchdog code was mixing msecs and
jiffies. Fix by using jiffies for everything.
--- include/linux/sched/ext.h | 13 +++ init/init_task.c | 2 + kernel/sched/core.c | 3 + kernel/sched/ext.c | 128 +++++++++++++++++++++++-- kernel/sched/ext.h | 25 +++++ kernel/sched/sched.h | 1 + tools/sched_ext/scx_example_qmap.bpf.c | 12 +++ tools/sched_ext/scx_example_qmap.c | 12 ++- 8 files changed, 185 insertions(+), 11 deletions(-)
include/linux/sched/ext.h +13 -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 */ };/*
@@ -315,6 +316,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 *
@@ -348,6 +358,7 @@ enum scx_ent_flags {SCX_TASK_OPS_PREPPED =1 <<8 ,/* prepared for BPF scheduler enable */ SCX_TASK_OPS_ENABLED =1 <<9 ,/* task has BPF scheduler enabled */ +SCX_TASK_WATCHDOG_RESET =1 <<16 ,/* task watchdog counter should be reset */ SCX_TASK_DEQD_FOR_SLEEP =1 <<17 ,/* last dequeue was for SLEEP */ SCX_TASK_CURSOR = 1 << 31, /* iteration cursor, not a task */
@@ -381,12 +392,14 @@ enum scx_kf_mask {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;u32 kf_mask;/* see scx_kf_mask above */ 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
@@ -4483,12 +4483,14 @@ 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 ; p->scx.kf_mask =0 ;atomic64_set (&p->scx.ops_state,0 ); + p->scx.runnable_at =INITIAL_JIFFIES ; p->scx.slice =SCX_SLICE_DFL ;#endif
@@ -5651,6 +5653,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 +119 -9
241 lines not on this page · raw message
kernel/sched/ext.h +25 -0
@@ -56,6 +56,8 @@ enum scx_deq_flags {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 scx_watchdog_timeout; +extern unsigned long scx_watchdog_timestamp;DECLARE_STATIC_KEY_FALSE (__scx_ops_enabled);#define scx_enabled () static_branch_unlikely(&__scx_ops_enabled)
@@ -67,6 +69,28 @@ void scx_post_fork(struct task_struct *p);void scx_cancel_fork (struct task_struct *p);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; + +if (!scx_enabled ()) +return ; + + last_check = scx_watchdog_timestamp; +if (unlikely (time_after (jiffies, last_check + scx_watchdog_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++;
@@ -98,6 +122,7 @@ 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 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
@@ -688,6 +688,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; u64 extra_enq_flags; /* see move_task_to_local_dsq() */ u32 nr_running;
tools/sched_ext/scx_example_qmap.bpf.c +12 -0
@@ -25,6 +25,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;
@@ -120,11 +122,20 @@ static int weight_to_idx(u32 weight)void BPF_STRUCT_OPS (qmap_enqueue ,struct task_struct *p,u64 enq_flags) { +static u32 user_cnt, kernel_cnt;struct task_ctx *tctx;u32 pid = p->pid;int idx =weight_to_idx (p->scx.weight);void *ring; +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" );
@@ -237,5 +248,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 +10 -2
@@ -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,7 +49,7 @@ int main(int argc, char **argv) skel =scx_example_qmap__open ();assert (skel); -while ((opt =getopt (argc, argv,"s:e:tTd:h" )) !=-1 ) { +while ((opt =getopt (argc, argv,"s:e:t:T:d:h" )) !=-1 ) {switch (opt) {case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;
@@ -55,6 +57,12 @@ int main(int argc, char **argv)case 'e' : 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 ]));return opt !='h' ;
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 17/32 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
@@ -411,6 +411,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
@@ -7665,6 +7665,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
@@ -1687,6 +1687,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 = { };
@@ -1697,6 +1699,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 ; }
@@ -1845,6 +1868,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: *
@@ -2528,6 +2563,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
@@ -67,6 +67,7 @@ void scx_pre_fork(struct task_struct *p);int scx_fork (struct task_struct *p);void scx_post_fork (struct task_struct *p);void scx_cancel_fork (struct task_struct *p); +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,
@@ -121,6 +122,8 @@ 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 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
@@ -27,6 +27,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;
@@ -224,6 +225,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.39.2
Tejun Heo
maintainerPATCH 18/32 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 simple and qmap example schedulers are updated to switch all tasks by default to ease testing. '-p' option is added which enables the original behavior of switching only tasks which are explicitly on SCHED_EXT.
v2: In the example schedulers, switch all tasks by default.
--- kernel/sched/core.c | 8 +++-- kernel/sched/ext.c | 45 ++++++++++++++++++++++++ kernel/sched/ext.h | 5 +++ tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_qmap.bpf.c | 9 +++++ tools/sched_ext/scx_example_qmap.c | 8 +++-- tools/sched_ext/scx_example_simple.bpf.c | 10 ++++++ tools/sched_ext/scx_example_simple.c | 8 +++-- 8 files changed, 87 insertions(+), 7 deletions(-)
kernel/sched/core.c +5 -3
@@ -1206,7 +1206,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;
@@ -5657,8 +5657,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 +45 -0
99 lines not on this page · raw message
kernel/sched/ext.h +5 -0
@@ -60,7 +60,9 @@ extern unsigned long scx_watchdog_timeout;extern unsigned long scx_watchdog_timestamp;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);
@@ -95,6 +97,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;
@@ -117,6 +121,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
@@ -52,6 +52,7 @@ void ___scx_bpf_error_format_checker(const char *fmt, ...) {} ___scx_bpf_error_format_checker(fmt, ##args); \ }) +void scx_bpf_switch_all(void) __ksym; s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym; bool scx_bpf_consume(u64 dsq_id) __ksym; u32 scx_bpf_dispatch_nr_slots(void) __ksym;
tools/sched_ext/scx_example_qmap.bpf.c +9 -0
@@ -25,6 +25,7 @@ char _license[] SEC("license") = "GPL";const volatile u64 slice_ns =SCX_SLICE_DFL ; +const volatile bool switch_partial;const volatile u32 stall_user_nth;const volatile u32 stall_kernel_nth;const volatile s32 disallow_tgid;
@@ -239,6 +240,13 @@ s32 BPF_STRUCT_OPS(qmap_prep_enable, struct task_struct *p,return -ENOMEM ; } +s32 BPF_STRUCT_OPS (qmap_init ) +{ +if (!switch_partial) +scx_bpf_switch_all (); +return 0 ; +} +void BPF_STRUCT_OPS (qmap_exit ,struct scx_exit_info *ei) {uei_record (&uei, ei);
@@ -251,6 +259,7 @@ struct sched_ext_ops qmap_ops = { .dequeue = (void *)qmap_dequeue, .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 +6 -2
@@ -20,13 +20,14 @@ 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 [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-d PID] [-p]\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" +" -p Switch only tasks on SCHED_EXT policy intead of all\n" " -h Display this help and exit\n" ;static volatile int exit_req;
@@ -50,7 +51,7 @@ int main(int argc, char **argv) skel =scx_example_qmap__open ();assert (skel); -while ((opt =getopt (argc, argv,"s:e:t:T:d:h" )) !=-1 ) { +while ((opt =getopt (argc, argv,"s:e:t:T:d:ph" )) !=-1 ) {switch (opt) {case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;
@@ -69,6 +70,9 @@ int main(int argc, char **argv)if (skel->rodata->disallow_tgid <0 ) skel->rodata->disallow_tgid =getpid ();break ; +case 'p' : + skel->rodata->switch_partial = true; +break ;default :fprintf (stderr, help_fmt,basename (argv[0 ]));return opt !='h' ;
tools/sched_ext/scx_example_simple.bpf.c +10 -0
@@ -15,6 +15,8 @@ char _license[] SEC("license") = "GPL"; +const volatile bool switch_partial; +struct user_exit_info uei;struct {
@@ -43,6 +45,13 @@ void BPF_STRUCT_OPS(simple_enqueue, struct task_struct *p, u64 enq_flags)scx_bpf_dispatch (p,SCX_DSQ_GLOBAL ,SCX_SLICE_DFL , enq_flags); } +s32 BPF_STRUCT_OPS (simple_init ) +{ +if (!switch_partial) +scx_bpf_switch_all (); +return 0 ; +} +void BPF_STRUCT_OPS (simple_exit ,struct scx_exit_info *ei) {uei_record (&uei, ei);
@@ -51,6 +60,7 @@ void BPF_STRUCT_OPS(simple_exit, struct scx_exit_info *ei) SEC(".struct_ops")struct sched_ext_ops simple_ops = { .enqueue = (void *)simple_enqueue, + .init = (void *)simple_init, .exit = (void *)simple_exit, .name ="simple" , };
tools/sched_ext/scx_example_simple.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 [-p]\n" "\n" +" -p Switch only tasks on SCHED_EXT policy intead of all\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_simple__open ();assert (skel); -while ((opt =getopt (argc, argv,"h" )) !=-1 ) { +while ((opt =getopt (argc, argv,"ph" )) !=-1 ) {switch (opt) { +case 'p' : + skel->rodata->switch_partial = true; +break ;default :fprintf (stderr, help_fmt,basename (argv[0 ]));return opt !='h' ;
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 19/32 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.
v3: * Make scx_example_central switch all tasks by default.
* Convert to BPF inline iterators.
v2: * Julia Lawall reported that scx_example_central can overflow the
dispatch buffer and malfunction. As scheduling for other CPUs can't be handled by the automatic retry mechanism, fix by implementing an explicit overflow and retry handling.
* Updated to use generic BPF cpumask helpers.
--- include/linux/sched/ext.h | 4 + kernel/sched/ext.c | 82 +++++++- kernel/sched/ext.h | 12 ++ kernel/sched/sched.h | 3 + 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 | 225 ++++++++++++++++++++++ tools/sched_ext/scx_example_central.c | 93 +++++++++ 9 files changed, 424 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
@@ -408,6 +408,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 +79 -3
125 lines not on this page · raw message
kernel/sched/ext.h +12 -0
@@ -19,6 +19,14 @@ enum scx_enq_flags {/* high 32bits are SCX specific */ +/* +* 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 extern const struct sched_class ext_sched_class;
kernel/sched/sched.h +3 -0
@@ -692,6 +692,9 @@ struct scx_rq {u64 ops_qseq;u64 extra_enq_flags;/* see move_task_to_local_dsq() */ u32 nr_running; +cpumask_var_t cpus_to_kick; +cpumask_var_t cpus_to_preempt; + struct irq_work kick_cpus_irq_work; };#endif /* CONFIG_SCHED_CLASS_EXT */
tools/sched_ext/.gitignore +1 -0
@@ -1,5 +1,6 @@ scx_example_simple scx_example_qmap +scx_example_central *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +6 -2
@@ -115,7 +115,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -Wall -Wno-compare-distinct-pointer-types \ -O2 -mcpu=v3 -all: scx_example_simple scx_example_qmap +all: scx_example_simple scx_example_qmap scx_example_central # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -174,10 +174,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_simple scx_example_qmap + rm -f scx_example_simple scx_example_qmap scx_example_central .PHONY: all clean
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -57,6 +57,7 @@ s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym; bool scx_bpf_consume(u64 dsq_id) __ksym; u32 scx_bpf_dispatch_nr_slots(void) __ksym; void scx_bpf_dispatch(struct task_struct *p, u64 dsq_id, u64 slice, u64 enq_flags) __ksym; +void scx_bpf_kick_cpu(s32 cpu, u64 flags) __ksym; s32 scx_bpf_dsq_nr_queued(u64 dsq_id) __ksym; bool scx_bpf_test_and_clear_cpu_idle(s32 cpu) __ksym; s32 scx_bpf_pick_idle_cpu(const cpumask_t *cpus_allowed) __ksym;
tools/sched_ext/scx_example_central.bpf.c new file +225 -0
225 lines not on this page · raw message
tools/sched_ext/scx_example_central.c new file +93 -0
93 lines not on this page · raw message
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 20/32 sched_ext: Make watchdog handle ops.dispatch() looping stall
In reply to Tejun HeoThe dispatch path retries if the local DSQ is still empty after ops.dispatch() either dispatched or consumed a task. This is both out of necessity and for convenience. It has to retry because the dispatch path might lose the tasks to dequeue while the rq lock is released while trying to migrate tasks across CPUs, and the retry mechanism makes ops.dispatch() implementation easier as it only needs to make some forward progress each iteration.
However, this makes it possible for ops.dispatch() to stall CPUs by repeatedly dispatching ineligible tasks. If all CPUs are stalled that way, the watchdog or sysrq handler can't run and the system can't be saved. Let's address the issue by breaking out of the dispatch loop after 32 iterations.
It is unlikely but not impossible for ops.dispatch() to legitimately go over the iteration limit. We want to come back to the dispatch path in such cases as not doing so risks stalling the CPU by idling with runnable tasks pending. As the previous task is still current in balance_scx(), resched_curr() doesn't do anything - it will just get cleared. Let's instead use scx_kick_bpf() which will trigger reschedule after switching to the next task which will likely be the idle task.
--- kernel/sched/ext.c | 17 +++++++++++++++++ tools/sched_ext/scx_example_qmap.bpf.c | 17 +++++++++++++++++ tools/sched_ext/scx_example_qmap.c | 8 ++++++-- 3 files changed, 40 insertions(+), 2 deletions(-)
kernel/sched/ext.c +17 -0
@@ -9,6 +9,7 @@enum scx_internal_consts {SCX_NR_ONLINE_OPS =SCX_OP_IDX (init),SCX_DSP_DFL_MAX_BATCH =32 , +SCX_DSP_MAX_LOOPS =32 ,SCX_WATCHDOG_MAX_TIMEOUT =30 *HZ , };
@@ -168,6 +169,7 @@ static DEFINE_PER_CPU(struct scx_dsp_ctx, scx_dsp_ctx);void scx_bpf_dispatch (struct task_struct *p,u64 dsq_id,u64 slice,u64 enq_flags); +void scx_bpf_kick_cpu (s32 cpu,u64 flags);struct scx_task_iter {struct sched_ext_entity cursor;
@@ -1287,6 +1289,7 @@ static int balance_scx(struct rq *rq, struct task_struct *prev,struct scx_rq *scx_rq = &rq->scx;struct scx_dsp_ctx *dspc =this_cpu_ptr (&scx_dsp_ctx);bool prev_on_scx = prev->sched_class == &ext_sched_class; +int nr_loops =SCX_DSP_MAX_LOOPS ;lockdep_assert_rq_held (rq);
@@ -1341,6 +1344,20 @@ static int balance_scx(struct rq *rq, struct task_struct *prev,return 1 ;if (consume_dispatch_q (rq, rf, &scx_dsq_global))return 1 ; + +/* +* ops.dispatch() can trap us in this loop by repeatedly +* dispatching ineligible tasks. Break out once in a while to +* allow the watchdog to run. As IRQ can't be enabled in +* balance(), we want to complete this scheduling cycle and then +* start a new one. IOW, we want to call resched_curr() on the +* next, most likely idle, task, not the current one. Use +* scx_bpf_kick_cpu() for deferred kicking. +*/ +if (unlikely (!--nr_loops)) { +scx_bpf_kick_cpu (cpu_of (rq),0 ); +break ; + } }while (dspc->nr_tasks);return 0 ;
tools/sched_ext/scx_example_qmap.bpf.c +17 -0
@@ -28,6 +28,7 @@ const volatile u64 slice_ns = SCX_SLICE_DFL;const volatile bool switch_partial;const volatile u32 stall_user_nth;const volatile u32 stall_kernel_nth; +const volatile u32 dsp_inf_loop_after;const volatile s32 disallow_tgid;u32 test_error_cnt;
@@ -187,6 +188,22 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cpu, struct task_struct *prev)s32 pid;int i; +if (dsp_inf_loop_after && nr_dispatched > dsp_inf_loop_after) { +struct task_struct *p; + +/* +* PID 2 should be kthreadd which should mostly be idle and off +* the scheduler. Let's keep dispatching it to force the kernel +* to call this function over and over again. +*/ + p =bpf_task_from_pid (2 ); +if (p) { +scx_bpf_dispatch (p,SCX_DSQ_GLOBAL , slice_ns,0 ); +bpf_task_release (p); +return ; + } + } +if (!idx || !cnt) {scx_bpf_error ("failed to lookup idx[%p], cnt[%p]" , idx, cnt);return ;
tools/sched_ext/scx_example_qmap.c +6 -2
@@ -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] [-d PID] [-p]\n" +"Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-l COUNT] [-d PID] [-p]\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" +" -l COUNT Trigger dispatch infinite looping after COUNT dispatches\n" " -d PID Disallow a process from switching into SCHED_EXT (-1 for self)\n" " -p Switch only tasks on SCHED_EXT policy intead of all\n" " -h Display this help and exit\n" ;
@@ -51,7 +52,7 @@ int main(int argc, char **argv) skel =scx_example_qmap__open ();assert (skel); -while ((opt =getopt (argc, argv,"s:e:t:T:d:ph" )) !=-1 ) { +while ((opt =getopt (argc, argv,"s:e:t:T:l:d:ph" )) !=-1 ) {switch (opt) {case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;
@@ -65,6 +66,9 @@ int main(int argc, char **argv)case 'T' : skel->rodata->stall_kernel_nth =strtoul (optarg,NULL ,0 );break ; +case 'l' : + skel->rodata->dsp_inf_loop_after =strtoul (optarg,NULL ,0 ); +break ;case 'd' : skel->rodata->disallow_tgid =strtol (optarg,NULL ,0 );if (skel->rodata->disallow_tgid <0 )
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 21/32 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
@@ -192,6 +192,71 @@ struct sched_ext_ops {*/ void (*dispatch)(s32 cpu,struct task_struct *prev); +/** +* 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
@@ -776,6 +776,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_CALL_OP (SCX_KF_REST , runnable, p, enq_flags); +do_enqueue_task (rq, p, enq_flags, sticky_cpu); }
@@ -836,6 +839,26 @@ static void dequeue_task_scx(struct rq *rq, struct task_struct *p, int deq_flagsops_dequeue (p, deq_flags); +/* +* 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_CALL_OP (SCX_KF_REST , stopping, p, false); + } + +if (SCX_HAS_OP (quiescent)) +SCX_CALL_OP (SCX_KF_REST , quiescent, p, deq_flags); +if (deq_flags &SCX_DEQ_SLEEP ) p->scx.flags |=SCX_TASK_DEQD_FOR_SLEEP ;else
@@ -1372,6 +1395,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_CALL_OP (SCX_KF_REST , running, p); +watchdog_unwatch_task (p, true); }
@@ -1410,6 +1437,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_CALL_OP (SCX_KF_REST , 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.39.2
Tejun Heo
maintainerPATCH 22/32 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.
v2: * Convert to BPF inline iterators.
--- 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 | 121 ++++++++++++++++++++-- tools/sched_ext/scx_example_central.c | 3 +- 7 files changed, 173 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
@@ -1202,13 +1202,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
@@ -82,6 +82,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 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,
@@ -141,6 +142,7 @@ static inline void scx_post_fork(struct task_struct *p) {}static inline void scx_cancel_fork (struct task_struct *p) {}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
@@ -686,12 +686,18 @@ 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; u64 extra_enq_flags; /* see move_task_to_local_dsq() */ u32 nr_running; + u32 flags; cpumask_var_t cpus_to_kick; cpumask_var_t cpus_to_preempt; struct irq_work kick_cpus_irq_work;
tools/sched_ext/scx_example_central.bpf.c +115 -6
181 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 retry:%10lu\n" , +printf ("timer :%10lu dispatch:%10lu mismatch:%10lu retry:%10lu\n" , + skel->bss->nr_timers, skel->bss->nr_dispatches, skel->bss->nr_mismatches, skel->bss->nr_retries);
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 23/32 sched_ext: Track tasks that are subjects of the in-flight SCX operation
In reply to Tejun HeoWhen some SCX operations are in flight, it is known that the subject task's rq lock is held throughout which makes it safe to access certain fields of the task - e.g. its current task_group. We want to add SCX kfunc helpers that can make use of this guarantee - e.g. to help determining the currently associated CPU cgroup from the task's current task_group.
As it'd be dangerous call such a helper on a task which isn't rq lock protected, the helper should be able to verify the input task and reject accordingly. This patch adds sched_ext_entity.kf_tasks[] that track the tasks which are currently being operated on by a terminal SCX operation. The new SCX_CALL_OP_[2]TASK[_RET]() can be used when invoking SCX operations which take tasks as arguments and the scx_kf_allowed_on_arg_tasks() can be used by kfunc helpers to verify the input task status.
Note that as sched_ext_entity.kf_tasks[] can't handle nesting, the tracking is currently only limited to terminal SCX operations. If needed in the future, this restriction can be removed by moving the tracking to the task side with a couple per-task counters.
--- include/linux/sched/ext.h | 2 + kernel/sched/ext.c | 91 +++++++++++++++++++++++++++++++-------- 2 files changed, 76 insertions(+), 17 deletions(-)
include/linux/sched/ext.h +2 -0
@@ -449,6 +449,7 @@ enum scx_kf_mask {SCX_KF_REST =1 <<5 ,/* other rq-locked operations */ __SCX_KF_RQ_LOCKED =SCX_KF_DISPATCH |SCX_KF_ENQUEUE |SCX_KF_REST , + __SCX_KF_TERMINAL = SCX_KF_ENQUEUE | SCX_KF_REST, };/*
@@ -464,6 +465,7 @@ struct sched_ext_entity {s32 sticky_cpu;s32 holding_cpu;u32 kf_mask;/* see scx_kf_mask above */ +struct task_struct *kf_tasks[2 ];/* see SCX_CALL_OP_TASK() */ atomic64_t ops_state;unsigned long runnable_at;
kernel/sched/ext.c +74 -17
184 lines not on this page · raw message
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 24/32 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.
v3: * Make scx_example_pair switch all tasks by default.
* Convert to BPF inline iterators.
* scx_bpf_task_cgroup() is added to determine the current cgroup from CPU controller's POV. This allows BPF schedulers to accurately track CPU cgroup membership.
* scx_exampl_flatcg added. This demonstrates flattened hierarchy implementation of CPU cgroup control and shows significant performance improvement when cgroups which are nested multiple levels are under competition.
v2: * Build fixes for different CONFIG combinations.
--- include/linux/sched/ext.h | 100 ++- init/Kconfig | 5 + kernel/sched/core.c | 70 +- kernel/sched/ext.c | 391 ++++++++++- kernel/sched/ext.h | 25 + kernel/sched/sched.h | 12 +- tools/sched_ext/.gitignore | 2 + tools/sched_ext/Makefile | 14 +- tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_flatcg.bpf.c | 824 +++++++++++++++++++++++ tools/sched_ext/scx_example_flatcg.c | 228 +++++++ tools/sched_ext/scx_example_flatcg.h | 49 ++ tools/sched_ext/scx_example_pair.bpf.c | 536 +++++++++++++++ tools/sched_ext/scx_example_pair.c | 143 ++++ tools/sched_ext/scx_example_pair.h | 10 + 15 files changed, 2386 insertions(+), 24 deletions(-) create mode 100644 tools/sched_ext/scx_example_flatcg.bpf.c create mode 100644 tools/sched_ext/scx_example_flatcg.c create mode 100644 tools/sched_ext/scx_example_flatcg.h 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 +97 -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 ,
@@ -108,14 +110,29 @@ 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 */ +#ifdef CONFIG_EXT_GROUP_SCHED +/* the cgroup the task is joining */ +struct cgroup *cgroup; +#endif +}; + +/* argument container for ops->cgroup_init() */ +struct scx_cgroup_init_args { +/* the weight of the cgroup [1..10000] */ +u32 weight; };/**
@@ -333,7 +350,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);
@@ -357,6 +375,79 @@ struct sched_ext_ops {*/ void (*disable)(struct task_struct *p); +#ifdef CONFIG_EXT_GROUP_SCHED +/** +* 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); +#endif /* CONFIG_CGROUPS */ +/* * All online ops must come before ops.init(). */
@@ -497,6 +588,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
@@ -1039,6 +1039,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 SCHED_MM_CID
kernel/sched/core.c +61 -9
188 lines not on this page · raw message
kernel/sched/ext.c +382 -9
515 lines not on this page · raw message
kernel/sched/ext.h +25 -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 */ };
@@ -162,3 +167,23 @@ 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_CGROUP_SCHED +#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_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_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 */ +#endif /* CONFIG_CGROUP_SCHED */
kernel/sched/sched.h +11 -1
@@ -424,6 +424,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;
@@ -528,6 +533,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 */
@@ -3418,7 +3428,7 @@ static inline void switch_mm_cid(struct task_struct *prev, struct task_struct *n #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 +2 -0
@@ -1,6 +1,8 @@ scx_example_simple scx_example_qmap scx_example_central +scx_example_pair +scx_example_flatcg *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +12 -2
@@ -115,7 +115,8 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -Wall -Wno-compare-distinct-pointer-types \ -O2 -mcpu=v3 -all: scx_example_simple scx_example_qmap scx_example_central +all: scx_example_simple scx_example_qmap scx_example_central scx_example_pair \ + scx_example_flatcg # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -178,10 +179,19 @@ 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) + +scx_example_flatcg: scx_example_flatcg.c scx_example_flatcg.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_simple scx_example_qmap scx_example_central + rm -f scx_example_simple scx_example_qmap scx_example_central \ + scx_example_pair scx_example_flatcg .PHONY: all clean
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -67,6 +67,7 @@ void scx_bpf_put_idle_cpumask(const struct cpumask *cpumask) __ksym; void scx_bpf_destroy_dsq(u64 dsq_id) __ksym; bool scx_bpf_task_running(const struct task_struct *p) __ksym; s32 scx_bpf_task_cpu(const struct task_struct *p) __ksym; +struct cgroup *scx_bpf_task_cgroup (struct task_struct *p) __ksym; #define BPF_STRUCT_OPS(name, args...) \ SEC("struct_ops/"#name) \
tools/sched_ext/scx_example_flatcg.bpf.c new file +824 -0
824 lines not on this page · raw message
tools/sched_ext/scx_example_flatcg.c new file +228 -0
228 lines not on this page · raw message
tools/sched_ext/scx_example_flatcg.h new file +49 -0
49 lines not on this page · raw message
tools/sched_ext/scx_example_pair.bpf.c new file +536 -0
536 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.39.2
Re: [PATCH 24/32] sched_ext: Add cgroup support
On Fri, Mar 17, 2023 at 11:33:25AM -1000, Tejun Heo wrote:
...
Quoted 22 lines
kernel/sched/ext.c +22
-0+/** +* scx_bpf_task_cgroup - Return the sched cgroup of a task +* @p: task of interest +* +* @p->sched_task_group->css.cgroup represents the cgroup @p is associated with +* from the scheduler's POV. SCX operations should use this function to +* determine @p's current cgroup as, unlike following @p->cgroups, +* @p->sched_task_group is protected by @p's rq lock and thus atomic w.r.t. all +* rq-locked operations. Can be called on the parameter tasks of rq-locked +* operations. The restriction guarantees that @p's rq is locked by the caller. +*/ +struct cgroup *scx_bpf_task_cgroup (struct task_struct *p) +{ +struct task_group *tg = p->sched_task_group; +struct cgroup *cgrp = &cgrp_dfl_root.cgrp; + +if (!scx_kf_allowed_on_arg_tasks (__SCX_KF_RQ_LOCKED, p)) + goto out; + +/* +* A task_group may either be a cgroup or an autogroup. In the latter +* case, @tg->css.cgroup is %NULL. A task_group can't become the other
kernel/sched/ext.c s32 scx_bpf_task_cpu(const struct task_struct *p) · line 3792
Quoted 10 lines
kernel/sched/ext.c +10
-0+* kind once created. +*/ +if (tg && tg->css.cgroup) + cgrp = tg->css.cgroup; +else + cgrp = &cgrp_dfl_root.cgrp; +out: +cgroup_get (cgrp); +return cgrp; +}
^ #ifdef CONFIG_CGROUP_SCHED, otherwise we may get build errors, like:
kernel/sched/ext.c:4251:34: error: 'struct task_struct' has no member named 'sched_task_group'
kernel/sched/ext.c BTF_ID_FLAGS(func, scx_bpf_error_bstr, KF_TRUSTED_ARGS) · line 3806
Quoted 9 lines
kernel/sched/ext.c +2
-0+ BTF_SET8_START(scx_kfunc_ids_any) BTF_ID_FLAGS(func, scx_bpf_kick_cpu) BTF_ID_FLAGS(func, scx_bpf_dsq_nr_queued)@@ -3431,6 +3803,7 @@ BTF_ID_FLAGS(func, scx_bpf_error_bstr, KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, scx_bpf_destroy_dsq) BTF_ID_FLAGS(func, scx_bpf_task_running, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_task_cpu, KF_RCU) +BTF_ID_FLAGS (func, scx_bpf_task_cgroup,KF_RCU |KF_ACQUIRE )
Ditto.
-Andrea
Tejun Heo
maintainerRe: [PATCH 24/32] sched_ext: Add cgroup support
Hello,
Quoted 3 lines · Andrea Righi
^ #ifdef
CONFIG_CGROUP_SCHED, otherwise we may get build errors, like:
kernel/sched/ext.c:4251:34: error: 'structtask_struct' has no member named 'sched_task_group'
Oops, thanks for spotting that. Will fix.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 25/32 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 | 33 ++++++++++++++++++++++++++++++++- kernel/sched/ext.h | 20 ++++++++++++++++++++ kernel/sched/sched.h | 2 ++ 4 files changed, 57 insertions(+), 2 deletions(-)
kernel/sched/core.c +3 -1
@@ -6019,8 +6019,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 +32 -1
@@ -126,6 +126,9 @@ static struct { static bool __cacheline_aligned_in_smp scx_has_idle_cpus;#endif /* CONFIG_SMP */ +/* for %SCX_KICK_WAIT */ +static u64 __percpu *scx_kick_cpus_pnt_seqs; +/* * Direct dispatch marker. *
@@ -3215,6 +3218,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 (scx_kick_cpus_pnt_seqs);int this_cpu =cpu_of (this_rq);int cpu;
@@ -3228,14 +3232,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); }void __init init_sched_ext_class (void )
@@ -3249,7 +3271,7 @@ void __init init_sched_ext_class(void)* through the generated vmlinux.h. */ WRITE_ONCE (v,SCX_WAKE_EXEC |SCX_ENQ_WAKEUP |SCX_DEQ_SLEEP | -SCX_TG_ONLINE ); +SCX_TG_ONLINE |SCX_KICK_PREEMPT );BUG_ON (rhashtable_init (&dsq_hash, &dsq_hash_params));init_dsq (&scx_dsq_global,SCX_DSQ_GLOBAL );
@@ -3257,6 +3279,12 @@ void __init init_sched_ext_class(void)BUG_ON (!alloc_cpumask_var (&idle_masks.cpu,GFP_KERNEL ));BUG_ON (!alloc_cpumask_var (&idle_masks.smt,GFP_KERNEL ));#endif + scx_kick_cpus_pnt_seqs = +__alloc_percpu (sizeof (scx_kick_cpus_pnt_seqs[0 ]) * +num_possible_cpus (), + __alignof__(scx_kick_cpus_pnt_seqs [0 ])); +BUG_ON (!scx_kick_cpus_pnt_seqs); +for_each_possible_cpu (cpu) {struct rq *rq =cpu_rq (cpu);
@@ -3265,6 +3293,7 @@ void __init init_sched_ext_class(void)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); }
@@ -3533,6 +3562,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
@@ -95,6 +96,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;
@@ -149,6 +166,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
@@ -710,6 +710,8 @@ struct scx_rq {u32 flags;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 /* CONFIG_SCHED_CLASS_EXT */
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 26/32 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.
v3: * Drop the const qualifier from scx_cpu_release_args.task. BPF enforces
access control through the verifier, so the qualifier isn't actually operative and only gets in the way when interacting with various helpers.
v2: * Add p->scx.kf_mask annotation to allow calling
scx_bpf_reenqueue_local() from ops.cpu_release() nested inside ops.init() and other sleepable operations.
--- include/linux/sched/ext.h | 53 +++++++++- kernel/sched/ext.c | 131 ++++++++++++++++++++++++- kernel/sched/ext.h | 24 ++++- 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 | 37 ++++++- tools/sched_ext/scx_example_qmap.c | 4 +- 8 files changed, 340 insertions(+), 12 deletions(-)
include/linux/sched/ext.h +52 -1
@@ -135,6 +135,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 */ +struct task_struct *task; +}; +/** * struct sched_ext_ops - Operation table for BPF scheduler implementation *
@@ -330,6 +356,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
@@ -534,12 +582,15 @@ enum scx_kf_mask {/* all non-sleepables may be nested inside INIT and SLEEPABLE */ SCX_KF_INIT =1 <<0 ,/* running ops.init() */ SCX_KF_SLEEPABLE =1 <<1 ,/* other sleepable init operations */ +/* ENQUEUE and DISPATCH may be nested inside CPU_RELEASE */ +SCX_KF_CPU_RELEASE =1 <<2 ,/* ops.cpu_release() */ /* ops.dequeue (in REST) may be nested inside DISPATCH */ SCX_KF_DISPATCH =1 <<3 ,/* ops.dispatch() */ SCX_KF_ENQUEUE =1 <<4 ,/* ops.enqueue() */ SCX_KF_REST =1 <<5 ,/* other rq-locked operations */ - __SCX_KF_RQ_LOCKED =SCX_KF_DISPATCH |SCX_KF_ENQUEUE |SCX_KF_REST , + __SCX_KF_RQ_LOCKED =SCX_KF_CPU_RELEASE |SCX_KF_DISPATCH | +SCX_KF_ENQUEUE |SCX_KF_REST , __SCX_KF_TERMINAL = SCX_KF_ENQUEUE | SCX_KF_REST, };
kernel/sched/ext.c +130 -1
185 lines not on this page · raw message
kernel/sched/ext.h +22 -2
@@ -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
@@ -82,6 +93,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);
@@ -96,13 +109,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, +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, +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
@@ -110,6 +127,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
@@ -708,6 +708,7 @@ struct scx_rq {u64 extra_enq_flags;/* see move_task_to_local_dsq() */ u32 nr_running;u32 flags; +bool cpu_released;cpumask_var_t cpus_to_kick;cpumask_var_t cpus_to_preempt;cpumask_var_t cpus_to_wait;
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -68,6 +68,7 @@ void scx_bpf_destroy_dsq(u64 dsq_id) __ksym; bool scx_bpf_task_running(const struct task_struct *p) __ksym; s32 scx_bpf_task_cpu(const struct task_struct *p) __ksym;struct cgroup *scx_bpf_task_cgroup (struct task_struct *p) __ksym; +u32 scx_bpf_reenqueue_local(void) __ksym; #define BPF_STRUCT_OPS(name, args...) \ SEC("struct_ops/"#name) \
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 +36 -1
@@ -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. * * This scheduler is primarily for demonstration and testing of sched_ext * features and unlikely to be useful for actual workloads.
@@ -81,7 +83,7 @@ struct { } dispatch_idx_cnt SEC(".maps");/* Statistics */ -unsigned long nr_enqueued, nr_dispatched, nr_dequeued; +unsigned long nr_enqueued, nr_dispatched, nr_reenqueued, nr_dequeued;s32 BPF_STRUCT_OPS (qmap_select_cpu ,struct task_struct *p,s32 prev_cpu,u64 wake_flags)
@@ -155,6 +157,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 ; + } + ring =bpf_map_lookup_elem (&queue_arr, &idx);if (!ring) {scx_bpf_error ("failed to find ring %d" , idx);
@@ -240,6 +258,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) {
@@ -275,6 +309,7 @@ struct sched_ext_ops qmap_ops = { .enqueue = (void *)qmap_enqueue, .dequeue = (void *)qmap_dequeue, .dispatch = (void *)qmap_dispatch, + .cpu_release = (void *)qmap_cpu_release, .prep_enable = (void *)qmap_prep_enable, .init = (void *)qmap_init, .exit = (void *)qmap_exit,
tools/sched_ext/scx_example_qmap.c +2 -2
@@ -92,9 +92,9 @@ int main(int argc, char **argv)long nr_enqueued = skel->bss->nr_enqueued;long nr_dispatched = skel->bss->nr_dispatched; -printf ("enq=%lu, dsp=%lu, delta=%ld, deq=%lu\n" , +printf ("enq=%lu, dsp=%lu, delta=%ld, reenq=%lu, deq=%lu\n" , nr_enqueued, nr_dispatched, nr_enqueued - nr_dispatched, - skel->bss->nr_dequeued); + skel->bss->nr_reenqueued, skel->bss->nr_dequeued);fflush (stdout);sleep (1 ); }
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 27/32 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 | 18 +++++++++++++++++- 2 files changed, 35 insertions(+), 1 deletion(-)
include/linux/sched/ext.h +18 -0
@@ -378,6 +378,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 ops.enqueue() or run 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 ops.enqueue() or run 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 +17 -1
@@ -1393,7 +1393,8 @@ static int balance_scx(struct rq *rq, struct task_struct *prev,* emitted in scx_notify_pick_next_task(). */ if (SCX_HAS_OP (cpu_acquire)) -SCX_CALL_OP (0 , cpu_acquire,cpu_of (rq),NULL ); +SCX_CALL_OP (SCX_KF_UNLOCKED , cpu_acquire,cpu_of (rq), +NULL ); rq->scx.cpu_released = false; }
@@ -1824,6 +1825,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_CALL_OP (SCX_KF_REST , 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_CALL_OP (SCX_KF_REST , cpu_offline,cpu_of (rq)); +} +#else /* !CONFIG_SMP */ static bool test_and_clear_cpu_idle (int cpu) {return false; }
@@ -2329,6 +2342,9 @@ DEFINE_SCHED_CLASS(ext) = { .balance = balance_scx, .select_task_rq = select_task_rq_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.39.2
Tejun Heo
maintainerPATCH 28/32 sched_ext: Implement core-sched support
In reply to Tejun HeoThe core-sched support is composed of the following parts:
* task_struct->scx.core_sched_at is added. This is a timestamp which can be used to order tasks. Depending on whether the BPF scheduler implements custom ordering, it tracks either global FIFO ordering of all tasks or local-DSQ ordering within the dispatched tasks on a CPU.
* prio_less() is updated to call scx_prio_less() when comparing SCX tasks. scx_prio_less() calls ops.core_sched_before() if available or uses the core_sched_at timestamp. For global FIFO ordering, the BPF scheduler doesn't need to do anything. Otherwise, it should implement ops.core_sched_before() which reflects the ordering.
* When core-sched is enabled, balance_scx() balances all SMT siblings so that they all have tasks dispatched if necessary before pick_task_scx() is called. pick_task_scx() picks between the current task and the first dispatched task on the local DSQ based on availability and the core_sched_at timestamps. Note that FIFO ordering is expected among the already dispatched tasks whether running or on the local DSQ, so this path always compares core_sched_at instead of calling into ops.core_sched_before().
qmap_core_sched_before() is added to scx_example_qmap. It scales the distances from the heads of the queues to compare the tasks across different priority queues and seems to behave as expected.
v2: * Sched core added the const qualifiers to prio_less task arguments.
Explicitly drop them for ops.core_sched_before() task arguments. BPF enforces access control through the verifier, so the qualifier isn't actually operative and only gets in the way when interacting with various helpers.
--- include/linux/sched/ext.h | 21 +++ kernel/Kconfig.preempt | 2 +- kernel/sched/core.c | 12 +- kernel/sched/ext.c | 219 +++++++++++++++++++++++-- kernel/sched/ext.h | 13 ++ tools/sched_ext/scx_example_qmap.bpf.c | 87 +++++++++- tools/sched_ext/scx_example_qmap.c | 5 +- 7 files changed, 342 insertions(+), 17 deletions(-)
include/linux/sched/ext.h +21 -0
@@ -316,6 +316,24 @@ struct sched_ext_ops {*/ bool (*yield)(struct task_struct *from,struct task_struct *to); +/** +* core_sched_before - Task ordering for core-sched +* @a: task A +* @b: task B +* +* Used by core-sched to determine the ordering between two tasks. See +* Documentation/admin-guide/hw-vuln/core-scheduling.rst for details on +* core-sched. +* +* Both @a and @b are runnable and may or may not currently be queued on +* the BPF scheduler. Should return %true if @a should run before @b. +* %false if there's no required ordering or @b should run before @a. +* +* If not specified, the default is ordering them according to when they +* became runnable. +*/ +bool (*core_sched_before)(struct task_struct *a,struct task_struct *b); +/** * set_weight - Set task weight * @p: task to set weight for
@@ -628,6 +646,9 @@ struct sched_ext_entity {struct task_struct *kf_tasks[2 ];/* see SCX_CALL_OP_TASK() */ atomic64_t ops_state;unsigned long runnable_at; +#ifdef CONFIG_SCHED_CORE +u64 core_sched_at;/* see scx_prio_less() */ +#endif /* BPF scheduler modifiable fields */
kernel/Kconfig.preempt +1 -1
@@ -135,7 +135,7 @@ config SCHED_CORE config SCHED_CLASS_EXT bool "Extensible Scheduling Class" - depends on BPF_SYSCALL && BPF_JIT && !SCHED_CORE + depends on BPF_SYSCALL && BPF_JIT help This option enables a new scheduler class sched_ext (SCX), which allows scheduling policies to be implemented as BPF programs to
kernel/sched/core.c +11 -1
@@ -163,7 +163,12 @@ static inline int __task_prio(const struct task_struct *p)if (p->sched_class == &idle_sched_class)return MAX_RT_PRIO +NICE_WIDTH ;/* 140 */ -return MAX_RT_PRIO +MAX_NICE ;/* 120, squash fair */ +#ifdef CONFIG_SCHED_CLASS_EXT +if (p->sched_class == &ext_sched_class) +return MAX_RT_PRIO +MAX_NICE +1 ;/* 120, squash ext */ +#endif + +return MAX_RT_PRIO +MAX_NICE ;/* 119, squash fair */ }/*
@@ -192,6 +197,11 @@ static inline bool prio_less(const struct task_struct *a,if (pa ==MAX_RT_PRIO +MAX_NICE )/* fair */ return cfs_prio_less (a, b, in_fi); +#ifdef CONFIG_SCHED_CLASS_EXT +if (pa ==MAX_RT_PRIO +MAX_NICE +1 )/* ext */ +return scx_prio_less (a, b, in_fi); +#endif +return false; }
kernel/sched/ext.c +208 -11
326 lines not on this page · raw message
kernel/sched/ext.h +13 -0
@@ -68,6 +68,14 @@ enum scx_enq_flags {enum scx_deq_flags {/* expose select DEQUEUE_* flags as enums */ SCX_DEQ_SLEEP =DEQUEUE_SLEEP , + +/* high 32bits are SCX specific */ + +/* +* The generic core-sched layer decided to execute the task even though +* it hasn't been dispatched yet. Dequeue from the BPF side. +*/ +SCX_DEQ_CORE_SCHED_EXEC =1LLU <<32 , };enum scx_tg_flags {
@@ -173,6 +181,11 @@ static inline const struct sched_class *next_active_class(const struct sched_clafor_active_class_range (class, (prev_class) > &ext_sched_class ? \ &ext_sched_class : (prev_class), (end_class)) +#ifdef CONFIG_SCHED_CORE +bool scx_prio_less (const struct task_struct *a,const struct task_struct *b, +bool in_fi); +#endif +#else /* CONFIG_SCHED_CLASS_EXT */ #define scx_enabled () false
tools/sched_ext/scx_example_qmap.bpf.c +85 -2
142 lines not on this page · raw message
tools/sched_ext/scx_example_qmap.c +3 -2
@@ -92,9 +92,10 @@ int main(int argc, char **argv)long nr_enqueued = skel->bss->nr_enqueued;long nr_dispatched = skel->bss->nr_dispatched; -printf ("enq=%lu, dsp=%lu, delta=%ld, reenq=%lu, deq=%lu\n" , +printf ("enq=%lu, dsp=%lu, delta=%ld, reenq=%lu, deq=%lu, core=%lu\n" , nr_enqueued, nr_dispatched, nr_enqueued - nr_dispatched, - skel->bss->nr_reenqueued, skel->bss->nr_dequeued); + skel->bss->nr_reenqueued, skel->bss->nr_dequeued, + skel->bss->nr_core_sched_execed);fflush (stdout);sleep (1 ); }
Signature · 1 line
2.39.2
Re: [PATCH 28/32] sched_ext: Implement core-sched support
On Fri, Mar 17, 2023 at 11:33:29AM -1000, Tejun Heo wrote:
...
Quoted 5 lines
kernel/sched/ext.c +4
-0+static int balance_scx (struct rq *rq,struct task_struct *prev, +struct rq_flags *rf) +{ +int ret;
kernel/sched/ext.c static int balance_scx(struct rq *rq, struct task_struct *prev, · line 1551
Quoted 10 lines
kernel/sched/ext.c +10
-0+ + ret =balance_one (rq, prev, rf, true); + +/* +* When core-sched is enabled, this ops.balance() call will be followed +* by put_prev_scx() and pick_task_scx() on this CPU and pick_task_scx() +* on the SMT siblings. Balance the siblings too. +*/ +if (sched_core_enabled (rq)) { +const struct cpumask *smt_mask =cpu_smt_mask (cpu_of (rq));
balance_scx() should be a no-op if CONFIG_SCHED_SMT is undefined or we may get a build error here.
For example with a minimal ppc64le config (and CONFIG_SCHED_SMT off) I can reproduce this:
./arch/powerpc/include/asm/smp.h:139:22: error: implicit declaration of function 'cpu_smt_mask'; did you mean 'cpu_cpu_mask'? [-Werror=implicit-function-declaration]
So maybe have something like this (or similar):
#ifdef CONFIG_SCHED_SMT
...
#else
static inline int balance_scx(struct rq *rq, struct task_struct *prev,
struct rq_flags *rf)
{
return 0
}
#endif
Thanks,
-Andrea
Tejun Heo
maintainerRe: [PATCH 28/32] sched_ext: Implement core-sched support
Hello, Andrea.
Quoted 28 lines · Andrea Righi
On Fri, Mar 17, 2023 at 11:33:29AM -1000, Tejun Heo wrote:
...Quoted 5 lines
kernel/sched/ext.c +4
-0+static int balance_scx (struct rq *rq,struct task_struct *prev, +struct rq_flags *rf) +{ +int ret;kernel/sched/ext.c static int balance_scx(struct rq *rq, struct task_struct *prev, · line 1551
Quoted 10 lines
kernel/sched/ext.c +10
-0+ + ret =balance_one (rq, prev, rf, true); + +/* +* When core-sched is enabled, this ops.balance() call will be followed +* by put_prev_scx() and pick_task_scx() on this CPU and pick_task_scx() +* on the SMT siblings. Balance the siblings too. +*/ +if (sched_core_enabled (rq)) { +const struct cpumask *smt_mask =cpu_smt_mask (cpu_of (rq));
balance_scx()should be a no-op ifCONFIG_SCHED_SMTis undefined or we may get a build error here.For example with a minimal ppc64le config (and
CONFIG_SCHED_SMToff) I can reproduce this:
./arch/powerpc/include/asm/smp.h:139:22: error: implicit declaration of function 'cpu_smt_mask'; did you mean 'cpu_cpu_mask'? [-Werror=implicit-function-declaration]So maybe have something like this (or similar):
Quoted 9 lines
#ifdef
CONFIG_SCHED_SMT
...
#else
static inline int balance_scx(struct rq *rq, structtask_struct*prev,
structrq_flags*rf)
{
return 0
}
#endif
Will fix.
Thank you.
Signature · 1 line
tejun
Tejun Heo
maintainerPATCH 29/32 sched_ext: Add vtime-ordered priority queue to dispatch_q's
In reply to Tejun HeoCurrently, a dsq is always a FIFO. A task which is dispatched earlier gets consumed or executed earlier. While this is sufficient when dsq's are used for simple staging areas for tasks which are ready to execute, it'd make dsq's a lot more useful if they can implement custom ordering.
This patch adds a vtime-ordered priority queue to dsq's. When the BPF scheduler dispatches a task with the new scx_bpf_dispatch_vtime() helper, it can specify the vtime tha the task should be inserted at and the task is inserted into the priority queue in the dsq which is ordered according to time_before64() comparison of the vtime values. When executing or consuming the dsq, the FIFO is always processed first and the priority queue is processed iff the FIFO is empty.
The design decision was made to allow both FIFO and priority queue to be available at the same timeq for all dsq's for three reasons. First, the new priority queue is useful for the local dsq's too but they also need the FIFO when consuming tasks from other dsq's as the vtimes may not be comparable across them. Second, the interface surface is smaller this way - the only additional interface necessary is scx_bpf_dispsatch_vtime(). Third, the overhead isn't meaningfully different whether they're available at the same time or not.
This makes it very easy for the BPF schedulers to implement proper vtime based scheduling within each dsq very easy and efficient at a negligible cost in terms of code complexity and overhead.
scx_example_simple and scx_example_flatcg are updated to default to weighted vtime scheduling (the latter within each cgroup). FIFO scheduling can be selected with -f option.
--- include/linux/sched/ext.h | 16 ++- init/init_task.c | 2 +- kernel/sched/core.c | 3 +- kernel/sched/ext.c | 137 ++++++++++++++++++++--- kernel/sched/ext.h | 1 + tools/sched_ext/scx_common.bpf.h | 1 + tools/sched_ext/scx_example_flatcg.bpf.c | 50 ++++++++- tools/sched_ext/scx_example_flatcg.c | 4 + tools/sched_ext/scx_example_simple.bpf.c | 66 ++++++++++- tools/sched_ext/scx_example_simple.c | 6 +- 10 files changed, 262 insertions(+), 24 deletions(-)
include/linux/sched/ext.h +15 -1
@@ -583,6 +583,7 @@ struct sched_ext_ops {struct scx_dispatch_q {raw_spinlock_t lock;struct list_head fifo;/* processed in dispatching order */ +struct rb_root_cached priq;/* processed in p->scx.dsq_vtime order */ u32 nr;u64 id;struct rhash_head hash_node;
@@ -595,6 +596,7 @@ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ SCX_TASK_BAL_KEEP =1 <<1 ,/* balance decided to keep current */ SCX_TASK_ENQ_LOCAL =1 <<2 ,/* used by scx_select_cpu_dfl() to set SCX_ENQ_LOCAL */ +SCX_TASK_ON_DSQ_PRIQ =1 <<3 ,/* task is queued on the priority queue of a dsq */ SCX_TASK_OPS_PREPPED =1 <<8 ,/* prepared for BPF scheduler enable */ SCX_TASK_OPS_ENABLED = 1 << 9, /* task has BPF scheduler enabled */
@@ -636,7 +638,10 @@ enum scx_kf_mask {*/ struct sched_ext_entity {struct scx_dispatch_q *dsq; -struct list_head dsq_node; +struct { +struct list_head fifo;/* dispatch order */ +struct rb_node priq;/* p->scx.dsq_vtime order */ + } dsq_node;struct list_head watchdog_node;u32 flags;/* protected by rq lock */ u32 weight;
@@ -664,6 +669,15 @@ struct sched_ext_entity {*/ u64 slice; +/* +* Used to order tasks when dispatching to the vtime-ordered priority +* queue of a dsq. This is usually set through scx_bpf_dispatch_vtime() +* but can also be modified directly by the BPF scheduler. Modifying it +* while a task is queued on a dsq may mangle the ordering and is not +* recommended. +*/ +u64 dsq_vtime; +/* * If set, reject future sched_setscheduler(2) calls updating the policy * to %SCHED_EXT with -%EACCES.
init/init_task.c +1 -1
@@ -105,7 +105,7 @@ struct task_struct init_task#endif #ifdef CONFIG_SCHED_CLASS_EXT .scx = { - .dsq_node = LIST_HEAD_INIT(init_task.scx.dsq_node), + .dsq_node.fifo = LIST_HEAD_INIT(init_task.scx.dsq_node.fifo), .watchdog_node = LIST_HEAD_INIT(init_task.scx.watchdog_node), .sticky_cpu = -1, .holding_cpu = -1,
kernel/sched/core.c +2 -1
@@ -4495,7 +4495,8 @@ 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.dsq_node.fifo); +RB_CLEAR_NODE (&p->scx.dsq_node.priq);INIT_LIST_HEAD (&p->scx.watchdog_node); p->scx.flags =0 ; p->scx.weight =0 ;
kernel/sched/ext.c +120 -17
232 lines not on this page · raw message
kernel/sched/ext.h +1 -0
@@ -63,6 +63,7 @@ enum scx_enq_flags { __SCX_ENQ_INTERNAL_MASK =0xffLLU <<56 ,SCX_ENQ_CLEAR_OPSS =1LLU <<56 , + SCX_ENQ_DSQ_PRIQ = 1LLU << 57, }; enum scx_deq_flags {
tools/sched_ext/scx_common.bpf.h +1 -0
@@ -57,6 +57,7 @@ s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym; bool scx_bpf_consume(u64 dsq_id) __ksym; u32 scx_bpf_dispatch_nr_slots(void) __ksym; void scx_bpf_dispatch(struct task_struct *p, u64 dsq_id, u64 slice, u64 enq_flags) __ksym; +void scx_bpf_dispatch_vtime(struct task_struct *p, u64 dsq_id, u64 slice, u64 vtime, u64 enq_flags) __ksym; void scx_bpf_kick_cpu(s32 cpu, u64 flags) __ksym; s32 scx_bpf_dsq_nr_queued(u64 dsq_id) __ksym; bool scx_bpf_test_and_clear_cpu_idle(s32 cpu) __ksym;
tools/sched_ext/scx_example_flatcg.bpf.c +49 -1
86 lines not on this page · raw message
tools/sched_ext/scx_example_flatcg.c +4 -0
@@ -30,6 +30,7 @@ const char help_fmt[] ="\n" " -s SLICE_US Override slice duration\n" " -i INTERVAL Report interval\n" +" -f Use FIFO scheduling instead of weighted vtime scheduling\n" " -p Switch only tasks on SCHED_EXT policy intead of all\n" " -h Display this help and exit\n" ;
@@ -149,6 +150,9 @@ int main(int argc, char **argv)case 'd' : dump_cgrps = true;break ; +case 'f' : + skel->rodata->fifo_sched = true; +break ;case 'p' : skel->rodata->switch_partial = true;break ;
tools/sched_ext/scx_example_simple.bpf.c +64 -2
104 lines not on this page · raw message
tools/sched_ext/scx_example_simple.c +5 -1
@@ -21,6 +21,7 @@ const char help_fmt[] ="\n" "Usage: %s [-p]\n" "\n" +" -f Use FIFO scheduling instead of weighted vtime scheduling\n" " -p Switch only tasks on SCHED_EXT policy intead of all\n" " -h Display this help and exit\n" ;
@@ -65,8 +66,11 @@ int main(int argc, char **argv) skel =scx_example_simple__open ();assert (skel); -while ((opt =getopt (argc, argv,"ph" )) !=-1 ) { +while ((opt =getopt (argc, argv,"fph" )) !=-1 ) {switch (opt) { +case 'f' : + skel->rodata->fifo_sched = true; +break ;case 'p' : skel->rodata->switch_partial = true;break ;
Signature · 1 line
2.39.2
Tejun Heo
maintainerPATCH 30/32 sched_ext: Documentation: scheduler: Document extensible scheduler class
In reply to Tejun HeoAdd Documentation/scheduler/sched-ext.rst which gives a high-level overview and pointers to the examples.
v2: Apply minor edits suggested by Bagas. Caveats section dropped as all of
them are addressed.
--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-ext.rst | 230 ++++++++++++++++++++++++++ include/linux/sched/ext.h | 2 + kernel/Kconfig.preempt | 2 + kernel/sched/ext.c | 2 + kernel/sched/ext.h | 2 + 6 files changed, 239 insertions(+) create mode 100644 Documentation/scheduler/sched-ext.rst
Documentation/scheduler/index.rst +1 -0
@@ -19,6 +19,7 @@ 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/Kconfig.preempt +2 -0
@@ -154,3 +154,5 @@ config SCHED_CLASS_EXT 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. + + See Documentation/scheduler/sched-ext.rst for more details.
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.39.2
Re: [PATCH 30/32] sched_ext: Documentation: scheduler: Document extensible scheduler class
Quoted 226 lines · Tejun Heo
Documentation/scheduler/sched-ext.rst new file +220
-0@@ -0,0 +1,230 @@ +========================== +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 the SysRq key sequence + :kbd:`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 :kbd:`SysRq-S`, or +detection of any internal error including stalled runnable tasks aborts the +BPF scheduler and reverts all tasks back to CFS. + +.. code-block:: none + + # make -j16 -C tools/sched_ext + # tools/sched_ext/scx_example_simple + local=0 global=3 + local=5 global=24 + local=9 global=44 + local=13 global=56 + local=17 global=72 + ^CEXIT: BPF scheduler unregistered + +If ``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: + +.. code-block:: none + + # cat /sys/kernel/debug/sched/ext + ops : simple + enabled : 1 + switching_all : 1 + switched_all : 1 + enable_state : enabled + + # grep ext /proc/self/sched + ext.enabled : 1 + +The 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_simple.bpf.c`` showing a minimal global FIFO +scheduler. + +.. code-block:: c + + s32 BPF_STRUCT_OPS(simple_init) + { + if (!switch_partial) + scx_bpf_switch_all(); + return 0; + } + + void BPF_STRUCT_OPS(simple_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(simple_exit, struct scx_exit_info *ei) + { + exit_type = ei->type; + } + + SEC(".struct_ops") + struct sched_ext_ops simple_ops = { + .enqueue = (void *)simple_enqueue, + .init = (void *)simple_init, + .exit = (void *)simple_exit, + .name = "simple", + }; + +Dispatch Queues +--------------- + +To match the impedance between the scheduler core and the BPF scheduler, +sched_ext uses DSQs (dispatch queues) which can operate as both a FIFO and a +priority queue. 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 simple 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. + +``scx_bpf_dispatch()`` queues the task on the FIFO of the target DSQ. Use +``scx_bpf_dispatch_vtime()`` for the priority queue. See the function +documentation and usage in ``tools/sched_ext/scx_example_simple.bpf.c`` for +more information. + +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_simple[.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
Documentation/scheduler/sched-ext.rst line 230
Quoted 10 lines
Documentation/scheduler/sched-ext.rst new file +10
-0+=============== + +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.
The doc LGTM, thanks!
Signature · 1 line
An old man doll... just what I always wanted! - Clara
Tejun Heo
maintainerPATCH 31/32 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.
v2: * Converted to BPF inline iterators.
--- tools/sched_ext/.gitignore | 1 + tools/sched_ext/Makefile | 9 +- tools/sched_ext/scx_example_userland.bpf.c | 269 ++++++++++++ tools/sched_ext/scx_example_userland.c | 403 ++++++++++++++++++ tools/sched_ext/scx_example_userland_common.h | 19 + 5 files changed, 699 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
@@ -3,6 +3,7 @@ scx_example_qmap scx_example_central scx_example_pair scx_example_flatcg +scx_example_userland *.skel.h *.subskel.h /tools/
tools/sched_ext/Makefile +7 -2
@@ -116,7 +116,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -O2 -mcpu=v3 all: scx_example_simple scx_example_qmap scx_example_central scx_example_pair \ - scx_example_flatcg + scx_example_flatcg scx_example_userland # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -187,11 +187,16 @@ scx_example_flatcg: scx_example_flatcg.c scx_example_flatcg.skel.h user_exit_inf $(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_simple scx_example_qmap scx_example_central \ - scx_example_pair scx_example_flatcg + scx_example_pair scx_example_flatcg scx_example_userland .PHONY: all clean
tools/sched_ext/scx_example_userland.bpf.c new file +269 -0
269 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.39.2
Tejun Heo
maintainerPATCH 32/32 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.
v3: * The userspace code is substantially restructured and rewritten. The
binary is renamed to scx_atropos and can now figure out the domain topology automatically based on L3 cache configuration. The LB logic which was rather broken in the previous postings are revamped and should behave better.
* Updated to support weighted vtime scheduling (can be turned off with --fifo-sched). Added a couple options (--slice_us, --kthreads-local) to modify scheduling behaviors.
* Converted to use BPF inline iterators.
v2: * Updated to use generic BPF cpumask helpers.
--- tools/sched_ext/Makefile | 13 +- tools/sched_ext/atropos/.gitignore | 3 + tools/sched_ext/atropos/Cargo.toml | 28 + tools/sched_ext/atropos/build.rs | 70 ++ tools/sched_ext/atropos/rustfmt.toml | 8 + tools/sched_ext/atropos/src/atropos_sys.rs | 10 + tools/sched_ext/atropos/src/bpf/atropos.bpf.c | 751 ++++++++++++++ tools/sched_ext/atropos/src/bpf/atropos.h | 44 + tools/sched_ext/atropos/src/main.rs | 942 ++++++++++++++++++ 9 files changed, 1867 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/atropos_sys.rs 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
tools/sched_ext/Makefile +11 -2
@@ -85,6 +85,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
@@ -116,7 +118,7 @@ BPF_CFLAGS = -g -D__TARGET_ARCH_$(SRCARCH) \ -O2 -mcpu=v3 all: scx_example_simple scx_example_qmap scx_example_central scx_example_pair \ - scx_example_flatcg scx_example_userland + scx_example_flatcg scx_example_userland atropos # sort removes libbpf duplicates when not cross-building MAKE_DIRS := $(sort $(BUILD_DIR)/libbpf $(HOST_BUILD_DIR)/libbpf \
@@ -192,13 +194,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 -C link-args=-lz -C link-args=-lelf -L $(BPFOBJ_DIR) +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_simple scx_example_qmap scx_example_central \ scx_example_pair scx_example_flatcg 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 +28 -0
@@ -0,0 +1,28 @@ +[package] +name = "scx_atropos" +version = "0.5.0" +authors = ["Dan Schatzberg <[email protected]>", "Meta"] +edition = "2021" +description = "Userspace scheduling with BPF" +license = "GPL-2.0-only" + +[dependencies] +anyhow = "1.0.65" +bitvec = { version = "1.0", features = ["serde"] } +clap = { version = "4.1", features = ["derive", "env", "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" +libbpf-sys = { version = "1.0.4", features = ["novendor", "static"] } +libc = "0.2.137" +log = "0.4.17" +ordered-float = "3.4.0" +simplelog = "0.12.0" + +[build-dependencies] +bindgen = { version = "0.61.0", features = ["logging", "static"], default-features = false } +libbpf-cargo = "0.13.0" + +[features] +enable_backtrace = []
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/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/bpf/atropos.bpf.c new file +751 -0
751 lines not on this page · raw message
tools/sched_ext/atropos/src/bpf/atropos.h new file +44 -0
44 lines not on this page · raw message
tools/sched_ext/atropos/src/main.rs new file +942 -0
942 lines not on this page · raw message
Signature · 1 line
2.39.2