# 讀 CS:APP 簡中版
> 搭配服用 http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html
## 辭典
:::spoiler {state="open"} >> 收縮點此 <<
|繁體中文||english|
|:-:|:-:|:-:|
| 作業系統 | 操作系统 | operating system |
| 匯流排 | 总线 | bus |
| 記憶體 | 主存, 內存 | main memory |
| 快取 | 高速缓存 | cache |
| 位元組 | 字节 | byte |
| 區段 | 节 | section |
| 載入 | 加载 | load |
| 組譯 | 汇编 | assemble |
| 堆疊 | 棧 | stack |
| 並行 | 并发 | concurrent |
| 平行 | 并行 | parallel |
| 程式 | 程序 | program |
|| 过程 | procedure |
| 行程 or 程序 | 进程 | process |
| 執行緒 | 线程 | thread |
|| 立即数 | immediate |
| 核心 | 内核 | kernel |
| 網際網路 | 万维网 | WWW |
| 1 補數 | 反码 | ones' complement |
| 2 補數 | 补码 | two's complement |
|| 端法 | endian |
|| 信号量 | semaphore |
| 例外 | 异常 | exception |
| 排程 | 调度 | scheduling |
| 暫停 | 挂起 | suspend |
| 資料結構 | 数据结构 | data structure |
| 韌體 | 固件 | firmware |
| | 套接字 | socket |
| | 数据报 | datagram |
| 埠 | 端口 | port |
| | 条件跳转 | conditional jump |
| | 条件传送 | conditional move |
| | 内联替换 | inline substitution |
| 最小平方法 | 最小乘积拟合 | least squares fit |
| | 內存別名 | memory aliasing |
| | 发射时间 | issue time |
https://zh.wikipedia.org/wiki/%E6%8E%A5%E5%8F%A3
:::
## 第 1 章
### In Unix, everything is file.
- file 是對 I/O 的抽象
- virtual memory 是對 program memory 的抽象
- process 是對 running program 的抽象
- 虛擬機是對 computer 的抽象
### 並行
- thread-level concurrency
- hyperthreading
- simultaneous multi-threading, e.g., FPU
- instruction-level concurrency
- single instruction multiple data, i.e., SIMD
## 第 2 章
> jserv ：第 2 章的習題每一題都要做
編譯參數
- `-m32` ：為 32 位元電腦編譯
- `-m64` ：為 64 位元電腦編譯
告訴大家一個神器： ==man ascii==
C 語言標準沒有明確定義 bitwise 右移，也沒有規定有號數該如何表示
| symbol || 32 位元 |
|:-:|:-:|:-:|
| $UMax$ | `UINT_MAX` | 0xFFFFFFFF|
| $TMin$ | `INT_MIN` | 0x80000000 |
| $TMax$ | `INT_MAX` | 0x7FFFFFFF |
A portable `printf()` may be implemented by macro, such as
```c
/* portable printf */
int32_t x;
uint64_t y;
printf("x = %PRId32, y = %PRIu64\n", x, y);
```
### 有無號數轉換
C 標準沒有定義，但大多數的系統依循不改變位元更改詮釋方式
```c
int main()
{
int v = -12345;
printf("v = %d, uv = %u\n", v, (unsigned)v);
return 0;
}
/* Result in:
* v = -12345, uv = 4294954951
*/
```
For an signed number $x$, the conversion to unsigned can be described by
$$
\mathrm{T2U}_w(x)=\begin{cases}
x, &x\geq 0 \\
x+2^w, &x<0
\end{cases}
$$
:::spoiler e.g.
$\mathrm{T2U}_{16}(-12345) = 65536+-12345 = 53191$
:::
\
For an unsigned number $u$,
$$
\mathrm{U2T}_w(u)=\begin{cases}
u, &u\geq \mathrm{TMax}_w \\
u-2^w, &u<\mathrm{TMax}_w
\end{cases}
$$
---
:::danger
unsigned 和 signed 運算的結果會被 implicitly 轉換成 unsigned
:::
在定義 INT_MIN 時最好寫成 `-INTMAX - 1`
一個數字被++擴展++時會使用 sign extension ，例如：
```c
short sx = -12345;
unsigned uy = sx;
printf("uy = %u:", uy);
show_bytes(&uy, sizeof(unsigned));
```
在我的電腦 (little endian) 上的執行結果是：
```shell
uy = 4294954951: c7 cf ff ff
```
:::warning
這是我所用的 `show_bytes()` 函式
```c
void show_bytes(void *ptr, size_t len)
{
for (int i = 0; i < len; i++)
printf(" %x", *((unsigned char *) ptr + i));
printf("\n");
}
```
我發現如果把 `unsigned char` 改成 `char` 就會錯，但是我不知道為什麼
:::
一個數字被++截斷++時會無視 sign 逕行截斷，例如：
```c
int x = 65534;
short sh = x;
printf("%hd\n", sh);
```
會得到 -2 而不是 32766 。
size_t 是無號的， ssize_t 是有號的
### 加法
無號數加法類型為模加法，無號數發生 overflow 不會終止程式 (不會發 signal) 。
在 unsigned 情境下，令 $s=x+y$ ：
- $s$ overflow $\iff$ $s<x$ $\iff$ $s<y$
而因為模加法的特性，使無號數形成 [Abelian group](https://en.wikipedia.org/wiki/Abelian_group) 。
在 signed 的情況下，令 $s=x+y$ ：
- $s$ positive overflow $\iff$ $(x>0)$ && $(y>0)$ && $(s\leq 0)$
- $s$ negative overflow $\iff$ $(x<0)$ && $(y<0)$ && $(s\geq 0)$
對某數 `x` 取 2 補數的方式，除了 `~x + 1` 之外，可以等價地使用：
- 先找到 `x` 的 least significant set bit
- 低於等於的 bit 不變
- 高於的 bit 取 `~` flip
### 乘法
對無號數一樣是模乘，因為一樣會 truncate 到 $2^w$ 內。
有號數一般需要將負值皆轉正，處理完 magnitude 後再處理 sign ，有些算法可以加速，例如 Booth’s Algorithm 。
:::success
使用 `malloc(sizeof(x) * n)` 時須小心 argument 的 overflow 問題，雖然一般使用上不會溢出，但是得要防範惡意輸入。若傳入值 `n` 與 input 有關，則呼叫 `malloc()` 前應先行檢查以避免安全漏洞。
:::
### 除法
速度甚至比乘法要慢得多，若有效能考量應避免使用。
:::info
page pointer : 72
:::
## 第 3 章 Machine-Level Programming
x86 assembly
### Intel 用詞
- word 16 bit `b`
- double word 32 bit `l`
- quad word 64 bit `q`
- oct word 128 bit
### Registers (整數)
- %rip : program counter
- (page 120)
- %rsp : stack pointer
- conditional code
### Instructions
- immediate $
- register %
- memory ()
immediate 在 `$` 後面接 C 語言數字表示法
1, 2 byte 指令會保持 8 byte 內的其它 byte 不變
4 byte 指令會把高位的 4 個 byte 清零
```
mov S, D # S to D
```
- movb : move byte
- movw : move word
- movl : move long word
- movq : move quad word
- movabsq : move an immediate to a registser
:::success
x86 的 store 和 load 都是用 `mov` 來實現
:::
```
movz S, R # move with zero extension
movs S, R # move with sign extension
```
`cltq` 為用於 `%eax` 到 `%rax` 的 sign extension
```
pushq S # push a quad word to stack
popq D # pop a quad word from stack
```
`%rsp` 會跟著更新
```
inc D # D <- D+1
dec D # D <- D-1
neg D # D <- -D
not D # D <- ~D
add S, D # D <- D+S
sub S, D # D <- D-S
imul S, D # 指定乘積暫存器的大小，超過會被丟棄
xor S, D
or S, D
and S, D
sal k, D # left shift
shl k, D # left shift
sar k, D # arithmetic right shift
shr k, D # logical right shift
```
The shift operations 的 `k` 需要是 immediate 或是放在 `%cl` 中的值， `%cl` 是一個 8 bit 暫存器。此處所有指令都會去設置 conditional code 。
```
leaq S, D # D <- &S
```
load effective address ，也就是讀地址，沒有其它 size 的變種。
不會改變 conditional code ，也因此常常被借用去進行跟取地址無關的簡單算術運算，有各種神奇用法，僅要求 `D` 需為 register 。
```
imulq S # 有號全乘法
mulq S # 無號全乘法
idivq S # 有號除法
divq S # 無號除法
```
乘法將 `S` $\times$ `%rax` 之後放到 `%rdx`:`%rax` ( 高位放在 `%rdx`) 。
除法將商放在 `%rax` ，將餘數放在 `%rdx` 。
`cqto` 指令將 `%rax` sign extend 到 `%rdx`:`%rax` 。
### Conditional
conditional code 欄位
- CF : 無號數操作有 carry out
- ZF : 結果為 0
- SF : 結果為負數
- OF : overflow
```
cmp S1, S2 # S2-S1 但不存結果，只變更 conditional code
test S1, S2 # 做 AND 運算但不存結果，只變更 conditional code
```
此二指令一樣可以有 b, w, l, q 尾綴。
若 `S1`, `S2` 相等則 `cmp` 後 ZF 會被設為 1 。
可以藉由 `testq %rax, %rax` 來檢查 `%rax` 為 (大於)、(小於)或(等於) 0 。
通常不會直接讀 conditional code 的值，而會：
- conditional set a byte
- conditional jump
- conditional move
|指令|同義||條件|
|:-|:-:|:-|:-|
|`sete D` | `setz` | `D <- ZF`|
|`setne D` | `setnz` | `D <- ~ZF`|
|`sets D` || `D <- SF`|
|`setns D` || `D <- ~SF`|
||||
|`setg D` | `setnle` | `D <- ~(SF^OF)&~ZF` |大於|
|`setge D` | `setnl` | `D <- ~(SF^OF)` |大於等於|
|`setl D` | `setnge` | `D <- SF^OF` |小於|
|`setle D` | `setng` | `D <- (SF^OF)｜ZF` |小於等於|
||||
|`seta D` | `setnbe` | `D <- ~CF&~ZF` |大於|
|`setae D` | `setnb` | `D <- ~CF` |大於等於|
|`setb D` | `setnae` | `D <- CF` |小於|
|`setbe D` | `setna` | `D <- CF｜ZF` |小於等於|
`D` 的 1 個 byte 會被設為 1 或 0 。
中間那組為有號數使用，最後那組為無號數使用， a, b 代表 above 和 below 。
`sete` 是在查看 zero flag 的，被用來當作 set when equal
### Jump and Conditional jump
跳到某個 label
|指令|同義|條件||
|:-|:-:|:-|:-|
|`jmp Label` |||
|`jmp *Operand` ||| with addressing mode|
|||||
|`je Label` | `jz` | `ZF` |
|`jne Label` | `jnz` | `~ZF` |
|`js Label` || `SF` |
|`jns Label` || `~SF` |
|||||
|`jg Label` | `jnle` |||
|`jge Label`| `jnl` |||
|`jl Label` | `jnge` |||
|`jle Label`| `jng` |||
|||||
|`ja Label` | `jnbe` |||
|`jae Label`| `jnb` |||
|`jb Label` | `jnae` |||
|`jbe Label`| `jna` |||
後面幾個 postfix 的語意跟 conditional 的表相同。
assembler 和 linker 較常用的跳轉地址編碼方式是 PC-relative ，少數時候才使用 absolute address 。
### Conditional move
類似 MUX 的概念，直接計算出每個 branch 的結果，再依 condition 選擇其中一個結果。
```
cmove S, R
cmovne S, R
cmovs S, R
cmovns S, R
cmovg S, R
cmovge S, R
cmovl S, R
cmovle S,R
cmova S, R
cmovae S, R
cmovb S, R
cmovbe S, R
```
邏輯與前述相似。
在 conditional move 可以取代 conditional jump 的情況下，可以使用 cmov 來避免 instruction miss 的 penalty ，但這麼做也不一定會提高效能，甚至 cmov 會導致非法取值。
例如：
```c
int foo(int *p)
{
return p ? *p : 0;
}
```
此情境無法使用 conditional move，因為在 `p` 為 NULL 的情況下，`*p` 會 dereference a NULL pointer。
此外，假設有 C 程式碼：
```c
v = <test> ? <then> : <else>;
```
那麼在 `then` 或 `else` 很複雜的情況下，conditional jump 可能會更有效率，因為只需要做一邊的運算。
GCC 大多時候還是會選擇 conditional jump，只有在兩個分支都非常簡單時才會選用 conditional move。
### Loop
assembly 基本上都是用 jump 和 conditional jump 來實現各種 loop。
#### do-while
do...while loop 會被等價翻譯成：
```cpp
loop:
body
if (test_expr)
goto loop;
```
#### while
gcc 翻譯 while loop 有兩種可能的做法：
空間效率較好：
```cpp
goto test;
loop:
body
test:
if (test_expr)
goto loop;
```
時間效率較好：
如果 compiler 認為初始的 test expression 一定成立，它可以砍掉前面的 if statement
```cpp
if (!test_expr)
goto done;
do {
body
} while (test_expr);
done:
```
#### for
```cpp
for (init_expr; test_expr; update_expr)
body
```
在 body 內沒有 `continue` 的情況下，其等價於
```cpp
init_expr;
while (test_expr) {
body
update_expr;
}
```
### switch..case
當 case 很多時 (say >= 4)，switch...case 會用 jump table 來實現以提高效率，使得跳轉的速度與 case 的數量無關，即使有上百個 case 也只要訪問一次 jump table。
gcc 引入了一些 C extension 來實現 jump table，使用 `&&` prefix 來表示 instruction 的地址，並支持 computed `goto`。
### Procedure
抽象化的 function 稱為 procedure
- passing control (跳去執行另一段程式，結束後回到 return point)
- passing data (參數傳遞)
- memory management (函式內的區域變數)
### Stack
- `%rbp` 指向 stack 底部 (高位址)
- `%rsp` 指向 stack 的頂端 (低位址)
底部是 stack 開始的地方，頂端是最外面，stack 的量為 `%rbp - %rsp`。
```
push S # 把 S 存進 stack，修改 %rsp
pop D # 從 stack 讀資料到 D，並修改 %rsp
```
x86-64 通常是用 `pushq` 和 `popq`
```
call Label # push return point 並依據 Label 改 %rip (jump 到 Label)
call *Operand
ret # 以 %rip 為 destination 的 pop
```
> p.166 圖 3-27
在 x86 使用 pass by registers 最多可以傳 6 個參數，registers 的順序有規定
傳遞時需要使用 stack 的情況：
- 參數超過 6 個時需要 pass by stack
- 當傳遞一個 local variable 的 address 時 (`&x`)，需要把 local variable 放到 memory 才有地址。原先 local variable 可能完全使用 register 而根本沒放在 memory
- 某些 array 和 struct
使用 pass by stack 時每個參數都要 align 到 8 (if in x86-64)；注意到在第二種情況只是要把變數存到 stack，並非 pass by stack，不需要每個都 align 到 8，詳細可參考 p.172 圖 3-33。
---
procedure 的轉換之間 register contents 不會被覆蓋，也就是說 registers 在 procedure 之間是共享的。x86-64 採用了一組統一的 conventions：
- `%rbx`, `%rbp`, `$r12`~`%r15` 列為 ==callee-saved==，callee 必須在 return 時將它們回復原狀
- 除了 `%rsp` 和 callee-saved registers 以外的所有 registers 都為 ==caller-saved==，也就是 caller 要自己負責保管好 (負責 save) 它們，途中任何 procedure 都能隨意修改這些數值而不恢復
### 遞迴
```c
unsigned fac(unsigned n)
{
if (n <= 1)
return 1;
return fac(n - 1) * n;
}
```
使用 gcc -O1 編譯：
```cpp=
movl $1, %eax
cmpl $1, %edi
jbe .L5
pushq %rbx
movl %edi, %ebx
leal -1(%rdi), %edi
call fac
imull %ebx, %eax
popq %rbx
ret
.L5:
ret
```
注意到第 4, 9 行即在實現 callee-saved convention for `%rbx`。
若使用到 -O2 則會基於 tail recursion 直接砍掉 function call：
```cpp
movl $1, %eax
cmpl $1, %edi
jbe .L1
.L2:
movl %edi, %edx
subl $1, %edi
imull %edx, %eax
cmpl $1, %edi
jne .L2
.L1:
ret
```
### Array, Struct, Union
x86 的 addressing mode 設計是對 pointer arithmetic 很友善的
### GDB
> p.194
:::info
page pointer : 201
:::
## 第 5 章
### strlen
在一般的走訪字串的操作中，常見如下迴圈：
```c
for (int i = 0; i < strlen(s); i++) {
...
}
```
`strlen(s)` 是個 $O(n)$ 運算，編譯器會嘗試將其改成：
```c
int len = strlen(s);
for (int i = 0; i < len; i++) {
...
}
```
以避免每次 loop 都呼叫一次 $O(n)$，最終變成了 $O(n^2)$ 複雜度。
然而，若是迴圈裡有一些對於 `s` 的修改，編譯器可能就不知道 `strlen(s)` 的值是否改變，使得它放棄進行上述的優化，最終產生效能很差的 object code。
### 指標取值
```c
for (int i = 0; i < len; i++)
*dest = *dest + data[i];
```
這段程式碼反覆去讀寫 `dest` 所指到的位址，大量 memory access 導致了很差的效能。一個常見的優化方式為：
```c
int n = *dest;
for (int i = 0; i < len; i++)
n = n + data[i];
*dest = n;
```
引入一個暫時的變數來讓 access `dest` 位址的次數降低到讀、寫各一次。
然而，因為編譯器不知道 `dest` 和 `data` 是否有 memory aliasing 的情況，所以也可能會放棄這樣的優化。
### 現代處理器
- ICU, instruction control unit
- EU, execution unit
CPU 的性能參數：
- latency
- 完成某運算需要的時間
- issue time
- 連續完成兩個某運算的間隔時間
- 因為現代 pipeline 特性，這個值可能遠小於 latency
- capacity
- 能夠執行某運算的執行單元總數
在一般的 CPU 上，例如普通的家用 Intel CPU，加法、整數乘法、浮點乘法通常被認為是重要功能，所以 CPU 設計者會為這些運算在 low latency 和 high throughtput 方面做較多的優化。
throught put 大致上是 $\propto$ $\text{capacity}$, $\dfrac{1}{\text{issue time}}$，簡單運算例如加法會藉由增加 capacity，而複雜運算例如乘法會藉由降低 issue time 方式。
#### Loop
```c
for (int i = 0; i < sz; i++)
acc = acc * data[i];
```
`i++` 使用 CPU 中的加法器，而 `acc` 運算使用乘法器，即使在同一個 CPU 中也是可以平行執行的。
#### 2 $\times$ 1 unrolling
```c
for (int i = 0; i < sz; i += 2)
acc = acc * data[i] * data[i + 1];
if (sz & 1)
acc = acc * data[sz - 1];
```
loop unrolling 可以減少運算 `i` 的次數，但是因為這裡的效能瓶頸是在乘法上，因此做 unrolling 優化雖有改進但效果有限。注意到因為每個 `acc` 都在等上一個 `acc` 算完，所以這個乘法運算無法 pipeline。
#### 2 $\times$ 2 unrolling
```c
for (int i = 0; i < sz; i += 2) {
acc0 = acc0 * data[i];
acc1 = acc1 * data[i + 1];
}
if (sz & 1)
acc0 = acc0 * data[sz - 1];
acc0 = acc0 * acc1;
```
#### Reassociation
編譯器會嘗試對 operands 做一些交換和 divide-and-conquer 來運用 CPU 性能，但是因為浮點數沒有交換律，所以大多數 compiler 不會亂換浮點數運算的順序。
> 例如將 $a+b+c+d$ 改成 $(a+b)+(c+d)$
下例說明改變順序的強效，將 $2\times 1$ unrolling 提到的例子改變順序：
```diff
for (int i = 0; i < sz; i += 2)
- acc = acc * data[i] * data[i + 1];
+ acc = acc * (data[i] * data[i + 1]);
```
在這個情況下，因為 `data` 相乘不 depend on `acc` 所以在 update `acc` 時可以讓下一輪的 `data` 進乘法 pipeline。這顯然相較原先加速許多，overall 的 critical path 可以變成一半。
### 使用 gprof 進行 code profiling
> p.388
首先編譯程式
```
gcc -Og -pg xxx.c -o xxx
```
`-pg` 命令防止函式被 inline
```
./xxx
```
```
gprof xxx
```
:::info
page pointer :
:::
## 第 6 章 Storage
### RAM
DRAM 以電容儲存，因此容易被干擾，通常幾個 ms 就需要更新一次。
DRAM 有 $w$ 個 DRAM 單元，每個單元有 $d$ 個 supercell ，每個 supercell 存 1 bit 。
DRAM 單元是二維的， $d = r\times c\quad$ (row, column)
加強版：
- Fast Page Mode DRAM
- Extended Data Out DRAM
- Sychronous DRAM (SDRAM)
- Double Data-Rate Sychronous DRAM (DDR SDRAM)
- Video RAM
Nonvolatile Memory：
- Programmable ROM (PROM)
- Erasable Programmable ROM (EPROM)
- Flash Memory
- SSD
:::success
跳過 disk 的部份 p.407
:::
I/O bus 連接各種 I/O ，雖然比 system bus 和 memory bus 慢，但是相容性較佳。
使用 PCI bus 可以達成 CPU architecture independence ，目前被 PCI express 取代
> Universal Serial Bus (USB)
:::success
p.413 skip
:::
### SSD
SSD 中有 translation layer 和 flash memory，通常 SSD 的讀比寫更快。
- 不需要驅動機械構造，省電、更快速
- 貴
- 損耗問題
假定 flash memory 有 $B$ 個區塊，每個區塊有 $P$ 個 page。
- 以 page 為單位進行讀寫
- 只有在 page 對應的區塊整個被擦除之後才能寫，但是擦除一個塊之後裡面的每個 page 都能寫一次
- 如果區塊原本有資料的話需要先搬到其它塊暫存
- 大約擦除 100000 次之後，區塊就會磨損到無法使用
- 因為擦除和資料複製的耗時，SSD 的寫通常比讀慢一個數量級
廠商通常會在 translation layer 的邏輯中，盡量讓每個區塊的使用次數一樣多，以平均磨損情況，延長 SSD 壽命。
### Locality
- temporal locality
- 存取過又重複被存取到
- spatial locality
- 存取過後附近 (位址) 的變數也被存取到
### Cache
對於 memory space 範圍到 $M=2^m$ 的記憶體
- $S=2^s$ cache set
- $E$ cache line in each set
- Each line has a $B=2^b$-byte block
每個 block 包含：
- valid bit
- tag, $m-(b+s)$-bit
- block with $B$-byte
:::info
page pointer : 425
:::
## 第 7 章 Linking
Linking 的時機可以在：
- compile time
- load time
- run time
本章討論 Linux on x86-64，並以 ELF-64 目標格式為例。
pre processor $\to$ compiler $\to$ assembler $\to$ linker $\to$ loader
### Linker
主要做兩件事：
- symbol resolution
- relocation
基本上 linker 不太知道 computer architecture，相關的事務已由 compiler 和 assembler 完成。
### object file
可歸類為三種：
- Relocatable
- Excutable，可以直接搬到 memory 執行
- Shared，可以做 dynamic linking, loading
系統選擇：
- Windows 使用 PE, portable executable
- MacOS 使用 Mach-O
- Linux 使用 ELF, executable and linkable format
在 object file 中不為 .bss section 分配位置以節省空間，執行時才在 memory 分配
Symbol 的結構：
```c
/* $begin elfsymbol */
typedef struct {
int name; /* string table offset */
int value; /* section offset, or VM address */
int size; /* object size in bytes */
char type : 4, /* data, func, section, or src file name (4 bits) */
binding : 4; /* local or global (4 bits) */
char reserved; /* unused */
char section; /* section header index, ABS, UNDEF, */
/* or COMMON */
} Elf_Symbol;
/* $end elfsymbol */
```
`section` 紀錄該 symbol 在 ELF 中的哪個 section，另外有三個特殊的 pseudosection for relocatable object file
可以藉由 `readelf` 工具去看 ELF，例如：
:::spoiler 試玩
```
$ readelf -a ptxt.o
ELF 檔頭：
魔術位元組： 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
類別: ELF64
資料: 2 的補數，小尾序(little endian)
Version: 1 (current)
OS/ABI: UNIX - System V
ABI 版本: 0
類型: REL (可重定位檔案)
系統架構: Advanced Micro Devices X86-64
版本: 0x1
進入點位址： 0x0
程式標頭起點： 0 (檔案內之位元組)
區段標頭起點： 6856 (檔案內之位元組)
旗標： 0x0
Size of this header: 64 (bytes)
Size of program headers: 0 (bytes)
Number of program headers: 0
Size of section headers: 64 (bytes)
Number of section headers: 14
Section header string table index: 13
區段標頭：
[號] 名稱 類型 位址 偏移量
大小 全體大小 旗標 連結 資訊 對齊
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .text PROGBITS 0000000000000000 00000040
0000000000000eb3 0000000000000000 AX 0 0 1
[ 2] .rela.text RELA 0000000000000000 000014f8
0000000000000468 0000000000000018 I 11 1 8
[ 3] .data PROGBITS 0000000000000000 00000ef3
0000000000000000 0000000000000000 WA 0 0 1
[ 4] .bss NOBITS 0000000000000000 00000ef3
0000000000000000 0000000000000000 WA 0 0 1
[ 5] .rodata PROGBITS 0000000000000000 00000ef8
00000000000000af 0000000000000000 A 0 0 8
[ 6] .comment PROGBITS 0000000000000000 00000fa7
000000000000002c 0000000000000001 MS 0 0 1
[ 7] .note.GNU-stack PROGBITS 0000000000000000 00000fd3
0000000000000000 0000000000000000 0 0 1
[ 8] .note.gnu.propert NOTE 0000000000000000 00000fd8
0000000000000020 0000000000000000 A 0 0 8
[ 9] .eh_frame PROGBITS 0000000000000000 00000ff8
0000000000000158 0000000000000000 A 0 0 8
[10] .rela.eh_frame RELA 0000000000000000 00001960
00000000000000f0 0000000000000018 I 11 9 8
[11] .symtab SYMTAB 0000000000000000 00001150
00000000000002d0 0000000000000018 12 12 8
[12] .strtab STRTAB 0000000000000000 00001420
00000000000000d7 0000000000000000 0 0 1
[13] .shstrtab STRTAB 0000000000000000 00001a50
0000000000000074 0000000000000000 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
l (large), p (processor specific)
本檔案中沒有區段群組。
本檔案中沒有程式標頭。
本檔案沒有動態區段。
重定位區段 '.rela.text' at offset 0x14f8 contains 47 entries:
偏移量 資訊 類型 符號值 符號名稱 + 加數
0000000003b4 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
0000000003ca 001000000004 R_X86_64_PLT32 0000000000000000 strdup - 4
0000000003e8 000700000002 R_X86_64_PC32 0000000000000000 .rodata - 4
0000000003f0 001100000004 R_X86_64_PLT32 0000000000000000 fopen - 4
000000000439 001200000004 R_X86_64_PLT32 0000000000000000 fgets - 4
00000000044d 001300000004 R_X86_64_PLT32 0000000000000000 fclose - 4
000000000465 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
00000000048b 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
0000000004aa 000700000002 R_X86_64_PC32 0000000000000000 .rodata - 4
0000000004b2 001100000004 R_X86_64_PLT32 0000000000000000 fopen - 4
000000000512 001000000004 R_X86_64_PLT32 0000000000000000 strdup - 4
000000000557 000c00000004 R_X86_64_PLT32 00000000000001e4 str_hash - 4
00000000057b 001200000004 R_X86_64_PLT32 0000000000000000 fgets - 4
0000000005b0 000700000002 R_X86_64_PC32 0000000000000000 .rodata - 2
0000000005b5 001000000004 R_X86_64_PLT32 0000000000000000 strdup - 4
0000000005fa 000c00000004 R_X86_64_PLT32 00000000000001e4 str_hash - 4
000000000624 001300000004 R_X86_64_PLT32 0000000000000000 fclose - 4
000000000633 001400000004 R_X86_64_PLT32 0000000000000000 pthread_exit - 4
000000000652 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
00000000069c 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
0000000006de 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
000000000912 000f00000004 R_X86_64_PLT32 0000000000000000 malloc - 4
000000000bae 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000bce 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000c30 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000c50 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000c6d 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000c79 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000ca4 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000ccd 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000ced 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000cfd 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000d09 001800000004 R_X86_64_PLT32 0000000000000000 free - 4
000000000d3e 000700000002 R_X86_64_PC32 0000000000000000 .rodata - 1
000000000d48 001c00000004 R_X86_64_PLT32 0000000000000000 printf - 4
000000000d57 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 10
000000000d61 001c00000004 R_X86_64_PLT32 0000000000000000 printf - 4
000000000d68 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 2c
000000000d6d 001d00000004 R_X86_64_PLT32 0000000000000000 puts - 4
000000000dca 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 84
000000000dd4 001c00000004 R_X86_64_PLT32 0000000000000000 printf - 4
000000000e21 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 8f
000000000e2b 001c00000004 R_X86_64_PLT32 0000000000000000 printf - 4
000000000e71 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 9d
000000000e7b 001c00000004 R_X86_64_PLT32 0000000000000000 printf - 4
000000000ea7 000700000002 R_X86_64_PC32 0000000000000000 .rodata + 2c
000000000eac 001d00000004 R_X86_64_PLT32 0000000000000000 puts - 4
重定位區段 '.rela.eh_frame' at offset 0x1960 contains 10 entries:
偏移量 資訊 類型 符號值 符號名稱 + 加數
000000000020 000200000002 R_X86_64_PC32 0000000000000000 .text + 0
000000000040 000200000002 R_X86_64_PC32 0000000000000000 .text + a5
000000000060 000200000002 R_X86_64_PC32 0000000000000000 .text + 1e4
000000000080 000200000002 R_X86_64_PC32 0000000000000000 .text + 388
00000000009c 000200000002 R_X86_64_PC32 0000000000000000 .text + 637
0000000000c0 000200000002 R_X86_64_PC32 0000000000000000 .text + 8e1
0000000000e0 000200000002 R_X86_64_PC32 0000000000000000 .text + b65
000000000100 000200000002 R_X86_64_PC32 0000000000000000 .text + be3
000000000120 000200000002 R_X86_64_PC32 0000000000000000 .text + c82
000000000140 000200000002 R_X86_64_PC32 0000000000000000 .text + d12
The decoding of unwind sections for machine type Advanced Micro Devices X86-64 is not currently supported.
Symbol table '.symtab' contains 30 entries:
編號: 值 大小 類型 約束 版本 索引名稱
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS ptxt.c
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
5: 0000000000000000 165 FUNC LOCAL DEFAULT 1 mystrlen
6: 00000000000000a5 319 FUNC LOCAL DEFAULT 1 replace_endl
7: 0000000000000000 0 SECTION LOCAL DEFAULT 5
8: 0000000000000000 0 SECTION LOCAL DEFAULT 7
9: 0000000000000000 0 SECTION LOCAL DEFAULT 8
10: 0000000000000000 0 SECTION LOCAL DEFAULT 9
11: 0000000000000000 0 SECTION LOCAL DEFAULT 6
12: 00000000000001e4 420 FUNC GLOBAL DEFAULT 1 str_hash
13: 0000000000000388 687 FUNC GLOBAL DEFAULT 1 ptxt_init
14: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND _GLOBAL_OFFSET_TABLE_
15: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND malloc
16: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND strdup
17: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND fopen
18: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND fgets
19: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND fclose
20: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND pthread_exit
21: 0000000000000637 682 FUNC GLOBAL DEFAULT 1 ptxt_distance
22: 00000000000008e1 644 FUNC GLOBAL DEFAULT 1 dp_generate_ops
23: 0000000000000b65 126 FUNC GLOBAL DEFAULT 1 dp_free_table
24: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND free
25: 0000000000000be3 159 FUNC GLOBAL DEFAULT 1 dp_destroy
26: 0000000000000c82 144 FUNC GLOBAL DEFAULT 1 ptxt_destroy
27: 0000000000000d12 417 FUNC GLOBAL DEFAULT 1 print_result
28: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND printf
29: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND puts
本檔案中沒有區段資訊。
Displaying notes found in: .note.gnu.property
Owner Data size Description
GNU 0x00000010 NT_GNU_PROPERTY_TYPE_0
Properties: x86 feature: IBT, SHSTK
```
:::
### duplicate symbol
Linux linker 按照下列規則來處理 duplicate symbol：
- functions 和 initialized global variables 是 strong symbols
- uninitialized global variable 是 weak symbols
- 不允許 duplicate strong symbol
- 如果有 strong symbol 和 weak symbol 同名，選擇 strong symbol
- 假設 **proga.c** 裡面有 `int x = 3`、**progb.c** 裡面有 `int x`，那麼在 **progb.c** 裡面指派 `x = 2` 會導致 **proga.c** 裡的 `x` 也被改成 2。
- 甚至不同 type 的同名符號也會被認為是 duplicate，導致無意間指派 float 給 char 之類的錯誤
- 如果有 duplicate weak symbol，隨便選一個
可以在 gcc 編譯時使用 `-fno-common` 來回報此錯誤，或是藉由初始化所有 global variable 來避免此問題
### static library
standard functions 會被分成一些集合，例如 ISO C99 有 libc 和 libm 等等
#### before 1：
交給 compiler 去辨識程式中的 standard functions
**pros**
- 對 programmer 便利
**cons**
- 當 standard functions 數量龐大時為 compiler 帶來負擔
- 每次更新 standard functions 時 compiler 也得更新
#### before 2：
把 standard functions 的集合做成一個 relocatable .o 檔
**pros**
- 不再影響 compiler 實作
**cons**
- 每個 executable file 都包含了整個集合，為 memory 和 disk 帶來負擔
- 每次更新 standard functions 時都要 recompile 整份 files
#### after：
引入 static library，把每個集合編譯成獨立的 module，並且當程式引用 standard function 時只會複製該 function，不會複製整個 module
**pros**
- 降低空間消耗
**cons**
- 編譯時需要注意順序
在 Linux 中，static library 以 archive 格式儲存，副檔名為 .a。可以藉由 `ar` command 來建立 static library。
```
$ gcc -c sum.c -o sum.o
$ ar rcs sum.a sum.o
$ gcc -c main.c -o main.o
$ gcc -static main.o ./sum.a -o main
$ ./main
```
如果 libraries 的相依關係為：
```graphviz
digraph {
rankdir = "TB";
foo [label="foo.c"];
x [label="libx.a"];
y [label="liby.a"];
z [label="libz.a"];
foo -> x;
foo -> y;
x -> z;
}
```
使用 gcc 編譯時必須將被依賴的 library 放在右邊
```
gcc foo.c libx.a liby.a libz.a -o foo
```
如果在上述的例子中，**libz.a** 的某些 function 也依賴於 **libx.a**，那便要如此編譯：
```
gcc foo.c libx.a liby.a libz.a libx.a -o foo
```
### relocate
assembler 會生成 relocation entry，讓之後的 linker 知道該如何對 symbol 做 relocate
```c
/* $begin elfrelo */
typedef struct {
int offset; /* offset of the reference to relocate */
int symbol : 24, /* symbol the reference should point to */
type : 8; /* relocation type */
} Elf32_Rel;
/* $end elfrelo */
```
ELF 定義了 32 種 relocation type
### Executable
### Dynamic linked shared library
:::info
page pointer : 485
:::
## 第 8 章
### Exceptions
檢測到事件發生時，會經由 exception table 跳到特定的 handler 。 handler 處理完之後有三種可能：
- 返回當前指令繼續執行
- 返回後從下個指令開始執行
- 中止該 process
每個 exception 都有 unique and nonegative 的 exception number ，此 number 可能由 CPU architechture 提供或 OS 提供。
通常由 CPU 分配的：
- divided by 0
- page fault
- overflow
- ...
通常由 OS 分配的：
- system call
- I/O signal
| 類別 | 原因 |||
|:-:|:--|:-:|:-:|
| interrupt | from I/O signal | asynchronous | 返回下一條指令|
| trap | 故意生成的 | synchronous | 返回下一條指令|
| fault | 可能可以恢復 | synchronous | 可能會返回當前指令|
| abort | 不可恢復的錯誤 | synchronous | 不返回|
#### Interrupt
:::warning
`ctrl + c` 產生的 interrupt 和 timer interrupt 是一樣的嗎？
:::
#### Trap
使用 system call 之前透過 trap 來產生 user process 和 kernel 之間的接口
#### Fault
- 可恢復 $\to$ 返回
- 不可恢復 $\to$ abort
例如 page fault ，將 page 從 disk 讀到 memory 之後就解決問題、可返回繼續執行了。
#### Abort
通常是硬體損壞、故障造成的
---
C 語言可以使用 `syscall` (trap instruction) 進行系統呼叫，但通常可以用 C standard library 包裝後的函數，例如 `write()` 之於 `printf()` 。
Arguments of system call is passed by registers rather than stack.
### Processes
抽象化
user mode 不可執行 privileged instruction
Linux 藉由 `/proc` 提供 user mode 取得 kernel 資訊、資料結構
context
- register contents
- program counter
- user stack
- status register
- kernel stack
- kernel 相關 data structure
Unix system function 遇到錯誤時通常會返回 -1 並設置 global variable `errno` 。做成例外處理包裝函式可以簡化程式碼。
#### fork()
除了 PID 以及 physical address 之外幾乎完全相同，包括打開的 file descriptor 。
return 兩次：
- 在 parent process 回傳子程序的 PID (非零)
- 在 child process 回傳 0
`fork()` 之後父子的執行順序不被保證
#### 回收 child process
> man waitpid
- 使用 `waitpid()` 來回收 (reap) 已終止的 child processes
- 已終止的 child process 為 zombie process 直到被 parent 回收
- 若 parent 先終止則 child 會被 kernel 中的 init 收養
init 為 PID = 1 的 process ，它不會被終止。
`waitpid()` ：等待自己的 child 終止，用法複雜
```c
pid_t waitpid(pid_t pid, int *wstatus, int options);
```
> The value of pid can be:
> < -1 meaning wait for any child process whose process group ID is equal to the absolute value of pid.
>
> -1 meaning wait for any child process.
>
> 0 meaning wait for any child process whose process group ID is equal to that of the calling process at the time of the call to waitpid().
>
> \> 0 meaning wait for the child whose process ID is equal to the value of pid.
`wait()` ：簡化版
children 回收的順序不固定，除非指定 pid 依序回收。
#### execve()
```c
int execve(const char *pathname, char *const argv[],
char *const envp[]);
```
執行 `pathname` 對應的 executable file
stack 圖見 p 522.
```graphviz
graph {
rankdir = LR;
}
```
### Signals
> man 7 signal
A signal is a small message that notifies a process that an event of some type has occurred in the system. [[source]](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/15-ecf-signals.pdf)
Defined in <signal.h> in C standard [C99 7.14]：
- `SIGABRT`
- `SIGFPE`
- `SIGILL`
- `SIGINT`
- `SIGSEGV`
- `SIGTERM`
其它定義在 POSIX 標準並由 Linux 所支援的：
- `SIGTSTP`
- `SIGALRM`
- `SIGKILL`
- `SIGCHLD`
- ...
待處理信號 pending signal
同類型的重複 pending signal 會被丟棄不會排隊
process group 可以用 `getpgrp()` 取得 PGID
pgid 預設為 parent 的 pid
發 signal ：
- 使用正數會送給指定 pid 的 process
- 使用負數會送給 group 中的所有 processes
- 使用 0 會送給 caller process 所屬 group 中的所有 processes
在 shell 使用 `ctrl + c` 會送 SIGINT 給前景 process group 中的所有 processes
接收到 signal 後的行為：
當 process $P$ 從 kernel mode 回到 user mode 時 (例如 system call 結束或 context switch) ，kernel 會檢查是否有 nonblocked 的 pending signal ，若有則選一個 signal 接收，若無則繼續下一道指令。
- terminate
- ignore
- execute signal handler
每種 signal 會有對應的 default action 。
> If the signal signum is delivered to the process, then one of the following happens:
> * If the disposition is set to SIG_IGN, then the signal is ignored.
> * If the disposition is set to SIG_DFL, then the default action associated with the signal (see signal(7)) occurs.
> * If the disposition is set to a function, then first either the disposition is reset to SIG_DFL, or the signal is blocked (see Portability below), and then handler is called with argument signum. If invocation of the handler caused the signal to be blocked, then the signal is unblocked upon return from the handler.
> The signals SIGKILL and SIGSTOP cannot be caught or ignored.
---
applications 可以用 `sigprocmask()` 來 block 或 unblock 特定信號，等 unblock 之後再處理的意思
```c
/* Prototype for the glibc wrapper function */
int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);
```
`how` 值：
- SIG_BLOCK
- SIG_UNBLOCK
- SIG_SETMASK
signal handler 應
- 盡可能簡單
- 使用安全的函式，其中唯一能安全產生輸出的方法為 `write()`
- 有些函數會更改 `errno` ，因此需要先存下原本的 `errno` 並在 handler 要返回時恢復原值
- block 所有 signals 防止 global data structure 被中途改變
- 在 global variable 使用 `volatile` ，因其可能被外部更改
- 使用 `sig_atomic_t`
> 關於「安全的函式」可見： [signal-safety(7) — Linux manual page](https://man7.org/linux/man-pages/man7/signal-safety.7.html)
```shell
$ gcc -pthread signal1.c csapp.c -o signal1
$ ./signal1
Hello from child 10057
Hello from child 10058
Hello from child 10059
Handler reaped child 10057
Handler reaped child 10058
^Z
[1]+ 停止 ./signal1
$ ps t
PID TTY STAT TIME COMMAND
5036 pts/0 Ss 0:00 /usr/bin/bash
10056 pts/0 T 0:00 ./signal1
10059 pts/0 Z 0:00 [signal1] <defunct>
10166 pts/0 R+ 0:00 ps t
```
因為重複的 pending signal 會被丟棄不會排隊，所以不應該使用 signal 來 count 。
為了 portability ，建議使用 `sigaction()` 來取代 `signal()` ，其有包裝版本 `Signal()` ，用法與 `signal()` 相同。
在 `fork()` 之前先 block `SIGCHLD` 信號可以避免一些 race condition (可能在 parent 要對 child 操作之前， child 就已經結束了) 。
> p.542
---
使用
```c
while (!pid) {}
```
會造成 busy waiting 的浪費，取而代之或許可使用
```c
while (!pid)
pause();
```
然而若在這兩行之間收到 interrupt ，那麼就再也無法從 `pause()` 醒來。一個好的解法是使用 `sigsuspend()`
### Nonlocal jump
```c
int setjmp(jmp_buf env);
int sigsetjmp(sigjmp_buf env, int savesigs);
void longjmp(jmp_buf env, int val);
void siglongjmp(sigjmp_buf env, int val);
```
> setjmp() and sigsetjmp() return 0 when called directly; on the "fake" return that occurs after longjmp() or siglongjmp(), the nonzero value specified in val is returned.
使用 `jmp_buf` 型態的 `env` 保存環境狀態，包括：
- program counter
- stack pointer
- register contents
`setjmp()` 的回傳值不能做 assignment
`longjmp()` 跳到最近初始化 `env` 的那個 `setjmp()`
`setjmp()` return 很多次， `longjmp()` 不 return
sig__ 版本是用來做 signal handling 的
### 監控 Processes 的工具
- `strace` ：印出使用的 system call ，若程式碼經過 static 編譯則可以看到更純淨的結果
- `ps` ： report a snapshot of the current processes
- `top` ： (我覺得 `htop` 更好用
## 第 9 章 Virtual Memory
在有 virtal addressing 的系統上，CPU 存取 virtual address，但此地址在真正到達 main memory 之前會被 MMU 翻譯成 physical address。
address space 是地址的集合，如果 address space 中的整數是連續的，則稱為 linear address space。
### Cache disk with virtual memory
為方便稱呼，將 L1, L2, L3 cache 稱為 SRAM cache，將 disk 在 main memory 的 page cache 稱為 DRAM cache。
由於 DRAM 慢 SRAM 十倍而 disk 慢 DRAM 數萬倍，因此 DRAM cache miss 的懲罰是非常昂貴的。因為此懲罰非常昂貴，因此作業系統在此通常用上非常精密複雜的演算法來做 page 替換。
main memory 中會 maintain 一份 page table 來紀錄 page 映射，page table entry 包括 valid bit 及 physical address，而 table entry 的 index 就是 page 在 disk 上的位置。
> p.564 圖
發生 page fault 會發 signal，如第 8 章所述。
### Memory management with virtual memory
上面舉的都是使用 main memory cache disk 的例子，在這種情況下 virtual memory space 會比 physical memory space 大，但 virtual memory space 在其它情形也可能大於 physical memory space。
virtual memory 可以用於記憶體管理，通常帶來幾個好處：
- 簡化 linking
- 在 virtual memory 的情況下，每個 process 的 memory layout 格式可以相同。在 Linux 上 64-bit addressing space 的 `.text` 區段總是從 `0x400000` 開始。
- 簡化 loading
- Linux 提供 `mmap()` system call 允許 application 自己做 memory map。
- 簡化 share
### Protection with virtual memory
提供 virtual address，使得存取位址是否合法變得非常容易辨認。page table entry 上可以增加一些額外的 bit 來紀錄該位址的存取/寫入是否允許。
### 地址翻譯
1. CPU 將 virtual address 傳給 MMU
2. MMU 生成對應 page table entry 的地址，並向 SRAM cache / main memory access
3. MMU 造出 physical address 並傳給 SRAM cache / main memory
4. SRAM cache / main memory 將 data 傳給 CPU
在第 2 步驟之後若 page table 中該 entry 的 valid bit 是 0，那 MMU 就觸發了 exception，交由 kernel 的 handler 處理。
通常 SRAM cache 當中是紀錄 physical address，因為地址翻譯發生在它之前。
### TLB
translation lookaside buffer
由於 MMU 每次都要去查 page table entry，因此在 MMU 端加入一個比 L1 cache 更近的 TLB 以快取 page table entry。
TLB 紀錄了 TLB index 及 TLB tag，兩者合起來的長度為 page number 的 bit 數。其邏輯大致與 cache 相同，都是使用 modular 的方式 hash。
```flow
st=>start: CPU sent an address to MMU
TLB=>condition: TLB hit?
PT=>operation: Look-up the page table in memory
page=>condition: Is the page in memory
(valid bit == 1)?
fault=>operation: Page fault
Load the page from disk
cache=>condition: Cache hit?
mem=>operation: Read the data from memory
get=>operation: MMU gets data at the address
e=>end: MMU returns the data to CPU
st->TLB->page->cache->get->e
TLB(yes)->page
TLB(no)->PT
PT->page
page(yes)->cache
page(no)->fault
fault->mem
cache(yes)->get
cache(no)->mem
mem->get
```
:::info
context switch 時 TLB 會置換嗎？我推測是需要
:::
### 多級 page table
在 virtual space 很大的情況下，page table 也會佔據非常大的空間。可能的解決方法是保存更小的 level 1 page table 於 main memory，並將完整的 level 2 page table 放在 disk 中。
> p.572 圖
藉由 TLB 的幫助，多級 page table 並不會比單級 page table 慢很多。
### Intel Core i7 example
`CR3` register 紀錄 level 1 page table 的起始位置
實際上的 page table entry 還會紀錄一些包括 access permission 的其它資訊：
- 唯讀或是可讀寫
- 一般 user 是否有訪問權限
- 相關的修改是否馬上寫回 cache
- 是否為 global page
- 能不能從這裡取 instruction (避免有人惡意將 data 當成 instruction 使用而導致 buffer overflow 之類)
......等等。
通常會精巧設計 bit 數，使得可以同時發 virtual page number 給 TLB 和發 virtual page offset 給 L1 cache，那麼在 TLB hit 之後就可以馬上回傳地址了。
### Linux vm
#### 結構
Linux 為每個 process 維護一個 virtual address space
> p.580 圖 9-26
kernel 為每個 process 維護一個 task_struct，每個 task_struct 中有一個 entry 指向 mm_struct，這個 struct 描述了 virtual memory 目前的狀態。而 mm_struct 又指向一條 lists of vm_area_structs。
> p.580 圖 9-27
mm_struct contains：
- `pgd` 指向 level 1 page table
- `mmap` 指向 vm_area_struct
vm_area_struct contains：
- `vm_start` area 在 virtual memory 的起始地址
- `vm_end` The first byte after our end address within vm_mm
- `vm_prot` 權限紀錄
- `vm_flags`
- `vm_next` linked-list 用
> task_struct 在 `<linux/sched.h>` 中
> mm_struct 及 vm_area_struct 都在 `<linux/mm_types.h>` 中
#### Page fault
觸發 page fault 之後會依序進行：
1. Is the address valid?
- 檢查該地址是否在某個 vm_area_struct 的 vm_start 和 vm_end 範圍之內
- If not, 觸發 segmentation fault 並 abort 此 process
- 實際上搜尋 list of vm_area_structs 的成本很高 ($O(n)$)，所以 Linux 是建一棵樹來搜尋
2. 訪問是否合法？
- 權限檢查
3. 這個操作是合法的，選擇 memory 中的一個 page 並取而代之
### Linux memory map
一個 object 可以被 map 到 virtual memory 的一個 area，作為 shared object 或 private object。
private object 使用 copy-on-write 技術
- 很多人共享資源時只維護一份資源，將該資源標為 read-only，並給所有人到該資源的指標
- 當有人想修改時，觸發 fault，接著 signal handler 複製一份副本讓它修改
copy-on-write 技術避免了不必要時的副本，節省了 memory 的用量。
### fork() and execve()
當某 process 呼叫 `fork()` 時，kernel 會複製原有的 mm_struct、vm_area_struct、page table 給新 process。並把兩個 process 中的每個 page 都標記為 read-only，當之後有 process 想寫時用 copy-on-write。
`execve()` 要做的事：
1. 刪除原先的 vm_area_struct
2. 為新 program 創建 vm_area_struct
3. map shared objects
4. 設置 program counter
### user-space mmap()
> p.586 圖 9-32
```c
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags,
int fd, off_t offset);
int munmap(void *addr, size_t length);
```
> man mmap
嘗試撰寫練習題 9.5：
```c
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
/* read txt */
int txt = open(argv[1], O_RDONLY);
if (txt == -1)
exit(1);
struct stat st;
fstat(txt, &st);
size_t sz = st.st_size;
void *start = mmap(NULL, sz, PROT_READ, MAP_PRIVATE, txt, 0);
/* write to stdout */
fwrite(start, sz, 1, stdout);
munmap(start, sz);
close(txt);
return 0;
}
```
略過很多 return value 的檢查
### allocator
> http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/lectures/19-malloc-basic.pdf
藉由 `brk()` 和 `sbrk()` 來控制 heap 大小。
allocator 的設計圍繞在幾個問題上：
- 如何紀錄空的 block
- 要配哪個空 block 出去
- 空 block 通常會比需要的空間來得大，剩餘部份該如何處理
- 如何處理剛被釋放的 block
> 需要配置的空間稱為 payload
分為：
- explicit allocator
- 例如 `malloc()` and `free()` in C
- implicit allocator
- 通常高階語言都是使用此類
#### fragmentation
- internal fragmentation
- 為了 alignment 或其它原因，配置一個比要求更大的空間
- external fragmentation
- 長期使用之後 memory 不再有大塊的連續空間可分配
Placement policy：
- first fit
- next fit
- best fit
#### Keeping track of free blocks
幾種常見的方式：
- implicit list
- 在 header 紀錄每個 block 的長度，這 implicitly 形成了一條 list
- explicit list
- 用 linked list (實際上就是用 pointer) 連接每個空的 block
- segregrated free list
- buddy system
- blocks sorted by size
#### implicit list
一個 block 前面通常會有一段 header 來描述 block size
兩個被釋放的連續 blocks 可以合併 (coalescing)，假設 A, B 兩塊相連
- 假設 B 是空的，那麼釋放 A 時就可以修改 A 的 block size 紀錄，並刪除 B 的 header
- 假設 A 是空的，那麼釋放 B 之後，我們一樣是要去修改 A 的 header，可是因為 singly linked 的結構，使得當我們要去找到 A 的 header 時要重新走訪 list
- 一個解決方式是在 block 後面加 footer，釋放 B 的時候從其 header 位址往前 access 一個 word，就能得知 block A 的資訊，不過這個方法會使管理的空間成本稍微上升
通常釋放之後不會馬上合併，以避免合併之後又馬上分割的情況
#### explicit list
使用 doubly-linked list 串起每個空的 block，走訪的成本從走過所有 blocks 降到走過所有空的 blocks。此外 list 的順序也更加自由，假設數字代表位址，在 list 上可以是：$1\to 4\to 2\to 3$ 這樣的順序，而不一定要像 $1\to 2\to 3\to 4$ 這樣遵從 address order。
#### segregrated free list
一開始就將空間切成一些 size class 等價類，可能是每個 class 各一條 list，例如 $\{1\}$, $\{2\}$, $[3, 7]$, $\{8, 9, 10\}$。那麼當需要配置 size 6 時就去 $[3,7]$ class 找，找不到再往上找。
假設 size 6, 7 的 blocks 已經用完了，那麼在被請求 size 6 時有兩種 policy：
- 給出一個在 class $\{8,9,10\}$ 的 block
- 將例如 size 8 的 block 切成 size 6 的 block 和 size 2 的 block 放到各自的 class，再給出 size 6 的 block
> 關於 glibc 可以參考：[glibc 的 malloc/free 實作](https://hackmd.io/@sysprog/c-memory?type=view#glibc-%E7%9A%84-mallocfree-%E5%AF%A6%E4%BD%9C)
==buddy system== 是一種特例，每種 size 都固定為 power of 2，其缺點為若需求都是 5, 9, 17 這種 $2^n+1$ 的數，buddy system 就會面臨嚴重的 internal fragmentation 問題。
### Garbage collection
Garbage collector 將 memory 視為一張 directed graph，節點被分為 root node 和 heap node。如果有 heap node 無法從某個 root node 到達，那麼它就是 unreachable，即為 garbage。
C 語言很難做 garbage collection，因為有時候 pointer 會用 integer 的形式存放，這會使 collector 認為該空間已經 unreachable。
## 第 10 章 System I/O
> 搭配 http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/lectures/16-io.pdf
### File
一個 Linux file 就是 $m$ 個 byte 的 sequence
$$
B_0, B_1,\dotsc,B_k,\dotsc, B_{m-1}
$$
所有 I/O 包括網路和 disk 都被抽象成 file ，可以進行：
- open
- read / write
- close
- current file position 設定
每個 process 都 maintain 一份 descriptor table ，建立時都已預設打開 0, 1, 2
- 0 為 stdin
- 1 為 stdout
- 2 為 stderr
file type :
- regular file
- 包括 text file 和 binary file ，但 kernel 不進行區分
- directory
- 一組 link ，每個 link 接到另一個 file
- 任何 directory 至少有 `.` 和 `..` link
- socket
- named pipe
- symbolic link
- character and block device
#### open()
> man open
```c
int open(const char *pathname, int flags);
int open(const char *pathname, int flags, mode_t mode);
```
其功能為將 file 轉換為對應的 file descriptor 數字。
`flags` :
- O_RDONLY
- O_WRONLY
- O_RDWR
- O_APPEND
- ...
`mode` 為文件的權限設定
使用 `close()` 關閉。
#### read and write
```c
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);
off_t lseek(int fd, off_t offset, int whence);
```
`read()` 和 `write()` 有 short count 的問題
`lseek()` 用於調整 current file position
### RIO
CSAPP 提供
- unbuffered
- buffered
#### unbuffered
```c
ssize_t rio_readn(int fd, void *usrbuf, size_t n);
ssize_t rio_writen(int fd, void *usrbuf, size_t n);
```
#### buffered
```c
/* Persistent state for the robust I/O (Rio) package */
#define RIO_BUFSIZE 8192
typedef struct {
int rio_fd; /* descriptor for this internal buf */
int rio_cnt; /* unread bytes in internal buf */
char *rio_bufptr; /* next unread byte in internal buf */
char rio_buf[RIO_BUFSIZE]; /* internal buffer */
} rio_t;
void rio_readinitb(rio_t *rp, int fd);
ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n);
ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen);
```
`rio_readinitb()` 用於初始化，將 `fd` 和 buffer `rp` 連接起來。
`rio_readnb()` 讀取最多 `n` 個 byte 。
`rio_readlinb()` 從一行讀取最多 `maxlen` - 1 個 byte ，最後一個位置放 NULL。 (?
:::spoiler `rio_read()` 函式
```c
/*
* rio_read - This is a wrapper for the Unix read() function that
* transfers min(n, rio_cnt) bytes from an internal buffer to a user
* buffer, where n is the number of bytes requested by the user and
* rio_cnt is the number of unread bytes in the internal buffer. On
* entry, rio_read() refills the internal buffer via a call to
* read() if the internal buffer is empty.
*/
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
int cnt;
while (rp->rio_cnt <= 0) { /* refill if buf is empty */
rp->rio_cnt = read(rp->rio_fd, rp->rio_buf, sizeof(rp->rio_buf));
if (rp->rio_cnt < 0) {
if (errno != EINTR) /* interrupted by sig handler return */
return -1;
} else if (rp->rio_cnt == 0) /* EOF */
return 0;
else
rp->rio_bufptr = rp->rio_buf; /* reset buffer ptr */
}
/* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */
cnt = n;
if (rp->rio_cnt < n)
cnt = rp->rio_cnt;
memcpy(usrbuf, rp->rio_bufptr, cnt);
rp->rio_bufptr += cnt;
rp->rio_cnt -= cnt;
return cnt;
}
```
:::
\
對於 application 來說 `rio_read()` 和 Linux `read()` 有相同語意。
### File Metadata
```c
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
int stat(const char *pathname, struct stat *statbuf);
int fstat(int fd, struct stat *statbuf);
int lstat(const char *pathname, struct stat *statbuf);
```
`stat()` 和 `fstat()` 分別用 path 和 fd 來查詢一個 file 的資訊。 `lstat()` 則主要用於 symbolic link 。
struct stat 定義如下：
```c
struct stat {
dev_t st_dev; /* ID of device containing file */
ino_t st_ino; /* Inode number */
mode_t st_mode; /* File type and mode */
nlink_t st_nlink; /* Number of hard links */
uid_t st_uid; /* User ID of owner */
gid_t st_gid; /* Group ID of owner */
dev_t st_rdev; /* Device ID (if special file) */
off_t st_size; /* Total size, in bytes */
blksize_t st_blksize; /* Block size for filesystem I/O */
blkcnt_t st_blocks; /* Number of 512B blocks allocated */
/* Since Linux 2.6, the kernel supports nanosecond
precision for the following timestamp fields.
For the details before Linux 2.6, see NOTES. */
struct timespec st_atim; /* Time of last access */
struct timespec st_mtim; /* Time of last modification */
struct timespec st_ctim; /* Time of last status change */
#define st_atime st_atim.tv_sec /* Backward compatibility */
#define st_mtime st_mtim.tv_sec
#define st_ctime st_ctim.tv_sec
};
```
> https://github.com/lattera/glibc/blob/master/sysdeps/unix/sysv/linux/bits/stat.h
:::spoiler 範例小程式
```c
#include "csapp.h"
int main(int argc, char **argv)
{
struct stat stat;
char *type, *readok;
/* $end statcheck */
if (argc != 2) {
fprintf(stderr, "usage: %s <filename>\n", argv[0]);
exit(0);
}
/* $begin statcheck */
Stat(argv[1], &stat);
if (S_ISREG(stat.st_mode)) /* Determine file type */
type = "regular";
else if (S_ISDIR(stat.st_mode))
type = "directory";
else
type = "other";
if ((stat.st_mode & S_IRUSR)) /* Check read access */
readok = "yes";
else
readok = "no";
printf("type: %s, read: %s\n", type, readok);
exit(0);
}
```
試用
```shell
$ ./statcheck ~/code
type: directory, read: yes
```
:::
### Directory
```c
DIR *opendir(const char *name);
DIR *fdopendir(int fd);
```
返回值為指向 directory stream 的指標， stream 是對 ordered list 的抽象。
```c
struct dirent *readdir(DIR *dirp);
struct dirent {
ino_t d_ino; /* Inode number */
off_t d_off; /* Not an offset; see below */
unsigned short d_reclen; /* Length of this record */
unsigned char d_type; /* Type of file; not supported
by all filesystem types */
char d_name[256]; /* Null-terminated filename */
};
```
```c
int closedir(DIR *dirp);
```
### File Sharing
kernel 使用三個 data structure 來表示被打開的 file ：
- desciptor table
- file table : 所有 process 共享
- v-node table : 所有 process 共享
> [vnode](https://man.openbsd.org/vnode.9)
當 `refcnt` 為 0 時該 file table 會被刪除
:::warning
file pos 是指 offset 還是 path ？如果是 offset ，那麼所謂 processes 共享是何意？
:::
可能有不同 fd 對應到同一個 file 的情形，例如使用 `open()` 打開兩次
### I/O
I/O redirection 可以透過 `dup2()` 實現
standard I/O streams :
```c
#include <stdio.h>
extern FILE *stdin;
extern FILE *stdout;
extern FILE *stderr;
```
型別為 `FILE` 的 stream 是一種對 fd 和 stream buffer 抽象
`fflush()` 用於清除緩衝區
#### I/O 守則
- 盡量使用 standard I/O 以增進效率 (更少的 system call) 與避開 short count 等麻煩的錯誤
- 在 signal handler 必須使用 Unix I/O
- 取得 metadata 必須使用 Unix I/O
- 不要使用帶 parser 的 read (例如 `scanf()`) 來讀 binary file ，比如說裡面可能有很多 `0xa`
跟 network 有關的輸入輸出會在第 11 章探討
## 第 11 章 Network Programming
client-server transaction
1. client 發 request 給 server
2. server 讀取 request 並處理要求
3. server 發送 response 給 client
4. client 處理收到的訊息
TCP/IP 訂定的 network byte order 是 big endian ，轉換 byte order 的函式：
```c
uint32_t htonl(uint32_t hostlong);
uint16_t htons(uint16_t hostshort);
uint32_t ntohl(uint32_t netlong);
uint16_t ntohs(uint16_t netshort);
```
n 代表 net ， h 代表 host
---
IP address 的整數表示和 dotted-decimal format 轉換：
$$
\mathtt{0x8002c2f2} \iff \mathtt{128.2.194.242}
$$
```c
int inet_pton(int af, const char *src, void *dst);
const char *inet_ntop(int af, const void *src,
char *dst, socklen_t size);
```
`af` 用於選擇 network address structure，必須是 `AF_INET` 或 `AF_INET6`；這些函式的 IP address 整數表示總是以 network byte order
n 同樣代表 net；p 代表 representation，也就是指 ddd.ddd.ddd.ddd 字串
- `inet_pton` with `AF_INET` 的情境下， `dst` 為 pointer to `struct in_addr`
```c
/* Internet address. */
typedef uint32_t in_addr_t;
struct in_addr
{
in_addr_t s_addr;
};
```
> <netinet/in.h>
- `inet_pton` with `AF_INET6` 的情境較為複雜，`dst` 為 pointer to `struct in6_addr`，詳細可參考 `man inet_pton`
---
nslookup 工具程式可由網址查詢 IP address。
port 有 16 bit，可表示範圍為 0 ~ 65535
```
ddd.ddd.ddd.ddd:<port>
```
每一個 connection 都唯一映射到一組 socket pair `(cliaddr:cliport, servaddr:servport)`
> cat /etc/services 可以看所有 services
:::success
若命名前後綴有 `in` 都是表示 internet
:::
### socket
socket 對 Linux 來說就是有對應 descriptor 的 opened file。
於 **<sys/socket.h>** 中之結構體如下：
```c
/* Structure describing a generic socket address. */
struct sockaddr
{
__SOCKADDR_COMMON (sa_); /* Common data: address family and length. */
char sa_data[14]; /* Address data. */
};
```
展開 macro `__SOCKADDR_COMMON` 後為：
```c
struct sockaddr
{
sa_family_t sa_family;
char sa_data[14];
};
```
```c
/* POSIX.1g specifies this type name for the `sa_family' member. */
typedef unsigned short int sa_family_t;
```
---
client 和 server 透過 `socket()` 來創造 socket descriptor
> man socket
```c
#include <sys/types.h> /* See NOTES */
#include <sys/socket.h>
int socket(int domain, int type, int protocol);
```
1. `domain` 選擇一種 protocol family，最常見的就是填入 `AF_INET` 和 `AF_INET6`
2. `type` 指定 communication semantics
3. `protocal` 在選定的 `domain` 下選一種特定的 protocol，一般來說每個 protocol family 中都只有一個 protocal，此時可以填入 0，不過也有一些例外，詳見 `man 5 protocols`
最終 `socket()` (如果沒有錯誤) 會返回一個打開的 socket fd，不過 read/write 權限還不會開啟。
### connect()
client 使用 `connect()` 來連 server
```c
int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
```
- `connect()` 嘗試與 socket address 為 `addr` 的 server 建立 Internet connection
- `connect()` 會 blocking 直到連接成功或發生錯誤
- 如果成功的話那 `sockfd` 就可以讀寫了
### bind(), listen(), accept()
`bind()`, `listen()`, `accept()` 都是由 server 所使用。
```c
int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
```
> bind() assigns the address specified by ++addr++ to the socket referred to by the file descriptor ++sockfd++.
```c
int listen(int sockfd, int backlog);
```
`listen()` 將 `sockfd` 轉化成 listening socket
> The ++backlog++ argument defines the maximum length to which the queue of pending connections for ++sockfd++ may grow.
```c
int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);
```
server 透過 `accept()` 來等待來自 client 的 `connect()`，並且會 blocking 在 `accept()`，直到成功時返回一個已連線的 descriptor。client 的 socket address 會被填在 `addr`。
listenfd 通常只會被建一次，例如 3 是 listenfd，如果有人來 connect，那 `accept()` 可能會回傳 connfd 4 專門服務該 clientfd，而 3 還是那個 listenfd。
:::success
`listen()` 有點像是建立一個 listenfd 但不會開始聽，要用 `accept()` 才會開始聽
:::
### getaddrinfo()
> man getaddrinfo
```c
#include <sys/types.h>
#include <sys/socket.h>
#include <netdb.h>
int getaddrinfo(const char *node, const char *service,
const struct addrinfo *hints,
struct addrinfo **res);
```
`node` 可以是 domain name 或 IP address with dotted-decimal format；`service` 可以是 service name 或 port number，如果填入 service name，例如 http，它會依此產生對應的 port number。
> Either ++node++ or ++service++, but not both, may be NULL.
回傳一個或多個 `struct addrinfo` 在 `res`，`*res` 指向一個 linked list 資料結構，其中每個 `addrinfo` 都可以用於 call `bind()` 或 call `connect()`。
> There are several reasons why the linked list may have more than one ++addrinfo++ structure, including: the network host is multihomed, accessible over multiple protocols (e.g., both AF_INET and AF_INET6); or the same service is available from multiple socket types (one SOCK_STREAM address and another SOCK_DGRAM address, for example). Normally, the application should try using the addresses in the order in which they are returned. The sorting function used within getaddrinfo() is defined in RFC 3484; the order can be tweaked for a particular system by editing /etc/gai.conf (available since glibc 2.5).
> p.657 圖 11-15
```c
/* Structure to contain information about address of a service provider. */
struct addrinfo
{
int ai_flags; /* Input flags. */
int ai_family; /* Protocol family for socket. */
int ai_socktype; /* Socket type. */
int ai_protocol; /* Protocol for socket. */
socklen_t ai_addrlen; /* Length of socket address. */
struct sockaddr *ai_addr; /* Socket address for socket. */
char *ai_canonname; /* Canonical name for service location. */
struct addrinfo *ai_next; /* Pointer to next in list. */
};
```
`getaddrinfo()` 中的 `hints` 只有 `flags`, `family`, `socktype` 和 `protocol` 能設置，其餘都要設為 0 或 NULL，它會自動完成。
使用這個函式的優點是讓我們在寫 client 和 server 程式碼的時候可以不用去管 protocol 是什麼，直接把 `ai_family`, `ai_addrlen` 傳給 `socket()`、把 `ai_addr` 和 `ai_protocol` 傳給 `connect()` 和 `bind()` 就好。
### getnameinfo()
```c
int getnameinfo(const struct sockaddr *addr, socklen_t addrlen,
char *host, socklen_t hostlen,
char *serv, socklen_t servlen, int flags);
```
與前一個函式相反，將 struct sockaddr 轉成 host 和 service 字串
:::info
page pointer : 658
:::
## 第 12 章
> 搭配 http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/lectures/23-concprog.pdf
### Concurrent program
並行的實現方式：
- Processes
- I/O multiplexing
- Threads
### Process-Based
```graphviz
digraph {
server[label="server 聆聽 request"];
client[label="client 發 request"];
accept[label="server 接受 request 、連接 client fd"];
fork[label="server fork()"];
p1[label="parent 關閉 client fd"];
p2[label="parent 繼續聆聽 request"];
c1[label="child 停止聆聽"];
c2[label="child 為 client 服務"];
server -> client -> accept -> fork;
fork -> p1 -> p2;
fork -> c1 -> c2;
}
```
獨立定址，缺點是 interprocess communication 的高成本
### I/O Multiplexing
[`select()`](https://man7.org/linux/man-pages/man2/select.2.html) 函式處理 `fd_set` 的集合
$$
(b_{n-1},\dotsc, b_1, b_0)\in \{0,1\}^n
$$
```c
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
void FD_CLR(int fd, fd_set *set);
int FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set);
```
- 使用 `FD_ZERO`, `FD_SET`, `FD_CLR`, `FD_ISSET` 來設定和檢查
- `FD_CLR` 設定指定的 bit fd 為 0
- `FD_ISSET` check if set
- `FD_SET` 設定指定的 bit fd 為 1
- `FD_ZERO` 全設為 0
`select()` 會一直 block 直到有 listenfd 或 stdin 準備好可讀
- read set
- ready set
I/O multiplexing 可以做成 event-driven ， event 會使 flow 往前走
I/O multiplexing 版本使用單一 process ，易於使用 gdb 等工具，另外不需要 IPC 所以效率更佳；缺點是程式碼較長且無法利用多核處理器。
### Thread-Based
> [相對於 process](https://hackmd.io/ymg-HRGqQLqRVKznvELO4g?view#Processes)
thread context
- thread ID (TID)
- (local) stack
- stack pointer
- program counter
- register contents
- status register
有獨立的 stack 但不會阻止其它 thread 存取 (透過指標等方式)
threads 共享的部份：
- 整個 virtual address
- 程式碼
- heap
- shared library 程式碼
- data
- opened file
:::warning
opened file or opened file descriptor?
:::
在本機執行
```c
/* $begin sharing */
#include "csapp.h"
#define N 3
void *thread(void *vargp);
char **ptr; /* global variable */ // line:conc:sharing:ptrdec
int main()
{
int i;
pthread_t tid;
char *msgs[N] = {"Hello from foo", "Hello from bar", "Kappa"};
ptr = msgs;
for (i = 0; i < N; i++)
Pthread_create(&tid, NULL, thread, (void *) i);
Pthread_exit(NULL);
}
void *thread(void *vargp)
{
int myid = (int) vargp;
static int cnt = 0; // line:conc:sharing:cntdec
printf("[%d]: %s (cnt=%d)\n", myid, ptr[myid],
++cnt); // line:conc:sharing:stack
return NULL;
}
/* $end sharing */
```
每次結果可能有所不同
```shell
$ ./sharing
[0]: Hello from foo (cnt=1)
[1]: Hello from bar (cnt=2)
[2]: Kappa (cnt=3)
$ ./sharing
[0]: Hello from foo (cnt=1)
[2]: Kappa (cnt=3)
[1]: Hello from bar (cnt=2)
```
注意 `cnt` 受到 `static` 的影響！
---
threads 不像 processes 那樣有父子關係，大家都是對等的，因此每個人都可以殺死每個人
- `pthread_create()`
- `pthread_self()` 取得 TID
- `pthread_join()` main thread 等待 peer thread 終止，但它的邏輯不像是 `wait()` ，它只能等待一個 thread
- `pthread_detach()` 分離的 thread 不會被別的 thread 殺死
A thread is either joinable or detached.
終止方法：
- 返回時自動終止
- `pthread_exit()` terminate calling thread ，不會 return
- 如果是 main thread 呼叫會等待所有 peer thread 終止，然後終止該 process
- 有 thread 呼叫 `exit()` 時終止該 process
- 透過 `pthread_cancel()` 終止其它 thread
### Semaphore
```c
#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem);
int sem_post(sem_t *sem);
```
> sem_wait() decrements (locks) the semaphore pointed to by sem. If the semaphore's value is greater than zero, then the decrement proceeds, and the function returns, immediately. If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts the call.
> sem_post() increments (unlocks) the semaphore pointed to by sem. If the semaphore's value consequently becomes greater than zero, then another process or thread blocked in a sem_wait(3) call will be woken up and proceed to lock the semaphore.
### Concurrent program
- $\mathrm{sequential}\cap \mathrm{concurrent} = \emptyset$
- $\mathrm{parallel}\subseteq \mathrm{cocurrent}$
#### thread-safe
一個函式是 thread-safe ***iff*** 在 multi-thread 情境總是能產生正確結果。
thread-unsafe 的例子：
- 不保護 shared variable
- 在多個 invocations 之間保持狀態的函式，如 `rand()`
- 回傳指向靜態變數的指標的函式
- 使用 thread-unsafe 函式的函式
解決方法：
- 重寫 function
- 在 thread-unsafe function 外面加 lock 然後重新包裝
:::warning
書中表示 `rand()` 是 thread-unsafe，但是 man 寫它是 thread-safe 和 MT-safe
:::
#### reentrance
> [reentrancy wiki](https://en.wikipedia.org/wiki/Reentrancy_(computing))
如果函式執行到一半被 context switch，此時重新呼叫一次仍然安全，該函式即為 reentrance。
:::warning
reentrant 和 thread-safe 的關聯？
:::
不可使用 shared variable，如果函式的 parameters 沒有指標，並且沒有使用靜態變數和全域變數，那該函式就是 reentrant，但若包含指標就不容易判定有沒有觸及 shared variable。
standard library 中 `_r` postfix 的函式就是 reentrant 版本。
#### Deadlock
lock 順序需要跟 unlock 順序相反以避免 deadlock
Sign in with Wallet
Connect another wallet