From patchwork Tue Oct 1 15:37:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13818669 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 D08F8CEACF8 for ; Tue, 1 Oct 2024 18:46:44 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender:List-Subscribe:List-Help :List-Post:List-Archive:List-Unsubscribe:List-Id:Content-Transfer-Encoding: MIME-Version:Message-ID:Date:Subject:Cc:To:From:Reply-To:Content-Type: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Owner; bh=PfwQHrR1N26H8vry7rac3/FsvRfxPCq6Z7LIZC/S99Y=; b=hQ9w/E703YZMblav/BouqRcNuz rnFN2W1QrWmhMosomb/ZZLG16bnBMlqv1jLacUk2v9jPzDsw78qoobG2RDxq8Zk1RICm4OPEGDa3n KgYW3dvo3rhpDLPJe25vEs+iL+nCD5LPOhMV+dmnAdBLcdx+j9U153v7AQCd7Fso6EVq732uBLGMT G/ZolNc2HNL+1FEW2SNydYlVNfL48VY+aM6MEVgYQmOeh7DOj3jeG6xsGydpBTknNe/ovmyCbre0g t4Bh//P5qHOboZBzWFcsAJvxt6QUF/yt+PEj/KFvoPkCYMFyvD8JJJHyR7G4o4amdvBkos/TTfbmw azIsr8tg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.98 #2 (Red Hat Linux)) id 1svhtK-00000003o4O-11nC; Tue, 01 Oct 2024 18:46:34 +0000 Received: from dfw.source.kernel.org ([139.178.84.217]) by bombadil.infradead.org with esmtps (Exim 4.98 #2 (Red Hat Linux)) id 1sveyE-00000003MD4-1Sp5 for linux-arm-kernel@lists.infradead.org; Tue, 01 Oct 2024 15:39:28 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 05D685C100D; Tue, 1 Oct 2024 15:39:16 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 5F181C4CEC6; Tue, 1 Oct 2024 15:39:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1727797159; bh=SohKAUfLV7IzJXvpfUahCfDYMFsDrTqFD0/Qs1d6Vqs=; h=From:To:Cc:Subject:Date:From; b=aFclFuvpEBpcM7lzq45poOnrpcXgakd7NUms9f4tP2tmMXKwMX3xVLQH//aJ2ELwY TwsWF3R3rmEcfhzNaG+u/78GpCwEoS6SCnSjbjfPMoH+dAla2eaG4uEnXydONtY8P+ 9cgENhCzUXFnx0SiMgxib2iXun4B0Of0/0j/lzVvdbzeHsAGxckQ+o1Jz2MhnYlfWS mjpmksmEcKMr0/ftnZdzVhGODAQ6iwWveOtFhCIRyTeDM/eTodXl/7h2bkWXHNv0PX cx8bnenb/32+ymWnQ63p8nTFjf071HOVyfVXD06xy1qPT1gi3S452Wt57tHotRwl8c RVO0jIOM2Gyjw== 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 , Herbert Xu , Alasdair Kergon , Mike Snitzer , Mikulas Patocka Subject: [PATCH v7 0/7] Optimize dm-verity and fsverity using multibuffer hashing Date: Tue, 1 Oct 2024 08:37:11 -0700 Message-ID: <20241001153718.111665-1-ebiggers@kernel.org> X-Mailer: git-send-email 2.46.2 MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20241001_083926_545985_B9BFC9E5 X-CRM114-Status: GOOD ( 16.18 ) 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, as does the alternative ahash-based approach proposed by Herbert (see my response at https://lore.kernel.org/linux-crypto/20240610164258.GA3269@sol.localdomain/). 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-2 add crypto_shash_finup_mb() and tests for it. - Patch 3-4 implement finup_mb on x86_64 and arm64, using an interleaving factor of 2. - Patch 5 adds multibuffer hashing support to fsverity. - Patch 6-7 add multibuffer hashing support to dm-verity. This patchset increases raw SHA-256 hashing throughput by up to 98%, depending on the CPU (see patches for per-CPU results). The throughput of cold-cache reads from dm-verity and fsverity increases by around 35%. Changed in v7: - Rebased onto v6.12-rc1 and dropped patches that were upstreamed. - Added performance results for more CPUs. Changed in v6: - All patches: added Reviewed-by and Acked-by tags - "crypto: testmgr - add tests for finup_mb": Whitespace fix - "crypto: testmgr - generate power-of-2 lengths more often": Fixed undefined behavior - "fsverity: improve performance by using multibuffer hashing": Simplified a comment - "dm-verity: reduce scope of real and wanted digests": Fixed mention of nonexistent function in commit message - "dm-verity: improve performance by using multibuffer hashing": Two small optimizations, and simplified a comment Changed in v5: - Reworked the dm-verity patches again. Split the preparation work into separate patches, fixed two bugs, and added some new cleanups. - Other small cleanups Changed in v4: - Reorganized the fsverity and dm-verity code to have a unified code path for single-block vs. multi-block processing. For data blocks they now use only crypto_shash_finup_mb(). 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 (7): crypto: shash - add support for finup_mb 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: reduce scope of real and wanted digests 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 | 58 +++++ crypto/testmgr.c | 73 +++++- drivers/md/dm-verity-fec.c | 19 +- drivers/md/dm-verity-fec.h | 5 +- drivers/md/dm-verity-target.c | 192 +++++++++++---- drivers/md/dm-verity.h | 34 +-- fs/verity/fsverity_private.h | 7 + fs/verity/hash_algs.c | 8 +- fs/verity/verify.c | 169 ++++++++++--- include/crypto/hash.h | 52 +++- 14 files changed, 1224 insertions(+), 121 deletions(-) base-commit: 9852d85ec9d492ebef56dc5f229416c925758edc