Skip to contentSkip to conversation

selftests/bpf: libarena cleanup and bitmap struct

PATCH Superseded Emil Tsalapatis 2 participants 10 messages Jul 1

Subsystems (3)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Emil Tsalapatis

author reviewer
#0 lore raw

v2 cover 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.

CHANGELOG

v1 -> v2: (https://lore.kernel.org/bpf/[email protected])

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

 .../bpf/libarena/include/libarena/bitmap.h    |  34 ++
 .../bpf/libarena/include/libarena/common.h    |   2 +-
 .../libarena/selftests/test_asan_buddy.bpf.c  |   8 +-
 .../bpf/libarena/selftests/test_bitmap.bpf.c  | 394 ++++++++++++++++++
 .../bpf/libarena/selftests/test_buddy.bpf.c   |   8 +-
 .../selftests/test_parallel_bitmap.bpf.c      | 191 +++++++++
 .../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 +-
 11 files changed, 900 insertions(+), 16 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
 create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c
 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
Signature · 1 line
2.54.0
author reviewer
#1 lore raw

PATCH v2 1/5 selftests/bpf: libarena: Fix can-loop zero variable definition

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.

---
 .../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
index a3eb1641ac36..931ace9a49e2 100644
@@ -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
index 256d62a03ce7..3266a28f53d7 100644
@@ -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
index b45a306816c0..5628f0987012 100644
@@ -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
index f08f2a92e194..5fa96eb74095 100644
@@ -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
index 50be57213dfb..1b4bb19b3c52 100644
@@ -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
author reviewer
#2 lore raw

PATCH v2 2/5 selftests/bpf: libarena: Clean up allocation state before buddy tests

In reply to 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")
---
 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
index 1b4bb19b3c52..569f0f64d518 100644
@@ -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
index 61ea68dce410..ba5a5a50f7c0 100644
@@ -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
index d59d9dd12ef2..f897405f701d 100644
@@ -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
author reviewer
#3 lore raw

PATCH v2 3/5 selftests/bpf: Add arena-based bitmap data structure

In reply to 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.

---
 .../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
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +34 -0
new file mode 100644
index 000000000000..cf6b63f5d9a4
@@ -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);
tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c new file +245 -0

245 lines not on this page · raw message

Signature · 1 line
2.54.0
#4 lore raw

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

This isn't a bug, but is BYTES_TO_BITS() used anywhere in the series, or could it be dropped from the header? BITS_PER_BYTE itself is used for building BITS_PER_LONG_LONG, but BYTES_TO_BITS appears…

tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 4

Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +4 -0
new file mode 100644
index 000000000000..cf6b63f5d9a4
@@ -0,0 +1,34 @@
+#pragma once
+
+#define BITS_PER_BYTE		8
+#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_BYTE)

This isn't a bug, but is BYTES_TO_BITS() used anywhere in the series, or could it be dropped from the header? BITS_PER_BYTE itself is used for building BITS_PER_LONG_LONG, but BYTES_TO_BITS appears unreferenced throughout the implementation.

tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h line 13

Quoted 9 lines
tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h new file +9 -0
+
+#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];
+};

[ ... ]

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

author reviewer
#5 lore raw

PATCH v2 4/5 selftests/bpf: libarena: Add bitmap selftets

In reply to Emil Tsalapatis

Add testing for the new arena bitmap data structure.

---
 .../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
tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c new file +394 -0
new file mode 100644
index 000000000000..e7d32f44d687
@@ -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;
+}
Signature · 1 line
2.54.0
#6 lore raw

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

This isn't a bug, but the subject says "selftets" — did you mean "selftests"?
Quoted 1 line

selftests/bpf: libarena: Add bitmap selftets

This isn't a bug, but the subject says "selftets" — did you mean "selftests"?

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

author reviewer
#7 lore raw

PATCH v2 5/5 selftests/bpf: libarena: Add parallel bitmap selftest

In reply to 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.

---
 .../selftests/test_parallel_bitmap.bpf.c      | 191 ++++++++++++++++++
 1 file changed, 191 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +191 -0
new file mode 100644
index 000000000000..5381deeb8d37
@@ -0,0 +1,191 @@
+// 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_WORDS	BITS_TO_LONG_LONGS(TEST_BITMAP_BITS)
+#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);
+}
Signature · 1 line
2.54.0
#8 lore raw

Re: [PATCH bpf-next v2 5/5] selftests/bpf: libarena: Add parallel bitmap selftest

This isn't a bug, but TEST_BITMAP_WORDS does not appear to be used anywhere in this file - could it be dropped, or is a use intended?
Quoted 8 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +2 -0
new file mode 100644
index 000000000000..5381deeb8d37
@@ -0,0 +1,191 @@
+// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
+

tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c line 12

Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +10 -0
+#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_WORDS	BITS_TO_LONG_LONGS(TEST_BITMAP_BITS)

This isn't a bug, but TEST_BITMAP_WORDS does not appear to be used anywhere in this file - could it be dropped, or is a use intended?

The sibling serial test (test_bitmap.bpf.c) defines the analogous TEST_WORDS macro and does use it as a loop bound.

tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c line 13

Quoted 1 line
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +1 -0
+#define TEST_BITMAP_SYNC_SPINS	BPF_MAX_LOOPS

[ ... ]

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

author reviewer
#9 lore raw

Re: [PATCH bpf-next v2 5/5] selftests/bpf: libarena: Add parallel bitmap selftest

Quoted 22 lines · bot+bpf-ci
Quoted 8 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +2 -0
new file mode 100644
index 000000000000..5381deeb8d37
@@ -0,0 +1,191 @@
+// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
+

tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c line 12

Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +10 -0
+#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_WORDS	BITS_TO_LONG_LONGS(TEST_BITMAP_BITS)

This isn't a bug, but TEST_BITMAP_WORDS does not appear to be used anywhere in this file - could it be dropped, or is a use intended?

Quoted 3 lines

The sibling serial test (test_bitmap.bpf.c) defines the analogous TEST_WORDS macro and does use it as a loop bound.

Ack to this and the bot nits. Sashiko failed to apply the patch, but the CI did so just fine.

Quoted 10 lines

tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c line 13

Quoted 1 line
tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c new file +1 -0
+#define TEST_BITMAP_SYNC_SPINS	BPF_MAX_LOOPS

[ ... ]

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