Golang 从第一个版本以来,GC 一直是大家诟病最多的。但是每一个版本的发布基本都伴随着 GC 的改进。下面列出一些比较重要的改动。
v1.1 STW
v1.3 Mark STW, Sweep 并行
v1.5 三色标记法
v1.8 hybrid write barrier
引用计数(reference counting)
标记-清扫(mark & sweep)
节点复制(Copying Garbage Collection)
分代收集(Generational Garbage Collection)
引用计数的思想非常简单:每个单元维护一个域,保存其它单元指向它的引用数量(类似有向图的入度)。当引用数量为 0 时,将其回收。引用计数是渐进式的,能够将内存管理的开销分布到整个程序之中。C++ 的 share_ptr 使用的就是引用计算方法。
引用计数算法实现一般是把所有的单元放在一个单元池里,比如类似 free list。这样所有的单元就被串起来了,就可以进行引用计数了。新分配的单元计数值被设置为 1(注意不是 0,因为申请一般都说 ptr = new object 这种)。每次有一个指针被设为指向该单元时,该单元的计数值加 1;而每次删除某个指向它的指针时,它的计数值减 1。当其引用计数为 0 的时候,该单元会被进行回收。虽然这里说的比较简单,实现的时候还是有很多细节需要考虑,比如删除某个单元的时候,那么它指向的所有单元都需要对引用计数减 1。那么如果这个时候,发现其中某个指向的单元的引用计数又为 0,那么是递归的进行还是采用其他的策略呢?递归处理的话会导致系统颠簸。关于这些细节这里就不讨论了,可以参考文章后面的给的参考资料。
优点
渐进式。内存管理与用户程序的执行交织在一起,将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World,GC 的时候挂起用户程序)。
算法易于实现。
内存单元能够很快被回收。相比于其他垃圾回收算法,堆被耗尽或者达到某个阈值才会进行垃圾回收。
缺点
原始的引用计数不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题,也除了很多解决方案,比如强引用等。
维护引用计数降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数,相比于一些追踪式的垃圾回收算法并不需要这些代价。
单元池 free list 实现的话不是 cache-friendly 的,这样会导致频繁的 cache miss,降低程序运行效率。
标记-清扫算法
标记-清扫算法的优点也就是基于追踪的垃圾回收算法具有的优点:避免了引用计数算法的缺点(不能处理循环引用,需要维护指针)。缺点也很明显,需要 STW。
三色标记算法
三色标记算法是对标记阶段的改进,原理如下:
起初所有对象都是白色。
从根出发扫描所有可达对象,标记为灰色,放入待处理队列。
从队列取出灰色对象,将其引用对象标记为灰色放入队列,自身标记为黑色。
重复 3,直到灰色对象队列为空。此时白色对象即为垃圾,进行回收。
可视化如下。
三色标记算法
三色标记的一个明显好处是能够让用户程序和 mark 并发的进行,具体可以参考论文:《On-the-fly garbage collection: an exercise in cooperation.》。Golang 的 GC 实现也是基于这篇论文,后面再具体说明。
优点
所有存活的数据结构都缩并地排列在 Tospace 的底部,这样就不会存在内存碎片的问题。
获取新内存可以简单地通过递增自由空间指针来实现。
缺点
内存得不到充分利用,总有一半的内存空间处于浪费状态。
分配对象的时候从新生代里面分配,如果后面发现对象的生命周期较长,则将其移到老年代,这个过程叫做 promote。随着不断 promote,最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高,STW 时间也会更短。
优点
性能更优。
缺点
实现复杂
7.1 Overview
在说 Golang 的具体垃圾回收流程时,我们先来看一下几个基本的问题。
1. 何时触发 GC
在堆上分配大于 32K byte 对象的时候进行检测此时是否满足垃圾回收条件,如果满足则进行垃圾回收。
View Code
上面是自动垃圾回收,还有一种是主动垃圾回收,通过调用 runtime.GC(),这是阻塞式的。
View Code
2. GC 触发条件
触发条件主要关注下面代码中的中间部分:forceTrigger || memstats.heap_live >= memstats.gc_trigger 。forceTrigger 是 forceGC 的标志;后面半句的意思是当前堆上的活跃对象大于我们初始化时候设置的 GC 触发阈值。在 malloc 以及 free 的时候 heap_live 会一直进行更新,这里就不再展开了。
View Code
3. 垃圾回收的主要流程
三色标记法,主要流程如下:
所有对象最开始都是白色。
从 root 开始找到所有可达对象,标记为灰色,放入待处理队列。
遍历灰色对象队列,将其引用对象标记为灰色放入待处理队列,自身标记为黑色。
处理完灰色对象队列,执行清扫工作。
详细的过程如下图所示,具体可参考 [9]。
关于上图有几点需要说明的是。
首先从 root 开始遍历,root 包括全局指针和 goroutine 栈上的指针。
mark 有两个过程。
从 root 开始遍历,标记为灰色。遍历灰色队列。
re-scan 全局指针和栈。因为 mark 和用户程序是并行的,所以在过程 1 的时候可能会有新的对象分配,这个时候就需要通过写屏障(write barrier)记录下来。re-scan 再完成检查一下。
Stop The World 有两个过程。
第一个是 GC 将要开始的时候,这个时候主要是一些准备工作,比如 enable write barrier。
第二个过程就是上面提到的 re-scan 过程。如果这个时候没有 stw,那么 mark 将无休止。
另外针对上图各个阶段对应 GCPhase 如下:
Off: _GCoff
Stack scan ~ Mark: _GCmark
Mark termination: _GCmarktermination
7.2 写屏障 (write barrier)
关于 write barrier,完全可以另外写成一篇文章,所以这里只简单介绍一下,这篇文章的重点还是 Golang 的 GC。垃圾回收中的 write barrier 可以理解为编译器在写操作时特意插入的一段代码,对应的还有 read barrier。
为什么需要 write barrier,很简单,对于和用户程序并发运行的垃圾回收算法,用户程序会一直修改内存,所以需要记录下来。
Golang 1.7 之前的 write barrier 使用的经典的 Dijkstra-style insertion write barrier [Dijkstra ‘78], STW 的主要耗时就在 stack re-scan 的过程。自 1.8 之后采用一种混合的 write barrier 方式 (Yuasa-style deletion write barrier [Yuasa ‘90] 和 Dijkstra-style insertion write barrier [Dijkstra ‘78])来避免 re-scan。具体的可以参考 17503-eliminate-rescan。
7.3 标记
下面的源码还是基于 go1.8rc3。这个版本的 GC 代码相比之前改动还是挺大的,我们下面尽量只关注主流程。垃圾回收的代码主要集中在函数 gcStart() 中。
// gcStart 是 GC 的入口函数,根据 gcMode 做处理。
// 1. gcMode == gcBackgroundMode(后台运行,也就是并行), _GCoff -> _GCmark
// 2. 否则 GCoff -> _GCmarktermination,这个时候就是主动 GC
func gcStart(mode gcMode, forceTrigger bool) {
…
}
1. STW phase 1
在 GC 开始之前的准备工作。
func gcStart(mode gcMode, forceTrigger bool) {
…
//在后台启动 mark worker
if mode == gcBackgroundMode {
gcBgMarkStartWorkers()
}
…
// Stop The World
systemstack(stopTheWorldWithSema)
…
if mode == gcBackgroundMode {
// GC 开始前的准备工作
//处理设置 GCPhase,setGCPhase 还会 enable write barrier
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()
// Start The World
systemstack(startTheWorldWithSema)
} else {
...
} } 2. Mark Mark 阶段是并行的运行,通过在后台一直运行 mark worker 来实现。
func gcStart(mode gcMode, forceTrigger bool) {
…
//在后台启动 mark worker
if mode == gcBackgroundMode {
gcBgMarkStartWorkers()
}
}
func gcBgMarkStartWorkers() {
// Background marking is performed by per-P G’s. Ensure that
// each P has a background GC G.
for , p := range &allp {
if p == nil || p.status == _Pdead {
break
}
if p.gcBgMarkWorker == 0 {
go gcBgMarkWorker(p)
notetsleepg(&work.bgMarkReady, -1)
noteclear(&work.bgMarkReady)
}
}
}
// gcBgMarkWorker 是一直在后台运行的,大部分时候是休眠状态,通过 gcController 来调度
func gcBgMarkWorker(_p *p) {
for {
// 将当前 goroutine 休眠,直到满足某些条件
gopark(…)
…
// mark 过程
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, gcDrainNoBlock|gcDrainFlushBgCredit)
case gcMarkWorkerFractionalMode:
gcDrain(&p.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
case gcMarkWorkerIdleMode:
gcDrain(&p.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
}
casgstatus(gp, _Gwaiting, _Grunning)
})
…
}
}
Mark 阶段的标记代码主要在函数 gcDrain() 中实现。
// gcDrain scans roots and objects in work buffers, blackening grey
// objects until all roots and work buffers have been drained.
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
…
// Drain root marking jobs.
if work.markrootNext < work.markrootJobs {
for !(preemptible && gp.preempt) {
job := atomic.Xadd(&work.markrootNext, +1) - 1
if job >= work.markrootJobs {
break
}
markroot(gcw, job)
if idle && pollWork() {
goto done
}
}
}
// 处理 heap 标记
// Drain heap marking jobs.
for !(preemptible && gp.preempt) {
...
//从灰色列队中取出对象
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)
} } 3. Mark termination (STW phase 2) mark termination 阶段会 stop the world。函数实现在 gcMarkTermination()。1.8 版本已经不会再对 goroutine stack 进行 re-scan 了。细节有点多,这里不细说了。 func gcMarkTermination() {
// World is stopped.
// Run gc on the g0 stack. We do this so that the g stack
// we're currently running on will no longer change. Cuts
// the root set down a bit (g0 stacks are not scanned, and
// we don't need to scan gc's internal state). We also
// need to switch to g0 so we can shrink the stack.
systemstack(func() {
gcMark(startTime)
// Must return immediately.
// The outer function's stack may have moved
// during gcMark (it shrinks stacks, including the
// outer function's stack), so we must not refer
// to any of its variables. Return back to the
// non-system stack to pick up the new addresses
// before continuing.
})
... } 7.4 清扫 清扫相对来说就简单很多了。
func gcSweep(mode gcMode) {
…
//阻塞式
if !_ConcurrentSweep || mode == gcForceBlockMode {
// Special case synchronous sweep.
…
// Sweep all spans eagerly.
for sweepone() != ^uintptr(0) {
sweep.npausesweep++
}
// Do an additional mProf_GC, because all ‘free’ events are now real as well.
mProf_GC()
mProf_GC()
return
}
// 并行式
// Background sweep.
lock(&sweep.lock)
if sweep.parked {
sweep.parked = false
ready(sweep.g, 0, true)
}
unlock(&sweep.lock) } 对于并行式清扫,在 GC 初始化的时候就会启动 bgsweep(),然后在后台一直循环。 func bgsweep(c chan int) {
sweep.g = getg()
lock(&sweep.lock)
sweep.parked = true
c <- 1
goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
for {
for gosweepone() != ^uintptr(0) {
sweep.nbgsweep++
Gosched()
}
lock(&sweep.lock)
if !gosweepdone() {
// This can happen if a GC runs between
// gosweepone returning ^0 above
// and the lock being acquired.
unlock(&sweep.lock)
continue
}
sweep.parked = true
goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
} }
func gosweepone() uintptr {
var ret uintptr
systemstack(func() {
ret = sweepone()
})
return ret
}
不管是阻塞式还是并行式,都是通过 sweepone()函数来做清扫工作的。如果对于上篇文章 Golang 内存管理 熟悉的话,这个地方就很好理解。内存管理都是基于 span 的,mheap_ 是一个全局的变量,所有分配的对象都会记录在 mheap_ 中。在标记的时候,我们只要找到对对象对应的 span 进行标记,清扫的时候扫描 span,没有标记的 span 就可以回收了。
// sweeps one span
// returns number of pages returned to heap, or ^uintptr(0) if there is nothing to sweep
func sweepone() uintptr {
…
for {
s := mheap_.sweepSpans[1-sg/2%2].pop()
…
if !s.sweep(false) {
// Span is still in-use, so this returned no
// pages to the heap and the span needs to
// move to the swept in-use list.
npages = 0
}
}
}
// Sweep frees or collects finalizers for blocks not marked in the mark phase.
// It clears the mark bits in preparation for the next GC round.
// Returns true if the span was returned to heap.
// If preserve=true, don’t return it to heap nor relink in MCentral lists;
// caller takes care of it.
func (s *mspan) sweep(preserve bool) bool {
…
}
7.5 其他
1. gcWork
这里介绍一下任务队列,或者说灰色对象管理。每个 P 上都有一个 gcw 用来管理灰色对象(get 和 put),gcw 的结构就是 gcWork。gcWork 中的核心是 wbuf1 和 wbuf2,里面存储就是灰色对象,或者说是 work(下面就全部统一叫做 work)。
type p struct {
…
gcw gcWork
}
type gcWork struct {
// wbuf1 and wbuf2 are the primary and secondary work buffers.
wbuf1, wbuf2 wbufptr
// Bytes marked (blackened) on this gcWork. This is aggregated
// into work.bytesMarked by dispose.
bytesMarked uint64
// Scan work performed on this gcWork. This is aggregated into
// gcController by dispose and may also be flushed by callers.
scanWork int64 }
既然每个 P 上有一个 work buffer,那么是不是还有一个全局的 work list 呢?是的。通过在每个 P 上绑定一个 work buffer 的好处和 cache 一样,不需要加锁。
var work struct {
full uint64 // lock-free list of full blocks workbuf
empty uint64 // lock-free list of empty blocks workbuf
pad0 [sys.CacheLineSize]uint8 // prevents false-sharing between full/empty and nproc/nwait
…
}
那么为什么使用两个 work buffer (wbuf1 和 wbuf2)呢?我下面举个例子。比如我现在要 get 一个 work 出来,先从 wbuf1 中取,wbuf1 为空的话则与 wbuf2 swap 再 get。在其他时间将 work buffer 中的 full 或者 empty buffer 移到 global 的 work 中。这样的好处在于,在 get 的时候去全局的 work 里面取(多个 goroutine 去取会有竞争)。这里有趣的是 global 的 work list 是 lock-free 的,通过原子操作 cas 等实现。下面列举几个函数看一下 gcWrok。
初始化。
1 func (w *gcWork) init() {
2 w.wbuf1 = wbufptrOf(getempty())
3 wbuf2 := trygetfull()
4 if wbuf2 == nil {
5 wbuf2 = getempty()
6 }
7 w.wbuf2 = wbufptrOf(wbuf2)
8 }
// put enqueues a pointer for the garbage collector to trace.
// obj must point to the beginning of a heap object or an oblet.
func (w *gcWork) put(obj uintptr) {
wbuf := w.wbuf1.ptr()
if wbuf == nil {
w.init()
wbuf = w.wbuf1.ptr()
// wbuf is empty at this point.
} else if wbuf.nobj == len(wbuf.obj) {
w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
wbuf = w.wbuf1.ptr()
if wbuf.nobj == len(wbuf.obj) {
putfull(wbuf)
wbuf = getempty()
w.wbuf1 = wbufptrOf(wbuf)
flushed = true
}
}
wbuf.obj[wbuf.nobj] = obj
wbuf.nobj++ }
// get dequeues a pointer for the garbage collector to trace, blocking
// if necessary to ensure all pointers from all queues and caches have
// been retrieved. get returns 0 if there are no pointers remaining.
//go:nowritebarrier
func (w *gcWork) get() uintptr {
wbuf := w.wbuf1.ptr()
if wbuf == nil {
w.init()
wbuf = w.wbuf1.ptr()
// wbuf is empty at this point.
}
if wbuf.nobj == 0 {
w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
wbuf = w.wbuf1.ptr()
if wbuf.nobj == 0 {
owbuf := wbuf
wbuf = getfull()
if wbuf == nil {
return 0
}
putempty(owbuf)
w.wbuf1 = wbufptrOf(wbuf)
}
}
// TODO: This might be a good place to add prefetch code
wbuf.nobj--
return wbuf.obj[wbuf.nobj] }
2. forcegc
我们上面讲了两种 GC 触发方式:自动检测和用户主动调用。除此之后 Golang 本身还会对运行状态进行监控,如果超过两分钟没有 GC,则触发 GC。监控函数是 sysmon(),在主 goroutine 中启动。
// The main goroutine
func main() {
…
systemstack(func() {
newm(sysmon, nil)
})
}
// Always runs without a P, so write barriers are not allowed.
func sysmon() {
…
for {
now := nanotime()
unixnow := unixnanotime()
lastgc := int64(atomic.Load64(&memstats.last_gc))
if gcphase == _GCoff && lastgc != 0 && unixnow-lastgc > forcegcperiod && atomic.Load(&forcegc.idle) != 0 {
lock(&forcegc.lock)
forcegc.idle = 0
forcegc.g.schedlink = 0
injectglist(forcegc.g) // 将 forcegc goroutine 加入 runnable queue
unlock(&forcegc.lock)
}
} }
var forcegcperiod int64 = 2 * 60 *1e9 //两分钟
趁着这个机会我总结了一下常见的 GC 算法。分别是:引用计数法、Mark-Sweep法、三色标记法、分代收集法。
目前引用计数法主要用在 c++ 标准库的 std::shared_ptr 、微软的 COM 、Objective-C 和 PHP 中。
但是引用计数法有个缺陷就是不能解决循环引用的问题。循环引用是指对象 A 和对象 B 互相持有对方的引用。这样两个对象的引用计数都不是 0 ,因此永远不能被收集。
另外的缺陷是,每次对象的赋值都要将引用计数加一,增加了消耗。
标记:从程序的根节点开始, 递归地 遍历所有对象,将能遍历到的对象打上标记。
清除:讲所有未标记的的对象当作垃圾销毁。
但是这个算法也有一个缺陷,就是人们常常说的 STW 问题(Stop The World)。因为算法在标记时必须暂停整个程序,否则其他线程的代码可能会改变对象状态,从而可能把不应该回收的对象当做垃圾收集掉。
当程序中的对象逐渐增多时,递归遍历整个对象树会消耗很多的时间,在大型程序中这个时间可能会是毫秒级别的。让所有的用户等待几百毫秒的 GC 时间这是不能容忍的。
golang 1.5以前使用的这个算法。
原理如下,
首先创建三个集合:白、灰、黑。
将所有对象放入白色集合中。
然后从根节点开始遍历所有对象(注意这里并不递归遍历),把遍历到的对象从白色集合放入灰色集合。
之后遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,之后将此灰色对象放入黑色集合
重复 4 直到灰色中无任何对象
通过write-barrier检测对象有变化,重复以上操作
收集所有白色对象(垃圾)
这个算法可以实现 “on-the-fly”,也就是在程序执行的同时进行收集,并不需要暂停整个程序。
但是也会有一个缺陷,可能程序中的垃圾产生的速度会大于垃圾收集的速度,这样会导致程序中的垃圾越来越多无法被收集掉。
使用这种算法的是 Go 1.5、Go 1.6。
一般 GC 都会分三代,在 java 中称之为新生代(Young Generation)、年老代(Tenured Generation)和永久代(Permanent Generation);在 .NET 中称之为第 0 代、第 1 代和第2代。
原理如下:
新对象放入第 0 代
当内存用量超过一个较小的阈值时,触发 0 代收集
第 0 代幸存的对象(未被收集)放入第 1 代
只有当内存用量超过一个较高的阈值时,才会触发 1 代收集
2 代同理
因为 0 代中的对象十分少,所以每次收集时遍历都会非常快(比 1 代收集快几个数量级)。只有内存消耗过于大的时候才会触发较慢的 1 代和 2 代收集。
因此,分代收集是目前比较好的垃圾回收方式。使用的语言(平台)有 jvm、.NET 。
golang 的 GC
go 语言在 1.3 以前,使用的是比较蠢的传统 Mark-Sweep 算法。
1.3 版本进行了一下改进,把 Sweep 改为了并行操作。
1.5 版本进行了较大改进,使用了三色标记算法。go 1.5 在源码中的解释是“非分代的、非移动的、并发的、三色的标记清除垃圾收集器”
go 除了标准的三色收集以外,还有一个辅助回收功能,防止垃圾产生过快手机不过来的情况。这部分代码在 runtime.gcAssistAlloc 中。
但是 golang 并没有分代收集,所以对于巨量的小对象还是很苦手的,会导致整个 mark 过程十分长,在某些极端情况下,甚至会导致 GC 线程占据 50% 以上的 CPU。
因此,当程序由于高并发等原因造成大量小对象的gc问题时,最好可以使用 sync.Pool 等对象池技术,避免大量小对象加大 GC 压力。