Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1262817 > unrolled thread

[PATCH 0/4] dm verity: add support for error correction

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/4] dm verity: add support for error correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 03:10 +0100
    [PATCH 1/4] dm verity: clean up duplicate hashing code Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 03:10 +0100
    [PATCH 4/4] dm verity: ignore zero blocks Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 03:10 +0100
    [PATCH 3/4] dm verity: add support for forward error correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 03:10 +0100
      Re: [PATCH 3/4] dm verity: add support for forward error correction kbuild test robot <lkp@intel.com> - 2015-11-05 06:40 +0100
    [PATCH 2/4] dm verity: separate function for parsing opt args Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 03:10 +0100
    Re: [PATCH 0/4] dm verity: add support for error correction Milan Broz <mbroz@redhat.com> - 2015-11-05 08:40 +0100
      Re: [PATCH 0/4] dm verity: add support for error correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-05 18:40 +0100
        Re: [PATCH 0/4] dm verity: add support for error correction Mike Snitzer <snitzer@redhat.com> - 2015-11-09 17:40 +0100
          Re: [PATCH 0/4] dm verity: add support for error correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-09 20:20 +0100
            Re: [PATCH 0/4] dm verity: add support for error correction Mike Snitzer <snitzer@redhat.com> - 2015-11-09 21:00 +0100
            Re: [PATCH 0/4] dm verity: add support for error correction Milan Broz <mbroz@redhat.com> - 2015-11-12 11:40 +0100
            Re: [PATCH 0/4] dm verity: add support for error correction Mikulas Patocka <mpatocka@redhat.com> - 2015-11-12 20:00 +0100
      Re: [PATCH 0/4] dm verity: add support for error correction Mikulas Patocka <mpatocka@redhat.com> - 2015-11-06 18:30 +0100
        Re: [PATCH 0/4] dm verity: add support for error correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-06 20:10 +0100
          Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Zdenek Kabelac <zkabelac@redhat.com> - 2015-11-06 20:30 +0100
            Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-06 21:30 +0100
              Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Zdenek Kabelac <zkabelac@redhat.com> - 2015-11-06 22:10 +0100
                Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Sami Tolvanen <samitolvanen@google.com> - 2015-11-06 22:30 +0100
                  Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Mikulas Patocka <mpatocka@redhat.com> - 2015-11-07 16:30 +0100
              Re: [dm-devel] [PATCH 0/4] dm verity: add support for error  correction Mikulas Patocka <mpatocka@redhat.com> - 2015-11-07 16:30 +0100
          Re: [PATCH 0/4] dm verity: add support for error correction Mikulas Patocka <mpatocka@redhat.com> - 2015-11-07 16:20 +0100
            Re: [PATCH 0/4] dm verity: add support for error correction Austin S Hemmelgarn <ahferroin7@gmail.com> - 2015-11-09 16:10 +0100

Page 1 of 2  [1] 2  Next page →

#1262817 — [PATCH 0/4] dm verity: add support for error correction

This patch set adds error correction support to dm-verity, which
makes it possible to recover from data corruption in exchange of
increased space overhead.

The feature is implemented as part of dm-verity to take advantage
of the existing hash tree to improve performance and locate known
erasures.

Sami Tolvanen (4):
  dm verity: clean up duplicate hashing code
  dm verity: separate function for parsing opt args
  dm verity: add support for forward error correction
  dm verity: ignore zero blocks

 Documentation/device-mapper/verity.txt |   34 ++
 drivers/md/dm-verity.c                 | 1004 +++++++++++++++++++++++++++-----
 2 files changed, 892 insertions(+), 146 deletions(-)

-- 
2.6.0.rc2.230.g3dd15c0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1262818 — [PATCH 1/4] dm verity: clean up duplicate hashing code

Handle dm-verity salting in one place to simplify the code.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 drivers/md/dm-verity.c | 262 +++++++++++++++++++++++++++----------------------
 1 file changed, 147 insertions(+), 115 deletions(-)

diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index edc624b..487cb66 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -173,6 +173,84 @@ static sector_t verity_position_at_level(struct dm_verity *v, sector_t block,
 	return block >> (level * v->hash_per_block_bits);
 }
 
