从零开始理解 JavaScriptCore 中的垃圾回收

2022年7月29日

作者：徐浩然

JavaScript 依赖垃圾回收（GC）来回收内存。本文将深入探讨 JSC 的垃圾回收系统。

在开始之前，我先简单介绍一下自己。我是徐浩然，斯坦福大学的一名博士生。虽然我对 JSC 的贡献尚不多，但我发现 JSC 是优雅的编译器设计和高效实现的宝库，我的研究正在探索如何以较低的工程成本将 JSC 的设计转移到支持其他编程语言（如 Lua）的方法。这篇文章最初发布在我的博客上——非常感谢 WebKit 项目将其交叉发布到他们的官方博客！

Filip Pizlo 关于GC 的博客文章非常出色地解释了 JSC GC 的新颖之处，并将其置于学术界和工业界各种 GC 方案的背景中。然而，作为一个 GC 背景知识较少的人，我感觉仅凭这篇博客不足以让我对算法和设计动机有扎实的理解。通过深入研究代码，并在 JSC 首席开发人员 Saam Barati 的大力帮助下，我写了这篇博客文章，希望能帮助更多人理解这个精妙的设计。

JSC 中的垃圾回收器是非紧凑式、分代式且大部分[1]是并发式的。除了并发，JSC 的 GC 还大量采用无锁编程以提高性能。

正如你所想象的，JSC 的 GC 设计相当复杂。我们将不深入探讨复杂的逻辑不变量和协议，而是从一个简单的设计开始，一步步改进，最终逼近 JSC 的设计。通过这种方式，我们不仅能理解 JSC 设计为什么有效，还能理解 JSC 设计是如何随着时间的推移而构建的。

但首先，让我们了解一些背景知识。

JSC 中的内存分配

内存分配器和 GC 本质上是紧密耦合的——分配器分配内存供 GC 回收，GC 释放内存供分配器重用。在本节中，我们将简要介绍 JSC 的内存分配器。

JSC 内存分配方案的核心是数据结构BlockDirectory[2]。它实现了一个固定大小的分配器，即一个只分配特定固定大小 S 内存块的分配器。该分配器维护着它拥有的固定大小（在当前代码中为 16KB）内存页（“块”）列表以及一个空闲列表。每个块被划分为大小为 S 的单元（cell），并在其末尾有一个页脚[3]，其中包含 GC 和分配所需的元数据，例如哪些单元是空闲的。通过在页脚聚合和共享元数据，它既节省了内存又提高了相关操作的性能：我们将在本文后面详细介绍。

当 BlockDirectory 需要进行分配时，它会尝试从其空闲列表中分配。如果空闲列表为空，它会尝试遍历其拥有的块[4]，查看是否能找到一个包含空闲单元（由 GC 标记为 free）的块。如果找到，它会扫描该块的页脚元数据以找出该块中所有空闲单元[5]，并将其放入空闲列表。否则，它会从 malloc[6] 分配一个新的块。请注意，这意味着 BlockDirectory 的空闲列表只包含一个块中的单元：这在代码中被称为 m_currentBlock，我们稍后将重新讨论这一点。

BlockDirectory 作为构建块，用于构建 JSC 中的内存分配器。JSC 采用了三种分配器：

  1. CompleteSubspace：这是一种分离式分配器，负责分配小型对象（最大尺寸约 8KB）。具体来说，存在一个预定义的、呈指数增长的尺寸类别列表[7]，每个尺寸类别都使用一个 BlockDirectory 来处理分配。因此，要分配一个对象，你需要找到足够容纳该对象的最小尺寸类别，并从该尺寸类别的目录中进行分配。
  2. PreciseAllocation：这用于处理 CompleteSubspace 分配器无法处理的大型分配[8]。它只是依赖标准的（类似 malloc 的）内存分配器，尽管在 JSC 中使用了一个名为 libpas 的自定义 malloc 实现。缺点是，由于 PreciseAllocation 是按对象创建的，GC 无法聚合和共享多个对象的元数据信息，以节省内存并提高性能（像 MarkedBlock 的块页脚那样）。因此，每个 PreciseAllocation 都带有高达 96 字节的 GC 头的巨大开销，用于存储该对象 GC 所需的各种元数据信息（尽管这种开销是合理的，因为每次分配已至少为 8KB）。
  3. IsoSubspace：每个 IsoSubspace 用于分配固定类型和固定大小的对象。因此，每个 IsoSubspace 简单地持有一个 BlockDirectory 进行分配（尽管 JSC 对小型 IsoSubspace 也有优化，通过让它们由 PreciseAllocation 支持[9]）。这是一项安全强化功能，旨在使基于释放后使用（use-after-free）的攻击变得更加困难[10]。

IsoSubspace 大多数情况下是 CompleteSubspace 的简化版，因此为了本文的目的，我们将忽略它。CompleteSubspace 处理常见情况：小型分配，而 PreciseAllocation 主要是大型分配的罕见慢速路径。

分代式 GC 基础

在 JSC 的分代式 GC 模型中，堆由一个小的“新生代”（伊甸园）组成，用于存放新分配的对象；以及一个大的“老生代”，用于存放经过一个 GC 周期后仍然存活的对象。每个 GC 周期要么是新生代 GC，要么是全量 GC。新对象在伊甸园中分配。当伊甸园满时，会调用新生代 GC 来垃圾回收伊甸园中不可达的对象。伊甸园中所有存活的对象随后被视为位于老生代中[11]。要回收老生代中的对象，需要进行全量 GC。

上述方案的有效性依赖于所谓的“分代假说”：

  1. GC 回收的大多数对象是年轻对象（在伊甸园中就已消亡），因此新生代 GC（只回收伊甸园）足以回收大部分新分配的内存。

  2. 从老生代指向伊甸园的指针远比从伊甸园指向老生代或从伊甸园指向伊甸园的指针稀少，因此新生代 GC 的运行时长大致与伊甸园的大小呈线性关系，因为它只需要从老生代的一小部分开始扫描。这意味着 GC 的成本可以通过分配成本进行分摊。

内联与外联元数据：为何如此？

几乎所有 GC 方案都使用某种元数据来追踪哪些对象是存活的。在本节中，我们将解释 JSC 中 GC 元数据的存储方式，以及其设计背后的动机。

在 JSC 中，GC 管理的每个对象都带有以下元数据：

  1. GC 管理的每个对象都继承自 JSCell 类，该类包含一个 1 字节的成员 cellState。这个 cellState 是一个颜色标记，有两种颜色：白色和黑色[12]。

  2. 每个对象还有两个对象外部元数据位：isNew[13] 和 isMarked。对于由 PreciseAllocation 分配的对象，这些位位于 GC 头中。对于由 CompleteSubspace 分配的对象，这些位位于块页脚中。

乍一看这可能觉得奇怪，因为 isNew 和 isMarked 本可以存储在 cellState 的未使用位中。然而，这是有意为之的。

内联元数据 cellState 对于变异器线程（执行 JavaScript 代码的线程）来说易于访问，因为它只是对象中的一个字段。然而，对于 GC 和分配器来说，它的内存局部性较差，而 GC 和分配器需要快速遍历 CompleteSubspace 所拥有（这是常见情况）的某个块中所有对象的元数据。外联元数据则具有相反的性能特性：对于变异器线程来说，它们的访问成本更高，但由于它们被聚合成位向量并存储在每个块的页脚中，GC 和分配器可以非常快速地遍历它们。

因此，JSC 同时保留了内联和外联元数据，以兼顾两者的优点：变异器线程的快速路径将只关注内联的 cellState，而 GC 和分配器逻辑则可以利用外联位 isNew 和 isMarked 的内存局部性。

当然，这样做的代价是设计更为复杂……所以我们必须一点点地展开它。

一个非常简单的 Stop-the-World 分代式 GC

让我们从一个非常简单的设计开始，以便理解所需的基本要素。我们将设计一个分代式但 Stop-the-World（即非增量也非并发）的 GC，完全不进行任何性能优化。在这种设计中，变异器端在“安全点”[14]将控制权移交给 GC 子系统，以启动一个 GC 周期（新生代或全量）。GC 子系统从头到尾执行 GC 周期（因此，在此潜在的长时间内应用程序无法运行，故称“Stop-the-World”），然后将控制权转回给变异器端。

