lua gc 源代码分析（干货）

KaaPexei

前两篇文章介绍了xlua是如何和C#通信的
今天我想分享下luaGC的原理和源代码分析。因为我发现大多数程序员对lua只停留在会用的阶段，关于内部的原理确知之甚少，大家的习惯可能都是有什么不明白的去网上搜搜，然后了解一下，仅此而已。
那今天我们就从GC的原理出发，然后再配合着源代码分析下luaGC的整个流程。
一、luaGC的原理是怎样的呢？
我们首先从传统的最简单的Naive Mark and Sweep算法开始介绍，然后介绍其改进版Incremental Mark and Sweep算法。

1、Naive Mark and Sweep算法
在开始讲算法流程之前，首先我们要对几个点进行说明，有个概念
1）所有新创建的对象，都要被放入一个单向链表中，新创建的对象实例，直接放置于列表头部。
2）所有被创建的实例，均分为可达和不可达状态，可达意味着它正在被使用，或者有潜在被使用的可能，那么global变量，在栈中的变量以及在寄存器中的变量以及被这些变量引用的变量则被视为可达的
3）GC则是以全局变量，栈和寄存器作为起点开始标记的。

有了以上的概念之后，我们看下GC的流程是怎样的。
1）GC开始前，新创建的对象均放置于allgc链表中
2）GC开始，进入标记阶段，从起始点（如栈）开始，标记所有被关联到的对象
3）标记结束后，进入清除阶段，所有未被标记的实例将被释放(未被标记的说明不可达，不可达就说明没用到，就是垃圾)，而被标记的对象则清除标记（清除标记是为了下一轮GC重新开始标记），本次gc结束

注意：
以上步骤只能一次性执行完，如果步骤被拆分了，那么在标记阶段结束之后，新创建的对象在本轮gc中将无法继续被标记，因此在清除阶段，这个新创建而可能会被使用到的对象将被清除掉，导致不可挽回的bug。

这种算法的缺点在于，一步到位的执行，会在瞬时极大影响程序运行的性能，为了解决这个问题，就必须要允许gc能够分n次执行，每次只执行其中的一小部分，将gc的性能开销均摊掉。基于这样的现实需求，传统的Mark and Sweep算法，只对对象标记表示不可清除，不标记表示可清除这种方式就显得不合时宜了，如果gc要分步骤执行，我们需要一种方式去记录标记的进度，需要一种方式灵活处理不断变化的对象之间的引用关系。

为此我们介绍另一种算法

2、Incremental Mark and Sweep算法
Incremental Mark and Sweep算法用的是三色标记法，每一轮gc处理中一共有3种颜色参与处理，分别是白色，灰色和黑色。
具体流程如下：
1)每个新创建的对象，将被标记为白色。
2)标记阶段：会将对象从白色标记为灰色，并放入一个专门放灰色对象的单向链表–gray列表中，这相当于记录了当前gc扫描的进度。
在lua中，gc的起始点是globals、stack和register，register在lua的gc中，并没有特别的意义，因为所有的操作都是在stack上进行的。因为mainthread和global_table包含gc起始点，因此他们要先push入gray列表中。

3)扫描阶段：gc对gray链表中的对象，一个一个进行扫描，扫描的过程就是将原本被标记为灰色的对象，标记为黑色，并遍历其所有引用的对象，将它们标记为灰色，并放入gray列表中，以等待下一次扫描。如此循环往复。 当gray链表为空时，意味着本轮gc标记阶段结束。

这一阶段扫描对象超过一定字节时本轮GC暂停，等待下次GC开始时继续扫描。带来的好处就是每次处理一部分，将gc处理的瞬时开销，均摊开来。

4)清理阶段：此时仍然为白色的实例，意味着它已经不可达，需要被清理，而黑色的则意味对象可达，不能被清除。

注意: 虽然多数对象经历标记阶段的时候，是从白色标记为灰色，但对于那种不可能引用其他对象的数据类型（如lua的string类型）是被直接被标记为黑色的。

看了上面的流程也许你觉得没什么，很简单对不对，但其实不是，下面我说几个问题，你可以思考一下

（1）如果在标记阶段，又有了新创建的对象怎么办？
    答案是为新创建的对象设置barrier，中文就是屏障的意思。barrier分为两种：
    一种是向前设置barrier，也就是直接将新创建的对象设置为灰色，并放入gray列表；
        这种情况，适用于已被标记为黑色的对象类型，为不会频繁改变引用关系的数据类型如lua的proto结构。
    另一种则是向后设置barrier，这种是将黑色对象设置为灰色，然后放入grayagain列表。
        这种情况适合被标记为黑色的对象类型会出现频繁改变引用关系情况的数据类型，如lua的table结构，也就是说，在两次调用gc功能的过程中，table中的同一个key，可能被赋值多个value，如果把这些value对象均标记为灰色，并放入gray列表，那么将会造成许多无谓的标记和扫描操作，因为这些value很可能不再被引用，需要被回收，因此，只要把已经被标记为黑色的table，重新设置为灰色，是避开这个性能问题的良好方式。

