Lua GC 的源码剖析 (1)
最近发现在大数据量的 lua 环境中，GC 占据了很多的 CPU 。差不多是整个 CPU 时间的 20% 左右。希望着手改进。这样，必须先对 lua 的 gc 算法极其实现有一个详尽的理解。我之前读过 lua 的源代码，由于 lua 源码版本变迁，这个工作还需要再做一次。这次我重新阅读了 lua 5.1.4 的源代码。从今天起，做一个笔记，详细分析一下 lua 的 gc 是如何实现的。阅读代码整整花掉了我一天时间。但写出来恐怕比阅读时间更长。我会分几天写在 blog 上。
Lua 采用一个简单的标记清除算法的 GC 系统。
在 Lua 中，一共只有 9 种数据类型，分别为 nil 、boolean 、lightuserdata 、number 、string 、 table 、 function 、 userdata 和 thread 。其中，只有 string table function thread 四种在 vm 中以引用方式共享，是需要被 GC 管理回收的对象。其它类型都以值形式存在。
但在 Lua 的实现中，还有两种类型的对象需要被 GC 管理。分别是 proto （可以看作未绑定 upvalue 的函数）， upvalue （多个 upvalue 会引用同一个值）。
Lua 是以 union + type 的形式保存值。具体定义可见 lobject.h 的 56 - 75 行：
/*
** Union of all Lua values
*/
typedef union {
GCObject *gc;
void *p;
lua_Number n;
int b;
} Value;
/*
** Tagged Values
*/
#define TValuefields Value value; int tt
typedef struct lua_TValue {
TValuefields;
} TValue;
我们可以看到，Value 以 union 方式定义。如果是需要被 GC 管理的对象，就以 GCObject 指针形式保存，否则直接存值。在代码的其它部分，并不直接使用 Value 类型，而是 TValue 类型。它比 Value 多了一个类型标识。用 int tt 记录。通常的系统中，每个 TValue 长为 12 字节。btw, 在 The implementation of Lua 5.0 中作者讨论了，在 32 位系统下，为何不用某种 trick 把 type 压缩到前 8 字节内。
所有的 GCObject 都有一个相同的数据头，叫作 CommonHeader ，在 lobject.h 里 43 行 以宏形式定义出来的。使用宏是源于使用上的某种便利。C 语言不支持结构的继承。
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
从这里我们可以看到：所有的 GCObject 都用一个单向链表串了起来。每个对象都以 tt 来识别其类型。marked 域用于标记清除的工作。
标记清除算法是一种简单的 GC 算法。每次 GC 过程，先以若干根节点开始，逐个把直接以及间接和它们相关的节点都做上标记。对于 Lua ，这个过程很容易实现。因为所有 GObject 都在同一个链表上，当标记完成后，遍历这个链表，把未被标记的节点一一删除即可。
Lua 在实际实现时，其实不只用一条链表维系所有 GCObject 。这是因为 string 类型有其特殊性。所有的 string 放在一张大的 hash 表中。它需要保证系统中不会有值相同的 string 被创建两份。顾 string 是被单独管理的，而不串在 GCObject 的链表中。
回头来看看 lua_State 这个类型。这是写 C 和 Lua 交互时用的最多的数据类型。顾名思义，它表示了 lua vm 的某种状态。从实现上来说，更接近 lua 的一个 thread 以及其间包含的相关数据（堆栈、环境等等）。事实上，一个 lua_State 也是一个类型为 thread 的 GCObject 。见其定义于 lstate.h 97 行。
/*
** `per thread' state
*/
struct lua_State {
CommonHeader;
lu_byte status;
StkId top; /* first free slot in the stack */
StkId base; /* base of current function */
global_State *l_G;
CallInfo *ci; /* call info for current function */
const Instruction *savedpc; /* `savedpc' of current function */
StkId stack_last; /* last free slot in the stack */
StkId stack; /* stack base */
CallInfo *end_ci; /* points after end of ci array*/
CallInfo *base_ci; /* array of CallInfo's */
int stacksize;
int size_ci; /* size of array `base_ci' */
unsigned short nCcalls; /* number of nested C calls */
unsigned short baseCcalls; /* nested C calls when resuming coroutine */
lu_byte hookmask;
lu_byte allowhook;
int basehookcount;
int hookcount;
lua_Hook hook;
TValue l_gt; /* table of globals */
TValue env; /* temporary place for environments */
GCObject *openupval; /* list of open upvalues in this stack */
GCObject *gclist;
struct lua_longjmp *errorJmp; /* current error recover point */
ptrdiff_t errfunc; /* current error handling function (stack index) */
};
一个完整的 lua 虚拟机在运行时，可有多个 lua_State ，即多个 thread 。它们会共享一些数据。这些数据放在 global_State *l_G 域中。其中自然也包括所有 GCobject 的链表。
所有的 string 则以 stringtable 结构保存在 stringtable strt 域。string 的值类型为 TString ，它和其它 GCObject 一样，拥有 CommonHeader 。但需要注意，CommonHeader 中的 next 域却和其它类型的单向链表意义不同。它被挂接在 stringtable 这个 hash 表中。
除 string 外的 GCObject 链表头在 rootgc （ lstate.h 75 行）域中。初始化时，这个域被初始化为主线程。见 lstate.c 170 行，lua_newstate 函数中：
g->rootgc = obj2gco(L);
每当一个新的 GCobject 被创建出来，都会被挂接到这个链表上，挂接函数有两个，在 lgc.c 687 行的
void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
global_State *g = G(L);
o->gch.next = g->rootgc;
g->rootgc = o;
o->gch.marked = luaC_white(g);
o->gch.tt = tt;
}
void luaC_linkupval (lua_State *L, UpVal *uv) {
global_State *g = G(L);
GCObject *o = obj2gco(uv);
o->gch.next = g->rootgc; /* link upvalue into `rootgc' list */
g->rootgc = o;
if (isgray(o)) {
if (g->gcstate == GCSpropagate) {
gray2black(o); /* closed upvalues need barrier */
luaC_barrier(L, uv, uv->v);
}
else { /* sweep phase: sweep it (turning it into white) */
makewhite(g, o);
lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
}
}
}
upvalue 在 C 中类型为 UpVal ，也是一个 GCObject 。但这里被特殊处理。为什么会这样？因为 Lua 的 GC 可以分步扫描。别的类型被新创建时，都可以直接作为一个白色节点（新节点）挂接在整个系统中。但 upvalue 却是对已有的对象的间接引用，不是新数据。一旦 GC 在 mark 的过程中（ gc 状态为 GCSpropagate ），则需增加屏障 luaC_barrier 。对于这个问题，会在以后详细展开。
lua 还有另一种数据类型创建时的挂接过程也被特殊处理。那就是 userdata 。见 lstring.c 的 95 行：
Udata *luaS_newudata (lua_State *L, size_t s, Table *e) {
Udata *u;
if (s > MAX_SIZET - sizeof(Udata))
luaM_toobig(L);
u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata)));
u->uv.marked = luaC_white(G(L)); /* is not finalized */
u->uv.tt = LUA_TUSERDATA;
u->uv.len = s;
u->uv.metatable = NULL;
u->uv.env = e;
/* chain it on udata list (after main thread) */
u->uv.next = G(L)->mainthread->next;
G(L)->mainthread->next = obj2gco(u);
return u;
}
这里并没有调用 luaC_link 来挂接新的 Udata 对象，而是直接使用的
/* chain it on udata list (after main thread) */
u->uv.next = G(L)->mainthread->next;
G(L)->mainthread->next = obj2gco(u);
把 u 挂接在 mainthread 之后。
从前面的 mainstate 创建过程可知。mainthread 一定是 GCObject 链表上的最后一个节点（除 Udata 外）。这是因为挂接过程都是向链表头添加的。
这里，就可以把所有 userdata 全部挂接在其它类型之后。这么做的理由是，所有 userdata 都可能有 gc 方法（其它类型则没有）。需要统一去调用这些 gc 方面，则应该有一个途径来单独遍历所有的 userdata 。除此之外，userdata 和其它 GCObject 的处理方式则没有区别，顾依旧挂接在整个 GCObject 链表上而不需要单独再分出一个链表。
处理 userdata 的流程见 lgc.c 的 127 行
/* move `dead' udata that need finalization to list `tmudata' */
size_t luaC_separateudata (lua_State *L, int all) {
这个函数会把所有带有 gc 方法的 userdata 挑出来，放到一个循环链表中。这个循环链表在 global_State 的 tmudata 域。需要调用 gc 方法的这些 userdata 在当个 gc 循环是不能被直接清除的。所以在 mark 环节的最后，会被重新 mark 为不可清除节点。见 lgc.c 的 545 行：
marktmu(g); /* mark `preserved' userdata */
这样，可以保证在调用 gc 方法环节，这些对象的内存都没有被释放。但因为这些对象被设置了 finalized 标记。（通过 markfinalized ），下一次 gc 过程不会进入 tmudata 链表，将会被正确清理。
具体 userdata 的清理流程，会在后面展开解释。