Skip to contentSkip to conversation

Can I get a checksum for a file from btrfs (without reading the whole file)?

DISCUSSION Lutz Vieweg 3 participants 4 messages Feb 5, 2015 – Feb 6, 2015 Btrfs file system

lore
Share & tools
lore
#0 lore raw

Hi,

use case: You have two huge files on a btrfs, you assume they contain the same bytes, but you do not know for sure.

Is there a way to get a checksum of both files from btrfs with less effort than reading the whole of both files and computing a hash sum?

(I was thinking that the btrfs-internal CRCs might be of use, here...)

Regards,

Lutz Vieweg

#1 lore raw

-------- Original Message --------
Subject: Can I get a checksum for a file from btrfs (without reading the whole file)?
From: Lutz Vieweg <[email protected]>
To: <[email protected]>
Date: 2015年02月05日 18:40

Quoted 7 lines

Hi,

use case: You have two huge files on a btrfs, you assume they contain the same bytes, but you do not know for sure.

Is there a way to get a checksum of both files from btrfs with less effort than reading the whole of both files and computing a hash sum?

For short, NO.

For long:
For current implement, btrfs use calculate 4K sector into 4bytes(32bit) crc32 and restore it into csum tree.

So, for large files, e.g. 1G(already quite small for modern storage), its checksum will be 1M in size. Which means even using crc32 (same as kernel and crc32(a+b) = crc32(a) + crc32(b)), you still needs to do crc32 on the all 1M crc32.
And if you want other checksum like md5/sha256, you have no choice but read them all and calculate.

But there is still some case btrfs can help you determine whether the files are the same in a faster way.
Prerequisite:
The two files are copied using clone(cp --reflink command) or deduplicated(see btrfs wiki:https://btrfs.wiki.kernel.org/index.php/Deduplication)

Method:
If cloned/deduplicated, file will share same file extents (one can up to 128M). So you can compare file extents to compare the whole file.
Per 128M compare will be definitely faster. (if not modified after cp --clone or deduplication)

I didn't see such implement yet, so it's just a concept...

Thanks,
Qu

Quoted 11 lines

(I was thinking that the btrfs-internal CRCs might be of use, here...)

Regards,

Lutz Vieweg

Signature · 3 lines
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#2 lore raw
Quoted 8 lines · Qu Wenruo

From: Lutz Vieweg <[email protected]>

Quoted 5 lines

use case: You have two huge files on a btrfs, you assume they contain the same bytes, but you do not know for sure.

Is there a way to get a checksum of both files from btrfs with less effort than reading the whole of both files and computing a hash sum?

For short, NO.

Quoted 7 lines

For long:
For current implement, btrfs use calculate 4K sector into 4bytes(32bit) crc32 and restore it into csum tree.

So, for large files, e.g. 1G(already quite small for modern storage), its checksum will be 1M in size. Which means even using crc32 (same as kernel and crc32(a+b) = crc32(a) + crc32(b)), you still needs to do crc32 on the all 1M crc32.

And yet, having to read only 1 MB checksums instead of 1 GB data sounds like a good deal - is there some userspace interface allowing to read (only) those per-4k checksums for a file?

Quoted 4 lines

But there is still some case btrfs can help you determine whether the files are the same in a faster way.
Prerequisite:
The two files are copied using clone(cp --reflink command) or deduplicated

In my case I know for sure that no cloning/deduplication happened when the files were written.

Regards,

Lutz Vieweg

#3 lore raw
Quoted 13 lines · Lutz Vieweg
Quoted 12 lines · Qu Wenruo

From: Lutz Vieweg <[email protected]>

Quoted 5 lines

use case: You have two huge files on a btrfs, you assume they contain the same bytes, but you do not know for sure.

Is there a way to get a checksum of both files from btrfs with less effort than reading the whole of both files and computing a hash sum?

For short, NO.

For long:
For current implement, btrfs use calculate 4K sector into 4bytes(32bit) crc32 and restore it into csum tree.

Quoted 7 lines
Quoted 3 lines

So, for large files, e.g. 1G(already quite small for modern storage), its checksum will be 1M in size. Which means even using crc32 (same as kernel and crc32(a+b) = crc32(a) + crc32(b)), you still needs to do crc32 on the all 1M crc32.

And yet, having to read only 1 MB checksums instead of 1 GB data sounds like a good deal - is there some userspace interface allowing to read (only) those per-4k checksums for a file?

Just a POC code how to get the csum for a given block (based on the SEARCH ioctl, needs root):

http://repo.or.cz/w/btrfs-progs-unstable/devel.git/commit/33a4d171552736da2977323797f53d9cea830e2f

crc32 is weak but can be used to detect early(-ier) if the files are different. A hash collision in the middle of huge files is possible but I guess very low.