深入Lua：垃圾回收

标记和清扫

Lua是一门自动内存管理的语言，它使用的是经典的标记和清扫算法。这个算法的原理其实非常简单，在我们的编程实践中或多或少都有类似的做法，一个理想的实现是这样的：

明确对象模型和关系：

• 统一对象模型，比如Lua所有类型的对象都统一为TValue。
• 所有动态分配的对象串连成一个链表(或多个)。
• 程序中有少数几个根集对象，比如Lua里的注册表，主线程等，这些根集对象再去引用其他对象，由此展开成对象的关系结构。

标记和清扫

• 在标记阶段，从根集对象开始标记，把整个对象层级都标记完，这些被标记到的对象称为可到达的对象。
• 在清扫阶段，遍历上面提到的对象链表，如果对象被标记过则擦除标记并跳过，如果对象没被标记，说明它不可到达，那就把它释放掉。

原理总是很简单，但现实又常常不是那么简单。如果遇到对象数量特别多的情况，GC就会成为一个很大的负担。

Lua 5.0之前，垃圾回收是一个stop the world的过程，即在执行GC的时候要一次性完成，它的好处是代码相对简单，5.0的GC代码不过几百行，如果你想了解GC算法本身，看一下5.0的lgc.h|c是非常好的。

这种stop the world的GC在轻量的应用中不是什么问题，如果遇到程序非常大，对象特别多的情况，效率就很成问题了。因此在5.1之后，Lua进化成一个步进的GC，原理还是标记和清扫，但是把一个GC周期分成很多步，一次只执行一步。这对GC的效率是一个很大的提升，代价就是GC代码变得很复杂，Lua 5.3已经有一千多行。

从代码上看，除了GC分步，还有upvalues，弱表，终结对象(有__gc元方法的对象)的处理，这些都加大了垃圾回收的复杂度。

一个GC对象分成三种颜色(三种状态):

• 白色：表示对象未被标记，在GC周期开始之前对象为白色，如果到清扫阶段还是白色，那就说明该对象不可到达，要被清除掉。
• 灰色：表示对象本身已标记，但它引用的对象未被标记，比如一个表已被标记，它的键值对象还未标记。这表示对象标记的一个中间状态。
• 黑色：表示对象和它引用的对象都已被标记，在清扫阶段黑色对象为可到达对象。

一个GC对象的“基类”是这个结构：

struct GCObject {
  GCObject *next; 
  lu_byte tt; 
  lu_byte marked;
};

其中marked就是对象的标记状态，它的位含义如下：

• 第0位：第1种白
• 第1位：第2种白
• 第2位：黑
• 第3位：标记为终结对象

灰色为0, 1, 2位都清0的情况。

我们注意到白色有两个状态，这是为了解决分步GC的中间新建对象的问题。比如在标记阶段和清扫阶段的中间，有一个新建的对象，它默认为白色；清扫的时候会因为它是白色而把它给释放掉。引入两种白色之后这样处理：

• g->currentwhite表示当前白，它是两种白色中的任意一种，我们假定为白1，在清扫阶段之前，所有白对象都是白1。
• 在标记阶段结束的时候，g->currentwhite切换为白2，现在之前那些白对象和g->currentwhite就是不同白了(因为它们是白1)。
• 在标记结束之后，清扫开始之前，新建一个对象，默认标记当g->currentwhite，也就是白2。
• 在清扫的时候，只会清扫和g->currentwhite不同的白，即白1。这样那些新建的对象就不会在清扫阶段被释放。而在清扫结束之后，这些新建的对象也会变成白2。等待下一个周期。

要被终结对象就是那些有__gc元方法的对象。

global_State有好多和GC相关的字段，其中有一些重要链表。所有GC对象总是在下面的一个链表中：

• allgc 所有未被标记为终结的对象
• finobj 所有被标记为终结的对象
• tobefnz 所有准备终结的对象(准备调用__gc的对象)
• fixedgc 不会被回收的对象

