前段时间看了一遍 mruby GC，基本把逻辑理清楚了，发补丁补了一些注释之余这里简单记一下。
搞过 rails 的同学会有印象，传统 Mark-Sweep 的主要问题是收集时间的不可控 [1]，不幸赶上 GC 的话，页面延迟会比较大。mruby 像 lua 一样将目标设定为可嵌入的解释器，对此很自然的考虑是令 GC 分阶段渐进执行，而三色 GC 也是最简单、最正确的渐进式 GC 的实现方式。
三色 GC 的思路来自 Knuth 的三色图遍历算法 [2]，对象分为黑、灰、白三种颜色，分别维护在不同的集合里。一轮 GC 的流程很简单：
为了让 Sweep 阶段渐进化，仍可以引入另一种白色，放到单独的集合里。到下一轮 GC 开始之后，新申请的对象会被标记为这种新的白色，至于旧的白色对象，则在理论上可以随时收集，不会受到新申请的白色对象的干扰。也就是说，mruby GC 在 Sweep 阶段回收的永远是上一轮 GC 留下的死对象。
此外一条铁律是：黑色对象不可以引用白色对象。然而在一轮 GC 期间对象的引用关系难免变化，比如新申请的白色对象，可能需要被黑对象引用。对此，需要用户手工调用 Write Barrier [3]，将黑对象重新标记为灰色。
其间的每一小步遍历的步子迈的都非常小，所以理论上对于延迟敏感的应用，三色 GC 要友好的多。但是因为将 GC 分派到多次执行的同时，也延长了一轮 GC 的周期，期间积累的内存占用会相对多一些。
在 mruby 中，GC 触发的时机有如下几个:
mrb_realloc_simple() 申请内存时内存不足，触发 mrb_full_gc()。mrb_obj_alloc() 申请对象时存活对象的数目超过阙值，触发 mrb_incremental_gc()。mrb_full_gc() 事先执行一次完整的清理。不管 mrb_full_gc() 还是 mrb_incremental_gc()，都是对 incremental_gc(mrb, limit) 的封装，它也正是 mruby GC 的中心函数，就像一台自动机那样维护着 mruby GC 的状态：
gc_state 的值为 GC_STATE_NONE: 表示前一轮 GC 已经完成，进入 root_scan_phase() 将根对象 mark，并 flip_white_par()，将两种白色切换，准备进入 Mark 阶段。GC_STATE_MARK: 执行 incremental_marking_phase() ，如果 gray_list 已经空了，再去扫描 atomic_gray_list 单独处理 Write Brrier 标记出来的灰色对象 [4]，完成 final_marking_phase()，准备进入 Sweep 阶段。GC_STATE_SWEEP: 执行 incremental_sweep_phase()，回收上一轮 GC 留下的死对象，之后将黑色对象标记为白色。完成之后将状态恢复为 GC_STATE_NONE。limit 参数在 Mark 阶段和 Sweep 阶段，分别指代一步渐进 GC 中标记或者回收的对象数目。在渐进式 GC 的一步中 (incremental_gc_step())，这个对象数目是跟据用户可设置的 gc_step_ratio 字段计算出来的。此外，渐进式 GC 不会立即回收内存，所以在一步走完之后，会相应地提高下次回收的阙值。
incremental_sweep_phase() 的实现在直观上有点粗暴，遍历待 Sweep 的堆中的所有对象，如果是死对象就回收。一开始我怀疑这里可能有性能问题，但是画了个火焰图发现瓶颈并没在这里，在 free() 面前它的消耗根本不值一提，就不了了之了。
除去三色 GC 将一轮 GC 分派到多次执行以外，另一条渐进式 GC 的思路是缩小每一轮 GC 的范围。好处是两方面的：减少了一轮 GC 的时间，更加及时地回收了内存。分代 GC 也正是最经实战考验的 GC 实现。
分代 GC 假定新的对象存活时间要比老对象短，将 GC 分为两种：
mruby 和 lua 都提供了一个分代模式的开关。不同在于 lua 将分代模式视为一个试验 feature，因为它没有性能数据支撑却引入了额外的复杂性而受到质疑，可能会被删除 [5]； 而 mruby 将分代模式默认开启，作为未来主要投入精力的方向，并且将分代模式的 major GC 按三色的方式分成了渐进的几步进行。
然而 mruby 及 lua 的分代 GC 模式并非 "严肃" 的分代实现，而是重用了三色 GC 的基础设施，没有加多少代码就提供了分代的支持，这也正是有趣的地方。在一轮 GC 之后仍存活的黑色对象即被视作老对象。也就是说，象征性地分了两代对象。
分代 GC 的逻辑在重用三色基础设施的同时，也在很大程度上把自己的逻辑和三色 GC 揉在了一起，在一开始理解起来并不是很容易。
在 mrb_incremental_gc() 中， mruby 会判断当前是否为 Minor GC，如果是，则调用 incremental_gc_until(mrb, GC_STATE_NONE) 一路跑到底，到 incremental_sweep_phase() 也有对 Minor GC 的特殊处理，那就是在回收的最后不会把黑色对象再重新标记为白色。
随着一轮又一轮 Minor GC，老对象会留下的越来越多，一旦超过了老对象的阙值 (majorgc_old_threshold)，就该触发 Major GC 了。 这时会触发 clear_all_old() 将当前的所有对象重置为白色，并设置一个奇怪的 gc_full = TRUE; [6]。但是等等，mrb_incremental_gc() 里面对于 is_major_gc() 的判断仅仅是对 GC 完成之后的清理工作，这是怎么回事？
这个问题困惑了我好久。想明白 mruby 是把 Major GC 也做了渐进化处理，这就容易理解多了。 Major GC 就等同于一轮普通的三色 GC，所以在 mrb_incremental_gc() 只迈了简单的一小步，而不是立即把所有老对象回收。凭印象，这也是和 lua 实现的一点不同之处。
cruby 那种最传统的 Mark-Sweep GC 实现中用户无需手工调用 Write Barrier 的幸福时代已经远去了。 mruby 的起点比 cruby 高得多，然而对于 cruby 的扩展开发者看来，强制使用 Write Barrier 却需要转变一下思路才好接受。
在扩展中每修改对象的引用，都要分外注意调用 Write Barrier，不然可能会有奇怪的 seg fault 出现，而且单纯靠 core dump 难以定位问题的位置 (但可以定位到漏掉 Write Barrier 的对象类型)。
mruby GC 并没有扫描 C 栈，那么对于 C 扩展的开发者而言，怎样避免下面这样的悲剧？
a = mrb_str_new(mrb, "a", 1);
b = mrb_str_new(mrb, "b", 1);
mrb_str_concat(mrb, a, b); // 内存紧张的话 a 或者 b 被回收了怎么办?
mruby 对此的应对方案是在 mrb_state 结构体中增加了一个数组，用来保存最近新申请对象的引用，每申请一个对象都会压入这个数组。到 GC 时会首先 mark 这一数组中引用的对象，从而避免了临时对象被回收的问题。当一个函数执行结束，其中的临时对象就不需要额外的保护了，将数组回退到执行之前的状态即可。它的名字有点奇怪：arena，但跟 dlmalloc 等内存分配器中 arena 的概念毫无联系。
但它带来了一个新的问题，那就是如果一个函数内部申请的对象较多，会导致 arena 数组溢出。因此 C 扩展的开发者需要额外注意，务必配合调用 mrb_arena_save() 与 mrb_arena_restore()，及时地回退 arena 。Issue #1533 属于这一问题的例子。
atomic_gray_list 里的原因还没有很想明白，哪位同学能帮忙解释下？gc_full 不是说内存满了，而是说接下来执行的是一轮 完整的 GC...