Go1.5的垃圾回收

2015-06-30

Go1.5的垃圾回收是一个非分代，非移动的，并发的，三色的标记清扫垃圾回收。

简单解释一下，非分代是指Go1.5的垃圾回收没有使用分代垃圾回收算法，非移动是指没有做内存的整理和紧缩，这里的"并发"是指在垃圾回收的时候，用户代码可以同时运行。三色标记清扫是一个经典的垃圾回收算法，更多基础知识相关可以看另一篇博客，本文假设读者对于垃圾回收有一些基本的了解。

Go1.5垃圾回收的实现被划分为五个阶段：

• GCoff 垃圾回收关闭状态
• GCscan 扫描阶段
• GCmark 标记阶段，write barrier生效
• GCmarktermination 标记结束阶段，STW，分配黑色对象
• GCsweep 清扫阶段

从比较宏观的角度，描述Go1.5的GC流程：

1. 从GCoff切换到GCscan阶段
2. 等待所有P都获知这个变化。这时所有的goroutine都会经过一个GC安全点，并且知道当前进入了GCscan阶段
3. 扫描各个goroutine栈，将所有遇到的指针标记并插入队列
4. 切换为GCmark阶段
5. 等待所有P获知这处变化
6. write barrier生效，所有的黑色/灰色/白色对象到白色对象的修改都会被捕获，标记并插入队列。malloc会分配白色对象
7. 同时，GC会遍历并标记所有可达的对象
8. GC完成对堆的标记之后，会依次处理P，从队列中拿出一些对象
9. 一旦GC将队列中所有的对象都处理完了，将进入到下一个阶段：GCmarktermination
10. 等待所有P获知这处变化
11. malloc现在分配黑色对象，未标记的可达对象会不断地减少
12. 再一次地，从队列中拿出对象并标记所有没被标记到的可达对象
13. 当所有P都处理完毕，并且没有新的灰色对象了(意味着所有可达对象都标记了)，切换到GCsweep阶段
14. 等待所有P获知这处变化
15. 从现在开始，malloc分配白色对象(使用之前需要sweep span)。不再需要write barrier
16. GC后台sweep
17. sweep完成之后，切换回GCoff，等待下一轮

扫描阶段到标记阶段切换是当没有更多的指针需要扫描时触发。扫描阶段只是将对象标记为灰色，但是不会标记为黑色。切换到标记阶段之后，write barrier生效。

Go1.5的设计目标是，尽量缩短STW(stop the world)的时间，提高应用程序的实时性。不stop the world，意味着垃圾回收过程将和用户代码同时运行。垃圾回收是在整理内存，而用户代码在分配和修改内存，让它们同时工作是很有技术挑战的。

并发的三色标记算法是一个经典算法，通过write barrier，维护"黑色对象不能引用白色对象"这条约束，就可以保证程序的正确性。Go1.5会在标记阶段开启write barrier。在这个阶段里，如果用户代码想要执行操作，修改一个黑色对象去引用白色对象，则write barrier代码直接将该白色对象置为灰色。去读源代码实现的时候，有一个很小的细节：原版的算法中只是黑色引用白色则需要将白色标记，而Go1.5实现中是不管黑色/灰色/白色对象，只要引用了白色对象，就将这个白色对象标记。这么做的原因是，Go的标记位图跟对象本身的内存是在不同的地方，无法原子性地进行修改，而采用一些线程同步的实现代价又较高，所以这里的算法做过一些变种的处理。

只有标记阶段是加了write barrier的。标记结束阶段stop the world了，没有用户代码同时运行，不加write barrier容易理解，但是扫描阶段为什么不加write barrier呢？其实，这个阶段会依次扫描各个goroutine，而当扫描其中某个goroutine时，那个goroutine是需要暂停运行的，只是不算stop the world而已。暂停后用户代码和垃圾回收不会同时修改对象，因此不需要write barrier。扫描阶段不需要进行递归地标记处理，所以其实停顿goroutine开销也不大。

扫描阶段会将各个goroutine的栈对象放到一个队列里。到标记阶段，就会从队列里取对象，并将算法执行下去。注意到还有一个标记结束阶段，为什么需要这个阶段呢？还有，为什么标记结束阶段会stop the world呢？其实从技术角度，完全不stop the world的算法是有的。Go1.5目前这么做只是考虑保持实现的简单。在标记期间，由于write barrier的存在，不停地有对象放到工作队列中，而垃圾回收则不停地从工作队列中取数据，明确一个“完成”的状态并不容易。如果stop the world，当生产者停止，消费者将队列消费完后，就是一个“完成”的状态。

扫描过程是把root集合进队列；标记过程是不停地从队列中拿数据，然后标记新的数据进队列；在标记结束阶段，stop the world之后，GC会重新执行一次扫描和标记过程。因为在扫描阶段并没有扫描所有的root集合，只扫描了goroutine的栈。而这一次，会将其它root集合进行扫描和标记。

关于分配对象的颜色问题，标记结束阶段是分配黑色对象，而其它阶段都是分配白色对象。分配白色对象，是只要接下来有活跃对象引用到它，标记的过程中算法都能保证这个对象会被打上正确的颜色。在标记结束阶段直接分配黑色对象，是因为接下来也没有标记过程了。

垃圾回收的算法需要用到一些额外的信息，比如对象标记的颜色，对象中是否包含指针（到其它对象的引用）。Go1.5使用位图来记录这些信息，每个内存地址都对应有一个位图。

有两种不同的位图表示，其中栈，数据区，bss区的位图，只需要用1位表示。因为这些是root集合对象，不需要标记是否活跃，只需要用1位来表示GC过程中是否需要访问指针。 另一种是堆位图，每个机器字长要用2个位表示。低位跟之前一样，0表示跳过，1表示需要访问指针。高位有其它含义。如果两位都是0，表示这是垃圾对象，垃圾回收不要处理它。

高位的含义由标记位对应的地址，相对于分配对象的首地址所在位置决定：

• 如果是第一个，则高位是GC标记位
• 如果是第二个，高位是GC的checkmarked位（用于调试）
• 如果是第三个或者更后，高位表示对象还在被描述中

Go1.5对2位表示的位图进行了分组处理，前面4个高位放一起，后面4个低位放一起。

标记位只是有1位，如何区分黑白灰三种颜色呢？Go1.5约定，标记并且在队列中的是灰色对象，标记了但是不在队列中的黑色对象，末标记的是白色对象。

这里面也还是有很多细节，像对象的修改并不是简单的一处内存改动，而相应的标记位也可能位到影响。还有比如memmove也是有writebarrier的，涉及到了一块bitmap的改动。memmove会发生什么事？引用这块对象的对象，都要修改。但是如何跟踪哪些对象引用这个对象呢？？？

Go1.5希望GC延迟在10ms以前，并且应用代码第50秒钟至少可以运行40秒。拿出25%的GOMAXPROCS的计算能力来执行GC。如何控制GC的频率和CPU占用率呢？Go1.5有一个GC控制器和对应的算法。

在1.5之前，垃圾回收是STW的，GC触发时机很容易捕获。当堆大小达到上一次GC完成后堆大小的两倍时，触发GC。比如上次GC完成，堆大小是4M，那么当堆增长到8M的时候会触发GC。但是在Go1.5中，分配量的计算就变得模糊了，因为应用程序可能在GC的过程中，分配对象。所以需要一个算法进行预估（GC控制器可以类比操作系统的进度调度器，控制算法可以类比进程调度的算法）。

算法比较复杂，只提一点点基本的思想，具体细节见原文。首先需要估算扫描的工作量。标记阶段消耗的CPU也是由扫描的数量控制的。然后需要用户代码协助。如果只有一个后台垃圾回收线程，而用户代码的分配速度快于标记的速度，最糟糕的情况垃圾回收将永远没机会完成。为了解决这种问题，用户代码在分配的时候可能会需要协助执行扫描的工作。接下来还需要进行CPU调度，用户代码协助会导致高估或者低估GC的CPU预算，所以要监控用户协助使用和后台回收使用的CPU，如果低于25%，切换后台扫描运行来提升GC的CPU使用率，否则可以不要运行后台收集以降低CPU。最后是触发频率控制，通过用户协助和CPU调度以及触发控制一起，创建一个反馈回路使得CPU使用率和堆增长都能达到优化目标。

本文写的超前了，目前Go1.5正式版还没放出来，不过git的代码已经可以去体验了_