[编程基础]luaGC简介

前言

在研究了一段时间的GC后,发现自己使用的两种语言,lua和c#的GC实现分别是两种高级GC算法,一个是增量式,一个是分代式。前者是标记清除,后者是标记压缩。

luaGC

在lua中,GC为标记清除增量式的,系统管理着所有已经创建了的对象,每个对象都有对其他对象的引用。root集合代表着已知的系统级别的对象引用。我们从root出发,就可以访问到系统引用到的所有对象。而没有被访问到的对象就是垃圾对象,需要被销毁。

三色垃圾回收

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

当前所有对象都是White状态;
将root集合引用到的对象从White设置成Gray,并放到Gray集合中;
while(Gray集合不为空)
{
    从Gray集合中移除一个对象0,并将0设置成Black状态;
    for(0中每一个引用的对象01){
        if(01在White状态){
            将01从White设置成Gray,并放到Gray集合中;
        }
    }
}
for(任意一个对象0){
    if(0在white状态)
        销毁对象0;
    else
        将0设置成White状态;
}

Increment Garbage Collection

上面的算法如果一次性执行,在对象很多的情况下,会执行很长时间,严重影响程序本身的响应速度。其中一个解决办法:把上面的算法分步执行,这样每个步骤所消耗的时间就比较小了。我们可以将上述的算法改为以下几个步骤。
首先标示所有root对象:
1. 当前所有对象都是White状态;
2. 将root集合引用到的对象从White设置成Gray,并且放在Gray集合中。
遍历访问所有gray对象。如果超出了本次计算量上限,退出等待下一次遍历:

while(Gray集合不为空,并且没有超出本次计算量的上限){
从Gray集合中移除一个对象0,并将0设置成Black状态;
for(0中每一个引用到的对象01){
if(01在White状态){
将01从White设置成Gray,并放到Gray集合中;
}
}
}

销毁垃圾对象:

for(任意一个对象0){
    if(0在White状态)
    销毁对象0;
    else
    将0设置成White状态;
}

在每个步骤之间,由于程序可以正常执行,所以会破坏当前对象之间的引用关系。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来表示所有的垃圾回收对象:

union GCObject{
    GCheader gch;
    union TString ts;
    union Udata u;
    union Closure cl;
    struct Table h;
    struct Proto p;
    struct UpValue uv;
    struct lua_state th;
}

#define CommonHeader GCObject *next;lu_byte tt;lu_byte marked

typedef struct GCheader {
    CommonHeader;
}GCheader;

marked这个标志用来记录对象与GC相关的一些标志位,其中0和1用来表示对象的white状态和垃圾状态。当垃圾回收的标识阶段结束后,剩下的white对象就是垃圾对象。由于lua并不是立即清除这些垃圾对象,而是一步一步逐渐清除,所以这些对象还会在系统中存在一段时间。这就需要我们能够区分同样为white状态的垃圾对象和非垃圾对象。lua使用两个标志位来表示white,就是为了高效的解决这个问题。这个标志位会轮流被当作white状态标志,另一个表示垃圾状态。在global_Static中保存着一个currentwhite,来表示当前是哪个标志位用来标识white。每当GC标识阶段完成,系统会切换这个标志位。这样原来为white的所有对象不需要遍历就会变成垃圾对象,而真正的white对象则使用新的标志位标识。
第二个标志位用来表示black状态,而既非white也非black也就是gray状态。
除了short string 和open upvalue之外,所有的GCObject都是通过next被串接到全局状态global_State中的allgc链表上。我们可以通过遍历allgc链表来访问系统中的所有GCObject,short string 被字符串标单独管理,open upvalue会在被close时也连接到allgc上。

引用关系

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

所有字符串对象,无论长串还是短串,都没有对其他对象的引用。
uesdata对象会引用到一个metatable和一个env table。
Upval对象通过v引用一个TValue,再通过这个TValue间接引用一个对象。在open状态下,这个v指向stack上的一个TValue。在close状态下,v指向Upval自己的TValue。
table对象会通过key,value引用到其他对象,并且如果数组部分有效,也会通过数组部分引用。并且table会引用一个metatable对象。
lua closure会引用到proto对象,并且会通过upvalue数组引用到Upval对象。
c closure会通过upvalues数组引用到其他对象,这里的upvalue与lua closure的upvalue完全不是一个意思。
Proto对象会引用到一些编译器产生的名称,常量,以及内嵌于本Proto中的Proto对象。
thread对象通过stack引用其他对象

barrier

在igc的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

对于lua5.0以后的版本支持userdata,它是可以带有__gc方法,当userdata被回收时会调用这个方法。所以一遍标记是不够的。不能简单的把变成垃圾的userdata简单剔除,那样就无法正确的调用__gc了。所以标记流程需要分两个阶段做。第一阶段把包括userdata在内的死亡对象剔除出去。然后在死对象中找回有__GC方法的,对它们再做一次标记复活相关的对象,这样才能保证userdata的__gc可以正确运行。执行完__gc的userdata最终会在下一轮gc中释放(如果没有在__gc中复活)。userdata有一个单向标记,标记__gc方法是否有运行过,这可以确保userdata的__gc只会执行一次,即使在__gc中复活(重新被root集合引用),也不会再次分离出来反复运行finalizer。也就是说,运行过finalizer的userdata就永久变成了一个没有finalizer的userdata了。

[编程基础]GC高级算法

在讨论完三大基础算法以后,我们现在来看看这基础算法的结合以后做成的高级算法。其中最具有代表性的就是:分代回收,增量回收,和并行回收,这三种。

1:分代回收

首先,我们来聊聊高级GC算法中最重要也是最常用的一种,即分代回收。由于GC和程序处理的本质是无关的,因此它所消耗的时间越短越好。分代回收的目的,正是为了在程序运行期间,将GC所消耗的时间尽量缩短。分代回收的基本思路,是利用来一般程序所具备的性质,即大部分对象都会在短时间内成为垃圾,而进过一定时间依然存活的对象往往拥有较长的寿命。如果寿命长的对象更容易存活下来,寿命短的对象则会被很快遗弃,那么如果对分配不久,诞生时间较短的“年轻”对象进行重点扫描,应该可以更有效的回收大部分垃圾。

在分代回收中,对象按照生成时间进行分代,刚诞生不久的年轻对象划分为新生代,而存活来较长时间的对象划分为老生代。根据具体实现方式的不同,可能还会划分更多的代。如果上述关于对象寿命的假说成立的话,那么只要对新生代对象进行扫描,就可以回收遗弃对象中很大一部分。像这种只扫描新生代对象的回收操作,被成为小回收。小回收中在扫描的时候如果遇到属于老生代的对象时,就不会对这个对象进行递归扫描了。这样一来,需要扫描的对象数量也会减少。然后把回收一次以后残留的对象划分到老生代中。

分代回收

上图中,任何地方都没有再被引用的对象F将会通过大回收进行回收。

上图(1)中的D被老生代E所引用,如果根据我们上面所有,如果在回收标记的时候,不对老生代中的对象进行递归引用标记操作的话,那D将不被任何对象引用,那将在一次GC中被回收掉。那这样的话,就就出现我们不期望的结果。所以我们需要做一次操作来,实现老生代对新生代的引用,这个操作一个记录,就是上图中的记录集,这个记录集就是对老生代对新生代引用变更的一个记录。在做小回收的时候,这个引用集将作为一个根来对待。

要让分代回收正确的工作,必须使记录集的内容保持更新。因此,在老生代到新生代的引用产生的瞬间,就必须对该引用进行记录,而负责执行这个操作的子程序,需要被嵌入到所有涉及对象更新操作的地方。这种检查程序需要对所有涉及修改对象内容的地方进行保护,因此被成为写屏障。

随着程序的不断运行,老生代区域中的“死亡”对象也在不断增加。为了避免这些“死亡”对象对内存的白白占用,所以需要有时候对所有的区域都进行一次扫描回收,这个操作叫做大回收或者完全回收。分代回收通过减少GC中扫描对象数量,达到减少GC带来平均中断时间的效果。不过由于还是要经历大回收的,所有最大中断时间并没有得到什么改善。

2:增量回收

在对实时性要求很高的程序中,比起缩短GC的平均中断时间,往往更重视缩短GC的最大中断时间。在这些实时性要求很高的程序中,必须能够对GC所产生的中断时间做出预测。在一般的GC算法中,做出这样的保证是不可能的,因为GC产生的中断时间与对象的数量和状态有关。因此,为了维持程序的实时性,不等到GC全部完成,而是将GC划分多个部分逐一执行。这种方式就叫做增量回收。在增量回收中,由于GC的过程是渐进的,在回收过程中程序本身也会继续运行,对象之间的引用关系也可能会发生变化。如果已经完成扫描和标记的对象被修改,对新的对象产生引用,这个新对象就不会被标记,这样明明还被引用的却会被回收。所以在增量回收中也采用了写屏障。当已经被标记的对象的引用发生变化时,通过写屏障会将新被引用的对象作为扫描的起点记录下来。由于增量回收的过程是分布渐进式的,可以将中断时间控制在一定长度之内。另一方面,由于中断操作需要消耗一定的时间,GC消耗的总时间会相应的增加。

3:并行回收

在现在的计算机中,一块芯片搭载多个cpu核心的多核处理器已经是一个司空见惯的东西了。那么在这种环境下,就需要利用多线程来充分发挥多CPU的性能,并行回收正是通过最大限度利用多CPU的处理能力来进行GC操作的一种方式。并行回收的基本原理是:是在原有的程序运行的同时进行GC操作,这一点和增量回收是相似的。因此也会遇到增量回收相同的问题。为了解决这个问题也需要写屏障来对当前的状态信息保持更新。

[编程基础]GC基础算法

基本术语

1.垃圾(Garbage)

就是需要被回收的对象

如果程序可能会直接或者间接地引用一个对象,那么这个对象就被视为“存活”,与之相反的,没有被引用到的就被视为“死亡”。将这些“死亡”对象找出来,然后作为垃圾进行回收,这就是GC的本质。

2.根(root)

就是判断对象是否可被引用的起始点。

至于哪里才是根,不同语言,不同编辑器都有不同的规定,但基本上是将变量和运行栈作为根。

三大基础GC算法

1.标记清除法/标记压缩法

标记清除是最早开发出的GC算法。原理非常简单,首先从根开始将可能被引用的对象用递归的方式进行标记,然后将没有标记到的对象作为垃圾进行回收。

标记清除算法

图中显示了标记清除算法的大致原理,1阶段显示了随着程序运行而分配出一些对象的状态,一个对象对其他的对象引用。2阶段开始执行GC操作,从根开始对可能被引用的对象打上“标记”,大多数情况下,这种标记通过对象内部的标志(flag)来实现。3阶段,被标记的对象所引用的对象也打上标记,一直重复这样的操作,就可以把从根开始可能被间接引用到的对象都打上标记。此阶段为标记阶段。

标记阶段完成时,被标记的对象就被视为“存活”对象,4阶段把所有对象都扫描一遍,将没有被标记的对象进行回收,这一阶段为清除阶段。

在扫描的同时,还需要将存活的标记状态清理掉,以便下一次GC操作做好准备,标记清除的消耗时间和存活对象数与对象总数的总和相关。

标记压缩算法,是标记清除算法的变形,他不是将没被标记的对象清除,而是不断压缩。

2:复制收集算法

标记清除算法有一个很大的问题,在分配大量对象的时候,当存活很少一部分的时候,还是需要对全部对象进行一次扫描,就算是不能在用的也要进行扫描,所需要用到的时间大大超过必要值。复制收集算法则试图克服这一问题,在复制收集算法里,会从根结点开始把被引用和间接引用的对象复制到另外一个空间,然后把原空间给回收。

复制收集

(1)为开始GC时候的内存状态,(2)在原对象空间以外再开辟了一个空间,然后把根引用到的对象(A)给复制过去,(3)把A所引用的对象也给复制过去,递归向下,把所有被根间接引用的对象都复制到新的空间内,而“死亡”对象就还留在旧空间内。(4)回收旧的对象空间,使用新的对象空间。这样就把所有的死亡对象都给释放掉了,留下的还存活的对象。

复制收集对比标记清除中,只有一开始标记的时候是需要递归遍历的,后面标记清除中的扫描所有的对象进行清除这步是不需要的。所有减少了不必要的扫描开销。

但是复制对象的内存开销会比较大,如果存活的对象比较多的情况下,这种算法就十分消耗内存。

还有一个好处就是,关系比较近的对象,可能会放在距离较近的内存空间,可以提高程序运行性能。

3:引用计数法

引用计数方式是GC算法中最简单,也是最容易实现的一种。它的原理:在每个对象中保存该对象的引用计数,当引用发生增减的时候对引用计数进行更新。当引用计数为0的时候,该对象将不被引用,因此可以释放相应的内存空间。

引用计数

图中(1)部分中,记录着所有对象都保存着自己被多少个其他对象进行引用的数量。(2)中对象引用发生变化时,引用计数也跟着变化。当引用b到d的引用失效,d的引用就为0,将被回收,所以d所引用对象的引用计数也将相应的减少。(3)中对所有引用计数为0的对象进行释放。在这个GC过程中,不需要对所有的对象进行扫描。

在这个GC算法中当对象不被引用的瞬间就会被释放。在其他GC算法中,要预测对象是否能被释放是一个很困难的事,但是在引用计数中,当为0就能被释放了。而且这个释放操作是针对每个对象个别执行的,因此对比其他GC算法,中断时间也比较短。

引用计数最大的缺点就是,不能释放被循化引用的对象

如上图所示,三个对象没有被其他对象所引用,但是相互之间循环引用了。因此它们永远都不会被释放,

还有一个问题就是,必须在引用计数发生变化的时候做出正确的增减,如果出现问题,就会出现内存错误,少加了就会释放过早,多加了就会出现内存泄漏。

最后一个缺点,引用计数管理不适合并行处理,如果多个线程同时对引用计数进行更新,引用计数可能会产生不一致的问题。为了避免这种情况的发生,对引用计数的操作必须采用独占的方式来进行。如果引用操作频繁发生,每次都要使用加锁等并发控制机制的话,其开销也是不可小觑的