Skip to contentSkip to conversation

dm-verity: Fix FEC for RS roots non-aligned to block size

PATCH In review Milan Broz 3 participants 6 messages Feb 22, 2021 – Feb 23, 2021

Subsystems (2)
lore
Share & tools
lore

Milan Broz

author
#0 lore raw

PATCH 1/1 dm-verity: Fix FEC for RS roots non-aligned to block size

Optional Forward Error Correction (FEC) code in dm-verity uses Reed-Solomon code and should support roots from 2 to 24.

The error correction parity bytes (of roots lengths per RS block) are stored on a separate device in sequence without any padding.

Currently, to access FEC device, the dm-verity-fec code uses dm-bufio client with block size set to verity data block (usually 4096 or 512 bytes).

Because this block size is not divisible by some (most!) of the roots supported lengths, data repair cannot work for partially stored parity bytes.

This patch changes FEC device dm-bufio block size to "roots << SECTOR_SHIFT" where we can be sure that the full parity data is always available. (There cannot be partial FEC blocks because parity must cover whole sectors.)

Because the optional FEC starting offset could be unaligned to this new block size, we have to use dm_bufio_set_sector_offset() to configure it.

The problem is easily reproducible using veritysetup, here for example for roots=13:

  # create verity device with RS FEC
  dd if=/dev/urandom of=data.img bs=4096 count=8 status=none
  veritysetup format data.img hash.img --fec-device=fec.img --fec-roots=13 | awk '/^Root hash/{ print $3 }' >roothash
  # create an erasure that should be always repairable with this roots setting
  dd if=/dev/zero of=data.img conv=notrunc bs=1 count=8 seek=4088 status=none
  # try to read it through dm-verity
  veritysetup open data.img test hash.img --fec-device=fec.img --fec-roots=13 $(cat roothash)
  dd if=/dev/mapper/test of=/dev/null bs=4096 status=noxfer
  # wait for possible recursive recovery in kernel
  udevadm settle
  veritysetup close test

Without it, FEC code usually ends on unrecoverable failure in RS decoder:
device-mapper: verity-fec: 7:1: FEC 0: failed to correct: -74
...

With the patch, errors are properly repaired.
device-mapper: verity-fec: 7:1: FEC 0: corrected 8 errors
...

This problem is present in all kernels since the FEC code introduction (kernel 4.5).

AFAIK the problem is not visible in Android ecosystem because it always use default RS roots=2.

---
 drivers/md/dm-verity-fec.c | 23 +++++++++++++----------
 1 file changed, 13 insertions(+), 10 deletions(-)
drivers/md/dm-verity-fec.c +13 -10
index fb41b4f23c48..be170581eb69 100644
@@ -61,18 +61,18 @@ static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio,
 static u8 *fec_read_parity(struct dm_verity *v, u64 rsb, int index,
 			   unsigned *offset, struct dm_buffer **buf)
 {
-	u64 position, block;
+	u64 position, block, rem;
 	u8 *res;
 
 	position = (index + rsb) * v->fec->roots;
-	block = position >> v->data_dev_block_bits;
-	*offset = (unsigned)(position - (block << v->data_dev_block_bits));
+	block = div64_u64_rem(position, v->fec->roots << SECTOR_SHIFT, &rem);
+	*offset = (unsigned)rem;
 
-	res = dm_bufio_read(v->fec->bufio, v->fec->start + block, buf);
+	res = dm_bufio_read(v->fec->bufio, block, buf);
 	if (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),
+		      (unsigned long long)(block),
 		      PTR_ERR(res));
 		*buf = NULL;
 	}
@@ -155,7 +155,7 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,
 
 		/* read the next block when we run out of parity bytes */
 		offset += v->fec->roots;
