Proposal draft for data checksumming for ext4

Proposal draft for data checksumming for ext4

[Lukáš Czerner]

Hi all,

I've started thinking about implementing data checksumming for ext4 file
system. This is not meant to be a formal proposal or a definitive design
description since I am not that far yet, but just a few ideas to start
the discussion and trying to figure out what the best design for data
checksumming in ext4 might be.



			   Data checksumming for ext4
				  Version 0.1
				 March 20, 2014


Goal
====

The goal is to implement data checksumming for ext4 file system in order
to improve data integrity and increase protection against silent data
corruption while maintaining reasonable performance and usability of the
file system.

While data checksums can be certainly used in different ways, for example
data deduplication this proposal is very much focused on data integrity.


Checksum function
=================

By default I plan to use crc32c checksum, but I do not see a reason why not
not to be able to support different checksum function. Also by default the
checksum size should be 32 bits, but the plan is to make the format
flexible enough to be able to support different checksum sizes.


Checksumming and Validating
===========================

On write checksums on the data blocks need to be computed right before its
bio is submitted and written out as metadata to its position (see bellow)
after the bio completes (similarly as we do unwritten extent conversion
today).

Similarly on read checksums needs to be computed after the bio completes
and compared with the stored values to verify that the data is intact.

All of this should be done using workqueues (Concurrency Managed
Workqueues) so we do not block the other operations and to spread the
checksum computation and comparison across CPUs. One wq for reads and one
for writes. Specific setup of the wq such as priority, or concurrency limits
should be decided later based on the performance evaluation.

While we already have ext4 infrastructure to submit bios in
fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
need the same for reads to be able to provide ext4 specific hooks for
io completion.


Where to store the checksums
============================

While the problems above are pretty straightforward when it comes to the
design, actually storing and retrieving the data checksums from to/from
the ext4 format requires much more thought to be efficient enough and play
nicely with the overall ext4 design while trying not to be too intrusive.

I came up with several ideas about where to store and how to access data
checksums. While some of the ideas might not be the most viable options,
it's still interesting to think about the advantages and disadvantages of
each particular solution.

a) Static layout
----------------

This scheme fits perfectly into the ext4 design. Checksum blocks
would be preallocated the same way as we do with inode tables for example.
Each block group should have it's own contiguous region of checksum blocks
to be able to store checksums for bocks from entire block group it belongs
to. Each checksum block would contain header including checksum of the
checksum block.

We still have unused 4 Bytes in the ext4_group_desc structure, so storing
a block number for the checksum table should not be a problem.

Finding a checksum location of each block in the block group should be done
in O(1) time, which is very good. Other advantage is a locality with the
data blocks in question since both resides in the same block group.

Big disadvantage is the fact that this solution is not very flexibile which
comes from the fact that the location of "checksum table" is statically
located at a precise position in the file system at mkfs time.

There are also other problems we should be concerned with. Ext4 file system
does have support for metadata checksumming so all the metadata does have
its own checksum. While we can avoid unnecessarily checksuming inodes, group
descriptors and basicall all statically positioned metadata, we still have
dynamically allocated metadata blocks such as extent blocks. These block
do not have to be checksummed but we would still have space reserved in the
checksum table.

I think that we should be able to make this feature without introducing any
incompatibility, but it would make more sense to make it RO compatible only
so we can preserve the checksums. But that's up to the implementation.

b) Special inode
----------------

This is very "lazy" solution and should not be difficult to implement. The
idea is to have a special inode which would store the checksum blocks in
it's own data blocks.

The big disadvantage is that we would have to walk the extent tree twice for
each read, or write. There is not much to say about this solution other than
again we can make this feature without introducing any incompatibility, but
it would probably make more sense to make it RO compatible to preserve the
checksums.

c) Per inode checksum b-tree
----------------------------

See d)

d) Per block group checksum b-tree
----------------------------------

Those two schemes are very similar in that both would store checksum in a
b-tree with a block number (we could use logical block number in per inode
tree) as a key. Obviously finding a checksum would be in logarithmic time,
while the size of the tree would be possibly much bigger in the per-inode
case. In per block group case we will have much smaller boundary of
number of checksum blocks stored.

This and the fact that we would have to have at least one checksum block
per inode (which would be wasteful in the case of small files) is making per
block group solution much more viable. However the major disadvantage of
per block group solution is that the checksum tree would create a source of
contention when reading/writing from/to a different inodes in the same block
group. This might be mitigated by having a worker thread per a range of block
groups - but it might still be a bottleneck.

Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
root of the tree. While the ext4_inode structure have 4Bytes of
i_obso_faddr but that's not enough. So we would have to figure out where to
store it - we could possibly abuse i_block to store it along with the extent
nodes.

File system scrub
=================

While this is certainly a feature which we want to have in both userspace
e2fsprogs and kernel I do not have any design notes at this stage.




I am sure that there are other possibilities and variants of those design
ideas, but I think that this should be enough to have a discussion started.
As I is not I think that the most viable option is d) that is, per block
group checksum tree, which gives us enough flexibility while not being too
complex solution.

I'll try to update this description as it will be getting more concrete
structure and I hope that we will have some productive discussion about
this at LSF.

Thanks!
-Lukas

Re: Proposal draft for data checksumming for ext4

[Darrick J. Wong]

On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
> Hi all,
> 
> I've started thinking about implementing data checksumming for ext4 file
> system. This is not meant to be a formal proposal or a definitive design
> description since I am not that far yet, but just a few ideas to start
> the discussion and trying to figure out what the best design for data
> checksumming in ext4 might be.
> 
> 
> 
> 			   Data checksumming for ext4
> 				  Version 0.1
> 				 March 20, 2014
> 
> 
> Goal
> ====
> 
> The goal is to implement data checksumming for ext4 file system in order
> to improve data integrity and increase protection against silent data
> corruption while maintaining reasonable performance and usability of the
> file system.
> 
> While data checksums can be certainly used in different ways, for example
> data deduplication this proposal is very much focused on data integrity.
> 
> 
> Checksum function
> =================
> 
> By default I plan to use crc32c checksum, but I do not see a reason why not
> not to be able to support different checksum function. Also by default the
> checksum size should be 32 bits, but the plan is to make the format
> flexible enough to be able to support different checksum sizes.

<nod> Were you thinking of allowing the use of different functions for data and
metadata checksums?

> Checksumming and Validating
> ===========================
> 
> On write checksums on the data blocks need to be computed right before its
> bio is submitted and written out as metadata to its position (see bellow)
> after the bio completes (similarly as we do unwritten extent conversion
> today).
> 
> Similarly on read checksums needs to be computed after the bio completes
> and compared with the stored values to verify that the data is intact.
> 
> All of this should be done using workqueues (Concurrency Managed
> Workqueues) so we do not block the other operations and to spread the
> checksum computation and comparison across CPUs. One wq for reads and one
> for writes. Specific setup of the wq such as priority, or concurrency limits
> should be decided later based on the performance evaluation.
> 
> While we already have ext4 infrastructure to submit bios in
> fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
> need the same for reads to be able to provide ext4 specific hooks for
> io completion.
> 
> 
> Where to store the checksums
> ============================
> 
> While the problems above are pretty straightforward when it comes to the
> design, actually storing and retrieving the data checksums from to/from
> the ext4 format requires much more thought to be efficient enough and play
> nicely with the overall ext4 design while trying not to be too intrusive.
> 
> I came up with several ideas about where to store and how to access data
> checksums. While some of the ideas might not be the most viable options,
> it's still interesting to think about the advantages and disadvantages of
> each particular solution.
> 
> a) Static layout
> ----------------
> 
> This scheme fits perfectly into the ext4 design. Checksum blocks
> would be preallocated the same way as we do with inode tables for example.
> Each block group should have it's own contiguous region of checksum blocks
> to be able to store checksums for bocks from entire block group it belongs
> to. Each checksum block would contain header including checksum of the
> checksum block.
> 
> We still have unused 4 Bytes in the ext4_group_desc structure, so storing
> a block number for the checksum table should not be a problem.

What if you have a 64bit filesystem?  Do you have some strategy in mind to work
around that?  What about the snapshot exclusion bitmap field?  Afaict that
never went in, so perhaps that field could be reused?

> Finding a checksum location of each block in the block group should be done
> in O(1) time, which is very good. Other advantage is a locality with the
> data blocks in question since both resides in the same block group.
> 
> Big disadvantage is the fact that this solution is not very flexibile which
> comes from the fact that the location of "checksum table" is statically
> located at a precise position in the file system at mkfs time.

