一、引言

（一）垃圾回收 概述

垃圾回收（Garbage Collection，GC） 是Go语言的核心特性之一，是实现内存自动管理的一种形式。golang的自动垃圾回收屏蔽了复杂且容易出错的内存操作，让开发变得更加简单、高效。在Go语言中，从实现机制上来说，垃圾回收可能是最复杂的模块了。了解垃圾回收的机制，有助于更好地理解Go语言的内存管理机制，从而更好的使用Go语言进行开发。

（二）垃圾回收相关组件

使用自带垃圾回收特性的编程语言开发应用程序中，垃圾回收涉及到一下三个组件：

• Allocator-分配器：在堆上申请内存
• Mutator-赋值器：将Allocator申请到的内存对象赋值给栈上的变量（或全局变量）。
• Collector-回收器：回收不再活跃的内存对象。

二、标记-清除 算法

Go语言使用标记-清除（Mark-Sweep）算法来进行内存垃圾回收。（关于其他经典的垃圾回收算法，参考本文<相关知识>一节。Mark-Sweep算法执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

• Mark阶段： 从根对象开始，对内存对象进行图遍历，对所有可达的对象进行标记。
• Sweep阶段： 对Mark阶段未被标记的内存对象进行回收，回收完毕后重置所有内存对象的标记以便下一轮‘标记-清除’。

什么是根对象？

★根对象主要是指应用程序中通过变量可以直接访问的对象。 ”

如图所示，假设应用程序在堆上申请了A-J共10个内存对象。其中可以被程序中的变量直接访问的只有对象A和B（分别被变量a、b直接访问），因此根对象只有A和B。其他内存对象都是间接访问，不是根对象。

a = &A
b = &B
a.f1 : &C
a.f2 : &D
a.f1.f1 : &F
a.f1.f2 : &G
a.f1.f3 : &H
b.f1 : &E
b.f1.f1 : &I
// 其他为列出的成员字段的值均为空

Untitled

图中因为所有的对象都可以通过根对象访问到，因此没有内存对象要回收。

如果应用程序之后将对象C成员对H的引用去除，a.f1.f3 = nil,

此时H对象变为从根对象不可达的待回收对象。

• Stage-1. 在标记阶段， 从根对象开始进行图遍历（深度优先/广度优先），将可达对象设置标记（用黑色标记）。 标记阶段完成后，对象H仍然为白色，未被标记。

• Stage-2.在清扫阶段： 遍历所有内存对象，对未被标记的对象H进行回收。

以上 就是'标记-清除'算法的主要过程。

三、三色标记法

（一）原始<标记-清除>算法的不足

原始的Mark-Sweep算法流程上相对简单，但是在实际应用中有一定的限制条件。在垃圾回收的整个过程中，如果应用程序并发进行内存相关操作，可能导致活跃对象被错误回收。

如上图所示，在标记阶段根对象A做DFS遍历完成后，Mutator并发修改了对内存对象D的引用关系（增加了A对象对D对象的引用，删除了B对象对D对象的引用），然后Collector在对根对象B做DFS遍历。最终导致的结果是，从根对象A可以到达对象D（即D是活跃的），但是标记结果显示对象D是可以被回收的内存对象，从而错误释放了对象D的内存。

在原始<标记-清除>算法中，要保证活跃对象不被被错误回收，需要满足以下必要条件：活跃白色对象必须从白色的根对象可达。这个条件在并发和增量执行的过程中其实是很难保证的，因而：原始的Mark-Sweep算法会在垃圾回收阶段Stop-The-World，不支持并发和增量执行

Go语言使用三色标记法和屏障技术来支持并发和增量执行。

（二）三色标记法

三色标记算法将所有的内存对象抽象为黑、白、灰三类。

• 白色： 初始色，如果标记阶段结束还是白色，则该内存对象将被回收。
• 灰色： 活跃的对象，存在于标记阶段中间状态，自身及其下游需要被进一步扫描、标记。所有的根对象在标记开始时被全部置为灰色。
• 黑色： 活跃的对象，已被标记完成，不会再通过该对象对其下游对象扫描标记。

三色标记法的基本过程

1. 垃圾回收开始前，所有的内存对象都是白色；
2. 垃圾回收开始时，所有根对象被标记会灰色；
3. 从灰色对象集合，选取一个灰色对象，将其下游白色对象置灰，将自己置为黑色；
4. 重复第3步骤，直至灰色对象集合为空。

三色标记法只能由白->灰->黑单调变色

用三色波面图来描述：

三色标记法本身仍然不能保证并发和增量执行的正确性。在并发和增量执行的场景下，

活跃对象（白色）被错误回收的必要条件：

1. 不存在从灰色对象到达该白色对象的路径。（该白色对象在标记阶段不会再被扫描到）
2. 存在从黑色对象到达该白色对象的路径。（否则结合1的话，该白色对象本来就是一个需要被回收的垃圾对象）

