bpf/arena: Direct kernel-side access
Subsystems (2)
Tejun Heo
reviewerPATCH v2 1/1 bpf/arena: Direct kernel-side access
Hello,
Internal preview of v2 before public posting. Recipients are only the three of you for review.
Motivation
----------
sched_ext's ops_cid.set_cmask() hands the BPF scheduler a struct scx_cmask *. The kernel translates a kernel cpumask to a cmask, but it had no way to write into the arena, so the cmask lived in kernel memory and was passed as a trusted pointer. BPF cmask helpers all operate on arena cmasks though, so the BPF side had to word-by-word probe-read the kernel cmask into an arena cmask via cmask_copy_from_kernel() before any helper could touch it. It works, but is clumsy.
The shape isn't unique to set_cmask. Sub-scheduler support is on the way and more sched_ext callbacks will want to pass structured data to BPF. Anywhere a kfunc or struct_ops callback wants to hand a struct to a BPF program, arena residence is the natural answer.
Approach
--------
Each arena gets a per-arena scratch page. Arenas stay sparsely mapped as today - PTEs are populated only for allocated pages. A new arch fault hook (bpf_arena_handle_page_fault) is wired into x86 page_fault_oops() and arm64 __do_kernel_fault(), after KFENCE. When a kernel-side access faults inside an arena's kern_vm range, the helper walks the stack to find the BPF program responsible, range-checks the fault address against prog->aux->arena, and atomically installs the scratch page into the empty PTE via a new ptep_try_install() wrapper. The kernel instruction then retries and reads/writes the scratch page. Real allocations naturally overwrite scratch PTEs; free paths and map destruction treat scratch as non-owned.
The mechanism is default behavior - no UAPI flag.
What this preserves
-------------------
All the debugging properties of today's sparse-PTE design are preserved:
* BPF programs still fault on unmapped arena accesses. The fault semantics (instruction retry with rdst = 0) and the violation report through bpf_streams are unchanged for prog-side accesses.
* The first kernel-side touch of an unmapped address is reported via bpf_streams the same way as a prog-side fault, with the stack walk attributing it to the originating prog.
* User-side fault semantics are unchanged. arena_vm_fault() treats a scratch PTE as absent and lazy-allocates a real page (or returns SIGSEGV under BPF_F_SEGV_ON_FAULT) the same as before.
* Repeat kernel-side faults on the same address after a free still re-install scratch, so the slot's "bad access" is reported on every fresh occurrence; only repeat faults without an intervening free are absorbed.
What changes for the kernel-side caller is just that an unmapped deref no longer oopses - it retries through the scratch page and emits a violation report. The same shape today's BPF instruction faults have.
Patches 1-2 (atomic PTE install + arena scratch-page recovery)
--------------------------------------------------------------
mm: Add ptep_try_install() for lockless empty-slot installs
bpf: Recover arena kernel faults with scratch page
Patches 3-5 (helpers used by struct_ops registration)
-----------------------------------------------------
bpf: Add sleepable variant of bpf_arena_alloc_pages for kernel callers
bpf: Add bpf_struct_ops_for_each_prog()
bpf/arena: Add bpf_arena_map_kern_vm_start() and bpf_prog_arena()
Patches 6-8 (sched_ext: arena auto-discovery, allocator, set_cmask)
-------------------------------------------------------------------
sched_ext: Require an arena for cid-form schedulers
sched_ext: Sub-allocator over kernel-claimed BPF arena pages
sched_ext: Convert ops.set_cmask() to arena-resident cmask
Patch 6 reads each member prog's prog->aux->arena via bpf_prog_arena() and requires the cid-form struct_ops to reference exactly one arena. Patch 7 builds a gen_pool sub-allocator inside that arena. Patch 8 converts set_cmask() to write into arena memory; BPF dereferences via __arena like any other arena struct, no probe-reads.
v1 -> v2
--------
* Dropped the BPF_F_ARENA_MAP_ALWAYS uapi flag and pre-populated garbage page. Replaced by lazy scratch-page install on first kernel-side fault.
* Dropped bpf-arena-pte-cb-prep: callbacks read scratch_page from a field in their data struct, not via arena indirection.
* Dropped bpf-prog-for-each-used-map: verifier already enforces one arena per prog (prog->aux->arena), so iteration over used_maps is unnecessary. bpf_prog_arena() exposes the prog's arena directly.
* New ptep_try_install() in <linux/pgtable.h>: the atomic install primitive used by the arena fault helper. Generic stub returns false; x86 and arm64 override with try_cmpxchg.
Base
----
sched_ext/for-7.2 with for-7.1-fixes merged in (de79a6cb3c3e).
v1 RFC for reference:
https://lore.kernel.org/all/[email protected]/
arch/arm64/include/asm/pgtable.h | 8 ++ arch/arm64/mm/fault.c | 4 + arch/x86/include/asm/pgtable.h | 8 ++ arch/x86/mm/fault.c | 5 ++ include/linux/bpf.h | 14 ++++ include/linux/pgtable.h | 16 ++++ kernel/bpf/arena.c | 141 +++++++++++++++++++++++++++++++--- kernel/bpf/bpf_struct_ops.c | 36 +++++++++ kernel/bpf/core.c | 5 ++ kernel/sched/build_policy.c | 4 + kernel/sched/ext.c | 132 +++++++++++++++++++++++++++++-- kernel/sched/ext_arena.c | 128 ++++++++++++++++++++++++++++++ kernel/sched/ext_arena.h | 18 +++++ kernel/sched/ext_cid.c | 16 +--- kernel/sched/ext_internal.h | 24 +++++- kernel/sched/ext_types.h | 10 +++ tools/sched_ext/include/scx/cid.bpf.h | 52 ------------- tools/sched_ext/scx_qmap.bpf.c | 6 +- 18 files changed, 540 insertions(+), 87 deletions(-)
Thanks.
--
tejun
Tejun Heo
reviewerPATCH 1/3 sched_ext: Rename scx_cmask.nr_bits to nr_cids
struct scx_cmask is a base-windowed bitmap over cid space. Each bit represents one cid, so the count of active bits is the count of cids. The sibling struct scx_cid_shard already uses nr_cids. Rename as a prep so the following patches that grow the cmask API can use the consistent name.
--- kernel/sched/ext_cid.h | 8 ++-- kernel/sched/ext_types.h | 12 ++--- tools/sched_ext/include/scx/cid.bpf.h | 64 +++++++++++++-------------- 3 files changed, 42 insertions(+), 42 deletions(-)
kernel/sched/ext_cid.h +4 -4
@@ -138,7 +138,7 @@ static inline bool scx_is_cid_type(void)static inline bool __scx_cmask_contains (const struct scx_cmask *m,u32 cid) { -return likely (cid >= m->base && cid < m->base + m->nr_bits); +return likely (cid >= m->base && cid < m->base + m->nr_cids); }/* Word in bits[] covering @cid. @cid must satisfy __scx_cmask_contains(). */
@@ -147,11 +147,11 @@ 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) +static inline void scx_cmask_init (struct scx_cmask *m,u32 base,u32 nr_cids) { m->base = base; - m->nr_bits = nr_bits; -memset (m->bits,0 ,SCX_CMASK_NR_WORDS (nr_bits) *sizeof (u64)); + m->nr_cids = nr_cids; +memset (m->bits,0 ,SCX_CMASK_NR_WORDS (nr_cids) *sizeof (u64)); }static inline void __scx_cmask_set (struct scx_cmask *m,u32 cid)
kernel/sched/ext_types.h +6 -6
@@ -67,10 +67,10 @@ struct scx_cid_topo {* cmask: variable-length, base-windowed bitmap over cid space * ----------------------------------------------------------- * -* A cmask covers the cid range [base, base + nr_bits). bits[] is aligned to the +* A cmask covers the cid range [base, base + nr_cids). 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; +* nr_cids 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
@@ -82,21 +82,21 @@ struct scx_cid_topo {*/ struct scx_cmask {u32 base; -u32 nr_bits; +u32 nr_cids; DECLARE_FLEX_ARRAY(u64, bits); };/* -* Number of u64 words of bits[] storage that covers @nr_bits regardless of base +* Number of u64 words of bits[] storage that covers @nr_cids 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 SCX_CMASK_NR_WORDS (nr_cids) (((nr_cids) + 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. +* aliasing zero-initialized storage; call scx_cmask_init() to set base/nr_cids. */ #define SCX_CMASK_DEFINE (name, cap_bits) \ DEFINE_RAW_FLEX(struct scx_cmask, name, bits, SCX_CMASK_NR_WORDS(cap_bits))
tools/sched_ext/include/scx/cid.bpf.h +32 -32
191 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH 1/3] sched_ext: Rename scx_cmask.nr_bits to nr_cids
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Low] Incomplete refactoring of `nr_bits` to `nr_cids` causes a compilation error in…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] Incomplete refactoring of nr_bits to nr_cids causes a compilation error in cmask_copy_from_kernel(). --
commit 7049bf95e9f693c1107678499b063bd2c1a25e08
Author: Tejun Heo <[email protected]>
sched_ext: Rename scx_cmask.nr_bits to nr_cids
struct scx_cmask is a base-windowed bitmap over cid space. Each bit represents one cid, so the count of active bits is the count of cids. The sibling struct scx_cid_shard already uses nr_cids. Rename as a prep so the following patches that grow the cmask API can use the consistent name.
Quoted 4 lines
kernel/sched/ext_types.h +0
-0
[ ... ]
kernel/sched/ext_types.h struct scx_cid_topo { · line 87
Quoted 8 lines
kernel/sched/ext_types.h +1
-1@@ -82,21 +82,21 @@ struct scx_cid_topo {*/ struct scx_cmask {u32 base; -u32 nr_bits; +u32 nr_cids; DECLARE_FLEX_ARRAY(u64, bits); };
Will this rename cause a build failure for BPF programs using cmask_copy_from_kernel() from tools/sched_ext/include/scx/cid.bpf.h?
It appears cmask_copy_from_kernel() still references the old nr_bits member:
static __always_inline void cmask_copy_from_kernel(struct scx_cmask __arena *dst,
const struct scx_cmask *src)
{
u32 base = 0, nr_bits = 0, nr_words, wi;
...
if (bpf_probe_read_kernel(&nr_bits, sizeof(nr_bits), &src->nr_bits)) {
scx_bpf_error("probe-read cmask->nr_bits failed");
return;
}
if (nr_bits > dst->nr_bits) {
scx_bpf_error("src cmask nr_bits=%u exceeds dst nr_bits=%u",
nr_bits, dst->nr_bits);
return;
}...
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Tejun Heo
reviewerPATCH 2/3 sched_ext: Track bits[] storage size in struct scx_cmask
In reply to Tejun Heoscx_cmask carries @base and @nr_cids but not the bits[] allocation size, so helpers reshaping the active range have no way to check it fits and later kfuncs taking caller-provided storage can't validate it.
Add @alloc_words (u64 word count) annotated with __counted_by, and split the bit-range API into three helpers:
- SCX_CMASK_DEFINE() / __SCX_CMASK_DEFINE() define an on-stack cmask, the latter taking an explicit capacity for oversized storage. SCX_CMASK_DEFINE_SHARD() is a thin wrapper that always reserves SCX_CID_SHARD_MAX_CPUS bits of storage.
- scx_cmask_init() / __scx_cmask_init() initialize a cmask, with the same tight-vs-explicit split.
- scx_cmask_reframe() reshapes the active range without resizing storage.
The BPF mirror (cmask_init / __cmask_init / cmask_reframe) gets the same shape.
Add scx_cmask_clear() and scx_cmask_fill() to zero and set the active-range bits respectively. scx_cpumask_to_cmask() uses scx_cmask_clear(); scx_cmask_init() would otherwise re-write @alloc_words on every call.
A later patch uses @alloc_words in scx_cmask_ref_shard() to refuse output storage that can't hold the requested shard.
--- kernel/sched/ext_cid.c | 48 ++++++++++++++++++++-- kernel/sched/ext_cid.h | 57 ++++++++++++++++++++++++++- kernel/sched/ext_types.h | 56 +++++++++++++++++++++----- tools/sched_ext/include/scx/cid.bpf.h | 57 +++++++++++++++++++++++++-- 4 files changed, 202 insertions(+), 16 deletions(-)
kernel/sched/ext_cid.c +45 -3
@@ -222,19 +222,61 @@ s32 scx_cid_init(struct scx_sched *sch)return 0 ; } +/** +* scx_cmask_clear - Zero every bit in @m's active range +* @m: cmask to clear +* +* Storage past the active range is left as is. +*/ +void scx_cmask_clear (struct scx_cmask *m) +{ +u32 nr_words; + +if (!m->nr_cids) +return ; + nr_words = (m->base + m->nr_cids -1 ) /64 - m->base /64 +1 ; +memset (m->bits,0 , nr_words *sizeof (u64)); +} + +/** +* scx_cmask_fill - Set every bit in @m's active range +* @m: cmask to fill +* +* Counterpart to scx_cmask_clear(). Storage past the active range is left as is. +*/ +void scx_cmask_fill (struct scx_cmask *m) +{ +u32 nr_words, head_bits, tail_bits; + +if (!m->nr_cids) +return ; + nr_words = (m->base + m->nr_cids -1 ) /64 - m->base /64 +1 ; +memset (m->bits,0xff , nr_words *sizeof (u64)); + +/* clear word-0 bits below base */ + head_bits = m->base &63 ; +if (head_bits) + m->bits[0 ] &= ~((1ULL << head_bits) -1 ); + +/* clear last-word bits at or past base + nr_cids */ + tail_bits = (m->base + m->nr_cids) &63 ; +if (tail_bits) + m->bits[nr_words -1 ] &= (1ULL << tail_bits) -1 ; +} +/** * scx_cpumask_to_cmask - Translate a kernel cpumask into a cmask * @src: source cpumask * @dst: cmask to write * -* Initialize @dst to cover the full cid space [0, num_possible_cpus()) and -* set the bit for each cid whose cpu is in @src. +* Clear @dst's active range and set the bit for each cid whose cpu is in +* @src and lies within that range. Out-of-range cids are silently ignored. */ void scx_cpumask_to_cmask (const struct cpumask *src,struct scx_cmask *dst) {s32 cpu; -scx_cmask_init (dst,0 ,num_possible_cpus ()); +scx_cmask_clear (dst);for_each_cpu (cpu, src) {s32 cid =__scx_cpu_to_cid (cpu);
kernel/sched/ext_cid.h +56 -1
73 lines not on this page · raw message
kernel/sched/ext_types.h +47 -9
74 lines not on this page · raw message
tools/sched_ext/include/scx/cid.bpf.h +54 -3
74 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH 2/3] sched_ext: Track bits[] storage size in struct scx_cmask
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] The per-CPU `scx_set_cmask_scratch` variable is never initialized, causing…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] The per-CPU scx_set_cmask_scratch variable is never initialized, causing scx_cpumask_to_cmask() to silently pass empty CPU masks to the BPF scheduler. --
commit c63d115e3f87dfb00acdde042926edb85a5907eb
Author: Tejun Heo <[email protected]>
sched_ext: Track bits[] storage size in struct scx_cmask
This commit adds an alloc_words field to struct scx_cmask to track the allocation size of the bits[] array, and splits the bit-range API into initialization, reframing, and clearing helpers.
Quoted 4 lines
kernel/sched/ext_cid.c +0
-0
[ ... ]
kernel/sched/ext_cid.c void scx_cpumask_to_cmask(const struct cpumask *src, struct scx_cmask *dst) · line 278
Quoted 6 lines
kernel/sched/ext_cid.c +1
-1@@ -275,10 +275,10 @@ void scx_cpumask_to_cmask(const struct cpumask *src, struct scx_cmask *dst) {s32 cpu; -scx_cmask_init (dst,0 ,num_possible_cpus ()); +scx_cmask_clear (dst);
Can this regression cause scx_cpumask_to_cmask() to generate empty masks when dst is scx_set_cmask_scratch?
Since scx_set_cmask_scratch is allocated zero-filled, its nr_cids defaults to 0.
With scx_cmask_init() removed here, if scx_set_cmask_scratch is passed as dst without being initialized elsewhere, scx_cmask_clear() will see !dst->nr_cids and return immediately doing nothing.
The subsequent loop then calls __scx_cmask_set(dst, cid) for each CPU. Because __scx_cmask_contains() evaluates to cid >= 0 && cid < 0, which is always false, no bits are ever set.
Could this result in the BPF scheduler receiving an empty cmask for operations like set_cpumask?
Quoted 2 lines
kernel/sched/ext_cid.c +0
-0for_each_cpu (cpu, src) {s32 cid =__scx_cpu_to_cid (cpu);
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Tejun Heo
reviewerPATCH 3/3 sched_ext: Add cmask mask ops
In reply to Tejun HeoSub-sched cap code and other upcoming consumers need bulk cmask ops, both mutating (and/or/copy/andnot) and predicate (subset/intersects).
cmask_walk_op2() walks the intersection of two ranges word by word; cmask_walk_op1() walks one range. Both are __always_inline and dispatched on a compile-time-constant op enum, so each public entry collapses to a specialized loop with the inner switch reduced to one arm.
Two-cmask ops only touch bits in the intersection of the two ranges; bits outside are left unchanged. scx_cmask_or_racy() and scx_cmask_copy_racy() mirror the locking forms but read @src word-by-word through data_race(); callers handle ordering with concurrent writers themselves.
--- kernel/sched/ext_cid.c | 259 +++++++++++++++++++++++++++++++++++++++++ kernel/sched/ext_cid.h | 8 ++ 2 files changed, 267 insertions(+)
kernel/sched/ext_cid.c +259 -0
@@ -393,6 +393,265 @@ __bpf_kfunc s32 scx_bpf_cpu_to_cid(s32 cpu, const struct bpf_prog_aux *aux)return scx_cpu_to_cid (sch, cpu); } +/* +* Set ops on cmasks. cmask_walk_op2() shares one walk across mutating +* (and/or/copy/andnot) and predicate (subset/intersects) two-cmask forms; +* cmask_walk_op1() does the same shape over a single cmask range. Every public +* entry passes a compile-time-constant @op; cmask_walk_op{1,2}() and +* cmask_word_op{1,2}() are __always_inline so the inner switch collapses to the +* selected op and cmask_op2_is_pred() folds the predicate early-exit out of +* mutating ops. +* +* Two-cmask ops only touch @dst bits inside the intersection of the two ranges; +* bits outside stay untouched. In particular, scx_cmask_copy() does NOT zero +* @dst bits that lie outside @src's range. +* +* The _RACY variants are otherwise identical to their non-racy counterpart but +* read @src word-by-word via data_race(). Memory ordering with concurrent +* writers is the caller's responsibility. +*/ +enum cmask_op2 { +/* mutating */ +CMASK_OP2_AND , +CMASK_OP2_OR , +CMASK_OP2_OR_RACY , +CMASK_OP2_COPY , +CMASK_OP2_COPY_RACY , +CMASK_OP2_ANDNOT , +/* predicates - short-circuit when the per-word result is true */ +CMASK_OP2_SUBSET , +CMASK_OP2_INTERSECTS , +}; + +static __always_inline bool cmask_op2_is_pred(const enum cmask_op2 op) +{ +return op ==CMASK_OP2_SUBSET || op ==CMASK_OP2_INTERSECTS ; +} + +static __always_inline bool cmask_word_op2(u64 *av, const u64 *bp, u64 mask, +const enum cmask_op2 op) +{ +switch (op) { +case CMASK_OP2_AND : + *av &= ~mask | *bp; +return false; +case CMASK_OP2_OR : + *av |= *bp & mask; +return false; +case CMASK_OP2_OR_RACY : + *av |=data_race (*bp) & mask; +return false; +case CMASK_OP2_COPY : + *av = (*av & ~mask) | (*bp & mask); +return false; +case CMASK_OP2_COPY_RACY : + *av = (*av & ~mask) | (data_race (*bp) & mask); +return false; +case CMASK_OP2_ANDNOT : + *av &= ~(*bp & mask); +return false; +case CMASK_OP2_SUBSET : +/* stop on the first bit in @sub not set in @super */ +return (*bp & ~*av) & mask; +case CMASK_OP2_INTERSECTS : +return (*av & *bp) & mask; + } +unreachable (); +} + +/* +* Walk the intersection of [@a_base, @a_base + @a_nr_cids) with [@b_base, +* @b_base + @b_nr_cids) word by word, applying @op. Mutating ops walk all words +* and return false; predicates return true on the first word whose per-word +* test is true. Empty intersection returns false (matches "no bits to consider" +* for both mutate and predicate). +* +* Base/nr_cids are taken as parameters so callers with snapshotted bounds can +* drive the walk with values independent of the cmask's header. +*/ +static __always_inline bool cmask_walk_op2(u64 *a_bits, u32 a_base, u32 a_nr_cids, +const u64 *b_bits,u32 b_base,u32 b_nr_cids, +const enum cmask_op2 op) +{ +u32 lo =max (a_base, b_base); +u32 hi =min (a_base + a_nr_cids, b_base + b_nr_cids); +u32 a_word_off = a_base /64 ; +u32 b_word_off = b_base /64 ; +u32 lo_word = lo /64 ; +u32 hi_word = (hi -1 ) /64 ; +u64 head_mask =GENMASK_U64 (63 , lo &63 ); +u64 tail_mask =GENMASK_U64 ((hi -1 ) &63 ,0 ); +u32 w; + +if (lo >= hi) +return false; + +if (lo_word == hi_word) +return cmask_word_op2 (&a_bits[lo_word - a_word_off], + &b_bits[lo_word - b_word_off], + head_mask & tail_mask, op); + +if (cmask_word_op2 (&a_bits[lo_word - a_word_off], + &b_bits[lo_word - b_word_off], head_mask, op) && +cmask_op2_is_pred (op)) +return true; + +for (w = lo_word +1 ; w < hi_word; w++) +if (cmask_word_op2 (&a_bits[w - a_word_off], + &b_bits[w - b_word_off], ~0ULL , op) && +cmask_op2_is_pred (op)) +return true; + +return cmask_word_op2 (&a_bits[hi_word - a_word_off], + &b_bits[hi_word - b_word_off], tail_mask, op); +} + +enum cmask_op1 { +CMASK_OP1_ANY_SET , +}; + +static __always_inline bool cmask_word_op1(const u64 *ap, u64 mask, +const enum cmask_op1 op) +{ +switch (op) { +case CMASK_OP1_ANY_SET : +return *ap & mask; + } +unreachable (); +} + +/* +* Walk [@a_base, @a_base + @a_nr_cids) of @a_bits word by word, applying @op. +* Returns true on the first word whose per-word test is true; returns false if +* no word matches or the range is empty. All current op1s short-circuit on +* per-word true; if a non-predicate op1 lands here, add a cmask_op1_is_pred() +* guard analogous to cmask_op2_is_pred(). +*/ +static __always_inline bool cmask_walk_op1(const u64 *a_bits, u32 a_base, +u32 a_nr_cids, +const enum cmask_op1 op) +{ +u32 lo = a_base; +u32 hi = a_base + a_nr_cids; +u32 a_word_off = a_base /64 ; +u32 lo_word = lo /64 ; +u32 hi_word = (hi -1 ) /64 ; +u64 head_mask =GENMASK_U64 (63 , lo &63 ); +u64 tail_mask =GENMASK_U64 ((hi -1 ) &63 ,0 ); +u32 w; + +if (lo >= hi) +return false; + +if (lo_word == hi_word) +return cmask_word_op1 (&a_bits[lo_word - a_word_off], + head_mask & tail_mask, op); + +if (cmask_word_op1 (&a_bits[lo_word - a_word_off], head_mask, op)) +return true; +for (w = lo_word +1 ; w < hi_word; w++) +if (cmask_word_op1 (&a_bits[w - a_word_off], ~0ULL , op)) +return true; +return cmask_word_op1 (&a_bits[hi_word - a_word_off], tail_mask, op); +} + +void scx_cmask_and (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_AND ); +} + +void scx_cmask_or (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_OR ); +} + +/** +* scx_cmask_or_racy - OR @src into @dst, reading @src without locking +* +* @src is read word-by-word through data_race(). Same per-bit independence +* rationale as scx_cmask_copy_racy(). Memory ordering with writers is the +* caller's responsibility. +*/ +void scx_cmask_or_racy (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_OR_RACY ); +} + +void scx_cmask_copy (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_COPY ); +} + +/** +* scx_cmask_copy_racy - Snapshot @src into @dst without locking +* +* @src is read word-by-word through data_race(). Head/tail masking matches +* scx_cmask_copy(). Each bit in a cmask is independent, so partial updates +* just leave some bits fresher than others. Memory ordering with writers is +* the caller's responsibility. +*/ +void scx_cmask_copy_racy (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_COPY_RACY ); +} + +void scx_cmask_andnot (struct scx_cmask *dst,const struct scx_cmask *src) +{ +cmask_walk_op2 (dst->bits, dst->base, dst->nr_cids, + src->bits, src->base, src->nr_cids,CMASK_OP2_ANDNOT ); +} + +/* +* Return true if @cm has any bit set in [@lo, @hi). Caller must ensure +* [@lo, @hi) is contained in @cm's range. +*/ +static bool cmask_any_set_in_range (const struct scx_cmask *cm,u32 lo,u32 hi) +{ +if (lo >= hi) +return false; +return cmask_walk_op1 (&cm->bits[lo /64 - cm->base /64 ], lo, hi - lo, +CMASK_OP1_ANY_SET ); +} + +/** +* scx_cmask_subset - test whether @sub is a subset of @super +* @sub: cmask to test +* @super: cmask to test against +* +* Return true iff every set bit of @sub is also set in @super. +*/ +bool scx_cmask_subset (const struct scx_cmask *sub,const struct scx_cmask *super) +{ +u32 super_end = super->base + super->nr_cids; +u32 sub_end = sub->base + sub->nr_cids; + +/* +* Set bits in @sub outside @super's range can't be in @super, so any +* such bit means not a subset. The walk below only visits words +* common to both ranges, so these need a separate scan. +*/ +if (sub->base < super->base && +cmask_any_set_in_range (sub, sub->base,min (super->base, sub_end))) +return false; +if (sub_end > super_end && +cmask_any_set_in_range (sub,max (sub->base, super_end), sub_end)) +return false; + +return !cmask_walk_op2 ((u64 *)super->bits, super->base, super->nr_cids, + sub->bits, sub->base, sub->nr_cids,CMASK_OP2_SUBSET ); +} + +bool scx_cmask_intersects (const struct scx_cmask *a,const struct scx_cmask *b) +{ +return cmask_walk_op2 ((u64 *)a->bits, a->base, a->nr_cids, + b->bits, b->base, b->nr_cids,CMASK_OP2_INTERSECTS ); +} +/** * scx_bpf_cid_topo - Copy out per-cid topology info * @cid: cid to look up
kernel/sched/ext_cid.h +8 -0
@@ -53,6 +53,14 @@ extern struct btf_id_set8 scx_kfunc_ids_init;void scx_cmask_clear (struct scx_cmask *m);void scx_cmask_fill (struct scx_cmask *m); +void scx_cmask_and (struct scx_cmask *dst,const struct scx_cmask *src); +void scx_cmask_or (struct scx_cmask *dst,const struct scx_cmask *src); +void scx_cmask_or_racy (struct scx_cmask *dst,const struct scx_cmask *src); +void scx_cmask_copy (struct scx_cmask *dst,const struct scx_cmask *src); +void scx_cmask_copy_racy (struct scx_cmask *dst,const struct scx_cmask *src); +void scx_cmask_andnot (struct scx_cmask *dst,const struct scx_cmask *src); +bool scx_cmask_subset (const struct scx_cmask *sub,const struct scx_cmask *super); +bool scx_cmask_intersects (const struct scx_cmask *a,const struct scx_cmask *b);s32 scx_cid_init (struct scx_sched *sch);int scx_cid_kfunc_init (void );void scx_cpumask_to_cmask (const struct cpumask *src,struct scx_cmask *dst);
Signature · 1 line
2.54.0
Tejun Heo
reviewerSorry, please ignore. This went out with the wrong head message.
Thanks.
Signature · 1 line
tejun