From mboxrd@z Thu Jan 1 00:00:00 1970 From: Song Liu Subject: Re: [PATCH bpf-next 05/11] bpf: avoid retpoline for lookup/update/delete calls on maps Date: Wed, 30 May 2018 10:06:47 -0700 Message-ID: References: <20180528004344.3606-1-daniel@iogearbox.net> <20180528004344.3606-6-daniel@iogearbox.net> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Cc: Alexei Starovoitov , Networking To: Daniel Borkmann Return-path: Received: from mail-qt0-f195.google.com ([209.85.216.195]:40662 "EHLO mail-qt0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753659AbeE3RGs (ORCPT ); Wed, 30 May 2018 13:06:48 -0400 Received: by mail-qt0-f195.google.com with SMTP id h2-v6so24169770qtp.7 for ; Wed, 30 May 2018 10:06:48 -0700 (PDT) In-Reply-To: <20180528004344.3606-6-daniel@iogearbox.net> Sender: netdev-owner@vger.kernel.org List-ID: On Sun, May 27, 2018 at 5:43 PM, Daniel Borkmann wrote: > While some of the BPF map lookup helpers provide a ->map_gen_lookup() > callback for inlining the map lookup altogether it is not available > for every map, so the remaining ones have to call bpf_map_lookup_elem() > helper which does a dispatch to map->ops->map_lookup_elem(). In > times of retpolines, this will control and trap speculative execution > rather than letting it do its work for the indirect call and will > therefore cause a slowdown. Likewise, bpf_map_update_elem() and > bpf_map_delete_elem() do not have an inlined version and need to call > into their map->ops->map_update_elem() resp. map->ops->map_delete_elem() > handlers. > > Before: > > # bpftool p d x i 1 > 0: (bf) r2 = r10 > 1: (07) r2 += -8 > 2: (7a) *(u64 *)(r2 +0) = 0 > 3: (18) r1 = map[id:1] > 5: (85) call __htab_map_lookup_elem#232656 > 6: (15) if r0 == 0x0 goto pc+4 > 7: (71) r1 = *(u8 *)(r0 +35) > 8: (55) if r1 != 0x0 goto pc+1 > 9: (72) *(u8 *)(r0 +35) = 1 > 10: (07) r0 += 56 > 11: (15) if r0 == 0x0 goto pc+4 > 12: (bf) r2 = r0 > 13: (18) r1 = map[id:1] > 15: (85) call bpf_map_delete_elem#215008 <-- indirect call via > 16: (95) exit helper > > After: > > # bpftool p d x i 1 > 0: (bf) r2 = r10 > 1: (07) r2 += -8 > 2: (7a) *(u64 *)(r2 +0) = 0 > 3: (18) r1 = map[id:1] > 5: (85) call __htab_map_lookup_elem#233328 > 6: (15) if r0 == 0x0 goto pc+4 > 7: (71) r1 = *(u8 *)(r0 +35) > 8: (55) if r1 != 0x0 goto pc+1 > 9: (72) *(u8 *)(r0 +35) = 1 > 10: (07) r0 += 56 > 11: (15) if r0 == 0x0 goto pc+4 > 12: (bf) r2 = r0 > 13: (18) r1 = map[id:1] > 15: (85) call htab_lru_map_delete_elem#238240 <-- direct call > 16: (95) exit > > In all three lookup/update/delete cases however we can use the actual > address of the map callback directly if we find that there's only a > single path with a map pointer leading to the helper call, meaning > when the map pointer has not been poisoned from verifier side. > Example code can be seen above for the delete case. > > Signed-off-by: Daniel Borkmann > Acked-by: Alexei Starovoitov Acked-by: Song Liu > --- > include/linux/filter.h | 3 +++ > kernel/bpf/hashtab.c | 12 ++++++--- > kernel/bpf/verifier.c | 67 +++++++++++++++++++++++++++++++++++++------------- > 3 files changed, 62 insertions(+), 20 deletions(-) > > diff --git a/include/linux/filter.h b/include/linux/filter.h > index b443f70..d407ede 100644 > --- a/include/linux/filter.h > +++ b/include/linux/filter.h > @@ -301,6 +301,9 @@ struct xdp_buff; > > /* Function call */ > > +#define BPF_CAST_CALL(x) \ > + ((u64 (*)(u64, u64, u64, u64, u64))(x)) > + > #define BPF_EMIT_CALL(FUNC) \ > ((struct bpf_insn) { \ > .code = BPF_JMP | BPF_CALL, \ > diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c > index b76828f..3ca2198 100644 > --- a/kernel/bpf/hashtab.c > +++ b/kernel/bpf/hashtab.c > @@ -503,7 +503,9 @@ static u32 htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) > struct bpf_insn *insn = insn_buf; > const int ret = BPF_REG_0; > > - *insn++ = BPF_EMIT_CALL((u64 (*)(u64, u64, u64, u64, u64))__htab_map_lookup_elem); > + BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, > + (void *(*)(struct bpf_map *map, void *key))NULL)); > + *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); > *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1); > *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, > offsetof(struct htab_elem, key) + > @@ -530,7 +532,9 @@ static u32 htab_lru_map_gen_lookup(struct bpf_map *map, > const int ret = BPF_REG_0; > const int ref_reg = BPF_REG_1; > > - *insn++ = BPF_EMIT_CALL((u64 (*)(u64, u64, u64, u64, u64))__htab_map_lookup_elem); > + BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, > + (void *(*)(struct bpf_map *map, void *key))NULL)); > + *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); > *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 4); > *insn++ = BPF_LDX_MEM(BPF_B, ref_reg, ret, > offsetof(struct htab_elem, lru_node) + > @@ -1369,7 +1373,9 @@ static u32 htab_of_map_gen_lookup(struct bpf_map *map, > struct bpf_insn *insn = insn_buf; > const int ret = BPF_REG_0; > > - *insn++ = BPF_EMIT_CALL((u64 (*)(u64, u64, u64, u64, u64))__htab_map_lookup_elem); > + BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, > + (void *(*)(struct bpf_map *map, void *key))NULL)); > + *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); > *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 2); > *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, > offsetof(struct htab_elem, key) + > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 4f4786e..5684b15 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -2421,8 +2421,11 @@ record_func_map(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta, > struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx]; > > if (func_id != BPF_FUNC_tail_call && > - func_id != BPF_FUNC_map_lookup_elem) > + func_id != BPF_FUNC_map_lookup_elem && > + func_id != BPF_FUNC_map_update_elem && > + func_id != BPF_FUNC_map_delete_elem) > return 0; > + > if (meta->map_ptr == NULL) { > verbose(env, "kernel subsystem misconfigured verifier\n"); > return -EINVAL; > @@ -5586,6 +5589,7 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) > struct bpf_insn *insn = prog->insnsi; > const struct bpf_func_proto *fn; > const int insn_cnt = prog->len; > + const struct bpf_map_ops *ops; > struct bpf_insn_aux_data *aux; > struct bpf_insn insn_buf[16]; > struct bpf_prog *new_prog; > @@ -5715,10 +5719,13 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) > } > > /* BPF_EMIT_CALL() assumptions in some of the map_gen_lookup > - * handlers are currently limited to 64 bit only. > + * and other inlining handlers are currently limited to 64 bit > + * only. > */ > if (prog->jit_requested && BITS_PER_LONG == 64 && > - insn->imm == BPF_FUNC_map_lookup_elem) { > + (insn->imm == BPF_FUNC_map_lookup_elem || > + insn->imm == BPF_FUNC_map_update_elem || > + insn->imm == BPF_FUNC_map_delete_elem)) { > aux = &env->insn_aux_data[i + delta]; > if (bpf_map_ptr_poisoned(aux)) > goto patch_call_imm; > @@ -5727,23 +5734,49 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) > if (!map_ptr->ops->map_gen_lookup) > goto patch_call_imm; > > - cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf); > - if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) { > - verbose(env, "bpf verifier is misconfigured\n"); > - return -EINVAL; > - } > + ops = map_ptr->ops; > + if (insn->imm == BPF_FUNC_map_lookup_elem && > + ops->map_gen_lookup) { > + cnt = ops->map_gen_lookup(map_ptr, insn_buf); > + if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) { > + verbose(env, "bpf verifier is misconfigured\n"); > + return -EINVAL; > + } > > - new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, > - cnt); > - if (!new_prog) > - return -ENOMEM; > + new_prog = bpf_patch_insn_data(env, i + delta, > + insn_buf, cnt); > + if (!new_prog) > + return -ENOMEM; > > - delta += cnt - 1; > + delta += cnt - 1; > + env->prog = prog = new_prog; > + insn = new_prog->insnsi + i + delta; > + continue; > + } > > - /* keep walking new program and skip insns we just inserted */ > - env->prog = prog = new_prog; > - insn = new_prog->insnsi + i + delta; > - continue; > + BUILD_BUG_ON(!__same_type(ops->map_lookup_elem, > + (void *(*)(struct bpf_map *map, void *key))NULL)); > + BUILD_BUG_ON(!__same_type(ops->map_delete_elem, > + (int (*)(struct bpf_map *map, void *key))NULL)); > + BUILD_BUG_ON(!__same_type(ops->map_update_elem, > + (int (*)(struct bpf_map *map, void *key, void *value, > + u64 flags))NULL)); > + switch (insn->imm) { > + case BPF_FUNC_map_lookup_elem: > + insn->imm = BPF_CAST_CALL(ops->map_lookup_elem) - > + __bpf_call_base; > + continue; > + case BPF_FUNC_map_update_elem: > + insn->imm = BPF_CAST_CALL(ops->map_update_elem) - > + __bpf_call_base; > + continue; > + case BPF_FUNC_map_delete_elem: > + insn->imm = BPF_CAST_CALL(ops->map_delete_elem) - > + __bpf_call_base; > + continue; > + } > + > + goto patch_call_imm; > } > > if (insn->imm == BPF_FUNC_redirect_map) { > -- > 2.9.5 >