C 語言 malloc 內存分配器實現原理深度解析

K&R malloc 實現核心邏輯全解析

《C 程序設計語言》第 8 章給出的 malloc/free 簡易實現，展示了動態內存分配器的核心數據結構：**空閒塊鏈表**、header 元數據、**首次適應** 算法。本文逐行解析。

核心數據結構

typedef long Align; // 強制對齊最受限類型 (通常 long/double)

union header {      // 每個塊頭部
    struct {
        union header *ptr; // 下一空閒塊指針
        unsigned size;     // 本塊大小 (含 header，單位：header 個數)
    } s;
    Align x;               // 強制對齊
};
typedef union header Header;

static Header base;        // 空鏈表錨點 (size=0)
static Header *freep = NULL; // 當前掃描起始指針

關鍵點：

• 塊大小以 **Header 個數** 為單位，便於指針算術。
• base 作為永久錨點，freep 記錄上次分配位置，下次從這裡開始掃描 (提高局部性)。
• 用戶可用內存 = 整塊 - 1 個 Header (元數據開銷)。

malloc 核心流程

void *malloc(unsigned nbytes) {
    Header *p, *prevp;
    unsigned nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; // 向上取整 + header

    if ((prevp = freep) == NULL) { // 首次調用初始化
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }

    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) { // 找到足夠大塊
            if (p->s.size == nunits) // 精確匹配：從鏈表摘除
                prevp->s.ptr = p->s.ptr;
            else { // 分割：從尾部割出用戶塊，縮小原塊
                p->s.size -= nunits;
                p += p->s.size;      // p 指向新分配塊的 header
                p->s.size = nunits;
            }
            freep = prevp; // 更新掃描起點
            return (void*)(p + 1); // 返回用戶數據區 (跳過 header)
        }
        if (p == freep) // 掃描一圈回到起點，無足夠塊
            if ((p = morecore(nunits)) == NULL)
                return NULL; // 向系統申請失敗
    }
}

morecore：向系統申請內存

#define NALLOC 1024 // 最小申請單元 (header 個數)

Header *morecore(unsigned nu) {
    if (nu < NALLOC) nu = NALLOC;
    Header *up = (Header*)sbrk(nu * sizeof(Header)); // 系統調用擴展堆
    if (up == (Header*)-1) return NULL;
    up->s.size = nu;
    free((void*)(up + 1)); // 將新塊加入空閒鏈表 (free 會合併相鄰塊)
    return freep;
}

• sbrk 增加進程數據段斷點，獲取原始內存。
• 新塊通過 free 插入鏈表，利用 free 的合併邏輯處理相鄰情況。

free：釋放並合併相鄰塊

void free(void *ap) {
    Header *bp, *p;
    bp = (Header*)ap - 1; // 回退到 header
    // 找到插入位置：按地址升序維護鏈表
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) // 跨越鏈表末尾/開頭
            break;

    // 嘗試與後塊合併
    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;

    // 嘗試與前塊合併
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;

    freep = p; // 更新掃描起點
}

算法特性總結

現代分配器演進

• ptmalloc (glibc)：多 arena、fastbins、smallbins、largebins、tcache (線程緩存)、mmap 大塊直接映射。
• jemalloc：分級分配、CPU 親和性、統計分析、防碎片。
• tcmalloc：線程本地緩存為主、中心頁堆、PageHeap。

理解 K&R 版本是掌握現代高性能分配器設計的基石。

1. 上一篇文章： C 語言細節深度解析：段錯誤、類型提升與 sizeof('A') 的陷阱
2. 下一篇文章： C 語言指針筆試題解析：哪個表達式不能表示 a[1] 的地址？

關於C語言

C# vs Java：語言特性、生態系統與選型決策全方位對比

前言 C# 與 Java 是企業級開發雙雄，語言層面日趨收斂

C# 封裝、多型與物件關係進階：事件驅動、值類型參考類型深度剖析

一、封裝：資訊隱藏與介面隔離 封裝核心在於將實作細節隱藏於類

C語言 printf 深度剖析：可變參數機制、線程安全與源碼實現

C語言 printf 深度剖析：可變參數機制、線程安全與源碼

Linux C 編程：信號集 sigset_t 與操作函數完整指南

信號集資料型別 typedef struct { unsig