（2）前面说了向后设置barrier的对象会放入grayagain列表，那grayagain列表又是什么时候变黑的呢？
    luaGC的过程中会有个GCSatomic阶段，也就是原子阶段。为什么叫原子阶段呢？就是说这个步骤是不可分步执行的。grayagain列表会在这个阶段被扫描标记为黑色。

（3）GCSatomic阶段为什么不能分步执行呢？
    因为如果分步执行了，就同标记阶段没什么区别了， 如果总是有不断的新建对象怎么办？那岂不是永远到不了清理阶段。

（4）那如果到了GCSatomic阶段之后的阶段又有新建的对象会怎样呢？
    我们说过每个新创建的对象，将被标记为白色。那白色到最后会被清理的，这不就出bug了吗？如果你看过lua源码的话就会发现有两种白色，WHITE0BIT 和 WHITE1BIT
    如果本次GC清理WHITE0BIT 的话，那么到了GCSatomic阶段之后的阶段，新创建的对象就会标记为WHITE1BIT，所以到最后清理阶段也不会被清除。
    到了下次GC的流程的时候就会扫描WHITE1BIT对象，到了GCSatomic阶段之后的阶段新创建的对象就会标记为WHITE0BIT。
    依此循环往复。

以上就是luaGC的整个过程，下面我们会对照着源码进行上述步骤的分析。
二、源代码流程分析
我现在用的lua版本是5.3.5,其他版本可能略有差异。
这里我们也会带着问题去分析，有利于我们理解的更深刻。
1、什么时候开始触发的GC？入口在哪里呢？
// lgc.h
#define luaC_condGC(L,pre,pos) \
    { if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; \
      condchangemem(L,pre,pos); }

/* more often than not, 'pre'/'pos' are empty */
#define luaC_checkGC(L)     luaC_condGC(L,(void)0,(void)0)
在lua中GC的入口是通过luaC_checkGC(L)  触发的。触发时机一般在内存分配的接口中，比如创建table表，string,userdata等的时候，下面粘贴部分逻辑大家参考
//lapi.c
LUA_API void lua_createtable (lua_State *L, int narray, int nrec) {
  Table *t;
  lua_lock(L);
  t = luaH_new(L);
  sethvalue(L, L->top, t);
  api_incr_top(L);
  if (narray > 0 || nrec > 0)
    luaH_resize(L, t, narray, nrec);
  luaC_checkGC(L);          //检测GC
  lua_unlock(L);
}


LUA_API void *lua_newuserdata (lua_State *L, size_t size) {
  Udata *u;
  lua_lock(L);
  u = luaS_newudata(L, size);
  setuvalue(L, L->top, u);
  api_incr_top(L);
  luaC_checkGC(L);         //检测GC
  lua_unlock(L);
  return getudatamem(u);
}

LUA_API const char *lua_pushlstring (lua_State *L, const char *s, size_t len) {
  TString *ts;
  lua_lock(L);
  ts = (len == 0) ? luaS_new(L, "") : luaS_newlstr(L, s, len);
  setsvalue2s(L, L->top, ts);
  api_incr_top(L);
  luaC_checkGC(L);      //检测GC
  lua_unlock(L);
  return getstr(ts);
}
从入口luaC_checkGC(L) 我们可以看到，只有当GCdebt的值大于0的时候，才能触发gc运作机制，而gc运作的机制均是在luaC_step函数里执行：
//lgc.c
/*
** performs a basic GC step when collector is running
*/
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 */   //GC流程
    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);
  }
}
这个函数，首先获取了debt的字节大小，所有的gc流程都在 singlestep 函数里进行处理，这里需要注意的是，当lua解释器能被处理的内存字节总大小，小于debt+GCSTEPSIZE时，那么gc将是一步到位执行完毕（gc的初始状态就是GCSpause，在上述的逻辑中，如果while条件判断内，gcstate等于GCSpause的话，说明本轮gc已经彻底完结，即将进入下一个gc轮回中）。当创建的gc对象足够多时，每次触发luaC_step函数，只会处理至多debt+GCSTEPSIZE个字节的数据，当程序满足跳出while循环的条件后，如果一轮gc已经完整执行完毕，那么需要重新设置totalbytes和GCdebt变量的大小，这些操作在setpause函数内执行：
//lgc.c
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);
}
2、luaGC的流程是怎样的呢？

//lgc.c
static lu_mem singlestep (lua_State *L) {
  global_State *g = G(L);
  switch (g->gcstate) {
    case GCSpause: {
      g->GCmemtrav = g->strt.size * sizeof(GCObject*);
      restartcollection(g);                                         //开始回收，标记根节点
      g->gcstate = GCSpropagate;
      return g->GCmemtrav;
    }
    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 */
    }
    case GCSatomic: {
      lu_mem work;
      propagateall(g);  /* make sure gray list is empty */
      work = atomic(L);  /* work is what was traversed by 'atomic' */  //原子阶段，grayagain列表就是在这个接口中处理的
      entersweep(L);                                                   //开始清理
      g->GCestimate = gettotalbytes(g);  /* first estimate */;
      return work;
    }
    case GCSswpallgc: {  /* sweep "regular" objects */            //清理g->finobj列表
      return sweepstep(L, g, GCSswpfinobj, &g->finobj);
    }
    case GCSswpfinobj: {  /* sweep objects with finalizers */
      return sweepstep(L, g, GCSswptobefnz, &g->tobefnz);         //清理g->tobefnz列表
    }
    case GCSswptobefnz: {  /* sweep objects to be finalized */
      return sweepstep(L, g, GCSswpend, NULL);
    }
    case GCSswpend: {  /* finish sweeps */                        //清理结束
      makewhite(g, g->mainthread);  /* sweep main thread */               
      checkSizes(L, g);
      g->gcstate = GCScallfin;
      return 0;
    }
    case GCScallfin: {  /* call remaining finalizers */
      if (g->tobefnz && g->gckind != KGC_EMERGENCY) {
        int n = runafewfinalizers(L);                            //回收后调用lua对象的gc方法
        return (n * GCFINALIZECOST);
      }
      else {  /* emergency mode or no more finalizers */
        g->gcstate = GCSpause;  /* finish collection */            //回收结束
        return 0;
      }
    }
    default: lua_assert(0); return 0;
  }
}
上面的接口就是luaGC的具体流程，相比上面的原理分析多了几个阶段，但是大同小异，我已经将主要部分做了注释，相信你能有个大概的了解，如果想更详细的话请看源码深入研究。

3、新创建的对象是在哪里设置的barrier呢？
看代码
//lgc.h
#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))


//lgc.c
/*
** barrier that moves collector forward, that is, mark the white object
** being pointed by a black object. (If in sweep phase, clear the black
** object to white [sweep it] to avoid other barrier calls for this
** same object.)
*/
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 */     //在原子阶段之后标记另一种白色
  }
}


/*
** barrier that moves collector backward, that is, mark the black object
** pointing to a white object as gray again.
*/
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);                              //这是向后设置barrier，这种是将黑色对象设置为灰色，然后放入grayagain列表。
}
通过上面代码的注释，在结合之前我们讲的部分正好对应上了。那调用又是在哪调用的呢？
下面粘贴部分代码我们看下
//lapi.c

LUA_API void lua_setuservalue (lua_State *L, int idx) {
  StkId o;
  lua_lock(L);
  api_checknelems(L, 1);
  o = index2addr(L, idx);
  api_check(L, ttisfulluserdata(o), "full userdata expected");
  setuservalue(L, uvalue(o), L->top - 1);
  luaC_barrier(L, gcvalue(o), L->top - 1);              //向前设置barrier
  L->top--;
  lua_unlock(L);
}

LUA_API void lua_rawset (lua_State *L, int idx) {
  StkId o;
  TValue *slot;
  lua_lock(L);
  api_checknelems(L, 2);
  o = index2addr(L, idx);
  api_check(L, ttistable(o), "table expected");
  slot = luaH_set(L, hvalue(o), L->top - 2);
  setobj2t(L, slot, L->top - 1);
  invalidateTMcache(hvalue(o));
  luaC_barrierback(L, hvalue(o), L->top-1);             //向后设置barrier
  L->top -= 2;
  lua_unlock(L);
}


LUA_API void lua_rawseti (lua_State *L, int idx, lua_Integer n) {
  StkId o;
  lua_lock(L);
  api_checknelems(L, 1);
  o = index2addr(L, idx);
  api_check(L, ttistable(o), "table expected");
  luaH_setint(L, hvalue(o), n, L->top - 1);
  luaC_barrierback(L, hvalue(o), L->top-1);             //向后设置barrier
  L->top--;
  lua_unlock(L);
}
至此luaGC的流程我们就分析完了，有很多细节的地方由于篇幅的关于并没有深入分析，之后找时间还会分享，欢迎关注。