動態記憶體配置 (Dynamic Memory Allocation)

Overview Table

9.9 動態記憶體配置器與 Heap (p.875)

雖然可直接用 mmap/munmap 建立虛擬記憶體區域,C 程式設計者通常用動態記憶體配置器 (dynamic memory allocator) 取得 run-time 記憶體,較方便也較可攜。配置器維護稱為 heap 的虛擬記憶體區域:demand-zero、緊接在 .bss 之後、向高位址成長;kernel 為每個 process 維護指向 heap 頂端的 brk 指標。

高位址
+---------------------------+
|        User stack         |  向下成長
+---------------------------+
|            ...            |
+---------------------------+
| Memory-mapped region      |
|  (shared libraries)       |
+---------------------------+
|            ...            |
+---------------------------+ <-- brk (top of the heap)
|           Heap            |  向上成長
+---------------------------+
| Uninitialized data (.bss) |
+---------------------------+
| Initialized data (.data)  |
+---------------------------+
|       Code (.text)        |
+---------------------------+
低位址 (0)

• heap 是各種大小 block 的集合;每個 block 是連續的虛擬記憶體 chunk,狀態為 allocated 或 free。
• Explicit allocator:應用程式自己 free(C 的 malloc package;C++ 的 new/delete)。
• Implicit allocator(= garbage collector):由配置器偵測不再使用的 block 並自動釋放(Lisp、ML、Java);見 09-Virtual-Memory/06-Garbage-Collection-and-Memory-Bugs。

9.9.1 malloc 與 free (p.876)

#include <stdlib.h>
void *malloc(size_t size);   // 成功回傳 block 指標,失敗回傳 NULL 並設 errno
void free(void *ptr);        // 無回傳值
#include <unistd.h>
void *sbrk(intptr_t incr);   // 成功回傳舊 brk,失敗回傳 -1 (errno=ENOMEM)

• malloc 回傳至少 size bytes 且對齊到可容納任何資料型別的 block:32-bit mode 位址為 8 的倍數,64-bit mode 為 16 的倍數 (p.877)。
• malloc 不初始化記憶體;要清零用 calloc(malloc 的薄包裝),要改變已配置 block 大小用 realloc。
• sbrk(incr) 把 kernel 的 brk 加上 incr 以伸縮 heap;incr == 0 回傳目前 brk;負的 incr 合法但棘手(回傳值指向新頂端之後 abs(incr) bytes 處)。
• free(ptr) 的 ptr 必須指向由 malloc/calloc/realloc 取得之 block 的開頭,否則行為未定義;且 free 無回傳值,不會告知任何錯誤 (p.877)。
• 本節術語:word = 4 bytes、double word = 8 bytes(與 Intel 把 4 bytes 叫 double word 不同,p.877 Aside)。

Figure 9.34 (p.878) 以 16-word 小 heap 示範:malloc 從 free block 前端切塊;請求 5 words 時 malloc 實際配 6 words(padding 一個 word 維持 double-word 對齊);free 後指標 p2 仍指向舊處——應用程式有責任不再使用它。

9.9.2 為何需要動態配置 (p.879)

程式常在 run time 才知道資料結構大小。用 #define MAXN 15213 硬編陣列上限:上限與實際可用虛擬記憶體無關、超過就得重新編譯,在百萬行等級的軟體中是維護惡夢。改用 array = (int *)Malloc(n * sizeof(int)) 在讀到 n 之後才配置,上限僅受可用虛擬記憶體限制。

9.9.3 配置器的限制與目標 (p.880)

Explicit allocator 的硬性限制:

兩個互相衝突的目標 (p.881):

• Goal 1 — 最大化 throughput:單位時間完成的 request 數(如 1 秒完成 500 allocate + 500 free = 1,000 ops/s)。合理目標:allocate 最壞情形與 free block 數成線性、free 為常數時間。
• Goal 2 — 最大化 memory utilization:虛擬記憶體受 disk 上 swap space 限制,並非無限。以 peak utilization 度量:request $R_k$ 完成後,$P_k$ = 目前所有 allocated blocks 的 payload 總和(aggregate payload),$H_k$ = 目前 heap 大小(單調不減):

目標是最大化整個序列的 $U_{n-1}$。

9.9.4 碎片化 (Fragmentation) (p.882)

Fragmentation = 未使用的記憶體無法滿足 allocate requests,是 heap 利用率差的主因。

9.9.5 實作議題 (p.882)

Naive allocator:heap 當大 byte 陣列,malloc 就遞增指標 p,free 什麼都不做——throughput 極佳但從不重用 blocks,utilization 極差。實用配置器必須處理四個議題:

1. Free block organization:如何追蹤 free blocks?
2. Placement:選哪個 free block 放新配置的 block?
3. Splitting:放進去之後,剩餘部分怎麼辦?
4. Coalescing:block 剛被 free 之後怎麼辦?

