作者 | 蔡柱梁

審校 | 重樓

前言

很多人都知道垃圾收集會掃描GC Roots，但是卻不清楚這么多的根對象，如何提升性能？提升性能的設計又會帶來什么新的問題？了解這些，對于JVM調優是很有幫助的。只有了解機制，才能更好地優化性能。

根節點枚舉

垃圾收集的第一件事就是根節點枚舉，這樣才能標記垃圾對象，完成垃圾收集。

OopMap

要進行根節點枚舉，最簡單的實現是遍歷掃描所有 GC Roots。可如果挨個遍歷做引用判斷的話，將會消耗大量的時間，而且至今為止所有垃圾收集器在做根節點枚舉時都是需要暫停用戶線程的（因為可達性分析算法做引用判斷時需要根節點的對象引用關系是不變的，這樣才能保證不會出現回收非死亡對象這種嚴重的Bug）。這樣Java的應用就無法提供給人使用了，因為明顯的卡頓對用戶體驗來說是毀滅性的打擊。

實際上，虛擬機不需要遍歷所有根節點，根據自己想要回收的內存區域去掃描這個區域相關的 GC Roots 即可。在 HotSpot 中，它是通過維護 OopMap 來記錄哪些地方存放著對象引用的，這樣收集器在掃描時就不需要檢查所有的 GC Roots。

安全點

在 OopMap 的協助下，HotSpot 可以快速準確地完成 GC Roots 枚舉，但是也帶來了新的問題：

可能導致引用關系變化或者說導致 OopMap 內容變化的指令非常多。如果為每一條指令都生成對應的 OopMap，那將會需要大量的額外存儲空間。這樣垃圾收集伴隨而來的空間成本就會變得無法忍受的高昂。

實際上， HotSpot 也只是在 “特定的位置” 記錄了這些信息，這些位置被稱為安全點（Safepoint）。用戶程序執行時并非在代碼指令流的任意位置都能夠停頓下來開始垃圾收集的，而是強制要求必須到達安全點才能夠暫停。

因此，安全點的選定既不能太少以至于讓垃圾收集器等待時間過長，也不能太多以至于過分增大運行時的內存負荷。安全點位置的選取基本上是以 “是否具有讓程序長時間執行的特征” 為標準進行選定的。“長時間執行”的最明顯特征就是指令序列的復用（例如：方法調用、循環跳轉、異常跳轉等等），所以只有具有這些功能的指令才會產生安全點。

知道安全點的選取之后，就要思考：如何在垃圾收集發生時讓所有線程（不包括執行 JNI 調用的線程）都跑到最近的安全點，然后停頓下來。有兩種方案可供選擇：搶先式中斷（Preemptive Suspension）和主動式中斷（Voluntary Suspension，目前大多數虛擬機都采用這個方案響應 GC 事件）。

• 搶先式中斷：搶先式中斷不需要線程的執行代碼主動配合，在垃圾收集發生時，系統首先把所有用戶線程全部中斷；如果發現有線程不在安全點上，就恢復該線程執行，讓它跑到安全點再重新中斷。
• 主動式中斷：當垃圾收集需要中斷線程時，不直接對線程操作，僅僅設置一個標志位，各個線程執行過程中會不停地輪詢該標志，一旦發現該標志為true時，就會在最近的安全點上主動掛起。

安全區域

安全點看似已經完美解決如何停頓用戶線程，讓虛擬機進入垃圾回收狀態的問題。安全點機制保證了程序執行時在不太長的時間內就會遇到可進入垃圾收集過程的安全點，但是程序“不執行”的時候呢？比如用戶線程處于 Sleep 狀態或者 Blocked 狀態，這時候線程無法響應虛擬機的中斷請求，不能再走到安全點中斷掛起自己，虛擬機也不可能一直傻傻地等線程重新激活走到安全點。對于這種情況，就必須引入安全區域（Safe Region）來解決。

安全區域是指能夠確保在某一段代碼片段之中，引用關系不會發生變化。因此，在這個區域任意地方開始垃圾收集都是安全的。我們也可以把安全區域看作為被拉伸了的安全點。

當用戶線程執行到安全區域時，首先會標識自己已進入安全區域，虛擬機發起垃圾收集時就不需要管那些聲明在安全區域的線程。當線程要離開安全區域時，它要檢查虛擬機是否已經完成垃圾收集過程中需要暫停用戶線程的階段(如：根節點枚舉)。如果完成了，那線程可以離開安全區域繼續執行；否則它需要收到垃圾收集器發出可以離開安全區域的信號才可以離開安全區域。

