关于golang:Go语言GC实现原理及源码分析-go1157

转载请申明出处哦~，本篇文章公布于 luozhiyun 的博客：https://www.luozhiyun.com/arc…

本文应用的 Go 的源码 1.15.7

介绍

三色标记法

三色标记法将对象的色彩分为了黑、灰、白，三种色彩。

1. 彩色：该对象曾经被标记过了，且该对象下的属性也全副都被标记过了（程序所须要的对象）；
2. 灰色：该对象曾经被标记过了，但该对象下的属性没有全被标记完（GC 须要从此对象中去寻找垃圾）；
3. 红色：该对象没有被标记过（对象垃圾）

在垃圾收集器开始工作时，从 GC Roots 开始进行遍历拜访，拜访步骤能够分为上面几步：

1. GC Roots 根对象会被标记成灰色；
2. 而后从灰色汇合中获取对象，将其标记为彩色，将该对象援用到的对象标记为灰色；
3. 反复步骤 2，直到没有灰色汇合能够标记为止；
4. 完结后，剩下的没有被标记的红色对象即为 GC Roots 不可达，能够进行回收。
   流程大略如下：
   

三色标记法所存在问题

多标 - 浮动垃圾问题

假如 E 曾经被标记过了（变成灰色了），此时 D 和 E 断开了援用，按理来说对象 E/F/G 应该被回收的，然而因为 E 曾经变为灰色了，其仍会被当作存活对象持续遍历上来。最终的后果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。

这部分本应该回收 然而没有回收到的内存，被称之为“浮动垃圾”。过程如下图所示：

漏标 - 悬挂指针问题

除了下面多标的问题，还有就是漏标问题。当 GC 线程曾经遍历到 E 变成灰色，D 变成彩色时，灰色 E 断开援用红色 G，彩色 D 援用了红色 G。此时切回 GC 线程持续跑，因为 E 曾经没有对 G 的援用了，所以不会将 G 放到灰色汇合。只管因为 D 从新援用了 G，但因为 D 曾经是彩色了，不会再从新做遍历解决。

最终导致的后果是：G 会始终停留在红色汇合中，最初被当作垃圾进行革除。这间接影响到了应用程序的正确性，是不可承受的，这也是 Go 须要在 GC 时解决的问题。

内存屏障

为了解决下面的悬挂指针问题，咱们须要引入屏障技术来保障数据的一致性。

A memory barrier, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction. This typically means that operations issued prior to the barrier are guaranteed to be performed before operations issued after the barrier.

内存屏障，是一种屏障指令，它能使 CPU 或编译器对在该屏障指令之前和之后收回的内存操作强制执行排序束缚，在内存屏障前执行的操作肯定会先于内存屏障后执行的操作。

那么为了在标记算法中保障正确性，那么咱们须要达成上面任意一个条件：

强三色不变性（strong tri-color invariant）：彩色对象不会指向红色对象，只会指向灰色对象或者彩色对象；弱三色不变性（weak tri-color invariant）：即使彩色对象指向红色对象，那么从灰色对象登程，总存在一条能够找到该红色对象的门路；

依据操作类型的不同，咱们能够将内存屏障分成 Read barrier（读屏障）和 Write barrier（写屏障）两种，在 Go 中都是应用 Write barrier（写屏障），起因在《Uniprocessor Garbage Collection Techniques》也提到了：

If a non copying collector is used the use of a read barrier is an unnecessary expense.there is no need to protect the mutator from seeing an invalid version of a pointer. Write barrier techniques are cheaper, because heap writes are several times less common than heap reads

对于一个不须要对象拷贝的垃圾回收器来说，Read barrier（读屏障）代价是很高的，因为对于这类垃圾回收器来说是不须要保留读操作的版本指针问题。相对来说 Write barrier（写屏障）代码更小，因为堆中的写操作远远小于堆中的读操作。

来上面咱们看看 Write barrier（写屏障）是如何做到这一点的。

Dijkstra Write barrier

Go 1.7 之前应用的是 Dijkstra Write barrier（写屏障），应用的实现相似上面伪代码：

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

如果该对象是红色的话，shade(ptr)会将对象标记成灰色。这样能够保障强三色不变性，它会保障 ptr 指针指向的对象在赋值给 *slot 前不是红色。

如下，根对象指向的 D 对象标记成彩色并将 D 对象指向的对象 E 标记成灰色；如果 D 断开对 E 的援用，改成援用 B 对象，那么这时触发写屏障将 B 对象标记成灰色。

Dijkstra Write barrier 尽管实现十分的简略，并且也能保障强三色不变性，然而在《Proposal: Eliminate STW stack re-scanning》中也提出了它具备一些毛病：

In particular, it presents a trade-off for pointers on stacks: either writes to pointers on the stack must have write barriers, which is prohibitively expensive, or stacks must be permagrey.

因为栈上的对象在垃圾收集中也会被认为是根对象，所以要么为栈上的对象减少写屏障，但这会大幅度减少写入指针的额定开销；要么当产生栈上的写操作时，将栈标记为恒灰（permagrey）。

Go 1.7 的时候抉择的是将栈标记为恒灰，但须要在标记终止阶段 STW 时对这些栈进行从新扫描（re-scan）。起因如下所形容：

without stack write barriers, we can‘t ensure that the stack won’t later contain a reference to a white object, so a scanned stack is only black until its goroutine executes again, at which point it conservatively reverts to grey. Thus, at the end of the cycle, the garbage collector must re-scan grey stacks to blacken them and finish marking any remaining heap pointers.

