Re: [PATCH bpf-next v2 18/35] 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 1 potential issue(s) to consider:
- [High] bpf: missing head guard target edge in update_insn() stack liveness
--

commit 4a8572cac3df2db5693520d517c638b94138c076
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() earlier and teaches
bpf_compute_const_regs(), compute_subprog_args(), and
bpf_compute_live_registers() about the synthetic edge from a loop header to
bpf_head_guard_target() when a may_goto may be inserted at the loop header.

> 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]
Should the stack-slot liveness pass in update_insn() also union
FM_LIVE_BEFORE of bpf_head_guard_target(env, insn_idx) into new_before, just
as bpf_compute_live_registers() does here for registers?

In kernel/bpf/liveness.c, bpf_compute_subprog_arg_access() ->
analyze_subprog() -> update_instance() -> update_insn() still computes
FM_LIVE_BEFORE using only the static 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];
	}
	may_read = rel_mask(fm, rel, FM_MAY_READ);
	must_write = rel_mask(fm, rel, FM_MUST_WRITE);
	live_before = rel_mask(fm, rel, FM_LIVE_BEFORE);
    ...
	for (w = 0; w < fm->words; w++) {
		unsigned long new_before = (new_after[w] & ~must_write[w]) | may_read[w];
    ...
}

When a loop has guard_at_header set, bpf_insert_loop_guards() places may_goto
in front of the loop header insn_idx, jumping directly to
t = bpf_head_guard_target(env, insn_idx) before insn_idx or the loop body
executes.

If a stack slot is read at or after t (so FM_LIVE_BEFORE is set at t) and is
overwritten (FM_MUST_WRITE) on every normal path through the loop to t (or by
insn_idx itself), update_insn() clears its bit via ~must_write[w] and marks
the slot dead (FM_LIVE_BEFORE == 0) before the loop header insn_idx.

When a verifier state arrives at insn_idx during the main pass,
flow_arrive() -> bpf_clean_verifier_state() -> clean_verifier_state() ->
__clean_func_state() sees bpf_stack_slot_alive() == false and marks the slot
as STACK_POISON (and resets spilled_ptr to NOT_INIT):

kernel/bpf/states.c:__clean_func_state() {
    ...
	for (i = 0; i < bpf_stack_nr_slots(st); i++) {
		bool lo_live = bpf_stack_slot_alive(env, frame, i * 2);
		bool hi_live = bpf_stack_slot_alive(env, frame, i * 2 + 1);

		if (!hi_live || !lo_live) {
    ...
			if (!hi_live) {
    ...
				bpf_mark_reg_not_init(env, spill);
			}
			for (j = start; j < end; j++)
				bpf_stack_slot(st, i)->slot_type[j] = STACK_POISON;
		}
	}
}

When check_loop_guard() -> bpf_flow_guard_edge() then propagates that state
from insn_idx to t, the slot arrives at t as STACK_POISON while
FM_LIVE_BEFORE is true at t.

Wouldn't this cause valid stack reads after the loop exit to be rejected with
"slot poisoned by dead code elimination", or cause a spilled pointer erased
to STACK_POISON at the loop header to merge with a scalar/zero slot from a
normal loop exit into STACK_INVALID in join_slot()?

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