Re: [PATCH bpf-next v3 18/45] 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 issue(s) 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 dc67a790eecafbb6bb6ef2d65c1ca1f5bfcd6434
Author: Alexei Starovoitov <ast@kernel.org>

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

This commit places loop guards right after loop discovery so pre-passes over
the control flow graph account for may_goto edges added at loop headers, and
extends bpf_edge_leaves_loop() to propagate constants when identifying loop
latches 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]
As reported by Sashiko on v2 [1], bpf_compute_live_registers() unions
state[t].in into new_in for t = bpf_head_guard_target(env, insn_idx), and
compute_subprog_args() joins the forward pointer and spill state from the
loop header into t, but does update_insn() in kernel/bpf/liveness.c also need
to union FM_LIVE_BEFORE of t into new_before for stack slot liveness?

In bpf_compute_subprog_arg_access() -> analyze_subprog() ->
update_instance() -> update_insn(), backward stack liveness only inspects
normal CFG successors:

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 in the current or caller frame is initialized before the
loop, overwritten (FM_MUST_WRITE) on every normal CFG path through the loop
to the exit t (or by the loop header instruction insn_idx itself), and then
read at or after t, update_insn() clears its liveness bit via ~must_write[w]
and leaves FM_LIVE_BEFORE as 0 at the loop header insn_idx.

When a verifier state reaches insn_idx during the main pass,
bpf_clean_verifier_state() -> clean_verifier_state() -> __clean_func_state()
sees bpf_stack_slot_alive() as false, resets spilled_ptr to NOT_INIT, and
marks the slot as STACK_POISON before the state is sent along the header
may_goto edge to t. Can that cause valid stack reads at or after t to be
rejected, or cause __clean_func_state() and join_slot() at t to mishandle
spilled pointers or uninitialized stack slots that were prematurely poisoned
at the loop header?

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 8c89bf67a8424..5af42d2dcab94 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -25219,6 +25219,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;

[Severity: High]
When bpf_flow_place_guards() returns a positive value and bpf_check()
re-runs bpf_compute_const_regs(), what happens to conditional jumps at or
after a head-guard target that were already rewritten in-place by
bpf_prune_dead_branches() earlier in bpf_check()?

Earlier in bpf_check(), the first bpf_compute_const_regs() pass and
bpf_prune_dead_branches() run before bpf_compute_loops() and
bpf_flow_place_guards():

kernel/bpf/verifier.c:bpf_check() {
	...
	ret = bpf_compute_const_regs(env);
	if (ret < 0)
		goto skip_full_check;

	ret = bpf_prune_dead_branches(env);
	if (ret < 0)
		goto skip_full_check;
	...
}

At that point aux[h].guard_at_header is not yet set. If a register (or a
read-only map load derived from it, such as r7 == &ro on normal exits versus
r7 == &rw at the loop header) resolves to a constant at the exit target t in
the first bpf_compute_const_regs() pass, bpf_prune_dead_branches()
permanently rewrites any conditional jump testing that constant at or after t
into BPF_JMP_A(taken ? insn->off : 0) and recomputes the CFG postorder.

Re-running bpf_compute_const_regs() after bpf_flow_place_guards() clears
aux->const_reg_mask at t, but won't the in-place BPF_JMP_A instruction
rewrites in env->prog->insnsi remain in effect when a state jumps from the
loop header to t via may_goto?

[1] https://lore.kernel.org/r/20261105204513.2230344-19-alexei.starovoitov@gmail.com

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