[PATCH bpf-next 0/5] selftests/bpf: libarena cleanup and bitmap struct

[PATCH bpf-next 0/5] selftests/bpf: libarena cleanup and bitmap struct

[Emil Tsalapatis]

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.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>

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.c

-- 
2.54.0

[PATCH bpf-next 1/5] libarena/selftests: Replace leftover st_ prefix with test_

[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%)

diff --git a/tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
similarity index 99%
rename from tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c
rename to tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
index 686caba2c643..256d62a03ce7 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/st_asan_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
@@ -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)
 {
diff --git a/tools/testing/selftests/bpf/libarena/selftests/st_asan_common.h b/tools/testing/selftests/bpf/libarena/selftests/test_asan_common.h
similarity index 100%
rename from tools/testing/selftests/bpf/libarena/selftests/st_asan_common.h
rename to tools/testing/selftests/bpf/libarena/selftests/test_asan_common.h
diff --git a/tools/testing/selftests/bpf/libarena/selftests/st_buddy.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
similarity index 100%
rename from tools/testing/selftests/bpf/libarena/selftests/st_buddy.bpf.c
rename to tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
-- 
2.54.0

[PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition

[Emil Tsalapatis]

BPF 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.

Reported-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../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(-)

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/common.h b/tools/testing/selftests/bpf/libarena/include/libarena/common.h
index a3eb1641ac36..931ace9a49e2 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/common.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/common.h
@@ -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);
diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
index 256d62a03ce7..3266a28f53d7 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_asan_buddy.bpf.c
@@ -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__,
diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
index b45a306816c0..5628f0987012 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
@@ -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);
 
diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c
index f08f2a92e194..5fa96eb74095 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c
@@ -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)
diff --git a/tools/testing/selftests/bpf/libarena/src/common.bpf.c b/tools/testing/selftests/bpf/libarena/src/common.bpf.c
index 50be57213dfb..1b4bb19b3c52 100644
--- a/tools/testing/selftests/bpf/libarena/src/common.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/common.bpf.c
@@ -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)
 {
-- 
2.54.0

Re: [PATCH bpf-next 2/5] selftests/bpf: libarena: Fix can-loop zero variable definition

[sashiko-bot]

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 <emil@etsalapatis.com>

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.

> diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
> index b45a306816c0e..5628f09870121 100644
> --- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
[ ... ]
> @@ -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)
> @@ -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?

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

[PATCH bpf-next 3/5] selftests/bpf: libarena: Clean up allocation state before buddy tests

[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 <emil@etsalapatis.com>
---
 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(-)

diff --git a/tools/testing/selftests/bpf/libarena/src/common.bpf.c b/tools/testing/selftests/bpf/libarena/src/common.bpf.c
index 1b4bb19b3c52..569f0f64d518 100644
--- a/tools/testing/selftests/bpf/libarena/src/common.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/common.bpf.c
@@ -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);
diff --git a/tools/testing/selftests/bpf/prog_tests/libarena.c b/tools/testing/selftests/bpf/prog_tests/libarena.c
index 61ea68dce410..ba5a5a50f7c0 100644
--- a/tools/testing/selftests/bpf/prog_tests/libarena.c
+++ b/tools/testing/selftests/bpf/prog_tests/libarena.c
@@ -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)
diff --git a/tools/testing/selftests/bpf/prog_tests/libarena_asan.c b/tools/testing/selftests/bpf/prog_tests/libarena_asan.c
index d59d9dd12ef2..f897405f701d 100644
--- a/tools/testing/selftests/bpf/prog_tests/libarena_asan.c
+++ b/tools/testing/selftests/bpf/prog_tests/libarena_asan.c
@@ -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;
 }
-
-- 
2.54.0

Re: [PATCH bpf-next 3/5] selftests/bpf: libarena: Clean up allocation state before buddy tests

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 923 bytes --]

> 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 <emil@etsalapatis.com>

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")


---
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

[PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure

[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 <emil@etsalapatis.com>
---
 .../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

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
new file mode 100644
index 000000000000..11623a82e66a
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
@@ -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);
diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
new file mode 100644
index 000000000000..a8ca814aa0c8
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
@@ -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 <emil@etsalapatis.com>
+ */
+
+#include <libarena/common.h>
+
+#include <libarena/asan.h>
+#include <libarena/bitmap.h>
+
+__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;
+
+	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);
+	u64 actual;
+
+	do {
+		u64 old = bmp->bits[idx];
+
+		if (!(old & val))
+			return false;
+
+		u64 new = old & ~val;
+		actual = cmpxchg(&bmp->bits[idx], old, new);
+
+		if (actual == old)
+			return true;
+
+	} while (can_loop);
+
+	return false;
+}
+
+__weak
+void bmp_clear(size_t bits, struct bitmap __arena *bmp)
+{
+	size_t nwords = BITS_TO_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		bmp->bits[i] = 0;
+}
+
+static __always_inline u64 bmp_last_word_mask(size_t bits)
+{
+	u32 rem = bits % BITS_PER_LONG;
+
+	return rem ? (1ULL << rem) - 1 : ~0ULL;
+}
+
+__weak
+void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2)
+{
+	size_t nwords = BITS_TO_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)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2)
+{
+	size_t nwords = BITS_TO_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)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+bool bmp_empty(size_t bits, struct bitmap __arena *bmp)
+{
+	size_t nwords = BITS_TO_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;
+}
+
+__weak
+void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src)
+{
+	size_t nwords = BITS_TO_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)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small)
+{
+	size_t nwords = BITS_TO_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;
+}
+
+__weak
+bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2)
+{
+	size_t nwords = BITS_TO_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 (arg1->bits[i] & arg2->bits[i] & mask)
+			return true;
+	}
+
+	return false;
+}
+
+__weak
+void bmp_print(size_t bits, struct bitmap __arena *bmp)
+{
+	size_t nwords = BITS_TO_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		arena_stderr("%016llx ", bmp->bits[i]);
+}
-- 
2.54.0

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

[sashiko-bot]

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 <emil@etsalapatis.com>

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.

> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> new file mode 100644
> index 0000000000000..11623a82e66a5
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> @@ -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];
> +};

[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?

[ ... ]

> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> new file mode 100644
> index 0000000000000..a8ca814aa0c85
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
[ ... ]
> +__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?

[ ... ]

> +__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?

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

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2476 bytes --]

> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> new file mode 100644
> index 000000000000..11623a82e66a
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> @@ -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 <emil@etsalapatis.com>
     */

while the header begins directly with #pragma once. Every other header in
this libarena series (common.h, asan.h, buddy.h) carries these tags.

> +#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);

[ ... ]


---
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

[PATCH bpf-next 5/5] selftests/bpf: libarena: Add bitmap selftets

[Emil Tsalapatis]

Add testing for the new arena bitmap data structure.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../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

diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
new file mode 100644
index 000000000000..991a2f420ac5
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
@@ -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;
+}
-- 
2.54.0