用C语言实现单片机malloc功能：TLSF算法实现单片机malloc函数及单片机malloc原理详解和测试

、传统内存管理与TLSF算法在嵌入式实时系统RTOS开发中内存分配是一个让人又爱又恨的话题。传统堆分配器如ptmalloc虽然功能强大但存在两个致命缺陷1、分配时间不确定最坏情况下需要遍历整个空闲链表时间复杂度O(n)无法满足硬实时要求2、内存碎片严重频繁的分配/释放导致大量无法利用的内存碎片TLSFTwo-Level Segregated Fit 算法正是为解决这些问题而生。它由西班牙马德里理工大学于2005年提出能够在O(1)时间复杂度内完成内存分配与释放且碎片率极低。本文将基于TLSF代码深入剖析其设计原理与工程实践。二、设计需求分析2.1 实时性需求指标传统分配器TLSF目标分配时间O(n) 不稳定O(1) 确定上限释放时间O(1)~O(n)O(1) 严格保证最坏情况可能遍历MB级内存固定32次位运算2.2 嵌入式场景约束// 我们的目标平台资源极其有限#define ALIGN_BYTES 0x04 // 4字节对齐适配32位ARM #define BIT_SIZE_CONFIG 8 // 位图使用8位节省RAM #define BLOCK_Min_SIZE (sizeof(List_Node)) // 最小块16字节关键约束确定性中断服务程序(ISR)中也能安全调用可预测性内存碎片必须可控内存对齐内存必须对齐三、核心设计方法两级分离适配3.1 设计哲学分而治之TLSF的核心思想是将不同大小的内存块分类管理。就像图书馆把书籍按类别分区存放找书时直接去对应区域而不是遍历整个书库。3.2 两级索引架构┌─────────────────────────────────────────────────────────┐ │ 第一级索引FLI: First Level Index │ │ 按2的幂次方分档16, 32, 64, 128, 256, 512, 1K, 2K... │ │ 共32档覆盖4GB地址空间 │ ├─────────────────────────────────────────────────────────┤ │ 第二级索引SLI: Second Level Index │ │ 每档内细分为8个子区间均匀划分 │ │ 例如256字节档256~287, 288~319, ..., 480~511 │ └─────────────────────────────────────────────────────────┘代码实现// 将大小映射到两级索引 static inline UINT_32 Change_Index(UINT_32 size, int Position_bit, UINT_32 alignment) { UINT_32 align_bit 0x01 alignment; return (Position_bit alignment) | ((align_bit - 1) (size (Position_bit - alignment))); } // 向上取整到合适的档 static UINT_32 Align_Index(UINT_32 size, UINT_32 alignment) { int Position_bit Get_highest_bit_position(size); return (Change_Index(size, Position_bit, alignment) (((0x01 (Position_bit - alignment)) - 1) size ? 1 : 0)); }示例 请求200字节内存Position_bit 8 (128 200 ≤ 256)第二级索引 (200 (8-3)) 0x07 6最终索引 (8 3) | 6 703.3 位图加速查找typedef struct Memory_Head { volatile TPED_BIT Map_bit[FREE_LIST_SIZE]; // 第一级位图32个8位组 volatile List_Node* Free_List_Head[FREE_LIST_SIZE][8]; // 256个空闲链表头 } Memory_Head;查找过程O(1)关键static int Find_Block(Memory_Head* Head, UINT_32 Index_len, UINT_32 x) { UINT_32 Bit_mask 0x01 Head-Map_unit_size; // 8 UINT_32 Bit_position Head-Map_unit_size; // 3 // 步骤1检查当前档是否有空闲块 if (Head-Map_bit[x Bit_position] (0x01U (x (Bit_mask - 1)))) { // 步骤2当前档无可用块跳到下一个第一级档 x Bit_mask - (x (Bit_mask - 1)); while ((x Bit_position) Index_len !Head-Map_bit[x Bit_position]) x Bit_mask; } // 步骤3在找到的第一级档中遍历第二级位图 Temp_bit Head-Map_bit[x Bit_position]; for (UINT_32 i (x (Bit_mask - 1)); i Bit_mask; i, x) { if (Temp_bit (0x01U i)) return x; // 找到 } return -1; }时间复杂度分析第一级跳转最多32次位运算第二级扫描最多8次位运算总计固定40次基本操作 → O(1)四、功能实现详解4.1 内存块结构设计typedef struct Base_Node { struct { volatile UINT_32 Block_Size : 31; // 块大小支持2GB volatile UINT_32 Used_flag : 1; // 使用标志 }; volatile void* Pre_addr; // 物理相邻前块用于合并 } Base_Node; typedef struct List_Node { Base_Node Base; struct List_Node* Prev; // 链表前驱同大小档 struct List_Node* Next; // 链表后继 } List_Node;设计亮点物理邻接指针Pre_addr实现O(1)合并无需遍历逻辑链表指针Prev/Next同档空闲块快速组织边界标记末尾哨兵块防止越界4.2 内存分配流程示意图4.3 初始化构建初始空闲块extern unsigned int Init_TLSF(Memory_Head* Head, void* Memory_addr, UINT_32 Memory_size, void (*Lock)(void), void (*Unlock)(void)) { // 4字节对齐内存大小 Memory_size ALIGN_SIZE(Memory_size); // 初始化管理头 Head-Total_Size Memory_size; Head-Available_Size 0; Head-Map_unit_size Get_highest_bit_position(sizeof(Head-Map_bit[0]) 3); if(Get_highest_bit_position(BLOCK_Min_SIZE) Head-Map_unit_size) return 0; // 清零位图与链表 for (UINT_32 i 0; i FREE_LIST_SIZE; i) { Head-Map_bit[i] 0; for (UINT_32 j 0; j 8; j) Head-Free_List_Head[i][j] NULL; } // 创建唯一大空闲块 List_Node* Node (List_Node*)Memory_addr; Node-Base.Pre_addr NULL; Node-Base.Used_flag 1; // 临时标记Add_Node会清零 Node-Base.Block_Size Memory_size - BLOCK_Min_SIZE; Add_Node(Head, Node); // 加入空闲链表更新位图 // 放置末尾哨兵防止向后合并越界 Node (List_Node*)((BYTE*)Memory_addr (Memory_size - BLOCK_Min_SIZE)); Node-Base.Pre_addr Memory_addr; Node-Base.Used_flag 1; // 永久占用 Node-Base.Block_Size BLOCK_Min_SIZE; Head-End_Addr_Node Node; return 1; }4.4 内存分配分割与适配extern void* TLSF_malloc(Memory_Head* Head, UINT_32 size) { // 参数校验与对齐 if(size 0 || size Head-Available_Size) return NULL; size ALIGN_SIZE(sizeof(Base_Node)); // 包含元数据 size (size BLOCK_Min_SIZE) ? BLOCK_Min_SIZE : ALIGN_SIZE(size); // O(1)查找合适空闲块 UINT_32 Index Align_Index(size, Head-Map_unit_size); int Node_index Find_Block(Head, FREE_LIST_SIZE, Index); if (Node_index -1) return NULL; // 取出块并分割如果剩余足够大 List_Node* Node Take_Out_Node(Head, Node_index); return (void*)((BYTE*)Partition_Node(Head, Node, size) ALIGN_SIZE(sizeof(Base_Node))); }分割策略关键优化最小分配快对于每次通过malloc( size )分配的字节大小size在TLSF内部查找匹配时往往存在一个最小匹配块当分配的字节小于这个匹配块时都会会返回这个最小匹配块。这个最小匹配块就是上图的最小地址匹配块的大小低于这个最小匹配块时不可以再度被分割。static void* Partition_Node(Memory_Head* Head, void* addr, UINT_32 size) { List_Node* Node (List_Node*)addr; if (Node-Base.Block_Size (size BLOCK_Min_SIZE)) { // 分割出剩余空闲块 List_Node* Divide_Node (List_Node*)((BYTE*)addr size); List_Node* Next_Node (List_Node*)((BYTE*)addr Node-Base.Block_Size); Divide_Node-Base.Block_Size Node-Base.Block_Size - size; Divide_Node-Base.Used_flag 0; Divide_Node-Base.Pre_addr addr; Next_Node-Base.Pre_addr Divide_Node; // 更新物理邻接 Node-Base.Block_Size size; Add_Node(Head, Divide_Node); // 剩余块回归空闲链表 } Node-Base.Used_flag 1; return Node; }4.5 内存释放立即合并extern void TLSF_free(Memory_Head* Head, void* addr) { if (Head NULL || addr NULL) return; // 回退到块头合并相邻空闲块 Merge_Node(Head, (BYTE*)addr - ALIGN_SIZE(sizeof(Base_Node))); }双向合并碎片抑制核心static void Merge_Node(Memory_Head* Head, void* addr) { List_Node* Node (List_Node*)addr; List_Node* Pre_Node (List_Node*)Node-Base.Pre_addr; List_Node* Next_Node (List_Node*)((BYTE*)Node Node-Base.Block_Size); // 向前合并 if (Pre_Node !Pre_Node-Base.Used_flag) { Delete_Node(Head, Pre_Node); Pre_Node-Base.Block_Size Node-Base.Block_Size; Next_Node-Base.Pre_addr Pre_Node; Node Pre_Node; } // 向后合并 if (!Next_Node-Base.Used_flag) { Delete_Node(Head, Next_Node); Node-Base.Block_Size Next_Node-Base.Block_Size; Next_Node (List_Node*)((BYTE*)Node Node-Base.Block_Size); Next_Node-Base.Pre_addr Node; } Add_Node(Head, Node); // 合并后的块回归空闲链表 }4.6 线程安全封装extern void* TLSF_malloc_Safe(Memory_Head* Head, UINT_32 size) { if (Head-Lock) Head-Lock(); // 获取互斥锁 void* ptr TLSF_malloc(Head, size); if (Head-Unlock) Head-Unlock(); // 释放锁 return ptr; }设计优势 锁机制外置支持关中断裸机RTOS互斥量多任务系统自旋锁SMP多核五、高级功能realloc的优化实现extern void* TLSF_realloc(Memory_Head* Head, void* addr, UINT_32 size) { List_Node* Node (List_Node*)((BYTE*)addr - ALIGN_SIZE(sizeof(Base_Node))); UINT_32 Old_size Node-Base.Block_Size; List_Node* Next_Node (List_Node*)((BYTE*)Node Old_size); size ALIGN_SIZE(size) ALIGN_SIZE(sizeof(Base_Node)); size (size BLOCK_Min_SIZE) ? BLOCK_Min_SIZE : ALIGN_SIZE(size); // 场景1当前块足够大直接分割 if (Old_size size) { if (Old_size (size BLOCK_Min_SIZE)) { // 分割并尝试与后邻居合并 List_Node* Free_Node (List_Node*)((BYTE*)Node size); Node-Base.Block_Size size; Free_Node-Base.Block_Size Old_size - size; Free_Node-Base.Pre_addr Node; if(Next_Node-Base.Used_flag 0) { // 与后邻居合并减少碎片 Delete_Node(Head, Next_Node); Free_Node-Base.Block_Size Next_Node-Base.Block_Size; ((List_Node*)((BYTE*)Free_Node Free_Node-Base.Block_Size))-Base.Pre_addr Free_Node; } Add_Node(Head, Free_Node);