by djwong

[permalink] [raw]

Subject: Re: [PATCH 08/16] ext4: Calculate and verify checksums for inode bitmaps

On Mon, Sep 05, 2011 at 02:45:28PM -0500, James Bottomley wrote:
> On Mon, 2011-09-05 at 11:22 -0700, Darrick J. Wong wrote:
> > On Fri, Sep 02, 2011 at 03:27:21PM -0600, Andreas Dilger wrote:
> > > On 2011-09-02, at 1:18 PM, Darrick J. Wong wrote:
> > > > On Wed, Aug 31, 2011 at 10:49:05PM -0600, Andreas Dilger wrote:
> > > >> On 2011-08-31, at 6:31 PM, Darrick J. Wong wrote:
> > > >>> Compute and verify the checksum of the inode bitmap; the checkum is stored in
> > > >>> the block group descriptor.
> > > >>
> > > >> I would prefer if there was a 16-bit checksum for the (most common)
> > > >> 32-byte group descriptors, and this was extended to a 32-bit checksum
> > > >> for the (much less common) 64-byte+ group descriptors. For filesystems
> > > >> that are newly formatted with the 64bit feature it makes no difference,
> > > >> but virtually all ext3/4 filesystems have only the smaller group descriptors.
> > > >>
> > > >> Regardless of whether using half of the crc32c is better or worse than
> > > >> using crc16 for the bitmap blocks, storing _any_ checksum is better than
> > > >> storing nothing at all. I would propose the following:
> > > >
> > > > That's an interesting reframing of the argument that I hadn't considered.
> > > > I'd fallen into the idea of needing crc32c because of its bit error
> > > > guarantees (all corruptions of odd numbers of bits and all corruptions of
> > > > fewer than ...4? bits) that I hadn't quite realized that even if crc16
> > > > can't guarantee to find any corruption at all, it still _might_, and that's
> > > > better than nothing.
> > > >
> > > > Ok, let's split the 32-bit fields and use crc16 for the case of 32-byte block
> > > > group descriptors.
> > >
> > > I noticed the crc16 calculation is actually _slower_ than crc32c,
> > > probably because the CPU cannot use 32-bit values when computing the
> > > result, so it has to do a lot of word masking, per your table at
> > > https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums.
> > > Also, there is the question of whether computing two different
> > > checksums is needlessly complicating the code, or if it is easier
> > > to just compute crc32c all the time and only make the storing of
> > > the high 16 bits conditional.
> > >
> > > What I'm suggesting is always computing the crc32c, but for filesystems
> > > that are not formatted with the 64bit option just store the low 16 bits
> > > of the crc32c value into bg_{block,inode}_bitmap_csum_lo. This is much
> > > better than not computing a checksum here at all. The only open question
> > > is whether 1/2 of crc32c is substantially worse at detecting errors than
> > > crc16 or not?
> >
> > All the literature I've read has suggested that crc16 can't guarantee any error
> > detection capability at all with data buffers longer than 256 bytes.
>
> Um, so in a hashing algorithm that maps f:Z_m -> Z_n you can never
> guarantee error detection if m>n because of hash collisions. All you
> can guarantee is that if f(a) != f(b) then a != b, so crc16 wouldn't be
> able to *guarantee* error detection in anything over 2 bytes.
>
> All of the rest of the magic in hashing functions goes into making sure
> that the collision sets don't include common errors (like bit flipping).
> In theory, for the correct polynomial, CRC-16 should be able to detect
> single, double and triple bit flip errors in blocks of up to 8191
> bytes ... of course, if those aren't your common errors, then this
> analysis is useless ...

Sorry, I grossly misspoke. Of course crc16 can't guarantee the ability to
detect all possible errors in any data block larger than 16 bits. What I meant
to say is that I wasn't sure what is the maximum number of bit errors that
crc16 polynomials can detect given a message length of 32768+32+128 bits.

In particular, I remember reading on the wikipedia page[1] that for polynomials
with odd numbers of terms (such as ansi crc16), the period for 2-bit errors is
65535 bits as you say; but as I recall, those polynomials also can't detect all
errors involving odd numbers of bit flips. For polynomials with even numbers
of terms (such as the t10dif one) the period in which it can detect 2-bit
errors is 32767 bits, but on the other hand they can detect odd numbers of
errors.

The people who study error rates on disk hardware at IBM tell me that bit flips
are more common than you'd like, though I was also looking for something that
can tell me if blocks are being written to the wrong places.

[1] http://en.wikipedia.org/wiki/Mathematics_of_CRC#Bitfilters

--D
>
> James
>
>

2011-09-06 13:00:56

by Martin K. Petersen

[permalink] [raw]

Subject: Re: [PATCH v1 00/16] ext4: Add metadata checksumming

>>>>> "Darrick" == Darrick J Wong <[email protected]> writes:

Darrick> I have some benchmarking data for various crc algorithms here:
Darrick> https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums#Benchmarking

I've been meaning to update my own benchmark results from a few years
ago but your table is much more comprehensive. Nice work!

Darrick> Yes, the only downside to the slice-by-8 method is that it eats
Darrick> 8K of data cache for the table. Not a huge issue on recent
Darrick> Intel and POWER where the L1D is 32K, but I imagine it could be
Darrick> painful elsewhere.

I'll see if I can come up with something better for the DIF CRC. It's
always calculated over either 512 or 4096-byte buffers.

--
Martin K. Petersen Oracle Linux Engineering