垃圾回收概述

需求

如果我们只是写一个如“Hello World”这般简单的程序话，垃圾回收本身就不是我们该考虑的问题，实际上，我们的程序是运行在操作系统上，当程序运行结束后，操作系统会自动回收所有程序使用的内存，也就是说，不是一直长时间运行的程序没有考虑垃圾回收的必要。同时，除了C和C++以外几乎所有语言都有垃圾回收机制，我们需要注意的是这里的垃圾回收本质指的是自动内存管理机制。C/C++有相应的内存管理接口，但需要手动。而其它大部分语言没有提供内存管理接口，都是自动管理，就是我们通常所说的拥有垃圾回收机制。
虽然我们可以使用更多拥有良好GC机制的语言进行高效编程，但C/C++可以说是所有高级语言的老祖宗了，大部分语言的解释器都依赖与C/C++实现，其实C才比较正确，C++提供面向对象的特性，同时提供了析构函数用于自动回收对象，注意是对象，对象里的数据则通过编写析构函数来回收。

学习GC原理

不论我们学习多少语言，会发现它们都提供了与C/C++交互的机制，或载入C/C++库的机制，比如java的jni，目的都说是提高效率。总之，我们终会使用C/C++，所以了解一些垃圾回收的方式还是有必要的。

lua的基本API

在学习源码之前，我们先来稍微体会一下lua脚本里面GC的使用，我们使用collectgarbage这一个函数即可。
collectgarbage("collect")进行一次手动垃圾回收，collectgarbage("stop")停止自动垃圾回收，collectgarbage("restart")重启垃圾回收器，collectgarbage("count")返回Lua使用的总内存，至于后面的指令，我们得稍微了解一下lua的垃圾回收机制了，根据官方文档lua采用的是incremental mark-and-sweep collector(渐进式标记-清除回收器)，我们需要分开来看。

标记-清除算法

标记：即标记不需要回收的对象。有两个部分，一是从根节点遍历可到达对象并标记，二是去除用户手动置空对象的标记，在lua里标记的颜色较多，我们等下说。
清除：即清除没有标记的对象并清除标记，最后还能选择的加一个收尾函数进行些可能需要的处理。

渐进式

lua的垃圾回收器，有两个控制参数mul和pause。对于每次标记-清除的程度不同，依据内存分配的多少来决定多大程度，它的参数是mul，而每次标记-清除属于step，众多的step组成一次collect，每次collect的间隔为pause。pause和mul的单位为100。这些有点抽象我们将源码的时候再更详细的去了解。到这里，我们就知道接下来的几个函数的意义了，collectgarbage("step",n)执行n次step，collectgarbage("setpause",n)设置回收器的pause为n/100，collectgarbage("setstepmul",n)设置回收器的mul为n/100。为了深入理解，我们还是来看看lua垃圾回收的源码吧。

源码分析

C语言

在源码解读前，我们先稍微提一下C语言中有哪些对象是需要回收的。C语言需要回收的是堆内存，而栈内存会在函数结束后自动回收。其实就是通过calloc和malloc分配的内存，主要用的多的是后者，而对于在函数内的int i=0之类的内存则会在函数结束后回收。其实还有全局变量，但所谓的垃圾指的一般是我们没有访问到这块内存的指针，同时它属于动态内存可能有不断扩大的风险，对于全局变量内存一般是固定的没有管理的必要性。

内存分布

一个进程的基本内存有四部分，代码区，全局变量区，栈区和堆区。我们发现这与lua虚拟机惊人的相似，只不过多了一个堆区。实际上，在操作系统上运行的程序，也相当于在系统这个虚拟机上运行的，几乎所有虚拟机都一个样，没什么好说的。我们主要看堆区的内存，这才是需要管理的部分。
在lua占用堆内存的是lightuserdate和GCObject，但我见到的都是GCObject，GCObject是一个联合体：

1
2
3
4
5
6
7
8
9
10
union GCObject {
  GCheader gch;
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};

