学校网站建设基本流程,东莞app下载安装,北京移动官方网站,怎样搭建大型企业网络TLSF (Two-Level Segregated Fit) 是一个O(1)时间复杂度的动态内存分配器#xff0c;特别适合实时系统。本文将深入分析TLSF的实现原理和源码细节。
1. 基本概念
1.1 关键特性 O(1)时间复杂度的内存分配和释放 低内存碎片化 确定性行为#xff0c;适合实时系统 支持多内…TLSF (Two-Level Segregated Fit) 是一个O(1)时间复杂度的动态内存分配器特别适合实时系统。本文将深入分析TLSF的实现原理和源码细节。
1. 基本概念
1.1 关键特性 O(1)时间复杂度的内存分配和释放 低内存碎片化 确定性行为适合实时系统 支持多内存池管理 最小内存对齐支持
1.2 核心数据结构
块头(Block Header)
typedef struct block_header_t {struct block_header_t* prev_phys_block; // 指向物理相邻的前一个块size_t size; // 块大小,包含控制位struct block_header_t* next_free; // 空闲块链表的下一个节点struct block_header_t* prev_free; // 空闲块链表的前一个节点
} block_header_t;块头中size字段的低两位用作标记位: bit 0: 当前块是否空闲 bit 1: 前一个块是否空闲
TLSF控制结构
typedef struct control_t {block_header_t block_null; // 空闲链表的哨兵节点unsigned int fl_bitmap; // 第一级位图unsigned int sl_bitmap[FL_INDEX_COUNT]; // 第二级位图block_header_t* blocks[FL_INDEX_COUNT][SL_INDEX_COUNT]; // 空闲块数组
} control_t;2. 内存布局
2.1 初始化后的内存布局举例
当调用 mm_initialize 初始化 TLSF 时,传入参数 heapstart0x10000, heapsize0x10000:
0x10000 ------------------------| struct mm_heap_s | -- heap控制结构(116字节)| (sizeof 116 bytes) |
0x10074 ------------------------| tlsf control block | -- tlsf内部控制块 | (tlsf_size() bytes) | (包含空闲块链表、位图等)
0x10474 ------------------------| first block header | -- 第一个block的header| (8 bytes) | 包含:
0x1047C ------------------------ - 块大小(含header) | first block | -- - 使用/空闲标志位 | user data area | 低2位用作标记位:| | bit 0: 当前块是否空闲------------------------ bit 1: 前一个块是否空闲| next block header || (8 bytes) |------------------------| next block || user data area || |------------------------| ... |
0x20000 ------------------------关键点说明:
mm_heap_s 结构(0x10000-0x10074): 大小: 116 字节 包含:
TLSF控制块(0x10074-0x10474): 大小: tlsf_size() 返回值 用于TLSF算法内部管理 包含空闲块链表、位图等数据结构
Block Header(8字节): 每个内存块的头部信息 只包含 size_t 类型的 size 字段(8字节) size字段低2位用作标记位 prev_phys_block 字段存在前一个块的尾部
内存对齐: 所有分配按 ALIGN_SIZE 对齐(32位系统4字节,64位8字节) 块大小也按 ALIGN_SIZE 对齐 确保访问效率
2.2 内存初始化过程
mm_initialize函数流程:
heap (FAR struct mm_heap_s *)heapstart; // 预留heap控制结构
heapstart sizeof(struct mm_heap_s);
heapsize - sizeof(struct mm_heap_s);heap-mm_tlsf tlsf_create(heapstart); // 创建TLSF控制块
heapstart tlsf_size();
heapsize - tlsf_size();mm_addregion(heap, heapstart, heapsize); // 添加可用内存区域tlsf_add_pool初始化内存池: 在内存起始处创建第一个block header header的size字段包含整个内存区域大小 将block加入到空闲链表中
block header的创建:
block offset_to_block(mem, -(tlsfptr_t)block_header_overhead);
// block_header_overhead sizeof(size_t) // 8字节3. 关键算法实现
3.1 内存分配大小计算
TLSF在分配内存时的大小计算涉及多个方面:
实际分配大小计算:
// 用户请求分配size字节时:
#if CONFIG_MM_BACKTRACE 0// 需要加上backtrace结构体大小actual_size size sizeof(struct memdump_backtrace_s);
#elseactual_size size;
#endif// 分配后用户实际可用大小:
user_size mm_malloc_size(heap, ptr);Block大小对齐: 所有分配按 ALIGN_SIZE 对齐(32位系统4字节,64位8字节) Block header(8字节)也需要对齐 分配大小向上取整到对齐大小
Block header大小:
// 每个block只需要一个size字段(8字节)
block_header_overhead sizeof(size_t); // 8字节// size字段的低2位用作标记位:
- bit 0: 当前块是否空闲
- bit 1: 前一个块是否空闲最小分配大小:
// 通过 tlsf_block_size_min() 获取
min_size MAX(sizeof(free_list_t), ALIGN_SIZE);分配流程中的大小计算:
void* mm_malloc(size_t size) {// 1. 确保最小分配大小if (size 1) size 1;// 2. 加上管理开销actual_size size overhead;// 3. 对齐大小 aligned_size ALIGN_SIZE_UP(actual_size);// 4. 分配内存块block tlsf_malloc(aligned_size);// 5. 返回用户可用内存return block;
}Block合并时的大小计算:
// 向前合并
total_size prev_size curr_size;// 向后合并
total_size curr_size next_size;// 双向合并
total_size prev_size curr_size next_size;特殊情况: 延迟释放的内存块保持原大小不变 重新分配时可能需要分配新块 内存池扩展时需要调整大小
大小限制:
// 最大块大小
max_size tlsf_block_size_max();// 最小块大小
min_size tlsf_block_size_min();// 对齐大小
align_size tlsf_align_size();实际分配举例:
用户申请: malloc(100)实际分配:
[block header:8字节] [用户数据:100字节] [backtrace:8字节]
总大小 116字节,向上对齐到8字节边界 120字节用户可用: 100字节
块大小: 120字节关键点说明: Block header只占8字节是TLSF的一个优化 通过位操作复用size字段的低位 对齐保证访问效率 Backtrace结构根据配置添加 分配大小必须在最小和最大值之间
TLSF使用两级位图来快速查找合适的空闲块:
第一级(FL): 根据大小范围划分块 使用位图快速定位范围 FL_INDEX_MAX 定义最大支持的块大小
第二级(SL): 在第一级范围内细分 SL_INDEX_COUNT 定义每个范围内的细分数量 也使用位图实现O(1)查找
3.2 映射算法
size到fl/sl索引的映射:
static void mapping_insert(size_t size, int* fli, int* sli) {int fl, sl;if (size SMALL_BLOCK_SIZE) {// 小块存储在第一个链表fl 0;sl size / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT);} else {fl tlsf_fls_sizet(size);sl (size (fl - SL_INDEX_COUNT_LOG2)) ^ (1 SL_INDEX_COUNT_LOG2);fl - (FL_INDEX_SHIFT - 1);}*fli fl;*sli sl;
}3.3 分配过程 根据请求大小计算fl/sl索引 在对应位置查找空闲块 如果没有合适的块,向上搜索更大的块 找到后分割块(如果太大) 更新位图和链表
关键代码:
static block_header_t* search_suitable_block(control_t* control, int* fli, int* sli) {int fl *fli;int sl *sli;// 先在指定fl/sl位置查找unsigned int sl_map control-sl_bitmap[fl] (~0U sl);if (!sl_map) {// 当前级别没有合适的块,查找更大的块const unsigned int fl_map control-fl_bitmap (~0U (fl 1));if (!fl_map) {return 0;}fl tlsf_ffs(fl_map);*fli fl;sl_map control-sl_bitmap[fl];}sl tlsf_ffs(sl_map);*sli sl;return control-blocks[fl][sl];
}3.4 释放过程 设置块为空闲 尝试与相邻的空闲块合并 将合并后的块插入适当的空闲链表 更新位图
3.5 合并算法
向前合并:
static block_header_t* block_merge_prev(control_t* control, block_header_t* block) {if (block_is_prev_free(block)) {block_header_t* prev block_prev(block);block_remove(control, prev);block block_absorb(prev, block);}return block;
}向后合并:
static block_header_t* block_merge_next(control_t* control, block_header_t* block) {block_header_t* next block_next(block);if (!block_is_last(block) block_is_free(next)) {block_remove(control, next);block block_absorb(block, next);}return block;
}4. 内存管理优化
4.1 延迟释放机制 通过delay list延迟释放内存 避免频繁的合并操作 提高实时性能
4.2 内存池扩展
支持动态扩展内存池:
TLSF_API pool_t tlsf_extend_pool(tlsf_t tlsf, void* mem, size_t bytes, size_t incr);4.3 碎片处理 分割时保留最小块大小 优先使用最适合大小的块 支持块合并减少碎片
5. 调试功能
5.1 内存检查
TLSF_API int tlsf_check(tlsf_t tlsf);
TLSF_API int tlsf_check_pool(pool_t pool);5.2 内存遍历
typedef void (*tlsf_walker)(void* ptr, size_t size, int used, void* user);
TLSF_API void tlsf_walk_pool(pool_t pool, tlsf_walker walker, void* user);6. 使用示例
6.1 基本使用
// 创建TLSF实例
void* mem malloc(1024 * 1024); // 1MB内存
tlsf_t tlsf tlsf_create(mem);// 分配内存
void* ptr tlsf_malloc(tlsf, 512);// 释放内存
tlsf_free(tlsf, ptr);// 销毁TLSF实例
tlsf_destroy(tlsf);6.2 内存池管理
// 添加新内存池
void* pool_mem malloc(1024 * 1024);
pool_t pool tlsf_add_pool(tlsf, pool_mem, 1024 * 1024);// 扩展内存池
void* new_mem malloc(512 * 1024);
tlsf_extend_pool(tlsf, pool, new_mem, 512 * 1024);7. 性能考虑
7.1 时间复杂度 分配: O(1) 释放: O(1) 重新分配: O(1) 合并: O(1)
7.2 空间开销 控制结构大小固定 每个块16字节开销 支持最小块大小限制
7.3 实时性保证 操作时间确定 无递归调用 无循环搜索
8. 最佳实践
选择合适的配置参数 FL_INDEX_MAX SL_INDEX_COUNT ALIGN_SIZE
内存池管理 合理规划内存池大小 适时扩展内存池 及时释放不用的内存池
性能优化 使用内存对齐 合理使用延迟释放 避免频繁的小内存分配
调试支持 定期检查内存完整性 使用内存遍历功能跟踪分配 合理设置调试选项
9. 总结
TLSF是一个高效的实时内存分配器通过巧妙的两级位图设计实现了O(1)的操作时间复杂度。其关键特点:
内存布局清晰: 控制结构固定大小 每个block只需8字节header 通过位图快速管理空闲块
内存管理高效: O(1)时间复杂度 支持内存对齐 低内存碎片 适合实时系统
功能完备: 支持多内存池 延迟释放机制 调试功能 内存追踪
理解其实现原理对于系统性能优化和内存管理都有重要帮助。
