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 inner header's loop_header points to outer (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 if-else body containing forward branches (loop_with_if_else) Signed-off-by: Eduard Zingerman --- tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_loop_hierarchy.c | 233 +++++++++++++++++++++ 2 files changed, 235 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c index 219ff2969868..35d92d176c1f 100644 --- a/tools/testing/selftests/bpf/prog_tests/verifier.c +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c @@ -57,6 +57,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" @@ -208,6 +209,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..84cabfa42485 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c @@ -0,0 +1,233 @@ +// 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 2 1: {{.*}} (07) r0 += 1") +__msg(" 2 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 3: {{.*}} (b7) r1 = 0") +__msg(" 1 4: {{.*}} (07) r1 += 1") +__msg(" 1 4 5: {{.*}} (a5) if r1 < 0xa goto pc-2") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") /* outer loop header */ +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") /* outer loop insn */ +__msg(" 1 1 3: {{.*}} (07) r1 += 1") /* inner loop header */ +__msg(" 1 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") /* inner loop insn */ +__msg(" 1 1 5: {{.*}} (a5) if r0 < 0xa goto pc-5") /* outer loop insn */ +__msg(" 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(" 0: {{.*}} (85) call bpf_get_prandom_u32") +__msg(" 1: {{.*}} (25) if r0 > 0x0 goto pc+2") +__msg(" 2: {{.*}} (b7) r0 = 2") +__msg(" 3: {{.*}} (05) goto pc+1") +__msg(" 4: {{.*}} (b7) r0 = 3") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") +__msg(" 1 1 5: {{.*}} (b7) r2 = 0") +__msg(" 1 1 6: {{.*}} (07) r2 += 1") +__msg(" 1 6 7: {{.*}} (a5) if r2 < 0x5 goto pc-2") +__msg(" 1 1 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 4: {{.*}} (b7) r2 = 0") +__msg(" 1 3 5: {{.*}} (07) r2 += 1") +__msg(" 1 5 6: {{.*}} (a5) if r2 < 0x3 goto pc-2") +__msg(" 1 3 7: {{.*}} (a5) if r1 < 0x5 goto pc-5") +__msg(" 1 1 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (bf) r1 = r0") +__msg(" 1 1 3: {{.*}} (25) if r1 > 0x5 goto pc+1") +__msg(" 1 1 4: {{.*}} (b7) r1 = 1") +__msg(" 1 1 5: {{.*}} (0f) r0 += r1") +__msg(" 1 1 6: {{.*}} (a5) if r0 < 0x64 goto pc-6") +__msg(" 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("Program dump") +__msg(" 0: {{.*}} (85) call bpf_get_prandom_u32") +__msg(" 1: {{.*}} (b7) r1 = 0") +__msg(" 2: {{.*}} (25) if r0 > 0x5 goto pc+2") +__msg(" 1 3: {{.*}} (b7) r1 = 1") +__msg(" 1 3 4: {{.*}} (05) goto pc+1") +__msg(" 5: {{.*}} (b7) r1 = 2") +__msg(" 1 3 6: {{.*}} (0f) r0 += r1") +__msg(" 1 3 7: {{.*}} (a5) if r0 < 0x10 goto pc-5") +__msg(" 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); +} + +char _license[] SEC("license") = "GPL"; -- 2.54.0