博客

一、三色标记法

作为一门现代化的语言，golang与java一样，都在语言中内置了垃圾回收的功能，不需要程序员自己去回收堆内存。而垃圾回收中，最重要的两个部分就是垃圾检测算法以及垃圾回收算法。垃圾检测算法决定哪些对象是垃圾需要被回收，主要有引用计数法和三色标记法。垃圾回收算法决定如何回收内存，主要有标记清除，标记复制，标记压缩等。由于，引用计数法有循环引用的问题，故大部分的语言都是使用三色标记法来检测垃圾的。

三色标记法需要从一些对象出发进行分析，这些对象是必然不能被回收的，如栈对象（栈是程序自动回收的，不归垃圾回收管理），全局变量等，它们会被记录起来，放到一个列表中，这个列表在java中就被称为GC ROOTS，golang也有类似的定义。三色标记法从GC ROOTS出发，通过层层引用，GC ROOTS可以间接引用到的对象（对象可达），就不是垃圾，而GC ROOTS无法间接引用到的对象（对象不可达），就是我们需要回收的垃圾，而使用算法分析对象可不可达的过程，也被称为可达性分析。

三色标记法将对象分为三种颜色，黑色，灰色以及白色。

• 黑色，黑色代表着对象是GC ROOTS可达的，即该对象是有用的，不能被回收。而且该对象引用的对象都已经被标记，一般标记的过程就是将该对象所有引用的对象加入灰色对象的队列。
• 灰色，灰色代表该对象是GC ROOTS可达的，并且该对象引用的对象还没有被全部标记，一旦该对象引用的对象被全部标记，灰色就会变为黑色。
• 白色，白色代表该对象是GC ROOTS不可达的或者当前还没有标记到该对象，一般GC（垃圾回收）开始时，GC ROOTS中的对象会全部标记为黑色，GC ROOTS引用的对象标记为灰色，其它的对象则是白色，当GC的标记过程结束以后，剩下的白色对象就是要清除的垃圾。

二、并发垃圾回收

在垃圾回收的过程中，有一部分操作是必须要停止所有的用户线程，这被称为STW（stop the world）。STW时间的长短，是衡量一个垃圾回收算法好坏的一个重要因素。在Golang早期的时候，Golang的垃圾回收是串行的，所以STW时间特别长，达到几百毫秒，在后续的更新中，Golang垃圾回收进行了多次优化。Golang1.8后，STW停顿时间低于1ms。

Golang垃圾回收一般分为2个阶段，标记和清除。而在Golang早期的时候， 标记和清除都要STW，并且标记和清除都是单线程执行。

首先，标记需要扫描整个内存的对象，这也就意味着，内存越大，标记的时间越久，而STW的时间也会越久。其次，单线程只能使用单个cpu，无法最大化的使用多核服务器上的cpu资源。所以在Golang后面的优化中，就改用了多线程来清理垃圾。同时，清理阶段垃圾回收线程可以和用户线程一起并行执行，使STW时间降低了一些。


但是，标记阶段仍然会耗时几百毫秒，对于正常的程序来说，仍然是较难接受的。故必须要对标记进行优化，减少标记阶段的STW时间。golang的思路时，通过STW进行初始标记，然后退出STW状态，通过多个goroutine进行并发标记，标记完之后进入STW，进行再次标记以校准对象的状态，标记完成后，进行清理阶段的准备。最后退出STW状态，恢复用户goroutine，并启动多个垃圾清理协程进行垃圾清理。



之所以需要再次STW进行最终标记，是因为并发标记时，如果用户协程和标记协程对同一个变量进行操作，会产生浮动垃圾（是需要处理的垃圾，但是标记算法误认为它不是垃圾）或者错误标记把有用的对象标记为垃圾。前者只是少回收一点垃圾，但是后者会导致用户的数据丢失，导致程序运行出错。

三、并发垃圾回收导致的问题

如上图所示，当标记协程标记完C后，C已经变为黑色对象，而黑色对象是不会再次扫描的。然后用户断开了A对象对C对象的链接，所以C对象其实已经是垃圾了，可以被回收。但是由于C对象是黑色对象，所以本轮GC是不会回收C对象的，C对象就变成了浮动垃圾。当然，等到下一次GC，系统仍然可以正常回收C对象。


如上图所示，当标记协程扫描完B后，B已经变为黑色对象，此时D还没有被扫描，所以是灰色对象。然后用户让B对象引用H对象，并断开了D对象对H对象的链接。但是由于B对象是黑色对象，所以本轮GC不会被再次扫描，而只被B对象引用的H对象，仍然是白色对象，在清理阶段，就会被当场垃圾清除掉，导致程序出现问题。

浮动垃圾的问题其实并不算严重，因为下次GC仍然可以正常回收，所以该问题可以不解决。但是错误标记对象导致对象被错误清理是不能接受的。要想解决错误标记的问题，就要让三色标记法满足三色不变式。

四、三色不变式

三色不变式分为两种，强三色不变式和弱三色不变式。只要三色标记法满足其中一个，就不会出现错误标记的问题。

