V8 增量 GC 之三色标记

因为要做组内分享，最近看了一下《垃圾回收算法与实现》，发现其实垃圾回收的算法基调基本上世纪 60 年代就曾经提出来了，后世的框架只是在给这些框架做组合和修补的工作。抛掉陈词滥调的分代假如不谈，V8 官博往年新发了一篇博文介绍 V8 GC 新进展，讲到增量回收的话题。本认为增量 GC 是什么陈腐货色，实际上早在 1975 年的一篇论文中，大宗师 Dijkstra 就曾经提出了这个问题的解决方案——三色标记算法。

令我纳闷的是，分代假如、清道夫算法跟传统的 Mark-Sweep 算法，都是合乎逻辑容易了解的；但到了三色标记这儿，好多材料都是语焉不详的：大家都尽力在形容这个算法的实现（其实也并不简单），有的也给出了动图（起初发现是抄的维基百科），但并没有博文真正解答这个问题：为什么不能间接用双色标记，而要用三色标记？

为了防止这个常识成为须要靠死记硬背能力记住的常识孤岛，我翻了一下大法师的论文原文，总算有了些脉络。

什么是垃圾回收

咱们首先先迅速而简略地介绍一下，到底什么是垃圾回收？其实顾名思义，次要是两点：垃圾、回收。

而后基于这两点有个 What/How/When，根本就把事儿讲明确了，翻译成官网术语就是：

• 什么是垃圾？如何找到垃圾？何时找垃圾？
• 什么是回收？怎么回收？何时回收？

对于所有的垃圾回收而言，垃圾其实都是指曾经没用的内存区域，回收就是指让这些区域能够被新的有用数据笼罩；对于怎么回收而言，也根本就是 Sweep 和 Compact 这两种策略，回收的机会也都是找完了就操作；然而在找垃圾（前面就称之为标记）的 How/When 这里，传统和增量就产生了区别：

对于传统的算法而言，垃圾回收是『全暂停 式』（Stop-The-World，前面简称 STW）的，当程序（专业术语称 mutator，指能扭转这个内存区域是否被程序援用的货色，比方程序自身。顺带一提，这个词儿也是 Dijkstra 推敲进去的）执行，GC 等着；特定机会时（比方内存满了）GC 执行，mutator 等着。因而它的如何找和何时找都比较简单：内存满，STW 开始；而找垃圾就是一种图的遍历，从 Root 登程，对所有能拜访的节点进行标记，拜访不到的就是垃圾。

采取 STW 这样凶残的策略，次要还是避免 mutator 在 GC 的时候捣鬼——这跟你用扫地机器人的时候把狗关屋子的情理是一样的；而增量标记，就等于赶着狗扫地，是一个跟 mutator 斗智斗勇的过程。

增量回收的窘境

对于增量回收而言，次要存在两个问题：第一个是须要暂停重启，第二个就是淘气的 mutator。

1、暂停重启

因为增量回收是 并发 的（concurrent），因而它的过程像上图一样（能够设想一下 CPU 的工夫片轮转），这就意味着 GC 可能被随时暂停、重启，因而暂停时须要保留过后的扫描后果，等下一波 GC 来之后还能持续启动。而双色标记实际上 仅仅是对扫描后果的形容 ：非黑即白，但疏忽了对 扫描进行状态的形容：这个点的子节点扫完了没有？如果我上次停在这样一个图上，重新启动的时候我就不仅要问：到底 A、B 点要不要扫子节点？

为了解决这种状况，Dijkstra 引入了另外一种色彩：灰色 ，它示意 这个节点被 Root 援用到，但子节点我还没解决；而彩色的意思就变为：这个节点被 Root 援用到，而且子节点都曾经标记实现。这样在复原扫码时，只须要解决灰色节点即可。

引入灰色标记还有一个益处，就是当图中没有灰色节点时，便是整个图标记实现之时，就能够进行清理工作了。

2、淘气的 mutator

解决了三色的问题，就能够增量回收了么？其实没有这么简略。咱们能够设想一下，什么是失败的垃圾回收？无非就是两点：

1. 把有用的货色扔了；
2. 把没用的货色留着；

其实只有有伎俩，没用的垃圾还是能够忍它留几轮；然而有用的被干掉是无法忍受的：我刚申明了一个变量你就通知我 Reference Error，我 fuuuuu 佛慈善。

对于传统的 STW 而言，通过根节点标记援用，能力立即辨别以后状态下的有用和没用，再做操作的时候便熟能生巧；然而对于增量回收而言就不同了，Dijkstra 在论文里举了一个很顽皮的 mutator：

1. 三个节点 ABC，C 在 AB 之间重复横跳，一会儿只有 A 指向 C，一会儿只有 B 指向 C；
2. 开始扫 A 时，C 的爸爸是 B，扫完了 A 节点是黑的，C 是白的；
3. 开始扫 B 时，C 的爸爸是 A，扫完了 B 没有子节点，B 节点是黑的，C 还是白的；
4. 因为 A 节点曾经标黑，无奈扫描其子节点，只好持续向后扫描；
5. 一顿蛇皮操作之后，C 被当成孤儿干掉了，C 的爸爸们留下了无奈的泪水。

解决办法：引入写屏障

方才的案例其实就是说了一个问题：在 mutator 瞎操作的状况下，很有可能将曾经标记为扫描完事儿的节点（彩色节点）续上一个过后还未被扫描的红色节点。而一旦这个红色节点后续又被其余曾经扫描过的节点援用到，也没有什么机制可能再收集它了。

在思考完这个案例之后，Dijkstra 提出了一个要求：不能让彩色节点指向红色节点！每当产生援用变动时，须要立即对被援用节点进行着色：即白的立即染灰，灰的和黑的不变。

比方下面 C 的例子，当 C 的父节点发送变动时，肯定会呈现相似这样的代码：A.C = C，产生之后，立即给 C 节点着色并推入灰色栈，这样就解决了不小心清理掉有用节点的问题。

总结

总而言之，三色标记次要是为了解决增量标记中传统双色标记过程无奈分片的问题，有了三色标记，传统的双色标记便能够暂停重启，因而就能够划分成小段，变成跟 mutator 并发的形式来运行；写屏障则是用来解决并发中 mutator 变动，导致有用内存被清理的问题。三色标记只是垃圾回收泛滥技术计划之中的一个小插曲，其余如分代假如、清道夫算法等都有其精妙之处，能够深入研究。

参考文章

• 朴神雄文 V8 GC Log
• 垃圾回收的算法与实现
• Lua JIT 文档：乏味的是，因为 Lua 在 5.0 之前始终应用 STW 的双色标记，因而只有它在文档里简略形容了一下三色标记与双色标记的区别，甚至还提出了四色标记算法；