我们一个个稍微细讲一下：

正常情况下，新建对象都会进入allgc链表。

如果给对象设置一个元表，且元表有__gc元方法，那么它会从allgc取出，加入到finobj去，并设置对象的FINALIZEDBIT标记位(就是上面说的第3个marked位)。

在标记阶段，finobj中的白对象会移到tobefnz链表去，然后标记这些对象，这样当前周期不会释放这些对象；清扫完之后会进入GCScallfin阶段，在这里调用tobefnz对象的gc方法，同时把对象移回allgc链表；如果gc中使对象重新变成可到达，则对象复活过来；否则下个周期这个对象就会被正常清除。

fixedgc 是那些不会被回收的对象，在新建完对象后，必须马上调用luaC_fix把对象从allgc移到fixedgc去。GC的过程不会对fixedgc进行清扫。

对于灰对象还有好几个链表：

• gray 普通的灰对象链表
• grayagain 在GCSatomic阶段(是标记阶段的一个子阶段)中重新访问的灰对象，这些灰对象包括：
  • 进行写屏蔽的黑对象
  • 在传播阶段的弱表
  • 所有线程对象
• weak 待清理的弱值表
• allweak 待清理的弱键值表
• ephemeron 弱键表

可以看出这些灰对象链表是由分步和弱表引入的附加数据结构，这也是GC中较为复杂的部分。

GC的核心函数是singlestep，它表示执行一步GC，每一步都在重复其中一个阶段，这些阶段是：

#define GCSpropagate    0       // 传播阶段：标记对象
#define GCSatomic   1           // 原子阶段：一次性标记
#define GCSswpallgc 2           // 清扫allgc
#define GCSswpfinobj    3       // 清扫finobj
#define GCSswptobefnz   4       // 清扫tobefnz
#define GCSswpend   5           // 清扫结束
#define GCScallfin  6           // 调用终结函数(__gc)
#define GCSpause    7           // 停止

GCSpause

GC始于GCSpause阶段，这一步主要标记几个根集对象，如主线程，注册表，基础类型的元表。

标记的核心宏是markobject

#define markobject(g,t) { if (iswhite(t)) reallymarkobject(g, obj2gco(t)); }

只有白对象才会调用reallymarkobject进行实际的标记，所以重复调用markobject是没有问题的。

reallymarkobject进行实际的标记，代码比较长这里就不列了，只说明它的逻辑：

• 调用white2gray把白色去掉，变成灰色。
• 如果是字符串，用户数据，调用gray2black直接变黑色
• 用户数据还要标记它的元表，和关联的用户值。
• 如果是线程，函数，函数原型和表，保留灰色，并链接到g->gray去。

标记完根集对象，进行GCSpropagate阶段。

GCSpropagate

GCSpropagate的任务是不断从gray链表中取对象出来，把它们链接到合适的链表去，并标志它们的引用对象。这个阶段的分步执行的，一次调用只处理一个对象，核心函数是propagatemark：

• 先从g->gray弹出一个对象，把这个对象变成黑色。根据对象的类型作不同的处理：
• 如果是C闭包：标记闭包中的upvalue。
• 如果是Lua闭包，由于里面的upvalue分成open和close状态，所以要分情况处理：
  • 直接标记close状态的upvalue。
  • 如果是open的状态，说明upvalue在栈程中栈上，这里不标记，等线程去标记。
• 如果是函数原型：标记原型里面的各种字符串对象，和常量数组。
• 如果是线程：把线程变为灰，移到grayagain链表，标记线程的栈上使用的元素。
• 如果是表：
  • 先标记它的元表
  • 如果不是弱表，标记它的键值
  • 如果是弱表，先把表变成灰色。
    • 如果是弱值表：只标记键对象，把表移到grayagain链表
    • 如果是全弱表：什么也不用标记，把表移到allweak链表
    • 如果是弱键表：如果键已标记则标记值对象；否则不标记值对象；把表移到grayagain链表。

