实时系统动态内存算法分析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)；

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三个版本代码都上传上去，希望大家多多支持；