2012年1月31日 星期二

Android Prelinker : Apriori

雖然 apriori 於 ICS 中被移除了, 但於 gingerbread 中還是長存著, 寫這篇文章順便為自己之前修改 Apriori 的部分發篇文介紹一下做個小結案

簡介
Prelink 的機制主要目的在於減少 Dynamic Linker 載入程式時 link 所花的時間已達到加速程式啟動, 目前在一般 Linux 有由Redhat 的 Jakub 所提出的 prelink[1], 並可有效減少 link time, 而該方法需要於檔案中塞入額外的資訊, 因此較不適用於 Android 的用途上, 也因此 Android 自己弄了一套 Prelink 機制.


Dynamic Linking


在開始說明 Prelink 前先來說明, dynamic linking 的流程與用途, 避免無相關背景知識讀者看無. 而為了簡化說明這邊僅介紹採用 ELF 格式下的情況.


一般而言我們在撰寫程式的時候會使用到一些函數庫, 例如 printf, scanf 等等各式各樣的函數, 但這些函數都經常被各個程式使用, 若每個程式都包含了一份各字的 printf, scanf 那麼整個系統將會變得相當龐大, 而 Dynamic Linking 就是在面對這樣的問題底下所出現一種解法, 將一些常用的函數抽出來變成一個函數庫, 並且函數庫可以在各個程式間共用, 避免不必要的浪費.


有了基本的概念後直接來看個 Hello World 的例子 :

#include <stdio.h>

int main(){
    printf("Hello world!\n");
    return 0;
}

其中的 printf 很明顯的不存在以上的程式中, 而是來自於 C library, 因此在編譯好的可執行檔中有紀錄幾個資訊
  1. 相依到哪些 Shared library
  2. 有哪些 Symbol (函數/變數皆屬於一個 Symbol)是來自外部 shared library (要注意並無紀錄 Symbol 是由哪個 shared library 來)
在執行程式時, 系統可根據在執行檔中的資訊去幫你進行 Dynamic Linking, 這個動作在 Linux 當中通常由 ld.so 來處理, 在 Android 中則由 /system/bin/linker 處理.


前面提到執行檔中僅紀錄有哪些 Symbol 是外來的, 並無紀錄其歸屬因此 Dynamic Linker 的主要工作流程如下
  1. 將執行檔載入記憶體中
  2. 載入所有相依的 Shared library (包含相依的相依)
  3. 查找 Symbol 在哪個  Shared library 中
  4. 將查找結果更新(Relocation)
  5. 所有 Symbol 處理完畢註1後才開始執行程式
因此程式的啟動時間總共是 1~4 在 Prelink 中主要可以加速的是 3+4 的部份.


其中 4  的更新的步驟主要是將  Shared library 的基底位置(Base Address, 指載入到的記憶體區段開頭)在加上 Symbol 在該動態函式庫的位址.

註解

註1 : 有些例外, 但這邊不探討, keyword 為 weak symbol


Prelink


在有了 Dynamic Linker 運作的基本流程後, 接著我們可以來探討 Prelink 的機制, Prelink 機制前面有提到主要目的在於減少查找 Symbol 在哪個  Shared library 的時間, 也就是先把所有符號查起來並且將結果存起來.


那該如何達到這點呢?首先我們所遇到的第一個問題會是 Shared library 的基底位置該如何處理, Shared library 在設計時變考量到必須可載入任何位置皆可以動(PIC), 否則將會因此浪費記憶體定址空間, 且也可能因此衝突.


所以有幾個方法可以處理這個問題 1. 掃描所有的 Shared library 並分配位址空間 2. 為 Shared library 預分配位址, 在 Android 中所採用的方法為後者也就是透過 prelink map 的方式來設定該 shared library.


在 Shared library 的基底位置決定後, 便可以先處理所有的 Relocation, 但要注意的是 Shared library 也因此喪失部份的彈性, 變得必須載入至固定位址, 因此在 Dynamic Linker 中也必須支援.


但相對的也可得到一些其他的優勢, 例如 Relocation 都處理完的話, 那其資訊也可以直接丟掉了, 在檔案大小上會小上一些, 間接的會再度加速整個程式載入的流程.


不過上敘的部份是針對 Android Prelink 機制而言 linux 上 prelink 完後會塞入一些額外資訊, 檔案反而會變肥.


Android Prelink 實作


