JVM 三色標記法與讀寫屏障
本文轉載自微信公眾號「運維開發故事」，作者老鄭。轉載本文請聯系運維開發故事公眾號。
三色標記法
GC 垃圾回收器其主要的目的是為了實現內存的回收，在這個過程中主要的兩個步驟就是：內存標記，內存回收。
三色標記法簡介
三色標記法，主要是為了高效的標記可被回收的內存塊。
三色標記(Tri-color Marking)作為工具來輔助推導，把遍歷對象圖過程中遇到的對象，按照“是否訪問過”這個條件標記成以下三種顏色：
- 白色：表示對象尚未被垃圾收集器訪問過。顯然在可達性分析剛剛開始的階段，所有的對象都是白色的，若在分析結束的階段，仍然是白色的對象，即代表不可達。
- 黑色：表示對象已經被垃圾收集器訪問過，且這個對象的所有引用都已經掃描過。黑色的對象代 表已經掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對 象不可能直接(不經過灰色對象)指向某個白色對象。
- 灰色：表示對象已經被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過。
三色標記過程
標記過程：
- 在 GC 并發開始的時候，所有的對象均為白色;
- 在將所有的 GC Roots 直接應用的對象標記為灰色集合;
- 如果判斷灰色集合中的對象不存在子引用，則將其放入黑色集合，若存在子引用對象，則將其所有的子引用對象存放到灰色集合，當前對象放入灰色集合
- 按照此步驟 3 ，依此類推，直至灰色集合中所有的對象變黑后，本輪標記完成，并且在白色集合內的對象稱為不可達對象，即垃圾對象。
- 標記結束后，為白色的對象為 GC Roots 不可達，可以進行垃圾回收。
誤標
什么是誤標?當下面兩個條件同時滿足，會產生誤標：
賦值器插入了一條或者多條黑色對象到白色對象的引用
賦值器刪除了全部從灰色對象到白色對象的直接引用或者間接引用
誤標的解決方案
要解決誤標的問題，只需要破壞這兩個條件中的任意一種即可，分別有兩種解決方案：增量更新(Incremental Update) 和原始快照(Snapshot At The Beginning, STAB)
增量更新
增量更新要破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關系時，就將這個新插入的引用記錄下來，等并發掃描結束之后，再將這些記錄過的引用關系中的黑色對象為根，重新掃描一次。這可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之后，它就變回灰色對象 了。
原始快照 (STAB)
原始快照要破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關系時，就將這個要刪 除的引用記錄下來，在并發掃描結束之后，再將這些記錄過的引用關系中的灰色對象為根，重新掃描 一次。這也可以簡化理解為，無論引用關系刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進行搜索。
漏標和多標
對于錯標其實細分出來會有兩種情況，分別是：漏標和多標
多標-浮動垃圾
如果標記執行到 E 此刻執行了 object.E = null
在這個時候， E/F/G 理論上是可以被回收的。但是由于 E 已經變為了灰色了，那么它就會繼續執行下去。最終的結果就是不會將他們標記為垃圾對象，在本輪標記中存活。在本輪應該被回收的垃圾沒有被回收，這部分被稱為“浮動垃圾”。浮動垃圾并不會影響程序的正確性，這些“垃圾”只有在下次垃圾回收觸發的時候被清理。還有在，標記過程中產生的新對象，默認被標記為黑色，但是可能在標記過程中變為“垃圾”。這也算是浮動垃圾的一部分。
漏標-讀寫屏障
寫屏障(Store Barrier)
給某個對象的成員變量賦值時，其底層代碼大概長這樣：
- /**
- * @param field 某個對象的成員屬性
- * @param new_value 新值，如：null
- */
- void oop_field_store(oop* field, oop new_value) {
- *fieild = new_value // 賦值操作
- }
所謂寫屏障，其實就是在賦值操作前后，加入一些處理的邏輯(類似 AOP 的方式)
- void oop_field_store(oop* field, oop new_value) {
- pre_write_barrier(field); // 寫屏障-寫前屏障
- *fieild = new_value // 賦值操作
- pre_write_barrier(field); // 寫屏障-寫后屏障
- }
寫屏障 + 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)。如果期間發生變化，則可以記錄起來，保證標記依然按照原本的視圖來。值得一提的是，掃描所有GC Roots 這個操作(即初始標記)通常是需要STW的，否則有可能永遠都掃不完，因為并發期間可能增加新的GC Roots。
SATB破壞了條件一：【灰色對象 斷開了 白色對象的引用】，從而保證了不會漏標。
一點小優化：如果不是處于垃圾回收的并發標記階段，或者已經被標記過了，其實是沒必要再記錄了，所以可以加個簡單的判斷：
- void pre_write_barrier(oop* field) {
- // 處于GC并發標記階段 且 該對象沒有被標記（訪問）過
- if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
- oop old_value = *field; // 獲取舊值
- remark_set.add(old_value); // 記錄 原來的引用對象
- }
- }
寫屏障 + 增量更新
當對象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)。
增量更新破壞了條件二：【黑色對象 重新引用了 該白色對象】，從而保證了不會漏標。
讀屏障(Load Barrier)
- oop oop_field_load(oop* field) {
- pre_load_barrier(field); // 讀屏障-讀取前操作
- return *field;
- }
讀屏障直接針對第一步 var objF = object.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); // 記錄讀取到的對象
- }
- }
- 這種做法是保守的
這種做法是保守的，但也是安全的。因為條件二中【黑色對象 重新引用了 該白色對象】，重新引用的前提是：得獲取到該白色對象，此時已經讀屏障就發揮作用了。
三色標記法與垃圾回收器
增量更新：CMS
原始快照(STAB)：G1，Shenandoah
參考文檔
https://www.jianshu.com/p/12544c0ad5c1
https://hllvm-group.iteye.com/group/topic/44381
https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/G1GettingStarted/index.html
https://tech.meituan.com/2016/09/23/g1.html
《深入理解 JVM 虛擬機-第三版》周志明
