Skip to content
← ENGINEERING NOTES
KERNEL7 min read

Linux 7.4: A Binary Search Cut KHO Boot Work to 50 ms

A memblock patch for Linux 7.4 swaps a linear scan for binary search, cutting KHO memory retrieval from minutes to ~50 ms. See why, and measure it yourself.

BY ASHLIN DARIUS GOVINDASAMY

Somewhere in the Linux 7.4 cycle, a kernel patch turned a retrieval step reported at several minutes into roughly 50 milliseconds, and the fix is an algorithm you met in your first year of programming: binary search. The change targets memblock, the allocator the kernel uses before the real memory manager exists, and it matters for Kexec HandOver (KHO), the machinery that lets a running kernel pass memory to its successor across a kexec reboot. This post explains what memblock and KHO are, why a linear scan went quadratic, and how to reproduce the effect with a 40-line C program.

What KHO and memblock actually are

Kexec HandOver is a mechanism that lets Linux preserve memory regions, which can hold serialized system state, across a kexec. The kernel documentation says it requires CONFIG_KEXEC_HANDOVER, and it landed in Linux 6.16. On top of it sits the Live Update Orchestrator (LUO), which the docs describe as a specialized kexec-based reboot that updates a running kernel to another version while preserving the state of selected resources. LUO arrived in 6.19. The target use case is cloud hosts: swap the hypervisor kernel without tearing down every guest.

Memblock is the other half. Early in boot, before the buddy allocator is up, the kernel tracks physical memory as a sorted array of regions (base, size). Adding or reserving a range means finding where it belongs in that array. If the successor kernel has to re-register hundreds of thousands of preserved pages, that find step runs hundreds of thousands of times.

The patch and its numbers

The patch, posted by Tarun Sahu in September 2026, switches memblock from a linear scan to binary search when locating the candidate region. According to the patch description as relayed by coverage, it uses memblock_bsearch_start in memblock_add_range() and memblock_isolate_range() instead of scanning from the start of the array. The slowdown shows up under heavy fragmentation, such as when KHO page preservation registers hundreds of thousands of disjoint folios.

The headline figure: about 393,000 pages, with retrieval dropping from roughly 268 seconds to roughly 50 milliseconds. Be careful quoting this. Phoronix's headline says ~268s, but its article body reportedly gives about 238 seconds, so the starting number varies by source. Either way it is minutes down to milliseconds. Coverage says the change was submitted for Linux 7.4, but I could not confirm the merge against the mainline tree from here, so check the kernel git log before assuming your kernel has it.

Why linear became quadratic

One linear scan over n regions costs about n steps. Registering n regions in address order means each lookup walks past everything already registered, so the total is about n squared over two. For n = 393,000 that is roughly 77 billion comparisons. Binary search needs about log2(n), around 19 steps per lookup, so the total is under eight million. The ratio is the whole story: the work stops growing with the square of the page count.

QUICK CHECK

Registering 400,000 disjoint regions in ascending order, each with a linear scan of the sorted array, costs roughly how many comparisons?

Reproduce it in user space

This is my own illustration, not kernel code. It keeps a sorted array of regions, registers disjoint ones in ascending order, and compares a linear lookup against a binary one.

c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct { unsigned long base, size; } region;
static region *r;
static size_t n;

static size_t find_linear(unsigned long a) {
    size_t i = 0;
    while (i < n && r[i].base + r[i].size <= a) i++;
    return i;
}

static size_t find_bsearch(unsigned long a) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t m = (lo + hi) / 2;
        if (r[m].base + r[m].size <= a) lo = m + 1; else hi = m;
    }
    return lo;
}

