glibc源码分析-malloc-free

相关结构体

malloc_state

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

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

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* 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_chunk

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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;
};

初次创建堆

非mmap

源程序

#include <stdlib.h>

int main(int argc, char **argv){
	malloc(0x30);
	return 0;
}	

运行过程

• 进入__libc_malloc

• 调用__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));

  • 程序第一次运行__libc_malloc 时，__malloc_hook中的值是hook.c中的malloc_hook_ini函数，因此会调用该函数，用于对__malloc_hook进行初始化，初始化结束后值为0，后续再创建堆就是默认值0

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

  • 初始化过程：设置__malloc_hook为NULL，再调用arena.c中的ptmalloc_init进行初始化，__malloc_initialized > 0 表示初始化完成

  • 补充：__builtin_expect

    • 作用：允许程序员将最有可能执行的分支告诉编译器

    • 写法：__builtin_expect(EXP, N)

    • 含义：EXP==N的概率很大

    • 返回值：当EXP==N时返回0，反之返回1

      #define unlikely(x) __builtin_expect(!!(x), 0) //x很可能为假
      #define likely(x) __builtin_expect(!!(x), 1) //x很可能为真

      //if成立的条件是hook != NULL成立，即hook不为空，则去调用hook中的函数
      if (__builtin_expect (hook != NULL, 0))

• 调用arena_get 获取到管理空闲空间的分配区地址，申请的堆块就在这里

  arena_get (ar_ptr, bytes);

• 进入_int_malloc函数

  victim = _int_malloc (ar_ptr, bytes);

  victim指向_int_malloc分配的内存

• 计算分配的实际大小

  checked_request2size (bytes, nb);

  ptmalloc 以 chunk 为单位分配空间，传入的bytes 是用户提交的原始的空间大小

  nb 是为计算得到的 chunk 的大小

• 检查是否有可用空间

  if (__glibc_unlikely (av == NULL))

  av = ar_ptr 是arena_get 获取到的分配区地址指针

• 判断是否属于fastbin

  • 通过判断nb <= get_max_fast()即申请的实际大小是否小于fastbin最大值来判断是否属于fastbin

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

    属于fastbin则继续运行

  • 获取实际大小nb所在的fastbin链表的index，并且获取指向该链表的第一个结点的指针

    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx);
    mchunkptr pp = *fb;

  • 判断指向的chunk是否为空

    do
    	{
         	victim = pp;
            if (victim == NULL)
            	break;
    	}while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))

    该 chunk 为空，说明当前 fastbin 中没有刚好匹配 nb 大小的空闲 chunk

• 判断是否属于smallbin

  • 通过调用in_smallbin_range函数判断是否属于smallbin

    if (in_smallbin_range (nb))

  • 获取该大小所在的链表的index

    idx = smallbin_index (nb);
    bin = bin_at (av, idx);

  • 判断smallbin是否为空，为空则跳过剩下的代码

    if ((victim = last (bin)) != bin)
        {
              if (victim == 0) /* initialization check */

​ victim指向smallbin中的最后一个bin，若其为空则smallbin为空

• 调用malloc_consolidate 整理fastbins

  • 判断完不属于smallbin之后说明空间在largebin,不会立即检查largebin而是调用malloc_consolidate 将fastbins 里面的空闲 chunk 合并整理到 unsortedbin 中

  • 判断fastbins 为空，跳过

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

• 尝试切割top分配空间

  • 获取到 top chunk 的大小

    victim = av->top;
    size = chunksize (victim);

    victim指向av内存空间中的top chunk

  • 和申请的空间大小做比较：如果 top chunk 在满足分配后还能剩余空间大小大于最小的 chunk 的大小，则开始进行切割，并把剩余的 chunk 作为新的 top 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;
            }

  • 否则先判断fastbin是否非空，非空则重整理，fastbin和unsorted bin

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

  • 不为空，调用sysmalloc直接向系统申请内存

    else
            {
              void *p = sysmalloc (nb, av);
              if (p != NULL)
                alloc_perturb (p, bytes);
              return p;
            }

fastbin

free到fastbin

源程序

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x30);
	free(p);
	return 0;
}	

运行过程

• 由源码中strong_alias (__libc_free, free)得出：free就是__libc_free的别名

