接上篇, Lua中的GC采用的是三色垃圾增量回收算法.
因此真正进入singlestep函数之前, 先来简单介绍一下三色垃圾回收算法.
在三色垃圾回收算法有,每个可回收对象都会有”黑”,”白”,”灰”三种颜色. 所有对象刚创建都是白色(这里暂不考虑barrier的效果), 一个完整的GC循环大概如下:
1. GC从根对象开始遍历并为对象标记颜色.(这里需要明确的时,根对象并不是指前面的global_State.allgc, 而是指Lua中的一些全局对象,比如lua_State, 注册表)
2. GC每当发现一个发现一个可回收对象A,就将其标记为”灰”色. 然后去遍历对象A引用了哪些可回收对象.
3. 当对象A引用的所有可回收对象都被标记以后, 对象A被标记为”黑色”.
4. GC递归执行2,3步骤直到遍历完所有可达的对象
5. GC清除掉所有的白色对象(这时global_State.allgc就派上用场了)
列举一下Lua中所有可回收对象,及每个对象都可能有哪些引用别的对象的方式(从函数reallymarkobject, propagatemark可以得出这些信息)
* “字符串(LUA_TSTRING)”: 不会引用其他对象,只要被标记就一定是黑色
* “用户数据(LUA_TUSERDATA)”: 元表(metatable), 用户数据(user value)
* “表(LUA_TTABLE)”: 元表(metatable), 表中的key和value字段,需要说明的是,如果__mode=”k”则,key的可达不会阻此key所引用的对象被回收,__mode=”v”同样如此, 更详细的弱表GC在这里
* “Lua闭包(LUA_TLCL)”: Lua函数原型(LUA_TPROTO), 上值(upvalue)
* “Lua C闭包(LUA_TCCL)”: 上值(upvalue)
* “协程(LUA_TTRHEAD)”: 栈上的所有Value
* “Lua函数原型(LUA_TPROTO)”: 常量字符串(literals), 上值的名字(upvalue names), 嵌套的LUA_TPROTO, 局部变量的名字
终于可以进行singlestep函数了.
singlestep函数本质上是个状态机, 会根据global_State.gcstate的值执行不同的逻辑, global_State.gcstate 共有8个可选值, LuaVM刚创建时global_State.gcstate默认值是GCSpause, 换句话说GC循环是从GCSpause状态开始的.
//lgc.h
#define GCSpropagate 0
#define GCSatomic 1
#define GCSswpallgc 2
#define GCSswpfinobj 3
#define GCSswptobefnz 4
#define GCSswpend 5
#define GCScallfin 6
#define GCSpause 7
//lstate.h
/*
** Some notes about garbage-collected objects: All objects in Lua must
** be kept somehow accessible until being freed, so all objects always
** belong to one (and only one) of these lists, using field 'next' of
** the 'CommonHeader' for the link:
**
** 'allgc': all objects not marked for finalization;
** 'finobj': all objects marked for finalization;
** 'tobefnz': all objects ready to be finalized;
** 'fixedgc': all objects that are not to be collected (currently
** only small strings, such as reserved words).
*/
typedef struct global_State {
...
GCObject *allgc; /* list of all collectable objects */
GCObject **sweepgc; /* current position of sweep in list */
GCObject *finobj; /* list of collectable objects with finalizers */
GCObject *gray; /* list of gray objects */
GCObject *grayagain; /* list of objects to be traversed atomically */
GCObject *weak; /* list of tables with weak values */
GCObject *ephemeron; /* list of ephemeron tables (weak keys) */
GCObject *allweak; /* list of all-weak tables */
GCObject *tobefnz; /* list of userdata to be GC */
GCObject *fixedgc; /* list of objects not to be collected */
...
};
//lstate.c
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
...
g->gcstate = GCSpause;
...
}
下面从GCSpause状态开始分析singlestep中每个状态都干了什么.
//lgc.c
static void restartcollection (global_State *g) {
g->gray = g->grayagain = NULL;
g->weak = g->allweak = g->ephemeron = NULL;
markobject(g, g->mainthread);
markvalue(g, &g->l_registry);
markmt(g);
markbeingfnz(g); /* mark any finalizing object left from previous cycle */
}
case GCSpause: {
g->GCmemtrav = g->strt.size * sizeof(GCObject*);
restartcollection(g);
g->gcstate = GCSpropagate;
return g->GCmemtrav;
}
GCSpause是一个GC循环的开始, 不存在灰色对象, 因此清空灰色对象列表
然后标记根(全局)对象:mainthread(主线程(协程), 注册表(registry), 全局元表(metatable), 上次GC循环中剩余的finalize中的对象
在GSpause状态下标记的对象即是上面提到的根对象, 下面进入GCSpropagate阶段
case GCSpropagate: {
g->GCmemtrav = 0;
lua_assert(g->gray);
propagatemark(g);
if (g->gray == NULL) /* no more gray objects? */
g->gcstate = GCSatomic; /* finish propagate phase */
return g->GCmemtrav; /* memory traversed in this step */
}
在GSpause状态下,每次都会取出一个灰色对象(引用的值还没有被标记的对象), 对他引用的所有对象进行标记.
直到所有灰色对象都变成黑色对象,就会进入GCSatomic状态.
在分析GSatomic之前, 先保存一下上下文, 来看看GC屏障(barrier)是怎么回事.
增量GC的标记过程可能会被打断(这一点可以从`case GCSpropagate`看出), 当一个对象被标记为黑色后, Lua应用程序可能会重新对这个黑色对象进行操作,这时就需要屏障(barrier)来感知这一行为.
Lua的GC有两种GC屏障,向前屏障(luaC_barrier)和向后屏障(luaC_barrierback).
#define luaC_barrier(L,p,v) ( \
(iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ? \
luaC_barrier_(L,obj2gco(p),gcvalue(v)) : cast_void(0))
#define luaC_barrierback(L,p,v) ( \
(iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ? \
luaC_barrierback_(L,p) : cast_void(0))
void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
global_State *g = G(L);
lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
if (keepinvariant(g)) /* must keep invariant? */
reallymarkobject(g, v); /* restore invariant */
else { /* sweep phase */
lua_assert(issweepphase(g));
makewhite(g, o); /* mark main obj. as white to avoid other barriers */
}
}
void luaC_barrierback_ (lua_State *L, Table *t) {
global_State *g = G(L);
lua_assert(isblack(t) && !isdead(g, t));
black2gray(t); /* make table gray (again) */
linkgclist(t, g->grayagain);
}
这两种屏障效果是相同的,之所以有两种不同的形式是因为出于效率考虑, 这一点Roberto大神也有明确说过, 不过具体出于什么原因确没有说.
我grep了所有代码, 发现发现只有三种情况下会调用luaC_barrier, 分别是: 为C闭包设置上值, 为full userdata设置用户数据, 设置元表(metatable)
这些操作都有一个明显的特别, 做这些操作时, 只会改变少量的引用关系, 可能Roberto大神觉得这种情况下直接将父节点变灰是不值得的(因为变灰后,会重新遍历所有引用的值).
虽然像tbl[k] = v这种操作也仅仅改变了一个引用关系,但是在两次singlestep之间有可能对一个表进行多次tbl[k] = v这种操作, 这样看来将tbl节点直接变灰是值得的, 因为中间可能会有多种变化(忽略这些变化可能会让GC负担更轻).
除了GCSatomic阶段是必须一次执行的外,标记和清除阶段都是增量进行的, 如果在执行完GCSatomic阶段后, 必须要保证新建的对象(新建对象默认全是白色的)不会被误清除.
Lua在这一点有一个精巧的实现, 在GC中有两种白色值(暂时称为W1,和W2), 在执行完GCSatomic之后白色值就会从W1切换到W2(假设GCSatomic之前白色值为W1), 在清除阶段只会清除白色值为W1的对像,并将所有非白色的对像置为W2的白色,而新建的对象白色值也都为W2, 在下一轮GC循环中,同样只会清除白色值为W2的对象, 而在GCSatomic之后对建的对象默认颜色值都为W1,依次交替进行.
在luaC_barrier_函数中, keepinvariant返回非0代表当前标记阶段还没有完成,因此直接将对象v挂在灰色列表(global_State.gray)上去, 让singlestep自行消化, 如果标记阶段已完成, 则直接将对象o置为白色, 留待下一个GC循环再重新进行标记跟踪(因为在GCSatomic阶段之后的白色对象必然时新一轮的白色值).
luaC_barrierback_函数比较粗爆,直接将对象t变为灰色. 这里会出现两种情况:
1. 在GCSatomic之前被调用, 直接将其挂到global_State.gray列表中,GCSpropagate, GCSatomic中会自行标记处理
2. 在GCSatomic之后被调用, 产生barrier的对象A必为新一轮的白色, 而在sweeplist阶段也会将对象t置为新一轮的白色,同样不会影响对象A的生命周期
现在恢复一下上下文, 进入GCSatomic状态.
static void propagateall (global_State *g) {
while (g->gray) propagatemark(g);
}
case GCSatomic: {
lu_mem work;
propagateall(g); /* make sure gray list is empty */
work = atomic(L); /* work is what was traversed by 'atomic' */
entersweep(L);
g->GCestimate = gettotalbytes(g); /* first estimate */;
return work;
}
之所以会上来先检测g->gray,是因为luaC_barrier函数的存在,它个函数在调用reallymarkobject时有可能会操作变量global_State.gray.
下面来看GCSatomic中最重要的步骤, atomic函数.
static l_mem atomic (lua_State *L) {
global_State *g = G(L);
l_mem work;
GCObject *origweak, *origall;
GCObject *grayagain = g->grayagain; /* save original list */
lua_assert(g->ephemeron == NULL && g->weak == NULL);
lua_assert(!iswhite(g->mainthread));
g->gcstate = GCSinsideatomic;
g->GCmemtrav = 0; /* start counting work */
markobject(g, L); /* mark running thread */
/* registry and global metatables may be changed by API */
markvalue(g, &g->l_registry);
markmt(g); /* mark global metatables */
/* remark occasional upvalues of (maybe) dead threads */
remarkupvals(g);
propagateall(g); /* propagate changes */
work = g->GCmemtrav; /* stop counting (do not recount 'grayagain') */
g->gray = grayagain;
propagateall(g); /* traverse 'grayagain' list */
g->GCmemtrav = 0; /* restart counting */
convergeephemerons(g);
/* at this point, all strongly accessible objects are marked. */
/* Clear values from weak tables, before checking finalizers */
clearvalues(g, g->weak, NULL);
clearvalues(g, g->allweak, NULL);
origweak = g->weak; origall = g->allweak;
work += g->GCmemtrav; /* stop counting (objects being finalized) */
separatetobefnz(g, 0); /* separate objects to be finalized */
g->gcfinnum = 1; /* there may be objects to be finalized */
markbeingfnz(g); /* mark objects that will be finalized */
propagateall(g); /* remark, to propagate 'resurrection' */
g->GCmemtrav = 0; /* restart counting */
convergeephemerons(g);
/* at this point, all resurrected objects are marked. */
/* remove dead objects from weak tables */
clearkeys(g, g->ephemeron, NULL); /* clear keys from all ephemeron tables */
clearkeys(g, g->allweak, NULL); /* clear keys from all 'allweak' tables */
/* clear values from resurrected weak tables */
clearvalues(g, g->weak, origweak);
clearvalues(g, g->allweak, origall);
luaS_clearcache(g);
g->currentwhite = cast_byte(otherwhite(g)); /* flip current white */
work += g->GCmemtrav; /* complete counting */
return work; /* estimate of memory marked by 'atomic' */
}
说一下这个global_State.grayagain变量, 在进行GCSpropagate, 为了防止每次进入singlestep时global_State.gray上都有对象产生活锁, 对于可能反复变灰,或者二次变灰的对象都会挂在global_State.grayagain变量上留待GCSatomic阶段一次性标记.
* atomic函数刚开始就先保存g->grayagain, 因此为atomic函数中间不会让出, 为原子操作, 不会受barrier函数的影响, 而除此之外在GCSatomic阶段惟一能进入g->grayagain的就只有LUA_TTHREAD和weak table(这个类型永远不会为黑色), 重复去遍历g->grayagain没有意义
* atomic开始重新遍历(跟踪)根对象（当前thread, 注册表l_registry, 全局metatable, 线程相关的上值), 原因如下：
1. 在lstate.c中函数init_registry会改变global_State.l_registry的值，并且不会有barrier的调用
2. 根据lapi.c中的lua_setmetatable函数可知，在修改全局metatable表时，同样不会有barrier
3. 线程相关的上值经常变化，因为必须在atomic阶段重新遍历标记。
* atomic接着去遍历之前的grayagain(grayagain上会有弱表的存在), 并清理弱表的空间)
* atomic接着去调用separatetobefnz函数将带__gc函数的需要回收的(白色)对象放到global_State.tobefnz表中,留待以后清理
这里需要修改一下前面说过所有对象都在allgc链表的说法.
当对一个对像设置__gc函数时, 例如`setmetatable(tbl, {__gc == function() end})`, LuaVM会调用luaC_checkfinalizer函数将对像tbl从global_State.allgc链表上移除,并将其添加到global_State.finobj上(ps.从这里可以得出一个结论,__gc元表设置越早效率越高,因为这一操作需要遍历才实现).
* atomic重新使global_State.tobefnz上的所有对象全部可达, 不然global_State.tobefnz上的对象就有可能被singlestep的后续步骤清除, 这样当调用__gc(tbl)时, 就无法传入正确的tbl.
* atomic最后重新清理了一下弱表(global_State.tobefnz上的对象是有可能引用弱表的,如果这些弱表在此时还是白色的,同样需要阻止其被回收,但是其中的一些key需要重新考虑清除一下), 将当前白色值切换到新一轮的白色值(在此之后,所有新建的对象虽然也为白色,但是在GC循环走完之前并不会被回收), 准备进入GCSswpallgc状态.
* atomic在进入GCSswpallgc前会将global_State.sweepgc指向global_State.allgc上几乎所有对象,之所以用’几乎’这个词, 是因为它是通过函数`sweeplist`来做转换的, 这里不直接使用g->sweepgc = &g->allgc, 是希望g->sweepgc尽可能为&(g->allgc->next)的值. 这样做是原因是, 在进入GCSswpallgc状态后,整个GC又进入了增量模式, 此时可能会有很多新创建的对象(而这些对象是下一轮GC的白色值,因为必然不会被回收)挂在global_State.allgc上, g->sweepgc指向&(g->allgc->next)可以尽可能的避免这些额外干扰.
static void entersweep (lua_State *L) {
global_State *g = G(L);
g->gcstate = GCSswpallgc;
lua_assert(g->sweepgc == NULL);
g->sweepgc = sweeplist(L, &g->allgc, 1);
}
GCSatomic状态之后又进入增量模式，接着就是GCSswpallgc状态。
GCSswpallgc的作用就是将global_State.sweepgc上的所有死对象释放（上GCSatomic状态以前的白色值的对象)并将活对象重新标记为当前白色值。
接下来的GCSswpfinobj和GCSswptobefnz两个状态也调用了sweepstep函数。但是从上下文分析global_State.finobj和global_State.tobefnz链表上是不可能有死对象的，因此它们的作用仅仅是将这些对象重新设置为新一轮的白色。
GCSswpend用来释放mainthread上的一些空间，如：字符串表，连接缓冲区等。
整个GC大循环的最后一步就是GCScallfin状态，在这个状态会逐个取出global_State.tobefnz链表上的对象，然后调用其__gc函数，并将其放入global_State.allgc链表中，准备在下个GC循环回正式回收此对象（这也意味着对象可以在GC函数中被复活，同时这个被被复活的对象会失去其原有的__gc函数)
整个GC流程到此结束，有时间再详细分析关于弱表的实现。