static double run(int bs, size_t count) {
    struct timespec t0, t1;
    n = 0;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (size_t k = 0; k < count; k++) {
        unsigned long a = k * 2 * 4096UL;   /* ascending, one hole between */
        size_t i = bs ? find_bsearch(a) : find_linear(a);
        memmove(&r[i + 1], &r[i], (n - i) * sizeof *r);
        r[i] = (region){ a, 4096 };
        n++;
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

int main(int argc, char **argv) {
    size_t count = argc > 1 ? strtoul(argv[1], 0, 10) : 100000;
    r = malloc((count + 1) * sizeof *r);
    printf("linear   %zu regions: %.3fs\n", count, run(0, count));
    printf("bsearch  %zu regions: %.3fs\n", count, run(1, count));
    return 0;
}
regions.c: linear vs binary lookup in a sorted region array
bash
gcc -O2 -o regions regions.c
./regions 100000
./regions 393000
Build and run

On the sandbox I wrote this in, 100,000 regions took 4.4 seconds linear against 0.003 seconds binary, and 393,000 regions took 68 seconds linear against 0.011 seconds binary. Your numbers will differ with CPU and cache, and the real kernel path does more than my toy, so do not read my figures as the kernel's. What carries over is the shape: quadratic against logarithmic.

Measure it properly

A single wall-clock number from a toy is a hint, not a result. Before you trust a comparison, pin the process to one core, repeat each run several times, and look at where the time goes. The linear version should show nearly all its cycles inside the lookup loop, while the binary version should be dominated by the memmove that shifts later entries. That second observation is the interesting one: once lookups are cheap, the next bottleneck is the insertion cost, which is a different problem with a different fix.

bash
for i in 1 2 3; do taskset -c 2 ./regions 200000; done

# where do the cycles go?
taskset -c 2 perf stat -e cycles,instructions,cache-misses ./regions 100000
taskset -c 2 perf record -g ./regions 100000 && perf report --stdio | head -40
Pin, repeat and profile the user-space demo

Here is the practical lesson for your own services. Anything that registers items one at a time into a sorted collection, such as route tables, ACL rules, allocator free lists or a firewall rule set, deserves a quick look. If the lookup is a scan, it works fine in testing with a hundred entries and falls over in production with a few hundred thousand. The cure is usually small: keep the data sorted and search it with a halving strategy, or use a structure built for it. The kernel patch is a good reminder that the fix does not need to be clever, it needs to be applied where the data grew.

It also explains why this patch is considered low risk. The invariant, that the array is sorted by address and regions do not overlap, already existed because the old code relied on it to stop scanning early. Binary search only exploits what the data structure already guaranteed. The behaviour is the same, the number of comparisons is not, and that is the kind of change reviewers like: easy to reason about, easy to measure, and limited to the lookup step.

Check what your kernel supports

You can see whether your running kernel was built with KHO, and inspect handed-over state if it was. The docs reference a debugfs path holding the previous kernel's state tree in flattened device tree format, and note that these interfaces may change.

bash
uname -r
zcat /proc/config.gz 2>/dev/null | grep -E 'CONFIG_KEXEC_HANDOVER|CONFIG_KEXEC='
# or, on distros that ship the config in /boot:
grep -E 'CONFIG_KEXEC_HANDOVER|CONFIG_KEXEC=' /boot/config-$(uname -r)

# After a handover boot (needs debugfs and root):
sudo ls /sys/kernel/debug/kho/in/ 2>/dev/null
sudo ls -l /sys/kernel/debug/kho/in/fdt 2>/dev/null
Is KHO built in, and is there handed-over state?
›Why not just use a better data structure?

A sorted array with binary search keeps memblock simple and cache friendly, which suits code that runs before the kernel has a general allocator. Insertion still shifts later entries, so very large arrays pay for memmove. A tree would avoid that but needs allocation, which is exactly what is unavailable this early. That tension is why a lookup fix is a small, safe patch rather than a redesign.

Gotchas and takeaways

  • Verify the fix is in your kernel before relying on it: coverage says it was submitted for 7.4, and I could not confirm the merge from the mainline tree.
  • Quote the number carefully. Sources disagree on 238 versus 268 seconds, and both describe a heavily fragmented 393,000-page case.
  • If you are not using KHO or Live Update, expect no change at all.
  • Profile before you optimize: a quadratic loop is invisible at a thousand entries and brutal at hundreds of thousands.
  • Sorted data plus a linear scan is a code smell worth grepping for in your own services too.

SOURCES

  1. Linux's Early Boot-Time Physical Memory Allocator Sees Big Speed-Up: ~268s To ~50ms — Phoronix
  2. Linux 7.4 memblock optimization targets KHO lookup — NeoTeo
  3. [PATCH] memblock: use binary search to locate... — LKML archive
  4. Live Update Orchestrator — The Linux Kernel documentation
  5. kho: make boot time huge page allocation work nicely with KHO — LWN.net

Frequently asked questions

What is Kexec HandOver (KHO)?

KHO lets Linux preserve selected memory regions, which can hold serialized state, across a kexec reboot. It needs CONFIG_KEXEC_HANDOVER and landed in Linux 6.16.

What did the memblock patch change?

It uses binary search instead of a linear scan to locate candidate regions in memblock_add_range() and memblock_isolate_range(). Reported results for about 393,000 preserved pages are roughly 268 seconds down to roughly 50 ms.

Will this speed up my normal boot?

No. Systems that do not use KHO or Live Update will not see a difference, because the slowdown only appears when hundreds of thousands of scattered pages are registered.

Is the fix in Linux 7.4?

Coverage says it was submitted for 7.4. Confirm against the kernel git log for your tree, since I could not verify the merge from mainline.

NEWSLETTER

Get the engineering notes in your inbox.

Kernels, GPUs, networks, AI infrastructure — and the things we broke along the way. No spam, one click to leave.

We store only your email address, to send you new articles. See our privacy policy.

TAGS

linuxkernelkexeckhomemblocklinux-7.4performance

RELATED

ENGINEERING NOTES

Things we built.Things we broke.Things we learned.