← 文章 / Writing

Systems9 min编者 nabunana ↗

拿一个 8KB 数组写个 malloc

MiniMalloc 里真正需要想明白的几件事:块头放哪、空闲块怎么找,以及 free 后怎样把内存拼回去。
#C#Memory#Data Structure#嵌入式

MiniMalloc 是个学习用的内存分配器。它不向操作系统要内存,所有分配和释放都发生在一个编译期创建的 8KB 数组里。

实现借了 FreeRTOS heap_4 的思路:给每块内存加一个块头,用地址有序的单向链表管理空闲块,分配时首次适配,释放时合并相邻空间。核心代码不到两百行,足够把 mallocfree 背后的账算一遍。

用户指针前面藏着块头

数组本身很普通:

#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 不能随便传一个块内地址。偏一个字节,分配器读到的就不再是合法的 nextBlockSize

初始化后可用空间是 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) 则会返回一个只含块头的分配,这些行为都和标准库不完全一样。它目前只拿来理解分配器结构,先不补成生产可用的内存管理库。

今聴いている / NOW LISTENINGYorushika

读完之后,留一点安静给音乐。这是一则状态记录,不是播放器。

站内搜索

AgentVibe的东西 真的看懂了吗Notes · 工程 反思 AI 能力 · 攒了一堆能跑的项目,能力却没长进。问题不在代码谁写的,在于我有没有真正想明白。谈谈多Agent并发与OpenclawNotes · AI 工作流 OpenClaw 工程取舍 · 把一个写文案的活拆成五六个 Agent 开会,听着爽,实际是 Token 火葬场。真正把事做完的,是单 Agent 加工具,加上几个克制的角色。一次 GitHub Actions 自动发布复盘Engineering · Astro GitHub Actions Nginx SSH CI/CD 部署 · 从旧 Hexo GitHub Pages、Astro 新站到服务器:怎样处理分支切换、SSH 信任、未入库的 94 首音乐,以及可回滚的原子发布.更新静态博客时,我不直接覆盖 /var/www/blogEngineering · Astro Nginx SFTP 部署 静态网站 · 这个 Astro 博客的发布过程:先在旁边准备好完整站点,核对资源,再一次替换并保留回滚。Java 没有断,WebSocket 为什么一直重连Engineering · Java WebSocket Nginx Vue 部署 · 一次公网部署故障复盘:REST 正常、进程没重启,WebSocket 却持续 403,子路由刷新也跟着 404。做“今天吃什么”,我只想让页面给一家店Engineering · Java Vue uni-app 推荐系统 产品设计 · ELMA 目前的项目思路:少问几个问题,一次给一家店,再从反馈和行为里慢慢学。做一个能按真实尺寸打印的卡牌 PDF 工具Projects · Python Pillow PDF Tkinter Desktop · 卡牌图片放进 A4 不难,麻烦的是毫米、DPI、图片比例和桌面程序里的几个小坑。三体模拟器跑起来以后,四条链路开始互相拖后腿Engineering · Java Vue WebSocket Canvas 性能优化 · 一次实时模拟项目里的拆分:积分照常跑,网络只发该发的,画布和归档各自守住上限。聊天摘要 Agent:消息拉全以后,才轮得到模型Agent · Python Agent SQLite Privacy 容错设计 · 记录聊天摘要从能运行到可以放心使用,中间补过的分页、游标、证据和隐私边界。拿一个 8KB 数组写个 mallocSystems · C Memory Data Structure 嵌入式 · MiniMalloc 里真正需要想明白的几件事:块头放哪、空闲块怎么找,以及 free 后怎样把内存拼回去。我为什么还在用 RSSNotes · RSS Reading Web · 不猜兴趣,也不替我调整顺序。想看的来源,自己订阅就够了。这个夏天看过的动画ACG · Anime ACG Life · 没做排名,只记下几段过了一阵子还会想起来的内容。ProjectsPage · 正在构建的项目与实验MusicPage · Yorushika、n-buna、Vocaloid 与听歌记录AboutPage · 关于这个数字空间和它的主人