Skip to contentSkip to conversation

bpf libarena allocator improvements

PATCH Superseded Emil Tsalapatis 3 participants 17 messages Nov 9

Subsystems (3)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Emil Tsalapatis

author reviewer
#0 lore raw

v4 cover bpf libarena allocator improvements

The libarena buddy allocator's design has up until now prioritized ease of verification. With new verifier features like unlimited global stack frames and a large stack size we can now improve the allocator's performance and robustness.

This patch introduces per-CPU caches for the allocator. The overall caching design is inspired by tcmalloc. Each CPU has its own static object LIFOs, one for each allocator order. This speeds up allocation and freeing for BPF programs that have some degree of locality. The CPU caches are lockless. The caches are replenished from and spilled into "transfer caches", per-order caches shared between the CPUs that amortize the cost of spilling/refilling. Data from the transfer caches is in turn moved from and to the allocator.

The patchset additionally includes code for allocator reentrancy and bulk allocations. The reentrancy code lets us safely allocate from an NMI context in general, and from a BPF syscall program context locklessly. The bulk allocation API is useful for replenishing the allocator caches and also on its own right for speeding up allocations during initialization.

Benchmark results from patch 2, run with the options from run_bench_libarena.sh (-a, 64-byte allocations) in a 16-vCPU VM, as the mean of three runs. Rows are the number of consecutive allocations, and then frees, in each benchmark iteration. Columns are the number of producers. Each entry shows the latency in ns before and with this series, followed by the speedup: the latency before divided by the latency with this series, so higher is better.

libarena-malloc-free, where each worker frees its own objects:

Allocation latency (before/after ns, speedup):

allocs 1 prod 2 prod 4 prod 8 prod

     1    269/68 3.9x    641/68 9.4x  1568/68 22.9x  4550/69 66.4x
     4    251/63 4.0x    557/63 8.9x  2326/67 34.5x  5221/74 70.4x
    16    247/61 4.0x  1027/64 16.0x  2570/67 38.1x  5315/74 71.8x
    64    242/75 3.2x  1129/146 7.8x 2469/190 13.0x 5521/374 14.8x

256 242/102 2.4x 1314/184 7.1x 2664/249 10.7x 5542/457 12.1x

Free latency (before/after ns, speedup):

allocs 1 prod 2 prod 4 prod 8 prod

     1    243/55 4.4x    273/56 4.9x  1428/55 25.9x  4371/56 78.2x
     4    242/51 4.7x    414/52 8.0x  2303/52 44.5x 5266/51 103.1x
    16    241/50 4.8x  1056/50 20.9x  2580/50 51.6x 5330/51 105.4x
    64    240/64 3.8x  1079/86 12.5x 2454/131 18.8x 5538/309 17.9x

256 238/124 1.9x 1206/107 11.2x 2681/178 15.0x 5546/406 13.7x

libarena-malloc-xfree, where each worker frees the objects allocated by the previous invocation, so with more than one producer most frees happen on a different CPU from the allocation:

Allocation latency (before/after ns, speedup):

allocs 1 prod 2 prod 4 prod 8 prod

     1    291/65 4.5x   857/65 13.2x  1165/67 17.5x  4172/70 59.8x
     4    243/63 3.9x   754/64 11.7x  2170/66 32.6x  4931/79 62.2x
    16    231/61 3.8x  1163/63 18.5x  2572/71 36.2x  5438/93 58.7x
    64    229/75 3.1x  1249/158 7.9x 2824/213 13.3x 5760/411 14.0x

256 228/100 2.3x 1269/210 6.0x 2746/264 10.4x 5669/466 12.2x

Free latency (before/after ns, speedup):

allocs 1 prod 2 prod 4 prod 8 prod

     1    266/55 4.8x   558/56 10.0x  1052/56 18.8x  4050/56 72.3x
     4    231/51 4.5x   583/52 11.2x  2032/51 39.6x  4875/52 93.9x
    16    223/50 4.5x  1019/50 20.3x  2492/50 49.6x 5396/51 106.5x
    64    222/63 3.5x  1156/84 13.8x 2801/122 23.0x 5735/320 17.9x

256 221/124 1.8x 1202/113 10.7x 2736/160 17.1x 5656/387 14.6x

Cc Harry Yoo <[email protected]>
Cc Kumar Kartikeya Dwivedi <[email protected]>

