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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Failure to check `can_loop` termination leads to severe tree corruption, memory leaks, and NULL pointer dereferences.
--

commit 090a58da31563cb07c7562cdaaf67470a54e90c0
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 for querying and modifying the tree, and uses 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..0e4aaec96b6fa
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c

[ ... ]

> +__weak
> +int rb_destroy(struct rbtree __arena *rbtree)
> +{
> +	int ret = 0;
> +
> +	arena_subprog_init();
> +
> +	if (unlikely(!rbtree))
> +		return -EINVAL;

[ ... ]

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

[Severity: High]
Does this code leak memory if the loop exits early due to the can_loop
limit being reached? If the loop aborts early, the rbtree container is freed
even though the remaining nodes have not been removed.

> +	return ret;
> +}

[ ... ]

> +static
> +struct rbnode __arena *rbnode_least_upper_bound(struct rbnode __arena *subtree, uint64_t key)
> +{
> +	struct rbnode __arena *node = subtree;
> +	int dir;
> +
> +	if (!subtree)
> +		return NULL;
> +
> +	while (can_loop) {
> +		dir = (key <= node->key) ? 0 : 1;
> +
> +		if (!node->child[dir])
> +			break;
> +
> +		node = node->child[dir];
> +	}
> +
> +	return node;

[Severity: High]
If this loop terminates early because can_loop evaluates to false, will it
return an internal tree node rather than a leaf node?

> +}

[ ... ]

> +static
> +int rb_node_insert(struct rbtree __arena *rbtree,
> +		   struct rbnode __arena *node)
> +{
> +	struct rbnode __arena *grandparent, *parent = rbtree->root;
> +	u64 key = node->key;
> +	struct rbnode __arena *uncle;
> +	int dir;
> +	int ret;

[ ... ]

> +	if (rbtree->insert != RB_DUPLICATE)
> +		parent = rbnode_find(parent, key);
> +	else
> +		parent = rbnode_least_upper_bound(parent, key);

[ ... ]

> +	node->parent = parent;
> +	/* Also works if key == parent->key. */
> +	if (key <= parent->key)
> +		parent->left = node;

[Severity: High]
If rbnode_find() or rbnode_least_upper_bound() returns an internal node
due to a can_loop timeout, does unconditionally overwriting parent->left or
parent->right here permanently detach and leak the existing subtree?

> +	else
> +		parent->right = node;

[ ... ]

> +static
> +int rb_node_remove(struct rbtree __arena *rbtree,
> +		   struct rbnode __arena *node)
> +{
> +	struct rbnode __arena *parent, *sibling, *close_nephew, *distant_nephew;
> +	bool free = (rbtree->alloc == RB_ALLOC);
> +	struct rbnode __arena *replace, *initial;

[ ... ]

> +	while (can_loop) {
> +
> +		/* Balancing reached the root, there can be no imbalance. */
> +		if (!parent)
> +			return 0;

[ ... ]

> +		sibling->is_red = true;
> +		node = parent;
> +		parent = node->parent;
> +		dir = rbnode_dir(node);
> +	}
> +
> +	if (node != initial) {
> +		dir = rbnode_dir(node);
> +		parent = node->parent;
> +		sibling = parent->child[1-dir];
> +	}
> +	/*
> +	 * Almost there. We know between the parent, sibling,
> +	 * and nephews only one or two of the nephews are red. If
> +	 * it is the close one, rotate it to the sibling position,
> +	 * paint it black, and paint the previous sibling red.
> +	 */
> +
> +	close_nephew = sibling->child[dir];
> +	distant_nephew = sibling->child[1 - dir];
> +
> +	/*
> +	 * If the distant red nephew is not red, rotate
> +	 * and repaint. We need the distant nephew
> +	 * to be red. We know the close nephew is red
> +	 * because at least one of them are, so the
> +	 * distant one is black if it exists.
> +	 */
> +	if (!distant_nephew || !distant_nephew->is_red) {
> +		rbnode_rotate(rbtree, sibling, 1 - dir);
> +		sibling->is_red = true;
> +		close_nephew->is_red = false;

[Severity: High]
Can this cause a NULL pointer dereference if the rebalancing loop above
exits early due to can_loop?

An early exit bypasses the guarantee that the sibling has red children,
which means both nephews, including close_nephew, might be NULL here.

> +		distant_nephew = sibling;
> +		sibling = close_nephew;
> +	}

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