selftests/bpf: Cases with empty range error under old clamping logic

A 64-bit and 32-bit examples leading to an empty register range error
when scev.c:bpf_clamp_scev_regs() intersected current register state
with computed iteration range:

        r1 = 0;           verification
        r3 = 0;               path
  loop:   r3 += 1;              | <---------.
          if r3 != 5 goto +0;   | r3 ∈ {5}  |
          r1 += 1;              |           |
          if r1 != 5 goto loop; '-----------'
        r0 = 0;
        exit;

- At header r3 ∈ {0,1,2,3,4}.
- After `if r3 != 5 goto ...` continued with r3 ∈ {5}.
- On a second iteration bpf_clamp_scev_regs() computed:

    r3 := {0,1,2,3,4} ∩ {5} = ∅

  And reported an error:

    verifier bug: scev clamp produced empty range for r3

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261026-scev-simpler-clamp-v2-8-f373aec9825f@gmail.com

1 files changed, 55 insertions, 0 deletions

diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 805157cfea78..4e58dd475b88 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -1604,6 +1604,61 @@ __naked void post_cond_jne_neg_step(void)
 "	::: __clobber_all);
 }
 
+/*
+ * r1 and r3 are widened independently, so the r3 == 5 path reaches the back
+ * edge with r3 past the last value it takes at the header.
+ */
+SEC("socket")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("loop header at 2, header_count is 5 ")
+__msg("loop header at 2, widening r1 to 0..4 step 1")
+__msg("loop header at 2, widening r3 to 0..4 step 1")
+__msg("3: (55) if r3 != 0x5 goto pc+1 {{.*}}; R3=5")
+__msg("loop header at 2, clamping r3 to 0..4 step 1")
+__msg("from 6 to 2: safe")
+__naked void clamp_dependent_overshoot(void)
+{
+	asm volatile ("					\
+	r1 = 0;						\
+	r3 = 0;						\
+1:	r3 += 1;					\
+	if r3 != 5 goto 2f;				\
+	r2 = 0;						\
+2:	r1 += 1;					\
+	if r1 != 5 goto 1b;				\
+	r0 = 0;						\
+	exit;						\
+"	::: __clobber_all);
+}
+
+/* Same with a 32-bit dependent register, SCEV (zext32 (linear r3 1)) */
+SEC("socket")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("loop header at 2, header_count is 5 ")
+__msg("loop header at 2, widening r1 to 0..4 step 1")
+__msg("loop header at 2, widening r3 to 0..4 step 1")
+__msg("3: (56) if w3 != 0x5 goto pc+1 {{.*}}; R3=5")
+__msg("loop header at 2, clamping r3 to 0..4 step 1")
+__msg("from 6 to 2: safe")
+__naked void clamp_dependent_overshoot32(void)
+{
+	asm volatile ("					\
+	r1 = 0;						\
+	w3 = 0;						\
+1:	w3 += 1;					\
+	if w3 != 5 goto 2f;				\
+	r2 = 0;						\
+2:	r1 += 1;					\
+	if r1 != 5 goto 1b;				\
+	r0 = 0;						\
+	exit;						\
+"	::: __clobber_all);
+}
+
 SEC("xdp")
 __success
 __log_level(2)