# CS:APP CH9 筆記
contributed by < `zhu849` >

## CS:APP 課程錄影章節
* L17 - Virtual Memory:Concepts
* L18 - Virtual Memory:Systems
* L19 - Dynamic Memory Allocation:Basic Concepts
* L20 - Dynamic Memory Allocation: Advanced Concepts

## 9.0 Abstract
* 虛擬記憶體主要的三個能力：
1. 將實體記憶體當作硬碟地址位置的快取，在實體記憶體只保留 active areas，根據不同需要在硬碟和實體記憶之間雙向傳輸資料
2. 為每個 process 提供統一的地址空間，簡化管理
3. 保護每個 process 的地址空間不被其他 process 破壞
* 章節對於虛擬記憶體會從兩個角度切入：
1. 虛擬記憶體如何工作
2. 應用程式如何使用和管理虛擬記憶體

## 9.1 Physical addressing & Virtual addressing
* 計算機系統的尋址模式主要有 physical addressing 和 virtual addressing
### physical addressing
* 執行過程
1. CPU 載入指令，生成一個有效的物理位址(PA)
2. 透過 memory bus 傳送給實體記憶體
3. 實體記憶體收到位址後，拿取目標位址的記憶體內容傳回給 CPU
4. CPU 將內容存放在一個暫存器內
* 早期的 PC 都是使用這種方式，現今有些微控制器或是超級電腦也是用這種方式尋址

### virtual addressing
* 執行過程
1. CPU 載入指令後生成一個虛擬位址(VA)來存取實體記憶體
2. 虛擬位址透過 Memory Management Unit(MMU) 做 address translation 轉換成物理位址
3. 實體記憶體收到位址後，拿取目標位址的記憶體內容傳回給 CPU
4. CPU 將內容存放在一個暫存器內
* 現代處理器使用尋址方式
* Memory Management Unit(MMU) 是 CPU 晶片上的硬體單元，利用存放在實體記憶體的查詢表來轉換虛擬位址
* 這個查詢表由作業系統所管理
* 為了達到 address translation 除了需要這個硬體外也需要作業系統的搭配

## 9.2 Address Space
* 地址空間：是一個非負整地址的有序集合，如果地址空間中整數是連續的又稱「線性地址空間」，entry 編號如 $\{0,1,2,...\}$
* 虛擬地址空間：CPU 從一個有 $N=2^n$ 個地址的地址空間生成虛擬地址，地址空間大小是由表示最大位址需要的位元數 $n$ 決定的，entry 編號如 $\{0,1,2,...,N-1\}$
* 物理地址空間：對應到系統中實體記憶體的 $M$ 個 byte，且 $M$ 不要求為 2 的冪次，entry 編號如 $\{0,1,2,...,M-1\}$

## 9.3 Virtual Memory as a Tool for Caching
* 概念上，虛擬記憶體是由 N 個連續 byte 的單元組成的陣列存放在硬碟內，每個 byte 有唯一的 virtual address 作為 index 去搜索陣列
* 和其他儲存器架構相同，最小傳輸單元定為一個 block，而虛擬記憶體的塊稱為 virtual page(VP)，實體記憶體被切割的塊稱作 physical page(PP)又可以別稱為 page frame
* 虛擬記憶體分成三種狀態:
1. unallocated:還沒被虛擬記憶體系統分配的空間，block 內沒有任何資料且在硬碟上不佔有任何空間
2. cached:該 page 目前正被存放到實體記憶體上
3. uncached:該 page 目前還沒被存放到實體記憶體上


### 9.3.1
* 使用 SRAM 當作 CPU 和實體記憶體的高速快取，並且用 DRAM 當作虛擬記憶體系統的快取，兩者的概念是相似的
* 因為 DRAM 和 SRAM 速度的差異，所以 DRAM cache 的 miss penalty 較 SRAM cache 來得大，也因為這些問題所以 virtual page 往往很大(通常是 4KB~2MB)
* miss 後的替換策略也是需要探討的議題，因為替換錯誤造成的 penalty 也相當高，因此 OS 對 DRAM cache 使用了更複雜的替換演算法
* 因為對硬碟存取時間很長，所以 DRAM cache 都是使用 write-back 的方法，而非 write-through
* //TODO:write-back 與 write-through

### 9.3.2
* 虛擬記憶體需要有方法來判定 VP 是否存在於 DRAM 快取中某個地方，如果 hit 則要再去找存在哪個 physical page 上；如果 miss 則要去選擇出一個 victim page 替換
* 上述的 page fault 功能是由一系列軟硬體組成： OS 軟體, MMU 的 address translation, page table 的資料結構
* page table 的功能是將 VP 映射到 PP 上，每次 address translation 轉換時都會讀取 page table
* OS 負責維護 page table 內容，和 DRAM 跟硬碟之間 page 的傳送
* page table 結構
* 假設每個 PTE 是由一個 vaild bit 和一個 n 位的位址組成
* valid bit：為 1 DRAM 中相對應的位址存有 PP 的起始位址，如果為 0 則表示這個 virtual page 還沒被分配

### 9.3.3
* 考慮讀取被包含在 VP2 內容的過程
1. 利用 vitrual address 當作 index 得知 PTE 2 的位址
2. page valid 被設為 1，可以得知 VP2 有被存到實體記憶體內
3. 使用 PTE 中的 physical address 來讀取實體記憶體的資料

