selftests/bpf: libarena cleanup and bitmap struct
Subsystems (3)
Emil Tsalapatis
reviewercover selftests/bpf: libarena cleanup and bitmap struct
Cleanup patches for libarena, along with a new bitmap data type that is in use by sched-ext. Patch 1 is an NFC that properly renames the buddy selftests for consistency. Patch 2 fixes the zero variable used in libarena for can_loop based looping, and afterwrds removes all bpf_for() instances from the code. Patch 3 fixes an (untriggered) edge case that could cause spurious selftest failures. Finally, patches 4 and 5 introduce the bitmap data structure along with selftests.
Emil Tsalapatis (5):
libarena/selftests: Replace leftover st_ prefix with test_ selftests/bpf: libarena: Fix can-loop zero variable definition selftests/bpf: libarena: Clean up allocation state before buddy tests selftests/bpf: Add arena-based bitmap data structure selftests/bpf: libarena: Add bitmap selftets
.../bpf/libarena/include/libarena/bitmap.h | 31 ++
.../bpf/libarena/include/libarena/common.h | 2 +-
...asan_buddy.bpf.c => test_asan_buddy.bpf.c} | 10 +-
.../{st_asan_common.h => test_asan_common.h} | 0
.../bpf/libarena/selftests/test_bitmap.bpf.c | 314 ++++++++++++++++++
.../{st_buddy.bpf.c => test_buddy.bpf.c} | 8 +-
.../selftests/test_parallel_spmc.bpf.c | 9 +-
.../selftests/bpf/libarena/src/bitmap.bpf.c | 191 +++++++++++
.../selftests/bpf/libarena/src/common.bpf.c | 9 +-
.../selftests/bpf/prog_tests/libarena.c | 8 +-
.../selftests/bpf/prog_tests/libarena_asan.c | 8 +-
11 files changed, 573 insertions(+), 17 deletions(-)
create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} (98%)
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_common.h => test_asan_common.h} (100%)
create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
rename tools/testing/selftests/bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} (97%)
create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.cSignature · 1 line
2.54.0
Emil Tsalapatis
reviewerPATCH 1/5 libarena/selftests: Replace leftover st_ prefix with test_
---
.../selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} | 2 +-
.../libarena/selftests/{st_asan_common.h => test_asan_common.h} | 0
.../bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} | 0
3 files changed, 1 insertion(+), 1 deletion(-)
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} (99%)
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_common.h => test_asan_common.h} (100%)
rename tools/testing/selftests/bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} (100%)tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c +1 -1
@@ -12,7 +12,7 @@ extern struct buddy __arena buddy;#ifdef BPF_ARENA_ASAN -#include "st_asan_common.h" +#include "test_asan_common.h" static __always_inline int asan_test_buddy_oob_single(size_t alloc_size) {
tools/testing/selftests/bpf/libarena/selftests/test_asan_common.h renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_common.h +0 -0
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_buddy.bpf.c +0 -0
Signature · 1 line
2.54.0
Re: [PATCH bpf-next 1/5] libarena/selftests: Replace leftover st_ prefix with test_
Quoted 8 lines · Emil Tsalapatis
---
.../selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} | 2 +-
.../libarena/selftests/{st_asan_common.h => test_asan_common.h} | 0
.../bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} | 0
3 files changed, 1 insertion(+), 1 deletion(-)
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} (99%)
rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_common.h => test_asan_common.h} (100%)
rename tools/testing/selftests/bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} (100%)nit: An empty commit message is weird.
The short message is self-explanatory here, but still... Maybe a brief comment on *why* this is done?
Quoted 25 lines
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c +1
-1@@ -12,7 +12,7 @@ extern struct buddy __arena buddy;#ifdef BPF_ARENA_ASAN -#include "st_asan_common.h" +#include "test_asan_common.h" static __always_inline int asan_test_buddy_oob_single(size_t alloc_size) {tools/testing/selftests/bpf/libarena/selftests/test_asan_common.h renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_common.h +0
-0tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_buddy.bpf.c +0
-0
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 1/5] libarena/selftests: Replace leftover st_ prefix with test_
Quoted 10 lines · Ihor Solodrai
Quoted 8 lines · Emil Tsalapatis
--- .../selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} | 2 +- .../libarena/selftests/{st_asan_common.h => test_asan_common.h} | 0 .../bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} | 0 3 files changed, 1 insertion(+), 1 deletion(-) rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_buddy.bpf.c => test_asan_buddy.bpf.c} (99%) rename tools/testing/selftests/bpf/libarena/selftests/{st_asan_common.h => test_asan_common.h} (100%) rename tools/testing/selftests/bpf/libarena/selftests/{st_buddy.bpf.c => test_buddy.bpf.c} (100%)
Quoted 5 lines
Acked-by Ihor Solodrai <[email protected]>nit: An empty commit message is weird.
The short message is self-explanatory here, but still... Maybe a brief comment on *why* this is done?
Ack, I must have a forgotten it... It's a cosmetic change to make it more obvious what the test is.
Quoted 26 lines
Quoted 26 lines
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c +1
-1@@ -12,7 +12,7 @@ extern struct buddy __arena buddy;#ifdef BPF_ARENA_ASAN -#include "st_asan_common.h" +#include "test_asan_common.h" static __always_inline int asan_test_buddy_oob_single(size_t alloc_size) {tools/testing/selftests/bpf/libarena/selftests/test_asan_common.h renamed from tools/testing/selftests/bpf/libarena/selftests/st_asan_common.h +0
-0tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c renamed from tools/testing/selftests/bpf/libarena/selftests/st_buddy.bpf.c +0
-0
Emil Tsalapatis
reviewerPATCH 2/5 selftests/bpf: libarena: Fix can-loop zero variable definition
In reply to Emil TsalapatisBPF can_loop based loops require the index variable to stay imprecise. This means we must initialize them from a currently imprecise variable instead of directly assigning 0 to them, like so:
static volatile u32 zero = 0;
for (i = zero; i < NUM_LOOPS; i++) {
/* loop body */
}The libarena implementation of this technique is currently faulty. For the technique to work, the variable must not be in a map. This includes the .rodata DATASEC map used for const variables. However, libarena still defines the zero variable as constant.
Modify the zero variable definition into a volatile variable. This change adds a complication caused by the compiler optimizing array derefences from
for (i = zero; i < NUM_LOOPS; i++) {
val = *(ptr + i);
}into
for (i = zero; i < NUM_LOOPS; i++) {
val = *ptr++;
}and causing verification failures. Use the barrier_var() clobber macro to prevent this optimization from taking place. After that, remove the bpf_for() invocations introduced in libarena for parallel spmc testing.
--- .../selftests/bpf/libarena/include/libarena/common.h | 2 +- .../bpf/libarena/selftests/test_asan_buddy.bpf.c | 8 ++++++-- .../selftests/bpf/libarena/selftests/test_buddy.bpf.c | 8 ++++++-- .../bpf/libarena/selftests/test_parallel_spmc.bpf.c | 9 ++++----- tools/testing/selftests/bpf/libarena/src/common.bpf.c | 3 +-- 5 files changed, 18 insertions(+), 12 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/common.h +1 -1
@@ -43,7 +43,7 @@ struct {* imprecise. To force the variable to be imprecise, initialize it with * the opaque volatile variable 0 instead of the constant 0. */ -extern const volatile u32 zero; +volatile u32 zero__weak ;extern volatile u64 asan_violated;int arena_fls (__u64 word);
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c +6 -2
@@ -154,7 +154,8 @@ __weak int asan_test_buddy_oob(void)size_t sizes[] = {7 ,8 ,17 ,18 ,64 ,256 ,317 ,512 ,1024 , }; -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret) {
@@ -163,6 +164,7 @@ __weak int asan_test_buddy_oob(void) }for (i = zero; i <sizeof (sizes) /sizeof (sizes[0 ]) && can_loop; i++) { +barrier_var (i); ret =asan_test_buddy_oob_single (sizes[i]);if (ret) { arena_stdout("%s:%d Failed for size %lu", __func__,
@@ -190,7 +192,8 @@ __stderr("Call trace:\n"__weak int asan_test_buddy_uaf (void ) {size_t sizes[] = {16 ,32 ,64 ,128 ,256 ,512 ,1024 ,16384 }; -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret) {
@@ -199,6 +202,7 @@ __weak int asan_test_buddy_uaf(void) }for (i = zero; i <sizeof (sizes) /sizeof (sizes[0 ]) && can_loop; i++) { +barrier_var (i); ret =asan_test_buddy_uaf_single (sizes[i]);if (ret) { arena_stdout("%s:%d Failed for size %lu", __func__,
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +6 -2
@@ -171,7 +171,8 @@ __weak int test_buddy_alloc_multiple(void) SEC("syscall")__weak int test_buddy_alignment (void ) { -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret)
@@ -179,6 +180,7 @@ __weak int test_buddy_alignment(void)/* Allocate various sizes and check alignment */ for (i = zero; i <17 && can_loop; i++) { +barrier_var (i); ptrs[i] =buddy_alloc (&buddy, alignment_sizes[i]);if (!ptrs[i]) { arena_stdout("alignment test: alloc failed for size %lu",
@@ -198,8 +200,10 @@ __weak int test_buddy_alignment(void) }/* Free all allocations */ -for (i = zero; i <17 && can_loop; i++) +for (i = zero; i <17 && can_loop; i++) { +barrier_var (i);buddy_free (&buddy, ptrs[i]); + }buddy_destroy (&buddy);
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c +4 -5
@@ -155,7 +155,7 @@ int spmc_quiesce_on_owner(u64 epoch) {u64 i; - bpf_for(i, 0, TEST_SPMC_SYNC_SPINS) { +for (i = zero; i <TEST_SPMC_SYNC_SPINS && can_loop; i++) {if (test_abort)return -EINTR ;if (smp_load_acquire (&owner_epoch) >= epoch)
@@ -175,8 +175,7 @@ int spmc_quiesce_on_stealer(u64 epoch)int err = -ETIMEDOUT ; target =STEALER_EPOCH (epoch); - bpf_for(i, 0, TEST_SPMC_SYNC_SPINS) { - +for (i = zero; i <TEST_SPMC_SYNC_SPINS && can_loop; i++) {if (test_abort) { err = -EINTR ;break ;
@@ -391,7 +390,7 @@ int spmc_wait_for_stealers_to_start(u64 target) {u64 i; - bpf_for(i, 0, TEST_SPMC_SYNC_SPINS) { +for (i = zero; i <TEST_SPMC_SYNC_SPINS && can_loop; i++) {if (test_abort)return -EINTR ;if (READ_ONCE (stealers_started) >= target)
@@ -537,7 +536,7 @@ static int spmc_wait_for_round_steals(u64 target)arena_subprog_init (); - bpf_for(i, 0, TEST_SPMC_SYNC_SPINS) { +for (i = zero; i <TEST_SPMC_SYNC_SPINS && can_loop; i++) {if (test_abort)return -EINTR ;if (round_steals >= target)
tools/testing/selftests/bpf/libarena/src/common.bpf.c +1 -2
@@ -4,9 +4,8 @@#include <libarena/asan.h> #include <libarena/buddy.h> -const volatile u32 zero =0 ; - struct buddy __arena buddy; +volatile u32 zero =0 ;int arena_fls (__u64 word) {
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] Missing `barrier_var()` clobber in open-coded loops allows compiler Loop Strength Reduction…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Missing barrier_var() clobber in open-coded loops allows compiler Loop Strength Reduction, leading to verifier failures. --
commit 3447132bcf1b724653f0483db116e1292c49b493
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: libarena: Fix can-loop zero variable definition
This patch modifies the zero variable to be a regular volatile instead of a const volatile, ensuring it remains imprecise in BPF can_loop constructs. Because this change can cause the compiler to optimize array accesses into pointer increments (which breaks verification), barrier_var() is added to several loops.
Quoted 4 lines
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +0
-0
[ ... ]
Quoted 11 lines
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +2
-1@@ -171,7 +171,8 @@ __weak int test_buddy_alignment(void) SEC("syscall")__weak int test_buddy_alignment (void ) { -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret)
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c __weak int test_buddy_alignment(void) · line 184
Quoted 5 lines
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +1
-0@@ -179,6 +180,7 @@ __weak int test_buddy_alignment(void)/* Allocate various sizes and check alignment */ for (i = zero; i <17 && can_loop; i++) { +barrier_var (i); ptrs[i] =buddy_alloc (&buddy, alignment_sizes[i]);
[Severity: Medium]
The commit message notes that modifying the zero variable definition requires using barrier_var() to prevent the compiler from optimizing array dereferences into pointer increments, which causes verification failures.
Since zero is now globally volatile, do we need to add barrier_var() to other loops that use zero for array dereferences to prevent loop strength reduction?
For instance, in test_buddy.bpf.c:test_buddy_alloc_multiple():
for (j = zero; j < sz && can_loop; j++) {
mem[j] = poison;
}And the outer loop in the same function:
for (i = zero; i < SEGARRLEN && can_loop; i++) {
sz = alloc_multiple_sizes[i % 9];
...
segarr[i].block = mem;
}Similar tight loops exist in other files, such as spmc_common_init() in test_parallel_spmc.bpf.c:
for (i = zero; i < TEST_SPMC_MAX_VALUES && can_loop; i++)
seen[i] = 0;And asan_test_buddy_oob_single() in test_asan_buddy.bpf.c:
for (i = zero; i < alloc_size && can_loop; i++) {
mem[i] = 0xba;
}Will these un-barriered loops also suffer from the same verification failures?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Re: [PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition
In reply to Emil TsalapatisQuoted 29 lines · Emil Tsalapatis
BPF
can_loopbased loops require the index variable to stay imprecise. This means we must initialize them from a currently imprecise variable instead of directly assigning 0 to them, like so:static volatile u32 zero = 0;
for (i = zero; i < NUM_LOOPS; i++) { /* loop body */ }The libarena implementation of this technique is currently faulty. For the technique to work, the variable must not be in a map. This includes the .rodata DATASEC map used for const variables. However, libarena still defines the zero variable as constant.
Modify the zero variable definition into a volatile variable. This change adds a complication caused by the compiler optimizing array derefences from
for (i = zero; i < NUM_LOOPS; i++) { val = *(ptr + i); }into
for (i = zero; i < NUM_LOOPS; i++) { val = *ptr++; }
Quoted 7 lines
and causing verification failures. Use the
barrier_var()clobber macro to prevent this optimization from taking place. After that, remove thebpf_for()invocations introduced in libarena for parallel spmc testing.Reported-by Eduard Zingerman <[email protected]>Signed-off-by Emil Tsalapatis <[email protected]>---
[...]
Ihor Solodrai
reviewerRe: [PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition
In reply to Emil TsalapatisQuoted 71 lines · Emil Tsalapatis
BPF
can_loopbased loops require the index variable to stay imprecise. This means we must initialize them from a currently imprecise variable instead of directly assigning 0 to them, like so:static volatile u32 zero = 0;
for (i = zero; i < NUM_LOOPS; i++) { /* loop body */ }The libarena implementation of this technique is currently faulty. For the technique to work, the variable must not be in a map. This includes the .rodata DATASEC map used for const variables. However, libarena still defines the zero variable as constant.
Modify the zero variable definition into a volatile variable. This change adds a complication caused by the compiler optimizing array derefences from
for (i = zero; i < NUM_LOOPS; i++) { val = *(ptr + i); }into
for (i = zero; i < NUM_LOOPS; i++) { val = *ptr++; }and causing verification failures. Use the
barrier_var()clobber macro to prevent this optimization from taking place. After that, remove thebpf_for()invocations introduced in libarena for parallel spmc testing.Reported-by Eduard Zingerman <[email protected]>Signed-off-by Emil Tsalapatis <[email protected]>--- .../selftests/bpf/libarena/include/libarena/common.h | 2 +- .../bpf/libarena/selftests/test_asan_buddy.bpf.c | 8 ++++++-- .../selftests/bpf/libarena/selftests/test_buddy.bpf.c | 8 ++++++-- .../bpf/libarena/selftests/test_parallel_spmc.bpf.c | 9 ++++----- tools/testing/selftests/bpf/libarena/src/common.bpf.c | 3 +-- 5 files changed, 18 insertions(+), 12 deletions(-)tools/testing/selftests/bpf/libarena/include/libarena/common.h +1
-1@@ -43,7 +43,7 @@ struct {* imprecise. To force the variable to be imprecise, initialize it with * the opaque volatile variable 0 instead of the constant 0. */ -extern const volatile u32 zero; +volatile u32 zero__weak ;extern volatile u64 asan_violated;int arena_fls (__u64 word);tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c +2
-1@@ -154,7 +154,8 @@ __weak int asan_test_buddy_oob(void)size_t sizes[] = {7 ,8 ,17 ,18 ,64 ,256 ,317 ,512 ,1024 , }; -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret) {
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c __weak int asan_test_buddy_oob(void) · line 167
Quoted 4 lines
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c +1
-0@@ -163,6 +164,7 @@ __weak int asan_test_buddy_oob(void) }for (i = zero; i <sizeof (sizes) /sizeof (sizes[0 ]) && can_loop; i++) { +barrier_var (i);
Looks like we are using two different idioms for keeping indices imprecise and blocking the compiler optimization: the barrier_var(i) like here, and volatile u32 i declaration in patches #4 and #5.
My understanding is the barrier is generally better performance-wise, since volatile var would be re-loaded every time.
Does it make sense to converge on a single pattern (at least in the context of libarena)?
Quoted 1 line
[...]
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition
Quoted 81 lines · Ihor Solodrai
Quoted 71 lines · Emil Tsalapatis
BPF
can_loopbased loops require the index variable to stay imprecise. This means we must initialize them from a currently imprecise variable instead of directly assigning 0 to them, like so:static volatile u32 zero = 0;
for (i = zero; i < NUM_LOOPS; i++) { /* loop body */ }The libarena implementation of this technique is currently faulty. For the technique to work, the variable must not be in a map. This includes the .rodata DATASEC map used for const variables. However, libarena still defines the zero variable as constant.
Modify the zero variable definition into a volatile variable. This change adds a complication caused by the compiler optimizing array derefences from
for (i = zero; i < NUM_LOOPS; i++) { val = *(ptr + i); }into
for (i = zero; i < NUM_LOOPS; i++) { val = *ptr++; }and causing verification failures. Use the
barrier_var()clobber macro to prevent this optimization from taking place. After that, remove thebpf_for()invocations introduced in libarena for parallel spmc testing.Reported-by Eduard Zingerman <[email protected]>Signed-off-by Emil Tsalapatis <[email protected]>--- .../selftests/bpf/libarena/include/libarena/common.h | 2 +- .../bpf/libarena/selftests/test_asan_buddy.bpf.c | 8 ++++++-- .../selftests/bpf/libarena/selftests/test_buddy.bpf.c | 8 ++++++-- .../bpf/libarena/selftests/test_parallel_spmc.bpf.c | 9 ++++----- tools/testing/selftests/bpf/libarena/src/common.bpf.c | 3 +-- 5 files changed, 18 insertions(+), 12 deletions(-)tools/testing/selftests/bpf/libarena/include/libarena/common.h +1
-1@@ -43,7 +43,7 @@ struct {* imprecise. To force the variable to be imprecise, initialize it with * the opaque volatile variable 0 instead of the constant 0. */ -extern const volatile u32 zero; +volatile u32 zero__weak ;extern volatile u64 asan_violated;int arena_fls (__u64 word);tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c +2
-1@@ -154,7 +154,8 @@ __weak int asan_test_buddy_oob(void)size_t sizes[] = {7 ,8 ,17 ,18 ,64 ,256 ,317 ,512 ,1024 , }; -int ret, i; +int ret; +u32 i; ret =buddy_init (&buddy);if (ret) {tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c __weak int asan_test_buddy_oob(void) · line 167
Quoted 4 lines
tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c +1
-0@@ -163,6 +164,7 @@ __weak int asan_test_buddy_oob(void) }for (i = zero; i <sizeof (sizes) /sizeof (sizes[0 ]) && can_loop; i++) { +barrier_var (i);Looks like we are using two different idioms for keeping indices imprecise and blocking the compiler optimization: the
barrier_var(i)like here, andvolatile u32 ideclaration in patches #4 and #5.
Quoted 6 lines
My understanding is the barrier is generally better performance-wise, since volatile var would be re-loaded every time.
Does it make sense to converge on a single pattern (at least in the context of libarena)?
I'm not sure we need to completely standardize because each idiom has its uses, but I do like the idea of mostly using one of the two patterns. I will try using volatile here to see if it prevents the loop optimizations and will update it next version if it works.
Quoted 2 lines
Quoted 2 lines
[...]
Emil Tsalapatis
reviewerPATCH 3/5 selftests/bpf: libarena: Clean up allocation state before buddy tests
In reply to Emil TsalapatisSummary: The buddy allocator requires the global BPF buddy allocator to not be already initialized. However, the test currently merely resets the allocator before the buddy tests instead of destroying it, and the test worked because the buddy test happened to run first. Properly destroy the allocator instead of resetting it.
--- tools/testing/selftests/bpf/libarena/src/common.bpf.c | 6 ++++++ tools/testing/selftests/bpf/prog_tests/libarena.c | 8 ++++++-- tools/testing/selftests/bpf/prog_tests/libarena_asan.c | 8 ++++++-- 3 files changed, 18 insertions(+), 4 deletions(-)
tools/testing/selftests/bpf/libarena/src/common.bpf.c +6 -0
@@ -37,6 +37,12 @@ __weak int arena_buddy_reset(void)return buddy_init (&buddy); } +SEC("syscall") +__weak int arena_buddy_destroy (void ) +{ +return buddy_destroy (&buddy); +} + __weak void __arena *arena_malloc(size_t size) {return buddy_alloc (&buddy, size);
tools/testing/selftests/bpf/prog_tests/libarena.c +6 -2
@@ -15,7 +15,12 @@ static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, {int ret; -if (!strstr (name,"test_buddy" )) { +if (strstr (name,"test_buddy" )) { +/* Buddy tests initialize the allocator directly. */ + ret =libarena_run_prog (bpf_program__fd (skel->progs.arena_buddy_destroy)); +if (!ASSERT_OK (ret,"arena_buddy_destroy" )) +return ; + }else { ret =libarena_run_prog (bpf_program__fd (skel->progs.arena_buddy_reset));if (!ASSERT_OK (ret,"arena_buddy_reset" ))return ;
@@ -24,7 +29,6 @@ static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, ret =libarena_run_prog (bpf_program__fd (prog));ASSERT_OK (ret, name); - }static void *run_libarena_parallel_prog (void *arg)
tools/testing/selftests/bpf/prog_tests/libarena_asan.c +6 -2
@@ -17,7 +17,12 @@ static void run_libarena_asan_test(struct libarena_asan *skel, {int ret; -if (!strstr (name,"test_buddy" )) { +if (strstr (name,"test_buddy" )) { +/* Buddy tests initialize the allocator directly. */ + ret =libarena_run_prog (bpf_program__fd (skel->progs.arena_buddy_destroy)); +if (!ASSERT_OK (ret,"arena_buddy_destroy" )) +return ; + }else { ret =libarena_run_prog (bpf_program__fd (skel->progs.arena_buddy_reset));if (!ASSERT_OK (ret,"arena_buddy_reset" ))return ;
@@ -90,4 +95,3 @@ void test_libarena_asan(void)return ; } -
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next 3/5] selftests/bpf: libarena: Clean up allocation state before buddy tests
This looks like a bug fix for the buddy test harness, where the run_libarena_test()/run_libarena_asan_test() path only reset the allocator rather than destroying it. Should this include a Fixes: tag?
Quoted 7 lines
Summary: The buddy allocator requires the global BPF buddy allocator to not be already initialized. However, the test currently merely resets the allocator before the buddy tests instead of destroying it, and the test worked because the buddy test happened to run first. Properly destroy the allocator instead of resetting it.
Signed-off-by Emil Tsalapatis <[email protected]>
This looks like a bug fix for the buddy test harness, where the run_libarena_test()/run_libarena_asan_test() path only reset the allocator rather than destroying it. Should this include a Fixes: tag?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/27749630149
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 3/5] selftests/bpf: libarena: Clean up allocation state before buddy tests
Quoted 6 lines · bot+bpf-ci
Quoted 6 lines
Summary: The buddy allocator requires the global BPF buddy allocator to not be already initialized. However, the test currently merely resets the allocator before the buddy tests instead of destroying it, and the test worked because the buddy test happened to run first. Properly destroy the allocator instead of resetting it.
Quoted 8 lines
Quoted 1 line
Signed-off-by Emil Tsalapatis <[email protected]>This looks like a bug fix for the buddy test harness, where the run_libarena_test()/run_libarena_asan_test() path only reset the allocator rather than destroying it. Should this include a Fixes: tag?
Fixes b1487dc1b181 ("selftests/bpf: Add selftests for libarena buddy allocator")
Not triggerable until we add the tests in this patchset.
Quoted 6 lines
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/27749630149
Re: [PATCH bpf-next 3/5] selftests/bpf: libarena: Clean up allocation state before buddy tests
In reply to Emil TsalapatisQuoted 7 lines · Emil Tsalapatis
Summary: The buddy allocator requires the global BPF buddy allocator to not be already initialized. However, the test currently merely resets the allocator before the buddy tests instead of destroying it, and the test worked because the buddy test happened to run first. Properly destroy the allocator instead of resetting it.
Signed-off-by Emil Tsalapatis <[email protected]>
Quoted 7 lines
--- tools/testing/selftests/bpf/libarena/src/common.bpf.c | 6 ++++++ tools/testing/selftests/bpf/prog_tests/libarena.c | 8 ++++++-- tools/testing/selftests/bpf/prog_tests/libarena_asan.c | 8 ++++++-- 3 files changed, 18 insertions(+), 4 deletions(-)[...]
Emil Tsalapatis
reviewerPATCH 4/5 selftests/bpf: Add arena-based bitmap data structure
In reply to Emil TsalapatisAdd an arena-based word-aligned bitmap data struture. The structure is useful as a building block, e.g., sched-ext uses it to represent cpumask structures.
--- .../bpf/libarena/include/libarena/bitmap.h | 31 +++ .../selftests/bpf/libarena/src/bitmap.bpf.c | 191 ++++++++++++++++++ 2 files changed, 222 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +31 -0
@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8 +#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +}; + +struct bitmap __arena *bmp_alloc(size_t bits); +void bmp_free(struct bitmap __arena *bmp); + +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp); +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp); + +void bmp_clear(size_t bits, struct bitmap __arena *bmp); +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +bool bmp_empty(size_t bits, struct bitmap __arena *bmp); +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src); + +bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2); +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small); +void bmp_print(size_t bits, struct bitmap __arena *bmp);
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +191 -0
191 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider: - [High] The `struct bitmap` uses a `u64` array, but bitwise helper macros rely on `sizeof(long)`, causing…
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] The struct bitmap uses a u64 array, but bitwise helper macros rely on sizeof(long), causing a severe memory layout and indexing mismatch between 64-bit BPF and 32-bit user-space.
- [High] bmp_set_bit and bmp_clear_bit perform non-atomic read-modify-write operations, leading to lost updates under concurrent access.
- [High] bmp_alloc incorrectly rejects bitmap sizes that are not exact multiples of BITS_PER_LONG, completely breaking allocations for standard cpumask sizes. --
commit e05abd6424c958e46d415ca79df966bf83a06a24
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: Add arena-based bitmap data structure
This commit adds an arena-based word-aligned bitmap data structure. The structure is intended to be used as a building block for features like sched-ext to represent cpumask structures.
Quoted 9 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +3
-0@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 13
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +10
-0+#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +};
[Severity: High]
Since struct bitmap defines its storage as a fixed-width u64 array, will using sizeof(long) and 1UL in BIT_WORD and BIT_MASK cause a mismatch between 32-bit user-space and 64-bit BPF?
On a 32-bit user-space process, BITS_PER_LONG is 32. Accessing bit 32 would compute BIT_WORD(32) = 1, pointing to bits 64-127 of the u64 array, while the 64-bit BPF program would correctly calculate BIT_WORD(32) = 0.
Should these macros use fixed-width indexing constants like sizeof(u64) * 8 and 1ULL instead to maintain the shared memory contract?
[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +0
-0
[ ... ]
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 20
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +9
-0+__weak +struct bitmap __arena *bmp_alloc(size_t bits) +{ + struct bitmap __arena *bmp; +size_t size =BITS_TO_LONGS (bits) *sizeof (bmp->bits[0 ]); + +/* Assume long-aligned masks. */ +if (bits %BITS_PER_LONG ) +return NULL ;
[Severity: High]
Does this logic artificially reject valid unaligned bit counts, preventing its use for standard cpumask sizes where nr_cpu_ids is not a multiple of 64?
The allocation size is already safely rounded up to the nearest word boundary via BITS_TO_LONGS(bits), and trailing bits seem to be handled cleanly by operations like bmp_last_word_mask.
Could this check be removed so callers aren't forced to artificially round up requested bits?
[ ... ]
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 47
Quoted 11 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +11
-0+__weak +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] |=BIT_MASK (bit); +} + +__weak +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] &= ~BIT_MASK (bit); +}
[Severity: High]
Will these non-atomic read-modify-write operations race if multiple CPUs concurrently set or clear different bits within the same 64-bit word?
Since the bitmap is intended for concurrent structures like sched-ext cpumasks, updates could be silently clobbered.
Should these functions use atomic built-ins such as __sync_fetch_and_or and __sync_fetch_and_and?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure
Quoted 40 lines · sashiko-bot
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Thestruct bitmapuses au64array, but bitwise helper macros rely onsizeof(long), causing a severe memory layout and indexing mismatch between 64-bit BPF and 32-bit user-space.
- [High]bmp_set_bitandbmp_clear_bitperform non-atomic read-modify-write operations, leading to lost updates under concurrent access.
- [High]bmp_allocincorrectly rejects bitmap sizes that are not exact multiples ofBITS_PER_LONG, completely breaking allocations for standard cpumask sizes. --commit
e05abd6424c958e46d415ca79df966bf83a06a24
Author: Emil Tsalapatis <[email protected]>selftests/bpf: Add arena-based bitmap data structure
This commit adds an arena-based word-aligned bitmap data structure. The structure is intended to be used as a building block for features like sched-ext to represent cpumask structures.
Quoted 9 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +3
-0@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 13
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +10
-0+#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +};[Severity: High]
Since struct bitmap defines its storage as a fixed-width u64 array, will using sizeof(long) and 1UL inBIT_WORDandBIT_MASKcause a mismatch between 32-bit user-space and 64-bit BPF?
Quoted 7 lines
On a 32-bit user-space process,
BITS_PER_LONGis 32. Accessing bit 32 would computeBIT_WORD(32)= 1, pointing to bits 64-127 of the u64 array, while the 64-bit BPF program would correctly calculateBIT_WORD(32)= 0.Should these macros use fixed-width indexing constants like sizeof(u64) * 8 and 1ULL instead to maintain the shared memory contract?
Ack, should be BITS_PER_LONG_LONG. We are not prioritizing 32-bit here.
Quoted 22 lines
[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +0
-0[ ... ]
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 20
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +9
-0+__weak +struct bitmap __arena *bmp_alloc(size_t bits) +{ + struct bitmap __arena *bmp; +size_t size =BITS_TO_LONGS (bits) *sizeof (bmp->bits[0 ]); + +/* Assume long-aligned masks. */ +if (bits %BITS_PER_LONG ) +return NULL ;[Severity: High]
Does this logic artificially reject valid unaligned bit counts, preventing its use for standard cpumask sizes wherenr_cpu_idsis not a multiple of 64?
Quoted 7 lines
The allocation size is already safely rounded up to the nearest word boundary via
BITS_TO_LONGS(bits), and trailing bits seem to be handled cleanly by operations likebmp_last_word_mask.Could this check be removed so callers aren't forced to artificially round up requested bits?
This is a deliberate design choice. The space savings we'd get by handling unaligned cpumasks are relatively small so we don't worry about it unless it proves to be a real issue.
Quoted 18 lines
[ ... ]
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 47
Quoted 11 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +11
-0+__weak +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] |=BIT_MASK (bit); +} + +__weak +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] &= ~BIT_MASK (bit); +}[Severity: High]
Will these non-atomic read-modify-write operations race if multiple CPUs concurrently set or clear different bits within the same 64-bit word?
Quoted 5 lines
Since the bitmap is intended for concurrent structures like sched-ext cpumasks, updates could be silently clobbered.
Should these functions use atomic built-ins such as
__sync_fetch_and_orand__sync_fetch_and_and?
Ack.
[email protected]
AI reviewRe: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure
In reply to Emil TsalapatisShould bitmap.h include an SPDX-License-Identifier header? The companion implementation file bitmap.bpf.c includes the standard tags:
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 3
Quoted 9 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +3
-0@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8
Should bitmap.h include an SPDX-License-Identifier header? The companion implementation file bitmap.bpf.c includes the standard tags:
// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
/*
* Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates.
* Copyright (c) 2025-2026 Emil Tsalapatis <[email protected]>
*/while the header begins directly with #pragma once. Every other header in this libarena series (common.h, asan.h, buddy.h) carries these tags.
Quoted 18 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +18
-0+#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +}; + +struct bitmap __arena *bmp_alloc(size_t bits); +void bmp_free(struct bitmap __arena *bmp); + +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp); +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp);
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 31
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +10
-0+ +void bmp_clear(size_t bits, struct bitmap __arena *bmp); +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +bool bmp_empty(size_t bits, struct bitmap __arena *bmp); +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src); + +bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2); +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small); +void bmp_print(size_t bits, struct bitmap __arena *bmp);
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/27749630149
Ihor Solodrai
reviewerRe: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure
In reply to Emil TsalapatisQuoted 65 lines · Emil Tsalapatis
Add an arena-based word-aligned bitmap data struture. The structure is useful as a building block, e.g., sched-ext uses it to represent cpumask structures.
Signed-off-by Emil Tsalapatis <[email protected]>--- .../bpf/libarena/include/libarena/bitmap.h | 31 +++ .../selftests/bpf/libarena/src/bitmap.bpf.c | 191 ++++++++++++++++++ 2 files changed, 222 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.ctools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +31
-0@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8 +#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +}; + +struct bitmap __arena *bmp_alloc(size_t bits); +void bmp_free(struct bitmap __arena *bmp); + +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp); +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp); + +void bmp_clear(size_t bits, struct bitmap __arena *bmp); +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +bool bmp_empty(size_t bits, struct bitmap __arena *bmp); +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src); + +bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2); +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small); +void bmp_print(size_t bits, struct bitmap __arena *bmp);tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0@@ -0,0 +1,191 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause +/* +* Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates. +* Copyright (c) 2025-2026 Emil Tsalapatis <[email protected]> +*/ + +#include <libarena/common.h> + +#include <libarena/asan.h> +#include <libarena/bitmap.h>
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 20
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0+ +__weak +struct bitmap __arena *bmp_alloc(size_t bits) +{ + struct bitmap __arena *bmp; +size_t size =BITS_TO_LONGS (bits) *sizeof (bmp->bits[0 ]); + +/* Assume long-aligned masks. */ +if (bits %BITS_PER_LONG ) +return NULL ;
I think this check may be dropped.
There is code below to handle non-aligned bits (bmp_last_word_mask etc), but here we forbid them, so masking doesn't run.
And you mentioned in the cover that this is supposed to be used as cpumask, but nr_cpu_ids is unlikely to be a multiple of 64, right?
Quoted 39 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +39
-0+ + bmp = (struct bitmap __arena *)arena_malloc(size); +if (!bmp) +return NULL ; + +bmp_clear (bits, bmp); + +return bmp; +} + +__weak +void bmp_free(struct bitmap __arena *bmp) +{ +arena_free (bmp); +} + +__weak +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] |=BIT_MASK (bit); +} + +__weak +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] &= ~BIT_MASK (bit); +} + +__weak +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp) +{ +return bmp->bits[BIT_WORD (bit)] &BIT_MASK (bit); +} + +__weak +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ +u64 val =BIT_MASK (bit); +u32 idx =BIT_WORD (bit);
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 69
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0+u64 actual; + + do { + u64 old = bmp->bits[idx]; + + if (!(old & val)) + return false; + + u64 new = old & ~val; + actual = cmpxchg(&bmp->bits[idx], old, new);
bmp_test_and_clear_bit() is atomic, but bmp_set_bit() and bmp_clear_bit() aren't.
So the concurrent set/clear on the same word can lose updates (last writer wins), right? Only test_and_clear seems to be safe cross-CPU. Are we missing test_and_set?
There is a doc on atomic bitops [1], and apparently in the kernel there is a convention to have a non-atomic variant for each RMW atomic operation, prefixed with '__', for example: test_and_clear_bit() and __test_and_clear_bit().
Maybe libarena should follow the same convention?
[1] https://docs.kernel.org/core-api/wrappers/atomic_bitops.html
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +9
-0+ +if (actual == old) +return true; + + }while (can_loop); + +return false; +} +
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure
Quoted 79 lines · Ihor Solodrai
Quoted 65 lines · Emil Tsalapatis
Add an arena-based word-aligned bitmap data struture. The structure is useful as a building block, e.g., sched-ext uses it to represent cpumask structures.
Signed-off-by Emil Tsalapatis <[email protected]>--- .../bpf/libarena/include/libarena/bitmap.h | 31 +++ .../selftests/bpf/libarena/src/bitmap.bpf.c | 191 ++++++++++++++++++ 2 files changed, 222 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.ctools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +31
-0@@ -0,0 +1,31 @@ +#pragma once + +#define BITS_PER_BYTE 8 +#define BYTES_TO_BITS (nb) ((nb) * BITS_PER_BYTE) + +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS (nr) (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define BIT_MASK (nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD (nr) ((nr) / BITS_PER_LONG) + +struct bitmap { +u64 bits[0 ]; +}; + +struct bitmap __arena *bmp_alloc(size_t bits); +void bmp_free(struct bitmap __arena *bmp); + +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp); +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp); +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp); + +void bmp_clear(size_t bits, struct bitmap __arena *bmp); +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2); +bool bmp_empty(size_t bits, struct bitmap __arena *bmp); +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src); + +bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2); +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small); +void bmp_print(size_t bits, struct bitmap __arena *bmp);tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0@@ -0,0 +1,191 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause +/* +* Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates. +* Copyright (c) 2025-2026 Emil Tsalapatis <[email protected]> +*/ + +#include <libarena/common.h> + +#include <libarena/asan.h> +#include <libarena/bitmap.h> tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 20
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0+ +__weak +struct bitmap __arena *bmp_alloc(size_t bits) +{ + struct bitmap __arena *bmp; +size_t size =BITS_TO_LONGS (bits) *sizeof (bmp->bits[0 ]); + +/* Assume long-aligned masks. */ +if (bits %BITS_PER_LONG ) +return NULL ;I think this check may be dropped.
Quoted 7 lines
There is code below to handle non-aligned bits (
bmp_last_word_masketc), but here we forbid them, so masking doesn't run.And you mentioned in the cover that this is supposed to be used as cpumask, but
nr_cpu_idsis unlikely to be a multiple of 64, right?
How about keeping the check here and removing the unaligned bit handling below? We don't test for it either, and I can't currently think of any good use cases for it. So we can make sure here that the caller knows the bit size should be word aligned.
Quoted 53 lines
Quoted 39 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +39
-0+ + bmp = (struct bitmap __arena *)arena_malloc(size); +if (!bmp) +return NULL ; + +bmp_clear (bits, bmp); + +return bmp; +} + +__weak +void bmp_free(struct bitmap __arena *bmp) +{ +arena_free (bmp); +} + +__weak +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] |=BIT_MASK (bit); +} + +__weak +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ + bmp->bits[BIT_WORD (bit)] &= ~BIT_MASK (bit); +} + +__weak +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp) +{ +return bmp->bits[BIT_WORD (bit)] &BIT_MASK (bit); +} + +__weak +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp) +{ +u64 val =BIT_MASK (bit); +u32 idx =BIT_WORD (bit);tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c line 69
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +10
-0+u64 actual; + + do { + u64 old = bmp->bits[idx]; + + if (!(old & val)) + return false; + + u64 new = old & ~val; + actual = cmpxchg(&bmp->bits[idx], old, new);
bmp_test_and_clear_bit()is atomic, butbmp_set_bit()andbmp_clear_bit()aren't.
Quoted 4 lines
So the concurrent set/clear on the same word can lose updates (last writer wins), right? Only
test_and_clearseems to be safe cross-CPU. Are we missingtest_and_set?
Yes, set/clear are not atomic and we are missing test and set. I can add those.
Quoted 7 lines
There is a doc on atomic bitops [1], and apparently in the kernel there is a convention to have a non-atomic variant for each RMW atomic operation, prefixed with '__', for example:
test_and_clear_bit()and__test_and_clear_bit().Maybe libarena should follow the same convention?
Yeah let's do that. AFAIK we only have cmpxchg for atomics so I'll use it for the logic. It's expensive, but I don't think we can generate anything like x86's btsl.
Quoted 14 lines
[1] https://docs.kernel.org/core-api/wrappers/atomic_bitops.html
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +9
-0+ +if (actual == old) +return true; + + }while (can_loop); + +return false; +} +
Emil Tsalapatis
reviewerPATCH 5/5 selftests/bpf: libarena: Add bitmap selftets
In reply to Emil TsalapatisAdd testing for the new arena bitmap data structure.
--- .../bpf/libarena/selftests/test_bitmap.bpf.c | 314 ++++++++++++++++++ 1 file changed, 314 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c new file +314 -0
@@ -0,0 +1,314 @@ +#include <libarena/common.h> + +#include <libarena/asan.h> +#include <libarena/bitmap.h> + +#define TEST_BITS (2 * BITS_PER_LONG) +#define TEST_WORDS BITS_TO_LONGS(TEST_BITS) +#define MID_BIT (BITS_PER_LONG + 1) +#define LAST_BIT (TEST_BITS - 1) + +static void test_bmp_setall(struct bitmap __arena *bmp) +{ +volatile u32 i; + +for (i = zero; i <TEST_WORDS && can_loop; i++) + bmp->bits[i] = ~0ULL ; +} + +SEC("syscall") +__weak int test_bitmap_alloc_free (void ) +{ + struct bitmap __arena *bmp; + + bmp =bmp_alloc (TEST_BITS ); +if (!bmp) +return -ENOMEM ; + +if (!bmp_empty (TEST_BITS , bmp)) + goto err; + +bmp_set_bit (LAST_BIT , bmp); +if (!bmp_test_bit (LAST_BIT , bmp)) + goto err; + +bmp_clear_bit (LAST_BIT , bmp); +if (bmp_test_bit (LAST_BIT , bmp)) + goto err; + +bmp_free (bmp); +return 0 ; + +err: +bmp_free (bmp); +return -EINVAL ; +} + +SEC("syscall") +__weak int test_bitmap_bit_ops (void ) +{ + struct bitmap __arena *bmp; + + bmp =bmp_alloc (TEST_BITS ); +if (!bmp) +return -ENOMEM ; + +bmp_set_bit (0 , bmp); +if (!bmp_test_bit (0 , bmp)) + goto err; + +bmp_set_bit (MID_BIT , bmp); +if (!bmp_test_bit (MID_BIT , bmp)) + goto err; + +bmp_set_bit (LAST_BIT , bmp); +if (!bmp_test_bit (LAST_BIT , bmp)) + goto err; + +if (bmp_test_bit (MID_BIT -1 , bmp)) + goto err; + +bmp_clear_bit (MID_BIT , bmp); +if (bmp_test_bit (MID_BIT , bmp)) + goto err; + +if (!bmp_test_bit (0 , bmp)) + goto err; + +if (!bmp_test_bit (LAST_BIT , bmp)) + goto err; + +bmp_clear_bit (0 , bmp); +bmp_clear_bit (LAST_BIT , bmp); +if (!bmp_empty (TEST_BITS , bmp)) + goto err; + +if (bmp->bits[0 ]) + goto err; + +if (bmp->bits[1 ]) + goto err; + +bmp_free (bmp); +return 0 ; + +err: +bmp_free (bmp); +return -EINVAL ; +} + +static bool test_bitmap_test_and_clear_single(struct bitmap __arena *bmp, size_t ind) +{ +if (bmp_test_and_clear_bit (ind, bmp)) +return false; + +bmp_set_bit (ind, bmp); + +if (!bmp_test_and_clear_bit (ind, bmp)) +return false; + +if (bmp_test_bit (ind, bmp)) +return false; + +if (bmp_test_and_clear_bit (ind, bmp)) +return false; + +return true; +} + +SEC("syscall") +__weak int test_bitmap_test_and_clear_bit (void ) +{ + struct bitmap __arena *bmp; + + bmp =bmp_alloc (TEST_BITS ); +if (!bmp) +return -ENOMEM ; + +if (!test_bitmap_test_and_clear_single (bmp,0 )) + goto err; + +if (!test_bitmap_test_and_clear_single (bmp,MID_BIT )) + goto err; + +if (!test_bitmap_test_and_clear_single (bmp,LAST_BIT )) + goto err; + +if (!bmp_empty (TEST_BITS , bmp)) + goto err; + +bmp_free (bmp); +return 0 ; + +err: +bmp_free (bmp); +return -EINVAL ; +} + +SEC("syscall") +__weak int test_bitmap_and (void ) +{ + struct bitmap __arena *src1 = NULL, *src2 = NULL, *dst = NULL; + + src1 =bmp_alloc (TEST_BITS ); + src2 =bmp_alloc (TEST_BITS ); + dst =bmp_alloc (TEST_BITS ); +if (!src1 || !src2 || !dst) + goto err; + +test_bmp_setall (dst); + +bmp_set_bit (0 , src1); +bmp_set_bit (MID_BIT , src1); +bmp_set_bit (LAST_BIT , src1); + +bmp_set_bit (MID_BIT , src2); +bmp_set_bit (LAST_BIT , src2); + +bmp_and (TEST_BITS , dst, src1, src2); + +if (bmp_test_bit (0 , dst)) + goto err; +if (!bmp_test_bit (MID_BIT , dst)) + goto err; +if (!bmp_test_bit (LAST_BIT , dst)) + goto err; + +if (dst->bits[0 ]) + goto err; +if (dst->bits[1 ] != (BIT_MASK (MID_BIT ) |BIT_MASK (LAST_BIT ))) + goto err; + +bmp_free (src1); +bmp_free (src2); +bmp_free (dst); +return 0 ; + +err: +bmp_free (src1); +bmp_free (src2); +bmp_free (dst); +return -EINVAL ; +} + +SEC("syscall") +__weak int test_bitmap_or (void ) +{ + struct bitmap __arena *src1 = NULL, *src2 = NULL, *dst = NULL; + + src1 =bmp_alloc (TEST_BITS ); + src2 =bmp_alloc (TEST_BITS ); + dst =bmp_alloc (TEST_BITS ); +if (!src1 || !src2 || !dst) + goto err; + +test_bmp_setall (dst); + +bmp_set_bit (0 , src1); +bmp_set_bit (LAST_BIT , src1); + +bmp_set_bit (MID_BIT , src2); +bmp_set_bit (LAST_BIT , src2); + +bmp_or (TEST_BITS , dst, src1, src2); + +if (!bmp_test_bit (0 , dst)) + goto err; +if (!bmp_test_bit (MID_BIT , dst)) + goto err; +if (!bmp_test_bit (LAST_BIT , dst)) + goto err; + +if (dst->bits[0 ] !=BIT_MASK (0 )) + goto err; +if (dst->bits[1 ] != (BIT_MASK (MID_BIT ) |BIT_MASK (LAST_BIT ))) + goto err; + +bmp_free (src1); +bmp_free (src2); +bmp_free (dst); +return 0 ; + +err: +bmp_free (src1); +bmp_free (src2); +bmp_free (dst); +return -EINVAL ; +} + +SEC("syscall") +__weak int test_bitmap_subset (void ) +{ + struct bitmap __arena *big = NULL, *small = NULL; + + big =bmp_alloc (TEST_BITS ); + small =bmp_alloc (TEST_BITS ); +if (!big || !small) + goto err; + +if (!bmp_subset (TEST_BITS , big, small)) + goto err; + +bmp_set_bit (0 , small); +if (bmp_subset (TEST_BITS , big, small)) + goto err; + +bmp_set_bit (0 , big); +if (!bmp_subset (TEST_BITS , big, small)) + goto err; + +bmp_set_bit (LAST_BIT , small); +if (bmp_subset (TEST_BITS , big, small)) + goto err; + +bmp_set_bit (LAST_BIT , big); +bmp_set_bit (MID_BIT , big); +if (!bmp_subset (TEST_BITS , big, small)) + goto err; + +if (bmp_subset (TEST_BITS , small, big)) + goto err; + +bmp_free (big); +bmp_free (small); +return 0 ; + +err: +bmp_free (big); +bmp_free (small); +return -EINVAL ; + +} + +SEC("syscall") +__weak int test_bitmap_intersects (void ) +{ + struct bitmap __arena *arg1 = NULL, *arg2 = NULL; + + arg1 =bmp_alloc (TEST_BITS ); + arg2 =bmp_alloc (TEST_BITS ); +if (!arg1 || !arg2) + goto err; + +if (bmp_intersects (TEST_BITS , arg1, arg2)) + goto err; + +bmp_set_bit (0 , arg1); +bmp_set_bit (MID_BIT , arg2); +if (bmp_intersects (TEST_BITS , arg1, arg2)) + goto err; + +bmp_set_bit (LAST_BIT , arg1); +bmp_set_bit (LAST_BIT , arg2); +if (!bmp_intersects (TEST_BITS , arg1, arg2)) + goto err; + +bmp_free (arg1); +bmp_free (arg2); +return 0 ; + +err: +bmp_free (arg1); +bmp_free (arg2); +return -EINVAL ; +}
Signature · 1 line
2.54.0
Re: [PATCH bpf-next 5/5] selftests/bpf: libarena: Add bitmap selftets
Quoted 3 lines · Emil Tsalapatis
Add testing for the new arena bitmap data structure.
Signed-off-by Emil Tsalapatis <[email protected]>
nit: Looks like bmp_copy() is not covered.
Quoted 6 lines
--- .../bpf/libarena/selftests/test_bitmap.bpf.c | 314 ++++++++++++++++++ 1 file changed, 314 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c[...]
Emil Tsalapatis
reviewerRe: [PATCH bpf-next 5/5] selftests/bpf: libarena: Add bitmap selftets
Quoted 8 lines · Ihor Solodrai
Quoted 3 lines · Emil Tsalapatis
Add testing for the new arena bitmap data structure.
Signed-off-by Emil Tsalapatis <[email protected]>Acked-by Ihor Solodrai <[email protected]>nit: Looks like
bmp_copy()is not covered.
Ack I will add a test.
Quoted 7 lines
Quoted 7 lines
--- .../bpf/libarena/selftests/test_bitmap.bpf.c | 314 ++++++++++++++++++ 1 file changed, 314 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c[...]