/*
** $Id: lgc.c,v 2.37 2005/12/22 16:19:56 roberto Exp roberto $
** Garbage Collector
** See Copyright Notice in lua.h
*/

#include <string.h>
#include <stdio.h>

#define lgc_c
#define LUA_CORE

#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lfunc.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "lstring.h"
#include "ltable.h"
#include "ltm.h"


#define GCSTEPSIZE	1024u // 无符号整数1024
#define GCSWEEPMAX	40
#define GCSWEEPCOST	10
#define GCFINALIZECOST	100


#define maskmarks	cast_byte(~(bitmask(BLACKBIT)|WHITEBITS)) // 仅黑色bit、白色bit为1，然后取反；最终仅黑白bit为0，其他bit都是1

#define makewhite(g,x)	\
   ((x)->gch.marked = cast_byte(((x)->gch.marked & maskmarks) | luaC_white(g))) // 标记为currentWhite

#define white2gray(x)	reset2bits((x)->gch.marked, WHITE0BIT, WHITE1BIT)
#define black2gray(x)	resetbit((x)->gch.marked, BLACKBIT)

#define stringmark(s)	reset2bits((s)->tsv.marked, WHITE0BIT, WHITE1BIT) // TString被重置为灰色


#define isfinalized(u)		testbit((u)->marked, FINALIZEDBIT)
#define markfinalized(u)	l_setbit((u)->marked, FINALIZEDBIT)


#define KEYWEAK         bitmask(KEYWEAKBIT)
#define VALUEWEAK       bitmask(VALUEWEAKBIT)

// markvalue()和markobject()用于标记处理白色对象（不是就跳过）

// 是可gc的数据类型，且为白色，则标记该obj
#define markvalue(g,o) { checkconsistency(o); \
  if (iscollectable(o) && iswhite(gcvalue(o))) reallymarkobject(g,gcvalue(o)); }

// 如果t是白色的，则根据数据类型进行处理，大多是把它标记为灰色
#define markobject(g,t) { if (iswhite(obj2gco(t))) \
		reallymarkobject(g, obj2gco(t)); }


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


static void removeentry (Node *n) {
  lua_assert(ttisnil(gval(n)));
  if (iscollectable(gkey(n)))
    setttype(gkey(n), LUA_TDEADKEY);  /* dead key; remove it */
}


static void reallymarkobject (global_State *g, GCObject *o) {
  // 断言是白色，且不是dead状态的object
  lua_assert(iswhite(o) && !isdead(g, o));
  // 将obj的marked bit map上的白色位置0，同时它的black位也是0，既不是白也不是黑，那就是灰
  white2gray(o);
  // 标记完了要进行后续处理，放进grey list中之类的
  switch (o->gch.tt) {
    case LUA_TSTRING: {
      // TString为啥不用在这里直接标记成黑色呢？
      // 按语义规范的话确实得变成黑色，但是sweep阶段只清理old white，将字符串标记为灰色已经足以让它不被回收
      // 在Lua 5.4的reallymarkobject()中你可以看到，TString会被直接标记成黑色，因为reallymarkobject不再统一对所有gcObj调用white2gray(o);
      return;
    }
    case LUA_TUSERDATA: {
      Table *mt = gco2u(o)->metatable; // 取userData的元表
      gray2black(o);  /* udata are never gray */

      // 为什么被扫描到的userData never gray，不用放入gray list，而是直接变成黑色？
      // 因为被它索引的子对象很少且数量固定，只有1个元表和1个env，所以直接在这里为它们打上标记，不用进入传播流程；
      if (mt) markobject(g, mt);
      markobject(g, gco2u(o)->env);
      return;
    }
    case LUA_TUPVAL: {
      // 标记uv->v所指向的实际内容（如果实际内容是个GCObject的话，会被标记）
      UpVal *uv = gco2uv(o);
      markvalue(g, uv->v);
      // 已经是个close upvalue了，那么uv直接置黑即可
      if (uv->v == &uv->u.value)  /* closed? */
        // open upvalue则保持为灰色，直接在atomic阶段调用remarkupvals()进行统一扫描处理
        // 为什么？因为open upvalue所保存的实际TValue，存储在虚拟栈上，是虚拟栈的某个栈位，而虚拟栈上的TValue，是相对活跃的，其内部数值（TValue的指向），后续可能还有非常频繁的变动，比如TValue本来引用着tableA的，过一会又变成引用着tableB；
        // 所以在atomic阶段重新扫一遍灰色open value，保留最新引用的子对象即可；

        // 而对于close upvalue，将uv-v标记后，UpVal实例没有其他的子对象需要扫描了，所以可以直接置黑
        gray2black(o);  /* open upvalues are never black */
        // close upvalue的指向，后续仍可能发生改变，这种情况则用luaC_barrier()来处理；
        // 因为close upvalue的实际TValue已经不存在于虚拟栈上，是相对不活跃的，变化比较低频，只要用户不去修改它，它的指向就是不变的；
      return;
    }
    case LUA_TFUNCTION: {
      // 把obj链接到gray链表的表头，obj的gclist成员是用于处理gray链表中的链接关系的，gc next成员则是用来处理allgc链表中的链接关系
      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);
  }
}