Having a big dumb block of checksums would be easier to prefetch from disk for
fsck and kernel driver, rather than having to dig through some tree structure.
(More on that below)

> There are also other problems we should be concerned with. Ext4 file system
> does have support for metadata checksumming so all the metadata does have
> its own checksum. While we can avoid unnecessarily checksuming inodes, group
> descriptors and basicall all statically positioned metadata, we still have
> dynamically allocated metadata blocks such as extent blocks. These block
> do not have to be checksummed but we would still have space reserved in the
> checksum table.

Don't forget directory blocks--they (should) have checksums too, so you can
skip those.

I wonder, could we use this table to store backrefs too?  It would make the
table considerably larger, but then we could (potentially) reconstruct broken
extent trees.

> I think that we should be able to make this feature without introducing any
> incompatibility, but it would make more sense to make it RO compatible only
> so we can preserve the checksums. But that's up to the implementation.

I think you'd have to have it be rocompat, otherwise you could write data with
an old kernel and a new kernel would freak out.

> b) Special inode
> ----------------
> 
> This is very "lazy" solution and should not be difficult to implement. The
> idea is to have a special inode which would store the checksum blocks in
> it's own data blocks.
> 
> The big disadvantage is that we would have to walk the extent tree twice for
> each read, or write. There is not much to say about this solution other than
> again we can make this feature without introducing any incompatibility, but
> it would probably make more sense to make it RO compatible to preserve the
> checksums.
> 
> c) Per inode checksum b-tree
> ----------------------------
> 
> See d)
> 
> d) Per block group checksum b-tree
> ----------------------------------
> 
> Those two schemes are very similar in that both would store checksum in a
> b-tree with a block number (we could use logical block number in per inode
> tree) as a key. Obviously finding a checksum would be in logarithmic time,
> while the size of the tree would be possibly much bigger in the per-inode
> case. In per block group case we will have much smaller boundary of
> number of checksum blocks stored.
> 
> This and the fact that we would have to have at least one checksum block
> per inode (which would be wasteful in the case of small files) is making per
> block group solution much more viable. However the major disadvantage of
> per block group solution is that the checksum tree would create a source of
> contention when reading/writing from/to a different inodes in the same block
> group. This might be mitigated by having a worker thread per a range of block
> groups - but it might still be a bottleneck.
> 
> Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
> root of the tree. While the ext4_inode structure have 4Bytes of
> i_obso_faddr but that's not enough. So we would have to figure out where to
> store it - we could possibly abuse i_block to store it along with the extent
> nodes.

I think(?) your purpose in using either a special inode or a btree to store the
checksums is to avoid wasting checksum blocks on things that are already
checksummed?  I'm not sure that we'd save enough space to justify the extra
processing.

--D

> File system scrub
> =================
> 
> While this is certainly a feature which we want to have in both userspace
> e2fsprogs and kernel I do not have any design notes at this stage.
> 
> 
> 
> 
> I am sure that there are other possibilities and variants of those design
> ideas, but I think that this should be enough to have a discussion started.
> As I is not I think that the most viable option is d) that is, per block
> group checksum tree, which gives us enough flexibility while not being too
> complex solution.
> 
> I'll try to update this description as it will be getting more concrete
> structure and I hope that we will have some productive discussion about
> this at LSF.
> 
> Thanks!
> -Lukas
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Proposal draft for data checksumming for ext4

[Lukáš Czerner]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 10123 bytes --]

On Thu, 20 Mar 2014, Darrick J. Wong wrote:

> Date: Thu, 20 Mar 2014 10:59:50 -0700
> From: Darrick J. Wong <darrick.wong@oracle.com>
> To: Lukáš Czerner <lczerner@redhat.com>
> Cc: linux-ext4@vger.kernel.org, Theodore Ts'o <tytso@mit.edu>
> Subject: Re: Proposal draft for data checksumming for ext4
> 
> On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
> > Hi all,
> > 
> > I've started thinking about implementing data checksumming for ext4 file
> > system. This is not meant to be a formal proposal or a definitive design
> > description since I am not that far yet, but just a few ideas to start
> > the discussion and trying to figure out what the best design for data
> > checksumming in ext4 might be.
> > 
> > 
> > 
> > 			   Data checksumming for ext4
> > 				  Version 0.1
> > 				 March 20, 2014
> > 
> > 
> > Goal
> > ====
> > 
> > The goal is to implement data checksumming for ext4 file system in order
> > to improve data integrity and increase protection against silent data
> > corruption while maintaining reasonable performance and usability of the
> > file system.
> > 
> > While data checksums can be certainly used in different ways, for example
> > data deduplication this proposal is very much focused on data integrity.
> > 
> > 
> > Checksum function
> > =================
> > 
> > By default I plan to use crc32c checksum, but I do not see a reason why not
> > not to be able to support different checksum function. Also by default the
> > checksum size should be 32 bits, but the plan is to make the format
> > flexible enough to be able to support different checksum sizes.
> 
> <nod> Were you thinking of allowing the use of different functions for data and
> metadata checksums?

Hi Darrick,

I have not, but I think that this would be very easy to do if we can
agree that it's good to have.


> 
> > Checksumming and Validating
> > ===========================
> > 
> > On write checksums on the data blocks need to be computed right before its
> > bio is submitted and written out as metadata to its position (see bellow)
> > after the bio completes (similarly as we do unwritten extent conversion
> > today).
> > 
> > Similarly on read checksums needs to be computed after the bio completes
> > and compared with the stored values to verify that the data is intact.
> > 
> > All of this should be done using workqueues (Concurrency Managed
> > Workqueues) so we do not block the other operations and to spread the
> > checksum computation and comparison across CPUs. One wq for reads and one
> > for writes. Specific setup of the wq such as priority, or concurrency limits
> > should be decided later based on the performance evaluation.
> > 
> > While we already have ext4 infrastructure to submit bios in
> > fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
> > need the same for reads to be able to provide ext4 specific hooks for
> > io completion.
> > 
> > 
> > Where to store the checksums
> > ============================
> > 
> > While the problems above are pretty straightforward when it comes to the
> > design, actually storing and retrieving the data checksums from to/from
> > the ext4 format requires much more thought to be efficient enough and play
> > nicely with the overall ext4 design while trying not to be too intrusive.
> > 
> > I came up with several ideas about where to store and how to access data
> > checksums. While some of the ideas might not be the most viable options,
> > it's still interesting to think about the advantages and disadvantages of
> > each particular solution.
> > 
> > a) Static layout
> > ----------------
> > 
> > This scheme fits perfectly into the ext4 design. Checksum blocks
> > would be preallocated the same way as we do with inode tables for example.
> > Each block group should have it's own contiguous region of checksum blocks
> > to be able to store checksums for bocks from entire block group it belongs
> > to. Each checksum block would contain header including checksum of the
> > checksum block.
> > 
> > We still have unused 4 Bytes in the ext4_group_desc structure, so storing
> > a block number for the checksum table should not be a problem.
> 
> What if you have a 64bit filesystem?  Do you have some strategy in mind to work
> around that?  What about the snapshot exclusion bitmap field?  Afaict that
> never went in, so perhaps that field could be reused?

Yes we can use the exclusion bitmap field. I think that would not be
a problem. We could also use addressing from the start of the block
group and keep the checksum table in the block group.

> 
> > Finding a checksum location of each block in the block group should be done
> > in O(1) time, which is very good. Other advantage is a locality with the
> > data blocks in question since both resides in the same block group.
> > 
> > Big disadvantage is the fact that this solution is not very flexibile which
> > comes from the fact that the location of "checksum table" is statically
> > located at a precise position in the file system at mkfs time.
> 
> Having a big dumb block of checksums would be easier to prefetch from disk for
> fsck and kernel driver, rather than having to dig through some tree structure.
> (More on that below)

I agree, it is also much more robust solution than having a tree.

> 
> > There are also other problems we should be concerned with. Ext4 file system
> > does have support for metadata checksumming so all the metadata does have
> > its own checksum. While we can avoid unnecessarily checksuming inodes, group
> > descriptors and basicall all statically positioned metadata, we still have
> > dynamically allocated metadata blocks such as extent blocks. These block
> > do not have to be checksummed but we would still have space reserved in the
> > checksum table.
> 
> Don't forget directory blocks--they (should) have checksums too, so you can
> skip those.
> 
> I wonder, could we use this table to store backrefs too?  It would make the
> table considerably larger, but then we could (potentially) reconstruct broken
> extent trees.

