Re: [PATCH bpf-next v4 18/46] bpf: Tell the passes over the graph where an added may_goto goes

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential
issues to consider:
- [High] bpf: missing head guard target edge in update_insn() stack
  liveness
- [High] bpf: bpf_prune_dead_branches() folds jumps before head guards
  are placed
--

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

bpf: Tell the passes over the graph where an added may_goto goes

This commit runs bpf_flow_place_guards() right after loop detection so
constant folding, subprog argument tracking, and register liveness
account for synthetic may_goto edges from loop headers, and adds
backward condition tracking in bpf_compute_leave_conds() to identify
loop exits controlled by flags.

> diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
> index 525c0faff1a66..6a2ee407412b8 100644
> --- a/kernel/bpf/liveness.c
> +++ b/kernel/bpf/liveness.c
[ ... ]
> @@ -2780,6 +2796,7 @@ int bpf_compute_live_registers(struct bpf_verifier_env *env)
>  			u32 new_out = 0;
>  			u32 new_in = 0;
>  			u32 use;
> +			int t;
>  
>  			succ = bpf_insn_successors(env, insn_idx);
>  			for (int s = 0; s < succ->cnt; ++s)
> @@ -2794,6 +2811,10 @@ int bpf_compute_live_registers(struct bpf_verifier_env *env)
>  				use |= state[insn_idx + insns[insn_idx].imm + 1].in &
>  				       mask_widen(GENMASK(BPF_REG_5, BPF_REG_1));
>  			new_in = (new_out & ~live->def) | use;
> +			/* may_goto that is added at the head of a loop goes there */
> +			t = bpf_head_guard_target(env, insn_idx);
> +			if (t >= 0)
> +				new_in |= state[t].in;
>  			if (new_out != live->out || new_in != live->in) {
>  				live->in = new_in;
>  				live->out = new_out;

[Severity: High]
Does update_insn() need the same bpf_head_guard_target() edge for
backward stack-slot liveness (FM_LIVE_BEFORE)?

compute_subprog_args() now propagates stack pointers and spills across
bpf_head_guard_target(), and bpf_compute_live_registers() unions
state[t].in into new_in at the loop header, but update_insn() still
computes FM_LIVE_BEFORE only from normal CFG successors minus
must_write:

kernel/bpf/liveness.c:update_insn() {
	...
	for (s = 0; s < succ->cnt; ++s) {
		unsigned long *succ_live;

		succ_live = rel_mask(fm, relative_idx(instance, succ->items[s]), FM_LIVE_BEFORE);
		for (w = 0; w < fm->words; w++)
			new_after[w] |= succ_live[w];
	}
	...
	for (w = 0; w < fm->words; w++) {
		unsigned long new_before = (new_after[w] & ~must_write[w]) | may_read[w];
}

If a stack slot is initialized before the loop header, overwritten on
every normal path through the loop to the exit target t, and read at or
after t, FM_LIVE_BEFORE is cleared at the loop header.  When a state
arrives at the header in flow_arrive(), __clean_func_state() sees
bpf_stack_slot_alive() == false, clears spilled_ptr to NOT_INIT, and
marks the slot STACK_POISON before check_loop_guard() delivers the state
along the head-guard edge to t.  Reads of that slot after t then fail
verification as reading a poisoned slot, or if the slot held a spilled
pointer before the header and a scalar on normal loop exits, join_slot()
at t can merge the poisoned slot with the scalar into STACK_INVALID when
allow_uninit_stack is set, allowing the spilled pointer bytes on the
may_goto path to be read as a scalar.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5faea922699af..62a58f38f4e22 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -25268,6 +25268,21 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
>  	if (ret < 0)
>  		goto skip_full_check;
>  
> +	/*
> +	 * It took the constants to remove dead branches and find the loops. Now it's known
> +	 * which edges the verifier may add, see bpf_head_guard_target(). What follows
> +	 * believes the constants.
> +	 */
> +	ret = bpf_flow_place_guards(env);
> +	if (ret > 0)
> +		ret = bpf_compute_const_regs(env);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
> +	ret = bpf_find_latches(env, true);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
>  	ret = bpf_compute_live_registers(env);
>  	if (ret < 0)
>  		goto skip_full_check;

[Severity: High]
Can re-running bpf_compute_const_regs() after bpf_flow_place_guards()
leave behind conditional jumps that bpf_prune_dead_branches() already
rewrote into unconditional jumps using constants that only hold on
normal loop exits?

Before bpf_compute_loops() and bpf_flow_place_guards() run, the first
bpf_compute_const_regs() pass has no head-guard edges, so a register (or
a read-only map load through it, as in the r7 == &ro vs &rw case from
the commit message) that is constant on all normal exits to t is marked
constant at and after t.  bpf_prune_dead_branches() then permanently
overwrites conditional jumps testing that register at or after t in
env->prog->insnsi with BPF_JMP_A and recomputes postorder.  Re-running
bpf_compute_const_regs() after bpf_flow_place_guards() clears
const_reg_mask at t, but the in-place BPF_JMP_A rewrites remain in the
program, so a state taking the header may_goto to t will unconditionally
follow the branch decided for normal exits.

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