为此，我们暂时抛开 CompleteSubspace：它是 PrecisionAllocation 针对小型分配的优化版本，虽然它是一项重要的优化，但没有它更容易理解 GC 算法。

结果表明，在这种设计中，我们只需要一个 isMarked 位。isMarked 位将指示对象在上次 GC 周期结束时是否可达（因此，如果对象存活了一个 GC 周期，它就在老生代中）。所有对象诞生时 isMarked = false。

GC 将使用广度优先搜索（BFS）来扫描和标记对象。对于全量 GC，我们希望在开始时将所有 isMarked 位重置为 false，然后执行 BFS 来扫描并标记所有从 GC 根可达的对象。然后所有未标记的对象都被认为是死的。对于新生代 GC，我们只想扫描伊甸园空间。幸运的是，老生代中的所有对象在上次 GC 周期结束时都已被标记，因此它们自然地被 BFS 忽略，所以我们可以简单地在全量 GC 中重用相同的 BFS 算法。伪代码如下：

新生代 GC 准备阶段：无需工作。

全量 GC 准备阶段[15]

for (JSCell* obj : heap)
    obj->isMarked = false;

新生代/全量 GC 标记阶段

while (!queue.empty()) {
    JSCell* obj = queue.pop();
    obj->ForEachChild([&](JSCell* child) {
        if (!child->isMarked) {
            child->isMarked = true;
            queue.push(child);
        }
    });
}

新生代/全量 GC 回收阶段

// One can easily imagine an optimization to make eden collection
// traverse only the eden space. We ignore it for simplicity.
for (JSCell* obj : heap) {
    if (!obj->isMarked)
        free(obj);
}

但是，扫描从哪里开始，才能扫描所有可达对象呢？对于全量 GC，答案很明确：我们只需从所有 GC 根[16]开始扫描。然而，对于新生代 GC，为了可靠地扫描所有可达对象，情况稍微复杂一些：

  1. 当然，我们仍然需要将 GC 根推送到初始队列。

  2. 如果老生代中的一个对象包含指向伊甸园中对象的指针，我们需要将这个老生代对象放入初始队列[17]。

第二种情况的不变量在变异器端维护。具体来说，每当在堆中将对象 A 的指针槽写入以指向另一个对象 B 时，需要检查 A.isMarked 是否为 true 且 B.isMarked 是否为 false。如果是，则需要将 A 放入“记忆集”。新生代 GC 必须将记忆集中的对象视为 GC 根。这被称为 WriteBarrier（写屏障）。伪代码如下：

// Executed after writing a pointer to 'dst' into a field of 'obj'
if (obj->isMarked && !dst->isMarked)
    addToRememberedSet(obj);

实现增量式 GC

Stop-the-World GC 对生产环境而言并非最优。一个 GC 周期（特别是全量 GC 周期）可能耗时很长。由于变异器（应用程序逻辑）在 Stop-the-World 期间无法运行，应用程序会显得对用户无响应，这对于长时间暂停来说是非常糟糕的用户体验。

缩短这段无响应时间的自然方法是增量地运行 GC：在安全点，变异器将控制权移交给 GC。GC 只运行一小段时间，完成当前 GC 周期（新生代或全量）的一部分工作，然后将控制权返回给变异器。这样，每个 GC 周期都被分解成许多小步骤，从而使用户对无响应期的感知度降低。

增量式 GC 给 GC 方案带来了一些新的挑战。

第一个挑战是 GC 和变异器之间额外的干扰：变异器，即分配器和 WriteBarrier，必须准备好看到部分完成的 GC 周期所产生的状态。GC 端也必须在变异器端进行更改的情况下，正确标记所有可达对象。

具体来说，我们的全量 GC 必须改变：想象一下，全量 GC 扫描了某个对象 o 并将控制权交回给变异器，然后变异器更改了 o 的一个字段以指向另一个对象 dst。对象 dst 不能在扫描中被遗漏。幸运的是，在这种情况下，o 将是 isMarked 状态，而 dst 将是 !isMarked 状态（如果 dst 已经是 isMarked，那么它已经被扫描，无需担心），所以 o 将被放入记忆集。

因此，为了使全量 GC 在增量 GC 方案中正确运行，它也必须像新生代 GC 一样，将记忆集视为 GC 根。

截至目前，算法的其他部分可以保持不变（我们将正确性证明留作读者的练习）。然而，“如果 GC 周期部分运行会发生什么？”是我们添加更多优化时必须牢记在心的问题。

第二个挑战是，变异器端可以反复将老生代对象放入记忆集，导致 GC 进行冗余工作：例如，GC 从记忆集中弹出了某个对象 o，从其开始遍历，然后将控制权移交给变异器。变异器再次修改 o，并将其放回记忆集。如果这种情况发生得过于频繁，增量式 GC 可能比 Stop-the-World GC 做更多的工作。

一旦我们将 GC 变为并发式，情况会变得更糟：在并发 GC 中，由于 GC 不再窃取变异器的 CPU 时间，变异器获得更高的吞吐量，因此会向记忆集中添加更多对象。事实上，JSC 观察到在没有任何缓解措施的情况下，内存消耗高达 5 倍。因此，采用了两种技术来缓解这个问题。

第一个也是显而易见的缓解措施是让 GC 最后扫描记忆集：只有当队列为空时，我们才开始从记忆集中弹出。JSC 采用的第二个缓解措施是一种称为时空调度器的技术。简而言之，如果它观察到变异器分配过快，变异器将获得越来越少的时间配额来运行，以便 GC 能够赶上（在极端情况下，变异器将获得零时间配额，从而回退到 Stop-the-World 方法）。Filip Pizlo 的博客文章已经解释得非常清楚，如果您感兴趣，可以查看。

无论如何，让我们更新新生代/全量 GC 标记阶段的伪代码。

while (!queue.empty() || !rmbSet.empty()) {
    // Both eden GC and full GC needs to consider the remembered set
    // Prioritize popping from queue, pop remembered set last
    JSCell* obj = !queue.empty() ? queue.pop() : rmbSet.pop();
    obj->ForEachChild([&](JSCell* child) {
        if (!child->isMarked) {
            child->isMarked = true;
            queue.push(child);
        }
    });
}

整合到 CompleteSubspace 中

是时候让我们的 CompleteSubspace 分配器重新登场了，这样我们就不必承受由 PreciseAllocation 引起的每个对象巨大的 GC 头开销。

对于 PreciseAllocation，实际的内存管理工作由 malloc 完成：当变异器想要分配一个对象时，它直接 malloc；当 GC 发现一个死对象时，它直接 free。

CompleteSubspace 引入了另一个复杂性，因为它只在 16KB 块级别从 malloc 分配/释放内存，并自行进行内存管理，将块划分为提供给应用程序的单元。因此，它必须追踪其每个单元是否可用于分配。变异器从可用单元中分配，GC 则将死单元标记为可再次分配。

isMarked 位不足以让 CompleteSubspace 分配器确定一个单元是否包含存活对象：新分配的对象 isMarked = false，但它们显然是存活对象。因此，我们需要另一个位。

事实上，我们还需要支持检查单元是否包含存活对象的其他充分理由。一个典型例子是保守式栈扫描：JSC 不精确理解栈的布局，因此它需要将栈上所有可能是指针并指向存活对象的东西都视为 GC 根，这涉及检查堆指针是否指向存活对象。

人们很容易想象某种 isLive 位，对于所有存活对象都为 true，只在对象死亡时由 GC 将其翻转为 false。然而，JSC 采用了一种稍微不同的方案，这是为了促进我们稍后将提到的优化。

正如您前面所见，JSC 使用的位被称为 isNew。

然而，请牢记：您不应将 isNew 视为一个能告诉您任何与其名称相关信息，或其本身指示任何信息的位。您应该将其视为一个辅助位，其唯一目的是，当与 isMarked 协同工作时，它们能告诉您一个单元是否包含存活对象。这种思维模式在我们下一节介绍逻辑版本控制时将变得更为重要。

围绕 isNew 和 isMarked 的核心不变量是：

  1. 在任何时刻，一个对象是死的，当且仅当其 isNew = false 且 isMarked = false。

如果我们是一个 Stop-the-World GC，那么为了维护这个不变量，我们只需要以下几点：

  1. 当一个对象诞生时，它的 isNew = true 且 isMarked = false。

  2. 在每个新生代或全量 GC 周期结束时，我们将所有对象的 isNew 设置为 false。