static void marktmu (global_State *g) {
  GCObject *u = g->tmudata;
  if (u) {
    do {
      u = u->gch.next;
      makewhite(g, u);  /* may be marked, if left from previous GC */
      reallymarkobject(g, u);
    } while (u != g->tmudata);
  }
}


/* move `dead' udata that need finalization to list `tmudata' */
size_t luaC_separateudata (lua_State *L, int all) {
  global_State *g = G(L);
  size_t deadmem = 0;
  // userdata在构建时都是链接到mainthread后面的
  GCObject **p = &g->mainthread->next;
  // 遍历所有的userdata
  GCObject *curr;
  while ((curr = *p) != NULL) {
    // userdata非白色 或 还没要求处理所有userdata
    // 或已经被打上finalized标记，表示它的finalized阶段已经度过（__gc元方法“已经”被执行过，或者它根本没有__gc元方法）

    // 不用对这种userdata obj作什么处理，直接跳过它们
    if (!(iswhite(curr) || all) || isfinalized(gco2u(curr)))
      p = &curr->gch.next;  /* don't bother with them */
    // 下面两个分支都属于，该userdata需要被回收的情况
    // 没有__gc元方法的userdata，直接打上FINALIZEDBIT标记即可
    else if (fasttm(L, gco2u(curr)->metatable, TM_GC) == NULL) {
      markfinalized(gco2u(curr));  /* don't need finalization */
      p = &curr->gch.next;
    }
    else {  /* must call its gc method */
      deadmem += sizeudata(gco2u(curr)); // 取userdata的大小累加
      markfinalized(gco2u(curr)); // 打上FINALIZEDBIT标记
      // 注意，这里是修改了*p的指向，即目前迭代到的userdata obj，被移除出了all gc list
      *p = curr->gch.next;

      // 将具有__gc元方法且未被执行过的userdata obj放到tmudata链表中
      /* link `curr' at the end of `tmudata' list */
      if (g->tmudata == NULL)  /* list is empty? */
        // tmudata是个循环链表
        g->tmudata = curr->gch.next = curr;  /* creates a circular list */
      else {
        // userdata被插入tmudata链表头节点的后面
        curr->gch.next = g->tmudata->gch.next;
        g->tmudata->gch.next = curr;
        // tmudata指向最新链接进来的obj
        g->tmudata = curr;
        // 见GCTM()函数，在sweep阶段第一个被处理的userdata是g->tmudata->gch.next
        // 所以tmudata指向的，实际上是链表的尾部，新加进来的userdata obj会被扔到链表的尾部
      }
    }
  }
  // 最终返回，本次要执行__gc元方法的userdata的累计有多少Bytes
  return deadmem;
}

static int traversetable (global_State *g, Table *h) {
  int i;
  int weakkey = 0;
  int weakvalue = 0;
  const TValue *mode;
  // 传播元表
  if (h->metatable)
    markobject(g, h->metatable);
  // 取元表的__mode键对应的value
  mode = gfasttm(g, h->metatable, TM_MODE);
  if (mode && ttisstring(mode)) {  /* is there a weak mode? */
    weakkey = (strchr(svalue(mode), 'k') != NULL);
    weakvalue = (strchr(svalue(mode), 'v') != NULL);
    if (weakkey || weakvalue) {  /* is really weak? */
      // 因为是增量式gc，中间可能更改过table的元表
      // 所以将bit map的两个相关bit位重置后，按当前key = __mode的value来重设bit位
      h->marked &= ~(KEYWEAK | VALUEWEAK);  /* clear bits */
      h->marked |= cast_byte((weakkey << KEYWEAKBIT) | (weakvalue << VALUEWEAKBIT));
      // 将table放进weak list中，放在gc传播流程的最后进行处理
      h->gclist = g->weak;  /* must be cleared after GC, ... */
      g->weak = obj2gco(h);  /* ... so put in the appropriate list */
    }
  }
  // 如果是完全的弱表，key和value都不需要传播，直接返回就行
  if (weakkey && weakvalue) return 1;

  // value非弱引用，传播value；table数组部分的key是常量，不是gc Obj，所以不用考虑key怎么处理
  if (!weakvalue) {
    i = h->sizearray;
    while (i--)
      markvalue(g, &h->array[i]);
  }

  // 遍历table的hash部分
  i = sizenode(h);
  while (i--) {
    Node *n = gnode(h, i);
    lua_assert(ttype(gkey(n)) != LUA_TDEADKEY || ttisnil(gval(n)));
    // 若key-value的value为nil，那么key肯定没法通过table的引用关系保留了，是死掉的，要清除
    if (ttisnil(gval(n)))
      removeentry(n);  /* remove empty entries */
    else {
      // 不能用nil作key
      lua_assert(!ttisnil(gkey(n)));
      // key-value，非弱引用的就传播
      if (!weakkey) markvalue(g, gkey(n));
      if (!weakvalue) markvalue(g, gval(n));
    }
  }
  return weakkey || weakvalue;
}


/*
** All marks are conditional because a GC may happen while the
** prototype is still being created
** 所有的尝试mark操作都是有条件的，因为luaC_step()可能发生在Proto的创建阶段（编译过程中会构建相关的常量值，比如字符串会进行内部化，使得lua vm占用的内存变大，使得lua gc步进）
*/
static void traverseproto (global_State *g, Proto *f) {
  int i;
  // 源代码的路径
  if (f->source) stringmark(f->source);
  // 已构建的常量
  for (i=0; i<f->sizek; i++)  /* mark literals */
    markvalue(g, &f->k[i]);
  // upvalues的名字
  for (i=0; i<f->sizeupvalues; i++) {  /* mark upvalue names */
    if (f->upvalues[i])
      stringmark(f->upvalues[i]);
  }
  // 已构建的，嵌套在proto内部的其他proto
  for (i=0; i<f->sizep; i++) {  /* mark nested protos */
    if (f->p[i])
      markobject(g, f->p[i]);
  }
  // local变量的名字
  for (i=0; i<f->sizelocvars; i++) {  /* mark local-variable names */
    if (f->locvars[i].varname)
      stringmark(f->locvars[i].varname);
  }
}



static void traverseclosure (global_State *g, Closure *cl) {
  markobject(g, cl->c.env);
  if (cl->c.isC) {
    int i;
    for (i=0; i<cl->c.nupvalues; i++)  /* mark its upvalues */
      markvalue(g, &cl->c.upvalue[i]);
  }
  else {
    int i;
    lua_assert(cl->l.nupvalues == cl->l.p->nups);
    markobject(g, cl->l.p);
    for (i=0; i<cl->l.nupvalues; i++)  /* mark its upvalues */
      markobject(g, cl->l.upvals[i]);
  }
}


static void checkstacksizes (lua_State *L, StkId max) {
  int ci_used = cast_int(L->ci - L->base_ci);  /* number of `ci' in use */
  int s_used = cast_int(max - L->stack);  /* part of stack in use */

  // 若当前正在处理overflow的报错，则不要调整了
  if (L->size_ci > LUAI_MAXCALLS)  /* handling overflow? */
    return;  /* do not touch the stacks */

  // CallInfo，当前使用的4倍 < CallInfo的当前总长 且 2倍的base大小 < CallInfo的当前总长
  // 则CallInfo数组缩小至原先的一半，保持当前使用的2倍 和 base大小 都 < CallInfo的新总长即可
  if (4*ci_used < L->size_ci && 2*BASIC_CI_SIZE < L->size_ci)
    luaD_reallocCI(L, L->size_ci/2);  /* still big enough... */
  // just for test
  condhardstacktests(luaD_reallocCI(L, ci_used + 1));

  // 调整虚拟栈大小，原理同上
  if (4*s_used < L->stacksize && 2*(BASIC_STACK_SIZE+EXTRA_STACK) < L->stacksize)
    luaD_reallocstack(L, L->stacksize/2);  /* still big enough... */
  // just for test
  condhardstacktests(luaD_reallocstack(L, s_used));
}


static void traversestack (global_State *g, lua_State *l) {
  StkId o, lim;
  CallInfo *ci;
  // 标记thread的global table，虽然thread的global table默认继承自mainthread，但是它是可以被setfenv()接口修改成另外的table的
  // markvalue()时的iswhite()检测避免了重复标记
  markvalue(g, gt(l));

  lim = l->top;
  // 遍历CallInfo数组，截止到current CallInfo，选取所有函数调用栈中，栈顶最高的，作为lim
  for (ci = l->base_ci; ci <= l->ci; ci++) {
    lua_assert(ci->top <= l->stack_last);
    if (lim < ci->top) lim = ci->top;
  }
  // l->top往下，都是在本次lua vm驱动过程中已使用的栈位，所以在该栈位之下的，都是当前还在使用的的栈位，要传播标记
  for (o = l->stack; o < l->top; o++)
    markvalue(g, o);
  // l->top以及往上的栈位，都是未使用到的栈位，置nil即可
  for (; o <= lim; o++)
    setnilvalue(o);
  // 检查CallInfo数组和虚拟栈的大小，太大时缩小它们
  checkstacksizes(l, lim);
}


