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 v4 1/9] selftests/bpf: libarena: Add bulk buddy allocation helpers
Date: Mon, 9 Nov 2026 18:20:46 +0000 [thread overview]
Message-ID: <20261109182055.7581-2-emil@etsalapatis.com> (raw)
In-Reply-To: <20261109182055.7581-1-emil@etsalapatis.com>
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.
buddy_free_bulk() fails only when its arguments are invalid or it cannot
take the allocator lock, in which case nothing was freed. Objects that
cannot be freed are reported individually, so a caller can tell from the
return value alone whether the array still owns its objects.
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 | 6 +
.../selftests/bpf/libarena/src/buddy.bpf.c | 148 ++++++++++++++----
2 files changed, 125 insertions(+), 29 deletions(-)
diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
index 90674ac077df..4c96307e2a2d 100644
--- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
+++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
@@ -76,8 +76,14 @@ 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);
void __arena *buddy_alloc_nogrow(struct buddy __arena *buddy, size_t size);
int buddy_grow(struct buddy __arena *buddy, size_t nr_chunks);
+int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
+ void __arena * __arena *out);
+int buddy_alloc_bulk_nogrow(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 d12c8924a0ad..514d0a59eaff 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,34 +749,35 @@ 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;
}
-static __always_inline
-void __arena *buddy_alloc_maygrow(struct buddy __arena *buddy, size_t size, bool grow)
+static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
+ int order, size_t norder, bool grow)
{
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;
@@ -779,23 +788,30 @@ void __arena *buddy_alloc_maygrow(struct buddy __arena *buddy, size_t size, bool
/* 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;
- asan_unpoison(address, size);
+ 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(object, size);
+ }
return address;
}
@@ -803,13 +819,13 @@ void __arena *buddy_alloc_maygrow(struct buddy __arena *buddy, size_t size, bool
__weak
void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
{
- return buddy_alloc_maygrow(buddy, size, true);
+ return buddy_alloc_memory(buddy, size, size_to_order(size), 0, true);
}
__weak
void __arena *buddy_alloc_nogrow(struct buddy __arena *buddy, size_t size)
{
- return buddy_alloc_maygrow(buddy, size, false);
+ return buddy_alloc_memory(buddy, size, size_to_order(size), 0, false);
}
__weak
@@ -838,6 +854,43 @@ int buddy_grow(struct buddy __arena *buddy, size_t nr_chunks)
return 0;
}
+static int buddy_alloc_bulk_memory(struct buddy __arena *buddy, size_t size, size_t norder,
+ void __arena * __arena *out, bool grow)
+{
+ 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, grow);
+ 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
+int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,
+ void __arena * __arena *out)
+{
+ return buddy_alloc_bulk_memory(buddy, size, norder, out, true);
+}
+
+__weak
+int buddy_alloc_bulk_nogrow(struct buddy __arena *buddy, size_t size, size_t norder,
+ void __arena * __arena *out)
+{
+ return buddy_alloc_bulk_memory(buddy, size, norder, out, false);
+}
+
static __always_inline int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr)
{
struct buddy_header __arena *header, *buddy_header;
@@ -941,3 +994,40 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
return ret;
}
+
+/*
+ * Fails only when the arguments are invalid or the buddy lock cannot be taken.
+ * Nothing is freed in either case. Objects that buddy_free_unlocked() rejects
+ * are reported there.
+ */
+__weak int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *addrs, size_t naddrs)
+{
+ unsigned long flags;
+ unsigned int i;
+ int ret;
+
+ 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;
+
+ buddy_free_unlocked(buddy, (u64)addrs[i]);
+ }
+
+ buddy_unlock(buddy, flags);
+
+ return 0;
+}
--
2.52.0
next prev parent reply other threads:[~2026-11-09 18:21 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-09 18:20 [PATCH bpf-next v4 0/9] bpf libarena allocator improvements Emil Tsalapatis
2026-11-09 18:20 ` Emil Tsalapatis [this message]
2026-11-09 18:20 ` [PATCH bpf-next v4 2/9] selftests/bpf: Add a parallel buddy allocator benchmark Emil Tsalapatis
2026-11-09 18:20 ` [PATCH bpf-next v4 3/9] selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlock Emil Tsalapatis
2026-11-09 18:29 ` sashiko-bot
2026-11-09 18:20 ` [PATCH bpf-next v4 4/9] selftests/bpf: libarena: Raise arena spinlock CPU limits Emil Tsalapatis
2026-11-09 18:32 ` sashiko-bot
2026-11-09 18:20 ` [PATCH bpf-next v4 5/9] selftests/bpf: libarena: Add buddy per-CPU caches Emil Tsalapatis
2026-11-09 18:38 ` sashiko-bot
2026-11-09 18:20 ` [PATCH bpf-next v4 6/9] selftests/bpf: libarena: Handle NMI reentrancy Emil Tsalapatis
2026-11-09 18:42 ` sashiko-bot
2026-11-09 19:05 ` bot+bpf-ci
2026-11-09 19:08 ` Emil Tsalapatis
2026-11-09 18:20 ` [PATCH bpf-next v4 7/9] selftests/bpf: libarena: Refill local caches in batches Emil Tsalapatis
2026-11-09 18:20 ` [PATCH bpf-next v4 8/9] selftests/bpf: libarena: Add a transfer cache Emil Tsalapatis
2026-11-09 18:20 ` [PATCH bpf-next v4 9/9] selftests/bpf: libarena: Cover buddy cache fast paths Emil Tsalapatis
2026-11-09 19:05 ` bot+bpf-ci
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=20261109182055.7581-2-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