那么，所有新分配的对象都是存活的，因为它们的 isNew 为 true。在每个 GC 周期结束时，一个对象是存活的，当且仅当其 isMarked 为 true，所以当我们（根据规则 2）将 isNew 设置为 false 后，关于死对象的不变量就被维护了，正如所期望的。

然而，在增量 GC 中，由于部分运行的 GC 周期状态可能会暴露给变异器，我们需要确保在这种情况下不变量也成立。

具体来说，在全量 GC 中，我们会在开始时将所有 isMarked 重置为 false。然后，在部分运行的 GC 周期中，变异器可能会看到一个存活对象，其 isMarked = false（因为它尚未被 GC 标记）且 isNew = false（因为它已经存活了一个先前的 GC 周期）。这违反了我们的不变量。

为了解决这个问题，在全量 GC 开始时，我们在清除 isMarked 之前，额外执行 isNew |= isMarked。现在，在整个全量 GC 周期中，所有存活对象都必须具有 isNew = true[18]，因此我们的不变量得以维护。在周期结束时，所有 isNew 位都被清除，结果所有未标记的对象都变为死的，因此我们的不变量仍然像预期一样被维护。所以让我们更新伪代码：

新生代 GC 准备阶段：无需工作。

全量 GC 准备阶段

// Do 'isNew |= isMarked, isMarked = false' for all
// PreciseAllocation and all cells in CompleteSubspace

for (PreciseAllocation* pa : allPreciseAllocations) {
    pa->isNew |= pa->isMarked;
    pa->isMarked = false;
}

for (BlockFooter* block : allCompleteSubspaceBlocks) {
    for (size_t cellId = 0; cellId < block->numCells; cellId++) {
        block->isNew[cellId] |= block->isMarked[cellId];
        block->isMarked[cellId] = false;
    }
}

新生代/全量 GC 回收阶段

// Update 'isNew = false' for CompleteSubspace cells
for (BlockFooter* block : allCompleteSubspaceBlocks) {
    for (size_t cellId = 0; cellId < block->numCells; cellId++) {
        block->isNew[cellId] = false;
    }
}

// For PreciseAllocation, in addition to updating 'isNew = false',
// we also need to free the dead objects
for (PreciseAllocation* pa : allPreciseAllocations) {
    pa->isNew = false;
    if (!pa->isMarked)
        free(pa);
}

在 CompleteSubspace 分配器中，检查块中的单元是否包含存活对象（如果没有，则该单元可用于分配）：

bool cellContainsLiveObject(BlockFooter* block, size_t cellId) {
    return block->isMarked[cellId] || block->isNew[cellId];
}

逻辑版本控制：无需清扫！

我们在全量 GC 周期开始和任何 GC 周期结束时都做了大量工作，因为我们必须遍历 CompleteSubspace 中的所有块并更新它们的 isMarked 和 isNew 位。尽管一个块中的位被聚合成位向量，从而具有良好的内存局部性，但这仍然可能是一个昂贵的操作，尤其是在我们有了并发 GC 之后（因为这个阶段无法并发进行）。所以我们想要更好的方法。

JSC 采用的优化是逻辑版本控制。我们不再在每个 GC 周期中物理上清除所有块中的所有位，而是只提升一个全局“逻辑版本”，表明所有位在逻辑上已被清除（或更新）。只有当我们在标记阶段实际需要标记块中的一个单元时，我们才会物理上清除（或更新）该块中的位向量。

您可能会问：既然未来无论如何都必须物理更新位向量，那为何还要费心使用逻辑版本控制呢？这里有两个充分的理由：

  1. 如果一个块中的所有单元都已死亡（无论是在此 GC 周期中消亡[19]，还是在此 GC 周期之前就已经死亡），那么我们将永远不会标记该块中的任何东西，因此逻辑版本控制使我们能够完全避免这项工作。这还意味着，在每个 GC 周期结束时，没有必要找出哪些块变得完全空，因为逻辑版本控制确保这些空块不会给未来的 GC 周期带来开销。

  2. 标记阶段可以由多个线程并发完成，并且可以在变异器线程运行的同时进行（我们的方案目前还不是并发的，但很快就会实现），而准备/回收阶段则必须在变异器停止时执行。因此，将工作转移到标记阶段可以减少并发环境中的 GC 延迟。

存在两个全局版本号：g_markVersion 和 g_newVersion[20]。每个块页脚也存储其本地版本号 l_markVersion 和 l_newVersion。

让我们从简单的情况开始：isNew 位的逻辑版本控制。

如果您回顾上面的伪代码，在 GC 中只有一个地方我们写入 isNew：在每个 GC 周期结束时，我们将所有 isNew 位设置为 false。因此，我们只需在那里递增 g_newVersion。本地版本 l_newVersion 小于 g_newVersion 意味着该块中所有 isNew 位已被逻辑上清除为 false。

当 CompleteSubspace 分配器分配新对象时，它需要以 isNew = true 开始。显然可以直接这样做，但 JSC 采用了一种更巧妙的方式，涉及一个名为 allocated 的块级位，以实现略微更好的性能。这不太有趣，所以我将其推迟到文章末尾，我们现在这里描述的方案将不采用此优化（但除此之外，在语义上与 JSC 故意保持等价）。

  1. 当 BlockDirectory 开始从一个新块分配时，它将该块的 l_newVersion 更新为 g_newVersion，并将所有已分配单元的 isNew 设置为 true（因为该块可能不完全为空），将所有空闲单元的 isNew 设置为 false。

  2. 每当它分配一个单元时，它将其 isNew 设置为 true。

为什么我们要费心将块中所有已分配单元的 isNew 设置为 true 呢？这是为了提供一个良好的特性。由于我们在每个 GC 周期结束时递增 g_newVersion，根据上述方案，对于任何具有最新 l_newVersion 的块，一个单元是存活的，当且仅当其 isNew 位被设置。现在，在检查一个单元是否存活时，如果其 l_newVersion 是最新的，那么我们就可以直接返回 isNew 而无需查看 isMarked，从而使我们的逻辑更简单。

isMarked 位的逻辑版本控制类似。在全量 GC 周期开始时，我们递增 g_markVersion，以表明所有标记位在逻辑上已被清除。请注意，新生代 GC 不会递增全局版本，因为它不清除 isMark 位。

这里有一个额外的复杂性：上述方案在增量 GC 中会失效。具体来说，在全量 GC 周期中，我们已经逻辑上清除了 isMarked 位，但我们没有对 isNew 位做任何处理，所以老生代中的所有单元对分配器来说都显得已死。在我们没有逻辑版本控制的旧方案中，这种情况通过在全量 GC 开始时执行 isNew |= isMarked 来防止，但现在有了逻辑版本控制，我们无法这样做。

JSC 通过以下巧妙的技巧解决了这个问题：在全量 GC 期间，我们也应该接受 l_markVersion 差一的情况。在这种情况下，我们知道 isMarked 位准确反映了一个单元是否存活，因为那是上一个 GC 周期的结果。如果您有点困惑，请查看脚注[21]以获取更详细的案例讨论。查看下面伪代码中的注释可能也会有所帮助。

bool cellContainsLiveObject(BlockFooter* block, size_t cellId) {
    if (block->l_newVersion == g_newVersion) {
        // A latest l_newVersion indicates that the cell is live if
        // and only if its 'isNew' bit is set, so we don't need to
        // look at the 'isMarked' bit even if 'isNew' is false
        return block->isNew[cellId];
    }

    // Now we know isNew bit is logically false, so we should
    // look at the isMarked bit to determine if the object is live
    if (isMarkBitLogicallyCleared(block)) {
        // The isMarked bit is logically false
        return false;
    }

    // The isMarked bit is valid and accurately tells us if
    // the object is live or not
    return block->isMarked[cellId];
}


// Return true if the isMarked bitvector is logically cleared
bool isMarkBitLogicallyCleared(BlockFooter* block) {
    if (block->l_markVersion == g_markVersion) {
        // The mark version is up-to-date, so not cleared
        return false;
    }

    if (IsFullGcRunning() && IsGcInMarkingPhase() &&
        block->l_markVersion == g_markVersion - 1) {
        // We are halfway inside a full GC cycle's marking phase,
        // and the mark version is off-by-one, so the old isMarked bit
        // should be accepted, and it accurately tells us if the
        // object is live or not
        return false;
    }

    return true;
}

