3、堆（Heap）原理：动态内存分配机制、碎片化问题、常见堆实现（dlmalloc、tlsf）
在MCU端侧推理引擎中，堆（Heap）是除静态全局区和栈之外最核心的内存来源。与PC端动辄数GB的虚拟内存不同，MCU的RAM通常只有几十KB到几MB，且不存在MMU进行地址映射，所有内存均为物理内存。推理框架中的权重张量、中间激活值、算子临时缓冲区，往往都通过堆进行动态分配。理解堆的工作原理，是进行三段式内存治理（Heap、Stack、Arena）的前提。本章将深入剖析动态内存分配的内在机制、碎片化的形成与危害，并对比两种主流堆实现——dlmalloc与TLSF，帮助你在实际项目中做出正确的堆选型与配置决策。
上图从宏观上对比了dlmalloc与TLSF在MCU端侧推理场景下的核心差异，并展示了碎片化从产生到最终导致分配失败的过程。接下来，我们将逐一拆解堆分配的内在机制、碎片化的数学本质，以及两种堆实现的具体工作原理。
3.1 动态内存分配机制：从malloc到chunk
在MCU上，堆通常由链接脚本划定一段连续RAM区域，起始地址和大小在编译期确定。运行时，堆管理器通过malloc/free接口向应用提供内存。其核心数据结构是chunk——一个带有元数据头部的内存块。每个chunk头部至少包含当前块大小、前一块大小（用于合并）、以及空闲/占用标志位。当应用请求N字节时，堆管理器会从空闲链表中找到一个满足条件的chunk，将其分割为“已分配块”和“剩余空闲块”，并更新元数据。
关键机制：边界标记（Boundary Tag）
dlmalloc和TLSF都采用边界标记法。每个chunk的头部和尾部各存一个size字段。这样做的好处是：当释放一个chunk时，堆管理器可以通过检查当前chunk尾部的前一size字段，快速判断物理相邻的前一个chunk是否空闲，从而实现O(1)时间的合并操作。代价是每个chunk需要额外的8~16字节元数据开销。对于频繁分配小对象的推理引擎（如4字节的标量），这个开销占比可能高达50%以上。
分配流程通常遵循以下步骤：
- 将请求大小对齐到8字节或16字节（MCU通常按4/8字节对齐）。
- 加上chunk头尾元数据大小，得到实际需要的chunk大小。
- 在空闲链表中查找合适的chunk（策略因实现而异）。
- 如果找到的chunk远大于请求大小，则进行分割，剩余部分作为新的空闲chunk插入链表。
- 更新位图或链表指针，返回给用户指向数据区的指针。
释放流程则相反：先根据用户指针回退到chunk头部，标记为空闲，然后尝试与前后相邻空闲块合并，最后插入空闲链表。这一机制保证了堆在长时间运行后，空闲块尽可能保持大块连续。
3.2 碎片化问题：内部碎片与外部碎片
碎片化是堆内存管理的核心难题，分为两类：
| 碎片类型 | 定义 | 产生原因 | 对推理引擎的影响 |
|---|---|---|---|
| 内部碎片 | 已分配块内未被使用的空间 | 对齐填充、元数据开销、请求大小与分配粒度不匹配 | 浪费RAM，但不会导致分配失败 |
| 外部碎片 | 空闲块分散在堆各处，无法满足大块连续分配 | 分配/释放顺序交错，大小不一 | 直接导致malloc失败，即使总空闲内存充足 |
在MCU推理场景中，外部碎片尤为致命。例如，一个模型需要分配一块16KB的中间激活缓冲区，但堆中最大的连续空闲块只有12KB，即使总空闲内存有40KB，分配依然失败。更糟糕的是，推理引擎通常无法优雅处理malloc失败——往往直接触发HardFault或看门狗复位。
风险提示：在推理引擎中，不要在回调函数或中断上下文中调用malloc。堆管理器通常不是可重入的，且中断中的分配行为可能导致链表损坏。如果必须在中断中分配，请使用专用的中断安全内存池（Arena）。
碎片化的数学本质是：假设堆大小为S，分配请求大小服从某种分布，经过长时间运行后，空闲块的数量和大小分布趋于一种稳态。对于通用堆（如dlmalloc），这个稳态往往包含大量小碎片。而TLSF通过将空闲块按大小分类到不同的链表中，使得分配时总能找到“最合适”的块，从而显著降低外部碎片率。
3.3 常见堆实现对比：dlmalloc与TLSF
在MCU端侧推理中，最常用的两种堆实现是dlmalloc和TLSF。它们的设计哲学截然不同。
3.3.1 dlmalloc：通用性与兼容性的代表
dlmalloc（Doug Lea's Malloc）是经典的操作系统级分配器，被广泛移植到嵌入式环境。其核心设计包括：
- 分箱（Bins）管理：将空闲块按大小分为多个链表，小对象（<512字节）有固定数量的bin，大对象使用树形结构。
- 边界标记：支持前后向合并，减少外部碎片。
- 首次适应策略：默认从最小的bin开始查找，找到第一个满足大小的块即分配。这种策略倾向于保留大块，但查找时间不确定。
dlmalloc的优点是代码成熟、移植简单、内存开销适中。缺点是分配延迟不可预测，最坏情况下需要遍历多个bin；且在高碎片化场景下，性能退化明显。对于推理引擎这种分配模式相对固定的场景，dlmalloc并非最优选择。
3.3.2 TLSF：实时性与低碎片的平衡
TLSF（Two-Level Segregated Fit）专为实时系统设计，其核心思想是用空间换时间，实现O(1)的分配和释放。
- 两级位图索引：第一级按2的幂次（如2^4, 2^5, ..., 2^30）划分大小区间；第二级在每个区间内进一步细分为多个子区间（通常8~32个）。
- Segregated Free List：每个子区间对应一个空闲链表，所有相同大小范围的chunk挂在同一个链表上。
- 分配过程：根据请求大小计算第一级和第二级索引，通过位图运算直接定位到非空链表，取出第一个chunk即可。整个过程不涉及遍历，时间复杂度恒为O(1)。
TLSF的碎片率通常比dlmalloc低30%~50%，因为其分配策略是“最合适”而非“首次适应”。但代价是内存开销更大：每个chunk需要额外的位图索引指针，且空闲链表的管理结构占用更多RAM。对于RAM紧张的MCU，需要权衡。
选型建议：如果推理引擎的分配模式是“启动时分配一次，运行中不再分配”，使用dlmalloc即可；如果运行中需要频繁分配/释放中间缓冲区（如动态shape模型），强烈建议使用TLSF，或直接使用Arena池化（见后续章节）。
3.4 案例拆解：一个动态shape模型的堆碎片化故障
某智能音箱产品使用Cortex-M7内核MCU，RAM共512KB，其中堆区域配置为256KB。推理引擎运行一个语音识别模型，输入音频帧长度固定，但中间特征图的宽度随说话人语速变化（动态shape）。初始版本使用dlmalloc作为堆管理器。
初始现象：设备运行约2小时后，推理任务偶发失败，日志显示malloc(16384) failed。重启后恢复正常，但故障复现周期越来越短。
关键数据：
- 堆总大小：256KB
- 运行2小时后，空闲内存总量：约80KB
- 最大连续空闲块：仅11KB
- 分配请求：16KB（中间激活缓冲区）
分析过程：通过堆监控工具（如mallinfo）导出空闲块分布，发现存在大量2KB~4KB的小碎片，散布在堆的各个地址。这些碎片来自不同shape下临时缓冲区的反复分配和释放。dlmalloc的首次适应策略倾向于使用低地址的空闲块，导致高地址的大块被反复分割，最终形成“蜂窝状”碎片。
实际操作步骤：
- 将堆管理器从dlmalloc切换为TLSF，保持堆大小不变。
- 在推理引擎初始化阶段，预分配所有可能的最大shape缓冲区（静态Arena），运行中不再动态分配。
- 对于无法预分配的小对象（如临时标量），使用专用的对象池（固定大小块链表）。
结果对比：
| 指标 | dlmalloc | TLSF | TLSF + Arena |
|---|---|---|---|
| 最大连续空闲块（2h后） | 11KB | 48KB | 128KB（Arena外） |
| 分配失败次数 | 3次/小时 | 0次 | 0次 |
| 平均分配延迟 | ~120μs | ~8μs | ~2μs（Arena命中） |
| 内存利用率 | 68% | 82% | 91% |
风险与代价：TLSF的初始内存开销比dlmalloc多约4KB（用于位图和链表头），对于256KB堆来说可接受。但Arena方案需要预先精确计算最大shape，如果模型后续升级导致shape增大，可能需要重新调整Arena大小，否则会分配失败。
复盘经验：在MCU推理引擎中，堆碎片化不是“堆不够大”的问题，而是“分配模式与堆策略不匹配”的问题。动态shape模型应优先考虑Arena池化，而非依赖通用堆。如果必须使用通用堆，TLSF是比dlmalloc更安全的选择。
3.5 常见误区与总结
误区一：堆越大越好。在MCU上，堆过大意味着静态区或栈区被压缩，可能导致编译链接失败或栈溢出。堆大小应根据峰值分配需求+30%余量来设定。
误区二：malloc失败后重试即可。在嵌入式实时系统中，malloc失败往往意味着系统即将崩溃。正确做法是：在开发阶段通过压力测试找出峰值分配量，并设置内存水位线告警。
误区三：所有内存都走堆。对于生命周期固定、大小固定的对象（如权重张量），应使用静态分配或Arena，避免堆的元数据开销和碎片风险。