世界建筑風(fēng)格漫游

來源：MRRiddler ，

blog.mrriddler.com/2017/02/10/計算機(jī)體系-編譯體系漫游/

要想讓代碼乖乖運(yùn)行，自然代碼要先經(jīng)過編譯，這篇文章就來聊聊編譯體系。

代碼的編譯過程分為四個階段，預(yù)處理、編譯、匯編、鏈接。而編譯階段是整個過程中最復(fù)雜的階段，編譯階段還可以分為詞法分析、語法分析、語義分析。

在一頭扎進(jìn)這四個階段之間，先聊一下語法、語義。人類之所以能在進(jìn)化的歷史長河中，成為動物中的佼佼者，進(jìn)化出的復(fù)雜的溝通機(jī)制—語言功不可沒。假如，我說出這句話：你個產(chǎn)品狗還在改需求！那么語法是啥呢？簡單說就是構(gòu)成這句話的順序，假如順序錯亂意思就不同了。那么語義是啥呢？就是語境，根據(jù)我說這句話的情景，才能解釋出你指的是誰。語法在編程語言中，表現(xiàn)出來的就是語法結(jié)構(gòu)和結(jié)合律。語義表現(xiàn)出來的就是上下文(context)。

預(yù)處理(Preprocess)：處理預(yù)處理符(#)，包括宏展開、頭文件引入。 詞法分析(Lexical Analysis、Tokenizer)：寫出的代碼實(shí)際上就是字符串，此階段需要對字符串進(jìn)行掃描(Scanner)，將字符串掃描出分析的最基本單位(token)，并在掃描過程中將它們分類，此階段是沒有任何語義的。也可以理解成將代碼掃描出基本表達(dá)式。 語法分析(Syntactic analysis、Parser)：生成AST抽象語法樹，檢查語法結(jié)構(gòu)，此階段是上下文無關(guān)的。也可以理解成將基本表達(dá)式按語法結(jié)構(gòu)組合成復(fù)合表達(dá)式。 語義分析(Semantic Analysis)：語義檢查(比如檢查浮點(diǎn)數(shù)乘以指針，雖然語法結(jié)構(gòu)正確但是語義檢查不合格)，將程序與上下文結(jié)合，進(jìn)行靜態(tài)類型分析，確定AST每個節(jié)點(diǎn)的類型。也可以理解將復(fù)合表達(dá)式結(jié)合環(huán)境(Environment)，并且確定基本表達(dá)式、復(fù)合表達(dá)式的類型。 中間碼(Intermediate Representation)：與語言無關(guān)、平臺無關(guān)的中間碼。如果編譯器面向多語言，對于任意語言編譯階段后可以生成通用的中間碼，這樣編譯器就有多語言的高拓展性了。生成中間碼后再交給匯編階段，再生成與平臺相關(guān)的匯編，這樣使編譯器將平臺相關(guān)性盡量往后推移。中間碼除了做為“橋接“，對中間碼的優(yōu)化也是整個編譯過程中的關(guān)鍵優(yōu)化。 匯編(Assemble)：對中間碼生成平臺具體的匯編，在這個階段添加對多個平臺的支持，編譯器就可以跨平臺了。最后生成機(jī)器碼。 鏈接(Link)：將每個機(jī)器碼編譯單位中引用的其他編譯單位中的變量、函數(shù)符號修正(fix)成真實(shí)地址。

編譯歷史

編譯的歷史基本就是計算機(jī)的進(jìn)化史，是很有趣的一段故事。Long time ago… 程序員寫程序都是用紙帶，那時候還在寫0、1機(jī)器碼。紙帶上打孔就是0，不打孔就是1。然后計算機(jī)讀取紙帶就是讀取指令。但是就像互聯(lián)網(wǎng)本質(zhì)就是提高效率一樣，這樣寫程序的效率怎能接受？并且，寫程序如果犯了錯誤怎么辦？重新從頭到尾再用新紙帶搞一遍？程序員們機(jī)智的開始想辦法了，先是這樣搞：

將指帶有誤的地方，用黑黑的小貼紙?zhí)钌先?，這樣將0改成1了。這也是Patch名字的由來。但是這樣寫指令效率還是太低，程序員們再機(jī)智的想辦法。后來將指令進(jìn)行符號化(Symbol)，抽象出指令集，這時就出現(xiàn)了匯編，程序員的效率上了一個檔次。但是新的問題又出現(xiàn)了。在寫過程調(diào)用的時候，要寫jmp 具體的函數(shù)地址。如果后來要在被調(diào)用的函數(shù)前面添加指令，那么函數(shù)地址也要跟著改。這樣牽一發(fā)動全身的感覺可不好，為了讓影響(impact)縮減到最小，不如將函數(shù)地址也符號化。凡是寫過程調(diào)用先寫成jmp func，等到程序生成機(jī)器碼的時候，再將func換成真正的函數(shù)地址，這一步也就是將程序員手動修正交由匯編器修正。

