在C++中内存管理是一个老生常谈的话题，我们都知道在C语言中使用malloc和free管理动态内存，C++中也有相应的Allocator；
但究竟内存分配器底层是干什么的，本文通过实现一个简单的内存分配器来管中窥豹；
本文翻译自：
源代码：
【译】实现一个简单的内存分配器
前言
本文将会实现 malloc(), calloc(), realloc() 和 free() 函数；
作为一个简单实现，本文实现的内存分配器不会很快很高效，并且不会对分配的内存进行内存页对齐；
在我们开始之前，需要先补充一些关于程序内存布局的内容：
众所周知，在操作系统中进程都是运行在各自的虚拟内存空间中的，这些内存空间通常分为5个部分：
- Text section：存放编译好的二进制代码指令；
- Data section：存放程序中声明的非零静态数据；
- BSS (Block Started by Symbol) ：存放程序中声明的零静态数据；
- Heap：存放动态数据；
- Stack：存放自动变量（局部变量），函数栈、入参等；
从上图中可以看到，栈和堆从相对的两个方向上生长；
同时，末尾定义了一个指针 brk 来作为整个数据段的结尾（brk 指针指向 Heap 的末尾！）：
- 当我们需要在堆中分配更多内存时，我们需要向操作系统提出申请来增加
brk指针； - 同样的，当我们想要释放内存时，需要减小
brk指针；
假设我们在 类 Unix 操作系统中，可以通过 sbrk() 系统调用来操作；
sbrk(0)：返回当前 brk 指针位置；sbrk(x)：增加 brk x个字节，分配内存；sbrk(-x)：减小 brk x个字节，释放内存；- 发生错误时，
sbrk()返回(void*) -1；
实际上，目前
sbrk()函数已经被废弃！更好的选择应当使用mmap()；
sbrk()函数并非线程安全，并且它分配的内存只能通过 LIFO 的方式增减！如果使用
man 2 sbrk，实际上可以看到：DESCRIPTION The brk and sbrk functions are historical curiosities left over from earlier days before the advent of virtual memory management. The brk() function sets the break or lowest address of a process's data segment (uninitialized data) to addr (immediately above bss). Data addressing is restricted between addr and the lowest stack pointer to the stack segment. Memory is allocated by brk in page size pieces; if addr is not evenly divisible by the system page size, it is increased to the next page boundary.但是在 glic 实现中，malloc 函数依旧使用
sbrk()函数来分配一些比较小的内存！
下面我们使用 sbrk() 函数来实现一个简单的内存分配器！
具体实现
malloc()
结构体定义
malloc(size) 函数分配 size 个字节的内存，并且返回指向这个内存的指针；
简单的实现如下：
void *malloc(size_t size) {
void *block;
block = sbrk(size);
if (block == (void*) -1)
return NULL;
return block;
}在上面的代码中，我们通过调用 sbrk() 函数来分配内存；
虽然实现非常简单，但是上面的代码无法实现我们的 free 函数；
因为 free(ptr) 函数要求释放传入指针指向的内存区域，但是我们在分配内存时，并未保存指针所对应的内存大小；
因此我们还需要一个结构来同时存放分配的指针以及分配的大小；
同时注意到，操作系统分配的堆内存都是连续的，因此我们只能释放掉堆顶部分的内存，而不能直接释放掉位于堆中间的内存区域；
为了解决这个问题，我们将释放的内存分为了两种情况：
- freeing memory：可用内存，位于堆中间，内容被释放但未被返还给操作系统；
- releasing memory：可以返还给操作系统的内存；
因此，释放某块内存并非将内存返还给 OS，而是将内存标记为可用，并且会在后面的 malloc 调用时再次被分配；
所有，到目前为止，我们的内存头应该定义为：
struct header_t {
size_t size;
unsigned is_free;
};当我们申请内存时，我们计算：total_size = header_size + size 并且调用 sbrk(total_size) 来移动 brk；
但是我们不能够保证我们申请的内存是连续的（可能有其他地方在调用 mmap等），因此我们不能简单的通过加减法来确定内存，而是要放在链表中：
struct header_t {
size_t size;
unsigned is_free;
struct header_t *next;
};此时，我们的内存类似于：
最后，让我们把整个内存块包裹在一个 union 中，来确保我们的内存块以 16字节的格式对齐：
typedef char ALIGN[16];
union header {
struct {
size_t size;
unsigned is_free;
union header *next;
} s;
ALIGN stub;
};
typedef union header header_t;函数实现
定义 head、tail 指针来指向整个堆区内存的首尾：
header_t *head, *tail;为了防止多个线程并发的访问内存，使用锁机制：
pthread_mutex_t global_malloc_lock;最后是 malloc 实现：
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，则返回 NULL；
如果请求内存大小合法，则调用 get_free_block()（遍历链表，寻找是否存在可用的内存空间）：
- 如果已经存在了足够大小的内存空间，则标记为不可用，并返回这个空间；
- 如果不存在对应大小的可用空间，则调用
sbrk()函数，向操作系统申请内存空间并返回；
free()
free 函数应当判断：
- 如果需要被释放内存的块位于堆的顶部，则我们向OS返还空间；
- 否则，我们只是标记这个部分空间；
实现如下：
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);
}首先，我们获取到需要释放的内存头（header = (header_t*)block - 1）；同时，sbrk(0) 获取当前程序的堆位置；
为了判断当前被释放的空间是否为堆顶，我们判断：
(char*)block + header->s.size 和 sbrk(0) 的大小即可；
此时，如果：
- 内存块为堆尾，则返还内存到操作系统；
- 否则，仅仅将内存块标识为
is_free即可；
calloc()
calloc(num, nsize) 函数用来申请 num 个大小为 nsize 的内存区域，并且将空间初始化为 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;
}这里，我们使用 nsize != size / num 来快速判断是否溢出！
随后使用 malloc 分配内存，最后使用 memset 清空内存；
realloc()
realloc() 函数用来修改所提供的内存大小；
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;
}首先我们获取到这个内存块的大小，如果内存块大小已经满足要求，则直接返回；
否则，我们先调用 malloc 申请一个更大的内存，然后通过 memcpy 复制内容到新的内存中，并释放原内存空间；
实现测试
静态链接测试
编写 main.cc：
#include <iostream>
extern "C" {
void *malloc(size_t size);
void free(void *block);
void print_mem_list();
}
int main() {
int *p_int = static_cast<int *>(malloc(sizeof(int *)));
*p_int = 1;
std::cout << "Int pointer Address: " << p_int << ", val: " << *p_int << std::endl;
print_mem_list();
double *p_double = static_cast<double *>(malloc(sizeof(double *)));
*p_double = 1.5;
std::cout << "Double pointer Address: " << p_double << ", val: " << *p_double << std::endl;
print_mem_list();
int char_size = 16;
char *p_string = static_cast<char *>(malloc(char_size * sizeof(char)));
for (int i = 0; i < char_size; ++i) {
p_string[i] = 'A' + i;
}
std::cout << "String pointer Address: " << p_string << ", val: " << *p_string << std::endl;
print_mem_list();
free(p_int);
std::cout << "After free int pointer, address: " << p_int << std::endl;
print_mem_list();
free(p_string);
std::cout << "After free string pointer, address: " << p_string << std::endl;
print_mem_list();
free(p_double);
std::cout << "After free double pointer, address: " << p_double << std::endl;
print_mem_list();
return 0;
}运行后输出如下：
Int pointer Address: 0x104dac018, val: 1
head = 0x104dac000, tail = 0x104dac000
addr = 0x104dac000, size = 8, is_free=0, next=0x0
Double pointer Address: 0x104dac038, val: 1.5
head = 0x104dac000, tail = 0x104dac020
addr = 0x104dac000, size = 8, is_free=0, next=0x104dac020
addr = 0x104dac020, size = 8, is_free=0, next=0x0
String pointer Address: ABCDEFGHIJKLMNOP, val: A
head = 0x104dac000, tail = 0x104dac040
addr = 0x104dac000, size = 8, is_free=0, next=0x104dac020
addr = 0x104dac020, size = 8, is_free=0, next=0x104dac040
addr = 0x104dac040, size = 16, is_free=0, next=0x0
After free int pointer, address: 0x104dac018
head = 0x104dac000, tail = 0x104dac040
addr = 0x104dac000, size = 8, is_free=1, next=0x104dac020
addr = 0x104dac020, size = 8, is_free=0, next=0x104dac040
addr = 0x104dac040, size = 16, is_free=0, next=0x0
After free string pointer, address: ABCDEFGHIJKLMNOP
head = 0x104dac000, tail = 0x104dac020
addr = 0x104dac000, size = 8, is_free=1, next=0x104dac020
addr = 0x104dac020, size = 8, is_free=0, next=0x0
After free double pointer, address: 0x104dac038
head = 0x104dac000, tail = 0x104dac020
addr = 0x104dac000, size = 8, is_free=1, next=0x104dac020
addr = 0x104dac020, size = 8, is_free=1, next=0x0动态链接测试
编译为动态库：
$ gcc -o memalloc.so -fPIC -shared memalloc.c-fPIC 和 -shared 选项确保编译后的输出具有位置相关代码，并告诉链接器生成适合动态链接的共享对象；
在Linux上，如果将环境变量 LD_PRELOAD 设置为共享对象的路径，则该文件将在任何其他库之前加载；
我们可以使用此技巧来加载我们的动态链接文件，以便在 Shell 中运行的命令将使用我们的内存分配函数：
export LD_PRELOAD=$PWD/memalloc.so此时再执行命令，将会使用我们的内存分配函数：
ls
memalloc.c memalloc.so README.md一旦完成了实验，可以执行 unset LD_PRELOAD 来停止使用我们的分配器；
附录
源代码：
参考文章：