通常C++通过指针引用计数来回收对象,但是这不能处理循环引用。为了避免引用计数的缺陷,后来出现了标记清除,分代等垃圾回收算法。Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 并发标记清理。标记清理算法的字面解释,就是将可达的内存块进行标记mark,最后没有标记的不可达内存块将进行清理sweep。
三色标记法
判断一个对象是不是垃圾需不需要标记,就看是否能从当前栈或全局数据区 直接或间接的引用到这个对象。这个初始的当前goroutine的栈和全局数据区称为GC的root区。扫描从这里开始,通过markroot将所有root区域的指针标记为可达,然后沿着这些指针扫描,递归地标记遇到的所有可达对象。因此引出几个问题:
- 标记清理能不能与用户代码并发
- 如何获得对象的类型而找到所有可达区域 标记位记录在哪里
- 何时触发标记清理
如何并发标记
标记清扫算法在标记和清理时需要停止所有的goroutine,来保证已经被标记的区域不会被用户修改引用关系,造成清理错误。但是每次GC都要StopTheWorld显然是不能接受的。Go的各个版本为减少STW做了各种努力。从Go1.5开始采用三色标记法实现标记阶段的并发。
- 最开始所有对象都是白色
- 扫描所有可达对象,标记为灰色,放入待处理队列
- 从队列提取灰色对象,将其引用对象标记为灰色放入队列,自身标记为黑色
- 写屏障监控对象内存修改,重新标色或是放入队列
完成标记后 对象不是白色就是黑色,清理操作只需要把白色对象回收内存回收就好。
大概理解所谓并发标记,首先是指能够跟用户代码并发的进行,其次是指标记工作不是递归地进行,而是多个goroutine并发的进行。前者通过write-barrier解决并发问题,后者通过gc-work队列实现非递归地mark可达对象。
write-barrier
用下面这个例子解释并发带来的问题,原文引用自CMS垃圾回收器原理。当从A这个GC root找到引用对象B时,B变灰A变黑。这时用户goroutine执行把A到B的引用改成了A到C的引用,同时B不再引用C。然后GC goroutine又执行,发现B没有引用对象,B变黑。而这时由于A已经变黑完成了扫描,C将当做白色不可达对象被清除。
解决办法:引入写屏障。当发现A已经标记为黑色了,若A又引用C,那么把C变灰入队。这个write_barrier是编译器在每一处内存写操作前生成一小段代码来做的。
// 写屏障伪代码
write_barrier(obj,field,newobj){
if(newobj.mark == FALSE){
newobj.mark = TRUE
push(newobj,$mark_stack)
}
*field = newobj
}
gc-work
如何非递归的实现遍历mark可达节点,显然需要一个队列。
这个队列也帮助区分黑色对象和灰色对象,因为标记位只有一个。标记并且在队列中的是灰色对象,标记了但是不在队列中的黑色对象,末标记的是白色对象。
root node queue
while(queue is not nil) {
dequeue // 节点出队
process // 处理当前节点
child node queue // 子节点入队
}
总结一下并发标记的过程:
gcstart启动阶段准备了N个goMarkWorkers。每个worker都处理以下相同流程。- 如果是第一次mark则首先
markroot将所有root区的指针入队。 - 从gcw中取节点出对开始扫描处理
scanobject,节点出队列就是黑色了。 - 扫描时获取该节点所有子节点的类型信息判断是不是指针,若是指针且并没有被标记则
greyobject入队。 - 每个worker都去gcw中拿任务直到为空break。
// 每个markWorker都执行gcDrain这个标记过程
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
// 如果还没有root区域入队则markroot
markroot(gcw, job)
if idle && pollWork() {
goto done
}
// 节点出队
b = gcw.get()
scanobject(b, gcw)
done:
}
func scanobject(b uintptr, gcw *gcWork) {
hbits := heapBitsForAddr(b)
s := spanOfUnchecked(b)
n := s.elemsize
for i = 0; i < n; i += sys.PtrSize { // Find bits for this word. if bits&bitPointer == 0 { continue // not a pointer } .... // Mark the object. if obj, hbits, span, objIndex := heapBitsForObject(obj, b, i); obj != 0 { greyobject(obj, b, i, hbits, span, gcw, objIndex) } } gcw.bytesMarked += uint64(n) gcw.scanWork += int64(i) } func greyobject(obj, base, off uintptr, hbits heapBits, span *mspan, gcw *gcWork, objIndex uintptr) { mbits := span.markBitsForIndex(objIndex) // If marked we have nothing to do. if mbits.isMarked() { return } if !hbits.hasPointers(span.elemsize) { return } gcw.put(obj) } 标记位
实现精确地垃圾回收的前提,就是能获得对象区域的类型信息,从而判断是否是指针。如何判断,最后又把可达标记记在哪里:通过堆区arena前面对应的bitmap。
结构体中不包含指针,其实不需要递归地标记结构体成员。如果没有类型信息只能对所有的结构体成员递归地标记下去。还有如果非指针成员刚好存储的内容对应着合法地址,那这个地址的对象就会碰巧被标记,导致无法回收。
这个bitmap位图区域每个字(32位或64位)会对应4位的标记位。heapBitsForAddr可以获取对应堆地址的bitmap位hbits,根据它可以判断是否是指针,如果是指针且之前没有被标记过,则mark当前对象为可达,并且greayObject入队,供给其他的markWorker来处理。
// 获取b对应的bitmap位图
obj, hbits, span, objIndex := heapBitsForObject(obj, b, i)
mbits := span.markBitsForIndex(objIndex)
// 判断是否被标记过 已标记或不是指针都不入队
mbits.isMarked()
hbits.hasPointers(span.elemsize)
gc_trigger最开始是4MB,next_gc初始为4MB,之后每次标记完成时将重新计算动态调整值大小。但gc_trigger至少要大于初始的4MB,同时至少要比当前使用的heap大1MB。
gcmark在每次标记结束后重置阈值大小。当前使用了4MB内存,这时设置gc_trigger为2*4MB,也就是当内存分配到8MB时会再次触发GC。回收之后内存为5MB,那下一次要达到10MB才会触发GC。这个比例triggerRatio是由gcpercent/100决定的。
func gcinit() {
_ = setGCPercent(readgogc())
memstats.gc_trigger = heapminimum
memstats.next_gc = uint64(float64(memstats.gc_trigger) / (1 +
gcController.triggerRatio) * (1 + float64(gcpercent)/100))
work.startSema = 1
work.markDoneSema = 1
}
func gcMark() {
memstats.gc_trigger = uint64(float64(memstats.heap_marked) *
(1 + gcController.triggerRatio))
}
强制垃圾回收
如果系统启动或短时间内大量分配对象,会将垃圾回收的gc_trigger推高。当服务正常后,活跃对象远小于这个阈值,造成垃圾回收无法触发。这个问题交给sysmon解决。它每隔2分钟force触发GC一次。这个forcegc的goroutine一直park在后台,直到sysmon将它唤醒开始执行gc而不用检查阈值。
// proc.go
var forcegcperiod int64 = 2 * 60 * 1e9
func init() { go forcegchelper()}
func sysmon() {
lastgc := int64(atomic.Load64(&memstats.last_gc))
if gcphase == _GCoff && lastgc != 0 &&
unixnow-lastgc> forcegcperiod &&
atomic.Load(&forcegc.idle) != 0 {
injectglist(forcegc.g)
}
}
func forcegchelper() {
for {
goparkunlock(&forcegc.lock, "force gc (idle)", traceEvGoBlock, 1)
gcStart(gcBackgroundMode, true)
}
}
标记与清理过程
这里结合gc-work那一节从头梳理一下gc的启动和流程。下面这个图总结了mark-sweep所有的状态变化。在代码里只有三个GC状态,分别对应这几个阶段。总结两个问题:
- 为什么markTermination需要rescan全局指针和栈。因为mark阶段是跟用户代码并发的,所以有可能栈上都分了新的对象,这些对象通过write barrier记录下来,在rescan的时候再检查一遍。
- 为什么还需要两个stopTheWorld 在GCtermination时需要STW不然永远都可能栈上出现新对象。在GC开始之前做准备工作(比如 enable write barrier)的时候也要STW。
- Off:
_GCoff- Stack scan + Mark:
_GCmark- Mark termination: _GCmarktermination
Goff to Gmark
gcstart由每次mallocgc触发,当然要满足gc_trriger等阈值条件才触发。整个启动过程都是STW的,它启动了所有将并发执行标记工作的goroutine,然后进入GCMark状态使能写屏障,启动gcController。
func gcStart(mode gcMode, forceTrigger bool) {
// 启动MarkStartWorkers的goroutine
if mode == gcBackgroundMode {
gcBgMarkStartWorkers()
}
gcResetMarkState()
systemstack(stopTheWorldWithSema)
// 完成之前的清理工作
systemstack(func() {
finishsweep_m()
})
// 进入Mark状态 使能写屏障
if mode == gcBackgroundMode {
gcController.startCycle()
setGCPhase(_GCmark)
gcBgMarkPrepare()
gcMarkRootPrepare()
atomic.Store(&gcBlackenEnabled, 1)
systemstack(startTheWorldWithSema)
}
}
Gmark
解释一下gcMarkWorker跟gcController的关系。gcstart中只是为所有的P都准备好对应的goroutine来做标记。但是他们一开始就gopark住当前G,直到被gccontroller的findRunnableGCWorker唤醒。goroutine源码记录讲了goroutine的过程,m启动后会一直通过schedule查找可执行的G,其中gcworker也是G的来源,但是首先要检查当前状态是不是Gmark。如果是就唤醒worker开始标记工作。
func gcBgMarkStartWorkers() {
for _, p := range &allp {
go gcBgMarkWorker(p)
notetsleepg(&work.bgMarkReady, -1)
noteclear(&work.bgMarkReady)
}
}
func schedule() {
...//schedule优先唤醒markworkerG 但首先gcBlackenEnabled != 0
if gp == nil && gcBlackenEnabled != 0 {
gp = gcController.findRunnableGCWorker(_g_.m.p.ptr())
}
}
唤醒后开始进入mark标记工作gcDrain。gc-work那一节讲了并发标记的过程,这里不重复。总结来说就是每个worker都去队列中拿节点(黑化节点),然后处理当前节点看有没有指针和没标记的对象,继续入队子节点(灰化节点),直到队列为空再也找不到可达对象。
func gcBgMarkWorker(_p_ *p) {
notewakeup(&work.bgMarkReady)
for {
gopark(func(g *g, parkp unsafe.Pointer) bool {
}, unsafe.Pointer(park), "GC worker (idle)", traceEvGoBlock, 0)
systemstack(func() {
casgstatus(gp, _Grunning, _Gwaiting)
gcDrain(&_p_.gcw, ...)
casgstatus(gp, _Gwaiting, _Grunning)
})
// 标记完成gcMarkDone()
if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
gcMarkDone()
}
}
}
Gmarktermination
mark结束后调用gcMarkDone,它主要是StopTheWorld然后进入gcMarkTermination中的gcMark。大概是做了rescan root区域的工作,但是看到有博客说Go1.8已经没有再rescan了,细节没看懂,代码里看起来却是又重新扫描了一次啊。
func gcMarkTermination() {
atomic.Store(&gcBlackenEnabled, 0)
setGCPhase(_GCmarktermination)
casgstatus(gp, _Grunning, _Gwaiting)
gp.waitreason = "garbage collection"
systemstack(func() {
gcMark(startTime)
setGCPhase(_GCoff)
gcSweep(work.mode)
})
casgstatus(gp, _Gwaiting, _Grunning)
systemstack(startTheWorldWithSema)
}
func gcMark(start_time int64) {
gcMarkRootPrepare()
gchelperstart()
gcDrain(gcw, gcDrainBlock)
gcw.dispose()
// gc结束后重置gc_trigger等阈值
...
}
Gsweep
有多个地方可以触发sweep,比如GC标记结束会触发gcsweep。如果是并发清除,需要回收从gc_trigger到当前活跃内存的那么多heap区域,唤醒后台的sweep goroutine。
func gcSweep(mode gcMode) {
lock(&mheap_.lock)
mheap_.sweepgen += 2
mheap_.sweepdone = 0
unlock(&mheap_.lock)
// Background sweep.
ready(sweep.g, 0, true)
}
// 在runtime初始化时进行gcenable
func gcenable() {
go bgsweep(c)
}
func bgsweep(c chan int) {
goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
for {
for gosweepone() != ^uintptr(0) {
sweep.nbgsweep++
Gosched()
}
goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
}
}
也就是系统初始化的时候开启了后台的bgsweep goroutine。这个G也是一进去就park了,唤醒后执行gosweepone。seepone的过程大概是:遍历所有的spans看它的sweepgen是否需要检查,如果要就检查这个mspan里所有的object的bit位看是否需要回收。这个过程可能触发mspan到mcentral的回收,最终可能回收到mheap的freelist当中。在freelist当中的内存再超过一定阈值时间后会被sysmon建议交还给内核。