隨著生產(chǎn)力的提升，程序的規(guī)模越來越大，新的問題出現(xiàn)了，程序膨脹到難以維護(hù)和閱讀了。程序員們就將程序模塊化、層次化。這樣也使編譯的單位更小粒度化。編譯的時候，不同編譯單位之間的細(xì)節(jié)是互相隔離的。比如，對于C語言系，一個.h和一個.m就構(gòu)成了一個編譯單位。.m匯編時，是不知道其他.m的全局變量、函數(shù)地址的，而調(diào)用的時候就只能用符號進(jìn)行調(diào)用，等到最后所有.m都生成機(jī)器碼后再進(jìn)行統(tǒng)一的修正。而負(fù)責(zé)這一步的就是鏈接器(Linker)，這一步也叫重定位(Relocation)。

目標(biāo)文件

經(jīng)過匯編這一階段后，就會生成目標(biāo)文件。目標(biāo)文件和可執(zhí)行文件已經(jīng)非常相近了，只是有些符號還未修正，結(jié)構(gòu)上會進(jìn)行調(diào)整。Windows平臺下為PE(Portable Executable)，Linux平臺下為ELF(Executable Linkable Format)，Mac平臺下為Mach-O。雖然不同平臺都有自己的格式，但是它們實(shí)際上都大同小異。下面大體聊一下文件的實(shí)際字段，這些知識會為后面我們搞一些符號重綁定做鋪墊。

section

首先，文件分段(section)。不同的Section放置不同的信息，文件還有一個section header table放置控制信息。實(shí)際上，就類似圖片格式和mutipart的HTTP報文。以下是一個ELF目標(biāo)文件的常見section：

—— —— —— —— —— —— ——

|header | -----> 文件頭

|—— —— —— —— —— —— ——|

|.text | -----> 代碼段

|—— —— —— —— —— —— ——|

|.data | -----> 已初始化全局變量、靜態(tài)變量

|—— —— —— —— —— —— ——|

|.bss | -----> 未初始化全局變量、靜態(tài)變量

|—— —— —— —— —— —— ——|

|other sections... |

|—— —— —— —— —— —— ——|

|section header table| -----> section控制信息表

|—— —— —— —— —— —— ——|

|.strtab | -----> 字符串表

|—— —— —— —— —— —— ——|

|.symtab | -----> 符號表

|—— —— —— —— —— —— ——|

|..... |

—— —— —— —— —— —— —— —

.text放置代碼，.data放置已初始化的全局變量和靜態(tài)變量，.bss放置未初始化的全局變量和靜態(tài)變量。為什么代碼和全局變量、靜態(tài)變量要分開放？實(shí)際上，這就是個等同性問題。代碼段就是可讀的數(shù)據(jù)，而全局變量、靜態(tài)變量是可讀可寫的數(shù)據(jù)。如果有多個進(jìn)程進(jìn)行同一份代碼，這些代碼都是等同的，不需要各自復(fù)制一份。而全局變量、靜態(tài)變量是不等同的，需要各自復(fù)制一份。而分什么又要分已初始化、未初始化呢？目標(biāo)文件未初始化的全局、靜態(tài)變量只需要放置一個占位符，代表其在.bss。而.bss在鏈接階段，變量不占空間，在裝載時由操作系統(tǒng)再分配空間?？梢钥吹剑热皇俏募袷?，不管怎么設(shè)計，主要的目的就是占更少的空間。

header有很多文件控制信息，就不一一表述了，其中最重要的就是記錄了section header table的起始地址。而section header table記錄了所有section的名字、類型、長度、在文件中的偏移量(offset)等。如果想要尋址到任意section都要通過這個header table。section header table實(shí)際上是由struct構(gòu)成的數(shù)組。

.strtab放置section名、變量名，包括符號名的字符串。由于在整個結(jié)構(gòu)中，字符串的長度是不定的，一般將這些字符串統(tǒng)一放置在一個table中，然后存儲table中的offset，最后尋址到字符串。比如，在下表中，我想找到girlfriend一詞，我只要拿到.strtab的base地址，加上girlfriend的offset 9就可以找到這個字符串。

0 1 2 3 4 5 6 7 8

i 0 w a n t 0 a 0

