malloc和free源码分析

libc2.23 的 malloc 和 free 函数源码分析

我们知道程序它有动态分配内存的操作，Linux 就是靠 malloc 和 free 来实现分配和回收的。

不刻意去说明都是用 64 位系统举例解释的

ptmalloc2 的分配策略

之前写堆概述的时候写过一次了这次粗略概括一下顺便复习了

分配

Linux系统中使用 ptmalloc2 ，在这个分配规则下，不是每一次 malloc 程序都会向系统申请内存。

在第一次 malloc()的时候，它会向操作系统申请 0x21000B(132KB) 的内存（固定值不会变），后续分配都从已经申请的这一大块内存中分割，用完了才会再次向系统申请内存。

那么如何去分割块呢？我们实践时会发现，并不是我们希望获得多少内存程序就分割给我们多少的。每一个被分割的堆块都需要标注它们的信息，例如是否被使用、堆块大小等数据特征，这就导致分割内存块的时候不可避免地要在内存块中额外开出一部分区域用于管理。

同时由于需要保证指针对齐，系统要求每一个堆块都是 SIZE_SZ*2 的整倍数，也就是说 32 位操作系统下的堆块大小必须是 8 的整数倍，64 位必须是 16 的整数倍。

以32位操作系统为例，size 的值必定为 8 的整数倍，二进制角度下看来，低三位永远是0，如果不利用起来的话就有点浪费。

如下图，在 malloc.c 中定义了下面的部分：

规定 size 的低三位不作为实际的 chunk 大小，而是标志位。三个标志位从高位到低位分别是：

1. NON_MAIN_ARENA：是否为主分配，0表示是主分配，权值为4
2. IS_MMAPPED：表示内存是否为 mmap 获得，0表示不是，权值为2
3. PREV_INUSE：表示前面一个内存块是否被使用，0表示不被使用，权值为1

在 64 位操作系统中就是低 4 位，多出一个标志位，但是这个标志位当前无任何意义，但是它同样不作为 chunk的大小。

如果是单单满足 SIZE_SZ*2 的整倍数，那么理论上我们应该是可以分配 0x10 大小的堆块的，但是我们实际运行malloc (0x10) 发现堆块大小是 0x20，这是为什么呢？

接下来我们了解一下chunk结构就能知道，chunk 的结构体有 0x10 个默认被包含在堆块里的必须分配的字节。

回收

目前来看，分配堆块的时候实际上操作很简单，就是从大堆块里面分割一块合适的大小就好了。但是释放以后不能像捏橡皮泥一样再把它放回去。如果我们每一次 free 都不做处理的操作直接丢弃，例如我们一次性申请了很多小的堆块并释放，只有再下次申请同样堆块才会被利用，如果我们不再分配同样的小堆块，这块区域就会被浪费。

这时我们要了解一下 ptmalloc 的又一个策略：尽量合并物理相邻的空闲堆块。就是回收时，可以把相邻的小堆块合并成大堆块。在合并的时候我可能前面会有 free 的内存块，后面也会有 free 的内存块。

那么我怎么在只知道我自身信息的情况下准确找到前后的 chunk 具体在哪呢？

这时需要把 malloc_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;
};

通过 prev_size 位我们不仅可以得知前一个 chunk 有没有被 free ，还可以得知 chunk 的大小。所以在一个 chunk 的结构体内，在 size 之前还会有一个 prev_size 。

在程序使用时，fd、bk 等指针可以给用户写数据，只有被释放的时候才会存储指针数据。

所以 prev_size 和 size 两个数据就占了 0x10 的空间，这也就是最小堆块是 0x20 的原因。

详细的回收处理

bin 就是空闲 chunk 的别名，我们使用链表结构来管理空闲堆块，我们说的 bin 也指代不同的链表表头。

fast bin

0x20~0x80 大小的 chunk，我们会把它扔进 fast bin 。

fast bin 管理 free_chunk 采用单链表方式，并且符合先进后出（FILO）的原则，比如：

p1=malloc(0x10);
p2=malloc(0x10);
free(p1);
free(p2);
p3=malloc(0x10);
p4=malloc(0x10);

最后 p3 的指针是原本指向 p2 的指针，p4 的指针是原本指向 p1的指针。

并且所有 fast bin 之后的 chunk 的 prev_inuse 位永远为 1 ，也就是说它永远被视为在使用中。由于这个位用于合并相邻堆块，所以 fast bin 不会被合并，free 掉的时候是多大就是多大。比如我们当前 fast bin 中只有 0x20 和 0x30 的堆块，我们新申请一个 0x50 的堆块，检查 fastbin 中没有就是没有，不会去合并 0x20 和 0x30 的两个堆块来拼 0x50 ，也不会切割某个堆块。

其他的都会参与切割与合并

unsorted bin

被释放的 free_chunk，经检查不属于 fast bin 之后会被丢进 unsorted bin。

unsorted bin 是双向链表结构，也就是说 unsorted bin 中有两个 ”头指针“ ，我们也把头部的两个 bin 看作 chunk。初始状态时，unsorted bin 中没有空闲 chunk，此时两个 bins 的的 fd 和 bk 都指向自身的 prev_size 。

unsorted bin 中 chunk 大小不一定相等且无序排列。

当需要检查 unsorted bin 的时候，会遍历整个链表，寻找第一个能满足的 chunk 大小切割。当然这中条件的分割也是基于最小 0x20 大小的基础上的。

small bin

small bin 一共有 62 个，它表示的范围就是4*SIZE_SZ~126*SIZE_SZ。

按照不同的大小范围区分成不同的链。当中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index，具体如下：

下标	2	3	4	5	x	63
SIZE_SZ=4（32 位）	16	24	32	40	24x	504
SIZE_SZ=8（64 位）	32	48	64	80	28x	1008

small bins 采用双向链表对 bin 进行管理，每个链表中存储的 chunk 大小都一致。

链表采用 FIFO 的规则，也就是先进先出，所以同一个链表中先被释放的 chunk 会先被分配出去。

large bin

large bin 一共有 63 个，从 small bin 最小不能表示的 chunk 开始，大到无穷。

large bin 从 128*SIZE_SZ 开始。那么下标为0的large bin表示的范围就是128*SIZE_SZ~144*SIZE_SZ(左闭右开)，同理下标为1的large bin表示的范围就是144*SIZE_SZ~160*SIZE_SZ，以此类推，等到32的时候就在原来的基础上加32*SIZE_SZ作为右开区间

它同样以二维双向链表进行管理，相同大小的 chunk 用 fd 和 bk 指针相连；不同大小的 chunk，用 fd_nextsize 和 bk_nextsize 指针连接。沿着 fd_nextsize 指针，chunk 大小递增。

大概结构如下图：

（省略了部分指针）

具体分配细节

malloc() 会对用户请求的size进行处理，来申请同时满足 SIZE_SZ*2 的整数倍，包含 0x10 的固定数据区域且大小最小的堆块。

在一些特殊情况下，并不是我们申请多大的堆块，就有多少区域来供我们向上写数据。

一个 size=0x20 的 chunk 中，0x20 字节分别为 prev_size，size，fd 和 bk。

prev_size 和 size 都不允许写，但是我们可以写 fd 和 bk ，以及下一个块的 prev_size 。所以size=0x20，我们可以写的数据段为 0x18 。

所以当我请求的内存小于等于 0x18 的时候，系统就会给我们 size=0x20 的 chunk 。一旦多了就会以 0x10( 2*SIZE_SZ) 为单位向上加直到满足条件。

计算好大小之后就进入分配环节，系统搜寻堆块的顺序是： fast bin -> small bin -> large bin -> unsorted bin

fast bin 、small bin 和large bin 在搜寻阶段都不进行合并和分割处理。如果在前三个bins中都没有找到合适的堆块，unsorted bin 会找第一个能满足的 chunk 并返回或者切割之后返回。如果切割之后剩余的部分小于 MINSIZE ，那么则不会切割整个返回。

unsorted bin 中每遍历一个不满足要求的 free_chunk 就会把这个堆块放进对应的 small bin 或者large bin当中。

源码分析

下载源码，还挺慢的就是说

我的环境是 ubuntu16.04

sudo apt-get install glibc-source 
sudo apt-get install libc6-dbg 
sudo tar xf /usr/src/glibc/glibc-2.23.tar.xz

之前我还在想为啥网上分析源码的都是一段一段的，没想到这个 malloc 它这么大个文件夹😶‍🌫️

malloc

在 glibc 内部，malloc() 函数就是 __libc_malloc() 函数，而 __libc_malloc() 函数的主要工作是_int_malloc() 完成的。

__libc_malloc

对应的在代码里加注释分析一下：

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
  
  //读取malloc_hook，若 malloc_hook 被设置，则直接调用
  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 函数，函数获取一个可用的分配区
  arena_get (ar_ptr, bytes);
    
  //这里！!调用了 _int_malloc()
  victim = _int_malloc (ar_ptr, bytes);
    
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  //可以理解为一个错误检验？如果 chunk 为空，但分配区指针不为空，再次调用 _int_malloc 获取
  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);
  //对分配的chunk 指针进行地址检查
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

assert 命令如果失败，即代表存在错误，会触发对应的异常，通常导致程序终止并打印出错误消息，以帮助定位和修复问题。

根据函数内容我们可以看出，在 malloc 时，会先检查 malloc_hook 所指向的区域。

我们就有一个利用思路是，修改 malloc_hook 为我们的 gadget ，修改后再次调用 malloc 就会执行 gadget 从而 getshell 。

_int_malloc

__libc_malloc 是通过调用 _int_malloc 来执行分配堆的操作的

static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its size */

  unsigned int block;               /* bit map traverser */
  unsigned int bit;                 /* bit map traverser */
  unsigned int map;                 /* current word of binmap */

  mchunkptr fwd;                    /* misc temp for linking */
  mchunkptr bck;                    /* misc temp for linking */

  const char *errstr = NULL;

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

省略掉一开始定义的一大堆变量，malloc 的第一步就是调用 checked_request2size() 设置 size。

checked_request2size() 函数就是用来查找最小的满足条件的 size 我就不复制了🤪

注意一系列的宏定义：

• __glibc_unlikely(exp) ：表示 exp 很可能为假
• __glibc_likely(exp) ：表示 exp 很可能为真
• __builtin_expect(exp,value) ：表示 exp==value 大概率成立

最后这一小节的意思就是如果没有可以分配的区域，那就调用 sys_malloc 系统调用去用 mmap 分配新的堆区。

fastbin

接下来函数就进入 fastbin 部分去查找可以利用的堆块

//检查堆块大小是否属于 fastbin
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      // 根据 nb 也就是前面返回的 size 获取 fastbins 数组的下标
      idx = fastbin_index (nb);
      // 得到链表头指针
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp = *fb;
      // 如果当前链表存在 chunk，则分配该链表的第一个 chunk
      do
        {
          victim = pp;
          //如果 victim==NULL 也就是 fastbin 链表中没有 chunk，直接 break 跳出 fastbin 的查找
          if (victim == NULL)
            break;
        }
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
             != victim);
      // 如果bin中有 chunk，检查所分配的 chunk 的 size 与所在链表的 size 是否匹配
      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);
          //根据 chunk 得到用户数据指针 p,并返回
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

补充一下这部分用到的宏定义：

#define get_max_fast() global_max_fast
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

其中末尾有调用到 check_remalloced_chunk 函数，函数具体内容如下：

static void
do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
  INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);

  //检查分配的块是否在内存堆 mmap 区域中
  if (!chunk_is_mmapped (p))
    {
      assert (av == arena_for_chunk (p));
      if (chunk_non_main_arena (p))
        assert (av != &main_arena);
      else
        assert (av == &main_arena);
    }
  //检查 prev_inuse 那三个标志位
  do_check_inuse_chunk (av, p);

  /* Legal size ... */
  //检查分配块的大小是否大于最小的有效大小（MINSIZE） 
  assert ((sz & MALLOC_ALIGN_MASK) == 0);
  assert ((unsigned long) (sz) >= MINSIZE);
  /* ... and alignment */
  assert (aligned_OK (chunk2mem (p)));
  /* chunk is less than MINSIZE more than request */
  //确保分配的块大小是否是满足申请的 size 条件的最小 size 
  assert ((long) (sz) - (long) (s) >= 0);
  assert ((long) (sz) - (long) (s + MINSIZE) < 0);
}

就是在检查分配的 chunk 的各个标志位双重保险确保分配的 chunk 是正确的。

smallbin

如果在 fastbin 中找不到就会进入到 smallbin

if (in_smallbin_range (nb))
    {
      //查找对应大小的 bin 下标
      idx = smallbin_index (nb);
      // 得到 small bin 的链表头地址
      bin = bin_at (av, idx);
      //// 这里会获取 small bin 的最后一个 chunk，如果 victim = bin，说明 small bin 是空的
      if ((victim = last (bin)) != bin)
        {
          if (victim == 0) /* initialization check */
            malloc_consolidate (av);
          else
            {
              // 获取 small bin 的倒数第二个 chunk，因为双向链表所以其实就是倒数第一个 chunk
              bck = victim->bk;
                // 检查倒数第二个 chunk 的 fd 指针是否指向最后一个 chunk
				if (__glibc_unlikely (bck->fd != victim))
                {
                  errstr = "malloc(): smallbin double linked list corrupted";
                  goto errout;
                }
              // 设置 victim 的下一个 chunk 的 inuse 位
              set_inuse_bit_at_offset (victim, nb);
              // 将最后一个 chunk 从 smallbin 中取出，重新设置链中的指针
              bin->bk = bck;
              bck->fd = bin;

              //如果不是主线程则要设置 A 标志位
              if (av != &main_arena)
                victim->size |= NON_MAIN_ARENA;
              //检查检查！
              check_malloced_chunk (av, victim, nb);
              //根据 chunk 得到用户数据指针 p,并返回
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }
    }

宏定义们：

#define NBINS             128
#define NSMALLBINS         64
#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)
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                  \
             - offsetof (struct malloc_chunk, fd))
#define first(b)     ((b)->fd)
#define last(b)      ((b)->bk)

在这一部分中，程序会首先用 last (bin)) != bin 检查符合目标大小的 smallbin 链是否为空。

但是考虑到一种情况是没初始化。当 small bin 没有初始化时，所有指针均为空，也就是紧接着检查的 victim == 0 。那就进行初始化操作调用 malloc_consolidate() 函数。

这个函数超级长，大概实现的功能是先判断堆是否被初始化。

如果已经被初始化了就把所有的 fast bin 取出来，先清除它们的标志位，然后扔到 unsorted bin 中尝试向前合并或者向后合并；如果没有初始化就调用 malloc_init_state 和 check_malloc_state 函数初始化堆。

其实如果 victim == 0 它一定是没有初始化的，所以合并 fastbin 那一部分很少执行到。可以理解为在这里这个函数就是用来初始化 arena 的。

largebin

如果不在 smallbin 里就会去查找 largebin 辣

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

短短三行，极简

先获取 largebin 对应的 index，然后如果 fastbin 不为空，调用 malloc_consolidate 。

因为 largebin 都已经存在了肯定已经初始化，实际上这里的函数作用是就只是合并 fast bin，但并不再 largebin 中寻找堆块。

之前不是提到说 fast bin 通常不会参与合并与分割嘛，但这就是个例外。举个例子：

我们想要申请一块 0x510 的堆块，同时内存区域中，有一块 0x20 的 fast bin 与一块 0x500 的 large bin 相邻。我们合并这两个堆块就能正好满足把一个 0x520 的 large bin 返回给用户。如果不合并的话就得重新切割 top_chunk 了，造成了空间浪费。

unsortedbin 和 largebin

unsortedbin 部分，也可能是 smallbin，也可能是 largebins

for (;; )
    {
      int iters = 0;
      // 检查 unsortedbin 是否为空，不为空就继续
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;
          // 判断当前申请的 size 是否合法
          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
          size = chunksize (victim);

这里的 while 循环就是开始遍历 unsorted chunk 了。

    //如果申请的大小在 smallbin 的范围中，且 unsortedbin 链表中只有一个 chunk 并指向 last_remainder，且该 chunk 的 size 大小大于用户申请的 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 */
        //拆分 chunk，更新last_remainder 的大小和开始地址
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
        //切割出剩下的 chunk 作为新的 av->last_remainder
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks (av);
        // 如果 remainder_size 的大小不属于 smallbin，则需要设置 nextsize 为空，后面会把它丢到 unsortedbin 中
        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;
      }

这段代码最开始的判断详细拆分一下就是：

• in_smallbin_range (nb) ：申请的大小在 small bin 的范围中
• bck == unsorted_chunks (av) ：unsorted bin 中只有一个 chunk 。
• victim == av->last_remainder：这个 chunk 刚好是最近被分割过的剩余部分。
• (unsigned long) (size) > (unsigned long) (nb + MINSIZE))：找到的这个 chunk的 size 大于需要的最小块大小+ MINSIZE 。

/* remove from unsorted list */
//如果上一个条件满足就是 chunk 要被分配出去了所以要把这个 chunk 从 unsortedbin 中解除
//因为这个指令在 if 外所以不满足也会拿出最后一个 chunk
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

前一个 if 条件不满足就到这里了

/* Take now instead of binning if exact fit */
//如果当前用户申请的size刚好与解链的chunk大小相同，则返回
      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;
        }

如果取出的这个 chunk 的 size 刚好等于这个 nb ，那就说明这个块一定是最合适的，就直接返回。如果不合适进入下面的部分：

