David Sterba wrote on 2016/05/30 17:15 +0200:
On Fri, May 27, 2016 at 09:39:53AM +0800, Qu Wenruo wrote:
Any comment?
This patch does not fix the submitted generic/352[1] and generic/353[2]
test cases, but also introduce a much better structure and design for
later backref walk use.
Instead of a list and do a O(n^3)~O(n^4) iteration for fiemap ioctl on a
reflinked(deduped) file, it's now only O(n)~O(nlogn) for SHARED flag
check to pass generic/352.
This is a good improvement, though there's potentially hidden cost in
the allocations and maintaining the temporary structures. Do you have
actual performance numbers?
Test case generic/352 is already the proof.
For a 1G file whose all file extents are pointing to the same 128K file
extent, fiemap will just soft lockup for backref walk.
Even for case(*) it doesn't hang, it takes about 3~4 seconds to do
check_shared() for one extent.
With this patch, chech_shared() returned immediately, if found any other
delayed ref/extent ref, making the whole fiemap ioctl super fast for
deduped file case.
*: Two 1G file, inside the same subvolume, pointing to the same 128K
file extent will not cause soft lockup.
We can use such patch to rework current backref walk code, which does
unneeded list iteration instead of faster rb tree search, but it's too
aggressive, and we want to do it step by step, starting from these bugs
exposed by inband dedupe.
Thanks,
Qu
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