g i r l f r i e n

d

.symtab就是大名鼎鼎的符號表。每個目標(biāo)文件都有自己的符號表，符號表記錄符號的映射，符號可以這樣分：文件外符號和文件內(nèi)符號，文件外符號就是使用在其他文件定義的符號，文件內(nèi)符號除了在文件內(nèi)定義給其他文件使用的符號，還包括每個section符號，在文件內(nèi)定義光是文件內(nèi)使用的符號。光文件內(nèi)使用的符號，對鏈接沒有幫助，主要為了崩潰后分析而存在。符號表也是一個由struct構(gòu)成的數(shù)組。ELF的32位符號sturct：

typedef struct {

int32_t st_name;

uint32_t st_value;

int32_t st_size;

unsigned char st_info;

unsigned char st_other;

uint16_t st_shndx;

} ELF32_Sym;

st_name字段就是符號的名字，表示為在.strtab中的字符串offset。st_info表示是局部符號、全局符號還是弱符號。符號也可以分為強(qiáng)符號(Strong Symbol)、弱符號(Weak Symbol)，顧名思義，強(qiáng)符號有唯一性，弱符號沒有唯一性，一個強(qiáng)符號可以和多個弱符號共存，多個重復(fù)的強(qiáng)符號不可以共存，鏈接器會報出duplicate dymbol，可以用attribute((weak))指明弱符號。相對的，符號也有強(qiáng)引用(Strong Reference)、弱引用(Weak Reference)，在鏈接進(jìn)行符號修正的時候，強(qiáng)引用必須修正，而弱引用可以不修正，可以用attribute((weakref))指明符號弱引用。

st_shndx字段指明了符號是文件外符號，還是文件內(nèi)符號。如果是文件外符號就為SHN_UNDEF。如果是文件內(nèi)符號包括給其他文件使用的、光自己使用的、section符號，就為所在section的索引號，而st_value表示所在section的offset。等到鏈接過后，不管是文件外符號還是文件內(nèi)符號，st_value指明實(shí)際地址。

符號修飾(Symbol-Decoration)與函數(shù)簽名(Function-Signature)

機(jī)智的同學(xué)已經(jīng)發(fā)現(xiàn)了，如果光按上面聊的方式進(jìn)行符號鏈接是有問題的，假如目標(biāo)文件有個func符號又引用了其他文件同名的func符號，那符號不就出現(xiàn)沖突了？這里就需要引入函數(shù)簽名，函數(shù)簽名是一個函數(shù)的名字、參數(shù)類型、所在類名組成的字符串，不同語言、不同編譯器對同一個函數(shù)生成的函數(shù)簽名是不一樣的，比如OC中函數(shù)簽名還要加上返回變量類型，C++中還要加上NameSpace。在鏈接的時候，過程調(diào)用符號不光是函數(shù)名，是對函數(shù)簽名處理后的結(jié)果，全局變量符號也是經(jīng)過類似用函數(shù)簽名處理后的結(jié)果。這一處理過程就是符號修飾。

fishhook

fishhook是facebook開源的重綁定Mach-O符號的庫，最常用來hook C語言函數(shù)，而且實(shí)際上只能重新綁定C符號，因?yàn)榉栃揎椷@一步只去掉了”_”，相當(dāng)于只針對C語言做了符號修飾。在了解了目標(biāo)文件后，重綁定就不是那么困難了。最基本的思路就是先拿到header，然后通過header拿到section header table，再找到.hash，.hash是一個用于加快訪問.symtab的哈希結(jié)構(gòu)，再索引到.symtab，詳見這里，通過name去.strtab比對符號名，如果匹配就置換value。

https://docs.oracle.com/cd/E2382401/html/819-0690/chapter6-48031.html

fishhook大體實(shí)現(xiàn)原理就是這樣，只不過對Mach-O平臺特性改進(jìn)一下方案就行。在Mach-O中類似于section header table的段叫做load commands。并且Mach-O中使用二級命名空間，先分segment，就相當(dāng)于上文中的section，然后再在同一segment中區(qū)分section。

先拿到header，通過header中的ncmds(segment的個數(shù))和cmdsize(segment的大小)字段就可以找到所有的segment。然后找到.strtab、.symtab、indirect symbol table。這個indirect symbol table是一個uint32_t的數(shù)組。它就是nl_symbol_ptr(non-lazy)和la_symbol_ptr(lazy )對應(yīng)的.symtab struct數(shù)組的索引。nl_symbol_ptr和la_symbol_ptr section section中的reserved1字段指明對應(yīng)的indirect symbol table起始o(jì)ffset。只要從這兩個section對應(yīng)的indirect symbol table起始表項再跳到.symtab去匹配、置換就可以了。