Definitely, that is one thing I did not discussed here, but I'd like
to have the checksum blocks self descriptive so we can alway know
where it belongs and who is the owner. So yes, having a backrefs is
really good idea.

> 
> > I think that we should be able to make this feature without introducing any
> > incompatibility, but it would make more sense to make it RO compatible only
> > so we can preserve the checksums. But that's up to the implementation.
> 
> I think you'd have to have it be rocompat, otherwise you could write data with
> an old kernel and a new kernel would freak out.

Yes, I think that we could make it not freak out, but we would loose
the checksums, so for that I think that having this rocompat will
probably make more sense.

Thanks!
-Lukas

> 
> > b) Special inode
> > ----------------
> > 
> > This is very "lazy" solution and should not be difficult to implement. The
> > idea is to have a special inode which would store the checksum blocks in
> > it's own data blocks.
> > 
> > The big disadvantage is that we would have to walk the extent tree twice for
> > each read, or write. There is not much to say about this solution other than
> > again we can make this feature without introducing any incompatibility, but
> > it would probably make more sense to make it RO compatible to preserve the
> > checksums.
> > 
> > c) Per inode checksum b-tree
> > ----------------------------
> > 
> > See d)
> > 
> > d) Per block group checksum b-tree
> > ----------------------------------
> > 
> > Those two schemes are very similar in that both would store checksum in a
> > b-tree with a block number (we could use logical block number in per inode
> > tree) as a key. Obviously finding a checksum would be in logarithmic time,
> > while the size of the tree would be possibly much bigger in the per-inode
> > case. In per block group case we will have much smaller boundary of
> > number of checksum blocks stored.
> > 
> > This and the fact that we would have to have at least one checksum block
> > per inode (which would be wasteful in the case of small files) is making per
> > block group solution much more viable. However the major disadvantage of
> > per block group solution is that the checksum tree would create a source of
> > contention when reading/writing from/to a different inodes in the same block
> > group. This might be mitigated by having a worker thread per a range of block
> > groups - but it might still be a bottleneck.
> > 
> > Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
> > root of the tree. While the ext4_inode structure have 4Bytes of
> > i_obso_faddr but that's not enough. So we would have to figure out where to
> > store it - we could possibly abuse i_block to store it along with the extent
> > nodes.
> 
> I think(?) your purpose in using either a special inode or a btree to store the
> checksums is to avoid wasting checksum blocks on things that are already
> checksummed?  I'm not sure that we'd save enough space to justify the extra
> processing.
> 
> --D
> 
> > File system scrub
> > =================
> > 
> > While this is certainly a feature which we want to have in both userspace
> > e2fsprogs and kernel I do not have any design notes at this stage.
> > 
> > 
> > 
> > 
> > I am sure that there are other possibilities and variants of those design
> > ideas, but I think that this should be enough to have a discussion started.
> > As I is not I think that the most viable option is d) that is, per block
> > group checksum tree, which gives us enough flexibility while not being too
> > complex solution.
> > 
> > I'll try to update this description as it will be getting more concrete
> > structure and I hope that we will have some productive discussion about
> > this at LSF.
> > 
> > Thanks!
> > -Lukas
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Proposal draft for data checksumming for ext4

[Andreas Dilger]

Some quick thoughts in this:
- checksum blocks should cover all non-static blocks in the group,
  don't need separate checksums for itable, bitmap, and descriptors
- if it is complex to skip static blocks with their own checksums, just
  leave those blocks empty (zero checksum).
- address in group descriptor should be relative to other group metadata,
  for example the block bitmap, so it works with/without flex_bg and it is
  clear that "0" is an invalid checksum block array address

Cheers, Andreas

> On Mar 23, 2014, at 19:59, Lukáš Czerner <lczerner@redhat.com> wrote:
> 
>> On Thu, 20 Mar 2014, Darrick J. Wong wrote:
>> 
>> Date: Thu, 20 Mar 2014 10:59:50 -0700
>> From: Darrick J. Wong <darrick.wong@oracle.com>
>> To: Lukáš Czerner <lczerner@redhat.com>
>> Cc: linux-ext4@vger.kernel.org, Theodore Ts'o <tytso@mit.edu>
>> Subject: Re: Proposal draft for data checksumming for ext4
>> 
>>> On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
>>> Hi all,
>>> 
>>> I've started thinking about implementing data checksumming for ext4 file
>>> system. This is not meant to be a formal proposal or a definitive design
>>> description since I am not that far yet, but just a few ideas to start
>>> the discussion and trying to figure out what the best design for data
>>> checksumming in ext4 might be.
>>> 
>>> 
>>> 
>>>               Data checksumming for ext4
>>>                  Version 0.1
>>>                 March 20, 2014
>>> 
>>> 
>>> Goal
>>> ====
>>> 
>>> The goal is to implement data checksumming for ext4 file system in order
>>> to improve data integrity and increase protection against silent data
>>> corruption while maintaining reasonable performance and usability of the
>>> file system.
>>> 
>>> While data checksums can be certainly used in different ways, for example
>>> data deduplication this proposal is very much focused on data integrity.
>>> 
>>> 
>>> Checksum function
>>> =================
>>> 
>>> By default I plan to use crc32c checksum, but I do not see a reason why not
>>> not to be able to support different checksum function. Also by default the
>>> checksum size should be 32 bits, but the plan is to make the format
>>> flexible enough to be able to support different checksum sizes.
>> 
>> <nod> Were you thinking of allowing the use of different functions for data and
>> metadata checksums?
> 
> Hi Darrick,
> 
> I have not, but I think that this would be very easy to do if we can
> agree that it's good to have.
> 
> 
>> 
>>> Checksumming and Validating
>>> ===========================
>>> 
>>> On write checksums on the data blocks need to be computed right before its
>>> bio is submitted and written out as metadata to its position (see bellow)
>>> after the bio completes (similarly as we do unwritten extent conversion
>>> today).
>>> 
>>> Similarly on read checksums needs to be computed after the bio completes
>>> and compared with the stored values to verify that the data is intact.
>>> 
>>> All of this should be done using workqueues (Concurrency Managed
>>> Workqueues) so we do not block the other operations and to spread the
>>> checksum computation and comparison across CPUs. One wq for reads and one
>>> for writes. Specific setup of the wq such as priority, or concurrency limits
>>> should be decided later based on the performance evaluation.
>>> 
>>> While we already have ext4 infrastructure to submit bios in
>>> fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
>>> need the same for reads to be able to provide ext4 specific hooks for
>>> io completion.
>>> 
>>> 
>>> Where to store the checksums
>>> ============================
>>> 
>>> While the problems above are pretty straightforward when it comes to the
>>> design, actually storing and retrieving the data checksums from to/from
>>> the ext4 format requires much more thought to be efficient enough and play
>>> nicely with the overall ext4 design while trying not to be too intrusive.
>>> 
>>> I came up with several ideas about where to store and how to access data
>>> checksums. While some of the ideas might not be the most viable options,
>>> it's still interesting to think about the advantages and disadvantages of
>>> each particular solution.
>>> 
>>> a) Static layout
>>> ----------------
>>> 
>>> This scheme fits perfectly into the ext4 design. Checksum blocks
>>> would be preallocated the same way as we do with inode tables for example.
>>> Each block group should have it's own contiguous region of checksum blocks
>>> to be able to store checksums for bocks from entire block group it belongs
>>> to. Each checksum block would contain header including checksum of the
>>> checksum block.
>>> 
>>> We still have unused 4 Bytes in the ext4_group_desc structure, so storing
>>> a block number for the checksum table should not be a problem.
>> 
>> What if you have a 64bit filesystem?  Do you have some strategy in mind to work
>> around that?  What about the snapshot exclusion bitmap field?  Afaict that
>> never went in, so perhaps that field could be reused?
> 
> Yes we can use the exclusion bitmap field. I think that would not be
> a problem. We could also use addressing from the start of the block
> group and keep the checksum table in the block group.
> 
>> 
>>> Finding a checksum location of each block in the block group should be done
>>> in O(1) time, which is very good. Other advantage is a locality with the
>>> data blocks in question since both resides in the same block group.
>>> 
>>> Big disadvantage is the fact that this solution is not very flexibile which
>>> comes from the fact that the location of "checksum table" is statically
>>> located at a precise position in the file system at mkfs time.
>> 
>> Having a big dumb block of checksums would be easier to prefetch from disk for
>> fsck and kernel driver, rather than having to dig through some tree structure.
>> (More on that below)
> 
> I agree, it is also much more robust solution than having a tree.
> 
>> 
>>> There are also other problems we should be concerned with. Ext4 file system
>>> does have support for metadata checksumming so all the metadata does have
>>> its own checksum. While we can avoid unnecessarily checksuming inodes, group
>>> descriptors and basicall all statically positioned metadata, we still have
>>> dynamically allocated metadata blocks such as extent blocks. These block
>>> do not have to be checksummed but we would still have space reserved in the
>>> checksum table.
>> 
>> Don't forget directory blocks--they (should) have checksums too, so you can
>> skip those.
>> 
>> I wonder, could we use this table to store backrefs too?  It would make the
>> table considerably larger, but then we could (potentially) reconstruct broken
>> extent trees.
> 
> Definitely, that is one thing I did not discussed here, but I'd like
> to have the checksum blocks self descriptive so we can alway know
> where it belongs and who is the owner. So yes, having a backrefs is
> really good idea.
> 
>> 
>>> I think that we should be able to make this feature without introducing any
>>> incompatibility, but it would make more sense to make it RO compatible only
>>> so we can preserve the checksums. But that's up to the implementation.
>> 
>> I think you'd have to have it be rocompat, otherwise you could write data with
>> an old kernel and a new kernel would freak out.
> 
> Yes, I think that we could make it not freak out, but we would loose
> the checksums, so for that I think that having this rocompat will
> probably make more sense.
> 
> Thanks!
> -Lukas
> 
>> 
>>> b) Special inode
>>> ----------------
>>> 
>>> This is very "lazy" solution and should not be difficult to implement. The
>>> idea is to have a special inode which would store the checksum blocks in
>>> it's own data blocks.
>>> 
>>> The big disadvantage is that we would have to walk the extent tree twice for
>>> each read, or write. There is not much to say about this solution other than
>>> again we can make this feature without introducing any incompatibility, but
>>> it would probably make more sense to make it RO compatible to preserve the
>>> checksums.
>>> 
>>> c) Per inode checksum b-tree
>>> ----------------------------
>>> 
>>> See d)
>>> 
>>> d) Per block group checksum b-tree
>>> ----------------------------------
>>> 
>>> Those two schemes are very similar in that both would store checksum in a
>>> b-tree with a block number (we could use logical block number in per inode
>>> tree) as a key. Obviously finding a checksum would be in logarithmic time,
>>> while the size of the tree would be possibly much bigger in the per-inode
>>> case. In per block group case we will have much smaller boundary of
>>> number of checksum blocks stored.
>>> 
>>> This and the fact that we would have to have at least one checksum block
>>> per inode (which would be wasteful in the case of small files) is making per
>>> block group solution much more viable. However the major disadvantage of
>>> per block group solution is that the checksum tree would create a source of
>>> contention when reading/writing from/to a different inodes in the same block
>>> group. This might be mitigated by having a worker thread per a range of block
>>> groups - but it might still be a bottleneck.
>>> 
>>> Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
>>> root of the tree. While the ext4_inode structure have 4Bytes of
>>> i_obso_faddr but that's not enough. So we would have to figure out where to
>>> store it - we could possibly abuse i_block to store it along with the extent
>>> nodes.
>> 
>> I think(?) your purpose in using either a special inode or a btree to store the
>> checksums is to avoid wasting checksum blocks on things that are already
>> checksummed?  I'm not sure that we'd save enough space to justify the extra
>> processing.
>> 
>> --D
>> 
>>> File system scrub
>>> =================
>>> 
>>> While this is certainly a feature which we want to have in both userspace
>>> e2fsprogs and kernel I do not have any design notes at this stage.
>>> 
>>> 
>>> 
>>> 
>>> I am sure that there are other possibilities and variants of those design
>>> ideas, but I think that this should be enough to have a discussion started.
>>> As I is not I think that the most viable option is d) that is, per block
>>> group checksum tree, which gives us enough flexibility while not being too
>>> complex solution.
>>> 
>>> I'll try to update this description as it will be getting more concrete
>>> structure and I hope that we will have some productive discussion about
>>> this at LSF.
>>> 
>>> Thanks!
>>> -Lukas
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Proposal draft for data checksumming for ext4

