今天来看一下 mark 过程是怎样实现的。

    所有的 GC 流程，都从 singlestep 函数开始。singlestep 就是一个最简单的状态机。GC 状态简单的从一个状态切换到下一个状态，循环不止。状态标识放在 global state 的 gcstate 域中。这一点前面以前谈过。

    开始的两个状态和 mark 过程有关。

    初始的 GCSpause 状态下，执行 markroot 函数。我们来看一下 markroot 的代码。见 lgc.c 的 501 行。

/* mark root set */
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;
}

    主要是把状态复位的操作以及标记根节点。

    lua 采用是 Tri-colour marking GC 算法 。需要维护一个灰色节点集。这里用 gary 存放。grayagain 保存着需要原子操作标记的灰色节点。

    weak 保存着需要清理的 weak 表。

    这里的 markobject 和 markvalue 都是用宏实现的。区别仅在于操作的是 GCObject 还是 TValue 。最终都是通过调用 reallymarkobject 实现的。markmt 也是直接 mark 的 global state 中的若干元表。这些元表作用于基本的几个数据类型。这些加起来成为整个数据的根。对 lua 语言有所了解的话，不难理解这几行实现。

    核心的实现见 lgc.c 的 69 行

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 的实际类型来 mark 它。reallymarkobject 的时间复杂度是 O(1) 的，它不会递归标记相关对象，虽然大多数 GCObject 都关联有其它对象。

    保证 O(1) 时间使得标记过程可以均匀分摊在逐个短小的时间片内，不至于停止世界太久。这里就需要用到三色标记法。

    reallymarkobject 进入时，先把对象设置为灰色(通过 white2gray 这个宏)。然后再根据具体类型，当一个对象的所有关联对象都被标记后，再从灰色转为黑色。

    因为 TSTRING 一定没有关联对象，而且所有的字符串都是统一独立处理的。这里可以做一个小优化，不需要设置为黑色，只要不是白色就可以清理。所以此处不必染黑。

    但 TUSERDATA 则不同，它是跟其它对象一起处理的。标记 userdata 就需要调用 gray2black 了。另外，还需要标记 userdata 的元表和环境表。

    TUPVAL 是一个特殊的东西。在 lua 编程，以及写 C 代码和 lua 交互时，都看不到这种类型。它用来解决多个 closure 共享同一个 upvalue 的情况。实际上是对一个 upvalue 的引用。问什么 TUPVAL 会有 open 和 closed 两种状态？应该这样理解。

    当一个 lua 函数本执行的时候，和 C 语言不一样，它不仅可以看到当前层次上的 local 变量，还可以看到上面所有层次的 local 变量。这个可见性是由 lua 解析器解析你的 lua 代码时定位的(换句话说，就是在“编译”期决定的)。那些不属于你的函数当前层次上的 local 变量，就称之为 upvalue 。upvalue 这个概念是由 parser 引入的。在 Lua 中，任何一个 function 其实都是由 proto 和运行时绑定的 upvalue 构成的。proto 将如何绑定 upvalue 是在 parser 生成的 bytecode 里描述清楚了的。如果对这一块的实现代码有兴趣，可以参考 lvm.c 的 719 行：

