Does btrfs use crc32 for error correction?

Does btrfs use crc32 for error correction?

[Timofey Titovets]

Stupid question:
Does btrfs use crc32 for error correction?
If no, why?

(AFAIK if using CRC that possible to fix 1 bit flip)

P.S. I try check that (i create image, create text file, flip bit, try
read and btrfs show IO-error)

Thanks!
-- 
Have a nice day,
Timofey.

Re: Does btrfs use crc32 for error correction?

[Hugo Mills]

[-- Attachment #1: Type: text/plain, Size: 876 bytes --]

On Tue, Sep 19, 2017 at 06:35:48PM +0300, Timofey Titovets wrote:
> Stupid question:
> Does btrfs use crc32 for error correction?

   It uses it for error _detection_. On read, it'll verify the data
(or metadata) against the checksum.

   With no reduncancy (single, RAID-0), a bad csum check will return
I/O error.

   With redundancy (RAID-1, 10, 5, 6), a bad csum check will try
reading the other copy. If that's good, it will use it and repair the
broken copy.

   Hugo.

> If no, why?
> 
> (AFAIK if using CRC that possible to fix 1 bit flip)
> 
> P.S. I try check that (i create image, create text file, flip bit, try
> read and btrfs show IO-error)
> 
> Thanks!

-- 
Hugo Mills             | Dullest spy film ever: The Eastbourne Ultimatum
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                       The Thick of It

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: Does btrfs use crc32 for error correction?

[Eric Sandeen]

On 9/19/17 10:35 AM, Timofey Titovets wrote:
> Stupid question:
> Does btrfs use crc32 for error correction?
> If no, why?
> 
> (AFAIK if using CRC that possible to fix 1 bit flip)
> 
> P.S. I try check that (i create image, create text file, flip bit, try
> read and btrfs show IO-error)
> 
> Thanks!

I wasn't aware that crc32 could (in general) be used for single bit correction; I've read up on that, and it seems pretty cool.
 
However, I don't think that the generator polynomial used in crc32c /can/ be used for error correction.  I just skimmed some reading, but that seems to be the case if I understand it correctly.

-Eric

Re: Does btrfs use crc32 for error correction?

[Marat Khalili]

Would be cool, but probably not wise IMHO, since on modern hardware you almost never get one-bit errors (usually it's a whole sector of garbage), and therefore you'd more often see an incorrect recovery than actually fixed bit.
-- 

With Best Regards,
Marat Khalili

Re: Does btrfs use crc32 for error correction?

[Timofey Titovets]

2017-09-19 21:04 GMT+03:00 Marat Khalili <mkh@rqc.ru>:
> Would be cool, but probably not wise IMHO, since on modern hardware you almost never get one-bit errors (usually it's a whole sector of garbage), and therefore you'd more often see an incorrect recovery than actually fixed bit.
> --
>
> With Best Regards,
> Marat Khalili

Over the past 2 months, I've thinking about some parity solution for
btrfs to have a trade-off between full duplication and single
profiles.

Something like the variable stripe len for mate(data), to fix one
sector's errors.
that is, calculate a one-time parity for each written extent.

But for now, I think that this can not be fixed without tricks or
changing the format.
(Because if you do this in FS lvl, i.e. use a space in B-Tree, this
will create one more exception, if you do this at block level, that
needs a "new" raid5, it's not cool).
But these are only my thoughts.

Therefore, I was recall that CRC in theory allow fixup one bit of error,
but for now, I do not have enough knowledge about CRC to try and
implement a proof of concept for this = \.

(I think that can be usefull not only in btrfs code, i.e. one bit CRC
correction)

But I also remember that btrfs have a lot of unused checksum space in
the checksum tree:
32 bytes of the checksum field, 4 bytes for CRC32C => 28 bytes of freedom =)

So for now I think about calculating the parity with the checksum data,
Proof of the concept (code):
https://github.com/Nefelim4ag/CRC32C_AND_8Byte_parity

As I see it:
1. Btrfs calculates parity 8/16 bytes and 4 bytes of CRC32C
    8/16 bytes stored at the end of the field.
2. Compatibility bits?
    Reason for absence:
     - For an old kernel that does not change anything, it's the same
for old btrfs progs
     - That possible to silent assume that it's have a parity and try
use it and fixup
     Because if it's missing or broken, we just fall back to old behaviour
    Reason for Yes:
     - May be we need to show by something that btrfs has parity +
CRC32 for this data?
3. For x86_64, this works comparably fast with HW CRC32
    --- Checking speed of hash / parity functions ---
    PAGE_SIZE: 4096, number of cycles: 1048576
    Parity64:   0xf7182ccbfc34f088    perf: 233750 usec, th:
18374.191641 MiB / s
    parity32:   0xb2cdc43                    perf: 464824 μs,    th:
9239.986094 MiB / s
    crc32:       0xa4aa10b2                 perf: 312446 μs,     th:
13746.270703 MiB / s
    xxhash64: 0x77e7064e1a16f422 perf: 367570 μs,     th: 11684.760171 MiB / s
4. If a CRC mismatch detected, try to correct the data by parity (for
single profile only):
4.1 Make a tmp data copy
4.2. Suppose that the 0+N block / stripe damaged
       inverse computation of that block from parity
4.3 Check CRC for page:
       - mismatch? -> N + 1 -> Go to 3.1
       - match? -> Hooray! -> Overwrite broken block

That solution will easy fix for most sort of bit flips and up to 1-16
byte -local- corruption

Possible parity combinations:
1 byte: x1 or x2 or x4 or x8 or x16
2 byte: x1 or x2 or x4 or x8
4 byte: x1 or x2 or x4
8 byte: x1 or x2 - fastest on x86_64 (i didn't have other CPUs)

That you think about that?

Thanks.

P.S.
Script for reproduction of 1 bit error case, where FS can't be mounted:
#!/bin/bash

DISK_IMAGE=$(mktemp)
MNT_TMP_DIR="$(mktemp -d)"

truncate -s 48M $DISK_IMAGE
mkfs.btrfs -f -L CRC_TEST -m single $DISK_IMAGE

TMP_DIR="$(mktemp -d)"

mount $DISK_IMAGE $MNT_TMP_DIR
echo "Test String: some_text_data" | tee $MNT_TMP_DIR/file.txt
umount $MNT_TMP_DIR

echo "Add 1 bit error: o -> n"
sed -i 's/some_text_data/snme_text_data/g' $DISK_IMAGE
btrfs check -b -p $DISK_IMAGE

echo "Fix 1 bit error: n -> o"
sed -i 's/snme_text_data/some_text_data/g' $DISK_IMAGE
btrfs check -b -p $DISK_IMAGE

mount $DISK_IMAGE $MNT_TMP_DIR
cat $MNT_TMP_DIR/file.txt
umount $MNT_TMP_DIR

rm -fv "$DISK_IMAGE"


-- 
Have a nice day,
Timofey.

Re: Does btrfs use crc32 for error correction?

[Timofey Titovets]

2017-09-19 19:51 GMT+03:00 Eric Sandeen <sandeen@redhat.com>:
> On 9/19/17 10:35 AM, Timofey Titovets wrote:
>> Stupid question:
>> Does btrfs use crc32 for error correction?
>> If no, why?
>>
>> (AFAIK if using CRC that possible to fix 1 bit flip)
>>
>> P.S. I try check that (i create image, create text file, flip bit, try
>> read and btrfs show IO-error)
>>
>> Thanks!
>
> I wasn't aware that crc32 could (in general) be used for single bit correction; I've read up on that, and it seems pretty cool.
>
> However, I don't think that the generator polynomial used in crc32c /can/ be used for error correction.  I just skimmed some reading, but that seems to be the case if I understand it correctly.
>
> -Eric

That possible, but if i understood doc about CRC16 bit correction
correctly, that need some tricks (As example preprocess all possible
bit flips and have a map of that) for fast find bit error.
Also in theory for CRC32C that possible with some state machine, to
move algo backward and forward over data.

I also check [1], so CRC32C (for our case) have hamming distance about 4.
So CRC32 in theory can fix up to HD-1 ~= 3 bit (If i understand all
things correctly);

So that possible to just brute force over data and flip 1-3 bit, and
try check if CRC fixed %)
In theory that safe for 1-2 bit error (Because again HD for input
data) (Proof of concept[2]).

Thanks.

1. https://users.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
2. https://github.com/Nefelim4ag/CRC32C_AND_8Byte_parity/commit/cb0fe76eac2ff036468bbc5ea75ebc06cb1e9928

-- 
Have a nice day,
Timofey.