v3 -> v4 (https://lore.kernel.org/bpf/[email protected]/)

- Rebase on bpf-next after the allocator compatibility fixes.
- Fix arena_spin_trylock() preemption pairing and add an irqsave variant.
- Raise the arena spinlock and per-CPU cache limits to 8192 (Harry).
- Use trylocks for the buddy and transfer locks in NMI context, allowing cache refills and spills when they succeed and deferring frees on lock failure. Detach the deferred list with one atomic exchange (Alexei).
- Move bulk spilling into the batch-refill patch, before the transfer cache, and add the transfer-cache measurements to its commit log (Alexei).
- Refill from existing chunks without growing the allocator, avoiding virtual-address exhaustion when only individual objects fit (Alexei).
- Restore smp_store_release() and force buddy_cache_free() inline; the measured free-latency difference disappears with inlining (Kumar).
- Address reviewer nits and clarify the cache footprint and free contracts.

v2 -> v3 (https://lore.kernel.org/bpf/[email protected]/)

- Release the per-CPU cache claim with barrier() and WRITE_ONCE() instead of smp_store_release(), since only contexts on the same CPU claim the cache (Harry).

v1 -> v2 (https://lore.kernel.org/bpf/[email protected]/)

- In the transfer cache, avoid taking two locks per free when it is full:
check the transfer array's count before taking its lock, and spill the local batch with buddy_free_bulk() when the array is full or busy (Alexei).
- Simplify the per-CPU caches: keep the guard in struct buddy_cache, claim the cache once per miss or full cache with the refill and spill paths out of line, keep the cache state in struct buddy, and move the definitions into buddy.h (Alexei).
- Make buddy_free_bulk() fail only when nothing was freed (Alexei).
- Time frees in the benchmark, add a cross-CPU variant, and add before and after numbers to the cover letter (Alexei).
- Addressed bot feedback.

Emil Tsalapatis (9):
selftests/bpf: libarena: Add bulk buddy allocation helpers selftests/bpf: Add a parallel buddy allocator benchmark selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlock selftests/bpf: libarena: Raise arena spinlock CPU limits selftests/bpf: libarena: Add buddy per-CPU caches selftests/bpf: libarena: Handle NMI reentrancy selftests/bpf: libarena: Refill local caches in batches selftests/bpf: libarena: Add a transfer cache selftests/bpf: libarena: Cover buddy cache fast paths

 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_libarena.c     | 118 +++-
 .../bpf/benchs/run_bench_libarena.sh          |  16 +
 .../bpf/libarena/benchs/bench_malloc.bpf.c    | 110 +++
 .../libarena/include/bpf_arena_spin_lock.h    |  40 +-
 .../bpf/libarena/include/libarena/buddy.h     |  58 ++
 .../bpf/libarena/include/libarena/common.h    |   4 +
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 273 ++++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 625 ++++++++++++++++--
 9 files changed, 1195 insertions(+), 53 deletions(-)
Signature · 1 line
2.52.0
author reviewer
#1 lore raw

PATCH v4 1/9 selftests/bpf: libarena: Add bulk buddy allocation helpers

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.

---
 .../bpf/libarena/include/libarena/buddy.h     |   6 +
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 148 ++++++++++++++----
 2 files changed, 125 insertions(+), 29 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +6 -0
index 90674ac077df..4c96307e2a2d 100644
@@ -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__  */
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +119 -29

258 lines not on this page · raw message

Signature · 1 line
2.52.0
author reviewer
#2 lore raw

PATCH v4 2/9 selftests/bpf: Add a parallel buddy allocator benchmark

In reply to Emil Tsalapatis

Add a benchmark for measuring buddy allocator latency under concurrent load. Each worker performs a configurable number of allocations followed by the corresponding frees, and the summary reports the mean latency of allocations and frees separately. The frees chain the objects through their first word, so the allocation size must be large enough to hold a pointer.

Add a cross-CPU variant in which each worker publishes its list in a shared slot, takes the list left there by the previous invocation and frees it. With more than one pinned worker, most objects are then freed on a different CPU from the one that allocated them.

Add both benchmarks to the libarena runner alongside the existing single-threaded cases, sweeping the producer count from 1 to 8 with a fixed allocation size and count to expose lock contention.

Report the existing libarena-malloc and libarena-calloc results in ns/allocation and summarize them by total allocation count, so that all libarena benchmarks share one output format. This replaces the previous ns/op unit and the invocation and allocations-per-invocation fields.

---
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_libarena.c     | 118 ++++++++++++++++--
 .../bpf/benchs/run_bench_libarena.sh          |  16 +++
 .../bpf/libarena/benchs/bench_malloc.bpf.c    | 110 ++++++++++++++++
 4 files changed, 237 insertions(+), 11 deletions(-)
tools/testing/selftests/bpf/bench.c +4 -0
index d5f494184f9d..fbbd55399019 100644
@@ -589,6 +589,8 @@ 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;
+extern const struct bench bench_libarena_malloc_free;
+extern const struct bench bench_libarena_malloc_xfree;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -675,6 +677,8 @@ static const struct bench *benchs[] = {
 	&bench_xdp_lb,
 	&bench_libarena_malloc,
 	&bench_libarena_calloc,
+	&bench_libarena_malloc_free,
+	&bench_libarena_malloc_xfree,
 };
 
 static void find_benchmark(void)
tools/testing/selftests/bpf/benchs/bench_libarena.c +107 -11

201 lines not on this page · raw message

tools/testing/selftests/bpf/benchs/run_bench_libarena.sh +16 -0
index 10afe4d52ebf..2dfa32cd95cc 100755
@@ -29,3 +29,19 @@ printf "\t-------------------\n"
 			"$($RUN_BENCH --alloc_size "$size" --nallocs "$nallocs" libarena-calloc)"
 	done
 done
+
+header "libarena parallel malloc/free\n"
+
+for producers in 1 2 4 8; do
+	summarize_libarena "$producers producers:" \
+		"$($RUN_BENCH -a -p "$producers" --alloc_size 64 --nallocs 1000 \
+		libarena-malloc-free)"
+done
+
+header "libarena parallel cross-CPU malloc/free\n"
+
+for producers in 1 2 4 8; do
+	summarize_libarena "$producers producers:" \
+		"$($RUN_BENCH -a -p "$producers" --alloc_size 64 --nallocs 1000 \
+		libarena-malloc-xfree)"
+done
tools/testing/selftests/bpf/libarena/benchs/bench_malloc.bpf.c +110 -0

120 lines not on this page · raw message

Signature · 1 line
2.52.0
author reviewer
#3 lore raw

PATCH v4 3/9 selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlock

In reply to Emil Tsalapatis

The arena_spin_trylock() macro is currently only used within the lock slowpath, and so does not disable preemption. However, this means it does not properly pair with arena_spin_unlock() that does. Rename the existing function to arena_spin_trylock_raw() to denote it just handles the test-and-test-and-set, and make a version of the function that handles preemption. Also add an _irqsave() variant.

Fixes 88d706ba7cc5 ("selftests/bpf: Introduce arena spin lock")
---
 .../libarena/include/bpf_arena_spin_lock.h    | 34 +++++++++++++++++--
 1 file changed, 32 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +32 -2
index 055b5892cb63..560ee18fd287 100644
@@ -233,7 +233,26 @@ static __always_inline int arena_spin_trylock(arena_spinlock_t __arena *lock)
 	if (unlikely(val))
 		return 0;
 
-	return likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL));
+	bpf_preempt_disable();
+	val = atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL);
+	if (unlikely(!val))
+		bpf_preempt_enable();
+
+	return val;
+}
+
+/*
+ * Trylock variant without preemption disable/reenable.
+ * Used within the lock slowpath.
+ */
+static __always_inline int arena_spin_trylock_raw(arena_spinlock_t __arena *lock)
+{
+	int val = atomic_read(&lock->val);
+
+	if (unlikely(val))
+		return 0;
+
+	return atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL);
 }
 
 __noinline __weak
