文章目錄

• 1. 垃圾回收的簡單回顧
• 2. 三色標記法

• 2.1 基本算法
• 2.2 多標-浮動垃圾
• 2.3 漏標-讀寫屏障

• 2.3.1 寫屏障（Store Barrier）

• (1) 寫屏障 + 增量更新
• (2) 寫屏障 + SATB

• 2.3.2 讀屏障（Load Barrier）

• 2.4 三色標記法與現代垃圾回收器

1. 垃圾回收的簡單回顧

關於垃圾回收算法，基本就是那麼幾種：標記-清除、標記-複製、標記-整理。在此基礎上可以增加分代（新生代/老年代），每代採取不同的回收算法，以提高整體的分配和回收效率。

無論使用哪種算法，標記總是必要的一步。垃圾回收器的工作流程大體如下：

1. 標記出哪些對象是存活的，哪些是垃圾（可回收）；
2. 進行回收（清除/複製/整理），如果有移動過對象（複製/整理），還需要更新引用。

本文着重來看下標記的部分的。CMS和G1都使用了三色標記法。

2. 三色標記法

2.1 基本算法

要找出存活對象，根據可達性分析，從GC Roots開始進行遍歷訪問，可達的則為存活對象：

最終結果：A/D/E/F/G 可達。

我們把遍歷對象圖過程中遇到的對象，按“是否訪問過”這個條件標記成以下三種顏色：

• 白色：尚未訪問過。
• 黑色：本對象已訪問過，而且本對象 引用到 的其他對象 也全部訪問過了。
• 灰色：本對象已訪問過，但是本對象 引用到 的其他對象 尚未全部訪問完。全部訪問後，會轉換為黑色。

  
三色標記遍歷過程：
假設現在有白、灰、黑三個集合（表示當前對象的顏色），其遍歷訪問過程為：

1. 初始時，所有對象都在 【白色集合】中；
2. 將GC Roots 直接引用到的對象 挪到 【灰色集合】中；
3. 從灰色集合中獲取對象：
   3.1. 將本對象 引用到的 其他對象 全部挪到 【灰色集合】中；
   3.2. 將本對象 挪到 【黑色集合】裏面。
4. 重複步驟3，直至【灰色集合】為空時結束。
5. 結束後，仍在【白色集合】的對象即為GC Roots 不可達，可以進行回收。

注：如果標記結束後對象仍為白色，意味着已經“找不到”該對象在哪了，不可能會再被重新引用。

當Stop The World （以下簡稱 STW）時，對象間的引用 是不會發生變化的，可以輕鬆完成標記。而當需要支持併發標記時，即標記期間應用線程還在繼續跑，對象間的引用可能發生變化，多標和漏標的情況就有可能發生。

2.2 多標-浮動垃圾

假設已經遍歷到E（變為灰色了），此時應用執行了 objD.fieldE = null ：D > E 的引用斷開。

此刻之後，對象E/F/G是“應該”被回收的。然而因為E已經變為灰色了，其仍會被當作存活對象繼續遍歷下去。最終的結果是：這部分對象仍會被標記為存活，即本輪GC不會回收這部分內存。

這部分本應該回收 但是 沒有回收到的內存，被稱之為“浮動垃圾”。浮動垃圾並不會影響應用程序的正確性，只是需要等到下一輪垃圾回收中才被清除。

另外，針對併發標記開始後的新對象，通常的做法是直接全部當成黑色，本輪不會進行清除。這部分對象期間可能會變為垃圾，這也算是浮動垃圾的一部分。

2.3 漏標-讀寫屏障

假設GC線程已經遍歷到E（變為灰色了），此時應用線程先執行了：

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 斷開引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

E > G 斷開，D引用 G。

此時切回GC線程繼續跑，因為E已經沒有對G的引用了，所以不會將G放到灰色集合；儘管因為D重新引用了G，但因為D已經是黑色了，不會再重新做遍歷處理。

最終導致的結果是：G會一直停留在白色集合中，最後被當作垃圾進行清除。這直接影響到了應用程序的正確性，是不可接受的。

不難分析，漏標只有同時滿足以下兩個條件時才會發生：

• 條件一：灰色對象 斷開了 白色對象的引用（直接或間接的引用）；即灰色對象 原來成員變量的引用 發生了變化。
• 條件二：黑色對象 重新引用了 該白色對象；即黑色對象 成員變量增加了 新的引用。

從代碼的角度看：

