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 --- tools/testing/selftests/bpf/progs/verifier_scev.c | 55 +++++++++++++++++++++++ 1 file changed, 55 insertions(+) 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) -- 2.56.0