Re: [PATCH bpf-next v2] bpf: Rewrite "rX <<= 32; rX >>= 32" into "wX = wX" to keep linked scalars

On 8/21/26 10:36 AM, Eduard Zingerman wrote:
> On Thu, 2026-08-20 at 21:28 -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,...)
> Does r1 fit into 32-bit range at this point?
> I assume it does, otherwise it won't be possible to infer information
> about r1 range through zero extended r2.

Yes, r1 is in 32-bit range.

>
>>    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.
> ...
>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 821b47ac75c5..e1de442801d9 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -15610,6 +15610,14 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>   	return 0;
>>   }
>>   
>> +static bool linked_base_fits_u32(const struct bpf_reg_state *reg)
>> +{
>> +	if (reg->id & BPF_ADD_CONST32)
>> +		return true;
>> +	return reg_smin(reg) >= (s64)reg->delta &&
>> +	       reg_smax(reg) <= (s64)U32_MAX + (s64)reg->delta;
>> +}
>> +
>>   /* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max
>>    * and var_off.
>>    */
>> @@ -15878,7 +15886,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>>   						insn->src_reg);
>>   					return -EACCES;
>>   				} else if (src_reg->type == SCALAR_VALUE) {
>> -					if (insn->off == 0) {
>> +					if (insn->off == 0 && insn->src_reg == insn->dst_reg &&
>> +					    (dst_reg->id & BPF_ADD_CONST) &&
>> +					    linked_base_fits_u32(dst_reg)) {
>> +						dst_reg->id = (dst_reg->id & ~BPF_ADD_CONST64) |
>> +							      BPF_ADD_CONST32;
> This commit consists of two parts:
> - a special case for wA = wA assignment
> - a rewrite for `rA <<= 32; rA >>= 32;` pair
>
> Could you please split it in two with separate selftest for each.

Let me explain a little bit more.

For these four insns

   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,...)

Eventually, the above insns will be converted to

   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: (bc) w2 = w2               ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
   6: (bc) w2 = w2               ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)

insn 5 and 6 are the ones to be changed.

Here:

   5: (67) r2 <<= 32             ; R2=scalar(smax=0x7fffffff00000000,...)
   6: (77) r2 >>= 32             ; R2=scalar(smin=0,umax=0xffffffff,...)
converted to
   5: (bc) w2 = w2               ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)

This insn
   6: (bc) w2 = w2               ; R2=scalar(id=1-5,smin=0,umax=0xffffffff)
is not really necessary. I put it here to maintain existing control flow graph.
Previously for insn 6, I used "goto pc+0" which will be removed later.
But "goto pc+0" has some impact on verification as it added yet another jump.
See bpf_is_state_visited():

         if (env->jmps_processed - env->prev_jmps_processed >= 2 &&
             env->insn_processed - env->prev_insn_processed >= 8)
                 add_new_state = true;

Here "goto pc+0" may impact for some programs. I didn't investigate this
in detail but probably I should investigate and fix the root cause.

Alternatively, we can rebuild the control flow graph by removing insn 6.
I am just not sure whether this is worthwhile or not.

> Also, could you please comment why the special case for `wA = wA` is necessary?

The second wA = wA is not needed. We can remove it and rebuild the control flow
for it, just not sure whether this is worthwhile or not. Probably yes.

> Is it because assign_scalar_id_before_mov() destroys the link:
>
>    static void assign_scalar_id_before_mov(struct bpf_verifier_env *env,
> 					  struct bpf_reg_state *src_reg)
> 	...
> 	if (src_reg->id & BPF_ADD_CONST)
> 		clear_scalar_id(src_reg);
>
> ?
>
> If that's the only reason, is it possible to extend existing wA = wB
> logic instead of adding a special case?
>
> Also note that this overlaps with Vineet's series [1].
> Representing zero extension as a combination of BPF_ADD_CONST32 and
> delta == 0 is a valid alternative for one of the patches there,
> but it also handles the value reconstruction on sync.
>
> [1] https://lore.kernel.org/bpf/[email protected]/

Thanks for the link. I see there are some change for BPF_ADD_CONST32.
I will wait after the above patch is settled.

>
>> +					} else if (insn->off == 0) {
>>   						bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;
>>   
>>   						if (is_src_reg_u32)
> ...