这个过程看起来是很复杂的，如果去掉弱表来看就变简单了，所以我们现在隐约知道，弱表会增大GC的负担。

当g->gray为空时，该阶段完毕，现在g->grayagain和g>allweak链表有值，且都是灰对象

GCSatomic

下一个阶段是GCSatomic，这是一次性完成的处理，它的代码是这样的：

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

propagateall保存g->gray为空，因为Lua的GC是分步的，在每一步的中间都有可能产生新对象，或者发生对象关系的变化：

static void propagateall (global_State *g) {
  while (g->gray) propagatemark(g);
}

接下来调用atomic函数，这个函数处理的东西非常多：

• 将状态设为GCSinsideatomic，在标记过程中根据这个状态有一些不同的处理。
• 调用remarkupvals，那些未标记的线程的栈上，存有open状态的upvalue，所以要在这里标记；那些已标记的线程，则已经在traversethread函数中标记过。
• 把grayagain赋给g->gray，然后调用propagateall再一次标记，这次那些待清理的弱表会到g->weak, g->allweak, g->ephemeron去。
• 将g->finobj中的白对象移动到g->tobefnz，标记它们使它们短暂复活，后面将调用它们的终结函数
• 调用clearkeys和clearvalues清理弱表的白项。
• 最后一步切换当前的白色值g->currentwhite，这样在清扫之前新建的对象就不会被清除。

虽然代码很多，但总结起来最复杂的部分就是处理弱表，特别是ephemeron表；在日常游戏逻辑中，一定要减少弱表的使用，大量的弱表会使GC的负担大大加重。

最后调用entersweep进行清扫阶段：

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

GCSswpallgc..GCSswpend

从这里开始进入清扫阶段，核心函数是sweepstep，清扫的逻辑相对标记就简单得多了，分别遍历g->allgc, g->finobj, g->tobefnz把里面是其他白的对象释放掉：

• 对象必须是其他白，因为当前白表示新创建的对象，不应该在这个周期释放，判断一个对象死亡的宏是这个：

#define isdeadm(ow,m)   (!(((m) ^ WHITEBITS) & (ow)))
#define isdead(g,v) isdeadm(otherwhite(g), (v)->marked)

• g->tobefnz也要遍历 ，因为在遍历的过程中，要把黑对象修改为当前白。

sweeplist的函数代码如下：

static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  global_State *g = G(L);
  // 其他白
  int ow = otherwhite(g);
  // 当前白
  int white = luaC_white(g);  /* current white */
  while (*p != NULL && count-- > 0) {
    GCObject *curr = *p;
    int marked = curr->marked;
    // 如果是其他白，说明对象死亡，释放它，并从链表移除
    if (isdeadm(ow, marked)) {  /* is 'curr' dead? */
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* change mark to 'white' */
      // 否则将当前对象标记为“当前白”
      curr->marked = cast_byte((marked & maskcolors) | white);
      p = &curr->next;  /* go to next element */
    }
  }
  return (*p == NULL) ? NULL : p;
}

freeobj根据对象类型释放里面的内存，其中：

• Lua闭包：在释放时，要对UpVal减引用，如果引用为0且为Close状态，则释放掉UpVal。从这可看出，Lua在局部的地方也使用了引用计数的内存管理。
• 线程：在释放之前要调用luaF_close把线上的open upvalue关闭掉。

GCScallfin

这个阶段主要任务是调用终结对象的__gc函数，核心函数是runafewfinalizers，一开始调用极少数终结函数，后面步骤慢慢增多。调用完毕后，tobefnz的对象清除FINALIZEDBIT标记位，并移动到allgc去，这样一来这个对象就变成一个普通的对象，并且它是不可到达的，下个GC周期就能正常被回收。

关于写屏障和触发GC的条件，请看下回分析。