接上篇高级内存管理，这篇分析一下lua的gc机制
lua的gc概述
lua的垃圾回收gc是一个很经典的实现。本文是基于的lua5.3.6版本的源码进行分析。lua的gc算法采用了标记清除算法。在Lua中字符串、表、用户数据、函数、线程、 内部结构等对象，都使用GC模块进行管理。
标记清除算法
该算法分为两个阶段：
标记阶段：gc进行回收过程，从若干根节点依次遍历进行标记，这样就把所有可以访问到的节点都进行了标记
清除阶段：遍历所有的节点，把上述标记阶段没有标记的节点全部进行清除
这个就是该算法的核心思想，lua早期版本只采用黑白两色标记，导致gc过程需要一次完成，后期版本采取了三色标记法，加入了一个灰色这样可以增量完成。
三色介绍
颜色就是算法描述的标记阶段标记，5.3版本的总共用了黑白灰三个颜色标记，下面描述一下这三个颜色, 这里特别说明下白色分为当前白和其他白。
白色：表示可以回收的状态，新创建的对象的初始状态就应该被设定为白色，如果该对象在GC标记阶段结束后，仍然为白色则此时白色代表当前对象为可回收状态。但其实本质上白色的设定就是为了标识可回收。这里的白色都是指代当前白。
灰色：中间状态，当前对象已经被GC访问过，但是该对象引用的其他对象还没有被标记。
黑色：不可回收状态，当前对象已经访问过了，并且该对象引用的其他对象也被标记过。
特殊：当前白和其他白。原因是gc在标记阶段和清除阶段之间，lua虚拟机仍然可能创建新的对象。这个时候如果还被标记当前白，就会导致错误的清除该对象，所有设计了这两个白色。这个时候用其他白作为新对象的标记色。清除的时候仍然可以合理清除掉。然后清除完毕了把黑色的设置为其他白, 然后虚拟机切换自己的当前白为其他白，这里设计比较巧妙。总之就是有两个白色，虚拟机在每轮gc的时候回来回切换白色，另外一个白色就降为其他白。
gc的具体实现
在分析gc的具体实现，先来做一些准备工作
数据对象的创建
//lobject.h
/*
** Common type for all collectable objects
*/
typedef struct GCObject GCObject;
/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/
#define CommonHeader GCObject *next; lu_byte tt; lu_byte marked
/*
** Common type has only the common header
*/
struct GCObject {
CommonHeader;
};
/*
** Union of all Lua values
*/
typedef union Value {
GCObject *gc; /* collectable objects */
void *p; /* light userdata */
int b; /* booleans */
lua_CFunction f; /* light C functions */
lua_Integer i; /* integer numbers */
lua_Number n; /* float numbers */
} Value;
#define TValuefields Value value_; int tt_
typedef struct lua_TValue {
TValuefields;
} TValue;lua中的数据全部是以TValue来实现的，具体该数据是什么类型依赖tt_字段，之类分为需要被gc管理回收的和不需要。需要被管理的数据类型有TString、Udata、Cloure、Table、Proto、lua_State这些。 需要被管理的都可以统一转换为GCObject类型，他们都有一个共同的部分CommonHeader,这里有三个字段next，tt和marked, next是指向下一个元素的指针，用于保存所有的GCObject， tt是数据类型和tt_一致，marked是上述算法提到的颜色标记
接下来我们来看看创建数据类型的函数，创建所有的gc回收的函数最后都会调用(lgc.c)luaC_newobj这个函数，以table创建为例
//ltable.c
Table *luaH_new (lua_State *L) {
GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
Table *t = gco2t(o);
t->metatable = NULL;
t->flags = cast_byte(~0);
t->array = NULL;
t->sizearray = 0;
setnodevector(L, t, 0);
return t;
}
//lgc.c
Object *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;
}
#define luaC_white(g) cast(lu_byte, (g)->currentwhite & WHITEBITS)从创建函数luaC_newobj我们可以看到主要做了三件事
- 创建table所需要的内存，通过调用luaM_newobject来创建(lua本身没有使用内存池, 就是用的操作系统提供的realloc函数进行分配的)
- 颜色标记为当前白， 这里使用的就是(g)->currentwhite 来进行操作的
- 把该对象挂载到g->allgc链表上, GC的所需要管理的所有生命周期的元素都在这个链表上
我们知道的数据类型创建以及位置，下面就可以进入正式的gc之旅了
gc触发
gc触发分为手动和自动触发
//手动触发
LUAI_FUNC void luaC_step (lua_State *L);
//自动触发
#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)手动触发没啥好说的,直接调用触发，自动触发机制需要满足GC的条件,这个条件通过g-> GCdebt、g-> totalbytes等参数计算来触发，本文就不讨论这部分内容。这两个最后都会调用到gc最重要的一个函数singlestep。
singlestep内部就是一个简单的状态机，会根据g->gcstate执行特定的环节的操作， 默认状态是GCSpause
标记阶段
GCSpause
//lgc.c
/*
** 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 */
}
switch (g->gcstate) {
case GCSpause: {
g->GCmemtrav = g->strt.size * sizeof(GCObject*);
restartcollection(g);
g->gcstate = GCSpropagate;
return g->GCmemtrav;
}
}这个阶段是gc的开始，主要是restartcollection， 其他是记录信息用作gc启动条件的，简单提一下。 目前阶段不存在任何的灰色对象。进行初始化清空灰色对象链表，其中g->gray是灰色节点链；g->grayagain是需要原子操作标记的灰色节点。其他三个示弱表链表这里不讨论。
然后依次标记markobject、markvalue、markmt、markbeingfnz。 这些分别对mainthread(主线程(协程), 注册表(registry), 全局元表(metatable), 上次GC循环中剩余的finalize中的对象。就是从root依次遍历可以到达的对象进行标记
这里底层会调用reallymarkobject, 这个函数会按照数据类型进行灰色或者黑色标记，灰色的加入grey链表里
/*
** 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;
}
}可以看到string和userdata直接标记为黑
GCSpropagate
/*
** traverse one gray object, turning it to black (except for threads,
** which are always gray).
*/
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;
…
default: lua_assert(0); return;
}
g->GCmemtrav += size;
}
case GCSpropagate: {
g->GCmemtrav = 0;
lua_assert(g->gray);
propagatemark(g);
if (g->gray == NULL) /* no more gray objects? */
g->gcstate = GCSatomic; /* finish propagate phase */
return g->GCmemtrav; /* memory traversed in this step */
}在该阶段就是从灰色链表取一个对象，然后标记黑色，根据它的类型分别进行遍历。图里就是table类型，调用traversetable进行遍历，把能访问到的对象进行标记(也是通过reallymarkobject进行的标记。
这里要说明一下的是，可以看到这里不是一个循环而是执行一次，当gray == NULL才会设置下一个状态。这里好处就可以减少阻塞的时间，更加及时的响应lua虚拟机运行
GCSatomic
case GCSatomic: {
lu_mem work;
propagateall(g); /* make sure gray list is empty */
work = atomic(L); /* work is what was traversed by 'atomic' */
entersweep(L);
g->GCestimate = gettotalbytes(g); /* first estimate */;
return work;
}
static void propagateall (global_State *g) {
while (g->gray) propagatemark(g);} 关于写屏障机制luaC_barrier这里提一下，因为我们都是单步执行的不像之前是stop the world一次搞完。所以会有一种情况我标记了黑色，然后修改了它，这时候就需要这个机制根据标记颜色进行再次修订，让gc感知到这个变化。
回到代码会发现先调用了propagateall再次检查gray链表，这是因为写屏障机制luaC_barrier会操作gray这个链表
对于atomic函数，这里只关乎主要流程，忽略一些细节
- 重新遍历根对象(当前thread, 注册表l_registry, 全局metatable, 线程相关的上值), 主要是因为这些值中有些是已经标记过但还可能会被修改，并且是没有使用写屏障的。还有这些值已经标记过不会在处理所以不会造成重复计算。
- 遍历一些grayagain，然后清理。这里提一下这个用于存放一些易变化的对象同时也有弱表。跟gray链表有点像但是单独存放。
- 将当前白色值切换到新一轮的白色值(在此之后,所有新建的对象虽然也为白色,但是在GC循环走完之前并不会被回收),
接下来是entersweep(L)函数
/*
** Enter first sweep phase.
** The call to 'sweeplist' tries to make pointer point to an object
** inside the list (instead of to the header), so that the real sweep do
** not need to skip objects created between "now" and the start of the
** real sweep.
*/
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);
}这里要说明的是通过sweeplist遍历g->allgc，然后g->sweepgc记录当前的位置。sweeplist的第三个参数1代表遍历访问几个元素。
这里之所以这样设计在该原子操作阶段进行一次清除操作， 该阶段结束后又会进行增量模式，添加的新对象是放在g->allgc表头的而且必然不会被回收的。这样可以尽可能的避免这种干扰。
GCSatomic状态之后又进入增量模式，接着就是GCSswpallgc状态。
清除阶段
case GCSswpallgc: { /* sweep "regular" objects */
return sweepstep(L, g, GCSswpfinobj, &g->finobj);
}
case GCSswpfinobj: { /* sweep objects with finalizers */
return sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
}
case GCSswptobefnz: { /* sweep objects to be finalized */
return sweepstep(L, g, GCSswpend, NULL);
}
case GCSswpend: { /* finish sweeps */
makewhite(g, g->mainthread); /* sweep main thread */
checkSizes(L, g);
g->gcstate = GCScallfin;
return 0;
}
case GCScallfin: { /* call remaining finalizers */
if (g->tobefnz && g->gckind != KGC_EMERGENCY) {
int n = runafewfinalizers(L);
return (n * GCFINALIZECOST);
}
else { /* emergency mode or no more finalizers */
g->gcstate = GCSpause; /* finish collection */
return 0;
}
}这个过程就是垃圾分类回收
GCSswpallgc就是通过上述的sweeplist增量的把g->allgc上面的死对象回收掉并且将或对象标记为当前白
GCSswpfinobj，GCSswptobefnz也是调用sweeplist进行清除并且标记，主要是对global_State.finobj和global_State.tobefnz链表，这里是用于当对象回收时候想要调用一些自己设置的回收函数，比如关闭连接等等之类的。
GCSswpend用来释放mainthread上的一些空间，如：字符串表，连接缓冲区等。
整个大循环最后一步就是GCScallfin，会遍历global_State.tobefnz链表上的对象，然后调用其__gc函数（就是自定义回收函数），然后把它放入global_State.allgc链表中，会在下个GC循环回回收
总结
到这gc的算法已经分析完毕了，像弱表，写屏障，greyagain，global_State.finobj以及gc触发机制都只是简单提了一下，和本主题不是强相关就忽略了。
最后总结一下该算法
1.用一个global_State.allgc保存所有的要管理的内存对象
2.从root节点开始标记能访问到的对象。GC只要发现一个可回收对象就标记为灰，然后遍历它所能访问到的对象
3.该对象没有可以访问的，标记为黑
4.递归重复2，3直到完成所有可访问的对象被遍历完毕为止
5.GC清除掉所有白色对象
写在最后，欢迎有任何建议和想法或者指出哪里写的不足的地方的童鞋联系我~~~
