Re: [patch] mm: speedup in __early_pfn_to_nid

[Yinghai Lu <yinghai@kernel.org>]

[-- Attachment #1: Type: text/plain, Size: 1317 bytes --]

On Mon, Mar 25, 2013 at 2:56 PM, Russ Anderson <rja@sgi.com> wrote:
> On Mon, Mar 25, 2013 at 10:11:27AM +0800, Lin Feng wrote:
>> On 03/24/2013 04:37 AM, Yinghai Lu wrote:
>> > +#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
>> > +int __init_memblock memblock_search_pfn_nid(unsigned long pfn,
>> > +                    unsigned long *start_pfn, unsigned long *end_pfn)
>> > +{
>> > +   struct memblock_type *type = &memblock.memory;
>> > +   int mid = memblock_search(type, (phys_addr_t)pfn << PAGE_SHIFT);
>>
>> I'm really eager to see how much time can we save using binary search compared to
>> linear search in this case :)
>
> I have machine time tonight to measure the difference.
>
> Based on earlier testing, a system with 9TB memory calls
> __early_pfn_to_nid() 2,377,198,300 times while booting, but
> only 6815 times does it not find that the memory range is
> the same as previous and search the table.  Caching the
> previous range avoids searching the table 2,377,191,485 times,
> saving a significant amount of time.
>
> Of the remaining 6815 times when it searches the table, a binary
> search may help, but with relatively few calls it may not
> make much of an overall difference.  Testing will show how much.

Please check attached patch that could be applied on top of your patch
in -mm.

Thanks

Yinghai

[-- Attachment #2: memblock_search_pfn_nid.patch --]
[-- Type: application/octet-stream, Size: 2761 bytes --]

---
 include/linux/memblock.h |    2 ++
 mm/memblock.c            |   18 ++++++++++++++++++
 mm/page_alloc.c          |   19 +++++++++----------
 3 files changed, 29 insertions(+), 10 deletions(-)

Index: linux-2.6/include/linux/memblock.h
===================================================================
--- linux-2.6.orig/include/linux/memblock.h
+++ linux-2.6/include/linux/memblock.h
@@ -63,6 +63,8 @@ int __memblock_reserve(phys_addr_t base,
 void memblock_trim_memory(phys_addr_t align);
 
 #ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
+int memblock_search_pfn_nid(unsigned long pfn, unsigned long *start_pfn,
+			    unsigned long  *end_pfn);
 void __next_mem_pfn_range(int *idx, int nid, unsigned long *out_start_pfn,
 			  unsigned long *out_end_pfn, int *out_nid);
 
Index: linux-2.6/mm/memblock.c
===================================================================
--- linux-2.6.orig/mm/memblock.c
+++ linux-2.6/mm/memblock.c
@@ -954,6 +954,24 @@ int __init_memblock memblock_is_memory(p
 	return memblock_search(&memblock.memory, addr) != -1;
 }
 
+#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
+int __init_memblock memblock_search_pfn_nid(unsigned long pfn,
+			 unsigned long *start_pfn, unsigned long *end_pfn)
+{
+	struct memblock_type *type = &memblock.memory;
+	int mid = memblock_search(type, (phys_addr_t)pfn << PAGE_SHIFT);
+
+	if (mid == -1)
+		return -1;
+
+	*start_pfn = type->regions[mid].base >> PAGE_SHIFT;
+	*end_pfn = (type->regions[mid].base + type->regions[mid].size)
+			>> PAGE_SHIFT;
+
+	return type->regions[mid].nid;
+}
+#endif
+
 /**
  * memblock_is_region_memory - check if a region is a subset of memory
  * @base: base of region to check
Index: linux-2.6/mm/page_alloc.c
===================================================================
--- linux-2.6.orig/mm/page_alloc.c
+++ linux-2.6/mm/page_alloc.c
@@ -4166,7 +4166,7 @@ int __meminit init_currently_empty_zone(
 int __meminit __early_pfn_to_nid(unsigned long pfn)
 {
 	unsigned long start_pfn, end_pfn;
-	int i, nid;
+	int nid;
 	/*
 	 * NOTE: The following SMP-unsafe globals are only used early
 	 * in boot when the kernel is running single-threaded.
@@ -4177,15 +4177,14 @@ int __meminit __early_pfn_to_nid(unsigne
 	if (last_start_pfn <= pfn && pfn < last_end_pfn)
 		return last_nid;
 
-	for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
-		if (start_pfn <= pfn && pfn < end_pfn) {
-			last_start_pfn = start_pfn;
-			last_end_pfn = end_pfn;
-			last_nid = nid;
-			return nid;
-		}
-	/* This is a memory hole */
-	return -1;
+	nid = memblock_search_pfn_nid(pfn, &start_pfn, &end_pfn);
+	if (nid != -1) {
+		last_start_pfn = start_pfn;
+		last_end_pfn = end_pfn;
+		last_nid = nid;
+	}
+
+	return nid;
 }
 #endif /* CONFIG_HAVE_ARCH_EARLY_PFN_TO_NID */