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

[tarunsahu]

Dongli Zhang <dongli.zhang@xxxxxxxxxx> writes:

> 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!

Glad to know it helped and thanks for testing this.

>
> 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);
We can also combine these two function. IIUC, kho_preserved_batch_start
does not overlap with other reserved regions so, they will be mutually
exclusives ranges and can directly be marked noinit while adding to
reserved list.

~Tarun

> +
> +	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@xxxxxxxxxx>
>> ---
>>  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
>> 
>>