[PATCH bpf 1/6] bpf: Avoid quadratic successor rescan in bpf_compute_scc

[PATCH bpf 1/6] bpf: Avoid quadratic successor rescan in bpf_compute_scc

[Daniel Borkmann]

The iterative Tarjan DFS in bpf_compute_scc() emulates recursion with an
explicit 'dfs' stack: when a successor has not been visited yet, the
successor is pushed and the walk restarts at the top of the loop. On the
way back to a vertex the successor scan starts over at index zero, so a
vertex with k successors rescans up to k successors on each of its up to k
descents, i.e. O(k^2) work.

For ordinary instructions k <= 2 and this is irrelevant. For a gotox the
successors are the jump table of the containing subprogram, whose size is
bounded only by the max_entries of the insn_array map, so k can reach the
1M instruction complexity limit. Loading such a program keeps a CPU busy
in the loop for a very long time before verification even begins.

Record in 'dfs_pos' the successor index each frame stopped at and resume
the scan there. Each edge is therefore examined a bounded number of times
and the walk becomes linear in the number of edges.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------
 1 file changed, 35 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 842c7d1eabcc..081f7003eae6 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -749,7 +749,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 	struct bpf_insn_aux_data *aux = env->insn_aux_data;
 	const u32 insn_cnt = env->prog->len;
 	int stack_sz, dfs_sz, err = 0;
-	u32 *stack, *pre, *low, *dfs;
+	u32 *stack, *pre, *low, *dfs, *dfs_pos;
 	u32 i, j, t, w;
 	u32 next_preorder_num;
 	u32 next_scc_id;
@@ -762,13 +762,16 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 	 * - 'stack' accumulates vertices in DFS order, see invariant comment below;
 	 * - 'pre[t] == p' => preorder number of vertex 't' is 'p';
 	 * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n';
-	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion.
+	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion;
+	 * - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its
+	 *   successors at index 'j'.
 	 */
 	stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
 	pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
 	low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
 	dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL_ACCOUNT);
-	if (!stack || !pre || !low || !dfs) {
+	dfs_pos = kvcalloc(insn_cnt, sizeof(*dfs_pos), GFP_KERNEL_ACCOUNT);
+	if (!stack || !pre || !low || !dfs || !dfs_pos) {
 		err = -ENOMEM;
 		goto exit;
 	}
@@ -851,6 +854,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 		stack_sz = 0;
 		dfs_sz = 1;
 		dfs[0] = i;
+		dfs_pos[0] = 0;
 dfs_continue:
 		while (dfs_sz) {
 			w = dfs[dfs_sz - 1];
@@ -860,13 +864,37 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 				next_preorder_num++;
 				stack[stack_sz++] = w;
 			}
-			/* Visit 'w' successors */
+			/*
+			 * Visit 'w' successors, resuming at the successor this
+			 * frame last descended into. Restarting the scan at zero
+			 * on every return to 'w' would examine each successor
+			 * once per descent, i.e. quadratic in the number of
+			 * successors, which for a gotox is the size of the jump
+			 * table.
+			 *
+			 * Re-folding the successors before that index would be a
+			 * no-op. Such a successor 's' has 'pre[s] != 0' by then,
+			 * so it is never pushed onto 'dfs' again, and low[s] can
+			 * only decrease while 's' is the top of 'dfs'. If 's' is
+			 * still on 'dfs' it sits below 'w' and cannot become the
+			 * top before 'w' is popped; otherwise the only remaining
+			 * write to low[s] is the pop of its SCC, setting it to
+			 * NOT_ON_STACK, for which the min below is a no-op.
+			 */
 			succ = bpf_insn_successors(env, w);
-			for (j = 0; j < succ->cnt; ++j) {
+			for (j = dfs_pos[dfs_sz - 1]; j < succ->cnt; ++j) {
 				if (pre[succ->items[j]]) {
 					low[w] = min(low[w], low[succ->items[j]]);
 				} else {
-					dfs[dfs_sz++] = succ->items[j];
+					/*
+					 * Resume at 'j', not 'j + 1': the successor
+					 * is revisited once its DFS completes, to
+					 * fold its low[] into low[w].
+					 */
+					dfs_pos[dfs_sz - 1] = j;
+					dfs_pos[dfs_sz] = 0;
+					dfs[dfs_sz] = succ->items[j];
+					dfs_sz++;
 					goto dfs_continue;
 				}
 			}
@@ -916,5 +944,6 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 	kvfree(pre);
 	kvfree(low);
 	kvfree(dfs);
+	kvfree(dfs_pos);
 	return err;
 }
-- 
2.43.0

[PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program

[Daniel Borkmann]

Every gotox instruction gets its own copy of the jump table of the subprog
containing it, and each distinct target in that table is a CFG successor
of the instruction. The number of such edges is therefore the number of
gotox instructions times the number of distinct targets, and neither
factor is bounded by anything except the instruction limit.

What is expensive is a BPF prog whose gotox instructions are themselves
the targets, which makes the edge count quadratic. 1024 such gotox are
already ~1e6 edges and about 4s of CPU to load.

Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka
the limit as the number of instructions the verifier processes. Progs
with real switch statements are orders of magnitude below this.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/cfg.c             | 15 +++++++++++++++
 2 files changed, 16 insertions(+)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 36b65797877d..04bb8f71cabe 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -977,6 +977,7 @@ struct bpf_verifier_env {
 		int cur_stack;
 		/* current position in the insn_postorder vector */
 		int cur_postorder;
+		u32 gotox_edges;
 	} cfg;
 	struct backtrack_state bt;
 	struct bpf_jmp_history_entry *cur_hist_ent;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 081f7003eae6..e9910228da58 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -9,6 +9,8 @@
 
 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
 
+#define BPF_MAX_GOTOX_EDGES	BPF_COMPLEXITY_LIMIT_INSNS
+
 /* non-recursive DFS pseudo code
  * 1  procedure DFS-iterative(G,v):
  * 2      label v as discovered
@@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
 			return PTR_ERR(jt);
 
 		env->insn_aux_data[t].jt = jt;
+
+		if (check_add_overflow(env->cfg.gotox_edges, jt->cnt,
+				       &env->cfg.gotox_edges) ||
+		    env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) {
+			verbose(env, "number of indirect jump edges in the program exceeds %u\n",
+				BPF_MAX_GOTOX_EDGES);
+			bpf_diag_program_structure(
+				env, t, "too many indirect jump edges",
+				"Reduce the number of indirect jumps, or the number of distinct targets they can reach.",
+				"The program has more than %u indirect jump edges in total, counted over every gotox instruction.",
+				BPF_MAX_GOTOX_EDGES);
+			return -E2BIG;
+		}
 	}
 
 	mark_prune_point(env, t);
-- 
2.43.0

Re: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

Pre-existing issues:
- [Critical] Integer overflow in jump table size calculation leads to massive out-of-bounds memory access.
--

commit 4185a35dbc8e33f3114fd8855cb5ca01b0ecf5a9
Author: Daniel Borkmann <daniel@iogearbox.net>

bpf: Bound the number of indirect jump edges in a program

Bounds the total number of gotox edges across the program at
BPF_COMPLEXITY_LIMIT_INSNS to prevent excessive memory and CPU usage
during program loading.

Reported-by: STAR Labs SG <info@starlabs.sg>

[ ... ]

> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 081f7003eae66..e9910228da587 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
>  			return PTR_ERR(jt);
>  
>  		env->insn_aux_data[t].jt = jt;
> +
> +		if (check_add_overflow(env->cfg.gotox_edges, jt->cnt,
> +				       &env->cfg.gotox_edges) ||
> +		    env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) {
> +			verbose(env, "number of indirect jump edges in the program exceeds %u\n",
> +				BPF_MAX_GOTOX_EDGES);
> +			bpf_diag_program_structure(
> +				env, t, "too many indirect jump edges",
> +				"Reduce the number of indirect jumps, or the number of distinct targets they can reach.",
> +				"The program has more than %u indirect jump edges in total, counted over every gotox instruction.",
> +				BPF_MAX_GOTOX_EDGES);
> +			return -E2BIG;
> +		}

[Severity: Critical]
This isn't a bug introduced by this patch, but it is a pre-existing issue
in the CFG discovery logic that remains unfixed in this patch series.

Can jt_from_subprog() in kernel/bpf/cfg.c overflow the shift operation
when calculating the size for memcpy()?

If a user with CAP_BPF creates an INSN_ARRAY map with a very large
max_entries (e.g., 0x20000000) and populates it, jt_cur->cnt can be up to
map->max_entries.

In kernel/bpf/cfg.c:jt_from_subprog():

    memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);

If jt_cur->cnt reaches 0x20000000, the expression jt_cur->cnt << 2
evaluates as a signed 32-bit integer, resulting in -2147483648.

When passed to memcpy(), which expects a size_t, this negative value is
sign-extended to 0xFFFFFFFF80000000 on 64-bit systems. memcpy() attempts
to copy over 18 exabytes of data, causing a catastrophic page fault.

Additionally, if max_entries is 0x40000000, the shift results in 0,
leaving jt->items uninitialized before it is passed to
sort_insn_array_uniq().

>  	}
>  
>  	mark_prune_point(env, t);

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260909204035.24289-1-daniel@iogearbox.net?part=2

Re: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program

[Daniel Borkmann]

On 9/9/26 10:57 PM, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> 
> Pre-existing issues:
> - [Critical] Integer overflow in jump table size calculation leads to massive out-of-bounds memory access.

false positive

> commit 4185a35dbc8e33f3114fd8855cb5ca01b0ecf5a9
> Author: Daniel Borkmann <daniel@iogearbox.net>
> 
> bpf: Bound the number of indirect jump edges in a program
> 
> Bounds the total number of gotox edges across the program at
> BPF_COMPLEXITY_LIMIT_INSNS to prevent excessive memory and CPU usage
> during program loading.
> 
> Reported-by: STAR Labs SG <info@starlabs.sg>
> 
> [ ... ]
> 
>> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
>> index 081f7003eae66..e9910228da587 100644
>> --- a/kernel/bpf/cfg.c
>> +++ b/kernel/bpf/cfg.c
>> @@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
>>   			return PTR_ERR(jt);
>>   
>>   		env->insn_aux_data[t].jt = jt;
>> +
>> +		if (check_add_overflow(env->cfg.gotox_edges, jt->cnt,
>> +				       &env->cfg.gotox_edges) ||
>> +		    env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) {
>> +			verbose(env, "number of indirect jump edges in the program exceeds %u\n",
>> +				BPF_MAX_GOTOX_EDGES);
>> +			bpf_diag_program_structure(
>> +				env, t, "too many indirect jump edges",
>> +				"Reduce the number of indirect jumps, or the number of distinct targets they can reach.",
>> +				"The program has more than %u indirect jump edges in total, counted over every gotox instruction.",
>> +				BPF_MAX_GOTOX_EDGES);
>> +			return -E2BIG;
>> +		}
> 
> [Severity: Critical]
> This isn't a bug introduced by this patch, but it is a pre-existing issue
> in the CFG discovery logic that remains unfixed in this patch series.
> 
> Can jt_from_subprog() in kernel/bpf/cfg.c overflow the shift operation
> when calculating the size for memcpy()?
> 
> If a user with CAP_BPF creates an INSN_ARRAY map with a very large
> max_entries (e.g., 0x20000000) and populates it, jt_cur->cnt can be up to
> map->max_entries.
> 
> In kernel/bpf/cfg.c:jt_from_subprog():
> 
>      memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> 
> If jt_cur->cnt reaches 0x20000000, the expression jt_cur->cnt << 2
> evaluates as a signed 32-bit integer, resulting in -2147483648.

Anything above max entries of 0x1FFFFFFF gets rejected, so this should not
be possible. I tried to reproduce the above and can confirm this is the
case.

> When passed to memcpy(), which expects a size_t, this negative value is
> sign-extended to 0xFFFFFFFF80000000 on 64-bit systems. memcpy() attempts
> to copy over 18 exabytes of data, causing a catastrophic page fault.
> 
> Additionally, if max_entries is 0x40000000, the shift results in 0,
> leaving jt->items uninitialized before it is passed to
> sort_insn_array_uniq().

Re: [PATCH bpf 2/6] bpf: Bound the number of indirect jump edges in a program

[Anton Protopopov]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> Every gotox instruction gets its own copy of the jump table of the subprog
> containing it, and each distinct target in that table is a CFG successor
> of the instruction. The number of such edges is therefore the number of
> gotox instructions times the number of distinct targets, and neither
> factor is bounded by anything except the instruction limit.
> 
> What is expensive is a BPF prog whose gotox instructions are themselves
> the targets, which makes the edge count quadratic. 1024 such gotox are
> already ~1e6 edges and about 4s of CPU to load.
> 
> Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka
> the limit as the number of instructions the verifier processes. Progs
> with real switch statements are orders of magnitude below this.
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Reported-by: STAR Labs SG <info@starlabs.sg>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  include/linux/bpf_verifier.h |  1 +
>  kernel/bpf/cfg.c             | 15 +++++++++++++++
>  2 files changed, 16 insertions(+)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 36b65797877d..04bb8f71cabe 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -977,6 +977,7 @@ struct bpf_verifier_env {
>  		int cur_stack;
>  		/* current position in the insn_postorder vector */
>  		int cur_postorder;
> +		u32 gotox_edges;
>  	} cfg;
>  	struct backtrack_state bt;
>  	struct bpf_jmp_history_entry *cur_hist_ent;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 081f7003eae6..e9910228da58 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -9,6 +9,8 @@
>  
>  #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
>  
> +#define BPF_MAX_GOTOX_EDGES	BPF_COMPLEXITY_LIMIT_INSNS
> +
>  /* non-recursive DFS pseudo code
>   * 1  procedure DFS-iterative(G,v):
>   * 2      label v as discovered
> @@ -388,6 +390,19 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
>  			return PTR_ERR(jt);
>  
>  		env->insn_aux_data[t].jt = jt;
> +
> +		if (check_add_overflow(env->cfg.gotox_edges, jt->cnt,
> +				       &env->cfg.gotox_edges) ||
> +		    env->cfg.gotox_edges > BPF_MAX_GOTOX_EDGES) {
> +			verbose(env, "number of indirect jump edges in the program exceeds %u\n",
> +				BPF_MAX_GOTOX_EDGES);
> +			bpf_diag_program_structure(
> +				env, t, "too many indirect jump edges",
> +				"Reduce the number of indirect jumps, or the number of distinct targets they can reach.",
> +				"The program has more than %u indirect jump edges in total, counted over every gotox instruction.",
> +				BPF_MAX_GOTOX_EDGES);
> +			return -E2BIG;
> +		}
>  	}
>  
>  	mark_prune_point(env, t);
> -- 
> 2.43.0

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>

[PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery

[Daniel Borkmann]

create_jt() builds the jump table of the subprogram containing a gotox by
copying out and sorting every insn_array map of the program, and it does
so once per gotox instruction. The cost is therefore the number of gotox
instructions times the number of entries in all of the maps. A program of
4003 instructions with 2000 gotox and one 500k entry map holding two
distinct targets has 4000 indirect jump edges, 0.4% of the limit, and
takes 351s to be rejected. The map costs next to nothing to prepare, as
an unset entry is already a valid target. At the insn limit, with a single
1M entry map, the same shape extrapolates to 43 hours.

All gotox instructions of a subprogram share the same jump table, so
build the table of every subprogram in a single pass over the maps and
hand each gotox a copy of it. Instruction aux data owns its jump table,
see bpf_clear_insn_aux_data(), hence the copy; the copies add up to the
number of indirect jump edges, which visit_gotox_insn() already bounds.

check_cfg() is then linear in the number of map entries plus the number
of indirect jump edges, so what still scales now with the program is what
BPF_MAX_GOTOX_EDGES bounds:

  gotox  map entries  edges     before     after
  ----------------------------------------------
    500       250000   1000     36.55s     0.07s
   1000       250000   2000     75.65s     0.07s
   2000       250000   4000    153.44s     0.07s
   2000       125000   4000     69.61s     0.04s
   2000       500000   4000    351.27s     0.15s

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h |  2 +
 kernel/bpf/cfg.c             | 99 +++++++++++++++++++++++-------------
 2 files changed, 65 insertions(+), 36 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 04bb8f71cabe..301a47d2b272 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -805,6 +805,7 @@ struct bpf_subprog_info {
 	u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
 	u32 postorder_start; /* The idx to the env->cfg.insn_postorder */
 	u32 exit_idx; /* Index of one of the BPF_EXIT instructions in this subprogram */
+	struct bpf_iarray *jt; /* jump table shared by all gotox of this subprogram */
 	u16 stack_depth; /* max. stack depth used by this function */
 	u16 stack_extra;
 	u32 insns_total;
@@ -978,6 +979,7 @@ struct bpf_verifier_env {
 		/* current position in the insn_postorder vector */
 		int cur_postorder;
 		u32 gotox_edges;
+		bool subprog_jts_ready;
 	} cfg;
 	struct backtrack_state bt;
 	struct bpf_jmp_history_entry *cur_hist_ent;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index e9910228da58..8aee94689229 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -286,15 +286,17 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map)
 }
 
 /*
- * Find and collect all maps which fit in the subprog. Return the result as one
- * combined jump table in jt->items (allocated with kvcalloc)
+ * Collect the jump table of every subprogram that has one, as the combined
+ * table of all maps whose targets land inside that subprogram. All gotox
+ * instructions of a subprogram share the same table, so this is done in a
+ * single pass over the maps rather than once per gotox.
  */
