From: Emil Tsalapatis <emil@etsalapatis.com>
To: bpf@vger.kernel.org
Cc: ast@kernel.org, andrii@kernel.org, eddyz87@gmail.com,
memxor@gmail.com, daniel@iogearbox.net,
Emil Tsalapatis <emil@etsalapatis.com>
Subject: [PATCH bpf-next v1 7/7] selftests/bpf: libarena: Cover buddy cache fast paths
Date: Tue, 20 Oct 2026 18:19:00 +0000 [thread overview]
Message-ID: <20261020181900.6755-8-emil@etsalapatis.com> (raw)
In-Reply-To: <20261020181900.6755-1-emil@etsalapatis.com>
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
prev parent reply other threads:[~2026-10-20 18:19 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-20 18:18 [PATCH bpf-next v1 0/7] bpf libarena allocator improvements Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 1/7] selftests/bpf: libarena: Add bulk buddy allocation helpers Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 2/7] selftests/bpf: Add a parallel buddy allocator benchmark Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 3/7] selftests/bpf: libarena: Add buddy per-CPU caches Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 4/7] selftests/bpf: libarena: Handle NMI reentrancy Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 5/7] selftests/bpf: libarena: Refill local caches in batches Emil Tsalapatis
2026-10-20 18:18 ` [PATCH bpf-next v1 6/7] selftests/bpf: libarena: Add a transfer cache Emil Tsalapatis
2026-10-20 18:19 ` Emil Tsalapatis [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261020181900.6755-8-emil@etsalapatis.com \
--to=emil@etsalapatis.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=memxor@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.