@@ -346,7 +365,7 @@ int arena_spin_lock_slowpath(arena_spinlock_t __arena *lock, u32 val)
 	 * attempt the trylock once more in the hope someone let go while we
 	 * weren't watching.
 	 */
-	if (arena_spin_trylock(lock))
+	if (arena_spin_trylock_raw(lock))
 		goto release;
 
 	/*
@@ -527,6 +546,17 @@ static __always_inline void arena_spin_unlock(arena_spinlock_t __arena *lock)
 		(__ret);                                 \
 	})
 
+#define arena_spin_trylock_irqsave(lock, flags)			\
+	({							\
+		int __ret;					\
+		bpf_local_irq_save(&(flags));			\
+		__ret = arena_spin_trylock((lock)) ? 0 : -EBUSY;\
+		if (__ret)					\
+			bpf_local_irq_restore(&(flags)); 	\
+		(__ret);                                 	\
+	})
+
+
 #define arena_spin_unlock_irqrestore(lock, flags) \
 	({                                        \
 		arena_spin_unlock((lock));        \
Signature · 1 line
2.52.0
#4 lore raw

Re: [PATCH bpf-next v4 3/9] selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlock

Thank you for your contribution! Sashiko AI review found 1 potential issue to consider: - [Low] selftests/bpf: inconsistent return values in arena_spin_trylock() variants --

Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Low] selftests/bpf: inconsistent return values in arena_spin_trylock() variants
--

commit 3875fb781c61e9ab8efcf22a434ad87a4732478e
Author: Emil Tsalapatis <[email protected]>

selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlock

This commit updates arena_spin_trylock() to disable preemption on lock acquisition, splits out arena_spin_trylock_raw() for the lock slowpath, and adds arena_spin_trylock_irqsave().

Quoted 16 lines
tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +7 -1
index 055b5892cb636..560ee18fd287f 100644
@@ -233,7 +233,26 @@ static __always_inline int arena_spin_trylock(arena_spinlock_t __arena *lock)
 	if (unlikely(val))
 		return 0;
 
-	return likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL));
+	bpf_preempt_disable();
+	val = atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL);
+	if (unlikely(!val))
+		bpf_preempt_enable();
+
+	return val;
+}

[ ... ]

tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h static __always_inline void arena_spin_unlock(arena_spinlock_t __arena *lock) · line 557

Quoted 13 lines
tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +9 -0
@@ -527,6 +546,17 @@ static __always_inline void arena_spin_unlock(arena_spinlock_t __arena *lock)
 		(__ret);                                 \
 	})
 
+#define arena_spin_trylock_irqsave(lock, flags)			\
+	({							\
+		int __ret;					\
+		bpf_local_irq_save(&(flags));			\
+		__ret = arena_spin_trylock((lock)) ? 0 : -EBUSY;\
+		if (__ret)					\
+			bpf_local_irq_restore(&(flags)); 	\
+		(__ret);                                 	\
+	})

[Severity: Low]
Should arena_spin_trylock() and arena_spin_trylock_irqsave() use the same return value convention?

arena_spin_trylock() returns 1 on success and 0 on failure, whereas arena_spin_trylock_irqsave() (like arena_spin_lock() and arena_spin_lock_irqsave()) returns 0 on success and -EBUSY on failure, so callers switching between the two trylock variants have to invert the check.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
author reviewer
#5 lore raw

PATCH v4 4/9 selftests/bpf: libarena: Raise arena spinlock CPU limits

In reply to Emil Tsalapatis

Bump the maximum number of CPUs supported by the arena spinlocks to 8K, up from 1K.

---
 .../selftests/bpf/libarena/include/bpf_arena_spin_lock.h    | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +3 -3
index 560ee18fd287..230bd112e8d5 100644
@@ -77,7 +77,7 @@ struct arena_qnode {
  * 16-17: tail index
  * 18-31: tail cpu (+1)
  */
-#define _Q_MAX_CPUS		1024
+#define _Q_MAX_CPUS		8192
 
 #define	_Q_SET_MASK(type)	(((1U << _Q_ ## type ## _BITS) - 1)\
 				      << _Q_ ## type ## _OFFSET)
