[PATCH bpf-next v3 00/16] Misc BPF gotox fixes

[PATCH bpf-next v3 00/16] Misc BPF gotox fixes

[Daniel Borkmann]

Address various open issues around gotox instruction, see individual
commits for details. Also BPF selftests are added to assert that these
are addressed.

v2 -> v3:
  - Rebased onto bpf-next given indirect call series landed
  - Split out the exit_idx sentinel as its own fix (Eduard)
  - Return early from visit_gotox_insn() on a revisited gotox (Eduard)
  - Check both ends of the target slice in check_indirect_jump() (Eduard)
  - Rewrite edge limit and nop target tests in inline asm (Eduard)
  - Name the patch modes BPF_PATCH_{KEEP,MOVE}_TARGET (Eduard)
  - Drop the insn array stale reuse test (Eduard)
  - Clear the insn array used flag with release semantics (sashiko)
  - Add fix for the exception callback index after dead subprog removal
  - Free the jump tables of removed subprogs and on a failed table build
  - Shift the poke descriptors along with the insn array slots
v1 -> v2:
  - Remove jt_spans_subprogs and reject right away (Eduard)
  - Rework jump table to no longer keep it in insn_aux_data (Eduard)
  - Fix up comments in bpf_compute_scc (Eduard)
  - Fix up commit message nit wrt signed_loader (Anton)
  - Added 3 more fixes related to gotox along with BPF selftests

Daniel Borkmann (16):
  bpf: Avoid quadratic successor rescan in bpf_compute_scc
  bpf: Bound the number of indirect jump edges in a program
  bpf: Rebase the exception callback subprog when dead subprogs are removed
  bpf: Leave out the hidden exit edge of a subprogram without an exit
  bpf: Cache the jump table of a subprogram during CFG discovery
  bpf: Reject indirect jumps that leave their subprogram
  bpf: Don't remove indirect jump targets in the nop removal pass
  bpf: Clear insn array jitted pointers on map reuse
  bpf: Clear the insn array used flag with release semantics
  bpf: Retarget indirect jump targets across prologue prepends
  selftests/bpf: Add tests for the indirect jump edge limit
  selftests/bpf: Add a test for a tail call in a subprogram without an exit
  selftests/bpf: Add tests for indirect jumps across subprograms
  selftests/bpf: Add a test for gotox nop targets
  selftests/bpf: Add tests for gotox targets across prologue prepends
  selftests/bpf: Add a test for an exception callback behind a dead subprog

 include/linux/bpf.h                           |   2 +-
 include/linux/bpf_verifier.h                  |  12 +-
 kernel/bpf/bpf_insn_array.c                   |  19 +-
 kernel/bpf/cfg.c                              | 241 ++++---
 kernel/bpf/fixups.c                           |  92 ++-
 kernel/bpf/liveness.c                         |  26 +-
 kernel/bpf/verifier.c                         |  37 +-
 .../selftests/bpf/prog_tests/bpf_insn_array.c | 650 +++++++++++++++++-
 .../selftests/bpf/prog_tests/exceptions.c     |   7 +
 .../bpf/progs/exceptions_dead_subprog.c       |  40 ++
 .../selftests/bpf/progs/verifier_cfg.c        |  38 +
 .../selftests/bpf/progs/verifier_gotox.c      | 125 +++-
 12 files changed, 1115 insertions(+), 174 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_dead_subprog.c

-- 
2.43.0

[PATCH bpf-next v3 01/16] 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>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/cfg.c | 26 ++++++++++++++++++++------
 1 file changed, 20 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 0de2f634ef67..54ff20234236 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -825,7 +825,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;
@@ -838,13 +838,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;
 	}
@@ -927,6 +930,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];
@@ -936,13 +940,22 @@ int bpf_compute_scc(struct bpf_verifier_env *env)
 				next_preorder_num++;
 				stack[stack_sz++] = w;
 			}
-			/* Visit 'w' successors */
+			/* Visit remaining 'w' successors */
 			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];
+					/*
+					 * Once DFS for succ->items[j] is complete,
+					 * pre[succ->items[j]] is non-zero, hence
+					 * resuming at 'j' allows to follow the
+					 * low[w] = min(...) update branch above.
+					 */
+					dfs_pos[dfs_sz - 1] = j;
+					dfs_pos[dfs_sz] = 0;
+					dfs[dfs_sz] = succ->items[j];
+					dfs_sz++;
 					goto dfs_continue;
 				}
 			}
@@ -992,5 +1005,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-next v3 02/16] 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 on the number of instructions the verifier processes. Progs
with real switch statements are orders of magnitude below this.

This bounds the edges only. Building the jump table of a gotox costs the
number of entries of all insn array maps regardless of how many distinct
targets they hold, which a later patch addresses separately.

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: Anton Protopopov <a.s.protopopov@gmail.com>
---
 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 646e447cebd8..67363c25526d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1004,6 +1004,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 54ff20234236..69e484b25b59 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

[PATCH bpf-next v3 03/16] bpf: Rebase the exception callback subprog when dead subprogs are removed

[Daniel Borkmann]

adjust_subprog_starts_after_remove() compacts subprog_info[] and the
func_info when whole subprograms are removed as dead code, but leaves
env->exception_callback_subprog alone, so an exception callback declared
through the exception_callback decl tag which sits behind a removed
subprogram keeps its old index. jit_subprogs() then takes the exception
callback from func[] at that index, which is past the end when the
callback was the last subprogram, or another subprogram otherwise.

Rebase the index along with the entries it refers to.

Fixes: b9ae0c9dd0ac ("bpf: Add support for custom exception callbacks")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/fixups.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index e9c2d6c06218..d49c50dae20a 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -506,6 +506,9 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 			 * in adjust_btf_func() - no need to adjust
 			 */
 		}
+		/* The exception callback is live, so it cannot sit inside the removed range. */
+		if (env->exception_callback_subprog >= j)
+			env->exception_callback_subprog -= j - i;
 	} else {
 		/* convert i from "first prog to remove" to "first to adjust" */
 		if (env->subprog_info[i].start == off)
-- 
2.43.0

[PATCH bpf-next v3 04/16] bpf: Leave out the hidden exit edge of a subprogram without an exit

[Daniel Borkmann]

visit_abnormal_return_insn() gives tail_call and ld_{abs,ind} insns a
second successor, the exit_idx of their subprogram, so that the hidden
exit from the subprogram is part of the CFG. check_subprogs() only
assigns exit_idx when it walks over a BPF_EXIT, and a subprogram whose
last insn jumps back into itself never has one, so exit_idx stays zero
and the edge points at insn 0 of the program:

  0: r0 = 0
  1: r0 = *(u8 *)skb[0]
  2: goto -2

For a subprogram other than main, update_insn() then reads the liveness
masks at a negative relative index. Such a subprogram can still load
when it leaves through a bpf_throw(), so mark exit_idx as unset in that
case and leave the hidden edge out, as there is no exit for it to reach.

Fixes: e40f5a6bf88a ("bpf: correct stack liveness for tail calls")
Fixes: ee861486e377 ("bpf: Fix ld_{abs,ind} failure path analysis in subprogs")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h |  6 +++++-
 kernel/bpf/cfg.c             | 10 +++++++---
 kernel/bpf/verifier.c        |  1 +
 3 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 67363c25526d..0b224498d307 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -815,7 +815,11 @@ struct bpf_subprog_info {
 	u32 start; /* insn idx of function entry point */
 	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 */
+	/*
+	 * Index of one of the BPF_EXIT instructions in this subprogram, or
+	 * U32_MAX when it has none.
+	 */
+	u32 exit_idx;
 	u16 stack_depth; /* max. stack depth used by this function */
 	u16 stack_extra;
 	u32 insns_total;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 69e484b25b59..f3f545c53264 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -515,17 +515,21 @@ static int visit_abnormal_return_insn(struct bpf_verifier_env *env, int t)
 {
 	struct bpf_subprog_info *subprog;
 	struct bpf_iarray *jt;
+	u32 n;
 
 	if (env->insn_aux_data[t].jt)
 		return 0;
 
-	jt = bpf_iarray_realloc(NULL, 2);
+	/* A subprogram without an exit has no hidden exit edge to take. */
+	subprog = bpf_find_containing_subprog(env, t);
+	n = subprog->exit_idx == U32_MAX ? 1 : 2;
+	jt = bpf_iarray_realloc(NULL, n);
 	if (!jt)
 		return -ENOMEM;
 
-	subprog = bpf_find_containing_subprog(env, t);
 	jt->items[0] = t + 1;
-	jt->items[1] = subprog->exit_idx;
+	if (n == 2)
+		jt->items[1] = subprog->exit_idx;
 	env->insn_aux_data[t].jt = jt;
 	return 0;
 }
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c495dc9070de..015909fe6843 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2470,6 +2470,7 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
 		return -E2BIG;
 	}
 	/* determine subprog starts. The end is one before the next starts */
+	env->subprog_info[env->subprog_cnt].exit_idx = U32_MAX;
 	env->subprog_info[env->subprog_cnt++].start = off;
 	sort(env->subprog_info, env->subprog_cnt,
 	     sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
-- 
2.43.0

[PATCH bpf-next v3 05/16] 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 343s 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 41 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
let every gotox use it in place: bpf_insn_successors() resolves a gotox
through its containing subprogram, and the tables are kept until the
verifier environment is torn down, so nothing is copied into the
instruction aux data. The edge accounting in visit_gotox_insn() moves
to the first visit of the gotox, marked by the BRANCH bit of its CFG
state, and a revisit returns right away since the first one already
pushed every target that still needed exploring.

The only user left of insn_aux_data[].jt is then the table which
visit_abnormal_return_insn() allocates for tail_call and
ld_{abs,ind} insns, so that bpf_insn_successors() reports the hidden
exit from their subprogram. Both are recognisable by their opcode, so
derive that edge in bpf_insn_successors() from the exit_idx of the
containing subprogram instead, again leaving it out when the subprogram
has no exit, and drop the field along with bpf_clear_insn_aux_data().
The instruction aux data then owns no allocation, thus nothing needs to
be freed when insns are removed or the verifier environment is torn
down.

Subprograms removed as dead code free their table in
adjust_subprog_starts_after_remove(), which also clears the slots that
the compaction of subprog_info vacates, as they still hold copies of the
moved entries and with them their table pointers.

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     35.34s     0.07s
   1000       250000   2000     82.00s     0.07s
   2000       250000   4000    148.62s     0.07s
   2000       125000   4000     74.54s     0.05s
   2000       500000   4000    342.71s     0.19s

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h |   5 +-
 kernel/bpf/cfg.c             | 190 ++++++++++++++++++-----------------
 kernel/bpf/fixups.c          |  30 ++----
 kernel/bpf/liveness.c        |  26 ++++-
 kernel/bpf/verifier.c        |   3 +-
 5 files changed, 134 insertions(+), 120 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0b224498d307..c775bd757706 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -660,7 +660,6 @@ struct bpf_insn_aux_data {
 		/* remember the offset of node field within type to rewrite */
 		u64 insert_off;
 	};
-	struct bpf_iarray *jt;	/* jump table for gotox or bpf_tailcall call instruction */
 	struct btf_struct_meta *kptr_struct_meta;
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
@@ -820,6 +819,7 @@ struct bpf_subprog_info {
 	 * U32_MAX when it has none.
 	 */
 	u32 exit_idx;
+	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;
@@ -1009,6 +1009,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;
@@ -1587,6 +1588,7 @@ bool bpf_is_throw_kfunc(struct bpf_insn *insn);
 int bpf_compute_const_regs(struct bpf_verifier_env *env);
 int bpf_prune_dead_branches(struct bpf_verifier_env *env);
 int bpf_check_cfg(struct bpf_verifier_env *env);
+void bpf_free_subprog_jts(struct bpf_verifier_env *env);
 int bpf_compute_postorder(struct bpf_verifier_env *env);
 int bpf_compute_scc(struct bpf_verifier_env *env);
 
@@ -1805,7 +1807,6 @@ struct bpf_kfunc_desc_tab {
 };
 
 /* Functions exported from verifier.c, used by fixups.c */
-void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len);
 void bpf_mark_subprog_exc_cb(struct bpf_verifier_env *env, int subprog);
 bool bpf_allow_tail_call_in_subprogs(struct bpf_verifier_env *env);
 bool bpf_verifier_inlines_helper_call(struct bpf_verifier_env *env, s32 imm);
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index f3f545c53264..ee89edd09d36 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 first target lands 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,56 +307,96 @@ 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);
 
 		/*
 		 * This is enough to check one element. The full table is
-		 * checked to fit inside the subprog later in create_jt()
+		 * checked to fit inside the subprog later in subprog_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);
+		subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
+		if (verifier_bug_if(!subprog, env, "no subprog contains insn %u of an insn array map",
+				    jt_cur->items[0])) {
+			kvfree(jt_cur);
+			return -EFAULT;
+		}
+
+		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;
+}
+
+/* Leave nothing behind on failure. */
+static int compute_subprog_jts(struct bpf_verifier_env *env)
+{
+	int err;
+
+	err = __compute_subprog_jts(env);
+	if (err)
+		bpf_free_subprog_jts(env);
+	return err;
+}
+
+void bpf_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 *
-create_jt(int t, struct bpf_verifier_env *env)
+subprog_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);
+	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", t))
+		return ERR_PTR(-EFAULT);
 	subprog_start = subprog->start;
 	subprog_end = (subprog + 1)->start;
