From: Alexei Starovoitov <ast@xxxxxxxxxx> 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 -- 2.43.5
