上次在 blog 上写 Lua GC 是 2011 年，lua 5.2 尚未发布时候的事情了。我认为仔细研读优秀开源代码是非常值得做的事情，但把研读过程写出来却意义不大。代人咀嚼这事吃力不讨好，每个人的技术背景不同，写得过细浪费阅读时间，写的粗糙又会使读者不得要领。一行行读代码本就只是件辛苦活，任何人沉下心来都能做到，想通过别人代读而节省时间，多半是做不到的。所以我那本 Lua 源码欣赏 也就一直搁置了。
沉在代码的逐行细节中往往一叶障目，反不如高屋建瓴的理解一下作者的思想。今年的 lua workshop ，Lua 的主要维护者 Roberto Ierusalimschy 做了题为 Garbage collection in Lua 的演讲，很好的讲述了 Lua 历史各个版本的 gc 算法实现。我没有听这个演讲，但阅读 Slide 结合源代码基本可以搞明白。这篇 Blog 分享一下我的理解。注意：我添加了许多自己的理解，很可能和演讲原意有极大的偏差。所以本篇仅代表我的个人立场。
几乎所有现代编程语言都有自动化内存管理设施，在内存不再使用的时候，能够自动释放它们。有两种方法可以做到这点，一是引用计数，二是垃圾收集。引用计数有循环引用无法将不再使用的对象引用减到零的问题，但这并不是 Lua 选择垃圾收集方法的主要原因。主要原因是对于动态语言来说，引用计数带来的额外开销太大，尤其是即使一段程序完全不分配内存，你也需要承担这额外开销。可以类比的动态语言是 Python ，它就是主要基于引用计数来实现自动内存管理的，Python 解释器的运行效率较低，我认为很大程度源于此。
以 Lua 为例，运行时的对象，要么存在于注册表间接引用的 table 中，要么存在于执行栈上（严格说来，注册表引用了主线程，执行栈在线程结构内）。当一个对象被一个 table 引用时，对于步进式垃圾收集，它需要一个 Barrier 来维持对象的可见性状态，这和递增引用计数的成本一致；不过对象从 table 中移除则不需要额外做递减引用计数的操作；我们可以认为在这个问题上，引用计数带来的成本仅仅是垃圾收集的两倍。但性能问题出在对象在执行栈上的操作。不光是函数调用和返回会在栈帧间传递对象的引用，任何一段代码都会在栈上反复移动对象。对于大部分静态语言，可以通过代码的静态分析，把加减引用的操作添加在必要的位置，然后再通过编译器优化，去掉不必要的操作。例如 C++ 的 RAII 机制，Objective-C 的 ARC 都是这么干的。但对于 Lua 来说，这就增加了太多的解释器的复杂度；即便生成了类似的代码，开销也无法忽略。对比 C++ ，它是通过大量 inline 函数才得以消除大部分 RAII 的冗余操作的，这在 Lua 这类动态语言中行不通。
Lua 因为引用计数的额外开销问题选择了垃圾收集器。垃圾收集器并不负责内存分配释放，内存的底层管理是通过在创建 Lua 虚拟机时从外部注入的分配器完成的。虚拟机工作时所有产生的对象都被串在一个链表上组成一个集合，而被虚拟机根集间接引用的对象都会被保留，剩下的对象引用无法被根集引用，则会在恰当的时机回收。虚拟机的根集包括了注册表，以及原生类型的 metatable 。全局表、主线程、标准库的代码等等，都被注册表所引用。
在 Lua 5.0 以前，Lua 使用的是一个非常简单的标记扫描算法。它从根集开始遍历对象，把能遍历到的对象标记为活对象；然后再遍历通过分配器分配出来的对象全集链表，把没有标记为活对象的其它对象都删除。
但是，Lua 5.0 支持 userdata ，它可以有 __gc 方法，当 userdata 被回收时，会调用这个方法。所以，一遍标记是不够的，不能简单的把死掉的 userdata 简单剔除，那样就无法正确的调用 __gc 了。所以标记流程需要分两个阶段做，第一阶段把包括 userdata 在内的死对象剔除出去，然后在死对象中找回有 __gc 方法的，对它们再做一次标记复活相关的对象，这样才能保证 userdata 的 __gc 可以正确运行。执行完 __gc 的 userdata 最终会在下一轮 gc 中释放（如果没有在 __gc 中复活）。 userdata 有一个单向标记，标记 __gc 方法是否有运行过，这可以保证 userdata 的 __gc 只会执行一次，即使在 __gc 中复活（重新被根集引用），也不会再次分离出来反复运行 finalizer 。也就是说，运行过 finalizer 的 userdata 就永久变成了一个没有 finalizer 的 userdata 了。
GC 的性能表现对整个系统的性能表现影响重大。Go 语言早期就是因为 GC 问题而饱受诟病。如果我们把 GC 关闭，那么 CPU 就完全没有额外开销，但是会有极大的内存开销；如果我们每次分配新对象都运行一遍 GC ，那么就不会有任何额外的内存开销，但是 CPU 开销会完全不可接受（现在 Lua 保留着一个宏开关，可以不停的运行完整的 GC ，用来测试 GC 实现的正确性）。Lua 5.0 采用的是一个折中的方案：每当内存分配总量超过上次 GC 后的两倍，就跑一遍新的 GC 流程。但 Lua 5.0 这种会把整个虚拟机都停下来的 （Stop the World ）的简单粗暴的 GC 实现，在实践中的问题非常明显，这导致 Lua 5.0 成为一个分水岭。5.0 之前的 Lua 多用于内嵌脚本，只充当系统中的底层模块间的粘合剂，而之后解决了大部分的 GC 停顿问题后，人们才逐渐让 Lua 承担更多工作。
从 Lua 5.1 开始，Lua 实现了一个步进式垃圾收集器。这个新的垃圾收集器会在虚拟机的正常指令逻辑间交错分布运行，尽量把每步的执行时间减到合理的范围。
一旦 GC 不能一次完成，它就无法把整个虚拟机看成一块静态数据加以分析。那么怎么办呢？我们就要借助 Mutator 模式 。只要我们把所有对象的修改都监控起来，从垃圾收集器的角度来看，程序就只是一段段在修改它需要去回收的数据的东西，它不用管程序到底执行了什么，只要知道什么时候修改了什么。
Lua 5.1 采用了一种三色标记的算法。每个对象都有三个状态：无法被访问到的对象是白色，可访问到，但没有递归扫描完全的对象是灰色，完全扫描过的对象是黑色。
我们可以假定在任何时间点，下列条件始终成立（ Invariants）：
所有被根集引用的对象要么是黑色，要么是灰色的。
黑色的对象不可能指向白色的。
那么，白色对象集就是日后会被回收的部分；黑色对象集就是需要保留的部分；灰色对象集是黑色集和白色集的边界。
随着收集器的运作，通过充分遍历灰色对象，就可以把它们转变为黑色对象，从而扩大黑色集。一旦所有灰色对象消失，收集过程也就完成了。
但 mutator 本身会打破上面的规则，比如原有一个黑色对象 t ，和一个白色对象 {} ，当我们运行 t.x = {} （触发了一个 mutator ) 时，就会让这个黑色对象指向一个白色对象。这时，我们需要在所有这种赋值的地方插入一个 write barrier 检查这种情况，恢复不变条件（invariant) 。
我们有两种方式维持不变条件：一种是把白色对象变为灰色的（forward），另一种是把黑色对象变回 (backward) 灰色。如果参考 Lua 5.1 以后的代码，在 lgc.h 中能找到两个 api 对象这两种操作，luaC_barrier 和 luaC_barrierback 。
什么时候采用什么方法更好是实现的时候凭经验（感觉？）决定的。比方说，给 table 赋值的时候，就直接把被赋值的黑色 table 变回灰色。我猜是因为大部分时候被修改的 table 都不会是黑色，同时不需要检查赋值的量的类型和颜色。如果一个黑色的 table 变回了灰色，就证明在扫描中途被打断（处于某种不常见的临界状态），就把它单独放在一个独立的链表 (grayagain）里，留待后面原子处理，避免它在黑和灰之间反复折腾。对于堆栈，则干脆不让它变黑，这样对栈的操作就不需要 barrier ，提高栈写入的性能。
如果是给对象设置一个 metatable ，例如 setmetatable(obj, mt) 这样的，我们可以采用 forward 策略，当 obj 为黑，而 mt 为白色的，将 mt 置灰。
扫描过程一步步的将灰色对象标记为黑色，最后会留下一些反复的灰色对象（曾被标记为黑色，又因为 mutator 的 barrier 检查变回了灰色），这些一次性原子的递归遍历，最后再遍历所有的堆栈。原子步骤中还包括清理需要清理的弱表（弱表中有至少一个白色对象的引用）、分离出需要调用 __gc 的对象。这些原子步骤是 GC 最可能长时间停顿的时机，但原子步骤是 GC 算法正确性的前提。所以我们应该注意，尽量减少不必要的 __gc 对象，减少不必要的弱表使用，才能尽可能的减少 GC 停顿。
和 Lua 5.0 的单次全量 GC 一样，__gc 对象对 gc 过程的影响很大。因为我们需要单独把带 __gc 方法的对象重新扫描一次复活所有相关对象，保证在 __gc 调用时相关对象都还在，和普通的扫描流程不同，这一步必须原子的单步完成，不可拆解。
步进式 GC 如何步进工作的呢？
和很多不了解算法实现的人的直觉不同，GC 的步进并不和真实的时间相关（通常多线程 GC 和时间相关，因为 GC 运行过程独立于主逻辑线程之外），它只和虚拟机分配新的内存有关。也就是说，只要虚拟机不分配更多内存，GC 是不会自动运行的。GC 依靠新增内存量来决定该做多少工作，它也依靠标记或清理的内存量来决定工作做了多少。每次做多了，会导致程序更多额外的停顿，做少了，会导致内存回收速度赶不上新增速度。
步进式 GC 比全量 GC 复杂，不能再只用一个量来控制 GC 的工作时间。对于全量 GC ，我们能调节的是 GC 的发生时机，对于 lua 5.0 ，就是 2 倍上次 GC 后的内存使用量；在 5.1 以后的版本中，这个 2 倍可以由 LUA_GCSETPAUSE 调节。另外增加了 LUA_GCSETSTEPMUL 来控制 GC 推进的速度，默认是 2 ，也就是新增内存速度的两倍。lua 用扫描内存的字节数和清理内存的字节数作为衡量工作进度的标准，有在使用的内存需要标记，没在使用的内存需要清理，GC 一个循环大约就需要处理所有已分配的内存数量的总量的工作。这里 2 是个经验数字，通常可以保证内存清理流程可以跑的比新增要快。
我见过不少人曾在邮件列表中抱怨，自己实现的 userdata 可能能被 Lua 感知到的内存并没有多少（只有一个指针），但实际占了很大的内存（背后的 C/C++ 对象），lua 虚拟机无法正确的驱动 GC 工作。如果大量分配这种 userdata ，程序使用的内存暴涨，无法及时回收。其实，正确的方法很简单，在分配新的 userdata 时，利用 lua_gc 传入 LUA_GCSTEP 让它步进相应真实占据的内存数量就可以了，而没有必要让虚拟机记住这个 userdata 真的使用了多少内存。
从上面的算法分析可见，步进式 GC 能够减少每次 GC 工作时的停顿时间，但是无法减少 GC 带来的额外开销，相反，GC 的时间成本（额外的 Barrier ）和空间成本（未能及时回收不再使用的内存）反而较之全量 GC 增加了。
我们经常可以看到峰值时 Lua 会使用大量超过我们预期的内存总量，是我们估算的程序需要的内存的两倍左右。这是因为长期运行的程序理论上应该稳定在一定的内存总开销左右，但 Lua 的 GC 周期触发条件却是新的不断分配的对象的内存总量达到过去的两倍。为了改善这点，Lua 引入了分代 GC 。在 Lua 5.2 中，以一个试验特性提供，后来因为没有收到太多正面反馈，又在 Lua 5.3 中移除。事实上 Lua 5.2 提供的分代 GC 过于简单，的确有设计问题，未能很好的解决问题，在还没有发布的 Lua 5.4 中，分代 GC 被重新设计实现。
分代 GC 之所以可以更及时的回收内存其实是基于这样的假设：
大部分对象被分配出来后很快就回收掉了（C/C++/Go 等静态语言中，特别把只存在于栈上的临时对象单列出来做内存管理正是如此）。所以，垃圾收集器可以集中精力对付刚刚构造出来的年轻对象。
我们将对象分为青年的和年老的两代，新创建出来的对象一律归为青年代，一旦年轻的对象经历了两轮收集周期而依旧健在，他们就成长为老年对象。在每个次级收集周期，收集器只对青年代的对象进行遍历清除工作。这样就避免了每次都遍历大量并不活跃却长期存活的老年对象，又可以及时清理掉大量生命短暂的青年对象。
次级收集周期越密集，单个周期内的青年对象数量就越少，需要做的工作也越少，停顿时间也就缩小了。可见增加收集周期并不会太多的增加整体工作量，却可以更及时的回收内存；而相对于之前的算法，增加收集周期则意味了更多的工作（因为每个周期都需要遍历所有的对象）。
对于分代 GC ，我们也有一个始终成立的条件（Invariant）：老对象不会指向新对象。但是，分步却变得更困难了。当变化发生时，无论是 forward 还是 backward 都有问题：对于 forward ，也就是把新对象变成老的，无疑会制造大量老对象，还需要递归变量，否则就会打破规则。如果是采用 backward 策略，更很难保持条件成立（对象很难知道谁引用了自己，就无法准确的把老对象变回新的）。
所以，需要引入第三态：触碰过的对象（The Touched Objects）。
当 back barrier 需要解决老对象指向新对象的问题时，老对象被标记为触碰过，并放入一个特别的集合。被触碰的对象在次级收集周期中也会参与遍历，但是不会被清理。被触碰的对象如果不再被触碰，那么在两个周期后，它会回到老年集。
这里为什么强调是两个次级收集周期而不是单个？这就要提到 Lua 5.2 所犯的错误。Lua 5.2 的分代 GC 算法中，就只针对单个次级收集周期处理。任何对象活过当前的收集周期，就会变老。这样处理固然简单，但有极大的问题。如果一个对象刚刚被创建出来，次级收集过程就开启了，它很容易就活过这个周期（例如函数尚未返回，刚在堆栈上创建出来的对象就不能回收），这个对象就迅速变老了。这种本该随即回收的对象未被回收的越多，并不老的老对象增多会进一步增加中间状态的对象数量，次级收集过程能收集的临时对象更少。
我们判定新东西变老（长期引用）的准则是活过足够长的时间，至少也要一个次要收集周期。所以活过当下的周期肯定不够（无法避免刚创建的对象变老），至少应该活过当下和前一个周期才行。
但是两个周期的实现算法势必要复杂的多。只判断在当前周期存活的规则很简单，每次次级收集后，所有没被收集的对象都归为老年代即可，然后就可以把触碰集直接清空。而两个周期的规则，则需要好几个链表之间倒腾：每个次级收集周期结束，只有部分新对象变老，另一些还需要维持，触碰对象集的一部分需要继承到下一个周期。这实现起来真的很复杂，并难以测试。
不过一个正确实现的分代 GC 可以极大的减少传统 GC 额外的内存开销。有同学在他的基于 skynet 的项目中尝试过切换到 lua 5.4 ，进程在长期运行时，内存使用峰值要少且稳定的多。
分代模式的一个问题是当进入主收集周期，必须做一次完整的标记清除，这和 Lua 5.0 的全量 GC 是一样的，这会带来停顿问题。只不过分代 GC 模式下，全量 GC 频率可以降的非常低，因为大量临时内存都通过次级收集周期清理掉了，内存并不会增长太快。当遇到必须消除停顿的环境，我们可以手工精确调整：发现内存持续增长，不要主动触发完整的主收集周期，而是主动切换到步进模式，然后周期性的调用 gc step （不等内存分配器来触发）在合理的时间内分布报完一个完整的 GC 周期，再切换回分代模式。
我认为 Lua 5.2/5.4 没有默认做这种自动模式切换，是因为默认 GC 无法通过时间驱动来分片工作，而必须依赖内存分配器新增内存驱动导致的。如果我们对 GC 工作原理有清晰的理解，便很容易在程序框架的周期循环内自己来驱动 GC 按需工作。