Can I get a checksum for a file from btrfs (without reading the whole file)?
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
-------- 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
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
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.