HawkEye—高效、细粒度的大页管理算法

1.作者简介

• Ashish Panwar：微软印度研究院，系统研究组高级研究员，博士毕业于印度科学学院(Indian Institute of Science)，ASPLOS一作三篇
• Sorav Bansal：印度理工学院计算机学院微软特聘教授，主要研究编程语言与操作系统，博士毕业于斯坦福大学
• K. Gopinath：印度科学学院计算机科学与自动化学院教授，主要研究计算机系统领域(操作系统，存储系统，系统安全和系统验证)

2.文章简介与摘要

文章发布于2019年，被ASPLOS接收

  对于操作系统，为了降低地址翻译的开销，高效的大页内存管理机制是十分有必要的。Ingens揭示了当时的大页内存管理机制的一些困难。

  本文提出了一个新的系统，叫做HawkEye/Linux，旨在提供一些解决性能、缺页中断延迟和内存膨胀的方案，它的核心是HawkEye管理算法。实验证明，HawkEye算法相比当时(2019)的SOTA系统展现出了更好的性能、更强的健壮性以及对于各种各样负载状况的适用性。

3.简介

  现代应用程序的内存使用量大，通用处理器的地址翻译开销值得重视
  现在的体系结构使用更大的多级TLB(转译后备缓冲器，快表)来尝试解决这个问题，它们也支持多种页面大小

  在虚拟机环境当中，因为涉及到两层地址转换，MMU的开销变得更加严重。同时，大页内存管理在一些重要的应用上呈现出了不尽如人意的性能，而一些文章认为，这是因为缺少一个合适的基于操作系统的大页内存管理算法导致的。

  而基于操作系统的大页内存管理算法需要权衡地址翻译开销、内存膨胀、缺页中断延迟、公平性以及算法本身的开销等问题；本文讨论了一些大页内存管理的细节、揭露了当前(2019)的方法的一些缺陷，并且提出了一套全新的算法来解决这些问题。

(1).当时的SOTA系统概述

Linux

  Linux通过后台运行的一个叫做khugepaged的内核线程来实现透明大页(Transparent Huge Page)，它采取两个机制：

• 1.在有连续可用内存的前提下发生缺页中断时，一次性分配一个大页面
• 2.通过选择性地压缩内存的方式将基本页面合成为大页面。

  当碎片化水平比较高且在发生缺页中断的时候难以分配大页面的时候，Linux会触发background promotion；在分配大页面时，khugepaged会按照先来先服务(FCFS) 的顺序来选择进程并为它们分配大页面，并且为了安全，在页面被映射到用户进程页表之前会被异步置零（CoW页面除外）

FreeBSD

  FreeBSD支持多种大页面尺寸。和Linux不一样，FreeBSD在缺页中断处理程序的物理内存位置保留了一块连续的区域，在分配大页时，FreeBSD会在一个大页面大小的内存区块当中的所有标准页面都被应用程序分配后才会进行相应的操作。
  当被内存压力显著提升的时候，如果被保留的内存区域只被部分映射，那么没有被用到的页面会被归还给页面分配器。基于这样的策略，FreeBSD在连续的内存管理上比Linux更加高效，但这样做的后果可能是更多的缺页中断以及更高的MMU开销（因为每个基本页面都需要一个TLB条目）

Ingens

来自Coordinated and efficient huge page management with ingens

  Ingens这篇文章指出了Linux和FreeBSD在大页内存管理策略上都存在一些问题，作者在此基础上提出了一个更好的策略，总结为以下三点：

• 1.Ingens使用自适应策略来平衡地址转换开销和内存膨胀：它采用基于conservative utilization-threshold(保守利用率的)大页面分配来防止在内存压力大时出现内存膨胀(我的理解是低利用率下的大页面分配可能导致原本所需的内存膨胀到一个更大值，因此在内存压力比较大的情况下，需要减少大页面的分配)，但在没有内存压力的情况下放宽阈值以积极分配大页面，以试图实现两者的最佳平衡。
• 2.为了减少同步置零导致的缺页中断高延迟，Ingens采用了一个专用的内核线程来完成异步置零(同步置零是在分配的时候完成置零，而异步置零则是在分配时标记为已置零状态，之后再通过其他方式将页面置零，即该操作与页面分配并不是同步进行的)
• 3.为了维持多进程之间的公平性，Ingens将内存连续性视为一种资源，并且采取了基于份额的策略来公平地分配大页面

  Ingens的论文指出当前的OS处理大页内存管理的问题总是存在采取spot fixes，也就是一些临时性的修复措施（相当于打补丁），这种方式不总是全面的，因此需要整体上的重新设计来解决相应的问题

