【3-3 Golang】GC—标记 清理

  上一篇文章我们主要介绍了三色标记法与写屏障技术，基于这些基础，本篇文章将重点介绍垃圾回收的整个处理流程（开启-标记-标记结束-清理），包括标记协程主流程，经典的startTheworld/stopTheworld问题，辅助标记是什么，清理过程等等。

垃圾回收概述

  Go语言将垃圾回收分为三个阶段：标记（三色标记扫描），标记终止（此时业务逻辑暂停，会再次扫描），未启动（可能也会执行清理工作）；定义如下：

_GCoff             = iota // GC not running; sweeping in background, write barrier disabled
_GCmark                   // GC marking roots and workbufs: allocate black, write barrier ENABLED
_GCmarktermination        // GC mark termination: allocate black, P's help GC, write barrier ENABLED

  垃圾回收过程的启动函数为gcStart，该函数主要逻辑如下：

• 首先检查上一次垃圾回收是否还有mspan未被清理，如果有还需要执行清理工作；
• 垃圾回收器的初始化是不能同时进行的，这里通过锁解决并发问题；
• 垃圾回收过程也是通过创建协程实现的，只是这些协程和普通的用户协程有所不同罢了；
• 垃圾回收的某些初始化工作，是不能与用户协程并发执行的，所以在初始化过程中还需要暂停用户协程（也就是传说中的STW）；

func gcStart(trigger gcTrigger) {
    // 如果还有mspan未被清理，执行清理工作
    for trigger.test() && sweepone() != ^uintptr(0) {
        sweep.nbgsweep++
    }

    //启动垃圾回收过程需要加锁
    semacquire(&work.startSema)  //startSema protects the transition from "off" to mark or mark termination.
    //有这把锁才能stopTheworld
    semacquire(&worldsema)    //Holding worldsema grants an M the right to try to stop the world.

    //创建垃圾回收主协程
    gcBgMarkStartWorkers()

    //STW
    systemstack(stopTheWorldWithSema)

    //设置垃圾回收阶段
    setGCPhase(_GCmark)

    //预处理需要标记的根对象
    gcMarkRootPrepare()

    //设置标识位（很多地方有用到这个标识判断是否在标记）
    atomic.Store(&gcBlackenEnabled, 1)

    //恢复用户协程
    systemstack(func() {
        now = startTheWorldWithSema(trace.enabled)
    })

    semrelease(&worldsema)
    semrelease(&work.startSema)
}

  gcStart函数这就执行结束了？标记过程呢？没看到对应的逻辑啊。想想标记过程肯定是漫长的，如果由gcStart函数同步调用，那可是会阻塞函数调用方的。注意上述主流程创建了垃圾回收主协程，就是这些协程执行的标记过程。

func gcBgMarkStartWorkers() {
    //与P数目保持一致
    for gcBgMarkWorkerCount < gomaxprocs {
        go gcBgMarkWorker()
    }
}

func gcBgMarkWorker() {

    for {
        // Go to sleep until woken by
        // gcController.findRunnableGCWorker.
        gopark(......) 
        {
            // gopark协程换出之前，会将该协程注册到公共pool
            // Release this G to the pool.
            gcBgMarkWorkerPool.push(......)
        }

        decnwait := atomic.Xadd(&work.nwait, -1)

        systemstack(func() {
            //标记扫描
            gcDrain(......)
        })

        incnwait := atomic.Xadd(&work.nwait, +1)

        // 如果该协程是最后一个执行完一轮标记任务，并且没有标记任务需要处理，则标记过程结束
        if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
            gcMarkDone()   //最终调用到gcMarkTermination，垃圾回收状态转换为_GCmarktermination、_GCoff
        }
    }

}

  这里我们需要关注两点：1）标记扫描主函数是gcDrain，该函数主要执行了我们上一篇文章介绍的三色标记过程，这里就不再赘述。2）垃圾回收协程是一个for循环，不过循环开始都是通过gopark协程让出CPU，该协程在什么时候被调度呢？与用户协程一样吗？注意到注释是这么说的，协程一直休眠直到被"gcController.findRunnableGCWorker"唤醒。要理解这一过程，只能去看看Go语言调度器了：

