4、堆内存管理：malloc/free实现原理、内部碎片与外部碎片、堆管理算法

堆内存管理，说白了就是动态内存分配。你写程序时不知道要多大空间，运行时才决定。这时候就得靠 malloc 和 free 这对好兄弟了。

我刚开始做嵌入式时，觉得堆管理很简单——不就是申请释放嘛。直到有一次产品跑着跑着就崩了，查了三天才发现是堆碎片惹的祸。嗯，从那以后我再也不敢小看堆管理了。

4.1 malloc/free 的实现原理

malloc 和 free 不是魔法，它们背后有一套机制在运作。我习惯把堆内存想象成一个大仓库，malloc 就是去仓库里划一块地，free 就是把地还回去。

具体怎么实现的？核心是维护一个「空闲链表」。每次 malloc 时，系统遍历这个链表，找到一块足够大的空闲内存，切一块给你，剩下的继续挂在链表上。free 时，把这块内存重新挂回链表，必要时还会和相邻的空闲块合并。

// 简化版的内存块结构
typedef struct mem_block {
    size_t       size;      // 块大小（包含头信息）
    int          free;      // 是否空闲
    struct mem_block *next; // 指向下一个块
    // 实际数据从这里开始
} mem_block_t;

你想想看，每次 malloc 都要遍历链表，效率能高吗？所以频繁申请释放小内存，性能会很难看。我在项目中遇到过，一个通信协议栈每秒申请释放上千次，结果 CPU 全耗在链表遍历上了。

4.2 内部碎片与外部碎片

碎片问题是堆管理的头号杀手。分两种：内部碎片和外部碎片。

4.2.1 内部碎片

内部碎片，说白了就是「浪费在自己肚子里」。比如你申请 30 字节，但系统最小分配单位是 32 字节，那 2 字节就浪费了。或者你申请 100 字节，系统给你 108 字节（含头信息），那 8 字节也是内部碎片。

申请大小	实际分配	内部碎片	浪费比例
1 字节	16 字节（对齐）	15 字节	93.75%
30 字节	32 字节	2 字节	6.25%
100 字节	108 字节	8 字节	7.4%

看到没？申请越小，浪费比例越高。所以我建议，尽量避免频繁申请小内存，能合并就合并。

4.2.2 外部碎片

外部碎片更隐蔽，也更致命。它指的是：总空闲内存够用，但被分割成很多小块，没有一块连续空间能满足你的申请。

举个例子：堆里有 100 字节空闲，但分成了 10 块，每块 10 字节。这时候你申请 20 字节，虽然总空闲够，但 malloc 会失败。这就是外部碎片。

4.3 堆管理算法

不同的算法，决定了你怎么从空闲链表中找合适的块。我常用的有三种：首次适应、最佳适应、最差适应。这里重点讲前两个。

4.3.1 首次适应算法

这个算法最简单：从头遍历空闲链表，找到第一个大小够用的块就分配。

// 首次适应算法伪代码
void *first_fit_malloc(size_t size) {
    mem_block_t *curr = free_list_head;
    while (curr != NULL) {
        if (curr->free && curr->size >= size) {
            // 找到了！切一块出来
            split_block(curr, size);
            curr->free = 0;
            return (void*)(curr + 1);
        }
        curr = curr->next;
    }
    return NULL; // 没找到
}

优点：速度快，不需要遍历整个链表。找到第一个就停。

缺点：容易在链表头部产生很多小碎片。你想想看，每次都从头部找，大的块被切得越来越小，最后头部全是碎渣。

我个人习惯，在内存比较充裕、申请次数不多的场景用首次适应。简单粗暴，够用就行。

4.3.2 最佳适应算法

最佳适应算法更「精打细算」：遍历整个空闲链表，找到大小最接近你需求的块。

// 最佳适应算法伪代码
void *best_fit_malloc(size_t size) {
    mem_block_t *curr = free_list_head;
    mem_block_t *best = NULL;
    size_t min_diff = SIZE_MAX;
    
    while (curr != NULL) {
        if (curr->free && curr->size >= size) {
            size_t diff = curr->size - size;
            if (diff < min_diff) {
                min_diff = diff;
                best = curr;
                // 如果完全匹配，直接退出
                if (diff == 0) break;
            }
        }
        curr = curr->next;
    }
    
    if (best != NULL) {
        split_block(best, size);
        best->free = 0;
        return (void*)(best + 1);
    }
    return NULL;
}

优点：碎片最小化，每次分配都「刚刚好」。

缺点：慢！每次都要遍历整个链表。而且容易留下很多极小的碎片（比如差 1 字节那种），这些小碎片几乎没法再用。

4.3.3 两种算法对比

对比项	首次适应	最佳适应
查找速度	快（找到即停）	慢（必须遍历完）
内存利用率	中等	较高
碎片情况	头部碎片多	微小碎片多
适用场景	通用场景	内存紧张、申请次数少

其实还有第三种——最差适应算法，专门找最大的块来分配。目的是留下较大的空闲块，减少小碎片。但实际效果嘛，我个人觉得不如前两种实用。

最后说一句：堆管理没有银弹。不同的算法适合不同的场景。我建议你在项目初期就评估好内存分配模式，选对算法，能省去后期很多头疼的问题。