Re: [PATCH bpf-next v3 09/12] bpf: Track low-32 scalar equality across narrowing stack fills

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2026-10-20 at 09:19 -0700, Vineet Gupta wrote:
> A 32-bit fill from a wider spilled scalar has the same shape as a 32-bit
> mov from a wider source, and the relation was dropped rather than
> recorded:
> 
>   r6 = ...                  /* full 64-bit unknown */
>   *(u64 *)(r10 - 8) = r6;   /* slot linked to r6 */
>   r2 = *(u32 *)(r10 - 8);   /* narrowing fill */
>   if w6 != 0 goto ...       /* not taken: r6's low 32 bits are 0 */
>   if r2 == 0 goto ...       /* not deduced today */
> 
> Record a low-32 link as the mov arm does. Stack slots are already
> first-class members of an ->id set, so sync_linked_regs() and the
> reconstruction helpers apply unchanged. A fill narrower than 32 bits has
> no expressible relation and still drops it.
> 
> Which extension rebuilds the high half depends on the load, so
> check_stack_read() takes is_ldsx and sets BPF_REG_LINK_SEXT where that
> is known. check_mem_access() then keeps a sign-extending link across a
> 4-byte sign-extending load only: BPF_REG_LINK_SEXT means (s32)(base +
> delta) specifically, so an 8- or 16-bit ldsx is a relation the kind
> cannot express, the same way the ALU arm's subreg_link is gated on
> (insn->off >> 3) == 4.
> 
> Costs. A bisect lands one clang regression here -- big_alloc2 2956 -> 3095
> insns, 157 -> 165 states -- but it is not this patch alone: it takes both
> this and the preceding reverse-direction patch, and neither moves
> big_alloc2 by itself. The external corpus does move for this patch alone,
> no verdict changes, six programs verifying in more instructions:
> 
>   +1812    2470 ->  4282  test_file_open    bpfjailer-lib-tests open
>   +1765   59556 -> 61321  twfw_connect4     tupperware-agent twfw_sock
>   +1765   59556 -> 61321  twfw_sendmsg4     same object
>    +752    5874 ->  6626  layered_enqueue   scx_layered 1.0.11.1
>    +252    2512 ->  2764  bpfj_exec_execve  exec_enforce
>    +252    2512 ->  2764  bpfj_exec_execveat  same object
> 
> +6598 over 25.2M, or +0.026%, and +218 states. The shape is the familiar
> one: a more precise recorded state has a smaller equivalence class and
> prunes against fewer predecessors.
> 
> Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
> ---

Please de-claude the comments.

...

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c

...

> @@ -4258,22 +4259,52 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
>  
>  			if (size <= spill_size &&
>  			    bpf_stack_narrow_access_ok(off, size, spill_size)) {
> +				bool narrowing = get_reg_width(reg) > size * BITS_PER_BYTE;
> +				/*
> +				 * A narrowing fill keeps only the slot's low 32 bits,
> +				 * so record a low-32 link rather than dropping the
> +				 * relation, as a 32-bit mov from a wide source does.
> +				 * Which link kind depends on how the load fills the high
> +				 * half, hence is_ldsx.
> +				 */
> +				bool subreg_link = narrowing && size == 4;
> +
>  				if (dst_regno < 0)
>  					return 0;
>  
> -				if (env->bpf_capable && size == 4 && spill_size == 4 &&
> -				    get_reg_width(reg) <= 32)
> +				if (env->bpf_capable && size == 4 &&
> +				    (subreg_link || (spill_size == 4 && !narrowing)))

This check can be simplified to 'env->bpf_capable && size == 4'.

>  					/* Ensure stack slot has an ID to build a relation
>  					 * with the destination register on fill.
>  					 */
>  					assign_scalar_id_before_mov(env, reg);

...

> @@ -7392,13 +7423,20 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b
>  			 * Sign-extension can change the register value relative
>  			 * to a scalar it is linked with by id (e.g. a zero-
>  			 * extending fill of the same spilled stack slot), thus
> -			 * drop the shared id in that case.
> +			 * drop the shared id in that case. Only a 4-byte
> +			 * BPF_REG_LINK_SEXT link survives: it says the high
> +			 * half is this very sign-extension. BPF_REG_LINK_ZEXT
> +			 * says the opposite and would be a lie about the value
> +			 * just produced, and an 8- or 16-bit sign extension is
> +			 * a relation BPF_REG_LINK_SEXT cannot express at all --
> +			 * it means (s32)(base + delta) specifically.
>  			 */
>  			bool no_sext = reg_umax(&regs[value_regno]) <
>  					(1ULL << (size * BITS_PER_BYTE - 1));
>  
>  			coerce_reg_to_size_sx(&regs[value_regno], size);
> -			if (!no_sext)
> +			if (!no_sext &&
> +			    !(size == 4 && regs[value_regno].link_kind == BPF_REG_LINK_SEXT))

Please make this:

  bool sext = reg_umax(&regs[value_regno]) >= (1ULL << (size * BITS_PER_BYTE - 1));
  bool sext32_link = ...;

  if (sext && !sext32_link)
    bpf_clear_scalar_id(&regs[value_regno]);

=> no giant comment necessary.

>  				bpf_clear_scalar_id(&regs[value_regno]);
>  		}
>  	}