[mingming cao]

On 03/23/2014 06:59 PM, Lukáš Czerner wrote:
> On Thu, 20 Mar 2014, Darrick J. Wong wrote:
>
>> Date: Thu, 20 Mar 2014 10:59:50 -0700
>> From: Darrick J. Wong <darrick.wong@oracle.com>
>> To: Lukáš Czerner <lczerner@redhat.com>
>> Cc: linux-ext4@vger.kernel.org, Theodore Ts'o <tytso@mit.edu>
>> Subject: Re: Proposal draft for data checksumming for ext4
>>
>> On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
>>> Hi all,
>>>
>>> I've started thinking about implementing data checksumming for ext4 file
>>> system. This is not meant to be a formal proposal or a definitive design
>>> description since I am not that far yet, but just a few ideas to start
>>> the discussion and trying to figure out what the best design for data
>>> checksumming in ext4 might be.
>>>
>>>
>>>
>>> 			   Data checksumming for ext4
>>> 				  Version 0.1
>>> 				 March 20, 2014
>>>
>>>
>>> Goal
>>> ====
>>>
>>> The goal is to implement data checksumming for ext4 file system in order
>>> to improve data integrity and increase protection against silent data
>>> corruption while maintaining reasonable performance and usability of the
>>> file system.
>>>
>>> While data checksums can be certainly used in different ways, for example
>>> data deduplication this proposal is very much focused on data integrity.
>>>
>>>
>>> Checksum function
>>> =================
>>>
>>> By default I plan to use crc32c checksum, but I do not see a reason why not
>>> not to be able to support different checksum function. Also by default the
>>> checksum size should be 32 bits, but the plan is to make the format
>>> flexible enough to be able to support different checksum sizes.
>>
>> <nod> Were you thinking of allowing the use of different functions for data and
>> metadata checksums?
>
> Hi Darrick,
>
> I have not, but I think that this would be very easy to do if we can
> agree that it's good to have.
>
>
>>
>>> Checksumming and Validating
>>> ===========================
>>>
>>> On write checksums on the data blocks need to be computed right before its
>>> bio is submitted and written out as metadata to its position (see bellow)
>>> after the bio completes (similarly as we do unwritten extent conversion
>>> today).
>>>
>>> Similarly on read checksums needs to be computed after the bio completes
>>> and compared with the stored values to verify that the data is intact.
>>>
>>> All of this should be done using workqueues (Concurrency Managed
>>> Workqueues) so we do not block the other operations and to spread the
>>> checksum computation and comparison across CPUs. One wq for reads and one
>>> for writes. Specific setup of the wq such as priority, or concurrency limits
>>> should be decided later based on the performance evaluation.
>>>
>>> While we already have ext4 infrastructure to submit bios in
>>> fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
>>> need the same for reads to be able to provide ext4 specific hooks for
>>> io completion.
>>>
>>>
>>> Where to store the checksums
>>> ============================
>>>
>>> While the problems above are pretty straightforward when it comes to the
>>> design, actually storing and retrieving the data checksums from to/from
>>> the ext4 format requires much more thought to be efficient enough and play
>>> nicely with the overall ext4 design while trying not to be too intrusive.
>>>
>>> I came up with several ideas about where to store and how to access data
>>> checksums. While some of the ideas might not be the most viable options,
>>> it's still interesting to think about the advantages and disadvantages of
>>> each particular solution.
>>>
>>> a) Static layout
>>> ----------------
>>>
>>> This scheme fits perfectly into the ext4 design. Checksum blocks
>>> would be preallocated the same way as we do with inode tables for example.
>>> Each block group should have it's own contiguous region of checksum blocks
>>> to be able to store checksums for bocks from entire block group it belongs
>>> to. Each checksum block would contain header including checksum of the
>>> checksum block.
>>>
>>> We still have unused 4 Bytes in the ext4_group_desc structure, so storing
>>> a block number for the checksum table should not be a problem.
>>
>> What if you have a 64bit filesystem?  Do you have some strategy in mind to work
>> around that?  What about the snapshot exclusion bitmap field?  Afaict that
>> never went in, so perhaps that field could be reused?
>
> Yes we can use the exclusion bitmap field. I think that would not be
> a problem. We could also use addressing from the start of the block
> group and keep the checksum table in the block group.
>
>>
>>> Finding a checksum location of each block in the block group should be done
>>> in O(1) time, which is very good. Other advantage is a locality with the
>>> data blocks in question since both resides in the same block group.
>>>
>>> Big disadvantage is the fact that this solution is not very flexibile which
>>> comes from the fact that the location of "checksum table" is statically
>>> located at a precise position in the file system at mkfs time.
>>
>> Having a big dumb block of checksums would be easier to prefetch from disk for
>> fsck and kernel driver, rather than having to dig through some tree structure.
>> (More on that below)
>
> I agree, it is also much more robust solution than having a tree.
>
>>
>>> There are also other problems we should be concerned with. Ext4 file system
>>> does have support for metadata checksumming so all the metadata does have
>>> its own checksum. While we can avoid unnecessarily checksuming inodes, group
>>> descriptors and basicall all statically positioned metadata, we still have
>>> dynamically allocated metadata blocks such as extent blocks. These block
>>> do not have to be checksummed but we would still have space reserved in the
>>> checksum table.
>>
>> Don't forget directory blocks--they (should) have checksums too, so you can
>> skip those.
>>
>> I wonder, could we use this table to store backrefs too?  It would make the
>> table considerably larger, but then we could (potentially) reconstruct broken
>> extent trees.
>
> Definitely, that is one thing I did not discussed here, but I'd like
> to have the checksum blocks self descriptive so we can alway know
> where it belongs and who is the owner. So yes, having a backrefs is
> really good idea.
>

