Dalvik VMのオブジェクト管理についての概要

Dalvik VMのGCに関連して、今回はオブジェクト管理の概要です。

Dalvik VMはオブジェクトをGCで管理しています。
GCはStop-the-World型のMark-Sweep GCです。
特にSweepはBitwise Sweepという方法でした。

DalvikではBitmapでメモリ上のどこにオブジェクトがあるかを管理しています。
それと同じ構造のMark Bitmapというのを作って、mark処理をします。
markingが終ってマークされていない部分がゴミです。
対応するオブジェクトをFreeします。

オブジェクトを管理するBitmapをObject Bitmapと言います。
このObject Bitmapをいつ管理するのかが気になります。

オブジェクト削除時にObject Bitmap管理はどうしてるのか？

オブジェクト生成時のObject Bitmap管理はどうしてるのか？

そもそも、Bitwize Sweepした後にコンパクションしなかったらフラグメントしまくるんじゃないの？

本エントリでこの3つの疑問を解決します。

まずは疑問１をサラッと解決しておきましょう。
Sweep処理の

//mydroid/dalvik/vm/alloc/Heap.c
void dvmCollectGarbageInternal(bool collectSoftReferences)
{
...
    dvmHeapSweepUnmarkedObjects(&numFreed, &sizeFreed);

を掘って行けばスグです。
dvmHeapSweepUnmarkedObjects()関数のコールツリーはこんな感じ。

//mydroid/dalvik/vm/alloc/Heap.c
void dvmCollectGarbageInternal(bool collectSoftReferences)
{
    //mydroid/dalvik/vm/alloc/MarkSweep.c
    dvmHeapSweepUnmarkedObjects(&numFreed, &sizeFreed)
    {
        //mydroid/dalvik/vm/alloc/MarkSweep.c
        dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps, sweepBitmapCallback, NULL);

このsweepBitmapCallbackが関数ポインタになっていて、マークされていないオブジェクトに対して呼出されます。
#連続したゴミオブジェクトがあると、纏めて適用するっぽいですが。
この関数からのコールツリーをドンドン辿って行きましょう。

//mydroid/dalvik/vm/alloc/MarkSweep.c
static bool sweepBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
{
    //mydroid/dalvik/vm/alloc/HeapSource.c
    dvmHeapSourceFree(hc)
    {
        //mydroid/dalvik/vm/alloc/HeapSource.c
        countFree(heap, ptr, true)
        {
            dvmHeapBitmapClearObjectBit(&heap->objectBitmap, ptr);

やっと出ました。結構深かったですね。
このdvmHeapBitmapClearObjectBit()関数でオブジェクトに対応するObject Bitmapをクリアしています。

これで、GC時にObject Bitmapのクリア処理を行っていることが分かりました。

続いて疑問２をやっつけましょう。
この疑問を解決すると自動的に疑問３も半分解決できちゃいます＞＜
なので、ここが本エントリのクライマックスです！

Dalvik VMはインタプリタしか持っていないので、そこからオブジェクト生成の実行パスを追って行くと良さそうです。
インタプリタの基本は巨大なswitch文です。
＃インタプリタの基本はswitchですが、Dalvik VMはスレッドインタプリタ（threaded interpreter）という手法を使っているそうです。コメントで指摘して頂いたRednaxelaFXさん、ありがとうございました。

各命令毎にcase文を作って処理しているだけです。
なので、今回はNEW命令を見ればよいでしょう。

メモリ管理の話が飽きて来たのでちょっと脱線(ォィ
Dalvikが処理できるバイトコードにはどんなものがあるんでしょう？
Java VMのスタックマシンではなくレジスタマシンらしいので、
Java Bytecodeとは違ったものになるでしょう。
特に今回のNEW命令が気になるところです。
いきなり答えですw
ニーモニックとシンタックスはこんな感じです。

new-instance vAA, type@BBBB
// 8itのレジスタ番号
// 16bitのクラス型index

なんてアッサリ。分かりやす過ぎ！
もっとDalvik Bytecodeのことが知りたい人は「Bytecode for the Dalvik VM」を見ればイイよ。
かなり新鮮ですよ。

さぁさっそくnew-instanceの処理部を見ましょう。

 //mydroid/dalvik/vm/mterp/c/OP_NEW_INSTANCE.c
HANDLE_OPCODE(OP_NEW_INSTANCE /*vAA, class@BBBB*/)
{
    newObj = dvmAllocObject(clazz, ALLOC_DONT_TRACK);

案の定、これも分かりやすい関数ですね。clazzはオブジェクトのクラス型です。
このクラスをひな形にしてオブジェクトを作れってわけですね。
では、どんどんこの関数を掘って行きましょう。
きっとObject Bitmapを管理している部分に行き着くはずです。

//mydroid/dalvik/vm/alloc/Alloc.c
Object* dvmAllocObject(ClassObject* clazz, int flags)
{
    //mydroid/dalvik/vm/alloc/Heap.c
    dvmMalloc(clazz->objectSize, flags)
    {
        //mydroid/dalvik/vm/alloc/Heap.c
        tryMalloc(size)
        {
            //mydroid/dalvik/vm/alloc/HeapSouce.c
            dvmHeapSourceAlloc(size + sizeof(DvmHeapChunk))
            {
                //mydroid/dalvik/vm/alloc/HeapSource.c
                countAllocation(heap, ptr, true)
                {
                    dvmHeapBitmapSetObjectBit(&heap->objectBitmap, ptr);

Object Bitmapをクリアする時と似た名前の関数が出てきました。
dvmHeapBitmapSetObjectBit()関数でオブジェクトに対応するObject Bitmapを管理しています。
これで、生成部分のObject Bitmapが管理できました。

さっきのコールツリーから、どうやらdvmHeapSourceAlloc()関数内でメモリ領域を確保しているようです。
どうやって確保しているのでしょうか？
Object Bitmapの空いている部分からオブジェクトサイズ分の領域を確保しないといけません。
でも、Object BitmapはGCで歯抜け状態なはず。
このフラグメントした領域をどうやって扱ってるのでしょうか？

謎は深まるばかりです。
さっそく、アタリをつけたdvmHeapSourceAlloc()関数を掘って行きましょう。

//mydroid/dalvik/vm/alloc/HeapSouce.c
void * dvmHeapSourceAlloc(size_t n)
{
...
    ptr = mspace_calloc(heap->msp, 1, n);
...
    return ptr;
}

なにやら怪しげな関数が出てきました。
Dalvik VMに関係するグローバルになっている関数は頭に「dvm」が付くはずです。
でも、これにはそれがない！何ヤツ？！

と恐れるまでもなく、見つかります。

//mydroid/bionic/libc/bionic/dlmalloc.c
void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
...
    mem = internal_malloc(ms, elem_size);
...
  return mem;
}

でたっ！Bionicだ！
Androidで最も価値があると言われている(そう私が思っている)Bionicですよ。

■Bionic(バイオニック)とは？
配置されているパス名からも自明ですが、libcです。
逆に言うと、libcのAndroid実装がBionicということです。

そして、このファイル名から答えが分かりました。
Doug Lea’s Mallocの様ですね。
ファイルの初めの方にも書いています。

This is a version (aka dlmalloc) of malloc/free/realloc written by
Doug Lea and released to the public domain,

そして、素晴らしいことにライセンスはクリエイティブ・コモンズです。
Bionicが素晴らしいのはココですよね。GPLに縛られないところ。

dlmallocの詳細は作者のページが一番詳しいので、そこを参照して下さい。図付きで分かりやすいです。

簡単に概要だけを説明すると、予めmmapしておいた領域をちゃんと管理しておいて、
空いている部分をFree Listとして管理するんです。
Free ListもFree領域サイズ毎に分けて管理しているので、
Allocationの時間もわりと早いしメモり効率もわりと良い。
シンプルながらも効率の良い素晴らしいアイデアです。

このdlmallocが管理している利用メモリ領域と、
Object Bitmapで管理している利用領域が一致します。
なので、Dalvik VM内でオブジェクトの生成はObject Bitmapだけで良いんですね。
どの領域を確保するかはdlmallocに任せれば良いのです。

美しいッ！
久々にコードを読んで涙が出ました；；

Dalvik VMのコードは本当に美しい。
でも、それを説明する人間(私)のレベルが低いので、
間違ってるところがあるかもしれません。
見つけたら是非教えて下さい。
お願いします。

Enjoy Reading!

• トラックボールのない端末でもカーソルを簡単に移動する方法 [Xperia_Report]
• Dalvik VMのGarbage Collection概要
• 空中に文字を書くアプリ「Air Writer」 続
• Android日本語入力アプリ 「simeji」 をバージョンアップしました
• Androidでベル打ち
• Simejiがローカル辞書を使えるようになりました
• Google Developer Day 2009でSimejiを展示します