[PATCH bpf-next v1 0/7] bpf libarena allocator improvements

[PATCH bpf-next v1 0/7] bpf libarena allocator improvements

[Emil Tsalapatis]

The libarena buddy allocator's design has up until now prioritized
ease of verification. With new verifier features like unlimited
global stack frames and a large stack size we can now improve
the allocator's performance and robustness.

This patch introduces per-CPU caches for the allocator. The overall
caching design is inspired by tcmalloc. Each CPU has its own static
object LIFOs, one for each allocator order. This speeds up allocation
and freeing for BPF programs that have some degree of locality. The
CPU caches are lockless. The caches are replenished from and spilled
into "transfer caches", per-order caches shared between the CPUs that
amortize the cost of spilling/refilling. Data from the transfer caches
is in turn moved from and to the allocator.

The patchset additionally includes code for allocator reentrancy and
bulk allocations. The reentrancy code lets us safely allocate from an
NMI context in general, and from a BPF syscall program context
locklessly. The bulk allocation API is useful for replenishing the
allocator caches and also on its own right for speeding up allocations
during initialization.

Cc: Harry Yoo <harry@kernel.org>
Cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>

Emil Tsalapatis (7):
  selftests/bpf: libarena: Add bulk buddy allocation helpers
  selftests/bpf: Add a parallel buddy allocator benchmark
  selftests/bpf: libarena: Add buddy per-CPU caches
  selftests/bpf: libarena: Handle NMI reentrancy
  selftests/bpf: libarena: Refill local caches in batches
  selftests/bpf: libarena: Add a transfer cache
  selftests/bpf: libarena: Cover buddy cache fast paths

 tools/testing/selftests/bpf/bench.c           |   2 +
 .../selftests/bpf/benchs/bench_libarena.c     | 100 ++-
 .../bpf/benchs/run_bench_libarena.sh          |   8 +
 .../bpf/libarena/benchs/bench_malloc.bpf.c    |  43 ++
 .../bpf/libarena/include/libarena/buddy.h     |  10 +
 .../libarena/include/libarena/buddy_cache.h   |  61 ++
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 277 ++++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 646 +++++++++++++++++-
 8 files changed, 1103 insertions(+), 44 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h

-- 
2.52.0

[PATCH bpf-next v1 1/7] selftests/bpf: libarena: Add bulk buddy allocation helpers

[Emil Tsalapatis]

The buddy allocator currently allocates and frees one object at a time.
Callers that need a group of equal-sized objects consequently take the
allocator lock and repeat the same split operations for every object.

Add buddy_alloc_bulk(), which obtains one block and divides it into a
power-of-two number of independently freeable objects. Add
buddy_free_bulk() to free an arbitrary array of objects while holding the
allocator lock once. Bulk frees cannot avoid coalescing each object
independently, but they still amortize lock acquisition.

The per-CPU caches added later use this interface to populate a cache with
one trip through the central allocator.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../bpf/libarena/include/libarena/buddy.h     |   4 +
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 139 ++++++++++++++----
 2 files changed, 115 insertions(+), 28 deletions(-)

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
index 528c69a1f38e..0ac888be365c 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
@@ -76,6 +76,10 @@ struct buddy {
 int buddy_init(struct buddy __arena *buddy);
 int buddy_destroy(struct buddy __arena *buddy);
 int buddy_free(struct buddy __arena *buddy, void __arena *free);
+int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *addrs,
+	size_t naddrs);
 void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size);
+int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
+	void __arena * __arena * out);
 
 #endif /* __BPF__  */
diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index 2490ab1396de..72b9ea3ac7d5 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -628,7 +628,7 @@ __weak int buddy_destroy(struct buddy __arena *buddy)
 	return 0;
 }
 
-__weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req)
+__weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req, int order_allocs)
 {
 	struct buddy_header __arena *header, *tmp_header, *next_header;
 	u32 idx, tmpidx, retidx;
@@ -636,7 +636,7 @@ __weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req)
 	u64 order = 0;
 	u64 i;
 
-	for (order = order_req; order < BUDDY_CHUNK_NUM_ORDERS && can_loop; order++) {
+	for (order = order_req + order_allocs; order < BUDDY_CHUNK_NUM_ORDERS && can_loop; order++) {
 		if (chunk->freelists[order] != BUDDY_CHUNK_ITEMS)
 			break;
 	}
@@ -658,11 +658,19 @@ __weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req)
 
 	header->prev_index = BUDDY_CHUNK_ITEMS;
 	header->next_index = BUDDY_CHUNK_ITEMS;
-	if (idx_set_order(chunk, retidx, order_req))
-		return (u64)NULL;
+	/*
+	 * For a bulk allocation, record the allocation state and size
+	 * of each item separately so each can be freed independently.
+	 */
+	for (i = zero, idx = retidx; i < (1U << order_allocs) && can_loop; i++) {
+		if (idx_set_order(chunk, idx, order_req))
+			return (u64)NULL;
 
-	if (idx_set_allocated(chunk, retidx, true))
-		return (u64)NULL;
+		if (idx_set_allocated(chunk, idx, true))
+			return (u64)NULL;
+
+		idx += 1U << order_req;
+	}
 
 	/*
 	 * Do not unpoison the address yet, will be done by the caller
@@ -673,7 +681,7 @@ __weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req)
 		return (u64)NULL;
 
 	/* If we allocated from a larger-order chunk, split the buddies. */
-	for (i = order_req; i < order && can_loop; i++) {
+	for (i = order_req + order_allocs; i < order && can_loop; i++) {
 		/*
 		 * Flip the bit for the current order (the bit is guaranteed
 		 * to be 0, so just add 1 << i).
@@ -706,14 +714,14 @@ __weak u64 buddy_chunk_alloc(struct buddy_chunk __arena *chunk, int order_req)
 }
 
 /* Scan the existing chunks for available memory. */
-static u64 buddy_alloc_from_existing_chunks(struct buddy __arena *buddy, int order)
+static u64 buddy_alloc_from_existing_chunks(struct buddy __arena *buddy, int order, int norder)
 {
 	struct buddy_chunk __arena *chunk;
 	u64 address;
 
 	for (chunk = buddy->first_chunk; chunk != NULL && can_loop;
 	     chunk = chunk->next) {
-		address = buddy_chunk_alloc(chunk, order);
+		address = buddy_chunk_alloc(chunk, order, norder);
 		if (address)
 			return address;
 	}
@@ -725,7 +733,8 @@ static u64 buddy_alloc_from_existing_chunks(struct buddy __arena *buddy, int ord
  * Try an allocation from a newly allocated chunk. Also
  * incorporate the chunk into the linked list.
  */
-static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_chunk __arena *chunk, int order)
+static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_chunk __arena *chunk,
+		int order, int norder)
 {
 	unsigned long flags;
 	u64 address;
@@ -733,7 +742,6 @@ static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_
 	if (buddy_lock(buddy, flags))
 		return (u64)NULL;
 
-
 	/*
 	 * Add the chunk into the allocator and try
 	 * to allocate specifically from that chunk.
@@ -741,33 +749,34 @@ static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_
 	chunk->next = buddy->first_chunk;
 	buddy->first_chunk = chunk;
 
-	address = buddy_chunk_alloc(buddy->first_chunk, order);
+	address = buddy_chunk_alloc(buddy->first_chunk, order, norder);
 
 	buddy_unlock(buddy, flags);
 
 	return (u64)address;
 }
-__weak
-void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
+static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
+		int order, size_t norder)
 {
 	void __arena *address = NULL;
+	u8 __arena *object;
 	struct buddy_chunk __arena *chunk;
+	unsigned int alloc_size;
+	unsigned int i, offset;
 	unsigned long flags;
-	int order;
 
 	if (!buddy)
 		return NULL;
 
-	order = size_to_order(size);
-	if (order >= BUDDY_CHUNK_NUM_ORDERS || order < 0) {
-		arena_stderr("invalid order %d (sz %lu)\n", order, size);
+	if (order < 0 || order >= BUDDY_CHUNK_NUM_ORDERS || norder >= BUDDY_CHUNK_NUM_ORDERS - order) {
+		arena_stderr("invalid order %d (norder %lu) (sz %lu)\n", order, norder, size);
 		return NULL;
 	}
 
 	if (buddy_lock(buddy, flags))
 		return NULL;
 
-	address = (u8 __arena *)buddy_alloc_from_existing_chunks(buddy, order);
+	address = (u8 __arena *)buddy_alloc_from_existing_chunks(buddy, order, norder);
 	buddy_unlock(buddy, flags);
 	if (address)
 		goto done;
@@ -775,28 +784,68 @@ void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
 	/* Get a new chunk. */
 	chunk = buddy_chunk_get(buddy);
 	if (chunk)
-		address = (u8 __arena *)buddy_alloc_from_new_chunk(buddy, chunk, order);
+		address = (u8 __arena *)buddy_alloc_from_new_chunk(buddy, chunk, order, norder);
 
 done:
 	/* If we failed to allocate memory, return NULL. */
 	if (!address)
 		return NULL;
 
+	alloc_size = BUDDY_MIN_ALLOC_BYTES << order;
+
 	/*
-	 * Unpoison exactly the amount of bytes requested. If the
-	 * data is smaller than the header, we must poison any
-	 * unused bytes that were part of the header.
+	 * Unpoison exactly the requested bytes in each allocation. Keep
+	 * the padding between the requested size and the rounded buddy
+	 * allocation poisoned.
 	 */
-	if (size < BUDDY_HEADER_OFF + sizeof(struct buddy_header __arena))
-		asan_poison(address + BUDDY_HEADER_OFF, BUDDY_POISONED,
-			    sizeof(struct buddy_header __arena));
+	for (i = zero, offset = zero; i < (1U << norder) && can_loop; i++, offset += alloc_size) {
+		object = (u8 __arena *)address + offset;
+
+		if (size < BUDDY_HEADER_OFF + sizeof(struct buddy_header __arena))
+			asan_poison(object + BUDDY_HEADER_OFF,
+				    BUDDY_POISONED,
+				    sizeof(struct buddy_header __arena));
 
-	asan_unpoison(address, size);
+		asan_unpoison(object, size);
+	}
 
 	return address;
 }
 
-static __always_inline int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr)
+__weak
+int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
+		void __arena * __arena * out)
+{
+	void __arena *address;
+	unsigned int i, off;
+	unsigned int step;
+	int order;
+
+	if (!buddy || !out || norder >= BUDDY_CHUNK_NUM_ORDERS)
+		return -EINVAL;
+
+	order = size_to_order(size);
+	address = buddy_alloc_memory(buddy, size, order, norder);
+	if (!address)
+		return -ENOMEM;
+
+	step = BUDDY_MIN_ALLOC_BYTES << order;
+	for (i = zero, off = zero; i < (1U << norder) && can_loop; i++, off += step)
+		out[i] = &address[off];
+
+	return 0;
+}
+
+__weak
+void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
+{
+	int order;
+
+	order = size_to_order(size);
+	return buddy_alloc_memory(buddy, size, order, 0);
+}
+
+static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr)
 {
 	struct buddy_header __arena *header, *buddy_header;
 	u64 idx, buddy_idx, tmp_idx;
@@ -900,4 +949,38 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 	return ret;
 }
 
+__weak int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *addrs, size_t naddrs)
+{
+	unsigned long flags;
+	unsigned int i;
+	int err;
+	int ret = 0;
+
+	if (!buddy)
+		return -EINVAL;
+
+	if (!naddrs)
+		return 0;
+
+	if (!addrs)
+		return -EINVAL;
+
+	ret = buddy_lock(buddy, flags);
+	if (ret)
+		return ret;
+
+	for (i = zero; i < naddrs && can_loop; i++) {
+		/* NULL pointers are ignored. */
+		if (!addrs[i])
+			continue;
+
+		err = buddy_free_unlocked(buddy, (u64)addrs[i]);
+		ret = ret ?: err;
+	}
+
+	buddy_unlock(buddy, flags);
+
+	return ret;
+}
+
 __weak char _license[] SEC("license") = "GPL";