Hello Lukas, Darrick,


I just read this documents, quite interesting. I wonder if this was 
discussed at ext4 workshop in Napa and any agreement has reached as to 
how to store the data checksumming?

Have you thought about store extent checksumming/backrefs rather than 
per data block?

If we are interested in adding backrefs, then I wonder if we could use 
this table to store reflink counters as well? I understand only data 
blocks referenced by multiple files need this, but this is  a O(1) 
faster solution than per-inode refcount tree,  and we are thinking of 
tracking data checksums/backrefs anyway, and the refcounters could be 
checksummed at the same time.

Mingming
>>
>>> I think that we should be able to make this feature without introducing any
>>> incompatibility, but it would make more sense to make it RO compatible only
>>> so we can preserve the checksums. But that's up to the implementation.
>>
>> I think you'd have to have it be rocompat, otherwise you could write data with
>> an old kernel and a new kernel would freak out.
>
> Yes, I think that we could make it not freak out, but we would loose
> the checksums, so for that I think that having this rocompat will
> probably make more sense.
>
> Thanks!
> -Lukas
>
>>
>>> b) Special inode
>>> ----------------
>>>
>>> This is very "lazy" solution and should not be difficult to implement. The
>>> idea is to have a special inode which would store the checksum blocks in
>>> it's own data blocks.
>>>
>>> The big disadvantage is that we would have to walk the extent tree twice for
>>> each read, or write. There is not much to say about this solution other than
>>> again we can make this feature without introducing any incompatibility, but
>>> it would probably make more sense to make it RO compatible to preserve the
>>> checksums.
>>>
>>> c) Per inode checksum b-tree
>>> ----------------------------
>>>
>>> See d)
>>>
>>> d) Per block group checksum b-tree
>>> ----------------------------------
>>>
>>> Those two schemes are very similar in that both would store checksum in a
>>> b-tree with a block number (we could use logical block number in per inode
>>> tree) as a key. Obviously finding a checksum would be in logarithmic time,
>>> while the size of the tree would be possibly much bigger in the per-inode
>>> case. In per block group case we will have much smaller boundary of
>>> number of checksum blocks stored.
>>>
>>> This and the fact that we would have to have at least one checksum block
>>> per inode (which would be wasteful in the case of small files) is making per
>>> block group solution much more viable. However the major disadvantage of
>>> per block group solution is that the checksum tree would create a source of
>>> contention when reading/writing from/to a different inodes in the same block
>>> group. This might be mitigated by having a worker thread per a range of block
>>> groups - but it might still be a bottleneck.
>>>
>>> Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
>>> root of the tree. While the ext4_inode structure have 4Bytes of
>>> i_obso_faddr but that's not enough. So we would have to figure out where to
>>> store it - we could possibly abuse i_block to store it along with the extent
>>> nodes.
>>
>> I think(?) your purpose in using either a special inode or a btree to store the
>> checksums is to avoid wasting checksum blocks on things that are already
>> checksummed?  I'm not sure that we'd save enough space to justify the extra
>> processing.
>>
>> --D
>>
>>> File system scrub
>>> =================
>>>
>>> While this is certainly a feature which we want to have in both userspace
>>> e2fsprogs and kernel I do not have any design notes at this stage.
>>>
>>>
>>>
>>>
>>> I am sure that there are other possibilities and variants of those design
>>> ideas, but I think that this should be enough to have a discussion started.
>>> As I is not I think that the most viable option is d) that is, per block
>>> group checksum tree, which gives us enough flexibility while not being too
>>> complex solution.
>>>
>>> I'll try to update this description as it will be getting more concrete
>>> structure and I hope that we will have some productive discussion about
>>> this at LSF.
>>>
>>> Thanks!
>>> -Lukas
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

Re: Proposal draft for data checksumming for ext4

[Dmitry Monakhov]

On Thu, 20 Mar 2014 10:59:50 -0700, "Darrick J. Wong" <darrick.wong@oracle.com> wrote:
> On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
> > Hi all,
> > 
> > I've started thinking about implementing data checksumming for ext4 file
> > system. This is not meant to be a formal proposal or a definitive design
> > description since I am not that far yet, but just a few ideas to start
> > the discussion and trying to figure out what the best design for data
> > checksumming in ext4 might be.
> > 
> > 
> > 
> > 			   Data checksumming for ext4
> > 				  Version 0.1
> > 				 March 20, 2014
> > 
> > 
> > Goal
> > ====
> > 
> > The goal is to implement data checksumming for ext4 file system in order
> > to improve data integrity and increase protection against silent data
> > corruption while maintaining reasonable performance and usability of the
> > file system.
> > 
> > While data checksums can be certainly used in different ways, for example
> > data deduplication this proposal is very much focused on data integrity.
> > 
> > 
> > Checksum function
> > =================
> > 
> > By default I plan to use crc32c checksum, but I do not see a reason why not
> > not to be able to support different checksum function. Also by default the
> > checksum size should be 32 bits, but the plan is to make the format
> > flexible enough to be able to support different checksum sizes.
> 
> <nod> Were you thinking of allowing the use of different functions for data and
> metadata checksums?
> 
> > Checksumming and Validating
> > ===========================
> > 
> > On write checksums on the data blocks need to be computed right before its
> > bio is submitted and written out as metadata to its position (see bellow)
> > after the bio completes (similarly as we do unwritten extent conversion
> > today).
> > 
> > Similarly on read checksums needs to be computed after the bio completes
> > and compared with the stored values to verify that the data is intact.
> > 
> > All of this should be done using workqueues (Concurrency Managed
> > Workqueues) so we do not block the other operations and to spread the
> > checksum computation and comparison across CPUs. One wq for reads and one
> > for writes. Specific setup of the wq such as priority, or concurrency limits
> > should be decided later based on the performance evaluation.
> > 
> > While we already have ext4 infrastructure to submit bios in
> > fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
> > need the same for reads to be able to provide ext4 specific hooks for
> > io completion.
> > 
> > 
> > Where to store the checksums
> > ============================
> > 
> > While the problems above are pretty straightforward when it comes to the
> > design, actually storing and retrieving the data checksums from to/from
> > the ext4 format requires much more thought to be efficient enough and play
> > nicely with the overall ext4 design while trying not to be too intrusive.
> > 
> > I came up with several ideas about where to store and how to access data
> > checksums. While some of the ideas might not be the most viable options,
> > it's still interesting to think about the advantages and disadvantages of
> > each particular solution.
> > 
> > a) Static layout
> > ----------------
> > 
> > This scheme fits perfectly into the ext4 design. Checksum blocks
> > would be preallocated the same way as we do with inode tables for example.
> > Each block group should have it's own contiguous region of checksum blocks
> > to be able to store checksums for bocks from entire block group it belongs
> > to. Each checksum block would contain header including checksum of the
> > checksum block.
Oh. The most thing that bother me about that feature is possible
performance degradation. number seeks increase dramatically because 
csumblock is not continuous with datablock. Off course journal should
absorb that and real io will happen during journal checkpoint.
But I assumes that mail server which does a lot of
create()/write()/fsync() will complain about bad performance.

