From 088a5477a9bdb410169ff158a581bc2585db546c Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Oct 2026 03:47:53 -0700 Subject: bpf: Avoid widening registers that hinder exact stack-slot tracking For loops like this: int arr[10]; for (int i = 0; i < 10; i++) arr[i] = i; use(arr[i]); SCEV-based loop widening converts `i` from being enumerated 10 times as a constant value 0, 1, ..., 9 to being enumerated once as a range [0..9]. From the point of view of the main verification pass, this replaces constant-offset stack access with varying-offset stack access. The verifier tracks stack values accessed through varying offsets much less precisely than those accessed via constant offsets. For example, the read at use(arr[i]) would yield STACK_MISC. Precision might be lost for the following operations: - spills (BPF_ST/STX to the stack): stored value can no longer be recovered when read back, e.g. after the loop; - fills (BPF_LDX from the stack): a varying-offset read of a spilled pointer yields a SCALAR_VALUE, so the pointer is lost. - calls that construct objects on the stack (dynptr, iter, irq_flag, res_spin_lock): the stack argument is required to have a constant offset. This commit adds logic to avoid widening registers used by such instructions: - During the main SCEV computation stage, collect_store_base_regs(): - inspects instructions accessing the stack (spill, fill, call to a function listed in bpf_needs_fixed_stack_off), and - if there is a SCEV expression for a stack base address register, records which registers the expression depends on in the bpf_loop->store_base_reg field. - `store_base_reg`s accumulated for nested loops are propagated to outer loops as well. - During the loop-widening stage, bpf_compute_loop_iters() refuses to widen a loop when some of the registers the loop changes appear in store_base_regs. Signed-off-by: Eduard Zingerman Signed-off-by: Alexei Starovoitov Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-35-bcba9bc53ac9@gmail.com --- include/linux/bpf_verifier.h | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'include/linux') diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index d760d2283ac5..308e779c3f74 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -708,6 +708,9 @@ struct bpf_loop_exit { int to; /* instruction outside the loop */ }; +/* SCEV/widening register space: r0..r10 plus every stack slot of a frame. */ +#define BPF_SCEV_REGS_NUM (MAX_BPF_REG + MAX_BPF_STACK_SLOTS) + struct bpf_loop { struct bpf_backedge backedges[MAX_BACKEDGES]; /* edges exiting from this loop, includes edges from nested loops */ @@ -717,6 +720,12 @@ struct bpf_loop { bool irreducible; bool backedges_overflow; bool exits_overflow; + /* + * Loop-entry registers used to compute stack addresses for loads, + * stores and calls requiring fixed stack offsets, in this and nested + * loops. + */ + unsigned long store_base_regs[BITS_TO_LONGS(BPF_SCEV_REGS_NUM)]; }; struct bpf_insn_aux_data { @@ -1876,6 +1885,7 @@ int bpf_stack_liveness_init(struct bpf_verifier_env *env); void bpf_stack_liveness_free(struct bpf_verifier_env *env); int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st); const unsigned long *bpf_may_write_mask(struct bpf_verifier_env *env, u32 insn_idx); +bool bpf_needs_fixed_stack_off(struct bpf_verifier_env *env, int insn_idx); bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 spi); int bpf_compute_live_registers(struct bpf_verifier_env *env); -- cgit v1.2.3