-- 
2.52.0

[PATCH bpf-next v1 2/7] selftests/bpf: Add a parallel buddy allocator benchmark

[Emil Tsalapatis]

Add a benchmark for measuring buddy allocator latency under concurrent
load. Each worker performs a configurable number of allocations followed
by the corresponding frees.

Vary the worker count, allocation count and allocation size to expose both
lock contention and cache pressure. Add the benchmark to the libarena
runner alongside the existing single-threaded cases.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 tools/testing/selftests/bpf/bench.c           |   2 +
 .../selftests/bpf/benchs/bench_libarena.c     | 100 ++++++++++++++++--
 .../bpf/benchs/run_bench_libarena.sh          |   8 ++
 .../bpf/libarena/benchs/bench_malloc.bpf.c    |  43 ++++++++
 4 files changed, 142 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c
index d5f494184f9d..7d2a3587971f 100644
--- a/tools/testing/selftests/bpf/bench.c
+++ b/tools/testing/selftests/bpf/bench.c
@@ -589,6 +589,7 @@ extern const struct bench bench_bpf_nop;
 extern const struct bench bench_xdp_lb;
 extern const struct bench bench_libarena_malloc;
 extern const struct bench bench_libarena_calloc;
+extern const struct bench bench_libarena_malloc_free;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -675,6 +676,7 @@ static const struct bench *benchs[] = {
 	&bench_xdp_lb,
 	&bench_libarena_malloc,
 	&bench_libarena_calloc,
+	&bench_libarena_malloc_free,
 };
 
 static void find_benchmark(void)
diff --git a/tools/testing/selftests/bpf/benchs/bench_libarena.c b/tools/testing/selftests/bpf/benchs/bench_libarena.c
index 24e432244bf5..1185a471123c 100644
--- a/tools/testing/selftests/bpf/benchs/bench_libarena.c
+++ b/tools/testing/selftests/bpf/benchs/bench_libarena.c
@@ -25,6 +25,10 @@ static struct {
 	struct libarena_bench *skel;
 	int bench_fd;
 	int reset_fd;
+	bool reset_each_run;
+	bool stop;
+	int stopped;
+	int samples;
 } ctx;
 
 enum {
@@ -36,7 +40,7 @@ static const struct argp_option opts[] = {
 	{ "alloc_size", ARG_LIBARENA_ALLOC_SIZE, "BYTES", 0,
 	  "Size of each arena allocation" },
 	{ "nallocs", ARG_LIBARENA_NALLOCS, "ITERS", 0,
-	  "Number of allocation per measurement" },
+	  "Number of allocations per invocation" },
 	{},
 };
 
@@ -68,12 +72,17 @@ const struct argp bench_libarena_argp = {
 	.parser = parse_arg,
 };
 
-static void validate(void)
+static void validate_common(void)
 {
 	if (env.consumer_cnt != 0) {
 		fprintf(stderr, "benchmark doesn't support consumers\n");
 		exit(1);
 	}
+}
+
+static void validate(void)
+{
+	validate_common();
 
 	if (env.producer_cnt != 1) {
 		fprintf(stderr, "benchmark supports exactly one producer\n");
@@ -81,6 +90,21 @@ static void validate(void)
 	}
 }
 
+static void malloc_free_validate(void)
+{
+	validate_common();
+
+	if (env.producer_cnt < 1) {
+		fprintf(stderr, "benchmark requires at least one producer\n");
+		exit(1);
+	}
+
+	if (args.alloc_size < sizeof(void *)) {
+		fprintf(stderr, "allocation size must hold a pointer\n");
+		exit(1);
+	}
+}
+
 static void setup_common(void)
 {
 	struct arena_alloc_reserve_args reserve_args = {
@@ -114,38 +138,55 @@ static void setup_common(void)
 	ctx.skel->bss->bench_alloc_size = args.alloc_size;
 	ctx.skel->bss->bench_nallocs = args.nallocs;
 	ctx.reset_fd = bpf_program__fd(ctx.skel->progs.arena_buddy_reset);
+	ctx.reset_each_run = false;
+	ctx.stop = false;
+	ctx.stopped = 0;
+	ctx.samples = 0;
 }
 
 static void malloc_setup(void)
 {
 	setup_common();
 	ctx.bench_fd = bpf_program__fd(ctx.skel->progs.bench_malloc);
+	ctx.reset_each_run = true;
 }
 
 static void calloc_setup(void)
 {
 	setup_common();
 	ctx.bench_fd = bpf_program__fd(ctx.skel->progs.bench_calloc);
+	ctx.reset_each_run = true;
+}
+
+static void malloc_free_setup(void)
+{
+	setup_common();
+	ctx.bench_fd = bpf_program__fd(ctx.skel->progs.bench_malloc_free);
+	ctx.skel->bss->bench_collect = false;
 }
 
 static void *producer(void *input)
 {
 	int err;
 
-	while (true) {
+	while (!__atomic_load_n(&ctx.stop, __ATOMIC_ACQUIRE)) {
 		err = libarena_run_prog(ctx.bench_fd);
 		if (err) {
 			fprintf(stderr, "libarena benchmark failed: %d\n", err);
 			exit(1);
 		}
 
-		err = libarena_run_prog(ctx.reset_fd);
-		if (err) {
-			fprintf(stderr, "libarena alloc reset failed: %d\n", err);
-			exit(1);
+		if (ctx.reset_each_run) {
+			err = libarena_run_prog(ctx.reset_fd);
+			if (err) {
+				fprintf(stderr, "libarena alloc reset failed: %d\n", err);
+				exit(1);
+			}
 		}
 	}
 
+	__atomic_add_fetch(&ctx.stopped, 1, __ATOMIC_RELEASE);
+
 	return NULL;
 }
 
@@ -155,6 +196,15 @@ static void measure(struct bench_res *res)
 	res->hits = atomic_swap(&ctx.skel->bss->bench_hits, 0);
 }
 
+static void malloc_free_measure(struct bench_res *res)
+{
+	(void)res;
+
+	if (++ctx.samples == env.warmup_sec)
+		__atomic_store_n(&ctx.skel->bss->bench_collect, true,
+				 __ATOMIC_RELAXED);
+}
+
 static void report_progress(int iter, struct bench_res *res, long delta_ns)
 {
 	double latency_ns = 0.0;
@@ -162,7 +212,7 @@ static void report_progress(int iter, struct bench_res *res, long delta_ns)
 	if (res->hits)
 		latency_ns = res->duration_ns / (double)res->hits;
 
-	printf("Iter %3d (%7.3lfus): latency %8.3lf ns/op (%ld allocations)\n",
+	printf("Iter %3d (%7.3lfus): latency %8.3lf ns/allocation (%ld allocations)\n",
 	       iter, (delta_ns - 1000000000) / 1000.0, latency_ns, res->hits);
 }
 
@@ -182,9 +232,27 @@ static void report_final(struct bench_res res[], int res_cnt)
 		return;
 	}
 
-	printf("Summary: %.3lf ns/op, %.0lf invocations for %u allocations/invocation)\n",
-	       duration_ns / (double)hits, hits / (double)res_cnt,
-	       ctx.skel->bss->bench_nallocs);
+	printf("Summary: %.3lf ns/allocation (%ld allocations)\n",
+	       duration_ns / (double)hits, hits);
+}
+
+static void malloc_free_report_final(struct bench_res res[], int res_cnt)
+{
+	struct bench_res final = {};
+
+	(void)res;
+	(void)res_cnt;
+
+	__atomic_store_n(&ctx.stop, true, __ATOMIC_RELEASE);
+	while (__atomic_load_n(&ctx.stopped, __ATOMIC_ACQUIRE) != env.producer_cnt)
+		usleep(1000);
+
+	final.duration_ns = __atomic_load_n(
+		&ctx.skel->bss->bench_duration_ns, __ATOMIC_RELAXED);
+	final.hits = __atomic_load_n(
+		&ctx.skel->bss->bench_hits, __ATOMIC_RELAXED);
+
+	report_final(&final, 1);
 }
 
 const struct bench bench_libarena_malloc = {
@@ -208,3 +276,13 @@ const struct bench bench_libarena_calloc = {
 	.report_progress = report_progress,
 	.report_final = report_final,
 };
+
+const struct bench bench_libarena_malloc_free = {
+	.name = "libarena-malloc-free",
+	.argp = &bench_libarena_argp,
+	.validate = malloc_free_validate,
+	.setup = malloc_free_setup,
+	.producer_thread = producer,
+	.measure = malloc_free_measure,
+	.report_final = malloc_free_report_final,
+};
diff --git a/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh b/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh
index 10afe4d52ebf..5d5f84310b26 100755
--- a/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh
+++ b/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh
@@ -29,3 +29,11 @@ printf "\t-------------------\n"
 			"$($RUN_BENCH --alloc_size "$size" --nallocs "$nallocs" libarena-calloc)"
 	done
 done
+
+header "libarena parallel malloc/free\n"
+
+for producers in 1 2 4 8; do
+	summarize_libarena "$producers producers:" \
+		"$($RUN_BENCH -a -p "$producers" --alloc_size 64 --nallocs 1000 \
+		libarena-malloc-free)"
+done
diff --git a/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c b/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c
index e06397dc9a40..3c9235c56b00 100644
--- a/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c
@@ -9,6 +9,7 @@ u32 bench_alloc_size;
 u32 bench_nallocs;
 long bench_hits;
 long bench_duration_ns;
+bool bench_collect;
 
 SEC("syscall")
 int bench_malloc(void)
@@ -49,3 +50,45 @@ int bench_calloc(void)
 	__sync_add_and_fetch(&bench_hits, i);
 	return 0;
 }
+
+struct bench_alloc {
+	struct bench_alloc __arena *next;
+};
+
+SEC("syscall")
+int bench_malloc_free(void)
+{
+	struct bench_alloc __arena *next, *obj, *head = NULL;
+	u64 duration_ns = 0, start_ns;
+	u32 i, nallocs;
+	bool collect;
+
+	collect = READ_ONCE(bench_collect);
+	for (i = zero; i < bench_nallocs && can_loop; i++) {
+		start_ns = bpf_ktime_get_ns();
+		obj = arena_malloc(bench_alloc_size);
+		duration_ns += bpf_ktime_get_ns() - start_ns;
+		if (!obj)
+			break;
+
+		obj->next = head;
+		head = obj;
+	}
+	nallocs = i;
+
+	for (i = zero; head && can_loop; i++) {
+		next = head->next;
+		arena_free(head);
+		head = next;
+	}
+
+	if (nallocs != bench_nallocs)
+		return -ENOMEM;
+
+	if (!collect)
+		return 0;
+
+	__sync_add_and_fetch(&bench_duration_ns, duration_ns);
+	__sync_add_and_fetch(&bench_hits, nallocs);
+	return 0;
+}
-- 
2.52.0

[PATCH bpf-next v1 3/7] selftests/bpf: libarena: Add buddy per-CPU caches

[Emil Tsalapatis]

Every small allocation currently reaches the central buddy allocator and
takes its lock. This serializes otherwise independent callers and touches
the buddy metadata on every allocation and free.

Add a fixed-size LIFO array for each cached order and CPU. Embed the cache
state in struct buddy and allocate each CPU's packed cache from the buddy
during initialization. Cache the eight smallest allocation orders and
retain the aggregate capacity of the two magazines this replaces.

Allocations pop from the local array and frees push onto it without taking
the buddy lock. Empty and full arrays fall through to the central buddy
allocator. Packed arrays avoid linked-list traversal and separately
allocated magazine containers on the fast path.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../bpf/libarena/include/libarena/buddy.h     |   3 +
 .../libarena/include/libarena/buddy_cache.h   |  45 +++++
 .../bpf/libarena/selftests/test_buddy.bpf.c   |   9 +
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 172 +++++++++++++++++-
 4 files changed, 224 insertions(+), 5 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
index 0ac888be365c..9150a9d22cce 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
@@ -2,6 +2,8 @@
 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
 #pragma once
 
+#include <libarena/buddy_cache.h>
+
 enum buddy_consts {
 	/*
 	 * Minimum allocation is 1 << BUDDY_MIN_ALLOC_SHIFT.
@@ -69,6 +71,7 @@ struct buddy {
 	struct buddy_chunk __arena *first_chunk;		/* Pointer to the chunk linked list. */
 	arena_spinlock_t lock;			/* Allocator lock */
 	u64 vaddr;				/* Allocation into reserved vaddr */
+	struct buddy_cache_state cache_state;
 };
 
 #ifdef __BPF__
diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
new file mode 100644
index 000000000000..769d966686f5
--- /dev/null
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
@@ -0,0 +1,45 @@
+// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
+/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+#pragma once
+
+/* Constants related to the buddy allocator's object caches. */
+enum buddy_cache_consts {
+	/*
+	 * Do not cache larger allocations to avoid excessive
+	 * memory consumption from the per-cpu lists.
+	 */
+	BUDDY_CACHE_NUM_ORDERS = 1 << 3,
+
+	/*
+	 * Just like arena spinlocks, hardcode percpu state to a maximum number of CPUs.
+	 * Since arena spinlocks are a hard dependency, use the exact same limit.
+	 */
+	BUDDY_CACHE_MAX_CPUS = 1024,
+
+	/*
+	 * Items transferred as one batch. This must remain a power of two because
+	 * buddy_alloc_bulk() expresses the number of objects as an order.
+	 */
+	BUDDY_CACHE_BATCH_SIZE = 8,
+
+	/*
+	 * Objects retained locally for each allocation order.
+	 */
+	BUDDY_CACHE_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 2,
+};
+
+struct buddy_cache_order {
+	u32 elems;
+	u32 __pad;
+	void __arena *objects[BUDDY_CACHE_CAPACITY];
+} __attribute__((aligned(64)));
+
+/* Dynamically allocated packed per-CPU slot slab. */
+struct buddy_cache {
+	struct buddy_cache_order orders[BUDDY_CACHE_NUM_ORDERS];
+};
+
+struct buddy_cache_state {
+	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
+	bool valid;
+};
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 5628f0987012..1a1856befeae 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
@@ -34,9 +34,18 @@ __weak int test_buddy_create(void)
 		if (ret)
 			return ret;
 
+#ifndef BPF_ARENA_ASAN
+		if (!buddy.cache_state.valid) {
+			buddy_destroy(&buddy);
+			return -EINVAL;
+		}
+#endif
+
 		ret = buddy_destroy(&buddy);
 		if (ret)
 			return ret;
+		if (buddy.cache_state.valid)
+			return -EINVAL;
 	}
 
 	return 0;
diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index 72b9ea3ac7d5..ce05e3e58eba 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -4,9 +4,13 @@
 #include <libarena/common.h>
 #include <libarena/asan.h>
 #include <libarena/buddy.h>
+#include <libarena/buddy_cache.h>
 
 #include <bpf_arena_spin_lock.h>
 
+_Static_assert(BUDDY_CACHE_MAX_CPUS == _Q_MAX_CPUS,
+	       "buddy caches must cover every CPU arena spinlocks support");
+
 /*
  * Buddy allocator arena-based implementation.
  *
@@ -38,18 +42,116 @@
  * and their allocation state. It also includes the freelist
  * heads for the allocation itself.
  */
+static u8 idx_get_order(struct buddy_chunk __arena *chunk, u64 idx);
+static u64 arena_next_pow2(__u64 n);
+static u64 size_to_order(size_t size);
+static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
+					int order, size_t norder);
+static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr);
+
+#define buddy_lock(buddy, flags) (arena_spin_lock_irqsave(&(buddy)->lock, (flags)))
+#define buddy_unlock(buddy, flags) (arena_spin_unlock_irqrestore(&(buddy)->lock, (flags)))
+
+/*
+ * Per-CPU caching is disabled in ASAN builds because its additional call-chain
+ * stack usage causes instrumented programs to exceed BPF's 512-byte stack limit.
+ */
+#ifdef BPF_ARENA_ASAN
+#define DISABLE_CACHE_IF_ASAN(...) do { return (__VA_ARGS__); } while (0)
+#else
+#define DISABLE_CACHE_IF_ASAN(...)
+#endif
+
+static __always_inline void __arena *
+buddy_cache_pop(struct buddy_cache __arena *cache, int order)
+{
+	struct buddy_cache_order __arena *slots;
+	void __arena *addr;
+	u32 elems;
+
+	slots = &cache->orders[order];
+	elems = READ_ONCE(slots->elems);
+	if (!elems)
+		return NULL;
+
+	addr = READ_ONCE(slots->objects[elems - 1]);
+	WRITE_ONCE(slots->elems, elems - 1);
+
+	return addr;
+}
+
+static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
+					    int order, void __arena *obj)
+{
+	struct buddy_cache_order __arena *slots;
+	u32 elems;
+
+	slots = &cache->orders[order];
+	elems = READ_ONCE(slots->elems);
+	if (elems >= BUDDY_CACHE_CAPACITY)
+		return -ENOMEM;
+
+	WRITE_ONCE(slots->objects[elems], obj);
+	WRITE_ONCE(slots->elems, elems + 1);
+
+	return 0;
+}
+
+void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	struct buddy_cache __arena *cache;
+	unsigned int cpu;
+
+	DISABLE_CACHE_IF_ASAN(NULL);
+
+	if (order >= BUDDY_CACHE_NUM_ORDERS)
+		return NULL;
+
+	cpu = bpf_get_smp_processor_id();
+	cache = state->percpu[cpu];
+
+	return buddy_cache_pop(cache, order);
+}
+
+/* Retrieve the order of an allocation from the address. */
+static int buddy_cache_get_order(void __arena *addr)
+{
+	struct buddy_chunk __arena *chunk;
+	u64 idx;
+
+	chunk = (void __arena *)((u64)addr & ~BUDDY_CHUNK_OFFSET_MASK);
+	idx = ((u64)addr & BUDDY_CHUNK_OFFSET_MASK) / BUDDY_MIN_ALLOC_BYTES;
+
+	return idx_get_order(chunk, idx);
+}
+
+int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	struct buddy_cache __arena *cache;
+	unsigned int cpu;
+	int order;
+
+	DISABLE_CACHE_IF_ASAN(-EINVAL);
+
+	order = buddy_cache_get_order(addr);
+	if (order >= BUDDY_CACHE_NUM_ORDERS)
+		return -EINVAL;
+
+	cpu = bpf_get_smp_processor_id();
+	cache = state->percpu[cpu];
 
+	return buddy_cache_push(cache, order, addr);
+}
 
 enum {
 	BUDDY_POISONED = (s8)0xef,
 
 	/* Number of pages to be allocated per chunk. */
-	BUDDY_CHUNK_PAGES	= BUDDY_CHUNK_BYTES / __PAGE_SIZE
+	BUDDY_CHUNK_PAGES	= BUDDY_CHUNK_BYTES / __PAGE_SIZE,
 };
 
-#define buddy_lock(buddy, flags) (arena_spin_lock_irqsave(&(buddy)->lock, (flags)))
-#define buddy_unlock(buddy, flags) (arena_spin_unlock_irqrestore(&(buddy)->lock, (flags)))
-
 /*
  * Reserve part of the arena address space for the allocator. We use
  * this to get aligned addresses for the chunks, since the arena
@@ -557,6 +659,46 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy)
 	return chunk;
 }
 
+static int buddy_cache_state_init(struct buddy __arena *buddy)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	struct buddy_cache __arena *cache;
+	unsigned int cpu, order;
+	int ret;
+
+	DISABLE_CACHE_IF_ASAN(0);
+
+	if (CONFIG_NR_CPUS > BUDDY_CACHE_MAX_CPUS)
+		return -E2BIG;
+
+	WRITE_ONCE(state->valid, false);
+
+	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++) {
+		ret = buddy_alloc_bulk(buddy, sizeof(*cache), 0,
+				       (void __arena * __arena *)&state->percpu[cpu]);
+		if (ret)
+			return ret;
+
+		cache = state->percpu[cpu];
+		for (order = zero; order < BUDDY_CACHE_NUM_ORDERS && can_loop; order++)
+			WRITE_ONCE(cache->orders[order].elems, 0);
+	}
+
+	WRITE_ONCE(state->valid, true);
+
+	return 0;
+}
+
+static void buddy_cache_state_destroy(struct buddy __arena *buddy)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	unsigned int cpu;
+
+	WRITE_ONCE(state->valid, false);
+	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++)
+		WRITE_ONCE(state->percpu[cpu], NULL);
+}
+
 __weak int buddy_init(struct buddy __arena *buddy)
 {
 	struct buddy_chunk __arena *chunk;
@@ -590,7 +732,16 @@ __weak int buddy_init(struct buddy __arena *buddy)
 
 	buddy_unlock(buddy, flags);
 
-	return chunk ? 0 : -ENOMEM;
+	if (!chunk)
+		return -ENOMEM;
+
+	ret = buddy_cache_state_init(buddy);
+	if (ret) {
+		buddy_destroy(buddy);
+		return ret;
+	}
+
+	return 0;
 }
 
 /*
@@ -606,6 +757,8 @@ __weak int buddy_destroy(struct buddy __arena *buddy)
 	if (!buddy)
 		return -EINVAL;
 
+	buddy_cache_state_destroy(buddy);
+
 	/*
 	 * Traverse all buddy chunks and free them back to the arena
 	 * with the same granularity they were allocated with.
@@ -839,9 +992,14 @@ int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
 __weak
 void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
 {
+	void __arena *address;
 	int order;
 
 	order = size_to_order(size);
+	address = buddy_cache_alloc(buddy, order);
+	if (address)
+		return address;
+
 	return buddy_alloc_memory(buddy, size, order, 0);
 }
 
@@ -938,6 +1096,10 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 	if (!addr)
 		return 0;
 
+	ret = buddy_cache_free(buddy, addr);
+	if (!ret)
+		return 0;
+
 	ret = buddy_lock(buddy, flags);
 	if (ret)
 		return ret;
-- 
2.52.0

[PATCH bpf-next v1 4/7] selftests/bpf: libarena: Handle NMI reentrancy

[Emil Tsalapatis]

An NMI can interrupt a cache operation and access the same per-CPU array.
BPF programs also only disable migration, so another task can preempt a
cache operation and run on the same CPU. Allowing the nested operation to
proceed would let it overwrite the interrupted operation's state.

Track active cache operations per CPU and reject nested access, following
the model used by the main BPF memory allocator. Claim the CPU with a
cmpxchg so that two tasks cannot both observe it as idle. An allocation
from NMI context succeeds only when the local cache can satisfy it without
taking the buddy lock.

When an NMI free cannot use the local cache, link the object onto an
intrusive deferred-free list. A later allocator operation from a safe
context drains that list while holding the buddy lock.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../bpf/libarena/include/libarena/buddy.h     |   3 +
 .../libarena/include/libarena/buddy_cache.h   |   6 +
 .../bpf/libarena/selftests/test_buddy.bpf.c   |   2 +
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 188 +++++++++++++++++-
 4 files changed, 189 insertions(+), 10 deletions(-)

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
index 9150a9d22cce..655b3f5624bf 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
@@ -51,6 +51,8 @@ struct buddy_header {
 	u32 next_index; /* Same for the next allocation. */
 };
 
+struct buddy_deferred_free;
+
 /*
  * We bring memory into the allocator 1 MiB at a time.
  */
@@ -72,6 +74,7 @@ struct buddy {
 	arena_spinlock_t lock;			/* Allocator lock */
 	u64 vaddr;				/* Allocation into reserved vaddr */
 	struct buddy_cache_state cache_state;
+	struct buddy_deferred_free __arena *deferred_free;
 };
 
 #ifdef __BPF__
diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
index 769d966686f5..cad198ac732d 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
@@ -43,3 +43,9 @@ struct buddy_cache_state {
 	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
 	bool valid;
 };
