本文介紹如何用c語言實現(xiàn)一個簡單的內(nèi)存分配器病涨，可替換glibc中的 malloc(), calloc(), realloc(), free().

這是一篇入門級別的文章，所以不會介紹所有的細節(jié)允睹。
代碼實現(xiàn)主要為了演示內(nèi)存分配器的基本工作原理，所以和工業(yè)級內(nèi)存分配器相比薄霜，缺少非常多的性能優(yōu)化茎芭，分配內(nèi)存時也不會按頁對齊，但是至少看锉，我們構(gòu)建的內(nèi)存分配器是可以工作的姿锭。

在構(gòu)建內(nèi)存分配器之前，需要先介紹程序的內(nèi)存布局伯铣。操作系統(tǒng)中的進程運行在它自己獨有的虛擬地址空間呻此，不同進程間的虛擬地址空間是獨立、相互隔離的腔寡。虛擬地址空間一般由以下5部分組成：

代碼段（Text section）：包含被處理器執(zhí)行的二進制指令
數(shù)據(jù)段（Data section）：包含程序中已手動初始化的全局靜態(tài)變量和局部靜態(tài)變量
BSS（Block Started by Symbol）段：包含了程序中未手動初始化的全局變量和局部靜態(tài)變量焚鲜。這部分數(shù)據(jù)會被初始化為零值。
堆：包含動態(tài)申請的內(nèi)存
棧：包含了局部變量，函數(shù)參數(shù)等

memlayout

如上圖所示忿磅，棧和堆的增長方向是相反的糯彬。
有時數(shù)據(jù)段、BSS段葱她、堆三個區(qū)域會統(tǒng)稱為"數(shù)據(jù)段"(data segment)撩扒，
它的尾部被一個叫做brk(program break)的指針所指向。
也就是說吨些，brk指向堆的尾部搓谆。

如果我們想在堆上申請更多的內(nèi)存，我們需要向操作系統(tǒng)請求增長brk锤灿。同理挽拔，釋放內(nèi)存時需要向操作系統(tǒng)請求減小brk。

在Linux系統(tǒng)（或其他Unix-like系統(tǒng)）下但校，我們需要使用sbrk()系統(tǒng)調(diào)用來操作程序的brk指針螃诅。

調(diào)用sbrk(0)返回當前brk的位置。
調(diào)用sbrk(x)并傳入正數(shù)表示對brk增長x字節(jié)大小状囱，即分配內(nèi)存术裸。
調(diào)用sbrk(-x)并傳入負數(shù)表示對brk減少x字節(jié)大小，即釋放內(nèi)存亭枷。
如果函數(shù)調(diào)用失敗袭艺，sbrk()將返回(void*)-1。

除了sbrk()叨粘，還可以使用mmap()申請內(nèi)存猾编。sbrk()并不是真正的線程安全。并且它只能按后進先出的順序增長和收縮升敲。
如果你執(zhí)行man 2 sbrk命令查看幫助手冊答倡，它會告訴你：

brk和sbrk是早期虛擬內(nèi)存管理出現(xiàn)之前的歷史遺留產(chǎn)物。

然而驴党，glibc中的malloc依然使用sbrk()來申請小塊內(nèi)存瘪撇，具體可以見The GNU C Library: Malloc Tunable Parameters。
所以港庄，我們也使用sbrk()來實現(xiàn)我們的簡單版本內(nèi)存分配器倔既。

malloc()

malloc(size)函數(shù)申請size字節(jié)大小的內(nèi)存并返回指向所申請內(nèi)存的指針。
第一版代碼實現(xiàn)如下：

void *malloc(size_t size)
{
    void *block;
    block = sbrk(size);
    if (block == (void*) -1)
        return NULL;
    return block;
}

上面的代碼鹏氧，我們指定size調(diào)用sbrk()渤涌。
如果成功，size大小的內(nèi)存在堆上被申請把还。
這很簡單实蓬，然而真是這樣嗎稿存？

問題在于我們?nèi)绾吾尫胚@塊內(nèi)存。
free(ptr)函數(shù)釋放ptr指針指向的內(nèi)存塊時瞳秽，ptr指針必須是之前通過malloc()或calloc()或realloc()調(diào)用返回的指針。
但是釋放一塊內(nèi)存的首先前提是率翅，我們知道這塊內(nèi)存的大小练俐。在上面這個實現(xiàn)中，我們沒有地方獲取關(guān)于大小的信息冕臭。所以腺晾，我們需要某種方法將大小信息存放在某處。
此外辜贵，我們需要理解悯蝉，操作系統(tǒng)所提供的堆內(nèi)存是連續(xù)的。所以我們只能釋放堆尾部的內(nèi)存托慨。我們不能將堆中間的內(nèi)存釋放給操作系統(tǒng)鼻由。你可以把堆想象成一個長條面包，你只能在尾部對它進行伸長或縮短厚棵，但是你必須保證它的完整性蕉世。