+/*
+ * Wrapper for crypto_shash_init, which handles verity salting.
+ */
+static int verity_hash_init(struct dm_verity *v, struct shash_desc *desc)
+{
+	int r;
+
+	desc->tfm = v->tfm;
+	desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
+
+	r = crypto_shash_init(desc);
+
+	if (unlikely(r < 0)) {
+		DMERR("crypto_shash_init failed: %d", r);
+		return r;
+	}
+
+	if (likely(v->version >= 1)) {
+		r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+		if (unlikely(r < 0)) {
+			DMERR("crypto_shash_update failed: %d", r);
+			return r;
+		}
+	}
+
+	return 0;
+}
+
+static int verity_hash_update(struct dm_verity *v, struct shash_desc *desc,
+			      const u8 *data, size_t len)
+{
+	int r = crypto_shash_update(desc, data, len);
+
+	if (unlikely(r < 0))
+		DMERR("crypto_shash_update failed: %d", r);
+
+	return r;
+}
+
+static int verity_hash_final(struct dm_verity *v, struct shash_desc *desc,
+			     u8 *digest)
+{
+	int r;
+
+	if (unlikely(!v->version)) {
+		r = crypto_shash_update(desc, v->salt, v->salt_size);
+
+		if (r < 0) {
+			DMERR("crypto_shash_update failed: %d", r);
+			return r;
+		}
+	}
+
+	r = crypto_shash_final(desc, digest);
+
+	if (unlikely(r < 0))
+		DMERR("crypto_shash_final failed: %d", r);
+
+	return r;
+}
+
+static int verity_hash(struct dm_verity *v, struct shash_desc *desc,
+		       const u8 *data, size_t len, u8 *digest)
+{
+	int r;
+
+	r = verity_hash_init(v, desc);
+	if (unlikely(r < 0))
+		return r;
+
+	r = verity_hash_update(v, desc, data, len);
+	if (unlikely(r < 0))
+		return r;
+
+	return verity_hash_final(v, desc, digest);
+}
+
 static void verity_hash_at_level(struct dm_verity *v, sector_t block, int level,
 				 sector_t *hash_block, unsigned *offset)
 {
@@ -253,10 +331,10 @@ out:
  * If "skip_unverified" is false, unverified buffer is hashed and verified
  * against current value of io_want_digest(v, io).
  */
-static int verity_verify_level(struct dm_verity_io *io, sector_t block,
-			       int level, bool skip_unverified)
+static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
+			       sector_t block, int level, bool skip_unverified,
+			       u8 *want_digest)
 {
-	struct dm_verity *v = io->v;
 	struct dm_buffer *buf;
 	struct buffer_aux *aux;
 	u8 *data;
@@ -273,75 +351,72 @@ static int verity_verify_level(struct dm_verity_io *io, sector_t block,
 	aux = dm_bufio_get_aux_data(buf);
 
 	if (!aux->hash_verified) {
-		struct shash_desc *desc;
-		u8 *result;
-
 		if (skip_unverified) {
 			r = 1;
 			goto release_ret_r;
 		}
 
-		desc = io_hash_desc(v, io);
-		desc->tfm = v->tfm;
-		desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
-		r = crypto_shash_init(desc);
-		if (r < 0) {
-			DMERR("crypto_shash_init failed: %d", r);
+		r = verity_hash(v, io_hash_desc(v, io),
+				data, 1 << v->hash_dev_block_bits,
+				io_real_digest(v, io));
+		if (unlikely(r < 0))
 			goto release_ret_r;
-		}
-
-		if (likely(v->version >= 1)) {
-			r = crypto_shash_update(desc, v->salt, v->salt_size);
-			if (r < 0) {
-				DMERR("crypto_shash_update failed: %d", r);
-				goto release_ret_r;
-			}
-		}
 
-		r = crypto_shash_update(desc, data, 1 << v->hash_dev_block_bits);
-		if (r < 0) {
-			DMERR("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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1262820 — [PATCH 4/4] dm verity: ignore zero blocks

Add ignore_zero_blocks option, which returns zeros for blocks matching a
zero hash without validating the content.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 Documentation/device-mapper/verity.txt |  5 ++
 drivers/md/dm-verity.c                 | 88 ++++++++++++++++++++++++++++++----
 2 files changed, 83 insertions(+), 10 deletions(-)

diff --git a/Documentation/device-mapper/verity.txt b/Documentation/device-mapper/verity.txt
index 3628d28..1b103b0 100644
--- a/Documentation/device-mapper/verity.txt
+++ b/Documentation/device-mapper/verity.txt
@@ -79,6 +79,11 @@ restart_on_corruption
     not compatible with ignore_corruption and requires user space support to
     avoid restart loops.
 
+ignore_zero_blocks
+    Do not verify blocks that are expected to contain zeros and always return
+    zeros instead. This may be useful if the partition contains unused blocks
+    that are not guaranteed to contain zeros.
+
 use_fec_from_device
     Use forward error correction (FEC) to recover from corruption if hash
     verification fails. Use encoding data from the specified device. This
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index 61dec39..485d59e 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -38,6 +38,7 @@
 
 #define DM_VERITY_OPT_LOGGING		"ignore_corruption"
 #define DM_VERITY_OPT_RESTART		"restart_on_corruption"
+#define DM_VERITY_OPT_IGN_ZEROS		"ignore_zero_blocks"
 
 #define DM_VERITY_OPT_FEC_DEV		"use_fec_from_device"
 #define DM_VERITY_OPT_FEC_BLOCKS	"fec_blocks"
@@ -45,7 +46,7 @@
 #define DM_VERITY_OPT_FEC_ROOTS		"fec_roots"
 
 #define DM_VERITY_OPTS_FEC		8
-#define DM_VERITY_OPTS_MAX		(1 + DM_VERITY_OPTS_FEC)
+#define DM_VERITY_OPTS_MAX		(2 + DM_VERITY_OPTS_FEC)
 
 static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
 
@@ -74,6 +75,7 @@ struct dm_verity {
 	struct crypto_shash *tfm;
 	u8 *root_digest;	/* digest of the root block */
 	u8 *salt;		/* salt: its size is salt_size */
+	u8 *zero_digest;	/* digest for a zero block */
 	unsigned salt_size;
 	sector_t data_start;	/* data offset in 512-byte sectors */
 	sector_t hash_start;	/* hash start in blocks */
@@ -422,9 +424,9 @@ release_ret_r:
  * of the hash tree if necessary.
  */
 static int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
-				 sector_t block, u8 *digest)
+				 sector_t block, u8 *digest, bool *is_zero)
 {
-	int r, i;
+	int r = 0, i;
 
 	if (likely(v->levels)) {
 		/*
@@ -436,7 +438,7 @@ static int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
 		 */
 		r = verity_verify_level(v, io, block, 0, true, digest);
 		if (likely(r <= 0))
-			return r;
+			goto out;
 	}
 
 	memcpy(digest, v->root_digest, v->digest_size);
@@ -444,10 +446,16 @@ static int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
 	for (i = v->levels - 1; i >= 0; i--) {
 		r = verity_verify_level(v, io, block, i, false, digest);
 		if (unlikely(r))
-			return r;
+			goto out;
 	}
 
-	return 0;
+out:
+	if (!r && v->zero_digest)
+		*is_zero = !memcmp(v->zero_digest, digest, v->digest_size);
+	else
+		*is_zero = false;
+
+	return r;
 }
 
 /*
@@ -496,11 +504,19 @@ static int verity_bv_hash_update(struct dm_verity *v, struct dm_verity_io *io,
 	return verity_hash_update(v, io_hash_desc(v, io), data, len);
 }
 
+static int verity_bv_zero(struct dm_verity *v, struct dm_verity_io *io,
+			  u8 *data, size_t len)
+{
+	memset(data, 0, len);
+	return 0;
+}
+
 /*
  * Verify one "dm_verity_io" structure.
  */
 static int verity_verify_io(struct dm_verity_io *io)
 {
+	bool is_zero;
 	struct dm_verity *v = io->v;
 	struct bvec_iter start;
 	unsigned b;
@@ -510,10 +526,23 @@ static int verity_verify_io(struct dm_verity_io *io)
 		struct shash_desc *desc = io_hash_desc(v, io);
 
 		r = verity_hash_for_block(v, io, io->block + b,
-					  io_want_digest(v, io));
+					  io_want_digest(v, io), &is_zero);
 		if (unlikely(r < 0))
 			return r;
 
+		if (is_zero) {
+			/*
+			 * If we expect a zero block, don't validate, just
+			 * return zeros.
+			 */
+			r = verity_for_bv_block(v, io, &io->iter,
+						verity_bv_zero);
+			if (unlikely(r < 0))
+				return r;
+
+			continue;
+		}
+
 		r = verity_hash_init(v, desc);
 		if (unlikely(r < 0))
 			return r;
@@ -674,6 +703,7 @@ static int verity_fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io,
 static int verity_fec_read_buf(struct dm_verity *v, struct dm_verity_io *io,
 			       u64 rsb, u64 target, int *neras)
 {
+	bool is_zero;
 	int i, j, target_index = -1;
 	struct dm_buffer *buf;
 	struct dm_bufio_client *bufio;
@@ -713,9 +743,13 @@ static int verity_fec_read_buf(struct dm_verity *v, struct dm_verity_io *io,
 		}
 
 		if (block < v->data_blocks &&
-		    verity_hash_for_block(v, io, block, want_digest) == 0) {
-			if (neras && *neras <= v->fec_roots &&
-			    verity_fec_is_erasure(v, io, want_digest, bbuf))
+		    verity_hash_for_block(v, io, block, want_digest,
+					  &is_zero) == 0) {
+			if (is_zero)
+				memset(bbuf, 0, 1 << v->data_dev_block_bits);
+			else if (neras && *neras <= v->fec_roots &&
+				 verity_fec_is_erasure(v, io, want_digest,
+						       bbuf))
 				io->erasures[(*neras)++] = i;
 		}
 
@@ -1066,6 +1100,8 @@ static void verity_status(struct dm_target *ti, status_type_t type,
 				DMEMIT("%02x", v->salt[x]);
 		if (v->mode != DM_VERITY_MODE_EIO)
 			args++;
+		if (v->zero_digest)
+			args++;
 		if (v->fec_dev)
 			args += DM_VERITY_OPTS_FEC;
 		if (!args)
@@ -1084,6 +1120,8 @@ static void verity_status(struct dm_target *ti, status_type_t type,
 				BUG();
 			}
 		}
+		if (v->zero_digest)
+			DMEMIT(" " DM_VERITY_OPT_IGN_ZEROS);
 		if (v->fec_dev)
 			DMEMIT(" " DM_VERITY_OPT_FEC_DEV " %s "
 			       DM_VERITY_OPT_FEC_BLOCKS " %llu "
@@ -1148,6 +1186,7 @@ static void verity_dtr(struct dm_target *ti)
 
 	kfree(v->salt);
 	kfree(v->root_digest);
+	kfree(v->zero_digest);
 
 	if (v->tfm)
 		crypto_free_shash(v->tfm);
@@ -1164,6 +1203,29 @@ static void verity_dtr(struct dm_target *ti)
 	kfree(v);
 }
 
+static int verity_alloc_zero_digest(struct dm_verity *v)
+{
+	int r;
+	u8 desc[v->shash_descsize];
+	u8 *zero_data;
+
+	v->zero_digest = kmalloc(v->digest_size, GFP_KERNEL);
+
+	if (!v->zero_digest)
+		return -ENOMEM;
+
+	zero_data = kzalloc(1 << v->data_dev_block_bits, GFP_KERNEL);
+
+	if (!zero_data)
+		return -ENOMEM; /* verity_dtr will free zero_digest */
+
+	r = verity_hash(v, (struct shash_desc *)desc, zero_data,
+			1 << v->data_dev_block_bits, v->zero_digest);
+
+	kfree(zero_data);
+	return r;
+}
+
 static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
 				 const char *opt_string)
 {
@@ -1178,6 +1240,12 @@ static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
 	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART)) {
 		v->mode = DM_VERITY_MODE_RESTART;
 		return 0;
+	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_IGN_ZEROS)) {
+		r = verity_alloc_zero_digest(v);
+		if (r)
+			v->ti->error = "Cannot allocate zero digest";
+
+		return r;
 	}
 
 	/* Remaining arguments require a value */
-- 
2.6.0.rc2.230.g3dd15c0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1262821 — [PATCH 3/4] dm verity: add support for forward error correction

Add support for correcting corrupted blocks using Reed-Solomon.

This code uses RS(255, N) interleaved across data and hash
blocks. Each error-correcting block covers N bytes evenly
distributed across the combined total data, so that each byte is a
maximum distance away from the others. This makes it possible to
recover from several consecutive corrupted blocks with relatively
small space overhead.

In addition, using verity hashes to locate erasures nearly doubles
the effectiveness of error correction. Being able to detect
corrupted blocks also improves performance, because only corrupted
blocks need to corrected.

For a 2 GiB partition, RS(255, 253) (two parity bytes for each
253-byte block) can correct up to 16 MiB of consecutive corrupted
blocks if erasures can be located, and 8 MiB if they cannot, with
16 MiB space overhead.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 Documentation/device-mapper/verity.txt |  29 ++
 drivers/md/dm-verity.c                 | 689 ++++++++++++++++++++++++++++++---
 2 files changed, 673 insertions(+), 45 deletions(-)

diff --git a/Documentation/device-mapper/verity.txt b/Documentation/device-mapper/verity.txt
index e15bc1a..3628d28 100644
--- a/Documentation/device-mapper/verity.txt
+++ b/Documentation/device-mapper/verity.txt
@@ -79,6 +79,35 @@ restart_on_corruption
     not compatible with ignore_corruption and requires user space support to
     avoid restart loops.
 
+use_fec_from_device
+    Use forward error correction (FEC) to recover from corruption if hash
+    verification fails. Use encoding data from the specified device. This
+    may be the same device where data and hash blocks reside, in which case
+    fec_start must be outside data and hash areas.
+
+    If the encoding data covers additional metadata, it must be accessible
+    on the hash device after the hash blocks.
+
+    Note: block sizes for data and hash devices must match.
+
+    A command line tool for generating encoding data is available from the
+    Android Open Source Project:
+    https://android.googlesource.com/platform/system/extras/+/master/verity/fec/
+
+fec_roots
+    Number of generator roots. This equals to the number of parity bytes in
+    the encoding data. For example, in RS(M, N) encoding, the number of roots
+    is M-N.
+
+fec_blocks
+    The number of encoding data blocks on the FEC device. The block size for
+    the FEC device is <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
 ===================
 
diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index da76f77..61dec39 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2012 Red Hat, Inc.
+ * Copyright (C) 2015 Google, Inc.
  *
  * Author: Mikulas Patocka <mpatocka@redhat.com>
  *
@@ -19,6 +20,8 @@
 #include <linux/module.h>
 #include <linux/device-mapper.h>
 #include <linux/reboot.h>
+#include <linux/rslib.h>
+#include <linux/vmalloc.h>
 #include <crypto/hash.h>
 
 #define DM_MSG_PREFIX			"verity"
@@ -31,10 +34,18 @@
 #define DM_VERITY_MAX_LEVELS		63
 #define DM_VERITY_MAX_CORRUPTED_ERRS	100
 
+#define DM_VERITY_FEC_RSM		255
+
 #define DM_VERITY_OPT_LOGGING		"ignore_corruption"
 #define DM_VERITY_OPT_RESTART		"restart_on_corruption"
 
-#define DM_VERITY_OPTS_MAX		1
+#define DM_VERITY_OPT_FEC_DEV		"use_fec_from_device"
+#define DM_VERITY_OPT_FEC_BLOCKS	"fec_blocks"
+#define DM_VERITY_OPT_FEC_START		"fec_start"
+#define DM_VERITY_OPT_FEC_ROOTS		"fec_roots"
+
+#define DM_VERITY_OPTS_FEC		8
+#define DM_VERITY_OPTS_MAX		(1 + DM_VERITY_OPTS_FEC)
 
 static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
 
@@ -54,8 +65,11 @@ enum verity_block_type {
 struct dm_verity {
 	struct dm_dev *data_dev;
 	struct dm_dev *hash_dev;
+	struct dm_dev *fec_dev;
 	struct dm_target *ti;
-	struct dm_bufio_client *bufio;
+	struct dm_bufio_client *data_bufio;
+	struct dm_bufio_client *hash_bufio;
+	struct dm_bufio_client *fec_bufio;
 	char *alg_name;
 	struct crypto_shash *tfm;
 	u8 *root_digest;	/* digest of the root block */
@@ -65,11 +79,17 @@ struct dm_verity {
 	sector_t hash_start;	/* hash start in blocks */
 	sector_t data_blocks;	/* the number of data blocks */
 	sector_t hash_blocks;	/* the number of hash blocks */
+	sector_t fec_start;	/* FEC data start in blocks */
+	sector_t fec_blocks;	/* number of blocks covered by FEC */
+	sector_t fec_rounds;	/* number of FEC rounds */
+	sector_t fec_hash_blocks;		/* blocks after hash_start */
 	unsigned char data_dev_block_bits;	/* log2(data blocksize) */
 	unsigned char hash_dev_block_bits;	/* log2(hash blocksize) */
 	unsigned char hash_per_block_bits;	/* log2(hashes in hash block) */
 	unsigned char levels;	/* the number of tree levels */
 	unsigned char version;
+	unsigned char fec_roots;/* number of parity bytes, M-N of RS(M, N) */
+	unsigned char fec_rsn;	/* N of RS(M, N) */
 	unsigned digest_size;	/* digest size for the current hash algorithm */
 	unsigned shash_descsize;/* the size of temporary space for crypto */
 	int hash_failed;	/* set to 1 if hash of any block failed */
@@ -96,6 +116,11 @@ struct dm_verity_io {
 
 	struct work_struct work;
 
+	struct rs_control *rs;
+	int *erasures;
+	size_t fec_pos;
+	u8 *fec_buf;
+
 	/*
 	 * Three variably-size fields follow this struct:
 	 *
@@ -148,7 +173,7 @@ struct buffer_aux {
 /*
  * Initialize struct buffer_aux for a freshly created buffer.
  */
-static void dm_bufio_alloc_callback(struct dm_buffer *buf)
+static void dm_hash_bufio_alloc_callback(struct dm_buffer *buf)
 {
 	struct buffer_aux *aux = dm_bufio_get_aux_data(buf);
 
@@ -322,6 +347,10 @@ out:
 	return 1;
 }
 
+static 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);
+
 /*
  * Verify hash of a metadata block pertaining to the specified data block
  * ("block" argument) at a specified level ("level" argument).
@@ -346,7 +375,7 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
 
 	verity_hash_at_level(v, block, level, &hash_block, &offset);
 
-	data = dm_bufio_read(v->bufio, hash_block, &buf);
+	data = dm_bufio_read(v->hash_bufio, hash_block, &buf);
 	if (IS_ERR(data))
 		return PTR_ERR(data);
 
@@ -367,6 +396,10 @@ static int verity_verify_level(struct dm_verity *v, struct dm_verity_io *io,
 		if (likely(memcmp(io_real_digest(v, io), want_digest,
 				  v->digest_size) == 0))
 			aux->hash_verified = 1;
+		else if (verity_fec_decode(v, io,
+					   DM_VERITY_BLOCK_TYPE_METADATA,
+					   hash_block, data, NULL) == 0)
+			aux->hash_verified = 1;
 		else if (verity_handle_err(v,
 					   DM_VERITY_BLOCK_TYPE_METADATA,
 					   hash_block)) {
@@ -391,8 +424,7 @@ release_ret_r:
 static int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
 				 sector_t block, u8 *digest)
 {
-	int i;
-	int r;
+	int r, i;
 
 	if (likely(v->levels)) {
 		/*
@@ -419,18 +451,62 @@ static int verity_hash_for_block(struct dm_verity *v, struct dm_verity_io *io,
 }
 
 /*
+ * Calls function f for 1 << v->data_dev_block_bits bytes in io->io_vec
+ * starting from (vector, offset). Assumes io->io_vec has enough data to
+ * process.
+ */
+static int verity_for_bv_block(struct dm_verity *v, struct dm_verity_io *io,
+			       struct bvec_iter *iter,
+			       int (*process)(struct dm_verity *v,
+					      struct dm_verity_io *io,
+					      u8 *data, size_t len))
+{
+	unsigned todo = 1 << v->data_dev_block_bits;
+	struct bio *bio = dm_bio_from_per_bio_data(io,
+						   v->ti->per_bio_data_size);
+
+	do {
+		int r;
+		u8 *page;
+		unsigned len;
+		struct bio_vec bv = bio_iter_iovec(bio, *iter);
+
+		page = kmap_atomic(bv.bv_page);
+		len = bv.bv_len;
+
+		if (likely(len >= todo))
+			len = todo;
+
+		r = process(v, io, page + bv.bv_offset, len);
+		kunmap_atomic(page);
+
+		if (r < 0)
+			return r;
+
+		bio_advance_iter(bio, iter, len);
+		todo -= len;
+	} while (todo);
+
+	return 0;
+}
+
+static int verity_bv_hash_update(struct dm_verity *v, struct dm_verity_io *io,
+				 u8 *data, size_t len)
+{
+	return verity_hash_update(v, io_hash_desc(v, io), data, len);
+}
+
+/*
  * Verify one "dm_verity_io" structure.
  */
 static int verity_verify_io(struct dm_verity_io *io)
 {
 	struct dm_verity *v = io->v;
-	struct bio *bio = dm_bio_from_per_bio_data(io,
-						   v->ti->per_bio_data_size);
+	struct bvec_iter start;
 	unsigned b;
 
 	for (b = 0; b < io->n_blocks; b++) {
 		int r;
-		unsigned todo;
 		struct shash_desc *desc = io_hash_desc(v, io);
 
 		r = verity_hash_for_block(v, io, io->block + b,
@@ -442,36 +518,24 @@ static int verity_verify_io(struct dm_verity_io *io)
 		if (unlikely(r < 0))
 			return r;
 
-		todo = 1 << v->data_dev_block_bits;
-		do {
-			u8 *page;
-			unsigned len;
-			struct bio_vec bv = bio_iter_iovec(bio, io->iter);
-
-			page = kmap_atomic(bv.bv_page);
-			len = bv.bv_len;
-			if (likely(len >= todo))
-				len = todo;
-			r = verity_hash_update(v, desc,  page + bv.bv_offset,
-					       len);
-			kunmap_atomic(page);
-
-			if (unlikely(r < 0))
-				return r;
-
-			bio_advance_iter(bio, &io->iter, len);
-			todo -= len;
-		} while (todo);
+		start = io->iter;
+		r = verity_for_bv_block(v, io, &io->iter,
+					verity_bv_hash_update);
+		if (unlikely(r < 0))
+			return r;
 
 		r = verity_hash_final(v, desc, io_real_digest(v, io));
 		if (unlikely(r < 0))
 			return r;
 
 		if (likely(memcmp(io_real_digest(v, io),
-				io_want_digest(v, io), v->digest_size) == 0))
+				  io_want_digest(v, io), v->digest_size) == 0))
+			continue;
+		else if (verity_fec_decode(v, io, DM_VERITY_BLOCK_TYPE_DATA,
+					   io->block + b, NULL, &start) == 0)
 			continue;
 		else if (verity_handle_err(v, DM_VERITY_BLOCK_TYPE_DATA,
-				io->block + b))
+					   io->block + b))
 			return -EIO;
 	}
 
@@ -479,6 +543,345 @@ static int verity_verify_io(struct dm_verity_io *io)
 }
 
 /*
+ * Returns an interleaved offset for a byte in RS block.
+ */
+static inline u64 verity_fec_interleave(struct dm_verity *v, u64 offset)
+{
+	u32 mod;
+
+	mod = do_div(offset, v->fec_rsn);
+	return offset + mod * (v->fec_rounds << v->data_dev_block_bits);
+}
+
+/*
+ * Decode a block using Reed-Solomon.
+ */
+static int verity_fec_decode_rs8(struct dm_verity *v,
+				 struct dm_verity_io *io, u8 *data, u8 *fec,
+				 int neras)
+{
+	int i;
+	uint16_t par[v->fec_roots];
+
+	for (i = 0; i < v->fec_roots; i++)
+		par[i] = fec[i];
+
+	return decode_rs8(io->rs, data, par, v->fec_rsn, NULL, neras,
+			  io->erasures, 0, NULL);
+}
+
+/*
+ * Read error-correcting codes for the requested RS block. Returns a pointer
+ * to the data block. Caller is responsible for releasing buf.
+ */
+static u8 *verity_fec_read_par(struct dm_verity *v, u64 rsb, int index,
+			       unsigned *offset, struct dm_buffer **buf)
+{
+	u64 block;
+	u8 *res;
+
+	block = (index + rsb) * v->fec_roots >> v->data_dev_block_bits;
+
+	*offset = (unsigned)((block << v->data_dev_block_bits) -
+			     (index + rsb) * v->fec_roots);
+
+	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;
+}
+
+/*
+ * Decode 1 << v->data_dev_block_bits FEC blocks from io->fec_buf and copy the
+ * corrected 'index' block to the beginning of the buffer.
+ */
+static int verity_fec_decode_buf(struct dm_verity *v, struct dm_verity_io *io,
+				 u64 rsb, int index, int neras)
+{
+	int r = -1, corrected = 0, i, res;
+	struct dm_buffer *buf;
+	unsigned offset;
+	u8 *par;
+
+	par = verity_fec_read_par(v, rsb, 0, &offset, &buf);
+	if (unlikely(!par))
+		return r;
+
+	for (i = 0; i < 1 << v->data_dev_block_bits; i++) {
+		if (offset >= 1 << v->data_dev_block_bits) {
+			dm_bufio_release(buf);
+
+			par = verity_fec_read_par(v, rsb, i, &offset, &buf);
+			if (unlikely(!par))
+				return r;
+		}
+
+		res = verity_fec_decode_rs8(v, io,
+				&io->fec_buf[i * v->fec_rsn], &par[offset],
+				neras);
+
+		if (res < 0)
+			goto out;
+
+		corrected += res;
+		offset += v->fec_roots;
+
+		/* copy corrected block to the beginning of fec_buf */
+		io->fec_buf[i] = io->fec_buf[i * v->fec_rsn + index];
+	}
+
+	r = corrected;
+
+out:
+	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);
+
+	return r;
+}
+
+/*
+ * Locate data block erasures using verity hashes.
+ */
+static int verity_fec_is_erasure(struct dm_verity *v, struct dm_verity_io *io,
+				 u8 *want_digest, u8 *data)
+{
+	if (unlikely(verity_hash(v, io_hash_desc(v, io),
+				 data, 1 << v->data_dev_block_bits,
+				 io_real_digest(v, io))))
+		return 0;
+
+	return memcmp(io_real_digest(v, io), want_digest, v->digest_size) != 0;
+}
+
+/*
+ * Read 1 << v->data_dev_block_bits interleaved FEC blocks into io->fec_buf
+ * and check for erasure locations if neras is non-NULL.
+ */
+static int verity_fec_read_buf(struct dm_verity *v, struct dm_verity_io *io,
+			       u64 rsb, u64 target, int *neras)
+{
+	int i, j, target_index = -1;
+	struct dm_buffer *buf;
+	struct dm_bufio_client *bufio;
+	u64 block, ileaved;
+	u8 *bbuf;
+	u8 want_digest[v->digest_size];
+
+	if (neras)
+		*neras = 0;
+
+	for (i = 0; i < v->fec_rsn; i++) {
+		ileaved = verity_fec_interleave(v, rsb * v->fec_rsn + i);
+
+		if (ileaved == target)
+			target_index = i;
+
+		block = ileaved >> v->data_dev_block_bits;
+		bufio = v->data_bufio;
+
+		if (block >= v->data_blocks) {
+			block -= v->data_blocks;
+
+			if (unlikely(block >= v->fec_hash_blocks))
+				continue;
+
+			block += v->hash_start;
+			bufio = v->hash_bufio;
+		}
+
+		bbuf = dm_bufio_read(bufio, block, &buf);
+
+		if (unlikely(IS_ERR(bbuf))) {
+			DMERR("%s: FEC %llu: read failed (block %llu): %ld",
+			      v->data_dev->name, (unsigned long long)rsb,
+			      (unsigned long long)block, PTR_ERR(bbuf));
+			return -1;
+		}
+
+		if (block < v->data_blocks &&
+		    verity_hash_for_block(v, io, block, want_digest) == 0) {
+			if (neras && *neras <= v->fec_roots &&
+			    verity_fec_is_erasure(v, io, want_digest, bbuf))
+				io->erasures[(*neras)++] = i;
+		}
+
+		for (j = 0; j < 1 << v->data_dev_block_bits; j++)
+			io->fec_buf[j * v->fec_rsn + i] = bbuf[j];
+
+		dm_bufio_release(buf);
+	}
+
+	return target_index;
+}
+
+/*
+ * Initialize Reed-Solomon and FEC buffers, and allocate them if needed.
+ */
+static int verity_fec_alloc_buffers(struct dm_verity *v,
+				    struct dm_verity_io *io)
+{
+	size_t bufsize;
+
+	if (!io->rs) {
+		io->rs = init_rs(8, 0x11d, 0, 1, v->fec_roots);
+
+		if (unlikely(!io->rs)) {
+			DMERR("init_rs failed");
+			return -ENOMEM;
+		}
+	}
+
+	bufsize = v->fec_rsn << v->data_dev_block_bits;
+
+	if (!io->fec_buf) {
+		io->fec_buf = vzalloc(bufsize);
+
+		if (unlikely(!io->fec_buf)) {
+			DMERR("vzalloc failed (%zu bytes)", bufsize);
+			return -ENOMEM;
+		}
+	} else
+		memset(io->fec_buf, 0, bufsize);
+
+	bufsize = v->fec_rsn * sizeof(int);
+
+	if (!io->erasures) {
+		io->erasures = kzalloc(bufsize, GFP_KERNEL);
+
+		if (unlikely(!io->erasures)) {
+			DMERR("kmalloc failed (%zu bytes)", bufsize);
+			return -ENOMEM;
+		}
+	} else
+		memset(io->erasures, 0, bufsize);
+
+	return 0;
+}
+
+/*
+ * Decode an interleaved RS block. If use_erasures is non-zero, uses hashes to
+ * locate erasures. If returns zero, the corrected block is in the beginning of
+ * io->fec_buf.
+ */
+static int verity_fec_decode_rsb(struct dm_verity *v,
+				 struct dm_verity_io *io, u64 rsb,
+				 u64 offset, int use_erasures)
+{
+	int r, neras = 0;
+
+	r = verity_fec_alloc_buffers(v, io);
+	if (unlikely(r < 0))
+		return -1;
+
+	r = verity_fec_read_buf(v, io, rsb, offset,
+				use_erasures ? &neras : NULL);
+	if (unlikely(r < 0))
+		return r;
+
+	r = verity_fec_decode_buf(v, io, rsb, r, neras);
+	if (r < 0)
+		return r;
+
+	r = verity_hash(v, io_hash_desc(v, io), io->fec_buf,
+			1 << v->data_dev_block_bits, io_real_digest(v, io));
+	if (unlikely(r < 0))
+		return r;
+
+	if (memcmp(io_real_digest(v, io), 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;
+	}
+
+	return 0;
+}
+
+static int verity_fec_bv_copy(struct dm_verity *v, struct dm_verity_io *io,
+			      u8 *data, size_t len)
+{
+	BUG_ON(io->fec_pos + len > 1 << v->data_dev_block_bits);
+	memcpy(data, &io->fec_buf[io->fec_pos], len);
+	io->fec_pos += len;
+	return 0;
+}
+
+/*
+ * Correct errors in a block. Copies corrected block to dest if non-NULL,
+ * otherwise to io->bio_vec starting from provided vector and offset.
+ */
+static 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;
+	u64 offset, res, rsb;
+
+	if (!v->fec_bufio)
+		return -1;
+
+	if (type == DM_VERITY_BLOCK_TYPE_METADATA)
+		block += v->data_blocks;
+
+	/*
+	 * For RS(M, N), the continuous FEC data is divided into blocks of N
+	 * bytes. Since block size may not be divisible by N, the last block
+	 * is zero padded when decoding.
+	 *
+	 * Each byte of the block is covered by a different RS(255, N) code,
+	 * and each code is interleaved over N blocks to make it less likely
+	 * that bursty corruption will leave us in unrecoverable state.
+	 */
+
+	offset = block << v->data_dev_block_bits;
+
+	res = offset;
+	do_div(res, v->fec_rounds << v->data_dev_block_bits);
+
+	/*
+	 * The base RS block we can feed to the interleaver to find out all
+	 * blocks required for decoding.
+	 */
+	rsb = offset - res * (v->fec_rounds << v->data_dev_block_bits);
+
+	/*
+	 * Locating erasures is slow, so attempt to recover the block without
+	 * them first. Do a second attempt with erasures if the corruption is
+	 * bad enough.
+	 */
+	r = verity_fec_decode_rsb(v, io, rsb, offset, 0);
+	if (r < 0)
+		r = verity_fec_decode_rsb(v, io, rsb, offset, 1);
+
+	if (r < 0)
+		return r;
+
+	if (dest)
+		memcpy(dest, io->fec_buf, 1 << v->hash_dev_block_bits);
+	else if (iter) {
+		io->fec_pos = 0;
+		r = verity_for_bv_block(v, io, iter, verity_fec_bv_copy);
+	}
+
+	return r;
+}
+
+
+/*
  * End one "io" structure with a given error.
  */
 static void verity_finish_io(struct dm_verity_io *io, int error)
