最近做题遇到了fastbin合并相关的内容，对于合并时机与合并过程一头雾水，于是结合glibc源码（glibc-2.23）看了看，做个小总结。

fastbin的简单介绍

首先帮助大家快速回顾一下fastbin，直接从走位的文章中搬运了过来。fastbin的chunksize为16到80字节，在内存分配和释放中，fastbin是速度最快的。fastbin的两个特点：
1、fastbin的个数为10个。
2、fastbin由单链表构成，无论是添加还是移除fastchunk，都对链表尾进行操作，采取后入先出算法。fastbinsY数组中每个fastbin元素均指向了该链表的rear end（尾结点），而尾结点通过其fd指针指向前一个结点。
如图所示：

合并时机

fastbin会在以下情况下进行合并（合并是对所有fastbin中的chunk而言）。
malloc：
1、在申请large chunk时。
2、当申请的chunk需要申请新的top chunk时。
free：
3、free的堆块大小大于fastbin中的最大size。（注意这里并不是指当前fastbin中最大chunk的size，而是指fastbin中所定义的最大chunk的size，是一个固定值。）
另外：malloc_consolidate既可以作为fastbin的初始化函数，也可以作为fastbin的合并函数。

第一种情况

截取了malloc中的部分关键代码。其中nb为所申请的chunk的真实大小。

  if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      bin = bin_at (av, idx);

      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;
            }
        }
    }
  else
    {
      idx = largebin_index (nb);
      if (have_fastchunks (av))
        malloc_consolidate (av);
    }

第一个malloc_consolidate (av)的作用是初始化fastbin，在这里跳过。我们聚焦第二个malloc_consolidate (av)。这里首先进行了in_smallbin_range (nb)，判断所申请的大小是否在smallbin所定义的大小中，如果不是，则会对fastbin进行合并。我们来写个小程序验证一下。

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
    void *ptr1,*ptr2,*ptr3,*ptr4;
    ptr1 = malloc(0x20);
    ptr2 = malloc(0x20);
    ptr3 = malloc(0x30);          //avoid merge with top chunk
    strcpy(ptr1,"aaaaaaaa");
    strcpy(ptr2,"bbbbbbbb");
    strcpy(ptr3,"cccccccc");
    free(ptr1);
    free(ptr2);
    ptr4 = malloc(0x500);
}

在free了ptr1与ptr2之后，此时的堆情况：

在malloc了一个large chunk之后，此时的堆情况：

我们发现fastbin已经进行了合并。
这里有人可能觉得这么做太激进了，因为可能在我们申请large chunk的时候根本用不上这些释放的空间，但是首先这能很好的解决碎片化问题，其次程序很少会连续的既使用小堆块，又使用大堆块，因此这种情况发生的并不多。

第二种情况

首先看一下关键代码

use_top:
      /*
         If large enough, split off the chunk bordering the end of memory
         (held in av->top). Note that this is in accord with the best-fit
         search rule.  In effect, av->top is treated as larger (and thus
         less well fitting) than any other available chunk since it can
         be extended to be as large as necessary (up to system
         limitations).

         We require that av->top always exists (i.e., has size >=
         MINSIZE) after initialization, so if it would otherwise be
         exhausted by current request, it is replenished. (The main
         reason for ensuring it exists is that we may need MINSIZE space
         to put in fenceposts in sysmalloc.)
       */

      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;
        }

      /* When we are using atomic ops to free fast chunks we can get
         here for all block sizes.  */
      else if (have_fastchunks (av))
        {
          malloc_consolidate (av);
          /* restore original bin index */
          if (in_smallbin_range (nb))
            idx = smallbin_index (nb);
          else
            idx = largebin_index (nb);
        }

      /*
         Otherwise, relay to handle system-dependent cases
       */
      else
        {
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }

首先判断top chunk的size是否足够我们进行下一次的分配，如果不够，那么判断是否有fastbin的存在，如果存在fastbin，那么则进行合并。然后再去与smallbin和largebin匹配。如果都不匹配，则扩展top chunk。
我们还是通过一个小程序来说明

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
        void *ptr1,*ptr2,*ptr3,*ptr4,*ptr5;
        ptr1 = malloc(0x20);
        ptr2 = malloc(0x20);
        ptr3 = malloc(0x20f00);
        ptr4 = malloc(0x30);          
        strcpy(ptr1,"aaaaaaaa");
        strcpy(ptr2,"bbbbbbbb");
        strcpy(ptr3,"cccccccc");
        free(ptr1);
        free(ptr2);
        ptr5 = malloc(0x70);
}

在malloc(0x70)之前,此时top chunk的size已经小于0x70

此时的堆情况

然后我们再申请一个比较小但是大于top size的堆

