4、可变大小内存池设计：伙伴算法(Buddy System)

伙伴算法，说白了就是解决「内存碎片」问题的一把好手。我在做嵌入式系统那几年，最头疼的就是固定大小内存池浪费空间，而普通malloc又容易产生外部碎片。后来接触到伙伴算法，才算是找到了一个不错的平衡点。

嗯，咱们先搞清楚它的核心思想，再一步步看分配和合并是怎么玩的。

伙伴算法的基本原理

伙伴算法的思路其实很朴素：把内存按2的幂次分成块。比如一块64KB的内存，可以分成两个32KB，每个32KB再分成两个16KB，以此类推。这些「成对」出现的块，就是所谓的「伙伴」。

为什么要按2的幂次分？因为这样分出来的块大小规整，合并的时候也方便——两个大小相同、地址连续的块，只要它们是从同一个父块分出来的，就能合并回去。

我当年第一次实现这个算法时，犯了个低级错误——没处理好地址对齐。伙伴的地址必须满足特定关系，否则合并时会出大问题。这个坑我后面会细说。

分配过程：从分裂到交付

假设我们有一个总大小为1MB的内存池，最小块大小为4KB。那么空闲链表数组就有8个元素（2^0到2^7，对应4KB到512KB）。

分配流程是这样的：

1. 计算请求大小对应的最小2的幂次块。比如请求6KB，最小块是8KB（2^3）。
2. 从8KB对应的链表开始找。如果有空闲块，直接取出。
3. 如果8KB链表为空，向上找16KB链表。找到后，把16KB块分裂成两个8KB的伙伴，一个返回给用户，另一个挂到8KB链表。
4. 如果16KB也没有，继续向上找32KB，分裂成两个16KB，其中一个再分裂成两个8KB……直到满足需求。

你看，这个过程有点像「递归向下」。每次分裂都把大块切成两半，直到大小合适。

合并过程：从释放到回收

释放的时候，伙伴算法的精髓才真正体现出来。你想想看，如果只是把块放回链表，那跟普通分配器有什么区别？

合并的关键在于：判断伙伴是否空闲。两个块互为伙伴的条件是：

• 大小相同
• 地址连续
• 它们是从同一个父块分裂出来的

具体怎么判断？用地址做异或运算。假设块大小为S，块起始地址为A，那么它的伙伴地址就是 A ^ S。这个公式很巧妙，因为伙伴的地址只差一个比特位。

释放流程：

1. 把当前块标记为空闲。
2. 计算伙伴地址，检查伙伴是否也是空闲且大小相同。
3. 如果是，把两个块从链表移除，合并成一个大块，然后递归检查合并后的大块是否还能继续合并。
4. 如果伙伴不空闲，直接把当前块挂到对应链表。

位图管理：高效追踪块状态

用链表管理空闲块虽然直观，但合并时查找伙伴的效率是个问题。位图（Bitmap）是另一种常见的管理方式，尤其适合伙伴算法。

位图的核心思想：用1个比特位表示一个块是否被占用。每个层级（不同大小的块）都有一个独立的位图。

层级	块大小	块数量	位图大小
0	4KB	256	32字节
1	8KB	128	16字节
2	16KB	64	8字节
3	32KB	32	4字节
4	64KB	16	2字节
5	128KB	8	1字节
6	256KB	4	0.5字节
7	512KB	2	0.25字节

用位图的好处是：

• 查找伙伴状态只需要O(1)时间——直接读对应比特位
• 内存开销小，1MB内存池的位图总共才几十字节
• 缓存友好，位图通常能塞进CPU缓存

但位图也有缺点：分配时扫描空闲块需要遍历位图，如果内存池很大，这个开销不可忽视。我一般建议位图配合「空闲链表」一起用——链表存空闲块，位图做合并时的快速校验。

伙伴算法的核心流程图

下面这张图展示了分配和合并的完整流程，我画的时候特意把分裂和合并的递归过程拆开了，方便理解。

代码实现要点

这里我给出一个简化版的伙伴算法核心结构，重点展示位图和链表如何配合：

// 伙伴算法内存池结构
typedef struct {
    void *base;           // 内存池基地址
    size_t total_size;    // 总大小
    size_t min_block;     // 最小块大小
    
    // 空闲链表数组，每个层级一个链表
    list_head_t free_lists[MAX_LEVEL];
    
    // 位图数组，每个层级一个位图
    uint8_t *bitmaps[MAX_LEVEL];
    size_t bitmap_size[MAX_LEVEL];
    
    // 层级数量
    int level_count;
} buddy_pool_t;

// 分配接口
void *buddy_alloc(buddy_pool_t *pool, size_t size) {
    // 1. 计算需要的层级
    int level = get_level(size, pool->min_block);
    if (level >= pool->level_count) return NULL;
    
    // 2. 从当前层级向上查找空闲块
    for (int i = level; i < pool->level_count; i++) {
        if (!list_empty(&pool->free_lists[i])) {
            // 3. 取出块，如果需要则分裂
            void *block = list_pop(&pool->free_lists[i]);
            while (i > level) {
                // 分裂：把块切成两半
                void *buddy = block + (1 << (i - 1 + min_shift));
                list_add(&pool->free_lists[i-1], buddy);
                // 更新位图
                set_bit(pool->bitmaps[i-1], get_index(buddy), 0);
                i--;
            }
            // 标记块已分配
            set_bit(pool->bitmaps[level], get_index(block), 1);
            return block;
        }
    }
    return NULL; // 没有足够内存
}

// 释放接口
void buddy_free(buddy_pool_t *pool, void *ptr, size_t size) {
    int level = get_level(size, pool->min_block);
    void *block = ptr;
    
    // 标记为空闲
    set_bit(pool->bitmaps[level], get_index(block), 0);
    
    // 尝试合并
    while (level < pool->level_count - 1) {
        void *buddy = (void *)((uintptr_t)block ^ (1 << (level + min_shift)));
        // 检查伙伴是否空闲
        if (is_buddy_free(pool, level, buddy)) {
            // 从链表移除伙伴
            list_remove(buddy);
            // 合并：取地址较小的块作为新块
            block = (block < buddy) ? block : buddy;
            level++;
        } else {
            break;
        }
    }
    
    // 挂入对应层级链表
    list_add(&pool->free_lists[level], block);
}

伙伴算法的优缺点

说了这么多，咱们客观总结一下：

• 优点：外部碎片少，合并效率高，分配和释放都是O(log N)复杂度。适合大小变化频繁、但总体内存需求可控的场景。
• 缺点：内部碎片依然存在（比如请求6KB给8KB块），而且频繁分裂合并会导致性能抖动。另外，伙伴算法对内存对齐要求严格，不适合非2的幂次大小。

嗯，伙伴算法就讲到这里。它不算完美，但在很多场景下确实好用。你想想看，一个算法能活几十年还在被广泛使用，本身就说明问题了。

---

公众号:蓝海资料掘金营，微信deep3321