-	jt = jt_from_subprog(env, subprog_start, subprog_end);
-	if (IS_ERR(jt))
-		return jt;
+
+	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 = subprog->jt;
 
 	/* Check that the every element of the jump table fits within the given subprogram */
 	for (i = 0; i < jt->cnt; i++) {
@@ -366,7 +408,6 @@ create_jt(int t, struct bpf_verifier_env *env)
 				"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);
 		}
 	}
@@ -383,26 +424,31 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
 	struct bpf_iarray *jt;
 	int i, w;
 
-	jt = env->insn_aux_data[t].jt;
-	if (!jt) {
-		jt = create_jt(t, env);
-		if (IS_ERR(jt))
-			return PTR_ERR(jt);
+	/*
+	 * The first visit pushes every target that still needs exploring, and
+	 * those are all done by the time this insn is revisited, so there is
+	 * nothing left to walk the jump table for.
+	 */
+	if (insn_state[t] & BRANCH)
+		return DONE_EXPLORING;
 
-		env->insn_aux_data[t].jt = jt;
+	jt = subprog_jt(t, env);
+	if (IS_ERR(jt))
+		return PTR_ERR(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(
+	insn_state[t] |= BRANCH;
+
+	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;
-		}
+			"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);
@@ -506,34 +552,6 @@ static int visit_func_ptrs_insn(int t, struct bpf_verifier_env *env,
 	return DONE_EXPLORING;
 }
 
-/*
- * Instructions that can abnormally return from a subprog (tail_call
- * upon success, ld_{abs,ind} upon load failure) have a hidden exit
- * that the verifier must account for.
- */
-static int visit_abnormal_return_insn(struct bpf_verifier_env *env, int t)
-{
-	struct bpf_subprog_info *subprog;
-	struct bpf_iarray *jt;
-	u32 n;
-
-	if (env->insn_aux_data[t].jt)
-		return 0;
-
-	/* A subprogram without an exit has no hidden exit edge to take. */
-	subprog = bpf_find_containing_subprog(env, t);
-	n = subprog->exit_idx == U32_MAX ? 1 : 2;
-	jt = bpf_iarray_realloc(NULL, n);
-	if (!jt)
-		return -ENOMEM;
-
-	jt->items[0] = t + 1;
-	if (n == 2)
-		jt->items[1] = subprog->exit_idx;
-	env->insn_aux_data[t].jt = jt;
-	return 0;
-}
-
 /* Visits the instruction at index t and returns one of the following:
  *  < 0 - an error occurred
  *  DONE_EXPLORING - the instruction was fully explored
@@ -556,13 +574,6 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 	/* All non-branch instructions have a single fall-through edge. */
 	if (BPF_CLASS(insn->code) != BPF_JMP &&
 	    BPF_CLASS(insn->code) != BPF_JMP32) {
-		if (BPF_CLASS(insn->code) == BPF_LD &&
-		    (BPF_MODE(insn->code) == BPF_ABS ||
-		     BPF_MODE(insn->code) == BPF_IND)) {
-			ret = visit_abnormal_return_insn(env, t);
-			if (ret)
-				return ret;
-		}
 		insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
 		return push_insn(t, t + insn_sz, FALLTHROUGH, env);
 	}
@@ -607,11 +618,6 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 				mark_subprog_might_sleep(env, t);
 			if (bpf_helper_changes_pkt_data(insn->imm))
 				mark_subprog_changes_pkt_data(env, t);
-			if (insn->imm == BPF_FUNC_tail_call) {
-				ret = visit_abnormal_return_insn(env, t);
-				if (ret)
-					return ret;
-			}
 		} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 			struct bpf_call_arg_meta meta;
 
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index d49c50dae20a..adc254b1a646 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -480,7 +480,11 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 
 	if (j > i) {
 		struct bpf_prog_aux *aux = env->prog->aux;
-		int move;
+		int move, k;
+
+		/* The removed subprogs own their jump tables. */
+		for (k = i; k < j; k++)
+			kvfree(env->subprog_info[k].jt);
 
 		/* move fake 'exit' subprog as well */
 		move = env->subprog_cnt + 1 - j;
@@ -488,6 +492,9 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 		memmove(env->subprog_info + i,
 			env->subprog_info + j,
 			sizeof(*env->subprog_info) * move);
+		/* The vacated tail still holds copies of the moved entries. */
+		memset(env->subprog_info + i + move, 0,
+		       sizeof(*env->subprog_info) * (j - i));
 		env->subprog_cnt -= j - i;
 
 		/* remove func_info and its aux */
@@ -586,23 +593,6 @@ static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
 	return 0;
 }
 
-/*
- * Clean up dynamically allocated fields of aux data for instructions [start, ...]
- */
-void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len)
-{
-	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
-	int end = start + len;
-	int i;
-
-	for (i = start; i < end; i++) {
-		if (aux_data[i].jt) {
-			kvfree(aux_data[i].jt);
-			aux_data[i].jt = NULL;
-		}
-	}
-}
-
 static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 {
 	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
@@ -615,8 +605,6 @@ static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 	if (bpf_prog_is_offloaded(env->prog->aux))
 		bpf_prog_offload_remove_insns(env, off, cnt);
 
-	bpf_clear_insn_aux_data(env, off, cnt);
-
 	err = bpf_remove_insns(env->prog, off, cnt);
 	if (err)
 		return err;
@@ -1688,6 +1676,8 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
 	env->prog = prog;
 	info[cnt + 1].start = info[cnt].start;
 	info[cnt].start = prog->len - len + 1;
+	/* The patch ends with the exit. */
+	info[cnt].exit_idx = prog->len - 1;
 	env->subprog_cnt++;
 	env->hidden_subprog_cnt++;
 	return 0;
diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
index 16fb7dc43726..cd9523f69298 100644
--- a/kernel/bpf/liveness.c
+++ b/kernel/bpf/liveness.c
@@ -350,14 +350,18 @@ bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
 	struct bpf_iarray *succ, *jt;
 	int insn_sz;
 
-	jt = env->insn_aux_data[idx].jt;
-	if (unlikely(jt))
-		return jt;
-
 	/* pre-allocated array of size up to 2; reset cnt, as it may have been used already */
 	succ = env->succ;
 	succ->cnt = 0;
 
+	/* All gotox of a subprogram share its jump table, see compute_subprog_jts() */
+	if (unlikely(insn_is_gotox(insn))) {
+		jt = bpf_find_containing_subprog(env, idx)->jt;
+		if (verifier_bug_if(!jt, env, "no jump table for gotox insn %u", idx))
+			return succ;
+		return jt;
+	}
+
 	opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)];
 	insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
 	if (opcode_info->can_fallthrough)
