Re: [PATCH] btrfs: fix check_shared for fiemap ioctl

From: Qu Wenruo <quwenruo@cn.fujitsu.com>
To: <dsterba@suse.cz>, Lu Fengqi <lufq.fnst@cn.fujitsu.com>,
	<linux-btrfs@vger.kernel.org>
Subject: Re: [PATCH] btrfs: fix check_shared for fiemap ioctl
Date: Tue, 31 May 2016 08:38:25 +0800	[thread overview]
Message-ID: <b91c1b77-39ee-1a75-a530-4618f7765bd6@cn.fujitsu.com> (raw)
In-Reply-To: <20160530151528.GB29147@twin.jikos.cz>

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