[permalink] [raw]

Subject: [PATCH v3 7/8] dm-verity: hash blocks with shash import+finup when possible

From: Eric Biggers <[email protected]>

Currently dm-verity computes the hash of each block by using multiple
calls to the "ahash" crypto API. While the exact sequence depends on
the chosen dm-verity settings, in the vast majority of cases it is:

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

This is inefficient for two main reasons:

- It makes multiple indirect calls, which is expensive on modern CPUs
especially when mitigations for CPU vulnerabilities are enabled.

Since the salt is the same across all blocks on a given dm-verity
device, a much more efficient sequence would be to do an import of the
pre-salted state, then a finup.

- It uses the ahash (asynchronous hash) API, despite the fact that
CPU-based hashing is almost always used in practice, and therefore it
experiences the overhead of the ahash-based wrapper for shash. This
also means that the new function crypto_shash_finup_mb(), which is
specifically designed for fast CPU-based hashing, is unavailable.

Since dm-verity was intentionally converted to ahash to support
off-CPU crypto accelerators, wholesale conversion to shash (reverting
that change) might not be acceptable. Yet, we should still provide a
fast path for shash with the most common dm-verity settings.

Therefore, this patch adds a new shash import+finup based fast path to
dm-verity. It 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.

This makes dm-verity optimized for what the vast majority of users want:
CPU-based hashing with the most common settings, while still retaining
support for rarer settings and off-CPU crypto accelerators.

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.

Signed-off-by: Eric Biggers <[email protected]>
---
drivers/md/dm-verity-fec.c | 13 +-
drivers/md/dm-verity-target.c | 336 ++++++++++++++++++++++++----------
drivers/md/dm-verity.h | 27 ++-
3 files changed, 263 insertions(+), 113 deletions(-)

diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c
index e46aee6f932e..b436b8e4d750 100644
--- a/drivers/md/dm-verity-fec.c
+++ b/drivers/md/dm-verity-fec.c
@@ -184,13 +184,14 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_io *io,
* 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), true)))
+ if (unlikely(verity_compute_hash_virt(v, io, data,
+ 1 << v->data_dev_block_bits,
+ verity_io_real_digest(v, io),
+ true)))
return 0;

return memcmp(verity_io_real_digest(v, io), want_digest,
v->digest_size) != 0;
}
@@ -386,13 +387,13 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io,

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), true);
+ r = verity_compute_hash_virt(v, io, fio->output,
+ 1 << v->data_dev_block_bits,
+ verity_io_real_digest(v, io), true);
if (unlikely(r < 0))
return r;

if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io),
v->digest_size)) {
diff --git a/drivers/md/dm-verity-target.c b/drivers/md/dm-verity-target.c
index bb5da66da4c1..2dd15f5e91b7 100644
--- a/drivers/md/dm-verity-target.c
+++ b/drivers/md/dm-verity-target.c
@@ -44,12 +44,16 @@

static unsigned int dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;

module_param_named(prefetch_cluster, dm_verity_prefetch_cluster, uint, 0644);

+/* Is at least one dm-verity instance using the bh workqueue? */
static DEFINE_STATIC_KEY_FALSE(use_bh_wq_enabled);

+/* Is at least one dm-verity instance using ahash_tfm instead of shash_tfm? */
+static DEFINE_STATIC_KEY_FALSE(ahash_enabled);
+
struct dm_verity_prefetch_work {
struct work_struct work;
struct dm_verity *v;
unsigned short ioprio;
sector_t block;
@@ -100,13 +104,13 @@ static sector_t verity_position_at_level(struct dm_verity *v, sector_t block,
int level)
{
return block >> (level * v->hash_per_block_bits);
}

-static int verity_hash_update(struct dm_verity *v, struct ahash_request *req,
- const u8 *data, size_t len,
- struct crypto_wait *wait)
+static int verity_ahash_update(struct dm_verity *v, struct ahash_request *req,
+ const u8 *data, size_t len,
+ struct crypto_wait *wait)
{
struct scatterlist sg;

if (likely(!is_vmalloc_addr(data))) {
sg_init_one(&sg, data, len);
@@ -133,16 +137,16 @@ static int verity_hash_update(struct dm_verity *v, struct ahash_request *req,
}

/*
* Wrapper for crypto_ahash_init, which handles verity salting.
*/
-static int verity_hash_init(struct dm_verity *v, struct ahash_request *req,
+static int verity_ahash_init(struct dm_verity *v, struct ahash_request *req,
struct crypto_wait *wait, bool may_sleep)
{
int r;

- ahash_request_set_tfm(req, v->tfm);
+ ahash_request_set_tfm(req, v->ahash_tfm);
ahash_request_set_callback(req,
may_sleep ? CRYPTO_TFM_REQ_MAY_SLEEP | CRYPTO_TFM_REQ_MAY_BACKLOG : 0,
crypto_req_done, (void *)wait);
crypto_init_wait(wait);

@@ -153,22 +157,22 @@ static int verity_hash_init(struct dm_verity *v, struct ahash_request *req,
DMERR("crypto_ahash_init failed: %d", r);
return r;
}

if (likely(v->salt_size && (v->version >= 1)))
- r = verity_hash_update(v, req, v->salt, v->salt_size, wait);
+ r = verity_ahash_update(v, req, v->salt, v->salt_size, wait);

return r;
}

-static int verity_hash_final(struct dm_verity *v, struct ahash_request *req,
- u8 *digest, struct crypto_wait *wait)
+static int verity_ahash_final(struct dm_verity *v, struct ahash_request *req,
+ u8 *digest, struct crypto_wait *wait)
{
int r;

if (unlikely(v->salt_size && (!v->version))) {
- r = verity_hash_update(v, req, v->salt, v->salt_size, wait);
+ r = verity_ahash_update(v, req, v->salt, v->salt_size, wait);

if (r < 0) {
DMERR("%s failed updating salt: %d", __func__, r);
goto out;
}
@@ -178,27 +182,47 @@ static int verity_hash_final(struct dm_verity *v, struct ahash_request *req,
r = crypto_wait_req(crypto_ahash_final(req), wait);
out:
return r;
}

-int verity_hash(struct dm_verity *v, struct ahash_request *req,
- const u8 *data, size_t len, u8 *digest, bool may_sleep)
+int verity_compute_hash_virt(struct dm_verity *v, struct dm_verity_io *io,
+ const u8 *data, size_t len, u8 *digest,
+ bool may_sleep)
{
int r;
- struct crypto_wait wait;

- r = verity_hash_init(v, req, &wait, may_sleep);
- if (unlikely(r < 0))
- goto out;
+ if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) {
+ struct ahash_request *req = verity_io_hash_req(v, io);
+ struct crypto_wait wait;

- r = verity_hash_update(v, req, data, len, &wait);
- if (unlikely(r < 0))
- goto out;
+ r = verity_ahash_init(v, req, &wait, may_sleep);
+ if (unlikely(r))
+ goto error;

- r = verity_hash_final(v, req, digest, &wait);
+ r = verity_ahash_update(v, req, data, len, &wait);
+ if (unlikely(r))
+ goto error;

-out:
+ r = verity_ahash_final(v, req, digest, &wait);
+ if (unlikely(r))
+ goto error;
+ } else {
+ struct shash_desc *desc = verity_io_hash_req(v, io);
+
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_import(desc, v->initial_hashstate);
+ if (unlikely(r))
+ goto error;
+
+ r = crypto_shash_finup(desc, data, len, digest);
+ if (unlikely(r))
+ goto error;
+ }
+ return 0;
+
+error:
+ DMERR("Error hashing block from virt buffer: %d", r);
return r;
}

static void verity_hash_at_level(struct dm_verity *v, sector_t block, int level,
sector_t *hash_block, unsigned int *offset)
@@ -323,13 +347,14 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
if (skip_unverified) {
r = 1;
goto release_ret_r;
}

- r = verity_hash(v, verity_io_hash_req(v, io),
- data, 1 << v->hash_dev_block_bits,
- verity_io_real_digest(v, io), !io->in_bh);
+ r = verity_compute_hash_virt(v, io, data,
+ 1 << v->hash_dev_block_bits,
+ verity_io_real_digest(v, io),
+ !io->in_bh);
if (unlikely(r < 0))
goto release_ret_r;

if (likely(memcmp(verity_io_real_digest(v, io), want_digest,
v->digest_size) == 0))
@@ -403,14 +428,17 @@ int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,

return r;
}

/*
- * Calculates the digest for the given bio
+ * Update the ahash_request of @io with the next data block from @iter, and
+ * advance @iter accordingly.
*/
-static int verity_for_io_block(struct dm_verity *v, struct dm_verity_io *io,
- struct bvec_iter *iter, struct crypto_wait *wait)
+static int verity_ahash_update_block(struct dm_verity *v,
+ struct dm_verity_io *io,
+ struct bvec_iter *iter,
+ struct crypto_wait *wait)
{
unsigned int todo = 1 << v->data_dev_block_bits;
struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
struct scatterlist sg;
struct ahash_request *req = verity_io_hash_req(v, io);
@@ -445,10 +473,71 @@ static int verity_for_io_block(struct dm_verity *v, struct dm_verity_io *io,
} while (todo);

return 0;
}

+static int verity_compute_hash(struct dm_verity *v, struct dm_verity_io *io,
+ struct bvec_iter *iter, u8 *digest,
+ bool may_sleep)
+{
+ int r;
+
+ if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) {
+ struct ahash_request *req = verity_io_hash_req(v, io);
+ struct crypto_wait wait;
+
+ r = verity_ahash_init(v, req, &wait, may_sleep);
+ if (unlikely(r))
+ goto error;
+
+ r = verity_ahash_update_block(v, io, iter, &wait);
+ if (unlikely(r))
+ goto error;
+
+ r = verity_ahash_final(v, req, digest, &wait);
+ if (unlikely(r))
+ goto error;
+ } else {
+ struct shash_desc *desc = verity_io_hash_req(v, io);
+ struct bio *bio =
+ dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
+ struct bio_vec bv = bio_iter_iovec(bio, *iter);
+ const unsigned int len = 1 << v->data_dev_block_bits;
+ const void *virt;
+
+ if (unlikely(len > bv.bv_len)) {
+ /*
+ * Data block spans pages. This should not happen,
+ * since this code path is not used if the data block
+ * size is greater than the page size, and all I/O
+ * should be data block aligned because dm-verity sets
+ * logical_block_size to the data block size.
+ */
+ DMERR_LIMIT("unaligned io (data block spans pages)");
+ return -EIO;
+ }
+
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_import(desc, v->initial_hashstate);
+ if (unlikely(r))
+ goto error;
+
+ virt = bvec_kmap_local(&bv);
+ r = crypto_shash_finup(desc, virt, len, digest);
+ kunmap_local(virt);
+ if (unlikely(r))
+ goto error;
+
+ bio_advance_iter(bio, iter, len);
+ }
+ return 0;
+
+error:
+ DMERR("Error hashing block from bio iter: %d", r);
+ return r;
+}
+
/*
* Calls function process for 1 << v->data_dev_block_bits bytes in the bio_vec
* starting from iter.
*/
int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io,
@@ -516,13 +605,12 @@ static noinline int verity_recheck(struct dm_verity *v, struct dm_verity_io *io,
io_loc.count = 1 << (v->data_dev_block_bits - SECTOR_SHIFT);
r = dm_io(&io_req, 1, &io_loc, NULL, IOPRIO_DEFAULT);
if (unlikely(r))
goto free_ret;

- r = verity_hash(v, verity_io_hash_req(v, io), buffer,
- 1 << v->data_dev_block_bits,
- verity_io_real_digest(v, io), true);
+ r = verity_compute_hash_virt(v, io, buffer, 1 << v->data_dev_block_bits,
+ verity_io_real_digest(v, io), true);
if (unlikely(r))
goto free_ret;

if (memcmp(verity_io_real_digest(v, io),
verity_io_want_digest(v, io), v->digest_size)) {
@@ -569,11 +657,10 @@ static int verity_verify_io(struct dm_verity_io *io)
bool is_zero;
struct dm_verity *v = io->v;
struct bvec_iter start;
struct bvec_iter iter_copy;
struct bvec_iter *iter;
- struct crypto_wait wait;
struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
unsigned int b;

if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
/*
@@ -586,11 +673,10 @@ static int verity_verify_io(struct dm_verity_io *io)
iter = &io->iter;

for (b = 0; b < io->n_blocks; b++) {
int r;
sector_t cur_block = io->block + b;
- struct ahash_request *req = verity_io_hash_req(v, io);

if (v->validated_blocks && bio->bi_status == BLK_STS_OK &&
likely(test_bit(cur_block, v->validated_blocks))) {
verity_bv_skip_block(v, io, iter);
continue;
@@ -613,21 +699,14 @@ static int verity_verify_io(struct dm_verity_io *io)
return r;

continue;
}

- r = verity_hash_init(v, req, &wait, !io->in_bh);
- if (unlikely(r < 0))
- return r;
-
start = *iter;
- r = verity_for_io_block(v, io, iter, &wait);
- if (unlikely(r < 0))
- return r;
-
- r = verity_hash_final(v, req, verity_io_real_digest(v, io),
- &wait);
+ r = verity_compute_hash(v, io, iter,
+ verity_io_real_digest(v, io),
+ !io->in_bh);
if (unlikely(r < 0))
return r;

if (likely(memcmp(verity_io_real_digest(v, io),
verity_io_want_digest(v, io), v->digest_size) == 0)) {
@@ -1031,15 +1110,20 @@ static void verity_dtr(struct dm_target *ti)
if (v->bufio)
dm_bufio_client_destroy(v->bufio);

kvfree(v->validated_blocks);
kfree(v->salt);
+ kfree(v->initial_hashstate);
kfree(v->root_digest);
kfree(v->zero_digest);

- if (v->tfm)
- crypto_free_ahash(v->tfm);
+ if (v->ahash_tfm) {
+ static_branch_dec(&ahash_enabled);
+ crypto_free_ahash(v->ahash_tfm);
+ } else {
+ crypto_free_shash(v->shash_tfm);
+ }

kfree(v->alg_name);

if (v->hash_dev)
dm_put_device(ti, v->hash_dev);
@@ -1081,33 +1165,33 @@ static int verity_alloc_most_once(struct dm_verity *v)
}

static int verity_alloc_zero_digest(struct dm_verity *v)
{
int r = -ENOMEM;
- struct ahash_request *req;
+ struct dm_verity_io *io;
u8 *zero_data;

v->zero_digest = kmalloc(v->digest_size, GFP_KERNEL);

if (!v->zero_digest)
return r;

- req = kmalloc(v->ahash_reqsize, GFP_KERNEL);
+ io = kmalloc(sizeof(*io) + v->hash_reqsize, GFP_KERNEL);

- if (!req)
+ if (!io)
return r; /* verity_dtr will free zero_digest */

zero_data = kzalloc(1 << v->data_dev_block_bits, GFP_KERNEL);

if (!zero_data)
goto out;

- r = verity_hash(v, req, zero_data, 1 << v->data_dev_block_bits,
- v->zero_digest, true);
-
+ r = verity_compute_hash_virt(v, io, zero_data,
+ 1 << v->data_dev_block_bits,
+ v->zero_digest, true);
out:
- kfree(req);
+ kfree(io);
kfree(zero_data);

return r;
}

@@ -1224,10 +1308,109 @@ static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
} while (argc && !r);

return r;
}

+static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name)
+{
+ struct dm_target *ti = v->ti;
+ struct crypto_ahash *ahash;
+ struct crypto_shash *shash = NULL;
+ const char *driver_name;
+
+ v->alg_name = kstrdup(alg_name, GFP_KERNEL);
+ if (!v->alg_name) {
+ ti->error = "Cannot allocate algorithm name";
+ return -ENOMEM;
+ }
+
+ ahash = crypto_alloc_ahash(alg_name, 0,
+ v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0);
+ if (IS_ERR(ahash)) {
+ ti->error = "Cannot initialize hash function";
+ return PTR_ERR(ahash);
+ }
+ driver_name = crypto_ahash_driver_name(ahash);
+ if (v->version >= 1 /* salt prepended, not appended? */ &&
+ 1 << v->data_dev_block_bits <= PAGE_SIZE) {
+ shash = crypto_alloc_shash(alg_name, 0, 0);
+ if (!IS_ERR(shash) &&
+ strcmp(crypto_shash_driver_name(shash), driver_name) != 0) {
+ /*
+ * ahash gave a different driver than shash, so probably
+ * this is a case of real hardware offload. Use ahash.
+ */
+ crypto_free_shash(shash);
+ shash = NULL;
+ }
+ }
+ if (!IS_ERR_OR_NULL(shash)) {
+ crypto_free_ahash(ahash);
+ ahash = NULL;
+ v->shash_tfm = shash;
+ v->digest_size = crypto_shash_digestsize(shash);
+ v->hash_reqsize = sizeof(struct shash_desc) +
+ crypto_shash_descsize(shash);
+ DMINFO("%s using shash \"%s\"", alg_name, driver_name);
+ } else {
+ v->ahash_tfm = ahash;
+ static_branch_inc(&ahash_enabled);
+ v->digest_size = crypto_ahash_digestsize(ahash);
+ v->hash_reqsize = sizeof(struct ahash_request) +
+ crypto_ahash_reqsize(ahash);
+ DMINFO("%s using ahash \"%s\"", alg_name, driver_name);
+ }
+ if ((1 << v->hash_dev_block_bits) < v->digest_size * 2) {
+ ti->error = "Digest size too big";
+ return -EINVAL;
+ }
+ return 0;
+}
+
+static int verity_setup_salt_and_hashstate(struct dm_verity *v, const char *arg)
+{
+ struct dm_target *ti = v->ti;
+
+ if (strcmp(arg, "-") != 0) {
+ v->salt_size = strlen(arg) / 2;
+ v->salt = kmalloc(v->salt_size, GFP_KERNEL);
+ if (!v->salt) {
+ ti->error = "Cannot allocate salt";
+ return -ENOMEM;
+ }
+ if (strlen(arg) != v->salt_size * 2 ||
+ hex2bin(v->salt, arg, v->salt_size)) {
+ ti->error = "Invalid salt";
+ return -EINVAL;
+ }
+ }
+ /*
+ * If the "shash with import+finup sequence" method has been selected
+ * (see verity_setup_hash_alg()), then create the initial hash state.
+ */
+ if (v->shash_tfm) {
+ SHASH_DESC_ON_STACK(desc, v->shash_tfm);
+ int r;
+
+ v->initial_hashstate = kmalloc(
+ crypto_shash_statesize(v->shash_tfm), GFP_KERNEL);
+ if (!v->initial_hashstate) {
+ ti->error = "Cannot allocate initial hash state";
+ return -ENOMEM;
+ }
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_init(desc) ?:
+ crypto_shash_update(desc, v->salt, v->salt_size) ?:
+ crypto_shash_export(desc, v->initial_hashstate);
+ if (r) {
+ ti->error = "Cannot set up initial hash state";
+ return r;
+ }
+ }
+ return 0;
+}
+
/*
* Target parameters:
* <version> The current format is version 1.
* Vsn 0 is compatible with original Chromium OS releases.
* <data device>
@@ -1348,42 +1531,13 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv)
r = -EINVAL;
goto bad;
}
v->hash_start = num_ll;

- v->alg_name = kstrdup(argv[7], GFP_KERNEL);
- if (!v->alg_name) {
- ti->error = "Cannot allocate algorithm name";
- r = -ENOMEM;
- goto bad;
- }
-
- v->tfm = crypto_alloc_ahash(v->alg_name, 0,
- v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0);
- if (IS_ERR(v->tfm)) {
- ti->error = "Cannot initialize hash function";
- r = PTR_ERR(v->tfm);
- v->tfm = NULL;
- goto bad;
- }
-
- /*
- * dm-verity performance can vary greatly depending on which hash
- * algorithm implementation is used. Help people debug performance
- * problems by logging the ->cra_driver_name.
- */
- DMINFO("%s using implementation \"%s\"", v->alg_name,
- crypto_hash_alg_common(v->tfm)->base.cra_driver_name);
-
- v->digest_size = crypto_ahash_digestsize(v->tfm);
- if ((1 << v->hash_dev_block_bits) < v->digest_size * 2) {
- ti->error = "Digest size too big";
- r = -EINVAL;
+ r = verity_setup_hash_alg(v, argv[7]);
+ if (r)
goto bad;
- }
- v->ahash_reqsize = sizeof(struct ahash_request) +
- crypto_ahash_reqsize(v->tfm);

v->root_digest = kmalloc(v->digest_size, GFP_KERNEL);
if (!v->root_digest) {
ti->error = "Cannot allocate root digest";
r = -ENOMEM;
@@ -1395,25 +1549,13 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv)
r = -EINVAL;
goto bad;
}
root_hash_digest_to_validate = argv[8];

- if (strcmp(argv[9], "-")) {
- v->salt_size = strlen(argv[9]) / 2;
- v->salt = kmalloc(v->salt_size, GFP_KERNEL);
- if (!v->salt) {
- ti->error = "Cannot allocate salt";
- r = -ENOMEM;
- goto bad;
- }
- if (strlen(argv[9]) != v->salt_size * 2 ||
- hex2bin(v->salt, argv[9], v->salt_size)) {
- ti->error = "Invalid salt";
- r = -EINVAL;
- goto bad;
- }
- }
+ r = verity_setup_salt_and_hashstate(v, argv[9]);
+ if (r)
+ goto bad;

argv += 10;
argc -= 10;

/* Optional parameters */
@@ -1512,11 +1654,11 @@ static int verity_ctr(struct dm_target *ti, unsigned int argc, char **argv)
r = -ENOMEM;
goto bad;
}

