聊聊 JVM 三色標記法

作者：老鄭 2023-01-08 13:46:49

因為SATB相對增量更新效率會高(當然SATB可能造成更多的浮動垃圾)，因為不需要在重新標記階段再次深度掃描被刪除引用對象，而CMS對增量更新的根對象會做深度掃描，G1因為很多對象都位于不同的region，CMS就一塊老年代區域，重新深度掃描對象的話G1的代價會比CMS高，所以G1選擇SATB不深度掃描對象，只是簡單標記，等到下一輪GC再深度掃描。

三色標記（Tri-Color-Marking）

垃圾收集器在并發標記的過程中，執行標記期間應用線程還在并行運行，對象間的引用關系時刻發生變化，垃圾收集器在標記過程中就容易發生多標和漏標（其實多標和漏標我們統稱為誤標）。

針對這一問題我們通過 “三色標記（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 中一塊掃描。這是大概的一個流程，后續會講到，先有一個印象。再回到寫屏障，下面是一個對象賦值操作：

/**
* @param field 某對象的成員變量，如 a.b.d 
* @param new_value 新值，如 null
*/
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 使用增量更新?

參考資料

1.《深入理解 JAVA 虛擬機-第三版》周志明

責任編輯：武曉燕來源：運維開發故事