-static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
-					  int subprog_start, int subprog_end)
+static int compute_subprog_jts(struct bpf_verifier_env *env)
 {
-	struct bpf_iarray *jt = NULL;
+	struct bpf_subprog_info *subprog;
+	struct bpf_iarray *jt, *jt_cur;
 	struct bpf_map *map;
-	struct bpf_iarray *jt_cur;
+	u32 old_cnt;
 	int i;
 
 	for (i = 0; i < env->insn_array_map_cnt; i++) {
@@ -305,40 +307,47 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
 		map = env->insn_array_maps[i];
 
 		jt_cur = jt_from_map(map);
-		if (IS_ERR(jt_cur)) {
-			kvfree(jt);
-			return jt_cur;
+		if (IS_ERR(jt_cur))
+			return PTR_ERR(jt_cur);
+
+		subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
+		if (!subprog) {
+			kvfree(jt_cur);
+			continue;
 		}
 
-		/*
-		 * This is enough to check one element. The full table is
-		 * checked to fit inside the subprog later in create_jt()
-		 */
-		if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end) {
-			u32 old_cnt = jt ? jt->cnt : 0;
-			jt = bpf_iarray_realloc(jt, old_cnt + jt_cur->cnt);
-			if (!jt) {
-				kvfree(jt_cur);
-				return ERR_PTR(-ENOMEM);
-			}
-			memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
+		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
+		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
+		if (!jt) {
+			subprog->jt = NULL;
+			kvfree(jt_cur);
+			return -ENOMEM;
 		}
+		memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
+		subprog->jt = jt;
 
 		kvfree(jt_cur);
 	}
 
-	if (!jt) {
-		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
-		bpf_diag_program_structure(
-			env, subprog_start, "missing jump table",
-			"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.",
-			"No jump table was found for the subprogram that starts at instruction %u.",
-			subprog_start);
-		return ERR_PTR(-EINVAL);
+	for (i = 0; i < env->subprog_cnt; i++) {
+		jt = env->subprog_info[i].jt;
+		if (jt)
+			jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt);
 	}
 
-	jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt);
-	return jt;
+	env->cfg.subprog_jts_ready = true;
+	return 0;
+}
+
+static void free_subprog_jts(struct bpf_verifier_env *env)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
+		kvfree(env->subprog_info[i].jt);
+		env->subprog_info[i].jt = NULL;
+	}
+	env->cfg.subprog_jts_ready = false;
 }
 
 static struct bpf_iarray *
@@ -347,16 +356,33 @@ create_jt(int t, struct bpf_verifier_env *env)
 	struct bpf_subprog_info *subprog;
 	int subprog_start, subprog_end;
 	struct bpf_iarray *jt;
-	int i;
+	int i, err;
+
+	if (!env->cfg.subprog_jts_ready) {
+		err = compute_subprog_jts(env);
+		if (err)
+			return ERR_PTR(err);
+	}
 
 	subprog = bpf_find_containing_subprog(env, t);
 	subprog_start = subprog->start;
 	subprog_end = (subprog + 1)->start;
-	jt = jt_from_subprog(env, subprog_start, subprog_end);
-	if (IS_ERR(jt))
-		return jt;
 
-	/* Check that the every element of the jump table fits within the given subprogram */
+	if (!subprog->jt) {
+		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
+		bpf_diag_program_structure(
+			env, subprog_start, "missing jump table",
+			"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.",
+			"No jump table was found for the subprogram that starts at instruction %u.",
+			subprog_start);
+		return ERR_PTR(-EINVAL);
+	}
+
+	jt = bpf_iarray_realloc(NULL, subprog->jt->cnt);
+	if (!jt)
+		return ERR_PTR(-ENOMEM);
+	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);
+
 	for (i = 0; i < jt->cnt; i++) {
 		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
 			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
@@ -693,6 +719,7 @@ int bpf_check_cfg(struct bpf_verifier_env *env)
 	env->prog->aux->might_sleep = env->subprog_info[0].might_sleep;
 
 err_free:
+	free_subprog_jts(env);
 	kvfree(insn_state);
 	kvfree(insn_stack);
 	env->cfg.insn_state = env->cfg.insn_stack = NULL;
-- 
2.43.0

Re: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 04bb8f71cabe..301a47d2b272 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -805,6 +805,7 @@ struct bpf_subprog_info {
>  	u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
>  	u32 postorder_start; /* The idx to the env->cfg.insn_postorder */
>  	u32 exit_idx; /* Index of one of the BPF_EXIT instructions in this subprogram */
> +	struct bpf_iarray *jt; /* jump table shared by all gotox of this subprogram */
>  	u16 stack_depth; /* max. stack depth used by this function */
>  	u16 stack_extra;
>  	u32 insns_total;
> @@ -978,6 +979,7 @@ struct bpf_verifier_env {
>  		/* current position in the insn_postorder vector */
>  		int cur_postorder;
>  		u32 gotox_edges;
> +		bool subprog_jts_ready;
>  	} cfg;
>  	struct backtrack_state bt;
>  	struct bpf_jmp_history_entry *cur_hist_ent;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index e9910228da58..8aee94689229 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c

[ ... ]

> @@ -286,15 +286,17 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map)
>  }
>
>  /*
> - * Find and collect all maps which fit in the subprog. Return the result as one
> - * combined jump table in jt->items (allocated with kvcalloc)
> + * Collect the jump table of every subprogram that has one, as the combined
> + * table of all maps whose targets land inside that subprogram. All gotox
> + * instructions of a subprogram share the same table, so this is done in a
> + * single pass over the maps rather than once per gotox.
>   */
> -static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
> -					  int subprog_start, int subprog_end)
> +static int compute_subprog_jts(struct bpf_verifier_env *env)
>  {
> -	struct bpf_iarray *jt = NULL;
> +	struct bpf_subprog_info *subprog;
> +	struct bpf_iarray *jt, *jt_cur;
>  	struct bpf_map *map;
> -	struct bpf_iarray *jt_cur;
> +	u32 old_cnt;
>  	int i;
>
>  	for (i = 0; i < env->insn_array_map_cnt; i++) {
> @@ -305,40 +307,47 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
>  		map = env->insn_array_maps[i];
>
>  		jt_cur = jt_from_map(map);
> -		if (IS_ERR(jt_cur)) {
> -			kvfree(jt);
> -			return jt_cur;
> +		if (IS_ERR(jt_cur))
> +			return PTR_ERR(jt_cur);
> +
> +		subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
> +		if (!subprog) {
> +			kvfree(jt_cur);
> +			continue;
>  		}

Is the block comment above accurate? It states the table is "all maps
whose targets land inside that subprogram", but the code attributes a map
by its first entry only:

    subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);

jt_from_map() sorts and de-duplicates, so items[0] is the map's lowest
target. A map whose lowest target is inside subprogram S but whose
remaining targets reach past (subprog + 1)->start is still merged into
S's table, so S->jt can contain targets that do not land inside S.

This case is not filtered here. The range check that rejects such
programs is in create_jt():

    for (i = 0; i < jt->cnt; i++)
            if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end)
                    ... return ERR_PTR(-EINVAL);

The old code's comment explained why testing a single element is
sufficient: "This is enough to check one element. The full table is
checked to fit inside the subprog later in create_jt()". The comment
above the loop in create_jt() said "Check that the every element of the
jump table fits within the given subprogram". Both are now deleted.

After the patch the one-element rationale appears nowhere in the file,
while the new comment asserts a stronger invariant than the code provides.

Would it be more accurate to say "all maps whose first target lands inside
that subprogram" and keep a note that the full table is validated later in
create_jt()?

In the follow-up commit e47f26bec05f ("bpf: Reject indirect jumps that
leave their subprogram"), the code is changed to match what this comment
already claims. The mismatch exists only at this commit.

> -		/*
> -		 * This is enough to check one element. The full table is
> -		 * checked to fit inside the subprog later in create_jt()
> -		 */
> -		if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end) {
> -			u32 old_cnt = jt ? jt->cnt : 0;
> -			jt = bpf_iarray_realloc(jt, old_cnt + jt_cur->cnt);
> -			if (!jt) {
> -				kvfree(jt_cur);
> -				return ERR_PTR(-ENOMEM);
> -			}
> -			memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> +		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
> +		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
> +		if (!jt) {
> +			subprog->jt = NULL;
> +			kvfree(jt_cur);
> +			return -ENOMEM;
>  		}
> +		memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> +		subprog->jt = jt;
>
>  		kvfree(jt_cur);
>  	}

[ ... ]

> @@ -693,6 +719,7 @@ int bpf_check_cfg(struct bpf_verifier_env *env)
>  	env->prog->aux->might_sleep = env->subprog_info[0].might_sleep;
>
>  err_free:
> +	free_subprog_jts(env);
>  	kvfree(insn_state);
>  	kvfree(insn_stack);
>  	env->cfg.insn_state = env->cfg.insn_stack = NULL;


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34404843294

Re: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery

[Daniel Borkmann]

On 9/9/26 11:34 PM, bot+bpf-ci@kernel.org wrote:
[...]
> In the follow-up commit e47f26bec05f ("bpf: Reject indirect jumps that
> leave their subprogram"), the code is changed to match what this comment
> already claims. The mismatch exists only at this commit.

Ok, then, will leave as-is unless there is a reason to spin a v2..

Re: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery

[Anton Protopopov]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> create_jt() builds the jump table of the subprogram containing a gotox by
> copying out and sorting every insn_array map of the program, and it does
> so once per gotox instruction. The cost is therefore the number of gotox
> instructions times the number of entries in all of the maps. A program of
> 4003 instructions with 2000 gotox and one 500k entry map holding two
> distinct targets has 4000 indirect jump edges, 0.4% of the limit, and
> takes 351s to be rejected. The map costs next to nothing to prepare, as
> an unset entry is already a valid target. At the insn limit, with a single
> 1M entry map, the same shape extrapolates to 43 hours.
> 
> All gotox instructions of a subprogram share the same jump table, so
> build the table of every subprogram in a single pass over the maps and
> hand each gotox a copy of it. Instruction aux data owns its jump table,
> see bpf_clear_insn_aux_data(), hence the copy; the copies add up to the
> number of indirect jump edges, which visit_gotox_insn() already bounds.
> 
> check_cfg() is then linear in the number of map entries plus the number
> of indirect jump edges, so what still scales now with the program is what
> BPF_MAX_GOTOX_EDGES bounds:
> 
>   gotox  map entries  edges     before     after
>   ----------------------------------------------
>     500       250000   1000     36.55s     0.07s
>    1000       250000   2000     75.65s     0.07s
>    2000       250000   4000    153.44s     0.07s
>    2000       125000   4000     69.61s     0.04s
>    2000       500000   4000    351.27s     0.15s
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  include/linux/bpf_verifier.h |  2 +
>  kernel/bpf/cfg.c             | 99 +++++++++++++++++++++++-------------
>  2 files changed, 65 insertions(+), 36 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 04bb8f71cabe..301a47d2b272 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -805,6 +805,7 @@ struct bpf_subprog_info {
>  	u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
>  	u32 postorder_start; /* The idx to the env->cfg.insn_postorder */
>  	u32 exit_idx; /* Index of one of the BPF_EXIT instructions in this subprogram */
> +	struct bpf_iarray *jt; /* jump table shared by all gotox of this subprogram */
>  	u16 stack_depth; /* max. stack depth used by this function */
>  	u16 stack_extra;
>  	u32 insns_total;
> @@ -978,6 +979,7 @@ struct bpf_verifier_env {
>  		/* current position in the insn_postorder vector */
>  		int cur_postorder;
>  		u32 gotox_edges;
> +		bool subprog_jts_ready;
>  	} cfg;
>  	struct backtrack_state bt;
>  	struct bpf_jmp_history_entry *cur_hist_ent;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index e9910228da58..8aee94689229 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -286,15 +286,17 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map)
>  }
>  
>  /*
> - * Find and collect all maps which fit in the subprog. Return the result as one
> - * combined jump table in jt->items (allocated with kvcalloc)
> + * Collect the jump table of every subprogram that has one, as the combined
> + * table of all maps whose targets land inside that subprogram. All gotox
> + * instructions of a subprogram share the same table, so this is done in a
> + * single pass over the maps rather than once per gotox.
>   */
> -static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
> -					  int subprog_start, int subprog_end)
> +static int compute_subprog_jts(struct bpf_verifier_env *env)
>  {
> -	struct bpf_iarray *jt = NULL;
> +	struct bpf_subprog_info *subprog;
> +	struct bpf_iarray *jt, *jt_cur;
>  	struct bpf_map *map;
> -	struct bpf_iarray *jt_cur;
> +	u32 old_cnt;
>  	int i;
>  
>  	for (i = 0; i < env->insn_array_map_cnt; i++) {
> @@ -305,40 +307,47 @@ static struct bpf_iarray *jt_from_subprog(struct bpf_verifier_env *env,
>  		map = env->insn_array_maps[i];
>  
>  		jt_cur = jt_from_map(map);
> -		if (IS_ERR(jt_cur)) {
> -			kvfree(jt);
> -			return jt_cur;
> +		if (IS_ERR(jt_cur))
> +			return PTR_ERR(jt_cur);
> +
> +		subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
> +		if (!subprog) {
> +			kvfree(jt_cur);
> +			continue;
>  		}
>  
> -		/*
> -		 * This is enough to check one element. The full table is
> -		 * checked to fit inside the subprog later in create_jt()
> -		 */
> -		if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end) {
> -			u32 old_cnt = jt ? jt->cnt : 0;
> -			jt = bpf_iarray_realloc(jt, old_cnt + jt_cur->cnt);
> -			if (!jt) {
> -				kvfree(jt_cur);
> -				return ERR_PTR(-ENOMEM);
> -			}
> -			memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> +		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
> +		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
> +		if (!jt) {
> +			subprog->jt = NULL;
> +			kvfree(jt_cur);
> +			return -ENOMEM;
>  		}
> +		memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> +		subprog->jt = jt;
>  
>  		kvfree(jt_cur);
>  	}
>  
> -	if (!jt) {
> -		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
> -		bpf_diag_program_structure(
> -			env, subprog_start, "missing jump table",
> -			"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.",
> -			"No jump table was found for the subprogram that starts at instruction %u.",
> -			subprog_start);
> -		return ERR_PTR(-EINVAL);
> +	for (i = 0; i < env->subprog_cnt; i++) {
> +		jt = env->subprog_info[i].jt;
> +		if (jt)
> +			jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt);
>  	}
>  
> -	jt->cnt = sort_insn_array_uniq(jt->items, jt->cnt);
> -	return jt;
> +	env->cfg.subprog_jts_ready = true;
> +	return 0;
> +}
> +
> +static void free_subprog_jts(struct bpf_verifier_env *env)
> +{
> +	int i;
> +
> +	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
> +		kvfree(env->subprog_info[i].jt);
> +		env->subprog_info[i].jt = NULL;
> +	}
> +	env->cfg.subprog_jts_ready = false;
>  }
>  
>  static struct bpf_iarray *
> @@ -347,16 +356,33 @@ create_jt(int t, struct bpf_verifier_env *env)
>  	struct bpf_subprog_info *subprog;
>  	int subprog_start, subprog_end;
>  	struct bpf_iarray *jt;
> -	int i;
> +	int i, err;
> +
> +	if (!env->cfg.subprog_jts_ready) {
> +		err = compute_subprog_jts(env);
> +		if (err)
> +			return ERR_PTR(err);
> +	}
>  
>  	subprog = bpf_find_containing_subprog(env, t);
>  	subprog_start = subprog->start;
>  	subprog_end = (subprog + 1)->start;
> -	jt = jt_from_subprog(env, subprog_start, subprog_end);
> -	if (IS_ERR(jt))
> -		return jt;
>  
> -	/* Check that the every element of the jump table fits within the given subprogram */
> +	if (!subprog->jt) {
> +		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
> +		bpf_diag_program_structure(
> +			env, subprog_start, "missing jump table",
> +			"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.",
> +			"No jump table was found for the subprogram that starts at instruction %u.",
> +			subprog_start);
> +		return ERR_PTR(-EINVAL);
> +	}
> +
> +	jt = bpf_iarray_realloc(NULL, subprog->jt->cnt);
> +	if (!jt)
> +		return ERR_PTR(-ENOMEM);
> +	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);
> +
>  	for (i = 0; i < jt->cnt; i++) {
>  		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
>  			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
> @@ -693,6 +719,7 @@ int bpf_check_cfg(struct bpf_verifier_env *env)
>  	env->prog->aux->might_sleep = env->subprog_info[0].might_sleep;
>  
>  err_free:
> +	free_subprog_jts(env);
>  	kvfree(insn_state);
>  	kvfree(insn_stack);
>  	env->cfg.insn_state = env->cfg.insn_stack = NULL;
> -- 
> 2.43.0
> 

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>

Re: [PATCH bpf 3/6] bpf: Cache the jump table of a subprogram during CFG discovery

[Eduard Zingerman]

On Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:

...

> @@ -347,16 +356,33 @@ create_jt(int t, struct bpf_verifier_env *env)
>  	struct bpf_subprog_info *subprog;
>  	int subprog_start, subprog_end;
>  	struct bpf_iarray *jt;
> -	int i;
> +	int i, err;
> +
> +	if (!env->cfg.subprog_jts_ready) {
> +		err = compute_subprog_jts(env);
> +		if (err)
> +			return ERR_PTR(err);
> +	}
>  
>  	subprog = bpf_find_containing_subprog(env, t);
>  	subprog_start = subprog->start;
>  	subprog_end = (subprog + 1)->start;
> -	jt = jt_from_subprog(env, subprog_start, subprog_end);
> -	if (IS_ERR(jt))
> -		return jt;
>  
> -	/* Check that the every element of the jump table fits within the given subprogram */
> +	if (!subprog->jt) {
> +		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
> +		bpf_diag_program_structure(
> +			env, subprog_start, "missing jump table",
> +			"Make sure subprograms containing gotox instructions are accompanied by jump tables referencing these subprograms.",
> +			"No jump table was found for the subprogram that starts at instruction %u.",
> +			subprog_start);
> +		return ERR_PTR(-EINVAL);
> +	}
> +
> +	jt = bpf_iarray_realloc(NULL, subprog->jt->cnt);
> +	if (!jt)
> +		return ERR_PTR(-ENOMEM);
> +	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);

What would it take to change the logic such that insn_aux_data no
longer owns the memory? (Thus making the copy unnecessary).

> +
>  	for (i = 0; i < jt->cnt; i++) {
>  		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
>  			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",

...

[PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram

[Daniel Borkmann]

The jump table of a subprog is collected in compute_subprog_jts() from the
insn_array maps of the program, and a map is attributed to the subprog that
contains its first entry. check_indirect_jump() instead resolves the targets
from the map the gotox register actually points to, bounded only by the
index range of that register, and never relates them back to the subprog
of the gotox.

The two disagree, so bpf_insn_successors() reports a subset of the edges the
BPF program can take and a gotox can enter a subprog the CFG never walked.
The x86 epilogue there pops the callee saved registers of its own subprog and
leaves the ones pushed by the current prologue unrestored, handing rbx, r13,
r14 and r15 to the kernel with the values the BPF program left in them.

Close both ends in check_indirect_jump(): confine the resolved targets to the
subprog of the gotox, and require each of them to be present in the jump table
the CFG walked, that is, in the successor set bpf_insn_successors() reported
for this instruction. The latter is the invariant that actually has to hold,
the former is kept because it names the problem the BPF program has.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: James Burton <jamesburton@meta.com>
Reported-by: Nuoqi Gui <gnq25@mails.tsinghua.edu.cn>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h                  |  1 +
 kernel/bpf/cfg.c                              | 35 +++++-----
 kernel/bpf/verifier.c                         | 65 +++++++++++++++++++
 .../selftests/bpf/progs/verifier_gotox.c      |  2 +-
 4 files changed, 85 insertions(+), 18 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 301a47d2b272..baf2e17d7019 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -826,6 +826,7 @@ struct bpf_subprog_info {
 	bool keep_fastcall_stack: 1;
 	bool changes_pkt_data: 1;
 	bool might_sleep: 1;
+	bool jt_spans_subprogs: 1;
 	u8 arg_cnt:4;
 
 	enum priv_stack_mode priv_stack_mode;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 8aee94689229..879587af8d08 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)
 			kvfree(jt_cur);
 			continue;
 		}
+		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
+			subprog->jt_spans_subprogs = true;
+			kvfree(jt_cur);
+			continue;
+		}
 
 		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
 		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
@@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)
 	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
 		kvfree(env->subprog_info[i].jt);
 		env->subprog_info[i].jt = NULL;
+		env->subprog_info[i].jt_spans_subprogs = false;
 	}
 	env->cfg.subprog_jts_ready = false;
 }
@@ -354,9 +360,8 @@ static struct bpf_iarray *
 create_jt(int t, struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprog;
-	int subprog_start, subprog_end;
 	struct bpf_iarray *jt;
-	int i, err;
+	int subprog_start, err;
 
 	if (!env->cfg.subprog_jts_ready) {
 		err = compute_subprog_jts(env);
@@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env)
 
 	subprog = bpf_find_containing_subprog(env, t);
 	subprog_start = subprog->start;
-	subprog_end = (subprog + 1)->start;
+
+	if (subprog->jt_spans_subprogs) {
+		verbose(env, "jump table of subprog starting at %u spans multiple subprogs\n",
+			subprog_start);
+		bpf_diag_program_structure(
+			env, subprog_start, "jump table spans subprograms",
+			"Keep every entry of a jump table inside one subprogram.",
+			"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u.",
+			subprog_start, (subprog + 1)->start);
+		return ERR_PTR(-EINVAL);
+	}
 
 	if (!subprog->jt) {
 		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
@@ -383,20 +398,6 @@ create_jt(int t, struct bpf_verifier_env *env)
 		return ERR_PTR(-ENOMEM);
 	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);
 
-	for (i = 0; i < jt->cnt; i++) {
-		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
-			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
-					t, subprog_start, subprog_end);
-			bpf_diag_program_structure(
-				env, t, "jump table target out of range",
-				"Keep every jump-table target inside the same subprogram.",
-				"The jump table for instruction %d points outside subprogram range [%u,%u).",
-				t, subprog_start, subprog_end);
-			kvfree(jt);
-			return ERR_PTR(-EINVAL);
-		}
-	}
-
 	return jt;
 }
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 72a3f5998dd2..45234e2fbee6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
 	return 0;
 }
 
+/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */
+static bool jt_contains(const struct bpf_iarray *jt, u32 target)
+{
+	int l = 0, r = jt->cnt - 1, m;
+
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		if (jt->items[m] == target)
+			return true;
+		if (jt->items[m] < target)
+			l = m + 1;
+		else
+			r = m - 1;
+	}
+	return false;
+}
+
+static int reject_gotox_out_of_subprog(struct bpf_verifier_env *env, u32 target,
+				       u32 subprog_start, u32 subprog_end)
+{
+	verbose(env, "indirect jump from insn %d to %u leaves the subprog [%u,%u)\n",
+		     env->insn_idx, target, subprog_start, subprog_end);
+	bpf_diag_program_structure(
+		env, env->insn_idx, "indirect jump leaves subprogram",
+		"Keep every reachable jump-table target inside the subprogram of the indirect jump.",
+		"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u).",
+		env->insn_idx, target, subprog_start, subprog_end);
+	return -EINVAL;
+}
+
+static int reject_gotox_without_cfg_edge(struct bpf_verifier_env *env, u32 target)
+{
+	verbose(env, "indirect jump from insn %d to %u is not in the jump table of the subprog\n",
+		     env->insn_idx, target);
+	bpf_diag_program_structure(
+		env, env->insn_idx, "indirect jump target without CFG edge",
+		"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump.",
+		"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram.",
+		env->insn_idx, target);
+	return -EINVAL;
+}
+
 /* gotox *dst_reg */
 static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
 	struct bpf_verifier_state *other_branch;
+	struct bpf_subprog_info *subprog;
+	u32 subprog_start, subprog_end;
 	struct bpf_reg_state *dst_reg;
+	struct bpf_iarray *jt;
 	struct bpf_map *map;
 	u32 min_index, max_index;
 	int err = 0;
@@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
 		return -EINVAL;
 	}
 
+	subprog = bpf_find_containing_subprog(env, env->insn_idx);
+	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", env->insn_idx))
+		return -EFAULT;
+	subprog_start = subprog->start;
+	subprog_end = (subprog + 1)->start;
+
+	jt = env->insn_aux_data[env->insn_idx].jt;
+	if (verifier_bug_if(!jt, env, "no jump table for insn %d", env->insn_idx))
+		return -EFAULT;
+
+	for (i = 0; i < n; i++) {
+		u32 target = env->gotox_tmp_buf->items[i];
+
+		if (target < subprog_start || target >= subprog_end)
+			return reject_gotox_out_of_subprog(env, target, subprog_start,
+							   subprog_end);
+		if (!jt_contains(jt, target))
+			return reject_gotox_without_cfg_edge(env, target);
+	}
+
 	for (i = 0; i < n - 1; i++) {
 		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
 		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
index 5b18c9a27717..3567b29e2378 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -318,7 +318,7 @@ __used static int test_subprog(void)
 }
 
 SEC("socket")
