为了理解ZGC算法，在网上查找资料时发现有文章称ZGC算法参考了C4垃圾回收算法，因此阅读了C4算法的论文C4: The Continuously Concurrent Compacting Collector，本文同G1垃圾收集器一样，属于阅读论文的笔记，大部分是论文逐字翻译，如有错误，请不吝赐教。

摘要

C4，是一种持续的、并发的、压缩式的垃圾收集器，是一种改进的无停顿垃圾收集算法，这里将介绍其在现在X86机上的实现。它使用读屏障(read barrier)实现了并发压缩(concurrent compaction)、并发重映射(concurrent remapping)以及并发增量更新追踪(concurrent incremental update tracing)。C4和其他分代垃圾收集器不同，其支持多代并发收集：不同的代采用非STW式的并发收集机制，因此不同的代垃圾回收可以独立进行(active)。C4可以持续进行并发的年轻代垃圾收集，即使同时执行长时间(长周期)的并发全堆垃圾收集。这个特性使得C4具有较高的分配率(allocation rate)，并能保证分代收集的高效性，而不至于牺牲响应时间或者引入STW停顿。...(C4在Azul系统应用、实现介绍，省略)。这篇文章我们会介绍C4在X86上的实现细节，比如如何增强Linux虚拟及物理内存的管理以支持高频率的虚拟内存操作(virtual memory operations)，满足无停顿的要求。我们也会讨论在长时间运行的应用中如何更新垃圾收集器管理的堆空间来提供高效率的、高吞吐量、低延迟的垃圾收集。

1 引言

分代垃圾回收基于weak generational hypothesis(弱分代理论)：比如大部分的对象都会在年轻代被回收(die)，因此集中精力优化年轻代的垃圾回收就会较好的提高垃圾回收性能。分代的垃圾回收可以提供较高的分配率(allocation rate)，也就保证了较高的吞吐量。许多分代垃圾回收算法将堆分成两代，年轻代分区往往分配较小的堆空间，也会频繁的触发对年轻代分区的回收。这保证了在高分配率的情况下只会造成Mutator线程的短时间中断，也使得老年代的垃圾回收被尽可能的推迟以及频率的降低，降低了垃圾回收造成的负载，响应时间只会在进行全堆(full heap)垃圾回收时被影响。

许多的垃圾收集算法都具有STW、复制、并发、年轻代回收等特点，通过多线程并发、低停顿的年轻代收集来提供可接受的垃圾回收代价。虽然年轻代的垃圾收集造成的延迟一般都比较低，但是在目前服务器规模(规模应该指当前普遍的处理能力，文章发表于2011年)下有时（甚至频发的）会造成长时间的GC停顿，这会发生在年轻代分区中分配大量中等年龄(medium life)的对象，这些对象在被提升(promoted)到老年代之前会被频繁的复制，也会发生在程序运行阶段改变时造成的大量、快速的长存活对象分配(long-lived)时。第一种场景一般会发生在缓存应用中，像具有许多状态对象会话(fat-state session)商业应用(比如门户网站，portals)，以及内存中具有许多副本数据的应用和消息系统中。后面一种场景则发生在应用程序状态变化中，比如应用启动时，应用故障恢复时，缓存预热时(cache hydration times)，分类或者一些内容数据更新重载入时。

因为对分区变大（指的是目前越来越大的内存空间）使老年代垃圾回收引入较大的STW停顿时间，从而影响停顿时间，这种问题是人尽皆知的。且现在许多应用都使用10（甚至100）数量级的GB内存空间，这种大空间造成的年轻代垃圾回收偶尔出现的长时间停顿愈加使许多商业应用所不能接受。目前的商业服务器环境都普遍配置了100数量级的GB内存空间，即使某些占用空间较少的应用都会保持10GB的存活数据。

问题的核心就是数据的压缩(compaction，指的是将存活数据移动到一起，减少空间碎片)和迁移(relocation，比如G1的evacuation等)：基本上所有的分代垃圾收集器都会进行数据迁移。实现一个没有提升(promotion，或晋升，年轻代对象在指定次数之后的垃圾收集之火依然存活会被晋升到老年代)是几乎不可能的。为了保证年轻代垃圾回收能够并发进行，就必须支持并发的对象迁移。许多文献都提出了并发对象迁移的实现，但是在本文写作时(论文发表于2011年）除了Azul's的JVM实现，没有其他的商业JVM支持并发压缩和迁移，其他商业虚拟机也包括. NET。

C4是一种分代的、持续并发压缩垃圾收集算法。C4在进行完整堆(full heap)收集时，同样也是对吞吐量友好的多代垃圾收集器，是一种基于单分代读屏障的垃圾无停顿垃圾收集器(single generation read barrier based Pauseless GC algorithm)。C4使用并发压缩方式收集所有的分代，避免了STW操作，使得应用程序在垃圾收集的任何阶段都能保持高吞吐量。不同代的垃圾回收操作或者阶段可以同时并发进行。目前的C4算法将堆分为年轻代和老年代，但是算法可以很容易扩展至N代。

X86上的C4实现基于自定义的Linux内核，这种内核支持新的虚拟内存系统，可以满足实现C4并发操作和页生命周期(page life)需要的特性和吞吐量。本文主要介绍如下内容：

1. C4算法的基础介绍，包括不同代之间如何并发回收以及页的生命周期(page lifecycle)。
2. 为了支持C4而添加到Linux内核的虚拟内存子系统。
3. C4对堆的管理逻辑（C4's updated heap management logic）。

2 C4算法

C4算法是一种分代的、并发、压缩式垃圾回收算法。它采用两个自定义的无停顿垃圾回收算法实例来支持年轻代和老年代的并发收集。每个分代都会经过对象标记(mark)、对象迁移(relocate)以及引用重映射(reference remap）这三个阶段。C4并发压缩算法的实现基础包括：

2.1 值加载屏障(读屏障, The loaded value Barrier, LVB）

LVD是对无停顿式GC读屏障的变形。LVB在将引用从内存加载和对Mutator变得可见时增加了一系列的不变式特性（invariants）（在使用这些引用时不要求其满足不变式特性）。所有被加载的引用都有如下不变式特性：

• 所有可见的（这里的可见应该是Mutator可见）引用值在没有被标记过时，都可以被安全的标记。
• 所有可见的引用值都指向它们引用的可被安全访问的目标对象。

在程序运行过程中，LVB可能会遇到某些被加载过的引用不满足上面的不变式特性。此时，在这些引用对后续应用操作之前，LVB会触发特定的垃圾收集代码立刻进行修复，使得引用满足上述要求的不变式特性。

LVB和其他屏障的不同主要体现在如下两点：

1. LVB同时在引用指向的目标地址和引用自身标记状态上引入了不变式特性。
2. LVB保证（或者要求）在不满足不变形特性时Mutator可以使用自我修复行为（下面介绍）进行及时的修复。这使得C4可以找到最快的执行路径，从而支持并发标记、并发迁移以及并发重映射等特性。

2.2 自我修复（Self Healing）

LVB读屏障是一种具有自我修复功能的屏障。因为LVB执行于引用加载过程中，所以它不仅仅可以访问验证过的引用值，也可以访问这些引用值的内存地址。当LVB被触发并且进行修复操作修改引用使其满足不变性约束时，它会自动的将引用的值拷贝到该值原先的内存地址处，以此修复该引用的内存源地址。这样可以让mutator线程能够快速修复引起LVB触发的根本原因（指的是引用源内存地址处发生变化），避免了后续其他引用同一内存地址LVB被重复触发，也就极大地减少了读屏障被触发的次数。每个引用源地址“最多触发一次”LVB屏障。因为堆中引用的数量是有限的，单程的对象标记（single pass）和单程的引用重映射可以保证使用单程前进（straight forward manner）的方式（译者注：单程应该指的是不用回溯）。

自我修复仅仅在LVB代码路径中启用，发生在引用加载操作中，并且在所有实际使用该引用值以及传播（指将该引用值赋值给其他变量）该引用值之前。这种近似于引用加载操作的语法赋予了LVB访问引用值源地址的权利，这也是执行修复操作的必要权限。通过自我修复操作，LVB大程度的减少了读屏障被触发的次数，使得LVB更加高效和可预测。

2.3 引用元数据和NMT状态

和其他单代无停顿垃圾收集算法类似，C4算法追踪了堆中对象引用的元数据的“Not Marked Through(NMT)”状态。在现代64位的硬件中，这些元数据是一些表示对象引用的数据比特位，它表示LVB，而不是内存地址。具有NMT状态的且状态和期望的NMT值不匹配（不一致）的对象引用将会触发LVB读屏障。

C4使用的NMT状态和其他无停顿垃圾收集算法不太一样，其他的垃圾收集算法维护了一个全局、单一的NMT状态期望值，而C4垃圾收集算法为不同代维护了不同的期望值。另外，C4使用引用元数据追踪了引用的代信息（generation）。这也使得LVB能够高效的校验指定代的NMT值是否正确。因为年轻代和老年代垃圾回收可以互相独立的进行，它们期望的NMT状态也就经常是不一样的。在C4垃圾收集器中，一个引用的代在该引用指向的值没有被重定位过（relocated）时，是不会发生变化的。

如果在一个标记阶段，LVB发现已经被加载过的对象引用和NMT不一致时，也就是当前值和该引用目标代的期望值不一致，那么LVB会修复该NMT状态为期望值，并且会将该应用记录到收集器的工作列表中，以此确保该引用可以被收集器安全的遍历。通过自我修复，加载该引用值的源内存地址也会被同时修复。

2.4 页保护和并发重定位

C4和其他垃圾收集器使用同样的页保护策略。在压缩内存空间（译者注：指将垃圾收集剩下的对象重定位到一起减少内存碎片时）页会被标记为受保护状态，LVB也会在遇到加载该引用的地址被标记为保护状态时被触发。为了恢复触发过程，LVB首先会获取引用值的新位置（译者注：指重定位后的新位置），然后修复引用值，在修复该引用值源内存地址上的值。当LVB触发但是重定位还没有完成时，LVB会首先协助进行重定位操作，然后修改引用值为其新位置。

2.5 快速释放（Release)

to be continued