lua gc

对于内存的管理，是程序在应用的时候的必需知识点。而lua的垃圾回收机制十分优秀，值得一读。

GC算法

大体原理是遍历系统中的所有对象，看哪些对象没有被引用，没有引用关系的就认为是可以回收的对象，可以删除 。

这里的关键在于，如何找出没有“引用”的对象。

引用计数

使用引用计数的GC算法，会在一个对象被引用的情况下将该对象的引用计数加一 ，反之减一。 如果引用计数为0 ，那么就是没有引用的对象。 引用计数算法的优点是不需要扫描每个对象，对象本身的引用计数只需要减到0，就会被回收。 缺点是会有循环引用问题。

循环引用，比如说A和B两个对象，相互引用了对方作为自己的成员变量。只有当自己销毁的时候才能将成员变量的引用计数-1。但是因为A对象的销毁又依赖于B对象，B对象销毁又依赖于A对象。这样就造成了循环引用的问题。

标记清除算法（ Mark and Sweep ）

它的原理是每一次做GC的时候，首先扫描并且标记系统中的所有对象，被扫描并且标记到的对象认为是可达的（ reachable ），这些对象不会被回收；反之，没有被标记的对象认为是可以回收的。 Lua采用的就是这种算法 。

双色标记清除算法

早期的Lua 5.0使用的是双色标记清除算法，该算法的原理是 ：系统中的每个对象非黑即白，也就是要么被引用，要么没有被引用。
具体操作是这样的：

• 新分配的对象是白色的
• 标记阶段将所有可到达的对象变黑
• 扫描阶段将释放所有白色（无法到达）的对象，并将所有黑色（幸存的）对象的颜色变回白色，等待下一轮的GC检查

这个算法的缺陷在于，每个对象的状态是“二元”的，每个对象只可能有一种状态，不能有其他中间状态，这就要求这个算法每次做GC操作时不可被打断地一次性扫描并清除完所有对象。
如果在遍历对象链表时标记每个对象颜色的过程中被打断，此时新增了一个对象，那么应该将这个对象标记为白色还是黑色？如果标记为白色，假如GC已经到了回收阶段，那么这个对象就会在没有遍历其关联对象的情况下被回收；如果标记为黑色，假如GC已经到了回收阶段，那么这个对象在本轮GC中并没有被扫描过就认为是不必回收的 。 可以看到，在双色标记清除算法中，标记阶段和回收阶段必须合在一起完成。不能被打断，也就意味着每次GC操作的代价极大。在GC过程中，程序必须暂停下来，不能进行其他操作。

三色增量标记清除算法

从Lua 5.1开始，采用了在该算法的基础上改进的三色增量标记清除算法。与前面的算法相比，这个算法中每个对象的颜色多了一种（实际上，在Lua中是4种，后面再展开讨论）。 这样的好处在于：它不必再要求GC一次性扫描完所有的对象，这个GC过程可以是增量的，可以被中断再恢复并继续进行的 。
3种颜色的分类如下：

• 白色： 当前对象为待访问状态，表示对象还没有被GC标记过，这也是任何一个对象创建后的初始状态。 换言之，如果一个对象在结束GC扫描过程后仍然是白色，则说明该对象没有被系统中的任何一个对象所引用，可以回收其空间了
• 灰色： 当前对象为待扫描状态，表示对象已经被GC访问过，但是该对象引用的其他对象还没有被访问到
• 黑色： 当前对象为己扫描状态，表示对象已经被GC访问过，并且该对象引用的其他对象也被访问过了

具体操作是这样的：

• 每个新创建的对象颜色为白色
• 初始化阶段，遍历gc root链表，把有引用的对象节点从白色置为灰色，并且放入到灰色节点链表中
• 标记阶段，当灰色链表中还有未扫描的元素（灰色链表非空），从中取出一个对象节点并将其标记为黑色，遍历这个对象关联的其他所有对象．如果是白色，标记为灰色，加入灰色链表中
• 回收阶段，遍历所有对象，如果为白色，这些对象都是没有被引用的对象，逐个回收。否则，重新加入对象链求中等待下一轮的 GC检查（黑色变白色，等待下次检查）。

可以看到，引入了灰色节点的概念后，算法不再要求一次性完整执行完毕，而是可以把已经扫描但是其引用的对象还未被扫描的对象置为灰色。 在标记阶段中，只要灰色节点集合中还有元素在，那么这个标记过程就会继续下去，即使中间被打断转而执行其他操作了，也没有关系 。