記憶集與卡表

使用分代收集理論實現的垃圾收集器存在對象跨代引用的問題（哪怕是現在ZGC，雖然沒有分代的概念了，但是仍然有區域的概念。跨代引用的問題本質上就是分區域進行垃圾收集，可是對象關系圖并非獨立所帶來的問題。這里以跨代引用為例子）。因此，我們有必要了解虛擬機是如何解決這個問題的。

記憶集是一種用于記錄從非收集區域指向收集區域的指針集合的抽象數據結構。

最簡單的實現方式如下：

Class RememberedSet {
 Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE];
}

這種記錄全部含跨代引用對象的實現方案，無論是空間占用還是維護成本都相當高。而在垃圾收集的場景中，收集器只需要通過記憶集判斷出某一塊非收集區域是否存在指向收集區域的指針即可。因此，設計記憶集時，可以選擇記錄精度更粗的實現方式來節省記憶集的存儲成本和維護成本，具體如下：

• 字長精度

每個記錄精確到機器字長（處理器的尋址位數），該字包含跨代指針。

• 對象精度

每個記錄精確到一個對象，該對象里有字段含有跨代指針。

• 卡精度

每個記錄精確到一塊內存區域，該區域內有對象含有跨代指針。

“卡精度” 所指的是用一種稱為“卡表”（Card Table）的方式去實現記憶集，這也是目前最常用的一種記憶集實現形式。這里需要知道“記憶集”是一種思路，只有一個大概設計方向的數據結構；而“卡表”則是“記憶集”的一種具體實現方案了，它定義了記憶集的記錄精度、堆內存的映射關系等。如果覺得還是難理解它們的關系，那可以簡單理解成 HashMap 與 Map 之間的關系。

HotSpot 是用一個字節數組實現卡表的，變量聲明如下

CARD_TABLE[this address >>9]=1;

CARD_TABLE 的每個元素都對應著一塊特定大小的內存塊，這個內存塊被稱作 “卡頁”。看上面代碼可知 HotSpot 中使用的卡頁是 2 的 9 次冪，即 512 字節，如下圖：

一個卡頁內往往有許多對象，只要卡頁內有對象的字段存在著跨代指針，那就將該卡頁對應的卡表元素標識為1，稱為這個元素變臟，沒有則標識為0。垃圾收集時，只要篩選卡表中變臟的元素對應卡頁中的對象加入 GC Root 中一起掃描即可。

寫屏障

我們已經用記憶集來縮減 GC Roots 掃描范圍的問題，但還沒有解決卡表元素如何維護的問題，例如：何時變臟、誰來讓它們變臟等等。

卡表元素何時變臟？有其他分代區域中對象引用了本區域對象時，其對應的卡表元素就應該變臟，變臟時間點原則上應該發生在引用類型字段賦值的那一刻。那么要如何才能在對象賦值的那一刻去更新維護卡表呢？垃圾收集在編譯執行的場景中發生，這里需要面對的是機器指令流。這就需要從機器碼層面去把維護卡表的動作放到每一個賦值的操作之中。

HotSpot 是通過寫屏障（Write Barrier）技術維護卡表的。

這個寫屏障可不是我們學習并發時說的“內存屏障”，千萬不要混淆。

寫屏障解決問題的思想類似Spring 的 AOP，在引用對象賦值這個動作做了一個切面，在對象賦值動作的前后做技術處理。在賦值前執行的部分叫“寫前屏障”（Pre-Write Barrier），在賦值后的部分邏輯則稱為“寫后屏障”（Post-Write Barrier）。

冷門小知識：在 G1 出現之前，其他收集器都只用了寫后屏障。

應用寫屏障后，虛擬機就會為所有賦值操作生成相應的指令，一旦收集器在寫屏障中增加了更新卡表操作，無論更新的是不是老年代對新生代的引用，每次只要對引用進行更新，就會產生額外的開銷，不過這個開銷與 Minor GC 時掃描整個老年代的代價相比還是低得多。

實際上，卡表除了寫屏障這個額外開銷以外，在高并發的場景下還有“偽共享”問題。現代 CPU 的緩存行大小一般為 64 字節。而我們卡表一個元素是一個字節，假設有 64 個卡表元素共享了一個緩存行，那么這 64 個卡表元素映射的32KB（64 * 512 字節）內存里的對象被不同線程更新時，就會導致更新卡表時因為是用了同一個緩存行而導致性能降低。