-__failure __msg("jump table for insn 4 points outside of the subprog [0,10]")
+__failure __msg("jump table of subprog starting at 0 spans multiple subprogs")
 __naked void jump_table_outside_subprog(void)
 {
 	asm volatile ("						\
-- 
2.43.0

Re: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 301a47d2b272..baf2e17d7019 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -826,6 +826,7 @@ struct bpf_subprog_info {
>  	bool keep_fastcall_stack: 1;
>  	bool changes_pkt_data: 1;
>  	bool might_sleep: 1;
> +	bool jt_spans_subprogs: 1;
>  	u8 arg_cnt:4;
>
>  	enum priv_stack_mode priv_stack_mode;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 8aee94689229..879587af8d08 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)
>  			kvfree(jt_cur);
>  			continue;
>  		}
> +		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
> +			subprog->jt_spans_subprogs = true;
> +			kvfree(jt_cur);
> +			continue;
> +		}
>
>  		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
>  		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
> @@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)
>  	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
>  		kvfree(env->subprog_info[i].jt);
>  		env->subprog_info[i].jt = NULL;
> +		env->subprog_info[i].jt_spans_subprogs = false;
>  	}
>  	env->cfg.subprog_jts_ready = false;
>  }
> @@ -354,9 +360,8 @@ static struct bpf_iarray *
>  create_jt(int t, struct bpf_verifier_env *env)
>  {
>  	struct bpf_subprog_info *subprog;
> -	int subprog_start, subprog_end;
>  	struct bpf_iarray *jt;
> -	int i, err;
> +	int subprog_start, err;
>
>  	if (!env->cfg.subprog_jts_ready) {
>  		err = compute_subprog_jts(env);
> @@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env)
>
>  	subprog = bpf_find_containing_subprog(env, t);
>  	subprog_start = subprog->start;
> -	subprog_end = (subprog + 1)->start;
> +
> +	if (subprog->jt_spans_subprogs) {
> +		verbose(env, "jump table of subprog starting at %u spans multiple subprogs\n",
> +			subprog_start);
> +		bpf_diag_program_structure(
> +			env, subprog_start, "jump table spans subprograms",
> +			"Keep every entry of a jump table inside one subprogram.",
> +			"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u.",
> +			subprog_start, (subprog + 1)->start);
> +		return ERR_PTR(-EINVAL);
> +	}

This isn't a bug, but since the cfg.c restructure appears to accept and
reject the same programs as before (the new items[jt_cur->cnt - 1] >=
(subprog + 1)->start test in compute_subprog_jts() accepts exactly the same
set of maps as the removed per-entry loop in create_jt()), would it be
cleaner to keep this Fixes-tagged patch to the check_indirect_jump() hunks
and send the jt_spans_subprogs refactor plus message rename as a separate
cleanup?

The functional security fix lives entirely in check_indirect_jump(), while
the cfg.c changes only modify the diagnostic wording and timing.

> [ ... ]
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 72a3f5998dd2..45234e2fbee6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
>  	return 0;
>  }
>
> +/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */
> +static bool jt_contains(const struct bpf_iarray *jt, u32 target)
> +{
> +	int l = 0, r = jt->cnt - 1, m;
> +
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		if (jt->items[m] == target)
> +			return true;
> +		if (jt->items[m] < target)
> +			l = m + 1;
> +		else
> +			r = m - 1;
> +	}
> +	return false;
> +}
> +
> +static int reject_gotox_out_of_subprog(struct bpf_verifier_env *env, u32 target,
> +				       u32 subprog_start, u32 subprog_end)
> +{
> +	verbose(env, "indirect jump from insn %d to %u leaves the subprog [%u,%u)\n",
> +		     env->insn_idx, target, subprog_start, subprog_end);
> +	bpf_diag_program_structure(
> +		env, env->insn_idx, "indirect jump leaves subprogram",
> +		"Keep every reachable jump-table target inside the subprogram of the indirect jump.",
> +		"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u).",
> +		env->insn_idx, target, subprog_start, subprog_end);
> +	return -EINVAL;
> +}
> +
> +static int reject_gotox_without_cfg_edge(struct bpf_verifier_env *env, u32 target)
> +{
> +	verbose(env, "indirect jump from insn %d to %u is not in the jump table of the subprog\n",
> +		     env->insn_idx, target);
> +	bpf_diag_program_structure(
> +		env, env->insn_idx, "indirect jump target without CFG edge",
> +		"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump.",
> +		"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram.",
> +		env->insn_idx, target);
> +	return -EINVAL;
> +}
> +
>  /* gotox *dst_reg */
>  static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  {
>  	struct bpf_verifier_state *other_branch;
> +	struct bpf_subprog_info *subprog;
> +	u32 subprog_start, subprog_end;
>  	struct bpf_reg_state *dst_reg;
> +	struct bpf_iarray *jt;
>  	struct bpf_map *map;
>  	u32 min_index, max_index;
>  	int err = 0;
> @@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
>  		return -EINVAL;
>  	}
>
> +	subprog = bpf_find_containing_subprog(env, env->insn_idx);
> +	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", env->insn_idx))
> +		return -EFAULT;
> +	subprog_start = subprog->start;
> +	subprog_end = (subprog + 1)->start;
> +
> +	jt = env->insn_aux_data[env->insn_idx].jt;
> +	if (verifier_bug_if(!jt, env, "no jump table for insn %d", env->insn_idx))
> +		return -EFAULT;
> +
> +	for (i = 0; i < n; i++) {
> +		u32 target = env->gotox_tmp_buf->items[i];
> +
> +		if (target < subprog_start || target >= subprog_end)
> +			return reject_gotox_out_of_subprog(env, target, subprog_start,
> +							   subprog_end);
> +		if (!jt_contains(jt, target))
> +			return reject_gotox_without_cfg_edge(env, target);
> +	}
> +
>  	for (i = 0; i < n - 1; i++) {
>  		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
>  		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],

This isn't a bug, but would it be worth a sentence in the changelog about
the cfg.c side (the new jt_spans_subprogs bit and the renamed verifier
message), so readers of the log know why verifier_gotox.c's __msg had to
change?

The changelog describes only the kernel/bpf/verifier.c half of the diff,
but the patch also changes kernel/bpf/cfg.c: it moves the 'jump table
entry outside the subprog' detection from a per-entry loop in create_jt()
into a per-map maximum test in compute_subprog_jts(), and replaces the old
per-entry rejection with an early flag test in create_jt(). That rewrite
changes the user-visible verifier message from 'jump table for insn %d
points outside of the subprog [%u,%u]' to 'jump table of subprog starting
at %u spans multiple subprogs'.

> diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
> index 5b18c9a27717..3567b29e2378 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
> @@ -318,7 +318,7 @@ __used static int test_subprog(void)
>  }
>
>  SEC("socket")
> -__failure __msg("jump table for insn 4 points outside of the subprog [0,10]")
> +__failure __msg("jump table of subprog starting at 0 spans multiple subprogs")
>  __naked void jump_table_outside_subprog(void)
>  {
>  	asm volatile ("						\


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34404843294

Re: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram

[Anton Protopopov]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> The jump table of a subprog is collected in compute_subprog_jts() from the
> insn_array maps of the program, and a map is attributed to the subprog that
> contains its first entry. check_indirect_jump() instead resolves the targets
> from the map the gotox register actually points to, bounded only by the
> index range of that register, and never relates them back to the subprog
> of the gotox.
> 
> The two disagree, so bpf_insn_successors() reports a subset of the edges the
> BPF program can take and a gotox can enter a subprog the CFG never walked.
> The x86 epilogue there pops the callee saved registers of its own subprog and
> leaves the ones pushed by the current prologue unrestored, handing rbx, r13,
> r14 and r15 to the kernel with the values the BPF program left in them.

Why only x86? Maybe just remove the three lines above?

> 
> Close both ends in check_indirect_jump(): confine the resolved targets to the
> subprog of the gotox, and require each of them to be present in the jump table
> the CFG walked, that is, in the successor set bpf_insn_successors() reported
> for this instruction. The latter is the invariant that actually has to hold,
> the former is kept because it names the problem the BPF program has.
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Reported-by: James Burton <jamesburton@meta.com>
> Reported-by: Nuoqi Gui <gnq25@mails.tsinghua.edu.cn>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  include/linux/bpf_verifier.h                  |  1 +
>  kernel/bpf/cfg.c                              | 35 +++++-----
>  kernel/bpf/verifier.c                         | 65 +++++++++++++++++++
>  .../selftests/bpf/progs/verifier_gotox.c      |  2 +-
>  4 files changed, 85 insertions(+), 18 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 301a47d2b272..baf2e17d7019 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -826,6 +826,7 @@ struct bpf_subprog_info {
>  	bool keep_fastcall_stack: 1;
>  	bool changes_pkt_data: 1;
>  	bool might_sleep: 1;
> +	bool jt_spans_subprogs: 1;
>  	u8 arg_cnt:4;
>  
>  	enum priv_stack_mode priv_stack_mode;
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 8aee94689229..879587af8d08 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)
>  			kvfree(jt_cur);
>  			continue;
>  		}
> +		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
> +			subprog->jt_spans_subprogs = true;
> +			kvfree(jt_cur);
> +			continue;
> +		}
>  
>  		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
>  		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
> @@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)
>  	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
>  		kvfree(env->subprog_info[i].jt);
>  		env->subprog_info[i].jt = NULL;
> +		env->subprog_info[i].jt_spans_subprogs = false;
>  	}
>  	env->cfg.subprog_jts_ready = false;
>  }
> @@ -354,9 +360,8 @@ static struct bpf_iarray *
>  create_jt(int t, struct bpf_verifier_env *env)
>  {
>  	struct bpf_subprog_info *subprog;
> -	int subprog_start, subprog_end;
>  	struct bpf_iarray *jt;
> -	int i, err;
> +	int subprog_start, err;
>  
>  	if (!env->cfg.subprog_jts_ready) {
>  		err = compute_subprog_jts(env);
> @@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env)
>  
>  	subprog = bpf_find_containing_subprog(env, t);
>  	subprog_start = subprog->start;
> -	subprog_end = (subprog + 1)->start;
> +
> +	if (subprog->jt_spans_subprogs) {
> +		verbose(env, "jump table of subprog starting at %u spans multiple subprogs\n",
> +			subprog_start);
> +		bpf_diag_program_structure(
> +			env, subprog_start, "jump table spans subprograms",
> +			"Keep every entry of a jump table inside one subprogram.",
> +			"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u.",
> +			subprog_start, (subprog + 1)->start);
> +		return ERR_PTR(-EINVAL);
> +	}
>  	if (!subprog->jt) {
>  		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
> @@ -383,20 +398,6 @@ create_jt(int t, struct bpf_verifier_env *env)
>  		return ERR_PTR(-ENOMEM);
>  	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);
>  
> -	for (i = 0; i < jt->cnt; i++) {
> -		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
> -			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
> -					t, subprog_start, subprog_end);
> -			bpf_diag_program_structure(
> -				env, t, "jump table target out of range",
> -				"Keep every jump-table target inside the same subprogram.",
> -				"The jump table for instruction %d points outside subprogram range [%u,%u).",
> -				t, subprog_start, subprog_end);
> -			kvfree(jt);
> -			return ERR_PTR(-EINVAL);
> -		}
> -	}
> -
>  	return jt;
>  }
>  
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 72a3f5998dd2..45234e2fbee6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
>  	return 0;
>  }
>  
> +/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */
> +static bool jt_contains(const struct bpf_iarray *jt, u32 target)
> +{
> +	int l = 0, r = jt->cnt - 1, m;
> +
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		if (jt->items[m] == target)
> +			return true;
> +		if (jt->items[m] < target)
> +			l = m + 1;
> +		else
> +			r = m - 1;
> +	}
> +	return false;
> +}
> +
> +static int reject_gotox_out_of_subprog(struct bpf_verifier_env *env, u32 target,
> +				       u32 subprog_start, u32 subprog_end)
> +{
> +	verbose(env, "indirect jump from insn %d to %u leaves the subprog [%u,%u)\n",
> +		     env->insn_idx, target, subprog_start, subprog_end);
> +	bpf_diag_program_structure(
> +		env, env->insn_idx, "indirect jump leaves subprogram",
> +		"Keep every reachable jump-table target inside the subprogram of the indirect jump.",
> +		"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u).",
> +		env->insn_idx, target, subprog_start, subprog_end);
> +	return -EINVAL;
> +}
> +
> +static int reject_gotox_without_cfg_edge(struct bpf_verifier_env *env, u32 target)
> +{
> +	verbose(env, "indirect jump from insn %d to %u is not in the jump table of the subprog\n",
> +		     env->insn_idx, target);
> +	bpf_diag_program_structure(
> +		env, env->insn_idx, "indirect jump target without CFG edge",
> +		"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump.",
> +		"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram.",
> +		env->insn_idx, target);
> +	return -EINVAL;
> +}
> +
>  /* gotox *dst_reg */
>  static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  {
>  	struct bpf_verifier_state *other_branch;
> +	struct bpf_subprog_info *subprog;
> +	u32 subprog_start, subprog_end;
>  	struct bpf_reg_state *dst_reg;
> +	struct bpf_iarray *jt;
>  	struct bpf_map *map;
>  	u32 min_index, max_index;
>  	int err = 0;
> @@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
>  		return -EINVAL;
>  	}
>  
> +	subprog = bpf_find_containing_subprog(env, env->insn_idx);
> +	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", env->insn_idx))
> +		return -EFAULT;
> +	subprog_start = subprog->start;
> +	subprog_end = (subprog + 1)->start;
> +
> +	jt = env->insn_aux_data[env->insn_idx].jt;
> +	if (verifier_bug_if(!jt, env, "no jump table for insn %d", env->insn_idx))
> +		return -EFAULT;
> +
> +	for (i = 0; i < n; i++) {

The items[] is sorted. Is this enough to just check 0-th and (n-1)-th elements?

> +		u32 target = env->gotox_tmp_buf->items[i];
> +
> +		if (target < subprog_start || target >= subprog_end)
> +			return reject_gotox_out_of_subprog(env, target, subprog_start,
> +							   subprog_end);
> +		if (!jt_contains(jt, target))
> +			return reject_gotox_without_cfg_edge(env, target);

Ah, I see, all elements should be checked because this check was added.

> +	}
> +
>  	for (i = 0; i < n - 1; i++) {
>  		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
>  		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
> diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
> index 5b18c9a27717..3567b29e2378 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
> @@ -318,7 +318,7 @@ __used static int test_subprog(void)
>  }
>  
>  SEC("socket")
> -__failure __msg("jump table for insn 4 points outside of the subprog [0,10]")
> +__failure __msg("jump table of subprog starting at 0 spans multiple subprogs")
>  __naked void jump_table_outside_subprog(void)
>  {
>  	asm volatile ("						\
> -- 
> 2.43.0

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>

Re: [PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram

[Eduard Zingerman]

On Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:

...

> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 8aee94689229..879587af8d08 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)
>  			kvfree(jt_cur);
>  			continue;
>  		}
> +		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
> +			subprog->jt_spans_subprogs = true;

This is a single place where the flag is set, why not report an error
here and drop the flag altogether?

> +			kvfree(jt_cur);
> +			continue;
> +		}
>  
>  		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
>  		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);

