Re: [PATCH 0/4] dm verity: add support for error correction
On Thu, Nov 05, 2015 at 08:34:04AM +0100, Milan Broz wrote: > could you please elaborate why is all this needed? To extend support > of some faulty flash chips? This makes dm-verity more robust against corruption caused by either hardware or software bugs, both of which we have seen in the past on actual devices. Note that unlike the error correction sometimes included in flash storage devices, this doesn't merely protect against random bit flips, it makes it possible to recover from several megabytes of corrupted or lost data. > Do you have some statistics that there are really such correctable errors > in real devices? Sorry, I don't have statistics to share at the moment. > Anyway, I really do not understand layer separation here. I should have elaborated more on this. Implementing this without integrity checking would not be feasible for a few reasons: 1. Being able to detect which blocks are corrupted allows us to avoid correcting valid blocks. Correcting errors is slow and this is the only way to keep performance acceptable. 2. Due to a property of erasure codes, we can correct twice as many errors if we know where the errors are. Using the hash tree to detect corrupted blocks lets us locate erasures. 3. Error correction algorithms may not produce valid output and without integrity checking, there's no reliable way to detect when we actually succeeded in correcting a block. > Are we sure this combination does not create some unintended > gap in integrity checking? Yes, I'm sure. Corrupted blocks are integrity checked again after they are corrected to make sure only valid data is allowed to pass. > Why the integrity check should even try to do some > error correction if there is an intentional integrity attack? Most corruption is not malicious and being able to recover from it makes the system more reliable. This doesn't make it any easier for an attacker to break dm-verity. That would still require finding a hash collision (or being able to modify the hash tree). > The second question - why are you writing another separate tool > for maintenance for dm-verity when there is veritysetup? Our tool for generating error correction metadata is independent from dm-verity. This data is also used by other software to correct errors during software updates, for example. If there's interest, I can help in adding this functionality to veritysetup. Sami -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 0/4] dm verity: add support for error correction
On Thu, Nov 05, 2015 at 08:34:04AM +0100, Milan Broz wrote: > could you please elaborate why is all this needed? To extend support > of some faulty flash chips? This makes dm-verity more robust against corruption caused by either hardware or software bugs, both of which we have seen in the past on actual devices. Note that unlike the error correction sometimes included in flash storage devices, this doesn't merely protect against random bit flips, it makes it possible to recover from several megabytes of corrupted or lost data. > Do you have some statistics that there are really such correctable errors > in real devices? Sorry, I don't have statistics to share at the moment. > Anyway, I really do not understand layer separation here. I should have elaborated more on this. Implementing this without integrity checking would not be feasible for a few reasons: 1. Being able to detect which blocks are corrupted allows us to avoid correcting valid blocks. Correcting errors is slow and this is the only way to keep performance acceptable. 2. Due to a property of erasure codes, we can correct twice as many errors if we know where the errors are. Using the hash tree to detect corrupted blocks lets us locate erasures. 3. Error correction algorithms may not produce valid output and without integrity checking, there's no reliable way to detect when we actually succeeded in correcting a block. > Are we sure this combination does not create some unintended > gap in integrity checking? Yes, I'm sure. Corrupted blocks are integrity checked again after they are corrected to make sure only valid data is allowed to pass. > Why the integrity check should even try to do some > error correction if there is an intentional integrity attack? Most corruption is not malicious and being able to recover from it makes the system more reliable. This doesn't make it any easier for an attacker to break dm-verity. That would still require finding a hash collision (or being able to modify the hash tree). > The second question - why are you writing another separate tool > for maintenance for dm-verity when there is veritysetup? Our tool for generating error correction metadata is independent from dm-verity. This data is also used by other software to correct errors during software updates, for example. If there's interest, I can help in adding this functionality to veritysetup. Sami -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 2/4] dm verity: separate function for parsing opt args
Move optional argument parsing into a separate function to make it
easier to add more of them without making verity_ctr even longer.
Signed-off-by: Sami Tolvanen
---
drivers/md/dm-verity.c | 31 ++-
1 file changed, 22 insertions(+), 9 deletions(-)
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index 487cb66..da76f77 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -34,6 +34,8 @@
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
+#define DM_VERITY_OPTS_MAX 1
+
static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
module_param_named(prefetch_cluster, dm_verity_prefetch_cluster, uint, S_IRUGO
| S_IWUSR);
@@ -725,6 +727,21 @@ static void verity_dtr(struct dm_target *ti)
kfree(v);
}
+static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
+const char *opt_string)
+{
+ if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING)) {
+ v->mode = DM_VERITY_MODE_LOGGING;
+ return 0;
+ } else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART)) {
+ v->mode = DM_VERITY_MODE_RESTART;
+ return 0;
+ }
+
+ v->ti->error = "Invalid feature arguments";
+ return -EINVAL;
+}
+
/*
* Target parameters:
*The current format is version 1.
@@ -752,7 +769,7 @@ static int verity_ctr(struct dm_target *ti, unsigned argc,
char **argv)
char dummy;
static struct dm_arg _args[] = {
- {0, 1, "Invalid number of feature args"},
+ {0, DM_VERITY_OPTS_MAX, "Invalid number of feature args"},
};
v = kzalloc(sizeof(struct dm_verity), GFP_KERNEL);
@@ -912,15 +929,11 @@ static int verity_ctr(struct dm_target *ti, unsigned
argc, char **argv)
goto bad;
}
- if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING))
- v->mode = DM_VERITY_MODE_LOGGING;
- else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART))
- v->mode = DM_VERITY_MODE_RESTART;
- else {
- ti->error = "Invalid feature arguments";
- r = -EINVAL;
+ r = verity_parse_opt_args(, v, opt_string);
+ if (r < 0)
goto bad;
- }
+
+ opt_params -= r;
}
}
--
2.6.0.rc2.230.g3dd15c0
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH 0/4] dm verity: add support for error correction
This patch set adds error correction support to dm-verity, which makes it possible to recover from data corruption in exchange of increased space overhead. The feature is implemented as part of dm-verity to take advantage of the existing hash tree to improve performance and locate known erasures. Sami Tolvanen (4): dm verity: clean up duplicate hashing code dm verity: separate function for parsing opt args dm verity: add support for forward error correction dm verity: ignore zero blocks Documentation/device-mapper/verity.txt | 34 ++ drivers/md/dm-verity.c | 1004 +++- 2 files changed, 892 insertions(+), 146 deletions(-) -- 2.6.0.rc2.230.g3dd15c0 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 4/4] dm verity: ignore zero blocks
Add ignore_zero_blocks option, which returns zeros for blocks matching a
zero hash without validating the content.
Signed-off-by: Sami Tolvanen
---
Documentation/device-mapper/verity.txt | 5 ++
drivers/md/dm-verity.c | 88 ++
2 files changed, 83 insertions(+), 10 deletions(-)
diff --git a/Documentation/device-mapper/verity.txt
b/Documentation/device-mapper/verity.txt
index 3628d28..1b103b0 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 zeros and always return
+zeros instead. This may be useful if the partition contains unused blocks
+that are not guaranteed to contain zeros.
+
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.c b/drivers/md/dm-verity.c
index 61dec39..485d59e 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -38,6 +38,7 @@
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
+#define DM_VERITY_OPT_IGN_ZEROS"ignore_zero_blocks"
#define DM_VERITY_OPT_FEC_DEV "use_fec_from_device"
#define DM_VERITY_OPT_FEC_BLOCKS "fec_blocks"
@@ -45,7 +46,7 @@
#define DM_VERITY_OPT_FEC_ROOTS"fec_roots"
#define DM_VERITY_OPTS_FEC 8
-#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;
@@ -74,6 +75,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 */
@@ -422,9 +424,9 @@ release_ret_r:
* of the hash tree if necessary.
*/
static 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 r, i;
+ int r = 0, i;
if (likely(v->levels)) {
/*
@@ -436,7 +438,7 @@ static 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);
@@ -444,10 +446,16 @@ static 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;
}
- return 0;
+out:
+ if (!r && v->zero_digest)
+ *is_zero = !memcmp(v->zero_digest, digest, v->digest_size);
+ else
+ *is_zero = false;
+
+ return r;
}
/*
@@ -496,11 +504,19 @@ static int verity_bv_hash_update(struct dm_verity *v,
struct dm_verity_io *io,
return verity_hash_update(v, 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;
@@ -510,10 +526,23 @@ static int verity_verify_io(struct dm_verity_io *io)
struct shash_desc *desc = io_hash_desc(v, io);
r = verity_hash_for_block(v, io, io->block + b,
- io_want_digest(v, io));
+ io_want_digest(v, io), _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,
[PATCH 1/4] dm verity: clean up duplicate hashing code
Handle dm-verity salting in one place to simplify the code.
Signed-off-by: Sami Tolvanen
---
drivers/md/dm-verity.c | 262 +++--
1 file changed, 147 insertions(+), 115 deletions(-)
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index edc624b..487cb66 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -173,6 +173,84 @@ static sector_t verity_position_at_level(struct dm_verity
*v, sector_t block,
return block >> (level * v->hash_per_block_bits);
}
+/*
+ * Wrapper for crypto_shash_init, which handles verity salting.
+ */
+static int verity_hash_init(struct dm_verity *v, struct shash_desc *desc)
+{
+ int r;
+
+ desc->tfm = v->tfm;
+ desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
+
+ r = crypto_shash_init(desc);
+
+ if (unlikely(r < 0)) {
+ DMERR("crypto_shash_init failed: %d", r);
+ return r;
+ }
+
+ if (likely(v->version >= 1)) {
+ r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+ if (unlikely(r < 0)) {
+ DMERR("crypto_shash_update failed: %d", r);
+ return r;
+ }
+ }
+
+ return 0;
+}
+
+static int verity_hash_update(struct dm_verity *v, struct shash_desc *desc,
+ const u8 *data, size_t len)
+{
+ int r = crypto_shash_update(desc, data, len);
+
+ if (unlikely(r < 0))
+ DMERR("crypto_shash_update failed: %d", r);
+
+ return r;
+}
+
+static int verity_hash_final(struct dm_verity *v, struct shash_desc *desc,
+u8 *digest)
+{
+ int r;
+
+ if (unlikely(!v->version)) {
+ r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+ if (r < 0) {
+ DMERR("crypto_shash_update failed: %d", r);
+ return r;
+ }
+ }
+
+ r = crypto_shash_final(desc, digest);
+
+ if (unlikely(r < 0))
+ DMERR("crypto_shash_final failed: %d", r);
+
+ return r;
+}
+
+static int verity_hash(struct dm_verity *v, struct shash_desc *desc,
+ const u8 *data, size_t len, u8 *digest)
+{
+ int r;
+
+ r = verity_hash_init(v, desc);
+ if (unlikely(r < 0))
+ return r;
+
+ r = verity_hash_update(v, desc, data, len);
+ if (unlikely(r < 0))
+ return r;
+
+ return verity_hash_final(v, desc, digest);
+}
+
static void verity_hash_at_level(struct dm_verity *v, sector_t block, int
level,
sector_t *hash_block, unsigned *offset)
{
@@ -253,10 +331,10 @@ out:
* If "skip_unverified" is false, unverified buffer is hashed and verified
* against current value of io_want_digest(v, io).
*/
-static int verity_verify_level(struct dm_verity_io *io, sector_t block,
- int level, bool skip_unverified)
+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)
{
- struct dm_verity *v = io->v;
struct dm_buffer *buf;
struct buffer_aux *aux;
u8 *data;
@@ -273,75 +351,72 @@ static int verity_verify_level(struct dm_verity_io *io,
sector_t block,
aux = dm_bufio_get_aux_data(buf);
if (!aux->hash_verified) {
- struct shash_desc *desc;
- u8 *result;
-
if (skip_unverified) {
r = 1;
goto release_ret_r;
}
- desc = io_hash_desc(v, io);
- desc->tfm = v->tfm;
- desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
- r = crypto_shash_init(desc);
- if (r < 0) {
- DMERR("crypto_shash_init failed: %d", r);
+ r = verity_hash(v, io_hash_desc(v, io),
+ data, 1 << v->hash_dev_block_bits,
+ io_real_digest(v, io));
+ if (unlikely(r < 0))
goto release_ret_r;
- }
-
- if (likely(v->version >= 1)) {
- r = crypto_shash_update(desc, v->salt, v->salt_size);
- if (r < 0) {
- DMERR("crypto_shash_update failed: %d", r);
- goto release_ret_r;
- }
- }
- r = crypto_shash_update(desc, data, 1 <<
v->hash_dev_block_bits);
- if (r < 0) {
- DMERR("crypto_shash_update failed: %d", r);
-
[PATCH 3/4] 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
---
Documentation/device-mapper/verity.txt | 29 ++
drivers/md/dm-verity.c | 689 ++---
2 files changed, 673 insertions(+), 45 deletions(-)
diff --git a/Documentation/device-mapper/verity.txt
b/Documentation/device-mapper/verity.txt
index e15bc1a..3628d28 100644
--- a/Documentation/device-mapper/verity.txt
+++ b/Documentation/device-mapper/verity.txt
@@ -79,6 +79,35 @@ 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.
+
+A command line tool for generating encoding data is available from the
+Android Open Source Project:
+
https://android.googlesource.com/platform/system/extras/+/master/verity/fec/
+
+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
===
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index da76f77..61dec39 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -1,5 +1,6 @@
/*
* Copyright (C) 2012 Red Hat, Inc.
+ * Copyright (C) 2015 Google, Inc.
*
* Author: Mikulas Patocka
*
@@ -19,6 +20,8 @@
#include
#include
#include
+#include
+#include
#include
#define DM_MSG_PREFIX "verity"
@@ -31,10 +34,18 @@
#define DM_VERITY_MAX_LEVELS 63
#define DM_VERITY_MAX_CORRUPTED_ERRS 100
+#define DM_VERITY_FEC_RSM 255
+
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
-#define DM_VERITY_OPTS_MAX 1
+#define DM_VERITY_OPT_FEC_DEV "use_fec_from_device"
+#define DM_VERITY_OPT_FEC_BLOCKS "fec_blocks"
+#define DM_VERITY_OPT_FEC_START"fec_start"
+#define DM_VERITY_OPT_FEC_ROOTS"fec_roots"
+
+#define DM_VERITY_OPTS_FEC 8
+#define DM_VERITY_OPTS_MAX (1 + DM_VERITY_OPTS_FEC)
static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
@@ -54,8 +65,11 @@ enum verity_block_type {
struct dm_verity {
struct dm_dev *data_dev;
struct dm_dev *hash_dev;
+ struct dm_dev *fec_dev;
struct dm_target *ti;
- struct dm_bufio_client *bufio;
+ struct dm_bufio_client *data_bufio;
+ struct dm_bufio_client *hash_bufio;
+ struct dm_bufio_client *fec_bufio;
char *alg_name;
struct crypto_shash *tfm;
u8 *root_digest;/* digest of the root block */
@@ -65,11 +79,17 @@ struct dm_verity {
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 */
+ sector_t fec_start; /* FEC data start in blocks */
+ sector_t fec_blocks;/* number of blocks covered by FEC */
+ sector_t fec_rounds;/* number of FEC rounds */
+ sector_t fec_hash_blocks; /* blocks after hash_start */
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(
[PATCH 3/4] 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 <samitolva...@google.com>
---
Documentation/device-mapper/verity.txt | 29 ++
drivers/md/dm-verity.c | 689 ++---
2 files changed, 673 insertions(+), 45 deletions(-)
diff --git a/Documentation/device-mapper/verity.txt
b/Documentation/device-mapper/verity.txt
index e15bc1a..3628d28 100644
--- a/Documentation/device-mapper/verity.txt
+++ b/Documentation/device-mapper/verity.txt
@@ -79,6 +79,35 @@ 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.
+
+A command line tool for generating encoding data is available from the
+Android Open Source Project:
+
https://android.googlesource.com/platform/system/extras/+/master/verity/fec/
+
+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
===
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index da76f77..61dec39 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -1,5 +1,6 @@
/*
* Copyright (C) 2012 Red Hat, Inc.
+ * Copyright (C) 2015 Google, Inc.
*
* Author: Mikulas Patocka <mpato...@redhat.com>
*
@@ -19,6 +20,8 @@
#include
#include
#include
+#include
+#include
#include
#define DM_MSG_PREFIX "verity"
@@ -31,10 +34,18 @@
#define DM_VERITY_MAX_LEVELS 63
#define DM_VERITY_MAX_CORRUPTED_ERRS 100
+#define DM_VERITY_FEC_RSM 255
+
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
-#define DM_VERITY_OPTS_MAX 1
+#define DM_VERITY_OPT_FEC_DEV "use_fec_from_device"
+#define DM_VERITY_OPT_FEC_BLOCKS "fec_blocks"
+#define DM_VERITY_OPT_FEC_START"fec_start"
+#define DM_VERITY_OPT_FEC_ROOTS"fec_roots"
+
+#define DM_VERITY_OPTS_FEC 8
+#define DM_VERITY_OPTS_MAX (1 + DM_VERITY_OPTS_FEC)
static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
@@ -54,8 +65,11 @@ enum verity_block_type {
struct dm_verity {
struct dm_dev *data_dev;
struct dm_dev *hash_dev;
+ struct dm_dev *fec_dev;
struct dm_target *ti;
- struct dm_bufio_client *bufio;
+ struct dm_bufio_client *data_bufio;
+ struct dm_bufio_client *hash_bufio;
+ struct dm_bufio_client *fec_bufio;
char *alg_name;
struct crypto_shash *tfm;
u8 *root_digest;/* digest of the root block */
@@ -65,11 +79,17 @@ struct dm_verity {
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 */
+ sector_t fec_start; /* FEC data start in blocks */
+ sector_t fec_blocks;/* number of blocks covered by FEC */
+ sector_t fec_rounds;/* number of FEC rounds */
+ sector_t fec_hash_blocks; /* blocks after hash_start */
unsigned char data_dev_block_bits; /* log2(data blocksize) */
unsigned char hash_dev_block_bits; /* log2(hash blocksiz
[PATCH 1/4] dm verity: clean up duplicate hashing code
Handle dm-verity salting in one place to simplify the code.
Signed-off-by: Sami Tolvanen <samitolva...@google.com>
---
drivers/md/dm-verity.c | 262 +++--
1 file changed, 147 insertions(+), 115 deletions(-)
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index edc624b..487cb66 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -173,6 +173,84 @@ static sector_t verity_position_at_level(struct dm_verity
*v, sector_t block,
return block >> (level * v->hash_per_block_bits);
}
+/*
+ * Wrapper for crypto_shash_init, which handles verity salting.
+ */
+static int verity_hash_init(struct dm_verity *v, struct shash_desc *desc)
+{
+ int r;
+
+ desc->tfm = v->tfm;
+ desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
+
+ r = crypto_shash_init(desc);
+
+ if (unlikely(r < 0)) {
+ DMERR("crypto_shash_init failed: %d", r);
+ return r;
+ }
+
+ if (likely(v->version >= 1)) {
+ r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+ if (unlikely(r < 0)) {
+ DMERR("crypto_shash_update failed: %d", r);
+ return r;
+ }
+ }
+
+ return 0;
+}
+
+static int verity_hash_update(struct dm_verity *v, struct shash_desc *desc,
+ const u8 *data, size_t len)
+{
+ int r = crypto_shash_update(desc, data, len);
+
+ if (unlikely(r < 0))
+ DMERR("crypto_shash_update failed: %d", r);
+
+ return r;
+}
+
+static int verity_hash_final(struct dm_verity *v, struct shash_desc *desc,
+u8 *digest)
+{
+ int r;
+
+ if (unlikely(!v->version)) {
+ r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+ if (r < 0) {
+ DMERR("crypto_shash_update failed: %d", r);
+ return r;
+ }
+ }
+
+ r = crypto_shash_final(desc, digest);
+
+ if (unlikely(r < 0))
+ DMERR("crypto_shash_final failed: %d", r);
+
+ return r;
+}
+
+static int verity_hash(struct dm_verity *v, struct shash_desc *desc,
+ const u8 *data, size_t len, u8 *digest)
+{
+ int r;
+
+ r = verity_hash_init(v, desc);
+ if (unlikely(r < 0))
+ return r;
+
+ r = verity_hash_update(v, desc, data, len);
+ if (unlikely(r < 0))
+ return r;
+
+ return verity_hash_final(v, desc, digest);
+}
+
static void verity_hash_at_level(struct dm_verity *v, sector_t block, int
level,
sector_t *hash_block, unsigned *offset)
{
@@ -253,10 +331,10 @@ out:
* If "skip_unverified" is false, unverified buffer is hashed and verified
* against current value of io_want_digest(v, io).
*/
-static int verity_verify_level(struct dm_verity_io *io, sector_t block,
- int level, bool skip_unverified)
+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)
{
- struct dm_verity *v = io->v;
struct dm_buffer *buf;
struct buffer_aux *aux;
u8 *data;
@@ -273,75 +351,72 @@ static int verity_verify_level(struct dm_verity_io *io,
sector_t block,
aux = dm_bufio_get_aux_data(buf);
if (!aux->hash_verified) {
- struct shash_desc *desc;
- u8 *result;
-
if (skip_unverified) {
r = 1;
goto release_ret_r;
}
- desc = io_hash_desc(v, io);
- desc->tfm = v->tfm;
- desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
- r = crypto_shash_init(desc);
- if (r < 0) {
- DMERR("crypto_shash_init failed: %d", r);
+ r = verity_hash(v, io_hash_desc(v, io),
+ data, 1 << v->hash_dev_block_bits,
+ io_real_digest(v, io));
+ if (unlikely(r < 0))
goto release_ret_r;
- }
-
- if (likely(v->version >= 1)) {
- r = crypto_shash_update(desc, v->salt, v->salt_size);
- if (r < 0) {
- DMERR("crypto_shash_update failed: %d", r);
- goto release_ret_r;
- }
- }
- r = crypto_shash_update(desc, data, 1 <<
v->hash_dev_block_bits);
- if (r < 0) {
- DMERR("cry
[PATCH 4/4] dm verity: ignore zero blocks
Add ignore_zero_blocks option, which returns zeros for blocks matching a
zero hash without validating the content.
Signed-off-by: Sami Tolvanen <samitolva...@google.com>
---
Documentation/device-mapper/verity.txt | 5 ++
drivers/md/dm-verity.c | 88 ++
2 files changed, 83 insertions(+), 10 deletions(-)
diff --git a/Documentation/device-mapper/verity.txt
b/Documentation/device-mapper/verity.txt
index 3628d28..1b103b0 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 zeros and always return
+zeros instead. This may be useful if the partition contains unused blocks
+that are not guaranteed to contain zeros.
+
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.c b/drivers/md/dm-verity.c
index 61dec39..485d59e 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -38,6 +38,7 @@
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
+#define DM_VERITY_OPT_IGN_ZEROS"ignore_zero_blocks"
#define DM_VERITY_OPT_FEC_DEV "use_fec_from_device"
#define DM_VERITY_OPT_FEC_BLOCKS "fec_blocks"
@@ -45,7 +46,7 @@
#define DM_VERITY_OPT_FEC_ROOTS"fec_roots"
#define DM_VERITY_OPTS_FEC 8
-#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;
@@ -74,6 +75,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 */
@@ -422,9 +424,9 @@ release_ret_r:
* of the hash tree if necessary.
*/
static 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 r, i;
+ int r = 0, i;
if (likely(v->levels)) {
/*
@@ -436,7 +438,7 @@ static 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);
@@ -444,10 +446,16 @@ static 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;
}
- return 0;
+out:
+ if (!r && v->zero_digest)
+ *is_zero = !memcmp(v->zero_digest, digest, v->digest_size);
+ else
+ *is_zero = false;
+
+ return r;
}
/*
@@ -496,11 +504,19 @@ static int verity_bv_hash_update(struct dm_verity *v,
struct dm_verity_io *io,
return verity_hash_update(v, 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;
@@ -510,10 +526,23 @@ static int verity_verify_io(struct dm_verity_io *io)
struct shash_desc *desc = io_hash_desc(v, io);
r = verity_hash_for_block(v, io, io->block + b,
- io_want_digest(v, io));
+ io_want_digest(v, io), _zero);
if (unlikely(r < 0))
return r;
+ if (is_zero) {
+ /*
+* If we expect a zero block, don't validate, just
+* return zeros.
+*/
+
[PATCH 0/4] dm verity: add support for error correction
This patch set adds error correction support to dm-verity, which makes it possible to recover from data corruption in exchange of increased space overhead. The feature is implemented as part of dm-verity to take advantage of the existing hash tree to improve performance and locate known erasures. Sami Tolvanen (4): dm verity: clean up duplicate hashing code dm verity: separate function for parsing opt args dm verity: add support for forward error correction dm verity: ignore zero blocks Documentation/device-mapper/verity.txt | 34 ++ drivers/md/dm-verity.c | 1004 +++- 2 files changed, 892 insertions(+), 146 deletions(-) -- 2.6.0.rc2.230.g3dd15c0 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 2/4] dm verity: separate function for parsing opt args
Move optional argument parsing into a separate function to make it
easier to add more of them without making verity_ctr even longer.
Signed-off-by: Sami Tolvanen <samitolva...@google.com>
---
drivers/md/dm-verity.c | 31 ++-
1 file changed, 22 insertions(+), 9 deletions(-)
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index 487cb66..da76f77 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -34,6 +34,8 @@
#define DM_VERITY_OPT_LOGGING "ignore_corruption"
#define DM_VERITY_OPT_RESTART "restart_on_corruption"
+#define DM_VERITY_OPTS_MAX 1
+
static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
module_param_named(prefetch_cluster, dm_verity_prefetch_cluster, uint, S_IRUGO
| S_IWUSR);
@@ -725,6 +727,21 @@ static void verity_dtr(struct dm_target *ti)
kfree(v);
}
+static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
+const char *opt_string)
+{
+ if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING)) {
+ v->mode = DM_VERITY_MODE_LOGGING;
+ return 0;
+ } else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART)) {
+ v->mode = DM_VERITY_MODE_RESTART;
+ return 0;
+ }
+
+ v->ti->error = "Invalid feature arguments";
+ return -EINVAL;
+}
+
/*
* Target parameters:
*The current format is version 1.
@@ -752,7 +769,7 @@ static int verity_ctr(struct dm_target *ti, unsigned argc,
char **argv)
char dummy;
static struct dm_arg _args[] = {
- {0, 1, "Invalid number of feature args"},
+ {0, DM_VERITY_OPTS_MAX, "Invalid number of feature args"},
};
v = kzalloc(sizeof(struct dm_verity), GFP_KERNEL);
@@ -912,15 +929,11 @@ static int verity_ctr(struct dm_target *ti, unsigned
argc, char **argv)
goto bad;
}
- if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING))
- v->mode = DM_VERITY_MODE_LOGGING;
- else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART))
- v->mode = DM_VERITY_MODE_RESTART;
- else {
- ti->error = "Invalid feature arguments";
- r = -EINVAL;
+ r = verity_parse_opt_args(, v, opt_string);
+ if (r < 0)
goto bad;
- }
+
+ opt_params -= r;
}
}
--
2.6.0.rc2.230.g3dd15c0
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
