Program

11 May 2019

程式編譯過程

  1. C program -> compiler -> assembly code(.o), object file
  2. object file(模組) -> Linker -> 把各個object file, shared object連成一個可執行檔
  3. loader load到記憶體裡

然後gcc本身可以想成是一個package, 內部其實含有很多的執行檔分別做不同事情, 如tokenizer,parser, linker等等, 所以我們呼叫gcc時, gcc會根據不同的參數來執行指定的執行檔執行

Preprocessing

第一步可以透過gcc -E的指令把C preprocess然後產出text檔, 這一步基本上就是把macro替換掉, 加入一些function routine(exit,_start,_end)

header檔不應該太大
Preprocess會把c檔裡的include的header file資訊也放到c檔裡面。因此當header檔很大而且有許多class、structure的定義甚至時作時，會導致每個c檔preprocess要很久，並且可能導致中間生成的object file包含很多不需要的text, data. 導致大專案編譯速度緩慢、執行檔很大。因此header file應該盡量拆小，不應該發生使用者為了使用某個function而include header，但那個header帶進來一大串的function, structure/class的declaration。

編譯成object file

這段其實是編譯器的精華, 他做的事情基本上就是把macro處理完, 還是text形式的程式碼真的轉換成machine-specific的assembly或binary file, 我們可以把整個流程分成幾個步驟

  1. 會透過tokenizer把程式裡面的symbol抓出來, 不論是variable name, function name, operators都是
  2. 抓出token後建立syntax tree, 這裡會簡單檢查語法(透過context free grammar,定義好一些規則, 看statement是否符合這些規則, 例如括號有對稱之類的)
  3. Semantic check, 判斷syntax完後換判斷語意, 這部分包括判斷運算的變數型態是否正確, 是否出現int a = 5.12這種不合法的語意
  4. 判斷完後會產生一種中介語言(intermediate code), 可能是p-code或者three-way code, 就是把整個程式碼的statement簡化成幾種簡單的表示形式, 接著就編譯成obj檔
  5. obj檔基本上就是把這個檔案內現有的程式變成Machine code的格式, 所以要用objdump才能看到asm的部分, 這時只是單純把c code轉成machine code, 變數或者import的Function位置都還沒填入, 畢竟只編譯單純一個檔案, 自然用到其他檔案的函式的話就不知道他們的位址, 這部分會交給後續的Linker來做填入變數, 函式的部分(relocation).

透過gcc -S可以把c檔變成assembly檔()
gcc -c可以把c變成obj檔, 不會呼叫linker

Object module

編成assembly code時，有變成.o檔的形式，他會紀錄這個程式的header,text segment,relocation info(aslr關係，紀錄text,儲存位置的offset)，symbol table。
library會用.o形式儲存，利用linker把library裡面的function link到那個主程式的檔案

基本上這裡引入的是模組化的概念, 原因是我們在寫程式時會用一堆函式來幫忙(因為應該沒人會想寫inline asm或者systemcall來時做東西吧…),包括libc裡面的各種函式或者自己寫的函式, 如果我們把這些已經寫好的東西每次都要import到現在這個新的程式碼裡面, 程式碼會爆炸大, 可能一個簡單hello world就要數百甚至數千行, 因次採用模組話概念, 把其他Function寫在其他.c檔, 最後可以編譯成不同的格式(o, a, so檔), 然後各個檔案編譯完後,最後再透過連結方式連結近來就好. 這樣單一個hello world程式碼就變成非常乾淨, 不會說要用printf就要把printf程式碼複製進來這個現在檔案.

程式檔本身是會有external reference的狀況(即引用其他c檔案的symbol, 如使用其他c檔案的variable, user-defined data type, function等等)，編譯成obj檔這部分只針對單一檔案進行，所以對這些external symbol是沒辦法解析的，obj檔通常會先把這些variable在程式碼中填入0x0或者0xfcffffff, 舉例而言mov 0x0 0x4(%esp), 因為不知道variable位址，所以指令上先填入0x0,之後linker在把正確位址填入。 linker連接完後，會把該行指令變成mov 0x804108 0x4(esp), 0x804108就是linker link完後該variable的VMA。

Linker

G++實際上在編譯複數個Cpp檔時，是逐一把cpp檔變成各個object file,接著在用linker把object file連再一起變成executables, 所以以下指令是等價的。而把多個object file連再一起的過程就是linker (ld)這隻binary。

$ gcc 1.c 2.c -o test
等於
$ gcc 1.c -o 1.o
$ gcc 2.c -o 2.o
$ gcc 1.o 2.o -o test

