[PATCH bpf-next v1 0/7] bpf libarena allocator improvements

[Emil Tsalapatis <emil@etsalapatis.com>]

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.

Cc: Harry Yoo <harry@kernel.org>
Cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>

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           |   2 +
 .../selftests/bpf/benchs/bench_libarena.c     | 100 ++-
 .../bpf/benchs/run_bench_libarena.sh          |   8 +
 .../bpf/libarena/benchs/bench_malloc.bpf.c    |  43 ++
 .../bpf/libarena/include/libarena/buddy.h     |  10 +
 .../libarena/include/libarena/buddy_cache.h   |  61 ++
 .../bpf/libarena/selftests/test_buddy.bpf.c   | 277 ++++++++
 .../selftests/bpf/libarena/src/buddy.bpf.c    | 646 +++++++++++++++++-
 8 files changed, 1103 insertions(+), 44 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/buddy_cache.h

-- 
2.52.0