多代 LRU

多代 LRU 是一种替代 LRU 实现，它优化了页面回收并提高了内存压力下的性能。页面回收决定了内核的缓存策略和过度提交内存的能力。它直接影响 kswapd 的 CPU 使用率和 RAM 效率。

设计概述

目标

设计目标是

  • 良好地表示访问时间的新近度

  • 尝试从空间局部性中获益

  • 快速路径以做出明显的选择

  • 简单的自纠正启发式方法

访问时间新近度的表示是所有 LRU 实现的核心。在多代 LRU 中，每一代代表一组具有相似访问时间新近度的页面。世代建立了一个（基于时间的）共同参考框架，因此有助于做出更好的选择，例如，在计算机上的不同 memcg 之间或数据中心中的不同计算机之间（用于作业调度）。

利用空间局部性可以在收集已访问位时提高效率。rmap 遍历针对单个页面，并不尝试从发现新的 PTE 中获益。页表遍历可以扫描地址空间中的所有新的 PTE，但地址空间可能太稀疏而无法获益。关键是优化这两种方法并将它们结合使用。

快速路径降低了代码复杂性和运行时开销。未映射的页面不需要 TLB 刷新；干净的页面不需要回写。只有当其他条件（例如访问时间新近度）相似时，这些事实才会有帮助。以世代为共同参考框架，其他因素会突出显示。但显而易见的选择可能不是好的选择；因此，自纠正是有必要的。

简单的自纠正启发式方法的好处是不言而喻的。同样，以世代为共同参考框架，这变得可以实现。具体来说，可以根据其他因素对同一代中的页面进行分类，并且反馈循环可以统计地比较这些类别之间的缺页百分比，并推断出哪些是更好的选择。

假设

热页面的保护和冷页面的选择基于页面访问通道和模式。有两个访问通道

  • 通过页表进行的访问

  • 通过文件描述符进行的访问

前一种通道的保护在设计上更强，因为

  1. 由于访问位的近似，确定前一种通道的访问模式的不确定性更高。

  2. 由于需要 TLB 刷新以及遇到脏位的可能性，驱逐前一种通道的成本更高。

  3. 对前一种通道保护不足的惩罚更高，因为应用程序通常不会像为阻塞 I/O 那样为主要缺页做好准备。例如，GUI 应用程序通常使用专用的 I/O 线程来避免阻塞渲染线程。

还有两种访问模式

  • 表现出时间局部性的访问

  • 不表现出时间局部性的访问

由于上述原因，除非存在 VM_SEQ_READ 或 VM_RAND_READ，否则假定前一种通道遵循前一种模式，并且除非观察到异常的缺页，否则假定后一种通道遵循后一种模式。

工作流程概述

每个 lruvec 的可驱逐页面分为多个世代。最年轻的世代号存储在 lrugen->max_seq 中，对于匿名类型和文件类型，它们以相同的速度老化。最老的世代号分别存储在匿名类型和文件类型的 lrugen->min_seq[] 中，因为无论交换约束如何，都可以驱逐干净的文件页面。这三个变量单调递增。

世代号被截断为 order_base_2(MAX_NR_GENS+1) 位，以便放入 folio->flags 中的 gen 计数器中。每个截断的世代号都是 lrugen->folios[] 的索引。滑动窗口技术用于跟踪至少 MIN_NR_GENS 个，最多 MAX_NR_GENS 个世代。当页面在 lrugen->folios[] 之一上时，gen 计数器存储 [1, MAX_NR_GENS] 范围内的值；否则它存储零。

每个世代分为多个层。通过文件描述符访问 N 次的页面位于层 order_base_2(N) 中。与世代不同，层没有专用的 lrugen->folios[]。与跨世代移动（需要 LRU 锁）相比，跨层移动仅涉及 folio->flags 上的原子操作，因此成本可以忽略不计。一个模仿 PID 控制器的反馈循环监视来自匿名类型和文件类型的所有层的缺页，并决定驱逐或保护哪些类型的哪些层。期望的效果是平衡匿名类型和文件类型之间的缺页百分比，使其与交换度级别成比例。

有两个概念上独立的程序：老化和驱逐。它们形成一个闭环系统，即页面回收。

老化

老化产生年轻世代。给定一个 lruvec，当 max_seq-min_seq+1 接近 MIN_NR_GENS 时，它会递增 max_seq。当老化发现热页面通过页表访问时，它会将热页面提升到最年轻的世代；当它递增 max_seq 时，冷页面的降级会随之发生。老化使用页表遍历和 rmap 遍历来查找新的 PTE。对于前者，它迭代 lruvec_memcg()->mm_list 并使用此列表上的每个 mm_struct 调用 walk_page_range() 来扫描 PTE，并且在每次迭代后，它会递增 max_seq。对于后者，当驱逐遍历 rmap 并找到新的 PTE 时，老化会扫描相邻的 PTE。对于两者，在找到新的 PTE 后，老化会清除已访问位，并将此 PTE 映射的页面的 gen 计数器更新为 (max_seq%MAX_NR_GENS)+1。

驱逐

