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