glibc2.23中的malloc和free源码分析

管理结构

malloc_chunk

chunk的基本结构

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  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;
};

// 典型的chunk结构
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if allocated            | |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             User data starts here...                          .
	    .                                                               .
	    .             (malloc_usable_size() bytes)                      .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk                                     |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

//free chunk
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk                            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Forward pointer to next chunk in list             |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Back pointer to previous chunk in list            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Unused space (may be 0 bytes long)                .
	    .                                                               .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• prev_size，当前的chunk为free的时候，表示物理相邻的前一个chunk的大小，并可以通过这个大小找到前一个chunk的起始位置。当该块为use的时候，该位可以被前一块的数据占用。
• size表示当前chunk的大小，由于size最小需要8字节对齐，因此其低3空闲，分别用作falg即NMP，其中N表示的是当前的chunk是否属于主进程，M表示的是当前的chunk是否是由mmap分配的P表示的是前一个chunk是否是空闲的。最开始的一个chunk该位总是置1，防止引用不存在的内存地址。
• fd当chunk空闲时，指向下一个空闲的chunk，bk指向上一个空闲的chunk
• fd_nextsize当为largebin的时候才是用，指向下一个与当前的chunk大小不同的chunk，largebin链表中相同大小的一组chunk仅第一块chunk的fd_nextsize,bk_nextsize指向下一个和上一个与当前大小不同的堆块，其余的chunk该位为空。

malloc_state

malloc_state是非常常用的一个结构体了，通常用mstate来表示。

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;//互斥锁

  /* Flags (formerly in max_fast).  */
  int flags;//标志位，用来表示当前的arena中是否存在fastbin或者内存是否连续等

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];//存放每一个fastbin链表的头指针，最多支持的bin的个数为10个

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;//top chunk堆顶

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;//指向上一个chunk分配出一个small chunk之后剩余的部分

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];//存储unsorted_bin,small_bin.large_bin的链表头

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];//每一个bit表示对应的bin中是否存在空闲chunk

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;//当前内存的分配量
  INTERNAL_SIZE_T max_system_mem;
};

每个分配区是一个malloc_state结构体的实例，ptmalloc使用这个结构体来管理每一个分配区，而参数的管理使用的是malloc_par结构体，全局拥有一个该结构体的实例。

分配区是为了加速多线程分配内存而引入的。主分配区和子分配区形成一个环形链表，每一个线程中都存在一个私有的变量存放分配区指针，在分配内存的时候，查看那个分配区没有上锁，即在哪个分配区分配内存，如果分配区全部被占用，则建立一个新的分配区。

对于sbrk和mmap两种分配方式，主分配区都可以实现。相对的子分配区则是预先mmap申请一块较大的内存。

#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)

针对fastbin中最大的bin，对32为系统来说，其数据空间最大为80字节，对64位系统来说其最大的数据空间为160字节。注意这里的数据空间都不不包含chunk头部的。

bins变量中存储了unsorted_bin，small_bin（62），large_bin（63）的链表头指针，其中bins[0],bins[127]都不存在，bins[1]中存储了unsorted_bin的chunk的链表头部，mchunkptr是malloc_chunk的结构体指针。

• small bin，从small bin定义的宏来看，其数组下标index与存储的chunk的大小的关系是：chunk_size = MALLOC_ALIGNMENT *index，其中MALLOC_ALIGNMENT=2 * SIZE_SZ。对32位系统来说，其最大的chunk的大小为504字节，64位为1008字节

  #define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
  #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
  #define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
  
  #define in_smallbin_range(sz)  \
    ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
  
  #define smallbin_index(sz) \
    ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
     + SMALLBIN_CORRECTION)

• large bin，共包含63个bin， 每个bin中的chunk的大小不一致，而是出于一定的范围之内，此外这63个bin被分成了6组，每组bin的chunk的大小之间的公差一致。

  largebin排列方式为从大到小依次排列，链表头的bk指针指向最小的堆块。

  #define largebin_index_32(sz)                                                \
    (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
     ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
     ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
     ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
     ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
     126)
  
  #define largebin_index_32_big(sz)                                            \
    (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
     ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
     ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
     ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
     ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
     126)
  
  // XXX It remains to be seen whether it is good to keep the widths of
  // XXX the buckets the same or whether it should be scaled by a factor
  // XXX of two as well.
  #define largebin_index_64(sz)                                                \
    (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
     ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
     ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
     ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
     ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
     126)
  
  #define largebin_index(sz) \
    (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
     : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
     : largebin_index_32 (sz))

binmap中的每一位表示对应的bin中是否存在空闲的chunk，4个block来管理，每个block有4个字节，也就是128个bit。

malloc_par

struct malloc_par
{
  /* Tunable parameters */
  unsigned long trim_threshold;//收缩阈值
  INTERNAL_SIZE_T top_pad;//分配内存时是否添加额外的pad，默认为0
  INTERNAL_SIZE_T mmap_threshold;//mmap的分配阈值
  INTERNAL_SIZE_T arena_test;//最小分配区
  INTERNAL_SIZE_T arena_max;//最大分配区

  /* Memory map support */
  int n_mmaps;//当前进程使用mmap()分配的内存块的个数
  int n_mmaps_max;//可以使用mmap()分配的内存块的最大数量
  int max_n_mmaps;
  /* the mmap_threshold is dynamic, until the user sets
     it manually, at which point we need to disable any
     dynamic behavior. */
  int no_dyn_threshold;//是否开启mmap分配阈值动态调整，0表示开启，默认为0

  /* Statistics */
  INTERNAL_SIZE_T mmapped_mem;//mmap分配的内存大小
  /*INTERNAL_SIZE_T  sbrked_mem;*/
  /*INTERNAL_SIZE_T  max_sbrked_mem;*/
  INTERNAL_SIZE_T max_mmapped_mem;//mmap分配的内存大小，一般与mmaped_mem相等
  INTERNAL_SIZE_T max_total_mem;  /* only kept for NO_THREADS *///单线程情况下统计进程分配的内存总数

  /* First address handed out by MORECORE/sbrk.  */
  char *sbrk_base;
};

• thrim_threshold字段表示收缩阈值，默认为128KB，当top chunk的大小大于这个阈值的时候，在调用free函数的时候可能会缩小top chunk，收缩内存。收缩阈值可以通过mallocopt函数设置。由于mmap分配阈值动态调整，free函数最大可以将收缩阈值设置为分配阈值的2倍。
• mmap_threshold表示分配阈值，默认值为128KB，32位系统中最大值为512KB，64位系统中的最大值为32MB。默认开启了mmap分配阈值的动态调整，但是不会超过最大值。
• arena_test和arena_max，当每个进程中的分配区的数量大于arena_max的时候不会创建新的分配区，当分配区数量小于arena_test的时候不会重用现有的分配区。

heap_info

typedef struct _heap_info
{
    mstate ar_ptr; /* Arena for this heap. */
    struct _heap_info *prev; /* Previous heap. */
    size_t size;   /* Current size in bytes. */
    size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
    /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
    char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

该结构体主要是为了非主线程分配内存使用的，也就是在非主分配区分配内存。因为主分区分配内存可以直接使用sbrk方式扩展内存，只有一个堆。而非主线程的heap是提前分配好的，因此当该heap资源用完时，就需要重新申请内存空间，因为一般情况下申请的内存空间是不连续的，因此需要记录一个线程中不同的heap的链接结构。

• ar_ptr表示该堆所对应的分配区
• prev该线程的上一个堆结构，注意到这里是采用单链表的形式来记录一个线程的所有堆结构的。
• size堆的大小

函数

malloc

程序调用的malloc函数也就是__libc_malloc函数，如果分配堆空间成功会返回一个新分配的chunk的指针，如果空间不足则返回的是NULL指针，出现错误的时候会将errno设置为相应的数值。这里需要注意的是当分配空间的大小是0的时候，malloc函数也会分配一个最小的chunk。看一下malloc的具体代码

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    (void) mutex_unlock (&ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}
libc_hidden_def (__libc_malloc)

从函数流程中我们可以看出，首先函数先检查了malloc_hook是否被设置，若被设置，则直接调用malloc_hook。若未被设置，则首先调用arena_get函数获取一个可用的分配区，然后调用_int_malloc函数，该函数是堆块分配的主函数。

如果_int_malloc函数返回的chunk的指针为空，且当前的分配区指针不为空，则再次尝试_int_malloc。对分配之后的chunk指针进行地址检查，检查是否为mmap并存在于当前分配区的chunk。

_int_malloc

 checked_request2size (bytes, nb);

 /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
    mmap.  */
 if (__glibc_unlikely (av == NULL))
   {
     void *p = sysmalloc (nb, av);
     if (p != NULL)
alloc_perturb (p, bytes);
     return p;
   }

首先是将传入的参数的大小设置为对齐，并判断传入的参数大小是否符合要求（若小于最小的chunk，则size为最小的chunk）然后检查传入的malloc_state结构体，若是当前没有可用的分配区，或者是第一次分配，则调用sysmalloc函数分配内存。这里需要注意的是第一次调用malloc的时候malloc_hook不为空其值为malloc_hook_ini函数，通过调用_init_malloc实现了一些初始化的操作，在后面详细分析该函数。

fastbin

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
  {
    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx);
    mchunkptr pp = *fb;
    do
      {
        victim = pp;
        if (victim == NULL)
          break;
      }
    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), av);
            return NULL;
          }
        check_remalloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }
  }

得到可以分配的内存之后，首先判断size的大小是否符合fastbin的大小范围，最大的fastbin是通过全局变量global_max_fast来表示的。在这一部分，首先获取size大小在fastbin链表中的表示相应大小的fastbin的链表头指针，即fb与pp。判断当前所在的链表中是否存在相应大小的fastbin chunk。若不存在则跳出fastbin分配函数，去申请相应大小的smallbin。

若链表非空，则分配第一个chunk。注意这里检查了所分配的chunk的size与当前fastbin链表所表示的size的大小是否相同，若不相同则调用malloc_printerr函数打印错误信息。接着调用了check_remalloced_chunk函数对chunk结构体的一些标志位做了检查，主要检查了该chunk是否是malloc_state所表示的分配区中的，检查这块chunk是否已经分配，是否重复分配和一些大小的检查。

