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.
28  *   range_tree_set(rt, 0, max);
30  *   start = range_tree_find(rt, len);
32  *     range_tree_clear(rt, start, len);
34  *   range_tree_set(rt, start, len);
52 	return rn->rn_last - rn->rn_start + 1;  in rn_size()
56 static inline struct range_node *__find_range(struct range_tree *rt, u32 len)  in __find_range()  argument
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()
75 s64 range_tree_find(struct range_tree *rt, u32 len)  in range_tree_find()  argument
79 	rn = __find_range(rt, len);  in range_tree_find()
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)
116 range_it_insert(struct range_node *rn, struct range_tree *rt)  in INTERVAL_TREE_DEFINE()
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()
123 range_it_remove(struct range_node *rn, struct range_tree *rt)  in range_it_remove()  argument
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()
131 range_it_iter_first(struct range_tree *rt, u32 start, u32 last)  in range_it_iter_first()  argument
133 	return __range_it_iter_first(&rt->it_root, start, last);  in range_it_iter_first()
137 int range_tree_clear(struct range_tree *rt, u32 start, u32 len)  in range_tree_clear()  argument
139 	u32 last = start + len - 1;  in range_tree_clear()
143 	while ((rn = range_it_iter_first(rt, start, last))) {  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()
148 			range_it_remove(rn, rt);  in range_tree_clear()
149 			rn->rn_last = start - 1;  in range_tree_clear()
150 			range_it_insert(rn, rt);  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()
160 			range_it_insert(new_rn, rt);  in range_tree_clear()
161 		} else if (rn->rn_start < start) {  in range_tree_clear()
163 			range_it_remove(rn, rt);  in range_tree_clear()
164 			rn->rn_last = start - 1;  in range_tree_clear()
165 			range_it_insert(rn, rt);  in range_tree_clear()
166 		} else if (rn->rn_last > last) {  in range_tree_clear()
168 			range_it_remove(rn, rt);  in range_tree_clear()
169 			rn->rn_start = last + 1;  in range_tree_clear()
170 			range_it_insert(rn, rt);  in range_tree_clear()
174 			range_it_remove(rn, rt);  in range_tree_clear()
184 int is_range_tree_set(struct range_tree *rt, u32 start, u32 len)  in is_range_tree_set()  argument
186 	u32 last = start + len - 1;  in is_range_tree_set()
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()
197 int range_tree_set(struct range_tree *rt, u32 start, u32 len)  in range_tree_set()  argument
199 	u32 last = start + len - 1;  in range_tree_set()
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()
210 	err = range_tree_clear(rt, start, len);  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()
220 	right = range_it_iter_first(rt, last + 1, last + 1);  in range_tree_set()
221 	if (right && right->rn_start != last + 1)  in range_tree_set()
222 		return -EFAULT;  in range_tree_set()
226 		range_it_remove(left, rt);  in range_tree_set()
227 		range_it_remove(right, 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()
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()
240 		range_it_remove(right, rt);  in range_tree_set()
241 		right->rn_start = start;  in range_tree_set()
242 		range_it_insert(right, rt);  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()
256 void range_tree_destroy(struct range_tree *rt)  in range_tree_destroy()  argument
260 	while ((rn = range_it_iter_first(rt, 0, -1U))) {  in range_tree_destroy()
261 		range_it_remove(rn, rt);  in range_tree_destroy()
266 void range_tree_init(struct range_tree *rt)  in range_tree_init()  argument
268 	rt->it_root = RB_ROOT_CACHED;  in range_tree_init()
269 	rt->range_size_root = RB_ROOT_CACHED;  in range_tree_init()