Skip to content

bpf libarena allocator improvements

Emil Tsalapatis bpf 5 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v5 Latest9 patches 0 repliesApplied 9/9
  2. v49 patches 1 replySuperseded
  3. v37 patches 7 repliesSuperseded
Earlier versions · 2
VersionPostedPatchesRepliesStatus
v27 patches3 repliesSuperseded
v17 patches3 repliesSuperseded

Patches in v5 All 9 applied

#Subject and filesSizeRepliesApplied
1/9selftests/bpf: libarena: Add bulk buddy allocation helperstools/testing/selftests/bpf/libarena/include/libarena/buddy.h tools/testing/selftests/bpf/libarena/src/buddy.bpf.c+125 -290 repliesApplied
2/9selftests/bpf: Add a parallel buddy allocator benchmarktools/testing/selftests/bpf/bench.c tools/testing/selftests/bpf/benchs/bench_libarena.c tools/testing/selftests/bpf/benchs/run_bench_libarena.sh +1 more+237 -110 repliesApplied
3/9selftests/bpf: libarena: Make spinlock trylock match arena_spin_unlocktools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h+33 -30 repliesApplied
4/9selftests/bpf: libarena: Raise arena spinlock CPU limitstools/testing/selftests/bpf/libarena/include/bpf_arena_spin_lock.h tools/testing/selftests/bpf/progs/arena_spin_lock.c+4 -40 repliesApplied
5/9selftests/bpf: libarena: Add buddy per-CPU cachestools/testing/selftests/bpf/libarena/include/libarena/buddy.h tools/testing/selftests/bpf/libarena/include/libarena/common.h tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c +1 more+273 -70 repliesApplied
6/9selftests/bpf: libarena: Handle NMI reentrancytools/testing/selftests/bpf/libarena/include/libarena/buddy.h tools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c tools/testing/selftests/bpf/libarena/src/buddy.bpf.c+131 -90 repliesApplied
7/9selftests/bpf: libarena: Refill local caches in batchestools/testing/selftests/bpf/libarena/include/libarena/buddy.h tools/testing/selftests/bpf/libarena/src/buddy.bpf.c+57 -50 repliesApplied
8/9selftests/bpf: libarena: Add a transfer cachetools/testing/selftests/bpf/libarena/include/libarena/buddy.h tools/testing/selftests/bpf/libarena/src/buddy.bpf.c+118 -150 repliesApplied
9/9selftests/bpf: libarena: Cover buddy cache fast pathstools/testing/selftests/bpf/libarena/selftests/test_buddy.bpf.c tools/testing/selftests/bpf/libarena/src/buddy.bpf.c+259 -00 repliesApplied

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v5 yet.

Read the v5 thread

Cover letter [PATCH bpf-next v5 0/9] 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]>

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

- Fix the buddy_alloc_memory() prototype in the per-CPU cache patch so every intermediate patch compiles.
- Keep buddy_cache_alloc() and buddy_cache_free() static, and make buddy_alloc_nogrow() use the per-CPU caches.
- Return 0 on arena_spin_trylock() success and -EBUSY on failure, and use that convention directly in the irqsave wrapper.
- Increase the arena_spin_lock selftest's arena size for the larger qnode array.
- Validate and poison objects before queuing deferred frees, and keep deferred-drain errors from changing bulk-free ownership semantics.
- Prevent allocator growth in NMI context.
- Simplify the cache overflow test's prefill loop.

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    |  42 +-
 .../bpf/libarena/include/libarena/buddy.h     |  58 ++
 .../bpf/libarena/include/libarena/common.h    |   4 +
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 265 +++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 645 +++++++++++++++++-
 .../selftests/bpf/progs/arena_spin_lock.c     |   2 +-
 10 files changed, 1209 insertions(+), 55 deletions(-)
Signature · 1 line
2.52.0