bpf libarena allocator improvements
Subsystems (3)
Emil Tsalapatis
reviewerv2 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 260/64 4.1x 602/65 9.3x 866/65 13.3x 4067/68 59.8x
4 244/62 3.9x 449/63 7.1x 2264/67 33.8x 4813/75 64.2x
16 233/62 3.8x 1047/63 16.6x 2198/69 31.9x 5044/77 65.5x
64 232/75 3.1x 883/142 6.2x 2558/191 13.4x 5603/380 14.7x256 232/104 2.2x 1288/149 8.6x 2758/240 11.5x 5549/446 12.4x
Free latency (before/after ns, speedup):
allocs 1 prod 2 prod 4 prod 8 prod
1 236/66 3.6x 250/67 3.7x 588/67 8.8x 4014/66 60.8x
4 236/61 3.9x 353/61 5.8x 2373/62 38.3x 4979/62 80.3x
16 231/60 3.9x 1104/61 18.1x 2233/61 36.6x 5126/61 84.0x
64 231/75 3.1x 861/97 8.9x 2555/140 18.2x 5666/331 17.1x256 230/137 1.7x 1182/107 11.0x 2766/179 15.5x 5584/404 13.8x
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 273/64 4.3x 865/64 13.5x 1192/65 18.3x 4274/69 61.9x
4 231/62 3.7x 740/63 11.7x 2431/67 36.3x 5053/79 64.0x
16 221/62 3.6x 342/63 5.4x 2233/68 32.8x 4991/89 56.1x
64 240/90 2.7x 959/153 6.3x 1503/113 13.3x 5178/353 14.7x256 221/102 2.2x 1294/210 6.2x 2512/252 10.0x 5640/374 15.1x
Free latency (before/after ns, speedup):
allocs 1 prod 2 prod 4 prod 8 prod
1 250/66 3.8x 594/66 9.0x 1055/65 16.2x 4147/66 62.8x
4 224/61 3.7x 590/62 9.5x 2393/61 39.2x 5061/62 81.6x
16 212/60 3.5x 304/61 5.0x 2158/62 34.8x 4984/61 81.7x
64 233/86 2.7x 915/105 8.7x 1469/95 15.5x 5174/268 19.3x256 214/133 1.6x 1215/121 10.0x 2511/166 15.1x 5633/309 18.2x
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 (7):
selftests/bpf: libarena: Add bulk buddy allocation helpers selftests/bpf: Add a parallel buddy allocator benchmark 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 +++ .../bpf/libarena/include/libarena/buddy.h | 56 ++ .../bpf/libarena/include/libarena/common.h | 4 + .../bpf/libarena/selftests/test_buddy.bpf.c | 273 ++++++++ .../selftests/bpf/libarena/src/buddy.bpf.c | 630 +++++++++++++++++- 8 files changed, 1166 insertions(+), 45 deletions(-)
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 1/7 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 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 | 4 + .../selftests/bpf/libarena/src/buddy.bpf.c | 142 ++++++++++++++---- 2 files changed, 118 insertions(+), 28 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +4 -0
@@ -76,6 +76,10 @@ struct buddy { int buddy_init(struct buddy __arena *buddy); int buddy_destroy(struct buddy __arena *buddy); int buddy_free(struct buddy __arena *buddy, void __arena *free); +int buddy_free_bulk(struct buddy __arena *buddy, void __arena * __arena *addrs, +size_t naddrs); void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size); +int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder, + void __arena * __arena *out);#endif /* __BPF__ */
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +114 -28
239 lines not on this page · raw message
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 2/7 selftests/bpf: Add a parallel buddy allocator benchmark
In reply to Emil TsalapatisAdd 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
@@ -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
@@ -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
119 lines not on this page · raw message
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 3/7 selftests/bpf: libarena: Add buddy per-CPU caches
In reply to Emil TsalapatisEvery 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.
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 | 215 +++++++++++++++++- 4 files changed, 257 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +34 -0
@@ -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 , + +/* +* 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
@@ -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
@@ -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 +210 -5
268 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH bpf-next v2 3/7] selftests/bpf: libarena: Add buddy per-CPU caches
Quoted 9 lines · 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, bounding each CPU's cache to about 1.5 KiB.
TIL the min alloc size is not PAGE_SIZE in BPF buddy allocator :)
Quoted 31 lines
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 <[email protected]>--- .../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(-)tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +3
-0@@ -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 { +/*
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h struct buddy_chunk { · line 80
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +10
-0+* 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)
Quoted 21 lines
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +6
-0+/* +* Objects retained locally for each allocation order. +*/ + BUDDY_CACHE_CAPACITY = 16, +}; +tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +7
-0@@ -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 ()];
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 81
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +10
-0+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.
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 89
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +8
-0+ +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?
Signature · 2 lines
Cheers, Harry / Hyeonggon
Emil Tsalapatis
reviewerRe: [PATCH bpf-next v2 3/7] selftests/bpf: libarena: Add buddy per-CPU caches
Quoted 60 lines · Harry Yoo
Quoted 9 lines · 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, bounding each CPU's cache to about 1.5 KiB.
TIL the min alloc size is not
PAGE_SIZEin BPF buddy allocator :)Quoted 31 lines
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 <[email protected]>--- .../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(-)tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +3
-0@@ -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 { +/* tools/testing/selftests/bpf/libarena/include/libarena/buddy.h struct buddy_chunk { · line 80
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +10
-0+* 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_idsfrom the kernel in BPF?NR_CPUSis upper bound supported by the kernel but during the boot process, the kernel updatesnr_cpu_idsbased on the processor of the system.
Quoted 2 lines
Kernels built with
CONFIG_MAXSMPwon't be able to use this because it uses very highNR_CPUS? (8192 on x86)
Agreed, but we should make the change in tandem with the arena spinlock code since it is also hardcoding the same constant. In fact, we should probably restructure the headers to make sure they are always in lockstep. I didn't do it in this series because I was planning it as a followup, we can also add the refactor as a preparatory commit here.
Quoted 27 lines
Quoted 27 lines
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +6
-0+/* +* Objects retained locally for each allocation order. +*/ + BUDDY_CACHE_CAPACITY = 16, +}; +tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +12
-0@@ -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
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 81
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +5
-0+* 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 ofcmpxchg()because this is percpu? Not sure if there'scmpxchg_local()equivalent in BPF...
We don't really have cmpxchg_local() available in BPF. I hacked up a prototype and the benefits were actually not that significant, about 2ns for hot alloc free loops.
Quoted 13 lines
On x86, cmpxchg instruction should be cheaper without LOCK prefix.
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 89
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +8
-0+ +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?
... this, however did matter significantly for hot loop frees. I will add it to v3 and respin.
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf-next v2 3/7] selftests/bpf: libarena: Add buddy per-CPU caches
Quoted 49 lines · Emil Tsalapatis
Quoted 5 lines · Harry Yoo
Quoted 4 lines · 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.
Quoted 22 lines
Quoted 5 lines
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_SIZEin BPF buddy allocator :)Quoted 14 lines
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 <[email protected]>---
[...]
We don't really have
cmpxchg_local()available in BPF. I hacked up a prototype and the benefits were actually not that significant, about 2ns for hot alloc free loops.Quoted 13 lines
On x86, cmpxchg instruction should be cheaper without LOCK prefix.
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c line 89
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/buddy.bpf.c +8
-0+ +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?
Quoted 2 lines
... this, however did matter significantly for hot loop frees. I will add it to v3 and respin.
What architecture are you measuring it on? Because on x86 smp_store_release() is equivalent to a WRITE_ONCE(), so unless this was suppressing compiler optimizations and the code changed by doing a simple store, I don't follow how it would help.
Emil Tsalapatis
reviewerPATCH v2 4/7 selftests/bpf: libarena: Handle NMI reentrancy
In reply to Emil TsalapatisAn NMI can interrupt the buddy allocator while it holds the buddy lock, so code running in NMI context must not take that lock.
Allow an allocation from NMI context only when the local cache can satisfy it without taking the buddy lock.
When an NMI free cannot use the local cache, link the object onto an intrusive deferred-free list. A later allocator operation from a safe context drains that list while holding the buddy lock.
--- .../bpf/libarena/include/libarena/buddy.h | 3 + .../bpf/libarena/selftests/test_buddy.bpf.c | 2 + .../selftests/bpf/libarena/src/buddy.bpf.c | 129 +++++++++++++++++- 3 files changed, 133 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +3 -0
@@ -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
@@ -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 +128 -1
195 lines not on this page · raw message
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 5/7 selftests/bpf: libarena: Refill local caches in batches
In reply to Emil TsalapatisCache hits avoid the central lock, but every cache miss still asks the buddy allocator for one object. A sequence of misses therefore repeats the same locking and metadata work.
Allocate eight objects with buddy_alloc_bulk() on a local-cache miss. Return one object directly and retain the other seven in the per-CPU LIFO array. This amortizes buddy locking and metadata updates over subsequent allocations. Skip the refill in NMI context, where the backend allocator cannot safely take its lock.
Express the array capacity as twice the batch size, so that a refilled array can still absorb a full batch of frees before it overflows.
--- .../bpf/libarena/include/libarena/buddy.h | 6 +++- .../selftests/bpf/libarena/src/buddy.bpf.c | 28 +++++++++++++++++-- 2 files changed, 30 insertions(+), 4 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +5 -1
@@ -81,10 +81,14 @@ enum buddy_cache_consts {*/ BUDDY_CACHE_MAX_CPUS =1024 , +/* 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 +25 -3
@@ -126,10 +126,28 @@ static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,return 0 ; } -void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order) +/* +* Refill an empty cache with one trip to the buddy allocator. Kept out of line +* so that cache hits do not pay for the refill path. +*/ +static __noinline void __arena * +buddy_cache_refill(struct buddy __arena *buddy, struct buddy_cache __arena *cache, +size_t size,int order) +{ + struct buddy_cache_order __arena *slots = &cache->orders[order]; + +if (buddy_alloc_bulk (buddy, size,BUDDY_CACHE_BATCH_ORDER , + (void __arena * __arena *)slots->objects)) +return NULL ; + +WRITE_ONCE (slots->elems,BUDDY_CACHE_BATCH_SIZE -1 ); +return slots->objects[BUDDY_CACHE_BATCH_SIZE -1 ]; +} + +void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t size, size_t order) { struct buddy_cache __arena *cache; - void __arena *address = NULL; + void __arena *address;if (!buddy_order_cached (order))return NULL ;
@@ -138,7 +156,11 @@ void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)if (!cache)return NULL ; +/* NMIs cannot take the buddy lock, so they only use what is already cached. */ address =buddy_cache_pop (cache, order); +if (!address && !bpf_in_nmi ()) + address =buddy_cache_refill (buddy, cache, size, order); +buddy_cache_exit (cache);return address;
@@ -1055,7 +1077,7 @@ void __arena *buddy_alloc(struct buddy __arena *buddy, size_t size)return NULL ; order =size_to_order (size); - address =buddy_cache_alloc (buddy, order); + address =buddy_cache_alloc (buddy, size, order);if (address)return address;
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 6/7 selftests/bpf: libarena: Add a transfer cache
In reply to Emil TsalapatisBatch 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. NMI context never takes the transfer lock and spills directly. Keep both slow paths out of line so that cache hits do not pay for them.
--- .../bpf/libarena/include/libarena/buddy.h | 11 ++ .../selftests/bpf/libarena/src/buddy.bpf.c | 123 +++++++++++++++++- 2 files changed, 131 insertions(+), 3 deletions(-)
tools/testing/selftests/bpf/libarena/include/libarena/buddy.h +11 -0
@@ -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 +120 -3
163 lines not on this page · raw message
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerPATCH v2 7/7 selftests/bpf: libarena: Cover buddy cache fast paths
In reply to Emil TsalapatisAdd 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
@@ -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
@@ -1172,6 +1172,11 @@ int buddy_alloc_bulk(struct buddy __arena *buddy, size_t size, size_t norder,if (!buddy || !out || norder >=BUDDY_CHUNK_NUM_ORDERS )return -EINVAL ; +/* +* Bulk allocations bypass the per-cpu caches and reserve one buddy +* block covering all returned objects. The buddy metadata records +* each object separately so it can later be freed independently. +*/ order =size_to_order (size); address =buddy_alloc_memory (buddy, size, order, norder);if (!address)
Signature · 1 line
2.52.0