small bin

 if (in_smallbin_range (nb))
   {
     idx = smallbin_index (nb);
     bin = bin_at (av, idx);
     //last(b) ((b)->bk)
     if ((victim = last (bin)) != bin)
       {
         if (victim == 0) /* initialization check */
           malloc_consolidate (av);
         else
           {
             bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
               {
                 errstr = "malloc(): smallbin double linked list corrupted";
                 goto errout;
               }
             set_inuse_bit_at_offset (victim, nb);
             bin->bk = bck;
             bck->fd = bin;

             if (av != &main_arena)
               victim->size |= NON_MAIN_ARENA;
             check_malloced_chunk (av, victim, nb);
             void *p = chunk2mem (victim);
             alloc_perturb (p, bytes);
             return p;
           }
       }
   }

先判断size的大小是否符合smallbin的范围内，若符合small bin的大小范围则在malloc_state结构体中找到与其对应大小的small bin数组的起始地址。接着判断该small bin链表是否为空（从这里可以看出，初始化的small bin的bk指针是指向自身的。

若链表不为空且链表中存储有相应大小的chunk，将链表尾部的chunk分配出去，从分配的链表指针变化我们可以看出，链表头部的bk指针指向的是链表尾部的chunk，链表尾部chunk的fd指针指向链表头部。在分配之前还会确认该chunk的链表指针是否正确，相当于检查了victim->bk->fd!=victim。分配完毕之后会对chunk结构体的标志位做一些检查，这里和fastbin的检查相似。

__glibc_unlikely (bck->fd != victim)

这里的特殊情况就是small bin没有初始化，此时所有的指针均为空，这时程序就会调用malloc_consolidate函数将fastbin链表中的所有的chunk进行合并，并将合并后的chunk插入到unsorted bin中。

large bin

else
{
    idx = largebin_index (nb);
    if (have_fastchunks (av))
        malloc_consolidate (av);
}

若不符合small bin的大小，则获取用户申请大小的size所在的large bin数组的下标，并将fastbin进行合并，并插入到unsorted bin链表中。

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){
    bck = victim->bk;
    if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (victim->size > av->system_mem, 0))
        malloc_printerr (check_action, "malloc(): memory corruption",
                         chunk2mem (victim), av);
    size = chunksize (victim);
    ...
}

首先通过判断unsorted bin不为空的情况，若链表不为空，则从链表的尾部开始对链表中的chunk进行处理。这里首先判断了chunk的size的大小是否合法，若合法则获取chunk size。

if (in_smallbin_range (nb) &&
    bck == unsorted_chunks (av) &&
    victim == av->last_remainder &&
    (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
    /* split and reattach remainder */
    remainder_size = size - nb;
    remainder = chunk_at_offset (victim, nb);
    unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
    av->last_remainder = remainder;
    remainder->bk = remainder->fd = unsorted_chunks (av);
    if (!in_smallbin_range (remainder_size))
    {
        remainder->fd_nextsize = NULL;
        remainder->bk_nextsize = NULL;
    }

    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);
    set_foot (remainder, remainder_size);

    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
}

如果用户申请的chunk的大小属于small bin的范围内，并且unsorted bin链表中只有一个chunk并指向last_remainder，且该chunk的size大小大于用户申请的size大小，就将该chunk拆分为两个chunk，将符合用户申请大小的chunk返回，拆分之后剩余的chunk插入到unsorted bin链表中，更新last_remainder。

unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

否则就将当前的chunk从unsorted bin链表中摘除，这里实现了一个类似于unlink的操作。

if (size == nb)
{
    set_inuse_bit_at_offset (victim, size);
    if (av != &main_arena)
        victim->size |= NON_MAIN_ARENA;
    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
}

如果用户申请的size的大小恰好与当前chunk的大小相同，则将当前的chunk返回。否则就将当前的chunk插入到bins中

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){
    ...
    if (in_smallbin_range (size))
    {
        victim_index = smallbin_index (size);
        bck = bin_at (av, victim_index);
        fwd = bck->fd;
    }
    else
    {
        victim_index = largebin_index (size);
        bck = bin_at (av, victim_index);
        fwd = bck->fd;
        
        
        /* maintain large bins in sorted order */
        if (fwd != bck)// largebin链表不为空
        {
            /* Or with inuse bit to speed comparisons */
            size |= PREV_INUSE;
            /* if smaller than smallest, bypass loop below */
            assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
            if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
            {//当前堆块的大小小于最小的堆块，则将当前堆块插入到链表的尾部
                fwd = bck;//指向链表最后一个堆块
                bck = bck->bk;

                victim->fd_nextsize = fwd->fd;
                victim->bk_nextsize = fwd->fd->bk_nextsize;
                //将链表首堆块的bk_nextsize和原链表最后一个堆块的fd_nextsize指向当前的chunk
                fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
            }
            else
            {//将当前的chunk插入到largebin链表中的合适位置
                assert ((fwd->size & NON_MAIN_ARENA) == 0);
                while ((unsigned long) size < fwd->size)//查找合适的位置
                {
                    fwd = fwd->fd_nextsize;
                    assert ((fwd->size & NON_MAIN_ARENA) == 0);
                }
                //此时fwd指向的是大小恰好小于等于当前chunk的堆块
                if ((unsigned long) size == (unsigned long) fwd->size)
                 //当前大小的chunk数组不为空，则将当前堆块插入到数组的第二个位置中，插入的操作在之后进行
                 //因为插入到此位置不用修改数组的首堆块的fd_nextsize和bk_nextsize
                    /* Always insert in the second position.  */
                    fwd = fwd->fd;
                else
                {
                    victim->fd_nextsize = fwd;
                    victim->bk_nextsize = fwd->bk_nextsize;
                    fwd->bk_nextsize = victim;
                    victim->bk_nextsize->fd_nextsize = victim;
                    //上一条语句相当于fwd->bk_nextsize->fd_nextsize=victim;
                    //如果我们控制了fwd指向的即大小恰好小于当前堆块的bk_nextsize的内容，就可以在改地址的+0x20处写入堆地址
                }
                bck = fwd->bk;
            }
        }
        else//largebin链表为空则只需要加入链表即可
            victim->fd_nextsize = victim->bk_nextsize = victim;
    }
    //上面我们只对不同大小的largebin数组进行链表的链接，还需要在大小相同的largebin chunk组成的数组中进行插入
    mark_bin (av, victim_index);
    victim->bk = bck;
    victim->fd = fwd;
    fwd->bk = victim;
    bck->fd = victim;//该语句相当于fwd->bk->fd=victim;如果我们控制了fwd的bk指针就可以在任意地址+0x10写入堆地址

    #define MAX_ITERS       10000
    if (++iters >= MAX_ITERS)
        break;
}

首先是获得chunk size所对应的bins中的列表的头指针，也就是chunk需要插入的地址。由于large chunk列表中的chunk的size大小并不一定相同，因此在获取插入位置的时候需要进行遍历链表，以保持large bin中的有序状态。在这个过程中并对指向上一个或下一个大小不同的chunk的bk_nextsize，fd_nextsize进行赋值。在得到头指针和index之后，设置bitmap并将该chunk插入到相应的链表中。最后的break的含义是为了防止unsorted bin中的chunk太多，而导致一直处理unsorted bin中chunk的情况。

从这里也可以看出，largebin链表是从大到小排列的，也就是链表尾部的chunk的size是最小的。

这里存在任意地址写入堆地址的漏洞

for (;; ){
    while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){
        //处理unsorted bin
        //分配small bin
    }
    if (!in_smallbin_range (nb))
    {
        bin = bin_at (av, idx);

        /* skip scan if empty or largest chunk is too small */
        if ((victim = first (bin)) != bin &&
            (unsigned long) (victim->size) >= (unsigned long) (nb))
        {
            victim = victim->bk_nextsize;
            while (((unsigned long) (size = chunksize (victim)) <
                    (unsigned long) (nb)))
                victim = victim->bk_nextsize;

            /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
            if (victim != last (bin) && victim->size == victim->fd->size)
                victim = victim->fd;

            remainder_size = size - nb;
            unlink (av, victim, bck, fwd);

            /* Exhaust */
            if (remainder_size < MINSIZE)
            {
                set_inuse_bit_at_offset (victim, size);
                if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
            }
            /* Split */
            else
            {
                remainder = chunk_at_offset (victim, nb);
                /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                bck = unsorted_chunks (av);
                fwd = bck->fd;
                if (__glibc_unlikely (fwd->bk != bck))
                {
                    errstr = "malloc(): corrupted unsorted chunks";
                    goto errout;
                }
                remainder->bk = bck;
                remainder->fd = fwd;
                bck->fd = remainder;
                fwd->bk = remainder;
                if (!in_smallbin_range (remainder_size))
                {
                    remainder->fd_nextsize = NULL;
                    remainder->bk_nextsize = NULL;
                }
                set_head (victim, nb | PREV_INUSE |
                          (av != &main_arena ? NON_MAIN_ARENA : 0));
                set_head (remainder, remainder_size | PREV_INUSE);
                set_foot (remainder, remainder_size);
            }
            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
        }
    }
    //...
}

接下来开始在bins数组中寻找合适的chunk，如果用户申请的chunk位于large bin的范围内，且其对应的链表中存在符合要求的chunk（这里的符合要求是指用户申请的chunk size大小小于链表中最大的chunk。

那么从链表尾部开始，即从最小的chunk开始，寻找最符合用户申请大小的chunk，即恰好大于等于用户申请大小的chunk。将符合要求的chunk拆分，如果拆分剩余的chunk的size大小没有办法组成一个chunk的话，则不进行拆分，直接返回较大的chunk。否则将拆分之后的chunk插入到unsorted bin中，注意的是这里进行了double free的检查if (__glibc_unlikely (fwd->bk != bck))

for (;; ){
    //处理unsorted bin，分配small bin
    //处理用户申请的size所对应的large bin中存在符合要求的chunk的情况
    ++idx;
    bin = bin_at (av, idx);
    block = idx2block (idx);
    map = av->binmap[block];
    bit = idx2bit (idx);

    for (;; )
    {
        /* Skip rest of block if there are no more set bits in this block.  */
        //根据block找到存在空闲chunk的large bin链表
        if (bit > map || bit == 0)
        {
            do
            {
                if (++block >= BINMAPSIZE) /* out of bins */
                    goto use_top;
            }
            while ((map = av->binmap[block]) == 0);

            bin = bin_at (av, (block << BINMAPSHIFT));
            bit = 1;
        }

        /* Advance to bin with set bit. There must be one. */
        //在block中找到的存在符合要求的large bin链表的头指针
        while ((bit & map) == 0)
        {
            bin = next_bin (bin);
            bit <<= 1;
            assert (bit != 0);
        }

        /* Inspect the bin. It is likely to be non-empty */
        victim = last (bin);

        /*  If a false alarm (empty bin), clear the bit. */
        if (victim == bin)
        {
            av->binmap[block] = map &= ~bit; /* Write through */
            bin = next_bin (bin);
            bit <<= 1;
        }

        else
        {
            size = chunksize (victim);

            /*  We know the first chunk in this bin is big enough to use. */
            assert ((unsigned long) (size) >= (unsigned long) (nb));

            remainder_size = size - nb;

            /* unlink */
            unlink (av, victim, bck, fwd);

            /* Exhaust */
            if (remainder_size < MINSIZE)
            {
               //...与上一个代码块相同，处理不能拆分chunk的操作
                set_inuse_bit_at_offset (victim, size);
                if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
            }

            /* Split */
            else
            {
                //...与上一个代码块相同，处理可以拆分chunk的操作
                //但是在插入unsorted bin之后设置了last_remainder
                remainder = chunk_at_offset (victim, nb);

                /* We cannot assume the unsorted list is empty and therefore
                         have to perform a complete insert here.  */
                bck = unsorted_chunks (av);
                fwd = bck->fd;
                if (__glibc_unlikely (fwd->bk != bck))
                {
                    errstr = "malloc(): corrupted unsorted chunks 2";
                    goto errout;
                }
                remainder->bk = bck;
                remainder->fd = fwd;
                bck->fd = remainder;
                fwd->bk = remainder;

                /* advertise as last remainder */
                if (in_smallbin_range (nb))
                    av->last_remainder = remainder;
                if (!in_smallbin_range (remainder_size))
                {
                    remainder->fd_nextsize = NULL;
                    remainder->bk_nextsize = NULL;
                }
                set_head (victim, nb | PREV_INUSE |
                          (av != &main_arena ? NON_MAIN_ARENA : 0));
                set_head (remainder, remainder_size | PREV_INUSE);
                set_foot (remainder, remainder_size);
            }
            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
        }
    }
}

如果对应大小的链表中不存在符合要求的chunk则向下一个较大的large bin链表中搜索符合要求的chunk。首先是根据binmap找到后方链表中存在空闲chunk的链表。map表示当前idx表示的bin在binmap中所在的block，map>0就表示当前的block中存在空闲chunk。若bit > map则表示当前的block中大于bit所表示的bin的large bin中不存在空闲chunk。那么就需要搜索下一个block。

找到存在空闲chunk的双向链表之后获取其头指针。在进行分配之前先检查了链表是否为空，防止binmap出错。若不为空选取其中最小的chunk即可以满足用户的要求，接下来就是和正常的large bin分配相同了。不同的是这里更新了last_remainder指针。

top chunk

如果large bin中不存在符合要求的chunk，那么就需要从top chunk上分配一块符合要求的chunk。

for (;; ){
    //处理unsorted bin，分配small bin
    //处理用户申请的size所对应的large bin中存在符合要求的chunk的情况
    //处理表示更大size的large bin链表中存在空闲chunk的情况
    use_top:
    victim = av->top;
    size = chunksize (victim);

    if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
    {
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        av->top = remainder;
        set_head (victim, nb | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE);

        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
    }
}

如果当前的top chunk的size大于用户申请的chunk的大小，并且拆分之后的chunk的大小大于MINSIZE，即可以组成一个新的chunk，那么直接将top chunk拆分。

否则先检查fastbin中是否存在空闲chunk(其他的线程可能释放)，如果存在空闲的chunk，那么就合并fastbin，进入下一个for循环再次查找bins。

否则就调用sysmalloc进一步分配内存。

总结

这里所说的用户申请的size包含chunk头部。

1. 检查是否设置了malloc_hook，若设置了则跳转进入malloc_hook（第一次调用malloc时设置了malloc_hook来实现初始化操作），若未设置则获取当前的分配区，进入int_malloc函数。
   1. 如果当前的分配区为空，则调用sysmalloc分配空间，返回指向新chunk的指针，否则进入下一步。
   2. 若用户申请的大小符合fastbin大小范围，若相应大小的链表不为空则返回链表头部的chunk，否则进入下一步。
   3. 如果用户申请的大小符合small bin的范围，则在相应大小的链表中寻找chunk，若small bin未初始化，则进入第4步，否则验证链表是否为空，若不为空将链表尾部的chunk分配给用户，否则进入第5步。
   4. 调用malloc_consolidate函数将fastbin进行合并插入到unsorted bin链表中（通过get_max_fast若堆未初始化则初始化堆）。
   5. 用户申请的大小符合large bin或small bin链表为空，开始处理unsorted bin链表中的chunk。在unsorted bin链表中查找符合大小的chunk，若用户申请的大小为small bin，unsorted bin中只有一块chunk并指向last_remainder，且chunk size的大小大于size+MINSIZE(保证拆分之后的remainder能组成一个chunk)，则对当前的chunk进行拆分，更新分配区中的last_remainder。否则进入下一步。
   6. 将当前的unsorted bin中的chunk取下，若其size恰好为用户申请的size，则将chunk返回给用户。否则进入下一步
   7. 获取当前chunk size所对应的bins数组中的头指针。（large bin需要保证从大到小的顺序，因此需要遍历）将其插入到对应的链表中。如果处理的chunk的数量大于MAX_ITERS则不在处理。进入下一步。
   8. 如果用户申请的空间的大小符合large bin的范围或者对应的small bin链表为空且unsorted bin链表中没有符合大小的chunk，则在对应的large bin链表中查找符合条件的chunk（即其大小要大于用户申请的size）。若找到相应的chunk则对chunk进行拆分，返回符合要求的chunk（无法拆分时整块返回）。否则进入下一步。
   9. 根据binmap找到表示更大size的large bin链表，若其中存在空闲的chunk，则将chunk拆分之后返回符合要求的部分，并更新last_remainder。否则进入下一步。
   10. 若top chunk的大小大于用户申请的空间的大小，则将top chunk拆分，返回符合用户要求的chunk，并更新last_remainder，否则进入下一步。
   11. 若fast bin不为空（其他线程可能释放chunk），则调用malloc_consolidate合并fastbin，返回第5步继续执行。否则进入下一步。
   12. 调用sysmalloc分配空间，返回指向新chunk的指针。
2. 若_int_malloc函数返回的chunk指针为空，且当前分配区指针不为空，则再次尝试_int_malloc
3. 对chunk指针进行检查，主要检查chunk是否为mmap，且位于当前的分配区内。

free

free(void* p)释放p指向的chunk指针，如果p是空值，则没有任何的效果。如果p已经被释放，那么将会触发未定义的行为。默认释放大容量内存的时候将直接交还给system，从而减少系统占用的空间。

void
__libc_free (void *mem)
{
  mstate ar_ptr;
  mchunkptr p;                          /* chunk corresponding to mem */

  void (*hook) (void *, const void *)
    = atomic_forced_read (__free_hook);
  if (__builtin_expect (hook != NULL, 0))
    {
      (*hook)(mem, RETURN_ADDRESS (0));
      return;
    }

  if (mem == 0)                              /* free(0) has no effect */
    return;

  p = mem2chunk (mem);

  if (chunk_is_mmapped (p))                       /* release mmapped memory. */
    {
      /* see if the dynamic brk/mmap threshold needs adjusting */
      if (!mp_.no_dyn_threshold
          && p->size > mp_.mmap_threshold
          && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
        {
          mp_.mmap_threshold = chunksize (p);
          mp_.trim_threshold = 2 * mp_.mmap_threshold;
          LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
                      mp_.mmap_threshold, mp_.trim_threshold);
        }
      munmap_chunk (p);
      return;
    }

  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);
}
libc_hidden_def (__libc_free)

程序首先判断free_hook是否被设置，如果被设置，则执行free_hook。如果未被设置，且需要释放的指针不为空值，则判断指针指向的chunk是否是mmap的。

如果chunk是由mmap分配的，则首先更新mmap分配和收缩阈值，然后调用munmap_chunk函数释放chunk。否则调用_int_free函数释放chunk。

_int_free

size = chunksize (p);

/* Little security check which won't hurt performance: the
   allocator never wrapps around at the end of the address space.
   Therefore we can exclude some size values which might appear
   here by accident or by "design" from some intruder.  */
//uintptr_t即unsigned long int
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
    || __builtin_expect (misaligned_chunk (p), 0))
  {
    errstr = "free(): invalid pointer";
  errout:
    if (!have_lock && locked)
      (void) mutex_unlock (&av->mutex);
    malloc_printerr (check_action, errstr, chunk2mem (p), av);
    return;
  }
/* We know that each chunk is at least MINSIZE bytes in size or a
   multiple of MALLOC_ALIGNMENT.  */
if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
  {
    errstr = "free(): invalid size";
    goto errout;
  }

首先获取chunk的大小，然后判断传入的chunk指针的合法性以及size的合法性。如果传入的size和指针合法，则首先判断chunk是否属于fastbin。

fastbin

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS//即若与top chunk相邻，不立即与top chunk合并
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
      {
	/* We might not have a lock at this point and concurrent modifications
	   of system_mem might have let to a false positive.  Redo the test
	   after getting the lock.  */
	if (have_lock
	    || ({ assert (locked == 0);
		  mutex_lock(&av->mutex);
		  locked = 1;
		  chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
	      }))
	  {
	    errstr = "free(): invalid next size (fast)";
	    goto errout;
	  }
	if (! have_lock)
	  {
	    (void)mutex_unlock(&av->mutex);
	    locked = 0;
	  }
      }
      //...
  }

接下来还是对fastbin的size进行了验证，主要是判断其大小是否小于2*SIZE_SZ，或者大于system_mem等非法值。如果size合法则进入下面的处理。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //size合法性验证
    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    //...
}

程序首先调用free_perturb函数，这个函数是用来清理chunk中的用户数据的

free_perturb (char *p, size_t n)
{
  if (__glibc_unlikely (perturb_byte))
    memset (p, perturb_byte, n);
}

即如果设置了perturb_byte的值，就会将chunk中的用户数据设置为该值。

接下来就是将malloc_state中表示fastbin中含有空闲chunk的位置为1，并获得与释放chunk大小对应的fast bin链表的头指针。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //size合法性验证
    //设置标志位，获取相应fast bin链表的头指针
    do
    {
        /* Check that the top of the bin is not the record we are going to add
           (i.e., double free).  */
        if (__builtin_expect (old == p, 0))
        {
            errstr = "double free or corruption (fasttop)";
            goto errout;
        }
        /* Check that size of fastbin chunk at the top is the same as
           size of the chunk that we are adding.  We can dereference OLD
           only if we have the lock, otherwise it might have already been
           deallocated.  See use of OLD_IDX below for the actual check.  */
        if (have_lock && old != NULL)
            old_idx = fastbin_index(chunksize(old));
        p->fd = old2 = old;
    }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);

    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
    {
        errstr = "invalid fastbin entry (free)";
        goto errout;
    }
}

