[置顶] Android学习之--prelink
最近移植一些既存的c程序到android中，不可避免的需要了解ndk，jni之类的东西，编译体系，toolchain之类的东西。偶尔，发现了Android中的src中有一个叫做“LOCAL_PRELINK_MODULE”的参数，它是Android采用的加快一些系统的函数库加载速度的手段。
因为对这个比较感兴趣，就稍微去了解了一下。
首先，需要了解一下什么是prelink
由RedHat的大牛Jakub Jelínek所发布的开源程序。通过修改ELF的可执行文件预先计算出函数库的relocation的信息，来加速系统对于被prelink处理过后的函数库的加载速度。
详细可以参考一下资源：
http://people.redhat.com/jakub/prelink/prelink.pdf
http://jserv.blogspot.com/2010/10/android.html这篇是台湾同胞写的，因为发布在blogspot上而悲惨的被墙了，所以在本文最后贴出来方便大家查看。
接着，就看看Android中什么地方使用到了
以下是Android的开发这David Turner在邮件列表中对于一个开发者的疑问的回答（原文链接）：
Android使用了一个定制的prelinker tool来降低系统库的大小和加载速度（通过预先指定可执行文件使用到的动态库的location地址配合定制的linker来完成）。它的回答中提到了，Android中使用的linker也是定制过的，没有完全实现一些ELF所规定的relocations相关的功能。这就会导致如果用其它的toolchain编译出的动态库如果用了一些Android的linker所不支持的特性，有可能就会出奇怪的问题。如果你用了其它的toolchain编译了一些动态库，导致在android上链接失败，最好还是使用android提供的toolchain。（从linker和两个prelink工具的代码看，默认的android执行的linker是在/system/bin/linker）
grep了一下android源代码，发现只有编译dalvik时会根据是否是模拟器来显示开启这个选项，而其它的库都默认是打开prelink的。
mydroid/bionic/linker/README.TXT文件中对Android中的prelink做了一些描述：android默认对所有系统的库都会进行prelink，一旦有新的库被加入或者更改时，需要重新更新prelink-linux-xxx.map的文件，android提供了定制的apriori和soslim（在使用）两个工具在build的时候进行相应的prelink动作。
主要由apriori（代码在mydroid/build/tools/apriori/下）和soslim（代码在mydroid/build/tools/soslim/）配合完成prelink的动作
dalvik/vm/Android.mk: LOCAL_PRELINK_MODULE := true
同时，build/core/prelink-linux-arm.map是关键的一个配置文件。
查看dalvik的代码，在Native.c的注释中，有关于dalvik中使用dynamic library的一些注意事项
最后，作为开发者我们可以如何使用它
适用于Android的系统开发者，用来定制系统级的动态库，加速定制的android的系统的启动及加载速度。
由于嵌入式设备尤其是android设备，目前的升级比较频繁，一旦prelink过的库函数修改过了，要求所有引用该库函数的可执行文件也要被重新编译。这就要求系统开发者谨慎的修改系统代码，毕竟每次OTA升级的代价还是很大的。
例子：
让我们以系统的一个可执行文件，service为例（mydroid/out/target/product/generic/system/bin/service）
使用readelf dump出该可执行elf文件的信息，可以看到.interp这个section，并发现它是指向/system/bin/linker这个定制化的android的连接器。为什么这里会有.interp这个section，主要是因为它的Dynamic Setction明确用到了一些库函数，而这些库函数是被prelink过的。
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .interp PROGBITS 00008114 000114 000013 00 A 0 0 1
[ 2] .hash HASH 00008128 000128 00022c 04 A 3 0 4
Dynamic section at offset 0x2068 contains 27 entries:
Tag Type Name/Value
...
0x00000004 (HASH) 0x8128
0x00000001 (NEEDED) Shared library: [liblog.so]
0x00000001 (NEEDED) Shared library: [libutils.so]
0x00000001 (NEEDED) Shared library: [libbinder.so]
0x00000001 (NEEDED) Shared library: [libc.so]
0x00000001 (NEEDED) Shared library: [libstdc++.so]
0x00000001 (NEEDED) Shared library: [libm.so]
0x00000020 (PREINIT_ARRAY) 0xa000
...
再来看看作为动态库的文件中prelink和不prelink的区别,以liblog.so为例(mydroid/system/core/liblog/xxx)
两者的编译命令如下：
target Prelink: liblog (out/target/product/generic/symbols/system/lib/liblog.so)
out/host/linux-x86/bin/apriori --prelinkmap build/core/prelink-linux-arm.map --locals-only --quiet out/target/product/generic/obj/SHARED_LIBRARIES/liblog_intermediates/LINKED/liblog.so --output out/target/product/generic/symbols/system/lib/liblog.so
target Strip: liblog (out/target/product/generic/obj/lib/liblog.so)
out/host/linux-x86/bin/soslim --strip --shady --quiet out/target/product/generic/symbols/system/lib/liblog.so --outfile out/target/product/generic/obj/lib/liblog.so
Install: out/target/product/generic/system/lib/liblog.so
out/host/linux-x86/bin/acp -fpt out/target/product/generic/obj/lib/liblog.so out/target/product/generic/system/lib/liblog.so
target Non-prelinked: liblog (out/target/product/generic/symbols/system/lib/liblog.so)
out/host/linux-x86/bin/acp -fpt out/target/product/generic/obj/SHARED_LIBRARIES/liblog_intermediates/LINKED/liblog.so out/target/product/generic/symbols/system/lib/liblog.so
target Strip: liblog (out/target/product/generic/obj/lib/liblog.so)
out/host/linux-x86/bin/soslim --strip --shady --quiet out/target/product/generic/symbols/system/lib/liblog.so --outfile out/target/product/generic/obj/lib/liblog.so
Install: out/target/product/generic/system/lib/liblog.so
out/host/linux-x86/bin/acp -fpt out/target/product/generic/obj/lib/liblog.so out/target/product/generic/system/lib/liblog.so
分别编译一份prelink的和没有prelink的库，再分别对其使用objdump和readelf查看它们区别，结果如下：
readelf.dump for prelink
------------------------------------------------------------------
[ 5] .rel.dyn REL 00000e28 000e28 000018 08 A 2 2 4
0x00000012 (RELSZ) 24 (bytes)
Relocation section '.rel.dyn' at offset 0xe28 contains 3 entries:
Offset Info Type Sym.Value Sym. Name
000030dc 00001515 R_ARM_GLOB_DAT 00000000 __stack_chk_guard
000030e0 00002d15 R_ARM_GLOB_DAT 00000000 __sF
000030e4 00003715 R_ARM_GLOB_DAT 00000000 _tolower_tab_
readelf.dump for non-prelink------------------------------------------------------------------
[ 5] .rel.dyn REL 00000e28 000e28 000030 08 A 2 2 4
0x00000012 (RELSZ) 48 (bytes)
Relocation section '.rel.dyn' at offset 0xe28 contains 6 entries:
Offset Info Type Sym.Value Sym. Name
00001034 00000017 R_ARM_RELATIVE
0000300c 00000017 R_ARM_RELATIVE
00003198 00000017 R_ARM_RELATIVE
000030dc 00001515 R_ARM_GLOB_DAT 00000000 __stack_chk_guard
000030e0 00002d15 R_ARM_GLOB_DAT 00000000 __sF
000030e4 00003715 R_ARM_GLOB_DAT 00000000 _tolower_tab_
objdump.dump for prelink
------------------------------------------------------------------
Disassembly of section .rel.dyn:
00000e28 <.rel.dyn>:
e28: 000030dc ldrdeq r3, [r0], -ip
e2c: 00001515 andeq r1, r0, r5, lsl r5
e30: 000030e0 andeq r3, r0, r0, ror #1
e34: 00002d15 andeq r2, r0, r5, lsl sp
e38: 000030e4 andeq r3, r0, r4, ror #1
e3c: 00003715 andeq r3, r0, r5, lsl r7
00001028 <__android_log_bwrite-0x18>:
1028: e28f0004 add r0, pc, #4 ; 0x4
102c: e5900000 ldr r0, [r0]
1030: eaffff8d b e6c <__android_log_bwrite-0x1d4>
1034: afa031a0 svcge 0x00a031a0
1038: 42402001 submi r2, r0, #1 ; 0x1
103c: 46c04770 undefined
Disassembly of section .fini_array:
00003008 <__FINI_ARRAY__>:
3008: ffffffff undefined instruction 0xffffffff
300c: afa01028 svcge 0x00a01028
3010: 00000000 andeq r0, r0, r0
00003014 <.dynamic>:
...
3040: 00000018 andeq r0, r0, r8, lsl r0
...Disassembly of section .data:
00003188 <__data_start>:
3188: ffffffff undefined instruction 0xffffffff
318c: ffffffff undefined instruction 0xffffffff
3190: ffffffff undefined instruction 0xffffffff
3194: ffffffff undefined instruction 0xffffffff
3198: afa010a1 svcge 0x00a010a1
objdump.dump for not-prelink------------------------------------------------------------------
Disassembly of section .rel.dyn:
00000e28 <.rel.dyn>:
e28: 00001034 andeq r1, r0, r4, lsr r0
e2c: 00000017 andeq r0, r0, r7, lsl r0
e30: 0000300c andeq r3, r0, ip
e34: 00000017 andeq r0, r0, r7, lsl r0
e38: 00003198 muleq r0, r8, r1
e3c: 00000017 andeq r0, r0, r7, lsl r0
e40: 000030dc ldrdeq r3, [r0], -ip
e44: 00001515 andeq r1, r0, r5, lsl r5
e48: 000030e0 andeq r3, r0, r0, ror #1
e4c: 00002d15 andeq r2, r0, r5, lsl sp
e50: 000030e4 andeq r3, r0, r4, ror #1
e54: 00003715 andeq r3, r0, r5, lsl r7
Disassembly of section .text:
00001028 <__android_log_bwrite-0x18>:
1028: e28f0004 add r0, pc, #4 ; 0x4
102c: e5900000 ldr r0, [r0]
1030: eaffff8d b e6c <__android_log_bwrite-0x1d4>
1034: 000031a0 andeq r3, r0, r0, lsr #3
1038: 42402001 submi r2, r0, #1 ; 0x1
103c: 46c04770 undefined
Disassembly of section .fini_array:
00003008 <__FINI_ARRAY__>:
3008: ffffffff undefined instruction 0xffffffff
300c: 00001028 andeq r1, r0, r8, lsr #32
3010: 00000000 andeq r0, r0, r0
Disassembly of section .dynamic:
00003014 <.dynamic>:
...
3040: 00000030 andeq r0, r0, r0, lsr r0...
Disassembly of section .data:
00003188 <__data_start>:
3188: ffffffff undefined instruction 0xffffffff
318c: ffffffff undefined instruction 0xffffffff
3190: ffffffff undefined instruction 0xffffffff
3194: ffffffff undefined instruction 0xffffffff
3198: 000010a1 andeq r1, r0, r1, lsr #1
从两者的数据很明显看出来prelink的要比non-prelink的数据简单一些，.so的大小也小一些。再跟prelink-linux-arm.map中的liblog.so所分配的地址一比较，可以很容易看到所有的prelink好的数据的地址在prelink类别的dump结果中都是从0xAFA00000开始的
参考资料：
Android Prelink代码分析
加速 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
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 帶來更快的動態連結時間，但付出的代價 (空間) 較高，而且不若後者有彈性。
更多相关文章
- [置顶] Android camera子系统HAL层介绍集锦
- Android核心分析---Android电话系统
- Android最佳实践之：代码性能优化——Strict Mode介绍
- Android 切换系统语言源码分析
- Android的WiFi子系统架构