[RFC,0/8] Optimize dm-verity and fsverity using multibuffer hashing

Message

Eric Biggers April 15, 2024, 9:37 p.m. UTC

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 two 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_finup2x() and tests for it.
- Patch 4-5 implement finup2x on x86_64 and arm64.
- Patch 6-8 update fsverity and dm-verity to use crypto_shash_finup2x()
  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/[e-mail]/)
  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
82-98%, and the throughput of cold-cache reads from dm-verity and
fsverity increases by very roughly 35%.

This is marked as RFC for now, as I'm soliciting feedback on the overall
concept, and some parts may need a bit more work.  The dm-verity and
fsverity patches are a bit large and I may try to split those up.

Eric Biggers (8):
  crypto: shash - add support for finup2x
  crypto: testmgr - generate power-of-2 lengths more often
  crypto: testmgr - add tests for finup2x
  crypto: x86/sha256-ni - add support for finup2x
  crypto: arm64/sha256-ce - add support for finup2x
  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    | 261 ++++++++++++-
 arch/arm64/crypto/sha2-ce-glue.c    |  40 ++
 arch/x86/crypto/sha256_ni_asm.S     | 352 +++++++++++++++++
 arch/x86/crypto/sha256_ssse3_glue.c |  40 ++
 crypto/testmgr.c                    |  59 ++-
 drivers/md/dm-verity-fec.c          |  31 +-
 drivers/md/dm-verity-fec.h          |   7 +-
 drivers/md/dm-verity-target.c       | 560 ++++++++++++++++++++--------
 drivers/md/dm-verity.h              |  43 +--
 fs/verity/fsverity_private.h        |   5 +
 fs/verity/hash_algs.c               |  31 +-
 fs/verity/open.c                    |   6 +
 fs/verity/verify.c                  | 177 +++++++--
 include/crypto/hash.h               |  34 ++
 14 files changed, 1403 insertions(+), 243 deletions(-)


base-commit: 0bbac3facb5d6cc0171c45c9873a2dc96bea9680