Re: [PATCH RESEND bpf-next v3 4/6] selftests/bpf: Add arena-based bitmap data structure

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [High] Silent failures and falsely reported lock acquisition in bounded atomic bit operations on loop abort.
- [High] `bmp_empty` and `bmp_subset` return `true` on an aborted loop, defaulting to an unsafe affirmative state.
- [Medium] Bulk operations unconditionally apply a bitmask to the last word even if the processing loop aborts early.
- [Medium] Missing `READ_ONCE()` or `volatile` cast in `bmp_test_bit` exposes lockless polling loops to compiler hoisting.
--

commit 634ac04142cf736158c99f577c0f903470937bfc
Author: Emil Tsalapatis <emil@etsalapatis.com>
selftests/bpf: Add arena-based bitmap data structure

This patch adds an arena-based word-aligned bitmap data structure. The
structure is useful as a building block for components like sched-ext
to represent cpumask structures.

> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> index 0000000000000..80e814401fb9e
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
[ ... ]
> +__weak
> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit);
> +}

[Severity: Medium]
Does this memory access need a READ_ONCE() or a volatile pointer cast?

If this function is used in a lockless concurrent polling loop, could the
compiler hoist the plain memory read out of the loop and cause an infinite
spin that misses updates from other CPUs?

[ ... ]
> +__weak
> +bool bmp_test_and_set_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	u64 val = BIT_MASK(bit);
> +	u32 idx = BIT_WORD(bit);
> +	u64 old, new, actual;
> +
> +	do {
> +		old = bmp->bits[idx];
> +
> +		if ((old & val))
> +			return true;
> +
> +		new = old | val;
> +		actual = cmpxchg(&bmp->bits[idx], old, new);
> +
> +		if (actual == old)
> +			return false;
> +
> +	} while (can_loop);
> +
> +	return false;
> +}

[Severity: High]
If the can_loop constraint is exhausted under heavy contention, this loop
will fall through and return false.

In test_and_set semantics, returning false usually means the bit was
previously 0 and is now successfully set to 1. Could this act as a false
lock acquisition and allow multiple threads to enter a critical section
simultaneously?

[ ... ]
> +__weak
> +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	u64 val = BIT_MASK(bit);
> +	u32 idx = BIT_WORD(bit);
> +	u64 old, new, actual;
> +
> +	do {
> +		old = bmp->bits[idx];
> +		new = old | val;
> +		actual = cmpxchg(&bmp->bits[idx], old, new);
> +
> +	} while (actual != old && can_loop);
> +}

[Severity: High]
If the loop aborts early due to can_loop being exhausted, does this fail
silently without successfully setting the bit?

[ ... ]
> +__weak
> +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2)
> +{
> +	size_t nwords = BITS_TO_LONG_LONGS(bits);
> +	volatile u32 i;
> +
> +	for (i = zero; i < nwords && can_loop; i++)
> +		dst->bits[i] = src1->bits[i] & src2->bits[i];
> +
> +	if (nwords && bits % BITS_PER_LONG_LONG)
> +		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
> +}

[Severity: Medium]
If the loop is aborted early by the can_loop constraint, will this bitmask
logic unconditionally apply to potentially uninitialized or stale data in the
dst->bits array?

Could this corrupt data structures relying on the array?

> +__weak
> +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2)
> +{
> +	size_t nwords = BITS_TO_LONG_LONGS(bits);
> +	volatile u32 i;
> +
> +	for (i = zero; i < nwords && can_loop; i++)
> +		dst->bits[i] = src1->bits[i] | src2->bits[i];
> +
> +	if (nwords && bits % BITS_PER_LONG_LONG)
> +		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
> +}

[Severity: Medium]
Similar to bmp_and, could this mask uninitialized memory if the loop aborted
early?

> +__weak
> +bool bmp_empty(size_t bits, struct bitmap __arena *bmp)
> +{
> +	size_t nwords = BITS_TO_LONG_LONGS(bits);
> +	volatile u32 i;
> +
> +	for (i = zero; i < nwords && can_loop; i++) {
> +		u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL;
> +
> +		if (bmp->bits[i] & mask)
> +			return false;
> +	}
> +
> +	return true;
> +}

[Severity: High]
If the can_loop limit is reached on a large bitmap before a mismatch is found,
this will fall through and return true.

Could this partially checked bitmap bypass resource accounting or access
control checks by falsely reporting an empty state?

> +__weak
> +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src)
> +{
> +	size_t nwords = BITS_TO_LONG_LONGS(bits);
> +	volatile u32 i;
> +
> +	for (i = zero; i < nwords && can_loop; i++)
> +		dst->bits[i] = src->bits[i];
> +
> +	if (nwords && bits % BITS_PER_LONG_LONG)
> +		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
> +}

[Severity: Medium]
Could this mask uninitialized memory if the loop aborted early?

> +__weak
> +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small)
> +{
> +	size_t nwords = BITS_TO_LONG_LONGS(bits);
> +	volatile u32 i;
> +
> +	for (i = zero; i < nwords && can_loop; i++) {
> +		u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL;
> +
> +		if (~big->bits[i] & small->bits[i] & mask)
> +			return false;
> +	}
> +
> +	return true;
> +}

[Severity: High]
Similar to bmp_empty, if the loop is aborted early, this returns true.
Could this falsely report a strict subset and lead to a fail-open condition?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260706181730.21731-1-emil@etsalapatis.com?part=4