]> www.infradead.org Git - users/jedix/linux-maple.git/commit
bpf: Introduce range_tree data structure and use it in bpf arena
authorAlexei Starovoitov <ast@kernel.org>
Fri, 8 Nov 2024 02:56:15 +0000 (18:56 -0800)
committerAndrii Nakryiko <andrii@kernel.org>
Wed, 13 Nov 2024 21:52:45 +0000 (13:52 -0800)
commitb795379757eb054925fbb6783559c86f01c1a614
tree7feaef198ba519f8e4c17370c6564005517153a2
parent871438170326dc28125cb823d19c1d5c5304474d
bpf: Introduce range_tree data structure and use it in bpf arena

Introduce range_tree data structure and use it in bpf arena to track
ranges of allocated pages. range_tree is a large bitmap that is
implemented as interval tree plus rbtree. The contiguous sequence of
bits represents unallocated pages.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Link: https://lore.kernel.org/bpf/20241108025616.17625-2-alexei.starovoitov@gmail.com
kernel/bpf/Makefile
kernel/bpf/arena.c
kernel/bpf/range_tree.c [new file with mode: 0644]
kernel/bpf/range_tree.h [new file with mode: 0644]