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

探索Lua5.2内部实现:Garbage Collection

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

Lua5.2采用垃圾回收机制对所有的lua对象(GCObject)进行管理。Lua虚拟机会定期运行GC,释放掉已经不再被被引用到的lua对象。

基本算法

基本的垃圾回收算法被称为"mark-and-sweep"算法。算法本身其实很简单。

首先,系统管理着所有已经创建了的对象。每个对象都有对其他对象的引用。root集合代表着已知的系统级别的对象引用。我们从root集合出发,就可以访问到系统引用到的所有对象。而没有被访问到的对象就是垃圾对象,需要被销毁。

我们可以将所有对象分成三个状态:

  1. White状态,也就是待访问状态。表示对象还没有被垃圾回收的标记过程访问到。
  2. Gray状态,也就是待扫描状态。表示对象已经被垃圾回收访问到了,但是对象本身对于其他对象的引用还没有进行遍历访问。
  3. Black状态,也就是已扫描状态。表示对象已经被访问到了,并且也已经遍历了对象本身对其他对象的引用。
基本的算法可以描述如下:

[plain] view plain copy
  1. 当前所有对象都是White状态;  
  2. 将root集合引用到的对象从White设置成Gray,并放到Gray集合中;  
  3. while(Gray集合不为空)  
  4. {  
  5.     从Gray集合中移除一个对象O,并将O设置成Black状态;  
  6.     for(O中每一个引用到的对象O1) {  
  7.         if(O1在White状态) {  
  8.             将O1从White设置成Gray,并放到到Gray集合中;  
  9.         }  
  10.     }  
  11. }  
  12. for(任意一个对象O){  
  13.     if(O在White状态)  
  14.         销毁对象O;  
  15.     else  
  16.         将O设置成White状态;  
  17. }  

Incremental Garbage Collection

上面的算法如果一次性执行,在对象很多的情况下,会执行很长时间,严重影响程序本身的响应速度。其中一个解决办法就是,可以将上面的算法分步执行,这样每个步骤所耗费的时间就比较小了。我们可以将上述算法改为以下下几个步骤。

首先标识所有的root对象:

[plain] view plain copy
  1. 当前所有对象都是White状态;  
  2. 将root集合引用到的对象从White设置成Gray,并放到Gray集合中;  

遍历访问所有的gray对象。如果超出了本次计算量上限,退出等待下一次遍历:

[plain] view plain copy
  1.   

while(Gray集合不为空,并且没有超过本次计算量的上限)

{ 从Gray集合中移除一个对象O,并将O设置成Black状态; for(O中每一个引用到的对象O1) { if(O1在White状态) { 将O1从White设置成Gray,并放到到Gray集合中; } } }

销毁垃圾对象:

[plain] view plain copy
  1. for(任意一个对象O){  
  2.     if(O在White状态)  
  3.         销毁对象O;  
  4.     else  
  5.         将O设置成White状态;  
  6. }  

在每个步骤之间,由于程序可以正常执行,所以会破坏当前对象之间的引用关系。black对象表示已经被扫描的对象,所以他应该不可能引用到一个white对象。当程序的改变使得一个black对象引用到一个white对象时,就会造成错误。解决这个问题的办法就是设置barrier。barrier在程序正常运行过程中,监控所有的引用改变。如果一个black对象需要引用一个white对象,存在两种处理办法:
  1. 将white对象设置成gray,并添加到gray列表中等待扫描。这样等于帮助整个GC的标识过程向前推进了一步。
  2. 将black对象该回成gray,并添加到gray列表中等待扫描。这样等于使整个GC的标识过程后退了一步。
这种垃圾回收方式被称为"Incremental Garbage Collection"(简称为"IGC",Lua所采用的就是这种方法。使用"IGC"并不是没有代价的。IGC所检测出来的垃圾对象集合比实际的集合要小,也就是说,有些在GC过程中变成垃圾的对象,有可能在本轮GC中检测不到。不过,这些残余的垃圾对象一定会在下一轮GC被检测出来,不会造成泄露。

GCObject

Lua使用union GCObject来表示所有的垃圾回收对象:

[cpp] view plain copy
  1. 182 /* 
  2. 183 ** Union of all collectable objects 
  3. 184 */  
  4. 185 union GCObject {  
  5. 186   GCheader gch;  /* common header */  
  6. 187   union TString ts;  
  7. 188   union Udata u;  
  8. 189   union Closure cl;  
  9. 190   struct Table h;  
  10. 191   struct Proto p;  
  11. 192   struct UpVal uv;  
  12. 193   struct lua_State th;  /* thread */  
  13. 194 };  

这就相当于在C++中,将所有的GC对象从GCheader派生,他们都共享GCheader。

[cpp] view plain copy
  1. 74 /* 
  2. 75 ** Common Header for all collectable objects (in macro form, to be 
  3. 76 ** included in other objects) 
  4. 77 */  
  5. 78 #define CommonHeader    GCObject *next; lu_byte tt; lu_byte marked  
  6. 79   
  7. 80   
  8. 81 /* 
  9. 82 ** Common header in struct form 
  10. 83 */  
  11. 84 typedef struct GCheader {  
  12. 85   CommonHeader;    
  13. 86 } GCheader;  

marked这个标志用来记录对象与GC相关的一些标志位。其中0和1位用来表示对象的white状态和垃圾状态。当垃圾回收的标识阶段结束后,剩下的white对象就是垃圾对象。由于lua并不是立即清除这些垃圾对象,而是一步步逐渐清除,所以这些对象还会在系统中存在一段时间。这就需要我们能够区分出同样为white状态的垃圾对象和非垃圾对象。Lua使用两个标志位来表示white,就是为了高效的解决这个问题。这个标志位会轮流被当作white状态标志,另一个表示垃圾状态。在global_State中保存着一个currentwhite,来表示当前是那个标志位用来标识white。每当GC标识阶段完成,系统会切换这个标志位,这样原来为white的所有对象不需要遍历就变成了垃圾对象,而真正的white对象则使用新的标志位标识。

第2个标志位用来表示black状态,而既非white也非black就是gray状态。

除了short string和open upvalue之外,所有的GCObject都通过next被串接到全局状态global_State中的allgc链表上。我们可以通过遍历allgc链表来访问系统中的所有GCObject。short string被字符串标单独管理。open upvalue会在被close时也连接到allgc上。

引用关系

垃圾回收过程通过对象之间的引用关系来标识对象。以下是lua对象之间在垃圾回收标识过程中需要遍历的引用关系:

所有字符串对象,无论是长串还是短串,都没有对其他对象的引用。

usedata对象会引用到一个metatable和一个env table。

Upval对象通过v引用一个TValue,再通过这个TValue间接引用一个对象。在open状态下,这个v指向stack上的一个TValue。在close状态下,v指向Upval自己的TValue。

Table对象会通过key,value引用到其他对象,并且如果数组部分有效,也会通过数组部分引用。并且,table会引用一个metatable对象。

Lua closure会引用到Proto对象,并且会通过upvalues数组引用到Upval对象。

C closure会通过upvalues数组引用到其他对象。这里的upvalue与lua closure的upvalue完全不是一个意思。

Proto对象会引用到一些编译期产生的名称,常量,以及内嵌于本Proto中的Proto对象。

Thread对象通过stack引用其他对象。

barrier

在《原理》中我们说过,incremental gc在mark阶段,为了保证“所有的black对象都不会引用white对象”这个不变性,需要使用barrier。

barrier被分为“向前”和“向后”两种。

luaC_barrier_函数用来实现“向前”的barrier。“向前”的意思就是当一个black对象需要引用一个white对象时,立即mark这个white对象。这样white对象就变为gray对象,等待下一步的扫描。这也就是帮助gc向前标识一步。luaC_barrier_函数被用在以下引用变化处:

  • 虚拟机执行过程中或者通过api修改close upvalue对其他对象的引用
  • 通过api设置userdata或table的metatable引用
  • 通过api设置userdata的env table引用
  • 编译构建proto对象过程中proto对象对其他编译产生对象的引用
luaC_barrierback_函数用来实现“向后”的barrier。“向后”的意思就是当一个black对象需要引用一个white对象时,将已经扫描过的black对象再次变为gray对象,等待重新扫描。这也就是将gc的mark后退一步。luaC_barrierback_目前只用于监控table的key和value对象引用的变化。Table是lua中最主要的数据结构,连全局变量都是被保存在一个table中,所以table的变化是比较频繁的,并且同一个引用可能被反复设置成不同的对象。对table的引用使用“向前”的barrier,逐个扫描每次引用变化的对象,会造成很多不必要的消耗。而使用“向后”的barrier就等于将table分成了“未变”和“已变”两种状态。只要一个table改变了一次,就将其变成gray,等待重新扫描。被变成gray的table在被重新扫描之前,无论引用再发生多少次变化也都无关紧要了。

引用关系变化最频繁的要数thread对象了。thread通过stack引用其他对象,而stack作为运行期栈,在一直不停地被修改。如果要监控这些引用变化,肯定会造成执行效率严重下降。所以lua并没有在所有的stack引用变化处加入barrier,而是直接假设stack就是变化的。所以thread对象就算被扫描完成,也不会被设置成black,而是再次设置成gray,等待再次扫描。

Upvalue

Upvalue对象在垃圾回收中的处理是比较特殊的。

对于open状态的upvalue,其v指向的是一个stack上的TValue,所以open upvalue与thread的关系非常紧密。引用到open upvalue的只可能是其从属的thread,以及lua closure。如果没有lua closure引用这个open upvalue,就算他一定被thread引用着,也已经没有实际的意义了,应该被回收掉。也就是说thread对open upvalue的引用完全是一个弱引用。所以Lua没有将open upvalue当作一个独立的可回收对象,而是将其清理工作交给从属的thread对象来完成。在mark过程中,open upvalue对象只使用white和gray两个状态,来代表是否被引用到。通过上面的引用关系可以看到,有可能引用open upvalue的对象只可能被lua closure引用到。所以一个gray的open upvalue就代表当前有lua closure正在引用他,而这个lua closure不一定在这个thread的stack上面。在清扫阶段,thread对象会遍历所有从属于自己的open upvalue。如果不是gray,就说明当前没有lua closure引用这个open upvalue了,可以被销毁。

当退出upvalue的语法域或者thread被销毁,open upvalue会被close。所有close upvalue与thread已经没有弱引用关系,会被转化为一个普通的可回收对象,和其他对象一样进行独立的垃圾回收。


GC步骤

global_State中的gcstate记录了当前incremental gc的执行状态。根据执行状态,整个gc过程被分为很多步执行。

GCSpause

GCSpause状态标志着当前没有开始gc。gc一旦开始,第一步要做的就是标识所有的root对象。root对象包括global_State引用的mainthread对象,registry table,全局的metatable和上次gc所产生的还没有进行finalize的垃圾对象。标识工作就是将white对象设置成gray,是通过函数reallymarkobject进行的。reallymarkobject会根据不同的对象作不同的处理。

对于string对象,本身没有对其它对象的引用,就可以立即设置成black,无需等待后面的遍历。对于userdata对象,只会引用到一个metatable和env,所以直接mark后也可以立即设置成black。对于upvalue对象,直接mark引用的对象。所有root对象会被设置成gray状态,等待下一步的propagate。第一步完成后,gc状态会切换成GCSpropagate。

GCSpropagate

这一步主要就是将所有gray对象变成black,并将其引用到的white对象变成gray,直到没有gray对象存在为止。
在GCSpropagate状态下,barrier会起作用。Lua并不监控所有的引用变化,否则会非常影响效率会。一些我们认为经常会发生变化的地方,比如stack的引用变化,就不用barrier。

barrier的位置
  • lapi.c moveto luaC_barrier
  • lapi.c lua_load luaC_barrier
  • lapi.c lua_setupvalue luaC_barrier
  • lcode.c addk luaC_barrier
  • lvm.c OP_SETUPVAL luaC_barrier
  • lapi.c lua_rawset lua_rawseti lua_rawsetp  luaC_barrierback
  • ltable.c luaH_newkey  luaC_barrierback
  • lvm.c luaV_settable luaC_barrierback
  • lvm.c OP_SETLIST luaC_barrierback
  • lapi.c lua_setmetatable luaC_objbarrier userdate->mt
  • lapi.c lua_setuservalue luaC_objbarrier
  • lapi.c lua_upvaluejoin luaC_objbarrier
  • ldo.c f_parser luaC_objbarrier initialize upvalue
  • lparser.c luaC_objbarrier
  • lapi.c lua_setmetatable luaC_objbarrierback

何时进行gc


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Lua 之面向对象编程发布时间:2022-07-22
下一篇:
利用 Lua 实现 App 动态化方案发布时间: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