Re: [PATCH 2/2] repair: don't grind CPUs with large extent lists

[Eric Sandeen <sandeen@sandeen.net>]

On 5/8/14, 10:56 PM, Dave Chinner wrote:
> On Thu, May 08, 2014 at 10:01:37PM -0500, Eric Sandeen wrote:
>> On 5/8/14, 8:17 PM, Dave Chinner wrote:
>>> From: Dave Chinner <dchinner@redhat.com>
>>>
>>> When repairing a large filesystem with fragemented files, xfs_repair
>>> can grind to a halt burning multiple CPUs in blkmap_set_ext().
>>> blkmap_set_ext() inserts extents into the blockmap for the inode
>>> fork and it keeps them in order, even if the inserts are not done in
>>> order.
>>>
>>> The ordered insert is highly inefficient - it starts at the first
>>> extent, and simple walks the array to find the insertion point. i.e.
>>> it is an O(n) operation. When we have a fragemented file with a
>>> large number of extents, the cost of the entire mapping operation
>>> is rather costly.
>>>
>>> The thing is, we are doing the insertion from an *ordered btree
>>> scan* which is inserting the extents in ascending offset order.
>>> IOWs, we are always inserting the extent at the end of the array
>>> after searching the entire array. i.e. the mapping operation cost is
>>> O(N^2).
>>>
>>> Fix this simply by reversing the order of the insert slot search.
>>> Start at the end of the blockmap array when we do almost all
>>> insertions, which brings the overhead of each insertion down to O(1)
>>> complexity. This, in turn, results in the overall map building
>>> operation being reduced to an O(N) operation, and so performance
>>> degrades linearly with increasing extent counts rather than
>>> exponentially.
>>>
>>> The result is that the test filesystem (27TB, 30M inodes, at ENOSPC)
>>> takes 5m10s to *fully repair* on my test system, rather that getting
>>> 15 (of 60) AGs into phase three and sitting there burning 3-4 CPUs
>>> making no progress for over half an hour.
>>
>> Did the blkmap_grow() changes sneak in here accidentally?
> 
> Ah, forgot to mention them. Do a realloc every 4 entries when we
> have hundreds of thousands of extents is just silly ;)

<snip>

> OK, I'll add "because we are doing an ascending offset order scan of
> the bmapbt" or words to that effect.

Ok, with those agreed-upon changes feel free to add a 

Reviewed-by: Eric Sandeen <sandeen@redhat.com>

- thanks for getting these done.

-Eric
 
> Thanks!
> 
> Cheers,
> 
> Dave.
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs