[PATCH bpf-next v2] 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.

Signed-off-by: Yonghong Song <[email protected]>
---
 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.

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