Dalvik虛擬機Java堆創建過程分析

使用C/C++開發應用程序最令頭痛的問題就是內存管理。慎不留神，要麼內存洩漏，要麼內存破壞。虛擬機要解決的問題之一就是幫助應用程序自動分配和釋放內存。為了達到這個目的，虛擬機在啟動的時候向操作系統申請一大塊內存當作對象堆。之後當應用程序創建對象時，虛擬機就會在堆上分配合適的內存塊。而當對象不再使用時，虛擬機就會將它占用的內存塊歸還給堆。Dalvik虛擬機也不例外，本文就分析它的Java堆創建過程。

在Dalvik虛擬機中，Java堆實際上是由一個Active堆和一個Zygote堆組成的，如圖1所示：

 

 

圖1 Dalvik虛擬機的Java堆

其中，Zygote堆用來管理Zygote進程在啟動過程中預加載和創建的各種對象，而Active堆是在Zygote進程fork第一個子進程之前創建的。之後無論是Zygote進程還是其子進程，都在Active堆上進行對象分配和釋放。這樣做的目的是使得Zygote進程和其子進程最大限度地共享Zygote堆所占用的內存。

為了管理Java堆，Dalvik虛擬機需要一些輔助數據結構，包括一個Card Table、兩個Heap Bitmap和一個Mark Stack。Card Table是為了記錄在垃圾收集過程中對象的引用情況的，以便可以實現Concurrent G。圖1的兩個Heap Bitmap，一個稱為Live Heap Bitmap，用來記錄上次GC之後，還存活的對象，另一個稱為Mark Heap Bitmap，用來記錄當前GC中還存活的對象。這樣，上次GC後存活的但是當前GC不存活的對象，就是需要釋放的對象。Davlk虛擬機使用標記-清除(Mark-Sweep)算法進行GC。在標記階段，通過一個Mark Stack來實現遞歸檢查被引用的對象，即在當前GC中存活的對象。有了這個Mark Stack，就可以通過循環來模擬函數遞歸調用。

Dalvik虛擬機Java堆的創建過程實際上就是上面分析的各種數據結構的創建過程，它們是在Dalvik虛擬機啟動的過程中創建的。接下來，我們就詳細分析這個過程。

Dalvik虛擬機在啟動的過程中，會通過調用函數dvmGcStartup來創建Java堆，它的實現如下所示：

booldvmGcStartup()

{

dvmInitMutex(&gDvm.gcHeapLock);

pthread_cond_init(&gDvm.gcHeapCond,NULL);

returndvmHeapStartup();

}

這個函數定義在文件dalvik/vm/alloc/Alloc.cpp中。

函數dvmGcStartup首先是分別初始化一個鎖和一個條件變量，它們都是用來保護堆的並行訪問的，接著再調用另外一個函數dvmHeapStartup來創建Java堆。

函數dvmHeapStartup的實現如下所示：

booldvmHeapStartup()

{

GcHeap*gcHeap;

if(gDvm.heapGrowthLimit==0){

gDvm.heapGrowthLimit=gDvm.heapMaximumSize;

}

gcHeap=dvmHeapSourceStartup(gDvm.heapStartingSize,

gDvm.heapMaximumSize,

gDvm.heapGrowthLimit);

......

gDvm.gcHeap=gcHeap;

......

if(!dvmCardTableStartup(gDvm.heapMaximumSize,gDvm.heapGrowthLimit)){

LOGE_HEAP("cardtablestartupfailed.");

returnfalse;

}

returntrue;

}

這個函數定義在文件dalvik/vm/alloc/Heap.cpp中

GcHeap*dvmHeapSourceStartup(size_tstartSize,size_tmaximumSize,

size_tgrowthLimit)

{

GcHeap*gcHeap;

HeapSource*hs;

mspacemsp;

size_tlength;

void*base;

......

/*

*Allocateacontiguousregionofvirtualmemorytosubdivided

*amongtheheapsmanagedbythegarbagecollector.

*/

length=ALIGN_UP_TO_PAGE_SIZE(maximumSize);

base=dvmAllocRegion(length,PROT_NONE,gDvm.zygote?"dalvik-zygote":"dalvik-heap");

......

/*Createanunlockeddlmallocmspacetouseas

*aheapsource.

*/

msp=createMspace(base,kInitialMorecoreStart,startSize);

......

gcHeap=(GcHeap*)calloc(1,sizeof(*gcHeap));

......

hs=(HeapSource*)calloc(1,sizeof(*hs));

......

hs->targetUtilization=gDvm.heapTargetUtilization*HEAP_UTILIZATION_MAX;

hs->minFree=gDvm.heapMinFree;

hs->maxFree=gDvm.heapMaxFree;

hs->startSize=startSize;

hs->maximumSize=maximumSize;

hs->growthLimit=growthLimit;

......

hs->numHeaps=0;

......

hs->heapBase=(char*)base;

hs->heapLength=length;

......

if(!addInitialHeap(hs,msp,growthLimit)){

......

}

if(!dvmHeapBitmapInit(&hs->liveBits,base,length,"dalvik-bitmap-1")){

......

}

if(!dvmHeapBitmapInit(&hs->markBits,base,length,"dalvik-bitmap-2")){

......

}

if(!allocMarkStack(&gcHeap->markContext.stack,hs->maximumSize)){

......

}

gcHeap->markContext.bitmap=&hs->markBits;

gcHeap->heapSource=hs;

gHs=hs;

returngcHeap;

......

}

