• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

深入探究Lua的GC算法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

对于内存的管理,是程序在应用的时候的必需知识点,《Lua设计与实现》中对Lua语言的GC原理做了一个详细的讲解,云风的blog也对其进行了详尽的讲解Lua GC 的源码剖析 系列

给出作者 

 在github上的lua源码链接:https://github.com/lichuang/Lua-5.1.4-codedump

这儿就继续做《Lua设计与实现》的阅读笔记,对Lua GC原理及其过程做一个详尽的讲解,由于篇幅较大,就一分为二,写上下篇来讲解整个过程。


一、GC的原理及其算法设计

不同的语言,对GC算法的设计不同,常见的GC算法是引用计数和Mark-Sweep算法, c#采用的是Mark-sweep && compact算法, Lua采用的是Mark-sweep算法,分开说一下:

引用计数算法:在一个对象被引用的情况下,将其引用计数加1,反之则减1,如果计数值为0,则在GC的时候回收,这个算法有个问题就是循环引用。

Mark-sweep算法:每次GC的时候,对所有对象进行一次扫描,如果该对象不存在引用,则被回收,反之则保存。

在Lua5.0及其更早的版本中,Lua的GC是一次性不可被打断的过程,使用的Mark算法是双色标记算法(Two color mark),这样系统中对象的非黑即白,要么被引用,要么不被引用,这会带来一个问题:在GC的过程中如果新加入对象,这时候新加入的对象无论怎么设置都会带来问题,如果设置为白色,则如果处于回收阶段,则该对象会在没有遍历其关联对象的情况下被回收;如果标记为黑色,那么没有被扫描就被标记为不可回收,是不正确的。


为了降低一次性回收带来的性能问题以及双色算法的问题,在Lua5.1后,Lua都采用分布回收以及三色增量标记清除算法(Tri-color incremental mark and sweep)


其基本的原理伪代码,参考书中原文为:

每个新创建的对象颜色设置为白色

//初始化阶段

遍历root节点中引用的对象,从白色置为灰色,并且放入到灰色节点列表中

//标记阶段

while(灰色链表中还有未扫描的元素):

从中取出一个对象,将其置为黑色

遍历这个对象关联的其他所有对象:

if 为白色

标记为灰色,加入到灰色链表中(insert to the head)

//回收阶段

遍历所有对象:

if 为白色,

没有被引用的对象,执行回收

else

重新塞入到对象链表中,等待下一轮GC


二、GC的数据结构

分析Lua中对于需要GC的类型数据

#define iscollectable(o) (ttype(o) >= LUA_TSTRING)

都会有一个基本的定义CommonHeader,其定义为:

next: GCObject链表指针,该指针用来将所有的GC对象都链接在一个表中;

tt: 数据类型:nil, boolean, number, string...

marked: 标记字段,byte表示的字段颜色定义为

这儿特定解释一下为什么会有两种白色,前面提到,5.1后的Lua采用的是三色标记算法,其实质是四色标记算法,分为0型白色和1型白色,在GC回收的时候,会设置当前的白色为其中一种,详见globalstate中的currentwhite,这样在代码回收的时候,如果当前对象的白色不为currentwhite,则认为其不可回收,这样的对象需要等到下一次的GC才能决定是否回收,具体参看后面的,会有对应的应用。对于global_state的设计为:

具体的参数的作用,详见注释,就不在一一解释了


三、GC的流程

1、数据的创建

想要了解GC的过程,首先看看数据是怎么在创建的时候被链接到GC链表中的,主要分为三种数据的创建

1) 一般数据的创建 luaC_link

简单直接,直接insert to the head

2) upval的创建 luaC_linkupval

3) userdata(udata)的创建 luaS_newdata


2、开始GC

整个GC过程分为五个阶段,其定义为

其执行GC的函数为singlestep,来看第一步的操作:


进一步看看markroot的操作:

其实就是reset一遍相关的变量,然后标记mainthread, G表,registry表,然后切换到下一个标记阶段。

参看定义:

最后都要执行reallymarkobject函数(此处需要展示一下我的竖屏截图便利了:D):

基本的注释都解释了各个对象是如何的处理的,udata是不会引用其他类型的数据,所以一步到黑色,upvalue则根据是否为close来决定是否标记到黑色,open状态的upvalue变化较为频繁,需要在后面的remarkupvals中解决。


3、GC的扫描阶段 GCSpropagate

只要处于这个阶段,就会分2种情况执行,一个是propagatemark,一个是atomic,让我们分别看其实现过程。

首先看处于灰色链表中一直都有对象的情况,在这步操作当中,是可以分步操作的,整个GC的分步操作,就是在这一步操作中,在每次扫描后,都会返回本次扫描标记的对象的大小之和,再下一个分步执行的时候再继续执行,而一旦进入atomic函数中,就需要一次性的执行,不能再分步执行了。

来看propagatemark函数是如何实现的:

对于table,如果该表是weak表,则退回到灰色状态,否则遍历表的数组和散列表部分进行标记,详见traversetable函数;

对于func,traverseclosure主要对func中的upval进行标记;

对于thread, 则将其移植到grayagain中,放在atomic中进行处理;

对于proto,对其中的字符串、upvalue、局部变量等进行遍历标记;

注意,这儿没有处理string\udata类型数据,这是放在其他部分进行的,不需要进行相关的标记;


4、GC 扫描阶段的barrier操作

由于采用分步式增量扫描标记算法,所以会出现在分步操作过程中,新增加的对象与被扫描过的对象之间有引用关系的变化,未来确保黑色对象引用的对象中有白色对象,lua提供了两种操作设计:

1)标记过程向前走一步 luaC_barrierf

如果新建对象是白色,而它被一个黑色对象引用了,那么将这个新建对象颜色从白色变为灰色;

2)标记过程向后走一步 luaC_barrierback

类似于上,此时将引用的它的黑色对象的颜色从黑色变为灰色,使得其重新被扫描一次

(或许你看出截图颜色变了,是的,回家了,又是新的编辑器了~)

从define可以看出,只有table需要进行luaC_barrierback,这是由于table本身设计,就是一个table可能会对应N个key或者value,这样如果新增一个key/value,如果将其置为灰色,然后将其加入gray链表中,这样多个添加会带来较大的性能。

采用向后,就是将该table对象退回到gray状态,这样添加多个,其实质都是只改变该table一次,注意这个gray不是改为gray链中,而是将该table加入到grayagain链中,在扫描完gray链后再扫描grayagain链即可。参考源码即可:

对比向前比较简单了:直接调用reallymarkoject


5、GC的atomic操作

当gray链表中对象都标记完成后,会执行一次atomic操作,注意这个操作是不能被打断的,所以叫原子操作,参考源码:

首先处理上一篇文章中提到的对open状态的upvalues,然后处理一次gray链表;

然后处理整个弱表,将lua_State指针指向meta表,然后处理一次gray链表

然后处理grayagain链表,类似于上

然后处理udata,其处理函数为luaC_separateudata:

注释很详细,注意放到tmudata链表中后,是在后续操作再集中处理一次;

处理完基本的几个数据后,atomic会把白色类型切换到下一个GC操作的白色类型,然后修改状态到回收阶段CGSsweepstring, 这儿对sweepstrgc进行了赋初值,是为了下面的字符串定位。


6、GC的回收阶段 GCSsweepstring/GCSsweep

首先进入的回收阶段是对字符串的处理

虽然是case,但是其实质是一个循环,每次取出散列表中的一个字符串链表,进行一次遍历回收,sweepwholelist最终会调用到sweeplist,等一下给出源码。

当处理完所有的字符串后,切换到GCSsweep状态:

关键操作是sweeplist,参看其源码:

代码中也对前面说的多色标记中的两种白色的作用做了讲解,otherwhite就是本次不可回收的白色,如果处理的对象的白色就是otherwhite,是不会被回收的


7、结束阶段 GCSfinalize

这是整个GC的最后阶段了,来看看其操作的源码:

首先处理,是否有前面提到的tmudata链表, 其操作函数为GCTM:

注意,udata本身有GC方法,未来确保其GC方法的调用,实在这次GC中调用G方法,但是这个udata本身,是在下一次的GC中才会被回收的。udata的GC调用则是在fasttm中调用TM_GC来实现。

初看也会迷糊怎么循环的,其实结合上面的case中的 if(g->tmudata)可以理解,为什么每次GCTM都会执行 g->tmudata的移动赋值操作。


最终万事大吉,本次GC流程走完,设置到GCSpause状态,等待下一次GC调用。


8、GC的进度控制

其实GC的调用,可以分为两种,一种是自动调用,一个是手动调用

自动调用函数: luaC_checkGC

一般不希望自动GC,可以采用setthreshold,将GCthreshold的值设置为非常大,这样不回自动触发GC

手动调用,则设置GC的相关参数 setthreshold:

estimate是对当前内存使用量的一个预估值,gcpause是一个百分比,通过lua_gc可以设置,另一个gc进度的参数是gcstepmul,其主要影响singlestep函数的调用次数,具体原因参看源码:

整个流程都在注释中讲解了,其中关键是lim的设置,然后不断的调用singlestep, 然后处理GC状态即可,注意setthreshold是设置的两次GC之间的时间间隔。由于修改了threshold,对于关闭自动GC的情况,需要再次重新设置关闭自动GC一次。


9、总结

对于lua的GC的原理的探究就到这儿,熟悉一门语言的GC流程后,同理去推导理解其他语言的GC会有很大帮助,同时也可以在平时使用lua的时候,对于GC的一些操作更加知其所以然。大家共勉!



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
openresty 常用Lua开发库Json库、cache 使用、编码转换发布时间:2022-07-22
下一篇:
Lua闭包使用心得发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap