内存管理 - 几种常见的内存分配算法 - 《软件开发》

前言
linear allocator
fixed size allocator
buddy allocator
后记

前言

这段时间关注到微软开发的一个内存分配器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);
    }
}

代码中有少量注释，仔细看应该不难理解；这个分配器的核心结构可以用下图来表示：

几种常见的内存分配算法 - 图1

header 总是指向当前可分配的内存块，end 指向可用内存的结束点，在分配内存时有两种情况：

如果可用内存足够，只需要把 end 向前移动 size，然后把 end 返回就可以了。
如果不够分配，则需要创建一个新的内存块，此时也有两种情况要处理：
请求的内存比默认的 buffer 小：创建一个 blksz 大小的内存块，将其插入到链表头，将 end 指向内存块尾；然后跳回第 1 步。
请求的内存比默认的 buffer 大：创建一个足够大的内存块，将其插入到链表头的下一个；然后直接返回这个内存块。这种情况用下图表示：

几种常见的内存分配算法 - 图2

fixed size allocator

fixed size allocator顾名思议，只能分配和释放固定大小的内存，其用途要比linear allocator广得多，它的核心思想是预创建内存块，然后将内存块切割成多个固定大小的小块，并将它们链接起来形成一个freelist；分配的时候从 freelist 取出小块返回；释放的时候将小块重新链接回 freelist；如果 freelist 没有多余内存就再创建一个内存大块；如此重复，最终的内存布局像下面这样：

几种常见的内存分配算法 - 图3

代码也不复杂，甚至比上面的还要简单：

// 内存项
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 指向了这块内存，其他槽位皆为空：

几种常见的内存分配算法 - 图4
接下来我们请求分配大小为 100 的内存，因为只能是 2 的幂，所以向上取整为 128，即等于 2^7；这表明该内存要从索引为 7 的 freelist 分配，这个 freelist 现在还是空的，要从更高索引的 freelist 切割内存过来用，经过一翻切割之后，变成下面这样：

几种常见的内存分配算法 - 图5
重复再分配 3 个 100 的内存之后，变成下面这样：

几种常见的内存分配算法 - 图6

总共分配出去 4 块 128 大小的内存，其中第 2 块和第 3 块使用完毕后回收回来；第 1 块和第 2 块是伙伴，第 3 块和第 4 块是伙伴，所以回收回来的这两个不是伙伴，他们不能合并，只能串成 freelist 放在 7 号索引处：

几种常见的内存分配算法 - 图7
接着第 1 块内存也释放了，它和第 2 块内存是伙伴，这两内存都已经释放，可以将它们合并变成一块 256 的内存，即等于 2^8，最终索引 8 的 freelist 将指向它：

几种常见的内存分配算法 - 图8

最后第 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 的内存分配接口，要满足多线程系统的性能要求，还要考虑安全性和可诊断，总之这是一个很有挑战的系统工程。

原文：https://zhuanlan.zhihu.com/p/369972058