在 Android 上的 Prelinker 實作相對於 linux 的 prelink 來說相當輕薄短小, 並且設計簡單, 執行流程如下

  1. 載入要 Prelink 的 Shared Library
  2. 查找 Prelink map 或從參數設定 Base Address
  3. 查找 Symbol , 若找的到即更新其 Address
  4. 處理掉相對位址的 Relocation
  5. 將已經處理完的 Relocation 從檔案中移除
  6. 把  Base Address 塞到檔案最後面

而其中第 6 項目, 個人猜測是 Android 為啥 ICS 以前不採用 strip 而採用自家的 soslim 來為  Shared library 瘦身的原因

但因不明原因 Android Prelink 機制只做半套, 只有 Local Prelink, 意思是只能處理同檔案下的 Symbol 而已, 因此能 Prelink 的有限.

在  Dynamic Linker (bionic/linker) 方面載入 Shared Library 的工作流程如下
  1. 開啟 Shared Library 檔案
  2. 判斷檔案後面有沒有塞 Prelink 資訊
  3. 有的話讀出其 Base Address
  4. 接著按照其資訊載入預定記憶體位置



Android Global Prelink


前面提到 Apriori 只有做 Local Prelink, 因此我們對於 Apriori 進行補完(實際上內部程式碼已經有 Global Prelink 的雛型, 但未完成)
  1. 載入要 Prelink 的 Shared Library
  2. 查找 Prelink map 或從參數設定 Base Address
  3. 載入相依的 Prelink 過的 Shared Library,  Non-prelink 的 Shared Library 將直接掠過
  4. 查找 Symbol , 若在已 Prelink 過的相依  Shared Library  找的到即更新其 Address
  5. 處理掉相對位址的 Relocation
  6. 將已經處理完的 Relocation 從檔案中移除
  7. 把  Base Address 塞到檔案最後面
主要在流程中插入載入相依的 Shared Library, 使得能處理的 Relocation 數激增, 在沒有 Undefined Weak Symbol 及 Multiple Definition 的情況下, 可以完全處理完畢, 與原本的 Apriori 相比有相當卓越的效果(文章最後面會附上實驗數據).



Android Partial Global Prelink



而 Apriori 的 prelink 是依賴 Prelink map 來實行, 未列於 Prelink map 的 Shared Library 將不會進行任何的 Prelink, 但經過觀察我們發現, 並非完全無法處理, 因為 Prelink 的必要條件在於有 Base Address 及 Symbol Offset, 但未列於 Prelink map 的 Shared Library 僅缺乏自身的 Base Address, 其相依的 Shared Library 已經 Prelink, 則其 Base Address 已經決定, 因此有相當大一部份是可以 Prelink 的, 也因此這個部份稱之為 Partial Global Prelink, 其運作流程如下:
  1. 載入要 Prelink 的 Shared Library
  2. 載入相依且 Prelink 過的 Shared Library,  Non-prelink 的 Shared Library 將直接掠過
  3. 查找 Symbol , 若在已 Prelink 過的相依  Shared Library  找的到即更新其 Address
  4. 將已經處理完的 Relocation 從檔案中移除, 相對位址類型的 Relocation 將不做任何處理
由流程可以看到, 相較於一般 Global Prelink 的行為較為簡化, 在這邊舉一個例子, 假設我們有一個 libfoo.so, 其原始碼如下:

#include <stdio.h>

int bar() {
    return 1;
}

int foo(){
    printf("Hello world!\n");
    return bar();
}

編譯出來後因為 libfoo.so 有用到 printf 因此會相依到 libc.so
而 libfoo.so 中有兩個 relocation 要處理, foo 函數中的 printf 及 bar
假設 libc.so 已經有 prelink 過那麼 libc.so 則已經有 Base Address,
因此如果我們對 libfoo.so 進行 Partial Global Prelink 後, relocation 將僅剩下 foo 函數中的 bar 要處理.

由以上例子可以看出此方式可大大減少 dynamic link time, 而且 bionic/linker 會優先查找自己的 symbol, 因此剩餘的 relocation 也可以快速的處理掉.



Android Executable Prelink

這部份就比較單純了, 因為 executable 不是 PIC, 其 Base Address 已經固定為 0, 所以直接來看流程吧.
  1. 載入要 Prelink 的 Executable
  2. 載入相依的 Prelink 過的 Shared Library,  Non-prelink 的 Shared Library 將直接掠過
  3. 查找 Symbol , 若在已 Prelink 過的相依  Shared Library  找的到即更新其 Address
  4. 處理掉相對位址的 Relocation
  5. 將已經處理完的 Relocation 從檔案中移除