然而即使是这样，却仍然有另一个没有解决的问题。 从上面的算法可以看出，没有被引用的对象的颜色在扫描过程中始终保持不变，为白色 。 那么，假如一个对象在GC过程的标记阶段之后创建，根据前面对颜色的描述，它应该是白色的，这样在紧跟着的回收阶段，这个对象就会在没有被扫描标记的情况下被认为是没有被引用的对象而删除 。

因此， Lua的GC算法除了前面的三色概念之外，又细分出来一个“双白色”的概念 。 简单地说， Lua中的白色分为“当前白色”和“非当前白色”。 这两种白色的状态交替使用，第N次GC使用的是第一种白色，那么下一次就是另外一种，以此类推。

代码在回收时会做判断，如果某个对象的白色不是此次GC使用的白色状态，那么将不会认为是没有被引用的对象而回收，这样的白色对象将留在下一次GC中进行扫描，因为在下一次GC中上一次幸免的白色将成为这次的回收颜色。

GC的全流程

Lua内部用一个宏表示哪些数据类型需要进行GC ( Garbage Collection，垃圾回收）操作 ：

#define iscollectable(o) (ttype(o) >= LUA_TSTRING)

可以看到， LUA_TSTRING（包括LUA_TSTRING）之后的数据类型都需要进行GC操作 。

需要进行GC操作的数据类型都会有一个CommonHeader宏定义的成员，并且这个成员在结构体定义的最开始部分。

#define CommoHeader GCObject *next; lu_byte tt; lu_byte marked //next：GCObject链表指针，这个指针将所有GC对象都链接在一起形成链表，tt：表示数据的类型，即[lua数据类型](https://github.com/losophy/losophy.github.io/issues/109)的宏，marked : 标记字段，用于存储前面提到的几种颜色

marked具体值定义如下：

#define WHITE0BIT	0 //0型白色
#define WHITE1BIT	1   //l型白色
#define BLACKBIT	2
#define FINALIZEDBIT	3  //FINALIZEDBIT用于标记没有被引用需要回收的 udata 。 udata 的处理与其他数据类型不同，由于它是用户传入的数据，它的回收可能会调用用户注册的GC函数，所以统一来处理。
#define KEYWEAKBIT	3  //用于标记弱表中的键的weak属性
#define VALUEWEAKBIT	4 //T用于标记弱表中的值的weak属性
#define FIXEDBIT	5  //用于表示该对象不可回收，仅用于lua_State对象自身的标记
#define SFIXEDBIT	6 //用于表示该对象不可回收，标记了一系列Lua语法中的关键字对应的字符串为不可回收字符串，具体可以看看luaXinit函数的实现
#define WHITEBITS	bit2mask(WHITE0BIT, WHITE1BIT)

这里WHITE0BIT和WHITE1BIT就是前面提到的两种白色状态，称为0型白色和l型白色。 当前的白色见lobal_State中的 currentwhite，而otherwhite宏用于表示非当前GC将要回收的白色类型 。 切换白色，需要使用changewhite宏 ； 要得到当前的白色状态，则使用luaC_white宏 。

在保存全局状态的global_State结构体中，有以下几个与GC相关的数据成员：

typedef struct global_State {
  lu_byte currentwhite;//存放当前GC的白色
  lu_byte gcstate;  //存放GC状态，分别有以下几种 ： GCS pause （暂停阶段） 、 GCSpropagate（传播阶段，用于遍历灰色节点检查对象的引用情况）、 GCSsweepstring （字符串回收阶段） , GCSsweep （回收阶段，用于对除了字符串之外的所有其他数据类型进行回收）和GCSfinalize （终止阶段） 。
  int sweepstrgc;  //字符串回收阶段，每次针对字符串散列桶的一组字符串进行回收，这个值用于记录对应的散列桶索引 。
  GCObject *rootgc;  //存放待GC对象的链表，所有对象创建之后都会放入该链表中
  GCObject **sweepgc; //待处理的回收数据都存放在rootgc链表中，由于回收阶段不是一次性全部回收这个链表的所有数据，所以使用这个变量来保存当前回收的位置，下一次从这个位置开始继续回收操作
  GCObject *gray;  //存放灰色节点的链表
  GCObject *grayagain; //存放需要一次性扫描处理的灰色节点链表，也就是说，这个链表上所有数据的处理需要一步到位，不能被打断
  GCObject *weak;  //存放弱表的链表
  GCObject *tmudata;  //所有带有GC元方法的 udata存放在一个链表中，这个成员指向这千链表的最后一个元素
  lu_mem GCthreshold;//开始进行GC的阔值，当totalbytes大于这个值时开始自动GC
  lu_mem totalbytes;  //当前分配的内存大小
  lu_mem estimate; //一个估计值，用于保存实际在用的内存大小 
  lu_mem gcdept;  //用于在单次GC之前保存待回收的数据大小
  int gcpause;  //用于控制下一轮GC开始的时机
  int gcstepmul; //控制GC的回收速度
  ...
} global_State;

新创建对象

从前面的分析可以知道，对于每个新创建的对象，最基本的操作就是将对象的颜色设置为白色，意指本次GC还未扫描到的对象，同时将对象挂载到扫描过程会遍历的链表上 。 基本思想就是如此，但是针对不同的数据类型，会有不同的处理。

一般的数据类型调用的是luaC_link函数

void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  global_State *g = G(L);
  o->gch.next = g->rootgc;
  g->rootgc = o;//将对象挂载到 rootgc链表上
  o->gch.marked = luaC_white(g);//设置颜色为白色
  o->gch.tt = tt;//设置数据的类型
}

