Linux 7.4 memblock optimizer cuts early boot memory scan from 268s to 50ms

A set of memblock improvements targeting the Linux 7.4 kernel replaces linear search with binary search in mm/memblock.c, the early boot-time physical memory allocator that operates before the full page allocator is initialized. Google engineer Tarun Sahu identified that memblock_add_range() and memblock_isolate_range() were scanning candidate regions linearly, causing severe slowdowns under heavy fragmentation. The change reduces worst-case complexity and cuts Kernel Handover memory retrieval time from approximately 268 seconds to approximately 50 milliseconds. This particularly benefits systems using Kernel Handover and the Live Update Orchestrator with many disjoint folios.

What changed in mm/memblock.c

• Algorithmic improvement: The core change replaces linear search with binary search in memblock_add_range() and memblock_isolate_range(), reducing worst-case complexity from O(N²) to O(N log N) and achieving O(N) for sequential appends.
• Specific workload impact: The optimization targets heavy fragmentation scenarios, particularly Kernel Handover (KHO) functionality used by the Live Update Orchestrator, where numerous disjoint folios previously caused pathological linear scan times.
• Measured performance gain: The patch documentation cites KHO memory retrieval time dropping from approximately 268 seconds to approximately 50 milliseconds—a reduction of over three orders of magnitude.
• Scope limitation: The memblock allocator is strictly an early boot-time mechanism that operates prior to full page allocator initialization; this change does not affect runtime memory allocation paths.
• Code location: All changes are confined to mm/memblock.c, the kernel's dedicated early physical memory reservation and isolation subsystem.

Why it matters

This fix eliminates a severe boot-time regression for Linux systems using kernel live patching and update orchestration, making enterprise rolling updates and high-availability deployments significantly more practical. It also demonstrates that long-standing linear algorithms in core kernel infrastructure can still yield dramatic improvements when revisited with modern workloads in mind, encouraging similar audits elsewhere in the memory management layer.