Re: [RFC PATCH bpf-next v1 09/11] bpf: Let the comparator of bpf_rbtree_add unwind

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Critical] bpf: clobbered R2 on bpf_rbtree_add() callback unwind causes UAF
- [High] bpf: __bpf_rbtree_add() leaves node->owner poisoned on comparator unwind
--

commit 55e1518aab2a62c50b8098afe20794d027a69689
Author: Kumar Kartikeya Dwivedi <memxor@gmail.com>

bpf: Let the comparator of bpf_rbtree_add unwind

This commit allows the comparator callback of bpf_rbtree_add() and
bpf_rbtree_add_impl() to unwind via unwind_exit. When the comparator
unwinds, the kfunc drops the uninserted node before leaving to the landing
pad, and the verifier invalidates non-owning references and releases the
caller's owning reference on revisit.

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 648abe1ba63ae..f8708b7181d72 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c

[ ... ]

> @@ -2784,7 +2788,8 @@ static int __bpf_rbtree_add(struct bpf_rb_root *root,
>  
>  	while (*link) {
>  		parent = *link;
> -		if (cb((uintptr_t)node, (uintptr_t)parent, 0, 0, 0)) {
> +		bpf_call_cb(cb, node, parent, 0, 0, 0, r0, unwound);
> +		if (r0) {
>  			link = &parent->rb_left;
>  		} else {
>  			link = &parent->rb_right;
> @@ -2796,6 +2801,15 @@ static int __bpf_rbtree_add(struct bpf_rb_root *root,
>  	rb_insert_color_cached(n, (struct rb_root_cached *)root, leftmost);
>  	WRITE_ONCE(node->owner, root);
>  	return 0;
> +
> +unwound:
> +	/*
> +	 * The comparator left with unwind_exit. The node is not in the tree, and
> +	 * the caller has let go of it: drop it, as the error path above does.
> +	 */
> +	__bpf_obj_drop_impl((void *)n - off, rec, false);
> +	bpf_unwind_leave();
> +	return r0;
>  }

[Severity: High]
Does the unwound path in __bpf_rbtree_add() leave node->owner poisoned with
BPF_PTR_POISON when the object survives __bpf_obj_drop_impl()?

At the start of __bpf_rbtree_add() in kernel/bpf/helpers.c, node->owner is
transitioned from NULL to BPF_PTR_POISON before the traversal loop:

	if (cmpxchg(&node->owner, NULL, BPF_PTR_POISON)) {
		/* Only called from BPF prog, no need to migrate_disable */
		__bpf_obj_drop_impl((void *)n - off, rec, false);
		return -EINVAL;
	}

When the comparator callback cb exits via unwind_exit during the while (*link)
loop, control jumps to unwound after cmpxchg() has already set node->owner to
BPF_PTR_POISON, and before WRITE_ONCE(node->owner, root) is reached.

If the object contains a bpf_refcount field and another active reference to it
exists (for example via bpf_refcount_acquire() before calling bpf_rbtree_add()
or inside the comparator before unwinding), __bpf_obj_drop_impl() decrements
the refcount and returns without freeing the object:

	if (rec && rec->refcount_off >= 0 &&
	    !refcount_dec_and_test((refcount_t *)(p + rec->refcount_off))) {
		return;
	}

Unlike bpf_rb_root_free(), which clears node->owner back to NULL before
dropping the reference:

	/* Ensure __bpf_rbtree_add() sees the node as unlinked. */
	smp_store_release(&node->owner, NULL);
	__bpf_obj_drop_impl(obj, field->graph_root.value_rec, false);

the unwound path in __bpf_rbtree_add() leaves node->owner set to
BPF_PTR_POISON on the surviving unlinked object, causing any subsequent
bpf_rbtree_add() or bpf_rbtree_add_impl() call on that object to fail the
cmpxchg() check with -EINVAL. Should node->owner be reset to NULL before
calling __bpf_obj_drop_impl() in the unwound path?

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index fd63ff36eb909..50c3d44c37e15 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -15738,7 +15738,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
>  		id = regs[BPF_REG_2].id;
>  		insn_aux->insert_off = regs[BPF_REG_2].var_off.value;
>  		insn_aux->kptr_struct_meta = btf_find_struct_meta(meta.arg_btf, meta.arg_btf_id);
> -		ref_convert_owning_non_owning(env, id);
> +		/*
> +		 * The comparator unwound: the node never went in, and the
> +		 * kfunc dropped it on its way to the pad. The comparator was
> +		 * handed the node too, and may have unwound with it in r0, so
> +		 * every non-owning reference goes. Otherwise the node is in
> +		 * the tree now.
> +		 */
> +		if (env->cur_state->unwound) {
> +			invalidate_non_owning_refs(env);
> +			err = release_reference(env, id);
> +			if (err)
> +				return err;
> +		} else {
> +			ref_convert_owning_non_owning(env, id);
> +		}
>  	}

[Severity: Critical]
Can an unwinding comparator callback with a two-register return type clobber
caller->regs[BPF_REG_2] in prepare_func_exit(), causing check_kfunc_call() to
release the wrong reference ID and leave a dangling owning pointer to the
dropped node?

During verifier setup, bpf_compute_subprog_ret_regs() sets ret_reg_pair = true
for any subprogram whose BTF return type is a 9-16 byte struct, and
btf_validate_return_type() allows static subprograms to return structs up to
16 bytes. Neither check_func_arg(), push_callback_call(), nor
check_cb_unwind() prevents the less callback passed to bpf_rbtree_add() or
bpf_rbtree_add_impl() from having ret_reg_pair == true.

When such a callback executes unwind_exit, prepare_func_exit() in
kernel/bpf/verifier.c computes nregs = 2 (where ret_regs[] = { BPF_REG_0,
BPF_REG_2 }) and copies both registers from the callee frame into the caller
frame before rewinding *insn_idx to callee->callsite:

	callee = state->frame[state->curframe];
	r0 = &callee->regs[BPF_REG_0];
	nregs = bpf_ret_reg_pair(env, callee->subprogno) ? 2 : 1;
	...
	if (callee->in_callback_fn && !unwinds) {
		...
	} else {
		for (i = 0; i < nregs; i++) {
			u32 regno = ret_regs[i];

			bpf_diag_mod_begin(env, &caller->regs[regno], &callee->regs[regno],
					   BPF_DIAG_MOD_WRITE);
			caller->regs[regno] = callee->regs[regno];
			bpf_diag_mod_end(env);
		}
	}

If the caller passed &n1->node (with id = n1_id) in BPF_REG_2 while keeping a
copy of n1 in a callee-saved register (R6-R9) or stack spill, and the
comparator callback acquires an owning reference to a second node n2 of the
same BTF type (for example via bpf_refcount_acquire() or
bpf_list_pop_front()), places &n2->node (with id = n2_id) into BPF_REG_2, and
executes unwind_exit:

1. prepare_func_exit() overwrites caller->regs[BPF_REG_2] with &n2->node
   (id = n2_id).

2. On the revisit of check_kfunc_call() at bpf_rbtree_add() with
   env->cur_state->unwound == true, check_func_args() succeeds because
   caller->regs[BPF_REG_2] holds a valid owning pointer of the expected
   node type, and release_reference(env, id) releases n2_id instead of n1_id.

3. At runtime, __bpf_rbtree_add() drops the caller's original node n1 via
   __bpf_obj_drop_impl(), while in the verifier state at the landing pad after
   unwind_goto, n1_id was never released and the caller's saved pointer to n1
   remains a valid owning PTR_TO_BTF_ID | MEM_ALLOC pointer to freed memory.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793147364.git.memxor@gmail.com?part=9