Re: [PATCH bpf v2 08/11] selftests/bpf: Add tests for the indirect jump edge limit

[Eduard Zingerman <eddyz87@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 878 bytes --]

On Mon, 2026-09-14 at 19:03 +0200, Daniel Borkmann wrote:
> Add corner case tests for programs whose gotox instructions are their own
> jump table targets.
> 
>   # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t bpf_insn_array
>   [...]
>   #24/10   bpf_insn_array/too-many-gotox-edges:OK
>   #24/11   bpf_insn_array/gotox-edges-at-limit:OK
>   #24/12   bpf_insn_array/gotox-edges-across-subprogs:OK
>   #24      bpf_insn_array:OK
>   Summary: 1/12 PASSED, 0 SKIPPED, 0/0 FAILED
> 
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
> ---

I think it's a bit of an overkill of a test.
Codex generated transformation to inline assembly as attached.
Object file size is 100k, but I think it is significantly easier
to understand in this form. Wdyt?

[-- Attachment #2: inline-asm-gotox.diff --]
[-- Type: text/x-patch, Size: 10629 bytes --]

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
index f102435675c2..70150b54bdaf 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
@@ -454,40 +454,8 @@ static void check_bpf_no_lookup(void)
 	close(map_fd);
 }
 
-#define GOTOX_CNT_AT_LIMIT	1000
 #define GOTOX_LOG_SZ		(256 * 1024)
 
-static const char gotox_limit_msg[] =
-	"number of indirect jump edges in the program exceeds";
-
-static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)
-{
-	/* the run of gotox itself, plus the insn right after it */
-	const __u32 jt_cnt = gotox_cnt + 1;
-	struct bpf_insn_array_value val = {};
-	int map_fd;
-	__u32 i;
-
-	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, jt_cnt);
-	if (!ASSERT_GE(map_fd, 0, "map_create"))
-		return map_fd;
-
-	for (i = 0; i < jt_cnt; i++) {
-		val.orig_off = first_gotox + i;
-		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0,
-			       "bpf_map_update_elem"))
-			goto err;
-	}
-
-	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
-		goto err;
-
-	return map_fd;
-err:
-	close(map_fd);
-	return -1;
-}
-
 static int gotox_prog_load_funcs(struct bpf_insn *insns, __u32 insn_cnt,
 				 int *fd_array, __u32 fd_array_cnt, char *log,
 				 int btf_fd, struct bpf_func_info *fi, __u32 fi_cnt)
@@ -523,208 +491,6 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
 				     -1, NULL, 0);
 }
 