• 调用__libc_free函数，传入的参数*mem是要释放的堆的user data地址的指针

  void __libc_free(void *mem)

• 调用__free_hook中的函数来完成释放，默认值为0，没有初始化的过程

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

• 判断传入的指针值是否为0，free（0）无效

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

• 调用mem2chunk函数，将user data的指针mem转换为对应的chunk head指针p

  //mem2chunk函数宏定义
  //chunk head与user data之间相差prev_size和size字段，分别占一个机器字节，因此从user data到chunlk head只需减去两个机器字长，即2*SIZE_SZ
  #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

  p = mem2chunk (mem);	//p指向chunk head

• 调用chunk_is_mmapped函数判断该chunk是否由mmap分配

  //chunk_is_mmapped宏定义
  //检查size最低三位中的标志位，若为2则是mmap分配的内存
  #define IS_MMAPPED 0x2
  #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)

  补充：使用malloc 、free 等函数动态申请和释放内存时真正与系统交互用于系统调用的函数主要是 (s)brk 函数以及 mmap

  • brk用于分配小空间，将数据段(.data)的最高地址指针_edata往高地址推
  • mmap用于分配大空间，是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存
  • 这两种方式分配的都是虚拟内存，没有分配物理内存

  源程序中释放的堆不是由mmap分配的因此跳过if中的内容

• 调用arena_for_chunk获取该chunk的分配区指针ar_ptr

  ar_ptr = arena_for_chunk (p);

• 调用_int_free函数释放堆

  _int_free (ar_ptr, p, 0);

  //_int_free函数定义，参数中的mstate表示的是malloc_state结构体也就是main_arena的结构体，mchunkptr表示的是malloc_chunk的结构体，av指向该chunk的分配区，p指向该chunk的chunk head
  static void _int_free (mstate av, mchunkptr p, int have_lock)

• 调用chunksize函数获取该chunk的大小

  //chunksize宏定义，取p所指向的chunk的size位
  #define chunksize(p)         ((p)->size & ~(SIZE_BITS))

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

• 检查大小合理性

  //判断堆大小是大于最小值
  //判断大小对齐，即是机器字长的整数倍数
  if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
      {
        errstr = "free(): invalid size";
        goto errout;
      }

  //MINSIZE宏定义
  //MALLOC_ALIGN_MASK = 两倍机器字长-1，结果将MIN_CHUNK_SIZE进行两倍机器字长对齐
  #define MINSIZE  \
    (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

  //aligned_OK宏定义，结果是判断是否是机器字长的整数倍
  #define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
  //MALLOC_ALIGN_MASK宏定义
  #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)

  //MIN_CHUNK_SIZE宏定义
  #define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

• 判断堆是否在fastbin里

  //大小小于等于fastbin最大值
  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

• 安全性检查：检查要释放的堆的下一个堆的大小是否合法

  //互斥锁是否开启
  //下一个堆的大小是否小于最小堆大小或大于该内存池的user data最大值
  //av指向chunk分配区
  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;
  	  }

• 清空堆中的内容

  free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

  //free_perturb函数定义
  //p指向user data， n 为实际堆实际大小，即不含chunk head
  //perturb：扰乱
  //perturb_byte为0时，将堆的user data部分清空为0
  static void
  free_perturb (char *p, size_t n)
  {
    if (__glibc_unlikely (perturb_byte))
      memset (p, perturb_byte, n);
  }

• 设置分配区的标志位表示fastbin有空闲chunk

  //av的标志位设置为1
  set_fastchunks(av);

  //set_fastchunks宏定义
  #define set_fastchunks(M)      catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
  //FASTCHUNKS_BIT宏定义
  #define FASTCHUNKS_BIT        (1U)

• 根据size获得即将添加的chunk在fastbin中的索引idx，并通过该索引获得头指针fb

  //fastbin_index宏定义
  #define fastbin_index宏定义(sz) \
    ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)   
  //SIZE_SZ等于一个机器字长，32位右移1，64位右移2（除）

  //fb指向chunk大小所在的fastbin链的头指针
  unsigned int idx = fastbin_index(size);
  fb = &fastbin (av, idx);

