引言

由于动态内存分配存在着执行时间不确定与内存碎片过多等问题，嵌入式实时系统中很少使用。TLSF动态内存算法中内存分配与释放均为常数，并且具有内存自动合并、灵活性强、内存碎片少等特点[1]。实时操作系统μC/OSII中内存分配使用的是一种静态内存分区方式，内存分配与释放的时间是确定的，缺乏灵活性，而且内存的分配与释放都需要指定正确的内存分区[2]，使用比较麻烦，容易出错。

本文把TLSF移植到μC/OSII中，以提高内存分配的灵活性与执行的实时性，并通过软件仿真测试TLSF在μC/OSII操作系统中的运行效果。

图1 TLSF数据结构图

1 对TLSF的简介

TLSF是一种二级隔离适应算法，使用位图与链表相结合的方式对内存池进行管理。TLSF实现过程如下： 定义一级索引最大值MAX_FLI（小于32）与二级索引最大值MAX_SLI，MAX_SLI等于2的 MAX_LOG2_SLI次方（MAX_LOG2_SLI为程序中计算方便定义的）；申请一块大的内存池，通过定义全局变量作为内存池，或者使用操作系统申请一块比较大的内存区（池）使用；使用tlsf_malloc函数申请内存，使用tlsf_free函数释放内存，还包括realloc与calloc函数等函数[3]。

TLSF的数据结构如图1所示。

使用如同μC/OSII中管理任务就绪表的形式定义变量FL_bitmap与SL_bitmaps[]，空闲链表中有空闲块相应位置1。使用一级索引fl与二级索引sl确定对应空闲链表中空闲块的大小值的范围。fl确定了此一索引管理的内存范围是[2^fl，2^(fl+1) )。二级索引值sl表示一级索引被平分为sl块[4]。

2 TLSF中用到的变量与结构体

2.1 tlsf_t结构体

每个内存区（池）都使用结构体tlsf_t管理，此结构存储在内存区的首部，其结构如下：

typedef struct TLSF_struct {

u32_t tlsf_signature;

/*TLSF算法标识符/标志符，用来区别于别的算法*/

#if TLSF_USE_LOCKS

TLSF_MLOCK_T lock;

/*TLSF锁，用于多线程访问的情况*/

#endif

#if TLSF_STATISTIC

/*统计功能，用于记录使用了多少内存，使用的内存最大值*/

size_t used_size;

size_t max_size;

#endif

area_info_t *area_head;

/*用于链接所有的内存区（池），链接不连续的内存区*/

/*位图，用于标志所在空闲链表中有无空闲块，有为1*/

u32_t fl_bitmap;

u32_t sl_bitmap[REAL_FLI];

bhdr_t *matrix[REAL_FLI][MAX_SLI];

/*空闲内存块链表，用于存储相应空闲内存块*/

} tlsf_t;

此结构体也记录内存区的基本信息，在tlsf.c中定义全局变量“static char *mp = NULL;”管理所有的内存区。在结构体tlsf_t中还用到两个结构体： area_info_t与bhdr_t。

2.2 结构体area_info_t

结构体area_info_t用来链接各个不相邻的内存区，其结构如下：

typedef struct area_info_struct {

bhdr_t *end;

/*指向末内存块，内存区（池）最后一块，低2字*/

struct area_info_struct *next;

/*指向下一个内存区（池），新增的内存*/

} area_info_t;

2.3 结构体bhdr_t

结构体bhdr_t存储各个空闲链表的表头，如果此链表中无空闲内存块，则为null。结构体如下所示：

typedef struct bhdr_struct {

struct bhdr_struct *prev_hdr; /*指向前一个物理内存块*/

size_t size;

/*内存块的大小，不包括prev_hdr与size的大小 */

/*由bit 1可知前一块是否空闲*/

union {

struct free_ptr_struct free_ptr;

u8_t buffer[1];/*读取buffer的值等于读取其地址，即此联合体的首地址，便于读取内存块的首地址*/

} ptr;

} bhdr_t;

