C/C++ 基礎：malloc 函數工作機制與空閒鏈表深度解析

malloc 是 C 語言動態記憶體分配的核心函數，理解其底層的 空閒鏈表 機制，能幫你寫出更高效、更少碎片的程式，也能在面試中脫穎而出。本文從原型、用法切入，深入剖析分配/釋放流程、碎片整理策略與常見坑點。

一、基本原型與用法

void *malloc(size_t size);  // 分配 size 位元組，成功返回指標，失敗返回 NULL
void free(void *ptr);       // 釋放 ptr 指向的記憶體塊

頭檔：<stdlib.h> (C) / <cstdlib> (C++)。C++ 建議優先使用 new/delete 或智慧指標。

二、空閒鏈表核心機制

堆內部維護一個 雙向循環鏈表，每個節點記錄：size、is_free、prev/next 指標。初始只有一個大塊「荒野區塊」。

分配流程

1. 首次適配/最佳適配：遍歷鏈表尋找 size ≥ 請求大小 + 元資料 的空閒塊。
2. 分塊：若剩餘空間足夠大（通常 > 16 位元組），將其分為「已分配塊」+「新空閒塊」。
3. 標記與返回：將前半塊標記 is_free = false，返回使用者可用地址（跳過元資料頭）。

釋放流程

1. 根據指標回推元資料頭，標記 is_free = true。
2. 鄰塊合併：檢查前後相鄰塊是否空閒，若是則合併為更大塊（更新 size、修正鏈表指標）。
3. 合併後的大塊重新掛入空閒鏈表。

三、碎片化與整理策略

長期運行後，空閒鏈表會產生大量細小碎片（外部碎片）。當請求大塊記憶體失敗時，分配器會觸發：

• 延遲合併：掃描整個鏈表，將所有相鄰空閒塊合併。
• 記憶體緊縮：移動已分配塊（需支援重定位，C/C++ 指標語義通常不支援）。
• 向 OS 請求更多記憶體：sbrk/mmap 擴展堆邊界。

四、常見錯誤與最佳實踐

五、malloc vs new/delete

• malloc/free：庫函數，不呼叫建構/解構函數，僅操作原始位元組。
• new/delete：運算子，自動呼叫建構/解構函數，型別安全，可重載。
• 非 POD 型別必須用 new/delete，否則物件未初始化/未清理。

掌握 malloc 的空閒鏈表模型，不只是知其然，更能在設計自定義分配器、排查堆損壞、優化高頻分配場景時，擁有底層視角的直覺判斷力。