Garbage Collector

, ,

在几乎所有的现代编程语言中，垃圾收集器都是一个复杂的系统，为了在不影响用户程序的情况下回收废弃的内存需要付出非常多的努力，Java 的垃圾收集机制是一个很好的例子，Java 8 中包含线性、并发、并行标记清除和 G1 四个垃圾收集器，想要理解它们的工作原理和实现细节需要花费很多的精力。

本文介绍 Go 语言运行时系统中垃圾收集器的设计与实现原理，讨论常见的垃圾收集机制、从 Go 语言的 v1.0 版本开始分析其演进过程，还会深入源代码分析垃圾收集器的工作原理。

设计原理

今天的编程语言通常会使用手动和自动两种方式管理内存，C、C++ 以及 Rust 等编程语言使用手动的方式管理内存，工程师需要主动申请或者释放内存；Objective-C 选择了自动引用计数，是一种自动的内存管理机制；而 Python、Ruby、Java 和 Go 等语言使用自动的内存管理系统，一般都是垃圾收集机制，程序员只需要负责申请内存，垃圾回收器会周期性释放结束生命周期的变量所占用的内存空间。

垃圾回收器主要包括三个目标：

  • 无内存泄漏：垃圾回收器最基本的目标就是减少防止程序员未及时释放导致的内存泄漏，垃圾回收器会识别并清理内存中的垃圾
  • 自动回收无用内存：垃圾回收器作为独立的子任务，不需要程序员显式调用即可自动清理内存垃圾
  • 内存整理：如果只是简单回收无用内存，那么堆上的内存空间会存在较多碎片而无法满足分配较大对象的需求，因此垃圾回收器需要重整内存空间，提高内存利用率

用户程序Mutator通过内存分配器Allocator在堆Heap上申请内存，垃圾回收器Collector会定时清理堆上的内存。内存分配器和垃圾收集器共同管理着程序中的堆内存空间。

常见的GC算法

根据判断对象是否存活的方法，可以简单将GC算法分为“引用计数式”垃圾回收和“追踪回收式”垃圾回收。前者根据每个对象的引用计数器是否为0来判断该对象是否为未引用的垃圾对象，后者先判断哪些对象存活，然后将其余的所有对象作为垃圾进行回收。追踪回收本身包括标记-清除Mark-Sweep、标记-复制Mark-Copy和标记-整理Mark-Compact三种回收算法。

引用计数

引用计数Reference counting会为每个对象维护一个计数器，当该对象被其他对象引用时加一，引用失效时减一，当引用次数归零后即可回收对象。使用这类GC方法的语言包括python、php、objective-C和C++标准库中的std::shared_ptr等。

以python为例，python中的每个对象都包含如下结构：

1
2
3
4
typedef struct_object {
    int ob_refcnt;
    struct_typeobject *ob_type;
}PyObject;

其中ob_refcnt为引用计数器，当一个对象有新的引用时计数器增一，当引用它的对象被删除时计数器减一。

引用计数法优点包括：

  • 原理和实现都比较简单
  • 回收的即时性：当对象的引用计数为0时立即回收，不像其他GC机制需要等待特定时机再回收，提高了内存的利用率
  • 不需要暂停应用即可完成回收

缺点包括：

  • 无法解决循环引用的回收问题：当ObjA引用了ObjB，ObjB也引用ObjA时，这两个对象的引用次数使用大于0，从而占用的内存无法被回收
  • 时间和空间成本较高：一方面是因为每个对象需要额外的空间存储引用计数器变量，另一方面是在栈上的赋值时修改引用次数时间成本较高（原本只需要修改寄存器中的值，现在计数器需要不断更新因此不是只读的，需要额外的原子操作来保证线程安全）
  • 引用计数是一种摊销算法，会将内存的回收分摊到整个程序的运行过程，但是当销毁一个很大的树形结构时无法保证响应时间

跟踪式算法

可达性分析算法

追踪式垃圾回收算法实现起来各不相同，但是第一步都是通过可达性分析算法标记Mark对象是否“可达”。一般可到达的对象主要包括两类：

  • GC Root对象：包括全局对象、栈上的对象（函数参数与内部变量）
  • 与GC Root对象通过引用链Reference Chain相连的对象

对于“不可达”的对象，可以认为该对象为垃圾对象并回收对应的内存空间。

内存空间中包含多个对象，从根对象出发依次遍历对象的子对象并将从根节点可达的对象都标记成存活状态，即 Object1,2,3,4四个对象，剩余的Object5,6,7三个对象因为从根节点不可达，所以会被当做垃圾。