驱逐消耗老化的世代。给定一个 lruvec，当以 min_seq%MAX_NR_GENS 为索引的 lrugen->folios[] 为空时，它会递增 min_seq。为了选择要从中驱逐的类型和层，它首先比较 min_seq[] 以选择较老的类型。如果两种类型同样老，它会选择其第一层具有较低缺页百分比的类型。第一层包含单次使用的未映射的干净页面，这是最佳选择。如果老化发现此页面通过页表访问并更新了其 gen 计数器，则驱逐会根据其 gen 计数器对页面进行排序。如果此页面通过文件描述符访问多次，并且反馈循环已检测到此页面所在层中的异常缺页，它还会将页面移动到下一代，即 min_seq+1。为此，反馈循环使用第一层作为基线，原因如前所述。

工作集保护

每一代都会在诞生时盖上时间戳。如果设置了 lru_gen_min_ttl，则当 lruvec 中最老的一代诞生时间在 lru_gen_min_ttl 毫秒内时，该 lruvec 将受到保护，不会被驱逐。换句话说，它可以防止 lru_gen_min_ttl 毫秒内的工作集被驱逐。如果无法将此工作集保存在内存中，则会触发 OOM 杀手。

这种基于时间的方法具有以下优点

  1. 它更容易配置，因为它与应用程序和内存大小无关。

  2. 它更可靠，因为它直接连接到 OOM 杀手。

mm_struct 列表

为每个 memcg 维护一个 mm_struct 列表，当任务迁移到新的 memcg 时，mm_struct 会跟随其所有者任务。

页表遍历器迭代 lruvec_memcg()->mm_list，并使用此列表上的每个 mm_struct 调用 walk_page_range() 以扫描 PTE。当多个页表遍历器迭代同一列表时，每个遍历器都会获得一个唯一的 mm_struct，因此它们可以并行运行。

页表遍历器会忽略任何错放的页面，例如，如果 mm_struct 已迁移，则当前 memcg 正在回收时，将忽略留在先前 memcg 中的页面。类似地，页表遍历器将忽略来自回收节点之外的节点的页面。

此基础结构还会跟踪上下文切换之间 mm_struct 的使用情况，以便页表遍历器可以跳过自上次迭代以来一直处于休眠状态的进程。

Rmap/PT 遍历反馈

在 LRU 列表上搜索映射每个页面的 PTE 的 rmap（以测试和清除访问位）可能很昂贵，因为来自不同 VMA（PA 空间）的页面对 rmap（VA 空间）不具有缓存友好性。对于主要使用映射页面的工作负载，搜索 rmap 可能会在回收路径中产生最高的 CPU 成本。

lru_gen_look_around() 利用空间局部性来减少进入 rmap 的次数。它扫描年轻 PTE 的相邻 PTE 并提升热页面。如果扫描是以缓存行高效方式完成的，它会将指向 PTE 表的 PMD 条目添加到布隆过滤器。这会在驱逐和老化之间形成反馈循环。

布隆过滤器

布隆过滤器是一种空间和内存高效的数据结构，用于集合成员测试，即测试元素是否不在集合中或可能在集合中。

在驱逐路径中，特别是在 lru_gen_look_around() 中，如果 PMD 有足够数量的热页面，则将其地址放置在过滤器中。在老化路径中，集合成员资格意味着将扫描 PTE 范围以查找年轻页面。

请注意，布隆过滤器在集合成员资格方面是概率性的。如果测试结果为假阳性，则代价是额外扫描 PTE 范围，这可能无论如何都会产生热页面。过滤器本身的参数可以控制限制中的误报率。

PID 控制器

一个模仿比例-积分-微分 (PID) 控制器的反馈循环监视匿名类型和文件类型的重故障，并决定当同一代中同时存在这两种类型时驱逐哪种类型。

PID 控制器使用世代而不是挂钟作为时间域，因为 CPU 可以在不同的内存压力下以不同的速率扫描页面。它会为每个新世代计算移动平均值，以避免永久锁定在次优状态。

Memcg LRU

memcg LRU 是每个节点的 memcg 的 LRU。它也是 LRU 的 LRU，因为每个节点和 memcg 组合都有一个 folios 的 LRU（请参阅 mem_cgroup_lruvec()）。它的目标是提高全局回收的可扩展性，这对于数据中心的全系统内存过度提交至关重要。请注意，memcg LRU 仅适用于全局回收。

memcg LRU 的基本结构可以通过类比活动/非活动 LRU（folios）来理解

  1. 它具有年轻的和旧的（世代），即活动和非活动的对应物；

  2. max_seq 的增加触发提升，即激活的对应物；

  3. 其他事件会触发类似的操作，例如，离线一个 memcg 会触发降级，即停用的对应物。

在全局回收方面，它有两个不同的特性

  1. 分片，允许每个线程在旧世代中从一个随机 memcg 开始，并提高并行性；

  2. 最终公平性，允许直接回收随意放弃，并减少延迟，而不会在一段时间内影响公平性。

在全局回收期间遍历 memcg 方面，它将最佳情况复杂度从 O(n) 提高到 O(1)，并且不影响最坏情况复杂度 O(n)。因此，平均而言，它具有亚线性复杂度。

摘要

多代 LRU（folios）可以分解为以下部分

  • 世代

  • Rmap 遍历

  • 通过 mm_struct 列表进行的页表遍历

  • 用于 rmap/PT 遍历反馈的布隆过滤器

  • 用于重故障反馈的 PID 控制器

老化和驱逐构成生产者-消费者模型；具体来说，后者通过世代上的滑动窗口驱动前者。在老化过程中，rmap 遍历通过将热的密集填充的页表插入到布隆过滤器来驱动页表遍历。在驱逐过程中，PID 控制器使用重故障作为反馈来选择要驱逐的类型和要保护的层。