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 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 --- .../bpf/libarena/include/libarena/buddy.h | 4 + .../selftests/bpf/libarena/src/buddy.bpf.c | 142 ++++++++++++++---- 2 files changed, 118 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..f150e1c37e3d 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..6dfaa23089a9 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,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; } -__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 +785,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 +950,40 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr) return ret; } +/* + * Fails only when the buddy lock cannot be taken, in which case nothing was + * freed. 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; +} + __weak char _license[] SEC("license") = "GPL"; -- 2.52.0