(2).HawkEye

  基于前述的SOTA系统以及Ingens改进策略的不足，本文提出了简单但有效的HawkEye算法，它的优势总结为以下几点：

• 1.做到了内存膨胀、地址翻译开销和大页面延迟等问题之间的权衡
• 2.将大页面分配给预期将会有最大提升的应用
• 3.改进了虚拟化系统当中的内存共享行为

  文章当中还展示了基于性能计数器测量得到的地址翻译开销可能和真是的开销有比较大的差距，在后续的实验部分会有相应的内容，整个HawkEye算法经过实验，可以对当前的系统产生客观的性能提升，并且增加非常小的开销（最坏情况下增加3.4%的单核开销）

4.动机

(1).地址翻译开销与内存膨胀

  在大页内存管理的几个问题当中最重要的权衡就是地址翻译开销和内存膨胀之间的权衡。
  Linux的同步大页面分配旨在最小化MMU开销，但这样的机制可能会在应用只利用很小一部分内存空间的时候产生严重的内存膨胀现象（简单来说就是，更大的页面能带来更小的页表，从而产生减少MMU开销，但是却会导致因为大页面而产生的内存膨胀和浪费现象显著增加）
  而FreeBSD只有在同一个大页面区域内所有的标准页面被分配后才会分配大页面，这种保守的策略可以显著减少内存膨胀的问题，但是通过延迟映射大页面的措施会牺牲性能（大页面的分配过于保守，MMU的开销相比Linux更大）
  Ingens的策略是动态的，在内存碎片水平很低的时候更加激进地分配大页面来减少MMU开销。为了评估碎片水平，Ingens采用了FMFI(可用内存碎片指数)，当FMFI小于0.5的时候说明碎片水平很低，此时Ingens表现得更像Linux，一旦可以分配大页面，就立刻尝试分配；而当FMFI大于0.5时，说明内存碎片水平已经比较高了，此时采取保守的基于利用率的策略，即当大页面空间内的某个固定比例的标准页面已经被利用时，才进行大页内存的分配，基于这样的策略又可以减少内存膨胀的问题。

  本文的作者则认为，虽然Ingens通过融合两种策略来尝试结合二者的优点，但是仍然无法解决在激进分配阶段所产生的内存膨胀问题，本文做的第一个实验就是基于此：

  实验在一台48GB物理内存的主机上基于Redis数据库完成了一个RSS(RSS表示当前进程实际驻留在物理内存中的内存量)大小的评估，实验过程分了三个阶段，第一阶段，Redis客户端会尝试向数据库插入1100万个键值对(10字节+4K字节)，这一阶段会最终占用45G左右的内存。
  第二阶段，客户端会随机删除80%的键，随机删除是为了使得Redis进程的内存空间变得更加零散。
  第三阶段再次进行插入操作，这个阶段会使得整个Redis进程占用的内存重新回到45G。
  从图中可以发现，三种方法在P1和P2阶段的RSS几乎都是一致的，但是到了P3阶段尝试再次进行插入的时候，在RSS达到32G左右的时候，Linux仍然在进行激进的大页分配，而此时Ingens已经感知到了内存碎片变得比较严重，开始尝试保守分配，正是因此，Ingens比Linux多坚持了一段时间才出现OutOfMemory，但是HawkEye直到实验的最后仍然能够顺利完成。
  作者评估，Linux大约有28G的内存因为内存膨胀而被浪费，而Ingens则有20G左右，这就揭示了作者认为Ingens不是最优解的真正原因：Ingens的策略在设计到内存膨胀的时候，只采用了保守分配策略，即只是依据目前的内存剩余情况和利用率进行下一步分配，却不能解决先前激进分配大页已经造成的内存浪费。

