火星蚊的地球記事

看這篇 paper。

問題 & 情境

Reactor pattern 處理一個 application 收到從一個或多個 client 同時（concurrently）送 request 的情況。

分散式環境的 server 必須處理多個送 request 過來的 client。為了處理 request，server 必須 demultiplex 以及 dispatch request 給對應的 service。設計 demultiplexing 及 dispatching 需考量：

• Availability
  server 在等待某些 request 時（例如 server 與 client 間需要多步驟溝通，server 正在等 client 的某個步驟），server 依然能處理收到的 request，不能因為處理某個 request 而 block 住，不然會卡到對其他 request 的 response。
• Efficiency
  server 要最小化 latency、最大化 throughput 以及避免不必要的 CPU 使用。
• Programming simplicity
  顧名思義，程式寫得愈簡單愈好。
• Adaptability
  容易新增或改進 service，修改最少現有的 code 就能加新功能或改進功能，例如新增 service 不用修改底層的 dispatching 機制。
• Portability
  容易 porting 到其他 OS 平台等。

常常聽到看到 reentrancy 但老是跟 thread-safety 搞得不是太清楚。

Reentrancy

reentrancy 是 function 可以在執行過程中被中斷，在上一次執行還沒完成前可以再次進入這個 function 執行而不會有問題，也就是第二次進入 function 執行結束後，第一次的執行仍能正確完成。中斷可以是 jump 或 call，也可以是系統的 interrupt 或 signal。

reentrancy 是 single thread 環境下就有的概念。像是被系統 interrupt 中斷時 interrupt handler 是不是能夠再 call 剛剛執行到一半的 function？反過來說，interrupt handler 能 call 的只有 reentrant function。另外，recursive function 一般會是 reentrancy，但如果它使用了 global 變數就不一定。

reentrancy function 可以是 thread-safe 但不一定是 thread-safe。thread-safe function 可以是 reentrancy 也可以不是（繞口令時間）。function 是 thread-safe 但不是 reentrancy 的例子：

1
2
3
4
5
6

function foo()
{
	mutex_lock();
	//blah...
	mutex_unlock();
}

在 single thread 的環境下，如果 foo() 執行到一半被 interrupt 打斷，interrupt handler 又 call foo() 會永遠等不到 mutex unlock，整個卡在那。

達成 reentrancy 的基本原則：

• 不使用 global（或 static）的變數
  但如果執行過程確保 global 變數或 state 能在執行前後保持一致，是可以用的。
• 不修改自身的 code
• 不 call non-reentrant function

Thread-safety

thread-safety 是在 multiple thread 的環境下，thread 間的 shared data 可以在任意執行順序下依然保持正確。

達到 thread-safety 的方式分兩大類，一是避免 race condition，二是 synchronization。

1. 避免 race condition

• 寫成不使用 global 變數的 reentrancy code
  這種 reentrancy code 的寫法可以達成 thread-safety，但不是所有 reentrancy code 都是 thread-safety。反之，因為有很多達成 thread-safety 的方式，不是所有 thread-safety 都是 reentrancy。
• 使用 thread-local storage（TLS）
  存在 TLS 裡的 data 是屬於某個 thread 的，不會在 thread 間共享。
• shared data 使用 immutable object
  data 不會變當然就沒有 race condition 的問題啦！XD

2. synchronization

• mutual exclusion 以及其變形們
  要注意 dead-lock 或 resource starvation 等等問題
• atomic operation
  確保 operation 不會被打斷的，通常有賴 instruction 層級的支援。高階 mutual exclusion 也是需要靠 atomic operation 實作的。

不同的 terminology

不同的 library、系統或語言可能自己定義 thread-safe 跟 reentrant。

例如 Qt 將 reentrant 以及 thread-safe 都定義在 multiple thread 的環境下。針對 class 來說，Qt 的 thread-safe class 是 multiple thread 可以 call 同一個 class instance 的 member function，而 reentrant class 則是 multiple thread 只要使用不同的 class instance 就能同時 call member function。

這篇是設計 concurrent algorithem 的理論概念，沒什麼例子。

兩種設計 concurrent algorithem 的方法：

• Task Decomposition：計算是一堆獨立的 task，可以由 thread 以任意順序執行。
• Data Decomposition：程式處理大量資料，其中個別 element 的計算可以獨立執行。

Task Decomposition

task decomposition 的目標是找出完全獨立的計算，才能 concurrent 執行多個 task。但是計算常常互相有關係，這樣的關係稱為 dependency。程式平行化前必須先消除 dependency。

將 sequential 程式轉成 concurrent 程式要確保原本有順序性的步驟也要依序完成，也就是確保 sequential consistency，使得 concurrent 程式在相同的 input 可以得到跟 sequential 程式一樣的結果。

concurrent 程式的基本架構：main thread 定義以及準備 task，產生 thread 執行 task，最後等待 thread 們完成工作。

一種分解 task 的方式是在要進行 concurrent 計算的外層進行分解，接著將 task 分給 thread 執行。另一種是 task 會在計算過程中動態產生，這需要額外程式碼封裝新產生的 task。

Task Decomposition 要考慮：

1. task 是什麼以及如何定義？
2. task 間的 dependency 為何以及如何滿足？
3. task 如何分派給 thread？

task 是什麼以及如何定義？

基本上，要識別出能獨立執行的 task，得依靠對程式以及其計算的理解。要對可能平行化執行的程式模擬兩個 thread 一起執行的狀況（真心覺得這靠練習跟經驗，做多了自然會有莫名的直覺(?)），以此決定 task 是否彼此獨立或有可接受的 dependency。

並行化（concurrent）程式執行最頻繁或者計算最繁重的地方可以有比較好的成效。因為並行化需要修改程式碼、驗證以及debug 等等，也會讓程式變得複雜，當然要選擇最有成效的地方做。除此之外，concurrent 程式會比 sequential 程式多出為了並行化的程式碼，例如管理及分派 task，所以會有 overhead。

找到可以獨立執行的 task 後，拆分 task 需注意：

1. task 數量至少要跟 thread 或 core 數量一樣多。
   確保不會有 idle 的 thread，能達到較好的 load balance。
2. 每個 task 的計算量（granularity）必須大到能抵消管理 task 及 thread 的 overhead。
   coarse-grained 代表 granularity 高（task 的計算量高），fine-grained 代表 granularity 低。如果 task 的 granularity 不夠大，光是管理 task 跟 thread 的 overhead 就把效能提升給吃光了。

這兩個條件看起來有點矛盾，因為在總 task 固定的情況下 task 愈大數量愈少，反之亦然，因此 要在 task 計算量及數量間取得平衡。並行化（concurrent）程式最主要的目的是減少執行時間，如果使用所有 core/thread 卻需要較長執行時間，寧可調整為使用較少 core/thread 但執行時間較短的 task decomposition。

拆分 task 可能需要多次嘗試，一個切法的效果不太好，就應該嘗試其他分解方式。

task 間的 dependency 為何以及如何滿足？

task 間的 dependency 有兩種：

1. 執行順序的 dependency
   某些 task 必須等其他 task 完成才能做，可能是需要前面 task 的結果作為參數。
   要滿足執行順序 dependency 最簡單的方式是將有此 dependency 的 task 交給同一個 thread 執行。但當某 task 需要許多 thread 的 task 完成後才能執行，或者 thread 間有執行順序的限制（例如要 thread1 做完前幾步 thread2 才能執行），而且無法以其他 task decomposition 處理時就得加入 synchoronization 機制來確保 thread 間的執行順序。
2. data dependency
   區分是否有 data dependency 的方法：先列出所有 assignment 左邊的變數，檢查這些變數是否有並行（concurrent）寫入或者寫入與讀取會並行發生的狀況，因為至少要有一個 thread 寫入變數才會有 data dependency。找到 data dependency 後就要看能不能消除 dependency。消除 data dependency 有很多種作法，最簡單的是以互斥存取（mutually exclusive access）的方式 access shared data，也就是使用 lock 或 mutex 保護資料。

消除 dependency 的方法很多，不見得都得用 mutually exclusive access，如果可以以消除 dependency 的作法來達到 concurrency，就可以減少使用 synchoronization 物件帶來的 overhead。

task 如何分派給 thread？

thread 執行時希望各 thread 有差不多的計算量，平衡 thread 們的 loading。

兩種分派 task 的方式：static scheduling 以及 dynamic scheduling。

static scheduling 會要並行化（concurrent）的計算外面決定 task 的切分，而且計算過程中不會改變。實作 static scheduling 會讓 N 個 thread 有 0 到 N-1 的唯一識別碼，可以透過識別碼分派 task 給 thread。static scheduling 適用於每個 task 的運算量差不多，或是能預先知道計算量的情況。反之，各 task 計算量變動大或無法預先知道的狀況比較適合 dynamic scheduling。

dynamic scheduling 在計算過程中才將 task 指派給 thread，會儘量平均各 thread 的計算量，理想上會有較好的 load balance。分派 task 給 thread 以及 thread 找新 task 的邏輯是原先 sequential 程式沒有的，這些額外的邏輯當然有 overhead。

最簡單的 scheduling 是為 task 加上 index，用 counter 記錄下一個要分派的 task，當 thread 要新 task 時就從 counter 得知拿哪個 task。這個 counter 是 thread 間共用的，因此 access 它需要 mutually exclusive。另一種 dynamic scheduling 使用 shared container 保存 task，通常會用 queue，thread 從 container 拿新 task 執行，例如 producer-consumer 就是這種方式的變形。因為放在 container 裡，task 必須被封裝成可以放進 container 的結構，例如可能是一包描述 task input 的 structure。

Data Decomposition

計算是一連串更新一個或多個巨大 data structure 中的 element 時，如果這些更新是彼此獨立的，則可以切割 data structure 並將不同部份分給不同 thread 處理，進而達到並行化（concurrent）。切割 data structure 並交給 thread 處理的方法稱為 data decomposition。

如何將 data structure 切割成多個連續區域（稱為 chunk）取決於 data structure 的 type，例如常見的 array 會依照 dimension 來切割。

將資料分割成 chunk 也代表將整個計算分解成針對單一 chunk 的 task，這些 task 會分配給 thread 執行。由於資料是已經分解過的，所以 thread 可以安心使用這些 data，不需要擔心其他 thread 也會使用到。但如果計算需要 chunk 鄰近的資料，task 間就得共享這些資料，thread 也需要彼此協調資料存取。

data decomposition 要考慮：

1. 如何將資料分割成 chunk？
2. 如何確保 task 能 access 到其計算所需的所有資料？
3. 如何分派 chunk 給 thread？

如何將資料分割成 chunk？

每個 chunk 都跟 task 有關，要考慮上述 task 的幾個條件，除此之外還需要注意：

1. 每個 thread 至少分到一個 chunk，每個 thread 分到的 chunk 愈多愈好。
2. 處理 chunk 的計算量要遠大於分割 data 所產生的 overhead。
   1. task 處理 chunk 需要的計算量一樣稱為 granularity，granularity 跟 chunk 中的 element 數量有關。
   2. 分割 data 還需要考慮 chunk 的 shape（就是形狀啦）。chunk 的 shape 決定了跟相鄰 chunk 的關係以及計算時如何處理資料交換，shape 並不見得是畫得出來、看得到的形狀，而是 chunk 之間的「關係」。資料交換是為了計算與更新自己的資料而需要去 access 別人（別的 chunk）的資料。如果每個 chunk 的邊界（處在邊界的 element）都需要資料交換，減少整體邊界數量就能減少資料交換。針對每個 chunk 減少與其相鄰的 chunk 數量也能降低交換資料的程式複雜度，因為一個 chunk 與愈多 chunk 相鄰代表一個 task 跟更多 task 有關聯。

考慮 chunk 的 shape 時，granularity 愈大表示 chunk 擁有的 element 數量愈多，也代表有愈多需要資料交換的 element，因此資料交換的 overhead 愈大，又需要在 shape 與 granularity 之間取得平衡。針對這個問題，一個解法是最大化 volume-to-surface ratio，也就是 chunk 的 element 數量與需要交換資料的邊界比例，也就是 chunk 的 element 數 / chunk 中在邊界的 element 數。例如一個 4 x 8 的資料（想像一個二維陣列），分割成兩個 2 x 8 的 chunk，volume-to-surface ratio 是 16 / 8 = 2，分割兩個 4 x 4 的 chunk 則是 16 / 4 = 4。

如何確保 task 能 access 到其計算所需的所有資料？

如果 chunk 內包含計算與更新所需的所有資料，task 間就不需要協調資料交換（這不是廢話）。反之，如果計算需要鄰近 chunk 的資料，就得找出較有效率的資料交換機制。一般有兩種方法：將資料從鄰近 chunk 複製到 task/thread 的 local structure，或者直接 access 鄰近 chunk 的資料。

如果鄰近 chunk 的資料不會隨著計算改變，複製資料是比較容易的方法，因為不需要處理同步問題。缺點是需要額外的儲存空間存放資料副本。這些額外配置的儲存空間一般稱為 ghost cells。複製資料也需要考慮複製次數，如果次數太多或每次複製太多資料，比較適合直接 access 鄰近 chunk 的資料。

直接 access 鄰近 chunk 的資料可以利用 thread 間以 shared memory 為基礎的溝通機制，在真正需要資料前也可以不用協調。缺點是必須確保拿到正確的資料，尤其是鄰近 chunk 也會更新其資料的時候。要確保拿到正確的資料，得找出計算過程中資料交換與更新資料間的關係或互動，才能知道如何協調。有些 sequential 程式計算 element 時需要鄰近 element 的舊資料而非更新後的新資料，此時 sequential 程式與 concurrent 程式遇到的問題是一樣的，concurrent 程式有時能借用 sequential 程式的解法。

如何分派 chunk 給 thread？

類似 task decomposition，與 chunk 關聯的 task 可以用 static 或 dynamic scheduling 指派給 thread。static scheduling 所有跟資料交換有關的協調可以在計算外面、也就是計算開始前處理好，適合 task 的計算是一致或可預期的情況。如果 task 處理各 chunk 的計算量不一致，dynamic scheduling 可能有比較好的 load balance，但也讓資料更新、交換以及與其他 task 協調變得複雜。

data decomposition 中 task 是由資料的分解方式定義的，應該以 task 間的關係找出所需的互動，不管這個 task 是由哪個 thread 執行。

選擇 Design Model 需考量的因素

在做 task 或 data decomposition 時，會考量以下四個因素以建立最有效率的 concurrent solution：

1. Efficiency（效率）
   效率必須考慮 concurrency 帶來的額外 overhead、thread 的調配以及 task 的組織方式等等問題。
2. Simplicity
   concurrent algorithem 愈簡單愈容易開發、debug、驗證以及維護。simplicity 著重在要加多少額外程式碼才能將程式並行化（concurrent）。
3. Portability
   使用不同 multiple threading model 的取捨。
4. Scalability
   考量 concurrent 程式在不同 core/thread 數以及 data set 上的行為如何。照目前的趨勢，機器的 core 數會愈來愈多，concurrent 程式應該要能夠有效率的在不同數量的 thread/core 或不同大小的 data set 上執行。

重要性：scalability > efficiency > simplicity ~ portability

有時候 concurrent 程式的 scalability 會在某個階段達到高峰後趨於平緩，這可能是因為 algorithem 的需求或是 threading model 提供的環境。遇到這種狀況要評估是否值得花更多力氣嘗試提高 scalability 或者使用不同的 threading model 重新寫過。

記錄開放街圖 Open Street Map（OSM） API 的基本使用跟文件。

Editing API

RESTful API，data 格式為 XML，目前版本為 v0.6。

文件：

• http://wiki.openstreetmap.org/wiki/API
• http://wiki.openstreetmap.org/wiki/API_v0.6

程式化編輯資料要注意的事情：

• http://wiki.openstreetmap.org/wiki/API#Terms_of_use
• http://wiki.openstreetmap.org/wiki/Automated_Edits_code_of_conduct

OSM 有提供測試用 API，測試站跟正式網站的帳號是分開的。

• 測試站：https://master.apis.dev.openstreetmap.org/
• 測試用 API：https://master.apis.dev.openstreetmap.org/
• 正式 API：http://api.openstreetmap.org/

編輯修改 element 必須 reference 到一個 changeset，可以想成修改 log。changeset 跟 element 一樣有 tag，文件建議包含 comment=* 以及 created_by=* tag，簡述改了什麼以及由誰修改。

API 使用流程

1. 生一個 changeset 得到 changeset id
2. call API 修改 element，會帶 changeset id
3. 關閉 changeset

changeset 如果沒有關掉，OSM 有規則會自動關閉它。

Authentication

editing API 需要 authentication，可以用 HTTP basic authentication，即在 http header 加上 Authorization: Basic xxx，其中 xxx 是 user:password 的 base64 字串。nodejs 下可以用 new Buffer("Hello World").toString('base64'); 得到 base64 字串。

以 curl 送 request：

1
2

$ curl https://master.apis.dev.openstreetmap.org/api/capabilities
$ curl -H "Authorization: Basic xxx" https://master.apis.dev.openstreetmap.org/api/0.6/permissions

除了 HTTP basic authentication 外也可以使用 OAuth，這我沒研究。

剩下 API 使用參考文件定義囉。

Overpass API

read only API

• http://wiki.openstreetmap.org/wiki/Overpass_API
• http://wiki.openstreetmap.org/wiki/Overpass_API/XAPI_Compatibility_Layer

Overpass API 有幾種 query 語法，大致分成 XML query format 跟 Overpass QL，相關文件：

• http://wiki.openstreetmap.org/wiki/Overpass_API/Language_Guide
• http://wiki.openstreetmap.org/wiki/Overpass_API/Overpass_QL

我只用 XAPI Compatibility Layer 做簡單的 map 讀取跟 tag query，沒使用上面比較複雜的 query 功能。

XAPI Compatibility Layer 基本 HTTP GET：

1
2
3

http://www.overpass-api.de/api/xapi?map?bbox=left,bottom,right,top
http://www.overpass-api.de/api/xapi?map?bbox=121.53828,25.045,121.540,25.05
http://www.overpass-api.de/api/xapi?node[bbox=121.53828,25.045,121.55,25.06][highway=traffic_signals]

tag 可以串很多，會被 and 起來，其中 node 也可以改成 way 跟 relation。

執行檔如何尋找 shared library

ELF 將依賴的 shared library 存在 .dynamic section 的 DT_NEED 欄位。

1
2
3
4
5
6
7

$ readelf -d main

Dynamic section at offset 0x868 contains 26 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [./libfoo.so]
 0x0000000000000001 (NEEDED)             Shared library: [./libbar.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]

如果是絕對路徑， dynamic linker 直接去該路徑存取 shared library。如果是相對路徑，則會依照以下順序到不同路徑下找 library：

• LD_LIBRARY_PATH 環境變數指定的路徑
• .dynamic section 中 DT_RUNPATH 欄位記錄的路徑
• /etc/ld.so.conf 設定的路徑（實際上是讀取 /etc/ld.so.cache）
• /lib
• /usr/lib

因為一個個搜尋路徑很慢，所以指令 ldconfig 除了更新系統中 library 的 SO-NAME soft link 外，還會將這些 SO-NAME 以特殊的形式存在 /etc/ld.so.cache 作為 cache 以加快搜尋。所以增加、刪除或更新 shared library 以及修改 /etc/ld.so.conf 後，都要執行 ldconfig 來更新 SO-NAME。

環境變數

幾個跟 dynamic linking 有關的常用環境變數。

LD_LIBRARY_PATH

臨時改變 shared library 的搜尋路徑，開發跟 debug 的時候很好用。

1

$ LD_LIBRARY_PATH=/home/foo ls

LD_PRELOAD

可以指定預先 load 的 shared library 或 object file，無論執行檔或使用的 shared library 有沒有依賴它。因為會使用先 load 的 shared library 的 symbol，所以可以用來改掉原本執行檔使用的 shared library，例如 standard C library。

1

$ LD_PRELOAD=./libfoo.so ./main

LD_DEBUG

可以看 dynamic linker 的 debug 訊息，設成 help 可以看可設定的值。

建立 & 安裝 shared library

build 出 shared library：

1

$ gcc -shared -fPIC -Wl,-soname,mysoname -o library_name sources

-shared 表示輸出 shared library，-fPIC 表示使用 PIC。-Wl 可以將參數傳給 linker。-soname 是指定 SO-NAME，如果不指定，shared library 預設沒有 SO-NAME，即無法用 ldconfig 建 soft link。shared library 的 SO-NAME 可以用 readelf -d 查看。

去除 symbol 資訊可以讓 shared library 檔案變小，常用在 release 時：

1

$ strip libfoo.so

安裝 shared library 通常是放到系統相關的路徑下，例如 /lib、/usr/lib 等，然後執行 ldconfig 更新 soft link。不過通常安裝會用 make install 之類的指令，不需要手動 copy 跟 ldconfig。

Related Posts & Ref

• ld-linux manual
• 《程式設計師的自我修養》ch8
• Dynamic Linking Basic
• Dynamic Linking PIC
• Dynamic Linking Relocation
• Shared Library Versioning
• Explicit Runtime Linking

相容性問題

使用 library 其中一個目標是不需要重新 compile 就能方便的升級程式的部份功能或者修正 bug。理想上，升級 library 只需要用新的檔案取代舊的。但是事情沒那麼美好，舊程式不見得能正常使用新 library，新舊程式間會有相容性問題。

依據舊程式能不能使用新 library，library 的更新分為相容更新與不相容更新。相容更新通常不修改 interface，可能只是修正 bug 或者加點新東西。不相容更新則改變了 interface，這時舊版程式無法正常使用新版 library。

library 以 binary 的形式發佈，代表 interface 是 binary 層級，也就是 ABI（Application Binary Layer），包含 call function 的 stack 結構、symbol 命名、memory 配置、參數的結構等等。

ABI 跟語言有很大關係，以 C 語言來說，只要跟 export 的 symbol（function 跟 variable）有關的修改，都會動到 ABI，例如增加 export 變數、增減 export 的 function 參數、修改 export 的資料結構（會改變 memory 配置，程式依舊配置使用新結構會踩壞記憶體）等等。至於 C++ 基本上是場災難，因為各家 compiler 甚至相同 compiler 的不同版本可能都對 C++ 的各種特性諸如 virtual function 等有不同實作方式，這會造成 ABI 不相容。C++ 有一些避免改到 interface 的原則及作法，例如 pimpl。

版號

既然有相容性問題，程式如何知道能不能使用新 library？系統必須有方法確保相容性、讓程式能正常執行，其中一個方法是以版號區分不同版本的 library，並讓程式指定它相容於哪些版本的 library。

在 Linux 系統中，shared library 的檔案命名規則為 libname.so.x.y.z。最前面是字首 lib，中間是 library 名稱，接著 .so，最後跟著三個版號數字。x 表示 major versison number，y 是 minor version number，z 為 release version number。

major version number 代表 library 有重大升級，不同 major version number 的 library 是不相容的。使用舊版的程式必須要經過修改及重新 compile 才能使用新版 library。系統中需要保留舊版 library 以讓未更新至使用新版 library 的程式依然能正常執行。

minor version number 表示 library 是增量升級，也就是加一些新的 interface 並且保持原本的 symbol 在名稱與語意上皆不變，例如增加一個 function。在 major version number 相同的狀況下，高 minor version number 的 library 向後相容低 minor version number 的 library，使用舊版 library 的程式可以使用新版 library，例如使用 1.1.z libary 的程式可以在 1.2.z library 上正常執行。

release version number 是 library 的 bug 修正、效能改進等等，不添加新 interface 也不改動舊 interface。因此相同 major version number 以及 minor version number 的不同 release version 之間的 library 完全相容，依賴某個 release version 的程式可以使用其他任一 release version。

SO-NAME

library 有版號之後，程式如何指定使用的 library 版本？

在 Solaris 跟 Linux 裡採用 SO-NAME 命名機制，SO-NAME 是 library 版號只保留 major version number，去掉 minor version 以及 release version，例如 libfoo.so.3.2.1 的 SO-NAME 是 libfoo.so.3。

Linux 系統會建立檔名為 SO-NAME 並指向 major version 相同、最新 minor 及 release version 的 library 實體檔案的 soft link，例如 /usr/lib/libcln.so.6 指向 /usr/lib/libcln.so.6.0.4。這麼做的好處是系統中的程式只需要記錄 library 的 SO-NAME，再藉由 soft link 就能使用該 major version 最新的 library。

記錄 SO-NAME 提供了一些彈性，讓 library 有一定的升級空間，不會讓程式只限定於某版本的 library。同時又能知道何種狀況是大幅度的更新，系統不應該自動使用新 major version 的 library，需保留舊版 library 讓使用的程式可以正常執行。當然，話是這麼說，版號只是個規則，還是需要由開發者判斷新版是否向後相容以決定如何升版號。

ELF 在 .dynamic 以 SO-NAME 記錄所需的 shared library：

1
2
3
4
5

$ readelf -d main
Dynamic section at offset 0x868 contains 26 entries:
  Tag        Type                         Name/Value
...
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]

Linux 指令 ldconfig 用來更新上述 library 的 soft link，它會掃過所有預設 shared library directory，例如 /lib、/usr/lib 等，更新所有 soft link，將其指向目前系統中最新的 library 或為新 library 建立 soft link。安裝或更新 library 需要執行 ldconfig。

link name

compile 時我們以 -lXXX 指定要 link 的 library，這個 XXX 稱為 link name。指定 link name 時省略了版號，compiler 會到系統相關的搜尋路徑中尋找最新版本的 XXX library。

Symbol Versioning

SO-NAME 有升級彈性，但仍有問題──假設依賴的 library 是 libfoo.2.3.1，SO-NAME 是 libfoo.2，但執行環境中只有 libfoo.2.2.1，以 SO-NAME 來看是正確的，但卻可能不相容，因為程式可能使用 libfoo.2.3.1 才有的 interface，這在 libfoo.2.2.1 中找不到，因而執行錯誤。這個問題稱為 Minor-revision Rendezvous Problem。

為解決 Minor-revision Rendezvous Problem，Solaris 2.5 發展出 symbol versioning 機制，提供 versioning 以及 scoping 機制。

Versioning

基本概念是在每個 import 及 export symbol 加上版號，例如 libfoo.1.3 要更新為 libfoo.1.4 時，就把 libfoo.1.4 增加的 symbol 加上 VERS_1.4 的標記。如此 SO-NAME 是 libfoo.1 各版 library 裡會有 VERS_1.2、VERS_1.3、VERS_1.4 等等擁有不同版號標記的 symbol，就能區別 symbol 的版本了。

versioning 定義了一些 symbol 集合。symbol 集合有名稱，例如 VERS_1.2，每個集合包含一些 symbol，一個集合能包含另一個集合，例如 VERS_1.2 包含 VERS_1.1，這種包含關係也像是繼承，VERS_1.2 繼承 VERS_1.1 的 symbol。symbol 集合由 symbol version script 指定，在 gcc 可以用 -Xlinker --version-script <script file> 指定。

versioning 機制讓 symbol 可以標上版號，build 執行檔時會記錄它需要的 symbol 及其版號。因為 symbol 只能有一個 version，在相同 major version 的 library 中，同一個 symbol 的 version 是固定的，否則會導致向後不相容。因此，執行檔執行時可以用 SO-NAME 找到系統中最新的 library，接著看它是不是有所需要版本的 symbol，如果有就能正常執行，以此解決 Minor-revision Rendezvous Problem。

但 Solaris 2.5 的 symbol versioning 有個限制：在一個 shared library 中每個 symbol 只能有一個 version，也就是如果 symbol 是 VERS_1.1 就不能再是 VERS_1.2。這造成如果 interface 只有小修改，例如只加一個參數、依然向後相容（只是擴充，舊有功能不變），由於無法讓新版 library 標示該 symbol 為新版，只能透過增加 major version 來表示 interface 改變，有點小題大作。

Example

source code

1

int foo(int x, int y);

1

int foo(int x, int y) { return (x + y); }

1
2

int foo(int x, int y);
int foo2(int x);

1
2

int foo(int x, int y) { return (x + y); }
int foo2(int x) { return (x + x); }

1
2
3
4
5
6
7

#include "foo-1.0.h"
#include <stdio.h>
int main()
{
    printf("%d\n", foo(2, 3));
    return 0;
}

1
2
3
4
5
6
7
8

#include "foo-1.1.h"
#include <stdio.h>
int main()
{
    printf("%d\n", foo(2, 3));
    printf("%d\n", foo2(12));
    return 0;
}

1
2
3
4
5
6

VERS_1.0 {
    global:
        foo;
    local:
        *;
};

1
2
3
4
5
6
7
8
9
10
11

VERS_1.0 {
    global:
        foo;
    local:
        *;
};

VERS_1.1 {
    global:
        foo2;
} VERS_1.0;

library 版本更新的時候，可由新的 symbol 集合看出它的 interface 改動，例如上面 1.1 版繼承了 1.0 版、增加了 symbol foo2。

1
2
3
4
5
6
7
8
9
10
11
12

1.0:
        gcc -shared -fPIC foo-1.0.c -Xlinker --version-script foo.1.0.ver -o libfoo.1.0.so
        rm -f libfoo.so
        ln -s libfoo.1.0.so libfoo.so
        gcc main1.c ./libfoo.so -o main1

1.1:
        gcc -shared -fPIC foo-1.1.c -Xlinker --version-script foo.1.1.ver -o libfoo.1.1.so
        rm -f libfoo.so
        ln -s libfoo.1.1.so libfoo.so
        gcc main2.c ./libfoo.so -o main2

看看 library 的 export symbol：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

$ readelf --dyn-syms libfoo.1.0.so 

Symbol table '.dynsym' contains 9 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 00000000000004b0     0 SECTION LOCAL  DEFAULT   10 
     2: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     3: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     4: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     5: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable
     6: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (3)
     7: 0000000000000600    20 FUNC    GLOBAL DEFAULT   12 foo@@VERS_1.0
     8: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.0

$ readelf --dyn-syms libfoo.1.1.so 

Symbol table '.dynsym' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000528     0 SECTION LOCAL  DEFAULT   10 
     2: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     3: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     4: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     5: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable
     6: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (4)
     7: 0000000000000680    20 FUNC    GLOBAL DEFAULT   12 foo@@VERS_1.0
     8: 0000000000000694    14 FUNC    GLOBAL DEFAULT   12 foo2@@VERS_1.1
     9: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.0
    10: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.1

兩個 library 的 symbol foo 後面加上 VERS 資訊。如果多個 symbol 集合裡有相同 symbol，第一次出現 symbol 的集合是該 symbol 的 version。另外，會被包含的集合必須先寫。也就是說 symbol version 的前後關係是由 version script 指定的，通常遵照數字順序寫（不然會誤導別人啦）。

執行檔可以看到使用的 symbol 版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

$ readelf --dyn-syms main1

Symbol table '.dynsym' contains 8 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     2: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND foo@VERS_1.0 (2)
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.2.5 (3)
     4: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (3)
     5: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     6: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     7: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable

$ readelf --dyn-syms main2

Symbol table '.dynsym' contains 9 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND foo2@VERS_1.1 (2)
     2: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND foo@VERS_1.0 (3)
     4: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.2.5 (4)
     5: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (4)
     6: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     7: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     8: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable

修改 soft link libfoo.so 指向的 library，main1 依然可以正常使用 1.1 版的 library，但 main2 無法使用 1.0 版的 library，會跳 ./main2: ./libfoo.so: version 'VERS_1.1' not found (required by ./main2) 找不到 symbol 的 error。

Scoping

在 symbol 集合裡，local: 的設置會將原本 global 的 symbol 變成 local 的，程式以及其他 shared library 無法使用到這些 symbol。這稱為 scoping 機制，算是補強 ELF 處理 C 的 global symbol scoping，因為 ELF 把所有 global symbol 當作 export symbol，這也是為什麼 Linux 下不需要特別指定哪些 global symbol 要 export 就能 export symbol（windows 就需要）。

上面的例子裡如果把 foo.1.0.ver 裡 local: *; 拿掉，原本其他的 export symbol 就不會被設成 local：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

$ readelf --dyn-syms libfoo.1.0.so

Symbol table '.dynsym' contains 14 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000570     0 SECTION LOCAL  DEFAULT   10
     2: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     3: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     4: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _Jv_RegisterClasses
     5: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable
     6: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (3)
     7: 00000000002009b8     0 NOTYPE  GLOBAL DEFAULT   22 _edata
     8: 00000000000006c0    20 FUNC    GLOBAL DEFAULT   12 foo@@VERS_1.0
     9: 00000000002009c0     0 NOTYPE  GLOBAL DEFAULT   23 _end
    10: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.0
    11: 00000000002009b8     0 NOTYPE  GLOBAL DEFAULT   23 __bss_start
    12: 0000000000000570     0 FUNC    GLOBAL DEFAULT   10 _init
    13: 00000000000006d4     0 FUNC    GLOBAL DEFAULT   13 _fini

GCC 對 symbol version 的擴充

GCC 對於 symbol version 提供兩個擴充。第一個是可以指定 symbol 的 version，例如 asm(".symver foo_new, foo@VERS_1.1"); 指定 foo_new 是 symbol foo 的 1.1 版。

第二個擴充是允許同個 symbol 有多個版本，這補充了 Solaris 版本機制的限制。例如上面例子裡想在 1.1 版的 foo() 增加一個參數，但希望仍保留舊版功能好能向後相容，這時候就能以指定不同版本來達到。

1
2
3
4
5
6

asm(".symver foo_old, foo@VERS_1.0");
asm(".symver foo_new, foo@@VERS_1.1");

int foo_old(int x, int y) { return x + y; }
int foo_new(int x, int y, int z) { return (x + y + z); }
int foo2(int x) { return (x + x); }

兩個 .symver 分別指定 foo_old() 是 foo 的版本 1.0，foo_new() 是版本 1.1。因為已經用 .symver 自訂 foo 這個 symbol，如果又寫 foo() link 時會有 multiple definition 錯誤。foo@@VERS_1.1 表示 foo 預設版本是 1.1，一個 symbol 的預設版號只能有一個，實驗看起來預設版號會影響 compile 執行檔時記錄的 symbol。由於仍然有 1.0 的 foo，main1 用新版 library 仍能正常執行。

1
2

int foo(int x, int y, int z);
int foo2(int x);

1
2
3
4
5
6
7
8

#include "foo-1.1.h"
#include <stdio.h>
int main()
{
    printf("%d\n", foo(2, 3, 5));
    printf("%d\n", foo2(12));
    return 0;
}

header 跟 library 檔一起發佈，在 compile 執行檔時讓執行檔知道有什麼 symbol，所以必須要是新版 foo 的 prototype，而且 function name 也要是 foo，而非 foo_new。（我想還是有別的方式可以做到同樣的事情，甚至可以刻意使用舊版 symbol，這只是我認為合理的 library 發佈以及使用方式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

$ readelf --dyn-syms libfoo.1.1.so 

Symbol table '.dynsym' contains 12 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     7: 0000000000000690    20 FUNC    GLOBAL DEFAULT   12 foo@VERS_1.0
     8: 00000000000006a4    28 FUNC    GLOBAL DEFAULT   12 foo@@VERS_1.1
     9: 00000000000006c0    14 FUNC    GLOBAL DEFAULT   12 foo2@@VERS_1.1
    10: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.0
    11: 0000000000000000     0 OBJECT  GLOBAL DEFAULT  ABS VERS_1.1

$ readelf --dyn-syms main2

Symbol table '.dynsym' contains 9 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     1: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND foo2@VERS_1.1 (2)
     6: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND foo@VERS_1.1 (2)

Semantic Versioning

由 Tom Preston-Werner 提出的 Semantic Versioning 以 spec 的形式提供了版號規範，例如每個數字代表的意義、何時該增加版號、如何增加版號以及如何區分版本的新舊等等。它定義的版號包含 MAJOR.MINOR.PATCH 三個數字，並且可以加上如 -alpha、-beta 等 pre-release 資訊。概念與上面說的 library 版號類似，interface 有變更時需增加 major verion，增加向後相容的功能時要增加 minor version，修 bug 則增加 patch version，只是它以精準定義的方式描述這些規則。

當然，它只定義了版號本身的規則，至於「什麼改變是有向後相容？是否更改的 interface？」等問題仍然要由開發者判斷。

Related posts & Ref

• Library Interface Versioning in Solaris and Linux / pdf
• 《程式設計師的自我修養》ch8
• Using LD, the GNU linker - Version Script
• Semantic Versioning
• Dynamic Linking Basic
• Dynamic Linking PIC
• Dynamic Linking Relocation
• Use Shared Library in Linux
• Explicit Runtime Linking

Load process 在 dynamic linking 的差別是 load 完執行檔後 OS 會先看 ELF 的 .interp section 知道要 load 哪個 dynamic linker，OS load dynamic linker 並將控制權先交給它，在 linux 下是 /lib/x86_64-linux-gnu/ld-2.19.so（很明顯也是個 shared library）。

dynamic linker 做的事情分成三步：

1. 啟動
2. load 所有需要的 shared library
3. relocation & initialization

dynamic linker 本身也是個 shared library，但它有一些限制，例如不能有依賴的 shared library、不能使用 global 變數、不能 call function 等等。在啟動階段，dynamic linker 會先找到自己的 GOT，而 GOT 第一個 entry 存的是 .dynamic section 的 offset。.dynamic section 保存了 dynamic linker 需要的資訊，例如依賴哪些 shared library，dynamic symbol table、dynamic relocation table 的位置等等。readelf -d 可以查看 .dynamic section。

透過 .dynamic 裡的資訊，linker 可以知道自己的 relocation table 以及 symbol table，能對自己進行 relocation。linker 做完針對自己的 relocation 後，才能開始使用 global 變數、call function 等等。

啟動完成後，dynamic linker 將自己的 symbol 以及 executable file 的 symbol 合併到 global symbol table。接著開始從 executable file 的 .dynamic 得知依賴哪些 shared library，一一打開 shared library 並將之 load 到 memory 中、建立 mapping，並且將 shared library 的 symbol 合併到 global symbol table，再搜尋 shared library 的 dependency。如此 traverse 整棵 shared library dependency tree 之後，即 load 完所需的 shared library。通常會以 BFS traverse dependency tree。

symbol 的部份，ELF 以 dynamic symbol table 保存模組間 import 及 export symbol 的關係，位於 .dynsym，作用以及記錄的資訊跟 .symtab 差不多，但只記錄給其他模組使用的 symbol 以及使用其他模組的 symbol。

traverse dependency tree 的順序跟 symbol 的優先度有關──當兩個 shared library 有相同的 symbol 時要使用誰的？在 Linux 中會優先使用先 load 的 symbol。也就是說，shared library 的 load 順序會影響 symbol 的優先度，而 link 時指定的 library 順序會影響 load 的順序。

接著，linker 開始 traverse executable file 以及 shared library 的 relocation table，使用 global symbol table 來修正 GOT 及 PLT 內的 address。dynamic linking 中的 relocation table .rela.dyn 用來修正 .got 及 data section，.rela.plt 則修正 .got.plt section 內的 address。relocation 完成後，如果 shared library 擁有 .init section，dynamic linker 會執行它以進行對 shared library 的初始化。

最後，dynamic linker 將控制權交給程式的入口開始執行。

Relocation example

雖然簡單來說 dynamic linker 會在 load shared library 時進行 relocation，但如Dynamic Linking PIC所說的，實際上 ELF 是以 lazy binding 來 bind symbol。用個簡單例子看看怎麼做的：

1
2
3
4

#ifndef __FOO_H
#define __FOO_H
int foo(int x, int y);
#endif

1
2
3
4

int foo(int x, int y)
{
    return (x + y);
}

1
2
3
4

#ifndef __BAR_H
#define __BAR_H
void bar(int a, int b, int n);
#endif

1
2
3
4
5
6

#include "foo.h"
void bar(int a, int b, int n)
{
    foo(a, b);
    foo(b, n);
}

1
2
3
4
5
6
7

#include "bar.h"

int main()
{
    bar(2, 3, 10);
    return 0;
}

1
2
3

$ gcc -g -shared -fPIC foo.c -o libfoo.so
$ gcc -g -shared -fPIC bar.c -o libbar.so
$ gcc -g main.c ./libfoo.so ./libbar.so -o main

最後編 executable file 時指定的 library 順序會影響 load library 的順序。

在 main()、bar() 跟 foo() 設中斷點，停在 main() 之後觀察 foo 的 relocation 資訊：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

$ gdb ./main
Reading symbols from ./main...done.
(gdb) b main
Breakpoint 1 at 0x40067a: file main.c, line 5.
(gdb) b bar
Breakpoint 2 at 0x400550
(gdb) b foo
Function "foo" not defined.
Make breakpoint pending on future shared library load? (y or [n]) y
Breakpoint 3 (foo) pending.
(gdb) r
Starting program: /home/cjw/source/dynamic-link/relocate/main

Breakpoint 1, main () at main.c:5
5           bar(2, 3, 10);

$ cat /proc/`pgrep main`/maps
00400000-00401000 r-xp 00000000 08:24 8259464                            /home/cjw/source/dynamic-link/relocate/main
00600000-00601000 rw-p 00000000 08:24 8259464                            /home/cjw/source/dynamic-link/relocate/main
7ffff762f000-7ffff77d0000 r-xp 00000000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff77d0000-7ffff79d0000 ---p 001a1000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d0000-7ffff79d4000 r--p 001a1000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d4000-7ffff79d6000 rw-p 001a5000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d6000-7ffff79da000 rw-p 00000000 00:00 0
7ffff79da000-7ffff79db000 r-xp 00000000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff79db000-7ffff7bda000 ---p 00001000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff7bda000-7ffff7bdb000 rw-p 00000000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff7bdb000-7ffff7bdc000 r-xp 00000000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7bdc000-7ffff7ddb000 ---p 00001000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7ddb000-7ffff7ddc000 rw-p 00000000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7ddc000-7ffff7dfc000 r-xp 00000000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7fd5000-7ffff7fd8000 rw-p 00000000 00:00 0
7ffff7ff6000-7ffff7ff8000 rw-p 00000000 00:00 0
7ffff7ff8000-7ffff7ffa000 r-xp 00000000 00:00 0                          [vdso]
7ffff7ffa000-7ffff7ffc000 r--p 00000000 00:00 0                          [vvar]
7ffff7ffc000-7ffff7ffd000 r--p 00020000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7ffd000-7ffff7ffe000 rw-p 00021000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7ffe000-7ffff7fff000 rw-p 00000000 00:00 0
7ffffffdd000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

$ readelf -r libbar.so

Relocation section '.rela.dyn' at offset 0x430 contains 8 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
...

Relocation section '.rela.plt' at offset 0x4f0 contains 3 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000200980  000300000007 R_X86_64_JUMP_SLO 0000000000000000 __gmon_start__ + 0
000000200988  000400000007 R_X86_64_JUMP_SLO 0000000000000000 foo + 0
000000200990  000700000007 R_X86_64_JUMP_SLO 0000000000000000 __cxa_finalize + 0

(gdb) x/1xbg 0x7ffff79da000+0x000000200988
0x7ffff7bda988: 0x00007ffff79da586

(gdb) info address foo
Symbol "foo" is a function at address 0x7ffff7bdb660.

libbar.so 裡需要修正 address 的位置是 0x7ffff79da000 + 0x000000200988，因為 library 要到 load 的時候才能知道起始位置，所以必須用 offset 算出要修改的地方，因為還沒用過 foo，這個 address 的內容還不是 foo 的 address。

1
2
3
4
5

$ readelf -S libbar.so
...
  [20] .got.plt          PROGBITS         0000000000200968  00000968
       0000000000000030  0000000000000008  WA       0     0     8
...

從 relocation entry 來看，relocate 的 offset 是 0x000000200988，在 .got.plt 裡。0x7ffff7bda988 這個位置在 load libbar.so 的第三個 segment，屬性是 rw-p，是可以修改的。

繼續跑看第一次 call foo()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

(gdb) c
Continuing.

Breakpoint 2, bar (a=2, b=3, n=10) at bar.c:7
7           foo(a, b);
(gdb) x/10i $pc
=> 0x7ffff79da6b1 <bar+17>:     mov    -0x8(%rbp),%edx
   0x7ffff79da6b4 <bar+20>:     mov    -0x4(%rbp),%eax
   0x7ffff79da6b7 <bar+23>:     mov    %edx,%esi
   0x7ffff79da6b9 <bar+25>:     mov    %eax,%edi
   0x7ffff79da6bb <bar+27>:     callq  0x7ffff79da580 <foo@plt>
   0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
   0x7ffff79da6c3 <bar+35>:     mov    -0x8(%rbp),%eax
   0x7ffff79da6c6 <bar+38>:     mov    %edx,%esi
   0x7ffff79da6c8 <bar+40>:     mov    %eax,%edi
   0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
(gdb) b *0x7ffff79da6bb
(gdb) c
(gdb) x/1i $pc
=> 0x7ffff79da6bb <bar+27>:     callq  0x7ffff79da580 <foo@plt>
(gdb) si
0x00007ffff79da580 in foo@plt () from ./libbar.so
(gdb) x/3i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
   0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
   0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
(gdb) si
0x00007ffff79da586 in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
(gdb) 
0x00007ffff79da58b in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
(gdb) 
0x00007ffff79da560 in ?? () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da560:      pushq  0x20040a(%rip)        # 0x7ffff7bda970
(gdb) 
0x00007ffff79da566 in ?? () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da566:      jmpq   *0x20040c(%rip)        # 0x7ffff7bda978
(gdb) x/3i $pc
=> 0x7ffff79da566:      jmpq   *0x20040c(%rip)        # 0x7ffff7bda978
   0x7ffff79da56c:      nopl   0x0(%rax)
   0x7ffff79da570 <__gmon_start__@plt>: jmpq   *0x20040a(%rip)        # 0x7ffff7bda980
(gdb) si
_dl_runtime_resolve () at ../sysdeps/x86_64/dl-trampoline.S:34
34      ../sysdeps/x86_64/dl-trampoline.S: No such file or directory.
2: x/i $pc
=> 0x7ffff7df02b0 <_dl_runtime_resolve>:        sub    $0x38,%rsp
(gdb) x/1xbg 0x7ffff7bda978
0x7ffff7bda978: 0x00007ffff7df02b0

0x7ffff79da580 是 foo 在 PLT 裡的位置，call foo() 的時候會跳過去。這個位置位於 load libbar.so 的第一個 segment，屬性 r-xp，可執行，同時也代表 PLT 是被放在可執行的 segment 裡。到 foo@plt 後會再跳到 foo 在 .got.plt 的 entry 所指的 address，也就是前面看到的 0x00007ffff79da586，同時也是 foo@plt 的下一個指令，最後在 0x7ffff79da566: jmpq *0x20040c(%rip) # 0x7ffff7bda978 會跳到 0x7ffff7bda978 記錄的位置 0x00007ffff7df02b0，即 _dl_runtime_resolve 的入口，到這邊當然是要 resolve symbol 啦，至於中間 push 的動作跟給 _dl_runtime_resolve 參數有關。

設中斷點在 call 完 foo() 之後，看看 resolve 完 foo 在 .got.plt 裡對應的 entry 會如何：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(gdb) b *0x7ffff79da6c0
Breakpoint 5 at 0x7ffff79da6c0: file bar.c, line 8.
(gdb) c
Continuing.

Breakpoint 3, foo (x=2, y=3) at foo.c:3
3           return (x + y);
2: x/i $pc
=> 0x7ffff7bdb66a <foo+10>:     mov    -0x4(%rbp),%edx
1: $pc = (void (*)()) 0x7ffff7bdb66a <foo+10>
(gdb) c
Continuing.

Breakpoint 5, bar (a=2, b=3, n=10) at bar.c:8
8           foo(b, n);
2: x/i $pc
=> 0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
1: $pc = (void (*)()) 0x7ffff79da6c0 <bar+32>
(gdb) x/7i $pc
=> 0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
   0x7ffff79da6c3 <bar+35>:     mov    -0x8(%rbp),%eax
   0x7ffff79da6c6 <bar+38>:     mov    %edx,%esi
   0x7ffff79da6c8 <bar+40>:     mov    %eax,%edi
   0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
   0x7ffff79da6cf <bar+47>:     leaveq 
   0x7ffff79da6d0 <bar+48>:     retq   
(gdb) x/1xbg 0x7ffff79da000+0x000000200988
0x7ffff7bda988: 0x00007ffff7bdb660
(gdb) info address foo
Symbol "foo" is a function at address 0x7ffff7bdb660.

出現 foo 的 address 啦！

再看第二次 call foo() 會怎樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

(gdb) b *0x7ffff79da6ca
Breakpoint 6 at 0x7ffff79da6ca: file bar.c, line 8.
(gdb) c
Continuing.

Breakpoint 6, 0x00007ffff79da6ca in bar (a=2, b=3, n=10) at bar.c:8
8           foo(b, n);
2: x/i $pc
=> 0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
(gdb) si
0x00007ffff79da580 in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
1: $pc = (void (*)()) 0x7ffff79da580 <foo@plt>
(gdb) x/5i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
   0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
   0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
   0x7ffff79da590 <__cxa_finalize@plt>: jmpq   *0x2003fa(%rip)        # 0x7ffff7bda990
   0x7ffff79da596 <__cxa_finalize@plt+6>:       pushq  $0x2
