// 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"
#include "../../../include/linux/filter.h"
/*
* The immediate dominator is printed by log_program() as the numeric column
* immediately before the "<insn#>:" field of every "Program dump" line:
*
* Program dump (scc? loop_header? idom insn#: live_regs_before):
* -1 0: ....... (b7) r0 = 0 <- idom(0) = -1 (subprog entry)
* 0 1: ....... (07) r0 += 1 <- idom(1) = 0
* ^^^^^^
* idom insn#
*/
/* Straight-line code, with an ldimm64 in the middle. */
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 0 1: {{.*}} (18) r1 = 0x1122334455667788")
__msg("{{.*}} 1 3: {{.*}} (07) r0 += 1")
__msg("{{.*}} 3 4: {{.*}} (0f) r0 += r1")
__msg("{{.*}} 4 5: {{.*}} (95) exit")
__naked void straight_line_ldimm64(void)
{
asm volatile (" \
r0 = 0; \
r1 = 0x1122334455667788 ll; \
r0 += 1; \
r0 += r1; \
exit; \
" ::: __clobber_all);
}
/*
* Asymmetric if-then-else diamond: the "then" arm is 5 instructions long, the
* "else" arm is a single instruction. The merge point (insn 8) is dominated by
* the branch (insn 1), not by either arm. This forces idoms_intersect() to walk
* the two predecessors up unequal postorder depths before they meet.
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (85) call bpf_get_prandom_u32#7")
__msg("{{.*}} 0 1: {{.*}} (25) if r0 > 0x0 goto pc+5")
__msg("{{.*}} 1 2: {{.*}} (b7) r1 = 1")
__msg("{{.*}} 2 3: {{.*}} (b7) r1 = 2")
__msg("{{.*}} 3 4: {{.*}} (b7) r1 = 3")
__msg("{{.*}} 4 5: {{.*}} (b7) r1 = 4")
__msg("{{.*}} 5 6: {{.*}} (05) goto pc+1")
__msg("{{.*}} 1 7: {{.*}} (b7) r1 = 9")
__msg("{{.*}} 1 8: {{.*}} (95) exit")
__naked void asymmetric_diamond(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
if r0 > 0 goto 1f; \
r1 = 1; \
r1 = 2; \
r1 = 3; \
r1 = 4; \
goto 2f; \
1: r1 = 9; \
2: exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
/*
* Simple loop: the header (insn 1) is dominated by the pre-header (insn 0). The
* back edge (insn 2 -> insn 1) must not change idom(1); the back-edge
* predecessor folds up via idoms_intersect().
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 0 1: {{.*}} (07) r0 += 1")
__msg("{{.*}} 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2")
__msg("{{.*}} 2 3: {{.*}} (95) exit")
__naked void simple_loop(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
if r0 < 10 goto 1b; \
exit; \
" ::: __clobber_all);
}
/*
* Loop with an if-else in its body. The in-loop merge point (insn 5) is
* dominated by the in-loop branch (insn 3), combining a back-edge intersect
* with a forward-diamond intersect.
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 0 1: {{.*}} (07) r0 += 1")
__msg("{{.*}} 1 2: {{.*}} (bf) r1 = r0")
__msg("{{.*}} 2 3: {{.*}} (25) if r1 > 0x5 goto pc+1")
__msg("{{.*}} 3 4: {{.*}} (b7) r1 = 1")
__msg("{{.*}} 3 5: {{.*}} (0f) r0 += r1")
__msg("{{.*}} 5 6: {{.*}} (a5) if r0 < 0x64 goto pc-6")
__msg("{{.*}} 6 7: {{.*}} (95) exit")
__naked void loop_with_if_else_body(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);
}
/*
* Nested loops: the idom chain runs inner-header -> outer-body -> outer-header
* -> pre-header. Exercises intersect across back edges at two nesting depths.
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 0 1: {{.*}} (07) r0 += 1")
__msg("{{.*}} 1 2: {{.*}} (b7) r1 = 0")
__msg("{{.*}} 2 3: {{.*}} (07) r1 += 1")
__msg("{{.*}} 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2")
__msg("{{.*}} 4 5: {{.*}} (a5) if r0 < 0xa goto pc-5")
__msg("{{.*}} 5 6: {{.*}} (95) exit")
__naked void nested_loops(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);
}
/*
* Loop header (insn 1) with two back edges (from insn 4 and insn 5), i.e. three
* predecessors. Both back edges route through the incrementing header, so the
* loop is bounded and verifies. Repeated idoms_intersect() at the header must
* stay stable and keep idom(1) at the pre-header (insn 0).
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r6 = 0")
__msg("{{.*}} 0 1: {{.*}} (07) r6 += 1")
__msg("{{.*}} 1 2: {{.*}} (25) if r6 > 0xa goto pc+3")
__msg("{{.*}} 2 3: {{.*}} (bf) r7 = r6")
__msg("{{.*}} 3 4: {{.*}} (a5) if r7 < 0x5 goto pc-4")
__msg("{{.*}} 4 5: {{.*}} (05) goto pc-5")
__msg("{{.*}} 2 6: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 6 7: {{.*}} (95) exit")
__naked void multi_backedge_header(void)
{
asm volatile (" \
r6 = 0; \
1: r6 += 1; \
if r6 > 10 goto 2f; \
r7 = r6; \
if r7 < 5 goto 1b; \
goto 1b; \
2: r0 = 0; \
exit; \
" ::: __clobber_all);
}
/*
* Irreducible CFG (loop with two entries, insn 3 and insn 5, reached from the
* insn 2 branch). Dominators remain well-defined; this is a convergence test
* for the fixpoint under irreducibility. Note insn 6 is dominated by the branch
* (insn 2), not by either arm.
*/
SEC("socket")
__success
__log_level(2)
__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("{{.*}} 2 3: {{.*}} (b7) r1 = 1")
__msg("{{.*}} 3 4: {{.*}} (05) goto pc+1")
__msg("{{.*}} 2 5: {{.*}} (b7) r1 = 2")
__msg("{{.*}} 2 6: {{.*}} (0f) r0 += r1")
__msg("{{.*}} 6 7: {{.*}} (a5) if r0 < 0x10 goto pc-5")
__msg("{{.*}} 7 8: {{.*}} (95) exit")
__naked void 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);
}
/*
* Idoms are computed per subprog. Layout (libbpf preorder) is:
* main: 0..1, sub: 2..7
* The callee entry (insn 2) must have idom -1 (subprog reset), and idoms inside
* the callee must reference only the callee's instructions, never main's. The
* in-callee merge (insn 7) is dominated by the in-callee branch (insn 3). The
* branch is on a prandom value so it is not constant-folded away.
*/
static __naked __noinline __used
unsigned long idoms_diamond_sub(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
if r0 > 0 goto 1f; \
r0 = 1; \
goto 2f; \
1: r0 = 2; \
2: exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (85) call pc+1")
__msg("{{.*}} 0 1: {{.*}} (95) exit")
__msg("{{.*}} -1 2: {{.*}} (85) call bpf_get_prandom_u32#7")
__msg("{{.*}} 2 3: {{.*}} (25) if r0 > 0x0 goto pc+2")
__msg("{{.*}} 3 4: {{.*}} (b7) r0 = 1")
__msg("{{.*}} 4 5: {{.*}} (05) goto pc+1")
__msg("{{.*}} 3 6: {{.*}} (b7) r0 = 2")
__msg("{{.*}} 3 7: {{.*}} (95) exit")
__naked void multi_subprog(void)
{
asm volatile (" \
call idoms_diamond_sub; \
exit; \
" ::: __clobber_all);
}
/*
* The first instruction of a subprog (insn 3) is itself a loop header, i.e. it
* has an incoming back edge. Its idom must still be -1 (the subprog entry has no
* dominator). Exercises the idoms[start]=start ... idoms[start]=-1 handling in
* compute_subprog_idoms().
*/
static __naked __noinline __used
unsigned long idoms_entry_header_sub(void)
{
asm volatile (" \
1: r1 += 1; \
if r1 < 10 goto 1b; \
r0 = 0; \
exit; \
" ::: __clobber_all);
}
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (b7) r1 = 0")
__msg("{{.*}} 0 1: {{.*}} (85) call pc+1")
__msg("{{.*}} 1 2: {{.*}} (95) exit")
__msg("{{.*}} -1 3: {{.*}} (07) r1 += 1")
__msg("{{.*}} 3 4: {{.*}} (a5) if r1 < 0xa goto pc-2")
__msg("{{.*}} 4 5: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 5 6: {{.*}} (95) exit")
__naked void entry_is_loop_header(void)
{
asm volatile (" \
r1 = 0; \
call idoms_entry_header_sub; \
exit; \
" ::: __clobber_all);
}
/*
* Self-loop: insn 1 is its own predecessor. idom(1) must be the pre-header
* (insn 0); the self-edge is ignored (idoms[pred] == -1 on the first pass, then
* idoms_intersect(a == b) short-circuits). Program is rejected later for an
* infinite loop, but the dump (and idoms) are printed before that.
*/
SEC("socket")
__failure
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (85) call bpf_get_prandom_u32#7")
__msg("{{.*}} 0 1: {{.*}} (a5) if r0 < 0xa goto pc-1")
__msg("{{.*}} 1 2: {{.*}} (95) exit")
__msg("infinite loop detected")
__naked void self_loop(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
1: if r0 < 10 goto 1b; \
exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
#if defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_powerpc)
/*
* Indirect jump (gotox) with a two-entry jump table. The gotox (insn 4) has two
* successors (insn 5 and insn 7), so both targets have the gotox as their only
* predecessor and idom.
*/
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg("{{.*}} -1 0: {{.*}} (18) r0 = {{0x[0-9a-f]+}}")
__msg("{{.*}} 0 2: {{.*}} (07) r0 += 8")
__msg("{{.*}} 2 3: {{.*}} (79) r0 = *(u64 *)(r0 +0)")
__msg("{{.*}} 3 4: {{.*}} (0d) gotox r0")
__msg("{{.*}} 4 5: {{.*}} (b7) r0 = 0")
__msg("{{.*}} 5 6: {{.*}} (95) exit")
__msg("{{.*}} 4 7: {{.*}} (b7) r0 = 1")
__msg("{{.*}} 7 8: {{.*}} (95) exit")
__naked void gotox_jump_table(void)
{
asm volatile (" \
.pushsection .jumptables,\"\",@progbits; \
jt0_%=: \
.quad ret0_%= - socket; \
.quad ret1_%= - socket; \
.size jt0_%=, 16; \
.global jt0_%=; \
.popsection; \
\
r0 = jt0_%= ll; \
r0 += 8; \
r0 = *(u64 *)(r0 + 0); \
.8byte %[gotox_r0]; \
ret0_%=: \
r0 = 0; \
exit; \
ret1_%=: \
r0 = 1; \
exit; \
" :
: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
: __clobber_all);
}
#endif
char _license[] SEC("license") = "GPL";