9.9.6 Implicit Free List (p.883)

block 格式:1-word header + payload + 選擇性 padding。header 編碼 block size(含 header 與 padding)與 allocated bit。double-word 對齊下 size 是 8 的倍數 → 低 3 bits 恆為 0,只需存高 29 bits,低 3 bits 可編碼其他資訊(最低位 = allocated bit,a=1 allocated、a=0 free):

 31                      3 2 1 0
+------------------------+-----+
|      Block size        |0 0 a|  Header (1 word)
+------------------------+-----+
|          Payload             |  malloc 回傳指向此處的指標
|    (allocated block only)    |
+------------------------------+
|      Padding (optional)      |
+------------------------------+

header 編碼公式:header = size | alloc_bit

• allocated、size 24 (0x18):0x00000018 | 0x1 = 0x00000019
• free、size 40 (0x28):0x00000028 | 0x0 = 0x00000028

heap 組織成連續的 allocated/free blocks 序列,free blocks 由 header 的 size 欄位隱式串連——走訪所有 blocks 即可間接走訪所有 free blocks:

Start                                                     終止 header
 of   | unused | 8/0 | 16/1 | 32/0 | 16/1 | 0/1 |
heap    padding  free  alloc  free   alloc  epilogue(size 0, a=1)
        (標記為 size/allocated bit)

• 需要特殊的結尾 block:size 0、allocated bit 設 1 的 terminating header(設 allocated 簡化 coalescing)。
• 優點:簡單。缺點:任何需要搜尋 free list 的操作(如 placement)都與 heap 中 allocated + free 總 block 數成線性。
• 對齊要求 + block 格式 ⇒ 最小 block size:double-word 對齊下每個 block 必為 8 bytes 的倍數,此格式的最小 block = 2 words(1 word header + 1 word 維持對齊)——即使只 malloc 1 byte 也配 2 words (p.884)。

9.9.7 放置策略 (Placement) (p.885)

應用程式要求 k bytes 時,配置器依 placement policy 搜尋夠大的 free block:

Segregated free list(9.9.14)可不需徹底搜尋就近似 best fit。

9.9.8 分割 Free Blocks (Splitting) (p.885)

找到 fit 之後的政策決定:

• 整塊使用:簡單快速,但造成 internal fragmentation;若 placement 產生的 fit 很好,尚可接受。
• 分割 (split):fit 不佳時,把 free block 切成兩半——前半成為 allocated block,剩餘部分成為新的 free block(如 Figure 9.37:8-word free block 滿足 3-word 請求後切成 16/1 + 16/0)。

9.9.9 取得額外 Heap 記憶體 (p.886)

找不到 fit 時的流程:

找不到 fit
   |
   v
合併 (coalesce) 實體相鄰的 free blocks 造出更大 free block
   |
   +-- 仍不夠大 / 已最大程度合併?
   |
   v
呼叫 sbrk 向 kernel 要額外 heap 記憶體
   |
   v
把新記憶體轉成一個大 free block,插入 free list,
再把 requested block 放進這個新 free block

9.9.10 合併 Free Blocks (Coalescing) (p.886)

free 一個 block 後,相鄰可能已有其他 free blocks,造成 false fragmentation:可用記憶體被切成許多小而無用的 free blocks(如兩個相鄰 3-word-payload free blocks 無法滿足 4-word 請求,即使總量足夠)。實用配置器必須合併相鄰 free blocks。

• Immediate coalescing:每次 free 就合併相鄰者——直觀、常數時間;但某些 request 模式會thrashing(同一 block 反覆合併又分割)。
• Deferred coalescing:延後到某時機(如配置失敗時掃描整個 heap 一次合併)。快的配置器常採用某種 deferred coalescing;本書討論假設 immediate coalescing。

9.9.11 Boundary Tags (p.887)

合併下一個 block 容易:current header 走到 next header,檢查 allocated bit,若 free 就把 size 加進 current header,常數時間。合併前一個 block 在只有 header 的 implicit list 中得線性搜尋整個 list。

Knuth 的 boundary tags:在每個 block 尾端加 footer(header 的複本)。前一個 block 的 footer 永遠位於 current block 開頭往前一個 word 處 → 常數時間得知前一 block 的起點與狀態。

+------------------------+-----+
|      Block size        | a/f |  Header
+------------------------+-----+
|          Payload             |
+------------------------------+
|      Padding (optional)      |
+------------------------------+
|      Block size        | a/f |  Footer (boundary tag, header 複本)
+------------------------------+

free 當前 block(n)時的四種 case(皆常數時間):

Practice 9.7 (p.888) 最小 block size(header/footer 各 4 bytes、payload 不可為 0):