ti->per_io_data_size = sizeof(struct dm_verity_io) +
- v->ahash_reqsize + v->digest_size * 2;
+ v->hash_reqsize + v->digest_size * 2;

r = verity_fec_ctr(v);
if (r)
goto bad;

diff --git a/drivers/md/dm-verity.h b/drivers/md/dm-verity.h
index 20b1bcf03474..15ffb0881cc9 100644
--- a/drivers/md/dm-verity.h
+++ b/drivers/md/dm-verity.h
@@ -37,13 +37,15 @@ 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 */
@@ -54,11 +56,11 @@ struct dm_verity {
unsigned char levels; /* the number of tree levels */
unsigned char version;
bool hash_failed:1; /* set if hash of any block failed */
bool use_bh_wq:1; /* try to verify in BH wq before normal 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;

@@ -92,45 +94,50 @@ struct dm_verity_io {
char *recheck_buffer;

/*
* 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;
}

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, bool may_sleep);
+extern int verity_compute_hash_virt(struct dm_verity *v,
+ struct dm_verity_io *io,
+ const u8 *data, size_t len, u8 *digest,
+ bool may_sleep);

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);
--
2.45.0

2024-05-07 00:26:02

by Eric Biggers

[permalink] [raw]

Subject: [PATCH v3 8/8] dm-verity: improve performance by using multibuffer hashing

From: Eric Biggers <[email protected]>

When supported by the hash algorithm, use crypto_shash_finup_mb() to
interleave the hashing of pairs of data blocks. On some CPUs this
nearly doubles hashing performance. The increase in overall throughput
of cold-cache dm-verity reads that I'm seeing on arm64 and x86_64 is
roughly 35% (though this metric is hard to measure as it jumps around a
lot).

For now this is only done on data blocks, not Merkle tree blocks. We
could use finup_mb on Merkle tree blocks too, but that is less important
as there aren't as many Merkle tree blocks as data blocks, and that
would require some additional code restructuring.

Signed-off-by: Eric Biggers <[email protected]>
---
drivers/md/dm-verity-fec.c | 24 +--
drivers/md/dm-verity-fec.h | 7 +-
drivers/md/dm-verity-target.c | 363 +++++++++++++++++++++++-----------
drivers/md/dm-verity.h | 28 +--
4 files changed, 264 insertions(+), 158 deletions(-)

diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c
index b436b8e4d750..c1677137a682 100644
--- a/drivers/md/dm-verity-fec.c
+++ b/drivers/md/dm-verity-fec.c
@@ -184,18 +184,18 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_io *io,
* 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)
{
+ u8 real_digest[HASH_MAX_DIGESTSIZE];
+
if (unlikely(verity_compute_hash_virt(v, io, data,
1 << v->data_dev_block_bits,
- verity_io_real_digest(v, io),
- true)))
+ real_digest, true)))
return 0;

- return memcmp(verity_io_real_digest(v, io), want_digest,
- v->digest_size) != 0;
+ return memcmp(real_digest, 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.
@@ -362,14 +362,15 @@ static void fec_init_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio)
* (indicated by @offset) in fio->output. If @use_erasures is non-zero, uses
* hashes to locate erasures.
*/
static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io,
struct dm_verity_fec_io *fio, u64 rsb, u64 offset,
- bool use_erasures)
+ const u8 *want_digest, bool use_erasures)
{
int r, neras = 0;
unsigned int pos;
+ u8 real_digest[HASH_MAX_DIGESTSIZE];

r = fec_alloc_bufs(v, fio);
if (unlikely(r < 0))
return r;

@@ -389,16 +390,15 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io,
}

