在这篇文章中，叙述了如何实现 malloc, calloc, realloc 和 free。在构建内存分配器之前，首先需要了解一个进程的内存布局：
text 段储存了编译为汇编的代码
data 段储存了初值不为零的静态数据
bss(Block Started by Symbol) 储存了初值为零的静态数据
heap 段储存了手动分配的内存。向上增长
stack 段储存了程序自动分配的内存，向下增长
就像栈顶指针指向了栈的顶部一样，brk 指针指向了堆区的末尾。在这片文章中，使用 sbrk 系统调用来分配内存。sbrk 有三种调用方法：
| 更推荐的方式是使用 mmap 分配内存。sbrk 系统调用在 MacOS 上标记为废弃。尽管如此，libc 依然使用 sbrk 用来分配一些比较小的内存。 |
sbrk(0) 用来获取当前 brk 指针的位置
sbrk(|x|) 用来将 brk 指针向上移动 |x| 个位置。也就是分配内存。
sbrk(-|x|) 用来将 brk 指针向下移动 -|x| 个位置。也就是释放内存。
一个简单的 mem_alloc 如下：
void *mem_alloc(size_t size){
void *block = sbrk(size);
if (block == (void*) -1)
return nullptr;
return block;
}mem_alloc 很简单，但是 mem_free 并不是这样，因为：
mem_free 必须知道需要释放的内存的大小
mem_free 只能从堆区末尾释放内存
以下是两个问题的解决方案：
对于第一点。我们建立一个链表，在链表节点中储存内存的大小
对于第二点。我们区分 release memory 和 free memory。当我们调用 mem_free 的时候，我们只是简单地在链表中将这块内存标记为 未使用 。当且仅当释放的内存是链表的最后一个节点时，我们才调用 sbrk 将内存归还给系统
另外，为了线程安全性，我们创建一个全局锁，在分配内存和释放内存时进行加锁。
链表节点的定义如下：
struct alignas(16) header_t {
size_t size = 0;
bool is_free = true;
header_t* next = nullptr;
};现在，如果我们分配一个内存，，其这块内存的实际布局为：
这样，mem_alloc 如下：
std::mutex global_mem_lock; (1)
header_t* mem_header = nullptr; (2)
header_t* get_free_block(size_t size) {
auto curr = mem_header;
while(curr) {
if(curr->is_free && curr->size >= size) {
return curr;
}
curr = curr->next;
}
return nullptr;
}
void* mem_alloc(size_t size) {
if(!size) return nullptr;
std::unique_lock<std::mutex> lock(global_mem_lock); (3)
auto header = get_free_block(size); (4)
if(header) {
header->is_free = false;
return (void*)(header + 1);
}
header = (header_t*)sbrk(sizeof(header_t) + size); (5)
if(header == (void*)-1) {
return nullptr;
}
header->size = size;
header->is_free = false;
header->next = nullptr;
if(!mem_header) {
mem_header = header;
}
return (void*)(header + 1);
}| 1 | 全局内存锁 |
| 2 | 链表头节点 |
| 3 | 在进行内存分配动作之前首先进行加锁操作 |
| 4 | 首先检查链表中是否有满足条件的空闲节点 |
| 5 | 未找到满足条件的空闲节点时才进行实际的内存分配操作 |
从上面的代码中可以看出，在查找空闲节点的时候使用的是 最先适应算法 ，而且不对空闲节点进行合并，从而简化了实现。
mem_free 代码如下：
void mem_free(void* block) {
if(!block) return;
std::unique_lock<std::mutex> lock(global_mem_lock);
auto header = (header_t*)block - 1;
void* brk_pos = sbrk(0);
if((char*)block + header->size < brk_pos) {
header->is_free = 1;
return;
}
// 释放的位置位于 brk 位置，进行实际释放动作
if(!mem_header->next) { // 释放的是最后一个节点
mem_header = nullptr;
} else { // 释放的只是尾节点
auto parent = mem_header;
while(parent && (parent->next != header)) {
parent = parent->next;
}
parent->next = nullptr;
}
sbrk(-sizeof(header_t) - header->size);
}mem_calloc 和 mem_realloc 也类似：
void* mem_calloc(size_t num, size_t nsize) {
if(!num || !nsize) return nullptr;
auto block = mem_alloc(num * nsize);
bzero(block, num * nsize);
return block;
}
void* mem_realloc(void* block, size_t size) {
if(!block) {
return mem_alloc(size);
}
if(!size) {
mem_free(block);
return nullptr;
}
auto header = (header_t*)block - 1;
if(header->size >= size) return block;
auto new_block = mem_alloc(size);
if(new_block) {
memcpy(new_block, block, size);
}
mem_free(block);
return new_block;
}