gc

手动 & 自动

现代高级编程语言管理内存的方式分为两种：自动和手动，像 C、C++等编程语言使用手动管理内存的方式，工程师编写代码过程中需要主动申请或者释放内存；而 PHP、Java 和 Go等语言使用自动的内存管理系统，有内存分配器和垃圾收集器来代为分配和回收内存，其中垃圾收集器就是我们常说的 GC。主流的垃圾回收算法：

引用计数（Objective-C）
追踪式垃圾回收

用户程序（Mutator）会通过内存分配器（Allocator）在堆上申请内存，而垃圾收集器（Collector）负责回收堆上的内存空间，内存分配器和垃圾收集器共同管理着程序中的堆内存空间。

设计原理

标记清除

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

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

根对象是 mutator 不需要通过其他对象就可以直接访问到的对象。比如全局对象，栈对象中的数据等。通过Root 对象，可以追踪到其他存活的对象。
全局变量：程序在编译期就能确定的那些存在于程序整个生命周期的变量。
执行栈：每个 goroutine (包括main函数)都拥有自己的执行栈，这些执行栈上包含栈上的变量及堆内存指针。（堆内存指针即在gorouine中申请或者引用了在堆内存的变量）

E 和 F 两个对象因为从根节点不可达，所以会被当做垃圾，即待回收的对象。

传统的标记清除算法步骤：

Stop the world ( STW )
Mark：通过 Root 和 Root 直接间接访问到的对象，来寻找所有可达的对象，并进行标记。
Sweep：对堆对象迭代，已标记的对象置位标记。所有未标记的对象加入freelist，可用于再分配。
Start the world

STW：随着用户程序申请越来越多的内存，系统中的垃圾也逐渐增多；当程序的内存占用达到一定阈值时，整个应用程序就会全部暂停，垃圾收集器会扫描已经分配的所有对象并回收不再使用的内存空间，当这个过程结束后，用户程序才可以继续执行。

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，朴素的 Mark Sweep 是整体 STW，并且分配速度慢，内存碎片率高。

为什么需要 STW ?

假如不需要 STW，应用程序和垃圾回收程序同时进行，还拿上面的图来举例，此时，垃圾回收线程已经把 C 标记为可达状态，从 Root 到 C 这条链路已经结束了，因为 C 没有指向下一对象了，垃圾回收不会继续下去了。与此同时，应用程序也在并发运行，应用程序让 C 指向了 F 了。因为垃圾回收线程不会继续从 C 往下扫描标记了，F 属于不可达对象（在 GC 看来），属于待回收的垃圾。但是这种回收是错误的回收。

本来不应该被回收的对象却被回收了，这在内存管理中是非常严重的错误，我们将这种错误称为悬挂指针，即指针没有指向特定类型的合法对象，影响了内存的安全性。

三色标记清除

三色标记算法将程序中的对象分成白色、黑色和灰色三类：

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

颜色在内部实现原理：

每个 span 中有一个名为 gcmarkBits的位图属性，该属性跟踪扫描，并将相应的位设置为1。

大致步骤如下：

初始将所有内存标记（默认）为白色；
然后将 root set 加入待扫描队列(进入队列即被视为变成灰色)；
然后使用并发 goroutine 扫描队列中的指针，如果指针还引用了其他指针，那么被引用的也进入队列，自身对象视为黑色（或者没有引用其他指针了）。

那么目前为止的三色清除标记是否可以不需要 STW 呢？显然从上面的步骤来看是做不到的。因为它无法解决并发执行的悬挂指针问题。

举个例子：

灰色对象 B 中包含指向白色对象 C 的指针 e，对象 C 尚未被扫描，此时，如有其他程序，将 e 指针从 B 对象中删除，并将指向对象 C 的新指针 f 插入到黑色对象 A 中，由于对象 A 早已完成扫描，对象 C 就会一直保持白色状态直到被回收。仍然出现了悬挂指针。故标记过程需的要 STW，因为对象引用关系如果在标记阶段做了修改，会影响标记结果的正确性。

可以看出，一个白色对象被黑色对象引用，是注定无法通过这个黑色对象来保证自身存活的，与此同时，如果所有能到达它的灰色对象与它之间的可达关系全部遭到破坏，那么这个白色对象必然会被视为垃圾清除掉。故当上述两个条件同时满足时，就会出现对象丢失的问题。如果这个白色对象下游还引用了其他对象，并且这条路径是指向下游对象的唯一路径，那么他们也是都会被清除。

为了防止这种现象的发生，最简单的方式就是 STW，直接禁止掉其他用户程序对对象引用关系的干扰，但是 STW 的过程有明显的资源浪费，对所有的用户程序都有很大影响，如何能在保证对象不丢失的情况下合理的尽可能的提高 GC 效率，减少 STW 时间呢？

想要保证 mark 和程序并行（即不需要 STW ），必须保证在标记过程中增量的一些引用关系的变化要识别出来（ STW 目的就是避免出现不能识别的增量的一些引用关系）。

使用并发的垃圾回收，也就是多个 Mutator 与 Mark 并发执行，想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性(Tri-color invariant)中的任意一种：

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

细看这两个三色不变性可以看出，其实就是分别破坏了上面的同时满足的条件之一。

想要并发或者增量地标记对象还是需要使用屏障技术，可以通过屏障技术来实现这两种不变性。

写屏障

内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

内存屏障只是对应一段特殊的代码
内存屏障这段代码在编译期间生成
内存屏障本质上在运行期间拦截内存写操作，相当于一个 hook 调用。

Dijkstra 插入写屏障

强三色不变性：黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象。

如果一个黑色对象不直接引用白色对象，那么就不会出现白色对象扫描不到，从而被当做垃圾回收掉的情景。

插入屏障（写屏障）拦截将白色指针插入黑色对象的操作，标记其对应对象为灰色状态（放入灰色列表中），这样就不存在黑色对象引用白色对象的情况了，满足强三色不变式，在插入指针 f 时将 C 对象标记为灰色。

Go v1.5 就是实现的写屏障，下图写屏障的伪代码：

writePointer(slot, ptr):
    // 标灰新的指针（对象），也就是加入待扫描队列中。
    shade(ptr)
    *slot = ptr

shade(ptr) ，标灰新的指针（对象），也就是加入待扫描队列中。

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

如果对栈上的写做拦截，那么流程代码会非常复杂，并且性能下降会非常大，得不偿失。根据局部性的原理来说，其实我们程序跑起来，大部分的其实都是操作在栈上，函数参数、函数调用导致的压栈出栈、局部变量，协程栈，如果这些也全部用上写屏障，那么复杂度和性能就是越不过去的坎。

所以 Go 选择仅对堆上的指针插入增加写屏障，这样就会出现在扫描结束后，栈上仍存在黑色对象引用白色对象的情况，不满足三色不变式，所以需要对栈进行重新扫描完成剩余对象的标记，这个过程需要 STW。

因为 gc 和程序是并行的，所以在mark阶段，栈上完全可能有新的对象生成（白色对象），但是栈已经被扫描过了，所以在堆上mark结束后，stw，然后重新扫描一下栈中新生的白色对象。

初始化 GC 任务，包括开启写屏障(write barrier)和开启辅助 GC(mutator assist)，统计 root 对象的任务数量等，这个过程需要 STW。

扫描所有 root 对象，包括全局指针和 goroutine(G) 栈上的指针(扫描对应 G 栈时需停止该 G)，将其加入标记队列(灰色队列)，并循环处理灰色队列的对象，直到灰色队列为空，该过程后台并行执行。

完成标记工作，重新扫描(re-scan)栈。因为 Mark 和 mutator 是并行的，所以在 Mark 过程中可能会有新的对象分配和指针赋值，这个时候就需要通过写屏障(write barrier)记录下来，re-scan 再检查一下，这个过程也是会 STW 的。按照标记结果回收所有的白色对象，该过程后台并行执行。

Go 团队在实现上选择了在标记阶段完成时暂停程序、将所有栈对象标记为灰色并重新扫描，在活跃 goroutine 非常多的程序中，重新扫描的过程需要占用 10 ~ 100ms 的时间。

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

Yuasa 删除写屏障

弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径。

如果一个白色对象的上游有灰色对象，则这个白色对象一定可以扫描到，从而不被回收。

删除屏障也是拦截写操作的，但是是通过保护灰色对象到白色对象的路径不会断来实现的。如上图例中，在删除指针 e 时将对象 C 标记为灰色（放入灰色列表中），这样 C 下游的所有白色对象，即使会被黑色对象引用，最终也还是会被扫描标记的，满足了弱三色不变式。这种方式的回收精度低，一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮，在下一轮 GC 中被清理掉。

伪代码：

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

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

Yuasa 的删除写屏障则需要在 GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需 STW。故也称快照垃圾收集（Snapshot GC)。

为什么需要STW？
一致性：在并发环境中，如果不暂停程序直接开始标记，可能会导致一些对象被错误地标记为不可达。例如，一个对象在GC开始后被某个指针引用，而这个引用在GC开始时并不存在，导致GC认为这个对象是不可达的。因此，STW扫描堆栈来获取一个一致的快照，是确保GC标记阶段的正确性的重要步骤。
初始标记：STW扫描堆栈的目的是获取一个“初始标记”，即在GC开始时记录所有根对象（如全局变量、栈上的局部变量等）和它们所引用的对象，这些对象是不可回收的。

混合写屏障

