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

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

[Yonghong Song]

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 what "wX = wX" computes as well
and which is exactly the relation BPF_ADD_CONST32 describes. So rewrite
the pair into "wX = wX" and let the mov turn the 64-bit link into a
32-bit one, which makes the -mcpu=v2 sequence track like an alu32 one.

The rewrite has to keep the program length, so the second shift becomes
a second "wX = wX" rather than being removed. A "goto pc+0" nop looks
like the obvious filler, but it is a jump, and bpf_is_state_visited()
decides where to place a checkpoint based on how many jumps it has
seen. One extra jump per shift pair re-times that heuristic and moves
the checkpoints of an enclosing loop, which can lose state pruning.

For example, clear_global_array_list() in the no_alu32 flavour of the
linked_list selftest calls the always_inline clear_list(), three
256 iteration loops in a row. With the shift pair, we have

  processed 15384 insns (limit 1000000) max_states_per_insn 4 total_states 260 peak_states 125 mark_read 0

With a "goto pc+0" filler the checkpoint changes its location, we have

  BPF program is too large. Processed 1000001 insn
  processed 1000001 insns (limit 1000000) max_states_per_insn 4 total_states 19479 peak_states 148 mark_read 0

The duplicated mov keeps both the insn and the jump counts the same as
before the rewrite. It is idempotent, the second mov re-derives the
same bounds and finds the 32-bit link already in place.

With this, the llvm22 and llvm23 code verifies, R2 keeps its id across
the zero extension 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: (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)
  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 sequence is rewritten as well, the rewrite is not tied to
BPF_ADD_CONST, so both its insns 4 and 5 become "w1 = w1". R1 carries
no id there, so the mov takes the ordinary zero extension path and ends
up with the same bounds the shift pair produced, the program verifies
as before.

Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 kernel/bpf/verifier.c | 48 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 47 insertions(+), 1 deletion(-)

Changelog:
  v1 -> v2:
    - v1: https://lore.kernel.org/bpf/20260820013925.2515018-1-yonghong.song@linux.dev/
    - Replace left/right unsigned 32bit ship with 32bit mov's. This is done before
      main verification.

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;
+					} else if (insn->off == 0) {
 						bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;
 
 						if (is_src_reg_u32)
@@ -19183,6 +19196,36 @@ static int check_and_resolve_insns(struct bpf_verifier_env *env)
 	return 0;
 }
 
+static bool is_shift_by_32(const struct bpf_insn *insn, u8 op)
+{
+	return insn->code == (BPF_ALU64 | op | BPF_K) && insn->off == 0 && insn->imm == 32;
+}
+
+/* 'rX <<= 32; rX >>= 32' => 'wX = wX; wX = wX' */
+static void bpf_rewrite_zext_shifts(struct bpf_verifier_env *env)
+{
+	struct bpf_insn *insn = env->prog->insnsi;
+	int i;
+
+	for (i = 0; i < env->prog->len - 1; i++) {
+		if (!is_shift_by_32(&insn[i], BPF_LSH) ||
+		    !is_shift_by_32(&insn[i + 1], BPF_RSH) ||
+		    insn[i].dst_reg != insn[i + 1].dst_reg)
+			continue;
+		if (bpf_is_jmp_point(env, i + 1))
+			continue;
+		/*
+		 * The second mov is redundant, but a nop (goto pc+0) cannot
+		 * be used here. A 'goto pc+0' is a jump, and the extra jump
+		 * may change where checkpoints are placed, see
+		 * bpf_is_state_visited(). The second mov avoids that.
+		 */
+		insn[i] = BPF_MOV32_REG(insn[i].dst_reg, insn[i].dst_reg);
+		insn[i + 1] = insn[i];
+		i++;
+	}
+}
+
 /* drop refcnt of maps used by the rejected program */
 static void release_maps(struct bpf_verifier_env *env)
 {
@@ -21149,6 +21192,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	if (ret < 0)
 		goto skip_full_check;
 
+	/* Needs the jump point marks left by bpf_check_cfg(). */
+	bpf_rewrite_zext_shifts(env);
+
 	ret = bpf_compute_postorder(env);
 	if (ret < 0)
 		goto skip_full_check;
-- 
2.53.0-Meta

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 5268 bytes --]

> 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 what "wX = wX" computes as well
> and which is exactly the relation BPF_ADD_CONST32 describes. So rewrite
> the pair into "wX = wX" and let the mov turn the 64-bit link into a
> 32-bit one, which makes the -mcpu=v2 sequence track like an alu32 one.
>
> The rewrite has to keep the program length, so the second shift becomes
> a second "wX = wX" rather than being removed. A "goto pc+0" nop looks
> like the obvious filler, but it is a jump, and bpf_is_state_visited()
> decides where to place a checkpoint based on how many jumps it has
> seen. One extra jump per shift pair re-times that heuristic and moves
> the checkpoints of an enclosing loop, which can lose state pruning.
>
> For example, clear_global_array_list() in the no_alu32 flavour of the
> linked_list selftest calls the always_inline clear_list(), three
> 256 iteration loops in a row. With the shift pair, we have
>
>   processed 15384 insns (limit 1000000) max_states_per_insn 4 total_states 260 peak_states 125 mark_read 0
>
> With a "goto pc+0" filler the checkpoint changes its location, we have
>
>   BPF program is too large. Processed 1000001 insn
>   processed 1000001 insns (limit 1000000) max_states_per_insn 4 total_states 19479 peak_states 148 mark_read 0
>
> The duplicated mov keeps both the insn and the jump counts the same as
> before the rewrite. It is idempotent, the second mov re-derives the
> same bounds and finds the 32-bit link already in place.
>
> With this, the llvm22 and llvm23 code verifies, R2 keeps its id across
> the zero extension 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: (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)
>   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 sequence is rewritten as well, the rewrite is not tied to
> BPF_ADD_CONST, so both its insns 4 and 5 become "w1 = w1". R1 carries
> no id there, so the mov takes the ordinary zero extension path and ends
> up with the same bounds the shift pair produced, the program verifies
> as before.
>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>

This looks like a bug fix for the BPF_ADD_CONST linked register tracking
mechanism. The zero-extension shift pattern wasn't properly handling
registers with BPF_ADD_CONST relationships, causing the verifier to lose
track of register bounds and reject valid programs.

Should this include:

  Fixes: 98d7ca374ba4 ("bpf: Track delta between \"linked\" registers.")


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/32447591531

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

[Eduard Zingerman]

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.

>   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.
Also, could you please comment why the special case for `wA = wA` is necessary?
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/20260814231945.3884596-1-vineet.gupta@linux.dev/

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

...

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

[Yonghong Song]

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/20260814231945.3884596-1-vineet.gupta@linux.dev/

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

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

[Eduard Zingerman]

On Sat, 2026-08-22 at 09:47 -0700, Yonghong Song wrote:

...

> > > @@ -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.

I understand why you insert `wA = wA` twice, the question is about a
special case for `wA = wA` in check_alu_op(), why would you need
additional handling there specifically?

> > 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?

^^^
The above part is still relevant for the question.