From: Jia He <hejianet@gmail.com> To: Russell King <linux@armlinux.org.uk>, Catalin Marinas <catalin.marinas@arm.com>, Will Deacon <will.deacon@arm.com>, Mark Rutland <mark.rutland@arm.com>, Ard Biesheuvel <ard.biesheuvel@linaro.org>, Andrew Morton <akpm@linux-foundation.org>, Michal Hocko <mhocko@suse.com> Cc: Wei Yang <richard.weiyang@gmail.com>, Kees Cook <keescook@chromium.org>, Laura Abbott <labbott@redhat.com>, Vladimir Murzin <vladimir.murzin@arm.com>, Philip Derrin <philip@cog.systems>, AKASHI Takahiro <takahiro.akashi@linaro.org>, James Morse <james.morse@arm.com>, Steve Capper <steve.capper@arm.com>, Pavel Tatashin <pasha.tatashin@oracle.com>, Gioh Kim <gi-oh.kim@profitbricks.com>, Vlastimil Babka <vbabka@suse.cz>, Mel Gorman <mgorman@suse.de>, Johannes Weiner <hannes@cmpxchg.org>, Kemi Wang <kemi.wang@intel.com>, Petr Tesarik <ptesarik@suse.com>, YASUAKI ISHIMATSU <yasu.isimatu@gmail.com>, Andrey Ryabinin <aryabinin@virtuozzo.com>, Nikolay Borisov <nborisov@suse.com>, Daniel Jordan <daniel.m.jordan@oracle.com>, Daniel Vacek <neelx@redhat.com>, Eugeniu Rosca <erosca@de.adit-jv.com>, linux-arm-kernel@lists.infradead.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, Jia He <hejianet@gmail.com>, Jia He <jia.he@hxt-semitech.com> Subject: [PATCH v8 3/6] arm: arm64: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn() Date: Wed, 11 Apr 2018 00:21:54 -0700 [thread overview] Message-ID: <1523431317-30612-4-git-send-email-hejianet@gmail.com> (raw) In-Reply-To: <1523431317-30612-1-git-send-email-hejianet@gmail.com> 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. Furthermore, if the pfn is in a *gap* of two memory region, skip to next region directly if possible. Signed-off-by: Jia He <jia.he@hxt-semitech.com> --- include/linux/early_pfn.h | 37 +++++++++++++++++++++++++++++-------- 1 file changed, 29 insertions(+), 8 deletions(-) diff --git a/include/linux/early_pfn.h b/include/linux/early_pfn.h index 1b001c7..f9e40c3 100644 --- a/include/linux/early_pfn.h +++ b/include/linux/early_pfn.h @@ -3,31 +3,52 @@ #ifndef __EARLY_PFN_H #define __EARLY_PFN_H #ifdef CONFIG_HAVE_MEMBLOCK_PFN_VALID +static int early_region_idx __init_memblock = -1; ulong __init_memblock memblock_next_valid_pfn(ulong pfn) { struct memblock_type *type = &memblock.memory; - unsigned int right = type->cnt; - unsigned int mid, left = 0; + struct memblock_region *regions = type->regions; + uint right = type->cnt; + uint mid, left = 0; + ulong start_pfn, end_pfn, next_start_pfn; phys_addr_t addr = PFN_PHYS(++pfn); + /* 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; + + early_region_idx++; + next_start_pfn = PFN_DOWN(regions[early_region_idx].base); + + if (pfn >= end_pfn && pfn <= next_start_pfn) + return next_start_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 */ + 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.7.4
WARNING: multiple messages have this Message-ID (diff)
From: hejianet@gmail.com (Jia He) To: linux-arm-kernel@lists.infradead.org Subject: [PATCH v8 3/6] arm: arm64: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn() Date: Wed, 11 Apr 2018 00:21:54 -0700 [thread overview] Message-ID: <1523431317-30612-4-git-send-email-hejianet@gmail.com> (raw) In-Reply-To: <1523431317-30612-1-git-send-email-hejianet@gmail.com> 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. Furthermore, if the pfn is in a *gap* of two memory region, skip to next region directly if possible. Signed-off-by: Jia He <jia.he@hxt-semitech.com> --- include/linux/early_pfn.h | 37 +++++++++++++++++++++++++++++-------- 1 file changed, 29 insertions(+), 8 deletions(-) diff --git a/include/linux/early_pfn.h b/include/linux/early_pfn.h index 1b001c7..f9e40c3 100644 --- a/include/linux/early_pfn.h +++ b/include/linux/early_pfn.h @@ -3,31 +3,52 @@ #ifndef __EARLY_PFN_H #define __EARLY_PFN_H #ifdef CONFIG_HAVE_MEMBLOCK_PFN_VALID +static int early_region_idx __init_memblock = -1; ulong __init_memblock memblock_next_valid_pfn(ulong pfn) { struct memblock_type *type = &memblock.memory; - unsigned int right = type->cnt; - unsigned int mid, left = 0; + struct memblock_region *regions = type->regions; + uint right = type->cnt; + uint mid, left = 0; + ulong start_pfn, end_pfn, next_start_pfn; phys_addr_t addr = PFN_PHYS(++pfn); + /* 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; + + early_region_idx++; + next_start_pfn = PFN_DOWN(regions[early_region_idx].base); + + if (pfn >= end_pfn && pfn <= next_start_pfn) + return next_start_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 */ + 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.7.4
next prev parent reply other threads:[~2018-04-11 7:23 UTC|newest] Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top 2018-04-11 7:21 [PATCH v8 0/6] optimize memblock_next_valid_pfn and early_pfn_valid on arm and arm64 Jia He 2018-04-11 7:21 ` Jia He 2018-04-11 7:21 ` [PATCH v8 1/6] arm: arm64: introduce CONFIG_HAVE_MEMBLOCK_PFN_VALID Jia He 2018-04-11 7:21 ` Jia He 2018-04-11 7:21 ` [PATCH v8 2/6] mm: page_alloc: remain memblock_next_valid_pfn() on arm/arm64 Jia He 2018-04-11 7:21 ` Jia He 2018-04-11 7:21 ` Jia He [this message] 2018-04-11 7:21 ` [PATCH v8 3/6] arm: arm64: page_alloc: reduce unnecessary binary search in memblock_next_valid_pfn() Jia He 2018-04-11 7:21 ` [PATCH v8 4/6] mm/memblock: introduce memblock_search_pfn_regions() Jia He 2018-04-11 7:21 ` Jia He 2018-04-11 7:21 ` [PATCH v8 5/6] arm: arm64: introduce pfn_valid_region() Jia He 2018-04-11 7:21 ` Jia He 2018-04-11 7:21 ` [PATCH v8 6/6] mm: page_alloc: reduce unnecessary binary search in early_pfn_valid() Jia He 2018-04-11 7:21 ` Jia He 2018-05-04 2:45 ` [PATCH v8 0/6] optimize memblock_next_valid_pfn and early_pfn_valid on arm and arm64 Jia He 2018-05-04 2:45 ` Jia He 2018-05-04 16:08 ` Daniel Vacek 2018-05-04 16:08 ` Daniel Vacek 2018-05-04 16:53 ` Pavel Tatashin 2018-05-04 16:53 ` Pavel Tatashin 2018-05-04 18:33 ` Daniel Vacek 2018-05-04 18:33 ` Daniel Vacek 2018-05-07 1:10 ` Jia He 2018-05-07 1:10 ` Jia He
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=1523431317-30612-4-git-send-email-hejianet@gmail.com \ --to=hejianet@gmail.com \ --cc=akpm@linux-foundation.org \ --cc=ard.biesheuvel@linaro.org \ --cc=aryabinin@virtuozzo.com \ --cc=catalin.marinas@arm.com \ --cc=daniel.m.jordan@oracle.com \ --cc=erosca@de.adit-jv.com \ --cc=gi-oh.kim@profitbricks.com \ --cc=hannes@cmpxchg.org \ --cc=james.morse@arm.com \ --cc=jia.he@hxt-semitech.com \ --cc=keescook@chromium.org \ --cc=kemi.wang@intel.com \ --cc=labbott@redhat.com \ --cc=linux-arm-kernel@lists.infradead.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=linux@armlinux.org.uk \ --cc=mark.rutland@arm.com \ --cc=mgorman@suse.de \ --cc=mhocko@suse.com \ --cc=nborisov@suse.com \ --cc=neelx@redhat.com \ --cc=pasha.tatashin@oracle.com \ --cc=philip@cog.systems \ --cc=ptesarik@suse.com \ --cc=richard.weiyang@gmail.com \ --cc=steve.capper@arm.com \ --cc=takahiro.akashi@linaro.org \ --cc=vbabka@suse.cz \ --cc=vladimir.murzin@arm.com \ --cc=will.deacon@arm.com \ --cc=yasu.isimatu@gmail.com \ /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.