lua 的垃圾清理

/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader  struct GCObject *next; lu_byte tt; lu_byte marked
/* Common type for all collectable objects */
typedef struct GCObject {
 CommonHeader;
} GCObject;

/*
** create a new collectable object (with given type and size) and link
** it to 'allgc' list.
*/
GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
 global_State *g = G(L);
 GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
 o->marked = luaC_white(g);
 o->tt = tt;
 o->next = g->allgc;
 g->allgc = o;
 return o;
}

/*
** Possible states of the Garbage Collector
*/
#define GCSpropagate 0
#define GCSenteratomic 1
#define GCSatomic 2
#define GCSswpallgc 3
#define GCSswpfinobj 4
#define GCSswptobefnz 5
#define GCSswpend 6
#define GCScallfin 7
#define GCSpause 8

/*
** Does one step of collection when debt becomes positive. 'pre'/'pos'
** allows some adjustments to be done only when needed. macro
** 'condchangemem' is used only for heavy tests (forcing a full
** GC cycle on every opportunity)
*/
#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,(void)0,(void)0)

/*
** performs a basic GC step if collector is running
*/
void luaC_step (lua_State *L) {
 global_State *g = G(L);
 lua_assert(!g->gcemergency);
 if (g->gcrunning) {  /* running? */
 if(isdecGCmodegen(g))
 genstep(L, g);
 else
 incstep(L, g);
  }
}

/* kinds of Garbage Collection */
#define KGC_INC 0 /* incremental gc */
#define KGC_GEN 1 /* generational gc */

/*
** Performs a basic incremental step. The debt and step size are
** converted from bytes to "units of work"; then the function loops
** running single steps until adding that many units of work or
** finishing a cycle (pause state). Finally, it sets the debt that
** controls when next step will be performed.
*/
static void incstep (lua_State *L, global_State *g) {
 int stepmul = (getgcparam(g->gcstepmul) | 1);  /* avoid division by 0 */
 l_mem debt = (g->GCdebt / WORK2MEM) * stepmul;
 l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem))
                 ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul
                 : MAX_LMEM;  /* overflow; keep maximum value */
 do {  /* repeat until pause or enough "credit" (negative debt) */
 lu_mem work = singlestep(L);  /* perform one single step */
 debt -= work;
  } while (debt > -stepsize && g->gcstate != GCSpause);
 if (g->gcstate == GCSpause)
 setpause(g);  /* pause until next cycle */
 else {
 debt = (debt / stepmul) * WORK2MEM;  /* convert 'work units' to bytes */
 luaE_setdebt(g, debt);
  }
}

static lu_mem singlestep (lua_State *L) {
 global_State *g = G(L);
 lu_mem work;
 lua_assert(!g->gcstopem);  /* collector is not reentrant */
 g->gcstopem = 1;  /* no emergency collections while collecting */
 switch (g->gcstate) {
 case GCSpause: {
 restartcollection(g);
 g->gcstate = GCSpropagate;
 work = 1;
 break;
    }
 case GCSpropagate: {
 if (g->gray == NULL) {  /* no more gray objects? */
 g->gcstate = GCSenteratomic;  /* finish propagate phase */
 work = 0;
      }
 else
 work = propagatemark(g);  /* traverse one gray object */
 break;
    }
 case GCSenteratomic: {
 work = atomic(L);  /* work is what was traversed by 'atomic' */
 entersweep(L);
 g->GCestimate = gettotalbytes(g);  /* first estimate */;
 break;
    }
 case GCSswpallgc: {  /* sweep "regular" objects */
 work = sweepstep(L, g, GCSswpfinobj, &g->finobj);
 break;
    }
 case GCSswpfinobj: {  /* sweep objects with finalizers */
 work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
 break;
    }
 case GCSswptobefnz: {  /* sweep objects to be finalized */
 work = sweepstep(L, g, GCSswpend, NULL);
 break;
    }
 case GCSswpend: {  /* finish sweeps */
 checkSizes(L, g);
 g->gcstate = GCScallfin;
 work = 0;
 break;
    }
 case GCScallfin: {  /* call remaining finalizers */
 if (g->tobefnz && !g->gcemergency) {
 g->gcstopem = 0;  /* ok collections during finalizers */
 work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST;
      }
 else {  /* emergency mode or no more finalizers */
 g->gcstate = GCSpause;  /* finish collection */
 work = 0;
      }
 break;
    }
 default: lua_assert(0); return 0;
  }
 g->gcstopem = 0;
 return work;
}

static void cleargraylists (global_State *g) {
 g->gray = g->grayagain = NULL;
 g->weak = g->allweak = g->ephemeron = NULL;
}

/*
** mark root set and reset all gray lists, to start a new collection
*/
static void restartcollection (global_State *g) {
 cleargraylists(g);
 markobject(g, g->mainthread);
 markvalue(g, &g->l_registry);
 markmt(g);
 markbeingfnz(g);  /* mark any finalizing object left from previous cycle */
}