@@ -366,6 +370,20 @@ bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
 	if (opcode_info->can_jump)
 		succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1;
 
+	/*
+	 * tail_call upon success and ld_{abs,ind} upon load failure return
+	 * from the subprogram, which is a hidden edge to its exit. A subprogram
+	 * without an exit insn has no exit to model.
+	 */
+	if (unlikely((bpf_helper_call(insn) && insn->imm == BPF_FUNC_tail_call) ||
+		     (BPF_CLASS(insn->code) == BPF_LD &&
+		      (BPF_MODE(insn->code) == BPF_ABS || BPF_MODE(insn->code) == BPF_IND)))) {
+		u32 exit_idx = bpf_find_containing_subprog(env, idx)->exit_idx;
+
+		if (exit_idx != U32_MAX)
+			succ->items[succ->cnt++] = exit_idx;
+	}
+
 	return succ;
 }
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 015909fe6843..80a3d15525b5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -22751,8 +22751,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	release_maps(env);
 	release_btfs(env);
 err_free_env:
-	if (env->insn_aux_data)
-		bpf_clear_insn_aux_data(env, 0, env->insn_aux_data_len);
+	bpf_free_subprog_jts(env);
 	vfree(env->insn_aux_data);
 	kvfree(env->fd_array);
 	bpf_stack_liveness_free(env);
-- 
2.43.0

[PATCH bpf-next v3 06/16] 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.

Close both ends: reject a map that reaches past the subprog holding its
first entry right when it is collected in compute_subprog_jts(), so that
every map of a program with a gotox is confined to one subprog, and
confine the resolved targets of a gotox to its subprog in
check_indirect_jump(). A target inside the subprog is then always in the
jump table the CFG walked, which is the invariant that actually has to
hold. The out-of-range check in visit_gotox_insn() cannot fire any more
once every table is confined and becomes a verifier_bug_if().

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>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/cfg.c                              | 52 ++++++-------------
 kernel/bpf/verifier.c                         | 33 ++++++++++++
 .../selftests/bpf/progs/verifier_gotox.c      |  2 +-
 3 files changed, 51 insertions(+), 36 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index ee89edd09d36..b0bd9ba951df 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -287,7 +287,7 @@ static struct bpf_iarray *jt_from_map(struct bpf_map *map)
 
 /*
  * Collect the jump table of every subprogram that has one, as the combined
- * table of all maps whose first target lands inside that subprogram. All gotox
+ * 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.
  */
@@ -310,16 +310,23 @@ static int __compute_subprog_jts(struct bpf_verifier_env *env)
 		if (IS_ERR(jt_cur))
 			return PTR_ERR(jt_cur);
 
-		/*
-		 * This is enough to check one element. The full table is
-		 * checked to fit inside the subprog later in subprog_jt()
-		 */
 		subprog = bpf_find_containing_subprog(env, jt_cur->items[0]);
 		if (verifier_bug_if(!subprog, env, "no subprog contains insn %u of an insn array map",
 				    jt_cur->items[0])) {
 			kvfree(jt_cur);
 			return -EFAULT;
 		}
+		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
+			verbose(env, "jump table of subprog starting at %u spans multiple subprogs, map id=%d\n",
+				subprog->start, map->id);
+			bpf_diag_program_structure(
+				env, subprog->start, "jump table spans subprograms",
+				"Keep every entry of a jump table inside one subprogram.",
+				"The jump table in map id %d for the subprogram that starts at instruction %u reaches past its end at instruction %u.",
+				map->id, subprog->start, (subprog + 1)->start);
+			kvfree(jt_cur);
+			return -EINVAL;
+		}
 
 		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
 		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
@@ -370,9 +377,7 @@ static struct bpf_iarray *
 subprog_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);
@@ -384,7 +389,6 @@ subprog_jt(int t, struct bpf_verifier_env *env)
 	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", t))
 		return ERR_PTR(-EFAULT);
 	subprog_start = subprog->start;
-	subprog_end = (subprog + 1)->start;
 
 	if (!subprog->jt) {
 		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
@@ -396,23 +400,7 @@ subprog_jt(int t, struct bpf_verifier_env *env)
 		return ERR_PTR(-EINVAL);
 	}
 
-	jt = subprog->jt;
-
-	/* Check that the every element of the jump table fits within the given subprogram */
-	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);
-			return ERR_PTR(-EINVAL);
-		}
-	}
-
-	return jt;
+	return subprog->jt;
 }
 
 /* "conditional jump with N edges" */
@@ -454,15 +442,9 @@ static int visit_gotox_insn(int t, struct bpf_verifier_env *env)
 	mark_prune_point(env, t);
 	for (i = 0; i < jt->cnt; i++) {
 		w = jt->items[i];
-		if (w < 0 || w >= env->prog->len) {
-			verbose(env, "indirect jump out of range from insn %d to %d\n", t, w);
-			bpf_diag_program_structure(
-				env, t, "indirect jump out of range",
-				"Keep indirect jump targets inside the program.",
-				"Instruction %d can jump indirectly to instruction %d, but the program only contains instructions 0 through %d.",
-				t, w, env->prog->len - 1);
-			return -EINVAL;
-		}
+		if (verifier_bug_if(w < 0 || w >= env->prog->len, env,
+				    "indirect jump from insn %d to %d out of range", t, w))
+			return -EFAULT;
 
 		mark_jmp_point(env, w);
 		mark_jump_target(env, w);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 80a3d15525b5..c1d6d217e0e8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19253,10 +19253,25 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
 	return 0;
 }
 
+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;
+}
+
 /* 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_map *map;
 	u32 min_index, max_index;
@@ -19300,6 +19315,24 @@ 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;
+
+	/*
+	 * Maps are confined to a subprog, see compute_subprog_jts(), and the
+	 * targets are sorted and free of duplicates, see sort_insn_array_uniq(),
+	 * so either all of them belong to this subprog or none of them does.
+	 */
+	if (env->gotox_tmp_buf->items[0] < subprog_start)
+		return reject_gotox_out_of_subprog(env, env->gotox_tmp_buf->items[0],
+						   subprog_start, subprog_end);
+	if (env->gotox_tmp_buf->items[n - 1] >= subprog_end)
+		return reject_gotox_out_of_subprog(env, env->gotox_tmp_buf->items[n - 1],
+						   subprog_start, subprog_end);
+
 	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 0e27c2c79c57..4931a77ba0b2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -366,7 +366,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

[PATCH bpf-next v3 07/16] bpf: Don't remove indirect jump targets in the nop removal pass

[Daniel Borkmann]

bpf_opt_remove_nops() drops every ja +0 and may_goto +0 unconditionally.
A gotox target may itself be such a transparent nop: it is a verified
entry of an insn array jump table that is reachable at run time through
the indirect jump. bpf_insn_array_adjust_after_remove() marks it as
INSN_DELETED instead, and bpf_insn_array_ready() skips INSN_DELETED
entries, so the program loads with a hole in its jump table. The x86
JIT, for example, lowers gotox to a raw indirect jump, so executing
that index jumps to the zeroed ips[] slot, that is, to address 0.
Fix by keeping an indirect jump target in place.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: Sandipan Roy <saroy@redhat.com>
Reported-by: James Burton <jamesburton@meta.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/fixups.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index adc254b1a646..d4e54fa42dae 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -727,6 +727,7 @@ int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
 
 int bpf_opt_remove_nops(struct bpf_verifier_env *env)
 {
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
 	bool is_may_goto_0, is_ja;
@@ -738,6 +739,8 @@ int bpf_opt_remove_nops(struct bpf_verifier_env *env)
 
 		if (!is_may_goto_0 && !is_ja)
 			continue;
+		if (aux[i].indirect_target)
+			continue;
 
 		err = verifier_remove_insns(env, i, 1);
 		if (err)
-- 
2.43.0

[PATCH bpf-next v3 08/16] bpf: Clear insn array jitted pointers on map reuse

[Daniel Borkmann]

An insn array records, per entry, the xlated offset, the jitted offset and
a jitted target pointer in ips[]. bpf_insn_array_init() runs when the map
is bound to a program and resets only xlated_off; the jitted offset and the
ips[] pointer are left as the previous owner set them. A program can be
verified and JITed and only then fail to load (e.g. bpf_check_tail_call()).
By that point bpf_prog_update_insn_ptrs() has already filled ips[] with
pointers into that program's JIT image. Thus, the map is handed back for
reuse with the stale pointers intact. If the next program reuses the map,
the stale pointer survives in the now active program's jump table,
pointing into the previous, freed image. Fix by resetting the jitted offset
and the ips[] pointer alongside the xlated offset.

Fixes: b4ce5923e780 ("bpf, x86: add new map type: instructions array")
Reported-by: Sandipan Roy <saroy@redhat.com>
Reported-by: James Burton <jamesburton@meta.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/bpf_insn_array.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index a2f84afe6f7c..5874abd1f743 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -199,12 +199,16 @@ int bpf_insn_array_init(struct bpf_map *map, const struct bpf_prog *prog)
 		return -EBUSY;
 
 	/*
-	 * Reset all the map indexes to the original values.  This is needed,
-	 * e.g., when a replay of verification with different log level should
-	 * be performed.
+	 * Reset the map to its pre-verification state. The xlated and jitted
+	 * offsets and the jitted target pointers are recomputed by the verifier
+	 * and the JIT for this program, so any values left by a previous owner
+	 * must be cleared here.
 	 */
-	for (i = 0; i < map->max_entries; i++)
+	for (i = 0; i < map->max_entries; i++) {
 		values[i].xlated_off = values[i].orig_off;
+		values[i].jitted_off = 0;
+		insn_array->ips[i] = 0;
+	}
 
 	return 0;
 }