@@ -490,6 +893,14 @@ static void verity_finish_io(struct dm_verity_io *io, int error)
 	bio->bi_private = io->orig_bi_private;
 	bio->bi_error = error;
 
+	if (io->rs)
+		free_rs(io->rs);
+
+	if (io->fec_buf)
+		vfree(io->fec_buf);
+
+	kfree(io->erasures);
+
 	bio_endio(bio);
 }
 
@@ -546,7 +957,7 @@ static void verity_prefetch_io(struct work_struct *work)
 				hash_block_end = v->hash_blocks - 1;
 		}
 no_prefetch_cluster:
-		dm_bufio_prefetch(v->bufio, hash_block_start,
+		dm_bufio_prefetch(v->hash_bufio, hash_block_start,
 				  hash_block_end - hash_block_start + 1);
 	}
 
@@ -608,6 +1019,10 @@ static int verity_map(struct dm_target *ti, struct bio *bio)
 	bio->bi_private = io;
 	io->iter = bio->bi_iter;
 
+	io->rs = NULL;
+	io->erasures = NULL;
+	io->fec_buf = NULL;
+
 	verity_submit_prefetch(v, io);
 
 	generic_make_request(bio);
@@ -622,6 +1037,7 @@ static void verity_status(struct dm_target *ti, status_type_t type,
 			  unsigned status_flags, char *result, unsigned maxlen)
 {
 	struct dm_verity *v = ti->private;
+	unsigned args = 0;
 	unsigned sz = 0;
 	unsigned x;
 
@@ -648,8 +1064,15 @@ static void verity_status(struct dm_target *ti, status_type_t type,
 		else
 			for (x = 0; x < v->salt_size; x++)
 				DMEMIT("%02x", v->salt[x]);
+		if (v->mode != DM_VERITY_MODE_EIO)
+			args++;
+		if (v->fec_dev)
+			args += DM_VERITY_OPTS_FEC;
+		if (!args)
+			return;
+		DMEMIT(" %u", args);
 		if (v->mode != DM_VERITY_MODE_EIO) {
-			DMEMIT(" 1 ");
+			DMEMIT(" ");
 			switch (v->mode) {
 			case DM_VERITY_MODE_LOGGING:
 				DMEMIT(DM_VERITY_OPT_LOGGING);
@@ -661,6 +1084,15 @@ static void verity_status(struct dm_target *ti, status_type_t type,
 				BUG();
 			}
 		}
+		if (v->fec_dev)
+			DMEMIT(" " DM_VERITY_OPT_FEC_DEV " %s "
+			       DM_VERITY_OPT_FEC_BLOCKS " %llu "
+			       DM_VERITY_OPT_FEC_START " %llu "
+			       DM_VERITY_OPT_FEC_ROOTS " %d",
+			       v->fec_dev->name,
+			       (unsigned long long)v->fec_blocks,
+			       (unsigned long long)v->fec_start,
+			       v->fec_roots);
 		break;
 	}
 }
@@ -707,8 +1139,12 @@ static void verity_dtr(struct dm_target *ti)
 	if (v->verify_wq)
 		destroy_workqueue(v->verify_wq);
 
-	if (v->bufio)
-		dm_bufio_client_destroy(v->bufio);
+	if (v->data_bufio)
+		dm_bufio_client_destroy(v->data_bufio);
+	if (v->hash_bufio)
+		dm_bufio_client_destroy(v->hash_bufio);
+	if (v->fec_bufio)
+		dm_bufio_client_destroy(v->fec_bufio);
 
 	kfree(v->salt);
 	kfree(v->root_digest);
@@ -718,11 +1154,12 @@ static void verity_dtr(struct dm_target *ti)
 
 	kfree(v->alg_name);
 
-	if (v->hash_dev)
-		dm_put_device(ti, v->hash_dev);
-
 	if (v->data_dev)
 		dm_put_device(ti, v->data_dev);
+	if (v->hash_dev)
+		dm_put_device(ti, v->hash_dev);
+	if (v->fec_dev)
+		dm_put_device(ti, v->fec_dev);
 
 	kfree(v);
 }