在 CompleteSubspace 中标记一个对象之前，我们需要将包含该单元的块的 l_markVersion 更新到最新，并物化该块中所有单元的 isMarked 位。也就是说，我们需要运行我们旧方案中全量 GC 准备阶段的逻辑：对该块中所有单元执行 isNew |= isMarked, isMarked = false。这如下所示。

// Used by GC marking phase to mark an object in CompleteSubspace
void markObject(BlockFooter* block, size_t cellId) {
    aboutToMark(block);
    block->isMarked[cellId] = true;
}


// Materialize 'isMarked' bits if needed
// To do this, we need to execute the operation at full GC
// prepare phase: isNew |= isMarked, isMarked = false
void aboutToMark(BlockFooter* block) {
    if (block->l_markVersion == g_markVersion) {
        // Our mark version is already up-to-date,
        // which means it has been materialized before
        return;
    }

    // Check if the isMarked bit is logically cleared to false.
    // The function is defined in the previous snippet.
    if (isMarkBitLogicallyCleared(block)) {
        // This means that the isMarked bitvector should
        // be treated as all false. So operation isNew |= isMarked
        // is no-op, so all we need to do is isMarked = false
        for (size_t cellId = 0; cellId < block->numCells; cellId++) {
            block->isMarked[cellId] = false;
        }
    } else {
        // The 'isMarked' bit is not logically cleared. Now let's
        // check if the 'isNew' bit is logically cleared.
        if (block->l_newVersion < g_newVersion) {
            // The isNew bitvector is logically cleared and should be
            // treated as false. So operation isNew |= isMarked becomes
            // isNew = isMarked (note that executing |= is incorrect
            // beacuse isNew could physically contain true!)
            for (size_t cellId = 0; cellId < block->numCells; cellId++) {
                block->isNew[cellId] = block->isMarked[cellId];
                block->isMarked[cellId] = false;
            }

            // We materialized isNew, so update it to latest version
            block->l_newVersion = g_newVersion;
        } else {
            // The l_newVersion is latest, which means that the cell is
            // live if and only if its isNew bit is set.
            // Since isNew already reflects liveness, we do not have to
            // perform the operation isNew |= isMarked (and in fact, it
            // must be a no-op since no dead cell can have isMarked =
            // true). So we only need to do isMarked = false
            for (size_t cellId = 0; cellId < block->numCells; cellId++) {
                block->isMarked[cellId] = false;
            }
        }
    }

    // We finished materializing isMarked, so update the version
    block->l_markVersion = g_markVersion;
}

一个有趣的事实是：尽管我们概念上想在上面执行 isNew |= isMarked，但上述代码根本没有执行 |= 操作 🙂

此外，让我们更新准备 GC 逻辑的伪代码。

新生代 GC 准备阶段：无需工作。

全量 GC 准备阶段

// For PreciseAllocation, we still need to manually do
// 'isNew |= isMarked, isMarked = false' for every allocation
for (PreciseAllocation* pa : allPreciseAllocations) {
    pa->isNew |= pa->isMarked;
    pa->isMarked = false;
}

// For CompleteSubspace, all we need to do is bump the
// global version for the 'isMarked' bit
g_markVersion++;

新生代/全量 GC 回收阶段

// For PreciseAllocation, we still need to manually
// update 'isNew = false' for each allocation, and also
// free the object if it is dead
for (PreciseAllocation* pa : allPreciseAllocations) {
    pa->isNew = false;
    if (!pa->isMarked)
        free(pa);
}

// For CompleteSubspace, all we need to do is bump the
// global version for the 'isNew' bit
g_newVersion++;

通过逻辑版本控制，GC 不再清扫 CompleteSubspace 块以回收死对象：回收是惰性发生的，即当分配器开始从该块分配时。然而，这引入了一个不希望的副作用。一些对象内部使用手动内存管理：它们拥有不受 GC 管理的额外内存，并在对象死亡时通过 C++ 析构函数释放该内存。这通过减少 GC 的工作量来提高性能。但是，现在我们可能不会立即清扫死对象并运行析构函数，因此如果块从未被分配，本应由析构函数释放的内存可能会无限期地保留。为了缓解这个问题，JSC 还会定期清扫块并运行死对象的析构函数。这由 IncrementalSweeper 实现，但我们不会深入细节。

总而言之，逻辑版本控制为 GC 方案提供了两个重要的优化：

  1. 对于 CompleteSubspace 对象，GC 的所谓“清扫”阶段（用于查找和回收死对象）被移除了。回收是惰性完成的。这显然比在每个 GC 周期中反复清扫块要好。
  2. 全量 GC 不需要在准备阶段重置所有 isMarked 位，而只在标记阶段通过 aboutToMark 惰性重置它们：这不仅减少了工作量，而且在我们将 GC 方案并发化后，还允许在变异器运行时并行和并发地完成这项工作。

优化 WriteBarrier：cellState 位

正如我们之前解释的，每当变异器修改已标记对象 o 的指针以指向未标记对象时，它需要将 o 添加到“记忆集”中，这被称为 WriteBarrier。在本节中，我们将更深入地探讨 WriteBarrier 并解释其周围的优化。

我们当前 WriteBarrier 的第一个问题是 isMarked 位位于块页脚，因此从对象指针检索其值需要相当多的计算。此外，它也不与对象位于同一个 CPU 缓存行中，这使得访问速度更慢。这是不理想的，因为无论是否将对象添加到记忆集，每次 WriteBarrier 都需要支付此成本。

第二个问题是我们的 WriteBarrier 每次运行时都会反复将同一个对象 o 添加到记忆集中。显而易见的解决方案是使 rememberedSet 成为一个哈希集以对其包含的对象进行去重，但执行哈希查找以检查对象是否已存在则过于昂贵。

这就是我们尚未解释的最后一个元数据位：cellState 位的用武之地，它解决了这两个问题。

我们没有将 rememberedSet 做成哈希表，而是在每个对象的对象头中保留一个字节（尽管我们只使用其中 1 位）名为 cellState，用于指示是否可能需要在 WriteBarrier 中将对象放入记忆集。由于此位作为对象字段位于对象头中（而不是块页脚中），因此拥有对象指针的变异器可以轻易访问它。

cellState 有两个可能的值：black（黑色）和 white（白色）。围绕 cellState 最重要的两个不变量如下：

  1. 对于任何 cellState = white 的对象，保证无需将其添加到记忆集。
  2. 除非在全量 GC 周期期间，所有 black（存活）对象都具有 isMarked = true。

不变量 1 作为快速路径：如果我们的对象是 white，WriteBarrier 可以立即返回，并且检查它只需要一条加载指令（加载 cellState）和一条比较指令来验证它是 white。

然而，如果对象是 black，则需要一个慢速路径来检查是否确实需要将该对象添加到记忆集。

让我们看看新的 WriteBarrier：

// Executed after writing a pointer to 'dst' into a field of 'obj'
void WriteBarrier(JSCell* obj) {
    if (obj->cellState == black)
        WriteBarrierSlowPath(obj);
}

首先要注意的是，WriteBarrier 不再检查 dst（指针指向的对象）是否已标记。显然这不影响正确性：我们只是降低了标准。然而，移除此 dst 检查的性能影响是一个棘手的问题，即使对 JSC 开发人员来说也没有明确答案。通过一些初步测试，他们的结论是重新添加 !isMarked(dst) 检查会略微降低性能。他们有两个假设。首先，不检查 dst 会导致更多对象被放入记忆集并需要由 GC 扫描，因此总工作量增加了。然而，变异器的工作量可能减少了，因为它执行的检查更少，触及的缓存行也更少（因为不触及外联的 isMarked 位）。当然，这种好处会被抵消，因为变异器将更多对象添加到记忆集中，但这也不太昂贵，因为记忆集只是一个分段向量。GC 必须做更多的工作，因为它需要扫描和标记更多对象。然而，在我们使方案并发后，GC 的标记阶段可以在变异器运行时并发进行，因此延迟可能[22]被隐藏了。其次，JSC 的 DFG 编译器有一个优化pass，它会将同一对象上的屏障合并在一起，而对于这种屏障来说，检查所有 dst 则更加困难。