插入屏障和删除屏障各有优缺点，Dijkstra 的插入写屏障在标记过程中无需 STW，可直接开始，并发进行，但结束时需要 STW 来重新扫描栈，标记栈上引用的白色对象的存活；Yuasa 的删除写屏障则需要在 GC 开始时 STW 扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象，但结束时无需 STW。

Go1.8 混合写屏障结合了Yuasa的删除写屏障和Dijkstra的插入写屏障。Golang 中的混合写屏障满足的是变形的弱三色不变式，同样允许黑色对象引用白色对象，白色对象处于灰色保护状态，但是只由堆上的灰色对象保护。

伪代码

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

shade(*slot)是删除写屏障的变形，例如，一个堆上的灰色对象B，引用白色对象C，在GC并发运行的过程中，如果栈已扫描置黑，而赋值器将指向C的唯一指针从B中删除，并让栈上其他对象引用它，这时，写屏障会在删除指向白色对象C的指针的时候就将C对象置灰，就可以保护下来了，且它下游的所有对象都处于被保护状态。

如果对象B在栈上，引用堆上的白色对象C，将其引用关系删除，且新增一个黑色对象到对象C的引用，那么就需要通shade(ptr)来保护了，在指针插入黑色对象时会触发对对象C的置灰操作。如果栈已经被扫描过了，那么栈上引用的对象都是灰色或受灰色保护的白色对象了，所以就没有必要再进行这步操作。

由于结合了 Yuasa 的删除写屏障和 Dijkstra 的插入写屏障的优点，只需要在开始时并发扫描各个goroutine的栈，使其变黑并一直保持，这个过程不需要 STW，而标记结束后，因为栈在扫描后始终是黑色的，也无需再进行 re-scan 操作了，减少了 STW 的时间。

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

总结下来就是：

GC刚开始的时候，会将栈上的可达对象全部标记为黑色。
GC期间，任何在栈上新创建的对象，均为黑色。

上面两点只有一个目的，将栈上的可达对象全部标黑，最后无需对栈进行STW，就可以保证栈上的对象不会丢失。有人说，一直是黑色的对象，那么不就永远清除不掉了么，这里强调一下，标记为黑色的是可达对象，不可达的对象一直会是白色，直到最后被回收。

堆上被删除（引用）的对象标记为灰色
堆上新添加（引用）的对象标记为灰色

大致流程如下：

GC 开始与根集合标记：
- GC启动时，会先进行一次短暂的停顿（STW），以初始化GC的内部状态。
- 在这次停顿中，所有活跃的对象（如全局变量、活跃栈帧中的指针等）被识别为根对象，并标记为灰色，表示它们需要被进一步扫描以确定其可达性。
并发标记阶段：
- GC与用户程序并发运行，从根集合开始，递归地扫描并标记所有可达的对象。
- 插入写屏障：当对象A新增一个指向对象B的指针时，如果对象B是白色（即未被标记），则将其标记为灰色。这确保了新增的引用不会导致对象B被错误地回收。
- 删除写屏障（在某些Go版本或实现中可能涉及，但具体行为可能有所不同）：当对象A删除一个指向对象B的指针时，如果对象B是灰色或白色，则将其重新标记为灰色（如果是白色，则直接标记为灰色；如果是灰色，则保持灰色状态）。这样做可以确保在后续扫描中，对象B仍然会被访问到，从而防止其被错误地回收。
栈上对象的处理：
- 在GC期间，栈上创建的新对象最初是未标记的（即白色的），但由于它们是活跃对象，因此它们会很快被GC识别并处理。具体来说，当GC的标记器遍历到包含这些新对象的栈帧时，它们会被标记为灰色，并在后续的扫描过程中变为黑色。
标记完成与清理：
- 当并发标记阶段完成足够的工作量或达到预定条件后，GC会再次执行STW，以完成剩余的标记工作（关闭写屏障等），并准备进入清理阶段。
- 清理阶段与用户程序并发进行，回收所有未被标记为可达（即黑色和灰色之外的对象）的内存。
对象删除与可达性：
- 需要注意的是，对象被删除（即其引用被移除）并不直接导致其被标记为灰色或任何其他特定颜色。相反，对象的可达性是通过GC的扫描过程来确定的。如果一个对象在扫描过程中没有被任何可达对象引用，则它最终会被识别为不可达，并在清理阶段被回收。

标记过程

前置知识：了解 go 的内存模型。

我们从 span 角度来看看标记过程。

垃圾收集器从 root set 开始然后跟随指针递归整个内存空间。分配于 noscan 的 span 的对象, 不会进行扫描。然而，此过程不是由同一个 goroutine 完成的，每个指针都排队在工作池中，然后，先看到的被标记为工作协程的后台协程从该池中出队，扫描对象，然后将在其中找到的指针排入队列。

