[28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst

Message ID	20221130082313.3241517-29-tj@kernel.org (mailing list archive)
State	RFC
Delegated to:	BPF
Headers	show Return-Path: <bpf-owner@kernel.org> Sender: Tejun Heo <htejun@gmail.com> From: Tejun Heo <tj@kernel.org> To: torvalds@linux-foundation.org, mingo@redhat.com, peterz@infradead.org, juri.lelli@redhat.com, vincent.guittot@linaro.org, dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de, bristot@redhat.com, vschneid@redhat.com, ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org, martin.lau@kernel.org, joshdon@google.com, brho@google.com, pjt@google.com, derkling@google.com, haoluo@google.com, dvernet@meta.com, dschatzberg@meta.com, dskarlat@cs.cmu.edu, riel@surriel.com Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, kernel-team@meta.com, Tejun Heo <tj@kernel.org> Subject: [PATCH 28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst Date: Tue, 29 Nov 2022 22:23:10 -1000 Message-Id: <20221130082313.3241517-29-tj@kernel.org> In-Reply-To: <20221130082313.3241517-1-tj@kernel.org> References: <20221130082313.3241517-1-tj@kernel.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Precedence: bulk
Series	[01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts \| expand [01/31] rhashtable: Allow rhashtable to be used from irq-safe contexts [02/31] cgroup: Implement cgroup_show_cftypes() [03/31] BPF: Add @prog to bpf_struct_ops->check_member() [04/31] sched: Allow sched_cgroup_fork() to fail and introduce sched_cancel_fork() [05/31] sched: Add sched_class->reweight_task() [06/31] sched: Add sched_class->switching_to() and expose check_class_changing/changed() [07/31] sched: Factor out cgroup weight conversion functions [08/31] sched: Expose css_tg() and __setscheduler_prio() in kernel/sched/sched.h [09/31] sched: Enumerate CPU cgroup file types [10/31] sched: Add @reason to sched_class->rq_{on\|off}line() [11/31] sched: Add @reason to sched_move_task() [12/31] sched: Add normal_policy() [13/31] sched_ext: Add boilerplate for extensible scheduler class [15/31] sched_ext: [TEMPORARY] Add temporary workaround kfunc helpers [16/31] sched_ext: Add scx_example_dummy and scx_example_qmap example schedulers [17/31] sched_ext: Add sysrq-S which disables the BPF scheduler [18/31] sched_ext: Implement runnable task stall watchdog [19/31] sched_ext: Allow BPF schedulers to disallow specific tasks from joining SCHED_EXT [20/31] sched_ext: Allow BPF schedulers to switch all eligible tasks into sched_ext [21/31] sched_ext: Implement scx_bpf_kick_cpu() and task preemption support [22/31] sched_ext: Add task state tracking operations [23/31] sched_ext: Implement tickless support [24/31] sched_ext: Add cgroup support [25/31] sched_ext: Implement SCX_KICK_WAIT [26/31] sched_ext: Implement sched_ext_ops.cpu_acquire/release() [27/31] sched_ext: Implement sched_ext_ops.cpu_online/offline() [28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst [29/31] sched_ext: Add a basic, userland vruntime scheduler [30/31] BPF: [TEMPORARY] Nerf BTF scalar value check [31/31] sched_ext: Add a rust userspace hybrid example scheduler

Context	Check	Description
bpf/vmtest-bpf-PR	fail	merge-conflict

Hello, On Mon, Dec 12, 2022 at 01:39:04PM +0100, Peter Zijlstra wrote: > On Tue, Nov 29, 2022 at 10:23:10PM -1000, Tejun Heo wrote: > > If you expect me to read this, please as to provide something readable, > not markup gibberish. Hmmm... Everything under Documentation/scheduler is in rst markup. I don't care about the file format. If plain text is preferable, that's fine but that'd look odd in that directory. For your reading convenience, the following is the formatted output: https://github.com/htejun/sched_ext/blob/sched_ext/Documentation/scheduler/sched-ext.rst and the following is the plain text version with markups stripped out. FWIW, while the double-backtick quoting is a bit distracting, there aren't whole lot of markups to strip out. ========================== Extensible Scheduler Class ========================== sched_ext is a scheduler class whose behavior can be defined by a set of BPF programs - the BPF scheduler. * sched_ext exports a full scheduling interface so that any scheduling algorithm can be implemented on top. * The BPF scheduler can group CPUs however it sees fit and schedule them together, as tasks aren't tied to specific CPUs at the time of wakeup. * The BPF scheduler can be turned on and off dynamically anytime. * The system integrity is maintained no matter what the BPF scheduler does. The default scheduling behavior is restored anytime an error is detected, a runnable task stalls, or on invoking SysRq key sequence like `SysRq-s`. Switching to and from sched_ext =============================== CONFIG_SCHED_CLASS_EXT is the config option to enable sched_ext and tools/sched_ext contains the example schedulers. sched_ext is used only when the BPF scheduler is loaded and running. If a task explicitly sets its scheduling policy to SCHED_EXT, it will be treated as SCHED_NORMAL and scheduled by CFS until the BPF scheduler is loaded. On load, such tasks will be switched to and scheduled by sched_ext. The BPF scheduler can choose to schedule all normal and lower class tasks by calling scx_bpf_switch_all() from its init() operation. In this case, all SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE and SCHED_EXT tasks are scheduled by sched_ext. In the example schedulers, this mode can be selected with the -a option. Terminating the sched_ext scheduler program, triggering SysRq key, or detection of any internal error including stalled runnable tasks aborts the BPF scheduler and reverts all tasks back to CFS. # make -j16 -C tools/sched_ext # tools/sched_ext/scx_example_dummy -a local=0 global=3 local=5 global=24 local=9 global=44 local=13 global=56 local=17 global=72 ^CEXIT: BPF scheduler 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: # cat /sys/kernel/debug/sched/ext ops : dummy enabled : 1 switching_all : 1 switched_all : 1 enable_state : enabled # grep ext /proc/self/sched ext.enabled : 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_dummy.bpf.c showing a minimal global FIFO scheduler. s32 BPF_STRUCT_OPS(dummy_init) { if (switch_all) scx_bpf_switch_all(); return 0; } void BPF_STRUCT_OPS(dummy_enqueue, struct task_struct *p, u64 enq_flags) { if (enq_flags & SCX_ENQ_LOCAL) scx_bpf_dispatch(p, SCX_DSQ_LOCAL, enq_flags); else scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, enq_flags); } void BPF_STRUCT_OPS(dummy_exit, struct scx_exit_info *ei) { exit_type = ei->type; } SEC(".struct_ops") struct sched_ext_ops dummy_ops = { .enqueue = (void *)dummy_enqueue, .init = (void *)dummy_init, .exit = (void *)dummy_exit, .name = "dummy", }; Dispatch Queues --------------- To match the impedance between the scheduler core and the BPF scheduler, sched_ext uses simple FIFOs called DSQs (dispatch queues). By default, there is one global FIFO (SCX_DSQ_GLOBAL), and one local dsq per CPU (SCX_DSQ_LOCAL). The BPF scheduler can manage an arbitrary number of dsq's using scx_bpf_create_dsq() and scx_bpf_destroy_dsq(). A CPU always executes a task from its local DSQ. A task is "dispatched" to a DSQ. A non-local DSQ is "consumed" to transfer a task to the consuming CPU's local DSQ. When a CPU is looking for the next task to run, if the local DSQ is not empty, the first task is picked. Otherwise, the CPU tries to consume the global DSQ. If that doesn't yield a runnable task either, ops.dispatch() is invoked. Scheduling Cycle ---------------- The following briefly shows how a waking task is scheduled and executed. 1. When a task is waking up, ops.select_cpu() is the first operation invoked. This serves two purposes. First, CPU selection optimization hint. Second, waking up the selected CPU if idle. The CPU selected by ops.select_cpu() is an optimization hint and not binding. The actual decision is made at the last step of scheduling. However, there is a small performance gain if the CPU ops.select_cpu() returns matches the CPU the task eventually runs on. A side-effect of selecting a CPU is waking it up from idle. While a BPF scheduler can wake up any cpu using the scx_bpf_kick_cpu() helper, using ops.select_cpu() judiciously can be simpler and more efficient. Note that the scheduler core will ignore an invalid CPU selection, for example, if it's outside the allowed cpumask of the task. 2. Once the target CPU is selected, ops.enqueue() is invoked. It can make one of the following decisions: * Immediately dispatch the task to either the global or local DSQ by calling scx_bpf_dispatch() with SCX_DSQ_GLOBAL or SCX_DSQ_LOCAL, respectively. * Immediately dispatch the task to a custom DSQ by calling scx_bpf_dispatch() with a DSQ ID which is smaller than 2^63. * Queue the task on the BPF side. 3. When a CPU is ready to schedule, it first looks at its local DSQ. If empty, it then looks at the global DSQ. If there still isn't a task to run, ops.dispatch() is invoked which can use the following two functions to populate the local DSQ. * scx_bpf_dispatch() dispatches a task to a DSQ. Any target DSQ can be used - SCX_DSQ_LOCAL, SCX_DSQ_LOCAL_ON | cpu, SCX_DSQ_GLOBAL or a custom DSQ. While scx_bpf_dispatch() currently can't be called with BPF locks held, this is being worked on and will be supported. scx_bpf_dispatch() schedules dispatching rather than performing them immediately. There can be up to ops.dispatch_max_batch pending tasks. * scx_bpf_consume() tranfers a task from the specified non-local DSQ to the dispatching DSQ. This function cannot be called with any BPF locks held. scx_bpf_consume() flushes the pending dispatched tasks before trying to consume the specified DSQ. 4. After ops.dispatch() returns, if there are tasks in the local DSQ, the CPU runs the first one. If empty, the following steps are taken: * Try to consume the global DSQ. If successful, run the task. * If ops.dispatch() has dispatched any tasks, retry #3. * If the previous task is an SCX task and still runnable, keep executing it (see SCX_OPS_ENQ_LAST). * Go idle. Note that the BPF scheduler can always choose to dispatch tasks immediately in ops.enqueue() as illustrated in the above dummy example. If only the built-in DSQs are used, there is no need to implement ops.dispatch() as a task is never queued on the BPF scheduler and both the local and global DSQs are consumed automatically. Where to Look ============= * include/linux/sched/ext.h defines the core data structures, ops table and constants. * kernel/sched/ext.c contains sched_ext core implementation and helpers. The functions prefixed with scx_bpf_ can be called from the BPF scheduler. * tools/sched_ext/ hosts example BPF scheduler implementations. * scx_example_dummy[.bpf].c: Minimal global FIFO scheduler example using a custom DSQ. * scx_example_qmap[.bpf].c: A multi-level FIFO scheduler supporting five levels of priority implemented with BPF_MAP_TYPE_QUEUE. ABI Instability =============== The APIs provided by sched_ext to BPF schedulers programs have no stability guarantees. This includes the ops table callbacks and constants defined in include/linux/sched/ext.h, as well as the scx_bpf_ kfuncs defined in kernel/sched/ext.c. While we will attempt to provide a relatively stable API surface when possible, they are subject to change without warning between kernel versions. Caveats ======= * The current implementation isn't safe in that the BPF scheduler can crash the kernel. * Unsafe cpumask helpers should be replaced by proper generic BPF helpers. * Currently, all kfunc helpers can be called by any operation as BPF doesn't yet support filtering kfunc calls per struct_ops operation. Some helpers are context sensitive as should be restricted accordingly. * Timers used by the BPF scheduler should be shut down when aborting. * There are a couple BPF hacks which are still needed even for sched_ext proper. They should be removed in the near future.

diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst index b430d856056a..8a27a9967284 100644 --- a/Documentation/scheduler/index.rst +++ b/Documentation/scheduler/index.rst @@ -18,6 +18,7 @@ Linux Scheduler sched-nice-design sched-rt-group sched-stats + sched-ext sched-debug text_files diff --git a/Documentation/scheduler/sched-ext.rst b/Documentation/scheduler/sched-ext.rst new file mode 100644 index 000000000000..81f78e05a6c2 --- /dev/null +++ b/Documentation/scheduler/sched-ext.rst @@ -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 sysrq-S. + +Switching to and from sched_ext +=============================== + +``CONFIG_SCHED_CLASS_EXT`` is the config option to enable sched_ext and +``tools/sched_ext`` contains the example schedulers. + +sched_ext is used only when the BPF scheduler is loaded and running. + +If a task explicitly sets its scheduling policy to ``SCHED_EXT``, it will be +treated as ``SCHED_NORMAL`` and scheduled by CFS until the BPF scheduler is +loaded. On load, such tasks will be switched to and scheduled by sched_ext. + +The BPF scheduler can choose to schedule all normal and lower class tasks by +calling ``scx_bpf_switch_all()`` from its ``init()`` operation. In this +case, all ``SCHED_NORMAL``, ``SCHED_BATCH``, ``SCHED_IDLE`` and +``SCHED_EXT`` tasks are scheduled by sched_ext. In the example schedulers, +this mode can be selected with the ``-a`` option. + +Terminating the sched_ext scheduler program, triggering sysrq-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_dummy -a + local=0 global=3 + local=5 global=24 + local=9 global=44 + local=13 global=56 + local=17 global=72 + ^CEXIT: BPF scheduler 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 : dummy + 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 ``.name`` which must be a valid BPF object name. All operations are +optional. The following modified excerpt is from +``tools/sched/scx_example_dummy.bpf.c`` showing a minimal global FIFO +scheduler. + +.. code-block:: c + + s32 BPF_STRUCT_OPS(dummy_init) + { + if (switch_all) + scx_bpf_switch_all(); + return 0; + } + + void BPF_STRUCT_OPS(dummy_enqueue, struct task_struct *p, u64 enq_flags) + { + if (enq_flags & SCX_ENQ_LOCAL) + scx_bpf_dispatch(p, SCX_DSQ_LOCAL, enq_flags); + else + scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, enq_flags); + } + + void BPF_STRUCT_OPS(dummy_exit, struct scx_exit_info *ei) + { + exit_type = ei->type; + } + + SEC(".struct_ops") + struct sched_ext_ops dummy_ops = { + .enqueue = (void *)dummy_enqueue, + .init = (void *)dummy_init, + .exit = (void *)dummy_exit, + .name = "dummy", + }; + +Dispatch Queues +--------------- + +To match the impedance between the scheduler core and the BPF scheduler, +sched_ext uses simple FIFOs called dsq's (dispatch queues). By default, +there is one global FIFO (``SCX_DSQ_GLOBAL``), and one local dsq per CPU +(``SCX_DSQ_LOCAL``). The BPF scheduler can manage an arbitrary number of +dsq's using ``scx_bpf_create_dsq()`` and ``scx_bpf_destroy_dsq()``. + +A task is always *dispatch*ed to a dsq for execution. The task starts +execution when a CPU *consume*s the task from the dsq. + +Internally, a CPU only executes tasks which are running on its local dsq, +and the ``.consume()`` operation is in fact a transfer of a task from a +remote dsq to the CPU's local dsq. A CPU therefore only consumes from other +dsq's when its local dsq is empty, and dispatching a task to a local dsq +will cause it to be executed before the CPU attempts to consume tasks which +were previously dispatched to other dsq's. + +Scheduling Cycle +---------------- + +The following briefly shows 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. First, CPU selection optimization + hint. Second, waking up the selected CPU if idle. + + The CPU selected by ``.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 ``.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 ``.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, ``.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 user-created 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 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 implemented, the built-in ``SCX_DSQ_GLOBAL`` dsq + is consumed by default. + +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. + +5. If there's still no task to run, ``.consume_final()`` is invoked. + ``.consume_final()`` is equivalent to ``.consume()``, but is invoked + right before the CPU goes idle. This provide schedulers with a hook that + can be used to implement, e.g., more aggressive work stealing from remote + dsq's. + +Note that the BPF scheduler can always choose to dispatch tasks immediately +in ``.enqueue()`` as illustrated in the above dummy example. In such case, +there's no need to implement ``.dispatch()`` as a task is never queued on +the BPF side. + +Where to Look +============= + +* ``include/linux/sched/ext.h`` defines the core data structures, ops table + and constants. + +* ``kernel/sched/ext.c`` contains sched_ext core implementation and helpers. + The functions prefixed with ``scx_bpf_`` can be called from the BPF + scheduler. + +* ``tools/sched_ext/`` hosts example BPF scheduler implementations. + + * ``scx_example_dummy[.bpf].c``: Minimal global FIFO scheduler example + using a custom dsq. + + * ``scx_example_qmap[.bpf].c``: A multi-level FIFO scheduler supporting + five levels of priority implemented with ``BPF_MAP_TYPE_QUEUE``. + +ABI Instability +=============== + +The APIs provided by sched_ext to BPF schedulers programs have no stability +guarantees. This includes the ops table callbacks and constants defined in +``include/linux/sched/ext.h``, as well as the ``scx_bpf_`` kfuncs defined in +``kernel/sched/ext.c``. + +While we will attempt to provide a relatively stable API surface when +possible, they are subject to change without warning between kernel +versions. + +Caveats +======= + +* The current implementation isn't safe in that the BPF scheduler can crash + the kernel. + + * Unsafe cpumask helpers should be replaced by proper generic BPF helpers. + + * Currently, all kfunc helpers can be called by any operation as BPF + doesn't yet support filtering kfunc calls per struct_ops operation. Some + helpers are context sensitive as should be restricted accordingly. + + * Timers used by the BPF scheduler should be shut down when aborting. + +* There are a couple BPF hacks which are still needed even for sched_ext + proper. They should be removed in the near future. diff --git a/include/linux/sched/ext.h b/include/linux/sched/ext.h index d9f941e23011..49eda3adeecf 100644 --- a/include/linux/sched/ext.h +++ b/include/linux/sched/ext.h @@ -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 <tj@kernel.org> * Copyright (c) 2022 David Vernet <dvernet@meta.com> diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c index aab9ae13b88f..a28144220501 100644 --- a/kernel/sched/ext.c +++ b/kernel/sched/ext.c @@ -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 <tj@kernel.org> * Copyright (c) 2022 David Vernet <dvernet@meta.com> diff --git a/kernel/sched/ext.h b/kernel/sched/ext.h index e1eaaba3d4c7..b97dbb840ac9 100644 --- a/kernel/sched/ext.h +++ b/kernel/sched/ext.h @@ -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 <tj@kernel.org> * Copyright (c) 2022 David Vernet <dvernet@meta.com>

[28/31] sched_ext: Add Documentation/scheduler/sched-ext.rst

Checks

Commit Message

Comments

Patch