case OP_CLOSURE: {
        Proto *p;
        Closure *ncl;
        int nup, j;
        p = cl->p->p[GETARG_Bx(i)];
        nup = p->nups;
        ncl = luaF_newLclosure(L, nup, cl->env);
        ncl->l.p = p;
        for (j=0; jl.upvals[j] = cl->upvals[GETARG_B(*pc)];
          else {
            lua_assert(GET_OPCODE(*pc) == OP_MOVE);
            ncl->l.upvals[j] = luaF_findupval(L, base + GETARG_B(*pc));
          }
        }
        setclvalue(L, ra, ncl);
        Protect(luaC_checkGC(L));
        continue;
      }

    我们会看到，调用 luaF_newLclosure 生成完一个 Lua Closure 后，会去填那张 upvalue 表。当 upvalue 尚在堆栈上时，其实是调用 luaF_findupval 去生成一个对堆栈上的特定值之引用的 TUPVAL 对象的。luaF_findupval 的实现不再列在这里，它的主要作用就是保证对堆栈相同位置的引用之生成一次。生成的这个对象就是 open 状态的。所有 open 的 TUPVAL 用一个双向链表串起来，挂在 global state 的 uvhead 中。

    一旦函数返回，某些堆栈上的变量就会消失，这时，还被某些 upvalue 引用的变量就必须找个地方妥善安置。这个安全的地方就是 TUPVAL 结构之中。修改引用指针的结果，就被认为是 close 了这个 TUPVAL 。相关代码可以去看 lfunc.c 中 luaF_close 的实现。

    走题太多。现在回来看 TUPVAL 的 mark 过程。mark upvalue 引用的对象之后，closed TUPVAL 就可以置黑了。为何 open 状态的 TUPVAL 需要留为灰色待处理呢？这是因为 open TUPVAL 是易变的。GC 分步执行，我们无法预料在 mark 流程走完前，堆栈上被引用的数据会不会发生变化。

    事实上，在 mark 的最后一个步骤，我们会看到所有的 open TUPVAL 被再次 mark 一次。做这件事情的函数是 lgc.c 516 行的：

static void remarkupvals (global_State *g) {
  UpVal *uv;
  for (uv = g->uvhead.u.l.next; uv != &g->uvhead; uv = uv->u.l.next) {
    lua_assert(uv->u.l.next->u.l.prev == uv && uv->u.l.prev->u.l.next == uv);
    if (isgray(obj2gco(uv)))
      markvalue(g, uv->v);
  }
}

    其它的数据类型处理都很简单。把自己挂在 gray 链表上即可。这条链表将在后面的 GCSpropagate 步骤被处理到。

    GC 状态为 GCSpropagate 时，singlestep 就是调用 propagatemark 处理 global state 中的 gray 链。

    今天白天因为有些其他工作做，所以没有留太多时间写这篇 Blog ，propagatemark 内部的细节分析得等到下一篇了。从总体看来，propagatemark 标记了各种 GCObject 的直接相关级的对象。

    到这里，我们可以回答昨天遗留下来的一个问题：GC 的分步过程是如何控制进度的。

    从前面分析过的代码上来，singlestep 的返回值决定了 GC 的进度。在 GC 进行过程中，如何知道做完整个 GC 流程的时间，以及目前做的进度呢？

    我们可以依靠的数据只有内存管理器辖下的内存数量。大致上，整个 GC 需要的总时间和 GCObject 的数量成正比。但每种类型的 GCObject 的处理时间复杂度却各不相同。仔细衡量每种类型的处理时间差别不太现实，它可能和具体机器也有关系。但我们却可以大体上认为，占用内存较多的对象，处理时间也更长一点。这里不包括 string 和 userdata 。它们即使占用内存较多，但却没有增加 mark 的时间。虽然不太精确，但对 table ，function ，thread 这些类型来说，这种估算方式却比较接近。

    所以在 propagatemark 过程中，每 mark 一个灰色节点，就返回了它实际占用的内存字节数作为 quantity 值。

    如果回顾昨天看过的代码。

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

    我们就能理解，当 gcstepmul 为 100 时，每次由 luaC_checkGC 满足条件后调用一次 luaC_step ，大致就会标记 1K 的数据(当处于 mark 环节中时)。而每次 luaC_step 会递增 GCthreshold 1K 。

