On Sun, Jun 24, 2018 at 8:54 PM, Jakub Kicinski
<jakub.kicin...@netronome.com> wrote:
> From: Jiong Wang <jiong.w...@netronome.com>
>
> NFP doesn't have integer divide instruction, this patch use reciprocal
> algorithm (the basic one, reciprocal_div) to emulate it.
>
> For each u32 divide, we would need 11 instructions to finish the operation.
>
> 7 (for multiplication) + 4 (various ALUs) = 11
>
> Given NFP only supports multiplication no bigger than u32, we'd require
> divisor and dividend no bigger than that as well.
>
> Also eBPF doesn't support signed divide and has enforced this on C language
> level by failing compilation. However LLVM assembler hasn't enforced this,
> so it is possible for negative constant to leak in as a BPF_K operand
> through assembly code, we reject such cases as well.
>
> Signed-off-by: Jiong Wang <jiong.w...@netronome.com>
> Reviewed-by: Jakub Kicinski <jakub.kicin...@netronome.com>
Acked-by: Song Liu <songliubrav...@fb.com>
> ---
> drivers/net/ethernet/netronome/nfp/bpf/jit.c | 58 ++++++++++++++++++-
> drivers/net/ethernet/netronome/nfp/bpf/main.h | 5 ++
> .../net/ethernet/netronome/nfp/bpf/verifier.c | 31 ++++++++++
> 3 files changed, 93 insertions(+), 1 deletion(-)
>
> diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
> b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
> index 7d7061d93358..d732b6cfc356 100644
> --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c
> +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c
> @@ -34,10 +34,11 @@
> #define pr_fmt(fmt) "NFP net bpf: " fmt
>
> #include <linux/bug.h>
> -#include <linux/kernel.h>
> #include <linux/bpf.h>
> #include <linux/filter.h>
> +#include <linux/kernel.h>
> #include <linux/pkt_cls.h>
> +#include <linux/reciprocal_div.h>
> #include <linux/unistd.h>
>
> #include "main.h"
> @@ -1493,6 +1494,32 @@ wrp_mul(struct nfp_prog *nfp_prog, struct
> nfp_insn_meta *meta,
> return 0;
> }
>
> +static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm)
> +{
> + swreg tmp_both = imm_both(nfp_prog), dst_both = reg_both(dst);
> + swreg dst_a = reg_a(dst), dst_b = reg_a(dst);
> + struct reciprocal_value rvalue;
> + swreg tmp_b = imm_b(nfp_prog);
> + swreg magic;
> +
> + if (imm > U32_MAX) {
> + wrp_immed(nfp_prog, dst_both, 0);
> + return 0;
> + }
> +
> + rvalue = reciprocal_value(imm);
> + magic = re_load_imm_any(nfp_prog, rvalue.m, imm_b(nfp_prog));
> + wrp_mul_u32(nfp_prog, tmp_both, tmp_both, dst_a, magic, true);
> + emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_SUB, tmp_b);
> + emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
> + SHF_SC_R_SHF, rvalue.sh1);
> + emit_alu(nfp_prog, dst_both, dst_a, ALU_OP_ADD, tmp_b);
> + emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b,
> + SHF_SC_R_SHF, rvalue.sh2);
> +
> + return 0;
> +}
> +
> static int adjust_head(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> {
> swreg tmp = imm_a(nfp_prog), tmp_len = imm_b(nfp_prog);
> @@ -1807,6 +1834,21 @@ static int mul_imm64(struct nfp_prog *nfp_prog, struct
> nfp_insn_meta *meta)
> return wrp_mul(nfp_prog, meta, true, false);
> }
>
> +static int div_imm64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> +{
> + const struct bpf_insn *insn = &meta->insn;
> +
> + return wrp_div_imm(nfp_prog, insn->dst_reg * 2, insn->imm);
> +}
> +
> +static int div_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> +{
> + /* NOTE: verifier hook has rejected cases for which verifier doesn't
> + * know whether the source operand is constant or not.
> + */
> + return wrp_div_imm(nfp_prog, meta->insn.dst_reg * 2, meta->umin_src);
> +}
> +
> static int neg_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> {
> const struct bpf_insn *insn = &meta->insn;
> @@ -2230,6 +2272,16 @@ static int mul_imm(struct nfp_prog *nfp_prog, struct
> nfp_insn_meta *meta)
> return wrp_mul(nfp_prog, meta, false, false);
> }
>
> +static int div_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> +{
> + return div_reg64(nfp_prog, meta);
> +}
> +
> +static int div_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> +{
> + return div_imm64(nfp_prog, meta);
> +}
> +
> static int neg_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)
> {
> u8 dst = meta->insn.dst_reg * 2;
> @@ -2983,6 +3035,8 @@ static const instr_cb_t instr_cb[256] = {
> [BPF_ALU64 | BPF_SUB | BPF_K] = sub_imm64,
> [BPF_ALU64 | BPF_MUL | BPF_X] = mul_reg64,
> [BPF_ALU64 | BPF_MUL | BPF_K] = mul_imm64,
> + [BPF_ALU64 | BPF_DIV | BPF_X] = div_reg64,
> + [BPF_ALU64 | BPF_DIV | BPF_K] = div_imm64,
> [BPF_ALU64 | BPF_NEG] = neg_reg64,
> [BPF_ALU64 | BPF_LSH | BPF_X] = shl_reg64,
> [BPF_ALU64 | BPF_LSH | BPF_K] = shl_imm64,
> @@ -3004,6 +3058,8 @@ static const instr_cb_t instr_cb[256] = {
> [BPF_ALU | BPF_SUB | BPF_K] = sub_imm,
> [BPF_ALU | BPF_MUL | BPF_X] = mul_reg,
> [BPF_ALU | BPF_MUL | BPF_K] = mul_imm,
> + [BPF_ALU | BPF_DIV | BPF_X] = div_reg,
> + [BPF_ALU | BPF_DIV | BPF_K] = div_imm,
> [BPF_ALU | BPF_NEG] = neg_reg,
> [BPF_ALU | BPF_LSH | BPF_K] = shl_imm,
> [BPF_ALU | BPF_END | BPF_X] = end_reg32,
> diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h
> b/drivers/net/ethernet/netronome/nfp/bpf/main.h
> index c10079b1a312..9845c1a2d4c2 100644
> --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h
> +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h
> @@ -399,6 +399,11 @@ static inline bool is_mbpf_mul(const struct
> nfp_insn_meta *meta)
> return is_mbpf_alu(meta) && mbpf_op(meta) == BPF_MUL;
> }
>
> +static inline bool is_mbpf_div(const struct nfp_insn_meta *meta)
> +{
> + return is_mbpf_alu(meta) && mbpf_op(meta) == BPF_DIV;
> +}
> +
> /**
> * struct nfp_prog - nfp BPF program
> * @bpf: backpointer to the bpf app priv structure
> diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
> b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
> index 30d4f1580693..f0f07e988c46 100644
> --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
> +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
> @@ -558,6 +558,37 @@ nfp_bpf_check_alu(struct nfp_prog *nfp_prog, struct
> nfp_insn_meta *meta,
> }
> }
>
> + /* NFP doesn't have divide instructions, we support divide by constant
> + * through reciprocal multiplication. Given NFP support multiplication
> + * no bigger than u32, we'd require divisor and dividend no bigger
> than
> + * that as well.
> + *
> + * Also eBPF doesn't support signed divide and has enforced this on C
> + * language level by failing compilation. However LLVM assembler
> hasn't
> + * enforced this, so it is possible for negative constant to leak in
> as
> + * a BPF_K operand through assembly code, we reject such cases as
> well.
> + */
> + if (is_mbpf_div(meta)) {
> + if (meta->umax_dst > U32_MAX) {
> + pr_vlog(env, "divisor is not within u32 value
> range\n");
> + return -EINVAL;
> + }
> + if (mbpf_src(meta) == BPF_X) {
> + if (meta->umin_src != meta->umax_src) {
> + pr_vlog(env, "dividend is not constant\n");
> + return -EINVAL;
> + }
> + if (meta->umax_src > U32_MAX) {
> + pr_vlog(env, "dividend is not within u32
> value range\n");
> + return -EINVAL;
> + }
> + }
> + if (mbpf_src(meta) == BPF_K && meta->insn.imm < 0) {
> + pr_vlog(env, "divide by negative constant is not
> supported\n");
> + return -EINVAL;
> + }
> + }
> +
> return 0;
> }
>
> --
> 2.17.1
>
