lua gc算法(2)

三色标记法

在前面的双色标记法中，我们可以看到一个对象可以分为白色和黑色。现在引入一个灰色的概念，标记那些已经被扫描到但是所引用的对象没有被扫描完的对象。

三色法分为两步，
新创建的对象标记为白色，并加入白色集合
#第一步为标记阶段
移动root节点引用的对象到灰色集合
当灰色集合不为空，
  选取一个灰色节点，标记为黑色，从灰色集合移动到黑色集合
  遍历这个节点所引用的白色节点，从白色集合移动到灰色集合

#第二阶段为清除阶段
剩下的白色节点为可以清理的节点
#算法中节点只能从白色移动到灰色，在从灰色移动到黑色。

白色，黄色以及蓝色分别代表了gc中的白色，灰色以及黑色, 步骤1.所有节点都是在白色集合 步骤2.A,F移动到灰色集合 步骤3.A,F移动到黑色结合；B,C,D移动到灰色集合 步骤4.B,C,D移动到黑色结合 步骤5.清除白色集合里的节点

标记阶段不变量

1.root集合都是灰色或者黑色
2.黑色节点不能引用白色节点
3.灰色节点定义为介于黑色和白色的节点
4.标记阶段的过程就是通过遍历灰色集合然后把他们变成黑色
5.灰色集合为空的时候标记阶段就结束了。

增量式垃圾收集器，标记阶段往往运行用户程序的时候，往往会引入新的对象。所以新对象的处理就是个麻烦，会打破不变量，所以引入屏障来恢复不变量。

屏障

站在垃圾收集器的角度，运行的程序就是个麻烦，因为在收集过程中，会不断破坏不变量“黑色节点不能引用白色节点”，比如t.x = {}，t已经被标记成黑色了，这个时候重新让他引用白色的x。
有两种方法来处理这种情况。
1.递进的方式，让新创建的白色节点直接变成灰色。
2.后退的方式，让黑色节点重新退回为灰色。
为了避免ping-pong，所以把黑色节点不是加入“灰色集合”而是加入“在次灰色集合”。这个灰色集合的遍历会以原子操作的方式进行。
还有栈永远设置成灰色，避免屏障操作当有变量写入栈上时。
不论的后退的方式还是栈永远设置成灰色都是处于性能的考虑，避免ping-pong.对于会经常增加引用的节点设置灰色后，不要在设置黑色是最好的选择，因为如果变成黑色了，很快又变成灰色了。

• 后退的例子，把表从黑色集合移动到“在次灰色集合”
  for i=1,N do a[i] = <exp> end
• 前进的例子,把元表从“白色集合“移动到“灰色结合”
  setmetatable(obj,mt)

Atomic步骤

• 标记阶段的结束都会调用atomic step。
• 这一步遍历“再次灰色集合”和栈
• 清理弱表
• 区分开了需要会被回收的集合，需要重新复活的集合。

#三色法增量式gc
移动root节点引用的对象到灰色集合
goto:标记过程

标记过程: 
  while 灰色节点集合不为空
    获取灰色集合的节点
    添加节点到黑色集合
    获取节点的相邻节点集合,添加到灰色集合
    if 某个条件(比如标记字节数够了)
      goto:程序逻辑

goto:原子步骤(灰色集合为空了)

程序逻辑：
  if 产生新节点
     goto:写屏障
  运行其他逻辑
  
写屏障：
   if 节点被表引用
      表退回到再次灰色集合
   节点加入灰色集合

原子步骤:
  遍历“再次灰色集合”（为了标记）
  goto:清理

清理：
  清理白色集合里内容