强引用、软引用、弱引用和虚引用

JDK1.2之后，Java对引用的概念进行了扩充，将引用分为强引用（Strong Reference）、软引用（Soft Reference）、弱引用（Weak Reference）、虚引用（Phantom Reference）4种。

JDK1.2之前，只有被引用和没有被引用两种状态

  • 强引用：指在程序代码之中普遍存在的，类似Object obj = new Object()这类的引用，只要强引用还存在，垃圾收集器永远不会回收被引用的对象
  • 软引用：用来描述一些还有用但并非必需的对象。对于软引用关联着的对象，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中进行第二次回收。如果这次回收还没有足够的内存，才会抛出内存溢出异常。在JDK1.2之后，提供了SoftReference类来实现软引用
  • 弱引用：用来描述非必需对象，但是他的强度比软引用更弱一些，被弱引用关联的对象只能生存到下一次垃圾收集之前。当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。在JDK1.2之后，提供了WeakReference类来实现弱引用
  • 虚引用：也被称为幽灵引用或者幻影引用。它是最弱的一种引用关系。一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。在JDK1.2之后，提供了PhantomReference类来实现虚引用。供对象被finalize之后，执行指定的逻辑的机制（cleaner)
引用类型 回收机制 用途 生存周期
强引用 从不回收 对象的一般状态 JVM停止运行时
软引用 内存不足时 对象缓存 内存不足时终止
弱引用 正常垃圾回收时 对象缓存 垃圾回收后中止
虚引用 正常垃圾回收时 跟踪对象的垃圾回收 垃圾回收后中止

追踪式算法优缺点

同引用计数法相比，追踪式算法具有如下优点：

  • 解决了循环引用对象的回收问题
  • 占用空间更少

缺点包括：

  • 同引用计数相比无法立刻识别出垃圾对象，需要依赖GC线程
  • 算法在标记时必须暂停整个程序，即Stop The World, STW，否则其他线程的代码会修改对象状态从而回收不该回收的对象

Mark-Sweep

标记清除收集器是跟踪式垃圾收集器，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

  • 标记阶段 — 从根对象出发查找并标记堆中所有存活的对象；
  • 清除阶段 — 遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；

标记阶段结束后会进入清除阶段，在该阶段中收集器会依次遍历堆中的所有对象，释放其中没有被标记的Object5,6,7 三个对象并将新的空闲内存空间以链表的结构串联起来，方便内存分配器的使用。

这是最传统的标记清除算法，垃圾收集器从垃圾收集的根对象出发，递归遍历这些对象指向的子对象并将所有可达的对象标记成存活；标记阶段结束后，垃圾收集器会依次遍历堆中的对象并清除其中的垃圾，整个过程需要标记对象的存活状态，用户程序在垃圾收集的过程中也不能执行，需要用到更复杂的机制来解决 STW 的问题。

标记清除算法的一个典型耗时是在标记期间，需要暂停程序（Stop the world，STW），标记结束之后，用户程序才可以继续执行。

优点包括：

  • 算法吞吐量较高，即运行用户代码时间 / （运行用户代码时间 + 运行垃圾收集时间）较高
  • 空间利用率高：同标记-复制相比不需要额外空间复制对象，也不需要像引用计数算法为每个对象设置引用计数器

缺点包括：

  • 清除后会产生大量的内存碎片空间，导致程序在运行时可能没法为较大的对象分配内存空间，导致提前进行下一次垃圾回收

Mark-Copy

标记-复制Mark-Copy算法将内存分成大小相同的两块，当某一块的内存使用完了之后就将使用中的对象挨个复制到另一块内存中，最后将当前内存恢复未使用的状态。

优点包括：

  • 标记-清除法需要在清除阶段对大量垃圾对象进行扫描，标记-复制则只需要从GC Root对象出发，将“可到达”的对象复制到另一块内存后直接清理当前这块的内存，因此提升了垃圾回收的效率
  • 解决了内存碎片化的问题，防止分配较大连续空间时的提前GC问题

缺点包括：

  • 同标记-清除法相比，在“可达”对象占比较高的情况下有复制对象的开销
  • 内存利用率较低，相当于可利用的内存仅有一半

Mark-Compact

标记-整理Mark-Compact算法综合了标记-清除法和标记-复制法的优势，既不会产生内存碎片化的问题，也不会有一半内存空间浪费的问题。该方法首先标记出所有“可达”的对象，然后将存活的对象移动到内存空间的一端，最后清理掉端边界以外的内存。

优点包括：

  • 避免了内存碎片化的问题
  • 在对象存活率较高的情况下，标记-整理算法由于不需要复制对象效率更高，因此更加适合老年代算法

缺点包括：

  • 整理过程较为复杂，需要多次遍历内存导致STW时间比标记-清除算法更长

三色抽象

为了解决原始标记清除算法带来的长时间 STW，多数现代的追踪式垃圾收集器都会实现三色标记算法的变种以缩短 STW 的时间。三色标记算法将程序中的对象分成白色、黑色和灰色三类：

  • 白色对象 — 默认值。本次回收没被扫描过的对象都是白色的。确认不可达的对象也是白色，但是会被标记「不可达」。暂无对象引用的潜在垃圾，其内存可能会被垃圾收集器回收；
  • 黑色对象 — 本对象有被其它对象引用，且已检测完本对象引用的其它对象。活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
  • 灰色对象 — 中间状态。本对象有被外部引用，但是本对象引用的其它对象尚未全部检测完。活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

在垃圾收集器开始工作时，程序中不存在任何的黑色对象，垃圾收集的根对象会被标记成灰色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束。

标记过程如下：

  1. 起初所有的对象都是白色的；

  2. 从根对象出发扫描所有可达对象，标记为灰色，放入待处理队列；

  3. 从待处理队列中取出灰色对象，将其引用的对象标记为灰色并放入待处理队列中，自身标记为黑色；

  4. 重复步骤3，直到待处理队列为空，此时白色对象即为不可达的“垃圾”，回收白色对象；

根对象在垃圾回收的术语中又叫做根集合，它是垃圾回收器在标记过程时最先检查的对象，包括：

  1. 全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量。
  2. 执行栈：每个 goroutine 都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
  3. 寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存区块。

因为用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW，在如下所示的三色标记过程中，用户程序建立了从 A 对象到 D 对象的引用，但是因为程序中已经不存在灰色对象了，所以 D 对象会被垃圾收集器错误地回收。

本来不应该被回收的对象却被回收了，这在内存管理中是非常严重的错误，我们将这种错误称为悬挂指针(dangling pointer)，即指针没有指向特定类型的合法对象，影响了内存的安全性，想要并发或者增量地标记对象还是需要使用屏障技术。

屏障技术

内存屏障技术Memory barrier是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的一种：

  • 强三色不变性 — 黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；
  • 弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径

上图分别展示了遵循强三色不变性和弱三色不变性的堆内存，遵循上述两个不变性中的任意一个，我们都能保证垃圾收集算法的正确性，而屏障技术就是在并发或者增量标记过程中保证三色不变性的重要技术。

垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

在这里想要介绍的是 Go 语言中使用的两种写屏障技术，分别是 Dijkstra 提出的插入写屏障和 Yuasa 提出的删除写屏障，这里会分析它们如何保证三色不变性和垃圾收集器的正确性。

插入写屏障

Dijkstra 在 1978 年提出了插入写屏障，通过如下所示的写屏障，用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性：

1
2
3
writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

上述插入写屏障的伪代码非常好理解，每当执行类似 *slot = ptr 的表达式时，会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色，其他情况则保持不变。

假设我们在应用程序中使用 Dijkstra 提出的插入写屏障，在一个垃圾收集器和用户程序交替运行的场景中会出现如上图所示的标记过程：

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色；
  2. 用户程序修改 A 对象的指针，将原本指向 B 对象的指针指向 C 对象，这时触发写屏障将 C 对象标记成灰色；
  3. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色；

Dijkstra 的插入写屏障是一种相对保守的屏障技术，它会将有存活可能的对象都标记成灰色以满足强三色不变性。在如上所示的垃圾收集过程中，实际上不再存活的 B 对象最后没有被回收；而如果我们在第二和第三步之间将指向 C 对象的指针改回指向 B，垃圾收集器仍然认为 C 对象是存活的，这些被错误标记的垃圾对象只有在下一个循环才会被回收。

插入式的 Dijkstra 写屏障虽然实现非常简单并且也能保证强三色不变性，但是它也有明显的缺点。因为栈上的对象在垃圾收集中也会被认为是根对象，所以为了保证内存的安全，Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描，这两种方法各有各的缺点，前者会大幅度增加写入指针的额外开销，后者重新扫描栈对象时需要暂停程序，垃圾收集算法的设计者需要在这两者之间做出权衡。