與 Global Prelink 部份差不多, 但不用去 Prelink Map 查找, 也不用將 Base Address 塞到檔案尾巴.


實驗數據

最重要的部份就是效果到底如何勒, 圖表中的神秘代號解釋如下 :
  1. lp : Local Prelink
  2. gp : Global Prelink
  3. re : Reorder DT_NEEDED entries
  4. pe : Prelink executable
  5. pgp : Partial global prelink
  6. are : Aggressive reorder look-up order 

圖1. Normalized Dynamic Link time

圖2. Normalized Number of Symbol Lookup

可由圖中觀察到 Global Prelink 以及 Executable Prelink 對於 Dynamic Link Time 有相當不錯的進步, 若原本 Dynamic Link Time 越長則效果會越好, Partial Global Prelink 在這份圖表中看不出什麼效果, 主要原因是採用的實驗對象是 Android 開機會開到的幾隻程式, 其中幾乎沒有包含 Non-Prelink 的 Shared Library.


Future Work

自從 Prelink 在 ICS 被拔掉後, 以上的東西就用不到了, 預期之後將會發展一套 cache 機制來加速 Dynamic Link Time, 來避免掉 Prelink 的缺點, 以及想辦法加速 Dynamic Link Time.


附註

以上的修改(包含只出現在圖表中的方法), 目前皆可在 0xdroid 抓的到程式碼, 分佈在 bionic 及 build 裡面.

參照
[1] http://people.redhat.com/jakub/prelink.pdf
[2] 程式設計師的自我修養:連結、載入、程式庫

2012年1月21日 星期六

Clang + LLVM as cross compiler


Update Note:

  1. (2012/11/22) 目前 trunk 及 3.2 以後,將以 -target 取代那串語意不太清楚的 -ccc-host-triple, 所以如果 clang 跟你抱怨 clang: error: unsupported option '-ccc-host-triple' 的話請將文中指令的 -ccc-host-triple 替換成 -target

這篇文章主要講解怎麼把 Clang + LLVM 來當作一般的 Cross Compiler 來用, 也就是一般使用 arm-linux-gcc 一樣, 跟平常用 gcc 一樣就能動了

arm-linux-gcc hello.c -o hello

所以最終目標是想要

clang -arch arm hello.c -o hello

不過很殘念的是這只能在 Darwin 上可以這樣用...在 cfe-dev 上有人提過 [1]

而最近雖然有偉大的 ELLCC 可以用, 但其使用的 C Library 看起來還不太齊全(至少不夠編出 SPEC2000, 來自 NetBSD C Library), 而且編譯 SPEC2000 的 perlbmk 也會鬼打牆似的 symbol redefine ...

所以在 ELLCC 成熟前先將就點退而其之用 clang 撐著用

用 Clang + LLVM 當 cross compiler 注意 LLVM 當初編的時候 Target 要開, 免得耍蠢

在這邊先假設已經有 Clang + LLVM 的執行檔下開始作說明

我們的暫定目標是將 Clnag + LLVM 弄成可以編出 arm-linux 上的程式

首先先弄一套 arm linux toolchain 懶得自己編就去弄一套 Code Sourcery 的以下是其中一個版本的 連結 (選IA32 GNU/Linux TAR)

或著是你可以到此 頁面 下載最新版

然後解壓縮放在你家, 接著確認他會不會動

# ~/arm-2011.09/bin/arm-none-linux-gnueabi-gcc -v

Using built-in specs.
COLLECT_GCC=arm-2011.09/bin/arm-none-linux-gnueabi-gcc
COLLECT_LTO_WRAPPER=/home/kito/arm-2011.09/bin/../libexec/gcc/arm-none-linux-gnueabi/4.6.1/lto-wrapper
Target: arm-none-linux-gnueabi
...
確認會動後下一步終於要啟動 clang 了
首先先將你的 arm-linux-gcc 的資料夾弄給 clang 知道
不用加 bin/, clang 會掃描該自料夾
clang -gcc-toolchain /home/kito/arm-2011.09/
主要原因是 clang 會去找 gcc 來用, 以此辨別 ld 跟 as 位置

接著
clang -gcc-toolchain /home/kito/arm-2011.09/  -ccc-host-triple arm-none-linux-gnueabi hello.c
看起來是這樣應該就要可以動了
但實際跑起來會跟你抱怨找不到 Library, 以及很嚴重的是 include 檔是抓 x86 的

/home/kito/arm-2011.09//lib/gcc/arm-none-linux-gnueabi/4.6.1/../../../../arm-none-linux-gnueabi/bin/ld: warning: library search path "/lib/../lib64" is unsafe for cross-compilation /home/kito/arm-2011.09//lib/gcc/arm-none-linux-gnueabi/4.6.1/../../../../arm-none-linux-gnueabi/bin/ld: warning: library search path "/usr/lib/../lib64" is unsafe for cross-compilation /home/kito/arm-2011.09//lib/gcc/arm-none-linux-gnueabi/4.6.1/../../../../arm-none-linux-gnueabi/bin/ld: warning: library search path "/lib" is unsafe for cross-compilation /home/kito/arm-2011.09//lib/gcc/arm-none-linux-gnueabi/4.6.1/../../../../arm-none-linux-gnueabi/bin/ld: warning: library search path "/usr/lib" is unsafe for cross-compilation /usr/lib/../lib64/crt1.o: file not recognized: File format not recognized clang-3: error: linker command failed with exit code 1 (use -v to see invocation)

所以下一步驟是加入搜索路徑

clang -ccc-host-triple arm-none-linux-gnueabi --sysroot=/home/kito/arm-2011.09/arm-none-linux-gnueabi/libc/ hello.c

然後~噁他在動~!!!
但相信只要是人都會覺得那串太長
所以把下面那串弄到 .bashrc 裡

alias arm-clang='/home/kito/llvm/llvm/bin/clang -gcc-toolchain /home/kito/arm-2011.09/ -ccc-host-triple arm-none-linux-gnueabi --sysroot=/home/kito/arm-2011.09/arm-none-linux-gnueabi/libc/'

從今以後也可以使用簡單的方式來編譯了

arm-clang hello.c -o hello

若要驗證可使用 qemu-arm 來驗證, 不過記得要加 -static 參數

最後要注意的是 sysroot 裡面的路徑 /home/kito/ 不可縮減為 ~/ 會因此找不到路徑呦



備註:
  1. clang 可使用 -march 來指定最佳化的ISA,如-march=armv4, -march=armv7
  2. clang 跟 gcc 在一些細節支援上有些不同, 必須留意(例如 clang 不支援 register storage class global variable )
  3. 上敘的使用方法還是會相依到 libgcc, 如果是要研究用途的請留意, 有個東西叫 compiler-rt 是 libgcc 的替代品, 但目前還不知道怎麼整進去
  4. 上敘的方法有拿去編譯 uClibc 跟 SPEC2000 試過了

[1] http://lists.cs.uiuc.edu/pipermail/cfe-dev/2010-July/009878.html

strace for Andorid JNI program

strace -f -F -p <pid_for_zygote>

這樣就可以看到 strace 到所有的 dvm 程式, 並且包含之後新開出來的 dvm

不過要注意的是需要 su 權限不然會看到下列的訊息
而以下為方便說明起見假設 zygote 的 pid 為 84

shell@android:/ $ strace  -f -F -p 84
attach: ptrace(PTRACE_ATTACH, ...): Operation not permitted

正常啟動則會像下面這樣開始吐一些訊息

shell@android:/ $ strace  -f -F -p 84
Process 1339 attached with 4 threads - interrupt to quit
[pid  1339] --- SIGSTOP (Stopped (signal)) @ 0 (0) ---
[pid  1339] --- SIGSTOP (Stopped (signal)) @ 0 (0) ---
[pid  1339] setup()                     = -1 ETIMEDOUT (Connection timed out)
[pid  1339] msgget(0x1, 0x4e07cd48, 0, 0x4e07cd48) = 0
[pid  1339] msgget(0x1, 0x4e07cd28, 0x1, 0x1) = 0
[pid  1339] recv(6604760,  <unfinished ...="">
[pid  1338] --- SIGSTOP (Stopped (signal)) @ 0 (0) ---
[pid  1338] 


輸出可能會有點雜亂, 大致的原則是程式開下去就會噴出一堆紀錄, 所以最好先輸出成檔案, 在拉到電腦端分析.

shell@android:/ $ strace  -f -F -p 84 &>/sdcard/strace.log

拉回電腦端就可以先用搜索 apk 關鍵字來鎖定你的程式的 pid 多少, 再配合 grep 即可快速濾出需要的資訊摟~

2012年1月10日 星期二

Register Allocation in GCC : Reload / LRA

這篇文主要是想簡短介紹一下邪惡的 Reload 以及目前 LRA 的一些狀況, 這部份大概是 GCC 最棘手的部份, 其中缺乏文件且程式碼又跟漿糊一樣, 一直到了近年來才有 Vladimir Makarov@redhat 在幫忙加註解兼整理, 這篇大致上是根據其 Wiki 頁面及 LRA 簡報再加上一些個人經驗所匯集而成的東西.

Reload

在介紹 Reload 前一定要提下 GCC reload 的 Wiki 頁面[1]頁面上的經典介紹, 其中第一段第一句
"Reload is the GCC equivalent of Satan."
在強而有力的開場白後, 接著就來介紹 Reload 到底做了甚麼事?
  • 產生 Spill Code
  • 想辦法符合 Instruction constraint
  • CSE (common subexpression elimination)
  • 融合 Frame Point 及 Stack Point (-fomit-frame-pointer)
  • 想辦法把所有 non-strict RTL 弄成 strict RTL
  • 蓋 Constant pool
所以在 Reload 完後, 基本上所有 insn 都已經符合  Instruction constraint, 言下之意就是可以輸出成組合語言了, 也因此 Reload 在 GCC backend 裡面是一個非常重要的里程碑, 而 reload_completed 這個變數則可以查詢目前使在 reload 前還是後, 亦或是正在 reload (variable:reload_in_progress).

雖然 Reload 很強大, 但問題就在於太強大太貪心作太多事了, 模組也沒切的很好, reload.c + reload1.c 大概超過一萬六千多行左右, 缺乏註解, 並且可怕的是其中的函數參數都很多, 而其中的一些 assertion 的邏輯也沒說明的很清楚, 導致目前沒多少人有膽去動...在 GCC 的程式碼堆裡面一直是個黑暗角落...而其中最大的問題是引入過多不必要的 Target Marco , 其中有相當程度的資訊基本尚可由 md 檔中推導而出, 導致 Porting 難度的增加.


LRA : Local Register Allocation


在一片混沌多年後, IRA 的主要作者 Vladimir Makarov@redhat 跳出來試著想要把 Reload 換掉, 當然如同 Register Allocation 一樣, 不是第一個跳出來挑戰的人, 但 Vladimir Makarov@redhat 卻是第一個成功將 Register Allocation 換掉的人, 也因此 LRA 這個計畫相當的令人期待.

大致了解 LRA 的使命後接著來介紹他所設定的幾個設計目標
  • 盡可能的將各個模組切開
  • 盡可能的將資訊反應到 RTL 上, Reload 則是偏好在 RTL 串上一堆 note
  • 將 MD 中 Insn 的 Constraint 作為主要資訊來源, 減少額外 Target Marco 的需要
接著是來看他內部的架構圖, 大致上是採用 Iterative pass 的方式來處理




其中比較要注意的是 Virtual Register 跟 Pseudo Register , 各家的 Register Allocation 皆有各自的定義, 而這邊的定義則是

  1. Hard Register : 代表目標機器的實體暫存器
  2. Virtual Register : 代表一些特殊的暫存器如 Argument  pointer, Frame pointer 及 Stack pointer, 但為何稱為  Virtual , 則是有些機器並無保留特定的 Register, 通常用 Stack pointer 加上 offset 來表示.
  3. Pseudo Register : 則是代表每一個可被分配暫存器的最小單位,  Pseudo Register 僅用於 Compiler 內部使用, 且數目可無限多個不被  Hard Register 的數目限制, 但最終經過 Register Allocation 後, IR 內部將不會有任何 Pseudo Register.

另外補上一些名詞說明

  1. Coalesce : 看到類似 mov a, b 的指令時, 試著強制合併 a, b 藉此分配到相同暫存器或記憶體空間(如 LRA 中的Memory-memory move), 以此消除搬移指令
  2. Inheritance : 這個是在 LRA 中的專有名詞, 跟 Coalesce 的概念有點類似, 但主要差別在於其作用範圍在 EBB
  3. Spill : 當暫存器不足以使用時, 將變數暫時存回 Memory, 這個行為稱為 Spill
  4. Constraint : 指 gcc 在每道 insn pattern 中對於每個 Operand 的規範, 通常寫在 md 檔裡面

目前 LRA 還尚在開發當中, 在 gcc 4.7 中尚無計畫合併進來, 但仍然是個相當令人期待的專案, 若 LRA 發展順利則可降低 Porting 難度, 以及實作 Register allocator 的難度, 否則現在卡了個 Reload 改 Register allocator 相當容易吃鱉還不知道真正錯誤原因而無從 debug 起...


參照連結
[1] http://gcc.gnu.org/wiki/reload
[2] http://vmakarov.fedorapeople.org/LRA.html