On Mon, Jan 6, 2025 at 8:12 AM Barret Rhoden <brho@xxxxxxxxxx> wrote:
>
> 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.
I copy pasted that 'break' from the original Darrick's
commit 6772fcc8890a ("xfs: convert xbitmap to interval tree")
This asymmetrical loop termination bothered me as well,
but as far as I understood the code it's correct,
so I kept it as-is.
In bpf arena we won't have overlaps and the way the range tree
is used with preceding is_range_tree_set() or range_tree_find()
even the 'while' part is not necessary,
but somebody might copy paste the code, as you said.
This particular 'break' is more of the optimization, I think, since
next call to range_it_iter_first() is supposed to return NULL anyway.