但是UpValue和udata类型的数据的创建过程有些不一样。
先来看UpValue，新建一个UpValue类型的数据，调用的是luaC_linkupval函数 。

void luaC_linkupval (lua_State *L, UpVal *uv) {
  global_State *g = G(L);
  GCObject *o = obj2gco(uv);
  o->gch.next = g->rootgc;  /* link upvalue into `rootgc' list */
  g->rootgc = o;
  if (isgray(o)) { 
    if (g->gcstate == GCSpropagate) {
      gray2black(o);  /* closed upvalues need barrier */
      luaC_barrier(L, uv, uv->v);
    }
    else {  /* sweep phase: sweep it (turning it into white) */
      makewhite(g, o);
      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
    }
  }
}

这里的疑问是，前面的数据类型在最开始的时候 ，都是将颜色设置为白色，而针对UpValue,则是根据颜色是不是灰色来做后面的一些操作 。 原因在于， UpValue是针对已有对象的间接引用，所以它的处理在对象颜色是灰色的情况下区分了两种情况 。

• 如果当前在扫描阶段，那么将对象从灰色变成黑色 。 需要注意的是，到这一步需要加barrier
• 如果不是在扫描阶段，都置为白色 。将其回收， 其实这个表达并不完全准确 。 这里置为白色，我的理解和创建其他类型数据的函数luaC_link一样，都是一个创建对象的正常流程

再来看udata数据的创建：

Udata *luaS_newudata (lua_State *L, size_t s, Table *e) {
  Udata *u;
  if (s > MAX_SIZET - sizeof(Udata))
    luaM_toobig(L);
  u = cast(Udata *, luaM_malloc(L, s + sizeof(Udata)));
  u->uv.marked = luaC_white(G(L));  /* is not finalized */
  u->uv.tt = LUA_TUSERDATA;
  u->uv.len = s;
  u->uv.metatable = NULL;
  u->uv.env = e;
  /* chain it on udata list (after main thread) */
  u->uv.next = G(L)->mainthread->next;//任何时候创建的 udata ，在GC链表中都会放在mainthread之后 。 除此之外，这类型的数据与其他数据并无差别 。 之所以这么做，是因为udata是用户注册的C数据。 在回收时，我们可能会调用用户注册的函数，此时就需要把这些udata统一放在一个地方来处理，这样做是为了方便编写代码
  G(L)->mainthread->next = obj2gco(u);
  return u;
}

初始化阶段

前面提到过，Lua的GC过程是增益的 、 中间可以被打断的，每一次单独进入GC时，都会根据当前GC所处的阶段来进行不同的处理，这个入口函数是singlestep。

