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. > _______________________________________________ xfs mailing list xfs@xxxxxxxxxxx http://oss.sgi.com/mailman/listinfo/xfs
