1
2
- unsorted bin：是bins的一个缓冲区，bins数组下标为1的即是unstored bin。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会进入unsorted bin上。当用户malloc的时候，先会到unsorted bin上查找是否有合适的bin，如果没有合适的bin，ptmalloc会将unsorted bin上的chunk放入bins上，然后到bins上查找合适的空闲chunk。
- small bins：小于512字节（64位机器1024字节）的chunk被称为small chunk，而保存small chunks的bin被称为small bin。数组从2开始编号到63，前62个bin为small bins，small bin每个bin之间相差8个字节（64位16字节），同一个small bin中的chunk具有相同大小。起始bin大小为16字节（64位系统32）。
- large bins：大于等于512字节（64位机器1024字节）的chunk被称为large chunk，而保存large chunks的bin被称为large bin。位于small bins后面，数组编号从64开始，后64个bin为large bins。同一个bin上的chunk，可以大小不一定相同。large bins都是通过等差步长的方式进行拆分。（以32位系统为例，前32个bin步长64，后16个bin步长512，后8个步长4096，后四个32768，后2个262144）（编号63到64的步长）。起始bin大小为512字节（64位系统1024）。
unsorted bin：
每次取最后的一个unsorted chunk。
-
如果unsorted chunk满足以下四个条件，它就会被切割为一块满足申请大小的chunk和另一块剩下的chunk，前者返回给程序，后者重新回到unsorted bin。
-
申请大小属于small bin范围
-
unosrted bin中只有该chunk
-
这个chunk同样也是last remainder chunk
-
切割之后的大小依然可以作为一个chunk
否则，从unsorted bin中删除unsorted chunk。
-
若unsorted chunk恰好和申请大小相同，则直接返回这个chunk
-
若unsorted chunk属于small bin范围，插入到相应small bin
-
若unsorted chunk属于large bin范围，则跳转到3。
此时unsorted chunk属于large bin范围。
-
若对应large bin为空，直接插入unsorted chunk，其fd_nextsize与bk_nextsize指向自身。
-
否则，跳转到4。
到这一步，我们需按大小降序插入对应largebin。
-
若对应large bin最后一个chunk大于unsorted chunk，则插入到最后
-
否则，从对应large bin第一个chunk开始，沿fd_nextsize（即变小）方向遍历，直到找到一个chunk fwd，其大小小于等于unsorted chunk的大小
-
若fwd大小等于unsorted chunk大小，则插入到fwd后面
-
否则，插入到fwd前面直到找到满足要求的unsorted chunk，或无法找到，去top chunk切割为止。
small bins
小于 0x200（0x400）B 的 chunk 叫做 small chunk，而 small bins 可以存放的就是这些 small chunks。chunk 大小同样是从 16B 开始每次+8B。
small bins 是 62 个双向循环链表，并且是 FIFO 的，这点和 fast bins 相反。同样相反的是相邻的空闲 chunk 会被合并。
chunk大小：0x10-0x1f0B（0x20-0x3f0），相邻bin存放的大小相差0x8（0x10）B。
释放非fast chunk时，按以下步骤执行：
-
若前一个相邻chunk空闲，则合并，触发对前一个相邻chunk的unlink操作
-
若下一个相邻chunk是top chunk，则合并并结束；否则继续执行3
-
若下一个相邻chunk空闲，则合并，触发对下一个相邻chunk的unlink操作；否则，设置下一个相邻chunk的PREV_INUSE为0
-
将现在的chunk插入unsorted bin。
-
若size超过了FASTBIN_CONSOLIDATION_THRESHOLD，则尽可能地合并fastbin中的chunk，放入unsorted bin。若top chunk大小超过了mp_.trim_threshold，则归还部分内存给OS。
large bins
大于等于 0x200（0x400）B 的 chunk 叫做 large chunk，而 large bins 可以存放的就是这些 large chunks。
large bins 是 63 个双向循环链表，插入和删除可以发生在任意位置，相邻空闲 chunk 也会被合并。chunk 大小就比较复杂了：
-
前 32 个bins：从 0x200B 开始每次+0x40B
-
接下来的 16个bins：每次+0x200B
-
接下来的 8 个bins：每次+0x1000B
-
接下来的 4 个bins：每次+0x8000B
-
接下来的 2 个bins：每次+0x40000B
-
最后的 1 个bin：只有一个 chunk，大小和 large bins 剩余的大小相同
注意同一个 bin 中的 chunks 不是相同大小的，按大小降序排列。这和上面的几种 bins 都不一样。而在取出chunk时，也遵循best fit原则，取出满足大小的最小chunk。
原文始发于微信公众号（由由学习吧）：bins
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论