switch (g->gcstate) {
  case GCSpause: {
    markroot(L);  /* start a new collection */
    return 0;
  }

初始化阶段将从root节点出发，遍历root连表上的所有节点，将它们的颜色从白色变成灰色，加入到gray链表中 。 初始化阶段的入口是markroot函数 ：

static void markroot (lua_State *L) {
  global_State *g = G(L);
  g->gray = NULL;
  g->grayagain = NULL;
  g->weak = NULL;
  markobject(g, g->mainthread); //针对object，标记对象的颜色为灰色，最终调用reallymarkobject函数
  /* make global table be traversed before main stack */
  markvalue(g, gt(g->mainthread)); //针对TValue，标记对象的颜色为灰色，最终调用reallymarkobject函数
  markvalue(g, registry(L));
  markmt(g);
  g->gcstate = GCSpropagate;
}

再看看reallymarkobject：

static void reallymarkobject (global_State *g, GCObject *o) {
  lua_assert(iswhite(o) && !isdead(g, o));
  white2gray(o);
  switch (o->gch.tt) {
    case LUA_TSTRING: {// 对于字符串类型的数据，由于这种类型没有引用其他数据，所以略过将其颜色改为灰色的流程，直接将不是黑色的字符串对象回收即可
      return;
    }
    case LUA_TUSERDATA: {//对于 udata类型的数据，因为这种类型永远也不会引用其他数据，所以这里也是一步到位，直接将其标记为黑色。 另外，对于这种类型，还需要标记对应的metatable和env表
      Table *mt = gco2u(o)->metatable;
      gray2black(o);  /* udata are never gray */
      if (mt) markobject(g, mt);
      markobject(g, gco2u(o)->env);
      return;
    }
    case LUA_TUPVAL: {//对于UpValue类型的数据，如果当前是close状态的话，那么该UpValue 已经没有与其他数据的引用关系了，可以直接标记为黑色 。 至于open状态的 UpValue ，由于其引用状态可能会频繁发生变动，所以留待后面的remarkupvals函数进行原子性的标记
      UpVal *uv = gco2uv(o);
      markvalue(g, uv->v);
      if (uv->v == &uv->u.value)  /* closed? */
        gray2black(o);  /* open upvalues are never black */
      return;
    }
    case LUA_TFUNCTION: {
      gco2cl(o)->c.gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TTABLE: {
      gco2h(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TTHREAD: {
      gco2th(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    case LUA_TPROTO: {
      gco2p(o)->gclist = g->gray;
      g->gray = o;
      break;
    }
    default: lua_assert(0);
  }
}

可以看到，对于绝大部分类型的对象，这里只是简单地将其颜色改变为灰色并加入到gray链表中，但是有几个类型是区别处理的。

扫描标记阶段

扫描阶段就是遍历灰色对象链表来分析对象的引用情况，这个阶段是GC所有阶段中步骤最长的 。 整个过程分为两部分。 第一步首先遍历gray链表来标记所有数据，在这个过程中，有些数据需要重新扫描，这些数据会放在grayagain链表中，调用atomic函数重新进行扫描。 而第二步则是遍历grayagain链表，一次性扫描其中的数据 。

case GCSpropagate: {
      if (g->gray)
        return propagatemark(g);
      else {  /* no more `gray' objects */
        atomic(L);  /* finish mark phase */
        return 0;
      }
    }

这一步将扫描所有gray链表中的对象，将它们及其引用到的对象标记成黑色 。 需要注意的是，前面的初始化阶段是一次到位的，而这一步却可以多次进行，每次扫描之后会返回本次扫描标记的对象大小之和，其入口函数是propagatemark，再次扫描时，只要gray链表中还有待扫描的对象，就继续执行这个函数进行标记 。 当灰色链表已经遍历完毕时，进入atomic函数中完成标记阶段。

可以看到，第一步遍历gray链表中对象的处理是可以中断的，而第二步调用atomic函数的操作是原子的、不能被打断的，这也是atomic函数的名字由来 。 这是Lua 5.1的GC算法优于之前版本的GC算法的原因之一 ： 可以增量地来进行数据扫描，不会因为一次GC扫描操作导致整个系统被卡住很久 。

propagatemark函数与前面的reallymarkobject函数做的事情其实差不多，都是对对象标记颜色的动作 。 区别在于，这里将对象从灰色标记成黑色，表示这个对象及其所引用的对象都已经标记过 。 另一个区别在于，前面的流程不会递归对一个对象所引用的对象进行标记，而这里会根据不同的类型调用对应的traverse*函数进行标记。 在实际工作中，对每种类型的对象的处理还不太一样，下面逐个类型来看看 。

扫描Table对象

在traversetable函数中，如果扫描到该表是弱表，那么将会把该对象加入weak链表中，这个链表将在扫描阶段的最后一步进行一次不能中断的处理，这部分将在后面谈到 。 同时，如果该表是弱表，那么将该对象回退到灰色状态，重新进行扫描。 在不是弱表的情况下，将遍历标记表的散列部分及数组部分的所有元素 。

switch (o->gch.tt) {
    case LUA_TTABLE: {
      Table *h = gco2h(o);
      g->gray = h->gclist;
      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */
      return sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h);
    }

扫描函数对象

针对函数对象，进行处理的函数是traverseclosure，该函数主要是对函数中的所有UpValue进行标记。 相关代码如下：

case LUA_TFUNCTION: {
      Closure *cl = gco2cl(o);
      g->gray = cl->c.gclist;
      traverseclosure(g, cl);
      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
                           sizeLclosure(cl->l.nupvalues);
    }

扫描线程对象

针对线程对象，这里的处理是将该对象从gclist中摘下来，放入grayagain链表中，同时将颜色退回到灰色，以备后面的原子阶段再做一次扫描 。 因为thread上关联的对象是Lua运行时的状态，变化很频繁，所以这里只是简单地放在grayagain链表中 ， 后面再一次性标记完毕 。 相关代码如下 ：

case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      g->gray = th->gclist;
      th->gclist = g->grayagain;
      g->grayagain = o;
      black2gray(o);
      traversestack(g, th);
      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci;
    }

扫描proto对象

最后一种特殊类型是Proto类型，将会调用traverseproto函数标记一个Proto数据中的文件名、字符串 、upvalue、局部变量等所有被引用的对象 。

扫描其余的类型

就是简单地调用gray2black将颜色从灰色置为黑色就好了。

barrier操作

从前面的描述可以知道，分步增量式的扫描标记算法中间可以被打断以执行其他操作，此时就会出现新增加的对象与已经被扫描过的对象之间会有引用关系的变化，而算法中需要保证不会出现黑色对象引用的对象中有白色对象的情况，于是需要两种不同的处理。

• 标记过程向前走一步。 这种情况指的是，如果一个新创建对象的颜色是白色，而它被一个黑色对象引用了，那么将这个对象的颜色从白色变成灰色，也就是这个GC过程中的进度向前走了一步。
• 标记过程向后走一步 。 与前面的情况一样，但是此时是将黑色的对象回退到灰色，也就是这个原先已经被标记为黑色的对象需要重新被扫描，这相当于在GC过程中向后走了一步 。
  在代码中，最终调用luaC_barrierf函数的都是向前走的操作；反之，调用luaC_barrierback的操作则是向后走的操作：

  #define luaC_barrier(L,p,v) { if (valiswhite(v) && isblack(obj2gco(p)))  \
  	luaC_barrierf(L,obj2gco(p),gcvalue(v)); }
  
  #define luaC_barriert(L,t,v) { if (valiswhite(v) && isblack(obj2gco(t)))  \
  	luaC_barrierback(L,t); }
  
  #define luaC_objbarrier(L,p,o)  \
  	{ if (iswhite(obj2gco(o)) && isblack(obj2gco(p))) \
  		luaC_barrierf(L,obj2gco(p),obj2gco(o)); }
  
  #define luaC_objbarriert(L,t,o)  \
     { if (iswhite(obj2gco(o)) && isblack(obj2gco(t))) luaC_barrierback(L,t); }

  可以看到，回退操作仅针对Table类型的对象，而其他类型的对象都是向前操作。
  Table是Lua中最常见的数据结构，而且一个Table与其关联的key、value之间是1比N的对应关系 。 如果针对Table对象做的是向前的标记操作，那么就意味着：但凡一个Table只要有新增的对象，都帘要将这个新对象标记为灰色并加入gray链表中等待扫描。
  实际上，这样会有不必要的开销 。 所以，针对Table类型的对象，使用的是针对该Table对象本身要做的向后操作，这样不论有多少个对象新增到Table中，只要改变了一次，就将这个Table对象回退到灰色状态，等待重新扫描 。 但是这里需要注意的是，对Table对象进行回退操作时，并不是将它放入gray链表中，因为这样做实际上还会出现前面提到的多次反复标记的问题。 针对Table对象，对它执行回退操作，是将它加入到 grayagain链表中，用于在扫描完毕gray链表之后再进行一次性的原子扫描：

  void luaC_barrierback (lua_State *L, Table *t) {
    global_State *g = G(L);
    GCObject *o = obj2gco(t);
    lua_assert(isblack(o) && !isdead(g, o));
    lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
    black2gray(o);  /* make table gray (again) */
    t->gclist = g->grayagain;
    g->grayagain = o;
  }

  可以看到，需要进行barrierback操作的对象，最后并没有如新建对象那样加入gray链表中，而是加入grayagain列表中，避免一个对象频繁地进行“被回退－扫描－回退－扫描”过程 。 既然需要重新扫描，那么一次J性地放在grayagain链表中就可以了 。 至于如何回收grayagain链表中的数据，下面将说明。

而相对地，向前的操作就简单多了：

void luaC_barrierf (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  lua_assert(ttype(&o->gch) != LUA_TTABLE);
  /* must keep invariant? */
  if (g->gcstate == GCSpropagate)
    reallymarkobject(g, v);  /* restore invariant */
  else  /* don't mind */
    makewhite(g, o);  /* mark as white just to avoid other barriers */
}

这里只要当前的GC没有在扫描标记阶段，就标记这个对象，否则将对象标记为白色，等待下一次的GC。
当gray链表中没有对象时，并不能马上进入下一个阶段，这是因为前面还有未处理的数据，这一步需要一次性不被中断地完成，其入口是atomic函数。
前面提到Lua的增量式GC算法分为多个阶段，可以被中断，然而这一步则例外。 这一步将处理弱表链表和前面提到的grayagain链表，是扫描阶段的最后一步，不可中断：

static void atomic (lua_State *L) {
  global_State *g = G(L);
  size_t udsize;  /* total size of userdata to be finalized */
  /* remark occasional upvalues of (maybe) dead threads */
  remarkupvals(g);//调用remarkupvals函数去标记open状态的UpValue
  /* traverse objects cautch by write barrier and by 'remarkupvals' */
  propagateall(g);//gray链表又会有新的对象，于是需要调用propagateall再次将gray链表中的对象标记一下
  /* remark weak tables */
  g->gray = g->weak;//修改gray链表指针，使其指向管理弱表的weak指针
  g->weak = NULL;
  lua_assert(!iswhite(obj2gco(g->mainthread)));
  markobject(g, L);  /* mark running thread *///标记当前的Lua_State指针以及基本的meta表
  markmt(g);  /* mark basic metatables (again) */
  propagateall(g);
  /* remark gray again */
  g->gray = g->grayagain;//修改gray链表指针指向grayagain指针
  g->grayagain = NULL;
  propagateall(g);//调用propagateall函数进行遍历扫描操作
  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
  marktmu(g);  /* mark `preserved' userdata */
  udsize += propagateall(g);  /* remark, to propagate `preserveness' */
  cleartable(g->weak);  /* remove collected objects from weak tables */
  /* flip current white */
  g->currentwhite = cast_byte(otherwhite(g));//将当前白色类型切换到了下一次GC操作的白色类型 
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gcstate = GCSsweepstring;//修改状态到下个回收阶段
  g->estimate = g->totalbytes - udsize;  /* first estimate */
}

现在就可以谈谈前面提到的对udata进行处理的luaC_separateudata函数了：

size_t luaC_separateudata (lua_State *L, int all) {
  global_State *g = G(L);
  size_t deadmem = 0;
  GCObject **p = &g->mainthread->next;
  GCObject *curr;
  while ((curr = *p) != NULL) {//如果该对象不需要回收，就继续处理下一个对象
    if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))//先看该对象有没有注册GC函数
      p = &curr->gch.next;  /* don't bother with them */
    else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
      markfinalized(gco2u(curr));  /* don't need finalization *///如果没有，就直接标记该对象的状态是finalized
      p = &curr->gch.next;
    }
    else {  /* must call its gc method */
      deadmem += sizeudata(gco2u(curr));
      markfinalized(gco2u(curr));//标记该对象为 finalized
      *p = curr->gch.next;
      /* link `curr' at the end of `tmudata' list */
      if (g->tmudata == NULL)  /* list is empty? *///将这些对象加入tmudata链表中，这里将udata放在一个链表中也是为了统一处理，后面将会提至Ufinalized状态的处理
        g->tmudata = curr->gch.next = curr;  /* creates a circular list */
      else {
        curr->gch.next = g->tmudata->gch.next;
        g->tmudata->gch.next = curr;
        g->tmudata = curr;
      }
    }
  }
  return deadmem;
}

