1. 原文

Concurrent marking in V8

2. 摘要翻译

本文会描述一种名为并发标记的垃圾回收技术。这种优化允许JS应用程序在垃圾回收扫描堆内存来标记存活对象的时候仍旧保持应用程序的正常运行。我们的benchmark显示并发标记技术减少了主线程60%-70%的标记耗时。并发标记正是 Orinoco project（这个项目计划渐进式地替换老版本的垃圾回收器，使用最新主流的并发、平行的垃圾回收器）的最新组成部分。并发标记技术会在 Chrome 64 以及 Node.js v10 中默认开启。

Background

存活对象标记是 V8 的 Mark-Compact 内存回收器中的一个阶段。在这个阶段内，垃圾回收期会侦测并标记所有存活的对象。标记开始于一系列已知的存活对象，比如说 global 对象以及当前激活的函数 - 它们被称为根节点。回收器将根节点标记给存活然后依循其中的指针侦测更多的存活对象。回收器持续标记新发现的对象然后继续依循指针来侦测更多的对象，直到没有更多的对象可以标记为止。在标记阶段的最后，所有堆内存中未被标记的对象就是应用程序已经不再使用的对象，并能被安全地回收。

我们可以把内存标记视作图遍历（graph traversal）。堆上的内存对象就像是图里的节点。从一个对象到另一个对象的指针则是图的边界。只要获得图中的一个节点我们就可以通过使用该节点对象的隐藏类型（hidden class）来找到该节点的所有边界。

V8使用每个对象 two mark-bits 以及 一个 marking worklist（一个专门用来存储暂存标记对象的栈） 来实现标记。Two mark-bits 编码了3种颜色：白色（00），灰色（10），以及黑色（11）。初始状态所有的对象都是白色，表示垃圾回收器尚未侦测到它们。当垃圾回收器侦测到对象并将对象推到 marking worklist（栈）内之后，该对象就会从白色被标记为灰色。当回收器将灰色对象从 marking worklist 里取出并访问其所有 fields 之后，将其标记为黑色。这种策略被称为三色标记。当不再有更多灰色对象之后，标记结束。剩余的所有白色对象即不可达对象，将可以被安全地回收。

请注意上述的标记算法仅仅当标记进行中时应用程序必须暂停，才可以正常工作。如果我们允许应用程序在标记过程中继续运行，则应用程序可能改变图并导致回收器将正存活的对象标记回收。

Reducing marking pause

如果一次将所有的标记操作都执行完成的话，在大型堆内存的情况下可能会耗费数百毫秒。

如此之长的停顿可能使应用程序陷入无法响应的状态并导致不佳的用户体验。在2011年V8从 stop-the-world 标记方式转向到渐进式标记。在渐进式标记过程中，回收器将标记工作拆分成多个小的工程，并允许应用程序在这些小工程之间正常运行：

垃圾回收器会自行选择在渐进式标记工作中的每个工程执行多少标记工作，以适应应用程序的内存分配需求。在普通情况下这已经大幅提升了应用程序的响应能力。对于那些堆内存体积非常大，且内存分配压力很大的情况来说，仍旧会有很长的停顿时间，因为回收器必须保持内存的回收节奏以适应应用程序的内存需求。

渐进式标记并非没有额外代价。应用程序必须在所有会改变对象图的操作发生时通知到内存回收器。V8使用 Dijkstra-style 的写屏障（write-barrier）来实现通知。在每次object.field = value形式的写操作之后，V8都会插入写屏障代码：

// 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);
  }
}

写屏障强制保障了不会出现一个黑色对象指向一个白色对象情况的发生。这也作为 strong tri-color invariant 被熟知，并保证了应用程序无法对垃圾回收器隐藏存活的对象，标记行为最终所有的白色对象都是真实不可达的，并可以被安全地清除。

渐进式标记与之前的博文中描述的闲时垃圾回收计划器结合的很好。Chrome 的 Blink 任务计划期能在主线程的空闲时段规划一系列小型的渐进式标记步骤，而避免带来任何的损耗。这种类型的优化工作得非常好，只要有空闲时长。

因写屏障的损耗，渐进式标记可能降低应用程序的吞吐量。如果使用额外的工作线程则可能既提升吞吐量又降低回收的停顿时长。在工作线程上有两种可行的标记方法：平行标记和并发标记。

平行标记发生在主线程和工作线程上。应用程序会在进行平行标记的时候停顿。这是多线程版本的 stop-the-world 标记。

并发标记主要发生在工作线程上。应用程序在并发标记的过程中将继续工作。

下述的两个场景描述了我们是如何在V8中添加对平行和并发标记的支持。

Parallel marking

在平行标记过程中，我们可以假设应用程序并没有在并行运行。这种假设大幅简化了实现，因为我们能假设对象图是静止不变的。为了以平行的方式标记对象图，我们需要保证垃圾回收器的数据结构线程安全并找到一个方法在线程之间高效地共享标记工作。下图显示了平行标记中用到的数据结构。箭头表示了数据流向。为了简化，图中省略了为堆内存去碎片而使用的数据结构。

请注意线程只会读取对象图而永远不会改变它。对象的 mark-bits 以及 marking worklist 必须支持读写操作。

Marking worklist and work stealing

marking worklist 的实现对性能来说非常关键，它可以将工作分发到其他无事可做的线程的方式来均衡线程间的性能表现。

关键点在于如何均衡：(a) 使用完全并发安全的数据结构来获得最佳的共享能力，考虑到所有的对象都可以潜在被分享给其他线程处理 (b) 使用完全本地线程的数据结构，当没有任何对象可以本分享出去，完全为本地线程的吞吐量进行优化。图6显示了V8如何通过一个基于内存段来进行本地线程插入和移除的 marking worklist 在这些需求之间获得均衡的。当一个内存段满了之后，它就被发布到一个共享的全局池中，在这里它就被标记为可被使用（available for stealing）。以这种方式V8得以让标记线程尽可能长地在本地操作，而不需要任何同步行为，并且同时能很好处理某些线程又有新的子对象图到达需要处理而其他某些线程因本地内存段已经被消耗光而无事可做的情况。

Concurrent marking

并发标记允许主线程正常工作的情况下在工作线程中访问堆内存的对象。这使得许多潜在的数据竞争（data races）成为了可能。举例来说，JS代码正在写入某个对象的字段，而同时一个工作线程正在读取这个字段。数据竞争可能误导垃圾回收器，将某些存活的对象标记为可释放或搞混指针的原始值。

每一个在主线程上变动对象图的行为都是一个潜在的数据竞争来源。因为V8是一个使用多种对象布局优化措施的高性能引擎，潜在的数据竞争来源列表相当的场。这里是一份高可能性的列表：

• Object allocation.
• Write to an object field.
• Object layout changes.
• Deserialization from the snapshot.
• Materialization during deoptimization of a function.
• Evacuation during young generation garbage collection.
• Code patching.

主线程必须和子线程同步这些操作。而同步操作的代价和复杂度则依据操作不同而不尽相同。大部分的操作都允许通过内存的原子访问来进行轻量级的同步，但一些操作必须要求对对象的独占访问。在下一个子节中，我们会将其中一些有意思的场景进行强调分析。

Write barrier

由对一个对象的字段的写操作引起的数据竞争可以由，将这次写操作转成一个 relaxed 原子写操作，并触发写屏障来解决：

// 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);
  }
}

这里有两处改动：

对源对象的颜色检查（color(object) == black）被移除了。 值上的由白到灰的颜色转换自动发生了。 写屏障在去除了对源对象的颜色检查之后变得更为保守，举例来说，可能将对象标记为存活即便这些对象并非真的可达。我们将这个检查移除了，是因为否则我们就需要在写操作和写屏障之间添加一个非常昂贵的内存栅栏：

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

只要没有这个内存栅栏，对象颜色的加载操作可以在写操作之前重新排列。如果我们不去阻止这个重新排列，那么写屏障可能观察灰色对象并将其释出（bail out），此时可能一个工作线程将这个对象标记掉了而没有看到它的最新值。原始的写屏障由 Dijkstra et al 提案，也咩有检查对象颜色。他们为了简化而这么做，但我们需要正确性。

Bailout worklist

