Golang GC算法

概括

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

   
   
   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)}):

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传