Normalize SPDX in libarena for missing/inconsistent headers. There are currently three files missing headers and two of them (both originally authored by Kartikeya, CC'ed below) that are GPLv2 only. This patch ensures all files in libarena have a dual GPLv2/BSD-2-Clause license in the example of other non- kernel BPF codebases, e.g., libbpf. Add the customary BPF selftests/ SPDX tag to the bpf_may_goto.h file that holds the may_goto and can_loop macros for BPF code. The original authors of the code from when it was still in bpf_experimental.h are CC'ed below. Also add the missing SPDX license to the libarena bitmap.h header. For bpf_arena_spinlock.h and bpf_atomic.h, move the license to Dual GPLv2/BSD-2-Clause. This ensures all components have the same license, with the same rationale as libbpf in tools/lib. Cc: Alexei Starovoitov Cc: Kumar Kartikeya Dwivedi Cc: Jose Marchesi Cc: Yonghong Song Cc: Ilya Leoshkevich Signed-off-by: Emil Tsalapatis --- .../selftests/bpf/libarena/include/bpf_arena_spin_lock.h | 2 +- tools/testing/selftests/bpf/libarena/include/bpf_atomic.h | 2 +- tools/testing/selftests/bpf/libarena/include/bpf_may_goto.h | 1 + tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h | 1 + .../testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c | 3 +++ 5 files changed, 7 insertions(+), 2 deletions(-) diff --git a/tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h b/tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h index ae6b72d15bb6..872fa20f29a5 100644 --- a/tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +++ b/tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h @@ -1,4 +1,4 @@ -// SPDX-License-Identifier: GPL-2.0 +// SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause /* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ #ifndef BPF_ARENA_SPIN_LOCK_H #define BPF_ARENA_SPIN_LOCK_H diff --git a/tools/testing/selftests/bpf/libarena/include/bpf_atomic.h b/tools/testing/selftests/bpf/libarena/include/bpf_atomic.h index 43c306e17f19..65582b2010ad 100644 --- a/tools/testing/selftests/bpf/libarena/include/bpf_atomic.h +++ b/tools/testing/selftests/bpf/libarena/include/bpf_atomic.h @@ -1,4 +1,4 @@ -// SPDX-License-Identifier: GPL-2.0 +// SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause /* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ #ifndef BPF_ATOMIC_H #define BPF_ATOMIC_H diff --git a/tools/testing/selftests/bpf/libarena/include/bpf_may_goto.h b/tools/testing/selftests/bpf/libarena/include/bpf_may_goto.h index 9ba90689d6ba..b32a420d4e1a 100644 --- a/tools/testing/selftests/bpf/libarena/include/bpf_may_goto.h +++ b/tools/testing/selftests/bpf/libarena/include/bpf_may_goto.h @@ -1,3 +1,4 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause #pragma once /* diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h index e2431ea6fdd6..8c5936ae9958 100644 --- a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h +++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h @@ -1,3 +1,4 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause #pragma once #define BITS_PER_BYTE 8 diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c index 76319a529f02..e66b3a26ca3d 100644 --- a/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c +++ b/tools/testing/selftests/bpf/libarena/selftests/test_bitmap.bpf.c @@ -1,3 +1,6 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + #include #include -- 2.54.0 The libarena code currently defines the non-atomic bitmap set/get operations as __weak functions, in accordance with the libarena coding style. This, however, is significant overhead to call functions that span single-digit instructions. Make an exception and expose the getters/setters as static inline functions in the header. Since the function body is now inlined into the caller, mark reads/writes with READ_ONCE()/WRITE_ONCE() to prevent compiler optimizations from breaking code that locklessly polls the bitmap. Signed-off-by: Emil Tsalapatis --- .../bpf/libarena/include/libarena/bitmap.h | 29 +++++++++++++++++-- .../selftests/bpf/libarena/src/bitmap.bpf.c | 18 ------------ 2 files changed, 26 insertions(+), 21 deletions(-) diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h index 8c5936ae9958..163e2b83d943 100644 --- a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h +++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h @@ -1,6 +1,8 @@ // SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause #pragma once +#include + #define BITS_PER_BYTE 8 #define BYTES_TO_BITS(nb) ((nb) * BITS_PER_BYTE) @@ -16,11 +18,8 @@ struct arena_bitmap { struct arena_bitmap __arena *bmp_alloc(size_t bits); void bmp_free(struct arena_bitmap __arena *bmp); -void __bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp); -void __bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp); void bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp); void bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp); -bool bmp_test_bit(u32 bit, struct arena_bitmap __arena *bmp); bool bmp_test_and_clear_bit(u32 bit, struct arena_bitmap __arena *bmp); bool bmp_test_and_set_bit(u32 bit, struct arena_bitmap __arena *bmp); @@ -33,3 +32,27 @@ void bmp_copy(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap bool bmp_intersects(size_t bits, struct arena_bitmap __arena *arg1, struct arena_bitmap __arena *arg2); bool bmp_subset(size_t bits, struct arena_bitmap __arena *big, struct arena_bitmap __arena *small); void bmp_print(size_t bits, struct arena_bitmap __arena *bmp); + +static __always_inline +void __bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp) +{ + volatile u64 __arena *word = &bmp->bits[BIT_WORD(bit)]; + + *word |= BIT_MASK(bit); +} + +static __always_inline +void __bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) +{ + volatile u64 __arena *word = &bmp->bits[BIT_WORD(bit)]; + + *word &= ~BIT_MASK(bit); +} + +static __always_inline +bool bmp_test_bit(u32 bit, struct arena_bitmap __arena *bmp) +{ + u64 word = READ_ONCE(bmp->bits[BIT_WORD(bit)]); + + return word & BIT_MASK(bit); +} diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c index 5ff8e688ddc7..0390f20ce366 100644 --- a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c @@ -34,24 +34,6 @@ void bmp_free(struct arena_bitmap __arena *bmp) arena_free(bmp); } -__weak -void __bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp) -{ - bmp->bits[BIT_WORD(bit)] |= BIT_MASK(bit); -} - -__weak -void __bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) -{ - bmp->bits[BIT_WORD(bit)] &= ~BIT_MASK(bit); -} - -__weak -bool bmp_test_bit(u32 bit, struct arena_bitmap __arena *bmp) -{ - return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit); -} - __weak bool bmp_test_and_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) { -- 2.54.0 The libarena buddy allocator currently uses arena_spin_lock/unlock to protect its internal data structures in its critical section. These locks disable preemption, but not IRQs. This in turns can cause ABBA deadlocks when an allocation/free operation gets an IRQ while in the critical section, and can only resume after another operation that in turn blocks on the buddy lock. We have concretely seen this with sched_ext schedulers: a) Task 1 on CPU A attempts an allocation during initialization, which is done without holding an rq lock. The task takes an IRQ in the middle of the allocation. b) Task 2 on CPU B exits. It attempts to take the buddy allocator lock during its sched-ext state teardown, and blocks on the spinlock. It does so while holding CPU B's rq lock. c) The scheduler run on CPU A and attempts to move tasks from CPU B's rq to CPU A's rq before resuming running Task 1. This requires B's rq lock, which requires Task 2 to take the buddy allocator lock first. Fix this by disabling IRQs when taking the buddy lock. We use the already existing arena_spin_[lock_irqsave, unlock_irqrestore] calls for this. Signed-off-by: Emil Tsalapatis --- .../selftests/bpf/libarena/src/buddy.bpf.c | 44 +++++++++---------- 1 file changed, 22 insertions(+), 22 deletions(-) diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c index c674ee5cfcc1..2490ab1396de 100644 --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c @@ -5,6 +5,8 @@ #include #include +#include + /* * Buddy allocator arena-based implementation. * @@ -45,15 +47,8 @@ enum { BUDDY_CHUNK_PAGES = BUDDY_CHUNK_BYTES / __PAGE_SIZE }; -static inline int buddy_lock(struct buddy __arena *buddy) -{ - return arena_spin_lock(&buddy->lock); -} - -static inline void buddy_unlock(struct buddy __arena *buddy) -{ - arena_spin_unlock(&buddy->lock); -} +#define buddy_lock(buddy, flags) (arena_spin_lock_irqsave(&(buddy)->lock, (flags))) +#define buddy_unlock(buddy, flags) (arena_spin_unlock_irqrestore(&(buddy)->lock, (flags))) /* * Reserve part of the arena address space for the allocator. We use @@ -385,6 +380,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) { u64 order, ord, min_order, max_order; struct buddy_chunk __arena *chunk; + unsigned long flags; size_t left; int power2; u64 vaddr; @@ -416,7 +412,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) return NULL; } - if (buddy_lock(buddy)) { + if (buddy_lock(buddy, flags)) { /* * We cannot reclaim the vaddr space, but that is ok - this * operation should always succeed. The error path is to catch @@ -520,7 +516,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) arena_stderr( "chunk has size of 0x%lx bytes (left %lx bytes)\n", sizeof(*chunk), left); - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return NULL; } @@ -531,7 +527,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) order = (power2 >= BUDDY_MIN_ALLOC_SHIFT) ? power2 - BUDDY_MIN_ALLOC_SHIFT : 0; if (idx_set_allocated(chunk, idx, true)) { - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return NULL; } @@ -547,7 +543,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) */ min_order = left ? order + 1 : order; if (add_leftovers_to_freelist(chunk, idx, min_order, max_order)) { - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return NULL; } @@ -556,7 +552,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) max_order = order; } - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return chunk; } @@ -564,6 +560,7 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy) __weak int buddy_init(struct buddy __arena *buddy) { struct buddy_chunk __arena *chunk; + unsigned long flags; int ret; if (!asan_ready()) @@ -579,7 +576,7 @@ __weak int buddy_init(struct buddy __arena *buddy) chunk = buddy_chunk_get(buddy); - if (buddy_lock(buddy)) { + if (buddy_lock(buddy, flags)) { bpf_arena_free_pages(&arena, chunk, BUDDY_CHUNK_PAGES); return -EINVAL; } @@ -591,7 +588,7 @@ __weak int buddy_init(struct buddy __arena *buddy) /* Put the chunk at the beginning of the list. */ buddy->first_chunk = chunk; - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return chunk ? 0 : -ENOMEM; } @@ -730,9 +727,10 @@ static u64 buddy_alloc_from_existing_chunks(struct buddy __arena *buddy, int ord */ static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_chunk __arena *chunk, int order) { + unsigned long flags; u64 address; - if (buddy_lock(buddy)) + if (buddy_lock(buddy, flags)) return (u64)NULL; @@ -745,7 +743,7 @@ static u64 buddy_alloc_from_new_chunk(struct buddy __arena *buddy, struct buddy_ address = buddy_chunk_alloc(buddy->first_chunk, order); - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return (u64)address; } @@ -754,6 +752,7 @@ void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size) { void __arena *address = NULL; struct buddy_chunk __arena *chunk; + unsigned long flags; int order; if (!buddy) @@ -765,11 +764,11 @@ void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size) return NULL; } - if (buddy_lock(buddy)) + if (buddy_lock(buddy, flags)) return NULL; address = (u8 __arena *)buddy_alloc_from_existing_chunks(buddy, order); - buddy_unlock(buddy); + buddy_unlock(buddy, flags); if (address) goto done; @@ -880,6 +879,7 @@ static __always_inline int buddy_free_unlocked(struct buddy __arena *buddy, u64 __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr) { + unsigned long flags; int ret; if (!buddy) @@ -889,13 +889,13 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr) if (!addr) return 0; - ret = buddy_lock(buddy); + ret = buddy_lock(buddy, flags); if (ret) return ret; ret = buddy_free_unlocked(buddy, (u64)addr); - buddy_unlock(buddy); + buddy_unlock(buddy, flags); return ret; } -- 2.54.0 The arena memory allocator currently does not provide the option to zero-initialize the allocated memory. Provide a calloc() operation that calls memset() on the returned memory. Reuse naive memset implementation already present in the arena ASAN code for now. Subsequent patches will optimize the function. Signed-off-by: Emil Tsalapatis --- .../bpf/libarena/include/libarena/common.h | 18 +++++++++++++ .../selftests/bpf/libarena/src/asan.bpf.c | 21 ++------------- .../selftests/bpf/libarena/src/common.bpf.c | 27 ++++++++++++++++++- 3 files changed, 46 insertions(+), 20 deletions(-) diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/common.h b/tools/testing/selftests/bpf/libarena/include/libarena/common.h index 931ace9a49e2..d32a51ff5e7f 100644 --- a/tools/testing/selftests/bpf/libarena/include/libarena/common.h +++ b/tools/testing/selftests/bpf/libarena/include/libarena/common.h @@ -49,6 +49,7 @@ extern volatile u64 asan_violated; int arena_fls(__u64 word); void __arena *arena_malloc(size_t size); +void __arena *arena_calloc(size_t ncount, size_t size); void arena_free(void __arena *ptr); /* @@ -61,6 +62,23 @@ void arena_free(void __arena *ptr); */ #define arena_subprog_init() do { asm volatile ("" :: "r"(&arena)); } while (0) +/* + * BPF does not currently support the memset intrinsics. for large + * sequential copies, or assignments of large data structures, + * the frontend will generate an intrinsic that causes the BPF + * backend to exit due to a missing implementation. Provide + * implementations for the intrinsic. + */ +static inline int arena_memset(s8 __arena *dst, s8 val, size_t size) +{ + size_t i; + + for (i = zero; i < size && can_loop; i++) + dst[i] = val; + + return 0; +} + #else /* ! __BPF__ */ #include diff --git a/tools/testing/selftests/bpf/libarena/src/asan.bpf.c b/tools/testing/selftests/bpf/libarena/src/asan.bpf.c index 5135d5c72a46..de656b69d13a 100644 --- a/tools/testing/selftests/bpf/libarena/src/asan.bpf.c +++ b/tools/testing/selftests/bpf/libarena/src/asan.bpf.c @@ -103,23 +103,6 @@ volatile bool asan_inited = false; */ volatile bool asan_report_once = false; -/* - * BPF does not currently support the memset/memcpy/memcmp intrinsics. - * For large sequential copies, or assignments of large data structures, - * the frontend will generate an intrinsic that causes the BPF backend - * to exit due to a missing implementation. Provide a simple implementation - * just for memset to use it for poisoning/unpoisoning the map. - */ -__weak int asan_memset(s8 __arena *dst, s8 val, size_t size) -{ - size_t i; - - for (i = zero; i < size && can_loop; i++) - dst[i] = val; - - return 0; -} - /* Validate a 1-byte access, always within a single byte. */ static __always_inline bool memory_is_poisoned_1(s8 __arena *addr) { @@ -422,7 +405,7 @@ __hidden __noasan int asan_poison(void __arena *addr, s8 val, size_t size) shadow = mem_to_shadow(addr); len = size >> ASAN_SHADOW_SHIFT; - asan_memset(shadow, val, len); + arena_memset(shadow, val, len); return 0; } @@ -463,7 +446,7 @@ __hidden __noasan int asan_unpoison(void __arena *addr, size_t size) shadow = mem_to_shadow(addr); len = size >> ASAN_SHADOW_SHIFT; - asan_memset(shadow, 0, len); + arena_memset(shadow, 0, len); /* * If we are allocating a non-granule aligned region, we need to adjust diff --git a/tools/testing/selftests/bpf/libarena/src/common.bpf.c b/tools/testing/selftests/bpf/libarena/src/common.bpf.c index 569f0f64d518..785d4872cb49 100644 --- a/tools/testing/selftests/bpf/libarena/src/common.bpf.c +++ b/tools/testing/selftests/bpf/libarena/src/common.bpf.c @@ -1,5 +1,7 @@ // SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ +#include + #include #include #include @@ -48,10 +50,33 @@ __weak void __arena *arena_malloc(size_t size) return buddy_alloc(&buddy, size); } +__weak void __arena *arena_calloc(size_t ncount, size_t size) +{ + void __arena *mem; + size_t total; + + /* + * Ideally we'd be using __builtin_mul_overflow here, + * but the BPF compiler backend doesn't implement __multi3. + * There are ways to optimize the division away from the + * overflow check, but any costs are dwarfed by the + * buddy_alloc() call. Keep it simple for now. + */ + if (unlikely(ncount && size >= ULLONG_MAX / ncount)) + return NULL; + + total = ncount * size; + + mem = buddy_alloc(&buddy, total); + if (likely(mem)) + arena_memset(mem, 0, total); + + return mem; +} + __weak void arena_free(void __arena *ptr) { buddy_free(&buddy, ptr); } - char _license[] SEC("license") = "GPL"; -- 2.54.0 Add a benchmark for measuring the performance of the malloc()/calloc() arena allocator calls. This is useful as a basic allocator performance check that we can easily expand later. As with the regular arena allocator, focus on sub-page allocations that cannot be satisfied efficiently with the BPF arena page allocation code. Signed-off-by: Emil Tsalapatis --- tools/testing/selftests/bpf/Makefile | 18 +- tools/testing/selftests/bpf/bench.c | 6 + .../selftests/bpf/benchs/bench_libarena.c | 210 ++++++++++++++++++ .../bpf/benchs/run_bench_libarena.sh | 31 +++ tools/testing/selftests/bpf/libarena/Makefile | 30 ++- .../bpf/libarena/benchs/bench_malloc.bpf.c | 51 +++++ 6 files changed, 334 insertions(+), 12 deletions(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_libarena.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_libarena.sh create mode 100644 tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index d3655a706482..22e9eb16c151 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -826,18 +826,22 @@ LIBARENA_MAKE_ARGS = \ BPF_TARGET_ENDIAN="$(BPF_TARGET_ENDIAN)" \ Q="$(Q)" -LIBARENA_BPF_DEPS := $(wildcard libarena/Makefile \ - libarena/include/* \ - libarena/include/libarena/* \ - libarena/src/* \ - libarena/selftests/* \ - libarena/*.bpf.o) +LIBARENA_COMMON_DEPS := $(wildcard libarena/Makefile \ + libarena/include/* \ + libarena/include/libarena/* \ + libarena/src/*) +LIBARENA_BPF_DEPS := $(LIBARENA_COMMON_DEPS) $(wildcard libarena/selftests/*) +LIBARENA_BENCH_BPF_DEPS := $(LIBARENA_COMMON_DEPS) $(wildcard libarena/benchs/*) LIBARENA_SKEL := libarena/libarena.skel.h +LIBARENA_BENCH_SKEL := libarena/libarena_bench.skel.h $(LIBARENA_SKEL): $(INCLUDE_DIR)/vmlinux.h $(BPFOBJ) $(LIBARENA_BPF_DEPS) +$(MAKE) -C libarena libarena.skel.h $(LIBARENA_MAKE_ARGS) +$(LIBARENA_BENCH_SKEL): $(INCLUDE_DIR)/vmlinux.h $(BPFOBJ) $(LIBARENA_BENCH_BPF_DEPS) | $(LIBARENA_SKEL) + +$(MAKE) -C libarena benchmarks $(LIBARENA_MAKE_ARGS) + ifneq ($(CLANG_HAS_ARENA_ASAN),) LIBARENA_ASAN_SKEL := libarena/libarena_asan.skel.h CFLAGS += -DHAS_BPF_ARENA_ASAN @@ -987,6 +991,7 @@ $(OUTPUT)/bench_sockmap.o: $(OUTPUT)/bench_sockmap_prog.skel.h $(OUTPUT)/bench_lpm_trie_map.o: $(OUTPUT)/lpm_trie_bench.skel.h $(OUTPUT)/lpm_trie_map.skel.h $(OUTPUT)/bench_bpf_nop.o: $(OUTPUT)/bpf_nop_bench.skel.h bench_bpf_timing.h $(OUTPUT)/bench_xdp_lb.o: $(OUTPUT)/xdp_lb_bench.skel.h bench_bpf_timing.h +$(OUTPUT)/bench_libarena.o: $(LIBARENA_BENCH_SKEL) $(OUTPUT)/bench_bpf_timing.o: bench_bpf_timing.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm @@ -1014,6 +1019,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_bpf_timing.o \ $(OUTPUT)/bench_bpf_nop.o \ $(OUTPUT)/bench_xdp_lb.o \ + $(OUTPUT)/bench_libarena.o \ $(OUTPUT)/usdt_1.o \ $(OUTPUT)/usdt_2.o \ # diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index b86b73456d3c..de672f61d4ab 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -288,6 +288,7 @@ extern struct argp bench_crypto_argp; extern struct argp bench_sockmap_argp; extern struct argp bench_lpm_trie_map_argp; extern struct argp bench_xdp_lb_argp; +extern struct argp bench_libarena_argp; static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp, 0, "Ring buffers benchmark", 0 }, @@ -306,6 +307,7 @@ static const struct argp_child bench_parsers[] = { { &bench_sockmap_argp, 0, "bpf sockmap benchmark", 0 }, { &bench_lpm_trie_map_argp, 0, "LPM trie map benchmark", 0 }, { &bench_xdp_lb_argp, 0, "XDP load-balancer benchmark", 0 }, + { &bench_libarena_argp, 0, "libarena allocator benchmark", 0 }, {}, }; @@ -585,6 +587,8 @@ extern const struct bench bench_lpm_trie_delete; extern const struct bench bench_lpm_trie_free; extern const struct bench bench_bpf_nop; extern const struct bench bench_xdp_lb; +extern const struct bench bench_libarena_malloc; +extern const struct bench bench_libarena_calloc; static const struct bench *benchs[] = { &bench_count_global, @@ -669,6 +673,8 @@ static const struct bench *benchs[] = { &bench_lpm_trie_free, &bench_bpf_nop, &bench_xdp_lb, + &bench_libarena_malloc, + &bench_libarena_calloc, }; static void find_benchmark(void) diff --git a/tools/testing/selftests/bpf/benchs/bench_libarena.c b/tools/testing/selftests/bpf/benchs/bench_libarena.c new file mode 100644 index 000000000000..24e432244bf5 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_libarena.c @@ -0,0 +1,210 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ +#include +#include +#include + +#include "bench.h" + +#include +#include +#include +#include + +#include "libarena/libarena_bench.skel.h" + +static struct { + __u64 alloc_size; + __u64 nallocs; +} args = { + .alloc_size = 64, + .nallocs = 10000, +}; + +static struct { + struct libarena_bench *skel; + int bench_fd; + int reset_fd; +} ctx; + +enum { + ARG_LIBARENA_ALLOC_SIZE = 12000, + ARG_LIBARENA_NALLOCS, +}; + +static const struct argp_option opts[] = { + { "alloc_size", ARG_LIBARENA_ALLOC_SIZE, "BYTES", 0, + "Size of each arena allocation" }, + { "nallocs", ARG_LIBARENA_NALLOCS, "ITERS", 0, + "Number of allocation per measurement" }, + {}, +}; + +static error_t parse_arg(int key, char *arg, struct argp_state *state) +{ + unsigned long value; + + switch (key) { + case ARG_LIBARENA_ALLOC_SIZE: + value = strtoull(arg, NULL, 10); + if (!value || value >= UINT_MAX) { + fprintf(stderr, "invalid alloc_size: %ld", value); + argp_usage(state); + } + args.alloc_size = value; + break; + case ARG_LIBARENA_NALLOCS: + args.nallocs = strtoull(arg, NULL, 10); + break; + default: + return ARGP_ERR_UNKNOWN; + } + + return 0; +} + +const struct argp bench_libarena_argp = { + .options = opts, + .parser = parse_arg, +}; + +static void validate(void) +{ + if (env.consumer_cnt != 0) { + fprintf(stderr, "benchmark doesn't support consumers\n"); + exit(1); + } + + if (env.producer_cnt != 1) { + fprintf(stderr, "benchmark supports exactly one producer\n"); + exit(1); + } +} + +static void setup_common(void) +{ + struct arena_alloc_reserve_args reserve_args = { + .nr_pages = ARENA_RESERVE_PAGES_DFL, + }; + int err; + + setup_libbpf(); + + ctx.skel = libarena_bench__open_and_load(); + if (!ctx.skel) { + fprintf(stderr, "failed to open and load skeleton\n"); + exit(1); + } + + err = libarena_run_prog_args( + bpf_program__fd(ctx.skel->progs.arena_alloc_reserve), + &reserve_args, sizeof(reserve_args)); + if (err) { + fprintf(stderr, "failed to reserve arena pages: %d\n", err); + exit(1); + } + + err = libarena_run_prog( + bpf_program__fd(ctx.skel->progs.arena_buddy_reset)); + if (err) { + fprintf(stderr, "failed to initialize arena allocator: %d\n", err); + exit(1); + } + + ctx.skel->bss->bench_alloc_size = args.alloc_size; + ctx.skel->bss->bench_nallocs = args.nallocs; + ctx.reset_fd = bpf_program__fd(ctx.skel->progs.arena_buddy_reset); +} + +static void malloc_setup(void) +{ + setup_common(); + ctx.bench_fd = bpf_program__fd(ctx.skel->progs.bench_malloc); +} + +static void calloc_setup(void) +{ + setup_common(); + ctx.bench_fd = bpf_program__fd(ctx.skel->progs.bench_calloc); +} + +static void *producer(void *input) +{ + int err; + + while (true) { + err = libarena_run_prog(ctx.bench_fd); + if (err) { + fprintf(stderr, "libarena benchmark failed: %d\n", err); + exit(1); + } + + err = libarena_run_prog(ctx.reset_fd); + if (err) { + fprintf(stderr, "libarena alloc reset failed: %d\n", err); + exit(1); + } + } + + return NULL; +} + +static void measure(struct bench_res *res) +{ + res->duration_ns = atomic_swap(&ctx.skel->bss->bench_duration_ns, 0); + res->hits = atomic_swap(&ctx.skel->bss->bench_hits, 0); +} + +static void report_progress(int iter, struct bench_res *res, long delta_ns) +{ + double latency_ns = 0.0; + + if (res->hits) + latency_ns = res->duration_ns / (double)res->hits; + + printf("Iter %3d (%7.3lfus): latency %8.3lf ns/op (%ld allocations)\n", + iter, (delta_ns - 1000000000) / 1000.0, latency_ns, res->hits); +} + +static void report_final(struct bench_res res[], int res_cnt) +{ + unsigned long duration_ns = 0; + long hits = 0; + int i; + + for (i = 0; i < res_cnt; i++) { + duration_ns += res[i].duration_ns; + hits += res[i].hits; + } + + if (!hits || !res_cnt) { + printf("Summary: no runs measured\n"); + return; + } + + printf("Summary: %.3lf ns/op, %.0lf invocations for %u allocations/invocation)\n", + duration_ns / (double)hits, hits / (double)res_cnt, + ctx.skel->bss->bench_nallocs); +} + +const struct bench bench_libarena_malloc = { + .name = "libarena-malloc", + .argp = &bench_libarena_argp, + .validate = validate, + .setup = malloc_setup, + .producer_thread = producer, + .measure = measure, + .report_progress = report_progress, + .report_final = report_final, +}; + +const struct bench bench_libarena_calloc = { + .name = "libarena-calloc", + .argp = &bench_libarena_argp, + .validate = validate, + .setup = calloc_setup, + .producer_thread = producer, + .measure = measure, + .report_progress = report_progress, + .report_final = report_final, +}; diff --git a/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh b/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh new file mode 100755 index 000000000000..10afe4d52ebf --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/run_bench_libarena.sh @@ -0,0 +1,31 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +RUN_BENCH="./bench -d3 -q" + +summarize_libarena() +{ + local bench="$1" + local summary + + summary=$(printf '%s\n' "$2" | tail -n1) + summary=${summary#Summary: } + printf "%-20s %s\n" "$bench" "$summary" +} + +header "libarena sequential malloc\n" + +for size in 16 64 256 1024 4096; do +subtitle "allocation size: $size" +printf "\t-------------------\n" + for nallocs in 10 50 100 500 1000 5000 10000; do + summarize_libarena "malloc:" \ + "$($RUN_BENCH --alloc_size "$size" --nallocs "$nallocs" libarena-malloc)" + summarize_libarena "calloc:" \ + "$($RUN_BENCH --alloc_size "$size" --nallocs "$nallocs" libarena-calloc)" + done +done diff --git a/tools/testing/selftests/bpf/libarena/Makefile b/tools/testing/selftests/bpf/libarena/Makefile index 5e2ab514805e..6d62eda34920 100644 --- a/tools/testing/selftests/bpf/libarena/Makefile +++ b/tools/testing/selftests/bpf/libarena/Makefile @@ -27,10 +27,17 @@ BPFDIR=$(abspath $(LIBARENA)/..) INCLUDE_DIR ?= $(BPFDIR)/tools/include LIBBPF_INCLUDE ?= $(INCLUDE_DIR) -# Scan src/ and selftests/ to generate the final binaries -LIBARENA_SOURCES = $(wildcard $(LIBARENA)/src/*.bpf.c) $(wildcard $(LIBARENA)/selftests/*.bpf.c) -LIBARENA_OBJECTS = $(notdir $(LIBARENA_SOURCES:.bpf.c=.bpf.o)) -LIBARENA_OBJECTS_ASAN = $(notdir $(LIBARENA_SOURCES:.bpf.c=_asan.bpf.o)) +# Build selftests and benchmarks into separate BPF objects and skeletons. +LIBARENA_CORE_SOURCES = $(wildcard $(LIBARENA)/src/*.bpf.c) +LIBARENA_TEST_SOURCES = $(wildcard $(LIBARENA)/selftests/*.bpf.c) +LIBARENA_BENCH_SOURCES = $(wildcard $(LIBARENA)/benchs/*.bpf.c) + +LIBARENA_OBJECTS = $(notdir $(LIBARENA_CORE_SOURCES:.bpf.c=.bpf.o) \ + $(LIBARENA_TEST_SOURCES:.bpf.c=.bpf.o)) +LIBARENA_OBJECTS_ASAN = $(notdir $(LIBARENA_CORE_SOURCES:.bpf.c=_asan.bpf.o) \ + $(LIBARENA_TEST_SOURCES:.bpf.c=_asan.bpf.o)) +LIBARENA_BENCH_OBJECTS = $(notdir $(LIBARENA_CORE_SOURCES:.bpf.c=.bpf.o) \ + $(LIBARENA_BENCH_SOURCES:.bpf.c=.bpf.o)) INCLUDES = -I$(LIBARENA)/include -I$(BPFDIR) ifneq ($(INCLUDE_DIR),) @@ -58,12 +65,19 @@ override BPF_CFLAGS += $(INCLUDES) CFLAGS = -O2 -no-pie CFLAGS += $(INCLUDES) -vpath %.bpf.c $(LIBARENA)/src $(LIBARENA)/selftests -vpath %.c $(LIBARENA)/src $(LIBARENA)/selftests +vpath %.bpf.c $(LIBARENA)/src $(LIBARENA)/selftests $(LIBARENA)/benchs +vpath %.c $(LIBARENA)/src $(LIBARENA)/selftests $(LIBARENA)/benchs skeletons: libarena.skel.h libarena_asan.skel.h .PHONY: skeletons +benchmarks: libarena_bench.skel.h +.PHONY: benchmarks + +libarena_bench.skel.h: libarena_bench.bpf.o + $(call msg,GEN-SKEL,libarena,$@) + $(Q)$(BPFTOOL) gen skeleton $< name "libarena_bench" > $@ + libarena_asan.skel.h: libarena_asan.bpf.o $(call msg,GEN-SKEL,libarena,$@) $(Q)$(BPFTOOL) gen skeleton $< name "libarena_asan" > $@ @@ -80,6 +94,10 @@ libarena.bpf.o: $(LIBARENA_OBJECTS) $(call msg,GEN-OBJ,libarena,$@) $(Q)$(BPFTOOL) gen object $@ $^ +libarena_bench.bpf.o: $(LIBARENA_BENCH_OBJECTS) + $(call msg,GEN-OBJ,libarena,$@) + $(Q)$(BPFTOOL) gen object $@ $^ + %_asan.bpf.o: %.bpf.c $(call msg,CLNG-BPF,libarena,$@) $(Q)$(CLANG) $(BPF_CFLAGS) $(ASAN_FLAGS) -DBPF_ARENA_ASAN $(BPF_TARGET_ENDIAN) -c $< -o $@ diff --git a/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c b/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c new file mode 100644 index 000000000000..e06397dc9a40 --- /dev/null +++ b/tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c @@ -0,0 +1,51 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ +#include + +#include +#include + +u32 bench_alloc_size; +u32 bench_nallocs; +long bench_hits; +long bench_duration_ns; + +SEC("syscall") +int bench_malloc(void) +{ + void __arena *mem; + u64 start_ns; + u32 i; + + start_ns = bpf_ktime_get_ns(); + for (i = zero; i < bench_nallocs && can_loop; i++) { + mem = arena_malloc(bench_alloc_size); + if (!mem) + return -ENOMEM; + } + + __sync_add_and_fetch(&bench_duration_ns, + bpf_ktime_get_ns() - start_ns); + __sync_add_and_fetch(&bench_hits, i); + return 0; +} + +SEC("syscall") +int bench_calloc(void) +{ + void __arena *mem; + u64 start_ns; + u32 i; + + start_ns = bpf_ktime_get_ns(); + for (i = zero; i < bench_nallocs && can_loop; i++) { + mem = arena_calloc(1, bench_alloc_size); + if (!mem) + return -ENOMEM; + } + + __sync_add_and_fetch(&bench_duration_ns, + bpf_ktime_get_ns() - start_ns); + __sync_add_and_fetch(&bench_hits, i); + return 0; +} -- 2.54.0 Clang currently provides no __builtin_{memset, memcpy, memcmp} for its BPF backend. This is especially an issue for arena code that is more likely to do these operations on buffers with user-provided bounds. One example is the arena ASAN implementation that uses memset to update the shadow bitmap. Arena ASAN actually already has a naive implementation of this operation. Another user would be a calloc() call that has to zero the memory it returns. Introduce a more optimized version of the memset() operation for arena memory and make it public to all libarena users. The operation uses word-sized assignments to speed up the function for larger sizes. We expose the function through common.h to allow for inlining from the callers. Signed-off-by: Emil Tsalapatis --- tools/testing/selftests/bpf/libarena/Makefile | 1 + .../bpf/libarena/include/libarena/common.h | 57 ++++++++++++++++++- 2 files changed, 56 insertions(+), 2 deletions(-) diff --git a/tools/testing/selftests/bpf/libarena/Makefile b/tools/testing/selftests/bpf/libarena/Makefile index 6d62eda34920..91164d43bd61 100644 --- a/tools/testing/selftests/bpf/libarena/Makefile +++ b/tools/testing/selftests/bpf/libarena/Makefile @@ -60,6 +60,7 @@ override BPF_CFLAGS += -O2 -g override BPF_CFLAGS += -Wno-incompatible-pointer-types-discards-qualifiers # Required for suppressing harmless vmlinux.h-related warnings. override BPF_CFLAGS += -Wno-missing-declarations +override BPF_CFLAGS += -fno-strict-aliasing override BPF_CFLAGS += $(INCLUDES) CFLAGS = -O2 -no-pie diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/common.h b/tools/testing/selftests/bpf/libarena/include/libarena/common.h index d32a51ff5e7f..a6220355a697 100644 --- a/tools/testing/selftests/bpf/libarena/include/libarena/common.h +++ b/tools/testing/selftests/bpf/libarena/include/libarena/common.h @@ -71,10 +71,63 @@ void arena_free(void __arena *ptr); */ static inline int arena_memset(s8 __arena *dst, s8 val, size_t size) { + size_t headalign; + size_t tailalign; + u8 uval = (u8)val; + size_t val64; size_t i; - for (i = zero; i < size && can_loop; i++) - dst[i] = val; + /* + * Calculate how many bytes to the next word-aligned one. + * We get this by truncating the 2s complement of the + * pointer to the last 3 bits. Intuitively, since + * + * The N LSBs of dst and -dst add to 1 << N, which + * is why dst + (-dst) = 0x0ULL through overflow. So the + * last N = 3 bits of the negative are the number of + * bytes to align dst on the last 3 bits. + * + */ + headalign = -(u64)dst & (sizeof(u64) - 1); + if (!headalign || size < headalign) + goto ptraligned; + + for (i = zero; i < headalign && can_loop; i++) + dst[i] = uval; + + dst += headalign; + size -= headalign; + +ptraligned: + + /* + * Make a word with all bytes equal to the byte we are setting. + * Since 1 byte -> 2 hex digits. + * + * Shifting the value by a 0 bytes is equal to multiplication by 0x01 + * Shifting by 1 bytes is equal to multiplication by 0x01 << 8, + * ... + * Shifting by 7 bytes is equal to multiplication by 0x01 << 56. + * + * End operation to replicate the byte into all the bytes of a word + * is (since a | b = a + b when a & b == 0): + * + * val + val * (1UL << 8) + val * (1UL << 16) + .. + val * (1UL << 56) + * = val * (1UL << 56 + 1UL << 48 + ... + 1UL << 0) + * = val * (0x01UL << 56 | 0x01UL << 48 + ... + 1UL << 0) + * = val * 0x0101 0101 0101 0101 + */ + val64 = (u8)val * 0x0101010101010101ULL; + + /* Pointer is now aligned, use word-aligned assignments. */ + for (i = zero; i < size / sizeof(u64) && can_loop; i++) + ((u64 __arena *)dst)[i] = val64; + + /* Go back to byte-aligned for the tail. */ + tailalign = size % sizeof(u64); + dst += size - tailalign; + for (i = zero; i < tailalign && can_loop; i++) + dst[i] = uval; return 0; } -- 2.54.0