聊聊 JVM 三色标记法

垃圾收集器在并发标记的过程中，执行标记期间应用线程还在并行运行，对象间的引用关系时刻发生变化，垃圾收集器在标记过程中就容易发生多标和漏标（其实多标和漏标我们统称为误标）。

针对这一问题我们通过 “三色标记 （Tri-Color-Marking）” 作为理论工具来辅助推导，将垃圾收集器遍历对象引用的过程中，“按照是否访问过” 这个条件标记成三种颜色。

• 黑色：表示对象已经被垃圾收集器访问过，并且这个对象的所有引用都被扫描过。它是安全存活的，如果有其他的对象指向了黑色的对象，无须重新扫描一遍。黑色对象不能直接（ 不经过灰色对象）指向白色对象。
• 灰色：表示已经被垃圾收集器访问过，但是这个对象至少存在一个引用还没有被扫描过。
• 白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析的开始阶段，所有的对象都是白色的，若在分析结束的时候还是白色的表示对象不可达。

三色标记示例代码（示例来源于网络）：

public class TriColorMarking {

    public static void main(String[] args){
        A a = new A();
        //开始做并发标记
        D d = a.b.d;   // 1.读
        a.b.d = null;  // 2.写
        a.d = d;       // 3.写
    }
}

class A {
    B b = new B();
    D d = null;
}

class B {
    C c = new C();
    D d = new D();
}

class C {
}

class D {
}

例子的一个简单说明：
1. 在 new A() 的时候会创建引用关系 A -> B ，B-> C , B -> D;
2. 当我们做并发标记的时候，垃圾收集器访问过 A、B、C、D 最终都标记为黑色。但是这个时候程序执行了一个 a.b.d = null 就标识 D 其实是没有引用，理论上 D 对象可以被回收。这种情况就产生了 “浮动垃圾”。
3. 当我们发现了 D 没有引用，标记为白色，但是在标记完成过后发现 a.d = d 。又新增了对象引用如果将 d 回收掉程序就会报错肯定是不行的。这是一个典型的 “多标” 场景。

下面我们会通过并发标记的过程中出现的漏标和多标场景进行分析。

漏标

在并发标记过程中，将原本消亡的对象标记为存活对象，这就是漏标。就会产生浮动垃圾，需要等到下次 GC 的时候清理。产生过程：

• 程序删除了全部从灰色对象到该白色对象的直接或者间接引用

标记过程中从图1到下图

其实浮动垃圾是可以接受的只会影响垃圾收集器的效率，或者说是收集的比率。

多标

在并发标记过程中，将原本存活的对象标记为需要回收的对象。产生过程：程序插入一条或者多条从黑色对象到白色对象的新引用 标记过程中从图1到下图

这种情况是不可以接受的，如果正在被使用的程序对象被 JVM 回收，会导致程序运行错误，是不可以接受的会导致严重 BUG。

解决漏标和多标

解决漏标和多标分别有两种解决方案：增量更新（Incremental Update） 和原始快照（Snapshot At The Beginning, STAB）

增量更新（Incremental Update）

这并发标记过程中，当黑色对象插入了新的指向白色引用关系时，就将这个插入引用记录下来，并发标记结束后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。简化理解, 黑色对象一旦新插入了指向白色对象的引用之后， 它就变成灰色对象。

原始快照（Snapshot At The Beginning, STAB）

这并发标记过程中，当灰色对象要删除白色对象的引用关系时，就将这个需要删除的记录下来，在并发扫描结束后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次，这样就能扫描到白色对象，将白色的对象直接标记为黑色（目的就是为了让这种对象在本轮 GC 清理中能够存活下来，待下一轮 GC 的时候重新扫描，这个对象也可能成为浮动垃圾） 总之，无论是引用关系记录插入还是删除，虚拟机的记录操作都是通过写屏障来实现的。

写屏障（Write Barrier）

