dm verity: add support for error correction
Subsystems (3)
cover 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(-)
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
PATCH 1/4 dm verity: clean up duplicate hashing code
Handle dm-verity salting in one place to simplify the code.
--- drivers/md/dm-verity.c | 262 +++++++++++++++++++++++++++---------------------- 1 file changed, 147 insertions(+), 115 deletions(-)
drivers/md/dm-verity.c +147 -115
@@ -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); - goto release_ret_r; - } - -if (!v->version) { - r =crypto_shash_update (desc, v->salt, v->salt_size); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); - goto release_ret_r; - } - } - - result =io_real_digest (v, io); - r =crypto_shash_final (desc, result); -if (r <0 ) { -DMERR ("crypto_shash_final failed: %d" , r); +if (likely (memcmp (io_real_digest (v, io), want_digest, + v->digest_size) ==0 )) + aux->hash_verified =1 ; +else if (verity_handle_err (v, +DM_VERITY_BLOCK_TYPE_METADATA , + hash_block)) { + r = -EIO ; goto release_ret_r; } -if (unlikely (memcmp (result,io_want_digest (v, io), v->digest_size))) { -if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_METADATA , - hash_block)) { - r = -EIO ; - goto release_ret_r; - } - }else - aux->hash_verified =1 ; } data += offset; - -memcpy (io_want_digest (v, io), data, v->digest_size); - -dm_bufio_release (buf); -return 0 ; +memcpy (want_digest, data, v->digest_size); + r =0 ; release_ret_r:dm_bufio_release (buf); -return r; }/* +* Find a hash for a given block, write it to digest and verify the integrity +* 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) +{ +int i; +int r; + +if (likely (v->levels)) { +/* +* First, we try to get the requested hash for +* the current block. If the hash block itself is +* verified, zero is returned. If it isn't, this +* function returns 1 and we fall back to whole +* chain verification. +*/ + r =verity_verify_level (v, io, block,0 , true, digest); +if (likely (r <=0 )) +return r; + } + +memcpy (digest, v->root_digest, v->digest_size); + +for (i = v->levels -1 ; i >=0 ; i--) { + r =verity_verify_level (v, io, block, i, false, digest); +if (unlikely (r)) +return r; + } + +return 0 ; +} + +/* * Verify one "dm_verity_io" structure. */ static int verity_verify_io (struct dm_verity_io *io)
@@ -350,54 +425,21 @@ static int verity_verify_io(struct dm_verity_io *io)struct bio *bio =dm_bio_from_per_bio_data (io, v->ti->per_bio_data_size);unsigned b; -int i;for (b =0 ; b < io->n_blocks; b++) { -struct shash_desc *desc; -u8 *result;int r;unsigned todo; +struct shash_desc *desc =io_hash_desc (v, io); -if (likely (v->levels)) { -/* -* First, we try to get the requested hash for -* the current block. If the hash block itself is -* verified, zero is returned. If it isn't, this -* function returns 0 and we fall back to whole -* chain verification. -*/ -int r =verity_verify_level (io, io->block + b,0 , true); -if (likely (!r)) - goto test_block_hash; -if (r <0 ) -return r; - } - -memcpy (io_want_digest (v, io), v->root_digest, v->digest_size); - -for (i = v->levels -1 ; i >=0 ; i--) { -int r =verity_verify_level (io, io->block + b, i, false); -if (unlikely (r)) -return r; - } + r =verity_hash_for_block (v, io, io->block + b, +io_want_digest (v, io)); +if (unlikely (r <0 )) +return r; -test_block_hash: - 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_init (v, desc); +if (unlikely (r <0 ))return 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); -return r; - } - } todo =1 << v->data_dev_block_bits; do { u8 *page;
@@ -408,37 +450,27 @@ test_block_hash: len = bv.bv_len;if (likely (len >= todo)) len = todo; - r =crypto_shash_update (desc, page + bv.bv_offset, len); + r =verity_hash_update (v, desc, page + bv.bv_offset, + len);kunmap_atomic (page); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); +if (unlikely (r <0 ))return r; - }bio_advance_iter (bio, &io->iter, len); todo -= len; }while (todo); -if (!v->version) { - r =crypto_shash_update (desc, v->salt, v->salt_size); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); -return r; - } - } - - result =io_real_digest (v, io); - r =crypto_shash_final (desc, result); -if (r <0 ) { -DMERR ("crypto_shash_final failed: %d" , r); + r =verity_hash_final (v, desc,io_real_digest (v, io)); +if (unlikely (r <0 ))return r; - } -if (unlikely (memcmp (result,io_want_digest (v, io), v->digest_size))) { -if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_DATA , - io->block + b)) -return -EIO ; - } + +if (likely (memcmp (io_real_digest (v, io), +io_want_digest (v, io), v->digest_size) ==0 )) +continue ; +else if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_DATA , + io->block + b)) +return -EIO ; }return 0 ;
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
Re: [PATCH 1/4] dm verity: clean up duplicate hashing code
Quoted 3 lines · Sami Tolvanen
Handle dm-verity salting in one place to simplify the code.
Signed-off-by Sami Tolvanen <[email protected]>
Thanks for cleaning this up!
-Kees
Quoted 345 lines
--- drivers/md/dm-verity.c | 262 +++++++++++++++++++++++++++---------------------- 1 file changed, 147 insertions(+), 115 deletions(-)drivers/md/dm-verity.c +147
-116@@ -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); - goto release_ret_r; - } - -if (!v->version) { - r =crypto_shash_update (desc, v->salt, v->salt_size); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); - goto release_ret_r; - } - } - - result =io_real_digest (v, io); - r =crypto_shash_final (desc, result); -if (r <0 ) { -DMERR ("crypto_shash_final failed: %d" , r); +if (likely (memcmp (io_real_digest (v, io), want_digest, + v->digest_size) ==0 )) + aux->hash_verified =1 ; +else if (verity_handle_err (v, +DM_VERITY_BLOCK_TYPE_METADATA , + hash_block)) { + r = -EIO ; goto release_ret_r; } -if (unlikely (memcmp (result,io_want_digest (v, io), v->digest_size))) { -if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_METADATA , - hash_block)) { - r = -EIO ; - goto release_ret_r; - } - }else - aux->hash_verified =1 ; } data += offset; - -memcpy (io_want_digest (v, io), data, v->digest_size); - -dm_bufio_release (buf); -return 0 ; +memcpy (want_digest, data, v->digest_size); + r =0 ; release_ret_r:dm_bufio_release (buf); -return r; }/* +* Find a hash for a given block, write it to digest and verify the integrity +* 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) +{ +int i; +int r; + +if (likely (v->levels)) { +/* +* First, we try to get the requested hash for +* the current block. If the hash block itself is +* verified, zero is returned. If it isn't, this +* function returns 1 and we fall back to whole +* chain verification. +*/ + r =verity_verify_level (v, io, block,0 , true, digest); +if (likely (r <=0 )) +return r; + } + +memcpy (digest, v->root_digest, v->digest_size); + +for (i = v->levels -1 ; i >=0 ; i--) { + r =verity_verify_level (v, io, block, i, false, digest); +if (unlikely (r)) +return r; + } + +return 0 ; +} + +/* * Verify one "dm_verity_io" structure. */ static int verity_verify_io (struct dm_verity_io *io)@@ -350,54 +425,21 @@ static int verity_verify_io(struct dm_verity_io *io)struct bio *bio =dm_bio_from_per_bio_data (io, v->ti->per_bio_data_size);unsigned b; -int i;for (b =0 ; b < io->n_blocks; b++) { -struct shash_desc *desc; -u8 *result;int r;unsigned todo; +struct shash_desc *desc =io_hash_desc (v, io); -if (likely (v->levels)) { -/* -* First, we try to get the requested hash for -* the current block. If the hash block itself is -* verified, zero is returned. If it isn't, this -* function returns 0 and we fall back to whole -* chain verification. -*/ -int r =verity_verify_level (io, io->block + b,0 , true); -if (likely (!r)) - goto test_block_hash; -if (r <0 ) -return r; - } - -memcpy (io_want_digest (v, io), v->root_digest, v->digest_size); - -for (i = v->levels -1 ; i >=0 ; i--) { -int r =verity_verify_level (io, io->block + b, i, false); -if (unlikely (r)) -return r; - } + r =verity_hash_for_block (v, io, io->block + b, +io_want_digest (v, io)); +if (unlikely (r <0 )) +return r; -test_block_hash: - 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_init (v, desc); +if (unlikely (r <0 ))return 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); -return r; - } - } todo =1 << v->data_dev_block_bits; do { u8 *page;@@ -408,37 +450,27 @@ test_block_hash: len = bv.bv_len;if (likely (len >= todo)) len = todo; - r =crypto_shash_update (desc, page + bv.bv_offset, len); + r =verity_hash_update (v, desc, page + bv.bv_offset, + len);kunmap_atomic (page); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); +if (unlikely (r <0 ))return r; - }bio_advance_iter (bio, &io->iter, len); todo -= len; }while (todo); -if (!v->version) { - r =crypto_shash_update (desc, v->salt, v->salt_size); -if (r <0 ) { -DMERR ("crypto_shash_update failed: %d" , r); -return r; - } - } - - result =io_real_digest (v, io); - r =crypto_shash_final (desc, result); -if (r <0 ) { -DMERR ("crypto_shash_final failed: %d" , r); + r =verity_hash_final (v, desc,io_real_digest (v, io)); +if (unlikely (r <0 ))return r; - } -if (unlikely (memcmp (result,io_want_digest (v, io), v->digest_size))) { -if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_DATA , - io->block + b)) -return -EIO ; - } + +if (likely (memcmp (io_real_digest (v, io), +io_want_digest (v, io), v->digest_size) ==0 )) +continue ; +else if (verity_handle_err (v,DM_VERITY_BLOCK_TYPE_DATA , + io->block + b)) +return -EIO ; }return 0 ; --2.6.0.rc2.230.g3dd15c0
Signature · 2 lines
Kees Cook Chrome OS Security
PATCH 2/4 dm verity: separate function for parsing opt args
In reply to Sami TolvanenMove optional argument parsing into a separate function to make it easier to add more of them without making verity_ctr even longer.
--- drivers/md/dm-verity.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-)
drivers/md/dm-verity.c +22 -9
@@ -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: * <version> 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 (&as, v, opt_string); +if (r <0 ) goto bad; - } + + opt_params -= r; } }
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
Re: [PATCH 2/4] dm verity: separate function for parsing opt args
Quoted 4 lines · Sami Tolvanen
Move optional argument parsing into a separate function to make it easier to add more of them without making
verity_ctreven longer.Signed-off-by Sami Tolvanen <[email protected]>
-Kees
Quoted 71 lines
--- drivers/md/dm-verity.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-)drivers/md/dm-verity.c +22
-10@@ -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: * <version> 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 (&as, v, opt_string); +if (r <0 ) goto bad; - } + + opt_params -= r; } } --2.6.0.rc2.230.g3dd15c0
Signature · 2 lines
Kees Cook Chrome OS Security
Re: [PATCH 2/4] dm verity: separate function for parsing opt args
In reply to Sami TolvanenQuoted 4 lines · Sami Tolvanen
Move optional argument parsing into a separate function to make it easier to add more of them without making
verity_ctreven longer.Signed-off-by Sami Tolvanen <[email protected]>
I've taken this patch, for Linux 4.5, but I've applied the following incremental patch ontop to make verity's optional argument parsing follow establish DM patterns (the code is very similar to dm-mpath.c:parse_features). Your follow-on patches will obviously need to be rebased on this, but the code will be much cleaner.
drivers/md/dm-verity.c +36 -33
@@ -723,19 +723,42 @@ 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) +static int verity_parse_opt_args (struct dm_arg_set *as,struct dm_verity *v) { -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 ; +int r; +unsigned argc; +struct dm_target *ti = v->ti; +const char *arg_name; + +static struct dm_arg _args[] = { + {0 ,DM_VERITY_OPTS_MAX ,"Invalid number of feature args" }, + }; + + r =dm_read_arg_group (_args, &as, &argc, &ti->error); +if (r) +return -EINVAL ; + +if (!argc)return 0 ; - } - v->ti->error ="Invalid feature arguments" ; -return -EINVAL ; +do { + arg_name =dm_shift_arg (&as); + argc--; + +if (!strcasecmp (arg_name,DM_VERITY_OPT_LOGGING )) { + v->mode =DM_VERITY_MODE_LOGGING ; +continue ; + + }else if (!strcasecmp (arg_name,DM_VERITY_OPT_RESTART )) { + v->mode =DM_VERITY_MODE_RESTART ; +continue ; + } + + ti->error ="Unrecognized verity feature request" ; +return -EINVAL ; + }while (argc && !r); + +return r; }/*
@@ -757,17 +780,13 @@ static int verity_ctr(struct dm_target *ti, unsigned argc, char **argv)struct dm_verity *v;struct dm_arg_set as;const char *opt_string; -unsigned int num, opt_params; +unsigned int num;unsigned long long num_ll;int r;int i;sector_t hash_position;char dummy; -static struct dm_arg _args[] = { - {0 ,DM_VERITY_OPTS_MAX ,"Invalid number of feature args" }, - }; - v =kzalloc (sizeof (struct dm_verity ),GFP_KERNEL );if (!v) { ti->error ="Cannot allocate verity structure" ;
@@ -912,25 +931,9 @@ static int verity_ctr(struct dm_target *ti, unsigned argc, char **argv) as.argc = argc; as.argv = argv; - r =dm_read_arg_group (_args, &as, &opt_params, &ti->error); -if (r) + r =verity_parse_opt_args (&as, v); +if (r <0 ) goto bad; - -while (opt_params) { - opt_params--; - opt_string =dm_shift_arg (&as); -if (!opt_string) { - ti->error ="Not enough feature arguments" ; - r = -EINVAL ; - goto bad; - } - - r =verity_parse_opt_args (&as, v, opt_string); -if (r <0 ) - goto bad; - - opt_params -= r; - } } v->hash_per_block_bits =
PATCH 3/4 dm verity: add support for forward error correction
In reply to Sami TolvanenAdd 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.
--- Documentation/device-mapper/verity.txt | 29 ++ drivers/md/dm-verity.c | 689 ++++++++++++++++++++++++++++++--- 2 files changed, 673 insertions(+), 45 deletions(-)
Documentation/device-mapper/verity.txt +29 -0
@@ -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 <data_block_size>. + +fec_start + This is the offset, in <data_block_size> blocks, from the start of the + FEC device to the beginning of the encoding data. + + Theory of operation ===================
drivers/md/dm-verity.c +644 -45
882 lines not on this page · raw message
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
kbuild test robot
build botRe: [PATCH 3/4] dm verity: add support for forward error correction
reproduce:
Hi Sami,
[auto build test ERROR on: dm/for-next]
[also build test ERROR on: v4.3 next-20151104]
url: https://github.com/0day-ci/linux/commits/Sami-Tolvanen/dm-verity-clean-up-duplicate-hashing-code/20151105-124458 base: https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git for-next config: i386-randconfig-a0-201544 (attached as .config) reproduce: # save the attached .config to linux build tree make ARCH=i386
All errors (new ones prefixed by >>):
drivers/md/dm-verity.c: In function 'verity_fec_decode_rs8':
>> drivers/md/dm-verity.c:569:9: error: implicit declaration of function 'decode_rs8' [-Werror=implicit-function-declaration]
return decode_rs8(io->rs, data, par, v->fec_rsn, NULL, neras,
^cc1: some warnings being treated as errors
vim +/decode_rs8 +569 drivers/md/dm-verity.c
563 int i;
564 uint16_t par[v->fec_roots];
565
566 for (i = 0; i < v->fec_roots; i++)
567 par[i] = fec[i];
568
> 569 return decode_rs8(io->rs, data, par, v->fec_rsn, NULL, neras,
570 io->erasures, 0, NULL);
571 }
572
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
kbuild test robot
build botRe: [PATCH 3/4] dm verity: add support for forward error correction
In reply to Sami Tolvanenreproduce: wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # save the attached .config to linux build tree…
Hi Sami,
[auto build test WARNING on: dm/for-next]
[also build test WARNING on: v4.3 next-20151105]
url: https://github.com/0day-ci/linux/commits/Sami-Tolvanen/dm-verity-clean-up-duplicate-hashing-code/20151105-124458 base: https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git for-next config: s390-allyesconfig (attached as .config)
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=s390
All warnings (new ones prefixed by >>):
drivers/md/dm-verity.c: In function 'verity_fec_decode_rsb':
>> drivers/md/dm-verity.c:812:1: warning: 'verity_fec_decode_rsb' uses dynamic stack allocation
}
^vim +/verity_fec_decode_rsb +812 drivers/md/dm-verity.c
796 if (r < 0)
797 return r;
798
799 r = verity_hash(v, io_hash_desc(v, io), io->fec_buf,
800 1 << v->data_dev_block_bits, io_real_digest(v, io));
801 if (unlikely(r < 0))
802 return r;
803
804 if (memcmp(io_real_digest(v, io), io_want_digest(v, io),
805 v->digest_size)) {
806 DMERR_LIMIT("%s: FEC %llu: failed to correct (%d erasures)",
807 v->data_dev->name, (unsigned long long)rsb, neras);
808 return -1;
809 }
810
811 return 0;
> 812 }
813
814 static int verity_fec_bv_copy(struct dm_verity *v, struct dm_verity_io *io,
815 u8 *data, size_t len)
816 {
817 BUG_ON(io->fec_pos + len > 1 << v->data_dev_block_bits);
818 memcpy(data, &io->fec_buf[io->fec_pos], len);
819 io->fec_pos += len;
820 return 0;
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
PATCH 4/4 dm verity: ignore zero blocks
In reply to Sami TolvanenAdd ignore_zero_blocks option, which returns zeros for blocks matching a zero hash without validating the content.
--- Documentation/device-mapper/verity.txt | 5 ++ drivers/md/dm-verity.c | 88 ++++++++++++++++++++++++++++++---- 2 files changed, 83 insertions(+), 10 deletions(-)
Documentation/device-mapper/verity.txt +5 -0
@@ -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
drivers/md/dm-verity.c +78 -10
189 lines not on this page · raw message
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
kbuild test robot
build botRe: [PATCH 4/4] dm verity: ignore zero blocks
reproduce: wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # save the attached .config to linux build tree…
Hi Sami,
[auto build test WARNING on: dm/for-next]
[also build test WARNING on: v4.3 next-20151105]
url: https://github.com/0day-ci/linux/commits/Sami-Tolvanen/dm-verity-clean-up-duplicate-hashing-code/20151105-124458 base: https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git for-next config: s390-allyesconfig (attached as .config)
reproduce:
wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=s390
All warnings (new ones prefixed by >>):
drivers/md/dm-verity.c: In function 'verity_alloc_zero_digest':
>> drivers/md/dm-verity.c:1226:1: warning: 'verity_alloc_zero_digest' uses dynamic stack allocation
}
^
drivers/md/dm-verity.c: In function 'verity_fec_decode_rsb':
drivers/md/dm-verity.c:846:1: warning: 'verity_fec_decode_rsb' uses dynamic stack allocation
}
^vim +/verity_alloc_zero_digest +1226 drivers/md/dm-verity.c
1210
1211 v->zero_digest = kmalloc(v->digest_size, GFP_KERNEL);
1212
1213 if (!v->zero_digest)
1214 return -ENOMEM;
1215
1216 zero_data = kzalloc(1 << v->data_dev_block_bits, GFP_KERNEL);
1217
1218 if (!zero_data)
1219 return -ENOMEM; /* verity_dtr will free zero_digest */
1220
1221 r = verity_hash(v, (struct shash_desc *)desc, zero_data,
1222 1 << v->data_dev_block_bits, v->zero_digest);
1223
1224 kfree(zero_data);
1225 return r;
> 1226 }
1227
1228 static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
1229 const char *opt_string)
1230 {
1231 int r;
1232 unsigned long long num_ll;
1233 unsigned char num_c;
1234 char dummy;
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
Quoted 7 lines · Sami Tolvanen
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.
Hi,
could you please elaborate why is all this needed? To extend support of some faulty flash chips?
Do you have some statistics that there are really such correctable errors in real devices?
Anyway, I really do not understand layer separation here. Either we have cryptographically strong data integrity checking or we have error-correction. Are we sure this combination does not create some unintended gap in integrity checking? Why the integrity check should even try to do some error correction if there is an intentional integrity attack?
IMO if you need an error correction, this should be placed as a separate layer below the crypto integrity check, the same as RAID operates.
The second question - why are you writing another separate tool for maintenance for dm-verity when there is veritysetup?
Milan
Quoted 2 lines · Milan Broz
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.
Quoted 2 lines
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.
Quoted 1 line
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.
Quoted 2 lines
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.
Quoted 2 lines
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).
Quoted 2 lines
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
Quoted 4 lines · Sami Tolvanen
Quoted 2 lines · Milan Broz
could you please elaborate why is all this needed? To extend support of some faulty flash chips?
Quoted 8 lines
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.
Google (via Android and/or ChromeOS) is the primary consumer of dm-verity.
As such I'm inclined to trust Google's need for this feature and that it has been carefully designed and implemented. But obviously we need to verify that.
Patches 1 and 2 look fine to me (just refactoring, no functional change). I may find something upon closer review but we'll cross that bridge if/when we get to it.
Quoted 14 lines
Quoted 2 lines
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.
Quoted 1 line
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.
Quoted 7 lines
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.
This all makes sense to me.
So for patch 3:
I'm left wondering: can the new error correction code be made an optional feature that is off by default? -- so as to preserve some isolation of this new code from the old dm-verity behaviour. Looking at the code it isn't immediately clear to me where any of this is _really_ optional; closest I see if verity_fec_decode() returning -1 if (!v->fec_bufio)... might be good to add a wrapper like verity_fec_is_enabled().
The if (v->fec_dev) {} block in verity_ctr() should probably be split out to a new function. Similar to how drivers/md/dm-thin.c:pool_create() will return error string via **error, etc.
In addition the kbuild errors/warnings (reported by the kbuild test robot) need fixing.
Also, the 2 other big questions from Mikulas need answering:
1) why aren't you actually adjustng error codes, returning success, if dm-verity was able to trap/correct the corruption?
2) please fix the code to preallocate all required memory -- so that verity_fec_alloc_buffers() isn't called in map. Any reason why you couldn't collect the table's fec options and determine how much additional memory is needed per dm_verity_io? And then just add that to the per-bio-data?
Quoted 5 lines
Quoted 2 lines
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.
Makes sense.
Quoted 8 lines
Quoted 2 lines
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).
Quoted 7 lines
Quoted 2 lines
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.
If this error correction feature is going to go upstream we really should see any associated userspace enablement also included in veritysetup. Really no sense in fragmenting the utilities used to setup a dm-verity device.
Quoted 3 lines · Mike Snitzer
I'm left wondering: can the new error correction code be made an optional feature that is off by default? -- so as to preserve some isolation of this new code from the old dm-verity behaviour.
It's optional in the sense that you must specify error correction parameters in the table to turn it on. Otherwise, verity_dec_decode returns -1 and dm-verity handles errors as before.
Quoted 1 line
might be good to add a wrapper like
verity_fec_is_enabled().
Sure. I can do this in v2 and address the other feedback and build issues as well.
Quoted 3 lines
Also, the 2 other big questions from Mikulas need answering:
1) why aren't you actually adjustng error codes, returning success, if dm-verity was able to trap/correct the corruption?
We don't see actual I/O errors very often. Most corruption we've seen is caused by flaky hardware that doesn't return errors. However, I can certainly change to code to attempt recovery in this case too.
Quoted 2 lines
2) please fix the code to preallocate all required memory -- so that
verity_fec_alloc_buffers()isn't called in map.
I tried to avoid preallocating the buffers because they are relatively large (up to 1 MiB depending on the Reed-Solomon parameters) and not required unless we have errors to correct. I suppose there's no way to safely do this in the middle of I/O?
Quoted 3 lines
If this error correction feature is going to go upstream we really should see any associated userspace enablement also included in veritysetup.
I can look into this.
Sami
Quoted 5 lines · Sami Tolvanen
Quoted 3 lines · Mike Snitzer
I'm left wondering: can the new error correction code be made an optional feature that is off by default? -- so as to preserve some isolation of this new code from the old dm-verity behaviour.
Quoted 8 lines
It's optional in the sense that you must specify error correction parameters in the table to turn it on. Otherwise,
verity_dec_decodereturns -1 and dm-verity handles errors as before.Quoted 1 line
might be good to add a wrapper like
verity_fec_is_enabled().Sure. I can do this in v2 and address the other feedback and build issues as well.
Thanks.
Quoted 7 lines
Quoted 3 lines
Also, the 2 other big questions from Mikulas need answering:
1) why aren't you actually adjustng error codes, returning success, if dm-verity was able to trap/correct the corruption?We don't see actual I/O errors very often. Most corruption we've seen is caused by flaky hardware that doesn't return errors. However, I can certainly change to code to attempt recovery in this case too.
OK, might be worthwhile to simulate underlying storage errors using the dm-flakey target underneath dm-verity just to validate your changes work as expected.
Quoted 7 lines
Quoted 2 lines
2) please fix the code to preallocate all required memory -- so that
verity_fec_alloc_buffers()isn't called in map.I tried to avoid preallocating the buffers because they are relatively large (up to 1 MiB depending on the Reed-Solomon parameters) and not required unless we have errors to correct. I suppose there's no way to safely do this in the middle of I/O?
Basically you want to be able to ensure forward progress of dm-verity IO even in the face of no system memory being generally available.
Hopefully this doesn't seem like make-work for you. This one of the design considerations imposed on DM targets because otherwise you run the risk of failing IO in the face of low memory. Which results in users experiencing failures.
1MB is quite large, especially if it is unlikely to be used. dm-cache does cope with the need for memory in the IO path, see 'struct prealloc', prealloc_data_structs() and other related functions in drivers/md/dm-cache-target.c
But in the dm-cache case a worker thread is processing work and needs memory for each work item. So it isn't the .map function that directly needs the memory.
DM-thinp also pre-allocates memory using a mempool, e.g. see drivers/md/dm-thin.c:bio_detain(). But again, this portion of dm-thinp is being run from a worker thread and _not_ the .map functons.
Could you architect the FEC code such that it punts IO to a worker thread only if errors need correcting? And have that worker thread's additional memory allocations be backed by a mempool?
On 11/09/2015 08:19 PM, Sami Tolvanen wrote:
...
Quoted 3 lines
We don't see actual I/O errors very often. Most corruption we've seen is caused by flaky hardware that doesn't return errors. However, I can certainly change to code to attempt recovery in this case too.
So if I understand it correctly, there is a simplified flash controller that can send data with bit flips without detection?
(IOW in "real" SSD this kind of error should be detected internally by some bad block management?)
This is why I asked about some statistics of real visible types of errors.
For this use case it makes sense to have error correction here but then we should clearly said that it makes no sense to switch it on for "real" hw that does internal integrity check or error correction
(but not authenticated integrity check as dm-verity).
...
Quoted 5 lines
Quoted 3 lines
If this error correction feature is going to go upstream we really should see any associated userspace enablement also included in veritysetup.
I can look into this.
Yes, please, patches do not to be production ready (I can integrate it to veritysetup upstream myself) but it would be very nice that released veritysetup can configure all dm-verity features in the same time the mainline kernel is marked stable.
(The same applies for dm-crypt & cryptsetup.)
Thanks,
Milan
Quoted 2 lines · Milan Broz
Yes, please, patches do not to be production ready (I can integrate it to veritysetup upstream myself)
I'm working on this and should have a patch for veritysetup for you next week.
Sami
Mikulas Patocka
maintainerQuoted 7 lines · Sami Tolvanen
Quoted 3 lines
Also, the 2 other big questions from Mikulas need answering:
1) why aren't you actually adjustng error codes, returning success, if dm-verity was able to trap/correct the corruption?We don't see actual I/O errors very often. Most corruption we've seen is caused by flaky hardware that doesn't return errors. However, I can certainly change to code to attempt recovery in this case too.
What flash controller and chips do you use? What is the probability of I/O error and what is the probability of silent data corruption? Is the silent data corruption permanent or transient? What is causing the silent data corruption (decay in flash chips?, errors on the bus?) Why can't you ask the hardware engineers to use a controler with proper error correction?
Without these data - it looks like you first wrote the patch and then tried to make some excuses why it should be accepted.
I'm also a little bit concerned that the patch will increase prevalence of crapware on the market - when accepted, this kind of reasoning will
follow: "now we have error correction in the kernel, so we cut down flash overprovisioning, save a dollar or two per device, and produce a crap that randomly corrupts user's data on the read-write partition (because that partition not protected by the error correction)".
Mikulas
Quoted 1 line · Mikulas Patocka
What flash controller and chips do you use?
Considering the number of different devices running Android, I don't have a good answer for this. I'm guessing most of them.
Quoted 1 line
Is the silent data corruption permanent or transient?
Most of the corruption we have observed is permanent, and typically caused by a write failure rather than a read failure. A while ago we also discovered a bug in our kernels which resulted in unexpected modification of read-only partitions and ended up causing quite a lot of problems. While in an ideal world this wouldn't happen, in real life it's better to have an additional layer of protection against issues like these.
Quoted 2 lines
Why can't you ask the hardware engineers to use a controler with proper error correction?
The most advanced hardware error correction I've seen only handles errors within a single sector and cannot detect all possible corruption, let alone correct it. If you have examples of hardware with proper error correction, I would love to take a look. Of course, if this is even $1-2 more expensive per device than the current hardware, chances are it's not going to make the budget cut with many device manufacturers, whether we like it or not.
Quoted 2 lines
Without these data - it looks like you first wrote the patch and then tried to make some excuses why it should be accepted.
I posted the patches primarily to hear your feedback, not necessarily to get them accepted. The only goal I have is to improve the reliability of devices using dm-verity. This solution makes it possible to recover from a large number of corrupted blocks with a very small storage overhead and no additional CPU overhead when the partition is not corrupted (and thus, no additional power consumption). I can fully understand that these may not be important concerns in other environments where one might just as well run raid5 over multiple dm-verity devices, as you suggested.
Quoted 2 lines
I'm also a little bit concerned that the patch will increase prevalence of crapware on the market
We are already concerned about current devices that end up with corrupted partitions for one reason or another. When an ecosystem consists of more than 10^9 devices, if even a small fraction of them are returned or need to be repaired due to a dm-verity failure, it quickly becomes very expensive and actively discourages device manufacturers from adopting dm-verity. This is not even considering the number of people inconvenienced by these issues.
Sami
Quoted 5 lines · Sami Tolvanen
Quoted 3 lines · Mike Snitzer
I'm left wondering: can the new error correction code be made an optional feature that is off by default? -- so as to preserve some isolation of this new code from the old dm-verity behaviour.
Quoted 8 lines
It's optional in the sense that you must specify error correction parameters in the table to turn it on. Otherwise,
verity_dec_decodereturns -1 and dm-verity handles errors as before.Quoted 1 line
might be good to add a wrapper like
verity_fec_is_enabled().Sure. I can do this in v2 and address the other feedback and build issues as well.
Hi Sami,
Any progress on v2 that takes into account previous review feedback?
Note I've staged the first 2 patches in this series for Linux 4.5 inclusion, see:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=dm-4.5
Mike
Quoted 1 line · Mike Snitzer
Any progress on v2 that takes into account previous review feedback?
Yes. Sorry for the delay, the changes have gone through a couple of rounds of internal reviews and testing first.
Quoted 2 lines
Note I've staged the first 2 patches in this series for Linux 4.5 inclusion
Great, thanks. I'll send v2 rebased on top of these today.
Sami
Mikulas Patocka
maintainerQuoted 9 lines · Milan Broz
Quoted 7 lines · Sami Tolvanen
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.
Quoted 7 lines
Hi,
could you please elaborate why is all this needed? To extend support of some faulty flash chips?
Do you have some statistics that there are really such correctable errors in real devices?
I'm also wondering what is this patch useful for. Disks and flash controllers have their own error detection and correction, so the controller will much more likely return an I/O error rather than corrupted data. And the patch does absolutely nothing to recover from an I/O error, it only attempts to correct corrupted reads.
Another point - if the read-only system partition is experiencing some errors, than the read-write partition will probably have errors too (because both partitions are on the same flash chip) and the Chromebook or smartphone will be unusable anyway because of errors on the writeable partition. Do you have some real case where such error corrections increase longevity of some device?
Quoted 8 lines
Anyway, I really do not understand layer separation here. Either we have cryptographically strong data integrity checking or we have error-correction. Are we sure this combination does not create some unintended gap in integrity checking? Why the integrity check should even try to do some error correction if there is an intentional integrity attack?
IMO if you need an error correction, this should be placed as a separate layer below the crypto integrity check, the same as RAID operates.
If error correction was placed below dm-verity, it would degrade performance because it would have to verify every sector, even if dm-verity said that the sector is valid.
But you can take raid5 in read-only mode, put it on several partitions protected with dm-verity and you get decent error correction (unlike this patch, it would also correct I/O errors returned by the flash controller). I suggest doing this.
Quoted 4 lines
The second question - why are you writing another separate tool for maintenance for dm-verity when there is veritysetup?
Milan
Mikulas
Quoted 2 lines · Mikulas Patocka
I'm also wondering what is this patch useful for. Disks and flash controllers have their own error detection and correction
I think I addressed this earlier. Some storage devices are able to correct bit flips, but don't have enough redundancy to correct larger errors. Using this patch set we can correct N MiB of consecutive corruption anywhere on the partition with the same amount of storage overhead.
Quoted 2 lines
Another point - if the read-only system partition is experiencing some errors, than the read-write partition will probably have errors too
On mobile devices, errors in read-only partitions often lead to bricked devices while errors in the read-write parts might only lead to lost cat photos. There are situations where people would prefer to have a working phone even if it fails to store some of their data.
Quoted 2 lines
Do you have some real case where such error corrections increase longevity of some device?
Yes, there have been several cases where read-only partition errors have rendered a device unusable. The sheer volume of mobile devices means that even if a tiny fraction of them suffer from such a problem, it's going to affect a large number of people.
Quoted 2 lines
But you can take raid5 in read-only mode, put it on several partitions protected with dm-verity and you get decent error correction
I agree. Unfortunately, we don't currently have the luxury of using raid on mobile devices.
Sami
Dne 6.11.2015 v 20:06 Sami Tolvanen napsal(a):
Quoted 26 lines · Mikulas Patocka
Quoted 2 lines
I'm also wondering what is this patch useful for. Disks and flash controllers have their own error detection and correction
I think I addressed this earlier. Some storage devices are able to correct bit flips, but don't have enough redundancy to correct larger errors. Using this patch set we can correct N MiB of consecutive corruption anywhere on the partition with the same amount of storage overhead.
Quoted 2 lines
Another point - if the read-only system partition is experiencing some errors, than the read-write partition will probably have errors too
On mobile devices, errors in read-only partitions often lead to bricked devices while errors in the read-write parts might only lead to lost cat photos. There are situations where people would prefer to have a working phone even if it fails to store some of their data.
Quoted 2 lines
Do you have some real case where such error corrections increase longevity of some device?
Yes, there have been several cases where read-only partition errors have rendered a device unusable. The sheer volume of mobile devices means that even if a tiny fraction of them suffer from such a problem, it's going to affect a large number of people.
Quoted 5 lines
Quoted 2 lines
But you can take raid5 in read-only mode, put it on several partitions protected with dm-verity and you get decent error correction
I agree. Unfortunately, we don't currently have the luxury of using raid on mobile devices.
AFAIK - you just build as much partition as need to have some 'space' dedicated for redundancy - and rest of 'partitions' you join as 'writable'
i.e. you have 1G of space - you want to give 250MB as 'redundancy' - so create 4 partition....
Since phones starts to have 64GB of storage space - it looks like a way to go.....
As no one bothers to upgrade 'old' phone - why to focus there??
And BTW - already seen couple bricked Nexus7....
(And no marhmallow in plan....)
(And interestingly all killed I've seen were on Lolipop - none with Kitkat)
Zdenek
Quoted 2 lines · Zdenek Kabelac
i.e. you have 1G of space - you want to give 250MB as 'redundancy' - so create 4 partition....
We cannot afford to set aside 25% of read-only partition space for redundancy on mobile devices, and would rather not impact performance any more than dm-verity already does. With error correction we have 0.8% space overhead in our use case and no performance degradation if the partition is not corrupted.
Sami
Dne 6.11.2015 v 21:27 Sami Tolvanen napsal(a):
Quoted 3 lines · Zdenek Kabelac
Quoted 2 lines
i.e. you have 1G of space - you want to give 250MB as 'redundancy' - so create 4 partition....
well data safety has it's price - user should choose what he prefers
- more games and videos or more safety...
Quoted 7 lines
We cannot afford to set aside 25% of read-only partition space for redundancy on mobile devices, and would rather not impact performance any more than dm-verity already does. With error correction we have 0.8% space overhead in our use case and no performance degradation if the partition is not corrupted.
I'm probably missing here some hw knowledge here - but if you loose a flash block of some size - then you typically get 'error' for all bytes the sector/block.
So how do you want to correctly 'restore' missing full sectors with just 0.8% data overhead ??
Or is the device which fails to correct block returning something 'still usable' (since e.g. SATA disk certainly not)
Zdenek
Quoted 2 lines · Zdenek Kabelac
So how do you want to correctly 'restore' missing full sectors with just 0.8% data overhead ??
We use interleaving. Each byte in a 4k block is part of a different Reed-Solomon block, which means an entire lost 4k data block looks like a single error. When we also spread the bytes that form a single Reed-Solomon block across the partition, we end up being able to correct several megabytes of consecutive corrupted blocks with very small space overhead.
Sami
Mikulas Patocka
maintainerQuoted 11 lines · Sami Tolvanen
Quoted 2 lines · Zdenek Kabelac
So how do you want to correctly 'restore' missing full sectors with just 0.8% data overhead ??
We use interleaving. Each byte in a 4k block is part of a different Reed-Solomon block, which means an entire lost 4k data block looks like a single error. When we also spread the bytes that form a single Reed-Solomon block across the partition, we end up being able to correct several megabytes of consecutive corrupted blocks with very small space overhead.
Sami
But the patch doesn't do any correction in case of I/O error - it just returns the bio with I/O error.
BTW. the function verity_fec_alloc_buffers does vzalloc and GFP_KERNEL kmalloc inside I/O handling code - that shouldn't be done - you should preallocate the data structures when the device is loaded.
Mikulas
Mikulas Patocka
maintainerQuoted 5 lines · Sami Tolvanen
Quoted 2 lines · Zdenek Kabelac
i.e. you have 1G of space - you want to give 250MB as 'redundancy' - so create 4 partition....
We cannot afford to set aside 25% of read-only partition space for
You can have 20 raid5 legs (with as big chunksizes as possible - so that sequential accesses are really sequential when they hit the flash device), and that means setting aside only 5%. Or even more legs.
Mikulas
Quoted 6 lines
redundancy on mobile devices, and would rather not impact performance any more than dm-verity already does. With error correction we have 0.8% space overhead in our use case and no performance degradation if the partition is not corrupted.
Sami
Mikulas Patocka
maintainerQuoted 9 lines · Sami Tolvanen
Quoted 2 lines · Mikulas Patocka
I'm also wondering what is this patch useful for. Disks and flash controllers have their own error detection and correction
I think I addressed this earlier. Some storage devices are able to correct bit flips, but don't have enough redundancy to correct larger errors. Using this patch set we can correct N MiB of consecutive corruption anywhere on the partition with the same amount of storage overhead.
So, why doesn't the patch correct I/O errors? It is more likely that the flash controller returns an I/O error than corrupted data. Why are you correcting corrupted data (that is unlikely) and not correcting I/O errors that are likely?
Quoted 7 lines
Quoted 2 lines
Another point - if the read-only system partition is experiencing some errors, than the read-write partition will probably have errors too
On mobile devices, errors in read-only partitions often lead to bricked devices while errors in the read-write parts might only lead to lost cat photos. There are situations where people would prefer to have a working phone even if it fails to store some of their data.
The read-write partition holds compiled applications and I doubt the smartphone would work if there were random bits flipped.
Quoted 7 lines
Quoted 2 lines
Do you have some real case where such error corrections increase longevity of some device?
Yes, there have been several cases where read-only partition errors have rendered a device unusable. The sheer volume of mobile devices means that even if a tiny fraction of them suffer from such a problem, it's going to affect a large number of people.
Why don't you reflash the device from bootloader? (by holding power and volume keys simultaneously on startup and using the fastboot utility)
Quoted 5 lines
Quoted 2 lines
But you can take raid5 in read-only mode, put it on several partitions protected with dm-verity and you get decent error correction
I agree. Unfortunately, we don't currently have the luxury of using raid on mobile devices.
Why not, it's just a simple kernel option. If raid5 already does data correction, there is no reason why to duplicate this work.
Quoted 1 line
Sami
Mikulas
Quoted 8 lines · Mikulas Patocka
Quoted 4 lines · Sami Tolvanen
Quoted 2 lines · Mikulas Patocka
Do you have some real case where such error corrections increase longevity of some device?
Quoted 7 lines
Quoted 4 lines
Yes, there have been several cases where read-only partition errors have rendered a device unusable. The sheer volume of mobile devices means that even if a tiny fraction of them suffer from such a problem, it's going to affect a large number of people.
Why don't you reflash the device from bootloader? (by holding power and volume keys simultaneously on startup and using the fastboot utility)
Requiring an end user to re-flash their device is not good business practice, even if it is a rare occurrence (it adds a potential attack-vector for malware, and is decidedly non-trivial to do for someone without programming background). Phones, tablets, and other embedded systems are the type of thing where the device needs to be usable when the user wants to access it, period. Minimizing the chances of the device not working (even for less common causes like this patch tries to protect against) is crucial to making the user experience as good as possible (and reducing customer support costs).
v2 cover dm verity: add support for error correction
In reply to Sami TolvanenChanges since v1:
- Added CONFIG_DM_VERITY_FEC and split error correction into dm-verity-fec.[ch] to further separate the functionality from the rest of dm-verity. Follows the same pattern as dm-uevent.
- Added missing dependencies for REED_SOLOMON to Kconfig.
- Renamed dm-verity.c to dm-verity-target.c to allow an optional object to be added. Follows the naming convention of dm-cache and dm-era.
- Changed the algorithm to work with one or more small buffers (~4k) instead of a single large one. The more buffers we can allocate, the faster it will work, but we don't have to preallocate a large amount of memory anymore.
- Changed memory allocation to use mempools. v2 preallocates all the memory required for each worker thread to guarantee forward progress in case of memory pressure. The code attempts to allocate more buffers (using GFP_NOIO) and uses them if available.
- Added graceful handling of IO errors, which are now treated as any other corruption.
- Rebased against linux-dm/for-next.
Sami Tolvanen (2):
dm verity: add support for forward error correction dm verity: ignore zero blocks
Documentation/device-mapper/verity.txt | 30 +
drivers/md/Kconfig | 12 +
drivers/md/Makefile | 5 +
drivers/md/dm-verity-fec.c | 836 +++++++++++++++++++++++++
drivers/md/dm-verity-fec.h | 146 +++++
drivers/md/{dm-verity.c => dm-verity-target.c} | 320 ++++++----
drivers/md/dm-verity.h | 129 ++++
7 files changed, 1343 insertions(+), 135 deletions(-)
create mode 100644 drivers/md/dm-verity-fec.c
create mode 100644 drivers/md/dm-verity-fec.h
rename drivers/md/{dm-verity.c => dm-verity-target.c} (82%)
create mode 100644 drivers/md/dm-verity.hSignature · 1 line
2.6.0.rc2.230.g3dd15c0
PATCH v2 1/2 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.
---
Documentation/device-mapper/verity.txt | 25 +
drivers/md/Kconfig | 12 +
drivers/md/Makefile | 5 +
drivers/md/dm-verity-fec.c | 830 +++++++++++++++++++++++++
drivers/md/dm-verity-fec.h | 146 +++++
drivers/md/{dm-verity.c => dm-verity-target.c} | 244 ++++----
drivers/md/dm-verity.h | 128 ++++
7 files changed, 1259 insertions(+), 131 deletions(-)
create mode 100644 drivers/md/dm-verity-fec.c
create mode 100644 drivers/md/dm-verity-fec.h
rename drivers/md/{dm-verity.c => dm-verity-target.c} (84%)
create mode 100644 drivers/md/dm-verity.hDocumentation/device-mapper/verity.txt +25 -0
@@ -79,6 +79,31 @@ 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. + +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 <data_block_size>. + +fec_start + This is the offset, in <data_block_size> blocks, from the start of the + FEC device to the beginning of the encoding data. + + Theory of operation ===================
drivers/md/Kconfig +12 -0
@@ -467,6 +467,18 @@ config DM_VERITY If unsure, say N. +config DM_VERITY_FEC + bool "Verity forward error correction support" + depends on DM_VERITY + select REED_SOLOMON + select REED_SOLOMON_DEC8 + ---help--- + Add forward error correction support to dm-verity. This option + makes it possible to use pre-generated error correction data to + recover from corrupted blocks. + + If unsure, say N. + config DM_SWITCH tristate "Switch target support (EXPERIMENTAL)" depends on BLK_DEV_DM
drivers/md/Makefile +5 -0
@@ -16,6 +16,7 @@ dm-cache-mq-y += dm-cache-policy-mq.o dm-cache-smq-y += dm-cache-policy-smq.o dm-cache-cleaner-y += dm-cache-policy-cleaner.o dm-era-y += dm-era-target.o +dm-verity-y += dm-verity-target.o md-mod-y += md.o bitmap.o raid456-y += raid5.o raid5-cache.o
@@ -63,3 +64,7 @@ obj-$(CONFIG_DM_LOG_WRITES) += dm-log-writes.o ifeq ($(CONFIG_DM_UEVENT),y) dm-mod-objs += dm-uevent.o endif + +ifeq ($(CONFIG_DM_VERITY_FEC),y) +dm-verity-objs += dm-verity-fec.o +endif
drivers/md/dm-verity-fec.c new file +830 -0
830 lines not on this page · raw message
drivers/md/dm-verity-fec.h new file +146 -0
146 lines not on this page · raw message
drivers/md/dm-verity-target.c renamed from drivers/md/dm-verity.c +113 -131
406 lines not on this page · raw message
drivers/md/dm-verity.h new file +128 -0
128 lines not on this page · raw message
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
PATCH v2 2/2 dm verity: ignore zero blocks
In reply to Sami TolvanenAdd ignore_zero_blocks option, which returns zeros for blocks matching a zero hash without validating the content.
--- Documentation/device-mapper/verity.txt | 5 ++ drivers/md/dm-verity-fec.c | 8 +++- drivers/md/dm-verity-target.c | 84 ++++++++++++++++++++++++++++++---- drivers/md/dm-verity.h | 3 +- 4 files changed, 90 insertions(+), 10 deletions(-)
Documentation/device-mapper/verity.txt +5 -0
@@ -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
drivers/md/dm-verity-fec.c +7 -1
@@ -210,6 +210,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;
@@ -270,7 +271,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
drivers/md/dm-verity-target.c +76 -8
162 lines not on this page · raw message
drivers/md/dm-verity.h +2 -1
@@ -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 */
Signature · 1 line
2.6.0.rc2.230.g3dd15c0
Quoted 22 lines · Sami Tolvanen
Changes since v1:
- Added
CONFIG_DM_VERITY_FECand split error correction into dm-verity-fec.[ch] to further separate the functionality from the rest of dm-verity. Follows the same pattern as dm-uevent.- Added missing dependencies for
REED_SOLOMONtoKconfig.- Renamed
dm-verity.ctodm-verity-target.cto allow an optional object to be added. Follows the naming convention of dm-cache and dm-era.- Changed the algorithm to work with one or more small buffers (~4k) instead of a single large one. The more buffers we can allocate, the faster it will work, but we don't have to preallocate a large amount of memory anymore.
- Changed memory allocation to use mempools. v2 preallocates all the memory required for each worker thread to guarantee forward progress in case of memory pressure. The code attempts to allocate more buffers (using
GFP_NOIO) and uses them if available.
Quoted 4 lines
- Added graceful handling of IO errors, which are now treated as any other corruption.
- Rebased against linux-dm/for-next.
Thanks a lot for these advances, at a high-level it sounds like you've handled the issues raised as part of v1 review very well.
I'll review closer now. Goal is to get these changes staged in linux-next for upstream inclusion during the 4.5 merge window.
Quoted 28 lines · Mike Snitzer
Quoted 25 lines · Sami Tolvanen
Changes since v1:
- Added
CONFIG_DM_VERITY_FECand split error correction into dm-verity-fec.[ch] to further separate the functionality from the rest of dm-verity. Follows the same pattern as dm-uevent.- Added missing dependencies for
REED_SOLOMONtoKconfig.- Renamed
dm-verity.ctodm-verity-target.cto allow an optional object to be added. Follows the naming convention of dm-cache and dm-era.- Changed the algorithm to work with one or more small buffers (~4k) instead of a single large one. The more buffers we can allocate, the faster it will work, but we don't have to preallocate a large amount of memory anymore.
- Changed memory allocation to use mempools. v2 preallocates all the memory required for each worker thread to guarantee forward progress in case of memory pressure. The code attempts to allocate more buffers (using
GFP_NOIO) and uses them if available.- Added graceful handling of IO errors, which are now treated as any other corruption.
Quoted 7 lines
Quoted 1 line
- Rebased against linux-dm/for-next.
Thanks a lot for these advances, at a high-level it sounds like you've handled the issues raised as part of v1 review very well.
I'll review closer now. Goal is to get these changes staged in linux-next for upstream inclusion during the 4.5 merge window.
I took a first pass through your code and pushed the result to this temporary branch here:
http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/log/?h=dm-verity-fec
As you'll see, I focused primarily on splitting the dm-verity core changes out from the FEC and ignore_zero_blocks changes.
Along the way I tweaked some style-nits here or there but the biggest difference between your v2 and what I pushed is captured in this commit:
http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/commit/?h=dm-verity-fec&id=cc1339fae225d8cdc8fffeff30f0a9981367d6c0
If you're OK with those changes I'll fold that commit into your main FEC commit.
I'll carry on with reviewing your new code (outside of dm-verity core) tomorrow.
Mike
Quoted 2 lines · Mike Snitzer
If you're OK with those changes I'll fold that commit into your main FEC commit.
Yes, these changes look fine. Thanks!
Sami
Quoted 5 lines · Sami Tolvanen
Quoted 2 lines · Mike Snitzer
If you're OK with those changes I'll fold that commit into your main FEC commit.
Yes, these changes look fine. Thanks!
OK, I reviewed the FEC code and have staged it in linux-next with the following fixes/tweaks/nits folded in. Please let me know if you see any problems with this (I'm obviously not an 80-columns zealot).
I'm going to carry on reviewing aspects of memory allocations, table loads via ctr, etc.. but the code I've staged in linux-dm.git's 'for-next' is worth handing off to linux-next to see if it catches anything, see:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next
I'd really appreciate it if you could do some regression testing, etc on your end to verify I didn't break anything while tweaking things.
Thanks!
From: Mike Snitzer <[email protected]>
Date: Fri, 4 Dec 2015 15:49:58 -0500
Subject: [PATCH] dm verity fec: whitespace fixes and other small nits
--- drivers/md/dm-verity-fec.c | 153 +++++++++++++++++++-------------------------- 1 file changed, 65 insertions(+), 88 deletions(-)
drivers/md/dm-verity-fec.c +65 -88
@@ -69,18 +69,15 @@ static u8 *fec_read_parity(struct dm_verity *v, u64 rsb, int index, position = (index + rsb) * v->fec->roots; block = position >> v->data_dev_block_bits; - *offset = (unsigned )(position - (block << v->data_dev_block_bits)); res =dm_bufio_read (v->fec->bufio, v->fec->start + block, buf); -if (unlikely (IS_ERR (res))) {DMERR ("%s: FEC %llu: parity read failed (block %llu): %ld" , v->data_dev->name, (unsigned long long )rsb, (unsigned long long )(v->fec->start + block),PTR_ERR (res)); *buf =NULL ; -return NULL ; }return res;
@@ -92,8 +89,7 @@ static u8 *fec_read_parity(struct dm_verity *v, u64 rsb, int index,/* Loop over each extra buffer slot. */ #define fec_for_each_extra_buffer (io, __i) \ - for (__i = DM_VERITY_FEC_BUF_PREALLOC; __i < DM_VERITY_FEC_BUF_MAX; \ - __i++) + for (__i = DM_VERITY_FEC_BUF_PREALLOC; __i < DM_VERITY_FEC_BUF_MAX; __i++)/* Loop over each allocated buffer. */ #define fec_for_each_buffer (io, __i) \
@@ -132,14 +128,14 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio, u64 rsb, int byte_index, unsigned block_offset, int neras) { - int r = -1, corrected = 0, res; + int r, corrected = 0, res;struct dm_buffer *buf;unsigned n, i, offset;u8 *par, *block; par =fec_read_parity (v, rsb, block_offset, &offset, &buf); -if (unlikely (!par)) -return r; +if (IS_ERR (par)) +return PTR_ERR (par);/* * Decode the RS blocks we have in bufs. Each RS block results in
@@ -148,9 +144,12 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,fec_for_each_buffer_rs_block (fio, n, i) { block =fec_buffer_rs_block (v, fio, n, i); res =fec_decode_rs8 (v, fio, block, &par[offset], neras); +if (res <0 ) { +dm_bufio_release (buf); -if (res <0 ) + r = res; goto error; + } corrected += res; fio->output[block_offset] = block[byte_index];
@@ -164,25 +163,20 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,if (offset >=1 << v->data_dev_block_bits) {dm_bufio_release (buf); - par =fec_read_parity (v, rsb, block_offset, &offset, - &buf); -if (unlikely (!par)) -return r; + par =fec_read_parity (v, rsb, block_offset, &offset, &buf); +if (unlikely (IS_ERR (par))) +return PTR_ERR (par); } } - done: r = corrected; error: -dm_bufio_release (buf); -if (r <0 && neras)DMERR_LIMIT ("%s: FEC %llu: failed to correct: %d" , v->data_dev->name, (unsigned long long )rsb, r);else if (r >0 )DMWARN_LIMIT ("%s: FEC %llu: corrected %d errors" , - v->data_dev->name, (unsigned long long )rsb, - r); + v->data_dev->name, (unsigned long long )rsb, r);return r; }
@@ -204,7 +198,7 @@ static int fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io,/* * 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. +* fits into buffers. Check for erasure locations if @neras is non-NULL. */ static int fec_read_bufs(struct dm_verity *v, struct dm_verity_io *io, u64 rsb, u64 target, unsigned block_offset,
@@ -299,7 +293,6 @@ static int fec_read_bufs(struct dm_verity *v, struct dm_verity_io *io, rs_block =fec_buffer_rs_block (v, fio, n, j); rs_block[i] = bbuf[k]; } - done:dm_bufio_release (buf); }
@@ -317,7 +310,6 @@ static int fec_alloc_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio)if (!fio->rs) { fio->rs =mempool_alloc (v->fec->rs_pool,0 ); -if (unlikely (!fio->rs)) {DMERR ("failed to allocate RS" );return -ENOMEM ;
@@ -329,7 +321,6 @@ static int fec_alloc_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio)continue ; fio->bufs[n] =mempool_alloc (v->fec->prealloc_pool,GFP_NOIO ); -if (unlikely (!fio->bufs[n])) {DMERR ("failed to allocate FEC buffer" );return -ENOMEM ;
@@ -342,12 +333,10 @@ static int fec_alloc_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio)continue ; fio->bufs[n] =mempool_alloc (v->fec->extra_pool,GFP_NOIO ); -/* we can manage with even one buffer if necessary */ if (unlikely (!fio->bufs[n]))break ; } - fio->nbufs = n;if (!fio->output) {
@@ -363,7 +352,7 @@ static int fec_alloc_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio) }/* -* Initialize buffers and clear erasures. fec_read_bufs assumes buffers are +* Initialize buffers and clear erasures. fec_read_bufs() assumes buffers are * zeroed before deinterleaving. */ static void fec_init_bufs (struct dm_verity *v,struct dm_verity_fec_io *fio)
@@ -371,27 +360,26 @@ static void fec_init_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio)unsigned n;fec_for_each_buffer (fio, n) -memset (fio->bufs[n],0 , - v->fec->rsn <<DM_VERITY_FEC_BUF_RS_BITS ); +memset (fio->bufs[n],0 , v->fec->rsn <<DM_VERITY_FEC_BUF_RS_BITS );memset (fio->erasures,0 ,sizeof (fio->erasures)); }/* * Decode all RS blocks in a single data block and return the target block -* (indicated by "offset") in fio->output. If use_erasures is non-zero, uses +* (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, -int use_erasures) +bool use_erasures) {int r, neras =0 ;unsigned pos; r =fec_alloc_bufs (v, fio);if (unlikely (r <0 )) -return -1 ; +return r;for (pos =0 ; pos <1 << v->data_dev_block_bits; ) {fec_init_bufs (v, fio);
@@ -418,9 +406,8 @@ static int fec_decode_rsb(struct dm_verity *v, struct dm_verity_io *io,if (memcmp (verity_io_real_digest (v, io),verity_io_want_digest (v, io), v->digest_size)) {DMERR_LIMIT ("%s: FEC %llu: failed to correct (%d erasures)" , - v->data_dev->name, (unsigned long long )rsb, - neras); -return -1 ; + v->data_dev->name, (unsigned long long )rsb, neras); +return -EILSEQ ; }return 0 ;
@@ -445,12 +432,12 @@ 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) { - int r = -1; + int r;struct dm_verity_fec_io *fio =fec_io (io);u64 offset, res, rsb;if (!verity_fec_is_enabled (v)) -return -1 ; +return -EOPNOTSUPP ;if (type ==DM_VERITY_BLOCK_TYPE_METADATA ) block += v->data_blocks;
@@ -481,12 +468,12 @@ int verity_fec_decode(struct dm_verity *v, struct dm_verity_io *io,* them first. Do a second attempt with erasures if the corruption is * bad enough. */ - r =fec_decode_rsb (v, io, fio, rsb, offset,0 ); -if (r <0 ) - r =fec_decode_rsb (v, io, fio, rsb, offset,1 ); - -if (r <0 ) -return r; + r =fec_decode_rsb (v, io, fio, rsb, offset, false); +if (r <0 ) { + r =fec_decode_rsb (v, io, fio, rsb, offset, true); +if (r <0 ) +return r; + }if (dest)memcpy (dest, fio->output,1 << v->data_dev_block_bits);
@@ -577,7 +564,6 @@ void verity_fec_dtr(struct dm_verity *v)if (f->dev)dm_put_device (v->ti, f->dev); - out:kfree (f); v->fec =NULL ;
@@ -610,13 +596,14 @@ int verity_fec_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v, unsigned *argc, const char *arg_name) { int r; +struct dm_target *ti = v->ti;const char *arg_value;unsigned long long num_ll;unsigned char num_c;char dummy;if (!*argc) { - v->ti->error ="FEC feature arguments require a value" ; + ti->error ="FEC feature arguments require a value" ;return -EINVAL ; }
@@ -624,9 +611,9 @@ int verity_fec_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v, (*argc)--;if (!strcasecmp (arg_name,DM_VERITY_OPT_FEC_DEV )) { - r =dm_get_device (v->ti, arg_value,FMODE_READ , &v->fec->dev); + r =dm_get_device (ti, arg_value,FMODE_READ , &v->fec->dev);if (r) { - v->ti->error ="FEC device lookup failed" ; + ti->error ="FEC device lookup failed" ;return r; }
@@ -634,7 +621,7 @@ int verity_fec_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,if (sscanf (arg_value,"%llu%c" , &num_ll, &dummy) !=1 || ((sector_t)(num_ll << (v->data_dev_block_bits -SECTOR_SHIFT )) >> (v->data_dev_block_bits -SECTOR_SHIFT ) != num_ll)) { - v->ti->error ="Invalid " DM_VERITY_OPT_FEC_BLOCKS ; + ti->error ="Invalid " DM_VERITY_OPT_FEC_BLOCKS ;return -EINVAL ; } v->fec->blocks = num_ll;
@@ -643,7 +630,7 @@ int verity_fec_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,if (sscanf (arg_value,"%llu%c" , &num_ll, &dummy) !=1 || ((sector_t)(num_ll << (v->data_dev_block_bits -SECTOR_SHIFT )) >> (v->data_dev_block_bits -SECTOR_SHIFT ) != num_ll)) { - v->ti->error ="Invalid " DM_VERITY_OPT_FEC_START ; + ti->error ="Invalid " DM_VERITY_OPT_FEC_START ;return -EINVAL ; } v->fec->start = num_ll;
@@ -652,13 +639,13 @@ int verity_fec_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,if (sscanf (arg_value,"%hhu%c" , &num_c, &dummy) !=1 || !num_c || num_c < (DM_VERITY_FEC_RSM -DM_VERITY_FEC_MAX_RSN ) || num_c > (DM_VERITY_FEC_RSM -DM_VERITY_FEC_MIN_RSN )) { - v->ti->error ="Invalid " DM_VERITY_OPT_FEC_ROOTS ; + ti->error ="Invalid " DM_VERITY_OPT_FEC_ROOTS ;return -EINVAL ; } v->fec->roots = num_c; }else { - v->ti->error ="Unrecognized verity FEC feature request" ; + ti->error ="Unrecognized verity FEC feature request" ;return -EINVAL ; }
@@ -677,8 +664,8 @@ int verity_fec_ctr_alloc(struct dm_verity *v) v->ti->error ="Cannot allocate FEC structure" ;return -ENOMEM ; } - v->fec = f; +return 0 ; }
@@ -689,6 +676,7 @@ int verity_fec_ctr_alloc(struct dm_verity *v)int verity_fec_ctr (struct dm_verity *v) {struct dm_verity_fec *f = v->fec; +struct dm_target *ti = v->ti;u64 hash_blocks;if (!verity_fec_is_enabled (v)) {
@@ -718,24 +706,22 @@ int verity_fec_ctr(struct dm_verity *v)* simplicity. */ if (v->data_dev_block_bits != v->hash_dev_block_bits) { - v->ti->error ="Block sizes must match to use FEC" ; + ti->error ="Block sizes must match to use FEC" ;return -EINVAL ; }if (!f->roots) { - v->ti->error ="Missing " DM_VERITY_OPT_FEC_ROOTS ; + ti->error ="Missing " DM_VERITY_OPT_FEC_ROOTS ;return -EINVAL ; } - f->rsn =DM_VERITY_FEC_RSM - f->roots;if (!f->blocks) { - v->ti->error ="Missing " DM_VERITY_OPT_FEC_BLOCKS ; + ti->error ="Missing " DM_VERITY_OPT_FEC_BLOCKS ;return -EINVAL ; } f->rounds = f->blocks; -if (do_div (f->rounds, f->rsn)) f->rounds++;
@@ -744,7 +730,7 @@ int verity_fec_ctr(struct dm_verity *v)* data_blocks and hash_blocks combined. */ if (f->blocks < v->data_blocks + hash_blocks || !f->rounds) { - v->ti->error ="Invalid " DM_VERITY_OPT_FEC_BLOCKS ; + ti->error ="Invalid " DM_VERITY_OPT_FEC_BLOCKS ;return -EINVAL ; }
@@ -753,89 +739,80 @@ int verity_fec_ctr(struct dm_verity *v)* it to be large enough. */ f->hash_blocks = f->blocks - v->data_blocks; -if (dm_bufio_get_device_size (v->bufio) < f->hash_blocks) { - v->ti->error ="Hash device is too small for " -DM_VERITY_OPT_FEC_BLOCKS ; + ti->error ="Hash device is too small for " +DM_VERITY_OPT_FEC_BLOCKS ;return -E2BIG ; } f->bufio =dm_bufio_client_create (f->dev->bdev, -1 << v->data_dev_block_bits, -1 ,0 ,NULL ,NULL ); - +1 << v->data_dev_block_bits, +1 ,0 ,NULL ,NULL );if (IS_ERR (f->bufio)) { - v->ti->error ="Cannot initialize dm-bufio" ; + ti->error ="Cannot initialize FEC bufio client" ;return PTR_ERR (f->bufio); }if (dm_bufio_get_device_size (f->bufio) < - (f->start + f->rounds * f->roots) - >> v->data_dev_block_bits) { - v->ti->error ="FEC device is too small" ; + ((f->start + f->rounds * f->roots) >> v->data_dev_block_bits)) { + ti->error ="FEC device is too small" ;return -E2BIG ; } f->data_bufio =dm_bufio_client_create (v->data_dev->bdev, -1 << v->data_dev_block_bits, -1 ,0 ,NULL ,NULL ); - +1 << v->data_dev_block_bits, +1 ,0 ,NULL ,NULL );if (IS_ERR (f->data_bufio)) { - v->ti->error ="Cannot initialize dm-bufio" ; + ti->error ="Cannot initialize FEC data bufio client" ;return PTR_ERR (f->data_bufio); }if (dm_bufio_get_device_size (f->data_bufio) < v->data_blocks) { - v->ti->error ="Data device is too small" ; + ti->error ="Data device is too small" ;return -E2BIG ; }/* Preallocate an rs_control structure for each worker thread */ f->rs_pool =mempool_create (num_online_cpus (), fec_rs_alloc, - fec_rs_free, (void *) v); - + fec_rs_free, (void *) v);if (!f->rs_pool) { - v->ti->error ="Cannot allocate RS pool" ; + ti->error ="Cannot allocate RS pool" ;return -ENOMEM ; } f->cache =kmem_cache_create ("dm_verity_fec_buffers" , - f->rsn <<DM_VERITY_FEC_BUF_RS_BITS , -0 ,0 ,NULL ); - + f->rsn <<DM_VERITY_FEC_BUF_RS_BITS , +0 ,0 ,NULL );if (!f->cache) { - v->ti->error ="Cannot create FEC buffer cache" ; + ti->error ="Cannot create FEC buffer cache" ;return -ENOMEM ; }/* Preallocate DM_VERITY_FEC_BUF_PREALLOC buffers for each thread */ f->prealloc_pool =mempool_create_slab_pool (num_online_cpus () * -DM_VERITY_FEC_BUF_PREALLOC , - f->cache); - +DM_VERITY_FEC_BUF_PREALLOC , + f->cache);if (!f->prealloc_pool) { - v->ti->error ="Cannot allocate FEC buffer prealloc pool" ; + ti->error ="Cannot allocate FEC buffer prealloc pool" ;return -ENOMEM ; } f->extra_pool =mempool_create_slab_pool (0 , f->cache); -if (!f->extra_pool) { - v->ti->error ="Cannot allocate FEC buffer extra pool" ; + ti->error ="Cannot allocate FEC buffer extra pool" ;return -ENOMEM ; }/* Preallocate an output buffer for each thread */ f->output_pool =mempool_create_kmalloc_pool (num_online_cpus (), -1 << v->data_dev_block_bits); - +1 << v->data_dev_block_bits);if (!f->output_pool) { - v->ti->error ="Cannot allocate FEC output pool" ; + ti->error ="Cannot allocate FEC output pool" ;return -ENOMEM ; }/* Reserve space for our per-bio data */ - v->ti->per_bio_data_size +=sizeof (struct dm_verity_fec_io ); + ti->per_bio_data_size +=sizeof (struct dm_verity_fec_io );return 0 ; }
Signature · 1 line
2.4.9 (Apple Git-60)
Quoted 3 lines · Mike Snitzer
I'd really appreciate it if you could do some regression testing, etc on your end to verify I didn't break anything while tweaking things.
Sure. The changes look fine. I applied them to my tree and everything still works as expected in my tests.
Thanks for taking the time to review the patches!
Sami
Quoted 7 lines · Sami Tolvanen
Quoted 3 lines · Mike Snitzer
I'd really appreciate it if you could do some regression testing, etc on your end to verify I didn't break anything while tweaking things.
Sure. The changes look fine. I applied them to my tree and everything still works as expected in my tests.
Great. Moving forward it'd be awesome if you could work to get your verity FEC support regression tests into cryptsetup's tests. We need a way to verify future DM and/or other kernel changes don't somehow cause this FEC support to regress.
Also, I know you said you'd be getting Milan a veritysetup patch soon. How are things going on that? Ideally that'll land in conjunction with the kernel's dm-verity FEC support.
Quoted 1 line
Thanks for taking the time to review the patches!
No problem, like I said I'll be reviewing the code further but at this point your changes seem to be on-track for upstream Linux 4.5 inclusion.
Mike
Quoted 2 lines · Mike Snitzer
Great. Moving forward it'd be awesome if you could work to get your verity FEC support regression tests into cryptsetup's tests.
Sure. These tests would basically involve generating a valid disk image, corrupting it up to the theoretical maximum, and verifying that dm-verity can correct it.
Quoted 2 lines
Also, I know you said you'd be getting Milan a veritysetup patch soon. How are things going on that?
I'm still planning to have a patch for him this week.
Sami
Quoted 7 lines · Sami Tolvanen
Quoted 2 lines · Mike Snitzer
Great. Moving forward it'd be awesome if you could work to get your verity FEC support regression tests into cryptsetup's tests.
Sure. These tests would basically involve generating a valid disk image, corrupting it up to the theoretical maximum, and verifying that dm-verity can correct it.
Does the code handle/report even the same type of data corruption for RS blocks? Or this is just silently ignored until data area corruption happens?
Sorry, I did not study the code here, I am just curious :)
(IOW I mean if data are ok but recovery metadata is corrupted.)
Milan
Quoted 9 lines · Milan Broz
Quoted 7 lines · Sami Tolvanen
Quoted 2 lines · Mike Snitzer
Great. Moving forward it'd be awesome if you could work to get your verity FEC support regression tests into cryptsetup's tests.
Sure. These tests would basically involve generating a valid disk image, corrupting it up to the theoretical maximum, and verifying that dm-verity can correct it.
Quoted 6 lines
Does the code handle/report even the same type of data corruption for RS blocks? Or this is just silently ignored until data area corruption happens?
Sorry, I did not study the code here, I am just curious :)(IOW I mean if data are ok but recovery metadata is corrupted.)
There is no preemptive accessing/checking of the RS blocks. Once a parity is needed for a given block, due to some corruption, the RS block will be accessed with:
fec_decode_bufs -> fec_read_parity() -> fec_decode_rs8() -> decode_rs8()
I'm not seeing any verification of the metadata in fec_read_parity() -- so it would seem that corrupt RS blocks would result in -EBADMSG being returned from decode_rs8() (by virtue of incorrect parity being passed to decode_rs8).
Sami (or others) am I right?
Quoted 6 lines · Mike Snitzer
I'm not seeing any verification of the metadata in
fec_read_parity()-- so it would seem that corrupt RS blocks would result in-EBADMSGbeing returned fromdecode_rs8()(by virtue of incorrect parity being passed todecode_rs8).Sami (or others) am I right?
Yes, decode_rs8 failing with -EBADMSG is one option. There are also two other cases:
1) If the parity data is only partially corrupted, it may still be possible to correct errors, provided that the actual data isn't too severely corrupted.
2) If there's too much corruption for Reed-Solomon to detect, it's also possible that decode_rs8 just returns bogus data, which we will catch when verifying the hash again. This is why combining error correction with integrity checking is essential.
In other words, the worst case is that we cannot correct errors for the blocks covered by the corrupted parity data.
Sami