@@ -109,7 +109,7 @@ static inline u32 encode_tail(int cpu, int idx)
 {
 	u32 tail;
 
-	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail  = (u32)(cpu + 1) << _Q_TAIL_CPU_OFFSET;
 	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */
 
 	return tail;
@@ -509,7 +509,7 @@ static __always_inline int arena_spin_lock(arena_spinlock_t __arena *lock)
 {
 	int val = 0;
 
-	if (CONFIG_NR_CPUS > 1024)
+	if (CONFIG_NR_CPUS > _Q_MAX_CPUS)
 		return -EOPNOTSUPP;
 
 	bpf_preempt_disable();
Signature · 1 line
2.52.0
#6 lore raw

Re: [PATCH bpf-next v4 4/9] selftests/bpf: libarena: Raise arena spinlock CPU limits

Thank you for your contribution! Sashiko AI review found 1 potential issue to consider: - [Medium] selftests/bpf: enlarged qnodes exceeds arena max_entries in arena_spin_lock.c --

Thank you for your contribution! Sashiko AI review found 1 potential issue to consider:
- [Medium] selftests/bpf: enlarged qnodes exceeds arena max_entries in arena_spin_lock.c
--

commit b35a00e6a80fa689cd0b2cdb4e1bcd8899fded17
Author: Emil Tsalapatis <[email protected]>

selftests/bpf: libarena: Raise arena spinlock CPU limits

This commit increases the maximum number of CPUs supported by the BPF arena spinlocks from 1024 to 8192.

tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h struct arena_qnode { · line 80

Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h +1 -1
index 560ee18fd287f..230bd112e8d59 100644
@@ -77,7 +77,7 @@ struct arena_qnode {
  * 16-17: tail index
  * 18-31: tail cpu (+1)
  */
-#define _Q_MAX_CPUS		1024
+#define _Q_MAX_CPUS		8192

[Severity: Medium]
Does raising _Q_MAX_CPUS to 8192 exceed the 100-page arena map limit in tools/testing/selftests/bpf/progs/arena_spin_lock.c?

tools/testing/selftests/bpf/progs/arena_spin_lock.c {
	struct {
		__uint(type, BPF_MAP_TYPE_ARENA);
		__uint(map_flags, BPF_F_MMAPABLE);
		__uint(max_entries, 100); /* number of pages */
	...
	} arena SEC(".maps");
	...
	struct arena_qnode __arena __hidden qnodes[_Q_MAX_CPUS][_Q_MAX_NODES];
}

With 16-byte struct arena_qnode and _Q_MAX_NODES of 4, qnodes grows from 64 KiB to 512 KiB (128 4-KiB pages), causing bpf_object__relocate() to reject loading the arena_spin_lock selftest with -E2BIG on 4-KiB page architectures.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
author reviewer
#7 lore raw

PATCH v4 5/9 selftests/bpf: libarena: Add buddy per-CPU caches

In reply to Emil Tsalapatis

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, retaining up to 63.75 KiB of objects per CPU. The cache metadata occupies 1600 bytes and consumes a 2 KiB buddy allocation per CPU.

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.

---
 .../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    | 220 +++++++++++++++++-
 4 files changed, 261 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +34 -0
index 4c96307e2a2d..ec5e79a07540 100644
@@ -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 = 8192,
+
+	/*
+	 * Objects retained locally for each allocation order.
+	 */
+	BUDDY_CACHE_CAPACITY = 16,
+};
+
+struct buddy_cache_order {
+	u32 elems;
+	u32 __pad;
+	void __arena *objects[BUDDY_CACHE_CAPACITY];
+} __attribute__((aligned(64)));
+
+/* Dynamically allocated packed per-CPU slot slab. */
+struct buddy_cache {
+	/* Claimed by an in-flight cache operation on this CPU. */
+	unsigned int active;
+	struct buddy_cache_order orders[BUDDY_CACHE_NUM_ORDERS];
+};
+
 struct buddy {
 	struct buddy_chunk __arena *first_chunk;		/* Pointer to the chunk linked list. */
 	arena_spinlock_t lock;			/* Allocator lock */
 	u64 vaddr;				/* Allocation into reserved vaddr */
+	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
 };
 
 #ifdef __BPF__
tools/testing/selftests/bpf/libarena/include/libarena/common.h +4 -0
index 940e82cc2928..62a49dcf31d6 100644
@@ -22,6 +22,10 @@
 #define __maybe_unused __attribute__((__unused__))
 #endif
 
+#ifndef min
+#define min(a, b) ((a) < (b) ? (a) : (b))
+#endif
+
 #define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))
 
 #define ARENA_PAGES (1UL << (32 - __builtin_ffs(__PAGE_SIZE) + 1))
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +9 -0
index 5628f0987012..85a7ea8b2e97 100644
@@ -34,9 +34,18 @@ __weak int test_buddy_create(void)
 		if (ret)
 			return ret;
 
+#ifndef BPF_ARENA_ASAN
+		if (!buddy.percpu[0]) {
+			buddy_destroy(&buddy);
+			return -EINVAL;
+		}
+#endif
+
 		ret = buddy_destroy(&buddy);
 		if (ret)
 			return ret;
+		if (buddy.percpu[0])
+			return -EINVAL;
 	}
 
 	return 0;
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +214 -6

270 lines not on this page · raw message

Signature · 1 line
2.52.0
#8 lore raw

Re: [PATCH bpf-next v4 5/9] selftests/bpf: libarena: Add buddy per-CPU caches

Thank you for your contribution! Sashiko AI review found 3 potential issues to consider: - [Medium] selftests/bpf: conflicting prototype for buddy_alloc_memory() - [Low] selftests/bpf…

Thank you for your contribution! Sashiko AI review found 3 potential issues to consider:
- [Medium] selftests/bpf: conflicting prototype for buddy_alloc_memory()
- [Low] selftests/bpf: buddy_alloc_nogrow() bypasses buddy_cache_alloc()
- [Low] selftests/bpf: missing static on buddy_cache_alloc() and buddy_cache_free()
--

commit 2da1f713f762ba4737b95c532cd5e6f183f3f061
Author: Emil Tsalapatis <[email protected]>

selftests/bpf: libarena: Add buddy per-CPU caches

This commit adds per-CPU LIFO array caches to the libarena buddy allocator for the eight smallest allocation orders so small allocations and frees can avoid taking the central buddy lock.

Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +0 -0
index 514d0a59eaff5..13c55cf53e524 100644

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 50

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +7 -0
@@ -38,18 +41,162 @@
  * and their allocation state. It also includes the freelist
  * heads for the allocation itself.
  */
+static u8 idx_get_order(struct buddy_chunk __arena *chunk, u64 idx);
+static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *allocated);
+static u64 arena_next_pow2(__u64 n);
+static u64 size_to_order(size_t size);
+static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
+					int order, size_t norder);
+static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr);

[Severity: Medium]
Does this forward declaration of buddy_alloc_memory() break the build at this commit? It omits the fifth parameter (bool grow) from the definition:

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c:
static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
int order, size_t norder, bool grow)

Although the later commit "selftests/bpf: libarena: Handle NMI reentrancy" adds bool grow to the prototype, this commit fails to compile with conflicting types and breaks bisection. Note also that buddy_alloc_memory(), arena_next_pow2(), size_to_order() and buddy_free_unlocked() are not called before their definitions in this patch.

