Golang学习 - 垃圾回收机制（GC）

垃圾回收(Garbage Collection，简称GC)是编程语言中提供的自动的内存管理机制，可以自动释放不需要的内存对象，并让出存储器资源。

一、垃圾回收的认识

1.1、垃圾回收的定义

当程序向操作系统申请的内存不再需要时，垃圾回收主动将其回收并供其他代码进行内存申请时候复用，或者将其归还给操作系统，这种针对内存级别资源的自动回收过程，即为垃圾回收。而负责垃圾回收的程序组件，即为垃圾回收器。
垃圾回收器的执行过程被划分为两个半独立的组件：

赋值器（Mutator）：这一名称本质上是在指代用户态的代码。因为对垃圾回收器而言，用户态的代码仅仅只是在修改对象之间的引用关系，也就是在对象图（对象之间引用关系的一个有向图）上进行操作。
回收器（Collector）：负责执行垃圾回收的代码。

1.2、根对象

根对象在垃圾回收的术语中又叫做根集合，它是垃圾回收器在标记过程时最先检查的对象。

下面的都是根对象

全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量。
执行栈：每个 goroutine 都包含自己的执行栈，这些执行栈上包含栈上的变量及指向分配的堆内存区块的指针。
寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某些赋值器分配的堆内存区块。

1.3、常见的垃圾回收机制

GC 算法其存在形式可以归结为追踪（Tracing）和引用计数（Reference Counting）这两种形式。

追踪式 GC：

从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆并确定需要保留的对象，从而回收所有可回收的对象。

引用计数式 GC：

每个对象自身包含一个被引用的计数器，当计数器归零时自动得到回收。

二、Go Gc

2.1、标记-清除（mark and sweep）算法

Golang1.3之前的时候主要用的普通的标记-清除算法，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段

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

标记清除算法明了，但是需要在一开始就需要进行 STW（stop the world）让程序暂停，效率很低。

2.2、三色标记

三色标记法实际上就是通过三个阶段的标记来确定清除的对象都有哪些。
白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收；
黑色对象：已经被标记（不会被回收）
灰色对象：活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

简单来说三色标记在工作的时候程序中不存在任何的黑色对象，垃圾收集的根对象会被标记成灰色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束。

三色标记垃圾收集器的执行过程

从灰色对象的集合中选择一个灰色对象并将其标记成黑色；
将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；
重复上述两个步骤直到对象图中不存在灰色对象；

A、F 是根节点，所以标记为灰色
从灰色的集合中取出一个 A，并标记为黑色
将 A 指向的对象 B 标记为灰色

下面是三色标记完成之后的状态：

用户程序对标记结果的影响

用户程序可能在标记执行的过程中修改对象的指针，所以三色标记清除算法本身是不可以并发或者增量执行的，它仍然需要 STW。

用户程序建立了从 A 对象到 D 对象的引用，但是因为程序中已经不存在灰色对象了，所以 D 对象会被垃圾收集器错误地回收。这种情况叫悬挂指针，即指针没有指向特定类型的合法对象，影响了内存的安全性，想要并发或者增量地标记对象还是需要使用屏障技术。

2.3、屏障技术

内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束。

想要在并发或者增量的标记算法中保证正确性（对象不丢失），我们需要达成以下两种三色不变性中的一种

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

插入写屏障

可以满足强三色不变式(不存在黑色对象引用白色对象的情况了，因为白色会强制变成灰色)

1
2
3

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

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

举例：在A对象引用B对象的时候，B对象被标记为灰色。(将B挂在A下游，B必须被标记为灰色)

上图是垃圾收集器和用户程序交替运行的场景：

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

在 Go 语言 v1.7 版本之前,会使用插入写屏障保证强三色不变性，但是运行时并没有在所有的垃圾收集根对象上开启插入写屏障。在实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描

删除写屏障

因为一旦该写屏障开始工作，它会保证开启写屏障时堆上所有对象的可达，所以也被称作快照垃圾收集（Snapshot GC）

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

被删除的对象，如果自身为灰色或者白色，那么被标记为灰色。

上图是垃圾收集器和用户程序交替运行的场景:

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

混合写屏障
Go V1.8版本引入了混合写屏障机制（hybrid write barrier），避免了对栈重新扫描的过程，极大的减少了STW的时间

混合写屏障规则&&具体操作：

GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
GC期间，任何在栈上创建的新对象，均为黑色。
被删除的对象标记为灰色。
被添加的对象标记为灰色。