From: Qiliang Yuan When bpf_jit_harden is on, the constants of a prog must not be in the JITed code. bpf_jit_blind_constants() replaces each insn that has a constant with 3 or 4 insns that calculate it. It patches each of these insns immediately, with bpf_patch_insn_data() or bpf_patch_insn_single(). Each call costs O(N) in a prog of N insns. One prog of test_verifier has a million insns: "ld_dw: xor semi-random 64 bit imms, test 5". With bpf_jit_harden=2 it does not load in 15 minutes. Queue the patches in the patch list, and commit one time at the end of the pass. bpf_patch_list_commit() needs bpf_verifier_env (env). But the pass also runs without env, for example for classic BPF progs. Add bpf_patch_list_apply(), the commit without env. In that case the list is a local variable of the pass. step bpf_patch_list_commit() bpf_patch_list_apply() ----------------- ---------------------------- ---------------------- all that can fail new image, aux data, prog new image, prog removed insns offload device, aux data WARN, -EINVAL the tables of the verifier, of the prog of the prog the new image insns, prog->len insns, prog->len - No pass without env removes insns. Thus bpf_patch_list_apply() rejects a list that has a removal. - bpf_jit_blind_insn() does not change. It writes a jump as if its patch was the only one, and that is the rule of the list. - The reallocation of the prog is the last thing that can fail. Thus an error leaves 'clone' valid, and the pass can free it. - With env, a jump that gets out of range gives -ERANGE, and the message names the jump. Before this patch the pass returns -ENOMEM, and the message names the patched insn. - core.c is also built without the verifier, when CONFIG_BPF_SYSCALL is off. Add stubs for the functions of the verifier that the pass calls. Load times with bpf_jit_harden=2 in an x86_64 VM with 8 vCPUs, before and after this patch. Wall time of 'veristat -q ', mean of 10 runs, and one run of test 5: before after pyperf180 1.222 s 0.087 s pyperf600 3.538 s 0.222 s test 5 > 900 s 1.5 s Signed-off-by: Qiliang Yuan Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 17 ++++++ kernel/bpf/core.c | 103 +++++++++++++++++++++++------------ 2 files changed, 86 insertions(+), 34 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index f8498de5eff5..65313a26abb2 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -2081,10 +2081,27 @@ int bpf_jit_subprogs(struct bpf_verifier_env *env); int bpf_fixup_call_args(struct bpf_verifier_env *env); int bpf_do_misc_fixups(struct bpf_verifier_env *env); int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn); +#ifdef CONFIG_BPF_SYSCALL struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off, const struct bpf_insn *patch, u32 len); int bpf_patch_list_commit(struct bpf_verifier_env *env); void bpf_patch_list_free(struct bpf_verifier_env *env); +#else +static inline struct bpf_insn *bpf_patch_list_add(struct bpf_verifier_env *env, u32 off, + const struct bpf_insn *patch, u32 len) +{ + return ERR_PTR(-EOPNOTSUPP); +} + +static inline int bpf_patch_list_commit(struct bpf_verifier_env *env) +{ + return -EOPNOTSUPP; +} + +static inline void bpf_patch_list_free(struct bpf_verifier_env *env) +{ +} +#endif int bpf_patch_list_del(struct bpf_verifier_env *env, u32 off); int bpf_patch_list_insert(struct bpf_verifier_env *env, u32 off, const struct bpf_insn *insns, u32 cnt); diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index 2deb5584dc85..b9d9d0de5b92 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -1963,17 +1963,48 @@ void bpf_jit_prog_release_other(struct bpf_prog *fp, struct bpf_prog *fp_other) bpf_prog_clone_free(fp_other); } +/* + * Apply the patches queued for 'prog' without a verifier env, which can't + * remove insns. Return the patched program, which may have moved. + */ +static struct bpf_prog *bpf_patch_list_apply(struct bpf_prog *prog, struct bpf_patch_list *pl) +{ + struct bpf_patch_image img; + struct bpf_prog *new; + int err; + + if (!pl->cnt) + return prog; + + err = bpf_patch_list_build(pl, prog, &img); + if (!err && WARN_ON_ONCE(img.del)) + err = -EINVAL; + if (!err) { + new = bpf_prog_realloc(prog, bpf_prog_size(img.new_cnt), GFP_USER); + if (new) { + prog = new; + bpf_patch_image_install(prog, &img); + } else { + err = -ENOMEM; + } + } + + bpf_patch_image_free(&img); + bpf_patch_list_release(pl); + return err ? ERR_PTR(err) : prog; +} + /* * Now this function is used only to blind the main prog and must be invoked only when * bpf_prog_need_blind() returns true. */ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bpf_prog *prog) { - struct bpf_insn insn_buff[16], aux[2]; + struct bpf_insn insn_buff[16], aux[2], *last; + struct bpf_patch_list pl = {}; struct bpf_prog *clone, *tmp; - int insn_delta, insn_cnt; struct bpf_insn *insn; - int i, rewritten; + int i, insn_cnt, rewritten, err = 0; if (WARN_ON_ONCE(env && env->prog != prog)) return ERR_PTR(-EINVAL); @@ -1982,7 +2013,7 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp if (!clone) return ERR_PTR(-ENOMEM); - /* make sure bpf_patch_insn_data() patches the correct prog */ + /* make sure the patches go to the clone */ if (env) env->prog = clone; @@ -2013,41 +2044,45 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_verifier_env *env, struct bp if (!rewritten) continue; - if (rewritten < 0) - tmp = ERR_PTR(rewritten); - else if (env) - tmp = bpf_patch_insn_data(env, i, insn_buff, rewritten); - else - tmp = bpf_patch_insn_single(clone, i, insn_buff, rewritten); - - if (IS_ERR_OR_NULL(tmp)) { - if (env) - /* restore the original prog */ - env->prog = prog; - /* Patching may have repointed aux->prog during - * realloc from the original one, so we need to - * fix it up here on error. - */ - bpf_jit_prog_release_other(prog, clone); - if (env && fatal_signal_pending(current)) - return ERR_PTR(-EINTR); - return IS_ERR(tmp) ? tmp : ERR_PTR(-ENOMEM); + if (rewritten < 0) { + err = rewritten; + break; } + last = env ? bpf_patch_list_add(env, i, insn_buff, rewritten) : + __bpf_patch_list_add(&pl, clone, i, insn_buff, rewritten); + if (IS_ERR(last)) { + err = PTR_ERR(last); + break; + } + } - clone = tmp; - insn_delta = rewritten - 1; - - if (env) - env->prog = clone; + if (!err && env) { + err = bpf_patch_list_commit(env); + tmp = env->prog; + } else if (!err) { + tmp = bpf_patch_list_apply(clone, &pl); + err = PTR_ERR_OR_ZERO(tmp); + } - /* Walk new program and skip insns we just inserted. */ - insn = clone->insnsi + i + insn_delta; - insn_cnt += insn_delta; - i += insn_delta; + if (err) { + if (env) { + bpf_patch_list_free(env); + /* restore the original prog */ + env->prog = prog; + } + bpf_patch_list_release(&pl); + /* + * The clone is reallocated when nothing else can fail, so + * 'clone' is still valid. + */ + bpf_jit_prog_release_other(prog, clone); + if (env && fatal_signal_pending(current)) + return ERR_PTR(-EINTR); + return ERR_PTR(err); } - clone->blinded = 1; - return clone; + tmp->blinded = 1; + return tmp; } bool bpf_insn_is_indirect_target(const struct bpf_verifier_env *env, const struct bpf_prog *prog, -- 2.55.0