几种常见的内存分配算法
前言
这段时间关注到微软开发的一个内存分配器mimalloc，感觉很厉害，从官方的 benchmark 看，比tcmalloc提升了7%, 比jemalloc提升了14%，而且它的核心代码只有几千行，看起来是值得好好研究一下。
在研究之前，我专门看了一些内存分配的算法，虽然对这些算法都有了解，但系统学习下来还是获益良多。所以在这篇文章里，我打算先介绍这些基础算法，然后在下一篇再来分析mimalloc的实现。
linear allocator
它的思路是预先创建内存块，然后在内存块上一直分配内存，这些分配出去的内存不用释放，到最后再一次性把内存块回收。
这种分配算法有很大的限制，但在一些特定场景里却很有用，比如一些局部逻辑，你需要创建大量的小对象，而这些对象会在使用完毕后一起释放掉，此时用 linear allocator 就能极大的提高分配效率。
它的核心代码非常简单，只有几十行，如下所示：
// 大的内存块
typedef struct linear_block {
struct linear_block *next;
} linear_block_t;
// 线性分配器
typedef struct linear_allocator {
linear_block_t *header; // 内存块链表头
uint8_t *end;
size_t blksz; // 内存块的大小，包含头结构的
} linear_allocator_t;
// 最小的块大小
#define LINEAR_MIN_BLOCK_SIZE 1024
// 内存块头大小
#define HEADER_SIZE sizeof(linear_block_t)
// 取内存块的Buffer
#define LINEAR_BUFFER(b) ((uint8_t*)(b) + HEADER_SIZE)
// 初始化
static void linear_init(linear_allocator_t *a, size_t size) {
a->blksz = size + HEADER_SIZE < LINEAR_MIN_BLOCK_SIZE ? LINEAR_MIN_BLOCK_SIZE : size + HEADER_SIZE;
a->header = NULL;
a->end = (uint8_t*)HEADER_SIZE; // 此举是为了在分配时减少一次判断
}
// 分配内存器
static inline linear_block_t* _linear_new_block(size_t size) {
return (linear_block_t *)malloc(size);
}
// 分配内存
static void* linear_alloc(linear_allocator_t *a, size_t size) {
if (a->end - LINEAR_BUFFER(a->header) < size) { // 内存不足，分配新的内存块
if (size + HEADER_SIZE > a->blksz) {
// 如果请求的大小比默认内存块大，则尝试创建更大的内存块
linear_block_t *block = _linear_new_block(HEADER_SIZE + size);
uint8_t *buffer = LINEAR_BUFFER(block);
if (a->header != NULL) {
// 如果头结点存在，则加到头结点后面去，这样头结点的内存块下次还能使用
block->next = a->header->next;
a->header->next = block;
} else {
// 如果头结点不存在，则成为头结点
block->next = NULL;
a->header = block;
a->end = buffer;
}
return buffer;
} else {
// 否则正常分配内存块，并成为链表头
linear_block_t *block = _linear_new_block(a->blksz);
block->next = a->header;
a->header = block;
a->end = (uint8_t*)block + a->blksz;
}
}
a->end -= size;
return a->end;
}
// 终止
static void linear_term(linear_allocator_t *a) {
linear_block_t *block = a->header;
linear_block_t *temp;
while (block) {
temp = block;
block = block->next;
free(temp);
}
}代码中有少量注释，仔细看应该不难理解；这个分配器的核心结构可以用下图来表示：
header 总是指向当前可分配的内存块，end指向可用内存的结束点，在分配内存时有两种情况：
- 如果可用内存足够，只需要把end向前移动size，然后把end返回就可以了。
- 如果不够分配，则需要创建一个新的内存块，此时也有两种情况要处理：
- 请求的内存比默认的buffer小：创建一个blksz大小的内存块，将其插入到链表头，将end指向内存块尾；然后跳回第1步。
- 请求的内存比默认的buffer大：创建一个足够大的内存块，将其插入到链表头的下一个；然后直接返回这个内存块。这种情况用下图表示：
fixed size allocator
fixed size allocator顾名思议，只能分配和释放固定大小的内存，其用途要比linear allocator广得多，它的核心思想是预创建内存块，然后将内存块切割成多个固定大小的小块，并将它们链接起来形成一个freelist；分配的时候从 freelist 取出小块返回；释放的时候将小块重新链接回 freelist；如果 freelist 没有多余内存就再创建一个内存大块；如此重复，最终的内存布局像下面这样：
代码也不复杂，甚至比上面的还要简单：
// 内存项
typedef struct fixed_item {
struct fixed_item *next;
} fixed_item_t;
// 内存块
typedef struct fixed_block {
struct fixed_block *next;
} fixed_block_t;
// 内存块头大小
#define FIXED_HEADER sizeof(fixed_block_t)
// 取内存块的Buffer
#define FIXED_BUFFER(b) ((uint8_t*)(b) + FIXED_HEADER)
// 固定大小分配器
typedef struct fixed_allocator {
fixed_block_t *block; // 内存块链表
size_t blocksize; // 内存块大小
size_t itemsize; // 内存项大小
fixed_item_t *freelist; // 可用的内存项链表
} fixed_allocator_t;
#define FIXED_MIN_BLOCK_SIZE 256
#define MIN_ITEM_SIZE 16
// 初始化
static void fixed_init(fixed_allocator_t *a, size_t blocksize, size_t itemsize) {
assert(itemsize + FIXED_HEADER < blocksize);
a->block = NULL;
a->blocksize = blocksize > FIXED_MIN_BLOCK_SIZE ? blocksize : FIXED_MIN_BLOCK_SIZE;
a->itemsize = itemsize > MIN_ITEM_SIZE ? itemsize : MIN_ITEM_SIZE;
a->freelist = NULL;
}
// 结束
static void fixed_term(fixed_allocator_t *alloc) {
fixed_block_t *block = alloc->block;
fixed_block_t *temp;
while (block) {
temp = block->next;
free(block);
block = temp;
}
}
// 分配内存项，由于是固定大小，所以不用指定大小
static void* fixed_alloc(fixed_allocator_t *a) {
if (a->freelist == NULL) {
// 没有可用内存，新建一个大块，加入链表
fixed_block_t *block = (fixed_block_t*)malloc(a->blocksize);
block->next = a->block;
a->block = block;
// 初始化可用项
size_t i;
size_t size = a->blocksize - FIXED_HEADER;
fixed_item_t *item;
for (i = 0; i + a->itemsize <= size; i += a->itemsize) {
item = (fixed_item_t*)(FIXED_BUFFER(block) + i);
item->next = a->freelist;
a->freelist = item;
}
}
// 分配内存
fixed_item_t *item = a->freelist;
a->freelist = a->freelist->next;
return item;
}
// 释放内存项
static void fixed_free(fixed_allocator_t *a, void *item) {
fixed_item_t *bitem = (fixed_item_t *)item;
bitem->next = a->freelist;
a->freelist = bitem;
}
// 取地址偏移
static uintptr_t _get_offset(fixed_allocator_t *a, fixed_item_t *item) {
fixed_block_t *block = a->block;
uint8_t *p = (uint8_t*)item;
while (block) {
if (FIXED_BUFFER(block) <= p && p < (uint8_t*)block + a->blocksize)
return p - FIXED_BUFFER(block);
block = block->next;
}
return 0;
}
static void fixed_print(fixed_allocator_t *a) {
printf("========================================\n");
fixed_item_t *item = a->freelist;
while (item) {
uintptr_t offset = _get_offset(a, item);
printf("(%lu--%lu), ", offset, offset+a->itemsize-1);
item = item->next;
}
printf("\n");
}由于只能分配固定大小的内存，它的功能也是受限的。但它却是很多现代内存管理器的重要组成部分，这些管理器会创建很多不同 size class 的 freelist，这样就能快速创建不同大小的小对象。
buddy allocator
另外一种分配器叫伙伴分配器，它比 fixed size allocator 的限制小一些，可以分配不同大小的内存，不过这些大小必须是2的幂；在释放内存的时候，如果这块内存的伙伴内存也处于释放状态，分配器会将两块内存合并起来变成大一倍的内存，并且这个过程会一直重复，直到没有释放的伙伴内存为止。
那么伙伴内存究竟是什么东西呢，可以想象成二叉树里的左右子结点，对于左结点来说右结点就是它的伙伴，对于右结点来说左结点就是它的伙伴。这两个伙伴有一样的大小，且内存连续，所以可以合并成大内存。这就是伙伴分配器的核心思想。
我先贴出代码，能通过代码理解这个算法当然最好，如果不能理解也没关系，后面会通过一些图例来分析。
// 最小的内存池大小
#define MIN_POOL_SIZE 1024
// 最小可分配的块大小
#define MIN_BLOCK_SIZE 16
// 最小可分配块的级别
#define MIN_LEVEL 4
// 内存块
typedef struct buddy_block {
struct buddy_block *next;
} buddy_block_t;
typedef buddy_block_t* buddy_block_p;
// 伙伴分配器
typedef struct buddy_allocator {
uint8_t *pool; // 内存池
uint8_t *base; // 内存池可分配的起始地址
buddy_block_p *freelist; // freelist数组，每一个slot存放一个freelist，内存块尺寸=2^i，i即是slot的索引。
int maxlv; // 最大级
int minlv; // 最小级
} buddy_allocator_t;
// 取块的级别，级别存在块的前一个字节处
#define GET_LEVEL(b) (*((uint8_t*)(b) - 1))
// 计算级别代表的内存大小
#define LEVEL_2_SIZE(lv) (1 << (lv))
// 地址偏移
#define GET_OFFSET(a, b) ((uintptr_t)(b) - (uintptr_t)(a)->base)
// 向上取整到2的幂
static inline uint64_t _roundup_pot(uint64_t v) {
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v |= v >> 32;
return ++v;
}
// 计算大小代表的级别
static inline int _calc_level(size_t size) {
int lv = MIN_LEVEL;
size_t sz = 1 << lv;
while (size > sz) {
sz <<= 1;
lv++;
}
return lv;
}
// 取一个内存块的伙伴内存块：
// |<---block--->|<---buddy--->|
// |<---buddy--->|<---block--->|
static inline buddy_block_t* _get_buddy(buddy_allocator_t *a, buddy_block_t *block, int lv) {
// 取相对地址
uintptr_t offsetaddr = GET_OFFSET(a, block);
// 通过xor即可以取到伙伴的地址，比如：
// 从左孩子取右孩子：offsetaddr=10000, lv=3: buddyaddr = 10000 ^ (1 << 3) = 10000^1000 = 11000
// 从右孩子取左孩子：offsetaddr=11000, lv=3: buddyaddr = 11000 ^ (1 << 3) = 11000^1000 = 10000
uintptr_t buddyaddr = offsetaddr ^ (1 << lv);
// 取绝对地址
return (buddy_block_t*)((uintptr_t)a->base + buddyaddr);
}
// 初始化
static void buddy_init(buddy_allocator_t *a, size_t poolsz, size_t minsz) {
poolsz = poolsz > MIN_POOL_SIZE ? poolsz : MIN_POOL_SIZE;
minsz = minsz > MIN_BLOCK_SIZE ? minsz : MIN_BLOCK_SIZE;
assert(minsz < poolsz);
poolsz = (size_t)_roundup_pot(poolsz);
minsz = (size_t)_roundup_pot(minsz);
a->maxlv = _calc_level(poolsz);
a->minlv = _calc_level(minsz);
// 这里多分配了一个sizeof(void*)，用于将level放到每个分配的block中
a->pool = (uint8_t*)calloc(poolsz + sizeof(void*), 1);
a->base = a->pool + sizeof(void*);
a->freelist = (buddy_block_p*)calloc(a->maxlv + 1, sizeof(buddy_block_p));
a->freelist[a->maxlv] = (buddy_block_t*)a->base;
}
// 结束
static void buddy_term(buddy_allocator_t *a) {
free(a->freelist);
free(a->pool);
}
// 分配
static void* buddy_alloc(buddy_allocator_t *a, size_t size) {
size += 1; // 多1个字节，用于存放level
int lv = _calc_level(size); // 得到该块的级别
// 向后查找可用的内存块，越往后内存块越大
int i = lv;
for (;; ++i) {
if (i > a->maxlv) return NULL;
if (a->freelist[i]) break;
}
// 从链表取出内存块
buddy_block_t *block = a->freelist[i];
a->freelist[i] = a->freelist[i]->next;
// 将内存块一级一级分割，并放入相应的freelist
buddy_block_t *buddy;
while(i-- > lv) {
buddy = _get_buddy(a, block, i);
a->freelist[i] = buddy;
}
// 记录该内存块的level，在free的时候会用到
// 这个level是放在block的前一个字节的
GET_LEVEL(block) = lv;
return block;
}
// 释放
static void buddy_free(buddy_allocator_t *a, void *p) {
buddy_block_t *block = (buddy_block_t*)p;
int i = GET_LEVEL(block);
buddy_block_t *buddy;
buddy_block_t **list;
for (;; ++i) {
// 取当前块的buddy块
buddy = _get_buddy(a, block, i);
// 判断buddy块是否有在freelist中
list = &a->freelist[i];
while ((*list != NULL) && (*list != buddy))
list = &(*list)->next;
if (*list != buddy) {
// 如果没找到buddy块，将block加入freelist
block->next = a->freelist[i];
a->freelist[i] = block;
return;
} else {
// 如果找到，将block和buddy合并成大块
block = block < buddy ? block : buddy;
// 从链表删除，然后继续循环合并块
*list = (*list)->next;
}
}
}
// 打印内存情况
static void buddy_print(buddy_allocator_t *a) {
printf("========================================\n");
for (int i = a->minlv; i <= a->maxlv; ++i) {
buddy_block_t *block = a->freelist[i];
size_t sz = LEVEL_2_SIZE(i);
printf("Lv %-2d (%lu) : ", i, sz);
while (block) {
uintptr_t offset = GET_OFFSET(a, block);
printf("(%lu--%lu), ", offset, offset + sz - 1);
block = block->next;
}
printf("\n");
}
}buddy allocator 使用一个 freelist 数组来存放各个 size 的内存块链表。数组的索引决定了内存块的大小，比如索引为4的槽位放的是 2^4=16 的内存块链表。假如我们创建的大内存是1024，那么一开始索引10的freelist指向了这块内存，其他槽位皆为空：
接下来我们请求分配大小为100的内存，因为只能是2的幂，所以向上取整为128，即等于2^7；这表明该内存要从索引为7的freelist分配，这个freelist现在还是空的，要从更高索引的freelist切割内存过来用，经过一翻切割之后，变成下面这样：
重复再分配3个100的内存之后，变成下面这样：
总共分配出去4块128大小的内存，其中第2块和第3块使用完毕后回收回来；第1块和第2块是伙伴，第3块和第4块是伙伴，所以回收回来的这两个不是伙伴，他们不能合并，只能串成freelist放在7号索引处：
接着第1块内存也释放了，它和第2块内存是伙伴，这两内存都已经释放，可以将它们合并变成一块256的内存，即等于2^8，最终索引8的freelist将指向它：
最后第4块内存也释放了，它和第3块内存是伙伴，3，4块内存合并成256的内存；这块合并完的内存和前面256大小的内存是伙伴，所以又合并变成一块512的内存；这块内存和最后那块512的内存又是伙伴，最终他们神奇的合并回1024的内存，并由索引为10的freelist引用着，也就是最前面那张图的样子。
经过这样的讲解，再结合代码来看是不是一眼了然了呢？代码里还有一些小技巧，比如通过异或得到伙伴的地址，用内存块前面一个字节来存放Level等，这些请通过代码和注释慢慢理解。
buddy allocator 有用在一些著名的内存分配器中，比如jemalloc；另外Linux内核似乎也用这个算法来管理空闲的物理页，这足以说明它是一个很重要的算法。
后记
The C Programming Language 第8.7节介绍了一个内存分配算法，可以分配任意大小的内存，内存回收之后还能合并相领的内存块，看起来似乎是一个通用的内存分配器。不过这个分配器太慢了，分配的时候必须遍历freelist找到合适大小的内存块，释放的时候也须遍历freelist，找到插入的位置，使内存块地址有序，这样才能合并。祖师爷的本意是想通过这个代码来介绍动态内存分配的核心技术；我们回过头来看看上面三个受限的分配器，也能得出内存分配其实是指针和链表的重度应用，通过自己实现一些分配器，你能更加理解指针和链表的操作。
但是，如果要实现一个通用的，高效的现代内存管理器，要考虑的问题就太多了：要抽象OS的内存分配接口，要满足多线程系统的性能要求，还要考虑安全性和可诊断，总之这是一个很有挑战的系统工程。