1.强三色不变式

强三色不变式指的是，在三色标记法进行标记时，不允许黑色对象引用白色对象。

1.弱三色不变式

弱三色不变式指的是，在三色标记法进行标记时，允许黑色对象引用白色对象，但是白色对象必须存在其他灰色对象对它的引用，或者有灰色对象对该白色对象是可达的。

五、插入写屏障

要想在三色标记法中实现三色不变式，就必须要加入一些额外的操作。在golang中，主要是依靠写屏障来实现三色不变式。写屏障，就是在对变量进行赋值的时候编译器自动插入额外的操作，如下图所示。比如说，在把白色对象赋值给黑色对象时，自动把白色对象变为灰色对象，就可以满足强三色不变式。



但是我们知道，大多数的情况下，我们都是操作栈上的变量，如果将所有的变量的赋值都加入写屏障，那么程序运行就会变慢。正常的赋值指令，翻译成汇编就是一条指令，如果加入写屏障维护三色不变式，那可能就要多加十几条汇编指令，导致程序运行GC时，将会耗费很多性能在写屏障的。所以，目前在golang实现的各个版本的写屏障，都是只对堆中变量使用写屏障，对栈中的变量则是不使用屏障。但是，如果只对堆中的变量使用写屏障，并发标记的时候毫无疑问会出问题，所以在写屏障的基础上优化出了两种解决方案，插入写屏障（incremental update）和删除写屏障（snapshot-at-the-beginning）。

在golang v1.5中，golang使用的是插入写屏障（incremental update）。插入写屏障满足的是强三色不变式，在实际算法落地的过程中，插入写屏障实现的是，不管是黑色对象还是白色对象引用其它对象，都会把被引用的对象从白色对象变为灰色对象，如果被引用的对象是灰色或者黑色则不处理。插入写屏障GC的时候，步骤如下：

1. 首先进行STW,开启GC，做完前置操作后退出STW。
2. 然后并行将GC ROOTS中的对象标记为黑色，并将其引用的对象标记为灰色。
3. 每当对象A引用一个对象X的时候，golang会调用IsStackAddr函数去判断对象A的地址是否是在栈上。如果地址位于堆中，golang就会将值标记为灰色，如果是地址位于栈中， 则不做处理。
4. 等GC协程完成整个内存的标记。
5. 再次进入STW，重新标记并扫描栈上的对象的所有可达的对象，防止栈上对象的可达对象被错误标记。
6. 在STW中完成清理阶段的前置准备。
7. 退出STW，开始并行清理垃圾。
   
   

六、删除写屏障

与插入写屏障不一样的地方在于，插入写屏障在GC开始时，并不需要把所有的栈上的对象标黑再开始。而删除写屏障需要在第一次STW需要将栈上的对象全部变为黑色对象才能开始，但是删除写屏障不需要在标记阶段结束时，再次去扫描栈上的对象。删除写屏障满足的是弱三色不变式。删除屏障GC的时候，步骤如下：

1. 首先进行STW,开启GC。
2. 将栈上的对象里面的对象全部标记为黑色，并将其引用的对象标记为灰色，然后退出STW。
3. 然后并行将GC ROOTS中的对象标记为黑色，并将其引用的对象标记为灰色。
4. 每次当用户改变一个对象X引用的对象时，golang会调用IsStackAddr函数去判断对象X的地址是否是在栈上。如果地址位于堆中，golang就会将对象X原来引用的对象标记为灰色，如果是地址位于栈中， 则不做处理。
5. 等GC协程完成整个内存的标记。
6. 再次进入STW，开始进行清理阶段的前置准备。
7. 退出STW，开始并行清理垃圾。
   
   

删除写屏障的缺点在于:

1. 初始STW时，需要将栈上的对象全部标记为黑色，并将其引用的对象标记为灰色，导致初始的STW时间变长。
2. 所有对象断开的被引用对象都会标记为灰色对象，这就意味着，这些对象中的垃圾也能存活到下一次GC开始前。所以删除写屏障的浮动垃圾会多一些。

五、混合写屏障

在golang v1.8中，综合了插入写屏障和删除写屏障，创造了一种新的写屏障，这种写屏障就被称为混合写屏障(hybrid write barrier)。混合写屏障在测试中显示，可以将STW的时间控制在50us以下。混合写屏障解决了插入写屏障扫描内存完成后需要额外重新标记栈区对象，并対栈区对象及其可达的对象进行可达性分析的缺点，也解决了删除写屏障需要在标记开始时，就必须把栈上的对象标记为黑色对象，并将其引用的对象标记为灰色的缺点。减少了GC过程中的STW时间。混合写屏障GC的工作流程如下：

1. 首先进行STW,开启GC，做完前置操作后退出STW。
2. 
   GC开始后新分配的对象会被直接标记黑色。
   
