Skip to contentSkip to conversation

bpf: Rewrite "rX <<= 32; rX >>= 32" into "wX = wX" to keep linked scalars

PATCH In review Yonghong Song 3 participants 5 messages Aug 21 – Aug 24

Subsystems (2)
lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH v2 1/1 bpf: Rewrite "rX <<= 32; rX >>= 32" into "wX = wX" to keep linked scalars

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.

---
 kernel/bpf/verifier.c | 48 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 47 insertions(+), 1 deletion(-)

Changelog:
v1 -> v2:
- v1: https://lore.kernel.org/bpf/[email protected]/
- Replace left/right unsigned 32bit ship with 32bit mov's. This is done before main verification.

kernel/bpf/verifier.c +47 -1
index 821b47ac75c5..e1de442801d9 100644
@@ -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;
Signature · 1 line
2.53.0-Meta
#1 lore raw
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…
Quoted 91 lines

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

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.

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

maintainer
#2 lore raw
In reply to Yonghong Song
Quoted 16 lines · 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]);
	}
Quoted 5 lines

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.

Quoted 14 lines

  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.

...

Quoted 20 lines
kernel/bpf/verifier.c +0 -0
index 821b47ac75c5..e1de442801d9 100644
@@ -15610,6 +15610,14 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
  	return 0;
  }

kernel/bpf/verifier.c +8 -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.
  */

kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 15893

Quoted 9 lines
kernel/bpf/verifier.c +5 -1
@@ -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/[email protected]/

Quoted 4 lines
kernel/bpf/verifier.c +1 -0
+					} else if (insn->off == 0) {
  						bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;


  if (is_src_reg_u32)

...

author reviewer
#3 lore raw
Quoted 17 lines · Eduard Zingerman
Quoted 16 lines · 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]);
	}
Quoted 8 lines
Quoted 5 lines

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.

Quoted 50 lines
Quoted 15 lines

  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.

...

Quoted 20 lines
kernel/bpf/verifier.c +8 -0
index 821b47ac75c5..e1de442801d9 100644
@@ -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.
   */

kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 15893

Quoted 9 lines
kernel/bpf/verifier.c +5 -1
@@ -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

Quoted 1 line

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.

Quoted 1 line

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.

Quoted 13 lines

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?

Quoted 6 lines

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.

Quoted 6 lines
Quoted 5 lines
kernel/bpf/verifier.c +1 -0
+					} else if (insn->off == 0) {
  						bool is_src_reg_u32 = get_reg_width(src_reg) <= 32;
 
  						if (is_src_reg_u32)

...

maintainer
#4 lore raw

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

...

Quoted 55 lines
Quoted 14 lines

kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 15893

Quoted 10 lines
kernel/bpf/verifier.c +5 -1
@@ -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

Quoted 1 line

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.

Quoted 7 lines

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

Quoted 1 line

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?

Quoted 8 lines
Quoted 8 lines

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);
Quoted 4 lines
Quoted 4 lines

?

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.