深入解读 V8 引擎的「并发标记」技术

背景

标记是 V8 的 Mark-Compact 垃圾收集器的一个阶段。在这个阶段中，收集器发现并标记了所有的活动对象。标记从一组已知的活动对象开始，例如全局对象和当前活动函数——所谓的根。收集器将根标记为活动的，并跟随指针来发现更多的活动对象。收集器继续标记新发现的对象并跟随标记指针，直到没有需要标记的对象为止。在标记结束时，应用程序无法访问堆中未被标记的对象，并且可以安全的回收。

我们可以将标记认为是 图遍历 。堆上的对象是图的节点。从一个对象指向另一个对象是图的边。从图中给一个节点，我们可以使用对象 隐藏的类 找出该节点所有外出边。

减少标记暂停

一次执行标记可能需要几百毫秒才能完成一个大的堆。

这样长时间的停顿可能会导致应用程序无响应，并导致用户体验不佳。在2011年，V8 从 stop-the-world 标记切换到增量标记。在增量标记期间，垃圾收集器将标记工作分解为更小的块，并且允许应用程序在块之间运行：

垃圾收集器选择在每个块中执行多少增量标记来匹配应用程序的分配速率。一般情况下，这极大地提高了应用程序的相应速度。对内存压力较大的堆，收集器仍然可能出现长时间的暂停来维持分配。

增量标记不是没有代价的。应用程序必须通知垃圾收集器关于改变对象图的所有操作。V8 使用 Dijkstra 风格的 write-barrier 机制来实现通知。在 JavaScript 中，每次表单 object.field = value 的写操作之后，V8 会插入 write-barrier 代码。

// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

Write-barrier 机制强制不变黑的对象指向白色对象。这也被称为强三色不变性，保证应用程序不能在垃圾收集器中隐藏活动对象，因此标记结束时的所有白色对象对于应用程序来说都是不可达的，可以安全释放。

就像 早期博客 中描述的那样，增量标记很好的集成了空闲时间垃圾收集调度。Chrome 的 Blink 任务调度程序可以在主线程的空闲时间调度小的增量标记步骤，而不会造成混乱。如果空闲时间可用，该优化效果将会非常好。

并行标记

在并行标记的时候，我们可以假定应用都不会同时运行。这大大的简化了实现，是因为我们可以假定对象图是静态的，而且不会改变。为了并行标记对象图，我们需要让垃圾收集数据结构是线程安全的，而且寻找一个可以在线程间运行的高效共享标记的方法。下面的示意图展示了并行标记包含的数据结构。箭头代表数据流的方向。简单来说，示意图省略了堆碎片处理所需的数据结构。

注意，这些线程只能读取对象图，而不能修改它。对象的标记位和标记列表必须支持读写访问。

标记工作列表和工作窃取（work stealing）

标记工作列表的实现对性能至关重要，而且它通过在其他线程没有工作可做的情况下，有多少工作可以分配给他们，来平衡快速线程本地的性能。

要权衡的两个极端的情况是（a）使用完全并发数据结构，达成最佳共享即所有对象都可以隐式共享，和（b）使用完全线程本地数据结构，没有对象可以共享，优化线程本地吞吐量。图6展示了 V8 是如何通过使用一个基于线程本地插入和删除的段的标记工作列表来平衡这些需求的。一旦一个段满了，它会被发布到一个可以用来窃取的共享全局池。使用这种方法，V8 允许标记线程在不用任何同步的情况下尽可能长的执行本地操作，而且还处理了当单个线程达成了一个新的对象子图，而另一个线程在完全耗尽了本地段时饥饿的情况。

并发标记

并发标记允许 JavaScript 在主线程上运行，而工作线程正在访问堆上的对象。这为潜在的竞态数据打开大门。举个例子：当工作者线程正在读取字段时，JavaScript 可能正在写入对象字段。竞态数据会混淆垃圾回收器释放活动对象或者将原始值和指针混合在一起。

主线程的每个改变对象图表的操作将会是竞态数据的潜在来源。由于 V8 是具有多种对象布局优化功能的高性能引擎，潜在竞态数据来源目录相当长。以下是高层次故障：

• 对象分配

• 写对象

• 对象布局变化

• 快照反序列化

• 功能脱优化实现

• 年轻代垃圾回收期间的疏散

• 代码修补

在以上这些操作上，主线程需要与工作线程同步。同步代价和复杂度是操作而定。大部分操作允许轻量级的同步和院子操作之间的访问，但是少部分操作需独占访问对象。在下面的小节中我们强调一些有趣的案例。

写屏障

通过写入对象字段导致的数据竞争通过将写入操作转变为放宽原子写入并调整写入屏障来解决：

// Called after atomic_relaxed_write(&object.field, value);
write_barrier(object, field_offset, value) {
  if (color(value) == white && atomic_color_transition(value, white, grey)) {
    marking_worklist.push(value);
  }
}

与上面的写屏障进行比较

// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

这有两个变化：

1  color检查原对象(color(object) == black)操作不存在

2 color值由白色转变为灰色操作变成原子操作

如果没有color原对象检查，写屏障变得更保守。举个例子，只要对象存在都会标记他们就算那些对象是无法获取的。 我们删除了这个检查以避免在写操作和写障碍之间需要昂贵的 内存栅栏 （memory fence）：

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

没有内存栅栏（memory fence），color对象加载操作在写操作之前将会被重排序。如果我们不阻止重排序，写屏障观察到grey object color并释放，而工作线程在没有看到新值的情况下标记对象。由Dijkstra等人提出的原始写屏障不会检查color对象。他们为了简单起见，但是我们需要他们的正确性