之前已经提到过bin，bin的英文翻译为垃圾桶，顾名思义，bin就是用来存放被free掉的chunk的

chunk被free后的处理

先上一张大佬的图

图比较复杂，直接讲解一下。为了减少内存碎片，ptmalloc在释放当前堆cur chunk时会检测cur chunk的P位和cur_chunk的物理相邻的下一个chunk是否是top chunk、物理相邻的下一个chunk的P位。如果curchunk的P位为0则合并物理相邻的上一个chunk，并且chunk的起始地址变为上一个chunk。如果curchunk的物理相邻的下一个(高地址)chunk的P位为0，则向前合并并且将curchunk的起始地址作为新的chunk的起始地址。如果待释放的前一个(高地址)chunk为topchunk，则将curchunk和topchunk合并，并且将curchunk的地址作为topchunk的新地址

bins的详解

先回顾一下chunk的数据结构

struct malloc_chunk {
  /* #define INTERNAL_SIZE_T size_t */
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* 这两个指针只在free chunk中存在*/
  struct malloc_chunk* bk;
 
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

fastbin

fastbin被存放在fastbinY数组中，该数组一共有10个元素。并且我们来做一个规定：

1. chunk size表示chunk的整体大小

2. unused size表示chunk中出去prev_size和size字段剩下的部分

然后我们来详细了解一下fastbin的特性：

1. 每个fast bin都是一个单链表，只是使用fd指针。fast bin无论是添加还是移除都是对链表尾进行操作，使用后入先出算法，所以fastbinY数组中每个fastbin元素都存放了该链表的尾结点，尾结点通过fd指针指向前一个结点

2. 数组中相同的链表存放的chunk大小相同，并且下标相邻的数组元素中的chunk链表的chunk size相差8字节(就是第一个元素chunk size都是16字节，第二个都是24字节，以此类推)，所以默认情况下大小尾16到80字节的chunk会被分到fast chunk中

3. 不会对freechunk进行合并操作。因为fastchunk本身就是为了快速存取chunk，所以每一个chunk的P位都是设置为1(表示前一个chunk已使用)。但是当释放的chunk与该chunk相邻的空闲chunk合并后大小大于一定的大小时(FASTBIN_CONSOLIDATION_THRESHOLD),内存碎片可能会比较多，我们就需要把fast bin中的chunk都进行合并

4. 用户通过malloc请求的大小如果属于fast chunk的大小范围，而这时fast bin支持的最大内存大小以及所有的fast bin链表都是空的(意思就是fast bin里面没有东西)，所以最开始使用malloc申请内存的时候即使申请的内存大小属于fast chunk的内存大小，它也不会交给fast bin处理，而是交给small bin，如果small bin也为空的话就交给unsorted bin

当我们第一次调用malloc(fast bin)的时候，系统执行_int_malloc函数，该函数首先会发现当前fast bin为空，就转交给small bin处理，进而又发现small bin 也为空，就调用malloc_consolidate函数对malloc_state结构体进行初始化，malloc_consolidate函数主要完成以下几个功能：

a. 首先判断当前malloc_state结构体中的fast bin是否为空，如果为空就说明整个malloc_state都没有完成初始化，需要对malloc_state进行初始化。

b. malloc_state的初始化操作由函数malloc_init_state(av)完成，该函数先初始化除fast bin之外的所有的bins(构建双链表，详情见后文small bins介绍)，再初始化fast bins。

然后当再次执行malloc(fast chunk)函数的时候，此时fast bin相关数据不为空了，就开始使用fast bin

free(fast chunk)操作：这个操作很简单，主要分为两步：先通过chunksize函数根据传入的地址指针获取该指针对应的chunk的大小；然后根据这个chunk大小获取该chunk所属的fast bin，然后再将此chunk添加到该fast bin的链尾即可。整个操作都是在_int_free函数中完成。得到第一个来自于fast bin的chunk之后，系统就将该chunk从对应的fast bin中移除，并将其地址返回给用户，见上面代码※2处。

unsorted bin

当释放较小或较大的chunk的时候，如果系统没有将它们添加到对应的bins中(为什么，在什么情况下会发生这种事情呢？详情见后文)，系统就将这些chunk添加到unsorted bin中。为什么要这么做呢？这主要是为了让“glibc malloc机制”能够有第二次机会重新利用最近释放的chunk(第一次机会就是fast bin机制)。利用unsorted bin，可以加快内存的分配和释放操作，因为整个操作都不再需要花费额外的时间去查找合适的bin了。

Unsorted bin的特性如下：

1. unsorted bin的个数： 1个。unsorted bin是一个由free chunks组成的循环双链表。

2. Chunk size: 在unsorted bin中，对chunk的大小并没有限制，任何大小的chunk都可以归属到unsorted bin中。这就是前言说的特例了，不过特例并非仅仅这一个，后文会介绍。

small bin

Small bin的特性如下：

1. small bin个数：62个。每个small bin也是一个由对应free chunk组成的循环双链表。同时Small bin采用FIFO(先入先出)算法：内存释放操作就将新释放的chunk添加到链表的front end(前端)，分配操作就从链表的rear end(尾端)中获取chunk。

2. chunk size：同一个small bin中所有chunk大小是一?样的，且第一个small bin中chunk大小为16字节，后续每个small bin中chunk的大小依次增加8字节，即最后一个small bin的chunk为16 + 62 * 8 = 512字节。

3. 合并操作：相邻的free chunk需要进行合并操作，即合并成一个大的free chunk。具体操作见下文free(small chunk)介绍。

4. malloc(small chunk)操作：类似于fast bins，最初所有的small bin都是空的，因此在对这些small bin完成初始化之前，即使用户请求的内存大小属于small chunk也不会交由small bin进行处理，而是交由unsorted bin处理，如果unsorted bin也不能处理的话，glibc malloc就依次遍历后续的所有bins，找出第一个满足要求的bin，如果所有的bin都不满足的话，就转而使用top chunk，如果top chunk大小不够，那么就扩充top chunk，这样就一定能满足需求了(还记得上一篇文章中在Top Chunk中留下的问题么？答案就在这里)。注意遍历后续bins以及之后的操作同样被large bin所使用

过后，当再次调用malloc(small chunk)的时候，如果该chunk size对应的small bin不为空，就从该small bin链表中取得small chunk，否则就需要交给unsorted bin及之后的逻辑来处理了。注意在malloc源码中，将bins数组中的第一个成员索引值设置为了1，而不是我们常用的0(在bin_at宏中，自动将i进行了减1处理…)。从上面代码可以看出在初始化的时候glibc malloc将所有bin的指针都指向了自己——这就代表这些bin都是空的。

5. free(small chunk)：当释放small chunk的时候，先检查该chunk相邻的chunk是否为free，如果是的话就进行合并操作：将这些chunks合并成新的chunk，然后将它们从small bin中移除，最后将新的chunk添加到unsorted bin中。

largebin

大于512字节的chunk称之为large chunk，large bin就是用于管理这些large chunk的。

Large bin的特性如下：

1. large bin的数量：63个。Large bin类似于small bin，只是需要注意两点：一是同一个large bin中每个chunk的大小可以不一样，但必须处于某个给定的范围(特例2) ；二是large chunk可以添加、删除在large bin的任何一个位置。

在这63个large bins中，前32个large bin依次以64字节步长为间隔，即第一个large bin中chunk size为512~575字节，第二个large bin中chunk size为576 ~ 639字节。紧随其后的16个large bin依次以512字节步长为间隔；之后的8个bin以步长4096为间隔；再之后的4个bin以32768字节为间隔；之后的2个bin以262144字节为间隔；剩下的chunk就放在最后一个large bin中。

鉴于同一个large bin中每个chunk的大小不一定相同，因此为了加快内存分配和释放的速度，就将同一个large bin中的所有chunk按照chunk size进行从大到小的排列：最大的chunk放在链表的front end，最小的chunk放在rear end。

2. 合并操作：类似于small bin。

3. malloc(large chunk)操作：

初始化完成之前的操作类似于small bin，这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小属于哪一个large bin，然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。如果大于，就从rear end开始遍历该large bin，找到第一个size相等或接近的chunk，分配给用户。如果该chunk大于用户请求的size的话，就将该chunk拆分为两个chunk：前者返回给用户，且size等同于用户请求的size；剩余的部分做为一个新的chunk添加到unsorted bin中。

如果该large bin中最大的chunk的size小于用户请求的size的话，那么就依次查看后续的large bin中是否有满足需求的chunk，不过需要注意的是鉴于bin的个数较多(不同bin中的chunk极有可能在不同的内存页中)，如果按照上一段中介绍的方法进行遍历的话(即遍历每个bin中的chunk)，就可能会发生多次内存页中断操作，进而严重影响检索速度，所以glibc malloc设计了Binmap结构体来帮助提高bin-by-bin检索的速度。Binmap记录了各个bin中是否为空，通过bitmap可以避免检索一些空的bin。如果通过binmap找到了下一个非空的large bin的话，就按照上一段中的方法分配chunk，否则就使用top chunk来分配合适的内存。

4. Free(large chunk)：类似于small chunk。

这些也就是有关bin的内容了

本文参考自知乎、CTFWIKI