三色标记过程

可达性分析

GC过程中需要对对象图遍历做可达性分析。使用了三色标记法进行分析。

什么三色？
白色：尚未访问过。
黑色：本对象已访问过，而且本对象 引用到 的其他对象 也全部访问过了。
灰色：本对象已访问过，但是本对象 引用到 的其他对象 尚未全部访问完。全部访问后，会转换为黑色。

三色标记过程是什么？
1.初始时，所有对象都在 【白色集合】中；
2.将GC Roots 直接引用到的对象 挪到 【灰色集合】中；
3.从灰色集合中获取对象：
3.1. 将本对象 引用到的 其他对象 全部挪到 【灰色集合】中；
3.2. 将本对象 挪到 【黑色集合】里面。
4.重复步骤3，直至【灰色集合】为空时结束。
5.结束后，仍在【白色集合】的对象即为GC Roots 不可达，可以进行回收。

Stop The World 时，对象间的引用 是不会发生变化的，可以轻松完成标记。
而当需要支持并发标记时，即标记期间应用线程还在继续跑，没有STW，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。

多标和漏标是什么意思？
浮动垃圾(多标)：将原本应该被清除的对象，误标记为存活对象。后果是垃圾回收不彻底，不过影响不大，可以在下个周期被回收；
对象消失(漏标)：将原本应该存活的对象，误标记为需要清理的对象。后果很严重，影响程序运行，是不可容忍的。

多标：
假设已经遍历到E（变为灰色了），此时应用执行了 objD.fieldE = null

E还会继续遍历下去，最终E、F、G都是黑色，导致没有在本轮GC中回收，需要等待下一轮GC。此外并发标记后产生的新对象，通常的做法是直接当成黑色，本轮不会清除，可能会成为浮动垃圾（本应回收的没被回收）。

漏标：
假设GC线程已经遍历到E，此时应用线程先执行了

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 断开引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G
1
2
3

E > G 断开，D引用 G。此刻扫描到E，E到G的引用切断了，G故不会加入灰色集合。D引用了G，但是D已经是黑色了，不会再遍历G。G在本轮GC中被回收，影响到程序的正确性。

漏标必须要同时满足以下两个条件：

• 赋值器插入了一条或者多条从黑色对象到白色对象的新引用；
• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

解决漏标问题
破坏两个条件之一即可。如下：

• 增量更新：Incremental Update。
• 原始快照：Snapshot At The Beginning，SATB。

增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用时，就将这个新加入的引用记录下来，待并发标记完成后，重新对这种新增的引用记录进行扫描；原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，也是将这个记录下来，并发标记完成后，对该记录进行重新扫描。

增量更新
如果在标记过程中发出引用的对象是黑色对象，且新的引用的目标对象为灰色或白色，那么就把发出引用的对象涂成灰色，后续会重新扫描。

write_barrier(obj, field, newobj) {
    // obj为引用者 newobj为被引用者 field为引用类型字段
    if($gc_phase == GC_MARK && obj.mark == TRUE && newobj.mark == FALSE) {
        obj.mark = FALSE;
        push(obj, $mark_stack);
    }
    *field = newobj;
}
1
2
3
4
5
6
7
8

原始快照
原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，并发扫描结束后，在将这些记录重新扫描一次。SATB 的过程可以简单理解为：当并发标记阶段引用的关系发生变化时，旧引用所指向的对象就会被标记，同时其子引用对象也会被递归标记，这样快照的完整性就得到保证了。

write_barrier(obj, field, newobj) {
    // obj为引用者 newobj为被引用者 field为引用类型字段
    oldobj = *field;
    if(gc_phase == GC_MARK && oldobj.mark == FALSE) {
        // 将被引用者涂成灰色
        oldobj.mark = TRUE;
        push(oldobj, $mark_stack);
    }
    *field = newobj;
}
1
2
3
4
5
6
7
8
9
10

当 GC 进入到标记阶段且 oldobj 没被标记时，则标记 oldobj，并将其记录。也就是说，在标记阶段中如果指针更新前引用的 oldobj 是白色对象，就将其涂成灰色，后续继续扫描。

增量更新和原始快照都需要记录引用关系，那这个记录的时间点发生在什么时刻呢？
都是通过写屏障维护的。变更引用类型字段的时候会产生环绕通知，JVM在环绕通知里加了记录引用关系的操作。
原始快照是通过写前屏障维护的。

参考

三色标记
三色标记