侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论
Go

Golang三色标记探究

林贤钦
2022-04-19 / 0 评论 / 1 点赞 / 449 阅读 / 3,571 字
温馨提示:
本文最后更新于 2022-04-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Golang三色标记

垃圾回收(Garbage Collection, 简称GC)是编程语言中提供的自动内存管理机制,自动释放不需要的对象,让出存储器资源,无需程序员动手。

Golang中的垃圾回收主要应用三色标记法,GC过程和其他用户的goroutine可并行运行,但需要一定时间的STW(stop the world),STW的过程中,CPU不执行用户代码,全部用于垃圾回收,这个过程的影响很大,Golang进行多次的迭代优化这个问题。

一、Go V1.5的三色并发标记法

三色标记法,实际上就是通过一定的步骤,将对象分为白色,黑色,灰色的过程,最后将白色的对象进行回收。

第一步,只要新创建的对象,颜色都默认标记为 “白色“。

5、Golang三色标记+混合写屏障GC模式全分析 - 图7

所谓的“程序”,就是一些对象和根节点的集合

5、Golang三色标记+混合写屏障GC模式全分析 - 图8

第二步,每次GC回收开始,然后从根节点开始遍历所有对象,把所有的对象从白色集合放入“灰色”集合 。

5、Golang三色标记+混合写屏障GC模式全分析 - 图9

第三步,遍历灰色集合,将灰色对象引用的白色对象从白色集合放入灰色集合,之后把灰色对象放入黑色集合。

5、Golang三色标记+混合写屏障GC模式全分析 - 图10

第四步,重复第三步,直到灰色中无任何对象。

5、Golang三色标记+混合写屏障GC模式全分析 - 图12

第五步,回收所有的白色集合中的对象,也就是垃圾回收。

5、Golang三色标记+混合写屏障GC模式全分析 - 图13

二、没有STW的三色标记法

我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改,会影响标记结果的正确性。我们举一个场景.

如果三色标记法, 标记过程不使用STW将会发生什么事情?

5、Golang三色标记+混合写屏障GC模式全分析 - 图14

5、Golang三色标记+混合写屏障GC模式全分析 - 图15

5、Golang三色标记+混合写屏障GC模式全分析 - 图16

5、Golang三色标记+混合写屏障GC模式全分析 - 图17

5、Golang三色标记+混合写屏障GC模式全分析 - 图18

可以看出,有两个问题, 在三色标记法中,是不希望被发生的

  • 条件1: 一个白色对象被黑色对象引用**(白色被挂在黑色下)**
  • 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)**

当以上两个条件同时满足时, 就会出现对象丢失现象! 如果上述中的白色对象3, 如果他还有很多下游对象的话, 也会一并都清理掉.

为了防止这种现象的发生,最简单的方式就是STW,直接禁止掉其他用户程序对对象引用关系的干扰,但是STW的过程有明显的资源浪费,对所有的用户程序都有很大影响,如何能在保证对象不丢失的情况下合理的尽可能的提高GC效率,减少STW时间呢?

我们需要一个机制,来破坏上面的两个条件可以满足了

三、屏障机制

我们让GC回收器,满足下面两种情况之一时,可保对象不丢失. 所以引出两种方式:“强·弱” 三色不变式

3.1、“强·弱” 三色不变式

  • 强三色不变式

    不存在黑色对象引用到白色对象的指针。

    5、Golang三色标记+混合写屏障GC模式全分析 - 图19

  • 弱三色不变式

    所有被黑色对象引用的白色对象都处于灰色保护状态.

5、Golang三色标记+混合写屏障GC模式全分析 - 图20

弱三色不变式满足条件1黑色对象引用白色对象,如果灰色对象断开白色对象的引用,将满足条件2,就会造成对象丢失

为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式“插入屏障(强三色不变式)”, “删除屏障(弱三色不变式)”.

3.2、插入屏障

具体操作: 在黑色对象A新引用对象B的时候,对象B被标记为灰色。(将B挂在A下游,B必须被标记为灰色)

满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了, 因为白色会强制变成灰色)

伪码如下:

添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //1
  标记灰色(新下游对象ptr)   
  //2
  当前下游对象slot = 新下游对象ptr                    
}

场景:

A.添加下游对象(nil, B)   //A 之前没有下游, 新添加一个下游对象B, B被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象C 更换为B,  B被标记为灰色

这段伪码逻辑就是写屏障,黑色对象的内存槽有两种位置,栈堆。栈空间的特点是容量小,但要求相应速度快,因为函数调用弹出频繁使用,所以”插入屏障“机制,在栈空间的对象操作中不使用,仅仅使用在堆空间对象的操作中。

因为插入屏障机制不在栈空间使用,所以需要STW来保证不存在白色对象挂在黑色对象之下,导致白色对象丢失。

接下来,我们用几张图,来模拟整个一个详细的过程

5、Golang三色标记+混合写屏障GC模式全分析 - 图21

5、Golang三色标记+混合写屏障GC模式全分析 - 图22

5、Golang三色标记+混合写屏障GC模式全分析 - 图23

5、Golang三色标记+混合写屏障GC模式全分析 - 图24

5、Golang三色标记+混合写屏障GC模式全分析 - 图26

但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况(如上图的对象9)。所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失,要对本次标记扫描启动STW暂停。 直到栈空间的三色标记结束.

STW保证重新扫描栈空间,保证所有栈对象被扫描到。

5、Golang三色标记+混合写屏障GC模式全分析 - 图27

5、Golang三色标记+混合写屏障GC模式全分析 - 图28

5、Golang三色标记+混合写屏障GC模式全分析 - 图29

5、Golang三色标记+混合写屏障GC模式全分析 - 图30

最后将栈和堆空间 扫描剩余的全部 白色节点清除. 这次STW大约的时间在10~100ms间.

3.3、删除屏障

具体操作: 被删除的对象,如果自身为灰色或者白色,那么被标记为灰色。

满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)

伪代码:

添加下游对象(当前下游对象slot, 新下游对象ptr) {
  //1
  if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {
          标记灰色(当前下游对象slot)     //slot为被删除对象, 标记为灰色
  }
  //2
  当前下游对象slot = 新下游对象ptr
}

场景:

A.添加下游对象(B, nil)   //A对象,删除B对象的引用。  B被A删除,被标记为灰(如果B之前为白)
A.添加下游对象(B, C)     //A对象,更换下游B变成C。   B被A删除,被标记为灰(如果B之前为白)

接下来,我们用几张图,来模拟整个一个详细的过程。

5、Golang三色标记+混合写屏障GC模式全分析 - 图31

5、Golang三色标记+混合写屏障GC模式全分析 - 图32

5、Golang三色标记+混合写屏障GC模式全分析 - 图33

5、Golang三色标记+混合写屏障GC模式全分析 - 图34

5、Golang三色标记+混合写屏障GC模式全分析 - 图35

5、Golang三色标记+混合写屏障GC模式全分析 - 图36

5、Golang三色标记+混合写屏障GC模式全分析 - 图37

这种方式的回收精度低,一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮,在下一轮GC中被清理掉。但是删除屏障可以保证条件2灰色对象与它之间的可达关系的白色对象遭到破坏这种情况不会被出现。

四、Go V1.8的混合写屏障(hybrid write barrier)机制

插入写屏障和删除写屏障的短板:

  • 插入写屏障:结束时需要STW来重新扫描栈,标记栈上引用的白色对象的存活;
  • 删除写屏障:回收精度低,GC开始时STW扫描堆栈来记录初始快照,这个过程会保护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制(hybrid write barrier),避免了对栈re-scan的过程,极大的减少了STW的时间。结合了两者的优点。

4.1、混合写屏障规则

具体操作:

  1. GC开始将栈上的根对象及引用下的所有对象全部扫描并标记为黑色(之后不再进行第二次重复扫描,无需STW)。
  2. GC期间,任何在上创建的新对象,均为黑色。
  3. 被删除的对象标记为灰色。
  4. 堆中被添加的对象标记为灰色。

满足: 变形的弱三色不变式

伪代码:

添加下游对象(当前下游对象slot, 新下游对象ptr) {
      //1 
        标记灰色(当前下游对象slot)    //只要当前下游对象被移走,就标记灰色
      //2 
      标记灰色(新下游对象ptr)
      //3
      当前下游对象slot = 新下游对象ptr
}

这里我们注意, 屏障技术是不在栈上应用的,因为要保证栈的运行效率。

4.2、混合写屏障的具体场景分析

接下来,我们用几张图,来模拟整个一个详细的过程。

注意混合写屏障是Gc的一种屏障机制,所以只是当程序执行GC的时候,才会触发这种机制。

5、Golang三色标记+混合写屏障GC模式全分析 - 图38

5、Golang三色标记+混合写屏障GC模式全分析 - 图39

场景一: 对象被一个堆对象删除引用,成为栈对象的下游

//前提:
堆对象4->对象7 = 对象7;    //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7;  //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null;    //对象4 删除引用 对象7

被删除的对象标记为灰,添加对象栈黑堆灰,所以对象7变成灰色

5、Golang三色标记+混合写屏障GC模式全分析 - 图40

5、Golang三色标记+混合写屏障GC模式全分析 - 图41

场景二: 对象被一个栈对象删除引用,成为另一个栈对象的下游

new 栈对象9;
对象8->对象3 = 对象3;      //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null;      //对象2 删除引用 对象3

新添加对象,栈黑堆灰,所以对象3是黑色

5、Golang三色标记+混合写屏障GC模式全分析 - 图42

5、Golang三色标记+混合写屏障GC模式全分析 - 图43

5、Golang三色标记+混合写屏障GC模式全分析 - 图44

场景三:对象被一个堆对象删除引用,成为另一个堆对象的下游

堆对象10->对象7 = 堆对象7;       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null;         //对象4 删除引用 对象7

删除的对象是灰色,添加的对象,栈黑堆灰,所以对象7是灰色

5、Golang三色标记+混合写屏障GC模式全分析 - 图45

5、Golang三色标记+混合写屏障GC模式全分析 - 图46

场景四:对象从一个栈对象删除引用,成为另一个堆对象的下游

堆对象10->对象7 = 堆对象7;       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null;         //对象4 删除引用 对象7

5、Golang三色标记+混合写屏障GC模式全分析 - 图48

5、Golang三色标记+混合写屏障GC模式全分析 - 图49

5、Golang三色标记+混合写屏障GC模式全分析 - 图50

Golang中的混合写屏障满足弱三色不变式,结合了删除写屏障和插入写屏障的优点,只需要在开始时并发扫描各个goroutine的栈,使其变黑并一直保持,这个过程不需要STW,而标记结束后,因为栈在扫描后始终是黑色的,也无需再进行re-scan操作了,减少了STW的时间。

五、总结

  1. 三色标记法,通过可达性算法,标记出黑色、灰色、白色对象,最后只有黑色和白色对象,将白色的对象进行回收
  2. Go V1.5通过插入屏障和删除屏障来保障对象不被误删,但由于栈空间使用频繁,栈空间不启用插入屏障,所以需要STW来保障,对象不被误删,效率比较普通
  3. Go V1.8通过混合写屏障机制, 栈空间不启动,堆空间启动。整个过程几乎不需要STW,效率较高。

插入屏障和删除屏障:插强删弱,插删均灰

混合写屏障:栈可达均为黑色,新加对象,栈黑堆灰,删除对象,均为灰色。

1

评论区