[ ... ]

Quoted 34 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +33 -0
+void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
+{
+	struct buddy_cache __arena *cache;
+	void __arena *address = NULL;
+
+	if (!buddy_order_cached(order))
+		return NULL;
+
+	cache = buddy_cache_enter(buddy);
+	if (!cache)
+		return NULL;
+
+	address = buddy_cache_pop(cache, order);
+	buddy_cache_exit(cache);
+
+	return address;
+}
+
+/*
+ * Retrieve the order of an allocation from the address. Reject addresses
+ * that do not start an allocated block so that the locked path can report
+ * them, instead of caching memory that overlaps a live allocation. Cached
+ * objects stay marked as allocated, so freeing an object that is already
+ * cached is not detected.
+ */
+static int buddy_cache_get_order(void __arena *addr)
+{
+	struct buddy_chunk __arena *chunk;
+	bool allocated;
+	u64 idx;
+
+	if ((u64)addr & (BUDDY_MIN_ALLOC_BYTES - 1))
+		return BUDDY_CHUNK_NUM_ORDERS;
 

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 169

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +10 -0
+	chunk = (void __arena *)((u64)addr & ~BUDDY_CHUNK_OFFSET_MASK);
+	idx = ((u64)addr & BUDDY_CHUNK_OFFSET_MASK) / BUDDY_MIN_ALLOC_BYTES;
+
+	if (idx_is_allocated(chunk, idx, &allocated) || !allocated)
+		return BUDDY_CHUNK_NUM_ORDERS;
+
+	return idx_get_order(chunk, idx);
+}
+
+__always_inline int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)

[Severity: Low]
Should buddy_cache_alloc() and buddy_cache_free() be marked static like the other internal cache helpers in buddy.bpf.c? Neither helper is declared in buddy.h or referenced outside this file, and omitting static prevents buddy_cache_alloc() from being inlined as a local helper into buddy_alloc().

[ ... ]

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +5 -1
@@ -819,7 +1012,18 @@ static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size
 __weak
 void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)
 {
-	return buddy_alloc_memory(buddy, size, size_to_order(size), 0, true);
+	void __arena *address;
+	int order;
+
+	if (!buddy)
+		return NULL;

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size · line 1029

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +7 -0
+
+	order = size_to_order(size);
+	address = buddy_cache_alloc(buddy, order);
+	if (address)
+		return address;
+
+	return buddy_alloc_memory(buddy, size, order, 0, true);
 }
 
 __weak

[Severity: Low]
Should buddy_alloc_nogrow() also check buddy_cache_alloc() before falling back to buddy_alloc_memory()?

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c:
__weak
void __arena *buddy_alloc_nogrow(struct buddy __arena *buddy, size_t size)

{
	return buddy_alloc_memory(buddy, size, size_to_order(size), 0, false);
}

When buddy_free() caches a small object, the object stays marked allocated and off the chunk freelists. Because buddy_alloc_nogrow() calls buddy_alloc_memory() directly, it always takes the central buddy lock and can return NULL when the chunk freelists are empty even though free objects of the requested order are sitting in the local per-CPU cache.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
author reviewer
#9 lore raw

PATCH v4 6/9 selftests/bpf: libarena: Handle NMI reentrancy

In reply to Emil Tsalapatis

An NMI can interrupt the buddy allocator while it holds the buddy lock, so code running in NMI context must not wait for that lock.

Use trylock for buddy operations in NMI context and normal locking in other contexts. If the buddy lock cannot be acquired, allocations return NULL and frees transfer ownership to an intrusive deferred-free list.

Drain deferred frees on a later successful lock acquisition, including from NMI context.

---
 .../bpf/libarena/include/libarena/buddy.h     |   3 +
 .../bpf/libarena/selftests/test_buddy.bpf.c   |   2 +
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 128 ++++++++++++++++--
 3 files changed, 123 insertions(+), 10 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +3 -0
index ec5e79a07540..7553ad5a879d 100644
@@ -49,6 +49,8 @@ struct buddy_header {
 	u32 next_index; /* Same for the next allocation. */
 };
 
+struct buddy_deferred_free;
+
 /*
  * We bring memory into the allocator 1 MiB at a time.
  */
@@ -103,6 +105,7 @@ struct buddy {
 	arena_spinlock_t lock;			/* Allocator lock */
 	u64 vaddr;				/* Allocation into reserved vaddr */
 	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
+	struct buddy_deferred_free __arena *deferred_free;
 };
 
 #ifdef __BPF__
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +2 -0
index 85a7ea8b2e97..e7c6ac76433c 100644
@@ -44,6 +44,8 @@ __weak int test_buddy_create(void)
 		ret = buddy_destroy(&buddy);
 		if (ret)
 			return ret;
+		if (buddy.deferred_free)
+			return -EINVAL;
 		if (buddy.percpu[0])
 			return -EINVAL;
 	}
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +118 -10

196 lines not on this page · raw message

Signature · 1 line
2.52.0
#10 lore raw

Re: [PATCH bpf-next v4 6/9] selftests/bpf: libarena: Handle NMI reentrancy

Thank you for your contribution! Sashiko AI review found 3 potential issues to consider: - [Medium] selftests/bpf: buddy_alloc_memory() grows allocator in NMI context - [Medium] selftests/bpf…

Thank you for your contribution! Sashiko AI review found 3 potential issues to consider:
- [Medium] selftests/bpf: buddy_alloc_memory() grows allocator in NMI context
- [Medium] selftests/bpf: unvalidated write and error propagation in deferred free
- [Low] selftests/bpf: deferred frees stay unpoisoned in buddy_deferred_free_start()
--

commit 88f6bdc1e521e6f215ca4ea48a935038a6d8cf00
Author: Emil Tsalapatis <[email protected]>

selftests/bpf: libarena: Handle NMI reentrancy

