Test cases covering the following branches in bpf_compute_loops(): - Case B: simple backedge creating a loop (loop_single) - Case B: two independent loops (loop_two_independent) - Case B + D: nested loops where the inner header's loop_header points to the outer header (loop_nested) - Case C: diamond CFG with no loops (fwd_edges_no_loop) - Case D: sibling inner loops within one outer loop (loop_nested_siblings) - Three levels of loop nesting (loop_three_levels) - Loop with an if-else body containing forward branches (loop_with_if_else) - Case E: An irreducible loop (loop_irreducible) - A self-loop (loop_self) - A test with sibling loops nested in outer loops (loop_nested_siblings_common_ancestors) - A test case with outer loop's backedge originating from an inner loop (loop_outer_backedge_from_inner). Cases B, C, D and E are described in loops.c:compute_loops_in_subprog(). Reviewed-by: Emil Tsalapatis Signed-off-by: Eduard Zingerman dominators test case --- tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_loop_hierarchy.c | 346 +++++++++++++++++++++ 2 files changed, 348 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c index 2f05a0ce829f..6b60d7720e2a 100644 --- a/tools/testing/selftests/bpf/prog_tests/verifier.c +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c @@ -74,6 +74,7 @@ #include "verifier_live_stack.skel.h" #include "verifier_liveness_exp.skel.h" #include "verifier_load_acquire.skel.h" +#include "verifier_loop_hierarchy.skel.h" #include "verifier_loops1.skel.h" #include "verifier_lwt.skel.h" #include "verifier_map_in_map.skel.h" @@ -261,6 +262,7 @@ void test_verifier_leak_ptr(void) { RUN(verifier_leak_ptr); } void test_verifier_linked_scalars(void) { RUN(verifier_linked_scalars); } void test_verifier_live_stack(void) { RUN(verifier_live_stack); } void test_verifier_liveness_exp(void) { RUN(verifier_liveness_exp); } +void test_verifier_loop_hierarchy(void) { RUN(verifier_loop_hierarchy); } void test_verifier_loops1(void) { RUN(verifier_loops1); } void test_verifier_lwt(void) { RUN(verifier_lwt); } void test_verifier_map_in_map(void) { RUN(verifier_map_in_map); } diff --git a/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c b/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c new file mode 100644 index 000000000000..0f49108c0e50 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c @@ -0,0 +1,346 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include +#include +#include "bpf_misc.h" + +/* + * kernel/bpf/loops.c:compute_loops() distinguish between + * the following cases: + * - B: backedge -> simple loop + * - C: cross edge to non-loop node -> no-op + * - D: edge to node whose header is in DFS path -> nested loop + * - E: edge to node whose header is NOT in DFS path -> irreducible + * + * Below test cases cover the above branches in various combinations. + */ + +/* Case B: single bounded loop. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 1 0 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 2 3: {{.*}} (95) exit") +__naked void loop_single(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case B: two independent loops at the same nesting level. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg("loop at 4{{$}}") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 2 0 1: {{.*}} (07) r0 += 1") +__msg(" 2 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 2 3: {{.*}} (b7) r1 = 0") +__msg(" 1 3 4: {{.*}} (07) r1 += 1") +__msg(" 1 4 4 5: {{.*}} (a5) if r1 < 0xa goto pc-2") +__msg(" 5 6: {{.*}} (95) exit") +__naked void loop_two_independent(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + if r0 < 10 goto 1b; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 10 goto 2b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case B + D: nested loops. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg("loop at 3, nested in 1") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 1 0 1: {{.*}} (07) r0 += 1") /* outer loop header */ +__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0") /* outer loop insn */ +__msg(" 1 1 2 3: {{.*}} (07) r1 += 1") /* inner loop header */ +__msg(" 1 3 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") /* inner loop insn */ +__msg(" 1 1 4 5: {{.*}} (a5) if r0 < 0xa goto pc-5") /* outer loop insn */ +__msg(" 5 6: {{.*}} (95) exit") +__naked void loop_nested(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 5 goto 2b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case C: forward edges, no loops. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" -1 0: {{.*}} (85) call bpf_get_prandom_u32") +__msg(" 0 1: {{.*}} (25) if r0 > 0x0 goto pc+2") +__msg(" 1 2: {{.*}} (b7) r0 = 2") +__msg(" 2 3: {{.*}} (05) goto pc+1") +__msg(" 1 4: {{.*}} (b7) r0 = 3") +__msg(" 1 5: {{.*}} (95) exit") +__naked void fwd_edges_no_loop(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + if r0 > 0 goto 1f; \ + r0 = 2; \ + goto 2f; \ +1: r0 = 3; \ +2: exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Case B + D: two sibling inner loops within one outer loop. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg("loop at 3, nested in 1") +__msg("loop at 6, nested in 1") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 1 0 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 2 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") +__msg(" 1 1 4 5: {{.*}} (b7) r2 = 0") +__msg(" 1 1 5 6: {{.*}} (07) r2 += 1") +__msg(" 1 6 6 7: {{.*}} (a5) if r2 < 0x5 goto pc-2") +__msg(" 1 1 7 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 8 9: {{.*}} (95) exit") +__naked void loop_nested_siblings(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 5 goto 2b; \ + r2 = 0; \ +3: r2 += 1; \ + if r2 < 5 goto 3b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Three levels of nesting. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg("loop at 3, nested in 1") +__msg("loop at 5, nested in 3") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 1 0 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 2 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 3 4: {{.*}} (b7) r2 = 0") +__msg(" 1 3 4 5: {{.*}} (07) r2 += 1") +__msg(" 1 5 5 6: {{.*}} (a5) if r2 < 0x3 goto pc-2") +__msg(" 1 3 6 7: {{.*}} (a5) if r1 < 0x5 goto pc-5") +__msg(" 1 1 7 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 8 9: {{.*}} (95) exit") +__naked void loop_three_levels(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + r2 = 0; \ +3: r2 += 1; \ + if r2 < 3 goto 3b; \ + if r1 < 5 goto 2b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Loop with an if-else body (forward branch inside loop, Case C). */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1") +__msg("Program dump") +__msg(" -1 0: {{.*}} (b7) r0 = 0") +__msg(" 1 0 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 1 2: {{.*}} (bf) r1 = r0") +__msg(" 1 1 2 3: {{.*}} (25) if r1 > 0x5 goto pc+1") +__msg(" 1 1 3 4: {{.*}} (b7) r1 = 1") +__msg(" 1 1 3 5: {{.*}} (0f) r0 += r1") +__msg(" 1 1 5 6: {{.*}} (a5) if r0 < 0x64 goto pc-6") +__msg(" 6 7: {{.*}} (95) exit") +__naked void loop_with_if_else(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = r0; \ + if r1 > 5 goto 2f; \ + r1 = 1; \ +2: r0 += r1; \ + if r0 < 100 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case E: irreducible loop. */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 3, irreducible") +__msg("Program dump") +__msg(" -1 0: {{.*}} (85) call bpf_get_prandom_u32#7") +__msg(" 0 1: {{.*}} (b7) r1 = 0") +__msg(" 1 2: {{.*}} (25) if r0 > 0x5 goto pc+2") +__msg(" 1 2 3: {{.*}} (b7) r1 = 1") +__msg(" 1 3 3 4: {{.*}} (05) goto pc+1") +__msg(" 2 5: {{.*}} (b7) r1 = 2") +__msg(" 1 3 2 6: {{.*}} (0f) r0 += r1") +__msg(" 1 3 6 7: {{.*}} (a5) if r0 < 0x10 goto pc-5") +__msg(" 7 8: {{.*}} (95) exit") +__naked void loop_irreducible(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = 0; \ + if r0 > 5 goto 2f; \ +1: r1 = 1; \ + goto 3f; \ +2: r1 = 2; \ +3: r0 += r1; \ + if r0 < 16 goto 1b; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__failure +__log_level(2) +__msg("loop at 1") +__msg("infinite loop detected at insn 1") +__naked void loop_self(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ +1: if r0 < 10 goto 1b; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* + * Loops at 5 and 7 are nested inside loops at 3 and 1. + * The edge 6 -> 7 exits loop at 5 and enters loop at 7. + * Check that it is logged only as an exit from loop at 5. + * + * 0: r0 = 0; + * do { + * 1: r0++; + * 2: r1 = 0; + * do { + * 3: r1++; + * 4: r2 = 0; + * do { + * 5: r2++; + * 6: } while (r2 < 3); + * do { + * 7: r2--; + * 8: } while (r2 != 0); + * 9: } while (r1 < 4); + * 10: } while (r0 < 5); + * 11: return r0; + */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 1{{$}}") +__msg_next(" backedge from 10, latch at 10") +__msg_next(" exit from 10 to 11") +__msg_next("loop at 3, nested in 1") +__msg_next(" backedge from 9, latch at 9") +__msg_next(" exit from 9 to 10") +__msg_next("loop at 5, nested in 3") +__msg_next(" backedge from 6, latch at 6") +__msg_next(" exit from 6 to 7") +__msg_next("loop at 7, nested in 3") +__msg_next(" backedge from 8, latch at 8") +__msg_next(" exit from 8 to 9") +__naked void loop_nested_siblings_common_ancestors(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + r2 = 0; \ +3: r2 += 1; \ + if r2 < 3 goto 3b; \ +4: r2 += -1; \ + if r2 != 0 goto 4b; \ + if r1 < 4 goto 2b; \ + if r0 < 5 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* + * The outer loop backedge (4 -> 2) originates in an inner loop. + * For now, latch should not be identified in such cases. + */ +SEC("socket") +__success +__log_level(2) +__msg("loop at 2{{$}}") +__msg_next(" backedge from 4, latch at -1") +__msg_next(" exit from 5 to 7") +__msg_next("loop at 3, nested in 2") +__msg_next(" backedge from 6, latch at 5") +__msg_next(" exit from 4 to 2") +__msg_next(" exit from 5 to 7") +__naked void loop_outer_backedge_from_inner(void) +{ + asm volatile (" \ + r6 = 99; \ + r2 = 2; \ +2: r6 += 1; /* loop at 2 */ \ +3: r2 += 1; /* loop at 3 */ \ +4: if r2 == 3 goto 2b; \ +5: if r6 > 100 goto 7f; \ + goto 3b; \ +7: r0 = 0; \ + exit; \ +" ::: __clobber_all); +} + +char _license[] SEC("license") = "GPL"; -- 2.53.0