uClibc malloc 記憶體分配機制深度解析：堆管理與 FA 結構

uClibc 是嵌入式 Linux 最常用的 C 函式庫，其 malloc 實作採用簡潔的堆管理結構。本文剖析 heap、heap_free_area (FA) 結構、初始化流程、FA 操作巨集、malloc/free 核心邏輯，幫助理解用戶空間記憶體分配器運作。

核心資料結構

struct heap {
    struct heap_free_area *free_areas;  // 空閒區循環鏈表頭
#ifdef HEAP_USE_LOCKING
    pthread_mutex_t lock;               // 多執行緒保護
#endif
};

struct heap_free_area {  // 簡稱 FA
    size_t size;                    // 空閒區大小（含 FA 本身）
    struct heap_free_area *next, *prev;  // 雙向循環鏈表
    // 注意：FA 結構體緊接在空閒區記憶體之後
};

堆初始化

// 全域堆物件
struct heap __malloc_heap = HEAP_INIT_WITH_FA(initial_fa);

// 靜態初始 FA：256 bytes 空閒區 + FA 結構
HEAP_DECLARE_STATIC_FREE_AREA(initial_fa, 256);

// 展開後：
static struct {
    char space[256 - sizeof(struct heap_free_area)];
    struct heap_free_area _fa;
} initial_fa = { "", { 256, 0, 0 } };

• 初始堆僅 256 bytes，後續不足時透過 sbrk/mmap 擴展。
• FA 結構置於空閒區尾部，FA+1 指向空閒區末端。

FA 關鍵操作巨集

FA 鏈表操作

// 從堆移除 FA
extern inline void __heap_delete(struct heap *heap, struct heap_free_area *fa) {
    if (fa->next) fa->next->prev = fa->prev;
    if (fa->prev) fa->prev->next = fa->next;
    else heap->free_areas = fa->next;  // 刪除頭節點
}

// 在 prev 與 next 之間插入 FA
extern inline void __heap_link_free_area(struct heap *heap, struct heap_free_area *fa,
                                         struct heap_free_area *prev, struct heap_free_area *next) {
    fa->next = next; fa->prev = prev;
    if (prev) prev->next = fa; else heap->free_areas = fa;
    if (next) next->prev = fa;
}

malloc 核心邏輯（簡化）

1. 遍歷 heap->free_areas 循環鏈表，尋找 size >= request_size 的 FA。
2. 找到後：
   • 若剩餘空間 ≥ HEAP_MIN_FREE_AREA_SIZE：分割 FA，前段回傳給用戶，後段形成新 FA 插入鏈表。
   • 若剩餘空間 < 最小值：整個 FA 分配出去（內部碎片），從鏈表移除。
3. 若遍歷完無適合 FA：呼叫 __heap_extend() 向 OS 申請新記憶體（sbrk 或 mmap），建立新 FA 插入鏈表，遞迴重試。

free 核心邏輯（簡化）

1. 根據指標計算對應 FA 位址（指標 - sizeof(size_t) 或類似機制）。
2. 檢查前後相鄰 FA 是否空閒，若是則合併（合併前後 FA 為單一大 FA）。
3. 將合併後的 FA 插入 heap->free_areas 鏈表（依位址排序有助減少碎片）。

多執行緒保護

定義 HEAP_USE_LOCKING 時，malloc/free 以 pthread_mutex_lock(&heap->lock) 保護整個操作，確保鏈表操作原子性。

與 glibc malloc 差異

除錯技巧

• MALLOC_CHECK_=1 環境變數啟用一致性檢查。
• mtrace() 追蹤分配/釋放配對。
• 自定義 __malloc_hook/__free_hook 注入記錄邏輯。

理解 uClibc malloc 簡潔設計，有助於嵌入式系統記憶體洩漏排查、碎片分析與自定義分配器開發。