Topic 11：垃圾回收

约 4935 个字 3 行代码 20 张图片 预计阅读时间 16 分钟

Outline

• 1. 概述
• 2. Mark-and-Sweep
• 3. 引用计数/Reference Counting
• 4. 拷贝式收集/Copying Collection
• 5. 编译器接口/Interface to the Compiler 「很遗憾，不考了」

1. 概述

运行时系统/Runtime System：包含语言隐式假定的、不在程序中显式描述的各项功能，比如 POSIX 信号处理、虚拟机执行、动态类加载和自动内存管理等等。

手动内存管理会出现很多问题，比如 Double Free、Use-After Free、Memory Leak 等等，和内存有关的错误也很难定位，因此需要兼顾性能、开发负担和安全性设计内存管理。

回忆操作系统课程学过的东西，我们把内存分为静态区/Static Area、运行时栈/Run-time Stack、堆/Heap 三个区域，分别在编译期分配、记录激活记录和通过 malloc、new 等动态分配。

所谓垃圾/Garbage，就是分配了但是不再使用的堆内存。下面就产生了一块垃圾：

垃圾回收/Garbage Collection 会自动释放不再被程序使用的垃圾，这一般是运行时系统的一部分，第一次在 LISP 中被实现。其分为两个阶段：

• 垃圾检测/Garbage Detection：识别哪些对象还是活的，哪些已经死了；
• 垃圾回收/Garbage Reclamation：真正释放死对象所占空间，更新内存管理数据结构。

理想的垃圾回收器应该满足下面性质：

• 安全：只有垃圾才会被回收；
• 完全：尽可能回收所有垃圾；
• 低开销：在时间和空间上占用最小额外资源；
• 停顿短：程序会因为等待垃圾回收被阻塞；
• 并行化：可以使用别的 CPU 核来回收垃圾；
• ...

