一. 源自某次技术需求后的发现

二. golang垃圾回收小史

1.13版本中，改进Scavenger，这部分是垃圾回收器在回收完垃圾后将内存返回给操作系统的结构，老版本是另开一个goroutine运行，在1.13版本也和其他用户goroutine并发执行，进一步提高了垃圾回收器的效率。

这里只是对于golang垃圾回收历史中几个我觉得比较重要的改进做了说明，现在golang的最新版本为1.17，如果对1.13版本之后的有关于golang垃圾回收历史感兴趣的同学可以搜索golang的官网查看相关的改动。

三. golang垃圾回收过程

以1.13版本为例子，垃圾回收的过程以STW作为界限可以分为5个阶段

每个阶段的触发函数如下:

四. 三色标记法

三色标记法是golang在堆内存中寻找存活对象的抽象过程。

其中黑色对象标识该对象已经被标记过了，且黑色对象引用的对象也全部都被标记过了。灰色对象表示该对象已经被标记了但是该对象引用的对象没有被全部标记。白色对象就是没有被标记的对象，被认为是潜在的垃圾，在标记开始前，所有对象都是白色对象。

在垃圾收集器开始工作时，从根对象开始进行遍历访问，有如下几个步骤:

五. 写屏障

1. 初始状态：假设某个黑色对象 C 指向某个灰色对象 A ，而 A 指向白色对象 B；
   
2. C.ref3 = C.ref2.ref1：赋值器并发地将黑色对象 C 指向（ref3）了白色对象 B；
   
3. A.ref1 = nil：移除灰色对象 A 对白色对象 B 的引用（ref2）；
   
4. 最终状态：在继续扫描的过程中，白色对象 B 永远不会被标记为黑色对象了（回收器不会重新扫描黑色对象），进而对象 B 被错误地回收

●强三色不变式

关注白色指针指向黑色对象的写入操作，不允许出现黑色指针指向白色，如果出现黑色对象指向白色对象，那就使用插入写屏障，具体的做法就是将黑色对象指向的白色对象涂灰或者将黑色对象涂灰。

●弱三色不变式

如果有黑色对象指向白色对象时继续观察，如果还有灰色对象指向该白色对象，说明满足弱三色不变式，弱三色不变式提醒我们关注对那些白色对象路径的破坏行为。解决这个问题的方式是删除写屏障，可以把灰色对象指向的白色对象涂灰，这样黑色对象指向的就是灰色对象而不是之前的白色对象。
使用写屏障之后，垃圾回收器的正确性就得到了保障。

六. gcDrain函数的实现

6.1 gcDrain函数的触发阶段

从之前的火焰图可以看出来，gcDrain函数是火焰图中大平顶函数的调用的函数之一

该函数的触发位置如图所示，处在STW之后的标记阶段

6.2 gcDrain函数的参数

func gcDrain(gcw *gcWork, flags gcDrainFlags)

gcDrain函数的参数有两个，其中gcw是该函数主要处理的结构，gcDrainFlags和golang的调度有很大关系

type p struct {
    ...
    // 每个p上绑定一个gcWork
    gcw gcWork
}

type gcWork struct {
	// 本地工作缓存，wbuf1为主工作缓存，wbuf2为副工作缓存
	wbuf1, wbuf2 *workbuf

	// 标记变黑的结点
	bytesMarked uint64

	// 每个p做了多少标记工作的记录，与调度有关
	scanWork int64

    // gcWork的workbuff是否与全局workbuff进行过flash操作
    flushedWork bool
}

p(process)是golang定义的一个抽象的概念，它不是物理上的CPU，当一个P有任务，需要创建或者唤醒一个系统线程去处理它队列中的任务，P决定同时执行的任务数量，我们平常会经常看到GOMAXPROCS这个参数，GOMAXPROCS就是限制系统线程执行用户层面的任务的数量，可以简单的理解为一个p对应一个物理核心。每个p上会绑定一个gcWork，gcWork中最重要的结构就是两个本地工作缓存wbuf1和wbuf2。

type workbuf struct {
	workbufhdr
	// uintptr 是golang的内置类型，可以存储指针的整型，这种指针类型是可以做运算的
	// obj 是一个指针数组，每个元素是一个可以进行计算的指针，该指针通过计算可以指向灰色对象
	obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
}

type workbufhdr struct {
	// 灰色对象
	node lfnode
	// 工作缓存中灰色对象的个数
	nobj int
}

// Lock-free stack node.
// lock-free机制的底层实现是CAS，目的是为了解决并发问题
type lfnode struct {
	next    uint64
	pushcnt uintptr
}

我们可以认为wbuf1和wbuf2中存储的是灰色对象，具体存储的地方就在obj这个指针数组中，其中指针数组中灰色对象的个数为nobj，灰色对象被定义为lfnode，lfnode的底层实现涉及到了CAS(Compare And Swag)，这是为了解决并发问题。

gcDrain函数主要就是在使用wbuf1、wbuf2以及全局wbuf来实现三色标记法，而引入全局wbuf的目的在于平衡每个P的工作量，不至于旱的旱死，涝的涝死。

6.3 操作gcWork中灰色对象的函数

针对gcWork的操作有六个，总结下来其实是四个，带有Fast后缀的方法是其主方法的简单实现形式，目的是减少使用主方法带来的代价。

6.3.1 put

func (w *gcWork) put(obj uintptr) {
	flushed := false
	wbuf := w.wbuf1
    ....
	// 如果wbuf1没有创建
	if wbuf == nil {
	        // 初始化并给wbuf1一个空值
		w.init()
		wbuf = w.wbuf1
	  // 如果wbuf1是满的
	} else if wbuf.nobj == len(wbuf.obj) {
	        // wbuf1和wbuf2进行交换
		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
		wbuf = w.wbuf1
	        // 如果交换之后还是满的
		if wbuf.nobj == len(wbuf.obj) {
		        // 就把wbuf1中的灰色对象放入全局工作缓存中
			putfull(wbuf)
	                // 与全局工作缓存执行过交流后设置该标记位
			w.flushedWork = true
		        // 将wbuf1的内容置为空
			wbuf = getempty()
			w.wbuf1 = wbuf
			flushed = true
		}
	}

	// 如果wbuf1不满，就直接操作wubf1
	wbuf.obj[wbuf.nobj] = obj
	wbuf.nobj++
	....
}

其中put操作就是将灰色对象放入wbuf1中，如果wbuf1满了就将wbuf1和wbuf2进行交换，如果交换之后依旧是满的，那么就将这部分灰色对象flush到全局工作缓存中，并将flushedWork标记为true，这意味着gcWork中的wbuf与全局wbuf有过数据交换。

6.3.2 tryGet

func (w *gcWork) tryGet() uintptr {
	wbuf := w.wbuf1
	if wbuf == nil {
		w.init()
		wbuf = w.wbuf1
	}
	// 当wbuf1缓冲区中没有灰色对象时
	if wbuf.nobj == 0 {
		// wubf1 与 wbuf2 进行对象互换
		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
		wbuf = w.wbuf1
		// 如果交换完还为空，意味着本地的主从buffer均为空
		if wbuf.nobj == 0 {
			owbuf := wbuf
			// 需要从全局工作缓存中取
			wbuf = trygetfull()
			// 如果全局工作缓存中也没有灰色对象，就返回
			if wbuf == nil {
				return 0
			}
			putempty(owbuf)
			// 将得到的灰色对象给wbuf1
			w.wbuf1 = wbuf
		}
	}

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

首先判断wbuf1中是否有灰色对象，如果没有就将wbuf1和wbuf2进行交换，如果两个wbuf均为空，那么就需要请求全局工作缓存中的灰色对象了，与全局工作缓存的交互保证了每个P上绑定的gcWork不至于太忙也不至于太闲。

5.3.3 balance

在gcDrain的源码中，如果全局工作wbuf为空，会尝试使用balance()函数将本地wbuf的一部分灰色对象贡献给全局wbuf

func (w *gcWork) balance() {
	if w.wbuf1 == nil {
		// 这里wbuf1, wbuf2队列还没有初始化
		return
	}
	// 如果wbuf2不为空，则上交到全局，并获取一个空的队列给wbuf2
	if wbuf := w.wbuf2; wbuf.nobj != 0 {
		putfull(wbuf)
		w.flushedWork = true
		w.wbuf2 = getempty()
	} else if wbuf := w.wbuf1; wbuf.nobj > 4 {
		// 把未满的wbuf1分成两半，并把其中一半上交到全局队列
		w.wbuf1 = handoff(wbuf)
		w.flushedWork = true // handoff did putfull
	} else {
		return
	}
	...
}

如果wbuf2不为空，意味着wbuf1与wbuf2已经进行过一次交换了，说明此时该p上的gcWork的工作量是比较大的，为了缓解工作压力，balance()函数会将wbuf2中的灰色对象全部flush到全局wbuf中。除了会扫描wbuf2以外，balance()还会扫描wbuf1中的灰色对象，如果wbuf1中的灰色对象的个数大于4，也会将wbuf1中的一半的灰色对象flush到全局wbuf中。

5.3.4 wbBufFlush

除了wbuf1和wbuf2以外，还有一个专门存放由写屏障产生的灰色对象，我们称之为wbbuf，在gcDrain中只使用了wbBufFlush函数将wbbuf中的灰色对象flush到全局wbuf中。

写屏障产生灰色对象后会把灰色对象放入到wbbuf中，等到wbbuf满了之后就flush到全局wbuf中。

5.4 gcDrain函数

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
	// 此处一定要开启写屏障，不开启就会抛出错误
	if !writeBarrier.needed {
		throw("gcDrain phase incorrect")
	}
	// 这一部分代码和调度有关，每个p都有固定的扫描灰色对象的工作量
	...
	
	// 如果根对象未扫描，则先扫描根对象，Jobs为根对象总数，next相当于一个对象任务的取数器
	if work.markrootNext < work.markrootJobs {
		// 一直循环直到被抢占或者STW
		for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
			// 从根对象扫描队列取出一个值
			job := atomic.Xadd(&work.markrootNext, +1) - 1
			if job >= work.markrootJobs {
				break
			}
			// 将会扫描根对象，并把它加入到标记队列gcWork中，即把对象变为灰色
			markroot(gcw, job)
			// 退出标记任务的条件，与调度有关
			...
			go done
		}
	}
	// 当根对象全部put到标记队列中，消费标记队列，根据对象图进行消费
	// 一直循环直到被抢占或者STW
	for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
		// 如果全局工作缓存为空,将本地的一部分工作放回全局队列中
		if work.full == 0 {
			/** balance函数用来平衡各个核的工作量**/
			gcw.balance()
		}
		// 获取任务，消费workbuf中的灰色对象
		// 使用tryGetFast快速获取工作队列中的对象，tryGet方法虽然可以获取，但是代价较大
		b := gcw.tryGetFast()
		if b == 0 {
			/****tryGet函数用来获取工作缓存中的灰色对象****/
			b = gcw.tryGet()
			if b == 0 {
				/****wbBufFlush函数将写屏障生成的灰色对象flush到全局工作缓存****/
				wbBufFlush(nil, 0)
				b = gcw.tryGet()
			}
		}
		// 获取不到对象，标记队列已为空，跳出循环
		if b == 0 {
			// Unable to get work.
			break
		}
		// 扫描获取到的对象
		scanobject(b, gcw)
		// 与调度有关，每个p只干自己分内之事
		...
	}
