On 2015-08-12 15:30, Chris Murphy wrote:
Yeah, duperemove doesn't use them because of the memory limitations. Theoretically it's possible to take the the CRC checksums of the individual blocks and then combine them to get a checksum of the blocks as a whold, but it really isn't worth it for that (it would take just about as long as the current hashing.On Wed, Aug 12, 2015 at 12:44 PM, Konstantin Svist <fry....@gmail.com> wrote:On 08/06/2015 04:10 AM, Austin S Hemmelgarn wrote:On 2015-08-05 17:45, Konstantin Svist wrote:Hi,I've been running btrfs on Fedora for a while now, with bedup --defrag running in a night-time cronjob. Last few runs seem to have gotten stuck, without possibility of even killing the process (kill -9 doesn't work) -- all I could do is hard power cycle. Did something change recently? Is bedup simply too out of date? What should I use to de-duplicate across snapshots instead? Etc.?AFAIK, bedup hasn't been actively developed for quite a while (I'm actually kind of surprised it runs with the newest btrfs-progs). Personally, I'd suggest using duperemove (https://github.com/markfasheh/duperemove)Thanks, good to know. Tried duperemove -- it looks like it builds a database of its own checksums every time it runs... why won't it use BTRFS internal checksums for fast rejection? Would run a LOT faster...I think the reason is duperremove does extent based deduplication. Where Btrfs checksums are 4KiB block based, not extent based. And so many 4KiB CRC32C checksums would need to be in memory, that could be kinda expensive. And also, I don't know if CRC32C checksums have essentially no practical chance of collision. If it's really rare, rather than "so improbable as to be impossible" then you could end up with "really rare" corruption where incorrect deduplication happens.
As for the collision properties of CRC32C, it's actually almost trivial to construct collisions. The reason that it is used in BTRFS is because there is a functional guarantee that any single bit error in a block _will_ result in a different CRC, and most larger errors will also. In other words, the usage of CRC32C in BTRFS is for error detection and because it's ridiculously fast on all modern processors. As far as the possibility of incorrect deduplication, the kernel does a bytewise comparison of the extents submitted before actually deduplicating them, so there's no chance (barring hardware issues and/or external influence from a ill-intentioned third-party) of it happening. Because of this, you could theoretically just call the ioctl on every possible combination of extents in the FS, but that would take a ridiculous amount of time (especially because calls involving the same byte ranges get internally serialized by the kernel), which is why we have programs like duperemove (while the hashing has to read all the data too, it's still a lot faster than just comparing all of it directly).
I'm pretty sure that that patch never made it into the kernel (the original one was for the kernel, not the userspace programs, and it never got brought in because the argument for it (better protection against malicious intent) was inherently invalid for the usage of checksums in BTRFS (if someone can rewrite your data arbitrarily on disk, they can do so for the checksums also)), and that it was block based (and as such less useful for deduplication than the CRC32C that we are currently using).There was a patch late last year I think to re-introduce sha256 hash as the checksum, but as far as I know it's not in btrfs-progs yet. I forget if that's file, extent or block based.
smime.p7s
Description: S/MIME Cryptographic Signature
