Re: [PATCH v4 sched_ext/for-7.3 03/40] tools/sched_ext: scx - Fix cmask_subset(), cmask_equal() and cmask_weight()

[Andrea Righi <arighi@nvidia.com>]

On Wed, Jul 08, 2026 at 11:23:52AM -1000, Tejun Heo wrote:
> cmask_equal(), cmask_weight() and cmask_subset() bounded their word walks
> with CMASK_NR_WORDS(nr_cids), which pads by one word and can't tell the last
> word in use without @base. The walks could thus cover a slack word past the
> active range, which cmask_reframe() leaves non-zero: a stale bit there gave
> cmask_equal() a spurious mismatch, cmask_weight() an inflated count, and
> cmask_subset() a spurious violation. cmask_subset() could also read
> @b->bits[] one word past its allocation (within the arena's fault-recovered
> range, so harmless), and deviated from the kernel scx_cmask_subset() by
> failing any @a range that doesn't nest inside @b's even when the overhanging
> bits are all clear.
> 
> Bound the cmask_equal() and cmask_weight() walks by the words the range
> actually spans, with early returns for empty ranges. Rewrite cmask_subset()
> to match the kernel semantics: scan @a's overhangs for set bits with
> cmask_next_set() and walk the words of the range intersection.
> cmask_subset() moves below cmask_next_set(), which it now uses. Padding bits
> don't need masking as every cmask helper keeps them clear.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>

Reviewed-by: Andrea Righi <arighi@nvidia.com>

Thanks,
-Andrea

> ---
>  tools/sched_ext/include/scx/cid.bpf.h | 88 +++++++++++++++++----------
>  1 file changed, 55 insertions(+), 33 deletions(-)
> 
> diff --git a/tools/sched_ext/include/scx/cid.bpf.h b/tools/sched_ext/include/scx/cid.bpf.h
> index db247e42fb45..6b0b4e41b288 100644
> --- a/tools/sched_ext/include/scx/cid.bpf.h
> +++ b/tools/sched_ext/include/scx/cid.bpf.h
> @@ -391,7 +391,9 @@ static __always_inline bool cmask_equal(const struct scx_cmask __arena *a,
>  
>  	if (a->base != b->base || a->nr_cids != b->nr_cids)
>  		return false;
> -	nr_words = CMASK_NR_WORDS(a->nr_cids);
> +	if (a->nr_cids == 0)
> +		return true;
> +	nr_words = (a->base + a->nr_cids - 1) / 64 - a->base / 64 + 1;
>  
>  	bpf_for(i, 0, CMASK_MAX_WORDS) {
>  		if (i >= nr_words)
> @@ -402,36 +404,6 @@ static __always_inline bool cmask_equal(const struct scx_cmask __arena *a,
>  	return true;
>  }
>  
> -/*
> - * True iff every bit set in @a is also set in @b over the intersection of
> - * their ranges. Bits of @a outside @b's range fail the test.
> - */
> -static __always_inline bool cmask_subset(const struct scx_cmask __arena *a,
> -					 const struct scx_cmask __arena *b)
> -{
> -	u32 a_end = a->base + a->nr_cids;
> -	u32 b_end = b->base + b->nr_cids;
> -	u32 a_wbase = a->base / 64;
> -	u32 b_wbase = b->base / 64;
> -	u32 nr_words, i;
> -
> -	/* any bit of @a outside @b's range is a subset violation */
> -	if (a->base < b->base || a_end > b_end)
> -		return false;
> -
> -	nr_words = CMASK_NR_WORDS(a->nr_cids);
> -	bpf_for(i, 0, CMASK_MAX_WORDS) {
> -		u32 wi_b;
> -
> -		if (i >= nr_words)
> -			break;
> -		wi_b = a_wbase + i - b_wbase;
> -		if (a->bits[i] & ~b->bits[wi_b])
> -			return false;
> -	}
> -	return true;
> -}
> -
>  /**
>   * cmask_next_set - find the first set bit at or after @cid
>   * @m: cmask to search
> @@ -488,16 +460,66 @@ static __always_inline u32 cmask_first_set(const struct scx_cmask __arena *m)
>  	     (cid) < (m)->base + (m)->nr_cids;					\
>  	     (cid) = cmask_next_set((m), (cid) + 1))
>  
> +/*
> + * True iff every bit set in @a is also set in @b. Matches the kernel-side
> + * scx_cmask_subset(): ranges don't need to nest, and set bits of @a outside
> + * @b's range fail the test.
> + */
> +static __always_inline bool cmask_subset(const struct scx_cmask __arena *a,
> +					 const struct scx_cmask __arena *b)
> +{
> +	u32 a_end = a->base + a->nr_cids;
> +	u32 b_end = b->base + b->nr_cids;
> +	u32 a_wbase = a->base / 64;
> +	u32 b_wbase = b->base / 64;
> +	u32 lo = a->base > b->base ? a->base : b->base;
> +	u32 hi = a_end < b_end ? a_end : b_end;
> +	u32 lo_word, hi_word, i;
> +
> +	/* set bits of @a outside @b's range can't be in @b */
> +	if (a->base < b->base &&
> +	    cmask_next_set(a, a->base) < (b->base < a_end ? b->base : a_end))
> +		return false;
> +	if (a_end > b_end &&
> +	    cmask_next_set(a, a->base > b_end ? a->base : b_end) < a_end)
> +		return false;
> +
> +	if (lo >= hi)
> +		return true;
> +
> +	/*
> +	 * Walk the words the range intersection spans. Plain word tests
> +	 * suffice: the scans above guarantee @a has no set bit outside @b's
> +	 * range and padding bits are kept clear by all cmask helpers.
> +	 */
> +	lo_word = lo / 64;
> +	hi_word = (hi - 1) / 64;
> +
> +	bpf_for(i, 0, CMASK_MAX_WORDS) {
> +		u32 w = lo_word + i;
> +
> +		if (w > hi_word)
> +			break;
> +		if (a->bits[w - a_wbase] & ~b->bits[w - b_wbase])
> +			return false;
> +	}
> +	return true;
> +}
> +
>  /*
>   * Population count over [base, base + nr_cids). Padding bits in the head/tail
>   * words are guaranteed zero by the mutating helpers, so a flat popcount over
> - * all words is correct.
> + * the words the range spans is correct.
>   */
>  static __always_inline u32 cmask_weight(const struct scx_cmask __arena *m)
>  {
> -	u32 nr_words = CMASK_NR_WORDS(m->nr_cids), i;
> +	u32 nr_words, i;
>  	u32 count = 0;
>  
> +	if (!m->nr_cids)
> +		return 0;
> +	nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1;
> +
>  	bpf_for(i, 0, CMASK_MAX_WORDS) {
>  		if (i >= nr_words)
>  			break;
> -- 
> 2.54.0
>