3. 然后并行将GC ROOTS中的对象标记为黑色，并将其引用的对象标记为灰色。注意在这个过程中，stack的标记是有先有后的，每个goroutine都有自己的stack，每当GC协程需要标记某个goroutine的stack时，就会停止goroutine的运行，然后在标记它对应的stack，最后在恢复goroutine。GC协程运行的过程中，除了当前正在被扫描的stack对应的goroutine不能运行以外，其它的goroutine都可以在其它的Processor上运行。
4. 每当对象A引用一个对象X的时候，golang会调用IsStackAddr函数去判断对象A的地址是否是在栈上。如果是地址位于栈中， 则不做处理。如果地址位于堆中，golang就会将对象A原来引用的对象标记为灰色，如果当前调用它的goroutine的stack还没被扫描，就会将对象A新引用的对象标记为灰色。
5. 等GC协程完成整个内存的标记。
6. 再次进入STW，在STW中完成清理阶段的前置准备。
7. 退出STW，开始并行清理垃圾。
   
   

六、混合写屏障的思考

混合写屏障的伪代码如下，其中slot是操作的变量的地址，*slot是该变量原来指向的对象的地址，ptr是将要赋值给slot的对象的地址。

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

从代码中可以看到，混合写屏障对于每一个对象都会使用删除写屏障，而插入写屏障则只有在操作的goroutine的栈未被完全扫描之前才会启用。这也就意味着goroutine对应的栈一旦被扫描，GC认为只需要删除写屏障就能保证不会出现错误标记的情况了。

首先，我们思考一下，为什么删除写屏障需要在最开始的时候将栈标记完毕。这是因为，如果删除写屏障的开始的时候没有将栈标记完毕，就会引发两个问题。

1. 当把栈对象引用的白色对象赋值给黑色的堆对象，然后断开栈对象与白色对象的引用。由于不对栈对象使用删除写屏障，导致白色对象只有黑色对象引用，白色对象会被错误回收。
2. 当把栈对象引用的白色对象赋值给黑色的栈对象，然后断开栈对象与白色对象的引用。由于不对栈对象使用删除写屏障，导致白色对象只有黑色对象引用，白色对象会被错误回收。

所以，在第一次STW的时候就将整个栈区扫描，标记完毕，删除写屏障就不会出现上述问题。而混合写屏障没有扫描标记整个栈区这个环节，同样也会面临同样的问题。

首先，我们分析一下第一个问题，这种情况下，只有对象的引用从栈区对象中，被复制到堆区对象才会有问题。因为堆区复制引用到栈区，或者堆区复制引用到堆区，当原来的堆对象断开引用都会触发混合写屏障，导致引用的对象被标记为灰色，而栈区复制引用到栈区，则可以看下面关于第二个问题的分析。问题1解决的方案就是伪代码中的

    if current stack is grey:
        shade(ptr)

当对象的引用从栈区对象中，被复制到堆区对象时。如果该goroutine的栈区的对象还没被标记，则被复制的对象就会被标记为灰色对象，必然不会被错误回收。如果该goroutine的栈区的对象已经被全部标记，则复制的对象必然已经被标记为灰色或者黑色，也必然不会被回收，这就解决了问题1。

然后再看下第2个问题，在golang语言，一个goroutine正常是无法访问到另一个goroutine的栈的，除非两种特殊的操作 —— channel和启动goroutine。所以在GC开启的情况下进行这两种操作的时候，就需要对栈对象启用混合写屏障来保证三色标记法能正确标记对象。在

Proposal: Eliminate STW stack re-scanning

中的Channel operations and go statements就对这个问题进行了解释。如果两个对象是同一个goroutine栈中的对象，则因为在GC协程标记某个栈时，对应的goroutine必定被挂起，所以当某个goroutine运行时，整个栈要么已经被标记为黑色，要么所有对象是白色的，不会出现这个goroutine的栈中一半栈对象是白色，而另一半栈对象是黑色。当栈对象互相复制自己的引用给同一个栈区的对象时，如果src栈对象和dst栈对象都是白色对象，那等下自然会被正常标记。如果都是黑色，那它们复制的引用对应的对象必然已被标记为灰色或者黑色，也不需要去特殊处理。

七、抢占试调度

在golang早期的版本中(golang v1.0)，使用的是协作试抢占。这就意味着，但GC需要STW的时候，需要等用户程序执行到safe-points(比如调用系统函数，读写channel，time.Sleep() )，但是如果用户程序一直没有执行到safe-points，那么GC永远不能完成STW。比如下面 这段代码

package main

import (
    "fmt"
)

func main() {
    for {
    }
}

在golang v1.4之后，golang变为了抢占试调度。golang在启动后，会启动一个线程运行 /src/runtime/proc.go中的sysmon函数，一旦某个goroutine运行超过10ms，sysmon就会向Goroutine对应的Processor（GMP模型里的P）发送SIGURG，然后在一系列的处理后，将超时的goroutine停止，这样类似GC这样的STW操作就能正常完成，或者其它的goroutine就有机会在该Processor上运行。

七、官方源码注释和文章

1. 
   Proposal: Eliminate STW stack re-scanning
   
2. 
   mgc.go注释
   
3. 
   mbarrier.go注释
   
4. 
   Proposal: Non-cooperative goroutine preemption