Re: [RESEND 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 2 potential issue(s) to consider:
- [High] Inserting duplicate keys into an `RB_DUPLICATE` rbtree overwrites existing subtrees, causing data loss and memory leaks.
- [High] The lock-free node freelist implementation is vulnerable to the ABA problem, leading to tree corruption.
--

commit 1c2293fc665383e2481f9d7ee15173fb46b0ea76
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 (key-value based, node based) 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..2ce2dfe5a2235
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c
> @@ -0,0 +1,1032 @@
[ ... ]
> +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 lock-free freelist implementation be vulnerable to the ABA problem
in concurrent environments?

If Thread A reads rbtree->freelist and evaluates rbnode->parent, and is then
delayed, Thread B could allocate rbnode, allocate its parent, and then free
rbnode back to the freelist. When Thread A resumes, the cmpxchg would
succeed because the freelist head is still rbnode, but it would erroneously
set the freelist head to the stale rbnode->parent. This could cause the
allocator to hand out an in-use tree node, leading to multiple concurrent
uses of the same memory and tree corruption.

[ ... ]

> +static
> +int rb_node_insert(rbtree_t *rbtree __arg_arena, rbnode_t *node __arg_arena)
> +{
> +	rbnode_t *grandparent, *parent = rbtree->root;
> +	enum rbnode_find_mode mode;
> +	u64 key = node->key;
> +	rbnode_t *uncle;
> +	int dir;
> +	int ret;
> +
> +	if (unlikely(!rbtree))
> +		return -EINVAL;
> +
> +	if (!parent) {
> +		rbtree->root = node;
> +		return 0;
> +	}
> +
> +	mode = RBN_FIND_DFL;
> +	/* Always find the first node with the key when allowing duplicates. */
> +	if (rbtree->insert == RB_DUPLICATE)
> +		mode = RBN_FIND_LUB;
> +	parent = rbnode_find(parent, key, mode);
> +
> +	if (key == parent->key && rbtree->insert != RB_DUPLICATE) {
> +		if (rbtree->insert == RB_UPDATE) {
> +			/*
> +			 * Replace the old node with the new one.
> +			 * Free up the old node.
> +			 */
> +			ret = rbnode_replace(rbtree, parent, node);
> +			if (ret)
> +				return ret;
> +
> +			if (rbtree->alloc == RB_ALLOC)
> +				rb_node_free(rbtree, parent);
> +
> +			return 0;
> +		}
> +
> +		/* Otherwise it's RB_DEFAULT. */
> +		return -EALREADY;
> +	}
> +
> +	node->parent = parent;
> +	/* Also works if key == parent->key. */
> +	if (key <= parent->key)
> +		parent->left = node;
> +	else
> +		parent->right = node;

Does this code overwrite existing subtrees when inserting duplicate keys
into an RB_DUPLICATE rbtree?

When rbnode_find() is called with RBN_FIND_LUB, it can break early when it
finds the target key whose child in the search direction has a different
key:

tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c:rbnode_find() {
    ...
		/*
		 * 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;
    ...
}

This causes it to return an internal node where node->child[dir] is
explicitly not NULL. Back in rb_node_insert(), the new node is
unconditionally assigned to parent->left or parent->right. This blindly
overwrites the existing child pointer, permanently detaching and leaking
the previous subtree.

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