//判断取出的这个 chunk 的 size 属不属于 smallbin
if (in_smallbin_range (size))
        {
          //将该chunk插入small bin中
          victim_index = smallbin_index (size);
          bck = bin_at (av, victim_index);
          fwd = bck->fd;
        }
 else
        {
          //不是的话插入 largebin
          victim_index = largebin_index (size);
          bck = bin_at (av, victim_index);
          fwd = bck->fd;

属于 smallbin 就丢进 smallbin，如果不属于就丢进 largebin 了。

这部分代码最开始开始的判断大小然后丢进 largebin、smallbin 的部分，就是我们前面说分配规则的时候提到的把 unsortedbin 中的堆块分类的实现。

我们丢进large bin 之后要设置相应的指针。large bin 中一个 chunk 有四个指针，每对链表头 bin 都管理一个二维双向链表，fd、bk 指针与相同大小的 chunk 连接，fd_nextsize 和 bk_nextsize 与不同大小的 chunk 连接。

   /* maintain large bins in sorted order */
         //这里的 bck 指的是表头 bin 所在的 chunk，fwd 指的是最大的 chunk。
//检测 largebin 是否非空
         if (fwd != bck)
           {
             /* Or with inuse bit to speed comparisons */
             //去除 P标志位
             size |= PREV_INUSE;
             /* if smaller than smallest, bypass loop below */
             //检查A标志位
             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;
                 fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
               }
             else
               {
                 assert ((fwd->size & NON_MAIN_ARENA) == 0);
                 while ((unsigned long) size < fwd->size)
                   {
                     fwd = fwd->fd_nextsize;
                     assert ((fwd->size & NON_MAIN_ARENA) == 0);
                   }

                 if ((unsigned long) size == (unsigned long) fwd->size)
                   /* 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;
                   }
                 bck = fwd->bk;
               }
           }
         //如果 largebin 为空，那么直接加入链表就行
         else
           victim->fd_nextsize = victim->bk_nextsize = victim;
       }

我们向一个空的 largebin 中插入 chunk 的流程大致如下：

fwd=bin->fd;
bck=bin->bk;
victim->bk_nextsize=bck;
victim->fd_nextsize=fwd;
fwd->bk_nextsize=bck->fd_nextsize=victim;

非空也一样，就是把 bin 的指针换成对应的前后 chunk 的指针。

中间没有注释的长长的一部分都是在查找合适的位置插入，然后修改指针。如果在当前的 largebin 中找到了 size 等于我们取出的 chunk 的堆块 size 的堆块，就只需要修改 fd 和 bk 指针；其他情况还需要修改 fd_nextsize 和 bk_nextsize 指针。

前面找到了插入的位置，接下来就是插入操作：

		  mark_bin (av, victim_index);
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;

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

上面对 unsortedbin 的遍历比较长，每一次便利的流程大概流程就是：

查找 unsortedbin 是否为空。不为空，且只有一个 chunk 且为 last_remainder 时，进行 last_remainder 切分后直接返回；如果有多个 chunk ，则需要将 chunk 从 unsortedbin 中解链，如果大小满足则返回，

如果chunk大小不满足，进行判断对应丢进 smallbin 或 largebin 。

注意，当取得 unsorted bin chunk 与我们申请的 chunk 大小相同时，程序进行了如下操作：

/* remove from unsorted list */
//将当前的chunk从unsortedbin 链表里解除
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);

据此我们可以发现另外一种利用方法，控制 av 的 bk 指针，那么就能向 bk 的 fd 指针写入 av 的值，发生 unsortedbin attack。

我们之前不是遍历 unsortedbin 又整理了一下 largebin 和 smallbin 嘛，如果在 unsortebin 里面没找到合适的就会再去查找一遍请求 size 对应的 bin 中的 chunk 。

   //确认用户申请的 chunk 大小不属于 smallbin
if (!in_smallbin_range (nb))
     {
       bin = bin_at (av, idx);

       /* skip scan if empty or largest chunk is too small */
       //如果 largebin 不为空，用户请求的 size 小于 large bin 中最大的 chunk size
       if ((victim = first (bin)) != bin &&
           (unsigned long) (victim->size) >= (unsigned long) (nb))
         {
           //while 循环获取刚好小于用户请求的 size 的 large bin
           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;

           //拆分符合要求的 large chunk
           remainder_size = size - nb;
           //将large chunk从 largebin 中解链
           unlink (av, victim, bck, fwd);

           /* Exhaust */
           //处理切分下来的剩余部分，如果切割下来的部分小于 MINSIZE 那就不切割了
           if (remainder_size < MINSIZE)
             {
               //把它物理相邻的下一个快prev_inuse位设1
               set_inuse_bit_at_offset (victim, size);
               if (av != &main_arena)
                 victim->size |= NON_MAIN_ARENA;
             }
           /* Split */
           else
             {
               //将切割的剩余部分插入 unsortedbin 中
               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;
               // remainder 不满足 small bin
               if (!in_smallbin_range (remainder_size))
                 {
                   //清空它的fd_nextsize和bk_nextsize
                   remainder->fd_nextsize = NULL;
                   remainder->bk_nextsize = NULL;
                 }
               // 设置分配的 chunk 堆头
               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;
         }
     }

在寻找时不是有说要找最小能满足的大小的块嘛，代码中 nb 是指用户需要的最小能满足的块的 size ，实际上并不是所有情况下都满足 size=nb 。例如：我们申请 0x1 大小的堆块，那就只能给它一个 0x20 的 chunk。或者 我们现在甚至没有 0x20 的块，但是有一个 0x30 的，那么这个 0x30 的 chunk 就是我们要寻找的堆块。

在处理切割下来的堆块时，它只检测了了 unsorted bin->fd->bk 是否等于那个 unsorted bin ，对于堆块来说就是只检测了 bk 指针。这是一个利用小技巧，也就是说这时我们可以修改 fd 指针为期望的值，不会在这里被检测到，就是 unsorted bin attack 了。

被切割的剩下 chunk 会被放在 unsortedbin ，但是程序仍然会检测它是不是在 small bin 的范围里。如果不在 small bin 范围内，就会清空它的 fd_nextsize 和 bk_nextsize 。因为它要回到 unsorted bin ，这两个字段就没什么用了，就会被清空。

如果当前的 large bin 中没有符合要求的 chunk，则在其它 size 的 large bin 中进行查找。首先需要看一下这个 binmap 结构：

++idx;
   bin = bin_at (av, idx);
   block = idx2block (idx);
   map = av->binmap[block];
   bit = idx2bit (idx);

这个结构用于快速检索一个 bin 是否为空，每一个 bit 表示对应的 bin 中是否存在空闲 chunk 。这一段就是说，如果 large bin 搜索完了都没有找到合适的 chunk ，那么就去下一个 idx 里面寻找。然后一共有4个 int ，每个 int 32位表示一块 map ，一共表示 128 位。

这段代码的执行流程就是：利用 idx 索引值来获取指向对应 bin 的指针。然后根据这个 bin 指针来获取

for (;; )
     {
       /* Skip rest of block if there are no more set bits in this block.  */
       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;
         }

两个判断条件：

• bit>map：如果这个位的权值都比它整个的 map 都大了，说明 map 上那个 bit 的权值必定为0
• bit==0：如果这个 bit 都是 0 说明这个 index 也不对。

两个条件只要满足其一就是没有空闲堆块，接着去查看下一个 index。

接下来的判断如果 map==0 ，说明这整个 block 都没有空闲块，就直接跳过，不为 0 则退出去执行下面的操作，如果超过了 block 的总数，那就说明 unsorted bin 和 large bin 中也没有合适的chunk，那我们就切割top_chunk了，这里用了一个 goto use_top; 跳转，在后面会分析到。

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

经过上面的流程，我们已经找到了合适的 block ，接下来就是寻找 block 的各个位了。从低位开始，如果检查到map那一位对应为0就找下一位，我们前面提到 bk 为 large bin 的最小块，所以先从它开始，也就是先执行 bin = next_bin (bin); 。

当然不能说 map 里面说这里有它就有，我还得自己判断一下这个bin里面是不是真的有，如果没有就要及时把标志位清除然后 bit<<1 去寻找下一个 index 。

找到合适的 large bin 的索引，我们就可以从中找合适的堆块，流程和上面一样：

 // 找到第一个大于申请 size 的 chunk 进行堆块划分
       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)
             {
               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 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;
         }
     }

