Dalvik仮想マシンにおけるDexClassLookup構造解析

Androidシステムでは、すべてのクラス定義および具体的なコードがDEXファイルに含まれています.しかし、機能の豊富なプログラムは往々にして複雑で、多くのクラスから構成されている.
各クラスは、クラス記述子(Class Descriptor)と呼ばれる文字列によって一意に識別され、2つのクラスに同じクラス記述子があるはずがない.クラス記述子には、クラス名だけでなく、クラスが存在するパッケージ名も含まれます.たとえば、クラス名が「com.trendmicro.mars」でクラス名が「Test」の場合、このクラスのクラス記述子は「Lcom/trendmicro/mars/Test;」です.
ただし、1つのDEXファイル内の多くのクラスから使用したいクラスを見つけ、DEXファイル内のすべてのクラスのクラス記述子文字列を1つずつ比較するだけでは、速度が遅くなり、ユーザー体験が悪くなることがよくあります.
Dalvik仮想マシンはこの問題を解決するために、DEXファイルをロードして検証するときに、いわゆるDexClassLookup構造体を生成し、クラスの検索速度を速めることができます.

struct DexClassLookup {
    int     size;
    int     numEntries;
    struct {
        u4      classDescriptorHash;
        int     classDescriptorOffset;
        int     classDefOffset;
    } table[1];
};

構造体は最初はint型のsizeで、このDexClassLookup構造体がいったい何バイトの空間を占有するかを示しています.このサイズにはsize変数自体の4バイトも含まれています.
次のint型numEntriesは、DexClassLookupにどれだけのエントリが含まれているかを示します.
最後に、特定のデータを格納する内部構造体を定義します.ただしtable[1]は、DexClassLookupにこの構造体データが1つしか含まれていないことを示すものではなく、ここでは次の配列のみを示し、具体的に何個あるかは、前のnumEntriesによって指定されている.
次に、この構造体がどのように生成されているかを見てみましょう(コードはdalviklibdexDexFile.cpp内にあります):

DexClassLookup* dexCreateClassLookup(DexFile* pDexFile)
{
    DexClassLookup* pLookup;
    int allocSize;
    int i, numEntries;
    int numProbes, totalProbes, maxProbes;

    numProbes = totalProbes = maxProbes = 0;

    assert(pDexFile != NULL);

    numEntries = dexRoundUpPower2(pDexFile->pHeader->classDefsSize * 2);
    allocSize = offsetof(DexClassLookup, table)
                    + numEntries * sizeof(pLookup->table[0]);

    pLookup = (DexClassLookup*) calloc(1, allocSize);
    if (pLookup == NULL)
        return NULL;
    pLookup->size = allocSize;
    pLookup->numEntries = numEntries;

    for (i = 0; i < (int)pDexFile->pHeader->classDefsSize; i++) {
        const DexClassDef* pClassDef;
        const char* pString;

        pClassDef = dexGetClassDef(pDexFile, i);
        pString = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);

        classLookupAdd(pDexFile, pLookup,
            (u1*)pString - pDexFile->baseAddr,
            (u1*)pClassDef - pDexFile->baseAddr, &numProbes);

        if (numProbes > maxProbes)
            maxProbes = numProbes;
        totalProbes += numProbes;
    }

    ...

    return pLookup;
}

コードは、まず、どのくらいのデータを格納するかを決定します.注意:クラスが複数あるからといって、エントリが複数生成されるわけではありません.具体的に生成されたエントリ数は、クラスの個数に2を乗じ、次の2のべき乗次数を計算することがわかります.たとえば、私が5つのクラスを持っている場合、まず2を乗じて10を得、次の2のべき乗次数が16であれば、16のエントリが生成されます.どうしてそうするの?ハンシュの衝突を最小限に抑えるためだと思います.
何個のデータを作成するかが分かれば、この構造体データを格納するためにどれだけの空間を開くか(現在の定義では、割り当て空間の計算式は8+numEntries*12)がわかり、メモリに連続した空間が割り当てられます.次に、DexClassLookup構造体の最初の2つの変数sizeとnumEntriesに値を割り当てます.
最後に、具体的なデータを記入します.プログラムでは、DEXファイルに含まれる各クラスを巡回し、それらのDexClassDef構造とクラス記述子を1つずつ取得し、classLookupAdd関数に渡して、そのクラスに対する迅速な検索データを記入させます(コードはdalviklibdexDexFile.cpp内にあります):