done:
	// 结束的相关收尾工作
	...
}

对于gcDrain函数，可以理解为一个生产者消费者问题，生产者生产灰色对象放入wbuf中，

其中write Barrier、mark root以及scan stack都是提供灰色对象的，这些操作中都会有着greyObject这个函数的影子。

func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
............
		if span.spanclass.noscan() {
			// 将灰色对象涂黑
			gcw.bytesMarked += uint64(span.elemsize)
			return
		}
	}
............
	// 将对象放入wbuf中，也就是将对象涂灰
	if !gcw.putFast(obj) {
		/****put函数将灰色对象放入工作缓存中****/
		gcw.put(obj)
	}
}

这个函数不仅仅是一个消费者，它也是一个生产者。

scanObject这个函数就是三色标记法中通过灰色对象去扫描该对象的引用对象，并将其涂灰

func scanobject(b uintptr, gcw *gcWork) {
	// 获取 b 的 heapBits 对象
	hbits := heapBitsForAddr(b)
	// 获取span
	s := spanOfUnchecked(b)
	// span对应的大小
	n := s.elemsize
	if n == 0 {
		throw("scanobject n == 0")
	}
	// 如果对象过大，切割后扫描
	// 每次最大只扫描128KB
	if n > maxObletBytes {
		if b == s.base() {
			if s.spanclass.noscan() {
		                // 涂黑操作
				gcw.bytesMarked += uint64(n)
				return
			}
			// 将多于128KB的对象重新放回gcworker中，下次再扫描
			for oblet := b + maxObletBytes; oblet < s.base()+s.elemsize; oblet += maxObletBytes {
				if !gcw.putFast(oblet) {
					gcw.put(oblet)
				}
			}
		}
		n = s.base() + s.elemsize - b
		if n > maxObletBytes {
			n = maxObletBytes
		}
	}

	var i uintptr
	for i = 0; i < n; i += sys.PtrSize {
		// 为了求出偏移量i，与传入的b做计算得到灰色对象真正的内存地址
        ...
		// 取出指针的值
		obj := *(*uintptr)(unsafe.Pointer(b + i))

		if obj != 0 && obj-b >= n {
			// 根据地址值去堆中查找对象
			if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
				// 调用 geryobject 标记对象并把对象放到标记队列中
				greyobject(obj, b, i, span, gcw, objIndex)
			}
		}
	}
	gcw.bytesMarked += uint64(n)
	gcw.scanWork += int64(i)
}

scanObject除了生产灰色对象到wbuf中以外，也会将灰色对象涂黑，所以grayObject，scanObject以及生产灰色对象的write Barrier、mark root以及scan stack组成了一个生产和消费灰色对象的生态圈，从而实现了三色标记算法。

七. 总结

说完上面的内容，再来看火焰图是不是就清晰很多了呢，大平顶出现的位置是scanObject，findObject等函数，这些函数主要的作用就是寻找灰色对象引用的对象并将其涂黑，为什么这里这些函数花费了大量的时间呢，是因为常驻于内存中结构体指针的数目太大了，所以减小垃圾回收压力的一个方法就是减少常驻于内存的结构体指针。