This commit switches the libarena buddy allocator to use trylock in NMI context and defers frees to an intrusive list when the buddy lock cannot be acquired.

Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +0 -0
index 13c55cf53e524..4d4d21356935d 100644

[ ... ]

Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +0 -1
@@ -46,10 +47,14 @@ static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al
 static u64 arena_next_pow2(__u64 n);
 static u64 size_to_order(size_t size);
 static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
-					int order, size_t norder);

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al · line 58

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +6 -1
+					int order, size_t norder, bool grow);
 static int buddy_free_unlocked(struct buddy __arena *buddy, u64 addr);
+static bool buddy_deferred_free_pending(struct buddy __arena *buddy);
+static int buddy_deferred_free_complete(struct buddy __arena *buddy);
 
-#define buddy_lock(buddy, flags) (arena_spin_lock_irqsave(&(buddy)->lock, (flags)))
+#define buddy_lock(buddy, flags)						\
+	(bpf_in_nmi() ? arena_spin_trylock_irqsave(&(buddy)->lock, (flags)) :	\
+			arena_spin_lock_irqsave(&(buddy)->lock, (flags)))
 #define buddy_unlock(buddy, flags) (arena_spin_unlock_irqrestore(&(buddy)->lock, (flags)))

[Severity: Medium]
Can buddy_alloc_memory() still call buddy_chunk_get() to grow the allocator when bpf_in_nmi() is true?

When an allocation in NMI context misses the per-cpu cache and existing chunks, buddy_alloc_memory() calls buddy_chunk_get():

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c:buddy_chunk_get() {
    ...
	ret = buddy_alloc_arena_vaddr(buddy, &vaddr);
	if (ret)
		return NULL;
    ...
	/* Unreserve the address space. */
	bpf_arena_free_pages(&arena, (void __arena *)vaddr,
			     BUDDY_CHUNK_PAGES);

	chunk = bpf_arena_alloc_pages(&arena, (void __arena *)vaddr,
				      BUDDY_CHUNK_PAGES, NUMA_NO_NODE, 0);
    ...
}

Because NMI programs are non-sleepable, bpf_arena_free_pages() defers unreservation to a workqueue via irq_work instead of updating the arena range tree synchronously. The immediately following bpf_arena_alloc_pages() at vaddr then always fails because the range is still marked reserved, logging an allocation failure and leaking 1 MiB of buddy->vaddr address space per attempt. Should buddy_alloc_memory() avoid calling buddy_chunk_get() when bpf_in_nmi() is true?

[ ... ]

Quoted 68 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +57 -0
@@ -970,6 +977,13 @@ static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size
 	if (buddy_lock(buddy, flags))
 		return NULL;
 
+	if (unlikely(buddy_deferred_free_pending(buddy))) {
+		if (buddy_deferred_free_complete(buddy)) {
+			buddy_unlock(buddy, flags);
+			return NULL;
+		}
+	}
+
 	address = (u8 __arena *)buddy_alloc_from_existing_chunks(buddy, order, norder);
 	buddy_unlock(buddy, flags);
 	if (address)
@@ -1176,10 +1190,90 @@ static __always_inline int buddy_free_unlocked(struct buddy __arena *buddy, u64
 	return 0;
 }
 
+static bool buddy_deferred_free_pending(struct buddy __arena *buddy)
+{
+	return buddy->deferred_free != NULL;
+}
+
+static __always_inline void buddy_deferred_free_push(struct buddy __arena *buddy,
+						   void __arena *first, void __arena *last)
+{
+	void __arena *head;
+
+	do {
+		head = READ_ONCE(buddy->deferred_free);
+		*(void __arena * __arena *)last = head;
+	} while (cmpxchg((void __arena * __arena *)&buddy->deferred_free,
+			 head, first) != head && can_loop);
+}
+
+static void buddy_deferred_free_start(struct buddy __arena *buddy, void __arena *addr)
+{
+	/*
+	 * Make a linked list by chaining the allocations into a linked list.
+	 * Possible because allocations are 16 bytes minimum and so fit a pointer.
+	 */
+	asan_unpoison(addr, sizeof(void *));
+	buddy_deferred_free_push(buddy, addr, addr);
+}
+
+static void buddy_deferred_free_start_bulk(struct buddy __arena *buddy,
+		 void __arena * __arena *addrs, size_t naddrs)
+{
+	void __arena *first, *last, *addr;
+	unsigned int i;
+
+	/*
+	 * Chain the allocations into a local linked list. Possible because
+	 * allocations are 16 bytes minimum and so fit a pointer.
+	 */
+	first = NULL;
+	last = NULL;
+	for (i = zero; i < naddrs && can_loop; i++) {
+		addr = addrs[i];
+		if (!addr)
+			continue;
+
+		asan_unpoison(addr, sizeof(void *));
+
+		if (!first)
+			first = addr;
+		else
+			*(void __arena * __arena *)last = addr;

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c static __always_inline int buddy_free_unlocked(struct buddy __arena *buddy, u64 · line 1252

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +10 -0
+
+		last = addr;
+	}
+
+	if (!first)
+		return;
+
+	/* Splice the local list onto the deferred-free list. */
+	buddy_deferred_free_push(buddy, first, last);
+}

[Severity: Low]
Does buddy_deferred_free_start() leave deferred objects unpoisoned in the asan shadow map until buddy_deferred_free_complete() runs?

Both buddy_deferred_free_start() and buddy_deferred_free_start_bulk() call asan_unpoison(addr, sizeof(void *)) and leave the freed object (including any padding bytes in the first 8 bytes when the allocation size was under 8 bytes) unpoisoned while it sits on buddy->deferred_free. Use-after-free accesses during that window will not be caught by asan, and writes to the first 8 bytes can corrupt the intrusive list pointer without triggering an asan violation.

Quoted 41 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +25 -3
+
+static int buddy_deferred_free_complete(struct buddy __arena *buddy)
+{
+	void __arena *head, *old;
+	int ret = 0, err;
+
+	head = __sync_lock_test_and_set((void __arena * __arena *)&buddy->deferred_free,
+					NULL);
+
+	while (head && can_loop) {
+		old = head;
+		head = *(void __arena * __arena *)head;
+
+		err = buddy_free_unlocked(buddy, (u64)old);
+		ret = ret ?: err;
+	}
+
+	return ret;
+}
+
 __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 {
 	unsigned long flags;
-	int ret;
+	int ret, err;
 
 	if (!buddy)
 		return -EINVAL;
@@ -1193,20 +1287,28 @@ __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr)
 		return 0;
 
 	ret = buddy_lock(buddy, flags);
-	if (ret)
-		return ret;
+	if (ret) {
+		buddy_deferred_free_start(buddy, addr);
+		return 0;
+	}
 
 	ret = buddy_free_unlocked(buddy, (u64)addr);
 

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c __weak int buddy_free(struct buddy __arena *buddy, void __arena *addr) · line 1306

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +6 -0
+	/* Drain any frees stranded during NMI/lock failure. */
+	if (unlikely(buddy_deferred_free_pending(buddy))) {
+		err = buddy_deferred_free_complete(buddy);
+		ret = ret ?: err;
+	}
+
 	buddy_unlock(buddy, flags);
 
 	return ret;
 }