@@ -730,6 +1167,11 @@ static void verity_dtr(struct dm_target *ti)
 static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
 				 const char *opt_string)
 {
+	int r;
+	unsigned long long num_ll;
+	unsigned char num_c;
+	char dummy;
+
 	if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING)) {
 		v->mode = DM_VERITY_MODE_LOGGING;
 		return 0;
@@ -738,6 +1180,53 @@ static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
 		return 0;
 	}
 
+	/* Remaining arguments require a value */
+	if (!as->argc)
+		goto bad;
+
+	if (!strcasecmp(opt_string, DM_VERITY_OPT_FEC_DEV)) {
+		r = dm_get_device(v->ti, dm_shift_arg(as), FMODE_READ,
+					  &v->fec_dev);
+		if (r) {
+			v->ti->error = "FEC device lookup failed";
+			return r;
+		}
+
+		return 1;
+	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_FEC_BLOCKS)) {
+		if (sscanf(dm_shift_arg(as), "%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;
+			return -EINVAL;
+		}
+
+		v->fec_blocks = num_ll;
+		return 1;
+	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_FEC_START)) {
+		if (sscanf(dm_shift_arg(as), "%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;
+			return -EINVAL;
+		}
+
+		v->fec_start = num_ll;
+		return 1;
+	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_FEC_ROOTS)) {
+		if (sscanf(dm_shift_arg(as), "%hhu%c", &num_c, &dummy) != 1 ||
+		    !num_c || num_c >= DM_VERITY_FEC_RSM) {
+			v->ti->error = "Invalid " DM_VERITY_OPT_FEC_ROOTS;
+			return -EINVAL;
+		}
+
+		v->fec_roots = num_c;
+		return 1;
+	}
+
+bad:
 	v->ti->error = "Invalid feature arguments";
 	return -EINVAL;
 }
