Explain
本篇文章是对Make Pall发表wili内容《LuaJIT 3.0 new Garbage Collector》的翻译和扩展，因为原文是对LuaJIT 2.x GC重要功能的简介和对LuaJIT 3.0 new GC的工作计划，所以它并不是系统性介绍GC的文章。希望以后能有精力系统性的对LuaJIT 2.x GC做个总结。
到目前（2025-1-17）为止，LuaJIT 3.0尚未发布。看Make列的3.0 plan，其中优化了很多功能，非常值得期待。但他也说了，3.0有可能永远不会发布，这将是非常遗憾的一件事情。
一、Two-Color Mark & Sweep
Two-Color Mark & Sweep 是标记-清除算法的简化版本，使用两种颜色（白色和黑色）来表示对象的状态：
- 白色对象：表示未被访问的对象，默认情况下所有新分配的对象都是白色。如果一个对象在垃圾回收周期中结束时仍然是白色，说明它是不可达的，可以被回收。
- 黑色对象：表示已被标记为可达的对象。黑色对象不会被清除，并会在清除阶段颜色翻转为白色以便参与下一个 GC 周期。
1.1 GC流程
标记阶段（Mark Phase）从 GC 根（例如，主线程，全局变量等）开始，迭代遍历所有可达（live）对象，并将它们标记为黑色。待标记完成，没有被标记为黑色的对象都被视为无法访问，即死对象。
清除阶段（Sweep Phase）遍历所有内存中的对象：如果对象为白色，则认为其是死对象，将其释放；如果对象为黑色，则认为其可达，将颜色翻转为白色，准备参与下一次GC。
1.2 主要缺点
该算法的主要缺点是非增量式（non-incremental），整个垃圾回收过程必须一次性完成，程序代码（mutator，指运行中的程序）无法与垃圾回收器并行执行。即回收操作是原子性的，需要完全暂停程序运行，这种暂停称为 Stop-the-world（STW），会导致程序响应延迟，特别是当内存中有大量对象时，暂停时间可能很长。
这种回收方式不适合实时系统或对响应时间要求高的场景，例如游戏或用户界面。
1.3 重要优化
为了提升效率和降低开销，算法中可以引入一些优化，例如：
- 交换颜色的意义：在每次垃圾回收结束后，反转白色和黑色的定义。例如，将“黑色”定义为“未访问”，将“白色”定义为“可达”。这样可以避免在清除阶段对黑色对象的颜色翻转操作，减少额外的步骤。
- 增量式改进：尽管基础算法是非增量式的，但可以通过引入写屏障（Write Barrier）等机制改进为增量式标记。
1.4 应用实例
Lua 5.0 使用了 Two-Color Mark & Sweep 算法，具有以下特点：
- 对象存储结构：所有对象都存储在一个链表中。这种设计的优点是方便遍历内存中的所有对象，缺点是访问速度较慢。
- 标记列表（Mark List）：在标记阶段，将需要遍历的对象放入一个独立的标记列表。这样可以加速标记阶段中对对象的处理，同时避免重复标记。
- 内存回收效率：Lua 5.0 的 GC 虽然简单，但由于设计目标是轻量级脚本语言，这种算法在小型脚本的场景中表现较好。
二、Tri-Color Incremental Mark & Sweep
Two-Color Mark & Sweep是 全停顿（Stop-the-world，STW） 的算法，会导致程序在垃圾回收时暂停。为了减少暂停时间，增量式垃圾回收 （Incremental GC）被提出， Tri-Color Marking则是其一种常用的技术。
Tri-Color Incremental是 Lua 5.1/5.2 和 LuaJIT 1.x/2.x 使用的 GC 算法，它是 Lua 5.0 链表算法的增强版。
Tri-Color Incremental Mark & Sweep 用三种颜色（白色、灰色、黑色）来区分对象的状态，三种颜色的定义如下：
- 白色（White）：表示未访问的对象。在标记阶段开始时，所有的对象都被标记为白色。如果某个对象在整个标记阶段结束后仍然是白色，则说明该对象是不可达的垃圾，可以被回收。
- 灰色（Gray）：表示已被标记，但未处理其引用对象的对象。意味着当前对象是可达的，但它可能引用其他未处理的对象。
- 黑色（Black）：表示已被标记并且其引用对象也被处理完毕的对象。意味着该对象和它的引用对象都是可达的，无需再次处理。
2.1 GC流程
任何时刻新分配的对象都被标记为白色。
标记阶段，垃圾回收器从GC根（GCroots）开始，遇到一个可达的对象，将其颜色从白色变为灰色，并将其加入灰色栈（graystack，或重新链入灰色列表）。灰色栈中的对象会被逐一迭代处理，每次从栈中移除一个灰色对象，遍历灰色对象的所有引用，将其引用的对象标记为灰色，并将灰色对象加入灰色栈中。一个对象的所有引用遍历完成后，将其颜色会灰色变为黑色。
清除阶段与前面提到的Two-Color算法类似。遍历所有内存中的对象：如果对象为白色，则认为其是死对象，将其释放；如果对象为黑色，则认为其可达，将颜色翻转为白色，准备参与下一次GC。
2.2 增量式（Incremental）
为了避免一次性完成垃圾回收而导致程序长时间暂停，Tri-Color 标记算法可以增量执行。垃圾回收器采用分段标记，一次只处理少量灰色对象，然后将控制权交还给应用程序（mutator）。
这种方式将垃圾回收暂停分散为许多短间隔，特别适合对交互性要求高的场景（例如游戏或互联网服务器）。
增量式GC存在黑色对象引用白色对象的问题。在增量过程中，mutator可能在回收器工作时，创建一个新的标记为白色的对象，并将白色对象（未处理）存储到一个黑色对象（已处理）中。如果发生这种情况，这个白色对象不会被标记为可达对象，而是在清除阶段被错误地回收，即使它实际上可以从一个可达对象中访问到。
对于此问题的解决方法，是维护三色不变性（Tri-ColorInvariant），GC必须满足以下两个不变性之一：
- 强三色不变性（Strong Tri-Color Invariant）：黑色对象不能直接引用白色对象。如果存在这种情况，白色对象可能会被错误地认为是不可达的，从而被误回收。
- 弱三色不变性（Weak Tri-Color Invariant）：黑色对象可以直接引用白色对象，但要求该白色对象必须存在其他灰色对象对它的引用，或者它的可达链路上游存在灰色对象。
通过插入屏障（Insertion Barrier）机制来实现。当对象A引用对象B时，如果对象B是白色，则将其标记为灰色，从而避免黑色对象直接引用白色对象。
2.3 写屏障（Write Barrier）
如果mutator在增量执行中破坏了三色不变性（如添加了新的引用），需要通过写屏障（Write Barrier）来修复。
写屏障（Write Barrier）在每次写操作后检查是否违反了三色不变性，如果发现不变性被破坏，需要采取修复操作。有两种修复方式：
- 后向屏障（Backward Barrier）：将黑色对象重新变为灰色，并将其重新加入灰色栈中，以便稍后重新处理。优点：对于需频繁写入（例如容器对象）的对象，可以减少对相同对象的后续屏障检查。
- 前向屏障（Forward Barrier）：立即将白色对象标记为灰色，并将其加入灰色栈中。优点：可以推动垃圾回收向前运行，适用于只进行孤立写操作的对象。
Lua 5.1/5.2 和 LuaJIT 1.x/2.x对Tables使用后向屏障，所有其他可遍历对象使用前向屏障。
LuaJIT 2.x 通过只检查标记黑色的table（忽略存储对象的颜色）进一步优化了table的写屏障。这样检查速度更快，而且仍然安全：写屏障可能会更频繁地触发，但这没有坏处。而且这在实践中并不重要，因为 GC 周期进展非常快，中间有较长的暂停，所以对象很少是黑色的。而且，存储的对象通常都是白色的。
以下是Mike Pall对LuaJIT中写屏障的一些介绍：
写屏障只需检查存储到其中的对象的灰色位（gray bit）。这是一个非常快速的测试，并且只有在未设置灰色位时才会触发（这种情况很少见）。
如果触发了写屏障，白色对象将变为浅灰色（light-gray），黑色对象将变为深灰色（dark-gray），深灰色对象还会被推送到快速顺序存储缓冲区 (sequential store buffer，SSB) 上。
浅灰色对象不需要推送到 SSB，但这需要检查标记位。如果触发屏障的性能成为问题，则可以避免这种情况。可以改为对 SSB 溢出进行检查。当收集器暂停时，可以完全避免检查标记位，因为不可能有任何黑色对象。
2.4 重要优化
程序堆栈（Stacks）始终保持为灰色，并在清除阶段之前重新遍历。这样可以避免对堆栈插槽的写入使用写屏障（堆栈插槽是写入操作最频繁的地方）。
没有对子对象的引用的对象可以立即从白色变为黑色，而不需要经过灰色堆栈。
可以通过使用两个白色并在进入清除阶段之前在它们之间翻转来使清除阶段成为增量。需要保留具有“current”白色的对象。只有具有“other”白色的对象才应该被释放。
三、Quad-Color Optimized Incremental Mark & Sweep
关于三色算法中的后向屏障（backward barriers）存在一个问题：如果标记位（mark bits）不在对象本身内联（inline），写屏障的检查会变得非常昂贵。因为当屏障触发时，必须对一个黑色对象进行准确的检查，确保它在重新变为灰色之前是黑色的。遗憾的是，在新的垃圾回收（GC）中，标记位（白色与黑色）是分隔存储的，只有灰色位（gray bit）在对象内联。
仅仅检查“不是灰色”并不好，因为这会导致写屏障在处理白色和黑色对象时都被触发，且每次写操作都会将它们转为灰色。这对于在GC暂停期间的白色对象尤其不利，因为大量灰色对象可能会不必要地积累在灰色栈中。
解决方案是引入第四种颜色，将灰色分为浅灰色和深灰色。新分配的可遍历对象为浅灰色：标记位为白色，灰色位被设置。通常情况下，新对象分配后会立即进行写操作。写屏障只检查灰色位是否被清除，并且在这种情况下不会触发。
当对象在标记阶段被标记时，它会变成深灰色（标记位变为黑色），并被推入灰色栈。如果对象不可达，清扫阶段会像处理其他白色对象一样回收浅灰色对象。
深灰色对象在遍历后会变为黑色（清除灰色位），并在清扫后变为白色。写屏障在这个短暂的期间可能会被触发，并通过将对象再次转为深灰色来回移屏障。
一个在一个GC周期中存活的对象会像其他所有存活对象一样变为白色。如果对象在此之后被写入，它会再次变为浅灰色。但这不会立刻将对象推入灰色栈！事实上，仅需要翻转灰色位，正如上述所解释的，这避免了进一步的写屏障。
四色算法的主要优点是超便宜的写屏障：只需检查灰色位，这只需要2或3条机器指令。而且由于初始着色和特定的颜色转换，像表格这样的对象在实践中几乎不会触发写屏障。写屏障的快速路径不需要访问标记位图，这避免了在Mutator运行时污染缓存。
四色算法可以通过将一些可遍历对象初始设为白色并使用前进写屏障（forward write barriers）来轻松回退到三色算法。而对于不可遍历对象，有一个明显的捷径：标记会立即将白色对象变为黑色，这只会触及标记位图。因为这些对象位于隔离的区域，它们不需要被遍历，并且在标记阶段其数据从不需要加载到缓存中。
这是将被LuaJIT 3.0使用的GC算法。对象和隔离的元数据在区域（arenas）中管理，而不是在链表中。
还有一些其他GC算法使用了比标准颜色更多的颜色，例如两个白色（如上所述）。然而，没有任何算法像这种算法那样使用颜色。另外，通过搜索“四色GC”（quad-color GC）或相关变种，什么也找不到。在没有相反证据的情况下，我（Mike Pall）在此声明我发明了该算法。如果你不同意，请立即通知我。与我在LuaJIT上的所有研究成果一样，我在此将相关的知识产权捐赠给公共领域。所以请随意使用、分享并享受它！