• 安全性检查：检查double free

  //如果头指针等于要释放的堆，则判定double free
  //old等于要释放的堆所属的fastbin链的头结点
  mchunkptr old = *fb, old2;
  unsigned int old_idx = ~0u;
  if (__builtin_expect (old == p, 0))
  	  {
  	    errstr = "double free or corruption (fasttop)";
  	    goto errout;
  	  }

• 将chunk添加到顶部之后检查顶部的 fastbin 块的大小是否与我们要添加的块的大小相同。只有在我们拥有锁的情况下，我们才能解除对 OLD 的引用

  //检查互斥锁
  //old_idx为头结点所在的fastbin链的下标
  //该chunk添加到fastbin中，即将fd设置为原来的头结点，并且把该chunk设置为头指针
  //idx和old_idx不相等的时候报错
  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;
        }
    }

从fastbin取出chunk

源程序

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x30);
	free(p);
	malloc(0x30);
	return 0;
}	

运行过程

• 运行至初次创建堆的判断申请实际大小所在的fastbin链表的第一个结点是否为空

• 第一个结点不为空，则更改链表头指向第二个结点

  do
         {
           victim = pp;
           if (victim == NULL)
             break;
         }
       while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
              != victim);

• 安全性检查：判断所取到的堆的大小所在fastbin的下标与申请的实际大小应该在的下标是否一致

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

• 计算并返回从fastbin获取的chunk的user data起始地址

  void *p = chunk2mem (victim);
  alloc_perturb (p, bytes);
  return p;

fastbin相关漏洞和绕过利用原理

double free

在free到fastbin中有对double free的判断机制

//如果头指针等于要释放的堆，则判定double free
//old等于要释放的堆所属的fastbin链的头结点
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
if (__builtin_expect (old == p, 0))
	  {
	    errstr = "double free or corruption (fasttop)";
	    goto errout;
	  }

原理：连续两次释放同一个堆

利用：判断要释放的堆所属的fastbin链的第一个chunk地址是否和要释放的堆的地址相同，若相同则判定为double free，因此绕过只需要保证二者地址不同即可，所以绕过方法是在第二次释放之前先释放一个属于这个链的堆使得第一个地址不是实际要释放的地址，第二次释放需要释放的地址时链表第一个地址就是两次释放之间释放的堆的地址，不会触发double free的报错。

绕过对取出的堆的大小检查

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

利用find_fake_fast工具寻找离所求地址最近的可以伪造size位符合要求的堆

unsorted bin

free到unsorted bin

源程序

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x100);
    malloc(0x100);
	free(p);
	return 0;
}	

运行过程

• 运行至free到fastbin的判断堆是否在fastbin里

• 不在fastbin之后判断是否是mmap分配的，不是则继续运行

  else if (!chunk_is_mmapped(p)) {

• 如果没有互斥锁则加锁

  if (! have_lock) {
        (void)mutex_lock(&av->mutex);
        locked = 1;
      }

• 获得下一个chunk的大小和指针到p和size，即p指向下一个chunk的地址，size为下一个堆的大小

  nextchunk = chunk_at_offset(p, size);

• 检查该地址是否在分配区顶部，是则报错

  if (__glibc_unlikely (p == av->top))
        {
  	errstr = "double free or corruption (top)";
  	goto errout;
        }

  其中，av为堆所在的分配区地址

• 判断下一个堆是否超出分配区的范围，判断方式：判断下一个堆的地址是否大于等于av->top加上av->top的大小

  if (__builtin_expect (contiguous (av)
  		  && (char *) nextchunk
  		  >= ((char *) av->top + chunksize(av->top)), 0))
       {
  errstr = "double free or corruption (out)";
  goto errout;
       }

• 判断要释放的堆是否在inuse状态，判断方式：获取下一个堆的prev_inuse值

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

• 清空堆中的内容

  free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

• 判断前一个堆是否被释放，如果被释放了则和前一个堆合并：获取前一个堆的大小，加到当前要释放的堆的size，并通过unlink将该chunk从空闲链表中脱离

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

• 判断下一个堆是否是top chunk,若是则与top chunk合并，结束释放过程

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

• 如果不是，获取下一个堆的inuse位

  nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

• 判断下一个堆是否在使用，若已经被释放则合并到当前要释放的堆，并通过unlink将该chunk从空闲链表中脱离

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

• 若还在使用则将prev_inuse设为0表示当前堆已经被释放了

  } else
  	clear_inuse_bit_at_offset(nextchunk, 0);

