golang GC 三色标记

Base on go 1.13

GC

首先需要想清楚的问题是，什么是GC？

GC是一种自动内存管理方式。支持GC的语言无需手动管理内存, 程序后台自动判断对象是否存活并回收其内存空间, 使开发人员从内存管理上解脱出来。

现如今很多语言都支持GC，比如Java，go，Python等，不过GC的原理和基本算法都没有太大的改变。

这里有一些核心的概念：

并发和并行：通常在GC领域中, 并发收集器则指垃圾回收的同时应用程序也在执行; 并行收集器指垃圾回收采取多个线程利用多个CPU一起进行GC. 不过一般我们说并发回收器, 就包含了这两层意思.

Safepoint: 安全点(Safepoint)是收集器能够识别出线程执行栈上的所有引用的一点或一段时间。

Stop The World(STW): 某些垃圾回收算法或者某个阶段进行时需要将应用程序完全暂停.

Mark: 从Root对象开始扫描, 标记出其引用的对象, 及这些对象引用的对象, 如此循环, 标记所有可达的对象.

Sweep: Sweep清除阶段扫描堆区域, 回收在标记阶段标记为Dead的对象, 通常通过空闲链表(free list)的方式.需要的 工作量和堆大小成正比.

评价GC的性能，我们有一些关心的指标：

• 程序吞吐量: 回收算法会在多大程度上拖慢程序? 可以通过GC占用的CPU与其他CPU时间的百分比描述
• GC吞吐量: 在给定的CPU时间内, 回收器可以回收多少垃圾?
• 堆内存开销: 回收器最少需要多少额外的内存开销?
• 停顿频率: 回收器造成的停顿频率是怎样的?
• 停顿分布: 停顿有时候很长, 有时候很短? 还是选择长一点但保持一致的停顿时间?
• 分配性能: 新内存的分配是快, 慢还是无法预测?
• 压缩: 当堆内存里还有小块碎片化的内存可用时, 回收器是否仍然抛出内存不足(OOM)的错误?如果不是, 那么你是否 发现程序越来越慢, 并最终死掉, 尽管仍然还有足够的内存可用?
• 并发:回收器是如何利用多核机器的?
• 伸缩:当堆内存变大时, 回收器该如何工作?

常见垃圾回收算法

这一章主要介绍三种常见垃圾回收算法，比如引用计数、标记清除、复制算法、分代收集等。

引用计数

引用计数的思想非常简单：每个对象维护一个域保存其它对象指向它的引用数量（类似有向图的入度）。当引用数量为 0 时，表示可以将其回收。引用计数是渐进式的，能够将内存管理的开销分布到整个程序之中。C++ 的 share_ptr 使用的就是引用计算方法。具体细节这里不多说。

pros

• 渐进式。内存管理与用户程序的执行交织在一起，将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World，GC 的时候挂起用户程序)。
• 算法易于实现。
• 内存单元能够很快被回收。相比于其他垃圾回收算法，堆被耗尽或者达到某个阈值才会进行垃圾回收。

cons:

• 原始的引用计数不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题，也除了很多解决方案，比如强引用等。
• 维护引用计数降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数，相比于一些追踪式的垃圾回收算法并不需要这些代价。
• 单元池 free list 实现的话不是 cache-friendly 的，这样会导致频繁的 cache miss，降低程序运行效率。

标记清除

标记清除算法是第一种自动内存管理，基于追踪的垃圾收集算法。内存单元并不会在变成垃圾(没有其余对象引用)之后立刻回收，而是保持不可达状态，直到到达某个阈值或者固定时间长度。此时系统会挂起用户程序，也就是我们常说的 STW，转而执行垃圾回收程序。垃圾回收程序对所有的存活单元进行一次全局遍历确定哪些单元可以回收。算法分两个部分：标记（mark）和清扫（sweep）。标记阶段表明所有的存活单元，清扫阶段将垃圾单元回收。可视化可以参考下图。

标记清除算法的优点也就是基于追踪的垃圾回收算法具有的优点：避免了引用计数算法的缺点（不能处理循环引用，需要维护指针）。缺点也很明显，需要 STW。

三色标记算法

三色标记算法是对标记清除算法中的标记阶段的优化，粗略的过程如下：

1. GC开始阶段起初所有对象都是白色。
2. 从根(全局变量和栈变量)出发扫描所有可达对象，标记为灰色，放入待处理队列。
3. 从队列取出灰色对象，将其引用对象标记为灰色放入队列，自身标记为黑色。
4. 重复 3，直到灰色对象队列为空。此时白色对象即为垃圾，进行回收。

可视化：

三色标记的一个明显好处是能够让用户程序和 mark 并发的执行，具体可以参考论文：《On-the-fly garbage collection: an exercise in cooperation.》。Golang 的 GC 实现也是基于这篇论文，具体细节后面再说。