/*
** traverse one gray object, turning it to black.
** Returns `quantity' traversed.
** 本函数处理的是灰色对象
** 每遍历1个灰色对象，就将它转为黑色，最终返回遍历过（through）的Bytes数
*/
static l_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  lua_assert(isgray(o));
  gray2black(o); // 标记为黑色

  // 主打的就是一个传播的过程，各种gcObj的子对象都会被打上标记并处理，该放到gray list的就放进去
  switch (o->gch.tt) {
    case LUA_TTABLE: {
      Table *h = gco2h(o);
      // obj从gray list的头部移除出来
      g->gray = h->gclist;
      // 传播处理Table的子对象，但该table是弱表的话，要让它继续保持为灰色，why？
      // 笔记里面详细说了，不在这里展开叙述
      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */
      // 返回Table实例的占用字节数
      return sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h);
    }
    case LUA_TFUNCTION: {
      Closure *cl = gco2cl(o);
      // obj从gray list的头部移除出来
      g->gray = cl->c.gclist;
      // 传播处理Closure的子对象，env、Proto、upvalues
      traverseclosure(g, cl);
      // 返回Closure实例的占用字节数
      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
                           sizeLclosure(cl->l.nupvalues);
    }
    case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      // obj从gray list的头部移除出来
      g->gray = th->gclist;
      // 转移到gray again list的头部
      th->gclist = g->grayagain;
      g->grayagain = o;
      // thread类型需要直接复灰，并扔到gray again list，为什么？
      // 这篇文章里有写：https://blog.codingnow.com/2011/03/lua_gc_5.html
      // 因为thread的内置虚拟栈变动太频繁了，我们经常会在上面构建一些临时的gcObj，比如函数中的local table；
      // 即使用write barrier back的方式去处理的话性能太低，因为每次往里加数据的时候都要“尝试触发”向后写屏障；
      // 在gc流程里，仅有在最后阶段仍处于虚拟栈中的obj才需要被保留（函数还没执行完），所以我们完全不需要去考虑那些“曾经”在虚拟栈里的obj，在atomic阶段重新扫一遍虚拟栈就可以了

      // 那么在atomic()执行时依旧要再放到grayagain吗？好像是的，那么在atomic()里面放到grayagain list之后呢？
      // 后续的传播流程中，不会再访问grayagain了，grayagain也会在下一轮gc开始前被清空，对于子协程来说，在新的一轮gc流程里，它没有被传播到的话就会被release
      // 所以这段代码我想它只是为了代码一致性而写成这样的吧，毕竟在atomic阶段放到grayagain list中对后续的gc流程是没有什么影响的，因为后续step不会再用到grayagain list了
      black2gray(o);

      // 标记thread的global table、虚拟栈中的局部变量，并尝试缩小CallInfo数组和虚拟栈的大小
      // 在first propagate时，先传播一遍，尽可能地减少atomic阶段的处理量
      traversestack(g, th);
      // 返回目前的thread内存占用字节数
      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci;
    }
    case LUA_TPROTO: {
      Proto *p = gco2p(o);
      // obj从gray list的头部移除出来
      g->gray = p->gclist;
      // 传播处理Proto的子对象
      traverseproto(g, p);
      return sizeof(Proto) + sizeof(Instruction) * p->sizecode +
                             sizeof(Proto *) * p->sizep +
                             sizeof(TValue) * p->sizek + 
                             sizeof(int) * p->sizelineinfo +
                             sizeof(LocVar) * p->sizelocvars +
                             sizeof(TString *) * p->sizeupvalues;
    }
    default: lua_assert(0); return 0;
  }
}


static size_t propagateall (global_State *g) {
  size_t m = 0;
  while (g->gray) m += propagatemark(g);
  return m;
}


/*
** 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
*/
// 这个函数告诉我们，1个key或者1个value，是否可以从1个弱表中被清除。不从弱表中清除不可收集的gcObj。
// 字符串的行为就像“值”，因此永远不会被删除。
// 对于其他gcObj：如果真的被收集起来，table就不能再持有它们；对于已经打上了FINALIZEDBIT标记的userdata，保存在key中可以不被从table中清除，保存在value中则不行
static int iscleared (const TValue *o, int 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)) || // 还是白色，那么需要从table中清除
    // userdata特殊处理，若不是作为key-value的key，且已经被打上FINALIZEDBIT标记，则需要从table中清除
    (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
    // 那么，为什么作为key的userdata，即使已经被打上FINALIZEDBIT标记，还能留在table中呢？
    // 见http://lua-users.org/lists/lua-l/2009-03/msg00438.html，是作者的特殊考量
    // 只是期望userdata还能以tbl[userdataObj]的形式，访问到自己的相关信息而已

    // 但如果是以tbl[id] = userdataObj的形式去索引的，恰好tbl是value为弱引用的弱表
    // 那么userdataObj变成垃圾，要执行__gc，userdataObj被重新置黑，执行到cleartable()，userdataObj就不保留在tbl中了，联系会被断开。
    // 因为后续userdataObj的__gc元方法会被执行，它的C层相关内容被释放（比如socket连接什么的），userdataObj就成了一个无效的对象，而我们通过tbl[id]的形式访问到一个已经无效的对象，这是没有意义的。
}


/*
** 从弱表中断开它们与弱引用子对象的链接关系
** clear collected entries from weaktables
*/
static void cleartable (GCObject *l) {
  while (l) {
    Table *h = gco2h(l);
    int i = h->sizearray;
    lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
               testbit(h->marked, KEYWEAKBIT));
    if (testbit(h->marked, VALUEWEAKBIT)) {
      while (i--) {
        TValue *o = &h->array[i];
        if (iscleared(o, 0))  /* value was collected? */
          setnilvalue(o);  /* remove value */
      }
    }
    i = sizenode(h);
    while (i--) {
      Node *n = gnode(h, i);
      if (!ttisnil(gval(n)) &&  /* non-empty entry? */
          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
        setnilvalue(gval(n));  /* remove value ... */
        removeentry(n);  /* remove entry from table */
      }
    }
    l = h->gclist;
  }
}