為了解決堆里面非尾部內(nèi)存無法釋放的問題，從現(xiàn)在開始我們將區(qū)分兩個概念：freeing內(nèi)存和releasing內(nèi)存婆硬。
freeing一塊內(nèi)存并不強制要求將這塊內(nèi)存歸還給操作系統(tǒng)狠轻。這意味著我們只是把這塊內(nèi)存標記為free（空閑）。這塊被標記為空閑的內(nèi)存可以在稍后被重復使用（比如調(diào)用malloc）彬犯。由于非堆尾部內(nèi)存無法釋放向楼，這是我們目前唯一的釋放方法。
releaseing一塊內(nèi)存則是將這塊內(nèi)存歸還給操作系統(tǒng)谐区。

現(xiàn)在湖蜕，每塊被申請的內(nèi)存塊有兩個信息需要存儲：

1. 大小
2. 內(nèi)存塊是否空閑，可在稍后被重復使用

為了存儲這些信息卢佣，我們?yōu)槊總€新的被申請的內(nèi)存塊添加一個自定義header重荠。
header看起來像這樣：

struct header_t {
    size_t size;
    unsigned is_free;
};

我們的設(shè)計很簡單。當程序申請size字節(jié)大小的內(nèi)存虚茶，我們計算total_size = header_size + size戈鲁，并調(diào)用sbrk(total_size)。再在通過sbrk()申請得到的內(nèi)存空間中放入header和真正的內(nèi)存塊嘹叫。header被內(nèi)部管理婆殿，它對上層應用是完全不可見的。

現(xiàn)在罩扇，我們的每塊內(nèi)存塊看起來像這樣：

node

我們不能百分百肯定通過我們malloc申請的內(nèi)存塊是連續(xù)的婆芦。因為上層應用可以不通過我們的malloc調(diào)用sbrk()怕磨。我們需要有一種手段遍歷我們的所有內(nèi)存塊（為什么需要遍歷？在后文中談free()的實現(xiàn)時會解釋）消约。所以為了記住所有通過我們malloc申請的內(nèi)存塊肠鲫，我們會將這些內(nèi)存塊放入一個鏈表中。現(xiàn)在我們的自定義header格式如下：

struct header_t {
    size_t size;
    unsigned is_free;
    struct header_t *next;
};

內(nèi)存塊鏈表看起來像這樣：

nodes

現(xiàn)在或粮，我們把整個自定義header結(jié)構(gòu)體和一個16字節(jié)大小的占位變量封裝入一個聯(lián)合體中导饲。這使得自定義header在內(nèi)存中占用16個字節(jié)大小。因為聯(lián)合體的大小取決于其中最大元素的大小氯材。自定義header之后緊跟著的就是實際提供給上層應用使用的內(nèi)存塊渣锦。

typedef char ALIGN[16];

union header {
    struct {
        size_t size;
        unsigned is_free;
        union header *next;
    } s;
    ALIGN stub;
};
typedef union header header_t;

我們會有頭尾兩個指針用于記錄整個鏈表。

header_t *head, *tail;

為了防止多個線程并行訪問內(nèi)存氢哮，我們引入了基礎(chǔ)鎖機制——互斥量袋毙。

我們使用一個全局鎖，所有對內(nèi)存的操作都需要獲取這個鎖冗尤，完成操作后釋放這個鎖听盖。

pthread_mutex_t global_malloc_lock;

我們的malloc現(xiàn)在修改成了這樣：

void *malloc(size_t size)
{
    size_t total_size;
    void *block;
    header_t *header;
    if (!size)
        return NULL;
    pthread_mutex_lock(&global_malloc_lock);
    header = get_free_block(size);
    if (header) {
        header->s.is_free = 0;
        pthread_mutex_unlock(&global_malloc_lock);
        return (void*)(header + 1);
    }
    total_size = sizeof(header_t) + size;
    block = sbrk(total_size);
    if (block == (void*) -1) {
        pthread_mutex_unlock(&global_malloc_lock);
        return NULL;
    }
    header = block;
    header->s.size = size;
    header->s.is_free = 0;
    header->s.next = NULL;
    if (!head)
        head = header;
    if (tail)
        tail->s.next = header;
    tail = header;
    pthread_mutex_unlock(&global_malloc_lock);
    return (void*)(header + 1);
}

