4、动态内存分配器实现：malloc/free 核心算法、内存碎片整理策略

动态内存分配，说白了就是让程序在运行时能按需申请和释放内存。在嵌入式世界里，这玩意儿是个双刃剑——用好了灵活高效，用不好就是死机、内存泄漏、碎片爆炸。我早年做的一个工业控制器项目，就因为一个malloc没处理好，导致设备在客户现场跑了三天后突然挂掉。嗯，从那以后我对动态内存分配器的设计就格外较真。

4.1 动态内存分配的核心挑战

嵌入式环境下的动态内存分配，跟PC上那套完全不是一回事。你想想看，我们的资源就那么点，RAM可能只有几十KB甚至几KB，没有MMU，没有虚拟内存，更没有操作系统帮你兜底。

核心挑战就三个：

• 实时性：分配和释放的时间必须是确定的，不能有不可预测的延迟
• 碎片化：频繁分配释放会导致内存碎片，最终明明有空间却分配不出来
• 可靠性：内存泄漏、野指针、重复释放，任何一个都能让系统崩溃

4.2 malloc/free 核心算法

市面上主流的动态内存分配算法有好几种，但真正适合嵌入式场景的，我个人认为就两种：空闲链表法和伙伴算法。咱们一个一个说。

4.2.1 空闲链表法（Free List）

这是最基础也是最直观的方法。核心思路是：维护一个空闲内存块的链表，每个节点记录块的大小和下一个空闲块的地址。malloc时遍历链表找合适的块，free时把块插回链表。

我习惯用首次适应（First Fit）策略，因为它速度快，而且对缓存友好。代码实现大概是这样的：

typedef struct free_block {
    size_t size;                // 块大小（包含头部）
    struct free_block *next;    // 下一个空闲块
} free_block_t;

// 内存池起始地址和大小
static free_block_t *free_list = NULL;
static void *heap_start = NULL;
static size_t heap_size = 0;

void *my_malloc(size_t size) {
    // 对齐到4字节
    size = (size + 3) & ~3;
    // 加上头部大小
    size += sizeof(free_block_t);

    free_block_t *prev = NULL;
    free_block_t *curr = free_list;

    while (curr) {
        if (curr->size >= size) {
            // 找到合适的块
            if (curr->size > size + sizeof(free_block_t) + 4) {
                // 分裂：剩余空间足够形成一个新空闲块
                free_block_t *new_block = (free_block_t *)((char *)curr + size);
                new_block->size = curr->size - size;
                new_block->next = curr->next;
                curr->size = size;
                if (prev) {
                    prev->next = new_block;
                } else {
                    free_list = new_block;
                }
            } else {
                // 不分裂，直接移除
                if (prev) {
                    prev->next = curr->next;
                } else {
                    free_list = curr->next;
                }
            }
            // 返回用户数据区
            return (void *)((char *)curr + sizeof(free_block_t));
        }
        prev = curr;
        curr = curr->next;
    }
    return NULL; // 分配失败
}

4.2.2 伙伴算法（Buddy System）

伙伴算法是另一种经典方案。它把内存按2的幂次分成不同大小的块，分配时向上取整到最近的2的幂，释放时尝试合并相邻的“伙伴”块。

它的好处是：碎片可控、合并速度快。坏处是：内部碎片严重——你申请33字节，它给你64字节的块，浪费了将近一半。

特性	空闲链表法	伙伴算法
分配速度	O(n)，n为空闲块数	O(log N)，N为内存大小
释放速度	O(1) 或 O(n)	O(log N)
外部碎片	较多	较少
内部碎片	较少	较多（2的幂对齐）
实现复杂度	低	中
适用场景	通用嵌入式	实时性要求高、分配大小规律

我个人在大多数项目中都用空闲链表法，因为它简单、可控。只有在需要硬实时保证的场景下，我才会用伙伴算法——比如飞行控制器的任务栈分配。

4.3 内存碎片整理策略

碎片是动态内存分配的头号敌人。你想想看，明明总空闲空间还有10KB，但最大连续块只有1KB，这时候你申请2KB就会失败。这就是碎片导致的“假性内存不足”。

我经历过最惨的一次：一个通信协议栈跑了72小时后，malloc突然返回NULL，但实际空闲内存还有40%。查了两天才发现是碎片问题。从那以后，我在每个项目里都会做碎片防御。

4.3.1 碎片产生的原因

• 分配大小不规律：一会儿申请8字节，一会儿申请128字节
• 释放顺序错乱：先分配的块后释放，导致中间出现空洞
• 长时间运行：碎片会随着时间累积，最终不可用

4.3.2 碎片整理的常用策略

策略一：内存压缩（Compaction）

这是最彻底的方案。把所有已分配的内存块移动到一端，空闲块合并到另一端。但代价很大——需要暂停所有任务，搬运数据，更新指针。我一般只在系统空闲时做，或者作为最后的“救命稻草”。

策略二：分桶管理（Segregated Free List）

把空闲块按大小范围分到不同的链表里。比如8-16字节一个桶，17-32字节一个桶，以此类推。这样分配时直接去对应桶里找，速度快，而且能减少碎片。

策略三：固定大小块分配

如果业务场景中申请的内存大小是固定的几种，那就干脆用固定大小块池。比如网络协议栈里，MTU大小的包就用固定块池。这能从根本上杜绝碎片。

4.4 动态内存分配器架构总览

下面这张图是我设计动态内存分配器时常用的架构。它把分配、释放、碎片管理三个模块分开，每个模块只做一件事。

4.5 实战建议：如何选择分配器

说了这么多，到底该用哪种方案？我个人的选择标准是这样的：

1. 如果内存小于64KB：用空闲链表法+首次适应。简单可靠，代码量小。
2. 如果内存大于64KB且分配大小规律：用伙伴算法。碎片少，速度快。
3. 如果分配大小固定：用固定块池。没有碎片，没有外部碎片，性能最好。
4. 如果系统需要长时间运行：必须加碎片整理机制。分桶+定期压缩是常见组合。