Re: [PATCH] bpf: Clear rb node linkage when freeing bpf_rb_root

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:

New issues:
- [High] Unbounded O(N) red-black tree traversal inside an IRQ-disabled spinlock critical section introduces latency spikes, potential soft/hard lockups, and deadlocks.

Pre-existing issues:
- [High] Nodes added to a deleted map element's rbtree after `bpf_obj_free_fields` are permanently leaked.
--

commit 867fefb5dd2755c5bd12c9f3bd37d5367c6793f3
Author: Kaitao Cheng <chengkaitao@kylinos.cn>

bpf: Clear rb node linkage when freeing bpf_rb_root

This commit modifies bpf_rb_root_free to clear red-black node linkage when
freeing a root. It mirrors list draining behavior by marking nodes as busy
while detaching the root, clearing the linkage, and releasing the owner
before dropping the containing object.

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index b5314c9fed3cf..c7f26336984f0 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -2296,22 +2296,30 @@ void bpf_rb_root_free(const struct btf_field *field, void *rb_root,
>  {
>  	struct rb_root_cached orig_root, *root = rb_root;
>  	struct rb_node *pos, *n;
> -	void *obj;
>  
>  	BUILD_BUG_ON(sizeof(struct rb_root_cached) > sizeof(struct bpf_rb_root));
>  	BUILD_BUG_ON(__alignof__(struct rb_root_cached) > __alignof__(struct bpf_rb_root));
>  
>  	__bpf_spin_lock_irqsave(spin_lock);
>  	orig_root = *root;
> +	bpf_rbtree_postorder_for_each_entry_safe(pos, n, &orig_root.rb_root) {
> +		struct bpf_rb_node_kern *node;
> +
> +		node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
> +		WRITE_ONCE(node->owner, BPF_PTR_POISON);
> +	}

[Severity: High]
Since there is no verifier-enforced limit on the number of nodes in a BPF
rbtree, could this O(N) post-order traversal trigger latency spikes, RCU
stalls, or NMI watchdog lockups?

This loop runs inside the __bpf_spin_lock_irqsave() critical section, which
disables local interrupts.

Additionally, since rb_first_postorder() and rb_next_postorder() are
exported and traceable, if an fentry/fexit BPF program is attached to them
and attempts to acquire the same bpf_spin_lock, will it cause a hard deadlock?

>  	*root = RB_ROOT_CACHED;
>  	__bpf_spin_unlock_irqrestore(spin_lock);

[Severity: High]
This isn't a bug introduced by this patch, but does this pattern permanently
leak memory if a concurrent BPF program adds a node after the tree is emptied?

When a map element is replaced or deleted, bpf_obj_free_fields() detaches
the tree here and sets *root = RB_ROOT_CACHED. However, a concurrent BPF
program running inside an RCU critical section might still hold a pointer
to the map element.

If that program takes the spinlock and calls bpf_rbtree_add(), it will
successfully add a new node to the now-emptied tree.

After the RCU grace period ends, bpf_mem_free_rcu() frees the map element,
but bpf_obj_free_fields() is never called again. Will the newly added node
be left behind and leaked?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260601055859.13888-1-kaitao.cheng@linux.dev?part=1