language-agnostic - 三色增量更新 GC : Does it need to scan each stack twice?

Question

让我给你简单介绍一下三色 GC(以防有人读过它但从未听说过)；如果您不在乎，请跳过它并跳转到问题。

三色 GC 的工作原理

在三色 GC 中，对象具有三种可能颜色中的一种；白色、灰色和黑色。三色 GC 可以描述如下:

所有对象最初都是白色的。

由于全局变量或堆栈变量引用了它(“根对象”)，因此所有可访问的对象都是灰色的。

我们取任何灰色对象，找到它对白色对象的所有引用，并将这些白色对象着色为灰色。然后我们将物体本身涂成黑色。

只要我们有灰色对象，我们就继续第 3 步。

如果我们不再有灰色对象，那么所有剩余的对象要么是白色的，要么是黑色的。

所有黑色物体都已被证明是可达的，并且必须保持活力。所有白色对象都无法访问并且可以删除。

到目前为止，这并不太复杂……至少如果 GC 是 StW(停止世界)，这意味着它会在收集垃圾时暂停所有线程。如果它是并发的，则三色 GC 具有一个必须始终为真的不变量:

黑色物体不能指代白色物体!

这对于 StW GC 自动适用，因为之前已经检查了每个黑色的对象，并且它指向的所有白色对象都是灰色的，因此黑色对象可能只引用其他黑色对象或灰色对象。

如果线程没有暂停，线程可以执行会破坏此不变量的代码。有几种方法可以防止这种情况:

捕获对指针的所有读取访问，并查看此读取访问是否是对白色对象进行的。如果是，请立即将该对象着色为灰色。如果现在将此对象的引用分配给黑色对象，则无关紧要，对象不再是灰色而不是白色(此实现使用读取屏障)

捕获对指针的所有写访问，并查看分配的对象是否为白色，分配给的对象是否为黑色。如果是，则将白色物体涂成灰色。这是更明显的做事方式，但也需要更多的处理时间(此实现使用写屏障)

由于读访问比写访问更常见，即使第二种可能性在击中屏障时涉及更多的处理时间，它被调用的频率较低，并且是最受欢迎的。像这样工作的 GC 被称为“增量更新 GC”。

这两种技术都有一种替代方法，称为 SatB(开头的快照)。这种变体的工作方式略有不同，考虑到并非真的有必要一直保持不变式，因为只要 GC 知道这个白色对象曾经是并且在当前 GC 循环期间仍然可以访问(要么因为仍然有灰色对象引用这个白色对象，或者因为这个白色对象的 a ref 被放到一个显式堆栈上，GC 在运行时也会考虑这个堆栈出灰色物体)。 SatB 收集器在实践中更常用，因为它们有一些优点，但恕我直言，它们更难实现。

我在这里指的是增量更新 GC，它使用变体 2:每当代码尝试使黑色对象指向白色对象时，它会立即将对象着色为灰色。这样这个对象就不会在收集周期中丢失。

问题

关于三色 GC 的内容到此为止。但是有一点我不了解三色 GC。假设我们有一个对象 A，它被堆栈引用并且它本身引用一个对象 B。

stack -> A.ref -> B

现在 GC 开始一个循环，停止线程，扫描堆栈并看到 A 可直接访问，将 A 着色为灰色。一旦完成对整个堆栈的扫描，它会再次取消暂停线程并在步骤 (3) 处开始处理。在它开始做任何事情之前，它被抢占(可能发生)并且线程再次运行并执行以下代码:

localRef = A.ref; // localRef points to B
A.ref = NULL;     // Now only the stack points to B
sleep(10000);     // Sleep for the whole GC cycle

由于不变量没有被违反，B 是白色的，但是没有被赋值给一个黑色的物体，B 的颜色没有改变，它仍然是白色的。 A 不再引用 B，因此在处理“灰色”A 时，B 不会改变其颜色，A 将变为黑色。在循环结束时，B仍然是白色的，看起来像垃圾。但是，localRef 指的是 B，因此它不是垃圾。

问题

我是对的，三色 GC 必须扫描每个线程的堆栈两次吗？在最开始时，识别根对象(颜色变灰)，然后在删除白色对象之前再次识别，因为这些对象可能会被堆栈引用，即使没有其他对象不再引用它们。到目前为止，我所看到的算法的描述都没有提到有关扫描堆栈两次的任何内容。他们都只是说，并发使用时，重要的是始终强制执行不变量，否则会丢失可达对象。但据我所知，这还不够。堆栈必须被视为一个单一的大对象，一旦被扫描，“堆栈是黑色的”，堆栈的每次 ref 更新都必须使对象变成灰色。

如果确实如此，使用增量更新可能比我最初想象的更棘手，并且有一些性能缺陷，因为堆栈更改是最频繁的。

Answer 1

一些术语:

让我给出一些名称，以便解释更清楚。

变量是数据的任何槽，它可能包含一个指针并且可能随着时间而改变。这包括全局变量、局部变量、CPU 寄存器和分配对象中的字段。

在三色增量或并发 GC 中，存在三种类型的变量:

真正的根，总是可以访问的(CPU 寄存器、全局变量)；

快速变量，以停止世界的方式扫描；

慢变量，用颜色处理。慢变量是彩色对象中的字段。

“真根”和“快速变量”以后统称为根。

应用程序线程被称为修改器，因为它们改变了变量的内容。

