[PATCH] memblock: use binary search to locate candidate regions
tarunsahu at google.com
tarunsahu at google.com
Fri Sep 4 07:51:12 PDT 2026
Dongli Zhang <dongli.zhang at oracle.com> 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 at 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
>>
>>
More information about the kexec
mailing list