Android

Rest Term::Tech Note

このページではAndroidアプリ開発関連のメモを書いています。

エミュレータ関連

エミュレータ操作のためのショートカットキー

ネットワークアドレス

エミュレータを動作させている開発環境とネットワーク通信を行いたい場合は上記の通り''10.0.2.2''を参照すれば良いです。

NDK(JNI)関連

JNIHelp

JNIで呼び出される関数名はパッケージ名、クラス名、メソッド名を連結した名前を付ける必要があり可読性を著しく損なう原因となっています。そこで、JNIから呼び出される関数をパッケージ単位で登録できる ''jniRegisterNativeMethods'' 関数を使うと便利です(以下抜粋)。

/* * Register native JNI-callable methods. * * "className" looks like "java/lang/String". */ int jniRegisterNativeMethods(JNIEnv* env, const char* className, const JNINativeMethod* gMethods, int numMethods) { jclass clazz; LOGV("Registering %s natives\n", className); clazz = (*env)->FindClass(env, className); if (clazz == NULL) { LOGE("Native registration unable to find class '%s'\n", className); return -1; } if ((*env)->RegisterNatives(env, clazz, gMethods, numMethods) < 0) { LOGE("RegisterNatives failed for '%s'\n", className); return -1; } return 0; } jint addVals(JNIEnv* env, jobject thiz, jint a, jint b) { return a + b; } jint subVals(JNIEnv* env, jobject thiz, jint a, jint b) { return a - b; } jint mulVals(JNIEnv* env, jobject thiz, jint a, jint b) { return a * b; } jint divVals(JNIEnv* env, jobject thiz, jint a, jint b) { return a / b; } static JNINativeMethod methods[] = { /* name, signature, func pointer */ {"addVals", "(II)I", (void*)addVals}, {"subVals", "(II)I", (void*)subVals}, {"mulVals", "(II)I", (void*)mulVals}, {"divVals", "(II)I", (void*)divVals}, }; EXPORT jint JNI_OnLoad(JavaVM* vm, void* reserved) { JNIEnv* env = NULL; if ((*vm)->GetEnv(vm, (void**)&env, JNI_VERSION_1_6) != JNI_OK) { return -1; } jniRegisterNativeMethods(env, "{パッケージ/クラス名}", methods, NELEM(methods)); return JNI_VERSION_1_6; }

最適化

コンパイル時に指定できる最適化関連のオプション

$ arm-linux-androideabi-g++  --target-help
The following options are target specific:
 -mabi=                      Specify an ABI
 -mabort-on-noreturn         Generate a call to abort if a noreturn function
                             returns
 -mandroid                   Generate code for the Android platform.
 -mapcs-float                Pass FP arguments in FP registers
 -mapcs-frame                Generate APCS conformant stack frames
 -mapcs-reentrant            Generate re-entrant, PIC code
 -march=                     Specify the name of the target architecture
 -mbig-endian                Assume target CPU is configured as big endian
 -mbionic                    Use Bionic C library
 -mcallee-super-interworking Thumb: Assume non-static functions may be called
                             from ARM code
 -mcaller-super-interworking Thumb: Assume function pointers may go to non-
                             Thumb aware code
 -mcirrus-fix-invalid-insns  Cirrus: Place NOPs to avoid invalid instruction
                             combinations
 -mcpu=                      Specify the name of the target CPU
 -mfix-cortex-m3-ldrd        Avoid overlapping destination and address
                             registers on LDRD instructions that may trigger
                             Cortex-M3 errata.
 -mfloat-abi=                Specify if floating point hardware should be used
 -mfp16-format=              Specify the __fp16 floating-point format
 -mfpu=                      Specify the name of the target floating point
                             hardware/format
 -mglibc                     Use GNU C library
 -mhard-float                Alias for -mfloat-abi=hard
 -mlittle-endian             Assume target CPU is configured as little endian
 -mlong-calls                Generate call insns as indirect calls, if
                             necessary
 -mpic-register=             Specify the register to be used for PIC addressing
 -mpoke-function-name        Store function names in object code
 -msched-prolog              Permit scheduling of a function's prologue
                             sequence
 -msingle-pic-base           Do not load the PIC register in function prologues
 -msoft-float                Alias for -mfloat-abi=soft
 -mstructure-size-boundary=  Specify the minimum bit alignment of structures
 -mthumb                     Compile for the Thumb not the ARM
 -mthumb-interwork           Support calls between Thumb and ARM instruction
                             sets
 -mtp=                       Specify how to access the thread pointer
 -mtpcs-frame                Thumb: Generate (non-leaf) stack frames even if
                             not needed
 -mtpcs-leaf-frame           Thumb: Generate (leaf) stack frames even if not
                             needed
 -mtune=                     Tune code for the given processor
 -muclibc                    Use uClibc C library
 -mvectorize-with-neon-quad  Use Neon quad-word (rather than double-word)
                             registers for vectorization
 -mword-relocations          Only generate absolute relocations on word sized
                             values.
 -mwords-little-endian       Assume big endian bytes, little endian words

 Known ARM CPUs (for use with the -mcpu= and -mtune= options):
   cortex-m0, cortex-m1, cortex-m3, cortex-m4, cortex-r4f, cortex-r4,
   cortex-a15, cortex-a9, cortex-a8, cortex-a5, arm1156t2f-s, arm1156t2-s,
   mpcore, mpcorenovfp, arm1176jzf-s, arm1176jz-s, arm1136jf-s, arm1136j-s,
   arm1026ej-s, arm926ej-s, fa726te, fmp626, fa626te, fa606te, iwmmxt2, iwmmxt,
   xscale, arm1022e, arm1020e, arm10e, arm968e-s, arm966e-s, arm946e-s, arm9e,
   arm1020t, arm10tdmi, ep9312, arm940t, arm922t, arm920t, arm920, arm9tdmi,
   arm9, arm740t, arm720t, arm710t, arm7tdmi-s, arm7tdmi, fa626, fa526,
   strongarm1110, strongarm1100, strongarm110, strongarm, arm810, arm8,
   arm7dmi, arm7dm, arm7m, arm7500fe, arm7500, arm7100, arm710c, arm720,
   arm710, arm700i, arm700, arm70, arm7di, arm7d, arm7, arm620, arm610, arm600,
   arm60, arm6, arm3, arm250, arm2

 Known ARM architectures (for use with the -march= option):
   iwmmxt2, iwmmxt, ep9312, armv7e-m, armv7-m, armv7-r, armv7-a, armv7,
   armv6-m, armv6t2, armv6zk, armv6z, armv6k, armv6j, armv6, armv5te, armv5e,
   armv5t, armv5, armv4t, armv4, armv3m, armv3, armv2a, armv2
Assembler options
=================

Use "-Wa,OPTION" to pass "OPTION" to the assembler.

ARM-specific assembler options:
 -k                      generate PIC code
 -mthumb                 assemble Thumb code
 -mthumb-interwork       support ARM/Thumb interworking
 -mapcs-32               code uses 32-bit program counter
 -mapcs-26               code uses 26-bit program counter
 -mapcs-float            floating point args are in fp regs
 -mapcs-reentrant        re-entrant code
 -matpcs                 code is ATPCS conformant
 -mbig-endian            assemble for big-endian
 -mlittle-endian         assemble for little-endian
 -mapcs-frame            use frame pointer
 -mapcs-stack-check      use stack size checking
 -mno-warn-deprecated    do not warn on use of deprecated feature
 -mcpu=<cpu name>        assemble for CPU <cpu name>
 -march=<arch name>      assemble for architecture <arch name>
 -mfpu=<fpu name>        assemble for FPU architecture <fpu name>
 -mfloat-abi=<abi>       assemble for floating point ABI <abi>
 -meabi=<ver>            assemble for eabi version <ver>
 -mimplicit-it=<mode>    controls implicit insertion of IT instructions
 -EB                     assemble code for a big-endian cpu
 -EL                     assemble code for a little-endian cpu
 --fix-v4bx              Allow BX in ARMv4 code

FPU(浮動小数点演算ユニット)関連のオプション

VFP/NEON関連のオプションです。

• ''ハードウェアFPUを利用''
  mfloat-abi オプションで指定します。

  -mfloat-abi=softfp

  を指定してコンパイルすると

  .fpu vfp
  
  ...
  fmsr s15, r3 @int
  fsitos s0, s15

  このようにVFP(Vector Floating-Point, ARMv6)命令を使います。

• ''FPUの指定''
  mfpu オプションで利用するFPUを指定できます。

  -mfloat-abi=softfp -mfpu=vfpv3-d16

  このようにFPU名を明示します。

  .fpu vfpv3-d16
   
  ...
  fmsr s15, r3 @int
  fsitos s0, s15

• ''NEONを利用したベクトル化''
  ベクトル化のオプションを追加指定します。

  -mfloat-abi=softfp -mfpu=neon -ftree-vectorize -mvectorize-with-neon-quad

  mfpu オプションでNEONを指定し、ftree-vectorize オプションでループのベクトル化を、mvectorize-with-neon-quad オプションでQレジスタ(128bitレジスタ)を利用するように指定します。

  .fpu neon
  
  ...
  vmla.i32  q8, q10, q9
  vst1.32 {q8}, [ip]!

  これでNEON(ARMv7)命令を使うようになります。-mfloat-abi=softfp は値の名前で勘違いしそうですが、浮動小数点演算をエミュレーション実行しているわけではなくハードウェア(FPU)で演算してくれます。このオプションはABI(Application Binary Interface)を指定するもので、関数呼び出し時のレジスタの使われ方が異なります。FPUがない(soft)場合との互換性が取れるように、ハードウェアFPUで関数によって演算が実行される場合でも浮動小数点引数は整数レジスタ(r)に渡されます。
  参考: ハードウェア VFP 命令の使用

数学演算関連のオプション

• ffast-math オプション
  これはAndroid特有のものではなくGCC一般の最適化オプションです。このオプションを指定すると次のオプションを一度に指定したことになります。

  -fno-math-errno
  -funsafe-math-optimizations
  -fno-trapping-math
  -ffinite-math-only
  -fno-signaling-nans

  実行速度最適化のためANSIやIEEEの規則や仕様を破ることをGCCに許します。例えば、sqrt 関数の引数が負にならないと仮定したりとか。結果として浮動小数点演算の精度が変わってしまうような最適化でも行うようになります。精度を重視する場合は指定しないようにしましょう。O3オプションを併せて指定されることが多いです。

ndk-buildコマンド

ndk-buildをコマンドラインから実行する際にコンパイルオプションなどを標準出力で確認したい場合は

$ ndk-build V=1

のように Vオプション を指定すれば確認できます。

開発での注意点、SDKバグ関連

XMLパーサー

Android 4.0 (Ice Cream Sandwich) から''XmlPullParser''のコア部分が変更となったため(バグの多いExpatPullParserが削除されKXmlParserに統一)、Android 3.2以前のプロジェクトで動作していたXMLを扱うプログラムが4.0以降では動作しなくなる可能性があります。

参考: Watch out for XmlPullParser.nextText()

画像処理/カメラ関連

画像処理を行うAndroidアプリ開発はメモリとの戦いです。とにかく OutOfMemory エラーが多発します。。

• android.graphics.BitmapFactory public class BitmapFactory { private static final int DECODE_BUFFER_SIZE = 16 * 1024; // デコード用バッファが16KB ... 省略 if (!is.markSupported()) { is = new BufferedInputStream(is, DECODE_BUFFER_SIZE); } if (tempStorage == null) tempStorage = new byte[16 * 1024]; // テンポラリストレージが16KB ... 省略 bm = nativeDecodeStream(is, tempStorage, outPadding, opts, true, scale); 画像のデコードに合計32KBしか使えない模様。ただし、tempStorage の方は任意に指定できる(?

• カメラデバイスオープン時の注意点
  カメラデバイスを開くときに(android.hardware.Camera#open)、API Level 11(Android 3.0)未満ではカメラ処理の種類を明示的に指定(android.view.SurfaceHolder#setType)しておかないとアプリが落ちてしまいます。

final SurfaceHolder holder = getHolder(); ## 以下の処理を忘れないように、これを忘れると2.x系ではカメラデバイスを開くときにアプリが落ちます holder.setType(SurfaceHolder.SURFACE_TYPE_PUSH_BUFFERS);

SURFACE_TYPE_PUSH_BUFFERS を指定すると「バッファに入れられた画像を画面表示する(カメラプレビュー)」という処理になります。

OpenCV for Android

OpenCV for Androidについては別ページに。

Androidソースコードリーディング

まだ殴り書きのメモ段階です、コードリーディングを進めながら整理していきます

Androidのソースコードリーディングを進めています。
Welcome to Android

• 構成 platform

  bionic         glibc互換 Cライブラリ
  bootable       ブート関連
  build          ビルドツール
  cts            互換性確認ツール
  dalvik         仮想マシン(DalvikVM)
  development    開発ツール(エミュレータとか)
  device         デバイス関連ファイル
  external       外部で開発されたソフトなど
  frameworks     Android フレームワーク
  hardware       ハードウェア制御ライブラリ
  ndk            Native Development Kit
  packages       標準インストールアプリ
  prebuilt       ビルドツール(ビルド済)
  sdk            Android SDK
  system         デバイスドライバのソース

• 名前の由来
  「GoogleのDan Bornsteinが自作の仮想マシンに付けたDalvikという名前は、祖先がむかし住んでいたアイスランドの漁村の名に由来している。」 とのこと。

• きっかけ
  主にNDK(JNI)を用いた開発中、スタックトレースに見慣れない単語(Zygoteなど)が頻発するため中身を知りたいと思ったから。

  at com.android.internal.os.ZygoteInit.main
  at dalvik.system.NativeStart.main

  とか、あとは画像処理アプリを作っているときはよくメモリが足りなくてつまづくことが多いです。

  ERROR/dalvikvm-heap(187): 2457600-byte external allocation too large for this process.
  ERROR/(187): VM won't let us allocate 2457600 bytes…
  ERROR/AndroidRuntime(187): java.lang.OutOfMemoryError: bitmap size exceeds VM budget

  などのエラー

Zygote

Androidアプリケーションはマルチタスクで実行することができますが、ここではその仕組みを調べます。

Androidを起動すると、まずZygote(ザイゴウト)というプロセスが立ち上がります(いわゆるinitプロセス)。このZygoteはすべてのAndroidアプリケーションの親プロセスになっています。アプリケーションを起動するには下図のようにZygoteから fork して子プロセスを作ります。

Zygoteは多くのライブラリを含んでいるため起動には時間がかかりますが、その後の子プロセス生成は非常に高速に行うことができます。また、子プロセスは親プロセスとメモリ領域を共有するためメモリ消費量も節約できます。

ここで、Zygoteプロセス起動からのフローを整理します。

• init.rc

  service zygote /system/bin/app_process -Xzygote /system/bin --zygote --start-system-server

  initでサービスを起動します。エントリーポイントは以下のようになっています。
• frameworks/base/cmds/app_process/app_main.cpp int main(int argc, const char* const argv[]) { // ProcessState.cpp で定義されているグローバル変数 mArgC = argc; mArgV = argv; mArgLen = 0; for (int i=0; i<argc; i++) { mArgLen += strlen(argv[i]) + 1; } mArgLen--; // ランタイム本体, 実装は base/core/jni/AndroidRuntime.cpp AppRuntime runtime; const char* argv0 = argv[0]; argc--; argv++; int i = runtime.addVmArguments(argc, argv); // コマンドライン引数のパース bool zygote = false; bool startSystemServer = false; bool application = false; const char* parentDir = NULL; const char* niceName = NULL; const char* className = NULL; while (i < argc) { const char* arg = argv[i++]; if (!parentDir) { parentDir = arg; } else if (strcmp(arg, "--zygote") == 0) { zygote = true; niceName = "zygote"; } else if (strcmp(arg, "--start-system-server") == 0) { startSystemServer = true; } else if (strcmp(arg, "--application") == 0) { application = true; } else if (strncmp(arg, "--nice-name=", 12) == 0) { niceName = arg + 12; } else { className = arg; break; } } if (niceName && *niceName) { setArgv0(argv0, niceName); set_process_name(niceName); } runtime.mParentDir = parentDir; if (zygote) { // --zygote --start-system-server の場合、ここでZygoteを起動 runtime.start("com.android.internal.os.ZygoteInit", startSystemServer ? "start-system-server" : ""); } else if (className) { runtime.mClassName = className; runtime.mArgC = argc - i; runtime.mArgV = argv + i; runtime.start("com.android.internal.os.RuntimeInit", application ? "application" : "tool"); } else { fprintf(stderr, "Error: no class name or --zygote supplied.\n"); app_usage(); LOG_ALWAYS_FATAL("app_process: no class name or --zygote supplied."); return 10; } } Zygoteを起動する AppRuntime#start の中身は以下のようになっています。JNI経由でJava側の static void main(String[] args) を呼び出しています。
• frameworks/base/core/jni/AndroidRuntime.cpp // Androidランタイムの開始 // VMを起動してJava側の main メソッドを呼び出す void AndroidRuntime::start(const char* className, const char* options) { ALOGD("\n>>>>>> AndroidRuntime START %s <<<<<<\n", className != NULL ? className : "(unknown)"); blockSigpipe(); /* * 'startSystemServer == true' means runtime is obsolete and not run from * init.rc anymore, so we print out the boot start event here. */ if (strcmp(options, "start-system-server") == 0) { /* track our progress through the boot sequence */ const int LOG_BOOT_PROGRESS_START = 3000; LOG_EVENT_LONG(LOG_BOOT_PROGRESS_START, ns2ms(systemTime(SYSTEM_TIME_MONOTONIC))); } const char* rootDir = getenv("ANDROID_ROOT"); if (rootDir == NULL) { rootDir = "/system"; if (!hasDir("/system")) { LOG_FATAL("No root directory specified, and /android does not exist."); return; } setenv("ANDROID_ROOT", rootDir, 1); } //const char* kernelHack = getenv("LD_ASSUME_KERNEL"); //ALOGD("Found LD_ASSUME_KERNEL='%s'\n", kernelHack); // VMを起動する JNIEnv* env; if (startVm(&mJavaVM, &env) != 0) { return; } onVmCreated(env); // 関数の登録 if (startReg(env) < 0) { ALOGE("Unable to register all android natives\n"); return; } // Java側の main メソッドを呼び出す準備 jclass stringClass; jobjectArray strArray; jstring classNameStr; jstring optionsStr; stringClass = env->FindClass("java/lang/String"); assert(stringClass != NULL); strArray = env->NewObjectArray(2, stringClass, NULL); assert(strArray != NULL); classNameStr = env->NewStringUTF(className); assert(classNameStr != NULL); env->SetObjectArrayElement(strArray, 0, classNameStr); optionsStr = env->NewStringUTF(options); env->SetObjectArrayElement(strArray, 1, optionsStr); // このスレッドはVMのメインスレッドになる、VMが終了するまで戻らない char* slashClassName = toSlashClassName(className); jclass startClass = env->FindClass(slashClassName); if (startClass == NULL) { ALOGE("JavaVM unable to locate class '%s'\n", slashClassName); /* keep going */ } else { // 呼び出すメソッドのIDを取得 (main メソッド) jmethodID startMeth = env->GetStaticMethodID(startClass, "main", "([Ljava/lang/String;)V"); // String型の配列を表す if (startMeth == NULL) { ALOGE("JavaVM unable to find main() in '%s'\n", className); /* keep going */ } else { // JNIでJavaの static void main(String[] args) を呼び出す env->CallStaticVoidMethod(startClass, startMeth, strArray); #if 0 if (env->ExceptionCheck()) threadExitUncaughtException(env); #endif } } free(slashClassName); ALOGD("Shutting down VM\n"); if (mJavaVM->DetachCurrentThread() != JNI_OK) ALOGW("Warning: unable to detach main thread\n"); if (mJavaVM->DestroyJavaVM() != 0) ALOGW("Warning: VM did not shut down cleanly\n"); } 続きは調べつつ書きます。

ashmem (Anonymouse Shared memory Subsystem)

Androidにおける共有メモリ用デバイスで、Linuxカーネルに組み込まれています。ashmem からメモリを確保するには /dev/ashmem をオープンして mmap を使います。mmap を行うと ashmem デバイスを通じて最終的に tmpfs からデータを取得します。

ashmem API

ashmemの機能は libcutils.so に含まれています。

• system/core/include/cutils/ashmem.h
  ashmemの提供するAPIは以下の5つ。内部では ioctl でデバイスドライバに情報を渡しているだけ。 // ASHMEM_SET_NAME, ASHMEM_SET_SIZE (/dev/ashmem リクエストコード) int ashmem_create_region(const char *name, size_t size); // ASHMEM_SET_PROT_MASK int ashmem_set_prot_region(int fd, int prot); // ASHMEM_PIN int ashmem_pin_region(int fd, size_t offset, size_t len); // ASHMEM_UPIN int ashmem_unpin_region(int fd, size_t offset, size_t len); // ASHMEM_GET_SIZE int ashmem_get_size_region(int fd); 共有メモリ領域生成には以下のように ashmem_create_region で返ってくるファイルディスクリプタを mmap に渡します。 // int ashmem_create_region(const char *name, size_t size); // 新しく共有メモリ領域を生成してファイルディスクリプタを返す // name: 領域に付けるラベル名、size: 領域のサイズ int fd = ashmem_create_region("my_shm_region", size); if(fd < 0) { //無効なファイルディスクリプタ } char* data = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); if(data == MAP_FAILED) { // マッピング失敗 } 他のプロセスから共有メモリを使うには binder (Android独自のデバイスドライバ)経由で使うようです。要調査。

Android SDKではJavaから ashmem を利用するために、''android.os.MemoryFile'' クラスが提供されています。アプリケーションキャッシュなどに利用すると良いです。また、 ashmem はグラフィックメモリのバッファなどでも利用されているとのことです。

binder

プロセス間通信
atodekaku

bionic

bionic はAndroidのCライブラリです。 glibc は組み込み向けには大きすぎるため BSD libc をAndroid向けに改良したライブラリが用いられています。

dlmalloc

(ここではv2.8.6を対象としています)
bionic にはDoug Leaという方が作った通称 dlmalloc と呼ばれるメモリ確保機構が含まれています。dlmalloc は速度と空間効率を両立したアルゴリズムを採用しており、フラグメンテーションの問題を最小限にします。スマートフォンデバイスのような組み込み環境に適しているとのことです。

• platform/bionic/libc/upstream-dlmalloc /* mspace is an opaque type representing an independent region of space that supports mspace_malloc, etc. */ typedef void* mspace; /* create_mspace creates and returns a new independent space with the given initial capacity, or, if 0, the default granularity size. It returns null if there is no system memory available to create the space. If argument locked is non-zero, the space uses a separate lock to control access. The capacity of the space will grow dynamically as needed to service mspace_malloc requests. You can control the sizes of incremental increases of this space by compiling with a different DEFAULT_GRANULARITY or dynamically setting with mallopt(M_GRANULARITY, value). */ DLMALLOC_EXPORT mspace create_mspace(size_t capacity, int locked); /* mspace_malloc behaves as malloc, but operates within the given space. */ DLMALLOC_EXPORT void* mspace_malloc(mspace msp, size_t bytes); 以下のようにメモリ確保関数を #define して使うことができます。 /* * MSPACES If MSPACES is defined, then in addition to malloc, free, etc., this file also defines mspace_malloc, mspace_free, etc. These are versions of malloc routines that take an "mspace" argument obtained using create_mspace, to control all internal bookkeeping. If ONLY_MSPACES is defined, only these versions are compiled. So if you would like to use this allocator for only some allocations, and your system malloc for others, you can compile with ONLY_MSPACES and then do something like... */ static mspace mymspace = create_mspace(0,0); // for example #define mymalloc(bytes) mspace_malloc(mymspace, bytes) まず create_mspace() で指定したサイズ(capacity, 0ならデフォルトの粒度)の領域をあらかじめ確保し、そこから必要なサイズの領域を mspace_malloc()　で取得します。デフォルトで確保される領域については以下の通りです。 DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS, system_info.dwAllocationGranularity in WIN32, otherwise 64K. Also settable using mallopt(M_GRANULARITY, x) The unit for allocating and deallocating memory from the system. On most systems with contiguous MORECORE, there is no reason to make this more than a page. However, systems with MMAP tend to either require or encourage larger granularities. You can increase this value to prevent system allocation functions to be called so often, especially if they are slow. The value must be at least one page and must be a power of two. Setting to 0 causes initialization to either page size or win32 region size. (Note: In previous versions of malloc, the equivalent of this option was called "TOP_PAD") // MORECORE_CONTIGUOUS では size_t が4bytesの場合 // (size_t)64U * (size_t)1024U = 4224bytes #else /* MORECORE_CONTIGUOUS */ #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U) フリーリストは''循環双方向リンクリスト''あるいは''トライ木(trie)''(内部では bin と呼ばれている)で管理されています。チャンク(リストのノード)のサイズは、フリーチャンクの最後の4バイトにも記録されています。これを活用して隣接するフリーチャンクを結合してメモリの断片化を避けています。各binはサイズ別にチャンクを管理しており、求めるサイズのチャンクをすばやく探せるようになっています。チャンクを解放するとき、可能であれば隣り合うフリーチャンクと結合させます(断片化防止)。解放するチャンクの直前または直後に位置するチャンクがフリーであれば、そのフリーチャンクはbinから外され、解放しようとしているチャンクと結合して適切なbinに配置されます。チャンクの構造は以下のようになっています。 // 小さいチャンクは循環双方向リンクリストで管理 "Small" chunks are stored in circular doubly-linked lists, and look like this: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space (may be 0 bytes long) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ // P は PINUE_BIT と呼ばれ、前のチャンクが割り当て済みかを示すビット(0:フリー, 1:割り当て済み) // 大きいチャンク(256bytes以上)はトライ木で管理 Larger chunks are kept in a form of bitwise digital trees (aka tries) keyed on chunksizes. Because malloc_tree_chunks are only for free chunks greater than 256 bytes, their size doesn't impose any constraints on user chunk sizes. Each node looks like: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk of same size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk of same size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pointer to left child (child[0]) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pointer to right child (child[1]) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pointer to parent | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | bin index of this chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ // チャンクは malloc_chunk/malloc_tree_chunk 構造体として定義されている // 循環双方向リンクリスト struct malloc_chunk { size_t prev_foot; /* Size of previous chunk (if free). */ size_t head; /* Size and inuse bits. */ struct malloc_chunk* fd; /* double links -- used only if free. */ struct malloc_chunk* bk; }; // トライ木(trie) struct malloc_tree_chunk { /* The first four fields must be compatible with malloc_chunk */ size_t prev_foot; size_t head; struct malloc_tree_chunk* fd; struct malloc_tree_chunk* bk; struct malloc_tree_chunk* child[2]; struct malloc_tree_chunk* parent; bindex_t index; }; 実は glibc malloc は dlmalloc から派生したもの、歴史はとても古いのです。シンプルな仕組みなのに効率が良く、現在でも広く利用されています。詳細は本家サイトにて、図付きでわかりやすいです。
  A Memory Allocator

DEXファイルフォーマット

Androidアプリは、それぞれが独自のLinuxプロセス内で実行され、それらのプロセスが個々にDalvik VMのインスタンスをホストしています。Dalvikは、デバイスが複数の仮想マシンを同時に効率よく実行できるように設計されています。効率が良い理由は、主にDalvikがDEX(Dalvik Executable)ベースのファイルを実行するからです。DEXはメモリの占有を最小限に抑えるよう最適化されたフォーマットです。
.dex — Dalvik Executable Format

データ型

DEXファイルフォーマットで扱えるデータ型は以下の11種類です。また、バイトオーダーはリトルエンディアンとなっています。

LEB128(Little-Endian Base 128)では可変長整数を扱います。これは DWARF3 フォーマットを参考にしたもので以下のような構造(2バイトの場合)になっています。

| Bitwise diagram of a two-byte LEB128 value                                                                  |
| First byte                                         | Second byte                                            |
| 1 | bit6 | bit5 | bit4 | bit3 | bit2 | bit1 | bit0 | 0 | bit13 | bit12 | bit11 | bit10 | bit9 | bit8 | bit7 |

各バイトの7ビットがデータで最上位ビットを使ってデータの終端を示しています。上の例だと2バイト目の最上位ビットが落ちているため、ここでこのデータは終了ということになります。値の大きさによってデータ長も変化するので、小さな整数値だとデータ長も短くなります。LEB128のような可変長整数の扱い方は特に珍しくはなく、バイナリネットワークプロトコルだとよく見かけます(thriftとか)。

ファイルレイアウト

内部のセクションは以下のようになっています。

型のシグネチャはJNIを利用するときにもよく目にします。以下にシグネチャと型の対応を載せます。

最後の配列型は例えば "[I" ならint型配列、"[D" ならdouble型配列を表します。

''Dalvik VMはJavaバイトコードを実行しません。''コンパイルされたJavaのクラスファイル(.class)をDEXファイル(.dex)に変換して生成されたバイトコードが実行されます。

• ''dx''
  classファイルをdexファイルに変換できるコマンド。Android SDKに入っています。

  $ dx
  usage:
   dx --dex [--debug] [--verbose] [--positions=<style>] [--no-locals]
   [--no-optimize] [--statistics] [--[no-]optimize-list=<file>] [--no-strict]
   [--keep-classes] [--output=<file>] [--dump-to=<file>] [--dump-width=<n>]
   [--dump-method=<name>[*]] [--verbose-dump] [--no-files] [--core-library]
   [--num-threads=<n>] [--incremental] [--force-jumbo]
   [<file>.class | <file>.{zip,jar,apk} | <directory>] ...
     Convert a set of classfiles into a dex file, optionally embedded in a
     jar/zip. Output name must end with one of: .dex .jar .zip .apk. Positions
     options: none, important, lines.
   dx --annotool --annotation=<class> [--element=<element types>]
   [--print=<print types>]
   dx --dump [--debug] [--strict] [--bytes] [--optimize]
   [--basic-blocks | --rop-blocks | --ssa-blocks | --dot] [--ssa-step=<step>]
   [--width=<n>] [<file>.class | <file>.txt] ...
     Dump classfiles, or transformations thereof, in a human-oriented format.
   dx --find-usages <file.dex> <declaring type> <member>
     Find references and declarations to a field or method.
     declaring type: a class name in internal form, like Ljava/lang/Object;
     member: a field or method name, like hashCode
   dx -J<option> ... <arguments, in one of the above forms>
     Pass VM-specific options to the virtual machine that runs dx.
   dx --version
     Print the version of this tool (1.7).
   dx --help
     Print this message.

  実際にAndroidプロジェクトディレクトリで以下のようにコマンドを実行してみます。--output オプションで出力ファイル名を指定し、その後に変換対象のclassファイルを含んだディレクトリを指定します。

  $ dx --dex --verbose --output=classes.dex bin/classes
  ignored resource bin/classes/./.DS_Store
  ignored resource bin/classes/./com/.DS_Store
  ignored resource bin/classes/./com/example/.DS_Store
  processing bin/classes/./com/example/hellojni/BuildConfig.class...
  processing bin/classes/./com/example/hellojni/MainActivity$1.class...
  processing bin/classes/./com/example/hellojni/MainActivity$2.class...
  processing bin/classes/./com/example/hellojni/MainActivity.class...
  processing bin/classes/./com/example/hellojni/R$attr.class...
  processing bin/classes/./com/example/hellojni/R$drawable.class...
  processing bin/classes/./com/example/hellojni/R$id.class...
  processing bin/classes/./com/example/hellojni/R$layout.class...
  processing bin/classes/./com/example/hellojni/R$menu.class...
  processing bin/classes/./com/example/hellojni/R$string.class...
  processing bin/classes/./com/example/hellojni/R$style.class...
  processing bin/classes/./com/example/hellojni/R.class...

  カレントディレクトリに classes.dex ファイルが生成されていたら成功です。このdexファイルは後述の dexdump コマンドで中身を覗くことができます。

Dalvik VMバイトコード

Dalvik VMは''レジスタマシン''として実装されています(JVMはスタックマシン)。Dalvik VMバイトコードの特徴を整理します。

• オペコードは8ビットで、これに必要な分だけオペランドが追加される
• 命令は16ビット単位でアライメントされる(16-bit code units)
• 各命令毎に指定できるレジスタ番号の異なり、4/8/16ビットの範囲の番号で指定する

Dalvik VMで実行されるバイトコードについて、以下の公式リファレンスを見ながら dexdump コマンドを使って整理していきます。
Bytecode for the Dalvik VM

• ''dexdump''
  Unix系OSでELFバイナリを読むときに使う objdump のようなもの。 前述の dx コマンドと同様にこれもAndroid SDKに入っています。

  $ dexdump
  dexdump: no file specified
  Copyright (C) 2007 The Android Open Source Project
  
  dexdump: [-c] [-d] [-f] [-h] [-i] [-l layout] [-m] [-t tempfile] dexfile...
  
   -c : verify checksum and exit
   -d : disassemble code sections
   -f : display summary information from file header
   -h : display file header details
   -i : ignore checksum failures
   -l : output layout, either 'plain' or 'xml'
   -m : dump register maps (and nothing else)
   -t : temp file name (defaults to /sdcard/dex-temp-*)

  以下のような簡単なJavaコードをコンパイルしてclassファイルを作り、それを dx コマンドでdexファイルに変換。 dexdump コマンドを使ってその中身を覗いてみます。

package hello; public class HelloWorld { public static void main(String[] args) { System.out.println("Hello, World!"); } public int add(int a, int b) { return a + b; } public int sub(int a, int b) { return a - b; } public int mul(int a, int b) { return a * b; } public int div(int a, int b) { return a / b; } }

コードをディスアセンブルするには -d オプションを付けて実行します。

## dexファイルに変換 $ dx --dex --output=hello.dex . ## dexファイルをディスアセンブル $ dexdump -d hello.dex Processing 'hello.dex'... Opened 'hello.dex', DEX version '035' Class #0 - Class descriptor : 'Lhello/HelloWorld;' Access flags : 0x0001 (PUBLIC) ## アクセスフラグ(スコープ) Superclass : 'Ljava/lang/Object;' ## 継承情報 Interfaces - Static fields - Instance fields - Direct methods - ## コンストラクタ #0 : (in Lhello/HelloWorld;) name : '<init>' type : '()V' access : 0x10001 (PUBLIC CONSTRUCTOR) code - registers : 1 ## レジスタ操作(参照)回数 ins : 1 ## 入力レジスタ outs : 1 ## 出力レジスタ insns size : 4 16-bit code units ## 命令は16bits単位、4x16=64bits (8bytes) 000178: |[000178] hello.HelloWorld.<init>:()V 000188: 7010 0700 0000 |0000: invoke-direct {v0}, Ljava/lang/Object;.<init>:()V // method@0007 00018e: 0e00 |0003: return-void catches : (none) positions : 0x0000 line=3 locals : 0x0000 - 0x0004 reg=0 this Lhello/HelloWorld; #1 : (in Lhello/HelloWorld;) ## main メソッド name : 'main' type : '([Ljava/lang/String;)V' ## 型情報、String型配列を引数に取る access : 0x0009 (PUBLIC STATIC) code - registers : 3 ins : 1 outs : 2 insns size : 8 16-bit code units ## sget-object でスタティックメソッド参照を取得してレジスタ(v0)に格納する ## const-string で文字列をレジスタ(v1)に格納する ## invoke-virtual でメソッド呼び出し(v0, v1)を行う 000190: |[000190] hello.HelloWorld.main:([Ljava/lang/String;)V 0001a0: 6200 0000 |0000: sget-object v0, Ljava/lang/System;.out:Ljava/io/PrintStream; // field@0000 0001a4: 1a01 0100 |0002: const-string v1, "Hello, World!" // string@0001 0001a8: 6e20 0600 1000 |0004: invoke-virtual {v0, v1}, Ljava/io/PrintStream;.println:(Ljava/lang/String;)V // method@0006 0001ae: 0e00 |0007: return-void catches : (none) positions : 0x0000 line=5 0x0007 line=6 locals : ## 以下インスタンスメソッド情報が続く Virtual methods - #0 : (in Lhello/HelloWorld;) ## add メソッド (return a + b) name : 'add' type : '(II)I' ## int型の引数2つを取り、int型の戻り値を返す access : 0x0001 (PUBLIC) code - registers : 4 ins : 3 outs : 0 insns size : 3 16-bit code units ## 3x16=48bytes (6bytes) ## add-int で2つのレジスタ(v2,v3)に格納された32ビット整数値を加算してレジスタ(v0)に格納 ## return でレジスタに格納された値を返す 0001b0: |[0001b0] hello.HelloWorld.add:(II)I 0001c0: 9000 0203 |0000: add-int v0, v2, v3 0001c4: 0f00 |0002: return v0 catches : (none) positions : 0x0000 line=8 locals : 0x0000 - 0x0003 reg=1 this Lhello/HelloWorld; #1 : (in Lhello/HelloWorld;) ## div メソッド (return a /b) name : 'div' type : '(II)I' access : 0x0001 (PUBLIC) code - registers : 4 ins : 3 outs : 0 insns size : 3 16-bit code units ## div-int で2つのレジスタ(v2,v3)に格納された32ビット整数値を除算してレジスタ(v0)に格納 ## return でレジスタに格納された値を返す 0001c8: |[0001c8] hello.HelloWorld.div:(II)I 0001d8: 9300 0203 |0000: div-int v0, v2, v3 0001dc: 0f00 |0002: return v0 catches : (none) positions : 0x0000 line=17 locals : 0x0000 - 0x0003 reg=1 this Lhello/HelloWorld; #2 : (in Lhello/HelloWorld;) ## mul メソッド (return a * b) name : 'mul' type : '(II)I' access : 0x0001 (PUBLIC) code - registers : 4 ins : 3 outs : 0 insns size : 3 16-bit code units ## mul-int で2つのレジスタ(v2,v3)に格納された32ビット整数値を乗算してレジスタ(v0)に格納 ## return でレジスタに格納された値を返す 0001e0: |[0001e0] hello.HelloWorld.mul:(II)I 0001f0: 9200 0203 |0000: mul-int v0, v2, v3 0001f4: 0f00 |0002: return v0 catches : (none) positions : 0x0000 line=14 locals : 0x0000 - 0x0003 reg=1 this Lhello/HelloWorld; #3 : (in Lhello/HelloWorld;) ## sub メソッド (return a - b) name : 'sub' type : '(II)I' access : 0x0001 (PUBLIC) code - registers : 4 ins : 3 outs : 0 insns size : 3 16-bit code units ## sub-int で2つのレジスタ(v2,v3)に格納された32ビット整数値を減算してレジスタ(v0)に格納 ## return でレジスタに格納された値を返す 0001f8: |[0001f8] hello.HelloWorld.sub:(II)I 000208: 9100 0203 |0000: sub-int v0, v2, v3 00020c: 0f00 |0002: return v0 catches : (none) positions : 0x0000 line=11 locals : 0x0000 - 0x0003 reg=1 this Lhello/HelloWorld; source_file_idx : 2 (HelloWorld.java)

Helloworldクラスでは単純な演算命令しか使っていないのでバイトコードを読むのも楽だと思います。

/dalvik/vm/mterp/out 以下にアーキテクチャ毎のバイトコードインタプリタのコードが入っています。

$ ls dalvik/vm/mterp
InterpAsm-allstubs.S     InterpAsm-armv7-a-neon.S  InterpAsm-x86.S          InterpC-armv5te.cpp       InterpC-mips.cpp
InterpAsm-armv5te-vfp.S  InterpAsm-armv7-a.S       InterpC-allstubs.cpp     InterpC-armv7-a-neon.cpp  InterpC-portable.cpp
InterpAsm-armv5te.S      InterpAsm-mips.S          InterpC-armv5te-vfp.cpp  InterpC-armv7-a.cpp       InterpC-x86.cpp

ガベージコレクション

Dalvik VMのGCには''Mark & Sweep(ビットマップマーキング)''アルゴリズムを採用しています。通常のMark & Sweep方式はLinuxのCopy On Write(データの書き換えが発生した時にコピーを行う)と相性が悪いです。Mark & Sweepは生きているオブジェクトのヘッダにマークビットを立てますが、これを行うと本来は必要のないコピーが行われてしまうからです。なので、Dalvik VMではビットマップマーキングという手法を併用してこの問題に対処しています。この手法は各オブジェクトのマークビットだけを集めたテーブル(ビットマップテーブル)を用意し、オブジェクトとは別の場所で管理する手法です。

• dalvik/vm/alloc

  $ ls
  Alloc.cpp      Copying.cpp   DlMalloc.h      HeapBitmap.h         HeapInternal.h  MarkSweep.h  Visit.cpp
  Alloc.h        DdmHeap.cpp   Heap.cpp        HeapBitmapInlines.h  HeapSource.cpp  TEST/        Visit.h
  CardTable.cpp  DdmHeap.h     Heap.h          HeapDebug.cpp        HeapSource.h    Verify.cpp   VisitInlines.h
  CardTable.h    DlMalloc.cpp  HeapBitmap.cpp  HeapDebug.h          MarkSweep.cpp   Verify.h     WriteBarrier.h
  $ du -sh *.cpp
  12K     Alloc.cpp
  16K     CardTable.cpp
  72K     Copying.cpp
  16K     DdmHeap.cpp
  4.0K    DlMalloc.cpp
  24K     Heap.cpp
  8.0K    HeapBitmap.cpp
  4.0K    HeapDebug.cpp
  40K     HeapSource.cpp
  28K     MarkSweep.cpp
  4.0K    Verify.cpp
  12K     Visit.cpp

Dalvik VMのヒープ

Dalvik VMのオブジェクトは専用のヒープに保持されます。これには2種類あり、１つは前述の Zygote 用のヒープ、もう１つはAndroidアプリケーションで使用するヒープです。ヒープの中身は以下のようになっています。

• dalvik/vm/alloc/HeapSource.cpp struct Heap { /* The mspace to allocate from. */ mspace msp; /* The largest size that this heap is allowed to grow to. */ size_t maximumSize; /* Number of bytes allocated from this mspace for objects, * including any overhead. This value is NOT exact, and * should only be used as an input for certain heuristics. */ size_t bytesAllocated; /* Number of bytes allocated from this mspace at which a * concurrent garbage collection will be started. */ size_t concurrentStartBytes; /* Number of objects currently allocated from this mspace. */ size_t objectsAllocated; /* * The lowest address of this heap, inclusive. */ char *base; /* * The highest address of this heap, exclusive. */ char *limit; /* * If the heap has an mspace, the current high water mark in * allocations requested via dvmHeapSourceMorecore. */ char *brk; }; 前述の dlmalloc の項で紹介した mspace をメンバとして持っています。オブジェクトはこの中にアロケーションされます。
• dalvik/vm/alloc/HeapBitmap.h
  マーキングで用いるビットマップは以下のように定義されています。実態は unsigned long の配列のようです。 struct HeapBitmap { /* The bitmap data, which points to an mmap()ed area of zeroed * anonymous memory. */ unsigned long *bits; /* The size of the used memory pointed to by bits, in bytes. This * value changes when the bitmap is shrunk. */ size_t bitsLen; /* The real size of the memory pointed to by bits. This is the * number of bytes we requested from the allocator and does not * change. */ size_t allocLen; /* The base address, which corresponds to the first bit in * the bitmap. */ uintptr_t base; /* The highest pointer value ever returned by an allocation * from this heap. I.e., the highest address that may correspond * to a set bit. If there are no bits set, (max < base). */ uintptr_t max; }; 処理の詳細については調べながら追記していきます。