Lua5.3 GC源码阅读(4)

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

Lua5.3 GC源码阅读(3)

接上篇, 在真正阅读luaC_step源码之前,先来看一下Lua的垃圾回收器对外提供了哪些可调参数, 以及这些参数是如何控制垃圾回收器的.

Lua提供了一个函数collectgarbage([opt[,arg]])用于控制GC的一些形为.

collectgarbage通过第一个参数opt来执行不同的功能:

“collect”: 执行一次完整的垃圾回收循环,这是默认选项.
“stop”: 停止垃圾回收器的运行, 在调用”restart”前,回收器只有被显式调用时才运行.
“restart”: 重新开始垃圾回收器的自动运行.
“count”: 以Kbytes为单位显示Lua使用的内存.
“isrunning”: 表示垃圾回收器是否在工作.
“step”: 单步运行垃圾回收器, 步长”大小”由arg控制.
“setpause”: 将arg设置为回收器的’间歇率’.
“setstepmul”: 将arg设置为回收器的’步进倍率’.

“collect/stop/restart/count/isrunning” 都是很直观, 重点应该是”step/setpause/setstepmul”是如何影响luaC_step的执行流程的.

先来看一下”step/setpause/setstepmul”都做了哪些操作.

//lapi.c
case LUA_GCCOUNT: {
  /* GC values are expressed in Kbytes: #bytes/2^10 */
  res = cast_int(gettotalbytes(g) >> 10);
 	break;
}
case LUA_GCSTEP: {	//"step"
	l_mem debt = 1;  /* =1 to signal that it did an actual step */
	lu_byte oldrunning = g->gcrunning;
	g->gcrunning = 1;  /* allow GC to run */
	if (data == 0) {
		luaE_setdebt(g, -GCSTEPSIZE);  /* to do a "small" step */
		luaC_step(L);
	}
	else {  /* add 'data' to total debt */
		debt = cast(l_mem, data) * 1024 + g->GCdebt;
		luaE_setdebt(g, debt);
		luaC_checkGC(L);
	}
	g->gcrunning = oldrunning;  /* restore previous state */
	if (debt > 0 && g->gcstate == GCSpause)  /* end of cycle? */
		res = 1;  /* signal it */
	break;
}
case LUA_GCSETPAUSE: {	//"setpause"
	res = g->gcpause;
	g->gcpause = data;
	break;
}
case LUA_GCSETSTEPMUL: {	//"setstepmul"
	res = g->gcstepmul;
	if (data < 40) data = 40;  /* avoid ridiculous low values (and 0) */
	g->gcstepmul = data;
	break;
}

//lstate.h
/* actual number of total bytes allocated */
#define gettotalbytes(g)        cast(lu_mem, (g)->totalbytes + (g)->GCdebt)

typedef struct global_State {
  ...
  l_mem totalbytes;  /* number of bytes currently allocated - GCdebt */
  l_mem GCdebt;  /* bytes allocated not yet compensated by the collector */
  lu_mem GCestimate;  /* an estimate of the non-garbage memory in use */
  int gcpause;  /* size of pause between successive GCs */
  int gcstepmul;  /* GC 'granularity' */
  ...
};

//lstate.c
#if !defined(LUAI_GCPAUSE)
#define LUAI_GCPAUSE    200  /* 200% */
#endif

#if !defined(LUAI_GCMUL)
#define LUAI_GCMUL      200 /* GC runs 'twice the speed' of memory allocation */
#endif

LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  int i;
  lua_State *L;
  global_State *g;
  LG *l = cast(LG *, (*f)(ud, NULL, LUA_TTHREAD, sizeof(LG)));
  if (l == NULL) return NULL;
  L = &l->l.l;
  g = &l->g;
  ...
  g->gcrunning = 0;  /* no GC while building state */
  g->GCestimate = 0;
  g->totalbytes = sizeof(LG);
  g->GCdebt = 0;
  g->gcpause = LUAI_GCPAUSE;
  g->gcstepmul = LUAI_GCMUL;
  ...
}

void luaE_setdebt (global_State *g, l_mem debt) {
  l_mem tb = gettotalbytes(g);
  lua_assert(tb > 0);
  if (debt < tb - MAX_LMEM)
    debt = tb - MAX_LMEM;  /* will make 'totalbytes == MAX_LMEM' */
  g->totalbytes = tb - debt;
  g->GCdebt = debt;
}

从上面代码可以得出两点结论:
1. global_State.totalbytes + global_State.GCdebt 就是整个LuaVM使用的全部内存总量
2. luaE_setdebt函数只会修改global_State.GCdebt, 但是不会改变整个LuaVM的使用内存总量
3. 步进倍率是靠变量global_State.gcstepmul控制的
4. 间歇率是靠变量global_State.gcpause来控制的
5. 根据注释可知GCestimate代表在使用的非垃圾内存

下面代码的就是GC如何通过global_State.gcstepmul和global_State.gcpause来精巧的控制步进倍率和间歇率

//lgc.c
static l_mem getdebt (global_State *g) {
  l_mem debt = g->GCdebt;
  int stepmul = g->gcstepmul;
  if (debt <= 0) return 0;  /* minimal debt */
  else {
    debt = (debt / STEPMULADJ) + 1;
    debt = (debt < MAX_LMEM / stepmul) ? debt * stepmul : MAX_LMEM;
    return debt;
  }
}

static void setpause (global_State *g) {
  l_mem threshold, debt;
  l_mem estimate = g->GCestimate / PAUSEADJ;  /* adjust 'estimate' */
  lua_assert(estimate > 0);
  threshold = (g->gcpause < MAX_LMEM / estimate)  /* overflow? */
            ? estimate * g->gcpause  /* no overflow */
            : MAX_LMEM;  /* overflow; truncate to maximum */
  debt = gettotalbytes(g) - threshold;
  luaE_setdebt(g, debt);
}


void luaC_step (lua_State *L) {
  global_State *g = G(L);
  l_mem debt = getdebt(g);  /* GC deficit (be paid now) */
  if (!g->gcrunning) {  /* not running? */
    luaE_setdebt(g, -GCSTEPSIZE * 10);  /* avoid being called too often */
    return;
  }
  do {  /* repeat until pause or enough "credit" (negative debt) */
    lu_mem work = singlestep(L);  /* perform one single step */
    debt -= work;
  } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause);
  if (g->gcstate == GCSpause)
    setpause(g);  /* pause until next cycle */
  else {
    debt = (debt / g->gcstepmul) * STEPMULADJ;  /* convert 'work units' to Kb */
    luaE_setdebt(g, debt);
    runafewfinalizers(L);
  }
}

回忆一下上篇内容:

1. global_State.GCdebt 代表着内存分配所产生的债务
2. checkGC函数保证只有global_State.GCdebt > 0 才会执行luaC_step.

getdebt会将当前债务(global_State.GCdebt)根据变量global_State.gcstepmul进行放大

luaC_step中的while循环会保证只有getdebt返回的债务值全部被偿还完之后才会退出(或者执行完了整个GC流程)

这样即可通过设置更高的global_State.gcstepmul值来达到增大步长

再来看setpause函数, 在不考虑边界情况下,下面代码可以看的更直观一些:

l_mem threshold = g->gcpause * g->GCestimate / PAUSEADJ;
luaE_setdebt(g, gettotalbytes(g) - threshold);

当gcpause=2*PAUSEADJ时, threshold = 2 * g->GCestimate.

在luaC_fullgc代码中可以确认当GC循环执行到GCScallfin状态以前,g->GCestimate与gettotalbytes(g)必然相等.

暂时不考虑GCScallfin状态对内存的影响,setpuase函数会将g->GCdebt设置为负的g->GCestimate, 这将会导致,当内存分配超过g->GCestimate之后才会再次开始垃圾回收循环, 与g->gcpause的含义一致.

void luaC_fullgc (lua_State *L, int isemergency) {

luaC_runtilstate(L, bitmask(GCScallfin)); /* run up to finalizers */
/* estimate must be correct after a full GC cycle */
lua_assert(g->GCestimate == gettotalbytes(g));
luaC_runtilstate(L, bitmask(GCSpause)); /* finish collection */
g->gckind = KGC_NORMAL;
setpause(g);
}

下篇接着看singlestep是如何执行标记清除的.

Lua5.3 GC源码阅读(2)

上篇已经提到表作为lua中的一种对象,其生命周期是被GC管理的.

下面就从一个表的创建来分析GC模块是如何接管其生命周期的.

先来看一段lua代码

--a.lua
local a = {}
a.foo = "bar"

使用`luac -p -l a.lua` 得到如下结果

main <a.lua:0,0> (3 instructions at 0x20d7a50)
0+ params, 2 slots, 1 upvalue, 1 local, 2 constants, 0 functions
        1       [1]     NEWTABLE        0 0 0
        2       [2]     SETTABLE        0 -1 -2 ; "foo" "bar"
        3       [2]     RETURN          0 1

NEWTABLE对就OPCODE中的OP_NEWTABLE.

根据lopcodes.h中的定义, OP_NEWTABLE使用A,B,C三个寄存器,其中寄存器A用来接收创建的table, 寄存器B和C用于为新创建的table预分配array部分大小和hash部分大小.

在lvm.c中找到代码片段刚好印证了上面的解释.

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;
}

从luaH_new的定义可以得到一个结论,所有需要GC管理的对象都会调用luaC_newobj函数来分配内存空间.

//ltable.c
Table *luaH_new (lua_State *L) {
  GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
  Table *t = gco2t(o);
  t->metatable = NULL;
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}

在luaC_newobj函数中, 首先调用luaM_newobject来为对象分配内存, 然后为正确管理此对象生命周期做了一些初始化操作.
1. 将对象标记为白色(lua5.3中使用的是三色标记清除垃圾回收算法)
2. 为此对象标记类型(类型的含义与上篇tt_字段的类型含义相同)
3. 将其挂在global_State上的allgc链表上.

由此可以得出一个结论,所有需要GC管理生命周期的对象都在allgc的链表上

//lgc.c
Object *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;
}

在luaM_newobject中就只做了两件事:

1. 调用g->frealloc进行分配内存,如果分配失败的话,执一次fullgc,再次尝试分配
2. 将新增使用内存量, 加入到global_State中的GCdebt字段中.

其中g->frealloc是在调用lua_newstate创建lua_State时指定的, 值得一提的是当lua_Alloc中的参数ptr为null时, osize参数为要new的对象的类型.

//lua.h
LUA_API lua_State *(lua_newstate) (lua_Alloc f, void *ud);
typedef void * (*lua_Alloc) (void *ud, void *ptr, size_t osize, size_t nsize);
//lmem.h
#define luaM_newobject(L,tag,s) luaM_realloc_(L, NULL, tag, (s))
//lmem.c
void *luaM_realloc_ (lua_State *L, void *block, size_t osize, size_t nsize) {
   void *newblock;
   global_State *g = G(L);
   size_t realosize = (block) ? osize : 0;
   lua_assert((realosize == 0) == (block == NULL));
 #if defined(HARDMEMTESTS)
   if (nsize > realosize && g->gcrunning)
     luaC_fullgc(L, 1);  /* force a GC whenever possible */
 #endif
   newblock = (*g->frealloc)(g->ud, block, osize, nsize);
   if (newblock == NULL && nsize > 0) {
     lua_assert(nsize > realosize);  /* cannot fail when shrinking a block */
     if (g->version) {  /* is state fully built? */
       luaC_fullgc(L, 1);  /* try to free some memory... */
       newblock = (*g->frealloc)(g->ud, block, osize, nsize);  /* try again */
     }
     if (newblock == NULL)
       luaD_throw(L, LUA_ERRMEM);
   }
   lua_assert((nsize == 0) == (newblock == NULL));
   g->GCdebt = (g->GCdebt + nsize) - realosize;
   return newblock;
}

OP_NEWTABLE的最后一步就是调用checkGC, 如果有未偿还的债务,就执行一次luaC_step.

//lvm.c
#define checkGC(L,c)  \
  { luaC_condGC(L, L->top = (c),  /* limit of live values */ \
		   Protect(L->top = ci->top));  /* restore top */ \
     luai_threadyield(L); }
//lgc.h
 #define luaC_condGC(L,pre,pos) \
         { if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; \
           condchangemem(L,pre,pos); }

Lua中的GC实现为’增量标记-清除回收器’, 每次调用luaC_step都会执行一次增加回收.

到目前为止, GC可以通过luaC_newobj和luaC_condGC来获得哪些对象需要被其管理生命周期, 并且什么时间触发增量GC操作.

后面开始分析luaC_step函数.

Lua5.3 GC源码阅读(1)

最近Lua 5.4 work1已经发布了, 其中GC最大的变化就是增加了分代GC的实现, 而GC在动态语言中一向是重中之重. 趁着这个机会, 我打算具体比较一下Lua5.3和Lua5.4中GC实现到底是如何变迁的, 根据以往的经验来看, 这其中必然充满各种精巧的设计.

