From patchwork Mon Apr 15 21:37:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630751 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id C7FCBC4345F for ; Mon, 15 Apr 2024 21:39:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=2qnzqLtTbZ8jkgQT5HNEapzIafs62yNd7Url+29s4TM=; b=Q8soo2cp9U0DdF FOnK3G0HNPMLR3CMLN5JXUWvRorVoY4Ie5wVPF9pNwHkWbaU/DBXsIAFs+rdqh3qCdqITUDSeIi4H HkSDygwnlOIvEqRZ0S2bpXQ6LahKE6AijutaS0AGSD40g1loEZTGOgdnsMHE+NN1yfp3rAowhgCfC uazT7GvqhakzvzzgVL54GoEpwL7BHlYxLn2I0jMUUkzbhNI5bWGGXCew3lqgZGgO2XEFGohRNllmD YYdyvnrVBet2Q2jOsVarymq8LfrcWP87iXfCgxxT9119ouMfAuXVt7uIUND6ighwTfbhBZaQSSUMr 1+7L9FYZ55QDTgwRJ95g==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2P-00000009z6J-3LJ9; Mon, 15 Apr 2024 21:38:53 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2M-00000009z2Q-32dH for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:52 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 44D9260AAE; Mon, 15 Apr 2024 21:38:49 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id AD94EC2BD11; Mon, 15 Apr 2024 21:38:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217128; bh=jDCHCoEErWTs1Q2o+tP+LLm0NSy78laxjUZAxWeOB6M=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=eRlf0YcDF/SicJvsN47ZdFH6AB8wrKRpcGpEGoc14NJ1tkNR4ly51L5wEoRiy8X8i 45IuY+2/V5e5sl8HAlYXDZ0AVc+W+NZ5LyrplU75CXQF1YS6wUNX/qXKF7R9DVyzrh NsSVC+lK5iF4k8I6tIRaeF8nLio3iiclZ24c0iXlvHYbptYMjhkAKpdNjunUro1m0v o2yjuLb4f5ubPMqPM1Mh+WjEtraY06uPa7OaUwJAdLMfH7AZthjqkT6LgP/gWJICbH 3AdK/A+84SyIi66+ByWJAlD7WQYKnMHn5IW8O9Q9+5sbE7MKbSeJv7r5+aUY8Gytkx TWbz5mY4uUSaA== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 1/8] crypto: shash - add support for finup2x Date: Mon, 15 Apr 2024 14:37:12 -0700 Message-ID: <20240415213719.120673-2-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143850_901342_754A4CF6 X-CRM114-Status: GOOD ( 24.84 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Most cryptographic hash functions are serialized, in the sense that they have an internal block size and the blocks must be processed serially. (BLAKE3 is a notable exception that has tree-based hashing built-in, but all the more common choices such as the SHAs and BLAKE2 are serialized.) This limits the performance of computing a single hash. Yet, computing multiple hashes simultaneously does not have this limitation. Modern CPUs are superscalar and often can execute independent instructions in parallel. As a result, on many modern CPUs, it is possible to hash two equal-length messages in about the same time as a single message, if all the instructions are interleaved. Meanwhile, a very common use case for hashing in the Linux kernel is dm-verity and fs-verity. Both use a Merkle tree that has a fixed block size, usually 4096 bytes with an empty or 32-byte salt prepended. The hash algorithm is usually SHA-256. Usually, many blocks need to be hashed at a time. This is an ideal scenario for multibuffer hashing. Linux actually used to support SHA-256 multibuffer hashing on x86_64, before it was removed by commit ab8085c130ed ("crypto: x86 - remove SHA multibuffer routines and mcryptd"). However, it was integrated with the crypto API in a weird way, where it behaved as an asynchronous hash that queued up and executed all requests on a global queue. This made it very complex, buggy, and virtually unusable. This patch takes a new approach of just adding an API crypto_shash_finup2x() that synchronously computes the hash of two equal-length messages, starting from a common state that represents the (possibly empty) common prefix shared by the two messages. The new API is part of the "shash" algorithm type, as it does not make sense in "ahash". It does a "finup" operation rather than a "digest" operation in order to support the salt that is used by dm-verity and fs-verity. There is no fallback implementation that does two regular finups if the underlying algorithm doesn't support finup2x, since users probably will want to avoid the overhead of queueing up multiple hashes when multibuffer hashing won't actually be used anyway. For now the API only supports 2-way interleaving, as the usefulness and practicality seems to drop off dramatically after 2. The arm64 CPUs I tested don't support more than 2 concurrent SHA-256 hashes. On x86_64, AMD's Zen 4 is a notable exception that can theoretically do 4 concurrent SHA-256 hashes (at least based on a microbenchmark of the sha256rnds2 instruction). However, increasing the interleaving factor further would involve tradeoffs such as no longer being able to cache the round constants in registers, further increasing the code size (both source and binary), further increasing the amount of state that users need to keep track of, and causing there to be more "leftover" hashes. Signed-off-by: Eric Biggers --- include/crypto/hash.h | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/include/crypto/hash.h b/include/crypto/hash.h index 5d61f576cfc86..3bb1b0b7b1242 100644 --- a/include/crypto/hash.h +++ b/include/crypto/hash.h @@ -198,10 +198,13 @@ struct shash_desc { * @finup: see struct ahash_alg * @digest: see struct ahash_alg * @export: see struct ahash_alg * @import: see struct ahash_alg * @setkey: see struct ahash_alg + * @finup2x: **[optional]** Finish calculating the digests of two equal-length + * messages, interleaving the instructions to potentially achieve + * better performance than hashing each message individually. * @init_tfm: Initialize the cryptographic transformation object. * This function is called only once at the instantiation * time, right after the transformation context was * allocated. In case the cryptographic hardware has * some special requirements which need to be handled @@ -229,10 +232,12 @@ struct shash_alg { unsigned int len, u8 *out); int (*export)(struct shash_desc *desc, void *out); int (*import)(struct shash_desc *desc, const void *in); int (*setkey)(struct crypto_shash *tfm, const u8 *key, unsigned int keylen); + int (*finup2x)(struct shash_desc *desc, const u8 *data1, + const u8 *data2, unsigned int len, u8 *out1, u8 *out2); int (*init_tfm)(struct crypto_shash *tfm); void (*exit_tfm)(struct crypto_shash *tfm); int (*clone_tfm)(struct crypto_shash *dst, struct crypto_shash *src); unsigned int descsize; @@ -771,10 +776,15 @@ static inline unsigned int crypto_shash_digestsize(struct crypto_shash *tfm) static inline unsigned int crypto_shash_statesize(struct crypto_shash *tfm) { return crypto_shash_alg(tfm)->statesize; } +static inline bool crypto_shash_supports_finup2x(struct crypto_shash *tfm) +{ + return crypto_shash_alg(tfm)->finup2x != NULL; +} + static inline u32 crypto_shash_get_flags(struct crypto_shash *tfm) { return crypto_tfm_get_flags(crypto_shash_tfm(tfm)); } @@ -864,10 +874,34 @@ int crypto_shash_digest(struct shash_desc *desc, const u8 *data, * Return: 0 on success; < 0 if an error occurred. */ int crypto_shash_tfm_digest(struct crypto_shash *tfm, const u8 *data, unsigned int len, u8 *out); +/** + * crypto_shash_finup2x() - finish hashing two equal-length messages + * @desc: the hash state that will be forked for the two messages. This + * contains the state after hashing a (possibly-empty) common prefix of + * the two messages. + * @data1: the first message (not including any common prefix from @desc) + * @data2: the second message (not including any common prefix from @desc) + * @len: length of @data1 and @data2 in bytes + * @out1: output buffer for first message digest + * @out2: output buffer for second message digest + * + * Users must check crypto_shash_supports_finup2x(tfm) before calling this. + * + * Context: Any context. + * Return: 0 on success; a negative errno value on failure. + */ +static inline int crypto_shash_finup2x(struct shash_desc *desc, + const u8 *data1, const u8 *data2, + unsigned int len, u8 *out1, u8 *out2) +{ + return crypto_shash_alg(desc->tfm)->finup2x(desc, data1, data2, len, + out1, out2); +} + /** * crypto_shash_export() - extract operational state for message digest * @desc: reference to the operational state handle whose state is exported * @out: output buffer of sufficient size that can hold the hash state * From patchwork Mon Apr 15 21:37:13 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630755 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id DB446C4345F for ; Mon, 15 Apr 2024 21:39:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=ZoyPxSQ6HpCr6GdTUveQRnKrx/L6FYzJmbqT53cxXqg=; b=oW8A2ycTNjdUoq sqYYSLasOzwr7MecHmjEFWhzr7Bh8BfHKuqNGwkmk4jSwR+rROOsffizqAXjXiRuzphuPLUojvyaF JbsrCKb1nK1D5OztJBNPMkbcq78Vcw8GOVdYf1F50UbGHSphw+WmXDkb0HkjB/pJSwleytweQWvTE +3DyloVW07dL/N9GUHXIDjGQjPBpd3il3hFPwc2Nx1cc5lhidCZxAHnqZxzeMJE1TT7l93up3A/4a 6sZbEtzGGbkc8SccTVEI5VI611vLxjgbspMBHajgJksCLIrAbHluZYTNxN7EwjDZZV8biy7LobM5K MUOTgOhpfxmLueg2YBKg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2b-00000009zBR-2WiA; Mon, 15 Apr 2024 21:39:05 +0000 Received: from sin.source.kernel.org ([145.40.73.55]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2N-00000009z2c-3tQn for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:55 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 17816CE0BA1; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 1B7A9C4AF07; Mon, 15 Apr 2024 21:38:49 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217129; bh=7EeMhSwgfXHIxMBvok4WynVvjspAaaT/x9LSuah1mWA=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=apE+WaJBVTRpZ06MLaJm1+uhetGmGUYYcBMHvgLZhO/1pHcokq4mrSb2AvKhTeRwf xgQHbuWmNISyO2WTgLlgnyaC/I9K5EKor3mU1h9hb5332peW7y0H3rrDe67N7WjlDt +OzW4TS+DpYD457BwLOg1/uSGFPtc6Vjv4mtI5sj01Bihh/ZF20hn5t6WwdT4n2nxF NkPOvElsVJc6/AuVe2U5jUNgbV0ZvHt1pSmB5op9tfZAi7dJPtzWjCz1JcleaA7MkK 8CbhbEdXhWaW0PjNxvfXhtkr8JwOBZlTLXXLD55DvPoSfLNaEaaXaGiC7PneW8s5MG FswQ1M7NTA0xQ== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 2/8] crypto: testmgr - generate power-of-2 lengths more often Date: Mon, 15 Apr 2024 14:37:13 -0700 Message-ID: <20240415213719.120673-3-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143852_320215_122858F4 X-CRM114-Status: GOOD ( 12.21 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Implementations of hash functions often have special cases when lengths are a multiple of the hash function's internal block size (e.g. 64 for SHA-256, 128 for SHA-512). Currently, when the fuzz testing code generates lengths, it doesn't prefer any length mod 64 over any other. This limits the coverage of these special cases. Therefore, this patch updates the fuzz testing code to generate power-of-2 lengths and divide messages exactly in half a bit more often. Signed-off-by: Eric Biggers --- crypto/testmgr.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/crypto/testmgr.c b/crypto/testmgr.c index 3dddd288ca02c..2200d70e2aa9d 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -899,16 +899,18 @@ static inline u32 prandom_u32_inclusive(struct rnd_state *rng, static unsigned int generate_random_length(struct rnd_state *rng, unsigned int max_len) { unsigned int len = prandom_u32_below(rng, max_len + 1); - switch (prandom_u32_below(rng, 4)) { + switch (prandom_u32_below(rng, 5)) { case 0: return len % 64; case 1: return len % 256; case 2: + return min(1U << (len % 10), max_len); + case 3: return len % 1024; default: return len; } } @@ -1004,10 +1006,12 @@ static char *generate_random_sgl_divisions(struct rnd_state *rng, unsigned int this_len; const char *flushtype_str; if (div == &divs[max_divs - 1] || prandom_bool(rng)) this_len = remaining; + else if (prandom_u32_below(rng, 4) == 0) + this_len = (remaining + 1) / 2; else this_len = prandom_u32_inclusive(rng, 1, remaining); div->proportion_of_total = this_len; if (prandom_u32_below(rng, 4) == 0) From patchwork Mon Apr 15 21:37:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630757 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 6AA33C00A94 for ; Mon, 15 Apr 2024 21:39:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=nkE12xwzLcWzs3HaH9eLZnw30Wy1GxER7RKKIE6ldEo=; b=ToJXwcvi1tQpSy wOKlsKMqJE7l0O9dIY2YNZCD78lFE17V3kPlYyWUqr7DuVyO2rV8QuJfS3/76l8sr1kDEp0ePcmBl 8OJNiAvh/uZx1djR9rpWpDbky76qaJArYoZ+76ffaQaKDNCtWu8+LmlIDH/B/Q9zrsazeN8YaeKvF yX3la/QuR0O5qNDUnG51/mCU+mpjy7jDmWsvgoB9Cqsmrw51wNxsToh9rolG/dYDxtWNE8tB6D5k3 ybo0rVN0NjQjFal39oIsAAYilJOdQeCwPLifxeDqIwUHi1Cy3JvrMbaxNp17h9KspksuwMQeVREDH u/vjZ2UMkjdZ7NFHDBvQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2d-00000009zCn-1xIL; Mon, 15 Apr 2024 21:39:07 +0000 Received: from sin.source.kernel.org ([2604:1380:40e1:4800::1]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2O-00000009z2v-0nFX for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:55 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 79748CE0E0D; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 7F143C4AF09; Mon, 15 Apr 2024 21:38:49 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217129; bh=hbXIxMNQiPU1jkfQ0yP6wwnFgvTFspy1GiHj+tI7hHg=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=XFDstHMuJ1BmztILQZsAjxXlnfjaMFlmrn0NOIO9NjMVQ2/JXiWtJevkGoB8ih+wQ eImM0PMMoLGATxNL/h9le9TleeW9jfLDoRNYjCqlM9Ra96wG87/H73AtHJ4YP4gCjg 4MXMS+dUlFyj3eew2pKHKwiKeiHjegGfCnxsWZUs/BKhnkDU80p23NxWD35ZIBiqbP SN/jWQ43nnVgRp3wls16EOmTfCmLir9FPFOyv3RRHlP6sQNaGYnd4+ul2Rgzt2x3/z DuTMaJfdey7ObNZrIQNV4PJqc7wBgOtMewPp4+xlI+/GDbm395kXIdFCnRgxnHnzsf f5pS0SeI12big== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 3/8] crypto: testmgr - add tests for finup2x Date: Mon, 15 Apr 2024 14:37:14 -0700 Message-ID: <20240415213719.120673-4-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143852_744920_1321B71F X-CRM114-Status: GOOD ( 17.20 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Update the shash self-tests to test the new finup2x method when CONFIG_CRYPTO_MANAGER_EXTRA_TESTS=y. Signed-off-by: Eric Biggers --- crypto/testmgr.c | 53 ++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 44 insertions(+), 9 deletions(-) diff --git a/crypto/testmgr.c b/crypto/testmgr.c index 2200d70e2aa9d..e6d42db6f344e 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -227,10 +227,12 @@ enum flush_type { /* finalization function for hash algorithms */ enum finalization_type { FINALIZATION_TYPE_FINAL, /* use final() */ FINALIZATION_TYPE_FINUP, /* use finup() */ + FINALIZATION_TYPE_FINUP2X_BUF1, /* use 1st buffer of finup2x() */ + FINALIZATION_TYPE_FINUP2X_BUF2, /* use 2nd buffer of finup2x() */ FINALIZATION_TYPE_DIGEST, /* use digest() */ }; /* * Whether the crypto operation will occur in-place, and if so whether the @@ -1105,19 +1107,27 @@ static void generate_random_testvec_config(struct rnd_state *rng, if (prandom_bool(rng)) { cfg->req_flags |= CRYPTO_TFM_REQ_MAY_SLEEP; p += scnprintf(p, end - p, " may_sleep"); } - switch (prandom_u32_below(rng, 4)) { + switch (prandom_u32_below(rng, 6)) { case 0: cfg->finalization_type = FINALIZATION_TYPE_FINAL; p += scnprintf(p, end - p, " use_final"); break; case 1: cfg->finalization_type = FINALIZATION_TYPE_FINUP; p += scnprintf(p, end - p, " use_finup"); break; + case 2: + cfg->finalization_type = FINALIZATION_TYPE_FINUP2X_BUF1; + p += scnprintf(p, end - p, " use_finup2x_buf1"); + break; + case 3: + cfg->finalization_type = FINALIZATION_TYPE_FINUP2X_BUF2; + p += scnprintf(p, end - p, " use_finup2x_buf2"); + break; default: cfg->finalization_type = FINALIZATION_TYPE_DIGEST; p += scnprintf(p, end - p, " use_digest"); break; } @@ -1342,11 +1352,14 @@ static int test_shash_vec_cfg(const struct hash_testvec *vec, return -EINVAL; } goto result_ready; } - /* Using init(), zero or more update(), then final() or finup() */ + /* + * Using init(), zero or more update(), then either final(), finup(), or + * finup2x(). + */ if (cfg->nosimd) crypto_disable_simd_for_test(); err = crypto_shash_init(desc); if (cfg->nosimd) @@ -1354,28 +1367,50 @@ static int test_shash_vec_cfg(const struct hash_testvec *vec, err = check_shash_op("init", err, driver, vec_name, cfg); if (err) return err; for (i = 0; i < tsgl->nents; i++) { + const u8 *data = sg_virt(&tsgl->sgl[i]); + unsigned int len = tsgl->sgl[i].length; + if (i + 1 == tsgl->nents && - cfg->finalization_type == FINALIZATION_TYPE_FINUP) { + (cfg->finalization_type == FINALIZATION_TYPE_FINUP || + cfg->finalization_type == FINALIZATION_TYPE_FINUP2X_BUF1 || + cfg->finalization_type == FINALIZATION_TYPE_FINUP2X_BUF2)) { + const u8 *unused_data = tsgl->bufs[XBUFSIZE - 1]; + u8 unused_result[HASH_MAX_DIGESTSIZE]; + const char *op; + if (divs[i]->nosimd) crypto_disable_simd_for_test(); - err = crypto_shash_finup(desc, sg_virt(&tsgl->sgl[i]), - tsgl->sgl[i].length, result); + if (cfg->finalization_type == FINALIZATION_TYPE_FINUP || + !crypto_shash_supports_finup2x(tfm)) { + err = crypto_shash_finup(desc, data, len, + result); + op = "finup"; + } else if (cfg->finalization_type == + FINALIZATION_TYPE_FINUP2X_BUF1) { + err = crypto_shash_finup2x( + desc, data, unused_data, len, + result, unused_result); + op = "finup2x_buf1"; + } else { /* FINALIZATION_TYPE_FINUP2X_BUF2 */ + err = crypto_shash_finup2x( + desc, unused_data, data, len, + unused_result, result); + op = "finup2x_buf2"; + } if (divs[i]->nosimd) crypto_reenable_simd_for_test(); - err = check_shash_op("finup", err, driver, vec_name, - cfg); + err = check_shash_op(op, err, driver, vec_name, cfg); if (err) return err; goto result_ready; } if (divs[i]->nosimd) crypto_disable_simd_for_test(); - err = crypto_shash_update(desc, sg_virt(&tsgl->sgl[i]), - tsgl->sgl[i].length); + err = crypto_shash_update(desc, data, len); if (divs[i]->nosimd) crypto_reenable_simd_for_test(); err = check_shash_op("update", err, driver, vec_name, cfg); if (err) return err; From patchwork Mon Apr 15 21:37:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630754 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id D4A0CC00A94 for ; Mon, 15 Apr 2024 21:39:18 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=1OUEVX5YZ94yDtY5TO+9zNPVal5is24U9Kl3QghKpd0=; b=vhRJArJYUXk53v XZDwFxRp66CIo3LuTffZa2a4/Kp+nFf12St86GD2+SCiaAgMwkt/xtHD4/KeC//OwAfYvIB2fQf3h PgLnRLoW2xK7GuGCFu5O6YHHEGzN+DrGAFh86hJmhDq4sD4ytrrZnw7bp5o/ymHaPCGw683M8v8x8 PnKPRedd/nylm/RzBaPgzYUjpP1ZEFRM3MXMfhDZm1aIXraEymL7X+C3I++8lZCoAq0WFVS3zOiYH AUEXYj3Il9LX1aDITWoHbCX3nuTWaSrqTrfD/6hrpywx+55d3POrNIEMgc/T2cAZlvfA07reCVD1F JgCdb7BFNq91Sqemanyg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2Z-00000009zAC-1F4I; Mon, 15 Apr 2024 21:39:03 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2M-00000009z2a-4BgC for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:53 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 5C34B60ECB; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id E3ED5C4AF0B; Mon, 15 Apr 2024 21:38:49 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217130; bh=c321mT1++24B2cOuBpkPmowxb5rUlrzEYMWZP0GuOs4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=oHEejC1oIL3/ZwzuoRve5ji4zudKAPW62iEVvJ+njQHi/n9nu39ciE3zh4WeuWmC8 KIqNKbvJ9x6PGGTvsRyRznUAtRP7QxfsQXxf2U9hLyG5cxT0R6CW1YyRLNFvBoz8Ri lr+ymJtj8R2gWnc6dgJ2m1ihhBt8GPH1Qc12hpklld/LAd5gI2r46K4gXQKdrs4QVt CRjV2GrKbYlamigz8JXsJQS6NeWzibf/EJYOYkhMFHB4BbM+PpUKMXmhSYxEW/eJ7D cdwINRYbVJgsrEIJXsu4wZMf53ZpbxsrieqZZnvpjWWRZycJMIhYuFT/JsTLbcdaD8 ueWObg//U1XEg== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 4/8] crypto: x86/sha256-ni - add support for finup2x Date: Mon, 15 Apr 2024 14:37:15 -0700 Message-ID: <20240415213719.120673-5-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143851_187727_B2AE474B X-CRM114-Status: GOOD ( 21.74 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Add an implementation of finup2x to sha256-ni. finup2x interleaves a finup operation for two equal-length messages that share a common prefix. dm-verity and fs-verity will take advantage of this for significantly improved performance on capable CPUs. This increases the throughput of SHA-256 hashing 4096-byte messages by the following amounts on the following CPUs: AMD Zen 1: 84% AMD Zen 4: 98% Intel Ice Lake: 4% Intel Sapphire Rapids: 20% For now, this seems to benefit AMD much more than Intel. This seems to be because current AMD CPUs support concurrent execution of the SHA-NI instructions, but unfortunately current Intel CPUs don't, except for the sha256msg2 instruction. Hopefully future Intel CPUs will support SHA-NI on more execution ports. Zen 1 supports 2 concurrent sha256rnds2, and Zen 4 supports 4 concurrent sha256rnds2, which suggests that even better performance may be achievable on Zen 4 by interleaving more than two hashes; however, doing so poses a number of trade-offs. Signed-off-by: Eric Biggers --- arch/x86/crypto/sha256_ni_asm.S | 352 ++++++++++++++++++++++++++++ arch/x86/crypto/sha256_ssse3_glue.c | 40 ++++ 2 files changed, 392 insertions(+) diff --git a/arch/x86/crypto/sha256_ni_asm.S b/arch/x86/crypto/sha256_ni_asm.S index 537b6dcd7ed80..08319b529eff9 100644 --- a/arch/x86/crypto/sha256_ni_asm.S +++ b/arch/x86/crypto/sha256_ni_asm.S @@ -327,10 +327,362 @@ SYM_TYPED_FUNC_START(sha256_ni_transform) .Ldone_hash: RET SYM_FUNC_END(sha256_ni_transform) +#undef DIGEST_PTR +#undef DATA_PTR +#undef NUM_BLKS +#undef SHA256CONSTANTS +#undef MSG +#undef STATE0 +#undef STATE1 +#undef MSG0 +#undef MSG1 +#undef MSG2 +#undef MSG3 +#undef TMP +#undef SHUF_MASK +#undef ABEF_SAVE +#undef CDGH_SAVE + +// parameters for __sha256_ni_finup2x() +#define SCTX %rdi +#define DATA1 %rsi +#define DATA2 %rdx +#define LEN %ecx +#define LEN8 %cl +#define LEN64 %rcx +#define OUT1 %r8 +#define OUT2 %r9 + +// other scalar variables +#define SHA256CONSTANTS %rax +#define COUNT %r10 +#define COUNT32 %r10d +#define FINAL_STEP %r11d + +// rbx is used as a temporary. + +#define MSG %xmm0 +#define STATE0_A %xmm1 +#define STATE1_A %xmm2 +#define STATE0_B %xmm3 +#define STATE1_B %xmm4 +#define TMP_A %xmm5 +#define TMP_B %xmm6 +#define MSG0_A %xmm7 +#define MSG1_A %xmm8 +#define MSG2_A %xmm9 +#define MSG3_A %xmm10 +#define MSG0_B %xmm11 +#define MSG1_B %xmm12 +#define MSG2_B %xmm13 +#define MSG3_B %xmm14 +#define SHUF_MASK %xmm15 + +#define OFFSETOF_STATE 0 // offsetof(struct sha256_state, state) +#define OFFSETOF_COUNT 32 // offsetof(struct sha256_state, count) +#define OFFSETOF_BUF 40 // offsetof(struct sha256_state, buf) + +.macro do_4rounds_2x i, m0_a, m1_a, m2_a, m3_a, m0_b, m1_b, m2_b, m3_b + movdqa (\i-32)*4(SHA256CONSTANTS), TMP_A + movdqa TMP_A, TMP_B + paddd \m0_a, TMP_A + paddd \m0_b, TMP_B + movdqa TMP_A, MSG + sha256rnds2 STATE0_A, STATE1_A + movdqa TMP_B, MSG + sha256rnds2 STATE0_B, STATE1_B + pshufd $0x0E, TMP_A, MSG + sha256rnds2 STATE1_A, STATE0_A + pshufd $0x0E, TMP_B, MSG + sha256rnds2 STATE1_B, STATE0_B +.if \i >= 12 && \i < 60 + movdqa \m0_a, TMP_A + movdqa \m0_b, TMP_B + palignr $4, \m3_a, TMP_A + palignr $4, \m3_b, TMP_B + paddd TMP_A, \m1_a + paddd TMP_B, \m1_b + sha256msg2 \m0_a, \m1_a + sha256msg2 \m0_b, \m1_b +.endif +.if \i >= 4 && \i < 52 + sha256msg1 \m0_a, \m3_a + sha256msg1 \m0_b, \m3_b +.endif +.endm + +// +// void __sha256_ni_finup2x(const struct sha256_state *sctx, +// const u8 *data1, const u8 *data2, int len, +// u8 out1[SHA256_DIGEST_SIZE], +// u8 out2[SHA256_DIGEST_SIZE]); +// +// This function computes the SHA-256 digests of two messages |data1| and +// |data2| that are both |len| bytes long, starting from the initial state +// |sctx|. |len| must be at least SHA256_BLOCK_SIZE. +// +// The instructions for the two SHA-256 operations are interleaved. On many +// CPUs, this is almost twice as fast as hashing each message individually due +// to taking better advantage of the CPU's SHA-256 and SIMD throughput. +// +SYM_FUNC_START(__sha256_ni_finup2x) + // Allocate 128 bytes of stack space, 16-byte aligned. + push %rbx + push %rbp + mov %rsp, %rbp + sub $128, %rsp + and $~15, %rsp + + // Load the shuffle mask for swapping the endianness of 32-bit words. + movdqa PSHUFFLE_BYTE_FLIP_MASK(%rip), SHUF_MASK + + // Set up pointer to the round constants. + lea K256+32*4(%rip), SHA256CONSTANTS + + // Initially we're not processing the final blocks. + xor FINAL_STEP, FINAL_STEP + + // Load the initial state from sctx->state. + movdqu OFFSETOF_STATE+0*16(SCTX), STATE0_A // DCBA + movdqu OFFSETOF_STATE+1*16(SCTX), STATE1_A // HGFE + movdqa STATE0_A, TMP_A + punpcklqdq STATE1_A, STATE0_A // FEBA + punpckhqdq TMP_A, STATE1_A // DCHG + pshufd $0x1B, STATE0_A, STATE0_A // ABEF + pshufd $0xB1, STATE1_A, STATE1_A // CDGH + + // Load sctx->count. Take the mod 64 of it to get the number of bytes + // that are buffered in sctx->buf. Also save it in a register with LEN + // added to it. + mov LEN, LEN + mov OFFSETOF_COUNT(SCTX), %rbx + lea (%rbx, LEN64, 1), COUNT + and $63, %ebx + jz .Lfinup2x_enter_loop // No bytes buffered? + + // %ebx bytes (1 to 63) are currently buffered in sctx->buf. Load them + // followed by the first 64 - %ebx bytes of data. Since LEN >= 64, we + // just load 64 bytes from each of sctx->buf, DATA1, and DATA2 + // unconditionally and rearrange the data as needed. + + movdqu OFFSETOF_BUF+0*16(SCTX), MSG0_A + movdqu OFFSETOF_BUF+1*16(SCTX), MSG1_A + movdqu OFFSETOF_BUF+2*16(SCTX), MSG2_A + movdqu OFFSETOF_BUF+3*16(SCTX), MSG3_A + movdqa MSG0_A, 0*16(%rsp) + movdqa MSG1_A, 1*16(%rsp) + movdqa MSG2_A, 2*16(%rsp) + movdqa MSG3_A, 3*16(%rsp) + + movdqu 0*16(DATA1), MSG0_A + movdqu 1*16(DATA1), MSG1_A + movdqu 2*16(DATA1), MSG2_A + movdqu 3*16(DATA1), MSG3_A + movdqu MSG0_A, 0*16(%rsp,%rbx) + movdqu MSG1_A, 1*16(%rsp,%rbx) + movdqu MSG2_A, 2*16(%rsp,%rbx) + movdqu MSG3_A, 3*16(%rsp,%rbx) + movdqa 0*16(%rsp), MSG0_A + movdqa 1*16(%rsp), MSG1_A + movdqa 2*16(%rsp), MSG2_A + movdqa 3*16(%rsp), MSG3_A + + movdqu 0*16(DATA2), MSG0_B + movdqu 1*16(DATA2), MSG1_B + movdqu 2*16(DATA2), MSG2_B + movdqu 3*16(DATA2), MSG3_B + movdqu MSG0_B, 0*16(%rsp,%rbx) + movdqu MSG1_B, 1*16(%rsp,%rbx) + movdqu MSG2_B, 2*16(%rsp,%rbx) + movdqu MSG3_B, 3*16(%rsp,%rbx) + movdqa 0*16(%rsp), MSG0_B + movdqa 1*16(%rsp), MSG1_B + movdqa 2*16(%rsp), MSG2_B + movdqa 3*16(%rsp), MSG3_B + + sub $64, %rbx // rbx = buffered - 64 + sub %rbx, DATA1 // DATA1 += 64 - buffered + sub %rbx, DATA2 // DATA2 += 64 - buffered + add %ebx, LEN // LEN += buffered - 64 + movdqa STATE0_A, STATE0_B + movdqa STATE1_A, STATE1_B + jmp .Lfinup2x_loop_have_data + +.Lfinup2x_enter_loop: + sub $64, LEN + movdqa STATE0_A, STATE0_B + movdqa STATE1_A, STATE1_B +.Lfinup2x_loop: + // Load the next two data blocks. + movdqu 0*16(DATA1), MSG0_A + movdqu 0*16(DATA2), MSG0_B + movdqu 1*16(DATA1), MSG1_A + movdqu 1*16(DATA2), MSG1_B + movdqu 2*16(DATA1), MSG2_A + movdqu 2*16(DATA2), MSG2_B + movdqu 3*16(DATA1), MSG3_A + movdqu 3*16(DATA2), MSG3_B + add $64, DATA1 + add $64, DATA2 +.Lfinup2x_loop_have_data: + // Convert the words of the data blocks from big endian. + pshufb SHUF_MASK, MSG0_A + pshufb SHUF_MASK, MSG0_B + pshufb SHUF_MASK, MSG1_A + pshufb SHUF_MASK, MSG1_B + pshufb SHUF_MASK, MSG2_A + pshufb SHUF_MASK, MSG2_B + pshufb SHUF_MASK, MSG3_A + pshufb SHUF_MASK, MSG3_B +.Lfinup2x_loop_have_bswapped_data: + + // Save the original state for each block. + movdqa STATE0_A, 0*16(%rsp) + movdqa STATE0_B, 1*16(%rsp) + movdqa STATE1_A, 2*16(%rsp) + movdqa STATE1_B, 3*16(%rsp) + + // Do the SHA-256 rounds on each block. +.irp i, 0, 16, 32, 48 + do_4rounds_2x (\i + 0), MSG0_A, MSG1_A, MSG2_A, MSG3_A \ + MSG0_B, MSG1_B, MSG2_B, MSG3_B + do_4rounds_2x (\i + 4), MSG1_A, MSG2_A, MSG3_A, MSG0_A \ + MSG1_B, MSG2_B, MSG3_B, MSG0_B + do_4rounds_2x (\i + 8), MSG2_A, MSG3_A, MSG0_A, MSG1_A \ + MSG2_B, MSG3_B, MSG0_B, MSG1_B + do_4rounds_2x (\i + 12), MSG3_A, MSG0_A, MSG1_A, MSG2_A \ + MSG3_B, MSG0_B, MSG1_B, MSG2_B +.endr + + // Add the original state for each block. + paddd 0*16(%rsp), STATE0_A + paddd 1*16(%rsp), STATE0_B + paddd 2*16(%rsp), STATE1_A + paddd 3*16(%rsp), STATE1_B + + // Update LEN and loop back if more blocks remain. + sub $64, LEN + jge .Lfinup2x_loop + + // Check if any final blocks need to be handled. + // FINAL_STEP = 2: all done + // FINAL_STEP = 1: need to do count-only padding block + // FINAL_STEP = 0: need to do the block with 0x80 padding byte + cmp $1, FINAL_STEP + jg .Lfinup2x_done + je .Lfinup2x_finalize_countonly + add $64, LEN + jz .Lfinup2x_finalize_blockaligned + + // Not block-aligned; 1 <= len <= 63 data bytes remain. Pad the block. + mov $64, %ebx + sub LEN, %ebx // ebx = 64 - LEN + sub %rbx, DATA1 // DATA1 -= 64 - LEN + sub %rbx, DATA2 // DATA2 -= 64 - LEN + movdqu 0*16(DATA1), MSG0_A + movdqu 1*16(DATA1), MSG1_A + movdqu 2*16(DATA1), MSG2_A + movdqu 3*16(DATA1), MSG3_A + movdqa MSG0_A, 0*16(%rsp) + movdqa MSG1_A, 1*16(%rsp) + movdqa MSG2_A, 2*16(%rsp) + movdqa MSG3_A, 3*16(%rsp) + mov $0x80, FINAL_STEP // using FINAL_STEP as a temporary + movd FINAL_STEP, MSG0_A + pxor MSG1_A, MSG1_A + movdqa MSG0_A, 4*16(%rsp) + movdqa MSG1_A, 5*16(%rsp) + movdqa MSG1_A, 6*16(%rsp) + movdqa MSG1_A, 7*16(%rsp) + cmp $56, LEN + jge 1f // will COUNT spill into its own block? + shl $3, COUNT + bswap COUNT + mov COUNT, 56(%rsp,%rbx) + mov $2, FINAL_STEP // won't need count-only block + jmp 2f +1: + mov $1, FINAL_STEP // will need count-only block +2: + movdqu 0*16(%rsp,%rbx), MSG0_A + movdqu 1*16(%rsp,%rbx), MSG1_A + movdqu 2*16(%rsp,%rbx), MSG2_A + movdqu 3*16(%rsp,%rbx), MSG3_A + + movdqu 0*16(DATA2), MSG0_B + movdqu 1*16(DATA2), MSG1_B + movdqu 2*16(DATA2), MSG2_B + movdqu 3*16(DATA2), MSG3_B + movdqa MSG0_B, 0*16(%rsp) + movdqa MSG1_B, 1*16(%rsp) + movdqa MSG2_B, 2*16(%rsp) + movdqa MSG3_B, 3*16(%rsp) + movdqu 0*16(%rsp,%rbx), MSG0_B + movdqu 1*16(%rsp,%rbx), MSG1_B + movdqu 2*16(%rsp,%rbx), MSG2_B + movdqu 3*16(%rsp,%rbx), MSG3_B + jmp .Lfinup2x_loop_have_data + + // Prepare a padding block, either: + // + // {0x80, 0, 0, 0, ..., count (as __be64)} + // This is for a block aligned message. + // + // { 0, 0, 0, 0, ..., count (as __be64)} + // This is for a message whose length mod 64 is >= 56. + // + // Pre-swap the endianness of the words. +.Lfinup2x_finalize_countonly: + pxor MSG0_A, MSG0_A + jmp 1f + +.Lfinup2x_finalize_blockaligned: + mov $0x80000000, %ebx + movd %ebx, MSG0_A +1: + pxor MSG1_A, MSG1_A + pxor MSG2_A, MSG2_A + ror $29, COUNT + movq COUNT, MSG3_A + pslldq $8, MSG3_A + movdqa MSG0_A, MSG0_B + pxor MSG1_B, MSG1_B + pxor MSG2_B, MSG2_B + movdqa MSG3_A, MSG3_B + mov $2, FINAL_STEP + jmp .Lfinup2x_loop_have_bswapped_data + +.Lfinup2x_done: + // Write the two digests with all bytes in the correct order. + movdqa STATE0_A, TMP_A + movdqa STATE0_B, TMP_B + punpcklqdq STATE1_A, STATE0_A // GHEF + punpcklqdq STATE1_B, STATE0_B + punpckhqdq TMP_A, STATE1_A // ABCD + punpckhqdq TMP_B, STATE1_B + pshufd $0xB1, STATE0_A, STATE0_A // HGFE + pshufd $0xB1, STATE0_B, STATE0_B + pshufd $0x1B, STATE1_A, STATE1_A // DCBA + pshufd $0x1B, STATE1_B, STATE1_B + pshufb SHUF_MASK, STATE0_A + pshufb SHUF_MASK, STATE0_B + pshufb SHUF_MASK, STATE1_A + pshufb SHUF_MASK, STATE1_B + movdqu STATE0_A, 1*16(OUT1) + movdqu STATE0_B, 1*16(OUT2) + movdqu STATE1_A, 0*16(OUT1) + movdqu STATE1_B, 0*16(OUT2) + + mov %rbp, %rsp + pop %rbp + pop %rbx + RET +SYM_FUNC_END(__sha256_ni_finup2x) + .section .rodata.cst256.K256, "aM", @progbits, 256 .align 64 K256: .long 0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5 .long 0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5 diff --git a/arch/x86/crypto/sha256_ssse3_glue.c b/arch/x86/crypto/sha256_ssse3_glue.c index e04a43d9f7d55..a6adf27d1df35 100644 --- a/arch/x86/crypto/sha256_ssse3_glue.c +++ b/arch/x86/crypto/sha256_ssse3_glue.c @@ -331,10 +331,15 @@ static void unregister_sha256_avx2(void) #ifdef CONFIG_AS_SHA256_NI asmlinkage void sha256_ni_transform(struct sha256_state *digest, const u8 *data, int rounds); +asmlinkage void __sha256_ni_finup2x(const struct sha256_state *sctx, + const u8 *data1, const u8 *data2, int len, + u8 out1[SHA256_DIGEST_SIZE], + u8 out2[SHA256_DIGEST_SIZE]); + static int sha256_ni_update(struct shash_desc *desc, const u8 *data, unsigned int len) { return _sha256_update(desc, data, len, sha256_ni_transform); } @@ -355,17 +360,52 @@ static int sha256_ni_digest(struct shash_desc *desc, const u8 *data, { return sha256_base_init(desc) ?: sha256_ni_finup(desc, data, len, out); } +static noinline_for_stack int +sha256_finup2x_fallback(struct sha256_state *sctx, const u8 *data1, + const u8 *data2, unsigned int len, u8 *out1, u8 *out2) +{ + struct sha256_state sctx2 = *sctx; + + sha256_update(sctx, data1, len); + sha256_final(sctx, out1); + sha256_update(&sctx2, data2, len); + sha256_final(&sctx2, out2); + return 0; +} + +static int sha256_ni_finup2x(struct shash_desc *desc, + const u8 *data1, const u8 *data2, + unsigned int len, u8 *out1, u8 *out2) +{ + struct sha256_state *sctx = shash_desc_ctx(desc); + + if (unlikely(!crypto_simd_usable() || len < SHA256_BLOCK_SIZE)) + return sha256_finup2x_fallback(sctx, data1, data2, len, + out1, out2); + + /* __sha256_ni_finup2x() assumes the following offsets. */ + BUILD_BUG_ON(offsetof(struct sha256_state, state) != 0); + BUILD_BUG_ON(offsetof(struct sha256_state, count) != 32); + BUILD_BUG_ON(offsetof(struct sha256_state, buf) != 40); + + kernel_fpu_begin(); + __sha256_ni_finup2x(sctx, data1, data2, len, out1, out2); + kernel_fpu_end(); + return 0; +} + static struct shash_alg sha256_ni_algs[] = { { .digestsize = SHA256_DIGEST_SIZE, .init = sha256_base_init, .update = sha256_ni_update, .final = sha256_ni_final, .finup = sha256_ni_finup, .digest = sha256_ni_digest, + .finup2x = sha256_ni_finup2x, .descsize = sizeof(struct sha256_state), .base = { .cra_name = "sha256", .cra_driver_name = "sha256-ni", .cra_priority = 250, From patchwork Mon Apr 15 21:37:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630756 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 38B19C04FFE for ; Mon, 15 Apr 2024 21:39:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=UOnymQ4go5pgNBqubvuC+s9zdX3DF9zo9heNeCBKVGc=; b=b6bS6fPdINnipY UFsVFhlrNrzrzVZXIu0zmxWIjQ0anDYK/IN47VpsCQ6yZYfE5x8W9GkQD1cYpOwOmYYeWrFRhc3SP mVVPMKZSbFfR4ax5OQGcXLgVWoWov71T0WQ9wqa6gq8vjaZf5kzvY4ewuzzHtN3VjYbGOdVQWwxdl Tv5+edypW6/Meb0VZ80P/Sh5a3MbRi/25zdyY+S6kOP4M2xrGsq1ktQ+hRWRNtj+ajD7wqimpNN7o hWoBr3lx50dOZDA5WjfoEcZNR/qdCVjezp7Gvm7k9g8F2G7AHtkegukKaB0lllT7MtFwhzVG7seS9 Of9PDFuvVTj8bWZXJ7gQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2e-00000009zDt-3rnp; Mon, 15 Apr 2024 21:39:08 +0000 Received: from sin.source.kernel.org ([145.40.73.55]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2O-00000009z3P-3wzw for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:59 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id EE16DCE0E29; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 53F2EC4AF0E; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217130; bh=+6OXEPm+JzuPSmBly6c9GdLMVk3Cx5tB37NvqDJaJfU=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=unDJ1EUgZV8gGYi7QtJ/KYcJdaeZOax6J/JPUg0h51yT9Reh3ppM2VsTTFGr5HX6w ktUBsF2kRH0zLY3/Tdq6hOp6oMQ5nixDyspsTzZkyjMF33C8Bd8Ez5rYPT3wYVj9Iu el8Qh8K7QwBpga24wm26GcWkNIOjLqb53pmhwekC+3NqgyQOajB3ZRy8jv1R/lt7oA lIPMl5LUhaE9SvYzW2hDFSLWNyFTG5fa4lipQugBbKrvRy6kjMM+EOCxWrMEgWFKvj 9FNQcwiQIBJUh5ZIv7NuDmNxsxspcMze2gmuJdatCHIiBuKzIFxURDA77kor5y0hpI ca0AKICiIBUTw== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 5/8] crypto: arm64/sha256-ce - add support for finup2x Date: Mon, 15 Apr 2024 14:37:16 -0700 Message-ID: <20240415213719.120673-6-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143853_432840_8EBE1BA0 X-CRM114-Status: GOOD ( 22.55 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Add an implementation of finup2x to sha256-ce. finup2x interleaves a finup operation for two equal-length messages that share a common prefix. dm-verity and fs-verity will take advantage of this for significantly improved performance on capable CPUs. On an ARM Cortex-X1, this increases the throughput of SHA-256 hashing 4096-byte messages by 82%. Signed-off-by: Eric Biggers --- arch/arm64/crypto/sha2-ce-core.S | 261 ++++++++++++++++++++++++++++++- arch/arm64/crypto/sha2-ce-glue.c | 40 +++++ 2 files changed, 295 insertions(+), 6 deletions(-) diff --git a/arch/arm64/crypto/sha2-ce-core.S b/arch/arm64/crypto/sha2-ce-core.S index fce84d88ddb2c..c290b85f64080 100644 --- a/arch/arm64/crypto/sha2-ce-core.S +++ b/arch/arm64/crypto/sha2-ce-core.S @@ -68,22 +68,26 @@ .word 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5 .word 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3 .word 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208 .word 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 + .macro load_round_constants tmp + adr_l \tmp, .Lsha2_rcon + ld1 { v0.4s- v3.4s}, [\tmp], #64 + ld1 { v4.4s- v7.4s}, [\tmp], #64 + ld1 { v8.4s-v11.4s}, [\tmp], #64 + ld1 {v12.4s-v15.4s}, [\tmp] + .endm + /* * int __sha256_ce_transform(struct sha256_ce_state *sst, u8 const *src, * int blocks) */ .text SYM_FUNC_START(__sha256_ce_transform) - /* load round constants */ - adr_l x8, .Lsha2_rcon - ld1 { v0.4s- v3.4s}, [x8], #64 - ld1 { v4.4s- v7.4s}, [x8], #64 - ld1 { v8.4s-v11.4s}, [x8], #64 - ld1 {v12.4s-v15.4s}, [x8] + + load_round_constants x8 /* load state */ ld1 {dgav.4s, dgbv.4s}, [x0] /* load sha256_ce_state::finalize */ @@ -153,5 +157,250 @@ CPU_LE( rev32 v19.16b, v19.16b ) /* store new state */ 3: st1 {dgav.4s, dgbv.4s}, [x0] mov w0, w2 ret SYM_FUNC_END(__sha256_ce_transform) + + .unreq dga + .unreq dgav + .unreq dgb + .unreq dgbv + .unreq t0 + .unreq t1 + .unreq dg0q + .unreq dg0v + .unreq dg1q + .unreq dg1v + .unreq dg2q + .unreq dg2v + + // parameters for __sha256_ce_finup2x() + sctx .req x0 + data1 .req x1 + data2 .req x2 + len .req w3 + out1 .req x4 + out2 .req x5 + + // other scalar variables + count .req x6 + final_step .req w7 + + // x8-x9 are used as temporaries. + + // v0-v15 are used to cache the SHA-256 round constants. + // v16-v23 are used for the data. + // v24-v31 are used for the state and temporaries as given below. + state0_a_q .req q24 + state0_a .req v24 + state1_a_q .req q25 + state1_a .req v25 + state0_b_q .req q26 + state0_b .req v26 + state1_b_q .req q27 + state1_b .req v27 + t0_a .req v28 + t0_b .req v29 + t1_a_q .req q30 + t1_a .req v30 + t1_b_q .req q31 + t1_b .req v31 + +#define OFFSETOF_COUNT 32 // offsetof(struct sha256_state, count) +#define OFFSETOF_BUF 40 // offsetof(struct sha256_state, buf) + + .macro do_4rounds_2x i, k, w0_a, w1_a, w2_a, w3_a, \ + w0_b, w1_b, w2_b, w3_b + add t0_a\().4s, \w0_a\().4s, \k\().4s + add t0_b\().4s, \w0_b\().4s, \k\().4s + .if \i < 48 + sha256su0 \w0_a\().4s, \w1_a\().4s + sha256su0 \w0_b\().4s, \w1_b\().4s + sha256su1 \w0_a\().4s, \w2_a\().4s, \w3_a\().4s + sha256su1 \w0_b\().4s, \w2_b\().4s, \w3_b\().4s + .endif + mov t1_a.16b, state0_a.16b + mov t1_b.16b, state0_b.16b + sha256h state0_a_q, state1_a_q, t0_a\().4s + sha256h state0_b_q, state1_b_q, t0_b\().4s + sha256h2 state1_a_q, t1_a_q, t0_a\().4s + sha256h2 state1_b_q, t1_b_q, t0_b\().4s + .endm + + .macro do_16rounds_2x i, k0, k1, k2, k3 + do_4rounds_2x \i + 0, \k0, v16, v17, v18, v19, v20, v21, v22, v23 + do_4rounds_2x \i + 4, \k1, v17, v18, v19, v16, v21, v22, v23, v20 + do_4rounds_2x \i + 8, \k2, v18, v19, v16, v17, v22, v23, v20, v21 + do_4rounds_2x \i + 12, \k3, v19, v16, v17, v18, v23, v20, v21, v22 + .endm + +// +// void __sha256_ce_finup2x(const struct sha256_state *sctx, +// const u8 *data1, const u8 *data2, int len, +// u8 out1[SHA256_DIGEST_SIZE], +// u8 out2[SHA256_DIGEST_SIZE]); +// +// This function computes the SHA-256 digests of two messages |data1| and +// |data2| that are both |len| bytes long, starting from the initial state +// |sctx|. |len| must be at least SHA256_BLOCK_SIZE. +// +// The instructions for the two SHA-256 operations are interleaved. On many +// CPUs, this is almost twice as fast as hashing each message individually due +// to taking better advantage of the CPU's SHA-256 and SIMD throughput. +// +SYM_FUNC_START(__sha256_ce_finup2x) + sub sp, sp, #128 + mov final_step, #0 + load_round_constants x8 + + // Load the initial state from sctx->state. + ld1 {state0_a.4s-state1_a.4s}, [sctx] + + // Load sctx->count. Take the mod 64 of it to get the number of bytes + // that are buffered in sctx->buf. Also save it in a register with len + // added to it. + ldr x8, [sctx, #OFFSETOF_COUNT] + add count, x8, len, sxtw + and x8, x8, #63 + cbz x8, .Lfinup2x_enter_loop // No bytes buffered? + + // x8 bytes (1 to 63) are currently buffered in sctx->buf. Load them + // followed by the first 64 - x8 bytes of data. Since len >= 64, we + // just load 64 bytes from each of sctx->buf, data1, and data2 + // unconditionally and rearrange the data as needed. + add x9, sctx, #OFFSETOF_BUF + ld1 {v16.16b-v19.16b}, [x9] + st1 {v16.16b-v19.16b}, [sp] + + ld1 {v16.16b-v19.16b}, [data1], #64 + add x9, sp, x8 + st1 {v16.16b-v19.16b}, [x9] + ld1 {v16.4s-v19.4s}, [sp] + + ld1 {v20.16b-v23.16b}, [data2], #64 + st1 {v20.16b-v23.16b}, [x9] + ld1 {v20.4s-v23.4s}, [sp] + + sub len, len, #64 + sub data1, data1, x8 + sub data2, data2, x8 + add len, len, w8 + mov state0_b.16b, state0_a.16b + mov state1_b.16b, state1_a.16b + b .Lfinup2x_loop_have_data + +.Lfinup2x_enter_loop: + sub len, len, #64 + mov state0_b.16b, state0_a.16b + mov state1_b.16b, state1_a.16b +.Lfinup2x_loop: + // Load the next two data blocks. + ld1 {v16.4s-v19.4s}, [data1], #64 + ld1 {v20.4s-v23.4s}, [data2], #64 +.Lfinup2x_loop_have_data: + // Convert the words of the data blocks from big endian. +CPU_LE( rev32 v16.16b, v16.16b ) +CPU_LE( rev32 v17.16b, v17.16b ) +CPU_LE( rev32 v18.16b, v18.16b ) +CPU_LE( rev32 v19.16b, v19.16b ) +CPU_LE( rev32 v20.16b, v20.16b ) +CPU_LE( rev32 v21.16b, v21.16b ) +CPU_LE( rev32 v22.16b, v22.16b ) +CPU_LE( rev32 v23.16b, v23.16b ) +.Lfinup2x_loop_have_bswapped_data: + + // Save the original state for each block. + st1 {state0_a.4s-state1_b.4s}, [sp] + + // Do the SHA-256 rounds on each block. + do_16rounds_2x 0, v0, v1, v2, v3 + do_16rounds_2x 16, v4, v5, v6, v7 + do_16rounds_2x 32, v8, v9, v10, v11 + do_16rounds_2x 48, v12, v13, v14, v15 + + // Add the original state for each block. + ld1 {v16.4s-v19.4s}, [sp] + add state0_a.4s, state0_a.4s, v16.4s + add state1_a.4s, state1_a.4s, v17.4s + add state0_b.4s, state0_b.4s, v18.4s + add state1_b.4s, state1_b.4s, v19.4s + + // Update len and loop back if more blocks remain. + sub len, len, #64 + tbz len, #31, .Lfinup2x_loop + + // Check if any final blocks need to be handled. + // final_step = 2: all done + // final_step = 1: need to do count-only padding block + // final_step = 0: need to do the block with 0x80 padding byte + tbnz final_step, #1, .Lfinup2x_done + tbnz final_step, #0, .Lfinup2x_finalize_countonly + add len, len, #64 + cbz len, .Lfinup2x_finalize_blockaligned + + // Not block-aligned; 1 <= len <= 63 data bytes remain. Pad the block. + sub w8, len, #64 // w8 = len - 64 + add data1, data1, w8, sxtw // data1 += len - 64 + add data2, data2, w8, sxtw // data2 += len - 64 + ld1 {v16.16b-v19.16b}, [data1] + st1 {v16.16b-v19.16b}, [sp] + mov x9, 0x80 + fmov d16, x9 + movi v17.16b, #0 + stp q16, q17, [sp, #64] + stp q17, q17, [sp, #96] + sub x9, sp, w8, sxtw // x9 = &sp[64 - len] + cmp len, #56 + b.ge 1f // will count spill into its own block? + lsl count, count, #3 + rev count, count + str count, [x9, #56] + mov final_step, #2 // won't need count-only block + b 2f +1: + mov final_step, #1 // will need count-only block +2: + ld1 {v16.4s-v19.4s}, [x9] + ld1 {v20.16b-v23.16b}, [data2] + st1 {v20.16b-v23.16b}, [sp] + ld1 {v20.4s-v23.4s}, [x9] + b .Lfinup2x_loop_have_data + + // Prepare a padding block, either: + // + // {0x80, 0, 0, 0, ..., count (as __be64)} + // This is for a block aligned message. + // + // { 0, 0, 0, 0, ..., count (as __be64)} + // This is for a message whose length mod 64 is >= 56. + // + // Pre-swap the endianness of the words. +.Lfinup2x_finalize_countonly: + movi v16.2d, #0 + b 1f +.Lfinup2x_finalize_blockaligned: + mov x8, #0x80000000 + fmov d16, x8 +1: + movi v17.2d, #0 + movi v18.2d, #0 + ror count, count, #29 // ror(lsl(count, 3), 32) + mov v19.d[0], xzr + mov v19.d[1], count + mov v20.16b, v16.16b + movi v21.2d, #0 + movi v22.2d, #0 + mov v23.16b, v19.16b + mov final_step, #2 + b .Lfinup2x_loop_have_bswapped_data + +.Lfinup2x_done: + // Write the two digests with all bytes in the correct order. +CPU_LE( rev32 state0_a.16b, state0_a.16b ) +CPU_LE( rev32 state1_a.16b, state1_a.16b ) +CPU_LE( rev32 state0_b.16b, state0_b.16b ) +CPU_LE( rev32 state1_b.16b, state1_b.16b ) + st1 {state0_a.4s-state1_a.4s}, [out1] + st1 {state0_b.4s-state1_b.4s}, [out2] + add sp, sp, #128 + ret +SYM_FUNC_END(__sha256_ce_finup2x) diff --git a/arch/arm64/crypto/sha2-ce-glue.c b/arch/arm64/crypto/sha2-ce-glue.c index 0a44d2e7ee1f7..0b125d8fda284 100644 --- a/arch/arm64/crypto/sha2-ce-glue.c +++ b/arch/arm64/crypto/sha2-ce-glue.c @@ -31,10 +31,15 @@ extern const u32 sha256_ce_offsetof_count; extern const u32 sha256_ce_offsetof_finalize; asmlinkage int __sha256_ce_transform(struct sha256_ce_state *sst, u8 const *src, int blocks); +asmlinkage void __sha256_ce_finup2x(const struct sha256_state *sctx, + const u8 *data1, const u8 *data2, int len, + u8 out1[SHA256_DIGEST_SIZE], + u8 out2[SHA256_DIGEST_SIZE]); + static void sha256_ce_transform(struct sha256_state *sst, u8 const *src, int blocks) { while (blocks) { int rem; @@ -122,10 +127,44 @@ static int sha256_ce_digest(struct shash_desc *desc, const u8 *data, { sha256_base_init(desc); return sha256_ce_finup(desc, data, len, out); } +static noinline_for_stack int +sha256_finup2x_fallback(struct sha256_state *sctx, const u8 *data1, + const u8 *data2, unsigned int len, u8 *out1, u8 *out2) +{ + struct sha256_state sctx2 = *sctx; + + sha256_update(sctx, data1, len); + sha256_final(sctx, out1); + sha256_update(&sctx2, data2, len); + sha256_final(&sctx2, out2); + return 0; +} + +static int sha256_ce_finup2x(struct shash_desc *desc, + const u8 *data1, const u8 *data2, + unsigned int len, u8 *out1, u8 *out2) +{ + struct sha256_ce_state *sctx = shash_desc_ctx(desc); + + if (unlikely(!crypto_simd_usable() || len < SHA256_BLOCK_SIZE)) + return sha256_finup2x_fallback(&sctx->sst, data1, data2, len, + out1, out2); + + /* __sha256_ce_finup2x() assumes the following offsets. */ + BUILD_BUG_ON(offsetof(struct sha256_state, state) != 0); + BUILD_BUG_ON(offsetof(struct sha256_state, count) != 32); + BUILD_BUG_ON(offsetof(struct sha256_state, buf) != 40); + + kernel_neon_begin(); + __sha256_ce_finup2x(&sctx->sst, data1, data2, len, out1, out2); + kernel_neon_end(); + return 0; +} + static int sha256_ce_export(struct shash_desc *desc, void *out) { struct sha256_ce_state *sctx = shash_desc_ctx(desc); memcpy(out, &sctx->sst, sizeof(struct sha256_state)); @@ -162,10 +201,11 @@ static struct shash_alg algs[] = { { .init = sha256_base_init, .update = sha256_ce_update, .final = sha256_ce_final, .finup = sha256_ce_finup, .digest = sha256_ce_digest, + .finup2x = sha256_ce_finup2x, .export = sha256_ce_export, .import = sha256_ce_import, .descsize = sizeof(struct sha256_ce_state), .statesize = sizeof(struct sha256_state), .digestsize = SHA256_DIGEST_SIZE, From patchwork Mon Apr 15 21:37:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630753 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id E0CF6C41513 for ; Mon, 15 Apr 2024 21:39:18 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=61VkLNAdxKhO4z0cFiPTGhpjYC9yg9D0Jglpyv1il7Q=; b=S19DPa5iPqSxoy ZKmVe0quzbAFvHVS7/jxxRpNJGEMwmzpVDSRJ1OStBdvj6vdx34IOfX2WeJDdsQd1odHwT15IijEZ JrB748tu1FxlH2b9oRtBcg7ho5+Fv/FBR7zC5CZoV45Xugz9/fCW7/56Dc4JO8eRpGDpddBY2qAV4 9B+B6uajJZGtOud0hnA2U5bRtLn9qUyXbxX/tJxRxgKxUWrAv6MXFZsd7BQvcDCOqQ3Yx5HNh+ZAh YUcMYD4hK7Ow6wkOLr19l1XQN2VtxR77JpDXC+0qXTPnVdaTUO8P0RoiAm6TmyFYsgqWdVkIoFBDb o1R4E3u6WWHUxrk9N1PA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2c-00000009zC1-29bF; Mon, 15 Apr 2024 21:39:06 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2N-00000009z3A-2wlo for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:55 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 2CE9E60ED2; Mon, 15 Apr 2024 21:38:51 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id B7C5BC32781; Mon, 15 Apr 2024 21:38:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217131; bh=1xJ/IShDstfbjrpvhfCgSB3980tF6vNkfAQaXiswAH8=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=LkYFIcBEQqcEaa5i+eqcSk4J9tiKuGMHEpisiEjlwUBd6yReJjSSEHrHJVM3MoPeN YUDbyIf8l489CUJ+zVzmv59M5gbgOtgcUlV/20NUpcvLl7ILUoKKa9ZEBfLQkKXMEE ApxHmBdrZoW++M6oydGR+q5pE+PQALepLmvF6WuC8xuXwaIYYJ59teu+XJsjCyx6Gk 6e+aiF1o9aZREHFrkY3UxiGPaGaOFb8S6vttk6uY6BblOGuJTKt6Hp74rk7dK2+L0w RL68V0Je2x4p/g8NzGDA3MNQTnWfw3WMn5QenbMjeLUx+h7HQKjS/4fFyBneZSyfxc xrl0VF2vw9Jew== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 6/8] fsverity: improve performance by using multibuffer hashing Date: Mon, 15 Apr 2024 14:37:17 -0700 Message-ID: <20240415213719.120673-7-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143852_034311_7445223E X-CRM114-Status: GOOD ( 32.72 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers When supported by the hash algorithm, use crypto_shash_finup2x() to interleave the hashing of pairs of data blocks. On some CPUs this nearly doubles hashing performance. The increase in overall throughput of cold-cache fsverity reads that I'm seeing on arm64 and x86_64 is roughly 35% (though this metric is hard to measure as it jumps around a lot). For now this is only done on the verification path, and only for data blocks, not Merkle tree blocks. We could use finup2x on Merkle tree blocks too, but that is less important as there aren't as many Merkle tree blocks as data blocks, and that would require some additional code restructuring. We could also use finup2x to accelerate building the Merkle tree, but verification performance is more important. Signed-off-by: Eric Biggers --- fs/verity/fsverity_private.h | 5 + fs/verity/hash_algs.c | 31 +++++- fs/verity/open.c | 6 ++ fs/verity/verify.c | 177 +++++++++++++++++++++++++++++------ 4 files changed, 186 insertions(+), 33 deletions(-) diff --git a/fs/verity/fsverity_private.h b/fs/verity/fsverity_private.h index b3506f56e180b..b72c03f8f4163 100644 --- a/fs/verity/fsverity_private.h +++ b/fs/verity/fsverity_private.h @@ -27,10 +27,11 @@ struct fsverity_hash_alg { /* * The HASH_ALGO_* constant for this algorithm. This is different from * FS_VERITY_HASH_ALG_*, which uses a different numbering scheme. */ enum hash_algo algo_id; + bool supports_finup2x; /* crypto_shash_supports_finup2x(tfm) */ }; /* Merkle tree parameters: hash algorithm, initial hash state, and topology */ struct merkle_tree_params { const struct fsverity_hash_alg *hash_alg; /* the hash algorithm */ @@ -65,10 +66,11 @@ struct merkle_tree_params { */ struct fsverity_info { struct merkle_tree_params tree_params; u8 root_hash[FS_VERITY_MAX_DIGEST_SIZE]; u8 file_digest[FS_VERITY_MAX_DIGEST_SIZE]; + u8 zero_block_hash[FS_VERITY_MAX_DIGEST_SIZE]; const struct inode *inode; unsigned long *hash_block_verified; }; #define FS_VERITY_MAX_SIGNATURE_SIZE (FS_VERITY_MAX_DESCRIPTOR_SIZE - \ @@ -82,10 +84,13 @@ const struct fsverity_hash_alg *fsverity_get_hash_alg(const struct inode *inode, unsigned int num); const u8 *fsverity_prepare_hash_state(const struct fsverity_hash_alg *alg, const u8 *salt, size_t salt_size); int fsverity_hash_block(const struct merkle_tree_params *params, const struct inode *inode, const void *data, u8 *out); +int fsverity_hash_2_blocks(const struct merkle_tree_params *params, + const struct inode *inode, const void *data1, + const void *data2, u8 *out1, u8 *out2); int fsverity_hash_buffer(const struct fsverity_hash_alg *alg, const void *data, size_t size, u8 *out); void __init fsverity_check_hash_algs(void); /* init.c */ diff --git a/fs/verity/hash_algs.c b/fs/verity/hash_algs.c index 6b08b1d9a7d7c..0be2903fa8f3f 100644 --- a/fs/verity/hash_algs.c +++ b/fs/verity/hash_algs.c @@ -82,12 +82,15 @@ const struct fsverity_hash_alg *fsverity_get_hash_alg(const struct inode *inode, if (WARN_ON_ONCE(alg->digest_size != crypto_shash_digestsize(tfm))) goto err_free_tfm; if (WARN_ON_ONCE(alg->block_size != crypto_shash_blocksize(tfm))) goto err_free_tfm; - pr_info("%s using implementation \"%s\"\n", - alg->name, crypto_shash_driver_name(tfm)); + alg->supports_finup2x = crypto_shash_supports_finup2x(tfm); + + pr_info("%s using implementation \"%s\"%s\n", + alg->name, crypto_shash_driver_name(tfm), + alg->supports_finup2x ? " (multibuffer)" : ""); /* pairs with smp_load_acquire() above */ smp_store_release(&alg->tfm, tfm); goto out_unlock; @@ -195,10 +198,34 @@ int fsverity_hash_block(const struct merkle_tree_params *params, if (err) fsverity_err(inode, "Error %d computing block hash", err); return err; } +int fsverity_hash_2_blocks(const struct merkle_tree_params *params, + const struct inode *inode, const void *data1, + const void *data2, u8 *out1, u8 *out2) +{ + SHASH_DESC_ON_STACK(desc, params->hash_alg->tfm); + int err; + + desc->tfm = params->hash_alg->tfm; + + if (params->hashstate) + err = crypto_shash_import(desc, params->hashstate); + else + err = crypto_shash_init(desc); + if (err) { + fsverity_err(inode, "Error %d importing hash state", err); + return err; + } + err = crypto_shash_finup2x(desc, data1, data2, params->block_size, + out1, out2); + if (err) + fsverity_err(inode, "Error %d computing block hashes", err); + return err; +} + /** * fsverity_hash_buffer() - hash some data * @alg: the hash algorithm to use * @data: the data to hash * @size: size of data to hash, in bytes diff --git a/fs/verity/open.c b/fs/verity/open.c index fdeb95eca3af3..4ae07c689c563 100644 --- a/fs/verity/open.c +++ b/fs/verity/open.c @@ -206,10 +206,16 @@ struct fsverity_info *fsverity_create_info(const struct inode *inode, if (err) { fsverity_err(inode, "Error %d computing file digest", err); goto fail; } + err = fsverity_hash_block(&vi->tree_params, inode, + page_address(ZERO_PAGE(0)), + vi->zero_block_hash); + if (err) + goto fail; + err = fsverity_verify_signature(vi, desc->signature, le32_to_cpu(desc->sig_size)); if (err) goto fail; diff --git a/fs/verity/verify.c b/fs/verity/verify.c index 4fcad0825a120..ded431512cf5a 100644 --- a/fs/verity/verify.c +++ b/fs/verity/verify.c @@ -77,29 +77,33 @@ static bool is_hash_block_verified(struct fsverity_info *vi, struct page *hpage, SetPageChecked(hpage); return false; } /* - * Verify a single data block against the file's Merkle tree. + * Verify the hash of a single data block against the file's Merkle tree. + * + * @real_dblock_hash specifies the hash of the data block, and @data_pos + * specifies the byte position of the data block within the file. * * In principle, we need to verify the entire path to the root node. However, * for efficiency the filesystem may cache the hash blocks. Therefore we need * only ascend the tree until an already-verified hash block is seen, and then * verify the path to that block. * * Return: %true if the data block is valid, else %false. */ static bool verify_data_block(struct inode *inode, struct fsverity_info *vi, - const void *data, u64 data_pos, unsigned long max_ra_pages) + const u8 *real_dblock_hash, u64 data_pos, + unsigned long max_ra_pages) { const struct merkle_tree_params *params = &vi->tree_params; const unsigned int hsize = params->digest_size; int level; u8 _want_hash[FS_VERITY_MAX_DIGEST_SIZE]; const u8 *want_hash; - u8 real_hash[FS_VERITY_MAX_DIGEST_SIZE]; + u8 real_hblock_hash[FS_VERITY_MAX_DIGEST_SIZE]; /* The hash blocks that are traversed, indexed by level */ struct { /* Page containing the hash block */ struct page *page; /* Mapped address of the hash block (will be within @page) */ @@ -125,11 +129,12 @@ verify_data_block(struct inode *inode, struct fsverity_info *vi, * doesn't cover data blocks fully past EOF. But the entire * page spanning EOF can be visible to userspace via a mmap, and * any part past EOF should be all zeroes. Therefore, we need * to verify that any data blocks fully past EOF are all zeroes. */ - if (memchr_inv(data, 0, params->block_size)) { + if (memcmp(vi->zero_block_hash, real_dblock_hash, + params->block_size) != 0) { fsverity_err(inode, "FILE CORRUPTED! Data past EOF is not zeroed"); return false; } return true; @@ -200,13 +205,14 @@ verify_data_block(struct inode *inode, struct fsverity_info *vi, struct page *hpage = hblocks[level - 1].page; const void *haddr = hblocks[level - 1].addr; unsigned long hblock_idx = hblocks[level - 1].index; unsigned int hoffset = hblocks[level - 1].hoffset; - if (fsverity_hash_block(params, inode, haddr, real_hash) != 0) + if (fsverity_hash_block(params, inode, haddr, + real_hblock_hash) != 0) goto error; - if (memcmp(want_hash, real_hash, hsize) != 0) + if (memcmp(want_hash, real_hblock_hash, hsize) != 0) goto corrupted; /* * Mark the hash block as verified. This must be atomic and * idempotent, as the same hash block might be verified by * multiple threads concurrently. @@ -219,55 +225,145 @@ verify_data_block(struct inode *inode, struct fsverity_info *vi, want_hash = _want_hash; kunmap_local(haddr); put_page(hpage); } - /* Finally, verify the data block. */ - if (fsverity_hash_block(params, inode, data, real_hash) != 0) - goto error; - if (memcmp(want_hash, real_hash, hsize) != 0) + /* Finally, verify the hash of the data block. */ + if (memcmp(want_hash, real_dblock_hash, hsize) != 0) goto corrupted; return true; corrupted: fsverity_err(inode, "FILE CORRUPTED! pos=%llu, level=%d, want_hash=%s:%*phN, real_hash=%s:%*phN", data_pos, level - 1, params->hash_alg->name, hsize, want_hash, - params->hash_alg->name, hsize, real_hash); + params->hash_alg->name, hsize, + level == 0 ? real_dblock_hash : real_hblock_hash); error: for (; level > 0; level--) { kunmap_local(hblocks[level - 1].addr); put_page(hblocks[level - 1].page); } return false; } +struct fsverity_verification_context { + struct inode *inode; + struct fsverity_info *vi; + unsigned long max_ra_pages; + + /* + * pending_data and pending_pos are used when the selected hash + * algorithm supports multibuffer hashing. They're used to temporarily + * store the virtual address and position of a mapped data block that + * needs to be verified. If we then see another data block, we hash the + * two blocks simultaneously using the fast multibuffer hashing method. + */ + const void *pending_data; + u64 pending_pos; + + /* Buffers to temporarily store the calculated data block hashes */ + u8 hash1[FS_VERITY_MAX_DIGEST_SIZE]; + u8 hash2[FS_VERITY_MAX_DIGEST_SIZE]; +}; + +static inline void +fsverity_init_verification_context(struct fsverity_verification_context *ctx, + struct inode *inode, + unsigned long max_ra_pages) +{ + ctx->inode = inode; + ctx->vi = inode->i_verity_info; + ctx->max_ra_pages = max_ra_pages; + ctx->pending_data = NULL; +} + +static bool +fsverity_finish_verification(struct fsverity_verification_context *ctx) +{ + int err; + + if (ctx->pending_data == NULL) + return true; + /* + * Multibuffer hashing is enabled but there was an odd number of data + * blocks. Hash and verify the last block by itself. + */ + err = fsverity_hash_block(&ctx->vi->tree_params, ctx->inode, + ctx->pending_data, ctx->hash1); + kunmap_local(ctx->pending_data); + ctx->pending_data = NULL; + return err == 0 && + verify_data_block(ctx->inode, ctx->vi, ctx->hash1, + ctx->pending_pos, ctx->max_ra_pages); +} + +static inline void +fsverity_abort_verification(struct fsverity_verification_context *ctx) +{ + if (ctx->pending_data) { + kunmap_local(ctx->pending_data); + ctx->pending_data = NULL; + } +} + static bool -verify_data_blocks(struct folio *data_folio, size_t len, size_t offset, - unsigned long max_ra_pages) +fsverity_add_data_blocks(struct fsverity_verification_context *ctx, + struct folio *data_folio, size_t len, size_t offset) { - struct inode *inode = data_folio->mapping->host; - struct fsverity_info *vi = inode->i_verity_info; - const unsigned int block_size = vi->tree_params.block_size; - u64 pos = (u64)data_folio->index << PAGE_SHIFT; + struct inode *inode = ctx->inode; + struct fsverity_info *vi = ctx->vi; + const struct merkle_tree_params *params = &vi->tree_params; + const unsigned int block_size = params->block_size; + const bool use_finup2x = params->hash_alg->supports_finup2x; + u64 pos = ((u64)data_folio->index << PAGE_SHIFT) + offset; if (WARN_ON_ONCE(len <= 0 || !IS_ALIGNED(len | offset, block_size))) return false; if (WARN_ON_ONCE(!folio_test_locked(data_folio) || folio_test_uptodate(data_folio))) return false; do { - void *data; - bool valid; - - data = kmap_local_folio(data_folio, offset); - valid = verify_data_block(inode, vi, data, pos + offset, - max_ra_pages); - kunmap_local(data); - if (!valid) - return false; + const void *data = kmap_local_folio(data_folio, offset); + int err; + + if (use_finup2x) { + if (ctx->pending_data) { + /* Hash and verify two data blocks. */ + err = fsverity_hash_2_blocks(params, + inode, + ctx->pending_data, + data, + ctx->hash1, + ctx->hash2); + kunmap_local(ctx->pending_data); + kunmap_local(data); + ctx->pending_data = NULL; + if (err != 0 || + !verify_data_block(inode, vi, ctx->hash1, + ctx->pending_pos, + ctx->max_ra_pages) || + !verify_data_block(inode, vi, ctx->hash2, + pos, ctx->max_ra_pages)) + return false; + } else { + /* Wait and see if there's another block. */ + ctx->pending_data = data; + ctx->pending_pos = pos; + } + } else { + /* Hash and verify one data block. */ + err = fsverity_hash_block(params, inode, data, + ctx->hash1); + kunmap_local(data); + if (err != 0 || + !verify_data_block(inode, vi, ctx->hash1, + pos, ctx->max_ra_pages)) + return false; + } + pos += block_size; offset += block_size; len -= block_size; } while (len); return true; } @@ -284,11 +380,19 @@ verify_data_blocks(struct folio *data_folio, size_t len, size_t offset, * * Return: %true if the data is valid, else %false. */ bool fsverity_verify_blocks(struct folio *folio, size_t len, size_t offset) { - return verify_data_blocks(folio, len, offset, 0); + struct fsverity_verification_context ctx; + + fsverity_init_verification_context(&ctx, folio->mapping->host, 0); + + if (!fsverity_add_data_blocks(&ctx, folio, len, offset)) { + fsverity_abort_verification(&ctx); + return false; + } + return fsverity_finish_verification(&ctx); } EXPORT_SYMBOL_GPL(fsverity_verify_blocks); #ifdef CONFIG_BLOCK /** @@ -305,10 +409,12 @@ EXPORT_SYMBOL_GPL(fsverity_verify_blocks); * filesystems) must instead call fsverity_verify_page() directly on each page. * All filesystems must also call fsverity_verify_page() on holes. */ void fsverity_verify_bio(struct bio *bio) { + struct inode *inode = bio_first_folio_all(bio)->mapping->host; + struct fsverity_verification_context ctx; struct folio_iter fi; unsigned long max_ra_pages = 0; if (bio->bi_opf & REQ_RAHEAD) { /* @@ -321,17 +427,26 @@ void fsverity_verify_bio(struct bio *bio) * reduces the number of I/O requests made to the Merkle tree. */ max_ra_pages = bio->bi_iter.bi_size >> (PAGE_SHIFT + 2); } + fsverity_init_verification_context(&ctx, inode, max_ra_pages); + bio_for_each_folio_all(fi, bio) { - if (!verify_data_blocks(fi.folio, fi.length, fi.offset, - max_ra_pages)) { - bio->bi_status = BLK_STS_IOERR; - break; + if (!fsverity_add_data_blocks(&ctx, fi.folio, fi.length, + fi.offset)) { + fsverity_abort_verification(&ctx); + goto ioerr; } } + + if (!fsverity_finish_verification(&ctx)) + goto ioerr; + return; + +ioerr: + bio->bi_status = BLK_STS_IOERR; } EXPORT_SYMBOL_GPL(fsverity_verify_bio); #endif /* CONFIG_BLOCK */ /** From patchwork Mon Apr 15 21:37:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630759 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id E47A7C00A94 for ; Mon, 15 Apr 2024 21:39:29 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=Q+Lna6xcPXFuv2SQ/IArEuMqrx+sIyqNKQxJo/XkeIo=; b=rrfBzt23bj0zw3 nzM+feVQC95+avaxzpRK8v1ZLK0NFTVwwSV5ExujQpokShmmCbyYB26a8lOOp3JUWEChTUdfFfIQl PssZVSoAYWNMFnXonxjQ+DBPg0lt0C0VPH0w4MbzqKzmD+kmrezQFm/JewAJd3zms/P9++s0qy6cV xxArBIh4GBRBmtFcrfwiql25KQeSR+9/+4G0zFvkkC3JJEEdlXNXAar+F/WO7oUvzMMZuSx4MTtGR tl0btaCGqvXpYAZjEAtRmgTc/RUd2l6ULCeGq04jtp4jfBK36x2etyYTeDaiFTvA+eGA5CWJXc+30 F12gtzh1qn8s2GanvvVw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2g-00000009zFQ-3W7d; Mon, 15 Apr 2024 21:39:10 +0000 Received: from dfw.source.kernel.org ([2604:1380:4641:c500::1]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2O-00000009z3S-0rk6 for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:38:59 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 9676E60ED0; Mon, 15 Apr 2024 21:38:51 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 26F60C113CC; Mon, 15 Apr 2024 21:38:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217131; bh=Lmr7ntSF7F2Uq9SDrut1jIQ5oTs6nnvHinkQVqQx9/4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=lJUtoVdNghIWs3U2FYutWsvpr4y0DVGwUt/XRPy3TOowyBDiy+9ikK6UYn/w8jJXY w8rSTbsDCfxWgaR5N69mjfjtiiNtqgoPrvmXOOhC7LU2zl0A0c1lAu3474eG0qN5El 9+kHhVPo0GBLzn2NlK7CFE8Znm05f/TcNzslObN88neHjfnRFY6C2GzIxBgm9srd9U tkmuv00fcThtGWxrOvPVNroySPcJCMnM3z/GuJHAwgJmAHXxAUICcTzD2f5aVEs/Rr o6iM5FFcbPeIKKixLKjJRRK5dQdz9V5H0IoNmO2TRQ7u8WrlOrETsC5IBqddxT9Qo0 HGm5lnV9JGwHQ== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 7/8] dm-verity: hash blocks with shash import+finup when possible Date: Mon, 15 Apr 2024 14:37:18 -0700 Message-ID: <20240415213719.120673-8-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143852_838362_4130C75B X-CRM114-Status: GOOD ( 32.34 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers Currently dm-verity computes the hash of each block by using multiple calls to the "ahash" crypto API. While the exact sequence depends on the chosen dm-verity settings, in the vast majority of cases it is: 1. crypto_ahash_init() 2. crypto_ahash_update() [salt] 3. crypto_ahash_update() [data] 4. crypto_ahash_final() This is inefficient for two main reasons: - It makes multiple indirect calls, which is expensive on modern CPUs especially when mitigations for CPU vulnerabilities are enabled. Since the salt is the same across all blocks on a given dm-verity device, a much more efficient sequence would be to do an import of the pre-salted state, then a finup. - It uses the ahash (asynchronous hash) API, despite the fact that CPU-based hashing is almost always used in practice, and therefore it experiences the overhead of the ahash-based wrapper for shash. This also means that the new function crypto_shash_finup2x(), which is specifically designed for fast CPU-based hashing, is unavailable. Since dm-verity was intentionally converted to ahash to support off-CPU crypto accelerators, wholesale conversion to shash (reverting that change) might not be acceptable. Yet, we should still provide a fast path for shash with the most common dm-verity settings. Therefore, this patch adds a new shash import+finup based fast path to dm-verity. It is used automatically when appropriate, i.e. when the ahash API and shash APIs resolve to the same underlying algorithm, the dm-verity version is not 0 (so that the salt is hashed before the data), and the data block size is not greater than the page size. This makes dm-verity optimized for what the vast majority of users want: CPU-based hashing with the most common settings, while still retaining support for rarer settings and off-CPU crypto accelerators. In benchmarks with veritysetup's default parameters (SHA-256, 4K data and hash block sizes, 32-byte salt), which also match the parameters that Android currently uses, this patch improves block hashing performance by about 15% on an x86_64 system that supports the SHA-NI instructions, or by about 5% on an arm64 system that supports the ARMv8 SHA2 instructions. This was with CONFIG_CRYPTO_STATS disabled; an even larger improvement can be expected if that option is enabled. Note that another benefit of using "import" to handle the salt is that if the salt size is equal to the input size of the hash algorithm's compression function, e.g. 64 bytes for SHA-256, then the performance is exactly the same as no salt. (This doesn't seem to be much better than veritysetup's current default of 32-byte salts, due to the way SHA-256's finalization padding works, but it should be marginally better.) In addition to the benchmarks mentioned above, I've tested this patch with cryptsetup's 'verity-compat-test' script. I've also lightly tested this patch with Android, where the new shash-based code gets used. Signed-off-by: Eric Biggers --- drivers/md/dm-verity-fec.c | 13 +- drivers/md/dm-verity-target.c | 336 ++++++++++++++++++++++++---------- drivers/md/dm-verity.h | 27 ++- 3 files changed, 263 insertions(+), 113 deletions(-) diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c index e46aee6f932ee..b436b8e4d7507 100644 --- a/drivers/md/dm-verity-fec.c +++ b/drivers/md/dm-verity-fec.c @@ -184,13 +184,14 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_io *io, * Locate data block erasures using verity hashes. */ static int fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io, u8 *want_digest, u8 *data) { - if (unlikely(verity_hash(v, verity_io_hash_req(v, io), - data, 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), true))) + if (unlikely(verity_compute_hash_virt(v, io, data, + 1 << v->data_dev_block_bits, + verity_io_real_digest(v, io), + true))) return 0; return memcmp(verity_io_real_digest(v, io), want_digest, v->digest_size) != 0; } @@ -386,13 +387,13 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io, pos += fio->nbufs << DM_VERITY_FEC_BUF_RS_BITS; } /* Always re-validate the corrected block against the expected hash */ - r = verity_hash(v, verity_io_hash_req(v, io), fio->output, - 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), true); + r = verity_compute_hash_virt(v, io, fio->output, + 1 << v->data_dev_block_bits, + verity_io_real_digest(v, io), true); if (unlikely(r < 0)) return r; if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io), v->digest_size)) { diff --git a/drivers/md/dm-verity-target.c b/drivers/md/dm-verity-target.c index bb5da66da4c17..2dd15f5e91b7d 100644 --- a/drivers/md/dm-verity-target.c +++ b/drivers/md/dm-verity-target.c @@ -44,12 +44,16 @@ static unsigned int dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE; module_param_named(prefetch_cluster, dm_verity_prefetch_cluster, uint, 0644); +/* Is at least one dm-verity instance using the bh workqueue? */ static DEFINE_STATIC_KEY_FALSE(use_bh_wq_enabled); +/* Is at least one dm-verity instance using ahash_tfm instead of shash_tfm? */ +static DEFINE_STATIC_KEY_FALSE(ahash_enabled); + struct dm_verity_prefetch_work { struct work_struct work; struct dm_verity *v; unsigned short ioprio; sector_t block; @@ -100,13 +104,13 @@ static sector_t verity_position_at_level(struct dm_verity *v, sector_t block, int level) { return block >> (level * v->hash_per_block_bits); } -static int verity_hash_update(struct dm_verity *v, struct ahash_request *req, - const u8 *data, size_t len, - struct crypto_wait *wait) +static int verity_ahash_update(struct dm_verity *v, struct ahash_request *req, + const u8 *data, size_t len, + struct crypto_wait *wait) { struct scatterlist sg; if (likely(!is_vmalloc_addr(data))) { sg_init_one(&sg, data, len); @@ -133,16 +137,16 @@ static int verity_hash_update(struct dm_verity *v, struct ahash_request *req, } /* * Wrapper for crypto_ahash_init, which handles verity salting. */ -static int verity_hash_init(struct dm_verity *v, struct ahash_request *req, +static int verity_ahash_init(struct dm_verity *v, struct ahash_request *req, struct crypto_wait *wait, bool may_sleep) { int r; - ahash_request_set_tfm(req, v->tfm); + ahash_request_set_tfm(req, v->ahash_tfm); ahash_request_set_callback(req, may_sleep ? CRYPTO_TFM_REQ_MAY_SLEEP | CRYPTO_TFM_REQ_MAY_BACKLOG : 0, crypto_req_done, (void *)wait); crypto_init_wait(wait); @@ -153,22 +157,22 @@ static int verity_hash_init(struct dm_verity *v, struct ahash_request *req, DMERR("crypto_ahash_init failed: %d", r); return r; } if (likely(v->salt_size && (v->version >= 1))) - r = verity_hash_update(v, req, v->salt, v->salt_size, wait); + r = verity_ahash_update(v, req, v->salt, v->salt_size, wait); return r; } -static int verity_hash_final(struct dm_verity *v, struct ahash_request *req, - u8 *digest, struct crypto_wait *wait) +static int verity_ahash_final(struct dm_verity *v, struct ahash_request *req, + u8 *digest, struct crypto_wait *wait) { int r; if (unlikely(v->salt_size && (!v->version))) { - r = verity_hash_update(v, req, v->salt, v->salt_size, wait); + r = verity_ahash_update(v, req, v->salt, v->salt_size, wait); if (r < 0) { DMERR("%s failed updating salt: %d", __func__, r); goto out; } @@ -178,27 +182,47 @@ static int verity_hash_final(struct dm_verity *v, struct ahash_request *req, r = crypto_wait_req(crypto_ahash_final(req), wait); out: return r; } -int verity_hash(struct dm_verity *v, struct ahash_request *req, - const u8 *data, size_t len, u8 *digest, bool may_sleep) +int verity_compute_hash_virt(struct dm_verity *v, struct dm_verity_io *io, + const u8 *data, size_t len, u8 *digest, + bool may_sleep) { int r; - struct crypto_wait wait; - r = verity_hash_init(v, req, &wait, may_sleep); - if (unlikely(r < 0)) - goto out; + if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) { + struct ahash_request *req = verity_io_hash_req(v, io); + struct crypto_wait wait; - r = verity_hash_update(v, req, data, len, &wait); - if (unlikely(r < 0)) - goto out; + r = verity_ahash_init(v, req, &wait, may_sleep); + if (unlikely(r)) + goto error; - r = verity_hash_final(v, req, digest, &wait); + r = verity_ahash_update(v, req, data, len, &wait); + if (unlikely(r)) + goto error; -out: + r = verity_ahash_final(v, req, digest, &wait); + if (unlikely(r)) + goto error; + } else { + struct shash_desc *desc = verity_io_hash_req(v, io); + + desc->tfm = v->shash_tfm; + r = crypto_shash_import(desc, v->initial_hashstate); + if (unlikely(r)) + goto error; + + r = crypto_shash_finup(desc, data, len, digest); + if (unlikely(r)) + goto error; + } + return 0; + +error: + DMERR("Error hashing block from virt buffer: %d", r); return r; } static void verity_hash_at_level(struct dm_verity *v, sector_t block, int level, sector_t *hash_block, unsigned int *offset) @@ -323,13 +347,14 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io, if (skip_unverified) { r = 1; goto release_ret_r; } - r = verity_hash(v, verity_io_hash_req(v, io), - data, 1 << v->hash_dev_block_bits, - verity_io_real_digest(v, io), !io->in_bh); + r = verity_compute_hash_virt(v, io, data, + 1 << v->hash_dev_block_bits, + verity_io_real_digest(v, io), + !io->in_bh); if (unlikely(r < 0)) goto release_ret_r; if (likely(memcmp(verity_io_real_digest(v, io), want_digest, v->digest_size) == 0)) @@ -403,14 +428,17 @@ int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io, return r; } /* - * Calculates the digest for the given bio + * Update the ahash_request of @io with the next data block from @iter, and + * advance @iter accordingly. */ -static int verity_for_io_block(struct dm_verity *v, struct dm_verity_io *io, - struct bvec_iter *iter, struct crypto_wait *wait) +static int verity_ahash_update_block(struct dm_verity *v, + struct dm_verity_io *io, + struct bvec_iter *iter, + struct crypto_wait *wait) { unsigned int todo = 1 << v->data_dev_block_bits; struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); struct scatterlist sg; struct ahash_request *req = verity_io_hash_req(v, io); @@ -445,10 +473,71 @@ static int verity_for_io_block(struct dm_verity *v, struct dm_verity_io *io, } while (todo); return 0; } +static int verity_compute_hash(struct dm_verity *v, struct dm_verity_io *io, + struct bvec_iter *iter, u8 *digest, + bool may_sleep) +{ + int r; + + if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) { + struct ahash_request *req = verity_io_hash_req(v, io); + struct crypto_wait wait; + + r = verity_ahash_init(v, req, &wait, may_sleep); + if (unlikely(r)) + goto error; + + r = verity_ahash_update_block(v, io, iter, &wait); + if (unlikely(r)) + goto error; + + r = verity_ahash_final(v, req, digest, &wait); + if (unlikely(r)) + goto error; + } else { + struct shash_desc *desc = verity_io_hash_req(v, io); + struct bio *bio = + dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); + struct bio_vec bv = bio_iter_iovec(bio, *iter); + const unsigned int len = 1 << v->data_dev_block_bits; + const void *virt; + + if (unlikely(len > bv.bv_len)) { + /* + * Data block spans pages. This should not happen, + * since this code path is not used if the data block + * size is greater than the page size, and all I/O + * should be data block aligned because dm-verity sets + * logical_block_size to the data block size. + */ + DMERR_LIMIT("unaligned io (data block spans pages)"); + return -EIO; + } + + desc->tfm = v->shash_tfm; + r = crypto_shash_import(desc, v->initial_hashstate); + if (unlikely(r)) + goto error; + + virt = bvec_kmap_local(&bv); + r = crypto_shash_finup(desc, virt, len, digest); + kunmap_local(virt); + if (unlikely(r)) + goto error; + + bio_advance_iter(bio, iter, len); + } + return 0; + +error: + DMERR("Error hashing block from bio iter: %d", r); + return r; +} + /* * Calls function process for 1 << v->data_dev_block_bits bytes in the bio_vec * starting from iter. */ int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io, @@ -516,13 +605,12 @@ static noinline int verity_recheck(struct dm_verity *v, struct dm_verity_io *io, io_loc.count = 1 << (v->data_dev_block_bits - SECTOR_SHIFT); r = dm_io(&io_req, 1, &io_loc, NULL, IOPRIO_DEFAULT); if (unlikely(r)) goto free_ret; - r = verity_hash(v, verity_io_hash_req(v, io), buffer, - 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), true); + r = verity_compute_hash_virt(v, io, buffer, 1 << v->data_dev_block_bits, + verity_io_real_digest(v, io), true); if (unlikely(r)) goto free_ret; if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io), v->digest_size)) { @@ -569,11 +657,10 @@ static int verity_verify_io(struct dm_verity_io *io) bool is_zero; struct dm_verity *v = io->v; struct bvec_iter start; struct bvec_iter iter_copy; struct bvec_iter *iter; - struct crypto_wait wait; struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); unsigned int b; if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { /* @@ -586,11 +673,10 @@ static int verity_verify_io(struct dm_verity_io *io) iter = &io->iter; for (b = 0; b < io->n_blocks; b++) { int r; sector_t cur_block = io->block + b; - struct ahash_request *req = verity_io_hash_req(v, io); if (v->validated_blocks && bio->bi_status == BLK_STS_OK && likely(test_bit(cur_block, v->validated_blocks))) { verity_bv_skip_block(v, io, iter); continue; @@ -613,21 +699,14 @@ static int verity_verify_io(struct dm_verity_io *io) return r; continue; } - r = verity_hash_init(v, req, &wait, !io->in_bh); - if (unlikely(r < 0)) - return r; - start = *iter; - r = verity_for_io_block(v, io, iter, &wait); - if (unlikely(r < 0)) - return r; - - r = verity_hash_final(v, req, verity_io_real_digest(v, io), - &wait); + r = verity_compute_hash(v, io, iter, + verity_io_real_digest(v, io), + !io->in_bh); if (unlikely(r < 0)) return r; if (likely(memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io), v->digest_size) == 0)) { @@ -1031,15 +1110,20 @@ static void verity_dtr(struct dm_target *ti) if (v->bufio) dm_bufio_client_destroy(v->bufio); kvfree(v->validated_blocks); kfree(v->salt); + kfree(v->initial_hashstate); kfree(v->root_digest); kfree(v->zero_digest); - if (v->tfm) - crypto_free_ahash(v->tfm); + if (v->ahash_tfm) { + static_branch_dec(&ahash_enabled); + crypto_free_ahash(v->ahash_tfm); + } else { + crypto_free_shash(v->shash_tfm); + } kfree(v->alg_name); if (v->hash_dev) dm_put_device(ti, v->hash_dev); @@ -1081,33 +1165,33 @@ static int verity_alloc_most_once(struct dm_verity *v) } static int verity_alloc_zero_digest(struct dm_verity *v) { int r = -ENOMEM; - struct ahash_request *req; + struct dm_verity_io *io; u8 *zero_data; v->zero_digest = kmalloc(v->digest_size, GFP_KERNEL); if (!v->zero_digest) return r; - req = kmalloc(v->ahash_reqsize, GFP_KERNEL); + io = kmalloc(sizeof(*io) + v->hash_reqsize, GFP_KERNEL); - if (!req) + if (!io) return r; /* verity_dtr will free zero_digest */ zero_data = kzalloc(1 << v->data_dev_block_bits, GFP_KERNEL); if (!zero_data) goto out; - r = verity_hash(v, req, zero_data, 1 << v->data_dev_block_bits, - v->zero_digest, true); - + r = verity_compute_hash_virt(v, io, zero_data, + 1 << v->data_dev_block_bits, + v->zero_digest, true); out: - kfree(req); + kfree(io); kfree(zero_data); return r; } @@ -1224,10 +1308,109 @@ static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v, } while (argc && !r); return r; } +static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name) +{ + struct dm_target *ti = v->ti; + struct crypto_ahash *ahash; + struct crypto_shash *shash = NULL; + const char *driver_name; + + v->alg_name = kstrdup(alg_name, GFP_KERNEL); + if (!v->alg_name) { + ti->error = "Cannot allocate algorithm name"; + return -ENOMEM; + } + + ahash = crypto_alloc_ahash(alg_name, 0, + v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0); + if (IS_ERR(ahash)) { + ti->error = "Cannot initialize hash function"; + return PTR_ERR(ahash); + } + driver_name = crypto_ahash_driver_name(ahash); + if (v->version >= 1 /* salt prepended, not appended? */ && + 1 << v->data_dev_block_bits <= PAGE_SIZE) { + shash = crypto_alloc_shash(alg_name, 0, 0); + if (!IS_ERR(shash) && + strcmp(crypto_shash_driver_name(shash), driver_name) != 0) { + /* + * ahash gave a different driver than shash, so probably + * this is a case of real hardware offload. Use ahash. + */ + crypto_free_shash(shash); + shash = NULL; + } + } + if (!IS_ERR_OR_NULL(shash)) { + crypto_free_ahash(ahash); + ahash = NULL; + v->shash_tfm = shash; + v->digest_size = crypto_shash_digestsize(shash); + v->hash_reqsize = sizeof(struct shash_desc) + + crypto_shash_descsize(shash); + DMINFO("%s using shash \"%s\"", alg_name, driver_name); + } else { + v->ahash_tfm = ahash; + static_branch_inc(&ahash_enabled); + v->digest_size = crypto_ahash_digestsize(ahash); + v->hash_reqsize = sizeof(struct ahash_request) + + crypto_ahash_reqsize(ahash); + DMINFO("%s using ahash \"%s\"", alg_name, driver_name); + } + if ((1 << v->hash_dev_block_bits) < v->digest_size * 2) { + ti->error = "Digest size too big"; + return -EINVAL; + } + return 0; +} + +static int verity_setup_salt_and_hashstate(struct dm_verity *v, const char *arg) +{ + struct dm_target *ti = v->ti; + + if (strcmp(arg, "-") != 0) { + v->salt_size = strlen(arg) / 2; + v->salt = kmalloc(v->salt_size, GFP_KERNEL); + if (!v->salt) { + ti->error = "Cannot allocate salt"; + return -ENOMEM; + } + if (strlen(arg) != v->salt_size * 2 || + hex2bin(v->salt, arg, v->salt_size)) { + ti->error = "Invalid salt"; + return -EINVAL; + } + } + /* + * If the "shash with import+finup sequence" method has been selected + * (see verity_setup_hash_alg()), then create the initial hash state. + */ + if (v->shash_tfm) { + SHASH_DESC_ON_STACK(desc, v->shash_tfm); + int r; + + v->initial_hashstate = kmalloc( + crypto_shash_statesize(v->shash_tfm), GFP_KERNEL); + if (!v->initial_hashstate) { + ti->error = "Cannot allocate initial hash state"; + return -ENOMEM; + } + desc->tfm = v->shash_tfm; + r = crypto_shash_init(desc) ?: + crypto_shash_update(desc, v->salt, v->salt_size) ?: + crypto_shash_export(desc, v->initial_hashstate); + if (r) { + ti->error = "Cannot set up initial hash state"; + return r; + } + } + return 0; +} + /* * Target parameters: * The current format is version 1. * Vsn 0 is compatible with original Chromium OS releases. * @@ -1348,42 +1531,13 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv) r = -EINVAL; goto bad; } v->hash_start = num_ll; - v->alg_name = kstrdup(argv[7], GFP_KERNEL); - if (!v->alg_name) { - ti->error = "Cannot allocate algorithm name"; - r = -ENOMEM; - goto bad; - } - - v->tfm = crypto_alloc_ahash(v->alg_name, 0, - v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0); - if (IS_ERR(v->tfm)) { - ti->error = "Cannot initialize hash function"; - r = PTR_ERR(v->tfm); - v->tfm = NULL; - goto bad; - } - - /* - * dm-verity performance can vary greatly depending on which hash - * algorithm implementation is used. Help people debug performance - * problems by logging the ->cra_driver_name. - */ - DMINFO("%s using implementation \"%s\"", v->alg_name, - crypto_hash_alg_common(v->tfm)->base.cra_driver_name); - - v->digest_size = crypto_ahash_digestsize(v->tfm); - if ((1 << v->hash_dev_block_bits) < v->digest_size * 2) { - ti->error = "Digest size too big"; - r = -EINVAL; + r = verity_setup_hash_alg(v, argv[7]); + if (r) goto bad; - } - v->ahash_reqsize = sizeof(struct ahash_request) + - crypto_ahash_reqsize(v->tfm); v->root_digest = kmalloc(v->digest_size, GFP_KERNEL); if (!v->root_digest) { ti->error = "Cannot allocate root digest"; r = -ENOMEM; @@ -1395,25 +1549,13 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv) r = -EINVAL; goto bad; } root_hash_digest_to_validate = argv[8]; - if (strcmp(argv[9], "-")) { - v->salt_size = strlen(argv[9]) / 2; - v->salt = kmalloc(v->salt_size, GFP_KERNEL); - if (!v->salt) { - ti->error = "Cannot allocate salt"; - r = -ENOMEM; - goto bad; - } - if (strlen(argv[9]) != v->salt_size * 2 || - hex2bin(v->salt, argv[9], v->salt_size)) { - ti->error = "Invalid salt"; - r = -EINVAL; - goto bad; - } - } + r = verity_setup_salt_and_hashstate(v, argv[9]); + if (r) + goto bad; argv += 10; argc -= 10; /* Optional parameters */ @@ -1512,11 +1654,11 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv) r = -ENOMEM; goto bad; } ti->per_io_data_size = sizeof(struct dm_verity_io) + - v->ahash_reqsize + v->digest_size * 2; + v->hash_reqsize + v->digest_size * 2; r = verity_fec_ctr(v); if (r) goto bad; diff --git a/drivers/md/dm-verity.h b/drivers/md/dm-verity.h index 20b1bcf034742..15ffb0881cc9c 100644 --- a/drivers/md/dm-verity.h +++ b/drivers/md/dm-verity.h @@ -37,13 +37,15 @@ struct dm_verity { struct dm_dev *data_dev; struct dm_dev *hash_dev; struct dm_target *ti; struct dm_bufio_client *bufio; char *alg_name; - struct crypto_ahash *tfm; + struct crypto_ahash *ahash_tfm; /* either this or shash_tfm is set */ + struct crypto_shash *shash_tfm; /* either this or ahash_tfm is set */ u8 *root_digest; /* digest of the root block */ u8 *salt; /* salt: its size is salt_size */ + u8 *initial_hashstate; /* salted initial state, if shash_tfm is set */ u8 *zero_digest; /* digest for a zero block */ unsigned int salt_size; sector_t data_start; /* data offset in 512-byte sectors */ sector_t hash_start; /* hash start in blocks */ sector_t data_blocks; /* the number of data blocks */ @@ -54,11 +56,11 @@ struct dm_verity { unsigned char levels; /* the number of tree levels */ unsigned char version; bool hash_failed:1; /* set if hash of any block failed */ bool use_bh_wq:1; /* try to verify in BH wq before normal work-queue */ unsigned int digest_size; /* digest size for the current hash algorithm */ - unsigned int ahash_reqsize;/* the size of temporary space for crypto */ + unsigned int hash_reqsize; /* the size of temporary space for crypto */ enum verity_mode mode; /* mode for handling verification errors */ unsigned int corrupted_errs;/* Number of errors for corrupted blocks */ struct workqueue_struct *verify_wq; @@ -92,45 +94,50 @@ struct dm_verity_io { char *recheck_buffer; /* * Three variably-size fields follow this struct: * - * u8 hash_req[v->ahash_reqsize]; + * u8 hash_req[v->hash_reqsize]; * u8 real_digest[v->digest_size]; * u8 want_digest[v->digest_size]; * * To access them use: verity_io_hash_req(), verity_io_real_digest() * and verity_io_want_digest(). + * + * hash_req is either a struct ahash_request or a struct shash_desc, + * depending on whether ahash_tfm or shash_tfm is being used. */ }; -static inline struct ahash_request *verity_io_hash_req(struct dm_verity *v, - struct dm_verity_io *io) +static inline void *verity_io_hash_req(struct dm_verity *v, + struct dm_verity_io *io) { - return (struct ahash_request *)(io + 1); + return io + 1; } static inline u8 *verity_io_real_digest(struct dm_verity *v, struct dm_verity_io *io) { - return (u8 *)(io + 1) + v->ahash_reqsize; + return (u8 *)(io + 1) + v->hash_reqsize; } static inline u8 *verity_io_want_digest(struct dm_verity *v, struct dm_verity_io *io) { - return (u8 *)(io + 1) + v->ahash_reqsize + v->digest_size; + return (u8 *)(io + 1) + v->hash_reqsize + v->digest_size; } extern int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io, struct bvec_iter *iter, int (*process)(struct dm_verity *v, struct dm_verity_io *io, u8 *data, size_t len)); -extern int verity_hash(struct dm_verity *v, struct ahash_request *req, - const u8 *data, size_t len, u8 *digest, bool may_sleep); +extern int verity_compute_hash_virt(struct dm_verity *v, + struct dm_verity_io *io, + const u8 *data, size_t len, u8 *digest, + bool may_sleep); extern int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io, sector_t block, u8 *digest, bool *is_zero); extern bool dm_is_verity_target(struct dm_target *ti); From patchwork Mon Apr 15 21:37:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13630758 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org 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 smtp.lore.kernel.org (Postfix) with ESMTPS id 5419EC4345F for ; Mon, 15 Apr 2024 21:39:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=7ZH763vTvK/s5MUTFaXPMAELc8wQXJOiz1Ar9uKXTtI=; b=rIHi2YbZuixD0u qbJXjoh4yeCXdvvHO1BTHcUK9UamuNzwY4C5Z2rV8KG6yR6cV75DaaIRBpoU5PCo1tCzCHGoHJAsk lsjCZcXIrcgz9Q4olBgcvwW/HcdpcVEO5Vg/IJBTw7vqzejFyORt70XtJ8YEZvouwmnJP0MnwO6mw dHgtgDbYC68B0iI1OQTqNQaYvtVQFomPczgo5AStXZI0mUujXIB/LqqPhaa4XNCyZ9l4IkUu42YN5 l6ZmiF2PHPCYiJFG0PTZkreHrWPWWF1Bt3zu3lAV8oeGlGpMMUjA8sOG/jG6PvXw5XZjzl/p0f97e T/qjUv+PZUJZ/6O3pdVg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2j-00000009zHe-0I38; Mon, 15 Apr 2024 21:39:13 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.97.1 #2 (Red Hat Linux)) id 1rwU2O-00000009z43-2wlP for linux-arm-kernel@lists.infradead.org; Mon, 15 Apr 2024 21:39:00 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 059B860EDE; Mon, 15 Apr 2024 21:38:52 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 905A8C32786; Mon, 15 Apr 2024 21:38:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713217131; bh=C/bgfHpsk+AudDdgUGcfi+WqhetOO/CnkHcMGsCaAPc=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=DmzkFFvfJoUXyUDLSqFTUcLiKTXfyS4ZP6Rgs0VaQ5GW2dT9JgvjlIIPqD5NyPSEX l8xsRI2vKuYCSKJis2OdPV2BqxV6b83/PzU9efpJ5gCgxR3aDw/ZOaa17YIQsjBlBF wYge7eRVUIKzOHzf1YPA7P5ROXA4dXtq+1kWZK/65Uzj2v1UWfgUb27ysAqlkin9vs LcWrTVF1m3LaKK4rmelXyiWtPxW1ZZCvII7GvqgoWycdckFVu+YnZX1tsiUaGbp4qi dZnfDQ5rnVDFe0Yk6gKCd61Azk1YmZ26ajS1QyudLS8lfp2o3bzXC1vkDV7NxXiNkP +HZl7mmn8wUcg== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [RFC PATCH 8/8] dm-verity: improve performance by using multibuffer hashing Date: Mon, 15 Apr 2024 14:37:19 -0700 Message-ID: <20240415213719.120673-9-ebiggers@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240415213719.120673-1-ebiggers@kernel.org> References: <20240415213719.120673-1-ebiggers@kernel.org> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240415_143853_158878_E2827F87 X-CRM114-Status: GOOD ( 31.32 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Eric Biggers When supported by the hash algorithm, use crypto_shash_finup2x() to interleave the hashing of pairs of data blocks. On some CPUs this nearly doubles hashing performance. The increase in overall throughput of cold-cache dm-verity reads that I'm seeing on arm64 and x86_64 is roughly 35% (though this metric is hard to measure as it jumps around a lot). For now this is only done on data blocks, not Merkle tree blocks. We could use finup2x on Merkle tree blocks too, but that is less important as there aren't as many Merkle tree blocks as data blocks, and that would require some additional code restructuring. Signed-off-by: Eric Biggers --- drivers/md/dm-verity-fec.c | 24 +-- drivers/md/dm-verity-fec.h | 7 +- drivers/md/dm-verity-target.c | 360 ++++++++++++++++++++++------------ drivers/md/dm-verity.h | 28 +-- 4 files changed, 261 insertions(+), 158 deletions(-) diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c index b436b8e4d7507..c1677137a6829 100644 --- a/drivers/md/dm-verity-fec.c +++ b/drivers/md/dm-verity-fec.c @@ -184,18 +184,18 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_io *io, * Locate data block erasures using verity hashes. */ static int fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io, u8 *want_digest, u8 *data) { + u8 real_digest[HASH_MAX_DIGESTSIZE]; + if (unlikely(verity_compute_hash_virt(v, io, data, 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), - true))) + real_digest, true))) return 0; - return memcmp(verity_io_real_digest(v, io), want_digest, - v->digest_size) != 0; + return memcmp(real_digest, want_digest, v->digest_size) != 0; } /* * Read data blocks that are part of the RS block and deinterleave as much as * fits into buffers. Check for erasure locations if @neras is non-NULL. @@ -362,14 +362,15 @@ static void fec_init_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio) * (indicated by @offset) in fio->output. If @use_erasures is non-zero, uses * hashes to locate erasures. */ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io, struct dm_verity_fec_io *fio, u64 rsb, u64 offset, - bool use_erasures) + const u8 *want_digest, bool use_erasures) { int r, neras = 0; unsigned int pos; + u8 real_digest[HASH_MAX_DIGESTSIZE]; r = fec_alloc_bufs(v, fio); if (unlikely(r < 0)) return r; @@ -389,16 +390,15 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io, } /* Always re-validate the corrected block against the expected hash */ r = verity_compute_hash_virt(v, io, fio->output, 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), true); + real_digest, true); if (unlikely(r < 0)) return r; - if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io), - v->digest_size)) { + if (memcmp(real_digest, want_digest, v->digest_size)) { DMERR_LIMIT("%s: FEC %llu: failed to correct (%d erasures)", v->data_dev->name, (unsigned long long)rsb, neras); return -EILSEQ; } @@ -419,12 +419,12 @@ static int fec_bv_copy(struct dm_verity *v, struct dm_verity_io *io, u8 *data, /* * Correct errors in a block. Copies corrected block to dest if non-NULL, * otherwise to a bio_vec starting from iter. */ int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io, - enum verity_block_type type, sector_t block, u8 *dest, - struct bvec_iter *iter) + enum verity_block_type type, sector_t block, + const u8 *want_digest, u8 *dest, struct bvec_iter *iter) { int r; struct dm_verity_fec_io *fio = fec_io(io); u64 offset, res, rsb; @@ -463,13 +463,13 @@ int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io, /* * Locating erasures is slow, so attempt to recover the block without * them first. Do a second attempt with erasures if the corruption is * bad enough. */ - r = fec_decode_rsb(v, io, fio, rsb, offset, false); + r = fec_decode_rsb(v, io, fio, rsb, offset, want_digest, false); if (r < 0) { - r = fec_decode_rsb(v, io, fio, rsb, offset, true); + r = fec_decode_rsb(v, io, fio, rsb, offset, want_digest, true); if (r < 0) goto done; } if (dest) diff --git a/drivers/md/dm-verity-fec.h b/drivers/md/dm-verity-fec.h index 8454070d28242..57c3f674cae93 100644 --- a/drivers/md/dm-verity-fec.h +++ b/drivers/md/dm-verity-fec.h @@ -68,11 +68,12 @@ struct dm_verity_fec_io { extern bool verity_fec_is_enabled(struct dm_verity *v); extern int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io, enum verity_block_type type, sector_t block, - u8 *dest, struct bvec_iter *iter); + const u8 *want_digest, u8 *dest, + struct bvec_iter *iter); extern unsigned int verity_fec_status_table(struct dm_verity *v, unsigned int sz, char *result, unsigned int maxlen); extern void verity_fec_finish_io(struct dm_verity_io *io); @@ -97,12 +98,12 @@ static inline bool verity_fec_is_enabled(struct dm_verity *v) return false; } static inline int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io, - enum verity_block_type type, - sector_t block, u8 *dest, + enum verity_block_type type, sector_t block, + const u8 *want_digest, u8 *dest, struct bvec_iter *iter) { return -EOPNOTSUPP; } diff --git a/drivers/md/dm-verity-target.c b/drivers/md/dm-verity-target.c index 2dd15f5e91b7d..3dd127c23de29 100644 --- a/drivers/md/dm-verity-target.c +++ b/drivers/md/dm-verity-target.c @@ -300,16 +300,16 @@ static int verity_handle_err(struct dm_verity *v, enum verity_block_type type, /* * Verify hash of a metadata block pertaining to the specified data block * ("block" argument) at a specified level ("level" argument). * - * On successful return, verity_io_want_digest(v, io) contains the hash value - * for a lower tree level or for the data block (if we're at the lowest level). + * On successful return, want_digest contains the hash value for a lower tree + * level or for the data block (if we're at the lowest level). * * If "skip_unverified" is true, unverified buffer is skipped and 1 is returned. * If "skip_unverified" is false, unverified buffer is hashed and verified - * against current value of verity_io_want_digest(v, io). + * against current value of want_digest. */ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io, sector_t block, int level, bool skip_unverified, u8 *want_digest) { @@ -318,10 +318,11 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io, u8 *data; int r; sector_t hash_block; unsigned int offset; struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); + u8 real_digest[HASH_MAX_DIGESTSIZE]; verity_hash_at_level(v, block, level, &hash_block, &offset); if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { data = dm_bufio_get(v->bufio, hash_block, &buf); @@ -349,27 +350,26 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io, goto release_ret_r; } r = verity_compute_hash_virt(v, io, data, 1 << v->hash_dev_block_bits, - verity_io_real_digest(v, io), - !io->in_bh); + real_digest, !io->in_bh); if (unlikely(r < 0)) goto release_ret_r; - if (likely(memcmp(verity_io_real_digest(v, io), want_digest, - v->digest_size) == 0)) + if (likely(!memcmp(real_digest, want_digest, v->digest_size))) aux->hash_verified = 1; else if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { /* * Error handling code (FEC included) cannot be run in a * tasklet since it may sleep, so fallback to work-queue. */ r = -EAGAIN; goto release_ret_r; } else if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_METADATA, - hash_block, data, NULL) == 0) + hash_block, want_digest, + data, NULL) == 0) aux->hash_verified = 1; else if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_METADATA, hash_block)) { struct bio *bio = @@ -473,71 +473,10 @@ static int verity_ahash_update_block(struct dm_verity *v, } while (todo); return 0; } -static int verity_compute_hash(struct dm_verity *v, struct dm_verity_io *io, - struct bvec_iter *iter, u8 *digest, - bool may_sleep) -{ - int r; - - if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) { - struct ahash_request *req = verity_io_hash_req(v, io); - struct crypto_wait wait; - - r = verity_ahash_init(v, req, &wait, may_sleep); - if (unlikely(r)) - goto error; - - r = verity_ahash_update_block(v, io, iter, &wait); - if (unlikely(r)) - goto error; - - r = verity_ahash_final(v, req, digest, &wait); - if (unlikely(r)) - goto error; - } else { - struct shash_desc *desc = verity_io_hash_req(v, io); - struct bio *bio = - dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); - struct bio_vec bv = bio_iter_iovec(bio, *iter); - const unsigned int len = 1 << v->data_dev_block_bits; - const void *virt; - - if (unlikely(len > bv.bv_len)) { - /* - * Data block spans pages. This should not happen, - * since this code path is not used if the data block - * size is greater than the page size, and all I/O - * should be data block aligned because dm-verity sets - * logical_block_size to the data block size. - */ - DMERR_LIMIT("unaligned io (data block spans pages)"); - return -EIO; - } - - desc->tfm = v->shash_tfm; - r = crypto_shash_import(desc, v->initial_hashstate); - if (unlikely(r)) - goto error; - - virt = bvec_kmap_local(&bv); - r = crypto_shash_finup(desc, virt, len, digest); - kunmap_local(virt); - if (unlikely(r)) - goto error; - - bio_advance_iter(bio, iter, len); - } - return 0; - -error: - DMERR("Error hashing block from bio iter: %d", r); - return r; -} - /* * Calls function process for 1 << v->data_dev_block_bits bytes in the bio_vec * starting from iter. */ int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io, @@ -581,41 +520,42 @@ static int verity_recheck_copy(struct dm_verity *v, struct dm_verity_io *io, io->recheck_buffer += len; return 0; } -static noinline int verity_recheck(struct dm_verity *v, struct dm_verity_io *io, - struct bvec_iter start, sector_t cur_block) +static int verity_recheck(struct dm_verity *v, struct dm_verity_io *io, + struct bvec_iter start, sector_t blkno, + const u8 *want_digest) { struct page *page; void *buffer; int r; struct dm_io_request io_req; struct dm_io_region io_loc; + u8 real_digest[HASH_MAX_DIGESTSIZE]; page = mempool_alloc(&v->recheck_pool, GFP_NOIO); buffer = page_to_virt(page); io_req.bi_opf = REQ_OP_READ; io_req.mem.type = DM_IO_KMEM; io_req.mem.ptr.addr = buffer; io_req.notify.fn = NULL; io_req.client = v->io; io_loc.bdev = v->data_dev->bdev; - io_loc.sector = cur_block << (v->data_dev_block_bits - SECTOR_SHIFT); + io_loc.sector = blkno << (v->data_dev_block_bits - SECTOR_SHIFT); io_loc.count = 1 << (v->data_dev_block_bits - SECTOR_SHIFT); r = dm_io(&io_req, 1, &io_loc, NULL, IOPRIO_DEFAULT); if (unlikely(r)) goto free_ret; r = verity_compute_hash_virt(v, io, buffer, 1 << v->data_dev_block_bits, - verity_io_real_digest(v, io), true); + real_digest, true); if (unlikely(r)) goto free_ret; - if (memcmp(verity_io_real_digest(v, io), - verity_io_want_digest(v, io), v->digest_size)) { + if (memcmp(real_digest, want_digest, v->digest_size)) { r = -EIO; goto free_ret; } io->recheck_buffer = buffer; @@ -647,22 +587,84 @@ static inline void verity_bv_skip_block(struct dm_verity *v, struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); bio_advance_iter(bio, iter, 1 << v->data_dev_block_bits); } +static noinline int +__verity_handle_data_hash_mismatch(struct dm_verity *v, struct dm_verity_io *io, + struct bio *bio, struct bvec_iter *start, + sector_t blkno, const u8 *want_digest) +{ + if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { + /* + * Error handling code (FEC included) cannot be run in the + * BH workqueue, so fallback to a standard workqueue. + */ + return -EAGAIN; + } + if (verity_recheck(v, io, *start, blkno, want_digest) == 0) { + if (v->validated_blocks) + set_bit(blkno, v->validated_blocks); + return 0; + } +#if defined(CONFIG_DM_VERITY_FEC) + if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_DATA, blkno, + want_digest, NULL, start) == 0) + return 0; +#endif + if (bio->bi_status) + return -EIO; /* Error correction failed; Just return error */ + + if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_DATA, blkno)) { + dm_audit_log_bio(DM_MSG_PREFIX, "verify-data", bio, blkno, 0); + return -EIO; + } + return 0; +} + +static __always_inline int +verity_check_data_block_hash(struct dm_verity *v, struct dm_verity_io *io, + struct bio *bio, struct bvec_iter *start, + sector_t blkno, + const u8 *real_digest, const u8 *want_digest) +{ + if (likely(memcmp(real_digest, want_digest, v->digest_size) == 0)) { + if (v->validated_blocks) + set_bit(blkno, v->validated_blocks); + return 0; + } + return __verity_handle_data_hash_mismatch(v, io, bio, start, blkno, + want_digest); +} + /* * Verify one "dm_verity_io" structure. */ static int verity_verify_io(struct dm_verity_io *io) { - bool is_zero; struct dm_verity *v = io->v; + const unsigned int block_size = 1 << v->data_dev_block_bits; + struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); + u8 want_digest[HASH_MAX_DIGESTSIZE]; + u8 real_digest[HASH_MAX_DIGESTSIZE]; struct bvec_iter start; struct bvec_iter iter_copy; struct bvec_iter *iter; - struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size); + /* + * The pending_* variables are used when the selected hash algorithm + * supports multibuffer hashing. They're used to temporarily store the + * virtual address and position of a mapped data block that needs to be + * verified. If we then see another data block, we hash the two blocks + * simultaneously using the fast multibuffer hashing method. + */ + const void *pending_data = NULL; + sector_t pending_blkno; + struct bvec_iter pending_start; + u8 pending_want_digest[HASH_MAX_DIGESTSIZE]; + u8 pending_real_digest[HASH_MAX_DIGESTSIZE]; unsigned int b; + int r; if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { /* * Copy the iterator in case we need to restart * verification in a work-queue. @@ -671,82 +673,174 @@ static int verity_verify_io(struct dm_verity_io *io) iter = &iter_copy; } else iter = &io->iter; for (b = 0; b < io->n_blocks; b++) { - int r; - sector_t cur_block = io->block + b; + sector_t blkno = io->block + b; + bool is_zero; if (v->validated_blocks && bio->bi_status == BLK_STS_OK && - likely(test_bit(cur_block, v->validated_blocks))) { + likely(test_bit(blkno, v->validated_blocks))) { verity_bv_skip_block(v, io, iter); continue; } - r = verity_hash_for_block(v, io, cur_block, - verity_io_want_digest(v, io), - &is_zero); + r = verity_hash_for_block(v, io, blkno, want_digest, &is_zero); if (unlikely(r < 0)) - return r; + goto error; if (is_zero) { /* * If we expect a zero block, don't validate, just * return zeros. */ r = verity_for_bv_block(v, io, iter, verity_bv_zero); if (unlikely(r < 0)) - return r; + goto error; continue; } start = *iter; - r = verity_compute_hash(v, io, iter, - verity_io_real_digest(v, io), - !io->in_bh); - if (unlikely(r < 0)) - return r; - - if (likely(memcmp(verity_io_real_digest(v, io), - verity_io_want_digest(v, io), v->digest_size) == 0)) { - if (v->validated_blocks) - set_bit(cur_block, v->validated_blocks); - continue; - } else if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) { - /* - * Error handling code (FEC included) cannot be run in a - * tasklet since it may sleep, so fallback to work-queue. - */ - return -EAGAIN; - } else if (verity_recheck(v, io, start, cur_block) == 0) { - if (v->validated_blocks) - set_bit(cur_block, v->validated_blocks); - continue; -#if defined(CONFIG_DM_VERITY_FEC) - } else if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_DATA, - cur_block, NULL, &start) == 0) { - continue; -#endif + if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) { + /* Hash and verify one data block using ahash. */ + struct ahash_request *req = verity_io_hash_req(v, io); + struct crypto_wait wait; + + r = verity_ahash_init(v, req, &wait, !io->in_bh); + if (unlikely(r)) + goto hash_error; + + r = verity_ahash_update_block(v, io, iter, &wait); + if (unlikely(r)) + goto hash_error; + + r = verity_ahash_final(v, req, real_digest, &wait); + if (unlikely(r)) + goto hash_error; + + r = verity_check_data_block_hash(v, io, bio, &start, + blkno, real_digest, + want_digest); + if (unlikely(r)) + goto error; } else { - if (bio->bi_status) { + struct shash_desc *desc = verity_io_hash_req(v, io); + struct bio_vec bv = bio_iter_iovec(bio, *iter); + const void *data; + + if (unlikely(bv.bv_len < block_size)) { /* - * Error correction failed; Just return error + * Data block spans pages. This should not + * happen, since this code path is not used if + * the data block size is greater than the page + * size, and all I/O should be data block + * aligned because dm-verity sets + * logical_block_size to the data block size. */ - return -EIO; + DMERR_LIMIT("unaligned io (data block spans pages)"); + r = -EIO; + goto error; } - if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_DATA, - cur_block)) { - dm_audit_log_bio(DM_MSG_PREFIX, "verify-data", - bio, cur_block, 0); - return -EIO; + + data = bvec_kmap_local(&bv); + + if (v->use_finup2x) { + if (pending_data) { + /* Hash and verify two data blocks. */ + desc->tfm = v->shash_tfm; + r = crypto_shash_import(desc, + v->initial_hashstate) ?: + crypto_shash_finup2x(desc, + pending_data, + data, + block_size, + pending_real_digest, + real_digest); + kunmap_local(data); + kunmap_local(pending_data); + pending_data = NULL; + if (unlikely(r)) + goto hash_error; + r = verity_check_data_block_hash( + v, io, bio, + &pending_start, + pending_blkno, + pending_real_digest, + pending_want_digest); + if (unlikely(r)) + goto error; + r = verity_check_data_block_hash( + v, io, bio, + &start, + blkno, + real_digest, + want_digest); + if (unlikely(r)) + goto error; + } else { + /* Wait and see if there's another block. */ + pending_data = data; + pending_blkno = blkno; + pending_start = start; + memcpy(pending_want_digest, want_digest, + v->digest_size); + } + } else { + /* Hash and verify one data block. */ + desc->tfm = v->shash_tfm; + r = crypto_shash_import(desc, + v->initial_hashstate) ?: + crypto_shash_finup(desc, data, block_size, + real_digest); + kunmap_local(data); + if (unlikely(r)) + goto hash_error; + r = verity_check_data_block_hash( + v, io, bio, &start, blkno, + real_digest, want_digest); + if (unlikely(r)) + goto error; } + + bio_advance_iter(bio, iter, block_size); } } + if (pending_data) { + /* + * Multibuffer hashing is enabled but there was an odd number of + * data blocks. Hash and verify the last block by itself. + */ + struct shash_desc *desc = verity_io_hash_req(v, io); + + desc->tfm = v->shash_tfm; + r = crypto_shash_import(desc, v->initial_hashstate) ?: + crypto_shash_finup(desc, pending_data, block_size, + pending_real_digest); + kunmap_local(pending_data); + pending_data = NULL; + if (unlikely(r)) + goto hash_error; + r = verity_check_data_block_hash(v, io, bio, + &pending_start, + pending_blkno, + pending_real_digest, + pending_want_digest); + if (unlikely(r)) + goto error; + } + return 0; + +hash_error: + DMERR("Error hashing block from bio iter: %d", r); +error: + if (pending_data) + kunmap_local(pending_data); + return r; } /* * Skip verity work in response to I/O error when system is shutting down. */ @@ -1321,10 +1415,34 @@ static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name) if (!v->alg_name) { ti->error = "Cannot allocate algorithm name"; return -ENOMEM; } + /* + * Allocate the hash transformation object that this dm-verity instance + * will use. We have a choice of two APIs: shash and ahash. Most + * dm-verity users use CPU-based hashing, and for this shash is optimal + * since it matches the underlying algorithm implementations and also + * allows the use of fast multibuffer hashing (crypto_shash_finup2x()). + * ahash adds support for off-CPU hash offloading. It also provides + * access to shash algorithms, but does so less efficiently. + * + * Meanwhile, hashing a block in dm-verity in general requires an + * init+update+final sequence with multiple updates. However, usually + * the salt is prepended to the block rather than appended, and the data + * block size is not greater than the page size. In this very common + * case, the sequence can be optimized to import+finup, where the first + * step imports the pre-computed state after init+update(salt). This + * can reduce the crypto API overhead significantly. + * + * To provide optimal performance for the vast majority of dm-verity + * users while still supporting off-CPU hash offloading and the rarer + * dm-verity settings, we therefore have two code paths: one using shash + * where we use import+finup or import+finup2x, and one using ahash + * where we use init+update(s)+final. We use the former code path when + * it's possible to use and shash gives the same algorithm as ahash. + */ ahash = crypto_alloc_ahash(alg_name, 0, v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0); if (IS_ERR(ahash)) { ti->error = "Cannot initialize hash function"; return PTR_ERR(ahash); @@ -1345,14 +1463,16 @@ static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name) } if (!IS_ERR_OR_NULL(shash)) { crypto_free_ahash(ahash); ahash = NULL; v->shash_tfm = shash; + v->use_finup2x = crypto_shash_supports_finup2x(shash); v->digest_size = crypto_shash_digestsize(shash); v->hash_reqsize = sizeof(struct shash_desc) + crypto_shash_descsize(shash); - DMINFO("%s using shash \"%s\"", alg_name, driver_name); + DMINFO("%s using shash \"%s\"%s", alg_name, driver_name, + v->use_finup2x ? " (multibuffer)" : ""); } else { v->ahash_tfm = ahash; static_branch_inc(&ahash_enabled); v->digest_size = crypto_ahash_digestsize(ahash); v->hash_reqsize = sizeof(struct ahash_request) + diff --git a/drivers/md/dm-verity.h b/drivers/md/dm-verity.h index 15ffb0881cc9c..8040ba1c0a538 100644 --- a/drivers/md/dm-verity.h +++ b/drivers/md/dm-verity.h @@ -55,10 +55,11 @@ struct dm_verity { unsigned char hash_per_block_bits; /* log2(hashes in hash block) */ unsigned char levels; /* the number of tree levels */ unsigned char version; bool hash_failed:1; /* set if hash of any block failed */ bool use_bh_wq:1; /* try to verify in BH wq before normal work-queue */ + bool use_finup2x:1; /* use crypto_shash_finup2x() */ unsigned int digest_size; /* digest size for the current hash algorithm */ unsigned int hash_reqsize; /* the size of temporary space for crypto */ enum verity_mode mode; /* mode for handling verification errors */ unsigned int corrupted_errs;/* Number of errors for corrupted blocks */ @@ -92,42 +93,23 @@ struct dm_verity_io { struct work_struct bh_work; char *recheck_buffer; /* - * Three variably-size fields follow this struct: - * - * u8 hash_req[v->hash_reqsize]; - * u8 real_digest[v->digest_size]; - * u8 want_digest[v->digest_size]; - * - * To access them use: verity_io_hash_req(), verity_io_real_digest() - * and verity_io_want_digest(). - * - * hash_req is either a struct ahash_request or a struct shash_desc, - * depending on whether ahash_tfm or shash_tfm is being used. + * This struct is followed by a variable-sized hash request of size + * v->hash_reqsize, either a struct ahash_request or a struct shash_desc + * (depending on whether ahash_tfm or shash_tfm is being used). To + * access it, use verity_io_hash_req(). */ }; static inline void *verity_io_hash_req(struct dm_verity *v, struct dm_verity_io *io) { return io + 1; } -static inline u8 *verity_io_real_digest(struct dm_verity *v, - struct dm_verity_io *io) -{ - return (u8 *)(io + 1) + v->hash_reqsize; -} - -static inline u8 *verity_io_want_digest(struct dm_verity *v, - struct dm_verity_io *io) -{ - return (u8 *)(io + 1) + v->hash_reqsize + v->digest_size; -} - extern int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io, struct bvec_iter *iter, int (*process)(struct dm_verity *v, struct dm_verity_io *io, u8 *data, size_t len));