<div dir="auto"></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Tejun Heo</strong> <span dir="auto"><<a href="mailto:tj@kernel.org">tj@kernel.org</a>></span><br>Date: Wed, May 1, 2024, 8:13 AM<br>Subject: [PATCHSET v6] sched: Implement BPF extensible scheduler class<br>To: <<a href="mailto:torvalds@linux-foundation.org">torvalds@linux-foundation.org</a>>, <<a href="mailto:mingo@redhat.com">mingo@redhat.com</a>>, <<a href="mailto:peterz@infradead.org">peterz@infradead.org</a>>, <<a href="mailto:juri.lelli@redhat.com">juri.lelli@redhat.com</a>>, <<a href="mailto:vincent.guittot@linaro.org">vincent.guittot@linaro.org</a>>, <<a href="mailto:dietmar.eggemann@arm.com">dietmar.eggemann@arm.com</a>>, <<a href="mailto:rostedt@goodmis.org">rostedt@goodmis.org</a>>, <<a href="mailto:bsegall@google.com">bsegall@google.com</a>>, <<a href="mailto:mgorman@suse.de">mgorman@suse.de</a>>, <<a href="mailto:bristot@redhat.com">bristot@redhat.com</a>>, <<a href="mailto:vschneid@redhat.com">vschneid@redhat.com</a>>, <<a href="mailto:ast@kernel.org">ast@kernel.org</a>>, <<a href="mailto:daniel@iogearbox.net">daniel@iogearbox.net</a>>, <<a href="mailto:andrii@kernel.org">andrii@kernel.org</a>>, <<a href="mailto:martin.lau@kernel.org">martin.lau@kernel.org</a>>, <<a href="mailto:joshdon@google.com">joshdon@google.com</a>>, <<a href="mailto:brho@google.com">brho@google.com</a>>, <<a href="mailto:pjt@google.com">pjt@google.com</a>>, <<a href="mailto:derkling@google.com">derkling@google.com</a>>, <<a href="mailto:haoluo@google.com">haoluo@google.com</a>>, <<a href="mailto:dvernet@meta.com">dvernet@meta.com</a>>, <<a href="mailto:dschatzberg@meta.com">dschatzberg@meta.com</a>>, <<a href="mailto:dskarlat@cs.cmu.edu">dskarlat@cs.cmu.edu</a>>, <<a href="mailto:riel@surriel.com">riel@surriel.com</a>>, <<a href="mailto:changwoo@igalia.com">changwoo@igalia.com</a>>, <<a href="mailto:himadrics@inria.fr">himadrics@inria.fr</a>>, <<a href="mailto:memxor@gmail.com">memxor@gmail.com</a>>, <<a href="mailto:andrea.righi@canonical.com">andrea.righi@canonical.com</a>>, <<a href="mailto:joel@joelfernandes.org">joel@joelfernandes.org</a>><br>Cc: <<a href="mailto:linux-kernel@vger.kernel.org">linux-kernel@vger.kernel.org</a>>, <<a href="mailto:bpf@vger.kernel.org">bpf@vger.kernel.org</a>>, <<a href="mailto:kernel-team@meta.com">kernel-team@meta.com</a>><br></div><br><br>Updates and Changes<br>
-------------------<br>
<br>
This is v6 of sched_ext (SCX) patchset.<br>
<br>
During the past five months, both the development and adoption of sched_ext<br>
have been progressing briskly. Here are some highlights around adoption:<br>
<br>
- Valve has been working with Igalia to implement a sched_ext scheduler for<br>
Steam Deck. The development is still in its early stages but they are<br>
already happy with the results (more consistent FPS) and are planning to<br>
enable the scheduler on Steam Deck.<br>
<br>
<a href="https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_lavd" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_lavd</a><br>
<a href="https://ossna2024.sched.com/event/1aBOT/optimizing-scheduler-for-linux-gaming-changwoo-min-igalia" rel="noreferrer noreferrer" target="_blank">https://ossna2024.sched.com/event/1aBOT/optimizing-scheduler-for-linux-gaming-changwoo-min-igalia</a><br>
<br>
- Ubuntu is considering to include sched_ext in the upcoming 24.10 release.<br>
Andrea Righi of Canonical has been actively working on a userspace<br>
scheduling framework since the end of the last year.<br>
<br>
<a href="https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_rustland" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_rustland</a><br>
<a href="https://discourse.ubuntu.com/t/introducing-kernel-6-8-for-the-24-04-noble-numbat-release/41958" rel="noreferrer noreferrer" target="_blank">https://discourse.ubuntu.com/t/introducing-kernel-6-8-for-the-24-04-noble-numbat-release/41958</a><br>
<br>
- We (Meta) are now deploying a sched_ext scheduler on one large production<br>
workload (web), conducting wide-scale verification benchmark on another<br>
(ads), and preparing production deployment on yet another workload (ML<br>
training). These are all using scx_layered, which is useful for quick<br>
prototyping and experiments. In the process, we've identified several<br>
common strategies which are useful across multiple workloads (e.g.<br>
soft-affinitizing related threads) and are in the process of implementing<br>
something more generic and polished.<br>
<br>
<a href="https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_layered" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_layered</a><br>
<br>
- Because Google's ghOSt framework (userspace scheduling framework with BPF<br>
hooks for optimization) is already available in the Google fleet, that's<br>
what Google is currently experimenting with. They are seeing promising<br>
results in a couple important workloads (search and cloud hosting) and<br>
trying to move on to deployment. The gap between ghOSt and sched_ext is<br>
not wide at this point and Google is working to port ghOSt schedulers on<br>
top of sched_ext.<br>
<br>
- ChromeOS is looking into scx_layered with focus on reducing latency (as a<br>
replacement to RT) with a prototype port of sched_ext on ChromeOS.<br>
<br>
- Oculus is facing a number of scheduling related challenges and looking<br>
into sched_ext. They have an android port that they're experimenting with<br>
although any actual deployment would have to wait until a newer platform<br>
kernel can be rolled out which will take quite a while.<br>
<br>
Although sched_ext is still out of tree, we're seeing wide interest and<br>
adoption across multiple organizations and different use cases. Plus, our<br>
first-hand experiences at Meta and the reports from other users definitively<br>
confirm the hypothesized merits of sched_ext - among others, lowered barrier<br>
of entry coupled with rapid and safe experiments leading to insights and<br>
performance gains in an easily deployable form.<br>
<br>
For example, scx_rusty and scx_layered are proving substantial benefits of<br>
better work conservation within L3 domains, soft affinity (flexibly grouping<br>
related threads together) and application specific prioritization for<br>
request-driven server workloads. scx_lavd is demonstrating the benefits of a<br>
new set of heuristics based on the runtime and the frequencies of waking up<br>
others and being woken up for gaming, and possibly other interactive,<br>
workloads.<br>
<br>
We're seeing constantly increasing interests both within Meta and from the<br>
wider community. The benefits are inherent and clear enough that I don't see<br>
a reason for the trend to change. However, being out of tree does add a lot<br>
of overhead in terms of decision making and logistics for everyone involved.<br>
<br>
Given that there already is substantial adoption which continues to grow and<br>
sched_ext doesn't affect the built-in schedulers or the rest of kernel in an<br>
invasive manner, I believe it's reasonable to consider sched_ext for<br>
inclusion. I and David Vernet would be happy to run the tree, respond to bug<br>
reports, coordinate with scheduler core or any other kernel subsystem that<br>
sched_ext may interact with.<br>
<br>
<br>
If you're interested in high-level arguments for and against. Please refer<br>
to the following discussion in the v4 posting:<br>
<br>
<a href="http://lkml.kernel.org/r/20230711011412.100319-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">http://lkml.kernel.org/r/20230711011412.100319-1-tj@kernel.org</a><br>
<br>
<br>
If you're interested in getting your hands dirty, the following repository<br>
contains example and practical schedulers along with documentation on how to<br>
get started:<br>
<br>
<a href="https://github.com/sched-ext/scx" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx</a><br>
<br>
The kernel and scheduler packages are available for Ubuntu, CachyOS and Arch<br>
(through CachyOS repo). Fedora packaging is in the works.<br>
<br>
There are also a slack and weekly office hour:<br>
<br>
<a href="https://schedextworkspace.slack.com" rel="noreferrer noreferrer" target="_blank">https://schedextworkspace.slack.com</a><br>
<br>
Office Hour: Mondays at 16:00 UTC (8:00 AM PST, 16:00 UTC, 17:00 CEST,<br>
1:00 AM KST). Please see the #office-hours channel for the<br>
zoom invite.<br>
<br>
<br>
The followings are significant changes from v5<br>
(<a href="http://lkml.kernel.org/r/20231111024835.2164816-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">http://lkml.kernel.org/r/20231111024835.2164816-1-tj@kernel.org</a>). For more<br>
detailed list of changes, please refer to the patch descriptions.<br>
<br>
- scx_pair, scx_userland, scx_next and the rust schedulers are removed from<br>
kernel tree and now hosted in <a href="https://github.com/sched-ext/scx" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx</a> along with<br>
all other schedulers.<br>
<br>
- SCX_OPS_DISABLING state is replaced with the new bypass mechanism which<br>
allows temporarily putting the system into simple FIFO scheduling mode. In<br>
addition to the shut down path, this is used to isolate the BPF scheduler<br>
across power management events.<br>
<br>
- ops.prep_enable() is replaced with ops.init_task() and<br>
ops.enable/disable() are now called whenever the task enters and leaves<br>
sched_ext instead of when the task becomes schedulable on sched_ext and<br>
stops being so. A new operation - ops.exit_task() - is called when the<br>
task stops being schedulable on sched_ext.<br>
<br>
- scx_bpf_dispatch() can now be called from ops.select_cpu() too. This<br>
removes the need for communicating local dispatch decision made by<br>
ops.select_cpu() to ops.enqueue() via per-task storage.<br>
<br>
- SCX_TASK_ENQ_LOCAL which told the BPF scheduler that scx_select_cpu_dfl()<br>
wants the task to be dispatched to the local DSQ was removed. Instead,<br>
scx_bpf_select_cpu_dfl() now dispatches directly if it finds a suitable<br>
idle CPU. If such behavior is not desired, users can use<br>
scx_bpf_select_cpu_dfl() which returns the verdict in a bool out param.<br>
<br>
- Dispatch decisions made in ops.dispatch() may now be cancelled with a new<br>
scx_bpf_dispatch_cancel() kfunc.<br>
<br>
- A new SCX_KICK_IDLE flag is available for use with scx_bpf_kick_cpu() to<br>
only send a resched IPI if the target CPU is idle.<br>
<br>
- exit_code added to scx_exit_info. This is used to indicate different exit<br>
conditions on non-error exits and enables e.g. handling CPU hotplugs by<br>
restarting the scheduler.<br>
<br>
- Debug dump added. When the BPF scheduler gets aborted, the states of all<br>
runqueues and runnable tasks are captured and sent to the scheduler binary<br>
to aid debugging. See <a href="https://github.com/sched-ext/scx/issues/234" rel="noreferrer noreferrer" target="_blank">https://github.com/sched-ext/scx/issues/234</a> for an<br>
example of the debug dump being used to root cause a bug in scx_lavd.<br>
<br>
- The BPF scheduler can now iterate DSQs and consume specific tasks.<br>
<br>
- CPU frequency scaling support added through cpuperf kfunc interface.<br>
<br>
- The current state of sched_ext can now be monitored through files under<br>
/sys/sched_ext instead of /sys/kernel/debug/sched/ext. This is to enable<br>
monitoring on kernels which don't enable debugfs. A drgn script<br>
tools/sched_ext/scx_show_state.py is added for additional visibility.<br>
<br>
- tools/sched_ext/include/scx/compat[.bpf].h and other facilities to allow<br>
schedulers to be loaded on older kernels are added. The current tentative<br>
target is maintaining backward compatibility for at least one major kernel<br>
release where reasonable.<br>
<br>
- Code reorganized so that only the parts necessary to integrate with the<br>
rest of the kernel are in the header files.<br>
<br>
<br>
Overview<br>
--------<br>
<br>
This patch set proposes a new scheduler class called ‘ext_sched_class’, or<br>
sched_ext, which allows scheduling policies to be implemented as BPF programs.<br>
<br>
More details will be provided on the overall architecture of sched_ext<br>
throughout the various patches in this set, as well as in the “How” section<br>
below. We realize that this patch set is a significant proposal, so we will be<br>
going into depth in the following “Motivation” section to explain why we think<br>
it’s justified. That section is laid out as follows, touching on three main<br>
axes where we believe that sched_ext provides significant value:<br>
<br>
1. Ease of experimentation and exploration: Enabling rapid iteration of new<br>
scheduling policies.<br>
<br>
2. Customization: Building application-specific schedulers which implement<br>
policies that are not applicable to general-purpose schedulers.<br>
<br>
3. Rapid scheduler deployments: Non-disruptive swap outs of scheduling<br>
policies in production environments.<br>
<br>
After the motivation section, we’ll provide a more detailed (but still<br>
high-level) overview of how sched_ext works.<br>
<br>
<br>
Motivation<br>
----------<br>
<br>
1. Ease of experimentation and exploration<br>
<br>
*Why is exploration important?*<br>
<br>
Scheduling is a challenging problem space. Small changes in scheduling<br>
behavior can have a significant impact on various components of a system, with<br>
the corresponding effects varying widely across different platforms,<br>
architectures, and workloads.<br>
<br>
While complexities have always existed in scheduling, they have increased<br>
dramatically over the past 10-15 years. In the mid-late 2000s, cores were<br>
typically homogeneous and further apart from each other, with the criteria for<br>
scheduling being roughly the same across the entire die.<br>
<br>
Systems in the modern age are by comparison much more complex. Modern CPU<br>
designs, where the total power budget of all CPU cores often far exceeds the<br>
power budget of the socket, with dynamic frequency scaling, and with or<br>
without chiplets, have significantly expanded the scheduling problem space.<br>
Cache hierarchies have become less uniform, with Core Complex (CCX) designs<br>
such as recent AMD processors having multiple shared L3 caches within a single<br>
socket. Such topologies resemble NUMA sans persistent NUMA node stickiness.<br>
<br>
Use-cases have become increasingly complex and diverse as well. Applications<br>
such as mobile and VR have strict latency requirements to avoid missing<br>
deadlines that impact user experience. Stacking workloads in servers is<br>
constantly pushing the demands on the scheduler in terms of workload isolation<br>
and resource distribution.<br>
<br>
Experimentation and exploration are important for any non-trivial problem<br>
space. However, given the recent hardware and software developments, we<br>
believe that experimentation and exploration are not just important, but<br>
_critical_ in the scheduling problem space.<br>
<br>
Indeed, other approaches in industry are already being explored. AMD has<br>
proposed an experimental patch set [0] which enables userspace to provide<br>
hints to the scheduler via “Userspace Hinting”. The approach adds a prctl()<br>
API which allows callers to set a numerical “hint” value on a struct<br>
task_struct. This hint is then optionally read by the scheduler to adjust the<br>
cost calculus for various scheduling decisions.<br>
<br>
[0]: <a href="https://lore.kernel.org/lkml/20220910105326.1797-1-kprateek.nayak@amd.com/" rel="noreferrer noreferrer" target="_blank">https://lore.kernel.org/lkml/20220910105326.1797-1-kprateek.nayak@amd.com/</a><br>
<br>
Huawei have also expressed interest [1] in enabling some form of programmable<br>
scheduling. While we’re unaware of any patch sets which have been sent to the<br>
upstream list for this proposal, it similarly illustrates the need for more<br>
flexibility in the scheduler.<br>
<br>
[1]: <a href="https://lore.kernel.org/bpf/dedc7b72-9da4-91d0-d81d-75360c177188@huawei.com/" rel="noreferrer noreferrer" target="_blank">https://lore.kernel.org/bpf/dedc7b72-9da4-91d0-d81d-75360c177188@huawei.com/</a><br>
<br>
Additionally, Google has developed ghOSt [2] with the goal of enabling custom,<br>
userspace driven scheduling policies. Prior presentations at LPC [3] have<br>
discussed ghOSt and how BPF can be used to accelerate scheduling.<br>
<br>
[2]: <a href="https://dl.acm.org/doi/pdf/10.1145/3477132.3483542" rel="noreferrer noreferrer" target="_blank">https://dl.acm.org/doi/pdf/10.1145/3477132.3483542</a><br>
[3]: <a href="https://lpc.events/event/16/contributions/1365/" rel="noreferrer noreferrer" target="_blank">https://lpc.events/event/16/contributions/1365/</a><br>
<br>
*Why can’t we just explore directly with CFS?*<br>
<br>
Experimenting with CFS directly or implementing a new sched_class from scratch<br>
is of course possible, but is often difficult and time consuming. Newcomers to<br>
the scheduler often require years to understand the codebase and become<br>
productive contributors. Even for seasoned kernel engineers, experimenting<br>
with and upstreaming features can take a very long time. The iteration process<br>
itself is also time consuming, as testing scheduler changes on real hardware<br>
requires reinstalling the kernel and rebooting the host.<br>
<br>
Core scheduling is an example of a feature that took a significant amount of<br>
time and effort to integrate into the kernel. Part of the difficulty with core<br>
scheduling was the inherent mismatch in abstraction between the desire to<br>
perform core-wide scheduling, and the per-cpu design of the kernel scheduler.<br>
This caused issues, for example ensuring proper fairness between the<br>
independent runqueues of SMT siblings.<br>
<br>
The high barrier to entry for working on the scheduler is an impediment to<br>
academia as well. Master’s/PhD candidates who are interested in improving the<br>
scheduler will spend years ramping-up, only to complete their degrees just as<br>
they’re finally ready to make significant changes. A lower entrance barrier<br>
would allow researchers to more quickly ramp up, test out hypotheses, and<br>
iterate on novel ideas. Research methodology is also severely hampered by the<br>
high barrier of entry to make modifications; for example, the Shenango [4] and<br>
Shinjuku scheduling policies used sched affinity to replicate the desired<br>
policy semantics, due to the difficulty of incorporating these policies into<br>
the kernel directly.<br>
<br>
[4]: <a href="https://www.usenix.org/system/files/nsdi19-ousterhout.pdf" rel="noreferrer noreferrer" target="_blank">https://www.usenix.org/system/files/nsdi19-ousterhout.pdf</a><br>
<br>
The iterative process itself also imposes a significant cost to working on the<br>
scheduler. Testing changes requires developers to recompile and reinstall the<br>
kernel, reboot their machines, rewarm their workloads, and then finally rerun<br>
their benchmarks. Though some of this overhead could potentially be mitigated<br>
by enabling schedulers to be implemented as kernel modules, a machine crash or<br>
subtle system state corruption is always only one innocuous mistake away.<br>
These problems are exacerbated when testing production workloads in a<br>
datacenter environment as well, where multiple hosts may be involved in an<br>
experiment; requiring a significantly longer ramp up time. Warming up memcache<br>
instances in the Meta production environment takes hours, for example.<br>
<br>
*How does sched_ext help with exploration?*<br>
<br>
sched_ext attempts to address all of the problems described above. In this<br>
section, we’ll describe the benefits to experimentation and exploration that<br>
are afforded by sched_ext, provide real-world examples of those benefits, and<br>
discuss some of the trade-offs and considerations in our design choices.<br>
<br>
One of our main goals was to lower the barrier to entry for experimenting<br>
with the scheduler. sched_ext provides ergonomic callbacks and helpers to<br>
ease common operations such as managing idle CPUs, scheduling tasks on<br>
arbitrary CPUs, handling preemptions from other scheduling classes, and<br>
more. While sched_ext does require some ramp-up, the complexity is<br>
self-contained, and the learning curve gradual. Developers can ramp up by<br>
first implementing simple policies such as global weighted vtime scheduling<br>
in only tens of lines of code, and then continue to learn the APIs and<br>
building blocks available with sched_ext as they build more featureful and<br>
complex schedulers.<br>
<br>
Another critical advantage provided by sched_ext is the use of BPF. BPF<br>
provides strong safety guarantees by statically analyzing programs at load<br>
time to ensure that they cannot corrupt or crash the system. sched_ext<br>
guarantees system integrity no matter what BPF scheduler is loaded, and<br>
provides mechanisms to safely disable the current BPF scheduler and migrate<br>
tasks back to a trusted scheduler. For example, we also implement in-kernel<br>
safety mechanisms to guarantee that a misbehaving scheduler cannot<br>
indefinitely starve tasks. BPF also enables sched_ext to significantly improve<br>
iteration speed for running experiments. Loading and unloading a BPF scheduler<br>
is simply a matter of running and terminating a sched_ext binary.<br>
<br>
BPF also provides programs with a rich set of APIs, such as maps, kfuncs,<br>
and BPF helpers. In addition to providing useful building blocks to programs<br>
that run entirely in kernel space (such as many of our example schedulers),<br>
these APIs also allow programs to leverage user space in making scheduling<br>
decisions. Specifically, the Atropos sample scheduler has a relatively<br>
simple weighted vtime or FIFO scheduling layer in BPF, paired with a load<br>
balancing component in userspace written in Rust. As described in more<br>
detail below, we also built a more general user-space scheduling framework<br>
called “rhone” by leveraging various BPF features.<br>
<br>
On the other hand, BPF does have shortcomings, as can be plainly seen from<br>
the complexity in some of the example schedulers. scx_pair.bpf.c illustrates<br>
this point well. To start, it requires a good amount of code to emulate<br>
cgroup-local-storage. In the kernel proper, this would simply be a matter of<br>
adding another pointer to the struct cgroup, but in BPF, it requires a<br>
complex juggling of data amongst multiple different maps, a good amount of<br>
boilerplate code, and some unwieldy bpf_loop()‘s and atomics. The code is<br>
also littered with explicit and often unnecessary sanity checks to appease<br>
the verifier.<br>
<br>
That being said, BPF is being rapidly improved. For example, Yonghong Song<br>
recently upstreamed a patch set [5] to add a cgroup local storage map type,<br>
allowing scx_pair.bpf.c to be simplified. There are plans to address other<br>
issues as well, such as providing statically-verified locking, and avoiding<br>
the need for unnecessary sanity checks. Addressing these shortcomings is a<br>
high priority for BPF, and as progress continues to be made, we expect most<br>
deficiencies to be addressed in the not-too-distant future.<br>
<br>
[5]: <a href="https://lore.kernel.org/bpf/20221026042835.672317-1-yhs@fb.com/" rel="noreferrer noreferrer" target="_blank">https://lore.kernel.org/bpf/20221026042835.672317-1-yhs@fb.com/</a><br>
<br>
Yet another exploration advantage of sched_ext is helping widening the scope<br>
of experiments. For example, sched_ext makes it easy to defer CPU assignment<br>
until a task starts executing, allowing schedulers to share scheduling queues<br>
at any granularity (hyper-twin, CCX and so on). Additionally, higher level<br>
frameworks can be built on top to further widen the scope. For example, the<br>
aforementioned “rhone” [6] library allows implementing scheduling policies in<br>
user-space by encapsulating the complexity around communicating scheduling<br>
decisions with the kernel. This allows taking advantage of a richer<br>
programming environment in user-space, enabling experimenting with, for<br>
instance, more complex mathematical models.<br>
<br>
[6]: <a href="https://github.com/Decave/rhone" rel="noreferrer noreferrer" target="_blank">https://github.com/Decave/rhone</a><br>
<br>
sched_ext also allows developers to leverage machine learning. At Meta, we<br>
experimented with using machine learning to predict whether a running task<br>
would soon yield its CPU. These predictions can be used to aid the scheduler<br>
in deciding whether to keep a runnable task on its current CPU rather than<br>
migrating it to an idle CPU, with the hope of avoiding unnecessary cache<br>
misses. Using a tiny neural net model with only one hidden layer of size 16,<br>
and a decaying count of 64 syscalls as a feature, we were able to achieve a<br>
15% throughput improvement on an Nginx benchmark, with an 87% inference<br>
accuracy.<br>
<br>
2. Customization<br>
<br>
This section discusses how sched_ext can enable users to run workloads on<br>
application-specific schedulers.<br>
<br>
*Why deploy custom schedulers rather than improving CFS?*<br>
<br>
Implementing application-specific schedulers and improving CFS are not<br>
conflicting goals. Scheduling features explored with sched_ext which yield<br>
beneficial results, and which are sufficiently generalizable, can and should<br>
be integrated into CFS. However, CFS is fundamentally designed to be a general<br>
purpose scheduler, and thus is not conducive to being extended with some<br>
highly targeted application or hardware specific changes.<br>
<br>
Targeted, bespoke scheduling has many potential use cases. For example, VM<br>
scheduling can make certain optimizations that are infeasible in CFS due to<br>
the constrained problem space (scheduling a static number of long-running<br>
VCPUs versus an arbitrary number of threads). Additionally, certain<br>
applications might want to make targeted policy decisions based on hints<br>
directly from the application (for example, a service that knows the different<br>
deadlines of incoming RPCs).<br>
<br>
Google has also experimented with some promising, novel scheduling policies.<br>
One example is “central” scheduling, wherein a single CPU makes all<br>
scheduling decisions for the entire system. This allows most cores on the<br>
system to be fully dedicated to running workloads, and can have significant<br>
performance improvements for certain use cases. For example, central<br>
scheduling with VCPUs can avoid expensive vmexits and cache flushes, by<br>
instead delegating the responsibility of preemption checks from the tick to<br>
a single CPU. See scx_central.bpf.c for a simple example of a central<br>
scheduling policy built in sched_ext.<br>
<br>
Some workloads also have non-generalizable constraints which enable<br>
optimizations in a scheduling policy which would otherwise not be feasible.<br>
For example,VM workloads at Google typically have a low overcommit ratio<br>
compared to the number of physical CPUs. This allows the scheduler to support<br>
bounded tail latencies, as well as longer blocks of uninterrupted time.<br>
<br>
Yet another interesting use case is the scx_flatcg scheduler, which is in<br>
0024-sched_ext-Add-cgroup-support.patch and provides a flattened<br>
hierarchical vtree for cgroups. This scheduler does not account for<br>
thundering herd problems among cgroups, and therefore may not be suitable<br>
for inclusion in CFS. However, in a simple benchmark using wrk[8] on apache<br>
serving a CGI script calculating sha1sum of a small file, it outperformed<br>
CFS by ~3% with CPU controller disabled and by ~10% with two apache<br>
instances competing with 2:1 weight ratio nested four level deep.<br>
<br>
[7] <a href="https://github.com/wg/wrk" rel="noreferrer noreferrer" target="_blank">https://github.com/wg/wrk</a><br>
<br>
Certain industries require specific scheduling behaviors that do not apply<br>
broadly. For example, ARINC 653 defines scheduling behavior that is widely<br>
used by avionic software, and some out-of-tree implementations<br>
(<a href="https://ieeexplore.ieee.org/document/7005306" rel="noreferrer noreferrer" target="_blank">https://ieeexplore.ieee.org/document/7005306</a>) have been built. While the<br>
upstream community may decide to merge one such implementation in the future,<br>
it would also be entirely reasonable to not do so given the narrowness of<br>
use-case, and non-generalizable, strict requirements. Such cases can be well<br>
served by sched_ext in all stages of the software development lifecycle --<br>
development, testing, deployment and maintenance.<br>
<br>
There are also classes of policy exploration, such as machine learning, or<br>
responding in real-time to application hints, that are significantly harder<br>
(and not necessarily appropriate) to integrate within the kernel itself.<br>
<br>
*Won’t this increase fragmentation?*<br>
<br>
We acknowledge that to some degree, sched_ext does run the risk of<br>
increasing the fragmentation of scheduler implementations. As a result of<br>
exploration, however, we believe that enabling the larger ecosystem to<br>
innovate will ultimately accelerate the overall development and performance<br>
of Linux.<br>
<br>
BPF programs are required to be GPLv2, which is enforced by the verifier on<br>
program loads. With regards to API stability, just as with other semi-internal<br>
interfaces such as BPF kfuncs, we won’t be providing any API stability<br>
guarantees to BPF schedulers. While we intend to make an effort to provide<br>
compatibility when possible, we will not provide any explicit, strong<br>
guarantees as the kernel typically does with e.g. UAPI headers. For users who<br>
decide to keep their schedulers out-of-tree,the licensing and maintenance<br>
overheads will be fundamentally the same as for carrying out-of-tree patches.<br>
<br>
With regards to the schedulers included in this patch set, and any other<br>
schedulers we implement in the future, both Meta and Google will open-source<br>
all of the schedulers we implement which have any relevance to the broader<br>
upstream community. We expect that some of these, such as the simple example<br>
schedulers and scx_rusty scheduler, will be upstreamed as part of the kernel<br>
tree. Distros will be able to package and release these schedulers with the<br>
kernel, allowing users to utilize these schedulers out-of-the-box without<br>
requiring any additional work or dependencies such as clang or building the<br>
scheduler programs themselves. Other schedulers and scheduling frameworks<br>
such as rhone may be open-sourced through separate per-project repos.<br>
<br>
3. Rapid scheduler deployments<br>
<br>
Rolling out kernel upgrades is a slow and iterative process. At a large scale<br>
it can take months to roll a new kernel out to a fleet of servers. While this<br>
latency is expected and inevitable for normal kernel upgrades, it can become<br>
highly problematic when kernel changes are required to fix bugs. Livepatch [8]<br>
is available to quickly roll out critical security fixes to large fleets, but<br>
the scope of changes that can be applied with livepatching is fairly limited,<br>
and would likely not be usable for patching scheduling policies. With<br>
sched_ext, new scheduling policies can be rapidly rolled out to production<br>
environments.<br>
<br>
[8]: <a href="https://www.kernel.org/doc/html/latest/livepatch/livepatch.html" rel="noreferrer noreferrer" target="_blank">https://www.kernel.org/doc/html/latest/livepatch/livepatch.html</a><br>
<br>
As an example, one of the variants of the L1 Terminal Fault (L1TF) [9]<br>
vulnerability allows a VCPU running a VM to read arbitrary host kernel<br>
memory for pages in L1 data cache. The solution was to implement core<br>
scheduling, which ensures that tasks running as hypertwins have the same<br>
“cookie”.<br>
<br>
[9]: <a href="https://www.intel.com/content/www/us/en/architecture-and-technology/l1tf.html" rel="noreferrer noreferrer" target="_blank">https://www.intel.com/content/www/us/en/architecture-and-technology/l1tf.html</a><br>
<br>
While core scheduling works well, it took a long time to finalize and land<br>
upstream. This long rollout period was painful, and required organizations to<br>
make difficult choices amongst a bad set of options. Some companies such as<br>
Google chose to implement and use their own custom L1TF-safe scheduler, others<br>
chose to run without hyper-threading enabled, and yet others left<br>
hyper-threading enabled and crossed their fingers.<br>
<br>
Once core scheduling was upstream, organizations had to upgrade the kernels on<br>
their entire fleets. As downtime is not an option for many, these upgrades had<br>
to be gradually rolled out, which can take a very long time for large fleets.<br>
<br>
An example of an sched_ext scheduler that illustrates core scheduling<br>
semantics is scx_pair.bpf.c, which co-schedules pairs of tasks from the same<br>
cgroup, and is resilient to L1TF vulnerabilities. While this example<br>
scheduler is certainly not suitable for production in its current form, a<br>
similar scheduler that is more performant and featureful could be written<br>
and deployed if necessary.<br>
<br>
Rapid scheduling deployments can similarly be useful to quickly roll-out new<br>
scheduling features without requiring kernel upgrades. At Google, for example,<br>
it was observed that some low-priority workloads were causing degraded<br>
performance for higher-priority workloads due to consuming a disproportionate<br>
share of memory bandwidth. While a temporary mitigation was to use sched<br>
affinity to limit the footprint of this low-priority workload to a small<br>
subset of CPUs, a preferable solution would be to implement a more featureful<br>
task-priority mechanism which automatically throttles lower-priority tasks<br>
which are causing memory contention for the rest of the system. Implementing<br>
this in CFS and rolling it out to the fleet could take a very long time.<br>
<br>
sched_ext would directly address these gaps. If another hardware bug or<br>
resource contention issue comes in that requires scheduler support to<br>
mitigate, sched_ext can be used to experiment with and test different<br>
policies. Once a scheduler is available, it can quickly be rolled out to as<br>
many hosts as necessary, and function as a stop-gap solution until a<br>
longer-term mitigation is upstreamed.<br>
<br>
<br>
How<br>
---<br>
<br>
sched_ext is a new sched_class which allows scheduling policies to be<br>
implemented in BPF programs.<br>
<br>
sched_ext leverages BPF’s struct_ops feature to define a structure which<br>
exports function callbacks and flags to BPF programs that wish to implement<br>
scheduling policies. The struct_ops structure exported by sched_ext is struct<br>
sched_ext_ops, and is conceptually similar to struct sched_class. The role of<br>
sched_ext is to map the complex sched_class callbacks to the more simple and<br>
ergonomic struct sched_ext_ops callbacks.<br>
<br>
Unlike some other BPF program types which have ABI requirements due to<br>
exporting UAPIs, struct_ops has no ABI requirements whatsoever. This provides<br>
us with the flexibility to change the APIs provided to schedulers as<br>
necessary. BPF struct_ops is also already being used successfully in other<br>
subsystems, such as in support of TCP congestion control.<br>
<br>
The only struct_ops field that is required to be specified by a scheduler is<br>
the ‘name’ field. Otherwise, sched_ext will provide sane default behavior,<br>
such as automatically choosing an idle CPU on the task wakeup path if<br>
.select_cpu() is missing.<br>
<br>
*Dispatch queues*<br>
<br>
To bridge the workflow imbalance between the scheduler core and sched_ext_ops<br>
callbacks, sched_ext uses simple FIFOs called dispatch queues (dsq's). By<br>
default, there is one global dsq (SCX_DSQ_GLOBAL), and one local per-CPU dsq<br>
(SCX_DSQ_LOCAL). SCX_DSQ_GLOBAL is provided for convenience and need not be<br>
used by a scheduler that doesn't require it. As described in more detail<br>
below, SCX_DSQ_LOCAL is the per-CPU FIFO that sched_ext pulls from when<br>
putting the next task on the CPU. The BPF scheduler can manage an arbitrary<br>
number of dsq's using scx_bpf_create_dsq() and scx_bpf_destroy_dsq().<br>
<br>
*Scheduling cycle*<br>
<br>
The following briefly shows a typical workflow for how a waking task is<br>
scheduled and executed.<br>
<br>
1. When a task is waking up, .select_cpu() is the first operation invoked.<br>
This serves two purposes. It both allows a scheduler to optimize task<br>
placement by specifying a CPU where it expects the task to eventually be<br>
scheduled, and the latter is that the selected CPU will be woken if it’s<br>
idle.<br>
<br>
2. Once the target CPU is selected, .enqueue() is invoked. It can make one of<br>
the following decisions:<br>
<br>
- Immediately dispatch the task to either the global dsq (SCX_DSQ_GLOBAL)<br>
or the current CPU’s local dsq (SCX_DSQ_LOCAL).<br>
<br>
- Immediately dispatch the task to a user-created dispatch queue.<br>
<br>
- Queue the task on the BPF side, e.g. in an rbtree map for a vruntime<br>
scheduler, with the intention of dispatching it at a later time from<br>
.dispatch().<br>
<br>
3. When a CPU is ready to schedule, it first looks at its local dsq. If empty,<br>
it invokes .consume() which should make one or more scx_bpf_consume() calls<br>
to consume tasks from dsq's. If a scx_bpf_consume() call succeeds, the CPU<br>
has the next task to run and .consume() can return. If .consume() is not<br>
defined, sched_ext will by-default consume from only the built-in<br>
SCX_DSQ_GLOBAL dsq.<br>
<br>
4. If there's still no task to run, .dispatch() is invoked which should make<br>
one or more scx_bpf_dispatch() calls to dispatch tasks from the BPF<br>
scheduler to one of the dsq's. If more than one task has been dispatched,<br>
go back to the previous consumption step.<br>
<br>
*Verifying callback behavior*<br>
<br>
sched_ext always verifies that any value returned from a callback is valid,<br>
and will issue an error and unload the scheduler if it is not. For example, if<br>
.select_cpu() returns an invalid CPU, or if an attempt is made to invoke the<br>
scx_bpf_dispatch() with invalid enqueue flags. Furthermore, if a task remains<br>
runnable for too long without being scheduled, sched_ext will detect it and<br>
error-out the scheduler.<br>
<br>
<br>
Closing Thoughts<br>
----------------<br>
<br>
Both Meta and Google have experimented quite a lot with schedulers in the<br>
last several years. Google has benchmarked various workloads using user<br>
space scheduling, and have achieved performance wins by trading off<br>
generality for application specific needs. At Meta, we are actively<br>
experimenting with multiple production workloads and seeing significant<br>
performance gains, and are in the process of deploying sched_ext schedulers<br>
on production workloads at scale. We expect to leverage it extensively to<br>
run various experiments and develop customized schedulers for a number of<br>
critical workloads.<br>
<br>
In closing, both Meta and Google believe that sched_ext will significantly<br>
evolve how the broader community explores the scheduling problem space,<br>
while also enabling targeted policies for custom applications. We’ll be able<br>
to experiment easier and faster, explore uncharted areas, and deploy<br>
emergency scheduler changes when necessary. The same applies to anyone who<br>
wants to work on the scheduler, including academia and specialized<br>
industries. sched_ext will push forward the state of the art when it comes<br>
to scheduling and performance in Linux.<br>
<br>
<br>
Written By<br>
----------<br>
<br>
David Vernet <<a href="mailto:dvernet@meta.com" target="_blank" rel="noreferrer">dvernet@meta.com</a>><br>
Josh Don <<a href="mailto:joshdon@google.com" target="_blank" rel="noreferrer">joshdon@google.com</a>><br>
Tejun Heo <<a href="mailto:tj@kernel.org" target="_blank" rel="noreferrer">tj@kernel.org</a>><br>
Barret Rhoden <<a href="mailto:brho@google.com" target="_blank" rel="noreferrer">brho@google.com</a>><br>
<br>
<br>
Supported By<br>
------------<br>
<br>
Paul Turner <<a href="mailto:pjt@google.com" target="_blank" rel="noreferrer">pjt@google.com</a>><br>
Neel Natu <<a href="mailto:neelnatu@google.com" target="_blank" rel="noreferrer">neelnatu@google.com</a>><br>
Patrick Bellasi <<a href="mailto:derkling@google.com" target="_blank" rel="noreferrer">derkling@google.com</a>><br>
Hao Luo <<a href="mailto:haoluo@google.com" target="_blank" rel="noreferrer">haoluo@google.com</a>><br>
Dimitrios Skarlatos <<a href="mailto:dskarlat@cs.cmu.edu" target="_blank" rel="noreferrer">dskarlat@cs.cmu.edu</a>><br>
<br>
<br>
Patchset<br>
--------<br>
<br>
This patchset is on top of bpf/for-next as of 2024-04-29:<br>
<br>
07801a24e2f1 ("bpf, docs: Clarify PC use in instruction-set.rst")<br>
<br>
and contains the following patches:<br>
<br>
NOTE: The doc added by 0038 contains a high-level overview and might be good<br>
place to start.<br>
<br>
0001-cgroup-Implement-cgroup_show_cftypes.patch<br>
0002-sched-Restructure-sched_class-order-sanity-checks-in.patch<br>
0003-sched-Allow-sched_cgroup_fork-to-fail-and-introduce-.patch<br>
0004-sched-Add-sched_class-reweight_task.patch<br>
0005-sched-Add-sched_class-switching_to-and-expose-check_.patch<br>
0006-sched-Factor-out-cgroup-weight-conversion-functions.patch<br>
0007-sched-Expose-css_tg-and-__setscheduler_prio.patch<br>
0008-sched-Enumerate-CPU-cgroup-file-types.patch<br>
0009-sched-Add-reason-to-sched_class-rq_-on-off-line.patch<br>
0010-sched-Factor-out-update_other_load_avgs-from-__updat.patch<br>
0011-cpufreq_schedutil-Refactor-sugov_cpu_is_busy.patch<br>
0012-sched-Add-normal_policy.patch<br>
0013-sched_ext-Add-boilerplate-for-extensible-scheduler-c.patch<br>
0014-sched_ext-Implement-BPF-extensible-scheduler-class.patch<br>
0015-sched_ext-Add-scx_simple-and-scx_example_qmap-exampl.patch<br>
0016-sched_ext-Add-sysrq-S-which-disables-the-BPF-schedul.patch<br>
0017-sched_ext-Implement-runnable-task-stall-watchdog.patch<br>
0018-sched_ext-Allow-BPF-schedulers-to-disallow-specific-.patch<br>
0019-sched_ext-Print-sched_ext-info-when-dumping-stack.patch<br>
0020-sched_ext-Print-debug-dump-after-an-error-exit.patch<br>
0021-tools-sched_ext-Add-scx_show_state.py.patch<br>
0022-sched_ext-Implement-scx_bpf_kick_cpu-and-task-preemp.patch<br>
0023-sched_ext-Add-a-central-scheduler-which-makes-all-sc.patch<br>
0024-sched_ext-Make-watchdog-handle-ops.dispatch-looping-.patch<br>
0025-sched_ext-Add-task-state-tracking-operations.patch<br>
0026-sched_ext-Implement-tickless-support.patch<br>
0027-sched_ext-Track-tasks-that-are-subjects-of-the-in-fl.patch<br>
0028-sched_ext-Add-cgroup-support.patch<br>
0029-sched_ext-Add-a-cgroup-scheduler-which-uses-flattene.patch<br>
0030-sched_ext-Implement-SCX_KICK_WAIT.patch<br>
0031-sched_ext-Implement-sched_ext_ops.cpu_acquire-releas.patch<br>
0032-sched_ext-Implement-sched_ext_ops.cpu_online-offline.patch<br>
0033-sched_ext-Bypass-BPF-scheduler-while-PM-events-are-i.patch<br>
0034-sched_ext-Implement-core-sched-support.patch<br>
0035-sched_ext-Add-vtime-ordered-priority-queue-to-dispat.patch<br>
0036-sched_ext-Implement-DSQ-iterator.patch<br>
0037-sched_ext-Add-cpuperf-support.patch<br>
0038-sched_ext-Documentation-scheduler-Document-extensibl.patch<br>
0039-sched_ext-Add-selftests.patch<br>
<br>
0001 : Cgroup prep.<br>
<br>
0002-0012: Scheduler prep.<br>
<br>
0013-0015: sched_ext core implementation and a couple example BPF scheduler.<br>
<br>
0016-0021: Utility features including safety mechanisms, switch-all and<br>
printing sched_ext state when dumping backtraces.<br>
<br>
0022-0027: Kicking and preempting other CPUs, task state transition tracking<br>
and tickless support. Demonstrated with an example central<br>
scheduler which makes all scheduling decisions on one CPU.<br>
<br>
0029-0030: cgroup support and the ability to wait for other CPUs after<br>
kicking them.<br>
<br>
0031-0033: Add CPU preemption and hotplug and power-management support.<br>
<br>
0034 : Add core-sched support.<br>
<br>
0035-0036: Add DSQ rbtree and iterator support.<br>
<br>
0037 : Add cpuperf (frequency scaling) support.<br>
<br>
0038 : Add documentation.<br>
<br>
0039 : Add selftests.<br>
<br>
The patchset is also available in the following git branch:<br>
<br>
git://<a href="http://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git" rel="noreferrer noreferrer" target="_blank">git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git</a> sched_ext-v6<br>
<br>
diffstat follows.<br>
<br>
Documentation/scheduler/index.rst | 1<br>
Documentation/scheduler/sched-ext.rst | 307 +<br>
MAINTAINERS | 13<br>
Makefile | 8<br>
drivers/tty/sysrq.c | 1<br>
include/asm-generic/vmlinux.lds.h | 1<br>
include/linux/cgroup-defs.h | 8<br>
include/linux/cgroup.h | 5<br>
include/linux/sched.h | 5<br>
include/linux/sched/ext.h | 210<br>
include/linux/sched/task.h | 3<br>
include/uapi/linux/sched.h | 1<br>
init/Kconfig | 5<br>
init/init_task.c | 12<br>
kernel/Kconfig.preempt | 24<br>
kernel/cgroup/cgroup.c | 97<br>
kernel/fork.c | 17<br>
kernel/sched/build_policy.c | 8<br>
kernel/sched/core.c | 324 +<br>
kernel/sched/cpufreq_schedutil.c | 50<br>
kernel/sched/deadline.c | 4<br>
kernel/sched/debug.c | 3<br>
kernel/sched/ext.c | 6641 +++++++++++++++++++++++++++++++<br>
kernel/sched/ext.h | 139<br>
kernel/sched/fair.c | 25<br>
kernel/sched/idle.c | 2<br>
kernel/sched/rt.c | 4<br>
kernel/sched/sched.h | 123<br>
kernel/sched/topology.c | 4<br>
lib/dump_stack.c | 1<br>
tools/Makefile | 10<br>
tools/sched_ext/.gitignore | 2<br>
tools/sched_ext/Makefile | 246 +<br>
tools/sched_ext/README.md | 270 +<br>
tools/sched_ext/include/bpf-compat/gnu/stubs.h | 11<br>
tools/sched_ext/include/scx/common.bpf.h | 301 +<br>
tools/sched_ext/include/scx/common.h | 71<br>
tools/sched_ext/include/scx/compat.bpf.h | 110<br>
tools/sched_ext/include/scx/compat.h | 197<br>
tools/sched_ext/include/scx/user_exit_info.h | 111<br>
tools/sched_ext/scx_central.bpf.c | 361 +<br>
tools/sched_ext/scx_central.c | 135<br>
tools/sched_ext/scx_flatcg.bpf.c | 939 ++++<br>
tools/sched_ext/scx_flatcg.c | 233 +<br>
tools/sched_ext/scx_flatcg.h | 51<br>
tools/sched_ext/scx_qmap.bpf.c | 673 +++<br>
tools/sched_ext/scx_qmap.c | 150<br>
tools/sched_ext/scx_show_state.py | 39<br>
tools/sched_ext/scx_simple.bpf.c | 149<br>
tools/sched_ext/scx_simple.c | 107<br>
tools/testing/selftests/sched_ext/.gitignore | 6<br>
tools/testing/selftests/sched_ext/Makefile | 216 +<br>
tools/testing/selftests/sched_ext/config | 9<br>
tools/testing/selftests/sched_ext/ddsp_bogus_dsq_fail.bpf.c | 42<br>
tools/testing/selftests/sched_ext/ddsp_bogus_dsq_fail.c | 57<br>
tools/testing/selftests/sched_ext/ddsp_vtimelocal_fail.bpf.c | 39<br>
tools/testing/selftests/sched_ext/ddsp_vtimelocal_fail.c | 56<br>
tools/testing/selftests/sched_ext/enq_last_no_enq_fails.bpf.c | 21<br>
tools/testing/selftests/sched_ext/enq_last_no_enq_fails.c | 60<br>
tools/testing/selftests/sched_ext/enq_select_cpu_fails.bpf.c | 43<br>
tools/testing/selftests/sched_ext/enq_select_cpu_fails.c | 61<br>
tools/testing/selftests/sched_ext/exit.bpf.c | 84<br>
tools/testing/selftests/sched_ext/exit.c | 55<br>
tools/testing/selftests/sched_ext/exit_test.h | 20<br>
tools/testing/selftests/sched_ext/hotplug.bpf.c | 55<br>
tools/testing/selftests/sched_ext/hotplug.c | 168<br>
tools/testing/selftests/sched_ext/hotplug_test.h | 15<br>
tools/testing/selftests/sched_ext/init_enable_count.bpf.c | 53<br>
tools/testing/selftests/sched_ext/init_enable_count.c | 166<br>
tools/testing/selftests/sched_ext/maximal.bpf.c | 164<br>
tools/testing/selftests/sched_ext/maximal.c | 51<br>
tools/testing/selftests/sched_ext/maybe_null.bpf.c | 26<br>
tools/testing/selftests/sched_ext/maybe_null.c | 40<br>
tools/testing/selftests/sched_ext/maybe_null_fail.bpf.c | 25<br>
tools/testing/selftests/sched_ext/minimal.bpf.c | 21<br>
tools/testing/selftests/sched_ext/minimal.c | 58<br>
tools/testing/selftests/sched_ext/prog_run.bpf.c | 32<br>
tools/testing/selftests/sched_ext/prog_run.c | 78<br>
tools/testing/selftests/sched_ext/reload_loop.c | 75<br>
tools/testing/selftests/sched_ext/runner.c | 201<br>
tools/testing/selftests/sched_ext/scx_test.h | 131<br>
tools/testing/selftests/sched_ext/select_cpu_dfl.bpf.c | 40<br>
tools/testing/selftests/sched_ext/select_cpu_dfl.c | 72<br>
tools/testing/selftests/sched_ext/select_cpu_dfl_nodispatch.bpf.c | 89<br>
tools/testing/selftests/sched_ext/select_cpu_dfl_nodispatch.c | 72<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch.bpf.c | 41<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch.c | 70<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch_bad_dsq.bpf.c | 37<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch_bad_dsq.c | 56<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch_dbl_dsp.bpf.c | 38<br>
tools/testing/selftests/sched_ext/select_cpu_dispatch_dbl_dsp.c | 56<br>
tools/testing/selftests/sched_ext/select_cpu_vtime.bpf.c | 92<br>
tools/testing/selftests/sched_ext/select_cpu_vtime.c | 59<br>
tools/testing/selftests/sched_ext/test_example.c | 49<br>
tools/testing/selftests/sched_ext/util.c | 71<br>
tools/testing/selftests/sched_ext/util.h | 13<br>
96 files changed, 15056 insertions(+), 139 deletions(-)<br>
<br>
<br>
Patchset History<br>
----------------<br>
<br>
v4 (<a href="http://lkml.kernel.org/r/20230711011412.100319-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">http://lkml.kernel.org/r/20230711011412.100319-1-tj@kernel.org</a>) -> v5:<br>
<br>
- Updated to rebase on top of the current bpf/for-next (2023-11-06).<br>
'0002-0010: Scheduler prep' were simply rebased on top of new EEVDF<br>
scheduler which demonstrate clean cut API boundary between sched-ext and<br>
sched core.<br>
<br>
- To accommodate 32bit configs, fields which use atomic ops and<br>
store_release/load_acquire are switched from 64bits to longs.<br>
<br>
- To help triaging, if sched_ext is enabled, backtrace dumps now show the<br>
currently active scheduler along with some debug information.<br>
<br>
- Fixes for bugs including p->scx.flags corruption due to unsynchronized<br>
SCX_TASK_DSQ_ON_PRIQ changes, and overly permissive BTF struct and scx_bpf<br>
kfunc access checks.<br>
<br>
- Other misc changes including renaming "type" to "kind" in scx_exit_info to<br>
ease usage from rust and other languages in which "type" is a reserved<br>
keyword.<br>
<br>
- scx_atropos is renamed to scx_rusty and received signficant updates to<br>
improve scalability. Load metrics are now tracked in BPF and accessed only<br>
as necessary from userspace.<br>
<br>
- Misc example scheduler improvements including the usage of resizable BPF<br>
.bss array, the introduction of SCX_BUG[_ON](), and timer CPU pinning in<br>
scx_central.<br>
<br>
- Improve Makefile and documentation for example schedulers.<br>
<br>
v3 (<a href="https://lkml.kernel.org/r/20230317213333.2174969-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">https://lkml.kernel.org/r/20230317213333.2174969-1-tj@kernel.org</a>) -> v4:<br>
<br>
- There aren't any significant changes to the sched_ext API even though we<br>
kept experimenting heavily with a couple BPF scheduler implementations<br>
indicating that the core API reached a level of maturity.<br>
<br>
- 0002-sched-Encapsulate-task-attribute-change-sequence-int.patch which<br>
implemented custom guard scope for scheduler attribute changes dropped as<br>
upstream is moving towards a more generic implementation.<br>
<br>
- Build fixes with different CONFIG combinations.<br>
<br>
- Core code cleanups and improvements including how idle CPU is selected and<br>
disabling ttwu_queue for tasks on SCX to avoid confusing BPF schedulers<br>
expecting ->select_cpu() call. See<br>
0012-sched_ext-Implement-BPF-extensible-scheduler-class.patch for more<br>
details.<br>
<br>
- "_example" dropped from the example schedulers as the distinction between<br>
the example-only and practically-useful isn't black-and-white. Instead,<br>
each scheduler has detailed comments and there's also a README file.<br>
<br>
- scx_central, scx_pair and scx_flatcg are moved into their own patches as<br>
suggested by Josh Don.<br>
<br>
- scx_atropos received sustantial updates including fixes for bugs that<br>
could cause temporary stalls and improvements in load balancing and wakeup<br>
target CPU selection. For details, See<br>
0034-sched_ext-Add-a-rust-userspace-hybrid-example-schedu.patch.<br>
<br>
v2 (<a href="http://lkml.kernel.org/r/20230128001639.3510083-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">http://lkml.kernel.org/r/20230128001639.3510083-1-tj@kernel.org</a>) -> v3:<br>
<br>
- ops.set_weight() added to allow BPF schedulers to track weight changes<br>
without polling p->scx.weight.<br>
<br>
- scx_bpf_task_cgroup() kfunc added to allow BPF scheduler to reliably<br>
determine the current cpu cgroup under rq lock protection. This required<br>
improving the kf_mask SCX operation verification mechanism and adding<br>
0023-sched_ext-Track-tasks-that-are-subjects-of-the-in-fl.patch.<br>
<br>
- Updated to use the latest BPF improvements including KF_RCU and the inline<br>
iterator.<br>
<br>
- scx_example_flatcg added to 0024-sched_ext-Add-cgroup-support.patch. It<br>
uses the new BPF RB tree support to implement flattened cgroup hierarchy.<br>
<br>
- A DSQ now also contains an rbtree so that it can be used to implement<br>
vtime based scheduling among tasks sharing a DSQ conveniently and<br>
efficiently. For more details, see<br>
0029-sched_ext-Add-vtime-ordered-priority-queue-to-dispat.patch. All<br>
eligible example schedulers are updated to default to weighted vtime<br>
scheduilng.<br>
<br>
- atropos scheduler's userspace code is substantially restructred and<br>
rewritten. The binary is renamed to scx_atropos and can auto-config the<br>
domains according to the cache topology.<br>
<br>
- Various other example scheduler updates including scx_example_dummy being<br>
renamed to scx_example_simple, the example schedulers defaulting to<br>
enabling switch_all and clarifying performance expectation of each example<br>
scheduler.<br>
<br>
- A bunch of fixes and improvements. Please refer to each patch for details.<br>
<br>
v1 (<a href="http://lkml.kernel.org/r/20221130082313.3241517-1-tj@kernel.org" rel="noreferrer noreferrer" target="_blank">http://lkml.kernel.org/r/20221130082313.3241517-1-tj@kernel.org</a>) -> v2:<br>
<br>
- Rebased on top of bpf/for-next - a5f6b9d577eb ("Merge branch 'Enable<br>
struct_ops programs to be sleepable'"). There were several missing<br>
features including generic cpumask helpers and sleepable struct_ops<br>
operation support that v1 was working around. The rebase gets rid of all<br>
SCX specific temporary helpers.<br>
<br>
- Some kfunc helpers are context-sensitive and can only be called from<br>
specific operations. v1 didn't restrict kfunc accesses allowing them to be<br>
misused which can lead to crashes and other malfunctions. v2 makes more<br>
kfuncs safe to be called from anywhere and implements per-task mask based<br>
runtime access control for the rest. The longer-term plan is to make the<br>
BPF verifier enforce these restrictions. Combined with the above, sans<br>
mistakes and bugs, it shouldn't be possible to crash the machine through<br>
SCX and its helpers.<br>
<br>
- Core-sched support. While v1 implemented the pick_task operation, there<br>
were multiple missing pieces for working core-sched support. v2 adds<br>
0027-sched_ext-Implement-core-sched-support.patch. SCX by default<br>
implements global FIFO ordering and allows the BPF schedulers to implement<br>
custom ordering via scx_ops.core_sched_before(). scx_example_qmap is<br>
updated so that the five queues' relative priorities are correctly<br>
reflected when core-sched is enabled.<br>
<br>
- Dropped balance_scx_on_up() which was called from put_prev_task_balance().<br>
UP support is now contained in SCX proper.<br>
<br>
- 0002-sched-Encapsulate-task-attribute-change-sequence-int.patch adds<br>
SCHED_CHANGE_BLOCK() which encapsulates the preparation and restoration<br>
sequences used for task attribute changes. For SCX, this replaces<br>
sched_deq_and_put_task() and sched_enq_and_set_task() from v1.<br>
<br>
- 0011-sched-Add-reason-to-sched_move_task.patch dropped from v1. SCX now<br>
distinguishes cgroup and autogroup tg's using task_group_is_autogroup().<br>
<br>
- Other misc changes including fixes for bugs that Julia Lawall noticed and<br>
patch descriptions updates with more details on how the introduced changes<br>
are going to be used.<br>
<br>
- MAINTAINERS entries added.<br>
<br>
The followings are discussion points which were raised but didn't result in<br>
code changes in this iteration.<br>
<br>
- There were discussions around exposing __setscheduler_prio() and, in v2,<br>
SCHED_CHANGE_BLOCK() in kernel/sched/sched.h. Switching scheduler<br>
implementations is innate for SCX. At the very least, it needs to be able<br>
to turn on and off the BPF scheduler which requires something equivalent<br>
to SCHED_CHANGE_BLOCK(). The use of __setscheduler_prio() depends on the<br>
behavior we want to present to userspace. The current one of using CFS as<br>
the fallback when BPF scheduler is not available seems more friendly and<br>
less error-prone to other options.<br>
<br>
- Another discussion point was around for_each_active_class() and friends<br>
which skip over CFS or SCX when it's known that the sched_class must be<br>
empty. I left it as-is for now as it seems to be cleaner and more robust<br>
than trying to plug each operation which may added unnecessary overheads.<br>
<br>
Thanks.<br>
<br>
--<br>
tejun<br>
<br>
</div>