Yuasa Write barrier

Yuasa Write barrier 是 Yuasa 在《Real-time garbage collection on general-purpose machines》中提出的一种删除屏障（deletion barrier）技术。其思维是当赋值器从灰色或红色对象中删除红色指针时，通过写屏障将这一行为告诉给并发执行的回收器。

该算法会应用如下所示的写屏障保障增量或者并发执行垃圾收集时程序的正确性，伪代码实现如下：

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

Hybrid write barrier

下面说了在 Go 1.7 之前应用的是 Dijkstra Write barrier（写屏障）来保障三色不变性。Go 在从新扫描的时候必须保障对象的援用不会扭转，因而会进行暂停程序（STW）、将所有栈对象标记为灰色并从新扫描，这通常会耗费 10～100 毫秒的工夫。

通过 Proposal: Eliminate STW stack re-scanning https://go.googlesource.com/p… 的介绍，能够晓得为了打消从新扫描所带来的性能损耗，Go 在 1.8 的时候应用 Hybrid write barrier（混合写屏障），联合了 Yuasa write barrier 和 Dijkstra write barrier，实现的伪代码如下：

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

这样做不仅简化 GC 的流程，同时缩小标记终止阶段的重扫老本。混合写屏障的根本思维是：

the write barrier shades the object whose reference is being overwritten, and, if the current goroutine’s stack has not yet been scanned, also shades the reference being installed.

翻译过去就是：对正在被笼罩的对象进行着色，且如果以后栈未扫描实现，则同样对指针进行着色。

同时，在 GC 的过程中所有新调配的对象都会立即变为彩色，在内存调配的时候 go\src\runtime\malloc.go 的 mallocgc 函数中能够看到：

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer { 
    ...  
    dataSize := size
    // 获取 mcache，用于解决微对象和小对象的调配
    c := gomcache()
    var x unsafe.Pointer
    // 示意对象是否蕴含指针，true 示意对象里没有指针
    noscan := typ == nil || typ.ptrdata == 0
    // maxSmallSize=32768 32k
    if size <= maxSmallSize {
        // maxTinySize= 16 bytes 
        if noscan && size < maxTinySize {...} else {...}
        // 大于 32 Kb 的内存调配, 通过 mheap 调配
    } else {...} 
    ...
    // 在 GC 期间调配的新对象都会被标记成彩色
    if gcphase != _GCoff {gcmarknewobject(span, uintptr(x), size, scanSize)
    }
    ...
    return x
}

在垃圾收集的标记阶段，将新建的对象标记成彩色，避免新调配的栈内存和堆内存中的对象被谬误地回收。

剖析

GC phase 垃圾收集阶段

GC 相干的代码在 runtime/mgc.go 文件下。通过正文介绍咱们能够晓得 GC 一共分为 4 个阶段：

1.sweep termination（清理终止）

1. 会触发 STW，所有的 P（处理器）都会进入 safe-point（平安点）；2. 清理未被清理的 span，不晓得什么是 span 的同学能够看看我的：详解 Go 中内存调配源码实现 https://www.luozhiyun.com/archives/434；

2.the mark phase（标记阶段）

1. 将 _GCoff GC 状态 改成 _GCmark，开启 Write Barrier（写入屏障）、mutator assists（帮助线程），将根对象入队；2. 恢复程序执行，mark workers（标记过程）和 mutator assists（帮助线程）会开始并发标记内存中的对象。对于任何指针写入和新的指针值，都会被写屏障笼罩，而所有新创建的对象都会被间接标记成彩色；3. GC 执行根节点的标记，这包含扫描所有的栈、全局对象以及不在堆中的运行时数据结构。扫描 goroutine 栈绘导致 goroutine 进行，并对栈上找到的所有指针加置灰，而后继续执行 goroutine。4. GC 在遍历灰色对象队列的时候，会将灰色对象变成彩色，并将该对象指向的对象置灰；5. GC 会应用分布式终止算法（distributed termination algorithm）来检测何时不再有根标记作业或灰色对象，如果没有了 GC 会转为 mark termination（标记终止）；

3.mark termination（标记终止）

1. STW，而后将 GC 阶段转为 _GCmarktermination, 敞开 GC 工作线程以及 mutator assists（帮助线程）；2. 执行清理，如 flush mcache；

4.the sweep phase（清理阶段）

1. 将 GC 状态转变至 _GCoff，初始化清理状态并敞开 Write Barrier（写入屏障）；2. 恢复程序执行，从此开始新创建的对象都是红色的；3. 后盾并发清理所有的内存治理单元

须要留神的是，下面提到了 mutator assists，因为有一种状况：

during the collection that the Goroutine dedicated to GC will not finish the Marking work before the heap memory in-use reaches its limit

因为 GC 标记的工作是调配 25% 的 CPU 来进行 GC 操作，所以有可能 GC 的标记工作线程比应用程序的分配内存慢，导致永远标记不完，那么这个时候就须要应用程序的线程来帮助实现标记工作：

If the collector determines that it needs to slow down allocations, it will recruit the application Goroutines to assist with the Marking work. This is called a Mutator Assist. One positive side effect of Mutator Assist is that it helps to finish the collection faster.

下次 GC 机会

下次 GC 的机会能够通过一个环境变量 GOGC 来管制，默认是 100，即增长 100% 的堆内存才会触发 GC。