复制算法

复制算法也是基于追踪的算法。其将整个堆等分为两个半区（semi-space），一个包含现有数据，另一个包含已被废弃的数据。复制式垃圾收集从切换（flip）两个半区的角色开始，然后收集器在老的半区，也就是 Fromspace 中遍历存活的数据结构，在第一次访问某个单元时把它复制到新半区，也就是 Tospace 中去。在 Fromspace 中所有存活单元都被访问过之后，收集器在 Tospace 中建立一个存活数据结构的副本，用户程序可以重新开始运行了。

这个算法在Java的GC中对新生代用的比较多。

pros:

• 所有存活的数据结构都缩并地排列在 Tospace 的底部，这样就不会存在内存碎片的问题。
• 获取新内存可以简单地通过递增自由空间指针来实现。

cons:

• 内存得不到充分利用，总有一半的内存空间处于浪费状态。

分代收集算法

基于追踪的垃圾回收算法（标记清除、复制算法）一个主要问题是在生命周期较长的对象上浪费时间（长生命周期的对象是不需要频繁扫描的）。同时，内存分配存在这么一个事实 “most object die young”。基于这两点，分代垃圾回收算法将对象按生命周期长短存放到堆上的两个（或者更多）区域，这些区域就是分代（generation）。对于新生代的区域的垃圾回收频率要明显高于老年代区域。

分配对象的时候从新生代里面分配，如果后面发现对象的生命周期较长，则将其移到老年代，这个过程叫做 promote。随着不断 promote，最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高，STW 时间也会更短。

优点就是性能更优。缺点也就是实现复杂。

golangGC的发展

Golang 从第一个版本以来，GC 一直是大家诟病最多的。但是每一个版本的发布基本都伴随着 GC 的改进。1.8通过hybrid write barrier, 使得STW降到了sub ms. 下面列出一些GC方面比较重大的改动:

golang GC 三色标记

主要流程

1. 有黑白灰三个集合. 初始时所有对象都是白色
2. 从Root对象开始标记, 将所有可达对象标记为灰色 3. 从灰色对象集合取出对象, 将其引用的对象标记为 灰色, 放入灰色集合, 并将自己标记为黑色
3. 重复第三步, 直到灰色集合为空, 即所有可达对象都 被标记
4. 标记结束后, 不可达的白色对象即为垃圾. 对内存进 行迭代清扫, 回收白色对象.
5. 重置GC状态

这里有一点要注意：go和java不同, go的对象在内存中并没有header。

上面三色标记的流程中有几个主要问题：

1. 标记和程序并发, 会漏标记对象吗? 如何解决的?
2. 哪里记录了对象的三色标记状态?
3. 标记时, 拿到一个指针, 怎么知道它是哪个对象? 也许 是某个对象的内部指针? 这个对象的内存哪些地方代表 了它引用的对象呢?

写屏障

垃圾回收中的 write barrier 可以理解为编译器在写操作时特意插入的一段代码，对应的还有 read barrier。为什么需要 write barrier？很简单，对于和用户程序并发运行的垃圾回收算法，用户程序会一直修改内存，所以需要记录下来并发标记阶段的修改。

这里举个例子：

var A Wb
var B Wb

type struct Wb{
	Obj *int
}

func simpleSet(c *int){
	A.Obj = nil
	B.Obj = c
	
	// Begin GC
	// scan A 
	
	A.Obj = c
	B.Obj = nil
	
	// scan B
}

如上图：

A.Obj = cB.Obj = nil

这个pipeline下来，导致C被漏标。

为了解决这个问题, go使用了写屏障(和内存写屏障不是同一个概念). 写屏障是在写入指针前执行的一小段代码, 用以防止并发标记时指针 丢失, 这一小段代码Go是在编译时加入的. Golang写屏障在mark和marktermination阶段处于开启状态.

上图, Step3，A.obj=C时, 会将C进行标记, 加入写屏障buf, 最终会flush到待扫描队列, 这样就不会丢失C及C引用的对象。

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。

Dijkstra写屏障是对被写入的指针进行grey操作, 不能防止指针从 heap被隐藏到黑色的栈中, 需要STW重扫描栈。
Yuasa写屏障是对将被覆盖的指针进行grey操作, 不能防止指针从栈被隐藏到黑色的heap对象中, 需要在GC开始时保存栈的快照。

go 1.8写屏障混合了两者, 既不需要GC开始时保存栈快照, 也不需要 STW重扫描栈。伪代码如下：

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

有兴趣的可以看看golang的提案：Proposal: Eliminate STW stack re-scanning

三色标记状态的记录

前面我们说了在golang的GC中，runtime可以知道每个对象的三色状态。 但是，并runtime并没有真正的三个集合来分别装三色对象(如果真的用三个集合来存储，性能肯定是堪忧的)。

mspan

• span用于保存大对象, 这种情况span只有一个元素
• span用于保存极小对象且不包含指针的对象(tiny object), 这种情况span会用一个元素保存多个对象

spanfreeindex

freeindex + allocBits

gcmarkBits用于在gc时标记哪些对象存活, 每次gc以后gcmarkBits会变为allocBits。如下图：

回到GC中的三色表示，"三色"的概念可以简单的理解为:

• 黑色: 对象在这次GC中已标记, 且这个对象包含的子对象也已标记
• 灰色: 对象在这次GC中已标记, 但这个对象包含的子对象未标记
• 白色: 对象在这次GC中未标记

在go内部对象并没有保存颜色的属性, 三色只是对它们的状态的描述,

• 白色的对象在它所在的span的gcmarkBits中对应的bit为0,
• 灰色的对象在它所在的span的gcmarkBits中对应的bit为1, 并且对象在标记队列中,
• 黑色的对象在它所在的span的gcmarkBits中对应的bit为1, 并且对象已经从标记队列中取出并处理。

每个P中都有wbBuf(write barrier buffer.)和gcw gcWork, 以及全局的workbuf标记队列, 来实现生产者-消费者模型, 在这些队列中的指针为灰色对象, 表示已标记, 待扫描。

从队列中出来并把其引用对象入队的为黑色对象, 表示已标记, 已扫 描. (runtime.scanobject).

GC完成后, gcmarkBits会移动到allocBits然后重新分配一个全部为0的bitmap, 这样黑色的对象就变为了白色。

扫描与对象元信息

标记时拿到一个指针p1, 如何知道哪里是其引用的对象?

回到前面所提到的内存结构图. go的gc heap通过下图的arenas 进行划分, 每个heapArena管理了64M内存. heapArena存储着 pointer, span, bitmap的索引关系。

• p1指向的对象所属heapArena: arenas[0][p+constbase/64M]
• 找到对象所属span: p1%64M/8K就知道了该对象在该 heapArena中的页index, 通过spans[index]即可找到其所属的 span(runtime.spanOf )
• 对象首地址: 找到对象所属的span, 根据span的elemsize和span 的startAddr, 即可知道其为该span中第几个对象以及其地址 (runtime.findObject)
• 对象的gcmarkBits: 知道了obj 在span中属于第几个对象, 即可知道如何设置其gcmarkBits.
• 对象引用的对象: bitmap每两个bit分别表示某8个字节是否是指针, 以及该字节所属对象后续字节是否还包含指针, 以此知道其引用的对象和减少扫描工作量. 这些bit是分配对象时, 根据对象type信息设置的.

GC 的触发

GC在满足一定条件之后就会被触发，触发的条件有3种：

type gcTriggerKind int

const (
	// gcTriggerHeap indicates that a cycle should be started when
	// the heap size reaches the trigger heap size computed by the
	// controller.
	gcTriggerHeap gcTriggerKind = iota

	// gcTriggerTime indicates that a cycle should be started when
	// it's been more than forcegcperiod nanoseconds since the
	// previous GC cycle.
	gcTriggerTime

	// gcTriggerCycle indicates that a cycle should be started if
	// we have not yet started cycle number gcTrigger.n (relative
	// to work.cycles).
	gcTriggerCycle
)

// A gcTrigger is a predicate for starting a GC cycle. Specifically,
// it is an exit condition for the _GCoff phase.
type gcTrigger struct {
	kind gcTriggerKind
	now  int64  // gcTriggerTime: current time
	n    uint32 // gcTriggerCycle: cycle number to start
}

• gcTriggerHeap: 当前分配的内存达到一定值就触发GC
• gcTriggerTime: 当一定时间没有执行过GC就触发GC
• gcTriggerCycle: 要求启动新一轮的GC, 已启动则跳过, 手动触发GC的runtime.GC()会使用这个条件

触发条件的判断在gctrigger的test函数：

// test reports whether the trigger condition is satisfied, meaning
// that the exit condition for the _GCoff phase has been met. The exit
// condition should be tested when allocating.
func (t gcTrigger) test() bool {
	if !memstats.enablegc || panicking != 0 || gcphase != _GCoff {
		return false
	}
	switch t.kind {
	case gcTriggerHeap:
		// Non-atomic access to heap_live for performance. If
		// we are going to trigger on this, this thread just
		// atomically wrote heap_live anyway and we'll see our
		// own write.
		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:
		// t.n > work.cycles, but accounting for wraparound.
		return int32(t.n-work.cycles) > 0
	}
	return true
}

上面的三个触发事件，有两个是自动触发，有一个是手动触发：

gcTriggerHeap

在我们向runtime申请对象时：

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	......
	if shouldhelpgc {
		if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
			gcStart(t)
		}
	}
	......
}

shouldhelpgc置shouldhelpgc

memstats.heap_live >= memstats.gc_trigger

heap_live的增加在分配器的代码分析中可以看到, 当值达到gc_trigger就会触发GC, 那么gc_trigger是如何决定的?

gcSetTriggerRatiotrigger = uint64(float64(memstats.heap_marked) * (1 + triggerRatio))

triggerRatio在每次GC之后都会调整更新, 计算triggerRatio的函数是encCycle, 公式是:

const triggerGain = 0.5
// 目标Heap增长率, 默认是1.0
goalGrowthRatio := gcEffectiveGrowthRatio()
// 实际Heap增长率, 等于总大小/存活大小-1
actualGrowthRatio := float64(memstats.heap_live)/float64(memstats.heap_marked) - 1
// GC标记阶段的使用时间(因为endCycle是在Mark Termination阶段调用的)
assistDuration := nanotime() - c.markStartTime
// GC标记阶段的CPU占用率, 目标值是0.25
utilization := gcBackgroundUtilization
if assistDuration > 0 {
		  // assistTime是G辅助GC标记对象所使用的时间合计
    // (nanosecnds spent in mutator assists during this cycle)
    // 额外的CPU占用率 = 辅助GC标记对象的总时间 / (GC标记使用时间 * P的数量)
		utilization += float64(c.assistTime) / float64(assistDuration*int64(gomaxprocs))
}
// 触发系数偏移值 = 目标增长率 - 原触发系数 - CPU占用率 / 目标CPU占用率 * (实际增长率 - 原触发系数)
// 参数的分析:
// 实际增长率越大, 触发系数偏移值越小, 小于0时下次触发GC会提早
// CPU占用率越大, 触发系数偏移值越小, 小于0时下次触发GC会提早
// 原触发系数越大, 触发系数偏移值越小, 小于0时下次触发GC会提早
triggerError := goalGrowthRatio - memstats.triggerRatio - utilization/gcGoalUtilization*(actualGrowthRatio-memstats.triggerRatio)

// 根据偏移值调整触发系数, 每次只调整偏移值的一半(渐进式调整)
triggerRatio := memstats.triggerRatio + triggerGain*triggerError

公式中的"目标Heap增长率"可以通过设置环境变量"GOGC"调整, 默认值是100, 增加它的值可以减少GC的触发。设置"GOGC=off"可以彻底关掉GC.

gcTriggerTime

sysmon

lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
return lastgc != 0 && t.now-lastgc > forcegcperiod

forcegcperiod的定义是2分钟, 也就是2分钟内没有执行过GC就会强制触发。

gcTriggerCycle

runtime.GC()

辅助GC GC Pacer 根对象

在GC的标记阶段首先需要标记的就是"根对象", 从根对象开始可到达的所有对象都会被认为是存活的。

根对象包含了全局变量, 各个G的栈上的变量等, GC会先扫描根对象然后再扫描根对象可到达的所有对象。

标记队列

GC标记队列，或者说灰色对象管理(发生在GC的并发标记阶段)。每个 P 上都有一个 gcw 对象来管理灰色对象（get 和 put操作），gcw 也就是 gcWork。gcWork 中的核心是 wbuf1 和 wbuf2，里面存储就是灰色对象，或者说是 work（下面就全部统一叫做 work）。

// runtime/mgcwork.go
type struct p {
	.......
	// gcw is this P's GC work buffer cache. The work buffer is
	// filled by write barriers, drained by mutator assists, and
	// disposed on certain GC state transitions.
	gcw gcWork
	......
}

type gcWork struct {
	// wbuf1 and wbuf2 are the primary and secondary work buffers.
	wbuf1, wbuf2 *workbuf

	// 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
	......
}

gcWork

标记队列的设计和协程调度的设计非常相似，分为Per P的队列和全局队列。这样的好处不言而喻，Per P的队列不需要加锁。

//runtime/mgc.go
var work struct {
	full  lfstack          // lock-free list of full blocks workbuf
	empty lfstack          // lock-free list of empty blocks workbuf
	pad0  cpu.CacheLinePad // prevents false-sharing between full/empty and nproc/nwait

	wbufSpans struct {
		lock mutex
		// free is a list of spans dedicated to workbufs, but
		// that don't currently contain any workbufs.
		free mSpanList
		// busy is a list of all spans containing workbufs on
		// one of the workbuf lists.
		busy mSpanList
	}
	......
	bytesMarked uint64
	......
}

整体high level 结构概括如下图：

这里gcWork为什么使用两个work buffer （wbuf1 和 wbuf2）呢？
比如我现在要 get 一个 灰色对象出来，先从 wbuf1 中取，wbuf1 为空的话则wbuf1与wbuf2 swap 再 get。在其他时间将 work buffer 中的 full 或者 empty buffer 迁移到 global 的 work 中。这样的好处在于将 get 或 put 操作的成本分摊到至少一个 work buffer 上，并减少全局work list上的争用。这里有趣的是 global 的 work full 和 empty list 是 lock-free 的，通过原子操作 cas 等实现。

gcWork初始化

func (w *gcWork) init() {
	w.wbuf1 = getempty()
	wbuf2 := trygetfull()
	if wbuf2 == nil {
		wbuf2 = getempty()
	}
	w.wbuf2 = wbuf2
}

getemptywork.empty listtrygetfull

我们可以看到gcWork初始化的时候：

1. wbuf1会获取一个空的work buffer；
2. wbuf2 会尽可能获取一个full work buffer，如果获取不到就会获取局部为空或者全部为空的work buffer；

这样做的好处在于初始化时候保证gcWork里面既有空的work buffer，也有full的work buffer。对于put和get操作时候，减少与全局标记队列的交互。

gcWork put

func (w *gcWork) put(obj uintptr) {
	w.checkPut(obj, nil)

	flushed := false
	wbuf := w.wbuf1
	if wbuf == nil {
		w.init()
		wbuf = w.wbuf1
		// wbuf is empty at this point.
	} else if wbuf.nobj == len(wbuf.obj) {
		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
		wbuf = w.wbuf1
		if wbuf.nobj == len(wbuf.obj) {
			putfull(wbuf)
			w.flushedWork = true
			wbuf = getempty()
			w.wbuf1 = wbuf
			flushed = true
		}
	}

	wbuf.obj[wbuf.nobj] = obj
	wbuf.nobj++

	// If we put a buffer on full, let the GC controller know so
	// it can encourage more workers to run. We delay this until
	// the end of put so that w is in a consistent state, since
	// enlistWorker may itself manipulate w.
	if flushed && gcphase == _GCmark {
		gcController.enlistWorker()
	}
}

put操作的时候会优先put进去wbuf1，如果wbuf1满了，就将wbuf1和wbuf2交换。如果交换之后wbuf1还是满的，就将wbuf1 push到全局的work.full list, 并从全局 work.empty list里面取出一个空的wbuf。最后执行put操作。

gcWork get

func (w *gcWork) tryGet() uintptr {
	wbuf := w.wbuf1
	if wbuf == nil {
		w.init()
		wbuf = w.wbuf1
		// wbuf is empty at this point.
	}
	if wbuf.nobj == 0 {
		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
		wbuf = w.wbuf1
		if wbuf.nobj == 0 {
			owbuf := wbuf
			wbuf = trygetfull()
			if wbuf == nil {
				return 0
			}
			putempty(owbuf)
			w.wbuf1 = wbuf
		}
	}

	wbuf.nobj--
	return wbuf.obj[wbuf.nobj]
}

work.emptywork.full

GC的流程

在Go 1.5 版本：

Go 1.5是Go转为并发三色标记清除法的版本. 大部分情况下能够将STW控制在10ms以下。

Go 1.12:

这里是基于golang1.13的最新代码分析，分为下面几个阶段：

1. 标记前准备(STW)
2. 并发标记
3. 标记终止(STW)
4. 并发回收

gcStart

// gcStart starts the GC. It transitions from _GCoff to _GCmark
func gcStart(trigger gcTrigger) {
	//检查和一些边界case
	......

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

	// gcBgMarkStartWorkers 创建后台Mark工作的goroutines;
	// 这些 goroutines 不会马上启动，知道进入mark阶段才会启动。
	gcBgMarkStartWorkers()

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

	......

	//  STW, 停止所有运行中的G, 并禁止它们运行
	systemstack(stopTheWorldWithSema)
	// !!!!!!!!!!!!!!!!
    // 世界已停止(STW)...
    // !!!!!!!!!!!!!!!!
    
	// 清扫上一轮GC未清扫的span, 确保上一轮GC已完成
	systemstack(func() {
		finishsweep_m()
	})
	
	......
	

	// 设置全局变量中的GC状态为_GCmark
    // 然后启用写屏障
	setGCPhase(_GCmark)
	// 重置后台标记任务的计数
	gcBgMarkPrepare() // Must happen before assist enable.
	// 计算扫描根对象的任务数量
	gcMarkRootPrepare()

	// 标记所有tiny alloc等待合并的对象
	gcMarkTinyAllocs()

	// 启用辅助GC
	atomic.Store(&gcBlackenEnabled, 1)

	// Concurrent mark.
	systemstack(func() {
		// 重新启动世界
		// 前面创建的后台 Mark 任务会开始工作, 所有后台标记任务都完成工作后, 进入完成标记阶段
		now = startTheWorldWithSema(trace.enabled)
		// 记录停止了多久, 和标记阶段开始的时间
		work.pauseNS += now - work.pauseStart
		work.tMark = now
	})
	// !!!!!!!!!!!!!!!
    // 世界已重新启动...
    // !!!!!!!!!!!!!!!
	......
}

Phase1:标记前准备(STW)

gcStart

sweeponegcBgMarkStartWorkers_GCmark

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.gcBgMarkWorker == 0 {
			go gcBgMarkWorker(p)
			 // 启动后等待该任务通知信号量bgMarkReady再继续
			notetsleepg(&work.bgMarkReady, -1)
			noteclear(&work.bgMarkReady)
		}
	}
}

findRunnableGCWorker

Phase2 并发标记

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

func gcBgMarkWorker(_p_ *p) {
	......

	for {
		// 将当前 goroutine 休眠，直到被gcController.findRunnable唤醒
		gopark(func(g *g, parkp unsafe.Pointer) bool {
			......
		}, unsafe.Pointer(park), waitReasonGCWorkerIdle, traceEvGoBlock, 0)

		......
		// 记录Mark 开始时间
		startTime := nanotime()
		_p_.gcMarkWorkerStartTime = startTime

		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() {
			casgstatus(gp, _Grunning, _Gwaiting)
			// 判断后台标记任务的模式
			switch _p_.gcMarkWorkerMode {
			default:
				throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
			// 这个模式下P应该专心执行标记
            // 执行标记, 直到被抢占, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
			case gcMarkWorkerDedicatedMode:
				gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
				......
				// Go back to draining, this time
				// without preemption.
				gcDrain(&_p_.gcw, gcDrainFlushBgCredit)
			// 这个模式下P应该适当执行标记
            // 执行标记, 直到被抢占, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
			case gcMarkWorkerFractionalMode:	
				gcDrain(&_p_.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit)、
			// 这个模式下P只在空闲时执行标记
            // 执行标记, 直到被抢占或者达到一定的量, 并且需要计算后台的扫描量来减少辅助GC和唤醒等待中的G
			case gcMarkWorkerIdleMode:
				gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
			}
			casgstatus(gp, _Gwaiting, _Grunning)
		})

		......

		// 判断是否所有后台标记任务都完成, 并且没有更多的任务
		if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
			......
			// 准备进入完成标记阶段
			gcMarkDone()
			......
		}
	}
}

gcDrain

// gcDrain scans roots and objects in work buffers, blackening grey
// objects until it is unable to get more work. It may return before
// GC is done; it's the caller's responsibility to balance work from
// other Ps.
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
	......
	
	// 如果根对象未扫描完, 则先扫描根对象
	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 check != nil && check() {
				goto done
			}
		}
	}

 	// 根对象已经在标记队列中, 消费标记队列
    // 如果标记了preemptible, 循环直到被抢占
	// Drain heap marking jobs.
	for !(preemptible && gp.preempt) {
		// 如果全局标记队列为空, 把本地标记队列的一部分工作分过去
        // (如果wbuf2不为空则移动wbuf2过去, 否则移动wbuf1的一半过去)
		if work.full == 0 {
			gcw.balance()
		}
		// 从本地标记队列中获取对象, 获取不到则从全局标记队列获取
		b := gcw.tryGetFast()
		if b == 0 {
			b = gcw.tryGet()
			if b == 0 {
				// Flush the write barrier
				// buffer; this may create
				// more work.
				wbBufFlush(nil, 0)
				b = gcw.tryGet()
			}
		}
		// 获取不到对象, 标记队列已为空, 跳出循环
		if b == 0 {
			// Unable to get work.
			break
		}
		// 扫描获取到的对象
		scanobject(b, gcw)

		// 如果已经扫描了一定数量的对象(gcCreditSlack的值是2000)
		if gcw.scanWork >= gcCreditSlack {
			// 把扫描的对象数量添加到全局
			atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
			if flushBgCredit {
				gcFlushBgCredit(gcw.scanWork - initScanWork)
				initScanWork = 0
			}
			checkWork -= gcw.scanWork
			gcw.scanWork = 0

			if checkWork <= 0 {
				checkWork += drainCheckThreshold
				if check != nil && check() {
					break
				}
			}
		}
	}

done:
	// 把扫描的对象数量添加到全局
	if gcw.scanWork > 0 {
		atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
		if flushBgCredit {
			gcFlushBgCredit(gcw.scanWork - initScanWork)
		}
		gcw.scanWork = 0
	}
}

在所有后台标记任务都把标记队列消费完毕时, 会执行gcMarkDone函数准备进入完成标记阶段(mark termination)。

