、传统内存管理与TLSF算法
在嵌入式实时系统（RTOS）开发中，内存分配是一个让人又爱又恨的话题。传统堆分配器（如ptmalloc）虽然功能强大，但存在两个致命缺陷：
1、分配时间不确定：最坏情况下需要遍历整个空闲链表，时间复杂度O(n)，无法满足硬实时要求；
2、内存碎片严重：频繁的分配/释放导致大量无法利用的内存碎片；
TLSF（Two-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 = 70
3.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);