[Severity: Medium]
Can buddy_deferred_free_start() and buddy_deferred_free_start_bulk() overwrite memory before validating that the address is an allocated block?

Unlike buddy_cache_free(), which checks alignment and allocation state via buddy_cache_get_order() before touching the block, the deferred-free paths unpoison and write the next pointer directly into *(void __arena * __arena *)addr when buddy_lock() fails. Passing an unaligned, interior,already-freed, or duplicate address while the lock is contended corrupts 8 bytes at addr or creates a cycle in buddy->deferred_free.

In addition, when buddy_deferred_free_complete() later drains an invalid entry, propagating its error causes buddy_alloc_memory() to abort and return NULL for an unrelated allocation, and causes buddy_free() to return an error even when the current caller's addr was freed without issue.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=6
#11 lore raw

Re: [PATCH bpf-next v4 6/9] selftests/bpf: libarena: Handle NMI reentrancy

In reply to Emil Tsalapatis
TL;DR: The prototype fix for buddy_alloc_memory() in this patch appears to repair a build break introduced by the previous per-CPU caches commit, which may break bisection; consider folding it into…
Quoted 1 line

selftests/bpf: libarena: Handle NMI reentrancy

TL;DR: The prototype fix for buddy_alloc_memory() in this patch appears to repair a build break introduced by the previous per-CPU caches commit, which may break bisection; consider folding it into that commit.

Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +0 -0

[ ... ]

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al · line 50

Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +1 -1
@@ -46,10 +47,14 @@ static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al
 static u64 arena_next_pow2(__u64 n);
 static u64 size_to_order(size_t size);
 static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
-					int order, size_t norder);
+					int order, size_t norder, bool grow);

This isn't a bug in the final tree, but this hunk appears to fix a build break from the previous commit, b92c329df4ab ("selftests/bpf: libarena:
Add buddy per-CPU caches"). That commit added the forward declaration:

	static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
						int order, size_t norder);

while the definition takes five parameters:

static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
int order, size_t norder, bool grow)

Won't b92c329df4ab fail with "conflicting types for buddy_alloc_memory", which breaks bisection? The prototype change is unrelated to NMI reentrancy and the commit message does not mention it.

Could it be folded into b92c329df4ab so that each commit in the series builds on its own?

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/42676408513

author reviewer
#12 lore raw

Re: [PATCH bpf-next v4 6/9] selftests/bpf: libarena: Handle NMI reentrancy

Quoted 32 lines · On Mon, Nov 9, 2026 at 7:05 PM <[email protected]> wrote:
Quoted 2 lines

selftests/bpf: libarena: Handle NMI reentrancy

TL;DR: The prototype fix for buddy_alloc_memory() in this patch appears to repair a build break introduced by the previous per-CPU caches commit, which may break bisection; consider folding it into that commit.

Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +0 -0

[ ... ]

tools/testing/selftests/bpf/libarena/src/buddy.bpf.c static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al · line 50

Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +1 -1
@@ -46,10 +47,14 @@ static int idx_is_allocated(struct buddy_chunk __arena *chunk, u64 idx, bool *al
 static u64 arena_next_pow2(__u64 n);
 static u64 size_to_order(size_t size);
 static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
-                                     int order, size_t norder);
+                                     int order, size_t norder, bool grow);

This isn't a bug in the final tree, but this hunk appears to fix a build break from the previous commit, b92c329df4ab ("selftests/bpf: libarena:
Add buddy per-CPU caches"). That commit added the forward declaration:

static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
int order, size_t norder);

while the definition takes five parameters:

static void __arena *buddy_alloc_memory(struct buddy __arena *buddy, size_t size,
int order, size_t norder, bool grow)

Quoted 7 lines

Won't b92c329df4ab fail with "conflicting types for buddy_alloc_memory", which breaks bisection? The prototype change is unrelated to NMI reentrancy and the commit message does not mention it.

Could it be folded into b92c329df4ab so that each commit in the series builds on its own?

Ack, the other nits are valid too but this definitely needs fixing.

pw-bot: cr

Quoted 8 lines

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/42676408513

author reviewer
#13 lore raw

PATCH v4 7/9 selftests/bpf: libarena: Refill local caches in batches

In reply to Emil Tsalapatis

Cache misses and full-cache frees take the buddy lock for each object. Batch cache refills and spills to amortize locking and metadata work. Refill without growing the allocator, falling back to individual allocation when a batch is unavailable.

---
 .../bpf/libarena/include/libarena/buddy.h     |  6 ++-
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 54 +++++++++++++++++--
 2 files changed, 56 insertions(+), 4 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +5 -1
index 7553ad5a879d..a4d96909f5b0 100644
@@ -81,10 +81,14 @@ enum buddy_cache_consts {
 	 */
 	BUDDY_CACHE_MAX_CPUS = 8192,
 
+	/* Objects moved to and from the buddy allocator at once, as an order. */
+	BUDDY_CACHE_BATCH_ORDER = 3,
+	BUDDY_CACHE_BATCH_SIZE = 1 << BUDDY_CACHE_BATCH_ORDER,
+
 	/*
 	 * Objects retained locally for each allocation order.
 	 */
-	BUDDY_CACHE_CAPACITY = 16,
+	BUDDY_CACHE_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 2,
 };
 
 struct buddy_cache_order {
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +51 -3

87 lines not on this page · raw message

Signature · 1 line
2.52.0
author reviewer
#14 lore raw

PATCH v4 8/9 selftests/bpf: libarena: Add a transfer cache

In reply to Emil Tsalapatis

Batch refills amortize local-cache misses, but every batch that refills an empty local array, and every free into a full one, still goes through the buddy lock. Under contention the buddy lock and its metadata updates dominate, and spare objects on one CPU cannot serve another.

Add a fixed-size shared transfer array for each cached order, protected by a per-order lock. A full local cache moves one batch into the transfer array, and an empty one takes a batch from it before falling back to the buddy allocator. Embed the transfer arrays in struct buddy so this layer requires no dynamically allocated containers.

Check the transfer array's count before taking its lock, so that a full or empty array does not cost a lock acquisition that cannot succeed. When the array is full or its lock is busy, spill the local batch to the buddy allocator with buddy_free_bulk(), so the next frees fit in the local cache instead of each taking the transfer and buddy locks. Use trylock for both locks in NMI context, deferring frees when the buddy lock cannot be acquired. Keep both slow paths out of line so that cache hits do not pay for them.

October 21 measurements in a 16-vCPU VM (means of three runs, 64 or 256 allocations per cycle, 2-8 producers) showed 17-60% lower allocation latency and 60-74% lower free latency than direct bulk spilling. With 8 producers and 256 allocations per cycle, cross-CPU allocation/free latencies dropped from 1188/1218 ns to 482/408 ns.

---
 .../bpf/libarena/include/libarena/buddy.h     |  11 ++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 122 +++++++++++++++---
 2 files changed, 118 insertions(+), 15 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +11 -0
index a4d96909f5b0..154a5d1ed0f1 100644
@@ -89,6 +89,9 @@ enum buddy_cache_consts {
 	 * Objects retained locally for each allocation order.
 	 */
 	BUDDY_CACHE_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 2,
+
+	/* Number of objects shared between per-CPU caches for each order. */
+	BUDDY_TRANSFER_CAPACITY = BUDDY_CACHE_BATCH_SIZE * 8,
 };
 
 struct buddy_cache_order {
@@ -104,11 +107,19 @@ struct buddy_cache {
 	struct buddy_cache_order orders[BUDDY_CACHE_NUM_ORDERS];
 };
 
+/* Per-order array shared between the per-CPU caches. */
+struct buddy_transfer_order {
+	arena_spinlock_t lock;
+	u32 elems;
+	void __arena *objects[BUDDY_TRANSFER_CAPACITY];
+} __attribute__((aligned(64)));
+
 struct buddy {
 	struct buddy_chunk __arena *first_chunk;		/* Pointer to the chunk linked list. */
 	arena_spinlock_t lock;			/* Allocator lock */
 	u64 vaddr;				/* Allocation into reserved vaddr */
 	struct buddy_cache __arena *percpu[BUDDY_CACHE_MAX_CPUS];
+	struct buddy_transfer_order transfer[BUDDY_CACHE_NUM_ORDERS];
 	struct buddy_deferred_free __arena *deferred_free;
 };
 
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +107 -15

171 lines not on this page · raw message

Signature · 1 line
2.52.0
author reviewer
#15 lore raw

PATCH v4 9/9 selftests/bpf: libarena: Cover buddy cache fast paths

In reply to Emil Tsalapatis

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.

---
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 262 ++++++++++++++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    |   5 +
 2 files changed, 267 insertions(+)
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +262 -0
index e7c6ac76433c..a25326a3b9a0 100644
@@ -17,6 +17,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 +239,248 @@ __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 __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;
+
+	cpu = bpf_get_smp_processor_id();
+	cache = buddy.percpu[cpu];
+	if (!cache) {
+		ret = -EINVAL;
+		goto out;
+	}
+	slots = &cache->orders[TEST_CACHE_ORDER];
+	transfer = &buddy.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";
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +5 -0
index ef7e87344e83..37803ee23fd1 100644
@@ -1223,6 +1223,11 @@ static int buddy_alloc_bulk_memory(struct buddy __arena *buddy, size_t size, siz
 	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, grow);
 	if (!address)
Signature · 1 line
2.52.0
#16 lore raw

Re: [PATCH bpf-next v4 9/9] selftests/bpf: libarena: Cover buddy cache fast paths

TL;DR: Nit only, in the test: test_buddy_cache_paths() frees bulk[0] and bulk[1] outside the loop; the review asks whether the loop could start at zero instead.
Quoted 1 line

selftests/bpf: libarena: Cover buddy cache fast paths

TL;DR: Nit only, in the test: test_buddy_cache_paths() frees bulk[0] and bulk[1] outside the loop; the review asks whether the loop could start at zero instead.

Quoted 1 line
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +0 -0

[ ... ]

Quoted 5 lines
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +5 -0
+	ret = buddy_free(&buddy, alloc_path_test.bulk[0]);
+	if (ret)
+		goto out;
+
+	ret = buddy_free(&buddy, alloc_path_test.bulk[1]);

tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c __weak int test_buddy_alignment(void) · line 424

Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +10 -0
+	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;
+	}

This isn't a bug, but is there a reason bulk[0] and bulk[1] are freed outside the loop in test_buddy_cache_paths()? Nothing checks the cache state between these frees, so could the loop start at zero and cover all nine frees?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/42676408513