+
+/* Per-CPU guard against nested or preempting cache operations. */
+
+struct __attribute__((aligned(64))) buddy_cache_active {
+	unsigned int value;
+};
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 1a1856befeae..6d123ec052b0 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
@@ -44,6 +44,8 @@ __weak int test_buddy_create(void)
 		ret = buddy_destroy(&buddy);
 		if (ret)
 			return ret;
+		if (buddy.deferred_free)
+			return -EINVAL;
 		if (buddy.cache_state.valid)
 			return -EINVAL;
 	}
diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index ce05e3e58eba..85d670b8762b 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -7,6 +7,7 @@
 #include <libarena/buddy_cache.h>
 
 #include <bpf_arena_spin_lock.h>
+#include <bpf_experimental.h>
 
 _Static_assert(BUDDY_CACHE_MAX_CPUS == _Q_MAX_CPUS,
 	       "buddy caches must cover every CPU arena spinlocks support");
@@ -48,6 +49,14 @@ static u64 size_to_order(size_t size);
 static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
 					int order, size_t norder);
 static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr);
+static bool buddy_deferred_free_pending(struct buddy __arena *buddy);
+static int buddy_deferred_free_complete(struct buddy __arena *buddy);
+static struct buddy_cache_active active[BUDDY_CACHE_MAX_CPUS];
+
+struct buddy_cache_ctx {
+	struct buddy_cache __arena *cache;
+	struct buddy_cache_active *active;
+};
 
 #define buddy_lock(buddy, flags) (arena_spin_lock_irqsave(&(buddy)->lock, (flags)))
 #define buddy_unlock(buddy, flags) (arena_spin_unlock_irqrestore(&(buddy)->lock, (flags)))
@@ -62,6 +71,31 @@ static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr);
 #define DISABLE_CACHE_IF_ASAN(...)
 #endif
 
+static __always_inline int
+buddy_cache_enter(struct buddy_cache_state __arena *state,
+		  struct buddy_cache_ctx *ctx)
+{
+	unsigned int cpu;
+
+	/*
+	 * No support for cache operations from contexts that interrupted or
+	 * preempted an in-flight operation on the same CPU, just like the
+	 * kernel's BPF memory allocator.
+	 */
+	cpu = bpf_get_smp_processor_id();
+	ctx->cache = state->percpu[cpu];
+	ctx->active = &active[cpu];
+	if (cmpxchg(&ctx->active->value, 0, 1))
+		return -EAGAIN;
+
+	return 0;
+}
+
+static __always_inline void buddy_cache_exit(struct buddy_cache_ctx *ctx)
+{
+	smp_store_release(&ctx->active->value, 0);
+}
+
 static __always_inline void __arena *
 buddy_cache_pop(struct buddy_cache __arena *cache, int order)
 {
@@ -100,18 +134,21 @@ static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
 void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
 {
 	struct buddy_cache_state __arena *state = &buddy->cache_state;
-	struct buddy_cache __arena *cache;
-	unsigned int cpu;
+	struct buddy_cache_ctx ctx;
+	void __arena *address = NULL;
 
 	DISABLE_CACHE_IF_ASAN(NULL);
 
 	if (order >= BUDDY_CACHE_NUM_ORDERS)
 		return NULL;
 
-	cpu = bpf_get_smp_processor_id();
-	cache = state->percpu[cpu];
+	if (buddy_cache_enter(state, &ctx))
+		return NULL;
+
+	address = buddy_cache_pop(ctx.cache, order);
+	buddy_cache_exit(&ctx);
 
-	return buddy_cache_pop(cache, order);
+	return address;
 }
 
 /* Retrieve the order of an allocation from the address. */
@@ -129,9 +166,9 @@ static int buddy_cache_get_order(void __arena *addr)
 int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
 {
 	struct buddy_cache_state __arena *state = &buddy->cache_state;
-	struct buddy_cache __arena *cache;
-	unsigned int cpu;
+	struct buddy_cache_ctx ctx;
 	int order;
+	int ret = 0;
 
 	DISABLE_CACHE_IF_ASAN(-EINVAL);
 
@@ -139,10 +176,13 @@ int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
 	if (order >= BUDDY_CACHE_NUM_ORDERS)
 		return -EINVAL;
 
-	cpu = bpf_get_smp_processor_id();
-	cache = state->percpu[cpu];
+	if (buddy_cache_enter(state, &ctx))
+		return -EAGAIN;
+
+	ret = buddy_cache_push(ctx.cache, order, addr);
+	buddy_cache_exit(&ctx);
 
-	return buddy_cache_push(cache, order, addr);
+	return ret;
 }
 
 enum {
@@ -707,6 +747,7 @@ __weak int buddy_init(struct buddy __arena *buddy)
 
 	if (!asan_ready())
 		return -EINVAL;
+	buddy->deferred_free = NULL;
 
 	/* Reserve enough address space to ensure allocations are aligned. */
 	ret = buddy_reserve_arena_vaddr(buddy);
@@ -777,6 +818,7 @@ __weak int buddy_destroy(struct buddy __arena *buddy)
 
 	/* Clear all fields. */
 	buddy->first_chunk = NULL;
+	buddy->deferred_free = NULL;
 
 	return 0;
 }
@@ -926,9 +968,19 @@ static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size
 		return NULL;
 	}
 
+	if (bpf_in_nmi())
+		return NULL;
+
 	if (buddy_lock(buddy, flags))
 		return NULL;
 
+	if (unlikely(buddy_deferred_free_pending(buddy))) {
+		if (buddy_deferred_free_complete(buddy)) {
+			buddy_unlock(buddy, flags);
+			return NULL;
+		}
+	}
+
 	address = (u8 __arena *)buddy_alloc_from_existing_chunks(buddy, order, norder);
 	buddy_unlock(buddy, flags);
 	if (address)
@@ -1084,6 +1136,98 @@ static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr)
 	return 0;
 }
 
+static bool buddy_deferred_free_pending(struct buddy __arena *buddy)
+{
+	return buddy->deferred_free != NULL;
+}
+
+static void buddy_deferred_free_start(struct buddy __arena *buddy, void __arena *addr)
+{
+	void __arena *head;
+	void __arena * __arena *new;
+
+	/*
+	 * Make a linked list by chaining the allocations into a linked list.
+	 * Possible because allocations are 16 bytes minimum and so fit a pointer.
+	 */
+	new = (void __arena * __arena *)addr;
+	asan_unpoison(addr, sizeof(void *));
+	do  {
+		head = buddy->deferred_free;
+		*new = head;
+	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
+			 head, (void __arena *)new) != head && can_loop);
+}
+
+static void buddy_deferred_free_start_bulk(struct buddy __arena *buddy,
+		 void __arena * __arena *addrs, size_t naddrs)
+{
+	void __arena *head, *first, *last, *addr;
+	unsigned int i;
+
+	/* Create a linked list locally. */
+	first = NULL;
+	last = NULL;
+	for (i = zero; i < naddrs && can_loop; i++) {
+		addr = addrs[i];
+		if (!addr)
+			continue;
+
+		asan_unpoison(addr, sizeof(void *));
+
+		if (!first)
+			first = addr;
+		else
+			*(void __arena * __arena *)last = addr;
+
+		last = addr;
+	}
+
+	if (!first)
+		return;
+
+	/*
+	 * Make a linked list by chaining the allocations into a linked list.
+	 * Possible because allocations are 16 bytes minimum and so fit a pointer.
+	 */
+	do  {
+		head = buddy->deferred_free;
+		*(void __arena * __arena *)last = head;
+	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
+			 head, first) != head && can_loop);
+}
+
+static int buddy_deferred_free_complete(struct buddy __arena *buddy)
+{
+	void __arena *head, *old;
+	int ret = 0, err;
+
+	do {
+		head = buddy->deferred_free;
+		if (!head)
+			break;
+		old = head;
+
+		/*
+		 * The cmpxchg is safe because we never pop from the list
+		 * without holding the buddy lock. The next pointer of
+		 * the element then cannot have been gotten invalidated.
+		 */
+
+	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
+			 old, NULL) != old && can_loop);
+
+	while (head && can_loop) {
+		old = head;
+		head = *(void __arena * __arena *)head;
+
+		err = buddy_free_unlocked(buddy, (u64)old);
+		ret = ret ?: err;
+	}
+
+	return ret;
+}
+
 __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 {
 	unsigned long flags;
@@ -1100,12 +1244,25 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 	if (!ret)
 		return 0;
 
+	if (bpf_in_nmi()) {
+		buddy_deferred_free_start(buddy, addr);
+		return 0;
+	}
+
 	ret = buddy_lock(buddy, flags);
 	if (ret)
 		return ret;
 
 	ret = buddy_free_unlocked(buddy, (u64)addr);
 
+	/* Drain any frees stranded during an NMI. */
+	if (unlikely(buddy_deferred_free_pending(buddy))) {
+		ret = buddy_deferred_free_complete(buddy);
+		if (ret)
+			goto out_unlock;
+	}
+
+out_unlock:
 	buddy_unlock(buddy, flags);
 
 	return ret;
@@ -1127,6 +1284,11 @@ __weak int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *
 	if (!addrs)
 		return -EINVAL;
 
+	if (bpf_in_nmi()) {
+		buddy_deferred_free_start_bulk(buddy, addrs, naddrs);
+		return 0;
+	}
+
 	ret = buddy_lock(buddy, flags);
 	if (ret)
 		return ret;
@@ -1140,6 +1302,12 @@ __weak int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *
 		ret = ret ?: err;
 	}
 
+	/* Drain any frees stranded during an NMI. */
+	if (unlikely(buddy_deferred_free_pending(buddy))) {
+		err = buddy_deferred_free_complete(buddy);
+		ret = ret ?: err;
+	}
+
 	buddy_unlock(buddy, flags);
 
 	return ret;
-- 
2.52.0

[PATCH bpf-next v1 5/7] selftests/bpf: libarena: Refill local caches in batches

[Emil Tsalapatis]

Cache hits avoid the central lock, but every cache miss still asks the
buddy allocator for one object. A sequence of misses therefore repeats
the same locking and metadata work.

Allocate eight objects with buddy_alloc_bulk() on a local-cache miss.
Return one object directly and retain the other seven in the per-CPU LIFO
array. This amortizes buddy locking and metadata updates over subsequent
allocations. Skip the refill in NMI context, where the backend allocator
cannot safely take its lock.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 44 +++++++++++++++++++
 1 file changed, 44 insertions(+)

diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index 85d670b8762b..3b760b1fc66e 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -185,6 +185,43 @@ int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
 	return ret;
 }
 
+static void __arena *buddy_cache_refill(struct buddy __arena *buddy,
+					size_t size, int order)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	struct buddy_cache_order __arena *slots;
+	struct buddy_cache_ctx ctx;
+	void __arena *address = NULL;
+	int ret;
+
+	DISABLE_CACHE_IF_ASAN(NULL);
+
+	if (order >= BUDDY_CACHE_NUM_ORDERS)
+		return NULL;
+
+	if (buddy_cache_enter(state, &ctx))
+		return NULL;
+
+	/* A free may have populated the cache between the miss and refill. */
+	address = buddy_cache_pop(ctx.cache, order);
+	if (address)
+		goto done;
+
+	slots = &ctx.cache->orders[order];
+	ret = buddy_alloc_bulk(buddy, size, arena_fls(BUDDY_CACHE_BATCH_SIZE) - 1,
+				(void __arena * __arena *)slots->objects);
+	if (ret)
+		goto done;
+
+	address = slots->objects[BUDDY_CACHE_BATCH_SIZE - 1];
+	WRITE_ONCE(slots->elems, BUDDY_CACHE_BATCH_SIZE - 1);
+
+done:
+	buddy_cache_exit(&ctx);
+
+	return address;
+}
+
 enum {
 	BUDDY_POISONED = (s8)0xef,
 
@@ -1052,6 +1089,13 @@ void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
 	if (address)
 		return address;
 
+	if (bpf_in_nmi())
+		return NULL;
+
+	address = buddy_cache_refill(buddy, size, order);
+	if (address)
+		return address;
+
 	return buddy_alloc_memory(buddy, size, order, 0);
 }
 
