selftests/bpf: Tests for loop hierarchy computation

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().

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-49-bcba9bc53ac9@gmail.com

2 files changed, 348 insertions, 0 deletions

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..0608e983d7fc
--- /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 <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/*
+ * kernel/bpf/loops.c:compute_loops_in_subprog() distinguishes 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 D). */
+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{{$}}")
+__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";