lua5.3 垃圾回收分析

前注

最近我一直在看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 GCSatoimic阶段后不会再从头遍历 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 链表为空,切换到 GCSatoimic
GCSatoimic 不分步 再次遍历 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什么情况下会卡顿?
以上看出, GCSatoimic 最有可能造成卡顿。
1、GCSatoimic 不能分步执行
2、GCSpropagate 分步执行是有副作用的,这段时间, rootgc 可能会引用新的白色对象,已标记黑色的 table 引用了白色对象,这些数据都需要在 GCSatoimic 重新遍历和标记
3、弱表处理,没有分步执行

所以,以下几种情况 GCSatoimic 的开销会比较大:
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

发表评论

邮箱地址不会被公开。 必填项已用*标注