Identifying reflink / CoW files
Hello,
Following the previous discussion:
https://www.spinics.net/lists/linux-btrfs/msg19075.html
I would be interested in finding a way to reliably identify reflink / CoW files in order to use deduplication programs (like fdupes, jdupes, rmlint) efficiently.
Using FIEMAP doesn't seem to be reliable according to this discussion on rmlint:
https://github.com/sahib/rmlint/issues/132#issuecomment-157665154
Is there another way that deduplication programs can easily use ?
Thanks
Quoted 5 lines · Saint Germain
Hello,
Following the previous discussion:
https://www.spinics.net/lists/linux-btrfs/msg19075.html
Quoted 7 lines
I would be interested in finding a way to reliably identify reflink / CoW files in order to use deduplication programs (like fdupes, jdupes, rmlint) efficiently.
Using FIEMAP doesn't seem to be reliable according to this discussion on rmlint:
https://github.com/sahib/rmlint/issues/132#issuecomment-157665154
Inline extents have no physical address (FIEMAP returns 0 in that field). You can't dedup them and each file can have only one, so if you see the FIEMAP_EXTENT_INLINE bit set, you can just skip processing the entire file immediately.
You can create a separate non-inline extent in a temporary file then use dedup to replace _both_ copies of the original inline extent. Or don't bother, as the savings are negligible.
Quoted 1 line
Is there another way that deduplication programs can easily use ?
The problem is that it's not files that are reflinked--individual extents are. "reflink file copy" really just means "a file whose extents are 100% shared with another file." It's possible for files on btrfs to have any percentage of shared extents from 0 to 100% in increments of the host page size. It's also possible for the blocks to be shared with different extent boundaries.
The quality of the result therefore depends on the amount of effort put into measuring it. If you look for the first non-hole extent in each file and use its physical address as a physical file identifier, then you get a fast reflink detector function that has a high risk of false positives. If you map out two files and compare physical addresses block by block, you get a slow function with a low risk of false positives (but maybe a small risk of false negatives too).
If your dedup program only does full-file reflink copies then the first extent physical address method is sufficient. If your program does block- or extent-level dedup then it shouldn't be using files in its data model at all, except where necessary to provide a mechanism to access the physical blocks through the POSIX filesystem API.
FIEMAP will tell you about all the extents (physical address for extents that have them, zero for other extent types). It's also slow and has assorted accuracy problems especially with compressed files. Any user can run FIEMAP, and it uses only standard structure arrays.
SEARCH_V2 is root-only and requires parsing variable-length binary btrfs data encoding, but it's faster than FIEMAP and gives more accurate results on compressed files.
Quoted 5 lines
Thanks
--
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 46 lines · Zygo Blaxell
Quoted 5 lines · Saint Germain
Hello,
Following the previous discussion:
https://www.spinics.net/lists/linux-btrfs/msg19075.htmlQuoted 7 lines
I would be interested in finding a way to reliably identify reflink / CoW files in order to use deduplication programs (like fdupes, jdupes, rmlint) efficiently.
Using FIEMAP doesn't seem to be reliable according to this discussion on rmlint:
https://github.com/sahib/rmlint/issues/132#issuecomment-157665154Inline extents have no physical address (FIEMAP returns 0 in that field). You can't dedup them and each file can have only one, so if you see the
FIEMAP_EXTENT_INLINEbit set, you can just skip processing the entire file immediately.You can create a separate non-inline extent in a temporary file then use dedup to replace _both_ copies of the original inline extent. Or don't bother, as the savings are negligible.
Quoted 1 line
Is there another way that deduplication programs can easily use ?
The problem is that it's not files that are reflinked--individual extents are. "reflink file copy" really just means "a file whose extents are 100% shared with another file." It's possible for files on btrfs to have any percentage of shared extents from 0 to 100% in increments of the host page size. It's also possible for the blocks to be shared with different extent boundaries.
The quality of the result therefore depends on the amount of effort put into measuring it. If you look for the first non-hole extent in each file and use its physical address as a physical file identifier, then you get a fast reflink detector function that has a high risk of false positives. If you map out two files and compare physical addresses block by block, you get a slow function with a low risk of false positives (but maybe a small risk of false negatives too).
If your dedup program only does full-file reflink copies then the first extent physical address method is sufficient. If your program does block- or extent-level dedup then it shouldn't be using files in its data model at all, except where necessary to provide a mechanism to access the physical blocks through the POSIX filesystem API.
Quoted 9 lines
FIEMAP will tell you about all the extents (physical address for extents that have them, zero for other extent types). It's also slow and has assorted accuracy problems especially with compressed files. Any user can run FIEMAP, and it uses only standard structure arrays.
SEARCH_V2is root-only and requires parsing variable-length binary btrfs data encoding, but it's faster than FIEMAP and gives more accurate results on compressed files.
As the dedup program only does full-file reflink, the first extent physical address method can be used as a fast first check to identify potential files.
But how to implement the second check in order to have 0% risk of false positive ?
Because you said that mapping out two files and comparing the physical addresses block by block also has a low risk of false positives.
Thank you very much for the detailed explanation !
Quoted 26 lines · Saint Germain
Quoted 15 lines · Zygo Blaxell
[...]
The quality of the result therefore depends on the amount of effort put into measuring it. If you look for the first non-hole extent in each file and use its physical address as a physical file identifier, then you get a fast reflink detector function that has a high risk of false positives. If you map out two files and compare physical addresses block by block, you get a slow function with a low risk of false positives (but maybe a small risk of false negatives too).If your dedup program only does full-file reflink copies then the first extent physical address method is sufficient. If your program does block- or extent-level dedup then it shouldn't be using files in its data model at all, except where necessary to provide a mechanism to access the physical blocks through the POSIX filesystem API.
Quoted 8 lines
FIEMAP will tell you about all the extents (physical address for extents that have them, zero for other extent types). It's also slow and has assorted accuracy problems especially with compressed files. Any user can run FIEMAP, and it uses only standard structure arrays.
SEARCH_V2is root-only and requires parsing variable-length binary btrfs data encoding, but it's faster than FIEMAP and gives more accurate results on compressed files.
Quoted 8 lines
As the dedup program only does full-file reflink, the first extent physical address method can be used as a fast first check to identify potential files.
But how to implement the second check in order to have 0% risk of false positive ?
Because you said that mapping out two files and comparing the physical addresses block by block also has a low risk of false positives.
In theory, what you do is call FIEMAP on each file and compare the physical blocks that come back. If they are large files you will have to call FIEMAP multiple times on both files, each time setting the start position to the end position of the previous run. Translate each result record into a range of physical addresses, then compare them. If there were no differences, the files are already deduped.
In practice, FIEMAP doesn't provide full accuracy for compressed extents, and in some cases the physical address data will compare equal when the files are in fact different. This is the small risk of false positives, and the only way to get 100% accuracy is to not use FIEMAP.
Instead you can use the SEARCH ioctl, which dumps out the binary extent items from btrfs. If you look up the items corresponding to one inode, you can get the real physical block address plus the offset from the beginning of the extent for compressed extents.
In Bees I encode the compressed extent start offset into the same uint64_t as the physical extent start address using the bottom 6 bits of the physical (bytenr) address:
https://github.com/Zygo/bees/blob/master/src/bees-types.cc#L744
This fills in an object which uniquely (and reversibly) identifies the block on the filesystem.
The raw btrfs extent data is extracted here:
https://github.com/Zygo/bees/blob/master/lib/extentwalker.cc#L533
BeesAddress gives no false positives, but it's built on top of hundreds of lines of userspace support code. :-/
Quoted 5 lines
Thank you very much for the detailed explanation !
--
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