揭開IBM Java JVM GC實(shí)現(xiàn)的神秘內(nèi)幕
按照Sam Borman的說法IBM java 1.3.0的GC是HotSpot的2倍，如果在多對(duì)稱架構(gòu)中性能更加的高。IBM Java JVM如何做到高性能的GC的呢？我把他們的這篇2萬多字的文章濃縮一下介紹給大家。
IBM JVM的GC分為三個(gè)步驟，Mark phase(標(biāo)記),Sweep phase(清掃),Compaction phase(內(nèi)存緊縮). 在了解這些過程之前，我們先看一下IBM Java JVM中的對(duì)象的Layout和Heap lay out
一個(gè)Java對(duì)象在IBM Java JVM中的結(jié)構(gòu)如下
1.size+flags
2.mptr
3.locknflags
4.objectdata
size+flags
這是一個(gè)4byte的slot(32 平臺(tái))。這個(gè)slot的主要功能就是描述對(duì)象的尺寸。
由于IBM Java中的對(duì)象都是以8byte的倍數(shù)分配的，因此對(duì)象的尺寸其實(shí)就是真實(shí)尺寸/8存放在4byte的slot中。另外在這個(gè)slot的低三位是保留字段起到標(biāo)記對(duì)象的作用。他們分別為bit1:swapped bit，這個(gè)交換位被用于Compaction phase即內(nèi)存緊縮階段使用。同時(shí)這一位在標(biāo)記堆棧溢出的時(shí)候（mark stack overflow)也被用于標(biāo)記NotYetScanned狀態(tài).bit2：dosed bit.這個(gè)位用于標(biāo)示這個(gè)對(duì)象是否被某個(gè)堆棧或者寄存器reference到了。如果這個(gè)標(biāo)志被至位則這個(gè)對(duì)象就不能在當(dāng)前的GC cycle中被刪除。而且如果某個(gè)reference指向的內(nèi)存不是一個(gè)真實(shí)的reference比如是一個(gè)簡單的float 或者integer變量但是它的值恰巧就是Heap中某個(gè)Object的地址的時(shí)候，我們就不能修改這個(gè)refernece。這種對(duì)象的bit2也被置為1。bit3:pinned bit。標(biāo)記一個(gè)對(duì)象是否是一個(gè)一個(gè)釘扣對(duì)象(PINNED object)。一個(gè)Pinned Object也不能被GC刪除，因?yàn)樗麄兛赡茉贖eap之外被reference到了。典型的一個(gè)例子就是Thread，還記得我上面說的僵死縣城么？它不能被刪除的道理就是這個(gè)。另外一種PinnedObject就是 JNI Object，即被本地代碼使用的對(duì)象。
Mptr:
在32平臺(tái)上也是4byte的slot。Mptr有兩個(gè)功能，
1。如果mptr不是一個(gè)數(shù)組，則Mptr指向一個(gè)方法塊(method block)，你可以通過這個(gè) method block來得到一個(gè)類塊(class block)。這個(gè)類塊，告訴你這個(gè)Object是屬于哪個(gè)class的實(shí)例。method block和class block由Class Loader分配，而不是heap在heap中進(jìn)行分配
2。如果mptr是一個(gè)數(shù)組(Array)，mptr包含了這個(gè)對(duì)象中，數(shù)組的元素個(gè)數(shù)。
lockflags
在32平臺(tái)上也是4byte的slot，但是這個(gè)slot只有低4位被用到。
bit2:是array flag.如果這個(gè)位被置位，那么這個(gè)對(duì)象就是一個(gè)數(shù)組同時(shí)mptr字段就包含了數(shù)組的元素個(gè)數(shù)。bit4是hashed和moved bit.如果這個(gè)位被置位，那么他就告訴我們這個(gè)對(duì)象在被hashed以后被刪除了。
Object Data：
就是這個(gè)對(duì)象本身的數(shù)據(jù)
Heap layout:
heap top
heap limit
heap base
heap base是heap的起始地址，heap top是heap的結(jié)束地址。heaplimit 是當(dāng)前程序使用的那段heap可以進(jìn)行擴(kuò)展和收縮的極限。你可以用-Xmx參數(shù)在java運(yùn)行的時(shí)候?qū)eap top和heap base進(jìn)行控制。
Alloc bits 和 mark bits
heap top allocmax markemax
heap limit alloc size marksize
heap base
上面這個(gè)結(jié)構(gòu)描述了heap和alloc bits 以及,markbits之間的關(guān)系。allocbits和markbits都是元素為1個(gè)bit的vector。他們與heap有同樣的長度，下面是兩個(gè)對(duì)象被分配以后在heap和兩個(gè)vector中的表現(xiàn)
- heaptop allocmax markmax
- heaplimit allocsize marksize
- object2top
- .
- .
- object2base object2allocbit object2markbit
- object1top
- .
- object1base object1allocbit
如上面的結(jié)構(gòu)，如果一個(gè)對(duì)象在heap被alloc出來，那么在allocbits中就標(biāo)示出這個(gè)對(duì)象的起始地址
所在的地址。allocbits中只標(biāo)記起始地址。但是這個(gè)過程告訴我們這個(gè)對(duì)象在那里被創(chuàng)建，但是不告訴我們這個(gè)對(duì)象是否存活。
當(dāng)在mark phase中如果某一個(gè)對(duì)象比如object2仍然存活，那么就在markbits中對(duì)應(yīng)的地址上標(biāo)記一下
The free list
IBM Java JVM中的空閑塊用用一個(gè)free list鏈標(biāo)示。如圖
freechunck1 freechunck2 freechunckn
size size size
next------------->next--->.........next--->NULL
freeStorage freeStorage freestorge
有了這些基本概念我們來看看Mark phase的工作情況
MarkPhase
GC的Mark phase將標(biāo)記所有還活著的對(duì)象。這個(gè)標(biāo)記所有可達(dá)對(duì)象的過程稱為tracing。Jvm的活動(dòng)狀態(tài)（active state)是由下面幾個(gè)部分組成的。1.每個(gè)線程的保存寄存器(saved registers)2.描述線程的堆棧3.Java類中的靜態(tài)元素3.以及局部和全局的JNI(Java Native Interface)引用。在Jvm中的方法調(diào)用都在C Stack上引發(fā)一個(gè)Frame。這個(gè)Frame包含了，對(duì)象實(shí)例，為局部變量的assignment結(jié)果或者傳入方法的參數(shù)。所有這些引用在Tracing過程中都被同等對(duì)待。實(shí)際上，我們可以把一個(gè)線程的堆棧看城一系列4-bytes slot的集合，然后對(duì)每一個(gè)堆棧都從頂向下對(duì)這些slot進(jìn)行掃描。在掃描的過程中都必須校驗(yàn)每個(gè)slot是否指向heap當(dāng)中的一個(gè)真實(shí)的對(duì)象。
因?yàn)樵谇懊嫖揖驼f過，很有可能這些slot值僅僅是一個(gè)int或float但是他們的值恰巧就等于heap中的一個(gè)對(duì)象地址。因此在掃描的時(shí)候必須相當(dāng)?shù)谋Ｊ兀瑨呙璧臅r(shí)候必須保證所有的指針都是一個(gè)對(duì)象，而且這個(gè)對(duì)象沒有在GC中被刪除。只有符合下面條件的slot才是一個(gè)指向?qū)ο蟮闹羔槨?.必須以8-byte的倍數(shù)分配的內(nèi)存2.必須在heap的范圍之內(nèi)(即大于heapbase小于heaptop)3.對(duì)應(yīng)的allocbit必須置為1。滿足這些條件的對(duì)象引用我們稱為roots，并且把他們的dosed bit置為1表示不能被GC刪除。我想大家已經(jīng)知道C#中為何連Int和Float都是OBject的原因了吧。在C#中因?yàn)槎际荗Bject因此，在tracing的過程中就減少了一次校驗(yàn)。這個(gè)減少對(duì)性能起到很大的影響。 如果掃描完成，那么Tracing過程便能安全精確的執(zhí)行。也就是說我們可以在roots中通過reference找到他對(duì)應(yīng)的objects，由于他們是真實(shí)的reference，那么我們就能夠在compactionphase中移動(dòng)對(duì)應(yīng)的對(duì)象并且修改這些reference。
Trace過程使用了一個(gè)可以容納4k的slots的stack。所有的引用逐個(gè)push進(jìn)入這個(gè)堆棧并且同時(shí)在markbits中進(jìn)行標(biāo)記。當(dāng)push和mark的工作完成之后，我們開始pop出這些slot并且進(jìn)行trace。
常規(guī)的對(duì)象(非數(shù)組對(duì)象)將通過mptr去訪問classblock，classblock將會(huì)告訴我們從這個(gè)對(duì)象中找到的其他對(duì)象的reference在那里？當(dāng)我們?cè)赾lassblock找到一個(gè)refernce以后，如果發(fā)現(xiàn)他沒有被mark，那么我們就在markallocbits中mark他然后把他再壓入堆棧。
數(shù)組對(duì)象利用mptr去訪問每個(gè)數(shù)組元素，如果他們沒有mark則mark然后壓入堆棧。
Trace過程一直持續(xù)進(jìn)行，直到堆棧為空。
MarkStack OverFlow
由于markStack限制了尺寸，因此它可能會(huì)溢出。如果溢出發(fā)生，那么我們就設(shè)定一個(gè)全局的標(biāo)志來表明發(fā)生了MarkStack OverFlow,然后我們將那些不能push入stack的OBject的bit1設(shè)定為NotYetScanned。然后當(dāng)tracing過程完成以后，檢驗(yàn)全局標(biāo)志如果發(fā)現(xiàn)有overflow則把NotYetScanned的對(duì)象再次壓入堆棧開始新的tracing過程。
并行Mark(Parallel Mark)
由于使用逐位清掃(bitwise sweep)和內(nèi)存緊縮規(guī)避功能，GC將化大部分的時(shí)間是用于Mark而非前面兩項(xiàng)。這就導(dǎo)致了IBM JVM需要開發(fā)一個(gè)GC的并行版本。并行GC的目的不是以犧牲單CPU系統(tǒng)上的效能來換取在4，8路對(duì)稱CPU系統(tǒng)上的高效率。
并行Mark的基本思想就是通過多個(gè)輔助線程(helper thread)和一個(gè)共享工作的工具來減少M(fèi)arking的時(shí)間。在單CPU系統(tǒng)中，執(zhí)行GC工作的只有一個(gè)主線程。Parallel mark仍然需要這個(gè)主線程的參與，他充當(dāng)了管理協(xié)調(diào)的角色。這個(gè)Thread所要執(zhí)行的工作和單CPU上的一樣多，包括他必須掃描C-Stack來鑒別需要收集的roots指針。一個(gè)有N路對(duì)稱CPU的系統(tǒng)自動(dòng)含有n-1個(gè)helper thread并且平均分布在每個(gè)CPU上，master thread將scan完的reference集合進(jìn)行分塊，然后交給helper thread獨(dú)立完成mark工作。
每個(gè)Helper thread都被分配了一個(gè)獨(dú)立的本地mark stack，以及一個(gè)shareable queue。sharqueue將存放help thread在mark overflow的時(shí)候的NotyetScanned對(duì)象。然后由master thread將sharequeue中的對(duì)象balance到其他已經(jīng)空閑的thread上去。
并發(fā)Mark(Concurrent mark)
Concurrent mark的主要目的在于當(dāng)heap增長的時(shí)候減少GC的pause time。只要heap到達(dá)heap limit的時(shí)候，Concurrent mark就會(huì)被執(zhí)行。在Concurrent phase中，GC要求應(yīng)用中的每個(gè)線程(不是指helper thread而是應(yīng)用程序自己開啟的線程以便充分利用系統(tǒng)資源)掃描他們自己的堆棧來得到roots。然后使用這些roots來同步的trace 可達(dá)對(duì)象。Tracing工作是由一個(gè)后臺(tái)的低優(yōu)先級(jí)的線程執(zhí)行，同時(shí)程序自己開啟的線程在分配內(nèi)存的時(shí)候必須執(zhí)行heap lock allocation。
由于使用程序自己開啟的線程并發(fā)的執(zhí)行mark live objects，我們必須紀(jì)錄那些已經(jīng)trace過的object的變化。這個(gè)功能是采用一個(gè)叫寫閘(write barrier) 來實(shí)現(xiàn)的。這個(gè)寫閘在每次改變引用的時(shí)候被激活。它告訴我們什么時(shí)候一個(gè)對(duì)象被跟新過了，以便我們從新掃描那部分heap。寫閘的具體實(shí)現(xiàn)是Heap會(huì)分配出512byte的內(nèi)存段每個(gè)段都分配了一個(gè)byte在卡表中(card table)。無論何時(shí)一個(gè)對(duì)象的reference被更新cardtable將同步紀(jì)錄這個(gè)對(duì)象的起始地址。使用Byte而不用bit的原因是寫byte要比寫bit快2倍，而且我們可能希望空余的bit會(huì)在未來被用到。
當(dāng)Concurrent mark執(zhí)行完畢以后，STW collection(stop total world)將會(huì)被執(zhí)行。stw的意思是指suspend所有程序自己開啟的線程。因此我們可以看到如果使用Concurrent mark那么在mark的時(shí)候應(yīng)用程序不會(huì)完全停止。只有收集需要進(jìn)行collection時(shí)以后才執(zhí)行stw。在上面的討論中我們認(rèn)為STW的mark,sweep,compaction可能會(huì)暫停應(yīng)用程序很長時(shí)間。其實(shí)IBM的gc的停止比我們想象中要短的多。STW只有在下面這些條件才執(zhí)行1.到達(dá)heap limited或者allocation fail2.System.gc方法被調(diào)用3.Concurrent mark 完成所有的工作因此我們可以通過調(diào)整系統(tǒng)參數(shù)來控制STW的執(zhí)行。當(dāng)STW執(zhí)行之前，會(huì)掃描卡表檢查那些heap需要從新trace，然后執(zhí)行通常的sweep。
Concurrent mark帶來的好處就是減少STW所帶來的停頓時(shí)間。但是這也需要程序自己開啟的線程付出一定的代價(jià)。這個(gè)代價(jià)就是需要執(zhí)行heap lock allocation。這個(gè)代價(jià)的大小主要取決于CPU有多少超標(biāo)量流水是空閑的。在Sun的HotSpot中仍然使用單個(gè)GC線程進(jìn)行全部的mark工作，因此IBMJava的GC要快的多而且有跟少的延遲。
Sweep phase
執(zhí)行完mark以后就執(zhí)行sweep。sweep phase其實(shí)是最有趣的一個(gè)階段，在我們上面的討論中一個(gè)比較尖銳的問題是GC控制對(duì)象的生存情況是否必要。這個(gè)在Sun的Java中可能存在，但是在IBMjava中GC根本不知道什么時(shí)候sweep了一個(gè)對(duì)象，甚至不知道sweep了那個(gè)對(duì)象。
在Sun的HotSpot種的sweep采用了通常的做法就是掃描allocbits和makrbits的交叉項(xiàng)，把那些沒有交叉的內(nèi)存給sweep掉。而在IBM種采用了一種相當(dāng)高效的方法叫bitsweep。這種方法直接在markbits中尋找長時(shí)間不使用的0位（1位代表mark了0位代表空閑或者
需要sweep的內(nèi)存）。一旦找到長時(shí)間不使用的0位，那么我們就去對(duì)照在Heap中對(duì)應(yīng)的地址來決定需要釋放的內(nèi)存。如果空閑的總數(shù)超過512*Header size那么我們就把這個(gè)free塊移到free list中。而那些小的內(nèi)存片則不會(huì)放入free list，因?yàn)樗麄儠?huì)在相鄰的對(duì)象執(zhí)行清除或者compact heap的時(shí)候被一起覆蓋掉。采用了bitsweep以后，GC根本不需要?jiǎng)h除單個(gè)對(duì)象，因?yàn)槲覀冎勒麄€(gè)要?jiǎng)h除的Chunck就是一個(gè)free storge。因此實(shí)際上，我們刪除一個(gè)chunck的時(shí)候我們根本不知道刪除了幾個(gè)對(duì)象以及刪除了那些對(duì)象。清掃完成以后，GC會(huì)把makrbit copy 到 allocbit上，保證所有的對(duì)象的reference都有效。因此myan提到effile中把refernece和本地的object分開處理，其實(shí)對(duì)于gc來說不是一個(gè)好主意。全部依靠reference可以一次清除多個(gè)對(duì)象，而分開處理就必須使用Hotspot的方法降低GC的性能。
Parallel bitwise sweep
IBMJava為了多對(duì)稱系統(tǒng)也設(shè)計(jì)了并行版本的bitwise sweep。其原理和并行Mark一致。
Compaction phase
當(dāng)清掃完畢以后，就開始執(zhí)行compaction。Java的compaction是相當(dāng)復(fù)雜的。因?yàn)橐苿?dòng)一個(gè)對(duì)象，必須修改他們所有的reference。而且如果一個(gè)reference是來自一個(gè)stack，并且我們不能確定它是否指向一個(gè)真實(shí)的object，可能它僅僅是一個(gè)float，那么這些object
就不能被移動(dòng)。一個(gè)對(duì)象是否可以被移動(dòng)設(shè)計(jì)到它的”dosed”位是被置位。同樣pinned object，那些被JNI引用的對(duì)象，只有到Jni unnpined的時(shí)候才能被移動(dòng)。Pinned object的可否移動(dòng)的判斷更加復(fù)雜。主要依賴于mptr低三位標(biāo)示它是否被清掃掉。標(biāo)示被清掃的 的位存在兩個(gè)地方：1. The size + flags 字段，如果被標(biāo)記到OLINK_IsSwapped. 2. mptr 被標(biāo)記到GC_FirstSwapped。因此看來Java把int 這種普通類型和Object分開處理在GC中會(huì)造成過多的不能移動(dòng)的對(duì)象和過多的碎片。對(duì)于GC來說很不明智，而且在其他地方也看不出有什么必要分開處理。
否則干嗎還要做一個(gè)Integer類呢？而C#在這點(diǎn)上來說優(yōu)勢(shì)更大。
IBM java中的Compaction算法為了避免過多的移動(dòng)對(duì)象和利用移動(dòng)處理一些沒有被收集的空閑塊因而出奇的復(fù)雜。他采用了一種和hotspot不同的算法。Sam Borman舉了一個(gè)很形象的例子，把整個(gè)Heap想象成一個(gè)倉庫，倉庫堆放了不同尺寸的家具。由于出庫的原因，家具之間存在著一定的空隙。Compaction的工作就是把家具往一個(gè)方向推來清理空隙。把靠近墻的家具推倒墻邊，然后讓第二個(gè)家具與***件緊靠在一起。以此類推，然后所有得家具靠再一起，而空隙在另外一邊。Pinned and dosed objects 不能被移動(dòng)的情況會(huì)復(fù)雜化這個(gè)算法，但是主要思想不變。
緊縮規(guī)避(Compaction avoidance)
Compaction avoidance的主要目的在于開辟較大內(nèi)存的時(shí)候降低Compaction的使用次數(shù)來保證GC pause time能夠足夠短。在Ibm jvm中的Compaction的執(zhí)行條件如下：
1． 如果開辟一個(gè)大內(nèi)存的時(shí)候遍例Free list發(fā)現(xiàn)沒有合適的free storge激發(fā)alloc failure時(shí)間
2． 在上次GC過程中出現(xiàn)了一次alloc failure
3． 被激活的Heap(heap limited到heap base之間的heap)只有5%為free
4． 被激活的Heap不大于128K
IBM Java JVM在上面四個(gè)條件中滿足一項(xiàng)就執(zhí)行compaction。其中最為常見的是***種，
為了避免Companction，Ibmjava采用了緊縮規(guī)避的方法。這個(gè)方法稱為荒野內(nèi)存(wilderness preservation),也就是在heap limit之上再開辟一塊內(nèi)存。這塊內(nèi)存保持原始狀態(tài)，其大小為激活Heap的5%,默認(rèn)設(shè)置為3M.如果一旦有一個(gè)大塊內(nèi)存需要開辟，而freelist中沒有合適的storge的時(shí)候就使用wilderness preservation保證不拋出 alloc failure。一旦wilderness被用盡則產(chǎn)生一個(gè)alloc failure通知GC執(zhí)行Compaction。通常來說wilderness preservation能夠保證不使用Compaction，因?yàn)榛旧鲜褂玫絯ilderness的對(duì)象是這個(gè)應(yīng)用程序中***的對(duì)象。
IBM的JVM關(guān)鍵實(shí)現(xiàn)就是這樣，我們可以看到IBM Java JVM使用的很多算法讓我們?cè)究紤]的一些gc的困難降低到了一個(gè)可以忍受的限度，比如STW的pause time，其實(shí)只涉及了sweep和compaction，mark phase在程序運(yùn)行的同時(shí)就完成了基本不影響程序的正常工作。而且由于使用了bitsweep,和緊縮規(guī)避使得STW的時(shí)間大大降低，他們兩個(gè)的工作量的總和不到Mark的30%。而且在多對(duì)稱處理器上又采用并行mark和sweep，可以近一部的提高GC效率。好了用了兩個(gè)小時(shí)寫這篇文章真的很累,我把Java的VM的實(shí)現(xiàn)細(xì)節(jié)公布出來，大家談?wù)摼汀庇械姆潘痢绷税伞?
【編輯推薦】
