JVM HotSpot 可達性分析算法實作細節

根節點枚舉

在之前關于可達性分析算法的介紹中我們講過，我們需要先找出可固定作為 GC Roots 的節點，然後沿着引用鍊去尋找那些無用的垃圾對象。GC Roots 節點一般在全局性引用（例如常量和類靜态屬性）與執行上下文（例如棧幀中的本地變量表）中，盡管目标明确，但查找過程要做到高效并非一件易事，若要逐個查找可作為起源的引用肯定需要消耗不少時間

迄今為止，所有收集器在根節點枚舉這一步驟時都是必須暫停使用者線程，也即 Stop The World，因為如果在分析過程中出現根節點集合中對象的引用關系仍在不斷變化的情況，分析結果的準确性也就無法保證了

在對棧記憶體進行分析時，虛拟機會看哪些位置存儲了 Reference 類型，如果發現某個位置确實存的是 Reference 類型，就意味着它所引用的對象這一次不能被回收。但問題是，棧幀的本地變量表裡面隻有一部分資料是 Reference 類型的，那些非 Reference 類型（基本資料類型）的資料對我們毫無用處，但我們還是不得不對整個棧全部掃描一遍，這是對時間和資源的一種浪費。在 HotSpot 的解決方案中采用了一組稱為 OopMap 的資料結構來實作直接找到對象引用，一旦類加載動作完成，HotSpot 就會把棧中代表引用的位置全部記錄下來，這樣收集器在掃描時就可以直接得知這些消息了

安全點

盡管有了 OopMap，但如果引用關系經常變化，虛拟機就需要為每一條指令都生成對應的 OopMap，這将會占用大量的額外存儲空間

HotSpot 當然沒那麼笨，它隻會在特定的位置去記錄這些資訊，這些位置被稱為安全點（SafePoint）。有了安全點的設定，使用者程式就必須執行到安全點才能暫停，而不是在代碼指令流的任意位置随意停頓。安全點的標明不能太少，讓收集器等待時間過長，也不能太頻繁，導緻增大運作時記憶體負擔。安全點的位置標明基本上是以“是否具有讓程式長時間執行的特征”為标準進行標明，“長時間執行”的最明顯特征就是指令序列的複用，例如方法調用、循環跳轉、異常跳轉等，隻有具有這些功能的指令才能産生安全點

對于安全點，另外一個要考慮的問題就是，如何在垃圾收集發生時讓所有線程都跑到最近的安全點。一般有兩種方案可供選擇：

• 搶先式中斷：垃圾收集發生時，系統首先把所有使用者線程全部中斷，如果發現有使用者線程中斷的地點不在安全點上，就恢複該線程執行，直至跑到安全點再中斷。現實中幾乎沒有虛拟機會采用搶先式中斷
• 主動式中斷：垃圾收集發生時，不直接對線程操作，而是設定一個标志位，各個線程在執行時會不停地主動去輪詢這個标志，一旦發現标志位為真就在最近的安全點主動中斷

安全區域

安全點看似解決了我們遇到的問題，但還有一個需要思考的點：如果某一個使用者線程正好處于“不執行”狀态該怎麼辦？所謂“不執行”就是沒有配置設定處理器時間片，典型的場景如使用者線程處于 Sleep 或 Blocked 狀态，這時線程無法響應中斷請求，自然也就不能走到安全點主動挂起自己，而虛拟機也不可能持續等待線程重新被分處理器時間片。對于這種情況，就需要引入安全區域（Safe Region）來解決

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

當使用者線程執行到安全區域時，首先會辨別自己已經進入安全區域，那樣當這段時間裡虛拟機要發起垃圾收集時就不必去管這些已經聲明自己在安全區域内的線程了。當線程要離開安全區域時，會檢查虛拟機是否已經完成了根節點枚舉，如果完成了，就繼續執行，否則一直等待，直到收到可以離開安全區域的信号為止

記憶集與卡表

之前在講解分代收集理論時，提到為了解決對象跨代引用的問題，垃圾收集器會在新生代建立名為記憶集（Remember Set）的資料結構，避免将整個老年代加入 GC Roots。事實上，所有涉及部分區域收集行為的垃圾收集器都會面臨相同的問題

記憶集是一種用于記錄非收集區域指向收集區域的指針集合的抽象資料結構，最簡單的實作可以是數組，其中存放非收集區域中所有含跨代引用的對象。實際上，收集器隻需要通過記憶集判斷某一塊非收集區域是否存在指向收集區域的指針即可，并不需要了解跨代指針的全部細節，是以我們可以适當選擇更粗犷的記錄粒度：