在将chunk插入fast bin链表的时候，首先判断了链表的第一个chunk是否与当前的chunk相同，即判断是否为double free。接下来就是通过CAS操作将chunk插入到fast bin链表中。

unsorted bin

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //处理size大小小于最大fast bin限制的chunk，将其插入到fast bin链表中
}
else if (!chunk_is_mmapped(p)) {
    if (! have_lock) {
        (void)mutex_lock(&av->mutex);
        locked = 1;
    }

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__glibc_unlikely (p == av->top))
    {
        errstr = "double free or corruption (top)";
        goto errout;
    }
    /* Or whether the next chunk is beyond the boundaries of the arena.  */
    if (__builtin_expect (contiguous (av)
			  && (char *) nextchunk
			  >= ((char *) av->top + chunksize(av->top)), 0))
      {
	errstr = "double free or corruption (out)";
	goto errout;
      }
    /* Or whether the block is actually not marked used.  */
    if (__glibc_unlikely (!prev_inuse(nextchunk)))
      {
	errstr = "double free or corruption (!prev)";
	goto errout;
      }

    nextsize = chunksize(nextchunk);
    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (nextsize >= av->system_mem, 0))
      {
	errstr = "free(): invalid next size (normal)";
	goto errout;
      }
    //...
}

如果需要释放的chunk不是mmap分配的，就对传入的chunk指针进行合法性验证。指针不能指向top chunk，物理相邻的下一个chunk是否超出了指定的范围，指针指向的chunk必须被标记为use，物理相邻的下一个chunk的size大小需要满足要求。如果验证合法，那么就进入下一步。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //处理size大小小于最大fast bin限制的chunk，将其插入到fast bin链表中
}
else if (!chunk_is_mmapped(p)) {
	free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    //合法性验证
    /* consolidate backward */
    if (!prev_inuse(p)) {
        prevsize = p->prev_size;
        size += prevsize;
        p = chunk_at_offset(p, -((long) prevsize));
        unlink(av, p, bck, fwd);
    }
    //...
}

如果物理相邻的上一个chunk是空闲的，则将两个chunk合并，这里采用了unlink函数。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //处理size大小小于最大fast bin限制的chunk，将其插入到fast bin链表中
}
else if (!chunk_is_mmapped(p)) {
	free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    //合法性验证
    //合并物理相邻的上一个chunk
    if (nextchunk != av->top) {
        /* get and clear inuse bit */
        nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

        /* consolidate forward */
        if (!nextinuse) {
            unlink(av, nextchunk, bck, fwd);
            size += nextsize;
        } else
            clear_inuse_bit_at_offset(nextchunk, 0);

        /*
        Place the chunk in unsorted chunk list. Chunks are
        not placed into regular bins until after they have
        been given one chance to be used in malloc.
          */

        bck = unsorted_chunks(av);
        fwd = bck->fd;
        if (__glibc_unlikely (fwd->bk != bck))//指针完整性验证
        {
            errstr = "free(): corrupted unsorted chunks";
            goto errout;
        }
        p->fd = fwd;
        p->bk = bck;
        if (!in_smallbin_range(size))
        {
            p->fd_nextsize = NULL;
            p->bk_nextsize = NULL;
        }
        bck->fd = p;
        fwd->bk = p;

        set_head(p, size | PREV_INUSE);
        set_foot(p, size);

        check_free_chunk(av, p);
    }
    /*
      If the chunk borders the current high end of memory,
      consolidate into top
    */

    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
    }
    //...
}

如果当前的chunk与top chunk相邻，则与top chunk合并。

否则判断物理相邻的下一个chunk是否是空闲的，如果是空闲的则进行合并，使用unlink将物理相邻的下一个chunk取下。如果非空闲，则将物理相邻的下一个chunk的prev_inuse置0，表示当前的chunk已经空闲。在判断unsorted bin链表头部和尾部指针正确之后，即将chunk插入到unsorted bin链表中。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //处理size大小小于最大fast bin限制的chunk，将其插入到fast bin链表中
}
else if (!chunk_is_mmapped(p)) {
	free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    //合法性验证
    //合并物理相邻的上一个chunk
    //将chunk合并到unsorted bin中
    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
        if (have_fastchunks(av))
            malloc_consolidate(av);

        if (av == &main_arena) {
            #ifndef MORECORE_CANNOT_TRIM
            if ((unsigned long)(chunksize(av->top)) >=
                (unsigned long)(mp_.trim_threshold))
                systrim(mp_.top_pad, av);
            #endif
        } else {
            /* Always try heap_trim(), even if the top chunk is not
	   large, because the corresponding heap might go away.  */
            heap_info *heap = heap_for_ptr(top(av));

            assert(heap->ar_ptr == av);
            heap_trim(heap, mp_.top_pad);
        }
    }

    if (! have_lock) {
        assert (locked);
        (void)mutex_unlock(&av->mutex);
    }
}

这里判断如果前面释放的chunk的大小比较大，就将fastbin中的chunk进行合并并添加到unsorted bin链表中，如果进程所在的分配区是主分配区并且可以收缩内存的话，就调用systrim收缩内存，否则就获得非主分配区的heap_info指针，调用heap_trim收缩heap。

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()/*忽略 if .. endif*/){
    //处理size大小小于最大fast bin限制的chunk，将其插入到fast bin链表中
}
else if (!chunk_is_mmapped(p)) {
    //处理chunk大于fast bin chunk的大小，且chunk为非mmap的情况
}
else {
    munmap_chunk (p);
}

最后如果chunk是mmap分配的则调用munmap释放该chunk。‘

总结

1. 首先检查free_hook，如果已经设置，则跳转到free_hook处，否则进入第二步
2. 如果chunk是通过mmap分配的，则调用munmap函数释放chunk，否则调用_int_free函数（这部分只分析_int_free函数，munmap在这里
   1. 对传入的指针和其指向的chunk size进行合法性验证，判断传入的chunk为inuse
   2. 若chunk size的大小满足fast bin的大小范围，则在经过指针和size的合法性验证之后将chunk插入到fast bin链表中。若chunk不是由mmap分配的，则进入下一步，否则进入第5步
   3. 此时chunk size的大小超过fast bin的规定范围，将chunk与物理相邻的前一个chunk进行前向合并，与物理相邻的后一个chunk(包含 top chunk)进行后向合并。合并后的chunk插入到unsorted bin链表中。进入下一步
   4. 判断释放的chunk size的大小，超过阈值之后收缩内存。
   5. chunk是通过mmap分配的，调用munmap释放chunk。

calloc

realloc

realloc(void* p, size_t n)，扩展已经分配的内存空间。如果p指向的chunk存在连续的空闲空间，则扩展p指向的chunk。否则分配一块新的chunk，并将p指向的chunk中的数据拷贝到新chunk中释放原有的chunk，返回新chunk指针。当p为空时，realloc等价于malloc。如果新的size小于原有的size则只会拷贝size大小的数据。

void *
__libc_realloc (void *oldmem, size_t bytes)
{
  mstate ar_ptr;
  INTERNAL_SIZE_T nb;         /* padded request size */

  void *newp;             /* chunk to return */

  void *(*hook) (void *, size_t, const void *) =
    atomic_forced_read (__realloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));

#if REALLOC_ZERO_BYTES_FREES
  if (bytes == 0 && oldmem != NULL)
    {
      __libc_free (oldmem); return 0;
    }
#endif

  /* realloc of null is supposed to be same as malloc */
  if (oldmem == 0)
    return __libc_malloc (bytes);
    /* chunk corresponding to oldmem */
    const mchunkptr oldp = mem2chunk (oldmem);
    /* its size */
    const INTERNAL_SIZE_T oldsize = chunksize (oldp);

    if (chunk_is_mmapped (oldp))
        ar_ptr = NULL;
    else
        ar_ptr = arena_for_chunk (oldp);

    /* Little security check which won't hurt performance: the
             allocator never wrapps around at the end of the address space.
             Therefore we can exclude some size values which might appear
             here by accident or by "design" from some intruder.  */
    if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
        || __builtin_expect (misaligned_chunk (oldp), 0))
    {
        malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
                         ar_ptr);
        return NULL;
    }

    checked_request2size (bytes, nb);

  //...
}
libc_hidden_def (__libc_realloc)

首先检查realloc_hook是否设置，否则跳转到realloc_hook处。若传入的指针为空，则相当于malloc，若新申请的size为0，且指针不为空，则相当于free(这里是设置了参数可以为0的条件)。

//size与指针合法性验证
if (chunk_is_mmapped (oldp))
{
    void *newmem;

    #if HAVE_MREMAP
    newp = mremap_chunk (oldp, nb);
    if (newp)
        return chunk2mem (newp);
    #endif
    /* Note the extra SIZE_SZ overhead. */
    if (oldsize - SIZE_SZ >= nb)
        return oldmem;                         /* do nothing */

    /* Must alloc, copy, free. */
    newmem = __libc_malloc (bytes);
    if (newmem == 0)
        return 0;              /* propagate failure */

    memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
    munmap_chunk (oldp);
    return newmem;
}
//...

接下来判断原有的chunk是否为mmap分配的，如果是则首先判断size的大小，如果新申请的size比原始的size大SIZE_SZ字节的话，就重新malloc一个新的chunk，并拷贝数据，调用munmap函数释放原始的chunk

这里可以看到即使是扩展mmap分配的chunk，也是通过malloc,copy,free这三个操作来实现的。即mmap分配的chunk经过扩展之后的chunk是通过malloc分配的。

//size和指针合法性验证
if (chunk_is_mmapped (oldp)){
    //处理chunk是mmap的情况
}
(void) mutex_lock (&ar_ptr->mutex);

newp = _int_realloc (ar_ptr, oldp, oldsize, nb);

(void) mutex_unlock (&ar_ptr->mutex);
assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
        ar_ptr == arena_for_chunk (mem2chunk (newp)));

if (newp == NULL)
{
    /* Try harder to allocate memory in other arenas.  */
    LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
    newp = __libc_malloc (bytes);
    if (newp != NULL)
    {
        memcpy (newp, oldmem, oldsize - SIZE_SZ);
        _int_free (ar_ptr, oldp, 0);
    }
}
return newp;

