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