region 0
region 1
region 2
memblock 的 regions 数组
每种用途一段区间，插入与隔离都要先找可能相交的 region
region 3
region 4
region 5
base 0
base 1
base 2
base 3
base 4
base 5
base 递增
越靠后的 region，base 越大
目标区间 [base, end)
memblock_add_range()
memblock_isolate_range()
从 index 0 开始线性扫描
region 0
region 1
region 2
region 3
region 4
region 5
逐项比较末尾
i = 0
才找到相交位置
前面的 region 都被白扫
KHO 恢复
保留 folio 互不相连
逐个注册回 memblock
393k 页
保留页待注册
每次注册都从 index 0 扫到相交位置
第 1 次注册
第 2 次注册
第 N 次注册
N 次注册 × 每次扫 N 项
O(N^2)
约 268s
KHO 恢复实测
启动多花几分钟
region 0
region 1
region 2
region 3
region 4
region 5
region 6
region 7
regions 数组：按 base 排序
灰 end ≤ base
绿 end > base
base
[0, 8)
[4, 8)
[4, 5)
mid = 3
mid = 5
end ≤ base → 丢掉左半
end > base → hi = 5
mid = 4 → 第一个候选
memblock_bsearch_start()
返回第一个末尾超过 base 的 region 下标
region 0
region 1
region 2
region 3
region 4
memblock_bsearch_start()
base 在最后一个 region 之后？
返回数组末尾 n
循环一次都不进
base > regions[n-1].end
新 region
O(1)
每次注册只做一次二分
顺序追加：总量 O(N^2) → O(N)
顺序追加是 KHO 的典型模式
region 0
region 1
region 2
region 3
region 4
region 5
交织插入：目标落在数组中间
插入 A
插入 B
插入 C
二分 O(log N)
从二分结果起线性扫 O(N)
O(N log N)
其余合并、拆分逻辑不动
for_each_memblock_type_from()
KHO 内存恢复：393k 个保留页
Before
约 268s
After
约 50ms
超过 5000 倍
memblock_bsearch_start()
两个调用方改用 for_each_memblock_type_from()
空格
播放/暂停
←
→
逐动作
R
重播
⚠
1x