而结构体struct free_ptr_struct用来链接一链表中的各个空闲内存块，结构如下：

typedef struct free_ptr_struct {

struct bhdr_struct *prev; /*链接逻辑上的前一个内存块*/

struct bhdr_struct *next; /*链接逻辑上的后一个内存块*/

} free_ptr_t;

3 TLSF中用到的函数

TLSF算法主要包括： 内存区的初始化函数init_memory_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，这也是整个内存区所管理的动态内存大小。

图2 内存区处理后的结构图

3.2 内存分配函数tlsf_malloc

此函数实现内存的分配，参数为内存大小，返回为内存首地址。其伪函数如下所示：

void *tlsf_malloc(size_t size){

void *ret;

#if USE_MMAP || USE_SBRK

……//当内存未初始化时，操作系统分配内存并初始化

#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 malloc_ex()流程

3.3 释放内存函数tlsf_realloc

内存释放的主要工作在函数free_ex中实现，主要是判断释放内存块的前后内存块是否也是空闲的，如果是空闲内存块，两块内存块合并为一个大的内存块，并根据内存大小加入相应的空闲链表中，并调整bit位。其伪代码如下：

void free_ex(void *ptr，void *mem_pool){

……/*得到b块后面的相邻物理块指针*/

if (tmp_b>size & FREE_BLOCK) {

/*b块后面的内存块free则合并内存*/

……/*根据tmp_b大小求出一级与二级索引值*/

……/*提取内存块，并根据内存块在链表中的位置调整空闲链表与位图标志位*/

…… /*把b（ptr）后面的内存块合并到b内存块中，size更新*/

}

if (b>size & PREV_FREE) {

…… /*b块前一块free？free则与前面的内存块合并*/

}

…… /*把调整过的内存块插入相应链表的表头*/

}

与内存分配相关的函数还包括tlsf_realloc、tlsf_calloc等，其实现过程与tlsf_malloc函数类似。

4 TLSF移植到μC/OSII

对TLSF的移植十分简单，需要与TLSF锁相关函数，包括锁的创建、申请、释放、消耗等功能，使用互斥量来实现TLSF锁功能[5]。相应的函数如下：

#include "ucos_ii.h"//加入头文件，需要使用互斥量来实现锁的功能

INT8U perr;

#define TLSF_MLOCK_T OS_EVENT*/*互斥量锁类型*/

#define TLSF_CREATE_LOCK(l) (*(l)) = OSMutexCreate (4，&perr) /*创建互斥量*/

#define TLSF_DESTROY_LOCK(l) OSMutexDel (*(l)，OS_DEL_ALWAYS，&perr) /*删除互斥量*/

#define TLSF_ACQUIRE_LOCK(l) OSMutexPend(*(l)，0，&perr) /*请求互斥量*/

#define TLSF_RELEASE_LOCK(l) OSMutexPost(*(l)) /*发送互斥量*/

5 实验测试

本次实验使用Keil4软件开发环境，以基于CortexM3内核的LPC1768处理器作为硬件测试环境[6]，利用软件仿真功能，对移植了TLSF后的实时操作系统进行测试。

测试方法是： 创建4个任务，每个任务请求内存，延时一段时间后释放内存，再延时一段时间分配内存。部分函数如下：

while(1){

p0 = tlsf_malloc(8*i0);

i0++;

if(i0==5)

i0=1;

OSTimeDly(OS_TICKS_PER_SEC);

tlsf_free(p0);

OSTimeDly(OS_TICKS_PER_SEC );

}

而在系统时钟中每隔1000个时钟节拍，执行print_all_blocks((tlsf_t *) mp)。此函数为TLSF内部自带的调试函数，用于输出各个内存块的使用情况。

系统运行输出情况如图4所示。

经实验测试，系统可正常运行。移植成功，内存碎片很少，得到了理想的效果。

图4 系统运行输出情况

结语

TLSF是一种适用于嵌入式系统的动态内存分配算法，具有很好的时间复杂度与很少的内存碎片，而且此算法是开源的，可以很好地应用到小型嵌入式系统中。