uC/os内存优化——TLSF算法

大家好，又见面了，我是你们的朋友全栈君。

需求

uC/os内存管理机制为内存块形式，用户申请内存是需要自己指定内存区内内存块数和内存块大小，看起来很灵活，实际上很不方便，需要使用者记住内存块大小，自己维护内存区，给使用者增加了负担。

TLSF算法能够满足实时性的要求，并且可有效的较小内部碎片。TLSF作为分离式空闲链表算法（Segregated Free Lists）的拓展–将相似的空闲块利用数组或者二叉树进行管理从而使响应时间与空闲块数量相互独立，能够满足实时系统的需求。LINUX使用的兄弟算法，能将碎片控制在内存块大小的1/2之下，而TLSF算法将内存块大小进行更细致的分类，将内部碎片尽量缩小。TLSF在内存释放时则会立即释放并且与相邻的空闲内存进行合并。其他的DSA或许会进行延迟合并，或者根本不合并。这种机制在应用反复申请相同大小的内存时会很有用，但是延迟合并带来的是时间的不可预测，所以TLSF避免了这种现象。

算法思想

TLSF的全称是Two Level Segregated Fit memory allocator，名称就显示了此算法的特点，segregated fit 和 two level。基本的Segregated Fit算法是使用一组链表来管理空闲块，每个链表只包含特定长度范围内的空闲块，而管理这些链表头的数组会非常冗长，TLSF使用了二位数组来管理这些表头，简化了查找定位的过程。在第一层将空闲块大小按照2的次幂进行粗分，因为内存块大小至少为2^4，所以一般分为（16、32、、、、2^31），第二层在第一层的基础上，按照规定好的间隔对内存块进行细分，比如我们可以将2^4~2^5大小的内存块进一步分为（16~20），（20~24），（24~28），（28~32）。分成几个区间可以由用户设定（但一定是2的次方个）。每一级都对应bitmap中的一个位来表示是否有空闲块。

内存状态立体化结构如图

比如上图中第一级的bitmap中第三位为1，那么就有大小为2^6~2^7的空闲块，再查看二级Bitmap,第二位为1说明有大小为2^6+16~2^6+32的空闲块。

那么给定一个内存大小怎么知道他所对应的一二级索引值呢

我们可以观察到，f的值为size的最高有效位的位数。S为偏移量除以区间大小。

算法实现

数据结构

代表链表中各个空闲块

typedef struct free_ptr_struct {
    struct bhdr_struct *prev;
    struct bhdr_struct *next;
} free_ptr_t;

//各个空闲表的表头
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;                /* 第0位表示此块是否被使用 */
    /* 第1位表示此块的前一内存块是否空闲*/
    /*联合体，buffer[0]内值即为free_ptr地址=此块首地址*/
    union {
        struct free_ptr_struct free_ptr;
        u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; ，注意读取buffer的值等于读取其地址
								即此联合体的首地址，便于读取ptr的首地址。 */
    } ptr;
} bhdr_t;

连接多个内存区

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;

辅助函数

size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)

此函数是内存池的初始化函数，返回值是实际可用的内存大小（可用于动态分配），参数是初始化时内存池的大小和内存池的首地址，使用时可以建一个数组并把数组大小和数组名当参数使用，需要注意的是，初始化后TLSF_STRUCT会放在首地址处，且内存池中只有一个内存区。

static __inline__ bhdr_t *process_area(void *area, size_t size)

此函数为内存区初始化函数，初始化函数会调用它来完成第一个内存区的初始化，添加内存区的函数也会调用它。返回值是内存区的首个块的指针（此块用来连接各个区，记录本区最后一个块），参数是区的起始地址和区的大小，此函数会将内存区分为三个块，首块，中块，末块。中块就是我们用来分配内存的块。

void free_ex(void *ptr, void *mem_pool)

此函数用来释放内存块，所谓的释放内存块就是将使用完的内存块放回MATRIX中，并且改变BITMAP的值，在放回前需要检查物理相邻块是否可以合并。而在初始化函数中调用此函数，可以把第一个内存区的中块放入到MATRIX中来满足第一次的内存申请，换言之就是初始化BITMAP和MATRIX。参数是指向待释放块的bhdr_t中的ptr指针和内存池地址。

