ptmalloc堆内存管理机制（主要讨论Linux x86下32位系统）

3. bin（chunk容器）

ptmalloc将相似大小的 chunk 用双向链表链接起来，这样的一个链表被称为一个 bin。 Ptmalloc 一共维护了 128 个 bin，并使用一个数组来存储这些 bin，这个数组被成为bin数组。

bin数组结构如下：

在32位平台下，bin[0] 和 bin[127] 是不存在的，因为最小的 chunk 为 16B， small bin 一共 62 个， large bin 一共 63 个，算上 bin[1] 加起来一共 128 个 bin。

其中 small bin 可以看成是公差为8的等差数列，其相邻两个 bin 的 chunk 的大小相差8B，如上图所示。large bin 的每个 bin 中的 chunk 大小不是一个固定的等差数列，而是分成六组，每组 bin 是一个固定公差的等差数列，每组的 bin 数量依次为 32、 16、 8、 4、 2、 1，公差依次为 64B、 512B、4096B、32768B、 262144B 等。
正是基于 bin 数组的这种关系，当用户给出一个需要申请的空间大小，ptmalloc 会很容易的确定改大小空间在哪个 bin 里。


fast bin：

• 不大于 max_fast（默认值为 64B）的 chunk 被释放后，首先会被放到 fast bin 中， fast bin 中的 chunk 并不改变它的使用标志 P。 这样也就无法将它们合并， 当需要给用户分配的 chunk 小于或等于 max_fast 时， ptmalloc 首先会在 fast bin 中查找相应的空闲块，然后才会去查找 bin 中的空闲 chunk。在某个特定的时候（在内存释放合并 top chunk 时，如果合并后的 chunk 的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认64KB）， 会触发进行 fast bins 的合并操作），ptmalloc会遍历 fast bin中的 chunk，18将相邻的空闲 chunk 进行合并， 并将合并后的 chunk 加入 unsorted bin 中，然后再将 usorted bin 里的 chunk 加入 bins 中。