中国精品课程网站,开发网站定制,网站seo优化全程记录思维导图,高级搜索引擎技巧TLSF算法介绍
TLSF#xff08;Two-Level Segregated Fit#xff0c;两级分割适应算法#xff09;。
第一级#xff08;first level,简称fl#xff09;#xff1a;将内存大小按2的幂次方划分一个粗粒度的范围#xff0c;如一个72字节的空闲内存的fl是6#xff08;72介…TLSF算法介绍
TLSFTwo-Level Segregated Fit两级分割适应算法。
第一级first level,简称fl将内存大小按2的幂次方划分一个粗粒度的范围如一个72字节的空闲内存的fl是672介于26与27之间。第二级second level简称sl在第一级的基础上做线性化的细粒度划分分为多少等份由可配置的SLI参数确定在32bit的系统中最优的SLI为4或者5。 若为4则等分为2416份每一份分割叫做Segregated list分割链表。 如图中的[104,…,111]链表上挂着的是大小范围为104…111的free blocks数字104,…,111代表的是内存的大小而非内存地址TLSF算法将内存分成不同大小的块。
这个分割链表管理了两个内存块一个大小为109字节一个大小为104字节。 TLSF算法根据需要的内存大小根据前面的两级分割算法计算出fl和sl采用good fit策略分割链表中的free block都必须大于需要的内存大小。
如需要一个72字节的内存假设SLI2简单起见 做4等分则fl6sl0加入选择sl0这个分割链表由于67小于72不满足分割列表中所有free block大于需要的内存条件所以取sl1如果sl1这个分割链表不为空则返回这个链表中第一个free block给到应用程序。
TLSF代码分析
TLSF在tlsf_malloc中先调用block_locate_free获取free block再调用block_prepare_used获取free block的内存地址返回给应用程序。
void* tlsf_malloc(tlsf_t tlsf, size_t size)
{control_t* control tlsf_cast(control_t*, tlsf);const size_t adjust adjust_request_size(size, ALIGN_SIZE);block_header_t* block block_locate_free(control, adjust); //获取空闲内存块头return block_prepare_used(control, block, adjust);//获取free block的内存地址
}在这个过程中与good fit相关的是两个函数mapping_search和serach_suitable_block()。
/* This version rounds up to the next block size (for allocations) */
static void mapping_search(size_t size, int* fli, int* sli)
{if (size SMALL_BLOCK_SIZE){const size_t round (1 (tlsf_fls_sizet(size) - SL_INDEX_COUNT_LOG2)) - 1;size round;}mapping_insert(size, fli, sli);
}static void mapping_insert(size_t size, int* fli, int* sli)
{int fl, sl;if (size SMALL_BLOCK_SIZE){/* Store small blocks in first list. */fl 0;sl tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT);}else{fl tlsf_fls_sizet(size);sl tlsf_cast(int, size (fl - SL_INDEX_COUNT_LOG2)) ^ (1 SL_INDEX_COUNT_LOG2);fl - (FL_INDEX_SHIFT - 1);}*fli fl;*sli sl;
}mapping_search先对size做一个四舍五入再根据size计算fl和sl作为下一步的search_suitable_block的起点。
static block_header_t* search_suitable_block(control_t* control, int* fli, int* sli)
{int fl *fli;int sl *sli;/*** First, search for a block in the list associated with the given** fl/sl index.*/unsigned int sl_map control-sl_bitmap[fl] (~0U sl);if (!sl_map){//没有free_block存在搜索下一个first levelconst unsigned int fl_map control-fl_bitmap (~0U (fl 1));if (!fl_map){//没有可用的free block内存已经用完return 0;}fl tlsf_ffs(fl_map);*fli fl;sl_map control-sl_bitmap[fl];}tlsf_assert(sl_map internal error - second level bitmap is null);sl tlsf_ffs(sl_map);*sli sl;//返回分割链表的第一个free blockreturn control-blocks[fl][sl];
}