JVM 通过写屏障（Write Barrier）来维护卡表，卡表是记忆集的实现。记忆集是用来缩小 GC Root 的扫描范围，我们在 GC 的时候只需要去过滤卡表变脏（Dirty）的元素，找到具体一块卡页内存块，放入 GC Root 中一块扫描。这是大概的一个流程，后续会讲到，先有一个印象。再回到写屏障，下面是一个对象赋值操作：

void oop_field_store(oop* field, oop new_value){ 
    *field = new_value; // 赋值操作
}

写屏障可以看做是虚拟机执行对象字段赋值的一个拦截，类比 Spring AOP 的切面思想。

void oop_field_store(oop* field, oop new_value){  
    pre_write_barrier(field);          // 写前屏障
    *field = new_value; 
    post_write_barrier(field, value);  // 写后屏障
}

写屏障，SATB

当对象B的成员变量的引用发生变化时，比如引用消失（a.b.d = null），我们可以利用写屏障，将B原来成员变量的引用对象D记录下来：

void pre_write_barrier(oop* field){
    oop old_value = *field;    // 获取旧值
    remark_set.add(old_value); // 记录原来的引用对象
}

写屏障，增量更新

当对象A的成员变量的引用发生变化时，比如新增引用（a.d = d），我们可以利用写屏障，将A新的成员变量引用对象D记录下来：

void post_write_barrier(oop* field, oop new_value){  
    remark_set.add(new_value);  // 记录新引用的对象
}

读屏障（Load Barrier）

oop oop_field_load(oop* field){
    pre_load_barrier(field); // 读屏障-读取前操作
    return *field;
}

读屏障是直接针对第一步：D d = a.b.d，当读取成员变量时，一律记录下来：

void pre_load_barrier(oop* field){  
    oop old_value = *field;
    remark_set.add(old_value); // 记录读取到的对象
}

记忆集和卡表（Remembered Set And Card Table）

垃圾收集器在新生代建立了记忆集（Remembered Set）的数据结构，用来避免把整个老年代的 GC root 扫描一遍。事实上并不只是新生代、 老年代之间才有跨代引用的问题， 所有涉及部分区域收集（Partial GC） 行为的垃圾收集器， 典型的如G1、 ZGC 和 Shenandoah 收集器， 都会面临相同的问题。记忆集是一种记录非收集区域指向收集区域的指针集合抽象的数据结构。

Hotspot 中使用一种叫做 “卡表” （Card Table）的方式来实现记忆集，也是目前最常用的一种方式。卡表和记忆集的关系，可以类比 Java 语言中 HashMap 和 Map 之间的关系。卡表是一个字节数组实现：CARD_TABLE[]， 每个元素都对应着一个标识的内存区域一块特定大小的内存块，称为“卡页”。Hotsport 卡页的大小是 2^9 也就是 512 字节。

一个卡页中可以包含多个对象，只要卡页内一个或者多个对象的字段存在跨代引用，其对应的卡表的元素标识就变成了1，表示该元素变脏，否则为 0。GC 时，只需要筛选卡表中变脏的元素加入到 GCRoot 中。

卡表的维护

如何让卡表变脏，即发生引用字段赋值时，如何更新卡表对应的标识为 1。Hotspot使用写屏障维护卡表状态。

收集器采用的解决方案

CMS : 写屏障，增量更新 

G1，Shednandoah: 写屏障 + STAB 

ZGC：读屏障

为什么 G1 采用 SATB，CMS 使用增量更新? 

因为SATB相对增量更新效率会高(当然SATB可能造成更多的浮动垃圾)，因为不需要在重新标记阶段再次深度扫描被删除引用对象，而CMS对增量更新的根对象会做深度扫描，G1因为很多对象都位于不同的region，CMS就一块老年代区域，重新深度扫描对象的话G1的代价会比CMS高，所以G1选择SATB不深度扫描对象，只是简单标记，等到下一轮GC再深度扫描。

参考资料

1.《深入理解 JAVA 虚拟机-第三版》周志明