某些操作，例如代码补丁（code patching），需要对对象的排他性访问。早先我们决定避免对对象的锁，因为它们可能导致优先级反转的问题（priority inversion problem），即主线程必须等待一个工作线程而这个工作线程又在拿着一个对象锁的情况下被重新调度了。作为对象锁的替代，我们允许工作线程使用紧急救助（bailout）的方式访问对象。工作线程通过将一个对象放入到 bailout worklist 来达成这一目标，它将会仅被主线程处理：

工作线程仅会在优化后的代码对象、隐藏类以及弱集合上进行紧急救助（bail out），因为访问这些内容会需要锁或非常昂贵的同步协议。

回想一下，bailout worklist 对于渐进式研发来说非常优秀。我们开始针对所有的队形类型实现工作线程的 bailing out，并一个个添加并发支持。

Object layout changes

一个对象的字段可以存储三种类型的值：一个经过标签的指针，一个经过标签的小整型（被熟知为 Smi），或者是一个未被标签的值类似于一个拆箱后的浮点型数值。指针标签化（Pointer tagging）是一个众所周知的技术，它能高校代表拆箱后的整型。在V8中经过标签的值最重要的一位是用来区分它到底是一个指针还是一个整型。这依赖于指针是 word-aligned。关于一个字段到底是经过标签的还是未经过标签的，可以通过对象的隐藏类中存储的信息获知。

某些操作在V8中改动了一个对象的字段，通过改动对象的隐藏类，将其从标签后改为未标签（或者正相反）的状态。这种对象布局的改动对并行标记来说是不安全的。如果改动发生在正好某个工作线程正在通过老的隐藏类并行访问这个对象，那么就有可能发生两种类型的BUG。第一类，工作线程可能因为把对象误认为是一个未被标签的值而忽视它的指针。写屏障会对这类型的BUG做出保护。第二类，工作线程可能将一个未被标签的值当做一个指针来处理，并取消它的引用，这会导致非法的内存访问，最终最具代表性的就是导致程序的崩溃。为了处理这种问题，我们使用了一个快照协议对对象的 mark-bit 进行同步。这个协议包含了两个部分：假设主线程将一个对象的字段从经过标签的改为未标签的，然后工作线程访问这个对象。在改动这个字段值钱，主线程保证这个对象已经被标记为黑色，并且将其推送到了 bailout worklist 以保证后续访问：

atomic_color_transition(object, white, grey);
if (atomic_color_transition(object, grey, black)) {
  // The object will be revisited on the main thread during draining
  // of the bailout worklist.
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

正如在上面的代码片段锁显示的，工作线程先是加载对象的隐藏类，并对所有依据对象隐藏类而来的指针字段进行快照，通过原子的 relaxed 读操作。接下来尝试使用一个原子的对比和替换操作将对象标记为黑色。如果标记成功那么这意味着快照必须与隐藏类一致，因为主线程在改动这个对象的布局之前将对象标记为黑色了。

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

请注意如果要将一个白色的对象不安全地改动其布局的话，必须将其在主线程上标记。不安全的布局变动相当少见，因此这不会对真实世界应用的性能造成冲击。

Putting it all together

我们将并行标记整合到现存的渐进式标记设施内。主线程由扫描根节点开始标记程序，并开始填充 marking worklist。在这之后主线程将并行标记任务分发到工作线程上。工作线程通过协同工作消耗 marking worklist 的方式，协助主线程开展更快的标记操作。偶尔主线程会通过 bailout worklist 以及 marking worklist 来处理标记操作。一旦 marking worklists 被清空，主线程会完成垃圾回收工作。在结束阶段，主线程会重新扫描根节点，并可能找到更多的白色对象。这些对象会被工作线程进行平行标记。

Results

我们的真实世界场景 benchmarking 框架显示这个优化在主线程的每个垃圾回收周期的标记时长阶段带来了 65% - 70% 的耗时减少，无论是移动端还是桌面端。

并发标记同样减少了 Node.js 的垃圾回收延时。这点特别重要，因为 Node.js 服务器实现了闲时垃圾回收计划器，因此将永远不会隐藏在 non-jank-critical 阶段产生的标记时长。并发标记会在 Node.js v10 中实装。

EOF