sched_ext: Add cmask, a base-windowed bitmap over cid space
Subsystems (2)
Tejun Heo
reviewerPATCH 10/17 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.
--- kernel/sched/ext_cid.h | 25 + kernel/sched/ext_types.h | 38 ++ tools/sched_ext/include/scx/cid.bpf.h | 597 +++++++++++++++++++++++ tools/sched_ext/include/scx/common.bpf.h | 1 + 4 files changed, 661 insertions(+) create mode 100644 tools/sched_ext/include/scx/cid.bpf.h
kernel/sched/ext_cid.h +25 -0
@@ -127,4 +127,29 @@ static inline s32 scx_cpu_to_cid(struct scx_sched *sch, s32 cpu)return __scx_cpu_to_cid (cpu); } +static inline bool __scx_cmask_contains (const struct scx_cmask *m,u32 cid) +{ +return likely (cid >= m->base && cid < m->base + m->nr_bits); +} + +/* Word in bits[] covering @cid. @cid must satisfy __scx_cmask_contains(). */ +static inline u64 *__scx_cmask_word (const struct scx_cmask *m,u32 cid) +{ +return (u64 *)&m->bits[cid /64 - m->base /64 ]; +} + +static inline void scx_cmask_init (struct scx_cmask *m,u32 base,u32 nr_bits) +{ + m->base = base; + m->nr_bits = nr_bits; +memset (m->bits,0 ,SCX_CMASK_NR_WORDS (nr_bits) *sizeof (u64)); +} + +static inline void __scx_cmask_set (struct scx_cmask *m,u32 cid) +{ +if (!__scx_cmask_contains (m, cid)) +return ; + *__scx_cmask_word (m, cid) |=BIT_U64 (cid &63 ); +} +#endif /* _KERNEL_SCHED_EXT_CID_H */
kernel/sched/ext_types.h +38 -0
@@ -63,4 +63,42 @@ struct scx_cid_topo {s32 node_idx; }; +/* +* cmask: variable-length, base-windowed bitmap over cid space +* ----------------------------------------------------------- +* +* A cmask covers the cid range [base, base + nr_bits). bits[] is aligned to the +* global 64-cid grid: bits[0] spans [base & ~63, (base & ~63) + 64), so the +* first (base & 63) bits of bits[0] are head padding and any tail past base + +* nr_bits is tail padding. Both must stay zero for the lifetime of the mask; +* all mutating helpers preserve that invariant. +* +* Grid alignment means two cmasks always address bits[] against the same global +* 64-cid windows, so cross-cmask word ops (AND, OR, ...) reduce to +* +* dst->bits[i] OP= src->bits[i - delta] +* +* with no bit-shifting, regardless of how the two bases relate mod 64. +*/ +struct scx_cmask { +u32 base; +u32 nr_bits; + DECLARE_FLEX_ARRAY(u64, bits); +}; + +/* +* Number of u64 words of bits[] storage that covers @nr_bits regardless of base +* alignment. The +1 absorbs up to 63 bits of head padding when base is not +* 64-aligned - always allocating one extra word beats branching on base or +* splitting the compute. +*/ +#define SCX_CMASK_NR_WORDS (nr_bits) (((nr_bits) + 63) / 64 + 1) + +/* +* Define an on-stack cmask for up to @cap_bits. @name is a struct scx_cmask * +* aliasing zero-initialized storage; call scx_cmask_init() to set base/nr_bits. +*/ +#define SCX_CMASK_DEFINE (name, cap_bits) \ + DEFINE_RAW_FLEX(struct scx_cmask, name, bits, SCX_CMASK_NR_WORDS(cap_bits)) +#endif /* _KERNEL_SCHED_EXT_TYPES_H */
tools/sched_ext/include/scx/cid.bpf.h new file +597 -0
597 lines not on this page · raw message
tools/sched_ext/include/scx/common.bpf.h +1 -0
@@ -1055,5 +1055,6 @@ static inline u64 scx_clock_irq(u32 cpu)#include "compat.bpf.h" #include "enums.bpf.h" +#include "cid.bpf.h" #endif /* __SCX_COMMON_BPF_H */
Signature · 1 line
2.53.0