它主要对mainthread之后的对象进行遍历（前面谈到了将udata放在mainthread之后，这是为了统一放在一个地方，方便处理）。

回收阶段

回收阶段分为两步，一步是针对字符串类型的回收，另一步则是针对其他类型对象的回收 ：

case GCSsweepstring: {
      lu_mem old = g->totalbytes;
      sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
      if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
        g->gcstate = GCSsweep;  /* end sweep-string phase */
      lua_assert(old >= g->totalbytes);
      g->estimate -= old - g->totalbytes;
      return GCSWEEPCOST;
    }
case GCSsweep: {
      lu_mem old = g->totalbytes;
      g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
      if (*g->sweepgc == NULL) {  /* nothing more to sweep? */
        checkSizes(L);
        g->gcstate = GCSfinalize;  /* end sweep phase */
      }
      lua_assert(old >= g->totalbytes);
      g->estimate -= old - g->totalbytes;
      return GCSWEEPMAX*GCSWEEPCOST;
    }

针对字符串类型的数据，每次调用sweepwholelist函数回收字符串散列桶数组中的一个字符串链表，其中每次操作的散列桶索引值存放在sweepstrgc变量中 。 当所有字符串散列桶数据全部遍历完毕时，切换到下一个状态GCSsweep进行其他数据的回收。

