Go作为一门具有自动内存管理系统的语言，具有着独特的垃圾回收机制。Go在1.3版本使用标记清除法回收内存，而在1.5版本后则使用三色标记法回收内存。本篇博客主要讲三色标记法。
头图来源：ただ町を見下ろした-雪町@土曜日東 B05a-pixiv
垃圾回收回收了什么
首先需要了解内存中的两种结构：堆（heap）和栈（stack）。栈空间用来存储函数中的局部变量以及函数调用栈，栈空间存储的数据在生命周期结束（如函数结束返回后）后由编译器自动清除，这部分的数据就不需要通过垃圾回收来回收。而在堆上分配的数据（如通过new生成的对象或go逃逸分析中存在内存逃逸的对象）并不会自动释放，此时则需要垃圾回收来回收这部分的内存。
垃圾回收的根对象都有哪些
- 全局变量：程序中存在于整个生命周期的变量
- 执行栈：每个goroutine都有自己独有的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
- 寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存区块。
垃圾回收大体步骤
- STW(stop-the-world,即在启动垃圾回收时暂停程序)开启写屏障，记录数据段以及栈中根节点的必要信息
- 开始标记阶段，此时mutator（用户程序）和GC标记并发执行
- 标记完成后再次STW，关闭写屏障
- mutator继续执行，GC进入清扫阶段
三色标记法
为了解决过去标记清除法带来长时间的STW，如今多数的追踪式垃圾收集器都会实现三色标记算法的变种来缩短STW时间。
三色标记
三色标记算法将程序中的对象分为白色、灰色、黑色三类：
- 白色对象 潜在的垃圾，其内存可能会被垃圾收集器回收
- 黑色对象 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象
- 灰色对象 被标记为活跃的对象
算法流程
如上图，三色标记法可以分为如下几个步骤：
- 从根对象（图中省略）出发,找到根对象引用的对象（图中A和F）并将其标记为灰色。
- 从被标记为灰色的对象，找出该对象所引用的对象将其标记为灰色，同时将该对象标记为黑色，保证该对象和被改对象引用的对象都不会被回收。
- 重复步骤1和2直至不存在灰色的对象
- 清除所有白色的对象。
屏障技术
内存屏障技术是一种屏障指令，它可以让CPU或编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。
为什么需要屏障技术
三色标记法本身并不能并发或增量地执行，仍然需要STW。如果在执行三色标记法回收内存时同时又不暂停程序会发生什么？举个例子，如下图
图中用户程序建立了从A对象到D对象的引用，但是很不巧，三色标记法已经认为它标记完了所有的对象（它并没有感应到这次修改操作）程序中已经不存在灰色对象了，因此D对象被错误地回收，使得A指向D对象的指针指向了一块不存在任何数据的地址（即悬垂指针）。为了避免以上的情况，想要并发或增量地标记对象就需要用到屏障技术。
强三色不变性
强三色不变性指的是黑色对象不会指向白色对象，只会指向灰色或黑色的对象。
弱三色不变性
弱三色不变性指的是黑色对象可以指向白色对象，但是黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。
插入写屏障
插入写屏障就是为了满足强三色不变性，具体操作就是在A对象引用B对象时，先将B对象标记为灰色然后再建立引用关系。伪代码如下：
writePointer(slot,ptr){
shade(ptr)
*slot = ptr
}这样做的意义就在于其将所有有存活可能的对象都标记为灰色来满足强三色不变性。
缺点
由于栈上的对象在垃圾收集中也会被认为是根对象，因此为了保证内存的安全，插入写屏障必须为栈上的对象增加写屏障或者在标记阶段完成重新扫描栈上的对象，这两种方式都各有缺点，前者会大幅度增加写入指针的额外开销而后者需要进行STW。
删除写屏障
删除写屏障会保证在开启写屏障期间堆上所有对象都是可达的，因此删除写屏障也被称作快照垃圾收集。伪代码如下：
writePointer(slot,ptr){
shade(*slot)
*slot = ptr
}删除写屏障会在老对象的引用删除前将被老对象引用的对象标记为灰色。这样做的目的是满足弱三色不变性，为了防止当老对象删除引用时，如果此时被引用的对象是白色，那么有其他对象引用这个对象时该对象被错误回收的情况。
缺点
删除写屏障的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮该对象才会被GC回收。同时在GC开始时，会STW扫描栈来记录初始快照，这个过程会保护开始时刻的所有存活的对象。
混合写屏障
Go在1.8版本引入了混合写屏障机制，它同时结合了插入删除写屏障的有点，避免对栈重复扫描的过程，极大降低了STW的时间。其伪代码如下：
writePointer(slot, ptr):
shade(*slot)
if current stack is grey:
shade(ptr)
*slot = ptr混合写屏障特点
- 写屏障只在堆上启用，栈上不开启写屏障
- GC开始将栈上的对象全部扫描并标记为黑色
- GC期间任何在栈上创建的新对象均为黑色
- 被删除的对象标记为灰色
- 被添加的对象标记为灰色