-- 
2.43.0

[PATCH bpf-next v3 09/16] bpf: Clear the insn array used flag with release semantics

[Daniel Borkmann]

A program that fails after the JIT ran, for example in bpf_check_tail_call(),
has already stored its jitted offsets and target pointers into the insn array
maps it uses through bpf_prog_update_insn_ptrs() when release_insn_arrays()
hands them back by clearing the used flag with a plain atomic_set(). Nothing
orders those stores before the flag, so on a weakly ordered architecture they
can still be in flight when the next program takes the map: it is acquired
with atomic_xchg() in bpf_insn_array_init() and reset there, and the late
stores then land on top of whatever the new owner has written since, be it
that reset or the pointers its own JIT stored, leaving entries that point
into an image which is about to be freed.

Clear the flag with atomic_set_release() instead, so that everything the
releasing program stored is visible before the map can be acquired again.
This pairs with the fully ordered atomic_xchg() on the acquire side.

Fixes: b4ce5923e780 ("bpf, x86: add new map type: instructions array")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/bpf_insn_array.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index 5874abd1f743..61d6a076dfdb 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -232,7 +232,8 @@ void bpf_insn_array_release(struct bpf_map *map)
 {
 	struct bpf_insn_array *insn_array = cast_insn_array(map);
 
-	atomic_set(&insn_array->used, 0);
+	/* Paired with atomic_xchg() in bpf_insn_array_init(). */
+	atomic_set_release(&insn_array->used, 0);
 }
 
 void bpf_insn_array_adjust(struct bpf_map *map, u32 off, u32 len)
-- 
2.43.0

[PATCH bpf-next v3 10/16] bpf: Retarget indirect jump targets across prologue prepends

[Daniel Borkmann]

A few patches do not expand in place, they prepend: bpf_convert_ctx_accesses()
puts the ctx save for gen_epilogue and the instructions of gen_prologue in
front of insn 0, and bpf_do_misc_fixups() prepends the may_goto counter init
at the start of every subprog that uses may_goto.

They copy the original instruction of 'tgt_idx' into the last slot of the
patch buffer, so it now lives at tgt_idx + delta, and call adjust_jmp_off()
to move direct branches from tgt_idx to tgt_idx + delta.

Nothing does the same for indirect branches, so a BPF_MAP_TYPE_INSN_ARRAY
slot that named tgt_idx keeps naming tgt_idx, which is now the first prepended
instruction, and insn_aux_data[tgt_idx].indirect_target makes the JIT emit
the landing pad there. Add a __bpf_patch_insn_data() variant and pass
BPF_PATCH_MOVE_TARGET at the affected call-sites to fix up the delta. The
poke descriptors of direct tail calls are shifted the same way, and the
original instruction is not searched for by content in that mode, as it
is the last slot by construction.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Fixes: 07ae6c130b46 ("bpf: Add helper to detect indirect jump targets")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf.h         |  2 +-
 kernel/bpf/bpf_insn_array.c |  4 +--
 kernel/bpf/fixups.c         | 56 ++++++++++++++++++++++++++-----------
 3 files changed, 43 insertions(+), 19 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 8594c8aff745..2cf04bba16bb 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -4289,7 +4289,7 @@ struct bpf_prog *bpf_prog_find_from_stack(void);
 int bpf_insn_array_init(struct bpf_map *map, const struct bpf_prog *prog);
 int bpf_insn_array_ready(struct bpf_map *map);
 void bpf_insn_array_release(struct bpf_map *map);
-void bpf_insn_array_adjust(struct bpf_map *map, u32 off, u32 len);
+void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len);
 void bpf_insn_array_adjust_after_remove(struct bpf_map *map, u32 off, u32 len);
 
 #ifdef CONFIG_BPF_SYSCALL
diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
index 61d6a076dfdb..92bbb71576ae 100644
--- a/kernel/bpf/bpf_insn_array.c
+++ b/kernel/bpf/bpf_insn_array.c
@@ -236,7 +236,7 @@ void bpf_insn_array_release(struct bpf_map *map)
 	atomic_set_release(&insn_array->used, 0);
 }
 
-void bpf_insn_array_adjust(struct bpf_map *map, u32 off, u32 len)
+void bpf_insn_array_adjust(struct bpf_map *map, u32 first, u32 len)
 {
 	struct bpf_insn_array *insn_array = cast_insn_array(map);
 	int i;
@@ -245,7 +245,7 @@ void bpf_insn_array_adjust(struct bpf_map *map, u32 off, u32 len)
 		return;
 
 	for (i = 0; i < map->max_entries; i++) {
-		if (insn_array->values[i].xlated_off <= off)
+		if (insn_array->values[i].xlated_off < first)
 			continue;
 		if (insn_array->values[i].xlated_off == INSN_DELETED)
 			continue;
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index d4e54fa42dae..37cf130ebb57 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -214,13 +214,19 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
 }
 #endif
 
+enum bpf_patch_mode {
+	BPF_PATCH_KEEP_TARGET,	/* targets of 'off' keep naming 'off', the first new insn */
+	BPF_PATCH_MOVE_TARGET,	/* targets of 'off' follow the original insn to 'off + len - 1' */
+};
+
 /* single env->prog->insni[off] instruction was replaced with the range
  * insni[off, off + cnt).  Adjust corresponding insn_aux_data by copying
  * [0, off) and [off, end) to new locations, so the patched range stays zero
  */
 static void adjust_insn_aux_data(struct bpf_verifier_env *env,
 				 struct bpf_prog *new_prog, u32 off, u32 cnt,
-				 struct bpf_insn *original_insn)
+				 struct bpf_insn *original_insn,
+				 enum bpf_patch_mode mode)
 {
 	struct bpf_insn_aux_data *data = env->insn_aux_data;
 	struct bpf_insn *insn = new_prog->insnsi;
@@ -253,7 +259,12 @@ static void adjust_insn_aux_data(struct bpf_verifier_env *env,
 		/* Expand insni[off]'s seen count to the patched range. */
 		data[i].seen = old_seen;
 		data[i].zext_dst = bpf_insn_def32(new_prog, insn + i) >= 0;
-		if (!memcmp(insn + i, original_insn, sizeof(struct bpf_insn))) {
+		/*
+		 * In BPF_PATCH_MOVE_TARGET mode the original insn is the last
+		 * slot by construction.
+		 */
+		if (mode == BPF_PATCH_KEEP_TARGET &&
+		    !memcmp(insn + i, original_insn, sizeof(struct bpf_insn))) {
 			data[i].non_stack_access =
 				data[off + cnt - 1].non_stack_access;
 			data[off + cnt - 1].non_stack_access = false;
@@ -277,9 +288,10 @@ static void adjust_insn_aux_data(struct bpf_verifier_env *env,
 	 * new instructions by the above memmove and memset, but the indirect jump target is
 	 * actually the first instruction, so move it back. This also matches with the behavior
 	 * of bpf_insn_array_adjust(), which preserves xlated_off to point to the first new
-	 * instruction.
+	 * instruction. For BPF_PATCH_MOVE_TARGET the original instruction is the last one,
+	 * so the flag already sits where needed.
 	 */
-	if (data[off + cnt - 1].indirect_target) {
+	if (mode == BPF_PATCH_KEEP_TARGET && data[off + cnt - 1].indirect_target) {
 		data[off].indirect_target = 1;
 		data[off + cnt - 1].indirect_target = 0;
 	}
@@ -299,7 +311,7 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
 	}
 }
 
-static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
+static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 first, u32 len)
 {
 	int i;
 
@@ -307,7 +319,7 @@ static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
 		return;
 
 	for (i = 0; i < env->insn_array_map_cnt; i++)
-		bpf_insn_array_adjust(env->insn_array_maps[i], off, len);
+		bpf_insn_array_adjust(env->insn_array_maps[i], first, len);
 }
 
 static void adjust_insn_arrays_after_remove(struct bpf_verifier_env *env, u32 off, u32 len)
@@ -318,7 +330,7 @@ static void adjust_insn_arrays_after_remove(struct bpf_verifier_env *env, u32 of
 		bpf_insn_array_adjust_after_remove(env->insn_array_maps[i], off, len);
 }
 
-static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
+static void adjust_poke_descs(struct bpf_prog *prog, u32 first, u32 len)
 {
 	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
 	int i, sz = prog->aux->size_poke_tab;
@@ -326,7 +338,7 @@ static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
 
 	for (i = 0; i < sz; i++) {
 		desc = &tab[i];
-		if (desc->insn_idx <= off)
+		if (desc->insn_idx < first)
 			continue;
 		desc->insn_idx += len - 1;
 	}
@@ -345,11 +357,14 @@ static bool bpf_rewrite_must_abort(void)
 	return false;
 }
 
-struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
-				     const struct bpf_insn *patch, u32 len)
+static struct bpf_prog *__bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
+					      const struct bpf_insn *patch, u32 len,
+					      enum bpf_patch_mode mode)
 {
 	struct bpf_prog *new_prog;
 	struct bpf_insn_aux_data *new_data = NULL;
+	/* The first slot whose targets move. */
+	u32 first = mode == BPF_PATCH_MOVE_TARGET ? off : off + 1;
 	struct bpf_insn original_insn;
 
 	if (bpf_rewrite_must_abort())
@@ -375,14 +390,20 @@ struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
 				env->insn_aux_data[off].orig_idx);
 		return NULL;
 	}
