| Message ID | 20240611034822.36603-1-ebiggers@kernel.org (mailing list archive) |
|---|---|
| Headers | show |
| Series | Optimize dm-verity and fsverity using multibuffer hashing | expand |
On Tue, 11 Jun 2024 at 05:49, Eric Biggers <ebiggers@kernel.org> wrote: > > 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. > I share Eric's skepticism that shoehorning this into ahash for theoretical reasons is going to lead anywhere. So I would strongly prefer this approach. We can always revisit this if/when this generic multibuffer ahash materializes. So for this series Acked-by: Ard Biesheuvel <ardb@kernel.org>
Hi Eric, On Mon, Jun 10, 2024 at 8:49 PM Eric Biggers <ebiggers@kernel.org> wrote: > > 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. Thank you for continuing to work on this! Improving dm-verity performance is a high priority for Android, and this patch series shows very promising results. FWIW, I would like to see this merged upstream, and any ahash improvements handled in follow-up patches. For the series: Reviewed-by: Sami Tolvanen <samitolvanen@google.com> Sami
Hi I'd like to ask what's the status of this patchset. Will Herbert accept it? What's the planned kernel version where it will appear? Mikulas On Mon, 10 Jun 2024, Eric Biggers wrote: > 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-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 adds multibuffer hashing support to fsverity. > - Patches 7-14 are cleanups and optimizations to dm-verity that prepare > the way for adding multibuffer hashing support. These don't depend on > any of the previous patches. > - Patch 15 adds multibuffer hashing support to dm-verity. > > 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 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 (15): > 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: move hash algorithm setup into its own function > dm-verity: move data hash mismatch handling into its own function > dm-verity: make real_digest and want_digest fixed-length > dm-verity: provide dma_alignment limit in io_hints > dm-verity: always "map" the data blocks > dm-verity: make verity_hash() take dm_verity_io instead of ahash_request > dm-verity: hash blocks with shash import+finup when possible > 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 | 90 ++++- > drivers/md/dm-verity-fec.c | 49 +-- > drivers/md/dm-verity-fec.h | 9 +- > drivers/md/dm-verity-target.c | 582 ++++++++++++++++------------ > drivers/md/dm-verity.h | 66 ++-- > fs/verity/fsverity_private.h | 7 + > fs/verity/hash_algs.c | 8 +- > fs/verity/verify.c | 170 ++++++-- > include/crypto/hash.h | 52 ++- > 14 files changed, 1440 insertions(+), 379 deletions(-) > > > base-commit: 6d4e1993a30539f556da2ebd36f1936c583eb812 > -- > 2.45.1 > >
On Wed, Jul 10, 2024 at 12:54:24PM +0200, Mikulas Patocka wrote: > Hi > > I'd like to ask what's the status of this patchset. > > Will Herbert accept it? What's the planned kernel version where it will > appear? > > Mikulas It's blocked by Herbert wanting to design the multibuffer hashing API in a more complex way that doesn't make sense. See the previous discussions. I don't know when Herbert will change his mind, so for now I've shifted my focus to the Android kernels. (In the mean time, the improvements that don't depend on the actual multibuffer hashing API still make sense to apply upstream, though.) - Eric
On Wed, 10 Jul 2024 at 20:14, Eric Biggers <ebiggers@kernel.org> wrote: > > On Wed, Jul 10, 2024 at 12:54:24PM +0200, Mikulas Patocka wrote: > > Hi > > > > I'd like to ask what's the status of this patchset. > > > > Will Herbert accept it? What's the planned kernel version where it will > > appear? > > > > Mikulas > > It's blocked by Herbert wanting to design the multibuffer hashing API in a more > complex way that doesn't make sense. See the previous discussions. I don't > know when Herbert will change his mind, so for now I've shifted my focus to the > Android kernels. Yeah, this is really quite unfortunate, especially since the alternative approach doesn't appear to be forthcoming. I'd prefer Eric's approach over what Herbert is proposing, as the former is available today and only addressess problems that are actually known to exist, rather than handwavy claims about what future developments in IPsec or h/w crypto accelerators might make meaningful use of.
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-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 adds multibuffer hashing support to fsverity. - Patches 7-14 are cleanups and optimizations to dm-verity that prepare the way for adding multibuffer hashing support. These don't depend on any of the previous patches. - Patch 15 adds multibuffer hashing support to dm-verity. 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 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 (15): 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: move hash algorithm setup into its own function dm-verity: move data hash mismatch handling into its own function dm-verity: make real_digest and want_digest fixed-length dm-verity: provide dma_alignment limit in io_hints dm-verity: always "map" the data blocks dm-verity: make verity_hash() take dm_verity_io instead of ahash_request dm-verity: hash blocks with shash import+finup when possible 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 | 90 ++++- drivers/md/dm-verity-fec.c | 49 +-- drivers/md/dm-verity-fec.h | 9 +- drivers/md/dm-verity-target.c | 582 ++++++++++++++++------------ drivers/md/dm-verity.h | 66 ++-- fs/verity/fsverity_private.h | 7 + fs/verity/hash_algs.c | 8 +- fs/verity/verify.c | 170 ++++++-- include/crypto/hash.h | 52 ++- 14 files changed, 1440 insertions(+), 379 deletions(-) base-commit: 6d4e1993a30539f556da2ebd36f1936c583eb812