Re: [PATCH bpf-next v2 1/3] selftests/bpf: libarena: Add rbtree data structure

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] rb_print() causes a NULL pointer dereference when called on an empty tree.
- [Medium] rb_destroy() leaks the rbtree structure if node removal fails.
--

commit 02f60ec9e8c02b47259587dc8e3bbe9137e1e4ed
Author: Emil Tsalapatis <emil@etsalapatis.com>
selftests/bpf: libarena: Add rbtree data structure

This commit adds a native red-black tree data structure to libarena. It
supports multiple APIs to query and modify the tree, using the libarena memory
allocator to manage its data.

> diff --git a/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c b/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c
> new file mode 100644
> index 0000000000000..7379eba6570af
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c

[ ... ]

> +__weak
> +int rb_destroy(struct rbtree __arena *rbtree)
> +{
> +	int ret;
> +
> +	arena_subprog_init();
> +
> +	if (rbtree->alloc == RB_NOALLOC) {

[ ... ]

> +		goto out;
> +	}
> +
> +	while (rbtree->root && can_loop) {
> +		ret = rb_remove(rbtree, rbtree->root->key);
> +		if (ret)
> +			return ret;

[Severity: Medium]
Does this leak the rbtree structure if rb_remove() fails?

If rb_remove() encounters an error (for example, due to tree corruption), it
returns early here. This skips the arena_free(rbtree) call at the out label,
potentially leaking the rbtree structure and any remaining nodes.

> +	}
> +
> +out:
> +	arena_free(rbtree);
> +	return 0;
> +}

[ ... ]

> +__weak
> +int rb_print(struct rbtree __arena *rbtree)
> +{
> +	enum rb_print_state stack[RB_MAXLVL_PRINT];
> +	struct rbnode __arena *rbnode = rbtree->root;
> +	enum rb_print_state state;
> +	struct rbnode __arena *next;
> +	u64 next_addr;
> +	u8 depth;
> +	int ret;
> +
> +	if (unlikely(!rbtree))
> +		return -EINVAL;
> +
> +	depth = 0;
> +	state = RB_NONE_VISITED;
> +
> +	arena_stderr("=== RB TREE START ===\n");
> +
> +	/* Even with can_loop, the verifier doesn't like infinite loops. */
> +	while (can_loop) {
> +		if (state == RB_NONE_VISITED)
> +			rbnode_print(depth, rbnode);

[Severity: Medium]
Does this cause a NULL pointer dereference if the tree is empty?

If a user calls rb_print() on an empty tree, rbtree->root is NULL. The loop
is entered and rb_print() passes the NULL rbnode to rbnode_print().

Looking at rbnode_print(), it unconditionally dereferences the node:

inline void rbnode_print(size_t depth, struct rbnode __arena *rbn)
{
        arena_stderr("[DEPTH %d] %p (%s)\n PARENT %p", depth, rbn,
                     rbn->is_red ? "red" : "black", rbn->parent);
        ...
}

Could this lead to a crash when calling rb_print() on an empty tree?

> +
> +		/* Find which child to traverse next. */
> +		state = rb_print_next_state(rbnode, state, &next_addr);

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260603182727.3922-1-emil@etsalapatis.com?part=1