Topchunk

如果在 large bin 中没有找到响应的 chunk，则需要在 top chunk 中查找

use_top:

	  //从 av->top 拿到 top_chunk 的地址
      victim = av->top;
	  //判断大小
      size = chunksize (victim);
	  //如果大小符合切割要求，就按照之前的流程切割并把 chunk 返回用户
      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.  */
	  //如果大小不满足需要，就先合并所有的 fastbin，接着执行之前的循环
      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
       */
	  //调用 sysmalloc 去分配新一页内存
      else
        {
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }
    }
}

需要注意程序会反复查找当前内存区域是否有合适的内存，如果实在没有才会去调用 sysmalloc。一次还是分配0x21000 的 chunk 作为新的 top_chunk ，原来的 top_chunk 将会被 free 。

如果我们没有改过 top_chunk 的 size ，那么新的和旧的 top_chunk 将会是物理相邻，如果 free 的top_chunk 不在 fast bin 范围内，那就会和新的 top_chunk 发生合并。

总结

malloc() 函数被调用时主要流程如下：

1. 检查是否设置了 malloc_hook ，若设置了则跳转进入 malloc_hook，若未设置则获取当前的分配区，进入int_malloc() 。
2. 如果当前的分配区为空，则调用 sysmalloc 分配空间，返回指向新 chunk 的指针，否则进入下一步。
3. 若用户申请的大小在 fast bin 的范围内，则考虑寻找对应 size 的 fastbin chunk ，如果这个对应 size 的 fastbin 中有满足的堆块就返回给用户，如果没有就进入下一步。
4. 如果用户申请的 size 符合 small bin 的范围，则在相应大小的链表中寻找 chunk 。若 small bin 未初始化，则调用 malloc_consolidate 初始化分配器，然后继续下面的步骤；如果已经初始化了，就寻找对应的 small bin 的链表，如果该 size 的 small bin 又满足的堆块就取出返回，否则继续下面的步骤。如果申请的不在 small bin 的范围，那么调用 malloc_consolidate 函数去合并所有 fastbin 并进入下一步。
5. 如果在上面的流程中都没有找到对应的块，会遍历 fast bins 中的 chunk，将相邻的 chunk 进行合并， 并链接到 unsorted bin 中。
6. 如果用户申请的大小符合 large bin 或 small bin 链表为空，完成了上一步之后，就会开始遍历处理 unsorted bin 链表中的 chunk 。如果 unsorted bin 只 有一个 chunk，这个 chunk 在上次分配时被使用过，且所需分配的 chunk 大 小属于 small bin，同时这个 chunk 的 size 大于等于需要分配的大小。这种情况下就直接将该 chunk 进行切割；否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历完成后，转入下一步。
7. 上面的步骤执行结束还没有找到堆块，就说明需要分配的是一块大的内存，或者 small bin 和 unsorted bin 中都找不到合适的 chunk，并且 fast bin 和 unsorted bin 中所有的 chunk 都清除干净了。程序就来时从 large bins 中按照 “smallest-first，best-fit” 的原则，找一个合适的 chunk，从中划分一块所需大小的 chunk，并将剩下的部分链接回到 bins 中。若操作成功，则分配结束，否则转到下一步。
8. 根据 binmap 找到表示更大 size 的 large bin 链表，若其中存在空闲的 chunk ，则将 chunk 拆分之后返回符合要求的部分，并更新 last_remainder。如果没有合适的堆块就进入下一步去 top chunk 中寻找。
9. 若top_chunk的大小大于用户申请的空间的大小，则将top_chunk拆分，返回符合用户要求的chunk，并更新last_remainder 。否则将再一次检查 fast bin，如果 fast bin 不为空，就调用 malloc_consolidate() 合并堆块后再次从第 4 步开始重新查找。
10. 如果前面的步骤中都没有找到合适的 chunk ，才会调用 sysmalloc() 重新分配空间并处理原本的 top chunk 。

free

__libc_free

一开始还以为 free 没有 malloc这么长了呢

free 函数也是由 __libc_free 函数完成 chunk 的释放的操作的。

__libc_free (void *mem)
{
  mstate ar_ptr;
  mchunkptr p;                          /* chunk corresponding to mem */
  // 判断是否设置了 free_hook
  void (*hook) (void *, const void *)
    = atomic_forced_read (__free_hook);
  if (__builtin_expect (hook != NULL, 0))
    {
      // 如果设置了就调用 free_hook
      (*hook)(mem, RETURN_ADDRESS (0));
      return;
    }

  //free(NULL) 无任何意义，直接返回
  if (mem == 0)                              /* free(0) has no effect */
    return;
    
  // 将用户提供的 mem 指针转换为堆块头指针
  p = mem2chunk (mem);

  // 判断 chunk 是否由 mmap 分配
  if (chunk_is_mmapped (p))                       /* release mmapped memory. */
    {
      /* see if the dynamic brk/mmap threshold needs adjusting */
      // 如果是 mmap 分配的，则首先更新 mmap 分配和收缩阈值
      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;
    }
    
  // 如果不是 mmap 创建，则调用 _int_free 函数
  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);
}

