垃圾回收就是找出不再应用的对象并回收这些内存。如何找出呢？这就不得不说一下三色标记法，这是 Go 语言垃圾回收的根底。本篇文章次要介绍三色标记法，包含三色标记算法，写屏障技术；以及 Go 语言是如何实现三色标记和写屏障的。
三色标记
想想写 C 程序时，咱们须要自申请内存（malloc），应用结束后还须要本人开释内存（free），如果不开释可是会造成内存泄露的。写 Go 程序貌似不须要关注内存的开释，因为垃圾回收帮忙咱们回收了无用内存（称之为垃圾）。思考一下，垃圾回收都负责回收哪些内存呢？通常指的是堆内存，栈上的内存为什么不必回收呢？因为随着函数的调用与返回，栈内存主动调配与开释。那如何辨认堆内存是不是垃圾呢？
垃圾内存的定义应该是什么呢？想想如果没有任何路径能拜访到这块内存，那这块内存是不是就是垃圾内存了？如何判断有无路径能拜访到呢？有一个经典的计划叫援用计数法，如果对象 A 援用了对象 B，这时候 B 对象的援用计数为 1（对象相互援用时更新援用计数），那么对象 B 内存必定就不是垃圾了，因为对象 A 还能拜访到对象 B，而回收之后对象 A 再拜访对象 B 程序是会异样的。那对象 A 如果没有任何路径能拜访到呢？也就是说对象 A 自身就是垃圾，这时候显然对象 A 和对象 B 都应该被回收。
那这样操作呢：先判断对象 A 的援用计数为 0，回收对象 A，同时将对象 A 指向的所有对象援用计数减 1，再判断这些对象的援用计数如果为 0，则回收，以此类推。这种计划可行吗？想想如果对象 A 援用对象 B，并且对象 B 也援用对象 A，也就是呈现了循环援用状况，并且没有其余任何对象援用到这两个对象，实践上这时候对象 A 和对象 B 应该被回收，然而援用计数法又无奈回收这两个对象。
还有什么其余方法吗？想想什么对象肯定不可回收，拜访某对象的路径有什么特点呢？比如说栈对象，比方全局对象呢，这两种类型对象必定是不能轻易回收的，而且堆内存上的对象，一般来说也都是从栈对象或全局对象，逐渐援用，才拜访到的。如下图所示：
那只须要从根对象开始扫描（如栈对象，全局对象），扫描到的对象必定就不是垃圾，剩下的没有被扫描到的对象就是垃圾须要被回收了。这也就是三色标记法的基本思路了。为什么是三色呢？不是只有两种状态吗，已扫描，未扫描；因为还有局部对象处于待扫描状态，想想最后根节点是不是待扫描，扫描到这些节点时，须要以此判断（标记）其指向的所有节点，这些节点将称为下一波待扫描节点。
三色标记法申明了三种类型对象：1）彩色，曾经扫描过的对象；2）灰色，就是待扫描对象；3）红色，没有扫描的对象。整个过程能够总结为：1）从灰色对象汇合中抉择一个对象，标为彩色；2）扫描该对象指向的所有对象，将其退出到灰色对象汇合；3）一直反复步骤 1 /2。扫描完结后，最终只剩下彩色对象与红色对象，而红色对象就是须要回收的垃圾。
思考下 Go 语言是如何实现这一过程呢？彩色对象如何标记呢？最终红色对象是须要回收的，如何实现红色对象的疾速回收呢？还记得上一篇文章介绍内存治理的根本单元是 mspan，申请内存就是从 mspan 查找闲暇内存块（bitmap 记录内存闲暇与否，allocBits）。其实还有另一个字段，也是一个 bitmap，用来实现内存块的标记：
type mspan struct {gcmarkBits *gcBits}
s.gcmarkBits = newMarkBits(s.nelems)gcmarkBits 的比特位数目与 mspan 分隔的内存块数目统一，1 示意彩色对象，0 示意红色对象。等等，那灰色对象呢？一个必填位怎么示意三种色彩？想想如果用两个比特位示意黑灰白三种对象，第一步从灰色对象汇合中抉择一个对象将其标黑，灰色对象汇合在哪？怎么抉择灰色对象？遍历吗？所以灰色对象，其实是另外有一个队列保护的，而且灰色对象的 gcmarkBits 曾经置位 1 了。函数 greyobject 实现了对象标灰的逻辑，参考如下：
func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
// objIndex 为该内存块在 mspan 的地位
mbits := span.markBitsForIndex(objIndex)
// 如果没有标记才执行标记操作
if mbits.isMarked() {return}
mbits.setMarked()
// 退出队列
if !gcw.putFast(obj) {gcw.put(obj)
}
}
// wbuf1 就是一个数组
func (w *gcWork) putFast(obj uintptr) bool {
wbuf := w.wbuf1
if wbuf == nil {return false} else if wbuf.nobj == len(wbuf.obj) {return false}
wbuf.obj[wbuf.nobj] = obj
wbuf.nobj++
return true
}而整个标记扫描过程，其实就是一个 for 循环，一直从队列获取灰色对象，扫描并标记其指向的对象（垃圾回收初始化阶段，曾经将跟对象增加到灰色对象汇合了）：
for {
// 获取灰色对象
b := gcw.tryGetFast()
if b == 0 {b = gcw.tryGet()
}
// 扫描 & 标记
scanobject(b, gcw)
}貌似整个逻辑略微清晰了，不过你有没有想过这么一个问题：获取到灰色对象 A 后，须要扫描其指向的所有对象，那么对象 A 存储的是什么数据呢？有蕴含指针吗？哪几个字节存储的是指针呢？之前咱们提到，申请内存时，依据该类型对象是否蕴含指针，分为两种规格的 mspan，所以扫描到某个对象时，先计算出其属于哪一个 mspan（怎么计算呢？），判断 mspan 规格就晓得该对象是否蕴含指针了。只是，哪几个字节蕴含指针了呢？不可能对象的所有字段都是指针类型吧？
先解决第一个问题，怎么计算对象调配到那种类型的 mspan 呢？毕竟只有一个内存首地址。其实在调配 mspan 的时候，为每一个 heapArena 记录了其所有的 mspan
//arenas 数组保护了所有的 heapArena
arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
// 为 heapArena 保护其调配的 mspan
func (h *mheap) setSpans(base, npage uintptr, s *mspan)
// 返回 mspan 指针，不就晓得了其规格
func spanOfUnchecked(p uintptr) *mspan {
// heapArena 大小为 64M，并且首地址也是 64M 对齐（首地址除以 64M 取整能够作为 heapArena 索引）ai := arenaIndex(p)
// 首地址除以页大小，就是第几个页，取余数
return mheap_.arenas[ai.l1()][ai.l2()].spans[(p/pageSize)%pagesPerArena]
}再解决第二个问题，如何晓得对象哪几个字节存储的是指针呢？貌似没有什么好方法，只能记录了。heapArena 应用一个 bitmap 保护了每一个 8 字节内存是否是指针：
// bitmap 须要多少字节
heapArenaBitmapBytes = heapArenaBytes / (goarch.PtrSize * 8 / 2)
type heapArena struct {
//
bitmap [heapArenaBitmapBytes]byte
// 下面刚介绍过，每一个 heapArena 记录了其所有的 mspan
spans [pagesPerArena]*mspan
}实践上不应该是 64M/8 比特位，64M/8/8 字节吗？怎么貌似 bitmap 大小还翻倍了？其实 bitmap 不止记录每一个 8 字节内存是否是指针，还记录了后续字节是否须要持续扫描。想想看，如果一个对象占了 1024 字节，并且只有第一个字段是指针类型，难道须要扫描 128 次吗?bitmap 的每一个字节，0- 3 比特示意是否蕴含指针，4- 7 比特示意是否须要持续扫描。
函数 scanobject 实现了对象扫描的过程，显著能看到判断是否蕴含指针，查找指针指向的对象并退出到灰色对象汇合等等：另外 mallocgc 函数在申请内存时，如果发现该对象蕴含指针，还须要保护更新 bitmap 对应比特位。
func scanobject(b uintptr, gcw *gcWork) {
// 计算 bitmap
hbits := heapBitsForAddr(b)
// 计算 mspan
s := spanOfUnchecked(b)
// 对象占用内存大小
n := s.elemsize
// 遍历扫描这一块内存，留神 hbits.next()，挪动到下一对比特位
for i = 0; i < n; i, hbits = i+goarch.PtrSize, hbits.next() {bits := hbits.bits()
if bits&bitScan == 0 {break // no more pointers in this object}
if bits&bitPointer == 0 {continue // not a pointer}
// obj 就是指向的对象
obj := *(*uintptr)(unsafe.Pointer(b + i))
// 指向本人不须要扫描
if obj != 0 && obj-b >= n {
// 查找对象，退出到灰色对象汇合
if obj, span, objIndex := findObject(obj, b, i); obj != 0 {greyobject(obj, b, i, span, gcw, objIndex)
}
}
}
}
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
if !noscan {
// 保护 bitmap
heapBitsSetType(uintptr(x), size, dataSize, typ)
}
}
type _type struct {
// 每种类型的 gcdata 保护着垃圾回收相干数据
gcdata *byte
}最初还有一个问题：如何实现红色对象的疾速回收呢？想想 mspan.allocBits 记录内存闲暇与否，0 示意闲暇，1 示意已调配；mspan.gcmarkBits 用户标记彩色和红色对象，0 示意红色也就是须要回收的对象，1 示意彩色对象。两个字段定义很近进！在三色标记实现之后，只须要 allocBits=gcmarkBits 不就能够了！
写屏障
Go 语言是多线程 + 多协程程序，垃圾回收过程也是基于协程并发执行，并且垃圾回收器标记 - 清理过程中，用户协程还失常执行。这就必然存在一个问题：假如初始状况对象 A 指向对象 B，对象 B 指向对象 C，也就是 A ->B->C；垃圾回收器曾经标记对象 A 为彩色，对象 B 为灰色，对象 C 还未扫描到是红色；因为用户协程并发执行，此时若用户协程批改对象 B 指向 nil，对象 A 指向对象 C；对象 A 曾经是彩色，不会再扫描了，对象 B 指向的又是空地址，此时对象 C 将永远无奈再次被扫描。最终，实践上对象 C 还在应用（对象 A 指向了对象 C），然而因为对象还是红色，回被回收。也就是垃圾回收器出错了。再想想看，标记扫描过程中，用户协程新申请的内存呢？垃圾回收器还能扫描到这些对象吗？
实质上是因为用户协程与垃圾回收器并发执行，导致彩色的对象指向了红色对象，而且没有其余任何灰色对象存在某条链路能指向该红色对象；最终，不应该被回收的对象被谬误的回收了，当然也可能导致某些应该被回收的对象没有被回收（这还好，至多不会异样，下次还能回收）。那怎么办呢？有什么方法吗？总不能在垃圾回收器标记 - 清理过程暂停所有用户协程吧。
在介绍解决方案之前，先提出几个概念：1）强三色不变性，彩色对象执行指向灰色对象，灰色对象只能指向红色对象，这样垃圾回收显然不会有任何异样；2）弱三色不变性，彩色对象能够指向红色对象，然而肯定要存在一条链路，使得存在灰色对象指向该红色对象，这样通过若干次扫描，仍然能扫描到该红色对象。
只有始终满足强三色不变性与弱三色不变性，垃圾回收就不会有问题。而针对这两个概念，也提出了两种不通的屏障技术（垃圾回收过程中，用户协程更改指针援用时，额定增加一些操作），插入写屏障和删除写屏障。
举个例子，假如初始状况对象 A 指向对象 B，对象 B 指向对象 C，也就是 A ->B->C；此时用户协程批改对象 A 指向对象 C，也就是彩色对象指向了红色对象，从而突破了强三色不变性，怎么办呢？在批改指针援用的同时，将对象 C 染为灰色即可，这样仍然满足强三色不变性。这种计划称为插入写屏障，伪代码如下：
//slot 行将指向 ptr，如果 prt 为红色，将 ptr 染为灰色对象
writePointer(slot, ptr):
shade(ptr)
*slot = ptr再举个例子，假如初始状况对象 A 指向对象 B，对象 B 指向对象 C，也就是 A ->B->C；此时用户协程批改对象 A 指向对象 C，也就是彩色对象指向了红色对象，然而仍然满足弱三色不变性，因为通过灰色对象 B 还是有可能扫描到对象 C 的；当然后续如果要批改对象 B 的援用时，是须要将对象 C 染为灰色的。这种计划称为删除写屏障，伪代码如下：
//slot 行将指向 ptr，也就是删除了 slot 和另一个对象的援用关系，将另一个对象染为灰色对象
writePointer(slot, ptr)
shade(*slot)
*slot = ptrGo 语言同时应用插入写屏障与删除写屏障，也就是说既将 ptr 染为灰色，又将 * slot 染为灰色。当然只有在垃圾回收过程中，才须要开启写屏障，平时是不须要的（升高性能）。
咱们平时写的 Go 程序，必定存在对象的相互援用，以及援用关系的变更，也没看到什么写屏障逻辑啊。其实在编译过程，会注入写屏障相干逻辑。咱们写一个小程序，反编译看看汇编代码，测试一下：
package main
type student struct {
score int
name string
next *student
}
func main() {var s = new(student)
var s1 = new(student)
var s2 = new(student)
s.next = s1
s1.next = s2
}
/*
go tool compile -S -N -l test.go
"".main STEXT
0x0060 00096 (test.go:14) CMPL runtime.writeBarrier(SB), $0
0x0067 00103 (test.go:14) JEQ 107
0x0069 00105 (test.go:14) JMP 113
0x006b 00107 (test.go:14) MOVQ DX, 24(CX)
0x006f 00111 (test.go:14) JMP 120
0x0071 00113 (test.go:14) CALL runtime.gcWriteBarrierDX(SB)
*/能够看到，判断 runtime.writeBarrier 如果不为 0，则跳转到 runtime.gcWriteBarrierDX 执行写屏障逻辑。在开启垃圾回收过程时，开启了写屏障标识：
func setGCPhase(x uint32) {atomic.Store(&gcphase, x)
// 在标记 - 清理过程时，开启写屏障标识
writeBarrier.needed = gcphase == _GCmark || gcphase == _GCmarktermination
writeBarrier.enabled = writeBarrier.needed || writeBarrier.cgo
}写屏障逻辑次要做了什么呢？其实就是退出到了一个缓存队列，灰度对象队列为空时，或者标记扫描过程完结时，会将该缓存队列的对象标灰（重新加入到灰色队列）从而再次扫描。如上面程序事例：
// 标记过程
for {b := gcw.tryGetFast()
if b == 0 {b = gcw.tryGet()
if b == 0 {
//flushes p's write barrier buffer to the GC work queue
wbBufFlush(nil, 0)
b = gcw.tryGet()}
}
}另外其实还有很多底层函数自身也都蕴含写屏障逻辑，参考 atomicstorep 函数（指针援用赋值）以及其调用：
func atomicstorep(ptr unsafe.Pointer, new unsafe.Pointer) {
if writeBarrier.enabled {atomicwb((*unsafe.Pointer)(ptr), new)
}
atomic.StorepNoWB(noescape(ptr), new)
}最初还有一个问题，已有对象援用关系变更有写屏障技术保障三色不变性，那新申请的对象呢？间接标记为彩色对象呗！这个过程也能在内存调配主函数 mallocgc 看到：
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
if gcphase != _GCoff {
// 新申请对象标黑
gcmarknewobject(span, uintptr(x), size, scanSize)
}
}总结
本篇文章次要介绍了三色标记的整个过程以及实现细节，留神须要联合内存治理文章一起学习；另外因为用户协程与垃圾回收的并发执行，可能导致的回收谬误，Go 语言还引入了写屏障技术。