Golang GC算法解读

柔光的暖阳◎ 2022-02-03 10:39 315阅读 0赞

## 概括 ##

Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 三色并发标记清理算法。  
**非分代**：不像Java那样分为年轻代和年老代，自然也没有minor gc和maj o gc的区别。  
**非紧缩**：在垃圾回收之后不会进行内存整理以清除内存碎片。  
**写屏障**：在并发标记的过程中，如果应用程序（mutator）修改了对象图，就可能出现标记遗漏的可能，写屏障就是为了处理标记遗漏的问题。  
**三色**：将GC中的对象按照搜索的情况分成三种：

1.  黑色: 对象在这次GC中已标记,且这个对象包含的子对象也已标记
2.  灰色: 对象在这次GC中已标记, 但这个对象包含的子对象未标记
3.  白色: 对象在这次GC中未标记  
    **并发**：可以和应用程序（mutator）在一定程度上并发执行。  
    **标记清理**：GC算法分为两个大步骤：标记阶段找出要回收的对象，清理阶段则回收未被标记的对象（要被回收的对象）

## 触发时机 ##

*  gcTriggerAlways: 强制触发GC，没找到什么情况下使用这个
 *  gcTriggerHeap: 当前分配的内存达到一定值（动态计算）就触发GC
 *  gcTriggerTime: 当一定时间（2分钟）没有执行过GC就触发GC
 *  gcTriggerCycle: 要求启动新一轮的GC, 已启动则跳过, 手动触发GC的runtime.GC()会使用这个条件

func gcStart(mode gcMode, trigger gcTrigger) {
        // Since this is called from malloc and malloc is called in
        // the guts of a number of libraries that might be holding
        // locks, don't attempt to start GC in non-preemptible or
        // potentially unstable situations.
        mp := acquirem()
        if gp := getg(); gp == mp.g0 || mp.locks > 1 || mp.preemptoff != "" {
            releasem(mp)
            return
        }
        releasem(mp)
        mp = nil
    
        // 检查GC条件是否满足，和下面的test()构成双检查锁，如果满足GC条件但目前处于GC清理阶段，那就参与清理
        for trigger.test() && gosweepone() != ^uintptr(0) {
            sweep.nbgsweep++
        }
    
        // 加锁检查
        semacquire(&work.startSema)
        if !trigger.test() {
            semrelease(&work.startSema)
            return
        }
        /***************  .....  *****************/
        
    }

在trigger.test()函数中，检查是否满足GC触发的条件

func (t gcTrigger) test() bool {
        if !memstats.enablegc || panicking != 0 {
            return false
        }
        if t.kind == gcTriggerAlways {
            return true
        }
        if gcphase != _GCoff {
            return false
        }
        switch t.kind {
        case gcTriggerHeap:
            // Non-atomic access to heap_live for performance. If
            // we are going to trigger on this, this thread just
            // atomically wrote heap_live anyway and we'll see our
            // own write.
            return memstats.heap_live >= memstats.gc_trigger
        case gcTriggerTime:
            if gcpercent < 0 {
                return false
            }
            lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
            // forcegcperiod = 2分钟
            return lastgc != 0 && t.now-lastgc > forcegcperiod
        case gcTriggerCycle:
            // t.n > work.cycles, but accounting for wraparound.
            return int32(t.n-work.cycles) > 0
        }
        return true
    }
    const (
        // gcTriggerAlways indicates that a cycle should be started
        // unconditionally, even if GOGC is off or we're in a cycle
        // right now. This cannot be consolidated with other cycles.
        gcTriggerAlways gcTriggerKind = iota
    
        // gcTriggerHeap indicates that a cycle should be started when
        // the heap size reaches the trigger heap size computed by the
        // controller.
        gcTriggerHeap
    
        // gcTriggerTime indicates that a cycle should be started when
        // it's been more than forcegcperiod nanoseconds since the
        // previous GC cycle.
        gcTriggerTime
    
        // gcTriggerCycle indicates that a cycle should be started if
        // we have not yet started cycle number gcTrigger.n (relative
        // to work.cycles).
        gcTriggerCycle
    )

## 算法过程 ##

1.  Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC
2.  Mark: 扫描所有根对象, 和根对象可以到达的所有对象, 标记它们不被回收
3.  Mark Termination: 完成标记工作, 重新扫描部分根对象(要求STW)
4.  Sweep: 按标记结果清扫span
    
     
    
    ![1036501-0d3bcaade977a46f.jpg][]
    
    golang\_gc.jpg

