三色標(biāo)記（Tri-Color-Marking）

垃圾收集器在并發(fā)標(biāo)記的過(guò)程中，執(zhí)行標(biāo)記期間應(yīng)用線程還在并行運(yùn)行，對(duì)象間的引用關(guān)系時(shí)刻發(fā)生變化，垃圾收集器在標(biāo)記過(guò)程中就容易發(fā)生多標(biāo)和漏標(biāo)（其實(shí)多標(biāo)和漏標(biāo)我們統(tǒng)稱為誤標(biāo)）。

針對(duì)這一問(wèn)題我們通過(guò) “三色標(biāo)記 （Tri-Color-Marking）” 作為理論工具來(lái)輔助推導(dǎo)，將垃圾收集器遍歷對(duì)象引用的過(guò)程中，“按照是否訪問(wèn)過(guò)” 這個(gè)條件標(biāo)記成三種顏色。

• 黑色：表示對(duì)象已經(jīng)被垃圾收集器訪問(wèn)過(guò)，并且這個(gè)對(duì)象的所有引用都被掃描過(guò)。它是安全存活的，如果有其他的對(duì)象指向了黑色的對(duì)象，無(wú)須重新掃描一遍。黑色對(duì)象不能直接（ 不經(jīng)過(guò)灰色對(duì)象）指向白色對(duì)象。
• 灰色：表示已經(jīng)被垃圾收集器訪問(wèn)過(guò)，但是這個(gè)對(duì)象至少存在一個(gè)引用還沒(méi)有被掃描過(guò)。
• 白色：表示對(duì)象尚未被垃圾收集器訪問(wèn)過(guò)。顯然在可達(dá)性分析的開(kāi)始階段，所有的對(duì)象都是白色的，若在分析結(jié)束的時(shí)候還是白色的表示對(duì)象不可達(dá)。

三色標(biāo)記示例代碼（示例來(lái)源于網(wǎng)絡(luò)）：

public class TriColorMarking {

    public static void main(String[] args){
        A a = new A();
        //開(kāi)始做并發(fā)標(biāo)記
        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 {
}

例子的一個(gè)簡(jiǎn)單說(shuō)明：
1. 在 new A() 的時(shí)候會(huì)創(chuàng)建引用關(guān)系 A -> B ，B-> C , B -> D;
2. 當(dāng)我們做并發(fā)標(biāo)記的時(shí)候，垃圾收集器訪問(wèn)過(guò) A、B、C、D 最終都標(biāo)記為黑色。但是這個(gè)時(shí)候程序執(zhí)行了一個(gè) a.b.d = null 就標(biāo)識(shí) D 其實(shí)是沒(méi)有引用，理論上 D 對(duì)象可以被回收。這種情況就產(chǎn)生了 “浮動(dòng)垃圾”。
3. 當(dāng)我們發(fā)現(xiàn)了 D 沒(méi)有引用，標(biāo)記為白色，但是在標(biāo)記完成過(guò)后發(fā)現(xiàn) a.d = d 。又新增了對(duì)象引用如果將 d 回收掉程序就會(huì)報(bào)錯(cuò)肯定是不行的。這是一個(gè)典型的 “多標(biāo)” 場(chǎng)景。

下面我們會(huì)通過(guò)并發(fā)標(biāo)記的過(guò)程中出現(xiàn)的漏標(biāo)和多標(biāo)場(chǎng)景進(jìn)行分析。

漏標(biāo)

在并發(fā)標(biāo)記過(guò)程中，將原本消亡的對(duì)象標(biāo)記為存活對(duì)象，這就是漏標(biāo)。就會(huì)產(chǎn)生浮動(dòng)垃圾，需要等到下次 GC 的時(shí)候清理。產(chǎn)生過(guò)程：

• 程序刪除了全部從灰色對(duì)象到該白色對(duì)象的直接或者間接引用

標(biāo)記過(guò)程中從圖1到下圖

其實(shí)浮動(dòng)垃圾是可以接受的只會(huì)影響垃圾收集器的效率，或者說(shuō)是收集的比率。

多標(biāo)

在并發(fā)標(biāo)記過(guò)程中，將原本存活的對(duì)象標(biāo)記為需要回收的對(duì)象。產(chǎn)生過(guò)程：程序插入一條或者多條從黑色對(duì)象到白色對(duì)象的新引用 標(biāo)記過(guò)程中從圖1到下圖

這種情況是不可以接受的，如果正在被使用的程序?qū)ο蟊?JVM 回收，會(huì)導(dǎo)致程序運(yùn)行錯(cuò)誤，是不可以接受的會(huì)導(dǎo)致嚴(yán)重 BUG。

解決漏標(biāo)和多標(biāo)

解決漏標(biāo)和多標(biāo)分別有兩種解決方案：增量更新（Incremental Update） 和原始快照（Snapshot At The Beginning, STAB）

增量更新（Incremental Update）

這并發(fā)標(biāo)記過(guò)程中，當(dāng)黑色對(duì)象插入了新的指向白色引用關(guān)系時(shí)，就將這個(gè)插入引用記錄下來(lái)，并發(fā)標(biāo)記結(jié)束后，再將這些記錄過(guò)的引用關(guān)系中的黑色對(duì)象為根，重新掃描一次。簡(jiǎn)化理解, 黑色對(duì)象一旦新插入了指向白色對(duì)象的引用之后， 它就變成灰色對(duì)象。

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

這并發(fā)標(biāo)記過(guò)程中，當(dāng)灰色對(duì)象要?jiǎng)h除白色對(duì)象的引用關(guān)系時(shí)，就將這個(gè)需要?jiǎng)h除的記錄下來(lái)，在并發(fā)掃描結(jié)束后，再將這些記錄過(guò)的引用關(guān)系中的灰色對(duì)象為根，重新掃描一次，這樣就能掃描到白色對(duì)象，將白色的對(duì)象直接標(biāo)記為黑色（目的就是為了讓這種對(duì)象在本輪 GC 清理中能夠存活下來(lái)，待下一輪 GC 的時(shí)候重新掃描，這個(gè)對(duì)象也可能成為浮動(dòng)垃圾） 總之，無(wú)論是引用關(guān)系記錄插入還是刪除，虛擬機(jī)的記錄操作都是通過(guò)寫屏障來(lái)實(shí)現(xiàn)的。

