TLSF内存分配器记录[通俗易懂]

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

论文：《TLSF: a New Dynamic Memory Allocator for Real-Time Systems》

这也是Unity底层使用的内存分配器。

我直接从论文中间部分开始看。

first level存的是每个内存分配大小，从2的四次方到2的31次方。

而对应每个大小，又指向一个二级列表，里面被分成4级，每一级的范围认为是同一类。

1表示空闲，所以只有2的六次方和2的15次方块是空闲的。再看它指向的二级列表。

只有2的六次方+16到2的6次方+32的这个块是空闲的。

其他也一样，就不赘述了。

这里挺重要的，为了加快合并，每个块被释放的时候，会往前1个word大小，找到前一块的头，

然后看他是否空闲，如果空闲，就合并。这里我们可以把块分配在块的开头来简化实现。

所以每个free block应该存在两个链表中。一个是分离的，包含同类大小的空闲块。还有一个是连续的物理的内存块列表。

 这里要注意，一个被使用的块，它的块头数据更小。

因为分配的大小最小是4，所以有多出两个bit，一个表示是否空闲，一个表示块是否是池的最后一个。

 460，2的八次方是256，460-256=204

204/16 = 12.75

接下来看实际实现：

 申请的大小里面，还要去掉pool_t的结构体大小。同时也要空余出2个size_t的大小。

 其中一个是第一块的freeblock的size，第二个是哨兵的size。注意，哨兵只有一个size字段。

 构造的时候，清空fl和sl的bitmap。同时把blocks里面的全都指向block_null这个结构体。

 然后，直接从起始点偏移pool_t，这里再往前block_header_overhead字节，是因为prev_phys_block字段是藏在上一块的末尾。

然后设置这个block的大小。然后要标记block为free，标记上一块为used。

 插入这个空闲块。

 如果块的大小小于256，也就是8 *32， 那么全都分配到0里面，否则就按照正常的方式计算，减去偏移量即可。

 这里把block插入到对应的list里面，同时更新blocks,fl,sl bitmaps.

 这是物理位置上拿到下一块的头部。

下一块size为0，被使用，上一块free标记。

 这个gap_minimu意义未知，后面再看。

现在要申请一个aligned_size大小的内存。

 这里搜索对应的fl sl的时候，需要保证申请块的大小一定大于size。所以有个round的过程。

 首先直接看对应的fl sl里面是否有空闲块，没有的话就去找更大的区间里面，是否还有free的，有的话就找到这个fl，

 这个函数是用来找最高位是多少，例如1024是2的10次方，那么就是11位。

 所以ffs是用来找最低的有效位，而fls是最高的有效位。

 从list里面移除。同时要更新blocks，

 ptr指向了block里面的具体数据。

align_ptr会把其实数据地址校正成对齐的地址。

gap意义还是不明，先继续看。

 首先拿到block的数据地址，然后便宜size，减去overhead拿到剩余的head地址。

剩余的size就是这个block的大小，减去size,再去除一个overhead的大小。

设置剩余块的size。

 这里的时候，这个block依然是free的，所以可以设置link_next

这样就成功从1M空间分配了72字节的内存。同时也保留了一个free block

 因为内存池设定对齐是8字节，如果你传入的对齐是16，那么未来就可能出现产生8字节gap的情况。

 如果我们不管他，是有问题的。因为我们的内存是连续的，对于上一块，他是被使用的，那么他会通过字节偏移访问下一块，但这样就会出错。因为中间多了8个字节。所以思路是，多申请一部分内存，把8字节扩展到足够放入一个空闲块。那么这个空闲块放入到free list里面。然后从后面的块去重新申请对齐情况下的内存即可。

但代码写的比较费解。

我们从后面反推，首先我们知道需要申请一块更大的内存，但要大多少我们后面算。

假定gap是8，那么我们先要申请一个head大小的，也就是32个字节。

因为需要16字节对齐，所以依然需要扩增到40.

也就是说，我们需要一块，size_t_32字节的数据。

 这个判断，我个人觉得有问题。

 这里的size只有32，所以，从ptr开始，偏移24个字节。因为8个字节是内部的，所以其实是32个字节，然后因为前面head 8个字节，所以总共是40个字节。

因为要多40个字节，那么我们一开始分配的大小也需要加上至少40个字节。不然到时候remain就不够了。

这里用的是这么多，56个字节，多了一点，感觉问题不大。