static void freeobj (lua_State *L, GCObject *o) {
  switch (o->gch.tt) {
    case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
    case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
    case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
    case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
    case LUA_TTHREAD: {
      lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
      luaE_freethread(L, gco2th(o));
      break;
    }
    case LUA_TSTRING: {
      G(L)->strt.nuse--;
      luaM_freemem(L, o, sizestring(gco2ts(o)));
      break;
    }
    case LUA_TUSERDATA: {
      luaM_freemem(L, o, sizeudata(gco2u(o)));
      break;
    }
    default: lua_assert(0);
  }
}



#define sweepwholelist(L,p)	sweeplist(L,p,MAX_LUMEM)

// 所有gc obj的清除操作，都由sweeplist()来完成
static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
  GCObject *curr;
  global_State *g = G(L);
  int deadmask = otherwhite(g);
  // 遍历gcObj链表，p是指针的指针，count用于防止循环执行过久
  while ((curr = *p) != NULL && count-- > 0) {
    // 又是upvalues相关的东西，暂时略过
    if (curr->gch.tt == LUA_TTHREAD)  /* sweep open upvalues of each thread */
      sweepwholelist(L, &gco2th(curr)->openupval);

    // ^ WHITEBITS（^ 0000 0011），除开后两bit的其他bit为1的话会被保留；
    // 后两bit，若为0和1（某一种白色）则是进行翻转操作；
    // 后两bit，若都为0（黑色、灰色）则都变成1；

    // ^ WHITEBITS后
    // atomic()中，current white已经翻转，所以现在的other white is dead = deadmask，是需要清除的那种白色
    // 若curr = 某一种白色，那么翻转后，它才和deadmask相匹配，那么意味着它是current white，是not dead，是本轮gc不需要清除的obj
    // 若curr = 黑色、灰色，那么翻转后，它后两bit都是1，那么必定与otherwhite相匹配，也是不需要清除的obj

    // 如果进入了vm的release阶段，见luaC_freeall()
    // 那么deadmask = 0100 0000，与黑色、灰色、任意一种白翻转后的结果都不匹配，必定进入release obj的分支

    // 另外，关于FIXEDBIT和SFIXEDBIT，一般情况下，具有SFIXEDBIT标记的gcObj，它不会被回收
    // 但是在luaC_freeall()执行后current white = 0100 0011，deadmask = 0100 0000
    // 此时就只有具有SFIXEDBIT标记的mainthread不会被回收，mainthread最终通过额外的处理被释放

    if ((curr->gch.marked ^ WHITEBITS) & deadmask) {  /* not dead? */
      // 断言 not dead 或 具有FIXEDBIT标记
      lua_assert(!isdead(g, curr) || testbit(curr->gch.marked, FIXEDBIT));

      // 测试代码
      // if ((isgray(curr) || iswhite(curr)) && (curr->gch.tt == LUA_TSTRING))
      //   printf("sweep make white deadmask=%d myres=%d my=%d currwhite=%d, mytype=%d str=%s\n", 
      //     deadmask, (curr->gch.marked ^ WHITEBITS), curr->gch.marked, g->currentwhite, curr->gch.tt, getstr(curr));

      // curr的当前颜色可能是current white，那么下面的makewhite其实是重复操作，毕竟其他bit位的信息是保留了下来的
      // 如果curr是黑色、灰色，那么下面的makewhite会将它重新打回白色，在下一轮gc中需要被重新扫描到才不会被清除
      makewhite(g, curr);  /* make it white (for next cycle) */

      // p是指向指针变量的指针变量，其指向直接迭代到下一个
      p = &curr->gch.next;
    }
    else {  /* must erase `curr' */
      // 测试代码
      // if ((isgray(curr) || iswhite(curr)) && (curr->gch.tt == LUA_TSTRING))
      //   printf("clear deadmask=%d myres=%d my=%d mytype=%d str=%s\n", 
      //     deadmask, (curr->gch.marked ^ WHITEBITS), curr->gch.marked, curr->gch.tt, getstr(curr));

      // 迭代到的obj要么为other white（需销毁）
      // 要么当前为lua vm的销毁阶段（见luaC_freeall()，此时的otherwhite并非任何一种白，无论marked标记怎么翻转，都不会与deadmask相匹配）
      lua_assert(isdead(g, curr) || deadmask == bitmask(SFIXEDBIT));
      // 原先指向的指针变量，其指向被修改为下一个，在此，准备release的gcObj被移除出all gc list（或是内部化TString的obj单链表）
      *p = curr->gch.next;
      // 如果脱离的gcObj是all gc list的头节点，那么需要调整头节点（g->rootgc的指向）
      if (curr == g->rootgc)  /* is the first element of the list? */
        g->rootgc = curr->gch.next;  /* adjust first */

      // 释放curr obj，释放对应的那块内存（所有gc数据类型都在这里释放）
      freeobj(L, curr);
    }
  }
  return p;
}


static void checkSizes (lua_State *L) {
  global_State *g = G(L);
  // 尝试缩小内部化字符串的hash数组
  /* check size of string hash */
  if (g->strt.nuse < cast(lu_int32, g->strt.size/4) &&
      g->strt.size > MINSTRTABSIZE*2)
    luaS_resize(L, g->strt.size/2);  /* table is too big */
  // 用于拼接字符串的临时缓冲区也尝试缩小
  /* check size of buffer */
  if (luaZ_sizebuffer(&g->buff) > LUA_MINBUFFER*2) {  /* buffer too big? */
    size_t newsize = luaZ_sizebuffer(&g->buff) / 2;
    luaZ_resizebuffer(L, &g->buff, newsize);
  }
}


static void GCTM (lua_State *L) {
  global_State *g = G(L);
  // tmudata指向链表的尾部
  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;

  // 这个userdata归还至all gc list中，挂在mainthread的后面，重新变回current white
  // 在下一轮的gc周期中，若它没被扫描到，则最终会被清除
  udata->uv.next = g->mainthread->next;  /* return it to `root' list */
  g->mainthread->next = o;
  makewhite(g, o);
  // 至于为什么不在此处直接将struct userdata释放，是因为，这个userdata可能还被某个弱表引用着，它们之间的联系还没有断开
  // 关于这点，你可以看下作者的解释，http://lua-users.org/lists/lua-l/2009-03/msg00438.html，在知识库文档中，我也详细地论述了这一点

  // 执行__gc元方法
  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 */
    // 调大gc step的准入门槛，再调整回来，防止__gc执行时gc step步进
    g->GCthreshold = 2*g->totalbytes;  /* avoid GC steps */

    // 执行__gc(userdata)
    setobj2s(L, L->top, tm);
    setuvalue(L, L->top+1, udata);
    L->top += 2;
    // 非protect call，若执行__gc元方法时报错，那么执行逻辑发生跳转(jmp_buf)，错误会被直接上抛至更上层受理
    luaD_call(L, L->top - 2, 0);
    // 执行__gc元方法报错时，下面两行代码不会执行，下次gc step的门槛直接变为2 * g->totalbytes
    // 若此时lua vm的内存占用已经很高，那么相当于lua vm的自动gc直接被stop了
    L->allowhook = oldah;  /* restore hooks */
    g->GCthreshold = oldt;  /* restore threshold */
  }
}


/*
** Call all GC tag methods
*/
void luaC_callGCTM (lua_State *L) {
  while (G(L)->tmudata)
    GCTM(L);
}


void luaC_freeall (lua_State *L) {
  global_State *g = G(L);
  int i;
  // currentwhite = 0100 0011，deadmask = 0100 0000
  // 这样一来仅具有SFIXEDBIT标记的mainthread不会被回收掉，其他gcObj都会被回收掉
  g->currentwhite = WHITEBITS | bitmask(SFIXEDBIT);  /* mask to collect all elements */
  sweepwholelist(L, &g->rootgc);
  for (i = 0; i < g->strt.size; i++)  /* free all string lists */
    sweepwholelist(L, &g->strt.hash[i]);
}


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


/* mark root set */
static void markroot (lua_State *L) {
  global_State *g = G(L);
  g->gray = NULL;
  g->grayagain = NULL;
  g->weak = NULL;
  // 标记并置灰mainthread
  markobject(g, g->mainthread);
  // 全局环境、注册表、基础类型的元表们，这些Table要先于mainthread被传播处理（遍历子对象并打上标记）
  /* make global table be traversed before main stack */
  markvalue(g, gt(g->mainthread));
  markvalue(g, registry(L));
  markmt(g);
  // gcstate进入传播阶段
  g->gcstate = GCSpropagate;
}

// 尝试remark所有open upvalue
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)))
    // 为什么是仅灰色才被重新remark？LClosure被构建出来后，立刻变成没有任何地方继续引用它，然后执行全量gc的话，此时LClosure的UpVal实例仍为open upvalue
    // 但显然LClosure是需要被回收掉的，与之绑定的UpVal实例也是需要被回收掉的
      markvalue(g, uv->v);
  }
}


