前注
最近我一直在看lua gc，阶段性做一下总结。网上很多文章没讲明白，我也当弥补下这个问题。文章以我看的lua 5.3.6做分析。
lua 垃圾回收发展历程
5.0 及以前使用的是双色标记清除法，gc 过程会停止主程序执行，直到 gc 完成；
5.1 实现了增量式 gc，采用三色标记法，gc 过程分多步，与主程序交替执行；
5.2 实现了分代 gc，实际效果不理想；
5.3 移除了分代 gc；
5.4 重新实现了分代 gc
两种标记清除算法
标记清除算法，就是遍历所有对象，将还在使用的对象打上标记，遍历完成后，没有标记的对象就是垃圾对象，要清理掉。
所以，系统至少需要记录两个数据集合，一个是所有的对象集合，一个是还在使用的对象集合。在 lua 中，还在使用的对象集合包括了全局变量、 栈中对象、处于激活状态的协程等。
双色标记清除法
- white状态：待访问状态。表示对象还没有被访问到。
- black状态：已访问状态。表示对象已经被访问到了。
步骤：
1. 初始时，所有对象都是标记white
2. 将root GC遍历对象，将访问过的对象标记black
3. 结束后，white的即为不可达对象，进行回收。
特点：
| 优点 | 实现简单 |
| 缺点 | gc 过程不可中断，需要暂停主程序。gc 过程中，white可能是未访问的对象，也可能是不可达对象，如果中断了，得从头开始。 |
三色标记清除法
- white状态：待访问状态。表示对象还没有被访问到。
- gray状态：待扫描状态。表示对象已经被访问到了，但是对象对其他对象的引用还没有全部访问。
- black状态：已扫描状态。表示对象已经被访问到了，并且对象对其他对象的引用已经全部访问了。
步骤：
1. 初始时，所有对象都标记white；
2. 将root GC遍历对象，标记gray，并加入gray链表；
3. 从gray链表中取出对象：
① 将该对象引用到的其他对象标记 gray，并加入gray链表；
② 将该对象标记 black。
4. 重复步骤3，直至gray链表为空时结束；
5. 结束后，white的即为不可达对象，进行回收。
特点：
| 优点 | gc可以中断，与主程序交替执行。black对象引用white对象后，black对象可回退为gray，或者white对象向前标记为gray，具体操作看对象类型，如果是table，回退为gray可避免频繁检查。 |
| 缺点 | 实现复杂 |
效果图：
提出问题
1. lua 需要gc的是哪些数据？
2. lua gc是怎么触发的？
3. lua 怎么判定数据可达？
4. 为什么用两种白色标记？
5. lua gc调优？
6. lua gc什么情况下会卡顿？
1. lua 需要gc的是哪些数据？
所有对象都要接受gc管理回收，但实际参与计算的，为table, string, closure, userdata, thread(coroutines), proto, upvalue 。
2. lua gc是怎么触发的？
2.1 自动触发 gc
/*
** Does one step of collection when debt becomes positive.
** 'condchangemem' is used only for heavy tests
*/
#define luaC_condGC(L,pre,pos) \
{ if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; \
condchangemem(L,pre,pos); }
#define luaC_checkGC(L) luaC_condGC(L,(void)0,(void)0)
在以下代码中，使用 luaC_checkGC 检查 gc 阈值 GCdebt ，当 GCdebt 大于0 时，执行 gc
1、创建新数据时 string, thread, userdata, table, closure
3、语法解析时
4、错误发生时
5、字符串拼接时 concat
6、栈增长时
备注：这里提下 GCdebt，字面意思就是 gc 债务，用以调节 gc 是否触发。当 GCdebt 大于0时，触发 gc， 而且，gc 单次的工作量也受这个参数影响。另外，跟这个参数有关的，lua 申请的总内存不是 totalbytes，而是 totalbytes + GCdebt，totalbytes 会根据 GCdebt 变化而变化，始终保持 totalbytes + GCdebt 为内存总量
2.2 手动触发 gc
使用 lua API：
collectgarbage "step"
collectgarbage "collect"
3. lua 怎么判定数据可达？
从 GC根集合（root set） 可访问的对象：
gc root set包含三部分：
1、主协程 g->mainthread，其栈记录了当前用到的所有对象
2、注册表 g->l_registry，包含了全局table(_G)，记录了全局变量和全局模块，还包括已加载的模块表 package.loaded
3、全局元表 g->mt，每种数据类型各一个，预留9个，暂时只有table和string的实现，效果如io模块的f:read()和 string模块的s:len()
备注：在 lua 5.0/5.1 中，rootgc 是指所有可回收对象，在 lua 5.2 之后, 取消了 rootgc 定义，改为 allgc。 一般情况下，root gc 是指存活对象，但具体项目得看作者定义，root 只表达了“根”集合，所以，root gc 表达所有可回收对象集合，或是所有存活对象集合都没有什么问题。
4. 为什么用两种白色标记？
假设只有一种白色标记，在gc过程中产生的新数据，标记白色的话，等到gc清理阶段，白色数据会被清理掉。
那么，新数据标记成黑色是否可行？
先说结论，可行，但可能会造成内存不及时清理。
看下 lua 新建数据的方法：
新加的数据，都会加到 g->allgc （可回收对象链表）头部，如果设置为黑色，在 gc GCSatomic阶段后不会再从头遍历 g->allgc，导致本次 gc 结束后黑色标记无法变为白色，数据要等到下下次 gc 才能被清理掉。
5.lua gc 调优？
collectgarbage ([opt [, arg]])
这个函数是 lua 垃圾回收的通用接口，通过不同参数，对外提供了不同的功能：
| "collect" | 做一次完整的垃圾收集循环。 这是默认选项。 |
| "stop" | 停止垃圾收集器的运行。 在调用重启前，收集器只会因显式的调用运行。 |
| "restart" | 重启垃圾收集器的自动运行。 |
| "count" | 以 K 字节数为单位返回 Lua 使用的总内存数。 这个值有小数部分，所以只需要乘上 1024 就能得到 Lua 使用的准确字节数（除非溢出）。 |
| "step" | 单步运行垃圾收集器。 步长“大小”由 arg 控制。 传入 0 时，收集器步进（不可分割的）一步。 传入非 0 值， 收集器收集相当于 Lua 分配这些多（K 字节）内存的工作。 如果收集器结束一个循环将返回 true 。 |
| "setpause" | 将 arg 设为收集器的间歇率。 返回 间歇率 的前一个值。 |
| "setstepmul" | 将 arg 设为收集器的步进倍率。 返回 步进倍率 的前一个值。 |
| "isrunning" | 返回表示收集器是否在工作的布尔值 （即未被停止）。 |
以上来源于云风的lua文档翻译，是我找到关于这块最好的中文注释了。
5.1 调整 gc 步进倍率
collectgarbage("setstepmul", Number)
值越小，gc步进倍率越小，默认值200，最小值40，这个参数的作用是什么？
先看下 g->gcstepmul 的代码，可以看出，lua 单步 gc 受这个参数影响。
/*
** get GC debt and convert it from Kb to 'work units' (avoid zero debt
** and overflows)
*/
static l_mem getdebt (global_State *g) {
l_mem debt = g->GCdebt;
if (debt <= 0) return 0;
else {
debt = (debt / STEPMULADJ) + 1;
debt = debt * g->gcstepmul;
return debt;
}
}
/*
** performs a basic GC step when collector is running
*/
void luaC_step (lua_State *L) {
global_State *g = G(L);
l_mem debt = getdebt(g);
do {
lu_mem work = singlestep(L); /* perform one single step */
debt -= work;
} while (debt > -GCSTEPSIZE && g->gcstate != GCSpause);
debt = (debt / g->gcstepmul) * STEPMULADJ; /* convert 'work units' to Kb */
luaE_setdebt(g, debt);
}
再看下 STEPMULADJ 和 g->gcstepmul 的默认值：
#define STEPMULADJ 200
#if !defined(LUAI_GCMUL) #define LUAI_GCMUL 200 /* GC runs 'twice the speed' of memory allocation */ #endif g->gcstepmul = LUAI_GCMUL;
这个参数影响了什么？
以上代码可以看出，就算 gc 什么事没做 （singlestep 返回0），debt 都会加 STEPMULADJ，保证 gc 向前推进。
但实际每次增加的 gc 工作 （work），为 g->gcstepmul，也就是说，g->gcstepmul 的值越大，单步能处理的 gc 工作 （work）就越多
5.2 调整 gc 间歇率参数
collectgarbage("setpause", Number)
设置 gcpause，并返回原来的 gcpause
值越小，表示gc暂停频率越低，也就是说，gc变得越频繁。默认值为200，为2倍暂停阈值大小，表示申请内存小于实际使用的2倍时，暂停gc
debt = gettotalbytes(g) - g->GCestimate * g->gcpause / PAUSEADJ; #define PAUSEADJ 100
5.3 单步运行垃圾收集器
collectgarbage("step", Number)
值为空或0，表示 gc 前进一步； 否则表示增加多少 debt，检查一次是否 gc，但未必会触发 gc
在 gc 暂停期间，此接口仍可执行 gc，且不改变 gc 原来的状态
6. lua gc什么情况下会卡顿？
先说下 gc 状态机
| 状态 | 分步 | 工作 |
|---|---|---|
| GCSpause | 不分步 | 开启新一轮 gc，遍历 rootgc 开始 mark（标记），table/proto/closure/thread 对象标记为 gray，加入 g->gray 链表，string/userdata 对象标记为黑色。遍历完成后，切换到 GCSpropagate |
| GCSpropagate | 分步 | 每次从 g->gray 链表取出一个对象，先标记为 black。如果对象是弱表或 thread，则加入 g->grayagain 链表，然后遍历这个对象的子项开始 mark，把没有标记的对象都标记了。当 g->gray 链表为空，切换到 GCSatomic |
| GCSatomic | 不分步 | 再次遍历 rootgc 开始 mark，对 GCSpropagate 期间可能的改变再重新标记，将未标记的对象加入 g->gray 链表。遍历 g->gray 链表取所有对象完成标记。遍历 g->grayagain 链表取所有对象完成标记，遍历弱表，将白色的项置为nil。遍历 g->finobj 链表，把白色的对象移到 g->tobefnz 链表。遍历 g->tobefnz 链表，完成 mark。切换当前白色到另一种白色。切换到 GCSswpallgc |
| GCSswpallgc | 分步 | 每次取 g->allgc 链表一定数量的对象, 将还是上一种白色的对象清理掉。同时将黑色对象标记为当前白色。当 g->allgc遍历完成，切换到 GCSswpfinobj |
| GCSswpfinobj | 分步 | 同上处理 g->finobj 链表。切换到 GCSswptobefnz |
| GCSswptobefnz | 分步 | 同上处理 g->tobefnz 链表。切换到 GCSswpend |
| GCSswpend | 不分步 | 收缩全局 string 的hash表，保证hash桶利用率超过 1/4， 切换到 GCScallfin |
| GCScallfin | 分步 | 每次取 g->tobefnz 链表一定数量的对象，将对象标记为白色，加入 g->allgc 链表 。 执行对象的 __gc meta函数。当 g->tobefnz 为空时，切换到 GCSpause |
再重点说下以上提到的几个变量：
g->allgc: 所有可回收的对象链表。
g->finobj: 带 __gc meta函数的对象链表。
g->tobefnz: 没有引用的带 __gc meta函数的对象链表。
新建对象时，对象会加入 g->allgc 链表，当对象设置 __gc meta函数时，这个对象会从 g->allgc 移到 g->finobj 链表，当这个对象不再引用后，从 g->finobj 移到 g->tobefnz，执行 __gc meta函数后，对象再移回到 g->allgc，等下一次 gc 清理。
g->gray: 等待遍历的对象链表
g->grayagain: 等待 g->gray 为空后，再遍历的对象链表
g->grayagain 的用途：
1. GCSpropagate 阶段的弱表。要扫描完所有对象后，才可以对弱表进行处理。
2. 黑色 table 引用白色对象时。如果又加入 g->gray，会导致 table 又被反复扫描
3. 协程。要等协程栈中对象都处理完，才可以对协程进行处理。
好了，回到题目：lua gc什么情况下会卡顿？
以上看出， GCSatomic 最有可能造成卡顿。
1、GCSatomic 不能分步执行
2、GCSpropagate 分步执行是有副作用的，这段时间， rootgc 可能会引用新的白色对象，已标记黑色的 table 引用了白色对象，这些数据都需要在 GCSatomic 重新遍历和标记
3、弱表处理，没有分步执行
所以，以下几种情况 GCSatomic 的开销会比较大：
1、系统不断产生大量大 table
2、不断有大量大 table 引用新数据
3、大量使用弱表
结束语
文章到这里就结束了，感谢阅读，有问题可以撩我。后面我找机会再研究下 lua 5.4 gc
参考链接：
http://wiki.luajit.org/new-garbage-collector
https://www.lua.org/wshop18/Ierusalimschy.pdf
http://cloudwu.github.io/lua53doc/manual.html