简单记录 golang 垃圾回收的基本原理
垃圾收集算法
主要来自 「深入理解Java虚拟机」
- 分代收集理论
- 标记-清除法：标记存活对象，然后清除没标记的对象；会产生内存碎片。
- 标记-复制法：标记，然后把存活对象移动到另一块空闲内存中；需要维护一段空闲内存导致内存利用率降低。
- 标记-整理法：先标记，然后移动存活对象到内存的一端，清理剩下的空间；移动存活对象需要STW，暂停时间长
诶，这里怎么没有我们经常听说的三色标记法呀博主是不是在偷懒打电动。其实不是，三色标记法是给垃圾回收过程添加并发能力的，用来保证并发情况下可达性分析的正确性（否则我们就要像JVM的Serial收集器那样单线程回收内存），因此没把它归在垃圾收集算法中。
goland的垃圾回收使用的垃圾收集算法是标记-清除法，只知道这些（名词）肯定不够，我们来看 golang 具体都做了什么操作和改进。
三色标记法
这里参考「深入理解Java虚拟机」，定义三种颜色对象的含义：
- 黑色是被访问过、且所有引用也扫描完毕的对象
- 灰色是被访问、但是所有引用尚未扫描完的对象
- 白色是没有被访问的对象，GC结束阶段仍是白色的对象会作为垃圾被回收
但是仅仅凭借三色标记法，我们还无法实现并发的垃圾回收：在三色标记的过程中，用户线程的修改会影响图中的引用关系，比如给黑色对象添加一个到白色对象的引用，这可能导致一个应该存活的对象被回收了。
在扫描对象图的过程中，用户线程删除了对象D到B的引用，并增加一个来自 A 的引用（此时A已扫描完毕，是黑色；D正在扫描引用，所以是灰色），因为 D 不再引用 B 所以此时不会扫描B。B 唯一的引用来自对象 A，可是垃圾回收线程不会再扫描黑色对象，所以 B 不会被扫描到从而保持白色，最后在清扫阶段被回收了。可怜的 A 以为它拥有 B，结果只是指向了一段错误的内存罢了。
还有一个问题，图里的根节点是从哪来的。根据[2]，主要是全局变量和栈。
内存屏障和写屏障
// TODO：什么是内存屏障
单独使用三色标记法我们还没法实现并发的垃圾回收，要达到目的我们还要在三色标记法的基础上加入写屏障来保证三色标记法分析的正确性。
「深入理解Java虚拟机」中提到 HotSpot 虚拟机使用的写屏障并非内存屏障，而是可看作一种在虚拟机层面实现的”对引用对象赋值“这一操作的AOP切片，但[2]和其他一些golang博客都说golang的写屏障是内存屏障的一种（不知道是否一人写错其他全部以讹传讹），目前水平和精力不足暂时不做深究。我这里简单将写屏障的实现理解为编译器生成的一段代码，在垃圾回收时，通过开启一个全局变量控制所有的写操作进入这段写屏障代码，完成染色操作。
Dijkstra 写屏障（又称插入写屏障）1： 增加一个黑色对象到白色对象的引用时，将该白色对象标为灰色
Yuasa 写屏障（又称删除写屏障）: 删除一个指向白色对象的引用时，将白色对象标为灰色
tri-color invariant:
- 强：黑色节点不能直接指向白色节点
- 弱：黑色节点指向的白色节点不能没有其他来自灰色节点的边（白可以被黑指，但是该白必须也要被灰指，避免该白色节点被扫描忽略）
满足其中一个三色不变性即可保证并发可达性分析的正确性，使用插入写屏障时能保证强三色不变性；使用删除写屏障保证弱三色不变性。
golang 早期使用 Dijk 写屏障，但是进行垃圾收集时并不会对所有根对象开启写屏障，采用的是标记阶段STW，然后将栈对象标为灰色并重新扫描的方法（我在[3]末尾找到这样的说明：The algorithm requires marking the free list and write barriers on roots. Both are unacceptable in practice.，可能在根对象上加写屏障的开销太大了)；
现在 golang 不是采用其中一种写屏障技术了，而是将二者结合形成混合写屏障，移除了标记结束之后 STW 将栈对象标为灰色然后重新扫描的过程。//TODO：其他操作有待学习
垃圾收集的阶段
// TODO：安全点 （Java
- 清理终止：STW
- 标记：开始标记和扫描
- 标记终止：STW
- 清理:
// TODO：为什么 清理终止和标记终止 阶段需要 STW？
总结
垃圾收集机制实在是太复杂了，我这里只能简单了解其原理，但是还有很多概念，比如安全点、内存屏障等没有搞清楚。如果以后有更深入的理解还会更新到这里的。
The End