Lua5.3的GC源码以前就断断续续看过一次了, 这次打算从头再分析一遍, 并做一下笔记为分析Lua5.4 GC做准备.

在Lua中字符串、表、用户数据、函数、线程、 内部结构等对象,都使用GC模块进行管理.

在分析GC流程前先做一些准备工作, 比如lua中的Value是如何实现的.

  //lobject.h

  /*
  ** Common type for all collectable objects
  */
  typedef struct GCObject GCObject;


  /*
  ** 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


  /*
  ** Common type has only the common header
  */
  struct GCObject {
    CommonHeader;
  };

 /*
  ** 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代码中,全部是以TValue来表示的,而这个TValue到底是哪种类型是靠tt_字段来标识的.

tt_字段中的bits0-3用来表示基础类型可选值如下.

  //lua.h
  #define LUA_TNIL                0
  #define LUA_TBOOLEAN            1
  #define LUA_TLIGHTUSERDATA      2
  #define LUA_TNUMBER             3
  #define LUA_TSTRING             4
  #define LUA_TTABLE              5
  #define LUA_TFUNCTION           6
  #define LUA_TUSERDATA           7
  #define LUA_TTHREAD             8

一些基础类型中可能会有不同的变种,tt_字段的bits4-5用来表示每个基础类型中更具体的子类型, 在lobject.h中定义如下:

 /*
  ** LUA_TFUNCTION variants:
  ** 0 - Lua function
  ** 1 - light C function
  ** 2 - regular C function (closure)
  */

  /* Variant tags for functions */
  #define LUA_TLCL        (LUA_TFUNCTION | (0 << 4))  /* Lua closure */
  #define LUA_TLCF        (LUA_TFUNCTION | (1 << 4))  /* light C function */
  #define LUA_TCCL        (LUA_TFUNCTION | (2 << 4))  /* C closure */


  /* Variant tags for strings */
  #define LUA_TSHRSTR     (LUA_TSTRING | (0 << 4))  /* short strings */
  #define LUA_TLNGSTR     (LUA_TSTRING | (1 << 4))  /* long strings */


  /* Variant tags for numbers */
  #define LUA_TNUMFLT     (LUA_TNUMBER | (0 << 4))  /* float numbers */
  #define LUA_TNUMINT     (LUA_TNUMBER | (1 << 4))  /* integer numbers */

tt_字段的bit6中来表示此value是否可回收, 其中宏定义同样在lobject.h中定义

  /* Bit mark for collectable types */
  #define BIT_ISCOLLECTABLE       (1 << 6)

在lobject.h中提供了一组宏用于获取tt_字段中的各种含义

  #define val_(o)         ((o)->value_)

  /* raw type tag of a TValue */
  #define rttype(o)       ((o)->tt_)

  /* tag with no variants (bits 0-3) */
  #define novariant(x)    ((x) & 0x0F)

  /* type tag of a TValue (bits 0-3 for tags + variant bits 4-5) */
  #define ttype(o)        (rttype(o) & 0x3F)

  /* type tag of a TValue with no variants (bits 0-3) */
  #define ttnov(o)        (novariant(rttype(o)))

其中CommonHeader中的tt字段与TValue中的tt_字段的bits0-5是一致的.

给silly增加热更新

最新抽了点时间给silly增加了一个silly.patch模块,用于对热更新提供一些有限的支持。

热更新最麻烦之处莫过于“数据迁移”, 即怎么使新函数(要更新的函数)以“运行时数据”的状态运行。

其实http这类无状态协议是最为简单的,因为他们不需要“数据迁移”的过程。http的这种架构,使得所有的函数都是无副作用的,所有的数据在请求结束给出Response的同时, 数据就已经存入了数据库。当需要热更新函数时,根本就不需要考虑数据的问题,直接替换就可以完美解决。

与此相对的是,通常的服务器或应用程序都会有“非局部变量”的存在(所有生命周期不是在函数被call时建立,ret时销毁的变量都可以认为是非局部变量,比如lua中的全局变量或上值)。

对于这类程序,在热更新时,就必须要小心处理这类数据,使热更新之后的函数安全的以“运行时数据”所代表的状态运行。当涉及数据结构或功能变化较大时,这种“数据迁移”的安全性很难面面俱道,也很难提出一个通用的解决方案。

再考虑一下解bug的场景,大多数情况下,bug可能只会出现在某几行代码或某几个函数之中,一般会延续之前的设计而不太会有大量数据结构或大量代码的改变。

