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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [Critical] ABA vulnerability in lock-free freelist operations leads to memory corruption
- [High] Inserting duplicate keys in `RB_DUPLICATE` mode silently overwrites subtrees and leaks memory
- [High] Unchecked early loop termination (`can_loop`) corrupts the tree structure and causes massive memory leaks
- [Medium] Missing build system integration renders new tests as dead code
--

commit 3a9a1af9570223a1c9cf74c5f2e9d724407fddac
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.
The data structure supports key-value and node-based APIs, and uses
the libarena memory allocator to manage its data.

> diff --git a/tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c
> new file mode 100644
> index 0000000000000..17d46c4af3324
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c
> @@ -0,0 +1,974 @@
> +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
> +
> +#include <libarena/common.h>

These new test files are added to the selftests directory, but they do not
appear to be integrated into the build system. Per the selftests subsystem
guidelines, files not explicitly added to variables like TEST_PROGS or
TEST_GEN_FILES in the Makefile won't be compiled or executed during normal
runs. Should these be added to the Makefile?

[ ... ]

> 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..2ce2dfe5a2235
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c

[ ... ]

> +static
> +rbnode_t *rbnode_find(rbnode_t *subtree, u64 key, enum rbnode_find_mode mode)
> +{
> +	rbnode_t *node = subtree;
> +	int dir;
> +
> +	if (!subtree)
> +		return NULL;
> +
> +	while (can_loop) {
> +		/*
> +		 * If we are not looking for the least upper bound,
> +		 * we have found the only key. Otherwise keep going
> +		 * until we find the "leftmost" instance of the key.
> +		 */
> +		if (mode == RBN_FIND_DFL && node->key == key)
> +			break;
> +
> +		dir = (key <= node->key) ? 0 : 1;
> +
> +		if (!node->child[dir])
> +			break;
> +
> +		/*
> +		 * For least upper bound lookups, ensure that we
> +		 * stop searching once we find the rightmost key.
> +		 */
> +		if (node->key == key && node->child[dir]->key != key)
> +			break;
> +
> +		node = node->child[dir];
> +	}
> +
> +	return node;
> +}

When mode is RBN_FIND_LUB, this loop can break early and return an internal
node that has a valid, non-NULL child. Back in rb_node_insert(), the new
node is unconditionally assigned to parent->left (since key <= parent->key)
which could silently overwrite the existing child pointer and leak the
existing subtree. Does this correctly handle duplicate key insertions without
detaching subtrees?

[ ... ]

> +static inline rbnode_t *rb_node_alloc_common(rbtree_t *rbtree __arg_arena, u64 key, u64 value)
> +{
> +	rbnode_t *rbnode = NULL;
> +
> +	if (unlikely(!rbtree))
> +		return NULL;
> +
> +	/* Use the built-in node cache for the rbtree to avoid going to the allocator. */
> +	do  {
> +		rbnode = rbtree->freelist;
> +		if (!rbnode)
> +			break;
> +
> +	} while (cmpxchg(&rbtree->freelist, rbnode, rbnode->parent) != rbnode && can_loop);

Could this lockless cmpxchg sequence suffer from the ABA problem?

If a thread is preempted after evaluating rbnode->parent but before executing
cmpxchg, another thread could pop rbnode, allocate it, and free it back to
the freelist with a completely different parent pointer. When the original
thread resumes, the cmpxchg succeeds but erroneously sets the freelist head
to the stale parent pointer. This could link an actively used tree node back
into the freelist and lead to memory corruption.

[ ... ]

> +__weak
> +int rb_node_free(rbtree_t *rbtree __arg_arena, rbnode_t *rbnode __arg_arena)
> +{
> +	rbnode_t *old;
> +
> +	do {
> +		old = rbtree->freelist;
> +		rbnode->parent = old;
> +	} while (cmpxchg(&rbtree->freelist, old, rbnode) != old && can_loop);
> +
> +	return 0;
> +}

Similarly, could this free implementation also be vulnerable to the ABA
problem if the freelist head is rapidly popped and pushed concurrently?

[ ... ]

> +static inline rbnode_t *rbnode_least(rbnode_t *subtree)
> +{
> +	while (subtree->left && can_loop)
> +		subtree = subtree->left;
> +
> +	return subtree;
> +}

If the loop limit is reached and can_loop terminates early, could this
return a node that still has a left child?

During node removal, this node would be swapped with the target node, leaving
the target node with both left and potentially right children. The removal
logic evaluates if (!node->left != !node->right) which would then bypass
the single-child handler and fall through to the zero-child path, setting the
parent's child pointer to NULL and leaking both subtrees. Are early loop
terminations via can_loop safely handled without leaving the tree structure
corrupted?

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