sched_ext: Capability-based CPU delegation for sub-schedulers
Subsystems (2)
Tejun Heo
reviewerPATCH v5 1/1 sched_ext: Capability-based CPU delegation for sub-schedulers
Hello,
Changes in v5:
- Patches 1-9 of v4 were applied to sched_ext/for-7.2-fixes and sched_ext/for-7.3 and are dropped. The series is rebased onto the updated for-7.3.
- New patch (01): WARN when a per-task op is dispatched on a scheduler other than the task's owner, with the two intentional non-owner call sites dispatching explicitly. Hardening out of the v4 placer-vs-owner review discussion. (sashiko AI)
- New prep patch (19): an in-place SAVE/RESTORE requeue of a running task re-ran cid admission and could bounce a task to the reject DSQ under a scheduler holding only SCX_CAP_ENQ_IMMED. Mark such enqueues with an internal IGNORE_CAPS flag which requires no caps. (sashiko AI)
- The CONFIG_EXT_SUB_SCHED=n scx_prog_sched() stub now also refuses a dead root scheduler, matching the =y behavior (12). (sashiko AI)
- scx_qmap: mask the highpri dispatch pick with the node's own cids and read the sub cgroup_id once in the dispatch path (32). (sashiko AI)
v4: https://lore.kernel.org/r/[email protected]
v3: https://lore.kernel.org/r/[email protected]
v2: https://lore.kernel.org/r/[email protected]
v1: https://lore.kernel.org/r/[email protected]
The existing sub-scheduler support only covers a part of scheduling. An scx_sched can attach to a cgroup subtree under another scx_sched and detach, and the dispatch path has programmatic delegation: dispatch runs as top-down recursion via scx_bpf_sub_dispatch(), so a parent decides when a child gets to pick tasks for the local cpu by calling into it.
The enqueue path is not implemented yet. Every scheduler in the hierarchy can insert into every local DSQ, so a parent has no way to partition CPUs among its children or protect its own share from them.
This patchset adds that control. Most importantly it enables sub-sched support on the enqueue path, and it extends the same control to the other paths that touch cpu access: occupancy, kicks and preemption, and idle reporting.
The enqueue path cannot use the dispatch path's programmatic model. Dispatch is top-down and the delegation is implicit in the call chain. Enqueue starts at the other end: a leaf picks a cid for a task, and which cids it may use is the cumulative result of its ancestors' delegation decisions. Resolving that programmatically on every enqueue would mean a cross-sched round-trip call chain, possibly retrying when a request cannot be granted as-is. Delegation is therefore state, not calls:
- Ownership is tracked per (scheduler, cid) as a set of capabilities:
- SCX_CAP_ENQ_IMMED: insert an IMMED task onto the cid's local DSQ. This is the baseline cap (SCX_CAP_BASE) required to make any use of a cpu.
- SCX_CAP_ENQ: insert any task onto the cid's local DSQ.
- SCX_CAP_PREEMPT: preempt a task outside the scheduler's own subtree.
Higher caps imply the lower ones for the holder's own use.
- The root owns every cap on every cid. A parent delegates caps to a child with scx_bpf_sub_grant() and takes them back with scx_bpf_sub_revoke(). A child's cap set is always a subset of its parent's.
- The cap state is sharded. The cid space is split into topology-aligned shards, and each scheduler tracks its caps in per-shard cmasks with a per-shard lock. Operations are broken up on shard boundaries and different shards never contend. Shards are expected to serve as the locality unit when cids are handed out to schedulers, so lock granularity scales naturally with the allocation pattern.
- Hot paths check a per-cpu effective-caps copy with a single read. Grant/revoke rings a per-cpu doorbell and the owning cpu folds the new config in at the top of balance(). Cross-sched communication happens only when the delegation set changes.
Enforcement:
- An insert that lacks the required cap is diverted to a kernel-internal per-rq reject DSQ and handed back to the BPF scheduler to re-decide, tagged with SCX_TASK_REENQ_CAP and the missing caps.
- A revoke evicts already-queued and running tasks through the same reenqueue path.
- CPU occupancy is tied to the task slice. Extending a slice requires baseline access on the cpu.
- Kicks are enforced at delivery. Any kick needs baseline access on the target cid, and SCX_KICK_PREEMPT degrades to a plain reschedule if the victim is outside the kicker's subtree and the kicker lacks SCX_CAP_PREEMPT.
Notifications:
- ops.sub_caps_updated() reports config-level changes per shard with coalescing.
- ops.sub_ecaps_updated() reports per-cpu effective changes when they take effect.
- ops.update_idle() is routed to the cid's owner, with a re-notification when ownership changes while the cpu sits idle.
A parent can evict a misbehaving child with scx_bpf_sub_kill().
To make it concrete, consider a root scheduler R with a child A, which in turn has a child A1:
- On enable, R owns every cap on every cid. A child starts with no caps and cannot use any cpu on its own, so a parent normally makes an initial grant when a child attaches.
- R grants cids 8-15 to A by calling scx_bpf_sub_grant() with A's cgroup id and a cmask. A grant is all-or-nothing per cid and can only hand down caps R holds literally.
- A learns of the grant through ops.sub_caps_updated(). As each cpu folds the change into its effective caps, A gets ops.sub_ecaps_updated() for that cid, and if the cpu is sitting idle, an ops.update_idle() re-notification so A can use it right away.
- Nesting chains through the same notifier: from its ops.sub_caps_updated(), A calls scx_bpf_sub_grant() to pass a subset, say cids 12-15, down to A1, whose own ops.sub_caps_updated() then fires. A1's cap set is a subset of A's, which is a subset of R's. Caps A holds only through implication cannot be re-delegated.
Using and then losing a cpu, from A's point of view, looks like this:
- Holding SCX_CAP_ENQ on cid 8, A inserts its tasks into cid 8's local DSQ from its enqueue and dispatch paths, extends their slices, and kicks the cpu as usual.
- R revokes cid 8. The revoke clears it across A's whole subtree, so A1 loses whatever it held on the cid too.
- Once the revoke reaches the cpu's effective caps, A's tasks queued on cid 8 are handed back to A's ops.enqueue() tagged with SCX_TASK_REENQ_CAP and the missing caps, a running task is evicted by zeroing its slice, and new inserts are rejected and handed back the same way.
- A places the bounced tasks somewhere it still holds, and the notifiers tell it that its holdings shrank.
The final three patches expand the scx_qmap hierarchical demo: a qmap instance splits the cpus it fully owns among itself and child qmaps in proportion to cpu.weight, time-shares the rounding leftovers through a round-robin pool, and can fault-inject dispatches to unheld cids to demonstrate the kernel-side enforcement.
Known limitations:
After this series, sub-scheduling works as long as tasks stay within their cgroup boundary and aren't affined away from the cpus their scheduler can use. Two pieces are still missing for full support:
- cgroup migration doesn't move a task across sub-schedulers. A task moved between cgroups served by different sub-scheds keeps its original scheduler.
- there is no fallback when a sub-scheduler holds no cpu a task is allowed to run on. Such a task, e.g. one affined only to cids its scheduler was never granted or has had revoked, has nowhere to go. The likely direction is reserving a slice off the root scheduler to run tasks without cpu access.
Based on sched_ext/for-7.3 (3d1519011e39).
This patchset contains the following 33 patches.
0001 sched_ext: Assert per-task ops run on the task's owner
0002 sched_ext: Make the kick machinery per-sched
0003 sched_ext: Add ops.init_cids() to finalize the cid layout before init 0004 sched_ext: Add CID sharding
0005 sched_ext: Add shard boundaries to scx_bpf_cid_override()
0006 sched_ext: Defer scx_sched kobj sysfs add into the enable workfns 0007 sched_ext: Add per-shard scx_sched storage scaffolding
0008 sched_ext: Add scx_cmask_ref for validated arena cmask access 0009 sched_ext: Build the set_cmask scratch from trusted geometry 0010 sched_ext: RCU-protect the sub-sched tree's children/sibling lists 0011 sched_ext: Add scx_skip_subtree_pre()
0012 sched_ext: Stop resolving a disabled scheduler's programs
0013 sched_ext: Add per-shard cap delegation for sub-schedulers
0014 sched_ext: Add coalescing sub_caps_updated() notifier for sub-schedulers 0015 sched_ext: Maintain per-cpu effective cap copies for single-read checks 0016 sched_ext: Add sub_ecaps_updated() effective-cap change notifier 0017 sched_ext: Generalize local-DSQ handling to rq-owned DSQs
0018 sched_ext: Add reject DSQ for cap-rejected dispatches
0019 sched_ext: Add SCX_ENQ_IGNORE_CAPS for in-place restore
0020 sched_ext: Add the SCX_CAP_ENQ_IMMED cap
0021 sched_ext: Assign a unique id to each scheduler instance
0022 sched_ext: Route task slice writes through set_task_slice()
0023 sched_ext: Track the cpu a task is runnable on
0024 sched_ext: Tie cpu occupancy to SCX_CAP_BASE through the task slice 0025 sched_ext: Add the SCX_CAP_ENQ cap
0026 sched_ext: Gate kicks on SCX_CAP_BASE and preemption on SCX_CAP_PREEMPT 0027 sched_ext: Authorize remote-move inserts against the placing scheduler 0028 sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds 0029 sched_ext: Replay ecaps notifications suppressed by bypass
0030 sched_ext: Add scx_bpf_sub_kill() to evict a child sub-scheduler 0031 tools/sched_ext: Add three-mask cmask intersection iterator
0032 tools/sched_ext: scx_qmap - Expand hierarchical sub-scheduling 0033 tools/sched_ext: scx_qmap - Add sub-sched cap fault injection
The patches are organized as follows:
- 01: prep. Assert per-task ops run on the task's owner.
- 02-12: plumbing. Per-sched kick machinery (02), ops.init_cids() (03), cid sharding (04-05), sysfs and per-shard storage prep (06-07), validated arena cmask access (08) and the trusted-geometry set_cmask build (09), RCU-safe tree walking (10-11), and gating a disabled scheduler's still-resolvable programs (12).
- 13-16: cap delegation. Per-shard caps with grant/revoke (13), the coalescing sub_caps_updated() notifier (14), per-cpu effective caps
(15) and the sub_ecaps_updated() notifier (16).
- 17-27: enforcement. The reject DSQ (17-18), the restore cap bypass (19), SCX_CAP_ENQ_IMMED (20), slice-based occupancy (21-24), SCX_CAP_ENQ (25), preemption and kick gating (26) and remote-move insert authorization (27).
- 28-30: idle routing and re-notification (28), bypass replay (29) and scx_bpf_sub_kill() (30).
- 31-33: scx_qmap hierarchical demo.
The patchset is also available in the following git branch:
git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git scx-sub-caps-v5
diffstat follows. Thanks.
include/linux/sched/ext.h | 33 +- init/init_task.c | 1 + kernel/sched/ext/cid.c | 508 +++++++++++++- kernel/sched/ext/cid.h | 17 +- kernel/sched/ext/ext.c | 852 ++++++++++++++++++----- kernel/sched/ext/idle.c | 86 ++- kernel/sched/ext/internal.h | 334 ++++++++- kernel/sched/ext/sub.c | 1120 +++++++++++++++++++++++++++++- kernel/sched/ext/sub.h | 121 +++- kernel/sched/ext/types.h | 74 +- kernel/sched/idle.c | 8 +- kernel/sched/sched.h | 17 +- tools/sched_ext/include/scx/cid.bpf.h | 77 ++ tools/sched_ext/include/scx/common.bpf.h | 24 + tools/sched_ext/include/scx/compat.bpf.h | 11 +- tools/sched_ext/scx_qmap.bpf.c | 852 ++++++++++++++++++++--- tools/sched_ext/scx_qmap.c | 355 +++++++++- tools/sched_ext/scx_qmap.h | 115 ++- 18 files changed, 4238 insertions(+), 367 deletions(-)
--
tejun
Tejun Heo
reviewerPATCH v5 1/33 sched_ext: Assert per-task ops run on the task's owner
A per-task op must be dispatched on the scheduler that owns the task. SCX_CALL_OP_TASK() and its _RET twin take @sch explicitly, and a caller that passes the wrong scheduler would silently run the op on it. Add a WARN_ON_ONCE() that @sch matches the task's owner so such a mismatch is caught rather than hidden.
Two sites legitimately target a scheduler other than the task's owner:cgroup_move() runs on the root sched, and scx_sub_init_cancel_task() fires exit_task() on a task not yet associated with @sch. Both switch to the inner __SCX_CALL_OP_TASK(), which dispatches on the explicit @sch without the assert.
--- kernel/sched/ext/ext.c | 20 +++++++++++++------- kernel/sched/ext/internal.h | 10 +++++++++- 2 files changed, 22 insertions(+), 8 deletions(-)
kernel/sched/ext/ext.c +13 -7
@@ -1436,8 +1436,12 @@ static void scx_dispatch_enqueue(struct scx_sched *sch, struct rq *rq,local_dsq_post_enq (sch, dsq, p, enq_flags); }else {/* -* Task on global/bypass DSQ: leave custody, task on -* non-terminal DSQ: enter custody. +* Global and bypass DSQs are terminal - the task leaves the +* scheduler's custody, so ops.dequeue() fires here. It can run +* without @p's rq lock (finish_dispatch() passes the dispatch +* rq); that's safe because dequeue_task_scx() waits on +* SCX_OPSS_DISPATCHING (see the ops_state note above) and so +* can't race it. A non-terminal DSQ keeps the task in custody. */ if (dsq->id ==SCX_DSQ_GLOBAL || dsq->id ==SCX_DSQ_BYPASS )call_task_dequeue (sch, rq, p,0 );
@@ -3446,8 +3450,9 @@ void scx_sub_init_cancel_task(struct scx_sched *sch, struct task_struct *p)lockdep_assert_held (&p->pi_lock);lockdep_assert_rq_held (task_rq (p)); +/* @p was never associated with @sch, dispatch on the explicit @sch */ if (SCX_HAS_OP (sch, exit_task)) -SCX_CALL_OP_TASK (sch, exit_task,task_rq (p), p, &args); +__SCX_CALL_OP_TASK (sch, ops, exit_task,task_rq (p), p, &args); }void scx_disable_and_exit_task (struct scx_sched *sch,struct task_struct *p)
@@ -4184,12 +4189,13 @@ void scx_cgroup_move_task(struct task_struct *p)* cgroup changes. Migration keys off css rather than cgroup identity, * so it can hand an unchanged-cgroup task here with cgrp_moving_from * NULL. Nothing to report to the BPF scheduler then, so skip it and -* keep prep_move and move paired. +* keep prep_move and move paired. Cgroup ops run on the root sched, +* dispatch on the explicit @sch. */ if (SCX_HAS_OP (sch, cgroup_move) && p->scx.cgrp_moving_from) -SCX_CALL_OP_TASK (sch, cgroup_move,task_rq (p), - p, p->scx.cgrp_moving_from, -tg_cgrp (task_group (p))); +__SCX_CALL_OP_TASK (sch, ops, cgroup_move,task_rq (p), + p, p->scx.cgrp_moving_from, +tg_cgrp (task_group (p))); p->scx.cgrp_moving_from =NULL ; }
kernel/sched/ext/internal.h +9 -1
@@ -1810,8 +1810,15 @@ do { \ current->scx.kf_tasks[0 ] =NULL ; \ }while (0 ) +/* +* A per-task op runs on @task's owner - WARN if @sch isn't it. Sites that must +* target a different scheduler call __SCX_CALL_OP_TASK() directly. +*/ #define SCX_CALL_OP_TASK(sch, op, locked_rq, task, args...) \ - __SCX_CALL_OP_TASK(sch, ops, op, locked_rq, task, ##args) +do { \ +WARN_ON_ONCE ((sch) !=scx_task_sched_rcu (task)); \ + __SCX_CALL_OP_TASK((sch), ops, op, locked_rq, task, ##args); \ +}while (0 )/* * Dispatch a task op through the cid-form ops_cid table. Only set_cmask() needs
@@ -1824,6 +1831,7 @@ do { \ #define SCX_CALL_OP_TASK_RET(sch, op, locked_rq, task, args...) \ ({ \ __typeof__((sch)->ops.op(task, ##args)) __ret; \ + WARN_ON_ONCE((sch) != scx_task_sched_rcu(task)); \ WARN_ON_ONCE(current->scx.kf_tasks[0]); \ current->scx.kf_tasks[0] = task; \ __ret = SCX_CALL_OP_RET((sch), op, locked_rq, task, ##args); \
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 2/33 sched_ext: Make the kick machinery per-sched
In reply to Tejun HeoThe kick machinery kept its targets in rq->scx shared by every sched on the cpu. A preempt kick carried no record of which scheduler requested it.
A later patch needs preempt kicks scoped to the requesting scheduler so a sub-scheduler can preempt only tasks in its own subtree. Move the kick masks into the per-sched per-cpu scx_sched_pcpu and have scx_kick_cpu() link the sched onto a per-cpu list (rq->scx.sched_pcpus_to_kick). The cpu's single kick irq_work walks that list and kicks each sched's targets on its behalf, so a kick stays attributed to its scheduler.
The SCX_KICK_WAIT sync set (cpus_to_sync, the kick_sync snapshot and the balance-callback trigger) stays in rq->scx: the waiter is the cpu, not the scheduler, and its only writers, the kick irq_work and the wait balance callback, are cpu-local.
On disable, free_kick_syncs() flushes each cpu's pending kick irq_work before clearing @ksyncs, so a late kick unlinks its to_kick_node instead of early-returning on a NULL @ksyncs and leaving the node linked at free.
v3: Flush the kick irq_work in free_kick_syncs() before clearing @ksyncs. (sashiko AI)
v2: Warn once per sched on scx_bpf_kick_cpu() from NMI.
--- kernel/sched/ext/ext.c | 121 +++++++++++++++++++++++++++--------- kernel/sched/ext/internal.h | 14 +++++ kernel/sched/sched.h | 6 +- 3 files changed, 106 insertions(+), 35 deletions(-)
kernel/sched/ext/ext.c +90 -31
@@ -4661,6 +4661,17 @@ static void scx_sched_free_rcu_work(struct work_struct *work)*/ WARN_ON_ONCE (!list_empty (&pcpu->deferred_reenq_local.node)); +/* +* Bypass blocks new kicks. Flush the kick irq_work so this +* pcpu's to_kick_node is off the list before it is freed. +*/ +irq_work_sync (&cpu_rq (cpu)->scx.kick_cpus_irq_work); +WARN_ON_ONCE (!list_empty (&pcpu->to_kick_node)); +free_cpumask_var (pcpu->cpus_to_kick); +free_cpumask_var (pcpu->cpus_to_kick_if_idle); +free_cpumask_var (pcpu->cpus_to_preempt); +free_cpumask_var (pcpu->cpus_to_wait); +exit_dsq (scx_bypass_dsq (sch, cpu)); }
@@ -5453,6 +5464,8 @@ static void free_kick_syncs(void)struct scx_kick_syncs __rcu **ksyncs =per_cpu_ptr (&scx_kick_syncs, cpu);struct scx_kick_syncs *to_free; +/* flush the pending kick before freeing @ksyncs */ +irq_work_sync (&cpu_rq (cpu)->scx.kick_cpus_irq_work); to_free =rcu_replace_pointer (*ksyncs,NULL , true);if (to_free)kvfree_rcu (to_free, rcu);
@@ -6004,6 +6017,7 @@ static void scx_dump_cpu(struct scx_sched *sch, struct seq_buf *s, bool dump_all_tasks) {struct rq *rq =cpu_rq (cpu); +struct scx_sched_pcpu *pcpu =per_cpu_ptr (sch->pcpu, cpu);struct rq_flags rf;struct task_struct *p;struct seq_buf ns;
@@ -6036,18 +6050,18 @@ static void scx_dump_cpu(struct scx_sched *sch, struct seq_buf *s,dump_line (&ns," curr=%s[%d] class=%ps" , rq->curr->comm, rq->curr->pid, rq->curr->sched_class); -if (!cpumask_empty (rq->scx.cpus_to_kick)) +if (!cpumask_empty (pcpu->cpus_to_kick))dump_line (&ns," cpus_to_kick : %*pb" , -cpumask_pr_args (rq->scx.cpus_to_kick)); -if (!cpumask_empty (rq->scx.cpus_to_kick_if_idle)) +cpumask_pr_args (pcpu->cpus_to_kick)); +if (!cpumask_empty (pcpu->cpus_to_kick_if_idle))dump_line (&ns," idle_to_kick : %*pb" , -cpumask_pr_args (rq->scx.cpus_to_kick_if_idle)); -if (!cpumask_empty (rq->scx.cpus_to_preempt)) +cpumask_pr_args (pcpu->cpus_to_kick_if_idle)); +if (!cpumask_empty (pcpu->cpus_to_preempt))dump_line (&ns," cpus_to_preempt: %*pb" , -cpumask_pr_args (rq->scx.cpus_to_preempt)); -if (!cpumask_empty (rq->scx.cpus_to_wait)) +cpumask_pr_args (pcpu->cpus_to_preempt)); +if (!cpumask_empty (pcpu->cpus_to_wait))dump_line (&ns," cpus_to_wait : %*pb" , -cpumask_pr_args (rq->scx.cpus_to_wait)); +cpumask_pr_args (pcpu->cpus_to_wait));if (!cpumask_empty (rq->scx.cpus_to_sync))dump_line (&ns," cpus_to_sync : %*pb" ,cpumask_pr_args (rq->scx.cpus_to_sync));
@@ -6339,8 +6353,17 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd,for_each_possible_cpu (cpu) {struct scx_sched_pcpu *pcpu =per_cpu_ptr (sch->pcpu, cpu); + node =cpu_to_node (cpu); pcpu->sch = sch;INIT_LIST_HEAD (&pcpu->deferred_reenq_local.node); +INIT_LIST_HEAD (&pcpu->to_kick_node); +if (!zalloc_cpumask_var_node (&pcpu->cpus_to_kick,GFP_KERNEL , node) || + !zalloc_cpumask_var_node (&pcpu->cpus_to_kick_if_idle,GFP_KERNEL , node) || + !zalloc_cpumask_var_node (&pcpu->cpus_to_preempt,GFP_KERNEL , node) || + !zalloc_cpumask_var_node (&pcpu->cpus_to_wait,GFP_KERNEL , node)) { + ret = -ENOMEM ; + goto err_free_pcpu; + } } sch->helper =kthread_run_worker (0 ,"sched_ext_helper" );
@@ -6485,6 +6508,14 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd, err_stop_helper:kthread_destroy_worker (sch->helper); err_free_pcpu: +for_each_possible_cpu (cpu) { +struct scx_sched_pcpu *pcpu =per_cpu_ptr (sch->pcpu, cpu); + +free_cpumask_var (pcpu->cpus_to_kick); +free_cpumask_var (pcpu->cpus_to_kick_if_idle); +free_cpumask_var (pcpu->cpus_to_preempt); +free_cpumask_var (pcpu->cpus_to_wait); + }for_each_possible_cpu (cpu) {if (cpu == bypass_fail_cpu)break ;
@@ -7498,7 +7529,8 @@ static bool can_skip_idle_kick(struct rq *rq)return !is_idle_task (rq->curr) && !(rq->scx.flags &SCX_RQ_IN_BALANCE ); } -static bool kick_one_cpu (s32 cpu,struct rq *this_rq,unsigned long *ksyncs) +static bool kick_one_cpu (s32 cpu,struct scx_sched_pcpu *pcpu,struct rq *this_rq, +unsigned long *ksyncs) {struct rq *rq =cpu_rq (cpu);struct scx_rq *this_scx = &this_rq->scx;
@@ -7517,25 +7549,25 @@ static bool kick_one_cpu(s32 cpu, struct rq *this_rq, unsigned long *ksyncs)*/ if ((cpu_online (cpu) || cpu ==cpu_of (this_rq)) && !sched_class_above (cur_class, &ext_sched_class)) { -if (cpumask_test_cpu (cpu, this_scx->cpus_to_preempt)) { +if (cpumask_test_cpu (cpu, pcpu->cpus_to_preempt)) {if (cur_class == &ext_sched_class) rq->curr->scx.slice =0 ; -cpumask_clear_cpu (cpu, this_scx->cpus_to_preempt); +cpumask_clear_cpu (cpu, pcpu->cpus_to_preempt); } -if (cpumask_test_cpu (cpu, this_scx->cpus_to_wait)) { +if (cpumask_test_cpu (cpu, pcpu->cpus_to_wait)) {if (cur_class == &ext_sched_class) {cpumask_set_cpu (cpu, this_scx->cpus_to_sync); ksyncs[cpu] = rq->scx.kick_sync; should_wait = true; } -cpumask_clear_cpu (cpu, this_scx->cpus_to_wait); +cpumask_clear_cpu (cpu, pcpu->cpus_to_wait); }resched_curr (rq); }else { -cpumask_clear_cpu (cpu, this_scx->cpus_to_preempt); -cpumask_clear_cpu (cpu, this_scx->cpus_to_wait); +cpumask_clear_cpu (cpu, pcpu->cpus_to_preempt); +cpumask_clear_cpu (cpu, pcpu->cpus_to_wait); }raw_spin_rq_unlock_irqrestore (rq, flags);
@@ -7562,6 +7594,7 @@ static void kick_cpus_irq_workfn(struct irq_work *irq_work)struct rq *this_rq =this_rq ();struct scx_rq *this_scx = &this_rq->scx;struct scx_kick_syncs __rcu *ksyncs_pcpu =__this_cpu_read (scx_kick_syncs); +struct scx_sched_pcpu *pcpu, *tmp;bool should_wait = false;unsigned long *ksyncs;s32 cpu;
@@ -7572,15 +7605,24 @@ static void kick_cpus_irq_workfn(struct irq_work *irq_work) ksyncs =rcu_dereference_bh (ksyncs_pcpu)->syncs; -for_each_cpu (cpu, this_scx->cpus_to_kick) { - should_wait |=kick_one_cpu (cpu, this_rq, ksyncs); -cpumask_clear_cpu (cpu, this_scx->cpus_to_kick); -cpumask_clear_cpu (cpu, this_scx->cpus_to_kick_if_idle); - } +/* +* Walk scheds with pending kicks on this cpu. scx_kick_cpu() adds to +* the list under local_irq_save() and only this irq_work consumes it. +* A plain list without locking is sufficient. +*/ +list_for_each_entry_safe (pcpu, tmp, &this_scx->sched_pcpus_to_kick, to_kick_node) { +list_del_init (&pcpu->to_kick_node); + +for_each_cpu (cpu, pcpu->cpus_to_kick) { + should_wait |=kick_one_cpu (cpu, pcpu, this_rq, ksyncs); +cpumask_clear_cpu (cpu, pcpu->cpus_to_kick); +cpumask_clear_cpu (cpu, pcpu->cpus_to_kick_if_idle); + } -for_each_cpu (cpu, this_scx->cpus_to_kick_if_idle) { -kick_one_cpu_if_idle (cpu, this_rq); -cpumask_clear_cpu (cpu, this_scx->cpus_to_kick_if_idle); +for_each_cpu (cpu, pcpu->cpus_to_kick_if_idle) { +kick_one_cpu_if_idle (cpu, this_rq); +cpumask_clear_cpu (cpu, pcpu->cpus_to_kick_if_idle); + } }/*
@@ -7705,11 +7747,8 @@ void __init init_sched_ext_class(void)INIT_LIST_HEAD (&rq->scx.runnable_list);INIT_LIST_HEAD (&rq->scx.ddsp_deferred_locals); -BUG_ON (!zalloc_cpumask_var_node (&rq->scx.cpus_to_kick,GFP_KERNEL , n)); -BUG_ON (!zalloc_cpumask_var_node (&rq->scx.cpus_to_kick_if_idle,GFP_KERNEL , n)); -BUG_ON (!zalloc_cpumask_var_node (&rq->scx.cpus_to_preempt,GFP_KERNEL , n)); -BUG_ON (!zalloc_cpumask_var_node (&rq->scx.cpus_to_wait,GFP_KERNEL , n));BUG_ON (!zalloc_cpumask_var_node (&rq->scx.cpus_to_sync,GFP_KERNEL , n)); +INIT_LIST_HEAD (&rq->scx.sched_pcpus_to_kick);raw_spin_lock_init (&rq->scx.deferred_reenq_lock);INIT_LIST_HEAD (&rq->scx.deferred_reenq_locals);INIT_LIST_HEAD (&rq->scx.deferred_reenq_users);
@@ -8491,12 +8530,27 @@ __bpf_kfunc bool scx_bpf_task_set_dsq_vtime(struct task_struct *p, u64 vtime,void scx_kick_cpu (struct scx_sched *sch,s32 cpu,u64 flags) { +struct scx_sched_pcpu *pcpu;struct rq *this_rq;unsigned long irq_flags; +/* +* The per-cpu kick list is guarded only by local_irq_save(), which does +* not mask NMIs, so kicking from NMI could corrupt it and is unsupported. +*/ +if (unlikely (in_nmi ())) { +if (!sch->warned_nmi_kick) { + sch->warned_nmi_kick = true; +pr_warn ("sched_ext: %s: scx_bpf_kick_cpu() from NMI ignored\n" , + sch->ops.name); + } +return ; + } +local_irq_save (irq_flags); this_rq =this_rq (); + pcpu =this_cpu_ptr (sch->pcpu);/* * While bypassing for PM ops, IRQ handling may not be online which can
@@ -8510,6 +8564,9 @@ void scx_kick_cpu(struct scx_sched *sch, s32 cpu, u64 flags)* Actual kicking is bounced to kick_cpus_irq_workfn() to avoid nesting * rq locks. We can probably be smarter and avoid bouncing if called * from ops which don't hold a rq lock. +* +* The kick masks are owned by @sch->pcpu, so that a preempt kick can be +* attributed to @sch. */ if (flags &SCX_KICK_IDLE ) {struct rq *target_rq =cpu_rq (cpu);
@@ -8524,16 +8581,18 @@ void scx_kick_cpu(struct scx_sched *sch, s32 cpu, u64 flags) }raw_spin_rq_unlock (target_rq); } -cpumask_set_cpu (cpu, this_rq->scx.cpus_to_kick_if_idle); +cpumask_set_cpu (cpu, pcpu->cpus_to_kick_if_idle); }else { -cpumask_set_cpu (cpu, this_rq->scx.cpus_to_kick); +cpumask_set_cpu (cpu, pcpu->cpus_to_kick);if (flags &SCX_KICK_PREEMPT ) -cpumask_set_cpu (cpu, this_rq->scx.cpus_to_preempt); +cpumask_set_cpu (cpu, pcpu->cpus_to_preempt);if (flags &SCX_KICK_WAIT ) -cpumask_set_cpu (cpu, this_rq->scx.cpus_to_wait); +cpumask_set_cpu (cpu, pcpu->cpus_to_wait); } +if (list_empty (&pcpu->to_kick_node)) +list_add_tail (&pcpu->to_kick_node, &this_rq->scx.sched_pcpus_to_kick);irq_work_queue (&this_rq->scx.kick_cpus_irq_work); out:local_irq_restore (irq_flags);
kernel/sched/ext/internal.h +14 -0
@@ -1126,6 +1126,19 @@ struct scx_sched_pcpu {struct scx_sched *sch;u64 flags;/* protected by rq lock */ +/* +* Kick state owned by this cpu for this sched. scx_kick_cpu() records +* targets here and links @to_kick_node onto the cpu's +* rq->scx.sched_pcpus_to_kick. The cpu's single kick irq_work walks +* that list and kicks each sched's targets on its behalf. Per-sched so +* a kick stays attributed to its scheduler. +*/ +cpumask_var_t cpus_to_kick; +cpumask_var_t cpus_to_kick_if_idle; +cpumask_var_t cpus_to_preempt; +cpumask_var_t cpus_to_wait; +struct list_head to_kick_node; +/* * The event counters are in a per-CPU variable to minimize the * accounting overhead. A system-wide view on the event counter is
@@ -1215,6 +1228,7 @@ struct scx_sched {*/ bool warned_zero_slice:1; bool warned_unassoc_progs:1; + bool warned_nmi_kick:1;struct list_head all;
kernel/sched/sched.h +2 -4
@@ -806,14 +806,12 @@ struct scx_rq {u32 flags;u32 nr_immed;/* ENQ_IMMED tasks on local_dsq */ u64 clock;/* current per-rq clock -- see scx_bpf_now() */ -cpumask_var_t cpus_to_kick; -cpumask_var_t cpus_to_kick_if_idle; -cpumask_var_t cpus_to_preempt; -cpumask_var_t cpus_to_wait;cpumask_var_t cpus_to_sync;bool kick_sync_pending;unsigned long kick_sync; +struct list_head sched_pcpus_to_kick;/* see kick_cpus_irq_workfn() */ +struct task_struct *sub_dispatch_prev;raw_spinlock_t deferred_reenq_lock;
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 3/33 sched_ext: Add ops.init_cids() to finalize the cid layout before init
In reply to Tejun HeoA cid-form scheduler that calls scx_bpf_cid_override() to install a custom cid layout can only do so from ops.init(). Enable-path setup that depends on the cid layout thus has to run after ops.init(), and ops.init() itself can't use anything derived from the final layout, which turned out to be too restrictive.
Add an ops.init_cids() callback dedicated to finalizing the cid layout. It runs before the rest of the enable-path setup, so the final layout is in effect for everything that follows including ops.init(), which now runs after the arena pool and cmask scratch allocations.
scx_bpf_cid_override() is restricted to ops.init_cids() at load time. It sits in a kfunc set gated by SCX_KF_ALLOW_INIT_CIDS, a flag set only on the init_cids op, so the verifier rejects a call from any other context. The runtime root-only check is dropped as ops.init_cids() only runs during root enable.
The qmap demo moves its override into a dedicated qmap_init_cids() and, while at it, introduces an enum for the cid override modes instead of hard-coded integers.
--- kernel/sched/ext/cid.c | 25 ++++++++----------- kernel/sched/ext/cid.h | 2 +- kernel/sched/ext/ext.c | 41 +++++++++++++++++++++++-------- kernel/sched/ext/internal.h | 16 ++++++++++--- tools/sched_ext/scx_qmap.bpf.c | 44 +++++++++++++++++++++------------- tools/sched_ext/scx_qmap.c | 12 +++++----- tools/sched_ext/scx_qmap.h | 8 +++++++ 7 files changed, 96 insertions(+), 52 deletions(-)
kernel/sched/ext/cid.c +10 -15
@@ -13,10 +13,10 @@/* * cid tables. * -* Pointers are published once on first enable and never revoked. The default -* mapping is populated before ops.init() runs; scx_bpf_cid_override() commits -* before it returns. As long as the BPF scheduler only uses the tables from -* those points onward, it sees a consistent view. +* Pointers are allocated on first enable and never freed. During root enable, +* the default mapping is populated and then ops.init_cids() is called which can +* use scx_bpf_cid_override() to change the mapping. The mapping stays stable +* until the root is disabled. */ s16 *scx_cid_to_cpu_tbl;s16 *scx_cpu_to_cid_tbl;
@@ -282,7 +282,7 @@ __bpf_kfunc_start_defs();* @cpu_to_cid__sz: must be nr_cpu_ids * sizeof(s32) bytes * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * -* May only be called from ops.init() of the root scheduler. Replace the +* May only be called from ops.init_cids() of the root scheduler. Replace the * topology-probed cid mapping with the caller-provided one. Each possible cpu * must map to a unique cid in [0, num_possible_cpus()). Topo info is cleared. * On invalid input, trigger scx_error() to abort the scheduler.
@@ -309,11 +309,6 @@ __bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid, u32 cpu_to_cid__sz,return ; } -if (scx_parent (sch)) { -scx_error (sch,"scx_bpf_cid_override() only allowed from root sched" ); -return ; - } -if (cpu_to_cid__sz != nr_cpu_ids *sizeof (s32)) {scx_error (sch,"scx_bpf_cid_override: expected %zu bytes, got %u" , nr_cpu_ids *sizeof (s32), cpu_to_cid__sz);
@@ -645,13 +640,13 @@ __bpf_kfunc void scx_bpf_cid_topo(s32 cid, struct scx_cid_topo *out__uninit,__bpf_kfunc_end_defs (); -BTF_KFUNCS_START(scx_kfunc_ids_init) +BTF_KFUNCS_START(scx_kfunc_ids_init_cids) BTF_ID_FLAGS(func, scx_bpf_cid_override, KF_IMPLICIT_ARGS | KF_SLEEPABLE) -BTF_KFUNCS_END(scx_kfunc_ids_init) +BTF_KFUNCS_END(scx_kfunc_ids_init_cids) -static const struct btf_kfunc_id_set scx_kfunc_set_init = { +static const struct btf_kfunc_id_set scx_kfunc_set_init_cids = { .owner = THIS_MODULE, - .set = &scx_kfunc_ids_init, + .set = &scx_kfunc_ids_init_cids, .filter = scx_kfunc_context_filter, };
@@ -668,7 +663,7 @@ static const struct btf_kfunc_id_set scx_kfunc_set_cid = {int scx_cid_kfunc_init (void ) { -return register_btf_kfunc_id_set (BPF_PROG_TYPE_STRUCT_OPS , &scx_kfunc_set_init) ?: +return register_btf_kfunc_id_set (BPF_PROG_TYPE_STRUCT_OPS , &scx_kfunc_set_init_cids) ?:register_btf_kfunc_id_set (BPF_PROG_TYPE_STRUCT_OPS , &scx_kfunc_set_cid) ?:register_btf_kfunc_id_set (BPF_PROG_TYPE_TRACING , &scx_kfunc_set_cid) ?:register_btf_kfunc_id_set (BPF_PROG_TYPE_SYSCALL , &scx_kfunc_set_cid);
kernel/sched/ext/cid.h +1 -1
@@ -51,7 +51,7 @@ struct scx_sched;extern s16 *scx_cid_to_cpu_tbl;extern s16 *scx_cpu_to_cid_tbl;extern struct scx_cid_topo *scx_cid_topo; -extern struct btf_id_set8 scx_kfunc_ids_init; +extern struct btf_id_set8 scx_kfunc_ids_init_cids;void scx_cmask_clear (struct scx_cmask *m);void scx_cmask_fill (struct scx_cmask *m);
kernel/sched/ext/ext.c +31 -10
117 lines not on this page · raw message
kernel/sched/ext/internal.h +13 -3
@@ -780,9 +780,18 @@ struct sched_ext_ops {void (*cpu_offline)(s32 cpu);/* -* All CPU hotplug ops must come before ops.init(). +* All CPU hotplug ops must come before ops.init_cids(). */ +/** +* @init_cids: Finalize the cid layout (cid-form only) +* +* Runs after the default cid layout is built, before ops.init(). A +* cid-form scheduler may call scx_bpf_cid_override() here for a custom +* layout. Ignored for cpu-form schedulers. +*/ +s32 (*init_cids)(void); +/** * @init: Initialize the BPF scheduler */
@@ -958,6 +967,7 @@ struct sched_ext_ops_cid {void (*sub_detach)(struct scx_sub_detach_args *args);void (*cid_online)(s32 cid);void (*cid_offline)(s32 cid); +s32 (*init_cids)(void);s32 (*init)(void);void (*exit)(struct scx_exit_info *info);
@@ -982,8 +992,8 @@ enum scx_opi {SCX_OPI_NORMAL_BEGIN =0 ,SCX_OPI_NORMAL_END =SCX_OP_IDX (cpu_online),SCX_OPI_CPU_HOTPLUG_BEGIN =SCX_OP_IDX (cpu_online), -SCX_OPI_CPU_HOTPLUG_END =SCX_OP_IDX (init), - SCX_OPI_END = SCX_OP_IDX(init), +SCX_OPI_CPU_HOTPLUG_END =SCX_OP_IDX (init_cids), + SCX_OPI_END = SCX_OP_IDX(init_cids), };/*
tools/sched_ext/scx_qmap.bpf.c +27 -17
68 lines not on this page · raw message
tools/sched_ext/scx_qmap.c +6 -6
@@ -157,11 +157,11 @@ int main(int argc, char **argv)u32 mode, i;if (!strcmp (optarg,"shuffle" )) - mode =1 ; + mode =QMAP_CID_OVR_SHUFFLE ;else if (!strcmp (optarg,"bad-dup" )) - mode =2 ; + mode =QMAP_CID_OVR_BAD_DUP ;else if (!strcmp (optarg,"bad-range" )) - mode =3 ; + mode =QMAP_CID_OVR_BAD_RANGE ;else {fprintf (stderr,"unknown cid-override mode '%s'\n" , optarg);return 1 ;
@@ -170,14 +170,14 @@ int main(int argc, char **argv)/* shuffle: reversed cpu_to_cid, bad-dup: dup cid 0, bad-range: identity */ for (i =0 ; i < nr_cpus; i++) { -if (mode ==1 ) +if (mode ==QMAP_CID_OVR_SHUFFLE ) skel->bss->cid_override_cpu_to_cid[i] = nr_cpus -1 - i;else skel->bss->cid_override_cpu_to_cid[i] = i; } -if (mode ==2 && nr_cpus >=2 ) +if (mode ==QMAP_CID_OVR_BAD_DUP && nr_cpus >=2 ) skel->bss->cid_override_cpu_to_cid[1 ] =0 ; -if (mode ==3 ) +if (mode ==QMAP_CID_OVR_BAD_RANGE ) skel->bss->cid_override_cpu_to_cid[0 ] = (s32 )nr_cpus;break ; }
tools/sched_ext/scx_qmap.h +8 -0
@@ -27,6 +27,14 @@*/ #define SCX_QMAP_MAX_CPUS 1024 +/* -C cid-override test modes. Selects cid_override_mode in scx_qmap.bpf.c. */ +enum qmap_cid_override { +QMAP_CID_OVR_OFF =0 ,/* disabled */ +QMAP_CID_OVR_SHUFFLE =1 ,/* valid reversed cpu->cid mapping */ +QMAP_CID_OVR_BAD_DUP =2 ,/* invalid: duplicate cid assignment */ +QMAP_CID_OVR_BAD_RANGE =3 ,/* invalid: out-of-range cid */ +}; +struct cpu_ctx {u64 dsp_idx;/* dispatch index */ u64 dsp_cnt;/* remaining count */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 4/33 sched_ext: Add CID sharding
In reply to Tejun HeoSub-sched operations need a scalable locking / work domain smaller than the whole cid space. Carve the cid space into topology-respecting shards: each shard is a contiguous cid range that stays within one LLC, and LLCs larger than the per-shard cap (default 24 cids, configurable via ops.cid_shard_size) split into enough shards to fit. A hard cap of SCX_CID_SHARD_MAX_CPUS prevents pathological sizes under custom configurations.
No-topo cids pack into their own shards so every cid has a shard assignment.
Also build scx_cid_shard_ranges[] for O(1) shard-to-cid-range lookup and scx_shard_node[] so callers can size or place work by NUMA without walking cids. Auto-built shards inherit their LLC's node. No-topo shards carry NUMA_NO_NODE.
--- kernel/sched/ext/cid.c | 132 ++++++++++++++++++++++++++++++++++-- kernel/sched/ext/cid.h | 4 ++ kernel/sched/ext/ext.c | 4 ++ kernel/sched/ext/internal.h | 13 ++++ kernel/sched/ext/types.h | 35 ++++++++-- 5 files changed, 176 insertions(+), 12 deletions(-)
kernel/sched/ext/cid.c +125 -7
@@ -18,13 +18,17 @@* use scx_bpf_cid_override() to change the mapping. The mapping stays stable * until the root is disabled. */ +u32 scx_nr_cid_shards;s16 *scx_cid_to_cpu_tbl;s16 *scx_cpu_to_cid_tbl; +s32 *scx_cid_to_shard; +s32 *scx_shard_node; +struct scx_cid_shard *scx_cid_shard_ranges;struct scx_cid_topo *scx_cid_topo;#define SCX_CID_TOPO_NEG (struct scx_cid_topo) { \ .core_cid = -1, .core_idx = -1, .llc_cid = -1, .llc_idx = -1, \ - .node_cid = -1, .node_idx = -1, \ + .node_cid = -1, .node_idx = -1, .shard_cid = -1, .shard_idx = -1, \ }/*
@@ -43,11 +47,40 @@ static const struct cpumask *cpu_llc_mask(int cpu, struct cpumask *fallbacks)return &ci->info_list[ci->num_leaves -1 ].shared_cpu_map; } +/* +* Compute per-LLC shard layout. Each shard holds at most @shard_size cids, and +* in any case no more than SCX_CID_SHARD_MAX_CPUS. Cores are spread as evenly +* as possible across shards so cpu count is balanced: the first *@nr_large_p +* shards get (*@cores_per_shard_p + 1) cores, the rest get *@cores_per_shard_p. +*/ +static void calc_shard_layout (const struct cpumask *llc_cpus,u32 shard_size, +u32 *cores_per_shard_p,u32 *nr_large_p) +{ +u32 nr_cores =0 , nr_cpus =0 , nr_shards; +int cpu; + +for_each_cpu (cpu, llc_cpus) { + nr_cpus++; +if (cpumask_first (topology_sibling_cpumask (cpu)) == cpu) + nr_cores++; + } + + nr_shards =max_t (u32,1 ,DIV_ROUND_UP (nr_cpus, shard_size)); + nr_shards =max_t (u32, nr_shards, +DIV_ROUND_UP (nr_cpus,SCX_CID_SHARD_MAX_CPUS )); + + *cores_per_shard_p = nr_cores / nr_shards; + *nr_large_p = nr_cores % nr_shards; +} +/* Allocate the cid tables once on first enable; never freed. */ static s32 scx_cid_arrays_alloc (void ) {u32 npossible =num_possible_cpus ();s16 *cid_to_cpu, *cpu_to_cid; +s32 *cid_to_shard; +s32 *shard_node; +struct scx_cid_shard *cid_shard_ranges;struct scx_cid_topo *cid_topo;if (scx_cid_to_cpu_tbl)
@@ -55,17 +88,27 @@ static s32 scx_cid_arrays_alloc(void) cid_to_cpu =kzalloc_objs (*scx_cid_to_cpu_tbl, npossible,GFP_KERNEL ); cpu_to_cid =kzalloc_objs (*scx_cpu_to_cid_tbl, nr_cpu_ids,GFP_KERNEL ); + cid_to_shard =kzalloc_objs (*scx_cid_to_shard, npossible,GFP_KERNEL ); + shard_node =kmalloc_objs (*scx_shard_node, npossible,GFP_KERNEL ); + cid_shard_ranges =kzalloc_objs (*scx_cid_shard_ranges, npossible,GFP_KERNEL ); cid_topo =kmalloc_objs (*scx_cid_topo, npossible,GFP_KERNEL ); -if (!cid_to_cpu || !cpu_to_cid || !cid_topo) { +if (!cid_to_cpu || !cpu_to_cid || !cid_to_shard || !shard_node || + !cid_shard_ranges || !cid_topo) {kfree (cid_to_cpu);kfree (cpu_to_cid); +kfree (cid_to_shard); +kfree (shard_node); +kfree (cid_shard_ranges);kfree (cid_topo);return -ENOMEM ; }WRITE_ONCE (scx_cid_to_cpu_tbl, cid_to_cpu);WRITE_ONCE (scx_cpu_to_cid_tbl, cpu_to_cid); +WRITE_ONCE (scx_cid_to_shard, cid_to_shard); +WRITE_ONCE (scx_shard_node, shard_node); +WRITE_ONCE (scx_cid_shard_ranges, cid_shard_ranges);WRITE_ONCE (scx_cid_topo, cid_topo);return 0 ; }
@@ -90,17 +133,29 @@ s32 scx_cid_init(struct scx_sched *sch) cpumask_var_t online_no_topo __free(free_cpumask_var) = CPUMASK_VAR_NULL;u32 next_cid =0 ;s32 next_node_idx =0 , next_llc_idx =0 , next_core_idx =0 ; -s32 cpu, ret; +s32 next_shard_idx =0 ; +u32 shard_size, max_cids; +u32 notopo_in_shard; +s32 notopo_shard_cid, notopo_shard_idx; +s32 cpu, cid, si, ret;/* CMASK_MAX_WORDS in cid.bpf.h covers NR_CPUS up to 8192 */ BUILD_BUG_ON (NR_CPUS >8192 );lockdep_assert_cpus_held (); + shard_size = sch->ops.cid_shard_size ?:SCX_CID_SHARD_SIZE_DFL ; + max_cids =min_t (u32, shard_size,SCX_CID_SHARD_MAX_CPUS ); + ret =scx_cid_arrays_alloc ();if (ret)return ret; +/* clear shard ranges and reset shard_node for repopulate */ +memset (scx_cid_shard_ranges,0 ,num_possible_cpus () *sizeof (*scx_cid_shard_ranges)); +for (si =0 ; si <num_possible_cpus (); si++) + scx_shard_node[si] =NUMA_NO_NODE ; + if (!zalloc_cpumask_var(&to_walk, GFP_KERNEL) || !zalloc_cpumask_var(&node_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&llc_scratch, GFP_KERNEL) ||
@@ -142,29 +197,60 @@ s32 scx_cid_init(struct scx_sched *sch)const struct cpumask *llc_mask =cpu_llc_mask (ncpu, llc_fallback);s32 llc_cid = next_cid;s32 llc_idx = next_llc_idx++; +u32 cores_per_shard, nr_large; +u32 shard_local =0 , cores_in_shard =0 , cids_in_shard =0 ; +s32 shard_cid, shard_idx;/* llc_scratch = node_scratch & this llc */ cpumask_and (llc_scratch, node_scratch, llc_mask);if (WARN_ON_ONCE (!cpumask_test_cpu (ncpu, llc_scratch)))return -EINVAL ; +calc_shard_layout (llc_scratch, shard_size, &cores_per_shard, &nr_large); + shard_cid = next_cid; + shard_idx = next_shard_idx++; + scx_shard_node[shard_idx] = nid; +while (!cpumask_empty (llc_scratch)) {s32 lcpu =cpumask_first (llc_scratch);const struct cpumask *sib =topology_sibling_cpumask (lcpu);s32 core_cid = next_cid;s32 core_idx = next_core_idx++;s32 ccpu; +u32 max_cores, cids_in_core;/* core_scratch = llc_scratch & this core */ cpumask_and (core_scratch, llc_scratch, sib);if (WARN_ON_ONCE (!cpumask_test_cpu (lcpu, core_scratch)))return -EINVAL ; +/* +* Advance to a new shard when either core or +* cid count reaches max. The latter bounds +* shard sizes under uneven SMT. Never start an +* empty shard. +*/ + cids_in_core =cpumask_weight (core_scratch); + max_cores = cores_per_shard + (shard_local < nr_large ?1 :0 ); +if (cores_in_shard && + (cores_in_shard >= max_cores || + cids_in_shard + cids_in_core > max_cids)) { + shard_local++; + cores_in_shard =0 ; + cids_in_shard =0 ; + shard_cid = next_cid; + shard_idx = next_shard_idx++; + scx_shard_node[shard_idx] = nid; + } + cores_in_shard++; + cids_in_shard += cids_in_core; +for_each_cpu (ccpu, core_scratch) {s32 cid = next_cid++; scx_cid_to_cpu_tbl[cid] = ccpu; scx_cpu_to_cid_tbl[ccpu] = cid; + scx_cid_to_shard[cid] = shard_idx; scx_cid_topo[cid] = (struct scx_cid_topo ){ .core_cid = core_cid, .core_idx = core_idx,
@@ -172,6 +258,8 @@ s32 scx_cid_init(struct scx_sched *sch) .llc_idx = llc_idx, .node_cid = node_cid, .node_idx = node_idx, + .shard_cid = shard_cid, + .shard_idx = shard_idx, };cpumask_clear_cpu (ccpu, llc_scratch);
@@ -184,12 +272,17 @@ s32 scx_cid_init(struct scx_sched *sch)/* * No-topo section: any possible cpu without a cid - normally just the -* not-online ones. Collect any currently-online cpus that land here in -* @online_no_topo so we can warn about them at the end. +* not-online ones. Pack into shards of up to min(@shard_size, +* SCX_CID_SHARD_MAX_CPUS) cids so that every cid has a valid shard +* assignment and the hard cap holds even with a large @shard_size. +* Collect any currently-online cpus that land here in @online_no_topo +* so we can warn about them at the end. */ -for_each_cpu (cpu, cpu_possible_mask) { -s32 cid; + notopo_in_shard =min_t (u32, shard_size,SCX_CID_SHARD_MAX_CPUS ); + notopo_shard_cid =-1 ; + notopo_shard_idx =-1 ; +for_each_cpu (cpu, cpu_possible_mask) {if (__scx_cpu_to_cid (cpu) !=-1 )continue ;if (cpu_online (cpu))
@@ -198,7 +291,18 @@ s32 scx_cid_init(struct scx_sched *sch) cid = next_cid++; scx_cid_to_cpu_tbl[cid] = cpu; scx_cpu_to_cid_tbl[cpu] = cid; + +if (notopo_in_shard >=min_t (u32, shard_size,SCX_CID_SHARD_MAX_CPUS )) { + notopo_shard_cid = cid; + notopo_shard_idx = next_shard_idx++; + notopo_in_shard =0 ; + } + notopo_in_shard++; + + scx_cid_to_shard[cid] = notopo_shard_idx; scx_cid_topo[cid] =SCX_CID_TOPO_NEG ; + scx_cid_topo[cid].shard_cid = notopo_shard_cid; + scx_cid_topo[cid].shard_idx = notopo_shard_idx; }if (!cpumask_empty (llc_fallback))
@@ -208,6 +312,20 @@ s32 scx_cid_init(struct scx_sched *sch)pr_warn ("scx_cid: online cpus with no usable topology: %*pbl\n" ,cpumask_pr_args (online_no_topo)); +/* +* Fill cid_shard_ranges[] from cid_to_shard[]. Shards are contiguous +* cid ranges by construction: base_cid is the first cid landing in a +* shard, nr_cids is the count. +*/ +for (cid =0 ; cid < next_cid; cid++) { +s32 sidx = scx_cid_to_shard[cid]; + +if (scx_cid_shard_ranges[sidx].nr_cids ==0 ) + scx_cid_shard_ranges[sidx].base_cid = cid; + scx_cid_shard_ranges[sidx].nr_cids++; + } + + scx_nr_cid_shards = next_shard_idx;return 0 ; }
kernel/sched/ext/cid.h +4 -0
@@ -48,8 +48,12 @@ struct scx_sched;* See the comment above the table definitions in cid.c for the * memory-ordering and visibility contract. */ +extern u32 scx_nr_cid_shards;extern s16 *scx_cid_to_cpu_tbl;extern s16 *scx_cpu_to_cid_tbl; +extern s32 *scx_cid_to_shard; +extern s32 *scx_shard_node; +extern struct scx_cid_shard *scx_cid_shard_ranges;extern struct scx_cid_topo *scx_cid_topo;extern struct btf_id_set8 scx_kfunc_ids_init_cids;
kernel/sched/ext/ext.c +4 -0
@@ -7172,6 +7172,9 @@ static int bpf_scx_init_member(const struct btf_type *t,case offsetof(struct sched_ext_ops , hotplug_seq): ops->hotplug_seq = *(u64 *)(udata + moff);return 1 ; +case offsetof(struct sched_ext_ops , cid_shard_size): + ops->cid_shard_size = *(u32 *)(udata + moff); +return 1 ;#ifdef CONFIG_EXT_SUB_SCHED case offsetof(struct sched_ext_ops , sub_cgroup_id): ops->sub_cgroup_id = *(u64 *)(udata + moff);
@@ -9865,6 +9868,7 @@ static int __init scx_init(void)CID_OFFSET_MATCH (timeout_ms, timeout_ms);CID_OFFSET_MATCH (exit_dump_len, exit_dump_len);CID_OFFSET_MATCH (hotplug_seq, hotplug_seq); +CID_OFFSET_MATCH (cid_shard_size, cid_shard_size);CID_OFFSET_MATCH (sub_cgroup_id, sub_cgroup_id);/* shared callbacks: the union view requires byte-for-byte offset match */ CID_OFFSET_MATCH (enqueue, enqueue);
kernel/sched/ext/internal.h +13 -0
@@ -845,6 +845,18 @@ struct sched_ext_ops {*/ u64 hotplug_seq; +/** +* @cid_shard_size: Target number of CIDs per shard +* +* Shards are contiguous CID ranges used as operation and locking +* domains for sub-scheduling. Each LLC is divided into ceil(nr_cpus / +* @cid_shard_size) shards, then cores are distributed across them +* evenly. If one core has more logical CPUs than @cid_shard_size, its +* shard will become larger than @cid_shard_size. Values above +* SCX_CID_SHARD_MAX_CPUS are capped. 0 means use the default (24). +*/ +u32 cid_shard_size; +/** * @cgroup_id: When >1, attach the scheduler as a sub-scheduler on the * specified cgroup.
@@ -977,6 +989,7 @@ struct sched_ext_ops_cid {u32 timeout_ms;u32 exit_dump_len;u64 hotplug_seq; +u32 cid_shard_size;u64 sub_cgroup_id;char name[SCX_OPS_NAME_LEN ];
kernel/sched/ext/types.h +30 -5
@@ -47,11 +47,16 @@ enum scx_consts { };/* -* Per-cid topology info. For each topology level (core, LLC, node), records -* the first cid in the unit and its global index. Global indices are -* consecutive integers assigned in cid-walk order, so e.g. core_idx ranges -* over [0, nr_cores_at_init) with no gaps. No-topo cids have all fields set -* to -1. +* Per-cid topology info. For each topology level (core, LLC, node) and shard, +* records the first cid in the unit and its global index. Global indices are +* consecutive integers assigned in cid-walk order, so e.g. core_idx ranges over +* [0, nr_cores_at_init) with no gaps. No-topo cids have core/LLC/node fields +* set to -1 but always have valid shard assignments. +* +* Shards are contiguous CID ranges used as scalable locking/work domains for +* sub-scheduler operations. By default each LLC becomes one shard, split into +* smaller shards if the LLC exceeds the target size. No-topo cids are packed +* into their own max-sized shards. * * @core_cid: first cid of this cid's core (smt-sibling group) * @core_idx: global index of that core, in [0, nr_cores_at_init)
@@ -59,6 +64,8 @@ enum scx_consts {* @llc_idx: global index of that LLC, in [0, nr_llcs_at_init) * @node_cid: first cid of this cid's NUMA node * @node_idx: global index of that node, in [0, nr_nodes_at_init) +* @shard_cid: first cid of this cid's shard +* @shard_idx: global index of that shard, in [0, scx_nr_cid_shards) */ struct scx_cid_topo {s32 core_cid;
@@ -67,6 +74,24 @@ struct scx_cid_topo {s32 llc_idx;s32 node_cid;s32 node_idx; +s32 shard_cid; +s32 shard_idx; +}; + +enum scx_cid_consts { +SCX_CID_SHARD_SIZE_DFL =24 , +SCX_CID_SHARD_MAX_CPUS =512 , +}; + +/* +* Per-shard metadata for O(1) shard->cid-range lookup. +* +* @base_cid: first cid of the shard +* @nr_cids: number of cids in the shard +*/ +struct scx_cid_shard { +s32 base_cid; +s32 nr_cids; };/*
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 5/33 sched_ext: Add shard boundaries to scx_bpf_cid_override()
In reply to Tejun HeoAn overridden cid mapping invalidates the auto-generated shard layout, so the override call has to provide both. Extend scx_bpf_cid_override() with a shard_start[] array that lists the first cid of each shard (starting at 0, strictly increasing, last shard implicitly extends to num_possible_cpus()).
A scheduler that wants only custom shards with the auto-generated cid mapping can read the current mapping and pass it back unchanged.
Overridden shards can span NUMA nodes, so scx_shard_node[] is rebuilt by majority count: each shard is assigned to the node that owns the most cpus in it.
v2: Snapshot the caller's cpu_to_cid/shard_start arrays before validating. (sashiko AI)
--- kernel/sched/ext/cid.c | 154 ++++++++++++++++++++--- tools/sched_ext/include/scx/compat.bpf.h | 11 +- tools/sched_ext/scx_qmap.bpf.c | 16 ++- tools/sched_ext/scx_qmap.c | 34 ++++- tools/sched_ext/scx_qmap.h | 1 + 5 files changed, 187 insertions(+), 29 deletions(-)
kernel/sched/ext/cid.c +137 -17
@@ -392,29 +392,66 @@ void scx_cpumask_to_cmask(const struct cpumask *src, struct scx_cmask *dst) } } +/* +* Return the index of the largest entry in @counts, or NUMA_NO_NODE if all +* entries are zero. Ties resolve to the lowest index. +*/ +static s32 pick_max_node (const u32 *counts,u32 n) +{ +s32 best =NUMA_NO_NODE ; +u32 best_count =0 , i; + +for (i =0 ; i < n; i++) { +if (counts[i] > best_count) { + best_count = counts[i]; + best = i; + } + } +return best; +} +__bpf_kfunc_start_defs ();/** -* scx_bpf_cid_override - Install an explicit cpu->cid mapping -* @cpu_to_cid: array of nr_cpu_ids s32 entries (cid for each cpu) -* @cpu_to_cid__sz: must be nr_cpu_ids * sizeof(s32) bytes +* scx_bpf_cid_override - Install an explicit cpu->cid mapping with shard info +* @cpu_to_cid_src: array of nr_cpu_ids s32 entries (cid for each cpu) +* @cpu_to_cid_src__sz: must be nr_cpu_ids * sizeof(s32) bytes +* @shard_start_src: array of first-cid-of-each-shard, strictly increasing from 0 +* @shard_start_src__sz: nr_shards * sizeof(s32) bytes * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * * May only be called from ops.init_cids() of the root scheduler. Replace the -* topology-probed cid mapping with the caller-provided one. Each possible cpu -* must map to a unique cid in [0, num_possible_cpus()). Topo info is cleared. -* On invalid input, trigger scx_error() to abort the scheduler. +* topology-probed cid mapping and shard layout with caller-provided ones. Each +* possible cpu must map to a unique cid in [0, num_possible_cpus()). The shard +* starts must be strictly increasing with the first entry 0 and all values < +* num_possible_cpus(). The last shard extends to num_possible_cpus() and no +* shard may span more than SCX_CID_SHARD_MAX_CPUS cids. Topo info +* (core/LLC/node) is cleared and the shard layout is set from the input. On +* invalid input, abort the scheduler. */ -__bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid, u32 cpu_to_cid__sz, -const struct bpf_prog_aux *aux) +__bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid_src, u32 cpu_to_cid_src__sz, +const s32 *shard_start_src,u32 shard_start_src__sz, +const struct bpf_prog_aux *aux) { cpumask_var_t seen __free(free_cpumask_var) = CPUMASK_VAR_NULL; + u32 *node_counts __free(kfree) = NULL; + s32 *cpu_to_cid __free(kfree) = NULL; + s32 *shard_start __free(kfree) = NULL; +u32 npossible =num_possible_cpus ();struct scx_sched *sch; +u32 nr_shards;bool alloced; -s32 cpu, cid; +s32 cpu, cid, si; -/* GFP_KERNEL alloc must happen before the rcu read section */ +/* +* GFP_KERNEL allocs must happen before the rcu read section. Snapshot +* the BPF-supplied arrays so a concurrent map mutation can't change +* them between validation and use. +*/ alloced =zalloc_cpumask_var (&seen,GFP_KERNEL ); + node_counts =kcalloc (nr_node_ids,sizeof (*node_counts),GFP_KERNEL ); + cpu_to_cid =kmemdup (cpu_to_cid_src, cpu_to_cid_src__sz,GFP_KERNEL ); + shard_start =kmemdup (shard_start_src, shard_start_src__sz,GFP_KERNEL );guard (rcu)();
@@ -422,17 +459,57 @@ __bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid, u32 cpu_to_cid__sz,if (unlikely (!sch))return ; -if (!alloced) { -scx_error (sch,"scx_bpf_cid_override: failed to allocate cpumask" ); +if (!alloced || !node_counts || !cpu_to_cid || !shard_start) { +scx_error (sch,"scx_bpf_cid_override: allocation failed" );return ; } -if (cpu_to_cid__sz != nr_cpu_ids *sizeof (s32)) { -scx_error (sch,"scx_bpf_cid_override: expected %zu bytes, got %u" , - nr_cpu_ids *sizeof (s32), cpu_to_cid__sz); +if (cpu_to_cid_src__sz != nr_cpu_ids *sizeof (s32)) { +scx_error (sch,"scx_bpf_cid_override: cpu_to_cid expected %zu bytes, got %u" , + nr_cpu_ids *sizeof (s32), cpu_to_cid_src__sz); +return ; + } + +if (!shard_start_src__sz || shard_start_src__sz %sizeof (s32)) { +scx_error (sch,"scx_bpf_cid_override: invalid shard_start size %u" , + shard_start_src__sz); +return ; + } + + nr_shards = shard_start_src__sz /sizeof (s32); + +/* validate shard_start[]: starts at 0, strictly increasing, in range */ +if (shard_start[0 ] !=0 ) { +scx_error (sch,"scx_bpf_cid_override: shard_start[0] must be 0, got %d" , + shard_start[0 ]); +return ; + } +for (si =1 ; si < nr_shards; si++) { +if (shard_start[si] <= shard_start[si -1 ]) { +scx_error (sch,"scx_bpf_cid_override: shard_start not increasing at [%d]" , + si); +return ; + } +if (shard_start[si] >= npossible) { +scx_error (sch,"scx_bpf_cid_override: shard_start[%d]=%d >= %u" , + si, shard_start[si], npossible); +return ; + } +if (shard_start[si] - shard_start[si -1 ] >SCX_CID_SHARD_MAX_CPUS ) { +scx_error (sch,"scx_bpf_cid_override: shard[%d] span %d exceeds max %d" , + si -1 , shard_start[si] - shard_start[si -1 ], +SCX_CID_SHARD_MAX_CPUS ); +return ; + } + } +if (npossible - shard_start[nr_shards -1 ] >SCX_CID_SHARD_MAX_CPUS ) { +scx_error (sch,"scx_bpf_cid_override: shard[%d] span %d exceeds max %d" , + nr_shards -1 , npossible - shard_start[nr_shards -1 ], +SCX_CID_SHARD_MAX_CPUS );return ; } +/* Validate first so that invalid input leaves globals untouched. */ for_each_possible_cpu (cpu) {s32 c = cpu_to_cid[cpu];
@@ -442,13 +519,56 @@ __bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid, u32 cpu_to_cid__sz,scx_error (sch,"cid %d assigned to multiple cpus" , c);return ; } + } + +for_each_possible_cpu (cpu) { +s32 c = cpu_to_cid[cpu]; + scx_cpu_to_cid_tbl[cpu] = c; scx_cid_to_cpu_tbl[c] = cpu; } -/* Invalidate stale topo info - the override carries no topology. */ -for (cid =0 ; cid <num_possible_cpus (); cid++) +/* +* Derive scx_shard_node[] by majority count: an overridden shard may +* span NUMA nodes, so assign each to the node that owns the most cpus. +*/ +for (si =0 ; si < nr_shards; si++) { +u32 end = (si +1 < nr_shards) ? shard_start[si +1 ] : npossible; + +memset (node_counts,0 , nr_node_ids *sizeof (*node_counts)); +for (cid = shard_start[si]; cid < end; cid++) { +s32 node =cpu_to_node (scx_cid_to_cpu_tbl[cid]); + +if (numa_valid_node (node)) + node_counts[node]++; + } + scx_shard_node[si] =pick_max_node (node_counts, nr_node_ids); + } + +/* +* Invalidate stale topo info and install shard layout from +* @shard_start. Walk shards to derive shard_cid/shard_idx for each cid. +*/ + si =0 ; +for (cid =0 ; cid < npossible; cid++) { +if (si +1 < nr_shards && cid >= shard_start[si +1 ]) + si++; + scx_cid_to_shard[cid] = si; scx_cid_topo[cid] =SCX_CID_TOPO_NEG ; + scx_cid_topo[cid].shard_cid = shard_start[si]; + scx_cid_topo[cid].shard_idx = si; + } + +/* Rebuild scx_cid_shard_ranges[] for the new layout. */ +memset (scx_cid_shard_ranges,0 , npossible *sizeof (*scx_cid_shard_ranges)); +for (si =0 ; si < nr_shards; si++) { +u32 end = (si +1 < nr_shards) ? shard_start[si +1 ] : npossible; + + scx_cid_shard_ranges[si].base_cid = shard_start[si]; + scx_cid_shard_ranges[si].nr_cids = end - shard_start[si]; + } + + scx_nr_cid_shards = nr_shards; }/**
tools/sched_ext/include/scx/compat.bpf.h +7 -4
@@ -122,15 +122,18 @@ static inline bool scx_bpf_sub_dispatch(u64 cgroup_id) }/* -* v7.2: scx_bpf_cid_override() for explicit cpu->cid mapping. Ignore if +* v7.3: scx_bpf_cid_override() for explicit cid and shard mapping. Ignore if * missing. */ -void scx_bpf_cid_override___compat(const s32 *cpu_to_cid, u32 cpu_to_cid__sz) __ksym __weak; +void scx_bpf_cid_override___compat(const s32 *cpu_to_cid, u32 cpu_to_cid__sz, + const s32 *shard_start, u32 shard_start__sz) __ksym __weak; -static inline void scx_bpf_cid_override (const s32 *cpu_to_cid,u32 cpu_to_cid__sz) +static inline void scx_bpf_cid_override (const s32 *cpu_to_cid,u32 cpu_to_cid__sz, +const s32 *shard_start,u32 shard_start__sz) {if (bpf_ksym_exists (scx_bpf_cid_override___compat)) -return scx_bpf_cid_override___compat (cpu_to_cid, cpu_to_cid__sz); +scx_bpf_cid_override___compat (cpu_to_cid, cpu_to_cid__sz, + shard_start, shard_start__sz); }/**
tools/sched_ext/scx_qmap.bpf.c +10 -6
@@ -54,18 +54,20 @@ const volatile u32 max_tasks;/* * Optional cid-override test harness. When cid_override_mode is non-zero, -* qmap_init_cids() calls scx_bpf_cid_override() with the caller-supplied -* cpu_to_cid array to exercise the kfunc's acceptance and error paths. See enum +* qmap_init_cids() calls scx_bpf_cid_override() with the caller-supplied arrays +* to exercise the kfunc's acceptance and error paths. See enum * qmap_cid_override for the modes. */ const volatile u32 cid_override_mode; +const volatile u32 cid_override_nr_shards;/* -* Array lives in bss (writable) because scx_bpf_cid_override()'s BPF -* verifier signature treats its len-paired pointer as read/write - rodata +* Arrays live in bss (writable) because scx_bpf_cid_override()'s BPF +* verifier signature treats its len-paired pointers as read/write - rodata * fails verification with "write into map forbidden". Userspace populates -* it before SCX_OPS_LOAD, same as rodata, and nothing writes it after. +* them before SCX_OPS_LOAD, same as rodata, and nothing writes them after. */ s32 cid_override_cpu_to_cid[SCX_QMAP_MAX_CPUS ]; +s32 cid_override_shard_start[SCX_QMAP_MAX_CPUS ];UEI_DEFINE (uei);
@@ -1082,7 +1084,9 @@ s32 BPF_STRUCT_OPS_SLEEPABLE(qmap_init_cids) }scx_bpf_cid_override ((const s32 *)cid_override_cpu_to_cid, - nr_cpu_ids *sizeof (s32)); + nr_cpu_ids *sizeof (s32), + (const s32 *)cid_override_shard_start, + cid_override_nr_shards *sizeof (s32));return 0 ; }
tools/sched_ext/scx_qmap.c +32 -2
@@ -43,7 +43,7 @@ const char help_fmt[] =" -p Switch only tasks on SCHED_EXT policy instead of all\n" " -I Turn on SCX_OPS_ALWAYS_ENQ_IMMED\n" " -F COUNT IMMED stress: force every COUNT'th enqueue to a busy local DSQ (use with -I)\n" -" -C MODE cid-override test (shuffle|bad-dup|bad-range)\n" +" -C MODE cid-override test (shuffle|bad-dup|bad-range|bad-mono)\n" " -v Print libbpf debug messages\n" " -h Display this help and exit\n" ;
@@ -155,6 +155,7 @@ int main(int argc, char **argv)case 'C' : {u32 nr_cpus =libbpf_num_possible_cpus ();u32 mode, i; +s32 shard_sz =4 ;if (!strcmp (optarg,"shuffle" )) mode =QMAP_CID_OVR_SHUFFLE ;
@@ -162,13 +163,15 @@ int main(int argc, char **argv) mode =QMAP_CID_OVR_BAD_DUP ; else if (!strcmp(optarg, "bad-range")) mode =QMAP_CID_OVR_BAD_RANGE ; + else if (!strcmp(optarg, "bad-mono")) + mode =QMAP_CID_OVR_BAD_MONO ; else {fprintf (stderr,"unknown cid-override mode '%s'\n" , optarg);return 1 ; } skel->rodata->cid_override_mode = mode; -/* shuffle: reversed cpu_to_cid, bad-dup: dup cid 0, bad-range: identity */ +/* shuffle: reversed cpu_to_cid; others: identity */ for (i =0 ; i < nr_cpus; i++) {if (mode ==QMAP_CID_OVR_SHUFFLE ) skel->bss->cid_override_cpu_to_cid[i] = nr_cpus -1 - i;
@@ -179,6 +182,33 @@ int main(int argc, char **argv) skel->bss->cid_override_cpu_to_cid[1 ] =0 ;if (mode ==QMAP_CID_OVR_BAD_RANGE ) skel->bss->cid_override_cpu_to_cid[0 ] = (s32 )nr_cpus; + +/* +* bad-mono needs >= 3 shards to build a 0-based but +* non-monotonic shard_start. Shrink the shard size so +* the test runs on any machine with >= 3 cpus. +*/ +if (mode ==QMAP_CID_OVR_BAD_MONO ) { +if (nr_cpus <3 ) { +fprintf (stderr,"bad-mono needs >= 3 cpus (have %u)\n" , + nr_cpus); +return 1 ; + } + shard_sz = nr_cpus /3 ; + } + +/* shards of shard_sz each */ + skel->rodata->cid_override_nr_shards = (nr_cpus + shard_sz -1 ) / shard_sz; +for (i =0 ; i < skel->rodata->cid_override_nr_shards; i++) + skel->bss->cid_override_shard_start[i] = i * shard_sz; + +if (mode ==QMAP_CID_OVR_BAD_MONO ) { +/* swap [1] and [2] to break monotonicity */ +s32 tmp = skel->bss->cid_override_shard_start[1 ]; + skel->bss->cid_override_shard_start[1 ] = + skel->bss->cid_override_shard_start[2 ]; + skel->bss->cid_override_shard_start[2 ] = tmp; + }break ; }case 'v' :
tools/sched_ext/scx_qmap.h +1 -0
@@ -33,6 +33,7 @@ enum qmap_cid_override {QMAP_CID_OVR_SHUFFLE =1 ,/* valid reversed cpu->cid mapping */ QMAP_CID_OVR_BAD_DUP =2 ,/* invalid: duplicate cid assignment */ QMAP_CID_OVR_BAD_RANGE =3 ,/* invalid: out-of-range cid */ + QMAP_CID_OVR_BAD_MONO = 4, /* invalid: non-monotonic shard_start */ }; struct cpu_ctx {
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 6/33 sched_ext: Defer scx_sched kobj sysfs add into the enable workfns
In reply to Tejun HeoSplit kobject_init_and_add() in scx_alloc_and_add_sched(): only kobject_init() runs there. A new scx_sched_sysfs_add() helper does kobject_add() (and creates sub_kset when the scheduler implements ops.sub_attach), called by both enable workfns once @sch is linked and its sysfs-visible state is initialized. Prep so a future caps attribute can rely on @sch being fully built by the time it's sysfs-visible. Add early enough that a stall later in enable still leaves sysfs inspectable.
--- kernel/sched/ext/ext.c | 73 +++++++++++++++++++++++-------------- kernel/sched/ext/internal.h | 1 + kernel/sched/ext/sub.c | 8 +++- 3 files changed, 53 insertions(+), 29 deletions(-)
kernel/sched/ext/ext.c +45 -28
@@ -5735,7 +5735,9 @@ static void scx_root_disable(struct scx_sched *sch)if (sch->sub_kset)kobject_del (&sch->sub_kset->kobj);#endif -kobject_del (&sch->kobj); +/* not added if enable failed before scx_sched_sysfs_add() */ +if (sch->kobj.state_in_sysfs) +kobject_del (&sch->kobj);free_kick_syncs ();
@@ -6452,36 +6454,15 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd,* disable. Released in scx_sched_free_rcu_work(). */ kobject_get(&parent->kobj); - ret =kobject_init_and_add (&sch->kobj, &scx_ktype, - &parent->sub_kset->kobj, - "sub-%llu", cgroup_id(cgrp)); - }else { - ret =kobject_init_and_add (&sch->kobj, &scx_ktype,NULL ,"root" ); - } - -if (ret <0 ) { -RCU_INIT_POINTER (ops->priv,NULL ); -kobject_put (&sch->kobj); -return ERR_PTR (ret); - } - -if (ops->sub_attach) { - sch->sub_kset =kset_create_and_add ("sub" ,NULL , &sch->kobj); -if (!sch->sub_kset) { -RCU_INIT_POINTER (ops->priv,NULL ); -kobject_put (&sch->kobj); -return ERR_PTR (-ENOMEM ); - } - } -#else /* CONFIG_EXT_SUB_SCHED */ - ret =kobject_init_and_add (&sch->kobj, &scx_ktype,NULL ,"root" ); -if (ret <0 ) { -RCU_INIT_POINTER (ops->priv,NULL ); -kobject_put (&sch->kobj); -return ERR_PTR (ret); }#endif /* CONFIG_EXT_SUB_SCHED */ +/* +* Init the kobj but don't add to sysfs yet. The enable path calls +* scx_sched_sysfs_add() once @sch's sysfs-visible state is initialized. +*/ +kobject_init (&sch->kobj, &scx_ktype); +/* * Consume the arena_map ref bpf_scx_reg_cid() took. Defer to here so * earlier failure paths leave cmd->arena_map set and bpf_scx_reg_cid
@@ -6539,6 +6520,36 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd,return ERR_PTR (ret); } +/* +* Add @sch's kobject to sysfs, and create its sub_kset if the scheduler +* implements ops.sub_attach. Called by the enable workfns once @sch's +* sysfs-visible state is initialized. +*/ +int scx_sched_sysfs_add (struct scx_sched *sch) +{ +#ifdef CONFIG_EXT_SUB_SCHED +struct scx_sched *parent =scx_parent (sch); +int ret; + +if (parent) + ret =kobject_add (&sch->kobj, &parent->sub_kset->kobj, +"sub-%llu" ,cgroup_id (sch_cgroup (sch))); +else + ret =kobject_add (&sch->kobj,NULL ,"root" ); +if (ret <0 ) +return ret; + +if (sch->ops.sub_attach) { + sch->sub_kset =kset_create_and_add ("sub" ,NULL , &sch->kobj); +if (!sch->sub_kset) +return -ENOMEM ; + } +return 0 ; +#else +return kobject_add (&sch->kobj,NULL ,"root" ); +#endif +} +static int check_hotplug_seq (struct scx_sched *sch,const struct sched_ext_ops *ops) {
@@ -6761,6 +6772,12 @@ static void scx_root_enable_workfn(struct kthread_work *work) sch->exit_info->flags |=SCX_EFLAG_INITIALIZED ; } + ret =scx_sched_sysfs_add (sch); +if (ret) { +cpus_read_unlock (); + goto err_disable; + } +for (i =SCX_OPI_CPU_HOTPLUG_BEGIN ; i <SCX_OPI_CPU_HOTPLUG_END ; i++)if (((void (**)(void ))ops)[i])set_bit (i, sch->has_op);
kernel/sched/ext/internal.h +1 -0
@@ -1690,6 +1690,7 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd,struct cgroup *cgrp, struct scx_sched *parent);int scx_validate_ops (struct scx_sched *sch,const struct sched_ext_ops *ops); +int scx_sched_sysfs_add (struct scx_sched *sch);extern raw_spinlock_t scx_sched_lock;extern struct mutex scx_enable_mutex;
kernel/sched/ext/sub.c +7 -1
@@ -270,7 +270,9 @@ void scx_sub_disable(struct scx_sched *sch)SCX_CALL_OP (sch, exit,NULL , sch->exit_info);if (sch->sub_kset)kobject_del (&sch->sub_kset->kobj); -kobject_del (&sch->kobj); +/* not added if enable failed before scx_sched_sysfs_add() */ +if (sch->kobj.state_in_sysfs) +kobject_del (&sch->kobj); }/* verify that a scheduler can be attached to @cgrp and return the parent */
@@ -363,6 +365,10 @@ void scx_sub_enable_workfn(struct kthread_work *work)if (ret) goto err_disable; + ret =scx_sched_sysfs_add (sch); +if (ret) + goto err_disable; +if (sch->level >=SCX_SUB_MAX_DEPTH ) {scx_error (sch,"max nesting depth %d violated" ,SCX_SUB_MAX_DEPTH );
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 7/33 sched_ext: Add per-shard scx_sched storage scaffolding
In reply to Tejun HeoAdd struct scx_pshard and sch->pshard[] indexed by shard_idx, each entry allocated on its shard's NUMA node from scx_shard_node[si]. The struct starts empty (one dummy field). Follow-up patches will grow it as shard-local state lands. Only cid-type schedulers with an arena pool get pshards.
Allocation happens after ops.init_cids() returns so any scx_bpf_cid_override() it issues has finalized scx_nr_cid_shards and scx_shard_node[]. sch->nr_pshards records the array size for the async RCU free path, which may run after a later scheduler's scx_cid_init() has rewritten the global.
v3: Build and publish pshard[] fully-formed here rather than a later patch.
v2: Free the partially-allocated pshard array on alloc failure. (sashiko AI)
--- kernel/sched/ext/ext.c | 8 ++++++ kernel/sched/ext/internal.h | 18 +++++++++++++ kernel/sched/ext/sub.c | 54 +++++++++++++++++++++++++++++++++++++ kernel/sched/ext/sub.h | 4 +++ 4 files changed, 84 insertions(+)
kernel/sched/ext/ext.c +8 -0
@@ -4681,6 +4681,8 @@ static void scx_sched_free_rcu_work(struct work_struct *work)free_pnode (sch->pnode[node]);kfree (sch->pnode); +scx_free_pshards (sch); +rhashtable_walk_enter (&sch->dsq_hash, &rht_iter); do { rhashtable_walk_start(&rht_iter);
@@ -6761,6 +6763,12 @@ static void scx_root_enable_workfn(struct kthread_work *work) goto err_disable; } + ret =scx_alloc_pshards (sch); +if (ret) { +cpus_read_unlock (); + goto err_disable; + } +if (sch->ops.init) { ret =SCX_CALL_OP_RET (sch, init,NULL );if (ret) {
kernel/sched/ext/internal.h +18 -0
@@ -1183,6 +1183,12 @@ struct scx_sched_pnode {struct scx_dispatch_q global_dsq; }; +#ifdef CONFIG_EXT_SUB_SCHED +struct scx_pshard { +int _dummy;/* until the first real field lands */ +}; +#endif +struct scx_sched {/* * cpu-form and cid-form ops share field offsets up to .priv (verified
@@ -1230,6 +1236,9 @@ struct scx_sched {*/ struct rhashtable dsq_hash;struct scx_sched_pnode **pnode; +#ifdef CONFIG_EXT_SUB_SCHED +struct scx_pshard **pshard;/* indexed by shard_idx */ +#endif struct scx_sched_pcpu __percpu *pcpu;u64 slice_dfl;
@@ -1245,6 +1254,15 @@ struct scx_sched {u32 dsp_max_batch;s32 level; +#ifdef CONFIG_EXT_SUB_SCHED +/* +* pshard[] size captured at enable for the async RCU free path - +* scx_nr_cid_shards may be rewritten by a later scx_cid_init() before +* free runs. While sch is active, use the global. +*/ +u32 nr_pshards; +#endif +/* * Updates to the following warned bitfields can race causing RMW issues * but it doesn't really matter.
kernel/sched/ext/sub.c +54 -0
60 lines not on this page · raw message
kernel/sched/ext/sub.h +4 -0
@@ -24,6 +24,8 @@ void drain_descendants(struct scx_sched *sch);void scx_sub_disable (struct scx_sched *sch);void scx_sub_enable_workfn (struct kthread_work *work);bool scx_bpf_sub_dispatch (u64 cgroup_id,const struct bpf_prog_aux *aux); +void scx_free_pshards (struct scx_sched *sch); +s32 scx_alloc_pshards (struct scx_sched *sch);#else /* CONFIG_EXT_SUB_SCHED */
@@ -33,6 +35,8 @@ static inline struct cgroup *sch_cgroup(struct scx_sched *sch) { return NULL; }static inline void set_cgroup_sched (struct cgroup *cgrp,struct scx_sched *sch) {}static inline void drain_descendants (struct scx_sched *sch) { }static inline void scx_sub_disable (struct scx_sched *sch) { } +static inline void scx_free_pshards (struct scx_sched *sch) {} +static inline s32 scx_alloc_pshards (struct scx_sched *sch) {return 0 ; }#endif /* CONFIG_EXT_SUB_SCHED */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 8/33 sched_ext: Add scx_cmask_ref for validated arena cmask access
In reply to Tejun Heokfuncs taking struct scx_cmask * from BPF arena memory have two problems. The pointer can be any value the BPF prog hands in, and the header (@base, @nr_cids, @alloc_words) can be mutated by the prog concurrently with kernel access.
Add scx_cmask_ref, a validated handle. _init() normalizes the input pointer into the arena's kern_vm range via scx_arena_to_kaddr() and snapshots the header, rejecting a range outside the machine or a nr_cids whose words exceed the declared @alloc_words. Downstream sizing uses the snapshot, not the live header. _shard() reads slices while _or() and _copy() write back, all bounded by the snapshot. No callers yet.
struct scx_cmask's bits[] carried __counted_by(alloc_words), so UBSAN_BOUNDS and FORTIFY_SOURCE bound accesses to the array. That bound is read from @alloc_words at the access. For an arena cmask @alloc_words is BPF-writable. A prog that sets it larger than the real allocation makes the check pass on a genuine overrun, so the annotation catches nothing, and it only runs under those debug configs. Drop it - _init() validates @alloc_words explicitly, and kernel-owned cmasks set it themselves.
v2: Validate @alloc_words in _init(), drop __counted_by. (Andrea, sashiko AI)
--- kernel/sched/ext/cid.c | 133 +++++++++++++++++++++++++++++++++++++++ kernel/sched/ext/cid.h | 7 +++ kernel/sched/ext/types.h | 39 +++++++++++- 3 files changed, 178 insertions(+), 1 deletion(-)
kernel/sched/ext/cid.c +133 -0
@@ -641,6 +641,12 @@ enum cmask_op2 {/* predicates - short-circuit when the per-word result is true */ CMASK_OP2_SUBSET ,CMASK_OP2_INTERSECTS , +/* +* @a is a BPF-arena cmask. Words on @a use READ_ONCE/WRITE_ONCE since +* BPF may read/write concurrently. See scx_cmask_ref_or() / _copy(). +*/ +CMASK_OP2_REF_OR , + CMASK_OP2_REF_COPY, }; static __always_inline bool cmask_op2_is_pred(const enum cmask_op2 op)
@@ -669,6 +675,12 @@ static __always_inline bool cmask_word_op2(u64 *av, const u64 *bp, u64 mask,return (READ_ONCE (*bp) & ~READ_ONCE (*av)) & mask;case CMASK_OP2_INTERSECTS :return (READ_ONCE (*av) &READ_ONCE (*bp)) & mask; +case CMASK_OP2_REF_OR : +WRITE_ONCE (*av,READ_ONCE (*av) | (READ_ONCE (*bp) & mask)); +return false; +case CMASK_OP2_REF_COPY : +WRITE_ONCE (*av, (READ_ONCE (*av) & ~mask) | (READ_ONCE (*bp) & mask)); +return false; }unreachable (); }
@@ -899,6 +911,127 @@ static const struct btf_kfunc_id_set scx_kfunc_set_cid = { .set = &scx_kfunc_ids_cid, }; +/** +* scx_cmask_ref_init - Bind a scx_cmask_ref to a BPF-arena cmask +* @sch: scheduler whose arena hosts @src +* @src: BPF-supplied cmask pointer +* @ref: output ref +* +* Snapshot @src's @base, @nr_cids and @alloc_words. The snapshot is necessary +* because BPF may mutate the live header asynchronously. +* +* Return 0 on success, -EINVAL if the range is out of bounds or @alloc_words +* doesn't cover it. +*/ +int scx_cmask_ref_init (struct scx_sched *sch,const struct scx_cmask *src, +struct scx_cmask_ref *ref) +{ +struct scx_cmask *kern_src =scx_arena_to_kaddr (sch, src); +u32 base, nr_cids, alloc_words, npossible =num_possible_cpus (); + + base =READ_ONCE (kern_src->base); + nr_cids =READ_ONCE (kern_src->nr_cids); + alloc_words =READ_ONCE (kern_src->alloc_words); + +if (unlikely (base >= npossible || nr_cids > npossible - base || +SCX_CMASK_NR_WORDS (nr_cids) > alloc_words)) +return -EINVAL ; + + ref->sch = sch; + ref->src = kern_src; + ref->base = base; + ref->nr_cids = nr_cids; + + ref->shard_first = scx_cid_to_shard[base]; +if (likely (nr_cids)) + ref->shard_end = scx_cid_to_shard[base + nr_cids -1 ] +1 ; +else + ref->shard_end = ref->shard_first; + +return 0 ; +} + +/** +* scx_cmask_ref_shard - Read one shard from @ref into @out +* @ref: validated ref +* @shard_idx: target shard, in [@ref->shard_first, @ref->shard_end) +* @out: output cmask whose @out->alloc_words must hold the shard +* +* Set @out to the intersection of @ref's range with @shard_idx's cid range, +* with bits[] read from @ref->src via READ_ONCE. Empty intersection sets +* @out->nr_cids to 0. scx_error()s on @ref's sched if @out can't hold the +* shard. +*/ +void scx_cmask_ref_shard (const struct scx_cmask_ref *ref,s32 shard_idx, +struct scx_cmask *out) +{ +const struct scx_cid_shard *shard = &scx_cid_shard_ranges[shard_idx]; +u32 shard_base = shard->base_cid; +u32 shard_end = shard_base + shard->nr_cids; +u32 isect_base, isect_end, nr_words, src_off, wi; +u64 head_mask, tail_mask; + + isect_base =max (ref->base, shard_base); + isect_end =min (ref->base + ref->nr_cids, shard_end); + +if (isect_base >= isect_end) { + out->base = shard_base; + out->nr_cids =0 ; +return ; + } + + nr_words = ((isect_end -1 ) /64 ) - (isect_base /64 ) +1 ; +if (nr_words > out->alloc_words) { +scx_error (ref->sch,"scx_cmask_ref_shard: out alloc_words=%u < %u for shard %d" , + out->alloc_words, nr_words, shard_idx); + out->base = shard_base; + out->nr_cids =0 ; +return ; + } + + out->base = isect_base; + out->nr_cids = isect_end - isect_base; + src_off = (isect_base /64 ) - (ref->base /64 ); + +for (wi =0 ; wi < nr_words; wi++) + out->bits[wi] =READ_ONCE (ref->src->bits[src_off + wi]); + + head_mask =GENMASK_U64 (63 , isect_base &63 ); + out->bits[0 ] &= head_mask; + tail_mask =GENMASK_U64 ((isect_end -1 ) &63 ,0 ); + out->bits[nr_words -1 ] &= tail_mask; +} + +/** +* scx_cmask_ref_or - OR @src into the arena cmask referenced by @ref +* @ref: validated ref +* @src: stable kernel cmask +* +* Bits inside the intersection of @ref's snapshotted range with @src's range +* are OR'd into @ref->src and bits outside are left unchanged. Stores on +* @ref->src use WRITE_ONCE since BPF may read/write concurrently. +*/ +void scx_cmask_ref_or (const struct scx_cmask_ref *ref,const struct scx_cmask *src) +{ +cmask_walk_op2 (ref->src->bits, ref->base, ref->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_REF_OR ); +} + +/** +* scx_cmask_ref_copy - Copy @src into the arena cmask referenced by @ref +* @ref: validated ref +* @src: stable kernel cmask +* +* Bits inside the intersection of @ref's snapshotted range with @src's range +* take @src's values and bits outside are left unchanged. Stores on @ref->src +* use WRITE_ONCE since BPF may read/write concurrently. +*/ +void scx_cmask_ref_copy (const struct scx_cmask_ref *ref,const struct scx_cmask *src) +{ +cmask_walk_op2 (ref->src->bits, ref->base, ref->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_REF_COPY ); +} +int scx_cid_kfunc_init (void ) { return register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_init_cids) ?:
kernel/sched/ext/cid.h +7 -0
@@ -293,4 +293,11 @@ static inline s32 scx_cpu_ret(struct scx_sched *sch, s32 cpu_or_cid) return scx_cid_to_cpu(sch, cpu_or_cid); } +int scx_cmask_ref_init (struct scx_sched *sch,const struct scx_cmask *src, +struct scx_cmask_ref *ref); +void scx_cmask_ref_shard (const struct scx_cmask_ref *ref,s32 shard_idx, +struct scx_cmask *out); +void scx_cmask_ref_or (const struct scx_cmask_ref *ref,const struct scx_cmask *src); +void scx_cmask_ref_copy (const struct scx_cmask_ref *ref,const struct scx_cmask *src); +#endif /* _KERNEL_SCHED_EXT_CID_H */
kernel/sched/ext/types.h +38 -1
@@ -116,7 +116,7 @@ struct scx_cmask {u32 base;u32 nr_cids;u32 alloc_words; - u64 bits[] __counted_by(alloc_words); +u64 bits[]; };/*
@@ -172,4 +172,41 @@ struct scx_cmask {#define SCX_CMASK_DEFINE_SHARD (NAME ,BASE ,NR_CIDS ) \ __SCX_CMASK_DEFINE(NAME, BASE, NR_CIDS, SCX_CID_SHARD_MAX_CPUS) +/* +* scx_cmask_ref: validated reference to a BPF-arena cmask. +* +* scx_cmask_ref_init() normalizes the pointer into the arena and snapshots +* @base/@nr_cids. The snapshot is what downstream code uses for sizing - the +* live header can be mutated concurrently by BPF. +* +* scx_cmask_ref_shard() reads one shard into a cmask. scx_cmask_ref_or() and +* scx_cmask_ref_copy() write back into the referenced arena cmask, bounded by +* the snapshot. +* +* Typical input use: +* +* struct scx_cmask_ref ref; +* SCX_CMASK_DEFINE(shard, 0, SCX_CID_SHARD_MAX_CPUS); +* s32 idx, ret; +* +* ret = scx_cmask_ref_init(sch, src, &ref); +* if (ret < 0) +* return ret; +* +* for (idx = ref.shard_first; idx < ref.shard_end; idx++) { +* scx_cmask_ref_shard(&ref, idx, shard); +* if (!shard->nr_cids) +* continue; +* ... use idx and shard ... +* } +*/ +struct scx_cmask_ref { +struct scx_sched *sch; +struct scx_cmask *src; +u32 base; +u32 nr_cids; +s32 shard_first; +s32 shard_end; +}; +#endif /* _KERNEL_SCHED_EXT_TYPES_H */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 9/33 sched_ext: Build the set_cmask scratch from trusted geometry
In reply to Tejun Heoscx_call_op_set_cpumask() builds a per-cpu cmask in the set_cmask scratch, which lives in BPF-writable arena. A scheduler can corrupt the scratch's inline header (base, nr_cids, alloc_words) from another cpu, so sizing and indexing the write from it risks an out-of-bounds write.
Drive the build from kernel-known geometry instead. scx_cmask_ref_init_kern() imposes base and nr_cids rather than reading them, and scx_cmask_ref_from_cpumask() fills the scratch from the ref. Neither reads the header back.
--- kernel/sched/ext/cid.c | 70 ++++++++++++++++++++++++++++++++++++++++++ kernel/sched/ext/cid.h | 4 +++ kernel/sched/ext/ext.c | 11 ++++--- 3 files changed, 81 insertions(+), 4 deletions(-)
kernel/sched/ext/cid.c +70 -0
@@ -951,6 +951,38 @@ int scx_cmask_ref_init(struct scx_sched *sch, const struct scx_cmask *src,return 0 ; } +/** +* scx_cmask_ref_init_kern - Bind a scx_cmask_ref to a kernel-owned cmask +* @sch: scheduler the cmask belongs to +* @m: kernel address of the target cmask, storage sized for @nr_cids at @base +* @base: first cid of the active range +* @nr_cids: active range length +* @ref: output ref +* +* Like scx_cmask_ref_init() but the geometry is supplied by the caller, not +* read from @m's header, so a concurrent BPF write to the header can't steer +* later sizing or offsets. Rewrite the header from the trusted geometry and +* bind @ref to it. +*/ +void scx_cmask_ref_init_kern (struct scx_sched *sch,struct scx_cmask *m, +u32 base,u32 nr_cids,struct scx_cmask_ref *ref) +{ +WRITE_ONCE (m->base, base); +WRITE_ONCE (m->nr_cids, nr_cids); +WRITE_ONCE (m->alloc_words,SCX_CMASK_NR_WORDS (nr_cids)); + + ref->sch = sch; + ref->src = m; + ref->base = base; + ref->nr_cids = nr_cids; + + ref->shard_first = scx_cid_to_shard[base]; +if (likely (nr_cids)) + ref->shard_end = scx_cid_to_shard[base + nr_cids -1 ] +1 ; +else + ref->shard_end = ref->shard_first; +} +/** * scx_cmask_ref_shard - Read one shard from @ref into @out * @ref: validated ref
@@ -1032,6 +1064,44 @@ void scx_cmask_ref_copy(const struct scx_cmask_ref *ref, const struct scx_cmask src->bits, src->base, src->nr_cids, CMASK_OP2_REF_COPY); } +/** +* scx_cmask_ref_from_cpumask - Populate @ref's arena cmask from a cpumask +* @ref: kern-bound ref, see scx_cmask_ref_init_kern() +* @cpumask: cpus to translate into cids +* +* Write @ref's active range one word at a time, setting each cid's bit when +* its cpu is in @cpumask. Offsets and length come from @ref's trusted geometry +* and stores use WRITE_ONCE since BPF may read concurrently, so the arena +* header is never read. +*/ +void scx_cmask_ref_from_cpumask (const struct scx_cmask_ref *ref, +const struct cpumask *cpumask) +{ +struct scx_cmask *m = ref->src; +u32 base = ref->base, nr_cids = ref->nr_cids; +u32 wi, nr_words; + +if (!nr_cids) +return ; + + nr_words = (base + nr_cids -1 ) /64 - base /64 +1 ; +for (wi =0 ; wi < nr_words; wi++) { +u32 word_first_cid = (base /64 + wi) *64 ; +u64 word =0 ; +u32 bit; + +for (bit =0 ; bit <64 ; bit++) { +u32 cid = word_first_cid + bit; + +if (cid < base || cid >= base + nr_cids) +continue ; +if (cpumask_test_cpu (__scx_cid_to_cpu (cid), cpumask)) + word |=BIT_U64 (bit); + } +WRITE_ONCE (m->bits[wi], word); + } +} +int scx_cid_kfunc_init (void ) { return register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_init_cids) ?:
kernel/sched/ext/cid.h +4 -0
@@ -295,8 +295,12 @@ static inline s32 scx_cpu_ret(struct scx_sched *sch, s32 cpu_or_cid)int scx_cmask_ref_init (struct scx_sched *sch,const struct scx_cmask *src,struct scx_cmask_ref *ref); +void scx_cmask_ref_init_kern (struct scx_sched *sch,struct scx_cmask *m, +u32 base,u32 nr_cids,struct scx_cmask_ref *ref);void scx_cmask_ref_shard (const struct scx_cmask_ref *ref,s32 shard_idx,struct scx_cmask *out); +void scx_cmask_ref_from_cpumask (const struct scx_cmask_ref *ref, +const struct cpumask *cpumask);void scx_cmask_ref_or (const struct scx_cmask_ref *ref,const struct scx_cmask *src);void scx_cmask_ref_copy (const struct scx_cmask_ref *ref,const struct scx_cmask *src);
kernel/sched/ext/ext.c +7 -4
@@ -424,12 +424,15 @@ static inline void scx_call_op_set_cpumask(struct scx_sched *sch, struct rq *rq, {if (scx_is_cid_type ()) {struct scx_cmask *kern_va = *this_cpu_ptr (sch->set_cmask_scratch); +struct scx_cmask_ref ref; +/* -* Build the per-CPU arena cmask and hand BPF its arena address. -* Caller holds the rq lock with IRQs disabled, which makes us -* the sole user of the scratch area. +* Build the per-cpu arena cmask from kernel geometry via @ref, +* never reading its BPF-writable header, and hand BPF the arena +* address. The rq lock makes this cpu the sole kernel writer. */ -scx_cpumask_to_cmask (cpumask, kern_va); +scx_cmask_ref_init_kern (sch, kern_va,0 ,num_possible_cpus (), &ref); +scx_cmask_ref_from_cpumask (&ref, cpumask);SCX_CALL_CID_OP_TASK (sch, set_cmask, rq, task,scx_kaddr_to_arena (sch, kern_va)); }else {
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 10/33 sched_ext: RCU-protect the sub-sched tree's children/sibling lists
In reply to Tejun HeoFuture kfuncs need to walk descendants without scx_sched_lock. Make the walker RCU-safe so that they can. A sub-sched's fields are initialized before it is linked, so a walk that observes a linked node also observes its setup. In-place changes after linking carry their own ordering.
Switch the children/sibling list ops to RCU and expand the descendant walker to accept rcu_read_lock as a valid read-side context. Walkers that mutate keep scx_sched_lock.
A sub-sched can be linked while an ancestor is bypassing, after the bypass walk that propagates the depth has passed its parent. Bypass state is a per-cpu flag plus a depth count and can't be established atomically at link time, so refuse to link under a bypassing ancestor. Take scx_bypass_lock across linking to check the parent's bypass state coherently.
v3: Reject linking under a bypassing ancestor instead of inheriting bypass_depth. (sashiko AI)
v2: Inherit bypass_depth before publishing @sch on the RCU sibling list.
--- kernel/sched/ext/ext.c | 18 +++++++++++++++--- kernel/sched/ext/sub.c | 11 +++++++---- kernel/sched/ext/sub.h | 4 ++-- 3 files changed, 24 insertions(+), 9 deletions(-)
kernel/sched/ext/ext.c +15 -3
@@ -5502,7 +5502,8 @@ s32 scx_link_sched(struct scx_sched *sch)const char *err_msg ="" ;s32 ret =0 ; - scoped_guard(raw_spinlock_irq, &scx_sched_lock) { + scoped_guard(raw_spinlock_irqsave, &scx_bypass_lock) /* for the parent bypass check */ + scoped_guard(raw_spinlock, &scx_sched_lock) {#ifdef CONFIG_EXT_SUB_SCHED struct scx_sched *parent =scx_parent (sch);
@@ -5519,6 +5520,17 @@ s32 scx_link_sched(struct scx_sched *sch)break ; } +/* +* Bypass state is spread across per-cpu flags and a +* depth count, so inheriting it is tricky and has no +* valid use case. Refuse it. +*/ +if (READ_ONCE (parent->bypass_depth)) { + err_msg ="parent bypassing" ; + ret = -EBUSY ; +break ; + } + ret =rhashtable_lookup_insert_fast (&scx_sched_hash, &sch->hash_node, scx_sched_hash_params);if (ret) {
@@ -5526,7 +5538,7 @@ s32 scx_link_sched(struct scx_sched *sch) break; } -list_add_tail (&sch->sibling, &parent->children); +list_add_tail_rcu (&sch->sibling, &parent->children); }#endif /* CONFIG_EXT_SUB_SCHED */
@@ -5553,7 +5565,7 @@ void scx_unlink_sched(struct scx_sched *sch)if (scx_parent (sch)) {rhashtable_remove_fast (&scx_sched_hash, &sch->hash_node, scx_sched_hash_params); -list_del_init (&sch->sibling); +list_del_rcu (&sch->sibling); }#endif /* CONFIG_EXT_SUB_SCHED */ list_del_rcu (&sch->all);
kernel/sched/ext/sub.c +7 -4
@@ -35,21 +35,24 @@ struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos, struct scx_schestruct scx_sched *next;lockdep_assert (lockdep_is_held (&scx_enable_mutex) || -lockdep_is_held (&scx_sched_lock)); +lockdep_is_held (&scx_sched_lock) || +rcu_read_lock_any_held ());/* if first iteration, visit @root */ if (!pos)return root;/* visit the first child if exists */ - next = list_first_entry_or_null(&pos->children, struct scx_sched, sibling); + next = list_first_or_null_rcu(&pos->children, struct scx_sched, sibling);if (next)return next;/* no child, visit my or the closest ancestor's next sibling */ while (pos != root) { -if (!list_is_last (&pos->sibling, &scx_parent (pos)->children)) -return list_next_entry (pos, sibling); + next =list_next_or_null_rcu (&scx_parent (pos)->children, &pos->sibling, + struct scx_sched, sibling); +if (next) +return next; pos =scx_parent (pos); }
kernel/sched/ext/sub.h +2 -2
@@ -46,8 +46,8 @@ static inline s32 scx_alloc_pshards(struct scx_sched *sch) { return 0; }* @root: sched to walk the descendants of * * Walk @root's descendants. @root is included in the iteration and the first -* node to be visited. Must be called with either scx_enable_mutex or -* scx_sched_lock held. +* node to be visited. Must be called with scx_enable_mutex, scx_sched_lock, or +* RCU read lock. */ #define scx_for_each_descendant_pre (pos, root) \ for ((pos) = scx_next_descendant_pre(NULL, (root)); (pos); \
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 11/33 sched_ext: Add scx_skip_subtree_pre()
In reply to Tejun HeoFactor the sibling/ancestor portion of scx_next_descendant_pre() out as scx_skip_subtree_pre(), a pre-order walk primitive that skips @pos's subtree, and call it from scx_next_descendant_pre(). Same locking rules as the existing primitive.
Used in a follow-up to fast-skip subtrees that have nothing to do during a descendant walk.
--- kernel/sched/ext/sub.c | 37 ++++++++++++++++++++++++++++--------- kernel/sched/ext/sub.h | 2 ++ 2 files changed, 30 insertions(+), 9 deletions(-)
kernel/sched/ext/sub.c +28 -9
@@ -21,6 +21,33 @@#ifdef CONFIG_EXT_SUB_SCHED +/** +* scx_skip_subtree_pre - Skip @pos's subtree in a pre-order walk +* @pos: current position +* @root: walk root +* +* In a walk started by scx_next_descendant_pre(), continue past @pos's subtree: +* return @pos's next sibling, or the closest ancestor's next sibling, or NULL +* if @pos's subtree is the last under @root. Same locking rules. +*/ +struct scx_sched *scx_skip_subtree_pre (struct scx_sched *pos,struct scx_sched *root) +{ +struct scx_sched *next; + +lockdep_assert (lockdep_is_held (&scx_enable_mutex) || +lockdep_is_held (&scx_sched_lock) || +rcu_read_lock_any_held ()); + +while (pos != root) { + next =list_next_or_null_rcu (&scx_parent (pos)->children, &pos->sibling, + struct scx_sched, sibling); +if (next) +return next; + pos =scx_parent (pos); + } +return NULL ; +} +/** * scx_next_descendant_pre - find the next descendant for pre-order walk * @pos: the current position (%NULL to initiate traversal)
@@ -48,15 +75,7 @@ struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos, struct scx_schereturn next;/* no child, visit my or the closest ancestor's next sibling */ -while (pos != root) { - next =list_next_or_null_rcu (&scx_parent (pos)->children, &pos->sibling, - struct scx_sched, sibling); -if (next) -return next; - pos =scx_parent (pos); - } - -return NULL ; +return scx_skip_subtree_pre (pos, root); }static struct scx_sched *scx_find_sub_sched (u64 cgroup_id)
kernel/sched/ext/sub.h +2 -0
@@ -15,6 +15,7 @@#ifdef CONFIG_EXT_SUB_SCHED +struct scx_sched *scx_skip_subtree_pre (struct scx_sched *pos,struct scx_sched *root);struct scx_sched *scx_next_descendant_pre (struct scx_sched *pos,struct scx_sched *root);void scx_set_task_sched (struct task_struct *p,struct scx_sched *sch);struct cgroup *sch_cgroup (struct scx_sched *sch);
@@ -30,6 +31,7 @@ s32 scx_alloc_pshards(struct scx_sched *sch);#else /* CONFIG_EXT_SUB_SCHED */ static inline struct scx_sched *scx_next_descendant_pre (struct scx_sched *pos,struct scx_sched *root) {return pos ?NULL : root; } +static inline struct scx_sched *scx_skip_subtree_pre (struct scx_sched *pos,struct scx_sched *root) {return NULL ; }static inline void scx_set_task_sched (struct task_struct *p,struct scx_sched *sch) {}static inline struct cgroup *sch_cgroup (struct scx_sched *sch) {return NULL ; }static inline void set_cgroup_sched (struct cgroup *cgrp,struct scx_sched *sch) {}
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 12/33 sched_ext: Stop resolving a disabled scheduler's programs
In reply to Tejun HeoA scheduler's BPF programs can outlive it. A timer it armed or a tracing program it loaded can fire after ops.exit() has run, before the programs are unloaded, and scx_prog_sched() still resolves the program to its scheduler through ops->priv. Harmless while kfuncs touch only lifetime-stable state, but a hazard once a kfunc reads global state a newly loaded scheduler can change underneath it.
Add scx_sched->dead, set right after ops.exit() and drained with synchronize_rcu(). It follows exit() rather than preceding it so exit()'s own kfunc calls still resolve to @sch. scx_prog_sched() returns NULL for a dead scheduler, so every kfunc's existing !sch bail rejects it at one choke point.
v2: Check dead in the CONFIG_EXT_SUB_SCHED=n scx_prog_sched() too. (sashiko AI)
--- kernel/sched/ext/ext.c | 8 ++++++++ kernel/sched/ext/internal.h | 19 +++++++++++++++---- kernel/sched/ext/sub.c | 9 +++++++++ 3 files changed, 32 insertions(+), 4 deletions(-)
kernel/sched/ext/ext.c +8 -0
@@ -5733,6 +5733,14 @@ static void scx_root_disable(struct scx_sched *sch)if (sch->ops.exit)SCX_CALL_OP (sch, exit,NULL , sch->exit_info); +/* +* @sch's non-ops programs such as timers and tracers can fire after +* ops.exit(). Now that exit is complete, stop scx_prog_sched() from +* resolving to @sch and drain in-flight resolvers. +*/ +WRITE_ONCE (sch->dead, true); +synchronize_rcu (); +scx_unlink_sched (sch);/*
kernel/sched/ext/internal.h +15 -4
@@ -1202,6 +1202,7 @@ struct scx_sched {struct sched_ext_ops_cid ops_cid; };bool is_cid_type;/* true if registered via bpf_sched_ext_ops_cid */ +bool dead;/* set after ops.exit(), gates scx_prog_sched() */ /* * Arena map auto-discovered from member progs at struct_ops attach.
@@ -1976,14 +1977,20 @@ static inline bool scx_task_on_sched(struct scx_sched *sch,static inline struct scx_sched *scx_prog_sched (const struct bpf_prog_aux *aux) {struct sched_ext_ops *ops; -struct scx_sched *root; +struct scx_sched *sch, *root; ops =bpf_prog_get_assoc_struct_ops (aux); -if (likely (ops)) -return rcu_dereference_all (ops->priv); +if (likely (ops)) { + sch =rcu_dereference_all (ops->priv); +if (sch &&unlikely (READ_ONCE (sch->dead))) +return NULL ; +return sch; + } root =rcu_dereference_all (scx_root);if (root) { +if (unlikely (READ_ONCE (root->dead))) +return NULL ;/* * COMPAT-v6.19: Schedulers built before sub-sched support was * introduced may have unassociated non-struct_ops programs.
@@ -2035,7 +2042,11 @@ static inline bool scx_task_on_sched(struct scx_sched *sch,static inline struct scx_sched *scx_prog_sched (const struct bpf_prog_aux *aux) { -return rcu_dereference_all (scx_root); +struct scx_sched *root =rcu_dereference_all (scx_root); + +if (root &&unlikely (READ_ONCE (root->dead))) +return NULL ; +return root; }static inline struct scx_sched *scx_parent (struct scx_sched *sch) {return NULL ; }
kernel/sched/ext/sub.c +9 -0
@@ -344,6 +344,15 @@ void scx_sub_disable(struct scx_sched *sch)if (sch->ops.exit)SCX_CALL_OP (sch, exit,NULL , sch->exit_info); + +/* +* @sch's non-ops programs such as timers and tracers can fire after +* ops.exit(). Now that exit is complete, stop scx_prog_sched() from +* resolving to @sch and drain in-flight resolvers. +*/ +WRITE_ONCE (sch->dead, true); +synchronize_rcu (); +if (sch->sub_kset)kobject_del (&sch->sub_kset->kobj);/* not added if enable failed before scx_sched_sysfs_add() */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 13/33 sched_ext: Add per-shard cap delegation for sub-schedulers
In reply to Tejun HeoCaps are per-cid permissions parents delegate to direct children via scx_bpf_sub_grant() / scx_bpf_sub_revoke(). A child's cap set is always a subset of its parent's. Sub-scheds check their caps locally, and cross-sched communication is needed only when the delegation set itself changes.
Caps will be used to implement sub-sched scheduling on the enqueue path. Picking a cid for a task at a leaf depends on which cids the leaf is allowed to use, and resolving that programmatically on every enqueue would mean a cross-sched round-trip call chain, possibly retrying if the request can't be granted as-is. The dispatch path is different - it runs as top-down recursion via scx_bpf_sub_dispatch().
Locking is per shard. cid space is split into shards, and each sub-sched has its own pshard->lock for each shard. Operations are broken up on shard boundaries. Different shards never contend. Shards are expected to be topology-aligned and likely to serve as the locality unit when cids are allocated to schedulers, so per-shard lock granularity scales naturally with the allocation pattern.
This patch adds the framework with a single dummy cap. Real caps land in later patches.
The enable path is reordered for pshards. scx_arena_pool_init() moves ahead of scx_link_sched() so the pshards are allocated before the sched becomes reachable - scx_alloc_pshards() skips allocation when the arena pool isn't initialized.
- scx_bpf_sub_grant(): Per-cid all-or-nothing grant to direct child.
- scx_bpf_sub_revoke(): Clear caps on @cmask across @child and its subtree.
- scx_bpf_sub_caps(): Lockless snapshot of caps on a cid range.
/sys/kernel/sched_ext/SCHED/caps shows the caps each scheduler currently holds.
v4: Move the pshard[] full build/publish and the err_disable scx_error() recording to earlier patches. (sashiko AI)
v3: Build pshard[] fully before publishing it, read it with READ_ONCE. (sashiko AI)
v2: Validate ops before scx_link_sched() publishes the sub. (sashiko AI)
--- kernel/sched/ext/ext.c | 77 ++++- kernel/sched/ext/internal.h | 56 +++- kernel/sched/ext/sub.c | 342 ++++++++++++++++++++++- kernel/sched/ext/sub.h | 2 + tools/sched_ext/include/scx/common.bpf.h | 6 + 5 files changed, 468 insertions(+), 15 deletions(-)
kernel/sched/ext/ext.c +74 -3
@@ -4742,9 +4742,52 @@ static ssize_t scx_attr_events_show(struct kobject *kobj, }SCX_ATTR (events); +#ifdef CONFIG_EXT_SUB_SCHED +static const char *scx_cap_names[__SCX_NR_CAPS] = { + [__SCX_CAP_DUMMY] ="dummy" , +}; + +static ssize_t scx_attr_caps_show (struct kobject *kobj, +struct kobj_attribute *ka,char *buf) +{ + struct scx_sched *sch = container_of(kobj, struct scx_sched, kobj); +u32 npossible =num_possible_cpus (); + struct scx_cmask *agg __free(kfree) = +kzalloc (struct_size (agg, bits,SCX_CMASK_NR_WORDS (npossible)),GFP_KERNEL ); + unsigned long *agg_bm __free(bitmap) = bitmap_zalloc(npossible, GFP_KERNEL); +ssize_t count =0 ; +s32 cap, si; + +if (!agg || !agg_bm) +return -ENOMEM ; + +for (cap =0 ; cap < __SCX_NR_CAPS; cap++) { +SCX_CMASK_DEFINE (snap,0 ,SCX_CID_SHARD_MAX_CPUS ); + +scx_cmask_init (agg,0 , npossible); +for (si =0 ; si < sch->nr_pshards; si++) { +struct scx_cmask *cm = &sch->pshard[si]->caps[cap].cmask; + +scx_cmask_reframe (snap, cm->base, cm->nr_cids); +scx_cmask_copy (snap, cm); +scx_cmask_or (agg, snap); + } +/* %*pbl takes unsigned long bitmap layout, convert from u64 */ +bitmap_from_arr64 (agg_bm, agg->bits, npossible); + count +=sysfs_emit_at (buf, count,"%s: %*pbl\n" , + scx_cap_names[cap], npossible, agg_bm); + } +return count; +} +SCX_ATTR (caps); +#endif /* CONFIG_EXT_SUB_SCHED */ +static struct attribute *scx_sched_attrs[] = { &scx_attr_ops.attr, &scx_attr_events.attr, +#ifdef CONFIG_EXT_SUB_SCHED + &scx_attr_caps.attr, +#endifNULL , };ATTRIBUTE_GROUPS (scx_sched);
@@ -6761,8 +6804,8 @@ static void scx_root_enable_workfn(struct kthread_work *work)/* * A cid-form scheduler finalizes its cid layout in ops.init_cids(), -* which may call scx_bpf_cid_override(). Run it before ops.init() so -* the final layout is in effect. +* which may call scx_bpf_cid_override(). Run it before the caps and +* shard state are built so the final layout is in effect. */ if (sch->is_cid_type && sch->ops_cid.init_cids) { ret =SCX_CALL_OP_RET (sch, init_cids,NULL );
@@ -6792,6 +6835,9 @@ static void scx_root_enable_workfn(struct kthread_work *work) goto err_disable; } +scx_init_root_caps (sch); + +/* the cid caps and shards are live now, so ops.init() can query them */ if (sch->ops.init) { ret =SCX_CALL_OP_RET (sch, init,NULL );if (ret) {
@@ -7473,7 +7519,7 @@ static struct bpf_struct_ops bpf_sched_ext_ops = {/* * cid-form cfi stubs. Stubs whose signatures match the cpu-form (param types -* identical, only param names differ across structs) are reused; only +* identical, only param names differ across structs) are reused. Only * set_cmask needs a fresh stub since the second argument type differs. */ static void sched_ext_ops_cid__set_cmask(struct task_struct *p,
@@ -9670,6 +9716,28 @@ __bpf_kfunc struct cgroup *scx_bpf_task_cgroup(struct task_struct *p, }#endif /* CONFIG_CGROUP_SCHED */ +#ifndef CONFIG_EXT_SUB_SCHED +__bpf_kfunc s32 scx_bpf_sub_grant(u64 cgroup_id, u64 caps, +const struct scx_cmask *cmask__ign, +struct scx_cmask *denied_out__ign, +const struct bpf_prog_aux *aux) +{ +return -EOPNOTSUPP ; +} + +__bpf_kfunc void scx_bpf_sub_revoke(u64 cgroup_id, u64 caps, +const struct scx_cmask *cmask__ign, +const struct bpf_prog_aux *aux) +{ +} + +__bpf_kfunc s32 scx_bpf_sub_caps(u64 cgroup_id, u64 caps, struct scx_cmask *out__ign, +const struct bpf_prog_aux *aux) +{ +return -EOPNOTSUPP ; +} +#endif /* !CONFIG_EXT_SUB_SCHED */ +__bpf_kfunc_end_defs ();BTF_KFUNCS_START (scx_kfunc_ids_any)
@@ -9714,6 +9782,9 @@ BTF_ID_FLAGS(func, scx_bpf_events)#ifdef CONFIG_CGROUP_SCHED BTF_ID_FLAGS(func, scx_bpf_task_cgroup, KF_IMPLICIT_ARGS | KF_RCU | KF_ACQUIRE)#endif +BTF_ID_FLAGS(func, scx_bpf_sub_grant, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_sub_revoke, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_sub_caps, KF_IMPLICIT_ARGS)BTF_KFUNCS_END (scx_kfunc_ids_any) static const struct btf_kfunc_id_set scx_kfunc_set_any = {
kernel/sched/ext/internal.h +52 -4
70 lines not on this page · raw message
kernel/sched/ext/sub.c +334 -8
376 lines not on this page · raw message
kernel/sched/ext/sub.h +2 -0
@@ -27,6 +27,7 @@ void scx_sub_enable_workfn(struct kthread_work *work);bool scx_bpf_sub_dispatch (u64 cgroup_id,const struct bpf_prog_aux *aux);void scx_free_pshards (struct scx_sched *sch);s32 scx_alloc_pshards (struct scx_sched *sch); +void scx_init_root_caps (struct scx_sched *sch);#else /* CONFIG_EXT_SUB_SCHED */
@@ -39,6 +40,7 @@ static inline void drain_descendants(struct scx_sched *sch) { }static inline void scx_sub_disable (struct scx_sched *sch) { }static inline void scx_free_pshards (struct scx_sched *sch) {}static inline s32 scx_alloc_pshards (struct scx_sched *sch) {return 0 ; } +static inline void scx_init_root_caps (struct scx_sched *sch) {}#endif /* CONFIG_EXT_SUB_SCHED */
tools/sched_ext/include/scx/common.bpf.h +6 -0
@@ -114,6 +114,12 @@ u32 scx_bpf_cidperf_cap(s32 cid) __ksym __weak; u32 scx_bpf_cidperf_cur(s32 cid) __ksym __weak; void scx_bpf_cidperf_set(s32 cid, u32 perf) __ksym __weak; +/* sub-scheduler cap control, scx_bpf_sub_caps() cgroup_id 0 == self */ +s32 scx_bpf_sub_grant(u64 cgroup_id, u64 caps, const struct scx_cmask *cmask, + struct scx_cmask *denied) __ksym __weak; +void scx_bpf_sub_revoke(u64 cgroup_id, u64 caps, const struct scx_cmask *cmask) __ksym __weak; +s32 scx_bpf_sub_caps(u64 cgroup_id, u64 caps, struct scx_cmask *out) __ksym __weak; +/* * Use the following as @it__iter when calling scx_bpf_dsq_move[_vtime]() from * within bpf_for_each() loops.
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 14/33 sched_ext: Add coalescing sub_caps_updated() notifier for sub-schedulers
In reply to Tejun HeoWire up ops_cid.sub_caps_updated() to notify sub-scheds of cap changes.
Three constraints shape the design:
1. Static memory. Deliveries use a fixed-size buffer, both for runtime efficiency and so notifications can't be lost under memory pressure.
2. High-frequency updates. Grant/revoke can mutate caps in bursts, and the notifier path must absorb that without amplifying it.
3. Recursive grant/revoke from the callback. A child receiving a notification can call grant/revoke on its own children, which can cascade recursively down its subtree.
(1) and (2) lead to coalescing into a fixed payload. Each delivery carries a single (cmask, caps) pair covering every change since the previous one. Direction (set vs cleared) isn't encoded as it doesn't fit in the fixed-size summary. The callback queries scx_bpf_sub_caps() for current state. Only one delivery is in flight per shard. Further changes fold into the same buffer and ship as the next callback, so a shard's callbacks fire in order.
(3) leads to deferred delivery. Events accumulate during grant/revoke and are delivered after the shard lock is released.
v2:
- Request a private stack for ops.sub_caps_updated(). (sashiko AI)
- Build cmask_arena_out via scx_cmask_ref, not by re-reading its header.
--- kernel/sched/ext/ext.c | 13 ++- kernel/sched/ext/internal.h | 71 ++++++++++++++ kernel/sched/ext/sub.c | 178 ++++++++++++++++++++++++++++++++++-- kernel/sched/ext/sub.h | 1 + 4 files changed, 254 insertions(+), 9 deletions(-)
kernel/sched/ext/ext.c +11 -2
@@ -7318,6 +7318,11 @@ static int bpf_scx_check_member(const struct btf_type *t,case offsetof(struct sched_ext_ops , dispatch): prog->aux->priv_stack_requested = true; prog->aux->recursion_detected = scx_pstack_recursion_on_dispatch; +break ; +case offsetof(struct sched_ext_ops , sub_caps_updated): + prog->aux->priv_stack_requested = true; + prog->aux->recursion_detected = scx_pstack_recursion_on_caps_updated; + break; }#endif /* CONFIG_EXT_SUB_SCHED */
@@ -7519,11 +7524,13 @@ static struct bpf_struct_ops bpf_sched_ext_ops = {/* * cid-form cfi stubs. Stubs whose signatures match the cpu-form (param types -* identical, only param names differ across structs) are reused. Only -* set_cmask needs a fresh stub since the second argument type differs. +* identical, only param names differ across structs) are reused. Some need +* fresh stubs, set_cmask due to an argument type difference and the sub-sched +* notifiers because no cpu-form stub exists to reuse. */ static void sched_ext_ops_cid__set_cmask (struct task_struct *p,const struct scx_cmask *cmask) {} +static void sched_ext_ops__sub_caps_updated (const struct scx_cmask *cmask,u64 caps) {}static struct sched_ext_ops_cid __bpf_ops_sched_ext_ops_cid = { .select_cid = sched_ext_ops__select_cpu,
@@ -7556,6 +7563,7 @@ static struct sched_ext_ops_cid __bpf_ops_sched_ext_ops_cid = {#endif .sub_attach = sched_ext_ops__sub_attach, .sub_detach = sched_ext_ops__sub_detach, + .sub_caps_updated = sched_ext_ops__sub_caps_updated, .cid_online = sched_ext_ops__cpu_online, .cid_offline = sched_ext_ops__cpu_offline, .init_cids = sched_ext_ops__init_cids,
@@ -10010,6 +10018,7 @@ static int __init scx_init(void)CID_OFFSET_MATCH (dump_task, dump_task);CID_OFFSET_MATCH (sub_attach, sub_attach);CID_OFFSET_MATCH (sub_detach, sub_detach); +CID_OFFSET_MATCH (sub_caps_updated, sub_caps_updated);CID_OFFSET_MATCH (init_cids, init_cids);CID_OFFSET_MATCH (init, init);CID_OFFSET_MATCH (exit, exit);
kernel/sched/ext/internal.h +71 -0
98 lines not on this page · raw message
kernel/sched/ext/sub.c +171 -7
283 lines not on this page · raw message
kernel/sched/ext/sub.h +1 -0
@@ -21,6 +21,7 @@ void scx_set_task_sched(struct task_struct *p, struct scx_sched *sch);struct cgroup *sch_cgroup (struct scx_sched *sch);void set_cgroup_sched (struct cgroup *cgrp,struct scx_sched *sch);void scx_pstack_recursion_on_dispatch (struct bpf_prog *prog); +void scx_pstack_recursion_on_caps_updated (struct bpf_prog *prog);void drain_descendants (struct scx_sched *sch);void scx_sub_disable (struct scx_sched *sch);void scx_sub_enable_workfn (struct kthread_work *work);
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 15/33 sched_ext: Maintain per-cpu effective cap copies for single-read checks
In reply to Tejun HeoChecking a sched's caps on a cid would need to test several cap bits against caps[] to account for implied caps. Also, caps[] modifications aren't synchronized against scheduling operations on each cpu, which can lead to awkward race conditions.
Collect them per cpu instead. caps[] under pshard->lock stays the target configuration. scx_sched_pcpu->ecaps is added, the transposed effective
copy: the set of cap bits the sched holds on that cpu which can be accessed with a single read. It is stable under the rq lock. It can also be read locklessly with READ_ONCE().
Grant and revoke only mutate caps[]. They queue a sync request on the target cpu's rq->scx.ecaps_to_sync and kick it, and the cpu recomputes the queued scheds' ecaps from caps[] in balance_one() under its own rq lock. A dying sched runs the sync directly to retire its queued request before freeing. As held references can defer the freeing past the enclosing root scheduler's lifetime, root enable discards leftover sync requests before going live.
--- kernel/sched/ext/ext.c | 10 +++ kernel/sched/ext/internal.h | 21 +++++- kernel/sched/ext/sub.c | 133 +++++++++++++++++++++++++++++++++++- kernel/sched/ext/sub.h | 16 +++++ kernel/sched/sched.h | 3 + 5 files changed, 180 insertions(+), 3 deletions(-)
kernel/sched/ext/ext.c +10 -0
@@ -2607,6 +2607,8 @@ static int balance_one(struct rq *rq, struct task_struct *prev) rq->scx.flags |=SCX_RQ_IN_BALANCE ; rq->scx.flags &= ~SCX_RQ_BAL_KEEP ; +scx_process_sync_ecaps (rq); +if ((sch->ops.flags &SCX_OPS_HAS_CPU_PREEMPT ) &&unlikely (rq->scx.cpu_released)) {/*
@@ -4664,6 +4666,9 @@ static void scx_sched_free_rcu_work(struct work_struct *work)*/ WARN_ON_ONCE (!list_empty (&pcpu->deferred_reenq_local.node)); +/* flush the queued ecaps syncs */ +scx_discard_ecaps_to_sync (cpu, pcpu); +/* * Bypass blocks new kicks. Flush the kick irq_work so this * pcpu's to_kick_node is off the list before it is freed.
@@ -6426,6 +6431,9 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd, node =cpu_to_node (cpu); pcpu->sch = sch;INIT_LIST_HEAD (&pcpu->deferred_reenq_local.node); +#ifdef CONFIG_EXT_SUB_SCHED +init_llist_node (&pcpu->ecaps_to_sync_node); +#endif INIT_LIST_HEAD (&pcpu->to_kick_node); if (!zalloc_cpumask_var_node(&pcpu->cpus_to_kick, GFP_KERNEL, node) || !zalloc_cpumask_var_node(&pcpu->cpus_to_kick_if_idle, GFP_KERNEL, node) ||
@@ -6770,6 +6778,8 @@ static void scx_root_enable_workfn(struct kthread_work *work) rq->scx.cpuperf_target =SCX_CPUPERF_ONE ; } +scx_discard_stale_ecaps_syncs (); +/* * Keep CPUs stable during enable so that the BPF scheduler can track * online CPUs by watching ->on/offline_cpu() after ->init().
kernel/sched/ext/internal.h +20 -1
@@ -1182,6 +1182,24 @@ struct scx_sched_pcpu {cpumask_var_t cpus_to_wait;struct list_head to_kick_node; +#ifdef CONFIG_EXT_SUB_SCHED +/* +* pshard->caps[cap_bit] is the set of cids the sched holds that one +* cap on. ecaps is its transpose: the set of SCX_CAP_* bits the sched +* holds on this cpu, collected so that the hot-path check is a single +* read. +* +* While pshard->caps[] under pshard->lock is the target configuration, +* ecaps is the effective copy owned by the cpu. It is written under the +* rq lock while processing rq->ecaps_to_sync. Can also be read with +* READ_ONCE() outside rq lock. +* +* See queue_sync_ecaps() and scx_process_sync_ecaps(). +*/ +u64 ecaps; +struct llist_node ecaps_to_sync_node; +#endif +/* * The event counters are in a per-CPU variable to minimize the * accounting overhead. A system-wide view on the event counter is
@@ -1291,7 +1309,8 @@ struct scx_pshard {/* * Per-cap cmask, inline via TRAILING_OVERLAP so cmask.bits[] overlaps -* the trailing _bits[] storage. Access as &caps[i].cmask. +* the trailing _bits[] storage. Access as &caps[i].cmask. See +* scx_sched_pcpu->ecaps. */ TRAILING_OVERLAP(struct scx_cmask, cmask, bits, u64 _bits[SCX_CMASK_NR_WORDS(SCX_CID_SHARD_MAX_CPUS)];
kernel/sched/ext/sub.c +131 -2
155 lines not on this page · raw message
kernel/sched/ext/sub.h +16 -0
@@ -29,6 +29,9 @@ bool scx_bpf_sub_dispatch(u64 cgroup_id, const struct bpf_prog_aux *aux);void scx_free_pshards (struct scx_sched *sch);s32 scx_alloc_pshards (struct scx_sched *sch);void scx_init_root_caps (struct scx_sched *sch); +void scx_process_sync_ecaps (struct rq *rq); +void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu); +void scx_discard_stale_ecaps_syncs (void );#else /* CONFIG_EXT_SUB_SCHED */
@@ -42,6 +45,9 @@ static inline void scx_sub_disable(struct scx_sched *sch) { }static inline void scx_free_pshards (struct scx_sched *sch) {}static inline s32 scx_alloc_pshards (struct scx_sched *sch) {return 0 ; }static inline void scx_init_root_caps (struct scx_sched *sch) {} +static inline void scx_process_sync_ecaps (struct rq *rq) {} +static inline void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu) {} +static inline void scx_discard_stale_ecaps_syncs (void ) {}#endif /* CONFIG_EXT_SUB_SCHED */
@@ -58,6 +64,16 @@ static inline void scx_init_root_caps(struct scx_sched *sch) {}for ((pos) =scx_next_descendant_pre (NULL , (root)); (pos); \ (pos) = scx_next_descendant_pre((pos), (root))) +#ifdef CONFIG_EXT_SUB_SCHED + +/* caps implied by holding @cap */ +static inline u64 scx_caps_implied (u64 cap) +{ +return 0 ; +} + +#endif /* CONFIG_EXT_SUB_SCHED */ +/* * One user of this function is scx_bpf_dispatch() which can be called * recursively as sub-sched dispatches nest. Always inline to reduce stack usage
kernel/sched/sched.h +3 -0
@@ -806,6 +806,9 @@ struct scx_rq {u32 flags;u32 nr_immed;/* ENQ_IMMED tasks on local_dsq */ u64 clock;/* current per-rq clock -- see scx_bpf_now() */ +#ifdef CONFIG_EXT_SUB_SCHED +struct llist_head ecaps_to_sync;/* pending ecaps syncs */ +#endif cpumask_var_t cpus_to_sync;bool kick_sync_pending;unsigned long kick_sync;
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 16/33 sched_ext: Add sub_ecaps_updated() effective-cap change notifier
In reply to Tejun HeoA sub-scheduler that gains or loses effective caps on a cpu may want to act on it right away - e.g. place or preempt on a newly usable cpu. The existing ops.sub_caps_updated() doesn't fit as it is delivered asynchronously to scheduling operations and can arrive before the per-cpu effective caps go live.
Add ops.sub_ecaps_updated(cid, before, after), a cid-form callback fired from scx_process_sync_ecaps() when a sub-sched's effective caps on a cid change. It runs in dispatch context so the sched can insert, kick or preempt on the cid directly. @before is the caps as of the last delivery.
Cpu hotplug rides the same machinery. Going down zeroes each sched's ecaps on the cpu's cid, with queued syncs discarded at consumption while the cpu is inactive. Coming back up queues a sync for every sched. reported_ecaps is kept across the down/up cycle, so the resync fires the callback only if ownership actually changed while the cpu was down.
v2: Compute cid below the active-cpu guard; discard queued syncs on !cpu_active(). (sashiko AI)
--- kernel/sched/ext/ext.c | 13 +++- kernel/sched/ext/internal.h | 19 +++++- kernel/sched/ext/sub.c | 129 +++++++++++++++++++++++++++++++++--- kernel/sched/ext/sub.h | 8 ++- 4 files changed, 154 insertions(+), 15 deletions(-)
kernel/sched/ext/ext.c +11 -2
@@ -2607,7 +2607,7 @@ static int balance_one(struct rq *rq, struct task_struct *prev) rq->scx.flags |=SCX_RQ_IN_BALANCE ; rq->scx.flags &= ~SCX_RQ_BAL_KEEP ; -scx_process_sync_ecaps (rq); +scx_process_sync_ecaps (rq, prev);if ((sch->ops.flags &SCX_OPS_HAS_CPU_PREEMPT ) &&unlikely (rq->scx.cpu_released)) {
@@ -3146,6 +3146,11 @@ static void handle_hotplug(struct rq *rq, bool online)if (scx_enabled ())scx_idle_update_selcpu_topology (&sch->ops); +if (online) +scx_online_ecaps (rq); +else +scx_offline_ecaps (rq); +if (online &&SCX_HAS_OP (sch, cpu_online))SCX_CALL_OP (sch, cpu_online,NULL ,scx_cpu_arg (cpu));else if (!online &&SCX_HAS_OP (sch, cpu_offline))
@@ -4666,7 +4671,7 @@ static void scx_sched_free_rcu_work(struct work_struct *work)*/ WARN_ON_ONCE (!list_empty (&pcpu->deferred_reenq_local.node)); -/* flush the queued ecaps syncs */ +/* retire the queued ecaps syncs so the pcpu can be freed */ scx_discard_ecaps_to_sync (cpu, pcpu);/*
@@ -7541,6 +7546,7 @@ static struct bpf_struct_ops bpf_sched_ext_ops = {static void sched_ext_ops_cid__set_cmask (struct task_struct *p,const struct scx_cmask *cmask) {}static void sched_ext_ops__sub_caps_updated (const struct scx_cmask *cmask,u64 caps) {} +static void sched_ext_ops__sub_ecaps_updated (s32 cid,u64 before,u64 after) {}static struct sched_ext_ops_cid __bpf_ops_sched_ext_ops_cid = { .select_cid = sched_ext_ops__select_cpu,
@@ -7574,6 +7580,7 @@ static struct sched_ext_ops_cid __bpf_ops_sched_ext_ops_cid = { .sub_attach = sched_ext_ops__sub_attach, .sub_detach = sched_ext_ops__sub_detach, .sub_caps_updated = sched_ext_ops__sub_caps_updated, + .sub_ecaps_updated = sched_ext_ops__sub_ecaps_updated, .cid_online = sched_ext_ops__cpu_online, .cid_offline = sched_ext_ops__cpu_offline, .init_cids = sched_ext_ops__init_cids,
@@ -9890,6 +9897,7 @@ static const u32 scx_kf_allow_flags[] = { #endif /* CONFIG_EXT_GROUP_SCHED */ [SCX_OP_IDX(sub_attach)] = SCX_KF_ALLOW_UNLOCKED, [SCX_OP_IDX(sub_detach)] = SCX_KF_ALLOW_UNLOCKED, + [SCX_OP_IDX(sub_ecaps_updated)] = SCX_KF_ALLOW_ENQUEUE | SCX_KF_ALLOW_DISPATCH, [SCX_OP_IDX(cpu_online)] = SCX_KF_ALLOW_UNLOCKED, [SCX_OP_IDX(cpu_offline)] = SCX_KF_ALLOW_UNLOCKED, [SCX_OP_IDX(init_cids)] = SCX_KF_ALLOW_UNLOCKED | SCX_KF_ALLOW_INIT_CIDS,
@@ -10029,6 +10037,7 @@ static int __init scx_init(void)CID_OFFSET_MATCH (sub_attach, sub_attach);CID_OFFSET_MATCH (sub_detach, sub_detach);CID_OFFSET_MATCH (sub_caps_updated, sub_caps_updated); +CID_OFFSET_MATCH (sub_ecaps_updated, sub_ecaps_updated);CID_OFFSET_MATCH (init_cids, init_cids);CID_OFFSET_MATCH (init, init);CID_OFFSET_MATCH (exit, exit);
kernel/sched/ext/internal.h +18 -1
@@ -770,12 +770,26 @@ struct sched_ext_ops {* Delivered asynchronously after the change is recorded, and may run * before it takes effect on any given cpu. Use it to track which caps * the sub-sched holds and propagate to its own children, not to decide -* if a task can run on a cpu now. +* if a task can run on a cpu now. sub_ecaps_updated() reports that per +* cpu, once it is in effect. * * May call scx_bpf_sub_grant() / scx_bpf_sub_revoke() on children. */ void (*sub_caps_updated)(const struct scx_cmask *cmask,u64 caps); +/** +* @sub_ecaps_updated: This sub-sched's effective caps on a cid changed +* @cid: the cid whose effective caps changed +* @before: effective caps as of the last delivery +* @after: effective caps now +* +* Invoked when this sub-sched's effective caps on @cid change, once the +* change is in effect on the cpu. Runs in dispatch context with rq lock +* held, and can perform all operations allowed in ops.dispatch() +* including inserting/moving tasks. +*/ +void (*sub_ecaps_updated)(s32 cid,u64 before,u64 after); +/* * All online ops must come before ops.cpu_online(). */
@@ -997,6 +1011,7 @@ struct sched_ext_ops_cid {s32 (*sub_attach)(struct scx_sub_attach_args *args);void (*sub_detach)(struct scx_sub_detach_args *args);void (*sub_caps_updated)(const struct scx_cmask *cmask,u64 caps); +void (*sub_ecaps_updated)(s32 cid,u64 before,u64 after);void (*cid_online)(s32 cid);void (*cid_offline)(s32 cid);s32 (*init_cids)(void);
@@ -1198,6 +1213,8 @@ struct scx_sched_pcpu {*/ u64 ecaps;struct llist_node ecaps_to_sync_node; +/* effective caps as of the last sub_ecaps_updated() delivery */ +u64 reported_ecaps;#endif /*
kernel/sched/ext/sub.c +119 -10
173 lines not on this page · raw message
kernel/sched/ext/sub.h +6 -2
@@ -29,7 +29,9 @@ bool scx_bpf_sub_dispatch(u64 cgroup_id, const struct bpf_prog_aux *aux);void scx_free_pshards (struct scx_sched *sch);s32 scx_alloc_pshards (struct scx_sched *sch);void scx_init_root_caps (struct scx_sched *sch); -void scx_process_sync_ecaps (struct rq *rq); +void scx_process_sync_ecaps (struct rq *rq,struct task_struct *prev); +void scx_online_ecaps (struct rq *rq); +void scx_offline_ecaps (struct rq *rq);void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu);void scx_discard_stale_ecaps_syncs (void );
@@ -45,7 +47,9 @@ static inline void scx_sub_disable(struct scx_sched *sch) { }static inline void scx_free_pshards (struct scx_sched *sch) {}static inline s32 scx_alloc_pshards (struct scx_sched *sch) {return 0 ; }static inline void scx_init_root_caps (struct scx_sched *sch) {} -static inline void scx_process_sync_ecaps (struct rq *rq) {} +static inline void scx_process_sync_ecaps (struct rq *rq,struct task_struct *prev) {} +static inline void scx_online_ecaps (struct rq *rq) {} +static inline void scx_offline_ecaps (struct rq *rq) {}static inline void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu) {}static inline void scx_discard_stale_ecaps_syncs (void ) {}
Signature · 1 line
2.55.0
Andrea Righi
reviewerRe: [PATCH v5 sched_ext/for-7.3 16/33] sched_ext: Add sub_ecaps_updated() effective-cap change notifier
Hi Tejun,
Quoted 21 lines · Tejun Heo
A sub-scheduler that gains or loses effective caps on a cpu may want to act on it right away - e.g. place or preempt on a newly usable cpu. The existing
ops.sub_caps_updated()doesn't fit as it is delivered asynchronously to scheduling operations and can arrive before the per-cpu effective caps go live.Add
ops.sub_ecaps_updated(cid, before, after), a cid-form callback fired fromscx_process_sync_ecaps()when a sub-sched's effective caps on a cid change. It runs in dispatch context so the sched can insert, kick or preempt on the cid directly. @before is the caps as of the last delivery.Cpu hotplug rides the same machinery. Going down zeroes each sched's ecaps on the cpu's cid, with queued syncs discarded at consumption while the cpu is inactive. Coming back up queues a sync for every sched.
reported_ecapsis kept across the down/up cycle, so the resync fires the callback only if ownership actually changed while the cpu was down.v2: Compute cid below the active-cpu guard; discard queued syncs on !cpu_active(). (sashiko AI)
Signed-off-by Tejun Heo <[email protected]>---
...
Quoted 30 lines
/*
* @pcpu's sched was unhashed before the grace period, so nothing new queues.
- * Flush its pending sync so the pcpu can be freed.scx_process_sync_ecaps()
- * takes nodes off the list before syncing and acquiring the rq lock waits for
- * any in-flight walk.
+ * Flush its pending sync so the pcpu can be freed. If the cpu is online and
+ * scx is enabled, drain viabalance_one(). Otherwise, discard under the rq
+ * lock.
*/
voidscx_discard_ecaps_to_sync(s32 cpu, struct scx_sched_pcpu *pcpu){kernel/sched/ext/sub.c +15
-3- scoped_guard (rq_lock_irqsave, cpu_rq(cpu)) -scx_process_sync_ecaps (cpu_rq (cpu)); +struct rq *rq =cpu_rq (cpu); -WARN_ON_ONCE (llist_on_list (&pcpu->ecaps_to_sync_node)); +while (true) { + scoped_guard (rq_lock_irqsave, rq) { +/* +* scx_process_sync_ecaps() takes the node off the list +* before it is done accessing @pcpu but does all of it +* under the rq lock. Off-list observed under the rq +* lock guarantees that the sync is complete. +*/ +if (!llist_on_list (&pcpu->ecaps_to_sync_node)) +return ; +/* +* Discard only when the cpu is truly down. cpu_active() +* is already set when scx_online_ecaps() queues an online +* resync while SCX_RQ_ONLINE is not - so test cpu_active(),
kernel/sched/ext/sub.c void scx_process_sync_ecaps(struct rq *rq) · line 503
Quoted 10 lines
kernel/sched/ext/sub.c +10
-0+* or that resync would be dropped. +*/ +if (!scx_enabled () || !cpu_active (cpu)) { +discard_queued_syncs (rq); +return ; + } + } +resched_cpu (cpu); +msleep (1 ); + }
This is a nit, so feel free to ignore. I was wondering if we could wait indefinitely in this loop if the target CPU never reaches balance_one(). However, I think the only way to never trigger balance_one() is a higher class monopolizing the CPU, but this can't happen because of the ext dl_server.
In that case, should we document this "dependency" here? Something like:
/*
* The active EXT deadline server guarantees that balance_one() eventually runs
* even under sustained FAIR or RT load.
*/
Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH v5 sched_ext/for-7.3 16/33] sched_ext: Add sub_ecaps_updated() effective-cap change notifier
Hello, Andrea.
Quoted 11 lines · Andrea Righi
This is a nit, so feel free to ignore. I was wondering if we could wait indefinitely in this loop if the target CPU never reaches
balance_one(). However, I think the only way to never triggerbalance_one()is a higher class monopolizing the CPU, but this can't happen because of the extdl_server.In that case, should we document this "dependency" here? Something like:
/*
* The active EXT deadline server guarantees thatbalance_one()eventually runs
* even under sustained FAIR or RT load.
*/
The guarantee is weaker than that. The ext dl_server is armed only while the rq has ext tasks queued, so an ext-idle cpu monopolized by a higher class can prolong the wait.
Rather than documenting the dependency, the wait can be removed altogether. llist can't unlink a single node but the list can be rebuilt excluding the node being drained under the rq lock, the way ____active_del_barrier() in i915 does. Will follow up with that.
Thanks.
--
tejun
Tejun Heo
reviewerPATCH v5 17/33 sched_ext: Generalize local-DSQ handling to rq-owned DSQs
In reply to Tejun HeoThe local DSQ is synchronized by the containing rq lock rather than its own dsq->lock. A later patch adds a second such DSQ. In preparation, factor the "rq owns the lock" test into dsq_is_rq_owned() and rename local_dsq_post_enq() to rq_owned_post_enq(), taking @rq explicitly.
No behavior change.
--- kernel/sched/ext/ext.c | 34 ++++++++++++++++++++++------------ 1 file changed, 22 insertions(+), 12 deletions(-)
kernel/sched/ext/ext.c +22 -12
@@ -96,6 +96,17 @@ static atomic_long_t scx_hotplug_seq = ATOMIC_LONG_INIT(0);/* Global cursor for the per-CPU tid allocator. Starts at 1; tid 0 is reserved. */ static atomic64_t scx_tid_cursor =ATOMIC64_INIT (1 ); +/* is @dsq synchronized by the containing rq lock instead of dsq->lock? */ +static bool dsq_is_rq_owned (struct scx_dispatch_q *dsq) +{ +switch (dsq->id) { +case SCX_DSQ_LOCAL : +return true; +default : +return false; + } +} +#ifdef CONFIG_EXT_SUB_SCHED /* * The sub sched being enabled. Used by scx_disable_and_exit_task() to exit
@@ -1270,11 +1281,10 @@ static void call_task_dequeue(struct scx_sched *sch, struct rq *rq, p->scx.flags &= ~SCX_TASK_IN_CUSTODY ; } -static void local_dsq_post_enq (struct scx_sched *sch,struct scx_dispatch_q *dsq, -struct task_struct *p,u64 enq_flags) +static void rq_owned_post_enq (struct scx_sched *sch,struct rq *rq, +struct scx_dispatch_q *dsq,struct task_struct *p, +u64 enq_flags) { - struct rq *rq = container_of(dsq, struct rq, scx.local_dsq); -call_task_dequeue (sch, rq, p,0 );/*
@@ -1334,13 +1344,13 @@ static void scx_dispatch_enqueue(struct scx_sched *sch, struct rq *rq, struct scx_dispatch_q *dsq, struct task_struct *p, u64 enq_flags) { - bool is_local = dsq->id == SCX_DSQ_LOCAL; + bool is_rq_owned = dsq_is_rq_owned(dsq);WARN_ON_ONCE (p->scx.dsq || !list_empty (&p->scx.dsq_list.node));WARN_ON_ONCE ((p->scx.dsq_flags &SCX_TASK_DSQ_ON_PRIQ ) || !RB_EMPTY_NODE (&p->scx.dsq_priq)); -if (!is_local) { +if (!is_rq_owned) {raw_spin_lock_nested (&dsq->lock, (enq_flags &SCX_ENQ_NESTED ) ?SINGLE_DEPTH_NESTING :0 );
@@ -1435,8 +1445,8 @@ static void scx_dispatch_enqueue(struct scx_sched *sch, struct rq *rq,* ops_state first, both sides would modify p->scx.flags * concurrently in a non-atomic way. */ -if (is_local) { -local_dsq_post_enq (sch, dsq, p, enq_flags); +if (is_rq_owned) { +rq_owned_post_enq (sch, rq, dsq, p, enq_flags); }else {/* * Global and bypass DSQs are terminal - the task leaves the
@@ -1487,7 +1497,7 @@ static void task_unlink_from_dsq(struct task_struct *p,static void scx_dispatch_dequeue (struct rq *rq,struct task_struct *p) {struct scx_dispatch_q *dsq = p->scx.dsq; -bool is_local = dsq == &rq->scx.local_dsq; +bool is_rq_owned = dsq &&dsq_is_rq_owned (dsq);lockdep_assert_rq_held (rq);
@@ -1511,7 +1521,7 @@ static void scx_dispatch_dequeue(struct rq *rq, struct task_struct *p)return ; } -if (!is_local) +if (!is_rq_owned)raw_spin_lock (&dsq->lock);/*
@@ -1533,7 +1543,7 @@ static void scx_dispatch_dequeue(struct rq *rq, struct task_struct *p) } p->scx.dsq =NULL ; -if (!is_local) +if (!is_rq_owned)raw_spin_unlock (&dsq->lock); }
@@ -2085,7 +2095,7 @@ static void move_local_task_to_local_dsq(struct scx_sched *sch,dsq_inc_nr (dst_dsq, p, enq_flags); p->scx.dsq = dst_dsq; -local_dsq_post_enq (sch, dst_dsq, p, enq_flags); +rq_owned_post_enq (sch, dst_rq, dst_dsq, p, enq_flags); }/**
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 18/33 sched_ext: Add reject DSQ for cap-rejected dispatches
In reply to Tejun HeoWhen a sub-scheduler dispatches a task to a CPU it lacks the required capability on, the task must be rejected rather than allowed to run.
Add the machinery for that. Each rq gets a reject DSQ, a kernel-internal holding queue that is never run and that the BPF scheduler cannot reach. An insert that must be refused is diverted there instead of the local DSQ, and a deferred requeue then hands the parked tasks back to the BPF scheduler to re-decide. A cap revoke extends this to already-queued tasks. When the revoke reaches the cpu's effective caps, the cpu scans its local DSQ and reenqueues the tasks that no longer qualify.
A migration-disabled task must run on its cpu, so a capless one is admitted anyway and counted in the new SCX_EV_SUB_FORCED_ADMIT event.
This is preparation for the actual sub-sched cap enforcement. The divert is wired but inert here.
v2: Admit offline-rq and migration_pending inserts to local, not reject. (sashiko AI)
--- include/linux/sched/ext.h | 15 ++++- kernel/sched/ext/ext.c | 42 ++++++++++-- kernel/sched/ext/internal.h | 19 +++++- kernel/sched/ext/sub.c | 127 +++++++++++++++++++++++++++++++++++- kernel/sched/ext/sub.h | 49 ++++++++++++++ kernel/sched/sched.h | 3 + 6 files changed, 244 insertions(+), 11 deletions(-)
include/linux/sched/ext.h +13 -2
@@ -58,6 +58,7 @@ enum scx_dsq_id_flags {SCX_DSQ_GLOBAL =SCX_DSQ_FLAG_BUILTIN |1 ,SCX_DSQ_LOCAL =SCX_DSQ_FLAG_BUILTIN |2 ,SCX_DSQ_BYPASS =SCX_DSQ_FLAG_BUILTIN |3 , +SCX_DSQ_REJECT =SCX_DSQ_FLAG_BUILTIN |4 ,/* internal - see find_dsq_for_dispatch() */ SCX_DSQ_LOCAL_ON =SCX_DSQ_FLAG_BUILTIN |SCX_DSQ_FLAG_LOCAL_ON , SCX_DSQ_LOCAL_CPU_MASK = 0xffffffffLLU, };
@@ -124,7 +125,7 @@ enum scx_ent_flags { SCX_TASK_DEAD = 5 << SCX_TASK_STATE_SHIFT,/* -* Bits 12 and 13 are used to carry reenqueue reason. In addition to +* Bits 12 to 14 are used to carry reenqueue reason. In addition to * %SCX_ENQ_REENQ flag, ops.enqueue() can also test for * %SCX_TASK_REENQ_REASON_NONE to distinguish reenqueues. *
@@ -132,15 +133,17 @@ enum scx_ent_flags {* KFUNC reenqueued by scx_bpf_dsq_reenq() and friends * IMMED reenqueued due to failed ENQ_IMMED * PREEMPTED preempted while running +* CAP sub-sched cap miss, see p->scx.reenq_reason_* */ SCX_TASK_REENQ_REASON_SHIFT =12 , -SCX_TASK_REENQ_REASON_BITS =2 , +SCX_TASK_REENQ_REASON_BITS =3 ,SCX_TASK_REENQ_REASON_MASK = ((1 <<SCX_TASK_REENQ_REASON_BITS ) -1 ) <<SCX_TASK_REENQ_REASON_SHIFT ,SCX_TASK_REENQ_NONE =0 <<SCX_TASK_REENQ_REASON_SHIFT ,SCX_TASK_REENQ_KFUNC =1 <<SCX_TASK_REENQ_REASON_SHIFT ,SCX_TASK_REENQ_IMMED =2 <<SCX_TASK_REENQ_REASON_SHIFT ,SCX_TASK_REENQ_PREEMPTED =3 <<SCX_TASK_REENQ_REASON_SHIFT , +SCX_TASK_REENQ_CAP =4 <<SCX_TASK_REENQ_REASON_SHIFT ,/* iteration cursor, not a task */ SCX_TASK_CURSOR = 1 << 31,
@@ -239,6 +242,14 @@ struct sched_ext_entity {*/ u64 dsq_vtime; +/* +* Sub-sched cap rejected reenq context, valid only while +* %SCX_TASK_REENQ_CAP is set. @reenq_reason_caps is the SCX_CAP_* bits +* that were needed but missing. @reenq_reason_cid is the target cid. +*/ +u64 reenq_reason_caps; +s32 reenq_reason_cid; +/* * If set, reject future sched_setscheduler(2) calls updating the policy * to %SCHED_EXT with -%EACCES.
kernel/sched/ext/ext.c +35 -7
114 lines not on this page · raw message
kernel/sched/ext/internal.h +18 -1
@@ -1135,6 +1135,13 @@ struct scx_event_stats {* from sub_bypass_dsq's. */ s64 SCX_EV_SUB_BYPASS_DISPATCH ; + +/* +* The number of times a migration-disabled task lacking the cap for its +* cid was allowed onto the local DSQ. It must run on its pinned CPU, so +* it can't be rejected. The violation is counted here. +*/ +s64 SCX_EV_SUB_FORCED_ADMIT ; };#define SCX_EVENTS_LIST (SCX_EVENT ) \
@@ -1150,7 +1157,8 @@ struct scx_event_stats {SCX_EVENT (SCX_EV_BYPASS_DISPATCH ); \SCX_EVENT (SCX_EV_BYPASS_ACTIVATE ); \SCX_EVENT (SCX_EV_INSERT_NOT_OWNED ); \ -SCX_EVENT (SCX_EV_SUB_BYPASS_DISPATCH) +SCX_EVENT (SCX_EV_SUB_BYPASS_DISPATCH ); \ +SCX_EVENT (SCX_EV_SUB_FORCED_ADMIT) struct scx_sched;
@@ -1270,6 +1278,9 @@ enum scx_cap_flags { __SCX_CAP_ALL =BIT_U64 (__SCX_NR_CAPS) -1 ,SCX_CAP_DUMMY =BIT_U64 (__SCX_CAP_DUMMY), + +/* caps whose loss strands queued tasks, see scx_process_sync_ecaps() */ + SCX_CAPS_REENQ_ON_LOSS = 0, };#ifdef CONFIG_EXT_SUB_SCHED
@@ -1583,6 +1594,9 @@ enum scx_reenq_flags {/* low 16bits determine which tasks should be reenqueued */ SCX_REENQ_ANY =1LLU <<0 ,/* all tasks */ +/* internal: kernel-issued on cap revoke, not accepted from BPF */ +SCX_REENQ_CAP_REVOKE =1LLU <<1 , + __SCX_REENQ_FILTER_MASK =0xffffLLU , __SCX_REENQ_USER_MASK = SCX_REENQ_ANY,
@@ -1835,6 +1849,9 @@ void scx_task_iter_start(struct scx_task_iter *iter, struct cgroup *cgrp);void scx_task_iter_unlock (struct scx_task_iter *iter);void scx_task_iter_stop (struct scx_task_iter *iter);struct task_struct *scx_task_iter_next_locked (struct scx_task_iter *iter); +void scx_dispatch_dequeue (struct rq *rq,struct task_struct *p); +void scx_do_enqueue_task (struct rq *rq,struct task_struct *p,u64 enq_flags, +int sticky_cpu);bool scx_consume_dispatch_q (struct scx_sched *sch,struct rq *rq,struct scx_dispatch_q *dsq,u64 enq_flags);bool scx_consume_global_dsq (struct scx_sched *sch,struct rq *rq);
kernel/sched/ext/sub.c +126 -1
160 lines not on this page · raw message
kernel/sched/ext/sub.h +49 -0
73 lines not on this page · raw message
kernel/sched/sched.h +3 -0
@@ -794,6 +794,9 @@ enum scx_rq_flags {struct scx_rq {struct scx_dispatch_q local_dsq; +#ifdef CONFIG_EXT_SUB_SCHED +struct scx_dispatch_q reject_dsq;/* staging for cap-rejected tasks */ +#endif struct list_head runnable_list;/* runnable tasks on this rq */ struct list_head ddsp_deferred_locals;/* deferred ddsps from enq */ unsigned long ops_qseq;
Signature · 1 line
2.55.0
Andrea Righi
reviewerRe: [PATCH v5 sched_ext/for-7.3 18/33] sched_ext: Add reject DSQ for cap-rejected dispatches
Hi Tejun,
Quoted 21 lines · Tejun Heo
When a sub-scheduler dispatches a task to a CPU it lacks the required capability on, the task must be rejected rather than allowed to run.
Add the machinery for that. Each rq gets a reject DSQ, a kernel-internal holding queue that is never run and that the BPF scheduler cannot reach. An insert that must be refused is diverted there instead of the local DSQ, and a deferred requeue then hands the parked tasks back to the BPF scheduler to re-decide. A cap revoke extends this to already-queued tasks. When the revoke reaches the cpu's effective caps, the cpu scans its local DSQ and reenqueues the tasks that no longer qualify.
A migration-disabled task must run on its cpu, so a capless one is admitted anyway and counted in the new
SCX_EV_SUB_FORCED_ADMITevent.This is preparation for the actual sub-sched cap enforcement. The divert is wired but inert here.
v2: Admit offline-rq and
migration_pendinginserts to local, not reject. (sashiko AI)Signed-off-by Tejun Heo <[email protected]>---
...
kernel/sched/ext/ext.c static void scx_dispatch_enqueue(struct scx_sched *sch, struct rq *rq, · line 1359
Quoted 11 lines
kernel/sched/ext/ext.c +6
-1@@ -1344,7 +1351,12 @@ static void scx_dispatch_enqueue(struct scx_sched *sch, struct rq *rq, struct scx_dispatch_q *dsq, struct task_struct *p, u64 enq_flags) { - bool is_rq_owned = dsq_is_rq_owned(dsq); + bool is_rq_owned = false; + +if (dsq->id ==SCX_DSQ_LOCAL ) { + dsq =scx_local_or_reject_dsq (sch, rq, p, &enq_flags); + is_rq_owned = true; + }
With CONFIG_EXT_SUB_SCHED=y, this calls scx_local_or_reject_dsq() for every local DSQ insertion even when there are no sub-schedulers attached. It shouldn't be too bad, but the hot path still pays for the out-of-line call and the CID/capability bookkeeping.
Maybe the same static key that I suggested for the ops.update_idle() case (PATCH 28/33) can be used here as well and we could do something like:
if (!static_branch_unlikely(&scx_has_sub_scheds))
return &rq->scx.local_dsq;Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH v5 sched_ext/for-7.3 18/33] sched_ext: Add reject DSQ for cap-rejected dispatches
Hello, Andrea.
Quoted 10 lines · Andrea Righi
With
CONFIG_EXT_SUB_SCHED=y, this callsscx_local_or_reject_dsq()for every local DSQ insertion even when there are no sub-schedulers attached. It shouldn't be too bad, but the hot path still pays for the out-of-line call and the CID/capability bookkeeping.Maybe the same static key that I suggested for the
ops.update_idle()case (PATCH 28/33) can be used here as well and we could do something like:if (!static_branch_unlikely(&scx_has_sub_scheds)) return &rq->scx.local_dsq;
Yeah, this and the other sub-sched hot paths will be gated behind the static key in follow-up patches.
Thanks.
--
tejun
Tejun Heo
reviewerPATCH v5 19/33 sched_ext: Add SCX_ENQ_IGNORE_CAPS for in-place restore
In reply to Tejun HeoA SAVE/RESTORE requeue re-inserts a running task in place and is immediately followed by set_next_task_scx(). It is not a real scheduling event: the task is already admitted to its cid and must return to the local DSQ unconditionally.
scx_caps_for_enq() maps an enqueue to the cap its local-DSQ insert requires. Add SCX_ENQ_IGNORE_CAPS, set it on the RESTORE-in-place branch of enqueue_task_scx(), and have scx_caps_for_enq() require no caps for it, so the cid admission gate never diverts an in-place restore to the reject DSQ.
--- kernel/sched/ext/ext.c | 7 +++++-- kernel/sched/ext/internal.h | 1 + kernel/sched/ext/sub.h | 3 +++ 3 files changed, 9 insertions(+), 2 deletions(-)
kernel/sched/ext/ext.c +5 -2
@@ -1878,10 +1878,13 @@ static void enqueue_task_scx(struct rq *rq, struct task_struct *p, int core_enq_* Restoring a running task will be immediately followed by * set_next_task_scx() which expects the task to not be on the BPF * scheduler as tasks can only start running through local DSQs. Force -* direct-dispatch into the local DSQ by setting the sticky_cpu. +* direct-dispatch into the local DSQ by setting the sticky_cpu. Mark +* IGNORE_CAPS to force entry into the local DSQ. */ -if (unlikely (enq_flags &ENQUEUE_RESTORE ) &&task_current (rq, p)) +if (unlikely (enq_flags &ENQUEUE_RESTORE ) &&task_current (rq, p)) { sticky_cpu =cpu_of (rq); + enq_flags |=SCX_ENQ_IGNORE_CAPS ; + }if (p->scx.flags &SCX_TASK_QUEUED ) {WARN_ON_ONCE (!task_runnable (p));
kernel/sched/ext/internal.h +1 -0
@@ -1568,6 +1568,7 @@ enum scx_enq_flags {SCX_ENQ_DSQ_PRIQ =1LLU <<57 ,SCX_ENQ_NESTED =1LLU <<58 ,SCX_ENQ_GDSQ_FALLBACK =1LLU <<59 ,/* fell back to global DSQ */ + SCX_ENQ_IGNORE_CAPS = 1LLU << 60, /* admit to local DSQ ignoring caps */ }; enum scx_deq_flags {
kernel/sched/ext/sub.h +3 -0
@@ -106,6 +106,9 @@ static inline u64 scx_missing_caps(struct scx_sched *sch, s32 cpu, u64 needed)/* map @enq_flags to the SCX_CAP_* bit required for the local-DSQ insert */ static inline u64 scx_caps_for_enq (u64 enq_flags) { +/* a restored task must be put into the local DSQ regardless of caps */ +if (enq_flags &SCX_ENQ_IGNORE_CAPS ) +return 0 ;return 0 ; }
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 20/33 sched_ext: Add the SCX_CAP_ENQ_IMMED cap
In reply to Tejun HeoReplace the __SCX_CAP_DUMMY placeholder with SCX_CAP_ENQ_IMMED, which gates inserting IMMED tasks onto a cid's local DSQ. An IMMED enqueue is guaranteed to either get its task running on the cpu at once or hand it back to the scheduler, so IMMED work can never pile up on the cpu's queue and a cpu can be shared across sub-scheds through IMMED access without any of them swamping it.
That makes ENQ_IMMED the natural baseline, the minimal cap to make any use of a cpu. SCX_CAP_BASE aliases it so gates on basic cpu access can state the intention instead of naming ENQ_IMMED.
Enforcement covers inserts and queued tasks. An insert without the cap is diverted to the reject DSQ, and queued tasks are reenqueued when the cap is lost. scx_bpf_sub_dispatch() skips a child that lacks the cap on the cpu, as its inserts would only be rejected. Vacating the running task on cap loss lands in a later patch.
--- kernel/sched/ext/ext.c | 2 +- kernel/sched/ext/internal.h | 11 ++++++++--- kernel/sched/ext/sub.c | 8 ++++++++ kernel/sched/ext/sub.h | 4 ++-- 4 files changed, 19 insertions(+), 6 deletions(-)
kernel/sched/ext/ext.c +1 -1
@@ -4792,7 +4792,7 @@ SCX_ATTR(events);#ifdef CONFIG_EXT_SUB_SCHED static const char *scx_cap_names[__SCX_NR_CAPS] = { - [__SCX_CAP_DUMMY] ="dummy" , + [__SCX_CAP_ENQ_IMMED] ="enq_immed" , }; static ssize_t scx_attr_caps_show(struct kobject *kobj,
kernel/sched/ext/internal.h +8 -3
@@ -1270,17 +1270,22 @@ struct scx_sched_pnode {* topology-aligned and likely to serve as the locality unit when cids are * allocated to schedulers, so per-shard lock granularity scales naturally with * the allocation pattern. +* +* ENQ_IMMED insert an IMMED task onto the cid's local DSQ */ enum scx_cap_flags { - __SCX_CAP_DUMMY =0 , + __SCX_CAP_ENQ_IMMED =0 , __SCX_NR_CAPS, __SCX_CAP_ALL =BIT_U64 (__SCX_NR_CAPS) -1 , -SCX_CAP_DUMMY =BIT_U64 (__SCX_CAP_DUMMY), +SCX_CAP_ENQ_IMMED =BIT_U64 (__SCX_CAP_ENQ_IMMED), + +/* alias for minimal cap to make any use of a cpu */ +SCX_CAP_BASE =SCX_CAP_ENQ_IMMED ,/* caps whose loss strands queued tasks, see scx_process_sync_ecaps() */ -SCX_CAPS_REENQ_ON_LOSS =0 , +SCX_CAPS_REENQ_ON_LOSS =SCX_CAP_ENQ_IMMED , };#ifdef CONFIG_EXT_SUB_SCHED
kernel/sched/ext/sub.c +8 -0
@@ -1279,6 +1279,14 @@ __bpf_kfunc bool scx_bpf_sub_dispatch(u64 cgroup_id, const struct bpf_prog_aux *return false; } +/* +* Skip a child that does not effectively hold the base cap on this cpu: +* its inserts would only be rejected. ecaps are synced at the top of +* balance_one() before dispatch, so this reflects the in-effect state. +*/ +if (scx_missing_caps (child,cpu_of (this_rq),SCX_CAP_BASE )) +return false; +return scx_dispatch_sched (child, this_rq, this_rq->scx.sub_dispatch_prev, true); }
kernel/sched/ext/sub.h +2 -2
@@ -109,13 +109,13 @@ static inline u64 scx_caps_for_enq(u64 enq_flags)/* a restored task must be put into the local DSQ regardless of caps */ if (enq_flags &SCX_ENQ_IGNORE_CAPS )return 0 ; -return 0 ; +return SCX_CAP_ENQ_IMMED ; }/* map queued @p to the SCX_CAP_* bit required to stay on its local DSQ */ static inline u64 scx_caps_for_task (struct task_struct *p) { -return 0 ; +return SCX_CAP_ENQ_IMMED ; }/* caps implied by holding @cap */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 21/33 sched_ext: Assign a unique id to each scheduler instance
In reply to Tejun HeoNeither a scx_sched pointer nor its cgroup id uniquely identifies a scheduler instance. A freed sched's memory can be reallocated, and a cgroup can detach one sched and attach another. Add a monotonic, never-reused u64 id. A later patch compares it to drop a slice request that outlived a change of a task's owning scheduler.
--- kernel/sched/ext/ext.c | 4 ++++ kernel/sched/ext/internal.h | 3 +++ 2 files changed, 7 insertions(+)
kernel/sched/ext/ext.c +4 -0
@@ -108,6 +108,9 @@ static bool dsq_is_rq_owned(struct scx_dispatch_q *dsq) } } +/* Cursor for unique scx_sched instance ids. id 0 is reserved. */ +static atomic64_t scx_sched_id_cursor =ATOMIC64_INIT (0 ); +#ifdef CONFIG_EXT_SUB_SCHED /* * The sub sched being enabled. Used by scx_disable_and_exit_task() to exit
@@ -6500,6 +6503,7 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd, level * sizeof(parent->ancestors[0])); sch->ancestors[level] = sch; sch->level = level; + sch->id =atomic64_inc_return (&scx_sched_id_cursor);if (ops->timeout_ms) sch->watchdog_timeout =msecs_to_jiffies (ops->timeout_ms);
kernel/sched/ext/internal.h +3 -0
@@ -1445,6 +1445,9 @@ struct scx_sched {struct list_head all; +/* unique instance id, monotonic and never reused */ +u64 id; +#ifdef CONFIG_EXT_SUB_SCHED struct rhash_head hash_node;
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 22/33 sched_ext: Route task slice writes through set_task_slice()
In reply to Tejun HeoA later change makes set_task_slice() also drop a pending out-of-band slice request, so the BPF-triggered writes to p->scx.slice need to funnel through one place. Introduce set_task_slice() and route those writes through it. update_curr_scx() decrements curr->scx.slice directly for accounting and is left alone. No functional change - the helper only assigns p->scx.slice.
v2: Reword the set_task_slice comment to "BPF-triggered writes". (Andrea)
--- kernel/sched/ext/ext.c | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-)
kernel/sched/ext/ext.c +19 -13
@@ -1165,6 +1165,12 @@ static void touch_core_sched_dispatch(struct rq *rq, struct task_struct *p)#endif } +/* set @p's slice, BPF-triggered writes to p->scx.slice go through here */ +static void set_task_slice (struct task_struct *p,u64 slice) +{ + p->scx.slice = slice; +} +static void update_curr_scx (struct rq *rq) {struct task_struct *curr = rq->curr;
@@ -1250,7 +1256,7 @@ static void dsq_dec_nr(struct scx_dispatch_q *dsq, struct task_struct *p)static void refill_task_slice_dfl (struct scx_sched *sch,struct task_struct *p) { - p->scx.slice =READ_ONCE (sch->slice_dfl); +set_task_slice (p,READ_ONCE (sch->slice_dfl));__scx_add_event (sch,SCX_EV_REFILL_SLICE_DFL ,1 ); }
@@ -1345,7 +1351,7 @@ static void rq_owned_post_enq(struct scx_sched *sch, struct rq *rq,if ((enq_flags &SCX_ENQ_PREEMPT ) && p != rq->curr && rq->curr->sched_class == &ext_sched_class) { - rq->curr->scx.slice =0 ; +set_task_slice (rq->curr,0 );resched_curr (rq); } }
@@ -2058,7 +2064,7 @@ static void yield_task_scx(struct rq *rq)if (SCX_HAS_OP (sch, yield))SCX_CALL_OP_2TASKS_RET (sch, yield, rq, p,NULL );else - p->scx.slice =0 ; +set_task_slice (p,0 ); }static bool yield_to_task_scx (struct rq *rq,struct task_struct *to)
@@ -3302,7 +3308,7 @@ static void task_tick_scx(struct rq *rq, struct task_struct *curr, int queued)* we can't trust the slice management or ops.core_sched_before(). */ if (scx_bypassing (sch,cpu_of (rq))) { - curr->scx.slice =0 ; +set_task_slice (curr,0 );touch_core_sched (rq, curr); }else if (SCX_HAS_OP (sch, tick)) {SCX_CALL_OP_TASK (sch, tick, rq, curr);
@@ -3441,7 +3447,7 @@ static void scx_disable_task(struct scx_sched *sch, struct task_struct *p)* control, after ops.disable() has observed their final values. */ p->scx.dsq_vtime =0 ; - p->scx.slice =0 ; +set_task_slice (p,0 );/* * Verify the task is not in BPF scheduler's custody. If flag
@@ -7091,7 +7097,7 @@ static void scx_root_enable_workfn(struct kthread_work *work) queue_flags |=DEQUEUE_CLASS ; scoped_guard (sched_change, p, queue_flags) { - p->scx.slice =READ_ONCE (sch->slice_dfl); +set_task_slice (p,READ_ONCE (sch->slice_dfl)); p->sched_class = new_class; } }
@@ -7734,7 +7740,7 @@ static bool kick_one_cpu(s32 cpu, struct scx_sched_pcpu *pcpu, struct rq *this_r !sched_class_above(cur_class, &ext_sched_class)) {if (cpumask_test_cpu (cpu, pcpu->cpus_to_preempt)) {if (cur_class == &ext_sched_class) - rq->curr->scx.slice =0 ; +set_task_slice (rq->curr,0 );cpumask_clear_cpu (cpu, pcpu->cpus_to_preempt); }
@@ -8084,9 +8090,9 @@ __bpf_kfunc bool scx_bpf_dsq_insert___v2(struct task_struct *p, u64 dsq_id,return false;if (slice) - p->scx.slice = slice; +set_task_slice (p, slice);else - p->scx.slice = p->scx.slice ?:1 ; +set_task_slice (p, p->scx.slice ?:1 );scx_dsq_insert_commit (sch, p, dsq_id, enq_flags);
@@ -8110,9 +8116,9 @@ static bool scx_dsq_insert_vtime(struct scx_sched *sch, struct task_struct *p,return false;if (slice) - p->scx.slice = slice; +set_task_slice (p, slice);else - p->scx.slice = p->scx.slice ?:1 ; +set_task_slice (p, p->scx.slice ?:1 ); p->scx.dsq_vtime = vtime;
@@ -8294,7 +8300,7 @@ static bool scx_dsq_move(struct bpf_iter_scx_dsq_kern *kit,if (kit->cursor.flags & __SCX_DSQ_ITER_HAS_VTIME) p->scx.dsq_vtime = kit->vtime;if (kit->cursor.flags & __SCX_DSQ_ITER_HAS_SLICE) - p->scx.slice = kit->slice; +set_task_slice (p, kit->slice);/* execute move */ locked_rq =move_task_between_dsqs (sch, p, enq_flags, src_dsq, dst_dsq);
@@ -8687,7 +8693,7 @@ __bpf_kfunc bool scx_bpf_task_set_slice(struct task_struct *p, u64 slice,if (unlikely (!sch || !scx_task_on_sched (sch, p)))return false; - p->scx.slice = slice; +set_task_slice (p, slice);return true; }
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 23/33 sched_ext: Track the cpu a task is runnable on
In reply to Tejun HeoAdd p->scx.runnable_cpu, the cpu @p is runnable on, or -1 when it is not. It is stamped as @p joins the runnable_list (set_task_runnable()) and cleared as it leaves (clr_task_runnable()), both under the rq lock.
task_cpu() can't answer "is @p on this rq" reliably: a remote wakeup changes it under @p's pi_lock alone, without the source rq lock, so it can read as the locked rq while @p is really elsewhere. runnable_cpu changes only under the rq lock, so a caller holding an rq lock can compare against it to know whether that is @p's current rq.
--- include/linux/sched/ext.h | 1 + init/init_task.c | 1 + kernel/sched/ext/ext.c | 9 +++++++++ 3 files changed, 11 insertions(+)
include/linux/sched/ext.h +1 -0
@@ -201,6 +201,7 @@ struct sched_ext_entity {s32 sticky_cpu;s32 holding_cpu;s32 selected_cpu; +s32 runnable_cpu;/* cpu @p is runnable on, -1 if not */ struct task_struct *kf_tasks[2 ];/* see SCX_CALL_OP_TASK() */ struct list_head runnable_node;/* rq->scx.runnable_list */
init/init_task.c +1 -0
@@ -145,6 +145,7 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = { .dsq_list.node = LIST_HEAD_INIT(init_task.scx.dsq_list.node), .sticky_cpu = -1, .holding_cpu = -1, + .runnable_cpu = -1, .runnable_node = LIST_HEAD_INIT(init_task.scx.runnable_node), .runnable_at = INITIAL_JIFFIES, .ddsp_dsq_id = SCX_DSQ_INVALID,
kernel/sched/ext/ext.c +9 -0
@@ -1865,11 +1865,19 @@ static void set_task_runnable(struct rq *rq, struct task_struct *p)* appended to the runnable_list. */ list_add_tail (&p->scx.runnable_node, &rq->scx.runnable_list); + +/* +* Record the rq @p is runnable on, maintained under the rq lock so it +* stays valid unlike task_cpu(), which a remote wakeup can move under +* pi_lock alone. +*/ +WRITE_ONCE (p->scx.runnable_cpu,cpu_of (rq)); }static void clr_task_runnable (struct task_struct *p,bool reset_runnable_at) {list_del_init (&p->scx.runnable_node); +WRITE_ONCE (p->scx.runnable_cpu,-1 );if (reset_runnable_at) p->scx.flags |=SCX_TASK_RESET_RUNNABLE_AT ; }
@@ -3531,6 +3539,7 @@ void init_scx_entity(struct sched_ext_entity *scx)RB_CLEAR_NODE (&scx->dsq_priq); scx->sticky_cpu =-1 ; scx->holding_cpu =-1 ; + scx->runnable_cpu =-1 ;INIT_LIST_HEAD (&scx->runnable_node); scx->runnable_at = jiffies; scx->ddsp_dsq_id =SCX_DSQ_INVALID ;
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 24/33 sched_ext: Tie cpu occupancy to SCX_CAP_BASE through the task slice
In reply to Tejun HeoA task's slice grants it cpu occupancy - how long it holds its cpu. In a sub-scheduler hierarchy cpu access is delegated through revocable capabilities, so a task's occupancy must follow them. Only its own scheduler sets its slice, and extending the slice is allowed only while that scheduler holds baseline cpu access (SCX_CAP_BASE) on the cpu. Otherwise a scheduler could keep occupying a cpu it has been denied simply by handing out long slices.
The cap check reads effective caps, which are coherent only under the task's rq lock, and the kernel decrements the slice under that lock as the task runs, so a running task's slice can be changed only there while a queued task's can be set directly. Make scx_bpf_task_set_slice() apply the slice under the rq lock. Synchronously when the caller already holds it, otherwise by stashing it in the new p->scx.slice_oob, tagged with the scheduler's id so a request that outlived a reassignment is dropped. Whether the caller holds @p's current rq lock is tested with p->scx.runnable_cpu.
Revocation is enforced through the same grant. When a cpu's effective caps lose SCX_CAP_BASE, the cap-revoke reenq scan also checks the running task and zeroes its slice to evict it. The scan runs as a balance callback after the pick, so this catches both the task that was running when the revoke landed and a capless task the pick just promoted off the local DSQ. The paths that keep a task on its cpu - holding on to the last runnable task in balance, the ENQ_LAST reinsertion and the slice refill on pick - skip tasks lacking baseline access. A migration-disabled task is exempt, mirroring its capless admission on insert.
v4: Test rq ownership with p->scx.runnable_cpu, closing a remote-wakeup TOCTOU. (sashiko AI)
v3: Keep a pending out-of-band slice request across refill and preserve. (sashiko AI)
v2: Only write slice directly when @p is queued on the held rq. (sashiko AI)
--- include/linux/sched/ext.h | 17 ++- kernel/sched/ext/ext.c | 200 ++++++++++++++++++++++++++++++++++-- kernel/sched/ext/internal.h | 19 +++- kernel/sched/ext/sub.h | 11 ++ 4 files changed, 231 insertions(+), 16 deletions(-)
include/linux/sched/ext.h +13 -4
@@ -223,10 +223,11 @@ struct sched_ext_entity {/* BPF scheduler modifiable fields */ /* -* Runtime budget in nsecs. This is usually set through -* scx_bpf_dsq_insert() 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. +* Runtime budget in nsecs - how long the task may hold its cpu. Owned +* by the task's scheduler. Set it when enqueuing via +* scx_bpf_dsq_insert(), or otherwise via scx_bpf_task_set_slice(). +* Automatically decreased 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
@@ -243,6 +244,14 @@ struct sched_ext_entity {*/ u64 dsq_vtime; +/* +* Out-of-band slice request from scx_bpf_task_set_slice() when the +* caller does not hold the rq lock, applied under the rq lock at the +* next slice consideration. One atomic64 packs the pending flag, the +* issuing sch's id, and the requested slice. See scx_slice_oob_consts. +*/ +atomic64_t slice_oob; +/* * Sub-sched cap rejected reenq context, valid only while * %SCX_TASK_REENQ_CAP is set. @reenq_reason_caps is the SCX_CAP_* bits
kernel/sched/ext/ext.c +190 -10
284 lines not on this page · raw message
kernel/sched/ext/internal.h +17 -2
@@ -400,8 +400,9 @@ struct sched_ext_ops {* @p: task running currently * * This operation is called every 1/HZ seconds on CPUs which are -* executing an SCX task. Setting @p->scx.slice to 0 will trigger an -* immediate dispatch cycle on the CPU. +* executing an SCX task. Setting a slice of 0 for @p with +* scx_bpf_task_set_slice() will trigger an immediate dispatch cycle on +* the CPU. */ void (*tick)(struct task_struct *p);
@@ -1103,6 +1104,18 @@ struct scx_event_stats {*/ s64 SCX_EV_REFILL_SLICE_DFL ; +/* +* The number of times an out-of-band slice request exceeded the maximum +* representable value and was clamped. +*/ +s64 SCX_EV_SLICE_CLAMPED ; + +/* +* The number of times a slice extension was denied because the +* scheduler lacked baseline cpu access on the task's cpu. +*/ +s64 SCX_EV_SLICE_DENIED ; +/* * The total duration of bypass modes in nanoseconds. */
@@ -1153,6 +1166,8 @@ struct scx_event_stats {SCX_EVENT (SCX_EV_REENQ_IMMED ); \SCX_EVENT (SCX_EV_REENQ_LOCAL_REPEAT ); \SCX_EVENT (SCX_EV_REFILL_SLICE_DFL ); \ +SCX_EVENT (SCX_EV_SLICE_CLAMPED ); \ +SCX_EVENT (SCX_EV_SLICE_DENIED ); \SCX_EVENT (SCX_EV_BYPASS_DURATION ); \SCX_EVENT (SCX_EV_BYPASS_DISPATCH ); \SCX_EVENT (SCX_EV_BYPASS_ACTIVATE ); \
kernel/sched/ext/sub.h +11 -0
@@ -124,9 +124,20 @@ static inline u64 scx_caps_implied(u64 cap) return 0; } +/* may @p keep running on @rq's cpu? requires baseline cpu access */ +static inline bool scx_task_can_stay_on_cpu (struct rq *rq,struct task_struct *p) +{ +/* a migration-disabled task is let in without caps, keep it likewise */ +if (unlikely (is_migration_disabled (p))) +return true; + +return likely (!scx_missing_caps (scx_task_sched (p),cpu_of (rq),SCX_CAP_BASE )); +} +#else /* CONFIG_EXT_SUB_SCHED */ static inline u64 scx_missing_caps (struct scx_sched *sch,s32 cpu,u64 needed) {return 0 ; } +static inline bool scx_task_can_stay_on_cpu (struct rq *rq,struct task_struct *p) {return true; }#endif /* CONFIG_EXT_SUB_SCHED */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 25/33 sched_ext: Add the SCX_CAP_ENQ cap
In reply to Tejun HeoAdd SCX_CAP_ENQ, which gates inserting tasks onto a cid's local DSQ. Unlike IMMED enqueue, plain enqueues can pile up, so ENQ is the stronger cap and implies ENQ_IMMED. Losing ENQ also triggers the reenq scan. The scan tests each queued task and the running task against the cap each needs via scx_caps_for_task(), so an ENQ-only loss reenqueues plain tasks, evicting a running one, while IMMED tasks, which need only ENQ_IMMED, stay put.
--- kernel/sched/ext/ext.c | 1 + kernel/sched/ext/internal.h | 14 +++++++++++--- kernel/sched/ext/sub.h | 12 ++++++++++-- 3 files changed, 22 insertions(+), 5 deletions(-)
kernel/sched/ext/ext.c +1 -0
@@ -4963,6 +4963,7 @@ SCX_ATTR(events);#ifdef CONFIG_EXT_SUB_SCHED static const char *scx_cap_names[__SCX_NR_CAPS] = { [__SCX_CAP_ENQ_IMMED] ="enq_immed" , + [__SCX_CAP_ENQ] ="enq" , }; static ssize_t scx_attr_caps_show(struct kobject *kobj,
kernel/sched/ext/internal.h +11 -3
@@ -1224,8 +1224,8 @@ struct scx_sched_pcpu {/* * pshard->caps[cap_bit] is the set of cids the sched holds that one * cap on. ecaps is its transpose: the set of SCX_CAP_* bits the sched -* holds on this cpu, collected so that the hot-path check is a single -* read. +* effectively holds on this cpu, with implied caps folded in, so that +* the hot-path check is a single read. * * While pshard->caps[] under pshard->lock is the target configuration, * ecaps is the effective copy owned by the cpu. It is written under the
@@ -1287,20 +1287,28 @@ struct scx_sched_pnode {* the allocation pattern. * * ENQ_IMMED insert an IMMED task onto the cid's local DSQ +* +* ENQ insert any task onto the cid's local DSQ (implies ENQ_IMMED) +* +* Implied caps apply to the holder's own use of a cid, not to delegation. +* scx_bpf_sub_grant() delegates literally-held caps, so a cap held only through +* implication is usable but cannot be re-delegated to a child. */ enum scx_cap_flags { __SCX_CAP_ENQ_IMMED =0 , + __SCX_CAP_ENQ =1 , __SCX_NR_CAPS, __SCX_CAP_ALL =BIT_U64 (__SCX_NR_CAPS) -1 ,SCX_CAP_ENQ_IMMED =BIT_U64 (__SCX_CAP_ENQ_IMMED), +SCX_CAP_ENQ =BIT_U64 (__SCX_CAP_ENQ),/* alias for minimal cap to make any use of a cpu */ SCX_CAP_BASE =SCX_CAP_ENQ_IMMED ,/* caps whose loss strands queued tasks, see scx_process_sync_ecaps() */ -SCX_CAPS_REENQ_ON_LOSS =SCX_CAP_ENQ_IMMED , +SCX_CAPS_REENQ_ON_LOSS =SCX_CAP_ENQ_IMMED |SCX_CAP_ENQ , };#ifdef CONFIG_EXT_SUB_SCHED
kernel/sched/ext/sub.h +10 -2
@@ -109,18 +109,26 @@ static inline u64 scx_caps_for_enq(u64 enq_flags)/* a restored task must be put into the local DSQ regardless of caps */ if (enq_flags &SCX_ENQ_IGNORE_CAPS )return 0 ; -return SCX_CAP_ENQ_IMMED ; +if (enq_flags &SCX_ENQ_IMMED ) +return SCX_CAP_ENQ_IMMED ; +return SCX_CAP_ENQ ; }/* map queued @p to the SCX_CAP_* bit required to stay on its local DSQ */ static inline u64 scx_caps_for_task (struct task_struct *p) { -return SCX_CAP_ENQ_IMMED ; +if (p->scx.flags &SCX_TASK_IMMED ) +return SCX_CAP_ENQ_IMMED ; +return SCX_CAP_ENQ ; }/* caps implied by holding @cap */ static inline u64 scx_caps_implied (u64 cap) { +switch (cap) { +case SCX_CAP_ENQ : +return SCX_CAP_ENQ_IMMED ; + }return 0 ; }
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 26/33 sched_ext: Gate kicks on SCX_CAP_BASE and preemption on SCX_CAP_PREEMPT
In reply to Tejun HeoA kick forces a scheduling event on the target cpu, and a preemption also evicts the running task. Gate both on caps. Any kick requires baseline access on the cid, and preempting a task the sub-sched does not own - whether by a SCX_ENQ_PREEMPT insert or a SCX_KICK_PREEMPT kick - requires the new SCX_CAP_PREEMPT. Gating either alone would leave a hole - the weakest cap authorizing preempting kicks, or plain kicks disturbing cpus the kicker has no access to.
Preempting the sched's own subtree is always allowed, and the cap extends the right to any task on the cid. PREEMPT implies ENQ, and so ENQ_IMMED.
A preempting insert tests the running task under the target rq lock and is rejected and reenqueued unless the victim is in the inserter's subtree or it holds PREEMPT. A migration-disabled task is admitted regardless, but with SCX_ENQ_PREEMPT stripped.
Kicks are enforced on the delivery path, where the effective caps can be read coherently under the target rq's lock. A kick from a sub-sched lacking SCX_CAP_BASE on the cid is dropped, and a SCX_KICK_PREEMPT kick without PREEMPT for a task outside the kicker's subtree degrades to a plain reschedule.
Unlike the enqueue caps, PREEMPT is checked only at the instant of the insert or kick, never as a standing property of a queued task.
v2: Clear SCX_ENQ_PREEMPT on the offline and migration_pending force-admits.
--- kernel/sched/ext/ext.c | 34 +++++++++++++++++++++++++--------- kernel/sched/ext/internal.h | 24 ++++++++++++++++++++++-- kernel/sched/ext/sub.c | 19 +++++++++++++++---- kernel/sched/ext/sub.h | 15 +++++++++++++++ 4 files changed, 77 insertions(+), 15 deletions(-)
kernel/sched/ext/ext.c +25 -9
@@ -294,7 +294,7 @@ static bool u32_before(u32 a, u32 b)* * Test whether @sch is a descendant of @ancestor. */ -static bool scx_is_descendant (struct scx_sched *sch,struct scx_sched *ancestor) +bool scx_is_descendant (struct scx_sched *sch,struct scx_sched *ancestor) {if (sch->level < ancestor->level)return false;
@@ -4964,6 +4964,7 @@ SCX_ATTR(events);static const char *scx_cap_names[__SCX_NR_CAPS] = { [__SCX_CAP_ENQ_IMMED] ="enq_immed" , [__SCX_CAP_ENQ] ="enq" , + [__SCX_CAP_PREEMPT] ="preempt" , }; static ssize_t scx_attr_caps_show(struct kobject *kobj,
@@ -7896,13 +7897,22 @@ static bool kick_one_cpu(s32 cpu, struct scx_sched_pcpu *pcpu, struct rq *this_r* During CPU hotplug, a CPU may depend on kicking itself to make * forward progress. Allow kicking self regardless of online state. If * @cpu is running a higher class task, we have no control over @cpu. -* Skip kicking. +* Skip kicking. A sub-sched lacking baseline access on @cid has no +* business forcing a reschedule there - skip. This is the authoritative +* cap check: ecaps is read here under @rq's lock. */ if ((cpu_online (cpu) || cpu ==cpu_of (this_rq)) && - !sched_class_above (cur_class, &ext_sched_class)) { + !sched_class_above (cur_class, &ext_sched_class) && + !scx_missing_caps (pcpu->sch, cpu,SCX_CAP_BASE )) {if (cpumask_test_cpu (cpu, pcpu->cpus_to_preempt)) { -if (cur_class == &ext_sched_class) -set_task_slice (rq->curr,0 ); +if (cur_class == &ext_sched_class) { +if (likely (!scx_missing_caps (pcpu->sch, cpu, +scx_caps_for_preempt (pcpu->sch, rq)))) +set_task_slice (rq->curr,0 ); +else +__scx_add_event (pcpu->sch, +SCX_EV_SUB_PREEMPT_DENIED ,1 ); + }cpumask_clear_cpu (cpu, pcpu->cpus_to_preempt); }
@@ -7926,15 +7936,18 @@ static bool kick_one_cpu(s32 cpu, struct scx_sched_pcpu *pcpu, struct rq *this_rreturn should_wait; } -static void kick_one_cpu_if_idle (s32 cpu,struct rq *this_rq) +static void kick_one_cpu_if_idle (s32 cpu,struct scx_sched_pcpu *pcpu, +struct rq *this_rq) {struct rq *rq =cpu_rq (cpu);unsigned long flags;raw_spin_rq_lock_irqsave (rq, flags); +/* idle kicks need baseline access too, see kick_one_cpu() */ if (!can_skip_idle_kick (rq) && - (cpu_online (cpu) || cpu ==cpu_of (this_rq))) + (cpu_online (cpu) || cpu ==cpu_of (this_rq)) && + !scx_missing_caps (pcpu->sch, cpu,SCX_CAP_BASE ))resched_curr (rq);raw_spin_rq_unlock_irqrestore (rq, flags);
@@ -7971,7 +7984,7 @@ static void kick_cpus_irq_workfn(struct irq_work *irq_work) }for_each_cpu (cpu, pcpu->cpus_to_kick_if_idle) { -kick_one_cpu_if_idle (cpu, this_rq); +kick_one_cpu_if_idle (cpu, pcpu, this_rq);cpumask_clear_cpu (cpu, pcpu->cpus_to_kick_if_idle); } }
@@ -9008,7 +9021,10 @@ __bpf_kfunc void scx_bpf_kick_cpu(s32 cpu, u64 flags, const struct bpf_prog_aux* @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * * cid-addressed equivalent of scx_bpf_kick_cpu(). An invalid @cid aborts the -* scheduler via scx_cid_to_cpu(). +* scheduler via scx_cid_to_cpu(). Caps are enforced on the delivery path: a +* kick is dropped if the caller lacks baseline access on @cid, and a +* %SCX_KICK_PREEMPT degrades to a plain reschedule if the caller lacks +* %SCX_CAP_PREEMPT for a task outside its subtree. */ __bpf_kfunc void scx_bpf_kick_cid(s32 cid, u64 flags, const struct bpf_prog_aux *aux) {
kernel/sched/ext/internal.h +22 -2
@@ -1155,6 +1155,13 @@ struct scx_event_stats {* it can't be rejected. The violation is counted here. */ s64 SCX_EV_SUB_FORCED_ADMIT ; + +/* +* The number of times a preempting kick was refused because the +* sub-sched lacked SCX_CAP_PREEMPT for a task outside its subtree. The +* kick degrades to a plain reschedule. +*/ +s64 SCX_EV_SUB_PREEMPT_DENIED ; };#define SCX_EVENTS_LIST (SCX_EVENT ) \
@@ -1173,7 +1180,8 @@ struct scx_event_stats {SCX_EVENT (SCX_EV_BYPASS_ACTIVATE ); \SCX_EVENT (SCX_EV_INSERT_NOT_OWNED ); \SCX_EVENT (SCX_EV_SUB_BYPASS_DISPATCH ); \ -SCX_EVENT (SCX_EV_SUB_FORCED_ADMIT) +SCX_EVENT (SCX_EV_SUB_FORCED_ADMIT ); \ +SCX_EVENT (SCX_EV_SUB_PREEMPT_DENIED) struct scx_sched;
@@ -1287,22 +1295,33 @@ struct scx_sched_pnode {* the allocation pattern. * * ENQ_IMMED insert an IMMED task onto the cid's local DSQ +* - kick the cid's cpu (except SCX_KICK_PREEMPT) * * ENQ insert any task onto the cid's local DSQ (implies ENQ_IMMED) * +* PREEMPT preempt any task running on the cid regardless of the owning +* sched (implies ENQ). Preempting a task in the sched's own subtree +* doesn't require any cap. +* - SCX_ENQ_PREEMPT inserts +* - SCX_KICK_PREEMPT kicks +* * Implied caps apply to the holder's own use of a cid, not to delegation. * scx_bpf_sub_grant() delegates literally-held caps, so a cap held only through -* implication is usable but cannot be re-delegated to a child. +* implication is usable but cannot be re-delegated to a child. When granting a +* cap, it usually makes sense to delegate its implied caps explicitly alongside +* it. */ enum scx_cap_flags { __SCX_CAP_ENQ_IMMED =0 , __SCX_CAP_ENQ =1 , + __SCX_CAP_PREEMPT =2 , __SCX_NR_CAPS, __SCX_CAP_ALL =BIT_U64 (__SCX_NR_CAPS) -1 ,SCX_CAP_ENQ_IMMED =BIT_U64 (__SCX_CAP_ENQ_IMMED),SCX_CAP_ENQ =BIT_U64 (__SCX_CAP_ENQ), +SCX_CAP_PREEMPT =BIT_U64 (__SCX_CAP_PREEMPT),/* alias for minimal cap to make any use of a cpu */ SCX_CAP_BASE =SCX_CAP_ENQ_IMMED ,
@@ -1914,6 +1933,7 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd, struct scx_sched *parent);int scx_validate_ops (struct scx_sched *sch,const struct sched_ext_ops *ops);int scx_sched_sysfs_add (struct scx_sched *sch); +bool scx_is_descendant (struct scx_sched *sch,struct scx_sched *ancestor);extern raw_spinlock_t scx_sched_lock;extern struct mutex scx_enable_mutex;
kernel/sched/ext/sub.c +15 -4
@@ -221,11 +221,14 @@ void scx_init_root_caps(struct scx_sched *sch)* @sch: enqueuing sub-sched * @rq: rq whose local DSQ @p targets * @p: task being inserted -* @enq_flags: in/out; %SCX_ENQ_IMMED is cleared when diverting to reject +* @enq_flags: in/out, unhonored flags are cleared * * Return @rq's local DSQ if @sch holds the required caps on @rq's cid, * otherwise @rq's reject DSQ after recording the reenq reason on @p. * +* %SCX_ENQ_IMMED and %SCX_ENQ_PREEMPT are cleared when diverting to reject. +* %SCX_ENQ_PREEMPT is also cleared on a fallback migration-disabled admission. +* * Bypass doesn't need special-casing as a bypassing sched's tasks are enqueued * to and run by its nearest non-bypassing ancestor. If root is bypassing, it * always holds all caps.
@@ -234,7 +237,12 @@ struct scx_dispatch_q *scx_local_or_reject_dsq(struct scx_sched *sch, struct rq struct task_struct *p, u64 *enq_flags) { s32 cid = __scx_cpu_to_cid(cpu_of(rq)); -u64 missing =scx_missing_caps (sch,cpu_of (rq),scx_caps_for_enq (*enq_flags)); +u64 needed =scx_caps_for_enq (*enq_flags); +u64 missing; + +if (*enq_flags &SCX_ENQ_PREEMPT ) + needed |=scx_caps_for_preempt (sch, rq); + missing =scx_missing_caps (sch,cpu_of (rq), needed);/* requirements met */ if (likely (!missing))
@@ -244,10 +252,12 @@ struct scx_dispatch_q *scx_local_or_reject_dsq(struct scx_sched *sch, struct rq* The task must run on this CPU regardless of caps: the rq is draining * offline (BPF scheduler bypassed), the task is migration-disabled, or a * migration is pending. Admit despite the missing caps and count it. +* Refuse preemptions. */ if (unlikely (!scx_rq_online (rq) ||is_migration_disabled (p) || p->migration_pending)) {__scx_add_event (sch,SCX_EV_SUB_FORCED_ADMIT ,1 ); + *enq_flags &= ~SCX_ENQ_PREEMPT ;return &rq->scx.local_dsq; }
@@ -257,9 +267,10 @@ struct scx_dispatch_q *scx_local_or_reject_dsq(struct scx_sched *sch, struct rq/* * Only local DSQ can honor IMMED and dsq_inc_nr() WARNs on IMMED into * others. Strip both the enq flag and the sticky task flag - the -* latter can carry in from an earlier admitted IMMED insert. +* latter can carry in from an earlier admitted IMMED insert. Strip +* PREEMPT too. */ - *enq_flags &= ~SCX_ENQ_IMMED ; + *enq_flags &= ~(SCX_ENQ_IMMED |SCX_ENQ_PREEMPT ); p->scx.flags &= ~SCX_TASK_IMMED ;return &rq->scx.reject_dsq;
kernel/sched/ext/sub.h +15 -0
@@ -122,10 +122,24 @@ static inline u64 scx_caps_for_task(struct task_struct *p)return SCX_CAP_ENQ ; } +/* the cap @sch needs to preempt @rq's current task, 0 if none */ +static inline u64 scx_caps_for_preempt (struct scx_sched *sch,struct rq *rq) +{ +struct task_struct *curr = rq->curr; + +/* a non-ext task can't be preempted by ext, own-subtree needs no cap */ +if (curr->sched_class != &ext_sched_class || +scx_is_descendant (scx_task_sched (curr), sch)) +return 0 ; +return SCX_CAP_PREEMPT ; +} +/* caps implied by holding @cap */ static inline u64 scx_caps_implied (u64 cap) {switch (cap) { +case SCX_CAP_PREEMPT : +return SCX_CAP_ENQ |SCX_CAP_ENQ_IMMED ;case SCX_CAP_ENQ :return SCX_CAP_ENQ_IMMED ; }
@@ -145,6 +159,7 @@ static inline bool scx_task_can_stay_on_cpu(struct rq *rq, struct task_struct *p#else /* CONFIG_EXT_SUB_SCHED */ static inline u64 scx_missing_caps (struct scx_sched *sch,s32 cpu,u64 needed) {return 0 ; } +static inline u64 scx_caps_for_preempt (struct scx_sched *sch,struct rq *rq) {return 0 ; }static inline bool scx_task_can_stay_on_cpu (struct rq *rq,struct task_struct *p) {return true; }#endif /* CONFIG_EXT_SUB_SCHED */
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 27/33 sched_ext: Authorize remote-move inserts against the placing scheduler
In reply to Tejun Heoscx_local_or_reject_dsq() authorizes a local-DSQ insert against the caps of the scheduler doing the insert. On the consume/dispatch paths that is the scheduler running balance_one(), passed down through scx_consume_dispatch_q() and move_local_task_to_local_dsq(), so the check is correct.
The remote-move path loses it. move_remote_task_to_local_dsq() re-activates @p on the destination rq through enqueue_task_scx(), which reconstructs the scheduler from the task, i.e. @p's owner. When an ancestor places a descendant's task - e.g. draining a bypassed sub-scheduler - the owner is a sub-scheduler of the placer, so authorizing against the owner checks a narrower cap set and can spuriously reject a task the placer is entitled to run.
Carry the placing scheduler across the activate_task() boundary the same way enq_flags already are, via a per-rq field set only for the duration of the re-activation, and have scx_local_or_reject_dsq() authorize against it. The placer's caps are a superset of the owner's, so this admits what the placer may run and keeps rejecting what it may not.
v2: Document @sch in move_remote_task_to_local_dsq()'s kerneldoc. (Andrea)
--- kernel/sched/ext/ext.c | 28 ++++++++++++++++------------ kernel/sched/ext/sub.c | 9 +++++++-- kernel/sched/sched.h | 3 ++- 3 files changed, 25 insertions(+), 15 deletions(-)
kernel/sched/ext/ext.c +16 -12
@@ -2268,6 +2268,7 @@ static void move_local_task_to_local_dsq(struct scx_sched *sch,/** * move_remote_task_to_local_dsq - Move a task from a foreign rq to a local DSQ +* @sch: scheduler placing @p * @p: task to move * @enq_flags: %SCX_ENQ_* * @src_rq: rq to move the task from, locked on entry, released on return
@@ -2275,7 +2276,8 @@ static void move_local_task_to_local_dsq(struct scx_sched *sch,* * Move @p which is currently on @src_rq to @dst_rq's local DSQ. */ -static void move_remote_task_to_local_dsq (struct task_struct *p,u64 enq_flags, +static void move_remote_task_to_local_dsq (struct scx_sched *sch, +struct task_struct *p,u64 enq_flags,struct rq *src_rq,struct rq *dst_rq) {lockdep_assert_rq_held (src_rq);
@@ -2291,15 +2293,19 @@ static void move_remote_task_to_local_dsq(struct task_struct *p, u64 enq_flags,switch_rq_lock (src_rq, dst_rq);/* -* We want to pass scx-specific enq_flags but activate_task() will -* truncate the upper 32 bit. As we own @rq, we can pass them through -* @rq->scx.remote_activate_enq_flags instead. +* activate_task() below truncates enq_flags to 32 bits and re-derives +* @p's owner, dropping our scx flags and the placing @sch. We own @rq, +* so stash both across the call. The enqueue reads them back, keeping +* the scx flags and checking caps against the placer, not the owner. */ WARN_ON_ONCE (!cpumask_test_cpu (cpu_of (dst_rq), p->cpus_ptr)); -WARN_ON_ONCE (dst_rq->scx.remote_activate_enq_flags); +WARN_ON_ONCE (dst_rq->scx.remote_activate_enq_flags || + dst_rq->scx.remote_activate_sch); dst_rq->scx.remote_activate_enq_flags = enq_flags; + dst_rq->scx.remote_activate_sch = sch;activate_task (dst_rq, p,0 ); dst_rq->scx.remote_activate_enq_flags =0 ; + dst_rq->scx.remote_activate_sch =NULL ; }/*
@@ -2431,12 +2437,12 @@ static bool unlink_dsq_and_switch_rq_lock(struct task_struct *p, !WARN_ON_ONCE (src_rq !=task_rq (p)); } -static bool consume_remote_task (struct rq *this_rq, +static bool consume_remote_task (struct scx_sched *sch,struct rq *this_rq,struct task_struct *p,u64 enq_flags,struct scx_dispatch_q *dsq,struct rq *src_rq) {if (unlink_dsq_and_switch_rq_lock (p, dsq, this_rq, src_rq)) { -move_remote_task_to_local_dsq (p, enq_flags, src_rq, this_rq); +move_remote_task_to_local_dsq (sch, p, enq_flags, src_rq, this_rq);return true; }else {switch_rq_lock (src_rq, this_rq);
@@ -2497,8 +2503,7 @@ static struct rq *move_task_between_dsqs(struct scx_sched *sch,raw_spin_unlock (&src_dsq->lock); }else {raw_spin_unlock (&src_dsq->lock); -move_remote_task_to_local_dsq (p, enq_flags, - src_rq, dst_rq); +move_remote_task_to_local_dsq (sch, p, enq_flags, src_rq, dst_rq); } }else {/*
@@ -2551,7 +2556,7 @@ bool scx_consume_dispatch_q(struct scx_sched *sch, struct rq *rq, }if (task_can_run_on_remote_rq (sch, p, rq, false)) { -if (likely (consume_remote_task (rq, p, enq_flags, dsq, task_rq))) +if (likely (consume_remote_task (sch, rq, p, enq_flags, dsq, task_rq)))return true; goto retry; }
@@ -2644,8 +2649,7 @@ static void dispatch_to_local_dsq(struct scx_sched *sch, struct rq *rq,scx_dispatch_enqueue (sch, src_rq,find_global_dsq (sch,task_cpu (p)), p, enq_flags |SCX_ENQ_GDSQ_FALLBACK ); }else { -move_remote_task_to_local_dsq (p, enq_flags, - src_rq, dst_rq); +move_remote_task_to_local_dsq (sch, p, enq_flags, src_rq, dst_rq);/* task has been moved to dst_rq, which is now locked */ locked_rq = dst_rq; }
kernel/sched/ext/sub.c +7 -2
@@ -237,12 +237,17 @@ struct scx_dispatch_q *scx_local_or_reject_dsq(struct scx_sched *sch, struct rq struct task_struct *p, u64 *enq_flags) { s32 cid = __scx_cpu_to_cid(cpu_of(rq)); +struct scx_sched *asch = rq->scx.remote_activate_sch ?: sch;u64 needed =scx_caps_for_enq (*enq_flags);u64 missing; +/* +* On a remote activation the scheduling sched (@asch) differs from +* @p's owner (@sch). Check caps against the scheduling sched. +*/ if (*enq_flags &SCX_ENQ_PREEMPT ) - needed |=scx_caps_for_preempt (sch, rq); - missing =scx_missing_caps (sch,cpu_of (rq), needed); + needed |=scx_caps_for_preempt (asch, rq); + missing =scx_missing_caps (asch,cpu_of (rq), needed);/* requirements met */ if (likely (!missing))
kernel/sched/sched.h +2 -1
@@ -800,8 +800,9 @@ struct scx_rq {struct list_head runnable_list;/* runnable tasks on this rq */ struct list_head ddsp_deferred_locals;/* deferred ddsps from enq */ unsigned long ops_qseq; -/* see move_remote_task_to_local_dsq() */ +/* both stashed across the activate_task() in move_remote_task_to_local_dsq() */ u64 remote_activate_enq_flags; +struct scx_sched *remote_activate_sch;u32 nr_running;u32 cpuperf_target;/* [0, SCHED_CAPACITY_SCALE] */ bool in_select_cpu;
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 28/33 sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds
In reply to Tejun Heo__scx_update_idle() notified only the root scheduler. A sub-scheduler that holds a cid needs that cid's idle state to place and kick on it.
Deliver ops.update_idle() to every scheduler that holds SCX_CAP_BASE on the transitioning cid. The root holds every cap, so a real transition always reaches it.
Real transitions are not enough on their own. A cid that is already idle when a sub-sched gains baseline access produces no transition, so the new holder would never learn it is idle. The ecaps sync arms a re-notify on the gain, and the next idle pick delivers ops.update_idle() to just that sched, leaving holders that already track the cpu untouched. A matching loss of baseline access drops any pending re-notify.
Bypass suppresses ops.update_idle() too, so a cpu that goes idle during a bypass window and stays idle yields no transition to re-deliver on un-bypass. Arm the same re-notify for every sched leaving bypass. The acute case is a child granted cids during its own ops.sub_attach(). The grant lands while the child is bypassed and the notify walk skips it, so on un-bypass it holds cids it never saw go idle. The root is owed the same and is armed through a separate per-rq flag, which keeps this working when sub-schedulers are compiled out.
v2: Gate the idle catch-up in pick_task_idle() to avoid a double ops.update_idle(). (sashiko AI)
--- kernel/sched/ext/ext.c | 40 ++++++++++++++++- kernel/sched/ext/idle.c | 86 ++++++++++++++++++++++++++----------- kernel/sched/ext/internal.h | 2 + kernel/sched/ext/sub.c | 24 ++++++++++- kernel/sched/idle.c | 8 +++- kernel/sched/sched.h | 2 + 6 files changed, 133 insertions(+), 29 deletions(-)
kernel/sched/ext/ext.c +38 -2
@@ -5541,6 +5541,38 @@ void scx_disable_bypass_dsp(struct scx_sched *sch) } } +/** +* unbypass_renotify_idle - Arm an idle re-notify for a sched leaving bypass +* @rq: rq of the cpu leaving bypass +* @pos: scheduler that just left bypass on @rq's cpu +* @pcpu: @pos's per-cpu state for @rq's cpu +* +* A sched leaving bypass is owed the ops.update_idle() calls suppressed while +* bypassing. A cpu that goes idle during the bypass window and stays idle won't +* produce a notification. Arm a re-notify that scx_bypass()'s resched flushes +* on the next idle pick. +* +* An acute case is ops.sub_attach(). If the parent grants the child cids while +* attaching, when attach is complete and bypass is lifted, the child may hold +* idle cids it never saw go idle. +* +* The root is no exception as bypass suppresses its notifications the same way. +* However, the root uses a separate per-rq flag so its re-notify keeps working +* even when !CONFIG_EXT_SUB_SCHED. +*/ +static void unbypass_renotify_idle (struct rq *rq,struct scx_sched *pos, +struct scx_sched_pcpu *pcpu) +{ +if (pos == scx_root) { + rq->scx.flags |=SCX_RQ_ROOT_IDLE_RENOTIFY ; +return ; + } +#ifdef CONFIG_EXT_SUB_SCHED + pcpu->idle_renotify = true; + rq->scx.flags |=SCX_RQ_SUB_IDLE_RENOTIFY ; +#endif +} +/** * scx_bypass - [Un]bypass scx_ops and guarantee forward progress * @sch: sched to bypass
@@ -5624,11 +5656,15 @@ void scx_bypass(struct scx_sched *sch, bool bypass)scx_for_each_descendant_pre (pos, sch) {struct scx_sched_pcpu *pcpu =per_cpu_ptr (pos->pcpu, cpu); +bool was_bypassing = pcpu->flags &SCX_SCHED_PCPU_BYPASSING ; -if (pos->bypass_depth) +if (pos->bypass_depth) { pcpu->flags |=SCX_SCHED_PCPU_BYPASSING ; -else + }else { pcpu->flags &= ~SCX_SCHED_PCPU_BYPASSING ; +if (was_bypassing) +unbypass_renotify_idle (rq, pos, pcpu); + } }raw_spin_unlock (&scx_sched_lock);
kernel/sched/ext/idle.c +61 -25
117 lines not on this page · raw message
kernel/sched/ext/internal.h +2 -0
@@ -1244,6 +1244,8 @@ struct scx_sched_pcpu {*/ u64 ecaps;struct llist_node ecaps_to_sync_node; +/* owed a forced update_idle() re-notify on this cpu */ +bool idle_renotify;/* effective caps as of the last sub_ecaps_updated() delivery */ u64 reported_ecaps;#endif
kernel/sched/ext/sub.c +23 -1
@@ -483,6 +483,10 @@ static void discard_queued_syncs(struct rq *rq)* pshard->caps[] is the target configuration. pcpu->ecaps is the effective * transposed copy owned by the cid's cpu and written only here under @rq's * lock. +* +* A sched that newly gains baseline access here is owed an update_idle() so it +* learns the cid's idle state. Such a gain arms the per-rq +* %SCX_RQ_SUB_IDLE_RENOTIFY gate so the next idle pick delivers it. */ void scx_process_sync_ecaps (struct rq *rq,struct task_struct *prev) {
@@ -518,7 +522,7 @@ void scx_process_sync_ecaps(struct rq *rq, struct task_struct *prev)struct scx_sched_pcpu *pcpu = container_of(pos, struct scx_sched_pcpu, ecaps_to_sync_node);struct scx_pshard *ps = pcpu->sch->pshard[shard]; -u64 old, ecaps, lost; +u64 old, ecaps, lost, gained;init_llist_node (pos);
@@ -530,6 +534,7 @@ void scx_process_sync_ecaps(struct rq *rq, struct task_struct *prev)WRITE_ONCE (pcpu->ecaps, ecaps); lost = old & ~ecaps; + gained = ecaps & ~old; lost_all |= lost;/* tell the sched its effective caps on this cid changed */
@@ -547,6 +552,18 @@ void scx_process_sync_ecaps(struct rq *rq, struct task_struct *prev)scx_flush_dispatch_buf (pcpu->sch, rq); pcpu->reported_ecaps = ecaps; } + +/* +* Gaining baseline access owes an update_idle() so the sched +* learns the cpu's idle state. Arm the per-rq gate so the next +* idle pick flushes it. Losing access drops any pending notify. +*/ +if (gained &SCX_CAP_BASE ) { + pcpu->idle_renotify = true; + rq->scx.flags |=SCX_RQ_SUB_IDLE_RENOTIFY ; + }else if (lost &SCX_CAP_BASE ) { + pcpu->idle_renotify = false; + } }/*
@@ -1441,6 +1458,11 @@ __bpf_kfunc s32 scx_bpf_sub_grant(u64 cgroup_id, u64 caps,caps_updated_record (cps, changed_cids, granted_caps, &to_deliver); +/* +* The sync arms an update_idle() re-notify if +* the cid gains baseline access, so the holder +* learns of an already-idle cid. +*/ scx_cmask_for_each_cid (cid, changed_cids)queue_sync_ecaps (child, cid); }
kernel/sched/idle.c +7 -1
@@ -503,7 +503,13 @@ static void set_next_task_idle(struct rq *rq, struct task_struct *next, bool firstruct task_struct *pick_task_idle (struct rq *rq,struct rq_flags *rf) { -scx_update_idle (rq, true, false); +/* +* Notify scx only on an idle-to-idle re-pick (the cpu was already idle). +* A real task->idle transition is delivered by set_next_task_idle(), so +* calling here too would duplicate it. +*/ +if (scx_enabled () &&is_idle_task (rq->curr)) +scx_update_idle (rq, true, false);return rq->idle; }
kernel/sched/sched.h +2 -0
@@ -787,6 +787,8 @@ enum scx_rq_flags {SCX_RQ_BAL_KEEP =1 <<3 ,/* balance decided to keep current */ SCX_RQ_CLK_VALID =1 <<5 ,/* RQ clock is fresh and valid */ SCX_RQ_BAL_CB_PENDING =1 <<6 ,/* must queue a cb after dispatching */ +SCX_RQ_SUB_IDLE_RENOTIFY =1 <<7 ,/* sub-scheds are owed update_idle() */ +SCX_RQ_ROOT_IDLE_RENOTIFY =1 <<8 ,/* the root is owed update_idle() */ SCX_RQ_IN_WAKEUP =1 <<16 , SCX_RQ_IN_BALANCE = 1 << 17,
Signature · 1 line
2.55.0
Andrea Righi
reviewerRe: [PATCH v5 sched_ext/for-7.3 28/33] sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds
Hi Tejun,
Quoted 27 lines · Tejun Heo
__scx_update_idle()notified only the root scheduler. A sub-scheduler that holds a cid needs that cid's idle state to place and kick on it.Deliver
ops.update_idle()to every scheduler that holdsSCX_CAP_BASEon the transitioning cid. The root holds every cap, so a real transition always reaches it.Real transitions are not enough on their own. A cid that is already idle when a sub-sched gains baseline access produces no transition, so the new holder would never learn it is idle. The ecaps sync arms a re-notify on the gain, and the next idle pick delivers
ops.update_idle()to just that sched, leaving holders that already track the cpu untouched. A matching loss of baseline access drops any pending re-notify.Bypass suppresses
ops.update_idle()too, so a cpu that goes idle during a bypass window and stays idle yields no transition to re-deliver on un-bypass. Arm the same re-notify for every sched leaving bypass. The acute case is a child granted cids during its ownops.sub_attach(). The grant lands while the child is bypassed and the notify walk skips it, so on un-bypass it holds cids it never saw go idle. The root is owed the same and is armed through a separate per-rq flag, which keeps this working when sub-schedulers are compiled out.v2: Gate the idle catch-up in
pick_task_idle()to avoid a doubleops.update_idle(). (sashiko AI)Signed-off-by Tejun Heo <[email protected]>---
...
Quoted 29 lines
kernel/sched/ext/idle.c +29
-0+/* +* Notify schedulers of an idle transition on @cpu's cid, delivering to every +* sched that holds %SCX_CAP_BASE on the cid (the root holds every cap). A real +* transition (@do_notify) reaches all holders. A forced one (@root_renotify for +* the root, a sub-sched's idle_renotify marker for a sub) reaches only the owed +* scheds. +*/ +static void scx_idle_notify (struct rq *rq,bool idle,bool do_notify,bool root_renotify) +{ +s32 cpu =cpu_of (rq); +s32 cid =scx_cpu_arg (cpu); +struct scx_sched *pos; + +lockdep_assert_rq_held (rq); + + pos =scx_next_descendant_pre (NULL , scx_root); +while (pos) { +bool forced = false; + +if (unlikely (scx_missing_caps (pos, cpu,SCX_CAP_BASE ))) { + pos =scx_skip_subtree_pre (pos, scx_root); +continue ; + } + +if (pos == scx_root) { + forced = root_renotify; + } +#ifdef CONFIG_EXT_SUB_SCHED + else if (per_cpu_ptr(pos->pcpu, cpu)->idle_renotify) {
kernel/sched/ext/idle.c static void update_builtin_idle(int cpu, bool idle) · line 772
Quoted 10 lines
kernel/sched/ext/idle.c +10
-0+per_cpu_ptr (pos->pcpu, cpu)->idle_renotify = false; + forced = true; + } +#endif +if ((do_notify || forced) &&SCX_HAS_OP (pos, update_idle) && + !scx_bypassing (pos, cpu)) +SCX_CALL_OP (pos, update_idle, rq, cid, idle); + pos =scx_next_descendant_pre (pos, scx_root); + } +}
So, this makes every real idle/busy transition walk the whole scheduler hierarchy and potentially invoke ops.update_idle() for every cap-holding scheduler while the rq lock is held and IRQs are disabled?
This becomes O(number of cap-holding schedulers) BPF callbacks per idle transition.
I haven't benchmarked this, so I'm not sure if it's a valid performance concern. We don't have to fix this now, it can be a future improvement. In that case, if we prove that we have a real bottleneck here, would it make sense to maintain a per-rq list of schedulers that both hold effective SCX_CAP_BASE and implement ops.update_idle()?
Also, for the root-only case, would it be worth keeping the old direct ops.update_idle() path behind a static key which is enabled while any sub-scheduler is attached?
Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH v5 sched_ext/for-7.3 28/33] sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds
Hello, Andrea.
Quoted 4 lines · Andrea Righi
So, this makes every real idle/busy transition walk the whole scheduler hierarchy and potentially invoke
ops.update_idle()for every cap-holding scheduler while the rq lock is held and IRQs are disabled?
Quoted 8 lines
This becomes O(number of cap-holding schedulers) BPF callbacks per idle transition.
I haven't benchmarked this, so I'm not sure if it's a valid performance concern. We don't have to fix this now, it can be a future improvement. In that case, if we prove that we have a real bottleneck here, would it make sense to maintain a per-rq list of schedulers that both hold effective
SCX_CAP_BASEand implementops.update_idle()?
If this becomes an actual problem, we can add an opt-out for update_idle notifications and maintain the list of scheds that are subscribing. With shallow nesting and most cpus granted exclusively, which are the expected initial use cases, I don't expect this to be a problem in practice. We'll see.
Quoted 3 lines
Also, for the root-only case, would it be worth keeping the old direct
ops.update_idle()path behind a static key which is enabled while any sub-scheduler is attached?
Yeah, will gate this and the other sub-sched hot paths behind a static key in follow-up patches.
Thanks.
--
tejun
Tejun Heo
reviewerPATCH v5 29/33 sched_ext: Replay ecaps notifications suppressed by bypass
In reply to Tejun Heoscx_process_sync_ecaps() consumes ecaps syncs while the sched is bypassing without delivering ops.sub_ecaps_updated(), leaving reported_ecaps stale. Nothing re-queued a sync when bypass lifted, so a cid whose caps never change again would never be notified. Attach-time initial grants hit this every time: they are consumed during the enable bypass window, so a sched never learned its initial effective caps through the callback.
Re-queue a sync for every (sched, cpu) with an undelivered delta at the per-cpu bypass exit in scx_bypass(), next to the idle renotify catch-up. The next balance on the cpu then delivers the pending delta with proper dispatch context.
--- kernel/sched/ext/ext.c | 4 +++- kernel/sched/ext/sub.c | 35 +++++++++++++++++++++++++++++++++++ kernel/sched/ext/sub.h | 2 ++ 3 files changed, 40 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +3 -1
@@ -5662,8 +5662,10 @@ void scx_bypass(struct scx_sched *sch, bool bypass) pcpu->flags |=SCX_SCHED_PCPU_BYPASSING ; }else { pcpu->flags &= ~SCX_SCHED_PCPU_BYPASSING ; -if (was_bypassing) +if (was_bypassing) {unbypass_renotify_idle (rq, pos, pcpu); +scx_unbypass_replay_ecaps (rq, pos); + } } }
kernel/sched/ext/sub.c +35 -0
@@ -575,6 +575,41 @@ void scx_process_sync_ecaps(struct rq *rq, struct task_struct *prev)scx_schedule_reenq_local (rq,SCX_REENQ_CAP_REVOKE ); } +/** +* scx_unbypass_replay_ecaps - Replay a bypass-suppressed ecaps notification +* @rq: rq of the cpu leaving bypass +* @sch: scheduler that just left bypass on @rq's cpu +* +* scx_process_sync_ecaps() consumes syncs while bypassing without delivering +* ops.sub_ecaps_updated(), leaving reported_ecaps stale. Nothing re-queues a +* sync when bypass lifts, so without a replay a cid that never changes again +* would never be notified. The attach-time initial grants are the acute case +* as they are consumed during the enable bypass window. Re-queue a sync for +* any undelivered delta so the next balance delivers it. +*/ +void scx_unbypass_replay_ecaps (struct rq *rq,struct scx_sched *sch) +{ +s32 cpu =cpu_of (rq); +struct scx_sched_pcpu *pcpu =per_cpu_ptr (sch->pcpu, cpu); +struct scx_pshard *ps; +s32 cid; + +lockdep_assert_rq_held (rq); + +/* root holds every cap and never uses ecaps */ +if (!sch->level) +return ; + +if (READ_ONCE (pcpu->ecaps) == pcpu->reported_ecaps) +return ; + + cid =__scx_cpu_to_cid (cpu); + ps = sch->pshard[scx_cid_to_shard[cid]]; + +guard (raw_spinlock)(&ps->lock); +queue_sync_ecaps (sch, cid); +} +/* * A cpu came back. Re-seed each sub-sched's ecaps on the cpu's cid. The sync * recomputes effective caps from the pshard and fires ops.sub_ecaps_updated()
kernel/sched/ext/sub.h +2 -0
@@ -30,6 +30,7 @@ void scx_free_pshards(struct scx_sched *sch);s32 scx_alloc_pshards (struct scx_sched *sch);void scx_init_root_caps (struct scx_sched *sch);void scx_process_sync_ecaps (struct rq *rq,struct task_struct *prev); +void scx_unbypass_replay_ecaps (struct rq *rq,struct scx_sched *sch);void scx_online_ecaps (struct rq *rq);void scx_offline_ecaps (struct rq *rq);void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu);
@@ -52,6 +53,7 @@ static inline void scx_free_pshards(struct scx_sched *sch) {}static inline s32 scx_alloc_pshards (struct scx_sched *sch) {return 0 ; }static inline void scx_init_root_caps (struct scx_sched *sch) {}static inline void scx_process_sync_ecaps (struct rq *rq,struct task_struct *prev) {} +static inline void scx_unbypass_replay_ecaps (struct rq *rq,struct scx_sched *sch) {}static inline void scx_online_ecaps (struct rq *rq) {}static inline void scx_offline_ecaps (struct rq *rq) {}static inline void scx_discard_ecaps_to_sync (s32 cpu,struct scx_sched_pcpu *pcpu) {}
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 30/33 sched_ext: Add scx_bpf_sub_kill() to evict a child sub-scheduler
In reply to Tejun HeoA cid-form scheduler can grant caps to and revoke them from its child sub-schedulers but has no way to tear one down. Add scx_bpf_sub_kill() to evict a direct child with a printf-style reason that reaches the child's scx_exit_info. No exit code is taken because the child is a separate scheduler whose exit-code semantics the parent cannot know. The child and its subtree are disabled through the usual async path under a new exit kind, SCX_EXIT_PARENT_KILL.
The bstr formatting infrastructure in ext.c is exposed through internal.h with scx_ prefixes so the kfunc, which lives in sub.c, can format the reason.
--- kernel/sched/ext/ext.c | 28 +++++++----- kernel/sched/ext/internal.h | 11 +++++ kernel/sched/ext/sub.c | 57 ++++++++++++++++++++++++ tools/sched_ext/include/scx/common.bpf.h | 18 ++++++++ 4 files changed, 102 insertions(+), 12 deletions(-)
kernel/sched/ext/ext.c +16 -12
@@ -187,14 +187,8 @@ static const struct rhashtable_params dsq_hash_params = {static LLIST_HEAD (dsqs_to_free); -/* string formatting from BPF */ -struct scx_bstr_buf { -u64 data[MAX_BPRINTF_VARARGS ]; -char line[SCX_EXIT_MSG_LEN ]; -}; - -static DEFINE_RAW_SPINLOCK (scx_exit_bstr_buf_lock); -static struct scx_bstr_buf scx_exit_bstr_buf; +DEFINE_RAW_SPINLOCK (scx_exit_bstr_buf_lock); +struct scx_bstr_buf scx_exit_bstr_buf;/* ops debug dump */ static DEFINE_RAW_SPINLOCK (scx_dump_lock);
@@ -5755,6 +5749,8 @@ static const char *scx_exit_reason(enum scx_exit_kind kind)return "disabled by sysrq-S" ;case SCX_EXIT_PARENT :return "parent exiting" ; +case SCX_EXIT_PARENT_KILL : +return "killed by parent scheduler" ;case SCX_EXIT_ERROR :return "runtime error" ;case SCX_EXIT_ERROR_BPF :
@@ -9368,8 +9364,8 @@ static s32 __bstr_format(struct scx_sched *sch, u64 *data_buf, char *line_buf, } __printf(3, 0) -static s32 bstr_format (struct scx_sched *sch,struct scx_bstr_buf *buf, -char *fmt,unsigned long long *data,u32 data__sz) +s32 scx_bstr_format (struct scx_sched *sch,struct scx_bstr_buf *buf, +char *fmt,unsigned long long *data,u32 data__sz) {return __bstr_format (sch, buf->data, buf->line,sizeof (buf->line), fmt, data, data__sz);
@@ -9399,7 +9395,7 @@ __bpf_kfunc void scx_bpf_exit_bstr(s64 exit_code, char *fmt,raw_spin_lock_irqsave (&scx_exit_bstr_buf_lock, flags); sch =scx_prog_sched (aux);if (likely (sch) && -bstr_format (sch, &scx_exit_bstr_buf, fmt, data, data__sz) >=0 ) +scx_bstr_format (sch, &scx_exit_bstr_buf, fmt, data, data__sz) >=0 )scx_exit (sch,SCX_EXIT_UNREG_BPF , exit_code,"%s" , scx_exit_bstr_buf.line);raw_spin_unlock_irqrestore (&scx_exit_bstr_buf_lock, flags); }
@@ -9424,7 +9420,7 @@ __bpf_kfunc void scx_bpf_error_bstr(char *fmt, unsigned long long *data,raw_spin_lock_irqsave (&scx_exit_bstr_buf_lock, flags); sch =scx_prog_sched (aux);if (likely (sch) && -bstr_format (sch, &scx_exit_bstr_buf, fmt, data, data__sz) >=0 ) +scx_bstr_format (sch, &scx_exit_bstr_buf, fmt, data, data__sz) >=0 )scx_exit (sch,SCX_EXIT_ERROR_BPF ,0 ,"%s" , scx_exit_bstr_buf.line);raw_spin_unlock_irqrestore (&scx_exit_bstr_buf_lock, flags); }
@@ -10060,6 +10056,13 @@ __bpf_kfunc s32 scx_bpf_sub_caps(u64 cgroup_id, u64 caps, struct scx_cmask *out_ {return -EOPNOTSUPP ; } + +__bpf_kfunc s32 scx_bpf_sub_kill_bstr(u64 cgroup_id, char *fmt, +unsigned long long *data,u32 data__sz, +const struct bpf_prog_aux *aux) +{ +return -EOPNOTSUPP ; +}#endif /* !CONFIG_EXT_SUB_SCHED */ __bpf_kfunc_end_defs ();
@@ -10109,6 +10112,7 @@ BTF_ID_FLAGS(func, scx_bpf_task_cgroup, KF_IMPLICIT_ARGS | KF_RCU | KF_ACQUIRE) BTF_ID_FLAGS(func, scx_bpf_sub_grant, KF_IMPLICIT_ARGS) BTF_ID_FLAGS(func, scx_bpf_sub_revoke, KF_IMPLICIT_ARGS) BTF_ID_FLAGS(func, scx_bpf_sub_caps, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_sub_kill_bstr, KF_IMPLICIT_ARGS)BTF_KFUNCS_END (scx_kfunc_ids_any) static const struct btf_kfunc_id_set scx_kfunc_set_any = {
kernel/sched/ext/internal.h +11 -0
@@ -51,6 +51,7 @@ enum scx_exit_kind {SCX_EXIT_UNREG_KERN ,/* kernel-initiated unregistration */ SCX_EXIT_SYSRQ ,/* requested by 'S' sysrq */ SCX_EXIT_PARENT ,/* parent exiting */ +SCX_EXIT_PARENT_KILL ,/* killed by parent scheduler */ SCX_EXIT_ERROR =1024 ,/* runtime error, error msg contains details */ SCX_EXIT_ERROR_BPF, /* ERROR but triggered through scx_bpf_error() */
@@ -1876,6 +1877,12 @@ struct scx_enable_cmd {int ret; }; +/* string formatting from BPF */ +struct scx_bstr_buf { +u64 data[MAX_BPRINTF_VARARGS ]; +char line[SCX_EXIT_MSG_LEN ]; +}; +extern struct scx_sched __rcu *scx_root; DECLARE_PER_CPU(struct rq *, scx_locked_rq_state);
@@ -1936,10 +1943,14 @@ struct scx_sched *scx_alloc_and_add_sched(struct scx_enable_cmd *cmd,int scx_validate_ops (struct scx_sched *sch,const struct sched_ext_ops *ops);int scx_sched_sysfs_add (struct scx_sched *sch);bool scx_is_descendant (struct scx_sched *sch,struct scx_sched *ancestor); +__printf(3, 0) s32 scx_bstr_format(struct scx_sched *sch, struct scx_bstr_buf *buf, +char *fmt,unsigned long long *data,u32 data__sz);extern raw_spinlock_t scx_sched_lock;extern struct mutex scx_enable_mutex;extern struct percpu_rw_semaphore scx_fork_rwsem; +extern raw_spinlock_t scx_exit_bstr_buf_lock; +extern struct scx_bstr_buf scx_exit_bstr_buf;#ifdef CONFIG_EXT_SUB_SCHED extern const struct rhashtable_params scx_sched_hash_params;extern struct rhashtable scx_sched_hash;
kernel/sched/ext/sub.c +57 -0
63 lines not on this page · raw message
tools/sched_ext/include/scx/common.bpf.h +18 -0
@@ -119,6 +119,8 @@ s32 scx_bpf_sub_grant(u64 cgroup_id, u64 caps, const struct scx_cmask *cmask, struct scx_cmask *denied) __ksym __weak; void scx_bpf_sub_revoke(u64 cgroup_id, u64 caps, const struct scx_cmask *cmask) __ksym __weak; s32 scx_bpf_sub_caps(u64 cgroup_id, u64 caps, struct scx_cmask *out) __ksym __weak; +s32 scx_bpf_sub_kill_bstr(u64 cgroup_id, char *fmt, + unsigned long long *data, u32 data__sz) __ksym __weak;/* * Use the following as @it__iter when calling scx_bpf_dsq_move[_vtime]() from
@@ -165,6 +167,22 @@ void ___scx_bpf_bstr_format_checker(const char *fmt, ...) {} ___scx_bpf_bstr_format_checker(fmt, ##args); \ }) +/* +* scx_bpf_sub_kill() wraps the scx_bpf_sub_kill_bstr() kfunc with variadic +* arguments instead of an array of u64. It kills the direct child sub-scheduler +* @cgid, passing the formatted reason to its user space, and evaluates to the +* kfunc's return value. On a kernel without sub-scheduler support the kfunc is +* absent and it returns -EOPNOTSUPP. +*/ +#define scx_bpf_sub_kill(cgid, fmt, args...) \ +({ \ + scx_bpf_bstr_preamble(fmt, args) \ + ___scx_bpf_bstr_format_checker(fmt, ##args); \ + bpf_ksym_exists(scx_bpf_sub_kill_bstr) ? \ + scx_bpf_sub_kill_bstr((cgid), ___fmt, ___param, \ + sizeof(___param)) : -EOPNOTSUPP; \ +}) +/* * scx_bpf_error() wraps the scx_bpf_error_bstr() kfunc with variadic arguments * instead of an array of u64. Invoking this macro will cause the scheduler to
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 31/33 tools/sched_ext: Add three-mask cmask intersection iterator
In reply to Tejun HeoAdd cmask_next_and2_set() and its round-robin wrap, extending cmask_next_and_set() to a three-mask intersection: the next cid set in all three masks at or after @start. A caller iterating the intersection of three cmasks can then scan it in one pass, folding the third mask into the word-level AND rather than skipping non-members one candidate at a time.
--- tools/sched_ext/include/scx/cid.bpf.h | 77 +++++++++++++++++++++++++++ 1 file changed, 77 insertions(+)
tools/sched_ext/include/scx/cid.bpf.h +77 -0
@@ -668,6 +668,83 @@ static __always_inline u32 cmask_next_and_set_wrap(const struct scx_cmask __arenreturn found < start ? found : a_end; } +/* +* Like cmask_next_and_set() but over the intersection of THREE masks. Return +* a->base + a->nr_cids if no cid is set in all three at or after @start. +*/ +static __always_inline u32 cmask_next_and2_set(const struct scx_cmask __arena *a, + const struct scx_cmask __arena *b, + const struct scx_cmask __arena *c, +u32 start) +{ +u32 a_end = a->base + a->nr_cids; +u32 b_end = b->base + b->nr_cids; +u32 c_end = c->base + c->nr_cids; +u32 a_wbase = a->base /64 ; +u32 b_wbase = b->base /64 ; +u32 c_wbase = c->base /64 ; +u32 lo = a->base > b->base ? a->base : b->base; +u32 hi = a_end < b_end ? a_end : b_end; +u32 last_wi, start_wi, start_bit, i; + + lo = lo > c->base ? lo : c->base; + hi = hi < c_end ? hi : c_end; + +if (lo >= hi) +return a_end; +if (start < lo) + start = lo; +if (start >= hi) +return a_end; + + last_wi = (hi -1 ) /64 ; + start_wi = start /64 ; + start_bit = start &63 ; + + bpf_for(i, 0, CMASK_MAX_WORDS) { +u32 abs_wi = start_wi + i; +u64 word; +u32 found; + +if (abs_wi > last_wi) +break ; + + word = a->bits[abs_wi - a_wbase] & b->bits[abs_wi - b_wbase] & + c->bits[abs_wi - c_wbase]; +if (i ==0 ) + word &=GENMASK_U64 (63 , start_bit); +if (!word) +continue ; + + found = abs_wi *64 +ctzll (word); +if (found >= hi) +return a_end; +return found; + } +return a_end; +} + +/* +* Round-robin variant of cmask_next_and2_set(): wrap to @a->base if the +* three-way intersection has no cid in the forward half. Return a->base + +* a->nr_cids if empty. +*/ +static __always_inline u32 cmask_next_and2_set_wrap(const struct scx_cmask __arena *a, + const struct scx_cmask __arena *b, + const struct scx_cmask __arena *c, +u32 start) +{ +u32 a_end = a->base + a->nr_cids; +u32 found; + + found =cmask_next_and2_set (a, b, c, start); +if (found < a_end || start <= a->base) +return found; + + found =cmask_next_and2_set (a, b, c, a->base); +return found < start ? found : a_end; +} +/** * cmask_from_cpumask - translate a kernel cpumask to a cid-space cmask * @m: cmask to fill. Zeroed first; only bits within [@m->base, @m->base +
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 32/33 tools/sched_ext: scx_qmap - Expand hierarchical sub-scheduling
In reply to Tejun Heosched_ext sub-scheduling began as dispatch delegation only: a parent could call into a child cgroup sub-scheduler's ops.dispatch() from its own dispatch path, but could not delegate cpus to the child for enqueue and the other paths. sched_ext has since gained cap-based cid delegation, where a parent grants and revokes a child's per-cid caps. Expand scx_qmap to demonstrate it.
scx_qmap can now delegate the cids it holds exclusively, split among itself and its children by cpu.weight. Each gets the floor of its share as dedicated cids. The leftover from rounding forms a shared pool, round-robined among them as an ENQ_IMMED time-share.
This shape is deliberate. Exclusive cids exercise the basic grant and revoke of ownership, and the shared pool exercises time-sharing one cid across several schedulers. The implemented policy is impractical, but it covers most of what a practical sub-scheduler would need without overcomplicating qmap.
Delegation nests. A cid a node receives from its parent only as a round-robin share stays self-local and is never re-delegated. A node left with no exclusive cid, e.g. after its cpus went offline, evicts its children.
v5: Highpri dispatch masked with self_cids, single-read dispatch cgroup_id, feed_weights race comment. (sashiko AI)
v4: Track all idle cids and mask with self_cids at the dispatch pick, dropping the reseed. (sashiko AI)
v3: Dispatch IMMED flags, repartition accounting order, partition-input snapshot. (sashiko AI)
v2: Use __sync_fetch_and_add() for the shared nr_dsps counter. (sashiko AI)
--- tools/sched_ext/scx_qmap.bpf.c | 758 ++++++++++++++++++++++++++++++--- tools/sched_ext/scx_qmap.c | 297 ++++++++++++- tools/sched_ext/scx_qmap.h | 98 ++++- 3 files changed, 1086 insertions(+), 67 deletions(-)
tools/sched_ext/scx_qmap.bpf.c +700 -58
@@ -1,21 +1,39 @@/* SPDX-License-Identifier: GPL-2.0 */ /* -* A simple five-level FIFO queue scheduler. +* scx_qmap: a demonstration and testing scheduler for sched_ext features. * -* There are five FIFOs implemented as arena-backed doubly-linked lists -* threaded through per-task context. A task gets assigned to one depending on -* its compound weight. Each CPU round robins through the FIFOs and dispatches -* more from FIFOs with higher indices - 1 from queue0, 2 from queue1, 4 from -* queue2 and so on. -* -* This scheduler demonstrates: +* A simple scheduler that exercises a broad set of sched_ext features. Unlikely +* to be useful for real workloads. It demonstrates: * * - BPF-side queueing using TIDs. * - BPF arena for scheduler state. * - Core-sched support. +* - Hierarchical sub-scheduling: delegating cpus to child cgroup schedulers. +* +* Base design: Five FIFOs (arena-backed doubly-linked lists through per-task +* context). A task is assigned to a FIFO by its compound weight. Each cpu +* round-robins the FIFOs, dispatching more from higher ones. +* +* Sub-scheduling: Any qmap sched can delegate cpus to its own child cgroup +* schedulers and keep the rest for its tasks. Terminology: +* +* excl - A cpu the delegatee owns wholly (ENQ_IMMED|ENQ|PREEMPT). +* shared - A cpu delegated as ENQ_IMMED only. Time-shared. +* held_excl / held_shared - What this node was handed by its parent. +* held-excl cpus are re-delegatable. A held-shared cpu is a +* time-share that stays self-local. +* self - The excl cpus the node kept for itself, plus all of held_shared. +* owner - Who holds a cid - a child slot, CID_SELF, or CID_NONE. * -* This scheduler is primarily for demonstration and testing of sched_ext -* features and unlikely to be useful for actual workloads. +* The scheduler splits its held-excl cpus among self and the children in +* proportion to each node's cpu.weight, handing each the floor of its share as +* excl cpus. The leftover from rounding forms a shared pool the round-robin +* timer hands around. With no excl cpu to delegate, the node evicts its +* children. +* +* This policy is a demonstration only, not a practical one. The split +* considers only direct children and is not work-conserving. It only exists to +* drive sub-sched primitives with as simple logic as possible. * * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <[email protected]>
@@ -52,6 +70,9 @@ const volatile bool always_enq_immed;const volatile u32 immed_stress_nth;const volatile u32 max_tasks; +/* sub-sched: period for handing the round-robin cid pool to the next child */ +const volatile u64 round_robin_ns; +/* * Optional cid-override test harness. When cid_override_mode is non-zero, * qmap_init_cids() calls scx_bpf_cid_override() with the caller-supplied arrays
@@ -89,12 +110,12 @@ struct { struct qmap_arena __arena_global qa; -/* -* Global idle-cid tracking, maintained via update_idle / cpu_offline and -* scanned by the direct-dispatch path. Allocated in qmap_init() from one -* arena page, sized to the full cid space. -*/ -struct scx_cmask __arena *qa_idle_cids; +/* ensure that BPF and userspace are seeing the same size for qmap_cmask */ +_Static_assert (QMAP_CMASK_WORDS ==CMASK_NR_WORDS (SCX_QMAP_MAX_CPUS ), +"QMAP_CMASK_WORDS must equal CMASK_NR_WORDS(SCX_QMAP_MAX_CPUS)" ); +_Static_assert (sizeof (struct qmap_cmask ) == + struct_size_t(struct scx_cmask, bits, QMAP_CMASK_WORDS), +"qmap_cmask must be exactly sized to back a full scx_cmask" );/* Per-queue locks. Each in its own .data section as bpf_res_spin_lock requires. */ __hidden struct bpf_res_spin_lock qa_q_lock0 SEC(".data.qa_q_lock0");
@@ -196,7 +217,7 @@ static int qmap_spin_lock(struct bpf_res_spin_lock *lock) }/* -* Try prev_cid, then scan taskc->cpus_allowed AND qa_idle_cids round-robin +* Try prev_cid, then scan cpus_allowed AND idle_cids AND self_cids round-robin * from prev_cid + 1. Atomic claim retries on race; bounded by * IDLE_PICK_RETRIES to keep the verifier's insn budget in check. */
@@ -212,17 +233,19 @@ static s32 pick_direct_dispatch_cid(struct task_struct *p, s32 prev_cid,if (!always_enq_immed && p->nr_cpus_allowed ==1 )return prev_cid; -if (cmask_test_and_clear (prev_cid, qa_idle_cids)) +if (cmask_test (prev_cid, &qa.self_cids.mask) && +cmask_test_and_clear (prev_cid, &qa.idle_cids.mask))return prev_cid; cid = prev_cid; bpf_for(i, 0, IDLE_PICK_RETRIES) { - cid =cmask_next_and_set_wrap (&taskc->cpus_allowed, - qa_idle_cids, cid +1 ); + cid =cmask_next_and2_set_wrap (&taskc->cpus_allowed, + &qa.idle_cids.mask, + &qa.self_cids.mask, cid +1 );barrier_var (cid);if (cid >= nr_cids)return -1 ; -if (cmask_test_and_clear (cid, qa_idle_cids)) +if (cmask_test_and_clear (cid, &qa.idle_cids.mask))return cid; }return -1 ;
@@ -346,6 +369,15 @@ s32 BPF_STRUCT_OPS(qmap_select_cid, struct task_struct *p, } } +/* +* A received time-shared cid is held ENQ_IMMED-only, so inserts must set +* SCX_ENQ_IMMED. +*/ +static u64 needs_immed (s32 cid) +{ +return qa.cid_shared[cid] ?SCX_ENQ_IMMED :0 ; +} +static int weight_to_idx (u32 weight) {/* Coarsely map the compound weight to a FIFO. */
@@ -369,9 +401,16 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)s32 cid;if (enq_flags &SCX_ENQ_REENQ ) { +u64 reason = p->scx.flags &SCX_TASK_REENQ_REASON_MASK ; +__sync_fetch_and_add (&qa.nr_reenqueued,1 );if (scx_bpf_task_cid (p) ==0 )__sync_fetch_and_add (&qa.nr_reenqueued_cid0,1 ); +/* cap-loss and IMMED-handback bounces, relocated below */ +if (reason ==SCX_TASK_REENQ_CAP ) +__sync_fetch_and_add (&qa.nr_reenq_cap,1 ); +else if (reason ==SCX_TASK_REENQ_IMMED ) +__sync_fetch_and_add (&qa.nr_reenq_immed,1 ); }if (p->flags &PF_KTHREAD ) {
@@ -394,6 +433,27 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)*/ taskc->core_sched_seq = qa.core_sched_tail_seqs[idx]++; +/* +* A node with children delegates most cids. A task of ours that can run +* on none of our self cids (e.g. a per-NUMA kthread pinned to delegated +* cids) would starve in SHARED/FIFO since we never pull those on a +* delegated cid. Force it onto its first allowed cid's local DSQ with +* needs_immed(): if we hold access there it runs, else the kernel +* rejects and bounces it back via REENQ_CAP. Best-effort +* anti-starvation nudge. +*/ +if (qa.nr_sub_scheds && !(enq_flags &SCX_ENQ_REENQ ) && + !cmask_intersects (&taskc->cpus_allowed, &qa.self_cids.mask)) { +s32 c =cmask_next_set_wrap (&taskc->cpus_allowed,0 ); + +if (c >=0 && c <scx_bpf_nr_cids ()) { + taskc->force_local = false; +scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL_ON | c, slice_ns, + enq_flags |needs_immed (c)); +return ; + } + } +/* * IMMED stress testing: Every immed_stress_nth'th enqueue, dispatch * directly to prev_cpu's local DSQ even when busy to force dsq->nr > 1
@@ -416,7 +476,8 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)*/ if (taskc->force_local) { taskc->force_local = false; -scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL , slice_ns, enq_flags); +scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL , slice_ns, + enq_flags |needs_immed (scx_bpf_task_cid (p)));return ; }
@@ -431,7 +492,8 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)if (!__COMPAT_is_enq_cpu_selected (enq_flags) && (cid =pick_direct_dispatch_cid (p,scx_bpf_task_cid (p), taskc)) >=0 ) {__sync_fetch_and_add (&qa.nr_ddsp_from_enq,1 ); -scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL_ON | cid, slice_ns, enq_flags); +scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL_ON | cid, slice_ns, + enq_flags |needs_immed (cid));return ; }
@@ -445,8 +507,9 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)s32 cid;scx_bpf_dsq_insert (p,SHARED_DSQ ,0 , enq_flags); - cid =cmask_next_and_set_wrap (&taskc->cpus_allowed, - qa_idle_cids,0 ); + cid =cmask_next_and2_set_wrap (&taskc->cpus_allowed, + &qa.idle_cids.mask, + &qa.self_cids.mask,0 );if (cid <scx_bpf_nr_cids ())scx_bpf_kick_cid (cid,SCX_KICK_IDLE );return ;
@@ -532,16 +595,19 @@ static bool dispatch_highpri(bool from_timer)if (!(taskc =lookup_task_ctx (p)))return false; -if (cmask_test (this_cid, &taskc->cpus_allowed)) +/* only run highpri tasks on cids this node holds, not delegated ones */ +if (cmask_test (this_cid, &taskc->cpus_allowed) && +cmask_test (this_cid, &qa.self_cids.mask)) cid = this_cid;else - cid =cmask_next_set_wrap (&taskc->cpus_allowed, - this_cid +1 ); + cid =cmask_next_and_set_wrap (&taskc->cpus_allowed, + &qa.self_cids.mask, + this_cid +1 );if (cid >= nr_cids)continue ;if (scx_bpf_dsq_move (BPF_FOR_EACH_ITER , p,SCX_DSQ_LOCAL_ON | cid, -SCX_ENQ_PREEMPT )) { +SCX_ENQ_PREEMPT |needs_immed (cid))) {if (cid == this_cid) { dispatched = true;__sync_fetch_and_add (&qa.nr_expedited_local,1 );
@@ -567,12 +633,38 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cid, struct task_struct *prev) struct cpu_ctx __arena *cpuc;task_ctx_t *taskc;u32 batch = dsp_batch ?:1 ; +s32 owner;s32 i;if (dispatch_highpri (false))return ; -if (!qa.nr_highpri_queued &&scx_bpf_dsq_move_to_local (SHARED_DSQ ,0 )) +/* +* Sub-sched routing: a child-owned cid goes to its owner. Never run +* this node's own tasks on a delegated cid. Read without the guard. +*/ + owner = qa.part.cid_owner[cid]; +if (owner ==CID_SHARED ) { +/* route to the live rr holder (0 = self, runs below) */ +s32 pos = qa.part.rr_pos; +u64 holder_cgid = (pos >=0 && pos <MAX_PARTS ) ? + qa.part.rr_slots[pos] :0 ; + +if (holder_cgid) { +scx_bpf_sub_dispatch (holder_cgid); +return ; + } + }else if (owner >=0 && owner <MAX_SUB_SCHEDS ) { +u64 cgid = qa.sub_sched_ctxs[owner].cgroup_id; + +if (cgid) { +if (scx_bpf_sub_dispatch (cgid)) +__sync_fetch_and_add (&qa.sub_sched_ctxs[owner].nr_dsps,1 ); +return ; + } + } + +if (!qa.nr_highpri_queued &&scx_bpf_dsq_move_to_local (SHARED_DSQ ,needs_immed (cid)))return ;if (dsp_inf_loop_after && qa.nr_dispatched > dsp_inf_loop_after) {
@@ -662,7 +754,7 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cid, struct task_struct *prev)if (!batch || !scx_bpf_dispatch_nr_slots ()) {if (dispatch_highpri (false))return ; -scx_bpf_dsq_move_to_local (SHARED_DSQ ,0 ); +scx_bpf_dsq_move_to_local (SHARED_DSQ ,needs_immed (cid));return ; }if (!cpuc->dsp_cnt)
@@ -672,12 +764,6 @@ void BPF_STRUCT_OPS(qmap_dispatch, s32 cid, struct task_struct *prev) cpuc->dsp_cnt =0 ; } -for (i =0 ; i <MAX_SUB_SCHEDS ; i++) { -if (qa.sub_sched_cgroup_ids[i] && -scx_bpf_sub_dispatch (qa.sub_sched_cgroup_ids[i])) -return ; - } -/* * No other tasks. @prev will keep running. Update its core_sched_seq as * if the task were enqueued and dispatched immediately.
@@ -910,10 +996,18 @@ void BPF_STRUCT_OPS(qmap_cgroup_set_bandwidth, struct cgroup *cgrp,void BPF_STRUCT_OPS (qmap_update_idle ,s32 cid,bool idle) {QMAP_TOUCH_ARENA (); + +/* +* The kernel delivers update_idle() for every cid this node holds +* SCX_CAP_BASE on. Track every cid's idle state regardless of +* delegation: the direct-dispatch pick masks idle_cids with self_cids +* at selection, so a cid already idle when it returns to self needs no +* reseed here. +*/ if (idle) -cmask_set (cid, qa_idle_cids); +cmask_set (cid, &qa.idle_cids.mask);else -cmask_clear (cid, qa_idle_cids); +cmask_clear (cid, &qa.idle_cids.mask); } void BPF_STRUCT_OPS(qmap_set_cmask, struct task_struct *p,
@@ -1065,6 +1159,486 @@ static int lowpri_timerfn(void *map, int *key, struct bpf_timer *timer)return 0 ; } +struct round_robin_timer { +struct bpf_timer timer; +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, u32); + __type(value, struct round_robin_timer); +} round_robin_timer SEC(".maps"); + +/* +* Partition update synchronization. qa.part can be written from concurrent +* contexts. This single-runner guard admits one writer at a time without +* holding a lock across the grant/revoke kfuncs. part_pending coalesces +* repartition requests that arrive while it is held. +* +* They live in .bss, not the arena: rr_advance() runs from a bpf_timer +* callback, where the verifier rejects atomic ops on arena memory. +*/ +static u64 part_busy; +static u64 part_pending; + +static bool part_try_start (void ) +{ +/* set busy, report whether it was previously clear (we acquired it) */ +return !__sync_fetch_and_or (&part_busy,1 ); +} + +static void part_end (void ) +{ +__sync_fetch_and_and (&part_busy,0 ); +} + +/* +* compute_partition() scratch. +* +* The excl-held cids are handed out in cid order: position 0..nr_excl-1 over +* the held cids is split into contiguous ranges, one per participant that gets +* at least one excl cid. Range k is owned by cp_range_owner[k] and ends at the +* cumulative position cp_range_end[k]. +*/ +static s32 cp_range_owner[MAX_PARTS ];/* exclusive range k: its owner id ... */ +static s32 cp_range_end[MAX_PARTS ];/* ... and the cumulative position it ends at */ + +/* a participant in the partition: self or an attached child */ +struct participant { +s32 slot;/* child slot, or CID_SELF */ +u32 weight;/* cpu.weight */ +}; + +/** +* place_one - assign one excl-held cid to its owner +* @cid: the excl-held cid to place +* @n: its position among the excl-held cids, in [0, nr_excl) +* @total_excl: how many positions are owned exclusively (the rest are shared) +* +* Position @n below @total_excl is owned exclusively. It falls in the range +* whose cumulative end it is under, owned by cp_range_owner[]. A position at or +* above @total_excl is the rounding leftover which joins the shared pool. +* +* A separate __noinline function to help verification. +*/ +__noinline int place_one(s32 cid, s32 n, s32 total_excl) +{ +s32 owner =CID_SELF , i, s; + +if (cid <0 || cid >=SCX_QMAP_MAX_CPUS || n <0 || n >=SCX_QMAP_MAX_CPUS || + total_excl <0 ) { +scx_bpf_error ("-ERANGE" ); +return 0 ; + } + +if (n < total_excl) { +for (i =0 ; i <MAX_PARTS ; i++) { +if (n < cp_range_end[i]) { + owner = cp_range_owner[i]; +break ; + } + } + qa.part.cid_owner[cid] = owner; + }else { + s = n - total_excl; +if (s <0 || s >=MAX_PARTS ) { +scx_bpf_error ("-ERANGE" ); +return 0 ; + } + qa.part.shared_cids[s] = cid; +/* time-shared: dispatch resolves the live holder via rr_pos */ + qa.part.cid_owner[cid] =CID_SHARED ; + } +return 0 ; +} + +/** +* compute_partition - build the cid partition from this node's held caps +* +* Decide each cid's owner, the shared pool and the rr rotation. __noinline to +* help verification. See the comment at the top of the file. +*/ +__noinline void compute_partition(void) +{ +s32 nr_cids = qa.nr_cids; +s32 nr_excl, total_excl =0 , nr_rr =0 ; +s32 sum_w, i, cid, n =0 , share, self_w; +u64 cgid_snap[MAX_SUB_SCHEDS ]; +s32 w_snap[MAX_SUB_SCHEDS ]; + +if (nr_cids >SCX_QMAP_MAX_CPUS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + +/* find out the cids we hold */ +scx_bpf_sub_caps (0 ,SCX_CAP_ENQ , (void *)(long )&qa.held_excl.mask); +scx_bpf_sub_caps (0 ,SCX_CAP_ENQ_IMMED , (void *)(long )&qa.held_shared.mask); +cmask_andnot (&qa.held_shared.mask, &qa.held_excl.mask);/* held only as ENQ_IMMED */ + + qa.part.nr_shared =0 ; + qa.part.nr_rr =0 ; + qa.part.rr_pos =0 ; + + nr_excl =cmask_weight (&qa.held_excl.mask); + qa.part.nr_excl = nr_excl; + +/* no excl cid: held_shared stays self-local, the rest unheld */ +if (!nr_excl) { + bpf_for(cid, 0, nr_cids) { +if (cmask_test (cid, &qa.held_shared.mask)) + qa.part.cid_owner[cid] =CID_SELF ; +else + qa.part.cid_owner[cid] =CID_NONE ; + } +return ; + } + +/* +* Snapshot membership and weights so the sum_w and share loops agree. +* A mid-compute change would otherwise wrap nr_shared negative. +*/ + self_w = qa.self_weight ?:100 ; + bpf_for(i, 0, MAX_SUB_SCHEDS) { + cgid_snap[i] = qa.sub_sched_ctxs[i].cgroup_id; + w_snap[i] = cgid_snap[i] ? (qa.sub_sched_ctxs[i].weight ?:100 ) :0 ; + } + +/* +* Participants are self plus each child. Give each a fixed range/rr +* slot: self at slot 0, child i at slot i+1. +* +* sum_w totals every participant's weight. +*/ + sum_w = self_w; + bpf_for(i, 0, MAX_SUB_SCHEDS) { +barrier_var (sum_w); + sum_w += w_snap[i]; + } + +/* +* Split [0, nr_excl) into one contiguous range per participant, each +* the floor of its weight share. cp_range_owner[]/cp_range_end[] record +* each range's owner and cumulative end, total_excl counts the +* exclusive slots, and the rest (nr_excl - total_excl) are shared. +* rr_slots[] lists every participant for the round-robin. +*/ + share = (u64 )nr_excl * self_w / sum_w; + total_excl += share; + cp_range_owner[0 ] =CID_SELF ; + cp_range_end[0 ] = total_excl; + qa.part.rr_slots[nr_rr++] =0 ;/* self holds slot 0 (cgid 0 = no grant) */ + + bpf_for(i, 0, MAX_SUB_SCHEDS) { +u64 cgid = cgid_snap[i]; +s32 w = w_snap[i]; + +barrier_var (total_excl); + share = (u64 )nr_excl * w / sum_w; + total_excl += share; + cp_range_owner[i +1 ] = cgid ? i :CID_NONE ; + cp_range_end[i +1 ] = total_excl; + +if (cgid) { +barrier_var (nr_rr); +if (nr_rr <0 || nr_rr >=MAX_PARTS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + qa.part.rr_slots[nr_rr++] = cgid; + } + } + +/* assign each cid: held-excl by position, the rest self/none */ + bpf_for(cid, 0, nr_cids) { +if (cmask_test (cid, &qa.held_excl.mask)) { +place_one (cid, n, total_excl); + n++; +barrier_var (n); + }else if (cmask_test (cid, &qa.held_shared.mask)) { + qa.part.cid_owner[cid] =CID_SELF ;/* time-share, self-local */ + }else { + qa.part.cid_owner[cid] =CID_NONE ;/* not held */ + } + } + + qa.part.nr_shared = nr_excl - total_excl; + qa.part.nr_rr = nr_rr; +} + +/* +* Charge elapsed wall time to each cid's current owner. Runs under the +* partition guard before every ownership change and from the stats flush, so +* alloc_ns[] reflects the layout that was in effect. Shared-pool time is +* charged to the live round-robin holder. +*/ +static __noinline void account_alloc(void) +{ +u64 now =bpf_ktime_get_ns (); +s32 rr_owner =CID_SELF ; +s32 nr_cids = qa.nr_cids; +u64 delta; +s32 cid, i; + +if (nr_cids <0 || nr_cids >SCX_QMAP_MAX_CPUS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + +/* first call starts the clock */ +if (!qa.alloc_ts) { + qa.alloc_ts = now; +return ; + } + delta = now - qa.alloc_ts; + qa.alloc_ts = now; + qa.alloc_window_ns += delta; + +/* resolve the live shared-pool holder to an owner id */ +if (qa.part.nr_shared && qa.part.nr_rr) { +u32 pos = qa.part.rr_pos; +u64 cgid = pos <MAX_PARTS ? qa.part.rr_slots[pos] :0 ; + +if (cgid) { + rr_owner =CID_NONE ; + bpf_for(i, 0, MAX_SUB_SCHEDS) +if (qa.sub_sched_ctxs[i].cgroup_id == cgid) + rr_owner = i; + } + } + + bpf_for(cid, 0, nr_cids) { +s32 owner = qa.part.cid_owner[cid]; + +if (owner ==CID_SHARED ) + owner = rr_owner; +if (owner >=0 && owner <MAX_SUB_SCHEDS ) + qa.alloc_ns[owner] += delta; +else if (owner ==CID_SELF ) + qa.self_alloc_ns += delta; + } +} + +/* +* apply_partition - execute the plan compute_partition() built +* +* Turn the owner map into the per-child, shared and self cmasks and issue the +* grant/revoke kfuncs as a delta against each child's previous grant. If no +* excl cid, evict every child. +*/ +__noinline void apply_partition(void) +{ +s32 nr_cids = qa.nr_cids; +s32 nr_shared = qa.part.nr_shared; +s32 i, cid; + +if (nr_cids <0 || nr_cids >SCX_QMAP_MAX_CPUS || + nr_shared <0 || nr_shared >MAX_PARTS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + +/* no excl cpu: run own tasks on the held shares, evict children */ +if (!qa.part.nr_excl) { +cmask_copy (&qa.self_cids.mask, &qa.held_shared.mask); + bpf_for(i, 0, MAX_SUB_SCHEDS) +if (qa.sub_sched_ctxs[i].cgroup_id) +scx_bpf_sub_kill (qa.sub_sched_ctxs[i].cgroup_id, +"parent holds no excl cpu to distribute" ); +return ; + } + +/* +* Snapshot the old pool. The per-child revoke below clears ENQ_IMMED on +* the previously-granted pool, so a cid that left the pool (now a +* sibling's excl) doesn't keep a stale ENQ_IMMED on its last holder. +*/ +cmask_copy (&qa.prev_rr_cids.mask, &qa.rr_cids.mask); + +/* turn the owner map into the rr pool, per-child excl, and self sets */ +cmask_init (&qa.rr_cids.mask,0 , nr_cids); +cmask_init (&qa.self_cids.mask,0 , nr_cids); + +/* snapshot each child's grant, then rebuild the new sets below */ + bpf_for(i, 0, MAX_SUB_SCHEDS) { +cmask_copy (&qa.sub_sched_ctxs[i].prev_granted.mask, + &qa.sub_sched_ctxs[i].granted_cids.mask); +cmask_init (&qa.sub_sched_ctxs[i].granted_cids.mask,0 , nr_cids); + } + + bpf_for(i, 0, nr_shared) +cmask_set (qa.part.shared_cids[i], &qa.rr_cids.mask); + bpf_for(cid, 0, nr_cids) { +s32 o = qa.part.cid_owner[cid]; + +if (cmask_test (cid, &qa.rr_cids.mask)) +continue ; +if (o >=0 && o <MAX_SUB_SCHEDS ) +cmask_set (cid, &qa.sub_sched_ctxs[o].granted_cids.mask); +else if (o ==CID_SELF ) +cmask_set (cid, &qa.self_cids.mask); + } + +/* +* Apply each child's exclusive cids as a delta against its previous +* grant. Separately clear the previous shared grant (ENQ_IMMED on the +* old pool), covering cids still pooled and cids that left for a +* sibling's excl. The current holder is granted the new pool below. +*/ + bpf_for(i, 0, MAX_SUB_SCHEDS) { + struct sub_sched_ctx __arena *ssc = &qa.sub_sched_ctxs[i]; +u64 cgid = ssc->cgroup_id; + +if (!cgid) +continue ; + +cmask_copy (&qa.to_revoke_cids.mask, &ssc->prev_granted.mask); +cmask_andnot (&qa.to_revoke_cids.mask, &ssc->granted_cids.mask); +cmask_copy (&qa.to_grant_cids.mask, &ssc->granted_cids.mask); +cmask_andnot (&qa.to_grant_cids.mask, &ssc->prev_granted.mask); + +scx_bpf_sub_revoke (cgid,SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.prev_rr_cids.mask); +scx_bpf_sub_revoke (cgid,SCX_CAP_ENQ |SCX_CAP_PREEMPT |SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.to_revoke_cids.mask); +scx_bpf_sub_grant (cgid,SCX_CAP_ENQ |SCX_CAP_PREEMPT |SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.to_grant_cids.mask,NULL ); + } + +/* the current holder of the shared pool gets ENQ_IMMED on all of it */ +if (nr_shared) { +s32 pos = qa.part.rr_pos; +u64 holder_cgid; + +if (pos <0 || pos >=MAX_PARTS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + + holder_cgid = qa.part.rr_slots[pos];/* 0 = self, nothing to grant */ +if (holder_cgid) +scx_bpf_sub_grant (holder_cgid,SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.rr_cids.mask,NULL ); + } +} + +/* +* Recompute the split off the node's held caps and apply it. The contexts this +* runs from (the sub-sched callbacks, the userspace poke, the rr timer) are not +* serialized by the kernel, so a single runner does the work. A caller that +* finds the guard held leaves part_pending set; the holder drains it before +* releasing, with the rr timer as a backstop. +*/ +static void redistribute (void ) +{ +s32 i; + +__sync_fetch_and_or (&part_pending,1 ); + +if (!part_try_start ()) +return ; + + bpf_for(i, 0, 1024) { +__sync_fetch_and_and (&part_pending,0 ); +/* charge elapsed time to the current partition before rebuilding it */ +account_alloc (); +compute_partition (); +apply_partition (); +if (!__sync_fetch_and_or (&part_pending,0 )) +break ; + } + +part_end (); +} + +/* userspace pokes this (PROG_RUN) to resplit after a cpu.weight change */ +SEC("syscall") +int repartition (void *ctx) +{ +redistribute (); +return 0 ; +} + +/* +* Userspace pokes this (PROG_RUN) to bring alloc_ns[] current before reading +* it for the stats display. Skipping when the partition guard is held is +* fine - alloc_ts is untouched, so the elapsed time is charged next time. +*/ +SEC("syscall") +int flush_alloc (void *ctx) +{ +if (part_try_start ()) { +account_alloc (); +part_end (); + } +return 0 ; +} + +/* +* Hand the shared pool to the next participant in the rotation. Self's turn +* just revokes the pool back to this sched. A child's turn grants it ENQ_IMMED +* on the entire pool. As only excl-held cids are time-shared, a wall-clock +* rotation works. Driven by the round-robin timer. +*/ +static void rr_advance (void ) +{ +s32 nr_shared, old_pos, new_pos; +u64 old_cgid, new_cgid; +u32 nr_rr;/* unsigned for % */ + +/* a redistribute holds the partition and rebuilds the pool, so skip */ +if (!part_try_start ()) +return ; + + nr_rr = qa.part.nr_rr; + nr_shared = qa.part.nr_shared; + +if (nr_shared <0 || nr_shared >MAX_PARTS ) { +scx_bpf_error ("-ERANGE" ); +return ; + } + +if (nr_shared && nr_rr >=2 ) { +/* close out the outgoing holder's pool time */ +account_alloc (); + + old_pos = qa.part.rr_pos; + new_pos = (old_pos +1 ) % nr_rr; + old_cgid = qa.part.rr_slots[old_pos]; + new_cgid = qa.part.rr_slots[new_pos]; + qa.part.rr_pos = new_pos; + +/* +* Move the ENQ_IMMED cap to the next participant. The shared +* cids stay marked CID_SHARED. qmap_dispatch() resolves the +* live holder via rr_pos without the guard, so a dispatch +* racing this handoff may reenqueue a task once. Harmless for a +* time-share. +*/ +if (old_cgid) +scx_bpf_sub_revoke (old_cgid,SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.rr_cids.mask); +if (new_cgid) +scx_bpf_sub_grant (new_cgid,SCX_CAP_ENQ_IMMED , + (void *)(long )&qa.rr_cids.mask,NULL ); + } + +part_end (); + +/* a resplit queued while we held the guard supersedes this rotation */ +if (__sync_fetch_and_or (&part_pending,0 )) +redistribute (); +} + +/* advance the time-shared cid pool every round_robin_ns */ +static int round_robin_timerfn (void *map,int *key,struct bpf_timer *timer) +{ +rr_advance (); +bpf_timer_start (timer, round_robin_ns,0 ); +return 0 ; +} +/* * Custom cid layout for the cid-override test. On invalid input the kfunc * scx_error()s and aborts the scheduler.
@@ -1142,16 +1716,43 @@ s32 BPF_STRUCT_OPS_SLEEPABLE(qmap_init) } qa.task_free_head = (task_ctx_t *)slab; +/* cache the cid count, trusted to be <= SCX_QMAP_MAX_CPUS hereafter */ + qa.nr_cids = nr_cids; + +/* cmasks are embedded in qa, so they only need initializing */ +cmask_init (&qa.idle_cids.mask,0 , nr_cids); +cmask_init (&qa.rr_cids.mask,0 , nr_cids); +cmask_init (&qa.prev_rr_cids.mask,0 , nr_cids); +cmask_init (&qa.self_cids.mask,0 , nr_cids); +cmask_init (&qa.to_revoke_cids.mask,0 , nr_cids); +cmask_init (&qa.to_grant_cids.mask,0 , nr_cids); +cmask_init (&qa.held_excl.mask,0 , nr_cids); +cmask_init (&qa.held_shared.mask,0 , nr_cids); + +scx_bpf_sub_caps (0 ,SCX_CAP_ENQ , (void *)(long )&qa.held_excl.mask); +scx_bpf_sub_caps (0 ,SCX_CAP_ENQ_IMMED , (void *)(long )&qa.held_shared.mask); +cmask_andnot (&qa.held_shared.mask, &qa.held_excl.mask); + + bpf_for(i, 0, MAX_SUB_SCHEDS) { +cmask_init (&qa.sub_sched_ctxs[i].granted_cids.mask,0 , nr_cids); +cmask_init (&qa.sub_sched_ctxs[i].prev_granted.mask,0 , nr_cids); + } +/* -* Allocate and initialize the idle cmask. Starts empty - update_idle -* fills it as cpus enter idle. +* The root starts holding every cid. qmap_sub_ecaps_updated() maintains +* per-cid shared state as effective caps settle, and redistribute() +* rebuilds owner and self from held caps. A non-root node starts with +* nothing. */ - qa_idle_cids =bpf_arena_alloc_pages (&arena,NULL ,1 ,NUMA_NO_NODE ,0 ); -if (!qa_idle_cids) { -scx_bpf_error ("failed to allocate idle cmask" ); -return -ENOMEM ; + bpf_for(i, 0, nr_cids) { +if (!sub_cgroup_id) { +cmask_set (i, &qa.self_cids.mask); + qa.part.cid_owner[i] =CID_SELF ; + }else { + qa.part.cid_owner[i] =CID_NONE ; + } } -cmask_init (qa_idle_cids,0 , nr_cids); + qa.part.nr_shared =0 ; ret =scx_bpf_create_dsq (SHARED_DSQ ,-1 );if (ret) {
@@ -1190,6 +1791,16 @@ s32 BPF_STRUCT_OPS_SLEEPABLE(qmap_init)return ret; } +/* sub-sched: drive the boundary-cid round-robin from a bpf timer */ + timer =bpf_map_lookup_elem (&round_robin_timer, &key); +if (!timer) +return -ESRCH ; +bpf_timer_init (timer, &round_robin_timer,CLOCK_MONOTONIC ); +bpf_timer_set_callback (timer, round_robin_timerfn); + ret =bpf_timer_start (timer, round_robin_ns,0 ); +if (ret) +return ret; +return 0 ; }
@@ -1202,13 +1813,20 @@ s32 BPF_STRUCT_OPS(qmap_sub_attach, struct scx_sub_attach_args *args) {s32 i; +/* as long as there is at least one excl cpu, children can attach */ +if (!cmask_weight (&qa.held_excl.mask)) +return -ENOSPC ; +for (i =0 ; i <MAX_SUB_SCHEDS ; i++) { -if (!qa.sub_sched_cgroup_ids[i]) { - qa.sub_sched_cgroup_ids[i] = args->ops->sub_cgroup_id; -bpf_printk ("attaching sub-sched[%d] on %s" , - i, args->cgroup_path); -return 0 ; - } +if (qa.sub_sched_ctxs[i].cgroup_id) +continue ; + + qa.sub_sched_ctxs[i].cgroup_id = args->ops->sub_cgroup_id; + qa.sub_sched_ctxs[i].weight =100 ;/* until userspace feeds it */ + qa.nr_sub_scheds++; +bpf_printk ("attaching sub-sched[%d] on %s" , i, args->cgroup_path); +redistribute (); +return 0 ; }return -ENOSPC ;
@@ -1219,15 +1837,37 @@ void BPF_STRUCT_OPS(qmap_sub_detach, struct scx_sub_detach_args *args)s32 i;for (i =0 ; i <MAX_SUB_SCHEDS ; i++) { -if (qa.sub_sched_cgroup_ids[i] == args->ops->sub_cgroup_id) { - qa.sub_sched_cgroup_ids[i] =0 ; -bpf_printk ("detaching sub-sched[%d] on %s" , - i, args->cgroup_path); -break ; - } +if (qa.sub_sched_ctxs[i].cgroup_id != args->ops->sub_cgroup_id) +continue ; + + qa.sub_sched_ctxs[i].cgroup_id =0 ; + qa.sub_sched_ctxs[i].weight =100 ; +cmask_init (&qa.sub_sched_ctxs[i].granted_cids.mask,0 , qa.nr_cids); + qa.nr_sub_scheds--; +bpf_printk ("detaching sub-sched[%d] on %s" , i, args->cgroup_path); +redistribute (); +break ; } } +void BPF_STRUCT_OPS (qmap_sub_caps_updated ,const struct scx_cmask *cmask,u64 caps) +{ +/* our held caps changed, redistribute */ +redistribute (); +} + +void BPF_STRUCT_OPS (qmap_sub_ecaps_updated ,s32 cid,u64 before,u64 after) +{ +/* +* Effective caps updated. Track which cids hold shared caps so a self +* task placed there enqueues IMMED. +*/ +if (after &SCX_CAP_ENQ_IMMED ) + qa.cid_shared[cid] = (after &SCX_CAP_ENQ ) ?0 :1 ; +else + qa.cid_shared[cid] =0 ; +} + SCX_OPS_CID_DEFINE(qmap_ops, .flags = SCX_OPS_ENQ_EXITING | SCX_OPS_TID_TO_TASK, .select_cid = (void *)qmap_select_cid,
@@ -1248,6 +1888,8 @@ SCX_OPS_CID_DEFINE(qmap_ops, .cgroup_set_bandwidth = (void *)qmap_cgroup_set_bandwidth, .sub_attach = (void *)qmap_sub_attach, .sub_detach = (void *)qmap_sub_detach, + .sub_caps_updated = (void *)qmap_sub_caps_updated, + .sub_ecaps_updated = (void *)qmap_sub_ecaps_updated, .init_cids = (void *)qmap_init_cids, .init = (void *)qmap_init, .exit = (void *)qmap_exit,
tools/sched_ext/scx_qmap.c +292 -5
379 lines not on this page · raw message
tools/sched_ext/scx_qmap.h +94 -4
134 lines not on this page · raw message
Signature · 1 line
2.55.0
Tejun Heo
reviewerPATCH v5 33/33 tools/sched_ext: scx_qmap - Add sub-sched cap fault injection
In reply to Tejun HeoAdd a fault-injection mode to the scx_qmap sub-scheduler that deliberately dispatches one of its own tasks to a cid it does not hold. The kernel cap check must reject it and re-enqueue with SCX_TASK_REENQ_CAP, so the nr_inject_attempts counter tracks nr_reenq_cap one to one, exercising the delivery-time cap enforcement.
--- tools/sched_ext/scx_qmap.bpf.c | 40 ++++++++++++++++++++++++++++++++++ tools/sched_ext/scx_qmap.c | 20 +++++++++++++---- tools/sched_ext/scx_qmap.h | 8 +++++++ 3 files changed, 64 insertions(+), 4 deletions(-)
tools/sched_ext/scx_qmap.bpf.c +40 -0
@@ -378,6 +378,24 @@ static u64 needs_immed(s32 cid)return qa.cid_shared[cid] ?SCX_ENQ_IMMED :0 ; } +/* first cid this node does NOT hold for fault injection, -1 if none */ +static s32 first_unavail_cid (void ) +{ +s32 nr_cids = qa.nr_cids, c; + +if (nr_cids >SCX_QMAP_MAX_CPUS ) { +scx_bpf_error ("-ERANGE" ); +return -1 ; + } + + bpf_for(c, 0, nr_cids) { +if (!cmask_test (c, &qa.held_excl.mask) && + !cmask_test (c, &qa.held_shared.mask)) +return c; + } +return -1 ; +} +static int weight_to_idx (u32 weight) {/* Coarsely map the compound weight to a FIFO. */
@@ -454,6 +472,28 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags) } } +/* +* Fault injection: deliberately dispatch one of our own tasks to a cid +* we don't hold. The kernel cap check must reject it and re-enqueue +* with SCX_TASK_REENQ_CAP, so nr_inject_attempts tracks nr_reenq_cap +* and proves delivery-time enforcement. Throttled. +*/ +if (qa.inject_mode ==QMAP_INJ_WRONG_CID && p->nr_cpus_allowed >1 && + !(enq_flags &SCX_ENQ_REENQ )) { +static u32 inj_cnt; + +if (!(++inj_cnt %64 )) { +s32 bad =first_unavail_cid (); + +if (bad >=0 &&cmask_test (bad, &taskc->cpus_allowed)) { +__sync_fetch_and_add (&qa.nr_inject_attempts,1 ); +scx_bpf_dsq_insert (p,SCX_DSQ_LOCAL_ON | bad, + slice_ns, enq_flags); +return ; + } + } + } +/* * IMMED stress testing: Every immed_stress_nth'th enqueue, dispatch * directly to prev_cpu's local DSQ even when busy to force dsq->nr > 1
tools/sched_ext/scx_qmap.c +16 -4
@@ -52,7 +52,7 @@ const char help_fmt[] ="\n" "Usage: %s [-s SLICE_US] [-e COUNT] [-t COUNT] [-T COUNT] [-l COUNT] [-b COUNT]\n" " [-N COUNT] [-P] [-M] [-H] [-c CG_PATH] [-d PID] [-D LEN] [-S] [-p] [-I]\n" -" [-F COUNT] [-i SEC] [-R MS] [-v]\n" +" [-F COUNT] [-i SEC] [-R MS] [-J MODE] [-v]\n" "\n" " -s SLICE_US Override slice duration\n" " -e COUNT Trigger scx_bpf_error() after COUNT enqueues\n"
@@ -74,6 +74,7 @@ const char help_fmt[] =" -C MODE cid-override test (shuffle|bad-dup|bad-range|bad-mono)\n" " -i SEC Stats and weight-refresh interval, seconds (default 5)\n" " -R MS Round-robin period for time-shared cpus, ms (default 200)\n" +" -J MODE Fault injection (wrong-cid: dispatch to a cid not held)\n" " -v Print libbpf debug messages\n" " -h Display this help and exit\n" ;
@@ -184,6 +185,7 @@ struct hier_prev {u64 nr_dsps[MAX_SUB_SCHEDS ];u64 nr_reenq_cap;u64 nr_reenq_immed; +u64 nr_inject_attempts; };/* current wall-clock time as "HH:MM:SS" for the startup and interval headers */
@@ -265,12 +267,14 @@ static void print_hier(struct qmap_arena *qa, struct hier_prev *prev, u64 own_cg }format_cid_ranges (qa,CID_SHARED , ranges,sizeof (ranges)); -printf ("hier : nsub=%llu excl=%u shared=%s rr=%s reenq cap/immed +%llu/+%llu\n" , +printf ("hier : nsub=%llu excl=%u shared=%s rr=%s reenq cap/immed +%llu/+%llu inj=+%llu\n" , (unsigned long long )qa->nr_sub_scheds, qa->part.nr_excl, ranges, rr, (unsigned long long )(qa->nr_reenq_cap - prev->nr_reenq_cap), - (unsigned long long )(qa->nr_reenq_immed - prev->nr_reenq_immed)); + (unsigned long long )(qa->nr_reenq_immed - prev->nr_reenq_immed), + (unsigned long long )(qa->nr_inject_attempts - prev->nr_inject_attempts)); prev->nr_reenq_cap = qa->nr_reenq_cap; prev->nr_reenq_immed = qa->nr_reenq_immed; + prev->nr_inject_attempts = qa->nr_inject_attempts;printf ("hier : %-4s %10s %4s %6s %8s %s\n" ,"" ,"cgroup" ,"w" ,"alloc" ,"disp/s" ,"cids" );
@@ -311,6 +315,7 @@ int main(int argc, char **argv)struct hier_prev hprev = {};const char *sub_cg_path =NULL ;char tbuf[32 ]; +u32 inject_mode =0 ;u64 own_cgid =0 ;libbpf_set_print (libbpf_print_fn);
@@ -331,7 +336,7 @@ int main(int argc, char **argv) skel->rodata->slice_ns =__COMPAT_ENUM_OR_ZERO ("scx_public_consts" ,"SCX_SLICE_DFL" ); skel->rodata->max_tasks =16384 ; -while ((opt =getopt (argc, argv,"s:e:t:T:l:b:N:PMHc:d:D:SpIF:C:i:R:vh" )) !=-1 ) { +while ((opt =getopt (argc, argv,"s:e:t:T:l:b:N:PMHc:d:D:SpIF:C:i:R:J:vh" )) !=-1 ) {switch (opt) {case 's' : skel->rodata->slice_ns =strtoull (optarg,NULL ,0 ) *1000 ;
@@ -465,6 +470,12 @@ int main(int argc, char **argv)if (round_robin_ms <10 ) round_robin_ms =10 ;break ; +case 'J' : +if (!strcmp (optarg,"wrong-cid" )) + inject_mode =QMAP_INJ_WRONG_CID ; +else + inject_mode =strtoul (optarg,NULL ,0 ); +break ;case 'v' : verbose = true;break ;
@@ -481,6 +492,7 @@ int main(int argc, char **argv) qa = &skel->arena->qa; qa->test_error_cnt = test_error_cnt; + qa->inject_mode = inject_mode;if (sub_cg_path) printf("%s scx_qmap started: sub-scheduler on %s, stats every %ds\n",
tools/sched_ext/scx_qmap.h +8 -0
@@ -60,6 +60,12 @@ struct qmap_fifo {s32 idx; }; +/* -J fault-injection modes. Selects inject_mode in struct qmap_arena. */ +enum qmap_inject { +QMAP_INJ_OFF =0 , +QMAP_INJ_WRONG_CID =1 ,/* dispatch to a cid we don't hold */ +}; +/* * scx_cmask's are embedded in struct qmap_arena with inline backing storage. * The bpf side uses &field.mask with the normal cmask_* helpers. Userspace
@@ -167,6 +173,8 @@ struct qmap_arena {/* bpf -> userspace: stats */ u64 nr_reenq_cap;/* SCX_TASK_REENQ_CAP bounces */ u64 nr_reenq_immed;/* SCX_TASK_REENQ_IMMED bounces */ +u64 nr_inject_attempts;/* fault-injection: dispatches to an unheld cid */ + u32 inject_mode; /* fault-injection mode (QMAP_INJ_*) */ };#endif /* __SCX_QMAP_H */
Signature · 1 line
2.55.0
Hi Tejun,
Quoted 3 lines · Tejun Heo
Hello,
Changes in v5:
I went through the series and tested the resulting kernel under virtme-ng. I couldn't trigger any crashes, lockups, or warnings, and I don't see any issues that should block applying this.
As I mentioned, one possible follow-up optimization would be to introduce a "scx_has_sub_scheds" static key, indicating whether any sub-scheduler is attached. This could preserve the current fast paths for the common case of a single root-only scheduler, avoiding the small potential overhead of sub-scheduler-specific hierarchy walks and capability checks. And it could also enable additional optimizations in the future.
For the series:
Thanks,
-Andrea
Quoted 260 lines
- Patches 1-9 of v4 were applied to sched_ext/for-7.2-fixes and sched_ext/for-7.3 and are dropped. The series is rebased onto the updated for-7.3.
- New patch (01): WARN when a per-task op is dispatched on a scheduler other than the task's owner, with the two intentional non-owner call sites dispatching explicitly. Hardening out of the v4 placer-vs-owner review discussion. (sashiko AI)
- New prep patch (19): an in-place SAVE/RESTORE requeue of a running task re-ran cid admission and could bounce a task to the reject DSQ under a scheduler holding only
SCX_CAP_ENQ_IMMED. Mark such enqueues with an internalIGNORE_CAPSflag which requires no caps. (sashiko AI)- The
CONFIG_EXT_SUB_SCHED=nscx_prog_sched()stub now also refuses a dead root scheduler, matching the =y behavior (12). (sashiko AI)-
scx_qmap: mask the highpri dispatch pick with the node's own cids and read the subcgroup_idonce in the dispatch path (32). (sashiko AI)v4: https://lore.kernel.org/r/[email protected]
v3: https://lore.kernel.org/r/[email protected]
v2: https://lore.kernel.org/r/[email protected]
v1: https://lore.kernel.org/r/[email protected]The existing sub-scheduler support only covers a part of scheduling. An
scx_schedcan attach to a cgroup subtree under anotherscx_schedand detach, and the dispatch path has programmatic delegation: dispatch runs as top-down recursion viascx_bpf_sub_dispatch(), so a parent decides when a child gets to pick tasks for the local cpu by calling into it.The enqueue path is not implemented yet. Every scheduler in the hierarchy can insert into every local DSQ, so a parent has no way to partition CPUs among its children or protect its own share from them.
This patchset adds that control. Most importantly it enables sub-sched support on the enqueue path, and it extends the same control to the other paths that touch cpu access: occupancy, kicks and preemption, and idle reporting.
The enqueue path cannot use the dispatch path's programmatic model. Dispatch is top-down and the delegation is implicit in the call chain. Enqueue starts at the other end: a leaf picks a cid for a task, and which cids it may use is the cumulative result of its ancestors' delegation decisions. Resolving that programmatically on every enqueue would mean a cross-sched round-trip call chain, possibly retrying when a request cannot be granted as-is. Delegation is therefore state, not calls:
- Ownership is tracked per (scheduler, cid) as a set of capabilities:
-
SCX_CAP_ENQ_IMMED: insert an IMMED task onto the cid's local DSQ. This is the baseline cap (SCX_CAP_BASE) required to make any use of a cpu.-
SCX_CAP_ENQ: insert any task onto the cid's local DSQ.-
SCX_CAP_PREEMPT: preempt a task outside the scheduler's own subtree.Higher caps imply the lower ones for the holder's own use.
- The root owns every cap on every cid. A parent delegates caps to a child with
scx_bpf_sub_grant()and takes them back withscx_bpf_sub_revoke(). A child's cap set is always a subset of its parent's.- The cap state is sharded. The cid space is split into topology-aligned shards, and each scheduler tracks its caps in per-shard cmasks with a per-shard lock. Operations are broken up on shard boundaries and different shards never contend. Shards are expected to serve as the locality unit when cids are handed out to schedulers, so lock granularity scales naturally with the allocation pattern.
- Hot paths check a per-cpu effective-caps copy with a single read. Grant/revoke rings a per-cpu doorbell and the owning cpu folds the new config in at the top of
balance(). Cross-sched communication happens only when the delegation set changes.Enforcement:
- An insert that lacks the required cap is diverted to a kernel-internal per-rq reject DSQ and handed back to the BPF scheduler to re-decide, tagged with
SCX_TASK_REENQ_CAPand the missing caps.- A revoke evicts already-queued and running tasks through the same reenqueue path.
- CPU occupancy is tied to the task slice. Extending a slice requires baseline access on the cpu.
- Kicks are enforced at delivery. Any kick needs baseline access on the target cid, and
SCX_KICK_PREEMPTdegrades to a plain reschedule if the victim is outside the kicker's subtree and the kicker lacksSCX_CAP_PREEMPT.Notifications:
-
ops.sub_caps_updated()reports config-level changes per shard with coalescing.-
ops.sub_ecaps_updated()reports per-cpu effective changes when they take effect.-
ops.update_idle()is routed to the cid's owner, with a re-notification when ownership changes while the cpu sits idle.A parent can evict a misbehaving child with
scx_bpf_sub_kill().To make it concrete, consider a root scheduler R with a child A, which in turn has a child A1:
- On enable, R owns every cap on every cid. A child starts with no caps and cannot use any cpu on its own, so a parent normally makes an initial grant when a child attaches.
- R grants cids 8-15 to A by calling
scx_bpf_sub_grant()with A's cgroup id and a cmask. A grant is all-or-nothing per cid and can only hand down caps R holds literally.- A learns of the grant through
ops.sub_caps_updated(). As each cpu folds the change into its effective caps, A getsops.sub_ecaps_updated()for that cid, and if the cpu is sitting idle, anops.update_idle()re-notification so A can use it right away.- Nesting chains through the same notifier: from its
ops.sub_caps_updated(), A callsscx_bpf_sub_grant()to pass a subset, say cids 12-15, down to A1, whose ownops.sub_caps_updated()then fires. A1's cap set is a subset of A's, which is a subset of R's. Caps A holds only through implication cannot be re-delegated.Using and then losing a cpu, from A's point of view, looks like this:
- Holding
SCX_CAP_ENQon cid 8, A inserts its tasks into cid 8's local DSQ from its enqueue and dispatch paths, extends their slices, and kicks the cpu as usual.- R revokes cid 8. The revoke clears it across A's whole subtree, so A1 loses whatever it held on the cid too.
- Once the revoke reaches the cpu's effective caps, A's tasks queued on cid 8 are handed back to A's
ops.enqueue()tagged withSCX_TASK_REENQ_CAPand the missing caps, a running task is evicted by zeroing its slice, and new inserts are rejected and handed back the same way.- A places the bounced tasks somewhere it still holds, and the notifiers tell it that its holdings shrank.
The final three patches expand the
scx_qmaphierarchical demo: a qmap instance splits the cpus it fully owns among itself and child qmaps in proportion to cpu.weight, time-shares the rounding leftovers through a round-robin pool, and can fault-inject dispatches to unheld cids to demonstrate the kernel-side enforcement.Known limitations:
After this series, sub-scheduling works as long as tasks stay within their cgroup boundary and aren't affined away from the cpus their scheduler can use. Two pieces are still missing for full support:
- cgroup migration doesn't move a task across sub-schedulers. A task moved between cgroups served by different sub-scheds keeps its original scheduler.
- there is no fallback when a sub-scheduler holds no cpu a task is allowed to run on. Such a task, e.g. one affined only to cids its scheduler was never granted or has had revoked, has nowhere to go. The likely direction is reserving a slice off the root scheduler to run tasks without cpu access.
Based on sched_ext/for-7.3 (
3d1519011e39).This patchset contains the following 33 patches.
0001
sched_ext: Assert per-task ops run on the task's owner
0002sched_ext: Make the kick machinery per-sched
0003sched_ext: Addops.init_cids()to finalize the cid layout before init 0004sched_ext: Add CID sharding
0005sched_ext: Add shard boundaries toscx_bpf_cid_override()
0006sched_ext: Deferscx_schedkobj sysfs add into the enable workfns 0007sched_ext: Add per-shardscx_schedstorage scaffolding
0008sched_ext: Addscx_cmask_reffor validated arena cmask access 0009sched_ext: Build theset_cmaskscratch from trusted geometry 0010sched_ext: RCU-protect the sub-sched tree's children/sibling lists 0011sched_ext: Addscx_skip_subtree_pre()
0012sched_ext: Stop resolving a disabled scheduler's programs
0013sched_ext: Add per-shard cap delegation for sub-schedulers
0014sched_ext: Add coalescingsub_caps_updated()notifier for sub-schedulers 0015sched_ext: Maintain per-cpu effective cap copies for single-read checks 0016sched_ext: Addsub_ecaps_updated()effective-cap change notifier 0017sched_ext: Generalize local-DSQ handling to rq-owned DSQs
0018sched_ext: Add reject DSQ for cap-rejected dispatches
0019sched_ext: AddSCX_ENQ_IGNORE_CAPSfor in-place restore
0020sched_ext: Add theSCX_CAP_ENQ_IMMEDcap
0021sched_ext: Assign a unique id to each scheduler instance
0022sched_ext: Route task slice writes throughset_task_slice()
0023sched_ext: Track the cpu a task is runnable on
0024sched_ext: Tie cpu occupancy toSCX_CAP_BASEthrough the task slice 0025sched_ext: Add theSCX_CAP_ENQcap
0026sched_ext: Gate kicks onSCX_CAP_BASEand preemption onSCX_CAP_PREEMPT0027sched_ext: Authorize remote-move inserts against the placing scheduler 0028sched_ext: Routeops.update_idle()to sub-schedulers and re-notify owed scheds 0029sched_ext: Replay ecaps notifications suppressed by bypass
0030sched_ext: Addscx_bpf_sub_kill()to evict a child sub-scheduler 0031tools/sched_ext: Add three-mask cmask intersection iterator
0032tools/sched_ext:scx_qmap- Expand hierarchical sub-scheduling 0033tools/sched_ext:scx_qmap- Add sub-sched cap fault injectionThe patches are organized as follows:
- 01: prep. Assert per-task ops run on the task's owner.
- 02-12: plumbing. Per-sched kick machinery (02),
ops.init_cids()(03), cid sharding (04-05), sysfs and per-shard storage prep (06-07), validated arena cmask access (08) and the trusted-geometryset_cmaskbuild (09), RCU-safe tree walking (10-11), and gating a disabled scheduler's still-resolvable programs (12).- 13-16: cap delegation. Per-shard caps with grant/revoke (13), the coalescing
sub_caps_updated()notifier (14), per-cpu effective caps
(15) and thesub_ecaps_updated()notifier (16).- 17-27: enforcement. The reject DSQ (17-18), the restore cap bypass (19),
SCX_CAP_ENQ_IMMED(20), slice-based occupancy (21-24),SCX_CAP_ENQ(25), preemption and kick gating (26) and remote-move insert authorization (27).- 28-30: idle routing and re-notification (28), bypass replay (29) and
scx_bpf_sub_kill()(30).- 31-33:
scx_qmaphierarchical demo.The patchset is also available in the following git branch:
git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.gitscx-sub-caps-v5diffstat follows. Thanks.
include/linux/sched/ext.h | 33 +- init/init_task.c | 1 + kernel/sched/ext/cid.c | 508 +++++++++++++- kernel/sched/ext/cid.h | 17 +- kernel/sched/ext/ext.c | 852 ++++++++++++++++++----- kernel/sched/ext/idle.c | 86 ++- kernel/sched/ext/internal.h | 334 ++++++++- kernel/sched/ext/sub.c | 1120 +++++++++++++++++++++++++++++- kernel/sched/ext/sub.h | 121 +++- kernel/sched/ext/types.h | 74 +- kernel/sched/idle.c | 8 +- kernel/sched/sched.h | 17 +- tools/sched_ext/include/scx/cid.bpf.h | 77 ++ tools/sched_ext/include/scx/common.bpf.h | 24 + tools/sched_ext/include/scx/compat.bpf.h | 11 +- tools/sched_ext/scx_qmap.bpf.c | 852 ++++++++++++++++++++--- tools/sched_ext/scx_qmap.c | 355 +++++++++- tools/sched_ext/scx_qmap.h | 115 ++- 18 files changed, 4238 insertions(+), 367 deletions(-)--
tejun
Tejun Heo
reviewerHello, Andrea.
Quoted 10 lines · Andrea Righi
I went through the series and tested the resulting kernel under virtme-ng. I couldn't trigger any crashes, lockups, or warnings, and I don't see any issues that should block applying this.
As I mentioned, one possible follow-up optimization would be to introduce a "
scx_has_sub_scheds" static key, indicating whether any sub-scheduler is attached. This could preserve the current fast paths for the common case of a single root-only scheduler, avoiding the small potential overhead of sub-scheduler-specific hierarchy walks and capability checks. And it could also enable additional optimizations in the future.
Yeah, gating the sub-sched-only paths behind a static key while no sub-scheduler is attached is on the todo list. Will follow up with incremental patches.
Quoted 3 lines
For the series:
Reviewed-by Andrea Righi <[email protected]>
Thanks a lot for the review and testing.
--
tejun
Tejun Heo
reviewerApplied 1-33 to sched_ext/for-7.3 with Andrea's Reviewed-by added.
Thanks.
--
tejun