> 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. > > memblock_search() open codes the same binary search, so reimplement it on > top of the new helper. > > Signed-off-by: Tarun Sahu <[email protected]>
Sashiko has reviewed this patch and found no issues. It looks great! -- Sashiko AI review ยท https://sashiko.dev/#/patchset/[email protected]?part=2
