[RFC,1/8] crypto: shash - add support for finup2x

From: Eric Biggers <ebiggers@google.com>

Most cryptographic hash functions are serialized, in the sense that they
have an internal block size and the blocks must be processed serially.
(BLAKE3 is a notable exception that has tree-based hashing built-in, but
all the more common choices such as the SHAs and BLAKE2 are serialized.)

This limits the performance of computing a single hash.  Yet, computing
multiple hashes simultaneously does not have this limitation.  Modern
CPUs are superscalar and often can execute independent instructions in
parallel.  As a result, on many modern CPUs, it is possible to hash two
equal-length messages in about the same time as a single message, if all
the instructions are interleaved.

Meanwhile, a very common use case for hashing in the Linux kernel is
dm-verity and fs-verity.  Both use a Merkle tree that has a fixed block
size, usually 4096 bytes with an empty or 32-byte salt prepended.  The
hash algorithm is usually SHA-256.  Usually, many blocks need to be
hashed at a time.  This is an ideal scenario for multibuffer hashing.

Linux actually used to support SHA-256 multibuffer hashing on x86_64,
before it was removed by commit ab8085c130ed ("crypto: x86 - remove SHA
multibuffer routines and mcryptd").  However, it was integrated with the
crypto API in a weird way, where it behaved as an asynchronous hash that
queued up and executed all requests on a global queue.  This made it
very complex, buggy, and virtually unusable.

This patch takes a new approach of just adding an API
crypto_shash_finup2x() that synchronously computes the hash of two
equal-length messages, starting from a common state that represents the
(possibly empty) common prefix shared by the two messages.

The new API is part of the "shash" algorithm type, as it does not make
sense in "ahash".  It does a "finup" operation rather than a "digest"
operation in order to support the salt that is used by dm-verity and
fs-verity.  There is no fallback implementation that does two regular
finups if the underlying algorithm doesn't support finup2x, since users
probably will want to avoid the overhead of queueing up multiple hashes
when multibuffer hashing won't actually be used anyway.

For now the API only supports 2-way interleaving, as the usefulness and
practicality seems to drop off dramatically after 2.  The arm64 CPUs I
tested don't support more than 2 concurrent SHA-256 hashes.  On x86_64,
AMD's Zen 4 is a notable exception that can theoretically do 4
concurrent SHA-256 hashes (at least based on a microbenchmark of the
sha256rnds2 instruction).  However, increasing the interleaving factor
further would involve tradeoffs such as no longer being able to cache
the round constants in registers, further increasing the code size (both
source and binary), further increasing the amount of state that users
need to keep track of, and causing there to be more "leftover" hashes.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 include/crypto/hash.h | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

Eric Biggers <ebiggers@kernel.org> wrote:
>
> The new API is part of the "shash" algorithm type, as it does not make
> sense in "ahash".  It does a "finup" operation rather than a "digest"
> operation in order to support the salt that is used by dm-verity and
> fs-verity.  There is no fallback implementation that does two regular
> finups if the underlying algorithm doesn't support finup2x, since users
> probably will want to avoid the overhead of queueing up multiple hashes
> when multibuffer hashing won't actually be used anyway.

For your intended users, will the SIMD fallback ever be invoked?

Cheers,

On Fri, Apr 19, 2024 at 06:35:01PM +0800, Herbert Xu wrote:
> Eric Biggers <ebiggers@kernel.org> wrote:
> >
> > The new API is part of the "shash" algorithm type, as it does not make
> > sense in "ahash".  It does a "finup" operation rather than a "digest"
> > operation in order to support the salt that is used by dm-verity and
> > fs-verity.  There is no fallback implementation that does two regular
> > finups if the underlying algorithm doesn't support finup2x, since users
> > probably will want to avoid the overhead of queueing up multiple hashes
> > when multibuffer hashing won't actually be used anyway.
> 
> For your intended users, will the SIMD fallback ever be invoked?
> 

If you mean the fallback to scalar instructions when !crypto_simd_usable(), by
default dm-verity and fs-verity do all hashing in process context, in which case
the scalar fallback will never be used.  dm-verity does support the
'try_verify_in_tasklet' option which makes hashing sometimes happen in softirq
context, and x86 Linux has an edge case where if a softirq comes in while the
kernel is in the middle of using SIMD instructions, SIMD instructions can't be
used during that softirq.  So in theory the !crypto_simd_usable() case could be
reached then.  Either way, I have the fallback implemented in the x86 and arm64
SHA-256 glue code for consistency with the rest of the crypto_shash API anyway.

If you mean falling back to two crypto_shash_finup() when the algorithm doesn't
support crypto_shash_finup2x(), my patches to dm-verity and fs-verity do that.
Modern x86_64 and arm64 systems will use crypto_shash_finup2x(), but dm-verity
and fs-verity need to work on all architectures and on older CPUs too.  The
alternative would be to put the fallback to two crypto_shash_finup() directly in
crypto_shash_finup2x() and have the users call crypto_shash_finup2x()
unconditionally (similar to how crypto_shash_digest() can be called even if the
underlying shash_alg doesn't implement ->digest()).  That would make for
slightly simpler code, though it feels a bit awkward to queue up multiple blocks
for multibuffer hashing when multibuffer hashing won't actually be used.  Let me
know if you have a preference about this.

- Eric