### 9.3.4
* DRAM cache miss 稱之為 page fault
* 考慮一個 CPU 想要使用 VP3 的內容
1. address translation 硬體從實體記憶體讀取 PTE 3
2. 從 valid bit 得知 VP3 沒有在 cache 內，觸發 page fault
3. page fault exception 觸發 kernel 內的 page fault exception handler
4. page fault exception handler 在快取內選擇一個 victim page(假設這裡選擇的是 VP4)
5. VP4 內容若有修改過則被寫回硬碟，否則可以直接丟棄
6. 將硬碟 VP3 的內容複製到 PP3 的位置
7. 更新 PTE3 的內容
8. page fault exception handler return 然後再執行一次導致 page fault 的指令
9. 重新將 virtual address 傳送到 address translation 內
10. address translation 硬體能夠正常處理這個 virtual address
* 在硬碟和 DRAM 傳送 page 的過程稱之為 swapping 或 paging
* 直到最後逼不得已才選擇 victim page 做置換的策略稱之為 demand paging

### 9.3.5
* malloc 和 page table 結構的關係：使用 malloc 指令後，VP5 是在硬碟上被創造並更新 PTE 5，指向它

### 9.3.6
* 局部性對於虛擬記憶體的效能有很大的影響，維持良好局部性能夠使虛擬記憶體發揮良好
* working set/resident set：局部性保證在某個任意時刻，程式會在某個 active page set 上執行
* 如果 working set 大小超出實體記憶體的大小，導致 page fault 頻繁發生，但是 CPU 實際效能卻不佳，稱之 thrashing
:::info
**Counting page faults**
可以使用 Linux 中的 getrusage 函式監控 page faults 的數量和資訊
:::

## 9.4 Virtual Memory as a Tool for Memory Management
* 在早期的系統中(e.g. DEC PDP-11/70)所支援的是一個比實體記憶體還小的虛擬地址空間，即使在這情況下仍是一個良好的機制
* 作業系統實際上給每個 process 一個獨立的 page table，且多個 virtual page 可以映射到同一個 physical page
* VM 簡化了 linking 和 loading 和程式碼跟資料的共享，以及應用程式的記憶體分配
* Simplifying linking：獨立的地址空間允許每個 process 的 memory image 能夠有相同格式無論 code 和 data 放在實體記憶體的哪個位置。這表示可執行文件對於其他部分(e.g. text section)是獨立於實體記憶體內的
* Simplifying loading：能夠更容易的將可執行檔和共享文件載入記憶體。新的 process 載入時，虛擬記憶體要將其 text 和 data section 載入並分配 VP，並修改其 PTE 的指標，等到實際要用到時才會載入到實體記憶體內
* Simplifying sharing：獨立的 address space 讓作業系統有一致的方法管理 user processes 和作業系統的共享空間。每個程序都有自己私有的 code, data ,stack, heap 等，這些空間就是宣告 VP 後不讓它映射到實體記憶體上
* Simplifying memory allocation：當程序用 malloc 要求額外的 heap 空間時，作業系統會給定一個數字(假設是 k)表示連續 k 個連續的 VP，然後將此映射到實體記憶體上任意 k 個 PP ，且 PP 可以隨機分散在實體記憶體上

:::info
**Memory Mapping**
將一組連續的 Virtual page 映射到任意的位置稱之為 memory mapping，linux 內提供一個函式 mmap 能夠讓應用程式自己做記憶體的映射
:::

## 9.5 VM as a Tool for Memory Protection
* 現代計算機系統對於記憶體的存取控制
* 不應該讓 user program 修改其 read-only code
* 不應該讓 user program 存取 kernel code 和 kernel data
* 不應該讓 process 存取其他 process 私有的記憶體空間
* 不能隨意的修改共享的虛擬記憶體空間，除非有經由 system call 進行 explicit interprocess communication
* 透過在 PTE 增加幾個 bit 做存取控制
* 如果某條指令違反這個存取限制條件，CPU 會觸發保護警告傳給 kernel 中的 exception handler，linux 上稱之為 segmentation fault

## 9.6 Address Translation
* 該小節會用到的符號、代稱
* address translation 是由 N 個 element 的虛擬地址空間和 M 個 element 的物理地址空間在做映射，其映射函數定義為
#### MMU 如何利用 page table 來實現映射
* CPU 中有一個控制暫存器 Page Table Base Register(PTBR)，用來指向目前使用的 page table
* n 位的虛擬位址包含兩個部分：p 位元的 virtual page offset 和 (n-p) 位元的 virtual page number(VPN)。MMU 會利用 VPN 選擇適當 PTE 將 page table entry 中的 PPN 和 VPN 做出其對應關係。VPN 和 PPN 的 offset 是相同的，都是指在某個 page 內的偏移量
* page hit 硬體執行過程
1. 處理器生成虛擬記憶體位址並將其傳送給 MMU
2. MMU 產生 PTE address 向快取/主記憶體要求該 address 的資料
3. 快取/主記憶體將 PTE 傳回給 MMU
4. MMU 生成實體記憶體位址並將其傳給快取/主記憶體要求資料
5. 快取/主記憶體返回要求的資料給處理器

* page miss 硬體執行過程
1. 處理器生成虛擬記憶體位址並將其傳送給 MMU
2. MMU 產生 PTE address 向快取/主記憶體要求該 address 的資料
3. 快取/主記憶體將 PTE 傳回給 MMU
4. MMU 檢查到 PTE 中的 valid bit 為0，MMU 觸發 exception，傳送 CPU 的控制信號到作業系統 kernel 中做處理
5. fault handler 選擇實體記憶體中的 victim page，如果該 page 被修改過則寫回硬碟
6. fault handler 將新的 page 放進實體記憶體中且將 PTE 更新
7. fault handler 回到原來的 process 再次執行造成 page fault 的指令，重新回到第一步執行就會是 page hit 的情形了


### 9.6.1
* 在同時具有虛擬記憶體和 SRAM 快取的系統內，應該使用實體位址訪問 SRAM 快取
* 多個 process 的 VP 同時共享快取，且快取不需要處理存取保護問題，因為存取權限的檢查是由 MMU 在做 address translation 過程的一部分
* page table entry 是可以快取的

