Re: [PATCH bpf-next] bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension

On Wed, 2026-08-19 at 18:39 -0700, Yonghong Song wrote:
> For the following test in
> tools/testing/selftests/bpf/progs/verifier_linked_scalars.c:
> 
> 	void alu32_negative_offset(void)
> 	{
> 		volatile char path[5];
> 		volatile int offset = bpf_get_prandom_u32();
> 		int off = offset;
> 
> 		if (off >= 5 && off < 10)
> 			path[off - 5] = '.';
> 
> 		/* So compiler doesn't say: error: variable 'path' set but not used */
> 		__sink(path[0]);
> 	}
> 
> Without alu32 (-mcpu=v2), the test
> verifier_linked_scalars/alu32_negative_offset will fail with llvm22 and
> llvm23 like below.
> 
>   3: (bf) r2 = r1               ; R1=scalar(id=1,...) R2=scalar(id=1,...)
>   4: (07) r2 += -5              ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
>   5: (67) r2 <<= 32             ; R2=scalar(smax=0x7fffffff00000000,...)
>   6: (77) r2 >>= 32             ; R2=scalar(smin=0,umax=0xffffffff,...)
>   7: (25) if r2 > 0x4 goto pc+5 ; R2=scalar(smin=0,smax=umax=4,...)
>   8: (bf) r2 = r10
>   9: (07) r2 += -5
>  10: (0f) r2 += r1              ; R1=scalar(id=1,smin=0,umax=0xffffffff)
>                                 ; R2=fp(smin=-5,smax=0xfffffffa)
>  11: (b7) r1 = 46               ; R1=46
>  12: (73) *(u8 *)(r2 -5) = r1
>  invalid unbounded variable-offset write to stack R2
> 
> R1 is never narrowed down, so the address stays unbounded and the store
> is rejected.
> 
> The test is okay for llvm21 with -mcpu=v2, see below:
> 
>   3: (07) r1 += -5              ; R1=scalar(smin=-5,smax=0xfffffffa)
>   4: (67) r1 <<= 32             ; R1=scalar(smax=0x7fffffff00000000,...)
>   5: (77) r1 >>= 32             ; R1=scalar(smin=0,umax=0xffffffff,...)
>   6: (25) if r1 > 0x4 goto pc+5 ; R1=scalar(smin=0,smax=umax=4,...)
>   7: (bf) r2 = r10
>   8: (07) r2 += -5
>   9: (0f) r2 += r1              ; R2=fp(smin=-5,smax=-1)
>  10: (b7) r1 = 46               ; R1=46
>  11: (73) *(u8 *)(r2 +0) = r1   ; fp-8=ppppm???
> 
> To fix the test issue with llvm22 and llvm23, note that the shift pair
> computes zext32(base + delta), which is exactly the relation
> BPF_ADD_CONST32 describes. So keep the link alive across the first
> shift and turn it from a 64-bit into a 32-bit one at the second, which
> makes the -mcpu=v2 sequence track like an alu32 one.
> 
> Two conditions guard this. First, a 32-bit link requires the linked
> value to fit into u32, because sync_linked_regs() zero extends the
> bounds it propagates through such a link. linked_base_fits_u32() checks
> that on the register state before the shift, mirroring the dst_umax
> check the alu32 add path already does. Second, in between the two
> shifts the register does not hold the value its id and delta describe,
> so the second shift must have a single incoming edge, otherwise the
> intermediate state could be checkpointed and another path pruned
> against it.
> 
> With this, the llvm22 and llvm23 code verifies, R2 keeps its id through
> both shifts and the jump narrows down R1:
> 
>   3: (bf) r2 = r1               ; R1=scalar(id=1,...) R2=scalar(id=1,...)
>   4: (07) r2 += -5              ; R2=scalar(id=1-5,smin=-5,smax=0xfffffffa)
>   5: (67) r2 <<= 32             ; R2=scalar(id=1-5,smax=0x7fffffff00000000)
>   6: (77) r2 >>= 32             ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
>   7: (25) if r2 > 0x4 goto pc+5 ; R1=scalar(id=1,smin=5,smax=9,...)
>                                 ; R2=scalar(id=1-5,smin=0,smax=4,...)
>   8: (bf) r2 = r10
>   9: (07) r2 += -5
>  10: (0f) r2 += r1              ; R2=fp(smin=0,smax=4)
>  11: (b7) r1 = 46               ; R1=46
>  12: (73) *(u8 *)(r2 -5) = r1   ; fp-8=ppppm???
> 
> The llvm21 log is unchanged, R1 carries no id there so the new code
> does not apply to it.
> 
> Signed-off-by: Yonghong Song <[email protected]>
> ---

I think this is too tricky. A simpler thing is to rewrite the incoming
program as `w2 = w1; nop;` in place of two shifts. The CFG check would
still be necessary, though.

...