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] 程式設計師的自我修養：連結、載入、程式庫