背景
最近，我在做叫 Ccache 的实验项目（https://github.com/yfractal/ccache），该项目用 Rust 实现核心功能，并与 Ruby 和 Golang 等语言进行集成。Rust 是一种系统编程语言，没有垃圾回收（GC）进行内存管理。但 Ruby 和 Golang 确实使用 GC。这引出了一个有趣的问题：Rust 如何安全有效地与使用 GC 的语言进行交互？因此，我花了一点时间了解 Ruby 的 GC 是如何工作的。
介绍
在本文中，我将描述 Ruby 2.2 引入的 RGenGC（Restricted Generational GC）是如何工作的。为了使事情更容易理解，我会先解释垃圾回收的基本原理，然后描述 RGenGC 解决的独特问题及其机制和源代码。在这个过程中，我尽量忽略不必要的细节。
垃圾回收
程序从操作系统分配虚拟内存，操作系统将虚拟内存映射到物理内存（或其他资源，如文件）。由于物理内存的限制和性能要求，程序需要在使用后将内存归还。
程序使用两种类型内存：栈内存和堆内存。Rust 主要使用栈内存，这需要在分配内存之前知道变量的大小。对于动态大小的结构（如 vector），Rust 在堆上分配内存。为了安全高效地管理内存，Rust 不允许共享可变和循环引用。这些限制使 Rust 能够使用引用计数来管理堆内存，但实现一些数据结果（双向链表）会变得困难 [1]。
C 要求程序员手动分配和释放堆内存，难以使用并容易出错。Rust 使用生命周期（lifetime）和所有权 (owership) 进行内存管理，从而达到明确、安全、高效的目的。
像 Ruby 和 Go 使用 GC——程序员不需要考虑何时释放内存，因为 GC 会处理这个事情。所以 GC 需要高效地将不再使用的内存归还系统。
Mark and Sweep 算法
Mark and Sweep 是一种检测和释放不再使用 (dead) 内存的垃圾回收算法。
为了找到不再使用 (dead) 的内存，Mark and Sweep 算法通过引用遍历所有可访问（rechable）对象。未访问到的对象被视为不活跃（dead），可以被释放。既，标记阶段标识所有可达对象并将其标记。在清除阶段，这些标记的对象被保留，而其他对象被释放。
为了遍历所有可访问对象，Mark and Sweep 使用广度优先搜索（BFS）算法。它递归地查找每个对象的所有直接引用。为了避免无限循环，访问完一个对象的所有引用用，需要标记为已被访问。
该算法维护一个队列以保存当前已知的可达对象（object）。它将一个 item 出队，并将这个 item 的所有引用入队，并将这个 item 标记为已访问。如果 item 的引用已经被标记为访问过，则不会将其添加到队列中。此过程持续到队列为空，表示所有可被访问的对象已被访问。
下面是伪代码：
queue = init_queue()
for object in global_objects:
object.visted = true
queue.enqueue(object)
while queue.is_empty() == true:
object = queue.dequeue
for reference in object.references:
if reference.visited == false
reference.visited = true
queue.enqueue(reference)
现在所有可达对象都已知，清除阶段将遍历所有对象。如果对象的已访问字段为 false，则表示对象不可访问，可以释放。
总结如下：
标记阶段：广度优先搜索标记所有活动对象。 清除阶段：扫描内存以释放未标记的对象
Mark and Compact
Mark and Sweep 可以释放不反问的对象，但它不能处理碎片问题，会在内存中创建空洞。
!
由于释放的对象是不连续的，即使总内存足够大，也有可能无法为大结构分配内存。
Mark and Compact 解决了这个问题，在标记对象的同时，将可被访问的对象重新排列，从而使空闲内存连续。
其思路是将内存分为两半：FROM space 和 TO space。当 FROM space“满”时，标记阶段开始。在标记阶段，将可被访问的对象，移动到 TO space。由于其他对象可能引用了移动的对象，需要在对象的旧内存中记录给对象已经被移动到新的地址，既 forward reference。之后将该对象，引用到的对象移动到 TO space，并更新地址。标记阶段结束后，所有可达引用都已移动到 TO space，则可释放 FROM space。
也可以将 TO space 视为 Mark and Sweep 算法中的队列，由两个指针表示队列的开始和结束。
Generational Garbage Collection
为了释放 TO space，Mark and Compact 法必须扫描所有对象，非常耗时。Generational Garbage Collection 通过多数时候仅扫描新对象来改进这一点。
Generational GC 基于一个简单的发现：如果一个对象存在很长时间，它往往会存在更长时间 [3]，新对象更有可能被回收，这意味着我们多数时候只需要检查新对象。例如，接收请求时，Rails 会创建 controller 实例，请求结束后应回收该实例。然而，数据库连接实例可能已经存在一段时间，不应回收，也不需要被回收。
简单来说，Generational GC 将对象分为两类：新生代和老年代。新生代对象是最近创建的，而老年代对象已经存在了一段时间。目标是扫描新生代对象并释放相关内存。
一个对象要被标记为不可被访问（dead），需要保证没有引用指向它。在标记阶段，我们目标是只扫描所有新生代对象。如果一个老对象引用了一个新对象，我们对其特殊记录，并在标记阶段扫描这个对象。这样就可以保证，释放一个对象的时候，没有任何其他对象引用该对象。
当我们引用一个对象的时候，例如 a.b = &c，如果 a 和 c 是同一时代，或者 a 比 c 更年轻的话，不需要做特殊处理，因为在 mark 阶段，可以被正常扫描到。当老对象，引用到新对象的时候，既 a 比 c 更老，则需要记录 a，并在 mark 阶段，扫描 a。
Ruby 的 RGenGC
Ruby 需要解决的问题
在 Ruby 2.2 之前，Ruby 只有 non-generational mark-and-sweep GC[4]。为了支持 Generational GC，我们需要一个写屏障 (Write Barrier) 来记录老对象引用新对象的情况。然而，由于 Ruby 有很多代码，以及第三方 C 扩展的存在，使得 Ruby 没办法做到向后兼容。
为了解决这个兼容性问题，Ruby 团队引入了 Write-Barrier-Unprotected Objects 这个概念。
Write-Barrier-Unprotected Objects
Write-Barrier 就是之前提到的，当老对象引用新对象的时候，需要做的记录。Unprotected 指的是，存在老对象引用了新对象，但没有记录的情况。
由于不能让所有 Ruby 对象在老对象引用新对象时使用 Write-Barrier，我们无法知道这些对象是否引用了新对象。在 Minor GC 期间，需要扫描这些对象。
Ruby RGenGC 标记步骤 [4]
1. Put the root-set objects and objects referenced from the remembered set objects into the work queue.
2. Repeat the following until the work queue is empty:
a. Dequeue an object p from the work queue.
b. For each object c referenced from p do:
i. If p is an old object:
• If c is already marked, makes c an old object and add c to the remembered set.
• If c is not marked and not an old object, makes c’s age two (becomes an old object at the next step).
ii. Increment the age of c by one, mark c, and then put c to work queue if c was not marked and is not an old object. Note that, in our implementation, if the age of an object becomes 3, the object becomes an old object.
为了确保 Write-Barrier-Unprotected Objects 的安全，Ruby 会检测这些对象并将其放入一个集合中，以便在 minor GC 期间扫描。从而 Ruby 可以安全的回收对象。
以下是相关的 Ruby 2.2 代码（删除了和本文无关代码）[6]：
static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
rgengc_check_relation(objspace, obj);
if (!gc_mark_set(objspace, obj)) return; /* already marked */
gc_aging(objspace, obj);
gc_grey(objspace, obj);
}
static void
rgengc_check_relation(rb_objspace_t *objspace, VALUE obj)
{
const VALUE old_parent = objspace->rgengc.parent_object;
if (old_parent) { /* parent object is old */
if (RVALUE_WB_UNPROTECTED(obj)) {
gc_remember_unprotected(objspace, obj)
} else {
if (!RVALUE_OLD_P(obj)) {
if (RVALUE_MARKED(obj)) {
/* An object pointed from an OLD object should be OLD. */
RVALUE_AGE_SET_OLD(objspace, obj);
if (is_incremental_marking(objspace)) {
if (!RVALUE_MARKING(obj)) {
gc_grey(objspace, obj);
}
} else {
rgengc_remember(objspace, obj);
}
} else {
RVALUE_AGE_SET_CANDIDATE(objspace, obj);
}
}
}
}
}
总结
本文介绍了几种基本的 GC 算法，以便更容易地理解 Ruby RGenGC。它没有涉及许多有趣的内容，例如并行垃圾回收器 [8]，只是讲解思路，所以有意地忽略了一些细节，比如 Mark and Compact 中，释放 TO space 之后，FROM space 会变成，TO sapce，TO space 变成 FROM space，既翻转 (flip)，因为这些并不影响理解算法主体，并且容易理解。更多的细节，可以参考一下链接 [2][3][4][5][7][8]。
原文： https://ruby-china.org/topics/43798
引用
- GhostCell: Separating Permissions from Data in Rust
- https://ruby-china.org/topics/32226
- A Real-Time Garbage Collector Based on the Lifetimes of Objects
- Gradual Write-Barrier Insertion into a Ruby Interpreter
- https://blog.peterzhu.ca/notes-on-ruby-gc/
- https://github.com/ruby/ruby/releases/tag/v2_2_1
- https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/resources/lecture-11-storage-allocation/
- https://inside.java/2022/08/01/sip062/
