mirror of
https://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git
synced 2024-12-28 16:52:18 +00:00
b795379757
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
22 lines
667 B
C
22 lines
667 B
C
/* SPDX-License-Identifier: GPL-2.0-only */
|
|
/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
|
|
#ifndef _RANGE_TREE_H
|
|
#define _RANGE_TREE_H 1
|
|
|
|
struct range_tree {
|
|
/* root of interval tree */
|
|
struct rb_root_cached it_root;
|
|
/* root of rbtree of interval sizes */
|
|
struct rb_root_cached range_size_root;
|
|
};
|
|
|
|
void range_tree_init(struct range_tree *rt);
|
|
void range_tree_destroy(struct range_tree *rt);
|
|
|
|
int range_tree_clear(struct range_tree *rt, u32 start, u32 len);
|
|
int range_tree_set(struct range_tree *rt, u32 start, u32 len);
|
|
int is_range_tree_set(struct range_tree *rt, u32 start, u32 len);
|
|
s64 range_tree_find(struct range_tree *rt, u32 len);
|
|
|
|
#endif
|