From: Mike Rapoport <rppt@linux.ibm.com> To: Hanjun Guo <guohanjun@huawei.com> Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>, Andrew Morton <akpm@linux-foundation.org>, Catalin Marinas <catalin.marinas@arm.com>, Jia He <hejianet@gmail.com>, Will Deacon <will@kernel.org>, linux-arm-kernel@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH v12 2/2] mm: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn Date: Tue, 23 Jul 2019 11:33:54 +0300 [thread overview] Message-ID: <20190723083353.GC4896@rapoport-lnx> (raw) In-Reply-To: <1563861073-47071-3-git-send-email-guohanjun@huawei.com> On Tue, Jul 23, 2019 at 01:51:13PM +0800, Hanjun Guo wrote: > From: Jia He <hejianet@gmail.com> > > After skipping some invalid pfns in memmap_init_zone(), 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. > > Furthermore, if the pfn is in a gap of two memory region, skip to next > region directly to speedup the binary search. How much speed up do you see with this improvements relatively to simple binary search in memblock_next_valid_pfn()? > Signed-off-by: Jia He <hejianet@gmail.com> > Signed-off-by: Hanjun Guo <guohanjun@huawei.com> > --- > mm/memblock.c | 37 +++++++++++++++++++++++++++++++------ > 1 file changed, 31 insertions(+), 6 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index d57ba51bb9cd..95d5916716a0 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -1256,28 +1256,53 @@ int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size, > unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn) > { > 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, next_start_pfn; > phys_addr_t addr = PFN_PHYS(++pfn); > + static int early_region_idx __initdata_memblock = -1; > > + /* fast path, return pfn+1 if next pfn is in the same region */ > + if (early_region_idx != -1) { > + start_pfn = PFN_DOWN(regions[early_region_idx].base); > + end_pfn = PFN_DOWN(regions[early_region_idx].base + > + regions[early_region_idx].size); > + > + if (pfn >= start_pfn && pfn < end_pfn) > + return pfn; > + > + /* try slow path */ > + if (++early_region_idx == type->cnt) > + goto slow_path; > + > + next_start_pfn = PFN_DOWN(regions[early_region_idx].base); > + > + if (pfn >= end_pfn && pfn <= next_start_pfn) > + return next_start_pfn; > + } > + > +slow_path: > + /* 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 */ > + early_region_idx = mid; > return pfn; > } > } while (left < right); > > if (right == type->cnt) > return -1UL; > - else > - return PHYS_PFN(type->regions[right].base); > + > + early_region_idx = right; > + > + return PHYS_PFN(regions[early_region_idx].base); > } > EXPORT_SYMBOL(memblock_next_valid_pfn); > #endif /* CONFIG_HAVE_MEMBLOCK_PFN_VALID */ > -- > 2.19.1 > -- Sincerely yours, Mike.
WARNING: multiple messages have this Message-ID (diff)
From: Mike Rapoport <rppt@linux.ibm.com> To: Hanjun Guo <guohanjun@huawei.com> Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>, Catalin Marinas <catalin.marinas@arm.com>, linux-kernel@vger.kernel.org, linux-mm@kvack.org, Jia He <hejianet@gmail.com>, Andrew Morton <akpm@linux-foundation.org>, Will Deacon <will@kernel.org>, linux-arm-kernel@lists.infradead.org Subject: Re: [PATCH v12 2/2] mm: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn Date: Tue, 23 Jul 2019 11:33:54 +0300 [thread overview] Message-ID: <20190723083353.GC4896@rapoport-lnx> (raw) In-Reply-To: <1563861073-47071-3-git-send-email-guohanjun@huawei.com> On Tue, Jul 23, 2019 at 01:51:13PM +0800, Hanjun Guo wrote: > From: Jia He <hejianet@gmail.com> > > After skipping some invalid pfns in memmap_init_zone(), 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. > > Furthermore, if the pfn is in a gap of two memory region, skip to next > region directly to speedup the binary search. How much speed up do you see with this improvements relatively to simple binary search in memblock_next_valid_pfn()? > Signed-off-by: Jia He <hejianet@gmail.com> > Signed-off-by: Hanjun Guo <guohanjun@huawei.com> > --- > mm/memblock.c | 37 +++++++++++++++++++++++++++++++------ > 1 file changed, 31 insertions(+), 6 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index d57ba51bb9cd..95d5916716a0 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -1256,28 +1256,53 @@ int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size, > unsigned long __init_memblock memblock_next_valid_pfn(unsigned long pfn) > { > 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, next_start_pfn; > phys_addr_t addr = PFN_PHYS(++pfn); > + static int early_region_idx __initdata_memblock = -1; > > + /* fast path, return pfn+1 if next pfn is in the same region */ > + if (early_region_idx != -1) { > + start_pfn = PFN_DOWN(regions[early_region_idx].base); > + end_pfn = PFN_DOWN(regions[early_region_idx].base + > + regions[early_region_idx].size); > + > + if (pfn >= start_pfn && pfn < end_pfn) > + return pfn; > + > + /* try slow path */ > + if (++early_region_idx == type->cnt) > + goto slow_path; > + > + next_start_pfn = PFN_DOWN(regions[early_region_idx].base); > + > + if (pfn >= end_pfn && pfn <= next_start_pfn) > + return next_start_pfn; > + } > + > +slow_path: > + /* 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 */ > + early_region_idx = mid; > return pfn; > } > } while (left < right); > > if (right == type->cnt) > return -1UL; > - else > - return PHYS_PFN(type->regions[right].base); > + > + early_region_idx = right; > + > + return PHYS_PFN(regions[early_region_idx].base); > } > EXPORT_SYMBOL(memblock_next_valid_pfn); > #endif /* CONFIG_HAVE_MEMBLOCK_PFN_VALID */ > -- > 2.19.1 > -- Sincerely yours, Mike. _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
next prev parent reply other threads:[~2019-07-23 8:34 UTC|newest] Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-07-23 5:51 [PATCH v12 0/2] introduce memblock_next_valid_pfn() (again) for arm64 Hanjun Guo 2019-07-23 5:51 ` Hanjun Guo 2019-07-23 5:51 ` [PATCH v12 1/2] mm: page_alloc: " Hanjun Guo 2019-07-23 5:51 ` Hanjun Guo 2019-07-23 8:30 ` Mike Rapoport 2019-07-23 8:30 ` Mike Rapoport 2019-07-24 8:29 ` Hanjun Guo 2019-07-24 8:29 ` Hanjun Guo 2019-08-01 8:06 ` Ard Biesheuvel 2019-08-01 8:06 ` Ard Biesheuvel 2019-08-01 8:06 ` Ard Biesheuvel 2019-07-23 5:51 ` [PATCH v12 2/2] mm: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn Hanjun Guo 2019-07-23 5:51 ` Hanjun Guo 2019-07-23 8:33 ` Mike Rapoport [this message] 2019-07-23 8:33 ` Mike Rapoport 2019-07-24 8:33 ` Hanjun Guo 2019-07-24 8:33 ` Hanjun Guo
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20190723083353.GC4896@rapoport-lnx \ --to=rppt@linux.ibm.com \ --cc=akpm@linux-foundation.org \ --cc=ard.biesheuvel@linaro.org \ --cc=catalin.marinas@arm.com \ --cc=guohanjun@huawei.com \ --cc=hejianet@gmail.com \ --cc=linux-arm-kernel@lists.infradead.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=will@kernel.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.