這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

函數dvmHeapSourceStartup的執行過程如下所示：

1. 將參數maximum指定的最大堆大小對齊到內存頁邊界，得到結果為length，並且調用函數dvmAllocRegion分配一塊大小等於length的匿名共享內存塊，起始地址為base。這塊匿名共享內存即作為Dalvik虛擬機的Java堆。

2. 調用函數createMspace將前面得到的匿名共享內存塊封裝為一個mspace，以便後面可以通過C庫得供的mspace_malloc和mspace_bulk_free等函數來管理Java堆。這個mspace的起始大小為Java堆的起始大小，這意味著一開始在該mspace上能夠分配的內存不能超過Java堆的起始大小。不過後面我們動態地調整這個mspace的大小，使得它可以使用更多的內存，但是不能超過Java堆的最大值。

3, 分配一個GcHeap結構體gcHeap和一個HeapSource結構體hs，用來維護Java堆的信息，包括Java堆的目標利用率、最小空閒值、最大空閒值、起始大小、最大值、增長上限值、堆個數、起始地址和大小等信信息。

4. 調用函數addInitialHeap在前面得到的匿名共享內存上創建一個Active堆。這個Active堆的最大值被設置為Java堆的起始大小。

5. 調用函數dvmHeapBitmapInit創建和初始化一個Live Bitmap和一個Mark Bitmap，它們在GC時會用得到。

6. 調用函數allockMarkStack創建和初始化一個Mark Stack，它在GC時也會用到。

7. 將前面創建和初始化好的Mark Bitmap和HeapSource結構體hs保存在前面創建的GcHeap結構體gcHeap中，並且將該GcHeap結構體gcHeap返回給調用者。同時，HeapSource結構體hs也會保存在全局變量gHs中。

為了更好地對照圖2來理解函數dvmHeapSourceStartup所做的事情，接下來我們詳細分析上述提到的關鍵函數dvmAllocRegion、createMspace、addInitialHeap、dvmHeapBitmapInit和allockMarkStack的實現。

函數dvmAllocRegion的實現如下所示：

view plaincopy

 

 

void*dvmAllocRegion(size_tbyteCount,intprot,constchar*name){

void*base;

intfd,ret;

byteCount=ALIGN_UP_TO_PAGE_SIZE(byteCount);

fd=ashmem_create_region(name,byteCount);

if(fd==-1){

returnNULL;

}

base=mmap(NULL,byteCount,prot,MAP_PRIVATE,fd,0);

ret=close(fd);

if(base==MAP_FAILED){

returnNULL;

}

if(ret==-1){

munmap(base,byteCount);

returnNULL;

}

returnbase;

} 這個函數定義在文件dalvik/vm/Misc.cpp中。

從這裡就可以清楚地看出，函數dvmAllocRegion所做的事情就是調用函數ashmem_create_region來創建一塊匿名共享內存。關於Android系統的匿名共享內存，可以參考前面Android系統匿名共享內存Ashmem(Anonymous Shared Memory)簡要介紹和學習計劃一文。

函數createMspace的實現如下所示：

staticmspacecreateMspace(void*begin,size_tmorecoreStart,size_tstartingSize)

{

//Clearerrnotoallowstrerroronerror.

errno=0;

//Allowaccesstoinitalpagesthatwillholdmspace.

mprotect(begin,morecoreStart,PROT_READ|PROT_WRITE);

//Createmspaceusingourbackingstoragestartingatbeginandwithafootprintof

//morecoreStart.Don'tuseaninternaldlmalloclock.WhenmorecoreStartbytesofmemoryare

//exhaustedmorecorewillbecalled.

mspacemsp=create_mspace_with_base(begin,morecoreStart,false/*locked*/);

if(msp!=NULL){

//Donotallowmorecorerequeststosucceedbeyondthestartingsizeoftheheap.

mspace_set_footprint_limit(msp,startingSize);

}else{

ALOGE("create_mspace_with_basefailed%s",strerror(errno));

}

returnmsp;

} 這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

參數begin指向前面創建的一塊匿名共享內存的起始地址，也就是Java堆的起始地址，函數createMspace通過C庫提供的函數create_mspace_with_base將該塊匿名共享內存封裝成一個mspace，並且通過調用C庫提供的函數mspace_set_footprint_limit設置該mspace的大小為Java堆的起始大小。

函數addInitialHeap的實現如下所示：

staticbooladdInitialHeap(HeapSource*hs,mspacemsp,size_tmaximumSize)

{

assert(hs!=NULL);

assert(msp!=NULL);

if(hs->numHeaps!=0){

returnfalse;

}

hs->heaps[0].msp=msp;

hs->heaps[0].maximumSize=maximumSize;

hs->heaps[0].concurrentStartBytes=SIZE_MAX;

hs->heaps[0].base=hs->heapBase;

hs->heaps[0].limit=hs->heapBase+maximumSize;

hs->heaps[0].brk=hs->heapBase+kInitialMorecoreStart;

hs->numHeaps=1;

returntrue;

} 這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

在分析函數addInitialHeap的實現之前，我們先解釋一下兩個數據結構HeapSource和Heap。

在結構體HeapSource中，有一個類型為Heap的數組heaps，如下所示：

structHeapSource{

......

/*Theheaps;heaps[0]isalwaystheactiveheap,

*whichnewobjectsshouldbeallocatedfrom.

*/

Heapheaps[HEAP_SOURCE_MAX_HEAP_COUNT];

/*Thecurrentnumberofheaps.

*/

size_tnumHeaps;

......

}; 這個結構體定義在文件dalvik/vm/alloc/HeapSource.cpp中。

這個Heap數組最多有HEAP_SOURCE_MAX_HEAP_COUNT個Heap，並且當前擁有的Heap個數記錄在numpHeaps中。

HEAP_SOURCE_MAX_HEAP_COUNT是一個宏，定義為2，如下所示：

/*Thelargestnumberofseparateheapswecanhandle.

*/

#defineHEAP_SOURCE_MAX_HEAP_COUNT2 這個宏定義在文件dalvik/vm/alloc/HeapSource.h中。

這意味著Dalvik虛擬機的Java堆最多可以劃分為兩個Heap，就是圖1所示的Active堆和Zygote堆。

結構Heap的定義如下所示：

structHeap{

/*Themspacetoallocatefrom.

*/

mspacemsp;

/*Thelargestsizethatthisheapisallowedtogrowto.

*/

size_tmaximumSize;

/*Numberofbytesallocatedfromthismspaceforobjects,

*includinganyoverhead.ThisvalueisNOTexact,and

*shouldonlybeusedasaninputforcertainheuristics.

*/

size_tbytesAllocated;

/*Numberofbytesallocatedfromthismspaceatwhicha

*concurrentgarbagecollectionwillbestarted.

*/

size_tconcurrentStartBytes;

/*Numberofobjectscurrentlyallocatedfromthismspace.

*/

size_tobjectsAllocated;

/*

*Thelowestaddressofthisheap,inclusive.

*/

char*base;

/*

*Thehighestaddressofthisheap,exclusive.

*/

char*limit;

/*

*Iftheheaphasanmspace,thecurrenthighwatermarkin

*allocationsrequestedviadvmHeapSourceMorecore.

*/

char*brk;

}; 這個結構體定義在文件dalvik/vm/alloc/HeapSource.cpp中。

結構體Heap用來描述一個堆，它的各個成員變量的含義如下所示：

msp：描述堆所使用內存塊。

maximumSize：描述堆可以使用的最大內存值。

bytesAllocated：描述堆已經分配的字節數。

concurrentStartBytes：描述堆已經分配的內存達到指定值就要觸發並行GC。

objectsAllocated：描述已經分配的對象數。

base：描述堆所使用的內存塊的起始地址。

limit：描述堆所使用的內存塊的結束地址。

brk：描述當前堆所分配的最大內存值。

回到函數addInitialHeap中，參數hs和msp指向的是在函數dvmHeapSourceStartup中創建的HeapSource結構體和mspace內存對象，而參數maximumSize描述的Java堆的增長上限值。

通過函數addInitialHeap的實現就可以看出，Dalvik虛擬機在啟動的時候，實際上只創建了一個Heap。這個Heap就是我們在圖1中所說的Active堆，它開始的時候管理的是整個Java堆。但是在圖1中，我們說Java堆實際上還包含有一個Zygote堆的，那麼這個Zygote堆是怎麼來的呢?

從前面Dalvik虛擬機進程和線程的創建過程分析一文可以知道，Zygote進程會通過調用函數forkAndSpecializeCommon來fork子進程，其中與Dalvik虛擬機Java堆相關的邏輯如下所示：

staticpid_tforkAndSpecializeCommon(constu4*args,boolisSystemServer)

{

pid_tpid;

......

if(!dvmGcPreZygoteFork()){

......

}

......

pid=fork();

if(pid==0){

......

}else{

......

}

returnpid;

} 這個函數定義在文件dalvik/vm/native/dalvik_system_Zygote.cpp中。

從這裡就可以看出，Zygote進程在fork子進程之前，會調用函數dvmGcPreZygoteFork來處理一下Dalvik虛擬機Java堆。接下來我們就看看函數dvmGcPreZygoteFork都做了哪些事情。

函數dvmGcPreZygoteFork的實現如下所示：

booldvmGcPreZygoteFork()

{

returndvmHeapSourceStartupBeforeFork();

} 這個函數定義在文件dalvik/vm/alloc/Alloc.cpp中。

函數dvmGcPreZygoteFork只是簡單地封裝了對另外一個函數dvmHeapSourceStartupBeforeFork的調用，後者的實現如下所示：

booldvmHeapSourceStartupBeforeFork()

{

HeapSource*hs=gHs;//usealocaltoavoidtheimplicit"volatile"

HS_BOILERPLATE();

assert(gDvm.zygote);

if(!gDvm.newZygoteHeapAllocated){

/*Ensureheapsaretrimmedtominimizefootprintpre-fork.

*/

trimHeaps();

/*Createanewheapforpost-forkzygoteallocations.Weonly

*tryonce,evenifitfails.

*/

ALOGV("Splittingoutnewzygoteheap");

gDvm.newZygoteHeapAllocated=true;

returnaddNewHeap(hs);

}

returntrue;

} 這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

前面我們在分析函數dvmHeapSourceStartup的實現時提到，全局變量gHs指向的是一個HeapSource結構體，它描述了Dalvik虛擬機Java堆的信息。同時，gDvm也是一個全局變量，它的類型為DvmGlobals。gDvm指向的DvmGlobals結構體的成員變量newZygoteHeapAllocated的值被初始化為false。因此，當函數dvmHeapSourceStartupBeforeFork第一次被調用時，它會先調用函數trimHeaps來將Java堆中沒有使用到的內存歸還給系統，接著再調用函數addNewHeap來創建一個新的Heap。這個新的Heap就是圖1所說的Zygote堆了。

由於函數dvmHeapSourceStartupBeforeFork第一次被調用之後，gDvm指向的DvmGlobals結構體的成員變量newZygoteHeapAllocated的值就會被修改為true，因此起到的效果就是以後Zygote進程對函數dvmHeapSourceStartupBeforeFork的調用都是無用功。這也意味著Zygote進程只會在fork第一個子進程的時候，才會將Java堆劃一分為二來管理。

接下來我們就繼續分析函數trimHeaps和addNewHeap的實現，以便更好地理解Dalvik虛擬機是如何管理Java堆的。

函數trimHeaps的實現如下所示：

/*

*Returnunusedmemorytothesystemifpossible.

*/

staticvoidtrimHeaps()

{

HS_BOILERPLATE();

HeapSource*hs=gHs;

size_theapBytes=0;

for(size_ti=0;inumHeaps;i++){

Heap*heap=&hs->heaps[i];

/*Returnthewildernesschunktothesystem.*/

mspace_trim(heap->msp,0);

/*Returnanywholefreepagestothesystem.*/

mspace_inspect_all(heap->msp,releasePagesInRange,&heapBytes);

}

/*Sameforthenativeheap.*/

dlmalloc_trim(0);

size_tnativeBytes=0;

dlmalloc_inspect_all(releasePagesInRange,&nativeBytes);

LOGD_HEAP("madvised%zd(GC)+%zd(native)=%zdtotalbytes",

heapBytes,nativeBytes,heapBytes+nativeBytes);

} 這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

函數trimHeaps對Dalvik虛擬機使用的Java堆和默認Native堆做了同樣的兩件事情。

第一件事情是調用C庫提供的函數mspace_trim/dlmalloc_trim來將沒有使用到的虛擬內存和物理內存歸還給系統，這是通過系統調用mremap來實現的。

第二件事情是調用C庫提供的函數mspace_inspect_all/dlmalloc_inspect_all將不能使用的內存碎片對應的物理內存歸還給系統，這是通過系統調用madvise來實現的。注意，在此種情況下，只能歸還無用的物理內存，而不能歸還無用的虛擬內存。因為歸還內存碎片對應的虛擬內存會使得堆的整體虛擬地址不連續。

函數addNewHeap的實現如下所示：

staticbooladdNewHeap(HeapSource*hs)

{

Heapheap;

assert(hs!=NULL);

if(hs->numHeaps>=HEAP_SOURCE_MAX_HEAP_COUNT){

......

returnfalse;

}

memset(&heap,0,sizeof(heap));

/*

*Heapstoragecomesfromacommonvirtualmemoryreservation.

*Thenewheapwillstartonthepageaftertheoldheap.

*/

char*base=hs->heaps[0].brk;

size_toverhead=base-hs->heaps[0].base;

assert(((size_t)hs->heaps[0].base&(SYSTEM_PAGE_SIZE-1))==0);

if(overhead+hs->minFree>=hs->maximumSize){

......

returnfalse;

}

size_tmorecoreStart=SYSTEM_PAGE_SIZE;

heap.maximumSize=hs->growthLimit-overhead;

heap.concurrentStartBytes=hs->minFree-CONCURRENT_START;

heap.base=base;

heap.limit=heap.base+heap.maximumSize;

heap.brk=heap.base+morecoreStart;

if(!remapNewHeap(hs,&heap)){

returnfalse;

}

heap.msp=createMspace(base,morecoreStart,hs->minFree);

if(heap.msp==NULL){

returnfalse;

}

/*Don'tletthesoon-to-be-oldheapgrowanyfurther.

*/

hs->heaps[0].maximumSize=overhead;

hs->heaps[0].limit=base;

mspace_set_footprint_limit(hs->heaps[0].msp,overhead);

/*Putthenewheapinthelist,atheaps[0].

*Shiftexistingheapsdown.

*/

memmove(&hs->heaps[1],&hs->heaps[0],hs->numHeaps*sizeof(hs->heaps[0]));

hs->heaps[0]=heap;

hs->numHeaps++;

returntrue;

} 這個函數定義在文件dalvik/vm/alloc/HeapSource.cpp中。

函數addNewHeap所做的事情實際上就是將前面創建的Dalvik虛擬機Java堆一分為二，得到兩個Heap。

在劃分之前，HeadSource結構體hs只有一個Heap，如圖2所示：

 

 

圖2 Dalvik虛擬機Java堆一分為二之前

接下來在未使用的Dalvik虛擬機Java堆中創建另外一個Heap，如圖3所示：

 

 

圖3 在未使用的Dalvik虛擬機Java堆中創建一個新的Heap

最後調整HeadSource結構體hs的heaps數組，即交heaps[0]和heaps[1]的值，結果如圖4所示：

 

 

圖4 Dalvik虛擬機Java堆一分為二之後

其中，heaps[1]就是我們在圖1中所說的Zygote堆，而heaps[0]就是我們在圖1中所說的Active堆。以後無論是Zygote進程，還是Zygote子進程，需要分配對象時，都在Active堆上進行。這樣就可以使得Zygote堆最大限度地在Zygote進程及其子進程中共享。

