From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: ARC-Seal: i=1; a=rsa-sha256; t=1522397809; cv=none; d=google.com; s=arc-20160816; b=mnapGLTDPfkV/oa+Sp7IPYv9DlFlHaSZmSJyrFIUHSD+pZcK2uxAFg8UmuK7KmxIhg vinJWzEsbPFPlZ9Fc1I5d30vV3JREbmYx+XmmNPe46dNNMhUzS2+FwrWR/EwmhcBzm6O cyEMSEOlKO7VTVg1OrD1ajZ7QqFeAyMLxUSIbC5hEGcgjupJcY3aq6u5IuIbX2slpP+P 66sdjB9f/EIOdK3/QD6P3idthPXgJHMnbvN/v8rvgUMrGBBct0+qFzS4nRtAm1v3rIUz OGYZ9mt7hmxBD56yNudrtUMdClojXa2l9INNLDgMB5KqK8j8F0zE8GL66A0qzu+Mvqzc /OeA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature:arc-authentication-results; bh=47sVWvofKdNwuFJvbzgAe8kFJ6Tq+S03IUJifBHaXXU=; b=aq/DzkZ8gyu7ItUwgR7mBPL3SvVQqsEd01MJBovgn3ghUer6ded7fQjAM2OfAJgQ/V MEnk6dx3dK04Zo1TiYrC74JDTT7/4l+9Wn4Qqm2DyLjmdezU0j9hrOyZ29bnAG2ZTBld cpLvvGmLfMAYBipN8XczQZi55pmGUMhd4VJlgzddd2vA0mJR+0A+3Vkv5eU7MvNi1HQn SCjgPFgT7Fffk7kerXVKNb+4hI04gDVR8qNV8nr+hTnmfZkJQCCvW+FZ9r1ScJajAvxN RAwptVQ6S944ZA1R+Mig5PGEQAquSwGEFAfinnCdLJEOaol66HUDdYrWgS4pDFVE4IFE Pv4g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=Yjzc+gRf; spf=pass (google.com: domain of hejianet@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=hejianet@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=Yjzc+gRf; spf=pass (google.com: domain of hejianet@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=hejianet@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com X-Google-Smtp-Source: AIpwx49esvadygjyZB0eJlzssdtdrFKJF9ueE+BcR4YlDj7/WIYv27X0tVAi41jZXajjohsg6tRxVw== From: Jia He To: Russell King , Andrew Morton , Michal Hocko , Catalin Marinas , Mel Gorman , Will Deacon , Mark Rutland , "H. Peter Anvin" Cc: Pavel Tatashin , Daniel Jordan , AKASHI Takahiro , Gioh Kim , Steven Sistare , Daniel Vacek , Eugeniu Rosca , Vlastimil Babka , linux-kernel@vger.kernel.org, linux-mm@kvack.org, James Morse , Ard Biesheuvel , Steve Capper , Thomas Gleixner , Ingo Molnar , x86@kernel.org, Greg Kroah-Hartman , Kate Stewart , Philippe Ombredanne , Johannes Weiner , Kemi Wang , Petr Tesarik , YASUAKI ISHIMATSU , Andrey Ryabinin , Nikolay Borisov , richard.weiyang@gmail.com, Jia He , Jia He Subject: [PATCH v4 2/5] arm: arm64: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn() Date: Fri, 30 Mar 2018 01:15:52 -0700 Message-Id: <1522397755-33393-3-git-send-email-hejianet@gmail.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1522397755-33393-1-git-send-email-hejianet@gmail.com> References: <1522397755-33393-1-git-send-email-hejianet@gmail.com> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: =?utf-8?q?1596349805736411755?= X-GMAIL-MSGID: =?utf-8?q?1596349805736411755?= X-Mailing-List: linux-kernel@vger.kernel.org List-ID: Commit b92df1de5d28 ("mm: page_alloc: skip over regions of invalid pfns where possible") optimized the loop in memmap_init_zone(). But there is still some room for improvement. E.g. if pfn and pfn+1 are in the same memblock region, we can simply pfn++ instead of doing the binary search in memblock_next_valid_pfn. Signed-off-by: Jia He --- arch/arm/include/asm/page.h | 1 + arch/arm/mm/init.c | 31 ++++++++++++++++++++++++------- arch/arm64/include/asm/page.h | 1 + arch/arm64/mm/init.c | 31 ++++++++++++++++++++++++------- mm/page_alloc.c | 5 +++-- 5 files changed, 53 insertions(+), 16 deletions(-) diff --git a/arch/arm/include/asm/page.h b/arch/arm/include/asm/page.h index 4355f0e..7a0404f 100644 --- a/arch/arm/include/asm/page.h +++ b/arch/arm/include/asm/page.h @@ -157,6 +157,7 @@ extern void copy_page(void *to, const void *from); typedef struct page *pgtable_t; #ifdef CONFIG_HAVE_ARCH_PFN_VALID +extern int early_region_idx; extern int pfn_valid(unsigned long); #endif diff --git a/arch/arm/mm/init.c b/arch/arm/mm/init.c index 0fb85ca..7779804 100644 --- a/arch/arm/mm/init.c +++ b/arch/arm/mm/init.c @@ -193,6 +193,8 @@ static void __init zone_sizes_init(unsigned long min, unsigned long max_low, } #ifdef CONFIG_HAVE_ARCH_PFN_VALID +int early_region_idx __meminitdata = -1; + int pfn_valid(unsigned long pfn) { return memblock_is_map_memory(__pfn_to_phys(pfn)); @@ -200,31 +202,46 @@ int pfn_valid(unsigned long pfn) EXPORT_SYMBOL(pfn_valid); /* HAVE_MEMBLOCK is always enabled on arm */ -unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn) +unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn, + int *last_idx) { struct memblock_type *type = &memblock.memory; + struct memblock_region *regions = type->regions; unsigned int right = type->cnt; unsigned int mid, left = 0; + unsigned long start_pfn, end_pfn; phys_addr_t addr = PFN_PHYS(++pfn); + /* fast path, return pfn+1 if next pfn is in the same region */ + if (*last_idx != -1) { + start_pfn = PFN_DOWN(regions[*last_idx].base); + end_pfn = PFN_DOWN(regions[*last_idx].base + + regions[*last_idx].size); + + if (pfn >= start_pfn && pfn < end_pfn) + return pfn; + } + + /* slow path, do the binary searching */ do { mid = (right + left) / 2; - if (addr < type->regions[mid].base) + if (addr < regions[mid].base) right = mid; - else if (addr >= (type->regions[mid].base + - type->regions[mid].size)) + else if (addr >= (regions[mid].base + regions[mid].size)) left = mid + 1; else { - /* addr is within the region, so pfn is valid */ + *last_idx = mid; return pfn; } } while (left < right); if (right == type->cnt) return -1UL; - else - return PHYS_PFN(type->regions[right].base); + + *last_idx = right; + + return PHYS_PFN(regions[*last_idx].base); } EXPORT_SYMBOL(memblock_next_valid_pfn); #endif /*CONFIG_HAVE_ARCH_PFN_VALID*/ diff --git a/arch/arm64/include/asm/page.h b/arch/arm64/include/asm/page.h index 60d02c8..84b503a 100644 --- a/arch/arm64/include/asm/page.h +++ b/arch/arm64/include/asm/page.h @@ -38,6 +38,7 @@ extern void clear_page(void *to); typedef struct page *pgtable_t; #ifdef CONFIG_HAVE_ARCH_PFN_VALID +extern int early_region_idx; extern int pfn_valid(unsigned long); #endif diff --git a/arch/arm64/mm/init.c b/arch/arm64/mm/init.c index 13e43ff..cd9b473 100644 --- a/arch/arm64/mm/init.c +++ b/arch/arm64/mm/init.c @@ -285,6 +285,8 @@ static void __init zone_sizes_init(unsigned long min, unsigned long max) #endif /* CONFIG_NUMA */ #ifdef CONFIG_HAVE_ARCH_PFN_VALID +int early_region_idx __meminitdata = -1; + int pfn_valid(unsigned long pfn) { return memblock_is_map_memory(pfn << PAGE_SHIFT); @@ -292,31 +294,46 @@ int pfn_valid(unsigned long pfn) EXPORT_SYMBOL(pfn_valid); /* HAVE_MEMBLOCK is always enabled on arm64 */ -unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn) +unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn, + int *last_idx) { struct memblock_type *type = &memblock.memory; + struct memblock_region *regions = type->regions; unsigned int right = type->cnt; unsigned int mid, left = 0; + unsigned long start_pfn, end_pfn; phys_addr_t addr = PFN_PHYS(++pfn); + /* fast path, return pfn+1 if next pfn is in the same region */ + if (*last_idx != -1) { + start_pfn = PFN_DOWN(regions[*last_idx].base); + end_pfn = PFN_DOWN(regions[*last_idx].base + + regions[*last_idx].size); + + if (pfn >= start_pfn && pfn < end_pfn) + return pfn; + } + + /* slow path, do the binary searching */ do { mid = (right + left) / 2; - if (addr < type->regions[mid].base) + if (addr < regions[mid].base) right = mid; - else if (addr >= (type->regions[mid].base + - type->regions[mid].size)) + else if (addr >= (regions[mid].base + regions[mid].size)) left = mid + 1; else { - /* addr is within the region, so pfn is valid */ + *last_idx = mid; return pfn; } } while (left < right); if (right == type->cnt) return -1UL; - else - return PHYS_PFN(type->regions[right].base); + + *last_idx = right; + + return PHYS_PFN(regions[*last_idx].base); } EXPORT_SYMBOL(memblock_next_valid_pfn); #endif /*CONFIG_HAVE_ARCH_PFN_VALID*/ diff --git a/mm/page_alloc.c b/mm/page_alloc.c index 8a92df7..f99b513 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -5453,8 +5453,9 @@ void __ref build_all_zonelists(pg_data_t *pgdat) * done. Non-atomic initialization, single-pass. */ #if (defined CONFIG_HAVE_MEMBLOCK) && (defined CONFIG_HAVE_ARCH_PFN_VALID) -extern unsigned long memblock_next_valid_pfn(unsigned long pfn); -#define skip_to_last_invalid_pfn(pfn) (memblock_next_valid_pfn(pfn) - 1) +extern unsigned long memblock_next_valid_pfn(unsigned long pfn, int *last_idx); +#define skip_to_last_invalid_pfn(pfn) \ + (memblock_next_valid_pfn(pfn, &early_region_idx) - 1) #endif #ifndef skip_to_last_invalid_pfn -- 2.7.4