func gcStart(mode gcMode, trigger gcTrigger) {
        // 拿到锁，保证只有一个执行流进入到这个临界区
        semacquire(&worldsema)
    
        // 启动后台扫描任务(G)
        if mode == gcBackgroundMode {
            gcBgMarkStartWorkers()
        }
    
        gcResetMarkState()
    
        work.stwprocs, work.maxprocs = gomaxprocs, gomaxprocs
        if work.stwprocs > ncpu {
            work.stwprocs = ncpu
        }
        work.heap0 = atomic.Load64(&memstats.heap_live)
        work.pauseNS = 0
        work.mode = mode
    
        now := nanotime()
        work.tSweepTerm = now
        work.pauseStart = now
        if trace.enabled {
            traceGCSTWStart(1)
        }
        systemstack(stopTheWorldWithSema)
        // Finish sweep before we start concurrent scan.
        systemstack(func() {
            finishsweep_m()
        })
        // clearpools before we start the GC. If we wait they memory will not be
        // reclaimed until the next GC cycle.
        clearpools()
    
        work.cycles++
        if mode == gcBackgroundMode { // Do as much work concurrently as possible
            gcController.startCycle()
            work.heapGoal = memstats.next_gc
    
            // Enter concurrent mark phase and enable
            // write barriers.
            setGCPhase(_GCmark)
    
            gcBgMarkPrepare() // Must happen before assist enable.
            gcMarkRootPrepare()
    
            // Mark all active tinyalloc blocks. Since we're
            // allocating from these, they need to be black like
            // other allocations. The alternative is to blacken
            // the tiny block on every allocation from it, which
            // would slow down the tiny allocator.
            gcMarkTinyAllocs()
    
            // At this point all Ps have enabled the write
            // barrier, thus maintaining the no white to
            // black invariant. Enable mutator assists to
            // put back-pressure on fast allocating
            // mutators.
            atomic.Store(&gcBlackenEnabled, 1)
    
            // Assists and workers can start the moment we start
            // the world.
            gcController.markStartTime = now
    
            // Concurrent mark.
            systemstack(func() {
                now = startTheWorldWithSema(trace.enabled)
            })
            work.pauseNS += now - work.pauseStart
            work.tMark = now
        }
    
        semrelease(&work.startSema)
    }

关键函数及路径：

1.  gcBgMarkStartWorkers():准备后台标记工作goroutine（allp）， 启动后等待该任务通知信号量bgMarkReady再继续，notewakeup(&work.bgMarkReady)
2.  gcResetMarkState():重置一些全局状态和所有gorontine的栈（一种根对象）扫描状态
3.  **systemstack(stopTheWorldWithSema):启动stop the world**
4.  systemstack(func()\{finishsweep\_m()\}): 不断去除要清理的span进行清理，然后重置gcmark位
5.  clearpools(): 清扫sched.sudogcache和sched.deferpool，不知道在干嘛......
6.  gcController.startCycle():启动新一轮GC，设置gc controller的状态位和计算一些估计值
7.  setGCPhase(\_GCmark):设置GC阶段，启用写屏障
8.  gcBgMarkPrepare():设置后台标记任务计数；work.nproc = ^uint32(0)，work.nwait = ^uint32(0)
9.  gcMarkRootPrepare(): 计算扫描根对象的任务数量
10. gcMarkTinyAllocs(): 标记所有tiny alloc等待合并的对象
11. atomic.Store(&gcBlackenEnabled, 1): 启用辅助GC
12. **systemstack(func()\{now=startTheWorldWithSema(trace.enable)\}): 停止stop the world**

func gcBgMarkWorker(_p_ *p) {
        /**********  .......  ***********/
        // 通知gcBgMarkStartWorkers可以继续处理
        notewakeup(&work.bgMarkReady)
    
        for {
    
            // 切换到g0运行
            systemstack(func() {
                // Mark our goroutine preemptible so its stack
                // can be scanned. This lets two mark workers
                // scan each other (otherwise, they would
                // deadlock). We must not modify anything on
                // the G stack. However, stack shrinking is
                // disabled for mark workers, so it is safe to
                // read from the G stack.
                casgstatus(gp, _Grunning, _Gwaiting)
                switch _p_.gcMarkWorkerMode {
                default:
                    throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
                case gcMarkWorkerDedicatedMode:
                    gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
                    if gp.preempt {
                        lock(&sched.lock)
                        for {
                            gp, _ := runqget(_p_)
                            if gp == nil {
                                break
                            }
                            globrunqput(gp)
                        }
                        unlock(&sched.lock)
                    }
                    // Go back to draining, this time
                    // without preemption.
                    gcDrain(&_p_.gcw, gcDrainNoBlock|gcDrainFlushBgCredit)
                case gcMarkWorkerFractionalMode:
                    gcDrain(&_p_.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit)
                case gcMarkWorkerIdleMode:
                    gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
                }
                casgstatus(gp, _Gwaiting, _Grunning)
            })
    
            /********   ......  ***********/
            // 判断是否所有后台标记任务都完成, 并且没有更多的任务
            if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
                gcMarkDone()
            }
        }
    }

