Re: [PATCH] memblock: use binary search to locate candidate regions

[Dongli Zhang <dongli.zhang@oracle.com>]

On Thu, Sep 3, 2026 8:59:06AM -0700, 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.

I encountered this issue with my workload. Initially, it was because I forgot to
set THP to "always", As a result, there were many 4K pages even though they were
contiguous.

Indeed, I noticed some delays or hiccups with my workload even with THP set to
"always".

In the past month, I used something like what I attached at the end of my reply
to reduce the number of memblock_reserve() calls. I never realized the poor
performance was caused by memblock_reserve() itself.

[    0.231623] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
--> delay
[   38.587378] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1

With your patch, I ran several rounds of tests with THP set to "never" (4K
pages) and no longer noticed any hiccups or delays with my workload.

[    0.247746] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
[    0.512019] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1


Thanks to this patch, I no longer have to put up with the delays or hiccups in
my workload!

Thank you very much!

Dongli Zhang


diff --git a/kernel/liveupdate/kexec_handover.c b/kernel/liveupdate/kexec_handover.c
index 7c4d86daf86d..03e1f914c800 100644
--- a/kernel/liveupdate/kexec_handover.c
+++ b/kernel/liveupdate/kexec_handover.c
@@ -67,6 +67,8 @@ union kho_page_info {
 static_assert(sizeof(union kho_page_info) == sizeof(((struct page *)0)->private));

 static bool kho_enable __ro_after_init =
IS_ENABLED(CONFIG_KEXEC_HANDOVER_ENABLE_DEFAULT);
+static phys_addr_t kho_preserved_batch_start __initdata;
+static phys_addr_t kho_preserved_batch_end __initdata;

 bool kho_is_enabled(void)
 {
@@ -610,25 +612,58 @@ static struct page *__init
kho_get_preserved_page(phys_addr_t phys,
 	return pfn_to_page(pfn);
 }

+static void __init kho_preserved_memory_batch_flush(void)
+{
+	phys_addr_t size;
+
+	if (kho_preserved_batch_start == kho_preserved_batch_end)
+		return;
+
+	size = kho_preserved_batch_end - kho_preserved_batch_start;
+	memblock_reserve(kho_preserved_batch_start, size);
+	memblock_reserved_mark_noinit(kho_preserved_batch_start, size);
+
+	kho_preserved_batch_start = 0;
+	kho_preserved_batch_end = 0;
+}
+
+static void __init kho_preserved_memory_batch_add(phys_addr_t phys,
+						  unsigned int order)
+{
+	phys_addr_t size = 1ULL << (order + PAGE_SHIFT);
+	phys_addr_t end = phys + size;
+
+	if (kho_preserved_batch_start == kho_preserved_batch_end) {
+		kho_preserved_batch_start = phys;
+		kho_preserved_batch_end = end;
+		return;
+	}
+
+	if (phys == kho_preserved_batch_end) {
+		kho_preserved_batch_end = end;
+		return;
+	}
+
+	kho_preserved_memory_batch_flush();
+	kho_preserved_batch_start = phys;
+	kho_preserved_batch_end = end;
+}
+
 static int __init kho_preserved_memory_reserve(unsigned long key, void *data)
 {
 	union kho_page_info info;
 	struct page *page;
 	unsigned int order;
 	phys_addr_t phys;
-	u64 sz;

 	phys = kho_decode_radix_key(key, &order);

-	sz = 1UL << (order + PAGE_SHIFT);
 	page = kho_get_preserved_page(phys, order);

-	/* Reserve the memory preserved in KHO in memblock */
-	memblock_reserve(phys, sz);
-	memblock_reserved_mark_noinit(phys, sz);
 	info.magic = KHO_PAGE_MAGIC;
 	info.order = order;
 	page->private = info.page_private;
+	kho_preserved_memory_batch_add(phys, order);

 	return 0;
 }
@@ -1687,8 +1722,13 @@ static void __init kho_mem_retrieve(void)
 		.leaf = kho_preserved_memory_reserve,
 	};

-	if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL))
+	kho_preserved_batch_start = 0;
+	kho_preserved_batch_end = 0;
+	if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL)) {
+		kho_preserved_memory_batch_flush();
 		goto err;
+	}
+	kho_preserved_memory_batch_flush();

 	return;

> 
> Signed-off-by: Tarun Sahu <tarunsahu@google.com>
> ---
>  mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
>  1 file changed, 36 insertions(+), 2 deletions(-)
> 
> diff --git a/mm/memblock.c b/mm/memblock.c
> index 9ce86349a29f..88940474b020 100644
> --- a/mm/memblock.c
> +++ b/mm/memblock.c
> @@ -160,6 +160,11 @@ static __refdata struct memblock_type *memblock_memory = &memblock.memory;
>  	     i < memblock_type->cnt;					\
>  	     i++, rgn = &memblock_type->regions[i])
>  
> +#define for_each_memblock_type_from(i, memblock_type, rgn, start)	\
> +	for (i = (start), rgn = &memblock_type->regions[i];		\
> +	     i < memblock_type->cnt;					\
> +	     i++, rgn = &memblock_type->regions[i])
> +
>  #define memblock_dbg(fmt, ...)						\
>  	do {								\
>  		if (memblock_debug)					\
> @@ -591,6 +596,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;
> +
> +	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
> @@ -651,7 +683,8 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>  	base = obase;
>  	nr_new = 0;
>  
> -	for_each_memblock_type(idx, type, rgn) {
> +	for_each_memblock_type_from(idx, type, rgn,
> +				    memblock_bsearch_start(type, base)) {
>  		phys_addr_t rbase = rgn->base;
>  		phys_addr_t rend = rbase + rgn->size;
>  
> @@ -827,7 +860,8 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
>  		if (memblock_double_array(type, base, size) < 0)
>  			return -ENOMEM;
>  
> -	for_each_memblock_type(idx, type, rgn) {
> +	for_each_memblock_type_from(idx, type, rgn,
> +				    memblock_bsearch_start(type, base)) {
>  		phys_addr_t rbase = rgn->base;
>  		phys_addr_t rend = rbase + rgn->size;
>  
> -- 
> 2.55.0.970.g62bdec98f9-goog
> 
>