The Linux Kernel Mailing List
 help / color / mirror / Atom feed
* [PATCHSET v4 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers
@ 2026-07-08 21:23 Tejun Heo
  2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 01/40] sched_ext: Record an error on errno-only sub-enable failure Tejun Heo
                   ` (41 more replies)
  0 siblings, 42 replies; 68+ messages in thread
From: Tejun Heo @ 2026-07-08 21:23 UTC (permalink / raw)
  To: David Vernet, Andrea Righi, Changwoo Min
  Cc: sched-ext, Emil Tsalapatis, linux-kernel, Tejun Heo

Hello,

Changes in v4:

- New patch (01): record an error on errno-only sub-enable failures, so
  the disable path runs and a half-initialized sub-scheduler is torn down
  instead of left linked. Pre-existing bug, split out early with a Fixes:
  tag. (sashiko AI)

- New patch (20): stop scx_prog_sched() from resolving a disabled
  scheduler. A program that outlives disable (a timer it armed, a tracing
  program it loaded) could still operate on a torn-down generation; gating
  one choke point closes a cross-generation pshard[] out-of-bounds.
  (sashiko AI)

- Flush the pending kick irq_work in free_kick_syncs() before clearing the
  per-cpu kick state, so a late kick unlinks cleanly at teardown (10).
  (sashiko AI)

- New prep patch (30): track the cpu a task is runnable on
  (p->scx.runnable_cpu), stamped under the rq lock. The slice write path
  uses it to test rq ownership (31), closing a remote-wakeup TOCTOU where a
  cached task_rq() could stale-match a migrated sleeping task. (sashiko AI)

- scx_qmap demo (39): track every cid's idle state regardless of
  delegation and mask it with the node's own cids at the dispatch pick,
  instead of reseeding from a separate idle set. Fixes an already-idle
  reclaimed cid being missed and drops a reseed race. The three-mask cmask
  iterator it uses is split into its own patch (38). (sashiko AI)

- Introduce pshard[] in its final build-then-publish form in the patch
  that adds it rather than rewriting it a few patches later (15, 21).

- Document the remaining limitations for full sub-scheduling support below.
  (Andrea)

v3: https://lore.kernel.org/r/20260707001229.1410929-1-tj@kernel.org
v2: https://lore.kernel.org/r/20260706014058.439853-1-tj@kernel.org
v1: https://lore.kernel.org/r/20260703080159.2314350-1-tj@kernel.org

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 (daf8e166ba59).

This patchset contains the following 40 patches.

 0001 sched_ext: Record an error on errno-only sub-enable failure
 0002 sched_ext: Fix premature ops->priv publication in scx_alloc_and_add_sched()
 0003 tools/sched_ext: scx - Fix cmask_subset(), cmask_equal() and cmask_weight()
 0004 sched_ext: Use READ_ONCE/WRITE_ONCE in cmask word ops and drop _RACY variants
 0005 sched_ext: Add SCX_CALL_CID_OP_TASK() for cid-form op dispatch
 0006 sched_ext: Rename extra_enq_flags to remote_activate_enq_flags
 0007 tools/sched_ext: scx_qmap - Use bare u64/u32/s32 integer types
 0008 sched_ext: Reject direct slice and dsq_vtime writes for cid-form schedulers
 0009 sched_ext: Make scx_bpf_kick_cid() return void
 0010 sched_ext: Make the kick machinery per-sched
 0011 sched_ext: Add ops.init_cids() to finalize the cid layout before init
 0012 sched_ext: Add CID sharding
 0013 sched_ext: Add shard boundaries to scx_bpf_cid_override()
 0014 sched_ext: Defer scx_sched kobj sysfs add into the enable workfns
 0015 sched_ext: Add per-shard scx_sched storage scaffolding
 0016 sched_ext: Add scx_cmask_ref for validated arena cmask access
 0017 sched_ext: Build the set_cmask scratch from trusted geometry
 0018 sched_ext: RCU-protect the sub-sched tree's children/sibling lists
 0019 sched_ext: Add scx_skip_subtree_pre()
 0020 sched_ext: Stop resolving a disabled scheduler's programs
 0021 sched_ext: Add per-shard cap delegation for sub-schedulers
 0022 sched_ext: Add coalescing sub_caps_updated() notifier for sub-schedulers
 0023 sched_ext: Maintain per-cpu effective cap copies for single-read checks
 0024 sched_ext: Add sub_ecaps_updated() effective-cap change notifier
 0025 sched_ext: Generalize local-DSQ handling to rq-owned DSQs
 0026 sched_ext: Add reject DSQ for cap-rejected dispatches
 0027 sched_ext: Add the SCX_CAP_ENQ_IMMED cap
 0028 sched_ext: Assign a unique id to each scheduler instance
 0029 sched_ext: Route task slice writes through set_task_slice()
 0030 sched_ext: Track the cpu a task is runnable on
 0031 sched_ext: Tie cpu occupancy to SCX_CAP_BASE through the task slice
 0032 sched_ext: Add the SCX_CAP_ENQ cap
 0033 sched_ext: Gate kicks on SCX_CAP_BASE and preemption on SCX_CAP_PREEMPT
 0034 sched_ext: Authorize remote-move inserts against the placing scheduler
 0035 sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds
 0036 sched_ext: Replay ecaps notifications suppressed by bypass
 0037 sched_ext: Add scx_bpf_sub_kill() to evict a child sub-scheduler
 0038 tools/sched_ext: Add three-mask cmask intersection iterator
 0039 tools/sched_ext: scx_qmap - Expand hierarchical sub-scheduling
 0040 tools/sched_ext: scx_qmap - Add sub-sched cap fault injection

The patches are organized as follows:

- 01-08: fixes and small prep.

- 09-20: plumbing. Per-sched kick machinery (09-10), ops.init_cids()
  (11), cid sharding (12-13), sysfs and per-shard storage prep (14-15),
  validated arena cmask access (16) and the trusted-geometry set_cmask
  build (17), RCU-safe tree walking (18-19), and gating a disabled
  scheduler's still-resolvable programs (20).

- 21-24: cap delegation. Per-shard caps with grant/revoke (21), the
  coalescing sub_caps_updated() notifier (22), per-cpu effective caps
  (23) and the sub_ecaps_updated() notifier (24).

- 25-34: enforcement. The reject DSQ (25-26), SCX_CAP_ENQ_IMMED (27),
  slice-based occupancy (28-31), SCX_CAP_ENQ (32), preemption and kick
  gating (33) and remote-move insert authorization (34).

- 35-37: idle routing and re-notification (35), bypass replay (36) and
  scx_bpf_sub_kill() (37).

- 38-40: 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-v4

diffstat follows. Thanks.

 include/linux/sched/ext.h                |   33 +-
 init/init_task.c                         |    1 +
 kernel/sched/ext/cid.c                   |  563 ++++++++++++---
 kernel/sched/ext/cid.h                   |   19 +-
 kernel/sched/ext/ext.c                   |  915 +++++++++++++++++++-----
 kernel/sched/ext/idle.c                  |   86 ++-
 kernel/sched/ext/internal.h              |  340 ++++++++-
 kernel/sched/ext/sub.c                   | 1126 +++++++++++++++++++++++++++++-
 kernel/sched/ext/sub.h                   |  118 +++-
 kernel/sched/ext/types.h                 |   74 +-
 kernel/sched/idle.c                      |    8 +-
 kernel/sched/sched.h                     |   18 +-
 tools/sched_ext/include/scx/cid.bpf.h    |  165 ++++-
 tools/sched_ext/include/scx/common.bpf.h |   26 +-
 tools/sched_ext/include/scx/compat.bpf.h |   11 +-
 tools/sched_ext/scx_qmap.bpf.c           |  840 ++++++++++++++++++++--
 tools/sched_ext/scx_qmap.c               |  375 +++++++++-
 tools/sched_ext/scx_qmap.h               |  147 +++-
 18 files changed, 4365 insertions(+), 500 deletions(-)

--
tejun

^ permalink raw reply	[flat|nested] 68+ messages in thread

end of thread, other threads:[~2026-07-09 22:28 UTC | newest]

Thread overview: 68+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-07-08 21:23 [PATCHSET v4 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers Tejun Heo
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 01/40] sched_ext: Record an error on errno-only sub-enable failure Tejun Heo
2026-07-09 20:37   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 02/40] sched_ext: Fix premature ops->priv publication in scx_alloc_and_add_sched() Tejun Heo
2026-07-09 20:38   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 03/40] tools/sched_ext: scx - Fix cmask_subset(), cmask_equal() and cmask_weight() Tejun Heo
2026-07-09 20:39   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 04/40] sched_ext: Use READ_ONCE/WRITE_ONCE in cmask word ops and drop _RACY variants Tejun Heo
2026-07-09 20:39   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 05/40] sched_ext: Add SCX_CALL_CID_OP_TASK() for cid-form op dispatch Tejun Heo
2026-07-09 20:41   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 06/40] sched_ext: Rename extra_enq_flags to remote_activate_enq_flags Tejun Heo
2026-07-09 20:41   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 07/40] tools/sched_ext: scx_qmap - Use bare u64/u32/s32 integer types Tejun Heo
2026-07-09 20:42   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 08/40] sched_ext: Reject direct slice and dsq_vtime writes for cid-form schedulers Tejun Heo
2026-07-09 20:56   ` Andrea Righi
     [not found]   ` <20260708214121.ABDD61F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 09/40] sched_ext: Make scx_bpf_kick_cid() return void Tejun Heo
2026-07-09 20:57   ` Andrea Righi
2026-07-08 21:23 ` [PATCH v4 sched_ext/for-7.3 10/40] sched_ext: Make the kick machinery per-sched Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 11/40] sched_ext: Add ops.init_cids() to finalize the cid layout before init Tejun Heo
     [not found]   ` <20260708215432.0DAD01F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 12/40] sched_ext: Add CID sharding Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 13/40] sched_ext: Add shard boundaries to scx_bpf_cid_override() Tejun Heo
     [not found]   ` <20260708214738.7A1811F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 14/40] sched_ext: Defer scx_sched kobj sysfs add into the enable workfns Tejun Heo
     [not found]   ` <20260708214720.193391F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 15/40] sched_ext: Add per-shard scx_sched storage scaffolding Tejun Heo
     [not found]   ` <20260708214419.34D441F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 16/40] sched_ext: Add scx_cmask_ref for validated arena cmask access Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 17/40] sched_ext: Build the set_cmask scratch from trusted geometry Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 18/40] sched_ext: RCU-protect the sub-sched tree's children/sibling lists Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 19/40] sched_ext: Add scx_skip_subtree_pre() Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 20/40] sched_ext: Stop resolving a disabled scheduler's programs Tejun Heo
     [not found]   ` <20260708215520.8C5461F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 21/40] sched_ext: Add per-shard cap delegation for sub-schedulers Tejun Heo
     [not found]   ` <20260708220057.20F581F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 22/40] sched_ext: Add coalescing sub_caps_updated() notifier " Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 23/40] sched_ext: Maintain per-cpu effective cap copies for single-read checks Tejun Heo
     [not found]   ` <20260708220327.7BA8B1F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 24/40] sched_ext: Add sub_ecaps_updated() effective-cap change notifier Tejun Heo
     [not found]   ` <20260708220220.87C181F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 25/40] sched_ext: Generalize local-DSQ handling to rq-owned DSQs Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 26/40] sched_ext: Add reject DSQ for cap-rejected dispatches Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 27/40] sched_ext: Add the SCX_CAP_ENQ_IMMED cap Tejun Heo
     [not found]   ` <20260708215657.DDB5E1F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 28/40] sched_ext: Assign a unique id to each scheduler instance Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 29/40] sched_ext: Route task slice writes through set_task_slice() Tejun Heo
     [not found]   ` <20260708215333.747381F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 30/40] sched_ext: Track the cpu a task is runnable on Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 31/40] sched_ext: Tie cpu occupancy to SCX_CAP_BASE through the task slice Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 32/40] sched_ext: Add the SCX_CAP_ENQ cap Tejun Heo
     [not found]   ` <20260708220009.E27C81F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 33/40] sched_ext: Gate kicks on SCX_CAP_BASE and preemption on SCX_CAP_PREEMPT Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 34/40] sched_ext: Authorize remote-move inserts against the placing scheduler Tejun Heo
2026-07-09 20:09   ` Andrea Righi
     [not found]   ` <20260708220444.DDA121F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 35/40] sched_ext: Route ops.update_idle() to sub-schedulers and re-notify owed scheds Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 36/40] sched_ext: Replay ecaps notifications suppressed by bypass Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 37/40] sched_ext: Add scx_bpf_sub_kill() to evict a child sub-scheduler Tejun Heo
     [not found]   ` <20260708221110.ED3521F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 38/40] tools/sched_ext: Add three-mask cmask intersection iterator Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 39/40] tools/sched_ext: scx_qmap - Expand hierarchical sub-scheduling Tejun Heo
     [not found]   ` <20260708220353.392CD1F000E9@smtp.kernel.org>
2026-07-09 22:28     ` Tejun Heo
2026-07-08 21:24 ` [PATCH v4 sched_ext/for-7.3 40/40] tools/sched_ext: scx_qmap - Add sub-sched cap fault injection Tejun Heo
2026-07-09 21:18 ` [PATCHSET v4 sched_ext/for-7.3] sched_ext: Capability-based CPU delegation for sub-schedulers Tejun Heo
2026-07-09 22:13 ` Tejun Heo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox