MiniMalloc 是个学习用的内存分配器。它不向操作系统要内存,所有分配和释放都发生在一个编译期创建的 8KB 数组里。
实现借了 FreeRTOS heap_4 的思路:给每块内存加一个块头,用地址有序的单向链表管理空闲块,分配时首次适配,释放时合并相邻空间。核心代码不到两百行,足够把 malloc 和 free 背后的账算一遍。
用户指针前面藏着块头
数组本身很普通:
#define CONFIG_HEAP (8 * 1024)
static uint8_t AllHeap[CONFIG_HEAP];
每个内存块开头放两个字段:下一空闲块的地址和当前块大小。
typedef struct heap_node {
struct heap_node *next;
size_t BlockSize;
} heap_node;
在当前 MinGW x64 环境里,块头占 16 字节。调用 heap_malloc(100) 时,实际请求要先加上块头,再向 8 字节边界对齐:
100 + 16 = 116
向上对齐后 = 120
分配器返回“块起点 + 16”,用户看到的只有数据区。heap_free() 收到指针后再减 16,找回原来的块头。
这也解释了为什么 free 不能随便传一个块内地址。偏一个字节,分配器读到的就不再是合法的 next 和 BlockSize。
初始化后可用空间是 8176 字节
空闲链表前后各有一个哨兵:head 放在管理结构里,tail 占用数组末尾一个块头的位置。初始化完成后是:
head → 一整块空闲内存 → tail
数组虽然有 8192 字节,尾哨兵要占 16 字节,因此 AllSize 初始值是 8176。tail 的块大小为 0,next 为 NULL,遍历到这里就知道已经没有可用块。
heap_init() 还要处理数组起始地址对齐。当前静态数组通常已经对齐,但代码不能靠这个巧合。对齐时跳过的字节同样要从 AllSize 扣掉。
第一次调用 heap_malloc() 时,如果 tail 还是 NULL,程序才执行初始化。测试可以直接调用 heap_init() 重置状态,所以这个函数每次都从 8192 重新计算,不能拿上一次的 AllSize 接着扣。
分配就是找一块、切一块
请求加块头并对齐后,程序从低地址开始遍历空闲链表,找到第一块装得下的空间。这里用 first-fit,没有做 best-fit。代码短,行为也容易测试。
如果选中的空闲块比请求大,并且剩余空间超过最小切割尺寸,就把尾部切成一个新的空闲块挂回链表:
切割前:[ 空闲块 ]
切割后:[ 已分配块 ][ 剩余空闲块 ]
剩余太小时不切,整块交给这次分配,免得留下一段只能装元数据的碎片。已分配块会从空闲链表摘掉,它只保留自己的 BlockSize,等释放时再回来。
AllSize 记录全部空闲块的大小之和。分配 100 字节时扣的是 120,不是 100;释放时也按块头里的完整大小加回。
free 为什么要按地址插入
释放后的块不会直接塞到链表头。InsertFreeBlock() 会找到合适的位置,让空闲链表始终按内存地址递增。
这样一来,新块的物理邻居只可能是链表前驱和后继。判断两块是否连续,只需检查前一块起点加上 BlockSize 是否正好等于后一块地址。连续就合并,并改掉链表指针。
释放前:[空闲 A][已分配 B][空闲 C]
插入后:[空闲 A][ 空闲 B ][空闲 C]
合并后:[ 一整块空闲空间 ]
配套测试会先释放中间块,再释放两侧,确认所有空间最终重新合成 8176 字节的一块。first-fit 复用、切割、耗尽后回收和最大分配边界也都有单独用例,目前是 47 项检查。
修过的三个问题
早期版本在相邻判断里把指针写成了 8 位整数:
uint8_t address = (uint8_t)block;
本来需要的是 uint8_t *。少了一个星号后,64 位地址只剩最低 8 位,块稍大一些就无法正确判断相邻,甚至可能把不相邻的空间拼到一起。
另一个问题是尾哨兵已经放进数组,账面上的 AllSize 却仍然保留 8192。最大请求会覆盖 tail,等下一次遍历或释放时才崩。修复后,初始化明确扣掉块头大小,并加了最大分配边界测试。
这个修复又暴露了重置问题:如果 heap_init() 不先把 AllSize 恢复成 CONFIG_HEAP,每调用一次都会继续少 16 字节。现在初始化从已知状态重算,可以重复调用。
这份实现没有线程同步,也不检测 double free 和越界写。heap_free(NULL) 会崩,heap_malloc(0) 则会返回一个只含块头的分配,这些行为都和标准库不完全一样。它目前只拿来理解分配器结构,先不补成生产可用的内存管理库。