...

[PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit

[Daniel Borkmann]

Build programs whose gotox instructions are their own jump table targets,
which makes the edge count quadratic.

  # 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>
---
 .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++
 1 file changed, 266 insertions(+)

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 0222a9a5d076..c69d44cd4607 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
@@ -453,6 +453,263 @@ 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 exit block 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(struct bpf_insn *insns, __u32 insn_cnt,
+			   int *fd_array, __u32 fd_array_cnt, char *log)
+{
+	LIBBPF_OPTS(bpf_prog_load_opts, opts);
+	int prog_fd;
+
+	log[0] = 0;
+	opts.fd_array = fd_array;
+	opts.fd_array_cnt = fd_array_cnt;
+	opts.log_buf = log;
+	opts.log_size = GOTOX_LOG_SZ;
+	opts.log_level = 1;
+
+	prog_fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
+	if (prog_fd >= 0) {
+		close(prog_fd);
+		return 0;
+	}
+	return prog_fd;
+}
+
+/* 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 void check_bpf_side(void)
 {
 	check_bpf_no_lookup();
@@ -490,6 +747,15 @@ static void __test_bpf_insn_array(void)
 
 	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();
 }
 #else
 static void __test_bpf_insn_array(void)
-- 
2.43.0

Re: [PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit

[bot+bpf-ci]

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

> selftests/bpf: Add tests for the indirect jump edge limit
>
> Build programs whose gotox instructions are their own jump table targets,
> which makes the edge count quadratic.

The one-sentence body describes the construction used by only two of the
three subtests this patch registers, and it is wrong for the third.

'gotox instructions are their own jump table targets' is accurate for
check_too_many_gotox_edges() and check_gotox_edges_across_subprogs(),
which both build their tables with gotox_jt_create(first_gotox, gotox_cnt)
over 'first_gotox + i' while gotox_run_fill() places the gotox run at
exactly those offsets:

    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);

It is not accurate for check_gotox_edges_at_limit(), which uses the
unrelated chained-block construction in gotox_chain_fill() and
gotox_chain_jt_create(). There, block k occupies insns[k * GOTOX_BLOCK_SZ
.. k * GOTOX_BLOCK_SZ + 3] with the gotox at k * 4 + 3, while the
jump-table entries are

    val.orig_off = (i + 1) * GOTOX_BLOCK_SZ;

i.e. 4, 8, ... 4000 - the BPF_LD_IMM64 at the head of each block. The
target set {4, 8, ...} and the gotox set {3, 7, ...} are disjoint, so no
gotox is its own jump-table target in that test.

The at-limit test also carries the load-bearing detail that the changelog
omits entirely: it sits at exactly BPF_MAX_GOTOX_EDGES (1000 gotox x 1000
entries == 1000000) and must still load, which is what pins the 'greater
than' rather than 'greater or equal' comparison in visit_gotox_insn().
Likewise the third subtest's point - that env->cfg.gotox_edges accumulates
across subprograms rather than per-subprogram - is not mentioned.

Could the changelog be generalized (e.g. 'build programs with quadratic
gotox edge counts') or expanded with a clause for the chained at-limit
case and the cross-subprog accumulation, so it matches what the three
subtests actually construct?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34404843294

Re: [PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit

[Anton Protopopov]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> Build programs whose gotox instructions are their own jump table targets,
> which makes the edge count quadratic.
> 
>   # 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>
> ---
>  .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++
>  1 file changed, 266 insertions(+)
> 
> 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 0222a9a5d076..c69d44cd4607 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> @@ -453,6 +453,263 @@ 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 exit block 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(struct bpf_insn *insns, __u32 insn_cnt,
> +			   int *fd_array, __u32 fd_array_cnt, char *log)
> +{
> +	LIBBPF_OPTS(bpf_prog_load_opts, opts);
> +	int prog_fd;
> +
> +	log[0] = 0;
> +	opts.fd_array = fd_array;
> +	opts.fd_array_cnt = fd_array_cnt;
> +	opts.log_buf = log;
> +	opts.log_size = GOTOX_LOG_SZ;
> +	opts.log_level = 1;
> +
> +	prog_fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
> +	if (prog_fd >= 0) {
> +		close(prog_fd);
> +		return 0;
> +	}
> +	return prog_fd;
> +}
> +
> +/* 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 void check_bpf_side(void)
>  {
>  	check_bpf_no_lookup();
> @@ -490,6 +747,15 @@ static void __test_bpf_insn_array(void)
>  
>  	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();
>  }
>  #else
>  static void __test_bpf_insn_array(void)
> -- 
> 2.43.0
> 

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>

[PATCH bpf 6/6] selftests/bpf: Add tests for indirect jumps across subprograms

[Daniel Borkmann]

Add various gotox corner case tests to improve corner case coverage.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
      ./test_progs -t bpf_insn_array,verifier_gotox,signed_loader
  [...]
  #24/13   bpf_insn_array/gotox-tracker-map:OK
  #24/14   bpf_insn_array/gotox-jt-spans-subprogs:OK
  #24/15   bpf_insn_array/gotox-jt-spans-with-own-table:OK
  #24/16   bpf_insn_array/gotox-target-without-cfg-edge:OK
  #24/17   bpf_insn_array/gotox-target-other-subprog:OK
  #24/18   bpf_insn_array/gotox-jt-per-subprog:OK
  #24/19   bpf_insn_array/gotox-span-unreached-entry:OK
  #24/20   bpf_insn_array/gotox-target-subprog-from-main:OK
  #24/21   bpf_insn_array/gotox-index-slice-other-subprog:OK
  #24/22   bpf_insn_array/gotox-target-other-global-subprog:OK
  #24/23   bpf_insn_array/gotox-callback-leaves-subprog:OK
  #24      bpf_insn_array:OK
  [...]
  #616     verifier_gotox:OK
  Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/prog_tests/bpf_insn_array.c | 715 +++++++++++++++++-
 1 file changed, 713 insertions(+), 2 deletions(-)

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 c69d44cd4607..d5a831a75d82 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0
 
 #include <bpf/bpf.h>
+#include <bpf/btf.h>
 #include <test_progs.h>
 
 #if defined(__x86_64__) || defined(__powerpc__) || defined(__aarch64__)
@@ -487,8 +488,9 @@ static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)
 	return -1;
 }
 
-static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
-			   int *fd_array, __u32 fd_array_cnt, char *log)
+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)
 {
 	LIBBPF_OPTS(bpf_prog_load_opts, opts);
 	int prog_fd;
@@ -499,6 +501,12 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
 	opts.log_buf = log;
 	opts.log_size = GOTOX_LOG_SZ;
 	opts.log_level = 1;
+	if (fi_cnt) {
+		opts.prog_btf_fd = btf_fd;
+		opts.func_info = fi;
+		opts.func_info_cnt = fi_cnt;
+		opts.func_info_rec_size = sizeof(*fi);
+	}
 
 	prog_fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
 	if (prog_fd >= 0) {
@@ -508,6 +516,13 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
 	return prog_fd;
 }
 
+static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
+			   int *fd_array, __u32 fd_array_cnt, char *log)
+{
+	return gotox_prog_load_funcs(insns, insn_cnt, fd_array, fd_array_cnt, log,
+				     -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)
 {
@@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)
 	free(log);
 }
 
+static int gotox_jt_create_offs(const __u32 *offs, __u32 cnt)
+{
+	struct bpf_insn_array_value val = {};
+	int map_fd;
+	__u32 i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, cnt);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return map_fd;
+
+	for (i = 0; i < cnt; i++) {
+		val.orig_off = offs[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;
+}
+
+#define GOTOX_SUB_START		4
+#define GOTOX_MAIN_TGT		2
+#define GOTOX_SUB_TGT		8
+#define GOTOX_TWO_INSN_CNT	10
+
+static void gotox_two_subprogs_fill(struct bpf_insn *insns, __u32 jt_idx, __u32 jt_off)
+{
+	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				GOTOX_SUB_START - 1 - 1);
+	insns[GOTOX_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[3] = BPF_EXIT_INSN();
+
+	/* r1 = &jt[0], by index 'jt_idx' into fd_array */
+	insns[GOTOX_SUB_START] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = jt_idx,
+	};
+	insns[GOTOX_SUB_START + 1] = (struct bpf_insn) { .imm = 0 };
+	insns[6] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, jt_off * 8);
+	insns[7] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[GOTOX_SUB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
+	insns[9] = BPF_EXIT_INSN();
+}
+
+/*
+ * An insn_array map is not necessarily a jump table: one that tracks
+ * instruction offsets covers the whole program and is of no subprog. Such a
+ * map must not keep a program with a gotox elsewhere from loading.
+ */
+static void check_gotox_tracker_map(void)
+{
+	const __u32 jt_track[] = { 0, GOTOX_MAIN_TGT, GOTOX_SUB_TGT };
+	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
+	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_two_subprogs_fill(insns, 1, 0);
+
+	map_fd[0] = gotox_jt_create_offs(jt_track, ARRAY_SIZE(jt_track));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	if (!ASSERT_OK(err, "program with a tracking map should load"))
+		fprintf(stderr, "verifier log: %s\n", log);
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+static void check_gotox_target_other_subprog(void)
+{
+	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
+	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
+	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_two_subprogs_fill(insns, 0, 0);
+
+	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 7 to 2 leaves the subprog [4,10)",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+static void check_gotox_jt_per_subprog(void)
+{
+	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
+	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
+	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_two_subprogs_fill(insns, 1, 0);
+
+	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+/*
+ * The spanning map is of no subprog and is dropped, and the entry the gotox
+ * register can reach is in the subprog of the gotox and in the jump table the
+ * CFG walked, so nothing unsafe is left and the program loads.
+ */
+static void check_gotox_span_unreached_entry(void)
+{
+	const __u32 jt_span[] = { GOTOX_MAIN_TGT, GOTOX_SUB_TGT };
+	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
+	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_two_subprogs_fill(insns, 0, 1);
+
+	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	if (!ASSERT_OK(err, "program with an unreachable spanning entry should load"))
+		fprintf(stderr, "verifier log: %s\n", log);
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+#define GOTOX_FWD_GOTOX		11
+#define GOTOX_FWD_OWN_TGT	12
+#define GOTOX_FWD_SUB_START	14
+#define GOTOX_FWD_INSN_CNT	16
+
+static void gotox_from_main_fill(struct bpf_insn *insns)
+{
+	insns[0] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
+	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				GOTOX_FWD_SUB_START - 1 - 1);
+	insns[2] = BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_6,
+			       offsetof(struct xdp_md, ingress_ifindex));
+	insns[3] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_2, 0, 4);
+
+	/* r1 = &jt_leaves[0], by index 1 into fd_array */
+	insns[4] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = 1,
+	};
+	insns[5] = (struct bpf_insn) { .imm = 0 };
+	insns[6] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
+	insns[7] = BPF_JMP_A(3);
+
+	/* r1 = &jt_own[0], by index 0 into fd_array */
+	insns[8] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = 0,
+	};
+	insns[9] = (struct bpf_insn) { .imm = 0 };
+	insns[10] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
+
+	insns[GOTOX_FWD_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[GOTOX_FWD_OWN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[13] = BPF_EXIT_INSN();
+	insns[GOTOX_FWD_SUB_START] = BPF_MOV64_IMM(BPF_REG_0, 1);
+	insns[15] = BPF_EXIT_INSN();
+}
+
+static void check_gotox_target_subprog_from_main(void)
+{
+	const __u32 jt_own[] = { GOTOX_FWD_OWN_TGT };
+	const __u32 jt_leaves[] = { GOTOX_FWD_SUB_START };
+	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_from_main_fill(insns);
+
+	map_fd[0] = gotox_jt_create_offs(jt_own, ARRAY_SIZE(jt_own));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_leaves, ARRAY_SIZE(jt_leaves));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 11 to 14 leaves the subprog [0,14)",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+/*
+ * The only map of the subprog holding the gotox reaches past that subprog, so
+ * the subprog is left without a jump table at all.
+ */
+static void check_gotox_jt_spans_subprogs(void)
+{
+	const __u32 jt_span[] = { GOTOX_FWD_OWN_TGT, GOTOX_FWD_SUB_START };
+	const __u32 jt_leaves[] = { GOTOX_FWD_SUB_START };
+	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_from_main_fill(insns);
+
+	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_leaves, ARRAY_SIZE(jt_leaves));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "jump table of subprog starting at 0 spans multiple subprogs",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+/*
+ * The subprog holding the gotox has a well formed jump table of its own and
+ * also collects a map that reaches past its end. The spanning map is still
+ * rejected, even though the subprog is not left without a table.
+ */
+static void check_gotox_jt_spans_with_own_table(void)
+{
+	const __u32 jt_own[] = { GOTOX_FWD_OWN_TGT };
+	const __u32 jt_span[] = { GOTOX_FWD_OWN_TGT, GOTOX_FWD_SUB_START };
+	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_from_main_fill(insns);
+
+	map_fd[0] = gotox_jt_create_offs(jt_own, ARRAY_SIZE(jt_own));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "jump table of subprog starting at 0 spans multiple subprogs",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+#define GOTOX_EDGE_MAIN_TGT	2
+#define GOTOX_EDGE_SUB_START	4
+#define GOTOX_EDGE_GOTOX	9
+#define GOTOX_EDGE_BR_TGT	10
+#define GOTOX_EDGE_JT_TGT	11
+#define GOTOX_EDGE_INSN_CNT	12
+
+static void gotox_no_edge_fill(struct bpf_insn *insns)
+{
+	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				GOTOX_EDGE_SUB_START - 1 - 1);
+	insns[GOTOX_EDGE_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[3] = BPF_EXIT_INSN();
+
+	insns[GOTOX_EDGE_SUB_START] =
+		BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+			    offsetof(struct xdp_md, ingress_ifindex));
+	insns[5] = BPF_JMP_IMM(BPF_JNE, BPF_REG_2, 0, 4);
+
+	/* r1 = &jt_span[0], by index 0 into fd_array */
+	insns[6] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = 0,
+	};
+	insns[7] = (struct bpf_insn) { .imm = 0 };
+	insns[8] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 8);
+
+	insns[GOTOX_EDGE_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[GOTOX_EDGE_BR_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
+	insns[GOTOX_EDGE_JT_TGT] = BPF_EXIT_INSN();
+}
+
+/*
+ * The gotox resolves a target inside its own subprog, but out of a map that
+ * spans subprogs and is therefore of no subprog. The CFG never walked that
+ * edge, so the jump has to be rejected even though it stays in the subprog.
+ */
+static void check_gotox_target_without_cfg_edge(void)
+{
+	const __u32 jt_span[] = { GOTOX_EDGE_MAIN_TGT, GOTOX_EDGE_BR_TGT };
+	const __u32 jt_sub[] = { GOTOX_EDGE_JT_TGT };
+	struct bpf_insn insns[GOTOX_EDGE_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_no_edge_fill(insns);
+
+	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log,
+			  "indirect jump from insn 9 to 10 is not in the jump table of the subprog",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+#define GOTOX_SLICE_SUB_START	6
+#define GOTOX_SLICE_GOTOX	14
+#define GOTOX_SLICE_SUB_TGT	15
+#define GOTOX_SLICE_INSN_CNT	17
+
+static void gotox_slice_fill(struct bpf_insn *insns)
+{
+	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				GOTOX_SLICE_SUB_START - 1 - 1);
+	insns[2] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[3] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[4] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[5] = BPF_EXIT_INSN();
+
+	insns[GOTOX_SLICE_SUB_START] =
+		BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
+			    offsetof(struct xdp_md, ingress_ifindex));
+	insns[7] = BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 1);
+	insns[8] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1);
+	insns[9] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_2, 3);
+
+	/* r1 = &jt_main[0], by index 0 into fd_array */
+	insns[10] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = 0,
+	};
+	insns[11] = (struct bpf_insn) { .imm = 0 };
+	insns[12] = BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2);
+	insns[13] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
+
+	insns[GOTOX_SLICE_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[GOTOX_SLICE_SUB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
+	insns[16] = BPF_EXIT_INSN();
+}
+
+static void check_gotox_index_slice_other_subprog(void)
+{
+	const __u32 jt_main[] = { 2, 3, 4 };
+	const __u32 jt_sub[] = { GOTOX_SLICE_SUB_TGT };
+	struct bpf_insn insns[GOTOX_SLICE_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_slice_fill(insns);
+
+	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 14 to 3 leaves the subprog [6,17)",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_log:
+	free(log);
+}
+
+static int gotox_btf_create(const __u32 *starts, const __u8 *linkage, __u32 cnt,
+			    struct bpf_func_info *fi, struct btf **pbtf)
+{
+	int int_id, proto_id, id;
+	struct btf *btf;
+	char name[24];
+	__u32 i;
+
+	btf = btf__new_empty();
+	if (!ASSERT_OK_PTR(btf, "btf__new_empty"))
+		return -1;
+
+	int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
+	if (!ASSERT_GT(int_id, 0, "btf__add_int"))
+		goto err;
+
+	proto_id = btf__add_func_proto(btf, int_id);
+	if (!ASSERT_GT(proto_id, 0, "btf__add_func_proto"))
+		goto err;
+
+	for (i = 0; i < cnt; i++) {
+		snprintf(name, sizeof(name), "gotox_f%u", i);
+		id = btf__add_func(btf, name, linkage[i], proto_id);
+		if (!ASSERT_GT(id, 0, "btf__add_func"))
+			goto err;
+		fi[i].insn_off = starts[i];
+		fi[i].type_id = id;
+	}
+
+	if (!ASSERT_OK(btf__load_into_kernel(btf), "btf__load_into_kernel"))
+		goto err;
+
+	*pbtf = btf;
+	return btf__fd(btf);
+err:
+	btf__free(btf);
+	return -1;
+}
+
+static void check_gotox_target_other_global_subprog(void)
+{
+	const __u32 starts[] = { 0, GOTOX_SUB_START };
+	const __u8 linkage[] = { BTF_FUNC_GLOBAL, BTF_FUNC_GLOBAL };
+	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
+	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
+	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	struct bpf_func_info fi[2];
+	struct btf *btf = NULL;
+	int btf_fd;
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_two_subprogs_fill(insns, 0, 0);
+
+	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
+	if (btf_fd < 0)
+		goto free_log;
+
+	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
+	if (map_fd[0] < 0)
+		goto free_btf;
+	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load_funcs(insns, ARRAY_SIZE(insns), map_fd, 2, log,
+				    btf_fd, fi, ARRAY_SIZE(fi));
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 7 to 2 leaves the subprog [4,10)",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_btf:
+	btf__free(btf);
+free_log:
+	free(log);
+}
+
+#define GOTOX_CB_MAIN_TGT	6
+#define GOTOX_CB_START		8
+#define GOTOX_CB_GOTOX		11
+#define GOTOX_CB_TGT		12
+#define GOTOX_CB_INSN_CNT	14
+
+static void gotox_callback_fill(struct bpf_insn *insns)
+{
+	insns[0] = BPF_MOV64_IMM(BPF_REG_1, 1);
+	/* r2 = &callback */
+	insns[1] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_2,
+		.src_reg = BPF_PSEUDO_FUNC,
+		.imm = GOTOX_CB_START - 1 - 1,
+	};
+	insns[2] = (struct bpf_insn) { .imm = 0 };
+	insns[3] = BPF_MOV64_IMM(BPF_REG_3, 0);
+	insns[4] = BPF_MOV64_IMM(BPF_REG_4, 0);
+	insns[5] = BPF_EMIT_CALL(BPF_FUNC_loop);
+	insns[GOTOX_CB_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[7] = BPF_EXIT_INSN();
+
+	/* r1 = &jt_main[0], by index 0 into fd_array */
+	insns[GOTOX_CB_START] = (struct bpf_insn) {
+		.code = BPF_LD | BPF_DW | BPF_IMM,
+		.dst_reg = BPF_REG_1,
+		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
+		.imm = 0,
+	};
+	insns[9] = (struct bpf_insn) { .imm = 0 };
+	insns[10] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
+	insns[GOTOX_CB_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[GOTOX_CB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[13] = BPF_EXIT_INSN();
+}
+
+static void check_gotox_callback_leaves_subprog(void)
+{
+	const __u32 starts[] = { 0, GOTOX_CB_START };
+	const __u8 linkage[] = { BTF_FUNC_GLOBAL, BTF_FUNC_STATIC };
+	const __u32 jt_main[] = { GOTOX_CB_MAIN_TGT };
+	const __u32 jt_cb[] = { GOTOX_CB_TGT };
+	struct bpf_insn insns[GOTOX_CB_INSN_CNT];
+	int map_fd[2] = { -1, -1 };
+	struct bpf_func_info fi[2];
+	struct btf *btf = NULL;
+	int btf_fd;
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	gotox_callback_fill(insns);
+
+	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
+	if (btf_fd < 0)
+		goto free_log;
+
+	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
+	if (map_fd[0] < 0)
+		goto free_btf;
+	map_fd[1] = gotox_jt_create_offs(jt_cb, ARRAY_SIZE(jt_cb));
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	err = gotox_prog_load_funcs(insns, ARRAY_SIZE(insns), map_fd, 2, log,
+				    btf_fd, fi, ARRAY_SIZE(fi));
+	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
+	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 11 to 6 leaves the subprog [8,14)",
+			  "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	close(map_fd[1]);
+free_btf:
+	btf__free(btf);
+free_log:
+	free(log);
+}
+
 static void check_bpf_side(void)
 {
 	check_bpf_no_lookup();
@@ -756,6 +1434,39 @@ static void __test_bpf_insn_array(void)
 
 	if (test__start_subtest("gotox-edges-across-subprogs"))
 		check_gotox_edges_across_subprogs();
+
+	if (test__start_subtest("gotox-tracker-map"))
+		check_gotox_tracker_map();
+
+	if (test__start_subtest("gotox-jt-spans-subprogs"))
+		check_gotox_jt_spans_subprogs();
+
+	if (test__start_subtest("gotox-jt-spans-with-own-table"))
+		check_gotox_jt_spans_with_own_table();
+
+	if (test__start_subtest("gotox-target-without-cfg-edge"))
+		check_gotox_target_without_cfg_edge();
+
+	if (test__start_subtest("gotox-target-other-subprog"))
+		check_gotox_target_other_subprog();
+
+	if (test__start_subtest("gotox-jt-per-subprog"))
+		check_gotox_jt_per_subprog();
+
+	if (test__start_subtest("gotox-span-unreached-entry"))
+		check_gotox_span_unreached_entry();
+
+	if (test__start_subtest("gotox-target-subprog-from-main"))
+		check_gotox_target_subprog_from_main();
+
+	if (test__start_subtest("gotox-index-slice-other-subprog"))
+		check_gotox_index_slice_other_subprog();
+
+	if (test__start_subtest("gotox-target-other-global-subprog"))
+		check_gotox_target_other_global_subprog();
+
+	if (test__start_subtest("gotox-callback-leaves-subprog"))
+		check_gotox_callback_leaves_subprog();
 }
 #else
 static void __test_bpf_insn_array(void)
-- 
2.43.0

Re: [PATCH bpf 6/6] selftests/bpf: Add tests for indirect jumps across subprograms

[bot+bpf-ci]

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

> selftests/bpf: Add tests for indirect jumps across subprograms
>
> Add various gotox corner case tests to improve corner case coverage.
>
>   # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
>       ./test_progs -t bpf_insn_array,verifier_gotox,signed_loader
>   [...]
>   #24/13   bpf_insn_array/gotox-tracker-map:OK
>   #24/14   bpf_insn_array/gotox-jt-spans-subprogs:OK
>   #24/15   bpf_insn_array/gotox-jt-spans-with-own-table:OK
>   #24/16   bpf_insn_array/gotox-target-without-cfg-edge:OK
>   #24/17   bpf_insn_array/gotox-target-other-subprog:OK
>   #24/18   bpf_insn_array/gotox-jt-per-subprog:OK
>   #24/19   bpf_insn_array/gotox-span-unreached-entry:OK
>   #24/20   bpf_insn_array/gotox-target-subprog-from-main:OK
>   #24/21   bpf_insn_array/gotox-index-slice-other-subprog:OK
>   #24/22   bpf_insn_array/gotox-target-other-global-subprog:OK
>   #24/23   bpf_insn_array/gotox-callback-leaves-subprog:OK
>   #24      bpf_insn_array:OK
>   [...]
>   #616     verifier_gotox:OK
>   Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED

This isn't a bug, but could the changelog say a sentence or two about
which rejection paths these 11 subtests pin down? The current form just
repeats itself ("various gotox corner case tests to improve corner case
coverage") and then pastes the test_progs output. The names of the
subtests are listed, but the message doesn't explain which verifier
behaviour each group exercises - things like targets leaving the
subprog, targets missing from the CFG jump table, one jump table shared
across subprogs, or callback cases. The sibling patch in this series
("selftests/bpf: Add tests for the indirect jump edge limit") does
state the shape of the program it builds and why, so the shorter form
here stands out within the series.

> 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 c69d44cd4607..d5a831a75d82 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c

[ ... ]

> @@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)
>  	free(log);
>  }
>
> +static int gotox_jt_create_offs(const __u32 *offs, __u32 cnt)
> +{

[ ... ]

> +/*
> + * An insn_array map is not necessarily a jump table: one that tracks
> + * instruction offsets covers the whole program and is of no subprog. Such a
> + * map must not keep a program with a gotox elsewhere from loading.
> + */
> +static void check_gotox_tracker_map(void)
                                                   ^^^^

This isn't a bug, but would it be worth rewording "is of no subprog"
here? Looking at compute_subprog_jts() in kernel/bpf/cfg.c, it does
attribute the map to the subprog containing its first entry and sets
jt_spans_subprogs there:

    subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
    if (!subprog) { ...continue; }
    if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
        subprog->jt_spans_subprogs = true;
        ...continue;
    }

Since valid_offsets() already guarantees every entry is less than
prog->len, the !subprog branch is effectively unreachable. A spanning
map doesn't become any subprog's jump table, but it does mark the
subprog holding its first entry. In the three tests using this pattern
(check_gotox_tracker_map, check_gotox_span_unreached_entry,
check_gotox_target_without_cfg_edge), that subprog happens to be main
and the gotox sits in the other subprog, which is why the outcomes are
what the tests assert. Had the spanning map's first entry landed in the
gotox's own subprog, check_gotox_tracker_map would fail to load and
check_gotox_target_without_cfg_edge would be rejected with the "spans
multiple subprogs" message instead. Would wording like "does not become
any subprog's jump table" make that dependency clearer?

> +{

[ ... ]

> +static void check_gotox_target_subprog_from_main(void)
> +{
> +	const __u32 jt_own[] = { GOTOX_FWD_OWN_TGT };
> +	const __u32 jt_leaves[] = { GOTOX_FWD_SUB_START };
> +	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_from_main_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_own, ARRAY_SIZE(jt_own));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_leaves, ARRAY_SIZE(jt_leaves));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 11 to 14 leaves the subprog [0,14)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}

This isn't a bug, but could these nine near-identical function bodies
share a small table-driven helper? The same roughly 20-line body
(calloc log, fill insns, two gotox_jt_create_offs() calls, load,
assert, close_maps/free_log labels) is repeated verbatim across
check_gotox_tracker_map, check_gotox_target_other_subprog,
check_gotox_jt_per_subprog, check_gotox_span_unreached_entry,
check_gotox_target_subprog_from_main, check_gotox_jt_spans_subprogs,
check_gotox_jt_spans_with_own_table, check_gotox_target_without_cfg_edge,
and check_gotox_index_slice_other_subprog. The only differences are the
two offset arrays, the fill helper, and the final assertion.

This file's own idiom already factors out that kind of boilerplate -
try_load_gotox_prog() and check_gotox_limit_hit() were introduced for
exactly that purpose in the preceding patch. A small helper taking
(fill, jt_a, jt_b, insn_cnt, expected_err, expected_msg), or a table of
cases, would collapse most of these bodies.

A side effect of the duplication is that the copies drifted:
check_gotox_jt_per_subprog is the only positive test that uses
ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)") and does not print the verifier
log on failure, while check_gotox_tracker_map and
check_gotox_span_unreached_entry both do 'if (!ASSERT_OK(err, ...))
fprintf(stderr, "verifier log: %s\n", log);', and it's also the only
new test without an explanatory comment.

[ ... ]

> +static void check_gotox_target_other_global_subprog(void)
> +{
> +	const __u32 starts[] = { 0, GOTOX_SUB_START };
> +	const __u8 linkage[] = { BTF_FUNC_GLOBAL, BTF_FUNC_GLOBAL };
> +	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	struct bpf_func_info fi[2];
> +	struct btf *btf = NULL;
> +	int btf_fd;
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 0, 0);
> +
> +	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
> +	if (btf_fd < 0)
> +		goto free_log;
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_btf;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load_funcs(insns, ARRAY_SIZE(insns), map_fd, 2, log,
> +				    btf_fd, fi, ARRAY_SIZE(fi));
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 7 to 2 leaves the subprog [4,10)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_btf:

This isn't a bug, but check_gotox_target_other_global_subprog() looks
line-for-line identical to check_gotox_target_other_subprog() - same
gotox_two_subprogs_fill(insns, 0, 0), same jt_main/jt_sub contents,
same asserted error string "indirect jump from insn 7 to 2 leaves the
subprog [4,10)". The only delta is the BTF func_info that makes subprog
1 BTF_FUNC_GLOBAL, plus the extra btf_fd/free_btf plumbing. Would a
single helper taking the jump tables, the optional BTF/func_info and
the expected log substring read better than the two near-copies?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34404843294

Re: [PATCH bpf 6/6] selftests/bpf: Add tests for indirect jumps across subprograms

[Anton Protopopov]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> Add various gotox corner case tests to improve corner case coverage.
> 
>   # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- \
>       ./test_progs -t bpf_insn_array,verifier_gotox,signed_loader

signed_loader? :)