這樣我們就分析完了函數addInitialHeap及其相關函數的實現，接下來我們繼續分析函數dvmHeapBitmapInit和allocMarkStack的實現。

函數dvmHeapBitmapInit的實現如下所示：

booldvmHeapBitmapInit(HeapBitmap*hb,constvoid*base,size_tmaxSize,

constchar*name)

{

void*bits;

size_tbitsLen;

assert(hb!=NULL);

assert(name!=NULL);

bitsLen=HB_OFFSET_TO_INDEX(maxSize)*sizeof(*hb->bits);

bits=dvmAllocRegion(bitsLen,PROT_READ|PROT_WRITE,name);

if(bits==NULL){

ALOGE("Couldnotmmap%zd-byteashmemregion'%s'",bitsLen,name);

returnfalse;

}

hb->bits=(unsignedlong*)bits;

hb->bitsLen=hb->allocLen=bitsLen;

hb->base=(uintptr_t)base;

hb->max=hb->base-1;

returntrue;

}

這個函數定義在文件dalvik/vm/alloc/HeapBitmap.cpp中。

參數hb指向一個HeapBitmap結構體，這個結構體正是函數dvmHeapBitmapInit要進行初始化的。參數base和maxSize描述的是Java堆的起始地址和大小。另外一個參數name描述的是參數hb指向的HeapBitmap結構體的名稱。

在分析函數dvmHeapBitmapInit的實現之前，我們先來了解一下結構體HeapBitmap的定義，如下所示：

structHeapBitmap{

/*Thebitmapdata,whichpointstoanmmap()edareaofzeroed

*anonymousmemory.

*/

unsignedlong*bits;

/*Thesizeoftheusedmemorypointedtobybits,inbytes.This

*valuechangeswhenthebitmapisshrunk.

*/

size_tbitsLen;

/*Therealsizeofthememorypointedtobybits.Thisisthe

*numberofbyteswerequestedfromtheallocatoranddoesnot

*change.

*/

size_tallocLen;

/*Thebaseaddress,whichcorrespondstothefirstbitin

*thebitmap.

*/

uintptr_tbase;

/*Thehighestpointervalueeverreturnedbyanallocation

*fromthisheap.I.e.,thehighestaddressthatmaycorrespond

*toasetbit.Iftherearenobitsset,(max*/

uintptr_tmax;

}; 這個結構體定義在文件dalvik/vm/alloc/HeapBitmap.h。

代碼對HeapBitmap結構體的各個成員變量的含義已經有很詳細的注釋，其中最重要的就是成員變量bits指向的一個類型為unsigned long的數組，這個數組的每一個bit都用來標記一個對象是否存活。

回到函數dvmHeapBitmapInit中，Java堆的起始地址為base，大小為maxSize，由此我們就知道，在Java堆上創建的對象的地址范圍為[base, maxSize)。但是通過C庫提供的mspace_malloc來在Java堆分配內存時，得到的內存地址是以8字節對齊的。這意味著我們只需要(maxSize / 8)個bit來描述Java堆的對象。結構體HeapBitmap的成員變量bits是一個類型為unsigned long的數組，也就是說，數組中的每一個元素都可以描述sizeof(unsigned long)個對象的存活。在32位設備上，一個unsigned long占用32個bit，這意味著需要一個大小為(maxSize / 8 / 32)的unsigned long數組來描述Java堆對象的存活。如果換成字節數來描述的話，就是說我們需要一塊大小為(maxSize / 8 / 32) × 4的內存塊來描述一個大小為maxSize的Java堆對象。

Dalvik虛擬機提供了一些宏來描述對象地址與HeapBitmap結構體的成員變量bits所描述的unsigned long數組的關系，如下所示：

#defineHB_OBJECT_ALIGNMENT8

#defineHB_BITS_PER_WORD(sizeof(unsignedlong)*CHAR_BIT)

/*isthedifferencefrom.basetoapointeraddress.

*istheindexof.bitsthatcontainsthebitrepresenting

*.

*/

#defineHB_OFFSET_TO_INDEX(offset_)\

((uintptr_t)(offset_)/HB_OBJECT_ALIGNMENT/HB_BITS_PER_WORD)

#defineHB_INDEX_TO_OFFSET(index_)\

((uintptr_t)(index_)*HB_OBJECT_ALIGNMENT*HB_BITS_PER_WORD)

#defineHB_OFFSET_TO_BYTE_INDEX(offset_)\

(HB_OFFSET_TO_INDEX(offset_)*sizeof(*((HeapBitmap*)0)->bits)) 這些宏定義在文件dalvik/vm/alloc/HeapBitmap.h中。

假設我們知道了一個對象的地址為ptr，Java堆的起始地址為base，那麼就可以計算得到一個偏移值offset。有了這個偏移值之後，就可以通過宏HB_OFFSET_TO_INDEX計算得到用來描述該對象存活的bit位於HeapBitmap結構體的成員變量bits所描述的unsigned long數組的索引index。有了這個index之後，我們就可以得到一個unsigned long值。接著再通過對象地址ptr的第4到第8位表示的數值為索引，在前面找到的unsigned long值取出相應的位，就可以得到該對象是否存活了。

相反，給出一個HeapBitmap結構體的成員變量bits所描述的unsigned long數組的索引index，我們可以通過宏HB_INDEX_TO_OFFSET找到一個偏移值offset，將這個偏移值加上Java堆的起始地址base，就可以得到一個Java對象的地址ptr。

第三個宏HB_OFFSET_TO_BYTE_INDEX借助宏HB_OFFSET_TO_INDEX來找出用來描述對象存活的bit在HeapBitmap結構體的成員變量bits所描述的內存塊的字節索引。

有了上述的基礎知識之後，函數dvmHeapBitmapInit的實現就一目了然了。

接下來我們再來看函數allocMarkStack的實現，如下所示：

view plaincopy

 

 

staticboolallocMarkStack(GcMarkStack*stack,size_tmaximumSize)

{

constchar*name="dalvik-mark-stack";

void*addr;

assert(stack!=NULL);

stack->length=maximumSize*sizeof(Object*)/

(sizeof(Object)+HEAP_SOURCE_CHUNK_OVERHEAD);

addr=dvmAllocRegion(stack->length,PROT_READ|PROT_WRITE,name);

if(addr==NULL){

returnfalse;

}

stack->base=(constObject**)addr;

stack->limit=(constObject**)((char*)addr+stack->length);

stack->top=NULL;

madvise(stack->base,stack->length,MADV_DONTNEED);

returntrue;

} 這個函數定義在文件vm/alloc/HeapSource.cpp中。

參數stack指向的是一個GcMarkStack結構體，這個結構體正是函數allocMarkStack要進行初始化的。參數maximumSize描述的是Java堆的大小。

同樣是在分析函數allocMarkStack的實現之前，我們先來了解一下結構體GcMarkStack的定義，如下所示：

structGcMarkStack{

/*Highestaddress(exclusive)

*/

constObject**limit;

/*Currenttopofthestack(exclusive)

*/

constObject**top;

/*Lowestaddress(inclusive)

*/

constObject**base;

/*Maximumstacksize,inbytes.

*/

size_tlength;

}; 這個結構體定義在文件dalvik/vm/alloc/MarkSweep.h中。

代碼對HeapBitmap結構體的各個成員變量的含義已經有很詳細的注釋。總結來說，GcMarkStack通過一個Object*數組來描述一個棧。這個Object*數組的大小通過成員變量length來描述。成員變量base和limit分別描述棧的最低地址和最高地址，另外一個成員變量top指向棧頂。

回到函數allocMarkStack中，我們分析一下需要一個多大的棧來描述Java堆的所有對象。首先，每一個Java對象都是必須要從Object結構體繼承下來的，這意味著每一個Java對象占用的內存都至少為sizeof(Object)。其次，通過C庫提供的接口mspace_malloc在Java堆上為對象分配內存時，C庫自己需要一些額外的內存來管理該塊內存，例如用額外的4個字節來記錄分配出去的內存塊的大小。額外需要的內存大小通過宏HEAP_SOURCE_CHUNK_OVERHEAD來描述。最後，我們就可以知道，一個大小為maximumSize的Java堆，在最壞情況下，存在(maximumSize / (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD))個對象。也就是說，GcMarkStack通過一個大小為(maximumSize / (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD))的Object*數組來描述一個棧。如果換成字節數來描述的話，就是說我們需要一塊大小為(maximumSize * sizeof(Object*) / (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD))的內存塊來描述一個GcMarkStack棧。

有了上述的基礎知識之後，函數allocMarkStack的實現同樣也一目了然了。

這樣，函數dvmHeapSourceStartup及其相關的函數dvmAllocRegion、createMspace、addInitialHeap、dvmHeapBitmapInit和allockMarkStack的實現我們就分析完了，回到前面的函數dvmHeapStartup中，它調用函數dvmHeapSourceStartup創建完成Java堆及其相關的Heap Bitmap和Mark Stack之後，還需要繼續調用函數dvmCardTableStartup來創建一個Card Table。這個Card Table在執行Concurrent GC時要使用到。

函數dvmCardTableStartup的實現如下所示：

view plaincopy

 

 

/*

*Maintainacardtablefromthethewritebarrier.Allwritesof

*non-NULLvaluestoheapaddressesshouldgothroughanentryin

*WriteBarrier,andfromtheretohere.

*

*Theheapisdividedinto"cards"ofGC_CARD_SIZEbytes,as

*determinedbyGC_CARD_SHIFT.Thecardtablecontainsonebyteof

*datapercard,tobeusedbytheGC.Thevalueofthebytewillbe

*oneofGC_CARD_CLEANorGC_CARD_DIRTY.

*

*Afteranystoreofanon-NULLobjectpointerintoaheapobject,

*codeisobligedtomarkthecarddirty.Thesettersin

*ObjectInlines.h[suchasdvmSetFieldObject]dothisforyou.The

*JITandfastinterpretersalsocontaincodetomarkcardsasdirty.

*

*Thecardtable'sbase[the"biasedcardtable"]getssettoa

*ratherstrangevalue.InordertokeeptheJITfromhavingto

*fabricateorloadGC_DIRTY_CARDtostoreintothecardtable,

*biasedbaseiswithinthemmapallocationatapointwhereit'slow

*byteisequaltoGC_DIRTY_CARD.SeedvmCardTableStartupfordetails.

*/

/*

*Initializesthecardtable;mustbecalledbeforeanyother

*dvmCardTable*()functions.

*/

booldvmCardTableStartup(size_theapMaximumSize,size_tgrowthLimit)

{

size_tlength;

void*allocBase;

u1*biasedBase;

GcHeap*gcHeap=gDvm.gcHeap;

intoffset;

void*heapBase=dvmHeapSourceGetBase();

assert(gcHeap!=NULL);

assert(heapBase!=NULL);

/*Allzerosisthecorrectinitialvalue;allclean.*/

assert(GC_CARD_CLEAN==0);

/*Setupthecardtable*/

length=heapMaximumSize/GC_CARD_SIZE;

/*Allocateanextra256bytestoallowfixedlow-byteofbase*/

allocBase=dvmAllocRegion(length+0x100,PROT_READ|PROT_WRITE,

"dalvik-card-table");

if(allocBase==NULL){

returnfalse;

}

gcHeap->cardTableBase=(u1*)allocBase;

gcHeap->cardTableLength=growthLimit/GC_CARD_SIZE;

gcHeap->cardTableMaxLength=length;

biasedBase=(u1*)((uintptr_t)allocBase-

((uintptr_t)heapBase>>GC_CARD_SHIFT));

offset=GC_CARD_DIRTY-((uintptr_t)biasedBase&0xff);

gcHeap->cardTableOffset=offset+(offset<0?0x100:0);

biasedBase+=gcHeap->cardTableOffset;

assert(((uintptr_t)biasedBase&0xff)==GC_CARD_DIRTY);

gDvm.biasedCardTableBase=biasedBase;

returntrue;

} 這個函數定主在文件dalvik/vm/alloc/CardTable.cpp中。

參數heapMaximumSize和growthLimit描述的是Java堆的最大值和增長上限值。

在Dalvik虛擬機中，Card Table和Heap Bitmap的作用是類似的。區別在於：

1. Card Table不是使用一個bit來描述一個對象，而是用一個byte來描述GC_CARD_SIZE個對象;

2. Card Table不是用來描述對象的存活，而是用來描述在Concurrent GC的過程中被修改的對象，這些對象需要進行特殊處理。

全局變量gDvm的成員變量gcHeap指向了一個GcHeap結構體。在GcHeap結構體，通過cardTableBase、cardTableLength、cardTableMaxLength和cardTableOffset這四個成員變量來描述一個Card Table。它們的定義如下所示：

view plaincopy

 

 

structGcHeap{

......

/*GC'scardtable*/

u1*cardTableBase;

size_tcardTableLength;

size_tcardTableMaxLength;

size_tcardTableOffset;

......

}; 這個結構體定義在文件dalvik/vm/alloc/HeapInternal.h中。

其中，成員變量cardTableBase和cardTableMaxLength描述的是創建的Card Table和起始地址和大小。成員變量cardTableLength描述的當前Card Table使用的大小。成員變量cardTableMaxLength和cardTableLength的關系就對應於Java堆的最大值(Maximum Size)和增長上限值(Growth Limit)的關系。

Card Table在真正使用的時候，並不是從成員變量cardTableBase描述的起始地址開始的，而是從一個相對起始地址有一定偏移的位置開始的。這個偏移量記錄在成員變量cardTableOffset中。相應地，Java堆的起始地址和Card Table的偏移地址的差值記錄在全局變量gDvm指向的結構體DvmGlobals的成員變量biasedCardTableBase。按照函數dvmCardTableStartup前面的注釋，之所以要這樣做，是為了避免JIT在Card Table偽造假值。至於JIT會在Card Table偽造假值的原因，就不得而知，因為還沒有研究JIT。在此也希望了解的同學可以告訴一下老羅:)

前面我們提到，在Card Table中，用一個byte來描述GC_CARD_SIZE個對象。GC_CARD_SIZE是一個宏，它的定義如下所示：

#defineGC_CARD_SHIFT7

#defineGC_CARD_SIZE(1<這兩個宏定義在文件dalvik/vm/alloc/CardTable.h中。

也就是說，在Card Table中，用一個byte來描述128個對象。每當一個對象在Concurrent GC的過程中被修改時，典型的情景就是我們通過函數dvmSetFieldObje修改了該對象的引用類型的成員變量。在這種情況下，該對象在Card Table中對應的字節會被設置為GC_CARD_DIRTY。相反，如果一個對象在Concurrent GC的過程中沒有被修改，那麼它在Card Table中對應的字節會保持為GC_CARD_CLEAN。

GC_CARD_DIRTY和GC_CARD_CLEAN是兩個宏，它們的定義在如下所示：

#defineGC_CARD_CLEAN0

#defineGC_CARD_DIRTY0x70 這兩個宏定義在文件dalvik/vm/alloc/CardTable.h中。

接下來我們再通過四個函數dvmIsValidCard、dvmCardFromAddr、dvmAddrFromCard和dvmMarkCard來進一步理解Card Table和對象地址的關系。

函數dvmIsValidCard的實現如下所示：

/*

*Returnstrueifftheaddressiswithintheboundsofthecardtable.

*/

booldvmIsValidCard(constu1*cardAddr)

{

GcHeap*h=gDvm.gcHeap;

u1*begin=h->cardTableBase+h->cardTableOffset;

u1*end=&begin[h->cardTableLength];

returncardAddr>=begin&&cardAddr} 這個函數定義在文件dalvik/vm/alloc/CardTable.cpp中。

參數cardAddr描述的是一個Card Table內部的地址。由於上述的偏移地址的存在，並不是所有的Card Table內部地址都是正確的Card Table地址。只有大於等於偏移地址並且小於當前使用的地址的地址才是正確的地址。