-	adjust_insn_aux_data(env, new_prog, off, len, &original_insn);
+	adjust_insn_aux_data(env, new_prog, off, len, &original_insn, mode);
 	adjust_subprog_starts(env, off, len);
-	adjust_insn_arrays(env, off, len);
+	adjust_insn_arrays(env, first, len);
 	bpf_adjust_func_ptrs(env, off, len);
-	adjust_poke_descs(new_prog, off, len);
+	adjust_poke_descs(new_prog, first, len);
 	return new_prog;
 }
 
+struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
+				     const struct bpf_insn *patch, u32 len)
+{
+	return __bpf_patch_insn_data(env, off, patch, len, BPF_PATCH_KEEP_TARGET);
+}
+
 /*
  * insn was moved down by delta insns inside its own patch. Operands relative
  * to the pc that point in front of the old position did not move with it.
@@ -883,7 +904,8 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
 						      -subprogs[0].stack_depth);
 			insn_buf[cnt++] = env->prog->insnsi[0];
-			new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
+			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
+							 BPF_PATCH_MOVE_TARGET);
 			if (!new_prog)
 				return -ENOMEM;
 			env->prog = new_prog;
@@ -906,7 +928,8 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			verifier_bug(env, "prologue is too long");
 			return -EFAULT;
 		} else if (cnt) {
-			new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
+			new_prog = __bpf_patch_insn_data(env, 0, insn_buf, cnt,
+							 BPF_PATCH_MOVE_TARGET);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -2666,7 +2689,8 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		}
 		cnt++;
 
-		new_prog = bpf_patch_insn_data(env, subprog_start, insn_buf, cnt);
+		new_prog = __bpf_patch_insn_data(env, subprog_start, insn_buf, cnt,
+						 BPF_PATCH_MOVE_TARGET);
 		if (!new_prog)
 			return -ENOMEM;
 		env->prog = prog = new_prog;
-- 
2.43.0

[PATCH bpf-next v3 11/16] selftests/bpf: Add tests for the indirect jump edge limit

[Daniel Borkmann]

Add tests for the indirect jump edge limit to the verifier_gotox suite: two
programs whose gotox instructions are their own jump table targets, one in
a single subprogram and one split across two, exceed the limit and are
rejected, and a chain of gotox which sits exactly at the limit still loads
and runs.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t verifier_gotox
  [...]
  #644/30  verifier_gotox/too-many-gotox-edges:OK
  #644/31  verifier_gotox/gotox-edges-at-limit:OK
  #644/32  verifier_gotox/gotox-edges-across-subprogs:OK
  #644     verifier_gotox:OK
  Summary: 1/32 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/progs/verifier_gotox.c      | 94 +++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
index 4931a77ba0b2..b917c2e14283 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -457,6 +457,100 @@ __naked void spill_fill_ptr_to_insn(void)
 	: __clobber_all);
 }
 
+/*
+ * Emit each table entry next to the instruction it targets. Numeric labels
+ * can be reused by .rept, while %= keeps table symbols unique per asm block.
+ * BASE is the code section: libbpf relocates section-relative byte offsets
+ * to instruction offsets in the loaded program.
+ */
+#define GOTOX_TABLE_BEGIN(COUNT) \
+	".pushsection .jumptables,\"\",@progbits;" \
+	"jt_%=:;" \
+	".global jt_%=;" \
+	".size jt_%=, 8 * (" #COUNT ");" \
+	".popsection;" \
+	"r1 = jt_%= ll;"
+
+#define GOTOX_TABLE_ENTRY(LABEL, BASE) \
+	".pushsection .jumptables,\"\",@progbits;" \
+	".quad " LABEL " - " BASE ";" \
+	".popsection;"
+
+/* N gotox instructions, each targeting all N gotox plus the final block. */
+#define GOTOX_SELF_TARGETS(N, BASE) \
+	GOTOX_TABLE_BEGIN(N + 1) \
+	"r0 = 0;" \
+	".rept " #N ";" \
+		GOTOX_TABLE_ENTRY("1f", BASE) \
+		"1:; .8byte %[gotox];" \
+	".endr;" \
+	GOTOX_TABLE_ENTRY("2f", BASE) \
+	"2:;"
+
+#define GOTOX_OPERAND \
+	__imm_insn(gotox, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
+
+/*
+ * Count edges even when their targets are already discovered. These
+ * programs deliberately use a scalar: the CFG edge limit must reject them
+ * before symbolic verification reaches the invalid gotox operand.
+ */
+SEC("socket")
+__description("too-many-gotox-edges")
+__failure __msg("number of indirect jump edges in the program exceeds")
+__naked void too_many_gotox_edges(void)
+{
+	asm volatile (
+		/* 1000 * 1001 = 1,001,000 edges. */
+		GOTOX_SELF_TARGETS(1000, "socket")
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+SEC("socket")
+__description("gotox-edges-at-limit")
+__success __retval(0)
+__naked void gotox_edges_at_limit(void)
+{
+	asm volatile (
+		/*
+		 * 1000 gotox * 1000 targets = 1,000,000 CFG edges. At run
+		 * time, each block loads the next table entry and jumps to
+		 * the following block, so the program terminates.
+		 */
+		GOTOX_TABLE_BEGIN(1000)
+		".rept 1000;"
+			GOTOX_TABLE_ENTRY("1f", "socket")
+			"r0 = *(u64 *)(r1 + 0);"
+			"r1 += 8;"
+			".8byte %[gotox];"
+			"1:;"
+		".endr;"
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+static __noinline __used __naked void gotox_edges_subprog(void)
+{
+	asm volatile (
+		GOTOX_SELF_TARGETS(750, ".text")
+		"r0 = 0; exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
+SEC("socket")
+__description("gotox-edges-across-subprogs")
+__failure __msg("number of indirect jump edges in the program exceeds")
+__naked void gotox_edges_across_subprogs(void)
+{
+	asm volatile (
+		/* Each subprog has 563,250 edges; together, 1,126,500. */
+		GOTOX_SELF_TARGETS(750, "socket")
+		"call gotox_edges_subprog;"
+		"exit;"
+		: : GOTOX_OPERAND : __clobber_all);
+}
+
 #endif /* __TARGET_ARCH_x86 || __TARGET_ARCH_arm64 || __TARGET_ARCH_powerpc*/
 
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

[PATCH bpf-next v3 12/16] selftests/bpf: Add a test for a tail call in a subprogram without an exit

[Daniel Borkmann]

Add a test with a subprogram which leaves through a tail call or a
bpf_throw() and never reaches an exit insn, so that the hidden edge of
the tail call has no exit to point at. The subprogram accesses its stack,
so that the liveness pass walks it.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t verifier_cfg
  [...]
  #624/21  verifier_cfg/tail call in a subprogram without an exit:OK
  #624     verifier_cfg:OK
  Summary: 1/21 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/progs/verifier_cfg.c        | 38 +++++++++++++++++++
 1 file changed, 38 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_cfg.c b/tools/testing/selftests/bpf/progs/verifier_cfg.c
index 3c3bb03e8217..07388a922e5b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_cfg.c
+++ b/tools/testing/selftests/bpf/progs/verifier_cfg.c
@@ -173,4 +173,42 @@ l1_%=:	exit;						\
 "	::: __clobber_all);
 }
 
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, __u32);
+	__type(value, __u32);
+} map_array SEC(".maps");
+
+extern void bpf_throw(__u64 cookie) __ksym;
+
+/*
+ * The subprogram leaves through the tail call or the exception and never
+ * reaches an exit insn, so the hidden edge of the tail call has no exit to
+ * point at. The stack access makes the liveness pass walk the subprogram,
+ * and the loop compiles to a single jump back onto itself.
+ */
+__noinline __used
+static int tail_call_or_throw_subprog(void *ctx)
+{
+	volatile __u32 idx = 0;
+
+	bpf_tail_call(ctx, &map_array, idx);
+	bpf_throw(0);
+	for (;;) {}
+}
+
+SEC("tc")
+__description("tail call in a subprogram without an exit")
+__arch_x86_64
+__arch_arm64
+__success
+__naked void tail_call_in_subprog_without_exit(void)
+{
+	asm volatile ("					\
+	call tail_call_or_throw_subprog;		\
+	exit;						\
+"	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

[PATCH bpf-next v3 13/16] selftests/bpf: Add tests for indirect jumps across subprograms

[Daniel Borkmann]

Add various gotox corner case tests for indirect jumps across subprograms,
and one where two subprograms only called from dead code sit in front of
the one owning a jump table, so that their removal compacts subprog_info[]
along with the tables.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t bpf_insn_array,verifier_gotox
  [...]
  #27/10   bpf_insn_array/gotox-jt-spans-subprogs:OK
  #27/11   bpf_insn_array/gotox-jt-spans-with-own-table:OK
  #27/12   bpf_insn_array/gotox-target-other-subprog:OK
  #27/13   bpf_insn_array/gotox-jt-per-subprog:OK
  #27/14   bpf_insn_array/gotox-jt-dead-subprogs:OK
  #27/15   bpf_insn_array/gotox-target-subprog-from-main:OK
  #27/16   bpf_insn_array/gotox-index-slice-other-subprog:OK
  #27/17   bpf_insn_array/gotox-target-other-global-subprog:OK
  #27/18   bpf_insn_array/gotox-callback-leaves-subprog:OK
  #27      bpf_insn_array:OK
  [...]
  #644     verifier_gotox:OK
  Summary: 2/50 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/prog_tests/bpf_insn_array.c | 541 ++++++++++++++++++
 1 file changed, 541 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..40e183269fb6 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__)
@@ -453,6 +454,519 @@ static void check_bpf_no_lookup(void)
 	close(map_fd);
 }
 
+#define GOTOX_LOG_SZ		(256 * 1024)
+
+/* Load and return the fd, which the caller owns. */
+static int gotox_prog_load_funcs_fd(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);
+
+	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;
+	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);
+	}
+
+	return bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
+}
+
+/* Load for the outcome only: 0 or the negative errno. */
+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)
+{
+	int prog_fd;
+
+	prog_fd = gotox_prog_load_funcs_fd(insns, insn_cnt, fd_array, fd_array_cnt, log,
+					   btf_fd, fi, fi_cnt);
+	if (prog_fd < 0)
+		return prog_fd;
+	close(prog_fd);
+	return 0;
+}
+
+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);
+}
+
+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();
+}
+
+/*
+ * Load 'insns' with the two jump tables 'jt_a' and 'jt_b', in this order in
+ * fd_array, and check the outcome. 'fi' describes the subprograms when given.
+ */
+static void check_gotox_two_maps(struct bpf_insn *insns, __u32 insn_cnt,
+				 const __u32 *jt_a, __u32 a_cnt,
+				 const __u32 *jt_b, __u32 b_cnt,
+				 int btf_fd, struct bpf_func_info *fi, __u32 fi_cnt,
+				 int expect_err, const char *expect_msg)
+{
+	int map_fd[2] = { -1, -1 };
+	char *log;
+	int err;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	map_fd[0] = gotox_jt_create_offs(jt_a, a_cnt);
+	if (map_fd[0] < 0)
+		goto free_log;
+	map_fd[1] = gotox_jt_create_offs(jt_b, b_cnt);
+	if (map_fd[1] < 0)
+		goto close_maps;
+
+	if (fi)
+		err = gotox_prog_load_funcs(insns, insn_cnt, map_fd, 2, log,
+					    btf_fd, fi, fi_cnt);
+	else
+		err = gotox_prog_load(insns, insn_cnt, map_fd, 2, log);
+	if (expect_err)
+		ASSERT_EQ(err, expect_err, "program should have been rejected");
+	else
+		ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)");
+	if (expect_msg)
+		ASSERT_HAS_SUBSTR(log, expect_msg, "verifier log");
+
+close_maps:
+	close(map_fd[0]);
+	if (map_fd[1] >= 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];
+
+	gotox_two_subprogs_fill(insns, 0, 0);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_main, ARRAY_SIZE(jt_main),
+			     jt_sub, ARRAY_SIZE(jt_sub), -1, NULL, 0,
+			     -EINVAL, "indirect jump from insn 7 to 2 leaves the subprog [4,10)");
+}
+
+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];
+
+	gotox_two_subprogs_fill(insns, 1, 0);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_main, ARRAY_SIZE(jt_main),
+			     jt_sub, ARRAY_SIZE(jt_sub), -1, NULL, 0,
+			     0, NULL);
+}
+
+#define GOTOX_DEAD_MAIN_LEN	7
+#define GOTOX_DEAD_SUB_LEN	6
+#define GOTOX_DEAD_INSN_CNT	(GOTOX_DEAD_MAIN_LEN + 3 * GOTOX_DEAD_SUB_LEN)
+#define GOTOX_DEAD_LIVE_CNT	10
+
+/* r1 = &jt[0], by index 'jt_idx' into fd_array; r1 = *r1; gotox r1; r0 = 0; exit */
+static void gotox_sub_fill(struct bpf_insn *insns, __u32 start, __u32 jt_idx)
+{
+	insns[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[start + 1] = (struct bpf_insn) { .imm = 0 };
+	insns[start + 2] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
+	insns[start + 3] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
+	insns[start + 4] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[start + 5] = BPF_EXIT_INSN();
+}
+
+/*
+ * Two subprograms which are only called from dead code sit in front of the
+ * live one, and all three own a jump table. Dead code removal drops both in
+ * one go, which compacts subprog_info[] along with the tables.
+ */
+static void check_gotox_jt_dead_subprogs(void)
+{
+	const __u32 sub_start[3] = { GOTOX_DEAD_MAIN_LEN,
+				     GOTOX_DEAD_MAIN_LEN + GOTOX_DEAD_SUB_LEN,
+				     GOTOX_DEAD_MAIN_LEN + 2 * GOTOX_DEAD_SUB_LEN };
+	struct bpf_insn insns[GOTOX_DEAD_INSN_CNT];
+	int map_fd[3] = { -1, -1, -1 };
+	struct bpf_prog_info info = {};
+	__u32 len = sizeof(info), tgt, i;
+	int prog_fd;
+	char *log;
+
+	log = calloc(1, GOTOX_LOG_SZ);
+	if (!ASSERT_OK_PTR(log, "calloc log"))
+		return;
+
+	insns[0] = BPF_MOV64_IMM(BPF_REG_1, 0);
+	insns[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 2);
+	insns[2] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				sub_start[0] - 2 - 1);
+	insns[3] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				sub_start[1] - 3 - 1);
+	insns[4] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0,
+				sub_start[2] - 4 - 1);
+	insns[5] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insns[6] = BPF_EXIT_INSN();
+
+	for (i = 0; i < ARRAY_SIZE(sub_start); i++) {
+		gotox_sub_fill(insns, sub_start[i], i);
+		tgt = sub_start[i] + 4;
+		map_fd[i] = gotox_jt_create_offs(&tgt, 1);
+		if (map_fd[i] < 0)
+			goto close_maps;
+	}
+
+	prog_fd = gotox_prog_load_funcs_fd(insns, ARRAY_SIZE(insns), map_fd,
+					   ARRAY_SIZE(map_fd), log, -1, NULL, 0);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto close_maps;
+
+	/* Both dead subprograms and the calls to them must be gone. */
+	if (ASSERT_OK(bpf_prog_get_info_by_fd(prog_fd, &info, &len),
+		      "bpf_prog_get_info_by_fd"))
+		ASSERT_EQ(info.xlated_prog_len / sizeof(struct bpf_insn),
+			  GOTOX_DEAD_LIVE_CNT, "xlated insn count");
+	close(prog_fd);
+close_maps:
+	for (i = 0; i < ARRAY_SIZE(map_fd); i++)
+		if (map_fd[i] >= 0)
+			close(map_fd[i]);
+	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];
+
+	gotox_from_main_fill(insns);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_own, ARRAY_SIZE(jt_own),
+			     jt_leaves, ARRAY_SIZE(jt_leaves), -1, NULL, 0,
+			     -EINVAL, "indirect jump from insn 11 to 14 leaves the subprog [0,14)");
+}
+
+/*
+ * 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];
+
+	gotox_from_main_fill(insns);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_span, ARRAY_SIZE(jt_span),
+			     jt_leaves, ARRAY_SIZE(jt_leaves), -1, NULL, 0,
+			     -EINVAL, "jump table of subprog starting at 0 spans multiple subprogs");
+}
+
+/*
+ * 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];
+
+	gotox_from_main_fill(insns);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_own, ARRAY_SIZE(jt_own),
+			     jt_span, ARRAY_SIZE(jt_span), -1, NULL, 0,
+			     -EINVAL, "jump table of subprog starting at 0 spans multiple subprogs");
+}
+
+#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];
+
+	gotox_slice_fill(insns);
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_main, ARRAY_SIZE(jt_main),
+			     jt_sub, ARRAY_SIZE(jt_sub), -1, NULL, 0,
+			     -EINVAL, "indirect jump from insn 14 to 3 leaves the subprog [6,17)");
+}
+
+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];
+	struct bpf_func_info fi[2];
+	struct btf *btf = NULL;
+	int btf_fd;
+
+	gotox_two_subprogs_fill(insns, 0, 0);
+
+	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
+	if (btf_fd < 0)
+		return;
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_main, ARRAY_SIZE(jt_main),
+			     jt_sub, ARRAY_SIZE(jt_sub), btf_fd, fi, ARRAY_SIZE(fi),
+			     -EINVAL, "indirect jump from insn 7 to 2 leaves the subprog [4,10)");
+	btf__free(btf);
+}
+
+#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];
+	struct bpf_func_info fi[2];
+	struct btf *btf = NULL;
+	int btf_fd;
+
+	gotox_callback_fill(insns);
+
+	btf_fd = gotox_btf_create(starts, linkage, ARRAY_SIZE(starts), fi, &btf);
+	if (btf_fd < 0)
+		return;
+
+	check_gotox_two_maps(insns, ARRAY_SIZE(insns), jt_main, ARRAY_SIZE(jt_main),
+			     jt_cb, ARRAY_SIZE(jt_cb), btf_fd, fi, ARRAY_SIZE(fi),
+			     -EINVAL, "indirect jump from insn 11 to 6 leaves the subprog [8,14)");
+	btf__free(btf);
+}
+
 static void check_bpf_side(void)
 {
 	check_bpf_no_lookup();
@@ -490,6 +1004,33 @@ static void __test_bpf_insn_array(void)
 
 	if (test__start_subtest("bpf-side-ops"))
 		check_bpf_side();
+
+	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-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-jt-dead-subprogs"))
+		check_gotox_jt_dead_subprogs();
+
+	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

[PATCH bpf-next v3 14/16] selftests/bpf: Add a test for gotox nop targets

[Daniel Borkmann]

Add a test to the verifier_gotox suite which exercises a gotox target which
is a ja +0, and checks that the nop removal pass keeps it.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t verifier_gotox
  [...]
  #644/33  verifier_gotox/jump_table_target_nop:OK
  #644     verifier_gotox:OK
  Summary: 1/33 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/progs/verifier_gotox.c      | 29 +++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
index b917c2e14283..f5a9878c7b8d 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -551,6 +551,35 @@ __naked void gotox_edges_across_subprogs(void)
 		: : GOTOX_OPERAND : __clobber_all);
 }
 
+/*
+ * The gotox target is a ja +0, which the nop removal pass must keep as the
+ * jump table still names it.
+ */
+SEC("socket")
+__success __retval(0)
+__xlated("goto pc+0")
+__naked void jump_table_target_nop(void)
+{
+	asm volatile ("						\
+	.pushsection .jumptables,\"\",@progbits;		\
+jt0_%=:								\
+	.quad nop_%= - socket;					\
+	.size jt0_%=, 8;					\
+	.global jt0_%=;						\
+	.popsection;						\
+								\
+	r0 = jt0_%= ll;						\
+	r0 = *(u64 *)(r0 + 0);					\
+	.8byte %[gotox_r0];					\
+nop_%=:								\
+	goto +0;						\
+	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm_insn(gotox_r0, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_0, 0, 0, 0))
+	: __clobber_all);
+}
+
 #endif /* __TARGET_ARCH_x86 || __TARGET_ARCH_arm64 || __TARGET_ARCH_powerpc*/
 
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

