上期文章说了很多关于标记的概念、流程，而标记的具体实现今天就来聊一聊。

在了解标记之前我们需要了解三色抽象。在 Go 语言的 MarkSweep 算法中它会把对象分成三类：

  • 黑：已经扫描完毕，子节点也扫描完毕。(也就是在 mSpan 结构中的 gcmarkbits = 1，位于队列之外)
  • 灰：已经扫描完毕，但子节点未扫描完毕。(也就是子节点大概率是白色，在 mSpan 结构中的 gcmarkbits = 1，位于扫描队列 wbuf1 或 wbuf2 或者全局的 Globally unique work 之内)
  • 白：未扫描，collector 不知道任何相关信息。（也就是 gcmarkbits = 0，并且没有在任何队列中）

这里黑、白、灰，本质上是抽象的概念，在代码中不会找到某个对象，它是表示颜色的。

文字描述还是有点抽象，再来看看图：

三色标记基本流程 (1)

最开始有个 root，它是指全局变量或栈上的指针或栈上的对象，它们是整个 GC 扫描的起点 root。可以看出来整个 GC 的过程就是个简单的广度优先遍历算法流程。最开始扫描根对象的时候，会把这些根对象放在 gcWorkBuf 里面，并且把 gcmarkbits 置为 1，这时候就变成了灰色。

然后从 gcWorkBuf 里取出指针，把它们的子对象往队列中放。比如 A 的两个子节点的 gcmarkbits 都被置为了 1 并且进入了队列，也就意味着 A 应该从队列中出来，这时候就会变成黑色。

当 E 的对象被推入到队列中后，它的子对象 F 会变为灰色，E 会变成黑色。按照这个过程一直执行下去，直到所有对象都会被扫描到并且被标记为黑色。

三色标记基本流程

最后可以发现还有个 G 没有被标记到，这就之前说的语法不可达对象，也就是语法垃圾，它最终会被 sweeper 回收掉。

虽然三色标记流程看上去很简单只是一个广度优先算法，但其实它的 wbBuf 设计得很复杂，目的就是为了后期可以进行一定的优化。我们如果从头去实现一个三色标记算法，如果不考虑性能，其实只需要实现一个队列就可以了。

一些问题

虽然我们有了三色标记，但还是要注意一些问题：

  1. 三色标记要求在标记过程中的对象是不能丢失的。因为我们整个标记流程是和应用程序并发进行的。比如上面的例子，虽然在标记对象，但这些对象彼此之间的引用很有可能在标记过程中被并发应用所修改。
  2. Mark 阶段 mutator 的指向堆的指针修改需要被记录下来。一旦堆上的指针被修改，我们需要某种手段去记录，这里其实是在说要开启 write barrier。
  3. GC Mark 的 CPU 控制要努力做到 25% 以内。

这里有个非常具体的例子：

标记例子 (1)

图右边是应用程序代码，可以理解为每个对象都有 x 和 y 两个指针。图左边的 A 是黑色，说明已经标记完成了，并且已经在队列里面；而 BCDE 都是白色，说明都在队列外面。从黑色指向灰色，灰色指向白色，这是合法的情况。

现在在应用程序中标记并发地执行，原来的指针也发生了变化。从 A 产生了指向 B 的指针，C 的指针不再指向 B 而是指向 D。继续执行下去的话，后来会出现问题，为什么？

标记例子 (3)

队列中灰色的 C 被标记后会变为黑色，它的两个子对象会被存入队列中、子对象会变成位色。最终 D 和 E 会由灰色变为黑色。我们就会发现，B 对象在应用程序并发执行的时候居然丢失了，也就会被当作垃圾回收。而它其实不应该作为垃圾被回收，相当于有个对象的指针变为非法了，Go 语言中其实不应该发生这种情况的。

所以，这便是三色抽象问题，在标记过程中对象漏标，导致被意外回收的情况。

OK，下期文章继续从理论到实际来解决这个问题。