跟 malloc 一样，函数会先读取 __free_hook 看看是否为空，如果不为空则直接由 free_hook 指向的函数代为执行 free ，这里也是我们经常劫持的钩子函数。

free_hook 劫持起来比 malloc_hook 困难，但是一旦劫持成功也会很方便。 malloc_hook 函数我们只能写 one_gadget ，而一旦条件苛刻那么就还得调栈啊之类的一些操作。如果劫持到了 free_hook 我们就可以直接写 system() 函数，然后 free 一个内容为 '/bin/sh' 的堆块就能 get shell。

_int_free

static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr *fb;             /* associated fastbin */
  mchunkptr nextchunk;         /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int nextinuse;               /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr bck;               /* misc temp for linking */
  mchunkptr fwd;               /* misc temp for linking */

  const char *errstr = NULL;
  int locked = 0;

  size = chunksize (p);

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

首先是各种各样的参数定义和错误检查。我把注释删掉了，注释的意思大概就是要检查用户是不是设置了恶意参数。

• __builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)：指针和size进行比较，不理解但尊重。也就是大概 p>0xfff.... ，主要是应该要检测被 free 的 chunk 的 size 不要过大。size 取负之后会变得很大，比如 0xfff... 这样的大数值通常指针不会指向这样的地址，f 开头的一般都是内核地址。
• __builtin_expect (misaligned_chunk (p), 0)：计算 chunk 的指针与上掩码（ 0x10-1也就是 0xf ），取出后四位观察是否为 0 。如果不为 0 则说明指针错误了，就会报错。这里主要是检查对齐，指针需要指到 0x10 的整倍数才能被正常 free 。

 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
  {
    errstr = "free(): invalid size";
    goto errout;
  }

check_inuse_chunk(av, p);

接下来又是在检查：

• size < MINSIZE：如果 size 还比 MINSIZE 要小，那肯定 size 错了。
• !aligned_OK (size)：chunk size 也要对齐，但是这个 check 一般不会被触发，因为再取出 chunk size 的时候就会把最低位与掉。

然后就是和 malloc 里相同的 check 来检查 inuse 位。

fast bin

接下来就是判断这个被 free 的 chunk 是不是在 fastbin 范围内了

//判断这个 chunk 的大小是不是属于 fastbin ，且其后一个 chunk 不是 topchunk
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    //判断 size 是否小于 MINSIZE 或者是 size>=system_mem
    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))
      {
	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;
	  }
      }

上面的代码检查 size 大小，如果大小有问题就用分配器的 lock 再次做一个判断，如果判断条件还是成立的话那就说明 size 真的被改成了非法数值，那就报错退出。如果进来了但是没有执行报错，说明可能多线程有点问题，就释放这个 arena 的锁。

检查完毕就开始释放这个 chunk：

   //清理 fastbin 中的数据
   free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
   
//初始化 fastbin
   set_fastchunks(av);
// 获取 size 对应的 fastbin 下标
   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;
   do
     {
   
   // 判断当前 fastbin 头 chunk 与要被释放的 chunk 是否相同（防止 double free）
   if (__builtin_expect (old == p, 0))
     {
       errstr = "double free or corruption (fasttop)";
       goto errout;
     }
       
   // 将要被释放的 chunk 放入 fastbin 头部，修改其 fd 指针指向 old
   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;
     }
 }

它首先调用了 一个 free_perturb() 函数，函数内容如下：

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

其实跟前面 malloc 那个函数差不多，就是看你有没有设置那个值，如果设置了就在 free 之前把堆块进行 memset 清空，但是不一样的是，perturb 中 memset 第二个参数是要根据你设置的值再异或一个 0xff 的。

其中有一个检查时针对 double free 的，那么如果真的 double free 了是什么样的呢？

我们 free(A) ，第一次 free A，对应的 bin 为空，这个 chunk 链入其中，现在 fast bin 中多了一个 A 。接下来我们第二次 free(A) ，A 会再次被加入 fast bin 中，然后会导致产生一个自己指向自己的指针。这时 fast bin中的情况就是两个A，A->A。此时我们再申请一个和 A 一样大的 chunk ，A 被申请走，但是fast bin 链中还剩下一个 A，但是此时我们手里有一个 A ，fast bin 中也有一个 A 。

这样我们就可以直接编辑 A 的指针域了。比如我让它指向了 got 表中的 free() 函数。那么此时 fast bin 中的情况就是 A->free@got 。然后我再次申请和 A 一样大小的 chunk ，A 被取出来， fast bin 中剩下free@got 。那么我第三次申请就得到了在 free@got 那边的 chunk ，然后假如我偷偷修改一下 free@got 为 system() ，那就能 get shell 了。同时我们可以看到，free@got 这个指针是能任意编辑的，也就是说我想申请到哪都不是问题，这样就能任意地址写了。

