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

On 8/20/26 9:57 AM, Eduard Zingerman wrote:
> 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.

For just left and right shift, probably `w2 = w2; nop;`.
But this approach is indeed simpler and easier to understand.
Will explore.

>
> ...