Re: [PATCH bpf-next 3/3] selftests/bpf: libarena: Add rb_next()

[Changwoo Min <changwoo@igalia.com>]

On 11/2/26 5:07 PM, Emil Tsalapatis wrote:
> On Wed Oct 28, 2026 at 6:00 AM UTC, Changwoo Min wrote:
>> Add rb_next(), the in-order successor through parent pointers.
>>
>> Add a selftest that walks a tree with repeated keys and checks the walk
>> against the order in which the head leaves the tree.
>>
>> Signed-off-by: Changwoo Min <changwoo@igalia.com>
>> ---
>>   .../bpf/libarena/include/libarena/rbtree.h    | 23 ++++++++
>>   .../bpf/libarena/selftests/test_rbtree.bpf.c  | 54 +++++++++++++++++++
>>   2 files changed, 77 insertions(+)
>>
>> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h b/tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h
>> index a8dd8c2e7596..956b4a24b52a 100644
>> --- a/tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h
>> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h
>> @@ -103,6 +103,29 @@ void rb_node_free(struct rbnode __arena *rbnode);
>>   
>>   int rb_integrity_check(struct rbtree __arena *rbtree);
>>   
>> +/*
>> + * Return the in-order successor of @node, or NULL if @node is the last one.
>> + * Walking from rb_first() with it visits the tree in key order, equal keys in
>> + * insertion order. Call it under the writer's lock.
>> + */
> 
> Let's move this to the main *.bpf.c file, with the rest of the traversal functions.

Sure. Will do in v2.

Regards,
Changwoo Min

> 
>> +static __always_inline struct rbnode __arena *rb_next(struct rbnode __arena *node)
>> +{
>> +	struct rbnode __arena *parent;
>> +
>> +	if (node->right) {
>> +		node = node->right;
>> +		while (node->left && can_loop)
>> +			node = node->left;
>> +		return node;
>> +	}
>> +
>> +	/* Climb until we leave a left subtree; its parent comes next. */
>> +	while ((parent = node->parent) && node == parent->right && can_loop)
>> +		node = parent;
>> +
>> +	return parent;
>> +}
>> +
>>   /*
>>    * Lockless reads of the head and the node count. They need not be called
>>    * under the writer's lock, so they are advisory: the tree may change before
>> diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c
>> index 57c4395c046a..784cc9edea17 100644
>> --- a/tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c
>> +++ b/tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c
>> @@ -425,6 +425,60 @@ __weak int test_rbtree_first_update(void)
>>   	return rb_destroy(rbtree);
>>   }
>>   
>> +#define NEXT_NR_NODES	64
>> +
>> +static struct rbnode __arena *next_nodes[NEXT_NR_NODES];
>> +
>> +SEC("syscall")
>> +__weak int test_rbtree_next(void)
>> +{
>> +	struct rbtree __arena *rbtree;
>> +	struct rbnode __arena *node;
>> +	u64 seed = 0xcafe;
>> +	int i;
>> +
>> +	rbtree = rb_create(RB_NOALLOC, RB_DUPLICATE);
>> +	if (!rbtree)
>> +		return 1;
>> +
>> +	/* Pseudo-random keys with repeats, so the walk crosses equal keys. */
>> +	for (i = 0; i < NEXT_NR_NODES && can_loop; i++) {
>> +		/* LCG using Knuth's MMIX constants for determinism. */
>> +		seed = seed * 6364136223846793005ULL + 1442695040888963407ULL;
>> +		node = rb_node_alloc((seed >> 33) % 16, i);
>> +		if (!node)
>> +			return 2;
>> +
>> +		if (rb_insert_node(rbtree, node))
>> +			return 3;
>> +	}
>> +
>> +	node = rb_first(rbtree);
>> +	for (i = 0; i < NEXT_NR_NODES && can_loop; i++) {
>> +		if (!node)
>> +			return 4;
>> +
>> +		next_nodes[i] = node;
>> +		node = rb_next(node);
>> +	}
>> +
>> +	if (node)
>> +		return 5;
>> +
>> +	for (i = 0; i < NEXT_NR_NODES && can_loop; i++) {
>> +		node = rb_first(rbtree);
>> +		if (node != next_nodes[i])
>> +			return 6;
>> +
>> +		if (rb_remove_node(rbtree, node))
>> +			return 7;
>> +
>> +		rb_node_free(node);
>> +	}
>> +
>> +	return rb_destroy(rbtree);
>> +}
>> +
>>   struct rb_embed {
>>   	u64 pad;
>>   	struct rbtree tree;
>