[RFC PATCH] mm: memblock: optimize memblock_find_in_range_node() to minimize the search work

From: Lin Feng
Date: Fri Jan 04 2013 - 04:35:56 EST

The memblock array is in ascending order and we traverse the memblock array in
reverse order so we can add some simple check to reduce the search work.

Tejun fix a underflow bug in 5d53cb27d8, but I think we could break there for
the same reason.

Cc: Tejun Heo <tj@xxxxxxxxxx>
Signed-off-by: Lin Feng <linfeng@xxxxxxxxxxxxxx>
mm/memblock.c | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 6259055..a710557 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -111,11 +111,18 @@ phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t start,
end = max(start, end);

for_each_free_mem_range_reverse(i, nid, &this_start, &this_end, NULL) {
+ /*
+ * exclude the regions out of the candidate range, since it's
+ * likely to find a suitable range, we ignore the worst case.
+ */
+ if (this_start >= end)
+ continue;
this_start = clamp(this_start, start, end);
this_end = clamp(this_end, start, end);

if (this_end < size)
- continue;
+ break;

cand = round_down(this_end - size, align);
if (cand >= this_start)

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/