func gcMarkDone() {
	......
	//记录完成标记阶段开始的时间和STW开始的时间
	// There was no global work, no local work, and no Ps
	// communicated work since we took markDoneSema. Therefore
	// there are no grey objects and no more objects can be
	// shaded. Transition to mark termination.
	now := nanotime()
	work.tMarkTerm = now
	work.pauseStart = now
	getg().m.preemptoff = "gcing"
	if trace.enabled {
		traceGCSTWStart(0)
	}
	// !!!!!!!!!!!!!!!!
    // 世界已停止(STW)...
    // !!!!!!!!!!!!!!!!
	// STW 
	systemstack(stopTheWorldWithSema)
	
	// 禁止辅助GC和后台标记任务的运行
	atomic.Store(&gcBlackenEnabled, 0)

	// 唤醒所有因为辅助GC而休眠的G
	gcWakeAllAssists()

	......
	
	 // 计算下一次触发gc需要的heap大小
	nextTriggerRatio := gcController.endCycle()

	// 进入完成标记阶段, 会重新启动世界
	gcMarkTermination(nextTriggerRatio)
}

PHASE3:标记终止(STW)

gcMarkTermination

func gcMarkTermination(nextTriggerRatio float64) {
	// World is stopped.
	// Start marktermination which includes enabling the write barrier.
	// 禁止辅助GC和后台标记任务的运行
	atomic.Store(&gcBlackenEnabled, 0)
	setGCPhase(_GCmarktermination)

	work.heap1 = memstats.heap_live
	startTime := nanotime()

	......
	
	systemstack(func() {
		// 开始STW中的标记
		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.
	})

	systemstack(func() {
		work.heap2 = work.bytesMarked
		......

		// 唤醒后台清扫任务, 将在STW结束后开始运行
		setGCPhase(_GCoff)
		gcSweep(work.mode)
	})

	......

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

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

	// Pacing changed, so the scavenger should be awoken.
	wakeScavenger()
	
	// 更新用时记录
	// Update timing memstats
	now := nanotime()
	sec, nsec, _ := time_now()
	......
	
	// Update work.totaltime.
	sweepTermCpu := int64(work.stwprocs) * (work.tMark - work.tSweepTerm)
	// We report idle marking time below, but omit it from the
	// overall utilization here since it's "free".
	markCpu := gcController.assistTime + gcController.dedicatedMarkTime + gcController.fractionalMarkTime
	markTermCpu := int64(work.stwprocs) * (work.tEnd - work.tMarkTerm)
	cycleCpu := sweepTermCpu + markCpu + markTermCpu
	work.totaltime += cycleCpu

	// Compute overall GC CPU utilization.
	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

	if work.userForced {
		memstats.numforcedgc++
	}

	......
	// 重新启动世界
	systemstack(func() { startTheWorldWithSema(true) })
	// !!!!!!!!!!!!!!!
    // 世界已重新启动...
    // !!!!!!!!!!!!!!!
	......
	
	// 移动标记队列使用的缓冲区到自由列表, 使得它们可以被回收
	prepareFreeWorkbufs()

	// Free stack spans. This must be done between GC cycles.
	systemstack(freeStackSpans)

	// Ensure all mcaches are flushed. Each P will flush its own
	// mcache before allocating, but idle Ps may not. Since this
	// is necessary to sweep all spans, we need to ensure all
	// mcaches are flushed before we start the next GC cycle.
	systemstack(func() {
		forEachP(func(_p_ *p) {
			_p_.mcache.prepareForSweep()
		})
	})
	......
}

gcSweep函数会唤醒后台清扫任务，进入Phase4

PHASE4:并发回收

gcSweep

func gcSweep(mode gcMode) {
	if gcphase != _GCoff {
		throw("gcSweep being done but phase is not GCoff")
	}

	lock(&mheap_.lock)
	// 增加sweepgen, 这样sweepSpans中两个队列角色会交换, 所有span都会变为"待清扫"的span
	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
	mheap_.sweepArenas = mheap_.allArenas
	mheap_.reclaimIndex = 0
	mheap_.reclaimCredit = 0
	unlock(&mheap_.lock)

	if !_ConcurrentSweep || mode == gcForceBlockMode {
		......
		return
	}

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

bgsweep

func gcenable() {
	// Kick off sweeping and scavenging.
	c := make(chan int, 2)
	go bgsweep(c)
	go bgscavenge(c)
	<-c
	<-c
	memstats.enablegc = true // now that runtime is initialized, GC is okay
}

func bgsweep(c chan int) {
	sweep.g = getg()
	// 等待唤醒
	lock(&sweep.lock)
	sweep.parked = true
	c <- 1
	goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
	
	// 循环清扫
	for {
		// 清扫一个span, 然后进入调度(一次只做少量工作)
		for sweepone() != ^uintptr(0) {
			sweep.nbgsweep++
			Gosched()
		}
		 // 释放一些未使用的标记队列缓冲区到heap
		for freeSomeWbufs(true) {
			Gosched()
		}
		lock(&sweep.lock)
		// 如果清扫未完成则继续循环
		if !isSweepDone() {
			// This can happen if a GC runs between
			// gosweepone returning ^0 above
			// and the lock being acquired.
			unlock(&sweep.lock)
			continue
		}
		sweep.parked = true
		// 否则让后台清扫任务进入休眠, 当前M继续调度
		goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
	}
}

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

// sweepone sweeps some unswept heap span and returns the number of pages returned
// to the heap, or ^uintptr(0) if there was nothing to sweep.
func sweepone() uintptr {
	......
	// Find a span to sweep.
	var s *mspan
	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 state := s.state.get(); 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 || s.sweepgen == sg+3) {
				print("runtime: bad span s.state=", 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) {
			break
		}
	}

	// Sweep the span we found.
	npages := ^uintptr(0)
	if s != nil {
		npages = s.npages
		if s.sweep(false) {
			// Whole span was freed. Count it toward the
			// page reclaimer credit since these pages can
			// now be used for span allocation.
			atomic.Xadduintptr(&mheap_.reclaimCredit, npages)
		} else {
			// 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的任务数量
	// 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 {
		......
	}
	_g_.m.locks--
	return npages
}

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

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 state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
		print("mspan.sweep: state=", 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

	// The allocBits indicate which unmarked objects don't need to be
	// processed since they were free at the end of the last GC cycle
	// and were not allocated since then.
	// If the allocBits index is >= s.freeindex and the bit
	// is not marked then the object remains unallocated
	// since the last GC.
	// This situation is analogous to being on a freelist.

	// Unlink & free special records for any objects we're about to free.
	// Two complications here:
	// 1. An object can have both finalizer and profile special records.
	//    In such case we need to queue finalizer for execution,
	//    mark the object as live and preserve the profile special.
	// 2. A tiny object can have several finalizers setup for different offsets.
	//    If such object is not marked, we need to queue all finalizers at once.
	// Both 1 and 2 are possible at the same time.
	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
		}
	}

	......

	// Count the number of free objects in this span.
	nalloc := uint16(s.countAlloc())
	if spc.sizeclass() == 0 && nalloc == 0 {
		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")
	}

	s.allocCount = nalloc
	wasempty := s.nextFreeIndex() == s.nelems
	s.freeindex = 0 // reset allocation index to start of span.
	if trace.enabled {
		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
	}

	// gcmarkBits becomes the allocBits.
	// get a fresh cleared gcmarkBits in preparation for next GC
	s.allocBits = s.gcmarkBits
	s.gcmarkBits = newMarkBits(s.nelems)

	// Initialize alloc bits cache.
	s.refillAllocCache(0)

	// 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 state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
			print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
			throw("mspan.sweep: bad span state after sweep")
		}
		// Serialization point.
		// At this point the mark bits are cleared and allocation ready
		// to go so release the span.
		atomic.Store(&s.sweepgen, sweepgen)
	}

	if nfreed > 0 && spc.sizeclass() != 0 {
		c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
		res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
		// mcentral.freeSpan updates sweepgen
	} else if freeToHeap {
		// Free large span to heap

		// NOTE(rsc,dvyukov): The original implementation of efence
		// in CL 22060046 used sysFree instead of sysFault, so that
		// the operating system would eventually give the memory
		// back to us again, so that an efence program could run
		// longer without running out of memory. Unfortunately,
		// calling sysFree here without any kind of adjustment of the
		// heap data structures means that when the memory does
		// come back to us, we have the wrong metadata for it, either in
		// the mspan structures or in the garbage collection bitmap.
		// Using sysFault here means that the program will run out of
		// memory fairly quickly in efence mode, but at least it won't
		// have mysterious crashes due to confused memory reuse.
		// It should be possible to switch back to sysFree if we also
		// implement and then call some kind of mheap.deleteSpan.
		if debug.efence > 0 {
			s.limit = 0 // prevent mlookup from finding this span
			sysFault(unsafe.Pointer(s.base()), size)
		} else {
			mheap_.freeSpan(s, true)
		}
		c.local_nlargefree++
		c.local_largefree += size
		res = true
	}
	if !res {
		// 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
}

从bgsweep和前面的分配器可以看出扫描阶段的工作是十分懒惰(lazy)的,
实际可能会出现前一阶段的扫描还未完成, 就需要开始新一轮的GC的情况,
所以每一轮GC开始之前都需要完成前一轮GC的扫描工作(Sweep Termination阶段).