9.9.12 實作簡單配置器 (p.890)

以 implicit free list + immediate boundary-tag coalescing 實作;最大 block size $2^{32}=4\text{GB}$,程式碼 64-bit clean(gcc -m32/-m64 皆可)。

memlib.c 記憶體模型 (p.890):mem_init 用大陣列模擬 heap(避免干擾系統 malloc);mem_sbrk 介面/語意同 sbrk 但拒絕縮小 heap。配置器 (mm.c) 匯出三個函式:mm_init(成功回傳 0)、mm_malloc、mm_free(語意同系統版本)。最小 block size = 16 bytes。

Heap 不變形式 (invariant form) (p.891, Figure 9.42):

        Prologue    Regular    Regular        Regular   Epilogue
        block       block 1    block 2  ...   block n   block
+------+----+----+---------+----------+-----+---------+-----+
|unused| 8/1| 8/1|hdr .. ftr|hdr .. ftr| ... |hdr .. ftr| 0/1 |
+------+----+----+---------+----------+-----+---------+-----+
 pad     hdr  ftr  ^
        (prologue) heap_listp

• 開頭 1 個 unused padding word(維持 double-word 對齊)。
• Prologue block:8-byte allocated block,只有 header+footer,初始化時建立、永不 free。
• Epilogue block:size 0 的 allocated block,只有 header。
• prologue/epilogue 是消除 coalescing 邊界條件的技巧——否則每次 free 都要檢查 block 是否在 heap 開頭/結尾,程式碼更亂、更易錯、更慢。
• 私有全域變數 heap_listp 恆指向 prologue block。

常數與巨集 (Figure 9.43, p.893)——考試常考的指標運算:

#define WSIZE     4            /* word / header / footer 大小 */
#define DSIZE     8            /* double word */
#define CHUNKSIZE (1<<12)      /* 每次擴充 heap 的預設量 = 4 KB */

#define PACK(size, alloc)  ((size) | (alloc))
#define GET(p)        (*(unsigned int *)(p))
#define PUT(p, val)   (*(unsigned int *)(p) = (val))
#define GET_SIZE(p)   (GET(p) & ~0x7)
#define GET_ALLOC(p)  (GET(p) & 0x1)
#define HDRP(bp)      ((char *)(bp) - WSIZE)
#define FTRP(bp)      ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

bp(block pointer)指向第一個 payload byte;巨集可組合,如 GET_SIZE(HDRP(NEXT_BLKP(bp))) 取得下一 block 的 size。

mm_init (p.894):mem_sbrk(4*WSIZE) 取 4 words → 依序寫入 padding、prologue header PACK(DSIZE,1)、prologue footer、epilogue header PACK(0,1);heap_listp += 2*WSIZE;再 extend_heap(CHUNKSIZE/WSIZE) 建立初始 free block。

extend_heap (p.894):在 (1) heap 初始化與 (2) mm_malloc 找不到 fit 時被呼叫。把 words 向上取整為偶數(size = (words%2) ? (words+1)*WSIZE : words*WSIZE)維持對齊;mem_sbrk 回傳的 chunk 緊接在舊 epilogue header 之後——舊 epilogue header 變成新 free block 的 header,chunk 最後一個 word 寫入新 epilogue header;最後呼叫 coalesce(bp)(舊 heap 很可能以 free block 結尾)。

mm_free 與 coalesce (p.896):mm_free 把 header/footer 的 alloc bit 清 0 後呼叫 coalesce;coalesce 依 GET_ALLOC(FTRP(PREV_BLKP(bp))) 與 GET_ALLOC(HDRP(NEXT_BLKP(bp))) 分四個 case 實作 Figure 9.40,case 3/4 最後 bp = PREV_BLKP(bp)。

mm_malloc (p.897):

1. size == 0 的 spurious request 回傳 NULL。
2. 調整 block size(adjusted size,含 header/footer overhead 與對齊):

if (size <= DSIZE)
    asize = 2*DSIZE;                                   /* 最小 16 bytes */
else
    asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);  /* 加 overhead 後向上取整到 8 的倍數 */

1. find_fit(asize) 搜尋 free list;找到就 place(bp, asize)(放置並視情況分割)。
2. 找不到則 extendsize = MAX(asize, CHUNKSIZE),extend_heap(extendsize/WSIZE) 後再 place。

Practice 9.8/9.9 (p.897):find_fit 為 implicit list 的 first-fit 搜尋;place 把 block 放在 free block 開頭,只有剩餘部分 ≥ 最小 block size (16 bytes) 才分割。

9.9.13 Explicit Free Lists (p.898)

implicit list 的配置時間與總 block 數成線性,不適合通用配置器(僅適合 block 數已知很小的特殊用途)。改為把 free blocks 組成顯式資料結構:free block 的 body 程式用不到,可存放指標——如在每個 free block 內放 pred / succ 指標構成雙向鏈結 free list:

 Allocated block               Free block
