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
next prev parent reply other threads:[~2026-10-20 18:19 UTC|newest]
Thread overview: 15+ 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:56 ` bot+bpf-ci
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:36 ` sashiko-bot
2026-10-20 18:56 ` bot+bpf-ci
2026-10-20 18:18 ` [PATCH bpf-next v1 4/7] selftests/bpf: libarena: Handle NMI reentrancy Emil Tsalapatis
2026-10-20 18:35 ` sashiko-bot
2026-10-20 18:56 ` bot+bpf-ci
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]
2026-10-20 18:35 ` [PATCH bpf-next v1 7/7] selftests/bpf: libarena: Cover buddy cache fast paths sashiko-bot
2026-10-20 21:41 ` [PATCH bpf-next v1 0/7] bpf libarena allocator improvements Alexei Starovoitov
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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox