揭秘Golang内存管理优化!三色标记法源码浅析

点击数:30

导语
       垃圾回收的第一步是什么呢?要找到垃圾,如果我们反其道而行之,找到所有的存活对象,是不是也等于找到了垃圾呢? 本文想要探讨的gcDrain函数就是使用三色标记法找到存活对象的一个重要函数,了解gcDrain函数就会对golang垃圾回收机制有更深的理解。

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

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

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

二. 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.17,如果对1.13版本之后的有关于golang垃圾回收历史感兴趣的同学可以搜索golang的官网查看相关的改动。

三. golang垃圾回收过程

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

阶段 说明 赋值器状态
SweepTermination 清扫终止阶段,为下一个阶段的并发标记做准备工作,启动写屏障 STW
Mark 扫描标记阶段,与赋值器并发执行,写屏障开启 并发
MarkTermination 标记终止阶段,保证一个周期内标记任务完成,停止写屏障 STW
GCoff 内存清扫阶段,将需要回收的内存暂存,写屏障关闭 并发
GCoff 内存归还阶段,将内存依照策略归还给操作系统,写屏障关闭 并发

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

再看下我们最早提到的火焰图中有关于垃圾回收这一部分:
可以看出我们性能较差的地方在gcBgMarkWorker这个函数中,说明我们在标记存活对象的过程中cpu耗费了大量的时间。其中gcDrain就是三色标记法在golang中的实现。

四. 三色标记法

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

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

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

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

五. 写屏障

golang1.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 被错误地回收
那么如何解决这种问题呢,golang1.5引入了写屏障机制来确保垃圾回收器的正确性。

●强三色不变式

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

●弱三色不变式

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

六. gcDrain函数的实现

6.1 gcDrain函数的触发阶段

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

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

 

6.2 gcDrain函数的参数

func gcDrain(gcw *gcWork, flags gcDrainFlags)

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

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上会绑定一个gcWorkgcWork中最重要的结构就是两个本地工作缓存wbuf1wbuf2

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
}

我们可以认为wbuf1wbuf2中存储的是灰色对象,具体存储的地方就在obj这个指针数组中,其中指针数组中灰色对象的个数为nobj,灰色对象被定义为lfnodelfnode的底层实现涉及到了CAS(Compare And Swag),这是为了解决并发问题。

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

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

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

6.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满了就将wbuf1wbuf2进行交换,如果交换之后依旧是满的,那么就将这部分灰色对象flush到全局工作缓存中,并将flushedWork标记为true,这意味着gcWork中的wbuf与全局wbuf有过数据交换。

 

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

5.3.4 wbBufFlush

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

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

5.4 gcDrain函数

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 {
            /** balance函数用来平衡各个核的工作量**/
            gcw.balance()
        }
        // 获取任务,消费workbuf中的灰色对象
        // 使用tryGetFast快速获取工作队列中的对象,tryGet方法虽然可以获取,但是代价较大
        b := gcw.tryGetFast()
        if b == 0 {
            /****tryGet函数用来获取工作缓存中的灰色对象****/
            b = gcw.tryGet()
            if b == 0 {
                /****wbBufFlush函数将写屏障生成的灰色对象flush到全局工作缓存****/
                wbBufFlush(nil, 0)
                b = gcw.tryGet()
            }
        }
        // 获取不到对象,标记队列已为空,跳出循环
        if b == 0 {
            // Unable to get work.
            break
        }
        // 扫描获取到的对象
        scanobject(b, gcw)
        // 与调度有关,每个p只干自己分内之事
        ...
    }
done:
    // 结束的相关收尾工作
    ...
}

对于gcDrain函数,可以理解为一个生产者消费者问题,生产者生产灰色对象放入wbuf中,

其中write Barriermark 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) {
        /****put函数将灰色对象放入工作缓存中****/
        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中以外,也会将灰色对象涂黑,所以grayObjectscanObject以及生产灰色对象的write Barriermark root以及scan stack组成了一个生产和消费灰色对象的生态圈,从而实现了三色标记算法。

七. 总结

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

 

参考文
1.【Golang】粗线条话GC(二)_哔哩哔哩_bilibili

2.GC 的认识 – 16. Go 历史各个版本在 GC 方面的改进?- 《Go 语言问题集(Go Questions)》 – 书栈网 · BookStack
3.Go 语言垃圾收集器的实现原理 | Go 语言设计与实现 (draveness.me)

本篇文章来源于微信公众号: 腾讯看点技术

Share
%d 博主赞过: