概括
Go的垃圾回收官方形容為 非分代 非緊縮 寫屏障 三色并發(fā)標(biāo)記清理算法。
非分代：不像Java那樣分為年輕代和年老代，自然也沒有minor gc和maj o gc的區(qū)別。
非緊縮：在垃圾回收之后不會進(jìn)行內(nèi)存整理以清除內(nèi)存碎片。
寫屏障：在并發(fā)標(biāo)記的過程中，如果應(yīng)用程序（mutator）修改了對象圖，就可能出現(xiàn)標(biāo)記遺漏的可能，寫屏障就是為了處理標(biāo)記遺漏的問題。
三色：將GC中的對象按照搜索的情況分成三種：
- 黑色: 對象在這次GC中已標(biāo)記,且這個對象包含的子對象也已標(biāo)記
- 灰色: 對象在這次GC中已標(biāo)記, 但這個對象包含的子對象未標(biāo)記
- 白色: 對象在這次GC中未標(biāo)記
并發(fā)：可以和應(yīng)用程序（mutator）在一定程度上并發(fā)執(zhí)行。
標(biāo)記清理：GC算法分為兩個大步驟：標(biāo)記階段找出要回收的對象，清理階段則回收未被標(biāo)記的對象（要被回收的對象）
觸發(fā)時機(jī)
- gcTriggerAlways: 強(qiáng)制觸發(fā)GC，沒找到什么情況下使用這個
- gcTriggerHeap: 當(dāng)前分配的內(nèi)存達(dá)到一定值（動態(tài)計(jì)算）就觸發(fā)GC
- gcTriggerTime: 當(dāng)一定時間（2分鐘）沒有執(zhí)行過GC就觸發(fā)GC
- gcTriggerCycle: 要求啟動新一輪的GC, 已啟動則跳過, 手動觸發(fā)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()構(gòu)成雙檢查鎖，如果滿足GC條件但目前處于GC清理階段，那就參與清理
for trigger.test() && gosweepone() != ^uintptr(0) {
sweep.nbgsweep++
}
// 加鎖檢查
semacquire(&work.startSema)
if !trigger.test() {
semrelease(&work.startSema)
return
}
/*************** ..... *****************/
}
在trigger.test()函數(shù)中，檢查是否滿足GC觸發(fā)的條件
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
)
算法過程
- Sweep Termination: 對未清掃的span進(jìn)行清掃, 只有上一輪的GC的清掃工作完成才可以開始新一輪的GC
- Mark: 掃描所有根對象, 和根對象可以到達(dá)的所有對象, 標(biāo)記它們不被回收
- Mark Termination: 完成標(biāo)記工作, 重新掃描部分根對象(要求STW)
-
Sweep: 按標(biāo)記結(jié)果清掃span
golang_gc.jpg
func gcStart(mode gcMode, trigger gcTrigger) {
// 拿到鎖，保證只有一個執(zhí)行流進(jìn)入到這個臨界區(qū)
semacquire(&worldsema)
// 啟動后臺掃描任務(wù)(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)
}
關(guān)鍵函數(shù)及路徑：
- gcBgMarkStartWorkers():準(zhǔn)備后臺標(biāo)記工作goroutine（allp）， 啟動后等待該任務(wù)通知信號量bgMarkReady再繼續(xù)，notewakeup(&work.bgMarkReady)
- gcResetMarkState():重置一些全局狀態(tài)和所有g(shù)orontine的棧（一種根對象）掃描狀態(tài)
- systemstack(stopTheWorldWithSema):啟動stop the world
- systemstack(func(){finishsweep_m()}): 不斷去除要清理的span進(jìn)行清理，然后重置gcmark位
- clearpools(): 清掃sched.sudogcache和sched.deferpool，不知道在干嘛......
- gcController.startCycle():啟動新一輪GC，設(shè)置gc controller的狀態(tài)位和計(jì)算一些估計(jì)值
- setGCPhase(_GCmark):設(shè)置GC階段，啟用寫屏障
- gcBgMarkPrepare():設(shè)置后臺標(biāo)記任務(wù)計(jì)數(shù)；work.nproc = ^uint32(0)，work.nwait = ^uint32(0)
- gcMarkRootPrepare(): 計(jì)算掃描根對象的任務(wù)數(shù)量
- gcMarkTinyAllocs(): 標(biāo)記所有tiny alloc等待合并的對象
- atomic.Store(&gcBlackenEnabled, 1): 啟用輔助GC
- systemstack(func(){now=startTheWorldWithSema(trace.enable)}): 停止stop the world
func gcBgMarkWorker(_p_ *p) {
/********** ....... ***********/
// 通知gcBgMarkStartWorkers可以繼續(xù)處理
notewakeup(&work.bgMarkReady)
for {
// 切換到g0運(yùn)行
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)
})
/******** ...... ***********/
// 判斷是否所有后臺標(biāo)記任務(wù)都完成, 并且沒有更多的任務(wù)
if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
gcMarkDone()
}
}
}
- gcDrain()是執(zhí)行標(biāo)記的函數(shù)
- 當(dāng)所有標(biāo)記任務(wù)完成時，執(zhí)行g(shù)cMarkDone()函數(shù)
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
initScanWork := gcw.scanWork
// 如果根對象未掃描完，則先掃描根對象，Jobs為根對象總數(shù)，next相當(dāng)于一個對象任務(wù)的取數(shù)器
if work.markrootNext < work.markrootJobs {
for !(preemptible && gp.preempt) {
job := atomic.Xadd(&work.markrootNext, +1) - 1
if job >= work.markrootJobs {
break
}
// 將會掃描根對象，并把它加入到標(biāo)記隊(duì)列g(shù)cWork中之中，也就是把對象變成灰色
markroot(gcw, job)
if check != nil && check() {
goto done
}
}
}
// 當(dāng)根對象全部put到標(biāo)記隊(duì)列中, 消費(fèi)標(biāo)記隊(duì)列，根據(jù)對象圖進(jìn)行消費(fèi)
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)
// 如果已經(jīng)掃描了一定數(shù)量的對象(gcCreditSlack的值是2000)
if gcw.scanWork >= gcCreditSlack {
// 把掃描的對象數(shù)量添加到全局
atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
// 減少輔助GC的工作量和喚醒等待中的G
if flushBgCredit {
gcFlushBgCredit(gcw.scanWork - initScanWork)
initScanWork = 0
}
idleCheck -= gcw.scanWork
gcw.scanWork = 0
// 如果是idle模式且達(dá)到了檢查的掃描量, 則檢查是否有其他任務(wù)(G), 如果有則跳出循環(huán)
if idle && idleCheck <= 0 {
idleCheck += idleCheckThreshold
if pollWork() {
break
}
}
}
}
done:
// 把掃描的對象數(shù)量添加到全局
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
}
// 暫時禁止啟動新的后臺標(biāo)記任務(wù)
atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff)
prevFractionalGoal := gcController.fractionalUtilizationGoal
gcController.fractionalUtilizationGoal = 0
// 轉(zhuǎn)換到Mark Termination階段，進(jìn)入STW階段
systemstack(stopTheWorldWithSema)
// 標(biāo)記對根對象的掃描已完成
work.markrootDone = true
// 禁止輔助GC和后臺任務(wù)
atomic.Store(&gcBlackenEnabled, 0)
// 喚醒所有因?yàn)檩o助GC而休眠的G
gcWakeAllAssists()
semrelease(&work.markDoneSema)
// 計(jì)算下一次觸發(fā)gc需要的heap大小
nextTriggerRatio := gcController.endCycle()
// 計(jì)算下一次觸發(fā)gc需要的heap大小
gcMarkTermination(nextTriggerRatio)
}
func gcMarkTermination(nextTriggerRatio float64) {
// 禁止輔助GC和后臺標(biāo)記任務(wù)的運(yùn)行
// 重新允許本地標(biāo)記隊(duì)列(下次GC使用)
// 設(shè)置當(dāng)前GC階段到完成標(biāo)記階段, 并啟用寫屏障
atomic.Store(&gcBlackenEnabled, 0)
gcBlackenPromptly = false
setGCPhase(_GCmarktermination)
systemstack(func() {gcMark(startTime)})
systemstack(func() {
// 設(shè)置當(dāng)前GC階段到關(guān)閉, 并禁用寫屏障
setGCPhase(_GCoff)
// 喚醒后臺清掃任務(wù), 將在STW結(jié)束后開始運(yùn)行
gcSweep(work.mode)
})
// 更新下一次觸發(fā)gc需要的heap大小(gc_trigger)
gcSetTriggerRatio(nextTriggerRatio)
// 重置清掃狀態(tài)
sweep.nbgsweep = 0
sweep.npausesweep = 0
// 統(tǒng)計(jì)執(zhí)行GC的次數(shù)然后喚醒等待清掃的G
lock(&work.sweepWaiters.lock)
memstats.numgc++
injectglist(work.sweepWaiters.head.ptr())
work.sweepWaiters.head = 0
unlock(&work.sweepWaiters.lock)
// 重新啟動世界
systemstack(func() { startTheWorldWithSema(true) })
// 移動標(biāo)記隊(duì)列使用的緩沖區(qū)到自由列表, 使得它們可以被回收
prepareFreeWorkbufs()
// 釋放未使用的棧
systemstack(freeStackSpans)
semrelease(&worldsema)
// 重新允許當(dāng)前的G被搶占
releasem(mp)
mp = nil
當(dāng)標(biāo)記的掃描工作完成之后，會進(jìn)入到GC Mark Termination階段，也就是gcMarkDone()函數(shù)，關(guān)鍵路徑：
- systemstack(stopTheWorldWithSema)：啟動STW
- gcWakeAllAssists()：喚醒所有因輔助gc而休眠的G
- nextTriggerRatio:=gcController.endCycle()：計(jì)算下一次觸發(fā)gc需要的heap大小
- setGCPhase(_GCmarktermination)：啟用寫屏障
- systemstack(func() {gcMark(startTime)})： 再次執(zhí)行標(biāo)記
- systemstack(func(){setGCPhase(_GCoff)；gcSweep(work.mode)})：關(guān)閉寫屏障，喚醒后臺清掃任務(wù)，將在STW結(jié)束后開始運(yùn)行
- gcSetTriggerRatio(nextTriggerRatio)：更新下次觸發(fā)gc時的heap大小
- systemstack(func() { startTheWorldWithSema(true) }): 停止STW
STW分析：web程序中，我們關(guān)注最大停頓時間
STW出現(xiàn)在兩個位置，分別是在初始標(biāo)記階段Mark和并發(fā)標(biāo)記完成后重標(biāo)記Mark Termination:
初始標(biāo)記階段：
- systemstack(stopTheWorldWithSema):啟動stop the world
- systemstack(func(){finishsweep_m()}): 不斷去除要清理的span進(jìn)行清理，然后重置gcmark位
- clearpools(): 清掃sched.sudogcache和sched.deferpool，不知道在干嘛......
- gcController.startCycle():啟動新一輪GC，設(shè)置gc controller的狀態(tài)位和計(jì)算一些估計(jì)值
- gcMarkRootPrepare(): 計(jì)算掃描根對象的任務(wù)數(shù)量
- gcMarkTinyAllocs(): 涂灰所有tiny alloc等待合并的對象
- systemstack(func(){now=startTheWorldWithSema(trace.enable)}): 停止stop the world
找出其中比較耗時的階段：
- finishsweep_m():如果上一次GC清掃階段沒有完成，那么在新的一輪GC階段中就會在阻塞在這里，使得原本可以和應(yīng)用程序并行的清掃階段被放進(jìn)STW。所以，如果頻繁的執(zhí)行GC，就可能會使得GC的最大停頓時間變長。
- clearpools():時間復(fù)雜度大概為：O(5*L),L為_defer中鏈表的長度。
- gcController.startCycle():O(P)，P為go的P的數(shù)量，和cpu數(shù)有關(guān)，時間復(fù)雜度可以忽略
- gcMarkRootPrepare(): O(全局變量區(qū))，包括bss段和data段
- gcMarkTinyAllocs(): O(P)
個人覺得，對STW影響最大的是finishsweep_m()階段，所有我們應(yīng)該盡量避免讓go在清掃期執(zhí)行新一輪的GC。
重新標(biāo)記階段
- systemstack(stopTheWorldWithSema)：啟動STW
- gcWakeAllAssists()：喚醒所有因輔助gc而休眠的G
- nextTriggerRatio:=gcController.endCycle()：計(jì)算下一次觸發(fā)gc需要的heap大小
- setGCPhase(_GCmarktermination)：啟用寫屏障
- systemstack(func() {gcMark(startTime)})： 再次執(zhí)行標(biāo)記
- systemstack(func(){setGCPhase(_GCoff)；gcSweep(work.mode)})：關(guān)閉寫屏障，喚醒后臺清掃任務(wù)，將在STW結(jié)束后開始運(yùn)行
- gcSetTriggerRatio(nextTriggerRatio)：更新下次觸發(fā)gc時的heap大小
- systemstack(func() { startTheWorldWithSema(true) }): 停止STW
找出其中比較耗時的階段：
- gcWakeAllAssists()：O(G)，將所有可運(yùn)行的G插入到調(diào)度鏈表
- systemstack(func() {gcMark(startTime)})：
