你有没有碰到过这种情况服务器内存明明还剩几个GBfree -h看着也够但某个进程一申请一块比较大的内存内核却直接报page allocation failure: order:4紧接着进程被 OOM Killer 干掉。如果你查过日志大概率会看到Node 0 DMA32 free:...那一串数字然后一头雾水剩余内存不少为什么就分配不出来问题多半出在内存碎片上。而要讲清楚内存碎片以及系统到底怎么处理它就绕不开一个经典设计——伙伴系统Buddy System。这是一套在现代操作系统内存管理里沿用了几十年的算法从 Unix 时代一路走到今天的 Linux依然是物理内存分配的核心支柱。这篇就把伙伴系统的来龙去脉、数据结构和实际运作讲透讲完你再去看buddyinfo就不会觉得那是天书了。1. 内存碎片到底从哪里来困扰每个内存分配器的根本难题1.1 先分清两种碎片内部碎片与外部碎片内存碎片说起来是一个词实际上包含两种完全不同的东西很多人没分清就开始讨论结果方向全偏了。内部碎片指的是系统把一个内存块分配出去了但程序真正用到的部分比这个块小剩余那部分被“锁”在块里谁也拿不走。举个最直白的例子假设内存按 4KB 的页为单位分配程序只用了 1KB那剩下的 3KB 就是内部碎片。内部碎片是“分配粒度”造成的解决思路是缩小分配单位或者让分配器支持更细的粒度。外部碎片指的是系统里有很多分散的空闲小块每个都小但加起来的空闲总量很大却凑不出一个足够大的连续块。就好比你钱包里全是零钱总额有一百块但想付一张五十块的整钞时拿不出来——零钱还是那些零钱但就是凑不成整。伙伴系统要解决的核心矛盾是外部碎片。1.2 为什么外部碎片这么难搞在一个长期运行的系统里内存会被反复分配、释放。如果每次分配和释放的内存块大小不一、地址交错时间一长底层物理内存就会像一块被啃过的奶酪到处是洞。举个例子。假设起始有一块连续 64 页的物理内存系统依次分配了 8 页、16 页、4 页、8 页图形化大概长这样[8页][16页][4页][8页][剩余28页连续]随后16 页和 8 页第一个8页被释放[8页空闲][16页空闲][4页占用][8页空闲][28页空闲]现在你把 8 页空闲和 16 页空闲加一起是 24 页但它们不连续中间隔着一个 4 页的占用块。此时如果有人申请一个 32 页的连续块系统只能拒绝虽然空闲总量仍有 48 页。这就是外部碎片的杀伤力可用总量充足但最大连续块不够。而且这个过程是动态的系统不能提前预知程序什么时候释放哪块内存所以只能靠分配算法来“对冲”这种不确定。1.3 分页机制并没能一劳永逸地解决碎片有人会问虚拟内存不是有分页机制吗进程看到的是连续虚拟地址底层物理页可以分散为什么还需要物理连续的大块分页确实把“进程视角的连续”和“物理的分散”解耦了但内核自己很多场景依然硬性要求物理连续比如DMA 设备直接访问内存时无法经过 MMU 做页表翻译要求物理地址连续内核页表本身需要连续物理页存储各种硬件驱动、固件交互用的内存块常常要求连续启停大页内存HugeTLB时需要物理连续的 2MB 或 1GB 块。所以物理内存分配器必须尽量让空闲块“完整而连续”。在 Linux 之前和早期 Unix 时代有人试过按任意大小做动态分区分配类似用户态malloc的 first-fit、best-fit 思路但问题是分配器需要维护空闲区间的复杂结构分配释放都得查表、切分、合并性能差且碎片同样严重。于是伙伴系统登场了用一套极其简单的规则把外部碎片控制在一个“可接受的范围内”。2. 伙伴系统的核心思想2的幂次拆分与伙伴合并规则2.1 一条最关键的规则伙伴的定义伙伴系统的全部核心可以浓缩成一句话把内存按照 2 的幂次方切成块每个块的大小必须是 2^order 个连续页分配时把一个大块不断对半拆直到刚好满足需求释放时检查相邻的同大小块是否空闲如果空闲就合并然后继续向上检查。这里最关键的概念是“伙伴buddy”。两个块互为伙伴必须满足三个条件大小相等物理地址相邻两个块合并之后仍然是一个大小为 2^(order1) 的合法块。举个例子大小为 4 页的块 A 起始地址是 0大小为 4 页的块 B 起始地址是第 4 页那么 A 和 B 就是伙伴它们合并成 8 页的块起始地址 0。但如果 B 起始地址是第 8 页虽然也相邻A 和 B 合并后是 12 页不是 2 的幂次所以它们不是伙伴关系不能合并。再换一种直观说法任何一个大小为 2^order 的块它的伙伴的起始地址是把该块起始地址的第 order 位翻转之后得到的。所以代码里可以用一个异或操作直接算出来。static inline unsigned long buddy_pfn(unsigned long pfn, unsigned int order) { return pfn ^ (1 order); }pfn是页框号page frame number1 order是当前块大小。这个异或操作就是伙伴系统里最优雅的“暗号”一按开关就能找到失散多年的兄弟。2.2 分配时怎么拆大块一分为二右半块进低阶链表假设系统现在只有一个大小为 8 页的空闲块有人申请 2 页order1分配器会这样做在 order1 的空闲链表里找发现没有空闲块往上找 order2、order3在 order3 找到那个 8 页块把 8 页块拆成两个 4 页块左半块继续拆成两个 2 页块把其中一个 2 页块返回给申请者剩下的 2 页块挂到 order1 链表另一个 4 页块挂到 order2 链表。整个过程可以把所有没分配出去的“半块”放到相应 order 的链表中等待下次使用。也就是说申请大块时拆出来的小块不会浪费都会被规整地收纳到对应的档位。这有点像你去银行换零钱你拿一张 100 元说要换 20 元柜员为了凑出 20 元可能先拆成 5050再拆出 2030但最终多余的 50 和 30 都还会作为现金留在系统里而不是扔掉。2.3 释放时怎么并从下往上递归合并释放过程正好反过来。还拿上面的例子现在释放那个 2 页块释放时需要找到它的伙伴另一个相邻的 2 页块。如果伙伴也是空闲的就把两者从各自链表中摘下来合并成一个 4 页块然后继续看这个 4 页块的伙伴是否空闲如果空闲继续合并成 8 页块一路向上直到无法合并为止。这就是伙伴系统名字的由来每个块都在找自己的“搭档”搭档凑齐了就合并升级。这个合并机制保证了系统空闲内存会不断“聚拢”大块数量尽量被恢复从而抑制外部碎片的恶化。2.4 为什么说它“优雅”简单规则 稳定复杂度如果你头一次接触伙伴系统可能会觉得这也没啥了不起。但它的优雅体现在三个层面第一规则极其简单。整个系统只需要维护若干个空闲链表和一个伙伴计算公式分配和释放各自只有两条核心逻辑拆、合。第二性能稳定。分配和释放的时间复杂度都是 O(log N)N 是系统内存按页数计算的总量。每次分配最多向上翻到 11 层MAX_ORDER 通常是 11对应最大连续块 2^10 1024 页在常见页大小下是 4MB所以无论内存多大查找次数都是个位数级别的常数。第三对碎片是“主动抑制”而不是“事后补救”。系统里任何空闲块都尽量保持完整大块的状态小的碎片只可能出现在分配出去的块里空闲区总能维持较大的连续面。3. 从数据结构到分配算法伙伴系统是怎么“跑”起来的3.1 free_area[order]一维数组一堆空闲链表伙伴系统的核心数据结构是一个数组free_area[MAX_ORDER]数组的下标就是 order。每个free_area[order]内部挂一个链表链上所有节点代表大小为 2^order 个页的空闲块。如果把 order 和块大小对应起来大概是这张表order连续页数内存大小页大小 4KB 时014 KB128 KB2416 KB3832 KB41664 KB532128 KB664256 KB7128512 KB82561 MB95122 MB1010244 MB在这个 table 里越靠上的 order 代表块越小越靠下代表块越大。系统在初始化阶段会把整块物理内存分成若干个大小为 2^10 的“最高档”块挂到最下面或者按实际连续情况挂到不同 order 上。每个内存节点node又分成若干个内存域zone比如 ZONE_DMA、ZONE_DMA32、ZONE_NORMAL每个 zone 都有自己的free_area数组所以你在/proc/buddyinfo里会看到多行一行对应一个 zone。3.2 怎么快速判断伙伴是否空闲PageBuddy 标志与位图伙伴系统效率的关键在于释放时能够“瞬间”判断伙伴是否空闲。如果每次释放都去遍历链表找伙伴那复杂度就没法看了。这里有两个常用方案早期内核用一张位图来记录“一对伙伴块是否有伙伴空闲”每次分配和释放时维护位图状态。现代内核则更直接每个物理页的struct page里有一个PageBuddy标志位如果这个页是空闲块的首页就会置上该标志同时它的_mapcount会被复用为 order 值。所以释放时的伙伴检查逻辑变成static inline int page_is_buddy(struct page *page, unsigned int order) { if (!PageBuddy(page)) // 伙伴页必须也是空闲块 return 0; if (buddy_order(page) ! order) // 伙伴大小必须与自己相等 return 0; return 1; }再加上用异或计算伙伴地址释放一个块时只需要做常数级别的检查不用遍历任何链表。3.3 分配路径拆分拿到一个空闲大块后怎么切当申请 order 的内存量时分配器先从free_area[order]拿一个块。如果没有就往free_area[order1]找再没有继续往上找直到最高的MAX_ORDER-1。找到一块之后用expand函数逐级拆分。下面的 C 伪代码示意了 Linux 中expand的核心逻辑注意我做了大量简化只保留拆分思想static inline void expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area) { unsigned long size 1 high; // 当前大块大小 while (high low) { // 进入下一阶更小的 order area--; high--; size 1; // 大块右半部分挂到下一阶空闲链表 list_add(page[size].lru, area-free_list[MIGRATE_MOVABLE]); // 设置右半部分的 order 值 set_page_order(page size, high); } }其中page是大块的起始页low是要拆到的目标 orderhigh是当前大块的 order。每循环一次就把大块的右半部分“挂账”左半部分继续往下拆直到达到目标 order。拆完之后目标 order 的左半块返回给调用者。3.4 释放路径合并向上合并直到撞到“非空闲”释放时核心函数叫__free_one_page。它的循环逻辑非常干净while (order MAX_ORDER - 1) { // 计算出伙伴的起始页框号 buddy_pfn pfn ^ (1 order); buddy page (buddy_pfn - pfn); // 伙伴不在该 order 的空闲链表上停止合并 if (!page_is_buddy(buddy, order)) break; // 把伙伴从空闲链表中摘掉 list_del(buddy-lru); // 合并后起始 pfn 取左块 pfn ~(1 order); order; } // 最终把合并后的块挂到 free_area[order] list_add(page-lru, zone-free_area[order].free_list[migratetype]); set_page_order(page, order);这段代码巧妙的地方在于伙伴只需要一行异或就算出来合并之后的起始地址直接把当前 order 对应的位清零即可。不需要记录额外信息数据结构本身就已经隐含了合并路径。3.5 一个 5 分钟的模拟从 order3 分配会发生什么我们假设系统里有一块 8 页的连续内存初始化后它作为一个 order3 的空闲块挂在free_area[3]上。现在进程申请 1 页order0rmqueue找free_area[0]空上到free_area[1]空上到free_area[2]空上到free_area[3]找到一个 8 页块。8 页块拆成两个 4 页块右半块order2挂到free_area[2]左 4 页块再拆成两个 2 页块右半块order1挂到free_area[1]左 2 页块再拆成两个 1 页块右半块order0挂到free_area[0]左 1 页返回给进程。此时系统的空闲状态是free_area[0]有 1 块free_area[1]有 1 块free_area[2]有 1 块free_area[3]空了。等到这块内存释放合并过程会逆着拆分的路径一步步把 1 页并成 2 页、2 页并成 4 页、4 页并成 8 页最终恢复为 order3 的大块。这也是为什么伙伴系统能“自动修复”内存你拆出去的块只要全都还回来最终一定能合并回原来的大块中间状态全部被空闲链表有序收纳。4. 一次完整的内存旅程以 Linux 内核为例看伙伴系统的工作细节4.1 从 memblock 到 buddy物理内存初始化Linux 启动初期物理内存管理用的是memblock一个非常简单的分配器专门服务启动阶段的内核镜像、页表等。等到内核内存管理子系统初始化完毕free_page_init()会把 memblock 里没被占用的物理页一个个释放给伙伴系统。每个页释放进伙伴系统的时候都会执行一次完整的“释放页并向上合并”流程。初始阶段内存全连续所以最终伙伴系统里会形成大量的 order104MB 大小的整块直到内存被切完。此时查看/proc/buddyinfo你会看到每个 zone 里最高 order 的块数量比较大低 order 基本是 0。这就是一台刚重启、内存管理干干净净的机器的状态。4.2 一次 malloc 背后到底怎么触达伙伴系统用户态程序调用malloc(3000)glibc 可能直接从内存池里分配不涉及系统调用。如果申请特别大或者内存池不够glibc 会用mmap或者brk向内核申请内存。这时内核才会通过缺页异常page fault触发真正的物理页分配。缺页处理函数最终会调用alloc_pages然后走get_page_from_freelist、rmqueue等核心路径从伙伴系统里取出物理页再建立页表映射。也就是说伙伴系统面对的是内核内部和各种驱动用户态程序说到底是间接消费者。4.3 一个不能忽略的现实问题锁竞争与 per-CPU pageset理论上伙伴系统很完美但真实世界有并发。多个 CPU 同时要分配内存如果每次都去抢同一个 zone 的free_area锁性能就是灾难。Linux 的做法是在每个 CPU 上维护一个小小的“页缓存”pageset里面存放一部分热页。分配内存时优先从本 CPU 的 pageset 拿不用加锁pageset 空了再向伙伴系统批量“进货”。这样兄弟系统在高并发下依然能保持不错的性能但也带来一个有趣的副作用/proc/buddyinfo里看到的 low-order 空闲块数量经常会有波动因为这些块可能暂时被某个 CPU 缓存走了。所以读这个文件时不要只看一两次的数应多采样观察趋势。4.4 教你看懂 /proc/buddyinfo用文件判断碎片程度机器上执行cat /proc/buddyinfo输出类似这样Node 0, zone DMA 1 0 1 0 2 1 1 0 1 1 3 Node 0, zone DMA32 5673 412 109 21 35 17 8 5 4 2 0 Node 0, zone Normal 12830 2670 1285 874 402 155 67 29 11 4 2从左到右分别是 order 0 到 order 10 的空闲块数量。怎么看碎片严不严重核心是看低 order 块多不多、高 order 块有没有。如果一个 zone 里 order 0 有几千块、但 order 9、order 10 是 0说明内存碎片化已经比较严重了如果 order 9、order 10 还有一定数量说明仍然存在大块连续内存安全性高很多。比如上面示例的 Normal zoneorder 9 有 4 块每块 2MB共 8MBorder 10 有 2 块每块 4MB共 8MB。这表示 16MB 连续内存仍然拿得出来很多要求苛刻的驱动都没问题。真正危险的状态是 order 8 以上全空、低 order 却高居不下那才是典型的“空闲但碎片化”。4.5 一个我踩过的坑不要被 free 命令骗了有次线上机器报内存分配失败我上去一看free -hMem 总共 64Gavailable 还有 20 多 G。直觉上不应该失败。后来查/proc/buddyinfo才看到DMA32 和 Normal 的高阶 order 几乎为 0低阶 order 全部爆满剩余内存全是碎片。那次是因为一个业务容器在反复创建和销毁线程产生大量页缓存和内核对象的分配释放把内存搅成了“细沙”。不看 buddyinfo 的话光看free永远找不到真凶。所以排查内存问题的顺序我建议是先 free 看总量再 budddyinfo 看分布最后才决定怎么优化。如果碎片严重但总量不高最简单快捷的方式是重启业务并观察低阶 order 是否会持续堆积如果内存总量充足但碎片严重则可以手动触发 compaction见后面第 6 章。5. 现实世界的伙伴系统迁移类型、页缓存与防碎片策略5.1 为什么 Linux 要给它打补丁引入迁移类型纯朴的伙伴系统有一个致命伤它把所有空闲块都混在一起用完全不关心这些页面未来会怎么被使用。有些页面一旦分配出去物理位置就永远固定了比如内核代码、某些驱动内存有些页面则可以随时迁移比如用户态进程的匿名页、页缓存里的文件页。当不可迁移的页和可迁移的页在物理地址上交错分布时即使可迁移页允许搬走也会因为中间夹着不可迁移页而无法合并出大块。于是 Linux 在伙伴系统之上引入了迁移类型migratetype每个空闲链表不再是一条而是按迁移类型分成多条MIGRATE_UNMOVABLE不可迁移内核映像、驱动内存等MIGRATE_MOVABLE可迁移用户态内存、页缓存等MIGRATE_RECLAIMABLE可回收某些内核缓存MIGRATE_CMA给 CMA 预留的可迁移区域MIGRATE_HIGHATOMIC给紧急原子分配预留。分配页面时系统会按迁移类型去对应的链表里找块如果当前类型的空闲块不足会去其他类型“借”。这个机制把不同生命周期的内存大致分开大大降低了它们互相“染色”导致碎片的风险。5.2 反碎片技术把可移动页赶一大块去有了迁移类型之后内核还提供“内存规整memory compaction”机制。它的核心思路是找到一片碎片较多的区域把其中的MIGRATE_MOVABLE页向区域的一端迁移迁移结束后区域的另一端就腾出了一整块连续物理内存。你可以手动触发全系统规整echo 1 /proc/sys/vm/compact_memory执行之后再去cat /proc/buddyinfo大概率能看到中高阶 order 的空闲块数量明显上升。这块机制是生产环境处理碎片最高效的“手工操作”之一尤其适合那种跑了几十天、内存分布混乱的常驻服务机器。5.3 伙伴系统 vs 内核里被扩展后的多链表结构拿原始设计对比 Linux 里的实际实现差别还是很大的整理成表格更直观维度教科书版伙伴系统Linux 内核实际实现空闲链表每个 order 一条每个 order 按迁移类型分多条块信息位图记录伙伴状态struct page的 PageBuddy 标志 order 字段并发控制一个全局锁zone lock per-CPU pageset跨 NUMA无感知按 node 分组优先本地内存分配失败处理直接失败可触发内存回收、内存规整、OOM 等机制一句话教科书版本是骨架Linux 在骨架上长满了肌肉和血管让它更适应真实世界的复杂场景。5.4 迁移类型不是万能的借来借去也会产生新问题迁移类型机制也有副作用。比如某台机器上不可迁移的内存特别多UNMOVABLE 类型的空闲链表被耗尽了内核就不得不从 MOVABLE 链表“借块”。借完之后MOVABLE 区域里就混入了 UNMOVABLE 的页并且这些页不会自动还回来会永久性降低该区域的迁移能力。内核里有一种机制叫borrow和“fallback”统计如果你去查看/sys/kernel/debug/extfrag/unusable_index就能看到每个 zone 在每档 order 下“不可用指数”有多高。指数越高说明该区域越难凑出对应大小的大块。正常健康的机器unusable_index 应该很低如果某个 order 的指数长期接近 0.5 或更高就需要考虑机器是不是该重启或者迁移业务了。6. 伙伴系统的天花板何时它不够用后续又是怎么补的6.1 天生只处理页粒度小于一页的请求不归它管伙伴系统管理的最小单位是一页也就是 4KB。但内核内部大量对象只有几十字节或几百字节比如task_struct、inode、dentry等。如果都用伙伴系统分配一页浪费率会惨不忍睹。所以内核在伙伴系统之上又实现了一个slab分配器以及后来的slub、slob它从伙伴系统中申请一大块页作为“原料”然后切成大小相等的对象供内核频繁分配小对象。可以这么理解伙伴系统是批发商slab 是零售商。伙伴系统保证批发环节的大块连续slab 负责把批发来的块切成细料卖给内核里的零散买家。两者配合既解决了外部碎片又把内部碎片控制在很小的范围内。6.2 大页内存HugeTLB碎片问题的“放大器”需要特别留意的是大页内存是对伙伴系统碎片最敏感的场景之一。2MB 大页对应 order91GB 大页对应 order20需要 CONFIG_ARCH_HAS_SET_DIRECT_MAP 等支持但伙伴系统本身 MAX_ORDER 通常只有 11有些架构专门做了扩展。如果你的机器运行一段时间后 order9 的连续块数量变成 0那么即使内存总空闲量很大echo 20 /proc/sys/vm/nr_hugepages也无法成功预留大页。这也是为什么很多数据库、虚拟化宿主机都建议启动时预留大页趁内存还干净的时候把大块锁住而不是运行几天后再去向碎片化严重的内存“乞讨”。如果你必须做什么echo 1 /proc/sys/vm/compact_memory之后再试会更有戏但仍不能保证 100% 成功。6.3 面对高位 order 分配失败内核和运维各自能做什么当分配 order 比较大的内存块失败时内核并不会立刻放弃而是会依次尝试慢路径分配唤醒 kswapd 回收可回收页执行 direct reclaim尝试直接回收页缓存执行内存规整compaction迁移可移动页腾出大块如果还不行才会调用 OOM Killer。作为运维/应用侧能做的除了上面说的主动触发 compact还可以通过drop_caches清掉页缓存这在很多碎片场景下立竿见影echo 3 /proc/sys/vm/drop_caches清完缓存后大量页缓存对应的物理页会归还给伙伴系统碎片空间变多大块连续内存的机会也会变大。但是要说明白这只适合页缓存占比高的场景如果碎片主要是不可迁移页造成效果有限。6.4 跳出内核看伙伴系统这套思想到处都是伙伴系统的应用远不止操作系统。很多用户态内存分配库、网络协议栈的内存池、文件系统的块分配器都在借鉴它的思想把资源按 2 的幂次分档管理维护一组空闲链表释放时尝试合并相邻同档空闲块。这种“同类合并、大块优先”的思路本质上是一种优秀的资源管理降碎片的通用模式。比如一些网络设备的包缓冲区采用 ring buffer 和固定档位分池分布式系统里的内存池、线程池也常用最小堆和分桶的方式管理空闲项。只要你有“资源会被反复申请和释放且时间不可控”的场景都可以想想类比伙伴系统的方案给资源分档、记录相邻关系、释放时主动合并。回到开头那个问题。当你再看到page allocation failure: order:4的报错别再对着free -h发呆了。先cat /proc/buddyinfo看看对应 zone 的高阶 order 是不是已经空了再判断能不能用compact_memory或drop_caches把碎片空间挤出来最后才考虑业务调整或者大页预留策略。伙伴系统不是魔法它只是把一个很复杂的问题用一条简单的“伙伴合并规则”约束到了可控范围。弄懂它之后你会觉得内存碎片没那么可怕——至少你能看出它来了也大概知道往哪个方向去治它。