Skip to contentSkip to conversation

bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension

PATCH In review Yonghong Song 3 participants 4 messages Aug 20

Subsystems (2)
lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH 1/1 bpf: Track linked scalars across a "rX <<= 32; rX >>= 32" zero extension

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.

---
 kernel/bpf/verifier.c | 50 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)
kernel/bpf/verifier.c +50 -0
index e421ea2b80c3..0fded097505e 100644
@@ -15584,6 +15584,50 @@ 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;
+}
+
+static bool is_shift32_insn(const struct bpf_insn *insn, u8 op)
+{
+	return insn->code == (BPF_ALU64 | op | BPF_K) && insn->off == 0 && insn->imm == 32;
+}
+
+/* Handle "rX <<= 32; rX >>= 32", which zero extends the lower 32 bits. */
+static bool is_zext_pair_lsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     const struct bpf_reg_state *dst_reg)
+{
+	struct bpf_insn *next;
+	int insn_idx = env->insn_idx;
+
+	if (!dst_reg->id || !is_shift32_insn(insn, BPF_LSH))
+		return false;
+	/* check_subprogs() guarantees a shift is never the last insn. */
+	next = &env->prog->insnsi[insn_idx + 1];
+	if (!is_shift32_insn(next, BPF_RSH) || next->dst_reg != insn->dst_reg)
+		return false;
+	/* Ensure the next insn has a single incoming edge. */
+	return !bpf_is_prune_point(env, insn_idx + 1);
+}
+
+static bool is_zext_pair_rsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     const struct bpf_reg_state *dst_reg)
+{
+	struct bpf_insn *prev;
+	int insn_idx = env->insn_idx;
+
+	if (!dst_reg->id || insn_idx == 0 || env->prev_insn_idx != insn_idx - 1)
+		return false;
+	if (!is_shift32_insn(insn, BPF_RSH))
+		return false;
+	prev = &env->prog->insnsi[insn_idx - 1];
+	return is_shift32_insn(prev, BPF_LSH) && prev->dst_reg == insn->dst_reg;
+}
+
 /* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max
  * and var_off.
  */
@@ -15694,6 +15738,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
 	 * alu32 ops will have zero-extended the result, making umax_value <= U32_MAX.
 	 */
 	u64 dst_umax = reg_umax(dst_reg);
+	bool base_fits_u32 = linked_base_fits_u32(dst_reg);
 
 	err = adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
 	if (err)
@@ -15743,6 +15788,11 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
 				dst_reg->id |= BPF_ADD_CONST64;
 			dst_reg->delta = off;
 		}
+	} else if (base_fits_u32 && is_zext_pair_lsh(env, insn, dst_reg)) {
+		/* Keep id and delta, the next insn completes the pair. */
+	} else if (is_zext_pair_rsh(env, insn, dst_reg)) {
+		if (dst_reg->id & BPF_ADD_CONST64)
+			dst_reg->id = (dst_reg->id & ~BPF_ADD_CONST64) | BPF_ADD_CONST32;
 	} else {
 		/*
 		 * Make sure ID is cleared otherwise dst_reg min/max could be
Signature · 1 line
2.53.0-Meta
#1 lore raw
Is the comment accurate? In is_zext_pair_lsh(), the check bpf_is_prune_point(env, insn_idx + 1) returns false when env->insn_aux_data[idx].prune_point is not set, but not every merge point gets that…
Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index e421ea2b80c3..0fded097505e 100644

[ ... ]

Quoted 22 lines
kernel/bpf/verifier.c +18 -0
@@ -15584,6 +15584,50 @@ 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;
+}
+
+static bool is_shift32_insn(const struct bpf_insn *insn, u8 op)
+{
+	return insn->code == (BPF_ALU64 | op | BPF_K) && insn->off == 0 && insn->imm == 32;
+}
+
+/* Handle "rX <<= 32; rX >>= 32", which zero extends the lower 32 bits. */
+static bool is_zext_pair_lsh(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     const struct bpf_reg_state *dst_reg)
+{
+	struct bpf_insn *next;

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 15614

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+	int insn_idx = env->insn_idx;
+
+	if (!dst_reg->id || !is_shift32_insn(insn, BPF_LSH))
+		return false;
+	/* check_subprogs() guarantees a shift is never the last insn. */
+	next = &env->prog->insnsi[insn_idx + 1];
+	if (!is_shift32_insn(next, BPF_RSH) || next->dst_reg != insn->dst_reg)
+		return false;
+	/* Ensure the next insn has a single incoming edge. */
+	return !bpf_is_prune_point(env, insn_idx + 1);
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Is the comment accurate? In is_zext_pair_lsh(), the check bpf_is_prune_point(env, insn_idx + 1) returns false when env->insn_aux_data[idx].prune_point is not set, but not every merge point gets that flag.

Looking at kernel/bpf/cfg.c, visit_gotox_insn() marks the gotox instruction itself as a prune point, but marks each jump-table target with mark_jmp_point() only, not mark_prune_point(). So an indirect-jump target instruction can have many incoming edges (one per jump-table entry plus a possible fall-through) while bpf_is_prune_point() returns false for it.

If such a target is the second shift of the pair, is_zext_pair_lsh() would still return true even though the instruction has multiple incoming edges.

The property actually being relied on appears to be "no verifier state is checkpointed at insn_idx + 1", which does follow from !bpf_is_prune_point(), since bpf_is_state_visited() in do_check() is itself guarded by bpf_is_prune_point(). On an edge that arrives at the second shift from somewhere other than the preceding first shift, is_zext_pair_rsh() would fail its "env->prev_insn_idx != insn_idx - 1" test and the id would be cleared as before.

Could the comment be reworded to state the actual invariant? For example:
"No state is checkpointed at insn_idx + 1, so the intermediate state between the two shifts can never be pruned against."

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 15615

Quoted 1 line
kernel/bpf/verifier.c +1 -0
+}

[ ... ]

---
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/32322608718

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

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

The llvm21 log is unchanged, R1 carries no id there so the new code does not apply to it.

---

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.

...

author reviewer
#3 lore raw
Quoted 80 lines · Eduard Zingerman
Quoted 79 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]);
	}

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

The llvm21 log is unchanged, R1 carries no id there so the new code does not apply to it.

---

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.

Quoted 2 lines

...