Hexo

点滴积累 豁达处之

0%

go GC

Posted on In
golang

go GC

简介

简单地说，垃圾回收(GC)是在后台运行一个守护线程，它的作用是在监控各个对象的状态，识别并且丢弃不再使用的对象来释放和重用资源。

Go的垃圾回收

当前Golang使用的垃圾回收机制是三色标记发配合写屏障和辅助GC，三色标记法是标记-清除法的一种增强版本。

三色标记

介绍

理解三色标记法的关键是理解对象的三色抽象以及波面（wavefront）推进这两个概念。三色抽象只是一种描述追踪式回收器的方法，在实践中并没有实际含义，它的重要作用在于从逻辑上严密推导标记清理这种垃圾回收方法的正确性。也就是说，当我们谈及三色标记法时，通常指标记清扫的垃圾回收。

从垃圾回收器的视角来看，三色抽象规定了三种不同类型的对象，并用不同的颜色相称：

  • 白色对象（可能死亡）：未被回收器访问到的对象。在回收开始阶段，所有对象均为白色，当回收结束后，白色对象均不可达。
  • 灰色对象（波面）：已被回收器访问到的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们可能还指向白色对象。
  • 黑色对象（确定存活）：已被回收器访问到的对象，其中所有字段都已被扫描，黑色对象中任何一个指针都不可能直接指向白色对象。

这样三种不变性所定义的回收过程其实是一个波面不断前进的过程，这个波面同时也是黑色对象和白色对象的边界，灰色对象就是这个波面。

当垃圾回收开始时，只有白色对象。随着标记过程开始进行时，灰色对象开始出现（着色），这时候波面便开始扩大。当一个对象的所有子节点均完成扫描时，会被着色为黑色。当整个堆遍历完成时，只剩下黑色和白色对象，这时的黑色对象为可达对象，即存活；而白色对象为不可达对象，即死亡。这个过程可以视为以灰色对象为波面，将黑色对象和白色对象分离，使波面不断向前推进，直到所有可达的灰色对象都变为黑色对象为止的过程。如下图所示：

gc_gc01

图中展示了根对象、可达对象、不可达对象，黑、灰、白对象以及波面之间的关系。

三色标记详解

三色标记法 实际上就是通过三个阶段的标记来确定清楚的对象都有哪些. 我们来看一下具体的过程.

第一步 , 就是只要是新创建的对象,默认的颜色都是标记为“白色”.

gc_gc02

这里面需要注意的是, 所谓“程序”, 则是一些对象的跟节点集合.

gc_gc03

所以上图,可以转换如下的方式来表示.

第二步, 每次GC回收开始, 然后从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”集合。

gc_gc04

第三步, 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合

gc_gc05

第四步, 重复第三步, 直到灰色中无任何对象.

gc_gc06

gc_gc07

第五步: 回收所有的白色标记表的对象. 也就是回收垃圾.

gc_gc08

以上便是三色并发标记法

没有STW的三色标记法

我们还是基于上述的三色并发标记法来说, 他是一定要依赖STW的. 因为如果不暂停程序, 程序的逻辑改变对象引用关系, 这种动作如果在标记阶段做了修改，会影响标记结果的正确性。我们举一个场景.

如果三色标记法, 标记过程不使用STW将会发生什么事情?

gc_gc42

gc_gc43

gc_gc44

gc_gc45

gc_gc46

可以看出，有两个问题, 在三色标记法中,是不希望被发生的

  • 条件1: 一个白色对象被黑色对象引用**(白色被挂在黑色下)**
  • 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏**(灰色同时丢了该白色)**

当以上两个条件同时满足时, 就会出现对象丢失现象!

只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：

  • 如果条件 1 被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
  • 如果条件 2 被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

写屏障、混合写屏障

“强-弱” 三色不变式

我们不妨将三色不变性所定义的波面根据这两个条件进行削弱：

  • 当满足原有的三色不变性定义（或上面的两个条件都不满足时）的情况称为强三色不变性（strong tricolor invariant）

gc_gc09

  • 当赋值器令黑色对象引用白色对象时（满足条件 1 时）的情况称为弱三色不变性（weak tricolor invariant）

gc_gc10

为了遵循上述的两个方式,Golang团队初步得到了如下具体的两种屏障方式“插入屏障”, “删除屏障”.

插入屏障

具体操作: 在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)

满足: 强三色不变式. (不存在黑色对象引用白色对象的情况了， 因为白色会强制变成灰色)

场景：

1
2
A.添加下游对象(nil, B)   //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象C 更换为B，  B被标记为灰色

这段伪码逻辑就是写屏障,. 我们知道,黑色对象的内存槽有两种位置, 栈和堆. 栈空间的特点是容量小,但是要求相应速度快,因为函数调用弹出频繁使用, 所以“插入屏障”机制,在栈空间的对象操作中不使用. 而仅仅使用在堆空间对象的操作中.

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

gc_gc11

gc_gc12

gc_gc13

gc_gc14

gc_gc15

gc_gc16

但是如果栈不添加,当全部三色标记扫描之后,栈上有可能依然存在白色对象被引用的情况. 所以要对栈重新进行三色标记扫描, 但这次为了对象不丢失, 要对本次标记扫描启动STW暂停. 直到栈空间的三色标记结束.

gc_gc17

gc_gc18

gc_gc19

最后将栈和堆空间 扫描剩余的全部 白色节点清除.

gc_gc20

删除屏障

具体操作: 被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。

满足: 弱三色不变式. (保护灰色对象到白色对象的路径不会断)

场景：

1
2
A.添加下游对象(B, nil)   //A对象，删除B对象的引用。  B被A删除，被标记为灰(如果B之前为白)
A.添加下游对象(B, C)         //A对象，更换下游B变成C。   B被A删除，被标记为灰(如果B之前为白)

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

gc_gc21

gc_gc22

gc_gc23

gc_gc24

gc_gc25

gc_gc26

gc_gc27

这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮GC中被清理掉。

Go V1.8的混合写屏障

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

  • 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
  • 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。

Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈re-scan的过程，极大的减少了STW的时间。结合了两者的优点。

混合写屏障规则

具体操作:

1、GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，

2、GC期间，任何在栈上创建的新对象，均为黑色。

3、被删除的对象标记为灰色。

4、被添加的对象标记为灰色。

满足: 变形的弱三色不变式.

注：这里我们注意， 屏障技术是不在栈上应用的，因为要保证栈的运行效率。

混合写屏障的具体场景

接下来，我们用几张图，来模拟整个一个详细的过程， 希望您能够更可观的看清晰整体流程。

注意混合写屏障是Gc的一种屏障机制，所以只是当程序执行GC的时候，才会触发这种机制。

GC开始：扫描栈区，将可达对象全部标记为黑

gc_gc28

gc_gc29

场景1

对象被一个堆对象删除引用，成为栈对象的下游

伪代码：

1
2
3
//前提：堆对象4->对象7 = 对象7；  //对象7 被 对象4引用
栈对象1->对象7 = 堆对象7；  //将堆对象7 挂在 栈对象1 下游
堆对象4->对象7 = null；    //对象4 删除引用 对象7

gc_gc30

gc_gc31

场景2

对象被一个栈对象删除引用，成为另一个栈对象的下游

伪代码：

1
2
3
new 栈对象9；
对象8->对象3 = 对象3；      //将栈对象3 挂在 栈对象9 下游
对象2->对象3 = null；      //对象2 删除引用 对象3

gc_gc32

gc_gc33

