Golang-GC Tri-Color Marking

引言：

• Go语言的一大特点就是其提供的垃圾回收机制，对于我这样的没有用过C++的初学者而言，简直是一个福音。

• 那么Go语言中的垃圾回收到底是怎么实现的呢？

  • 答：标记-清除。

• 相比于JVM中各种眼花缭乱的垃圾回收器和多种垃圾回收机制，Go提供的就是标记-清除型的GC。

• 其中，标记采用的是三色标记法，这种方法也用在了JVM的CMS，G1的等垃圾回收器中。

三色标记法 - 基本逻辑

实际上，三色标记法就是用三种颜色来标记对象在可达性分析过程中的状态。按照我的理解，就是对存在于GCRoot中的对象进行BFS遍历。

我们都知道在使用BFS的时候，需要用一个队列来模拟遍历过程。因此就有了三种颜色所表示的意义：

1. 黑色 - 已经从队列中poll出来了对象
2. 灰色 - 目前正在队列中的对象
3. 白色 - 还没有进过队列的对象

整个三色标记的过程如下：

1. 所有对象初始均为白色
2. 从GCRoot开始，用BFS遍历对象，进入队列即标记为灰色。
3. 将灰色对象所引用的对象加入队列，弹出所有灰色对象并标记为黑色。进入队列的标为灰色。
4. 一直遍历直到没有新的对象能够加入队列。
5. 剩余的所有白色对象就是不可达的对象，GC会移除这些对象。

GolangGC中的一些实现细节 - hybrid write barrier

根据上述的有关三色标记法的基本逻辑，其实不难发现整个过程是必须要STW的。然而JVM中的GC早都实现了并发标记的功能了，Golang岂能不用并发标记？

然而，使用并发标记，势必会在某些情况下出现问题，比如回收了合法的对象。总结来说，当以下两个条件同时被满足时，就会出现问题。

1. 黑色对象持有白色对象的引用
2. 另一个灰色对象也拥有这个白色对象的引用，但是这个引用被删除了。

为了避免这两个条件被同时满足，Golang在v1.5版本设置了插入屏障和删除屏障。

插入屏障：把一个新的对象挂在某个对象下，直接标记这个新对象为灰色。

删除屏障：如果要删除一个对象的引用，如果这个对象是白色的就被标记为灰色。

插入写屏障和删除写屏障的短板：

• 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；

• 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。

混合写屏障规则

1. GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
2. GC期间，任何在栈上创建的新对象，均为黑色。
3. 被删除的对象标记为灰色。
4. 被添加的对象标记为灰色。