/* Always re-validate the corrected block against the expected hash */
r = verity_compute_hash_virt(v, io, fio->output,
1 << v->data_dev_block_bits,
- verity_io_real_digest(v, io), true);
+ real_digest, true);
if (unlikely(r < 0))
return r;

- if (memcmp(verity_io_real_digest(v, io), verity_io_want_digest(v, io),
- v->digest_size)) {
+ if (memcmp(real_digest, want_digest, v->digest_size)) {
DMERR_LIMIT("%s: FEC %llu: failed to correct (%d erasures)",
v->data_dev->name, (unsigned long long)rsb, neras);
return -EILSEQ;
}

@@ -419,12 +419,12 @@ static int fec_bv_copy(struct dm_verity *v, struct dm_verity_io *io, u8 *data,
/*
* Correct errors in a block. Copies corrected block to dest if non-NULL,
* otherwise to a bio_vec starting from iter.
*/
int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io,
- enum verity_block_type type, sector_t block, u8 *dest,
- struct bvec_iter *iter)
+ enum verity_block_type type, sector_t block,
+ const u8 *want_digest, u8 *dest, struct bvec_iter *iter)
{
int r;
struct dm_verity_fec_io *fio = fec_io(io);
u64 offset, res, rsb;

@@ -463,13 +463,13 @@ int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io,
/*
* Locating erasures is slow, so attempt to recover the block without
* them first. Do a second attempt with erasures if the corruption is
* bad enough.
*/
- r = fec_decode_rsb(v, io, fio, rsb, offset, false);
+ r = fec_decode_rsb(v, io, fio, rsb, offset, want_digest, false);
if (r < 0) {
- r = fec_decode_rsb(v, io, fio, rsb, offset, true);
+ r = fec_decode_rsb(v, io, fio, rsb, offset, want_digest, true);
if (r < 0)
goto done;
}

if (dest)
diff --git a/drivers/md/dm-verity-fec.h b/drivers/md/dm-verity-fec.h
index 8454070d2824..57c3f674cae9 100644
--- a/drivers/md/dm-verity-fec.h
+++ b/drivers/md/dm-verity-fec.h
@@ -68,11 +68,12 @@ struct dm_verity_fec_io {

extern bool verity_fec_is_enabled(struct dm_verity *v);

extern int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io,
enum verity_block_type type, sector_t block,
- u8 *dest, struct bvec_iter *iter);
+ const u8 *want_digest, u8 *dest,
+ struct bvec_iter *iter);

extern unsigned int verity_fec_status_table(struct dm_verity *v, unsigned int sz,
char *result, unsigned int maxlen);

extern void verity_fec_finish_io(struct dm_verity_io *io);
@@ -97,12 +98,12 @@ static inline bool verity_fec_is_enabled(struct dm_verity *v)
return false;
}

static inline int verity_fec_decode(struct dm_verity *v,
struct dm_verity_io *io,
- enum verity_block_type type,
- sector_t block, u8 *dest,
+ enum verity_block_type type, sector_t block,
+ const u8 *want_digest, u8 *dest,
struct bvec_iter *iter)
{
return -EOPNOTSUPP;
}

diff --git a/drivers/md/dm-verity-target.c b/drivers/md/dm-verity-target.c
index 2dd15f5e91b7..d367198aefe7 100644
--- a/drivers/md/dm-verity-target.c
+++ b/drivers/md/dm-verity-target.c
@@ -300,16 +300,16 @@ static int verity_handle_err(struct dm_verity *v, enum verity_block_type type,

/*
* Verify hash of a metadata block pertaining to the specified data block
* ("block" argument) at a specified level ("level" argument).
*
- * On successful return, verity_io_want_digest(v, io) contains the hash value
- * for a lower tree level or for the data block (if we're at the lowest level).
+ * On successful return, want_digest contains the hash value for a lower tree
+ * level or for the data block (if we're at the lowest level).
*
* If "skip_unverified" is true, unverified buffer is skipped and 1 is returned.
* If "skip_unverified" is false, unverified buffer is hashed and verified
- * against current value of verity_io_want_digest(v, io).
+ * against current value of want_digest.
*/
static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
sector_t block, int level, bool skip_unverified,
u8 *want_digest)
{
@@ -318,10 +318,11 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
u8 *data;
int r;
sector_t hash_block;
unsigned int offset;
struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
+ u8 real_digest[HASH_MAX_DIGESTSIZE];

verity_hash_at_level(v, block, level, &hash_block, &offset);

if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
data = dm_bufio_get(v->bufio, hash_block, &buf);
@@ -349,27 +350,26 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
goto release_ret_r;
}

