垃圾回收顾名思义，就是回收不再使用的对象和内存空间。大家也许常常听到一些和垃圾回收相关的名词，比方说STW(stop the world)。即垃圾收集器的暂停程序，用于暂停运行的程序，让垃圾回收器扫描不再使用的内存空间，当他结束后，应用程序才会继续运行。而说到最常见的垃圾回收算法，有标记清除(Mark&Sweep)和引用计数(Reference&Count)。在go中使用了标记清除的算法，并在此基础之上使用了三色标记法(白、灰、黑)和写屏障的技术。

标记清除

从标记清楚的字面意思来看，垃圾回收分为两个阶段，即: 标记(Mark)、清除(Sweep)。

  • 标记：从根对象开始出发查找并标记堆中所有存活的对象。
  • 清除：遍历堆中所有的对象，回收未被标记的垃圾对象，并将回收的内存放入空闲链表。

而在我们使用标记清除算法的时候，往往需要STW，同步暂停程序的运行，标记阶段结束后，才会进入清除阶段，清除时会遍历堆中所有的对象。为了减少了STW的时间，于是golang采用了异步标记的模式，即三色标记法。

三色标记法

三色标记法，将不同的对象分成了3个颜色：

  • 白色：潜在垃圾，可能会被回收。
  • 灰色：活跃对象，包括从根对象可达的对象以及不存在外部引用的对象。
  • 黑色：活跃对象。

当垃圾收集器开始工作时，先将所有的对象标记为白色，这一步需要STW。然后将所有根对象标记为灰色，放入集合中。 而三色标记法的步骤简单描述如下：

  1. 从灰色对象的集合中选择一个对象标记为黑色。
  2. 将黑色对象所有可达的对象标记为灰色，保证该对象和被该对象引用的对象都不会被回收。
  3. 重复上述两步，直到内存中没有灰色对象。

在完成上述步骤之后，堆中就只有黑色的活跃对象和白色的潜在垃圾对象，白色对象用于垃圾收集器的回收。 因为这个过程是异步的，所以在并发执行的过程当中一定会遇到对象指针发生改变的问题，即:

A(黑色) → B(灰色) → C(白色)

A(黑色) → B(灰色) → C(白色)
  ↓
D(白色)

从上面可以看出，本来不应该回收的，却被回收了。为了避免这一点，go于是引入了屏障技术。

屏障技术

内存屏障技术是一种指令，在用户程序读取、创建、更新对象的时候执行的一个指令，类似一个hook。为了保证并发或增量条件下标记算法的准确性，我们需要达成两种三色不变性:

  1. 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或黑色对象。
  2. 弱三色不变性：黑色对象指向的白色对象必须包含一条灰色对象经由多个白色对象的可达路径。
# 强三色不变性

A(黑色) → B(灰色) → C(白色)
            ↓
          D(白色)

E(黑色) → F(黑色)          

# 弱三色不变性

A(黑色) → B(灰色) → C(白色)
  ↓         ↓
D(白色) ← E(白色)

插入写屏障

伪代码:

writePointer(slot, ptr):
  shade(ptr)
  *slot = ptr

每当执行*slot=ptr时，都会先执行写屏障shade(ptr)。如果ptr是白色，则将改对象设置为灰色，其他情况不变。写屏障技术会将有存活可能的所有对象都标记为灰色，以满足强三色不变性。但这回有一点问题，如下:

A(黑色) → B(灰色)
            ↓
         C(白色)

A(黑色)  B(灰色)
    ↓       ↓
    →   C(灰色)

如上步骤可以看出，B并没有被回收。于是在Gov1.8的版本当中，引入了混合写屏障。

混合写屏障

伪代码:

writePointer(slot, ptr):
  shade(ptr)
  if current stack is grey:
    shade(ptr)
  *slot = ptr

混合写屏障会将被覆盖的对象标记为灰色，并在当前栈没有扫描时将新对象也标记为灰色。在垃圾收集标记的阶段，我们需要将创建的所有新对象都标记为黑色，防止新分配的栈内存和堆内存被错误的回收。

完整的GC过程

  1. 标记准备(Mark Setup, 需STW)， 打开写屏障。
  2. 使用三色标记法，并发去标记对象。Mark
  3. 标记结束(Mark Terminate, 需STW)，关闭写屏障。
  4. 清理(Sweeping, 并发)