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

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

[Kaitao Cheng]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

bpf_rb_root_free() detaches the root by copying the current rb_root_cached
and then replacing the live root with RB_ROOT_CACHED. It then walks the
copied root and drops each object contained in the tree.

This leaves the rb node state intact while dropping the object. If the
object is refcounted and survives the drop, its bpf_rb_node_kern still
contains an owner pointer to the freed root and stale rb tree linkage. If
a later bpf_rb_root allocation reuses the same address, bpf_rbtree_remove()
can incorrectly pass the owner check and call rb_erase_cached() on a node
whose rb pointers belong to the old tree.

Mirror the list draining behavior by marking nodes as busy while the root
is being detached, then clear the rb node and release the owner before
dropping the containing object. This makes surviving nodes unowned and
safe to reject from remove or accept for a later add.

Fixes: 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")
Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
---
 kernel/bpf/helpers.c | 18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 9ca195104667..46e8eada463b 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -2307,22 +2307,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);
+	}
 	*root = RB_ROOT_CACHED;
 	__bpf_spin_unlock_irqrestore(spin_lock);
 
 	bpf_rbtree_postorder_for_each_entry_safe(pos, n, &orig_root.rb_root) {
-		obj = pos;
-		obj -= field->graph_root.node_offset;
+		struct bpf_rb_node_kern *node;
 
-
-		__bpf_obj_drop_impl(obj, field->graph_root.value_rec, false);
+		node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
+		RB_CLEAR_NODE(pos);
+		/* Ensure __bpf_rbtree_add() sees the node as unlinked. */
+		smp_store_release(&node->owner, NULL);
+		__bpf_obj_drop_impl((char *)pos - field->graph_root.node_offset,
+				    field->graph_root.value_rec, false);
 	}
 }
 
-- 
2.50.1 (Apple Git-155)

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

[sashiko-bot]

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

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1751 bytes --]

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 9ca195104667..46e8eada463b 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -2307,22 +2307,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);
> +	}
>  	*root = RB_ROOT_CACHED;
>  	__bpf_spin_unlock_irqrestore(spin_lock);

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?

(from review discussion at
https://lore.kernel.org/bpf/20260601061503.EFD881F00898@smtp.kernel.org/)

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/26738658508

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

[Yonghong Song]

On 5/31/26 10:58 PM, Kaitao Cheng wrote:
> From: Kaitao Cheng <chengkaitao@kylinos.cn>
>
> bpf_rb_root_free() detaches the root by copying the current rb_root_cached
> and then replacing the live root with RB_ROOT_CACHED. It then walks the
> copied root and drops each object contained in the tree.
>
> This leaves the rb node state intact while dropping the object. If the
> object is refcounted and survives the drop, its bpf_rb_node_kern still
> contains an owner pointer to the freed root and stale rb tree linkage. If
> a later bpf_rb_root allocation reuses the same address, bpf_rbtree_remove()
> can incorrectly pass the owner check and call rb_erase_cached() on a node
> whose rb pointers belong to the old tree.
>
> Mirror the list draining behavior by marking nodes as busy while the root
> is being detached, then clear the rb node and release the owner before
> dropping the containing object. This makes surviving nodes unowned and
> safe to reject from remove or accept for a later add.
>
> Fixes: 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")
> Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>

Please use [PATCH bpf] tag so CI can test it. Do we need a selftest?

LGTM with a few nits below.

Acked-by: Yonghong Song <yonghong.song@linux.dev>

> ---
>   kernel/bpf/helpers.c | 18 +++++++++++++-----
>   1 file changed, 13 insertions(+), 5 deletions(-)
>
> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 9ca195104667..46e8eada463b 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -2307,22 +2307,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;

Move 'struct bpf_rb_node_kern *node;' and the below to the top function declaration.
This will make code simpler.

> +
> +		node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
> +		WRITE_ONCE(node->owner, BPF_PTR_POISON);
> +	}
>   	*root = RB_ROOT_CACHED;
>   	__bpf_spin_unlock_irqrestore(spin_lock);
>   
>   	bpf_rbtree_postorder_for_each_entry_safe(pos, n, &orig_root.rb_root) {
> -		obj = pos;
> -		obj -= field->graph_root.node_offset;

We can keep this two ...

> +		struct bpf_rb_node_kern *node;
>   
> -
> -		__bpf_obj_drop_impl(obj, field->graph_root.value_rec, false);
> +		node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
> +		RB_CLEAR_NODE(pos);
> +		/* Ensure __bpf_rbtree_add() sees the node as unlinked. */
> +		smp_store_release(&node->owner, NULL);
> +		__bpf_obj_drop_impl((char *)pos - field->graph_root.node_offset,
> +				    field->graph_root.value_rec, false);

and then __bpf_obj_drop_impl(...) will not change.

>   	}
>   }
>   

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

