xfs
[Top] [All Lists]

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

To: Dave Chinner <david@xxxxxxxxxxxxx>
Subject: Re: [PATCH 2/2] repair: don't grind CPUs with large extent lists
From: Eric Sandeen <sandeen@xxxxxxxxxxx>
Date: Thu, 08 May 2014 23:18:48 -0500
Cc: xfs@xxxxxxxxxxx
Delivered-to: xfs@xxxxxxxxxxx
In-reply-to: <20140509035653.GJ26353@dastard>
References: <1399598222-4349-1-git-send-email-david@xxxxxxxxxxxxx> <1399598222-4349-3-git-send-email-david@xxxxxxxxxxxxx> <536C4511.3050201@xxxxxxxxxxx> <20140509035653.GJ26353@dastard>
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.5.0
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@xxxxxxxxxx>
>>>
>>> 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@xxxxxxxxxx>

- thanks for getting these done.

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

<Prev in Thread] Current Thread [Next in Thread>