(gdb) si
foo (x=2, y=3) at foo.c:2
2       {
2: x/i $pc
=> 0x7ffff7bdb660 <foo>:        push   %rbp
1: $pc = (void (*)()) 0x7ffff7bdb660 <foo>

一樣跳到 foo@plt，接著會跳到 foo 於 .got.plt 所記錄的 address，現在是 foo() 的 address 了所以就會進 foo() 了！

總結上面的 lazy binding 行為，call function 時會跳到 PLT 裡執行，進到 PLT 的第一個指令是跳到 symbol 於 GOT 裡所指向的位置。第一次 call 時 GOT 記錄的 address 會是 PLT 對應的下一個指令，相當於繼續執行 PLT 的 instruction，接著一路 call 到 resolve symbol 的 function 找 symbol 以及將 address 填進 GOT。之後再 call 到相同 function 一樣會先到 PLT，但第一個指令就會從 GOT 得到正確 address、跳去該 function 執行。

觀察 main 裡的 bar 也會有類似的情況，只是 main 因為是 executable file，relocation entry 的 offset 已經是 load 進 memory 的 address，可以不用像 shared library 那樣要用 load 的 memory 開頭算 offset。

Initialization

除了一般會進入 shared library 的 .init section 進行初始化外，GCC 還提供了 shared library 的 constructor 及 destructor 擴充語法，可以讓 function 在 load shared library 時執行以做更多初始化的動作，宣告語法如下：

1
2

void __attribute__((constructor)) init();
void __attribute__((destructor)) fini();

使用這種 constructor 跟 destructor 必須使用系統預設的 standard runtime library 以及啟動檔案，不可以用 -nostartfiles 以及 -nostdlib 參數。constructor 會在 load shared library 時執行（執行 main 之前），而 destructor 則會在執行 exit() 時執行。如果是 Explicit Runtime Linking，constructor 會在 dlopen() 時執行，destructor 則在 dlclose() 時執行。

Murmur & 省略的細節

上面這樣順順列下來看起來好簡單，但其實我找 GOT 跟 PLT 到底在做什麼找～很～久～一直錯把 GOT 當 PLT，就搞不懂是在幹嘛……

PIC 跟 GOT/PLT 還有不少細節，例如 ELF 怎麼處理 library 內跟跨 library 的 function call？變數的 relocation 怎麼做的？resolve function 怎麼知道要找哪個 symbol？這些先暫時略過，不然我永遠寫不完……Orz

Related posts & Ref

• Dynamic Linking Basic
• Dynamic Linking PIC
• Shared Library Versioning
• Use Shared Library in Linux
• Explicit Runtime Linking
• 《程式設計師的自我修養》ch7
• https://www.bottomupcs.com/chapter08.xhtml
• 你所不知道的 C 語言：動態連結器篇

用 Linux 桌面最麻煩的地方之一是中文介面。我已經放棄設語系為中文，畢竟 terminal 各種 message 顯示中文實在很奇怪，但還是需要輸入法跟能看一點的字型啊啊啊啊啊……

• distribution：Debian 8
• 桌面環境：KDE

輸入法

我先試了 scim，但用起來好像有點 bug，導致操作有點卡。後來換 hime，它的各種切換快捷鍵、符號輸入等等操作跟 windows 的中文輸入法差不多，就用它啦～

裝完、修改完設定檔 ~/.xsessionrc 讓 KDE 去用它，改完 relogin。

1
2
3
4
5

$ sudo apt-get install hime hime-chewing
$ cat ~/.xsessionrc
export GTK_IM_MODULE=hime
export XMODIFIERS=@im=hime
export QT_IM_MODULE=hime

中文字型

比較喜歡沒襯線、像麥克筆寫的字體。

目前覺得 Noto 系列跟 WenQuanYi Micro Hei 系列不錯。一般字體就挑順眼的，等寬字體是用 WenQuanYi Micro Hei Mono。WenQuanYi 還有正黑體的版本，但我覺得微米黑（Micro Hei）比較好看。

1

$ sudo apt-get install fonts-noto fonts-wqy-microhei fonts-wqy-zenhei

Ref：http://wiki.ubuntu.hk/w/%E4%B8%AD%E6%96%87%E5%AD%97%E5%9E%8B

想不到標題只好亂寫。跟這篇有點相關，但講點別的。

因為某些邏輯有點複雜，修改程式很容易會改壞東西，而且改的那個人也不見得會測到所有該測的條件。

這種問題的解法之一是 unit test，用充分的測試保護那個 module，就能確保之後的修改比較不會改壞原本好的東西。但是那個 project 還沒裝 unit test framework，我也不熟，而且有點時間壓力，我認為先做出一個堪用的版本比架起 unit test framework 重要。

不過我也真的覺得要是之後改了一點 code，就可能會山崩，阿不是，是壞一堆沒想到的地方啊啊啊。光想到可能會 bug 相連到天邊、牽一髮動全身就覺得可怕。

後來我用比較彈性的做法，讓之後可以用新增 class 或一小段 code 而不修改原本 code 的方式加新的邏輯。咦？好眼熟喔！阿不就OCP？真是突然體會了為什麼那些 principle 那麼討厭「修改原有 code」，因為改原本的 code 就有風險、有可能造成意想不掉的 bug。這種事就是工程師最討厭的──我明明沒動那裡為什麼那邊會壞。

修改意味著可能有 bug，而且蠻高的機率需要修改，來不及架測試安全網，至少以遵守 OCP 的方式避免之後生 bug，也是一個方法。無法降低風險至零，但應該要能降低到能夠掌控。

設計原則也好，自動測試也好，它們只是方法不同，最終的目標是一樣的──完成一個有品質的軟體、系統。漸漸覺得，好像是看情況使用，而不見得非得如何。當然，有好設計以及自動測試的軟體是更好的。

Dynamic linking 遇到的問題

Dynamic linking 想解決的一大問題是 memory 浪費。直覺想法是如果能讓不同 process 都會使用到的 library 在 memory 只有一份就能節省空間。對不同 process 來說 library 的內容必須是相同的才能共用。library 主要是 instruction 以及 data （executable file 都是這樣辣），data 不可能在 process 間共用，因為每個 process 都需要它自己的 data，不然會互相干擾（好像有古代系統是共用的…），因此能共用的主要是 instruction。

excutable file、object file 以及 library 等 binary file 中 instruction 會以不同定址方式 access symbol，絕對定址模式會將 symbol 的 virtual address 寫進 instruction，相對定址模式則跟 instruction 及 data 之間的相對位置有關。也就是說，無論是 executable file 還是要共用的 library，instruction 都可能涉及 symbol 的 address 資訊。

不像 executable file，library 在 compile time 無法知道會被 load 到哪，因為系統裡會有多個 library，如果各自指定要 load 到哪可能會撞到，所以得等到 runtime 由系統決定，其中 symbol 位置也要到 runtime 才能決定。這使得 compile time 無法修改 instruction 內的 address 資訊，也就是 static linking 做的事。

另一方面，即使在 runtime 修改 library 的 instruction，也會造成不同 process 實際上有不同的 library instruction 而無法共用。例如 library A 使用某個外部 symbol foo，process 1 跟 process 2 都有使用 library A，但它們分別以 library B 跟 library C 來提供 symbol foo 給 library A。此時，process 1 的 foo 的 address 在 library B，process 2 則在 library C，runtime 修改 library A instruction 會有兩種版本。

Position-independent Code（PIC）

上面的問題基本上是因為 instruction 裡含有 symbol address 相關資訊，就出現 Position-independent Code（PIC）「與位置無關的程式碼」來解決。

由於 process 有各自的 data section 而且可以修改裡面的值，PIC 將 library 會被修改的部分（instruction 中的 address 相關資訊）放到 data section，讓 instruction 跟 address 無關而能共用。

library 的 address reference 可分為 library 內與跨 library，各自又再分成 reference 到資料或 instruction（function call 或 jump），處理方式主要依據 library 內或跨 library 而不同。

library 內

同一 library 內的 instruction 跟資料間相對位置是固定的，所以可以用相對位置來 access 資料、call function 或 jump。

跨 library

ELF 在 data section 放一個指向其他 library 的 symbol 的 pointer array，稱為 Global Offset Table（GOT）。instruction 可以從 GOT 找到對應的 element 進行間接 reference。先找到 GOT（不同平台有不同作法，可以用相對定址也可以有特殊 register 記錄），再從 GOT 以及 instruction 所知道的「該 symbol 在 GOT 裡的 offset」得到 element，最後得到 symbol address。

GOT 由 linker 載入 library 時填填內容，同樣使用 relocation table 的 entry 標示需要修改的位置及如何修改。relocation table 不會管 offset 指向的位置是什麼，改那個地方的內容就對了，放 GOT element 就會改 GOT。至於變數與 call function 的差別在 GOT element 存的是變數還是 function 的 address，不過實際上 ELF 有區分變數跟 function，這部份下一篇再說。

雖然 GOT 可以達到 PIC，但代價是 access symbol 的速度會變慢，因為要先找到 GOT 再間接定址。

Example

1
2
3
4
5
6
7
8

extern int sum;

int foo(int a, int b)
{
    static int* p = (int*)123;    // avoid to be placed in .bss
    p = ∑
    return a + b;
}

1
2

$ gcc -c foo.c
$ gcc -fPIC -c foo.c -o foo.o.pic

有 -fPIC 跟沒有的差別：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

$ objdump -d foo.o

foo.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   89 75 f8                mov    %esi,-0x8(%rbp)
   a:   48 c7 05 00 00 00 00    movq   $0x0,0x0(%rip)        # 15 <foo+0x15>
  11:   00 00 00 00 
  15:   8b 55 fc                mov    -0x4(%rbp),%edx
  18:   8b 45 f8                mov    -0x8(%rbp),%eax
  1b:   01 d0                   add    %edx,%eax
  1d:   5d                      pop    %rbp
  1e:   c3                      retq   


$ objdump -d foo.o.pic

foo.o.pic:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d fc                mov    %edi,-0x4(%rbp)
   7:   89 75 f8                mov    %esi,-0x8(%rbp)
   a:   48 8b 05 00 00 00 00    mov    0x0(%rip),%rax        # 11 <foo+0x11>
  11:   48 89 05 00 00 00 00    mov    %rax,0x0(%rip)        # 18 <foo+0x18>
  18:   8b 55 fc                mov    -0x4(%rbp),%edx
  1b:   8b 45 f8                mov    -0x8(%rbp),%eax
  1e:   01 d0                   add    %edx,%eax
  20:   5d                      pop    %rbp
  21:   c3                      retq   

結果是用 -fPIC compile 出來跟沒有用的 object file 不一樣（好像廢話），而且沒有 -fPIC 無法 link 成 shared object。

1
2

$ gcc -shared foo.o -o foo.so
/usr/bin/ld: foo.o: relocation R_X86_64_32S against `sum' can not be used when making a shared object; recompile with -fPIC

relocation table 如果有 R_X86_64_32S 定址無法變成 DSO。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

$ readelf -r foo.o

Relocation section '.rela.text' at offset 0x240 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000000000d  000300000002 R_X86_64_PC32     0000000000000000 .data - 8
000000000011  000a0000000b R_X86_64_32S      0000000000000000 sum + 0

Relocation section '.rela.eh_frame' at offset 0x270 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0

$ readelf -r foo.o.pic

Relocation section '.rela.text' at offset 0x278 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000000000d  000b00000009 R_X86_64_GOTPCREL 0000000000000000 sum - 4
000000000014  000300000002 R_X86_64_PC32     0000000000000000 .data - 4

Relocation section '.rela.eh_frame' at offset 0x2a8 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0

再看看 shared library 的 section 們，只列出比較相關的部份。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

$ gcc -fPIC -shared -o foo.so foo.c
$ readelf -S foo.so
There are 27 section headers, starting at offset 0x1170:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  ...
  [ 3] .dynsym           DYNSYM           00000000000001f8  000001f8
       0000000000000150  0000000000000018   A       4     2     8
  [ 4] .dynstr           STRTAB           0000000000000348  00000348
       00000000000000ab  0000000000000000   A       0     0     1
  ...
  [ 7] .rela.dyn         RELA             0000000000000430  00000430
       00000000000000d8  0000000000000018   A       3     0     8
  [ 8] .rela.plt         RELA             0000000000000508  00000508
       0000000000000030  0000000000000018  AI       3    10     8
  ...
  [10] .plt              PROGBITS         0000000000000560  00000560
       0000000000000030  0000000000000010  AX       0     0     16
  ...
  [18] .dynamic          DYNAMIC          0000000000200760  00000760
       00000000000001c0  0000000000000010  WA       4     0     8
  [19] .got              PROGBITS         0000000000200920  00000920
       0000000000000030  0000000000000008  WA       0     0     8
  [20] .got.plt          PROGBITS         0000000000200950  00000950
       0000000000000028  0000000000000008  WA       0     0     8
  ...

Lazy Binding

dynamic linking 以犧牲一點效能達到模組使用的靈活度。效能降低發生在兩個地方：程式開始執行時的 linking 工作以及 GOT 帶來的間接定址。

程式裡可能有很多 function 在執行過程中不會或很少被用到，例如錯誤處理跟少用的功能。一開始執行就 link 所有 library 裡的 function 顯然有點浪費，畢竟可能花時間 link 了卻沒用到。如果等到 function 第一次被使用時才 bind symbol（找 symbol、relocate 等等）可以加快程式啟動的速度，這個方法稱為 lazy binding。

ELF 用 Procedure Linkage Table（PLT）來實作 lazy binding。在沒有 lazy binding 前，會藉由 GOT 進行間接跳轉來 access 另一個模組的 function 。有了 lazy binding 表示一開始 load 模組時不會把 GOT 填完，所以使用 GOT 跳轉前要多一層 PLT 的處理：如果 GOT element 沒有值，會先由 dynamic linker 找到該 function 的 address，填入 GOT 後跳去該 function 執行。之後再使用到同一個 function，由於 GOT 裡已經有值，可以直接進行間接跳轉。

Related posts & Ref

• Dynamic Linking Basic
• Dynamic Linking Relocation
• Shared Library Versioning
• Use Shared Library in Linux
• Explicit Runtime Linking
• 《程式設計師的自我修養》ch7
• https://www.bottomupcs.com/chapter08.xhtml
• 你所不知道的 C 語言：動態連結器篇