一、GC实现需要考虑的问题

1、着色可以处理循环引用

mark and sweep实现，通过着色的方法，一个优点就是可以避免循环引用，当A和B两个对象可能互相指向对方时，着色可以避免无限递归。

2、全量集和可达集

sweep的时候是清除没有被访问过的节点，相当于从全量集合中删除子集。所以就需要有一种方法，能够找到系统中所有的变量；加上一个遍历的起点(也就是根节点)，从而mark所有可达节点。

3、增量收集中的引用关系变化

增量GC实现的问题在于增量过程中，这些变量的引用关系可能变化

二、全量集和可达集

1、全量集

所有的可回收对象共享一个CommonHeader结构，该结构中的next可以组成一个链表。
/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
通过global_State结构的
GCObject *allgc; /* list of all collectable objects */
字段作为一个链表的开始，可以将所有的可回收对象组成一个链表。当需要全量集合时，遍历这个链表即可。

2、可达集

在三色标记中，可达集合为黑色和灰色，但是灰色只是中间状态，它们是下一次增量mark的起始集合，在最终sweep的时候，它们应该为空。global_State的
GCObject *gray; /* list of gray objects */
字段作为gray集合的链表头指针，每次从该集合开始增量mark，并且当这个集合为空时，一个mark周期结束。

3、初始gray集合

Only objects accessible from the root set are
preserved.
– root set: the registry and shared metatables.
– the registry contains the global table (_G), the main thread, and package.loaded.

三、增量过程中引用变化问题

1、三色之间的限制

这里最为关键的一点是“黑色不能指向白色”，因为黑色要经过灰色这个过程。从逻辑上说，如果黑色表示它指向节点都已经被mark过，所以该黑色节点在之后的mark阶段不会被考虑，而它指向白色，意味着白色节点没有被mark过，该白色节点可能失去被mark的机会。三色之间总共有六个可能的指向：黑白、黑灰、灰白、灰灰、白白、白黑，除了黑白之外，其它都是合法指向。
● Objects in the root set are gray or black.
● A black object cannot point to a white object.
● Gray objects define the boundary between the black objects and the white objects.
● Collection advances by traversing gray objects,turning them black.
– which may create new gray objects
● Collection ends when there are no more gray objects.

2、增量过程中如果黑色引用白色

此时有两种方法：一种是把黑色变成灰色，另一种是把白色变成灰色。无论如何，新变成灰色的节点会在下次mark时被重新检测。
It can either move forward the white object to gray or move backward the black object to gray

3、赋值时对三色限制的保证

tsecer@harry: cat glob.assign.lua
a = b

tsecer@harry: ../src/luac -l -l glob.assign.lua

main <glob.assign.lua:0,0> (3 instructions at 0x7faa60)
0+ params, 2 slots, 1 upvalue, 0 locals, 2 constants, 0 functions
1 [1] GETTABUP 0 0 -2 ; _ENV "b"
2 [1] SETTABUP 0 -1 0 ; _ENV "a"
3 [1] RETURN 0 1
constants (2) for 0x7faa60:
1 "a"
2 "b"
locals (0) for 0x7faa60:
upvalues (1) for 0x7faa60:
0 _ENV 1 0
tsecer@harry:
虚拟机指令OP_SETTABUP对应的逻辑会执行到luaV_fastset，其中会执行luaC_barrierback，如果a为黑色而b为白色，则将a重新变为黑色。
#define luaV_fastset(L,t,k,slot,f,v) \
(!ttistable(t) \
? (slot = NULL, 0) \
: (slot = f(hvalue(t), k), \
ttisnil(slot) ? 0 \
: (luaC_barrierback(L, hvalue(t), v), \
setobj2t(L, cast(TValue *,slot), v), \
1)))

4、栈变量修改的保持

从lua虚拟机代码来看，对于局部变量的修改并没有尝试进行三色保持。那么考虑下面代码
local a={}
假设在这条指令之后进行GC的mark和sweep，那么新创建的table会被认为没有被引用，此时就可能会被回，这名显示错误的。
所以在最后回收的时候，gc会对栈中的所有变量全部进行一次mark，在栈变量不多并且操作频发的情况下，最后统一mark比每次赋值都mark的代码更低。
static l_mem atomic (lua_State *L) {
……
markobject(g, L); /* mark running thread */
……
}
static lu_mem traversethread (global_State *g, lua_State *th) {
……
for (; o < th->top; o++) /* mark live elements in the stack */
markvalue(g, o);
……
}

四、代码说明

1、数据结构

代码中使用的都是TValue，
/*
** Union of all Lua values
*/
typedef union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;

#define TValuefields Value value_; int tt_

typedef struct lua_TValue {
TValuefields;
} TValue;

而lua管理的是GCUnion

/*
** Union of all collectable objects (only for conversions)
*/
union GCUnion {
GCObject gc; /* common header */
struct TString ts;
struct Udata u;
union Closure cl;
struct Table h;
struct Proto p;
struct lua_State th; /* thread */
};

2、假设局部变量创建table

对于一个函数的堆栈，堆栈中的基本单元并不是我们在C语言中使用的CPU word，而是虚拟机自定义的TValue结构，每次堆栈的访问、增减都是以该单位为最小粒度操作。
tsecer@harry: cat localtable.lua
local a = {}
tsecer@harry: ../src/luac -l -l localtable.lua

main <localtable.lua:0,0> (2 instructions at 0x7eda50)
0+ params, 2 slots, 1 upvalue, 1 local, 0 constants, 0 functions
1 [1] NEWTABLE 0 0 0
2 [1] RETURN 0 1
constants (0) for 0x7eda50:
locals (1) for 0x7eda50:
0 a 2 3
upvalues (1) for 0x7eda50:
0 _ENV 1 0
tsecer@harry:
可以看到，虚拟机指令OP_NEWTABLE对应的是创建一个table，然后让栈中变量ra(Value类型)的gc指针指向新创建的table，所以相当于栈中有一个指针指向新创建的Table对象
vmcase(OP_NEWTABLE) {
int b = GETARG_B(i);
int c = GETARG_C(i);
Table *t = luaH_new(L);
sethvalue(L, ra, t);
if (b != 0 || c != 0)
luaH_resize(L, t, luaO_fb2int(b), luaO_fb2int(c));
checkGC(L, ra + 1);
vmbreak;
}

3、遍历函数中栈常量

由于栈中变量的TValue类型的gc指向Table，所以可以访问到Table对象，从而可以避免该对象被回收。
static int traverseproto (global_State *g, Proto *f) {
……
for (i = 0; i < f->sizek; i++) /* mark literals */
markvalue(g, &f->k[i]);
……
}

4、新创建节点添加到gc链表上

所有lua创建的对象在创建时都通过luaC_newobj完成，可以看到，新创建的对象挂在了global_State中allgc链表的开始。
GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
global_State *g = G(L);
GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
o->marked = luaC_white(g);
o->tt = tt;
o->next = g->allgc;
g->allgc = o;
return o;
}