有趣的部分在于上述不变量是如何由相关方维护的。一如既往，有三个参与者：变异器（WriteBarrier）、分配器和 GC。

与分配器的交互是最简单的。所有对象诞生时都是 white。这是正确的，因为新生的对象未被标记，所以没有理由被记住。

与 GC 的交互发生在 GC 标记阶段：

  1. 当我们标记一个对象并将其推入队列时，我们将其 cellState 设置为 white。
  2. 当我们从队列中弹出一个对象时，在开始扫描其子对象之前，我们将其 cellState 设置为 black。

在伪代码中，新生代/全量 GC 标记阶段现在看起来如下所示（第 5 行和第 9 行是新添加的用于处理 cellState 的逻辑，其他行未变）：

while (!queue.empty() || !rmbSet.empty()) {
    // Both eden GC and full GC needs to consider remembered set
    // Prioritize popping from queue, pop remembered set last
    JSCell* obj = !queue.empty() ? queue.pop() : rmbSet.pop();
    obj->cellState = black;           // <----------------- newly added

    obj->ForEachChild([&](JSCell* child) {
        if (!child->isMarked) {
            markObject(child);
            child->cellState = white; // <----------------- newly added
            queue.push(child);
        }
    });
}

让我们论证为什么上述代码维护了不变量。

  1. 对于不变量 1，请注意在上述代码中，一个对象只有在队列中时才是 white（因为一旦它被弹出，它就会再次变为 black），等待扫描其子对象。因此，保证该对象稍后仍会被 GC 扫描，所以我们无需将该对象添加到记忆集，正如所期望的。
  2. 对于不变量 2，在任何 GC 周期结束时，任何存活对象都已被标记，这意味着它已被扫描，所以它是 black，正如所期望的。

现在让我们看看 WriteBarrierSlowPath 应该做什么。显然，如果它只是无条件地将对象添加到记忆集中，那是正确的，但这也会挫败 cellState 作为优化机制的大部分目的：我们想要更好的东西。cellState 的一个关键用例是防止在对象已在记忆集中时再次将其添加进去。因此，在我们将对象放入记忆集后，我们会将其 cellState 设置为 white，如下所示。

void WriteBarrierSlowPath(JSCell* obj) { 
    obj->cellState = white;
    addToRememberedSet(obj);
}

让我们证明上述代码为何有效。一旦我们将一个对象添加到记忆集，我们将其设置为 white。我们不需要再次将同一个对象添加到记忆集，直到它被 GC 从集合中弹出。但当 GC 弹出该对象时，它会将其 cellState 设置回 black，所以我们没问题。

JSC 采用了又一项优化。在全量 GC 期间，我们可能会看到一个 black 对象，其 isMarked = false（请注意，由于不变量 2，这是对象未标记的唯一可能情况）。在这种情况下，没有必要将对象添加到记忆集，因为该对象最终会在未来被扫描（或者在被扫描之前某个时候它已经死亡，在这种情况下我们也安然无恙）。此外，我们可以将其翻转回 white，这样下次在该对象上运行 WriteBarrier 时，我们就不必进入这个慢速路径。综上所述，优化后的版本如下：

void WriteBarrierSlowPath(JSCell* obj) {
    if (IsFullGcRunning()) {
        if (!isMarked(obj)) {
            // Do not add the object to remembered set
            // In addition, set cellState to white so this
            // slow path is not triggered on the next run
            obj->cellState = white;
            return;
        }
    } else {
        assert(isMarked(obj)); // due to invariant 2
    }

    obj->cellState = white;
    addToRememberedSet(obj);
}

实现并发并变得更加“狂野”

至此，我们已经拥有了一个非常好的增量式和分代式垃圾回收器：变异器、分配器和 GC 都针对常见情况拥有各自的快速路径，并且通过逻辑版本控制，我们尽可能地避免了冗余工作。在我看来，这是性能与工程复杂性之间的一个良好平衡点。

然而，由于 JSC 是 Safari 性能的核心驱动力之一，将性能置于首位，即使以工程复杂性为代价，也毫不奇怪。为了压榨出每一丝性能，JSC 使其 GC 并发化。这绝非易事：由于 GC 的性质，使用锁来防范某些竞态条件往往太慢，因此大量采用了无锁编程。

但一旦涉及到无锁编程，就会开始出现各种依赖于体系结构的内存重排序问题。x86-64 是更严格的体系结构：它只需要 StoreLoadFence()，并提供类似 TSO 的语义。JSC 还支持 ARM64 CPU，后者提供的保证更少：加载-加载、加载-存储、存储-加载和存储-存储都可能被 CPU 重排序，因此需要更多的操作屏障。更糟的是，出于性能原因，JSC 经常避免在 ARM64 上使用内存屏障。他们有所谓的 Dependency 类，通过一些令人胆战心惊的汇编技巧在 ARM64 上创建隐式的 CPU 数据依赖，这样他们就可以在不支付内存屏障成本的情况下获得特定数据流所需的内存顺序。可以想象，有了所有这些复杂性和优化，代码变得难以阅读。

因此，由于我有限的专业知识，如果我在本文中遗漏解释或错误解释了一些重要的竞态条件，特别是某些 ARM64 特有的条件，请不要感到惊讶：如果您发现本文有任何问题，请告诉我。

让我们首先了解并发假设。JavaScript 是一种单线程语言，因此总是只有一个变异器线程[23]。除了变异器线程，JSC 还有一组编译线程、一个 GC 线程和一组标记线程。只有 GC 标记阶段是并发的：在此期间，变异器线程、编译线程和一组标记线程并发运行（是的，标记本身也是并行完成的）。然而，所有其他 GC 阶段都在变异器线程和编译线程停止的情况下运行。

一些不那么有趣的问题

首先，isMarked 和 isNew 位向量必须确保并发访问安全，因为多个线程（包括标记线程和变异器）可能会并发更新它。使用带有适当重试/退出机制的 CAS 对于位向量本身就足够了。

BlockFooter 更难处理，需要用锁保护：多个线程可能同时调用 aboutToMark()，因此 aboutToMark() 必须受到保护。对于读取方（isMarked() 函数，它首先检查 l_markVersion 是否最新，然后读取 isMarked 位向量），在 x86-64 上，由于 x86-TSO，不需要锁或任何内存屏障（只要 aboutToMark 注意在位向量之后更新 l_markVersion）。在 ARM64 上，由于允许加载-加载重排序，因此需要 Dependency。

使 cellContainsLiveObject（或 JSC 行话中的 isLive）检查无锁化更难，因为它可能涉及同时读取 isMarked 位和 isNew 位。JSC 采用了乐观锁来提供快速路径。这与您在教科书中能找到的乐观锁方案没有太大区别，所以我不会深入细节。

当然，还有更多微妙的问题需要改变。上面几乎所有的伪代码都需要适应并发，要么通过使用锁或 CAS，要么通过使用某种内存屏障和并发协议来确保代码在竞态条件下正确工作。但现在让我们转向一些更重要和棘手的问题。

WriteBarrier 与标记之间的竞态

最重要的竞态之一是 WriteBarrier 与 GC 标记线程之间的竞态。标记线程和变异器线程可以并发访问对象的 cellState。出于性能原因，使用锁是不可行的，因此出现了竞态条件。

值得注意的是，我们是在将指针写入对象之后才调用 WriteBarrier 的。这不仅使用起来更方便（特别是对于 JIT 生成的代码），而且还允许一些优化：例如，在某些情况下，对同一对象的多次写入可能只在最后调用一次 WriteBarrier。

考虑到这一点，让我们分析一下为什么我们当前的实现存在缺陷。假设 o 是一个对象，变异器想将指向另一个对象 target 的指针存储到 o 的字段 f 中。GC 的标记逻辑想要扫描 o 并将其子对象添加到队列中。我们需要确保 GC 将观察到 o->target 指针链接。

让我们首先看看正确的逻辑：

变异器 (WriteBarrier) GC (标记器)
存储(o.f, target)
StoreLoadFence() // WriteBarrier 开始
t1 = 加载(o.cellState)
if (t1 == black): WriteBarrierSlowPath(o)
 存储(o.cellState, black)
StoreLoadFence()
t2 = 加载(o.f) // 加载 o 的子对象
对 t2 进行一些检查并将其推入队列