对于其他类型数据的回收，我们调用sweeplist函数进行：

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  GCObject *curr;
  global_State *g = G(L);
  int deadmask = otherwhite(g);
  while ((curr = *p) != NULL && count-- > 0) {
    if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
      sweepwholelist(L, &gco2th(curr)->openupval);
    if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
      lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));
      makewhite(g, curr);  /* make it white (for next cycle) */
      p = &curr->gch.next;
    }
    else {  /* must erase `curr' */
      lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
      *p = curr->gch.next;
      if (curr == g->rootgc)  /* is the first element of the list? */
        g->rootgc = curr->gch.next;  /* adjust first */
      freeobj(L, curr);
    }
  }
  return p;
}

可以看到，这里我们首先拿到otherwhite，这表示本次GC操作不可以被回收的白色类型 。 后面就是依次遍历链表中的数据，判断每个对象的白色是否满足被回收的颜色条件。

结束阶段

走到了最后一步回收阶段，这一阶段主要针对tmudata链表进行处理，在所有数据都处理完毕后，重新将GC状态切换到暂停状态，这表示下一次新的GC可以开始了 。 相关代码如下：

case GCSfinalize: {
      if (g->tmudata) {
        GCTM(L);
        if (g->estimate > GCFINALIZECOST)
          g->estimate -= GCFINALIZECOST;
        return GCFINALIZECOST;
      }
      else {
        g->gcstate = GCSpause;  /* end collection */
        g->gcdept = 0;
        return 0;
      }
    }

