1 // SPDX-License-Identifier: GPL-2.0-only
13  * rn->rn_rbnode links it into an interval tree while
14  * rn->rb_range_size links it into a second rbtree sorted by size of the range.
23  * The implementation relies on external lock to protect rbtree-s.
24  * The alloc/free of range_node-s is done via bpf_mem_alloc.
52 	return rn->rn_last - rn->rn_start + 1;  in rn_size()
58 	struct rb_node *rb = rt->range_size_root.rb_root.rb_node;  in __find_range()
66 			rb = rb->rb_right;  in __find_range()
68 			rb = rb->rb_left;  in __find_range()
81 		return -ENOENT;  in range_tree_find()
82 	return rn->rn_start;  in range_tree_find()
89 	struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;  in __range_size_insert()
96 			link = &rb->rb_left;  in __range_size_insert()
98 			link = &rb->rb_right;  in __range_size_insert()
103 	rb_link_node(&rn->rb_range_size, rb, link);  in __range_size_insert()
104 	rb_insert_color_cached(&rn->rb_range_size, root, leftmost);  in __range_size_insert()
107 #define START(node) ((node)->rn_start)
108 #define LAST(node)  ((node)->rn_last)
118 	__range_size_insert(rn, &rt->range_size_root);  in INTERVAL_TREE_DEFINE()
119 	__range_it_insert(rn, &rt->it_root);  in INTERVAL_TREE_DEFINE()
125 	rb_erase_cached(&rn->rb_range_size, &rt->range_size_root);  in range_it_remove()
126 	RB_CLEAR_NODE(&rn->rb_range_size);  in range_it_remove()
127 	__range_it_remove(rn, &rt->it_root);  in range_it_remove()
133 	return __range_it_iter_first(&rt->it_root, start, last);  in range_it_iter_first()
139 	u32 last = start + len - 1;  in range_tree_clear()
144 		if (rn->rn_start < start && rn->rn_last > last) {  in range_tree_clear()
145 			u32 old_last = rn->rn_last;  in range_tree_clear()
149 			rn->rn_last = start - 1;  in range_tree_clear()
157 				return -ENOMEM;  in range_tree_clear()
158 			new_rn->rn_start = last + 1;  in range_tree_clear()
159 			new_rn->rn_last = old_last;  in range_tree_clear()
161 		} else if (rn->rn_start < start) {  in range_tree_clear()
162 			/* Overlaps with the left side of the clearing range */  in range_tree_clear()
164 			rn->rn_last = start - 1;  in range_tree_clear()
166 		} else if (rn->rn_last > last) {  in range_tree_clear()
169 			rn->rn_start = last + 1;  in range_tree_clear()
186 	u32 last = start + len - 1;  in is_range_tree_set()
187 	struct range_node *left;  in is_range_tree_set()  local
190 	left = range_it_iter_first(rt, start, last);  in is_range_tree_set()
191 	if (left && left->rn_start <= start && left->rn_last >= last)  in is_range_tree_set()
193 	return -ESRCH;  in is_range_tree_set()
199 	u32 last = start + len - 1;  in range_tree_set()
201 	struct range_node *left;  in range_tree_set()  local
205 	left = range_it_iter_first(rt, start, last);  in range_tree_set()
206 	if (left && left->rn_start <= start && left->rn_last >= last)  in range_tree_set()
214 	/* Do we have a left-adjacent range ? */  in range_tree_set()
215 	left = range_it_iter_first(rt, start - 1, start - 1);  in range_tree_set()
216 	if (left && left->rn_last + 1 != start)  in range_tree_set()
217 		return -EFAULT;  in range_tree_set()
219 	/* Do we have a right-adjacent range ? */  in range_tree_set()
221 	if (right && right->rn_start != last + 1)  in range_tree_set()
222 		return -EFAULT;  in range_tree_set()
224 	if (left && right) {  in range_tree_set()
225 		/* Combine left and right adjacent ranges */  in range_tree_set()
226 		range_it_remove(left, rt);  in range_tree_set()
228 		left->rn_last = right->rn_last;  in range_tree_set()
229 		range_it_insert(left, rt);  in range_tree_set()
233 	} else if (left) {  in range_tree_set()
234 		/* Combine with the left range */  in range_tree_set()
235 		range_it_remove(left, rt);  in range_tree_set()
236 		left->rn_last = last;  in range_tree_set()
237 		range_it_insert(left, rt);  in range_tree_set()
241 		right->rn_start = start;  in range_tree_set()
245 		left = bpf_mem_alloc(&bpf_global_ma, sizeof(struct range_node));  in range_tree_set()
247 		if (!left)  in range_tree_set()
248 			return -ENOMEM;  in range_tree_set()
249 		left->rn_start = start;  in range_tree_set()
250 		left->rn_last = last;  in range_tree_set()
251 		range_it_insert(left, rt);  in range_tree_set()
260 	while ((rn = range_it_iter_first(rt, 0, -1U))) {  in range_tree_destroy()
268 	rt->it_root = RB_ROOT_CACHED;  in range_tree_init()
269 	rt->range_size_root = RB_ROOT_CACHED;  in range_tree_init()