背景
memblock 是内核启动早期的物理内存管理器，每种用途的地址区间放在按 base 排序的 regions 数组里。往里插一个区间（memblock_add_range()），或把一段区间从现有 region 中切出来（memblock_isolate_range()），都要先找到与目标区间可能相交的 region，而这两个函数一直从 index 0 开始线性扫描整个数组。
KHO（kexec handover）把这个问题放大到不可接受：kexec 切换内核时被保留的内存页，新内核启动时要逐个 folio 注册回 memblock。严重碎片化下保留 folio 有几十万个且互不相连，每个注册都要在已经很大的数组里从头扫一遍。N 次注册各扫 N 项，总量 O(N^2)，393k 页的恢复实测花了约 268s。
每次注册都从头扫
┌─────────────────────────────────────┐
│ KHO 恢复逐个注册几十万个保留 folio │
└──────────────────┬──────────────────┘
▼
┌─────────────────────────────────────┐
│ 每次注册从 index 0 线性扫描 regions │
│ 数组找交叠位置 │
└──────────────────┬──────────────────┘
▼
┌─────────────────────────────────────┐
│ N 次注册各扫一遍数组，总量 O(N^2)， │
│ 启动多花几分钟 │
└─────────────────────────────────────┘
问题
- KHO 恢复时几十万个互不相连的保留 folio 逐个注册进 memblock
- 插入与隔离每次从 index 0 线性扫描 regions 数组找相交位置
- N 次操作各扫 N 项退化成 O(N^2)，启动多花数分钟
方案
regions 数组按 base 排序，排在前面且末尾不超过目标 base 的 region 必然不相交，可以直接跳过。新增的 memblock_bsearch_start() 用这个性质做二分，返回第一个末尾超过 base 的 region 下标；目标 base 落在最后一个 region 之后时直接返回数组末尾，循环一次都不进。
两个函数把遍历宏换成从该下标开始的 for_each_memblock_type_from()，其余合并、拆分逻辑不动。
二分定位起点再扫
┌───────────────────────────────────────┐
│ regions 数组本来就按 base 排序 │
└───────────────────┬───────────────────┘
▼
┌───────────────────────────────────────┐
│ 二分找第一个末尾超过 base 的 region， │
│ 之前的必不相交 │
└───────────────────┬───────────────────┘
▼
┌───────────────────────────────────────┐
│ 从二分结果起线性扫，其余 region 跳过 │
└───────────────────────────────────────┘
顺序追加是 KHO 的典型模式：目标 base 总在末尾，二分走快速路径 O(1) 返回，注册总量从 O(N^2) 降到 O(N)；交织插入的最坏情况也只剩二分本身的 O(N log N)。
收益
393k 个保留页的 KHO 启动恢复实测：
| 指标 | Before | After | 改善 |
|---|---|---|---|
| KHO 内存恢复耗时 | 约 268s | 约 50ms | 超过 5000 倍 |