您的位置 首页 golang

揭秘golang垃圾回收!三色标记法深入剖析

作者:victoryjin,腾讯PCG策略开发工程师

源自某次技术需求后的发现

对于想要 golang 垃圾回收的来源于一次技术需求,某天,当我愉快的把代码灰度发布到正式环境后,出现了问题,123平台的火焰图有些异常。

图里 runtime.scanobject 这部分是大平顶,这说明 cpu 在这部分耗时是很久的,而 runtime.scanobject 是属于 runtime.gcDrain 这个函数的,最下方调用的函数是 runtime.gcBgMarkWorker ,这些函数看上去和垃圾回收是有关系的(garbage collection),那么 golang 的垃圾回收是什么样的呢?

1.golang垃圾回收小史

golang 版本发展的历史中,垃圾回收器机制的演进占据了重要的位置。

golang 在1.0版本引入了串行标记清扫,在进行标记和清扫工作时,所有的 goroutine 都会停下来(stop the word)等待这两个工作的结束。如果说我们的服务中要使用到大量的内存, golang 程序会发生明显的卡顿现象,这对于后台服务来说是无法忍受的。到了1.3版本,将清扫的过程抽离了出来,和用户 goroutine 一起执行,提高了不少性能。

在1.5版本中, golang 的垃圾回收机制迎来了巨大的改变,在原先版本中标记存活对象的过程是完全占用一个 goroutine 的,而1.5版本中,标记过程和开启了写屏障的用户 goroutine 可以同时运行。实现了并行版本的三色标记清除垃圾收集器,极大的降低了 STW 的时间,

1.8版本中,引入了混合写屏障,消除了对栈本身的重新扫描,又一次降低了 STW 的时间。

1.13版本中,改进 Scavenger ,这部分是垃圾回收器在回收完垃圾后将内存返回给操作系统的结构,老版本是另开一个 goroutine 运行,在1.13版本也和其他用户 goroutine 并发执行,进一步提高了垃圾回收器的效率。

这里只是对于 golang 垃圾回收历史中几个我觉得比较重要的改进做了说明,现在 golang 的最新版本为1.16.6,如果对1.13版本之后的有关于 golang 垃圾回收历史感兴趣的同学可以搜索 golang 的官网查看相关的改动。

2.golang垃圾回收过程

以1.13版本为例子,垃圾回收的过程以 STW 作为界限可以分为5个阶段

阶段

说明

赋值器状态

SweepTermination

清扫终止阶段,为下一个阶段的并发标记做准备工作,启动写屏障

STW

Mark

扫描标记阶段,与赋值器并发执行,写屏障开启

并发

MarkTermination

标记终止阶段,保证一个周期内标记任务完成,停止写屏障

STW

GCoff

内存清扫阶段,将需要回收的内存暂存,写屏障关闭

并发

GCoff

内存归还阶段,将内存依照策略归还给操作系统,写屏障关闭

并发

每个阶段的触发函数如下:

再看下我们最早提到的火焰图中有关于垃圾回收这一部分:

可以看出我们性能较差的地方在 gcBgMarkWorker 这个函数中,说明我们在标记存活对象的过程中 cpu 耗费了大量的时间。其中 gcDrain 就是三色标记法在 golang 中的实现。

3. 三色标记法

三色标记法是 golang 在堆内存中寻找存活对象的抽象过程。

其中黑色对象标识该对象已经被标记过了,且黑色对象引用的对象也全部都被标记过了。灰色对象表示该对象已经被标记了但是该对象引用的对象没有被全部标记。白色对象就是没有被标记的对象,被认为是潜在的垃圾,在标记开始前,所有对象都是白色对象。

在垃圾收集器开始工作时,从根对象开始进行遍历访问,有如下几个步骤:

通过这种方式, golang 垃圾收集器就可以找到需要进行回收的垃圾,不过这是抽象层面的做法,具体的实现在之后的章节会有介绍。

4. 写屏障

golang 1.5之后,标记垃圾的协程和用户用户协程可以并发执行,这样就会出现问题,如果把垃圾标记为存活对象,虽然这对于垃圾收集器来讲是错误的但是它不影响程序的正确性,垃圾收集器只要在下一次垃圾收集的过程中将这个对象收集就好了,但是如果标记垃圾执行在前,将一个对象标记为垃圾,然而用户协程又引用了这个对象,这就会造成把存活对象当作垃圾的冤案。下面有一个例子可以说明这个问题

  1. 初始状态:假设某个黑色对象 C 指向某个灰色对象 A ,而 A 指向白色对象 B;
  2. C.ref3 = C.ref2.ref1 :赋值器并发地将黑色对象 C 指向( ref3 )了白色对象 B;
  3. A.ref1 = nil :移除灰色对象 A 对白色对象 B 的引用( ref2 );
  4. 最终状态:在继续扫描的过程中,白色对象 B 永远不会被标记为黑色对象了(回收器不会重新扫描黑色对象),进而对象 B 被错误地回收

那么如何解决这种问题呢, golang 1.5引入了写屏障机制来确保垃圾回收器的正确性。

  • 强三色不变式

关注白色指针指向黑色对象的写入操作,不允许出现黑色指针指向白色,如果出现黑色对象指向白色对象,那就使用插入写屏障,具体的做法就是将黑色对象指向的白色对象涂灰或者将黑色对象涂灰。

  • 弱三色不变式

如果有黑色对象指向白色对象时继续观察,如果还有灰色对象指向该白色对象,说明满足弱三色不变式,弱三色不变式提醒我们关注对那些白色对象路径的破坏行为。解决这个问题的方式是删除写屏障,可以把灰色对象指向的白色对象涂灰,这样黑色对象指向的就是灰色对象而不是之前的白色对象。

使用写屏障之后,垃圾回收器的正确性就得到了保障。

5.gcDrain函数的实现

5.1gcDrain函数的触发阶段

从之前的火焰图可以看出来, gcDrain 函数是火焰图中大平顶函数的调用的函数之一。

该函数的触发位置如图所示,处在第一次 STW 之后的标记阶段,

5.2gcDrain函数的参数

 func gcDrain(gcw *gcWork, flags gcDrainFlags)
  

gcDrain 函数的参数有两个,其中 gcw 是该函数主要处理的结构, gcDrainFlags golang 的调度有很大关系

 type p struct {
    ...
    // 每个p上绑定一个gcWork
    gcw gcWork
}

type gcWork struct {
    // 本地工作缓存,wbuf1为主工作缓存,wbuf2为副工作缓存
 wbuf1, wbuf2 *workbuf

 // 标记变黑的结点
 bytesMarked uint64

    // 每个p做了多少标记工作的记录,与调度有关
 scanWork int64

    // gcWork的workbuff是否与全局workbuff进行过flash操作
    flushedWork bool
}
  

p(process) golang 定义的一个抽象的概念,它不是物理上的 CPU ,当一个 P 有任务,需要创建或者唤醒一个系统线程去处理它队列中的任务, P 决定同时执行的任务数量,我们平常会进场看到 GOMAXPROCS 这个参数, GOMAXPROCS 就是限制系统线程执行用户层面的任务的数量,可以简单的理解为一个 p 对应一个物理核心。每个 p 上会绑定一个 gcWork gcWork 中最重要的结构就是两个本地工作缓存 wbuf1 wbuf2

 type workbuf struct {
 workbufhdr
 // uintptr 是golang的内置类型,可以存储指针的整型,这种指针类型是可以做运算的
 // obj 是一个指针数组,每个元素是一个可以进行计算的指针,该指针通过计算可以指向灰色对象
 obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
}

type workbufhdr struct {
 // 灰色对象
 node lfnode
 // 工作缓存中灰色对象的个数
 nobj int
}

//  lock -free stack node.
// lock-free机制的底层实现是CAS,目的是为了解决并发问题
type lfnode struct {
 next    uint64
 pushcnt uintptr
}
  

我们可以认为 wbuf1 wbuf2 中存储的是灰色对象,具体存储的地方就在 obj 这个指针数组中,其中指针数组中灰色对象的个数为 nobj ,灰色对象被定义为 lfnode ,这种结果的底层实现是 CAS(Compare And Swag)

gcDrain 函数主要就是在使用 wbuf1 wbuf2 以及全局 wbuf 来实现三色标记法,而引入全局 wbuf 的目的在于平衡每个 P 的工作量,不至于旱的旱死,涝的涝死。

5.3 操作gcWork中灰色对象的函数

针对 gcWork 的操作有四个,总结下来其实是两个,带有 Fast 后缀的方法是其主方法的简单实现形式,目的是减少使用主方法带来的代价。

5.3.1 put

 func (w *gcWork) put(obj uintptr) {
        flushed := false
        wbuf := w.wbuf1
   ....
    // 如果wbuf1没有创建
    if wbuf == nil {
           // 初始化并给wbuf1一个空值
           w.init()
           wbuf = w.wbuf1
       // 如果wbuf1是满的
     } else if wbuf.nobj == len(wbuf.obj) {
            // wbuf1和wbuf2进行交换
            w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
            wbuf = w.wbuf1
            // 如果交换之后还是满的
            if wbuf.nobj == len(wbuf.obj) {
                  // 就把wbuf1中的灰色对象放入全局工作缓存中
                  putfull(wbuf)
                  // 与全局工作缓存执行过交流后设置该标记位
                  w.flushedWork = true
                  // 将wbuf1的内容置为空
                  wbuf = getempty()
                  w.wbuf1 = wbuf
                  flushed = true
            }
    }

    // 如果wbuf1不满,就直接操作wubf1
    wbuf.obj[wbuf.nobj] = obj
    wbuf.nobj++
    ....
}
  

其中 put 操作就是将灰色对象放入 wbuf1 中,如果 wbuf1 满了就将 wbuf1 wbuf2 进行交换,如果交换之后依旧是满的,那么就将这部分灰色对象flush到全局工作缓存中,并将 flushedWork 标记为true,这意味着 gcWork 中的 wbuf 与全局 wbuf 有过数据交换。

5.3.2 tryGet

 func (w *gcWork) tryGet() uintptr {
 wbuf := w.wbuf1
 if wbuf == nil {
  w.init()
  wbuf = w.wbuf1
 }
 // 当wbuf1缓冲区中没有灰色对象时
 if wbuf.nobj == 0 {
  // wubf1 与 wbuf2 进行对象互换
  w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
  wbuf = w.wbuf1
  // 如果交换完还为空,意味着本地的主从buffer均为空
  if wbuf.nobj == 0 {
   owbuf := wbuf
   // 需要从全局工作缓存中取
   wbuf = trygetfull()
   // 如果全局工作缓存中也没有灰色对象,就返回
   if wbuf == nil {
    return 0
   }
   putempty(owbuf)
   // 将得到的灰色对象给wbuf1
   w.wbuf1 = wbuf
  }
 }

 wbuf.nobj--
 return wbuf.obj[wbuf.nobj]
}
  

首先判断 wbuf1 中是否有灰色对象,如果没有就将 wbuf1 wbuf2 进行交换,如果两个 wbuf 均为空,那么就需要请求全局工作缓存中的灰色对象了,与全局工作缓存的交互保证了每个 P 上绑定的 gcWork 不至于太忙也不至于太闲。

5.3.3 balance

gcDrain 的源码中,如果全局工作 wbuf 为空,会尝试使用 balance() 函数将本地 wbuf 的一部分灰色对象贡献给全局 wbuf

 func (w *gcWork) balance() {
 if w.wbuf1 == nil {
  // 这里wbuf1, wbuf2队列还没有初始化
  return
 }
 // 如果wbuf2不为空,则上交到全局,并获取一个空的队列给wbuf2
 if wbuf := w.wbuf2; wbuf.nobj != 0 {
  putfull(wbuf)
  w.flushedWork = true
  w.wbuf2 = getempty()
 } else if wbuf := w.wbuf1; wbuf.nobj > 4 {
  // 把未满的wbuf1分成两半,并把其中一半上交到全局队列
  w.wbuf1 = handoff(wbuf)
  w.flushedWork = true // handoff did putfull
 } else {
  return
 }
 ...
}
  

如果 wbuf2 不为空,意味着 wbuf1 wbuf2 已经进行过一次交换了,说明此时该 p 上的 gcWork 的工作量是比较大的,为了缓解工作压力, balance() 函数会将 wbuf2 中的灰色对象全部 flush 到全局 wbuf 中。除了会扫描 wbuf2 以外, balance() 还会扫描 wbuf1 中的灰色对象,如果 wbuf1 中的灰色对象的个数大于4,也会将 wbuf1 中的一半的灰色对象 flush 到全局 wbuf 中。

5.3.4 wbBufFlush

除了 wbuf1 wbuf2 以外,还有一个专门存放由写屏障产生的灰色对象,我们称之为 wbbuf ,在 gcDrain 中只使用了 wbBufFlush 函数将 wbbuf 中的灰色对象 flush 到全局 wbuf 中。

写屏障产生灰色对象后会把灰色对象放入到 wbbuf 中,等到 wbbuf 满了之后就 flush 到全局 wbuf 中。

5.4gcDrain函数

 func gcDrain(gcw *gcWork, flags gcDrainFlags) {
 // 此处一定要开启写屏障,不开启就会抛出错误
 if !writeBarrier.needed {
  throw("gcDrain phase incorrect")
 }
 // 这一部分代码和调度有关,每个p都有固定的扫描灰色对象的工作量
 ...
 
 // 如果根对象未扫描,则先扫描根对象,Jobs为根对象总数,next相当于一个对象任务的取数器
 if work.markrootNext < work.markrootJobs {
  // 一直循环知道被抢占或者STW
  for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
   // 从根对象扫描队列取出一个值
   job := atomic.Xadd(&work.markrootNext, +1) - 1
   if job >= work.markrootJobs {
    break
   }
   // 将会扫描根对象,并把它加入到标记队列gcWork中,即把对象变为灰色
   markroot(gcw, job)
   // 退出标记任务的条件,与调度有关
   ...
   go done
  }
 }
 // 当根对象全部put到标记队列中,消费标记队列,根据对象图进行消费
 // 一直循环直到被抢占或者STW
 for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
  // 如果全局工作缓存为空,将本地的一部分工作放回全局队列中
  if work.full == 0 {
   gcw.balance()
  }
  // 获取任务,消费workbuf中的灰色对象
  // 使用tryGetFast快速获取工作队列中的对象,tryGet方法虽然可以获取,但是代价较大
  b := gcw.tryGetFast()
  if b == 0 {
   b = gcw.tryGet()
   if b == 0 {
    // Flush the write barrier
    //  buffer ; this may create
    // more work.
    wbBufFlush(nil, 0)
    b = gcw.tryGet()
   }
  }
  // 获取不到对象,标记队列已为空,跳出循环
  if b == 0 {
   // Unable to get work.
   break
  }
  // 扫描获取到的对象
  scanobject(b, gcw)
  // 与调度有关,每个p只干自己分内之事
  ...
 }
done:
 // 结束的相关收尾工作
 ...
}
  

对于 gcDrain 函数,可以理解为一个生产者消费者问题,生产者生产灰色对象放入 wbuf 中,消费者从 wbuf 中拿出灰色对象并涂黑。

其中 write Barrier mark root 以及 scan stack 都是提供灰色对象的,这些操作中都会有着 greyObject 这个函数的影子,

 func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
............
  if span.spanclass.noscan() {
     // 将灰色对象涂黑
   gcw.bytesMarked += uint64(span.elemsize)
   return
  }
 }
............
 /// 将对象放入wbuf中,也就是将对象涂灰
 if !gcw.putFast(obj) {
  gcw.put(obj)
 }
}
  

这个函数不仅仅是一个消费者,它也是一个生产者。

scanObject 这个函数就是三色标记法中通过灰色对象去扫描该对象的引用对象,并将其涂灰

 func scanobject(b uintptr, gcw *gcWork) {
 // 获取 b 的 heapBits 对象
 hbits := heapBitsForAddr(b)
 // 获取span
 s := spanOfUnchecked(b)
 // span对应的大小
 n := s.elemsize
 if n == 0 {
  throw("scanobject n == 0")
 }
 // 如果对象过大,切割后扫描
    // 每次最大只扫描128KB
 if n > maxObletBytes {
  if b == s.base() {
   if s.spanclass.noscan() {
                // 涂黑操作
    gcw.bytesMarked += uint64(n)
    return
   }
   // 将多于128KB的对象重新放回gcworker中,下次再扫描
   for oblet := b + maxObletBytes; oblet < s.base()+s.elemsize; oblet += maxObletBytes {
    if !gcw.putFast(oblet) {
     gcw.put(oblet)
    }
   }
  }
  n = s.base() + s.elemsize - b
  if n > maxObletBytes {
   n = maxObletBytes
  }
 }

 var i uintptr
 for i = 0; i < n; i += sys.PtrSize {
  // 为了求出偏移量i,与传入的b做计算得到灰色对象真正的内存地址
        ...
  // 取出指针的值
  obj := *(*uintptr)(unsafe.Pointer(b + i))

  if obj != 0 && obj-b >= n {
   // 根据地址值去堆中查找对象
   if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
    // 调用 geryobject 标记对象并把对象放到标记队列中
    greyobject(obj, b, i, span, gcw, objIndex)
   }
  }
 }
 gcw.bytesMarked += uint64(n)
 gcw.scanWork += int64(i)
}
  

scanObject 除了生产灰色对象到 wbuf 中以外,也会将灰色对象涂黑,所以 grayObject scanObject 以及生产灰色对象的 write Barrier mark root 以及 scan stack 组成了一个生产和消费灰色对象的生态圈,从而实现了三色标记算法。

6. 总结

说完上面的内容,再来看火焰图是不是就清晰很多了呢,大平顶出现的位置是 scanObject findObject 等函数,这些函数主要的作用就是寻找灰色对象引用的对象并将其涂黑,为什么这里这些函数花费了大量的时间呢,是因为常驻于内存中结构体指针的数目太大了,所以减小垃圾回收压力的一个方法就是减少常驻于内存的结构体指针。

文章来源:智云一二三科技

文章标题:揭秘golang垃圾回收!三色标记法深入剖析

文章地址:https://www.zhihuclub.com/87143.shtml

关于作者: 智云科技

热门文章

发表评论

您的电子邮箱地址不会被公开。

网站地图