JVM 三色標(biāo)記法與讀寫(xiě)屏障
本文轉(zhuǎn)載自微信公眾號(hào)「運(yùn)維開(kāi)發(fā)故事」，作者老鄭。轉(zhuǎn)載本文請(qǐng)聯(lián)系運(yùn)維開(kāi)發(fā)故事公眾號(hào)。
三色標(biāo)記法
GC 垃圾回收器其主要的目的是為了實(shí)現(xiàn)內(nèi)存的回收，在這個(gè)過(guò)程中主要的兩個(gè)步驟就是：內(nèi)存標(biāo)記，內(nèi)存回收。
三色標(biāo)記法簡(jiǎn)介
三色標(biāo)記法，主要是為了高效的標(biāo)記可被回收的內(nèi)存塊。
三色標(biāo)記(Tri-color Marking)作為工具來(lái)輔助推導(dǎo)，把遍歷對(duì)象圖過(guò)程中遇到的對(duì)象，按照“是否訪問(wèn)過(guò)”這個(gè)條件標(biāo)記成以下三種顏色：
- 白色：表示對(duì)象尚未被垃圾收集器訪問(wèn)過(guò)。顯然在可達(dá)性分析剛剛開(kāi)始的階段，所有的對(duì)象都是白色的，若在分析結(jié)束的階段，仍然是白色的對(duì)象，即代表不可達(dá)。
- 黑色：表示對(duì)象已經(jīng)被垃圾收集器訪問(wèn)過(guò)，且這個(gè)對(duì)象的所有引用都已經(jīng)掃描過(guò)。黑色的對(duì)象代 表已經(jīng)掃描過(guò)，它是安全存活的，如果有其他對(duì)象引用指向了黑色對(duì)象，無(wú)須重新掃描一遍。黑色對(duì) 象不可能直接(不經(jīng)過(guò)灰色對(duì)象)指向某個(gè)白色對(duì)象。
- 灰色：表示對(duì)象已經(jīng)被垃圾收集器訪問(wèn)過(guò)，但這個(gè)對(duì)象上至少存在一個(gè)引用還沒(méi)有被掃描過(guò)。
三色標(biāo)記過(guò)程
標(biāo)記過(guò)程：
- 在 GC 并發(fā)開(kāi)始的時(shí)候，所有的對(duì)象均為白色;
- 在將所有的 GC Roots 直接應(yīng)用的對(duì)象標(biāo)記為灰色集合;
- 如果判斷灰色集合中的對(duì)象不存在子引用，則將其放入黑色集合，若存在子引用對(duì)象，則將其所有的子引用對(duì)象存放到灰色集合，當(dāng)前對(duì)象放入灰色集合
- 按照此步驟 3 ，依此類推，直至灰色集合中所有的對(duì)象變黑后，本輪標(biāo)記完成，并且在白色集合內(nèi)的對(duì)象稱為不可達(dá)對(duì)象，即垃圾對(duì)象。
- 標(biāo)記結(jié)束后，為白色的對(duì)象為 GC Roots 不可達(dá)，可以進(jìn)行垃圾回收。
誤標(biāo)
什么是誤標(biāo)?當(dāng)下面兩個(gè)條件同時(shí)滿足，會(huì)產(chǎn)生誤標(biāo)：
賦值器插入了一條或者多條黑色對(duì)象到白色對(duì)象的引用
賦值器刪除了全部從灰色對(duì)象到白色對(duì)象的直接引用或者間接引用
誤標(biāo)的解決方案
要解決誤標(biāo)的問(wèn)題，只需要破壞這兩個(gè)條件中的任意一種即可，分別有兩種解決方案：增量更新(Incremental Update) 和原始快照(Snapshot At The Beginning, STAB)
增量更新
增量更新要破壞的是第一個(gè)條件，當(dāng)黑色對(duì)象插入新的指向白色對(duì)象的引用關(guān)系時(shí)，就將這個(gè)新插入的引用記錄下來(lái)，等并發(fā)掃描結(jié)束之后，再將這些記錄過(guò)的引用關(guān)系中的黑色對(duì)象為根，重新掃描一次。這可以簡(jiǎn)化理解為，黑色對(duì)象一旦新插入了指向白色對(duì)象的引用之后，它就變回灰色對(duì)象 了。
原始快照 (STAB)
原始快照要破壞的是第二個(gè)條件，當(dāng)灰色對(duì)象要?jiǎng)h除指向白色對(duì)象的引用關(guān)系時(shí)，就將這個(gè)要?jiǎng)h 除的引用記錄下來(lái)，在并發(fā)掃描結(jié)束之后，再將這些記錄過(guò)的引用關(guān)系中的灰色對(duì)象為根，重新掃描 一次。這也可以簡(jiǎn)化理解為，無(wú)論引用關(guān)系刪除與否，都會(huì)按照剛剛開(kāi)始掃描那一刻的對(duì)象圖快照來(lái)進(jìn)行搜索。
漏標(biāo)和多標(biāo)
對(duì)于錯(cuò)標(biāo)其實(shí)細(xì)分出來(lái)會(huì)有兩種情況，分別是：漏標(biāo)和多標(biāo)
多標(biāo)-浮動(dòng)垃圾
如果標(biāo)記執(zhí)行到 E 此刻執(zhí)行了 object.E = null
在這個(gè)時(shí)候， E/F/G 理論上是可以被回收的。但是由于 E 已經(jīng)變?yōu)榱嘶疑耍敲此蜁?huì)繼續(xù)執(zhí)行下去。最終的結(jié)果就是不會(huì)將他們標(biāo)記為垃圾對(duì)象，在本輪標(biāo)記中存活。在本輪應(yīng)該被回收的垃圾沒(méi)有被回收，這部分被稱為“浮動(dòng)垃圾”。浮動(dòng)垃圾并不會(huì)影響程序的正確性，這些“垃圾”只有在下次垃圾回收觸發(fā)的時(shí)候被清理。還有在，標(biāo)記過(guò)程中產(chǎn)生的新對(duì)象，默認(rèn)被標(biāo)記為黑色，但是可能在標(biāo)記過(guò)程中變?yōu)?ldquo;垃圾”。這也算是浮動(dòng)垃圾的一部分。
漏標(biāo)-讀寫(xiě)屏障
寫(xiě)屏障(Store Barrier)
給某個(gè)對(duì)象的成員變量賦值時(shí)，其底層代碼大概長(zhǎng)這樣：
- /**
- * @param field 某個(gè)對(duì)象的成員屬性
- * @param new_value 新值，如：null
- */
- void oop_field_store(oop* field, oop new_value) {
- *fieild = new_value // 賦值操作
- }
所謂寫(xiě)屏障，其實(shí)就是在賦值操作前后，加入一些處理的邏輯(類似 AOP 的方式)
- void oop_field_store(oop* field, oop new_value) {
- pre_write_barrier(field); // 寫(xiě)屏障-寫(xiě)前屏障
- *fieild = new_value // 賦值操作
- pre_write_barrier(field); // 寫(xiě)屏障-寫(xiě)后屏障
- }
寫(xiě)屏障 + SATB
當(dāng)對(duì)象E的成員變量的引用發(fā)生變化時(shí)(objE.fieldG = null;)，我們可以利用寫(xiě)屏障，將E原來(lái)成員變量的引用對(duì)象G記錄下來(lái)：
- void pre_write_barrier(oop* field) {
- oop old_value = *field; // 獲取舊值
- remark_set.add(old_value); // 記錄 原來(lái)的引用對(duì)象
- }
【當(dāng)原來(lái)成員變量的引用發(fā)生變化之前，記錄下原來(lái)的引用對(duì)象】 這種做法的思路是：嘗試保留開(kāi)始時(shí)的對(duì)象圖，即原始快照(Snapshot At The Beginning，SATB)，當(dāng)某個(gè)時(shí)刻 的GC Roots確定后，當(dāng)時(shí)的對(duì)象圖就已經(jīng)確定了。比如 當(dāng)時(shí) D是引用著G的，那后續(xù)的標(biāo)記也應(yīng)該是按照這個(gè)時(shí)刻的對(duì)象圖走(D引用著G)。如果期間發(fā)生變化，則可以記錄起來(lái)，保證標(biāo)記依然按照原本的視圖來(lái)。值得一提的是，掃描所有GC Roots 這個(gè)操作(即初始標(biāo)記)通常是需要STW的，否則有可能永遠(yuǎn)都掃不完，因?yàn)椴l(fā)期間可能增加新的GC Roots。
SATB破壞了條件一：【灰色對(duì)象 斷開(kāi)了 白色對(duì)象的引用】，從而保證了不會(huì)漏標(biāo)。
一點(diǎn)小優(yōu)化：如果不是處于垃圾回收的并發(fā)標(biāo)記階段，或者已經(jīng)被標(biāo)記過(guò)了，其實(shí)是沒(méi)必要再記錄了，所以可以加個(gè)簡(jiǎn)單的判斷：
- void pre_write_barrier(oop* field) {
- // 處于GC并發(fā)標(biāo)記階段 且 該對(duì)象沒(méi)有被標(biāo)記（訪問(wèn)）過(guò)
- if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
- oop old_value = *field; // 獲取舊值
- remark_set.add(old_value); // 記錄 原來(lái)的引用對(duì)象
- }
- }
寫(xiě)屏障 + 增量更新
當(dāng)對(duì)象D的成員變量的引用發(fā)生變化時(shí)(objD.fieldG = G;)，我們可以利用寫(xiě)屏障，將D新的成員變量引用對(duì)象G記錄下來(lái)：
- void post_write_barrier(oop* field, oop new_value) {
- if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
- remark_set.add(new_value); // 記錄新引用的對(duì)象
- }
- }
【當(dāng)有新引用插入進(jìn)來(lái)時(shí)，記錄下新的引用對(duì)象】 這種做法的思路是：不要求保留原始快照，而是針對(duì)新增的引用，將其記錄下來(lái)等待遍歷，即增量更新(Incremental Update)。
增量更新破壞了條件二：【黑色對(duì)象 重新引用了 該白色對(duì)象】，從而保證了不會(huì)漏標(biāo)。
讀屏障(Load Barrier)
- oop oop_field_load(oop* field) {
- pre_load_barrier(field); // 讀屏障-讀取前操作
- return *field;
- }
讀屏障直接針對(duì)第一步 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); // 記錄讀取到的對(duì)象
- }
- }
- 這種做法是保守的
這種做法是保守的，但也是安全的。因?yàn)闂l件二中【黑色對(duì)象 重新引用了 該白色對(duì)象】，重新引用的前提是：得獲取到該白色對(duì)象，此時(shí)已經(jīng)讀屏障就發(fā)揮作用了。
三色標(biāo)記法與垃圾回收器
增量更新：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 虛擬機(jī)-第三版》周志明
