内存管理-75-lru_gen-2-文档翻译
基于 Linux-6.1.115
一、multigen_lru.rst
注: 翻译自 Documentation/mm/multigen_lru.rst
Multi-Gen LRU(多代 LRU)
多代 LRU 是一种替代性的 LRU 实现，它优化了页面回收并改善了内存压力下的性能。页面回收决定了内核的缓存策略和内存过量使用(overcommit)的能力。它直接影响 kswapd 的 CPU 使用率和 RAM 利用效率。
1. 设计概述
1.1 目标
设计目标如下：
良好地表示访问时近性(access recency);
尽量利用空间局部性(spatial locality);
为显而易见的选择提供快速路径;
简单的自校正启发式算法;
访问时近性的表示是所有 LRU 实现的核心。在多代 LRU 中，每一代代表一组具有相似访问时近性的页面。代建立了一个(基于时间的)公共参考框架，因此有助于做出更好的决策，例如：在同一台计算机上的不同 memcg 之间，或在数据中心中的不同计算机之间(用于任务调度)做出取舍。
利用空间局部性可以提高收集 accessed 位时的效率。rmap 遍历针对的是单个页面，不会尝试利用发现年轻 PTE 的机会。页表遍历可以扫描一个地址空间中所有的年轻 PTE，但地址空间可能太稀疏以至于没有收益。关键是优化这两种方法并将它们组合使用。
快速路径减少了代码复杂度和运行时开销。未映射的页面不需要 TLB 刷新；干净的页面不需要写回。这些事实只有在其他条件(例如访问时近性)相似时才有帮助。有了代作为公共参考框架，额外的因素就会凸显出来。但显而易见的选择不一定是好的选择，因此自校正是必要的。
简单的自校正启发式算法的好处是不言而喻的。同样，有了代作为公共参考框架，这变得可以实现。具体来说，同一代中的页面可以根据额外因素进行分类，而反馈循环可以统计地比较这些类别之间的 refault 百分比，并推断出哪些类别是更好的选择。
1.2 假设
热页的保护和冷页的选择基于页面访问通道和访问模式。有两种访问通道：
通过页表的访问;
通过文件描述符的访问;
前一种通道的保护在设计上更强，原因如下：
(1) 由于 accessed 位的近似性，判断前一种通道的访问模式具有更高的不确定性。
(2) 淘汰前一种通道的代价更高，因为需要 TLB 刷新且更可能遇到 dirty 位。
(3) 对前一种通道保护不足的惩罚更高，因为应用程序通常不像准备阻塞式 I/O 那样为 major page fault 做准备。例如：GUI 应用程序通常使用专用的 I/O 线程来避免阻塞渲染线程。
还有两种访问模式：
表现出时间局部性的访问;
不表现出时间局部性的访问;
出于上述原因，前一种通道(页表访问)被假定遵循前一种模式(时间局部性)，除非存在 VM_SEQ_READ 或 VM_RAND_READ；后一种通道(文件描述符访问)被假定遵循后一种模式(无时间局部性)，除非观察到异常的 refault。
2. 工作流概述
对于每个 lruvec，可回收页被划分为多个代。最年轻代的序号存储在 lrugen->max_seq 中，匿名页和文件页共用此序号，因为它们在老化时被同等对待。最老代的序号分别存储在 lrugen->min_seq[] 中，匿名页和文件页各一个，因为干净的文件页可以在不受 swap 约束的情况下被淘汰。这三个变量单调递增。
代序号被截断为 order_base_2(MAX_NR_GENS+1) 位以适配 folio->flags 中的 gen 计数器。每个截断后的代序号是 lrugen->folios[] 的索引。使用滑动窗口####技术来追踪至少 MIN_NR_GENS (2) 个、至多 MAX_NR_GENS (4)个代。当页面在 lrugen->folios[] 之一上时，gen 计数器存储 [1, MAX_NR_GENS] 范围内的值；否则存储零。
每一代被划分为多个层(tiers)。通过文件描述符被访问 N 次的页面位于第 order_base_2(N) 层####。与代不同，层没有专用的 lrugen->folios[]。与跨代移动需要持有 LRU lock 不同，跨层移动只涉及对 folio->flags 的原子操作，因此代价可以忽略不计。一个仿照 PID 控制器建模的反馈循环监控匿名和文件类型所有层的 refault，并决定淘汰或保护哪些类型的哪些层。
有两个概念上独立的过程：老化和淘汰。它们构成一个闭环系统，即页面回收。
2.1 老化(Aging)
老化产生年轻的代。给定一个 lruvec，当 max_seq - min_seq + 1 接近 MIN_NR_GENS (2)时，它递增 max_seq。老化通过页表发现被访问的热页时，将其提升到最年轻的代；冷页的降级则在递增 max_seq 时作为后果自然发生####。老化使用页表遍历和 rmap 遍历来寻找年轻的 PTE。对于前者，它遍历 lruvec_memcg()->mm_list，对此链表上的每个 mm_struct 调用 walk_page_range() 来扫描 PTE，每次迭代结束后递增 max_seq。对于后者，当淘汰过程遍历 rmap 时发现了一个年轻的 PTE，老化会扫描其相邻的 PTE。对于这两种方式，在发现年轻 PTE 时，老化清除 accessed 位并将该 PTE 映射的页面的 gen 计数器更新为 (max_seq%MAX_NR_GENS)+1。
2.2 淘汰(Eviction)
淘汰消耗老的代。给定一个 lruvec，当由 min_seq%MAX_NR_GENS 索引的 lrugen->folios[] 变为空时，它递增 min_seq。为了选择要淘汰的类型和层，它首先比较 min_seq[] 来选择更老的类型。如果两种类型同样老，则选择第一层 refault 百分比更低的那个。第一层包含一次性使用的未映射干净页，这是最佳选择。如果老化发现某页通过页表被访问并更新了其 gen 计数器，淘汰会根据该 gen 计数器对页面进行排序。如果某页通过文件描述符被多次访问，且反馈循环从该页所在的层检测到异常的 refault，淘汰还会将此页移动到下一代(即 min_seq+1)。为此，反馈循环使用第一层作为基线，原因如前所述。
2.3 工作集保护(Working Set Protection)
每一代在创建时被打上时间戳。如果设置了 lru_gen_min_ttl，当一个 lruvec 的最老代是在 lru_gen_min_ttl 毫秒内创建的，则该 lruvec 将被保护不受淘汰。换句话说，它防止 lru_gen_min_ttl 毫秒内的工作集被淘汰。如果此工作集无法保留在内存中，则触发 OOM killer。
这种基于时间的方法具有以下优势：
(1) 配置更容易，因为它与具体应用和内存大小无关。
(2) 更可靠，因为它直接连接到 OOM killer。
2.4 Rmap/PT 遍历反馈
为 LRU 链表上的每个页面搜索 rmap 以找到映射它的 PTE(测试和清除 accessed 位)可能很昂贵，因为来自不同 VMA(物理地址空间)的页面对 rmap(虚拟地址空间)来说不是 cache 友好的。对于主要使用映射页面的工作负载，搜索 rmap 可能在回收路径中产生最高的 CPU 开销。
lru_gen_look_around() 利用空间局部性来减少 rmap 访问次数。它扫描年轻 PTE 的相邻 PTE 并提升热页。如果扫描以 cache line 高效的方式完成，它会将指向该 PTE 表的 PMD 条目添加到 Bloom filter 中。这在淘汰和老化之间形成了反馈循环。
2.5 Bloom Filter
Bloom filter 是一种在空间和内存上高效的数据结构，用于集合成员资格测试 —— 即测试一个元素是否不在集合中或可能在集合中。
在淘汰路径中，具体是在 lru_gen_look_around() 中，如果一个 PMD 具有足够数量的热页，其地址将被放入 filter。在老化路径中，集合成员资格意味着该 PTE 范围将被扫描以寻找年轻页面。
注意 Bloom filter 对集合成员资格是概率性的。如果测试产生假阳性，代价是额外扫描一个 PTE 范围 —— 这可能无论如何都会产生热页。filter 本身的参数可以在极限情况下控制假阳性率。
2.6 Memcg LRU
Memcg LRU 是一个 per-node 的 memcg LRU。它也是"LRUs 的 LRU"，因为每个节点和 memcg 的组合都有一个 folio 的 LRU(参见 mem_cgroup_lruvec())。其目标是提高全局回收的可扩展性，这对数据中心中系统范围的内存过量使用至关重要。注意 memcg LRU 仅适用于全局回收。
memcg LRU 的基本结构可以通过与 active/inactive LRU(folio 层面的)的类比来理解：
(1) 它有年轻代和老代(generations)，即 active 和 inactive 的对应物；
(2) max_seq 的递增触发提升，即 activation 的对应操作；
(3) 其他事件触发类似操作，例如：offine 一个 memcg 触发降级，即 deactivation 的对应操作。
在全局回收方面，它有两个显著特性：
(1) 分片(Sharding)，允许每个线程从一个随机的 memcg(在老代中)开始，提高了并行度；
(2) 最终公平性(Eventual fairness)，允许直接回收随时退出并减少延迟，而不影响一段时间内的公平性。
在全局回收期间遍历 memcg 时，它将最佳情况复杂度从 O(n) 提升到 O(1)，且不影响最坏情况复杂度 O(n)。因此，平均而言，它具有亚线性复杂度。
2.7 总结
多代 LRU(folio 层面)可以分解为以下部分：
(1) 代(Generations)
(2) Rmap 遍历
(3) 页表遍历
(4) Bloom filter
(5) PID 控制器
老化和淘汰形成生产者-消费者模型；具体地，后者通过代的滑动窗口驱动前者####。在老化内部，rmap 遍历通过将热的、页面密集的页表插入 Bloom filter 来驱动页表遍历。在淘汰内部，PID 控制器使用 refault 作为反馈来选择要淘汰的类型和要保护的层。
核心架构图(对应总结)：
┌──────────────────────────────────────────────────────────┐ │ 闭环页面回收系统 │ │ │ │ ┌───────────────────┐ ┌───────────────────┐ │ │ │ 老化(Aging) │<─────── │ 淘汰(Eviction) │ │ │ │ [生产者] │ 滑动窗口 │ [消费者] │ │ │ │ │ 驱动 │ │ │ │ │ ┌──────────────┐ │ │ ┌──────────────┐ │ │ │ │ │ 页表遍历 │ │ Bloom │ │ PID 控制器 │ │ │ │ │ │ (walk_pte) │ │<─filter─┤ │ (refault反馈)│ │ │ │ │ └──────────────┘ │ │ └──────────────┘ │ │ │ │ ↑ │ │ │ │ │ │ │ ┌─────┴────────┐ │ │ 选择类型/层淘汰 │ │ │ │ │ Rmap 遍历 │ │ │ │ │ │ │ │ (look_around)│ │ │ │ │ │ │ └──────────────┘ │ │ │ │ │ └───────────────────┘ └───────────────────┘ │ │ │ │ 代(Generations): 公共时间参考框架 │ │ [Gen min_seq(最老)] ← ... → [Gen max_seq(最年轻)] │ └──────────────────────────────────────────────────────────┘
二、multigen_lru.rst
注: 翻译自 Documentation/admin-guide/mm/multigen_lru.rst
Multi-Gen LRU(多代 LRU)
多代 LRU 是一种替代性的 LRU 实现，它优化了页面回收并改善了内存压力下的性能。页面回收决定了内核的缓存策略和内存过量使用(overcommit)的能力。它直接影响 kswapd 的 CPU 使用率和 RAM 利用效率。
1. 快速开始
使用以下配置构建内核：
CONFIG_LRU_GEN=y
CONFIG_LRU_GEN_ENABLED=y
2. 运行时选项
/sys/kernel/mm/lru_gen/ 包含以下子节描述的稳定 ABI 接口。
/sys/kernel/mm/lru_gen # ls -l -rw-r--r-- 1 root root 4096 2010-01-01 08:00 enabled -rw-r--r-- 1 root root 4096 2010-01-01 19:27 min_ttl_ms
2.1 终止开关
enabled 文件节点，接受不同的值来启用或禁用以下组件。其默认值取决于 CONFIG_LRU_GEN_ENABLED。除非某些组件出现意外的副作用，否则所有组件都应启用。当硬件不支持某个组件时，写入 enabled 不会生效，但即使主开关关闭，合法的值也会被接受。
0x0001: 多代 LRU 的主开关。
0x0002: 批量清除叶子页表项(PTE)中的 accessed 位(当 MMU 设置了该位时，例如在 x86 上)。该行为理论上可能加剧锁竞争(mmap_lock)。如果禁用，多代 LRU 在连续映射热页的工作负载上会有轻微的性能下降 —— 这些页面的 accessed 位本可通过更少的大批量操作来清除。
0x0004: 同时清除非叶子页表项中的 accessed 位(当 MMU 设置了该位时，例如在 x86 上)。该行为尚未在 Intel 和 AMD 之外的 x86 变体上验证。如果禁用，多代 LRU 将有可忽略的性能下降。
[yYnN]: 同时应用于上述所有组件。
示例:
echo y >/sys/kernel/mm/lru_gen/enabled cat /sys/kernel/mm/lru_gen/enabled 0x0007 echo 5 >/sys/kernel/mm/lru_gen/enabled cat /sys/kernel/mm/lru_gen/enabled 0x0005
2.2 抖动预防(Thrashing Prevention)
个人电脑对抖动(thrashing)更敏感，因为它会导致卡顿(渲染 UI 时的延迟)并对用户体验产生负面影响。多代 LRU 为大多数没有运行 oomd 的笔记本电脑和台式机用户提供了抖动预防功能。
用户可以向 min_ttl_ms 写入 N，以防止 N 毫秒内的工作集被淘汰。如果此工作集无法保留在内存中，则触发 OOM killer。换句话说，此选项充当一个可调节的减压阀 —— 当打开时，它会终止那些(希望是)不再被使用的应用程序。
基于人类可察觉延迟的平均值(约 100ms)，N=1000 (看起来单位是 0.1ms)通常可以消除因抖动导致的不可容忍的卡顿。更大的值如 N=3000 可以使卡顿不那么明显，但有过早触发 OOM kill 的风险。
默认值 0 表示禁用。
2.3 实验性功能
(1) /sys/kernel/debug/lru_gen ####接受以下子节描述的命令。支持多行命令，也支持使用分隔符 , 和 ; 进行拼接。
(2) /sys/kernel/debug/lru_gen_full 提供用于调试的额外统计信息。CONFIG_LRU_GEN_STATS=y 会在此文件中保留已淘汰代的历史统计数据。
2.4 工作集估算(Working Set Estimation)
工作集估算测量一个应用程序在给定时间间隔内需要多少内存，通常对应用程序性能的影响很小。例如：数据中心希望优化任务调度(装箱问题)以提高内存利用率。当一个新任务进来时，任务调度器需要在选择候选服务器之前，找出它管理的每台服务器是否能为此新任务分配一定量的内存。为此，任务调度器需要估算现有任务的工作集。
读取 lru_gen 时，它会返回每个 memcg 和节点在不同时间间隔内被访问的页面数量的直方图。MAX_NR_GENS 决定每个直方图的桶数。直方图是非累积的。
memcg memcg_id memcg_pathnode node_idmin_gen_nr age_in_ms nr_anon_pages nr_file_pages...max_gen_nr age_in_ms nr_anon_pages nr_file_pages
每个桶包含在 age_in_ms 时间内被访问过的估算页面数。例如：min_gen_nr 包含最冷的页面，max_gen_nr 包含最热的页面，因为前者的 age_in_ms 最大，后者的 age_in_ms 最小。
用户可以向 lru_gen 写入以下命令来创建一个新代 max_gen_nr+1：
+ memcg_id node_id max_gen_nr [can_swap [force_scan]]
can_swap 默认继承系统 swap 设置 —— 如果设置为 1，在 swap 关闭时也强制扫描匿名页，反之亦然。force_scan 默认为 1 —— 如果设置为 0，将采用启发式方法减少开销，但这也可能降低覆盖率。
典型用例是：任务调度器以固定时间间隔运行此命令来创建新代，然后根据由该时间间隔定义的冷页大小对其管理的服务器进行排名。
2.5 主动回收(Proactive Reclaim)
主动回收在没有内存压力时触发页面回收。它通常只针对冷页。例如：当一个新任务进来时，任务调度器想要在其选中的服务器上主动回收冷页，以提高成功部署此新任务的机会。
用户可以向 lru_gen 写入以下命令来淘汰序号小于等于 min_gen_nr 的代：
- memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]]
min_gen_nr 应该小于 max_gen_nr-1，因为 max_gen_nr 和 max_gen_nr-1 尚未完全老化(等同于 active 链表)，因此不能被淘汰。swappiness 覆盖 /proc/sys/vm/swappiness 中的默认值。nr_to_reclaim 限制淘汰的页面数量。
典型用例是：任务调度器在尝试在某台服务器上部署新任务之前运行此命令。如果由于高估而未能回收到足够的冷页，它将根据工作集估算步骤获得的排名结果在下一台服务器上重试。这种不那么强硬的方法限制了对现有任务的影响。
3. 核心概念速查表(补充)：
--------------------------------------------------------------------------------- 接口 路径 说明 --------------------------------------------------------------------------------- 主开关 /sys/kernel/mm/lru_gen/enabled 稳定 ABI，位掩码控制各组件 抖动预防 /sys/kernel/mm/lru_gen/min_ttl_ms 保护 N 毫秒内的工作集 调试信息 /sys/kernel/debug/lru_gen 读取直方图，写入老化/淘汰命令 详细统计 /sys/kernel/debug/lru_gen_full 含已淘汰代的历史数据 ------------------------------------------------------------------------------------------------------------------------------------------------------------------ 命令格式 含义 --------------------------------------------------------------------------------- + memcg_id node_id max_gen_nr [can_swap [force_scan]] 创建新代(触发老化) - memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]] 淘汰旧代(主动回收) ---------------------------------------------------------------------------------