btrfs: obtain block checksums from user space

btrfs: obtain block checksums from user space

[Matwey V. Kornilov]

Hello,

I would like to read the list of the checksums for the specific file
stored onto btrfs filesystem. I think I could use the checksums in the
manner like rsync does, but safe both CPU (because csums are already
calculated for the file) and I/O (because I don't need to reread all the
file from the hard drive).

I've looked through linux kernel sources and not found appropriate ioctl
to do this. Frankly speaking, I've not found good documentations for all
available btrfs ioctls.

Re: btrfs: obtain block checksums from user space

[Austin S Hemmelgarn]

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

On 2015-09-24 14:06, Matwey V. Kornilov wrote:
>
> Hello,
>
> I would like to read the list of the checksums for the specific file
> stored onto btrfs filesystem. I think I could use the checksums in the
> manner like rsync does, but safe both CPU (because csums are already
> calculated for the file) and I/O (because I don't need to reread all the
> file from the hard drive).
As of right now, there is no way to do this from userspace without just 
directly parsing the on-disk format (which isn't safe or reliable if the 
filesystem is mounted). It has been discussed before, but the 
discussions haven't really gotten anywhere.

It's worth noting that the way btrfs does checksums isn't per-file, it's 
per-block. This means that:
a. I think (I'm not 100% certain about this) that the checksum in btrfs 
includes the padding up to the end of the block for blocks that aren't full.
b. Files that get stored in-line in their metadata block won't have a 
checksum just for the file data (because the checksum will cover the 
whole metadata block).
c. While it is possible with some checksum algorithms (if I remember 
right, CRC32c is one such algorithm, and that is what btrfs uses for 
it's checksums) to combine the checksums from a group of data blocks to 
get the checksum for data as a whole, this in and of itself takes a 
significant amount of CPU time for large amounts of data.

All in all, this means that if you just want a checksum of the contents 
of the file, it's almost certainly better to just do it in userspace.
If you're trying to figure out what changed, using send/receive and 
snapshots is more efficient (usually).
>
> I've looked through linux kernel sources and not found appropriate ioctl
> to do this. Frankly speaking, I've not found good documentations for all
> available btrfs ioctls.
I agree that this documentation really needs to be improved (if you want 
to take the time to figure out how it all works, patches for the 
documentation would be greatly appreciated).


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 3019 bytes --]

Re: btrfs: obtain block checksums from user space

[Matwey V. Kornilov]

2015-09-24 21:35 GMT+03:00 Austin S Hemmelgarn <ahferroin7@gmail.com>:
> On 2015-09-24 14:06, Matwey V. Kornilov wrote:
>>
>>
>> Hello,
>>
>> I would like to read the list of the checksums for the specific file
>> stored onto btrfs filesystem. I think I could use the checksums in the
>> manner like rsync does, but safe both CPU (because csums are already
>> calculated for the file) and I/O (because I don't need to reread all the
>> file from the hard drive).
>
> As of right now, there is no way to do this from userspace without just
> directly parsing the on-disk format (which isn't safe or reliable if the
> filesystem is mounted). It has been discussed before, but the discussions
> haven't really gotten anywhere.
>
> It's worth noting that the way btrfs does checksums isn't per-file, it's
> per-block. This means that:
> a. I think (I'm not 100% certain about this) that the checksum in btrfs
> includes the padding up to the end of the block for blocks that aren't full.
> b. Files that get stored in-line in their metadata block won't have a
> checksum just for the file data (because the checksum will cover the whole
> metadata block).
> c. While it is possible with some checksum algorithms (if I remember right,
> CRC32c is one such algorithm, and that is what btrfs uses for it's
> checksums) to combine the checksums from a group of data blocks to get the
> checksum for data as a whole, this in and of itself takes a significant
> amount of CPU time for large amounts of data.
>
> All in all, this means that if you just want a checksum of the contents of
> the file, it's almost certainly better to just do it in userspace.
> If you're trying to figure out what changed, using send/receive and
> snapshots is more efficient (usually).

I want the checksums of the every block of the file to see which part
has been changed.
I cannot use send/receive because my other file replica is on the
remote host but not on the same filesystem. Compare with how rsync
works. It calculates checksums of the chunks of both versions of the
file and then syncs different chunks over the network. I just want to
utilize the fact that btrfs already has the data I need to calculate.

>>
>>
>> I've looked through linux kernel sources and not found appropriate ioctl
>> to do this. Frankly speaking, I've not found good documentations for all
>> available btrfs ioctls.
>
> I agree that this documentation really needs to be improved (if you want to
> take the time to figure out how it all works, patches for the documentation
> would be greatly appreciated).
>



-- 
With best regards,
Matwey V. Kornilov
http://blog.matwey.name
xmpp://0x2207@jabber.ru

Re: btrfs: obtain block checksums from user space

[Austin S Hemmelgarn]

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

On 2015-09-24 14:48, Matwey V. Kornilov wrote:
> 2015-09-24 21:35 GMT+03:00 Austin S Hemmelgarn <ahferroin7@gmail.com>:
>> On 2015-09-24 14:06, Matwey V. Kornilov wrote:
>>>
>>>
>>> Hello,
>>>
>>> I would like to read the list of the checksums for the specific file
>>> stored onto btrfs filesystem. I think I could use the checksums in the
>>> manner like rsync does, but safe both CPU (because csums are already
>>> calculated for the file) and I/O (because I don't need to reread all the
>>> file from the hard drive).
>>
>> As of right now, there is no way to do this from userspace without just
>> directly parsing the on-disk format (which isn't safe or reliable if the
>> filesystem is mounted). It has been discussed before, but the discussions
>> haven't really gotten anywhere.
>>
>> It's worth noting that the way btrfs does checksums isn't per-file, it's
>> per-block. This means that:
>> a. I think (I'm not 100% certain about this) that the checksum in btrfs
>> includes the padding up to the end of the block for blocks that aren't full.
>> b. Files that get stored in-line in their metadata block won't have a
>> checksum just for the file data (because the checksum will cover the whole
>> metadata block).
>> c. While it is possible with some checksum algorithms (if I remember right,
>> CRC32c is one such algorithm, and that is what btrfs uses for it's
>> checksums) to combine the checksums from a group of data blocks to get the
>> checksum for data as a whole, this in and of itself takes a significant
>> amount of CPU time for large amounts of data.
>>
>> All in all, this means that if you just want a checksum of the contents of
>> the file, it's almost certainly better to just do it in userspace.
>> If you're trying to figure out what changed, using send/receive and
>> snapshots is more efficient (usually).
>
> I want the checksums of the every block of the file to see which part
> has been changed.
> I cannot use send/receive because my other file replica is on the
> remote host but not on the same filesystem. Compare with how rsync
> works. It calculates checksums of the chunks of both versions of the
> file and then syncs different chunks over the network. I just want to
> utilize the fact that btrfs already has the data I need to calculate.
On current versions of btrfs-progs, btrfs send has a mode that will just 
spit out the metadata, which can then be parsed to figure out what has 
changed.  The parsing is of course non-trivial, but should still be 
faster than checksumming everything, and I'm relatively sure (although I 
may be wrong) that the send stream format is well documented.



[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 3019 bytes --]

Re: btrfs: obtain block checksums from user space

[Calvin Walton]

On Thu, 2015-09-24 at 21:48 +0300, Matwey V. Kornilov wrote:
> 2015-09-24 21:35 GMT+03:00 Austin S Hemmelgarn <ahferroin7@gmail.com>
> :
> > On 2015-09-24 14:06, Matwey V. Kornilov wrote:

> > It's worth noting that the way btrfs does checksums isn't per-file, 
> > it's
> > per-block. This means that:
[...]
> > All in all, this means that if you just want a checksum of the
> > contents of
> > the file, it's almost certainly better to just do it in userspace.
> > If you're trying to figure out what changed, using send/receive and
> > snapshots is more efficient (usually).
> 
> I want the checksums of the every block of the file to see which part
> has been changed.
> I cannot use send/receive because my other file replica is on the
> remote host but not on the same filesystem. Compare with how rsync
> works. It calculates checksums of the chunks of both versions of the
> file and then syncs different chunks over the network. I just want to
> utilize the fact that btrfs already has the data I need to calculate.

The problem with trying to use btrfs checksums to compare two different
files is that the blocks might not match up, if only due to
fragmentation. E.g., the same 1gb file might be stored like this on one
machine:

[ 256MB ][    512 MB    ][ 256MB ]

And like this on the other:
[     512MB     ][     512MB     ]

Since the checksums are per block, and the blocks can be different
arrangements on different machines, they're not really all that useful
for doing comparisons like you want.

-- 
Calvin Walton <calvin.walton@kepstin.ca>

Re: btrfs: obtain block checksums from user space

[Hugo Mills]

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

On Mon, Sep 28, 2015 at 07:11:51PM -0400, Calvin Walton wrote:
> On Thu, 2015-09-24 at 21:48 +0300, Matwey V. Kornilov wrote:
> > 2015-09-24 21:35 GMT+03:00 Austin S Hemmelgarn <ahferroin7@gmail.com>
> > :
> > > On 2015-09-24 14:06, Matwey V. Kornilov wrote:
> 
> > > It's worth noting that the way btrfs does checksums isn't per-file, 
> > > it's
> > > per-block. This means that:
> [...]
> > > All in all, this means that if you just want a checksum of the
> > > contents of
> > > the file, it's almost certainly better to just do it in userspace.
> > > If you're trying to figure out what changed, using send/receive and
> > > snapshots is more efficient (usually).
> > 
> > I want the checksums of the every block of the file to see which part
> > has been changed.
> > I cannot use send/receive because my other file replica is on the
> > remote host but not on the same filesystem. Compare with how rsync
> > works. It calculates checksums of the chunks of both versions of the
> > file and then syncs different chunks over the network. I just want to
> > utilize the fact that btrfs already has the data I need to calculate.
> 
> The problem with trying to use btrfs checksums to compare two different
> files is that the blocks might not match up, if only due to
> fragmentation. E.g., the same 1gb file might be stored like this on one
> machine:
> 
> [ 256MB ][    512 MB    ][ 256MB ]
> 
> And like this on the other:
> [     512MB     ][     512MB     ]
> 
> Since the checksums are per block, and the blocks can be different
> arrangements on different machines, they're not really all that useful
> for doing comparisons like you want.

   No, those are extents, not blocks, and the FS doesn't checksum in
extents. :) Blocks are 4 KiB in size.

   Hugo.

-- 
Hugo Mills             | SCSI is usually fixed by remembering that it needs
hugo@... carfax.org.uk | three terminations: One at each end of the chain.
http://carfax.org.uk/  | And the goat.
PGP: E2AB1DE4          |                             Andrew McDonald, HantsLUG

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

Re: btrfs: obtain block checksums from user space

[Calvin Walton]

On Mon, 2015-09-28 at 23:16 +0000, Hugo Mills wrote:
> On Mon, Sep 28, 2015 at 07:11:51PM -0400, Calvin Walton wrote:

> > 
> > The problem with trying to use btrfs checksums to compare two
> > different
> > files is that the blocks might not match up, if only due to
> > fragmentation. E.g., the same 1gb file might be stored like this on
> > one
> > machine:
> > 
> > [ 256MB ][    512 MB    ][ 256MB ]
> > 
> > And like this on the other:
> > [     512MB     ][     512MB     ]
> > 
> > Since the checksums are per block, and the blocks can be different
> > arrangements on different machines, they're not really all that
> > useful
> > for doing comparisons like you want.
> 
>    No, those are extents, not blocks, and the FS doesn't checksum in
> extents. :) Blocks are 4 KiB in size.

Oh, wow, btrfs is storing a lot more checksums than I thought it was...

Thanks for clearing up my misconception.

-- 
Calvin Walton <calvin.walton@kepstin.ca>

Re: btrfs: obtain block checksums from user space

[David Sterba]

On Thu, Sep 24, 2015 at 09:06:32PM +0300, Matwey V. Kornilov wrote:
> I would like to read the list of the checksums for the specific file
> stored onto btrfs filesystem. I think I could use the checksums in the
> manner like rsync does, but safe both CPU (because csums are already
> calculated for the file) and I/O (because I don't need to reread all the
> file from the hard drive).
> 
> I've looked through linux kernel sources and not found appropriate ioctl
> to do this. Frankly speaking, I've not found good documentations for all
> available btrfs ioctls.

I have the ioctl docs in my todo and barely started it. There's no
single ioctl for getting the per-block checksums but it is possible
using several calls to the SEARCH_TREE. I have a prototype in my gits in
branch dev/block-csum-search (2nd patch from the top), I'll try to find
some time to make it a proper subcommand, so far the command UI is not
righ enough and the output is quite rough.