-- 
2.52.0

[PATCH bpf-next v1 6/7] selftests/bpf: libarena: Add a transfer cache

[Emil Tsalapatis]

Per-CPU caches keep hot objects local, but they cannot move spare capacity
between CPUs. A producer can overflow its local cache into the buddy while
another CPU underflows and refills from the buddy, causing avoidable lock
and metadata traffic.

Add a fixed-size shared transfer array for each cached order, protected by
a per-order lock. Move one batch from a full local cache to the transfer
array and consume one batch on a local miss. Fall back to the buddy when
the shared array is full or empty.

Embed the transfer arrays in the buddy cache state so this intermediate
layer requires no dynamically allocated containers.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../libarena/include/libarena/buddy_cache.h   |  10 ++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 123 +++++++++++++++++-
 2 files changed, 130 insertions(+), 3 deletions(-)

diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
index cad198ac732d..9fa90097dc98 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h
@@ -26,6 +26,9 @@ enum buddy_cache_consts {
 	 * Objects retained locally for each allocation order.
 	 */
 	BUDDY_CACHE_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 2,
+
+	/* Number of objects shared between per-CPU caches for each order. */
+	BUDDY_TRANSFER_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 8,
 };
 
 struct buddy_cache_order {
@@ -39,8 +42,15 @@ struct buddy_cache {
 	struct buddy_cache_order orders[BUDDY_CACHE_NUM_ORDERS];
 };
 
+struct buddy_transfer_order {
+	arena_spinlock_t lock;
+	u32 elems;
+	void __arena *objects[BUDDY_TRANSFER_CAPACITY];
+} __attribute__((aligned(64)));
+
 struct buddy_cache_state {
 	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
+	struct buddy_transfer_order transfer[BUDDY_CACHE_NUM_ORDERS];
 	bool valid;
 };
 
diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index 3b760b1fc66e..2248631392b2 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -131,6 +131,78 @@ static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
 	return 0;
 }
 
+static int buddy_transfer_take_batch(struct buddy_cache_state __arena *state,
+				     int order,
+				     struct buddy_cache_order __arena *slots)
+{
+	struct buddy_transfer_order __arena *transfer;
+	unsigned long flags;
+	u32 elems, start;
+	unsigned int i;
+	int ret = 0;
+
+	transfer = &state->transfer[order];
+	if (arena_spin_lock_irqsave(&transfer->lock, flags))
+		return -EAGAIN;
+
+	elems = READ_ONCE(transfer->elems);
+	if (elems < BUDDY_CACHE_BATCH_SIZE) {
+		ret = -ENOENT;
+		goto out_unlock;
+	}
+
+	start = elems - BUDDY_CACHE_BATCH_SIZE;
+	for (i = zero; i < BUDDY_CACHE_BATCH_SIZE && can_loop; i++)
+		WRITE_ONCE(slots->objects[i],
+			   READ_ONCE(transfer->objects[start + i]));
+
+	WRITE_ONCE(transfer->elems, start);
+	WRITE_ONCE(slots->elems, BUDDY_CACHE_BATCH_SIZE);
+
+out_unlock:
+	arena_spin_unlock_irqrestore(&transfer->lock, flags);
+	return ret;
+}
+
+static int buddy_transfer_put_batch(struct buddy_cache_state __arena *state,
+				    int order,
+				    struct buddy_cache_order __arena *slots)
+{
+	struct buddy_transfer_order __arena *transfer;
+	unsigned long flags;
+	u32 elems, local_elems, start;
+	unsigned int i;
+	int ret = 0;
+
+	transfer = &state->transfer[order];
+	if (arena_spin_lock_irqsave(&transfer->lock, flags))
+		return -EAGAIN;
+
+	elems = READ_ONCE(transfer->elems);
+	if (elems > BUDDY_TRANSFER_CAPACITY - BUDDY_CACHE_BATCH_SIZE) {
+		ret = -ENOMEM;
+		goto out_unlock;
+	}
+
+	local_elems = READ_ONCE(slots->elems);
+	if (local_elems < BUDDY_CACHE_BATCH_SIZE) {
+		ret = -EINVAL;
+		goto out_unlock;
+	}
+
+	start = local_elems - BUDDY_CACHE_BATCH_SIZE;
+	for (i = zero; i < BUDDY_CACHE_BATCH_SIZE && can_loop; i++)
+		WRITE_ONCE(transfer->objects[elems + i],
+			   READ_ONCE(slots->objects[start + i]));
+
+	WRITE_ONCE(slots->elems, start);
+	WRITE_ONCE(transfer->elems, elems + BUDDY_CACHE_BATCH_SIZE);
+
+out_unlock:
+	arena_spin_unlock_irqrestore(&transfer->lock, flags);
+	return ret;
+}
+
 void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
 {
 	struct buddy_cache_state __arena *state = &buddy->cache_state;
@@ -185,6 +257,38 @@ int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
 	return ret;
 }
 
+static int buddy_cache_transfer_free(struct buddy __arena *buddy,
+				     void __arena *addr)
+{
+	struct buddy_cache_state __arena *state = &buddy->cache_state;
+	struct buddy_cache_order __arena *slots;
+	struct buddy_cache_ctx ctx;
+	int order, ret;
+
+	DISABLE_CACHE_IF_ASAN(-EINVAL);
+
+	order = buddy_cache_get_order(addr);
+	if (order >= BUDDY_CACHE_NUM_ORDERS)
+		return -EINVAL;
+
+	if (buddy_cache_enter(state, &ctx))
+		return -EAGAIN;
+
+	/* An allocation may have made room since the first local attempt. */
+	ret = buddy_cache_push(ctx.cache, order, addr);
+	if (!ret)
+		goto done;
+
+	slots = &ctx.cache->orders[order];
+	ret = buddy_transfer_put_batch(state, order, slots);
+	if (!ret)
+		ret = buddy_cache_push(ctx.cache, order, addr);
+
+done:
+	buddy_cache_exit(&ctx);
+	return ret;
+}
+
 static void __arena *buddy_cache_refill(struct buddy __arena *buddy,
 					size_t size, int order)
 {
@@ -208,6 +312,12 @@ static void __arena *buddy_cache_refill(struct buddy __arena *buddy,
 		goto done;
 
 	slots = &ctx.cache->orders[order];
+	ret = buddy_transfer_take_batch(state, order, slots);
+	if (!ret) {
+		address = buddy_cache_pop(ctx.cache, order);
+		goto done;
+	}
+
 	ret = buddy_alloc_bulk(buddy, size, arena_fls(BUDDY_CACHE_BATCH_SIZE) - 1,
 				(void __arena * __arena *)slots->objects);
 	if (ret)
@@ -745,10 +855,12 @@ static int buddy_cache_state_init(struct buddy __arena *buddy)
 
 	DISABLE_CACHE_IF_ASAN(0);
 
+	WRITE_ONCE(state->valid, false);
 	if (CONFIG_NR_CPUS > BUDDY_CACHE_MAX_CPUS)
 		return -E2BIG;
 
-	WRITE_ONCE(state->valid, false);
+	for (order = zero; order < BUDDY_CACHE_NUM_ORDERS && can_loop; order++)
+		WRITE_ONCE(state->transfer[order].elems, 0);
 
 	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++) {
 		ret = buddy_alloc_bulk(buddy, sizeof(*cache), 0,
@@ -762,18 +874,19 @@ static int buddy_cache_state_init(struct buddy __arena *buddy)
 	}
 
 	WRITE_ONCE(state->valid, true);
-
 	return 0;
 }
 
 static void buddy_cache_state_destroy(struct buddy __arena *buddy)
 {
 	struct buddy_cache_state __arena *state = &buddy->cache_state;
-	unsigned int cpu;
+	unsigned int cpu, order;
 
 	WRITE_ONCE(state->valid, false);
 	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++)
 		WRITE_ONCE(state->percpu[cpu], NULL);
+	for (order = zero; order < BUDDY_CACHE_NUM_ORDERS && can_loop; order++)
+		WRITE_ONCE(state->transfer[order].elems, 0);
 }
 
 __weak int buddy_init(struct buddy __arena *buddy)
@@ -1293,6 +1406,10 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 		return 0;
 	}
 
+	ret = buddy_cache_transfer_free(buddy, addr);
+	if (!ret)
+		return 0;
+
 	ret = buddy_lock(buddy, flags);
 	if (ret)
 		return ret;
-- 
2.52.0

[PATCH bpf-next v1 7/7] selftests/bpf: libarena: Cover buddy cache fast paths

[Emil Tsalapatis]

Add coverage for the bulk allocation helpers. Check object stride, bounds
and contents, then free the objects in a non-sequential order to exercise
their independent metadata and coalescing.

Exercise local-cache initialization, batch refill, LIFO reuse and capacity
overflow. Verify that overflow moves a batch into the transfer cache and
that a later underflow consumes it without reaching the buddy allocator.

Document and test that explicit bulk allocations bypass the per-CPU cache.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 266 ++++++++++++++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    |   8 +-
 2 files changed, 273 insertions(+), 1 deletion(-)

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 6d123ec052b0..f14c2945d1e1 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
@@ -4,6 +4,7 @@
 #include <libarena/common.h>
 
 #include <libarena/asan.h>
+#include <libarena/buddy_cache.h>
 #include <libarena/buddy.h>
 
 extern struct buddy __arena buddy;
@@ -17,6 +18,24 @@ struct segarr_entry {
 #define SEGARRLEN (512)
 static struct segarr_entry __arena segarr[SEGARRLEN];
 static void __arena *ptrs[17];
+
+enum buddy_alloc_path_test_consts {
+	TEST_BULK_NORDER = 3,
+	TEST_BULK_ITEMS = 1 << TEST_BULK_NORDER,
+	TEST_BULK_SIZE = 17,
+	TEST_BULK_STEP = 32,
+	TEST_CACHE_ORDER = 2,
+	TEST_CACHE_SIZE = BUDDY_MIN_ALLOC_BYTES << TEST_CACHE_ORDER,
+};
+
+struct buddy_alloc_path_test_storage {
+	void __arena *bulk[BUDDY_CACHE_CAPACITY + 1];
+	void __arena *to_free[BUDDY_CACHE_CAPACITY + 1];
+	void __arena *drain[BUDDY_CACHE_BATCH_SIZE];
+};
+
+static struct buddy_alloc_path_test_storage __arena alloc_path_test;
+
 size_t __arena alloc_sizes[] = { 3, 17, 1025, 129, 16350, 333, 9, 517 };
 size_t __arena alloc_multiple_sizes[] = { 3, 17, 1025, 129, 16350, 333, 9, 517, 2099 };
 size_t __arena alloc_free_sizes[] = { 3, 17, 64, 129, 256, 333, 512, 517 };
@@ -221,4 +240,251 @@ __weak int test_buddy_alignment(void)
 	return 0;
 }
 