void *malloc_ex(size_t size, void *mem_pool)

此函数用来申请内存，参数传递所需要的块大小和内存池地址，此函数会先调用函数MAPPING_INSERT计算出内存块大小对应的第一级索引FL与第二级索引SL，再根据这两个参数调用函数FIND_SUITTABLE寻找到大于要求SIZE的空闲块。如果没能在现有内存区中找到可用的内存块，那么会使用 get_new_area 函数申请新的内存，再用add_new_area将此内存加入内存池。若系统物理内存已经不足，那么分配失败。若分配成功，则将内存块分割，得到剩余的内存也放入MATRIX对应的链表中。

void destroy_memory_pool(void *mempool)

此函数用于销毁内存池，将tlsf_signature置0即可。

size_t add_new_area(void *area, size_t area_size, void *mem_pool)

此函数用于将新建内存区加入内存池，并判断此内存区是否可与之前存在的内存区进行合并（如果物理相邻）。参数为新建内存区的地址和大小，我们可以通过get_new_area调用操作系统动态内存申请函数申请新的内存区。

剩下还有一些辅助函数：

static __inline__ void MAPPING_SEARCH(size_t *_r, int *_fl, int *_sl)

此函数用来找到能容纳所要求大小的内存块的一二级检索fl和sl,因为原大小_r，对应的fl和sl找到的内存块链表中的内存块不一定能容纳_r,所以该函数要先增大_r到下一个大小区间。

static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)

此函数与MAPPING_SEARCH很相似，只是不用将大小再扩大。

关键函数

Process_area()区处理函数，对内存块进行相应的处理，如下图所示区初始形态。

Add_new_area() 增加新的区，如果新区与原有内存池物理相邻，则合并两个相邻的内存区，否则通过区头相链，如下图所示，右侧为每个新加入的区。

void *tlsf_malloc(size_t)  内存分配函数，size为所需内存块的大小，分配成功后返回内存块指针ret，失败返回NULL，主要工作在malloc_ex（）中实现。malloc_ex()代码程序框图如图所示，源码较多，暂不列出，有能力的小伙伴可以自己尝试实现。

void *tlsf_free(void *ptr)  内存释放函数ptr为释放内存的首地址，主要工作在free_ex()中实现，判断释放内存块前后相邻块是否为空闲，如果空闲将两个内存块合并为一个大的内存块，并根据大小加入相应的空闲链表，最后调整位图。

以上内容为算法源码主要思想及主要代码

算法移植

该算法移植是基于Linux系统下开发的，而我是移植到window下运行，会有点问题，所以建议大家还是在linux下移植。

首先，我们把算法中用到的宏定义移植到了os_cfg.h文件中，放到了该文件的最底部。

然后我们将该算法的结构体定义到了os.h文件memory部分中，并将所有数据类型统一为uC/os中的数据格式，CPU_INT08U,CPU_INT32U等。同时将以下代码加入到了os.h文件中

最后在工程中source文件下建立os_tlsf.c和os_tlsf.h文件，将算法的源码移植到.c文件中，头文件中的外部函数声明移植到.h文件中。部分文件需要添加额外的#include “os.h” 文件等。

测试代码：

该算法在Linux下运行可申请内存池大小为1024*1024B，但在windows32位程序中最多只申请了62320B的内存空间。

此算法代码用到了两个linux下的系统调用，sbrk(),map()，window下不支持这两个函数，有心得小伙伴可以尝试在window下实现替换这两个函数。

思考反思：

由于segregated fit本身机制的原因，有可能会出现有时内存明明可以容纳却无法分配的现象。比方说现在我们创建了一个为128+32字节的内存块，当我们使用一级segregated fit时，他将被存储在2^7~2^8大小的链表中，而我们接下来使用melloc申请一个大小为128+64的内存块时，因为我们无法知道2^7~2^8的链表中的块是否能一定容纳下128+64大小的块，所以会无法完成申请。当使用二级将内存块大小进一步细分时，会减少这种情况的发生概率，但是无法消除。如果在此链表上使用顺序查找，则会使得分配时间不可调度。