Re: bedup --defrag freezing

[Austin S Hemmelgarn <ahferroin7@gmail.com>]

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

On 2015-08-12 15:30, Chris Murphy wrote:
> On Wed, Aug 12, 2015 at 12:44 PM, Konstantin Svist <fry.kun@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.
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.

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).
>
> 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.
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).



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