[PATCH RESEND bpf-next v3 0/6] selftests/bpf: libarena cleanup and bitmap struct

[PATCH RESEND bpf-next v3 0/6] 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 to 6
introduce the bitmap data structure along with selftests.

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

CHANGELOG
=========

v3 was resent as the first submission was missing the first patch.

v2 -> v3: (https://lore.kernel.org/bpf/20260701185235.4516-1-emil@etsalapatis.com)
- Remove unused macros and fix typo in commit message (AI)

v1 -> v2: (https://lore.kernel.org/bpf/20260618085626.19633-1-emil@etsalapatis.com)

- Added acks by Ihor and Eduard
- Fix missing commit message (Ihor)
- Enforce 64 bits per cell with BITS_TO_LONG_LONG (Sashiko)
- Add test for bmp_copy (Ihor)
- Add atomic versions of _set() and _clear() (Ihor) and add a parallel
  selftest for them.


Emil Tsalapatis (6):
  selftests/bpf: libarena: 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 selftests
  selftests/bpf: libarena: Add parallel bitmap selftest

 .../bpf/libarena/include/libarena/bitmap.h    |  34 ++
 .../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  | 394 ++++++++++++++++++
 .../{st_buddy.bpf.c => test_buddy.bpf.c}      |   8 +-
 .../selftests/test_parallel_bitmap.bpf.c      | 190 +++++++++
 .../selftests/test_parallel_spmc.bpf.c        |   9 +-
 .../selftests/bpf/libarena/src/bitmap.bpf.c   | 245 +++++++++++
 .../selftests/bpf/libarena/src/common.bpf.c   |   9 +-
 .../selftests/bpf/prog_tests/libarena.c       |   8 +-
 .../selftests/bpf/prog_tests/libarena_asan.c  |   8 +-
 12 files changed, 900 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/selftests/test_parallel_bitmap.bpf.c
 create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c

-- 
2.54.0

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

[Emil Tsalapatis]

The st_ (selftests_) prefix is confusing and has been replaced
with the more descriptive test_. However, last patch did not
properly move all files to the new prefix. Rename the existing
files to complete the move.

Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
---
 .../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 RESEND bpf-next v3 2/6] 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. Using barrier_var() is
the only way to break the optimization, as annotating the index as
volatile does not suffice.

After that, remove the bpf_for() invocations introduced in libarena for
parallel spmc testing.

Reported-by: Eduard Zingerman <eddyz87@gmail.com>
Acked-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

[PATCH RESEND bpf-next v3 3/6] 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.

Fixes: b1487dc1b181 ("selftests/bpf: Add selftests for libarena buddy allocator")
Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
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

[PATCH RESEND bpf-next v3 4/6] 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    |  34 +++
 .../selftests/bpf/libarena/src/bitmap.bpf.c   | 245 ++++++++++++++++++
 2 files changed, 279 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..cf6b63f5d9a4
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
@@ -0,0 +1,34 @@
+#pragma once
+
+#define BITS_PER_BYTE		8
+#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_BYTE)
+
+#define BITS_PER_LONG_LONG	(sizeof(long long) * BITS_PER_BYTE)
+#define BITS_TO_LONG_LONGS(nr)	(((nr) + BITS_PER_LONG_LONG - 1) / BITS_PER_LONG_LONG)
+#define BIT_MASK(nr)		(1ULL << ((nr) % BITS_PER_LONG_LONG))
+#define BIT_WORD(nr)		((nr) / BITS_PER_LONG_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);
+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);
+bool bmp_test_and_set_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..80e814401fb9
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
@@ -0,0 +1,245 @@
+// 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_LONG_LONGS(bits) * sizeof(bmp->bits[0]);
+
+	/* Assume long-aligned masks. */
+	if (bits % BITS_PER_LONG_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 old, new, actual;
+
+	do {
+		old = bmp->bits[idx];
+
+		if (!(old & val))
+			return false;
+
+		new = old & ~val;
+		actual = cmpxchg(&bmp->bits[idx], old, new);
+
+		if (actual == old)
+			return true;
+
+	} while (can_loop);
+
+	return false;
+}
+
+__weak
+bool bmp_test_and_set_bit(u32 bit, struct bitmap __arena *bmp)
+{
+	u64 val = BIT_MASK(bit);
+	u32 idx = BIT_WORD(bit);
+	u64 old, new, actual;
+
+	do {
+		old = bmp->bits[idx];
+
+		if ((old & val))
+			return true;
+
+		new = old | val;
+		actual = cmpxchg(&bmp->bits[idx], old, new);
+
+		if (actual == old)
+			return false;
+
+	} while (can_loop);
+
+	return false;
+}
+
+__weak
+void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp)
+{
+	u64 val = BIT_MASK(bit);
+	u32 idx = BIT_WORD(bit);
+	u64 old, new, actual;
+
+	do {
+		old = bmp->bits[idx];
+		new = old & ~val;
+		actual = cmpxchg(&bmp->bits[idx], old, new);
+
+	} while (actual != old && can_loop);
+}
+
+__weak
+void bmp_set_bit(u32 bit, struct bitmap __arena *bmp)
+{
+	u64 val = BIT_MASK(bit);
+	u32 idx = BIT_WORD(bit);
+	u64 old, new, actual;
+
+	do {
+		old = bmp->bits[idx];
+		new = old | val;
+		actual = cmpxchg(&bmp->bits[idx], old, new);
+
+	} while (actual != old && can_loop);
+}
+
+__weak
+void bmp_clear(size_t bits, struct bitmap __arena *bmp)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		bmp->bits[i] = 0;
+}
+
+static __always_inline u64 bmp_last_word_mask(size_t bits)
+{
+	u32 rem = bits % BITS_PER_LONG_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_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		dst->bits[i] = src1->bits[i] & src2->bits[i];
+
+	if (nwords && bits % BITS_PER_LONG_LONG)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		dst->bits[i] = src1->bits[i] | src2->bits[i];
+
+	if (nwords && bits % BITS_PER_LONG_LONG)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+bool bmp_empty(size_t bits, struct bitmap __arena *bmp)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++) {
+		u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL;
+
+		if (bmp->bits[i] & mask)
+			return false;
+	}
+
+	return true;
+}
+
+__weak
+void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		dst->bits[i] = src->bits[i];
+
+	if (nwords && bits % BITS_PER_LONG_LONG)
+		dst->bits[nwords - 1] &= bmp_last_word_mask(bits);
+}
+
+__weak
+bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++) {
+		u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL;
+
+		if (~big->bits[i] & small->bits[i] & mask)
+			return false;
+	}
+
+	return true;
+}
+
+__weak
+bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2)
+{
+	size_t nwords = BITS_TO_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++) {
+		u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL;
+
+		if (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_LONG_LONGS(bits);
+	volatile u32 i;
+
+	for (i = zero; i < nwords && can_loop; i++)
+		arena_stderr("%016llx ", bmp->bits[i]);
+}
-- 
2.54.0

[PATCH RESEND bpf-next v3 5/6] selftests/bpf: libarena: Add bitmap selftests

[Emil Tsalapatis]

Add testing for the new arena bitmap data structure.

Acked-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../bpf/libarena/selftests/test_bitmap.bpf.c  | 394 ++++++++++++++++++
 1 file changed, 394 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..e7d32f44d687
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
@@ -0,0 +1,394 @@
+#include <libarena/common.h>
+
+#include <libarena/asan.h>
+#include <libarena/bitmap.h>
+
+#define TEST_BITS	(2 * BITS_PER_LONG_LONG)
+#define TEST_WORDS	BITS_TO_LONG_LONGS(TEST_BITS)
+#define MID_BIT		(BITS_PER_LONG_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;
+}
+
+static bool test_bitmap_test_and_set_single(struct bitmap __arena *bmp, size_t ind)
+{
+	if (bmp_test_and_set_bit(ind, bmp))
+		return false;
+
+	if (!bmp_test_and_set_bit(ind, bmp))
+		return false;
+
+	if (!bmp_test_bit(ind, bmp))
+		return false;
+
+	__bmp_clear_bit(ind, bmp);
+
+	if (bmp_test_and_set_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_test_and_set_bit(void)
+{
+	struct bitmap __arena *bmp;
+
+	bmp = bmp_alloc(TEST_BITS);
+	if (!bmp)
+		return -ENOMEM;
+
+	if (!test_bitmap_test_and_set_single(bmp, 0))
+		goto err;
+
+	if (!test_bitmap_test_and_set_single(bmp, MID_BIT))
+		goto err;
+
+	if (!test_bitmap_test_and_set_single(bmp, LAST_BIT))
+		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;
+}
+
+SEC("syscall")
+__weak int test_bitmap_copy(void)
+{
+	struct bitmap __arena *arg1 = NULL, *arg2 = NULL;
+
+	arg1 = bmp_alloc(TEST_BITS);
+	arg2 = bmp_alloc(TEST_BITS);
+	if (!arg1 || !arg2)
+		goto err;
+
+	__bmp_set_bit(0, arg1);
+	__bmp_set_bit(MID_BIT, arg1);
+
+	/* Make sure those get overwritten. */
+	__bmp_set_bit(1, arg2);
+	__bmp_set_bit(MID_BIT + 2, arg2);
+
+	bmp_copy(TEST_BITS, arg2, arg1);
+
+	/* Bitmaps are equal if a subset of each other. */
+	if (!bmp_subset(TEST_BITS, arg1, arg2) ||
+	    !bmp_subset(TEST_BITS, arg2, arg1))
+		goto err;
+
+	bmp_free(arg1);
+	bmp_free(arg2);
+	return 0;
+
+err:
+	bmp_free(arg1);
+	bmp_free(arg2);
+	return -EINVAL;
+}
-- 
2.54.0

[PATCH RESEND bpf-next v3 6/6] selftests/bpf: libarena: Add parallel bitmap selftest

[Emil Tsalapatis]

Add a selftest for testing the atomic bitmap set/clear/
test_and_set/test_and_clear operations. The selftest
checks atomicity by spawning two threads, each of which
either only works on even bits or with odd bits. The
test checks that threads do not affect each other's
bits.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../selftests/test_parallel_bitmap.bpf.c      | 190 ++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c

diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
new file mode 100644
index 000000000000..eec2871e2b0d
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
@@ -0,0 +1,190 @@
+// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
+
+#include <bpf_atomic.h>
+
+#include <libarena/common.h>
+
+#include <libarena/asan.h>
+#include <libarena/bitmap.h>
+
+#define TEST_BITMAP_THREADS	2
+#define TEST_BITMAP_BITS	(2 * BITS_PER_LONG_LONG)
+#define TEST_BITMAP_SYNC_SPINS	BPF_MAX_LOOPS
+#define TEST_BITMAP_ITERS	10 * 1000 * 1000
+
+static struct bitmap __arena *bitmap;
+static volatile u64 started;
+static volatile bool test_abort;
+
+/*
+ * The test needs cmpxchg atomics on arena memory.
+ */
+#if defined(ENABLE_ATOMICS_TESTS) &&				  \
+	(defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
+	 defined(__TARGET_ARCH_s390) || \
+	 defined(__TARGET_ARCH_powerpc) ||				  \
+	 (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64))
+static bool bitmap_tests_enabled(void)
+{
+	return true;
+}
+#else
+static bool bitmap_tests_enabled(void)
+{
+	return false;
+}
+#endif
+
+__weak
+int bitmap_wait_for_start(void)
+{
+	u64 i;
+
+	__sync_fetch_and_add(&started, 1);
+
+	for (i = zero; i < TEST_BITMAP_SYNC_SPINS && can_loop; i++) {
+		if (test_abort)
+			return -EINTR;
+		if (smp_load_acquire(&started) >= TEST_BITMAP_THREADS)
+			return 0;
+	}
+
+	test_abort = true;
+	return -ETIMEDOUT;
+}
+
+/*
+ * The test makes sure writes don't clobber each other by overwriting
+ * the same word. One thread always writes on even bits, the other on
+ * odds. Both should be able to operate on the bitmap oblivious of the
+ * other's operations.
+ */
+__weak
+int bitmap_test_bit_sequence(u32 bit)
+{
+	if (bmp_test_and_clear_bit(bit, bitmap))
+		return -EINVAL;
+
+	if (bmp_test_and_set_bit(bit, bitmap))
+		return -EINVAL;
+	if (!bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	if (!bmp_test_and_set_bit(bit, bitmap))
+		return -EINVAL;
+	if (!bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	if (!bmp_test_and_clear_bit(bit, bitmap))
+		return -EINVAL;
+	if (bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	if (bmp_test_and_clear_bit(bit, bitmap))
+		return -EINVAL;
+
+	bmp_set_bit(bit, bitmap);
+	if (!bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	bmp_clear_bit(bit, bitmap);
+	if (bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	bmp_set_bit(bit, bitmap);
+	if (!bmp_test_bit(bit, bitmap))
+		return -EINVAL;
+
+	return 0;
+
+}
+
+static void bitmap_test_reset_single(int parity)
+{
+	u32 bit;
+
+	for (bit = parity; bit < TEST_BITMAP_BITS && can_loop; bit += 2)
+		bmp_clear_bit(bit, bitmap);
+
+}
+
+static int bitmap_test_common_single(int parity)
+{
+	u32 bit;
+	int ret;
+
+	for (bit = parity; bit < TEST_BITMAP_BITS && can_loop; bit += 2) {
+		if (test_abort)
+			return -EINTR;
+
+		ret = bitmap_test_bit_sequence(bit);
+		if (ret) {
+			test_abort = true;
+			return ret;
+		}
+	}
+
+	return 0;
+}
+
+static int bitmap_test_common(int parity)
+{
+	int ret;
+	u32 i;
+
+	arena_subprog_init();
+
+	ret = bitmap_wait_for_start();
+	if (ret)
+		return ret;
+
+	for (i = zero; i < TEST_BITMAP_ITERS && can_loop; i++) {
+		ret = bitmap_test_common_single(parity);
+		if (ret)
+			return ret;
+
+		if (test_abort)
+			break;
+
+		bitmap_test_reset_single(parity);
+	}
+
+	return 0;
+}
+
+SEC("syscall") int parallel_test_bitmap__enabled(void)
+{
+	return bitmap_tests_enabled() ? 0 : -EOPNOTSUPP;
+}
+
+SEC("syscall") int parallel_test_bitmap__init(void)
+{
+	bitmap = bmp_alloc(TEST_BITMAP_BITS);
+	if (!bitmap)
+		return -ENOMEM;
+
+	return 0;
+}
+
+SEC("syscall") int parallel_test_bitmap__fini(void)
+{
+	int ret = 0;
+
+	if (!bitmap)
+		return -EINVAL;
+
+	bmp_free(bitmap);
+	bitmap = NULL;
+
+	return ret;
+}
+
+SEC("syscall") int parallel_test_bitmap__0(void)
+{
+	return bitmap_test_common(0);
+}
+
+SEC("syscall") int parallel_test_bitmap__1(void)
+{
+	return bitmap_test_common(1);
+}
-- 
2.54.0

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

[sashiko-bot]

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

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

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

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

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

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

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

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

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

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

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

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

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

Could this corrupt data structures relying on the array?

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

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

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

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

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

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

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

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

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

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

Re: [PATCH RESEND bpf-next v3 6/6] selftests/bpf: libarena: Add parallel bitmap selftest

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Spurious test failure due to BPF instruction budget exhaustion during atomic operation retries
--

commit 03c6a4c41937c3d9d257316bef5f1cacfa40aa71
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Add parallel bitmap selftest
    
This commit introduces a new selftest for the libarena atomic bitmap
operations. It spawns two threads that concurrently modify even and odd
bits to verify that operations do not improperly affect adjacent bits.

> diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
> new file mode 100644
> index 0000000000000..eec2871e2b0d1
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c

[ ... ]

> +__weak
> +int bitmap_test_bit_sequence(u32 bit)
> +{

[ ... ]

> +	if (bmp_test_and_clear_bit(bit, bitmap))
> +		return -EINVAL;
> +
> +	bmp_set_bit(bit, bitmap);
> +	if (!bmp_test_bit(bit, bitmap))
> +		return -EINVAL;

[Severity: Medium]
Will this test fail spuriously if the BPF loop budget is exhausted during
the atomic operation retries?

The test executes a high number of iterations to intentionally run until
the BPF loop budget (can_loop) is exhausted.

Because the two threads heavily contend on the same bitmap words, cmpxchg
operations in helpers like bmp_set_bit can frequently fail and retry.

If the budget runs out precisely during a retry inside bmp_set_bit, the
helper will exit early without performing the atomic operation. This
function then unconditionally asserts the outcome by checking bmp_test_bit.

Since the bit was never set, this will fail and abort the test with
-EINVAL, rather than cleanly terminating due to budget exhaustion.

> +
> +	bmp_clear_bit(bit, bitmap);
> +	if (bmp_test_bit(bit, bitmap))
> +		return -EINVAL;

[ ... ]

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

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

[Kumar Kartikeya Dwivedi]

On Mon Jul 6, 2026 at 8:27 PM CEST, sashiko-bot wrote:
> Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
> - [High] Silent failures and falsely reported lock acquisition in bounded atomic bit operations on loop abort.
> - [High] `bmp_empty` and `bmp_subset` return `true` on an aborted loop, defaulting to an unsafe affirmative state.
> - [Medium] Bulk operations unconditionally apply a bitmask to the last word even if the processing loop aborts early.
> - [Medium] Missing `READ_ONCE()` or `volatile` cast in `bmp_test_bit` exposes lockless polling loops to compiler hoisting.
> --
>
> commit 634ac04142cf736158c99f577c0f903470937bfc
> Author: Emil Tsalapatis <emil@etsalapatis.com>
> selftests/bpf: Add arena-based bitmap data structure
>
> This patch adds an arena-based word-aligned bitmap data structure. The
> structure is useful as a building block for components like sched-ext
> to represent cpumask structures.
>
>> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
>> index 0000000000000..80e814401fb9e
>> --- /dev/null
>> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> [ ... ]
>> +__weak
>> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp)
>> +{
>> +	return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit);
>> +}
>
> [Severity: Medium]
> Does this memory access need a READ_ONCE() or a volatile pointer cast?
>
> If this function is used in a lockless concurrent polling loop, could the
> compiler hoist the plain memory read out of the loop and cause an infinite
> spin that misses updates from other CPUs?
>

This one seems worth addressing; I would ignore the rest about can_loop
exhaustion. Please send a follow up fix.

> [...]

Re: [PATCH RESEND bpf-next v3 0/6] selftests/bpf: libarena cleanup and bitmap struct

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Kumar Kartikeya Dwivedi <memxor@gmail.com>:

On Mon,  6 Jul 2026 14:17:24 -0400 you wrote:
> 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 to 6
> introduce the bitmap data structure along with selftests.
> 
> [...]

Here is the summary with links:
  - [RESEND,bpf-next,v3,1/6] selftests/bpf: libarena: Replace leftover st_ prefix with test_
    https://git.kernel.org/bpf/bpf-next/c/83a93e3b80bd
  - [RESEND,bpf-next,v3,2/6] selftests/bpf: libarena: Fix can-loop zero variable definition
    https://git.kernel.org/bpf/bpf-next/c/38ce1fcb3e33
  - [RESEND,bpf-next,v3,3/6] selftests/bpf: libarena: Clean up allocation state before buddy tests
    https://git.kernel.org/bpf/bpf-next/c/0cd6fdd7e85f
  - [RESEND,bpf-next,v3,4/6] selftests/bpf: Add arena-based bitmap data structure
    https://git.kernel.org/bpf/bpf-next/c/62406d9e6e67
  - [RESEND,bpf-next,v3,5/6] selftests/bpf: libarena: Add bitmap selftests
    https://git.kernel.org/bpf/bpf-next/c/7e6b29e8ec54
  - [RESEND,bpf-next,v3,6/6] selftests/bpf: libarena: Add parallel bitmap selftest
    https://git.kernel.org/bpf/bpf-next/c/015b8e873858

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

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

[Emil Tsalapatis]

On Mon Jul 6, 2026 at 3:04 PM EDT, Kumar Kartikeya Dwivedi wrote:
> On Mon Jul 6, 2026 at 8:27 PM CEST, sashiko-bot wrote:
>> Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
>> - [High] Silent failures and falsely reported lock acquisition in bounded atomic bit operations on loop abort.
>> - [High] `bmp_empty` and `bmp_subset` return `true` on an aborted loop, defaulting to an unsafe affirmative state.
>> - [Medium] Bulk operations unconditionally apply a bitmask to the last word even if the processing loop aborts early.
>> - [Medium] Missing `READ_ONCE()` or `volatile` cast in `bmp_test_bit` exposes lockless polling loops to compiler hoisting.
>> --
>>
>> commit 634ac04142cf736158c99f577c0f903470937bfc
>> Author: Emil Tsalapatis <emil@etsalapatis.com>
>> selftests/bpf: Add arena-based bitmap data structure
>>
>> This patch adds an arena-based word-aligned bitmap data structure. The
>> structure is useful as a building block for components like sched-ext
>> to represent cpumask structures.
>>
>>> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
>>> index 0000000000000..80e814401fb9e
>>> --- /dev/null
>>> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
>> [ ... ]
>>> +__weak
>>> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp)
>>> +{
>>> +	return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit);
>>> +}
>>
>> [Severity: Medium]
>> Does this memory access need a READ_ONCE() or a volatile pointer cast?
>>
>> If this function is used in a lockless concurrent polling loop, could the
>> compiler hoist the plain memory read out of the loop and cause an infinite
>> spin that misses updates from other CPUs?
>>
>
> This one seems worth addressing; I would ignore the rest about can_loop
> exhaustion. Please send a follow up fix.

The function is __weak so AFAICT the compiler would not optimize the
call away even if it was reasoning based on the function's body. I
likewise don't think READ_ONCE() would affect anything (correct me
if I'm wrong).

That being said, this function should probably be defined straight in the
bitmap.h header as static inline. It's dumb to require a full call for
a bit operation just because we use __weak the convention for libarena
external API functions. 

I'll send a new patch with the call moved to the header and READ/WRITE
once for the non-atomic get/set/clear ops.

>
>> [...]

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

[Kumar Kartikeya Dwivedi]

On Mon Jul 6, 2026 at 9:17 PM CEST, Emil Tsalapatis wrote:
> On Mon Jul 6, 2026 at 3:04 PM EDT, Kumar Kartikeya Dwivedi wrote:
>> On Mon Jul 6, 2026 at 8:27 PM CEST, sashiko-bot wrote:
>>> Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
>>> - [High] Silent failures and falsely reported lock acquisition in bounded atomic bit operations on loop abort.
>>> - [High] `bmp_empty` and `bmp_subset` return `true` on an aborted loop, defaulting to an unsafe affirmative state.
>>> - [Medium] Bulk operations unconditionally apply a bitmask to the last word even if the processing loop aborts early.
>>> - [Medium] Missing `READ_ONCE()` or `volatile` cast in `bmp_test_bit` exposes lockless polling loops to compiler hoisting.
>>> --
>>>
>>> commit 634ac04142cf736158c99f577c0f903470937bfc
>>> Author: Emil Tsalapatis <emil@etsalapatis.com>
>>> selftests/bpf: Add arena-based bitmap data structure
>>>
>>> This patch adds an arena-based word-aligned bitmap data structure. The
>>> structure is useful as a building block for components like sched-ext
>>> to represent cpumask structures.
>>>
>>>> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
>>>> index 0000000000000..80e814401fb9e
>>>> --- /dev/null
>>>> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
>>> [ ... ]
>>>> +__weak
>>>> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp)
>>>> +{
>>>> +	return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit);
>>>> +}
>>>
>>> [Severity: Medium]
>>> Does this memory access need a READ_ONCE() or a volatile pointer cast?
>>>
>>> If this function is used in a lockless concurrent polling loop, could the
>>> compiler hoist the plain memory read out of the loop and cause an infinite
>>> spin that misses updates from other CPUs?
>>>
>>
>> This one seems worth addressing; I would ignore the rest about can_loop
>> exhaustion. Please send a follow up fix.
>
> The function is __weak so AFAICT the compiler would not optimize the
> call away even if it was reasoning based on the function's body. I
> likewise don't think READ_ONCE() would affect anything (correct me
> if I'm wrong).
>

Hm, right about __weak. But as you note below, changing it to static inline
invalidates the assumption compiler won't use the body to optimize code, so
let's just add it while at it.

> That being said, this function should probably be defined straight in the
> bitmap.h header as static inline. It's dumb to require a full call for
> a bit operation just because we use __weak the convention for libarena
> external API functions.
>
> I'll send a new patch with the call moved to the header and READ/WRITE
> once for the non-atomic get/set/clear ops.
>

SGTM.

>>
>>> [...]