From patchwork Tue May 7 00:23:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13656142 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 62364C25B10 for ; Tue, 7 May 2024 00:25:38 +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: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:In-Reply-To:References: List-Owner; bh=+Yzlfp3OVIwj+AZ7zB2obHuReXagGoxQreXzxCkc9HU=; b=S+HbQFaj8TylUw GbuKwDKPPo3VI4bSSibtYTiBRl9MmRLVJuVkMALm3jqBPvGkRWbDAq9sk/uWMt/z9SCZRoQe9HVGl Kvi5Jhu6fu2W22qKRo5oGMbPwd2JrIsDbPY/H/vGMrUnaqQRbN+pUONV37PNt2UFK5w2N36jnfGML aueLTs24l92aKyvJtfUzuvnQyAmHiXuqetw59CSOVzYCNZ82x0H4ZGhZ7qVGXRjCqGXAZGZS/clUi UEiLfrB7VWIrXanUK6dvRHX11YiMuIRT8HFokaktFC89AfAa0aF3ep8fDSMh164GrKR/3grcJmv58 449cE1Q06Odoy8qwJV4Q==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1s48e7-000000098zz-38f6; Tue, 07 May 2024 00:25:27 +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 1s48dz-000000098t8-0jvD for linux-arm-kernel@lists.infradead.org; Tue, 07 May 2024 00:25:21 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id B0D3BCE1002; Tue, 7 May 2024 00:25:16 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id A76A4C116B1; Tue, 7 May 2024 00:25:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1715041515; bh=s7eBMIDMnKUPCUXSt92sBihifomPay5rghqvBJKTjqk=; h=From:To:Cc:Subject:Date:From; b=DKFHtSIzwCtggFmwgVNyvFpYLdhnLcCxCQPuHNK4a5PxuijN0Tf6AHz/0noYtG9zT Sep4DM7tMwaUOrbZ2Y0DXhUnEj9pEQrOiLsUgwYqbdqyy68jNRYkiXAUbEhA7xdlWK 87vSxjbRIGh8Dy4R9dJemz3OEvcFshe9IO1vvZhPdDFkLOA8ZLt1nETEcIU+4GR7vr Se2KmaAfUIuXOKDb++oC/wCPx95eOeedCLoVNxISpFpggzYzqd1hvRfFMuUN8W76MX uzr43qdjXmKCsMS0g9OvUD3bTNBsacI09UjVD+h8EbxupBl7M+NjbDEcXgYn5HP19C pdKq/AIJhz7PA== 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: [PATCH v3 0/8] Optimize dm-verity and fsverity using multibuffer hashing Date: Mon, 6 May 2024 17:23:35 -0700 Message-ID: <20240507002343.239552-1-ebiggers@kernel.org> X-Mailer: git-send-email 2.45.0 MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240506_172519_598710_6235B317 X-CRM114-Status: GOOD ( 13.05 ) 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 On many modern CPUs, it is possible to compute the SHA-256 hash of two equal-length messages in about the same time as a single message, if all the instructions are interleaved. This is because each SHA-256 (and also most other cryptographic hash functions) is inherently serialized and therefore can't always take advantage of the CPU's full throughput. An earlier attempt to support multibuffer hashing in Linux was based around the ahash API. That approach had some major issues. This patchset instead takes a much simpler approach of just adding a synchronous API for hashing equal-length messages. This works well for dm-verity and fsverity, which use Merkle trees and therefore hash large numbers of equal-length messages. This patchset is organized as follows: - Patch 1-3 add crypto_shash_finup_mb() and tests for it. - Patch 4-5 implement finup_mb on x86_64 and arm64, using an interleaving factor of 2. - Patch 6-8 update fsverity and dm-verity to use crypto_shash_finup_mb() to hash pairs of data blocks when possible. Note: the patch "dm-verity: hash blocks with shash import+finup when possible" is revived from its original submission (https://lore.kernel.org/dm-devel/20231030023351.6041-1-ebiggers@kernel.org/) because this new work provides a new motivation for it. On CPUs that support multiple concurrent SHA-256's (all arm64 CPUs I tested, and AMD Zen CPUs), raw SHA-256 hashing throughput increases by 70-98%, and the throughput of cold-cache reads from dm-verity and fsverity increases by very roughly 35%. Changed in v3: - Change API from finup2x to finup_mb. It now takes arrays of data buffer and output buffers, avoiding hardcoding 2x in the API. Changed in v2: - Rebase onto cryptodev/master - Add more comments to assembly - Reorganize some of the assembly slightly - Fix the claimed throughput improvement on arm64 - Fix incorrect kunmap order in fs/verity/verify.c - Adjust testmgr generation logic slightly - Explicitly check for INT_MAX before casting unsigned int to int - Mention SHA3 based parallel hashes - Mention AVX512-based approach Eric Biggers (8): crypto: shash - add support for finup_mb crypto: testmgr - generate power-of-2 lengths more often crypto: testmgr - add tests for finup_mb crypto: x86/sha256-ni - add support for finup_mb crypto: arm64/sha256-ce - add support for finup_mb fsverity: improve performance by using multibuffer hashing dm-verity: hash blocks with shash import+finup when possible dm-verity: improve performance by using multibuffer hashing arch/arm64/crypto/sha2-ce-core.S | 281 +++++++++++++- arch/arm64/crypto/sha2-ce-glue.c | 40 ++ arch/x86/crypto/sha256_ni_asm.S | 368 ++++++++++++++++++ arch/x86/crypto/sha256_ssse3_glue.c | 39 ++ crypto/shash.c | 60 +++ crypto/testmgr.c | 91 ++++- drivers/md/dm-verity-fec.c | 31 +- drivers/md/dm-verity-fec.h | 7 +- drivers/md/dm-verity-target.c | 563 ++++++++++++++++++++-------- drivers/md/dm-verity.h | 43 +-- fs/verity/fsverity_private.h | 5 + fs/verity/hash_algs.c | 32 +- fs/verity/open.c | 6 + fs/verity/verify.c | 177 +++++++-- include/crypto/hash.h | 45 ++- 15 files changed, 1543 insertions(+), 245 deletions(-) base-commit: ed265f7fd9a635d77c8022fc6d9a1b735dd4dfd7