dm-verity: hash blocks with shash import+finup when possible

From: Eric Biggers <[email protected]>

Commit d1ac3ff008fb ("dm verity: switch to using asynchronous hash crypto API"), from Linux v4.12, made dm-verity do its hashing using the ahash API instead of the shash API. While this added support for hardware (off-CPU) hashing offload, it slightly hurt performance for everyone else due to additional crypto API overhead. This API overhead is becoming increasingly significant as I/O speeds increase and CPUs achieve increasingly high SHA-2 speeds using native SHA-2 instructions.

Recent crypto API patches
(https://lore.kernel.org/linux-crypto/[email protected])
are reducing that overhead. However, it cannot be eliminated.

Meanwhile, another crypto API related sub-optimality of how dm-verity currently implements block hashing is that it always computes each hash using multiple calls to the crypto API. The most common case is:

1. crypto_ahash_init()
2. crypto_ahash_update() [salt]
3. crypto_ahash_update() [data]
4. crypto_ahash_final()

With less common dm-verity settings, the update of the salt can happen after the data, or the data can require multiple updates.

Regardless, each call adds some API overhead. Again, that's being reduced by recent crypto API patches, but it cannot be eliminated; each init, update, or final step necessarily involves an indirect call to the actual "algorithm", which is expensive on modern CPUs, especially when mitigations for speculative execution vulnerabilities are enabled.

A significantly more optimal sequence for the common case is to do an import (crypto_ahash_import(), then a finup (crypto_ahash_finup()). This results in as few as one indirect call, the one for finup.

Implementing the shash and import+finup optimizations independently would result in 4 code paths, which seems a bit excessive. This patch therefore takes a slightly simpler approach. It implements both optimizations, but only together. So, dm-verity now chooses either the existing, fully general ahash method; or it chooses the new shash import+finup method which is optimized for what most dm-verity users
want: CPU-based hashing with the most common dm-verity settings.

The new method is used automatically when appropriate, i.e. when the ahash API and shash APIs resolve to the same underlying algorithm, the dm-verity version is not 0 (so that the salt is hashed before the data), and the data block size is not greater than the page size.

In benchmarks with veritysetup's default parameters (SHA-256, 4K data and hash block sizes, 32-byte salt), which also match the parameters that Android currently uses, this patch improves block hashing performance by about 15% on an x86_64 system that supports the SHA-NI instructions, or by about 5% on an arm64 system that supports the ARMv8 SHA2 instructions. This was with CONFIG_CRYPTO_STATS disabled; an even larger improvement can be expected if that option is enabled.

Note that another benefit of using "import" to handle the salt is that if the salt size is equal to the input size of the hash algorithm's compression function, e.g. 64 bytes for SHA-256, then the performance is exactly the same as no salt. (This doesn't seem to be much better than veritysetup's current default of 32-byte salts, due to the way SHA-256's finalization padding works, but it should be marginally better.)

In addition to the benchmarks mentioned above, I've tested this patch with cryptsetup's 'verity-compat-test' script. I've also lightly tested this patch with Android, where the new shash-based code gets used.

---
 drivers/md/dm-verity-fec.c    |  12 +-
 drivers/md/dm-verity-target.c | 354 +++++++++++++++++++++++++---------
 drivers/md/dm-verity.h        |  26 ++-
 3 files changed, 281 insertions(+), 111 deletions(-)

index 3ef9f018da60..0781bfba9dbd 100644
@@ -176,23 +176,23 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,
 
 	return r;
 }
 
 /*
  * Locate data block erasures using verity hashes.
  */
 static int fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io,
 			  u8 *want_digest, u8 *data)
 {
-	if (unlikely(verity_hash(v, verity_io_hash_req(v, io),
-				 data, 1 << v->data_dev_block_bits,
-				 verity_io_real_digest(v, io))))
+	if (unlikely(verity_compute_hash_virt(v, io, data,
+					      1 << v->data_dev_block_bits,
+					      verity_io_real_digest(v, io))))
 		return 0;
 
 	return memcmp(verity_io_real_digest(v, io), want_digest,
 		      v->digest_size) != 0;
 }
 
 /*
  * Read data blocks that are part of the RS block and deinterleave as much as
  * fits into buffers. Check for erasure locations if @neras is non-NULL.
  */

