tlsf
上一篇我们看了dsa的分类和简单的内存管理算法实现，这篇文档我们来看TLSF的实现，一种更加高级的内存管理算法；
一、实现原理
基本的Segregated Fit算法是使用一组链表，每个链表只包含特定长度范围来的空闲块的方式来管理空闲块的，这样链表数组的长度可能会很大。TLSF为了简化查找定位过程，使用了两层链表。
第一层，将空闲内存块的大小根据2的幂进行分类，如（16、32、64...），第一级的索引值fli决定了这一级内存块的大小，范围为[2^i,2^(i+1)];第一级索引值一般是动态计算出来，其经验值为
第二层链表在第一层的基础上，按照一定的间隔，线性分段，其范围应该在1-32，对于32bit的处理器，第二级的索引值sli一般为4或者5(经验值)。
下面这个图很好的说明了fl和sl这两级索引的作用，FL_bitmap和SL_bitmaps[]的每个bit代表是否被使用，下图将fl分为8级，sl分为4级，这里说明下，下图sl分了8个小区，我们计算sl时会将8个小区合为4个小区；
比如2的6次方这一段，分为4个小区间[64,80），[80,96)，[96,112)，[112，128)，每一级的链表都有一个bitmap用于标记对应的链表中是否有内存块。比如第一级的FL_bitmap为110...1..0,次高位为1，次高位对应着2的6次方这一段，说明这一段有空闲块，其对应的第二级链表的SL_bitmap位00000010，其对应着[80,96)这个区间有空闲块，即下面的89 Byte；
通过两级索引来查找或释放内存，malloc与free的所有操作花费是个时间常数，时间响应复杂度都为O(1)；
二、代码分析
对于TLSF的分析，我们也同之前一样，分析init、malloc、free三个函数，完整代码等上传后会更新下载地址；
我们分析的是TLSF-2.4.6，其他TLSF-1.0和TLSF3.0版本等我都上传到svn，；
1、申请内存池：
/* 初始化内存池，*/
size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
{
tlsf_t *tlsf;
bhdr_t *b, *ib;
/* 内存池指针非空，内存池大小非零*/
if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
return -1;
}
if (((unsigned long) mem_pool & PTR_MASK)) {/* PTR_MASK =0x03 即mem_pool低两位都为0，对齐到一个字（相对于32位的就是4个字节）*/
ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
return -1;
}
tlsf = (tlsf_t *) mem_pool; /*此内存区，如果是上电初始化，则内存区为空*/
/* Check if already initialised 此内存池已经初始化了*/
if (tlsf->tlsf_signature == TLSF_SIGNATURE) {/* 销毁此内存区（内存池）时，tlsf_signature赋值0*/
mp = mem_pool;
b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
return b->size & BLOCK_SIZE;
}
mp = mem_pool;
/* Zeroing the memory pool */
memset(mem_pool, 0, sizeof(tlsf_t)); /* 内存池首sizeof(tlsf_t)字节清零，*/
tlsf->tlsf_signature = TLSF_SIGNATURE;
TLSF_CREATE_LOCK(&tlsf->lock);
/* 对内存池中tlsf_t控制块之后的内存空间处理，返回bhdr_t类型指针ib*/
ib = process_area(GET_NEXT_BLOCK
(mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE); /* 调整指针指向*/
free_ex(b->ptr.buffer, tlsf); /* 删除b内存块，并根据情况合并内存块，更新相应信息*/
tlsf->area_head = (area_info_t *) ib->ptr.buffer; /* tlsf初始化为ib->ptr.buffer*/
#if TLSF_STATISTIC
tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
tlsf->max_size = tlsf->used_size;
#endif
return (b->size & BLOCK_SIZE); /* 返回内存池中可用内存大小（总可分配动态内存大小）*/
}分析函数前先看几个结构体：
typedef struct free_ptr_struct {
struct bhdr_struct *prev;
struct bhdr_struct *next;
} free_ptr_t;typedef struct bhdr_struct {
//prev_hdr指向前一内存块，只有当size的bit0为1（当前块被使用）时才有效
struct bhdr_struct *prev_hdr;
//size存储了剩余内存空间的大小，但最低两位用来做使用标识，其中最低位bit0表示当前块是否使用，bit1表示前一内存块是否被使用，置0表示使用，1表示未使用；
size_t size;
union {
struct free_ptr_struct free_ptr;
u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; ，注意读取buffer的值等于读取其地址即此联合体的首地址，便于读取ptr的首地址。 */
} ptr;
} bhdr_t;
/* This structure is embedded at the beginning of each area, giving us
* enough information to cope with a set of areas */
/*由于连接多个内存区，*/
typedef struct area_info_struct {
bhdr_t *end; /*指向末内存块*/
struct area_info_struct *next; /*指向下一个内存区，新增的内存*/
} area_info_t;
typedef struct TLSF_struct {
/* the TLSF's structure signature */
u32_t tlsf_signature;
#if TLSF_USE_LOCKS
TLSF_MLOCK_T lock;
#endif
#if TLSF_STATISTIC
/* These can not be calculated outside tlsf because we
* do not know the sizes when freeing/reallocing memory. */
size_t used_size;
size_t max_size;
#endif
/* A linked list holding all the existing areas */
area_info_t *area_head;
/* the first-level bitmap */
/* This array should have a size of REAL_FLI bits */
u32_t fl_bitmap;
/* the second-level bitmap */
u32_t sl_bitmap[REAL_FLI];
bhdr_t *matrix[REAL_FLI][MAX_SLI];
} tlsf_t;这么多结构体是否有些眼花缭乱，我们重点看下TLSF_struct和bhdr_struct，TLSF内存管理区的开头都会有一个TLSF_struct结构体，它存储了有关TLSF操作的相关信息，其中matrix[REAL_FLI][MAX_SLI]存储了所有分区的使用情况，fl_bitmap和sl_bitmap就是上面图分析的一级和二级索引，用位来标明是否是否有空闲块；
在TLSF中，内存块单位是由bhdr_struct来管理的，它内部结构体并不复杂，笔者已经对每个成员做了注释，相信不难理解，因为这里是以字方式对其，所以成员变量size的低2bit都为0，所以可以来代表其他含义；
了解了这些结构体，我们就可以着手分析函数了，这里关键是process_area函数，它负责将新的内存块分区：
static __inline__ bhdr_t *process_area(void *area, size_t size)
{
bhdr_t *b, *lb, *ib;
area_info_t *ai;
ib = (bhdr_t *) area;
ib->size =
(sizeof(area_info_t) <
MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
lb->prev_hdr = b;
lb->size = 0 | USED_BLOCK | PREV_FREE;
ai = (area_info_t *) ib->ptr.buffer;
ai->next = 0;
ai->end = lb;
return ib;
}这个函数实现并不复杂，它初始化了我们的之前申请的内存区域，我们先看下他的输入参数：
ib = process_area(GET_NEXT_BLOCK(mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
这里有两个入参，一个是mem_pool+sizeof(tlsf_t)地址，即我们TLSF申请的整个内存地址加上tlsf_struct所占用的地址，得到未使用内存的首地址，第二个参数是这块地址的大小，process_area函数的功能我通过下面的图进行说明，它初始化了mem_pool的内存区域；
如上图所示，process_area函数在mem_pool的开始定义了三块block，分别是ib，b，lb，上图对每一块的内存做了说明，尤其是size的最低2bit，我们在下面的函数中还会用到，还要注意process_area返回的是ib的地址；
回到init_memory_pool函数，接下来执行free_ex(b->ptr.buffer, tlsf);
/* 函数功能：释放ftr所在的内存块，并根据情况合并前后内存块，更新相应bitmap标志位
形参： ptr 释放内存指针； men_pool 内存池的首地址
返回： viod * （无符号指针）。分配成功后，返回内存块的指针ret；分配失败返回NULL。
*/
/* */
void free_ex(void *ptr, void *mem_pool)
{
tlsf_t *tlsf = (tlsf_t *) mem_pool;
bhdr_t *b, *tmp_b;
int fl = 0, sl = 0;
if (!ptr) { /*ptr为NULL，直接返回*/
return;
}
b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
b->size |= FREE_BLOCK; /* 所释放内存块状态更新（size后两位更新）*/
TLSF_REMOVE_SIZE(tlsf, b); /* #if TLSF_STATISTIC */
b->ptr.free_ptr.prev = NULL;
b->ptr.free_ptr.next = NULL;
tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); /* 得到b块后面的相邻物理块指针*/
if (tmp_b->size & FREE_BLOCK) { /* b块后面块是free的？其后内存块free则合并内存*/
MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl); /* 根据tmp_b大小求出一级与二级索引值*/
EXTRACT_BLOCK(tmp_b, tlsf, fl, sl); /* 提取内存块，并根据内存块在链表中的位置调整空闲链表与位图标志位*/
b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD; /* 把b（ptr）后面的内存块合并到b内存块中，size更新*/
}
if (b->size & PREV_FREE) { /* b块前一块free？free则与前面的内存块合并*/
tmp_b = b->prev_hdr; /* 得到b块前1物理块 */
MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
b = tmp_b; /* 更新b指针的值，即b指向合并后的内存块地址*/
}
MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl); /**/
INSERT_BLOCK(b, tlsf, fl, sl); /* 把释放的内存块插入相应链表的表头*/
tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
tmp_b->size |= PREV_FREE; /* 更新后一块的信息，以表示释放的内存块空闲的*/
tmp_b->prev_hdr = b; /* 更新后一块内存块的物理块prev_hdr*/
}上面代码第15行的b指向的地址就是上面图示中的内存块b的首地址，如果能看懂这点，就可以继续往下；
代码中两个if执行的条件，都不会执行；
if (tmp_b->size & FREE_BLOCK)，这里的tmp_b其实是在上面process_area函数中的b内存块，b内存块的size赋值为USED_BLOCK，即为0，所以这里不会执行；
if (b->size & PREV_FREE) ，这里的b为process_area函数中的ib内存块，ib赋值为PREV_USED，即为0，所以这里也不会执行；
然后是函数MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);这个函数是用我们之前介绍的利用大小计算两级f1和s1的值，源码已经给出，感兴趣的可以仔细研究，这里我们只需要知道MAPPING_INSERT函数用我们前面列出的公式，通过size得到了f1和s1；
INSERT_BLOCK(b, tlsf, fl, sl);是将b内存块插入内存块双向链表；
/* 插入内存块，且总是查入表头*/
#define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
_b -> ptr.free_ptr.prev = NULL; /* 插入表头，则前项指针为空*/ \
_b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
if (_tlsf -> matrix [_fl][_sl]) /*若原链表非空，原表头的前项指针指向_b内存块，以形成双向链表*/
_tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
_tlsf -> matrix [_fl][_sl] = _b; \
set_bit (_sl, &_tlsf -> sl_bitmap [_fl]);/*更新位图标志位*/ \
set_bit (_fl, &_tlsf -> fl_bitmap); \
} while(0)这里的while(0)是为了程序的健壮性，可自行百度，我们在pool_mem开头定义了tlsf_struct结构体，这个宏的主要作用就是将内存块b放到双向链表_tlsf -> matrix [_fl][_sl]中，插入时都是往表头插入；
这里想说明的一点是，这里是在初始化函数调用的INSERT_BLOCK宏，这里插入的位置是_fl=0,_sl=0，将上面内存图示的b块首地址赋给了_tlsf->matrix[0][0];
set_bit是置位操作，我们前面说过，如果为1，其对应位上的内存块就为空闲，当有使用时，需要调用clear_bit进行清零；
到这里内存初始化函数就分析完了，我们得到了一大块可用内存，并且通过bitmap（两级索引）来管理内存块；
2、malloc：
/* 函数功能：ex内存分配函数，实际内存分配函数
形参： size 所需内存的大小； men_pool 内存池的首地址
返回： viod * （无符号指针）。分配成功后，返回内存块的指针ret；分配失败返回NULL。
*/
void *malloc_ex(size_t size, void *mem_pool)
{
tlsf_t *tlsf = (tlsf_t *) mem_pool;
bhdr_t *b, *b2, *next_b;
int fl, sl;
size_t tmp_size;
/* 调整size值，最小为MIN_BLOCK_SIZE，最小（sizeof(free_ptr_t)）*/
size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
/* Rounding up the requested size and calculating fl and sl */
MAPPING_SEARCH(&size, &fl, &sl); /* 查找满足所需内存大小的一级与二级索引，size的值被调整为所需状态*/
/* Searching a free block, recall that this function changes the values of fl and sl,
so they are not longer valid when the function fails */
b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl); /* 根据fl与sl的值得到适合的内存块的链表的表头*/
/* 以下部分是用于当前内存池中，没有所需内存块时，从内存中得到新的内存区（使用sbrk or mmap函数）*/
#if USE_MMAP || USE_SBRK
......
#endif
if (!b) /* 如果b空闲链表表头为NULL，表示分配内存失败！*/
return NULL; /* Not found */
EXTRACT_BLOCK_HDR(b, tlsf, fl, sl); /* 根据一级与二级索引值，从相应链表中得到内存块，并调整bitmap位图*/
/*-- found: */
next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); /* 根据b->size得到next的物理相邻内存块*/
/* Should the block be split? */
tmp_size = (b->size & BLOCK_SIZE) - size; /* 分割所需内存，得到剩余内存大小*/
if (tmp_size >= sizeof(bhdr_t)) { /* 分割后的剩余内存值大于等于sizeof(bhdr_t)值，即大于等于一个块头*/
tmp_size -= BHDR_OVERHEAD;
b2 = GET_NEXT_BLOCK(b->ptr.buffer, size); /* 得到剩余内存块的地址*/
b2->size = tmp_size | FREE_BLOCK | PREV_USED; /* 为分割下来的内存块的size赋值*/
next_b->prev_hdr = b2; /* next_b内存块链接相邻的前一个物理内存块*/
MAPPING_INSERT(tmp_size, &fl, &sl); /* 查找剩余内存块的空闲链表的一级与二级索引值*/
INSERT_BLOCK(b2, tlsf, fl, sl); /* 插入内存块，且总是查入表头*/
/* 更新b2块的前一块的内存地址，*/
/*add by vector,right?*/ b2->prev_hdr = b;
/* size后两位更新，只把0bit改为USED_BLOCK*/
b->size = size | (b->size & PREV_STATE); /* 参数size为所需内存大小，更新b块的状态*/
} else { /* 所得内存块不需要分割，只需更新size的后两位*/
next_b->size &= (~PREV_FREE);
b->size &= (~FREE_BLOCK); /* Now it's used */
}
TLSF_ADD_SIZE(tlsf, b);
return (void *) b->ptr.buffer;
}看懂了前面的初始化函数，这个malloc函数就比较好理解了，可以分三步看这个函数：
step1.函数MAPPING_SEARCH(&size, &fl, &sl);它根据malloc入参size计算出fl和sl的值，公式之前已经给出；
step2.函数EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);这个函数根据fl和sl的值提取出需要的内存，并给相对应的bitmap清零，标明这块内存已经使用；
step3.if...else部分，这部分是处理切割内存的，如果申请的内存区域可以被切割，就将其割为更小的块，并做相应处理；
malloc函数还是比较简单的，这里不做赘述了；
3、free函数
我们在init函数中，其实已经分析了free函数；
好的，到这里我们已经将TLSF的主要思路介绍明白了，TLSF其实还要负责的多，代码中有许多优化处理，包括公式与c代码的转换；比如ffs和fls，分别表示find first set（返回最低位为1的位置）和find last set（返回最高位为1的位置），ffs可以在c中找到刚好大于size（申请大小）的内存块位置；fls可以用来计算下面函数：
其他细节可以下载TLSF代码学习，稍后笔者会把1.0-3.0三个版本代码都上传上去，希望大家多多支持；
相关阅读
最近开始研究推荐系统，其中常见的相似度算法有以下几种：1. 欧几里得距离欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用