[PATCH bpf v1 1/8] bpf: Check ancestor frames for rbtree callbacks

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

bpf_rbtree_add() invokes its comparator while the caller holds the root
lock. The native insertion code retains raw parent and link pointers across
the callback, so the verifier prohibits unlocking, consuming tree nodes,
or changing RCU state from that callback.

in_rbtree_lock_required_cb() only checks the innermost verifier frame.
Static subprogram calls are permitted while holding a spin lock, and such a
call pushes a frame without in_callback_fn set. Consequently, all callback
restrictions disappear in the nested frame. The subprogram can unlock the
tree, remove and drop the node being compared, then relock. Native insertion
resumes with the stale parent pointer and links freed memory into the tree.

Walk all active frames for the rbtree callback instead. Benign static
subprograms remain permitted, while callback restrictions follow execution
into nested frames.

Fixes: a44b1334aadd ("bpf: Allow calling static subprogs while holding a bpf_spin_lock")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/verifier.c | 25 ++++++++++++++-----------
 1 file changed, 14 insertions(+), 11 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 32d31fa67036..26139fa09f12 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10235,9 +10235,10 @@ static void account_current_path(struct bpf_verifier_env *env)
 					frame ? state->frame[frame - 1] : NULL);
 }
 
-/* Are we currently verifying the callback for a rbtree helper that must
- * be called with lock held? If so, no need to complain about unreleased
- * lock
+/*
+ * Are we currently verifying the callback for an rbtree kfunc that must
+ * be called with a lock held, or one of that callback's subprogs? If so,
+ * no need to complain about an unreleased lock.
  */
 static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
 {
@@ -10245,17 +10246,19 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
 	struct bpf_insn *insn = env->prog->insnsi;
 	struct bpf_func_state *callee;
 	int kfunc_btf_id;
+	u32 frame;
 
-	if (!state->curframe)
-		return false;
-
-	callee = state->frame[state->curframe];
+	for (frame = state->curframe; frame; frame--) {
+		callee = state->frame[frame];
+		if (!callee->in_callback_fn)
+			continue;
 
-	if (!callee->in_callback_fn)
-		return false;
+		kfunc_btf_id = insn[callee->callsite].imm;
+		if (is_rbtree_lock_required_kfunc(kfunc_btf_id))
+			return true;
+	}
 
-	kfunc_btf_id = insn[callee->callsite].imm;
-	return is_rbtree_lock_required_kfunc(kfunc_btf_id);
+	return false;
 }
 
 static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
-- 
2.53.0