header_t *get_free_block(size_t size)
{
    header_t *curr = head;
    while(curr) {
        if (curr->s.is_free && curr->s.size >= size)
            return curr;
        curr = curr->s.next;
    }
    return NULL;
}

讓我來對上面這段代碼做個解釋：

首先檢查申請的大小是否為0。如果是0裂七，則返回NULL媳溺。
對于有效的大小，首先獲取鎖碍讯。然后調(diào)用get_free_block() - 這個函數(shù)會遍歷鏈表悬蔽，檢查是否存在已被標記為空閑并且大于申請大小的內(nèi)存塊。這里捉兴，我們按鏈表的順序查找并進行選取蝎困。

如果存在一個大于申請大小的空閑內(nèi)存塊，我們將這塊內(nèi)存標記為非空閑倍啥，釋放全局鎖禾乘，并返回一個指向該內(nèi)存塊的指針。這種情況虽缕，header指針指向剛才遍歷鏈表所找到的內(nèi)存塊始藕。注意，對于上層應用氮趋，我們需要隱藏header的存在伍派。當我們執(zhí)行(header + 1)，指針指向header之后的位置剩胁。也即是真正內(nèi)存塊的起始位置诉植，上層應用感興趣的位置。然后將指針類型轉(zhuǎn)換成(void*)并返回昵观。

如果沒有找到足夠大的空閑內(nèi)存塊晾腔，我們將調(diào)用sbrk()擴展堆舌稀。堆擴展的大小為申請大小加header的大小。因此灼擂，我們首先計算整體大斜诓椤：total_size = sizeof(header_t) + size；然后剔应，我們向操作系統(tǒng)申請增加brk：sbrk(total_size)潮罪。

在剛才向操作系統(tǒng)申請得到的內(nèi)存塊上，我們首先寫入header领斥。在c語言中，void*向其它指針類型轉(zhuǎn)換時不需要強轉(zhuǎn)類型沃暗。所以我們不需要顯式的寫成：header = (header_t *)block月洛；
我們在header中填入上層應用申請的大小（而不是總大心踝丁）嚼黔，并且標記它為非空閑。我們更新header中的next指針指向惜辑，以及全局head和tail的指向唬涧，以保證鏈表為最新狀態(tài)。正如前面所描述的盛撑，我們對上層應用隱藏header碎节，所以返回(void*)(header + 1)。最后抵卫，確保釋放全局鎖狮荔。

free()

現(xiàn)在，我們來看下free()函數(shù)需要做什么介粘。首先殖氏，檢查被釋放的內(nèi)存是否在堆尾部。如果是姻采，我們將這塊內(nèi)存歸還給操作系統(tǒng)雅采。如果不是，我們將它標記為空閑慨亲，期望稍后可以重用它婚瓜。

void free(void *block)
{
    header_t *header, *tmp;
    void *programbreak;

    if (!block)
        return;
    pthread_mutex_lock(&global_malloc_lock);
    header = (header_t*)block - 1;

    programbreak = sbrk(0);
    if ((char*)block + header->s.size == programbreak) {
        if (head == tail) {
            head = tail = NULL;
        } else {
            tmp = head;
            while (tmp) {
                if(tmp->s.next == tail) {
                    tmp->s.next = NULL;
                    tail = tmp;
                }
                tmp = tmp->s.next;
            }
        }
        sbrk(0 - sizeof(header_t) - header->s.size);
        pthread_mutex_unlock(&global_malloc_lock);
        return;
    }
    header->s.is_free = 1;
    pthread_mutex_unlock(&global_malloc_lock);
}

首先，我們需要得到這塊內(nèi)存的header信息刑棵。即得到對應header的地址闰渔。做法很簡單，我們只需要對free傳入地址再向前移動header大小即可铐望。
header = (header_t*)block - 1;

sbrk(0)返回當前brk的位置冈涧。為了檢查被釋放的內(nèi)存塊是否在堆尾部茂附，我們首先找到被釋放的內(nèi)存塊的尾部，使用如下方式計算 (char*)block + header->s.size督弓。然后用它和brk位置比較营曼。

如果確實是堆尾部，那么我們可以收縮堆的大小并將內(nèi)存歸還給操作系統(tǒng)愚隧。首先蒂阱，我們調(diào)整head和tail指針指向。然后狂塘，計算需要釋放的內(nèi)存大小录煤。即header的大小和實際塊的大小：sizeof(header_t) + header->s.size荞胡。為了釋放這塊內(nèi)存妈踊，我們調(diào)用sbrk()并傳入這個值的負數(shù)形式。

