在這篇文章中我將帶著大家實現一個自己的內存分配器。這個內存分配器 十分簡單 ，它旨在幫助大家對操作系統內部的內存分配過程有更深的理解。所以它並不會很高效。簡單的說，這個內存分配器 只是能用 (Just works)。
我們主要會使用 C 語言來進行編程。但在編程前，我們首先要對我們操作系統的內存存儲方式有一定的了解。
操作系統的內存存儲#
我們的操作系統的內存中，主要存在著 5 個部分。這 5 個部分分別是：
kernel: 存儲著我們的操作系統的內核。stack: 存儲著程序的變量。heap: 存儲著程序動態申請的內存。data: 存儲著靜態變量。text: 存儲著程序的代碼段。
其中，相對動態的 heap 和 stack 的大小是不固定的，heap 可以往上（往 高 內存地址）生長，stack 可以往下（往 低 內存地址）生長。所以當我們在 C 中使用 malloc 等命令時，實際上就是 heap 區域往上生長了一點。我們可以從圖中看出在 heap 的頂部有一個 brk 指針，這個指針限定了 heap 的區域範圍。所以當我們要 malloc 一段新內存的時候，就是把 brk 指針往上移。移動 brk 的過程在 Unix/Linux 系統下有一個專門的函數叫做 sbrk。這個函數有 3 個用法：
sbrk(0)會返回當前的brk地址。sbrk(n)會將brk向上擴展n個字節。這裡n是正數。sbrk(-n)會將brk向下擴展n個字節。這裡n是正數。
sbrk() 分配成功的話會返回分配的區域的啟始地址。若 sbrk() 內存分配失敗，它會返回 (void *) -1 （即 0xFFFFFFFF）
sbrk()實際上已經被現代操作系統給棄用了，因為已經有了更好的內存分配方法，例如mmap()。但由於sbrk()簡單且直觀，所以我們在這裡仍然使用sbrk()來做內存分配。
實現 malloc(size_t size)#
malloc(size_t size) 接受一個參數代表需要分配的內存大小。我們很直觀的就可以想到是不是直接調用 sbrk(size) 就完事兒了？
確實，直接調用的話可以分配出新的內存，但當我們使用完這段內存，對它進行 free() 釋放的時候就出問題了。因為我們不知道這一段需要被釋放的內存有多大，所以我們沒有辦法釋放。
另外，由於 brk 指針是始終指向 heap 的頂部的，而我們是通過調整 brk 的位置來將內存還給操作系統。所以我們其實只能 真正釋放 （還給操作系統）處於 heap 頂部的內存分配，中間的內存其實是很難被真正釋放的（你可以做一個整體遷移，但這樣消耗太大了）。雖然我們無法真正釋放處於中間的內存，但我們可以把它們有效的利用起來，即 標記被釋放的內存，使這一段內存可以被另一段程序給「分配」 。所以，我們 malloc 的時候實際上包括一個循環所有我們所有已經分配的內存，查詢其是否被釋放以及其大小是否足夠滿足我們要求的過程。
最後，sbrk() 命令並不是只有我們才可以調用，而是任何程序都可以調用。所以在我們分配一段內存的時候，完全有可能出現另一個程序也來分配一段內存的情況。換句話說，我們沒有辦法保證我們分配的內存在物理地址上是連續的， 這將使我們在上一段所說的「循環」過程無法進行 。所以我們要通過 鏈表 的方式把我們分配的每一段內存鏈接起來。
所以我們在 malloc 時要把關於這一段分配的內存的一些必要信息一起寫入。準確的講是寫在分配的內存的前面。這些必要信息包括 分配的內存大小，是否被釋放 以及 下個內存分配的地址。
struct header_t {
size_t size;
unsigned is_free; /* shorthand for unsigned int */
union header *next; /* linked list for our heap */
}
然後，為了方便處理，我們希望我們所有分配的內存的頭部信息的大小是相同的。所以我們要做一個對齊，使所有頭部信息的大小都是 16 比特。
typedef char ALIGH[16]; /* ALIGH is 16 bits */
union header {
struct {
size_t size;
unsigned is_free; /* shorthand for unsigned int */
union header *next; /* linked list for our heap */
} s;
ALIGH stub;
};
typedef union header header_t; /* so header_t will have a fixed 16 bytes size */
為了方便循環鏈表和釋放，我們還要有兩個指針來指向鏈表的頭部和尾部。
/* a head and tail pointer to track our heap */
header_t *head, *tail;
最後，我們為了避免競爭，還要引入 互斥鎖。
/* set a mutex lock to prevent concurrently accessing memory */
pthread_mutex_t global_malloc_lock;
這樣，我們就終於可以來完成我們的 malloc() 函數了。
header_t *get_free_block(size_t size);
/* sbrk(0) => return the current address of program break
* sbrk(x) => increase brk by x bytes
* sbrk(-x) => decrease brk by x bytes
* if sbrk() fails, it will return (void *) -1 / 0xFFFFFFFF
* */
void *malloc(size_t size) {
if (!size) /* if the requested size is zero, return */
return NULL;
size_t total_size; /* header size + block size */
void *block;
header_t *header;
pthread_mutex_lock(&global_malloc_lock); /* acquire the lock */
header = get_free_block(size); /* check if there have available free block that has a size of bigger than ‘size’ */
if (header) { /* exists */
header -> s.is_free = 0; /* this block is not free */
pthread_mutex_unlock(&global_malloc_lock); /* release the lock */
return (void *)(header + 1); /* return the address of the block instead of the header */
}
total_size = sizeof(header_t) + size; /* not exists, we have to create one */
block = sbrk(total_size);
if (block == (void *) -1) { /* malloc failed */
pthread_mutex_unlock(&global_malloc_lock); /* release the lock */
return NULL;
}
header = block;
header -> s.size = size;
header -> s.is_free = 0;
header -> s.next = NULL;
if (!head) /* if the head pointer of the heap not exists, make header be the head */
head = header;
if (tail) /* if the tail pointer of the heap exists, */
tail -> s.next = header;
tail = header; /* make this header be the tail (or the new tail) */
pthread_mutex_unlock(&global_malloc_lock); /* release the lock */
return (void *)(header + 1); /* return the address of the block instead of the header */
}
header_t *get_free_block(size_t size) {
header_t *curr = head;
while (curr) {
if (curr -> s.is_free == 1 && curr -> s.size >= size)
return curr;
curr = curr -> s.next;
}
return NULL;
}
malloc() 的流程如下：首先檢驗傳入的參數 size 是否合法。若合法，則繼續嘗試取得互斥鎖。成功得到鎖🔒後，通過 get_free_block() 尋找內存分配鏈表中的被釋放的、空間足夠大的內存塊。若找到了，則將其標記為未釋放，然後釋放互斥鎖，返回這塊內存地址。 注意這裡 (void *)(header + 1) 的意思是返回分配的 內存塊 地址，因為 header 是頭部信息的地址，頭部信息又占用 16 比特。另一方面，如果沒有在已分配的內存中找到合適的內存塊，我們就需要通過 sbrk 新申請一塊。這裡我們申請的大小等於我們的頭部信息大小和內存塊大小之和。申請若成功，則將其鏈接到我們的鏈表上，返回內存塊地址。
實現 free(void *block)#
free(void *block) 接受內存塊的地址，並將其釋放。釋放策略如下：如果這塊內存剛好在鏈表的末尾，即 brk 上，我們可以調用 sbrk() 把這塊內存還給操作系統。若這塊內存在鏈表中間，則我們簡單的將其標記為「釋放」。
/* if the block-to-be-freed is at the end of the heap, then we return it to the OS.
* otherwise we simply mark it as ‘free’
* */
void free(void *block){
header_t *header, *tmp;
void *programbreak;
if (!block) /* if this block not exists */
return;
pthread_mutex_lock(&global_malloc_lock);
header = (header_t *)block - 1; /* header address */
programbreak = sbrk(0); /* get current brk location */
if ((char *)block + header -> s.size == programbreak) { /* this is the end of the heap */
if (head == tail) { /* currently there is only one block in the heap, we will erase it */
head = tail = NULL;
} else { /* otherwise we will remove the tail */
tmp = head;
while (tmp) {
if (tmp -> s.next == tail) {
tmp -> s.next = NULL;
tail = tmp;
}
tmp = tmp -> s.next;
}
}
/* release the space */
sbrk(0 - sizeof(header_t) - header -> s.size);
pthread_mutex_unlock(&global_malloc_lock);
return;
}
/* if this block is in the middle of our heap, we mark it as ‘free’ */
header -> s.is_free = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
這段代碼中，(header_t *)block - 1 的意思是將內存塊地址映射到 header * 後，-1 得到頭部信息的地址。 (char *)block 是內存塊的初始地址，初始地址加上內存塊大小就是終止地址，若終止地址被 brk 指著說明這塊內存是可以被釋放給操作系統的。釋放時注意還要更新鏈表。
這樣，內存分配中核心的兩個函數就被我們實現了。接下來我們繼續實現兩個非常有用的函數：calloc 和 realloc
實現 calloc(size_t num, size_t nsize)#
calloc(size_t num, size_t nsize) 接受一個數量參數 num 和一個大小參數 nsize，然後分配 num 個 nsize 大小的內存塊，並將所有分配的內存賦 0 然後將初始地址返回。
/* calloc allocates ‘num’ elements with size of ‘nsize’.
* */
void *calloc(size_t num, size_t nsize) {
if (!num || !nsize)
return NULL; /* num and nsize must be valid */
size_t size;
void *block;
size = num * nsize;
if (nsize != size / num)
return NULL; /* multiply overflow */
block = malloc(size);
if (!block)
return NULL; /* malloc failed */
memset(block, 0, size); /* reset all value in this block */
return block;
}
值得注意的是中間有一個判斷溢出的過程。其他的應該問題都不大。
實現 realloc(void *block, size_t size)#
realloc(void *block, size_t size) 將一個內存塊重新分配大小。實際上這裡的邏輯是這樣的：若重新分配的大小 小於等於 原來的內存塊大小，那麼函數直接返回原來的內存塊地址，即不動它。若重新分配的大小 大於 原來的內存塊大小，則調用 malloc 新分配一塊內存塊，然後將原來的內存塊裡的內容複製過去，再返回新的內存塊地址。
/* change the given block’s size
* */
void *realloc(void *block, size_t size){
if (!block || !size) /* block and size must be valid */
return NULL;
header_t *header;
void *ret;
header = (header_t *)block - 1;
if (header -> s.size >= size) /* if the original block already has enough space for the data */
return block;
ret = malloc(size); /* allocate a new space */
if (ret) {
memcpy(ret, block, header -> s.size); /* move data in block to ret */
free(block); /* free original block */
}
return ret;
}