深入理解Linux堆分配器-DLMalloc

By xia0

0x00 序

当学习漏洞利用到一定阶段的时候,就需要对操作系统层面有足够的认识。无疑Linux的堆管理一直是不能甚解。因此这篇文章将对Linux的DLMalloc进行详细的介绍,以此对操作系统的堆管理有一个清晰整体的认识,当我在学习的过程中,好像没有发现一篇中文文章来详细介绍相关内容,所以本文仅仅是我通过学习和实践得到的理解,若有不对,请指出。

0x01 目录

1.DLMalloc
2.内存Chunk
3.Bin
4.malloc源码free()函数分析

0x02 DLMalloc

Doug Lea’s Malloc (dlmalloc)是一个GNU C库的内存分配器,它能够通过calloc(),malloc(), free()和realloc()等动态分配和释放的函数来管理内存。
明显内存分配器在操作系统中是相当重要的,主要在需要满足下列的特点:

  • 稳定性(stability)
  • 性能(performance)
  • 避免碎片化(avoidance of fragmentation)
  • 低空间开销(low space overhead)
    根据上面的内存特点,将有助于后面对chunk以及Bin等的理解。

0x03 内存chunk

1.什么是chunk?
chunk是堆中一些连续的内存块,可以用作分配,释放,拆分,合并。不存在两个连续的释放chunk,这是在于相邻的chunk会合并。

2.数据结构

struct malloc_chunk {
    INTERNAL_SIZE_T prev_size; //当前chunk前一个chunk的大小,仅在前一个为freed才使用
    INTERNAL_SIZE_T size;      //当前chunk的大小
    struct malloc_chunk * fd;  //如果当前为释放chunk,指向双向free list中前一个chunk
    struct malloc_chunk * bk;  //如果当前为释放chunk,指向双向free list中后一个chunk
}

根据上面的描述我们可以知道,chunk在分配时和释放时数据结构是不同的,看下面的图例:

  • allocate chunk
    0-0
  • freed chunk
    0-1

3.更多细节
因为chunk是按照8字节对齐的,所以当前块中的size低三位将用作相关标志,从右到左A M P分别代表:是否在主heap?是否通过mmap()分配?前一个chunk是否在使用?
然后可以想到有一个最小chunk的存在,其大小为16字节()。

4.特殊chunk
top chunk:指可能内存边界的末端,也被称作wilderness chunk。如果其他bin都不满足malloc的情况下,就会从top chunk里去一部分去满足分配请求,剩余的则作为新的top chunk,并且top chunk不在任何一个bin中。随着被分离和合并top chunk会增大和减小。

last_remainder:和top chunk一样,不在任何一个bin中,但最终可能会合并到一个bin中。可以看英文原文解释:The last_remainder chunk is the result of allocation requests for small chunks that have no exact fit in any of the bins. If the request is larger than the last_remainder chunk but smaller than a block in a bin, then the chunk is split again. The last_remainder chunk is the result of having to split a larger chunk into two, one part of it is handed out from the allocation, and the other because the last_remainder chunk.

0x04 Bin

chunk一旦被释放后就会被存储在叫做Bin的链表中,Bin有不同大小的链表,方便与下次查找到最适当的chunk。通常来说有small-bin,large-bin,fast-bin。
这里我主要介绍fsatbin和normalbin

(1)fastbin:是一种单链表bin,不同系统定义了一个最大值,当chunk大小小于等于这个最大值时,就会被释放到fastbin中,正如名字那样,为了更快的free和malloc,这个链表是无序的,是后进先出(LIFO),并且不与其他chunk合并。
(2)normalbin:是一种双向链表bin,当chunk大小大于fastbin的大小时就会被放入这个bin,并且有着各种大小的normalbin(减少碎片),bin内部的chunk按大小组织起来。释放后会于相邻的chunk合并。

0x05 free()源代码分析及相关细节

free(void *mem)-->__libc_free(void *mem)

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.
         Dumped fake mmapped chunks do not affect the threshold.  */
      if (!mp_.no_dyn_threshold
          && chunksize_nomask (p) > mp_.mmap_threshold
          && chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX
          && !DUMPED_MAIN_ARENA_CHUNK (p))
        {
          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); //跳转到_int_free
}

