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

[Daniel Borkmann <daniel@iogearbox.net>]

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

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

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

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

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

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