大家好，又见面了，我是你们的朋友全栈君。
上一节讲到了TLSF的数据结构，下面继续哈。
TLSF用两个层次的分类对不同尺寸的内存块进行分类。第一层次的类别目录为2n，n为4，5，……，31的整数，称为FLI（First-level Segregated Fit）。每一个FLI类别又根据第二层的SLI细分为2SLI个子类别。第二层的每个类别，都对应一条属于该类别尺寸范围内的内存块链表。为了加快分配与合并内存块的速度，链表是不排序的。所有的链表头指针用数组元素尺寸为32位的二维数组存储起来。各个类别所表示的内存块尺寸范围可参见图1。第一层次、第二层次都使用位图指示该类别有无空闲内存块，有则该类别对应的位为1，否则为0。详情看上图哈。图里说的很明显了。
1.1 TLSF数据结构
TLSF 将管理内存块所需要的信息嵌入到每一个模块中（无论模块空闲与否）并将联系模块的指针放入到两个链表： 带有一定大小内存块的链表和由物理地址管理的链表。这种数据结构称为“头部结构”。由于申请内存块的大小一般为4 的倍数，所以两个最低有效位用来表示内存的状态：内存块是否空闲（F 位），内存块是否是内存池中的最后一个（T 位）。我们利用公式1 来确定所申请内存处于的链表位置[3]：
例如，假设SLI=4 且size=460，则第一级目录中的f=8，第二级目录中的s=12。
好，TLSF的数据结构就讲这么多，下面详细讲解下TLSF算法。
2 .首先说下用到的结构体。
上一节说到了TLSF的结构体，它里面还定义了一些结构体。下面看一下定义。
2.1 area_info_t 结构体
结构体area—info—t用来链接各个不相邻的内存区，
其结构如下：
代码语言：javascript复制/*由于连接多个内存区，*/
typedef struct area_info_struct {
bhdr_t *end; /*指向末内存块,，内存区(池)最后一块，低2字*/
struct area_info_struct *next; /*指向下一个内存区，新增的内存*/
} area_info_t;2.2 bhdr_t 结构体 结构体bhdr_t存储各个空闲链表的表头，如果此链表中无空闲内存块，则为null。
结构体如下所示：
代码语言：javascript复制typedef struct bhdr_struct {
/* This pointer is just valid if the first bit of size is set */
struct bhdr_struct *prev_hdr; /*指向前一个物理内存块*/
/* The size is stored in bytes ，size之后归此bhdr_t控制块管理的内存块大小*/
size_t size; /* bit 0 indicates whether the block is used and */
/* bit 1 allows to know whether the previous block is free */ /*内存块的大小，不包括prev hdr与size的大小*/
union {
struct free_ptr_struct free_ptr;
u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; ，注意读取buffer的值等于读取其地址
即此联合体的首地址，便于读取ptr的首地址。 */
} ptr;
} bhdr_t;而结构体struct free_ptr_structt用来链接一链表中的各个空闲内存块，
结构如下：
代码语言：javascript复制typedef struct free_ptr_struct {
struct bhdr_struct *prev;/*链接逻辑上的前一个内存块*/
struct bhdr_struct *next;<span style="font-family: Arial, Helvetica, sans-serif;">/*链接逻辑上的后一个内存块*/</span>
} free_ptr_t;好，结构体就有这些。等到我们移植的时候也是移植这些结构体。
下面说下TLSF算法用到的一些函数。
3. 重要函数！
TLSF算法主要包括：内存区的初始化函数imtmemory_pool（）、内存区销毁函数destroy_memory_pool()、增加内存区函数add_new_area()，以及内存分配相关的函数tlsf_malloc()、tlsf_free()、tlsf_realloc()、tlsf_calloc()等，还有一些自己带的打印内存块状态信息的打印函数等调试函数。
3.1 内存池初始化函数init_memory_pool()
此函数用来初始化一块大的内存区，为结构体tlsf赋值(内存区首地址的N个字节)，并通过调用函数process_area对剩下的内存区进行处理，处理后的内存如图2所示。之后，把内存块b释放掉，得到初始内存块b，这也是整个内存区所管理的动态内存大小。
3.2 内存池销毁函数destroy_memory_pool()
代码语言：javascript复制/* 内存池销毁函数*/
/******************************************************************/
void destroy_memory_pool(void *mem_pool)
{
/******************************************************************/
tlsf_t *tlsf = (tlsf_t *) mem_pool;
tlsf->tlsf_signature = 0; /* 用来表示内存区销毁*/
TLSF_DESTROY_LOCK(&tlsf->lock); /* 操作系统函数相关，或自定义函数*/
}3.3内存分配函数tlsf_malloc()
代码语言：javascript复制/* 函数功能：tlsf内存分配函数
形参： size 所需内存的大小
返回： viod * （无符号指针）。分配成功后，返回内存块的指针ret；分配失败返回NULL。
*/
/******************************************************************/
void *tlsf_malloc(size_t size)
{
/******************************************************************/
void *ret;
#if USE_MMAP || USE_SBRK
if (!mp) { /* 如果分配内存块时，没有初始化一个内存区，可以使用以下函数得到一个内存区，并初始化此内存区*/
size_t area_size;
void *area;
area_size = sizeof(tlsf_t) BHDR_OVERHEAD * 8; /* Just a safety constant */
area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
area = get_new_area(&area_size);
if (area == ((void *) ~0))
return NULL; /* Not enough system memory */
init_memory_pool(area_size, area);
}
#endif
TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock); /*获取上锁，与操作系统有关*/
ret = malloc_ex(size, mp);
TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock); /*获取解锁，与操作系统有关*/
return ret;
}此函数中，主要是通过内部内存分配函数malloc_ex()来实现的，
其流程如图3所示。
3.4 内存释放函数tlsf_free() 内存释放的主要工作在函数free_ex()中实现，主要是判断释放内存块的前后内存块是否也是空闲的，如果是空闲内存块，两块内存块合并为一个大的内存块，并根据内存大小加入相应的空闲链表中，并调整bit位。
代码语言：javascript复制/* 函数功能：tlsf内存释放函数
形参： ptr 所需内存的首地址指针
返回： viod 无返回
*/
/******************************************************************/
void tlsf_free(void *ptr)
{
/******************************************************************/
TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock); /*上锁，与操作系统有关*/
free_ex(ptr, mp);
TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock); /*解锁，与操作系统有关*/
}/* 函数功能：释放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*/
}除了这些函数外，还有很多的函数用到。这些需要大家看源码了哦。不过重要的函数就这几个哈。
下节讲讲怎么讲这个算法移植到uc/os上哈！
未完待续！！
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/149111.html原文链接：https://javaforall.cn
