From: William Lee Irwin III <wli@holomorphy.com>

Based on Arjan van de Ven's idea, with guidance and testing from James
Bottomley.

The physical ordering of pages delivered to the IO subsystem is strongly
related to the order in which fragments are subdivided from larger blocks
of memory tracked by the page allocator.

Consider a single MAX_ORDER block of memory in isolation acted on by a
sequence of order 0 allocations in an otherwise empty buddy system.
Subdividing the block beginning at the highest addresses will yield all the
pages of the block in reverse, and subdividing the block begining at the
lowest addresses will yield all the pages of the block in physical address
order.

Empirical tests demonstrate this ordering is preserved, and that changing
the order of subdivision so that the lowest page is split off first
resolves the sglist merging difficulties encountered by driver authors at
Adaptec and others in James Bottomley's testing.

James found that before this patch, there were 40 merges out of about 32K
segments.  Afterward, there were 24007 merges out of 19513 segments, for a
merge rate of about 55%.  Merges of 128 segments, the maximum allowed, were
observed afterward, where beforehand they never occurred.  It also improves
dbench on my workstation and works fine there.
Signed-off-by: William Lee Irwin III <wli@holomorphy.com>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>