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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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




[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux