像 Dalvik 這類 VM ，最有趣的是 Garbage Collection (GC)。Dalvik 的 GC 是否萬中無一的人中之龍? 撥門進戶一看，以為是風姿綽的美少女，原來是隔壁的大嬸。不過，黑貓白貓都無關，只要老牛能拖車。
dvmGcStartup
朋友曾介紹一個小工具 tree ，這是一個能在文字模式下，將目錄及檔案以樹狀形式呈現。用 tree 列出 vm/ 目錄下所有子目錄和檔案，能看到有一個 GC.h 在 vm/alloc/ 目錄下。這應該就是我們所需要的。在 GC.h 裡面可以看到十來個 function 的定義，任意挑一個，就第一個 function dvmCollectGarbage() 好了。dvmCollectGarbage() 就在 vm/alloc/Alloc.c 檔案裡。利用 editor 的 folding 功能，列出所有 function ，快速的瀏覽一次。 dvmGcStartup() 這個 function 熠熠生輝，看到 Startup ，不自主就是要去看一下，看如何啟動。
001 bool dvmGcStartup(void)
002 {
003 dvmInitMutex(&gDvm.gcHeapLock);
004
005 return dvmHeapStartup();
006 }
內容很簡單，只有 initialize 一個 mutex 和呼叫 dvmHeapStartup()。 dvmHeapStartup() 看來是 heap 的初始化動化，用以分配、管理記憶體。 Heap 讓我感到好奇，但最好先確定 dvmGcStartup() 在混元太初之時，是否真有被呼叫。喚來火眼金睛 grep 探查一番，grep 的雙眼兩束紅光，閃電雷擊之間發現了 vm/Init.c 呼叫很大。於是催動座騎九天神牛 Emacs ，快速來 Init.c ，一一檢視 dvmGcStartup() 出現的位置。其中 dvmStartup() 裡除了呼叫 dvmGcStartup() 之外，還呼叫了許許多多的 dvmXXXStartup()。這又是一個 的通則，儘量將功能類似的符號，已相同形式的名字。然而，敝人覺的 Dalvik 使用 Startup 不如 Init 來的直覺、通用。很明顯， dvmStartup() 應該是 Dalvik 集中初始化一些子系統的地方。查下呼叫 dvmStartup() 的位置，會看一個熟悉的符號，JNI_CreateJavaVM()。這是 create Dalvik VM 環境的 function 。
Heap
回頭來看 Heap ，GC 必定和 Heap 有關，先看一下 heap 對瞭解 GC 應該很有幫助。話說 dvmGcStartup() 呼叫 dvmHeapStartup() ，我不免進去查看一番。
dvmHeapStartup() 的動作大致為
- create 一個 GcHeap by dvmHeapSourceStartup()
- assign gDvm.gcHeap 為其面的 object
- dvmHeapInitHeapRefTable()
- dvmInitializeHeapWorkerState()
HeapSource
在 dvmHeapSourceStartup() 裡可以看到呼叫 createMspace() 以建立 mspace ，並將 mspace 用以 allocate 記憶體。mspace_alloc()
001 /* Create an unlocked dlmalloc mspace to use as
002 * the small object heap source.
003 */
004 msp = createMspace(startSize, absoluteMaxSize, 0);
005 if (msp == NULL) {
006 return false;
007 }
008
009 /* Allocate a descriptor from the heap we just created.
010 */
011 gcHeap = mspace_malloc(msp, sizeof(*gcHeap));
因此，mspace 是 Dalvik 用來管理記憶體的機制。如果你在 Dalvik 的目錄下 grep mspace_malloc ，就如泥牛入水，什麼也找不到。但前面的註解裡有提到 dlmalloc ，透過 search engine 會發現 其實是由 Doug Lea 實作的註名 memory allocator。mspace 其實是 dlmalloc 裡，用以管理和設定可分配的記憶體範圍。createMspace() 傳入的前兩個參數就是設定空間的大小， dlmalloc 會自動從系統配置這些空間。
雖然 Dalvik 使用 dlmalloc ，但另外包了一層。好處是，未來隨時可以把 dlmalloc 換掉，如果有必要的話。Dalvik 用
- GcHeap
- HeapSource
- Heap
/* The heaps; heaps[0] is always the active heap,
* which new objects should be allocated from.
*/
Heap heaps[HEAP_SOURCE_MAX_HEAP_COUNT];
一個 HeapSource 能有多個 Heap ，事實上是三個。使用時，永遠使用第一個來 allocate memory。addNewHeap() 永遠將新加入的 mspace 加在第一個 Heap，而原本 Heap 的內容往後移一個位置。dvmHeapSourceStartup() 即在 create 新的 mspace 後，呼叫 addNewHeap() ，將之加入 HeapSource。
dvmHeapSourceStartup() create GcHeap 、HeapSource 、Heap、mspace 各一。GcHeap 裡有 pointer GcHeap::heapSource 指向 HeapSource ，而 HeapSource::heaps 如前述。 一個 Heap 管理一個 mspace，是一塊連續可分配的空間，由起始位址 (base address)和空間大小指定該空間。每當從 Heap 分配一塊記憶體時，會在 Heap::objectBitmap 標示 heap 哪些相對位址有 GC 所管理的 object 。 實際上，記憶體的分配是由 dlmalloc 處理，HeapSource.c 裡的 countAllocation() 負責在 Heap::objectBitmap 進行標記，以追蹤這些區塊的位置，並紀錄記憶體使用的狀況。
HeapSource.c 裡
- dvmHeapSourceAlloc()
- dvmHeapSourceAllocAndGrow()
Heap::objectBitmap 是一個塊連續記憶體，每一個 bit 代表 8 bytes 為單位的區塊。若某 object 離 mspace 開頭位址 n 個 8bytes ，則標記第 n 個 bit。
Garbage Collection
當 dvmMalloc() 發現記憶體不足時，就會呼叫 dvmCollectGarbageInternal() 開始進行記憶體回收。回收演算法的主要邏輯不複雜。
- dvmHeapBeginMarkStep()
- setup 一個新的 bitmap
- dvmHeapMarkRootSet()
- 標記所有的 root object
- dvmHeapScanMarkedObjects()
- 掃描所有已標記的 object ，看是否 reference 到其它未標記的 object，並加入標記。
- 直到沒有發現任何新 object 為止。
- dvmHeapFinishMarkStep()
- 比較新的 bitmap 和原本在 Heap 裡的 bitmap
- 釋放標記在 Heap::objectBitmap 裡，卻未在新 bitmap 裡出現的 object 。
dvmHeapScanMarkedObjects() 是透過 dvmHeapBitmapWalkList() 進行第一輪掃描，針對 dvmHeapMarkRootSet() 已標記的 object 。dvmHeapBitmapWalkList() 會呼叫一個參數傳入的 callback， 將掃描新發現的 object 加入到一個 stack 裡。dvmHeapScanMarkedObjects() 呼叫 processMarkStack() 處理 stack 裡的 object 。 當 processMarkStack() 處理stack 裡的 object 時，新發現的物件會加入該 stack 。 processMarkStack() 會不斷從 stack pop object ，並檢視是否 reference 未標記物件，直到清空 stack 。檢視 object 的 reference 是由 MarkSweep.c 裡的 scanObject() 進行。 scanObject() 檢查 object 的每一個欄位所 reference 的物件是否尚未被標記。
Dalvik 在記憶體管理方面甚是單純，甚至連 object 的 reuse 都沒有。因此，也沒 generation 的設計。目前也沒進行周期性的 scan ，似乎一直用到不夠時才開始掃描。許多地方都顯示出，其實 Dalvik 有不少設計是趕出來的，未來還有不少的改進空間。
結論
嚴格看來，Dalvik 算是一個小系統。即始是小系統，要 trace 每一個角落也很花時間。最重要的是摸清整個 soruce tree 的主要架構，接下來就可以隨時針對需要知道/想知道的部分進行細部探索。要清楚 soruce tree 的最好方法是了解系統的一些基礎設計，像是記憶體管理， main() function 執行的主要流程等。至於其它設計，則是像翻字典一樣，而要時依靠對 soruce tree 的熟悉，可以很快的 trace 其內容。
另外，建議在 trace 時，能為 main() function 的主要流程畫下一張 follow chart ，之後 trace 時，當指引地圖，妙用無窮。