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 --- .../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 #include +#include #include 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