(2).缺页中断延迟与缺页中断次数

  操作系统需要在将页面映射到进程地址空间之前，将页面置零，否则可能产生一些不安全的信息流动（之前进程在内存遗留的数据被其他进程访问到），而对于大页面来说，清零的开销要显著高于标准页面(2MB大小的页面是4KB的512倍，清零的开销肯定是要高很多的)。
  作者在基于Linux的实验系统上进行测试，一个标准大小的页面清零需要消耗整个缺页中断流程时间的25%，而大页面的情况下，这个时间会增长到97%，也就是说，大页面的情况下，缺页中断流程时间中的97%都是在进行页面置零操作。
  更高的缺页中断延迟会产生用户可以明显感知到的显著延迟，所以Ingens解决这个问题的方法是：Ingens只在缺页中断处理程序中分配标准大小的页面，之后再将标准页面合并为大页面的操作交给khugepaged这个异步线程来完成（也就是前面所说的异步置零）
  大页内存管理的一大优势就在于，相邻内存访问的情况下，缺页中断的次数会明显减少，因为在更大的页面下，相邻内存在同一页面下的概率更高，缺页中断次数就会减少，但是Ingens的策略可能导致页面不会合并，从而导致缺页中断次数可能会比真正的大页面要多很多，而这样一来，大页面的这个优势在Ingens下就可能失效了。
  而这一点就引出了本文的第二个实验：使用一个测试程序分配10GB的缓冲区，并且对每一次访问一个基本页面中的字节，最后释放缓冲区，在实验十轮之后可以得到以下的结果：

  对于有同步置零的Linux，开启大页面之后，测试流程中缺页中断数从2620万次降低到了5.15万次，减少到了之前的五百分之一，同时因为同步置零本身的开销，大页面的情况下，平均缺页中断时间从3.5微秒飙升至465微妙，恶化近133倍。
  Ingens的异步置零操作的确显著降低了缺页中断的平均时间，但是缺页中断次数和小页面的Linux几乎是完全一致的，最后从时间上来看，甚至要比小页面情况下花费时间更长。
  最后一栏的测试中去除了同步置零的操作，可以看到小页面中置零操作的时间占比大约是25%，而大页面中指令操作的时间占比则是约97%，这与前面所说的是一致的。

(3).多处理器大页面分配

  操作系统需要公平地在多处理器之间分配大页面，Ingens通过定义一种基于比例的大页面提升(提升即promote，也可以叫做分配在这里是将小页面合并为大页面的过程)度量来尝试实现公平分配。
  过程是这样：Ingens会对分配了大页面但是不经常访问的应用程序进行惩戒(penalize)，这个部分通过页表项当中的访问位(这就是之前作业分析Linux页表结构当中一定会注意到的字段_PAGE_BIT_ACCESSED)来实现。
  但是Ingens的公平策略有一个显著的缺陷(哈哈哈，这篇文章真的一直在吐槽Ingens)：如果两个进程P1和P2，它们有相似的大页内存需求，但是P1经常性地随机在不同标准页面的位置访问，而P2只在几个比较集中的位置访问，则P1显然应该优先于P2被分配大页面，但是Ingens的惩戒策略对于这种情况下对于P1和P2的表现是一致的。
  这里简单描述一下为什么P1应该被优先分配大页面，P1因为涉及到更加频繁的随机访问，就可能经常会在TLB中查询，因为TLB的条目数量固定，如果页面大小比较小，那么随机访问可能会导致TLB命中次数显著下降，因为随机访问到同一页面内的概率会下降，而如果页面更大，此时TLB命中的概率就会增加，因为TLB中只对应逻辑地址的前部和页面号，因此如果能够多次命中相同页面，访问延迟就会大大降低。

  因此本文认为，将MMU开销视作系统开销，并尝试以均衡不同进程间的MMU开销的策略才是真正公平的算法。
  除此之外，Ingens在激进分配阶段可能因为零星几次缺页中断就给程序分配大页面，但是这个大页面可能并不是程序所需要的，但是它们仍然被分配到了大页面。

