GO垃圾回收学习

Posted by DeepBlue on 08-17,2021

Go垃圾回收学习

标记清除法

标记清除(Mark-Sweep)算法是最常见的垃圾收集算法,标记清除收集器是跟踪式垃圾收集器,其执行过程可以分成标记(Mark)和清除(Sweep)两个阶段:

  1. 标记阶段 — 从根对象出发查找并标记堆中所有存活的对象;
  2. 清除阶段 — 遍历堆中的全部对象,回收未被标记的垃圾对象并将回收的内存加入空闲链表;

在标记要STW(Stop The World)因为在标记阶段如果我们不将程序暂停的话可能在标记过程中已经被标记为不可达的对象重新与GC ROOT建立了引用关系,这时候我们将这个对象清除掉的话就会发生不应该被回收的对象却被回收了这种事情,这在内存管理中是非常严重的错误,我们将这种错误称为悬挂指针,即指针没有指向特定类型的合法对象,影响了内存的安全性。

在清除阶段

三色标记法

Go语言采用三色抽象的标记方法进行内存垃圾的标记以及清除,三色标记法即将内存中的所有对象抽象成三种颜色的对象,分别是灰色、黑色和白色三种对象,这三种色彩的对象分别对应不同类型的对象,具体描述如下:

  • 白色对象 — 潜在的垃圾,其内存可能会被垃圾收集器回收;
  • 黑色对象 — 活跃的对象,包括不存在任何引用外部指针的对象以及从根对象可达的对象;
  • 灰色对象 — 活跃的对象,因为存在指向白色对象的外部指针,垃圾收集器会扫描这些对象的子对象;

三色不变性

  • 强三色不变性 — 黑色对象不会指向白色对象,只会指向灰色对象或者黑色对象;
  • 弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径

三色标记算法执行过程

1.将程序创建的对象都标记为白色

img

2.GC开始:扫描所有可到达的对象,标记为灰色

img

3.从灰色对象中找到其引用对象标记为灰色,把灰色对象本身标记为黑色

img

4.监视对象中的内存修改,并持续上一步的操作,直到灰色标记的对象不存在

img

5.回收所有白色对象

img

6.把所有的黑色对象变成白色对象,以便于下一次GC工作的进行。

img

三色标记算法完成后就可以将所有的白色对象(垃圾)进行清理,在清理过程中是可以和用户程序进行并发的,因为黑色对象是程序恢复后接着使用的对象,如果不碰触黑色对象,只清除白色的对象,肯定不会影响程序逻辑。所以:清除操作和用户逻辑可以并发。

Go并发标记的实现

为了提高GO在垃圾清理方面的效率,我们有没有一种方法使得标记过程也可以使得GC程序和用户程序并发执行或者减短STW的时间呢?答案是可以的。

为了使的GC过程中用户程序STW的时间变得更短(变得更短不代表不会STW,只是相较于传统的标记清除方法STW时间更短,而不是完全没有STW)GO使用了写屏障技术来缩短STW的时间。

什么是写屏障?

“写屏障”这个词虽然看起来高深,但是它的含义却相当naive——就是对一个对象引用进行写操作(即引用赋值)之前或之后附加执行的逻辑,相当于为引用赋值挂上的一小段钩子代码。

插入写屏障

Dijkstra 在 1978 年提出了插入写屏障,通过如下所示的写屏障,用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性:

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

上述插入写屏障的伪代码非常好理解,每当执行类似 *slot = ptr 的表达式时,我们会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的,那么该函数会将该对象设置成灰色,其他情况则保持不变。

dijkstra-insert-write-barrier

假设我们在应用程序中使用 Dijkstra 提出的插入写屏障,在一个垃圾收集器和用户程序交替运行的场景中会出现如上图所示的标记过程:

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色;
  2. 用户程序修改 A 对象的指针,将原本指向 B 对象的指针指向 C 对象,这时触发写屏障将 C 对象标记成灰色;
  3. 垃圾收集器依次遍历程序中的其他灰色对象,将它们分别标记成黑色;

Dijkstra 的插入写屏障是一种相对保守的屏障技术,它会将有存活可能的对象都标记成灰色以满足强三色不变性。在如上所示的垃圾收集过程中,实际上不再存活的 B 对象最后没有被回收;而如果我们在第二和第三步之间将指向 C 对象的指针改回指向 B,垃圾收集器仍然认为 C 对象是存活的,这些被错误标记的垃圾对象只有在下一个循环才会被回收。

插入式的 Dijkstra 写屏障虽然实现非常简单并且也能保证强三色不变性,但是它也有明显的缺点。因为栈上的对象在垃圾收集中也会被认为是根对象,所以为了保证内存的安全,Dijkstra 必须为栈上的对象增加写屏障或者在标记阶段完成重新对栈上的对象进行扫描,这两种方法各有各的缺点,前者会大幅度增加写入指针的额外开销,后者重新扫描栈对象时需要暂停程序,垃圾收集算法的设计者需要在这两者之间做出权衡。