对于增量或并发 GC，GC 暂停会定期发生。世界停止(mutator 暂停)，并扫描根。该扫描揭示了对彩色物体的许多引用。相应地调整对象颜色(此类白色对象变为灰色)。

当 GC 是增量的时，会发生一些对象扫描事件:扫描一些灰色对象(并涂成黑色)，使引用的白色对象变灰。此事件(“标记”)会维持一段时间，但不一定只要有灰色对象。在某个时刻，标记停止，世界被唤醒。 GC 被称为“增量”，因为 GC 循环以小增量执行，与 mutator 事件交错。

在并发 GC 中，灰色对象的扫描与 mutator 事件同时发生。一旦根部被扫描，世界就会被唤醒。对于并发 GC，访​​问屏障实现起来有点复杂，因为它们必须处理来自 GC 线程的并发访问；但在概念层面上，这与增量 GC 没有太大区别。并发 GC 可以看作是对增量 GC 的优化，它利用了多个 CPU 内核的存在(当只有一个内核时，并发 GC 比增量 GC 优势不大)。

根不需要受到访问屏障的保护，因为它们是在世界停止的情况下进行扫描的。当同时满足以下条件时，GC 标记阶段结束:

刚刚扫描了根；

所有对象都是黑色或白色，但不是灰色。

所以这种情况只能在暂停期间发生。此时，扫描阶段开始，在此期间释放白色物体。扫描可以增量或同时进行；扫描期间创建的对象会立即涂成黑色。扫描完成后，可以进行新的 GC 标记阶段:对象(此时全部为黑色)都重新绘制为白色(这是通过简单地更改解释颜色位的方式自动完成的)。

变量分类:

说了这么多，我现在可以回答你的问题了。有了上面的描述，问题就变成了:根是什么？这实际上取决于实现；有几种可能性和权衡。

必须始终扫描真正的根；真正的根是 CPU 寄存器内容和全局变量。请注意，堆栈不是真正的根；只有当前堆栈帧指针是。

由于快速变量可以无障碍访问，因此习惯上使堆栈帧成为快速变量(即根也是如此)。这是因为虽然写访问在系统范围内很少见，但它们在局部变量中却很常见。已经测量到(在一些 Lisp 程序中)大约 99% 的(指针值的)写操作都有一个局部变量作为目标。

在分代 GC 的情况下，快速变量通常会进一步扩展:“年轻代”包括一个特殊的新对象分配区域，长度有限，并作为快速变量进行扫描。快速变量的优点是快速访问(因此得名)；缺点是所有这些快速变量只能在暂停(世界停止)期间扫描。快速变量的大小需要权衡，这通常会转化为对年轻代大小的限制。更大的年轻代以更长的暂停为代价提高了平均性能(通过减少访问障碍的数量)。

在另一个极端，您可能根本没有快速变量，也没有根，只有真正的根。然后将堆栈帧作为对象处理，每个对象都有自己的颜色。暂停是最小的(仅仅是十几个寄存器的快照)，但即使访问局部变量也必须使用屏障。这是昂贵的，但有一些优点:

可以对暂停时间做出硬保证。如果堆栈帧是根，这是很困难的，因为每个新线程都有自己的堆栈，因此当启动新线程时，根的总大小可能会增长到任意数量。如果只有 CPU 寄存器和全局变量(典型情况下不超过几十个，并且它们的数量在编译时已知)是根，那么停顿可以保持很短。

这允许在堆中动态分配堆栈帧。如果您使用协程和延续，就像 Scheme 的 call/cc 一样，这是必需的。原始。在这种情况下，帧不再作为纯“堆栈”处理。在 GC 感知语言中正确处理延续主要需要动态分配函数框架。

可以使堆栈帧非根，同时保持年轻代为根。仍然可以保证暂停时间(取决于年轻代的大小，这是固定的)，并且可以应用一些技巧来确保堆栈帧在其功能处于事件状态时在年轻代中。这样可以保证对局部变量的无障碍访问。所有这些都不是真正免费的，但是对于大多数用途来说，它可以变得足够高效。

另一个概念 View :

另一种查看根处理的方法如下:根是不始终保持三色规则(无黑白指针)的变量；这些变量可以不受约束地改变。但是必须通过停止世界并扫描它们来定期使它们重新排列。

在实践中，mutator 正在与 GC 竞争。 Mutators 创建新对象，并指向它们；每次暂停都会创建新的灰色对象。在并发或增量 GC 中，如果让 mutator 使用 root 的时间过长，那么每次暂停都可能创建一大批新的灰色对象。在最坏的情况下，GC 无法足够快地扫描对象以跟上灰色对象的创建速度。这是一个问题，因为白色对象只能在清除阶段释放，只有在 GC 可能完成其标记的某个时间点才能达到该阶段。增量 GC 的常用实现策略是在每次暂停期间扫描灰色对象，以获得与根的总大小成正比的总大小。因此，暂停时间仍然受根总大小的限制，如果比例因子很好地平衡，那么可以保证 GC 最终会终止标记阶段并进入清除阶段。

在并发 GC 中，事情稍微复杂一些，因为 mutator 在野外自由漫游。一个可能的实现将在世界仍然停止时进行一点增量标记。

引用书目:

Garbage Collection: Algorithms for Automatic Dynamic Memory Management : 一本关于垃圾收集的必读书。