我们先不关注其他的,只需要知道会调用_int_free就就可以了

__libc_free(void *mem)-->_int_free (mstate av, mchunkptr p, int have_lock)

static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  INTERNAL_SIZE_T size;        /* 当前chunk的大小 */
  mfastbinptr *fb;             /* 相关的fastbin */
  mchunkptr nextchunk;         /* 下一个相邻的chunk */
  INTERNAL_SIZE_T nextsize;    /* 下一个chunk的大小 */
  int nextinuse;               /* 下一个chunk正在使用时为真 */
  INTERNAL_SIZE_T prevsize;    /* 前一个chunk的大小 */
  mchunkptr bck;               /* 指向free链表中向后一个chunk */
  mchunkptr fwd;               /* 指向free链表中向前一个chunk */

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

  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.  */
  //一些安全检查
  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)
        __libc_lock_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;
    }

  check_inuse_chunk(av, p); //检查当前chunk是否在使用

  /*
    如果满足,则将该chunk放入fastbin以便malloc时能够快速找到和使用
  */
  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
      ) {

    if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, 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);
                  __libc_lock_lock (av->mutex);
                  locked = 1;
                  chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
                    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
              }))
          {
            errstr = "free(): invalid next size (fast)";
            goto errout;
          }
        if (! have_lock)
          {
            __libc_lock_unlock (av->mutex);
            locked = 0;
          }
      }

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

  /*
    Consolidate other non-mmapped chunks as they arrive.
  */
  //检查是否是通过mmap()分配的内存
  else if (!chunk_is_mmapped(p)) {
    if (! have_lock) {
      __libc_lock_lock (av->mutex);
      locked = 1;
    }

    nextchunk = chunk_at_offset(p, size);//返回下一个chunk的地址

    /* Lightweight tests: check whether the block is already the
       top block.  */
    //检查下一个是否为top-chunk
    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 (chunksize_nomask (nextchunk) <= 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);

    /* 与后面chunk一个合并 */
    if (!prev_inuse(p)) {
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);//将后一个chunk从双向链表上取下来
    }

    if (nextchunk != av->top) {
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

      /* 与前面chunk一个合并*/
      if (!nextinuse) {
        unlink(av, nextchunk, bck, fwd);//将前一个chunk从双向链表上取下来
        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);
    }

    /*
      如果当前chunk正好与topchunk相邻,则合并到topchunk
    */

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

    /*
      If freeing a large space, consolidate possibly-surrounding
      chunks. Then, if the total unused topmost memory exceeds trim
      threshold, ask malloc_trim to reduce top.

      Unless max_fast is 0, we don't know if there are fastbins
      bordering top, so we cannot tell for sure whether threshold
      has been reached unless fastbins are consolidated.  But we
      don't want to consolidate on each free.  As a compromise,
      consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
      is reached.
    */

    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);
      __libc_lock_unlock (av->mutex);
    }
  }
  /*
    If the chunk was allocated via mmap, release via munmap().
  */

  else {
    munmap_chunk (p);
  }
}

这里看看unlink()宏定义

#define unlink( P, BK, FD ) {            
    BK = P->bk;                          
    FD = P->fd;                          
    FD->bk = BK;  //可能会造成任意写                       
    BK->fd = FD;                         
}

现在我们重点放在unlink(),当两个相邻chunk需要合并的时候,势必需要将临近的chunk从原来的双链表上取下来,然后与当前chunk合并成一个更大的块。等等!怎么取下来的呢?如果这里存在一个恶意的chunk即fd和bk都是一些恶意地址指针,则会出现任意地址写的一个漏洞。在这里我们就先不去讨论进一步的利用过程,只需知道存在一个这样的漏洞即可,后面会根据这个分析去漏洞利用。

glibc/malloc.c源码

0x06 参考

  1. Vudo malloc tricks
  2. A Memory Allocator
  3. Once upon a free()