这基本上只是上面章节中伪代码的副本，除了我们有两个 StoreLoadFence()。一个 StoreLoadFence() 保证在屏障之后没有 LOAD 可以被 CPU 乱序执行引擎执行，直到屏障之前所有的 STORE 都完成。让我们首先分析一下没有任何一个屏障可能出现的问题。

为了完全清楚，前置条件是 o.cellState = white（因为 o 在 GC 队列中）且 o.f = someOldValue。

如果变异器 WriteBarrier 没有屏障，可能会出现什么问题？没有屏障，CPU 可以在第 1 行的 STORE 之前执行第 3 行的 LOAD。然后，在以下交错执行中：

  1. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = white
  2. [GC 第 1 行] 存储(o.cellState, black)
  3. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = 某个旧值
  4. [变异器 第 1 行] 存储(o.f, target)

现在，变异器没有将 o 添加到记忆集（因为 t1 是 white，而不是 black），GC 中的 t2 是 o.f 中的旧值而不是 target，因此 GC 没有将 target 推入队列。所以从 o 到 target 的指针链接在 GC 中被遗漏了。这可能导致 target 尽管是存活的，但被错误地回收。

那么如果 GC 标记逻辑没有屏障，可能会出现什么问题？类似地，没有屏障，CPU 可以在第 1 行的 STORE 之前执行第 3 行的 LOAD。然后，在以下交错执行中：

  1. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = 某个旧值
  2. [变异器 第 1 行] 存储(o.f, target)
  3. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = white
  4. [GC 第 1 行] 存储(o.cellState, black)

与上面类似，变异器看到 t1 = white，GC 看到 t2 = oldValue。因此 o 未被添加到记忆集，target 未被推入队列，指针链接被遗漏。

最后，让我们分析一下如果两个屏障都存在，代码为何能正确运行。不幸的是，除了手动枚举所有交错执行之外，没有更好的方法。由于屏障的存在，变异器 第 1 行必须在 变异器 第 3 行之前执行，GC 第 1 行必须在 GC 第 3 行之前执行，但其余四行可以任意重排序。因此，有 4! / 2! / 2! = 6 种可能的交错执行。那么，开始吧！

交错执行 1

  1. [变异器 第 1 行] 存储(o.f, target)
  2. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = white
  3. [GC 第 1 行] 存储(o.cellState, black)
  4. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = target

在这种交错执行中，变异器没有将 o 添加到记忆集，但 GC 看到了 target，所以没问题。

交错执行 2

  1. [GC 第 1 行] 存储(o.cellState, black)
  2. [GC 第 3 行] t2 = 加载(o.f)                // t2 = 某个旧值
  3. [变异器 第 1 行] 存储(o.f, target)
  4. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = black

在这种交错执行中，GC 看到了旧值，但变异器将 o 添加到了记忆集，因此 GC 最终会从记忆集中耗尽并再次扫描 o，届时它将看到正确的新值 target，所以没问题。

交错执行 3

  1. [变异器 第 1 行] 存储(o.f, target)
  2. [GC 第 1 行] 存储(o.cellState, black)
  3. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = black
  4. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = target

在这种交错执行中，GC 看到了新值 target，尽管如此，变异器看到了 t1 = black 并将 o 添加到了记忆集。这很不幸，因为 GC 将再次扫描 o，但它不影响正确性。

交错执行 4

  1. [变异器 第 1 行] 存储(o.f, target)
  2. [GC 第 1 行] 存储(o.cellState, black)
  3. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = target
  4. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = black

与交错执行 3 相同。

交错执行 5

  1. [GC 第 1 行] 存储(o.cellState, black)
  2. [变异器 第 1 行] 存储(o.f, target)
  3. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = black
  4. [GC 第 3 行] t2 = 加载(o.f)                // t2 = target

与交错执行 3 相同。

交错执行 6

  1. [GC 第 1 行] 存储(o.cellState, black)
  2. [变异器 第 1 行] 存储(o.f, target)
  3. [GC 第 3 行] t2 = 加载(o.f)                 // t2 = target
  4. [变异器 第 3 行] t1 = 加载(o.cellState)    // t1 = black

与交错执行 3 相同。

这证明了有了这两个 StoreLoadFence()，我们的代码不再容易受到上述竞态条件的影响。

WriteBarrier 与标记之间的另一个竞态条件

仅仅上述修复是不够的：WriteBarrier 和 GC 标记线程之间还存在另一个竞态。回想一下，在 WriteBarrierSlowPath 中，如果对象未被标记（这可能发生在全量 GC 期间），我们尝试将其翻转回 white，如下所示：

... omitted ...
if (!isMarked(obj)) {
    obj->cellState = white;
    return;
}
... omitted ...

结果表明，在将对象设置为 white 后，我们需要执行一个 StoreLoadFence()，并再次检查对象是否已被标记。如果它变为已标记，我们需要将 obj->cellState 设置回 black。

如果没有这个修复，代码容易受到以下竞态的影响：

  1. [前置条件] o.cellState = black 且 o.isMarked = false
  2. [WriteBarrier] 检查 isMarked()                 // 看到 false
  3. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  4. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  5. [WriteBarrier] 存储(o.cellState, white)
  6. [后置条件] o.cellState = white 且 o.isMarked = true

这个后置条件是糟糕的，因为 o 未来不会被添加到记忆集，尽管它需要被添加（因为 GC 已经扫描过它了）。

现在，让我们证明当应用了修复后，代码为何是正确的。现在 WriteBarrier 的逻辑看起来像这样：

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [WriteBarrier] t1 = isMarked()
  3. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)

请注意，我们省略了第一行“Check isMarked()”，因为它必须是交错执行中第一个被执行的，否则 if 检查将根本不会通过。

WriteBarrier 中的三行不能被 CPU 重排序：第 1-2 行不能重排序，因为有 StoreLoadFence()；第 2-3 行不能重排序，因为第 3 行是一个只有在第 2 行为真时才执行的存储操作。GC 中的两行不能被 CPU 重排序，因为第 2 行存储到与第 1 行相同的字段 o.cellState。

此外，请注意，如果在 WriteBarrier 结束时，对象是 black 但 GC 只执行到第 1 行，这也没关系：这很不幸，因为此对象上的下一次 WriteBarrier 将把对象添加到记忆集，尽管这是不必要的。然而，它不影响我们的正确性。所以现在，让我们再次枚举所有交错执行！

交错执行 1。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [WriteBarrier] t1 = isMarked() // t1 = false
  3. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 未执行

对象未标记且为白色，正常。

交错执行 2。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [WriteBarrier] t1 = isMarked() // t1 = false
  3. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  4. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 未执行

对象在队列中且为白色，正常。

交错执行 3。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  3. [WriteBarrier] t1 = isMarked() // t1 = true
  4. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

对象在队列中且为黑色，不幸但正常。

交错执行 4。

  1. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  2. [WriteBarrier] 存储(o.cellState, white)
  3. [WriteBarrier] t1 = isMarked() // t1 = true
  4. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

对象在队列中且为黑色，不幸但正常。

交错执行 5。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [WriteBarrier] t1 = isMarked() // t1 = false
  3. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  4. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 未执行

交错执行 6。

对象已标记且为黑色，正常。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  3. [WriteBarrier] t1 = isMarked() // t1 = true
  4. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

交错执行 6。

交错执行 7。

  1. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  2. [WriteBarrier] 存储(o.cellState, white)
  3. [WriteBarrier] t1 = isMarked() // t1 = true
  4. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

交错执行 6。

交错执行 8。

  1. [WriteBarrier] 存储(o.cellState, white)
  2. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  3. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  4. [WriteBarrier] t1 = isMarked() // t1 = true
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

交错执行 6。

交错执行 9。

  1. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  2. [WriteBarrier] 存储(o.cellState, white)
  3. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  4. [WriteBarrier] t1 = isMarked() // t1 = true
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

交错执行 6。

交错执行 10。

  1. [GC 标记] CAS(o.isMarked, true), 存储(o.cellState, white), 将 'o' 推入队列
  2. [GC 标记] 从队列中弹出 'o', 存储(o.cellState, black)
  3. [WriteBarrier] 存储(o.cellState, white)
  4. [WriteBarrier] t1 = isMarked() // t1 = true
  5. [WriteBarrier] if (t1 == true): 存储(o.cellState, black)   // 已执行

交错执行 6。