### 9.6.2
* 因為每次 CPU 生成一次虛擬位址，MMU 就必須再查一次 PTE 讓虛擬位址轉成實體位址，多存取一次記憶體最差情況約會耗費數十數百個 cycle clock，如果將 PTE 放置在 SRAM L1 記憶體內做快取可以將耗費降低到 1~2 cycle clock
* 所以在 MMU 中加入一個 PTE 的快取稱為 Translation Lookaside Buffer(TLB)
* TLB 是虛擬位址的快取，每一列中存放 TBLT, TLBI, VPO 三種內容，TLBI 根據 TLB 數量決定(若有 $2^t$ 個 TLB entry 則用 t 個 bit 去表示)，剩餘部分的位元為 TLB Tag(TLBT)
* TLB Hit 過程
1. CPU 生成虛擬記憶體位址
2. MMU 用 VPN 到 TLB 做查詢
3. MMU 從 TLB 拿到對應的 PTE
4. MMU 將虛擬位址轉換成實體位址送到快取/記憶體請求資料
5. 快取/主記憶體返回要求的資料給 CPU


* TLB Miss 過程
1. CPU 生成虛擬記憶體位址
2. MMU 用 VPN 到 TLB 做查詢，發現 TLB 中並沒有快取這個 page
3. MMU 將 PTEA 送到快取/記憶體請求 PTE
4. 快取/主記憶體將 PTE 資料更新到 TLB
5. MMU 將虛擬位址轉換成實體位址送到快取/記憶體請求資料
6. 快取/主記憶體返回要求的資料給 CPU

### 9.6.3
* Multi-level page 使用階層結構的 page table 來壓縮 page table
* 這種方法減少記憶體使用的兩種理由
* 因為如果 level-1 page 是 NULL 則 level-2 page 根本不存在，在典型結構中大部分的虛擬位址空間多半是 unallocated
* 只有 level-1 page 一直都存在記憶體當中，虛擬記憶體系統可以隨時創造 level-2 以上的 page 或將 page 放入實體記憶體
* 虛擬位址可以被劃分為 k 個 VPN 和 1個 VPO，每個 VPN 都是 level-i 的 index 用於搜尋下一層的 page，只有 PPO 和 VPO 是相同的


* 切割越多層則需要查詢更多次的 PTE 直觀上認為會耗費更多時間，實際上並沒有慢很多

### 9.6.4
#### end-to-end address translation 過程
* 基本假設
* The memory is byte addressable.
* Memory accesses are to 1-byte words (not 4-byte words).
* Virtual addresses are 14 bits wide (n = 14).
* Physical addresses are 12 bits wide (m = 12).
* The page size is 64 bytes (P = 64).
* The TLB is four-way set associative with 16 total entries.
* The L1 d-cache is physically addressed and direct mapped, with a 4-byte line size and 16 total sets.
* 基於假設的記憶體系統結構

* TLB, Page Table, Cache 結構如下

* 例子：假設 CPU 執行一條讀取位址 0x03d4 的指令(CPU 一次讀一個 word)
1. MMU 從虛擬位址拿出 VPN (0x0F) 檢查 TLB 中的 index 3(11%4) 的列中是否有 TBLI 為 0x3(TLBT)
2. 發現 TLB 有，就將 0x0D(PPN) 回傳給 MMU
* 如果 TLB miss 就需要去 PT 拿取相對應的 PTE 來更新 TLB
3. MMU 將 PTE 拿到的 PPN (0x0D) 和虛擬位址的 VPO (0x14) 組合成實體位址 (0x354)
4. MMU 將實體位址送到快取，快取將拿到的位址切割出欄位
5. 快取查詢 index=5, offset=0 中 tag 是否為 0x0D ，結果查詢到 valid bit 為 1 將 offset= 0 的內容 0x36 傳回 MMU
6. MMU 將拿到的值傳回 CPU
* 其他可能會遇到的狀況像是：TLB miss, MMU 需要去 page table 中的 PTE 取出 PPN 更新
* 如果查詢到的 PTE valid bit=0 則產生 page fault，kernel 要負責去置換 page 重新執行指令
* 如果查詢到的 PTE valid bit=1 但是快取中沒有該資料

## 9.7 Intel Core i7/Linux 記憶體系統
* 支援 48bit 的虛擬位址空間和 52bit 的物理為址空間。處理器封裝成四個核，每個核獨立處理但是更想 L3 快取，其他單元都是個別擁有。核之間利用 QuickPath 和其他核互相傳遞內容
* QuickPath：為了讓每個 core 能夠和其他 core (或是其他外部連接的 I/O Bus)直接通訊而產生的技術

### 9.7.1
* 採用四層的 PT 架構，每個 process 有自己私有的 PT 架構
* 雖然 i7 能夠允許 page in/out，但是與已分配 page 相關的 page 都會先保留在記憶體(必要時才成為 victim page 節省開銷)
* CR3 控制暫存器存放的是 level-1 PT (L1)的起始位置，CR3 的值是每個 process content 的一部分，每次 content switch 時 CR3 值都會一起改變
* 地址位元詳細內容如下表所示，分成兩種不同格式，差別在於 last page 多了一個 Dirty bit
* 且當 P=1 時 page table physical address 存放的是一個 PPN，否則是 next level 的 PT 位址
* XD bit 是用來控制某些 page 對於存取指令的能力，這個 bit 可以用來防禦 buffer overflow attack
* MMU 做地址轉譯的過程中 page fault handler 會用到兩個 bit
* Dirty bit:對某個 page 進行寫入後，用於讓 kernel 得知替換該頁時是否寫回 victim page 到硬碟上
* Reference bit:每次存取 page 都會將其修改，用於替換演算法選擇 victim page
* VPN 會為 L1 PT 提供 index，L1 PTE 內存放的是 next-level page 的 base-address

#### 加速存取過程技巧
* 在地址轉譯過程中有兩個過程:
* MMU 將虛擬位址轉成實體位址，
* 將實體位址送到 L1 快取拿資料
* 實際硬體將兩件事情同時做來達到加速。VPN 在轉譯成 PPN 的過程中，因為 VPO = PPO，可以利用這個性質先去 L1 cache 找到對應的 set 和 offset 的內容，先將 Tag 讀出來，等到 PPN 拿到的同時可以馬上比對就能直接去記憶體拿資料了

### 9.7.2
* Linux 對每個 process 都維護一份虛擬地址空間，虛擬空間位址存放在 user stack 之上
* kernel virtual memory 的某些部份是 map 到共享的 physical page (e.g. kernel code & global data structure)
* kernel virtual memory 中 Linux 也會將一部分連續的虛擬地址空間映射到連續的 physical page 上(大小等同於實體 DRAM 大小)，這種方式讓 kernel 能夠更容易的存取實體記憶體的特定位址
* 像是要去存取 PT 或是 memory-mapped I/O 指令時
* kernel virtual memory 其餘的部分存放的就是每個 process 不同的資料(e.g. PT, 執行不同 process 會用到的 kernel stack)

#### Linux Virtual Memory Areas
* Linux 將虛擬記憶體組成一些 area 或稱 segment，這些段之間是用某種方式連結的(e.g. code segment, stack, shared area)
* 這種概念史的虛擬地址空間可以存在間隙，也讓 kernel 不用紀錄不存在的 VP，更省資源
* kernel 幫系統中每個 process 維護一個單獨的結構(task_struct)，結構內維護著 kernel 執行該 process 所需要的所有訊息(e.g. PID, pointer to the user stack, name of the executable object file, and program counter)
* 其中一個 Entry 指向一個 mm_struct 結構，該結構描述虛擬記憶體目前的狀態，其中又有兩個 entry 分別是:
* pgd：指向 level-1 PT 的 base address
* mmap：指向一個 vm_area_structs 結構的 list
* 每個 vm_area_structs 都描述了目前虛擬地址空間的一個 area，當 kernel 執行某個 process 時，就將 pgd 存在 CR3 control register 中

#### Linux Page Fault Exception Handling
* kernel 中 page fault handler 的處理程序
1. VA 是否合法，透過比對 vm_area_struct list 中所有的 vm_end 和 vm_start 判斷 VA 是否在合法區域內，若不合法則觸發 segmentation fault(1)
2. 判斷是否具有能夠存取該 page 的能力(e.g. 寫入唯讀頁面，user mode 想去存取 kernal mode 才能用的 page)，若不合法則觸發 protection exception(2)
3. 經過上述的檢查後，正常處理缺頁，選擇 victim page 做置換，返回時重做引發 page fault 的指令(3)


## 9.8 Memory Mapping
* Linux 利用硬碟上的某個 object 聯繫虛擬記憶體區域來達到初始化，這個過程稱為 memory mapping，虛擬記憶體區域可以映射到兩種目標對象：
* Linux 文件系統中的一般文件：一塊虛擬記憶體能夠映射到硬碟上一個普通文件的連續部分，文建會按 page size 切割成很多個 page 按照 demand page 的機制來取用，如果虛擬記憶體配置的比文件實體的記憶體要大時，剩餘部分補0
* 匿名文件(Anonymous file)：由 kernel 所創造全部都是 b'0 的文件，又稱 demand-zero pages
* 當 kernel 在實體記憶體上選擇 victim page 後，將這個匿名文件覆寫到 victim page 上，然後將 PT 上該 page 註記為可用的，過程中記憶體和硬碟並沒有實體傳輸
* 一旦 VP 被初始化後，就在 kernel 所維護的 swap file 之間做交換，也稱做 swap space/area。在任何時候目前執行的 process 能夠使用的 VP 的數量都被 swap space 所限制住

### 9.8.1
* 每個 process 能夠擁有自己的一個虛擬地址空間，讓 process 間不會輕易做錯誤的存取，但是多個 process 也可能會有需要相同 text area 的時候
* 在 Linux 每個執行 bash 的 process 都會有相同的 text area
* 每個 C 程式都需要標準函式庫
* 但在實體記憶體上存多個相同的內容的副本太浪費，所以 memory map 對 object 在多個 process 共享有一套機制
* 一個 object 在做 map 時能夠是 shared object 或 private object
* shared object：當虛擬地址空間映射到的是一個 shared object 則所有映射到這個空間的 process 都能夠看到對這個空間寫入的內容，這些改寫也會同時反應在硬碟上的資料，且在實體記憶體上僅需一份實體資料

* private object：反之，當虛擬地址空間映射到的是一個 private object，對其的修改不會反應在硬碟本來的資料上。利用 copy-on-write 的技術來做映射，實體記憶體上本來只有一份副本，且能夠被多個 process 共享和讀取，但是當有映射到該 object 其中一個 process 要做寫入時會觸發 protection fault，透過這種方式能夠有效使用記憶體
* fault handler 得知 protection fault 是因為嘗試寫入 private copy-on-write area 引發的，就會在實體記憶體中創造這個 page 的副本，更新 PTE 指向新的副本，使這個 page 恢復可寫入的權限，fault handler 返回後，CPU 會重新執行指令

