memblock: use binary search to locate candidate regions

Use binary search 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 candidate search complexity to O(log N)
(from O(N)), cutting KHO memory retrieval time from ~268s to ~50ms.

memblock_search() open codes the same binary search, so reimplement it on
top of the new helper.

Signed-off-by: Tarun Sahu <tarunsahu@google.com>
Reviewed-by: Pratyush Yadav <pratyush@kernel.org>
Link: https://patch.msgid.link/20261008190828.3221718-2-tarunsahu@google.com
Signed-off-by: Mike Rapoport (Microsoft) <rppt@kernel.org>

0 files changed, 0 insertions, 0 deletions