static void classLookupAdd(DexFile* pDexFile, DexClassLookup* pLookup,
    int stringOff, int classDefOff, int* pNumProbes)
{
    const char* classDescriptor =
        (const char*) (pDexFile->baseAddr + stringOff);
    const DexClassDef* pClassDef =
        (const DexClassDef*) (pDexFile->baseAddr + classDefOff);
    u4 hash = classDescriptorHash(classDescriptor);
    int mask = pLookup->numEntries-1;
    int idx = hash & mask;

    int probes = 0;
    while (pLookup->table[idx].classDescriptorOffset != 0) {
        idx = (idx + 1) & mask;
        probes++;
    }

    pLookup->table[idx].classDescriptorHash = hash;
    pLookup->table[idx].classDescriptorOffset = stringOff;
    pLookup->table[idx].classDefOffset = classDefOff;
    *pNumProbes = probes;
}

関数はまずclassDescriptor Hashを呼び出し、クラス記述子に対応するHash値を計算します.これは数値です.
そして,コードはエントリ数の多少に基づいて1つのmaskを算出し,先に計算したHash値と以下を用いて,そのエントリデータが配列に格納されている位置の下付き文字を算出する.前述したように,データのエントリ数は必ず2のべき乗次数である.例えば、8であれば、下付きの値はHashが3位、16であればHashが4位となります.これは,なぜ高速検索データのエントリ数が2のべき乗次数でなければならないのかを説明する.
次に、配列内のこの下付き文字に対応するエントリが別のクラスの情報を格納しているかどうかを見てみましょう.この場合,衝突であり,2つの異なるクラスが同じ数字にマッピングされる.いったん衝突が発生したら、プログラムは非常に簡単な処理方法を使って、直接下標に1を加えて、maskともう一度付き合って、次に保存しようとする位置を得て、もう一度最初に判断して、使われていない位置を見つけるまで.しかしながら、このような処理は、他のクラスが格納すべき位置を占め、性能を低下させる可能性がある.したがって,前のコードはエントリ数を計算する際に人為的に2を乗じ,衝突の確率を低減する.しかし、このように処理すると、ストレージスペースが浪費されます.最後に、空の位置が見つかった場合、前述のクラス記述子Hash値、クラス記述子文字列、およびそのクラスのDexClassDefのDEXファイルヘッダに対するオフセット量などの情報を含む対応するクラスの具体的なデータが、その位置に格納される.
では、DexClassLookup構造体データの生成方法を見てから、Dalvik仮想マシンがクラスの検索速度を速めるためにどのように利用しているかを見てみましょう(コードはdalviklibdexDexFile.cpp内にあります):

const DexClassDef* dexFindClass(const DexFile* pDexFile,
    const char* descriptor)
{
    const DexClassLookup* pLookup = pDexFile->pClassLookup;
    u4 hash;
    int idx, mask;

    hash = classDescriptorHash(descriptor);
    mask = pLookup->numEntries - 1;
    idx = hash & mask;

    while (true) {
        int offset;

        offset = pLookup->table[idx].classDescriptorOffset;
        if (offset == 0)
            return NULL;

        if (pLookup->table[idx].classDescriptorHash == hash) {
            const char* str;

            str = (const char*) (pDexFile->baseAddr + offset);
            if (strcmp(str, descriptor) == 0) {
                return (const DexClassDef*)
                    (pDexFile->baseAddr + pLookup->table[idx].classDefOffset);
            }
        }

        idx = (idx + 1) & mask;
    }
}

検索するコードは簡単ですが、まずクラスを検索するクラス記述子に対して、同じアルゴリズムでHash値を計算し、エントリの数に応じてHash値の低いビットを取ります.この値を下にして、配列内の対応する位置のデータを読み込んでみます.衝突が起こらなければ、一度に探しているクラスを見つけることができます.衝突がある場合は、次の位置の情報をループしてみましょう.したがって,検索時に文字列の1文字ずつの比較を1つの4バイトの数字に変換した比較であり,速度が大幅に速くなったことがわかる.
DEXファイルごとに、最初に計算するだけでいいので、ロードするたびに計算する必要はありません.ご存知のように、1つのDEXファイルが最初にロードされたとき、Dalvikは仮想的に検証と最適化を行い、後でこのDEXファイルを再ロードするときに、最適化されたODEXファイルを直接読み取ることができ、ロード速度を速めることができます.ODEXファイルには、このDEXファイルに対応したDexClassLookup構造体データが含まれており、直接mmapをメモリに入れればよいので、これ以上計算する必要はありません.
ここでは、なぜDEXファイルに対応するDexClassLookup構造体データが直接含まれていないのか、ELFファイルのように説明します.理論的には、これらは静的データなので、実行時に変更されません.唯一の解釈はAndroidが迅速に検索する機能とDEXを縛り付けたくないのではなく、Dalvik仮想マシン自身が実現していると思います.これにより、異なるバージョンの仮想マシンは、異なる高速検索アルゴリズムを完全に使用することができます.