Re: [PATCH bpf-next 1/2] bpf: Introduce range_tree data structure and use it in bpf arena

[Barret Rhoden <brho@google.com>]

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;
> +}