Go gc 原理及源码分析
里程碑
- v1.1 mark & sweep STW(标记-清扫)
- v1.3 Mark STW, Sweep 并行(分离了标记和清扫的操作,标记过程STW,清扫过程并发执行)
- v1.5 三色标记法
- v1.8 hybrid write barrier
gc算法
- 引用计数(reference counting)
python
- 标记-清扫(mark & sweep)
java、go
- 复制收集(Copy and Collection)
Go gc演变
mark & sweep
Stop the World
Mark
Sweep
Start the World
三色标记法
- 首先创建三个集合:白、灰、黑。
- 将所有对象放入白色集合中。(标记为白色)
- 然后从根节点开始遍历所有对象(注意这里并不递归遍历),把遍历到的对象从白色集合放入灰色集合。
- 之后遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,之后将此灰色对象放入黑色集合
- 重复 4 直到灰色中无任何对象
- 通过write-barrier检测对象有变化,重复以上操作
- 收集所有白色对象(垃圾)
根:
- 全局变量:程序在编译期就能确定的那些存在于程序整个生命周期的变量。
- 执行栈:每个 goroutine 都包含自己的执行栈,这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
- 寄存器:寄存器的值可能表示一个指针,参与计算的这些指针可能指向某些赋值器分配的堆内存区块。
时间轴
目前整个GC流程会进行两次STW(Stop The World), 第一次是Stack scan阶段, 第二次是Mark Termination阶段.
- 第一次STW会准备根对象的扫描, 启动写屏障(Write Barrier)和辅助GC(mutator assist).
- 第二次STW会重新扫描部分根对象, 禁用写屏障(Write Barrier)和辅助GC(mutator assist).
对象丢失问题
条件: 1.一个白色对象被黑色对象引用,是注定无法通过这个黑色对象来保证自身存活的, 2.与此同时,如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏,那么这个白色对象必然会被视为垃圾清除掉。
write-barrier
弱三色不变式:所有被黑色对象引用的白色对象都处于灰色保护状态(直接或间接从灰色对象可达)。强三色不变式:不存在黑色对象到白色对象的指针。
插入屏障(v1.5)
// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(ptr)
*slot = ptr
}
插入屏障拦截将白色指针插入黑色对象的操作,标记其对应对象为灰色状态,这样就不存在黑色对象引用白色对象的情况了,满足强三色不变式
缺点:
- 由于 Dijkstra 插入屏障的“保守”,在一次回收过程中可能会残留一部分对象没有回收成功,只有在下一个回收过程中才会被回收;
- 在标记阶段中,每次进行指针赋值操作时,都需要引入写屏障,这无疑会增加大量性能开销;为了避免造成性能问题,Go 团队在最终实现时,没有为所有栈上的指针写操作,启用写屏障,而是当发生栈上的写操作时,将栈标记为灰色,但此举产生了灰色赋值器,将会需要标记终止阶段 STW 时对这些栈进行重新扫描。
删除屏障
// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(*slot)
*slot = ptr
}
为了防止丢失从灰色对象到白色对象的路径,应该假设 *slot 可能会变为黑色,为了确保 ptr 不会在被赋值到 *slot 前变为白色,shade(*slot) 会先将 *slot 标记为灰色,进而该写操作总是创造了一条灰色到灰色或者灰色到白色对象的路径,满足弱三色不变性
Yuasa 删除屏障的优势则在于不需要标记结束阶段的重新扫描,结束时候能够准确的回收所有需要回收的白色对象。缺陷是 Yuasa 删除屏障会拦截写操作,进而导致波面的退后,产生“冗余”的扫描。
hybrid write barrier
// 混合写屏障
func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) {
shade(*slot)
shade(ptr)
*slot = ptr
}
结合了 Dijkstra 和 Yuasa 写屏障的优势,但缺点也非常明显,因为着色成本是双倍的,而且编译器需要插入的代码也成倍增加,随之带来的结果就是编译后的二进制文件大小也进一步增加。为了针对写屏障的性能进行优化,Go 1.10 前后,Go 团队随后实现了批量写屏障机制。其基本想法是将需要着色的指针统一写入一个缓存,每当缓存满时统一对缓存中的所有 ptr 指针进行着色。
源码解读
gcStart()
// go触发gc都是从这开始
func gcStart(trigger gcTrigger) {
...
// Ok, we're doing it! Stop everybody else
semacquire(&worldsema)
if trace.enabled {
traceGCStart()
}
// Check that all Ps have finished deferred mcache flushes.
for _, p := range allp {
if fg := atomic.Load(&p.mcache.flushGen); fg != mheap_.sweepgen {
println("runtime: p", p.id, "flushGen", fg, "!= sweepgen", mheap_.sweepgen)
throw("p mcache not flushed")
}
}
// 启动后台扫描任务
gcBgMarkStartWorkers()
systemstack(gcResetMarkState)
// 重置参数
work.stwprocs, work.maxprocs = gomaxprocs, gomaxprocs
if work.stwprocs > ncpu {
// This is used to compute CPU time of the STW phases,
// so it can't be more than ncpu, even if GOMAXPROCS is.
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)
}
// 停止所有运行中的G,并禁止运行
systemstack(stopTheWorldWithSema)
// 清扫上一轮GC未清扫的span,确保上一轮gc已完成
systemstack(func() {
finishsweep_m()
})
// 清扫sched.sudogcache和sched.deferpool
// reclaimed until the next GC cycle.
clearpools()
// 增加gc计数
work.cycles++
// 标记新一轮gc已开始
gcController.startCycle()
work.heapGoal = memstats.next_gc
// In STW mode, disable scheduling of user Gs. This may also
// disable scheduling of this goroutine, so it may block as
// soon as we start the world again.
if mode != gcBackgroundMode {
schedEnableUser(false)
}
// 设置GC状态,启用写屏障
setGCPhase(_GCmark)
// 重置后台标记任务的计数
gcBgMarkPrepare() // Must happen before assist enable.
// 计算扫描根对象的任务数量
gcMarkRootPrepare()
// 标记所有tiny alloc等待合并的对象
gcMarkTinyAllocs()
// 启用辅助GC
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
})
// In STW mode, we could block the instant systemstack
// returns, so don't do anything important here. Make sure we
// block rather than returning to user code.
if mode != gcBackgroundMode {
Gosched()
}
semrelease(&work.startSema)
}
gc时间优化
版本 | 发布时间 | GC算法 | STW时间 | 重大更新 |
---|---|---|---|---|
V1.1 | 2013/5 | STW | 可能秒级别 | |
V1.3 | 2014/6 | Mark和Sweep分离. Mark STW, Sweep并发 | 百ms级别 | |
V1.4 | 2014/12 | runtime代码基本都由C和少量汇编改为Go和少量汇编, 包括GC部分, 以此实现了准确式GC,减少了堆大小, 同时对指针的写入引入了write barrier, 为1.5铺垫 | 百ms级别 | |
V1.5 | 2015/8 | 三色标记法, 并发Mark, 并发Sweep. 非分代, 非移动, 并发的收集器 | 10ms-40ms级别 | 重要更新版本,生产上GC基本不会成为问题 |
V1.6 | 2016/2 | 1.5中一些与并发GC不协调的地方更改. 集中式的GC协调协程, 改为状态机实现 | 5-20ms | |
V1.7 | 2016/8 | GC时栈收缩改为并发, span中对象分配状态由freelist改为bitmap | 1-3ms左右 | |
V1.8 | 2017/2 | hybird write barrier, 消除了stw中的重新扫描栈 | sub ms | Golang GC进入Sub ms时代 |
参考
cloud.tencent.com/developer/a… www.bookstack.cn/read/qcrao-…