在这种情况下,热更新实现的复杂度就可以降低不止一个数量级。在实现上也可以有更好的保证。

因此,这次新增的silly.patch模块也仅仅对热更新bugfix做了一些支持。


silly.patch模块只提供一个功能,即将a函数中的所有“非局部变量” patch 到b函数中去,以便b函数以a当前的运行时状态继续运行。

借助luaVM提供了一组调试函数,使得我们可以方便的对a,b两个函数进行“数据迁移”。

比如,使用debug.getinfo来遍历出a,b两个函数的所有上值,然后使用debug.getuservalue和debug.upvaluejoin将b函数的所有上值均引用至a函数的上值。这样就可以使逻辑以b函数的代码以a函数的数据去运行。

但是这里面有些问题需要处理.

a,b两个函数必然不会相同(不然也不会去更新了),那也就不能保证a函数的第一个上值意义与b函数的第一个上值意义完全相同。比如下面代码:

local foo = "hello"
local bar = "world"
local function f1()
	print(foo)
	print(bar)
end
local function f2()
	print(bar)
	print(foo)
end

如果a函数是f1, b函数是f2。f1的第二个上值是foo(因为使用了print,所以第一个上值是_ENV),而f2的第二个上值是bar。如果按上值的id去patch,上述代码就会出现很诡异的bug。

因此silly.patch模块做了一个简单的约定,如果要拿b函数去修复a函数,就必须保证a函数中使用的所有上值在b函数中必须不得改变其意义。

有了这个约定,silly.patch就可以根据“非局部变量”的名字去进行“数据迁移”。 比如f1使用了上值foo, f2中只要foo的意义不变,不管他属于f2的第几个上值,都可以保证“数据迁移”的正确性。

还需要注意的是,如果a和b函数的上值变量是函数时,需要递归对其上值函数进行“数据迁移”。


silly.patch仅仅是对热更新做了支持,他并不是一个完整的热更新模块。还需要对silly.patch进行一定的封装才可以使用。

在进行封装时一般的步骤为,生成新函数b,找到等修复函数a, 执行silly.patch, 将a的数据迁移到b函数上, 然后使用b函数替换为a函数。

生成新函数b,一般是通过load/loadfile来生成一个chunk, 然后调用chunk来生成.

为了避免在调用chunk函数时有副作用,一般在调用load/loadfile时,会传入一个新的_ENV表作来将chunk置于沙盒之中,如果有顾虑新的函数b会使用新的全局变量(即函数a从没使用过的全局变量),可以在整个热更新的最后, 将load/loadfile时传入的_ENV表有选择性的合并运行时环境中(只合并运行时环境不存在的变量)。

比较麻烦的是怎么找到要修复的函数并进行替换,lua中提供的debug接口中并不能获取一个chunk中的所有函数。

当然就算提供了这样一个接口也很难使用。在lua中,function是first class, 这就意味着当你定义两个变量指向同一个函数时,这个函数就拥有了两个名字。

因此在我们约定不给可能会热更新的函数起别名的情况下,有两种实现方式。

一种不太通用的实现是,在每个chunk中实现两个函数,一个函数提供通过名字对chunk中的任意函数进行定位,一个函数提供通过名字对chunk中任意函数进行替换。这种方法比较麻烦,而且容易出错。

另一种方式依赖于一个事实,一般每一个lua模块都会导出一些接口函数供其他函数使用,那么就从这些接口上做文章。

比如我们想要将module模块中a函数热更新为b函数,我们可以直接require “module”得到module模块的接口函数表,然后再根据名字定位到相应的函数,如果替换则直接将module模块函数表中的相应字段重新赋值就可以了。

如果想要热更module中某个local函数,就比较很麻烦,但是也可以办到。在上文silly.patch的实现中可以得知,如果一个函数有上值,而且上值是一个函数的情况下,silly.patch同样会对上值函数进行“数据迁移”,这也意味着,上值函数同时也会被热更新到最新。所以,在需要热更新某个local函数时,可以通过热更调用他的模块接口函数来实现。

但是需要注意的是,这里有一个坑。如果函数module.a1和函数module.a2同时引用了module中的一个名为foo的局部函数。如果只热更module.a1的话,module.a2将依然会使用旧的foo函数。

基于通用考虑,在silly的console模块提供了一个patch命令, 这个命令正是基于方式2来实现的。