+SEC("syscall")
+__weak int test_buddy_bulk_alloc_free(void)
+{
+	const size_t uncached_size =
+		(BUDDY_MIN_ALLOC_BYTES << (BUDDY_CACHE_NUM_ORDERS - 1)) + 1;
+	void __arena *sentinel = (void __arena *)&alloc_path_test;
+	u8 __arena *mem;
+	unsigned int i, j, idx;
+	int ret, destroy_ret;
+
+	ret = buddy_init(&buddy);
+	if (ret)
+		return ret;
+
+	/*
+	 * A 17-byte request rounds up to a 32-byte buddy allocation. Verify
+	 * that the bulk allocator returns every child at the expected stride,
+	 * without writing beyond the requested output array.
+	 */
+	alloc_path_test.bulk[TEST_BULK_ITEMS] = sentinel;
+	ret = buddy_alloc_bulk(&buddy, TEST_BULK_SIZE, TEST_BULK_NORDER,
+			       alloc_path_test.bulk);
+	if (ret)
+		goto out;
+	if (alloc_path_test.bulk[TEST_BULK_ITEMS] != sentinel) {
+		ret = -EOVERFLOW;
+		goto out;
+	}
+
+	for (i = zero; i < TEST_BULK_ITEMS && can_loop; i++) {
+		mem = alloc_path_test.bulk[i];
+		if (!mem) {
+			ret = -ENOMEM;
+			goto out;
+		}
+		if (i && (u64)mem !=
+			 (u64)alloc_path_test.bulk[i - 1] + TEST_BULK_STEP) {
+			ret = -EINVAL;
+			goto out;
+		}
+
+		for (j = zero; j < TEST_BULK_SIZE && can_loop; j++)
+			mem[j] = (u8)(i + 1);
+	}
+
+	for (i = zero; i < TEST_BULK_ITEMS && can_loop; i++) {
+		mem = alloc_path_test.bulk[i];
+		for (j = zero; j < TEST_BULK_SIZE && can_loop; j++) {
+			if (mem[j] != (u8)(i + 1)) {
+				ret = -EINVAL;
+				goto out;
+			}
+		}
+
+		/* Five is coprime to eight, producing a permutation of all items. */
+		idx = (i * 5) & (TEST_BULK_ITEMS - 1);
+		alloc_path_test.to_free[i] = alloc_path_test.bulk[idx];
+	}
+	alloc_path_test.to_free[TEST_BULK_ITEMS] = NULL;
+
+	ret = buddy_free_bulk(&buddy, alloc_path_test.to_free,
+			      TEST_BULK_ITEMS + 1);
+	if (ret)
+		goto out;
+
+	/*
+	 * Order eight is immediately above the per-CPU cache range. Free a bulk
+	 * allocation one child at a time in a non-sequential order to exercise
+	 * independent metadata and coalescing without the cache intercepting it.
+	 */
+	ret = buddy_alloc_bulk(&buddy, uncached_size, TEST_BULK_NORDER,
+			       alloc_path_test.bulk);
+	if (ret)
+		goto out;
+
+	for (i = zero; i < TEST_BULK_ITEMS && can_loop; i++) {
+		idx = (i * 5) & (TEST_BULK_ITEMS - 1);
+		ret = buddy_free(&buddy, alloc_path_test.bulk[idx]);
+		if (ret)
+			goto out;
+	}
+
+out:
+	destroy_ret = buddy_destroy(&buddy);
+	return ret ?: destroy_ret;
+}
+
+SEC("syscall")
+__weak int test_buddy_cache_paths(void)
+{
+#ifdef BPF_ARENA_ASAN
+	return 0;
+#else
+	struct buddy_cache_state __arena *state;
+	struct buddy_cache __arena *cache;
+	struct buddy_cache_order __arena *slots;
+	struct buddy_transfer_order __arena *transfer;
+	void __arena *direct, *cached, *reused, *refilled, *overflow_reused;
+	void __arena *transferred;
+	unsigned int cpu, i;
+	int ret, destroy_ret;
+
+	ret = buddy_init(&buddy);
+	if (ret)
+		return ret;
+
+	state = &buddy.cache_state;
+
+	cpu = bpf_get_smp_processor_id();
+	cache = state->percpu[cpu];
+	if (!cache) {
+		ret = -EINVAL;
+		goto out;
+	}
+	slots = &cache->orders[TEST_CACHE_ORDER];
+	transfer = &state->transfer[TEST_CACHE_ORDER];
+	if (READ_ONCE(slots->elems) || READ_ONCE(transfer->elems)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* A miss bulk-refills the local order and returns one object directly. */
+	direct = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (!direct || READ_ONCE(slots->elems) != BUDDY_CACHE_BATCH_SIZE - 1) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	/* Subsequent allocations and frees stay on the packed local stack. */
+	cached = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (!cached || READ_ONCE(slots->elems) != BUDDY_CACHE_BATCH_SIZE - 2) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	ret = buddy_free(&buddy, cached);
+	if (ret)
+		goto out;
+	reused = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (reused != cached) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* Drain the local stack, then verify that the next miss refills it. */
+	for (i = zero; i < BUDDY_CACHE_BATCH_SIZE - 2 && can_loop; i++) {
+		alloc_path_test.drain[i] = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+		if (!alloc_path_test.drain[i]) {
+			ret = -ENOMEM;
+			goto out;
+		}
+	}
+	if (READ_ONCE(slots->elems)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	refilled = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (!refilled ||
+	    READ_ONCE(slots->elems) != BUDDY_CACHE_BATCH_SIZE - 1) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* Bulk allocation bypasses the cache. Fill the remaining local slots. */
+	ret = buddy_alloc_bulk(&buddy, TEST_CACHE_SIZE,
+			       arena_fls(BUDDY_CACHE_CAPACITY) - 1,
+			       alloc_path_test.bulk);
+	if (ret)
+		goto out;
+
+	ret = buddy_free(&buddy, alloc_path_test.bulk[0]);
+	if (ret)
+		goto out;
+
+	ret = buddy_free(&buddy, alloc_path_test.bulk[1]);
+	if (ret)
+		goto out;
+
+	for (i = 2;
+	     i <= BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE && can_loop;
+	     i++) {
+		ret = buddy_free(&buddy, alloc_path_test.bulk[i]);
+		if (ret)
+			goto out;
+	}
+	if (READ_ONCE(slots->elems) != BUDDY_CACHE_CAPACITY) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* A free beyond local capacity transfers a batch to the shared cache. */
+	ret = buddy_free(&buddy,
+			 alloc_path_test.bulk[BUDDY_CACHE_CAPACITY -
+					      BUDDY_CACHE_BATCH_SIZE + 1]);
+	if (ret)
+		goto out;
+	if (READ_ONCE(slots->elems) !=
+			BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE + 1 ||
+	    READ_ONCE(transfer->elems) != BUDDY_CACHE_BATCH_SIZE) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	overflow_reused = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (overflow_reused != alloc_path_test.bulk[BUDDY_CACHE_CAPACITY -
+							 BUDDY_CACHE_BATCH_SIZE + 1] ||
+	    READ_ONCE(slots->elems) !=
+			BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* Drain locally, then consume the batch without touching buddy. */
+	for (i = zero;
+	     i < BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE && can_loop;
+	     i++) {
+		alloc_path_test.drain[i] = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+		if (!alloc_path_test.drain[i]) {
+			ret = -ENOMEM;
+			goto out;
+		}
+	}
+	transferred = buddy_alloc(&buddy, TEST_CACHE_SIZE);
+	if (transferred != alloc_path_test.bulk[BUDDY_CACHE_CAPACITY -
+						     BUDDY_CACHE_BATCH_SIZE] ||
+	    READ_ONCE(slots->elems) != BUDDY_CACHE_BATCH_SIZE - 1 ||
+	    READ_ONCE(transfer->elems)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* Interior pointers are rejected without consuming the allocation. */
+	i = BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE + 2;
+	if (!buddy_free(&buddy, (u8 __arena *)alloc_path_test.bulk[i] +
+				 BUDDY_MIN_ALLOC_BYTES)) {
+		ret = -EINVAL;
+		goto out;
+	}
+	ret = buddy_free(&buddy, alloc_path_test.bulk[i]);
+
+out:
+	destroy_ret = buddy_destroy(&buddy);
+	return ret ?: destroy_ret;
+#endif
+}
+
 __weak char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
index 2248631392b2..796dacf3c6a2 100644
--- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
@@ -318,7 +318,8 @@ static void __arena *buddy_cache_refill(struct buddy __arena *buddy,
 		goto done;
 	}
 
-	ret = buddy_alloc_bulk(buddy, size, arena_fls(BUDDY_CACHE_BATCH_SIZE) - 1,
+	ret = buddy_alloc_bulk(buddy, size,
+				arena_fls(BUDDY_CACHE_BATCH_SIZE) - 1,
 				(void __arena * __arena *)slots->objects);
 	if (ret)
 		goto done;
@@ -1179,6 +1180,11 @@ int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
 	if (!buddy || !out || norder >= BUDDY_CHUNK_NUM_ORDERS)
 		return -EINVAL;
 
+	/*
+	 * Bulk allocations bypass the per-cpu caches and reserve one buddy
+	 * block covering all returned objects. The buddy metadata records
+	 * each object separately so it can later be freed independently.
+	 */
 	order = size_to_order(size);
 	address = buddy_alloc_memory(buddy, size, order, norder);
 	if (!address)
-- 
2.52.0

Re: [PATCH bpf-next v1 4/7] selftests/bpf: libarena: Handle NMI reentrancy

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] selftests/bpf: buddy_free() overwrites error with deferred free status
--

commit 6b8ade1832d5b23360c4e6c8d75625a18af4fe8e
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Handle NMI reentrancy

This commit adds per-CPU reentrancy protection to the libarena buddy cache
and defers frees issued from NMI context onto an intrusive list when the
local cache cannot be used.

> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index ce05e3e58ebae..85d670b8762bb 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c

[ ... ]

> @@ -1100,12 +1244,25 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
>  	if (!ret)
>  		return 0;
>  
> +	if (bpf_in_nmi()) {
> +		buddy_deferred_free_start(buddy, addr);
> +		return 0;
> +	}
> +
>  	ret = buddy_lock(buddy, flags);
>  	if (ret)
>  		return ret;
>  
>  	ret = buddy_free_unlocked(buddy, (u64)addr);
>  
> +	/* Drain any frees stranded during an NMI. */
> +	if (unlikely(buddy_deferred_free_pending(buddy))) {
> +		ret = buddy_deferred_free_complete(buddy);
> +		if (ret)
> +			goto out_unlock;
> +	}
> +
> +out_unlock:
>  	buddy_unlock(buddy, flags);
>  
>  	return ret;

[Severity: Medium]
In buddy_free() in tools/testing/selftests/bpf/libarena/src/buddy.bpf.c, if
buddy_free_unlocked(buddy, (u64)addr) fails (for example, returning -EINVAL
on an unaligned or invalid address) while buddy_deferred_free_pending(buddy)
is true, calling buddy_deferred_free_complete(buddy) unconditionally
overwrites ret. If draining the deferred list succeeds, ret is set to 0 and
the error from buddy_free_unlocked() is lost.

Also, the goto out_unlock statement jumps directly to the immediately
adjacent out_unlock label.

Should buddy_free() preserve any error from buddy_free_unlocked() in the
same way buddy_free_bulk() does:

	if (unlikely(buddy_deferred_free_pending(buddy))) {
		err = buddy_deferred_free_complete(buddy);
		ret = ret ?: err;
	}

and drop the redundant out_unlock label?

[ ... ]

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

Re: [PATCH bpf-next v1 7/7] selftests/bpf: libarena: Cover buddy cache fast paths

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] selftests/bpf: buddy_cache_get_order() accepts interior pointers on free
- [Low] selftests/bpf: error return clobbered in buddy_free() during NMI drain
--

commit 05ed9b95b2e617e5142c6f1c186bbaa3122d07f7
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Cover buddy cache fast paths

This commit adds BPF selftests covering bulk allocations and per-CPU and
transfer cache fast paths in libarena's buddy allocator, and documents that
buddy_alloc_bulk() bypasses the per-CPU caches.

> 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 6d123ec052b0f..f14c2945d1e11 100644
> --- a/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c

[ ... ]

> @@ -221,4 +240,251 @@ __weak int test_buddy_alignment(void)

[ ... ]

> +SEC("syscall")
> +__weak int test_buddy_cache_paths(void)
> +{

[ ... ]

> +	/* Bulk allocation bypasses the cache. Fill the remaining local slots. */
> +	ret = buddy_alloc_bulk(&buddy, TEST_CACHE_SIZE,
> +			       arena_fls(BUDDY_CACHE_CAPACITY) - 1,
> +			       alloc_path_test.bulk);
> +	if (ret)
> +		goto out;

[ ... ]

> +	/* Interior pointers are rejected without consuming the allocation. */
> +	i = BUDDY_CACHE_CAPACITY - BUDDY_CACHE_BATCH_SIZE + 2;
> +	if (!buddy_free(&buddy, (u8 __arena *)alloc_path_test.bulk[i] +
> +				 BUDDY_MIN_ALLOC_BYTES)) {
> +		ret = -EINVAL;
> +		goto out;
> +	}

[Severity: Medium]
Will this interior pointer check in test_buddy_cache_paths() fail when
BPF_ARENA_ASAN is disabled because buddy_cache_free() accepts the interior
pointer as an order-0 object?

When buddy_alloc_bulk() allocates the TEST_CACHE_SIZE (order 2) objects via
buddy_chunk_alloc() in tools/testing/selftests/bpf/libarena/src/buddy.bpf.c,
only the head granule of each object has its order and allocated bit recorded:

	for (i = zero, idx = retidx; i < (1U << order_allocs) && can_loop; i++) {
		if (idx_set_order(chunk, idx, order_req))
			return (u64)NULL;

		if (idx_set_allocated(chunk, idx, true))
			return (u64)NULL;

		idx += 1U << order_req;
	}

The interior granule at alloc_path_test.bulk[i] + BUDDY_MIN_ALLOC_BYTES
(idx + 1) retains its zero-initialized order nibble (0) and allocated bit (0).

When test_buddy_cache_paths() passes that interior pointer to buddy_free(),
the call chain:

  buddy_free()
    -> buddy_cache_free()
      -> buddy_cache_get_order()

reads the order directly without checking alignment or whether idx is marked
allocated in chunk->allocated:

static int buddy_cache_get_order(void __arena *addr)
{
	struct buddy_chunk __arena *chunk;
	u64 idx;

	chunk = (void __arena *)((u64)addr & ~BUDDY_CHUNK_OFFSET_MASK);
	idx = ((u64)addr & BUDDY_CHUNK_OFFSET_MASK) / BUDDY_MIN_ALLOC_BYTES;

	return idx_get_order(chunk, idx);
}

Because idx_get_order() returns 0 for the unallocated interior granule and
the order-0 per-CPU cache has room, buddy_cache_push() pushes the interior
pointer into ctx.cache->orders[0] and buddy_free() returns 0, causing
test_buddy_cache_paths() to return -EINVAL.

Should buddy_cache_get_order() (or buddy_cache_free() and
buddy_cache_transfer_free()) verify that addr is aligned to
BUDDY_MIN_ALLOC_BYTES and that idx is marked allocated via idx_is_allocated()
before accepting the pointer into the cache?

> +	ret = buddy_free(&buddy, alloc_path_test.bulk[i]);

[Severity: Low]
In tools/testing/selftests/bpf/libarena/src/buddy.bpf.c, can buddy_free()
lose the error returned by buddy_free_unlocked() when a deferred NMI free is
pending?

Looking at buddy_free():

	ret = buddy_free_unlocked(buddy, (u64)addr);

	/* Drain any frees stranded during an NMI. */
	if (unlikely(buddy_deferred_free_pending(buddy))) {
		ret = buddy_deferred_free_complete(buddy);
		if (ret)
			goto out_unlock;
	}

If buddy_free_unlocked() returns an error (such as -EINVAL for an invalid or
interior pointer that bypassed the cache) while buddy_deferred_free_pending()
is true, buddy_deferred_free_complete() overwrites ret with 0 on success.

By contrast, buddy_free_bulk() in the same file preserves any earlier error:

	/* Drain any frees stranded during an NMI. */
	if (unlikely(buddy_deferred_free_pending(buddy))) {
		err = buddy_deferred_free_complete(buddy);
		ret = ret ?: err;
	}

Should buddy_free() preserve ret in the same way when draining deferred frees?

> +
> +out:
> +	destroy_ret = buddy_destroy(&buddy);
> +	return ret ?: destroy_ret;
> +#endif
> +}

[ ... ]

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

Re: [PATCH bpf-next v1 3/7] selftests/bpf: libarena: Add buddy per-CPU caches

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] selftests/bpf: missing cache validity and NULL checks in buddy.bpf.c
- [Medium] selftests/bpf: missing pointer validation in buddy_cache_free()
- [Medium] selftests/bpf: out-of-bounds write in buddy_cache_state_destroy()
--

commit 8dee6e0e331ae6f1872b723dff5e251350292c90
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Add buddy per-CPU caches

This commit introduces per-CPU LIFO array caches in struct buddy for the
eight smallest allocation orders so small allocations and frees can bypass
the central buddy allocator lock on the fast path.

> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index 72b9ea3ac7d53..ce05e3e58ebae 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c

[ ... ]

> @@ -38,18 +42,116 @@
>   * and their allocation state. It also includes the freelist
>   * heads for the allocation itself.
>   */

[ ... ]

> +static __always_inline void __arena *
> +buddy_cache_pop(struct buddy_cache __arena *cache, int order)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	void __arena *addr;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (!elems)
> +		return NULL;
> +
> +	addr = READ_ONCE(slots->objects[elems - 1]);
> +	WRITE_ONCE(slots->elems, elems - 1);
> +
> +	return addr;
> +}
> +
> +static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
> +					    int order, void __arena *obj)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (elems >= BUDDY_CACHE_CAPACITY)
> +		return -ENOMEM;
> +
> +	WRITE_ONCE(slots->objects[elems], obj);
> +	WRITE_ONCE(slots->elems, elems + 1);
> +
> +	return 0;
> +}
> +
> +void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu;
> +
> +	DISABLE_CACHE_IF_ASAN(NULL);
> +
> +	if (order >= BUDDY_CACHE_NUM_ORDERS)
> +		return NULL;
> +
> +	cpu = bpf_get_smp_processor_id();
> +	cache = state->percpu[cpu];
> +
> +	return buddy_cache_pop(cache, order);
> +}

