Re: [PATCH bpf-next v2 3/7] selftests/bpf: libarena: Add buddy per-CPU caches

[Harry Yoo <harry@kernel.org>]

On Wed, Oct 21, 2026 at 11:26:37PM +0000, Emil Tsalapatis wrote:
> Every small allocation currently reaches the central buddy allocator and
> takes its lock. This serializes otherwise independent callers and touches
> the buddy metadata on every allocation and free.
> 
> Add a fixed-size LIFO array for each cached order and CPU. Keep the
> per-CPU cache pointers in struct buddy and allocate each CPU's packed
> cache from the buddy during initialization. Cache the eight smallest
> allocation orders, up to 2 KiB. Each array holds 16 objects, bounding each
> CPU's cache to about 1.5 KiB.

TIL the min alloc size is not PAGE_SIZE in BPF buddy allocator :)

> Allocations pop from the local array and frees push onto it without taking
> the buddy lock. Empty and full arrays fall through to the central buddy
> allocator. Packed arrays keep the fast path to a bounds check and a single
> slot access.
> 
> BPF programs only disable migration, so another task can preempt a cache
> operation and run on the same CPU, and an IRQ or NMI program can interrupt
> one. Claim the CPU with a cmpxchg on a per-CPU flag before touching its
> arrays, following the model used by the main BPF memory allocator. An
> operation that finds the CPU already claimed falls through to the central
> buddy allocator.
> 
> Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
> ---
>  .../bpf/libarena/include/libarena/buddy.h     |  34 +++
>  .../bpf/libarena/include/libarena/common.h    |   4 +
>  .../bpf/libarena/selftests/test_buddy.bpf.c   |   9 +
>  .../selftests/bpf/libarena/src/buddy.bpf.c    | 215 +++++++++++++++++-
>  4 files changed, 257 insertions(+), 5 deletions(-)
> 
> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
> index f150e1c37e3d..66349915745b 100644
> --- a/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/buddy.h
> @@ -65,10 +65,44 @@ struct buddy_chunk {
>  	struct buddy_chunk __arena	*next;
>  };
>  
> +/* Constants related to the buddy allocator's object caches. */
> +enum buddy_cache_consts {
> +	/*
> +	 * Do not cache larger allocations to avoid excessive
> +	 * memory consumption from the per-cpu lists.
> +	 */
> +	BUDDY_CACHE_NUM_ORDERS = 1 << 3,
> +
> +	/*
> +	 * Just like arena spinlocks, hardcode percpu state to a maximum number of CPUs.
> +	 * Since arena spinlocks are a hard dependency, use the exact same limit.
> +	 */
> +	BUDDY_CACHE_MAX_CPUS = 1024,

Is there no way to get nr_cpu_ids from the kernel in BPF?
NR_CPUS is upper bound supported by the kernel but during the boot
process, the kernel updates nr_cpu_ids based on the processor of the
system.

Kernels built with CONFIG_MAXSMP won't be able to use this because
it uses very high NR_CPUS? (8192 on x86)

> +	/*
> +	 * Objects retained locally for each allocation order.
> +	 */
> +	BUDDY_CACHE_CAPACITY = 16,
> +};
> +
> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index 6dfaa23089a9..c41e163b014f 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> @@ -7,6 +7,9 @@
>  /*
>   * Buddy allocator arena-based implementation.
>   *
> +static __always_inline struct buddy_cache __arena *
> +buddy_cache_enter(struct buddy __arena *buddy)
> +{
> +	struct buddy_cache __arena *cache;
> +
> +	/* The caches only exist between buddy_init() and buddy_destroy(). */
> +	cache = buddy->percpu[bpf_get_smp_processor_id()];
> +	if (unlikely(!cache))
> +		return NULL;
> +
> +	/*
> +	 * No support for cache operations from contexts that interrupted or
> +	 * preempted an in-flight operation on the same CPU, just like the
> +	 * kernel's BPF memory allocator.
> +	 */
> +	if (cmpxchg(&cache->active, 0, 1))
> +		return NULL;

Maybe use cmpxchg_local() instead of cmpxchg() because this is percpu?
Not sure if there's cmpxchg_local() equivalent in BPF...

On x86, cmpxchg instruction should be cheaper without LOCK prefix.

> +
> +	return cache;
> +}
> +
> +static __always_inline void buddy_cache_exit(struct buddy_cache __arena *cache)
> +{
> +	smp_store_release(&cache->active, 0);
> +}

We don't need this barrier because this is percpu?

-- 
Cheers,
Harry / Hyeonggon