Lua的垃圾回收（下）
Lua 5.3版本的垃圾回收
Lua垃圾回收源码实现
结合前面描述的垃圾回收的流程，我们参照源码进行逐个的拆解和介绍。
lua的垃圾回收主要都是在接口luaC_step里面完成的，这里面本质上是控制了一个状态机，根据global_State->gcstate进行渐进式的垃圾回收处理。
GCSpause
GCSpause是Lua垃圾回收的起始状态，这一步的核心逻辑在接口restartcollection中，主要任务是将根节点集合标记为灰色，建立灰色初始链表，具体实现如下：
/*
** mark root set and reset all gray lists, to start a new collection
*/
static void restartcollection (global_State *g) {
g->gray = g->grayagain = NULL;
g->weak = g->allweak = g->ephemeron = NULL;
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, strings, and closed upvalues are visited
** and turned black here. Other objects are marked gray and added
** to appropriate list to be visited (and turned black) later. (Open
** upvalues are already linked in 'headuv' list.)
*/
static void reallymarkobject (global_State *g, GCObject *o) {
reentry:
white2gray(o);
switch (o->tt) {
case LUA_TSHRSTR: {
gray2black(o);
g->GCmemtrav += sizelstring(gco2ts(o)->shrlen);
break;
}
case LUA_TLNGSTR: {
gray2black(o);
g->GCmemtrav += sizelstring(gco2ts(o)->u.lnglen);
break;
}
case LUA_TUSERDATA: {
TValue uvalue;
markobjectN(g, gco2u(o)->metatable); /* mark its metatable */
gray2black(o);
g->GCmemtrav += sizeudata(gco2u(o));
getuservalue(g->mainthread, gco2u(o), &uvalue);
if (valiswhite(&uvalue)) { /* markvalue(g, &uvalue); */
o = gcvalue(&uvalue);
goto reentry;
}
break;
}
case LUA_TLCL: {
linkgclist(gco2lcl(o), g->gray);
break;
}
case LUA_TCCL: {
linkgclist(gco2ccl(o), g->gray);
break;
}
case LUA_TTABLE: {
linkgclist(gco2t(o), g->gray);
break;
}
case LUA_TTHREAD: {
linkgclist(gco2th(o), g->gray);
break;
}
case LUA_TPROTO: {
linkgclist(gco2p(o), g->gray);
break;
}
default: lua_assert(0); break;
}
}restartcollection用于重新开启一轮GC，在接口中有：
1）先将灰色链表g->gray、弱引用链表g->weak等重置，其中
·g->gray普通的灰色对象表
·g->grayagain是在分布标记阶段被重新置灰的对象组成的表
2)对主线程的对象进行标记markobject(g, g->mainthread)
3）对注册表的对象进行标记markvalue(g, &g->l_registry)
4）对基础类型的元表进行标记markmt，其中markmt处理的是基本类型的metatable是全局元表
5）对tobefnz链表进行标记
·上述流程底层都是reallymarkobject接口
·接口reallymarkobject中，对于值类型对象直接设置为black，对于闭包、table、thread、proto等引用类型添加到灰色链表，作为灰色链表的初始集合
·reallymarkobject建立gray表，是通过接口linkgclist采取头插法进行插入，通过字段gclist进行节点间的串联
·无论是white2gray还是gray2black，都是对CommonHeader->marked字段进行对应比特位的设置
总结下来，这一步就是将根集合的值类型设置为black，其他非值类型设置为灰，添加到global_state->gray表中，建立灰色表的初始集合之后进入GCSpropagate状态。
GCSpropagate
分步标记阶段，轮询灰色链表，若链表非空，则pop一个对象遍历其子对象进行处理，直到灰色链表为空（为空则进入到GCSatomic状态），主要逻辑在接口propagatemark：
static void propagatemark (global_State *g) {
lu_mem size;
GCObject *o = g->gray;
lua_assert(isgray(o));
gray2black(o);
switch (o->tt) {
case LUA_TTABLE: {
Table *h = gco2t(o);
g->gray = h->gclist; /* remove from 'gray' list */
size = traversetable(g, h);
break;
}
case LUA_TLCL: {
LClosure *cl = gco2lcl(o);
g->gray = cl->gclist; /* remove from 'gray' list */
size = traverseLclosure(g, cl);
break;
}
case LUA_TCCL: {
CClosure *cl = gco2ccl(o);
g->gray = cl->gclist; /* remove from 'gray' list */
size = traverseCclosure(g, cl);
break;
}
case LUA_TTHREAD: {
lua_State *th = gco2th(o);
g->gray = th->gclist; /* remove from 'gray' list */
linkgclist(th, g->grayagain);
black2gray(o);
size = traversethread(g, th);
break;
}
case LUA_TPROTO: {
Proto *p = gco2p(o);
g->gray = p->gclist; /* remove from 'gray' list */
size = traverseproto(g, p);
break;
}
default: lua_assert(0); return;
}
g->GCmemtrav += size;
}propagatemark接口中：
（1）gray2black(o)：取灰色队列的队头并设置为黑，设置marked字段的BLACKBIT
（2）针对队头元素类型不同调用不同接口进行处理：
·table类型，取接口traversetable进行处理
非弱引用表，调用接口traversestrongtable进行处理，本质上遍历table的顺序数组和哈希表部分，调用接口markvalue进行处理。
弱引用表，则：
1）弱引用val表，调用接口traverseweakvalue处理，key部分markvalue常规处理，并将表放入grayagain表
2）弱引用key表，调用接口traverseephemeron处理，val部分通过reallymarkobject进行标记，然后把表放到grayagain中
3）kv都是弱引用，直接插入到allweak链表中
总结起来，在渐进标记阶段对于强引用表的key、val通过接口markvalue进行标记（就是进行灰色和黑色标记）；对于弱引用表强引用部分正常使用markvalue进行标记，弱引用部分丢到grayagain链表等到统一后面阶段统一处理。
·closure类型，取traverseLclosure和traverseCclosure处理
1）closure分为两个部分，proto部分和upvalue部分
2）proto部分，通过markobjectN进行处理，将proto添加到灰色表中
3）upvalue部分，非open状态的upvalue通过markvalue进行标记；open状态的upvalue在栈上，后续处理thread的时候会处理到，这里先标记
·thread类型，取traversethread进行处理
1）lua的线程中global_state->stack和global_stack->top分别存放线程栈的栈顶和栈底
2）traversethread在此阶段遍历栈，取里面每个object进行处理，调用接口markvalue进行标记
·proto类型，取traverseproto进行处理
1）proto包含upvalue、locvar、constant、proto几个部分
2）各个部分通过markobjectN进行处理
GCSatomic
当灰色节点已经被处理处理完毕之后if (g->gray == NULL){}垃圾回收进入GCSatomic阶段，分为几个部分：
propagateall
static void propagateall (global_State *g) {
while (g->gray) propagatemark(g);
} propagateall因为从propagate到atomic阶段非连续执行，期间节点状态可能会发生变化，因此在后续处理之前遍历gray链表，把残余的灰色节点处理完，以统一的状态进入下一状态。
atomic
static l_mem atomic (lua_State *L) {
GCObject *grayagain = g->grayagain; /* save original list */
g->gcstate = GCSinsideatomic;
markobject(g, L); /* mark running thread */
/* registry and global metatables may be changed by API */
markvalue(g, &g->l_registry);
markmt(g); /* mark global metatables */
remarkupvals(g);
propagateall(g); /* propagate changes */
work = g->GCmemtrav;
g->gray = grayagain;
propagateall(g); /* traverse 'grayagain' list */
g->GCmemtrav = 0; /* restart counting */
convergeephemerons(g);
clearvalues(g, g->weak, NULL);
clearvalues(g, g->allweak, NULL);
origweak = g->weak; origall = g->allweak;
work += g->GCmemtrav; /*stop count (objects being finalized) */
separatetobefnz(g, 0); /* separate objects to be finalized */
g->gcfinnum = 1; /* there may be objects to be finalized */
markbeingfnz(g); /* mark objects that will be finalized */
propagateall(g); /* remark, to propagate 'resurrection' */
g->GCmemtrav = 0; /* restart counting */
convergeephemerons(g);
/* at this point, all resurrected objects are marked. */
/* remove dead objects from weak tables */
clearkeys(g, g->ephemeron, NULL);
clearkeys(g, g->allweak, NULL);
/* clear values from resurrected weak tables */
clearvalues(g, g->weak, origweak);
clearvalues(g, g->allweak, origall);
luaS_clearcache(g);
g->currentwhite = cast_byte(otherwhite(g)); /
return work; /* estimate of memory marked by 'atomic' */
}（1）切换内存回收的状态为GCSinsideatomic
（2）GCSpropagate到GCSinsideatomic中间内存状态会发生变化，需要对：
·主线程：markobject(g,L)
·注册表：markvalue(g,&g->l_registry)
·原始元表：markmt(g)
·僵死线程：remarkupvals(g)，进行重新标记，加入gray
·并通过propagateall对gray和grayagain进行统一处理
·通过一系列clearvalues和clearkeys释放一些内存
·convergeephemerons?
1）global_state->ephemeron存放的是key为弱引用的table组成的链表
2）convergeephemerons中遍历链表，调用traverseephemeron接口处理
·切换currentwhite的白色状态
结合前面来看，因为在此执行序列中，期间创建的对象通过atomic接口在前面已经标记了一份，所以不存在临时创建但未标记的object，但是后续过程也是分步进行的，为避免出现冲突，在这里切换currentwhite状态，这样后续创建的对象的white为新类型且和之前的white类型不同，就不会被错误回收掉。
entersweep
static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
global_State *g = G(L);
int ow = otherwhite(g);
int white = luaC_white(g); /* current white */
while (*p != NULL && count-- > 0) {
GCObject *curr = *p;
int marked = curr->marked;
if (isdeadm(ow, marked)) { /* is 'curr' dead? */
*p = curr->next; /* remove 'curr' from list */
freeobj(L, curr); /* erase 'curr' */
}
else { /* change mark to 'white' */
curr->marked = cast_byte((marked & maskcolors) | white);
p = &curr->next; /* go to next element */
}
}
return (*p == NULL) ? NULL : p;
}
static void entersweep (lua_State *L) {
global_State *g = G(L);
g->gcstate = GCSswpallgc;
lua_assert(g->sweepgc == NULL);
g->sweepgc = sweeplist(L, &g->allgc, 1);
}entersweep做了两件事：
1）切换GC状态为GCSswpallgc
2）sweepgc指向后续垃圾回收的起始扫描位置，在当前位置指向allgc链表
为什么是指向g->allgc->next呢？因为entersweep之后，GC流程又进入了增量分步执行的状态，此期间有新对象创建又会挂在allgc链表头，被g->allgc指向，此时头部的元素一定为白且不能回收，为了避免这种情况，直接从第二个开始遍历回收即可。
GCSswpallgc
static lu_mem sweepstep (lua_State *L, global_State *g,
int nextstate, GCObject **nextlist) {
if (g->sweepgc) {
l_mem olddebt = g->GCdebt;
g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX);
g->GCestimate += g->GCdebt - olddebt;
if (g->sweepgc) /* is there still something to sweep? */
return (GCSWEEPMAX * GCSWEEPCOST);
}
/* else enter next state */
g->gcstate = nextstate;
g->sweepgc = nextlist;
return 0;
}
static GCObject **sweeplist (lua_State *L, GCObject **p, lu_mem count) {
global_State *g = G(L);
int ow = otherwhite(g);
int white = luaC_white(g); /* current white */
while (*p != NULL && count-- > 0) {
GCObject *curr = *p;
int marked = curr->marked;
if (isdeadm(ow, marked)) { /* is 'curr' dead? */
*p = curr->next; /* remove 'curr' from list */
freeobj(L, curr); /* erase 'curr' */
}
else { /* change mark to 'white' */
curr->marked = cast_byte((marked & maskcolors) | white);
p = &curr->next; /* go to next element */
}
}
return (*p == NULL) ? NULL : p;
}（1）GCSswpallgc这步做的工作包括：
回收global_state->allgc链表上的元素
并设置垃圾回收状态为GCSswpfinobj
设置下次链表回收的起始位置为global_state->finobj
（2）global_state->finobj这个链表存有具有回收接口的可回收对象；在lua中，当调用接口luaC_newobj创建一个可回收对象的时候，会将其添加到allgc列表中，但是在后续处理这个对象的时候，在lua_setmetatable里面，即设置元表的时候会检查，是不是设置了__gc元方法，若设置了，则通过接口luaC_checkfinalizer将这个对象移到finobj列表中
（3）前面提到Lua的三色标记法，分别是黑白灰三色，但实际上Lua的白色分为0型白色和1型白色，这是因为Lua的GC是渐进式分步骤进行的，在标记完成之后清理尚未完成之前，可能会有对象创建，因为对象在标记之后，默认是白色的，此时若是按照白色进行处理会被回收掉，又不能设置为黑（设置黑之后若是此对象不再被引用则就一直黑了，没办法翻白被回收）所以引申出0型白和1型白，叠加lua_state->currentwhite进行判断是否是当前白，当对象刚创建出来的时候，默认为白色，且白的类型和lua_state->currentwhite保持一致，此时清理的时候先判断是不是当前白luaC_white，是的话表示是垃圾回收阶段创建的对象，暂不清理，等下个阶段lua_state->currentwhite翻成另外一个类型白（假设上个阶段是0型白，下个阶段就变成1型阶段）这个在atomic接口进行，若此对象在下个阶段仍为白，则变成非当前白otherwhite表示非垃圾清理阶段创建的对象且未被引用，可以清理了
（4）而sweeplist，主要就是遍历垃圾回收链表p，对于里面的元素
·此节点为white节点&且非当前标白的节点（！0）
·GCObject->marked：用于记录当前对象的颜色：白色-0、白色-1、还是黑色；分别对应marked的bit-1（1<<0）、bit-2(1<<1)、bit-3（1<<2）
·在创建时设置上，表示当前对象是白色，且白的类型和lua_state->currentwhite一致
·isdeadm为true表示此对象为：
·否则标记此对象为当前白（同时也 把black标记bit给清除了）
（5）需要注意的是：
·lua_state->currentwhite的初始值为1，在atomic接口中会通过otherwhite进行切换，值的切换是1->2和2->1
·这里看代码有#define otherwhite(g) ((g)->currentwhite ^ WHITEBITS)，这是C的代码，所以这里的^代表的含义是异或，而初始值g->currentwhite = bitmask(WHITE0BIT)为1，在atomic中通过otherwhite进行切换，即1^3切换为2，和2^3切换为1
GCSswpfinobj
GCSswptobefnz
·依次处理链表g->finobj、g->tobefnz上的对象，并进行状态的切换
GCSswpend
·makewhite(g,g->mainthread)将mainthread重置为curr-white（luaC_white）
GCScallfin
static GCObject *udata2finalize (global_State *g) {
GCObject *o = g->tobefnz; /* get first element */
g->tobefnz = o->next; /* remove it from 'tobefnz' list */
o->next = g->allgc; /* return it to 'allgc' list */
g->allgc = o;
resetbit(o->marked, FINALIZEDBIT); /* object is "normal" again */
if (issweepphase(g))
makewhite(g, o); /* "sweep" object */
return o;
}
static void GCTM (lua_State *L, int propagateerrors) {
setgcovalue(L, &v, udata2finalize(g));
tm = luaT_gettmbyobj(L, &v, TM_GC);
if (tm != NULL && ttisfunction(tm)) { /* is there a finalizer? */
lu_byte oldah = L->allowhook;
setobj2s(L, L->top, tm); /* push finalizer... */
setobj2s(L, L->top + 1, &v); /* ... and its argument */
L->top += 2; /* and (next line) call the finalizer */
L->ci->callstatus |= CIST_FIN; /* will run a finalizer */
status = luaD_pcall(L,dothecall,NULL,savestack(L,L->top - 2), 0);
L->ci->callstatus &= ~CIST_FIN;
L->allowhook = oldah; /* restore hooks */
g->gcrunning = running; /* restore state */
if (status != LUA_OK && propagateerrors) { /* error while running __gc? */
if (status == LUA_ERRRUN) { /* is there an error object? */
luaO_pushfstring(L, "error in __gc metamethod (%s)", msg);
status = LUA_ERRGCMM; /* error in __gc metamethod */
}
luaD_throw(L, status); /* re-throw error */
}
}
}（1）Lua的对象创建之后，若是对象设置有元表，则这个对象会放到global_state->finobj链表里面管理，在垃圾回收过程中，在atomic阶段的separatetobefnz接口中，若finobj里面的对象不可达（即iswhite），则会被移入到global_state->tobefnz链表中。
（2）对于具有gc元方法的object，在当前轮次的垃圾回收并不直接回收，而是先执行其元方法，执行完毕之后放回到allgc链表中，等下次gc做回收，主要通过如下接口完成：
·udata2finalize将tobefnz链表中的对象放到allgc链表中；
·通过luaT_gettmbyobj取gc元方法，通过luaD_pcall执行；
因为对于Lua来说GC元方法可能是开协程执行的，所以很难说在一个回收周期里面做完，所以这里对具备回收条件的带元方法的对象，将gc方法和实际对象的回收放到两个回收周期里面做，避免执行流等待或者一些指令执行的时序问题。
参考文献
Lua GC机制分析与理解-上 - 知乎 (zhihu.com)
Lua垃圾回收机制和弱引用table - 简书 (jianshu.com)
Lua 5.3 设计实现(六) GC 垃圾回收 | Yuerer's Blog
云风的 BLOG: Lua GC 的工作原理 (codingnow.com)
深入 Lua Garbage Collector(四) | 趣果有间 (kelele67.github.io)
[Lua]弱表Weak table超越-CSDN博客lua 弱表