程序调用了_int_realloc函数来执行扩展内存的操作。如果调用失败，则在尝试在其他的arena处分配内存（LIBC_PROBE没看懂，注释是这样写的）。

int_realloc

void*
_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
	     INTERNAL_SIZE_T nb)
{
    //参数定义
    if (__builtin_expect (oldp->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (oldsize >= av->system_mem, 0))
    {
        errstr = "realloc(): invalid old size";
        errout:
        malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
        return NULL;
    }

    check_inuse_chunk (av, oldp);

    /* All callers already filter out mmap'ed chunks.  */
    assert (!chunk_is_mmapped (oldp));

    next = chunk_at_offset (oldp, oldsize);
    INTERNAL_SIZE_T nextsize = chunksize (next);
    if (__builtin_expect (next->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (nextsize >= av->system_mem, 0))
    {
        errstr = "realloc(): invalid next size";
        goto errout;
    }
    //...
}

程序首先对传入的指针指向的chunk和其物理相邻的下一个chunk进行了合法性验证，包含size的大小应在一定的范围内，原始chunk不能为mmap分配等。

void*
_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
	     INTERNAL_SIZE_T nb)
{
    //参数定义和安全性检查
    //逻辑就是首先获得一个大于等于原有chunk的chunk，之后在进行拆分
    if ((unsigned long) (oldsize) >= (unsigned long) (nb))
    {
      /* already big enough; split below */
      newp = oldp;
      newsize = oldsize;
    }
    else
    {
        newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
        if (newmem == 0)
            return 0; /* propagate failure */

        newp = mem2chunk (newmem);
        newsize = chunksize (newp);

        /*
             Avoid copy if newp is next chunk after oldp.
           */
        if (newp == next)
        {
            newsize += oldsize;
            newp = oldp;
        }
        else
        {
            //这里是正常进行扩展的部分，也就是malloc一个申请大小的chunk，拷贝数据之后释放原有的chunk
            /*
                 Unroll copy of <= 36 bytes (72 if 8byte sizes)
                 We know that contents have an odd number of
                 INTERNAL_SIZE_T-sized words; minimally 3.
               */

            copysize = oldsize - SIZE_SZ;
            s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
            d = (INTERNAL_SIZE_T *) (newmem);
            ncopies = copysize / sizeof (INTERNAL_SIZE_T);
            assert (ncopies >= 3);

            if (ncopies > 9)
                memcpy (d, s, copysize);

            else
            {
                *(d + 0) = *(s + 0);
                *(d + 1) = *(s + 1);
                *(d + 2) = *(s + 2);
                if (ncopies > 4)
                {
                    *(d + 3) = *(s + 3);
                    *(d + 4) = *(s + 4);
                    if (ncopies > 6)
                    {
                        *(d + 5) = *(s + 5);
                        *(d + 6) = *(s + 6);
                        if (ncopies > 8)
                        {
                            *(d + 7) = *(s + 7);
                            *(d + 8) = *(s + 8);
                        }
                    }
                }
            }

            _int_free (av, oldp, 1);
            check_inuse_chunk (av, newp);
            return chunk2mem (newp);
        }
    }
    //...
}

判断如果新分配的大小小于原有的大小的，暂时将新分配的大小设置为原有的大小，之后在进行分拆。如果新分配的大小大于原有的大小，先使用malloc分配一块用户申请的大小的chunk。

• 若该chunk与原有的chunk相邻，则直接将新的chunk指针设置为原有的chunk指针，同时更新size。（这里是为了避免拷贝造成的时间消耗）。
• 否则判断需要拷贝的字节的大小，如果需要拷贝的字节数较大则直接调用memcpy进行拷贝，否则手工拷贝
• 拷贝数据完成之后，将原有的chunk释放

经过这里我们获得的chunk一定大于或者等于原有的chunk，因此需要进行分拆

void*
_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
	     INTERNAL_SIZE_T nb)
{
    //参数定义和安全性检查
    if ((unsigned long) (oldsize) >= (unsigned long) (nb))
    {
      /* already big enough; split below */
      newp = oldp;
      newsize = oldsize;
    }
    else
    {
        //分配新的chunk，若与原有的chunk相邻，则合并
        //否则拷贝数据，释放原有的chunk
    }
    /* If possible, free extra space in old or extended chunk */
    //拆分并释放多余的chunk空间
    assert ((unsigned long) (newsize) >= (unsigned long) (nb));

    remainder_size = newsize - nb;

    if (remainder_size < MINSIZE)   /* not enough extra to split off */
    {
        set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_inuse_bit_at_offset (newp, newsize);
    }
    else   /* split remainder */
    {
        remainder = chunk_at_offset (newp, nb);
        set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        /* Mark remainder as inuse so free() won't complain */
        set_inuse_bit_at_offset (remainder, remainder_size);
        _int_free (av, remainder, 1);
    }

    check_inuse_chunk (av, newp);
    return chunk2mem (newp);
}

尝试进行拆分，这里需要注意的是拆分之后的chunk的大小需要满足组成一个chunk的条件。如果不能拆分则返回当前的chunk，如果可以进行拆分则释放拆分之后的chunk，返回合适的chunk。

总结

1. 首先判断realloc_hook是否设置，如果设置则跳转到realloc_hook位置，否则进入下一步
2. 如果该chunk是mmap分配的，则通过malloc,copy,free的操作进行申请空间，拷贝数据，释放原有的chunk。这里需要注意的是如果设置了HAVE_MREMAP，则调用mremap_chunk函数进行分配chunk(该函数之后在进行分析)。如果不是则进入下一步
3. 得到一个大于等于原有chunk大小的新chunk。进入下一步
   1. 如果新申请的大小小于原有的chunk，则返回原有的chunk，否则进入下一步
   2. 根据用户申请的大小，malloc一个新的chunk，如果该chunk位于原有的chunk之后，则合并chunk，返回原有的chunk指针（这里是为了避免拷贝耗时）否则进入下一步
   3. 根据需要拷贝的数据大小选择不同的拷贝方式，释放原有的chunk，返回新分配的chunk指针。
4. 尝试进行拆分，如果拆分成功则将拆分之后的chunk释放，否则返回该chunk

sysmalloc

sysmalloc (INTERNAL_SIZE_T nb, mstate av)，函数用来扩展或者更改top chunk，从系统申请内存。

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    /*
     If have mmap, and the request size meets the mmap threshold, and
     the system supports mmap, and there are few enough currently
     allocated mmapped regions, try to directly map this request
     rather than expanding top.
   */
    if (av == NULL
        || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
            && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
        char *mm;           /* return value from mmap call*/

        try_mmap:
        /*
         Round up size to nearest page.  For mmapped chunks, the overhead
         is one SIZE_SZ unit larger than for normal chunks, because there
         is no following chunk whose prev_size field could be used.

         See the front_misalign handling below, for glibc there is no
         need for further alignments unless we have have high alignment.
       */
        if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
            size = ALIGN_UP (nb + SIZE_SZ, pagesize);
        else
            size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
        tried_mmap = true;

        /* Don't try if size wraps around 0 */
        if ((unsigned long) (size) > (unsigned long) (nb))
        {
            mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));

            if (mm != MAP_FAILED)
            {
                /*
                 The offset to the start of the mmapped region is stored
                 in the prev_size field of the chunk. This allows us to adjust
                 returned start address to meet alignment requirements here
                 and in memalign(), and still be able to compute proper
                 address argument for later munmap in free() and realloc().
               */

                if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
                {
                    /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
                     MALLOC_ALIGN_MASK is 2*SIZE_SZ-1.  Each mmap'ed area is page
                     aligned and therefore definitely MALLOC_ALIGN_MASK-aligned.  */
                    assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
                    front_misalign = 0;
                }
                else
                    front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
                if (front_misalign > 0)
                {
                    correction = MALLOC_ALIGNMENT - front_misalign;
                    p = (mchunkptr) (mm + correction);
                    p->prev_size = correction;
                    set_head (p, (size - correction) | IS_MMAPPED);
                }
                else
                {
                    p = (mchunkptr) mm;
                    set_head (p, size | IS_MMAPPED);
                }

                /* update statistics */

                int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
                atomic_max (&mp_.max_n_mmaps, new);

                unsigned long sum;
                sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
                atomic_max (&mp_.max_mmapped_mem, sum);

                check_chunk (av, p);

                return chunk2mem (p);
            }
        }
    }
    if (av == NULL)
        return 0;
    //...
}

如果当前的分配区为空，或者是需要分配的大小大于mmap分配的阈值且分配完毕之后还存在可以分配的内存(通过n_mmaps<n_mmaps_max进行判断)。就采用mmap分配内存。

由于通过mmap分配的内存不存在chunk上下文之间的结构，需要加上表示prev_size的字段。因此需要重新计算需要分配的内存的大小，并进行对齐。接着调用MMAP函数进行分配一块可读可写的内存。这里的MMAP实际上就是调用的__mmap函数。之后在进行分析。

如果MMAP函数调用成功则进行相关的标志位设置，更新malloc_par中表示内存分配的chunk数量和内存大小的字段。

如果mmap失败，且当前分配区不可用，则返回空指针。

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    if (av == NULL
        || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
            && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
        //处理可以使用mmap的情况
    }
    if (av == NULL)
        return 0;
    /* Record incoming configuration of top */

  old_top = av->top;
  old_size = chunksize (old_top);
  old_end = (char *) (chunk_at_offset (old_top, old_size));

  brk = snd_brk = (char *) (MORECORE_FAILURE);

  /*
     If not the first time through, we require old_size to be
     at least MINSIZE and to have prev_inuse set.
   */

  assert ((old_top == initial_top (av) && old_size == 0) ||
          ((unsigned long) (old_size) >= MINSIZE &&
           prev_inuse (old_top) &&
           ((unsigned long) old_end & (pagesize - 1)) == 0));

  /* Precondition: not enough current space to satisfy nb request */
  assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));


  if (av != &main_arena)
    {
      //...
    }
    //...
}

首先对top chunk的大小和标志位进行检查，如果top chunk的大小足以分配用户申请的大小的chunk则返回错误。否则判断当前的分配区是否为主分配区（因为主分配区可以直接使用sbrk从系统分配内存）

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    if (av == NULL
        || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
            && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
        //处理可以使用mmap的情况
    }
    if (av == NULL)
        return 0;
    // top chunk 参数和大小检查
    if (av != &main_arena)
    {
        heap_info *old_heap, *heap;
        size_t old_heap_size;

        /* First try to extend the current heap. */
        old_heap = heap_for_ptr (old_top);
        old_heap_size = old_heap->size;
        if ((long) (MINSIZE + nb - old_size) > 0
            && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
        {
            av->system_mem += old_heap->size - old_heap_size;
            arena_mem += old_heap->size - old_heap_size;
            set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
                      | PREV_INUSE);
        }
        //...
    }
    //...
}

