先看一个内存回收框架图，有不理解的评论区留言，一起讨论第一章：问题本质——“空闲充足但不可分配”的结构性矛盾
1.1 大页失败不是容量问题，而是拓扑约束问题
Linux 内存管理中最容易被误判的问题，是将“分配失败”简单归因于“内存不足”，但在高阶页（high-order allocation）场景下，这一判断在绝大多数情况下是错误的。Linux 的物理页分配器（buddy allocator）从设计上就不是一个“任意组合”的资源池，而是一个严格遵守 2^n 连续块约束的离散空间分配系统。当用户或内核请求 order=9（2MB）的页面时，系统必须在物理地址空间中找到一段对齐且连续的 512 个 page frame，并且该区间不能跨越不同的 pageblock 或 zone 边界，也不能包含任何已经被占用的页。这里的“连续”不仅是地址连续，还隐含了同一迁移类型（migrate type）、同一 NUMA 节点、同一 zone 水位策略允许等多重约束，因此本质上这是一个多维约束下的“拓扑匹配问题”。
这直接导致一个现象：即使系统中存在数 GB 的空闲页，只要这些页在物理空间中呈现为离散分布（例如被长期运行的 slab、page cache、匿名页穿插占用），就无法满足高阶分配。进一步地，从数学上看，buddy allocator 的 free_area 是按 order 分层的离散集合，每一层维护的是“可直接使用的连续块集合”，而不是“可拼接资源集合”，因此不存在类似用户态内存分配器那种“碎片拼接”的能力。换句话说，Linux 内核不会做“scatter-gather”式的物理页组合（除非通过 IOMMU 等硬件抽象），因此碎片的存在直接破坏了可分配空间的连通性（connectivity），而不是容量（capacity）。
1.2 外部碎片的度量：从直觉到内核指标
在内核层面，碎片并不是一个模糊概念，而是可以被量化的结构性指标。Linux 使用所谓的 external fragmentation index 来描述某个 order 的碎片程度，其核心思想是：在所有空闲页中，有多少比例能够组成目标 order 的连续块。其近似表达可以理解为：
fragmentation(order) ≈ 1 - (free_blocks_of_order / total_free_pages_scaled)
更直观的解释是：如果系统中空闲页很多，但高阶 free_area[n] 几乎为 0，那么碎片指数趋近于 1，说明碎片极其严重。从 /proc/buddyinfo 可以直接观察这一结构，例如：
Node 0, zone Normal:order 0: 10000order 9: 0
这意味着所有空闲页都停留在低阶链表中，无法通过 buddy merge 形成高阶块。进一步地，内核在 compaction 决策中还会结合 extfrag_threshold 参数，当某个 order 的碎片指数超过阈值时，才会触发规整（compaction），否则认为“失败是合理的”，直接放弃高阶分配尝试。这说明：碎片不仅影响结果，还影响内核是否“尝试修复问题”。从系统论角度看，这是一种典型的“结构性不可达状态”：资源存在，但在当前拓扑与约束条件下不可达。
第二章：Buddy Allocator 的结构性限制与数学本质
2.1 2^n 分配模型与空间二叉划分
Buddy allocator 的本质可以理解为对物理内存空间进行一种完全二叉划分（binary partitioning）。整个物理地址空间被视为一个 order=N 的大块（例如 1GB 对应 order=18），每次分配请求都会在这棵隐式二叉树中向下查找最小满足条件的节点。如果目标 order 的 free list 为空，则向上寻找更大的块并进行递归拆分（split），直到生成目标大小的块。这个过程在数学上等价于：
将一个区间 [0, 2^N) 递归划分为若干 disjoint 的 2^k 子区间
关键约束在于：这些子区间必须严格对齐（alignment = size），例如一个 order=9 的块必须从 2MB 边界开始。这种对齐约束意味着，即使两个相邻的 order=8 块在地址上连续，如果它们的起始地址不满足 2MB 对齐，也无法被视为一个合法的 order=9 块。因此，buddy 系统不仅要求连续，还要求对齐连续（aligned contiguity），这进一步收紧了可用空间。
2.2 合并（coalescing）失败的根本原因
释放路径中的 coalescing 是减少碎片的唯一被动机制，但它的触发条件极其严格：两个 buddy 必须同时处于 free 状态、order 相同、且地址满足 buddy 关系（通常通过 XOR 运算计算）。现实系统中，这三个条件很难同时满足，因为：
生命周期不一致：相邻块可能属于不同生命周期对象（如一个来自 page cache，一个来自 slab），释放时间不同；
类型隔离：不同 migrate type 的页不会合并（例如 MOVABLE 与 UNMOVABLE）；
fallback 污染：高阶分配失败时会从其他 migrate type 借用，导致同一 pageblock 内混入不同类型页。
从概率角度看，随着系统运行时间增加，满足“可合并”的相邻块概率趋近于 0，因此 free_area 高阶链表逐渐枯竭。这解释了为什么碎片是一个随时间单调恶化的问题（除非主动 compaction）。更进一步，从信息论角度看，buddy 系统在运行过程中不断“丢失结构信息”（即哪些块原本属于同一大块），而 coalescing 是一个信息恢复过程，但在噪声（分配/释放扰动）下几乎不可逆。
第三章：碎片产生机制——生命周期失配与分配器叠加效应
3.1 生命周期错配：碎片的第一性原理
碎片的根本来源可以抽象为一句话：不同生命周期的对象被放置在同一物理邻域中。在 Linux 中，典型的内存使用者包括：
当这些对象在时间维度上呈现不同的分配/释放节奏时，物理空间会逐渐形成“棋盘状”分布。例如，一个长期存在的 slab 页夹在两个短生命周期 page cache 页之间，当 cache 被回收后，中间的 slab 页阻断了合并路径。这种现象可以形式化为：在一维地址空间上，存在一个随机过程，其释放事件分布不均匀，导致连续 free 区间长度的期望值快速下降。
3.2 多分配器叠加：slab、page allocator 与 LRU 的耦合
Linux 并非单一分配器系统，而是一个分层分配体系：buddy 提供页级分配，slab/SLUB 在其上构建对象分配，page cache 使用页但受 LRU 管理。这种分层导致一个关键问题：上层分配器的局部最优行为会破坏底层的全局结构。例如，SLUB 为了减少对象分配延迟，会尽量重用已有 slab 页，即使该页只剩一个对象在使用，也不会释放回 buddy；而 page cache 在 LRU 回收时是按冷热程度而非物理位置选择页，这会导致释放出的页在物理空间上高度离散。
slab 页通常标记为 RECLAIMABLE 或 UNMOVABLE，这意味着在 compaction 过程中，这些页要么难以迁移，要么完全不可迁移，从而成为“锚点”（anchor），阻断 free page 的聚集。多个分配器的叠加效应可以被看作一个“多目标优化问题”：slab 优化分配延迟，LRU 优化缓存命中率，而 buddy 需要优化连续性，这三者之间并不存在全局一致的目标函数，因此碎片成为不可避免的副产物。
第四章：水位线、分配路径与慢路径触发机制
4.1 watermark 与分配决策的状态机
Linux 内存分配的第一道决策机制是 zone watermark，它将每个 zone 的空闲页状态划分为三个区间：high、low、min。分配请求首先在 fast path 中检查当前 free_pages 是否高于 high watermark，如果是，则直接从 free_area 中分配；否则进入 slow path。这一机制本质上是一个基于状态机的负载调节系统：当内存充裕时，尽量避免昂贵操作；当内存紧张时，逐步引入 reclaim、compaction 等手段。
对于高阶分配而言，这一状态机更加复杂，因为即使总空闲页数高于 watermark，也可能因为碎片而失败。因此，内核引入了 __alloc_pages_slowpath()，在其中串联多个子状态：direct reclaim → compaction → retry → fallback → fail。这一流程可以视为一个“逐步放宽约束”的搜索过程：先尝试在当前结构中找到解，如果失败，则通过 reclaim 增加 free pages，再通过 compaction 改变结构，最后如果仍失败，则降低要求（例如 fallback 到低阶页或不同 zone）。
4.2 slowpath 的代价与失败不可避免性
slowpath 的核心问题在于：它试图在运行时修复一个长期积累的结构性问题，而这在复杂系统中通常代价极高且成功率有限。direct reclaim 主要作用是增加 free pages，但对连续性帮助有限；compaction 则直接作用于结构，但其成本包括 page migration（涉及拷贝、TLB flush、cache 失效等），并且受限于不可移动页。当这两者都无法满足需求时，内核只能选择失败或降级（例如 THP fallback）。
从复杂度角度看，compaction 相当于在一个带障碍物的网格中寻找最大连续空区，其时间复杂度与内存规模和碎片程度高度相关，最坏情况下接近 O(n)。因此，内核必须在“分配成功率”和“延迟”之间做权衡，这也是为什么在很多场景下，内核会主动放弃高阶分配，而不是无限重试。
第五章：Compaction——对抗碎片的唯一主动机制
5.1 双指针扫描与页面迁移模型
Compaction 的实现可以抽象为一个经典的“双指针压缩算法”：一个指针（free scanner）从高地址向低地址扫描空闲页，另一个指针（migrate scanner）从低地址向高地址扫描可迁移页，当两者相遇时，将 migrate 页搬迁到 free 页位置，从而在低地址侧形成连续空区。这一过程在实现上涉及多个子系统：page isolation（将页从 LRU 或 slab 中隔离）、migration（复制数据并更新映射）、free list 更新等。
关键在于：并非所有页都可以被迁移。内核通过 PageMovable、引用计数、锁状态等判断一个页是否可迁移，这使得 compaction 实际上是在一个“带约束的可移动子集”上进行操作。可以将其形式化为：在集合 P 中找到一个子集 M（movable pages），通过重新排列 M 来最大化某个区间的连续 free 空间，但集合 U（unmovable pages）构成不可穿越的障碍。
5.2 compaction 失败的必然性
在实际系统中，compaction 很少能够完全消除碎片，其失败通常源于以下几个根本性限制：第一，不可移动页（如内核栈、页表、部分 slab）在空间中形成“永久障碍”；第二，可移动页的迁移成本受限于系统负载和延迟要求，内核不会无限制地执行迁移；第三，migration 本身也可能失败（例如分配不到目标页、锁冲突等）。此外，compaction 过程中还存在所谓的“migration failure feedback”，即如果连续多次迁移失败，内核会降低后续尝试的积极性。
从理论上看，这类似于一个带障碍的 packing 问题，其最优解是 NP-hard 的近似形式，内核只能采用启发式算法，因此无法保证找到全局最优的连续空间布局。这解释了为什么在长期运行系统中，即使频繁触发 compaction，高阶分配成功率仍然会逐渐下降。
第六章：页面迁移与 migrate type 隔离机制
6.1 migrate type 的设计动机与实现
为了降低碎片产生概率，Linux 引入了 migrate type，将 pageblock（通常为 2MB）划分为不同类型：MOVABLE、UNMOVABLE、RECLAIMABLE、CMA 等。其核心思想是将具有相似迁移属性的页集中放置，从而在 compaction 时能够整体移动或回收。每个 pageblock 在初始化时会被标记为某种类型，buddy 分配器在分配时优先从匹配类型的 free list 中获取页。
这一机制本质上是一种“类型分区（type partitioning）”策略，类似于内存分配中的 segregation 技术。理论上，如果所有 MOVABLE 页都集中在若干 pageblock 中，那么这些 block 可以通过 compaction 被完全腾空，从而形成大块连续空间。然而，这一理想状态在实际中很难维持，因为系统行为是动态的。
6.2 fallback 机制对隔离的破坏
当某个 migrate type 的 free list 不足时，内核会触发 fallback，从其他类型中“借用”页。例如，当 MOVABLE 不足时，可能从 UNMOVABLE 类型中分配页。这一机制提高了分配成功率，但其副作用是：破坏了类型隔离。一旦一个 pageblock 中混入多种类型的页，其整体迁移能力将下降，因为其中的 UNMOVABLE 页会阻止整个 block 被释放。
从长期来看，fallback 会导致系统逐渐趋向于“完全混合”的状态，即每个 pageblock 中都包含不同类型的页，从而使 compaction 几乎失效。这可以被看作一个熵增过程：初始时系统是有序的（类型分区），随着 fallback 和分配扰动，系统逐渐无序化（类型混合），而内核缺乏足够强的机制来逆转这一过程。
第七章：THP 失败路径与延迟权衡机制
7.1 THP 分配策略的三阶段模型
Transparent Huge Page（THP）是高阶分配的典型应用，其默认使用 order=9（2MB）。THP 的分配路径可以分为三个阶段：首先尝试直接分配（fast path），如果失败则进入 compaction（同步或异步），如果仍失败则回退到 base page（4KB）。这一流程体现了一个典型的“机会主义优化策略”：优先利用已有连续空间，其次尝试重构空间，最后放弃优化。
关键在于，THP 的目标不仅是成功分配，还要控制延迟。如果每次 page fault 都触发重度 compaction，会导致严重的 latency spike，因此内核引入了 defer、kcompactd 等机制，将 compaction 部分转移到后台执行。这使得 THP 成为一个“弱保证”机制：尽量提供大页，但不保证成功。
7.2 失败统计与系统行为反馈
内核通过 /proc/vmstat 中的 thp_fault_fallback、thp_collapse_alloc_failed 等指标来记录 THP 失败情况，这些指标不仅用于观测，也参与内核策略调整。例如，当失败率过高时，内核可能减少主动 compaction 的频率。THP 的失败本质上反映了系统当前的碎片状态，是一个“结构健康度”的信号。
从性能角度看，THP 失败并不只是“少用了一点内存”，而是会带来 TLB miss 增加、page table 开销上升等连锁反应。因此，在高性能场景（如数据库、虚拟化）中，THP 失败往往意味着需要重新设计内存策略（例如使用 HugeTLB 预分配），而不是简单依赖内核自动优化。
第八章：NUMA 架构下的碎片放大效应
8.1 局部性优先与资源隔离的冲突
在 NUMA 系统中，内存被划分为多个 node，每个 node 拥有独立的 buddy allocator 和 free_area。内核默认优先在本地 node 分配内存，以保证访问延迟最低。然而，这一策略在碎片场景下会放大问题：某个 node 可能已经严重碎片化，而其他 node 仍然有大块连续空间，但由于局部性优先策略，请求不会跨 node 分配，从而导致失败。
这可以被视为一个典型的“局部最优 vs 全局最优”冲突：局部最优策略（低延迟访问）在资源不均衡时会导致全局失败。内核提供了诸如 zone_reclaim_mode、numactl 等工具来调整这一行为，但默认策略仍然偏向局部性。
8.2 跨节点 fallback 与碎片传播
当本地 node 无法满足请求时，内核可能进行 node fallback，从其他 node 分配内存。这虽然提高了成功率，但会引入两个问题：一是访问延迟增加（remote access），二是将碎片问题“传播”到其他 node，因为 fallback 同样可能破坏目标 node 的 migrate type 隔离。随着时间推移，多个 node 之间的碎片状态会趋于一致，即整体恶化。
从系统动力学角度看，NUMA 下的碎片演化是一个耦合系统，各 node 之间通过 fallback 和负载迁移相互影响，最终可能达到一个“全局高碎片”的稳态。这也是为什么在大规模 NUMA 系统中，提前预留大页（HugeTLB）往往是唯一可靠的方案。
第九章：诊断与优化——从观测到控制的工程体系
9.1 多维观测：从 free list 到迁移统计
要理解和控制碎片，必须建立多维观测体系。首先，通过 /proc/buddyinfo 可以观察各 order 的 free block 分布，这是最直接的结构视图；其次，/proc/pagetypeinfo 提供 migrate type 维度的信息，可以判断类型隔离是否被破坏；再次，/proc/vmstat 中的 compaction 和 THP 指标可以反映系统动态行为。此外，还可以通过 tracepoints（如 mm_compaction_begin/end）进行细粒度分析。
关键在于，不要只看“free memory”，而要关注“free memory 的结构”。一个系统是否健康，取决于其高阶 free block 是否充足，以及 compaction 成功率是否稳定。
9.2 优化策略：从被动修复到主动设计
工程上，解决碎片问题的策略可以分为三类：第一类是“规避”，即避免在运行时依赖高阶分配，例如使用 HugeTLB 在启动时预留连续内存；第二类是“隔离”，通过控制内存生命周期和 migrate type，减少不同类型页的混合，例如将长生命周期对象集中分配；第三类是“调度”，通过调整 THP、compaction、NUMA 策略，在性能和成功率之间取得平衡。
本质上，这些策略的目标都是一致的：在时间维度上保持空间结构的可控性。因为碎片问题不是瞬时产生的，而是长期演化的结果，因此必须从系统设计层面介入，而不是依赖内核在运行时“修复一切”。
Linux 大页分配失败的根本原因，不是内存不足，而是物理空间结构在长期动态演化后失去连续性与可重构性。buddy allocator 提供的是一个高效但刚性的分配模型，compaction 提供的是一个代价高昂且不完备的修复机制，而 slab、page cache、NUMA 等子系统在各自优化目标驱动下不断引入结构扰动。
最终结果是：系统在容量上富余，但在拓扑上破碎。
真正的解决思路不在于“如何在失败后修复”，而在于如何在系统设计阶段避免进入不可恢复的碎片状态。这也是所有高性能内存系统（数据库、虚拟化平台、DPDK 应用）共同遵循的原则：提前分配、隔离生命周期、减少动态结构扰动。