• 字長精度：每個記錄精确到一個機器字長，該字包含跨代指針
• 對象精度：每個記錄精确到一個對象，該對象裡有字段含跨代指針
• 卡精度：每個記錄精确到一塊記憶體區域，該區域有對象含跨代指針

最常用的是第三種“卡精度”，使用一種稱為“卡表”的方式去實作記憶集。這裡要提的一點是，記憶集隻是一種抽象的資料結構，卡表是記憶集的一種具體實作，兩者的關系可以類比 Java 中的 Map 和 HashMap

卡表最簡單的形式可以是一個位元組數組，HotSpot 虛拟機也确實這麼做了。位元組數組的每一個元素都對應其辨別的記憶體區域中一塊特定大小的記憶體塊，這個記憶體塊稱為“卡頁”。一個卡頁的記憶體通常包含不止一個元素，隻要卡頁内有一個或多個對象的字段存在跨代指針，那就将對應卡表的數組元素辨別為 1，否則為 0。發生垃圾收集時，隻要篩選出卡表中變髒的元素，就能輕易地把它們加入 GC Roots

寫屏障

如何維護卡表元素呢？例如它們何時變髒，誰來把它們變髒等。何時變髒的答案很明顯，隻要有其他分代區域的對象引用了本區域對象，那麼對應的卡表元素就應該變髒，變髒時間點原則上應該發生在引用類型字段指派的那一刻

問題是如何變髒呢？HotSpot 虛拟機是通過寫屏障（Write Barrier）技術來維護卡表狀态的。寫屏障可以看作是虛拟機對“引用類型字段指派”這個動作的 AOP 切面，在引用對象指派時會産生一個環形通知，供程式執行額外的動作。應用寫屏障後，虛拟機就會為所有指派操作生成對應的指令。盡管這個動作也會産生額外開銷，但和 Minor GC 時掃描整個老年代相比根本不值一提

卡表在高并發場景下還會面臨僞共享（False Sharing）問題。現代中央處理器的緩存系統是以緩存行（Cache Line）為機關存儲的，當多線程修改互相獨立的變量，而這些變量恰好共享同一緩存行，則會導緻性能降低。如果所有卡表元素共享同一緩存行，那麼更新時有可能會出現僞共享問題。一種簡單的解決方案是先檢查卡表标記，隻有當該卡表元素未被标記過時才将其标記為變髒

并發的可達性分析

可達性分析算法理論上要求全過程都基于一個能保障一緻性的快照，即必須當機全部使用者線程。在根結點枚舉階段，由于 GC Roots 相比整個 Java 堆的全部對象畢竟還算極少數，且有各種優化技巧（如 OopMap），它帶來的停頓可以說微不足道。但如果從 GC Roots 開始往下周遊對象圖，那麼這一階段的停頓時間必然與 Java 堆容量成正比例關系：堆越大，存儲的對象就越多，對象圖結果越複雜，自然花的時間也越多

是以，部分垃圾收集器是允許使用者線程與收集器線程并發工作的，但如果在收集器标記對象的同時，使用者線程修改了引用關系，就會産生兩種後果：把原本應該消亡的對象錯誤标記為存活；把原本應該存活的對象錯誤标記為消亡。前一種還好一些，不過是産生浮動垃圾罷了，而後一種就非常緻命了，程式肯定會是以發生錯誤。為了更好地說明這個問題，我們按照“是否通路過”為條件将對象标記為以下三種顔色：

• 白色：表示對象尚未被垃圾收集器通路過
• 黑色：表示對象已經被垃圾收集器通路過，且該對象的所有引用都已經被掃描
• 灰色：表示對象已經被垃圾收集器通路過，但該對象至少還有一個引用沒有被掃描

前面提到過的将應該存活的對象錯誤标記為消亡這一現象稱為“對象消失”問題，即原本應該是黑色的對象被誤标為白色，這一問題當且僅當以下兩個條件同時滿足時才會發生：

• 指派器插入一條或多條從黑色對象到白色對象的新引用
• 指派器删除了全部從灰色對象到該白色對象的直接或間接引用

要想解決對象消失問題，隻需破壞這兩個條件的任意一個即可，由此産生了兩種解決方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）

增量更新破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用，就将其記錄下來，等并發掃描結束後，再将記錄過的新引用關系中的黑色對象作為根，重新掃描一次