(4).如何测算地址翻译开销？

  一种比较普遍的做法是使用WSS(Working Set Size)来测算MMU开销，WSS表示进程当前正在使用的活跃页面的集合大小，当WSS随时间增长变化较快的时候，则说明当前内存访问频繁，可能造成更大的MMU开销。

  作者团队发现：利用WSS测算MMU开销可能是不太正确的，对于现代硬件来说，访问内存的模式在MMU开销中发挥了重要作用，例如序列化地访问可以减少TLB未命中导致的延迟，因此有了下一个实验：

  团队利用NPB测试组件进行了一次测试，对于mg.D和cg.D两个负载，mg.D相较于cg.D有显著更高的WSS，但是mg.D的TLB未命中率(0.03%)显著低于cg.D(28.57%)，从而导致mg.D的MMU开销实际上比cg.D更低。
  因此，本文提出了一个可以用来直接计算MMU开销的公式：

  不过这些数据来自硬件计数器，所以可能存在可移植性的问题，因此本文还提出了这个方法的一些变种(HawkEyePMU和HawkEye-G)。

5.设计与实现

(1).HawkEye概述

  上图中展示了HawkEye算法的设计目标，这个方法基于四个主要的观察结果：

• 1.通过异步置零可以显著降低大页面缺页中断的延迟
• 2.通过识别并去除大页面中的零填充页面可有效减少内存膨胀问题(去掉大页面中没有被利用到的部分)
• 3.决定是否要将基本页面合并为大页面时，应该更加细粒度地追踪大页面区域的内存访问时间、频率等更多因素
• 4.大页内存分配的公平性应该考虑MMU开销

(2).异步页面置零

策略来源与问题解决

  文章采取了在2000年代曾经被内核开发者讨论的异步预置零(async pre-zeroing)方案，早年间Linux开发者认为这种策略因为两个主要原因而不能达到整体上的性能提升，而到了今天，这个方案可能可以被重新审视一下。

  第一个主要原因是：异步预清零的线程可能会污染缓存，从而干扰目前主要的负载。特别地，这种措施可能会遭受两次缓存未命中的问题：即第一次异步预清零线程对页面进行置零操作，而因为这个页面不是被程序所需要的内存，因此会发生第一次缓存未命中；之后等到应用程序真正访问这片内存的时候，可能距离上一次访问已经很久了，从而再次导致缓存未命中，这样就会导致总体的性能表现不佳。
  然而在现代硬件当中，这个问题可以通过非临时提示(non-temporal hints) 来部分解决，非临时提示可以让硬件绕过缓存而直接对内存进行load和store指令，这样就可以减少两次缓存未命中的问题。

  第二个问题则是没有共识或是实质性的证据能够证明：页面预清零对于真实的工作负载是有好处的。作者团队观察到早期对于页面预清零策略的讨论主要是针对4KB页面，在先前的实验中，我们可以观察到4KB页面的清零策略可能只有25%左右的提升，因此当初的开发者没有采纳这个方法也是可以理解的，但是对于2MB大页面的内存，这个提升幅度可能会达到97%，因此这种异步预清零的策略在如今考虑大页内存管理的情况下值得被重新审视。

  除此之外，页面预置零可以在物理内存空间上产生很多全零的页面，这位虚拟化的系统提供了一个优势：多个虚拟机或进程可能可以共用这些空白页面，从而节省内存资源。

实现

  HawkEye基于Linux的Buddy Allocator，通过zero和non-zero两个列表来管理空闲的页面。当页面被进程释放时，首先会被添加到non-zero列表，在分配页面的时候，会优先选择zero列表中的页面。同时，一个速度有限的线程会周期性地利用非临时性写将non-zero列表中的页面置零，之后再添加到zero列表中。
  因为预清零主要涉及到了顺序内存访问，非临时性的stor指令可以提供和常规store指令(对于缓存的store)一致的性能，并且这样做不会污染缓存。
  还有一个值得关注的是CoW(写时拷贝)或基于文件系统的内存区域，对于这些区域来说，预清零可能是不必要甚至说是比较浪费的(因为写时拷贝会在真正发生写操作的时候才进行复制，因此不会存在之前的内存脏页数据被新的进程访问的问题，预先置零只会增加这个过程的开销)，因此对于这个问题，可以通过优先从non-zero列表中分配页面来解决。