我们也有方法来绕过 double free 检查。因为对于 double free 的检查只有这里一处，我们就可以先 free(A) 再 free(B)，再 free(A) ，这样就造成 double free 啦！

如果过了检测，就将这个 chunk 链在 fast bin 的顶部，就是一个普通的单链表的插入。因为后进先出，所以只在 fast bin 的一端插入删除。

unsortedbin

它一共就三个大的 if-else 分支条件，是不是属于 large bin 、是不是属于 mmap 分配，和其他情况，也就是 unsorted bin 。

如果chunk是 mmap 分配的话那就调用 munmap_chunk() 函数去 free 这个 chunk。这部分代码就在 _int_free 函数的最后，我们不去讨论这部分具体的代码实现

else {
    munmap_chunk (p);
  }

接下来我们就来分析 unsorted bin：

 else if (!chunk_is_mmapped(p)) {
   if (! have_lock) {
     //用一个分配器的时候先加锁，用完了释放
     (void)mutex_lock(&av->mutex);
     locked = 1;
   }

   // 获取 next_chunk
   nextchunk = chunk_at_offset(p, size);

   /* Lightweight tests: check whether the block is already the
      top block.  */
   // 检查当前 chunk 是否是 top chunk 头（防止 double free）
   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.  */
   // 判断 next chunk 是否超过分配区
   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.  */
   // 检查 next chunk 的 inuse 位，判断被释放的 chunk 是否在使用 
   if (__glibc_unlikely (!prev_inuse(nextchunk)))
     {
errstr = "double free or corruption (!prev)";
goto errout;
     }

   // 判断 next chunk 的 size 是否合法
   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 的内容
   free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

上面的部分就是对堆块的各种检查，保证 free 这个堆块不会发生错误。其中 nextchunk->size <= 2 * SIZE_SZ的检查，也就是如果下一个 chunk 的 size 小于 MINSIZE 也会报错， 因为会涉及到 chunk 的向前合并或者向后合并，因此需要对前后堆块都进行检查。

下面就是向前和向后合并堆块大小的操作

   /* consolidate backward */
   // 如果前一个 prev chunk 也处于释放状态，则用 unlink 合并两个 chunk
   if (!prev_inuse(p)) {
     prevsize = p->prev_size;
     size += prevsize;
     p = chunk_at_offset(p, -((long) prevsize));
     unlink(av, p, bck, fwd);
   }

   // 如果 next chunk 不是 top chunk
   if (nextchunk != av->top) {
     /* get and clear inuse bit */
     nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

     /* consolidate forward */
     // 如果 next chunk 也处于释放中，则继续向下合并 next chunk
     if (!nextinuse) {
unlink(av, nextchunk, bck, fwd);
size += nextsize;
     } else
   // 清除 inuse 位
clear_inuse_bit_at_offset(nextchunk, 0);

     // 获取当前 unsortedbin 的末尾 chunk 和链表头 chunk
     bck = unsorted_chunks(av);
     fwd = bck->fd;
     if (__glibc_unlikely (fwd->bk != bck))
{
  errstr = "free(): corrupted unsorted chunks";
  goto errout;
}
     // 将当前 chunk 插入 unsortedbin 中
     p->fd = fwd;
     p->bk = bck;
     // 如果 size 不属于 small bin，需要设置 large bin
     if (!in_smallbin_range(size))
{
  p->fd_nextsize = NULL;
  p->bk_nextsize = NULL;
}
     // 更新链表头尾指针
     bck->fd = p;
     fwd->bk = p;

     // 设置 chunk 的头部和尾部 prev_size
     set_head(p, size | PREV_INUSE);
     set_foot(p, size);

     check_free_chunk(av, p);
   }

   // 如果当前 chunk 临近 top chunk，则直接合并到 top chunk
   else {
     size += nextsize;
     set_head(p, size | PREV_INUSE);
     av->top = p;
     check_chunk(av, p);
   }

下面就是一个比较特殊的情况，就是我们如果一下子回收一个 0x10000B 这么大的空间，会回收给系统，这样可以减少资源占用。

    // 如果前面释放的 chunk 大小较大，将 fast bin 合并到 unsortedbin 中
    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (have_fastchunks(av))
	malloc_consolidate(av);

      // 如果进程的分配区是主分配区，调用 systrim 收缩内存，否则获取非主分配区的 heap_info，用 heap_trim 收缩 heap
      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);
    }
  }

先调用 malloc_consolidate 合并所有 fast bin 。如果进程所在的分配区是主分配区并且可以收缩内存的话，就调用 systrim 收缩内存，否则就获得非主分配区的 heap_info 指针，调用 heap_trim 收缩 heap 。

总结

free不像 malloc 那么复杂，大致上就是属于 fast bin 的直接加入对应链表，不属于 fast bin 的向前合并或者向后合并然后加入 unsorted bin 。如果一次free太多的空间有可能会被操作系统回收。

---

这里有对 ptmalloc2 的相关代码的分析：Glibc内存管理 (seebug.org)

这个前半部分的理论讲的比较细，源码分析部分就比较粗略了

碎碎念：

计算机发明者和计算机各种语言各种库的发明者好牛，他们的脑子和我的好像是不太一样的🥹