Skip to contentSkip to conversation

bpf: Clear rb node linkage when freeing bpf_rb_root

PATCH Superseded Kaitao Cheng 4 participants 6 messages Jun 1 – Jun 5 BPF

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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.

Fixes 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")
---
 kernel/bpf/helpers.c | 18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)
kernel/bpf/helpers.c +13 -5
index 9ca195104667..46e8eada463b 100644
@@ -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)
#1 lore raw
Thank 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
index b5314c9fed3cf..c7f26336984f0 100644
@@ -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 -0
 	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?

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
#2 lore raw
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 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
index b5314c9fed3cf..c7f26336984f0 100644
@@ -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 -0
 	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?

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() 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.

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, 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.

Signature · 2 lines
Thanks
Kaitao Cheng
#3 lore raw
In reply to Kaitao Cheng
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 13 lines
kernel/bpf/helpers.c +0 -1
index 9ca195104667..46e8eada463b 100644
@@ -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

reviewer Acked-by on v1 1/1
#4 lore raw
In reply to Kaitao Cheng
Quoted 13 lines · Kaitao Cheng

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.

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")

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
index 9ca195104667..46e8eada463b 100644
@@ -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 -1
  	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 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
  	}
  }
 
#5 lore raw
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 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.

Quoted 4 lines
Quoted 2 lines
Fixes 9c395c1b99bd ("bpf: Add basic bpf_rb_{root,node} support")

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.

Quoted 9 lines

---
  kernel/bpf/helpers.c | 18 +++++++++++++-----

  1 file changed, 13 insertions(+), 5 deletions(-)
kernel/bpf/helpers.c +0 -0
index 9ca195104667..46e8eada463b 100644

kernel/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