垃圾回收與記憶體錯誤 (Garbage Collection & Memory Bugs)

Overview Table

9.10 Garbage Collection 概念 (p.901–902)

Garbage collector 是會自動釋放程式不再需要的已配置區塊(即 garbage)的動態儲存配置器 (dynamic storage allocator)。在支援 GC 的系統中,應用程式只呼叫 malloc、從不呼叫 free;collector 週期性地找出 garbage 區塊,並代替應用程式呼叫 free 把它們放回 free list。

• 忘記 free 是常見程式錯誤:如 void garbage() { int *p = Malloc(15213); return; } — 區塊在程式整個生命期都佔著 heap,無法再被利用 (p.902)。
• GC 起源於 1960 年代初 MIT 的 John McCarthy(Lisp 系統);現代語言如 Java、ML、Perl、Mathematica 都內建 GC。
• 本章聚焦 McCarthy 最初的 Mark&Sweep 演算法,因為它可以架在既有 malloc package 之上,為 C/C++ 程式提供 GC。

9.10.1 可達圖 (Reachability Graph) (p.902–903)

Collector 把記憶體視為一張有向圖:節點分成 root nodes 與 heap nodes。每個 heap node 對應一個已配置 heap 區塊;有向邊 p → q 表示區塊 p 中某位置指向區塊 q 中某位置。Root nodes 是「不在 heap 內、但含有指向 heap 的指標」的位置:暫存器 (registers)、stack 上的變數、read/write data 區的全域變數。

   Root nodes:   [reg]   [stack var]   [global]
                    \        |            /
                     v       v           v
   Heap nodes:      (A) --> (B)         (C)
                              \          |
                               v         v
                              (D)       (E)      (F)  (G)
                  |<---- reachable ---->|      |<-unreachable->|
                                                = garbage,可回收

• 節點 p reachable(可達) ⇔ 存在從任一 root node 到 p 的有向路徑。
• 任一時刻的 unreachable 節點 = garbage,應用程式永遠無法再使用它們。
• Collector 的角色:維護可達圖的某種表示,週期性回收不可達節點(free 之、放回 free list)。

Exact vs. Conservative Collector (p.903)

Collector 可以 on demand 執行,也可作為獨立執行緒與應用程式平行執行、持續更新可達圖並回收 garbage。

與 C malloc package 整合的資料流 (Figure 9.50, p.903)

  C application ──malloc()──> ┌────────────────────────────┐
     program                  │ Dynamic storage allocator  │
                              │  malloc 找不到合適 free 區塊 │
                              │        │                   │
                              │        v                   │
                              │  Conservative GC ──free()──│──> 回收 garbage 至 free list
                              │        │                   │
                              │        v                   │
                              │  malloc 重試;仍失敗 →      │
                              │  向 OS 要更多 heap;        │
                              │  成功回傳 ptr / 失敗回傳 NULL│
                              └────────────────────────────┘

9.10.2 Mark&Sweep 演算法 (p.903–905)

Mark&Sweep collector 分兩階段:mark 階段標記 root nodes 的所有可達且已配置的後代 (descendants);sweep 階段掃過整個 heap,釋放每個「已配置但未標記」的區塊。標記通常用 block header 中閒置的低位 bit (spare low-order bit) 表示。

假設 typedef void *ptr,依賴以下輔助函式 (p.904):

/* Figure 9.51 (p.904) */
void mark(ptr p) {                     void sweep(ptr b, ptr end) {
    if ((b = isPtr(p)) == NULL)            while (b < end) {
        return;                                if (blockMarked(b))
    if (blockMarked(b))                            unmarkBlock(b);
        return;                                else if (blockAllocated(b))
    markBlock(b);                                  free(b);
    len = length(b);                           b = nextBlock(b);
    for (i = 0; i < len; i++)              }
        mark(b[i]);   /* 遞迴 DFS */       return;
    return;                            }
}

• mark 對每個 root node 呼叫一次;若 p 不指向已配置且未標記的 heap 區塊就立即返回,否則標記該區塊並對區塊中每個字組遞迴呼叫(深度優先走訪可達圖)。
• mark 階段結束時:已配置且未標記 ⇒ 保證不可達 ⇒ garbage。
• sweep 只呼叫一次,線性走訪 heap 每個區塊:已標記者清除標記(為下一輪做準備);未標記且已配置者 free。

