From a739ff3f543afbb4a041c16cd0182c8e8d366e70 Mon Sep 17 00:00:00 2001 From: Sami Tolvanen Date: Thu, 3 Dec 2015 14:26:30 +0000 Subject: dm verity: add support for forward error correction Add support for correcting corrupted blocks using Reed-Solomon. This code uses RS(255, N) interleaved across data and hash blocks. Each error-correcting block covers N bytes evenly distributed across the combined total data, so that each byte is a maximum distance away from the others. This makes it possible to recover from several consecutive corrupted blocks with relatively small space overhead. In addition, using verity hashes to locate erasures nearly doubles the effectiveness of error correction. Being able to detect corrupted blocks also improves performance, because only corrupted blocks need to corrected. For a 2 GiB partition, RS(255, 253) (two parity bytes for each 253-byte block) can correct up to 16 MiB of consecutive corrupted blocks if erasures can be located, and 8 MiB if they cannot, with 16 MiB space overhead. Signed-off-by: Sami Tolvanen Signed-off-by: Mike Snitzer --- Documentation/device-mapper/verity.txt | 35 ++++++++++++++++++++++++++++++++-- 1 file changed, 33 insertions(+), 2 deletions(-) (limited to 'Documentation') diff --git a/Documentation/device-mapper/verity.txt b/Documentation/device-mapper/verity.txt index e15bc1a0fb98..d602c801ff59 100644 --- a/Documentation/device-mapper/verity.txt +++ b/Documentation/device-mapper/verity.txt @@ -18,11 +18,11 @@ Construction Parameters 0 is the original format used in the Chromium OS. The salt is appended when hashing, digests are stored continuously and - the rest of the block is padded with zeros. + the rest of the block is padded with zeroes. 1 is the current format that should be used for new devices. The salt is prepended when hashing and each digest is - padded with zeros to the power of two. + padded with zeroes to the power of two. This is the device containing data, the integrity of which needs to be @@ -79,6 +79,32 @@ restart_on_corruption not compatible with ignore_corruption and requires user space support to avoid restart loops. +use_fec_from_device + Use forward error correction (FEC) to recover from corruption if hash + verification fails. Use encoding data from the specified device. This + may be the same device where data and hash blocks reside, in which case + fec_start must be outside data and hash areas. + + If the encoding data covers additional metadata, it must be accessible + on the hash device after the hash blocks. + + Note: block sizes for data and hash devices must match. Also, if the + verity is encrypted the should be too. + +fec_roots + Number of generator roots. This equals to the number of parity bytes in + the encoding data. For example, in RS(M, N) encoding, the number of roots + is M-N. + +fec_blocks + The number of encoding data blocks on the FEC device. The block size for + the FEC device is . + +fec_start + This is the offset, in blocks, from the start of the + FEC device to the beginning of the encoding data. + + Theory of operation =================== @@ -98,6 +124,11 @@ per-block basis. This allows for a lightweight hash computation on first read into the page cache. Block hashes are stored linearly, aligned to the nearest block size. +If forward error correction (FEC) support is enabled any recovery of +corrupted data will be verified using the cryptographic hash of the +corresponding data. This is why combining error correction with +integrity checking is essential. + Hash Tree --------- -- cgit v1.2.3 From 0cc37c2df4fa0aa702f9662edce4b7ce12c86b7a Mon Sep 17 00:00:00 2001 From: Sami Tolvanen Date: Thu, 3 Dec 2015 14:26:31 +0000 Subject: dm verity: add ignore_zero_blocks feature If ignore_zero_blocks is enabled dm-verity will return zeroes for blocks matching a zero hash without validating the content. Signed-off-by: Sami Tolvanen Signed-off-by: Mike Snitzer --- Documentation/device-mapper/verity.txt | 5 ++ drivers/md/dm-verity-fec.c | 8 +++- drivers/md/dm-verity-target.c | 87 ++++++++++++++++++++++++++++++---- drivers/md/dm-verity.h | 3 +- 4 files changed, 93 insertions(+), 10 deletions(-) (limited to 'Documentation') diff --git a/Documentation/device-mapper/verity.txt b/Documentation/device-mapper/verity.txt index d602c801ff59..89fd8f9a259f 100644 --- a/Documentation/device-mapper/verity.txt +++ b/Documentation/device-mapper/verity.txt @@ -79,6 +79,11 @@ restart_on_corruption not compatible with ignore_corruption and requires user space support to avoid restart loops. +ignore_zero_blocks + Do not verify blocks that are expected to contain zeroes and always return + zeroes instead. This may be useful if the partition contains unused blocks + that are not guaranteed to contain zeroes. + use_fec_from_device Use forward error correction (FEC) to recover from corruption if hash verification fails. Use encoding data from the specified device. This diff --git a/drivers/md/dm-verity-fec.c b/drivers/md/dm-verity-fec.c index 88143d36a1d2..1cc10c4de701 100644 --- a/drivers/md/dm-verity-fec.c +++ b/drivers/md/dm-verity-fec.c @@ -205,6 +205,7 @@ static int fec_read_bufs(struct dm_verity *v, struct dm_verity_io *io, u64 rsb, u64 target, unsigned block_offset, int *neras) { + bool is_zero; int i, j, target_index = -1; struct dm_buffer *buf; struct dm_bufio_client *bufio; @@ -264,7 +265,12 @@ static int fec_read_bufs(struct dm_verity *v, struct dm_verity_io *io, /* locate erasures if the block is on the data device */ if (bufio == v->fec->data_bufio && - verity_hash_for_block(v, io, block, want_digest) == 0) { + verity_hash_for_block(v, io, block, want_digest, + &is_zero) == 0) { + /* skip known zero blocks entirely */ + if (is_zero) + continue; + /* * skip if we have already found the theoretical * maximum number (i.e. fec->roots) of erasures diff --git a/drivers/md/dm-verity-target.c b/drivers/md/dm-verity-target.c index 4f90ec2c6b7a..5c5d30cb6ec5 100644 --- a/drivers/md/dm-verity-target.c +++ b/drivers/md/dm-verity-target.c @@ -31,8 +31,9 @@ #define DM_VERITY_OPT_LOGGING "ignore_corruption" #define DM_VERITY_OPT_RESTART "restart_on_corruption" +#define DM_VERITY_OPT_IGN_ZEROES "ignore_zero_blocks" -#define DM_VERITY_OPTS_MAX (1 + DM_VERITY_OPTS_FEC) +#define DM_VERITY_OPTS_MAX (2 + DM_VERITY_OPTS_FEC) static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE; @@ -309,10 +310,9 @@ release_ret_r: * of the hash tree if necessary. */ int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io, - sector_t block, u8 *digest) + sector_t block, u8 *digest, bool *is_zero) { - int i; - int r; + int r = 0, i; if (likely(v->levels)) { /* @@ -324,7 +324,7 @@ int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io, */ r = verity_verify_level(v, io, block, 0, true, digest); if (likely(r <= 0)) - return r; + goto out; } memcpy(digest, v->root_digest, v->digest_size); @@ -332,10 +332,15 @@ int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io, for (i = v->levels - 1; i >= 0; i--) { r = verity_verify_level(v, io, block, i, false, digest); if (unlikely(r)) - return r; + goto out; } +out: + if (!r && v->zero_digest) + *is_zero = !memcmp(v->zero_digest, digest, v->digest_size); + else + *is_zero = false; - return 0; + return r; } /* @@ -382,11 +387,19 @@ static int verity_bv_hash_update(struct dm_verity *v, struct dm_verity_io *io, return verity_hash_update(v, verity_io_hash_desc(v, io), data, len); } +static int verity_bv_zero(struct dm_verity *v, struct dm_verity_io *io, + u8 *data, size_t len) +{ + memset(data, 0, len); + return 0; +} + /* * 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; struct bvec_iter start; unsigned b; @@ -396,10 +409,24 @@ static int verity_verify_io(struct dm_verity_io *io) struct shash_desc *desc = verity_io_hash_desc(v, io); r = verity_hash_for_block(v, io, io->block + b, - verity_io_want_digest(v, io)); + verity_io_want_digest(v, io), + &is_zero); if (unlikely(r < 0)) return r; + if (is_zero) { + /* + * If we expect a zero block, don't validate, just + * return zeros. + */ + r = verity_for_bv_block(v, io, &io->iter, + verity_bv_zero); + if (unlikely(r < 0)) + return r; + + continue; + } + r = verity_hash_init(v, desc); if (unlikely(r < 0)) return r; @@ -604,6 +631,8 @@ static void verity_status(struct dm_target *ti, status_type_t type, args++; if (verity_fec_is_enabled(v)) args += DM_VERITY_OPTS_FEC; + if (v->zero_digest) + args++; if (!args) return; DMEMIT(" %u", args); @@ -620,6 +649,8 @@ static void verity_status(struct dm_target *ti, status_type_t type, BUG(); } } + if (v->zero_digest) + DMEMIT(" " DM_VERITY_OPT_IGN_ZEROES); sz = verity_fec_status_table(v, sz, result, maxlen); break; } @@ -671,6 +702,7 @@ static void verity_dtr(struct dm_target *ti) kfree(v->salt); kfree(v->root_digest); + kfree(v->zero_digest); if (v->tfm) crypto_free_shash(v->tfm); @@ -688,6 +720,37 @@ static void verity_dtr(struct dm_target *ti) kfree(v); } +static int verity_alloc_zero_digest(struct dm_verity *v) +{ + int r = -ENOMEM; + struct shash_desc *desc; + u8 *zero_data; + + v->zero_digest = kmalloc(v->digest_size, GFP_KERNEL); + + if (!v->zero_digest) + return r; + + desc = kmalloc(v->shash_descsize, GFP_KERNEL); + + if (!desc) + 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, desc, zero_data, 1 << v->data_dev_block_bits, + v->zero_digest); + +out: + kfree(desc); + kfree(zero_data); + + return r; +} + static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v) { int r; @@ -718,6 +781,14 @@ static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v) v->mode = DM_VERITY_MODE_RESTART; continue; + } else if (!strcasecmp(arg_name, DM_VERITY_OPT_IGN_ZEROES)) { + r = verity_alloc_zero_digest(v); + if (r) { + ti->error = "Cannot allocate zero digest"; + return r; + } + continue; + } else if (verity_is_fec_opt_arg(arg_name)) { r = verity_fec_parse_opt_args(as, v, &argc, arg_name); if (r) diff --git a/drivers/md/dm-verity.h b/drivers/md/dm-verity.h index 8e853722f6c6..fb419f422d73 100644 --- a/drivers/md/dm-verity.h +++ b/drivers/md/dm-verity.h @@ -40,6 +40,7 @@ struct dm_verity { struct crypto_shash *tfm; u8 *root_digest; /* digest of the root block */ u8 *salt; /* salt: its size is salt_size */ + u8 *zero_digest; /* digest for a zero block */ unsigned salt_size; sector_t data_start; /* data offset in 512-byte sectors */ sector_t hash_start; /* hash start in blocks */ @@ -123,6 +124,6 @@ extern int verity_hash(struct dm_verity *v, struct shash_desc *desc, 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); + sector_t block, u8 *digest, bool *is_zero); #endif /* DM_VERITY_H */ -- cgit v1.2.3