func schedule() {
    if gp == nil && gcBlackenEnabled != 0 {
        gp = gcController.findRunnableGCWorker(_g_.m.p.ptr())
    }
}

  到这里，垃圾回收的启动过程以及工作协程的主逻辑我们基本有个大致解了，当然有一些细节目前还未详细介绍，如STW，如gcDrain，如标记结束阶段（有兴趣可以自己学习研究）等等。

startTheworld/stopTheworld

  上一篇文章我们提到由于用户协程与垃圾回收工作协程并发执行，所以需要写屏障，这就可以了吗？当然不是，垃圾回收的某些初始化工作，是不能与用户协程并发执行的，所以在初始化过程中还需要暂停用户协程，这就是所谓的stopTheworld。如何暂停用户协程呢？

  思考一下，线程M调度协程G是需要绑定逻辑处理器P的，那如果没有可用的逻辑处理P当然也就无法调度用户协程了？逻辑处理器P可以分为三种：1）空闲，没有被任何线程M绑定，这种直接更新其状态即可；2）系统调用中，说明已被线程M绑定，并且正在执行系统调用，同样的直接更新状态即可（系统调度返回后，检测逻辑处理器P的状态不对，线程M会休眠）；3）运行中，也就是已被线程M绑定，并且正在调度用户协程，这种是需要通知其暂停用户协程的，如何通知呢？还记得介绍Go语言调度器提到的抢占式调度吗？协作式抢占调度与基于信号的抢占式调度。对，就是通过这两种方案实现的（与Go版本有关）。

  stopTheWorldWithSema函数的实现逻辑如下：

func stopTheWorldWithSema() {
    //调度器锁
    lock(&sched.lock)
    //等待暂停的P数目
    sched.stopwait = gomaxprocs
    // 标识GC等待运行
    atomic.Store(&sched.gcwaiting, 1)

    //通知所有运行中的P暂停用户协程（抢占式调度：协作式或基于信号实现）
    preemptall()

    //暂停当前P
    _g_.m.p.ptr().status = _Pgcstop // Pgcstop is only diagnostic.
    sched.stopwait--

    for _, p := range allp {
        s := p.status
        //暂停系统调用中的P
        if s == _Psyscall && atomic.Cas(&p.status, s, _Pgcstop) {
            p.syscalltick++
            sched.stopwait--
        }
    }

    //暂停空闲P
    for {
        p := pidleget()
        if p == nil {
            break
        }
        p.status = _Pgcstop
        sched.stopwait--
    }

    wait := sched.stopwait > 0
    unlock(&sched.lock)

    //如果还有P没有暂停，循环阻塞等待
    if wait {
        for {
            // wait for 100us, then try to re-preempt in case of any races
            if notetsleep(&sched.stopnote, 100*1000) {
                noteclear(&sched.stopnote)
                break
            }
            preemptall()
        }
    }
}

  这里貌似还有一个问题：sched.stopwait维护着需要暂停P的数目，P处于运行状态的时候，是基于信号通知用户协程暂停的，通知的结果是不确定的，所以这里才会循环阻塞等待；只是用户协程暂停时，怎么更新sched.stopwait呢？想想用户协程让出CPU之后，该执行什么逻辑呢？当然是调度器了！

func schedule() {
    // 如果等待gc，则暂停M
    if sched.gcwaiting != 0 {
        gcstopm()
        goto top
    }
}