### 9.8.2
* fork 函式備目前 process 所使用時，kernel 會為新的 process 建造各種資料結構，並分配給他一個 PID
* 新 process 的虛擬記憶體會有和原 process 相同的 mm_struct, area struct, PT，原 process 和新的 process 的 page 都被設定成 read-only 而且 area struct 被標記成 private copy on write
* 當 fork 完成返回時新 process 和原 process 的虛擬記憶體相同，當其中一個 process 進行 write 時， copy on write 機制就會創建新的空間
### 9.8.3
* 當有一個 program 執行 execve("a.out", NULL, NULL) 為例
1. 刪除原 process 存在的 user area
* 刪除 user 部分目前 process 虛擬地址中的 area struct
2. 映射新 process 的 private area
* 創造新 program 中 text, data, bss, stack 的 new area struct
* 所有新創造的區域都是 private copy-on-write
* text, data area 部分映射到 a.out 的 area 上
* bss 是一個 demand-zero，映射到 a.out 定義的 anonymous file 上
* heap, stack 也是 demand-zero，初始長度是 0
3. 映射新 process 的 shared areas
* 動態連接到 program 上，然後映射到 user 的虛擬地址空間中的 shared region
4. 設定 program counter
* 將目前 PC 指向新 process 的 text area 的 entry point
5. 當 process scheduler 選擇到這個 process 時就會從 PC 的位址開始執行
* Linux 就可以根據需要置換 code 和 data page

### 9.8.4
* Linux process 可以利用 **mmap** 來要求 kernel 創造新的虛擬記憶體區塊，將 object 映射到這些區塊上
* 參數 *prot* 包含對新的虛擬記憶體區塊存取權限的敘述
* 參數 *flag* 是對映射 object 的敘述
* 利用 **munmap** 可以刪除虛擬記憶體區塊

:::warning
Write a C program **mmapcopy.c** that uses mmap to copy an arbitrary-sized disk file to stdout. The name of the input file should be passed as a command line argument.
// TODO
:::
## 9.9 Dynamic Memory Allocation
* 雖然能夠使用 mmap 和 munmap 來建立虛擬記憶體空間，但是程式開發者認為仍需要動態記憶體分配器
* 動態記憶體分配器維護著 heap，kernel 為每個 process 維護一個變數 brk 指向 heap top
* 分配器將 heap 是唯一種任意大小的區塊，每個區塊都能做分配或是釋放
* 分配器主要有兩種:
* 兩者都是透過應用程式主動分配區塊，差別在於釋放已分配的區塊
* Explicit allocators：需要透過應用程式主動釋放區塊(e.g. C 中的 malloc & free, C++ 的 new & delete)
* Implicit allocators：要求分配器去偵測不再會被 program 用到的區塊，並釋放它。又稱為 garbage collectors(e.g. Java 依賴 garbage collection 去釋放記憶體區塊)

### 9.9.1
* C 標準函式庫 malloc 提供的就是 explicit allocator，回傳一個指標指向一塊對齊的記憶體(在 linux 32bit 對齊 8byte 的倍數, 64bit對齊 16 byte 的倍數)
* 如果 malloc 遭遇錯誤會返回 NULL ，設置 errno
::: warning
在 Intel 系統中 double word 為 4byte(單個 word 2byte)，但本章節使用的 double word 為 8byte(單個 word 4byte)
:::
* malloc 不會對分配好的記憶體做初始化，如果需要做初始化(all b'0)的記憶體區塊可以用 calloc，需要改變已分配的記憶體大小可以使用 realloc
* 可以透過使用 mmap 和 munmap 來動態記憶體分配還能使用 sbrk function
* sbrk 透過輸入 incr 改變 brk 指向的位置伸縮 heap 的大小，如果成功回傳 brk 舊值，失敗則回傳 -1 並將 errno 設為 ENOMEM (Out of memory)
* 在 sbrk 中若 incr 為負值仍是合法操作，回傳值會指向原 heap + abs(incr) byte 的地方
* free 中的 ptr 必須指向已分配區塊，若不是則 free 行為是未定義的，且什麼都不會回傳(回傳型態為 void)，所以不會告知錯誤，所以應該謹慎使用
* malloc & free 舉例 - 每個方框 4byte, 共 16 word, double-word aligned
1. process 請求一個 4 word 的區塊，malloc 返回指向區塊第一個字的指標
2. process 請求一個 5 word 的區塊，malloc 配置一個 6 word 的記憶體(為了對齊)並返回指向第一個字的指標
3. process 請求一個 5 word 的區塊，malloc 配置一個 6 word 的記憶體並返回指向第一個字的指標
4. 釋放 p2 指向被分配的區塊，雖然被釋放了但 p2 仍指向該位置，應用程式需要控制再 malloc 新區塊前不能使用 p2 指向的記憶體區塊
5. process 請求一個 2 word 的區塊，malloc 優先找到 p2 區塊的記憶體配置一個 2 word 的記憶體並返回指向第一個字的指標

### 9.9.2
* 使用動態記憶體分配的原因是很多程式在 runtime 執行時才會知道所需要資料結構的大小
* 考慮以下程式，將大小固定的寫法沒有辦法根據不同機器上所擁有的虛擬記憶體空間做制定:

#include "csapp.h"

#define MAXN 15213

int array[MAXN];

int main()
{
	int i, n;
	
	scanf("%d", &n);
	if(n > MAXN)
		app_error("Input file too big");
	for(i = 0;i < n; i++)
		scanf("%d", &array[i]);
	exit(0);
}

* 改善後的動態分配版本：

#include "csapp.h"

int main()
{
	int *array, i, n;
	array = (int *)Malloc(n * sizeof(int));
	for(i = 0;i < n; i++)
		scanf("%d", &array[i]);
	free(array)
	exit(0);
}

### 9.9.3
* Explicit allocators 的要求和限制
* Handling arbitrary request sequences：可以有任意的分配請求, 釋放請求的順序。分配器不能假設一個分配請求一定會有一個釋放請求對應
* Making immediate responses to requests：應該在請求當下立刻執行，不能因為最佳化效能改變、暫緩記憶體的分配和釋放順序
* Using only the heap：為了保持 heap 的靈活性，non-scalar 的資料結構都存放在 heap 中
* Aligning blocks (alignment requirement)
* Not modifying allocated blocks：只能操作或改變沒有使用的區塊，分配好的區塊不能被修改或移動了(e.g. 壓縮區塊不能被允許)
* 分配器的最大吞吐量和最佳記憶體使用率是衝突的，所以需要做權衡和設計
* 假設要透過最小化分配, 釋放記憶體時間來最大化吞吐量，但是分配釋放時間是和區塊大小成正比的
* 假設最大化記憶體使用量，但因為 process 能夠使用虛擬記憶體是被硬碟上的交換空間所限制的，所以沒辦法無限的使用
* heap 使用率的計算
* 給定某個請求順序 $R_0,R_1,R_2...,R_k,...,R_{n-1}$ ，某個 process 請求 $p$ word 區塊，有在使用的區塊大小總和為 $P_k$ (aggregate payload)，$H_k$是目前的 heap 大小
* 使用率為 $U_k = \dfrac{max_{i<=k}P_i}{H_k}$


### 9.9.4
* Fragmentation：雖然有未使用的空間但沒辦法來滿足分配請求的空間稱之，分為兩種:
* Internal fragmentation：分配的空間比使用的多，或是為了對齊產生的空間浪費。數量取決於實現設計的方式和請求的模式
* External fragmentation：當可使用空間加起來滿足分配請求但是沒有一個單獨的區塊足夠大來做處理。數量除了實現設計的方式和請求的模式，還和未來的請求有關
* 因為外碎不可預測性所以分配器通常用 heuristics 方法來維持少量連續的閒置區塊，而非多塊分散的閒置區塊
### 9.9.5
* 實現分配器要考量其吞吐量和使用率的權衡，需要考慮以下問題
* 如何記錄閒置區塊與組織的方式
* 如何選擇合適的閒置區塊
* 如何將閒置區塊在分配後分割剩於的閒置區塊
* 如何處理釋放的區塊

### 9.9.6
* 分配器的實作都需要搭配資料結構鑾區別區塊的邊界，分辨已分配區塊和閒置區塊，這些訊息會被鑲入區塊本身，令其為 header
* 一個區塊的組成有 one word header, payload, additional padding
* 如果區塊需要對齊則其大小都會是 8 的倍數，區塊的後三位皆為0，用來當作 allocated bit 辨識區塊是否配置
* 假設有一個已配置的區塊大小是 24(0x18) header 位置是 0x00000018 | 0x1 = 0x00000019
* 假設有一個閒置區塊大小是 40(0x28) header 位置是 0x00000028 | 0x0 = 0x00000028
* 使用 padding 可以用來處理外部碎片的問題，或是用於對齊
* 稱以下這種結構為 implicit free list 是因為閒置區塊透過 header 大小數值連接的，分配器可以透過閱覽所有區塊來得知閒置區塊的集合
* 這需要一個特別的結束區塊讓瀏覽的硬體知道結束點在哪裡
* 優點是簡單，但這樣的結構會有額外操作的開銷(e.g. 追蹤 list 所有內容找到閒置區塊)
* 根據系統不同，list 所建立的區塊需要有"基本單位"的概念

### 9.9.7
* 分配器執行搜索找到閒置區塊的方法稱為 placement policy，常見的有:
* first fit - 每次從第一個合適區塊開始搜尋。適合將大區塊保留在後面使用，但靠近開頭的部分存在很多內碎
* next fit - 從合適區塊開始搜尋，下一次搜尋是從上次搜尋的最後位置開始，較 first fit 快一些，但記憶體使用率較 first fit 低
* best fit - 對整個 list 搜尋找到最適合的區塊，記憶體使用率最高但需要徹底搜尋
### 9.9.8
* 分配器找到適合的區塊後就將閒置區塊分割，分割策略與此息息相關

### 9.9.9
* 如果分配器不能幫配置請求找到適合的區塊時，系統會有兩種對應方式:
* 合併實體記憶體上相鄰的閒置區塊來創造一個更大的區塊
* 上述方法如果仍無法滿足，則分配器就會透過 sbrk function 向 kernel 請求額外的 heap 記憶體，分配器將額外的記憶體轉成一個大的閒置區塊插入到 free list 中，在將請求配置的區塊放在這個閒置區塊中

### 9.9.10
* 當分配器釋放已分配的區塊時，可能有其他閒置區塊與其相鄰，這些相鄰的閒置區塊稱為 false fragmentation
* 假設下圖要請求配置一個 4 word 區塊就會失敗
* 所以分配器需要有能力合併相鄰的閒置區塊，合併又分為兩種:
* immediate coalescing：每次釋放區塊時就合併所有相鄰的閒置區塊，有可能造成額外的分割合併操作(e.g. 釋放後馬上又要配置新區塊)
* deferred coalescing：不馬上做合併，到某個請求失敗後才做合併的動作
### 9.9.11
* 位在前面的區塊如果釋放後透過 header pointer 可以檢查和後面的區塊是否可以合併，但是後方區塊釋放需要追蹤整個 list 才能和前方區塊合併這樣的方法代表 free 操作所需要的時間取決於 heap 大小且無法在常數時間做完
* 衍生出 boundary tags 的方法能夠在常數時間做完 free 操作
* 透過在區塊的結尾處加上一個header 的副本 - footer，透過 footer 就可以檢查前一個區塊的狀態
* 且 footer 位置永遠都會在區塊的開始位置前 1byte 的位置

* 加上 footer 後分配器釋放可能的四種合併狀態:





* footer 的缺點是每個區塊永遠需要一個 header 和一個 footer 這對需要很多小區塊的 process 來說會浪費大量的記憶體空間

### 9.9.12
* 詳情見實作，習題額外要求兩項功能做輔助
:::warning
Implement a **find_fit** function for the simple allocator described in Section 9.9.12.
**static void \*find_fit(size_t asize)**
Your solution should perform a first-fit search of the implicit free list.
:::
::: warning
Implement a **place** function for the example allocator.
**static void place(void \*bp, size_t asize)**
Your solution should place the requested block at the beginning of the free block, splitting only if the size of the remainder would equal or exceed the minimum block size.
:::
### 9.9.13
* 區塊的分配時間和 heap 大小成線性關係，通用的分配器不適合用 implicit free list，更好的方法是用精確的資料結構，因為程式運作時不會存在一個主要的閒置區塊存在，所以這些資料結構的指標應該放在區塊內部，所以 heap 可以生成一個雙向的 list，每個閒置區塊中包含一個 pred 和 succ
* 這個方法使 first fit 的搜尋時間從 heap 大小的線性關係降為閒置區塊數量的線性關係，但釋放空間時間會取決於選擇的區塊的排序策略決定(可能是常數或線性)
* 其中一種方法是用 LIFO 順序維護 list，將釋放出來的區塊放在 list 起點
* 另一種方法是用地址順序維護 list ，但是這種方法需要線性時間找到合適的 prec，但是記憶體使用率較好
* Explicit Free Lists 缺點是閒置區塊需要足夠大包含所有需要的指標, header, footer，這導致區塊單元比較大，也更可能造成內碎問題

### 9.9.14
* Segregated Free Lists 是一種減少分配時間的方法，透過維護多個閒置 list ，每個 list 有相同大小的區塊，將所有相同大小的分成一個等價類稱為 size class
* 當分配器想從 Segregated Free Lists 要求一個區塊時，搜尋對應的 list 是否還有可用區塊，如果沒有就往下一個 list 找

* 主要的架構分為幾種：
* Simple Segregated Storage
* 每個 size class 的閒置 list 包含大小相等的塊，每塊大小就是這個 size class 最大的元素大小
* 分配區塊時搜尋對應的 list ，如果 list 為空分配器會向 OS 請求一個固定大小的額外記憶體，將這個記憶體分成大小相等的塊形成新的閒置空間 list
* 釋放空間時將空間插入閒置 list 最前方
* 優點是分配釋放操作都是常數時間
* 缺點是每個閒置區塊都需要有一個 succ pointer 所以區塊最小需要 1 word，且容易造成內碎和外碎
* Segregated Fits
* 分配器維護一個閒置區塊 list 的 array，每個 list 有一種 size class
* 分配區塊時找到最合適的插入，剩餘空間分割出來插入適當的閒置區塊的 list 中
* Clib GNU 的 malloc 就是這種方法
* Buddy Systems
* 每個 size class 都是2的冪次
* 假設 heap 大小是 $2^m$ word，每區塊 list 大小是 $2^k$,0<=k<=m
* 分配區塊時會遞回對半切割原本 heap 空間直到可以符合該大小最接近的2冪次的大小，過程中沒有被配置的區塊則會加入閒置 list 中
* 優點是能夠快速計算出夥伴的位址，且能夠快速搜尋和合併，適合用於事先知道區塊大小需求是2的冪次的程式
* 缺點是要求區塊大小為2的冪次會有內碎問題

## 9.10 Garbage Collection
* 忘記釋放已配置的記憶體是一種常見的編程錯誤，如下面的例子

void garbage()
{
	int *p = (int *)malloc(15213);
	return;/* Array p is garbage at this point */
}

* garbage collector 是一種動態記憶體分配器，它會自動釋放不再使用的已配置區塊。透過定期的辨識哪些是垃圾區塊進行回收

### 9.10.1
* 垃圾收集器將記憶體視為一張 reachability graph，該圖中又分成 root node 和 heap node，每個 heap node 對應於 heap 中的一個已分配區塊，有向指標代表某個區塊使用指向另外一個區塊的指標，這些節點可以是暫存器或是 stack 的變量亦或是虛擬記憶體內的全域變數。當存在跟節點能夠到達的 heap 節點時稱此點為可達的
* 垃圾收集器的任務就是將那些不可達的點定期回收到閒置空間列表
* 像是 ML 或是 Java 的垃圾收集器對使用指標有嚴格控管，所以能夠精確回收。但是 C 和 C++ 這種通常沒辦法用可達圖來精確表示，這樣的收集器稱作 conservative garbage collectors ，這種收集器可能會使某些不可達的點倍標記程可達的
* 使用 malloc 都會向 heap 要求空間，但是如果當 malloc 無法找到一塊合適的空間時就需要使用垃圾收集器去呼叫 free 多回收一些空閒區塊，如果回收後仍失敗則會向 OS 要求額外的記憶體

### 9.10.2
* Mark & Sweep 垃圾收集器由 mark 階段和 sweep 階段組成
* mark 階段：將所有可達的點標記
* sweep 階段：將釋放所有未標記的區塊
* 如果 p 沒有指向一個已分配的區塊且未標記就會回傳，否則標記該區塊可達的點都標記。標記階段結束後，沒有被標記的點保證是不可達所以可以在 sweep 階段做回收

### 9.10.3
* Mark & Sweep 在 C 的挑戰
* C 沒有對記憶體位置做類別標記的能力，所以沒有辦法判斷傳入的內容是不是指標
* 即便得知是指標，也沒有辦法判斷是否指向一個已配置的區塊的 payload 上
* 對上述第二個問題解決方法是將已配分的區塊建構成一個 balanced binary tree，這棵樹的左子樹的所有塊都放在較小的 address 位址，而右子樹都放在較大的 address 位址
* 這個要求使得每個已分配區塊都要在 header 加上 right 和 left，指向下一個已分配的區塊，這樣在查找時就能夠用大小來辨別區塊的有效性
* 缺點是這樣有可能造成有些不正確的標記，使某些不可達的點沒有被釋放，造成不必要的外碎
* 像是 C 中可達的某個點包含 int 或是 float 在 payload 內的值剛好對應到某個位址，則那個值的區塊會被標示為可達的，因為無法推估該 int 或是 float 是否是該位址或是只是單純的變數宣告，所以才會將該區塊不管如何都標記成可達的，實際上可能是不可達的區塊

## 9.11 Common Memory-Related Bugs in C Programs
### 9.11.1 Dereferencing Bad Pointers
* 在虛擬地址空間上會有一塊空間是映射到沒意義的資料上，這塊記憶體位址通常是不能被使用的，或是唯讀記憶體的部分，企圖寫入這些位置都會令 OS 啟動例外處理
* 常見的錯誤像是 scanf 的引用

scanf("%d", &val)

* 上述的這行常常被寫成以下的狀況：

scanf("%d", val)

* 這種情況下 val 被視為一個地址，並將讀到的內容寫到 val 這個值的地址上，若系統沒有保護這個處理，val 所代表地址的記憶體內容將會被覆寫
### 9.11.2 Reading Uninitialized Memory
* 雖然 bss 的記憶體位置會 loader 被初始化成0 ，但是 heap memory 並不會作初始化
* 常見的錯誤像是：

int *matvec(int **A, int *x, int n)
{
	int i, j;
	int *y = (int *)Malloc(n * sizeof(int));
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			y[i] += A[i][j] * x[j];	
	return y;
}

* 使用者誤以為 y 的記憶體內容都被初始化了，正確的方式是要再對 y 做初始化，或是使用 calloc
### 9.11.3 Allowing Stack Buffer Overflows
* 如果一個城市不檢查輸入字串的大小就寫到 stack 中的 buffer 很容易就產生 buffer overflow
* 下面這個例子就是因為 gets 讀入任意長度的字鑽到 buffer 中，應該改用 fgets 去限制讀入的長度或是做額外的長度檢查

void bufoverflow()
{
	char buf[64];
	gets(buf);
	return;
}

### 9.11.4 Assuming that Pointers and the Objects They Point to Are the Same Size
* 以下這個範例是建構一個指標的指標指向一個 int 型態的指標陣列，這個錯誤是假設指標的指標的大小被預設是和指標相同(int 和 int* 差異)
* 而且這段程式碼在 Core i7 配置時並不會錯誤，因為指標的大小會比 int 大，但是在釋放時就會釋放出比原本預期還大的空間而出現錯誤

/* Create an nxm array */
int **makeArray1(int n, int m)
{
	int i;
	int **A= (int **)Malloc( n * sizeof(int));
	
	for(i = 0; i < n; i++)
		A[i] = (int *)Malloc(m * sizeof(int));
	return A;
}

### 9.11.5 Making Off-by-One Errors
* 這個錯誤是因為宣告的指標陣列大小只有 n 但是下面的 for 卻使用到了 n+1 個，會將沒有被宣告使用的那個記憶體空間覆寫

/* Create an nxm array */
int **makeArray2(int n, int m)
{
	int i;
	int **A = (int **)Malloc(n * sizeof(int *));
	for (i = 0; i <= n; i++)
		A[i] = (int *)Malloc(m * sizeof(int));
	return;
}

### 9.11.6 Referencing a Pointer Instead of the Object It Points to
* 如果寫程式時不考慮符號的優先權和結合性，有可能使指標指向非預期的位置
* 下面這段程式的目的是為了要刪除一個索引為 \*size 陣列的內容，然後重新做 heapify，原本的目的是將 *size 指向的值減1，但是實際上這樣撰寫會變成減少指標的位址的值
* 解決方式是在對優先權或是結合性有疑慮時使用括號

int *binheapDelete(int **binheap, int *size)
{
	int *packet = binheap[0];

	binheap[0] = binheap[*size - 1];
	*size--; /* This should be (*size)-- */
	heapify(binheap, *size, 0);
	return(packet);
}

### 9.11.7 Misunderstanding Pointer Arithmetic
* 有些錯誤是忘記指標的算術運算是以指向的目標大小為單位做運算，單位不一定是 byte 或是 word 等，下面程式的目的就是要掃描一個 int 陣列，但每次迴圈都使指標指向本身位址後4位的陣列內容

int *search(int *p, int val)
{
	while (*p && *p != val)
	p += sizeof(int); /* Should be p++ */
	return p;
}

### 9.11.8 Referencing Nonexistent Variables
* 這個函式會回傳一個地址位置給一個指標接，但是因為它是區域變數，回傳後雖然是一個記憶體位址，但實際上是不合法的指向空間，如果其它程序重用了這個位置，回傳收到的指標也指向這個位置產生嚴重錯誤

int *stackref()
{
	int val;
	
	return &val;
}

### 9.11.9
* 使用一個已經被釋放的 heap 區塊中的資料也會有錯誤

int *heapref(int n, int m)
{
	int i;
	int *x, *y;

	x = (int *)Malloc(n * sizeof(int));

	/* ... */ /* Other calls to malloc and free go here */

	free(x);

	y = (int *)Malloc(m * sizeof(int));
	for (i = 0; i < m; i++)
		y[i] = x[i]++; /* Oops! x[i] is a word in a free block */

	return y;
}

### 9.11.10 Introducing Memory Leaks
* Memory Leaks 的問題是因為宣告了空間但是卻忘記釋放，但是根據定義這些空間又不會被釋放，造成 heap 使用率很低甚至占用過多

void lead(int n)
{
	int *x = (int *)Malloc(n * sizeof(int));
	
	return; /* x is garbage at this point */
}