拆分与合并连续物理页
伙伴分配器把空闲物理页组织为不同 order 的连续块,并用空闲链表管理同阶块。
相关概念
工程问题#
内核既需要单页,也需要连续多页;反复分配和释放之后,必须尽量保留可供较大请求使用的连续区域。
实际实现#
分配时可从更高阶空闲块逐级拆分;释放时根据页号定位同阶伙伴,满足条件后合并。实际空闲集合还按 zone 与迁移类型区分。
处理流程#
- 确定所需页数对应的 order
- 搜索可用块并按需拆分
- 归还时检查相邻伙伴
- 逐级合并后挂回空闲链表
源码片段#
固定版本 · 原文摘录mm/page_alloc.cv6.12 · L822–L843
822 if (page_is_guard(buddy))823 clear_page_guard(zone, buddy, order);824 else825 __del_page_from_free_list(buddy, zone, order, buddy_mt);826827 if (unlikely(buddy_mt != migratetype)) {828 /*829 * Match buddy type. This ensures that an830 * expand() down the line puts the sub-blocks831 * on the right freelists.832 */833 set_pageblock_migratetype(buddy, migratetype);834 }835836 combined_pfn = buddy_pfn & pfn;837 page = page + (combined_pfn - pfn);838 pfn = combined_pfn;839 order++;840 }841842done_merging:843 set_buddy_order(page, order);__free_one_page
已确认伙伴可合并后,先将伙伴移出空闲链表(或清除保护页状态),调整迁移类型,再以伙伴与当前页号的共同低端位置更新块首地址并增加 order。前文负责查找伙伴及合并资格检查。
截取释放路径的合并主体;它不包含查找伙伴、zone 锁保护及合并后重新挂入空闲链表的完整流程。
收益与取舍#
工程分析带来的收益
- 伙伴位置可由页号和阶数计算
- 合并可恢复较大的连续块
付出的代价
- 工程分析:二次幂粒度可能浪费块内空间
- 外部碎片仍可能导致高阶分配失败
可比较的选择
按大小分组的可变长空闲块可按请求大小分配以减少二次幂粒度浪费,但邻块合并、空闲块索引和碎片管理更复杂。
版本与适用范围#
对应 Linux 页分配器的伙伴核心;实际路径还包含 per-CPU 页列表、回收、压缩与 NUMA 选择。
参考来源#
源码、官方文档与原始论文01
linux · __free_one_page / expand / __rmqueue_smallest
源码v6.12mm/page_alloc.c · __free_one_page / expand / __rmqueue_smallest
相关实现与比较#
4 个相关案例limit_req 把漏桶计算、红黑树查状态与队列回收组合起来,按配置的 key 管理请求速率。
附源码片段 · 通信与流量
QEMU 的 QEMUTimerList 用有序单链表维护定时器,链表头就是下一到期项。
附源码片段 · 调度与资源分配
缓存块命中后可能需要从队列中间移除,双向链表让这一步保持常数时间。
附源码片段 · 内存管理
Redis List 提供左右两端的插入和弹出;在 quicklist 编码下,用带头尾指针的双向节点链组织紧凑数据块。
附源码片段 · 内存管理