记录一次服务器宕机分析过程（2）-深入Lua GC

继续接着上一篇文章记录一次服务器宕机分析过程（1）-排查问题分析宕机问题

---

Lua GC算法

Lua GC实现的是一个三色增量标记回收算法（Tri-Color Incremental Mark & Sweep）。它是基于二色标记回收算法（Two-Color Mark & Sweep）的改进。
Two-Color Mark & Sweep

状态变化图
首先，我们先了解一下二色标记回收算法。在算法中，所有新建对象都会被初始化为白色。一次回收的过程大概是：

1. 从root对象组（所有最上层定义的对象）开始遍历，所有可达对象都被标记为黑色。
2. 等遍历完成后，剩余的白色对象即为可回收对象，我们回收这些白色对象。
3. 重置黑色对象为白色对象，等待下次回收过程。

一个示例如下图所示：

二色回收过程

这个算法有个缺点，就是执行过程必须是完整的。如果一次处理的数据量过大，会占用比较大的时间片，有一定的性能问题。

Tri-Color Incremental Mark & Sweep

状态变化图
为了能够分步执行回收算法，Lua在5.1版本开始使用三色增量标记回收算法。同样，所有新建对象都会被初始化为白色。一次回收的过程大概是：

1. （1）从root对象组（所有最上层定义的对象）开始遍历，所有可达对象都push入栈并被标记为灰色。
   （2）从栈中pop出一个对象，标记为黑色，遍历这个对象的可达对象，如果是白色，标记为灰色push入栈；（重复执行这个过程执行到栈为空为止）。
2. 等遍历完成后，剩余的白色对象即为可回收对象，我们回收这些白色对象。
3. 重置黑色对象为白色对象，等待下次回收过程。

过程 1 耗费整个回收算法最多的时间，是可分步执行的，步骤的中间会新建白色对象，为了将它们纳入标记过程，有两种方式：
（1）直接置灰push入栈 (barrier fwd)。
（2）指向这个白色对象的黑色对象被重新置灰push入栈 (barrier back)。
ps：根据具体对象类型选择barrier的方式。

一个示例如下图所示：

三色回收过程

---

Lua 源码分析

我们来看下Lua的源码（github.com/LuaDist/lua/tree/lua-5.3/src）来理解一些具体的GC执行流程。先看下触发GC的代码，在lua执行的过程中，会经常通过luaC_checkGC宏命令，根据GCdebt的值（受设置的pause影响）确定是否需要GC：

#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,,)

如果需要GC，则执行luaC_step：

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

luaC_step会根据debt的值（受设置的stepmul的影响）执行多步singlestep：

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;
      int sw;
      propagateall(g);  /* make sure gray list is empty */
      work = atomic(L);  /* work is what was traversed by 'atomic' */
      sw = entersweep(L);
      g->GCestimate = gettotalbytes(g);  /* first estimate */;
      return work + sw * GCSWEEPCOST;
    }
    case GCSswpallgc: {  /* sweep "regular" objects */
      return sweepstep(L, g, GCSswpfinobj, &g->finobj);
    }
    case GCSswpfinobj: {  /* sweep objects with finalizers */
      return sweepstep(L, g, GCSswptobefnz, &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);
        return (n * GCFINALIZECOST);
      }
      else {  /* emergency mode or no more finalizers */
        g->gcstate = GCSpause;  /* finish collection */
        return 0;
      }
    }
    default: lua_assert(0); return 0;
  }
}

singlestep根据当前的GC state判定这步执行什么代码。GC有以下几种state：

1. GCSpause： GC cycle的初始化过程；一步完成。
2. GCSpropagate： 遍历对象，直到栈空 ；多步完成。
3. GCSatomic： 处理收尾工作；一步完成。
4. GCSswpallgc： 清理 allgc 链表；多步完成。
5. GCSswpfinobj： 清理 finobj 链表；一步完成。
6. GCSswptobefnz： 清理 tobefnz 链表；一步完成。
7. GCSswpend： sweep main thread ；一步完成。
8. GCScallfin： 执行一些 finalizer (__gc) 完成循环；一步完成。

其中GCSpropagate是最耗时的遍历对象的过程，根据log显示大部分的singlestep都在做GCSpropagate。

---

结合算法和源码分析宕机问题

按照三色标记回收算法的增量计算方式，如果在GCSpropagate阶段，不断的新增大量的新对象，会不断增加GCSpropagate的工作量。如果每个step执行的singlestep不够多的话，可能导致GC cycle长时间处在GCSpropagate状态。

根据这个猜想，我在singlestep函数内打印了状态信息，果然发现GC一直处在GCSpropagate状态，而内存一直在涨。在之前的实验中，我们通过调节stepmul在一定程度上解决了内存上涨问题，是因为这样可以增加每个step可执行的singlestep数量，让GC可以更快跳出GCSpropagate状态，完成GC cycle。

Tips：

1. 对于大量产生临时内存的程序要关注lua的GC工作情况，如有需要可以适当调节setpause、setstepmul参数。
2. 可以加入GC保护机制，超过多少内存强制GC。
3. 可以加入内存报警机制。

---

算法参考：wiki.luajit.org/New-Garbage-Collector
文章参考：zhuanlan.zhihu.com/p/22403251
代码参考：github.com/LuaDist/lua/tree/lua-5.3/src