[Kaitao Cheng]

在 2026/6/1 14:15, 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.

The critical sections protected by the bpf_spin_lock are very small.
They only do simple pointer/value assignments and do not perform
any expensive operation, so I do not think they should introduce
noticeable latency by themselves.

> 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?

I am not entirely sure whether this needs to be changed. I would like
to hear others' opinions on this. If we do want to avoid calling
rb_first_postorder()/rb_next_postorder() here, the straightforward
fix would be to duplicate these two helpers with exactly the same
implementation but under different names, and use the renamed versions
locally. That feels somewhat redundant to me, though.

>>  	*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?

This looks like a more general pre-existing issue. I am not sure whether
we should fix it in this series, and would like to hear others' opinions.

If we do want to fix it here, maybe we need to distinguish map_free/delete
from in-place map_update. For map_free/delete, a concurrent bpf_rbtree_add()
after the tree is detached should fail and drop the node. For in-place
map_update, the root should still be reset so that it remains usable.

-- 
Thanks
Kaitao Cheng

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

[Kaitao Cheng]

在 2026/6/2 02:06, Yonghong Song 写道:
> 
> 
> On 5/31/26 10:58 PM, Kaitao Cheng wrote:
>> From: Kaitao Cheng <chengkaitao@kylinos.cn>
>>
>> bpf_rb_root_free() detaches the root by copying the current rb_root_cached
>> and then replacing the live root with RB_ROOT_CACHED. It then walks the
>> copied root and drops each object contained in the tree.
>>
>> This leaves the rb node state intact while dropping the object. If the
>> object is refcounted and survives the drop, its bpf_rb_node_kern still
>> contains an owner pointer to the freed root and stale rb tree linkage. If
>> a later bpf_rb_root allocation reuses the same address, bpf_rbtree_remove()
>> can incorrectly pass the owner check and call rb_erase_cached() on a node
>> whose rb pointers belong to the old tree.
>>
>> Mirror the list draining behavior by marking nodes as busy while the root
>> is being detached, then clear the rb node and release the owner before
>> dropping the containing object. This makes surviving nodes unowned and
>> safe to reject from remove or accept for a later add.
>>
>> Fixes: 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")
>> Signed-off-by: Kaitao Cheng <chengkaitao@kylinos.cn>
> 
> Please use [PATCH bpf] tag so CI can test it. Do we need a selftest?

The bug fixed by this patch has fairly strict reproduction conditions,
so it is difficult to find a stable reproducer.

I have addressed the other feedback. Thanks for your review.
please see v2 for details.
https://lore.kernel.org/all/20260605094143.5509-1-kaitao.cheng@linux.dev/

> LGTM with a few nits below.
> 
> Acked-by: Yonghong Song <yonghong.song@linux.dev>
> 
>> ---
>>   kernel/bpf/helpers.c | 18 +++++++++++++-----
>>   1 file changed, 13 insertions(+), 5 deletions(-)
>>
>> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
>> index 9ca195104667..46e8eada463b 100644
>> --- a/kernel/bpf/helpers.c
>> +++ b/kernel/bpf/helpers.c
>> @@ -2307,22 +2307,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;
> 
> Move 'struct bpf_rb_node_kern *node;' and the below to the top function declaration.
> This will make code simpler.
> 
>> +
>> +        node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
>> +        WRITE_ONCE(node->owner, BPF_PTR_POISON);
>> +    }
>>       *root = RB_ROOT_CACHED;
>>       __bpf_spin_unlock_irqrestore(spin_lock);
>>         bpf_rbtree_postorder_for_each_entry_safe(pos, n, &orig_root.rb_root) {
>> -        obj = pos;
>> -        obj -= field->graph_root.node_offset;
> 
> We can keep this two ...
> 
>> +        struct bpf_rb_node_kern *node;
>>   -
>> -        __bpf_obj_drop_impl(obj, field->graph_root.value_rec, false);
>> +        node = rb_entry(pos, struct bpf_rb_node_kern, rb_node);
>> +        RB_CLEAR_NODE(pos);
>> +        /* Ensure __bpf_rbtree_add() sees the node as unlinked. */
>> +        smp_store_release(&node->owner, NULL);
>> +        __bpf_obj_drop_impl((char *)pos - field->graph_root.node_offset,
>> +                    field->graph_root.value_rec, false);
> 
> and then __bpf_obj_drop_impl(...) will not change.
> 
>>       }
>>   }
>>   
> 

-- 
Thanks
Kaitao Cheng