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

[Yonghong Song <yonghong.song@linux.dev>]

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 <yonghong.song@linux.dev>
---
 kernel/bpf/verifier.c | 50 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e421ea2b80c3..0fded097505e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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
-- 
2.53.0-Meta