30、综合实战：实现一个简易内存分配器
说实话，动态内存管理是C语言里最让人又爱又恨的部分。爱它，是因为它给了我们极大的灵活性；恨它，是因为一旦用不好，段错误、内存泄漏就找上门了。今天，咱们就亲手写一个简易的内存分配器。别怕，我会带着你一步步来。
我刚开始做嵌入式项目时，就遇到过标准库的malloc在资源紧张的环境下表现不佳的情况。嗯，从那以后，我就开始琢磨：能不能自己控制内存的分配和释放？于是就有了今天这个实战。
1. 核心思路：我们到底要做什么？
说白了，我们要实现一个类似malloc和free的东西。但这次，内存池是我们自己管理的。
基本想法是这样的：
- 预先申请一大块静态内存（比如一个全局数组）。
- 自己维护一个“空闲链表”，记录哪些内存块是空闲的。
- 用户请求分配时，从空闲链表中找一块合适的给他。
- 用户释放时，把内存块重新挂回空闲链表。
你想想看，这不就是一个小型的内存管家吗？
核心要点： 我们只实现最简单的“首次适应”算法。也就是从链表头开始找，找到第一个足够大的空闲块就分配出去。
2. 数据结构设计：怎么管理这些内存块？
每个内存块都需要一个“头部”来记录元信息。我习惯用一个结构体来表示：
// 内存块头部
typedef struct mem_block {
size_t size; // 数据区大小（不含头部）
int free; // 1=空闲，0=已分配
struct mem_block *next; // 指向下一个块
} mem_block_t;注意，这个头部是紧挨着数据区的。也就是说，用户拿到的指针，其实是 头部 + 1 的位置。这样做的好处是，释放时我们只需要从用户指针回退一个头部大小，就能拿到完整的元信息。
我的小习惯： 头部里只放必要的信息。size、free标志、next指针，这三个就够了。别放太多，否则每个块的开销太大。
3. 内存池初始化：先圈一块地
我们需要一个全局的内存池。我建议用静态数组，这样地址是固定的，调试起来也方便。
#define POOL_SIZE 1024 * 10 // 10KB
static char memory_pool[POOL_SIZE];初始化时，整个池子就是一个大空闲块。我们把第一个头部放在池子的起始位置：
void mem_init() {
mem_block_t *first = (mem_block_t*)memory_pool;
first->size = POOL_SIZE - sizeof(mem_block_t);
first->free = 1;
first->next = NULL;
}这里要注意：size 记录的是数据区的大小，不是整个块的大小。整个块的大小是 sizeof(mem_block_t) + size。
我曾经踩过的坑： 初始化时忘记减去头部大小，导致后续分配时总感觉内存少了几个字节。后来排查了半天才发现是这里算错了。所以，一定要把头部大小算清楚。
4. 分配内存：my_malloc 的实现
分配的逻辑其实不复杂：遍历空闲链表，找到第一个 free == 1 且 size >= 请求大小 的块。
但这里有个关键点：如果找到的块比请求的大很多，我们要不要分割？我的答案是：要分割。否则会造成内部碎片。
void *my_malloc(size_t size) {
mem_block_t *curr = (mem_block_t*)memory_pool;
mem_block_t *best = NULL;
// 遍历链表，首次适应
while (curr != NULL) {
if (curr->free && curr->size >= size) {
best = curr;
break;
}
curr = curr->next;
}
if (best == NULL) {
return NULL; // 没有合适的块
}
// 如果剩余空间足够大，就分割
size_t remaining = best->size - size;
if (remaining > sizeof(mem_block_t) + 4) { // 至少能再放一个头部+4字节
mem_block_t *new_block = (mem_block_t*)((char*)(best + 1) + size);
new_block->size = remaining - sizeof(mem_block_t);
new_block->free = 1;
new_block->next = best->next;
best->size = size;
best->next = new_block;
}
best->free = 0;
return (void*)(best + 1);
}为什么剩余空间要大于 sizeof(mem_block_t) + 4 才分割？因为新块至少需要一个头部，再加上一点点数据区，否则分割没有意义。
注意： 返回给用户的是 best + 1，也就是跳过头部，直接指向数据区。用户完全不知道头部的存在，这才是封装。
5. 释放内存：my_free 的实现
释放相对简单。用户把指针还给我们，我们回退一个头部大小，拿到 mem_block_t，然后把 free 标志置为1。
但这里有个进阶操作：合并相邻的空闲块。如果不合并，内存会越来越碎片化。
void my_free(void *ptr) {
if (ptr == NULL) return;
mem_block_t *block = (mem_block_t*)ptr - 1;
block->free = 1;
// 尝试向后合并
mem_block_t *next = block->next;
if (next != NULL && next->free) {
block->size += sizeof(mem_block_t) + next->size;
block->next = next->next;
}
// 尝试向前合并（需要遍历链表找到前一个块）
mem_block_t *curr = (mem_block_t*)memory_pool;
while (curr != NULL && curr->next != block) {
curr = curr->next;
}
if (curr != NULL && curr->free) {
curr->size += sizeof(mem_block_t) + block->size;
curr->next = block->next;
}
}向前合并需要遍历链表，效率不高。但考虑到我们的池子只有10KB，这点开销可以接受。
我的建议： 在实际项目中，如果内存块数量很多，可以考虑用双向链表，这样向前合并就不用遍历了。但今天这个简易版本，单向链表就够了。
6. 整体流程图：看看数据怎么流动
下面这张图展示了从初始化到分配、释放的完整流程。我特意画得比较直观，方便你理解。
7. 测试一下：写个简单的demo
光说不练假把式。我们来写几行代码测试一下：
#include <stdio.h>
#include <string.h>
int main() {
mem_init();
char *p1 = (char*)my_malloc(100);
char *p2 = (char*)my_malloc(200);
char *p3 = (char*)my_malloc(50);
strcpy(p1, "Hello, memory allocator!");
printf("p1: %s\n", p1);
my_free(p2);
my_free(p1);
char *p4 = (char*)my_malloc(150);
printf("p4 allocated, size=150\n");
my_free(p3);
my_free(p4);
printf("All tests passed!\n");
return 0;
}如果一切正常，你应该能看到输出。注意，这里我们没有处理内存耗尽的情况，实际项目中一定要加错误处理。
注意： 这个分配器没有线程安全保护。如果在多线程环境下使用，需要加锁。不过作为教学示例，单线程足够了。
8. 总结与思考
写到这里，一个简易的内存分配器就完成了。它虽然简单，但麻雀虽小五脏俱全：有初始化、分配、释放、分割、合并。你想想看，标准库的malloc底层也不过是这些思路的延伸。
我个人觉得，动手实现一次内存分配器，对理解C语言的内存模型非常有帮助。以后再遇到段错误、内存泄漏，你至少能猜到问题可能出在哪个环节。
最后，留个思考题给你：如果我想支持“对齐分配”（比如要求返回的地址是8字节对齐），该怎么改？嗯，这个问题留给你自己琢磨。