if (g->gcstate != GCSpause) {
    if (g->gcdept < GCSTEPSIZE)
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {
      g->gcdept -= GCSTEPSIZE;
      g->GCthreshold = g->totalbytes;
    }
  }

    依赖自动 GC ，只有 totalbytes 持续增长才会驱动 luaC_step 不断工作下去的。但增长速度如果快于 mark 速度，那么就会产生问题。这正是 lua 手册中所警告的：“step multiplier 控制了收集器相对内存分配的速度。 更大的数字将导致收集器工作的更主动的同时，也使每步收集的尺寸增加。 小于 1 的值会使收集器工作的非常慢，可能导致收集器永远都结束不了当前周期。”

    我们也可以看到，自动 GC 过程处于 sweep 流程时，收集器也并不那么急于释放内存了。因为释放内存会导致 totalbytes 减少，如果没有新的对象分配出来，totalbytes 是不会增加到触发新的 luaC_step 的。

    手动分步 GC 则是另一番光景。lua_gc GCSTEP 使用的 data 值，在处于 mark 流程时，便可以认为扫描的内存字节数乘上 step multiplier 这个系数。当然这只是大致上个估计。毕竟内存不是理想中的逐字节扫描的。

    等待所有灰色节点都处理完，我们就可以开始清理那些剩下的白色节点了吗？不，因为 mark 是分步执行的，中间 lua 虚拟机中的对象关系可能又发生的变化。所以在开始清理工作前，我们还需要做最后一次扫描。这个过程不可以再被打断。

    让我们看看相关的处理函数。见 lgc.c 526 行：

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);
  /* traverse objects cautch by write barrier and by \'remarkupvals\' */
  propagateall(g);
  /* remark weak tables */
  g->gray = g->weak;
  g->weak = NULL;
  lua_assert(!iswhite(obj2gco(g->mainthread)));
  markobject(g, L);  /* mark running thread */
  markmt(g);  /* mark basic metatables (again) */
  propagateall(g);
  /* remark gray again */
  g->gray = g->grayagain;
  g->grayagain = NULL;
  propagateall(g);
  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));
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gcstate = GCSsweepstring;
  g->estimate = g->totalbytes - udsize;  /* first estimate */
}

    代码中注释的很详细。propagateall 是用来迭代所有的灰色节点的。所以每个关键步骤结束后，都需要调用一下保证处理完所有可能需要标记的对象。第一个步骤是那些 open 的 TUPVAL ，在前面已经提及。然后是处理弱表。

    弱表是个比较特殊的东西，这里，弱表需要反复 mark ，跟 write barrier 的行为有关，超出了今天的话题。write barrier 还会引起另一些对象再 mark ，即对 grayagain 链的处理。都留到明天再谈。

    接下来处理 userdata 的部分，luaC_separateudata 之前已经解释过了。

    所以的一切都标记完后，那些不被引用的对象就都被分离出来了。可以安全的清理所有尚被引用的弱表。cleartable 就是干的这件事情。实现没有什么好谈的，一目了然。这里也不列代码了。不过值得一提的是对可以清理的项的判定函数：iscleared 。见 lgc.c 的 329 行。

/*
** The next function tells whether a key or value can be cleared from
** a weak table. Non-collectable objects are never removed from weak
** tables. Strings behave as `values\', so are never removed too. for
** other objects: if really collected, cannot keep them; for userdata
** being finalized, keep them in keys, but not in values
*/
static int iscleared (const TValue *o, int iskey) {
    printf("is cleared %p,%d\\n", o,iskey);
  if (!iscollectable(o)) return 0;
  if (ttisstring(o)) {
    stringmark(rawtsvalue(o));  /* strings are `values\', so are never weak */
    return 0;
  }
  return iswhite(gcvalue(o)) ||
    (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
}

    如果你对 for userdata being finalized, keep them in keys, but not in values 这一句表示困惑的话。可以读读 Roberto 对此的解释 。

    和那些被清理掉的 userdata 一样。当 userdata 被标为白色，在下一个 GC 周期中，它便不再认为是 isfinalized 状态。对应弱表中的 k/v 就被真的被清除掉了。

建议继续学习：

1. Nginx源码分析-事件循环    (阅读：5001)
2. Hive的入口 -- Hive源码解析    (阅读：4849)
3. Nginx与Lua    (阅读：4762)
4. Storm源码浅析之topology的提交    (阅读：4483)
5. Hive源码解析-之-语法解析器    (阅读：4345)
6. Nginx源码分析-内存池    (阅读：4226)
7. Nginx源码分析-Epoll模块    (阅读：4001)
8. Lua GC 的源码剖析 (2)    (阅读：3967)
9. Ameba , 一个简单的 lua 多线程实现    (阅读：3659)
10. 使用 luajit 的 ffi 绑定 zeromq    (阅读：3420)