(3).平衡性能与内存膨胀问题

  作者团队认为MMU开销和内存膨胀之间的矛盾是可以解决的，他们观察到：高内存占用的负载的内存分配通常是“零填充页面分配”，而通常的例外是基于文件系统的或是CoW的内存区域。
  然而对于现代的大规模工作负载中，大页面主要用于被内核置零的匿名页面，比如Linux只支持对匿名内存使用大页模式(匿名内存指的是在操作系统中不予实际文件名关联的内存分配，例如堆、栈空间以及动态分配的内存区域，一般便是在文件系统中没有对应文件的内存)。而这个性质使得Linux在面临内存压力的情况下从内存膨胀中自动恢复成为可能。

  因此HawkEye基于此设计了这样一个步骤，简单来说就是：HawkEye在第一次发生缺页中断的时候就会开始分配大页面；当面临内存压力的时候，为了回收未使用的内存，HawkEye会扫描所有现存的大页面来找到其中的零填充页面。如果一个大页中的零填充页面超过了一个阈值，HawkEye就会将大页面拆成多个标准页面，并且在之后通过标准的Copy-On-Write页面管理技术将这些零填充的基准页面进行去重为一个规范的零页面。
  这种方法使得对应用程序正在使用的零页面进行去重变得可能，当然，这可能导致一些罕见情况下，Copy-On-Write发生的缺页中断数量略微增加，当然，这不会影响正确性。

  为了触发内存膨胀的恢复机制，HawkEye使用了两个水位线：high和low来完成这个流程。当已分配内存的占比超越了high值(HawkEye原型中定为85%)时，一个速度有限的膨胀恢复线程就会被激活，它会周期性地执行操作直到已分配内存降到low值以下(HawkEye原型中定为70%)。
  而膨胀恢复线程会做这些操作：基于已经测算到的MMU开销，从应用中选择一个需要被扫描(并且有可能发生降级，应该是大页分拆)的程序，其中具有最低的MMU负载的程序会被优先选择进行扫描(因为低MMU负载可能意味着更多内存访问在相同页面内，大页内存的分配对这个进程来说可能是不必要的)，这样的策略确保了最不需要大页面的程序总是被优先考虑，这和HawkEye的页面分配策略保持一致。

  扫描大页面，检验是否零填充的过程会在遇到第一个非零字节的时候停止；而实际上，每个在使用（非零填充）的页面遇到首个非零字节的位置总是比较小的，团队检验了总计56种不同的负载，并且发现在一个4KB页面中发现首个非零字节的平均位置在9.11字节：

  因此，平均下来每个正在使用的页面只需要扫描是个字节即可。但是对于膨胀的页面(没有被使用到的全零填充页面)，整个4096字节都需要被扫描，这使得HawkEye方法的膨胀恢复线程开销与系统中的膨胀页面数量成比例，而并非与已经分配的内存大小成比例，这个性质使得HawkEye方法对于高内存系统被来说是适用的。

  这种方法与虚拟机系统中为实现基于内容的页面共享技术而存在的标准内核去重线程的行为几乎是一致的(基于内容的页面共享与CoW息息相关，对于相同内容的物理页，可以通过ksm线程完成合并，然后再分配相应的虚拟页，仅当发生修改时才会复制一份进行修改，再进行写入)，但是目前的内核当中，大页内存管理(khugepaged)和内核同页合并(ksm)是相互独立的，它们共同工作可能会产生冲突，Ingens通过修改ksm的行为，使得其仅对不常用的大页面进行降级，而SmartMD则根据访问频率和重复率(共享页面占的比例)来降级页面，这些措施对于正在使用的页面是很有效的，而HawkEye的方案则是通过识别未使用的零页面识别出来进行合并，这比一般的同页合并逻辑更快。