1.  gcDrain()是执行标记的函数
2.  当所有标记任务完成时，执行gcMarkDone()函数

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
        initScanWork := gcw.scanWork
        // 如果根对象未扫描完，则先扫描根对象，Jobs为根对象总数，next相当于一个对象任务的取数器
        if work.markrootNext < work.markrootJobs {
            for !(preemptible && gp.preempt) {
                job := atomic.Xadd(&work.markrootNext, +1) - 1
                if job >= work.markrootJobs {
                    break
                }
                // 将会扫描根对象，并把它加入到标记队列gcWork中之中，也就是把对象变成灰色
                markroot(gcw, job)
                if check != nil && check() {
                    goto done
                }
            }
        }
    
        // 当根对象全部put到标记队列中, 消费标记队列，根据对象图进行消费
        for !(preemptible && gp.preempt) {
            if work.full == 0 {
                gcw.balance()
            }
    
            var b uintptr
            if blocking {
                b = gcw.get()
            } else {
                b = gcw.tryGetFast()
                if b == 0 {
                    b = gcw.tryGet()
                }
            }
            if b == 0 {
                // work barrier reached or tryGet failed.
                break
            }
            scanobject(b, gcw)
    
            // 如果已经扫描了一定数量的对象(gcCreditSlack的值是2000)
            if gcw.scanWork >= gcCreditSlack {
                // 把扫描的对象数量添加到全局
                atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
                // 减少辅助GC的工作量和唤醒等待中的G
                if flushBgCredit {
                    gcFlushBgCredit(gcw.scanWork - initScanWork)
                    initScanWork = 0
                }
                idleCheck -= gcw.scanWork
                gcw.scanWork = 0
                
                // 如果是idle模式且达到了检查的扫描量, 则检查是否有其他任务(G), 如果有则跳出循环
                if idle && idleCheck <= 0 {
                    idleCheck += idleCheckThreshold
                    if pollWork() {
                        break
                    }
                }
            }
        }
    
    done:
        // 把扫描的对象数量添加到全局
        if gcw.scanWork > 0 {
            atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
            // 减少辅助GC的工作量和唤醒等待中的G
            if flushBgCredit {
                gcFlushBgCredit(gcw.scanWork - initScanWork)
            }
            gcw.scanWork = 0
        }
    }

func gcMarkDone() {
        semacquire(&work.markDoneSema)
    
        // Re-check transition condition under transition lock.
        if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
            semrelease(&work.markDoneSema)
            return
        }
    
        // 暂时禁止启动新的后台标记任务
        atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff)
        prevFractionalGoal := gcController.fractionalUtilizationGoal
        gcController.fractionalUtilizationGoal = 0
        // 转换到Mark Termination阶段，进入STW阶段
        systemstack(stopTheWorldWithSema)
        // 标记对根对象的扫描已完成
        work.markrootDone = true
        // 禁止辅助GC和后台任务
        atomic.Store(&gcBlackenEnabled, 0)
        // 唤醒所有因为辅助GC而休眠的G
        gcWakeAllAssists()
    
        semrelease(&work.markDoneSema)
        // 计算下一次触发gc需要的heap大小
        nextTriggerRatio := gcController.endCycle()
    
        // 计算下一次触发gc需要的heap大小
        gcMarkTermination(nextTriggerRatio)
    }

