Re: [PATCH bpf-next v3 27/45] bpf: Track a pointer to one of a set of functions

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: unconditional R1-R5 split in do_check_insn() causes state explosion
--

commit 75a36349ee42f80ce6f3c17dd0dfc5718a853221
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Track a pointer to one of a set of functions

This commit tracks a pointer read from a function table as a single
register state representing a set of target functions (func_set) instead
of branching states at the load instruction. The function set is later
expanded into individual function targets when a callx instruction or a
helper/kfunc call requires a specific function.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 437a3fc03d0bf..41500f03b41be 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -12028,13 +12072,93 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
[ ... ]
> +/* The insn needs to know the function: go on with each function of the set. */
> +static int split_func_set(struct bpf_verifier_env *env, int regno)
> +{
> +	struct bpf_reg_state *reg = reg_state(env, regno);
> +	struct bpf_verifier_state *branch;
> +	struct bpf_func_set *set;
> +	u32 i;
> +
> +	if (reg->type != PTR_TO_FUNC || !reg->func_set)
> +		return 0;
> +	set = env->func_sets[reg->func_set - 1];
> +	reg->func_set = 0;
> +	for (i = 0; i < set->cnt; i++) {
> +		reg->subprogno = set->subprog[i];
> +		if (i == set->cnt - 1)
> +			break;
> +		branch = push_stack(env, env->insn_idx, env->insn_idx, false);
> +		if (IS_ERR(branch))
> +			return PTR_ERR(branch);
> +	}
> +	return 0;
> +}
[ ... ]
> @@ -20952,6 +21068,12 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
>  				return check_func_callx(env, insn, &env->insn_idx);
>  			if (insn->src_reg == BPF_PSEUDO_CALL)
>  				return check_func_call(env, insn, &env->insn_idx);
> +			/* a callback is one function */
> +			for (i = BPF_REG_1; i <= BPF_REG_5; i++) {
> +				err = split_func_set(env, i);
> +				if (err)
> +					return err;
> +			}
>  			if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL)
>  				return check_kfunc_call(env, insn, &env->insn_idx);
>  			return check_helper_call(env, insn, &env->insn_idx);

[Severity: Medium]
In do_check_insn(), split_func_set() is called unconditionally across all
registers BPF_REG_1 through BPF_REG_5 before every kfunc and helper call,
without checking whether the register is actually a callback argument or
even live at env->insn_idx.

Within a basic block, helper and kfunc calls that do not invoke synchronous
callbacks do not have a flow point set, so do_check_block() steps into the
call instruction without running bpf_flow_deliver() or
bpf_clean_verifier_state():

  do_check_block()
    do_check_insn()
      split_func_set()

If a caller-saved register in R1..R5 was loaded with a func_set of size N
earlier in the block and copied to a callee-saved register R6..R9 or
spilled to the stack before a helper or kfunc call that does not overwrite
that register, the dead register still holds PTR_TO_FUNC with reg->func_set
set when reaching the call.

In that case, split_func_set() clones env->cur_state N - 1 times onto
env->head at env->insn_idx. After env->cur_state finishes the call,
flow_drain() delivers those N - 1 states to env->insn_idx, allocating N - 1
flow_state objects, cleaning the dead register in flow_arrive(), and queuing
a duplicate pending state at env->insn_idx that re-verifies the call and the
rest of the basic block a second time.

Furthermore, if a second register in R1..R5 is marked live in
live_regs_before at the call while also holding a func_set, looping over
BPF_REG_1..BPF_REG_5 splits both registers and produces all N * N
combinations at env->insn_idx. For example, bpf_timer_set_callback_proto
sets arg3_type = ARG_PTR_TO_PROG_AUX, which causes bpf_get_call_summary() to
set arg_slot_cnt = 3 and compute_insn_live_regs() to mark R3 live in
live_regs_before even though the BPF program only passes R1 and R2. If a
program loads a callback from a table of N >= 33 functions into R3 and
copies r2 = r3 before calling bpf_timer_set_callback(), splitting both R2
and R3 creates N * N >= 1089 unjoinable states at env->insn_idx, exceeding
BPF_FLOW_MAX_STATES (1024) in flow_merge() and failing verification with
-E2BIG.

Should split_func_set() only be invoked for registers that correspond to
actual callback arguments (such as inside check_func_arg() /
process_kf_arg_ptr_to_func(), or gated on the call prototype and
live_regs_before)?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261106035111.3315285-1-alexei.starovoitov@gmail.com?part=27