也就是说lua将所有堆内存的数据都抽象为一个GCObject来管理，具体的内容如上。global_State并没有包含进去，从它的结构体申明也可以发现它没有CommonHeader。由之前的分析也可以知道，这块内存是挂载到主协程上管理的。

垃圾回收器

在各种头文件里，我们并没有发现垃圾回收器的结构体，那它的状态pause和mul保存在哪里呢，我们只能去collectgarbage函数在C里的表现来探究了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int luaB_collectgarbage (lua_State *L) {
  static const char *const opts[] = {"stop", "restart", "collect",
    "count", "step", "setpause", "setstepmul", NULL};
  static const int optsnum[] = {LUA_GCSTOP, LUA_GCRESTART, LUA_GCCOLLECT,
    LUA_GCCOUNT, LUA_GCSTEP, LUA_GCSETPAUSE, LUA_GCSETSTEPMUL};
  int o = luaL_checkoption(L, 1, "collect", opts);
  int ex = luaL_optint(L, 2, 0);
  int res = lua_gc(L, optsnum[o], ex);
  switch (optsnum[o]) {
    case LUA_GCCOUNT: {
      int b = lua_gc(L, LUA_GCCOUNTB, 0);
      lua_pushnumber(L, res + ((lua_Number)b/1024));
      return 1;
    }
    case LUA_GCSTEP: {
      lua_pushboolean(L, res);
      return 1;
    }
    default: {
      lua_pushnumber(L, res);
      return 1;
    }
  }
}

容易看出核心语句是int res = lua_gc(L, optsnum[o], ex);，optsum是垃圾回收的指令，ex是额外的参数，res是返回值。最后的switch则根据指令的不同将不同的结果入栈。我们注意到获取使用内存时，有两部分—LUA_GCCOUNT和LUA_GCCOUNTB，后面我们会看到它们的区别。

lapi.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
LUA_API int lua_gc (lua_State *L, int what, int data) {
  int res = 0;
  global_State *g;
  lua_lock(L);
  g = G(L);
  switch (what) {
    case LUA_GCSTOP: {
      g->GCthreshold = MAX_LUMEM;
      break;
    }
    case LUA_GCRESTART: {
      g->GCthreshold = g->totalbytes;
      break;
    }
    case LUA_GCCOLLECT: {
      luaC_fullgc(L);
      break;
    }
    case LUA_GCCOUNT: {
      /* GC values are expressed in Kbytes: #bytes/2^10 */
      res = cast_int(g->totalbytes >> 10);
      break;
    }
    case LUA_GCCOUNTB: {
      res = cast_int(g->totalbytes & 0x3ff);
      break;
    }
    case LUA_GCSTEP: {
      lu_mem a = (cast(lu_mem, data) << 10);
      if (a <= g->totalbytes)
        g->GCthreshold = g->totalbytes - a;
      else
        g->GCthreshold = 0;
      while (g->GCthreshold <= g->totalbytes) {
        luaC_step(L);
        if (g->gcstate == GCSpause) {  /* end of cycle? */
          res = 1;  /* signal it */
          break;
        }
      }
      break;
    }
    case LUA_GCSETPAUSE: {
      res = g->gcpause;
      g->gcpause = data;
      break;
    }
    case LUA_GCSETSTEPMUL: {
      res = g->gcstepmul;
      g->gcstepmul = data;
      break;
    }
    default: res = -1;  /* invalid option */
  }
  lua_unlock(L);
  return res;
}

我们从这里可以看到不少东西，比如pause和mul是存储在全局状态机里，连使用的内存也存在里面，而LUA_GCCOUNT和LUA_GCCOUNTB只是为了把内存的kb和byte区分处理，在全局状态机里存储内存的单位是byte而输出则是kbyte。实际上连垃圾回收器的状态也存储在全局状态机上，我们通过g->GCthreshold改变垃圾回收器的运行状态，注意这和状态不同，g->gcstate是gc运行过程中的状态，标志当前回收处于哪个阶段，有以下这些类型