删除写屏障

删除写屏障,一旦该写屏障开始工作,它会保证开启写屏障时堆上所有对象的可达,所以也被称作快照垃圾收集(Snapshot GC)

writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时,将白色的老对象涂成灰色,这样删除写屏障就可以保证弱三色不变性,老对象引用的下游对象一定可以被灰色对象引用。

yuasa-delete-write-barrier

假设我们在应用程序中使用删除写屏障,在一个垃圾收集器和用户程序交替运行的场景中会出现如上图所示的标记过程:

  1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色;
  2. 用户程序将 A 对象原本指向 B 的指针指向 C,触发删除写屏障,但是因为 B 对象已经是灰色的,所以不做改变;
  3. 用户程序将 B 对象原本指向 C 的指针删除,触发删除写屏障,白色的 C 对象被涂成灰色
  4. 垃圾收集器依次遍历程序中的其他灰色对象,将它们分别标记成黑色;

上述过程中的第三步触发了删除写屏障的着色,因为用户程序删除了 B 指向 C 对象的指针,所以 C 和 D 两个对象会分别违反强三色不变性和弱三色不变性:

  • 强三色不变性 — 黑色的 A 对象直接指向白色的 C 对象;
  • 弱三色不变性 — 垃圾收集器无法从某个灰色对象出发,经过几个连续的白色对象访问白色的 C 和 D 两个对象;

删除写屏障通过对 C 对象的着色,保证了 C 对象和下游的 D 对象能够在这一次垃圾收集的循环中存活,避免发生悬挂指针以保证用户程序的正确性。

混合写屏障

在 Go 语言 v1.7 版本之前,运行时会使用 Dijkstra 插入写屏障保证强三色不变性,但是运行时并没有在所有的垃圾收集根对象上开启插入写屏障。因为应用程序可能包含成百上千的 Goroutine,而垃圾收集的根对象一般包括全局变量和栈对象,如果运行时需要在几百个 Goroutine 的栈上都开启写屏障,会带来巨大的额外开销,所以 Go 团队在实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描,在活跃 Goroutine 非常多的程序中,重新扫描的过程需要占用 10 ~ 100ms 的时间。

Go 语言在 v1.8 组合 Dijkstra 插入写屏障和 Yuasa 删除写屏障构成了如下所示的混合写屏障,该写屏障会将被覆盖的对象标记成灰色并在当前栈没有扫描时将新对象也标记成灰色

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

为了移除栈的重扫描过程,除了引入混合写屏障之外,在垃圾收集的标记阶段,我们还需要将创建的所有新对象都标记成黑色,防止新分配的栈内存和堆内存中的对象被错误地回收,因为栈内存在标记阶段最终都会变为黑色,所以不再需要重新扫描栈空间。

GO GC执行流程

阶段说明赋值器状态
SweepTermination清扫终止阶段,为下一个阶段的并发标记做准备工作,启动写屏障STW
Mark扫描标记阶段,与赋值器并发执行,写屏障开启并发
MarkTermination标记终止阶段,保证一个周期内标记任务完成,停止写屏障STW
GCoff内存清扫阶段,将需要回收的内存归还到堆中,写屏障关闭并发
GCoff内存归还阶段,将过多的内存归还给操作系统,写屏障关闭并发

gc-process

  1. 清理终止阶段;
    1. 暂停程序,所有的处理器在这时会进入安全点(Safe point);
    2. 如果当前垃圾收集循环是强制触发的,我们还需要处理还未被清理的内存管理单元;
  2. 标记阶段;
    1. 将状态切换至 _GCmark、开启写屏障、用户程序协助(Mutator Assists)并将根对象入队;
    2. 恢复执行程序,标记进程和用于协助的用户程序会开始并发标记内存中的对象,写屏障会将被覆盖的指针和新指针都标记成灰色,而所有新创建的对象都会被直接标记成黑色;
    3. 开始扫描根对象,包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构,扫描 Goroutine 栈期间会暂停当前处理器;
    4. 依次处理灰色队列中的对象,将对象标记成黑色并将它们指向的对象标记成灰色;
    5. 使用分布式的终止算法检查剩余的工作,发现标记阶段完成后进入标记终止阶段;
  3. 标记终止阶段;
    1. 暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序;
    2. 清理处理器上的线程缓存;
  4. 清理阶段;
    1. 将状态切换至 _GCoff 开始清理阶段,初始化清理状态并关闭写屏障;
    2. 恢复用户程序,所有新创建的对象会标记成白色;
    3. 后台并发清理所有的内存管理单元,当 Goroutine 申请新的内存管理单元时就会触发清理;