目录
1 最初还不是tlsf
早几年(2019年之前)idf使用的堆管理器实现很简单，使用一个链表将所有(空闲和非空闲)的内存块串起来。对此，已经有同学分析过，可以参考这篇博客：esp32 heap 内存管理简析。下面这张图也是来自这篇博客，一目了然：
2 为什么要引入tlsf
旧的堆管理器的实现比较简单，性能一般，无论是申请还是释放都需要遍历整个堆，时间复杂度是O(N)，这对于RTOS是难以接受的。对此，有很多改进的方向：
- free list
- separate fit
- two level separate fit
可以认为上述三种堆管理器的实现是层层改进的。free list只会将空闲的内存块串起来，减少了申请和释放时需要遍历的链表长度。separate fit更进一步，将不同大小或不同大小范围的空闲内存块分别使用链表串起来，进一步减少了申请和释放时的时间消耗，如下图所示：
但这种实现仍然存在问题，如果坚持一个链表中的空闲内存块保持一个固定的大小，那么申请和释放固然能做到O(1)，但不同大小内存块数量的分配很难做到灵活通用，需要开发者自己根据应用来配置，不是很方便，且几乎不可能避免内部碎片的问题。如果坚持一个链表中的空闲块大小保持在一定的范围，再辅之以申请时的内存分割和释放时的内存合并，那么内存的使用会更灵活，内部碎片也更小，但申请的时候就难免需要遍历链表，做不到O(1)。
对此，two level separate fit也即tlsf被提出，具体的说，进一步细化separate fit的划分，第一级指示一个粗略的内存大小范围（这就是separate fit所做的），在第一级划分的基础上进行第二级细化——将第一级的范围进一步划分成间隔更小的子区间，进而实现在内部碎片可控的情况下，申请和释放做到O(1)。
3 tlsf算法概览
tlsf早在十多年前就被提出了，相关论文可在此处下载。本节将介绍这个算法的总体设计。
先给出tlsf的设计示意图，再对着图介绍会更清晰：
tlsf首先将内存块的大小按照2的次幂进行第一级的划分，以上图为例，第一级区间的范围分别是（起点不是固定的）：
- [24, 25 - 1)
- [25, 26 - 1)
- [26, 27 - 1)
- …
不难看出，第一级区间的个数取决于要管理的内存块的大小，第一级区间中最大的那个区间不可能超过实际的最大内存块的大小。在第一级区间划分的基础上进行均匀分割，得到第二级区间。若将第一级区间均匀划分为2SLI份（也即任一一级区间下第二级区间的个数为2SLI，SLI在实现的时候是固定不变的，是一个常量），且使用2f表示第一级区间大小范围的左边界（为方便叙述，对于一个区间的边界，本文采用左小右大），则第二级区间的区间大小为：
- 2f / 2SLI
note：其中，左边界2f表示此时第一级区间的区间范围为[2f, 2f+1 - 1)
不妨将第二级区间的区间大小记为N，则第二级区间的范围分别是：
- [2f, 2f + N)
- [2f + N, 2f + 2N)
- [2f + 2N, 2f + 3N)
- …
每个二级区间都存在一个链表（可能是空链表），这个链表上串着所有大小处于这个二级区间的空闲内存块。此外，对于一二级区间，使用位图来标识其中是否存在空闲内存块，这将使得我们可以快速查找可用区间。
不难注意到，不管是划分一级区间还是划分二级区间，都使用2的次幂，这当然是刻意为之，可以在给定内存大小，计算其应当属于哪个一二级区间时提供方便。具体的说，给定大小size，则其所属一二级区间的索引如下计算：
因为2的幂次的使用，上式可以使用位运算快速得出。至于为什么是这样算，一级索引f的计算很好理解，s的计算可以参考tlsf设计示意图中的红色标注。size减去2f得到size在所属一级区间中的偏移，用这个偏移除以二级区间的大小即可得到二级索引。得到f及s之后，通过位图可以快速判断出相应的二级区间是否存在空闲内存块。
为了实现申请内存O(1)的复杂度，tlsf使用提级申请的方式。具体的说，若申请的size落入二级区间为：
- [2f, 2f + N)
则我们不会在该区间遍历链表，而是提级到下一个区间去申请：
- [2f + N, 2f + 2N)
显然提级之后的区间中任一内存块都符合内存大小的要求，这就避免了链表遍历，实现了O(1)。这样做当然有代价——会造成内部碎片。虽然由于两级划分的机制，使得内部碎片的大小控制在2N以内。但如果size足够大，也即2f足够大，那么2N也会很大，所以tlsf还配套有内存块的申请时分割机制，控制内部碎片的大小处于一个极低的水平。
申请和释放都做到了O(1)，且内部碎片也得以控制，是否就意味着tlsf完美了呢？当然不是，还要考虑外部碎片，过多的分割会导致外部碎片增加。对此，tlsf也提供了内存块的释放时合并机制，虽然不能完全解决外部碎片，但至少能加以控制。世上并不存在完美的堆管理器，只是工程会不断权衡取舍以及改进，最终得到一个各方面性能都相对较好的。或许，对于小型嵌入式系统来说，tlsf就是那个工程选择的结果，除了idf，还有其它一些RTOS或开发框架也在使用这个算法。
4 idf中使用的tlsf算法的设计与实现
idf中使用的tlsf的实现来自一个开源项目：GitHub - mattconte/tlsf: Two-Level Segregated Fit memory allocator implementation.。基于tlsf，idf增加了一些封装，实现了上层接口与底层算法的分离，以及堆调试等特性。相关源码全部位于heap组件。下文就将介绍其中的tlsf的设计与实现，其它内容将在后续博文中介绍。
4.1 先看结构
4.1.1 管理内存块的结构
每个内存块(block)都存在一个block_header_t，这个类型定义在heap_tlsf.h：
typedef struct block_header_t
{
/* 指向物理上的前一个内存块 */
struct block_header_t* prev_phys_block;
/* 内存块的大小(申请者可以使用的大小) */
size_t size;
/* 空闲的内存块串成双向链表 */
struct block_header_t* next_free;
struct block_header_t* prev_free;
} block_header_t;
对于其中前两个字段需要进一步说明：
- prev_phys_block：这个字段的存在用于内存释放时的合并，当尝试与物理上上一个block合并时，必须知道物理上上一个内存块的位置。
- size：由于
tlsf默认会对申请的内存大小进行向上4字节对齐，因此size的最低两个bit可以用作表示其它含义。具体的，bit0为1表示当前block空闲；bit0为0表示当前block已被申请；bit1为1表示物理上前一个block空闲；bit1为0表示物理上前一个block已被申请。
tlsf在heap_tlsf_block_functions.h中定义了一些block相关的功能接口，这些功能接口大部分都通俗易懂，基本代码本身等同于注释，但也有少数需要说明一下：
- 哨兵
block
为了标识tlsf堆的物理边界，最后一个block为空，也就是一个size为0的block，可以利用这个特性来判断一个block是不是最后的那个：
static inline __attribute__((__always_inline__)) int block_is_last(const block_header_t* block)
{
return block_size(block) == 0;
}
block指针与ptr指针
在源码中经常看到block指针与ptr指针，两者的转换关系如下：
static inline __attribute__((__always_inline__)) block_header_t* block_from_ptr(const void* ptr)
{
/* (block_header_t *)((unsigned char *)ptr - offsetof(block_header_t, size) + sizeof(size_t)) */
return tlsf_cast(block_header_t*,
tlsf_cast(unsigned char*, ptr) - block_start_offset);
}
static inline __attribute__((__always_inline__)) void* block_to_ptr(const block_header_t* block)
{
/* (void *)((unsigned char *)block + offsetof(block_header_t, size) + sizeof(size_t)) */
return tlsf_cast(void*,
tlsf_cast(unsigned char*, block) + block_start_offset);
}
用图来解释更形象：
- 相邻的
block
为了优化元数据开销，block的邻接关系不是很直观。当前block的prev_phys_block字段被藏在了物理上前一个block的最后一个字，其实这本身也不难理解，但源码中有一个稍微恶心人的地方是使用sizeof(size_t)替代sizeof(block_header_t *)，虽然两者在数值上相等，但含义不一样呀。
还是以图来解释：
当我们想获取当前block的前一个block时，直接返回当前block的prev_phys_block字段即可：
static inline __attribute__((__always_inline__)) block_header_t* block_prev(const block_header_t* block)
{
return block->prev_phys_block;
}
当我们想获取当前block的后一个block时，我们需要先把ptr指针往地址增加的方向挪size个字节，再将其往地址减少的方向挪sizeof(block_header_t *)个字节：
/* 将ptr指针往下挪size个字节 */
/* 这个函数有两个让人觉得变扭的地方: */
/* 1. size是unsigned long类型，ptr被转换为long类型，两者相加的时候会发生一次隐式类型转换， */
/* 虽然目标类型是无符号类型，不至于产生未定义行为，也不会影响正确性，但非得这么写嘛。 */
/* 2. 调用该函数时，有时候size参数会传入负数，如offset_to_block(mem, -(tlsfptr_t)block_header_overhead); */
/* 虽然最终补码相加，正确性不会受到影响，但非得这么写嘛。 */
static inline __attribute__((__always_inline__)) block_header_t* offset_to_block(const void* ptr, size_t size)
{
return tlsf_cast(block_header_t*, tlsf_cast(tlsfptr_t, ptr) + size);
}
/* 将ptr指针往下挪size个字节后再往上挪block_header_overhead */
/* block_header_overhead被宏定义为(sizeof(size_t)) */
/* 这就是我觉得不直观的地方，如果使用sizeof(block_header_t *)在含义上会更准确 */
static inline __attribute__((__always_inline__)) block_header_t* block_next(const block_header_t* block)
{
block_header_t* next = offset_to_block(block_to_ptr(block),
block_size(block) - block_header_overhead);
return next;
}
当我们想链接当前block及其后一个block时，只需要设置其后一个block的prev_phys_block字段：
static inline __attribute__((__always_inline__)) block_header_t* block_link_next(block_header_t* block)
{
block_header_t* next = block_next(block);
next->prev_phys_block = block;
return next;
}
- 标记
block空闲与否
当我们标记当前block已被申请时，除了标记其自身相应比特(size字段的bit0)，还需要标记其后一个block的相应比特(size字段的bit1)：
static inline __attribute__((__always_inline__)) void block_mark_as_used(block_header_t* block)
{
block_header_t* next = block_next(block);
block_set_prev_used(next);
block_set_used(block);
}
当我们标记当前block处于空闲状态时，也要考虑其后一个block。此外，在相应接口中，还会链接当前block及其后一个block：
static inline __attribute__((__always_inline__)) void block_mark_as_free(block_header_t* block)
{
block_header_t* next = block_link_next(block);
block_set_prev_free(next);
block_set_free(block);
}
这似乎也说得通，毕竟标记空闲的接口在释放内存或分割内存时使用，彼时，肯定伴随有链接操作（prev_phys_block字段在内存块空闲时有意义）。但我个人觉得这里的封装是不太好的，至少我从block_mark_as_free这个名字里丝毫看不出含有链接两个block的意思。这也违反了一个接口只做一件事的原则。
4.1.2 管理tlsf堆的结构
每个tlsf堆都存在一个control_t用于堆管理，这是tlsf实现的核心结构，也是定义在heap_tlsf.h：
typedef struct control_t
{
/* 空节点(作为哨兵节点指示不含空闲内存块的空的空闲链表) */
block_header_t block_null;
/* 一级位图 */
unsigned int fl_bitmap;
/* 二级位图 */
unsigned int sl_bitmap[FL_INDEX_COUNT];
/* 空闲链表指针 */
block_header_t* blocks[FL_INDEX_COUNT][SL_INDEX_COUNT];
} control_t;
仍然用图来说明：
二级区间和一级区间的数量等信息定义在heap_tlsf_config.h：
#if !CONFIG_SPIRAM
#define TLSF_MAX_POOL_SIZE (SOC_DIRAM_DRAM_HIGH - SOC_DIRAM_DRAM_LOW)
#else
#define TLSF_MAX_POOL_SIZE SOC_EXTRAM_DATA_SIZE
#endif
enum tlsf_config
{
/* 二级区间的数量做log2运算的结果 */
/* 对于idf，二级区间的数量为2的5次幂，也即32个 */
/* 取这个数字是非常合理的，这意味着使用一个32bit整数即可作为一个一级区间所辖的所有二级区间的位图 */
SL_INDEX_COUNT_LOG2 = 5,
/* 申请内存时会默认进行4字节对齐的操作 */
ALIGN_SIZE_LOG2 = 2,
ALIGN_SIZE = (1 << ALIGN_SIZE_LOG2),
/* 上文说过一级区间的数量取决于硬件最大的连续内存大小 */
/* 考虑到元数据开销，最大可用内存一定是小于这个大小的 */
#if (TLSF_MAX_POOL_SIZE <= (256 * 1024))
FL_INDEX_MAX = 18, //Each pool can have up 256KB
#elif (TLSF_MAX_POOL_SIZE <= (512 * 1024))
FL_INDEX_MAX = 19, //Each pool can have up 512KB
#elif (TLSF_MAX_POOL_SIZE <= (1 * 1024 * 1024))
FL_INDEX_MAX = 20, //Each pool can have up 1MB
#elif (TLSF_MAX_POOL_SIZE <= (2 * 1024 * 1024))
FL_INDEX_MAX = 21, //Each pool can have up 2MB
#elif (TLSF_MAX_POOL_SIZE <= (4 * 1024 * 1024))
FL_INDEX_MAX = 22, //Each pool can have up 4MB
#elif (TLSF_MAX_POOL_SIZE <= (8 * 1024 * 1024))
FL_INDEX_MAX = 23, //Each pool can have up 8MB
#elif (TLSF_MAX_POOL_SIZE <= (16 * 1024 * 1024))
FL_INDEX_MAX = 24, //Each pool can have up 16MB
#elif (TLSF_MAX_POOL_SIZE <= (32 * 1024 * 1024))
FL_INDEX_MAX = 25, //Each pool can have up 32MB
#else
#error "Higher TLSF pool sizes should be added for this new config"
#endif
/* 二级区间的数量 */
SL_INDEX_COUNT = (1 << SL_INDEX_COUNT_LOG2),
/* 一级区间的起点 */
FL_INDEX_SHIFT = (SL_INDEX_COUNT_LOG2 + ALIGN_SIZE_LOG2),
/* 一级区间的数量 */
FL_INDEX_COUNT = (FL_INDEX_MAX - FL_INDEX_SHIFT + 1),
/* 细块阈值 */
SMALL_BLOCK_SIZE = (1 << FL_INDEX_SHIFT),
};
需要进一步说明的是，由于存在4字节对齐的操作，因此申请的内存的大小会被调整为4的倍数，因此二级区间划分时，若区间大小低于4字节，那就没意义了。由于二级区间的数量为SL_INDEX_COUNT ，所以，一级区间的起点应当为SL_INDEX_COUNT * 4。具体到上面的定义，一级区间的起点为128字节。
但显然我们不可能把内存块的大小都保持在不小于128字节的水平，这对于小型嵌入式系统太不合理了。对于小于128字节的内存块，不妨将其称为细块，这些细块将统一存放于第0个一级区间，对应着一级位图的bit0。自然的，[128, 255)范围的内存块位于第1个一级区间，对应一级位图的bit1。再后面的，以此类推：
4.2 优化内存块的元数据开销
上文说过，为了优化元数据开销，当前block的prev_phys_block字段被藏在了物理上前一个block的最后一个字。这样说其实是不够准确的，更准确的说：当前block的prev_phys_block字段被藏在了物理上上一个空闲block的最后一个字。之所以强调空闲，是因为只有在物理上上一个block空闲时，当前block的prev_phys_block字段才有意义。稍微有点绕，但不难解释清楚。
还是祭出这幅图：
不难看出，当内存块被申请时，就要从空闲链表中摘出来，这时，next_free以及prev_free字段所在的位置就可以给申请者使用了。再加上prev_phys_block字段位于物理上上一个block的尾部，因此一个被申请的内存块的元数据开销只有4个字节。
block的可用区域的尾部在未被申请出来时存放的是物理上下一个block的prev_phys_block字段，一旦被申请这部分内容可能会被覆盖，因此prev_phys_block字段就不再有意义了。那么，prev_phys_block字段被破坏了会存在问题嘛？当然是不存在问题的。因为当前block被申请出去之后，其物理上下一个block的prev_phys_block字段根本不会使用到，该字段只在释放block时尝试合并其物理上上一个block时才会用到。若当前block不为空闲，那么释放其物理上下一个block时进行的向上合并尝试就会及时终止，不用去访问该字段。破坏一个根本用不到的数据，自然不会有问题。但总有一天要用到该字段的，比如释放当前block，使之回归空闲状态之后，就有可能访问该字段。这也没什么，只要我们在释放时顺便恢复它就行了。唯一的问题就是，还能不能恢复？当然是可以的，显然，我们有ptr，有size，就很容易找到这个字段，找到之后将其赋值为当前block指针即可，这个恢复的操作就在上文介绍的block_link_next接口中。
4.3 一二级位图索引的计算
给定size，计算其对应的一二级位图索引（也是二维数组blocks的索引），这已经在本文的第3节介绍过了，但考虑到代码实现不是那么直观，所以这里还是专门给一节进行说明。
首先看一级位图索引的计算，也就是对log2(size)进行向下取整，实际上可以转化为计算最高位的1所在的位置（从0开始计数）：
static inline __attribute__((__always_inline__)) int tlsf_fls(unsigned int word)
{
/* 31 - 前导0的个数，即为最高位的0所在位置 */
const int bit = word ? 32 - __builtin_clz(word) : 0;
return bit - 1;
}
函数mapping_insert基本上就本文第3节中公式的直译，但还是稍微绕了一点弯。这一点弯主要在于减去2SLI时，使用的不是剑法操作，而是亦或操作，将性能考虑到极致（这很嵌入式）：
static inline __attribute__((__always_inline__)) void mapping_insert(size_t size, int* fli, int* sli)
{
int fl, sl;
if (size < SMALL_BLOCK_SIZE)
{
/* bit0表示1-127字节的细块。对于1-127字节的细块，fl为0 */
fl = 0;
/* sl为size / 4，也即： */
/* sl 0 1 2 3 ...... 31 */
/* 1-3字节 4-7字节 8-11字节 12-15字节 ...... 124-127字节 */
sl = tlsf_cast(int, size) >> 2;
}
else
{
/* 最高位的1所在位置就是向下取整log2(size) */
fl = tlsf_fls(size);
/* 用亦或来做减法的前提是：减数的bit0-bit31中为1的，被减数的相应bit也要为1 */
/* 对于size来说，其bit[fl]是为1的，那么右移fl - SL_INDEX_COUNT_LOG2后，bit[SL_INDEX_COUNT_LOG2]必然为1 */
/* 因此这里可以用亦或来做减法 */
sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2);
/* 调整一下fl，因为bit1表示128-255，是有起始大小的 */
fl -= (FL_INDEX_SHIFT - 1);
}
/* 输出要计算的fli和sli */
*fli = fl;
*sli = sl;
}
上文提到，tlsf在申请内存时，会提级申请，提级操作在mapping_search中实现。mapping_search在调用mapping_insert计算fli和sli之前，会先对size做一个增加的操作，具体来说，将size增加其所属二级区间的大小再减1（同属一个一级区间的所有二级区间有着相同的大小），使其落入未增加之前所属二级区间的下一个区间，也即提升到邻接的更大的二级区间。有一个特殊情况：size等于其所属二级区间的左边界，此时，即便增加size也无法实现提升。但这不存在问题，因为此时size所属的二级区间内的任一空闲内存块的大小都是满足要求的（>=size），换句话说，此时根本无需提升。
static inline __attribute__((__always_inline__)) void mapping_search(size_t size, int* fli, int* sli)
{
if (size >= SMALL_BLOCK_SIZE)
{
/* 增加size的操作很简单，加上当前所属二级区间的间隔再减1 */
const size_t round = (1 << (tlsf_fls(size) - SL_INDEX_COUNT_LOG2)) - 1;
size += round;
}
mapping_insert(size, fli, sli);
}
需要注意的是，这样一个提级的操作，使得我们在计算最大空闲内存块（largest_free_block）的大小时，需要将真实的最大内存块的大小向减小的方向，按其所属的二级区间的大小对齐。这是显然的，不考虑特殊情况的话，size提升之后得到size' > size，如果最大内存块的大小为size，那么也是不够的，因为提级之后，我们需要的是size'。
4.4 tlsf堆的创建与销毁
4.4.1 tlsf堆的创建
tlsf提供接口tlsf_create_with_pool用于创建堆，先梳理一下函数的调用关系：
- tlsf_create_with_pool
- tlsf_create
- control_construct
- tlsf_add_pool
- tlsf_create
然后按部就班的看一下这几个函数的实现，首先是tlsf_create_with_pool：
tlsf_t tlsf_create_with_pool(void* mem, size_t bytes)
{
/* 在mem的开头初始化control_t */
tlsf_t tlsf = tlsf_create(mem);
/* 从mem + sizeof(control_t)的地址开始，直到mem的结束，这块内存就是堆刚建立时的最初的空闲内存块 */
/* 需要把这块内存添加到堆，这块内存的大小显然就是bytes - sizeof(control_t) */
tlsf_add_pool(tlsf, (char*)mem + tlsf_size(), bytes - tlsf_size());
return tlsf;
}
tlsf_create基本上就是control_construct套了个壳，多了一个地址对齐校验：
tlsf_t tlsf_create(void* mem)
{
/* tlsf要求mem的起始地址按照ALIGN_SIZE对齐，对于IDF来说就是4字节对齐 */
if (((tlsfptr_t)mem % ALIGN_SIZE) != 0)
{
printf("tlsf_create: Memory must be aligned to %u bytes.\n",
(unsigned int)ALIGN_SIZE);
return 0;
}
/* tlsf使用control_t管理堆，这部分放在mem的开头 */
control_construct(tlsf_cast(control_t*, mem));
return tlsf_cast(tlsf_t, mem);
}
control_construct做了control_t的初始化：
static void control_construct(control_t* control)
{
int i, j;
control->block_null.next_free = &control->block_null;
control->block_null.prev_free = &control->block_null;
/* 将bitmap清0，所有链表置空（指向block_null） */
control->fl_bitmap = 0;
for (i = 0; i < FL_INDEX_COUNT; ++i)
{
control->sl_bitmap[i] = 0;
for (j = 0; j < SL_INDEX_COUNT; ++j)
{
control->blocks[i][j] = &control->block_null;
}
}
}
tlsf_add_pool主要做了两件事：
- 初始化两个
block，一个位于开头，作为最初也是最大的block，另一个位于结尾，是哨兵block - 将开头的那个block插入（头插）空闲链表
/* 除了一个pool最末尾的哨兵block，一个正常的block，最小也得有除了prev_phys_block字段之外其它block_header_t的字段 */
/* 此时这个block申请出来有8个字节可用，空闲时有prev和next指针可以串到空闲链表 */
#define block_size_min (sizeof(block_header_t) - sizeof(block_header_t*))
/* block不可能超过芯片中最大块的内存的大小 */
#define block_size_max (tlsf_cast(size_t, 1) << FL_INDEX_MAX)
......
pool_t tlsf_add_pool(tlsf_t tlsf, void* mem, size_t bytes)
{
block_header_t* block;
block_header_t* next;
/* 一个pool的开销是两个size_t */
/* 堆刚刚建立的时候，开头一个block，尾部还有一个哨兵block */
const size_t pool_overhead = tlsf_pool_overhead();
/* 开头那个block的size是传入的字节数减去pool的开销之后在向下按ALIGN_SIZE对齐 */
/* 这就是最初的整块空闲内存的大小了 */
const size_t pool_bytes = align_down(bytes - pool_overhead, ALIGN_SIZE);
......
/* block的大小须在合法范围内 */
if (pool_bytes < block_size_min || pool_bytes > block_size_max)
{
......
return 0;
}
/* 设置开头的block，并将其插入空闲链表 */
/* 这个block没有prev block，其prev block的状态设置为used */
block = offset_to_block(mem, -(tlsfptr_t)block_header_overhead);
block_set_size(block, pool_bytes);
block_set_free(block);
block_set_prev_used(block);
block_insert(tlsf_cast(control_t*, tlsf), block);
/* 哨兵block非常特别，位于pool的末尾，是整个pool中唯一一个size为0，且被标记为已使用的block */
/* 不需要（也无法）串到空闲链表 */
next = block_link_next(block);
block_set_size(next, 0);
block_set_used(next);
block_set_prev_free(next);
return mem;
}
用一幅图来描述刚刚建立的堆的样子：
4.4.2 tlsf堆的销毁
tlsf并没有正儿八经的销毁堆的函数，tlsf_remove_pool勉强算一个吧，但要求pool处于刚刚建立或整体空闲的状态，也即tlsf_add_pool之后并未申请内存，或申请了但全部释放了。听起来就不像有什么卵用的样子，实际上这个函数也确实没被调用。这里就一带而过了：
void tlsf_remove_pool(tlsf_t tlsf, pool_t pool)
{
control_t* control = tlsf_cast(control_t*, tlsf);
block_header_t* block = offset_to_block(pool, -(int)block_header_overhead);
int fl = 0, sl = 0;
/* 限制tlsf堆处于完全空闲的状态 */
tlsf_assert(block_is_free(block) && "block should be free");
tlsf_assert(!block_is_free(block_next(block)) && "next block should not be free");
tlsf_assert(block_size(block_next(block)) == 0 && "next block size should be zero");
/* 移除唯一的空闲块 */
mapping_insert(block_size(block), &fl, &sl);
remove_free_block(control, block, fl, sl);
/* 此时control_t会回到初始状态，也即刚刚执行完control_construct的状态 */
}
4.5 内存块的申请与释放
4.5.1 内存块的插入与移除
block_insert用于将一个给定的block插入到空闲链表，插入分两步，第一步是根据block的size得到第一二级索引，第二步是采用头插的方式，将block插入相应的空闲链表：
static inline __attribute__((__always_inline__)) void block_insert(control_t* control, block_header_t* block)
{
int fl, sl;
/* 根据给定block的size来确定应该插入到哪个空闲链表（属于哪个一级和二级区间） */
mapping_insert(block_size(block), &fl, &sl);
/* 将block插入fl及sl指定的链表 */
insert_free_block(control, block, fl, sl);
}
insert_free_block用于完成插入操作：
static inline __attribute__((__always_inline__)) void insert_free_block(control_t* control, block_header_t* block, int fl, int sl)
{
/* block之间会形成循环链表，将control->blocks[fl][sl]指向的节点视为头结点 */
block_header_t* current = control->blocks[fl][sl];
tlsf_assert(current && "free list cannot have a null entry");
tlsf_assert(block && "cannot insert a null entry into the free list");
/* 采用头插的方式插入新节点 */
block->next_free = current;
block->prev_free = &control->block_null;
current->prev_free = block;
/* ptr必须是ALIGN_SIZE（4字节）对齐的 */
/* 也就意味着block必须是ALIGN_SIZE（4字节）对齐的 */
tlsf_assert(block_to_ptr(block) == align_ptr(block_to_ptr(block), ALIGN_SIZE)
&& "block not aligned properly");
/* 将插入的节点作为新的头结点 */
control->blocks[fl][sl] = block;
/* 设置fl及sl对应的bitmap，表示相应的区间存在空闲的内存块（至少存在一个空闲块==>刚刚插入的那个） */
control->fl_bitmap |= (1 << fl);
control->sl_bitmap[fl] |= (1 << sl);
}
block_remove用于从空闲链表中移除一个给定的block，也是分两步操作。值得注意的是，tlsf不会检查给定的block是否存在于空闲链表，这一点需要由调用者保证：
static inline __attribute__((__always_inline__)) void block_remove(control_t* control, block_header_t* block)
{
int fl, sl;
/* 确定要移除的block在哪个链表 */
mapping_insert(block_size(block), &fl, &sl);
/* 移除block */
remove_free_block(control, block, fl, sl);
}
remove_free_block用于完成移除操作：
static inline __attribute__((__always_inline__)) void remove_free_block(control_t* control, block_header_t* block, int fl, int sl)
{
/* 循环链表移除节点 */
block_header_t* prev = block->prev_free;
block_header_t* next = block->next_free;
tlsf_assert(prev && "prev_free field can not be null");
tlsf_assert(next && "next_free field can not be null");
next->prev_free = prev;
prev->next_free = next;
if (control->blocks[fl][sl] == block)
{
/* 如果要删除的节点恰好就是头结点，那么需要将头节点调整为要删除节点的下一个节点 */
control->blocks[fl][sl] = next;
/* 如果新的头结点指向了block_null，说明fl及sl对应的区间已经没有空闲块了 */
if (next == &control->block_null)
{
/* 二级区间对应的bitmap肯定是要清除的 */
control->sl_bitmap[fl] &= ~(1 << sl);
/* 若fl对应的一级区间包含的所有二级区间全部都空了，那么一级区间对应的bitmap也要清除 */
if (!control->sl_bitmap[fl])
{
control->fl_bitmap &= ~(1 << fl);
}
}
}
}
用一幅图总结一下，内存块在空闲链表中的状态：
4.5.2 内存块的分割与合并
内存分割与合并的动机已在上文中解释了，这里介绍一下它们的实现。不妨先看合并操作，合并有两个方向：
- 合并物理上前一个
block
static inline __attribute__((__always_inline__)) block_header_t* block_merge_prev(control_t* control, block_header_t* block)
{
/* 合并前一个block的前提是前一个block要空闲 */
if (block_is_prev_free(block))
{
/* 若判断前一个block空闲的话，其实已经满足了一个隐含的条件：前一个block是存在的 */
/* 获取前一个block */
block_header_t* prev = block_prev(block);
tlsf_assert(prev && "prev physical block can't be null");
tlsf_assert(block_is_free(prev) && "prev block is not free though marked as such");
/* 此时前一个block还位于空闲链表，先将其摘出来 */
block_remove(control, prev);
/* 合并操作，分别传入物理上前一个和后一个block */
block = block_absorb(prev, block);
}
return block;
}
- 合并物理上后一个
block
static inline __attribute__((__always_inline__)) block_header_t* block_merge_next(control_t* control, block_header_t* block)
{
/* 首先保证后一个block是存在的 */
block_header_t* next = block_next(block);
tlsf_assert(next && "next physical block can't be null");
/* 其次后一个block要空闲 */
if (block_is_free(next))
{
/* 且不能是最后一个block */
/* 最后一个block必然是非空闲的，堆创建的时候就将哨兵block设置为已使用 */
/* 因此若该断言触发的话，基本可以说明堆已经被破坏了 */
tlsf_assert(!block_is_last(block) && "previous block can't be last");
/* 此时后一个block还位于空闲链表，先将其摘出来 */
block_remove(control, next);
/* 合并操作，分别传入物理上前一个和后一个block */
block = block_absorb(block, next);
}
return block;
}
两者都调用block_absorb实现功能：
static inline __attribute__((__always_inline__)) block_header_t* block_absorb(block_header_t* prev, block_header_t* block)
{
tlsf_assert(!block_is_last(prev) && "previous block can't be last");
/* 合并所带来的内存包含block的可用内存以及block的size字段(sizeof(size_t)) */
prev->size += block_size(block) + block_header_overhead;
/* 将合并后的prev及其物理上下一个block串起来 */
block_link_next(prev);
#ifdef MULTI_HEAP_POISONING_SLOW
/* 使能堆调试之后，会在空闲的内存中填充特殊字节，有关内容会在介绍堆调试的博客中进一步阐述 */
/* 这里只填充了元数据的部分，因为在释放block的时候，非元数据的部分已经填充好了 */
/* 因为要合并，所以block的元数据部分也会成为prev的可用内存，因而也要填充 */
multi_heap_internal_poison_fill_region(block, sizeof(block_header_t), true /* free */);
#endif
/* 注意，合并后的prev仍然是脱离于空闲链表的，因此可以肯定，后续还有插入操作 */
return prev;
}
再看分割操作，分割操作分为三种：
- 从
空闲块的头部分割出指定大小的内存，并将剩下的内存块归还给堆
static inline __attribute__((__always_inline__)) void block_trim_free(control_t* control, block_header_t* block, size_t size)
{
/* 既然是要分割空闲块，那么肯定要是空闲块 */
tlsf_assert(block_is_free(block) && "block must be free");
/* block本身可用的内存总不能比指定分割的大小还小吧，所以校验一下： */
/* block_size(block) >= sizeof(block_header_t) + size */
if (block_can_split(block, size))
{
/* 分割并返回分割出的block————remaining_block */
block_header_t* remaining_block = block_split(block, size);
/* 对于空闲块，必须得穿串儿 */
/* 尽管它即将不是空闲的了 */
block_link_next(block);
/* 被分割的block是空闲的 */
block_set_prev_free(remaining_block);
/* 将分割出的block插入空闲链表(归还给堆) */
block_insert(control, remaining_block);
}
}
- 从
非空闲块的头部分割出指定大小的内存，并将剩下的内存块归还给堆
static inline __attribute__((__always_inline__)) void block_trim_used(control_t* control, block_header_t* block, size_t size)
{
/* 既然是要分割非空闲块，那么肯定要是非空闲块 */
tlsf_assert(!block_is_free(block) && "block must be used");
if (block_can_split(block, size))
{
/* 分割操作 */
block_header_t* remaining_block = block_split(block, size);
/* 被分割的block是非空闲的 */
block_set_prev_used(remaining_block);
/* 进行一次向后合并 */
/* 在分割空闲块的时候并没有这个操作，因为空闲块的后面一个block不可能是空闲的 */
/* 后面介绍内存释放的时候会进一步说明这一点 */
remaining_block = block_merge_next(control, remaining_block);
/* 将分割出的block插入空闲链表(归还给堆) */
block_insert(control, remaining_block);
}
}
- 从
空闲块的头部分割出指定大小的内存，并将分割出的内存块归还给堆，返回剩下的内存块（不要对这种做法感到奇怪，看4.6节）
static inline __attribute__((__always_inline__)) block_header_t* block_trim_free_leading(control_t* control, block_header_t* block, size_t size)
{
/* 将分割成的两个block中后一个返回给调用者，前一个归还给堆 */
block_header_t* remaining_block = block;
if (block_can_split(block, size))
{
/* 分割操作 */
/* 注意这里分割的大小减去了sizeof(size_t) */
remaining_block = block_split(block, size - block_header_overhead);
/* 前一个block是作为空闲块归还给堆，因此标记空闲 */
block_set_prev_free(remaining_block);
/* 对于空闲块，必须得穿串儿 */
block_link_next(block);
/* 把前一个block归还给堆 */
block_insert(control, block);
}
return remaining_block;
}
三者都调用block_split实现功能：
static inline __attribute__((__always_inline__)) block_header_t* block_split(block_header_t* block, size_t size)
{
/* 把当前block的ptr指针向下挪size个字节，再向上挪sizeof(size_t) */
/* 更准确的应当理解为向上挪sizeof(block_header_t *) */
/* 得到的指针就指向分割后剩下的block，当然此时还未给其填充元数据，仅仅是找到了位置 */
block_header_t* remaining =
offset_to_block(block_to_ptr(block), size - block_header_overhead);
/* 剩下的block的大小是原block大小减去分割的size以及一个block的元数据开销(分割完block的数量会加一) */
const size_t remain_size = block_size(block) - (size + block_header_overhead);
tlsf_assert(block_to_ptr(remaining) == align_ptr(block_to_ptr(remaining), ALIGN_SIZE)
&& "remaining block not aligned properly");
tlsf_assert(block_size(block) == remain_size + size + block_header_overhead);
/* 设置剩下的block的元数据 */
block_set_size(remaining, remain_size);
tlsf_assert(block_size(remaining) >= block_size_min && "block split with invalid size");
/* 设置分割出的block的元数据 */
block_set_size(block, size);
/* 剩下的block是刚分割得到的，热乎着呢，肯定没被申请 */
/* 因此标记为空闲，并穿串儿 */
block_mark_as_free(remaining);
return remaining;
}
还是用图来示意，一图胜千言（尽管画图的人很累-_-!!）：
4.5.3 内存块的申请
先看几个操作铺垫一下：
- 计算最低位的1所在的位置（从0开始计）
static inline __attribute__((__always_inline__)) int tlsf_ffs(unsigned int word)
{
/* 先把除最低位的1之外的位都变为0 */
const unsigned int reverse = word & (~word + 1);
/* 再使用31 - 前导0的个数 */
const int bit = 32 - __builtin_clz(reverse);
return bit - 1;
}
- 调整申请的大小（
tlsf堆会对申请的大小进行向上4字节对齐）
static inline __attribute__((__always_inline__)) size_t adjust_request_size(size_t size, size_t align)
{
size_t adjust = 0;
if (size)
{
/* 向上对齐 */
const size_t aligned = align_up(size, align);
/* 对齐后的大小不能超过block_size_max，否则会造成对sl_bitmap字段的访问越界 */
if (aligned < block_size_max)
{
/* 申请内存也不能太小 */
/* block_size_min有12个字节，是包含元数据的，因此我觉得最小申请大小设置为8字节比较合适，也即: */
/* adjust = tlsf_max(aligned, block_size_min - block_header_overhead); */
adjust = tlsf_max(aligned, block_size_min);
}
}
return adjust;
}
- 查找可用的内存块
static inline __attribute__((__always_inline__)) block_header_t* block_locate_free(control_t* control, size_t size)
{
int fl = 0, sl = 0;
block_header_t* block = 0;
if (size)
{
/* 按照提级的方式根据size计算合适的一二级索引 */
mapping_search(size, &fl, &sl);
/* 一级索引值过大，说明申请的size已经超过了系统 */
if (fl < FL_INDEX_COUNT)
{
block = search_suitable_block(control, &fl, &sl);
}
}
if (block)
{
tlsf_assert(block_size(block) >= size);
/* 将找到的大小足够的内存块从空闲链表摘除 */
remove_free_block(control, block, fl, sl);
}
return block;
}
再看search_suitable_block做什么：
static inline __attribute__((__always_inline__)) block_header_t* search_suitable_block(control_t* control, int* fli, int* sli)
{
int fl = *fli;
int sl = *sli;
/* 从二级位图中将二级索引对应的bit及更高位的bit都取出来 */
unsigned int sl_map = control->sl_bitmap[fl] & (~0U << sl);
/* 如果结果为0，就说明当前整个一级区间已经没有大小足够的空闲内存块了 */
if (!sl_map)
{
/* 因此要尝试往更大的一级区间查找，也即： */
/* 取出一级索引对应bit更高位的bit */
const unsigned int fl_map = control->fl_bitmap & (~0U << (fl + 1));
/* 如果为0，说明找不到大小足够的空闲内存块了 */
if (!fl_map)
{
return 0;
}
/* 否则就从更高位的bit中取出最低的那个不为0的bit */
fl = tlsf_ffs(fl_map);
/* 该bit所在位置就是新的一级索引 */
*fli = fl;
/* 取出新的一级区间对应的二级位图 */
sl_map = control->sl_bitmap[fl];
}
tlsf_assert(sl_map && "internal error - second level bitmap is null");
/* 从新的二级位图中找到最低位的bit所在位置作为新的二级索引 */
/* 显然，sl_map肯定是非0的，所以新的二级索引肯定能找到 */
sl = tlsf_ffs(sl_map);
*sli = sl;
/* 于是，终于找到了"最合适"的空闲内存块 */
return control->blocks[fl][sl];
}
- 完成申请后尝试分割
static inline __attribute__((__always_inline__)) void* block_prepare_used(control_t* control, block_header_t* block, size_t size)
{
void* p = 0;
if (block)
{
tlsf_assert(size && "size must be non-zero");
/* 尝试进行分割 */
block_trim_free(control, block, size);
/* 分割得到的内存即将返回给调用者使用，因此标记为used */
block_mark_as_used(block);
/* 返回ptr指针，调用者是看不到元数据的 */
p = block_to_ptr(block);
}
return p;
}
有了上述铺垫之后，再看内存申请函数tlsf_malloc就水到渠成了：
void* tlsf_malloc(tlsf_t tlsf, size_t size)
{
control_t* control = tlsf_cast(control_t*, tlsf);
/* 向上4字节对齐 */
size_t adjust = adjust_request_size(size, ALIGN_SIZE);
/* 查找最合适的空闲内存块 */
block_header_t* block = block_locate_free(control, adjust);
/* 尝试分割内存块并向调用者返回ptr指针 */
return block_prepare_used(control, block, adjust);
}
上层存在realloc接口，自然tlsf堆也提供了tlsf_realloc：
void* tlsf_realloc(tlsf_t tlsf, void* ptr, size_t size)
{
control_t* control = tlsf_cast(control_t*, tlsf);
void* p = 0;
/* realloc的size为0，则行为是释放内存 */
if (ptr && size == 0)
{
tlsf_free(tlsf, ptr);
}
/* realloc的指针为0，则行为是申请内存 */
else if (!ptr)
{
p = tlsf_malloc(tlsf, size);
}
/* 剩下的一种最常见的情况就是，在已申请的内存基础上调整大小 */
else
{
/* 获取当前block及其物理上相邻的下一个block */
block_header_t* block = block_from_ptr(ptr);
block_header_t* next = block_next(block);
const size_t cursize = block_size(block);
/* 计算当前block及其物理上相邻的下一个block一共能提供多少内存 */
const size_t combined = cursize + block_size(next) + block_header_overhead;
/* 将realloc的大小向上4字节对齐 */
const size_t adjust = adjust_request_size(size, ALIGN_SIZE);
/* 只能对used的内存块进行realloc */
tlsf_assert(!block_is_free(block) && "block already marked as free");
/* 重新申请内存的时间开销肯定是最大的，但有以下情况发生时不得不重新申请: */
/* 所需的大小大于原大小 */
/* 且下一个block非空闲(也就不可能合并)，或下一个block空闲，能合并，但合并之后大小还是不够 */
if (adjust > cursize && (!block_is_free(next) || adjust > combined))
{
/* 此时只能重新申请 */
p = tlsf_malloc(tlsf, size);
if (p)
{
const size_t minsize = tlsf_min(cursize, size);
/* 将原内存的内容拷贝到新申请的内存 */
memcpy(p, ptr, minsize);
/* 释放原内存 */
tlsf_free(tlsf, ptr);
}
}
else
{
/* 执行到这里说明，realloc的大小小于原大小，或大于原大小，但当前block于下一个block可用合并且合并后大小是够用的 */
/* 大于原大小的情况 */
if (adjust > cursize)
{
/* 与下一个block合并 */
block_merge_next(control, block);
/* 将合并后的block标记为used(本来就是要返回给调用者使用的) */
block_mark_as_used(block);
}
/* 尝试分割，减少内部碎片 */
block_trim_used(control, block, adjust);
p = ptr;
}
}
return p;
}
4.5.4 内存块的释放
内存释放的接口tlsf_free就很好理解了，内多少内容：
void tlsf_free(tlsf_t tlsf, void* ptr)
{
/* 不能释放空指针 */
if (ptr)
{
control_t* control = tlsf_cast(control_t*, tlsf);
block_header_t* block = block_from_ptr(ptr);
/* 要释放的内存肯定得是used */
tlsf_assert(!block_is_free(block) && "block already marked as free");
/* 将该block标记为空闲 */
block_mark_as_free(block);
/* 向前合并 */
block = block_merge_prev(control, block);
/* 向后合并 */
block = block_merge_next(control, block);
/* 将释放的内存块归还给堆 */
block_insert(control, block);
}
}
值得说明的是：
在内存释放时，会尝试合并block：block_merge_prev、block_merge_next。往前、后一个block各尝试一次合并操作，而不是一直遍历前面和后面的节点，从而使得释放也是O(1)的复杂度。那么这样的合并操作足够吗，会不会出现相邻block本可以合并但没有合并的情况？当然是不会出现的。这不难想明白，如果每次释放都执行上述的合并逻辑，那么就不可能出现合并不彻底的情况。举例来说，a b c三个相邻的block，释放c的时候，b若处于free状态，那么b、c会合并，此时a不可能是free的，因为如果a是free的，那么释放b的时候就会将它合并。
4.6 内存块的地址对齐申请
地址对齐这种申请方式相对少见一些，但也有些应用确实存在这样的要求，比如申请cacheline对齐的内存，存放关键数据，从而优化性能。对此，提供了tlsf_memalign_offs实现地址对齐申请。先说明一下这个函数的几个参数：
- tlsf：指向tlsf堆(也即指向
control_t) - align：地址对齐参数
- size：要申请的内存的大小
- data_offset：偏移参数，需要注意的是，该参数需要是
4字节的整数倍，可以为0。不管传入的值是否满足对齐要求，函数总会进行向上对齐操作。其含义具体是，返回给用户的ptr指针指向可用内存的起始，则((unsigned int)ptr + data_offset_aligned) % align == 0，为了方便后面的叙述，不妨把该条件称为偏移对齐条件。
在分析源码之前，还得做一些铺垫。若是我们自己设计实现这个函数，应该怎么做呢？不难想到的是，我们肯定要申请比参数指定的size更大的内存，因为很难保证偏移对齐条件一申请就满足，不太可能这么巧合。只有申请足够大的内存，才能在不满足偏移对齐条件的时候，通过调整返回给用户的地址来达成条件。这里所谓的调整，实质上就是将最初返回给用户的地址向后挪一挪。
向后挪一挪必然导致前面空出一块，这空出来的内存应该怎么处理，是任其浪费还是归还给堆？答案是只能归还给堆，理由如下：
- 避免内存浪费（当然，这不能解释"只能"）
- 还有一个刚性的理由，free的时候并没有对地址对齐申请的情况做特殊处理，仍然把按照地址对齐申请的内存块按一般的内存块归还，因此它必须是一般的内存块，不允许前面还有一个gap。否则tlsf对元数据的处理就会出错。
既然要归还给堆，那么空出来的内存的大小就是有要求的，比如只空出4字节是没法归还给堆的，因为最小的block也不止4字节。源码中要求这个空出来的大小不小于sizeof(block_header_t)，这个大小就足够进行归还操作了。
现在还剩下一个问题，解决了，我们的思路就通了。这个问题就是，申请足够大的内存，到底是多大。这个问题用文字解释很麻烦，还是得上图（看到这里的同学，我画了这么多图，你们不点个赞心里过的去嘛？）。当data_offset_aligned < align的时候，一般最初申请出的内存，大体可以归为以下两种位置分布：
再看data_offset_aligned > align的时候：
不难看出来，有这么个结论：
现在是时候过一遍源码了：
void* tlsf_memalign_offs(tlsf_t tlsf, size_t align, size_t size, size_t data_offset)
{
control_t* control = tlsf_cast(control_t*, tlsf);
const size_t adjust = adjust_request_size(size, ALIGN_SIZE);
const size_t off_adjust = align_up(data_offset, ALIGN_SIZE);
/* 除了便宜，还得留足空出来的内存，以便归还给堆 */
const size_t gap_minimum = sizeof(block_header_t) + off_adjust;
/* adjust + align + sizeof(block_header_t)，这样最初申请的内存的大小就够了 */
const size_t size_with_gap = adjust_request_size(adjust + align + gap_minimum - off_adjust, align);
/* 如果对齐参数小于4字节对齐，那么什么都不用做，申请出来的内存就一定满足了偏移对齐条件(也无需多申请内存) */
const size_t aligned_size = (adjust && align > ALIGN_SIZE) ? size_with_gap : adjust;
/* 最初申请的内存 */
block_header_t* block = block_locate_free(control, aligned_size);
/* 等效于tlsf_assert(sizeof(block_header_t *) == sizeof(size_t)) */
tlsf_assert(sizeof(block_header_t) == block_size_min + block_header_overhead);
if (block)
{
/* 这部分的代码计算两个量 */
/* 1. aligned : 偏移对齐的对齐点 */
/* 2. gap : 偏移对齐的对齐点与最初申请出的内存的ptr指针的间隔 */
/* 结合下文的图不难看明白逻辑，不适合用文字解释 */
void* ptr = block_to_ptr(block);
void* aligned = align_ptr(ptr, align);
size_t gap = tlsf_cast(size_t,
tlsf_cast(tlsfptr_t, aligned) - tlsf_cast(tlsfptr_t, ptr));
if ((gap && gap < gap_minimum) || (!gap && off_adjust && align > ALIGN_SIZE))
{
const size_t gap_remain = gap_minimum - gap;
const size_t offset = tlsf_max(gap_remain, align);
const void* next_aligned = tlsf_cast(void*,
tlsf_cast(tlsfptr_t, aligned) + offset);
aligned = align_ptr(next_aligned, align);
gap = tlsf_cast(size_t,
tlsf_cast(tlsfptr_t, aligned) - tlsf_cast(tlsfptr_t, ptr));
}
/* 如果需要挪一挪 */
if (gap)
{
tlsf_assert(gap >= gap_minimum && "gap size too small");
/* 则将返回给用户的地址完后挪一挪，并把挪动带来的前面的空白归还给堆 */
block = block_trim_free_leading(control, block, gap - off_adjust);
}
}
/* 尾部没准也有可以分割的内存 */
return block_prepare_used(control, block, adjust);
}
最后再补充说明一下，最终，局部变量gap表示的含义如下：
tlsf_memalign在tlsf_memalign_offs的基础上做了一个简单的封装，也就是设置data_offset_aligned为0：
void* tlsf_memalign(tlsf_t tlsf, size_t align, size_t size)
{
return tlsf_memalign_offs(tlsf, align, size, 0);
}
4.7 tlsf堆的完整性检测
所谓堆的完整性，指的是管理堆的元数据是否遭到破坏。通常发生堆内存溢出时会导致堆的完整性被破坏。对此，tlsf提供了一些堆完整性检测的接口：
tlsf_check从control_t出发，验证其正确性，并进一步遍历所有空闲链表，验证其中每个空闲块的元数据的正确性：
int tlsf_check(tlsf_t tlsf)
{
int i, j;
control_t* control = tlsf_cast(control_t*, tlsf);
int status = 0;
/* 遍历一级区间 */
for (i = 0; i < FL_INDEX_COUNT; ++i)
{
/* 遍历二级区间 */
for (j = 0; j < SL_INDEX_COUNT; ++j)
{
/* 获取一级区间对应的位图 */
const int fl_map = control->fl_bitmap & (1 << i);
/* 获取当前二级区间对应的位图 */
const int sl_list = control->sl_bitmap[i];
const int sl_map = sl_list & (1 << j);
/* 获取当前二级区间对应的空闲链表 */
const block_header_t* block = control->blocks[i][j];
/* 一级区间都显示为空（没有空闲块），那么当前二级区间肯定也要为空 */
if (!fl_map)
{
tlsf_insist(!sl_map && "second-level map must be null");
}
/* 如果当前二级区间为空，那么其对应的空闲链表也要为空（指向block_null） */
if (!sl_map)
{
tlsf_insist(block == &control->block_null && "block list must be null");
continue;
}
/* 能走到这里，说明当前二级区间不为空 */
tlsf_insist(sl_list && "no free blocks in second-level map");
tlsf_insist(block != &control->block_null && "block should not be null");
/* 遍历当前二级区间对应的空闲链表 */
while (block != &control->block_null)
{
int fli, sli;
/* 既然处于空闲链表，那么当前块肯定是空闲的 */
tlsf_insist(block_is_free(block) && "block should be free");
/* 因为释放时有合并的逻辑，因此正常情况下不可能出现相邻的空闲块 */
tlsf_insist(!block_is_prev_free(block) && "blocks should have coalesced");
tlsf_insist(!block_is_free(block_next(block)) && "blocks should have coalesced");
/* 当前block空闲，则它的下一个block对它的标记也应当是空闲 */
tlsf_insist(block_is_prev_free(block_next(block)) && "block should be free");
/* block的size要在合法范围内 */
tlsf_insist(block_size(block) >= block_size_min && "block not minimum size");
/* 根据当前空闲块的大小，计算一级索引和二级索引 */
mapping_insert(block_size(block), &fli, &sli);
/* 索引值必须和当前遍历的一、二级区间相应 */
tlsf_insist(fli == i && sli == j && "block size indexed in wrong list");
block = block->next_free;
}
}
}
return status;
}
tlsf_check_pool从头开始遍历所有内存块（包括空闲和非空闲），并调用integrity_walker检查所有block的完整性：
int tlsf_check_pool(pool_t pool)
{
integrity_t integ = { 0, 0 };
/* 遍历pool中的所有block，并调用integrity_walker去校验每一个block */
tlsf_walk_pool(pool, integrity_walker, &integ);
return integ.status;
}
void tlsf_walk_pool(pool_t pool, tlsf_walker walker, void* user)
{
tlsf_walker pool_walker = walker ? walker : default_walker;
/* 获得首个block */
block_header_t* block =
offset_to_block(pool, -(int)block_header_overhead);
while (block && !block_is_last(block))
{
pool_walker(
block_to_ptr(block),
block_size(block),
!block_is_free(block),
user);
/* 遍历完当前block后，遍历下一个block */
block = block_next(block);
}
}
static void integrity_walker(void* ptr, size_t size, int used, void* user)
{
block_header_t* block = block_from_ptr(ptr);
integrity_t* integ = tlsf_cast(integrity_t*, user);
const int this_prev_status = block_is_prev_free(block) ? 1 : 0;
const int this_status = block_is_free(block) ? 1 : 0;
const size_t this_block_size = block_size(block);
int status = 0;
(void)used;
/* 相邻block之前的空闲标记要对的上 */
tlsf_insist(integ->prev_status == this_prev_status && "prev status incorrect");
/* block的大小要对的上 */
tlsf_insist(size == this_block_size && "block size incorrect");
integ->prev_status = this_status;
/* 如果堆未遭到破坏，那么最终的integ->status为0，也即tlsf_check_pool返回0 */
integ->status += status;
}
上述堆完整性检测接口也是更上层接口的基础，更多关于堆调试的内容会在后续博客介绍。
参考
[1] esp32 heap 内存管理简析
[2] esp-idf
[3] GitHub - mattconte/tlsf: Two-Level Segregated Fit memory allocator implementation.
[4] LiteOS内存管理：TLSF算法
[5] TLSF算法分析