static void atomic (lua_State *L) {
  global_State *g = G(L);
  size_t udsize;  /* total size of userdata to be finalized */

  // upvalues的处理，暂时略过，因为不懂，2333
  /* remark occasional upvalues of (maybe) dead threads */
  remarkupvals(g);

  /* traverse objects cautch by write barrier and by 'remarkupvals' */
  propagateall(g);

  // 重新对弱表跑一遍传播处理，因为弱表没有write barrier，传播暂停期间可能附加了新的子对象，或被修改了强弱引用关系
  /* remark weak tables */
  g->gray = g->weak;
  g->weak = NULL;

  // mainthread作为传播操作的根节点之一，它这个时候肯定已经经过一轮传播处理，是灰色了
  lua_assert(!iswhite(obj2gco(g->mainthread)));

  // 标记当前正在执行的thread，保证当前正在执行的thread一定被传播处理过
  // 我一开始其实不太明白为什么会有这一句，在我的设想里，当前运行的thread应该已经在grayagain list里面了
  // 因为L所对应的thread正在被执行，既然它正在被执行，就算它不在global Environment里面，也应该在mainthread的虚拟栈上；
  // 并且如果gray list不为空，那么是执行不到atomic()的

  // 后来想了一下，这个推论可能未必正确
  // 如果我们纯在C程序中，调用luaE_newthread()构建了一个新的thread，然后纯在C程序中驱动它，阁下又该如何应对？
  // 这个thread，它确实不在global Environment里面（因为没塞进去），也不在mainthread的虚拟栈上（不是在lua层驱动的），但它在驱动过程中会引起lua vm的内存增长，从而触发gc Step推进
  markobject(g, L);  /* mark running thread */

  // 第二次传播处理基础类型的元表们，因为它们依附于g->mt，这玩意儿也是没有write barrier机制保护的，见lua_setmetatable()
  markmt(g);  /* mark basic metatables (again) */
  propagateall(g);

  // 遍历处理grayagain list
  /* remark gray again */
  g->gray = g->grayagain;
  g->grayagain = NULL;
  propagateall(g);

  // 从all gc list中分离那些需要回收（白色）且具有__gc元方法，且还没有执行过的userdata，到tmudata链表，并累计它们的字节数
  udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
  // 传播处理tmudata链表中userdata，保留它们的元表和env，这些东西在__gc元方法执行的时候需要用到
  marktmu(g);  /* mark `preserved' userdata */
  udsize += propagateall(g);  /* remark, to propagate `preserveness' */

  // 从弱表中断开它们与弱引用子对象的链接关系，之后去才能去release那些没有引用关系的obj
  cleartable(g->weak);  /* remove collected objects from weak tables */

  /* flip current white */
  g->currentwhite = cast_byte(otherwhite(g));
  // 进入sweep阶段
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gcstate = GCSsweepstring;
  g->estimate = g->totalbytes - udsize;  /* first estimate */
}

// 是个闭合的状态机函数
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: {
      // 传播阶段，初始时gray list中的元素依次为：基础类型的元表、注册表、全局环境、mainthread
      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;
      // 逐个清理字符串内部化的hash数组
      sweepwholelist(L, &g->strt.hash[g->sweepstrgc++]);
      // 判断是否结束内部化字符串的sweep
      if (g->sweepstrgc >= g->strt.size)  /* nothing more to sweep? */
        g->gcstate = GCSsweep;  /* end sweep-string phase */
      // estimate将已经清理掉的内部化字符串所占用的字节数排除在外
      lua_assert(old >= g->totalbytes);
      g->estimate -= old - g->totalbytes;
      return GCSWEEPCOST;
    }
    case GCSsweep: {
      lu_mem old = g->totalbytes;
      // 从sweepgc指向的位置开始，继续遍历处理all gc list，sweep一段
      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);
      // estimate将已经清理掉的gc obj所占用的字节数排除在外
      g->estimate -= old - g->totalbytes;
      return GCSWEEPMAX*GCSWEEPCOST;
    }
    case GCSfinalize: {
      // 处理那些准备回收且带有__gc元方法的userdata，执行__gc元方法
      // 这个过程也是分步的，返回GCFINALIZECOST作为任务项的“产出价值”
      if (g->tmudata) {
        GCTM(L);
        // 但estimate为啥还需要再减一下GCFINALIZECOST呢？是个小问题，但我不太明白
        if (g->estimate > GCFINALIZECOST)
          g->estimate -= GCFINALIZECOST;

        return GCFINALIZECOST;
      }
      else {
      // 状态机回归到GCSpause，外部重设gc触发阈值，等待开始下一轮gc周期
        g->gcstate = GCSpause;  /* end collection */
        g->gcdept = 0;
        return 0;
      }
    }
    default: lua_assert(0); return 0;
  }
}