但是三色标记法让并发和增量执行的实现变得容易。回到<标记-清除>中的异常例子。

因为活跃对象（白色）被错误回收的两个条件都是必要条件，要保证活跃对象都被发现，我们可以两个条件都破坏，也可以只破坏一个条件。由此，就衍生了两种三色不变性：

• 强三色不变性：不存在黑色对象对白色对象的直接引用。（隐含了一层意思：如果该对象是活跃对象，那么必然存在从灰色对象到该对象的路径）。强三色不变性破坏了两个必要条件。
• 弱三色不变性：被黑色对象直接引用的白色对象，必须要能够通过一些灰色对象可达。破坏了"不存在从灰色对象到达该白色对象的路径。"这个必要条件。

Go语言的三色不变性通过引入屏障技术来实现。

标记-清除>算法和<三色标记法> 本身都不能保证在并发和增量执行的场景下垃圾回收的正确性，那么引入<三色标记法>的优势是什么，我们还需要结合屏障技术来看。（参考插入写屏障最后的对比）

四、屏障技术

内存屏障技术是一种CPU屏障指令，用于让CPU和编译器对屏障指令前后的内存操作的执行顺序进行强制约束。现在处理器为了优化性能，经常会改变程序指令的执行顺序，而内存屏障技术则是用来对一些内存操作的执行顺序进行强制约束。内存屏障指令前的内存操作一定会在内存屏障指令后的操作之前执行。

内存屏障技术本身并不能用来保证三色不变性。但是我们可以利用内存屏障技术在内存操作之前执行特定的（用于保护三色不变性）的指令（执行特定代码）（就像Hook一样）。

（一）哪些内存操作适合启用写屏障

我们可以吧内存操作分为以下几种：

1. 堆对象的读：
2. 堆对象的写：
3. 栈对象的读：
4. 栈对象的写：

所有对象的读对性能都有比较高的性能要求；栈对象的读写一方面对性能要求高，一方面栈对象启用写屏障的实现难度较大。因而在Go语言语境下，只对堆对象的写启用写屏障。

（二）插入写屏障

插入写屏障由Dijkstra 1978 年在《An exercise in cooperation. Communications of the ACM, 21(11), 966–975, 1978.》提出，可以用来保证内存对象的强三色不变性。

★插入写屏障的基本含义：当Mutator在增加一个内存对象A到另一个内存对象B的指向时（在有向图中增加A->B这条边），引入内存屏障，将内存对象B置灰。 ”

插入写屏障可以用下面的伪代码表示：

// DijkstraWritePointer : 插入写屏障
// @param slot ： 上游对象中用来指向下游对象的插槽，比如c.f1=&d, 则slog为&c.f1
// @param ptr  ： 下游对象的地址，
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)   // 着色，置灰
    *slot = ptr  // 让slot对应的上游对象中增加对ptr对应的下游对象的引用。
}

我们看下插入写屏障如何保证强三色不变性：

先假设栈对象也开启了写屏障

仍然以前面的例子来说明：

当插入C->D这条边时，触发插入写屏障。

用伪代码描述的话，大概是这样子：没有插入写屏障时，Mutator原本增加C->D:

    c.f1 = &d

引入插入写屏障后,

    DijkstraWritePointer(&c.f1, &d)

插入写屏障因为在新增对象引用时，直接把被引用的对象置灰；因此不会存在黑色对象直接指向白色对象的情况，而且被应用对象及其下游对象通过灰色对象必然可达（因为被引用本身就是灰色对象）

再引入栈对象不启用写屏障这一限制条件：

对于插入写屏障算法来说，如果栈对象不开启插入写屏障，在回收过程中，如果把一个对象插入到栈对象（黑色）的下游，则可能不会被发现，最终导致被错误回收。

如图，增加A->B,A->D两条边的时候都不会触发插入写屏障

Go语言早期的做法是，标记阶段结束后，STW，重新扫描一遍栈对象（此处STW占用大概10ms-100ms）。对于栈空间STW期间的扫描标记，只需要将被栈对象直接引用的堆空间对象直接置黑（不需要置灰），因为其下游子对象是通过写屏障处理的。

对比三色标记和原始的标记清除算法

在原始的<标记-清除>算法中，使用新增黑色对象对白色对象的引用时，将白色对象置为黑色（需要先递归处理白色对象的下游），也能避免活跃内存对象被错误回收。

（三）删除写屏障

删除写屏障有Yuasa 在 1990 年的论文 Real-time garbage collection on general-purpose machines提出。

★删除写屏障的基本含义：当Mutator在删除一个内存对象A到另一个内存对象B的指向时（在有向图中删除A->B这条边），引入内存屏障，将内存对象B置灰。 ”

插入写屏障可以用下面的伪代码表示：

