Golang 中的 GC 算法：三色标记与混合写屏障
标记清除法
在 v1.0~v1.3 版本中都是用的是标记清除算法。首先我们需要了解 STW（Stop The World）是什么，顾名思义，STW 是将当前程序完全暂停，不执行用户程序并开始垃圾回收。标记清除算法的流程如下：
- Stop the world；
- 标记：从根对象开始标记，将可达对象和不可达对象区分开；
- 清除：将不可达对象回收；
- 恢复用户程序的执行。
标记清除算法如此简单粗暴很明显有非常突出的性能问题，体现在
- STW 会导致程序卡顿，对程序相应带来不可接受的延时；
- 标记过程需要扫描整个堆空间；
- 清除数据会产生堆碎片，这里需要参照内存分配算法。
v1.0 是完全串行的标记清除算法，v1.1 实现了多核系统的并行垃圾收集和标记，v1.3 运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持，实现了真正精确的垃圾收集。
三色标记法
在 v1.5 中 Golang 实现了三色标记法，三色标记法的流程如下：
- 所有对象都标记为白色；
- 从根节点开始将对象标记为灰色；
- 从灰色及各种选择一个灰色对象并将其标记为黑色；
- 将该黑色对象指向的对象都标记为灰色；
- 重复步骤2、步骤3 直到不存在灰色对象。
- 回收白色对象。
写屏障
三色不变式
如果我们在使用三色标记法时采用和标记清除法相同的 STW 措施时肯定可以正常运行，但正是为了解决 STW 时间过长而采用的三色标记法，所以程序和GC是要并行的，如果有如下情况将会回收不应回收的对象：
- 黑色对象指向白色对象；
- 直接或间接指向该白色对象的灰色对象切断了依赖链条；
这种情况在标记完之后会将该白色对象清除掉，而黑色对象将产生悬浮指针问题。
强三色不变式：不允许黑色对象引用白色对象
弱三色不变式：黑色对象可以引用白色对象，但是这个白色对象必须存在其他灰色对象对它的引用，或者可达它的链路上游存在灰色对象。
而为了实现三色不变式，引入了屏障机制。
插入写屏障
写屏障这个名字如果没有接触过会感到很迷惑，其实它就是在进行写操作之前添加额外的处理，可以看作对函数的进一步封装。
writePointer(slot, ptr):
shade(ptr)
*slot = ptr
上述插入写屏障的伪代码非常好理解，每当执行类似 *slot = ptr 的表达式时，我们会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色，其他情况则保持不变。
通过这种方法就可以保证强三色不变式。
因为栈上的对象在垃圾收集中也会被认为是根对象，所以为了保证内存的安全，插入写屏障必须为栈上的对象增加写屏障，而用户代码执行过程中对会对栈上的数据频繁读写，所以会大幅增加写入的额外开销；另一种方法是不对栈上的空间开启插入写屏障，而是在标记阶段完成后 Stop the World，并对栈上的对象进行扫描，这两种方法各有利弊。
删除写屏障
writePointer(slot, ptr)
shade(*slot)
*slot = ptr
被删除对象，如果自身为灰色或者白色，那么被标记为灰色。
通过这种方法就可以保证弱三色不变式。
这种方式的缺点是，对于本次要删除的对象，只有在下一轮之后才会被清除。
混合写屏障
v1.8 使用了混合写屏障将垃圾收集时最坏的 STW 时间缩短至 0.05ms 以内。
writePointer(slot, ptr):
shade(*slot)
if current stack is grey:
shade(ptr)
*slot = ptr
该写屏障会将被覆盖的对象标记成灰色并在当前 goroutine 的栈没有扫描时将新对象也标记成灰色。
标记阶段开始时将栈上的可达对象全部扫描并标记为黑色。
在垃圾收集的标记阶段，我们需要将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，同时因为栈中的对象在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。
通过这种方法就可以保证变形的弱三色不变式。
关于 if current stack is grey 的问题，这个判断如果单纯看写屏障不容易搞明白适用条件，这里的标记阶段是并发执行的，当涉及到不同 goroutine 的操作时，例如 channel 带来的变量复制情况，会在不同的栈上进行操作，这里是为了防止另一个栈将我们需要的对象进行回收。