void luaC_step (lua_State *L) {
  global_State *g = G(L);

  // 我们可以把luaC_step()理解成一个worker（打工人），把lim理解成每天需要完成的工作量
  // 每次luaC_step()开始打工时，工作量lim都会重置，默认的数额 = 1024 / 100 * 200 = 2048
  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  // 若lim == 0，那么今天的工作量贼大，基本做不完的那种，相当于每次调用luaC_step()都可以执行1次完整的gc流程
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */

  // gcdept是欠债的累计数额，它会累计lua vm的当前内存使用量 超出 gc step门槛阈值的部分；
  g->gcdept += g->totalbytes - g->GCthreshold;

  do {
    // 只要还有活没干完，那就继续干，干完为止

    // singlestep()里面包含了各种各样的任务项，它们对应的“产出价值”各不相同

    // 在propagate阶段，我们可以大体上认为，占用内存较多的对象，扫描它的时间也更长一点。这里不包括 string 和 userdata，它们即使占用内存较多，但却没有增加 mark（扫描）的时间。虽然不太精确，但对 table ，function ，thread 这些类型来说，这种估算方式却比较接近。
    // 所以在 propagatemark 过程中，每 mark 一个灰色节点，就返回它实际占用的内存字节数，作为任务项的“产出价值”

    // 在sweep阶段，却又不是以被清除obj的实际占用内存，来作为任务项的“产出价值”，而是转而以一些特定的小数字（GCSWEEPMAX、GCSWEEPCOST、GCFINALIZECOST）作为“产出价值”；
    // 因为luaC_step()是由内存增长来推动的，如果把清掉的内存数量作为“产出价值”，那么lua vm的内存占用就很难下降了

    lim -= singlestep(L); // 猛猛干活，用任务项的“产出价值”抵消今天的工作量

    // 如果已经跑完一轮完整gc流程，那就直接提前下班，开始放假
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);

  // if (g->gcstate > GCSpropagate) {
  //   printf("now g->gcstate = %d\n", g->gcstate);
  //   luaD_throw(L, LUA_ERRMEM);
  // }

  // 一轮完整的gc周期还没执行完，设置下次触发luaC_step()的阈值，GCthreshold
  if (g->gcstate != GCSpause) {
    // 累计到的欠债不是很多，按1K Bytes提高阈值，worker可以悠闲一点，不用立刻开始干活
    if (g->gcdept < GCSTEPSIZE)
      g->GCthreshold = g->totalbytes + GCSTEPSIZE;  /* - lim/g->gcstepmul;*/
    else {
      // 归还欠债，每次归还的数额固定为GCSTEPSIZE
      g->gcdept -= GCSTEPSIZE;
      // 欠债太多，已经欠下若干次luaC_step()还没执行了，所以需要尽快触发luaC_step()，追平欠债
      g->GCthreshold = g->totalbytes;
    }
  }
  // 执行完luaC_step()，g->gcstate == GCSpause，那就是一个完整的gc流程已经跑完了，以另一种方式设置下次触发luaC_step()的阈值（进入下一轮gc周期的阈值）
  else {
    lua_assert(g->totalbytes >= g->estimate);
    setthreshold(g);
  }
}


void luaC_fullgc (lua_State *L) {
  global_State *g = G(L);
  // 如果当前周期还没执行完GCSpropagate阶段，那么意味着current white还未发生翻转，即使当前的gcObj为white，也并非需要clear的对象
  // 重置部分成员变量，并将状态直接切至sweep阶段
  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);

  // 若之前的propagate阶段并未结束，那么sweep阶段执行完后，所有的gcObj都被重置回current white
  // 若之前已经进行到sweep阶段，那么就按将sweep阶段完全执行完来做
  // 但不执行userdata的__gc元方法
  /* finish any pending sweep phase */
  while (g->gcstate != GCSfinalize) {
    lua_assert(g->gcstate == GCSsweepstring || g->gcstate == GCSsweep);
    singlestep(L);
  }

  // 标记根源节点，开始执行full gc，直到本轮gc周期结束
  markroot(L);
  while (g->gcstate != GCSpause) {
    singlestep(L);
  }
  // 设置下一轮gc的起点
  setthreshold(g);
}


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));
  // 断言gcstate在GCSpause、GCSfinalize阶段不会执行到luaC_barrierf()
  // 想了一些确实如此，GCSpause时，还没有黑色对象；GCSfinalize时，所有的gcObj都已经变回白色
  lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
  // o不是table类型
  lua_assert(ttype(&o->gch) != LUA_TTABLE);

  // GCSpropagate阶段一定要保持黑色obj的颜色正确性
  /* must keep invariant? */
  if (g->gcstate == GCSpropagate)
    // 所以对v进行标记传播的处理，立刻白转灰
    reallymarkobject(g, v);  /* restore invariant */
  else  /* don't mind */
    // 那么目前一定处于sweep阶段，直接将黑色的gcObj o恢复成白色即可
    // 免得后续为o添加子对象的时候，还触发写屏障机制
    makewhite(g, o);  /* mark as white just to avoid other barriers */
}

// 在Lua5.1中，只有Table作为黑色obj时，才需要向后设置屏障
void luaC_barrierback (lua_State *L, Table *t) {
  global_State *g = G(L);
  GCObject *o = obj2gco(t);
  // 断言obj为黑色，并且还未死亡
  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;
}


void luaC_link (lua_State *L, GCObject *o, lu_byte tt) {
  global_State *g = G(L);
  // 将新的gc对象o，链接到rootgc链表的头部，作为头节点
  o->gch.next = g->rootgc;
  g->rootgc = o;
  // 将gc对象o，标记为白色，luaC_white(g)返回的是一个仅带有白色信息的bit map（当前只有1bit为1），bit map的每个二进制位都带有特殊含义
  o->gch.marked = luaC_white(g);
  o->gch.tt = tt;
}


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;

  // 如果这个旧的open upvalue已经被扫描过，就会是灰色，才进行下面的处理
  if (isgray(o)) {
    // 当前还处于传播阶段，那么灰色的open upvalue可以直接变成黑色的close upvalue
    // 向前设置屏障，保证open upvalue当前最新的TValue指向也被扫描到即可
    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) */
      // 在sweep阶段，灰色直接变回白色即可
      makewhite(g, o);
      // 如果已经进入分步执行的GCSfinalize阶段，此时不应该再有灰色UpVal的了，扫描阶段还未重启；被保留下来的那些也已经black to white
      lua_assert(g->gcstate != GCSfinalize && g->gcstate != GCSpause);
    }
  }
}