Dalvik VMのGarbage Collection概要

ちょっと時間ができたので、知り合いのブログを読みあさってました。
すると、安藤恐竜さんとこでこんな翻訳記事を見つけました。

Track memory allocations（日本語超訳）
大半のケースでは、数多くの小さくて短命なオブジェクトが原因でGCが起動される。世代別GCのような場合には、このようなオブジェクトの回収を最適化し、頻繁にGCが起動されることを防ぐことができる。AndroidのGCは、残念ながらそのような最適化を行うことができず、パフォーマンスに影響の多い一連のコードの中で、短命なオブジェクトを作ると、そのままアプリケーションの性能にとって影響が多くなってしまう。

マジっすか？！一応原文もチェック。

Track memory allocations
Most of the time, garbage collection occurs because of tons of small, short-lived objects and some garbage collectors, like generational garbage collectors, can optimize the collection of these objects so that the application does not get interrupted too often. The Android garbage collector is unfortunately not able to perform such optimizations and the creation of short-lived objects in performance critical code paths is thus very costly for your application.

マジだ。ずっとCopyGCで軽量なGCをやってると思ってました。
世代別でCopyGCとMark-Sweep GCだと…。
ちゃんと調べよう！

2009年03月14日にgitしてきたcupcakeです。
＃どうやったらcupcakeのリビジョン番号とか調べられるんだろう？

ヒープは１つで、Mark-Sweep GCで管理していました。

アルゴリズムの超簡単解説。
0: 全スレッドを止める（管理がメンドウなので、GC中はオブジェクトは作らせない）
１： 絶対消してはいけないオブジェクトをMarkしてそのオブジェクトをスタックにPush
２： スタックからオブジェクトをPop
３： Popしたオブジェクトから参照できるMarkされていないオブジェクトをMarkしてPush
　　　（つまり、MarkされているオブジェクトはPushしない）
4: スタックが空になるまで、2と３を繰り返す
5: Markされていないオブジェクトを削除
6: 全スレッドを再開

まぁ色々細かい制御はありますが、アルゴリズムはこんな感じです。
おもむろに出てきたスタックはアルゴリズムの本質ではありません。
後の説明上、出しておきました。
本質は、
「絶対消してはいけないオブジェクトからの参照ツリーを全部マークする。」
「マークされていないオブジェクトは削除する。」
です。

GCが発生するタイミングはいくつかあります。
オブジェクトのAllocationに失敗したりだとか、
java.lang.System.gc()を呼出したり。

入り口はいくつかあるようですが、メインとなる関数は以下です。

//mydroid/dalvik/vm/alloc/Heap.c
void dvmCollectGarbageInternal(bool collectSoftReferences)
{
...
}

この関数でMark-Sweep GCのアルゴリズムを実行します。

dvmCollectGarbageInternal()の中身です。

//mydroid/dalvik/vm/alloc/Heap.c
void dvmCollectGarbageInternal(bool collectSoftReferences)
{
    ...
    // (0)これで全部のスレッドを停止させる
    dvmSuspendAllThreads(SUSPEND_FOR_GC);
 
    ...
    // (1)Rootから参照を辿る（Mark and Push）
    dvmHeapMarkRootSet();
 
    ...
    // (2)(3)(4)参照をドンドン辿る(Mark and Push)
    dvmHeapScanMarkedObjects();
 
    ...
    // (5)Markされていないオブジェクトを掃除
    dvmHeapSweepUnmarkedObjects(&numFreed, &sizeFreed);
 
    ...
    // (6)全スレッドを再開
    dvmResumeAllThreads(SUSPEND_FOR_GC);
}

絶対削除してはいけないオブジェクトがあります。
それらの参照元をRootセットと言っています。
例えば、実行途中のスタック内のローカル変数であったり、
現在停止中のThreadオブジェクトであったり、GCで管理しない領域であったりします。
こいつらの参照先オブジェクトを消すとDangling Pointerになっちゃいます。

以下がRootセットの全部っぽいです。

//mydroid/dalvik/vm/alloc/MarkSweep.c
/* Mark the set of root objects.
 *
 * Things we need to scan:
 * - System classes defined by root classloader
 * - For each thread:
 *   - Interpreted stack, from top to "curFrame"
 *     - Dalvik registers (args + local vars)
 *   - JNI local references
 *   - Automatic VM local references (TrackedAlloc)
 *   - Associated Thread/VMThread object
 *   - ThreadGroups (could track & start with these instead of working
 *     upward from Threads)
 *   - Exception currently being thrown, if present
 * - JNI global references
 * - Interned string table
 * - Primitive classes
 * - Special objects
 *   - gDvm.outOfMemoryObj
 * - Objects allocated with ALLOC_NO_GC
 * - Objects pending finalization (but not yet finalized)
 * - Objects in debugger object registry
 *
 * Don't need:
 * - Native stack (for in-progress stuff in the VM)
 *   - The TrackedAlloc stuff watches all native VM references.
 */

結構ありますね。これらから参照されるオブジェクトは消しちゃダメなので、
MarkしてスタックにPushしておきます。

MarkしてスタックにPushする関数も見ておきます。

//mydroid/dalvik/vm/alloc/MarkSweep.c
#define MARK_STACK_PUSH(stack, obj) \
    do { \
        *--(stack).top = (obj); \
    } while (false)
 
//{{ 中略 }}
 
static void
_markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
        bool checkFinger, bool forceStack)
{
    if (!setAndReturnMarkBit(ctx, hc)) {
        /* This object was not previously marked.
         */
        if (forceStack || (checkFinger && (void *)hc < ctx->finger)) {
            /* This object will need to go on the mark stack.
             */
            MARK_STACK_PUSH(ctx->stack, obj);
        }
...

分かりやすい関数名ですね。
Markしていないオブジェクトについては、setAndReturnMarkBit()でMarkして、
MARK_STACK_PUSH()でスタックにPushです。
Mark済みのオブジェクトはsetAndReturnMarkBit()がfalseを返すのでスタックにPushしません。

ずっとMarkって言ってますが、実際はオブジェクトにどうやってマークするのでしょうか？
Java VMの場合はオブジェクトのヘッダ部分にmark領域があって、そこに印を付けます。
でもDalvikは違います。
ヒープにはそんな余計な領域を作らず、別に管理用領域を設けています。
そこでオブジェクトの位置やマークやらを管理しています。
詳しくは、Google I/Oの資料をご覧下さい。
プレゼン資料の28ページ目ぐらいからです。

<追記(2009.03.15)>
Dalvikのソースコード中にWITH_OBJECT_HEADERSという記述が散見されます。
#define WITH_OBJECT_HEADERS 0
と無効化されているのですが、これはDalvikの開発途上ではオブジェクトにヘッダーを持たせる
実装方法を試みていた名残のようです。

管理構造をビットマップとか言ったりします。
これを実装しているのが//mydroid/dalvik/vm/alloc/HeapBitmap.{h|c}です。

オブジェクト管理用のビットマップとマーク用のビットマップがあります。
オブジェクト管理ビットマップはオブジェクトがメモリ上のどこに配置されているかを記憶しています。
マーク用ビットマップはそれに対応するマークを管理します。
つまり、それぞれが１対１に対応しています。

オブジェクトのメモリアドレスからオブジェクト管理ビットマップのインデックスが引けます。
このインデックスに対応するマーク用ビットマップの位置にマークします。
これでオブジェクトにマークしたことになります。

ここまで長かったですが、とりあえずRootセットから参照されているオブジェクトをMarkできました。
Markされたオブジェクトはスタックに積まれている状態です。
あとは、このスタックからオブジェクトをPopして、
そこから辿れるMarkされていないオブジェクトをMarkして、
スタックにPushです。
これを繰り返すだけです。
実装はとても簡単です。

//mydroid/dalvik/vm/alloc/MarkSweep.c
static void
processMarkStack(GcMarkContext *ctx)
{
    ...
    while (ctx->stack.top != base) {
        scanObject(*ctx->stack.top++, ctx);
    }
}

MARK_STACK_PUSH()でスタックをデクリメントしたので、ここではインクリメントしてPopを実現しています。
このscanObject()でオブジェクトのインスタンスフィールドを計算し、
そこから参照できるオブジェクトに対して、_markObjectNonNullCommon()を呼出しています。
スタックに何も入っていない状態になるまでこれを繰り返します。

マークされていないオブジェクトは全部必要ないので掃除します。
掃除は簡単、マーク用ビットマップを調べて、マークされていない場所を見つけます。
それに対応するオブジェクト管理ビットマップを探します。
そこからオブジェクトのアドレスを計算できるので、その領域を削除するだけ。
削除といっても管理ビットマップの当該インデックスをクリアするだけですが…

ちなみに、このゴミ集め手法はBitwise Sweepとか言われてたりします。
JavaVMのMark-Sweep GCはスライドコンパクションという方法でゴミ集めします。
歯抜けになったヒープを、左から順に詰めて行く作業です。
ゴミを上書きして、領域を解放しています。事実上、生きているオブジェクトを集めています。
なので、Mark-Sweep Compact GCとも言われます。
想像に易いですが、オブジェクトが移動しまくるので重いです。
Dalvik VMの場合はコレがないのでちょっと軽いようです。
その代わり、Allocationするときはオブジェクト管理ビットマップの操作が入るので若干重いはずです。
Java VMのAllocationはヒープの端っこを移動するだけで領域確保できるので比較的軽いです。

簡単に説明しようとしたら、結構掛かっちゃいましたね（汗
分かり難かったらごめんなさい。
間違ってる場所があったら教えて下さい。

特殊参照とかMutexLockだとかをすっ飛ばして概要だけです。
もっと詳しく知りたい方はソースをどうぞ。
Cですが分かりやすく書かれているので読みやすいです。

では、Enjoy Reading!

Tweet

• AndroidでWebマッシュアップ開発の基礎
• Baiduへ転職しました
• 空中に文字を書くアプリ「Air Writer」 続
• 「simeji」をAndroid SDK1.5のソフトキーボードに対応しました
• トラックボールのない端末でもカーソルを簡単に移動する方法 [Xperia_Report]
• Androidでベル打ち
• Androidアプリ開発者に絶対オススメのレイアウト本「Android Layout Cookbook」