r = verity_compute_hash_virt(v, io, data,
1 << v->hash_dev_block_bits,
- verity_io_real_digest(v, io),
- !io->in_bh);
+ real_digest, !io->in_bh);
if (unlikely(r < 0))
goto release_ret_r;

- if (likely(memcmp(verity_io_real_digest(v, io), want_digest,
- v->digest_size) == 0))
+ if (likely(!memcmp(real_digest, want_digest, v->digest_size)))
aux->hash_verified = 1;
else if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
/*
* Error handling code (FEC included) cannot be run in a
* tasklet since it may sleep, so fallback to work-queue.
*/
r = -EAGAIN;
goto release_ret_r;
} else if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_METADATA,
- hash_block, data, NULL) == 0)
+ hash_block, want_digest,
+ data, NULL) == 0)
aux->hash_verified = 1;
else if (verity_handle_err(v,
DM_VERITY_BLOCK_TYPE_METADATA,
hash_block)) {
struct bio *bio =
@@ -473,71 +473,10 @@ static int verity_ahash_update_block(struct dm_verity *v,
} while (todo);

return 0;
}

-static int verity_compute_hash(struct dm_verity *v, struct dm_verity_io *io,
- struct bvec_iter *iter, u8 *digest,
- bool may_sleep)
-{
- int r;
-
- if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) {
- struct ahash_request *req = verity_io_hash_req(v, io);
- struct crypto_wait wait;
-
- r = verity_ahash_init(v, req, &wait, may_sleep);
- if (unlikely(r))
- goto error;
-
- r = verity_ahash_update_block(v, io, iter, &wait);
- if (unlikely(r))
- goto error;
-
- r = verity_ahash_final(v, req, digest, &wait);
- if (unlikely(r))
- goto error;
- } else {
- struct shash_desc *desc = verity_io_hash_req(v, io);
- struct bio *bio =
- dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
- struct bio_vec bv = bio_iter_iovec(bio, *iter);
- const unsigned int len = 1 << v->data_dev_block_bits;
- const void *virt;
-
- if (unlikely(len > bv.bv_len)) {
- /*
- * Data block spans pages. This should not happen,
- * since this code path is not used if the data block
- * size is greater than the page size, and all I/O
- * should be data block aligned because dm-verity sets
- * logical_block_size to the data block size.
- */
- DMERR_LIMIT("unaligned io (data block spans pages)");
- return -EIO;
- }
-
- desc->tfm = v->shash_tfm;
- r = crypto_shash_import(desc, v->initial_hashstate);
- if (unlikely(r))
- goto error;
-
- virt = bvec_kmap_local(&bv);
- r = crypto_shash_finup(desc, virt, len, digest);
- kunmap_local(virt);
- if (unlikely(r))
- goto error;
-
- bio_advance_iter(bio, iter, len);
- }
- return 0;
-
-error:
- DMERR("Error hashing block from bio iter: %d", r);
- return r;
-}
-
/*
* Calls function process for 1 << v->data_dev_block_bits bytes in the bio_vec
* starting from iter.
*/
int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io,
@@ -581,41 +520,42 @@ static int verity_recheck_copy(struct dm_verity *v, struct dm_verity_io *io,
io->recheck_buffer += len;

return 0;
}

-static noinline int verity_recheck(struct dm_verity *v, struct dm_verity_io *io,
- struct bvec_iter start, sector_t cur_block)
+static int verity_recheck(struct dm_verity *v, struct dm_verity_io *io,
+ struct bvec_iter start, sector_t blkno,
+ const u8 *want_digest)
{
struct page *page;
void *buffer;
int r;
struct dm_io_request io_req;
struct dm_io_region io_loc;
+ u8 real_digest[HASH_MAX_DIGESTSIZE];

page = mempool_alloc(&v->recheck_pool, GFP_NOIO);
buffer = page_to_virt(page);

io_req.bi_opf = REQ_OP_READ;
io_req.mem.type = DM_IO_KMEM;
io_req.mem.ptr.addr = buffer;
io_req.notify.fn = NULL;
io_req.client = v->io;
io_loc.bdev = v->data_dev->bdev;
- io_loc.sector = cur_block << (v->data_dev_block_bits - SECTOR_SHIFT);
+ io_loc.sector = blkno << (v->data_dev_block_bits - SECTOR_SHIFT);
io_loc.count = 1 << (v->data_dev_block_bits - SECTOR_SHIFT);
r = dm_io(&io_req, 1, &io_loc, NULL, IOPRIO_DEFAULT);
if (unlikely(r))
goto free_ret;

r = verity_compute_hash_virt(v, io, buffer, 1 << v->data_dev_block_bits,
- verity_io_real_digest(v, io), true);
+ real_digest, true);
if (unlikely(r))
goto free_ret;

- if (memcmp(verity_io_real_digest(v, io),
- verity_io_want_digest(v, io), v->digest_size)) {
+ if (memcmp(real_digest, want_digest, v->digest_size)) {
r = -EIO;
goto free_ret;
}

io->recheck_buffer = buffer;
@@ -647,22 +587,84 @@ static inline void verity_bv_skip_block(struct dm_verity *v,
struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);

bio_advance_iter(bio, iter, 1 << v->data_dev_block_bits);
}

+static noinline int
+__verity_handle_data_hash_mismatch(struct dm_verity *v, struct dm_verity_io *io,
+ struct bio *bio, struct bvec_iter *start,
+ sector_t blkno, const u8 *want_digest)
+{
+ if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
+ /*
+ * Error handling code (FEC included) cannot be run in the
+ * BH workqueue, so fallback to a standard workqueue.
+ */
+ return -EAGAIN;
+ }
+ if (verity_recheck(v, io, *start, blkno, want_digest) == 0) {
+ if (v->validated_blocks)
+ set_bit(blkno, v->validated_blocks);
+ return 0;
+ }
+#if defined(CONFIG_DM_VERITY_FEC)
+ if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_DATA, blkno,
+ want_digest, NULL, start) == 0)
+ return 0;
+#endif
+ if (bio->bi_status)
+ return -EIO; /* Error correction failed; Just return error */
+
+ if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_DATA, blkno)) {
+ dm_audit_log_bio(DM_MSG_PREFIX, "verify-data", bio, blkno, 0);
+ return -EIO;
+ }
+ return 0;
+}
+
+static __always_inline int
+verity_check_data_block_hash(struct dm_verity *v, struct dm_verity_io *io,
+ struct bio *bio, struct bvec_iter *start,
+ sector_t blkno,
+ const u8 *real_digest, const u8 *want_digest)
+{
+ if (likely(memcmp(real_digest, want_digest, v->digest_size) == 0)) {
+ if (v->validated_blocks)
+ set_bit(blkno, v->validated_blocks);
+ return 0;
+ }
+ return __verity_handle_data_hash_mismatch(v, io, bio, start, blkno,
+ want_digest);
+}
+
/*
* Verify one "dm_verity_io" structure.
*/
static int verity_verify_io(struct dm_verity_io *io)
{
- bool is_zero;
struct dm_verity *v = io->v;
+ const unsigned int block_size = 1 << v->data_dev_block_bits;
+ struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
+ u8 want_digest[HASH_MAX_DIGESTSIZE];
+ u8 real_digest[HASH_MAX_DIGESTSIZE];
struct bvec_iter start;
struct bvec_iter iter_copy;
struct bvec_iter *iter;
- struct bio *bio = dm_bio_from_per_bio_data(io, v->ti->per_io_data_size);
+ /*
+ * The pending_* variables are used when the selected hash algorithm
+ * supports multibuffer hashing. They're used to temporarily store the
+ * virtual address and position of a mapped data block that needs to be
+ * verified. If we then see another data block, we hash the two blocks
+ * simultaneously using the fast multibuffer hashing method.
+ */
+ const void *pending_data = NULL;
+ sector_t pending_blkno;
+ struct bvec_iter pending_start;
+ u8 pending_want_digest[HASH_MAX_DIGESTSIZE];
+ u8 pending_real_digest[HASH_MAX_DIGESTSIZE];
unsigned int b;
+ int r;

if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
/*
* Copy the iterator in case we need to restart
* verification in a work-queue.
@@ -671,82 +673,177 @@ static int verity_verify_io(struct dm_verity_io *io)
iter = &iter_copy;
} else
iter = &io->iter;

for (b = 0; b < io->n_blocks; b++) {
- int r;
- sector_t cur_block = io->block + b;
+ sector_t blkno = io->block + b;
+ bool is_zero;

if (v->validated_blocks && bio->bi_status == BLK_STS_OK &&
- likely(test_bit(cur_block, v->validated_blocks))) {
+ likely(test_bit(blkno, v->validated_blocks))) {
verity_bv_skip_block(v, io, iter);
continue;
}

- r = verity_hash_for_block(v, io, cur_block,
- verity_io_want_digest(v, io),
- &is_zero);
+ r = verity_hash_for_block(v, io, blkno, want_digest, &is_zero);
if (unlikely(r < 0))
- return r;
+ goto error;

if (is_zero) {
/*
* If we expect a zero block, don't validate, just
* return zeros.
*/
r = verity_for_bv_block(v, io, iter,
verity_bv_zero);
if (unlikely(r < 0))
- return r;
+ goto error;

continue;
}