-/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */
-static void gotox_run_fill(struct bpf_insn *insns, __u32 gotox_cnt)
-{
-	__u32 i;
-
-	insns[0] = BPF_MOV64_IMM(BPF_REG_1, 0);
-	for (i = 1; i <= gotox_cnt; i++)
-		insns[i] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
-}
-
-static void check_gotox_limit_hit(const char *log, int err)
-{
-	ASSERT_EQ(err, -E2BIG, "program should have been rejected");
-	ASSERT_HAS_SUBSTR(log, gotox_limit_msg, "verifier log");
-}
-
-static bool try_load_gotox_prog(__u32 gotox_cnt, char *log, int *err)
-{
-	const __u32 insn_cnt = gotox_cnt + 3;
-	struct bpf_insn *insns;
-	bool attempted = false;
-	int map_fd;
-
-	insns = calloc(insn_cnt, sizeof(*insns));
-	if (!ASSERT_OK_PTR(insns, "calloc insns"))
-		return false;
-
-	gotox_run_fill(insns, gotox_cnt);
-	insns[gotox_cnt + 1] = BPF_MOV64_IMM(BPF_REG_0, 0);
-	insns[gotox_cnt + 2] = BPF_EXIT_INSN();
-
-	map_fd = gotox_jt_create(1, gotox_cnt);
-	if (map_fd < 0)
-		goto free_insns;
-
-	*err = gotox_prog_load(insns, insn_cnt, &map_fd, 1, log);
-	close(map_fd);
-	attempted = true;
-free_insns:
-	free(insns);
-	return attempted;
-}
-
-/*
- * The extra exit target in the jump table makes for gotox_cnt * (gotox_cnt
- * + 1) edges, hence the program is over the limit by gotox_cnt edges.
- */
-static void check_too_many_gotox_edges(void)
-{
-	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT;
-	char *log;
-	int err;
-
-	log = calloc(1, GOTOX_LOG_SZ);
-	if (!ASSERT_OK_PTR(log, "calloc log"))
-		return;
-
-	if (try_load_gotox_prog(gotox_cnt, log, &err))
-		check_gotox_limit_hit(log, err);
-
-	free(log);
-}
-
-/*
- * A chain of blocks, where block k loads jt[k] and jumps to it. The jump
- * table holds the starts of the blocks that follow plus the exit block,
- * which is gotox_cnt targets for gotox_cnt gotox, so the program sits
- * exactly at the limit and must still load.
- */
-#define GOTOX_BLOCK_SZ		4
-
-static void gotox_chain_fill(struct bpf_insn *insns, __u32 gotox_cnt)
-{
-	struct bpf_insn *at;
-	__u32 k;
-
-	for (k = 0; k < gotox_cnt; k++) {
-		at = insns + k * GOTOX_BLOCK_SZ;
-
-		/* r1 = &jt[0], by index 0 into fd_array */
-		at[0] = (struct bpf_insn) {
-			.code = BPF_LD | BPF_DW | BPF_IMM,
-			.dst_reg = BPF_REG_1,
-			.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
-			.imm = 0,
-		};
-		at[1] = (struct bpf_insn) { .imm = 0 };
-		at[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, k * 8);
-		at[3] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
-	}
-
-	insns[gotox_cnt * GOTOX_BLOCK_SZ] = BPF_MOV64_IMM(BPF_REG_0, 0);
-	insns[gotox_cnt * GOTOX_BLOCK_SZ + 1] = BPF_EXIT_INSN();
-}
-
-static int gotox_chain_jt_create(__u32 gotox_cnt)
-{
-	struct bpf_insn_array_value val = {};
-	int map_fd;
-	__u32 i;
-
-	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, gotox_cnt);
-	if (!ASSERT_GE(map_fd, 0, "map_create"))
-		return map_fd;
-
-	for (i = 0; i < gotox_cnt; i++) {
-		val.orig_off = (i + 1) * GOTOX_BLOCK_SZ;
-		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0,
-			       "bpf_map_update_elem"))
-			goto err;
-	}
-
-	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
-		goto err;
-
-	return map_fd;
-err:
-	close(map_fd);
-	return -1;
-}
-
-static void check_gotox_edges_at_limit(void)
-{
-	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT;
-	const __u32 insn_cnt = gotox_cnt * GOTOX_BLOCK_SZ + 2;
-	struct bpf_insn *insns;
-	char *log;
-	int map_fd, err;
-
-	log = calloc(1, GOTOX_LOG_SZ);
-	if (!ASSERT_OK_PTR(log, "calloc log"))
-		return;
-
-	insns = calloc(insn_cnt, sizeof(*insns));
-	if (!ASSERT_OK_PTR(insns, "calloc insns"))
-		goto free_log;
-
-	gotox_chain_fill(insns, gotox_cnt);
-
-	map_fd = gotox_chain_jt_create(gotox_cnt);
-	if (map_fd < 0)
-		goto free_insns;
-
-	err = gotox_prog_load(insns, insn_cnt, &map_fd, 1, log);
-	close(map_fd);
-
-	if (!ASSERT_OK(err, "program at the edge limit should load"))
-		fprintf(stderr, "verifier log: %s\n", log);
-
-free_insns:
-	free(insns);
-free_log:
-	free(log);
-}
-
-static void check_gotox_edges_across_subprogs(void)
-{
-	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT * 3 / 4;
-	const __u32 sub_start = gotox_cnt + 3;
-	const __u32 insn_cnt = 2 * (gotox_cnt + 3);
-	int map_fd[2] = { -1, -1 };
-	struct bpf_insn *insns;
-	char *log;
-	int err;
-
-	log = calloc(1, GOTOX_LOG_SZ);
-	if (!ASSERT_OK_PTR(log, "calloc log"))
-		return;
-
-	insns = calloc(insn_cnt, sizeof(*insns));
-	if (!ASSERT_OK_PTR(insns, "calloc insns"))
-		goto free_log;
-
-	gotox_run_fill(insns, gotox_cnt);
-	insns[gotox_cnt + 1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0,
-					    BPF_PSEUDO_CALL, 0,
-					    sub_start - (gotox_cnt + 1) - 1);
-	insns[gotox_cnt + 2] = BPF_EXIT_INSN();
-
-	gotox_run_fill(insns + sub_start, gotox_cnt);
-	insns[sub_start + gotox_cnt + 1] = BPF_MOV64_IMM(BPF_REG_0, 0);
-	insns[sub_start + gotox_cnt + 2] = BPF_EXIT_INSN();
-
-	map_fd[0] = gotox_jt_create(1, gotox_cnt);
-	if (map_fd[0] < 0)
-		goto free_insns;
-	map_fd[1] = gotox_jt_create(sub_start + 1, gotox_cnt);
-	if (map_fd[1] < 0)
-		goto close_maps;
-
-	err = gotox_prog_load(insns, insn_cnt, map_fd, 2, log);
-	check_gotox_limit_hit(log, err);
-
-close_maps:
-	close(map_fd[0]);
-	close(map_fd[1]);
-free_insns:
-	free(insns);
-free_log:
-	free(log);
-}
-
 static int gotox_jt_create_offs(const __u32 *offs, __u32 cnt)
 {
 	struct bpf_insn_array_value val = {};
@@ -1501,12 +1267,6 @@ static void __test_bpf_insn_array(void)
 		check_no_map_reuse();
 	if (test__start_subtest("bpf-side-ops"))
 		check_bpf_side();
-	if (test__start_subtest("too-many-gotox-edges"))
-		check_too_many_gotox_edges();
-	if (test__start_subtest("gotox-edges-at-limit"))
-		check_gotox_edges_at_limit();
-	if (test__start_subtest("gotox-edges-across-subprogs"))
-		check_gotox_edges_across_subprogs();
 	if (test__start_subtest("gotox-jt-spans-subprogs"))
 		check_gotox_jt_spans_subprogs();
 	if (test__start_subtest("gotox-jt-spans-with-own-table"))
diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
index 4931a77ba0b2..b917c2e14283 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -457,6 +457,100 @@ __naked void spill_fill_ptr_to_insn(void)
 	: __clobber_all);
 }
 