删除写屏障

Yuasa 在 1990 年的论文 Real-time garbage collection on general-purpose machines 中提出了删除写屏障，因为一旦该写屏障开始工作，它会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）

This guarantees that no objects will become unreachable to the garbage collector traversal all objects which are live at the beginning of garbage collection will be reached even if the pointers to them are overwritten.

该算法会使用如下所示的写屏障保证增量或者并发执行垃圾收集时程序的正确性：

1
2
3
writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时，将白色的老对象涂成灰色，这样删除写屏障就可以保证弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用。

假设我们在应用程序中使用 Yuasa 提出的删除写屏障，在一个垃圾收集器和用户程序交替运行的场景中会出现如上图所示的标记过程：

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色；
  2. 用户程序将 A 对象原本指向 B 的指针指向 C，触发删除写屏障，但是因为 B 对象已经是灰色的，所以不做改变；
  3. 用户程序将 B 对象原本指向 C 的指针删除，触发删除写屏障，白色的 C 对象被涂成灰色；
  4. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色；

上述过程中的第三步触发了 Yuasa 删除写屏障的着色，因为用户程序删除了 B 指向 C 对象的指针，所以 C 和 D 两个对象会分别违反强三色不变性和弱三色不变性：

  • 强三色不变性 — 黑色的 A 对象直接指向白色的 C 对象；
  • 弱三色不变性 — 垃圾收集器无法从某个灰色对象出发，经过几个连续的白色对象访问白色的 C 和 D 两个对象；

Yuasa 删除写屏障通过对 C 对象的着色，保证了 C 对象和下游的 D 对象能够在这一次垃圾收集的循环中存活，避免发生悬挂指针以保证用户程序的正确性。

Go 语言的垃圾收集器演进过程

Go 语言的垃圾收集器从诞生的第一天起就一直在演进，除了少数几个版本没有大更新之外，几乎每次发布的小版本都会提升垃圾收集的性能，而与性能一同提升的还有垃圾收集器代码的复杂度，本文章将从 Go 语言 v1.0 版本开始分析垃圾收集器的演进过程。

  1. v1.0 — 完全串行的标记和清除过程，需要暂停整个程序；
  2. v1.1 — 在多核主机并行执行垃圾收集的标记和清除阶段；
  3. v1.3 — 运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持，实现了真正精确的垃圾收集Go 1.3 Release Notes - The Go Programming Language；
    • 将 unsafe.Pointer 类型转换成整数类型的值认定为不合法的，可能会造成悬挂指针等严重问题；
  4. v1.5 — 实现了基于三色标记清扫的并发垃圾收集器Go 1.5 concurrent garbage collector pacing；
    • 大幅度降低垃圾收集的延迟从几百 ms 降低至 10ms 以下；
    • 计算垃圾收集启动的合适时间并通过并发加速垃圾收集的过程；
  5. v1.6 — 实现了去中心化的垃圾收集协调器；
  6. v1.7 — 通过并行栈收缩将垃圾收集的时间缩短至 2ms 以内；
  7. v1.8 — 使用混合写屏障将垃圾收集的时间缩短至 0.5ms 以内Proposal: Eliminate STW stack re-scanning；
  8. v1.9 — 彻底移除暂停程序的重新扫描栈的过程；
  9. v1.10 — 更新了垃圾收集调频器（Pacer）的实现，分离软硬堆大小的目标Proposal: Separate soft and hard heap size goal；
  10. v1.12 — 使用新的标记终止算法简化垃圾收集器的几个阶段Proposal: Simplify mark termination and eliminate mark 2；
  11. v1.13 — 通过新的 Scavenger 解决瞬时内存占用过高的应用程序向操作系统归还内存的问题Proposal: Smarter Scavenging；
  12. v1.14 — 使用全新的页分配器优化内存分配的速度Proposal: Scaling the Go page allocator；

我们从 Go 语言垃圾收集器的演进能够看到该组件的实现和算法变得越来越复杂，最开始的垃圾收集器还是不精确的单线程 STW 收集器，最新版本的垃圾收集器却支持并发垃圾收集、去中心化协调等特性。

reference

https://zhuanlan.zhihu.com/p/297177002

GC 的认识 - 9. 什么是写屏障、混合写屏障，如何实现？

Go 语言垃圾收集器的实现原理 | Go 语言设计与实现

Golang垃圾回收(GC)介绍 | Random walk to my blog

https://learnku.com/articles/59021