From patchwork Mon Jun 25 03:54:15 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934053 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="TgNKhqQW"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db183W64z9s2L for ; Mon, 25 Jun 2018 13:55:24 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753244AbeFYDyx (ORCPT ); Sun, 24 Jun 2018 23:54:53 -0400 Received: from mail-wr0-f175.google.com ([209.85.128.175]:34784 "EHLO mail-wr0-f175.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752755AbeFYDyt (ORCPT ); Sun, 24 Jun 2018 23:54:49 -0400 Received: by mail-wr0-f175.google.com with SMTP id a12-v6so12090179wro.1 for ; Sun, 24 Jun 2018 20:54:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=cxdbNjZrN8bhNGUWd2yP2ffNBIbLtGLcCDnJXKb+lnc=; b=TgNKhqQWbmCXElYUJT30zSjlcCrx/oXwl9mXv9IDEmSWZEHwIfLDbx8FMS/0WkMCtM m0e9+BglNcjowX3mQJltaoU5Qc4AIfN63hA9/F31Hr+2RjOGPtfMHXnncaLSxb/3bxn/ 8LWsonB1dgS5XTcyh8H2oe2lNK2Yu4bQi0WkrgFUwV9UqiWqJWI8Ox6EyzCw6/hzn7CD i0GlqcVrnkehWMp7pO89TDEx0rKjbvvYBZWYuPRDHD7cYOW3VRY9govjuJbIXA3XK5WX sIjR138V+RsDUxl8pi/4T7bbsDG7XyNisk0tPZIekMZs+Qo22cpfEDnxyuwTt0G0CJNs 5DKg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=cxdbNjZrN8bhNGUWd2yP2ffNBIbLtGLcCDnJXKb+lnc=; b=OJq1dC1KLnAbN+SFL6e+M/yM/M9mY/fuvfaQrYZpQHJG9DGB1+g+H2EZeNpTIXDMh/ emH4B4KAfcao0uuVabtCFOVODZgDS8X21sQ2WATnTfYiABhAXXBSt9arcY3/YaaWxW0x ixT9/zgrvBlMGWI57s1wGjkZQSjjBxSfltTy1BhIgjnX+45B/Blm6a5lMmqk65r7B8Bd ZPvs5ox2O9/ecOY7004sl7smwu4AuVQHEZBuvYQ/qRgKgeEVqGzFfYa3vPCzxODCmJuF zW2jOGQDU9xf52B2bCjpoA4v0MIvlX7kx2HcsB5OS5aIlaNtDLm+ZtoG/bP5UgtEjQ6m p4vA== X-Gm-Message-State: APt69E3eqUgmZOvNuO5DNfvI71M8XrRoTV+oeU4rtCBHZeXD0tZgY7dC fZ7YRI7T9C0QZxHVLQuESrJYCQ== X-Google-Smtp-Source: ADUXVKIBjFIyhW2NP37yBgSFvL1PI3YxqA6g4muRqg+8bL4XZUel8l2zQNLR4eCYvpIdBk9Jf0SfGA== X-Received: by 2002:a5d:478d:: with SMTP id w13-v6mr7997696wrq.188.1529898888168; Sun, 24 Jun 2018 20:54:48 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:47 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 1/7] nfp: bpf: allow source ptr type be map ptr in memcpy optimization Date: Sun, 24 Jun 2018 20:54:15 -0700 Message-Id: <20180625035421.2991-2-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang Map read has been supported on NFP, this patch enables optimization for memcpy from map to packet. This patch also fixed one latent bug which will cause copying from unexpected address once memcpy for map pointer enabled. Reported-by: Mary Pham Reported-by: David Beckett Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski Acked-by: Song Liu --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index 8a92088df0d7..33111739b210 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -670,7 +670,7 @@ static int nfp_cpp_memcpy(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) xfer_num = round_up(len, 4) / 4; if (src_40bit_addr) - addr40_offset(nfp_prog, meta->insn.src_reg, off, &src_base, + addr40_offset(nfp_prog, meta->insn.src_reg * 2, off, &src_base, &off); /* Setup PREV_ALU fields to override memory read length. */ @@ -3299,7 +3299,8 @@ curr_pair_is_memcpy(struct nfp_insn_meta *ld_meta, if (!is_mbpf_load(ld_meta) || !is_mbpf_store(st_meta)) return false; - if (ld_meta->ptr.type != PTR_TO_PACKET) + if (ld_meta->ptr.type != PTR_TO_PACKET && + ld_meta->ptr.type != PTR_TO_MAP_VALUE) return false; if (st_meta->ptr.type != PTR_TO_PACKET) From patchwork Mon Jun 25 03:54:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934051 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="Mi7fieRH"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db103yg7z9s2L for ; Mon, 25 Jun 2018 13:55:16 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753279AbeFYDyz (ORCPT ); Sun, 24 Jun 2018 23:54:55 -0400 Received: from mail-wr0-f170.google.com ([209.85.128.170]:45046 "EHLO mail-wr0-f170.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753059AbeFYDyv (ORCPT ); Sun, 24 Jun 2018 23:54:51 -0400 Received: by mail-wr0-f170.google.com with SMTP id p12-v6so10439448wrn.11 for ; Sun, 24 Jun 2018 20:54:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=mRuoNqppsQwYwNpAguvgo0JxUSf7yhrL50JJtMEkjsE=; b=Mi7fieRHvB/+fcU4/lkrqtse0YQGvvszbmiyknnHm9lRjyann/3ifa9pTLa480SlTS CJcPZv++XtFQRxcB8TLVLEizXRClJXwBxx8mTMIhrmubjtuuupFC0hx/tugIKNAGo6Gn iedS5FSFf0iPXrs3xaL0p4oSuY76Q1Ee6bx7+JbdQUCerS1vakU/NxBh7pUdZGE1RcN5 1emuiFuAkmQxzCC7rdxpeJu2YSqB8sBpMRVPr5VtQw9+76eSRb0kmFj6N9VjG5YDBXmx DNBFwEff0sk64k3/LzwGTtMcS1Ofbu6FKmTHFeqjbhvikFCdPwQEzEBMauWkNqtFiNsZ GSpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=mRuoNqppsQwYwNpAguvgo0JxUSf7yhrL50JJtMEkjsE=; b=hNMbBRfF7dzg7iJsToEvyKP479ws4Qo5kqfqGeBZKa+UJlgySYiT3inraBFoDOzw8N lEZRNF3O7EOUwWfQegrzZBma5EmWBVXPr77tgrfcj9kI9OCAksQzwXERJmSXOJCBDHV2 3N4fW5K8kwjR8eCbNoPqT0PKaOzje4TcUm5kztLkDgZfCevBbnQBNxy/YTQFIJWWt5qY yq6/3tpht1cfRPIm4aNFQPzz64xaKKPRKe7quYskRY479jU/RUAfkZVh/OJI6cJ0LTIL 9KG6iMNS2sInLVp2HnnOEKnPjwoLfgzoOFQUAToJusxPJVnovjRfKRHzY22EXoJXHNKc lhbg== X-Gm-Message-State: APt69E0iHKgdf4DWOiAmKC/B7bKnNjyFXpyoBuhg7/fqYThuH7b17bvz psagykKozhujS5hT/WQxZcBs/A== X-Google-Smtp-Source: AAOMgpdiOA79ar2w/lfEPWZw8wu6m7+ZBYtNJ8xli2YVASHIeWEieSOLnaFSUBDgGlN11GoMt/YFtw== X-Received: by 2002:adf:d149:: with SMTP id b9-v6mr345274wri.17.1529898890152; Sun, 24 Jun 2018 20:54:50 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:49 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 2/7] lib: reciprocal_div: implement the improved algorithm on the paper mentioned Date: Sun, 24 Jun 2018 20:54:16 -0700 Message-Id: <20180625035421.2991-3-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang The new added "reciprocal_value_adv" implements the advanced version of the algorithm described in Figure 4.2 of the paper except when dividend has MSB set which would require u128 divide on host and actually could be easily handled before calling the new "reciprocal_value_adv". The advanced version requires more complex calculation to get the reciprocal multiplier and other control variables, but then could reduce the required emulation operations. It makes no sense to use this advanced version for host divide emulation, those extra complexities for calculating multiplier etc could completely waive our saving on emulation operations. However, it makes sense to use it for JIT divide code generation (for example eBPF JIT backends) for which we are willing to trade performance of JITed code with that of host. As shown by the following pseudo code, the required emulation operations could go down from 6 (the basic version) to 3 or 4. To use the result of "reciprocal_value_adv", suppose we want to calculate n/d, the C-style pseudo code will be the following, it could be easily changed to real code generation for other JIT targets. struct reciprocal_value_adv rvalue; u8 pre_shift, exp; if (d >= (1u << 31)) { result = n >= d; return; } rvalue = reciprocal_value_adv(d, 32) exp = rvalue.exp; if (rvalue.is_wide_m && !(d & 1)) { pre_shift = fls(d & -d) - 1; rvalue = reciprocal_value_adv(d >> pre_shift, 32 - pre_shift); } else { pre_shift = 0; } // code generation starts. if (imm == 1 << exp) { result = n >> exp; } else if (rvalue.is_wide_m) { // pre_shift must be zero when reached here. t = (n * rvalue.m) >> 32; result = n - t; result >>= 1; result += t; result >>= rvalue.sh - 1; } else { if (pre_shift) result = n >> pre_shift; result = ((u64)result * rvalue.m) >> 32; result >>= rvalue.sh; } Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski --- include/linux/reciprocal_div.h | 65 ++++++++++++++++++++++++++++++++++ lib/reciprocal_div.c | 37 +++++++++++++++++++ 2 files changed, 102 insertions(+) diff --git a/include/linux/reciprocal_div.h b/include/linux/reciprocal_div.h index e031e9f2f9d8..5a695e4697d3 100644 --- a/include/linux/reciprocal_div.h +++ b/include/linux/reciprocal_div.h @@ -25,6 +25,9 @@ struct reciprocal_value { u8 sh1, sh2; }; +/* "reciprocal_value" and "reciprocal_divide" together implement the basic + * version of the algorithm described in Figure 4.1 of the paper. + */ struct reciprocal_value reciprocal_value(u32 d); static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R) @@ -33,4 +36,66 @@ static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R) return (t + ((a - t) >> R.sh1)) >> R.sh2; } +struct reciprocal_value_adv { + u32 m; + u8 sh, exp; + bool is_wide_m; +}; + +/* "reciprocal_value_adv" implements the advanced version of the algorithm + * described in Figure 4.2 of the paper except when dividend has MSB set which + * would require u128 divide on host and actually could be easily handled before + * calling "reciprocal_value_adv". + * + * The advanced version requires more complex calculation to get the reciprocal + * multiplier and other control variables, but then could reduce the required + * emulation operations. + * + * It makes no sense to use this advanced version for host divide emulation, + * those extra complexities for calculating multiplier etc could completely + * waive our saving on emulation operations. + * + * However, it makes sense to use it for JIT divide code generation for which + * we are willing to trade performance of JITed code with that of host. As shown + * by the following pseudo code, the required emulation operations could go down + * from 6 (the basic version) to 3 or 4. + * + * To use the result of "reciprocal_value_adv", suppose we want to calculate + * n/d: + * + * struct reciprocal_value_adv rvalue; + * u8 pre_shift, exp; + * + * if (d >= (1u << 31)) { + * result = n >= d; + * return; + * } + * rvalue = reciprocal_value_adv(d, 32) + * exp = rvalue.exp; + * if (rvalue.is_wide_m && !(d & 1)) { + * pre_shift = fls(d & -d) - 1; + * rvalue = reciprocal_value_adv(d >> pre_shift, 32 - pre_shift); + * } else { + * pre_shift = 0; + * } + * + * // code generation starts. + * if (imm == 1 << exp) { + * result = n >> exp; + * } else if (rvalue.is_wide_m) { + * // pre_shift must be zero when reached here. + * t = (n * rvalue.m) >> 32; + * result = n - t; + * result >>= 1; + * result += t; + * result >>= rvalue.sh - 1; + * } else { + * if (pre_shift) + * result = n >> pre_shift; + * result = ((u64)result * rvalue.m) >> 32; + * result >>= rvalue.sh; + * } + */ +struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec); + #endif /* _LINUX_RECIPROCAL_DIV_H */ diff --git a/lib/reciprocal_div.c b/lib/reciprocal_div.c index fcb4ce682c6f..a41501ebad7c 100644 --- a/lib/reciprocal_div.c +++ b/lib/reciprocal_div.c @@ -26,3 +26,40 @@ struct reciprocal_value reciprocal_value(u32 d) return R; } EXPORT_SYMBOL(reciprocal_value); + +struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec) +{ + struct reciprocal_value_adv R; + u32 l, post_shift; + u64 mhigh, mlow; + + l = fls(d - 1); + post_shift = l; + /* NOTE: mlow/mhigh could overflow u64 when l == 32 which means d has + * MSB set. This case needs to be handled before calling + * "reciprocal_value_adv", please see the comment at + * include/linux/reciprocal_div.h. + */ + mlow = 1ULL << (32 + l); + do_div(mlow, d); + mhigh = (1ULL << (32 + l)) + (1ULL << (32 + l - prec)); + do_div(mhigh, d); + + for (; post_shift > 0; post_shift--) { + u64 lo = mlow >> 1, hi = mhigh >> 1; + + if (lo >= hi) + break; + + mlow = lo; + mhigh = hi; + } + + R.m = (u32)mhigh; + R.sh = post_shift; + R.exp = l; + R.is_wide_m = mhigh > U32_MAX; + + return R; +} +EXPORT_SYMBOL(reciprocal_value_adv); From patchwork Mon Jun 25 03:54:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934047 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="qNObEU+w"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db0h5Dmfz9s2L for ; Mon, 25 Jun 2018 13:55:00 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753458AbeFYDy4 (ORCPT ); Sun, 24 Jun 2018 23:54:56 -0400 Received: from mail-wr0-f196.google.com ([209.85.128.196]:41193 "EHLO mail-wr0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753196AbeFYDyx (ORCPT ); Sun, 24 Jun 2018 23:54:53 -0400 Received: by mail-wr0-f196.google.com with SMTP id h10-v6so12058307wrq.8 for ; Sun, 24 Jun 2018 20:54:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=LaIDj4zQNlHjFdOJ2e7+YxPbCpjsqJbSE5/B5Ji2I0k=; b=qNObEU+wOdjZM6VMMbKb590pJkT7/eznf1t3kOKla4rBfpeC2tfeRmit/S+tmAmdLC 8DvFjlA4ksAR9tCwQ7UDdau3SgvL0eEPMv1cO0J0yapgfr6IzC/d6aQvUUfFQrD7EVRs 0if+dsjy5M0wXOkREDXZHHp+bAum6ipAazxBjTWWq6nxom7rUZ2SQFY0tjbZloX1ywc4 asjQQKgMonSaCGY5762LSUMUudBK5t90RE0/ZDOWKOvu0tfC1dnSJUbTwPzQg34st5cg S0xbUuv/gg6DHAxbiZOvRqoBYbXfKME5vDmc6lhPnGXp61XlTSd1+qFfyWRsb1L5OGNX 7Mcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=LaIDj4zQNlHjFdOJ2e7+YxPbCpjsqJbSE5/B5Ji2I0k=; b=mLS8rnRo8DKOyIBJY7W1wUl1GunLRBuK4cSDM4xZ5+KE84HH+xPzy0qawVn37KA3cq b5GPhcGW1aEP2FzCEd1CKnH04vfX/wXl/Yi5+2J0pJCx9Cs9k4oOJJAa/Qv37awtZHIo f8mDqAlwTUayWtRzfYjOKLh2yu9X7DKpnKenyG3un6p+MuKWiVTp3wP+/4lapeIm9QuC RBR248s8+qTgU2geFfLisyka5LW2R99guRpZ2qQBK2oCbxau2TdSf9N/aNWL9oOJy+jy WmrrXkUbDxmuIMkuF1DVTBJ23qbozJ+HV945Se7nvMkzeSnwyv/QBOgZ0zoU2zVE1Uj+ LXzA== X-Gm-Message-State: APt69E0V59qtMlh/L/r+jpMqY6Nc9/jz1rA8NxeAx0hu2yl7OTlvqxU6 TuiT55ioL4RxdNA1KxRGgUifVQ== X-Google-Smtp-Source: AAOMgpdHkzluQiCNvez5Xf8jhE7q4obA0fLUjBxGY/o2KAIPX/pBa/bj0t1Sbz5Rvx0jvF2rV8sUvQ== X-Received: by 2002:adf:e644:: with SMTP id b4-v6mr9265839wrn.254.1529898892120; Sun, 24 Jun 2018 20:54:52 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:51 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 3/7] nfp: bpf: rename umin/umax to umin_src/umax_src Date: Sun, 24 Jun 2018 20:54:17 -0700 Message-Id: <20180625035421.2991-4-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang The two fields are a copy of umin and umax info of bpf_insn->src_reg generated by verifier. Rename to make their meaning clear. Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski Acked-by: Song Liu --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 12 ++++++------ drivers/net/ethernet/netronome/nfp/bpf/main.h | 10 +++++----- drivers/net/ethernet/netronome/nfp/bpf/offload.c | 2 +- drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 4 ++-- 4 files changed, 14 insertions(+), 14 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index 33111739b210..4a629e9b5c0f 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -1772,8 +1772,8 @@ static int shl_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) u8 dst, src; dst = insn->dst_reg * 2; - umin = meta->umin; - umax = meta->umax; + umin = meta->umin_src; + umax = meta->umax_src; if (umin == umax) return __shl_imm64(nfp_prog, dst, umin); @@ -1881,8 +1881,8 @@ static int shr_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) u8 dst, src; dst = insn->dst_reg * 2; - umin = meta->umin; - umax = meta->umax; + umin = meta->umin_src; + umax = meta->umax_src; if (umin == umax) return __shr_imm64(nfp_prog, dst, umin); @@ -1995,8 +1995,8 @@ static int ashr_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) u8 dst, src; dst = insn->dst_reg * 2; - umin = meta->umin; - umax = meta->umax; + umin = meta->umin_src; + umax = meta->umax_src; if (umin == umax) return __ashr_imm64(nfp_prog, dst, umin); diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index 654fe7823e5e..5975a19c28cb 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -263,8 +263,8 @@ struct nfp_bpf_reg_state { * @func_id: function id for call instructions * @arg1: arg1 for call instructions * @arg2: arg2 for call instructions - * @umin: copy of core verifier umin_value. - * @umax: copy of core verifier umax_value. + * @umin_src: copy of core verifier umin_value for src opearnd. + * @umax_src: copy of core verifier umax_value for src operand. * @off: index of first generated machine instruction (in nfp_prog.prog) * @n: eBPF instruction number * @flags: eBPF instruction extra optimization flags @@ -301,11 +301,11 @@ struct nfp_insn_meta { struct nfp_bpf_reg_state arg2; }; /* We are interested in range info for some operands, - * for example, the shift amount. + * for example, the shift amount which is kept in src operand. */ struct { - u64 umin; - u64 umax; + u64 umin_src; + u64 umax_src; }; }; unsigned int off; diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c index 7eae4c0266f8..856a0003bb75 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c @@ -191,7 +191,7 @@ nfp_prog_prepare(struct nfp_prog *nfp_prog, const struct bpf_insn *prog, meta->insn = prog[i]; meta->n = i; if (is_mbpf_indir_shift(meta)) - meta->umin = U64_MAX; + meta->umin_src = U64_MAX; list_add_tail(&meta->l, &nfp_prog->insns); } diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index 4bfeba7b21b2..e862b739441f 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -555,8 +555,8 @@ nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx) const struct bpf_reg_state *sreg = cur_regs(env) + meta->insn.src_reg; - meta->umin = min(meta->umin, sreg->umin_value); - meta->umax = max(meta->umax, sreg->umax_value); + meta->umin_src = min(meta->umin_src, sreg->umin_value); + meta->umax_src = max(meta->umax_src, sreg->umax_value); } return 0; From patchwork Mon Jun 25 03:54:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934052 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="wWSkk7Ef"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db121Q57z9s2L for ; Mon, 25 Jun 2018 13:55:18 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754136AbeFYDzQ (ORCPT ); Sun, 24 Jun 2018 23:55:16 -0400 Received: from mail-wr0-f194.google.com ([209.85.128.194]:46433 "EHLO mail-wr0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752755AbeFYDyz (ORCPT ); Sun, 24 Jun 2018 23:54:55 -0400 Received: by mail-wr0-f194.google.com with SMTP id l14-v6so6998687wrq.13 for ; Sun, 24 Jun 2018 20:54:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=2seFnecXLBjztyABZuOTjmIL4jFL+BPikt8Rq9ZuHIg=; b=wWSkk7EfTAEPVocTs4vfqyJOj/M2ibSTMd6JuGued7SPDHqHzCrl3NwnqxtGJMAZ8x mz0NIKqKR6By9vHdDTD4aLm33/V9aJ2rZPqGLZ5kYSrb/JB9NjA6QI+FKVYtvJE2O6Mx iSY5lBEfr7GUo9uWL8kO2IRsjMK7t9QqAia01yU1niTZvEZCSVO5MLDilbDCiebN5znd xpaW1EZmQXWPgQV9TNwRw4muBeJo/Hx8mZIvbwIb2qBt4etFADRS4At5s9jZ1tjEVRS1 cRnrA7SKNm8acmynQD/afZtNFlmv5mqyECCXdpXrpLzHcEuy0zaHWeH+KmjG59ygHEdh jIRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=2seFnecXLBjztyABZuOTjmIL4jFL+BPikt8Rq9ZuHIg=; b=Y11O4w9ZlHFckpFcpt8RAn1ydZd3I15cA7dlAkQXr6gmQOf6k4tQK1ERyCV0dYMrRI tnDFexkPleV9fQTR3vmYMlIQcsxUP+GfK8GAMHJGzsSuvkUKC0Go5HK/jp/JPQ9gbp6t OigVStz04QfHUYvlch0LVBU6LTSVO/8JF0LkbLM6gNK6Nox9m8sijP9MzIcxI/CFf81m ZhApo+l1+1QcTpsacpfm/6lDBxxt06/1NJYYUDT807vxxX6jEL8zEps9LRiivRP2SrV3 s884aILekYgEmSC/2QPRkO/pKW1pxycCVbvel/mMc5TJaBfTvRcFTbX86E9aei9r3aQ+ J6KA== X-Gm-Message-State: APt69E0BSb7UiFEwfkMv223jYOjLZJTZeGCjfGFMmOb27ZgKVQi1WSLo VmVwCZEnbPjD1IxhXb40B9r54g== X-Google-Smtp-Source: AAOMgpenTIA7R51LIwRmVJqUdW17UjIziBMf1kCdogjxcpf8Z/gHi4tzjomuthDtmX2YgGvJWvzGOA== X-Received: by 2002:adf:e112:: with SMTP id d18-v6mr2302535wri.42.1529898894061; Sun, 24 Jun 2018 20:54:54 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.52 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:53 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 4/7] nfp: bpf: copy range info for all operands of all ALU operations Date: Sun, 24 Jun 2018 20:54:18 -0700 Message-Id: <20180625035421.2991-5-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang NFP verifier hook is coping range information of the shift amount for indirect shift operation so optimized shift sequences could be generated. We want to use range info to do more things. For example, to decide whether multiplication and divide are supported on the given range. This patch simply let NFP verifier hook to copy range info for all operands of all ALU operands. Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski Acked-by: Song Liu --- drivers/net/ethernet/netronome/nfp/bpf/main.h | 33 +++++++------------ .../net/ethernet/netronome/nfp/bpf/offload.c | 4 ++- .../net/ethernet/netronome/nfp/bpf/verifier.c | 6 +++- 3 files changed, 20 insertions(+), 23 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index 5975a19c28cb..c985d0ac61a3 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -265,6 +265,8 @@ struct nfp_bpf_reg_state { * @arg2: arg2 for call instructions * @umin_src: copy of core verifier umin_value for src opearnd. * @umax_src: copy of core verifier umax_value for src operand. + * @umin_dst: copy of core verifier umin_value for dst opearnd. + * @umax_dst: copy of core verifier umax_value for dst operand. * @off: index of first generated machine instruction (in nfp_prog.prog) * @n: eBPF instruction number * @flags: eBPF instruction extra optimization flags @@ -300,12 +302,15 @@ struct nfp_insn_meta { struct bpf_reg_state arg1; struct nfp_bpf_reg_state arg2; }; - /* We are interested in range info for some operands, - * for example, the shift amount which is kept in src operand. + /* We are interested in range info for operands of ALU + * operations. For example, shift amount, multiplicand and + * multiplier etc. */ struct { u64 umin_src; u64 umax_src; + u64 umin_dst; + u64 umax_dst; }; }; unsigned int off; @@ -339,6 +344,11 @@ static inline u8 mbpf_mode(const struct nfp_insn_meta *meta) return BPF_MODE(meta->insn.code); } +static inline bool is_mbpf_alu(const struct nfp_insn_meta *meta) +{ + return mbpf_class(meta) == BPF_ALU64 || mbpf_class(meta) == BPF_ALU; +} + static inline bool is_mbpf_load(const struct nfp_insn_meta *meta) { return (meta->insn.code & ~BPF_SIZE_MASK) == (BPF_LDX | BPF_MEM); @@ -384,25 +394,6 @@ static inline bool is_mbpf_xadd(const struct nfp_insn_meta *meta) return (meta->insn.code & ~BPF_SIZE_MASK) == (BPF_STX | BPF_XADD); } -static inline bool is_mbpf_indir_shift(const struct nfp_insn_meta *meta) -{ - u8 code = meta->insn.code; - bool is_alu, is_shift; - u8 opclass, opcode; - - opclass = BPF_CLASS(code); - is_alu = opclass == BPF_ALU64 || opclass == BPF_ALU; - if (!is_alu) - return false; - - opcode = BPF_OP(code); - is_shift = opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH; - if (!is_shift) - return false; - - return BPF_SRC(code) == BPF_X; -} - /** * struct nfp_prog - nfp BPF program * @bpf: backpointer to the bpf app priv structure diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c index 856a0003bb75..78f44c4d95b4 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c @@ -190,8 +190,10 @@ nfp_prog_prepare(struct nfp_prog *nfp_prog, const struct bpf_insn *prog, meta->insn = prog[i]; meta->n = i; - if (is_mbpf_indir_shift(meta)) + if (is_mbpf_alu(meta)) { meta->umin_src = U64_MAX; + meta->umin_dst = U64_MAX; + } list_add_tail(&meta->l, &nfp_prog->insns); } diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index e862b739441f..7bd9666bd8ff 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -551,12 +551,16 @@ nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx) if (is_mbpf_xadd(meta)) return nfp_bpf_check_xadd(nfp_prog, meta, env); - if (is_mbpf_indir_shift(meta)) { + if (is_mbpf_alu(meta)) { const struct bpf_reg_state *sreg = cur_regs(env) + meta->insn.src_reg; + const struct bpf_reg_state *dreg = + cur_regs(env) + meta->insn.dst_reg; meta->umin_src = min(meta->umin_src, sreg->umin_value); meta->umax_src = max(meta->umax_src, sreg->umax_value); + meta->umin_dst = min(meta->umin_dst, dreg->umin_value); + meta->umax_dst = max(meta->umax_dst, dreg->umax_value); } return 0; From patchwork Mon Jun 25 03:54:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934048 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="UIXxzjdN"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db0l5ZhMz9s2L for ; Mon, 25 Jun 2018 13:55:03 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754067AbeFYDzC (ORCPT ); Sun, 24 Jun 2018 23:55:02 -0400 Received: from mail-wr0-f181.google.com ([209.85.128.181]:38629 "EHLO mail-wr0-f181.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753196AbeFYDy5 (ORCPT ); Sun, 24 Jun 2018 23:54:57 -0400 Received: by mail-wr0-f181.google.com with SMTP id e18-v6so12075013wrs.5 for ; Sun, 24 Jun 2018 20:54:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=xOpONvW9bBiKXk4RA4mt4uJYbejg/2EZAzw0OGTcinw=; b=UIXxzjdN76oMzLLhYf4WuGh3+7zLwvbTrFeInx+s1t7lr4kbbOSNB3PcEne/iTySKl p0TNz0aoq95iGfUeYnDsmTawbUKPdnhZ5TjHJOcCZpl6kkKf42wF3S8aUT5/dZxpGY+e x/uWxK1JfkSkTUjr/u9Hk32qsXtWL7t88S0DeCWtVHsrlZdP+wuzfFHjbABwkZSwd4mq aWFEj7OyrLaz+xVMsMcURfSBsv/V7D7UvfinNrxVV7zPUG1LirluTgBDqzkabZHwXQWW zrf31fVol2R+Du27Rza7tmloseywRf5rc3yz8QfFSXlKLod8NDbI2v5n1B6okJw4SH4V 75uA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=xOpONvW9bBiKXk4RA4mt4uJYbejg/2EZAzw0OGTcinw=; b=cJa2HP0QjxsJlTr73XFHgZYgFlyDpnhdmp78vV23FOfZ0PIt2dKjlKfOWtIn2WGEaz 0O6cA/VvXF7SRDiOheOcHYRO+YpCp0UxO/Orog8Nk7SR06oTKfAtMNrr9RUd7dv8wWTG 4PKTc+kXcqZLUuj4I2iBQL+HwMQrj2GkR1cBGPBWFaKv4o00MW8bhswrRKfZWlaG15aL kOTGPXORjmtQq7YnB1AxQNyAq3ORm+ulbX5FMUl1b6mxyZKmI/CEIJYCeH1V6hbUtQS6 T8aufHdE4Dvwa7JSF+eCDAyDxMKfAGdiXAbxux8vq0RMkpdsR81YZOCA09HX8oTJZHYz iwYg== X-Gm-Message-State: APt69E2s4Lchf0zux33QsA+ydgHgtCnienUWZinMk/gBY9Td+WeyA55J yog4mbamFfKukDzprwwPGrJJnQ== X-Google-Smtp-Source: ADUXVKJwpHbG9wV7nV8uNO4/kHE4L4xQWSMxAMQUongNdN/4iNJzG9xsE3qSgafSjbtJM6NqPFJvwA== X-Received: by 2002:a5d:4204:: with SMTP id n4-v6mr8058193wrq.55.1529898896182; Sun, 24 Jun 2018 20:54:56 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:55 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 5/7] nfp: bpf: support u16 and u32 multiplications Date: Sun, 24 Jun 2018 20:54:19 -0700 Message-Id: <20180625035421.2991-6-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang NFP supports u16 and u32 multiplication. Multiplication is done 8-bits per step, therefore we need 2 steps for u16 and 4 steps for u32. We also need one start instruction to initialize the sequence and one or two instructions to fetch the result depending on either you need the high halve of u32 multiplication. For ALU64, if either operand is beyond u32's value range, we reject it. One thing to note, if the source operand is BPF_K, then we need to check "imm" field directly, and we'd reject it if it is negative. Because for ALU64, "imm" (with s32 type) is expected to be sign extended to s64 which NFP mul doesn't support. For ALU32, it is fine for "imm" be negative though, because the result is 32-bits and here is no difference on the low halve of result for signed/unsigned mul, so we will get correct result. Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski Acked-by: Song Liu --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 137 ++++++++++++++++++ drivers/net/ethernet/netronome/nfp/bpf/main.h | 5 + .../net/ethernet/netronome/nfp/bpf/verifier.c | 58 ++++++-- drivers/net/ethernet/netronome/nfp/nfp_asm.h | 28 ++++ 4 files changed, 217 insertions(+), 11 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index 4a629e9b5c0f..7d7061d93358 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -415,6 +415,60 @@ emit_alu(struct nfp_prog *nfp_prog, swreg dst, reg.dst_lmextn, reg.src_lmextn); } +static void +__emit_mul(struct nfp_prog *nfp_prog, enum alu_dst_ab dst_ab, u16 areg, + enum mul_type type, enum mul_step step, u16 breg, bool swap, + bool wr_both, bool dst_lmextn, bool src_lmextn) +{ + u64 insn; + + insn = OP_MUL_BASE | + FIELD_PREP(OP_MUL_A_SRC, areg) | + FIELD_PREP(OP_MUL_B_SRC, breg) | + FIELD_PREP(OP_MUL_STEP, step) | + FIELD_PREP(OP_MUL_DST_AB, dst_ab) | + FIELD_PREP(OP_MUL_SW, swap) | + FIELD_PREP(OP_MUL_TYPE, type) | + FIELD_PREP(OP_MUL_WR_AB, wr_both) | + FIELD_PREP(OP_MUL_SRC_LMEXTN, src_lmextn) | + FIELD_PREP(OP_MUL_DST_LMEXTN, dst_lmextn); + + nfp_prog_push(nfp_prog, insn); +} + +static void +emit_mul(struct nfp_prog *nfp_prog, swreg lreg, enum mul_type type, + enum mul_step step, swreg rreg) +{ + struct nfp_insn_ur_regs reg; + u16 areg; + int err; + + if (type == MUL_TYPE_START && step != MUL_STEP_NONE) { + nfp_prog->error = -EINVAL; + return; + } + + if (step == MUL_LAST || step == MUL_LAST_2) { + /* When type is step and step Number is LAST or LAST2, left + * source is used as destination. + */ + err = swreg_to_unrestricted(lreg, reg_none(), rreg, ®); + areg = reg.dst; + } else { + err = swreg_to_unrestricted(reg_none(), lreg, rreg, ®); + areg = reg.areg; + } + + if (err) { + nfp_prog->error = err; + return; + } + + __emit_mul(nfp_prog, reg.dst_ab, areg, type, step, reg.breg, reg.swap, + reg.wr_both, reg.dst_lmextn, reg.src_lmextn); +} + static void __emit_ld_field(struct nfp_prog *nfp_prog, enum shf_sc sc, u8 areg, u8 bmask, u8 breg, u8 shift, bool imm8, @@ -1380,6 +1434,65 @@ static void wrp_end32(struct nfp_prog *nfp_prog, swreg reg_in, u8 gpr_out) SHF_SC_R_ROT, 16); } +static void +wrp_mul_u32(struct nfp_prog *nfp_prog, swreg dst_hi, swreg dst_lo, swreg lreg, + swreg rreg, bool gen_high_half) +{ + emit_mul(nfp_prog, lreg, MUL_TYPE_START, MUL_STEP_NONE, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_32x32, MUL_STEP_1, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_32x32, MUL_STEP_2, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_32x32, MUL_STEP_3, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_32x32, MUL_STEP_4, rreg); + emit_mul(nfp_prog, dst_lo, MUL_TYPE_STEP_32x32, MUL_LAST, reg_none()); + if (gen_high_half) + emit_mul(nfp_prog, dst_hi, MUL_TYPE_STEP_32x32, MUL_LAST_2, + reg_none()); + else + wrp_immed(nfp_prog, dst_hi, 0); +} + +static void +wrp_mul_u16(struct nfp_prog *nfp_prog, swreg dst_hi, swreg dst_lo, swreg lreg, + swreg rreg) +{ + emit_mul(nfp_prog, lreg, MUL_TYPE_START, MUL_STEP_NONE, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_16x16, MUL_STEP_1, rreg); + emit_mul(nfp_prog, lreg, MUL_TYPE_STEP_16x16, MUL_STEP_2, rreg); + emit_mul(nfp_prog, dst_lo, MUL_TYPE_STEP_16x16, MUL_LAST, reg_none()); +} + +static int +wrp_mul(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, + bool gen_high_half, bool ropnd_from_reg) +{ + swreg multiplier, multiplicand, dst_hi, dst_lo; + const struct bpf_insn *insn = &meta->insn; + u32 lopnd_max, ropnd_max; + u8 dst_reg; + + dst_reg = insn->dst_reg; + multiplicand = reg_a(dst_reg * 2); + dst_hi = reg_both(dst_reg * 2 + 1); + dst_lo = reg_both(dst_reg * 2); + lopnd_max = meta->umax_dst; + if (ropnd_from_reg) { + multiplier = reg_b(insn->src_reg * 2); + ropnd_max = meta->umax_src; + } else { + u32 imm = insn->imm; + + multiplier = re_load_imm_any(nfp_prog, imm, imm_b(nfp_prog)); + ropnd_max = imm; + } + if (lopnd_max > U16_MAX || ropnd_max > U16_MAX) + wrp_mul_u32(nfp_prog, dst_hi, dst_lo, multiplicand, multiplier, + gen_high_half); + else + wrp_mul_u16(nfp_prog, dst_hi, dst_lo, multiplicand, multiplier); + + 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); @@ -1684,6 +1797,16 @@ static int sub_imm64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) return 0; } +static int mul_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) +{ + return wrp_mul(nfp_prog, meta, true, true); +} + +static int mul_imm64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) +{ + return wrp_mul(nfp_prog, meta, true, false); +} + static int neg_reg64(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) { const struct bpf_insn *insn = &meta->insn; @@ -2097,6 +2220,16 @@ static int sub_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) return wrp_alu32_imm(nfp_prog, meta, ALU_OP_SUB, !meta->insn.imm); } +static int mul_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) +{ + return wrp_mul(nfp_prog, meta, false, true); +} + +static int mul_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) +{ + return wrp_mul(nfp_prog, meta, false, false); +} + static int neg_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) { u8 dst = meta->insn.dst_reg * 2; @@ -2848,6 +2981,8 @@ static const instr_cb_t instr_cb[256] = { [BPF_ALU64 | BPF_ADD | BPF_K] = add_imm64, [BPF_ALU64 | BPF_SUB | BPF_X] = sub_reg64, [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_NEG] = neg_reg64, [BPF_ALU64 | BPF_LSH | BPF_X] = shl_reg64, [BPF_ALU64 | BPF_LSH | BPF_K] = shl_imm64, @@ -2867,6 +3002,8 @@ static const instr_cb_t instr_cb[256] = { [BPF_ALU | BPF_ADD | BPF_K] = add_imm, [BPF_ALU | BPF_SUB | BPF_X] = sub_reg, [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_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 c985d0ac61a3..c10079b1a312 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -394,6 +394,11 @@ static inline bool is_mbpf_xadd(const struct nfp_insn_meta *meta) return (meta->insn.code & ~BPF_SIZE_MASK) == (BPF_STX | BPF_XADD); } +static inline bool is_mbpf_mul(const struct nfp_insn_meta *meta) +{ + return is_mbpf_alu(meta) && mbpf_op(meta) == BPF_MUL; +} + /** * 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 7bd9666bd8ff..30d4f1580693 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -516,6 +516,51 @@ nfp_bpf_check_xadd(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, return nfp_bpf_check_ptr(nfp_prog, meta, env, meta->insn.dst_reg); } +static int +nfp_bpf_check_alu(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, + struct bpf_verifier_env *env) +{ + const struct bpf_reg_state *sreg = + cur_regs(env) + meta->insn.src_reg; + const struct bpf_reg_state *dreg = + cur_regs(env) + meta->insn.dst_reg; + + meta->umin_src = min(meta->umin_src, sreg->umin_value); + meta->umax_src = max(meta->umax_src, sreg->umax_value); + meta->umin_dst = min(meta->umin_dst, dreg->umin_value); + meta->umax_dst = max(meta->umax_dst, dreg->umax_value); + + /* NFP supports u16 and u32 multiplication. + * + * For ALU64, if either operand is beyond u32's value range, we reject + * it. One thing to note, if the source operand is BPF_K, then we need + * to check "imm" field directly, and we'd reject it if it is negative. + * Because for ALU64, "imm" (with s32 type) is expected to be sign + * extended to s64 which NFP mul doesn't support. + * + * For ALU32, it is fine for "imm" be negative though, because the + * result is 32-bits and there is no difference on the low halve of + * the result for signed/unsigned mul, so we will get correct result. + */ + if (is_mbpf_mul(meta)) { + if (meta->umax_dst > U32_MAX) { + pr_vlog(env, "multiplier is not within u32 value range\n"); + return -EINVAL; + } + if (mbpf_src(meta) == BPF_X && meta->umax_src > U32_MAX) { + pr_vlog(env, "multiplicand is not within u32 value range\n"); + return -EINVAL; + } + if (mbpf_class(meta) == BPF_ALU64 && + mbpf_src(meta) == BPF_K && meta->insn.imm < 0) { + pr_vlog(env, "sign extended multiplicand won't be within u32 value range\n"); + return -EINVAL; + } + } + + return 0; +} + static int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx) { @@ -551,17 +596,8 @@ nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx) if (is_mbpf_xadd(meta)) return nfp_bpf_check_xadd(nfp_prog, meta, env); - if (is_mbpf_alu(meta)) { - const struct bpf_reg_state *sreg = - cur_regs(env) + meta->insn.src_reg; - const struct bpf_reg_state *dreg = - cur_regs(env) + meta->insn.dst_reg; - - meta->umin_src = min(meta->umin_src, sreg->umin_value); - meta->umax_src = max(meta->umax_src, sreg->umax_value); - meta->umin_dst = min(meta->umin_dst, dreg->umin_value); - meta->umax_dst = max(meta->umax_dst, dreg->umax_value); - } + if (is_mbpf_alu(meta)) + return nfp_bpf_check_alu(nfp_prog, meta, env); return 0; } diff --git a/drivers/net/ethernet/netronome/nfp/nfp_asm.h b/drivers/net/ethernet/netronome/nfp/nfp_asm.h index f6677bc9875a..cdc4e065f6f5 100644 --- a/drivers/net/ethernet/netronome/nfp/nfp_asm.h +++ b/drivers/net/ethernet/netronome/nfp/nfp_asm.h @@ -426,4 +426,32 @@ static inline u32 nfp_get_ind_csr_ctx_ptr_offs(u32 read_offset) return (read_offset & ~NFP_IND_ME_CTX_PTR_BASE_MASK) | NFP_CSR_CTX_PTR; } +enum mul_type { + MUL_TYPE_START = 0x00, + MUL_TYPE_STEP_24x8 = 0x01, + MUL_TYPE_STEP_16x16 = 0x02, + MUL_TYPE_STEP_32x32 = 0x03, +}; + +enum mul_step { + MUL_STEP_1 = 0x00, + MUL_STEP_NONE = MUL_STEP_1, + MUL_STEP_2 = 0x01, + MUL_STEP_3 = 0x02, + MUL_STEP_4 = 0x03, + MUL_LAST = 0x04, + MUL_LAST_2 = 0x05, +}; + +#define OP_MUL_BASE 0x0f800000000ULL +#define OP_MUL_A_SRC 0x000000003ffULL +#define OP_MUL_B_SRC 0x000000ffc00ULL +#define OP_MUL_STEP 0x00000700000ULL +#define OP_MUL_DST_AB 0x00000800000ULL +#define OP_MUL_SW 0x00040000000ULL +#define OP_MUL_TYPE 0x00180000000ULL +#define OP_MUL_WR_AB 0x20000000000ULL +#define OP_MUL_SRC_LMEXTN 0x40000000000ULL +#define OP_MUL_DST_LMEXTN 0x80000000000ULL + #endif From patchwork Mon Jun 25 03:54:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934049 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="RkTRHVMs"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db0q68m7z9s2L for ; Mon, 25 Jun 2018 13:55:07 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754017AbeFYDzB (ORCPT ); Sun, 24 Jun 2018 23:55:01 -0400 Received: from mail-wr0-f195.google.com ([209.85.128.195]:33598 "EHLO mail-wr0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753711AbeFYDy7 (ORCPT ); Sun, 24 Jun 2018 23:54:59 -0400 Received: by mail-wr0-f195.google.com with SMTP id k16-v6so12092016wro.0 for ; Sun, 24 Jun 2018 20:54:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=/gH6u1q/DasmTSTYXLdL/NrYiN+R3YjslJWg862kz7U=; b=RkTRHVMsOsfsOubvT8WCmIal8dfV3mnb1oPw9KDSpW/uSxfahtLV4lAoEV5cQLTLFC xA7v8t/W2ScmYxJqRdGFM0S2+7fXI/04zYn6bxE+4Eww0yn4pjPSEr3CjrPy7rbCQW5w Ugt+YNZAhsqY0/eLo0uo/Ti4N9gXZ3CrYOiMy2PaZ36ogcooHckGl5nBb/jH8V1Hew0g 3Yr0tpqqXRZLctGM+S8E99AopKc05NsDo/MO42HFj2ISfJbWXBhZ80GTqH7g0pE8HqmB TGgqwynpccqrqpoLzWwSBLikpOlFoUDlyOkMBSRhQPPa3QK5oCj3u6dovxUuYaxgXMA6 AdSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=/gH6u1q/DasmTSTYXLdL/NrYiN+R3YjslJWg862kz7U=; b=cOolAVh2+q460Ylonkqvzyo4Uu96ZKBa3hftLqzwTSW0m11HPSTiA5qwN1CcauVbH0 9w1ChFoRwLK5iH4RcpolroYh7nUJFWdvb4DkCHBcRpZHtSBvB50tcnlTUrl4M1mV2vjX 3iqic2bhhLyVKPW9aCVL+ZmbE7mOjM6mG0uJyM2eT+aQXksUSHJzulxTjpNuGGLcATvZ X7y0NtthJ1SjLX1cITJD7yK9331vB3R4DNQl37YboLh28fbyWuHcIuK5dk4gFvUc3G5D XeekPVwITsE4crv+793LLL+zgXh3pF/3kPCns5V6xViD4smNwwzD8ZUyH6Xxe/FgfrCt gHEQ== X-Gm-Message-State: APt69E3/wyggOHTaxFuqJiQF3pvKZwtCvvzjfBEi7r8FpAZG+Vv7ygSZ kurBiAIQk12EuF0LwK/z+X7tuw== X-Google-Smtp-Source: AAOMgpfMgvj5DfT3sNG2HrDcAojq207+2Va2OFmN/9HEdy0tCy2RjW/AraSxgwsHtAtLf7Or/8q7aQ== X-Received: by 2002:adf:a35b:: with SMTP id d27-v6mr7957674wrb.189.1529898898145; Sun, 24 Jun 2018 20:54:58 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:57 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 6/7] nfp: bpf: support u32 divide using reciprocal_div.h Date: Sun, 24 Jun 2018 20:54:20 -0700 Message-Id: <20180625035421.2991-7-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang 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 Reviewed-by: Jakub Kicinski Acked-by: Song Liu --- 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 -#include #include #include +#include #include +#include #include #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; } From patchwork Mon Jun 25 03:54:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 934050 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="r/XEdQb4"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41Db0t00t7z9s2L for ; Mon, 25 Jun 2018 13:55:09 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754128AbeFYDzH (ORCPT ); Sun, 24 Jun 2018 23:55:07 -0400 Received: from mail-wr0-f195.google.com ([209.85.128.195]:41200 "EHLO mail-wr0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753921AbeFYDzB (ORCPT ); Sun, 24 Jun 2018 23:55:01 -0400 Received: by mail-wr0-f195.google.com with SMTP id h10-v6so12058438wrq.8 for ; Sun, 24 Jun 2018 20:55:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=FdkTASvFAXOVl+IYrhVl2LzUAuN9U3W6QAXxlWeQJSI=; b=r/XEdQb4ChSaNi17q8jSnuixmNDhqPx1kxZeTSmewCDDBDjCa3tpojXdWVw4RThmCV PewIwwuBFxsaa3nuxJjZ7AvowYDXlJhVH5BnVxy50HIhxZDWC7zvfHIxcTV4qsgK8KSJ dE8Mckt+/1yEU9qqmg2jDQOtyCeQT+A9Vjrl56nL4eJWkP3eLSAdH4XauZV6Dkbf6UR+ N+zRVSB5WnFPjcis9amCFgUoN6fCwV7Wp+d3Lf11zXo3yPvIA0l2RwUUcnQeFoLGsibk sNCioiPCCRUXqz9vz+tbTMOfWQ+1CE+7Df46uY/k8w1XzXUbrep3GEIr2qStF1eHWDO1 YY4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=FdkTASvFAXOVl+IYrhVl2LzUAuN9U3W6QAXxlWeQJSI=; b=AkkIScBlPzu0qrMtfzULkTWam3ft15iwhH4tZlH22C/cWwm2UfaZJ6iSQe4PdgRT4L d6qWZObim8A9iGqIIiMVyzMnVNwPgI3RLBPSo2mPNybDU6AkNAQJhiwZw+f3DgFQNYm9 mc7L/KJfsyO8HpSE9S5owaGg4V3t9dPMJ62A9De495DZKSB4rgyr+JikGmOT/CiXNvCb dasgdfTpwfIEBKGoe4D4x9mKRQNxF/R2brqkN2/ry5EQgbEY0PZJG3pCPr+cGQx2YyPP obny/55f9CV7IPA9K5P0BnR6iVjegdbId9N8BllM4ykMmT9X17sjv1j9JeHAkLOhM/vj i49g== X-Gm-Message-State: APt69E0q2n52iz2+0hfS++2tPcrg2ftwvQZ7n14+gzZSvK5dzYpLd8UA 6xkIke47g6JFgEhYP7dForm/Cg== X-Google-Smtp-Source: ADUXVKJC4Oqy60ub2H60cMMGJiKMBhp7oZ+GIHbjg0wi3H581m+pDFD8a5Kw2mdgRZnDUIlmGGIvug== X-Received: by 2002:adf:ee0e:: with SMTP id y14-v6mr9013366wrn.63.1529898900092; Sun, 24 Jun 2018 20:55:00 -0700 (PDT) Received: from jkicinski-Precision-T1700.netronome.com ([75.53.12.129]) by smtp.gmail.com with ESMTPSA id r2-v6sm13299648wrq.55.2018.06.24.20.54.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Jun 2018 20:54:59 -0700 (PDT) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: oss-drivers@netronome.com, netdev@vger.kernel.org, Jiong Wang Subject: [PATCH bpf-next 7/7] nfp: bpf: migrate to advanced reciprocal divide in reciprocal_div.h Date: Sun, 24 Jun 2018 20:54:21 -0700 Message-Id: <20180625035421.2991-8-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180625035421.2991-1-jakub.kicinski@netronome.com> References: <20180625035421.2991-1-jakub.kicinski@netronome.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Jiong Wang As we are doing JIT, we would want to use the advanced version of the reciprocal divide (reciprocal_value_adv) to trade performance with host. We could reduce the required ALU instructions from 4 to 2 or 1. Signed-off-by: Jiong Wang Reviewed-by: Jakub Kicinski --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 38 ++++++++++++++----- .../net/ethernet/netronome/nfp/bpf/verifier.c | 16 ++++++-- 2 files changed, 42 insertions(+), 12 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index d732b6cfc356..f99ac00bd649 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -1498,8 +1498,9 @@ 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; + struct reciprocal_value_adv rvalue; swreg tmp_b = imm_b(nfp_prog); + u8 pre_shift, exp; swreg magic; if (imm > U32_MAX) { @@ -1507,15 +1508,34 @@ static int wrp_div_imm(struct nfp_prog *nfp_prog, u8 dst, u64 imm) return 0; } - rvalue = reciprocal_value(imm); + rvalue = reciprocal_value_adv(imm, 32); + exp = rvalue.exp; + if (rvalue.is_wide_m && !(imm & 1)) { + pre_shift = fls(imm & -imm) - 1; + rvalue = reciprocal_value_adv(imm >> pre_shift, 32 - pre_shift); + } else { + pre_shift = 0; + } 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); + if (imm == 1 << exp) { + emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, dst_b, + SHF_SC_R_SHF, exp); + } else if (rvalue.is_wide_m) { + 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, 1); + 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.sh - 1); + } else { + if (pre_shift) + emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, + dst_b, SHF_SC_R_SHF, pre_shift); + wrp_mul_u32(nfp_prog, dst_both, dst_both, dst_a, magic, true); + emit_shf(nfp_prog, dst_both, reg_none(), SHF_OP_NONE, + dst_b, SHF_SC_R_SHF, rvalue.sh); + } return 0; } diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index f0f07e988c46..39c2c24fea11 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -561,12 +561,22 @@ 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. + * that as well. There is a further range requirement on dividend, + * please see the NOTE below. * * 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. + * + * NOTE: because we are using "reciprocal_value_adv" which doesn't + * support dividend with MSB set, so we need to JIT separate NFP + * sequence to handle such case. It could be a simple sequence if there + * is conditional move, however there isn't for NFP. So, we don't bother + * generating compare-if-set-branch sequence by rejecting the program + * straight away when the u32 dividend has MSB set. Divide by such a + * large constant would be rare in practice. Also, the programmer could + * simply rewrite it as "result = divisor >= the_const". */ if (is_mbpf_div(meta)) { if (meta->umax_dst > U32_MAX) { @@ -578,8 +588,8 @@ nfp_bpf_check_alu(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, 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"); + if (meta->umax_src > U32_MAX / 2) { + pr_vlog(env, "dividend is bigger than U32_MAX/2\n"); return -EINVAL; } }