1
2
3
4
5
#define GCSpause        0
#define GCSpropagate    1
#define GCSsweepstring  2
#define GCSsweep        3
#define GCSfinalize     4

对于collect则会执行一次fullgc，不过我们还是先看一下step的执行。首先对于GCthreshold得讲一下，由之前的代码可知GCthreshold等于MAX_LUMEM时表示回收器停止，这个MAX_LUMEM是unsignedlong的最大值，应该基本达不到这么大的内存，而GCthreshold等于totalbytes表示垃圾回收器在正常执行。好了回到我们的step，首先将步数data扩大1024倍，之前说过回收与内存有关，接下来就是与总内存比较，过多则GCthreshold直接清零，否则在GCthreshold内去除相应大小，luaC_step(L);实现清理的方法，结果是使得GCthreshold超过totalbytes，实际上我们是通过减少totalbytes达到这一步的，另一个if判断垃圾回收器是否pause，不是太重要。我们来看看luaC_step(L)的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void luaC_step (lua_State *L) {
  global_State *g = G(L);
  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */
  g->gcdept += g->totalbytes - g->GCthreshold;
  do {
    lim -= singlestep(L);
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);
  if (g->gcstate != GCSpause) {
    if (g->gcdept < GCSTEPSIZE)
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {
      g->gcdept -= GCSTEPSIZE;
      g->GCthreshold = g->totalbytes;
    }
  }
  else {
    setthreshold(g);
  }
}

先由mul参数计算lim，0表示没有限制。接着由totalbytes和GCthreshold的差，确定计划回收多少内存，注意这里只是一个step，gcdept还残留着之前的数据。singlestep才是最终的回收函数，它会根据此时全局状态机上挂的各种参数来回收相应内存，返回值是回收了具体多少内存，这里有关pause的判定，与之前类似，这里的目的是将lim降为非正数，接下来就是一些收尾内容，调整相关参数。在此之前，我们来看一看luaC_fullgc与此的差别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void luaC_fullgc (lua_State *L) {
  global_State *g = G(L);
  if (g->gcstate <= GCSpropagate) {
    /* reset sweep marks to sweep all elements (returning them to white) */
    g->sweepstrgc = 0;
    g->sweepgc = &g->rootgc;
    /* reset other collector lists */
    g->gray = NULL;
    g->grayagain = NULL;
    g->weak = NULL;
    g->gcstate = GCSsweepstring;
  }
  lua_assert(g->gcstate != GCSpause && g->gcstate != GCSpropagate);
  /* finish any pending sweep phase */
  while (g->gcstate != GCSfinalize) {
    lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
    singlestep(L);
  }
  markroot(L);
  while (g->gcstate != GCSpause) {
    singlestep(L);
  }
  setthreshold(g);
}

第一步用于清除状态，准备开始FullGC，对于lua_assert没什么，要你自己去加。接下来不断执行singlestep(L);直到GCSfinalize状态，注意这里只是为了结束之前未完成的清理。接下来markroot(L)开始标记，while则依赖singlestep(L);执行清除操作，直到GCSpause表示一个周期结束。最后，我们还要看一下luaC_checkGC(L)这是一个lua虚拟机内容改变时经常调用的函数，如字符串入栈。它是一个宏，定义如下

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

里面的luaC_step()我们已经见过了，表示执行一次step，至此我们已经大概明白自动垃圾回收是怎么回事了，在lua里并非有一个专门的线程来垃圾回收，而是在有些lua操作的时候，通过调用垃圾回收函数来实现的。

markroot函数

在看回收函数前，我们有必要先来看看lua是如何标记元素的

1
2
3
4
5
6
7
8
9
10
11
12
static void markroot (lua_State *L) {
  global_State *g = G(L);
  g->gray = NULL;
  g->grayagain = NULL;
  g->weak = NULL;
  markobject(g, g->mainthread);
  /* make global table be traversed before main stack */
  markvalue(g, gt(g->mainthread));
  markvalue(g, registry(L));
  markmt(g);
  g->gcstate = GCSpropagate;
}

