# CS:APP Ch3 Machine-level Representation of Programs
透過高級語言開發效率更高也更可靠，用高級的語言開發可以在不同的機器上編譯和執行，而 assembly code 則是與特定機器密切相關。
## 為什麼還需要學習 assembly code 呢？
1. 通過閱讀 assembly code ，可以了解編譯器如何優化、理解電腦如何執行程式並分析其中的低效率之處。
2. 試圖最大化一段關鍵程式碼效率的過程中，可以透過不斷修改程式碼，並觀察編譯器產生的 assembly code 來了解如何最大化效率。
3. 高級語言提供的抽象層會隱藏我們想了解的程式運行行為。例如了解 thread 之間是如何共享資料或是如何管理私有資料等。
## 重要名詞
- **Instruction Set Architecture** (ISA) : 必須理解 ISA 才能夠撰寫 assembly code 或是 machine code ，裏面定義處理器狀態、指令的格式以及每個指令應該執行所發生的行為。
- **Machine code**: byte-level programs that a processor executes
- **Assembly code**: A text representation of machine code
- ISA 的例子有 x86, x86-64, ARM or RISC V
- Instruction Set 是一個 software 和 hardware 之間的 interface。 (延伸閱讀: [計算機組織結構](https://hackmd.io/K2Gp6cozT7-rvsVG6Kktjg?view#Computer-Architecture))
- **Micro architecture**: Implementation of ISA in processor
- examples: cache size and core frequency
- 一般我們在看組合語言會發現裏面是不會去控制 cache 的。
* machine-level program 是由 ISA 所組成的，而 micro architecture 的概念包含的是處理器內部的構成和這些構成如何執行 ISA ，可以理解為 micro architecture 負責去實作出 ISA ，因此我們是無法透過 ISA 去控制 micro architecture 。
* 另外一個概念是不同的 processor 是可能支援相同的 ISA ，例如 intel 和 AMD 的處理器就都支援 x86 的 ISA ，但可想而知，Intel 和 AMD 的 microarchitecture 是不同的。
## Assembly / Machine Code View
我們知道 assembly code 和 C code 之間是有所差別的，有很多細節是在編寫 C code 無法去控制的，但對於程式設計師來說，這些概念應該要能夠了解
- Program counter ( PC ) : 下一個要執行 instruction 在記憶體中的位址。
- Integer Register file : 在 x86-64 的架構下，有 16 個暫存器可以使用，每個可以儲存 64 bits 的值，可以用來儲存 address （對應於 C 的 pointer ）或整數資料。
- Condition codes : 儲存 arithmetic or logical operation （例如 if 和 while） 的狀態資訊。
- Memory : 在 Ｃ 語言中我們可以使用各式各樣的資料結構、 signed / unsigned 或是指針，但對於 machine code 來說這些都只是一連串的 byte-addressed array 。
## Turning C into Object Code
gcc 利用一整套工具將原始程式碼轉換為可執行的程式。
### Compiler
- C preprocessor 插入所有 #include 所指定的標頭檔，並擴展所有 #define 指定的 macro ，接著產生 assembly code 。
### Assembler
- 將 .s 轉為 .o
- 將 instruction 轉換為二進位格式。
- object code 是 machine code 的一種，差別在於不同檔案的程式碼尚未有 linkage 。
### Linker
- resolve reference between files
- Combine with static run-time libraries. ex: `malloc` , `printf`
- Some libraries are dynamically linked
- 所產生的 machine code 可以被處理器直接執行。
可以參考： [CS:APP CH7 Linking 筆記](https://hackmd.io/@haogroot/cs-app_ch7)
## Disassembling object code
### 使用 GDB
- 進入到 GDB 之後，可以針對個別 procedure 進行 disassembling
| 指令 | 效果 |
| -------- | -------- |
| $ disas | disassemble 當前函式 |
| $ disas funcA | disassemble 函式 funcA |
| $ disas 0x005566 | disassemble 位址 0x005566 附近的函式 |
| $ disas 0x001234, 0x005566 | disassemble 指定位址內的程式碼 |
| $ print /x $rip | 以 16進制輸出 program counter 內容 |
## 使用 objdump
- 會顯示每個 instruction 的 bit pattern
- 製造出幾乎一樣的 assembly code ( disassembler 所使用的指令命名規則可能和 GCC 產生的 assembly code 有些微不同 )
- 可以對完整的執行檔 (a.out) 或是 .o file 來直接執行，且 objdump 不需要知道原始 source code 就能夠 disassemble 。
## Data types in Assembly code
- Integer : 最一開始是由 16 bit 擴展為 32 bit 的架構， Intel 定義 "word" 為 16-bits 的 data type 。而 "double word" or "long word" 代表 32-bits 大小的資料，"quad word" 代表 64-bits。在 assembly code 中的 integer 大小可以為 1, 2, 4 or 8 bytes.
- Floating Point : 4 (對應到 c 的 float ), 8 (對應到 c 的 double ) 和 10 bytes（對應到 long double ，但不建議使用他，並不是所有類型的機器都支援，且執行起來低效）
## x86-64 integer Register
資料來源： [https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf](https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf)
每個 x86-64 的 CPU 都包含 16 個暫存器來儲存資料和 pointer 。這些暫存器也可以只使用其 low-order 的 4, 2 or 1 bytes ，暫存器名稱可以由圖得知。在早期的 32 bit 架構下，例如 IA-32 ，只有 8 個暫存器且以 e 開頭來命名各暫存器，例如 `%eax` , `%esp` 。
## Operand Type in Assembly code
有三種 operand type ，分別是 Immediate, Register and Memory
* **Immediate** : 內含常數，其表示方式開頭必定有 '$' ，ex: `$0x5566`, `$-123`
* **Register** : 為 x86-64 integer type ，ex: `%rax`, `$r14`
* **Memory** : 根據 register 給定的位址再到該記憶體位址讀出 data 。
Register Indirect addressing: `(%rax)` 代表的是先從暫存器 `%rax` 讀出內容，該內容只是一個 memory address，接著到 memory 中該位址讀出資料，這樣的動作如同在 C 中 dereferencing pointer 。
這樣的 memory addressing Mode 還有許多種格式，可以參考 [wikipedia](https://en.wikipedia.org/wiki/Addressing_mode#Indexed_absolute) 或書中 p121 ，下面投影片提供 general form。
❓Scale 為什麼只能夠是 1, 2, 4 or 8 呢？
由於我們從 memory 中讀出來的資料，必定是某一種的 data type (char, integer, long ...） ，例如我們要讀出一個 integer ，他在 memory 上的 address 必定是對齊 4 的倍數，因此 scale 必須符合各種 data type 的大小，即 1, 2, 4 or 8 。
資料來源：[http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
## Operations in Assembly code
### Moving Data
```wasm
mov src, dst
```
src 和 dst 可以是任何一種 operand type ，但在 x86-64 有一條限制，**src 和 dst 不能同時都是 memory 的位址** 。
### load effective address
```cpp
leaq Src, Dst
```
這個指令等同於將 &Src 寫到 Dst 中，可以為後續的操作製作出指標。
但其實這個指令還有一個妙用，可以用來計算 `x + k*y` ，其中 k 為 1, 2, 4 or 8 ，為什麼 k 只能為這4個值呢？ 可以回憶前面學到的 complete memory addressing mode 搭配以下範例。
更多的 arithmetic operations 可見下圖：
# Machine-Level Programming - Control
在 C 語言當中，我們有 `if` , `while` 等可以根據測試條件來決定執行順序，在 assembly code 中有兩種基本的機制來實現這樣的行為，
1. 計算測試條件，根據結果**改變控制 flow** ，在以下 Conditional Branch 章節探討。
2. 計算測試條件，根據結果**改變資料 flow** ，在以下 Conditional Moves 章節探討。
## Condition Codes
除了 16 個 integer register ，CPU 還維護著一組 condition code register ，用來紀錄最近 arithmetic or logical operation 的結果，藉此來執行條件分支 （conditional branching）指令。常見的有以下：
- CF Carry Flag：用來檢查 unsigned 變數運算是否 overflow
- ZF Zero Flag：用來檢查運算結果是否為 0
- SF Sign Flag：用來檢查 signed 運算結果是否為負數
- OF Overflow Flag：用來檢查 signed 變數運算結果是否為負數
:warning: leadq 指令不會改變任何 condition codes, 他是用來進行地址計算的。
## Jumping
正常情況下指令會照順序一條一條執行， jump 指令會導致執行順序切換到程式中的某個位置。在 assembly code 中， jump 指令的目的地通常會用一個 Label 來指明。
- jump 指令會 implicitly read condition codes 來決定是否執行 jump 。
## Conditional Branch
以下圖程式碼為例，首先比較 x 跟 y 並設定 condition code，如果 `x ≤ y` 就 jump 到 Label `.L4` 。
資料來源：[http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
再將上圖的組合語言再轉換為 C 語言幫助理解（如下圖右邊程式碼），這樣的行為如同使用 C 中的 `goto` 。
source: [http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
這種根據測試條件來改變控制 flow 的作法使用在現代 CPU 上有可能會導致效能下降。
考慮到 CPU 使用 pipeline 技術，一條指令會被拆分為好幾個階段，如此 pipeline 內可以充滿待執行的指令來提升效能。 但是當遇到 conditional branch 的狀況，CPU 會採取 branch predict 方式，猜測接下來會執行哪個分支，才能夠在 pipeline 上預先放好待執行的指令 （現代 cpu 設計都試圖達到 90% 以上成功率），但是若預測失敗，也就代表許多已經執行的指令需要捨棄，造成效能上的浪費。
## Conditional Moves
相較於 Conditional branch 可能造成效能的浪費，Conditional move 透過一次將兩種結果事先計算好，接著再根據條件是否滿足選取對應的結果，這樣子就不需要執行 branch predict ，可以依照指令順序執行，可見下圖範例。
source: [http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
但是 Conditional Move 並不總是提高效率，如果分支都需要執行大量的運算，那麼當相對應條件不滿足，不滿足分支所做的工作也是白費，同樣是效能上的浪費。或是分支的執行可能會造成無法預期的結果等（可見下圖）。
source: [http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
老實說，編譯器並沒有足夠多的資訊來判斷該使用何種 Conditional Branch 或是 Conditional Moves 才有效率，根據 GCC 的測試結果來看，只有當兩個分支的 expression 都很容易計算時，才會使用 Conditional move ，其餘還是採用 Conditional branch 。
## Jump table structure
Switch statement 搭配 jump table 來實現， jump table 是一個 array ，內部存放著某個 code section 的 address ，當透過 index 來取得對應的 address，就可以 jump 過去，jump table 讓實現 multi-way branching 更加高效。
可見書 p159 的範例。
# Machine-Level Programming - Procedures
procedure 是一種封裝程式碼的方式，用一組指定的參數和一個回傳值來實現特定功能，可以在任意地方呼叫使用 procedure 。在不同的程式語言中， procedure 有不同形式的呈現，可以是 function, method, subroutine 或 handler 等等。
## x86-64 Stack structure
C 語言使用 procedure 過程中，可以透過 stack 來管理所需要操作的資料。
- 當 procedure 需要的記憶體空間超過 register 所能提供的，就會在 stack 上分配新空間，稱之為 stack frame，下圖即為 stack frame 的架構。
- stack 的記憶體是採取後進先出的原則。若是由 procedure P 呼叫 procedure Q ，此時 stack 中已經包含了 procedure P 的 stack frame，當 Q 執行時，透過 `pushq` 幫 procedure Q 向下新增他所需要的 stack frame，procedure Q 可以在 stack 中為 local variable 分配使用的空間，當 procedure Q 要回傳時，由 `popq` 指令來增加 `%rsp` ，值得注意的是，procedure Q 所使用的記憶體並不會被清空，單純透過移動 `%rsp` 指向的位置來分配 stack 。
- stack 是往 lower address 方向擴展，因此 `%rsp` 總是指向 the lowest address 。
- 事實上，許多 procedure 根本不需要分配 stack frame ，過程中所需要的參數可以都過 register 來傳遞即可 。 這邊也意味著一件事情，當我們在寫程式碼時候，應該避免傳遞不需要的參數，避免宣告不需要的記憶體，否則會造成 stack 空間的浪費，這樣的問題在遞迴使用過程更是嚴重，過多的 recursion 會造成 stack overflow 問題。 (延伸： [tail recursion](https://stackoverflow.com/questions/33923/what-is-tail-recursion) 透過參數來傳遞結果，減少不要 stack 的使用，來避免 stackoverflow 的具體例子)
-
假設 procedure P 呼叫 procedure Q, Q 執行完返回到 P 這樣的過程會發生以下機制：
### Passing Control:
控制轉移到 procedure Q 前：
(1) 將 return address（ P 中呼叫 Q 的該條指令的後面位址） push 進 stack 中。
(2) 要將 program counter 設為 Q code section 的開始位址並 jump (在 x86-64 中為 `call` 指令)
在 procedure Q 執行完回傳時：
(1) 從 stack 中 pop 出 return address 並 jump (在 x86-64 中為 `ret` 指令)
(2) 再將 program counter 設為 P 中呼叫 Q 的該條指令的後面位址 。
### Passing Data
例如 P 必須向 Q 提供一個或多個參數，Q 必須能夠向 P 回傳一個值。
總共有 6 個 register 可以用來存放參數，還有一個 register `%rax` 來存放 return value ，因此要是傳遞的參數超過 6 個，必須要在 stack frame 額外分配空間，這些空間將位於圖中的 "Argument build Area" 區塊，另外，通過 stack 傳遞的資料大小都向 8 的倍數對齊。
### Managing Local Data
以下狀況發生時，必須將 local data 存放到 stack frame 中的 "Local Variables" 區塊，且 stack frame 在 call procedure 到 called procedure 回傳時都必須被存著。
1. register 不足以存放所有的 local variable 。
2. 對一個 local variable 使用 & ，必須為它產生一個位址。
3. 某些 local variable 為 array 或 struct ，因此必須能夠透過 array 或 struct 被訪問
以下圖遞迴為例，function `who()` 呼叫 `amI()` ， `amI()` 會再遞迴呼叫到 `amI()` ，可以觀察到 stack frame 是不斷的增長。
source: [http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
當 `amI()` 逐一回傳時，回到了 `who()` 時，從下圖可以知道此時 `%rsp` 指向的是 `who()` 的 stack frame 。
source: [http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf)
### Register Saving Conventions
前面提到當 register 不敷使用時，才會在 stack frame 上分配記憶體，但若是遞迴的狀況下，這些 register 可能會不斷被多個 procedure 使用到，被呼叫者 (callee) 有可能將呼叫者 (caller) 所使用的 register 內資料覆蓋掉。因此 x86-64 採用統一的 register saving conventions 來避免這種狀況。
1. Caller Saved
- caller 在呼叫 procedure 之前，會將 register 內資料存在自己的 stack frame 中
- 可以理解為這類型的 register 內的值都可以自由被修改，因為 caller 本身必須負責去保存該 register 的資料。
2. Callee Saved
- callee 在使用 register 之前，會先將該 register 資料存在自己的 stack frame 中
- callee 在回傳到 caller 之前，再將資料恢復到 register 中
- 舉例來說，procedure P 呼叫 procedure Q ， 在進入 procedure Q 時，callee-saved register 必須由 Q 先存在 stack frame 中或是完全不去使用它，當 Q 要回傳回 P 時，再將這些 register 內的資料恢復原狀。
下面圖中詳述 x86-64 架構中各 register 的類型
### Observation about Recusion
stack frame 的機制讓我們使用遞迴時候不需要做任何額外的處理。
- stack frame 意味著每個 procedure 可以保有自己的 private storage
- Saved register & local variables
- Saved return pointer
- Register saving contentions 可以避免 procedure 呼相汙染彼此的資料
- Stack 在 procedure 被呼叫時候分配，在回傳時 deallocate ，這樣的機制很自然的符合 function 的 call / return 順序。
# Machine-level Programming - Data
## 3.8 Array Access
```cpp
T A[N]
```
上面是在 C 語言宣告一個 array 的方法，他在記憶體分配一塊 L * N bytes 的連續記憶體，其中 L 為 data type T 的大小。且引入 identifier A ，可以用 A 來表示一個指向 Array A 開頭的指標。
## Pointer Access
- 每個指標都對應到一個 type 。 這個 type 表明指標該指向哪一類物件 ( object ) 。
```cpp
int *ip;
char **cpp;
```
變數 `ip` 是一個指向 int type 物件的指標，而 `cpp` 指向的物件，其本身就是一個指向 char type 物件的指標。
* 每個指標都有一個值，這個值是某個指定類型的物件的位址。
* `&` 可以產生指標，對於一個表示某個變數的表達式 Expr ， `&Expr` 給出該變數位址的一個指標。
* `*` 間接引用指標，對於一個表示位址的表達式 Expr ， `*Expr` 給出該位址處的值。
表達式 `Expr` 與 `* &Expr` 是相等的。
* Array 和指標緊密關聯，一個 array 的名字等於其首位元素的位址，因此 Array 變數又等同於一個指向 Arr[0] 的指標。 而 array 名字搭配上指標運算就如同陣列引用有一樣的效果，也就是說 `*(Arr + i )` 等同於 Arr[i] 。
* 陣列引用和指標運算都需要用物件大小對偏移量進行伸縮。當我們寫表達式 `p+i` ，這裡的指標 p 的值為 *`p`* ，得到的位址計算為 `p+ L*i` ，這裡 L 是與 p 相關連的 data type 的大小。
* 將指標由一種 data type 強制轉換成另一種 type ，**只改變他的 type** ，**不改變他的值**。
強制類型轉換的一個效果其實就是**改變指標運算的伸縮量**。
例如，p 是一個 char * type 的指標，他的值為 *s* ，那麼表達式 (int *) p+7 計算為 *s*+28 （強制類型轉換的優先級高於加法），而 (int *) (p+7) 計算為 *s*+7 。\
* 指標也可以指向函式，提供一個強大的儲存和向程式碼傳遞引用的功能。函式指標的值是該函式 machine code 的第一條指令的位址。
```cpp
int (*f) (int*);
```
這是一個函式指標的宣告，要從裡（從 "f" 開始）往外讀。 因此，我們看到像 "(* f)*"* 聲明的那樣，f 是一個指標，而 *" (** f) (int *)" 代表 f 是一個指向函式的指標，這個函式是以一個 int* 作為參數。
最後，我們看到，他是指向以 int* 為參數並回傳 int 的函式的指標。
*f 兩邊的括號是必須的，否則宣告變成：
```cpp
int *f (int *);
```
會被解讀為
```cpp
(int *) f (int *);
```
變為一個單純函式的宣告，以 int* 作為參數，並回傳 int * 。
| Reference | Type | Value |
| -------- | -------- | -------- |
| &val[i] - val | long | i |
val[i] 為 index 為 i 處的值，透過 `&` 來取得指向 val[i] 的指標，而 `val` 本身也是指標，兩個指標相減就等同相同 Array 中兩個值的 index 差距。
延伸閱讀： [Pointer subtraction Confusion on stackoverflow](https://stackoverflow.com/a/3238520/4545634) 加
## Alignment Principle
> 如果 primitive data type 需要 K bytes， 則位址必須是 K 倍數 （通常是 2, 4 or 8），這樣的設計簡化了 CPU 和 memory 之間接口的設計。
例如一個 CPU 總是從 memory 中讀 8 bytes ，則位址就必須是 8 的倍數。如果我們能保證所有 double type data 的 address 都對齊 8 的倍數，就可以用一個記憶體操作的指令來讀或寫。否則需要執行兩次 memory access ，因為資料可能被放在兩個 8 bytes 的 memory 區塊內。 儘管沒有對齊位址 CPU 仍舊能夠正常運動，但是會造成效能的降低，因此還是建議要做好對齊。
編譯器會於 assembly code 放入以下命令，來表明 global data 怎麼對齊：
```wasm
.align 8
```
### Struct Alignment
在一個 struct 內會有各種不同 data type ，必須要能夠滿足每種 type 的 alignment 需求，同時 initial address 也必須滿足 alignment 要求，因此 struct 最終都以內部最大的 data type 來作為 alignment 的標準。
在 struct 內可以將較大的 data type 先宣告，這樣可以避免空間浪費，參考下方投影片的例子。
投影片來源 :
1. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/05-machine-basics.pdf
2. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf
3. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/07-machine-procedures.pdf
4. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/08-machine-data.pdf
5. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/09-machine-advanced.pdf
###### tags: `CS:APP`
Sign in with Wallet
Connect another wallet