計算機體系 – 編譯體系漫遊

（點選上方公眾號，可快速關註）

來源：MRRiddler ，

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 essay-header table放置控制資訊。實際上，就類似圖片格式和mutipart的HTTP報文。以下是一個ELF標的檔案的常見section：

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

|essay-header              |  —–> 檔案頭 

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

|.text               |  —–> 程式碼段

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

|.data               |  —–> 已初始化全域性變數、靜態變數

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

|.bss                |  —–> 未初始化全域性變數、靜態變數

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

|other sections…   |  

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

|section essay-header table|  —–> section控制資訊表

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

|.strtab             |  —–> 字串表

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

|.symtab             |  —–> 符號表

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

|…..               |

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

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

essay-header有很多檔案控制資訊，就不一一表述了，其中最重要的就是記錄了section essay-header table的起始地址。而section essay-header table記錄了所有section的名字、型別、長度、在檔案中的偏移量(offset)等。如果想要定址到任意section都要透過這個essay-header table。section essay-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語言做了符號修飾。在瞭解了標的檔案後，重系結就不是那麼困難了。最基本的思路就是先拿到essay-header，然後透過essay-header拿到section essay-header table，再找到.hash，.hash是一個用於加快訪問.symtab的雜湊結構，再索引到.symtab，詳見這裡，透過name去.strtab比對符號名，如果匹配就置換value。

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

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

先拿到essay-header，透過essay-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 */

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

};

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

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

|essay-header              |  

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

|load commands       |  

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

|__Text              |  

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

|__Data              |  —–> |

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

|other sections…   |  

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

|.strtab             |  

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

|.dynsym             |  —–> indirect symbol table

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

|…..               |

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

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

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

連結

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

靜態連結分為兩階段(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結構找到地址。

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

取用

• 程式員的自我修養—連結、裝載與庫

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，看技術乾貨