取得library,function和把複數個object file合在一起(處理reloc,external reference(存取其他.o檔的變數、函式), 就像上述說的obj檔基本上就是把程式碼變成machine code, 但因為只編譯單一檔案, 所以他對使用的外部函式(import其他檔案的函式)一無所知, 所以這時的很多指令用到的symbol其實位置都沒填入, linker一部分工作就是負責把這些symbol建立起來, 位置填入，並把複數個obj檔的區段做合併(如合併symbol table, text等等)

gcc file1.o file2.o -o exe : 把3個object檔statically link成一個executables
gcc -L[Dir] -l[object file] : -L就是加入library的位置, -l就是找Dir裡面的指定的library連起來(.so(dynamic link)或者.a(static link))
上面兩個步驟基本上就是static linking, 就是把所有object檔案擠在一起變成一個很肥的executables

linker一般採用two-pass linking，把object file連結成執行黨檔的步驟分成兩步:

  1. 空間位址分配:
    • 掃描所有obj檔，獲得各個區段的長度、屬性、位址，將各個obj檔symbol table裡的symbol搜集起來放到一個全域的symbol table，
    • 賦予每個segment一個虛擬位址(Virtual Memory Address, VMA)
  2. 符號解析和relocate:
    • 配合reloc table進行符號解析跟位址重定(例如external reference符號，把符號位址填入，原本單一個obj檔可能有很多符號來自另一個obj檔，所以暫時填入0,linker就是要把正確的位址填入)
    • 決定每個符號(function, variable)各個符號的offset
ld a.o b.o -e main -o ab

-o: 輸出的檔名為ab
-e: 將function main作為程式的入口, ld會把_start呼叫main

Relocation Table

一個程式檔裡可以有0或多個重定表，確切說是任何需要重定位址的segment都需要一個重定表(如.rel.data, .rel.text), 可以使用objdump -r a.o來看一個obj檔裡的reloc segments

重定表內紀錄該segment內需要重定的symbol(如.rel.text就紀錄text區段需要重定的symbol/function等等)，每個symbol就叫一個relocation entry, 紀錄該symbol跟symbol距離該segment的起點的offset, 以及reloc的info(如重定項的類別，符號在symbol table的offset)

每種處理器處理重定向的細節都會有所不同，所以才會要有重定向的類別的資訊。

在linker連結obj檔時，一個很大的任務就是把reloc table裡的所有symbol都定址，正常狀況下未定址的symbol他的section位址在symbol table都是顯示UND，然後linker就是要把reloc table裡每個entry都iterate一遍，去global symbol table找到該symbol並定址。 如果linker最終有發現有reloc entry找不到reference, 那就會報錯。

Shared Object

Object檔問題是每次編譯都要放到binary裡面, 一來是程式會變得很肥大, 二來是如果很多程式經常會使用某個object file, 那變成那個object file會複製很多份放到各個binary file裡面, 非常佔空間, 所以用shared object讓需要的人再來linked這個object, 而不用binary編譯時就把library放到程式裡面.

通常會下pic(position independent code)的指令, 目標就是把一個程式編譯成library的形式能夠給其他program之後import, 裡面可以含有多個.c .h檔, 把它包成一個so檔(如libc.so)

gcc -shared PIC test1.o test2.o -o libfoo.so
PIC指令讓code在編譯時盡量不要在asm裡面有絕對的記憶體位置, 盡量都用相對的形式(如rsp +0x10000之類的)

如果有用自己產生的shared object,執行時可能也要設定LD_LIBRARY_PATH, 不然linux會不知道去哪裡找shared object

useful commands

  • ldd: 看程式有link那些shared object
  • nm: 看程式有哪些symbol
  • objdump: 把binary變成asm, 但不會顯示shared object裡的library的asm, 只會顯示當前執行檔的
  • readelf: 讀elf檔格式跟各個section位置

執行流程

當編譯成執行檔並執行後, OS接收到指令會開啟一個Process來跑我們這個執行檔,同時OS也會allocate好記憶體跟page table給這個process, 而執行檔在編譯時就已經把一些C的startup routine連接好(libc_start_main等等) 所以program counter一開始會先把這些程式的start up routine跑完才開始跑main function, 接著either main function return或者呼叫exit 程式就會終止, 終止時會一樣由程式編譯進去的exit handler來處理好一些事情然後OS真的把process kill掉

Loading a program

loader在編譯時已經以shared object的形式跟binary檔link再一起(所以ldd binary file時除了看到libc library通常還會看到一個ld-linux.so, 這個就是loader), loader的工作就是把程式的symbol, 程式各個片段放到memory裡執行

把程式移到memory，

  • 讀header(text segment, symbol table…)
  • 建立virtual address
  • 把程式、data寫進memory，stack建好(esp,ebp…)
  • eip移到該處執行

Dynamic linking (lazy linkage)

static linking直接把用到的library的.o檔放進binary file裡，結果是binary file會變超肥，因為包含很多.o檔。
dynamic linking 只有在要call那個function時才load該.o檔
第一次call function時，會用linker, loader把該.o檔、function import進來，第二次呼叫該function後就已經有該function，不用在call linker, loader，程式就已經把該function load進memory且知道位址了。

Reference

shared library, object file
C compile stage

Program memory layout

  • stack allocate從high address到low address(往下長)
  • heap allocate從low address到high address(往上長)
  • bss:沒initialize的直會放在這裡，例如沒initialize的全域變數(但exec會幫忙做initialize to default value)
  • data: 有initialize的data放這，例如initialize的全域變數
  • bss/data section都是同時可以read/write
  • text: 程式碼區段: 只能read,執行

stack 會有fp,sp紀錄現在這個frame

fp:存這個frame的base，

  • 一來能夠在遞迴時fp持續指向上個stack frame位置，能夠在這個frame return後能再次回到上個frame位置，
  • 本身不像sp會動，所以可以拿來當作指向這個stack裡面變數的基準

EX: mov $eax, $fp + 0x48

ELF format

  • ELF header就是紀錄magic number, entry point, machine, type(.o, .so)之類的資訊
  • Program header table紀錄各個section位置