kernel/bpf/range_tree.c

Source file repositories/reference/linux-study-clean/kernel/bpf/range_tree.c

File Facts

System
Linux kernel
Corpus path
kernel/bpf/range_tree.c
Extension
.c
Size
7098 bytes
Lines
263
Domain
Core OS
Bucket
Scheduler, Processes, Timers, Sync, And Syscalls
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct range_node {
	struct rb_node rn_rbnode;
	struct rb_node rb_range_size;
	u32 rn_start;
	u32 rn_last; /* inclusive */
	u32 __rn_subtree_last;
};

static struct range_node *rb_to_range_node(struct rb_node *rb)
{
	return rb_entry(rb, struct range_node, rb_range_size);
}

static u32 rn_size(struct range_node *rn)
{
	return rn->rn_last - rn->rn_start + 1;
}

/* Find range that fits best to requested size */
static inline struct range_node *__find_range(struct range_tree *rt, u32 len)
{
	struct rb_node *rb = rt->range_size_root.rb_root.rb_node;
	struct range_node *best = NULL;

	while (rb) {
		struct range_node *rn = rb_to_range_node(rb);

		if (len <= rn_size(rn)) {
			best = rn;
			rb = rb->rb_right;
		} else {
			rb = rb->rb_left;
		}
	}

	return best;
}

s64 range_tree_find(struct range_tree *rt, u32 len)
{
	struct range_node *rn;

	rn = __find_range(rt, len);
	if (!rn)
		return -ENOENT;
	return rn->rn_start;
}

/* Insert the range into rbtree sorted by the range size */
static inline void __range_size_insert(struct range_node *rn,
				       struct rb_root_cached *root)
{
	struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
	u64 size = rn_size(rn);
	bool leftmost = true;

	while (*link) {
		rb = *link;
		if (size > rn_size(rb_to_range_node(rb))) {
			link = &rb->rb_left;
		} else {
			link = &rb->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(&rn->rb_range_size, rb, link);
	rb_insert_color_cached(&rn->rb_range_size, root, leftmost);
}

#define START(node) ((node)->rn_start)
#define LAST(node)  ((node)->rn_last)

INTERVAL_TREE_DEFINE(struct range_node, rn_rbnode, u32,
		     __rn_subtree_last, START, LAST,
		     static inline __maybe_unused,
		     __range_it)

static inline __maybe_unused void
range_it_insert(struct range_node *rn, struct range_tree *rt)
{
	__range_size_insert(rn, &rt->range_size_root);
	__range_it_insert(rn, &rt->it_root);
}

static inline __maybe_unused void
range_it_remove(struct range_node *rn, struct range_tree *rt)
{
	rb_erase_cached(&rn->rb_range_size, &rt->range_size_root);
	RB_CLEAR_NODE(&rn->rb_range_size);

Annotation

Implementation Notes