func gcMarkTermination(nextTriggerRatio float64) {
        // 禁止辅助GC和后台标记任务的运行
        // 重新允许本地标记队列(下次GC使用)
        // 设置当前GC阶段到完成标记阶段, 并启用写屏障
        atomic.Store(&gcBlackenEnabled, 0)
        gcBlackenPromptly = false
        setGCPhase(_GCmarktermination)
    
        systemstack(func() {gcMark(startTime)})
    
        systemstack(func() {
            // 设置当前GC阶段到关闭, 并禁用写屏障
            setGCPhase(_GCoff)
            // 唤醒后台清扫任务, 将在STW结束后开始运行
            gcSweep(work.mode)
        })
        
        // 更新下一次触发gc需要的heap大小(gc_trigger)
        gcSetTriggerRatio(nextTriggerRatio)
    
        // 重置清扫状态
        sweep.nbgsweep = 0
        sweep.npausesweep = 0
    
        // 统计执行GC的次数然后唤醒等待清扫的G
        lock(&work.sweepWaiters.lock)
        memstats.numgc++
        injectglist(work.sweepWaiters.head.ptr())
        work.sweepWaiters.head = 0
        unlock(&work.sweepWaiters.lock)
        
        // 重新启动世界
        systemstack(func() { startTheWorldWithSema(true) })
        // 移动标记队列使用的缓冲区到自由列表, 使得它们可以被回收
        prepareFreeWorkbufs()
        // 释放未使用的栈
        systemstack(freeStackSpans)
       
        semrelease(&worldsema)
        // 重新允许当前的G被抢占
        releasem(mp)
        mp = nil

当标记的扫描工作完成之后，会进入到GC Mark Termination阶段，也就是gcMarkDone()函数，关键路径：

1.  **systemstack(stopTheWorldWithSema)：启动STW**
2.  gcWakeAllAssists()：唤醒所有因辅助gc而休眠的G
3.  nextTriggerRatio:=gcController.endCycle()：计算下一次触发gc需要的heap大小
4.  setGCPhase(\_GCmarktermination)：启用写屏障
5.  systemstack(func() \{gcMark(startTime)\})： 再次执行标记
6.  systemstack(func()\{setGCPhase(\_GCoff)；gcSweep(work.mode)\})：关闭写屏障，唤醒后台清扫任务，将在STW结束后开始运行
7.  gcSetTriggerRatio(nextTriggerRatio)：更新下次触发gc时的heap大小
8.  **systemstack(func() \{ startTheWorldWithSema(true) \}): 停止STW**

## STW分析：web程序中，我们关注最大停顿时间 ##

STW出现在两个位置，分别是在初始标记阶段Mark和并发标记完成后重标记Mark Termination:

### 初始标记阶段： ###

*  **systemstack(stopTheWorldWithSema):启动stop the world**
 *  systemstack(func()\{finishsweep\_m()\}): 不断去除要清理的span进行清理，然后重置gcmark位
 *  clearpools(): 清扫sched.sudogcache和sched.deferpool，不知道在干嘛......
 *  gcController.startCycle():启动新一轮GC，设置gc controller的状态位和计算一些估计值
 *  gcMarkRootPrepare(): 计算扫描根对象的任务数量
 *  gcMarkTinyAllocs(): 涂灰所有tiny alloc等待合并的对象
 *  **systemstack(func()\{now=startTheWorldWithSema(trace.enable)\}): 停止stop the world**

找出其中比较耗时的阶段：

*  finishsweep\_m():如果上一次GC清扫阶段没有完成，那么在新的一轮GC阶段中就会在阻塞在这里，使得原本可以和应用程序并行的清扫阶段被放进STW。所以，如果频繁的执行GC，就可能会使得GC的最大停顿时间变长。
 *  clearpools():时间复杂度大概为：O(5\*L),L为\_defer中链表的长度。
 *  gcController.startCycle():O(P)，P为go的P的数量，和cpu数有关，时间复杂度可以忽略
 *  gcMarkRootPrepare(): O(全局变量区)，包括bss段和data段
 *  gcMarkTinyAllocs(): O(P)

个人觉得，对STW影响最大的是finishsweep\_m()阶段，所有我们应该尽量避免让go在清扫期执行新一轮的GC。

### 重新标记阶段 ###

*  **systemstack(stopTheWorldWithSema)：启动STW**
 *  gcWakeAllAssists()：唤醒所有因辅助gc而休眠的G
 *  nextTriggerRatio:=gcController.endCycle()：计算下一次触发gc需要的heap大小
 *  setGCPhase(\_GCmarktermination)：启用写屏障
 *  systemstack(func() \{gcMark(startTime)\})： 再次执行标记
 *  systemstack(func()\{setGCPhase(\_GCoff)；gcSweep(work.mode)\})：关闭写屏障，唤醒后台清扫任务，将在STW结束后开始运行
 *  gcSetTriggerRatio(nextTriggerRatio)：更新下次触发gc时的heap大小
 *  **systemstack(func() \{ startTheWorldWithSema(true) \}): 停止STW**

找出其中比较耗时的阶段：

*  gcWakeAllAssists()：O(G)，将所有可运行的G插入到调度链表
 *  systemstack(func() \{gcMark(startTime)\})：

[1036501-0d3bcaade977a46f.jpg]: /images/20220203/66f01576c7054dac828ca944e16d547f.png