Linux 7.4 speeds up the boot-time memory allocator 5,000× with a binary search
On October 24, 2026, a patch from Google engineer Tarun Sahu replaces the linear search in Linux’s boot-time memory allocator with a binary search in mm/memblock.c. KHO memory retrieval drops from 268 seconds to 50 milliseconds, a gain that matters most for reboot-free kernel updates.
October 24, 2026. A patch sent for the Linux 7.4 merge window replaces a linear search with a binary search in mm/memblock.c, the physical memory allocator used at the very start of boot. Measured result: KHO memory retrieval drops from roughly 268 seconds to roughly 50 milliseconds. The author, Tarun Sahu, a Google engineer, spotted that a linear scan had survived for years in a path that is, in fact, central. Michael Larabel of Phoronix sums up the general reaction: it is surprising it lasted this long.
For a system administrator or platform lead, the episode is a lesson: the worst regressions are not in exotic algorithms but in the simple loops nobody looks at anymore — and their bill only shows up on the workloads you do not yet have.
The allocator nobody sees
memblock is the kernel’s first physical memory allocator. It runs before the page allocator — the buddy allocator — is brought up, at a point where the kernel has none of the memory-management structures the rest of the system relies on. It is the code that carves up, isolates, and reserves physical memory regions during the earliest stages of startup.
Its job is thankless and invisible: it executes for only a few moments, on varied hardware, then hands control to the real allocator. As a result, its code is rarely read, and its complexity flaws hide behind runtimes so short that nobody measures them — until fragmentation makes them explode.
The hidden cost of KHO fragmentation
The trigger is KHO, short for Kernel Handover. It is the feature that serializes and restores kernel memory state across a hot update via kexec: instead of rebooting the machine from scratch, you transfer the outgoing kernel’s state into the incoming one. It is used by Meta’s Live Update Orchestrator and its relatives.
When memory is heavily fragmented — thousands of disjoint folios, exactly what KHO produces as it reconstructs state — finding the candidate region inside memblock becomes the bottleneck. The code walked the regions one by one, at O(n) per insertion, and the accumulation turned KHO memory retrieval into an operation lasting several minutes.
One line of code that changes the complexity
Tarun Sahu’s fix is a change of method: in memblock_add_range() and memblock_isolate_range(), the linear scan for a candidate yields to a binary search. The patch comment is terse:
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.
In plain terms: the binary search lowers the worst-case complexity to O(N log N) — and O(N) for sequential appends — and drops KHO memory retrieval from 268 seconds to 50 milliseconds. A 5,000× gain, achieved with no new data structure, no new hardware, and no allocator rewrite: it was just a matter of looking in the right place.
The technical moral is twofold. First, a disguised O(N²) often hides inside an innocent for loop, invisible on small test datasets and catastrophic on real ones. Second, this kind of defect is not fixed by adding power: cutting a boot time by 5,000× would require a machine 5,000 times faster, which no purchase can deliver. The right order of magnitude is bought with complexity, not silicon.
Why it matters for live updates
The 268 seconds figure is not theoretical: it is how long KHO took to reconstruct fragmented memory state, before the allocator handed off to the page allocator. For an operator betting on reboot-free kernel updates — the work Meta is pushing with the Live Update Orchestrator — every second of reconstruction is a second of downtime or failover, on fleets where a full reboot is off the table.
The fix lands in a Linux 7.4 merge window already rich in optimizations of the same kind: the workqueue changes promise “10 to 100 times” speedups on some paths, and hundreds of MM patches were merged. The trend is clear: the kernel keeps hunting hidden complexity in paths more than a decade old, because that is where the most profitable gains sleep.
For an operator, the implication is concrete. If you are testing KHO or an equivalent live-update mechanism, this fix changes your end-to-end measurements: the time you attributed to state transfer may actually be an allocator’s search time, and it disappears with the 7.4 kernel.
Verdict
If you maintain a Linux fleet where reboot is costly or forbidden, watch the Linux 7.4 merge closely and plan KHO trials with this patch: a 5,000× improvement on memory reconstruction can be the difference between a live update that ships and one that is abandoned.
If you run ordinary machines that reboot in seconds, you will never see the gain: memblock runs for only a few moments on a normal boot. Just keep the lesson — the next regression of this kind is probably sleeping in a linear loop in your own stack, not in the kernel. And before throwing hardware at a slow path, first check whether the complexity is even the right order.