问题又来了，我们事实上可以发现判定一块内存是否是垃圾又是一个不可判定问题：假设 \(P\) 是一个不使用内存 \(M\) 的程序，如果考虑一个新的程序 \(P'\)，其运行时会先运行 \(P\)，运行完然后使用内存 \(M\)，那么 \(M\) 是否会被使用其实等价于判断 \(P\) 是否停机。丸辣！这是停机问题，不可判定。

又需要靠保守估计了，只回收那些确定一定是垃圾的内存，这样垃圾回收器就一定是安全的。主要想法是使用可达性信息，判断哪些堆分配对象可以通过指针和指针链访问到，不可访问到的对象一定不可用，因此是垃圾。

常见的垃圾回收方法有：

• 引用计数/Reference Counting：统计每一个内存单元被引用的次数，在分配新块的时候初始化，指针赋值/销毁的时候更新；
• 追踪回收/Tracing：在分配堆上内存失败的时候，GC 介入检测内存单元是否可达，常见的技术有 Mark-Sweep 和 Copying Collection；
• 现代方法还包括 Generational GC 等。

基础数据结构：有向图/Directed Graph：

• 节点是程序变量和堆上分配的记录，边代表指针，a 储存了指向 b 的指针，则对应一条有向边 a->b。
• 程序变量是有向图的根节点，可以是寄存器、栈上的局部变量/形式参数或者全局变量。
• 一个节点可达，当且仅当存在一条从根节点出发的路径到达该节点：\(r \rightarrow \cdots \rightarrow n\)。

对于这个图，图中的 · 即为变量或是 record 中的字段。如有出边，则代表它是个指针，指向一个 record。

附加数据结构：空闲链表/Free List：内存管理器需要追踪哪些部分的内存是空闲的，以便快速分配。

2. Mark-and-Sweep

2.1 概览

算法分为两个阶段：

• Mark：从根节点出发，搜索并且标记可以到达的所有节点，一般使用深度优先搜索/DFS；
• Sweep：使用线性扫描的方法扫描堆，将所有没有标记的节点放到空闲链表中，最后将所有标记的节点解除标记。

在垃圾回收之后，程序继续执行，当程序需要分配一个新的 record 的时候，都会从空闲链表中分配一个块，如果空闲链表中没有合适的块，则需要再次进行垃圾回收。

我们进行代价分析：

• 假设对的内存有 \(H\) 个字，可以达到的数据有 \(R\) 个字；
• 标记一个字的代价为 \(c_1\)，扫描一个字的代价为 \(c_2\)；
• 那么总体的开销就为 \(c_1R + c_2H\)，长期来看，分配对象数等于回收对象数，因此摊还后的代价为 \(\frac{c_1R + c_2H}{H - R}\)；
• 如果堆一直接近满，那么时间花费极大！

2.2 显式栈与指针反转

话说回来，算法的问题不仅仅在于开销，由于深度优先搜索是迭代的，极端条件下容易递归过深爆栈，\(N\) 个元素的列表就需要 \(N\) 个栈空间。解决方法是手动模拟一个栈，初始的时候压入所有的根节点，每次弹出栈顶节点 \(T\)，标记 \(T\)，把 \(T\) 指向的所有节点压入栈中，重复执行直到栈空，这样对于 \(N\) 个元素的列表就至多需要 \(N\) 个记录/字的空间了，也同时将递归转化成了迭代。

解决方法是使用一个对指针的黑魔法，也叫做指针反转/Pointer Reversal/Deutsch-Schorr-Waite Algorithm，想法是通过修改图的连接将 DFS 的栈存在图上，这就不需要栈了，具体方法如下：

• 当在搜索的时候，如果遇见一个新的 record，标记这个 record，将这个 record 的一个指针指回其在 DFS 中的父节点，这就相当于将这个 record 压入栈中；
• 当一路搜索结束的时候，如果我们不能走得更深了，就掉头，随着往回走的连接走，同时恢复指针，这就相当于弹出栈顶元素；

具体算法如下，其中 \(x\) 是当前节点，\(t\) 是回溯的时候需要恢复的父节点，\(y\) 是存储子节点和字段值的临时变量，\(done\) 代表现在处理完了多少个字段：

注意对于非指针字段，只需要单纯递增 \(done\) 即可，具体算法的使用可以参见作业题。

2.3 内存碎片

这部分呼应了 OS 的内容，堆经常会面临下面两个问题之一：

• 外部碎片/External Fragmentation：程序需要一个大小为 \(n\) 的内存区域，但是有很多大小比 \(n\) 小的空闲块，导致无法分配；
• 内部碎片/Internal Fragmentation：程序需要一块内存的时候，由于种种原因，分配的内存比实际需要的大，导致浪费。

基于内存碎片，可以分析一下 Mark-and-Sweep 的优势与缺陷：

• 优点 1：如果只有很少的垃圾，算法的效率就会很高；
• 缺点 1：如果垃圾很多，链表会很长，效率就很低；
• 优点 2：可以收集循环引用的垃圾，这一点可以参照一下 C++ 的智能指针；
• 优点 3：GC 期间数据不会移动；
• 缺点 2：正常的程序执行会因为垃圾回收被阻塞；
• 缺点 3：引起堆的内存碎片，影响很深远。

3. 引用计数/Reference Counting

主要想法：记录一下多少个指针指向每一个记录，这也就是记录引用计数/Reference Counting；当引用计数达到 0 的时候，这意味着这个记录就变成了垃圾，因此可以回收。引用计数比 Mark-and-Sweep 更积极，因为可以立即回收无引用的对象，不需要等到全局扫描。

具体来讲，如何实现记录呢？每次赋值操作都对引用计数进行更新：

• 对于赋值操作 \(x.fi = p\)，\(p\) 的引用计数增加 1，\(x.fi\) 原本指向的对象的引用计数减少 1；
• 当引用计数为 0 的时候，把 \(p\) 加入空闲链表，同时递归地对 \(p\) 的所有出边所指向的对象的引用计数减少 1；

引用计数的优点在于：

• GC 的开销是渐进式的，内存管理和程序执行可以同时进行，也可以和手动内存管理并行，就不需要专门为了进行 GC 暂停程序执行（对比 Mark-and-Sweep 需要停顿）；
• 可以立即回收复用，减少延迟，无需等到下一次内存扫描；
• 实现也相对简单，不需要复杂的图遍历算法，只需要维护计数。

缺点也很明显，也有很曹丹的问题：首先就是循环引用的问题：下面这张图中，如果解引用 A，那么就会留下 C 和 C 引用的块，这两个块循环引用，引用计数无法到 0，因此无法回收，导致内存泄漏。

另外一个缺点就是增加/减少 RC 值是非常频繁的，带来非常昂贵的开销，并且也需要在目标代码中加入大量指令。

循环引用也不是解决不了，可以考虑使用混合回收/Hybrid GC，平时用引用计数应对大多数场景，定期启动 Mark-and-Sweep 来处理残留的循环引用。别的优化方法也包括静态分析、局部变量优化、硬件支持等。

4. 拷贝式收集/Copying Collection

4.1 Cheney 算法与指针转发

主要方法是将堆内存分为两个部分：分别为 From-Space 和 To-Space，To-Space 为程序使用的堆内存空间，To-Space 暂时空闲，直到垃圾回收的时候才会被使用。

基本算法为所有空间从 From-Space 开始向上分配，直到 next == limit，也就是当 From-Space 满了的时候，将可达对象复制到 To-Space，交换两个空间的角色。

拷贝式收集的优点在于：

• 分配速度非常快，只需要将 next 指针向上移动即可；
• 不会产生内存碎片，因为每次 GC 之后所有的可达节点都在 To-Space 的前端，未使用的空间都在后面，永远不会产生外部碎片。

但是拷贝式分配的关键问题在于：

• 必须拷贝所有可达对象，这就像 Mark-and-Sweep 一样；
• 必须要保留对象之间的指针关系；
• 必须避免重复拷贝同一个对象。

和 Mark-and-Sweep 一样，拷贝式收集也依赖迭代遍历对象图，迭代式拷贝的挑战也是一样的，需要的栈的大小正比于最长的引用链长度，深度嵌套的对象图会导致栈溢出。 Cheney 的思路是在 To-Space 中使用一个工作队列，按广度优先/BFS 处理新复制的对象，思想和 DFS 中的指针反转类似，避免了 BFS 队列的额外空间。

我们的方法将 To-Space 划分为三个区域：

• 复制且扫描了的区域：这个区域内 Record 字段的所有指针都已经被处理了，因此我们就不需要再管了；
• 复制但未扫描的区域：仅仅复制了对象，但是还没有扫描对象的指针，因此需要将这些对象加入工作队列；
• 未使用的区域：这个区域是空闲的，可以用来存放新的对象。

当区分复制且扫描了的区域和复制但未扫描的区域的指针 scan 和 next 重合的时候，就意味着所有可达对象都已经被复制且扫描了，算法结束。于是 Cheney 算法被分为两个部分：算法本体和指针转发/Pointer Forwarding：

<img class="center-picture" src="assets/11 garbage/11-12.webp" alt="Copying Collection" width="550" /

主算法的逻辑：

指针转发的目的在于将每一个对象在 To-Space 中分配新的位置，保证所有的指针都准确的引用新的拷贝。为了使得避免重复拷贝一个对象，我们使用一个 trick：在复制对象之后，将对象的第一个字段改写为指向新副本的指针，这样在后续遇到同一对象引用时，直接返回该指针。一是为了判断是否已经复制过，二是为了获取新副本的地址。且使用 scan 指针和 next 指针之间的区域作为工作队列，于是指针转发算法的逻辑如下：

PPT 有更加丰富的讲解，这里就不再赘述了。

4.2 局部性

众所周知，程序的局部性非常重要，但是广度优先拷贝的局部性很差，因为在 To-Space 中的对象是按照同一深度复制，因此相邻地址的对象可能不相关，对应父子关系的对象往往分散在大跨度内存。而深度优先拷贝往往会有更加好的局部性，但是需要额外的栈空间或者指针反转/Pointer Reversal 等复杂算法。于是可以修改指针转发算法，提出一种混合拷贝算法：

方法是当拷贝一个对象的时候，尽量立刻拷贝他的一个孩子，并且持续进行深度优先拷贝，直到遇到一个已经拷贝过的对象，或者没有孩子了。最终这个算法会变成深度优先拷贝，但是确实利用了一部分局部性。

这个算法不考，但是考试可能涉及局部性。

总而言之，拷贝式收集的优点在于简单、自动处理内存碎片，并且运行时间与活跃对象数成正比，但是缺点在于浪费一半的内存，并且局部性很差，也需要精确的内存信息（比如需要区分指针字段和数据字段）。

5. 编译器接口/Interface to the Compiler

5.1 实现快速分配

尽管垃圾回收是运行时系统的一部分，但是这不代表编译器不能做任何事情。编译器可能通过下面这些方式和编译器交互：

• 生成代码在内存上分配 records；
• 为每一个 GC 周期描述根节点位置；
• 描述在堆上的 record 布局，指示字段类型；
• 生成读写屏障/Write Barrier，维持并发正确性；
• ...

高效率的内存分配和垃圾回收对于一些情况至关重要，比如函数式语言，因为函数式语言倾向于创建大量的不可变对象，并且这些对象往往需要频繁的分配和回收；以及内存密集型应用，因为每次访问往往伴随一次分配，需要快速完成。经验来说，每七条指令就有一次存储写入。一个很大的开销就是在堆上创建 record，为了实现快速的内存分配和 GC，可以使用拷贝式收集。

一般的分配流程如下：

需要注意的是，上图中的 A 和 B 都不属于分配开销，因为 A 是编译器的工作，B 是用户的工作/运行时库的工作。

这有很大的优化空间：首先，第一条和第六条就可以通过内联展开的方式，将调用函数和从函数返回优化掉，注意到 A 实际上对应的是寄存器优化中对 MOVE 指令的优化，可以直接和第三条合并掉，第四条也可以去掉，因为我们有 B 了，况且联想 C 中的 malloc 也没有清零。只剩下第二条和第五条不可以优化了，但是这两条可以在不同的分配器中共享，可以隐性优化。更加极限的操作依赖于将 next 和 limit 保存在寄存器中，完成一次检查和推进仅需 3 条机器指令，每次分配的总开销降低到大约 4 条指令。

5.2 描述数据布局

由于 GC 需要处理不同种类的 Records，因此需要编译器提供一些信息：

• 在拷贝式收集的时候，\(\mathit{scan} \leftarrow \mathit{scan} + \operatorname*{sizeof}(\mathit{record\ at\ scan})\)，因此需要提供记录的大小；
• 在拷贝式收集的指针转发的时候，需要知道哪些字段是指针，哪些是数据，因此需要提供字段类型信息；
• ...

一个简单的解决方法是编译器在编译的时候，为每一个 Record 生成一个类型描述符，这个描述符指向一个特殊类型的 Record，这个 Record 中包含所有需要的信息，比如对象的大小、指针字段的位置、还有别的字段信息。这对于面向对象语言是完全没有开销的，对于静态类型语言也就需要一个字的开销而已。

5.3 描述根节点

GC 需要从根节点开始追踪可达对象，这就需要辨别所有在寄存器、栈帧中的局部变量、临时变量、全局变量中的所有指针，并且指出他们到底是在栈上还是在寄存器中：

Tiger 的解决方法是在编译期生成一个 Pointer Map，指示哪个变量是一个指针，将这个 Map 传递给 GC，GC 使用这些指针进行遍历。因为每一条指令都有可能使得活跃临时变量集合发生改变，因此这个指针映像在程序的每一点都是不同的，因此需要但不必须在每一个点都生成 Map。这显然不切实际也不必须，因为并非每一条指令都创建新的 record。为了减少 Map 的数目，我们只在特殊的程序点生成 Map，比如在分配 record 之前、在函数调用之前（可能间接调用分配）。

GC 需要从最顶部的栈帧（调用链的终点）向下扫描栈帧，每处理完了一个栈帧，就可以通过返回地址索引到下一个栈帧的 Pointer Map，识别出栈帧中的指针。需要特殊处理 callee-saved 寄存器：考虑调用链 \(f \rightarrow g \rightarrow h\)，\(g\) 在调用 \(h\) 前，对于这些 callee-saved 寄存器，必须在 pointer map 中额外记录哪些是 \(g\) 自己使用的，哪些是从 \(f\) 继承来的。

5.4 导出指针

导出指针/Derived Pointers 是编译器需要处理的一个问题，因为编译器需要处理指针计算，而指针计算可能会产生导出指针，这些导出指针可能指向对象的任何地方：

move t1, a - 2000
move t2, t1 + i
move t3, M[t2]

显然这个 t1 就是一个导出指针，且其从基指针 a 导出，指针映像必须指示出导出指针，并且指出导出这个指针的基指针。导出指针也需要在 GC 中被处理，比如在拷贝式收集中，当基指针移动到新的地点的时候，导出指针也需要被移动到新的地点：

再考虑循环不变指针：

这里 t1 经过循环优化，变成了循环不变的导出指针，循环内部通过 M[t1 + i] 进行访问，但是如果后续没有任何代码使用基指针 a，那么 a 就被判定为死亡，但是对于 GC 来讲，基指针必须保持活跃，GC 需要直到基指针的新地址来正确更新导出指针。解决方法是添加新的规则，导出指针隐式保持基指针活跃，于是 a 就不会被判定为死亡，至少基指针的活跃区间要覆盖掉导出指针的活跃区间。