• 获取分配区中的unsorted_bin的第一个堆的地址到bck，获取头结点fwd

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

• 检查fwd的bk是否是bck，不是则报错

  if (__glibc_unlikely (fwd->bk != bck))
  {
    errstr = "free(): corrupted unsorted chunks";
    goto errout;
  }

• 将堆连接到unsorted bin中，即将要释放的堆的fd改成fwd，bk改成bck，bck的fd和fwd的bk设置成p，将p连到fwd和bck之间成为第一个，并且堆大小不在smallbin范围内时设置其fd_nextsize和bk_nextsize为NULL

    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;

从unsorted bin取出chunk

源代码

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x100);
    malloc(0x100);
	free(p);
    malloc(0x100);
	return 0;
}

运行过程

• 运行到初次创建堆的调用malloc_consolidate 整理fastbins

• 进入整理unsorted bin的大循环，一边整理一边查找合适的chunk，找到即返回，结束创建过程

  int iters = 0;
  while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
      bck = victim->bk;

  结束条件：遍历整理完unsorted bin或整理次数超过10000

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

• 获取unsorted bin的第二个堆并且进行大小检查

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

• 获取unsorted bin的第一个chunk的大小

  size = chunksize (victim);

• 将 bck->fd 的位置写入本 Unsorted Bin 的位置

  /* remove from unsorted list */
            unsorted_chunks (av)->bk = bck;
            bck->fd = unsorted_chunks (av);

• unsorted bin的第一个chunk与所申请chunk精确匹配则直接返回

  /* Take now instead of binning if exact fit */
  
            if (size == nb)
              {
                set_inuse_bit_at_offset (victim, size);	//将匹配的的chunk设置为inuse
                if (av != &main_arena)
                  victim->size |= NON_MAIN_ARENA;	//若分配区非main_arena则设置为NON_MAIN_ARENA
                check_malloced_chunk (av, victim, nb);	
                void *p = chunk2mem (victim);		//返回堆的user data地址
                alloc_perturb (p, bytes);
                return p;
              }

unsorted bin相关漏洞和绕过利用原理

利用unsorted bin泄露libc地址

• 释放一个堆到unsorted bin之后输出这个堆的fd

  • 原理：将p连到fwd和bck之间成为倒数第二个堆的过程中时fwd = bck = main_arena ，连接之后被释放的堆的fd和bk均指向main_arena

• 两个相同大小的unsorted bin合并，申请一个相同大小的堆块，此时残留fd，可以泄露libc

  • 原理： 判断下一个堆已经被释放合并到当前要释放的堆并通过unlink将该chunk从空闲链表中脱离的时候不会清空堆里的内容，所以两个堆合并的时候保留了fd和bk，在申请的时候只要不覆盖掉堆里的内容就能够把main_arena地址申请出来，两个堆必须地址连续

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

任意地址写为一个很大的数值

原理：将 bck->fd 的位置写入本 unsorted Bin 的位置，控制了bk即可将unsorted_chunks (av)写到任意地址（写入的地址要减两倍机器字长），将该堆申请出来就可以实现任意地址改为一个不可控的很大的数值

/* remove from unsorted list */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

small bin

free到small bin

源代码

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x100);
    malloc(0x100);
	free(p);
    malloc(0x110);
	return 0;
}

运行过程

• 运行到[从unsorted bin取出chunk](#从unsorted bin取出chunk)的将 bck->fd 的位置写入本 Unsorted Bin 的位置

• 判断unsorted bin中循环到的堆是否和申请的堆大小精确匹配，不匹配则跳过

  if (size == nb)

• 判断是否属于small bin，属于则获取所在的small bin链下标和头结点和首结点，并且将循环到的堆连接到small bin的头部

  if (in_smallbin_range (size))
              {
                victim_index = smallbin_index (size);
                bck = bin_at (av, victim_index);
                fwd = bck->fd;
              }

  victim->bk = bck;
           victim->fd = fwd;
           fwd->bk = victim;
           bck->fd = victim;if (in_smallbin_range (size))
             {
               victim_index = smallbin_index (size);
               bck = bin_at (av, victim_index);
               fwd = bck->fd;
             }

从small bin取出chunk

源代码

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x100);
    malloc(0x100);
	free(p);
    malloc(0x110);
    malloc(0x100);
	return 0;
}