+/*
+ * Emit each table entry next to the instruction it targets. Numeric labels
+ * can be reused by .rept, while %= keeps table symbols unique per asm block.
+ * BASE is the code section: libbpf relocates section-relative byte offsets
+ * to instruction offsets in the loaded program.
+ */
+#define GOTOX_TABLE_BEGIN(COUNT) \
+	".pushsection .jumptables,\"\",@progbits;" \
+	"jt_%=:;" \
+	".global jt_%=;" \
+	".size jt_%=, 8 * (" #COUNT ");" \
+	".popsection;" \
+	"r1 = jt_%= ll;"
+
+#define GOTOX_TABLE_ENTRY(LABEL, BASE) \
+	".pushsection .jumptables,\"\",@progbits;" \
+	".quad " LABEL " - " BASE ";" \
+	".popsection;"
+
+/* N gotox instructions, each targeting all N gotox plus the final block. */
+#define GOTOX_SELF_TARGETS(N, BASE) \
+	GOTOX_TABLE_BEGIN(N + 1) \
+	"r0 = 0;" \
+	".rept " #N ";" \
+		GOTOX_TABLE_ENTRY("1f", BASE) \
+		"1:; .8byte %[gotox];" \
+	".endr;" \
+	GOTOX_TABLE_ENTRY("2f", BASE) \
+	"2:;"
+
+#define GOTOX_OPERAND \
+	__imm_insn(gotox, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
+
+/*
+ * Count edges even when their targets are already discovered. These
+ * programs deliberately use a scalar: the CFG edge limit must reject them
+ * before symbolic verification reaches the invalid gotox operand.
+ */
+SEC("socket")
+__description("too-many-gotox-edges")
+__failure __msg("number of indirect jump edges in the program exceeds")
+__naked void too_many_gotox_edges(void)
+{
+	asm volatile (
+		/* 1000 * 1001 = 1,001,000 edges. */
+		GOTOX_SELF_TARGETS(1000, "socket")
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+SEC("socket")
+__description("gotox-edges-at-limit")
+__success __retval(0)
+__naked void gotox_edges_at_limit(void)
+{
+	asm volatile (
+		/*
+		 * 1000 gotox * 1000 targets = 1,000,000 CFG edges. At run
+		 * time, each block loads the next table entry and jumps to
+		 * the following block, so the program terminates.
+		 */
+		GOTOX_TABLE_BEGIN(1000)
+		".rept 1000;"
+			GOTOX_TABLE_ENTRY("1f", "socket")
+			"r0 = *(u64 *)(r1 + 0);"
+			"r1 += 8;"
+			".8byte %[gotox];"
+			"1:;"
+		".endr;"
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+static __noinline __used __naked void gotox_edges_subprog(void)
+{
+	asm volatile (
+		GOTOX_SELF_TARGETS(750, ".text")
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+SEC("socket")
+__description("gotox-edges-across-subprogs")
+__failure __msg("number of indirect jump edges in the program exceeds")
+__naked void gotox_edges_across_subprogs(void)
+{
+	asm volatile (
+		/* Each subprog has 563,250 edges; together, 1,126,500. */
+		GOTOX_SELF_TARGETS(750, "socket")
+		"call gotox_edges_subprog;"
+		"exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
 #endif /* __TARGET_ARCH_x86 || __TARGET_ARCH_arm64 || __TARGET_ARCH_powerpc*/
 
 char _license[] SEC("license") = "GPL";