Go: GC 原理

标记清扫法

Go 1.3 的 GC 采用标记清扫法，分为两个步骤：

• 标记
• 清扫

标记的过程很简单：从对象根节点开始 dfs，每遍历到一个节点就做标记，最后没有标记的节点就是要清理的节点：

例如上图：对象 4 和对象 5 将在清扫过程中被清理

为了保证 GC 的过程中，对象之间的引用关系不被改变，go runtime 会 阻塞除了 gc 以外的所有 goroutine，这个过程被称为 STW（stop-the-world）

STW 的时间越长，整个应用程序阻塞的时间就会越长，给用户的体验就是进程「卡住了」

三色标记法

1.3 版本的 Go 采用的标记清扫法的 STW 时间太长了

在 1.5 版本，Go 引入了三色标记法

原理

三色标记法将程序中的对象分成白色、黑色和灰色三类。

• 白色：不确定对象。
• 灰色：存活对象，子对象待处理。
• 黑色：存活对象。

标记过程如下：

1. STW，标记准备，将所有节点标记为白色
2. 解除 STW
3. 将所有根节点标记为 灰色
4. 遍历灰色集合：将灰色节点标记为黑色，灰色节点的字节点标记为灰色
5. 持续步骤 4，直到灰色集合为空

用几张图来展示三色标记法的过程：

最终，对象 4 和对象 5 处于白色集合，将被 GC 掉

存在的问题

在标记的过程中，是没有 STW 的，也就是说，GC 和其它 goroutine 是并发执行的

并发执行，意味着 GC 过程中，其它 goroutine 可能修改了对象间的引用关系 ，这会带来两个问题：

• 某一个对象，没有被任何对象引用，但无法被 GC
• 某一个对象，被其它对象引用，但是被 GC

第一种情况还好，即使这一次没有被 GC，下一轮 GC 也可以把它回收掉

但第二种情况就比较严重了，回收了正在使用的对象，这会带来严重后果：

在这个情景下，由于对象 0 已经是黑色，无法将对象 4、5 标记为黑色，会导致对象 4、5 在本轮 GC 错误回收！

错误回收发生的根本原因还是在于：黑色对象直接引用了一个白色对象，白色对象无法被染色，于是就被回收了

屏障

为了避免上述问题，我们当然可以在标记时，设置 STW，防止并发修改

但这样就退化为标记清扫法了，我们应该在没有 STW 的前提（即允许并发修改）下，保证对象不被错误回收

Go 在实现三色标记法时，引入了写屏障

插入写屏障

插入写屏障的原理是：不允许一个黑色节点的子节点为白色

引入写屏障，可以在允许并发修改的条件下，保证对象不被错误回收

这样，对象 4、5 就不会被回收了

为了保证栈的读写效率，写屏障只会在堆对象启用，不会在栈对象启用

这意味着如果对象 4、5 如果存储在栈区，还是有可能被错误回收的

因此，使用插入写屏障，需要在白色对象回收完毕后，再单独扫描一遍栈区，并且，这个扫描过程 需要 STW

删除写屏障

原理直接看图吧：

引入删除屏障，也可以在允许并发修改的条件下，保证对象不被错误回收

但是这种删除方式会出现 遗漏删除 的问题：

对象 1、2、3 应该在这一轮被 GC，但是却没有，只能在下一轮 GC

当然，标准的 Go 实现（至少到目前为止）并未使用传统意义上的删除写屏障，在 1.5 ～ 1.8 版本间，Go 使用的是插入写屏障机制

混合写屏障

插入写屏障和删除写屏障的短板：

• 插入写屏障：结束时 需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；
• 删除写屏障：回收精度低

为了弥补这两种方式的短板，Go 1.8 引入了 混合写屏障

As of Go 1.7, the one remaining source of unbounded and potentially non-trivial stop-the-world (STW) time is stack re-scanning. We propose to eliminate the need for stack re-scanning by switching to a hybrid write barrier that combines a Yuasa-style deletion write barrier [Yuasa ‘90] and a Dijkstra-style insertion write barrier [Dijkstra ‘78]. Preliminary experiments show that this can reduce worst-case STW time to under 50µs, and this approach may make it practical to eliminate STW mark termination altogether.

Eliminating stack re-scanning will in turn simplify and eliminate many other parts of the garbage collector that exist solely to improve the performance of stack re-scanning. This includes stack barriers (which introduce significant complexity in many parts of the runtime) and maintenance of the re-scan list. Hence, in addition to substantially improving STW time, the hybrid write barrier should also reduce the overall complexity of the garbage collector.

顾名思义，混合写屏障就是将 插入写屏障 与 删除写屏障 结合起来了，具体规则如下：

• GC 开始将栈上的对象 全部扫描并标记为黑色（这一步需要 STW，但时间很短）
• GC 期间，任何在栈上创建的新对象，均为黑色。
• 堆上添加一个新的引用对象，将引用对象标记为灰色
• 堆上删除一个已有引用对象，将引用对象标记为灰色

这种方式避免了结束时需要 STW 重新扫描栈，但仍然存在 回收精度低 的问题

所以目前我还没有弄清楚为什么 Go1.8 要引入混合写屏障，直接用删除写屏障不就好了吗？

Golang 官方给出了混合写屏障的优缺点：

The advantage of the hybrid barrier is that it lets a stack scan permanently blacken a stack (without a STW and without write barriers to the stack), which entirely eliminates the need for stack re-scanning, in turn eliminating the need for stack barriers and re-scan lists. Stack barriers in particular introduce significant complexity throughout the runtime, as well as interfering with stack walks from external tools such as GDB and kernel-based profilers.

Also, like the Dijkstra-style write barrier, the hybrid barrier does not require a read barrier, so pointer reads are regular memory reads; and it ensures progress, since objects progress monotonically from white to grey to black.

The disadvantages of the hybrid barrier are minor. It may result in more floating garbage, since it retains everything reachable from roots (other than stacks) at any point during the mark phase. However, in practice it’s likely that the current Dijkstra barrier is retaining nearly as much. The hybrid barrier also prohibits certain optimizations: in particular, the Go compiler currently omits a write barrier if it can statically show that the pointer is nil, but the hybrid barrier requires a write barrier in this case. This may slightly increase binary size.

用中文来说的话：如果在栈引入屏障，它在运行时 会引入相当的复杂性，同时也干扰了如 GDB 和基于内核的性能分析等外部工具的栈回溯。

因此，混合写屏障通过将栈上对象全部标记为黑色，彻底避免了重新 STW 来扫描栈（STW stack re-scanning），同时也避免了栈上的写屏障，保证了运行效率

当然，混合写屏障还是有缺点的：可能产生一些浮动垃圾（但是 dijkstra 风格的插入写屏障还是有浮动垃圾的可能）

GC 的时机

自动触发

// src/runtime/mgc.go
const (
	gcTriggerHeap gcTriggerKind = iota
	gcTriggerTime
	gcTriggerCycle
)

一共有三种触发方式：

• gcTriggerHeap：堆内存分配
• gcTriggerTime：定时触发，以 runtime.forcegcperiod 变量为准，默认 2min 一次
• gcTriggerCycle：如果没有启用 GC，那么启用（这种方式出现在手动调用 runtime.GC()）

手动触发

可以调用 runtime.GC() 来手动触发 GC

自动触发基本流程

go 的 runtime 在初始化时，会启动一个 goroutine 用于 GC：

func init() {
	go forcegchelper()
}

func forcegchelper() {
	forcegc.g = getg()
	lockInit(&forcegc.lock, lockRankForcegc)
	for {
		lock(&forcegc.lock)
		if forcegc.idle != 0 {
			throw("forcegc: phase error")
		}
		atomic.Store(&forcegc.idle, 1)
		goparkunlock(&forcegc.lock, waitReasonForceGCIdle, traceEvGoBlock, 1) // 将当前 goroutine 挂起，等待被唤醒
        // this goroutine is explicitly resumed by sysmon
		if debug.gctrace > 0 {
			println("GC forced")
		}

		gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
	}
}

这个 goroutine 会先被挂起，等待被其它 goroutine 唤醒

唤醒这个操作实际上是由一个监控 goroutine 完成的：

func sysmon() {
	...
	for {
		...
		// check if we need to force a GC
		if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
			lock(&forcegc.lock)
			forcegc.idle = 0
			var list gList
			list.push(forcegc.g) // 将 forcegc.g 加入到 GRQ 中
			injectglist(&list)
			unlock(&forcegc.lock)
		}
		if debug.schedtrace > 0 && lasttrace+int64(debug.schedtrace)*1000000 <= now {
			lasttrace = now
			schedtrace(debug.scheddetail > 0)
		}
		unlock(&sched.sysmonlock)
	}
}

这个函数会不停检测 idle time 是否与 forcegcperiod 相等，如果相等，会将 forcegc 这个 goroutine 加入到全局队列中，等待调度

参考资料

• Golang 垃圾回收+混合写屏障 GC 全分析
• Proposal: Eliminate STW stack re-scanning