首先根据top chunk的指针取出该堆的heap info结构体

由于非主线程的堆都是按照HEAP_MAX_SIZE进行对齐分配的，因此我们将top chunk的地址保留前n位即可以获取heap_info结构体的起始地址

接着调用grow_heap函数尝试向top chunk的高地址处增加相应的大小。

grow_heap

/* Grow a heap.  size is automatically rounded up to a
   multiple of the page size. */

static int
grow_heap (heap_info *h, long diff)
{
    size_t pagesize = GLRO (dl_pagesize);
    long new_size;

    diff = ALIGN_UP (diff, pagesize);
    new_size = (long) h->size + diff;
    if ((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE)
        return -1;

    if ((unsigned long) new_size > h->mprotect_size)
    {
        if (__mprotect ((char *) h + h->mprotect_size,
                        (unsigned long) new_size - h->mprotect_size,
                        PROT_READ | PROT_WRITE) != 0)
            return -2;

        h->mprotect_size = new_size;
    }

    h->size = new_size;
    LIBC_PROBE (memory_heap_more, 2, h, h->size);
    return 0;
}

函数对于需要增加的大小采用pagesize进行对齐，并验证增加之后的heap是否超过了单线程所允许的最大的heap。通过验证之后，首先修改了新heap所在内存的保护标志，接着及重新赋值size即达到了增加heap的效果。

如果grop heap成功则修改malloc_state即表示当前分配区的结构体中表示内存分配总量的值。

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    if (av == NULL
        || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
            && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
        //处理可以使用mmap的情况
    }
    if (av == NULL)
        return 0;
    // top chunk 参数和大小检查
    if (av != &main_arena)
    {
        //参数获取
        if ((long) (MINSIZE + nb - old_size) > 0
            && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
        {
            //直接向top chunk高地址处扩展内存成功
        }
        else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
        {
            /* Use a newly allocated heap.  */
            heap->ar_ptr = av;
            heap->prev = old_heap;
            av->system_mem += heap->size;
            arena_mem += heap->size;
            /* Set up the new top.  */
            top (av) = chunk_at_offset (heap, sizeof (*heap));
            set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);

            /* Setup fencepost and free the old top chunk with a multiple of
             MALLOC_ALIGNMENT in size. */
            /* The fencepost takes at least MINSIZE bytes, because it might
             become the top chunk again later.  Note that a footer is set
             up, too, although the chunk is marked in use. */
            old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
            set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
            if (old_size >= MINSIZE)
            {
                set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
                set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
                set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
                _int_free (av, old_top, 1);
            }
            else
            {
                set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
                set_foot (old_top, (old_size + 2 * SIZE_SZ));
            }
        }
        else if (!tried_mmap)
            /* We can at least try to use to mmap memory.  */
            goto try_mmap;
    }
    //...
}

如果直接扩展内存失败，则调用new_heap函数重新申请一块heap内存。(大部分情况下扩展内存失败的原因是因为该heap的大小已经达到HEAP_MAX_SIZE了)。

new_heap

/* Create a new heap.  size is automatically rounded up to a multiple
   of the page size. */

static heap_info *
internal_function
new_heap (size_t size, size_t top_pad)
{
    size_t pagesize = GLRO (dl_pagesize);
    char *p1, *p2;
    unsigned long ul;
    heap_info *h;
    //对size进行调整
    if (size + top_pad < HEAP_MIN_SIZE)
        size = HEAP_MIN_SIZE;
    else if (size + top_pad <= HEAP_MAX_SIZE)
        size += top_pad;
    else if (size > HEAP_MAX_SIZE)
        return 0;
    else
        size = HEAP_MAX_SIZE;
    size = ALIGN_UP (size, pagesize);

    /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
     No swap space needs to be reserved for the following large
     mapping (on Linux, this is the case for all non-writable mappings
     anyway). */
    p2 = MAP_FAILED;
    if (aligned_heap_area)
    {
        p2 = (char *) MMAP (aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
                            MAP_NORESERVE);
        aligned_heap_area = NULL;
        if (p2 != MAP_FAILED && ((unsigned long) p2 & (HEAP_MAX_SIZE - 1)))
        {
            __munmap (p2, HEAP_MAX_SIZE);
            p2 = MAP_FAILED;
        }
    }
    if (p2 == MAP_FAILED)
    {
        p1 = (char *) MMAP (0, HEAP_MAX_SIZE << 1, PROT_NONE, MAP_NORESERVE);
        if (p1 != MAP_FAILED)
        {
            p2 = (char *) (((unsigned long) p1 + (HEAP_MAX_SIZE - 1))
                           & ~(HEAP_MAX_SIZE - 1));
            ul = p2 - p1;
            if (ul)
                __munmap (p1, ul);
            else
                aligned_heap_area = p2 + HEAP_MAX_SIZE;
            __munmap (p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
        }
        else
        {
            /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
             is already aligned. */
            p2 = (char *) MMAP (0, HEAP_MAX_SIZE, PROT_NONE, MAP_NORESERVE);
            if (p2 == MAP_FAILED)
                return 0;

            if ((unsigned long) p2 & (HEAP_MAX_SIZE - 1))
            {
                __munmap (p2, HEAP_MAX_SIZE);
                return 0;
            }
        }
    }
    if (__mprotect (p2, size, PROT_READ | PROT_WRITE) != 0)
    {
        __munmap (p2, HEAP_MAX_SIZE);
        return 0;
    }
    h = (heap_info *) p2;
    h->size = size;
    h->mprotect_size = size;
    LIBC_PROBE (memory_heap_new, 2, h, h->size);
    return h;
}

首先函数对size进行了调整（页大小对齐），注意这里的top pad是需要多分配的内存的大小。aligned_heap_area是上一次调用mmap分配结束之后的地址

• 如果aligned_heap_area存在那么尝试从改地址处分配HEAP_MAX_SIZE大小的内存空间（防止内存碎片化），如果成功，则将aligned_heap_area置为空表示已经分配完成，判断分配的内存空间的大小，如果不合法则释放该内存
• 如果分配失败，则申请分配2*HEAP_MAX_SIZE大小的内存空间，起始地址由内核决定。若分配成功则截取HEAP_MAX_SIZE大小的空间，设置aligned_heap_area为高地址处的内存空间。
• 如果2*HEAP_MAX_SIZE分配失败，则申请分配HEAP_MAX_SIZE大小的内存空间，如果失败则返回空指针。

分配成功之后修改新空间所在的内存地址的可读写权限，并更新heap_info结构体中表示内存大小的值。返回新的结构体指针。

如果分配新的堆块成功，则将该堆加入到本线程的堆链表中，更新malloc_state中表示内存分配数量的值和top chunk指针。接着就会释放之前的top chunk。

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    if (av == NULL
        || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
            && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
        //处理可以使用mmap的情况
    }
    if (av == NULL)
        return 0;
    // top chunk 参数和大小检查
    if (av != &main_arena)
    {
       //处理当前的分配区为非主分配区的情况
    }
    else     /* av == main_arena */


    { /* Request enough space for nb + pad + overhead */
        size = nb + mp_.top_pad + MINSIZE;

        /*
         If contiguous, we can subtract out existing space that we hope to
         combine with new space. We add it back later only if
         we don't actually get contiguous space.
       */

        if (contiguous (av))
            size -= old_size;

        /*
         Round to a multiple of page size.
         If MORECORE is not contiguous, this ensures that we only call it
         with whole-page arguments.  And if MORECORE is contiguous and
         this is not first time through, this preserves page-alignment of
         previous calls. Otherwise, we correct to page-align below.
       */

        size = ALIGN_UP (size, pagesize);

        /*
         Don't try to call MORECORE if argument is so big as to appear
         negative. Note that since mmap takes size_t arg, it may succeed
         below even if we cannot call MORECORE.
       */

        if (size > 0)
        {
            brk = (char *) (MORECORE (size));
            LIBC_PROBE (memory_sbrk_more, 2, brk, size);
        }
        if (brk != (char *) (MORECORE_FAILURE))
        {
            /* Call the `morecore' hook if necessary.  */
            void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
            if (__builtin_expect (hook != NULL, 0))
                (*hook)();
        }
        else
        {
            /*
             If have mmap, try using it as a backup when MORECORE fails or
             cannot be used. This is worth doing on systems that have "holes" in
             address space, so sbrk cannot extend to give contiguous space, but
             space is available elsewhere.  Note that we ignore mmap max count
             and threshold limits, since the space will not be used as a
             segregated mmap region.
           */

            /* Cannot merge with old top, so add its size back in */
            if (contiguous (av))
                size = ALIGN_UP (size + old_size, pagesize);

            /* If we are relying on mmap as backup, then use larger units */
            if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
                size = MMAP_AS_MORECORE_SIZE;

            /* Don't try if size wraps around 0 */
            if ((unsigned long) (size) > (unsigned long) (nb))
            {
                char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));

                if (mbrk != MAP_FAILED)
                {
                    /* We do not need, and cannot use, another sbrk call to find end */
                    brk = mbrk;
                    snd_brk = brk + size;

                    /*
                     Record that we no longer have a contiguous sbrk region.
                     After the first time mmap is used as backup, we do not
                     ever rely on contiguous space since this could incorrectly
                     bridge regions.
                   */
                    set_noncontiguous (av);
                }
            }
        }
        //...
    }
    //...
}

如果当前的分区为主分配区，首先是对传入的size进行了修正。如果分配区是连续的内存的话，就不用重新分配old_size了。接着调用MORECORE进行分配内存。这里的MORECORE是一个宏定义，其默认调用的是__default_morecore

void *
__default_morecore (ptrdiff_t increment)
{
    void *result = (void *) __sbrk (increment);
    if (result == (void *) -1)
        return NULL;

    return result;
}
libc_hidden_def (__default_morecore)

