GC

0x1. 基本原理

状态

• 白色：表示初始状态
• 灰色：表示正在迭代遍历其引用的对象
• 黑色：表示已经遍历完。

状态切换

如上图所示，白色状态其实包括两种，这个是为了防止在gc过程中加入对象。这里的两种白色表明每一轮gc的颜色。当遍历结束后如果还是白色那说明这个对象没有被引用就可以回收释放了。

根结点与存储链表

由于需要找引用关系，因此需要知道从哪个对象开始迭代，在lua中很明显就是lua_State这个结构，所有需要GC的对象都会直接或者间接被lua_State引用。

除了引用的根结点，还是需要知道分配的对象都放在哪里，不然我们就无法找到白色的对象，因为白色之所以成为白色对象，是因为没有被引用。在lua中这个是由链表组成，也就是所有分配的对象都会链接到一起。

0x2. 实现

引用关系

GC的标记就是从根节点global_State开始，按照上图的引用关系进行深度优先遍历。当整个图遍历完成之后，标记阶段也就结束了。

GC算法

GC算法从GCSpause状态开始，回收完一轮之后又回到GCSpause状态。在每个阶段都会判断当前执行的耗时，以决定是否暂停，防止由于GC导致卡住整个lua线程。GCSpropagate是标记阶段也就是前面讲的图遍历。

GCSseepstring和GCSsweep是回收阶段。这里为什么要将string的回收和其他对象分开呢？主要原因在于string的特殊性：

• 字符串没有下级引用
• lua中的字符串是全局复用的，保存在全局的hash表中。hash桶内部也是一个链表，和GClist一样，因此可以共用。

GC的入口函数有两个，luaC_step和luaC_fullgc。其中luaC_step是增量GC，会在lua执行过程中调用，大部分申请内存的地方都会调用。而luaC_fullgc则是lua提供给用户程序的接口，由于这个是全量GC，可能会卡住较长时间，需要谨慎调用。