-		if (offset >= 1 << v->data_dev_block_bits) {
+		if (offset >= (v->fec->roots << SECTOR_SHIFT)) {
 			dm_bufio_release(buf);
 
 			par = fec_read_parity(v, rsb, block_offset, &offset, &buf);
@@ -674,7 +674,7 @@ int verity_fec_ctr(struct dm_verity *v)
 {
 	struct dm_verity_fec *f = v->fec;
 	struct dm_target *ti = v->ti;
-	u64 hash_blocks;
+	u64 hash_blocks, start_blocks, fec_blocks;
 	int ret;
 
 	if (!verity_fec_is_enabled(v)) {
@@ -744,15 +744,18 @@ int verity_fec_ctr(struct dm_verity *v)
 	}
 
 	f->bufio = dm_bufio_client_create(f->dev->bdev,
-					  1 << v->data_dev_block_bits,
+					  f->roots << SECTOR_SHIFT,
 					  1, 0, NULL, NULL);
 	if (IS_ERR(f->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)) {
+	dm_bufio_set_sector_offset(f->bufio, f->start << v->data_dev_block_bits >> SECTOR_SHIFT);
+
+	start_blocks = div64_u64(f->start << v->data_dev_block_bits, v->fec->roots << SECTOR_SHIFT);
+	fec_blocks   = div64_u64(f->rounds * f->roots, v->fec->roots << SECTOR_SHIFT);
+	if (dm_bufio_get_device_size(f->bufio) < (start_blocks + fec_blocks)) {
 		ti->error = "FEC device is too small";
 		return -E2BIG;
 	}
Signature · 6 lines
2.30.1

--
dm-devel mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/dm-devel
author
#2 lore raw
Quoted 6 lines · Jérôme Carretero

I smoke-tested by fuzzing contiguous ranges of user data (not hash tree) and correction works up to the amount of added correction (since erasures are identified by hashes).

Thanks for testing!

Quoted 1 line

Since the fix looks obvious, this should probably CC to stable?

Yes, I forgot to add the tag, I think this should go to all stable kernels.

(It only needs dm_bufio_set_sector_offset() that was added later than FEC, IIRC.)

Milan

p.s.
There are also bugs in userspace veritysetup if FEC has hash area is stored on the same device, then code miscalculates parity bytes then. This will be fixed soon in next stable cryptsetup release.

--
dm-devel mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/dm-devel

Reviewed-by on v1 1/1
#3 lore raw
In reply to Milan Broz

Hi Milan,

Quoted 7 lines · Milan Broz

Optional Forward Error Correction (FEC) code in dm-verity uses Reed-Solomon code and should support roots from 2 to 24.

The error correction parity bytes (of roots lengths per RS block) are stored on a separate device in sequence without any padding.

Quoted 6 lines

Currently, to access FEC device, the dm-verity-fec code uses dm-bufio client with block size set to verity data block (usually 4096 or 512 bytes).

Because this block size is not divisible by some (most!) of the roots supported lengths, data repair cannot work for partially stored parity bytes.

Ah, good catch!

Quoted 28 lines

This patch changes FEC device dm-bufio block size to "roots << SECTOR_SHIFT" where we can be sure that the full parity data is always available. (There cannot be partial FEC blocks because parity must cover whole sectors.)

Because the optional FEC starting offset could be unaligned to this new block size, we have to use dm_bufio_set_sector_offset() to configure it.

The problem is easily reproducible using veritysetup, here for example for roots=13:

  # create verity device with RS FEC
  dd if=/dev/urandom of=data.img bs=4096 count=8 status=none
  veritysetup format data.img hash.img --fec-device=fec.img --fec-roots=13 | awk '/^Root hash/{ print $3 }' >roothash
  # create an erasure that should be always repairable with this roots setting
  dd if=/dev/zero of=data.img conv=notrunc bs=1 count=8 seek=4088 status=none
  # try to read it through dm-verity
  veritysetup open data.img test hash.img --fec-device=fec.img --fec-roots=13 $(cat roothash)
  dd if=/dev/mapper/test of=/dev/null bs=4096 status=noxfer
  # wait for possible recursive recovery in kernel
  udevadm settle
  veritysetup close test

Without it, FEC code usually ends on unrecoverable failure in RS decoder:
device-mapper: verity-fec: 7:1: FEC 0: failed to correct: -74
...

Quoted 8 lines

With the patch, errors are properly repaired.
device-mapper: verity-fec: 7:1: FEC 0: corrected 8 errors
...

This problem is present in all kernels since the FEC code introduction (kernel 4.5).

AFAIK the problem is not visible in Android ecosystem because it always use default RS roots=2.

That's correct, Android always uses the default value to minimize space overhead, which is why we never ran into this.

Quoted 21 lines
---
 drivers/md/dm-verity-fec.c | 23 +++++++++++++----------
 1 file changed, 13 insertions(+), 10 deletions(-)
drivers/md/dm-verity-fec.c +1 -3
index fb41b4f23c48..be170581eb69 100644
@@ -61,18 +61,18 @@ static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio,
 static u8 *fec_read_parity(struct dm_verity *v, u64 rsb, int index,
                           unsigned *offset, struct dm_buffer **buf)
 {
-       u64 position, block;
+       u64 position, block, rem;
        u8 *res;
 
        position = (index + rsb) * v->fec->roots;
-       block = position >> v->data_dev_block_bits;
-       *offset = (unsigned)(position - (block << v->data_dev_block_bits));

drivers/md/dm-verity-fec.c static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio, · line 75

Quoted 10 lines
drivers/md/dm-verity-fec.c +4 -2
+       block = div64_u64_rem(position, v->fec->roots << SECTOR_SHIFT, &rem);
+       *offset = (unsigned)rem;
 
-       res = dm_bufio_read(v->fec->bufio, v->fec->start + block, buf);
+       res = dm_bufio_read(v->fec->bufio, block, buf);
        if (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),
+                     (unsigned long long)(block),

Nit: parentheses not needed around block.

drivers/md/dm-verity-fec.c static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio, · line 158

Quoted 9 lines
drivers/md/dm-verity-fec.c +1 -1
                      PTR_ERR(res));
                *buf = NULL;
        }
@@ -155,7 +155,7 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,
 
                /* read the next block when we run out of parity bytes */
                offset += v->fec->roots;
-               if (offset >= 1 << v->data_dev_block_bits) {
+               if (offset >= (v->fec->roots << SECTOR_SHIFT)) {

Same here, but I suppose it might help with readability.

Quoted 24 lines
drivers/md/dm-verity-fec.c +2 -2
                        dm_bufio_release(buf);
 
                        par = fec_read_parity(v, rsb, block_offset, &offset, &buf);
@@ -674,7 +674,7 @@ int verity_fec_ctr(struct dm_verity *v)
 {
        struct dm_verity_fec *f = v->fec;
        struct dm_target *ti = v->ti;
-       u64 hash_blocks;
+       u64 hash_blocks, start_blocks, fec_blocks;
        int ret;
 
        if (!verity_fec_is_enabled(v)) {
@@ -744,15 +744,18 @@ int verity_fec_ctr(struct dm_verity *v)
        }
 
        f->bufio = dm_bufio_client_create(f->dev->bdev,
-                                         1 << v->data_dev_block_bits,
+                                         f->roots << SECTOR_SHIFT,
                                          1, 0, NULL, NULL);
        if (IS_ERR(f->bufio)) {
                ti->error = "Cannot initialize FEC bufio client";
                return PTR_ERR(f->bufio);
        }
 

drivers/md/dm-verity-fec.c int verity_fec_ctr(struct dm_verity *v) · line 761

Quoted 10 lines
drivers/md/dm-verity-fec.c +5 -2
-       if (dm_bufio_get_device_size(f->bufio) <
-           ((f->start + f->rounds * f->roots) >> v->data_dev_block_bits)) {
+       dm_bufio_set_sector_offset(f->bufio, f->start << v->data_dev_block_bits >> SECTOR_SHIFT);
+
+       start_blocks = div64_u64(f->start << v->data_dev_block_bits, v->fec->roots << SECTOR_SHIFT);
+       fec_blocks   = div64_u64(f->rounds * f->roots, v->fec->roots << SECTOR_SHIFT);
+       if (dm_bufio_get_device_size(f->bufio) < (start_blocks + fec_blocks)) {
                ti->error = "FEC device is too small";
                return -E2BIG;
        }

I haven't tested the code, but it looks correct to me. Thanks for fixing this!

Sami

--
dm-devel mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/dm-devel

author
#4 lore raw

PATCH 1/2 dm-bufio: subtract the number of initial sectors in dm_bufio_get_device_size

In reply to Milan Broz

From: Mikulas Patocka <[email protected]>

dm_bufio_get_device_size returns returns the device size in blocks. Before returning the value, we must subtract the nubmer of starting sectors. The number of starting sectos may not be divisible by block size.

Note that currently, no target is using dm_bufio_set_sector_offset and dm_bufio_get_device_size simultaneously, so this patch has no effect. However, an upcoming patch that fixes dm-verity-fec needs this change.

---
 drivers/md/dm-bufio.c | 4 ++++
 1 file changed, 4 insertions(+)
drivers/md/dm-bufio.c +4 -0
index fce4cbf9529d..50f3e673729c 100644
@@ -1526,6 +1526,10 @@ EXPORT_SYMBOL_GPL(dm_bufio_get_block_size);
 sector_t dm_bufio_get_device_size(struct dm_bufio_client *c)
 {
 	sector_t s = i_size_read(c->bdev->bd_inode) >> SECTOR_SHIFT;
+	if (s >= c->start)
+		s -= c->start;
+	else
+		s = 0;
 	if (likely(c->sectors_per_block_bits >= 0))
 		s >>= c->sectors_per_block_bits;
 	else
Signature · 6 lines
2.30.1

--
dm-devel mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/dm-devel
author
#5 lore raw

PATCH 2/2 dm-verity: Fix FEC for RS roots non-aligned to block size

Optional Forward Error Correction (FEC) code in dm-verity uses Reed-Solomon code and should support roots from 2 to 24.

The error correction parity bytes (of roots lengths per RS block) are stored on a separate device in sequence without any padding.

Currently, to access FEC device, the dm-verity-fec code uses dm-bufio client with block size set to verity data block (usually 4096 or 512 bytes).

Because this block size is not divisible by some (most!) of the roots supported lengths, data repair cannot work for partially stored parity bytes.

This patch changes FEC device dm-bufio block size to "roots << SECTOR_SHIFT" where we can be sure that the full parity data is always available. (There cannot be partial FEC blocks because parity must cover whole sectors.)

Because the optional FEC starting offset could be unaligned to this new block size, we have to use dm_bufio_set_sector_offset() to configure it.

The problem is easily reproducible using veritysetup, here for example for roots=13:

  # create verity device with RS FEC
  dd if=/dev/urandom of=data.img bs=4096 count=8 status=none
  veritysetup format data.img hash.img --fec-device=fec.img --fec-roots=13 | awk '/^Root hash/{ print $3 }' >roothash
  # create an erasure that should be always repairable with this roots setting
  dd if=/dev/zero of=data.img conv=notrunc bs=1 count=8 seek=4088 status=none
  # try to read it through dm-verity
  veritysetup open data.img test hash.img --fec-device=fec.img --fec-roots=13 $(cat roothash)
  dd if=/dev/mapper/test of=/dev/null bs=4096 status=noxfer
  # wait for possible recursive recovery in kernel
  udevadm settle
  veritysetup close test

Without it, FEC code usually ends on unrecoverable failure in RS decoder:
device-mapper: verity-fec: 7:1: FEC 0: failed to correct: -74
...

With the patch, errors are properly repaired.
device-mapper: verity-fec: 7:1: FEC 0: corrected 8 errors
...

This problem is present in all kernels since the FEC code introduction (kernel 4.5).

AFAIK the problem is not visible in Android ecosystem because it always use default RS roots=2.

---
 drivers/md/dm-verity-fec.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)
drivers/md/dm-verity-fec.c +12 -10
index fb41b4f23c48..66401ca1f624 100644
@@ -61,18 +61,18 @@ static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio,
 static u8 *fec_read_parity(struct dm_verity *v, u64 rsb, int index,
 			   unsigned *offset, struct dm_buffer **buf)
 {
-	u64 position, block;
+	u64 position, block, rem;
 	u8 *res;
 
 	position = (index + rsb) * v->fec->roots;
-	block = position >> v->data_dev_block_bits;
-	*offset = (unsigned)(position - (block << v->data_dev_block_bits));
+	block = div64_u64_rem(position, v->fec->roots << SECTOR_SHIFT, &rem);
+	*offset = (unsigned)rem;
 
-	res = dm_bufio_read(v->fec->bufio, v->fec->start + block, buf);
+	res = dm_bufio_read(v->fec->bufio, block, buf);
 	if (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),
+		      (unsigned long long)block,
 		      PTR_ERR(res));
 		*buf = NULL;
 	}
@@ -155,7 +155,7 @@ static int fec_decode_bufs(struct dm_verity *v, struct dm_verity_fec_io *fio,
 
 		/* read the next block when we run out of parity bytes */
 		offset += v->fec->roots;
-		if (offset >= 1 << v->data_dev_block_bits) {
+		if (offset >= v->fec->roots << SECTOR_SHIFT) {
 			dm_bufio_release(buf);
 
 			par = fec_read_parity(v, rsb, block_offset, &offset, &buf);
@@ -674,7 +674,7 @@ int verity_fec_ctr(struct dm_verity *v)
 {
 	struct dm_verity_fec *f = v->fec;
 	struct dm_target *ti = v->ti;
-	u64 hash_blocks;
+	u64 hash_blocks, fec_blocks;
 	int ret;
 
 	if (!verity_fec_is_enabled(v)) {
@@ -744,15 +744,17 @@ int verity_fec_ctr(struct dm_verity *v)
 	}
 
 	f->bufio = dm_bufio_client_create(f->dev->bdev,
-					  1 << v->data_dev_block_bits,
+					  f->roots << SECTOR_SHIFT,
 					  1, 0, NULL, NULL);
 	if (IS_ERR(f->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)) {
+	dm_bufio_set_sector_offset(f->bufio, f->start << (v->data_dev_block_bits - SECTOR_SHIFT));
+
+	fec_blocks = div64_u64(f->rounds * f->roots, v->fec->roots << SECTOR_SHIFT);
+	if (dm_bufio_get_device_size(f->bufio) < fec_blocks) {
 		ti->error = "FEC device is too small";
 		return -E2BIG;
 	}
Signature · 6 lines
2.30.1

--
dm-devel mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/dm-devel