前言：让我们继续学习新的概念——bin，学习资料来自庄明强老师的《Glibc 内存管理》，博客的大部分内容来自这本书。

0X00 bin 的介绍

简单来说：bin 就是空闲 chunk 的容器

用户 free 掉的内存并不是都会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区中空闲的 chunk，当用户进行下一次分配请求时，ptmalloc 会在空闲的 chunk 中选择一个合适的分配给他，这样就避免了频繁地系统调用

ptmalloc 把大小相似的 chunk，用双向链表连接起来，这样就形成了一个 bin。ptmalloc 一共维护了 128 个这样的 bin，并使用数组来存储这些 bin 如下：

0X01 ptmalloc bin 分类

再回到这张图，数组中的第一个 bin 是 unsorted bin，数组中从第 2 个到第 64 个 bin 是 small bin，它的 chunk size 依次递增 8bytes，每个 small bin 中的 chunk 大小相同。small bin 是一个双向链表。双向链表不是循环链表，它是有顺序的。在相同大小 chunk 的 bin 中 的排序是按照「最近使用」的顺序，也就是说，排在后面的最容易被选中，刚被释放的放在前面。

small bin 后面是 large bin

largin bin 中 chunk 的大小不是固定的，而是有一个范围。其中的顺序是按大小排序的，越大的放在越下面，如果大小相同，按照「最近使用」的顺序

当空闲的 chunk 被连接到 bin 的时候，ptmalloc 会把表示该 chunk 是否正在使用的标志 p 设置为 0。（注意！这个标志实际处在下一个 chunk 中）。同时，ptmalloc 还会检查它前后（物理前后）的 chunk 是否为空，如果为空，ptmalloc 会把这些 chunk 合并成一个大的 chunk，然后把合并后的 chunk 放入 unsorted bin 中。但是对于较小的 chunk，ptmalloc 会把它放入 fast bins 中。

• Fast Bins

用户很有可能请求小的内存，而且释放之后也很可能再次请求小内存。所以合并释放小内存，并不明智。在 fast bins 中，不大于 max_fast （默认值为 64B）的 chunk 被释放后，首先会被放到 fast bins 中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用户分配的 chunk 小于或等于 max_fast 时，ptmalloc 首先会在 fast bins 中查找相应的空闲块，如果找不到，才会去 bins（那个数组）中查找数据块。

在某个特定的时刻，ptmalloc 会遍历整个 fast bins 将相邻的空闲 chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，再加入到其他的 bin 中。

• unsorted bin

如果被用户释放的 chunk 或在 fast bins 中合并的 chunk 大于 max_fast，则 ptmalloc 会把这些 chunk 放入 unsorted bin 中。在查找合适的 chunk 的时候，首先在 unsorted bin 中查找合适的空闲 chunk，然后才查找 bins。

如果 unsorted bin 中没有合适的 chunk，则会把 unsorted bin 中的 chunk 加入到 bins 的其他 bin 中，再进行查找

0X02 特殊的 Chunk

并不是所有的 chunk 都按照上面的方式来组织，实际上，有三种例外的情况：

Top chunk，mmaped chunk 和 last remainder

Top chunk

top chunk 对于主分配区和非主分配区是不一样的

1）对于非主分配区来说

ptmalloc 会预先从 mmap 区域划分一个出一个 sub_heap，用来相应用户的申请内存的请求。由于内存是从低向高分配的，在空闲内存的最高处，必然存在着空闲的 chunk，这个就是 top chunk。在 fast bin 和 bins 都不能满足用户的申请请求时，ptmalloc 就会尝试在 top chunk 中分出一块内存给用户。

如果当前的 top chunk 也不够大，分配程序会重新分配一个 sub ，并把当前的 top chunk 迁移到新的 sub heap 上。新的 sub heap 与旧的 sub heap 用单链表连接在一起，然后在新的 sub heap 上分配内存。top chunk 在分配的时候总是在 fast bin 和 bins 之后才被考虑，所以不论 top chunk 有多大，他都不会被放进 fast bin 或者 bin 中

top chunk 会随着内存的分配变换大小，如果有被释放的 chunk 与 top chunk 相邻，增大 top chunk 的大小。如果回收的内存大于某一个阈值，并且 Top chunk 也超过了某个收缩阈值，ptmalloc 会收缩 sub heap。

如果 top chunk 包含了整个 sub heap，那么 ptmalloc 会调用 mumap 把整个 sub heap 回收

2）对于主分配区来说

由于「主分配区」是唯一能访进程 heap 区域的分配区。他可以通过 brk() sbrk() 增大收缩 heap 的大小。ptmalloc 在开始的时候，会预先分配一块较大的内存，这就是 heap

mmaped chunk

当申请一块较大的 chunk。并且 fast bin 和 bins 都不能满足分配，top chunk 也不能满足的时候，ptmalloc 会使用 mmap 直接分配页（4 KB），这样的 chunk 在被 free 的时候时直接解除映射，直接还给操作系统。再次访问这块内存，会报 segment fault 的错误。这样的 chunk 也不会包含在任何 bin 中。

Last remainder

当需要一个小的 chunk 的时候，small chunk 中没有，如果 Last remainder chunk 的大小大于所分配的 chunk，那么就会从 Last remainder chunk 中分出去一个 chunk，剩下的部分还会作为 Last remainder。和上述的 chunk 一样， Last remainder 也不属于任何一个 bin。