Executable and Linkable Format(ELF)

Object file: Compiler編譯原始碼產生的檔案

目前常見的可執行檔格式 :
      Windows下的PE(Portable Executable)
      Linux的ELF(Executable Linkable Format)

Object file就是原始碼編譯過還沒Link的檔案(Windows的.obj和Linux的.o)
廣義來說，Object file和可執行檔的格式其實幾乎是一樣的

Object file被分成好幾個塊Section

    Code Section:常見的名稱有.code或是.data
                 用來存放source code編譯過後產生的instruction

    Data Section:global variable和local static variable都存放在這邊
                 (注意: 不包含local variable以及dynamic variable
                        前者放在程式被load到memory後配置的stack
                        後者放在程式被load到memory後配置的heap  )

                 Data Section又分成三個部分

                 1. .data: 放置已初始化的global variable
                    以及static local variable

                 2. .bss:  放置未初始化的global variable
                    以及static local variable，因為他們的值都是零
                    不需要花額外空間存放零這個值。bss只是為未初始化
                    的變數預留位置而已

                 3. .rodata: 放置Read-Only data，比如說加const修飾過
                    的變數，或是字串常數。ex: printf("%d", a);的%d
                    char a[] = "abcd"; 中的abcd

 
  ELF layout(http://en.wikipedia.org/wiki/File:Elf-layout--en.svg)

這邊出一個小問題，請問一下code中 x1和x2會被放在什麼區段中

static int x1 = 0;
static int x2 = 1;

x1會放在.bss中，x2會放在.data中。x1可以被當作未初始化，compiler最佳化之後
會把x1放到.bss中，節省空間，因為.bss不佔空間。另一個變數x2因為已經初始化
為1，所以放在.data區段中。

除了上述這些比較常用的區段外，ELF還有很多預設的區段。甚至我們可以自己定義區段
比如說我們可以在ELF檔中加入一個"music"的區段，裡面存放一首MP3音樂
程式執行時候可以直接讀取這個區段的MP3資料，把資料加入object file
可以使用objcopy這個指令

ELF檔一開始會有個ELF Header，Header最開頭是ELF的magic number
當OS load可執行檔的時候，會去檢查magic number是否正確
如果錯誤就拒絕載入。Header檔接下來包含一些檔案的資訊
比如說是Little-Endian還是Big-Endian、程式開始執行的的進入點
在unix下，可使用readelf來詳細查看ELF檔案

ELF Header有個e_shoff會定義Section Header Table在ELF檔中的位置
Section Header Table明確的定義這個ELF檔各個區段的資訊
內容包含區段的名稱、所佔的長度、在檔案中的位置、以及讀寫權限等屬性

同樣的，可以使用"readelf -S"來查看Section Header Table的內容

ELF檔還有一些重要的Table如下:

    Relocation Table: Linker在Link object file檔的時候會需要對
                      object file的某些地方作relocation
                      這時候會參考此表進行relocation

    Symbol Table: 儲存所有用到的variable以及function的名稱
                  可以使用nm列出Object file的Symbol Table
                  其中包含Sysmbol所在區段、以及所在位置等資訊

Strong Symbol and Weak Symbol(強型別和弱型別)

Compiler會把已經初始化的Global varible當作Strong Symbol
未初始化的Global varible為Weak Symbol
我們可以使用GCC提供的 "__attribute__((weak))"
來定義任意一個Strong Symbol為Weak Symbol
以下是一個例子:

extern int ext;

int weak;
int strong = 1;
__attribute__((weak)) weak2 = 2;

int main(){
    return 0;
}

在這個例子中weak和weak2都是Weak Symbol
strong和main是Strong Symbol
ext不是Strong也不是Weak，因為他是一個外部變數

Compiler會按照下列規則處理Strong以及Weak Symbol

Rule1: Strong Symbol不能在不同的Obj檔被多次定義
       這就是我們常常看到的重複定義錯誤

Rule2: 如果一個Symbol在某個檔案是Strong，在其他檔案都是Weak
       Compiler會選擇Strong Symbol

Rule3: 如果一個Symbol在每個檔案都是Weak，會選擇最大的Type
       比如說一個同樣名稱的int和double global varible
       Compiler在Link的時候會選擇double

外部符號的Reference也有分兩種

Strong Reference:  在Link時找不到符號定義會回報錯誤
Weak Reference:   在Link時找不到符號定義不會回報錯誤，通常會預設為0

下面是GCC把foo()宣告成weak reference的擴充keyword

__attribute__((weakref)) void foo();

int main()
{
    foo();
}

上面這段code可以編譯成執行檔且不會產生錯誤

但是我們執行程式的話，因為沒有定義foo()，foo的位置為0
因此會發生不合法的位置存取錯誤

Weak Symbol和 Weak Reference對函式庫的設計非常有用
函式庫可以定義一些Weak Symbol的函式
使用者可以自己定義一些Strong Symbol達到擴充功能
因為Strong Symbol會蓋掉Weak Symobl

我們也可以透過Weak Reference使用一些擴充功能
以後就算我們把擴充功能去掉，程式還是可以正常Link

Static Linking(靜態連結)

Linking : Linker把多個Obj檔加工合併成一個Output檔

方法有下列兩種

1. 依序累加: 把Input的Obj檔依照次序合併起來
             Output檔依序為ObjA的.text .data .bss section
             接下來放ObjB的.text .data .bss section，以此類推

   缺點: 浪費空間，以x86來說最小的page為4096bytes
             有可能ObjA和ObjB的.text section加起來小於一個page
             但是使用此方法卻必須放在兩個不同的page

2. 相似區段合併:
                 把所有Obj檔的.text合併到輸出檔的.text section
                 依序合併.data、.bss這些section
                 目前static linking採用此方法

目前gcc Linker使用一種叫Two-pass Linking的方法，整個Linking過程分兩步驟


1. 分配空間和位置: 先掃描一遍所有的Obj檔，計算出各個section所需要
                   配置的空間大小以及虛擬位置(VMA)

2. 符號解析和重定(relocation) : 對所有使用到的Symbol做調整以及relocation

一般來說，如果我們使用到一些外部變數或是函式。在編譯的時候Compiler由於
還不知道這些變數和函數的位置，因此會先填一個假的位置到產生出來的指令中
當Linker做Linking的時候，就會去對這些假位置做調整並且換成正確的位置
這個動作叫做Relocation


重定表: 紀錄哪些指令需要被調整的一張table，可以重定的ELF檔中都會有一份table


Static Linking有下列缺點

1. 空間浪費: 每個程式內部都會有printf()、scanf()這些函式
2. 更新困難: 假如要更新某個lib檔，必須要對所有使用到這個lib檔
             的程式重新Link。並且重新發佈給使用者。

extern "C"

大家都知道extern "C"這個關鍵字是用來讓C++與C相容

例如:

extern "C" {
       int func(int);
       int var;
   }

C++會把大括號裡面的code當作C來處理
因此不會使用C++的Name Mangling機制
而會使用C原本的機制
目前Visual C++會把符號前面加上"_"
GCC則不會做修飾

因此我們常常會看到C Library中這樣寫

#ifdef __cplusplus
extern "C" {
#endif

void *memset (void *, int, size_t);
char *strcat (char *, const char *);
int   strcmp (const char *, const char *);
char *strcpy (char *, const char *);


#ifdef __cplusplus
}
#endif

就是因為C++會自動把memset修飾成_Z6memsetPvii
造成Linker在C Library中找不到這個符號發生錯誤
這時候可以使用__cpluscplus這個Macro來辨別是否是編譯C++程式
Compiler會在編譯C++程式時自動定義這個Macro

分析大型專案程式碼的方法(How to trace the source code of a big project)

要如何Trace一個數百萬行的程式呢? 這是一個好問題

在幾十萬行甚至數百萬行的程式，是不可能一行一行去Trace code
我們也不需要去瞭解code每一行的意思
這時候工具就很重要了

我們最重要要知道的事就是整個系統的流程，這點可以利用GDB來觀察


整個分析系統的方式分為三個步驟

1.觀察
  一開始利用GDB執行程式，並隨意操作系統
  這時候可以觀察debug訊息以及thread的狀態
  根據印出來的訊息，在適當的地方觀察系統流程和架構

2.適度修改
  適度修改是說在run time的時候利用GDB修改執行的程式
  避免用editor直接修改code
  可以把GDB當成是Interpreter來用，設定中斷點把某一行code換掉
  甚至可以直接修改記憶體內容。修改完之後觀察執行結果是否如我們猜測的一樣
  這邊可以利用GDB提供的資訊，比如說call stack、變數內容、變數type進行分析
  直到瞭解系統整個流程為止

3.擴充
  幫這個系統加入一些新的功能，同樣的我們不需要用editor修改code
  只要透過GDB在run time時候修改code即可
  當你可以為一個系統加入新功能的時候，大概就瞭解整個系統八九成了


4.驗證的macro
  在GDB當中可以加入驗證你程式正確性的macro
  大部分open source專案(比如說Apache)都會提供GDB macro讓你驗證程式
  你也可以自行撰寫macro來自動驗證你修改的程式是否正確


另外盡量不要使用GUI的GDB
原因有兩個

1.GUI的GDB往往都不是最新版本的GDB，沒辦法用一些新的功能
2.在有些情況下X-window會整個爛掉，比如說開發一個新的輸入法

程式設計師的自我修養：連結、載入、程式庫

看完這本書後我有個心得，強烈推薦每位程式設計師都該讀這本書!

本書就如同他副標題所寫得，詳細的帶讀者深入瞭解一個程式的Linking, Loading, Library是如何運作的。書中先從最基本的Compile and Linking開始介紹，之後慢慢介紹Static Linking、剖析Object檔、Loading、Dynamic Linking。作者不只分析了Linux下的ELF檔，連Windows的Dynamic Linking機制都有詳細的介紹。本書是每個想要瞭解系統在做什麼的程式設計師必讀的一本書。我當場在書局翻過之後就決定買一本回家看了。

就我求學的經驗，就算念到碩班，能把這些東西搞清楚的人也沒幾個。很多人念到碩士畢業可能連程式怎麼在OS中執行都沒有概念。雖然說不用懂這些東西也能寫程式，不過我相信要寫一手好程式是不可能不去瞭解Compiler。這本書提供了一個很好的入門點，學C和C++有一段時間的朋友們相信讀了這本書都會有恍然大悟的感覺! 很推薦大家去讀這本好書。

最後離題一下，我一直覺得國內中文書很缺少這類偏底層、系統的書籍(這本書也是大陸人寫得)。反而國內很喜歡出一些程式語言的入門書(什麼一個禮拜學會C++......)。說真的有時候很羨慕大陸，他們真的出了很多硬底子技術的書。這點真的值得國內出版社省思。

底下是一些讀書筆記，大家可以參考看看

• C++名稱修飾(Name Mangling)
• Static Linking(靜態連結)
• Strong Symbol and Weak Symbol(強型別和弱型別)
• Executable and Linkable Format(ELF)

C++名稱修飾(Name Mangling)

在70年代以前，Compiler產生Object檔時
符號名稱和對應的變數、函式名稱是一樣的
也就是說如果你在code宣告定義一個foo函式
foo在Object檔中對應的符號名稱也叫做foo

這樣的設計有個缺點，如果你使用C Library
你就不能使用C Library已經定義好的變數與函式名稱
否則有重複定義的問題

因此後來UNIX就規定code經過編譯之後
要在對應的符號名稱前加入"_"
比如說"foo"就變成"_foo"
這個方法的確可以減少符號衝突的機率
但是並沒辦法完全解決符號衝突的問題
因此C++加入了Namespace來解決符號衝突的問題

C++有繼承和多載等特性
以多載來說，要讓Compiler能分辨兩個相同名稱的函式
就必須要在產生的符號上動一些手腳
這個動作叫做Name Mangling

以下列這個例子來說

int func(int);
float func(float);

class C {
    int func(int);
    class C2 {
        int func(int);
    };
};

namespace N {
    int func(int);
    class C {
        int func(int);
    };
}

這段code一共有6個func函式，他們不同的地方只有參數以及Namespace不一樣
Compiler會使用這些函式的Function Signature來辨別他們
Function Signature會加入函式所在Class以及Namespace等資訊
用來辨別不同的函式，就好像函式的簽名一樣


例如:
class C {                      Function Signature
    int func(int);        ==>  int C::func(int)
    class C2 {
        int func(int);    ==>  int C::C2::func(int)
    };
};

namespace N {
    int func(int);       ==>  int N::func(int)
    class C {
        int func(int);   ==>  int N::C::func(int)
    };
}

當compiler在把source code編譯成object檔的時候
會使用Name Mangling這個方法，把Function Signature修飾後轉成對應的符號
例如(使用GCC):


                            修飾過後的符號名稱
int C::C2::func(int)   ==>  _ZN1C2C24funcEi
int N::C::func(int)    ==>  _ZN1N1C4funcEi
int func(int)            ==>  _Z4funci
float func(float)      ==>  _Z4funcf

GCC的C++名稱修飾規則如下

1.所有的符號都由"_Z"開頭
2.如果是巢狀的名稱，就在開頭的"_Z"之後加上"N"
3.接下來是Namespace以及Class的名稱，寫法為字串長度 + "N" or "C"
4.如果是巢狀名稱的話，最後以"E"結尾
5.E後面接retrun type，int寫為i，float寫為f

此外binutils當中提供一個工具"c++filt"可以幫我們解析修飾過得名稱
ex:

$ c++filt _ZN1N1C4funcEi
N::C::func(int)

C++的global varible以及static varible同樣也會經過修飾
例如Namespace foo中的global varible bar會被修飾成 _ZN3foo3barE

不同編譯器Name Mangling的作法通常會不一樣
例如Visual C++就使用和GCC完全不同的Name Mangling方法


Reference: http://en.wikipedia.org/wiki/Name_mangling
                 程式設計師的自我修養：連結、載入、程式庫

USB Complete: The Developer's Guide(USB完全開發手冊)

前些日子因為工作要用到USB的關係，我從書局買了這本書。讀完這本書之後再搭配一些網路上的文件。我很快花了一個多禮拜的就搞懂USB的基本原理。

這本書寫得不但詳細而且好懂。因為我是搭配USB spec一起看，有些地方spec沒寫清楚，回頭看一下這本書就瞭解之前不懂得地方了。書中舉了很多Windows USB Driver的sample code(written in C# and VB)，雖然我最後沒有用書中的範例，不過sample code還是幫助我瞭解了整個USB的概念。總而言之，這是本很好介紹USB的起步書，推薦給想要瞭解USB的新手！

附註: 這本書同時還有中譯本，翻得也不錯。如果覺得英文書太貴也可以考慮買中文書。

Programming Embedded Systems in C and C++(嵌入式系統–使用 C/C++)

這本書是很多人推薦的嵌入式入門書，內容針對嵌入式系統做了一些基本的簡介。如果你是一個完全沒有嵌入式概念的人，看這本書或許是一個不錯的選擇。因為作者寫得很淺顯，只要你會基本的C和C++就能看懂這本書。

或許這是一本不錯的新手入門書，不過這本書有個問題。現在已經是2011年了，而這本書出版的日期是1999年。書中使用的一些硬體(80186)現在都不是主流的產品。此外一些Embedded Systems重要的元件像是Keypad, LCD, Button, ADC......都沒有介紹。簡單的說，這真的就是一本給初學者簡單認識Embedded Systems的書。如果你是完全沒概念的新手，這本書或許可以給你一些協助。不過我還是建議去看 現代嵌入式系統開發專案實務 這本中文書，這本才是真正可以帶你進入Embedded Systems的入門書。

至於有經驗的開發者完全不建議來看這本書，因為你根本學不到什麼。

附帶一提，這本書有翻譯成中文版。不過我覺得翻譯的沒有很好，有些名詞怪怪的。還是建議新手要看的話看原文書會比較好。

註: 這本書有第二版不過我沒看過，第二版是2006年出得。

Les 4 Vies de Steve Jobs(你所不知道的4個賈伯斯)

這是我在Jobs過世之前去圖書館預約的，不過沒想到還沒拿到書就聽到他去世的消息。

這整本書是由Daniel Ichbiah這位法國記者所撰寫，此作者之前也寫過Bill Gates傳記。這本書主要的資料來源都是作者實際去採訪蘋果的創始員工，像是Wozniak、Kottke......等，因此整個角度有點像是從旁觀著來描述Jobs。附帶一提，Jobs唯一的一本授權的自傳是今天開始販售的《Steve Jobs: A Biography》。

這本書收集了大量的資料，內容非常的豐富，作者和翻譯也寫得非常好，讀起來的感覺就像在讀一本小說而且很流暢。作者一共把Jobs的一生分成4個階段：

1. 求學生崖到創立蘋果時期
2. 推出Apple II成為美國最年輕的百萬富翁，之後因為麥金塔的失敗而被自己請來的CEO John Sculley趕出蘋果
3. 失落的十年，直到把NeXT和Pixar推向高峰，重返蘋果
4. 推出iMac和iPod從此邁向事業高峰

看完了這本書真的很佩服Jobs，他是一個真正在做創新的人，他早期推出的產品有些雖然失敗。但是事後都證明他當時的眼光是沒有錯得，只是推出的時間太早了或是當時的技術還達不到他的要求。

另一個佩服他的一點就是在他被趕出蘋果之後，這段時間長達了10年，而且這段時間剛好是他的死對頭Bill Gates最輝煌的年代，他還能重生並且重返蘋果。要是一般人承受他當時的壓力可能早就放棄了。

總之，這是一本很值得一看的書。這本書從Jobs的創業夥伴的角度來描寫他，這點或許可以和之後推出的Job傳來一起閱讀。看看兩方不同的觀點也是很有意思的