此时对fastbin进行了合并。

第三种情况

在free(chunk)的时候，如果chunk的大小大于fastbin中所定义的最大堆块的大小，则进行合并。

    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (have_fastchunks(av))
    malloc_consolidate(av);

这里还是拿小程序进行演示。

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
        void *ptr1,*ptr2,*ptr3,*ptr4;
        ptr1 = malloc(0x70);
        ptr2 = malloc(0x70);
        ptr3 = malloc(0x70);  // avoid merge with top chunk
        ptr4 = malloc(0x100);
        strcpy(ptr1,"aaaaaaaa");
        strcpy(ptr2,"bbbbbbbb");
        strcpy(ptr3,"cccccccc");
        free(ptr1);
        free(ptr2);
        free(ptr4);
}

在free(ptr1),free(ptr2)之后，此时的堆情况

在free(ptr4)以后的堆情况

可以看到fastbin被合并了。这里需要注意由于是合并到了unsortbin中，所以有时我们可以利用这里泄漏出libc基地址。

合并过程

那么fastbin到底是怎么在进行合并的呢？这里我们结合malloc_consolidate函数来分析

static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* current fastbin being consolidated */
  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
  mchunkptr       p;                  /* current chunk being consolidated */
  mchunkptr       nextp;              /* next chunk to consolidate */
  mchunkptr       unsorted_bin;       /* bin header */
  mchunkptr       first_unsorted;     /* chunk to link to */

  /* These have same use as in free() */
  mchunkptr       nextchunk;
  INTERNAL_SIZE_T size;
  INTERNAL_SIZE_T nextsize;
  INTERNAL_SIZE_T prevsize;
  int             nextinuse;
  mchunkptr       bck;
  mchunkptr       fwd;

  /*
    If max_fast is 0, we know that av hasn't
    yet been initialized, in which case do so below
  */

  if (get_max_fast () != 0) {
    (av);

    unsorted_bin = unsorted_chunks(av);

    maxfb = &fastbin (av, NFASTBINS - 1);
    fb = &fastbin (av, 0);
    do {
      p = atomic_exchange_acq (fb, 0);
      if (p != 0) {
    do {
      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);

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

      if (nextchunk != av->top) {
        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);
      }

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

    } while ( (p = nextp) != 0);

      }
    } while (fb++ != maxfb);
  }
  else {
    malloc_init_state(av);
    check_malloc_state(av);
  }
}

大概过程（会循环fastbin中的每一块）：
1、首先将与该块相邻的下一块的PREV_INUSE置为1。
2、如果相邻的上一块未被占用，则合并，再判断相邻的下一块是否被占用，若未被占用，则合并。
3、不管是否完成合并，都会把fastbin或者完成合并以后的bin放到unsortbin中。（如果与top chunk相邻，则合并到top chunk中）这点尤其要注意，这也是为什么可以泄漏出libc基地址的原因。
还是通过小程序来演示：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
    void *ptr1,*ptr2,*ptr3,*ptr4,*ptr5,*ptr6,*ptr7;
    ptr1 = malloc(0x20);
    ptr2 = malloc(0x20);
    ptr3 = malloc(0x20);
    ptr4 = malloc(0x20);
    ptr5 = malloc(0x20);
    ptr6 = malloc(0x100);
    strcpy(ptr1,"aaaaaaaa");
    strcpy(ptr2,"bbbbbbbb");
    strcpy(ptr3,"cccccccc");
    strcpy(ptr4,"dddddddd");
    strcpy(ptr5,"eeeeeeee");
    strcpy(ptr6,"ffffffff");
    free(ptr1);
    free(ptr2);
    free(ptr4);
    free(ptr6);
}

在没有合并之前的堆：

合并之后的堆：

可以发现相邻的fastbin已经进行了合并并放入到unsortbin中，单独的fastbin也放入到了unsortbin中。
fastbin只能和fastbin进行合并吗？显然是否定的，只要相邻的chunk是空闲的，我们就可以将其合并。

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(){
    void *ptr1,*ptr2,*ptr3,*ptr4;
    ptr1 = malloc(0x100);
    ptr2 = malloc(0x20);
    ptr3 = malloc(0x20);
    ptr4 = malloc(0x100);
    strcpy(ptr1,"aaaaaaaa");
    strcpy(ptr2,"bbbbbbbb");
    strcpy(ptr3,"cccccccc");
    free(ptr1);
    free(ptr2);
    free(ptr4);

}

合并前的堆：

合并后的堆：

我们可以看到fastbin已经被合并进了相邻的unsortbin中。

文章到这里就结束了，这是二进制刚入门的新人第一次写文，如果有任何不对的地方，欢迎大家指正。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工 作，每周日13:00-18:00直播授课