前言

在上一篇文章中，详细介绍了堆内存管理中涉及到的基本概念以及相互关系，同时也着重介绍了堆中chunk分配和释放策略中使用到的隐式链表技术。通过前面的介绍，我们知道使用隐式链表来管理内存中chunk总会涉及到内存的遍历，效率极低。对此glibc malloc引入了显示链表技术来提高堆内存分配和释放的效率。

所谓的显示链表就是我们在数据结构中常用的链表，而链表本质就是将一些属性相同的“节点”串联起来，方便管理。在glibc malloc中这些链表统称为bin，链表中的“节点”就是各个chunk，结点的共同属性就是：1）均为free chunk；2）同一个链表中各个chunk的大小相等（有一个特例，详情见后文）。

bin介绍

如前文所述，bin是一种记录free chunk的链表数据结构。系统针对不同大小的free chunk，将bin分为4类：1）Fast bin；2）Unsorted bin；3）Small bin；4）Large bin。

在glibc中用于记录bin的数据结构有两种，分别如下所示：

fastbinsY:这是一个数组，用于记录所有fast bin是；

bins:这也是一个数组，用于记录所有fast bins之外的所有bins。事实上，一共有126个bins，分别是：

bin 1 为unsorted bin;
bin 2 到63为small bin;
bin 64到126为large bin。
其中具体数据结构定义如下：

struct malloc_state
{
  ……
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  ……
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];  // #define NBINS    128
  ……
};

这里mfastbinptr的定义：typedef struct malloc_chunk *mfastbinptr;
mchunkptr的定义：typedef struct malloc_chunk* mchunkptr;

画图更直观：

那么处于bins中各个free chunk是如何链接在一起的呢？回顾malloc_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;
};

其中的fd和bk指针就是指向当前chunk所属链表中forward或者backward chunk。

Fast Bin

既然有fast bin，那就肯定有fast chunk——chunk size为16到80字节的chunk就叫做fast chunk。为了便于后文描述，这里对chunk的大小做如下约定：

1）只要说到chunk size，那就表示该malloc_chunk的实际整体大小。

2）而说到chunk unused size，就表示该malloc_chunk中刨除诸如prev_size，size，fd和bk这类辅助成员之后的实际可用的大小。因此，对free chunk而言，其实可用大小总是比实际整体大小少16字节。

在内存分配和释放过程中，fast bin是所有bin中操作速度最快的。下面详细介绍fast bin的一些特性：

1）fast bin的个数——10个。

2）每个fast bin都是一个单链表（只使用fd指针）。为什么使用单链表呢？因为fast bin中无论是添加还是移除fast chunk，都是对“链表尾”进行操作，而不会对中间的fast chunk进行操作。更具体点就是LIFO(后入)算法：添加操作(free内存)就是将新的fast chunk加入链表尾，删除操作（malloc内存）就是将链表尾部的fast chunk删除。需要注意的是，为了实现LIFO算法，fashbinsY数组中每个fastbin元素均指向了该链表的rear end(尾节点)，而尾结点通过其fd指针指向前一个结点，以此类推。

3）chunk size:10个fast bin中所包含fast chunk size是按照步进8字节排列，即第一个fast bin中所有fast chunk size均为16字节，第二个fast bin为24字节，以此类推。在进行malloc初始化的时候，最大的fast chunk size被设置为80字节（chunk unused size 为64字节），因此模式情况下大小为16到80字节的chunk被分配到fast chunk。

4）不会对free chunk进行合并操作。鉴于设计fast bin的初衷就是进行快速的小内存分配和释放，因此系统将fast bin的chunk的P总是设置成1，这样即使当fast bin中某个chunk同一个free chunk相邻的时候，系统也不会进行自动合并操作，而是保留两者。虽然这样可能会造成额外的碎片化问题，但瑕不掩瑜。

5）malloc（fast chunk）操作：即用户通过malloc申请的大小属于fast chunk的大小范围（注意：用户请求size加上16字节是实际内存chunk size）。初始化的时候fast bin支持的最大内存大小以及所有fast bin链表都是空的，所以当最开始使用malloc申请内存的时候，即使申请的内存大小属于fast chunk的内存大小，它也不会交由fast bin来处理，而是向下传递交由small bin来处理，如果small bin也为空就交给unsorted bin处理。

* Maximum size of memory handled in fastbins.  */
static INTERNAL_SIZE_T global_max_fast;
 
/* offset 2 to use otherwise unindexable first 2 bins */
/*这里SIZE_SZ就是sizeof(size_t)，在32位系统为4，64位为8，fastbin_index就是根据要malloc的size来快速计算该size应该属于哪一个fast bin，即该fast bin的索引。因为fast bin中chunk是从16字节开始的，所有这里以8字节为单位(32位系统为例)有减2*8 = 16的操作！*/
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
 
 
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
 
#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
 

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

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

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

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

static void *
_int_malloc (mstate av, size_t bytes)
{
  ……
  /*
     If the size qualifies as a fastbin, first check corresponding bin.
     This code is safe to execute even if av is not yet initialized, so we
     can try it without checking, which saves some time on this fast path.
   */
   //第一次执行malloc(fast chunk)时这里判断为false，因为此时get_max_fast ()为0
   if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
  ※1  idx = fastbin_index (nb);
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp = *fb;
      do
        {
          victim = pp;
          if (victim == NULL)
            break;
        }
   ※2 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))!= victim);
      if (victim != 0)
        {
          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
            {
              errstr = "malloc(): memory corruption (fast)";
            errout:
              malloc_printerr (check_action, errstr, chunk2mem (victim));
              return NULL;
            }
          check_remalloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

得到第一个来自于fast bin的chunk之后，系统就将该chunk从对应的fast bin中移除，并将其地址返回给用户。

6）free（fast chunk）操作：这个操作很简单，主要分两步：先通过chunksize函数根据传入的地址指针获取该指针对应的chunk的大小，然后根据这个chunk大小获取该chunk所属的fast bin，然后在将此chunk添加到fast bin的链尾即可。整个操作都在_int_free函数中完成。

在main arena中fast bins(即数组fastbinsY)的整体操作示意图如下图：