Card Table的起始地址記錄在GcHeap結構體的成員變量cardTableBase中，而偏移量記錄在另外一個成員變量cardTableOffset中，因此將這兩個值相加即可得到Card Table的偏移地址。另外，當前Card Table使用的大小記錄在GcHeap結構體的成員變量cardTableLength中，因此，通過這些信息我們就可以判斷參數cardAddr描述的是否是一個正確的Card Table地址。

函數dvmCardFromAddr的實現如下所示：

/*

*Returnstheaddressoftherelevantbyteinthecardtable,given

*anaddressontheheap.

*/

u1*dvmCardFromAddr(constvoid*addr)

{

u1*biasedBase=gDvm.biasedCardTableBase;

u1*cardAddr=biasedBase+((uintptr_t)addr>>GC_CARD_SHIFT);

assert(dvmIsValidCard(cardAddr));

returncardAddr;

} 這個函數定義在文件dalvik/vm/alloc/CardTable.cpp中。

參數addr描述的是一個對象地址，函數dvmCardFromAddr返回它在Card Table中對應的字節的地址。全局變量gDvm指向的結構體DvmGlobals的成員變量biasedCardTableBase記錄的是Java堆的起始地址與Card Table的偏移地址的差值。將參數addr的值左移GC_CARD_SHIFT位，相當於是得到對象addr在Card Table的字節索引值。將這個索引值加上Java堆的起始地址與Card Table的偏移地址的差值，即可得到對象addr在Card Table中對應的字節的地址。

函數dvmAddrFromCard的實現如下所示：

/*

*Returnsthefirstaddressintheheapwhichmapstothiscard.

*/

void*dvmAddrFromCard(constu1*cardAddr)

{

assert(dvmIsValidCard(cardAddr));

uintptr_toffset=cardAddr-gDvm.biasedCardTableBase;

return(void*)(offset<} 這個函數定義在文件dalvik/vm/alloc/CardTable.cpp中。

參數cardAddr描述的是一個Card Table地址，函數dvmAddrFromCard返回它對應的對象的地址，它所執行的操作剛剛是和上面分析的函數dvmCardFromAddr相反。在此這裡不再多述，同學會自己體會一下。

函數dvmMarkCard的實現如下所示：

/*

*Dirtiesthecardforthegivenaddress.

*/

voiddvmMarkCard(constvoid*addr)

{

u1*cardAddr=dvmCardFromAddr(addr);

*cardAddr=GC_CARD_DIRTY;

} 這個函數定義在文件dalvik/vm/alloc/CardTable.cpp中。

在Concurrent GC執行的過程中，如果修改了一個對象的類型為引用的成員變量，那麼就需要調用函數dvmMarkCard來將該對象在Card Table中對應的字節設置為GC_CARD_DIRTY，以便後面可以對這個對象進行特殊的處理。這個特殊的處理我們後面分析Dalvik虛擬機的垃圾收集過程時再分析。

函數dvmMarkCard的實現很簡單，它首先是通過函數dvmCardFromAddr找到對象在Card Table中對應的字節的地址，然後再將訪字節的值設置為GC_CARD_DIRTY。

有了這些基礎知識之後，回到函數dvmCardTableStartup中，我們需要知道要創建的Card Table的大小以及該Card Table使用的偏移量。正常來說，我們需要的Card Table的大小為(heapMaximumSize / GC_CARD_SIZE)，其中，heapMaximumSize為Java堆的大小。但是前面分析的偏移量的存在，我們需要額外的一些內存。額外的內存大小為0x100，即256個字節。因此，我們最終需要的Card Table的大小length就為：

(heapMaximumSize / GC_CARD_SIZE) + 0x100

我們通過調用函數dvmAllocRegion來創建Card Table，得到其起始地址為allocBase。接下來就可以計算Card Table使用的偏移地址。

首先是計算一個偏移地址biasedBase：

(u1 *)((uintptr_t)allocBase - ((uintptr_t)heapBase >> GC_CARD_SHIFT))

其中，heapBase是Java堆的起始地址。

用GC_CARD_DIRTY的值減去biasedBase地址的低8位，就可以得到一個初始偏移量offset：

GC_CARD_DIRTY - ((uintptr_t)biasedBase & 0xff)

GC_CARD_DIRTY的值定義為0x70，biasedBase地址的低8位描述的值界於0和0xff之間，因此，上面計算得到的offset可能為負數。在這種情況下，需要將它的值加上256，這是因為我們需要保證Card Table使用的偏移量是正數。最終得到的偏移量如下所示：

offset + (offset < 0 ? 0x100 : 0)

這裡之所以是加上256，是因為我們在創建Card Table的時候，額外地增加了256個字節，因此這裡不僅可以保證偏移量是正數，還可以保證最終使用的Card Table不會超出前面通過調用函數dvmAllocRegion創建的內存塊范圍。

上述計算得到的偏移量保存在gcHeap->cardTableOffset中。相應地，Java堆的起始地址和Card Table使用的偏移地址的差值需要調整為：

biasedBase + gcHeap->cardTableOffset

得到的結果保存在gDvm.biasedCardTableBase中。

這裡之所以要采取這麼奇怪的算法來給Card Table設置一個偏移量，就是為了前面說的，避免JIT在Card Table偽造假值。

至此，我們就分析完成Dalvik虛擬機在啟動的過程中創建Java堆及其相關的Mark Heap Bitmap、Live Heap Bitmap、Mark Stack和Card Table數據結構了。