編譯體系漫遊【優秀文章轉載】

時間 2017-02-10 17:57:00 Mr.Riddler's Puzzle

原文 http://blog.mrriddler.com/2017/02/10/編譯體系漫遊/

主題技術

代碼的編譯過程分為四個階段，預處理、編譯、彙編、連結。而編譯階段是整個過程中最複雜的階段，編譯階段還可以分為詞法分析、文法分析、語義分析。

在一頭紮進這四個階段之間，先聊一下文法、語義。人類之是以能在進化的曆史長河中，成為動物中的佼佼者，進化出的複雜的溝通機制—語言功不可沒。假如，我說出這句話：你個産品狗還在改需求！那麼文法是啥呢？簡單說就是構成這句話的順序，假如順序錯亂意思就不同了。那麼語義是啥呢？就是語境，根據我說這句話的情景，才能解釋出你指的是誰。文法在程式設計語言中，表現出來的就是文法結構和結合律。語義表現出來的就是上下文(context)。

預處理(Preprocess)：處理預處理符(#)，包括宏展開、頭檔案引入。

詞法分析(Lexical Analysis、Tokenizer)：寫出的代碼實際上就是字元串，此階段需要對字元串進行掃描(Scanner)，将字元串掃描出分析的最基本機關(token)，并在掃描過程中将它們分類，此階段是沒有任何語義的。也可以了解成将代碼掃描出基本表達式。
文法分析(Syntactic analysis、Parser)：生成AST抽象文法樹，檢查文法結構，此階段是上下文無關的。也可以了解成将基本表達式按文法結構組合成複合表達式。
語義分析(Semantic Analysis)：語義檢查(比如檢查浮點數乘以指針，雖然文法結構正确但是語義檢查不合格)，将程式與上下文結合，進行靜态類型分析，确定AST每個節點的類型。也可以了解将複合表達式結合環境(Environment)，并且确定基本表達式的類型。
中間碼(Intermediate Representation)：與語言無關、平台無關的中間碼。如果編譯器面向多語言，對于任意語言編譯階段後可以生成通用的中間碼，這樣編譯器就有多語言的高拓展性了。生成中間碼後再交給彙編階段，再生成與平台相關的彙編，這樣使編譯器将平台相關性盡量往後推移。中間碼除了做為“橋接“，對中間碼的優化也是整個編譯過程中的關鍵優化。
彙編(Assemble)：對中間碼生成平台具體的彙編，在這個階段添加對多個平台的支援，編譯器就可以跨平台了。最後生成機器碼。
連結(Link)：将每個機器碼編譯機關中引用的其他編譯機關中的變量、函數符号修正(fix)成真實位址。

編譯曆史

編譯的曆史基本就是計算機的進化史，是很有趣的一段故事。Long time ago… 程式員寫程式都是用紙帶，那時候還在寫0、1機器碼。紙帶上打孔就是0，不打孔就是1。然後計算機讀取紙帶就是讀取指令。但是就像網際網路本質就是提高效率一樣，這樣寫程式的效率怎能接受？并且，寫程式如果犯了錯誤怎麼辦？重新從頭到尾再用新紙帶搞一遍？程式員們機智的開始想辦法了，先是這樣搞：

編譯體系漫遊【優秀文章轉載】

将指帶有誤的地方，用黑黑的小貼紙填上去，這樣将0改成1了。這也是Patch名字的由來。但是這樣寫指令效率還是太低，程式員們再機智的想辦法。後來将指令進行符号化(Symbol)，抽象出指令集，這時就出現了彙編，程式員的效率上了一個檔次。但是新的問題又出現了。在寫過程調用的時候，要寫jmp 具體的函數位址。如果後來要在被調用的函數前面添加指令，那麼函數位址也要跟着改。這樣牽一發動全身的感覺可不好，為了讓影響(impact)縮減到最小，不如将函數位址也符号化。凡是寫過程調用先寫成jmp func，等到程式生成機器碼的時候，再将func換成真正的函數位址，這一步也就是将程式員手動修正交由彙編器修正。

随着生産力的提升，程式的規模越來越大，新的問題出現了，程式膨脹到難以維護和閱讀了。程式員們就将程式子產品化、階層化。這樣也使編譯的機關更小粒度化。編譯的時候，不同編譯機關之間的細節是互相隔離的。比如，對于C語言系，一個.h和一個.m就構成了一個編譯機關。.m彙編時，是不知道其他.m的全局變量、函數位址的，而調用的時候就隻能用符号進行調用，等到最後所有.m都生成機器碼後再進行統一的修正。而負責這一步的就是連結器(Linker)，這一步也叫重定位(Relocation)。

目标檔案

經過彙編這一階段後，就會生成目标檔案。目标檔案和可執行檔案已經非常相近了，隻是有些符号還未修正，結構上會進行調整。Windows平台下為PE(Portable Executable)，Linux平台下為ELF(Executable Linkable Format)，Mac平台下為Mach-O。雖然不同平台都有自己的格式，但是它們實際上都大同小異。下面大體聊一下檔案的實際字段，這些知識會為後面我們搞一些符号重綁定做鋪墊。

section

首先，檔案分段(section)。不同的Section放置不同的資訊，檔案還有一個section header table放置控制資訊。實際上，就類似圖檔格式和mutipart的HTTP封包。以下是一個ELF目标檔案的常見section：

—— —— —— —— —— —— ——
|header              |  -----> 檔案頭 
|—— —— —— —— —— —— ——|
|.text               |  -----> 代碼段
|—— —— —— —— —— —— ——|
|.data               |  -----> 已初始化全局變量、靜态變量
|—— —— —— —— —— —— ——|
|.bss                |  -----> 未初始化全局變量、靜态變量
|—— —— —— —— —— —— ——|
|other sections...   |  
|—— —— —— —— —— —— ——|
|section header table|  -----> section控制資訊表
|—— —— —— —— —— —— ——|
|.strtab             |  -----> 字元串表
|—— —— —— —— —— —— ——|
|.symtab             |  -----> 符号表
|—— —— —— —— —— —— ——|
|.....               |
—— —— —— —— —— —— —— —

.text放置代碼，.data放置已初始化的全局變量和靜态變量，.bss放置未初始化的全局變量和靜态變量。為什麼代碼和全局變量、靜态變量要分開放？實際上，這就是個等同性問題。代碼段就是可讀的資料，而全局變量、靜态變量是可讀可寫的資料。如果有多個程序進行同一份代碼，這些代碼都是等同的，不需要各自複制一份。而全局變量、靜态變量是不等同的，需要各自複制一份。而分什麼又要分已初始化、未初始化呢？目标檔案未初始化的全局、靜态變量隻需要放置一個占位符，代表其在.bss。而.bss在連結階段，變量不占空間，在裝載時由作業系統再配置設定空間。可以看到，既然是檔案格式，不管怎麼設計，主要的目的就是占更少的空間。

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

.strtab放置section名、變量名，包括符号名的字元串。由于在整個結構中，字元串的長度是不定的，一般将這些字元串統一放置在一個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就是大名鼎鼎的符号表。每個目标檔案都有自己的符号表，符号表記錄符号的映射，符号可以這樣分：檔案外符号和檔案内符号，檔案外符号就是使用在其他檔案定義的符号，檔案内符号除了在檔案内定義給其他檔案使用的符号，還包括每個section符号，在檔案内定義光是檔案内使用的符号。光檔案内使用的符号，對連結沒有幫助，主要為了崩潰後分析而存在。符号表也是一個由struct構成的數組。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表示是局部符号、全局符号還是弱符号。符号也可以分為強符号(Strong Symbol)、弱符号(Weak Symbol)，顧名思義，強符号有唯一性，弱符号沒有唯一性，一個強符号可以和多個弱符号共存，多個重複的強符号不可以共存，連結器會報出duplicate dymbol，可以用attribute((weak))指明弱符号。相對的，符号也有強引用(Strong Reference)、弱引用(Weak Reference)，在連結進行符号修正的時候，強引用必須修正，而弱引用可以不修正，可以用attribute((weakref))指明符号弱引用。

st_shndx字段指明了符号是檔案外符号，還是檔案内符号。如果是檔案外符号就為SHN_UNDEF。如果是檔案内符号包括給其他檔案使用的、光自己使用的、section符号，就為所在section的索引号，而st_value表示所在section的offset。等到連結過後，不管是檔案外符号還是檔案内符号，st_value指明實際位址。

符号修飾(Symbol-Decoration)與函數簽名(Function-Signature)

機智的同學已經發現了，如果光按上面聊的方式進行符号連結是有問題的，假如目标檔案有個func符号又引用了其他檔案同名的func符号，那符号不就出現沖突了？這裡就需要引入函數簽名，函數簽名是一個函數的名字、參數類型、所在類名組成的字元串，不同語言、不同編譯器對同一個函數生成的函數簽名是不一樣的，比如OC中函數簽名還要加上傳回變量類型，C++中還要加上NameSpace。在連結的時候，過程調用符号不光是函數名，是對函數簽名處理後的結果，全局變量符号也是經過類似用函數簽名處理後的結果。這一處理過程就是符号修飾。

fishhook

fishhook是facebook開源的重綁定Mach-O符号的庫，最常用來hook C語言函數，而且實際上隻能重新綁定C符号，因為符号修飾這一步隻去掉了””，相當于隻針對C語言做了符号修飾。在了解了目标檔案後，重綁定就不是那麼困難了。最基本的思路就是先拿到header，然後通過header拿到section header table，再找到.hash，.hash是一個用于加快通路.symtab的哈希結構，再索引到.symtab，詳見這裡，通過name去.strtab比對符号名，如果比對就置換value。

fishhook大體實作原理就是這樣，隻不過對Mach-O平台特性改進一下方案就行。在Mach-O中類似于section header table的段叫做load commands。并且Mach-O中使用二級命名空間，先分segment，就相當于上文中的section，然後再在同一segment中區分section。

先拿到header，通過header中的ncmds(segment的個數)和cmdsize(segment的大小)字段就可以找到所有的segment。然後找到.strtab、.symtab、indirect symbol table。這個indirect symbol table是一個uint32_t的數組。它就是nl_symbol_ptr(non-lazy)和la_symbol_ptr(lazy )對應的.symtab struct數組的索引。nl_symbol_ptr和la_symbol_ptr section section中的reserved1字段指明對應的indirect symbol table起始offset。隻要從這兩個section對應的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
|—— —— —— —— —— —— ——|
|.....               |
—— —— —— —— —— —— —— —

更加詳細的格式，推薦這篇文章。

連結

上面聊了這麼多，那靜态連結到底是如何将多個目标檔案連結成一個可執行檔案的呢？

靜态連結分為兩階段(Two-pass Linking)，第一階段先掃描所有目标檔案，調整結構。将所有目标檔案相同section合并，包括.symtab合并成全局.symtab，然後為每個section配置設定虛拟位址，再将全局.symtab中的符号進行置換成虛拟位址。

這裡如何将全局.symtab中的符号置換成虛拟位址呢？實際上，在配置設定section虛拟位址後，符号的虛拟位址按所在section虛拟位址加offset就可以計算出了。

第二階段将所有符号進行修正。通過重定位表找到所有section中需要被修正的符号位置，然後從全局.symtab查詢出虛拟位址置換。

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

靜态連結庫

靜态連結庫就是一組目标檔案，經過壓縮、索引而成的一個檔案形式。當我們平時在使用靜态連結庫的時候，實際上連結器會根據所需的符号，在庫中搜尋到相應的目标檔案，并将其連結入最終可執行檔案。

動态連結

随着靜态連結慢慢發展起來，靜态連結也暴露出了問題。靜态連結将連結與被連結的目标檔案結合的太緊密了，導緻如果多個目标檔案要連結同一個目标檔案，那這個被連結的目标檔案相當于要被複制多份，每個可執行檔案都要包含這個被連結的目标檔案的内容，這樣會占太多備援空間。那怎麼辦？将連結與被連結的目标檔案先隔離開，将連結的時機往後推移，等到裝載的時候再進行連結。這樣，讓被連結的目标檔案隻占一份空間就好。

既然動态連結隔離開了連結、被連結目标檔案，連結目标檔案需動态連結的符号，就需要先做個動态連結占位符。這也就是說，在目标檔案連結成可執行檔案時，即使是用作動态連結的目标檔案也要作為動态連結庫輸入到連結階段，以供目标檔案識别哪些符号是動态符号。

動态連結重定位

上面已經聊完了在連結階段對靜态連結進行重定位，根據符号所在section的虛拟位址和所在section的offset。而動态連結可以這樣重定位嗎？不行，這時動态連結庫的位址還沒有确定，必須等到裝載以後作業系統配置設定。那可以等到裝載以後，确定位址後再直接進行重定位嗎？不行，假如動态連結庫被多個程序引用，裝載時動态連結庫進行重定位，動态連結庫映射到每個程序中的虛拟位址都不一樣，動态連結庫隻能對一個程序重定位，那麼動态連結庫就不是共享的了。那怎麼搞？

通過.got(global offset table)，.got就是一個指針數組，.got存儲引用符号的實際位址。而代碼段引用符号直接更改為引用.got項的位移，這在連結階段以後就不會再改變了。然後将.got配置設定在.data section，裝載時每個程序複制一份并修正。實際上，動态連結重定位指的就是在裝載的時候，根據全局符号表修正.got表項。動态連結庫使用全局變量、靜态變量、引用檔案外過程調用都要經過.got。.got就像indirection table一樣，解決多程序共享動态連結庫。

這樣，動态連結庫雖然在不同程序中有不同的映射虛拟空間，但實體空間上共享。.got在不同程序中，虛拟空間和實體空間都不共享。如下圖所示：

virtual address             ->             physical address
 —— —— —— —— —— —— ——
|processA            |  
|—— —— —— —— —— —— ——|
|.....               |  
|—— —— —— —— —— —— ——|
|dynamic libiraries  |----------                
|—— —— —— —— —— —— ——|         |
|.....               |         |           |.....               |
|—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
|.got                |---------|---------->|.got                |
|—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
|.....               |         |           |.....               |  
|—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
                               ----------->|dynamic libiraries  |                 
 —— —— —— —— —— —— ——          |           |—— —— —— —— —— —— ——|
|processB            |         |           |.....               |
|—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
|.....               |         |    ------>|.got                |
|—— —— —— —— —— —— ——|         |    |      |—— —— —— —— —— —— ——|
|dynamic libiraries  |----------    |      |.....               |
|—— —— —— —— —— —— ——|              |
|.....               |              |
|—— —— —— —— —— —— ——|              |
|.got                |---------------  
|—— —— —— —— —— —— ——|       
|.....               |  
|—— —— —— —— —— —— ——|

動态連結庫檔案外符号重定位用.got就搞定了，那動态連結庫檔案内符号呢？靜态連結同樣是在連結階段重定位就搞定了。動态連結将絕對尋址指令更換成相對尋址指令，隻要指令的offset不變，相對尋址指令就可根據目前位址和offset得到正确的位址，這樣檔案内符号根本不需要重定位了。基于以上兩點的處理，代碼段在連結後就不需要更改了，這樣的代碼段也叫做位址無關碼(PIC)，也就是說代碼段和裝載後的位址無關。

延遲綁定(PLT)

由于要跳過.got引用動态連結庫的符号，動态連結庫比靜态連結庫慢5%左右，但相比于節省的大量空間還是很劃算的。除此之外，動态連結還會有其他的問題，裝載時需要進行重定位，會導緻性能下降。不如，直接延遲綁定，等到過程調用符号運作時被用到再進行重定位。

整個過程強烈推薦這篇文章，要想了解動态連結重定位，沒有比追彙編更好的方法了。動态連結和延遲綁定整個過程都是由動态連結器幫我們完成的。當引用符号(callq)時，先jmpq去plt結構，使用了PLT，引用符号就要先jmpq去plt結構。如果沒找到相應的位址，然後再jmpq去.got.plt或.got中。再把符号相應.rela.plt表中的索引和.got.plt相應的表項，pushq入棧，rela.plt中有符号的類型和名字。再jmp到動态連結庫中(_dl_fixup)，去全局符号表中找到符号相應的位址。再将位址reloc到.got.plt或.got相應表項。然後就完成了延遲綁定，下次引用同樣的符号就可以jmpq去plt結構找到位址。

編譯體系漫遊【優秀文章轉載】

編譯曆史

目标檔案

section

符号修飾(Symbol-Decoration)與函數簽名(Function-Signature)

fishhook

連結

靜态連結庫

動态連結

動态連結重定位

延遲綁定(PLT)

繼續閱讀

ios導航欄圖檔自适應, 根據圖檔大小适配

16、32、64位編譯器基本資料位元組數

iOS進階_NSURLRequest(二.參數整理&JSON解析&Plist檔案反序列化)

避免在類别(category)中定義屬性(@property)

深入了解Objective-C：Category(上)

如何快速的開發一個完整的iOS直播app】(點贊功能)

NSProxy與消息轉發機制

iOS社會化分享-iOS系統分享，shareSDK分享，Umeng分享

iOS進階（二）Objective-C底層原理

IOS開發檔案路徑

使用ReactiveCocoa初探MVVM

iOS Crash棧的捕獲和分析

【如何快速的開發一個完整的iOS直播app】(采集篇)

如何快速的開發一個完整的iOS直播app】(建立房間)