寫屏障（Write Barrier）

JVM 通過(guò)寫屏障（Write Barrier）來(lái)維護(hù)卡表，卡表是記憶集的實(shí)現(xiàn)。記憶集是用來(lái)縮小 GC Root 的掃描范圍，我們?cè)?GC 的時(shí)候只需要去過(guò)濾卡表變臟（Dirty）的元素，找到具體一塊卡頁(yè)內(nèi)存塊，放入 GC Root 中一塊掃描。這是大概的一個(gè)流程，后續(xù)會(huì)講到，先有一個(gè)印象。再回到寫屏障，下面是一個(gè)對(duì)象賦值操作：

/**
* @param field 某對(duì)象的成員變量，如 a.b.d 
* @param new_value 新值，如 null
*/
void oop_field_store(oop* field, oop new_value){ 
    *field = new_value; // 賦值操作
}

寫屏障可以看做是虛擬機(jī)執(zhí)行對(duì)象字段賦值的一個(gè)攔截，類比 Spring AOP 的切面思想。

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

寫屏障，SATB

當(dāng)對(duì)象B的成員變量的引用發(fā)生變化時(shí)，比如引用消失（a.b.d = null），我們可以利用寫屏障，將B原來(lái)成員變量的引用對(duì)象D記錄下來(lái)：

void pre_write_barrier(oop* field){
    oop old_value = *field;    // 獲取舊值
    remark_set.add(old_value); // 記錄原來(lái)的引用對(duì)象
}

寫屏障，增量更新

當(dāng)對(duì)象A的成員變量的引用發(fā)生變化時(shí)，比如新增引用（a.d = d），我們可以利用寫屏障，將A新的成員變量引用對(duì)象D記錄下來(lái)：

void post_write_barrier(oop* field, oop new_value){  
    remark_set.add(new_value);  // 記錄新引用的對(duì)象
}

讀屏障（Load Barrier）

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

讀屏障是直接針對(duì)第一步：D d = a.b.d，當(dāng)讀取成員變量時(shí)，一律記錄下來(lái)：

void pre_load_barrier(oop* field){  
    oop old_value = *field;
    remark_set.add(old_value); // 記錄讀取到的對(duì)象
}

記憶集和卡表（Remembered Set And Card Table）

垃圾收集器在新生代建立了記憶集（Remembered Set）的數(shù)據(jù)結(jié)構(gòu)，用來(lái)避免把整個(gè)老年代的 GC root 掃描一遍。事實(shí)上并不只是新生代、 老年代之間才有跨代引用的問(wèn)題， 所有涉及部分區(qū)域收集（Partial GC） 行為的垃圾收集器， 典型的如G1、 ZGC 和 Shenandoah 收集器， 都會(huì)面臨相同的問(wèn)題。記憶集是一種記錄非收集區(qū)域指向收集區(qū)域的指針集合抽象的數(shù)據(jù)結(jié)構(gòu)。

Hotspot 中使用一種叫做 “卡表” （Card Table）的方式來(lái)實(shí)現(xiàn)記憶集，也是目前最常用的一種方式。卡表和記憶集的關(guān)系，可以類比 Java 語(yǔ)言中 HashMap 和 Map 之間的關(guān)系?？ū硎且粋€(gè)字節(jié)數(shù)組實(shí)現(xiàn)：CARD_TABLE[]， 每個(gè)元素都對(duì)應(yīng)著一個(gè)標(biāo)識(shí)的內(nèi)存區(qū)域一塊特定大小的內(nèi)存塊，稱為“卡頁(yè)”。Hotsport 卡頁(yè)的大小是 2^9 也就是 512 字節(jié)。

一個(gè)卡頁(yè)中可以包含多個(gè)對(duì)象，只要卡頁(yè)內(nèi)一個(gè)或者多個(gè)對(duì)象的字段存在跨代引用，其對(duì)應(yīng)的卡表的元素標(biāo)識(shí)就變成了1，表示該元素變臟，否則為 0。GC 時(shí)，只需要篩選卡表中變臟的元素加入到 GCRoot 中。

卡表的維護(hù)

如何讓卡表變臟，即發(fā)生引用字段賦值時(shí)，如何更新卡表對(duì)應(yīng)的標(biāo)識(shí)為 1。Hotspot使用寫屏障維護(hù)卡表狀態(tài)。

收集器采用的解決方案

CMS : 寫屏障，增量更新 

G1，Shednandoah: 寫屏障 + STAB 

ZGC：讀屏障

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

因?yàn)镾ATB相對(duì)增量更新效率會(huì)高(當(dāng)然SATB可能造成更多的浮動(dòng)垃圾)，因?yàn)椴恍枰谥匦聵?biāo)記階段再次深度掃描被刪除引用對(duì)象，而CMS對(duì)增量更新的根對(duì)象會(huì)做深度掃描，G1因?yàn)楹芏鄬?duì)象都位于不同的region，CMS就一塊老年代區(qū)域，重新深度掃描對(duì)象的話G1的代價(jià)會(huì)比CMS高，所以G1選擇SATB不深度掃描對(duì)象，只是簡(jiǎn)單標(biāo)記，等到下一輪GC再深度掃描。

參考資料

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