インクリメンタルGC実装の解剖1

LuaのインクリメンタルGCの実装をちょこっと調べたので、解説・解剖がてらログしておく。
インクリメンタルGCについてはこちらが参考になる。
 
まずはGCを呼ぶ関数を調べてみる。
とりあえず"gc.*("とかでgrepすると、
lua_gc」という明らかにGC呼び出し関数を発見。

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

 
さっぱり分からん。
でも、調べるのはGCの実装方法であって深く追う必要はないので、
唯一使用されている関数「luaC_step」をgrep
 
すると、lgc.cとlgc.hというファイル内に関数を見つけた。
これがGC実装の核だろう。

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 {
    lua_assert(g->totalbytes >= g->estimate);
    setthreshold(g);
  }
}

 
怪しい怪しい。
「singlestep(L)」が怪しい。grep
 

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);
        return GCFINALIZECOST;
      }
      else {
        g->gcstate = GCSpause;  /* end collection */
        g->gcdept = 0;
        return 0;
      }
    }
    default: lua_assert(0); return 0;
  }
}

 
ここがlua_gc関数の実処理部だろう。
stateをみてGCのフェーズを切り分けているようだ。
各ケース分にてどういう処理をするか予想してみる。

  • GCSpause → case文の中にmarkrootが在ることからGCフェイズの最初に到達する処理だろう。
  • GCSpropagate → 「propagate:広める」という意味からもルートをマークした後、ルートに紐づくオブジェクトをマークするのだろう。
  • GCSsweepstring → StringのオブジェクトをSweepする処理だろう。Stringだけ特別視している事からオブジェクト管理が特別だと推測される。
  • GCSsweep → Sweepフェイズ
  • GCSfinalize → Finalize定義を消化するんだろう

 
順をおってMark処理をおってみよう。
まずは「markroot」から。

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

markが頭にきているメソッドでroot全てにマークしているんだろう。

がルートのようだ。
 
Rubyだと関数スタック領域とかも走査するわけだが、
それが無いって事は使用するポインタもLua上で管理すると言う事なんだろう。
つまり中間言語のC上では自由に使っちゃ駄目で、Lua上で使用したオブジェクトに関して
管理しますよーってことなはず。(違ってたら赤面)
 
markvalue,markobjectに関してはswitch文で各種類のオブジェクトごとマークしてるみたい
なのでここは知らなくていいや。
 
次に「propagatemark」を見てみる。
このメソッドには前の走査で見つけたrootオブジェクトを一つ渡している。

/*
** traverse one gray object, turning it to black.
** Returns `quantity' traversed.
*/
static l_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  lua_assert(isgray(o));
  gray2black(o);
  switch (o->gch.tt) {
    case LUA_TTABLE: {
      Table *h = gco2h(o);
      g->gray = h->gclist;
      if (traversetable(g, h))  /* table is weak? */
        black2gray(o);  /* keep it gray */
      return sizeof(Table) + sizeof(TValue) * h->sizearray +
                             sizeof(Node) * sizenode(h);
    }
    case LUA_TFUNCTION: {
      Closure *cl = gco2cl(o);
      g->gray = cl->c.gclist;
      traverseclosure(g, cl);
      return (cl->c.isC) ? sizeCclosure(cl->c.nupvalues) :
                           sizeLclosure(cl->l.nupvalues);
    }
    case LUA_TTHREAD: {
      lua_State *th = gco2th(o);
      g->gray = th->gclist;
      th->gclist = g->grayagain;
      g->grayagain = o;
      black2gray(o);
      traversestack(g, th);
      return sizeof(lua_State) + sizeof(TValue) * th->stacksize +
                                 sizeof(CallInfo) * th->size_ci;
    }
    case LUA_TPROTO: {
      Proto *p = gco2p(o);
      g->gray = p->gclist;
      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;
  }
}

実はコメント部をみるだけで事足りるわけで、rootオブジェクトをtraverse(下まで辿る)して
辿ったオブジェクトの数を返しているようだ。
ふと、思ったことが、インクリメンタル処理はどこにあるのかという事。
つまり、markobjの個数を返すのはいいが、どこで個数制限して処理をミューテータ(GC呼び出したユーザプログラムを行う処理)に返すのだろうか。
 
実はその処理はもう登場していて、一番最初の「luaC_step」内にある。

void luaC_step (lua_State *L) {
  global_State *g = G(L);
  /* markするオブジェクトの個数(多分sweepだろう)設定 */
  l_mem lim = (GCSTEPSIZE/100) * g->gcstepmul;
  if (lim == 0)
    lim = (MAX_LUMEM-1)/2;  /* no limit */
  g->gcdept += g->totalbytes - g->GCthreshold;
  do {
    /* markしたオブジェクトが帰ってくる */
    lim -= singlestep(L);
    /* ルート走査の場合は黙ってbreak */
    if (g->gcstate == GCSpause)
      break;
  } while (lim > 0);
  .
  .
}

 
なるほど、呼び出し元でやってる訳か、これだとmark・sweepのインクリメンタル化が一緒にできるからいいな。
 
長々書いたので、sweep処理部はまた今度の機会にログする。