[bpf-next,0/2] bpf: range_tree for bpf arena

Message

Alexei Starovoitov Nov. 8, 2024, 2:56 a.m. UTC

From: Alexei Starovoitov <[e-mail]>

Introduce range_tree (internval tree plus rbtree) to track
unallocated ranges in bpf arena and replace maple_tree with it.
This is a step towards making bpf_arena|free_alloc_pages non-sleepable.
The previous approach to reuse drm_mm to replace maple_tree reached
dead end, since sizeof(struct drm_mm_node) = 168 and
sizeof(struct maple_node) = 256 while
sizeof(struct range_node) = 64 introduced in this patch.
Not only it's smaller, but the algorithm splits and merges
adjacent ranges. Ultimate performance doesn't matter.
The main objective of range_tree is to work in context
where kmalloc/kfree are not safe. It achieves that via bpf_mem_alloc.

Alexei Starovoitov (2):
  bpf: Introduce range_tree data structure and use it in bpf arena
  selftests/bpf: Add a test for arena range tree algorithm

 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/arena.c                            |  34 ++-
 kernel/bpf/range_tree.c                       | 262 ++++++++++++++++++
 kernel/bpf/range_tree.h                       |  21 ++
 .../bpf/progs/verifier_arena_large.c          | 110 +++++++-
 5 files changed, 412 insertions(+), 17 deletions(-)
 create mode 100644 kernel/bpf/range_tree.c
 create mode 100644 kernel/bpf/range_tree.h