深入理解屏障技术

数据小冰

发布于 2022-08-15 14:46:13

8150

发布于 2022-08-15 14:46:13

什么是垃圾回收

本文中的“垃圾”是指计算机中一段内存空间，我们知道CPU、内存和硬盘等是程序运行所需要的资源，这些资源是有限的。程序中对象的分配需要分配内存，这里的内存是实打实的物理内存，对机器来说，内存是有限的，当这片内存分配给A程序之后，就不能分配给B程序了（共享内存除外），所以当分配的对象不再使用时，要尽早释放掉占用的物理内存，进行回收利用。所以垃圾回收（GC)就是回收不在使用的物理内存，并且我们通常所说的垃圾回收是指自动垃圾回收（Automatic Garbage Collection).

垃圾回收的范围

程序中使用到的内存分为两种，分为堆内存和栈内存。垃圾回收的是堆内存，不含栈内存。函数的调用和返回，函数及局部变量占用的内存会自动释放。也就是说栈中的数据可以通过简单的编译器指令自动清理，所以不需要专门进行垃圾回收。

为什么要垃圾回收

在什么是垃圾回收中也说了进行垃圾回收的目的是对内存进行重复使用。这里着重强调自动垃圾回收，有自动回收相应的也有手动回收。早期的语言是没有自动垃圾回收的，例如C语言，释放内存需手动使用free来进行，一旦忘记释放，就到导致内存泄露。所以内存泄露bug在c语言中是一个非常普遍的问题，虽然有valgrind工具来检测泄露，但工具也不是100%的能检测出来。带有自动垃圾回收的语言很受程序员欢迎，像Java、Golang语言，语言自带垃圾回收，不用在花很多精力在内存释放上面，大大降低了开发的心智负担，提升了开发效率。所以总结起来，带有自动垃圾回收的语言能够减轻开发的心智负担，提升开发的效率，减少手动管理内存存在泄漏的bug。

垃圾回收算法

主流的垃圾回收算法有两种，分别是追踪式垃圾回收算法和引用计数法（ Reference counting ）。追踪式垃圾回收算法一般有标记和清除两个阶段，所以标记-清除（Mark-Sweep)算法也代指的是追踪式垃圾回收算法。

标记-清除算法

标记-清除算法由标记阶段和清除阶段构成，标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就可以令不能利用的内存空间重新得到利用。

那应该标记哪些对象呢？其核心思想是判断一个对象是否可达，因为一旦某个对象不可达就可以立刻被GC回收。如何判断一个对象是否可达，第一步找出所有的全局变量和当前函数栈中的变量，将其标记为可达；第二步，从已经标记的数据开始，进一步标记它们可访问的变量，依次类推，知道没有可标记的对象为止，则剩下未标记的对象即为不可达对象。然后将不可达的对象清理掉。

引用计数算法

顾名思义，就是对对象的引用情况进行计数，通过记录每个对象被引用的次数，来确定这个对象是否可以被回收。创建对象的时候，对这个新的对象的引用数为1，更新指针的时候例如将A对象的指针重新指向B对象，则A对象的引用数量-1，B对象引用数量+1.

Go垃圾回收算法

Go垃圾回收算法采用的是标记-清除法，从语言诞生以来经过了一系列优化，下面按时间维度做一个说明。

Go1.3之前的标记-清除算法

整个过程分为两个步骤:标记（Mark)和清除(Sweep).在执行标记清除工作前，需要STW（stop the world），即暂停应用程序的运行，对外表现是应用程序卡顿。然后找出可达的对象，做上标记。最后回收未标记的对象，即不可达的对象。

如上图所示，进程中有对象1到对象5一共5个对象，目前从进程的全局变量或栈上可达的对象有对象1、对象2、对象3这三个对象，对象4和对象5不可达。对上面进程的对象进行标记，找出所有可达的对象，对其进行标注，这里填充为黑色方便区分。标记完之后，得到的对象状态图如下图所示。

最后进行清理(sweep)操作，将标注之后不可达(未标颜色的）对象清除，得到对象状态图如下所示。

整个标记-清除阶段完成之后，也就是一轮GC介绍，然后start the world，即恢复应用程序的执行。

可以看到，STW范围涵盖标记和清除全部阶段，这个期间应用程序都是卡住的，整个过程的耗时大约在百毫秒-秒数量级，这对应用程序的影响还是挺大的。

这里补充一下在Go1.0和Go1.1版本GC的演进情况：

Go1.0是完全串行的标记和清除，就是上图所示的过程，在GC的整个过程中应用程序是暂停的。
Go1.1在多核主机上实现了并行执行垃圾回收的标记和清除

Go1.3优化后的标记-清除算法

Go1.3版本在前面的版本上做了简单的优化，具体来说有两点：

将停止STW提到了清除(Sweep)前面
实现了真正精确的垃圾收集，运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持

因为在标记(mark)之后，哪些对象是存活的，哪些被清除(sweep)是已知的，sweep的是不再被引用的对象，sweep结束前，这些对象不会再被分配到，所以sweep和用户程序并发运行没有问题。无论全局还是栈不可能能访问的到这些对象，可以安全清理。

Go1.5三色并发标记垃圾回收

在Go1.5版本中，使用了三色标记算法。标记和清扫都并发执行的，但标记阶段的前后需要 STW 一定时间来做 GC 的准备工作和栈的re-scan。下面介绍三色标记的具体做法。

初始时将所有的内存对象都标记为白色，将所有对象加入白色集合中。

2. 从根节点开始遍历所有对象，把遍历到的对象从白色集合放入灰色集合

遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合

4. 重复步骤3，直到灰色集合中无任何对象

5. 回收白色集合中的所有对象

三色标记过程中需不需要STW

三色标记的过程中需不需要STW呢？答案是需要。通过反证法，只要能找到一个不STW会导致的反例

因为没有进行STW，也就说下面的代码会和进行垃圾回收的程序并发运行，我们假设进行GC回收的时候，triColor的代码执行到object1.a=new(A)了。此时三色标记的状态图如下所示：

func triColor(){
 object2:=new(B)
 object1:=new(B)
 object1.a=new(A)
 
 object2.a=object1.a
 object1.a=nil
}

GC开始执行三色标记，将根对象object1和object2加入到灰色集合

2. 将object2加入到黑色集合，因为它没有引用其他对象，所以不存在将它的引用的子对象加入灰色集合

3. 这时用户程序执行object2.a=object1.a和object1.a=nil，因为没有STW,用户程序和GC程序是并发执行的，得到状态图如下

4. 这时GC对Object1进行标记，将其标记为黑色，加入到黑色集合，因为前面已执行object1.a=nil了，所以它也没有子对象了，得到状态图如下

5. 执行清除操作，将白色对象清理掉

但这与实际不符啊！！！，newA怎么被清理了，它还在被object2引用，它是不能被清理的。这不正确，一个被正常引用的对象被无辜清理掉了。为啥会这样呢？就是因为用户程序和GC程序并发执行，导致在回收的过程中引用会发生变化，使得GC回收对象不正确了，所以「执行三色标记的时候不执行STW是不可以的」。

写屏障（Write Barrier）

前一小节说了，三色并发标记是需要STW的，因为不暂停用户程序逻辑改变对象的引用关系，会导致不正确的标记，引发GC回收错误。为了防止错误回收的产生，最简单的方式是STW。但是STW的过程对用户程序有很大的影响，那怎么保证对象不丢失的情况下合理的尽可能的提高GC效率，减少STW时间呢？我们需要达成以下两种三色不变性中的任意一种：

强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象。
弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。

结合前面的例子，可以看到，一个白色对象被黑色对象引用，是注定无法通过这个黑色对象来保证自身存活的。于此同时，如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏，那么这个白色对象必然会被视为垃圾清除掉。所以当上面两个条件同时满足时，就会出现对象丢失的问题。如果这个白色对象还引用了其他对象，并且这条路径是指向下游对象的唯一路径，那它们一定会被清理掉。

为了更通俗的理解三色标记，可以将颜色分一个等级关系:黑色>灰色>白色，对象的引用关系要符合颜色等级的顺序，就是黑色不能直接引用白色。黑色可以黑色，黑色可以到灰色。

现在我们再回头看三色不变形是如何破坏黑色直接引用白色对象关系的。

先来看强三色不变性，黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象，根据定义，就是黑色不能指向白色，具体做法是遇到黑色指向白色的对象，强行将白色对象改为灰色对象。这种做法看起比较暴力，不过能保证对象不会误清理，虽然可能会导致一个真正被清理的对象标记为灰色，接着会标记为黑色，出现本次清理不会被清理掉，会将一个本应该本次被清理的对象留到了下一轮GC.

在来看弱三色不变性，黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。虽然有黑色对象执行白色对象，但是这个白色对象迟早会被标记为灰色对象，最后会被标记为黑色对象。因为还存在可达白色对象的灰色对象，随着这个灰色对象以及可达路径上对象不断的被标记，这个白色对象最终会染色成黑色。所以，白色对象不会被清理掉。

Go垃圾回收中通过“插入屏障”和“删除屏障”的方式，实现了上述三色不变形，放在对象被误回收。

「插入屏障」：插入屏障拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色，这样就不存在黑色对象引用了白色对象的情况，满足了强三色不变性。插入屏障的伪代码如下

writePointer(slot,ptr):
 shade(ptr)
 *slot = ptr

slot指当前下游对象，ptr是新下游对象，直接将新下游对象ptr标记为灰色，让将新下游对象ptr赋值给当前下游对象slot.假设当前对象为CA,则 CA.writePointer(nil,B) 表示CA之前没有下游对象，新添加一个下游对象B，并且将B标记为灰色。CA.writePointer(C,B)表示将当前对象CA的下游对象C更换为B，并将B标记为灰色。

程序跑起来，大部分的其实都是操作在栈上，函数参数啊、函数调用导致的压栈出栈、局部变量啊，协程栈，如果对栈上的写做拦截，将会导致流程代码非常复杂，并且性能下降会非常大，得不偿失。所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中。

下面通过一组图来说明插入屏障的工作流程

初始栈和堆上对象关系如下图

2. 根对象标记为灰色，加入灰色集合

3. 将灰色对象引用的对象加入灰色集合并标记为灰色，将父灰色对象标记为黑色，加入黑色集合

4. 用户程序给对象3添加引用对象6，给对象1添加引用对象7

5. 因为对象3在堆上，有写屏障，会强行将对象6标记为灰色，加入灰色集合，对象7在栈上，没有写屏障，继续为白色

6. 然后对象2和对象6的引用对象加入灰色集合，它们没有引用对象，所以跳过，并将它们标记会黑色，加入黑色集合

7. 前面已经标记完所有灰色对象，栈上对象引用关系有变化，需要重新标记，在标记前，需要启动STW

8. 对栈上的对象进行重新三色标记，标记完之后，对象7会被标记为黑色，并被加入到黑色集合中

9. 栈上对象重新标记完，停止STW

10. 将白色对象清理掉

「删除屏障」：删除屏障也是拦截写操作的，但是是通过保护灰色对象到白色对象的路径不会断来实现的，满足了弱三色不变性。下面举例说明

初始对象状态如下图所示，对象1引用对象2，对象2引用对象3

GC开始将对象1标记灰色，并将其加入到灰色集合

用户程序删除指针p1,触发删除屏障，所以对象2被标记为灰色对象，并将它加入灰色对象集合

GC程序继续进行三色标记，最终对象1、对象2和对象3都被标记为黑色

「对象2和对象3已经是垃圾了」，但是他们被标记为黑色，也就是本轮CG不会回收。所以说删除屏障的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮 GC 中被清理掉

混合写屏障(hybrid write barrier)

Go1.8版本引入了混合写屏障机制，避免了对栈的重新扫描，大大减少了STW的时间。混合写屏障=插入屏障+删除屏障，它是变形的弱三色不变性，结合了两者的优点。插入写屏障在标记开始时无需STW，可直接开始，并发进行，但结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；删除写屏障则需要在GC开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需STW。

在详细分析混合写屏障之前，我们先从用户程序(mutator)的角度对指针的操作进行一个分类。写业务接口的俗称curd boy😁，一个接口一般有curd，分别对应的是c(create)创建、u(update)更新、r(read)查看、d(delete)删除操作。对应到指针来说，我们关心cud操作,也就是新增对象、删掉对象、修改对象。如下表所示。