调试分代 GC 的几个 bugs

接上篇，让 version 不是每次加一，而是对老对象每次加比较多，就可以达到降低老生代的 GC 扫描频率，从而降低每次 GC 的扫描开销，间接地实现分代 GC。思想特别简单，但是实践下来还是遇到了不少 bug，好在都陆续解决掉了，没有让方案执行不下去。几个非常印象深刻的 bug 记录一下，如果不是真正实践下来，这些地方在设计的时候根本想不到。

当我们推对象的版本的时候，需要保证约束不被打破：版本较大的对象，不能够指向版本较小的对象，也就是老生代禁止指向新生代。如果一个对象的 next version 加 20，那么它必须将它的孩子的版本，全部都递归地加到不小于它，才能保证这个约束。

第一个地方是，一个对象可能是被多个对象指向的，比如该对象的版本是 10，它被一个版本 12 对象指向了，同时也被一个版本为 30 的对象指向了，那它应该将该对象的版本设置为多少？似乎应该设置为 30，也就是推到跟最老生代的对象的版本一致。因为如果只将它的版本修改到 12，那么就会出现版本 30 对象，引用到版本为 12 的对象，打破约束。而设置到 30，则是 12->30, 30->30，避免了老生代指向新生代对象。

被多个对象指向时，将版本推到最大的那个，仅仅这么做是不行的，一个极为隐蔽的 bug 出现了。假设当前的 gc 版本是 10，然后我们遇到一个对象 A，它同时被版本 12 的对象 B 和版本 30 的对象 C 指向，我们将该对象 A 的版本设置为 30。下一次 gc 版本到 12 了，我们从 root 开始扫描到了版本 12 的 B 对象，然后由于它引用的对象 A 版本为 30，会跳过对 A 的标记过程。假设 root -> B -> A 这条路径是一直活跃的，也就是 A 其实是活跃对象，那么经过好几个版本，这条路径的版本会一直增加 10->12->16->24->32 ... 对象 A 本应该一直是活跃的。然而，我们选择将 A 的版本推到 30，有可能在 root -> C -> A 这条路径，在版本 30 的时候 C 对象不再是活跃的，于是从 root 到 A 不可达，于是在版本 30 的时候，A 被当作垃圾 GC 掉了！

也就是说，当同时存在 root -> B -> A 和 root -> C -> A 多条路径的时候，选择哪条路径至关重要，选错了就可能会导致 A 被误删。无脑将 A 推到较大的版本 30，有可能导致选路径，这样做是不行的。

选小的版本不行，会导致出现老生代引用新生代约束被打破。选大的版本也不行，有可能选错活跃对象的可达路径。这个极为隐蔽的 bug 的解决方式是，新生代，中生代，老生代，等等这些在版本设计上面，必须有相遇的版本。比如说扫描一次后还活跃，版本加到 4 的倍数上，扫描两次后还活跃，则版本加到 8 的倍数上，扫描三次后还活跃，则版本加到 24 的倍数上。由于有这种倍数关系的设计，不管从哪个版本开始推，不同的对象总会有相遇的版本。还是看前面的例子，我们让 C 对象一定会经过 32 这个版本，由不管 root -> C -> A 还是 root -> B -> A，它们都会在 32 这个特定的版本相遇。在版本 32 时刻，如果 C 不再活跃了，也会有 root -> B -> A 这条路径保证 A 对象不会被误删。

或者这样更直观一点，像高速公路那样，有多条道。起初最右道上的对象，每次 GC 后存活，则版本 +2。而 GC 几次之后，移到中间道上。中间车道的对象是每次版本 +4 的。再左侧车道，则每次 +8，最左车道，每次版本 +24。对象的分代就是从最右道，越迁到中间到，再继续往最左道。在同一条道上，它们的版本号就会交汇。

下一个 bug，是 write barrier 的处理方式。我之前的想法很天真，就是如果老生代引用新生代，就把新生代对象推到老生代去。遇到的坑是，会有太多的新生代对象，被推到老生代，导致分代彻底失去意义。还是举例子，我在调度器里面用到了 vector 这样数据结构，来实现调度的队列。vector 是这门语言中为数不多的带副作用的操作，也就是唯一需要加 write barrier 的操作。如果一个 vector 对象版本较大，而 vector-set 更新其中一个元素，新的元素的版本较小，加 barrier 就需要把新的元素，版本号增加到跟 vector 一样。注意，这里是需要一个递归过程的，如果 vector-set 的元素修改了版本，那它所指向的对象的版本也需要递归修改，否则还是破坏约束。这个递归可能很深，完全不可控。我遇到的 case 就是调度队列的 vector，引用了 coroutine 对象，然后 coroutine 对象又有自己的栈，这个栈上的对象又要继续递归更新版本，结果一通操作下来，几乎所有对象，都被更新了一遍。这显然就不是我们想要的分代 GC 了，所有新生代对象都推到老生代去，集中到老生代，那分代就完全没有意义了嘛。

找了下资料，我发现 lua 也遇到了这样的问题。云风的博客里面有记录过，这个问题就是 "forward ro backward"

无论是 forward 还是 backward 都有问题：对于 forward ，也就是把新对象变成老的，无疑会制造大量老对象，还需要递归变量，否则就会打破规则。如果是采用 backward 策略，更很难保持条件成立（对象很难知道谁引用了自己，就无法准确的把老对象变回新的）

lua 的解决方式是引入了 The Touched Objects 的概念，Touched 还是在老生代的，但是对于出现老生代引用新生代的场景，特别地记录下来，然后即使是老生代对象(touched)，依然要 GC 做扫描。教科书上这个术语其实就是 remember set。我原本想避开这个概念，看来想得太天真了，踩坑了才知道这里避不开。

印象最深刻的 bug 就是这两个。其它的 bug 也是陆续解了好久，其实此刻我都无法 100% 确认跟分代 GC 相关的 bug 全部解完了。lua 那边，它在 5.4 版本支持了分代，但是其实它的分代和增量两种 GC 是相互独立的，也就是说，用户可以设置运行在增量模式，也可以设置运行在分代模式，却无法同时支持分代和增量。而我这边却是同时支持增量和分代的，这么一想还是挺高级的。