+--------------+-----+       +--------------+-----+
|  Block size  | a/f |       |  Block size  | a/f |   Header
+--------------------+       +--------------------+
|                    |       | pred (predecessor) |
|     Payload        |       +--------------------+
|                    |       | succ (successor)   |
+--------------------+       +--------------------+
| Padding (optional) |       |   (old payload)    |
+--------------------+       +--------------------+
|  Block size  | a/f |       |  Block size  | a/f |   Footer
+--------------+-----+       +--------------+-----+

• first-fit 配置時間:從「總 block 數線性」降為「free block 數線性」。
• free 的時間取決於 list 的排序政策:

• 缺點:free block 必須裝得下所有指標 + header (+ footer) → 最小 block size 變大,增加 internal fragmentation 的可能。

9.9.14 Segregated Free Lists (p.899)

Segregated storage:維護多條 free lists,每條放大小相近的 blocks——把所有可能的 block size 分割成 size classes(等價類)。例如以 2 的冪分割:

$\{1\},\{2\},\{3,4\},\{5\text{–}8\},\dots ,\{1025\text{–}2048\},\{2049\text{–}4096\},\{4097\text{–}\mathrm{\infty }\}$

或小 blocks 各自成類、大 blocks 以 2 的冪分割。配置器維護一個 free list 陣列(依 size 遞增排列);要 size n 的 block 時搜尋對應的 list,不夠就搜尋下一個更大的 class。

Simple Segregated Storage (p.900)

每個 size class 的 free list 只含同一大小的 blocks(= 該 class 的最大元素;如 class {17–32} 的 list 全是 32-byte blocks)。

• 配置:對應 list 非空 → 直接拿第一個 block 整塊使用(從不 split);list 空 → 向 OS 要固定大小 chunk(通常是 page size 倍數),切成等大 blocks 串成新 list。
• 釋放:直接把 block 插回對應 list 開頭(從不 coalesce)。
• 優點:allocate/free 皆快速常數時間;同 chunk 內 blocks 等大 → 由位址即可推得 size;不 coalesce → allocated block 不需 header 也不需 footer;list 只在頭端插刪 → 單向鏈結即可。唯一必要欄位是 free block 內 1 word 的 succ 指標 ⇒ 最小 block size = 1 word。
• 缺點:易受 internal fragmentation(不 split)與極端 external fragmentation(不 coalesce;Practice 9.10:反覆 malloc/free 交替 pattern 會讓某 size class 累積大量永不重用的 free blocks)。

Segregated Fits (p.900)

每條 free list 對應一個 size class,內含該 class 中各種大小的 blocks(explicit 或 implicit list)。

• 配置:決定 request 的 size class → 對該 list first-fit 搜尋 → 找到就(選擇性)split,碎片插回適當 list;找不到就搜尋下一個更大 class;全部都沒有才向 OS 要記憶體,配置後把剩餘放入適當 class。
• 釋放:coalesce 後放回適當的 free list。
• 是 GNU malloc(C 標準函式庫)等 production-quality 配置器的選擇:又快又省記憶體——搜尋侷限在 heap 的特定部分;且 segregated list 上的簡單 first-fit 搜尋近似整個 heap 的 best-fit 搜尋,utilization 佳。

Buddy Systems (p.901)

segregated fits 的特例:每個 size class 都是 2 的冪。heap 為 $2^m$ words,為每個 $2^k$($0\le k\le m$)維護 free list;請求大小向上取整到最近的 2 的冪。

allocate 2^k:
  找最小的可用 2^j (k <= j <= m)
  j == k ? 完成
         : 反覆對半分割直到 j == k,
           每次分出的另一半 (buddy) 放入對應 free list

free 2^k:
  與 free 的 buddy 持續合併,遇到 allocated buddy 即停止

關鍵性質:由 block 的位址與大小可直接算出 buddy 的位址——兩者恰好差一個 bit。例:size 32 bytes、位址 xxx...x00000 的 block,其 buddy 在 xxx...x10000。

• 優點:搜尋與合併都快。
• 缺點:size 必須是 2 的冪 → 可能嚴重 internal fragmentation,不適合通用 workload;適合 block sizes 已知為 2 的冪的特定應用。

各種 Free List 組織比較

Exam/Test Patterns

Related Notes

• 09-Virtual-Memory/04-Memory-Mapping
• 09-Virtual-Memory/06-Garbage-Collection-and-Memory-Bugs
• 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching
• 09-Virtual-Memory/Practice-Virtual-Memory
• 07-Linking/03-Executable-Loading-and-Dynamic-Linking
• 03-Machine-Level-Programs/05-Arrays-and-Data-Structures