var G = objE.fieldG; // 1.讀
objE.fieldG = null;  // 2.寫
objD.fieldG = G;     // 3.寫

1. 讀取 對象E的成員變量fieldG的引用值，即對象G；
2. 對象E 往其成員變量fieldG，寫入 null值。
3. 對象D 往其成員變量fieldG，寫入 對象G ；

我們只要在上面這三步中的任意一步中做一些“手腳”，將對象G記錄起來，然後作為灰色對象再進行遍歷即可。比如放到一個特定的集合，等初始的GC Roots遍歷完（併發標記），該集合的對象 遍歷即可（重新標記）。

重新標記是需要STW的，因為應用程序一直在跑的話，該集合可能會一直增加新的對象，導致永遠都跑不完。當然，併發標記期間也可以將該集合中的大部分先跑了，從而縮短重新標記STW的時間，這個是優化問題了。

寫屏障用於攔截第二和第三步；而讀屏障則是攔截第一步。它們的攔截的目的很簡單：就是在讀寫前後，將對象G給記錄下來。

2.3.1 寫屏障（Store Barrier）

給某個對象的成員變量賦值時，其底層代碼大概長這樣：

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

所謂的寫屏障，其實就是指在賦值操作前後，加入一些處理（可以參考AOP的概念）：

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

(1) 寫屏障 + 增量更新

當對象D的成員變量的引用發生變化時（objD.fieldG = G;），我們可以利用寫屏障，將D新的成員變量引用對象G記錄下來：

void post_write_barrier(oop* field, oop new_value) {  
  if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
      remark_set.add(new_value); // 記錄新引用的對象
  }
}

【當有新引用插入進來時，記錄下新的引用對象】
這種做法的思路是：針對新增的引用，將其記錄下來等待遍歷，即增量更新（Incremental Update）。達到的效果是D由黑色變灰色。

增量更新破壞了條件二：【黑色對象 重新引用了 該白色對象】，從而保證了不會漏標。

(2) 寫屏障 + SATB

當對象E的成員變量的引用發生變化時（objE.fieldG = null;），我們可以利用寫屏障，將E原來成員變量的引用對象G記錄下來：

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

【當原來成員變量的引用發生變化之前，記錄下原來的引用對象】
這種做法的思路是：嘗試保留開始時的對象圖，即原始快照（Snapshot At The Beginning，SATB），當某個時刻 的GC Roots確定後，當時的對象圖就已經確定了。
比如 當時 D是引用着G的，那後續的標記也應該是按照這個時刻的對象圖走（D引用着G）。如果期間發生變化，則可以記錄起來，保證標記依然按照原本的視圖來。

SATB破壞了條件一：【灰色對象 斷開了 白色對象的引用】，從而保證了不會漏標。

使用SATB的原因：
1.因為增量更新會在重新標記的時候將從黑色變成灰色的對象在掃描一遍，會更費時。
2.使用SATB就會大大減少掃描對象，原因是隻多掃描在GC堆棧中發生改變的引用（和G1的一個RSet進行配合，RSet為每個）

2.3.2 讀屏障（Load Barrier）

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

讀屏障是直接針對第一步：var G = objE.fieldG;，當讀取成員變量時，一律記錄下來：

void pre_load_barrier(oop* field, oop old_value) {  
  if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
      oop old_value = *field;
      remark_set.add(old_value); // 記錄讀取到的對象
  }
}

這種做法是保守的，但也是安全的。因為條件二中【黑色對象 重新引用了 該白色對象】，重新引用的前提是：得獲取到該白色對象，此時已經讀屏障就發揮作用了。

2.4 三色標記法與現代垃圾回收器

現代追蹤式（可達性分析）的垃圾回收器幾乎都借鑑了三色標記的算法思想，儘管實現的方式不盡相同：比如白色/黑色集合一般都不會出現（但是有其他體現顏色的地方）、灰色集合可以通過棧/隊列/緩存日誌等方式進行實現、遍歷方式可以是廣度/深度遍歷等等。

對於讀寫屏障，以Java HotSpot VM為例，其併發標記時對漏標的處理方案如下：

• CMS：寫屏障 + 增量更新
• G1：寫屏障 + SATB
• ZGC：讀屏障

工程實現中，讀寫屏障還有其他功能，比如寫屏障可以用於記錄跨代/區引用的變化，讀屏障可以用於支持移動對象的併發執行等。功能之外，還有性能的考慮，所以對於選擇哪種，每款垃圾回收器都有自己的想法。