func gcstopm() {
    sched.stopwait--
    //如果所有P都暂停了，通知
    if sched.stopwait == 0 {
        notewakeup(&sched.stopnote)
    }
}

  原来是这么暂停用户协程的，看来还是需要对Go调度器有较深了解。startTheworld就是一个反过程，这里就不在赘述了。

  辅助标记什么意思呢？谁辅助，辅助谁呢？我们已经知道，Go语言启动了多个协程用户处理标记扫描工作，思考一下，与此同时，用户协程还在正常分配内存，如果内存分配过快呢？甚至超过了标记扫描的速度呢？为了解决这个问题，Go语言是这么做的：如果某些用户协程分配内存过快，则需要帮助执行一些标记扫描任务，并且甚至还会暂停其调度。

  在内存分配入口函数mallocgc很容易找到这段逻辑：

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    //只有垃圾回收过程才会走到辅助标记
    if gcBlackenEnabled != 0 {
        assistG = getg()

        assistG.gcAssistBytes -= int64(size)
        // 小于0，说明有欠债，需要帮助辅助标记
        if assistG.gcAssistBytes < 0 {
            gcAssistAlloc(assistG)
        }
    }
}

  怎么衡量是否内存分配过快呢？垃圾回收协程执行了多少标记扫描任务（相当于工作挣钱，全局维护了一个现金池），相应的用户协程就能申请一定比例的内存（用户协程花钱）；用户协程申请了内存（买东西付钱），有了欠债，怎么办，先从全局现金池借呗，如果不够怎么办（申请内存过多），不够了再帮忙挣钱呗！

func gcAssistAlloc(gp *g) {

retry:
    // 申请了内存（买东西），就需要付钱，assistWorkPerByte定义了之间的比例关系
    assistWorkPerByte := gcController.assistWorkPerByte.Load()
    assistBytesPerWork := gcController.assistBytesPerWork.Load()

    //计算该用户协程需要付多少钱
    debtBytes := -gp.gcAssistBytes
    scanWork := int64(assistWorkPerByte * float64(debtBytes))

    // 全局现金池，需要先借钱
    bgScanCredit := atomic.Loadint64(&gcController.bgScanCredit)
    //相当于借的钱
    stolen := int64(0)
    if bgScanCredit > 0 {

        // 全局现金池不够，不足以还债
        if bgScanCredit < scanWork {
            stolen = bgScanCredit
            //债肯定还没还完
            gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(stolen))
        } else {

            //可以还完债
            stolen = scanWork
            gp.gcAssistBytes += debtBytes
        }

        //借钱了，全局扣除
        atomic.Xaddint64(&gcController.bgScanCredit, -stolen)

        //用户协程还剩了这些债务
        scanWork -= stolen

        if scanWork == 0 {
            // We were able to steal all of the credit we needed.
            return
        }
    }

    //辅助标记（挣钱还债）
    systemstack(func() {
        gcAssistAlloc1(gp, scanWork)
    })

    //还有欠债
    if gp.gcAssistBytes < 0 {
        //被抢占了，让出CPU；一旦恢复执行，再次借钱
        if gp.preempt {
            Gosched()
            goto retry
        }

        //阻塞
        if !gcParkAssist() {
            goto retry
        }
    }
}

  辅助标记过程与垃圾回收协程基本类似，通过gcDrainN函数实现；一旦辅助标记也没有还清债务，则阻塞用户协程，这里是将其添加到全局队列work.assistQueue（不能放到P协程队列，不然还会被调度）。什么时候再恢复该用户协程的执行呢？当然是垃圾回收协程做了更多的工作之后，发现有用户协程因为申请内存过快被阻塞，解除的。

//垃圾回收标记扫描主逻辑
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
    if gcw.heapScanWork > 0 {
        if flushBgCredit {
            //gcFlushBgCredit函数更新全局现金池，恢复阻塞的用户协程
            gcFlushBgCredit(gcw.heapScanWork - initScanWork)
        }
        gcw.heapScanWork = 0
    }
}

  清理不是很简单吗？之前介绍过，mspan.allocBits记录内存空闲与否，0表示空闲，1表示已分配；mspan.gcmarkBits用户标记黑色和白色对象，0表示白色也就是需要回收的对象，1表示黑色对象，在三色标记完成之后，只需要allocBits=gcmarkBits就可以了（参考sweepone函数实现）。

  首先清理是一个异步过程，并不是说三色标记完成之后，就清理所有的mspan。分配内存的时候，从mcentral获取mspan的时候，如果没有清理则执行清理工作，清理之后如果有空闲内存则返回；另外，垃圾回收启动的时候，也需要清理上一次标记后的所有mspan。

  怎么标记mspan有没有被清理呢？Go语言使用字段sweepgen表示，这是一个整型，通过与全局的 mheap_.sweepgen比较，以此判断该mspan是否已被清理，判断方式如下：

