LuaJIT Garbage Collector Algorithms

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 溢出进行检查。当收集器暂停时，可以完全避免检查标记位，因为不可能有任何黑色对象。