@@ -968,17 +1457,17 @@ static int verity_ctr(struct dm_target *ti, unsigned argc, char **argv)
 	}
 	v->hash_blocks = hash_position;
 
-	v->bufio = dm_bufio_client_create(v->hash_dev->bdev,
+	v->hash_bufio = dm_bufio_client_create(v->hash_dev->bdev,
 		1 << v->hash_dev_block_bits, 1, sizeof(struct buffer_aux),
-		dm_bufio_alloc_callback, NULL);
-	if (IS_ERR(v->bufio)) {
-		ti->error = "Cannot initialize dm-bufio";
-		r = PTR_ERR(v->bufio);
-		v->bufio = NULL;
+		dm_hash_bufio_alloc_callback, NULL);
+	if (IS_ERR(v->hash_bufio)) {
+		ti->error = "Cannot initialize dm-bufio for hash device";
+		r = PTR_ERR(v->hash_bufio);
+		v->hash_bufio = NULL;
 		goto bad;
 	}
 
-	if (dm_bufio_get_device_size(v->bufio) < v->hash_blocks) {
+	if (dm_bufio_get_device_size(v->hash_bufio) < v->hash_blocks) {
 		ti->error = "Hash device is too small";
 		r = -E2BIG;
 		goto bad;
@@ -994,6 +1483,115 @@ static int verity_ctr(struct dm_target *ti, unsigned argc, char **argv)
 		goto bad;
 	}
 
+	if (v->fec_dev) {
+		/*
+		 * FEC is computed over data blocks, hash blocks, and possible
+		 * metadata. In other words, FEC covers total of fec_blocks
+		 * blocks consisting of the following:
+		 *
+		 *  data blocks | hash blocks | metadata (optional)
+		 *
+		 * We allow metadata after hash blocks to support a use case
+		 * where all data is stored on the same device and FEC covers
+		 * the entire area.
+		 *
+		 * If metadata is included, we require it to be available on the
+		 * hash device after the hash blocks.
+		 */
+
+		u64 hash_blocks = v->hash_blocks - v->hash_start;
+
+		/*
+		 * Require matching block sizes for data and hash devices for
+		 * simplicity.
+		 */
+		if (v->data_dev_block_bits != v->hash_dev_block_bits) {
+			ti->error = "Block sizes must match to use FEC";
+			r = -EINVAL;
+			goto bad;
+		}
+
+		if (!v->fec_roots) {
+			ti->error = "Missing " DM_VERITY_OPT_FEC_ROOTS;
+			r = -EINVAL;
+			goto bad;
+		}
+
+		v->fec_rsn = DM_VERITY_FEC_RSM - v->fec_roots;
+
+		if (!v->fec_blocks) {
+			ti->error = "Missing " DM_VERITY_OPT_FEC_BLOCKS;
+			r = -EINVAL;
+			goto bad;
+		}
+
+		v->fec_rounds = v->fec_blocks;
+
+		if (do_div(v->fec_rounds, v->fec_rsn))
+			v->fec_rounds++;
+
+		/*
+		 * Due to optional metadata, fec_blocks can be larger than
+		 * data_blocks and hash_blocks combined.
+		 */
+		if (v->fec_blocks < v->data_blocks + hash_blocks ||
+				!v->fec_rounds) {
+			ti->error = "Invalid " DM_VERITY_OPT_FEC_BLOCKS;
+			r = -EINVAL;
+			goto bad;
+		}
+
+		/*
+		 * Metadata is accessed through the hash device, so we require
+		 * it to be large enough.
+		 */
+		v->fec_hash_blocks = v->fec_blocks - v->data_blocks;
+
+		if (dm_bufio_get_device_size(v->hash_bufio) <
+				v->fec_hash_blocks) {
+			ti->error = "Hash device is too small for "
+					DM_VERITY_OPT_FEC_BLOCKS;
+			r = -E2BIG;
+			goto bad;
+		}
+
+		v->fec_bufio = dm_bufio_client_create(v->fec_dev->bdev,
+					1 << v->data_dev_block_bits,
+					1, 0, NULL, NULL);
+
+		if (IS_ERR(v->fec_bufio)) {
+			ti->error = "Cannot initialize dm-bufio";
+			r = PTR_ERR(v->fec_bufio);
+			v->fec_bufio = NULL;
+			goto bad;
+		}
+
+		if (dm_bufio_get_device_size(v->fec_bufio) <
+				(v->fec_start + v->fec_rounds * v->fec_roots)
+				>> v->data_dev_block_bits) {
+			ti->error = "FEC device is too small";
+			r = -E2BIG;
+			goto bad;
+		}
+
+		v->data_bufio = dm_bufio_client_create(v->data_dev->bdev,
+					1 << v->data_dev_block_bits,
+					1, 0, NULL, NULL);
+
+		if (IS_ERR(v->data_bufio)) {
+			ti->error = "Cannot initialize dm-bufio";
+			r = PTR_ERR(v->data_bufio);
+			v->data_bufio = NULL;
+			goto bad;
+		}
+
+		if (dm_bufio_get_device_size(v->data_bufio) < v->data_blocks) {
+			ti->error = "Data device is too small";
+			r = -E2BIG;
+			goto bad;
+		}
+	}
+
 	return 0;
 
 bad:
@@ -1037,5 +1635,6 @@ module_exit(dm_verity_exit);
 MODULE_AUTHOR("Mikulas Patocka <mpatocka@redhat.com>");
 MODULE_AUTHOR("Mandeep Baines <msb@chromium.org>");
 MODULE_AUTHOR("Will Drewry <wad@chromium.org>");
+MODULE_AUTHOR("Sami Tolvanen <samitolvanen@google.com>");
 MODULE_DESCRIPTION(DM_NAME " target for transparent disk integrity checking");
 MODULE_LICENSE("GPL");
-- 
2.6.0.rc2.230.g3dd15c0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1262937 — Re: [PATCH 3/4] dm verity: add support for forward error correction

[Multipart message — attachments visible in raw view] — view raw

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

[toc] | [prev] | [next] | [standalone]

#1262822 — [PATCH 2/4] dm verity: separate function for parsing opt args

Move optional argument parsing into a separate function to make it
easier to add more of them without making verity_ctr even longer.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 drivers/md/dm-verity.c | 31 ++++++++++++++++++++++---------
 1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/drivers/md/dm-verity.c b/drivers/md/dm-verity.c
index 487cb66..da76f77 100644
--- a/drivers/md/dm-verity.c
+++ b/drivers/md/dm-verity.c
@@ -34,6 +34,8 @@
 #define DM_VERITY_OPT_LOGGING		"ignore_corruption"
 #define DM_VERITY_OPT_RESTART		"restart_on_corruption"
 
+#define DM_VERITY_OPTS_MAX		1
+
 static unsigned dm_verity_prefetch_cluster = DM_VERITY_DEFAULT_PREFETCH_SIZE;
 
 module_param_named(prefetch_cluster, dm_verity_prefetch_cluster, uint, S_IRUGO | S_IWUSR);
@@ -725,6 +727,21 @@ static void verity_dtr(struct dm_target *ti)
 	kfree(v);
 }
 
+static int verity_parse_opt_args(struct dm_arg_set *as, struct dm_verity *v,
+				 const char *opt_string)
+{
+	if (!strcasecmp(opt_string, DM_VERITY_OPT_LOGGING)) {
+		v->mode = DM_VERITY_MODE_LOGGING;
+		return 0;
+	} else if (!strcasecmp(opt_string, DM_VERITY_OPT_RESTART)) {
+		v->mode = DM_VERITY_MODE_RESTART;
+		return 0;
+	}
+
+	v->ti->error = "Invalid feature arguments";
+	return -EINVAL;
+}
+
 /*
  * Target parameters:
  *	<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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1262975

On 11/05/2015 03:02 AM, Sami Tolvanen wrote:
> 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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263446

On Thu, Nov 05, 2015 at 08:34:04AM +0100, Milan Broz wrote:
> could you please elaborate why is all this needed? To extend support
> of some faulty flash chips?

This makes dm-verity more robust against corruption caused by either
hardware or software bugs, both of which we have seen in the past on
actual devices.

Note that unlike the error correction sometimes included in flash
storage devices, this doesn't merely protect against random bit flips,
it makes it possible to recover from several megabytes of corrupted
or lost data.

> Do you have some statistics that there are really such correctable errors
> in real devices?

Sorry, I don't have statistics to share at the moment.

> Anyway, I really do not understand layer separation here.

I should have elaborated more on this. Implementing this without
integrity checking would not be feasible for a few reasons:

  1. Being able to detect which blocks are corrupted allows us to
     avoid correcting valid blocks. Correcting errors is slow and
     this is the only way to keep performance acceptable.

  2. Due to a property of erasure codes, we can correct twice as
     many errors if we know where the errors are. Using the hash
     tree to detect corrupted blocks lets us locate erasures.

  3. Error correction algorithms may not produce valid output and
     without integrity checking, there's no reliable way to detect
     when we actually succeeded in correcting a block.

> Are we sure this combination does not create some unintended
> gap in integrity checking?

Yes, I'm sure. Corrupted blocks are integrity checked again after they
are corrected to make sure only valid data is allowed to pass.

> Why the integrity check should even try to do some
> error correction if there is an intentional integrity attack?

Most corruption is not malicious and being able to recover from it
makes the system more reliable. This doesn't make it any easier for an
attacker to break dm-verity. That would still require finding a hash
collision (or being able to modify the hash tree).

> The second question - why are you writing another separate tool
> for maintenance for dm-verity when there is veritysetup?

Our tool for generating error correction metadata is independent from
dm-verity. This data is also used by other software to correct errors
during software updates, for example. If there's interest, I can help
in adding this functionality to veritysetup.

Sami
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1265836

On Thu, Nov 05 2015 at 12:33pm -0500,
Sami Tolvanen <samitolvanen@google.com> wrote:

> On Thu, Nov 05, 2015 at 08:34:04AM +0100, Milan Broz wrote:
> > could you please elaborate why is all this needed? To extend support
> > of some faulty flash chips?
> 
> This makes dm-verity more robust against corruption caused by either
> hardware or software bugs, both of which we have seen in the past on
> actual devices.
> 
> Note that unlike the error correction sometimes included in flash
> storage devices, this doesn't merely protect against random bit flips,
> it makes it possible to recover from several megabytes of corrupted
> or lost data.

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.

> > Do you have some statistics that there are really such correctable errors
> > in real devices?
> 
> Sorry, I don't have statistics to share at the moment.
> 
> > Anyway, I really do not understand layer separation here.
> 
> I should have elaborated more on this. Implementing this without
> integrity checking would not be feasible for a few reasons:
> 
>   1. Being able to detect which blocks are corrupted allows us to
>      avoid correcting valid blocks. Correcting errors is slow and
>      this is the only way to keep performance acceptable.
> 
>   2. Due to a property of erasure codes, we can correct twice as
>      many errors if we know where the errors are. Using the hash
>      tree to detect corrupted blocks lets us locate erasures.
> 
>   3. Error correction algorithms may not produce valid output and
>      without integrity checking, there's no reliable way to detect
>      when we actually succeeded in correcting a block.

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?

> > 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.

> > Why the integrity check should even try to do some
> > error correction if there is an intentional integrity attack?
> 
> Most corruption is not malicious and being able to recover from it
> makes the system more reliable. This doesn't make it any easier for an
> attacker to break dm-verity. That would still require finding a hash
> collision (or being able to modify the hash tree).
> 
> > The second question - why are you writing another separate tool
> > for maintenance for dm-verity when there is veritysetup?
> 
> Our tool for generating error correction metadata is independent from
> dm-verity. This data is also used by other software to correct errors
> during software updates, for example. If there's interest, I can help
> in adding this functionality to veritysetup.

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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1265955

On Mon, Nov 09, 2015 at 11:37:35AM -0500, Mike Snitzer wrote:
> 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.

> 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.

> 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.

> 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?

> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1265980

On Mon, Nov 09 2015 at  2:19pm -0500,
Sami Tolvanen <samitolvanen@google.com> wrote:

> On Mon, Nov 09, 2015 at 11:37:35AM -0500, Mike Snitzer wrote:
> > 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.
> 
> > 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.

> > 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.

> > 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?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1267798

On 11/09/2015 08:19 PM, Sami Tolvanen wrote:
...
> 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).

...

>> 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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1268206

On Mon, 9 Nov 2015, Sami Tolvanen wrote:

> > 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264180

On Thu, 5 Nov 2015, Milan Broz wrote:

> On 11/05/2015 03:02 AM, Sami Tolvanen wrote:
> > 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?

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?

> 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.

> The second question - why are you writing another separate tool
> for maintenance for dm-verity when there is veritysetup?
> 
> Milan

Mikulas
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264231

On Fri, Nov 06, 2015 at 12:23:29PM -0500, Mikulas Patocka wrote:
> 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.

> 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.

> 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.

> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264258 — Re: [dm-devel] [PATCH 0/4] dm verity: add support for error correction

Dne 6.11.2015 v 20:06 Sami Tolvanen napsal(a):
> On Fri, Nov 06, 2015 at 12:23:29PM -0500, Mikulas Patocka wrote:
>> 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.
>
>> 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.
>
>> 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.
>
>> 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



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264457 — Re: [dm-devel] [PATCH 0/4] dm verity: add support for error correction

On Fri, Nov 06, 2015 at 08:20:15PM +0100, Zdenek Kabelac wrote:
> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264553 — Re: [dm-devel] [PATCH 0/4] dm verity: add support for error correction

Dne 6.11.2015 v 21:27 Sami Tolvanen napsal(a):
> On Fri, Nov 06, 2015 at 08:20:15PM +0100, Zdenek Kabelac wrote:
>> 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...

>
> 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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264572 — Re: [dm-devel] [PATCH 0/4] dm verity: add support for error correction

On Fri, Nov 06, 2015 at 10:05:24PM +0100, Zdenek Kabelac wrote:
> 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1264863 — Re: [dm-devel] [PATCH 0/4] dm verity: add support for error correction

On Fri, 6 Nov 2015, Sami Tolvanen wrote:

> On Fri, Nov 06, 2015 at 10:05:24PM +0100, Zdenek Kabelac wrote:
> > 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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web