On 11/7/24 9:56 PM, Alexei Starovoitov wrote:
+/* Clear the range in this range tree */
+int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
+{
+ u32 last = start + len - 1;
+ struct range_node *new_rn;
+ struct range_node *rn;
+
+ while ((rn = range_it_iter_first(rt, start, last))) {
+ if (rn->rn_start < start && rn->rn_last > last) {
+ u32 old_last = rn->rn_last;
+
+ /* Overlaps with the entire clearing range */
+ range_it_remove(rn, rt);
+ rn->rn_last = start - 1;
+ range_it_insert(rn, rt);
+
+ /* Add a range */
+ new_rn = bpf_mem_alloc(&bpf_global_ma, sizeof(struct range_node));
+ if (!new_rn)
+ return -ENOMEM;
+ new_rn->rn_start = last + 1;
+ new_rn->rn_last = old_last;
+ range_it_insert(new_rn, rt);
+ } else if (rn->rn_start < start) {
+ /* Overlaps with the left side of the clearing range */
+ range_it_remove(rn, rt);
+ rn->rn_last = start - 1;
+ range_it_insert(rn, rt);
+ } else if (rn->rn_last > last) {
+ /* Overlaps with the right side of the clearing range */
+ range_it_remove(rn, rt);
+ rn->rn_start = last + 1;
+ range_it_insert(rn, rt);
+ break;
^^^
did you mean to have the break here, but not in the "contains entire
range" case? for the arena use case, i think you never have overlapping
intervals, so once you hit the last one, you can break. (in both
cases). though TBH, i'd just never break in case you ever have
intervals that overlap (i.e. two intervals containing 'last') - either
for arenas or for someone who copies this code for another use of
interval trees.
barret
+ } else {
+ /* in the middle of the clearing range */
+ range_it_remove(rn, rt);
+ bpf_mem_free(&bpf_global_ma, rn);
+ }
+ }
+ return 0;
+}