start = *iter;
- r = verity_compute_hash(v, io, iter,
- verity_io_real_digest(v, io),
- !io->in_bh);
- if (unlikely(r < 0))
- return r;
-
- if (likely(memcmp(verity_io_real_digest(v, io),
- verity_io_want_digest(v, io), v->digest_size) == 0)) {
- if (v->validated_blocks)
- set_bit(cur_block, v->validated_blocks);
- continue;
- } else if (static_branch_unlikely(&use_bh_wq_enabled) && io->in_bh) {
- /*
- * Error handling code (FEC included) cannot be run in a
- * tasklet since it may sleep, so fallback to work-queue.
- */
- return -EAGAIN;
- } else if (verity_recheck(v, io, start, cur_block) == 0) {
- if (v->validated_blocks)
- set_bit(cur_block, v->validated_blocks);
- continue;
-#if defined(CONFIG_DM_VERITY_FEC)
- } else if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_DATA,
- cur_block, NULL, &start) == 0) {
- continue;
-#endif
+ if (static_branch_unlikely(&ahash_enabled) && !v->shash_tfm) {
+ /* Hash and verify one data block using ahash. */
+ struct ahash_request *req = verity_io_hash_req(v, io);
+ struct crypto_wait wait;
+
+ r = verity_ahash_init(v, req, &wait, !io->in_bh);
+ if (unlikely(r))
+ goto hash_error;
+
+ r = verity_ahash_update_block(v, io, iter, &wait);
+ if (unlikely(r))
+ goto hash_error;
+
+ r = verity_ahash_final(v, req, real_digest, &wait);
+ if (unlikely(r))
+ goto hash_error;
+
+ r = verity_check_data_block_hash(v, io, bio, &start,
+ blkno, real_digest,
+ want_digest);
+ if (unlikely(r))
+ goto error;
} else {
- if (bio->bi_status) {
+ struct shash_desc *desc = verity_io_hash_req(v, io);
+ struct bio_vec bv = bio_iter_iovec(bio, *iter);
+ const void *data;
+
+ if (unlikely(bv.bv_len < block_size)) {
/*
- * Error correction failed; Just return error
+ * Data block spans pages. This should not
+ * happen, since this code path is not used if
+ * the data block size is greater than the page
+ * size, and all I/O should be data block
+ * aligned because dm-verity sets
+ * logical_block_size to the data block size.
*/
- return -EIO;
+ DMERR_LIMIT("unaligned io (data block spans pages)");
+ r = -EIO;
+ goto error;
}
- if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_DATA,
- cur_block)) {
- dm_audit_log_bio(DM_MSG_PREFIX, "verify-data",
- bio, cur_block, 0);
- return -EIO;
+
+ data = bvec_kmap_local(&bv);
+
+ if (v->use_finup_mb) {
+ if (pending_data) {
+ const u8 *datas[2] = { pending_data,
+ data };
+ u8 *outs[2] = { pending_real_digest,
+ real_digest };
+ /* Hash and verify two data blocks. */
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_import(desc,
+ v->initial_hashstate) ?:
+ crypto_shash_finup_mb(desc,
+ datas,
+ block_size,
+ outs,
+ 2);
+ kunmap_local(data);
+ kunmap_local(pending_data);
+ pending_data = NULL;
+ if (unlikely(r))
+ goto hash_error;
+ r = verity_check_data_block_hash(
+ v, io, bio,
+ &pending_start,
+ pending_blkno,
+ pending_real_digest,
+ pending_want_digest);
+ if (unlikely(r))
+ goto error;
+ r = verity_check_data_block_hash(
+ v, io, bio,
+ &start,
+ blkno,
+ real_digest,
+ want_digest);
+ if (unlikely(r))
+ goto error;
+ } else {
+ /* Wait and see if there's another block. */
+ pending_data = data;
+ pending_blkno = blkno;
+ pending_start = start;
+ memcpy(pending_want_digest, want_digest,
+ v->digest_size);
+ }
+ } else {
+ /* Hash and verify one data block. */
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_import(desc,
+ v->initial_hashstate) ?:
+ crypto_shash_finup(desc, data, block_size,
+ real_digest);
+ kunmap_local(data);
+ if (unlikely(r))
+ goto hash_error;
+ r = verity_check_data_block_hash(
+ v, io, bio, &start, blkno,
+ real_digest, want_digest);
+ if (unlikely(r))
+ goto error;
}
+
+ bio_advance_iter(bio, iter, block_size);
}
}

+ if (pending_data) {
+ /*
+ * Multibuffer hashing is enabled but there was an odd number of
+ * data blocks. Hash and verify the last block by itself.
+ */
+ struct shash_desc *desc = verity_io_hash_req(v, io);
+
+ desc->tfm = v->shash_tfm;
+ r = crypto_shash_import(desc, v->initial_hashstate) ?:
+ crypto_shash_finup(desc, pending_data, block_size,
+ pending_real_digest);
+ kunmap_local(pending_data);
+ pending_data = NULL;
+ if (unlikely(r))
+ goto hash_error;
+ r = verity_check_data_block_hash(v, io, bio,
+ &pending_start,
+ pending_blkno,
+ pending_real_digest,
+ pending_want_digest);
+ if (unlikely(r))
+ goto error;
+ }
+
return 0;
+
+hash_error:
+ DMERR("Error hashing block from bio iter: %d", r);
+error:
+ if (pending_data)
+ kunmap_local(pending_data);
+ return r;
}

/*
* Skip verity work in response to I/O error when system is shutting down.
*/
@@ -1321,10 +1418,34 @@ static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name)
if (!v->alg_name) {
ti->error = "Cannot allocate algorithm name";
return -ENOMEM;
}