執行流程與範例 (Figure 9.52, p.905)

狀態轉換:  [Before mark] --mark(root)--> [After mark] --sweep(heap)--> [After sweep]

heap:      1     2     3     4     5     6         root → 4
指標關係:  3→1,  4→3,  4→6

Before mark:  全部 unmarked
After  mark:  1* 2  3* 4* 5  6*     (* = marked;1,3,4,6 從 root 可達)
After sweep:  1  [Free] 3  4  [Free] 6   (2、5 不可達 → 回收至 free list)

9.10.3 Conservative Mark&Sweep for C (p.905–906)

Mark&Sweep 適合 C 的原因:它 works in place、不移動任何區塊。但 C 對 isPtr 的實作構成兩大挑戰:

1. C 不對記憶體位置標記型別資訊 → isPtr 無法判斷輸入 p 到底是不是指標。
2. 即使已知 p 是指標,也沒有明顯方法判斷 p 是否指向某已配置區塊 payload 內的位置(p 可能指向區塊中間,而非開頭)。

第 2 個問題的解法:把已配置區塊集合維護成平衡二元搜尋樹 (balanced binary tree),不變量 (invariant) 為「左子樹的區塊位址都較小、右子樹都較大」。每個已配置區塊 header 需額外兩個欄位 left、right,各指向某已配置區塊的 header;isPtr 用此樹做二分搜尋,每一步靠 header 的 size 欄位判斷 p 是否落在該區塊範圍 (extent) 內。

Allocated block header (Figure 9.53, p.905):
┌──────┬──────┬───────┬─────────────────────┐
│ Size │ Left │ Right │  Remainder of block │
└──────┴──┬───┴───┬───┴─────────────────────┘
          │       └──> 位址較大的區塊之 header
          └──> 位址較小的區塊之 header

9.11 C 程式常見記憶體錯誤 (p.906–911)

記憶體錯誤之所以可怕,在於它們常在時間與空間上都遠離病灶處才發作 (manifest at a distance):寫錯資料到錯的位置,程式可能跑好幾個小時後才在毫不相干的地方掛掉。以下十類是 C 程式的經典 bug。

9.12 章節總結 (p.911–912)

虛擬記憶體是主記憶體的抽象:處理器產生 virtual address,經位址轉譯 (address translation) 變成 physical address 再送往主記憶體;轉譯需要硬體(用 page table 轉譯)與軟體(OS 提供 page table 內容)緊密合作。

• VM 三大能力:
  • Caching:自動把磁碟上最近使用的虛擬位址空間內容快取到主記憶體;VM 的快取區塊叫 page,存取磁碟上的 page 觸發 page fault,由 OS 的 fault handler 把 page 從磁碟複製進主記憶體(必要時 write back 被逐出的 page)。
  • 簡化記憶體管理:進而簡化 linking、行程間資料共享、記憶體配置、程式載入。
  • 簡化記憶體保護:在每個 PTE 中加入 protection bits。
• 位址轉譯必須與硬體快取整合;PTE 多半在 L1,但存取成本通常被 TLB(on-chip 的 PTE 快取)消除。
• Memory mapping:把虛擬記憶體區塊與磁碟檔案區塊關聯以初始化之;是共享資料、建立新行程、載入程式的高效機制;可用 mmap 手動建立/刪除 area,但多數程式依賴 heap 上的動態配置器如 malloc。
• Allocator 兩類:explicit allocator 要求應用程式自己 free;implicit allocator(= garbage collector) 自動釋放未使用且不可達的區塊。Allocator 是「有系統級手感的應用級程式」,幾乎不靠型別系統直接操作記憶體。

        VM 全章知識地圖(9.12 總結視角)
  virtual address ──> [TLB / page tables] ──> physical address ──> cache/DRAM
        │  miss: page fault → OS handler 從 disk 調頁
        │
  memory mapping (mmap) ──> heap ──> dynamic allocator
                                       ├─ explicit  (malloc/free)
                                       └─ implicit  (garbage collector)

Exam/Test Patterns

Related Notes

• 09-Virtual-Memory/05-Dynamic-Memory-Allocation
• 09-Virtual-Memory/02-VM-Management-and-Protection
• 09-Virtual-Memory/04-Memory-Mapping
• 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety
• 03-Machine-Level-Programs/04-Procedures-and-the-Stack
• 07-Linking/03-Executable-Loading-and-Dynamic-Linking