@@ -377,23 +377,23 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io,
 			return r;
 
 		r = fec_decode_bufs(v, fio, rsb, r, pos, neras);
 		if (r < 0)
 			return r;
 
 		pos += fio->nbufs << DM_VERITY_FEC_BUF_RS_BITS;
 	}
 
 	/* Always re-validate the corrected block against the expected hash */
-	r = verity_hash(v, verity_io_hash_req(v, io), fio->output,
-			1 << v->data_dev_block_bits,
-			verity_io_real_digest(v, io));
+	r = verity_compute_hash_virt(v, io, fio->output,
+				     1 << v->data_dev_block_bits,
+				     verity_io_real_digest(v, io));
 	if (unlikely(r < 0))
 		return r;
 
 	if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io),
 		   v->digest_size)) {
 		DMERR_LIMIT("%s: FEC %llu: failed to correct (%d erasures)",
 			    v->data_dev->name, (unsigned long long)rsb, neras);
 		return -EILSEQ;
 	}
 

index 2f555b420367..0134cce4246c 100644
@@ -31,38 +31,40 @@ enum verity_block_type {
 };
 
 struct dm_verity_fec;
 
 struct dm_verity {
 	struct dm_dev *data_dev;
 	struct dm_dev *hash_dev;
 	struct dm_target *ti;
 	struct dm_bufio_client *bufio;
 	char *alg_name;
-	struct crypto_ahash *tfm;
+	struct crypto_ahash *ahash_tfm; /* either this or shash_tfm is set */
+	struct crypto_shash *shash_tfm; /* either this or ahash_tfm is set */
 	u8 *root_digest;	/* digest of the root block */
 	u8 *salt;		/* salt: its size is salt_size */
+	u8 *initial_hashstate;	/* salted initial state, if shash_tfm is set */
 	u8 *zero_digest;	/* digest for a zero block */
 	unsigned int salt_size;
 	sector_t data_start;	/* data offset in 512-byte sectors */
 	sector_t hash_start;	/* hash start in blocks */
 	sector_t data_blocks;	/* the number of data blocks */
 	sector_t hash_blocks;	/* the number of hash blocks */
 	unsigned char data_dev_block_bits;	/* log2(data blocksize) */
 	unsigned char hash_dev_block_bits;	/* log2(hash blocksize) */
 	unsigned char hash_per_block_bits;	/* log2(hashes in hash block) */
 	unsigned char levels;	/* the number of tree levels */
 	unsigned char version;
 	bool hash_failed:1;	/* set if hash of any block failed */
 	bool use_tasklet:1;	/* try to verify in tasklet before work-queue */
 	unsigned int digest_size;	/* digest size for the current hash algorithm */
-	unsigned int ahash_reqsize;/* the size of temporary space for crypto */
+	unsigned int hash_reqsize; /* the size of temporary space for crypto */
 	enum verity_mode mode;	/* mode for handling verification errors */
 	unsigned int corrupted_errs;/* Number of errors for corrupted blocks */
 
 	struct workqueue_struct *verify_wq;
 
 	/* starting blocks for each tree level. 0 is the lowest level. */
 	sector_t hash_level_block[DM_VERITY_MAX_LEVELS];
 
 	struct dm_verity_fec *fec;	/* forward error correction */
 	unsigned long *validated_blocks; /* bitset blocks validated */

@@ -81,61 +83,65 @@ struct dm_verity_io {
 	bool in_tasklet;
 
 	struct bvec_iter iter;
 
 	struct work_struct work;
 	struct tasklet_struct tasklet;
 
 	/*
 	 * Three variably-size fields follow this struct:
 	 *
-	 * u8 hash_req[v->ahash_reqsize];
+	 * u8 hash_req[v->hash_reqsize];
 	 * u8 real_digest[v->digest_size];
 	 * u8 want_digest[v->digest_size];
 	 *
 	 * To access them use: verity_io_hash_req(), verity_io_real_digest()
 	 * and verity_io_want_digest().
+	 *
+	 * hash_req is either a struct ahash_request or a struct shash_desc,
+	 * depending on whether ahash_tfm or shash_tfm is being used.
 	 */
 };
 
-static inline struct ahash_request *verity_io_hash_req(struct dm_verity *v,
-						     struct dm_verity_io *io)
+static inline void *verity_io_hash_req(struct dm_verity *v,
+				       struct dm_verity_io *io)
 {
-	return (struct ahash_request *)(io + 1);
+	return io + 1;
 }
 
 static inline u8 *verity_io_real_digest(struct dm_verity *v,
 					struct dm_verity_io *io)
 {
-	return (u8 *)(io + 1) + v->ahash_reqsize;
+	return (u8 *)(io + 1) + v->hash_reqsize;
 }
 
 static inline u8 *verity_io_want_digest(struct dm_verity *v,
 					struct dm_verity_io *io)
 {
-	return (u8 *)(io + 1) + v->ahash_reqsize + v->digest_size;
+	return (u8 *)(io + 1) + v->hash_reqsize + v->digest_size;
 }
 
 static inline u8 *verity_io_digest_end(struct dm_verity *v,
 				       struct dm_verity_io *io)
 {
 	return verity_io_want_digest(v, io) + v->digest_size;
 }
 
 extern int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io,
 			       struct bvec_iter *iter,
 			       int (*process)(struct dm_verity *v,
 					      struct dm_verity_io *io,
 					      u8 *data, size_t len));
 