[Severity: Medium]
Should buddy_cache_alloc() and buddy_cache_free() check that buddy is
non-NULL, that READ_ONCE(state->valid) is true, and that cache is non-NULL
before calling buddy_cache_pop() or buddy_cache_push()?

In buddy_alloc(), buddy_cache_alloc(buddy, order) is now called before
buddy_alloc_memory() checks if (!buddy):

buddy_alloc()
    order = size_to_order(size);
    address = buddy_cache_alloc(buddy, order);
    if (address)
        return address;
    return buddy_alloc_memory(buddy, size, order, 0);

Calling buddy_alloc(NULL, size) for a cached order (order <
BUDDY_CACHE_NUM_ORDERS) will therefore dereference &buddy->cache_state in
buddy_cache_alloc().

In addition, buddy_cache_state_init() and buddy_cache_state_destroy()
maintain state->valid with WRITE_ONCE(), but neither this commit nor the
follow-up commits in the series check state->valid or cache != NULL in
buddy.bpf.c. If buddy_alloc() or buddy_free() is called while cache_state is
uninitialized or destroyed (where state->valid is false and
state->percpu[cpu] is NULL), buddy_cache_pop() and buddy_cache_push() will
dereference NULL at arena address 0. Because BPF exception handling on
reserved page 0 zeroes loads and ignores stores, buddy_cache_push() will
read elems as 0, ignore the stores, and return 0, causing buddy_free() to
silently drop the freed block instead of returning it to the central buddy
allocator.

> +
> +/* Retrieve the order of an allocation from the address. */
> +static int buddy_cache_get_order(void __arena *addr)
> +{
> +	struct buddy_chunk __arena *chunk;
> +	u64 idx;
> +
> +	chunk = (void __arena *)((u64)addr & ~BUDDY_CHUNK_OFFSET_MASK);
> +	idx = ((u64)addr & BUDDY_CHUNK_OFFSET_MASK) / BUDDY_MIN_ALLOC_BYTES;
> +
> +	return idx_get_order(chunk, idx);
> +}
> +
> +int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu;
> +	int order;
> +
> +	DISABLE_CACHE_IF_ASAN(-EINVAL);
> +
> +	order = buddy_cache_get_order(addr);
> +	if (order >= BUDDY_CACHE_NUM_ORDERS)
> +		return -EINVAL;
> +
> +	cpu = bpf_get_smp_processor_id();
> +	cache = state->percpu[cpu];
>  
> +	return buddy_cache_push(cache, order, addr);
> +}

[Severity: Medium]
What prevents buddy_cache_free() from accepting unaligned, interior, or
unallocated pointers before buddy_free_unlocked() can validate them?

In buddy_free(), buddy_cache_free() is invoked prior to
buddy_free_unlocked():

buddy_free()
    ret = buddy_cache_free(buddy, addr);
    if (!ret)
        return 0;
    ...
    ret = buddy_free_unlocked(buddy, (u64)addr);

While buddy_free_unlocked() checks that addr is aligned to
BUDDY_MIN_ALLOC_BYTES and verifies that idx is marked allocated via
idx_set_allocated(chunk, idx, false), buddy_cache_get_order() divides by
BUDDY_MIN_ALLOC_BYTES and reads idx_get_order(chunk, idx) without checking
either alignment or chunk->allocated.

When a chunk is initialized in buddy_chunk_get(), chunk->orders is
zero-initialized, and buddy_chunk_alloc() only sets the order and allocated
bit at the head index idx of each allocated block (advancing by idx += 1U <<
order_req), leaving interior sub-block indices with allocated == 0 and
order == 0.

If a caller passes an interior pointer such as
(u8 __arena *)alloc_path_test.bulk[i] + BUDDY_MIN_ALLOC_BYTES (as tested by
test_buddy_cache_paths() in the follow-up commit "selftests/bpf: libarena:
Cover buddy cache fast paths"), buddy_cache_get_order() reads order 0 at
idx + 1, and buddy_cache_free() pushes the interior pointer into the order-0
per-CPU cache and returns 0 instead of failing with -EINVAL. Likewise, an
unaligned pointer inside an allocated cached-order block has its low bits
truncated by the division in buddy_cache_get_order() and is pushed unaligned
into the per-CPU cache, corrupting subsequent buddy_alloc() returns.

[ ... ]

> @@ -557,6 +659,46 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy)
>  	return chunk;
>  }
>  
> +static int buddy_cache_state_init(struct buddy __arena *buddy)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu, order;
> +	int ret;
> +
> +	DISABLE_CACHE_IF_ASAN(0);
> +
> +	if (CONFIG_NR_CPUS > BUDDY_CACHE_MAX_CPUS)
> +		return -E2BIG;
> +
> +	WRITE_ONCE(state->valid, false);
> +
> +	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++) {
> +		ret = buddy_alloc_bulk(buddy, sizeof(*cache), 0,
> +				       (void __arena * __arena *)&state->percpu[cpu]);
> +		if (ret)
> +			return ret;
> +
> +		cache = state->percpu[cpu];
> +		for (order = zero; order < BUDDY_CACHE_NUM_ORDERS && can_loop; order++)
> +			WRITE_ONCE(cache->orders[order].elems, 0);
> +	}
> +
> +	WRITE_ONCE(state->valid, true);
> +
> +	return 0;
> +}
> +
> +static void buddy_cache_state_destroy(struct buddy __arena *buddy)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	unsigned int cpu;
> +
> +	WRITE_ONCE(state->valid, false);
> +	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++)
> +		WRITE_ONCE(state->percpu[cpu], NULL);
> +}

[Severity: Medium]
Can buddy_cache_state_destroy() overflow state->percpu[] when CONFIG_NR_CPUS
is greater than BUDDY_CACHE_MAX_CPUS (1024)?

While buddy_cache_state_init() checks if (CONFIG_NR_CPUS >
BUDDY_CACHE_MAX_CPUS) and returns -E2BIG, buddy_init() handles that failure
by calling buddy_destroy() -> buddy_cache_state_destroy():

buddy_init()
    ret = buddy_cache_state_init(buddy);
    if (ret) {
        buddy_destroy(buddy);
        return ret;
    }

In addition, arena_buddy_destroy() and arena_buddy_reset() in common.bpf.c
call buddy_destroy() directly before buddy_init(). Since
buddy_cache_state_destroy() loops up to CONFIG_NR_CPUS without bounding
against BUDDY_CACHE_MAX_CPUS, won't it write past the end of
state->percpu[BUDDY_CACHE_MAX_CPUS] and clobber adjacent arena memory on
kernels built with CONFIG_NR_CPUS > 1024?