下面是32位下.symtab的struct，可以看到和上段文章講的幾乎一致：

struct nlist {

union {

char *n_name; /* for use when in-core */

uint32_t n_strx; /* index into the string table */

} n_un;

uint8_t n_type; /* type flag, see below */

uint8_t n_sect; /* section number or NO_SECT */

int16_t n_desc; /* see <mach-o/stab.h> */

uint32_t n_value; /* value of this symbol (or stab offset) */

};

上文提到的Mach-O格式如下：

—— —— —— —— —— —— ——

|header |

|—— —— —— —— —— —— ——|

|load commands |

|—— —— —— —— —— —— ——|

|__Text |

|—— —— —— —— —— —— ——| —— __nl_symbol_ptr

|__Data | -----> |

|—— —— —— —— —— —— ——| —— __la_symbol_ptr

|other sections... |

|—— —— —— —— —— —— ——|

|.strtab |

|—— —— —— —— —— —— ——|

|.dynsym | -----> indirect symbol table

|—— —— —— —— —— —— ——|

|..... |

—— —— —— —— —— —— —— —

更加詳細(xì)的格式，推薦這篇文章。

http://turingh.github.io/2016/03/07/mach-o文件格式分析/

鏈接

上面聊了這么多 ，那靜態(tài)鏈接到底是如何將多個目標(biāo)文件鏈接成一個可執(zhí)行文件的呢？

靜態(tài)鏈接分為兩階段(Two-pass Linking)，第一階段先掃描所有目標(biāo)文件，調(diào)整結(jié)構(gòu)。將所有目標(biāo)文件相同section合并，包括.symtab合并成全局.symtab，然后為每個section分配虛擬地址，再將全局.symtab中的符號進(jìn)行置換成虛擬地址。

這里如何將全局.symtab中的符號置換成虛擬地址呢？實(shí)際上，在分配section虛擬地址后，符號的虛擬地址按所在section虛擬地址加offset就可以計算出了。

第二階段將所有符號進(jìn)行修正。通過重定位表找到所有section中需要被修正的符號位置，然后從全局.symtab查詢出虛擬地址置換。

每個section都會對應(yīng)一個重定位段，這些重定位段組成一個重定位表。每個重定位表項叫做重定位入口(Relocation Entry)，它記錄了所需重定向符號所在段的offset。

靜態(tài)鏈接庫

靜態(tài)鏈接庫就是一組目標(biāo)文件，經(jīng)過壓縮、索引而成的一個文件形式。當(dāng)我們平時在使用靜態(tài)鏈接庫的時候，實(shí)際上鏈接器會根據(jù)所需的符號，在庫中搜索到相應(yīng)的目標(biāo)文件，并將其鏈接入最終可執(zhí)行文件。

動態(tài)鏈接

隨著靜態(tài)鏈接慢慢發(fā)展起來，靜態(tài)鏈接也暴露出了問題。靜態(tài)鏈接將鏈接與被鏈接的目標(biāo)文件結(jié)合的太緊密了，導(dǎo)致如果多個目標(biāo)文件要鏈接同一個目標(biāo)文件，那這個被鏈接的目標(biāo)文件相當(dāng)于要被復(fù)制多份，每個可執(zhí)行文件都要包含這個被鏈接的目標(biāo)文件的內(nèi)容，這樣會占太多冗余空間。那怎么辦？將鏈接與被鏈接的目標(biāo)文件先隔離開，將鏈接的時機(jī)往后推移，等到裝載的時候再進(jìn)行鏈接。這樣，讓被鏈接的目標(biāo)文件只占一份空間就好。

既然動態(tài)鏈接隔離開了鏈接、被鏈接目標(biāo)文件，鏈接目標(biāo)文件需動態(tài)鏈接的符號，就需要先做個動態(tài)鏈接占位符。這也就是說，在目標(biāo)文件鏈接成可執(zhí)行文件時，即使是用作動態(tài)鏈接的目標(biāo)文件也要作為動態(tài)鏈接庫輸入到鏈接階段，以供目標(biāo)文件識別哪些符號是動態(tài)符號。

動態(tài)鏈接重定位