+ /*
+ * Allocate the hash transformation object that this dm-verity instance
+ * will use. We have a choice of two APIs: shash and ahash. Most
+ * dm-verity users use CPU-based hashing, and for this shash is optimal
+ * since it matches the underlying algorithm implementations and also
+ * allows the use of fast multibuffer hashing (crypto_shash_finup_mb()).
+ * ahash adds support for off-CPU hash offloading. It also provides
+ * access to shash algorithms, but does so less efficiently.
+ *
+ * Meanwhile, hashing a block in dm-verity in general requires an
+ * init+update+final sequence with multiple updates. However, usually
+ * the salt is prepended to the block rather than appended, and the data
+ * block size is not greater than the page size. In this very common
+ * case, the sequence can be optimized to import+finup, where the first
+ * step imports the pre-computed state after init+update(salt). This
+ * can reduce the crypto API overhead significantly.
+ *
+ * To provide optimal performance for the vast majority of dm-verity
+ * users while still supporting off-CPU hash offloading and the rarer
+ * dm-verity settings, we therefore have two code paths: one using shash
+ * where we use import+finup or import+finup_mb, and one using ahash
+ * where we use init+update(s)+final. We use the former code path when
+ * it's possible to use and shash gives the same algorithm as ahash.
+ */
ahash = crypto_alloc_ahash(alg_name, 0,
v->use_bh_wq ? CRYPTO_ALG_ASYNC : 0);
if (IS_ERR(ahash)) {
ti->error = "Cannot initialize hash function";
return PTR_ERR(ahash);
@@ -1345,14 +1466,16 @@ static int verity_setup_hash_alg(struct dm_verity *v, const char *alg_name)
}
if (!IS_ERR_OR_NULL(shash)) {
crypto_free_ahash(ahash);
ahash = NULL;
v->shash_tfm = shash;
+ v->use_finup_mb = crypto_shash_mb_max_msgs(shash);
v->digest_size = crypto_shash_digestsize(shash);
v->hash_reqsize = sizeof(struct shash_desc) +
crypto_shash_descsize(shash);
- DMINFO("%s using shash \"%s\"", alg_name, driver_name);
+ DMINFO("%s using shash \"%s\"%s", alg_name, driver_name,
+ v->use_finup_mb ? " (multibuffer)" : "");
} else {
v->ahash_tfm = ahash;
static_branch_inc(&ahash_enabled);
v->digest_size = crypto_ahash_digestsize(ahash);
v->hash_reqsize = sizeof(struct ahash_request) +
diff --git a/drivers/md/dm-verity.h b/drivers/md/dm-verity.h
index 15ffb0881cc9..d5f659e1bdef 100644
--- a/drivers/md/dm-verity.h
+++ b/drivers/md/dm-verity.h
@@ -55,10 +55,11 @@ struct dm_verity {
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_bh_wq:1; /* try to verify in BH wq before normal work-queue */
+ bool use_finup_mb:1; /* use crypto_shash_finup_mb() */
unsigned int digest_size; /* digest size for the current hash algorithm */
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 */

@@ -92,42 +93,23 @@ struct dm_verity_io {
struct work_struct bh_work;

char *recheck_buffer;

/*
- * Three variably-size fields follow this struct:
- *
- * 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.
+ * This struct is followed by a variable-sized hash request of size
+ * v->hash_reqsize, either a struct ahash_request or a struct shash_desc
+ * (depending on whether ahash_tfm or shash_tfm is being used). To
+ * access it, use verity_io_hash_req().
*/
};

static inline void *verity_io_hash_req(struct dm_verity *v,
struct dm_verity_io *io)
{
return io + 1;
}

-static inline u8 *verity_io_real_digest(struct dm_verity *v,
- struct dm_verity_io *io)
-{
- 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->hash_reqsize + 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));
--
2.45.0

2024-05-31 06:13:56

by Eric Biggers

[permalink] [raw]

Subject: Re: [PATCH v3 6/8] fsverity: improve performance by using multibuffer hashing

On Fri, May 31, 2024 at 12:50:20PM +0800, Herbert Xu wrote:
> Eric Biggers <[email protected]> wrote:
> >
> > + if (multibuffer) {
> > + if (ctx->pending_data) {
> > + /* Hash and verify two data blocks. */
> > + err = fsverity_hash_2_blocks(params,
> > + inode,
> > + ctx->pending_data,
> > + data,
> > + ctx->hash1,
> > + ctx->hash2);
> > + kunmap_local(data);
> > + kunmap_local(ctx->pending_data);
> > + ctx->pending_data = NULL;
> > + if (err != 0 ||
> > + !verify_data_block(inode, vi, ctx->hash1,
> > + ctx->pending_pos,
> > + ctx->max_ra_pages) ||
> > + !verify_data_block(inode, vi, ctx->hash2,
> > + pos, ctx->max_ra_pages))
> > + return false;
> > + } else {
> > + /* Wait and see if there's another block. */
> > + ctx->pending_data = data;
> > + ctx->pending_pos = pos;
> > + }
> > + } else {
> > + /* Hash and verify one data block. */
> > + err = fsverity_hash_block(params, inode, data,
> > + ctx->hash1);
> > + kunmap_local(data);
> > + if (err != 0 ||
> > + !verify_data_block(inode, vi, ctx->hash1,
> > + pos, ctx->max_ra_pages))
> > + return false;
> > + }
> > + pos += block_size;
>
> I think this complexity is gross. Look at how we did GSO in
> networking. There should be a unified code-path for aggregated
> data and simple data, not an aggregated path versus a simple path.
>
> I think ultimately it stems from the fact that this code went from
> ahash to shash. What were the issues back then? If it's just vmalloc
> we should fix ahash to support that, rather than making users of the
> Crypto API go through contortions like this.

It can't be asynchronous, period. As I've explained, that would be far too
complex, and it would also defeat the purpose because it would make performance
worse. Messages *must* be queued up and hashed in the caller's context.

What could make sense would be some helper functions and an associated struct
for queueing up messages for a particular crypto_shash, up to its mb_max_msgs
value, and then flushing them and retrieving the digests. These would be
provided by the crypto API.

I think this would address your concern, in that the users (fsverity and
dm-verity) would have a unified code path for multiple vs. single blocks.

I didn't think it would be worthwhile to go there yet, given that fsverity and
dm-verity just want 2x or 1x, and it ends up being simpler and more efficient to
handle those cases directly. But we could go with the more general queueing
helper functions instead if you feel they should be included from the start.

- Eric

2024-05-31 06:53:06

by Eric Biggers

[permalink] [raw]

Subject: Re: [PATCH v3 6/8] fsverity: improve performance by using multibuffer hashing

On Thu, May 30, 2024 at 11:13:48PM -0700, Eric Biggers wrote:
> On Fri, May 31, 2024 at 12:50:20PM +0800, Herbert Xu wrote:
> > Eric Biggers <[email protected]> wrote:
> > >
> > > + if (multibuffer) {
> > > + if (ctx->pending_data) {
> > > + /* Hash and verify two data blocks. */
> > > + err = fsverity_hash_2_blocks(params,
> > > + inode,
> > > + ctx->pending_data,
> > > + data,
> > > + ctx->hash1,
> > > + ctx->hash2);
> > > + kunmap_local(data);
> > > + kunmap_local(ctx->pending_data);
> > > + ctx->pending_data = NULL;
> > > + if (err != 0 ||
> > > + !verify_data_block(inode, vi, ctx->hash1,
> > > + ctx->pending_pos,
> > > + ctx->max_ra_pages) ||
> > > + !verify_data_block(inode, vi, ctx->hash2,
> > > + pos, ctx->max_ra_pages))
> > > + return false;
> > > + } else {
> > > + /* Wait and see if there's another block. */
> > > + ctx->pending_data = data;
> > > + ctx->pending_pos = pos;
> > > + }
> > > + } else {
> > > + /* Hash and verify one data block. */
> > > + err = fsverity_hash_block(params, inode, data,
> > > + ctx->hash1);
> > > + kunmap_local(data);
> > > + if (err != 0 ||
> > > + !verify_data_block(inode, vi, ctx->hash1,
> > > + pos, ctx->max_ra_pages))
> > > + return false;
> > > + }
> > > + pos += block_size;
> >
> > I think this complexity is gross. Look at how we did GSO in
> > networking. There should be a unified code-path for aggregated
> > data and simple data, not an aggregated path versus a simple path.
> >
> > I think ultimately it stems from the fact that this code went from
> > ahash to shash. What were the issues back then? If it's just vmalloc
> > we should fix ahash to support that, rather than making users of the
> > Crypto API go through contortions like this.
>
> It can't be asynchronous, period. As I've explained, that would be far too
> complex, and it would also defeat the purpose because it would make performance
> worse. Messages *must* be queued up and hashed in the caller's context.
>
> What could make sense would be some helper functions and an associated struct
> for queueing up messages for a particular crypto_shash, up to its mb_max_msgs
> value, and then flushing them and retrieving the digests. These would be
> provided by the crypto API.
>
> I think this would address your concern, in that the users (fsverity and
> dm-verity) would have a unified code path for multiple vs. single blocks.
>
> I didn't think it would be worthwhile to go there yet, given that fsverity and
> dm-verity just want 2x or 1x, and it ends up being simpler and more efficient to
> handle those cases directly. But we could go with the more general queueing
> helper functions instead if you feel they should be included from the start.
>

Looking at it again a bit more closely, both fsverity and dm-verity have
per-block information that they need to keep track of in the queue in addition
to the data buffers and hashes: the block number, and in dm-verity's case also a
bvec_iter pointing to that block.

So I think it really does make sense to have them both handle the queueing
themselves, and not have it split between them and some crypto API helper
functions (i.e. two queues that mirror each other).

It would be possible, though, to organize the code in dm-verity and fsverity to
represent the queue as an array and operate on it as such. That would also
address your concern about the two code paths. Again, things would end up being
a bit less efficient than my more optimized code that handles 1x and 2x (which
is all that's actually needed for now) specifically, but it would work, I think.

- Eric

2024-05-31 18:51:36

by Eric Biggers

[permalink] [raw]

Subject: Re: [PATCH v3 6/8] fsverity: improve performance by using multibuffer hashing

On Fri, May 31, 2024 at 04:49:28PM +0800, Herbert Xu wrote:
> On Thu, May 30, 2024 at 11:52:58PM -0700, Eric Biggers wrote:
> >
> > Looking at it again a bit more closely, both fsverity and dm-verity have
> > per-block information that they need to keep track of in the queue in addition
> > to the data buffers and hashes: the block number, and in dm-verity's case also a
> > bvec_iter pointing to that block.
>
> Again I'm not asking you to make this API asynchronous at all.

What exactly are you suggesting, then? It seems that you want multibuffer
hashing to be supported by the existing ahash API. However, that only works if
it's made asynchronous, given how the messages would have to be queued up on a
global queue. That has a huge number of issues which I've already explained.
(And it was even tried before, and it failed.)

> I was just commenting on the added complexity in fsverify due to
> the use of the linear shash API instead of the page-based ahash API.

It's the other way around. The shash version is much simpler. Just look at the
diff of commit 8fcd94add6c5 that changed from ahash to shash:

4 files changed, 71 insertions(+), 200 deletions(-)

> This complexity was then compounded by the multi-buffer support.

fsverity and dm-verity will have to be updated to use multibuffer hashing
anyway, given that transparently supporting it in the existing API is not
viable. If your concern is that in my current patchset fsverity and dm-verity
have separate code paths for multibuffer vs. single-buffer, as I mentioned I can
address that by restructuring them to operate on arrays (similar to what I
already did with the crypto API part).

> I think this would look a lot simpler if it moved back to ahash.
>
> The original commit mentioned that ahash was bad for fsverify
> because of vmalloc. But the only use of linear pointers in fsverify
> seems to be from kmalloc. Where is the vmalloc coming from?

XFS is working on adding support for fsverity, and XFS was planning to provide
their Merkle tree blocks in vmalloced buffers. Their plans have shifted several
times, and I think their latest plan no longer uses vmalloced buffers. But in
any case it's still very convenient and much simpler to be able to just use
virtual addresses without having to worry about what type of memory it is.

- Eric

2024-06-03 18:50:09

by Eric Biggers

[permalink] [raw]

Subject: Re: [PATCH v3 6/8] fsverity: improve performance by using multibuffer hashing

On Fri, May 31, 2024 at 11:51:26AM -0700, Eric Biggers wrote:
> On Fri, May 31, 2024 at 04:49:28PM +0800, Herbert Xu wrote:
> > On Thu, May 30, 2024 at 11:52:58PM -0700, Eric Biggers wrote:
> > >
> > > Looking at it again a bit more closely, both fsverity and dm-verity have
> > > per-block information that they need to keep track of in the queue in addition
> > > to the data buffers and hashes: the block number, and in dm-verity's case also a
> > > bvec_iter pointing to that block.
> >
> > Again I'm not asking you to make this API asynchronous at all.
>
> What exactly are you suggesting, then? It seems that you want multibuffer
> hashing to be supported by the existing ahash API. However, that only works if
> it's made asynchronous, given how the messages would have to be queued up on a
> global queue. That has a huge number of issues which I've already explained.
> (And it was even tried before, and it failed.)
>
> > I was just commenting on the added complexity in fsverify due to
> > the use of the linear shash API instead of the page-based ahash API.
>
> It's the other way around. The shash version is much simpler. Just look at the
> diff of commit 8fcd94add6c5 that changed from ahash to shash:
>
> 4 files changed, 71 insertions(+), 200 deletions(-)
>
> > This complexity was then compounded by the multi-buffer support.
>
> fsverity and dm-verity will have to be updated to use multibuffer hashing
> anyway, given that transparently supporting it in the existing API is not
> viable. If your concern is that in my current patchset fsverity and dm-verity
> have separate code paths for multibuffer vs. single-buffer, as I mentioned I can
> address that by restructuring them to operate on arrays (similar to what I
> already did with the crypto API part).
>
> > I think this would look a lot simpler if it moved back to ahash.
> >
> > The original commit mentioned that ahash was bad for fsverify
> > because of vmalloc. But the only use of linear pointers in fsverify
> > seems to be from kmalloc. Where is the vmalloc coming from?
>
> XFS is working on adding support for fsverity, and XFS was planning to provide
> their Merkle tree blocks in vmalloced buffers. Their plans have shifted several
> times, and I think their latest plan no longer uses vmalloced buffers. But in
> any case it's still very convenient and much simpler to be able to just use
> virtual addresses without having to worry about what type of memory it is.
>

I've now unified the code paths for single-block and multi-block processing in
fsverity and dm-verity, which I think addresses your remaining concern that's
feasible to address. Your feedback has been conflating different issues, and it
only comes in once every few weeks, so it's a bit hard to follow. But I think
the remaining thing that you're asking for is to make the API to be part of
"ahash" and use the existing async completion callback. That's not actually
feasible, for the reasons that I've explained in detail. See in particular
https://lore.kernel.org/linux-crypto/[email protected]/.

Thanks,

- Eric