[PATCH bpf-next v3 15/16] selftests/bpf: Add tests for gotox targets across prologue prepends

[Daniel Borkmann]

Add tests to the bpf_insn_array suite for a gotox whose jump table points
at the first instruction of a subprogram.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t bpf_insn_array
  [...]
  #27/19   bpf_insn_array/gotox-target-prologue-shift:OK
  #27/20   bpf_insn_array/gotox-target-ctx-prologue-shift:OK
  #27      bpf_insn_array:OK
  Summary: 1/20 PASSED, 0 SKIPPED, 0/0 FAILED

As small nit, cleanup the extra whitespaces between subtests.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
---
 .../selftests/bpf/prog_tests/bpf_insn_array.c | 127 +++++++++++++++---
 1 file changed, 108 insertions(+), 19 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 40e183269fb6..bfedeed24ac5 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
@@ -972,65 +972,154 @@ static void check_bpf_side(void)
 	check_bpf_no_lookup();
 }
 
+/* Return the xlated index of the first insn equal to 'insn', or -1. */
+static int xlated_insn_index(int prog_fd, const struct bpf_insn *insn)
+{
+	struct bpf_insn *xlated;
+	int idx = -1;
+	__u32 cnt, i;
+
+	if (!ASSERT_OK(get_xlated_program(prog_fd, &xlated, &cnt), "get_xlated_program"))
+		return -1;
+	for (i = 0; i < cnt; i++)
+		if (!memcmp(&xlated[i], insn, sizeof(*insn))) {
+			idx = i;
+			break;
+		}
+	free(xlated);
+	return idx;
+}
+
+/*
+ * Load 'insns' with a jump table naming insn 0, which a prologue prepend
+ * pushes down, and check that the slot followed it.
+ */
+static void check_gotox_target_prepend(enum bpf_prog_type prog_type,
+				       struct bpf_insn *insns, __u32 insn_cnt)
+{
+	LIBBPF_OPTS(bpf_prog_load_opts, opts);
+	struct bpf_insn_array_value val = {};
+	int prog_fd = -1, map_fd, idx;
+	__u32 key = 0;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	val.orig_off = 0;
+	if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &key, &val, 0), 0, "bpf_map_update_elem"))
+		goto cleanup;
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	opts.fd_array = &map_fd;
+	opts.fd_array_cnt = 1;
+	prog_fd = bpf_prog_load(prog_type, NULL, "GPL", insns, insn_cnt, &opts);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	idx = xlated_insn_index(prog_fd, &insns[0]);
+	if (!ASSERT_GT(idx, 0, "insn 0 was prepended to"))
+		goto cleanup;
+	if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &key, &val), 0, "bpf_map_lookup_elem"))
+		goto cleanup;
+	ASSERT_EQ(val.xlated_off, (__u32)idx, "gotox target followed insn 0 past the prepend");
+cleanup:
+	if (prog_fd >= 0)
+		close(prog_fd);
+	close(map_fd);
+}
+
+static void check_gotox_target_prologue_shift(void)
+{
+	struct bpf_insn insns[] = {
+		/* insn 0: gotox target and subprog start */
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		/* may_goto +4 -> exit block, bounds the loop */
+		BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 4, 0),
+		/* r1 = &jt[0] (insns 2 and 3) */
+		BPF_LD_IMM64_RAW(BPF_REG_1, BPF_PSEUDO_MAP_IDX_VALUE, 0),
+		BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0), /* r1 = ips[0] */
+		/* insn 5: gotox r1 -> insn 0 */
+		BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0),
+		BPF_MOV64_IMM(BPF_REG_0, XDP_PASS), /* insn 6: exit block */
+		BPF_EXIT_INSN(),
+	};
+
+	check_gotox_target_prepend(BPF_PROG_TYPE_XDP, insns, ARRAY_SIZE(insns));
+}
+
+static void check_gotox_target_ctx_prologue_shift(void)
+{
+	struct bpf_insn insns[] = {
+		/* insn 0: gotox target and subprog start */
+		BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, -8),
+		BPF_JMP_IMM(BPF_JEQ, BPF_REG_7, 0x5a5a, 12), /* second visit exits */
+		BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0x5a5a),
+		BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), /* r6 = ctx */
+		BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_6, offsetof(struct __sk_buff, data)),
+		BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_6, offsetof(struct __sk_buff, data_end)),
+		BPF_MOV64_REG(BPF_REG_4, BPF_REG_2),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 1),
+		BPF_JMP_REG(BPF_JGT, BPF_REG_4, BPF_REG_3, 5),
+		/* insn 9: direct packet write -> tc unclone prologue prepended at insn 0 */
+		BPF_ST_MEM(BPF_B, BPF_REG_2, 0, 0),
+		/* r5 = &jt[0] (insns 10 and 11) */
+		BPF_LD_IMM64_RAW(BPF_REG_5, BPF_PSEUDO_MAP_IDX_VALUE, 0),
+		BPF_LDX_MEM(BPF_DW, BPF_REG_5, BPF_REG_5, 0), /* r5 = ips[0] */
+		/* insn 13: gotox r5 -> insn 0 */
+		BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_5, 0, 0, 0),
+		BPF_MOV64_IMM(BPF_REG_0, 0), /* insn 14: exit block */
+		BPF_EXIT_INSN(),
+	};
+
+	check_gotox_target_prepend(BPF_PROG_TYPE_SCHED_CLS, insns, ARRAY_SIZE(insns));
+}
+
 static void __test_bpf_insn_array(void)
 {
 	/* Test if offsets are adjusted properly */
-
 	if (test__start_subtest("one2one"))
 		check_one_to_one_mapping();
-
 	if (test__start_subtest("simple"))
 		check_simple();
-
 	if (test__start_subtest("deletions"))
 		check_deletions();
-
 	if (test__start_subtest("deletions-with-functions"))
 		check_deletions_with_functions();
-
 	if (test__start_subtest("blindness"))
 		check_blindness();
-
 	/* Check all kinds of operations and related restrictions */
-
 	if (test__start_subtest("incorrect-index"))
 		check_incorrect_index();
-
 	if (test__start_subtest("load-unfrozen-map"))
 		check_load_unfrozen_map();
-
 	if (test__start_subtest("no-map-reuse"))
 		check_no_map_reuse();
-
 	if (test__start_subtest("bpf-side-ops"))
 		check_bpf_side();
-
 	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-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-jt-dead-subprogs"))
 		check_gotox_jt_dead_subprogs();
-
 	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();
+	if (test__start_subtest("gotox-target-prologue-shift"))
+		check_gotox_target_prologue_shift();
+	if (test__start_subtest("gotox-target-ctx-prologue-shift"))
+		check_gotox_target_ctx_prologue_shift();
 }
 #else
 static void __test_bpf_insn_array(void)
-- 
2.43.0

[PATCH bpf-next v3 16/16] selftests/bpf: Add a test for an exception callback behind a dead subprog

[Daniel Borkmann]

Add a test where a static subprogram only called from dead code sits in
front of the exception callback, so that its removal compacts
subprog_info[] underneath the callback's index.

  # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t exceptions
  [...]
  #129/119 exceptions/exception_cb_behind_dead_subprog:OK
  #129     exceptions:OK
  Summary: 1/119 PASSED, 0 SKIPPED, 0/0 FAILED

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../selftests/bpf/prog_tests/exceptions.c     |  7 ++++
 .../bpf/progs/exceptions_dead_subprog.c       | 40 +++++++++++++++++++
 2 files changed, 47 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_dead_subprog.c

diff --git a/tools/testing/selftests/bpf/prog_tests/exceptions.c b/tools/testing/selftests/bpf/prog_tests/exceptions.c
index 639866ce09a9..3705db18c1bb 100644
--- a/tools/testing/selftests/bpf/prog_tests/exceptions.c
+++ b/tools/testing/selftests/bpf/prog_tests/exceptions.c
@@ -6,6 +6,7 @@
 #include "exceptions_ext.skel.h"
 #include "exceptions_fail.skel.h"
 #include "exceptions_assert.skel.h"
+#include "exceptions_dead_subprog.skel.h"
 
 static char log_buf[1024 * 1024];
 
@@ -410,9 +411,15 @@ static void test_exceptions_assertions(void)
 	RUN_TESTS(exceptions_assert);
 }
 
+static void test_exceptions_dead_subprog(void)
+{
+	RUN_TESTS(exceptions_dead_subprog);
+}
+
 void test_exceptions(void)
 {
 	test_exceptions_success();
 	test_exceptions_failure();
 	test_exceptions_assertions();
+	test_exceptions_dead_subprog();
 }
diff --git a/tools/testing/selftests/bpf/progs/exceptions_dead_subprog.c b/tools/testing/selftests/bpf/progs/exceptions_dead_subprog.c
new file mode 100644
index 000000000000..4f8b82a85234
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/exceptions_dead_subprog.c
@@ -0,0 +1,40 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+#include "bpf_experimental.h"
+
+/*
+ * Read-only and frozen, so the verifier sees a constant zero, while clang
+ * cannot fold the volatile read and keeps the call below.
+ */
+const volatile int never;
+
+/* Only called from dead code, hence removed as a whole before the JIT runs. */
+static __noinline int dead_subprog(struct __sk_buff *ctx)
+{
+	return ctx->len;
+}
+
+__noinline int exception_cb_behind_dead_subprog_cb(u64 cookie)
+{
+	return 42;
+}
+
+/*
+ * libbpf appends the exception callback behind the subprograms reached by
+ * calls, so removing the dead one compacts subprog_info[] underneath the
+ * callback's index.
+ */
+SEC("?tc")
+__exception_cb(exception_cb_behind_dead_subprog_cb)
+__success __retval(42)
+int exception_cb_behind_dead_subprog(struct __sk_buff *ctx)
+{
+	if (never)
+		return dead_subprog(ctx);
+	bpf_throw(0);
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.43.0

Re: [PATCH bpf-next v3 13/16] selftests/bpf: Add tests for indirect jumps across subprograms

[bot+bpf-ci]

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

> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> index 0222a9a5d076..40e183269fb6 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c

[ ... ]

> +/*
> + * Load 'insns' with the two jump tables 'jt_a' and 'jt_b', in this order in
> + * fd_array, and check the outcome. 'fi' describes the subprograms when given.
> + */
> +static void check_gotox_two_maps(struct bpf_insn *insns, __u32 insn_cnt,
> +				 const __u32 *jt_a, __u32 a_cnt,
> +				 const __u32 *jt_b, __u32 b_cnt,
> +				 int btf_fd, struct bpf_func_info *fi, __u32 fi_cnt,
> +				 int expect_err, const char *expect_msg)
> +{
> +	int map_fd[2] = { -1, -1 };
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	map_fd[0] = gotox_jt_create_offs(jt_a, a_cnt);
> +	if (map_fd[0] < 0)
> +		goto free_log;
> +	map_fd[1] = gotox_jt_create_offs(jt_b, b_cnt);
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	if (fi)
> +		err = gotox_prog_load_funcs(insns, insn_cnt, map_fd, 2, log,
> +					    btf_fd, fi, fi_cnt);
> +	else
> +		err = gotox_prog_load(insns, insn_cnt, map_fd, 2, log);

This isn't a bug, but is the if (fi) split needed here? Calling
gotox_prog_load_funcs() unconditionally looks equivalent, since it
already skips BTF setup for fi_cnt == 0, and that would make
gotox_prog_load() unnecessary.

> +	if (expect_err)
> +		ASSERT_EQ(err, expect_err, "program should have been rejected");
> +	else
> +		ASSERT_EQ(err, 0, "bpf(BPF_PROG_LOAD)");
> +	if (expect_msg)
> +		ASSERT_HAS_SUBSTR(log, expect_msg, "verifier log");
> +
> +close_maps:
> +	close(map_fd[0]);
> +	if (map_fd[1] >= 0)
> +		close(map_fd[1]);
> +free_log:
> +	free(log);
> +}

[ ... ]

> +#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();
> +}

[ ... ]

> +/* r1 = &jt[0], by index 'jt_idx' into fd_array; r1 = *r1; gotox r1; r0 = 0; exit */
> +static void gotox_sub_fill(struct bpf_insn *insns, __u32 start, __u32 jt_idx)
> +{
> +	insns[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[start + 1] = (struct bpf_insn) { .imm = 0 };
> +	insns[start + 2] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
> +	insns[start + 3] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	insns[start + 4] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[start + 5] = BPF_EXIT_INSN();
> +}

This isn't a bug, but could gotox_two_subprogs_fill() reuse
gotox_sub_fill() for its subprogram half? The jt_off argument looks
like it is always 0 at every call site.

[ ... ]


---
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/36171663872

Re: [PATCH bpf-next v3 05/16] bpf: Cache the jump table of a subprogram during CFG discovery

[Alexei Starovoitov]

On Fri, Sep 25, 2026 at 07:52 PM Daniel Borkmann <daniel@iogearbox.net> wrote:
> Subprograms removed as dead code free their table in
> adjust_subprog_starts_after_remove(), which also clears the slots that
> the compaction of subprog_info vacates, as they still hold copies of the
> moved entries and with them their table pointers.

can we free the tables right after bpf_compute_live_registers() ?
bpf_insn_successors() is the only reader and nothing calls it
after that point.
can be a follow up...

Re: [PATCH bpf-next v3 00/16] Misc BPF gotox fixes

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Fri, 25 Sep 2026 19:52:27 +0200 you wrote:
> Address various open issues around gotox instruction, see individual
> commits for details. Also BPF selftests are added to assert that these
> are addressed.
> 
> v2 -> v3:
>   - Rebased onto bpf-next given indirect call series landed
>   - Split out the exit_idx sentinel as its own fix (Eduard)
>   - Return early from visit_gotox_insn() on a revisited gotox (Eduard)
>   - Check both ends of the target slice in check_indirect_jump() (Eduard)
>   - Rewrite edge limit and nop target tests in inline asm (Eduard)
>   - Name the patch modes BPF_PATCH_{KEEP,MOVE}_TARGET (Eduard)
>   - Drop the insn array stale reuse test (Eduard)
>   - Clear the insn array used flag with release semantics (sashiko)
>   - Add fix for the exception callback index after dead subprog removal
>   - Free the jump tables of removed subprogs and on a failed table build
>   - Shift the poke descriptors along with the insn array slots
> v1 -> v2:
>   - Remove jt_spans_subprogs and reject right away (Eduard)
>   - Rework jump table to no longer keep it in insn_aux_data (Eduard)
>   - Fix up comments in bpf_compute_scc (Eduard)
>   - Fix up commit message nit wrt signed_loader (Anton)
>   - Added 3 more fixes related to gotox along with BPF selftests
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3,01/16] bpf: Avoid quadratic successor rescan in bpf_compute_scc
    https://git.kernel.org/bpf/bpf-next/c/3852e19cb954
  - [bpf-next,v3,02/16] bpf: Bound the number of indirect jump edges in a program
    https://git.kernel.org/bpf/bpf-next/c/57f6eca2f63b
  - [bpf-next,v3,03/16] bpf: Rebase the exception callback subprog when dead subprogs are removed
    https://git.kernel.org/bpf/bpf-next/c/8608ec8e9819
  - [bpf-next,v3,04/16] bpf: Leave out the hidden exit edge of a subprogram without an exit
    https://git.kernel.org/bpf/bpf-next/c/939bb6270ee3
  - [bpf-next,v3,05/16] bpf: Cache the jump table of a subprogram during CFG discovery
    https://git.kernel.org/bpf/bpf-next/c/fa5ebade2a54
  - [bpf-next,v3,06/16] bpf: Reject indirect jumps that leave their subprogram
    https://git.kernel.org/bpf/bpf-next/c/19581372dd81
  - [bpf-next,v3,07/16] bpf: Don't remove indirect jump targets in the nop removal pass
    https://git.kernel.org/bpf/bpf-next/c/c48a91c049fd
  - [bpf-next,v3,08/16] bpf: Clear insn array jitted pointers on map reuse
    https://git.kernel.org/bpf/bpf-next/c/9aa11c4656b7
  - [bpf-next,v3,09/16] bpf: Clear the insn array used flag with release semantics
    https://git.kernel.org/bpf/bpf-next/c/a83512036e08
  - [bpf-next,v3,10/16] bpf: Retarget indirect jump targets across prologue prepends
    https://git.kernel.org/bpf/bpf-next/c/fba62d33c125
  - [bpf-next,v3,11/16] selftests/bpf: Add tests for the indirect jump edge limit
    https://git.kernel.org/bpf/bpf-next/c/db8c58c83f5a
  - [bpf-next,v3,12/16] selftests/bpf: Add a test for a tail call in a subprogram without an exit
    https://git.kernel.org/bpf/bpf-next/c/5add2c64f474
  - [bpf-next,v3,13/16] selftests/bpf: Add tests for indirect jumps across subprograms
    https://git.kernel.org/bpf/bpf-next/c/17c7d885efe8
  - [bpf-next,v3,14/16] selftests/bpf: Add a test for gotox nop targets
    https://git.kernel.org/bpf/bpf-next/c/2cc0a520a8e7
  - [bpf-next,v3,15/16] selftests/bpf: Add tests for gotox targets across prologue prepends
    https://git.kernel.org/bpf/bpf-next/c/28e458bbb44b
  - [bpf-next,v3,16/16] selftests/bpf: Add a test for an exception callback behind a dead subprog
    https://git.kernel.org/bpf/bpf-next/c/91ed1942edef

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html