BTW: it looks like we do not try to optimize io pattern inside
jbd2_log_do_checkpoint(). For example __flush_batch() can submit
buffer in sorted order(according to block numbers).
 
 
> > 
> > We still have unused 4 Bytes in the ext4_group_desc structure, so storing
> > a block number for the checksum table should not be a problem.
> 
> What if you have a 64bit filesystem?  Do you have some strategy in mind to work
> around that?  What about the snapshot exclusion bitmap field?  Afaict that
> never went in, so perhaps that field could be reused?
> 
> > Finding a checksum location of each block in the block group should be done
> > in O(1) time, which is very good. Other advantage is a locality with the
> > data blocks in question since both resides in the same block group.
> > 
> > Big disadvantage is the fact that this solution is not very flexibile which
> > comes from the fact that the location of "checksum table" is statically
> > located at a precise position in the file system at mkfs time.
> 
> Having a big dumb block of checksums would be easier to prefetch from disk for
> fsck and kernel driver, rather than having to dig through some tree structure.
> (More on that below)
> 
> > There are also other problems we should be concerned with. Ext4 file system
> > does have support for metadata checksumming so all the metadata does have
> > its own checksum. While we can avoid unnecessarily checksuming inodes, group
> > descriptors and basicall all statically positioned metadata, we still have
> > dynamically allocated metadata blocks such as extent blocks. These block
> > do not have to be checksummed but we would still have space reserved in the
> > checksum table.
> 
> Don't forget directory blocks--they (should) have checksums too, so you can
> skip those.
Just quick note: We can hide checksum for directory inside
ext4_dir_entry_2 for a special dirs '.' or '..' simply be increasing
->rec_len which make this feature compatible with older FS
> 
> I wonder, could we use this table to store backrefs too?  It would make the
> table considerably larger, but then we could (potentially) reconstruct broken
> extent trees.
> 
> > I think that we should be able to make this feature without introducing any
> > incompatibility, but it would make more sense to make it RO compatible only
> > so we can preserve the checksums. But that's up to the implementation.
> 
> I think you'd have to have it be rocompat, otherwise you could write data with
> an old kernel and a new kernel would freak out.
> 
> > b) Special inode
> > ----------------
> > 
> > This is very "lazy" solution and should not be difficult to implement. The
> > idea is to have a special inode which would store the checksum blocks in
> > it's own data blocks.
> > 
> > The big disadvantage is that we would have to walk the extent tree twice for
> > each read, or write. There is not much to say about this solution other than
> > again we can make this feature without introducing any incompatibility, but
> > it would probably make more sense to make it RO compatible to preserve the
> > checksums.
> > 
> > c) Per inode checksum b-tree
> > ----------------------------
> > 
> > See d)
> > 
> > d) Per block group checksum b-tree
> > ----------------------------------
> > 
> > Those two schemes are very similar in that both would store checksum in a
> > b-tree with a block number (we could use logical block number in per inode
> > tree) as a key. Obviously finding a checksum would be in logarithmic time,
> > while the size of the tree would be possibly much bigger in the per-inode
> > case. In per block group case we will have much smaller boundary of
> > number of checksum blocks stored.
> > 
> > This and the fact that we would have to have at least one checksum block
> > per inode (which would be wasteful in the case of small files) is making per
> > block group solution much more viable. However the major disadvantage of
> > per block group solution is that the checksum tree would create a source of
> > contention when reading/writing from/to a different inodes in the same block
> > group. This might be mitigated by having a worker thread per a range of block
> > groups - but it might still be a bottleneck.
> > 
> > Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
> > root of the tree. While the ext4_inode structure have 4Bytes of
> > i_obso_faddr but that's not enough. So we would have to figure out where to
> > store it - we could possibly abuse i_block to store it along with the extent
> > nodes.
> 
> I think(?) your purpose in using either a special inode or a btree to store the
> checksums is to avoid wasting checksum blocks on things that are already
> checksummed?  I'm not sure that we'd save enough space to justify the extra
> processing.
> 
> --D
> 
> > File system scrub
> > =================
> > 
> > While this is certainly a feature which we want to have in both userspace
> > e2fsprogs and kernel I do not have any design notes at this stage.
> > 
> > 
> > 
> > 
> > I am sure that there are other possibilities and variants of those design
> > ideas, but I think that this should be enough to have a discussion started.
> > As I is not I think that the most viable option is d) that is, per block
> > group checksum tree, which gives us enough flexibility while not being too
> > complex solution.
> > 
> > I'll try to update this description as it will be getting more concrete
> > structure and I hope that we will have some productive discussion about
> > this at LSF.
> > 
> > Thanks!
> > -Lukas
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Proposal draft for data checksumming for ext4

[Darrick J. Wong]

On Mon, Apr 28, 2014 at 08:21:51PM +0400, Dmitry Monakhov wrote:
> On Thu, 20 Mar 2014 10:59:50 -0700, "Darrick J. Wong" <darrick.wong@oracle.com> wrote:
> > On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
> > > Hi all,
> > > 
> > > I've started thinking about implementing data checksumming for ext4 file
> > > system. This is not meant to be a formal proposal or a definitive design
> > > description since I am not that far yet, but just a few ideas to start
> > > the discussion and trying to figure out what the best design for data
> > > checksumming in ext4 might be.
> > > 
> > > 
> > > 
> > > 			   Data checksumming for ext4
> > > 				  Version 0.1
> > > 				 March 20, 2014
> > > 
> > > 
> > > Goal
> > > ====
> > > 
> > > The goal is to implement data checksumming for ext4 file system in order
> > > to improve data integrity and increase protection against silent data
> > > corruption while maintaining reasonable performance and usability of the
> > > file system.
> > > 
> > > While data checksums can be certainly used in different ways, for example
> > > data deduplication this proposal is very much focused on data integrity.
> > > 
> > > 
> > > Checksum function
> > > =================
> > > 
> > > By default I plan to use crc32c checksum, but I do not see a reason why not
> > > not to be able to support different checksum function. Also by default the
> > > checksum size should be 32 bits, but the plan is to make the format
> > > flexible enough to be able to support different checksum sizes.
> > 
> > <nod> Were you thinking of allowing the use of different functions for data and
> > metadata checksums?
> > 
> > > Checksumming and Validating
> > > ===========================
> > > 
> > > On write checksums on the data blocks need to be computed right before its
> > > bio is submitted and written out as metadata to its position (see bellow)
> > > after the bio completes (similarly as we do unwritten extent conversion
> > > today).
> > > 
> > > Similarly on read checksums needs to be computed after the bio completes
> > > and compared with the stored values to verify that the data is intact.
> > > 
> > > All of this should be done using workqueues (Concurrency Managed
> > > Workqueues) so we do not block the other operations and to spread the
> > > checksum computation and comparison across CPUs. One wq for reads and one
> > > for writes. Specific setup of the wq such as priority, or concurrency limits
> > > should be decided later based on the performance evaluation.
> > > 
> > > While we already have ext4 infrastructure to submit bios in
> > > fs/ext4/page-io.c where the entry point is ext4_bio_write_page() we would
> > > need the same for reads to be able to provide ext4 specific hooks for
> > > io completion.
> > > 
> > > 
> > > Where to store the checksums
> > > ============================
> > > 
> > > While the problems above are pretty straightforward when it comes to the
> > > design, actually storing and retrieving the data checksums from to/from
> > > the ext4 format requires much more thought to be efficient enough and play
> > > nicely with the overall ext4 design while trying not to be too intrusive.
> > > 
> > > I came up with several ideas about where to store and how to access data
> > > checksums. While some of the ideas might not be the most viable options,
> > > it's still interesting to think about the advantages and disadvantages of
> > > each particular solution.
> > > 
> > > a) Static layout
> > > ----------------
> > > 
> > > This scheme fits perfectly into the ext4 design. Checksum blocks
> > > would be preallocated the same way as we do with inode tables for example.
> > > Each block group should have it's own contiguous region of checksum blocks
> > > to be able to store checksums for bocks from entire block group it belongs
> > > to. Each checksum block would contain header including checksum of the
> > > checksum block.
> Oh. The most thing that bother me about that feature is possible
> performance degradation. number seeks increase dramatically because 
> csumblock is not continuous with datablock. Off course journal should
> absorb that and real io will happen during journal checkpoint.
> But I assumes that mail server which does a lot of
> create()/write()/fsync() will complain about bad performance.
> 
> BTW: it looks like we do not try to optimize io pattern inside
> jbd2_log_do_checkpoint(). For example __flush_batch() can submit
> buffer in sorted order(according to block numbers).
>  
>  
> > > 
> > > We still have unused 4 Bytes in the ext4_group_desc structure, so storing
> > > a block number for the checksum table should not be a problem.
> > 
> > What if you have a 64bit filesystem?  Do you have some strategy in mind to work
> > around that?  What about the snapshot exclusion bitmap field?  Afaict that
> > never went in, so perhaps that field could be reused?
> > 
> > > Finding a checksum location of each block in the block group should be done
> > > in O(1) time, which is very good. Other advantage is a locality with the
> > > data blocks in question since both resides in the same block group.
> > > 
> > > Big disadvantage is the fact that this solution is not very flexibile which
> > > comes from the fact that the location of "checksum table" is statically
> > > located at a precise position in the file system at mkfs time.
> > 
> > Having a big dumb block of checksums would be easier to prefetch from disk for
> > fsck and kernel driver, rather than having to dig through some tree structure.
> > (More on that below)
> > 
> > > There are also other problems we should be concerned with. Ext4 file system
> > > does have support for metadata checksumming so all the metadata does have
> > > its own checksum. While we can avoid unnecessarily checksuming inodes, group
> > > descriptors and basicall all statically positioned metadata, we still have
> > > dynamically allocated metadata blocks such as extent blocks. These block
> > > do not have to be checksummed but we would still have space reserved in the
> > > checksum table.
> > 
> > Don't forget directory blocks--they (should) have checksums too, so you can
> > skip those.
> Just quick note: We can hide checksum for directory inside
> ext4_dir_entry_2 for a special dirs '.' or '..' simply be increasing
> ->rec_len which make this feature compatible with older FS