先获取全局状态机，然后清除所有标记，然后mark*()则是进行标记的核心函数，总共有四个部分，我们一一来看。

markobject函数

这是一个宏，注意我们传入了主虚拟机L为t

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

iswhite可以先不管，我们看reallymarkobject的内容，注意这里使用obj2gco进行类型转化，等价于cast。

lgc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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: {
      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: {
      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);
  }
}

在开始解读前，我们先说两个东西。不知道你是否还记得在GCObject联合体的申明里面有一个GCheader的部分，它的内容其实就是封装CommonHeader的一个结构体，没错就是每个可回收对象的共有开头，不知道你有没有发觉出什么？其实这里是一项非常有趣的技术，这里运用了联合体内存共享的机制，GCheader和具体对象的CommonHeader共享同一块内存，我们访问GCObject的gch就可以访问到具体对象CommonHeader里的内容了，因此我们就能将可回收对象转化为GCObject进行统一处理了，的确值得好好学习。
接下来再对CommonHeader里的marked稍加说明，它的类型是lu_byte，实际上就是unsigned char，不过只要记住它是个8位二进制数就行了，也就是说它可以标记8个状态，有下面这些

1
2
3
4
5
6
7
8
9
#define WHITE0BIT       0
#define WHITE1BIT       1
#define BLACKBIT        2
#define FINALIZEDBIT    3
#define KEYWEAKBIT      3
#define VALUEWEAKBIT    4
#define FIXEDBIT        5
#define SFIXEDBIT       6
#define WHITEBITS       bit2mask(WHITE0BIT, WHITE1BIT)

lua里面用到的就只要7位，bit2mask函数是一个宏用于将后面两个标志结合到一起，实现比较简单，对于每一个标志可以通过1<<“相应数字”来得到标志位，然后再使用“|”按位与运算即可得到最后的标志位。标志位的具体意思，稍微等等，我们只要先记住SFIXEDBIT只有主协程才有就行了。
好了回到我们的函数，white2gray(o)给o标记上WHITE0BIT和WHITE1BIT，即WHITEBITS，接下来判断o的类型，虽然我们入口传入的是lua主协程，但这个函数是广泛适用的，所以需要判断。对于字符串并没有做标记，这就是为什么状态里有sweep和sweepstring了。如果是userdata，将metatable部分标黑后，将它的两部分分别再进行标记，一个典型的递归。对于upval，使用markvalue标记它的值，因为具体无法确定，只知道它是TValue，但本质也是调用markobject，接下来判断是否为自身，如果是则将其标黑，则主要防止不断上传导致无限循环一直都无法标记。接下来几种数据类型内部也会有许多可回收对象，故将其的gclist挂到全局状态机的gray上，方式与之前TString处理Hash冲突的方式相同。

markvalue函数和markmt函数

这两个函数本身没什么好说的，也是通过调用reallymarkobject函数实现的

1
2
#define markvalue(g,o) { checkconsistency(o); \
  if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }

参数gt(g->mainthread)表示lua虚拟机的所有全局表，registry(L)则是全局表_G，它是挂载在全局状态机上面的。对于主协程没有太大区别，但我们还有协程，所以挂在虚拟机上和全局状态机上是不同的。

1
2
3
4
5
static void markmt (global_State *g) {
  int i;
  for (i=0; i<NUM_TAGS; i++)
    if (g->mt[i]) markobject(g, g->mt[i]);
}

这个函数则是用于标记全局状态机的元表。后两部分加起来可以发现与对userdate的处理是类似的，全局表与一般表的区别是它挂载的位置不同。
由以上分析可以知道，我们标记主要有两大成分，一是主协程上的gclist和全局表，二是全局状态机上的全局表和元表。

singlestep函数