(4).细粒度的大页内存分配

  当前的系统一般是通过从低到高地顺序扫描虚拟地址从而进行页面提升的，这种方法对于某些高频访问区域不处于低虚拟地址空间的应用来说效率并不高(可以理解，因为如果进程需要大页面，但是高频访问区域处在高虚拟地址的时候，该进程的页面提升总是要更晚才能发生，而在这之前可能已经发生比较频繁的未命中了)。
  因此HawkEye的方法是基于内存访问模式来决定是否进行页面提升：首先文章定义了一个用于HawkEye进行提升页面的指标—访问覆盖率，它表示短时间内从一个大页面大小的区域访问基本页面的次数。
  HawkEye方法会定期采样页表项中的访问位(先前已经提到)，并且它会在不同的样本之间采取指数移动平均的方式的方式进行维护(这个就很像计网当中测算RTT的方式了)，更具体一点说：HawkEye会将访问位清零，一秒之后统计有多少个页面被访问过，这个过程每30秒重复一次。
  访问覆盖率这个指标一定程度上反映了对于TLB空间的需求(因为统计的是页面覆盖率，页面覆盖率越高，TLB中存储的条目就会越多，因为同一页访问多次不会增加访问覆盖率)，HawkEye使用了一个基于进程的数据结构，称为access_map，它是一个桶的数组，每个桶中都会存储访问覆盖率大致相同的大页面区域；在x86机器上，如果使用2MB的大页面，则访问覆盖率的范围就是从0~512(基于透明大页机制实现的大页管理，会动态地将标准页面合并为大页面)，基于此，访问覆盖率在0~49之间的被放在桶0中，50~99之间的被放在桶1中，以此类推，例如这就是对于进程A、B和C的access_map：

  每次采样之后，内存区域都可以基于新计算出的访问覆盖率向上或向下移动，桶的内部以链表形式管理，当内存区域向上移动，会被加到链表头；当向下移动，则会被加到链表尾，在桶内，页面则会从头到尾被提升为大页面。这样的策略有助于对最近访问的区域进行优先处理。

(5).多处理器大页内存分配

  这里仅提了一下关于HawkEye不基于硬件计数器的变种(HawkEye-G和HawkEye-PMU)，这里就不再赘述了。

(6).局限性

阈值的选择

  在评判内存压力的时候采取了low和high两个静态的基准，而这样的措施可能过于保守或者过于激进，比较理想的做法可能是进行动态调整。

大页面饥饿现象

  虽然HawkEye的确行之有效，但是一些恶意进程可能操控HawkEye来分配过量的大页面从而使得其他进程更难被分配到大页面。

6.实验与评估

• 实验平台：两块Intel 志强E5-2690 v3 48核心(开启超线程)，96GB物理内存
• 操作系统：基于Linux 4.3的CentOS 7.4
• 评估方向：基于访问覆盖率的细粒度提升策略在各种负载下的提升；内存膨胀与性能的权衡；低缺页中断延迟的影响；异步预清零线程导致的缓存干扰以及开启异步页面预清零对于内存效率的影响

  首先是基于访问覆盖率的细粒度提升策略在各种负载下的提升，相较于基准页面，HawkEye方法的加速以及页面提升时间节省幅度都要远高于Linux和Ingens：

  然后是对于Graph500和XSBench的访问覆盖率、MMU负载以及大页面数量比较，可以发现，HawkEye的方法也要显著优于Linux和Ingens：

  在对于异步页面清零的对比上，HawkEye大页管理的各项指标都要优于Linux和Ingens:

结论

  透明大页管理非常有必要，但实在是相当复杂，对于操作系统来说，为了权衡性能与稳定性，更加有效且高效的算法是必要的。本文中指出了对于当前已经存在的大页内存管理方法的一些重要细节，并且提出了一系列用于解决这些问题的算法，称为HawkEye。

  这是我第一次阅读体系结构相关领域的论文，其中肯定会存在很多瑕疵与错误，若有发现错误希望不吝赐教，感谢各位。