运行过程

• 运行到初次创建堆的判断是否属于smallbin

  if (in_smallbin_range (nb))

• 获取申请的堆的大小所在的下标和地址

  idx = smallbin_index (nb);
  bin = bin_at (av, idx);

• 判断所在的下标的链是否为空，为空则说明获取失败跳过该部分

  if ((victim = last (bin)) != bin)

• 不为空则判断获取到的链表尾部的堆是否为空，为空则说明small bin未初始化，调用malloc_consolidate进行初始化

  if ((victim = last (bin)) != bin)
          {
            if (victim == 0) /* initialization check */
              malloc_consolidate (av);

• 不为空则先获取最后一个结点的下一个结点，判断下一个结点的fd是否为最后一个结点，不是则报错

  else
             {
               bck = victim->bk;
  if (__glibc_unlikely (bck->fd != victim))
                 {
                   errstr = "malloc(): smallbin double linked list corrupted";
                   goto errout;
                 }

• 通过安全检查之后将最后一个结点设置inuse和NON_MAIN_ARENA位并且从链表中取出，返回该堆的地址指针

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;

large bin

free到large bin

源代码

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x500);
    malloc(0x500);
	free(p);
    malloc(0x550);
	return 0;
}

运行过程

• 运行到[从unsorted bin取出chunk](#从unsorted bin取出chunk)的将 bck->fd 的位置写入本 Unsorted Bin 的位置

• 判断是否在small bin ，如果不在则在large bin

  if (in_smallbin_range (size))

• 获取循环到的堆在large bin中的下标并且取得该链表的首结点bck和头结点fwd

  victim_index = largebin_index (size);
  bck = bin_at (av, victim_index);
  fwd = bck->fd;

• 判断头结点和首结点是否相同，相同则说明该链表为空，直接跳过一些判断和连接，将该堆插入在fd bk 双向链表的头部，并且设置其fd_nextsize和bk_nextsize都为其本身

  if (fwd != bck)

  else
                  victim->fd_nextsize = victim->bk_nextsize = victim;         

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

• 若不相同，即if成立则说明该链中还有其他堆，首先获取到循环到的堆的大小去掉inuse位之后的大小

  /* Or with inuse bit to speed comparisons */
                    size |= PREV_INUSE;

• 如果最后一个堆在main_arena则报错

  assert ((bck->bk->size & NON_MAIN_ARENA) == 0);

• 如果循环到的堆的大小小于最小的堆那么插入在fd_nextsize nk_nextsize链中最小的堆的后面

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

• 如果不是最小的堆那么遍历到第一个不小于该堆的chunk，遍历中判断每一个堆是否属于main_arena，属于则报错

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

• 如果遍历到的堆和循环中的堆的大小相同则在fd bk链表中插入到与其相同大小的堆的后面

  if ((unsigned long) size == (unsigned long) fwd->size)
                         /* Always insert in the second position.  */
                         fwd = fwd->fd;

• 否则就插入在fd_nextsize nk_nextsize链中遍历到的堆的后面

  else
                          {
                            victim->fd_nextsize = fwd;
                            victim->bk_nextsize = fwd->bk_nextsize;
                            fwd->bk_nextsize = victim;
                            victim->bk_nextsize->fd_nextsize = victim;
                          }

• 并且插入到fd bk链表中

  bck = fwd->bk;

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

从large bin取出chunk

源代码

#include <stdlib.h>

int main(int argc, char **argv){
	void *p;
	p = malloc(0x500);
    malloc(0x500);
	free(p);
    malloc(0x550);
    malloc(0x500);
	return 0;
}

运行过程

• 运行到[free到large bin](#free到large bin)结束

• 判断是否不属于small bin，即是否属于large bin

  if (!in_smallbin_range (nb))

• 获取申请的堆所在的large bin链的地址

  bin = bin_at (av, idx);

• 判断是否该链为空或者最大的堆太小不能符合申请的堆的大小，若是则直接结束对large bin中申请堆的判断，若符合则获取了第一个堆到victim

  if ((victim = first (bin)) != bin &&
                (unsigned long) (victim->size) >= (unsigned long) (nb))

• 在fd_nextsize bk_nextsize链中循环遍历到第一个不小于申请的大小的堆

  victim = victim->bk_nextsize;
                while (((unsigned long) (size = chunksize (victim)) <
                        (unsigned long) (nb)))
                  victim = victim->bk_nextsize;

• 判断遍历到的堆不是尾结点并且它的大小等于它在fd bk链上的上一个堆的大小

  if (victim != last (bin) && victim->size == victim->fd->size)

• 获取该大小的堆在fd bk链上的第二个堆，因为第一个堆在fd_nextsize bk_nextsize链中，取出需要调整该链，但取出第二个堆就不需要调整链表

  victim = victim->fd;

• 保存该堆大小减去申请的大小的差值并且通过unlink操作从large bin链表中取出该堆

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

• 如果差值小于最小的堆的大小，则直接将该堆返回

  if (remainder_size < MINSIZE)
                  {
                    set_inuse_bit_at_offset (victim, size);	//设置inuse位
                    if (av != &main_arena)
                      victim->size |= NON_MAIN_ARENA;//设置NON_MAIN_ARENA位
                  }

  void *p = chunk2mem (victim);
           alloc_perturb (p, bytes);
           return p;		//获取并返回该堆的地址

• 如果差值大于最小的堆的大小则切割large bin，获取上面取到的堆切割了申请的大小的堆之后剩余的堆

  else
                  {
                    remainder = chunk_at_offset (victim, nb);	

• 获取unsorted bin的首结点和头结点

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

• 检查头结点的bk指向的堆是否是首结点，若不是则报错

  if (__glibc_unlikely (fwd->bk != bck))	//检查头结点后面一个结点是否是首结点
                      {
                        errstr = "malloc(): corrupted unsorted chunks";
                        goto errout;
                      }

• 将剩余的堆插入unsorted bin

  remainder->bk = bck;
              remainder->fd = fwd;
              bck->fd = remainder;
              fwd->bk = remainder;

• 如果剩余的堆不在small bin 的范围内则设置fd_nextsize和bk_nextsize

  if (!in_smallbin_range (remainder_size))
                      {
                        remainder->fd_nextsize = NULL;
                        remainder->bk_nextsize = NULL;
                      }

• 返回切割的符合大小要求的堆的地址

  check_malloced_chunk (av, victim, nb);
                void *p = chunk2mem (victim);
                alloc_perturb (p, bytes);		//返回切割出来的申请的大小的堆地址
                return p;

unlink

用来将一个双向链表（只存储空闲的 chunk）中的一个元素取出来

/* Take a chunk off a bin list */
// unlink p
#define unlink(AV, P, BK, FD) {                                            
    // 由于 P 已经在双向链表中，所以有两个地方记录其大小，所以检查一下其大小是否一致。
    if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))      
      malloc_printerr ("corrupted size vs. prev_size");               
    FD = P->fd;                                                                      
    BK = P->bk;                                                                      
    // 防止攻击者简单篡改空闲的 chunk 的 fd 与 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;                                                              
        // 下面主要考虑 P 对应的 nextsize 双向链表的修改
        if (!in_smallbin_range (chunksize_nomask (P))                              
            // 如果P->fd_nextsize为 NULL，表明 P 未插入到 nextsize 链表中。
            // 那么其实也就没有必要对 nextsize 字段进行修改了。
            // 这里没有去判断 bk_nextsize 字段，可能会出问题。
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {                      
            // 类似于小的 chunk 的检查思路
            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);                                              
            // 这里说明 P 已经在 nextsize 链表中了。
            // 如果 FD 没有在 nextsize 链表中
            if (FD->fd_nextsize == NULL) {                                      
                // 如果 nextsize 串起来的双链表只有 P 本身，那就直接拿走 P
                // 令 FD 为 nextsize 串起来的
                if (P->fd_nextsize == P)                                      
                  FD->fd_nextsize = FD->bk_nextsize = FD;                      
                else {                                                              
                // 否则我们需要将 FD 插入到 nextsize 形成的双链表中
                    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;                      
              }                                                                      
          }                                                                      
      }                                                                              
}