所以让我们更新伪代码。然而，我想指出的是，在 JSC 的实现中，他们没有在 obj->cellState = white 之后使用 StoreLoadFence()。相反，他们将 obj->cellState = white 变成了一个从 black 到 white 的 CAS（内存顺序为 memory_order_seq_cst）。这比 StoreLoadFence() 更强，所以他们的逻辑也是正确的。尽管如此，以防我的分析遗漏了与其他组件的一些其他竞态，我们的伪代码将坚持他们的逻辑……

变异器 WriteBarrier 伪代码

void WriteBarrier(JSCell* obj) {
    StoreLoadFence(); // Note the fence!
    if (obj->cellState == black)
        WriteBarrierSlowPath(obj);
}

void WriteBarrierSlowPath(JSCell* obj) {
    if (IsGcRunning()) {
        if (!isMarked(obj)) {
            if (SUCCESS == 
                CompareAndSwap(obj->cellState, black /*from*/, white /*to*/)) {
                if (isMarked(obj)) {
                    obj->cellState = black;
                }
            }
            return;
        }
    } else {
        assert(isMarked(obj));
    }

    obj->cellState = white;
    // Add 'obj' to remembered set
    rmbSet.push(obj);
}

新生代/全量 GC 标记阶段

while (!queue.empty() || !rmbSet.empty()) {
    JSCell* obj = !queue.empty() ? queue.pop() : rmbSet.pop();
    obj->cellState = black;

    StoreLoadFence(); // Note the fence!

    obj->ForEachChild([&](JSCell* child) {
        if (!child->isMarked) {
            markObject(child);
            child->cellState = white;
            queue.push(child);
        }
    });
}

移除 WriteBarrier 中不必要的内存屏障

现在，WriteBarrier 不再有危险的竞态条件。然而，我们每次执行 WriteBarrier 都会执行一个 StoreLoadFence()，这是一个非常昂贵的 CPU 指令。我们能优化它吗？

想法如下：屏障用于防范与 GC 的竞态。因此，如果 GC 正在并发运行，我们肯定需要屏障。然而，如果 GC 没有运行，屏障就是不必要的。因此，我们可以先检查 GC 是否正在运行，只有当 GC 确实在运行时才执行屏障。

JSC 更为巧妙：它没有进行两次检查（一次检查 GC 是否正在运行，另一次检查 cellState 是否为 black），而是将它们合并为一个单一检查，用于 GC 未运行且对象为 white 的快速路径。技巧如下：

  1. 假设 cellState 枚举中 black = 0 且 white = 1。
  2. 创建一个名为 blackThreshold 的全局变量。这个 blackThreshold 通常是 0，但在 GC 周期开始时，它将被设置为 1，并在 GC 周期结束时重置回 0。
  3. 现在，检查 obj->cellState > blackThreshold。

然后，如果检查成功，我们知道可以立即返回：此检查唯一能成功的情况是当 GC 未运行且我们是 white（因为 blackThreshold = 0 且 cellState = 1 是通过检查的唯一情况）。这样，快速路径只执行一次检查。如果检查失败，那么我们回退到慢速路径，执行完整的程序：检查 GC 是否正在运行，如果需要则执行屏障，然后再次检查 cellState 是否为 black。伪代码如下：

void WriteBarrier(JSCell* obj) {
    if (obj->cellState > g_blackThreshold) {
        // Fast-path: the only way to reach here is when
        // the GC is not running and the cellState is white
        return;
    }

    if (!IsGcRunning()) {
        // g_blackThreshold is 0, so our object is
        // actually black, we need to go to WriteBarrierSlowPath
        WriteBarrierSlowPath(obj);
    } else {
        // GC is running so we need to execute the fence
        // and check cellState again
        StoreLoadFence();
        if (obj->cellState == black) {
            WriteBarrierSlowPath(obj);
        }
    }
}

请注意，在 WriteBarrier 与 GC 设置/清除 IsGcRunning() 标志以及改变 g_blackThreshold 值之间没有竞态，因为当 GC 启动/完成时，变异器总是在一个安全点停止（当然，在 WriteBarrier 内部进行到一半不是一个安全点）。

“无阻塞双重收集快照”

并发 GC 还为 GC 标记阶段使用的 ForEachChild 函数引入了新的复杂性，该函数用于扫描特定对象引用的所有对象。每个 JavaScript 对象都有一个 Structure（即，隐藏类），它描述了如何将此对象的内容解释为对象字段。由于 GC 标记阶段与变异器并发运行，并且变异器可能会改变对象的 Structure，甚至可能改变对象 butterfly 的大小，GC 必须确保，尽管存在竞态条件，它永远不会因解引用无效指针而崩溃，也永远不会遗漏扫描子对象。出于性能原因，使用锁显然是不可行的。JSC 使用了所谓的无阻塞双重收集快照来解决这个问题。请参阅 Filip Pizlo 的 GC 博客文章以了解其工作原理。

一些次要的设计细节和优化

如果您想实际阅读并理解 JSC 的代码，本节可能会对您有所帮助，否则请随意跳过：这些细节并非设计的核心，也不特别有趣。我提及它们只是为了弥合本文解释的 GC 方案与 JSC 实际实现之间的差距。

如前所述，每个 CompleteSubspace 拥有一系列 BlockDirectory 来处理不同大小的分配；每个 BlockDirectory 都有一个活动块 m_currentBlock，它从中分配内存，并通过维护该块中所有可用单元的空闲列表来实现这一点。但它具体是如何工作的呢？

结果表明，每个 BlockDirectory 都有一个 cursor（游标），它在新生代或全量 GC 周期结束时被重置以指向块列表的开头。在它被重置之前，它只能向前移动。BlockDirectory 将向前移动游标，直到找到一个包含可用单元的块，并从中分配。如果游标到达列表末尾，它将尝试从另一个 BlockDirectory 窃取一个 16KB 的块并从中分配。如果这也失败了，它将从 malloc 分配一个新的 16KB 块并从中分配。

我还提到，一个 BlockDirectory 使用空闲列表从当前活跃块 m_currentBlock 中进行分配。值得注意的是，在 JSC 的实际实现中，m_currentBlock 中的单元格不遵守 isNew 位的规则。因此，要检查存活度，要么需要进行特殊情况检查以查看单元格是否来自 m_currentBlock（例如，参见 HeapCell::isLive），要么，对于 GC[24]，停止变异器，销毁空闲列表（并在该过程中填充 isNew），进行任何所需的检查，然后重建空闲列表并恢复变异器。后者由 两 个函数 stopAllocating() 和 resumeAllocating() 实现，它们在世界被 停止 或 恢复 时自动调用。

允许 m_currentBlock 不遵守 isNew 规则的动机是（微小的）性能提升。不是为每次分配手动将 isNew 设置为 true，而是使用块级别的 allocated 位（在 BlockDirectory 中聚合为位向量）来指示块是否已满活对象。当 空闲列表变空（即，块已完全分配）时，我们只需将该块的 allocated 设置为 true。在查询单元格存活度时，我们 首先检查此位，如果它已设置，则直接返回 true。allocated 位向量在 每个 GC 周期结束时被清除，并且由于 isNew 的全局逻辑版本也已提升，这有效地清除了所有 isNew 位，正如我们所期望的那样。

JSC 的设计还支持所谓的*约束求解器*，它允许指定隐式引用边（即，未在对象中表示为指针的边）。这主要用于支持 JavaScript 与 DOM 的交互。本文不涵盖此部分。

JSC 中有多种弱引用实现。通用（但效率较低）的实现是 WeakImpl，它表示一个弱引用边。管理它们的数据结构是 WeakSet，你可以在 每个块的页脚 和 每个 PreciseAllocation GC 头 中看到它。然而，JSC 还采用了更高效的专用实现来处理 JavaScript 中的弱映射特性。本文不涵盖其细节。

在 JSC 中，对象也可能拥有析构函数。析构函数的运行有三种方式。首先，当我们开始从一个块中分配时，死单元格的析构函数会运行。其次，IncrementalSweeper 定期扫描块并运行析构函数。最后，当 VM 关闭时，会调用 lastChanceToFinalize() 函数，以确保所有析构函数都在那时运行。本文不涵盖 lastChanceToFinalize() 的细节。