/*
** Mark an object.  Userdata with no user values, strings, and closed
** upvalues are visited and turned black here.  Open upvalues are
** already indirectly linked through their respective threads in the
** 'twups' list, so they don't go to the gray list; nevertheless, they
** are kept gray to avoid barriers, as their values will be revisited
** by the thread or by 'remarkupvals'.  Other objects are added to the
** gray list to be visited (and turned black) later.  Both userdata and
** upvalues can call this function recursively, but this recursion goes
** for at most two levels: An upvalue cannot refer to another upvalue
** (only closures can), and a userdata's metatable must be a table.
*/
static void reallymarkobject (global_State *g, GCObject *o) {
 switch (o->tt) {
 case LUA_VSHRSTR:
 case LUA_VLNGSTR: {
 set2black(o);  /* nothing to visit */
 break;
    }
 case LUA_VUPVAL: {
 UpVal *uv = gco2upv(o);
 if (upisopen(uv))
 set2gray(uv);  /* open upvalues are kept gray */
 else
 set2black(uv);  /* closed upvalues are visited here */
 markvalue(g, uv->v);  /* mark its content */
 break;
    }
 case LUA_VUSERDATA: {
 Udata *u = gco2u(o);
 if (u->nuvalue == 0) {  /* no user values? */
 markobjectN(g, u->metatable);  /* mark its metatable */
 set2black(u);  /* nothing else to mark */
 break;
      }
      /* else... */
    }  /* FALLTHROUGH */
 case LUA_VLCL: case LUA_VCCL: case LUA_VTABLE:
 case LUA_VTHREAD: case LUA_VPROTO: {
 linkobjgclist(o, g->gray);  /* to be visited later */
 break;
    }
 default: lua_assert(0); break;
  }
}

/*
** traverse one gray object, turning it to black.
*/
static lu_mem propagatemark (global_State *g) {
 GCObject *o = g->gray;
 nw2black(o);
 g->gray = *getgclist(o);  /* remove from 'gray' list */
 switch (o->tt) {
 case LUA_VTABLE: return traversetable(g, gco2t(o));
 case LUA_VUSERDATA: return traverseudata(g, gco2u(o));
 case LUA_VLCL: return traverseLclosure(g, gco2lcl(o));
 case LUA_VCCL: return traverseCclosure(g, gco2ccl(o));
 case LUA_VPROTO: return traverseproto(g, gco2p(o));
 case LUA_VTHREAD: return traversethread(g, gco2th(o));
 default: lua_assert(0); return 0;
  }
}

#define luaC_barrier(L,p,v) (  \
    (iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ? \
 luaC_barrier_(L,obj2gco(p),gcvalue(v)) : cast_void(0))

#define luaC_barrierback(L,p,v) (  \
    (iscollectable(v) && isblack(p) && iswhite(gcvalue(v))) ? \
 luaC_barrierback_(L,p) : cast_void(0))

/*
** Barrier that moves collector forward, that is, marks the white object
** 'v' being pointed by the black object 'o'.  In the generational
** mode, 'v' must also become old, if 'o' is old; however, it cannot
** be changed directly to OLD, because it may still point to non-old
** objects. So, it is marked as OLD0. In the next cycle it will become
** OLD1, and in the next it will finally become OLD (regular old). By
** then, any object it points to will also be old.  If called in the
** incremental sweep phase, it clears the black object to white (sweep
** it) to avoid other barrier calls for this same object. (That cannot
** be done is generational mode, as its sweep does not distinguish
** whites from deads.)
*/
void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
 global_State *g = G(L);
 lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
 if (keepinvariant(g)) {  /* must keep invariant? */
 reallymarkobject(g, v);  /* restore invariant */
 if (isold(o)) {
 lua_assert(!isold(v));  /* white object could not be old */
 setage(v, G_OLD0);  /* restore generational invariant */
    }
  }
 else {  /* sweep phase */
 lua_assert(issweepphase(g));
 if (g->gckind == KGC_INC)  /* incremental mode? */
 makewhite(g, o);  /* mark 'o' as white to avoid other barriers */
  }
}


/*
** barrier that moves collector backward, that is, mark the black object
** pointing to a white object as gray again.
*/
void luaC_barrierback_ (lua_State *L, GCObject *o) {
 global_State *g = G(L);
 lua_assert(isblack(o) && !isdead(g, o));
 lua_assert((g->gckind == KGC_GEN) == (isold(o) && getage(o) != G_TOUCHED1));
 if (getage(o) == G_TOUCHED2)  /* already in gray list? */
 set2gray(o);  /* make it gray to become touched1 */
 else  /* link it in 'grayagain' and paint it gray */
 linkobjgclist(o, g->grayagain);
 if (isold(o))  /* generational mode? */
 setage(o, G_TOUCHED1);  /* touched in current cycle */
}

#define WHITE0BIT 3  /* object is white (type 0) */
#define WHITE1BIT 4  /* object is white (type 1) */
#define BLACKBIT 5  /* object is black */
#define FINALIZEDBIT 6  /* object has been marked for finalization */

#define TESTBIT 7



#define WHITEBITS bit2mask(WHITE0BIT, WHITE1BIT)


#define iswhite(x)      testbits((x)->marked, WHITEBITS)
#define isblack(x)      testbit((x)->marked, BLACKBIT)
#define isgray(x)  /* neither white nor black */ \
    (!testbits((x)->marked, WHITEBITS | bitmask(BLACKBIT)))

#define tofinalize(x)   testbit((x)->marked, FINALIZEDBIT)

#define otherwhite(g)   ((g)->currentwhite ^ WHITEBITS)

/*
** Maximum number of elements to sweep in each single step.
** (Large enough to dissipate fixed overheads but small enough
** to allow small steps for the collector.)
*/
#define GCSWEEPMAX 100