到了结束阶段，其实也可以中断。 只要tmudata链表中还有对象，就一直调用GCTM函数来处理。 前面提到，tmudata链表是用来存放所有自带GC元方法的udata对象，因此这里的工作就是调用这些注册的GC元方法进行对象回收：

static void GCTM (lua_State *L) {
  global_State *g = G(L);
  GCObject *o = g->tmudata->gch.next;  /* get first element */
  Udata *udata = rawgco2u(o);
  const TValue *tm;
  /* remove udata from `tmudata' */
  if (o == g->tmudata)  /* last element? */
    g->tmudata = NULL;
  else
    g->tmudata->gch.next = udata->uv.next;
  udata->uv.next = g->mainthread->next;  /* return it to `root' list */
  g->mainthread->next = o;
  makewhite(g, o);
  tm = fasttm(L, udata->uv.metatable, TM_GC);
  if (tm != NULL) {
    lu_byte oldah = L->allowhook;
    lu_mem oldt = g->GCthreshold;
    L->allowhook = 0;  /* stop debug hooks during GC tag method */
    g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */
    setobj2s(L, L->top, tm);
    setuvalue(L, L->top+1, udata);
    L->top += 2;
    luaD_call(L, L->top - 2, 0);
    L->allowhook = oldah;  /* restore hooks */
    g->GCthreshold = oldt;  /* restore threshold */
  }
}

