大家好，又见面了，我是你们的朋友全栈君。
论文：《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个字节，多了一点，感觉问题不大。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/148701.html原文链接：https://javaforall.cn