-extern int verity_hash(struct dm_verity *v, struct ahash_request *req,
-		       const u8 *data, size_t len, u8 *digest);
+extern int verity_compute_hash_virt(struct dm_verity *v,
+				    struct dm_verity_io *io,
+				    const u8 *data, size_t len, u8 *digest);
 
 extern int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
 				 sector_t block, u8 *digest, bool *is_zero);
 
 extern bool dm_is_verity_target(struct dm_target *ti);
 extern int dm_verity_get_mode(struct dm_target *ti);
 extern int dm_verity_get_root_digest(struct dm_target *ti, u8 **root_digest,
 				     unsigned int *digest_size);
 
 #endif /* DM_VERITY_H */

base-commit: 2af9b20dbb39f6ebf9b9b6c090271594627d818e

2.42.0

Hi Eric,

That's an impressive performance improvement. Thanks for the patch!

Sami

That would provide the import+finup optimization, but it would retain the overhead of ahash compared to shash. That overhead includes a small amount of extra CPU time as well as the bio size being increased by sizeof(struct ahash_request). It's a small difference, but dm-verity performance is really important.

Note that dm-verity also has to use an ugly and error-prone workaround to use ahash at all, since its hash blocks can be cached in vmalloc memory; see verity_hash_update(). shash handles vmalloc memory much more naturally, since no translation from vmalloc address to page to linear address is needed.

I'm thinking that avoiding the extra overhead of ahash, combined with avoiding the workaround for vmalloc memory, makes it worthwhile to use shash for the import+export code path. If it was just ahash vs. shash by itself, we wouldn't bother, but the fact that we can combine the two optimizations seems attractive.

This patch limits the use of shash to blocks of at most PAGE_SIZE (*), which is the same as what ahash does internally.

(*) Except when the data block size is <= PAGE_SIZE but the hash block size is

worrying too much about, but it could be excluded from the shash-based code.

- Eric

So why not drop ahash and always use shash? Does anybody care about offload for dm-verity?

Alternatively, we could incorporate this into ahash itself. Then you could have an optimised code path that does not do SGs if the underlying algorithm is shash.

I really do not wish to see this ahash/shash paradigm proliferate.

OK. But we do still have the module signature verification code path and I think that one still needs the can-sleep flag.

Thanks,

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

I'd love to do that; it's what I did in fsverity. Someone did intentionally convert dm-verity from shash to ahash in 2017, though; see commit d1ac3ff008fb. So we'd be reverting that. Maybe there are people who'd still care. Maybe not. I haven't yet gotten any complaints about switching fsverity to shash in v6.5 (and I only used ahash originally because of the precedent of dm-verity).

Do you have in mind making struct ahash_request specify the data by either scatterlist or by virtual address? It might be possible. It would be necessary to wire up all possible combinations of (SG, virt) x (ahash_alg, shash_alg), with the vmalloc_to_page() hack for the virt + ahash_alg case.

Well, struct shash_desc used to have that flag, but it never did anything. The few use cases like this might be more simply served by just having a helper function crypto_shash_update_large() that passes the data in chunks to crypto_shash_update().

- Eric

Yes that's what I had in mind. We need to do something similar for akcipher now that the top-level interface is linear only but the drivers are still SG-based.

Are you volunteering to add this interface? :)

The module signature path is really broken right now, at least on non-preemptible kernels.

Thanks,

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt