加速 Android 的動態連結

就如人們所熟悉，Android 底層運作 Dalvik 虛擬機器，在 C Library 層面採用衍生自 NetBSD libc 的 bionic。與過往的 Java 為基礎的操作環境 (OE; Operating Environment，如 Transvirtual 的 PocketLinux / XOE) 不同的是，每個 VM instance 均為獨立的 Linux process，且由 Zygote 所「孵化」。就系統的角度來說，縱使底層對 system library 做了 prelink (透過工具 build/tools/apriori)，但因語言實做的特性，需頻繁經由 JNI 去存取底層服務，也就是說，有大量的 dlopen()/dlsym() 操作，這些均無法透過 prelink 來縮減載入時間。

在 COSCUP 2010 的議程「打造特製的 Android Toolchain」中，小弟介紹了 0xlab 近來的幾項嘗試與改進項目，除了 GNU Toolchain (採用 gcc-4.4.4 搭配一系列的修改) 之外，就包含 Android bionic libc 與 prelink 的修改，企圖引入 DT_GNU_HASH 的機制 (也稱為 gnu hashstyle，或 gnu hash)，以加速 Android 的動態連結。現在基礎工作大致完畢，陸續提交到 AOSP (Android Open Source Project) 的 Code Review，應該會納入 Android Gingerbread 以及後續的版本中。實驗平台採用 Qualcomm MSM7x25 (arm1136j-s)，平均縮減 26% 的 ELF 動態連結時間，這對所有的 Android Activity (Java 程式) 與需要額外作 dlopen() 處理的系統函式庫，如 Qualcomm 的 camera HAL/service 或 Opencore/DSP，均可適用。

這過程中，讓小弟學習到頗多，從一開始的分析 (透過 oprofile 與開啟 bionic 裡頭 linker 的除錯資訊)，觀察到 Android 的動態連結處理，有點類似 OpenOffice 所面臨的議題，於是嘗試引入 DT_GNU_HASH。背景知識可參考以下文獻：

• LWN 清晰的介紹文章 "Optimizing Linker Load Times"，涵蓋四項 linker 參數背後的處理機制: -Wl,-O1, -Bdirect Linking, dynsor, gnu hashstyle (Precomputed Hash Values)
• Ali Bahrami 的 blog 文章 "GNU Hash ELF Sections" 與 "The Cost Of ELF Symbol Hashing"，淺顯易懂
  
• glibc 維護者 Ulrich Drepper 的論文 "How To Write Shared Libraries" (不要被 How To 字眼騙了，其實頗深入)，廣泛探討從歷史因素到 DSO 運作機制，以及 GNU Hackers 如何參照 Sun Microsystems 過往的改良機制，重新實做出 gnu hashstyle

gnu hashstyle 採用 Daniel J Bernstein 提出的 hash function，Jakub Jelinek 做了分析，比較原本 ELF hash:

The number of collisions in the 537403 symbols is:
name  2sym collision # 3sym collision # more than 3sym collision #
sysv            1749                5
libiberty         42
dcache            37
djb2              29
sdbm              39
djb3              31
rot              337               39                         61
sax               34
fnv               40
oat               30

sysv 那項是原本的 hash function，而 djb2 則是 GNU Toolchain 採用的方案。就現有自由軟體的實做來看，包含 glibc, uClibc, dietlibc (前三者支援 GNU/Linux), FreeBSD libc 均提供 gnu hashstyle 的支援，但 Android 未正式在 bionic 提供。需留意的是，prelink 方案總是比 gnu hashstyle 帶來更快的動態連結時間，但付出的代價 (空間) 較高，而且不若後者有彈性。