Dunno if there is real value in "leaves the subprog" for different
types of "leaves"... But nice to see more tests.

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>

>   [...]
>   #24/13   bpf_insn_array/gotox-tracker-map:OK
>   #24/14   bpf_insn_array/gotox-jt-spans-subprogs:OK
>   #24/15   bpf_insn_array/gotox-jt-spans-with-own-table:OK
>   #24/16   bpf_insn_array/gotox-target-without-cfg-edge:OK
>   #24/17   bpf_insn_array/gotox-target-other-subprog:OK
>   #24/18   bpf_insn_array/gotox-jt-per-subprog:OK
>   #24/19   bpf_insn_array/gotox-span-unreached-entry:OK
>   #24/20   bpf_insn_array/gotox-target-subprog-from-main:OK
>   #24/21   bpf_insn_array/gotox-index-slice-other-subprog:OK
>   #24/22   bpf_insn_array/gotox-target-other-global-subprog:OK
>   #24/23   bpf_insn_array/gotox-callback-leaves-subprog:OK
>   #24      bpf_insn_array:OK
>   [...]
>   #616     verifier_gotox:OK
>   Summary: 3/79 PASSED, 0 SKIPPED, 0/0 FAILED
> 
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  .../selftests/bpf/prog_tests/bpf_insn_array.c | 715 +++++++++++++++++-
>  1 file changed, 713 insertions(+), 2 deletions(-)
> 
> 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 c69d44cd4607..d5a831a75d82 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> @@ -1,6 +1,7 @@
>  // SPDX-License-Identifier: GPL-2.0
>  
>  #include <bpf/bpf.h>
> +#include <bpf/btf.h>
>  #include <test_progs.h>
>  
>  #if defined(__x86_64__) || defined(__powerpc__) || defined(__aarch64__)
> @@ -487,8 +488,9 @@ static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)
>  	return -1;
>  }
>  
> -static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
> -			   int *fd_array, __u32 fd_array_cnt, char *log)
> +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)
>  {
>  	LIBBPF_OPTS(bpf_prog_load_opts, opts);
>  	int prog_fd;
> @@ -499,6 +501,12 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
>  	opts.log_buf = log;
>  	opts.log_size = GOTOX_LOG_SZ;
>  	opts.log_level = 1;
> +	if (fi_cnt) {
> +		opts.prog_btf_fd = btf_fd;
> +		opts.func_info = fi;
> +		opts.func_info_cnt = fi_cnt;
> +		opts.func_info_rec_size = sizeof(*fi);
> +	}
>  
>  	prog_fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
>  	if (prog_fd >= 0) {
> @@ -508,6 +516,13 @@ static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
>  	return prog_fd;
>  }
>  
> +static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
> +			   int *fd_array, __u32 fd_array_cnt, char *log)
> +{
> +	return gotox_prog_load_funcs(insns, insn_cnt, fd_array, fd_array_cnt, log,
> +				     -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)
>  {
> @@ -710,6 +725,669 @@ static void check_gotox_edges_across_subprogs(void)
>  	free(log);
>  }
>  
> +static int gotox_jt_create_offs(const __u32 *offs, __u32 cnt)
> +{
> +	struct bpf_insn_array_value val = {};
> +	int map_fd;
> +	__u32 i;
> +
> +	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, cnt);
> +	if (!ASSERT_GE(map_fd, 0, "map_create"))
> +		return map_fd;
> +
> +	for (i = 0; i < cnt; i++) {
> +		val.orig_off = offs[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;
> +}
> +
> +#define GOTOX_SUB_START		4
> +#define GOTOX_MAIN_TGT		2
> +#define GOTOX_SUB_TGT		8
> +#define GOTOX_TWO_INSN_CNT	10
> +
> +static void gotox_two_subprogs_fill(struct bpf_insn *insns, __u32 jt_idx, __u32 jt_off)
> +{
> +	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
> +				GOTOX_SUB_START - 1 - 1);
> +	insns[GOTOX_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[3] = BPF_EXIT_INSN();
> +
> +	/* r1 = &jt[0], by index 'jt_idx' into fd_array */
> +	insns[GOTOX_SUB_START] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = jt_idx,
> +	};
> +	insns[GOTOX_SUB_START + 1] = (struct bpf_insn) { .imm = 0 };
> +	insns[6] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, jt_off * 8);
> +	insns[7] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[GOTOX_SUB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
> +	insns[9] = BPF_EXIT_INSN();
> +}
> +
> +/*
> + * An insn_array map is not necessarily a jump table: one that tracks
> + * instruction offsets covers the whole program and is of no subprog. Such a
> + * map must not keep a program with a gotox elsewhere from loading.
> + */
> +static void check_gotox_tracker_map(void)
> +{
> +	const __u32 jt_track[] = { 0, GOTOX_MAIN_TGT, GOTOX_SUB_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 1, 0);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_track, ARRAY_SIZE(jt_track));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	if (!ASSERT_OK(err, "program with a tracking map should load"))
> +		fprintf(stderr, "verifier log: %s\n", log);
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +static void check_gotox_target_other_subprog(void)
> +{
> +	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 0, 0);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 7 to 2 leaves the subprog [4,10)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +static void check_gotox_jt_per_subprog(void)
> +{
> +	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 1, 0);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +/*
> + * The spanning map is of no subprog and is dropped, and the entry the gotox
> + * register can reach is in the subprog of the gotox and in the jump table the
> + * CFG walked, so nothing unsafe is left and the program loads.
> + */
> +static void check_gotox_span_unreached_entry(void)
> +{
> +	const __u32 jt_span[] = { GOTOX_MAIN_TGT, GOTOX_SUB_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 0, 1);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	if (!ASSERT_OK(err, "program with an unreachable spanning entry should load"))
> +		fprintf(stderr, "verifier log: %s\n", log);
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +#define GOTOX_FWD_GOTOX		11
> +#define GOTOX_FWD_OWN_TGT	12
> +#define GOTOX_FWD_SUB_START	14
> +#define GOTOX_FWD_INSN_CNT	16
> +
> +static void gotox_from_main_fill(struct bpf_insn *insns)
> +{
> +	insns[0] = BPF_MOV64_REG(BPF_REG_6, BPF_REG_1);
> +	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
> +				GOTOX_FWD_SUB_START - 1 - 1);
> +	insns[2] = BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_6,
> +			       offsetof(struct xdp_md, ingress_ifindex));
> +	insns[3] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_2, 0, 4);
> +
> +	/* r1 = &jt_leaves[0], by index 1 into fd_array */
> +	insns[4] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = 1,
> +	};
> +	insns[5] = (struct bpf_insn) { .imm = 0 };
> +	insns[6] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
> +	insns[7] = BPF_JMP_A(3);
> +
> +	/* r1 = &jt_own[0], by index 0 into fd_array */
> +	insns[8] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = 0,
> +	};
> +	insns[9] = (struct bpf_insn) { .imm = 0 };
> +	insns[10] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
> +
> +	insns[GOTOX_FWD_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[GOTOX_FWD_OWN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[13] = BPF_EXIT_INSN();
> +	insns[GOTOX_FWD_SUB_START] = BPF_MOV64_IMM(BPF_REG_0, 1);
> +	insns[15] = BPF_EXIT_INSN();
> +}
> +
> +static void check_gotox_target_subprog_from_main(void)
> +{
> +	const __u32 jt_own[] = { GOTOX_FWD_OWN_TGT };
> +	const __u32 jt_leaves[] = { GOTOX_FWD_SUB_START };
> +	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_from_main_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_own, ARRAY_SIZE(jt_own));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_leaves, ARRAY_SIZE(jt_leaves));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 11 to 14 leaves the subprog [0,14)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +/*
> + * The only map of the subprog holding the gotox reaches past that subprog, so
> + * the subprog is left without a jump table at all.
> + */
> +static void check_gotox_jt_spans_subprogs(void)
> +{
> +	const __u32 jt_span[] = { GOTOX_FWD_OWN_TGT, GOTOX_FWD_SUB_START };
> +	const __u32 jt_leaves[] = { GOTOX_FWD_SUB_START };
> +	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_from_main_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_leaves, ARRAY_SIZE(jt_leaves));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "jump table of subprog starting at 0 spans multiple subprogs",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +/*
> + * The subprog holding the gotox has a well formed jump table of its own and
> + * also collects a map that reaches past its end. The spanning map is still
> + * rejected, even though the subprog is not left without a table.
> + */
> +static void check_gotox_jt_spans_with_own_table(void)
> +{
> +	const __u32 jt_own[] = { GOTOX_FWD_OWN_TGT };
> +	const __u32 jt_span[] = { GOTOX_FWD_OWN_TGT, GOTOX_FWD_SUB_START };
> +	struct bpf_insn insns[GOTOX_FWD_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_from_main_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_own, ARRAY_SIZE(jt_own));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "jump table of subprog starting at 0 spans multiple subprogs",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +#define GOTOX_EDGE_MAIN_TGT	2
> +#define GOTOX_EDGE_SUB_START	4
> +#define GOTOX_EDGE_GOTOX	9
> +#define GOTOX_EDGE_BR_TGT	10
> +#define GOTOX_EDGE_JT_TGT	11
> +#define GOTOX_EDGE_INSN_CNT	12
> +
> +static void gotox_no_edge_fill(struct bpf_insn *insns)
> +{
> +	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
> +				GOTOX_EDGE_SUB_START - 1 - 1);
> +	insns[GOTOX_EDGE_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[3] = BPF_EXIT_INSN();
> +
> +	insns[GOTOX_EDGE_SUB_START] =
> +		BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
> +			    offsetof(struct xdp_md, ingress_ifindex));
> +	insns[5] = BPF_JMP_IMM(BPF_JNE, BPF_REG_2, 0, 4);
> +
> +	/* r1 = &jt_span[0], by index 0 into fd_array */
> +	insns[6] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = 0,
> +	};
> +	insns[7] = (struct bpf_insn) { .imm = 0 };
> +	insns[8] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 8);
> +
> +	insns[GOTOX_EDGE_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[GOTOX_EDGE_BR_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
> +	insns[GOTOX_EDGE_JT_TGT] = BPF_EXIT_INSN();
> +}
> +
> +/*
> + * The gotox resolves a target inside its own subprog, but out of a map that
> + * spans subprogs and is therefore of no subprog. The CFG never walked that
> + * edge, so the jump has to be rejected even though it stays in the subprog.
> + */
> +static void check_gotox_target_without_cfg_edge(void)
> +{
> +	const __u32 jt_span[] = { GOTOX_EDGE_MAIN_TGT, GOTOX_EDGE_BR_TGT };
> +	const __u32 jt_sub[] = { GOTOX_EDGE_JT_TGT };
> +	struct bpf_insn insns[GOTOX_EDGE_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_no_edge_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_span, ARRAY_SIZE(jt_span));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log,
> +			  "indirect jump from insn 9 to 10 is not in the jump table of the subprog",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +#define GOTOX_SLICE_SUB_START	6
> +#define GOTOX_SLICE_GOTOX	14
> +#define GOTOX_SLICE_SUB_TGT	15
> +#define GOTOX_SLICE_INSN_CNT	17
> +
> +static void gotox_slice_fill(struct bpf_insn *insns)
> +{
> +	insns[0] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
> +				GOTOX_SLICE_SUB_START - 1 - 1);
> +	insns[2] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[3] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[4] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[5] = BPF_EXIT_INSN();
> +
> +	insns[GOTOX_SLICE_SUB_START] =
> +		BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
> +			    offsetof(struct xdp_md, ingress_ifindex));
> +	insns[7] = BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 1);
> +	insns[8] = BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1);
> +	insns[9] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_2, 3);
> +
> +	/* r1 = &jt_main[0], by index 0 into fd_array */
> +	insns[10] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = 0,
> +	};
> +	insns[11] = (struct bpf_insn) { .imm = 0 };
> +	insns[12] = BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2);
> +	insns[13] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
> +
> +	insns[GOTOX_SLICE_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[GOTOX_SLICE_SUB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 1);
> +	insns[16] = BPF_EXIT_INSN();
> +}
> +
> +static void check_gotox_index_slice_other_subprog(void)
> +{
> +	const __u32 jt_main[] = { 2, 3, 4 };
> +	const __u32 jt_sub[] = { GOTOX_SLICE_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_SLICE_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_slice_fill(insns);
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, ARRAY_SIZE(insns), map_fd, 2, log);
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 14 to 3 leaves the subprog [6,17)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_log:
> +	free(log);
> +}
> +
> +static int gotox_btf_create(const __u32 *starts, const __u8 *linkage, __u32 cnt,
> +			    struct bpf_func_info *fi, struct btf **pbtf)
> +{
> +	int int_id, proto_id, id;
> +	struct btf *btf;
> +	char name[24];
> +	__u32 i;
> +
> +	btf = btf__new_empty();
> +	if (!ASSERT_OK_PTR(btf, "btf__new_empty"))
> +		return -1;
> +
> +	int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
> +	if (!ASSERT_GT(int_id, 0, "btf__add_int"))
> +		goto err;
> +
> +	proto_id = btf__add_func_proto(btf, int_id);
> +	if (!ASSERT_GT(proto_id, 0, "btf__add_func_proto"))
> +		goto err;
> +
> +	for (i = 0; i < cnt; i++) {
> +		snprintf(name, sizeof(name), "gotox_f%u", i);
> +		id = btf__add_func(btf, name, linkage[i], proto_id);
> +		if (!ASSERT_GT(id, 0, "btf__add_func"))
> +			goto err;
> +		fi[i].insn_off = starts[i];
> +		fi[i].type_id = id;
> +	}
> +
> +	if (!ASSERT_OK(btf__load_into_kernel(btf), "btf__load_into_kernel"))
> +		goto err;
> +
> +	*pbtf = btf;
> +	return btf__fd(btf);
> +err:
> +	btf__free(btf);
> +	return -1;
> +}
> +
> +static void check_gotox_target_other_global_subprog(void)
> +{
> +	const __u32 starts[] = { 0, GOTOX_SUB_START };
> +	const __u8 linkage[] = { BTF_FUNC_GLOBAL, BTF_FUNC_GLOBAL };
> +	const __u32 jt_main[] = { GOTOX_MAIN_TGT };
> +	const __u32 jt_sub[] = { GOTOX_SUB_TGT };
> +	struct bpf_insn insns[GOTOX_TWO_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	struct bpf_func_info fi[2];
> +	struct btf *btf = NULL;
> +	int btf_fd;
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_two_subprogs_fill(insns, 0, 0);
> +
> +	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
> +	if (btf_fd < 0)
> +		goto free_log;
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_btf;
> +	map_fd[1] = gotox_jt_create_offs(jt_sub, ARRAY_SIZE(jt_sub));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load_funcs(insns, ARRAY_SIZE(insns), map_fd, 2, log,
> +				    btf_fd, fi, ARRAY_SIZE(fi));
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 7 to 2 leaves the subprog [4,10)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_btf:
> +	btf__free(btf);
> +free_log:
> +	free(log);
> +}
> +
> +#define GOTOX_CB_MAIN_TGT	6
> +#define GOTOX_CB_START		8
> +#define GOTOX_CB_GOTOX		11
> +#define GOTOX_CB_TGT		12
> +#define GOTOX_CB_INSN_CNT	14
> +
> +static void gotox_callback_fill(struct bpf_insn *insns)
> +{
> +	insns[0] = BPF_MOV64_IMM(BPF_REG_1, 1);
> +	/* r2 = &callback */
> +	insns[1] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_2,
> +		.src_reg = BPF_PSEUDO_FUNC,
> +		.imm = GOTOX_CB_START - 1 - 1,
> +	};
> +	insns[2] = (struct bpf_insn) { .imm = 0 };
> +	insns[3] = BPF_MOV64_IMM(BPF_REG_3, 0);
> +	insns[4] = BPF_MOV64_IMM(BPF_REG_4, 0);
> +	insns[5] = BPF_EMIT_CALL(BPF_FUNC_loop);
> +	insns[GOTOX_CB_MAIN_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[7] = BPF_EXIT_INSN();
> +
> +	/* r1 = &jt_main[0], by index 0 into fd_array */
> +	insns[GOTOX_CB_START] = (struct bpf_insn) {
> +		.code = BPF_LD | BPF_DW | BPF_IMM,
> +		.dst_reg = BPF_REG_1,
> +		.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +		.imm = 0,
> +	};
> +	insns[9] = (struct bpf_insn) { .imm = 0 };
> +	insns[10] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
> +	insns[GOTOX_CB_GOTOX] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[GOTOX_CB_TGT] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[13] = BPF_EXIT_INSN();
> +}
> +
> +static void check_gotox_callback_leaves_subprog(void)
> +{
> +	const __u32 starts[] = { 0, GOTOX_CB_START };
> +	const __u8 linkage[] = { BTF_FUNC_GLOBAL, BTF_FUNC_STATIC };
> +	const __u32 jt_main[] = { GOTOX_CB_MAIN_TGT };
> +	const __u32 jt_cb[] = { GOTOX_CB_TGT };
> +	struct bpf_insn insns[GOTOX_CB_INSN_CNT];
> +	int map_fd[2] = { -1, -1 };
> +	struct bpf_func_info fi[2];
> +	struct btf *btf = NULL;
> +	int btf_fd;
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	gotox_callback_fill(insns);
> +
> +	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
> +	if (btf_fd < 0)
> +		goto free_log;
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_main, ARRAY_SIZE(jt_main));
> +	if (map_fd[0] < 0)
> +		goto free_btf;
> +	map_fd[1] = gotox_jt_create_offs(jt_cb, ARRAY_SIZE(jt_cb));
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load_funcs(insns, ARRAY_SIZE(insns), map_fd, 2, log,
> +				    btf_fd, fi, ARRAY_SIZE(fi));
> +	ASSERT_EQ(err, -EINVAL, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, "indirect jump from insn 11 to 6 leaves the subprog [8,14)",
> +			  "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_btf:
> +	btf__free(btf);
> +free_log:
> +	free(log);
> +}
> +
>  static void check_bpf_side(void)
>  {
>  	check_bpf_no_lookup();
> @@ -756,6 +1434,39 @@ static void __test_bpf_insn_array(void)
>  
>  	if (test__start_subtest("gotox-edges-across-subprogs"))
>  		check_gotox_edges_across_subprogs();
> +
> +	if (test__start_subtest("gotox-tracker-map"))
> +		check_gotox_tracker_map();
> +
> +	if (test__start_subtest("gotox-jt-spans-subprogs"))
> +		check_gotox_jt_spans_subprogs();
> +
> +	if (test__start_subtest("gotox-jt-spans-with-own-table"))
> +		check_gotox_jt_spans_with_own_table();
> +
> +	if (test__start_subtest("gotox-target-without-cfg-edge"))
> +		check_gotox_target_without_cfg_edge();
> +
> +	if (test__start_subtest("gotox-target-other-subprog"))
> +		check_gotox_target_other_subprog();
> +
> +	if (test__start_subtest("gotox-jt-per-subprog"))
> +		check_gotox_jt_per_subprog();
> +
> +	if (test__start_subtest("gotox-span-unreached-entry"))
> +		check_gotox_span_unreached_entry();
> +
> +	if (test__start_subtest("gotox-target-subprog-from-main"))
> +		check_gotox_target_subprog_from_main();
> +
> +	if (test__start_subtest("gotox-index-slice-other-subprog"))
> +		check_gotox_index_slice_other_subprog();
> +
> +	if (test__start_subtest("gotox-target-other-global-subprog"))
> +		check_gotox_target_other_global_subprog();
> +
> +	if (test__start_subtest("gotox-callback-leaves-subprog"))
> +		check_gotox_callback_leaves_subprog();
>  }
>  #else
>  static void __test_bpf_insn_array(void)
> -- 
> 2.43.0
> 

Re: [PATCH bpf 1/6] bpf: Avoid quadratic successor rescan in bpf_compute_scc

[Eduard Zingerman]

On Wed, 2026-09-09 at 22:40 +0200, Daniel Borkmann wrote:
> The iterative Tarjan DFS in bpf_compute_scc() emulates recursion with an
> explicit 'dfs' stack: when a successor has not been visited yet, the
> successor is pushed and the walk restarts at the top of the loop. On the
> way back to a vertex the successor scan starts over at index zero, so a
> vertex with k successors rescans up to k successors on each of its up to k
> descents, i.e. O(k^2) work.
> 
> For ordinary instructions k <= 2 and this is irrelevant. For a gotox the
> successors are the jump table of the containing subprogram, whose size is
> bounded only by the max_entries of the insn_array map, so k can reach the
> 1M instruction complexity limit. Loading such a program keeps a CPU busy
> in the loop for a very long time before verification even begins.
> 
> Record in 'dfs_pos' the successor index each frame stopped at and resume
> the scan there. Each edge is therefore examined a bounded number of times
> and the walk becomes linear in the number of edges.
> 
> Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
> Reported-by: STAR Labs SG <info@starlabs.sg>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

The change looks correct, but I'd cleanup the comments a bit,
to me these look too LLM-ish.

>  kernel/bpf/cfg.c | 41 +++++++++++++++++++++++++++++++++++------
>  1 file changed, 35 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 842c7d1eabcc..081f7003eae6 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -749,7 +749,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	struct bpf_insn_aux_data *aux = env->insn_aux_data;
>  	const u32 insn_cnt = env->prog->len;
>  	int stack_sz, dfs_sz, err = 0;
> -	u32 *stack, *pre, *low, *dfs;
> +	u32 *stack, *pre, *low, *dfs, *dfs_pos;
>  	u32 i, j, t, w;
>  	u32 next_preorder_num;
>  	u32 next_scc_id;
> @@ -762,13 +762,16 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	 * - 'stack' accumulates vertices in DFS order, see invariant comment below;
>  	 * - 'pre[t] == p' => preorder number of vertex 't' is 'p';
>  	 * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n';
> -	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion.
> +	 * - 'dfs' DFS traversal stack, used to emulate explicit recursion;
> +	 * - 'dfs_pos[k] == j' => the frame 'dfs[k]' resumes visiting its
> +	 *   successors at index 'j'.
>  	 */
>  	stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
>  	dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL_ACCOUNT);
> -	if (!stack || !pre || !low || !dfs) {
> +	dfs_pos = kvcalloc(insn_cnt, sizeof(*dfs_pos), GFP_KERNEL_ACCOUNT);
> +	if (!stack || !pre || !low || !dfs || !dfs_pos) {
>  		err = -ENOMEM;
>  		goto exit;
>  	}
> @@ -851,6 +854,7 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  		stack_sz = 0;
>  		dfs_sz = 1;
>  		dfs[0] = i;
> +		dfs_pos[0] = 0;
>  dfs_continue:
>  		while (dfs_sz) {
>  			w = dfs[dfs_sz - 1];
> @@ -860,13 +864,37 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  				next_preorder_num++;
>  				stack[stack_sz++] = w;
>  			}
> -			/* Visit 'w' successors */
> +			/*
> +			 * Visit 'w' successors, resuming at the successor this
> +			 * frame last descended into. Restarting the scan at zero
> +			 * on every return to 'w' would examine each successor
> +			 * once per descent, i.e. quadratic in the number of
> +			 * successors, which for a gotox is the size of the jump
> +			 * table.

Please drop the paragraph above, this fact was already stated in the
commit message.

> +			 *
> +			 * Re-folding the successors before that index would be a

I think "visiting" is a better term in this context.

> +			 * no-op. Such a successor 's' has 'pre[s] != 0' by then,
> +			 * so it is never pushed onto 'dfs' again, and low[s] can
> +			 * only decrease while 's' is the top of 'dfs'. If 's' is
> +			 * still on 'dfs' it sits below 'w' and cannot become the
> +			 * top before 'w' is popped; otherwise the only remaining
> +			 * write to low[s] is the pop of its SCC, setting it to
> +			 * NOT_ON_STACK, for which the min below is a no-op.
> +			 */

Tbh, I find this paragraph extremely hard to parse.
Why not simply /* Visit the next 'w' successor */ ?

>  			succ = bpf_insn_successors(env, w);
> -			for (j = 0; j < succ->cnt; ++j) {
> +			for (j = dfs_pos[dfs_sz - 1]; j < succ->cnt; ++j) {
>  				if (pre[succ->items[j]]) {
>  					low[w] = min(low[w], low[succ->items[j]]);
>  				} else {
> -					dfs[dfs_sz++] = succ->items[j];
> +					/*
> +					 * Resume at 'j', not 'j + 1': the successor
> +					 * is revisited once its DFS completes, to
> +					 * fold its low[] into low[w].
> +					 */

/*
 * Once DFS for succ->items[j] is complete, the pre[succ->items[j]] would be non-zero,
 * hence resuming at 'j' allows to follow the update low[w] = min(...) branch above.
 */

> +					dfs_pos[dfs_sz - 1] = j;
> +					dfs_pos[dfs_sz] = 0;
> +					dfs[dfs_sz] = succ->items[j];
> +					dfs_sz++;
>  					goto dfs_continue;
>  				}
>  			}
> @@ -916,5 +944,6 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
>  	kvfree(pre);
>  	kvfree(low);
>  	kvfree(dfs);
> +	kvfree(dfs_pos);
>  	return err;
>  }