[ ... ]

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

Re: [PATCH bpf-next v1 2/7] selftests/bpf: Add a parallel buddy allocator benchmark

[bot+bpf-ci]

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

> selftests/bpf: Add a parallel buddy allocator benchmark

TL;DR: Commit message only: it claims worker count, allocation count and size
are varied but the script sweeps only producers, and omits the changed
malloc/calloc output. Plus a nit on unneeded (void) casts.

>     selftests/bpf: Add a parallel buddy allocator benchmark
>
>     Add a benchmark for measuring buddy allocator latency under concurrent
>     load. Each worker performs a configurable number of allocations followed
>     by the corresponding frees.
>     Vary the worker count, allocation count and allocation size to expose both
>     lock contention and cache pressure. Add the benchmark to the libarena
>     runner alongside the existing single-threaded cases.
>     Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>

This isn't a bug, but the changelog says the worker count, allocation count
and allocation size are varied, while the new section of
run_bench_libarena.sh only sweeps the producer count:

  for producers in 1 2 4 8; do
	summarize_libarena "$producers producers:" \
		"$($RUN_BENCH -a -p "$producers" --alloc_size 64 --nallocs 1000 \
		libarena-malloc-free)"
  done

The changelog also doesn't mention that the output of the existing
libarena-malloc and libarena-calloc benchmarks changes.  The progress line
goes from "ns/op" to "ns/allocation", the Summary line drops the
invocations and allocations/invocation fields in favour of a total
allocation count, and the --nallocs help text changes as well.

Could the changelog say which parameters the runner actually sweeps, and
mention that the libarena-malloc/calloc output changes too (and why)?

> diff --git a/tools/testing/selftests/bpf/benchs/bench_libarena.c b/tools/testing/selftests/bpf/benchs/bench_libarena.c
> --- a/tools/testing/selftests/bpf/benchs/bench_libarena.c
> +++ b/tools/testing/selftests/bpf/benchs/bench_libarena.c

[ ... ]

> @@ -155,6 +196,15 @@ static void measure(struct bench_res *res)
>  	res->hits = atomic_swap(&ctx.skel->bss->bench_hits, 0);
>  }
>
> +static void malloc_free_measure(struct bench_res *res)
> +{
> +	(void)res;
> +
> +	if (++ctx.samples == env.warmup_sec)
> +		__atomic_store_n(&ctx.skel->bss->bench_collect, true,
> +				 __ATOMIC_RELAXED);
> +}

[ ... ]

> @@ -182,9 +232,27 @@ static void report_final(struct bench_res res[], int res_cnt)

[ ... ]

> +static void malloc_free_report_final(struct bench_res res[], int res_cnt)
> +{
> +	struct bench_res final = {};
> +
> +	(void)res;
> +	(void)res_cnt;

This isn't a bug, but are the (void)res and (void)res_cnt casts needed here
and in malloc_free_measure()?  The other bench callbacks, including
producer() in this file, leave unused parameters as they are.

[ ... ]


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

Re: [PATCH bpf-next v1 3/7] selftests/bpf: libarena: Add buddy per-CPU caches

[bot+bpf-ci]

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

> selftests/bpf: libarena: Add buddy per-CPU caches

TL;DR:
- Per-CPU cache pop/push may race under preemption or IRQ, handing one object
  to two callers (fixed later in series)
- Changelog mentions nonexistent replaced magazines
- Macro with hidden return is a nit

>     selftests/bpf: libarena: Add buddy per-CPU caches
>
>     Every small allocation currently reaches the central buddy allocator and
>     takes its lock. This serializes otherwise independent callers and touches
>     the buddy metadata on every allocation and free.
>
>     Add a fixed-size LIFO array for each cached order and CPU. Embed the cache
>     state in struct buddy and allocate each CPU's packed cache from the buddy
>     during initialization. Cache the eight smallest allocation orders and
>     retain the aggregate capacity of the two magazines this replaces.
>
>     Allocations pop from the local array and frees push onto it without taking
>     the buddy lock. Empty and full arrays fall through to the central buddy
>     allocator. Packed arrays avoid linked-list traversal and separately
>     allocated magazine containers on the fast path.
>
>     Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>

The changelog says the new arrays "retain the aggregate capacity of the two
magazines this replaces" and avoid "separately allocated magazine
containers".  Is that wording accurate?

The parent tree has no magazine-based cache.  Looking at the parent's
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c, there is no cache code
at all, and "git log -S magazine -- tools/testing/selftests/bpf/libarena"
finds no commits.  "git grep -i magazine" on HEAD~1, HEAD and 871a40830e46
also returns nothing.

This commit adds the first per-CPU cache rather than replacing anything, so
the sentence has nothing to refer to in git history.  Is it left over from an
earlier revision of the series?

That sentence is also the only stated reason for BUDDY_CACHE_CAPACITY =
BUDDY_CACHE_BATCH_SIZE * 2 in buddy_cache.h.  BUDDY_CACHE_BATCH_SIZE is not
used for any batch transfer until 3d2fe8494239 ("selftests/bpf: libarena:
Refill local caches in batches").

Could the changelog explain the capacity choice directly, and move the
history of earlier revisions below the --- line?

> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index 72b9ea3ac7d5..ce05e3e58eba 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c

[ ... ]

> @@ -38,18 +42,116 @@
>  * and their allocation state. It also includes the freelist
>  * heads for the allocation itself.
>  */

[ ... ]

> +/*
> + * Per-CPU caching is disabled in ASAN builds because its additional call-chain
> + * stack usage causes instrumented programs to exceed BPF's 512-byte stack limit.
> + */
> +#ifdef BPF_ARENA_ASAN
> +#define DISABLE_CACHE_IF_ASAN(...) do { return (__VA_ARGS__); } while (0)
> +#else
> +#define DISABLE_CACHE_IF_ASAN(...)
> +#endif
> +

This isn't a bug, but DISABLE_CACHE_IF_ASAN() hides a return inside a macro
that looks like a function call.  It is used as:

    DISABLE_CACHE_IF_ASAN(NULL);     in buddy_cache_alloc()
    DISABLE_CACHE_IF_ASAN(-EINVAL);  in buddy_cache_free()
    DISABLE_CACHE_IF_ASAN(0);        in buddy_cache_state_init()

Documentation/process/coding-style.rst (chapter 12, "Things to avoid when
using macros") lists macros that affect control flow first, because they exit
the caller unexpectedly.  Elsewhere in libarena, ASAN-only behaviour uses a
plain "#ifdef BPF_ARENA_ASAN" (asan.h, asan.bpf.c, test_buddy.bpf.c,
test_asan_buddy.bpf.c).

Would an explicit "#ifdef BPF_ARENA_ASAN / return ...; / #endif" at each
site, or a static const bool checked with if, make the early exit visible to
the reader?

> +static __always_inline void __arena *
> +buddy_cache_pop(struct buddy_cache __arena *cache, int order)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	void __arena *addr;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (!elems)
> +		return NULL;
> +
> +	addr = READ_ONCE(slots->objects[elems - 1]);
> +	WRITE_ONCE(slots->elems, elems - 1);
> +
> +	return addr;
> +}
> +
> +static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
> +					    int order, void __arena *obj)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (elems >= BUDDY_CACHE_CAPACITY)
> +		return -ENOMEM;
> +
> +	WRITE_ONCE(slots->objects[elems], obj);
> +	WRITE_ONCE(slots->elems, elems + 1);
> +
> +	return 0;
> +}
> +
> +void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
> +{

[ ... ]

> +	cpu = bpf_get_smp_processor_id();
> +	cache = state->percpu[cpu];
> +
> +	return buddy_cache_pop(cache, order);
> +}

Can two operations on the same CPU interleave here and hand out the same
object twice?

buddy_cache_alloc() and buddy_cache_free() pick the cache with
bpf_get_smp_processor_id().  buddy_cache_pop() and buddy_cache_push() then do
a separate load of slots->elems, an access to the slot, and a store of the
new count.  Nothing disables preemption or IRQs, and no atomic is used.  The
buddy lock path this bypasses uses arena_spin_lock_irqsave(), which disables
IRQs and preemption.

BPF programs only disable migration.  bpf_prog_test_run_syscall() calls
bpf_prog_run_pin_on_cpu(), which does migrate_disable() and nothing more, and
SEC("syscall") programs are sleepable.  tools/testing/selftests/bpf/
config.x86_64 sets CONFIG_PREEMPT=y.

The parallel benchmark from the previous commit runs

    bench -a -p 8 ... libarena-malloc-free

and bench's next_cpu() returns cpu_set->next_cpu++ % env.nr_cpus.  On a VM
with fewer than 8 CPUs, two producers are therefore pinned to the same CPU
and can preempt each other.  An NMI or IRQ-context BPF program that uses the
same buddy can also interrupt the sequence.

Interleaving on one CPU, starting with elems = 5:

    task A: buddy_cache_pop(): elems = 5, addr = objects[4] = X
            <preempted before WRITE_ONCE(slots->elems, 4)>
    task B: buddy_cache_pop(): elems = 5, addr = objects[4] = X, elems = 4
            returns X
    task A: WRITE_ONCE(slots->elems, 4), returns X

Both tasks now own X.  In bench_malloc_free() both write obj->next into it,
which corrupts their lists and then double-frees X back into the cache.

A push interleaved with a pop has the same effect: the pusher's late store of
elems + 1 re-exposes a slot that was already popped.  Pushes that race each
other lose objects.

This appears to be fixed later in the series by c455eb9bee8a ("selftests/bpf:
libarena: Handle NMI reentrancy"), which adds a per-CPU cmpxchg guard around
the cache operations.  Its message states: "BPF programs also only disable
migration, so another task can preempt a cache operation and run on the same
CPU. Allowing the nested operation to proceed would let it overwrite the
interrupted operation's state."


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

Re: [PATCH bpf-next v1 4/7] selftests/bpf: libarena: Handle NMI reentrancy

[bot+bpf-ci]

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

> selftests/bpf: libarena: Handle NMI reentrancy

TL;DR: Nits only: buddy_deferred_free_start() and
buddy_deferred_free_start_bulk() repeat the same cmpxchg push loop and
comment, which could share a helper; one comment is misplaced.

> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index ce05e3e58eba..85d670b8762b 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c

[ ... ]

> @@ -1084,6 +1136,98 @@ static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr)
> [ ... ]
> +static void buddy_deferred_free_start(struct buddy __arena *buddy, void __arena *addr)
> +{
> +	void __arena *head;
> +	void __arena * __arena *new;
> +
> +	/*
> +	 * Make a linked list by chaining the allocations into a linked list.
> +	 * Possible because allocations are 16 bytes minimum and so fit a pointer.
> +	 */
> +	new = (void __arena * __arena *)addr;
> +	asan_unpoison(addr, sizeof(void *));
> +	do  {
> +		head = buddy->deferred_free;
> +		*new = head;
> +	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
> +			 head, (void __arena *)new) != head && can_loop);
> +}
> +
> +static void buddy_deferred_free_start_bulk(struct buddy __arena *buddy,
> +		 void __arena * __arena *addrs, size_t naddrs)
> +{
> +	void __arena *head, *first, *last, *addr;
> [ ... ]
> +	/*
> +	 * Make a linked list by chaining the allocations into a linked list.
> +	 * Possible because allocations are 16 bytes minimum and so fit a pointer.
> +	 */
> +	do  {
> +		head = buddy->deferred_free;
> +		*(void __arena * __arena *)last = head;
> +	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
> +			 head, first) != head && can_loop);
> +}

this isn't a bug, but could buddy_deferred_free_start() and
buddy_deferred_free_start_bulk() share a small helper that pushes a
pre-linked [first, last] segment onto buddy->deferred_free?

The cmpxchg push loop and the block comment above it are repeated word for
word in both functions, and buddy_deferred_free_start() is the bulk push with
first == last == addr.

In the bulk version, the comment "Make a linked list by chaining the
allocations into a linked list" also sits above the push onto
buddy->deferred_free, while the local list is actually built earlier under
"Create a linked list locally."


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