在这篇文章中我将带着大家实现一个自己的内存分配器。这个内存分配器 十分简单 ，它旨用于帮助大家对操作系统内部的内存分配过程有更深的理解。所以它并不会很高效。简单的说，这个内存分配器 只是能用 (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;
}