通过之前的分析可以知道此函数用于执行一次step，但这个step与collectgarbage(“step”)有些不太一样。

lgc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static l_mem singlestep (lua_State *L) {
  global_State *g = G(L);
  /*lua_checkmemory(L);*/
  switch (g->gcstate) {
    case GCSpause: {
      markroot(L);  /* start a new collection */
      return 0;
    }
    case GCSpropagate: {
      if (g->gray)
        return propagatemark(g);
      else {  /* no more `gray' objects */
        atomic(L);  /* finish mark phase */
        return 0;
      }
    }
    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;
    }
    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;
      }
    }
    default: lua_assert(0); return 0;
  }
}

先判断处于回收的哪个阶段，如果是pause阶段，则标记根节点。注意我们只标记了根节点，而“标记-回收算法”还需要将可到达元素标记，由之前分析可知，我们执行markroot后，回收将进入propagate状态，意思即为增殖。如果处于propagate状态，观察全局状态机的grey是否有值，有则执行propagatemark进行增殖标记，否则结束执行atomic结束标记过程，执行atomic后会进入sweepstring阶段，等下我们会分析的。如果回收器处于sweepstring阶段，则使用sweepwholelist进行真正的回收操作，它每次会在全局状态机的字符串表strt上移动一次，然后计算清理前后的内存差，并令全局状态机的estimate减去相应内存，当然这并不重要。最后如果strt遍历结束，则进入sweep阶段。对于sweep阶段与上一个类似，只不过遍历的是全局状态机的sweepgc，sweepgc是包含所有可回收对象的表的指针(也可以称为数组)，这是什么意思？在lua里所有回收对象类似于树林的存储方式，所有根节点组成全局状态机里的rootgc，而处于同一深度的元素通过next互相联系，它们组成一个链表用于我们进行每次sweeplist，并返回下一个sweeplist，达到最深以后进入finalize阶段。如果处于finalize阶段，则通过GCTM清理全局状态机的userdata，tmudata是所有userdata的链表，此表遍历结束则进入pause。至此singlestep方法结束。
对于接下来各种函数再具体分析无聊且没太大意义，这里我们总结一下。lua总共有三种颜色标记，可以通过is*看它们的定义

1
2
3
#define iswhite(x)      test2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
#define isblack(x)      testbit((x)->gch.marked, BLACKBIT)
#define isgray(x)       (!isblack(x) && !iswhite(x))

任何对象初始均为白色标记，在markobject通过white2gray标灰，灰表示所有有引用的对象，在propagatemark我们则通过gray2black标黑，黑表示强引用，所以在markobject里可以直接将userdata和upval标黑，它一定不会被回收，propagatemark里面还通过调用traversestack来实现遍历其它节点。在propagatemark主要判断table,function,thread和proto，其中有标回灰色的倾向，主要针对弱引用，其出现在表和协程的结构里面，主要是在C里表现为存在GCObject的指针，注意function和proto没有此倾向，其内部数据依赖于自身的栈和固有的常量表，执行完就可以回收，不存在弱引用现象。sweepwholelist本质是调用sweeplist并输入最大数，sweeplist遍历传入的链表，清除白色标记(等于没标记)的实体，还有一个遍历的上限。

源码总结

我们前面大部分都专注于“标记-回收”部分，而对于gclist，sweepgc等的构建过程，我们没有过多的解读，主要这并非垃圾回收的主要部分，实在不行的话，其实直接将所有GCObject放入一个链表里都可以，但lua的gc过程所要求的结构并非这样，也就是说gc过程决定对象的存储结构，读了gc过程自然也好猜出构建的过程。

结尾

到这里，我们已经对lua的整个垃圾回收机制有了一个大体的认识，不过我们还是需要时刻谨记我们读源码的目的是什么？更好的利用和学习有参考意义的算法，而对于一些细枝末节是我们需要在实战中不断注意提升的，至于自己也能想到的东西一遍过就足矣了。