[PATCH bpf-next v3 01/12] bpf: Keep the 32-bit range across a sign extension that cannot change it

[Vineet Gupta <vineet.gupta@linux.dev>]

This patch addresses the verifier deficiency where it would throw away
a good range whenever that range crossed zero.

| 1: (54) w0 &= 63      ; R0=scalar(smin32=0,smax32=63,...)
| 2: (14) w0 -= 63      ; R0=scalar(smin32=-63,smax32=0,...)
| 3: (bc) w0 = (s8)w0   ; R0=scalar(smin32=-128,smax32=127,...)
| 4: (c6) if w0 s< 0xffffffc1 goto pc+2
| ...
| 7: (34) w0 /= 0
| div by zero

[-63, 0] already fits an s8, so insn 3 cannot change any value in it, yet
the range comes out widened to [-128, 127]. The guard at insn 4 then
cannot be resolved and the div becomes reachable.

The issue is the following check in coerce_subreg_to_size_sx()

	top_smax_value = ((u32)reg_s32_max(reg) >> num_bits) << num_bits;
	top_smin_value = ((u32)reg_s32_min(reg) >> num_bits) << num_bits;

	if (top_smax_value != top_smin_value)
		goto out;

which doesn't fire when the range includes zero, since the top bits
differ. e.g. for [-63, 0]:

    smin32 = -63: high bits all ones
    smax32 =   0: high bits all zero

The cheap noop test above it does not catch this either -- it only looks
at reg_umax(), which a negative smin makes huge.

The 64-bit twin, coerce_reg_to_size_sx(), had the same gap and was given
an equivalent early return by commit 0892ef2a7ef3 ("bpf: Representation
for intervals with steps"). This patch does the same for the 32-bit path,
for the s8 and s16 widths it handles. It doesn't improve anything in
selftests or corpora of external objects -- the shape above only shows up
in the test the next patch adds -- but seems like the right thing to do
anyways.

Fixes: 8100928c8814 ("bpf: Support new sign-extension mov insns")
Signed-off-by: Vineet Gupta <vineet.gupta@linux.dev>
---
v3: was v2 5/13.
 - moved to the front: it is unrelated to the low-32 tracking (Alexei)
 - narrowed to the 32-bit path. Commit 0892ef2a7ef3 ("bpf:
   Representation for intervals with steps") has since given
   coerce_reg_to_size_sx() an equivalent early return, so Fixes:
   1f9a1ea821ff goes with that half.
 - measured inert: 0 instruction and 0 state changes on both selftest
   corpora and on 441 external objects.

 kernel/bpf/verifier.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 62f8951126ba..e1b41975a442 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6182,6 +6182,7 @@ static void set_sext32_default_val(struct bpf_reg_state *reg, int size)
 static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
 {
 	s32 init_s32_max, init_s32_min, s32_max, s32_min, u32_val;
+	s32 field_smin, field_smax;
 	u32 top_smax_value, top_smin_value;
 	u32 num_bits = size * 8;
 
@@ -6192,6 +6193,27 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
 	if (reg_umax(reg) < (1ULL << (num_bits - 1)))
 		return;
 
+	if (size == 1) {
+		field_smin = S8_MIN;
+		field_smax = S8_MAX;
+	} else {
+		/* size == 2 */
+		field_smin = S16_MIN;
+		field_smax = S16_MAX;
+	}
+
+	/*
+	 * The range already fits the field, so (sN)v == v for every value the
+	 * register can hold and the sign extension changes nothing. The test
+	 * above misses this once the range straddles zero: it only looks at
+	 * reg_umax(), which a negative smin makes huge.
+	 *
+	 * This has to precede reg_step_reset() below: the extension is a noop,
+	 * so the base/step line still holds and there is nothing to discard.
+	 */
+	if (reg_s32_min(reg) >= field_smin && reg_s32_max(reg) <= field_smax)
+		return;
+
 	/* See comment at reg_step_check_unsigned(). */
 	reg_step_reset(reg);
 
-- 
2.53.0-Meta