可以看出其调用了__sbrk进行扩展内存，如果调用成功则优先执行after_morecore_hook，否则调用mmap申请内存，并将malloc_state的表示内存空间是否连续的值设为no

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    //处理分配区为空或者可以使用mmap的情况
    if (av != &main_arena)
    {
       //处理当前的分配区为非主分配区的情况
    }
    else     /* av == main_arena */
    {
        //调用MORECORE(sbrk)，并处理调用失败的情况(mmap分配)，若调用成功则优先执行hook
        if (brk != (char *) (MORECORE_FAILURE))
        {
            if (mp_.sbrk_base == 0)
                mp_.sbrk_base = brk;
            av->system_mem += size;

            /*
             If MORECORE extends previous space, we can likewise extend top size.
           */

            if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
                set_head (old_top, (size + old_size) | PREV_INUSE);

            else if (contiguous (av) && old_size && brk < old_end)
            {
                /* Oops!  Someone else killed our space..  Can't touch anything.  */
                malloc_printerr (3, "break adjusted to free malloc space", brk,
                                 av);
            }

            /*
             Otherwise, make adjustments:

           * If the first time through or noncontiguous, we need to call sbrk
              just to find out where the end of memory lies.

           * We need to ensure that all returned chunks from malloc will meet
              MALLOC_ALIGNMENT

           * If there was an intervening foreign sbrk, we need to adjust sbrk
              request size to account for fact that we will not be able to
              combine new space with existing space in old_top.

           * Almost all systems internally allocate whole pages at a time, in
              which case we might as well use the whole last page of request.
              So we allocate enough more memory to hit a page boundary now,
              which in turn causes future contiguous calls to page-align.
           */

            else
            {
                front_misalign = 0;
                end_misalign = 0;
                correction = 0;
                aligned_brk = brk;

                /* handle contiguous cases */
                if (contiguous (av))
                {
                    /* Count foreign sbrk as system_mem.  */
                    if (old_size)
                        av->system_mem += brk - old_end;

                    /* Guarantee alignment of first new chunk made from this space */

                    front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
                    if (front_misalign > 0)
                    {
                        /*
                         Skip over some bytes to arrive at an aligned position.
                         We don't need to specially mark these wasted front bytes.
                         They will never be accessed anyway because
                         prev_inuse of av->top (and any chunk created from its start)
                         is always true after initialization.
                       */

                        correction = MALLOC_ALIGNMENT - front_misalign;
                        aligned_brk += correction;
                    }

                    /*
                     If this isn't adjacent to existing space, then we will not
                     be able to merge with old_top space, so must add to 2nd request.
                   */

                    //top chunk的大小
                    correction += old_size;

                    /* Extend the end address to hit a page boundary */
                    end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
                    //top chunk结束位置至新分配内存空间的大小
                    correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;

                    assert (correction >= 0);
                    snd_brk = (char *) (MORECORE (correction));

                    /*
                     If can't allocate correction, try to at least find out current
                     brk.  It might be enough to proceed without failing.

                     Note that if second sbrk did NOT fail, we assume that space
                     is contiguous with first sbrk. This is a safe assumption unless
                     program is multithreaded but doesn't use locks and a foreign sbrk
                     occurred between our first and second calls.
                   */

                    if (snd_brk == (char *) (MORECORE_FAILURE))
                    {
                        correction = 0;
                        snd_brk = (char *) (MORECORE (0));
                    }
                    else
                    {
                        /* Call the `morecore' hook if necessary.  */
                        void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
                        if (__builtin_expect (hook != NULL, 0))
                            (*hook)();
                    }
                }

                /* handle non-contiguous cases */
                else
                {
                    if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
                        /* MORECORE/mmap must correctly align */
                        assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
                    else
                    {
                        front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
                        if (front_misalign > 0)
                        {
                            /*
                             Skip over some bytes to arrive at an aligned position.
                             We don't need to specially mark these wasted front bytes.
                             They will never be accessed anyway because
                             prev_inuse of av->top (and any chunk created from its start)
                             is always true after initialization.
                           */

                            aligned_brk += MALLOC_ALIGNMENT - front_misalign;
                        }
                    }

                    /* Find out current end of memory */
                    if (snd_brk == (char *) (MORECORE_FAILURE))
                    {
                        snd_brk = (char *) (MORECORE (0));
                    }
                }
                //此时已经获得了对齐之后的内存空间的起始地址aligned_brk
                /* Adjust top based on results of second sbrk */
                if (snd_brk != (char *) (MORECORE_FAILURE))
                {
                    av->top = (mchunkptr) aligned_brk;
                    set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
                    av->system_mem += correction;

                    /*
                     If not the first time through, we either have a
                     gap due to foreign sbrk or a non-contiguous region.  Insert a
                     double fencepost at old_top to prevent consolidation with space
                     we don't own. These fenceposts are artificial chunks that are
                     marked as inuse and are in any case too small to use.  We need
                     two to make sizes and alignments work out.
                   */

                    if (old_size != 0)
                    {
                        /*
                         Shrink old_top to insert fenceposts, keeping size a
                         multiple of MALLOC_ALIGNMENT. We know there is at least
                         enough space in old_top to do this.
                       */
                        old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
                        set_head (old_top, old_size | PREV_INUSE);

                        /*
                         Note that the following assignments completely overwrite
                         old_top when old_size was previously MINSIZE.  This is
                         intentional. We need the fencepost, even if old_top otherwise gets
                         lost.
                       */
                        chunk_at_offset (old_top, old_size)->size =
                            (2 * SIZE_SZ) | PREV_INUSE;

                        chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
                            (2 * SIZE_SZ) | PREV_INUSE;

                        /* If possible, release the rest. */
                        if (old_size >= MINSIZE)
                        {
                            _int_free (av, old_top, 1);
                        }
                    }
                }
            }
        }
        //...
    }
    //...
}

如果sbrk扩展内存成功

• 若扩展的内存是否与原始的top chunk相邻（通过判断brk==old_end）且不是通过mmap分配的，此时直接增加top chunk的size即可。

• 否则先判断sbrk的执行是否出错，如果未出错则表示新分配的内存地址大于原有的top chunk但是不连续。

  • 先判断malloc_state的连续标志位，如果标志位为连续，则表示不是通过mmap分配的（会设置不连续标志位），应该是进程内的其他线程调用sbrk分配了内存空间。那么这一段内存也算是进程分配的内存空间更新malloc_state中的system_mem值。然后将分配的brk指针按照MALLOC_ALIGNMENT对齐。由于地址不连续就需要放弃当前top chunk的内存区域，程序中将top chunk的大小和对齐消耗的内存大小之和存储在correction变量中，调用sbrk函数在内存中又分配这correction大小的空间，其起始地址存储在snd_brk中。若分配失败则将snd_brk存储为第一次brk结束的地址，并置空correction变量。

    这部分的操作主要是为了弥补top chunk的损失，因为之后top chunk就释放了。需要补偿的原因是因为在进入主分配操作的时候，曾经判断malloc_state的连续性，如果连续则减去了top chunk的大小之后采用sbrk分配相应大小的内存。所以在使用sbrk这种方法的时候需要补偿top chunk才能够分配到符合用户大小的空间。

    而sbrk分配失败而采用mmap分配的时候则是加上了top chunk的大小，因此mmap不需要补偿。

  • 如果是采用MMAP分配的空间，则只需要对内存的起始地址进行对齐就可以了。

到这里我们获取得到了经过对齐之后的内存空间起始地址aligned_brk，更新top chunk指针。由于地址不连续因此需要在靠近不连续内存起始的地方设置fenceposts，以防止之前的chunk与这部分内存区域合并。每个fenceposts的大小为2*size_sz（共两个），将其prev_inuse始终置为1。然后释放top chunk中剩余的部分。到这里就基本上完成了内存扩展的部分。

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
    //参数定义
    //处理分配区为空或者可以使用mmap的情况
    if (av != &main_arena)
    {
       //处理当前的分配区为非主分配区的情况
    }
    else     /* av == main_arena */
    {
        //处理分配区为主分配区的情况
    }
    //经过上面的操作之后top chunk已经被扩展到可以分配用户输入大小的程度了
    if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
        av->max_system_mem = av->system_mem;
    check_malloc_state (av);

    /* finally, do the allocation */
    p = av->top;
    size = chunksize (p);

    /* check that one of the above allocation paths succeeded */
    if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
    {
        remainder_size = size - nb;
        remainder = chunk_at_offset (p, nb);
        av->top = remainder;
        set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE);
        check_malloced_chunk (av, p, nb);
        return chunk2mem (p);
    }

    /* catch all failure paths */
    __set_errno (ENOMEM);
    return 0;
}

经过top chunk扩展之后向用户分配内存。

总结

1. 检查当前的分配区为空或者可以进行mmap，则调用mmap分配内存，若分配成功则返回分配的内存指针。否则进入下一步。
2. 若当前分配区是主分配区则进入下一步，若当前分配区不是主分配区，则调用grow_heap增加top chunk空间，如果失败则调用new_heap重新分配一块内存。并在当前的top chunk的高地址处设置两块inuse的chunk（fencepost）以防止内存块与之后的内存块进行合并。进入第9步
3. 当前的分配区是主分配区。若malloc_state连续，则尝试使用MORECODE(sbrk)分配size-top_chunk.size大小的内存空间，若分配失败则进入下一步。分配成功之后执行after_morecode_hook，进入第4步。
4. 尝试使用mmap分配size大小的空间，若分配成功则设置当前的malloc_state不连续，进入下一步。
5. 判断新分配的内存空间与top chunk连续则直接改变top chunk的size，进入第n步，否则进入下一步。
6. 新分配的内存空间与top chunk不连续，若malloc_state标志位连续，则表示采用sbrk分配的内存空间，需要尝试对top chunk size大小的内存空间进行补偿，获取分配的补偿内存空间的起始地址，失败后不在尝试。进入第8步。若标志位不连续，进入下一步。
7. 此时表示分配空间采用mmap分配，且不连续，则直接获取分配空间的结束地址，进入下一步。
8. 此时已经获取了新分配的内存空间的起始和结束地址，设置top chunk指针，并设置fencepost，进入下一步
9. 此时top chunk已经扩展完成，根据用户传入的size分配内存空间。

malloc_hook_ini

在第一次调用malloc的时候，malloc_hook不为空指向malloc_hook_ini函数，完成初始化工作。malloc_hook_ini函数定义在glibc源代码的malloc/hooks.c文件中

static void *
malloc_hook_ini (size_t sz, const void *caller)
{
  __malloc_hook = NULL;
  ptmalloc_init ();
  return __libc_malloc (sz);
}

函数首先将malloc_hook的位置设置为空，然后调用了ptmalloc_init函数继续执行初始化，初始化完成之后重新调用__libc_malloc函数，也就是重新执行malloc。

ptmalloc_init

函数定义在malloc/arena.c文件中

