GC

基础概念

标记算法

• Go采用可达性分析，GC Roots主要是全局变量、协程栈等
• 具体通过三色标记法来做可达性分析，类似BFS，流程如下
  • 所有对象分为白色（垃圾对象），黑色（已扫描的存活对象），灰色（待扫描的存活 对象）
  • a. 开始时认为所有对象都是白色，遍历GC Roots，将根对象指向的所有对象标记为灰色
  • b. 取出一个灰色对象A，将A指向的所有对象标记为灰色，然后将A标记为黑色（扫描完成）
  • c. 循环执行b，直到没有灰色对象；所有对象分为黑白两种，白色可回收，黑色存活

GC算法

• Go采用标记-清除算法，清除会产生内存碎片，但是由于Go采用tcmalloc做内存管理，tcmalloc本身是碎片化的内存管理方案，因此产生内存碎片这一点对Go来说问题不大
• Tips：Java为什么不采用标记-清除？Java的垃圾回收器大都采用复制算法/标记压缩算法，无论哪种，都涉及对堆内存的移动，而Go却不用。核心原因是两种语言的内存分配策略不同。Java的内存分配策略比较简单，简单来说，会有一个指向堆顶的指针，代表已经使用的内存，分配x大小的内存时，只需要把堆顶指针后移x即可。如果采用标记清除，清除后堆顶指针没法前移，必须压缩内存才行。所以Java的内存管理相对来说是“懒惰”的，更多的依赖于Java的GC。即使对于CMS收集器采用标记清除算法，在运行一段时间后仍然需要压缩内存。

Go GC发展史

• Go GC可以以1.5和1.8作为两个重要节点
• 1.5以前是比较原始的GC，STW严重，1.5种支持并发标记清除，基本可以达到生产水平
• 1.8对并发标记阶段做了进一步优化，STW时间大幅度减少，可控制在1ms以下
• 1.8以后核心的流程基本不变，主要是对一些细节优化；具体STW时间只能作为参考，实际还是要考虑机器的内存大小以及负载等情况
• 纵观这几个阶段，可以发现无论哪种语言，GC发展都是朝着这几个方向走
  • 单线程GC -》多线程GC
  • STW GC -》并行GC
  • 在实现标记和两阶段都能和用户线程并行后，进一步压缩STW时间

GC原理

并发的三色标记法

• 三色标记法的正确性：标记阶段如果全程STW，三色标记法可以正确标记，但如果要和mutator并行，由于mutator会改变引用关系，可能会破坏三色标记法的正确性，导致漏标存活对象。参考下图，最终C会被漏标

• 简单分析可以发现当下述两个条件同时满足时，会破坏三色标记法的正确性（漏标存活对象）
  • 条件1：mutator让黑色对象引用白色对象C，如上图A.field1 = C（A为黑色，C为白色）
  • 条件2：mutator删除了最后一个灰色对象指向白色对象C的引用（让白色对象失去了灰色对象的保护），如上图B.field1 = nil（B为灰色，field1为白色），这里为nil只是一个特殊情况，其实赋值为其他对象也是同理，对于原先的field1（C）来说，都是删除了引用
• 因此为了保住三色标记法正确性，只要破坏上述的某个条件即可，根据这两个条件有的文章也引出了强弱三色不变性的概念

写屏障

• 写屏障
  • Go 1.5和1.8引入了多种写屏障，正是为了保证并发标记过程中三色标记法的正确性。所谓屏障，就是在赋值操作（引用关系变更）前的一些hook操作
  • Go的写屏障是在编译的过程中嵌入到代码中的，对于所有赋值操作，都会嵌入写屏障，具体执不执行得看屏障是否开启。具体可以在Go编译后的汇编语言中佐证
  • Go的写屏障主要有Dijkstra插入屏障和Yuasa删除屏障两种
  • 栈上不开启写屏障：写屏障对性能有一定的影响，而Go更多时候是对栈上对象进行操作（由于逃逸分析大多数对象分配在栈上），程序运行时栈的变化是很迅速的，加上一个Go程序可能会有成百上千个协程栈，出于性能考虑，Go团队设计了栈上对象写操作不开启写屏障；也正是因为这个原因，导致了1.5的STW需要rescan协程栈，1.8引入混合写屏障，其实都是为了在栈上不开启写屏障时，能够确保三色标记法的正确性