GCTM函数的主要逻辑就是循环遍历tmudata链表中的对象，针对每个对象调用 fasttm函数，其中会使用GC元方法来进行对象的回收。

当所有操作都完成，tmudata链表中不再有对象了，此时一个GC的完整流程就走完了，Lua将GC状态切换到GCSpause，等待下一次的GC操作。

进度控制

在Lua代码中，有两种回收方式，一种是自动回收，一种是由用户自己调用API来触发一次回收。
自动回收会在每次调用内存分配相关的操作时检查是再满足触发条件，这个操作在宏luaC_checkGC中进行：

#define luaC_checkGC(L) { \
  condhardstacktests(luaD_reallocstack(L, L->stacksize - EXTRA_STACK - 1)); \
  if (G(L)->totalbytes >= G(L)->GCthreshold) \
	luaC_step(L); }

可以看到，触发自动化GC的条件就是： totalbytes大于等于GCthreshold值。 在这两个变量中，totalbytes用于保存当前分配的内存大小，而GCthreshold保存的是一个阈值，这个值可以由一些参数影响和控制，由此改变触发的条件。
由于自动GC会在使用者不知道的情况下触发，不太可控，因而很多人选择关闭它，具体操作就是通过将GCthreshold设置为一个非常大的值来达到一直不满足自动触发条件。
接下来，看看手动GC受哪些参数影响 。 首先，estimate和gcpause两个成员将影响每次GCthreshold的值：

#define setthreshold(g)  (g->GCthreshold = (g->estimate/100) * g->gcpause)

这里estimate是一个预估的当前使用的内存数量，而gcpause则是一个百分比，这个宏的作用就是按照估计值的百分比计算出新的阈值来 。 其中，gcpause通过lua_gc这个C接口来进行设置。 可以看到，百分比越大，下一次开始GC的时间就会越长 。

另一个影响GC进度的参数是gcstepmul成员，它同样可以通过lua_gc来设置。 这个参数将影响每次手动GC时调用singlestep函数的次数，从而影响到GC回收的速度：

void luaC_step (lua_State *L) {
  global_State *g = G(L);
  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;//GCSTEPSIZE 是一个宏，表示每次 GC 的步长大小 。 使用这个宏以及gcstepmul参数，可以计算出这一次回收计划至少回收的内存数量 
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */
  g->gcdept += g->totalbytes - g->GCthreshold;//gcdept用于在每次回收之前累加当前使用内存到阔值之间的差值，用于后面计算下一次触发GC的阑值
  do {//当计划待回收内存还没有回收完之前，一直循环调用 singlestep 函数来进行回收，除非这里完成了完整的GC
    lim -= singlestep(L);
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);//完成回收之后，设置下一次触发回收操作的阈值；如果完成了一个 GC,那么调用 setthreshold来计算下一次GC的阔值。 
  if (g->gcstate != GCSpause) {//如果此时状态不是GCSpause ，那么表示没有完成一个GC 
    if (g->gcdept < GCSTEPSIZE)//如果前面保存的 gcdept太小，小于GCSTEPSIZE ，那么下一次阔值就设置得比当前使用内存大GCSTEPSIZE ，即只要再多分配 GCSTEPSIZE 的内存就会再次触发GC 
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {//否则将 gcdept 减去 GCSTEPSIZE ，将GCthreshold设置得跟 totalbytes一样，以求尽快触发下一次GC 。 
      g->gcdept -= GCSTEPSIZE;
      g->GCthreshold = g->totalbytes;
    }
  }
  else {
    lua_assert(g->totalbytes >= g->estimate);
    setthreshold(g);
  }

可以看到setthreshold只会在一次GC完成之后被调用，而不会影响没有完成的GC全流程 。 因此，setthreshold影响的是两次完整GC之间的时长 。 而gcdept参数会在每次GC完毕之后重新清零，它用于保存一次完整GC的内部状态。
同时，还需要注意的一点是，这个过程会改变GCthreshold的值，所以如果希望关闭自动GC,还需要在手动执行完一次GC之后重新设置关闭自动GC。

从lua-5.1.1中分离出来的gc实现代码

lgc

reference

《Lua设计与实现》
New Garbage Collector 详见：http://wiki.luajit.org/New-Garbage-Collector

---

El que realiza lo que desea, es grande; el que quiere realizar lo que puede, es sabio.