static void
    ptmalloc_init (void)
{
    if (__malloc_initialized >= 0)
        return;

    __malloc_initialized = 0;

    #ifdef SHARED
    //这里是保证只有主分配区使用sbrk分配连续的内存空间
    //如果glibc不在默认的命名空间，或者是程序是静态编译并调用了dl_open函数加载ptmalloc_ini
    //这种情况下glibc不允许使用sbrk分配内存（修改了__morecore）
    /* In case this libc copy is in a non-default namespace, never use brk.
     Likewise if dlopened from statically linked program.  */
    Dl_info di;
    struct link_map *l;

    if (_dl_open_hook != NULL
        || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
            && l->l_ns != LM_ID_BASE))
        __morecore = __failing_morecore;
    #endif

    thread_arena = &main_arena;
    thread_atfork (ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
    //...
}

函数首先判断了ptmalloc是否已经被初始化__malloc_initialized变量的初始值为-1，若未初始化则设置初始化变量。

thread_atfork函数用来设置fork时处理锁的函数，防止死锁。在fork之前父进程调用ptmalloc_lock_all将所有的分配区锁住，禁止分配内存，子线程创建完毕之后，父进程执行ptmalloc_unlock_all释放所有的锁，由于子进程拷贝了父进程的互斥锁的状态，因此子进程执行ptmalloc_unlock_all2重新初始化所有的锁。

static void
    ptmalloc_init (void)
{
    //判断是否已经初始化
    //获取主分配区
      const char *s = NULL;
  if (__glibc_likely (_environ != NULL))
    {
      char **runp = _environ;
      char *envline;

      while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
                               0))
        {
          //获取第一次出现=的位置
          size_t len = strcspn (envline, "=");

          if (envline[len] != '=')
            /* This is a "MALLOC_" variable at the end of the string
               without a '=' character.  Ignore it since otherwise we
               will access invalid memory below.  */
            continue;

          switch (len)
            {
            case 6:
              if (memcmp (envline, "CHECK_", 6) == 0)
                s = &envline[7];
              break;
            case 8:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "TOP_PAD_", 8) == 0)
                    __libc_mallopt (M_TOP_PAD, atoi (&envline[9]));
                  else if (memcmp (envline, "PERTURB_", 8) == 0)
                    __libc_mallopt (M_PERTURB, atoi (&envline[9]));
                }
              break;
            case 9:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "MMAP_MAX_", 9) == 0)
                    __libc_mallopt (M_MMAP_MAX, atoi (&envline[10]));
                  else if (memcmp (envline, "ARENA_MAX", 9) == 0)
                    __libc_mallopt (M_ARENA_MAX, atoi (&envline[10]));
                }
              break;
            case 10:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "ARENA_TEST", 10) == 0)
                    __libc_mallopt (M_ARENA_TEST, atoi (&envline[11]));
                }
              break;
            case 15:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
                    __libc_mallopt (M_TRIM_THRESHOLD, atoi (&envline[16]));
                  else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
                    __libc_mallopt (M_MMAP_THRESHOLD, atoi (&envline[16]));
                }
              break;
            default:
              break;
            }
        }
    }
    if (s && s[0])
    {
        __libc_mallopt (M_CHECK_ACTION, (int) (s[0] - '0'));
        if (check_action != 0)
            __malloc_check_init ();//定义在malloc/hooks.c文件中。
        //将free,malloc,realloc,memalign函数的hook指向了各自的检查函数，用来检查是否已经初始化
    }
    void (*hook) (void) = atomic_forced_read (__malloc_initialize_hook);
    if (hook != NULL)
        (*hook)();
    __malloc_initialized = 1;
}

这一部分是从环境变量中读取相应的配置参数的值，如果某些项存在则调用__libc_mallopt函数设置相应的值。在函数调用的结尾处查看是否存在__malloc_initialize_hook，如果存在则执行相应的hook函数，否则设置初始化变量为1表示已经完成了初始化。

malloc_consolidate

该函数的主要作用是对堆进行初始化，以及将fastbin中的空闲chunk合并到unsorted bin中。

if (get_max_fast () != 0) {
    ...
}
else {
  malloc_init_state(av);
  check_malloc_state(av);
}

首先函数调用get_max_fast函数，该函数可以判断堆是否进行了初始化。因为在未初始化的时候，其返回值global_max_fast为0。若未初始化则对堆进行初始化，主要是将global_max_fast设置为DEFAULT_MXFAST，设置bins链表，将其fd,bk指针均指向自身，初始化top chunk。

若已经进行了初始化，则首先执行

clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
maxfb = &fastbin (av, NFASTBINS - 1);
fb = &fastbin (av, 0);

清除malloc_state中的fastbin相关的标志位，表示该分配区中不包含fast bin，获取unsorted bin链表的头指针。获取fastbin中表示最大和最小chunk链表的头指针。

do {
      p = atomic_exchange_acq (fb, 0);
      if (p != 0) {
        do {
         ...
        } while ( (p = nextp) != 0);

      }
    } while (fb++ != maxfb);

接着对fastbin中表示每个大小的chunk链表执行相同的操作，直到所有的fastbin都处理完毕。

首先是将当前的fastbin链表的头指针赋值给p，并将指针置为0表示该fastbin链表不包含任何的chunk。这里用到的是atomic_exchange_acq函数，即比较和替换函数。若fastbin当前链表不为空，则对每一个chunk执行下面的操作

#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
check_inuse_chunk(av, p);
nextp = p->fd;

/* Slightly streamlined version of consolidation code in free() */
size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);

首先对当前的chunk调用check_inuse_chunk进行检查，主要是调用do_check_chunk检查了chunk是否在min_address和max_address之间，并检查了物理相邻的下一个chunk的prev_inuse位是否为1。接着获取了该chunk的size，和物理相邻的下一个chunk的起始地址以及chunk_size。

if (!prev_inuse(p)) {
    prevsize = p->prev_size;
    size += prevsize;
    p = chunk_at_offset(p, -((long) prevsize));
    unlink(av, p, bck, fwd);
}

判断物理相邻的上一个chunk是否是空闲的，若是空闲的则将这两个chunk合并，并调用unlink函数将上一个chunk从链表中删除。

if (nextchunk != av->top) {
    ...
}

else {
    size += nextsize;
    set_head(p, size | PREV_INUSE);
    av->top = p;
}

接着就是判断当前的chunk（或者是合并完之后的chunk）是否和top chunk相邻。若与top chunk相邻，则将当前的chunk与top chunk进行合并。并设置top chunk的prev_inuse位为1。如果与top chunk不相邻则执行下面的操作

nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

if (!nextinuse) {
    size += nextsize;
    unlink(av, nextchunk, bck, fwd);
} else
    clear_inuse_bit_at_offset(nextchunk, 0);

first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;

if (!in_smallbin_range (size)) {
    p->fd_nextsize = NULL;
    p->bk_nextsize = NULL;
}

set_head(p, size | PREV_INUSE);
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size);

判断当前chunk物理相邻的下一个chunk是否是空闲的，若是空闲的则继续合并，若不是空闲的则清除下一个chunk的prev_inuse位，表示当前的chunk已经是空闲的了。并将当前的chunk插入到unsorted bin的链表头部，并设置当前chunk的prev_inuse为1，下一个chunk的prev_size为当前的size。

这样malloc_consolidate函数就完成了。

总结

1. 首先通过get_max_fast判断堆是否初始化，若未初始化，则初始化堆，否则进入下一步。
2. 将malloc_state中表示fastbin中含有空闲chunk的标志位清空，进入下一步。
3. 对fast bin中的每个chunk进行下列操作
   1. 与其物理相邻的chunk进行前向合并
   2. 若与top chunk相邻，则与top chunk进行合并
   3. 与其物理相邻的chunk进行后向合并

unlink

/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {                                            \
    FD = P->fd;								      \
    BK = P->bk;								      \
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))		      \
      malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
    else {								      \
        FD->bk = BK;							      \
        BK->fd = FD;							      \
        if (!in_smallbin_range (P->size)				      \
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {		      \
	    if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)	      \
		|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
	      malloc_printerr (check_action,				      \
			       "corrupted double-linked list (not small)",    \
			       P, AV);					      \
            if (FD->fd_nextsize == NULL) {				      \
                if (P->fd_nextsize == P)				      \
                  FD->fd_nextsize = FD->bk_nextsize = FD;		      \
                else {							      \
                    FD->fd_nextsize = P->fd_nextsize;			      \
                    FD->bk_nextsize = P->bk_nextsize;			      \
                    P->fd_nextsize->bk_nextsize = FD;			      \
                    P->bk_nextsize->fd_nextsize = FD;			      \
                  }							      \
              } else {							      \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;		      \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;		      \
              }								      \
          }								      \
      }									      \
}

函数主要是将传入的chunk指针指向的chunk从当前的空闲链表中删除，注意到这里进行了双向链表的完整性检查if (__builtin_expect (FD->bk != P || BK->fd != P, 0))。

如果chunk的大小是largebin的范围内，需要对fd_nextsize,bk_nextsize进行操作，共分为三种情况。

if (FD->fd_nextsize == NULL) {				      \
    if (P->fd_nextsize == P)				      \
      FD->fd_nextsize = FD->bk_nextsize = FD;		      \
    else {							      \
        ...
      }							      \
  } else {							      \
    ...\
  }

第一种情况是largebin链表中仅存在一组相同的chunk，则移除首chunk，将后记chunk的nextsize指向其本身。

if (FD->fd_nextsize == NULL) {				      \
    if (P->fd_nextsize == P)
        ...\
    else {							      \
        FD->fd_nextsize = P->fd_nextsize;			      \
        FD->bk_nextsize = P->bk_nextsize;			      \
        P->fd_nextsize->bk_nextsize = FD;			      \
        P->bk_nextsize->fd_nextsize = FD;			      \
      }							      \
  } else {							      \
    ...
  }

第二种情况则是存在多组不同大小的chunk，需要unlink的chunk大小为多个，则要将首chunk的fd_nextsize,bk_nextsize拷贝到后继chunk中，接着需要将上一个和下一个不同大小的堆块的fd_nextsize,bk_nextsize指向后继chunk。

if (FD->fd_nextsize == NULL){
    ...\
  } else {							      \
    P->fd_nextsize->bk_nextsize = P->bk_nextsize;		      \
    P->bk_nextsize->fd_nextsize = P->fd_nextsize;		      \
  }

第三种情况则是存在多组不同大小的chunk，但是unlink大小的chunk只有一个。此时只需要将上一个和下一个不同大小的chunk的fd_nextsize,bk_nextsize修改即可。

sbrk

sbrk,mmap,munmap函数之后补