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

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的次幂进行第一级的划分，以上图为例，第一级区间的范围分别是（起点不是固定的）：

• [2⁴, 2⁵ – 1)
• [2⁵, 2⁶ – 1)
• [2⁶, 2⁷ – 1)
• …

不难看出，第一级区间的个数取决于要管理的内存块的大小，第一级区间中最大的那个区间不可能超过实际的最大内存块的大小。在第一级区间划分的基础上进行均匀分割，得到第二级区间。若将第一级区间均匀划分为2^SLI份（也即任一一级区间下第二级区间的个数为2^SLI，SLI在实现的时候是固定不变的，是一个常量），且使用2^f表示第一级区间大小范围的左边界（为方便叙述，对于一个区间的边界，本文采用左小右大），则第二级区间的区间大小为：

• 2^f / 2^SLI
  note：其中，左边界2^f表示此时第一级区间的区间范围为[2^f, 2^f+1 – 1)

不妨将第二级区间的区间大小记为N，则第二级区间的范围分别是：

• [2^f, 2^f + N)
• [2^f + N, 2^f + 2N)
• [2^f + 2N, 2^f + 3N)
• …

每个二级区间都存在一个链表（可能是空链表），这个链表上串着所有大小处于这个二级区间的空闲内存块。此外，对于一二级区间，使用位图来标识其中是否存在空闲内存块，这将使得我们可以快速查找可用区间。

不难注意到，不管是划分一级区间还是划分二级区间，都使用2的次幂，这当然是刻意为之，可以在给定内存大小，计算其应当属于哪个一二级区间时提供方便。具体的说，给定大小size，则其所属一二级区间的索引如下计算：

因为2的幂次的使用，上式可以使用位运算快速得出。至于为什么是这样算，一级索引f的计算很好理解，s的计算可以参考tlsf设计示意图中的红色标注。size减去2^f得到size在所属一级区间中的偏移，用这个偏移除以二级区间的大小即可得到二级索引。得到f及s之后，通过位图可以快速判断出相应的二级区间是否存在空闲内存块。

为了实现申请内存O(1)的复杂度，tlsf使用提级申请的方式。具体的说，若申请的size落入二级区间为：

• [2^f, 2^f + N)

则我们不会在该区间遍历链表，而是提级到下一个区间去申请：

• [2^f + N, 2^f + 2N)

显然提级之后的区间中任一内存块都符合内存大小的要求，这就避免了链表遍历，实现了O(1)。这样做当然有代价——会造成内部碎片。虽然由于两级划分的机制，使得内部碎片的大小控制在2N以内。但如果size足够大，也即2^f足够大，那么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节介绍过了，但考虑到代码实现不是那么直观，所以这里还是专门给一节进行说明。

首先看一级位图索引的计算，也就是对log₂(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节中公式的直译，但还是稍微绕了一点弯。这一点弯主要在于减去2^SLI时，使用的不是剑法操作，而是亦或操作，将性能考虑到极致（这很嵌入式）：

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_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主要做了两件事：

1. 初始化两个block，一个位于开头，作为最初也是最大的block，另一个位于结尾，是哨兵block
2. 将开头的那个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 内存块的分割与合并

内存分割与合并的动机已在上文中解释了，这里介绍一下它们的实现。不妨先看合并操作，合并有两个方向：

1. 合并物理上前一个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;
}

2. 合并物理上后一个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;
}

再看分割操作，分割操作分为三种：

1. 从空闲块的头部分割出指定大小的内存，并将剩下的内存块归还给堆

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);
	}
}

2. 从非空闲块的头部分割出指定大小的内存，并将剩下的内存块归还给堆

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);
	}
}

3. 从空闲块的头部分割出指定大小的内存，并将分割出的内存块归还给堆，返回剩下的内存块（不要对这种做法感到奇怪，看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. 计算最低位的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;
}

2. 调整申请的大小（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;
}

3. 查找可用的内存块

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];
}

4. 完成申请后尝试分割

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实现地址对齐申请。先说明一下这个函数的几个参数：

1. tlsf：指向tlsf堆(也即指向control_t)
2. align：地址对齐参数
3. size：要申请的内存的大小
4. data_offset：偏移参数，需要注意的是，该参数需要是4字节的整数倍，可以为0。不管传入的值是否满足对齐要求，函数总会进行向上对齐操作。其含义具体是，返回给用户的ptr指针指向可用内存的起始，则((unsigned int)ptr + data_offset_aligned) % align == 0，为了方便后面的叙述，不妨把该条件称为偏移对齐条件。

在分析源码之前，还得做一些铺垫。若是我们自己设计实现这个函数，应该怎么做呢？不难想到的是，我们肯定要申请比参数指定的size更大的内存，因为很难保证偏移对齐条件一申请就满足，不太可能这么巧合。只有申请足够大的内存，才能在不满足偏移对齐条件的时候，通过调整返回给用户的地址来达成条件。这里所谓的调整，实质上就是将最初返回给用户的地址向后挪一挪。

向后挪一挪必然导致前面空出一块，这空出来的内存应该怎么处理，是任其浪费还是归还给堆？答案是只能归还给堆，理由如下：

1. 避免内存浪费（当然，这不能解释”只能”）
2. 还有一个刚性的理由，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提供了一些堆完整性检测的接口：

1. 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;
}

2. 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算法分析