// if sweepgen == h->sweepgen - 2, the span needs sweeping
// if sweepgen == h->sweepgen - 1, the span is currently being swept
// if sweepgen == h->sweepgen, the span is swept and ready to use
// if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
// if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
// h->sweepgen is incremented by 2 after every GC

  sweep就是清理的意思，gen是第几代的缩写（generation）。注释说h->sweepgen没开启一轮GC，自增2；假设初始h->sweepgen等于X，mspan.sweepgen也等于X（新申请的mspan.sweepgen直接赋值为h->sweepgen），根据上面描述，该mspan已经清理可以使用；开启新一轮GC后，h->sweepgen等于X+2，满足第一个条件，说明该mspan需要被清理。设计的还是非常巧妙的，不然还需要设法维护每一个mspan的清理状。

  清理mspan是有可能并发执行的，用户协程申请内存时就有可能执行清理工作，所以清理mspan也是需要加锁的（基于cas），下面是获取待清理mspan逻辑：

func (l *sweepLocker) tryAcquire(s *mspan) (sweepLocked, bool) {
    //状态非待清理
    if atomic.Load(&s.sweepgen) != l.sweepGen-2 {
        return sweepLocked{}, false
    }
    //设置状态为清理中
    if !atomic.Cas(&s.sweepgen, l.sweepGen-2, l.sweepGen-1) {
        return sweepLocked{}, false
    }
    return sweepLocked{s}, true
}

//获取mspan执行清理的过程
if s, ok := sl.tryAcquire(s); ok {
    if s.sweep(false)
}

  另外，如果mspan被缓存在mcache使用情况下，mspan.sweepgen满足的是第四以及第五个条件；当mspan无可用内存分配时，会从mcache缓存删除，此时也会修改mspan.sweepgen；另外在垃圾回收标记终止阶段，也会删除所有逻辑处理器P的mcache（同样会修改mspan.sweepgen）。所以不用担心缓存的mspan无法被清理。

  最后，还记得mcentral的结构定义吗（如下）？partial与full都是一个数组，数组长度为2，都是一个数组索引的mspan已经被清理，另一个数组索引的mspan还未被清理。那到底partial[0]是已被清理的，还是partial[1]是已被清理的呢？答案是不一定。

type mcentral struct {
    spanclass spanClass

    //partial存储有空闲内存的mspan
    partial [2]spanSet // list of spans with a free object

    //full存储的mspan没有空闲内存
    full    [2]spanSet // list of spans with no free objects
}

  我们看看Go语言是如何获取已被清理和未清理的mspan：

func (c *mcentral) partialUnswept(sweepgen uint32) *spanSet {
    return &c.partial[1-sweepgen/2%2]
}

func (c *mcentral) partialSwept(sweepgen uint32) *spanSet {
    return &c.partial[sweepgen/2%2]
}

  sweepgen每次自增2，只能是偶数；如2、4、6、8，但是除以2之后，就有可能是奇数了，如1、2、3、4。假设当前sweepgen等于10，根据上面代码的计算方式，则本轮已清理的mspan都在partial[1]，未清理的都在partial[0]，开启下一轮之前，需要清理所有的mspan，清理后的mspan都在partial[1]；新一轮GC开启，h->sweepgen自增2等于12，根据上面代码的计算方式，已清理的mspan都在partial[0]，未清理的都在partial[1]（刚好partial[1]数组的mspan在新一轮GC标记扫描后，是需要被清理的）。

  同样的，由于h->sweepgen自增2，已清理的mspan和未清理的mspan，在数组partial和full的索引是轮询的，避免了每次开启GC后，还需要迁移mcentral的所有mspan。

  本篇文章主要介绍了垃圾回收的基本流程，包括垃圾回收工作协程的创建与调度，经典的startTheworld/stopTheworld问题，辅助标记是什么，清理过程（重点琢磨sweepgen的设计思路）等等。更多细节还需要读者不断学习研究。