• Dijkstra插入屏障
  • 定义：当mutator让黑色对象引用白色对象时，将白色对象标记为灰色；eg. A.field1 = C，若C为白色，会被标记为灰色
  • 可以看到插入屏障破坏了条件1，将C标记成灰色，这样就不存在黑色对象引用白色对象了（实际变成黑色对象引用灰色对象）
  • 代码实现如下：slot理解为原对象（field1），ptr理解为即将指向的对象（C），在执行赋值操作*slot = ptr 前，shade(ptr)会将即将指向的ptr（C）标记为非白色（灰色）

• Yuasa删除屏障
  • 定义：当mutator删除灰色对象到白色对象的引用时，会将被删除的白色对象标记为灰色；eg. B.field1 = nil时，若field1为白色，标记为灰色
  • 删除屏障破坏了条件2，将field1标记为灰色，这样就不存在删除灰色到白色对象的引用了（实际变成删除灰色对象到灰色对象的引用）
  • 代码实现如下：slot理解为field1，ptr理解为nil，执行赋值前将slot（field1）指向的对象标记为非白色（灰色）

• 混合屏障
  • 将删除和插入屏障结合到一起
  • 代码实现如下：对于A.field1 = B，会将原先的field1指向的对象以及即将指向的对象B标记为非白色（灰色）

Go GC写屏障演变

• Go v1.5只引入了插入屏障，可以解决【并发的三色标记法】中提到的漏标存活对象情况，如下面【图一】，由于A.field1=C会触发插入屏障，所以C被标记为灰色
• 但是前面提到，写屏障只会在堆上开启，对于栈上对象的写操作，不会触发，所以当进行【图二】的操作时，仍然会漏标对象
• Go v1.5采用的补偿措施便是并发扫描结束后STW，rescan所有协程栈，这样C会被重新标记到。当然这也增大了STW时间

【图一】 【图二】

• Go v1.8使用了混合写屏障，如下图，B.field1= nil时，由于B是堆上的对象，触发删除屏障，C被标记为灰色

• 到这里，混合屏障可以保证并发标记时，不会漏标对象，同时标记结束STW时，不需要rescan协程栈；混合屏障通用栈上不开启，它可以保证无论是对堆还是栈上对象的写操作，都不会漏掉存活对象，具体怎么证明，其实不大好解释，官方也没给出证明；但我们可以设想一些特殊情况

标记模式

• 并发标记阶段，每个P（GMP模型中的调度器）会有一个gcwork，该结构是Producer/Consumer模型，负责存储灰色对象，同时有一个全局的work，如果某个P产生灰色对象速度过快，会dispose到全局work中
• 同时每个P中会有一个标记协程（mark worker），负责消费gcwork进行标记，为了避免影响Mutator，Go GC保证这些worker只会占用25%的CPU
• 为了控制25%的CPU，Go GC会给每个worker设置一个标记模式，共有以下三种模式
  • gcMarkWorkerDedicatedMode：这种模式下worker会专心负责标记任务直到结束，不会被其他协程抢占
  • gcMarkWorkerFractionalMode：这种模式下worker会负责标记，但是可以被抢占
  • gcMarkWorkerIdleMode：当P没有其他协程可以调度时，才会执行标记协程
• 在GC开启前，会根据25%的比例以及GOPROCS的个数计算出需要gcMarkWorkerDedicatedMode和gcMarkWorkerFractionalMode两种模式的协程个数，例如如果GOPROCS为6，那么需要1个gcMarkWorkerDedicatedMode和1个gcMarkWorkerFractionalMode模式的协程
• 并发标记时，在协程调度过程中，会在合适时间执行findRunnable（）方法，看看当前有没有需要执行的worker，如果有，则以相应的模式启动worker，并将数量-1；等到这个P的worker执行完后，再归将对应的标记模式数量+1，让给其他P去执行

• Tips：每个worker只会处理自己P上的gcwork，处理完后归还标记模式，交给另外的P处理。那么如果自己的gcwork处理完后，后面就不会再处理了，在其他worker执行期间自己的gcwork会由于mutator的屏障产生灰色对象吗？答案是不会，因为当自己的gcwork处理完了，就证明这个协程栈已经被标记完了，对象要么是黑色要么是白色（确定不可达），所以不可能再访问到可能存活的白色对象

  辅助标记

清除阶段

源码解读