讀 CS:APP 簡中版

搭配服用 http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

辭典

>> 收縮點此 <<

繁體中文		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/接口

第 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 位元
$U M a x$	`UINT_MAX`	0xFFFFFFFF
$T M i n$	`INT_MIN`	0x80000000
$T M a x$	`INT_MAX`	0x7FFFFFFF

A portable printf() may be implemented by macro, such as

    /* portable printf */
    int32_t x;
    uint64_t y;
    printf("x = %PRId32, y = %PRIu64\n", x, y);

有無號數轉換

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

{T 2 U}_{w} (x) = {\begin{cases} x, & x \geq 0 \\ x + 2^{w}, & x < 0 \end{cases}

e.g.

{T 2 U}_{16} (- 12345) = 65536 + - 12345 = 53191

For an unsigned number

u

{U 2 T}_{w} (u) = {\begin{cases} u, & u \geq {TMax}_{w} \\ u - 2^{w}, & u < {TMax}_{w} \end{cases}

unsigned 和 signed 運算的結果會被 implicitly 轉換成 unsigned

在定義 INT_MIN 時最好寫成 -INTMAX - 1

一個數字被擴展時會使用 sign extension ，例如：

short sx = -12345;
unsigned uy = sx;
printf("uy = %u:", uy);
show_bytes(&uy, sizeof(unsigned));

在我的電腦 (little endian) 上的執行結果是：

uy = 4294954951: c7 cf ff ff

這是我所用的 show_bytes() 函式

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 逕行截斷，例如：

    int x = 65534;
    short sh = x;
    printf("%hd\n", sh);

會得到 -2 而不是 32766 。

size_t 是無號的， ssize_t 是有號的

加法

無號數加法類型為模加法，無號數發生 overflow 不會終止程式 (不會發 signal) 。

在 unsigned 情境下，令

s = x + y

：

$s$ overflow
$⟺$
$s < x$
$⟺$
$s < y$

而因為模加法的特性，使無號數形成 Abelian group 。

在 signed 的情況下，令

s = x + y

：

$s$ positive overflow
$⟺$
$(x > 0)$ &&
$(y > 0)$ &&
$(s \leq 0)$
$s$ negative overflow
$⟺$
$(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 。

使用 malloc(sizeof(x) * n) 時須小心 argument 的 overflow 問題，雖然一般使用上不會溢出，但是得要防範惡意輸入。若傳入值 n 與 input 有關，則呼叫 malloc() 前應先行檢查以避免安全漏洞。

除法

速度甚至比乘法要慢得多，若有效能考量應避免使用。

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

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 會導致非法取值。

例如：

int foo(int *p)
{
    return p ? *p : 0;
}

此情境無法使用 conditional move，因為在 p 為 NULL 的情況下，*p 會 dereference a NULL pointer。

此外，假設有 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 會被等價翻譯成：

loop:
    body
    if (test_expr)
        goto loop;

while

gcc 翻譯 while loop 有兩種可能的做法：

空間效率較好：

    goto test;
loop:
    body
test:
    if (test_expr)
        goto loop;

時間效率較好：
如果 compiler 認為初始的 test expression 一定成立，它可以砍掉前面的 if statement

    if (!test_expr)
        goto done;
    do {
        body
    } while (test_expr);
done:

for

    for (init_expr; test_expr; update_expr)
        body

在 body 內沒有 continue 的情況下，其等價於

    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 都能隨意修改這些數值而不恢復

遞迴

unsigned fac(unsigned n)
{
    if (n <= 1)
        return 1;
    return fac(n - 1) * n;
}

使用 gcc -O1 編譯：












	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：

	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

page pointer : 201

第 5 章

strlen

在一般的走訪字串的操作中，常見如下迴圈：

    for (int i = 0; i < strlen(s); i++) {
        ...
    }

strlen(s) 是個

O (n)

運算，編譯器會嘗試將其改成：

    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        ...
    }

以避免每次 loop 都呼叫一次

O (n)

，最終變成了

O (n^{2})

複雜度。

然而，若是迴圈裡有一些對於 s 的修改，編譯器可能就不知道 strlen(s) 的值是否改變，使得它放棄進行上述的優化，最終產生效能很差的 object code。

指標取值

    for (int i = 0; i < len; i++)
        *dest = *dest + data[i];

這段程式碼反覆去讀寫 dest 所指到的位址，大量 memory access 導致了很差的效能。一個常見的優化方式為：

    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

capacity

\frac{1}{issue time}

，簡單運算例如加法會藉由增加 capacity，而複雜運算例如乘法會藉由降低 issue time 方式。

Loop

    for (int i = 0; i < sz; i++)
        acc = acc * data[i];

i++ 使用 CPU 中的加法器，而 acc 運算使用乘法器，即使在同一個 CPU 中也是可以平行執行的。

2
$\times$ 1 unrolling

    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

    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 提到的例子改變順序：

    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

page pointer :

第 6 章 Storage

RAM

DRAM 以電容儲存，因此容易被干擾，通常幾個 ms 就需要更新一次。

DRAM 有

w

個 DRAM 單元，每個單元有

d

個 supercell ，每個 supercell 存 1 bit 。

DRAM 單元是二維的，

d = r \times c

(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

跳過 disk 的部份 p.407

I/O bus 連接各種 I/O ，雖然比 system bus 和 memory bus 慢，但是相容性較佳。

使用 PCI bus 可以達成 CPU architecture independence ，目前被 PCI express 取代

Universal Serial Bus (USB)

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

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 的結構：

/* $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，例如：

試玩

$ 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 的相依關係為：

使用 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

/* $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

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

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 終止，用法複雜

    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()

       int execve(const char *pathname, char *const argv[],
                  char *const envp[]);

執行 pathname 對應的 executable file

stack 圖見 p 522.

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]

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 之後再處理的意思

    /* 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

$ 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

使用

    while (!pid) {}

會造成 busy waiting 的浪費，取而代之或許可使用

    while (!pid)
        pause();

然而若在這兩行之間收到 interrupt ，那麼就再也無法從 pause() 醒來。一個好的解法是使用 sigsuspend()

Nonlocal jump

       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 來紀錄該位址的存取/寫入是否允許。

地址翻譯

CPU 將 virtual address 傳給 MMU
MMU 生成對應 page table entry 的地址，並向 SRAM cache / main memory access
MMU 造出 physical address 並傳給 SRAM cache / main memory
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。

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 之後會依序進行：

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 是建一棵樹來搜尋
訪問是否合法？
- 權限檢查
這個操作是合法的，選擇 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() 要做的事：

刪除原先的 vm_area_struct
為新 program 創建 vm_area_struct
map shared objects
設置 program counter

user-space mmap()

p.586 圖 9-32

#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：

#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 實作

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}, \dots, B_{k}, \dots, 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

    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

    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

ssize_t rio_readn(int fd, void *usrbuf, size_t n);
ssize_t rio_writen(int fd, void *usrbuf, size_t n);

buffered

/* 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。 (?

rio_read() 函式

/*
 * 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

#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 定義如下：

           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

範例小程式

#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);
}

試用

$ ./statcheck ~/code
type: directory, read: yes

I/O

I/O redirection 可以透過 dup2() 實現

standard I/O streams :

    #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

client 發 request 給 server
server 讀取 request 並處理要求
server 發送 response 給 client
client 處理收到的訊息

TCP/IP 訂定的 network byte order 是 big endian ，轉換 byte order 的函式：

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 轉換：

0 x 8002 c 2 f 2 ⟺ 128.2 .194 .242

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

/* 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

若命名前後綴有 in 都是表示 internet

socket

socket 對 Linux 來說就是有對應 descriptor 的 opened file。

於 <sys/socket.h> 中之結構體如下：

/* 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 後為：

struct sockaddr
  {
    sa_family_t sa_family;
    char sa_data[14];
  };

/* 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

#include <sys/types.h>          /* See NOTES */
#include <sys/socket.h>

int socket(int domain, int type, int protocol);

domain 選擇一種 protocol family，最常見的就是填入 AF_INET 和 AF_INET6
type 指定 communication semantics
protocal 在選定的 domain 下選一種特定的 protocol，一般來說每個 protocol family 中都只有一個 protocal，此時可以填入 0，不過也有一些例外，詳見 man 5 protocols

最終 socket() (如果沒有錯誤) 會返回一個打開的 socket fd，不過 read/write 權限還不會開啟。

connect()

client 使用 connect() 來連 server

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 所使用。

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.

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.

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。

listen() 有點像是建立一個 listenfd 但不會開始聽，要用 accept() 才會開始聽

getaddrinfo()

man getaddrinfo

#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

/* 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()

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 字串

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

獨立定址，缺點是 interprocess communication 的高成本

I/O Multiplexing

select() 函式處理 fd_set 的集合

(b_{n - 1}, \dots, b_{1}, b_{0}) \in {0, 1}^{n}

    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

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

opened file or opened file descriptor?

在本機執行

/* $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 */

每次結果可能有所不同

$ ./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

#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

$sequential \cap concurrent = \emptyset$
$parallel \subseteq cocurrent$

thread-safe

一個函式是 thread-safe iff 在 multi-thread 情境總是能產生正確結果。

thread-unsafe 的例子：

不保護 shared variable
在多個 invocations 之間保持狀態的函式，如 rand()
回傳指向靜態變數的指標的函式
使用 thread-unsafe 函式的函式

解決方法：

重寫 function
在 thread-unsafe function 外面加 lock 然後重新包裝

書中表示 rand() 是 thread-unsafe，但是 man 寫它是 thread-safe 和 MT-safe

reentrance

reentrancy wiki

如果函式執行到一半被 context switch，此時重新呼叫一次仍然安全，該函式即為 reentrance。

reentrant 和 thread-safe 的關聯？

不可使用 shared variable，如果函式的 parameters 沒有指標，並且沒有使用靜態變數和全域變數，那該函式就是 reentrant，但若包含指標就不容易判定有沒有觸及 shared variable。

standard library 中 _r postfix 的函式就是 reentrant 版本。

Deadlock

lock 順序需要跟 unlock 順序相反以避免 deadlock

讀 CS:APP 簡中版

辭典

第 1 章

In Unix, everything is file.

並行

第 2 章

有無號數轉換

加法

乘法

除法

第 3 章 Machine-Level Programming

Intel 用詞

Registers (整數)

Instructions

Conditional

Jump and Conditional jump

Conditional move

Loop

do-while

while

for

switch..case

Procedure

Stack

遞迴

Array, Struct, Union

GDB

第 5 章

strlen

指標取值

現代處理器

Loop

2 × 1 unrolling

2 × 2 unrolling

Reassociation

使用 gprof 進行 code profiling

第 6 章 Storage

RAM

SSD

Locality

Cache

第 7 章 Linking

Linker

object file

duplicate symbol

static library

before 1：

before 2：

after：

relocate

Executable

Dynamic linked shared library

第 8 章

Exceptions

Interrupt

Trap

Fault

Abort

Processes

fork()

回收 child process

execve()

Signals

Nonlocal jump

監控 Processes 的工具

第 9 章 Virtual Memory

Cache disk with virtual memory

Memory management with virtual memory

Protection with virtual memory

地址翻譯

TLB

多級 page table

Intel Core i7 example

Linux vm

結構

Page fault

Linux memory map

fork() and execve()

user-space mmap()

allocator

2
$\times$ 1 unrolling

2
$\times$ 2 unrolling