metadata_csum already does this.

--D
> > 
> > I wonder, could we use this table to store backrefs too?  It would make the
> > table considerably larger, but then we could (potentially) reconstruct broken
> > extent trees.
> > 
> > > I think that we should be able to make this feature without introducing any
> > > incompatibility, but it would make more sense to make it RO compatible only
> > > so we can preserve the checksums. But that's up to the implementation.
> > 
> > I think you'd have to have it be rocompat, otherwise you could write data with
> > an old kernel and a new kernel would freak out.
> > 
> > > b) Special inode
> > > ----------------
> > > 
> > > This is very "lazy" solution and should not be difficult to implement. The
> > > idea is to have a special inode which would store the checksum blocks in
> > > it's own data blocks.
> > > 
> > > The big disadvantage is that we would have to walk the extent tree twice for
> > > each read, or write. There is not much to say about this solution other than
> > > again we can make this feature without introducing any incompatibility, but
> > > it would probably make more sense to make it RO compatible to preserve the
> > > checksums.
> > > 
> > > c) Per inode checksum b-tree
> > > ----------------------------
> > > 
> > > See d)
> > > 
> > > d) Per block group checksum b-tree
> > > ----------------------------------
> > > 
> > > Those two schemes are very similar in that both would store checksum in a
> > > b-tree with a block number (we could use logical block number in per inode
> > > tree) as a key. Obviously finding a checksum would be in logarithmic time,
> > > while the size of the tree would be possibly much bigger in the per-inode
> > > case. In per block group case we will have much smaller boundary of
> > > number of checksum blocks stored.
> > > 
> > > This and the fact that we would have to have at least one checksum block
> > > per inode (which would be wasteful in the case of small files) is making per
> > > block group solution much more viable. However the major disadvantage of
> > > per block group solution is that the checksum tree would create a source of
> > > contention when reading/writing from/to a different inodes in the same block
> > > group. This might be mitigated by having a worker thread per a range of block
> > > groups - but it might still be a bottleneck.
> > > 
> > > Again we still have 4 Bytes in ext4_group_desc to store the pointer to the
> > > root of the tree. While the ext4_inode structure have 4Bytes of
> > > i_obso_faddr but that's not enough. So we would have to figure out where to
> > > store it - we could possibly abuse i_block to store it along with the extent
> > > nodes.
> > 
> > I think(?) your purpose in using either a special inode or a btree to store the
> > checksums is to avoid wasting checksum blocks on things that are already
> > checksummed?  I'm not sure that we'd save enough space to justify the extra
> > processing.
> > 
> > --D
> > 
> > > File system scrub
> > > =================
> > > 
> > > While this is certainly a feature which we want to have in both userspace
> > > e2fsprogs and kernel I do not have any design notes at this stage.
> > > 
> > > 
> > > 
> > > 
> > > I am sure that there are other possibilities and variants of those design
> > > ideas, but I think that this should be enough to have a discussion started.
> > > As I is not I think that the most viable option is d) that is, per block
> > > group checksum tree, which gives us enough flexibility while not being too
> > > complex solution.
> > > 
> > > I'll try to update this description as it will be getting more concrete
> > > structure and I hope that we will have some productive discussion about
> > > this at LSF.
> > > 
> > > Thanks!
> > > -Lukas
> > > --
> > > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > > the body of a message to majordomo@vger.kernel.org
> > > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Proposal draft for data checksumming for ext4

[Andreas Dilger]

[-- Attachment #1.1: Type: text/plain, Size: 2407 bytes --]


On Apr 28, 2014, at 10:21 AM, Dmitry Monakhov <dmonakhov@openvz.org> wrote:
>> On Thu, Mar 20, 2014 at 05:40:06PM +0100, Lukáš Czerner wrote:
>>> There are also other problems we should be concerned with. Ext4 file system
>>> does have support for metadata checksumming so all the metadata does have
>>> its own checksum. While we can avoid unnecessarily checksuming inodes, group
>>> descriptors and basicall all statically positioned metadata, we still have
>>> dynamically allocated metadata blocks such as extent blocks. These block
>>> do not have to be checksummed but we would still have space reserved in the
>>> checksum table.
>> 
>> Don't forget directory blocks--they (should) have checksums too, so you can
>> skip those.
> 
> Just quick note: We can hide checksum for directory inside
> ext4_dir_entry_2 for a special dirs '.' or '..' simply by increasing
> ->rec_len which make this feature compatible with older FS

First note - the htree index information for each directory is already
stored after the ".." entry in block 0 of the directory.

Also note that there is also a feature we developed for Lustre named
"dirdata" (EXT4_FEATURE_INCOMPAT_DIRDATA is already reserved) that
allows storing more information with each directory entry[*].  We
use this to store a 128-bit identifier with each object so that it is
unique across the cluster, so it is available efficiently for readdir.

We've needed to modify the handling of the htree index data so that
it properly skips the extended directory entry (patch attached), and
this also cleans up this code a bit to conform to modern coding style.
Without this patch, the htree code assumes that the dx_info struct is
immediately following hard-coded "." and ".." entries and does not
actually check the de->rec_len for these entries to determine the right
amount of data to skip.

The patch is based on an older kernel and may not apply directly to
mainline, but is required for any similar changes in this area.

That said, I think that Darrick's metadata checksum patches already
store per-directory-block checksums at the end of the directory in
a dummy entry, so I'm not sure what else is needed here?

Cheers, Andreas

[*] for reference the dirdata patch is at http://git.hpdd.intel.com/?p=fs/lustre-release.git;a=blob;f=ldiskfs/kernel_patches/patches/sles11sp2/ext4-data-in-dirent.patch


[-- Attachment #1.2: ext4-kill-dx_root.patch --]
[-- Type: application/octet-stream, Size: 7043 bytes --]

diff -r -u linux-stage.orig/fs/ext4/namei.c linux-stage/fs/ext4/namei.c
--- linux-stage.orig/fs/ext4/namei.c	2012-12-31 15:03:28.000000000 -0500
+++ linux-stage/fs/ext4/namei.c	2012-12-31 15:06:16.000000000 -0500
@@ -115,22 +115,13 @@
  * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
  */
 
-struct dx_root
+struct dx_root_info
 {
-	struct fake_dirent dot;
-	char dot_name[4];
-	struct fake_dirent dotdot;
-	char dotdot_name[4];
-	struct dx_root_info
-	{
-		__le32 reserved_zero;
-		u8 hash_version;
-		u8 info_length; /* 8 */
-		u8 indirect_levels;
-		u8 unused_flags;
-	}
-	info;
-	struct dx_entry	entries[0];
+	__le32 reserved_zero;
+	u8 hash_version;
+	u8 info_length; /* 8 */
+	u8 indirect_levels;
+	u8 unused_flags;
 };
 
 struct dx_node
@@ -220,6 +211,17 @@
 	ext3_rec_len_from_disk(p->rec_len));
 }
  
