外部内存碎片是一个由来已久的 Linux 内核编程难题。随着系统持续运行，物理页面会不断分配给不同任务，时间一长，内存就会逐渐碎片化。最终，在运行时间较长且负载繁忙的系统中，真正连续的物理页面可能所剩无几。由于 Linux 内核具备完善的虚拟内存管理能力，物理内存碎片在大多数场景下通常不是致命问题，因为借助页表机制，即使物理页面分散，映射到虚拟地址空间后依然可以保持连续（除非使用大页）。但对于必须从内核线性映射区申请连续物理内存的场景，问题就会变得十分棘手，例如通过 slab/块分配器分配结构体对象（这是内核态中非常常见且高频的操作），或者为不支持 scatter/gather 模式的 DMA 缓冲区分配内存等。这类需求往往会触发频繁的直接内存回收与内存规整，进而造成系统性能明显波动，甚至出现分配失败的情况（在慢速内存分配路径中，还会根据页面分配标志位执行不同处理）。
如果内核编程不再依赖线性地址空间中的高阶连续物理内存分配，那么内存碎片问题理论上就能从根本上得到缓解。但对于像 Linux kernel 这样庞大而复杂的工程来说，这种大规模改动显然并不现实。因此，从 Linux 2.x 时代一直到现在，内核社区始终在持续探索各种缓解 Linux 内存碎片的方法，其中不乏设计巧妙的 patch。虽然一些已经合入主线的 patch 也曾引发争议，例如内存规整机制就在 LSFMM 2014 大会上被不少开发者批评效率偏低、执行速度较慢，而且还存在一些难以稳定复现的 bug，但社区并没有因此放弃，而是在后续版本中不断打磨和优化这项能力。
在这一领域中，最具代表性、也最坚持推动改进的人物之一就是 Mel Gorman。有两组非常重要的 patch 都出自他之手。第一组在 Linux 2.6.24 版本中合并，这组 patch 在被社区正式接纳前总共迭代了 28 个版本，整个周期以“年”为单位来计算（2005 年 2 月已有其 v19 版本介绍，而正式合入的 v28 则是在 2007 年 10 月）。第二组 patch 则在 Linux 5.0 中合并，在 1 或 2 socket 的机器上，相较于未打 patch 的版本，整体可减少 94% 的内存碎片事件。
本文将重点介绍当前广泛使用的 3.10 版本 Linux 内核中，伙伴分配器为预防内存碎片所做的扩展、内存规整的基本原理、如何查看碎片指数，以及如何量化内存规整带来的延迟开销等内容。
反碎片简史
在进入正文之前，先为大家整理一份 Linux 内核开发历史上围绕高阶内存分配优化与内存碎片治理所做努力的资料汇总。下面列出的每一篇文章都很值得深入阅读，希望这张表能为关注 Linux 内核反碎片机制细节的读者提供检索和学习上的便利。
下面我们正式进入主题。
Linux 伙伴分配器
Linux 使用伙伴算法作为页分配器，这种分配方式以结构清晰、实现高效著称。基于经典伙伴算法，Linux 内核又做了若干关键扩展：
分区的伙伴分配器；
Per-CPU pageset；
按迁移类型进行分组；
我们此前介绍过，Linux 内核使用 node、zone、page 来描述物理内存。分区伙伴分配器的工作对象，实际上是某个 node 下的某个 zone。4.8 版本以前，页面回收策略同样也是基于 zone 设计的，因为早期 Linux 主要面向 32 位处理器，且系统中普遍存在大量高端内存。但这种设计会导致同一 node 内不同 zone 的页面老化速度不一致，从而引出许多复杂问题。社区长期以来为此加入了不少十分 tricky 的 patch 来缓解各种异常情况，但始终没有从根源上彻底解决。随着近些年 64 位处理器和大内存服务器越来越普及，Mel Gorman 将页面回收策略从 zone 级别迁移到 node 级别，从而较好地解决了这一问题。我们在使用 BPF 编写工具观察内存回收行为时，需要特别注意这一变化。
Per-CPU pageset 主要用于优化单页分配，可以有效降低多处理器之间的锁竞争。由于它和内存碎片治理本身关系不大，因此本文不作展开。
按迁移类型分组，才是本文重点讨论的 Linux 内存反碎片机制。
根据迁移类型进行分组
在理解迁移类型之前，我们需要先了解内存地址空间布局。每种处理器架构都会定义自己的地址空间组织方式，例如 x86_64 的相关定义可在 mm.txt 中找到。对于依赖页表访问虚拟地址空间的场景（例如用户空间堆内存申请），通常并不要求底层必须是连续物理内存。原因是什么？我们以 Intel 5-level 页表为例，虚拟地址从低到高通常可划分为：页内偏移、页表索引、页中间目录索引、页上层目录索引、页四级目录索引以及页全局目录索引。物理内存页帧号保存在页表项中，通过页表索引即可定位对应页帧，再将页帧号与页内偏移组合起来，就能得到实际物理地址。假设我们需要把某个页表项对应的物理页面迁移出去，只需分配一个新页面，将旧页面中的数据拷贝到新页面，再把该页表项更新为新的页帧号即可，原来的虚拟地址并不会发生变化，因此这类页面通常是可迁移的。
但线性映射区不同，它满足“虚拟地址 = 物理地址 + 常量”的关系。如果物理地址发生变化，那么虚拟地址也会随之改变，继续访问原有虚拟地址的代码就可能直接出错。因此，这类页面显然不适合随意迁移。也正因为如此，当通过页表访问的可迁移页面与通过线性映射访问的不可迁移页面混合管理时，就非常容易形成外部内存碎片。为了解决这一问题，Linux 内核根据页面的可移动性定义了多种迁移类型，并按照迁移类型对页面进行分组管理，以实现反碎片化和高阶内存分配优化。
内核定义的迁移类型实际上有不少种，但在大多数分析场景中，我们通常只需要重点关注 3 个：MIGRATE_UNMOVABLE、MIGRATE_MOVABLE 和 MIGRATE_RECLAIMABLE。这 3 类才是最核心、最有代表性的迁移类型，其他类型大多服务于特殊用途，本文不再展开。若想查看每种迁移类型在不同 order 上的分布情况，可以直接读取 /proc/pagetypeinfo。
具体页面会从哪一种迁移类型中分配，取决于申请页面时使用的页面分配标志位。例如，面向用户空间的内存需求通常会使用 __GFP_MOVABLE，而文件页往往使用 __GFP_RECLAIMABLE。当某一类迁移类型中的页面耗尽时，内核可以从其他迁移类型中“盗用”物理页。为了尽量减少新的碎片产生，盗用通常会从最大的页块开始进行（页块大小由 pageblock_order 决定，细节这里不展开）。上述 3 种迁移类型的备用优先级从高到低分别为：
MIGRATE_UNMOVABLE: MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE
MIGRATE_RECALIMABlE: MIGRATE_UNMOVABLE, MIGRATE_MOVABLE
MIGRATE_MOVABLE: MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE
内核引入按迁移类型分组的主要目的就是降低外部内存碎片，因此一旦系统中频繁发生“盗用”行为，通常就意味着已经出现了较多外部内存碎片事件，并为后续高阶连续物理内存分配埋下隐患。我在上一篇《我们为什么要禁用 THP》中提到过，可以借助内核提供的 ftrace 事件来分析外部内存碎片事件，具体步骤如下：
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable
cat /sys/kernel/debug/tracing/trace_pipe > ~/extfrag.log执行一段时间后按下 Ctrl-c，然后执行：
echo 0 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable即可停止采集。这个事件中包含了多个分析字段：
如果要统计一段时间内发生外部内存碎片事件的次数，我们只需要重点关注 fallback_order < pageblock order 的事件即可（在 x86_64 环境下，该值通常为 9）。
可以看到，按迁移类型分组本质上只是延缓了 Linux 内存碎片的恶化速度，并不能从根本上彻底消除碎片问题。因此，随着系统运行时间不断增长，当内存碎片累积到一定程度、无法满足连续物理内存分配需求时，仍然会引发性能下降甚至分配失败。也正因为如此，仅依赖这一机制还远远不够，Linux 内核还需要配合其他手段进一步治理和规整内存碎片。
未完待续...
