bpf: Clear rb node linkage when freeing bpf_rb_root
PATCH 1/1 bpf: Clear rb node linkage when freeing bpf_rb_root
From: Kaitao Cheng <[email protected]>
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.
--- kernel/bpf/helpers.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-)
kernel/bpf/helpers.c +13 -5
@@ -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); } }
Signature · 1 line
2.50.1 (Apple Git-155)
[email protected]
AI reviewThank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
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 <[email protected]>
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.
Quoted 11 lines
kernel/bpf/helpers.c +0
-1@@ -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 ));
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2310
Quoted 10 lines
kernel/bpf/helpers.c +6
-0BUILD_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?
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2323
Quoted 2 lines
kernel/bpf/helpers.c +0
-0*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?
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Quoted 46 lines · 在 2026/6/1 14:15, [email protected] 写道:
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 afterbpf_obj_free_fieldsare permanently leaked. --commit
867fefb5dd2755c5bd12c9f3bd37d5367c6793f3
Author: Kaitao Cheng <[email protected]>bpf: Clear rb node linkage when freeing
bpf_rb_rootThis commit modifies
bpf_rb_root_freeto 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.Quoted 11 lines
kernel/bpf/helpers.c +0
-1@@ -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 ));kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2310
Quoted 10 lines
kernel/bpf/helpers.c +6
-0BUILD_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?
Quoted 2 lines
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.
Quoted 3 lines
Additionally, since
rb_first_postorder()andrb_next_postorder()are exported and traceable, if an fentry/fexit BPF program is attached to them and attempts to acquire the samebpf_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.
Quoted 12 lines
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2323
Quoted 2 lines
kernel/bpf/helpers.c +0
-0*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.
Quoted 6 lines
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, butbpf_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.
Signature · 2 lines
Thanks Kaitao Cheng
[email protected]
AI reviewSince 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?
Quoted 13 lines
kernel/bpf/helpers.c +0
-1@@ -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 ));
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2323
Quoted 10 lines
kernel/bpf/helpers.c +6
-0__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/[email protected]/)
[ ... ]
---
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
Quoted 13 lines · Kaitao Cheng
From: Kaitao Cheng <[email protected]>
bpf_rb_root_free()detaches the root by copying the currentrb_root_cachedand then replacing the live root withRB_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_kernstill contains an owner pointer to the freed root and stale rb tree linkage. If a laterbpf_rb_rootallocation reuses the same address,bpf_rbtree_remove()can incorrectly pass the owner check and callrb_erase_cached()on a node whose rb pointers belong to the old tree.
Quoted 7 lines
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 <[email protected]>
Please use [PATCH bpf] tag so CI can test it. Do we need a selftest?
LGTM with a few nits below.
Quoted 11 lines
--- kernel/bpf/helpers.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-)kernel/bpf/helpers.c +0
-0@@ -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;
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2317
Quoted 10 lines
kernel/bpf/helpers.c +2
-1struct 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.
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2322
Quoted 10 lines
kernel/bpf/helpers.c +4
-2+ + 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 ...
kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2333
Quoted 10 lines
kernel/bpf/helpers.c +7
-2+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.
Quoted 3 lines
kernel/bpf/helpers.c +0
-0} }
Quoted 21 lines · Yonghong Song
Quoted 18 lines · Kaitao Cheng
From: Kaitao Cheng <[email protected]>
bpf_rb_root_free()detaches the root by copying the currentrb_root_cachedand then replacing the live root withRB_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_kernstill contains an owner pointer to the freed root and stale rb tree linkage. If a laterbpf_rb_rootallocation reuses the same address,bpf_rbtree_remove()can incorrectly pass the owner check and callrb_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.
Quoted 4 lines
Quoted 2 lines
Fixes 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")Signed-off-by Kaitao Cheng <[email protected]>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/[email protected]/
Quoted 55 lines
LGTM with a few nits below.
Acked-by Yonghong Song <[email protected]>Quoted 9 lines
---
kernel/bpf/helpers.c| 18 +++++++++++++-----1 file changed, 13 insertions(+), 5 deletions(-)kernel/bpf/helpers.c +0
-0kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2315
Quoted 10 lines
kernel/bpf/helpers.c +2
-1@@ -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.kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 2322
Quoted 9 lines
kernel/bpf/helpers.c +4
-2+ + 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 ...
Quoted 9 lines
kernel/bpf/helpers.c +1
-0+ 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.
Quoted 3 lines
}
}
Signature · 2 lines
Thanks Kaitao Cheng