+struct dx_root_info *dx_get_dx_info(char *buf)
+{
+	struct ext4_dir_entry_2 *de = buf;
+
+	/* get dotdot first, then dx_info is right after dotdot entry */
+	de = (struct ext4_dir_entry_2 *)((char *)de + EXT4_DIR_REC_LEN(1));
+	de = (struct ext4_dir_entry_2 *)((char *)de + EXT4_DIR_REC_LEN(2));
+
+	return (struct dx_root_info *)de;
+}
+
 /*
  * Future: use high four bits of block for coalesce-on-delete flags
  * Mask them off for now.
@@ -374,7 +375,7 @@
 {
 	unsigned count, indirect;
 	struct dx_entry *at, *entries, *p, *q, *m;
-	struct dx_root *root;
+	struct dx_root_info *dx_info;
 	struct buffer_head *bh;
 	struct dx_frame *frame = frame_in;
 	u32 hash;
@@ -382,17 +383,18 @@
 	frame->bh = NULL;
 	if (!(bh = ext4_bread (NULL,dir, 0, 0, err)))
 		goto fail;
-	root = (struct dx_root *) bh->b_data;
-	if (root->info.hash_version != DX_HASH_TEA &&
-	    root->info.hash_version != DX_HASH_HALF_MD4 &&
-	    root->info.hash_version != DX_HASH_LEGACY) {
-		ext4_warning(dir->i_sb, "Unrecognised inode hash code %d for directory "
-                             "#%lu", root->info.hash_version, dir->i_ino);
+
+	dx_info = dx_get_dx_info(bh->b_data);
+	if (dx_info->hash_version != DX_HASH_TEA &&
+	    dx_info->hash_version != DX_HASH_HALF_MD4 &&
+	    dx_info->hash_version != DX_HASH_LEGACY) {
+		ext4_warning(dir->i_sb, "Unknown inode hash code %u for "
+			    "directory %lu", dx_info->hash_version, dir->i_ino);
 		brelse(bh);
 		*err = ERR_BAD_DX_DIR;
 		goto fail;
 	}
-	hinfo->hash_version = root->info.hash_version;
+	hinfo->hash_version = dx_info->hash_version;
 	if (hinfo->hash_version <= DX_HASH_TEA)
 		hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 	hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
@@ -400,27 +402,25 @@
 		ext4fs_dirhash(d_name->name, d_name->len, hinfo);
 	hash = hinfo->hash;
 
-	if (root->info.unused_flags & 1) {
+	if (dx_info->unused_flags & 1) {
 		ext4_warning(dir->i_sb, "Unimplemented inode hash flags: %#06x",
-			     root->info.unused_flags);
+			     dx_info->unused_flags);
 		brelse(bh);
 		*err = ERR_BAD_DX_DIR;
 		goto fail;
 	}
 
-	if ((indirect = root->info.indirect_levels) > 1) {
+	indirect = dx_info->indirect_levels;
+	if (indirect > 1) {
 		ext4_warning(dir->i_sb, "Unimplemented inode hash depth: %#06x",
-			     root->info.indirect_levels);
+			     dx_info->indirect_levels);
 		brelse(bh);
 		*err = ERR_BAD_DX_DIR;
 		goto fail;
 	}
 
-	entries = (struct dx_entry *) (((char *)&root->info) +
-				       root->info.info_length);
-
-	if (dx_get_limit(entries) != dx_root_limit(dir,
-						   root->info.info_length)) {
+	entries = (struct dx_entry *)((char *)dx_info + dx_info->info_length);
+	if (dx_get_limit(entries) != dx_root_limit(dir, dx_info->info_length)) {
 		ext4_warning(dir->i_sb, "dx entry: limit != root limit");
 		brelse(bh);
 		*err = ERR_BAD_DX_DIR;
@@ -504,7 +505,7 @@
 	if (frames[0].bh == NULL)
 		return;
 
-	if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
+	if (dx_get_dx_info(frames[0].bh->b_data)->indirect_levels)
 		brelse(frames[1].bh);
 	brelse(frames[0].bh);
 }
@@ -1400,17 +1403,16 @@
 	const char	*name = dentry->d_name.name;
 	int		namelen = dentry->d_name.len;
 	struct buffer_head *bh2;
-	struct dx_root	*root;
+	struct dx_root_info *dx_info;
 	struct dx_frame	frames[2], *frame;
 	struct dx_entry *entries;
-	struct ext4_dir_entry_2	*de, *de2;
+	struct ext4_dir_entry_2 *de, *de2, *dot_de, *dotdot_de;
 	char		*data1, *top;
 	unsigned	len;
 	int		retval;
 	unsigned	blocksize;
 	struct dx_hash_info hinfo;
 	ext4_lblk_t  block;
-	struct fake_dirent *fde;
 
 	blocksize =  dir->i_sb->s_blocksize;
 	dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
@@ -1420,18 +1422,18 @@
 		brelse(bh);
 		return retval;
 	}
-	root = (struct dx_root *) bh->b_data;
+
+	dot_de = (struct ext4_dir_entry_2 *)bh->b_data;
+	dotdot_de = ext4_next_entry(dot_de, blocksize);
 
 	/* The 0th block becomes the root, move the dirents out */
-	fde = &root->dotdot;
-	de = (struct ext4_dir_entry_2 *)((char *)fde +
-		ext4_rec_len_from_disk(fde->rec_len, blocksize));
-	if ((char *) de >= (((char *) root) + blocksize)) {
+	de = ext4_next_entry(dotdot_de, blocksize);
+	if ((char *)de >= bh->b_data + blocksize) {
 		EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
 		brelse(bh);
 		return -EIO;
 	}
-	len = ((char *) root) + blocksize - (char *) de;
+	len = (char *)dot_de + blocksize - (char *)de;
 
 	/* Allocate new block for the 0th block's dirents */
 	bh2 = ext4_append(handle, dir, &block, &retval);
@@ -1450,19 +1453,21 @@
 	de->rec_len = ext4_rec_len_to_disk(data1 + blocksize - (char *) de,
 					   blocksize);
 	/* Initialize the root; the dot dirents already exist */
-	de = (struct ext4_dir_entry_2 *) (&root->dotdot);
-	de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
-					   blocksize);
-	memset (&root->info, 0, sizeof(root->info));
-	root->info.info_length = sizeof(root->info);
-	root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
-	entries = root->entries;
+	dotdot_de->rec_len = ext4_rec_len_to_disk(blocksize -
+			le16_to_cpu(dot_de->rec_len), blocksize);
+
+	/* initialize hashing dx_info */
+	dx_info = dx_get_dx_info(bh->b_data);
+	memset(dx_info, 0, sizeof(*dx_info));
+	dx_info->info_length = sizeof(*dx_info);
+	dx_info->hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
+	entries = (void *)dx_info + sizeof(*dx_info);
 	dx_set_block(entries, 1);
 	dx_set_count(entries, 1);
-	dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
+	dx_set_limit(entries, dx_root_limit(dir, sizeof(*dx_info)));
 
 	/* Initialize as for dx_probe */
-	hinfo.hash_version = root->info.hash_version;
+	hinfo.hash_version = dx_info->hash_version;
 	if (hinfo.hash_version <= DX_HASH_TEA)
 		hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 	hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
@@ -1732,7 +1740,7 @@
 			/* Set up root */
 			dx_set_count(entries, 1);
 			dx_set_block(entries + 0, newblock);
-			((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
+			dx_get_dx_info(frames->bh->b_data)->indirect_levels = 1;
 
 			/* Add new access path frame */
 			frame = frames + 1;

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



[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 833 bytes --]