lua的GC

关于lua的gc云风大佬在 Lua GC 的源码剖析 系列文章中讲得很清楚，这里做一下简单的记录。

分步gc

lua使用的是一种三色标记清除算法（tri-color incremental mark & sweep），大体步骤如下：
初始阶段，所有对象标为白色；
标记阶段的开始，将所有从root可达的对象标记为灰色；
标记阶段，逐个取出灰色对象，将其本身标记为黑色，将其所有引用的白色对象标记为灰色；
当不存在灰色对象时，进入清除阶段，清除所有白色对象，将所有黑色对象标记回白色。

具体而言，lua的gc分为markroot、mark、atomic、sweepstring、sweep、finalize几个阶段（见singlestep()）。
markroot函数将若干lua对象链表的根节点置为灰色，放入gray链表/队列；mark阶段类似树的广度优先遍历，从gray队列中取出灰色对象，标为黑色，再将其所引用的对象置为灰色，加入gray队列；mark是分步执行的，中间对象关系可能又发生变化，在开始清理工作前，还需要做最后一次扫描，这个过程不可以再被打断，就是atomic函数；sweepstring阶段分步清理字符串；sweep阶段分步清理其他对象；userdata对象可能会有自定义gc方法，finalize阶段就用来调用这些gc方法，userdata对象本身则放在下轮gc清理。

标记阶段和清除阶段都是可以分步的，所以称为分步gc。但中间可能出现这样的情况：A引用B，B引用C；A已经标记为黑色，B标记为灰色，C为白色；在gc间歇期间，程序修改了对象间的引用关系， B不再引用C，而A开始引用C。C本来是活跃对象，但却会被清除，这会造成严重错误。算法引入写屏障技术，来解决这种问题：将此 白色 对象标记成 灰色，称为barrier forward，因为正常是白色->灰色->黑色的转换方向；将此 黑色 对象标记回 灰色，称为barrier back。

如何确定gc的步伐大小是一系列的微操，见singlestep()、luaC_setp()。

数据类型

在Lua中共有9种数据类型，分别为nil、boolean、lightuserdata、number、string、table、function、userdata和thread。其中只有string table function thread四种在vm中以引用方式共享，是需要被GC管理回收的对象。其它类型都以值形式存在。
另外还有两种类型的对象需要被GC管理，分别是proto和upvalue。

string创建后挂载于g->strt->hash
upvalue创建后被链在g->uvhead
table、thread、function、proto则都是挂在g->rootgc上，在mark阶段简单加到gray队列即可

markroot

有3个链表用于标记和清理过程，gray是灰色对象的链表，grayagain是在atomic阶段需要再次标记的对象的链表，weak是弱表的链表。
markroot()先将这三个链表清空，再将mainthread、mainthread的全局表、注册表、各类型元表标记，放到gray队列中，开始mark阶段。

string

mark的时候只是置灰，不挂载到gray上，所以它没有黑色。
在sweepstring阶段集中处理g->strt->hash。

userdata

rootgc初始化为mainthread，创建其他对象时使用的是头部插入，所以mainthread是链表的最后一个元素。
但是luaS_newudata()中将userdata挂到mainthread后，所以rootgc链表被mainthread分为两部分，后边是userdata，前边是其他对象。
userdata没有灰色，mark时直接标为黑色。
atomic中遍历mainthread之后的userdata链表（luaC_separateudata()），空闲且有gc方法的从rootgc移到g->tmudata中。
finalize阶段专门用来处理tmudata链表，对每个元素标记为白色，返还给rootgc，然后调用它的gc方法。
没有gc方法的空闲数据，就在sweep阶段被清理掉；有gc方法的，第一轮gc时先调用gc方法，第二轮gc时在sweep阶段清理掉userdata本身，通过finalized标志来识别userdata的状态。

string和userdata不引用其他对象，都是叶子节点。

upval

mark的时候：
如果是opend的，其指向栈上变量，将其指向的变量变灰；
如果是closed，其已是叶子节点，直接变黑。

以下引用自 Lua GC 的源码剖析 (4)：

为何 open 状态的 TUPVAL 需要留为灰色待处理呢？这是因为 open TUPVAL 是易变的。GC 分步执行，我们无法预料在 mark 流程走完前，堆栈上被引用的数据会不会发生变化。事实上，在 mark 的最后一个步骤，我们会看到所有的 open TUPVAL 被再次 mark 一次，做这件事情的函数是 remarkupvals。

thread

mark的时候，从gray移到grayagain，且不变黑。
堆栈是随着运行过程不断变化的，为了效率其上数据的修改是不经过barrier的，所以把它推迟到atomic阶段重扫描。

table

traversetable()的时候，弱表不会从灰变黑，而是转移到weak链表上。
若弱表引用的元素被移除，也需要将元素从弱表中移除，atomic()中会调用cleartable()来做这件事。
移除table中hash部分value为nil的entry是通过removeentry()：

static void removeentry (Node *n) {lua_assert(ttisnil(gval(n)));if (iscollectable(gkey(n)))ttype(gkey(n)) = LUA_TDEADKEY; /* dead key; remove it */
}

可以看到只是将key设为LUA_TDEADKEY类型，并没有从表中真删掉，那何时真正删除呢？是rehash的时候。
所以 高性能 Lua 技巧（译） 中这样说“你不该期望通过从一个大表里删除一些数据来回收内存，更好的做法是删除这个表本身。”。

参考

讲解 Lua 内部实现的 gc 机制
Lua GC 的工作原理
Lua GC 的源码剖析