From patchwork Fri May 8 18:15:44 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luke Nelson X-Patchwork-Id: 11537331 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id B1B8215AB for ; Fri, 8 May 2020 18:16:15 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 754B3208CA for ; Fri, 8 May 2020 18:16:15 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="GVqt5wFx"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=cs.washington.edu header.i=@cs.washington.edu header.b="I6sVrCye" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 754B3208CA Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=cs.washington.edu Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:Cc:List-Subscribe: List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id:References: In-Reply-To:Message-Id:Date:Subject:To:From:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=i7UHSARk1d3c6M8ZM2pCrUDgJ9/s+ic0q9ZotJ03UhA=; b=GVqt5wFxOpqr69mnvrN5X2UM31 vnRdNoEIFkc8Urz5KAK9IaD7DSiueFfqOZF9gpc3kPywCRxvszAX+OoFeNMZQYWMWr+r5oPNGWnWZ RbgGln8CoUXCv3lVL/IE7CWZeJb2D0N0JM2qbBpWxoLDE8SObS4mrvO6ReB/p6kIN/ZrtrBN+KSzu hLci8WtX2ecPFkJOOWn8fVjHh5kcfLJXlHuICxicrXId19DbSxrHE7gxDAViaW4AzCwNX84VWhpwL SYOg6dV7oobZyH7nl6oZXQef7k5gP+kmpGFZ/RM4/yUu8pPKkY2JKoH2KrCxTC0hqwLls0Gc2cn+0 IqJM/3kQ==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7Xf-0007qJ-00; Fri, 08 May 2020 18:16:11 +0000 Received: from mail-pl1-x643.google.com ([2607:f8b0:4864:20::643]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7XV-0007gC-Pw for linux-arm-kernel@lists.infradead.org; Fri, 08 May 2020 18:16:03 +0000 Received: by mail-pl1-x643.google.com with SMTP id b8so1078129plm.11 for ; Fri, 08 May 2020 11:16:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.washington.edu; s=goo201206; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=+grFk/1b6m5GXQB6Do7/JZsbw7ECp6r+S8upQGe4+gI=; b=I6sVrCyeN1Al9+YXglL0XwffqWho/yTDT1r7S/K6Apz4jUPalQFiMfGpHSI54ALlc+ V6dIZM6i+WLjQlh5ywJ5byFfTeg9EfIH49M7i84H/uOfLRN+vZzIfo59Q3OEXEIJQEsx 7x2tnn1OPyog3FsuhfzlEBVIKdmsUugJfu5W4= 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=+grFk/1b6m5GXQB6Do7/JZsbw7ECp6r+S8upQGe4+gI=; b=lZK6PkBWITs8BZ4i/RcIf9jmtOaqvyOaFqV2xdjxCfwfWR6KoDV2SEPzU2Kk/N0OHE hRezwXtMmOC9ieizWdVfdNJPy2Oa8dsY8cNqrqt5ftoyb/Iakj7kRJLkGCHN0TWgkj6g /1htIRVaP/SNe1GOH0vkGkNYDRj4nS6PYQgvBF7WksL4m7H+M8MhOqW1KUIoNKJWqnv3 +mn7BR+cI1pxIuXPDH05hDMawEvRr54dZehBAg5IOC0MoDtQu/bupl6DXqwNfZwN7Y7a JQO+LxY3m+sLL7H6ZnPHPAe4KI0YI/z5rEjtlFDY7Mjfpv6CSqqZ6LGDeQvIc6AGvgMm ijZA== X-Gm-Message-State: AGi0PuZXAKJ/SbINIUbzCe6dh+R52JgMROSG0f0STE1oYLNB4kruagn8 XTUTOyz82OSjhyxYktr7tWnkZA== X-Google-Smtp-Source: APiQypKtbeWNjjqucMJ+BC3YWrrXzqesmFdn18zvEh3fztWZsGRRr05NnDcv2TODGa7UTSA8QZCmwg== X-Received: by 2002:a17:902:6114:: with SMTP id t20mr3762825plj.324.1588961760860; Fri, 08 May 2020 11:16:00 -0700 (PDT) Received: from localhost.localdomain (c-73-53-94-119.hsd1.wa.comcast.net. [73.53.94.119]) by smtp.gmail.com with ESMTPSA id e11sm2349463pfl.85.2020.05.08.11.15.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 May 2020 11:16:00 -0700 (PDT) From: Luke Nelson X-Google-Original-From: Luke Nelson To: bpf@vger.kernel.org Subject: [PATCH bpf-next v2 1/3] arm64: insn: Fix two bugs in encoding 32-bit logical immediates Date: Fri, 8 May 2020 11:15:44 -0700 Message-Id: <20200508181547.24783-2-luke.r.nels@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200508181547.24783-1-luke.r.nels@gmail.com> References: <20200508181547.24783-1-luke.r.nels@gmail.com> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200508_111601_836614_ABD4B408 X-CRM114-Status: GOOD ( 16.52 ) X-Spam-Score: -0.1 (/) X-Spam-Report: SpamAssassin version 3.4.4 on bombadil.infradead.org summary: Content analysis details: (-0.1 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [2607:f8b0:4864:20:0:0:0:643 listed in] [list.dnswl.org] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.0 SPF_PASS SPF: sender matches SPF record 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mark Rutland , Song Liu , Catalin Marinas , Alexei Starovoitov , Will Deacon , Daniel Borkmann , Marc Zyngier , John Fastabend , clang-built-linux@googlegroups.com, Zi Shen Lim , Yonghong Song , Andrii Nakryiko , Xi Wang , Luke Nelson , Alexios Zavras , KP Singh , Thomas Gleixner , linux-arm-kernel@lists.infradead.org, netdev@vger.kernel.org, linux-kernel@vger.kernel.org, Martin KaFai Lau , Christoffer Dall MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org This patch fixes two issues present in the current function for encoding arm64 logical immediates when using the 32-bit variants of instructions. First, the code does not correctly reject an all-ones 32-bit immediate, and returns an undefined instruction encoding. Second, the code incorrectly rejects some 32-bit immediates that are actually encodable as logical immediates. The root cause is that the code uses a default mask of 64-bit all-ones, even for 32-bit immediates. This causes an issue later on when the default mask is used to fill the top bits of the immediate with ones, shown here: /* * Pattern: 0..01..10..01..1 * * Fill the unused top bits with ones, and check if * the result is a valid immediate (all ones with a * contiguous ranges of zeroes). */ imm |= ~mask; if (!range_of_ones(~imm)) return AARCH64_BREAK_FAULT; To see the problem, consider an immediate of the form 0..01..10..01..1, where the upper 32 bits are zero, such as 0x80000001. The code checks if ~(imm | ~mask) contains a range of ones: the incorrect mask yields 1..10..01..10..0, which fails the check; the correct mask yields 0..01..10..0, which succeeds. The fix for both issues is to generate a correct mask based on the instruction immediate size, and use the mask to check for all-ones, all-zeroes, and values wider than the mask. Currently, arch/arm64/kvm/va_layout.c is the only user of this function, which uses 64-bit immediates and therefore won't trigger these bugs. We tested the new code against llvm-mc with all 1,302 encodable 32-bit logical immediates and all 5,334 encodable 64-bit logical immediates. Fixes: ef3935eeebff ("arm64: insn: Add encoder for bitwise operations using literals") Co-developed-by: Xi Wang Signed-off-by: Xi Wang Signed-off-by: Luke Nelson Reviewed-by: Marc Zyngier Suggested-by: Will Deacon --- arch/arm64/kernel/insn.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/arch/arm64/kernel/insn.c b/arch/arm64/kernel/insn.c index 4a9e773a177f..cc2f3d901c91 100644 --- a/arch/arm64/kernel/insn.c +++ b/arch/arm64/kernel/insn.c @@ -1535,16 +1535,10 @@ static u32 aarch64_encode_immediate(u64 imm, u32 insn) { unsigned int immr, imms, n, ones, ror, esz, tmp; - u64 mask = ~0UL; - - /* Can't encode full zeroes or full ones */ - if (!imm || !~imm) - return AARCH64_BREAK_FAULT; + u64 mask; switch (variant) { case AARCH64_INSN_VARIANT_32BIT: - if (upper_32_bits(imm)) - return AARCH64_BREAK_FAULT; esz = 32; break; case AARCH64_INSN_VARIANT_64BIT: @@ -1556,6 +1550,12 @@ static u32 aarch64_encode_immediate(u64 imm, return AARCH64_BREAK_FAULT; } + mask = GENMASK(esz - 1, 0); + + /* Can't encode full zeroes, full ones, or value wider than the mask */ + if (!imm || imm == mask || imm & ~mask) + return AARCH64_BREAK_FAULT; + /* * Inverse of Replicate(). Try to spot a repeating pattern * with a pow2 stride. From patchwork Fri May 8 18:15:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luke Nelson X-Patchwork-Id: 11537333 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 71A2315AB for ; Fri, 8 May 2020 18:16:33 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 317A0208CA for ; Fri, 8 May 2020 18:16:33 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="KNUptkqY"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=cs.washington.edu header.i=@cs.washington.edu header.b="lSt6/YnZ" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 317A0208CA Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=cs.washington.edu Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:Cc:List-Subscribe: List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id:References: In-Reply-To:Message-Id:Date:Subject:To:From:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=+tqZ2ngtCnmm22V/88NUsKUt/OJd9aOldZPvsZKyQUE=; b=KNUptkqYr8lrx6di2E4CPrHtYL KuL7Xtzjj5BNTFqo57GUT/jvEPBqr9iZMjCkV6VVYDio0g8mPV0rPEfDLM1QQTKQ9RkANlDZ9wwqb WIG6K2yBddPoiStuMWkrW9ooUn1TFGrsPFDv3PmhP7s1/EjWoC0492LNmgYnKDed1zyEpYwMhk+3j 7viOI0SADD7yJ78MN/DH7U4fNfcqnipBW2RutUo/bkKwBA/NUH8af/RQDVbv2caDmeSBHL3GOmhwF KNMUHAFlAZehUetohADTIZ8TQbdVjGZsKU6gFvxfv2ZLd+wgYKtnTZgco5Dj7Q9tYyQvFg0H3HVMt FM4/6fPw==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7Xv-0008AO-7T; Fri, 08 May 2020 18:16:27 +0000 Received: from mail-pg1-x541.google.com ([2607:f8b0:4864:20::541]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7XY-0007iX-Ad for linux-arm-kernel@lists.infradead.org; Fri, 08 May 2020 18:16:06 +0000 Received: by mail-pg1-x541.google.com with SMTP id f23so557995pgj.4 for ; Fri, 08 May 2020 11:16:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.washington.edu; s=goo201206; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=QNHfNzbVU0PwOL9SMJsHOvS8VR9Nkm49Q+JbsICKVBg=; b=lSt6/YnZZSbQrQgUgCitEjIy1NaXh9eqislb+AXqXdOIXgD+sWVeDy/U+Cagq8aI8C grBm7OvnGpKsQ6eQXmw0VgY3/PqLP+f2wuJd62XTIEiibArJ9VhiEyDWKeuwBt+xyWvy rjqYirbVCxNBT1OYuAmC8h+MyumhSTUPGFiFk= 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=QNHfNzbVU0PwOL9SMJsHOvS8VR9Nkm49Q+JbsICKVBg=; b=CUv0HbcwKZ89nk0pt0W+JFRMaeL4WePs6DVXb7Aismf0T1NrUDbIj7z9fLjFaPN1YG lHzxcW7vMVDb4dVNZ4e9XpXiphSVXiWo/4DSvK7QtvYp9MNJ3MHvHmFnIbPNSsf/HtLM 0BSg5E/tyq0I8Y1eJhyZr0X4T6etuJjW3agKrfkltntljF3cINiP+eAZs7Q11eZ7RCNZ mLsfGblRToaZjezsUAdZ2xGNNQjZctmBucroRJAXo00jDDRY56oaRNRClnFxk2TKl3gf MYwH6Qsc5OGbabdWFf9lBfaJi5rxF/U/s5hDpT9wKbpVrxfnEsmY3Jy+vnLfcPnsemLh r6OQ== X-Gm-Message-State: AGi0PuY7qkTmVRHmEg1o+jhveDzUqDVuc7X2hN59GtuJIoWwvmnQCVJu axNAAhBM0hYmrmkzaosILzTKOw== X-Google-Smtp-Source: APiQypL6mCb8hthDp9DwZO0MjCS8e0X4SVZU29TXxPDkXQ5usopWSeukTVWvFzjCdNLs6FR8d/63Aw== X-Received: by 2002:a62:3181:: with SMTP id x123mr4058797pfx.109.1588961763199; Fri, 08 May 2020 11:16:03 -0700 (PDT) Received: from localhost.localdomain (c-73-53-94-119.hsd1.wa.comcast.net. [73.53.94.119]) by smtp.gmail.com with ESMTPSA id e11sm2349463pfl.85.2020.05.08.11.16.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 May 2020 11:16:02 -0700 (PDT) From: Luke Nelson X-Google-Original-From: Luke Nelson To: bpf@vger.kernel.org Subject: [PATCH bpf-next v2 2/3] bpf, arm64: Optimize AND, OR, XOR, JSET BPF_K using arm64 logical immediates Date: Fri, 8 May 2020 11:15:45 -0700 Message-Id: <20200508181547.24783-3-luke.r.nels@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200508181547.24783-1-luke.r.nels@gmail.com> References: <20200508181547.24783-1-luke.r.nels@gmail.com> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200508_111604_459215_46C4B162 X-CRM114-Status: GOOD ( 15.92 ) X-Spam-Score: -0.1 (/) X-Spam-Report: SpamAssassin version 3.4.4 on bombadil.infradead.org summary: Content analysis details: (-0.1 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [2607:f8b0:4864:20:0:0:0:541 listed in] [list.dnswl.org] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.0 SPF_PASS SPF: sender matches SPF record 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mark Rutland , Song Liu , Catalin Marinas , Alexei Starovoitov , Will Deacon , Ard Biesheuvel , Daniel Borkmann , Marc Zyngier , John Fastabend , clang-built-linux@googlegroups.com, Zi Shen Lim , Yonghong Song , Andrii Nakryiko , Xi Wang , Luke Nelson , Torsten Duwe , KP Singh , Thomas Gleixner , linux-arm-kernel@lists.infradead.org, Greg Kroah-Hartman , linux-kernel@vger.kernel.org, netdev@vger.kernel.org, Enrico Weigelt , Martin KaFai Lau , Christoffer Dall MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org The current code for BPF_{AND,OR,XOR,JSET} BPF_K loads the immediate to a temporary register before use. This patch changes the code to avoid using a temporary register when the BPF immediate is encodable using an arm64 logical immediate instruction. If the encoding fails (due to the immediate not being encodable), it falls back to using a temporary register. Example of generated code for BPF_ALU32_IMM(BPF_AND, R0, 0x80000001): without optimization: 24: mov w10, #0x8000ffff 28: movk w10, #0x1 2c: and w7, w7, w10 with optimization: 24: and w7, w7, #0x80000001 Since the encoding process is quite complex, the JIT reuses existing functionality in arch/arm64/kernel/insn.c for encoding logical immediates rather than duplicate it in the JIT. Co-developed-by: Xi Wang Signed-off-by: Xi Wang Signed-off-by: Luke Nelson Acked-by: Daniel Borkmann --- arch/arm64/net/bpf_jit.h | 14 +++++++++++++ arch/arm64/net/bpf_jit_comp.c | 37 +++++++++++++++++++++++++++-------- 2 files changed, 43 insertions(+), 8 deletions(-) diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h index eb73f9f72c46..f36a779949e6 100644 --- a/arch/arm64/net/bpf_jit.h +++ b/arch/arm64/net/bpf_jit.h @@ -189,4 +189,18 @@ /* Rn & Rm; set condition flags */ #define A64_TST(sf, Rn, Rm) A64_ANDS(sf, A64_ZR, Rn, Rm) +/* Logical (immediate) */ +#define A64_LOGIC_IMM(sf, Rd, Rn, imm, type) ({ \ + u64 imm64 = (sf) ? (u64)imm : (u64)(u32)imm; \ + aarch64_insn_gen_logical_immediate(AARCH64_INSN_LOGIC_##type, \ + A64_VARIANT(sf), Rn, Rd, imm64); \ +}) +/* Rd = Rn OP imm */ +#define A64_AND_I(sf, Rd, Rn, imm) A64_LOGIC_IMM(sf, Rd, Rn, imm, AND) +#define A64_ORR_I(sf, Rd, Rn, imm) A64_LOGIC_IMM(sf, Rd, Rn, imm, ORR) +#define A64_EOR_I(sf, Rd, Rn, imm) A64_LOGIC_IMM(sf, Rd, Rn, imm, EOR) +#define A64_ANDS_I(sf, Rd, Rn, imm) A64_LOGIC_IMM(sf, Rd, Rn, imm, AND_SETFLAGS) +/* Rn & imm; set condition flags */ +#define A64_TST_I(sf, Rn, imm) A64_ANDS_I(sf, A64_ZR, Rn, imm) + #endif /* _BPF_JIT_H */ diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c index cdc79de0c794..083e5d8a5e2c 100644 --- a/arch/arm64/net/bpf_jit_comp.c +++ b/arch/arm64/net/bpf_jit_comp.c @@ -356,6 +356,7 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx, const bool isdw = BPF_SIZE(code) == BPF_DW; u8 jmp_cond, reg; s32 jmp_offset; + u32 a64_insn; #define check_imm(bits, imm) do { \ if ((((imm) > 0) && ((imm) >> (bits))) || \ @@ -488,18 +489,33 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx, break; case BPF_ALU | BPF_AND | BPF_K: case BPF_ALU64 | BPF_AND | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_AND(is64, dst, dst, tmp), ctx); + a64_insn = A64_AND_I(is64, dst, dst, imm); + if (a64_insn != AARCH64_BREAK_FAULT) { + emit(a64_insn, ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_AND(is64, dst, dst, tmp), ctx); + } break; case BPF_ALU | BPF_OR | BPF_K: case BPF_ALU64 | BPF_OR | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_ORR(is64, dst, dst, tmp), ctx); + a64_insn = A64_ORR_I(is64, dst, dst, imm); + if (a64_insn != AARCH64_BREAK_FAULT) { + emit(a64_insn, ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_ORR(is64, dst, dst, tmp), ctx); + } break; case BPF_ALU | BPF_XOR | BPF_K: case BPF_ALU64 | BPF_XOR | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_EOR(is64, dst, dst, tmp), ctx); + a64_insn = A64_EOR_I(is64, dst, dst, imm); + if (a64_insn != AARCH64_BREAK_FAULT) { + emit(a64_insn, ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_EOR(is64, dst, dst, tmp), ctx); + } break; case BPF_ALU | BPF_MUL | BPF_K: case BPF_ALU64 | BPF_MUL | BPF_K: @@ -628,8 +644,13 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx, goto emit_cond_jmp; case BPF_JMP | BPF_JSET | BPF_K: case BPF_JMP32 | BPF_JSET | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_TST(is64, dst, tmp), ctx); + a64_insn = A64_TST_I(is64, dst, imm); + if (a64_insn != AARCH64_BREAK_FAULT) { + emit(a64_insn, ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_TST(is64, dst, tmp), ctx); + } goto emit_cond_jmp; /* function call */ case BPF_JMP | BPF_CALL: From patchwork Fri May 8 18:15:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luke Nelson X-Patchwork-Id: 11537335 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 6FB61913 for ; Fri, 8 May 2020 18:16:45 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 3A2C62173E for ; Fri, 8 May 2020 18:16:45 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="gJo3SDcl"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=cs.washington.edu header.i=@cs.washington.edu header.b="CCWu0Lup" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 3A2C62173E Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=cs.washington.edu Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:Cc:List-Subscribe: List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id:References: In-Reply-To:Message-Id:Date:Subject:To:From:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=kTgtVedBvQVbXcxKFoPjkuaUDF2N+MwLfhyBoa6o9jo=; b=gJo3SDcl7kQ0YvFx6EgNQ9fLQV 0VzKX9bZdEamu6ZD4FVjcYHLLemiStdff1d7VRuJzZrqfkJdTgy6WlBDxo4vsw/MSdmAvFcCz9kmH O6suOnOfuzwWAg35DFHKihShjFKwF3yHbekdyLI8aamzcAzMlgeaLmfmkzU8T2tlei0H2ovm+Htkf g48CI6J2yXgk2mdlsx2b8ncgRMRt08Z7R+GtusxYw80+cUI1ciKU8wZ9TX/BPKdgzoNhr5Y50UwR0 f83x8TtJyrlfc798ROc8asJKF7AR+0mkuPiHKd9KOJPG/MP+CeGvIXTkEnyZWRgzcVSCvK1gHOzEI RAFX0JEQ==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7Y9-0008Pz-KL; Fri, 08 May 2020 18:16:41 +0000 Received: from mail-pg1-x542.google.com ([2607:f8b0:4864:20::542]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX7Xa-0007l2-Ju for linux-arm-kernel@lists.infradead.org; Fri, 08 May 2020 18:16:08 +0000 Received: by mail-pg1-x542.google.com with SMTP id d22so1230064pgk.3 for ; Fri, 08 May 2020 11:16:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.washington.edu; s=goo201206; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=1RkJFS+t50tivJwSHzxWQpizFYGiyRAPi5B/W8OYM90=; b=CCWu0LupJQSLY09+5kTFGNYiHYCgaMr3aDRuRcSjVMD7wkRduR4zrHrWLKa53mVjjP 9DMnW8euiPBliMtpPia67Qi698Z94wMFIWcXHzXx/3KnrghW58Dl0By0ArPQMx0jRC4E xAxlH1UM5bTdYo8pmzNqUBGKcKRxGOFWRpDAk= 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=1RkJFS+t50tivJwSHzxWQpizFYGiyRAPi5B/W8OYM90=; b=d1v13HGiLIz+GJQ1E8pIyJHHXsXZmAoLbmzOhrNNpormmTSFZQJeM3BEn0VGFkx7LP avDGLTtt9M/3sFguX9121N2EVeDQ3SeCDJe1kiZ8/TAhMcUR9YH+eCZi0UVV5Tq4f4In nvW5P/WLJLNESnWJPKrmYxsmwnaJ4njPwvT3yQcTkbr2574SS4oWBWEiV3NLu8XKGeZ7 mBLV6ln5LikPSRSgAIuiV/TYOa+i8hKjqLzjsTEECoBznqcU2CuiKALxL7OL+EAlxRZ5 90nawlcHRP0ixIFrn71nGLawpDVUZs7tHWErdRXVJ708rV23EYucfaPpj+Tk6T7yjJz0 W5hQ== X-Gm-Message-State: AGi0PuZMcEyH7q0/sYpgg5xlxDfwlVoMzS8OsZAFcT2NUrWk7OT/Zw09 TFlEOyMFjBgecvhlMZc7XZTlPw== X-Google-Smtp-Source: APiQypKlpWm+EIgUVSCtoFz2t937EsJIcePxRHt5/hrRD9OkiuRJ1E5BYoVCYwVZF5C/mgLC1saWKA== X-Received: by 2002:aa7:951b:: with SMTP id b27mr4228455pfp.2.1588961765560; Fri, 08 May 2020 11:16:05 -0700 (PDT) Received: from localhost.localdomain (c-73-53-94-119.hsd1.wa.comcast.net. [73.53.94.119]) by smtp.gmail.com with ESMTPSA id e11sm2349463pfl.85.2020.05.08.11.16.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 08 May 2020 11:16:05 -0700 (PDT) From: Luke Nelson X-Google-Original-From: Luke Nelson To: bpf@vger.kernel.org Subject: [PATCH bpf-next v2 3/3] bpf, arm64: Optimize ADD, SUB, JMP BPF_K using arm64 add/sub immediates Date: Fri, 8 May 2020 11:15:46 -0700 Message-Id: <20200508181547.24783-4-luke.r.nels@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200508181547.24783-1-luke.r.nels@gmail.com> References: <20200508181547.24783-1-luke.r.nels@gmail.com> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200508_111606_672093_E910D644 X-CRM114-Status: GOOD ( 14.54 ) X-Spam-Score: -0.1 (/) X-Spam-Report: SpamAssassin version 3.4.4 on bombadil.infradead.org summary: Content analysis details: (-0.1 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [2607:f8b0:4864:20:0:0:0:542 listed in] [list.dnswl.org] 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record -0.0 SPF_PASS SPF: sender matches SPF record 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mark Rutland , Song Liu , Catalin Marinas , Alexei Starovoitov , Will Deacon , Daniel Borkmann , Marc Zyngier , John Fastabend , clang-built-linux@googlegroups.com, linux-arm-kernel@lists.infradead.org, Zi Shen Lim , Yonghong Song , Andrii Nakryiko , Xi Wang , Luke Nelson , Alexios Zavras , KP Singh , Thomas Gleixner , Allison Randal , Greg Kroah-Hartman , linux-kernel@vger.kernel.org, netdev@vger.kernel.org, Martin KaFai Lau , Christoffer Dall MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org The current code for BPF_{ADD,SUB} BPF_K loads the BPF immediate to a temporary register before performing the addition/subtraction. Similarly, BPF_JMP BPF_K cases load the immediate to a temporary register before comparison. This patch introduces optimizations that use arm64 immediate add, sub, cmn, or cmp instructions when the BPF immediate fits. If the immediate does not fit, it falls back to using a temporary register. Example of generated code for BPF_ALU64_IMM(BPF_ADD, R0, 2): without optimization: 24: mov x10, #0x2 28: add x7, x7, x10 with optimization: 24: add x7, x7, #0x2 The code could use A64_{ADD,SUB}_I directly and check if it returns AARCH64_BREAK_FAULT, similar to how logical immediates are handled. However, aarch64_insn_gen_add_sub_imm from insn.c prints error messages when the immediate does not fit, and it's simpler to check if the immediate fits ahead of time. Co-developed-by: Xi Wang Signed-off-by: Xi Wang Signed-off-by: Luke Nelson Acked-by: Daniel Borkmann --- arch/arm64/net/bpf_jit.h | 8 ++++++++ arch/arm64/net/bpf_jit_comp.c | 36 +++++++++++++++++++++++++++++------ 2 files changed, 38 insertions(+), 6 deletions(-) diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h index f36a779949e6..923ae7ff68c8 100644 --- a/arch/arm64/net/bpf_jit.h +++ b/arch/arm64/net/bpf_jit.h @@ -100,6 +100,14 @@ /* Rd = Rn OP imm12 */ #define A64_ADD_I(sf, Rd, Rn, imm12) A64_ADDSUB_IMM(sf, Rd, Rn, imm12, ADD) #define A64_SUB_I(sf, Rd, Rn, imm12) A64_ADDSUB_IMM(sf, Rd, Rn, imm12, SUB) +#define A64_ADDS_I(sf, Rd, Rn, imm12) \ + A64_ADDSUB_IMM(sf, Rd, Rn, imm12, ADD_SETFLAGS) +#define A64_SUBS_I(sf, Rd, Rn, imm12) \ + A64_ADDSUB_IMM(sf, Rd, Rn, imm12, SUB_SETFLAGS) +/* Rn + imm12; set condition flags */ +#define A64_CMN_I(sf, Rn, imm12) A64_ADDS_I(sf, A64_ZR, Rn, imm12) +/* Rn - imm12; set condition flags */ +#define A64_CMP_I(sf, Rn, imm12) A64_SUBS_I(sf, A64_ZR, Rn, imm12) /* Rd = Rn */ #define A64_MOV(sf, Rd, Rn) A64_ADD_I(sf, Rd, Rn, 0) diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c index 083e5d8a5e2c..561a2fea9cdd 100644 --- a/arch/arm64/net/bpf_jit_comp.c +++ b/arch/arm64/net/bpf_jit_comp.c @@ -167,6 +167,12 @@ static inline int epilogue_offset(const struct jit_ctx *ctx) return to - from; } +static bool is_addsub_imm(u32 imm) +{ + /* Either imm12 or shifted imm12. */ + return !(imm & ~0xfff) || !(imm & ~0xfff000); +} + /* Stack must be multiples of 16B */ #define STACK_ALIGN(sz) (((sz) + 15) & ~15) @@ -479,13 +485,25 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx, /* dst = dst OP imm */ case BPF_ALU | BPF_ADD | BPF_K: case BPF_ALU64 | BPF_ADD | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_ADD(is64, dst, dst, tmp), ctx); + if (is_addsub_imm(imm)) { + emit(A64_ADD_I(is64, dst, dst, imm), ctx); + } else if (is_addsub_imm(-imm)) { + emit(A64_SUB_I(is64, dst, dst, -imm), ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_ADD(is64, dst, dst, tmp), ctx); + } break; case BPF_ALU | BPF_SUB | BPF_K: case BPF_ALU64 | BPF_SUB | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_SUB(is64, dst, dst, tmp), ctx); + if (is_addsub_imm(imm)) { + emit(A64_SUB_I(is64, dst, dst, imm), ctx); + } else if (is_addsub_imm(-imm)) { + emit(A64_ADD_I(is64, dst, dst, -imm), ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_SUB(is64, dst, dst, tmp), ctx); + } break; case BPF_ALU | BPF_AND | BPF_K: case BPF_ALU64 | BPF_AND | BPF_K: @@ -639,8 +657,14 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx, case BPF_JMP32 | BPF_JSLT | BPF_K: case BPF_JMP32 | BPF_JSGE | BPF_K: case BPF_JMP32 | BPF_JSLE | BPF_K: - emit_a64_mov_i(is64, tmp, imm, ctx); - emit(A64_CMP(is64, dst, tmp), ctx); + if (is_addsub_imm(imm)) { + emit(A64_CMP_I(is64, dst, imm), ctx); + } else if (is_addsub_imm(-imm)) { + emit(A64_CMN_I(is64, dst, -imm), ctx); + } else { + emit_a64_mov_i(is64, tmp, imm, ctx); + emit(A64_CMP(is64, dst, tmp), ctx); + } goto emit_cond_jmp; case BPF_JMP | BPF_JSET | BPF_K: case BPF_JMP32 | BPF_JSET | BPF_K: