7.2 垃圾收集器

7.2.1 设计原理

Golang 的内存管理组件：

mutator-allocator-collector

如上图所示，用户程序（Mutator）会通过内存分配器（Allocator）在堆上申请内存，而垃圾收集器（Collector）负责回收堆上的内存空间，内存分配器和垃圾收集器共同管理着程序中的堆内存空间。

标记清除

标记清除（Mark-Sweep）是跟踪式垃圾收集器，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

1. 标记阶段：从根对象出发查找并标记堆中所有存活的对象
2. 清除阶段：遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表

标记 Mark

mark-sweep-mark-phase

如图所示，内存空间中包含多个对象，从根对象出发依次遍历对象的子对象并将从根节点可达的对象都标记成存活状态，即 A、C 和 D 三个对象，剩余的 B、E 和 F 三个对象因为从根节点不可达，所以会被当做垃圾。

清除 Sweep

mark-sweep-sweep-phase

标记阶段结束后会进入清除阶段，在该阶段中收集器会依次遍历堆中的所有对象，释放其中没有被标记的 B、E 和 F 三个对象并将新的空闲内存空间以链表的结构串联起来，方便内存分配器的使用。

标记阶段结束后，垃圾收集器会依次遍历堆中的对象并清除其中的垃圾，整个过程需要标记对象的存活状态，用户程序在垃圾收集的过程中也不能执行，即暂停程序（Stop the world，STW）。

三色标记

tri-color-objects

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

1. 黑色对象：活跃的对象，包括：
   • 不存在任何引用外部指针的对象
   • 从根对象可达的对象
2. 白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收
3. 灰色对象：活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象

工作流程

tri-color-mark-sweep

垃圾收集器开始工作时，程序中不存在任何的黑色对象，垃圾收集的根对象会被标记成灰色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束。

三色标记垃圾收集器工作步骤分为三步：

1. 从灰色对象的集合中选择一个灰色对象并将其标记成黑色
2. 将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收
3. 重复上述两个步骤直到对象图中不存在灰色对象

tri-color-mark-sweep-after-mark-phase

因为用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW。如下图所示，若用户在标记过程中建立了从 A 对象到 D 对象的引用，但因程序中已经不存在灰色对象，所以 D 对象会被垃圾收集器错误地回收。

tri-color-mark-sweep-and-mutator

本来不应该被回收的对象却被回收了，这在内存管理中是非常严重的错误，这种错误称为悬挂指针，即指针没有指向特定类型的合法对象，影响了内存的安全性，想要并发或者增量地标记对象还是需要使用屏障技术。

屏障技术

内存屏障技术是一种屏障指令，可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束。

多数的现代处理器都会乱序执行指令以最大化性能，屏障技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

若在并发或者增量的标记算法中保证正确性，需要达成以下两种三色不变性（Tri-color invariant）中的一种：

1. 强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象
2. 弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径

strong-weak-tricolor-invariant

屏障技术可以分为：

1. 读屏障（Read barrier）
2. 写屏障（Write barrier）

因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。

插入写屏障

由 Dijkstra 提出，通过如下所示的写屏障，用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性：

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

当执行类似 *slot = ptr 的表达式时，会执行上述写屏障通过 shade 函数尝试改变指针的颜色:

• 如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色
• 其他情况则保持不变

dijkstra-insert-write-barrier

插入写屏障的流程：

1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色
2. 用户程序修改 A 对象的指针，将原本指向 B 对象的指针指向 C 对象，这时触发写屏障将 C 对象标记成灰色
3. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色

Dijkstra 的插入写屏障是一种相对保守的屏障技术，会将有存活可能的对象都标记成灰色以满足强三色不变性。

上图所示的流程中，实际上不再存活的 B 对象最后没有被回收，被错误标记的垃圾对象只有在下一个循环才会被回收。

缺点：

栈上的对象在垃圾收集中也会被认为是根对象，所以为了保证内存的安全，Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描，这两种方法各有各的缺点，前者会大幅度增加写入指针的额外开销，后者重新扫描栈对象时需要暂停程序。

删除写屏障

由 Yuasa 提出，删除写屏障会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）。

该算法会使用如下所示的写屏障保证增量或者并发执行垃圾收集时程序的正确性：

writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

在老对象的引用被删除时，将白色的老对象涂成灰色，可以保证弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用。

yuasa-delete-write-barrier

删除写屏障的流程：

1. 圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色
2. 用户程序将 A 对象原本指向 B 的指针指向 C，触发删除写屏障，但是因为 B 对象已经是灰色的，所以不做改变
3. 用户程序将 B 对象原本指向 C 的指针删除，触发删除写屏障，白色的 C 对象被涂成灰色
4. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色

增量和并发

传统的垃圾收集算法会在垃圾收集的执行期间暂停应用程序，一旦触发垃圾收集，垃圾收集器会抢占 CPU 的使用权占据大量的计算资源以完成标记和清除工作。

stop-the-world-collector

为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，会使用下面的策略优化：

1. 增量垃圾收集：增量地标记和清除垃圾，降低应用程序暂停的最长时间
2. 并发垃圾收集：利用多核的计算资源，在用户程序执行时并发标记和清除垃圾

增量收集器

增量式（Incremental）的垃圾收集可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但是这也减少了应用程序暂停的最大时间：

incremental-collector

并发收集器

并发（Concurrent）的垃圾收集能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器能够减少垃圾收集对应用程序的影响：

concurrent-collector

7.2.2 Golang GC 的演进过程

1. v1.0：完全串行的标记和清除过程，需要暂停整个程序
2. v1.1：在多核主机并行执行垃圾收集的标记和清除阶段
3. v1.3：运行时基于只有指针类型的值包含指针的假设增加了对栈内存的精确扫描支持，实现了真正精确的垃圾收集
4. v1.5：实现了基于三色标记清扫的并发垃圾收集器
5. v1.6：实现了去中心化的垃圾收集协调器
6. v1.7：通过并行栈收缩将垃圾收集的时间缩短至 2ms 以内
7. v1.8：使用混合写屏障将垃圾收集的时间缩短至 0.5ms 以内
8. v1.9：彻底移除暂停程序的重新扫描栈的过程
9. v1.10：更新了垃圾收集调频器（Pacer）的实现，分离软硬堆大小的目标
10. v1.12：使用新的标记终止算法简化垃圾收集器的几个阶段
11. v1.13：通过新的 Scavenger 解决瞬时内存占用过高的应用程序向操作系统归还内存的问题
12. v1.14：使用全新的页分配器优化内存分配的速度

并发垃圾收集

golang-concurrent-collector

首先，并发垃圾收集器必须在合适的时间点触发垃圾收集循环，假设我们的 Go 语言程序运行在一台 4 核的物理机上，那么在垃圾收集开始后，收集器会占用 25% 计算资源在后台来扫描并标记内存中的对象。

Go 语言的并发垃圾收集器会在扫描对象之前暂停程序做一些标记对象的准备工作，其中包括启动后台标记的垃圾收集器以及开启写屏障，如果在后台执行的垃圾收集器不够快，应用程序申请内存的速度超过预期，运行时会让申请内存的应用程序辅助完成垃圾收集的扫描阶段，在标记和标记终止阶段结束之后就会进入异步的清理阶段，将不用的内存增量回收。

回收堆目标

Go 语言运行时的默认配置会在堆内存达到上一次垃圾收集的 2 倍时，触发新一轮的垃圾收集，这个行为可以通过环境变量 GOGC 调整，在默认情况下它的值为 100，即增长 100% 的堆内存才会触发 GC。

stop-the-world-garbage-collector-heap

因为并发垃圾收集器会与程序一起运行，所以它无法准确的控制堆内存的大小，并发收集器需要在达到目标前触发垃圾收集，这样才能够保证内存大小的可控，并发收集器需要尽可能保证垃圾收集结束时的堆内存与用户配置的 GOGC 一致。

concurrent-garbage-collector-heap

并发垃圾收集器的同时使用垃圾收集调步（Pacing）算法计算触发的垃圾收集的最佳时间，确保触发的时间既不会浪费计算资源，也不会超出预期的堆大小。如上图所示，其中黑色的部分是上一次垃圾收集后标记的堆大小，绿色部分是上次垃圾收集结束后新分配的内存，因为我们使用并发垃圾收集，所以黄色的部分就是在垃圾收集期间分配的内存，最后的红色部分是垃圾收集结束时与目标的差值，我们希望尽可能减少红色部分内存，降低垃圾收集带来的额外开销以及程序的暂停时间。

混合写屏障

混合写屏障将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色：

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

为了移除栈的重扫描过程，除了引入混合写屏障之外，在垃圾收集的标记阶段，我们还需要将创建的所有新对象都标记成黑色，防止新分配的栈内存和堆内存中的对象被错误地回收，因为栈内存在标记阶段最终都会变为黑色，所以不再需要重新扫描栈空间。

7.2.3 实现原理

工作流程

Golang 垃圾收集可以分成清除终止、标记、标记终止和清除四个不同阶段，它们分别完成了不同的工作：

garbage-collector-phases

1. 清理终止阶段：
   1. 暂停程序，所有的处理器在这时会进入安全点（Safe point）
   2. 如果当前垃圾收集循环是强制触发的，还需要处理还未被清理的内存管理单元
2. 标记阶段：
   1. 将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assists）并将根对象入队
   2. 恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色
   3. 开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器 P
   4. 依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色
   5. 使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段
3. 标记终止阶段：
   1. 暂停程序，将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序
   2. 清理处理器上的线程缓存
4. 清理阶段：
   1. 将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障
   2. 恢复用户程序，所有新创建的对象会标记成白色
   3. 后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理

全局变量

垃圾收集中有一些比较重要的全局变量：

1. runtime.gcphase 是垃圾收集器当前处于的阶段，可能处于 _GCoff、_GCmark 和 _GCmarktermination，Goroutine 在读取或者修改该阶段时需要保证原子性
2. runtime.gcBlackenEnabled 是一个布尔值，当垃圾收集处于标记阶段时，该变量会被置为 1，在这里辅助垃圾收集的用户程序和后台标记的任务可以将对象涂黑
3. runtime.gcController 实现了垃圾收集的调步算法，它能够决定触发并行垃圾收集的时间和待处理的工作
4. runtime.gcpercent 是触发垃圾收集的内存增长百分比，默认情况下为 100，即堆内存相比上次垃圾收集增长 100% 时应该触发 GC，并行的垃圾收集器会在到达该目标前完成垃圾收集
5. runtime.writeBarrier 是一个包含写屏障状态的结构体，其中的 enabled 字段表示写屏障的开启与关闭
6. runtime.worldsema 是全局的信号量，获取该信号量的线程有权利暂停当前应用程序

触发时机

运行时会通过runtime.gcTrigger.test决定是否需要触发垃圾收集，当满足触发垃圾收集的基本条件时：

1. 允许垃圾收集
2. 程序没有崩溃
3. 没有处于垃圾收集循环

会根据三种不同方式触发进行不同的检查：

func (t gcTrigger) test() bool {
	if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
		return false
	}
	switch t.kind {
	case gcTriggerHeap:
		return memstats.heap_live >= memstats.gc_trigger
	case gcTriggerTime:
		if gcpercent < 0 {
			return false
		}
		lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
		return lastgc != 0 && t.now-lastgc > forcegcperiod
	case gcTriggerCycle:
		return int32(t.n-work.cycles) > 0
	}
	return true
}

1. gcTriggerHeap：堆内存的分配达到控制器计算的触发堆大小
2. gcTriggerTime：如果一定时间内没有触发，就会触发新的循环，该触发条件由 runtime.forcegcperiod 变量控制，默认为 2 分钟
3. gcTriggerCycle ：如果当前没有开启垃圾收集，则触发新的循环

用于开启垃圾收集的方法 runtime.gcStart 会接收一个 runtime.gcTrigger 类型的谓词，所有出现 runtime.gcTrigger 结构体的位置都是触发垃圾收集的代码：

1. runtime.sysmon 和 runtime.forcegchelper — 后台运行定时检查和垃圾收集
2. runtime.GC — 用户程序手动触发垃圾收集
3. runtime.mallocgc — 申请内存时根据堆大小触发垃圾收集

garbage-collector-trigger

后台触发

运行时会在应用程序启动时在后台开启一个用于强制触发垃圾收集的 Goroutine，该 Goroutine 的职责非常简单 — 调用 runtime.gcStart 尝试启动新一轮的垃圾收集：

func init() {
	go forcegchelper()
}

func forcegchelper() {
	forcegc.g = getg()
	for {
		lock(&forcegc.lock)
		atomic.Store(&forcegc.idle, 1)
		goparkunlock(&forcegc.lock, waitReasonForceGGIdle, traceEvGoBlock, 1)
		gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
	}
}

为了减少对计算资源的占用，该 Goroutine 会在循环中调用 runtime.goparkunlock 主动陷入休眠等待其他 Goroutine 的唤醒，runtime.forcegchelper 在大多数时间都是陷入休眠的，但是它会被系统监控器 runtime.sysmon 在满足垃圾收集条件时唤醒：

func sysmon() {
	...
	for {
		...
		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)
			injectglist(&list)
			unlock(&forcegc.lock)
		}
	}
}

系统监控在每个循环中都会主动构建一个 runtime.gcTrigger 并检查垃圾收集的触发条件是否满足，如果满足条件，系统监控会将 runtime.forcegc 状态中持有的 Goroutine 加入全局队列等待调度器的调度。

手动触发

用户程序会通过 runtime.GC 函数在程序运行期间主动通知运行时执行，该方法在调用时会阻塞调用方直到当前垃圾收集循环完成，在垃圾收集期间也可能会通过 STW 暂停整个程序：

func GC() {
	n := atomic.Load(&work.cycles)
	gcWaitOnMark(n)
	gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
	gcWaitOnMark(n + 1)

	for atomic.Load(&work.cycles) == n+1 && sweepone() != ^uintptr(0) {
		sweep.nbgsweep++
		Gosched()
	}

	for atomic.Load(&work.cycles) == n+1 && atomic.Load(&mheap_.sweepers) != 0 {
		Gosched()
	}

	mp := acquirem()
	cycle := atomic.Load(&work.cycles)
	if cycle == n+1 || (gcphase == _GCmark && cycle == n+2) {
		mProf_PostSweep()
	}
	releasem(mp)
}

1. 在正式开始垃圾收集前，运行时需要通过 runtime.gcWaitOnMark 等待上一个循环的标记终止、标记和清除终止阶段完成；
2. 调用 runtime.gcStart 触发新一轮的垃圾收集并通过 runtime.gcWaitOnMark 等待该轮垃圾收集的标记终止阶段正常结束；
3. 持续调用 runtime.sweepone 清理全部待处理的内存管理单元并等待所有的清理工作完成，等待期间会调用 runtime.Gosched 让出处理器；
4. 完成本轮垃圾收集的清理工作后，通过 runtime.mProf_PostSweep 将该阶段的堆内存状态快照发布出来，我们可以获取这时的内存状态；

申请内存

使用runtime.mallocgc申请内存时，对于微对象、小对象和大对象三类的创建都可能会触发新的垃圾收集循环：

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	shouldhelpgc := false
	...
	if size <= maxSmallSize {
		if noscan && size < maxTinySize {
			...
			v := nextFreeFast(span)
			if v == 0 {
				v, _, shouldhelpgc = c.nextFree(tinySpanClass)
			}
			...
		} else {
			...
			v := nextFreeFast(span)
			if v == 0 {
				v, span, shouldhelpgc = c.nextFree(spc)
			}
		  ...
		}
	} else {
		shouldhelpgc = true
		...
	}
	...
	if shouldhelpgc {
		if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
			gcStart(t)
		}
	}

	return x
}

1. 当前线程的内存管理单元中不存在空闲空间时，创建微对象和小对象需要调用 runtime.mcache.nextFree 从中心缓存或者页堆中获取新的管理单元，在这时就可能触发垃圾收集
2. 当用户程序申请分配 32KB 以上的大对象时，一定会构建 runtime.gcTrigger 结构体尝试触发垃圾收集

垃圾收集启动

垃圾收集在启动过程调用 runtime.gcStart，主要职责是修改全局的垃圾收集状态到 _GCmark 并做一些准备工作，流程为：

1. 两次调用 runtime.gcTrigger.test 检查是否满足垃圾收集条件
2. 暂停程序、在后台启动用于处理标记任务的工作 Goroutine、确定所有内存管理单元都被清理以及其他标记阶段开始前的准备工作
3. 进入标记阶段、准备后台的标记工作、根对象的标记工作以及微对象、恢复用户程序，进入并发扫描和标记阶段

并发扫描与标记辅助

runtime.gcBgMarkWorker 是后台的标记任务执行的函数，该函数的循环中执行了对内存中对象图的扫描和标记，流程如下：

1. 获取当前处理器以及 Goroutine 打包成runtime.gcBgMarkWorkerNode 类型的结构并主动陷入休眠等待唤醒
2. 根据处理器上的 gcMarkWorkerMode 模式决定扫描任务的策略
3. 所有标记任务都完成后，调用 runtime.gcMarkDone 方法完成标记阶段

标记终止

当所有处理器的本地任务都完成并且不存在剩余的工作 Goroutine 时，后台并发任务或者辅助标记的用户程序会调用 runtime.gcMarkDone 通知垃圾收集器。

当所有可达对象都被标记后，该函数会将垃圾收集的状态切换至 _GCmarktermination。

内存清理

垃圾收集的清理中包含对象回收器（Reclaimer）和内存单元回收器，这两种回收器使用不同的算法清理堆内存：

1. 对象回收器在内存管理单元中查找并释放未被标记的对象，但是如果 runtime.mspan 中的所有对象都没有被标记，整个单元就会被直接回收，该过程会被 runtime.mcentral.cacheSpan 或者 runtime.sweepone 异步触发；
2. 内存单元回收器会在内存中查找所有的对象都未被标记的 runtime.mspan，该过程会被 runtime.mheap.reclaim 触发；

Reference

1. https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/