上面已經(jīng)聊完了在鏈接階段對靜態(tài)鏈接進(jìn)行重定位，根據(jù)符號所在section的虛擬地址和所在section的offset。而動態(tài)鏈接可以這樣重定位嗎？不行，這時動態(tài)鏈接庫的地址還沒有確定，必須等到裝載以后操作系統(tǒng)分配。那可以等到裝載以后，確定地址后再直接進(jìn)行重定位嗎？不行，假如動態(tài)鏈接庫被多個進(jìn)程引用，裝載時動態(tài)鏈接庫進(jìn)行重定位，動態(tài)鏈接庫映射到每個進(jìn)程中的虛擬地址都不一樣，動態(tài)鏈接庫只能對一個進(jìn)程重定位，那么動態(tài)鏈接庫就不是共享的了。那怎么搞？

通過.got(global offset table)，.got就是一個指針數(shù)組，.got存儲引用符號的實(shí)際地址。而代碼段引用符號直接更改為引用.got項的位移，這在鏈接階段以后就不會再改變了。然后將.got分配在.data section，裝載時每個進(jìn)程復(fù)制一份并修正。實(shí)際上，動態(tài)鏈接重定位指的就是在裝載的時候，根據(jù)全局符號表修正.got表項。動態(tài)鏈接庫使用全局變量、靜態(tài)變量、引用文件外過程調(diào)用都要經(jīng)過.got。.got就像indirection table一樣，解決多進(jìn)程共享動態(tài)鏈接庫。

這樣，動態(tài)鏈接庫雖然在不同進(jìn)程中有不同的映射虛擬空間，但物理空間上共享。.got在不同進(jìn)程中，虛擬空間和物理空間都不共享。如下圖所示：

virtual address -> physical address

—— —— —— —— —— —— ——

|processA |

|—— —— —— —— —— —— ——|

|..... |

|—— —— —— —— —— —— ——|

|dynamic libiraries |----------

|—— —— —— —— —— —— ——| |

|..... | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|.got |---------|---------->|.got |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|..... | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

----------->|dynamic libiraries |

—— —— —— —— —— —— —— | |—— —— —— —— —— —— ——|

|processB | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|..... | | ------>|.got |

|—— —— —— —— —— —— ——| | | |—— —— —— —— —— —— ——|

|dynamic libiraries |---------- | |..... |

|—— —— —— —— —— —— ——| |

|..... | |

|—— —— —— —— —— —— ——| |

|.got |---------------

|—— —— —— —— —— —— ——|

|..... |

|—— —— —— —— —— —— ——|

動態(tài)鏈接庫文件外符號重定位用.got就搞定了，那動態(tài)鏈接庫文件內(nèi)符號呢？靜態(tài)鏈接同樣是在鏈接階段重定位就搞定了。動態(tài)鏈接將絕對尋址指令更換成相對尋址指令，只要指令的offset不變，相對尋址指令就可根據(jù)當(dāng)前地址和offset得到正確的地址，這樣文件內(nèi)符號根本不需要重定位了?；谝陨蟽牲c(diǎn)的處理，代碼段在鏈接后就不需要更改了，這樣的代碼段也叫做地址無關(guān)碼(PIC)，也就是說代碼段和裝載后的地址無關(guān)。

延遲綁定(PLT)

由于要跳過.got引用動態(tài)鏈接庫的符號，動態(tài)鏈接庫比靜態(tài)鏈接庫慢5%左右，但相比于節(jié)省的大量空間還是很劃算的。除此之外，動態(tài)鏈接還會有其他的問題，裝載時需要進(jìn)行重定位，會導(dǎo)致性能下降。不如，直接延遲綁定，等到過程調(diào)用符號運(yùn)行時被用到再進(jìn)行重定位。

整個過程強(qiáng)烈推薦這篇文章，要想理解動態(tài)鏈接重定位，沒有比追匯編更好的方法了。動態(tài)鏈接和延遲綁定整個過程都是由動態(tài)鏈接器幫我們完成的。當(dāng)引用符號(callq)時，先jmpq去plt結(jié)構(gòu)，使用了PLT，引用符號就要先jmpq去plt結(jié)構(gòu)。如果沒找到相應(yīng)的地址，然后再jmpq去.got.plt或.got中。再把符號相應(yīng).rela.plt表中的索引和.got.plt相應(yīng)的表項，pushq入棧，rela.plt中有符號的類型和名字。再jmp到動態(tài)鏈接庫中(_dl_fixup)，去全局符號表中找到符號相應(yīng)的地址。再將地址reloc到.got.plt或.got相應(yīng)表項。然后就完成了延遲綁定，下次引用同樣的符號就可以jmpq去plt結(jié)構(gòu)找到地址。

http://sysfork.com/post/linux-dynamic-lib-lazy-load/

引用

程序員的自我修養(yǎng)—鏈接、裝載與庫

關(guān)注「ImportNew」，看技術(shù)干貨