JSC 对栈上和寄存器中的指针采用保守方法：GC 使用 UNIX 信号暂停变异器线程，以便它可以复制其栈内容和 CPU 寄存器值，以搜索看起来像指针的数据。然而，重要的是要注意，UNIX 信号**不**用于暂停变异器的执行：变异器总是在安全点**主动**暂停自身。这至关重要，否则它可能会在奇怪的地方被暂停，例如，在一个 HeapCell::isLive 检查中，在它读取 isNew 之后但在读取 isMarked 之前，然后 GC 执行了 isNew |= isMarked, isMarked = false，然后就出问题了。所以看起来暂停线程的唯一原因是 GC 获取 CPU 寄存器值，包括 SP 寄存器值，以便 GC 知道栈的末尾在哪里。我尚不清楚是否有可能以协作方式而不是使用开销大的 UNIX 信号来做到这一点。

致谢

我感谢 Apple JSC 团队的 Saam Barati 为这篇博客文章提供了巨大帮助。当然，本文中的任何错误都由我负责。

脚注

  1. 在每个 GC 周期开始和结束时仍然需要短暂的“停顿世界”暂停，如果变异器线程（即运行 JavaScript 代码的线程）产生垃圾的速度过快以至于 GC 线程无法跟上，则可能会有意地执行此暂停。 ↩︎
  2. 实际的分配逻辑在 LocalAllocator 中实现。尽管在代码中 BlockDirectory 持有一个 LocalAllocator 的链表，但（截至撰写本文时，对于此博客中链接的代码库版本）该链表总是只包含一个元素，因此 BlockDirectory 和 LocalAllocator 是一对一的，可以被视为一个集成组件。这种关系未来可能会改变，但无论如何，这对于本文的目的来说并不重要。 ↩︎
  3. 由于页脚位于 16KB 块的末尾，并且块也按 16KB 对齐，因此可以从任何对象指针进行简单的位运算来访问其所在块的页脚。 ↩︎
  4. 类似于每个单元格的信息被聚合并存储在块页脚中，每个块的信息被聚合成位向量并存储在 BlockDirectory 中以进行快速查找。具体来说，两个位向量 empty 和 canAllocateButNotEmpty 跟踪一个块是否为空或部分为空。此 代码 相对混乱，因为位向量以 非标准方式布局 以使大小调整更容易，但从概念上讲，它只是每个块级布尔属性对应一个位向量。 ↩︎
  5. 虽然看似简单，但实际上一点也不简单（如您在代码中看到的那样）。空闲单元格由 GC 标记为空闲，由于并发和性能优化，其逻辑变得非常复杂：我们稍后将重新讨论这一点。 ↩︎
  6. 实际上，它还 尝试从其他分配器中窃取 块，并且操作系统内存分配器可能对 VM 有 一些特殊要求，但为了简化，我们忽略了这些细节。 ↩︎
  7. 在当前实现中，大小（字节）列表为 16、32、48、64、80，然后对于 n >= 1 直到大约 8KB，为 80 * 1.4 ^ n。指数增长保证了由于内部碎片造成的开销最多是总分配大小的一小部分（在这种情况下为 40%）。 ↩︎
  8. 一个有趣的实现细节是，IsoSubspace 和 CompleteSubspace 总是返回 16 字节对齐的内存，而 PreciseAllocation 总是返回模 16 余 8 的内存地址。这允许通过简单的位运算来识别对象是否由 PreciseAllocation 分配。 ↩︎
  9. JSC 在这里还有另一个小的优化。有时一个 IsoSubspace 包含的对象非常少，以至于使用 16KB 内存页（BlockDirectory 的块大小）来保存它们是一种浪费。因此，IsoSubspace 的前几个内存页使用了所谓的“下层”（lower-tier），它们是由 PreciseAllocation 分配的较小内存页。在本文中，为了简化，我们将忽略这个设计细节。 ↩︎
  10. IsoSubspace 的内存仅由其自身使用，绝不会被其他分配器窃取。因此，IsoSubspace 中的内存地址只能重复用于分配相同类型的对象。因此，对于任何由 IsoSubspace 分配的类型 A，即使类型 A 存在释放后使用 (use-after-free) 错误，也无法分配 A、释放它、然后在同一地址分配类型 B，并利用该错误欺骗 VM 将攻击者控制的 B 中的整数字段解释为 A 中的指针字段。 ↩︎
  11. 在一些 GC 方案中，一个伊甸对象需要经过两次（而不是一次）伊甸 GC 才能被认为是老年代对象。这种设计的目的是确保任何老年代对象至少比一次伊甸 GC 的间隔更“老”。相比之下，在 JSC 的设计中，一个在伊甸集合（eden collection）之前立即创建的对象将立即被视为老年代对象，然后只能通过完整 GC 回收。这两种设计之间的性能差异对我来说不清楚。我推测 JSC 选择其当前设计是因为它更容易实现并发。 ↩︎
  12. 代码中还有一种额外的颜色 Grey。然而，事实证明 White 和 Grey 之间没有区别（您可以通过 grep 搜索所有 cellState 的使用来验证，并观察到对 cellState 的唯一比较是检查它是否为 Black）。解释这些颜色含义的注释并未完全捕捉所有不变量。在我看来，JSC 确实应该清理并更新这些注释，因为它很容易让试图理解设计的读者感到困惑。 ↩︎
  13. 该位在代码中实际称为 isNewlyAllocated。为了本文的方便，我们将其缩写为 isNew。 ↩︎
  14. 安全点是 GC 中的一个术语。在安全点，堆和栈处于 GC 可理解的连贯状态，因此 GC 可以正确地追踪哪些对象是死的或活的。 ↩︎
  15. 对于 PreciseAllocation，所有已分配对象都链接到一个链表中，因此我们可以轻松遍历所有对象（活的或死的）。这效率不高：我们稍后将解释 CompleteSubspace 的优化。 ↩︎
  16. 请记住，虽然这目前是正确的，但随着我们在设计中添加更多优化，这将不再是正确的。 ↩︎
  17. 请注意，我们将老年代对象推入队列，而不是伊甸对象，因为此指针可能在 GC 周期开始时已被覆盖，从而使伊甸对象可能变得可回收。 ↩︎
  18. 另请注意，在此 GC 周期之前已死亡的所有对象，即 CompleteSubspace 中块的空闲单元格，仍然是 isNew = false 和 isMarked = false，正如期望的那样。 ↩︎
  19. 回想一下，在分代假说下，大多数对象都“英年早逝”。因此，“伊甸块中的所有对象在伊甸 GC 期间都被发现已死亡”是完全合理的。 ↩︎
  20. 在 JSC 中，版本存储在 uint32_t 中，并且它们有一堆逻辑来处理 uint32_t 溢出的情况。在我看来，这是一种过度优化，导致了非常难以测试的边缘情况，尤其是在并发环境中。因此，我们将忽略这种复杂性：通过为每个块的页脚多花费 8 字节来使用 uint64_t 版本号，可以轻松避免这些问题。 ↩︎
  21. 请注意，在上次完整 GC 周期和当前完整 GC 周期之间可能运行了任意数量的伊甸 GC 周期，但伊甸 GC 不会提升标记版本。因此，对于在上次 GC 周期（无论是伊甸 GC 还是完整 GC）之前创建的任何对象，isMarked 位忠实地反映了它是否存活，我们将接受该位，因为其标记版本必须相差一。对于在上次 GC 周期之后创建的对象，它必须具有最新的 isNew 版本，因此我们可以通过 isNew 知道它是否存活。在这两种情况下，该方案都能正确判断对象是否存活，正如期望的那样。 ↩︎
  22. 可能不会：首先，GC 和变异器之间的真共享和伪共享会导致速度变慢。其次，正如我们之前讨论的，JSC 使用时空调度器 (Time-Space Scheduler) 来防止变异器在 GC 运行时分配过快。具体来说，变异器将被有意暂停至少 30% 的时间。因此，只要 GC 在运行，变异器就会遭受 30% 或更多的“性能税”惩罚。 ↩︎
  23. 真实情况有点复杂。JSC 实际上为不同的 JavaScript 脚本重用同一个 VM。然而，在任何时刻，最多只有一个脚本可以运行。所以从技术上讲，存在多个互斥的变异器线程，但这不影响我们的 GC 叙述。 ↩︎
  24. GC 需要检查大量单元格，并且其逻辑已经足够复杂，因此少一个特殊情况分支可能对工程和性能都有益。 ↩︎