多代 LRU

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

设计概述

目标

设计目标是

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

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

  • 快速路径做出显而易见的选择

  • 简单的自我纠正启发法

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

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

快速路径降低了代码复杂性和运行时开销。未映射的页面不需要 TLB 刷新;干净的页面不需要写回。只有当其他条件(例如,访问新近度)相似时,这些事实才有用。以代为共同参考框架,其他因素会更加突出。但显而易见的选择可能不是好的选择;因此自我纠正至关重要。

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

假设

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

  • 通过页表访问

  • 通过文件描述符访问

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

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

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

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

还有两种访问模式

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

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

由于上述原因,除非存在 VM_SEQ_READVM_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 killer。

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

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

  2. 它更可靠,因为它直接连接到 OOM killer。

mm_struct 列表

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

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

页表遍历器忽略任何错位的页面,例如,如果 mm_struct 已迁移,则当当前 memcg 正在回收时,将忽略留在先前 memcg 中的页面。同样,页表遍历器将忽略来自回收下的节点以外的节点的页面。

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

Rmap/PT 遍历反馈

搜索 rmap 以查找 LRU 列表上的每个页面映射的 PTE(以测试和清除访问位)可能很昂贵,因为来自不同 VMA(PA 空间)的页面对 rmap(VA 空间)不友好。对于主要使用映射页面的工作负载,搜索 rmap 可能会导致回收路径中最高的 CPU 成本。

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

Bloom 过滤器

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

在驱逐路径中,具体来说,在 lru_gen_look_around() 中,如果 PMD 具有足够数量的热页面,则将其地址放置在过滤器中。在老化路径中,集合成员意味着将扫描 PTE 范围以查找新的页面。

请注意,Bloom 过滤器在集合成员资格方面是概率性的。如果测试是假阳性,则成本是额外扫描 PTE 范围,这可能会产生热页面。过滤器本身的参数可以控制限制中的假阳性率。

PID 控制器

模仿比例-积分-微分 (PID) 控制器的反馈循环监视匿名和文件类型的缺页中断,并决定当两种类型都来自同一代时要驱逐哪种类型。

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

Memcg LRU

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

memcg LRU 的基本结构可以通过类似于 active/inactive LRU(的 folios)来理解

  1. 它具有年轻和旧(代),即 active 和 inactive 的对应项;

  2. max_seq 的递增触发提升,即激活的对应项;

  3. 其他事件触发类似的操作,例如,离线 memcg 触发降级,即停用的对应项。

在全局回收方面,它具有两个不同的功能

  1. 分片,允许每个线程从随机 memcg(在旧代中)开始并提高并行性;

  2. 最终公平性,允许直接回收随意退出并减少延迟,而不影响一段时间内的公平性。

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

总结

多代 LRU(的 folios)可以分解为以下部分

  • Rmap 遍历

  • 通过 mm_struct 列表的页表遍历

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

  • 用于缺页中断反馈的 PID 控制器

老化和驱逐形成生产者-消费者模型;具体来说,后者通过对代进行滑动窗口来驱动前者。在老化中,rmap 遍历通过将热的密集填充的页表插入到 Bloom 过滤器来驱动页表遍历。在驱逐中,PID 控制器使用缺页中断作为反馈来选择要驱逐的类型和要保护的层级。