再谈HotSpot JVM GC机制中的写屏障

前言

在比较久之前的一篇文章《再谈JVM里的记忆集合》中，笔者曾经写了这么一段话：

HotSpot通过写屏障（write barrier）来维护卡表。我们已经知道，内存屏障的主要作用是防止指令重排序，它也是volatile关键字的基础。有了写屏障，JVM就可以保证引用发生改变时，对卡表中的卡做标记与访问内存的顺序不发生变化。在CardTableRS初始化时，所做的第一件事就是创建卡表需要的屏障集合（barrier set）……

为什么划掉了呢？（原文也已经划掉了）

在上文中，笔者犯了一个原则性的低级错误，即把Java内存模型中的内存屏障/内存栅栏（memory barrier/fence）与HotSpot GC机制中的写屏障（write barrier）混为一谈了，但这两者实际上毫无关系。Doug Lea大佬也在《JSR-133 Cookbook for Compiler Writers》一文中明确指出：

Memory barriers are unrelated to the kinds of "write barriers" used in some garbage collectors.

带来困扰，十分抱歉。

写屏障是个有些复杂的话题，准确来说，它在GC中的应用也有不止一处。下面先纠正错误，简单解释写屏障的概念，及其与卡表的关系。

写屏障与卡表

“写屏障”这个词虽然看起来高深，但是它的含义却相当naive——就是对一个对象引用进行写操作（即引用赋值）之前或之后附加执行的逻辑，相当于为引用赋值挂上的一小段钩子代码。

前文所述“HotSpot通过写屏障来维护卡表”，写屏障就是在将引用赋值写入内存之前，先做一步mark card——即将出现跨代引用的内存块对应的卡页置为dirty，如下图所示。

而之前提到过的JVM参数-XX:+UseCondCardMark，就是开启有条件的写屏障：在将卡页置为dirty之前，先检查它是否已经为dirty状态，如果已经是了，就不必再执行mark card动作，以避免虚共享。

写屏障除了用于维护卡表之外，在并行GC（如CMS、G1）中的并发标记阶段还有一个更重要的用途。下面以CMS垃圾收集器为例简单解说。

并行GC中并发标记的漏标隐患

我们已经知道，CMS垃圾收集器的执行分为以下6个阶段：

初始标记
并发标记
并发预清理
重新标记
并发清理
并发重置

其中，只有不带“并发”字眼的初始标记、重新标记两个阶段是stop-the-world的，其他4个阶段都是与用户线程（GC界的术语称作mutator）并行的，这符合CMS收集器追求最少STW时间与最高响应度的宗旨。

初始标记和并发标记阶段就是进行可达性分析。CMS的根搜索机制是深度优先的三色标记（tri-color marking）算法，属于基础知识，不再展开讲了。

初始标记阶段会只遍历GC Roots直接可达的那些对象，并压入标记栈（mark stack）；并发标记阶段会逐一从标记栈中弹出对象，然后不断递归标记它们直接引用的对象，重复压入-弹出过程，直到标记栈为空。

在并发标记阶段，难点在于：用户线程并未停止，仍然在改变对象的引用关系。这有可能造成原本活动的对象被漏标，进而破坏GC的正确性。示例如下图所示。

(a) 搜索对象A的直接子对象，标记对象B为可达（灰色），并将B压入标记栈。此时A的直接子对象搜索完毕，标记为存活（黑色），将A弹出标记栈；

(b) (c) 与此同时，用户线程改变引用，让A引用C，并移除掉B对C的引用；

事实上，不止是CMS，在其他任何并行的垃圾回收器中，都有对象漏标的隐患。Wilson指出，出现漏标的充要条件是以下两个情况同时发生：

mutator使黑色对象直接引用了白色对象；
mutator删除了从灰色对象到白色对象之间的所有引用路径。

强三色不变式与增量更新写屏障

为了解决漏标问题，需要破坏上文所述的两个情况，亦即强制回收器满足如下两个条件之一。

强三色不变式：保证永远不会存在黑色对象到白色对象的引用（破坏情况1）。
弱三色不变式：所有被黑色对象引用的白色对象都处于灰色保护状态，即直接或间接从灰色对象可达（破坏情况2）。

强/弱三色不变式都可以通过屏障技术来实现，并且在不同环境下有多种不同的屏障技术。CMS收集器采用增量更新（incremental update）写屏障实现强三色不变式，具体来讲，是Dijkstra等人提出的Dijkstra写屏障，其逻辑是：

拦截使黑色对象引用指向白色对象的mutate操作，强制被引用指向的白色对象置为灰色状态，并将其压入标记栈。

Dijkstra写屏障的逻辑用伪码表示如下。

write_barrier(obj, field, newobj) {
  if(newobj.mark == FALSE) {
    newobj.mark = TRUE
    push(newobj, $mark_stack)
  }
  *field = newobj
}

可见，之所以名为“增量更新”，是指写屏障会持续hook引用的插入和变更。下图示出了加入增量更新写屏障后，并发标记阶段引用发生更改的情况，可见对象C可以安全地存活了。

但是，增量更新写屏障无法探知堆外（如栈上）GC Roots的引用变化，所以CMS收集器在并发标记和预清理完成后，还得做一次重新标记，即再做一次根搜索。

The End

G1的解决思路与CMS又有不同，是采用了初始快照（snapshot-at-the-beginning, SATB）写屏障实现了弱三色不变式。G1垃圾收集器非常复杂，应该择日好好总结一下，今天就不提了。

明天早起搬砖，民那晚安。