sched_ext: Add cmask, a base-windowed bitmap over cid space
authorTejun Heo <tj@kernel.org>
Wed, 29 Apr 2026 18:09:10 +0000 (08:09 -1000)
committerTejun Heo <tj@kernel.org>
Wed, 29 Apr 2026 18:25:07 +0000 (08:25 -1000)
commita58e6b79b432f2f08e6a2bbe638a60e4424a7cba
treef2e6b2c6fbb608b86277ec2d82164e5e5519729b
parent32a54807c9a56a161f29f6640f9f4ef88380398c
sched_ext: Add cmask, a base-windowed bitmap over cid space

Sub-scheduler code built on cids needs bitmaps scoped to a slice of cid
space (e.g. the idle cids of a shard). A cpumask sized for NR_CPUS wastes
most of its bits for a small window and is awkward in BPF.

scx_cmask covers [base, base + nr_bits). bits[] is aligned to the global
64-cid grid: bits[0] spans [base & ~63, (base & ~63) + 64). Any two
cmasks therefore address bits[] against the same global windows, so
cross-cmask word ops reduce to

dest->bits[i] OP= operand->bits[i - delta]

with no bit-shifting, at the cost of up to one extra storage word for
head misalignment. This alignment guarantee is the reason binary ops
can stay word-level; every mutating helper preserves it.

Kernel side in ext_cid.[hc]; BPF side in tools/sched_ext/include/scx/
cid.bpf.h. BPF side drops the scx_ prefix (redundant in BPF code) and
adds the extra helpers that basic idle-cpu selection needs.

No callers yet.

v2: Narrow to helpers that will be used in the planned changes;
    set/bit/find/zero ops will be added as usage develops.

v3: cmask_copy_from_kernel: validate src->base == 0 via probe-read;
    bit-level nr_bits check instead of round-up word count. (Sashiko)

v4: Bump CMASK_CAS_TRIES to 1<<23 so abort fires only after seconds
    of real spinning, not on plausible contention. Switch
    __builtin_ctzll() to the ctzll() wrapper for clang compat
    (Changwoo).

Signed-off-by: Tejun Heo <tj@kernel.org>
Reviewed-by: Cheng-Yang Chou <yphbchou0911@gmail.com>
Reviewed-by: Changwoo Min <changwoo@igalia.com>
Reviewed-by: Andrea Righi <arighi@nvidia.com>
kernel/sched/ext_cid.h
kernel/sched/ext_types.h
tools/sched_ext/include/scx/cid.bpf.h [new file with mode: 0644]
tools/sched_ext/include/scx/common.bpf.h