接上篇, 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流程到此结束，有时间再详细分析关于弱表的实现。