gc_gc34

场景3

对象被一个堆对象删除引用，成为另一个堆对象的下游

伪代码：

1
2
堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

gc_gc35

gc_gc36

gc_gc37

场景4

对象从一个栈对象删除引用，成为另一个堆对象的下游

伪代码：

1
2
堆对象10->对象7 = 堆对象7；       //将堆对象7 挂在 堆对象10 下游
堆对象4->对象7 = null；         //对象4 删除引用 对象7

gc_gc38

gc_gc39

gc_gc40

Golang中的混合写屏障满足弱三色不变式，结合了删除写屏障和插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行re-scan操作了，减少了STW的时间。

对象回收流程

根对象

在GC的标记阶段首先需要标记的就是”根对象”, 从根对象开始可到达的所有对象都会被认为是存活的.
根对象包含了全局变量, 各个G的栈上的变量等, GC会先扫描根对象然后再扫描根对象可到达的所有对象.
扫描根对象包含了一系列的工作

  • Fixed Roots: 特殊的扫描工作
    • fixedRootFinalizers: 扫描析构器队列
    • fixedRootFreeGStacks: 释放已中止的G的栈
  • Flush Cache Roots: 释放mcache中的所有span, 要求STW
  • Data Roots: 扫描可读写的全局变量
  • BSS Roots: 扫描只读的全局变量
  • Span Roots: 扫描各个span中特殊对象(析构器列表)
  • Stack Roots: 扫描各个G的栈

标记阶段(Mark)会做其中的”Fixed Roots”, “Data Roots”, “BSS Roots”, “Span Roots”, “Stack Roots”.
完成标记阶段(Mark Termination)会做其中的”Fixed Roots”, “Flush Cache Roots”.

标记队列

GC的标记阶段会使用”标记队列”来确定所有可从根对象到达的对象都已标记, 上面提到的”灰色”的对象就是在标记队列中的对象.
举例来说, 如果当前有[A, B, C]这三个根对象, 那么扫描根对象时就会把它们放到标记队列:

1
work queue: [A, B, C]

后台标记任务从标记队列中取出A, 如果A引用了D, 则把D放入标记队列:

1
work queue: [B, C, D]

后台标记任务从标记队列取出B, 如果B也引用了D, 这时因为D在gcmarkBits中对应的bit已经是1所以会跳过:

1
work queue: [C, D]

如果并行运行的go代码分配了一个对象E, 对象E会被立刻标记, 但不会进入标记队列(因为确定E没有引用其他对象).
然后并行运行的go代码把对象F设置给对象E的成员, 写屏障会标记对象F然后把对象F加到运行队列:

1
work queue: [C, D, F]

后台标记任务从标记队列取出C, 如果C没有引用其他对象, 则不需要处理:

1
work queue: [D, F]

后台标记任务从标记队列取出D, 如果D引用了X, 则把X放入标记队列:

1
work queue: [F, X]

后台标记任务从标记队列取出F, 如果F没有引用其他对象, 则不需要处理.
后台标记任务从标记队列取出X, 如果X没有引用其他对象, 则不需要处理.
最后标记队列为空, 标记完成, 存活的对象有[A, B, C, D, E, F, X].

当前1.9版本的 Go 以 STW 为界限，可以将 GC 划分为五个阶段：

阶段 说明 赋值器状态
SweepTermination 清扫终止阶段，为下一个阶段的并发标记做准备工作，启动写屏障 STW
Mark 扫描标记阶段，与赋值器并发执行，写屏障开启 并发
MarkTermination 标记终止阶段，保证一个周期内标记任务完成，停止写屏障 STW
GCoff 内存清扫阶段，将需要回收的内存归还到堆中，写屏障关闭 并发
GCoff 内存归还阶段，将过多的内存归还给操作系统，写屏障关闭 并发

完整的GC流程图示：

gc_gc41

源码分析

gcStart

go触发gc会从gcStart函数开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
func gcStart(mode gcMode, trigger gcTrigger) {
	// 判断当前G是否可抢占, 不可抢占时不触发GC
	mp := acquirem()
	if gp := getg(); gp == mp.g0 || mp.locks > 1 || mp.preemptoff != "" {
		releasem(mp)
		return
	}
	releasem(mp)
	mp = nil

	// 并行清扫上一轮GC未清扫的span
	for trigger.test() && gosweepone() != ^uintptr(0) {
		sweep.nbgsweep++
	}

	// 上锁, 然后重新检查gcTrigger的条件是否成立, 不成立时不触发GC
	// transition.
	semacquire(&work.startSema)
	// Re-check transition condition under transition lock.
	if !trigger.test() {
		semrelease(&work.startSema)
		return
	}

	// 记录是否强制触发, gcTriggerCycle是runtime.GC用的
	work.userForced = trigger.kind == gcTriggerAlways || trigger.kind == gcTriggerCycle

	// 判断是否指定了禁止并行GC的参数
	// start multiple STW GCs.
	if mode == gcBackgroundMode {
		if debug.gcstoptheworld == 1 {
			mode = gcForceMode
		} else if debug.gcstoptheworld == 2 {
			mode = gcForceBlockMode
		}
	}

	// Ok, we're doing it!  Stop everybody else
	semacquire(&worldsema)

	// 跟踪处理
	if trace.enabled {
		traceGCStart()
	}

	// 启动后台扫描任务(G)
	if mode == gcBackgroundMode {
		gcBgMarkStartWorkers()
	}

	// 重置标记相关的状态
	gcResetMarkState()

	// 重置参数
	work.stwprocs, work.maxprocs = gcprocs(), gomaxprocs
	work.heap0 = atomic.Load64(&memstats.heap_live)
	work.pauseNS = 0
	work.mode = mode

	// 记录开始时间
	now := nanotime()
	work.tSweepTerm = now
	work.pauseStart = now
	
	// 停止所有运行中的G, 并禁止它们运行
	systemstack(stopTheWorldWithSema)
	
	// !!!!!!!!!!!!!!!!
	// 世界已停止(STW)...
	// !!!!!!!!!!!!!!!!
	
	// 清扫上一轮GC未清扫的span, 确保上一轮GC已完成
	// Finish sweep before we start concurrent scan.
	systemstack(func() {
		finishsweep_m()
	})
	// 清扫sched.sudogcache和sched.deferpool
	clearpools()

	// 增加GC计数
	work.cycles++
	
	// 判断是否并行GC模式
	if mode == gcBackgroundMode { // Do as much work concurrently as possible
		// 标记新一轮GC已开始
		gcController.startCycle()
		work.heapGoal = memstats.next_gc

		// 设置全局变量中的GC状态为_GCmark
		// 然后启用写屏障
		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(startTheWorldWithSema)
		
		// !!!!!!!!!!!!!!!
		// 世界已重新启动...
		// !!!!!!!!!!!!!!!
		
		// 记录停止了多久, 和标记阶段开始的时间
		now = nanotime()
		work.pauseNS += now - work.pauseStart
		work.tMark = now
	} else {
		// 不是并行GC模式
		// 记录完成标记阶段开始的时间
		t := nanotime()
		work.tMark, work.tMarkTerm = t, t
		work.heapGoal = work.heap0

		// 跳过标记阶段, 执行完成标记阶段
		// 所有标记工作都会在世界已停止的状态执行
		// (标记阶段会设置work.markrootDone=true, 如果跳过则它的值是false, 完成标记阶段会执行所有工作)
		// 完成标记阶段会重新启动世界
		// Perform mark termination. This will restart the world.
		gcMarkTermination(memstats.triggerRatio)
	}

	semrelease(&work.startSema)
}

gcBgMarkStartWorkers

接下来一个个分析gcStart调用的函数, 建议配合上面的”回收对象的流程”中的图理解.

gcBgMarkStartWorkers函数用于启动后台标记任务, 先分别对每个P启动一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func gcBgMarkStartWorkers() {
	for _, p := range &allp {
		if p == nil || p.status == _Pdead {
			break
		}
		// 如果已启动则不重复启动
		if p.gcBgMarkWorker == 0 {
			go gcBgMarkWorker(p)
			// 启动后等待该任务通知信号量bgMarkReady再继续
			notetsleepg(&work.bgMarkReady, -1)
			noteclear(&work.bgMarkReady)
		}
	}
}

stopTheWorldWithSema

stopTheWorldWithSema函数会停止整个世界, 这个函数必须在g0中运行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
func stopTheWorldWithSema() {
	_g_ := getg()
	if _g_.m.locks > 0 {
		throw("stopTheWorld: holding locks")
	}

	lock(&sched.lock)
	
	// 需要停止的P数量
	sched.stopwait = gomaxprocs
	
	// 设置gc等待标记, 调度时看见此标记会进入等待
	atomic.Store(&sched.gcwaiting, 1)
	
	// 抢占所有运行中的G
	preemptall()
	
	// 停止当前的P
	// stop current P
	_g_.m.p.ptr().status = _Pgcstop // Pgcstop is only diagnostic.
	
	// 减少需要停止的P数量(当前的P算一个)
	sched.stopwait--
	
	// 抢占所有在Psyscall状态的P, 防止它们重新参与调度
	// try to retake all P's in Psyscall status
	for i := 0; i < int(gomaxprocs); i++ {
		p := allp[i]
		s := p.status
		if s == _Psyscall && atomic.Cas(&p.status, s, _Pgcstop) {
			if trace.enabled {
				traceGoSysBlock(p)
				traceProcStop(p)
			}
			p.syscalltick++
			sched.stopwait--
		}
	}
	
	// 防止所有空闲的P重新参与调度
	// stop idle P's
	for {
		p := pidleget()
		if p == nil {
			break
		}
		p.status = _Pgcstop
		sched.stopwait--
	}
	wait := sched.stopwait > 0
	unlock(&sched.lock)

	// 如果仍有需要停止的P, 则等待它们停止
	// wait for remaining P's to stop voluntarily
	if wait {
		for {
			// 循环等待 + 抢占所有运行中的G
			// wait for 100us, then try to re-preempt in case of any races
			if notetsleep(&sched.stopnote, 100*1000) {
				noteclear(&sched.stopnote)
				break
			}
			preemptall()
		}
	}

	// 逻辑正确性检查
	// sanity checks
	bad := ""
	if sched.stopwait != 0 {
		bad = "stopTheWorld: not stopped (stopwait != 0)"
	} else {
		for i := 0; i < int(gomaxprocs); i++ {
			p := allp[i]
			if p.status != _Pgcstop {
				bad = "stopTheWorld: not stopped (status != _Pgcstop)"
			}
		}
	}
	if atomic.Load(&freezing) != 0 {
		lock(&deadlock)
		lock(&deadlock)
	}
	if bad != "" {
		throw(bad)
	}
	
	// 到这里所有运行中的G都会变为待运行, 并且所有的P都不能被M获取
	// 也就是说所有的go代码(除了当前的)都会停止运行, 并且不能运行新的go代码
}

finishsweep_m

finishsweep_m函数会清扫上一轮GC未清扫的span, 确保上一轮GC已完成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func finishsweep_m() {
	// sweepone会取出一个未sweep的span然后执行sweep
	// 详细将在下面sweep阶段时分析
	for sweepone() != ^uintptr(0) {
		sweep.npausesweep++
	}

	// 所有span都sweep完成后, 启动一个新的markbit时代
	// 这个函数是实现span的gcmarkBits和allocBits的分配和复用的关键, 流程如下
	// - span分配gcmarkBits和allocBits
	// - span完成sweep
	//   - 原allocBits不再被使用
	//   - gcmarkBits变为allocBits
	//   - 分配新的gcmarkBits
	// - 开启新的markbit时代
	// - span完成sweep, 同上
	// - 开启新的markbit时代
	//   - 2个时代之前的bitmap将不再被使用, 可以复用这些bitmap
	nextMarkBitArenaEpoch()
}

gcBgMarkPrepare

gcBgMarkPrepare函数会重置后台标记任务的计数:

1
2
3
4
func gcBgMarkPrepare() {
	work.nproc = ^uint32(0)
	work.nwait = ^uint32(0)
}

gcMarkRootPrepare

函数会计算扫描根对象的任务数量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
func gcMarkRootPrepare() {
	// 释放mcache中的所有span的任务, 只在完成标记阶段(mark termination)中执行
	if gcphase == _GCmarktermination {
		work.nFlushCacheRoots = int(gomaxprocs)
	} else {
		work.nFlushCacheRoots = 0
	}

	// 计算block数量的函数, rootBlockBytes是256KB
	// Compute how many data and BSS root blocks there are.
	nBlocks := func(bytes uintptr) int {
		return int((bytes + rootBlockBytes - 1) / rootBlockBytes)
	}

	work.nDataRoots = 0
	work.nBSSRoots = 0

	// data和bss每一轮GC只扫描一次
	// 并行GC中会在后台标记任务中扫描, 完成标记阶段(mark termination)中不扫描
	// 非并行GC会在完成标记阶段(mark termination)中扫描
	// Only scan globals once per cycle; preferably concurrently.
	if !work.markrootDone {
		// 计算扫描可读写的全局变量的任务数量
		for _, datap := range activeModules() {
			nDataRoots := nBlocks(datap.edata - datap.data)
			if nDataRoots > work.nDataRoots {
				work.nDataRoots = nDataRoots
			}
		}

		// 计算扫描只读的全局变量的任务数量
		for _, datap := range activeModules() {
			nBSSRoots := nBlocks(datap.ebss - datap.bss)
			if nBSSRoots > work.nBSSRoots {
				work.nBSSRoots = nBSSRoots
			}
		}
	}

	// span中的finalizer和各个G的栈每一轮GC只扫描一次
	// 同上
	if !work.markrootDone {
		// 计算扫描span中的finalizer的任务数量
		work.nSpanRoots = mheap_.sweepSpans[mheap_.sweepgen/2%2].numBlocks()

		// 计算扫描各个G的栈的任务数量
		work.nStackRoots = int(atomic.Loaduintptr(&allglen))
	} else {
		work.nSpanRoots = 0
		work.nStackRoots = 0

		if debug.gcrescanstacks > 0 {
			// Scan stacks anyway for debugging.
			work.nStackRoots = int(atomic.Loaduintptr(&allglen))
		}
	}

	// 计算总任务数量
	// 后台标记任务会对markrootNext进行原子递增, 来决定做哪个任务
	// 这种用数值来实现锁自由队列的办法挺聪明的, 尽管google工程师觉得不好(看后面markroot函数的分析)
	work.markrootNext = 0
	work.markrootJobs = uint32(fixedRootCount + work.nFlushCacheRoots + work.nDataRoots + work.nBSSRoots + work.nSpanRoots + work.nStackRoots)
}

gcMarkTinyAllocs

函数会标记所有tiny alloc等待合并的对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func gcMarkTinyAllocs() {
	for _, p := range &allp {
		if p == nil || p.status == _Pdead {
			break
		}
		c := p.mcache
		if c == nil || c.tiny == 0 {
			continue
		}
		// 标记各个P中的mcache中的tiny
		// 在上面的mallocgc函数中可以看到tiny是当前等待合并的对象
		_, hbits, span, objIndex := heapBitsForObject(c.tiny, 0, 0)
		gcw := &p.gcw
		// 标记一个对象存活, 并把它加到标记队列(该对象变为灰色)
		greyobject(c.tiny, 0, 0, hbits, span, gcw, objIndex)
		// gcBlackenPromptly变量表示当前是否禁止本地队列, 如果已禁止则把标记任务flush到全局队列
		if gcBlackenPromptly {
			gcw.dispose()
		}
	}
}

startTheWorldWithSema

startTheWorldWithSema函数会重新启动世界:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
func startTheWorldWithSema() {
	_g_ := getg()
	
	// 禁止G被抢占
	_g_.m.locks++        // disable preemption because it can be holding p in a local var
	
	// 判断收到的网络事件(fd可读可写或错误)并添加对应的G到待运行队列
	gp := netpoll(false) // non-blocking
	injectglist(gp)
	
	// 判断是否要启动gc helper
	add := needaddgcproc()
	lock(&sched.lock)
	
	// 如果要求改变gomaxprocs则调整P的数量
	// procresize会返回有可运行任务的P的链表
	procs := gomaxprocs
	if newprocs != 0 {
		procs = newprocs
		newprocs = 0
	}
	p1 := procresize(procs)
	
	// 取消GC等待标记
	sched.gcwaiting = 0
	
	// 如果sysmon在等待则唤醒它
	if sched.sysmonwait != 0 {
		sched.sysmonwait = 0
		notewakeup(&sched.sysmonnote)
	}
	unlock(&sched.lock)
	
	// 唤醒有可运行任务的P
	for p1 != nil {
		p := p1
		p1 = p1.link.ptr()
		if p.m != 0 {
			mp := p.m.ptr()
			p.m = 0
			if mp.nextp != 0 {
				throw("startTheWorld: inconsistent mp->nextp")
			}
			mp.nextp.set(p)
			notewakeup(&mp.park)
		} else {
			// Start M to run P.  Do not start another M below.
			newm(nil, p)
			add = false
		}
	}
	
	// 如果有空闲的P，并且没有自旋中的M则唤醒或者创建一个M
	if atomic.Load(&sched.npidle) != 0 && atomic.Load(&sched.nmspinning) == 0 {
		wakep()
	}
	
	// 启动gc helper
	if add {
		newm(mhelpgc, nil)
	}
	
	// 允许G被抢占
	_g_.m.locks--
	
	// 如果当前G要求被抢占则重新尝试
	if _g_.m.locks == 0 && _g_.preempt { // restore the preemption request in case we've cleared it in newstack
		_g_.stackguard0 = stackPreempt
	}
}

gcBgMarkWorker

重启世界后各个M会重新开始调度, 调度时会优先使用上面提到的findRunnableGCWorker函数查找任务, 之后就有大约25%的P运行后台标记任务.
后台标记任务的函数是gcBgMarkWorker

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
func gcBgMarkWorker(_p_ *p) {
	gp := getg()
	
	// 用于休眠后重新获取P的构造体
	type parkInfo struct {
		m      muintptr // Release this m on park.
		attach puintptr // If non-nil, attach to this p on park.
	}
	gp.m.preemptoff = "GC worker init"
	park := new(parkInfo)
	gp.m.preemptoff = ""
	
	// 设置当前的M并禁止抢占
	park.m.set(acquirem())
	// 设置当前的P(需要关联到的P)
	park.attach.set(_p_)
	
	// 通知gcBgMarkStartWorkers可以继续处理
	notewakeup(&work.bgMarkReady)
	
	for {
		// 让当前G进入休眠
		gopark(func(g *g, parkp unsafe.Pointer) bool {
			park := (*parkInfo)(parkp)
			
			// 重新允许抢占
			releasem(park.m.ptr())
			
			// 设置关联的P
			// 把当前的G设到P的gcBgMarkWorker成员, 下次findRunnableGCWorker会使用
			// 设置失败时不休眠
			if park.attach != 0 {
				p := park.attach.ptr()
				park.attach.set(nil)
				if !p.gcBgMarkWorker.cas(0, guintptr(unsafe.Pointer(g))) {
					return false
				}
			}
			return true
		}, unsafe.Pointer(park), "GC worker (idle)", traceEvGoBlock, 0)
		
		// 检查P的gcBgMarkWorker是否和当前的G一致, 不一致时结束当前的任务
		if _p_.gcBgMarkWorker.ptr() != gp {
			break
		}
		
		// 禁止G被抢占
		park.m.set(acquirem())
		
		if gcBlackenEnabled == 0 {
			throw("gcBgMarkWorker: blackening not enabled")
		}
		
		// 记录开始时间
		startTime := nanotime()
		
		decnwait := atomic.Xadd(&work.nwait, -1)
		if decnwait == work.nproc {
			println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
			throw("work.nwait was > work.nproc")
		}
		
		// 切换到g0运行
		systemstack(func() {
			// 设置G的状态为等待中这样它的栈可以被扫描(两个后台标记任务可以互相扫描对方的栈)
			casgstatus(gp, _Grunning, _Gwaiting)
			
			// 判断后台标记任务的模式
			switch _p_.gcMarkWorkerMode {
			default:
				throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
			case gcMarkWorkerDedicatedMode:
				// 这个模式下P应该专心执行标记
				// 执行标记, 直到被抢占, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
				gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
				// 被抢占时把本地运行队列中的所有G都踢到全局运行队列
				if gp.preempt {
					lock(&sched.lock)
					for {
						gp, _ := runqget(_p_)
						if gp == nil {
							break
						}
						globrunqput(gp)
					}
					unlock(&sched.lock)
				}
				// 继续执行标记, 直到无更多任务, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
				// Go back to draining, this time
				// without preemption.
				gcDrain(&_p_.gcw, gcDrainNoBlock|gcDrainFlushBgCredit)
			case gcMarkWorkerFractionalMode:
				// 这个模式下P应该适当执行标记
				// 执行标记, 直到被抢占, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
				gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
			case gcMarkWorkerIdleMode:
				// 这个模式下P只在空闲时执行标记
				// 执行标记, 直到被抢占或者达到一定的量, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
				gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
			}
			
			// 恢复G的状态到运行中
			casgstatus(gp, _Gwaiting, _Grunning)
		})
		
		// 如果标记了禁止本地标记队列则flush到全局标记队列
		if gcBlackenPromptly {
			_p_.gcw.dispose()
		}
		
		// 累加所用时间
		duration := nanotime() - startTime
		switch _p_.gcMarkWorkerMode {
		case gcMarkWorkerDedicatedMode:
			atomic.Xaddint64(&gcController.dedicatedMarkTime, duration)
			atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 1)
		case gcMarkWorkerFractionalMode:
			atomic.Xaddint64(&gcController.fractionalMarkTime, duration)
			atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, 1)
		case gcMarkWorkerIdleMode:
			atomic.Xaddint64(&gcController.idleMarkTime, duration)
		}
		
		incnwait := atomic.Xadd(&work.nwait, +1)
		if incnwait > work.nproc {
			println("runtime: p.gcMarkWorkerMode=", _p_.gcMarkWorkerMode,
				"work.nwait=", incnwait, "work.nproc=", work.nproc)
			throw("work.nwait > work.nproc")
		}
		
		// 判断是否所有后台标记任务都完成, 并且没有更多的任务
		if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
			// 取消和P的关联
			_p_.gcBgMarkWorker.set(nil)
			
			// 允许G被抢占
			releasem(park.m.ptr())
			
			// 准备进入完成标记阶段
			gcMarkDone()
			
			// 休眠之前会重新关联P
			// 因为上面允许被抢占, 到这里的时候可能就会变成其他P
			// 如果重新关联P失败则这个任务会结束
			park.m.set(acquirem())
			park.attach.set(_p_)
		}
	}
}

gcDrain

函数用于执行标记:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
	if !writeBarrier.needed {
		throw("gcDrain phase incorrect")
	}
	
	gp := getg().m.curg
	
	// 看到抢占标志时是否要返回
	preemptible := flags&gcDrainUntilPreempt != 0
	
	// 没有任务时是否要等待任务
	blocking := flags&(gcDrainUntilPreempt|gcDrainIdle|gcDrainNoBlock) == 0
	
	// 是否计算后台的扫描量来减少辅助GC和唤醒等待中的G
	flushBgCredit := flags&gcDrainFlushBgCredit != 0
	
	// 是否只执行一定量的工作
	idle := flags&gcDrainIdle != 0
	
	// 记录初始的已扫描数量
	initScanWork := gcw.scanWork
	
	// 扫描idleCheckThreshold(100000)个对象以后检查是否要返回
	idleCheck := initScanWork + idleCheckThreshold
	
	// 如果根对象未扫描完, 则先扫描根对象
	// Drain root marking jobs.
	if work.markrootNext < work.markrootJobs {
		// 如果标记了preemptible, 循环直到被抢占
		for !(preemptible && gp.preempt) {
			// 从根对象扫描队列取出一个值(原子递增)
			job := atomic.Xadd(&work.markrootNext, +1) - 1
			if job >= work.markrootJobs {
				break
			}
			// 执行根对象扫描工作
			markroot(gcw, job)
			// 如果是idle模式并且有其他工作, 则返回
			if idle && pollWork() {
				goto done
			}
		}
	}
	
	// 根对象已经在标记队列中, 消费标记队列
	// 如果标记了preemptible, 循环直到被抢占
	// Drain heap marking jobs.
	for !(preemptible && gp.preempt) {
		// 如果全局标记队列为空, 把本地标记队列的一部分工作分过去
		// (如果wbuf2不为空则移动wbuf2过去, 否则移动wbuf1的一半过去)
		if work.full == 0 {
			gcw.balance()
		}
		
		// 从本地标记队列中获取对象, 获取不到则从全局标记队列获取
		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)
		
		// 如果已经扫描了一定数量的对象(gcCreditSlack的值是2000)
		if gcw.scanWork >= gcCreditSlack {
			// 把扫描的对象数量添加到全局
			atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
			// 减少辅助GC的工作量和唤醒等待中的G
			if flushBgCredit {
				gcFlushBgCredit(gcw.scanWork - initScanWork)
				initScanWork = 0
			}
			idleCheck -= gcw.scanWork
			gcw.scanWork = 0
			
			// 如果是idle模式且达到了检查的扫描量, 则检查是否有其他任务(G), 如果有则跳出循环
			if idle && idleCheck <= 0 {
				idleCheck += idleCheckThreshold
				if pollWork() {
					break
				}
			}
		}
	}
	
done:
	// 把扫描的对象数量添加到全局
	// Flush remaining scan work credit.
	if gcw.scanWork > 0 {
		atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
		// 减少辅助GC的工作量和唤醒等待中的G
		if flushBgCredit {
			gcFlushBgCredit(gcw.scanWork - initScanWork)
		}
		gcw.scanWork = 0
	}
}

markroot

markroot 函数用于执行根对象扫描工作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
func markroot(gcw *gcWork, i uint32) {
	// 判断取出的数值对应哪种任务
	// (google的工程师觉得这种办法可笑)
	baseFlushCache := uint32(fixedRootCount)
	baseData := baseFlushCache + uint32(work.nFlushCacheRoots)
	baseBSS := baseData + uint32(work.nDataRoots)
	baseSpans := baseBSS + uint32(work.nBSSRoots)
	baseStacks := baseSpans + uint32(work.nSpanRoots)
	end := baseStacks + uint32(work.nStackRoots)

	switch {
	// 释放mcache中的所有span, 要求STW
	case baseFlushCache <= i && i < baseData:
		flushmcache(int(i - baseFlushCache))

	// 扫描可读写的全局变量
	// 这里只会扫描i对应的block, 扫描时传入包含哪里有指针的bitmap数据
	case baseData <= i && i < baseBSS:
		for _, datap := range activeModules() {
			markrootBlock(datap.data, datap.edata-datap.data, datap.gcdatamask.bytedata, gcw, int(i-baseData))
		}

	// 扫描只读的全局变量
	// 这里只会扫描i对应的block, 扫描时传入包含哪里有指针的bitmap数据
	case baseBSS <= i && i < baseSpans:
		for _, datap := range activeModules() {
			markrootBlock(datap.bss, datap.ebss-datap.bss, datap.gcbssmask.bytedata, gcw, int(i-baseBSS))
		}

	// 扫描析构器队列
	case i == fixedRootFinalizers:
		if work.markrootDone {
			break
		}
		for fb := allfin; fb != nil; fb = fb.alllink {
			cnt := uintptr(atomic.Load(&fb.cnt))
			scanblock(uintptr(unsafe.Pointer(&fb.fin[0])), cnt*unsafe.Sizeof(fb.fin[0]), &finptrmask[0], gcw)
		}

	// 释放已中止的G的栈
	case i == fixedRootFreeGStacks:
		if !work.markrootDone {
			systemstack(markrootFreeGStacks)
		}

	// 扫描各个span中特殊对象(析构器列表)
	case baseSpans <= i && i < baseStacks:
		// mark MSpan.specials
		markrootSpans(gcw, int(i-baseSpans))

	// 扫描各个G的栈
	default:
		// 获取需要扫描的G
		var gp *g
		if baseStacks <= i && i < end {
			gp = allgs[i-baseStacks]
		} else {
			throw("markroot: bad index")
		}

		// 记录等待开始的时间
		if (status == _Gwaiting || status == _Gsyscall) && gp.waitsince == 0 {
			gp.waitsince = work.tstart
		}

		// 切换到g0运行(有可能会扫到自己的栈)
		systemstack(func() {
			// 判断扫描的栈是否自己的
			userG := getg().m.curg
			selfScan := gp == userG && readgstatus(userG) == _Grunning
			
			// 如果正在扫描自己的栈则切换状态到等待中防止死锁
			if selfScan {
				casgstatus(userG, _Grunning, _Gwaiting)
				userG.waitreason = "garbage collection scan"
			}
			
			// 扫描G的栈
			scang(gp, gcw)
			
			// 如果正在扫描自己的栈则把状态切换回运行中
			if selfScan {
				casgstatus(userG, _Gwaiting, _Grunning)
			}
		})
	}
}

scang

scang函数负责扫描G的栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
func scang(gp *g, gcw *gcWork) {

	// 标记扫描未完成
	gp.gcscandone = false

	const yieldDelay = 10 * 1000
	var nextYield int64

	// 循环直到扫描完成
loop:
	for i := 0; !gp.gcscandone; i++ {
		// 判断G的当前状态
		switch s := readgstatus(gp); s {
		default:
			dumpgstatus(gp)
			throw("stopg: invalid status")

		// G已中止, 不需要扫描它
		case _Gdead:
			// No stack.
			gp.gcscandone = true
			break loop

		// G的栈正在扩展, 下一轮重试
		case _Gcopystack:
		// Stack being switched. Go around again.

		// G不是运行中, 首先需要防止它运行
		case _Grunnable, _Gsyscall, _Gwaiting:
			if castogscanstatus(gp, s, s|_Gscan) {
				// 原子切换状态成功时扫描它的栈
				if !gp.gcscandone {
					scanstack(gp, gcw)
					gp.gcscandone = true
				}
				// 恢复G的状态, 并跳出循环
				restartg(gp)
				break loop
			}

		// G正在扫描它自己, 等待扫描完毕
		case _Gscanwaiting:
		// newstack is doing a scan for us right now. Wait.

		// G正在运行
		case _Grunning:
			// 如果已经有抢占请求, 则抢占成功时会帮我们处理
			if gp.preemptscan && gp.preempt && gp.stackguard0 == stackPreempt {
				break
			}

			// 抢占G, 抢占成功时G会扫描它自己
			// Ask for preemption and self scan.
			if castogscanstatus(gp, _Grunning, _Gscanrunning) {
				if !gp.gcscandone {
					gp.preemptscan = true
					gp.preempt = true
					gp.stackguard0 = stackPreempt
				}
				casfrom_Gscanstatus(gp, _Gscanrunning, _Grunning)
			}
		}

		// 第一轮休眠10毫秒, 第二轮休眠5毫秒
		if i == 0 {
			nextYield = nanotime() + yieldDelay
		}
		if nanotime() < nextYield {
			procyield(10)
		} else {
			osyield()
			nextYield = nanotime() + yieldDelay/2
		}
	}

	// 扫描完成, 取消抢占扫描的请求
	gp.preemptscan = false // cancel scan request if no longer needed
}

gcMarkDone

在所有后台标记任务都把标记队列消费完毕时, 会执行gcMarkDone函数准备进入完成标记阶段(mark termination):
在并行GC中gcMarkDone会被执行两次, 第一次会禁止本地标记队列然后重新开始后台标记任务, 第二次会进入完成标记阶段(mark termination)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
func gcMarkDone() {
top:
	semacquire(&work.markDoneSema)
	if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
		semrelease(&work.markDoneSema)
		return
	}

	// 暂时禁止启动新的后台标记任务
	atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff)
	atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, -0xffffffff)

	// 判断本地标记队列是否已禁用
	if !gcBlackenPromptly {
		// 本地标记队列是否未禁用, 禁用然后重新开始后台标记任务

		// 禁用本地标记队列
		gcBlackenPromptly = true

		atomic.Xadd(&work.nwait, -1)

		semrelease(&work.markDoneSema)

		// 把所有本地标记队列中的对象都推到全局标记队列
		systemstack(func() {
			forEachP(func(_p_ *p) {
				_p_.gcw.dispose()
			})
		})

		// 除错用
		gcMarkRootCheck()

		// 允许启动新的后台标记任务
		atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 0xffffffff)
		atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, 0xffffffff)

		// 如果确定没有更多的任务则可以直接跳到函数顶部
		// 这样就当作是第二次调用了
		incnwait := atomic.Xadd(&work.nwait, +1)
		if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
			goto top
		}
	} else {
		// 记录完成标记阶段开始的时间和STW开始的时间
		now := nanotime()
		work.tMarkTerm = now
		work.pauseStart = now
		
		// 禁止G被抢占
		getg().m.preemptoff = "gcing"
		
		// 停止所有运行中的G, 并禁止它们运行
		systemstack(stopTheWorldWithSema)
		
		// !!!!!!!!!!!!!!!!
		// 世界已停止(STW)...
		// !!!!!!!!!!!!!!!!
		
		// 标记对根对象的扫描已完成, 会影响gcMarkRootPrepare中的处理
		work.markrootDone = true
		
		// 禁止辅助GC和后台标记任务的运行
		atomic.Store(&gcBlackenEnabled, 0)
		
		// 唤醒所有因为辅助GC而休眠的G
		gcWakeAllAssists()
		semrelease(&work.markDoneSema)
		
		// 计算下一次触发gc需要的heap大小
		nextTriggerRatio := gcController.endCycle()
		
		// 进入完成标记阶段, 会重新启动世界
		gcMarkTermination(nextTriggerRatio)
	}
}

gcMarkTermination

gcMarkTermination函数会进入完成标记阶段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
func gcMarkTermination(nextTriggerRatio float64) {
	// World is stopped.
	// Start marktermination which includes enabling the write barrier.
	// 禁止辅助GC和后台标记任务的运行
	atomic.Store(&gcBlackenEnabled, 0)
	
	// 重新允许本地标记队列(下次GC使用)
	gcBlackenPromptly = false
	
	// 设置当前GC阶段到完成标记阶段, 并启用写屏障
	setGCPhase(_GCmarktermination)

	// 记录开始时间
	work.heap1 = memstats.heap_live
	startTime := nanotime()

	// 禁止G被抢占
	mp := acquirem()
	mp.preemptoff = "gcing"
	_g_ := getg()
	_g_.m.traceback = 2
	
	// 设置G的状态为等待中这样它的栈可以被扫描
	gp := _g_.m.curg
	casgstatus(gp, _Grunning, _Gwaiting)
	gp.waitreason = "garbage collection"

	// 切换到g0运行
	systemstack(func() {
		// 开始STW中的标记
		gcMark(startTime)
		
		// 必须立刻返回, 因为外面的G的栈有可能被移动, 不能在这之后访问外面的变量
	})

	// 重新切换到g0运行
	systemstack(func() {
		work.heap2 = work.bytesMarked
		
		// 如果启用了checkmark则执行检查, 检查是否所有可到达的对象都有标记
		if debug.gccheckmark > 0 {
			gcResetMarkState()
			initCheckmarks()
			gcMark(startTime)
			clearCheckmarks()
		}

		// 设置当前GC阶段到关闭, 并禁用写屏障
		// marking is complete so we can turn the write barrier off
		setGCPhase(_GCoff)
		
		// 唤醒后台清扫任务, 将在STW结束后开始运行
		gcSweep(work.mode)

		// 除错用
		if debug.gctrace > 1 {
			startTime = nanotime()
			gcResetMarkState()
			finishsweep_m()

			// Still in STW but gcphase is _GCoff, reset to _GCmarktermination
			// At this point all objects will be found during the gcMark which
			// does a complete STW mark and object scan.
			setGCPhase(_GCmarktermination)
			gcMark(startTime)
			setGCPhase(_GCoff) // marking is done, turn off wb.
			gcSweep(work.mode)
		}
	})

	// 设置G的状态为运行中
	_g_.m.traceback = 0
	casgstatus(gp, _Gwaiting, _Grunning)

	// 跟踪处理
	if trace.enabled {
		traceGCDone()
	}

	// all done
	mp.preemptoff = ""

	if gcphase != _GCoff {
		throw("gc done but gcphase != _GCoff")
	}

	// 更新下一次触发gc需要的heap大小(gc_trigger)
	gcSetTriggerRatio(nextTriggerRatio)

	// 更新用时记录
	// Update timing memstats
	now := nanotime()
	sec, nsec, _ := time_now()
	unixNow := sec*1e9 + int64(nsec)
	work.pauseNS += now - work.pauseStart
	work.tEnd = now
	atomic.Store64(&memstats.last_gc_unix, uint64(unixNow)) // must be Unix time to make sense to user
	atomic.Store64(&memstats.last_gc_nanotime, uint64(now)) // monotonic time for us
	memstats.pause_ns[memstats.numgc%uint32(len(memstats.pause_ns))] = uint64(work.pauseNS)
	memstats.pause_end[memstats.numgc%uint32(len(memstats.pause_end))] = uint64(unixNow)
	memstats.pause_total_ns += uint64(work.pauseNS)

	// 更新所用cpu记录
	sweepTermCpu := int64(work.stwprocs) * (work.tMark - work.tSweepTerm)
	markCpu := gcController.assistTime + gcController.dedicatedMarkTime + gcController.fractionalMarkTime
	markTermCpu := int64(work.stwprocs) * (work.tEnd - work.tMarkTerm)
	cycleCpu := sweepTermCpu + markCpu + markTermCpu
	work.totaltime += cycleCpu

	totalCpu := sched.totaltime + (now-sched.procresizetime)*int64(gomaxprocs)
	memstats.gc_cpu_fraction = float64(work.totaltime) / float64(totalCpu)

	// 重置清扫状态
	// Reset sweep state.
	sweep.nbgsweep = 0
	sweep.npausesweep = 0

	// 统计强制开始GC的次数
	if work.userForced {
		memstats.numforcedgc++
	}

	// 统计执行GC的次数然后唤醒等待清扫的G
	lock(&work.sweepWaiters.lock)
	memstats.numgc++
	injectglist(work.sweepWaiters.head.ptr())
	work.sweepWaiters.head = 0
	unlock(&work.sweepWaiters.lock)

	// 性能统计用
	mProf_NextCycle()

	// 重新启动世界
	systemstack(startTheWorldWithSema)

	// !!!!!!!!!!!!!!!
	// 世界已重新启动...
	// !!!!!!!!!!!!!!!

	// 性能统计用
	mProf_Flush()

	// 移动标记队列使用的缓冲区到自由列表, 使得它们可以被回收
	prepareFreeWorkbufs()

	// 释放未使用的栈
	systemstack(freeStackSpans)

	// 除错用
	if debug.gctrace > 0 {
		util := int(memstats.gc_cpu_fraction * 100)

		var sbuf [24]byte
		printlock()
		print("gc ", memstats.numgc,
			" @", string(itoaDiv(sbuf[:], uint64(work.tSweepTerm-runtimeInitTime)/1e6, 3)), "s ",
			util, "%: ")
		prev := work.tSweepTerm
		for i, ns := range []int64{work.tMark, work.tMarkTerm, work.tEnd} {
			if i != 0 {
				print("+")
			}
			print(string(fmtNSAsMS(sbuf[:], uint64(ns-prev))))
			prev = ns
		}
		print(" ms clock, ")
		for i, ns := range []int64{sweepTermCpu, gcController.assistTime, gcController.dedicatedMarkTime + gcController.fractionalMarkTime, gcController.idleMarkTime, markTermCpu} {
			if i == 2 || i == 3 {
				// Separate mark time components with /.
				print("/")
			} else if i != 0 {
				print("+")
			}
			print(string(fmtNSAsMS(sbuf[:], uint64(ns))))
		}
		print(" ms cpu, ",
			work.heap0>>20, "->", work.heap1>>20, "->", work.heap2>>20, " MB, ",
			work.heapGoal>>20, " MB goal, ",
			work.maxprocs, " P")
		if work.userForced {
			print(" (forced)")
		}
		print("\n")
		printunlock()
	}

	semrelease(&worldsema)

	// 重新允许当前的G被抢占
	releasem(mp)
	mp = nil

	// 如果是并行GC, 让当前M继续运行(会回到gcBgMarkWorker然后休眠)
	// 如果不是并行GC, 则让当前M开始调度
	if !concurrentSweep {
		Gosched()
	}
}

gcSweep

函数会唤醒后台清扫任务:
后台清扫任务会在程序启动时调用的gcenable函数中启动.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func gcSweep(mode gcMode) {
	if gcphase != _GCoff {
		throw("gcSweep being done but phase is not GCoff")
	}

	// 增加sweepgen, 这样sweepSpans中两个队列角色会交换, 所有span都会变为"待清扫"的span
	lock(&mheap_.lock)
	mheap_.sweepgen += 2
	mheap_.sweepdone = 0
	if mheap_.sweepSpans[mheap_.sweepgen/2%2].index != 0 {
		// We should have drained this list during the last
		// sweep phase. We certainly need to start this phase
		// with an empty swept list.
		throw("non-empty swept list")
	}
	mheap_.pagesSwept = 0
	unlock(&mheap_.lock)

	// 如果非并行GC则在这里完成所有工作(STW中)
	if !_ConcurrentSweep || mode == gcForceBlockMode {
		// Special case synchronous sweep.
		// Record that no proportional sweeping has to happen.
		lock(&mheap_.lock)
		mheap_.sweepPagesPerByte = 0
		unlock(&mheap_.lock)
		// Sweep all spans eagerly.
		for sweepone() != ^uintptr(0) {
			sweep.npausesweep++
		}
		// Free workbufs eagerly.
		prepareFreeWorkbufs()
		for freeSomeWbufs(false) {
		}
		mProf_NextCycle()
		mProf_Flush()
		return
	}

	// 唤醒后台清扫任务
	lock(&sweep.lock)
	if sweep.parked {
		sweep.parked = false
		ready(sweep.g, 0, true)
	}
	unlock(&sweep.lock)
}

bgsweep

后台清扫任务的函数是bgsweep

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 {
		// 清扫一个span, 然后进入调度(一次只做少量工作)
		for gosweepone() != ^uintptr(0) {
			sweep.nbgsweep++
			Gosched()
		}
		// 释放一些未使用的标记队列缓冲区到heap
		for freeSomeWbufs(true) {
			Gosched()
		}
		// 如果清扫未完成则继续循环
		lock(&sweep.lock)
		if !gosweepdone() {
			unlock(&sweep.lock)
			continue
		}
		// 否则让后台清扫任务进入休眠, 当前M继续调度
		sweep.parked = true
		goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
	}
}

gosweepone

函数会从sweepSpans中取出单个span清扫:

1
2
3
4
5
6
7
8
9
//go:nowritebarrier
func gosweepone() uintptr {
	var ret uintptr
	// 切换到g0运行
	systemstack(func() {
		ret = sweepone()
	})
	return ret
}

sweepone

sweepone 函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
func sweepone() uintptr {
	_g_ := getg()
	sweepRatio := mheap_.sweepPagesPerByte // For debugging

	// 禁止G被抢占
	// increment locks to ensure that the goroutine is not preempted
	// in the middle of sweep thus leaving the span in an inconsistent state for next GC
	_g_.m.locks++
	
	// 检查是否已完成清扫
	if atomic.Load(&mheap_.sweepdone) != 0 {
		_g_.m.locks--
		return ^uintptr(0)
	}
	
	// 更新同时执行sweep的任务数量
	atomic.Xadd(&mheap_.sweepers, +1)

	npages := ^uintptr(0)
	sg := mheap_.sweepgen
	for {
		// 从sweepSpans中取出一个span
		s := mheap_.sweepSpans[1-sg/2%2].pop()
		// 全部清扫完毕时跳出循环
		if s == nil {
			atomic.Store(&mheap_.sweepdone, 1)
			break
		}
		// 其他M已经在清扫这个span时跳过
		if s.state != mSpanInUse {
			// This can happen if direct sweeping already
			// swept this span, but in that case the sweep
			// generation should always be up-to-date.
			if s.sweepgen != sg {
				print("runtime: bad span s.state=", s.state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n")
				throw("non in-use span in unswept list")
			}
			continue
		}
		// 原子增加span的sweepgen, 失败表示其他M已经开始清扫这个span, 跳过
		if s.sweepgen != sg-2 || !atomic.Cas(&s.sweepgen, sg-2, sg-1) {
			continue
		}
		// 清扫这个span, 然后跳出循环
		npages = s.npages
		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
		}
		break
	}

	// 更新同时执行sweep的任务数量
	// Decrement the number of active sweepers and if this is the
	// last one print trace information.
	if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 {
		if debug.gcpacertrace > 0 {
			print("pacer: sweep done at heap size ", memstats.heap_live>>20, "MB; allocated ", (memstats.heap_live-mheap_.sweepHeapLiveBasis)>>20, "MB during sweep; swept ", mheap_.pagesSwept, " pages at ", sweepRatio, " pages/byte\n")
		}
	}
	// 允许G被抢占
	_g_.m.locks--
	// 返回清扫的页数
	return npages
}

span的sweep函数用于清扫单个span:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
func (s *mspan) sweep(preserve bool) bool {
	// It's critical that we enter this function with preemption disabled,
	// GC must not start while we are in the middle of this function.
	_g_ := getg()
	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
		throw("MSpan_Sweep: m is not locked")
	}
	sweepgen := mheap_.sweepgen
	if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
		print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
		throw("MSpan_Sweep: bad span state")
	}

	if trace.enabled {
		traceGCSweepSpan(s.npages * _PageSize)
	}

	// 统计已清理的页数
	atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))

	spc := s.spanclass
	size := s.elemsize
	res := false

	c := _g_.m.mcache
	freeToHeap := false

	// 判断在special中的析构器, 如果对应的对象已经不再存活则标记对象存活防止回收, 然后把析构器移到运行队列
	specialp := &s.specials
	special := *specialp
	for special != nil {
		// A finalizer can be set for an inner byte of an object, find object beginning.
		objIndex := uintptr(special.offset) / size
		p := s.base() + objIndex*size
		mbits := s.markBitsForIndex(objIndex)
		if !mbits.isMarked() {
			// This object is not marked and has at least one special record.
			// Pass 1: see if it has at least one finalizer.
			hasFin := false
			endOffset := p - s.base() + size
			for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
				if tmp.kind == _KindSpecialFinalizer {
					// Stop freeing of object if it has a finalizer.
					mbits.setMarkedNonAtomic()
					hasFin = true
					break
				}
			}
			// Pass 2: queue all finalizers _or_ handle profile record.
			for special != nil && uintptr(special.offset) < endOffset {
				// Find the exact byte for which the special was setup
				// (as opposed to object beginning).
				p := s.base() + uintptr(special.offset)
				if special.kind == _KindSpecialFinalizer || !hasFin {
					// Splice out special record.
					y := special
					special = special.next
					*specialp = special
					freespecial(y, unsafe.Pointer(p), size)
				} else {
					// This is profile record, but the object has finalizers (so kept alive).
					// Keep special record.
					specialp = &special.next
					special = *specialp
				}
			}
		} else {
			// object is still live: keep special record
			specialp = &special.next
			special = *specialp
		}
	}

	// 除错用
	if debug.allocfreetrace != 0 || raceenabled || msanenabled {
		// Find all newly freed objects. This doesn't have to
		// efficient; allocfreetrace has massive overhead.
		mbits := s.markBitsForBase()
		abits := s.allocBitsForIndex(0)
		for i := uintptr(0); i < s.nelems; i++ {
			if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
				x := s.base() + i*s.elemsize
				if debug.allocfreetrace != 0 {
					tracefree(unsafe.Pointer(x), size)
				}
				if raceenabled {
					racefree(unsafe.Pointer(x), size)
				}
				if msanenabled {
					msanfree(unsafe.Pointer(x), size)
				}
			}
			mbits.advance()
			abits.advance()
		}
	}

	// 计算释放的对象数量
	// Count the number of free objects in this span.
	nalloc := uint16(s.countAlloc())
	if spc.sizeclass() == 0 && nalloc == 0 {
		// 如果span的类型是0(大对象)并且其中的对象已经不存活则释放到heap
		s.needzero = 1
		freeToHeap = true
	}
	nfreed := s.allocCount - nalloc
	if nalloc > s.allocCount {
		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
		throw("sweep increased allocation count")
	}

	// 设置新的allocCount
	s.allocCount = nalloc

	// 判断span是否无未分配的对象
	wasempty := s.nextFreeIndex() == s.nelems

	// 重置freeindex, 下次分配从0开始搜索
	s.freeindex = 0 // reset allocation index to start of span.
	if trace.enabled {
		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
	}

	// gcmarkBits变为新的allocBits
	// 然后重新分配一块全部为0的gcmarkBits
	// 下次分配对象时可以根据allocBits得知哪些元素是未分配的
	// gcmarkBits becomes the allocBits.
	// get a fresh cleared gcmarkBits in preparation for next GC
	s.allocBits = s.gcmarkBits
	s.gcmarkBits = newMarkBits(s.nelems)

	// 更新freeindex开始的allocCache
	// Initialize alloc bits cache.
	s.refillAllocCache(0)

	// 如果span中已经无存活的对象则更新sweepgen到最新
	// 下面会把span加到mcentral或者mheap
	// We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
	// because of the potential for a concurrent free/SetFinalizer.
	// But we need to set it before we make the span available for allocation
	// (return it to heap or mcentral), because allocation code assumes that a
	// span is already swept if available for allocation.
	if freeToHeap || nfreed == 0 {
		// The span must be in our exclusive ownership until we update sweepgen,
		// check for potential races.
		if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
			print("MSpan_Sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
			throw("MSpan_Sweep: bad span state after sweep")
		}
		atomic.Store(&s.sweepgen, sweepgen)
	}

	if nfreed > 0 && spc.sizeclass() != 0 {
		// 把span加到mcentral, res等于是否添加成功
		c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
		res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
		// freeSpan会更新sweepgen
		// MCentral_FreeSpan updates sweepgen
	} else if freeToHeap {
		// 把span释放到mheap
		// Free large span to heap
		if debug.efence > 0 {
			s.limit = 0 // prevent mlookup from finding this span
			sysFault(unsafe.Pointer(s.base()), size)
		} else {
			mheap_.freeSpan(s, 1)
		}
		c.local_nlargefree++
		c.local_largefree += size
		res = true
	}
	
	// 如果span未加到mcentral或者未释放到mheap, 则表示span仍在使用
	if !res {
		// 把仍在使用的span加到sweepSpans的"已清扫"队列中
		// The span has been swept and is still in-use, so put
		// it on the swept in-use list.
		mheap_.sweepSpans[sweepgen/2%2].push(s)
	}
	return res
}

总结

GoV1.3- 普通标记清除法，整体过程需要启动STW，效率极低。

GoV1.5- 三色标记法， 堆空间启动写屏障，栈空间不启动，全部扫描之后，需要重新扫描一次栈(需要STW)，效率普通

GoV1.8-三色标记法，混合写屏障机制， 栈空间不启动，堆空间启动。整个过程几乎不需要STW，效率较高。

参考资料

参考资料