标记结束后，黑色对象是内存中正在使用的对象，而白色对象是要收集的对象。由于struct2的实例是在匿名函数中创建的（其中一种情况），并且无法从堆栈访问，因此它保持为白色，可以清除。

GC 触发时机

gcTriggerHeap：当所分配的堆大小达到阈值（由控制器计算的触发堆的大小）时，将会触发。
gcTriggerTime：当距离上一个 GC 周期的时间超过一定时间时，将会触发。时间周期以runtime.forcegcperiod 变量为准，默认 2 分钟。
手动触发的 runtime.GC 方法。
gcTriggerCycle：如果没有开启 GC，则启动 GC。

Go GC 过程

标记

Marking setup

为了打开写屏障，必须停止每个goroutine（STW），让垃圾收集器观察并等待每个goroutine进行函数调用，等待函数调用是为了保证goroutine停止时处于安全点。

stw_mark

// 如果goroutine4 处于如下循环中，运行时间取决于slice numbers的大小
func add(numbers []int) int {
    var v int
    for _, n := range numbers {
             v += n
     }
     return v
}

下面的代码中，由于for{}循环所在的goroutine 永远不会中断，导致始终无法进入STW阶段，资源浪费；Go 1.14 之后，此类goroutine 能被异步抢占，使得进入STW的时间不会超过抢占信号触发的周期，程序也不会因为仅仅等待一个goroutine的停止而停顿在进入STW之前的操作上。

func main() {
    go func() {
        for {
        }
    }()
    time.Sleep(time.Milliecond)
    runtime.GC()
    println("done")
}

Marking

一旦写屏障打开，垃圾收集器就开始标记阶段，垃圾收集器所做的第一件事是占用25%CPU。

标记阶段需要标记在堆内存中仍然在使用中的值。首先检查所有现goroutine的堆栈，以找到堆内存的根指针。然后收集器必须从那些根指针遍历堆内存图，标记可以回收的内存。

当存在新的内存分配时，会暂停分配内存过快的那些 goroutine，并将其转去执行一些辅助标记（Mark Assist）的工作，从而达到放缓继续分配、辅助 GC 的标记工作的目的。

Mark 终止

关闭写屏障，执行各种清理任务（STW - optional ）

Sweep（清理）

清理阶段用于回收标记阶段中标记出来的可回收内存。当应用程序goroutine尝试在堆内存中分配新内存时，会触发该操作，清理导致的延迟和吞吐量降低被分散到每次内存分配时。

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

清除阶段出现新对象：

清除阶段是扫描整个堆内存，可以知道当前清除到什么位置，创建的新对象判定下，如果新对象的指针位置已经被扫描过了，那么就不用作任何操作，不会被误清除，如果在当前扫描的位置的后面，把该对象的颜色标记为黑色，这样就不会被误清除了。

GC 演示过程

package main

import (
	"os"
	"runtime"
	"runtime/trace"
)

func gcfinished() *int {
	p := 1
	runtime.SetFinalizer(&p, func(_ *int) {
		println("gc finished")
	})
	return &p
}
func allocate() {
	_ = make([]byte, int((1<<20)*0.25))
}
func main() {
	f, _ := os.Create("trace.out")
	defer f.Close()
	trace.Start(f)
	defer trace.Stop()
	gcfinished()
	// 当完成 GC 时停止分配
	for n := 1; n < 50; n++ {
		println("#allocate: ", n)
		allocate()
	}
	println("terminate")
}

运行程序

$ GODEBUG=gctrace=1 go run main.go                                                                       
gc 1 @0.005s 3%: 0.023+0.87+0.059 ms clock, 0.19+0.80/0.42/0+0.47 ms cpu, 4->4->0 MB, 5 MB goal, 8 P

栈分析

gc 1      : 第一个GC周期
@0.005s   : 从程序开始运行到第一次GC时间为0.001 秒
5%        : 此次GC过程中CPU 占用率

wall clock
0.023+0.87+0.059 ms clock
0.023 ms  : STW，Marking Start, 开启写屏障
0.87 ms   : Marking阶段
0.059 ms  : STW，Marking终止，关闭写屏障

CPU time
0.19+0.80/0.42/0+0.47 ms cpu
0.19 ms   : STW，Marking Start
0.80 ms  : 辅助标记时间
0.42 ms  : 并发标记时间
0 ms   : GC 空闲时间
0.47 ms   : Mark 终止时间

4->4->0 MB， 5 MB goal
4 MB      ：标记开始时，堆大小实际值
4 MB      ：标记结束时，堆大小实际值
0 MB      ：标记结束时，标记为存活对象大小
5 MB      ：标记结束时，堆大小预测值

8 P
8P       ：本次GC过程中使用的goroutine 数量