From patchwork Mon Jun 3 18:37:23 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Biggers X-Patchwork-Id: 13684072 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 E6FB2C25B76 for ; Mon, 3 Jun 2024 18:39:25 +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=b3pojVzzFmhh0vpxvTjPrt1BFyue2UvPMYxrrecqJ/8=; b=eRoNu0RKpGFYKU TVT9bcMGc2eBNVm0v6qnO6H3pvRuEBk4EiRdhoA3Moskzqwvxj5MHECfIphpNTf8yZZQdiinEoK9b 0JdHMF7VFt+hUhoombQgOIIrkA+ks8HoBx4YSWAC8QSsdbCVwe0Og9MtwgvkzRPuPxY0wD0RqfJGe KWjB8FRClhch8mChmsOPX4MFrcUgW115RK50ti33HnB6F1yUN/0qgR9Dy+ae3K1Rk3EBJgy6QTANX jj52jCN3UCcj1dfyXBY+cDjzvM5kN3QlO3VnJwh2meQdd6vnGG1kjuamjP3A6Nwz43GytIAkxWqti 1m+natgOK+oM27d9ecrw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.97.1 #2 (Red Hat Linux)) id 1sECaS-000000002lg-1RIE; Mon, 03 Jun 2024 18:39:16 +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 1sECaH-000000002cO-3J3A for linux-arm-kernel@lists.infradead.org; Mon, 03 Jun 2024 18:39:09 +0000 Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id D10CFCE0E8B; Mon, 3 Jun 2024 18:39:03 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id D00EBC2BD10; Mon, 3 Jun 2024 18:39:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1717439943; bh=cuaWNZB+W8ps7z5awlku/z83BkDgv1blEbXuyhu0RU4=; h=From:To:Cc:Subject:Date:From; b=LVDmVIBB/u9JAy2fKk7Att6u6L85xJe6vmd8Wj9JE5RUJRwaQ8l8b9bZl2oWq6FAX GyOTI4YeJtrH1BoL/FKgKYEy256xAAk6K7+20ZPD0aQGqzkpPJGEmwiWTDWIAxzfi7 RE7yLEpyC4hbikfnQN5mkot1TboxNqo0FF6AH40ncEuzN+Gms7SZ+O9mIHLiWVQ9Aq 5EljsdCUiXfifbe4vWw77Sz+NurqU4wt6uWThFLv0BGnj/LkYQYRibcBL4L9Bo3q2F BcVXlEDeCKf9R0eSl7CVhWHV59O8d4UmqCAT8j9THNUI63AVANadbj+Llcgl1FlbDV hflvAehx52Sgg== From: Eric Biggers To: linux-crypto@vger.kernel.org, fsverity@lists.linux.dev, dm-devel@lists.linux.dev, Herbert Xu Cc: x86@kernel.org, linux-arm-kernel@lists.infradead.org, Ard Biesheuvel , Sami Tolvanen , Bart Van Assche Subject: [PATCH v4 0/8] Optimize dm-verity and fsverity using multibuffer hashing Date: Mon, 3 Jun 2024 11:37:23 -0700 Message-ID: <20240603183731.108986-1-ebiggers@kernel.org> X-Mailer: git-send-email 2.45.1 MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20240603_113906_249096_DDA652A6 X-CRM114-Status: GOOD ( 14.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 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 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 (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 | 90 ++++- drivers/md/dm-verity-fec.c | 31 +- drivers/md/dm-verity-fec.h | 7 +- drivers/md/dm-verity-target.c | 545 ++++++++++++++++++++-------- drivers/md/dm-verity.h | 43 +-- fs/verity/fsverity_private.h | 7 + fs/verity/hash_algs.c | 8 +- fs/verity/verify.c | 173 +++++++-- include/crypto/hash.h | 45 ++- 14 files changed, 1494 insertions(+), 243 deletions(-) base-commit: aabbf2135f9a9526991f17cb0c78cf1ec878f1c2