// YuasaWritePointer : 删除写屏障
// @param slot ： 上游对象中用来指向下游对象的插槽，比如a.f1=&d, 则slog为&a.f1
// @param ptr  ： 下游对象的地址，比如a.f1=&d, 则ptr为&d. ptr 可能为nil
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) // 着色，把插槽原来指向的对象置灰（注意这里是*slot，不是slot）
    *slot = ptr  // 插槽指向新的对象，也可能指向nil
}

我们看下删除写屏障如何保证弱三色不变性：

先假设栈对象也开启了写屏障

仍然以前面的例子来说明：

当删除B->D这条边时，触发删除写屏障。

用伪代码描述的话，大概是这样子：没有删除写屏障时，Mutator原本删除B->D:

    b.f1 = nil

引入删除写屏障后,

    YuasaWritePointer(&b.f1, nil)

删除写屏障因为在删除对象引用关系时，将原来的被引用对象置灰，即直接创造了一条到达被引用对象（包括其下游对象）的路径，因而破坏了'不存在从灰色对象到达该白色对象的路径。'这个条件。实现了弱三色不变性。

再引入栈对象不启用写屏障这一限制条件：

对于删除写屏障算法来说，如果栈对象不开启插入写屏障，在回收过程中，如果把一个对象从栈对象直接下游移动到其他对象（黑色对象）直接下游，则可能不会被发现，最终导致被错误回收。

上图中，因为C属于栈对象，因此在删除C->D时，不会触发删除写屏障。为了解决这个问题，要求删除写屏障扫描栈对象必须STW。删除写屏障在栈扫描时的STW必须是全局的，我们可以结合具体的场景来分析：STW主要是为了规避两种场景的错误回收：

1. 将堆对象从一个栈对象下游移动到一个黑色的栈对象下游。
2. 将堆对象从一个栈对象下游移动到一个黑色堆对象下游。

第一种场景只会在一个goroutine下出现（goroutine有独立栈） 第二种场景可以发生不同goroutine。

只在goroutine维度STW无法保证第二种场景垃圾回收能正确回收。

（四）混合写屏障

插入写屏障和删除写屏障针对栈对象不开启写屏障的限制条件都有了解决方案，都能够满足三色不变性。但是他们也有各自的短板：

• 插入写屏障：需要两次STW。
• 删除写屏障：GC开始时需要一次STW（全局所有goroutine）， 回收精度较低。

引入混合写屏障的设计目标，主要是要补齐插入/删除写屏障中的STW短板。其设计思想是：在删除写屏障的基础上，引入插入写屏障，从而实现删除写屏障的全局STW进化为goroutine维度的STW。（但是Go语言的演进是从插入写屏障->混合写屏障，很多网上文章的描述反而不好理解）

// 混合写屏障伪代码
func HybridWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
 shade(*slot) // 删除写屏障
 shade(ptr)   // 插入写屏障
 *slot = ptr
}

在删除写屏障中，我们已经列举了需要STW进行栈扫描的场景。

1. 将堆对象从一个栈对象下游移动到一个黑色的栈对象下游。
2. 将堆对象从一个栈对象下游移动到一个黑色堆对象下游。

第一种场景是在同一个goroutine进行的， 第二种场景，因为是将栈对象下游移动到黑色的堆对象下游，如果我们对堆对象开启插入写屏障，就可以保证对象不被错误回收。从而实现了在混合写屏障下，只需要做goroutine的STW。

五、相关知识

五种经典的垃圾回收算法

Go语言底层原理剖析中介绍了五种经典的垃圾回收算法。1. 标记-清除： 两阶段，第一阶段标记存活的内存对象，第二阶段清扫未被标记的对象。2. 标记-压缩： 通过将分散的、活着的对象移动到更紧密的空间来解决内存碎片问题。也是两阶段，第一阶段扫描存活的内存对象，并将其压缩到空闲的区域，3. 半空间复制： '标记-压缩'的演化版本，保留一半空间用于压缩，通过空间换时间，牺牲一半内存空间换取压缩的效率提升。4. 引用计数： 每个对象都包含一个引用计数，每当其他对象引用了此对象时，引用计数就会增加。每个对象都包含一个引用计数，每当其他对象引用了此对象时，引用计数就会增加。5. 分代GC： 将对象按照存活时间进行划分。优先回收刚创建不久的对象。

六、参考文献

1. 《Go语言底层原理剖析》第19、20章
2. Go 语言设计与实现--7.2 垃圾收集器
3. Mark-and-Sweep: Garbage Collection Algorithm
4. Tri-color marking
5. Barrier techniques for incremental tracing
6. wikipedia:
7. On-the-fly garbage collection: an exercise in cooperation.
8. Real-time garbage collection on general-purpose machines
9. Golang三色标记+混合写屏障GC模式全分析
10. golang 垃圾回收（五）混合写屏障