為了提升性能，在更新卡表元素狀態前，要先判斷下狀態是否已經“臟”了，只有還是“干凈”的元素需要更改狀態，這個叫有條件更新卡表，我們可以通過 -XX:+UseCondCardMark 來選擇是“有條件更新卡表”，還是“無條件更新卡表”。

PS：具體是開啟“有條件更新卡表”更好，還是使用“無條件更新卡表”更好，需要根據自己應用進行實測來判斷。

并發的可達性分析，三色標記算法

眾所周知，當前主流的垃圾收集器基本上都是依靠可達性分析算法來判斷對象是否存活，可達性分析算法理論上要求全過程都基于一個能保障一致性的快照中才進行分析，這意味著“Stop the World”。根節點枚舉這個步驟在 OopMap 的優化技巧下，它所需要的停頓時間已經非常短暫且相對固定（不隨堆容量而增長）了。可是從 GC Roots 往下遍歷對象圖，這一步驟的停頓時間勢必與堆容量成正比關系——堆的對象越多，對象圖越復雜，標記對象所產生的停頓時間越長。

“標記”階段是所有追蹤式垃圾收集算法的共同特征，如果這個階段會隨堆變大而等比例增加停頓時間，那么采用這類型算法的垃圾收集器都會被詬病。因此，如果能夠削減這部分的停頓時間的話，那么帶來的收益也將會是巨大的。

為了降低用戶線程的停頓問題，出現了三色標記算法。三色標記算法通過將垃圾回收過程拆分為多個小步驟，使得垃圾回收器和應用程序可以交替執行（也就是支持并發執行），從而減少垃圾回收對應用程序運行的影響，增強了實時性和響應性。

三色標記算法顧名思義，它定義了三種顏色，如下：

• 白色

表示對象尚未被垃圾收集器訪問過。

• 黑色

表示對象已經被垃圾收集器訪問過，而且其子對象也掃描完成（因此黑色對象不可能沒有關聯灰色對象直接指向白色對象），屬于存活對象。

• 灰色

表示對象已經被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過。三色標記算法的執行過程如下：

1.初始化階段

• 所有對象最初都標記為白色。
• 根對象標記為灰色，并將其放入一個待處理集合（通常是隊列或棧）。

2.標記階段

• 從灰色對象集合中取出一個對象，將其標記為黑色，并將該對象引用的所有白色子對象標記為灰色，并加入灰色對象集合。
• 重復上述過程，直到灰色對象集合為空。

3.清除階段

• 當標記階段完成后，所有仍為白色的對象即為垃圾對象，可以被回收。

要支持并發執行，要注意不能誤刪存活對象，否則就是一個嚴重 Bug。Wilson 于 1940 年在理論上證明了，當且僅當以下兩個條件同時滿足時，會產生誤刪問題：

• 賦值器插入了一條或者多條從黑色對象到白色對象的新引用。
• 賦值器刪除了全部從灰色對象到某白色對象的直接或間接引用。

因此，要解決誤刪問題，只需要破壞上述任一條件即可。由此分別產生了兩種解決方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

• 增量更新是破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關系時，就將這個新插入的引用記錄下來，等并發掃描結束后，再將這些記錄過的引用關系中的黑色對象為根，重新掃描一次。
• 原始快照是破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關系時，就將這個要刪除的引用記錄下來，在并發掃描結束后，再將這些記錄過的引用關系中的灰色對象為根，重新掃描一次。

以上兩種方案都是通過寫屏障實現的。在 HotSpot 中，這兩種方案都有實際的應用，比如 CMS 就是基于增量更新來做并發標記的，G1 和 Shenandoah 則是使用原始快照來實現的。

總結

這里對上面的知識點進行簡單的總結。

• 安全區域

解決何時可以開始垃圾收集（必須 Stop the world 的行為）。

• 記憶集

解決 GC Roots 掃描范圍問題。

• 寫屏障

解決卡表維護問題。

至此，各位對垃圾收集實現的細節應該比較清楚了，想更深入了解就需要結合實際的垃圾收集器的實現來學習了。

作者介紹

蔡柱梁，51CTO社區編輯，從事Java后端開發8年，做過傳統項目廣電BOSS系統，后投身互聯網電商，負責過訂單，TMS，中間件等。