如果這塊內(nèi)存不是鏈表的最后一個元素泪漂，我們將header中的is_free字段設(shè)置為1廊营。函數(shù)get_free_block()會檢查這個字段以決定是否需要真正調(diào)用sbrk()。

譯者yoko注萝勤，個人覺得在這個簡單的內(nèi)存分配器實現(xiàn)中露筒，判斷被釋放的內(nèi)存是否是堆尾部，可以直接判斷該內(nèi)存塊是否為鏈表的最后一個元素敌卓。畢竟使用sbrk(0)的方式多了一次系統(tǒng)調(diào)用慎式。
補充說明，鏈表的最后一個元素為堆尾部成立的前提是趟径，程序中所有的動態(tài)內(nèi)存都是由我們自己的內(nèi)存分配器所分配管理瞬捕。用sbrk(0)則沒有這個限制。

calloc()

calloc(num, nsize)函數(shù)申請一個數(shù)組的內(nèi)存舵抹，數(shù)組元素個數(shù)為num肪虎，每個元素的大小為nsize字節(jié)，該函數(shù)返回指向被申請內(nèi)存的指針惧蛹。并且扇救，這塊內(nèi)存內(nèi)部的值都被初始化為0。

void *calloc(size_t num, size_t nsize)
{
    size_t size;
    void *block;
    if (!num || !nsize)
        return NULL;
    size = num * nsize;
    /* check mul overflow */
    if (nsize != size / num)
        return NULL;
    block = malloc(size);
    if (!block)
        return NULL;
    memset(block, 0, size);
    return block;
}

這里香嗓，我們做了個快速的乘法結(jié)果溢出的檢查迅腔，然后調(diào)用malloc()，并且通過memset()函數(shù)將申請的內(nèi)存內(nèi)部的值都初始化為0靠娱。

realloc()

realloc()函數(shù)用于修改內(nèi)存塊的大小沧烈。

void *realloc(void *block, size_t size)
{
    header_t *header;
    void *ret;
    if (!block || !size)
        return malloc(size);
    header = (header_t*)block - 1;
    if (header->s.size >= size)
        return block;
    ret = malloc(size);
    if (ret) {

        memcpy(ret, block, header->s.size);
        free(block);
    }
    return ret;
}

這里，我們首先獲取內(nèi)存塊的header像云，檢查當前的大小是否已滿足被要求的大小锌雀。如果已滿足蚂夕，則什么也不需要做。

如果大小不滿足腋逆，我們調(diào)用malloc()來獲取一塊被要求大小的內(nèi)存塊婿牍，然后使用memcpy()將老內(nèi)存塊的內(nèi)容拷貝至新的內(nèi)存塊上。然后對老內(nèi)存塊調(diào)用free()進行釋放惩歉。

編譯以及使用我們的內(nèi)存分配器

完整代碼見這個github倉庫

我們會先編譯我們的內(nèi)存分配器等脂，然后運行一個使用我們內(nèi)存分配器的程序，比如說ls命令撑蚌。

首先上遥，我們把它編譯成一個動態(tài)庫文件。

$gcc -o memalloc.so -fPIC -shared memalloc.c

-fPIC和-shared選項用于確保編譯輸出的文件的是代碼位置獨立的并且是可被動態(tài)鏈接的動態(tài)庫争涌。

在Linux粉楚，如果你將一個動態(tài)庫文件的路徑設(shè)置在環(huán)境變量LD_PRELOAD中，這個庫文件會優(yōu)先被加載第煮。利用這個特性可以保證我們一會在shell中運行程序時使用我們實現(xiàn)的malloc(),free(),calloc()和realloc()。

$export LD_PRELOAD=$PWD/memalloc.so

然后

$ ls
memalloc.c      memalloc.so

這就是使用我們內(nèi)存分配器的ls運行的結(jié)果抑党。
如果你不相信這一點包警，你可以在malloc()打印一些調(diào)試信息。

感謝閱讀底靠。歡迎評論害晦。

英文原文地址： Memory Allocators 101 - Write a simple memory allocator by Arjun Sreedharan

原文鏈接： https://pengrl.com/p/18873/
原文出處： yoko blog (https://pengrl.com)
原文作者： yoko (https://github.com/q191201771)
版權(quán)聲明： 本文歡迎任何形式轉(zhuǎn)載，轉(zhuǎn)載時完整保留本聲明信息（包含原文鏈接暑中、原文出處壹瘟、原文作者、版權(quán)聲明）即可鳄逾。本文后續(xù)所有修改都會第一時間在原始地址更新稻轨。

本篇文章由一文多發(fā)平臺ArtiPub自動發(fā)布