您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言記憶體管理深度解析：malloc 實作原理與自由鏈表

編輯：關於C

K&R《C程式設計語言》第八章：儲存分配器實作詳解

標準庫 malloc/free 的經典教學實作：隱式自由鏈表、首次適應演算法、記憶體對齊、分割與合併機制。

核心資料結構：區塊頭部

typedef long Align; // 強制對齊到最嚴格類型邊界

union header {
    struct {
        union header *ptr; // 下一個自由區塊指標
        unsigned size;     // 區塊大小 (含頭部，單位：Header)
    } s;
    Align x; // 強制聯合體對齊
};
typedef union header Header;

static Header base;        // 空鏈表錨點
static Header *freep = NULL; // 自由鏈表游標

malloc 核心流程

void *malloc(unsigned nbytes) {
    Header *p, *prevp;
    unsigned nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    // +1 為頭部空間
    
    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->s.size = nunits;
            }
            freep = prevp; // 下次從這裡開始搜尋 (首次適應優化)
            return (void*)(p + 1); // 回傳頭部之後的資料區
        }
        if (p == freep) // 繞完一圈未找到
            if ((p = morecore(nunits)) == NULL)
                return NULL; // 向系統要記憶體失敗
    }
}

morecore：向作業系統申請記憶體

#define NALLOC 1024 // 最小申請單位

Header *morecore(unsigned nu) {
    if (nu < NALLOC) nu = NALLOC;
    char *cp = sbrk(nu * sizeof(Header)); // 系統呼叫擴展資料段
    if (cp == (char*)-1) return NULL;
    
    Header *up = (Header*)cp;
    up->s.size = nu;
    free((void*)(up + 1)); // 將新記憶體加入自由鏈表
    return freep;
}

free：釋放與合併

void free(void *ap) {
    Header *bp = (Header*)ap - 1; // 回頭找頭部
    Header *p;
    
    // 找到插入位置：按位址排序的循環鏈表
    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;
}

關鍵設計精華

機制	設計	優勢
隱式鏈表	區塊頭部串聯所有自由區塊	無額外記憶體開銷
首次適應	從上次位置搜尋第一個夠大的	快速、殘留大區塊供大分配
邊界標記合併	釋放時檢查前後鄰居是否自由	減少外部碎片、O(1) 合併
對齊保證	聯合體含最嚴格類型	滿足所有類型對齊需求
分割策略	高位址分割歸還，低位址留在鏈表	簡化合併邏輯