* Re: [PATCH v3 2/2] memblock: use binary search to locate candidate regions
2026-09-26 9:24 ` [PATCH v3 2/2] memblock: use binary search to locate candidate regions Tarun Sahu
@ 2026-09-26 9:31 ` sashiko-bot
2026-09-30 11:33 ` tarunsahu
2026-10-03 7:56 ` Mike Rapoport
2026-10-04 13:47 ` Pratyush Yadav
2 siblings, 1 reply; 7+ messages in thread
From: sashiko-bot @ 2026-09-26 9:31 UTC (permalink / raw)
To: Tarun Sahu, dmatlack, Pasha Tatashin, Andrew Morton, Mike Rapoport
Cc: kexec, linux-mm, Pratyush Yadav, linux-kernel, dev.jain
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] mm: commit message falsely claims O(N log N) worst-case complexity
--
commit ffd047af563941b5aabcd86a52d569f9b40c01ec
Author: Tarun Sahu <tarunsahu@google.com>
memblock: use binary search to locate candidate regions
This commit introduces a binary search helper, memblock_bsearch_start(),
to optimize finding candidate regions in memblock_add_range() and
memblock_isolate_range(), aiming to reduce boot-time overhead during heavy
memory fragmentation.
> Under heavy memory fragmentation (such as KHO page preservation registering
> hundreds of thousands of disjoint folios), scanning from index 0 on every
> insertion and isolation results in O(N^2) complexity, causing boot-time
> memory retrieval to take several minutes (~268s for 393k pages).
>
> Using binary search reduces the worst-case complexity to O(N log N)
> (and O(N) for sequential appends), cutting KHO memory retrieval time
> from ~268s to ~50ms.
[Severity: Medium]
Is the claim of O(N log N) worst-case complexity mathematically accurate here?
While the binary search reduces the time to locate the insertion index to
O(log N), the regions are still stored in a contiguous array. If disjoint
memory regions are inserted in an order that requires inserting into the
middle of the array, the subsequent elements still need to be shifted.
Looking at memblock_insert_region() which is called during insertion:
static void __init_memblock memblock_insert_region(...)
{
...
memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
...
}
Because this memory move operation guarantees the worst-case complexity of a
single insertion remains O(N), wouldn't inserting N disjoint regions in
descending or scattered order still result in an O(N^2) worst-case time
complexity overall?
The described KHO workload sequentially appends regions, which avoids the
shifting overhead and achieves O(N) overall. Could the commit message be
updated to clarify that this patch improves sequential insertion to O(N),
but the worst-case for fragmented insertions remains O(N^2) due to the array
shifting?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20260926092448.4090401-1-tarunsahu@google.com?part=2
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 2/2] memblock: use binary search to locate candidate regions
2026-09-26 9:31 ` sashiko-bot
@ 2026-09-30 11:33 ` tarunsahu
0 siblings, 0 replies; 7+ messages in thread
From: tarunsahu @ 2026-09-30 11:33 UTC (permalink / raw)
To: sashiko-reviews, dmatlack, Pasha Tatashin, Andrew Morton, Mike Rapoport
Cc: kexec, linux-mm, Pratyush Yadav, linux-kernel, dev.jain
sashiko-bot@kernel.org writes:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [Medium] mm: commit message falsely claims O(N log N) worst-case complexity
> --
>
> commit ffd047af563941b5aabcd86a52d569f9b40c01ec
> Author: Tarun Sahu <tarunsahu@google.com>
>
> memblock: use binary search to locate candidate regions
>
> This commit introduces a binary search helper, memblock_bsearch_start(),
> to optimize finding candidate regions in memblock_add_range() and
> memblock_isolate_range(), aiming to reduce boot-time overhead during heavy
> memory fragmentation.
>
>> Under heavy memory fragmentation (such as KHO page preservation registering
>> hundreds of thousands of disjoint folios), scanning from index 0 on every
>> insertion and isolation results in O(N^2) complexity, causing boot-time
>> memory retrieval to take several minutes (~268s for 393k pages).
>>
>> Using binary search reduces the worst-case complexity to O(N log N)
>> (and O(N) for sequential appends), cutting KHO memory retrieval time
>> from ~268s to ~50ms.
>
> [Severity: Medium]
> Is the claim of O(N log N) worst-case complexity mathematically accurate here?
>
> While the binary search reduces the time to locate the insertion index to
> O(log N), the regions are still stored in a contiguous array. If disjoint
> memory regions are inserted in an order that requires inserting into the
> middle of the array, the subsequent elements still need to be shifted.
>
> Looking at memblock_insert_region() which is called during insertion:
>
> static void __init_memblock memblock_insert_region(...)
> {
> ...
> memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
> ...
> }
>
> Because this memory move operation guarantees the worst-case complexity of a
> single insertion remains O(N), wouldn't inserting N disjoint regions in
> descending or scattered order still result in an O(N^2) worst-case time
> complexity overall?
Right. Here is the analysis below
KHO preserved regions is sorted in incremental order. So searching the candidate
is O(1) and insertion cost is O(1). So for N insertion is O(N).
for random regions, worst case (invertedly sorted)
Total Cost:
Sum(log(i) + i, i=0, i=N)
OlogN! + O(N(N+1)/2) ~ O (N^2)
hence, sashiko is right, So how can we improve this: we cannot.
Incoming regions can overlap and there can be already present
regions in memblock_reserved array that might overlap with incoming
regions. So, only possible solution is one-by-by insertion. So here,
finding the location for insertion using binary search is best we can
do with linear arrays.
As KHO is the only user of having large reserved regions which are
sorted, Patch fulfils its purpose. I will update the commit msg to
correctly populate the time complexities.
~Tarun
>
> The described KHO workload sequentially appends regions, which avoids the
> shifting overhead and achieves O(N) overall. Could the commit message be
> updated to clarify that this patch improves sequential insertion to O(N),
> but the worst-case for fragmented insertions remains O(N^2) due to the array
> shifting?
>
> --
> Sashiko AI review · https://sashiko.dev/#/patchset/20260926092448.4090401-1-tarunsahu@google.com?part=2
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v3 2/2] memblock: use binary search to locate candidate regions
2026-09-26 9:24 ` [PATCH v3 2/2] memblock: use binary search to locate candidate regions Tarun Sahu
2026-09-26 9:31 ` sashiko-bot
@ 2026-10-03 7:56 ` Mike Rapoport
2026-10-04 13:47 ` Pratyush Yadav
2 siblings, 0 replies; 7+ messages in thread
From: Mike Rapoport @ 2026-10-03 7:56 UTC (permalink / raw)
To: Tarun Sahu
Cc: Andrew Morton, Pasha Tatashin, dmatlack, kexec, linux-kernel,
dev.jain, Pratyush Yadav, linux-mm
On Sat, Sep 26, 2026 at 09:24:48AM +0000, Tarun Sahu wrote:
> Use binary search (memblock_bsearch_start) in memblock_add_range() and
> memblock_isolate_range() to locate candidate regions instead of linearly
> scanning from index 0.
>
> Under heavy memory fragmentation (such as KHO page preservation registering
> hundreds of thousands of disjoint folios), scanning from index 0 on every
> insertion and isolation results in O(N^2) complexity, causing boot-time
> memory retrieval to take several minutes (~268s for 393k pages).
>
> Using binary search reduces the worst-case complexity to O(N log N)
> (and O(N) for sequential appends), cutting KHO memory retrieval time
> from ~268s to ~50ms.
>
> memblock_search() open codes the same binary search, so reimplement it on
> top of the new helper.
>
> Signed-off-by: Tarun Sahu <tarunsahu@google.com>
>
> mm/memblock.c | 53 +++++++++++++++++++++++++++++++++++----------------
> 1 file changed, 37 insertions(+), 16 deletions(-)
>
> diff --git a/mm/memblock.c b/mm/memblock.c
> index 59dda7d085f3..87c71435c80c 100644
> --- a/mm/memblock.c
> +++ b/mm/memblock.c
> @@ -586,6 +586,33 @@ static void __init_memblock memblock_insert_region(struct memblock_type *type,
> type->total_size += size;
> }
>
> +/**
> + * memblock_bsearch_start - Find the first region index where rend > base
> + * @type: memblock type to search
> + * @base: base physical address of the candidate range
> + *
> + * Returns the first region index that could potentially overlap @base.
> + */
> +static int __init_memblock memblock_bsearch_start(struct memblock_type *type,
> + phys_addr_t base)
I'd call it __memblock_search()
> +{
> + int mid, low = 0;
> + int high = type->cnt;
> +
> + if (type->cnt && base >= type->regions[type->cnt - 1].base +
> + type->regions[type->cnt - 1].size)
> + return type->cnt;
Using local variables would make it more readable IMHO.
> +
> + while (low < high) {
> + mid = (low + high) / 2;
> + if (type->regions[mid].base + type->regions[mid].size <= base)
> + low = mid + 1;
> + else
> + high = mid;
> + }
> + return low;
> +}
> +
> /**
> * memblock_add_range - add new memblock region
> * @type: memblock type to add new region into
> @@ -609,7 +636,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
> bool insert = false;
> phys_addr_t obase = base;
> phys_addr_t end = base + memblock_cap_size(base, &size);
> - int idx, nr_new, start_rgn = -1, end_rgn;
> + int idx, start_idx, nr_new, start_rgn = -1, end_rgn;
>
> if (!size)
> return 0;
> @@ -644,8 +671,9 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
> */
> base = obase;
> nr_new = 0;
> + start_idx = memblock_bsearch_start(type, base);
>
> - for (idx = 0; idx < type->cnt; idx++) {
> + for (idx = start_idx; idx < type->cnt; idx++) {
> struct memblock_region *rgn = &type->regions[idx];
> phys_addr_t rbase = rgn->base;
> phys_addr_t rend = rbase + rgn->size;
> @@ -809,7 +837,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
> int *start_rgn, int *end_rgn)
> {
> phys_addr_t end = base + memblock_cap_size(base, &size);
> - int idx;
> + int idx, start_idx;
>
> *start_rgn = *end_rgn = 0;
>
> @@ -821,7 +849,9 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
> if (memblock_double_array(type, base, size) < 0)
> return -ENOMEM;
>
> - for (idx = 0; idx < type->cnt; idx++) {
> + start_idx = memblock_bsearch_start(type, base);
> +
> + for (idx = start_idx; idx < type->cnt; idx++) {
> struct memblock_region *rgn = &type->regions[idx];
> phys_addr_t rbase = rgn->base;
> phys_addr_t rend = rbase + rgn->size;
> @@ -2062,19 +2092,10 @@ void __init memblock_mem_limit_remove_map(phys_addr_t limit)
>
> static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
> {
> - unsigned int left = 0, right = type->cnt;
> + int idx = memblock_bsearch_start(type, addr);
>
> - do {
> - unsigned int mid = (right + left) / 2;
> -
> - if (addr < type->regions[mid].base)
> - right = mid;
> - else if (addr >= (type->regions[mid].base +
> - type->regions[mid].size))
> - left = mid + 1;
> - else
> - return mid;
> - } while (left < right);
> + if (idx < type->cnt && addr >= type->regions[idx].base)
> + return idx;
> return -1;
> }
>
> base-commit: 1f18d740165163910df64d3063e1ad31648bc5e0
> --
> 2.56.0.rc1.315.gc6ed9934b7-goog
>
--
Sincerely yours,
Mike.
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 2/2] memblock: use binary search to locate candidate regions
2026-09-26 9:24 ` [PATCH v3 2/2] memblock: use binary search to locate candidate regions Tarun Sahu
2026-09-26 9:31 ` sashiko-bot
2026-10-03 7:56 ` Mike Rapoport
@ 2026-10-04 13:47 ` Pratyush Yadav
2 siblings, 0 replies; 7+ messages in thread
From: Pratyush Yadav @ 2026-10-04 13:47 UTC (permalink / raw)
To: Tarun Sahu
Cc: Andrew Morton, Pasha Tatashin, dmatlack, Mike Rapoport, kexec,
linux-kernel, dev.jain, Pratyush Yadav, linux-mm
On Sat, Sep 26 2026, Tarun Sahu wrote:
> Use binary search (memblock_bsearch_start) in memblock_add_range() and
> memblock_isolate_range() to locate candidate regions instead of linearly
> scanning from index 0.
>
> Under heavy memory fragmentation (such as KHO page preservation registering
> hundreds of thousands of disjoint folios), scanning from index 0 on every
> insertion and isolation results in O(N^2) complexity, causing boot-time
> memory retrieval to take several minutes (~268s for 393k pages).
>
> Using binary search reduces the worst-case complexity to O(N log N)
> (and O(N) for sequential appends), cutting KHO memory retrieval time
> from ~268s to ~50ms.
>
> memblock_search() open codes the same binary search, so reimplement it on
> top of the new helper.
>
> Signed-off-by: Tarun Sahu <tarunsahu@google.com>
>
> mm/memblock.c | 53 +++++++++++++++++++++++++++++++++++----------------
> 1 file changed, 37 insertions(+), 16 deletions(-)
>
> diff --git a/mm/memblock.c b/mm/memblock.c
> index 59dda7d085f3..87c71435c80c 100644
> --- a/mm/memblock.c
> +++ b/mm/memblock.c
> @@ -586,6 +586,33 @@ static void __init_memblock memblock_insert_region(struct memblock_type *type,
> type->total_size += size;
> }
>
> +/**
> + * memblock_bsearch_start - Find the first region index where rend > base
> + * @type: memblock type to search
> + * @base: base physical address of the candidate range
> + *
> + * Returns the first region index that could potentially overlap @base.
> + */
> +static int __init_memblock memblock_bsearch_start(struct memblock_type *type,
> + phys_addr_t base)
> +{
> + int mid, low = 0;
> + int high = type->cnt;
> +
> + if (type->cnt && base >= type->regions[type->cnt - 1].base +
> + type->regions[type->cnt - 1].size)
> + return type->cnt;
In some testing I did of this patch some time ago, I recall that this
check didn't have much of a difference on performance. The binary search
is the real optimization.
Do you think this check is worth keeping?
Other than this, I only have a couple minor nitpicks below.
Regardless of these small comments, this patch LGTM so feel free to add
Reviewed-by: Pratyush Yadav <pratyush@kernel.org>
> +
> + while (low < high) {
> + mid = (low + high) / 2;
> + if (type->regions[mid].base + type->regions[mid].size <= base)
> + low = mid + 1;
> + else
> + high = mid;
> + }
> + return low;
> +}
> +
> /**
> * memblock_add_range - add new memblock region
> * @type: memblock type to add new region into
> @@ -609,7 +636,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
> bool insert = false;
> phys_addr_t obase = base;
> phys_addr_t end = base + memblock_cap_size(base, &size);
> - int idx, nr_new, start_rgn = -1, end_rgn;
> + int idx, start_idx, nr_new, start_rgn = -1, end_rgn;
>
> if (!size)
> return 0;
> @@ -644,8 +671,9 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
> */
> base = obase;
> nr_new = 0;
> + start_idx = memblock_bsearch_start(type, base);
>
> - for (idx = 0; idx < type->cnt; idx++) {
> + for (idx = start_idx; idx < type->cnt; idx++) {
Nit: why have start_idx as a separate variable? Why not assign idx to
the result of memblock_bsearch_start() directly?
> struct memblock_region *rgn = &type->regions[idx];
> phys_addr_t rbase = rgn->base;
> phys_addr_t rend = rbase + rgn->size;
> @@ -809,7 +837,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
> int *start_rgn, int *end_rgn)
> {
> phys_addr_t end = base + memblock_cap_size(base, &size);
> - int idx;
> + int idx, start_idx;
>
> *start_rgn = *end_rgn = 0;
>
> @@ -821,7 +849,9 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
> if (memblock_double_array(type, base, size) < 0)
> return -ENOMEM;
>
> - for (idx = 0; idx < type->cnt; idx++) {
> + start_idx = memblock_bsearch_start(type, base);
> +
> + for (idx = start_idx; idx < type->cnt; idx++) {
Same here.
> struct memblock_region *rgn = &type->regions[idx];
> phys_addr_t rbase = rgn->base;
> phys_addr_t rend = rbase + rgn->size;
> @@ -2062,19 +2092,10 @@ void __init memblock_mem_limit_remove_map(phys_addr_t limit)
>
> static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
> {
> - unsigned int left = 0, right = type->cnt;
> + int idx = memblock_bsearch_start(type, addr);
>
> - do {
> - unsigned int mid = (right + left) / 2;
> -
> - if (addr < type->regions[mid].base)
> - right = mid;
> - else if (addr >= (type->regions[mid].base +
> - type->regions[mid].size))
> - left = mid + 1;
> - else
> - return mid;
> - } while (left < right);
> + if (idx < type->cnt && addr >= type->regions[idx].base)
> + return idx;
> return -1;
> }
>
> base-commit: 1f18d740165163910df64d3063e1ad31648bc5e0
--
Regards,
Pratyush Yadav
^ permalink raw reply [flat|nested] 7+ messages in thread