[PATCH 3/3] XFS: Sort delayed write buffers before dispatch

[Andi Kleen]

Dave Chinner <david at fromorbit.com> writes:

> Currently when the xfsbufd writes delayed write buffers, it pushes
> them to disk in the order they come off the delayed write list. If
> there are lots of buffers Ñ•pread widely over the disk, this results
> in overwhelming the elevator sort queues in the block layer and we
> end up losing the posibility of merging adjacent buffers to minimise
> the number of IOs.
>
> Add a sort array to the buftarg so that we can do high level sorting
> of the buffers once they are pulled off the delwri queue for
> writeback. Currently this array can hold 4096 buffers at a time
> which gives us a window 32 times larger than the default elevator
> maximums for ordering buffers.

At first look it seems a bit wasteful because the elevator
sorts again. Is your window that much bigger than the elevators?
Perhaps the sort queue in the elevator should be just enlarged?

>
> Ideally this should use a list sort rather than requiring an
> external buffer to sort the buffers in, but for simplicity
> just do it via sort function.

Doing merge sort on lists is relatively simple There are
plenty examples in a google search. An alternative is also
to construct a rbtree on the fly and then walk it.

But if you use sort() this way you probably should at least
add a u64 swap function to lib/sort.c, otherwise
all the pointers will be exchanged byte-by-byte on 64bit
systems which is rather slow.

-andi


-- 
ak at linux.intel.com -- Speaking for myself only.