glibc 中的 malloc 与 free 概述 (二)

Catalpa 网络安全爱好者
  2019-03-15 2019-03-15 Created   2024-10-17 08:49:15 2024-10-17 08:49:15 Updated   7.3k Words  34 Mins  

malloc 中的 consolidate

在 malloc 的流程中有几处调用到了这个函数，它的主要作用是遍历 fastbin 链表，将其中的堆块进行合并，插入到 unsorted bin 当中。

Update: 2020-11-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#if __STD_C
static void malloc_consolidate(mstate av)
#else
static void malloc_consolidate(av) mstate av;
#endif
{
  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) {  // 首先判断分配区是否初始化，如果没有就调到最后初始化分配区
    clear_fastchunks(av);

    unsorted_bin = unsorted_chunks(av);  // 获取 unsortedbin 链表

    /*
      Remove each chunk from fast bin and consolidate it, placing it
      then in unsorted bin. Among other reasons for doing this,
      placing in unsorted bin avoids needing to calculate actual bins
      until malloc is sure that chunks aren't immediately going to be
      reused anyway.
    */

#if 0
    /* It is wrong to limit the fast bins to search using get_max_fast
       because, except for the main arena, all the others might have
       blocks in the high fast bins.  It's not worth it anyway, just
       search all bins all the time.  */
    maxfb = &fastbin (av, fastbin_index(get_max_fast ()));
#else
    maxfb = &fastbin (av, NFASTBINS - 1);  // 获取最大的 fastbin 链表
#endif
    fb = &fastbin (av, 0);  // 取出第一条链表
    do {
#ifdef ATOMIC_FASTBINS
      p = atomic_exchange_acq (fb, 0);
#else
      p = *fb;  // 取出链表的第一个堆块
#endif
      if (p != 0) {  // 判断表是否为空
#ifndef ATOMIC_FASTBINS
	*fb = 0;
#endif
	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(p, bck, fwd);
	  }

	  if (nextchunk != av->top) {   // 判断当前堆块物理上的下一个堆块是否是 top chunk
	    nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

	    if (!nextinuse) {  // 判断是否可以前向合并
	      size += nextsize;
	      unlink(nextchunk, bck, fwd);
	    } else
	      clear_inuse_bit_at_offset(nextchunk, 0);

	    first_unsorted = unsorted_bin->fd;
	    unsorted_bin->fd = p;
	    first_unsorted->bk = p;    // 将合并后的堆块插入到 unsorted bin

	    if (!in_smallbin_range (size)) {   // 如果合并之后的 chunk 是一个 large bin chunk
	      p->fd_nextsize = NULL;
	      p->bk_nextsize = NULL;    // unsortedbin 中 这两个指针无用，清空
	    }

	    set_head(p, size | PREV_INUSE);
	    p->bk = unsorted_bin;
	    p->fd = first_unsorted;
	    set_foot(p, size);    // 将 largebin chunk 插入 unsortedbin
	  }

	  else {
	    size += nextsize;    // 如果和 top chunk 相邻，则与 topchunk 合并
	    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);
  }
}

consolidate 的逻辑还算简单，主要是对 fastbin 进行操作，首先要判断分配区是否已经初始化，如果是，会逐个 fastbin 链表进行遍历，如果链表为空，就转移到下一个链表，如果不空，就依次取出其中的 chunk，首先判断是否能够进行后向合并，然后判断是否能进行前向合并，最后判断能否与 topchunk 合并，在合并的过程中，要考虑到合并出来的堆块是 smallbin 还是 largebin，以便于用不同的方式插入 unsortedbin。参考下图

malloc_free_8.png

sYSMALLOc

这个函数会在所有缓冲区和 topchunk 都不能满足分配要求时调用，主要功能是向操作系统申请新的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#if __STD_C
static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
#else
static Void_t* sYSMALLOc(nb, av) INTERNAL_SIZE_T nb; mstate av;
#endif
{
  mchunkptr       old_top;        /* incoming value of av->top */
  INTERNAL_SIZE_T old_size;       /* its size */
  char*           old_end;        /* its end address */

  long            size;           /* arg to first MORECORE or mmap call */
  char*           brk;            /* return value from MORECORE */

  long            correction;     /* arg to 2nd MORECORE call */
  char*           snd_brk;        /* 2nd return val */

  INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
  INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
  char*           aligned_brk;    /* aligned offset into brk */

  mchunkptr       p;              /* the allocated/returned chunk */
  mchunkptr       remainder;      /* remainder from allocation */
  unsigned long   remainder_size; /* its size */

  unsigned long   sum;            /* for updating stats */

  size_t          pagemask  = mp_.pagesize - 1;
  bool            tried_mmap = false;

首先是各种变量的定义，它们的功能在注释里面写的比较清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#if HAVE_MMAP
  if ((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.
    */
#if 1
    /* See the front_misalign handling below, for glibc there is no
       need for further alignments.  */
    size = (nb + SIZE_SZ + pagemask) & ~pagemask;
#else
    size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
#endif

接着判断一下 HAVE_MMAP 宏定义是否为 1，引用 malloc.c 的注释如下

1
2
3
4
5
6
7
8
9
Define HAVE_MMAP as true to optionally make malloc() use mmap() to
  allocate very large blocks.  These will be returned to the
  operating system immediately after a free(). Also, if mmap
  is available, it is used as a backup strategy in cases where
  MORECORE fails to provide space from system.

  This malloc is best tuned to work with mmap for large requests.
  If you do not have mmap, operations involving very large chunks (1MB
  or so) may be slower than you'd like.

选项是可以自定义的，这是因为有些操作系统并不支持 mmap，又或者用户不希望程序使用 mmap 向系统申请空间，就可以将这个选项关闭。

然后会判断是否能通过 mmap 分配内存，需要满足 2 个条件，一是 nb 大于等于 mmap 的分配阈值，二是当前进程通过 mmap 方式分配的内存总量小于最大值，这两个最大值分别是

1
2
DEFAULT_MMAP_THRESHOLD     128 * 1024
DEFAULT_MMAP_MAX       (65536)

不知道为什么，第二个判断似乎总能成功，有了解的大哥请告诉我

如果上面两个条件都能满足，就会进入到 mmap 的分配流程，首先要重新计算 size，引用 malloc.c 的注释如下

1
2
3
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.

重新计算 size 的原因有两个，一是 mmap 分配的内存块必须页对齐，二是 mmap 分配出来的堆块没有下一个堆块的 prev_size 空间可以复用，所以需要重新计算 size。

计算 size 之后会执行下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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, MAP_PRIVATE));

      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 1
	/* 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);
#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
#endif
	  {
	    p = (mchunkptr)mm;
	    set_head(p, size|IS_MMAPPED);
	  }

	/* update statistics */

	if (++mp_.n_mmaps > mp_.max_n_mmaps)
	  mp_.max_n_mmaps = mp_.n_mmaps;

	sum = mp_.mmapped_mem += size;
	if (sum > (unsigned long)(mp_.max_mmapped_mem))
	  mp_.max_mmapped_mem = sum;
#ifdef NO_THREADS
	sum += av->system_mem;
	if (sum > (unsigned long)(mp_.max_total_mem))
	  mp_.max_total_mem = sum;
#endif

	check_chunk(av, p);

	return chunk2mem(p);
      }
    }
  }
#endif

首先要判断 size 是否小于 nb，如果出现这种情况，说明 size 发生了溢出，不会继续分配内存，否则进入到主要的 mmap 逻辑。 直接调用 mmap 函数尝试分配一个堆块，分配成功就不需要进一步检查对齐的问题了，因为 mmap 的堆块本来就是页对齐的。

之后会将堆块的 IS_MMAPED 标志位置 1，表示它是通过 mmap 方式分配出来的。之后就是一些更新全局变量的操作，并且返回堆块。

如果在 mmap 这一支不能成功分配堆块，有 3 种情况，一是 nb 大于 mmap 的分配阈值，二是 size 发生溢出，不能通过 mmap 分配，三是 mmap 分配失败。

如果发生上面的三种情况，会进入到下一个阶段，即拓展 top chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 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 & pagemask) == 0));

  /* Precondition: not enough current space to satisfy nb request */
  assert((unsigned long)(old_size) < (unsigned long)(nb + MINSIZE));
#ifndef ATOMIC_FASTBINS
  /* Precondition: all fastbins are consolidated */
  assert(!have_fastchunks(av));
#endif

首先保存旧的 top chunk 信息，然后判断 top chunk 是否合法，当程序执行到这里，top chunk 有两种情况，一是没有被初始化，size 等于 0，二是已经被初始化，但是 size 不能满足 nb，这使就要求 size 大于 MINSIZE ，并且 prev_inuse 标志位为 1，并且 top chunk 的尾部是对齐的。

最下面是一个比较重要的判断，如果没有开启 ATOMIC_FASTBINS，当程序执行到这里时，所有的 fastbin chunk 一定是通过 consolidate 合并过了，如果还有 fastbin chunk 残留在链表中，说明发生了一些错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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) {  // 尝试扩展当前 heap
      av->system_mem += old_heap->size - old_heap_size;
      arena_mem += old_heap->size - old_heap_size;
#if 0
      if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
	max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
#endif
      set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
	       | PREV_INUSE);
    }
    else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {  // 扩展 heap 失败，尝试分配新的 heap
      /* Use a newly allocated heap.  */
      heap->ar_ptr = av;
      heap->prev = old_heap;
      av->system_mem += heap->size;
      arena_mem += heap->size;
#if 0
      if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
	max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
#endif
      /* 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. */
      /* 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 -= MINSIZE;
      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);
#ifdef ATOMIC_FASTBINS
	_int_free(av, old_top, 1);
#else
	_int_free(av, old_top);
#endif
      } 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)   // 检查是否还能使用 mmap
      /* We can at least try to use to mmap memory.  */
      goto try_mmap;

  }

如果当前线程的分配区不是主分配区，会先尝试拓展当前的 heap，通过调整 sub_heap 的边界尝试获取更多的空间，如果失败，就会尝试新建一个 heap(使用 brk() 拓展) ，在新建 heap 的代码中，和 pwn 题有关系的就是 __int_free(av, old_top)，这句代码，因为它会将旧的 top chunk 加入到 unsortedbin 中，这也是 house of orange 以及一系列衍生攻击的基础。

注意！ 下面的代码从 sYSMALLOc 尾部取得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* if (av !=  &main_arena) */

  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);    // 返回堆块
  }

拓展出新的 heap 之后就可以切割出满足要求的堆块了。

如果拓展 topchunk 或者是 分配新的 heap 都失败了，就会检查是否尝试过 mmap，如果没有，就会跳转到 mmap 部分尝试映射一块内存。

如果当前分配区属于主分配区，那么情况要复杂很多，不过最后的效果是差不多的，而且这段代码和 pwn 题关联并不是很大，想要详细了解的同学可以自行分析一下 glibc 的源代码。

sYSMALLOc 的执行流程可以参考下面这张图片(省略了在主分配区的情况)

malloc_free_9.png

malloc 几个细节

malloc 还有几个细节，在这里稍作解释。

  1. 物理内存分配时间。上一篇文章提到调用 malloc 并不会立即在物理页面上创建相应的堆块，而是当用户真正使用这块空间的时候才会创建，这是由于 malloc 给程序分配的是虚拟地址，当程序访问这个虚拟地址的时候，MMU 发现虚拟地址没有对应的物理内存，触发页中断，这时候硬件会陷入内核处理中断，操作系统负责分配物理内存，MMU 再将虚拟地址绑定到物理内存上面，完成内存分配操作。
  2. MMU： 英文 Memory Management Unit 内存管理单元，这个模块一般都被集成在 CPU 中，CPU 发出的是虚拟地址(例如调试的时候经常看到的 0x400000 等)，正常情况下这个如果使用这个地址去寻找内存的话是找不到的，需要先经过 MMU 将虚拟地址转换成物理内存地址才能正常寻址。

简单理解 brk 与 mmap：

这两个属于底层的系统调用，malloc 就是依靠它们完成内存分配的，brk 在原有的 heap 基础上进行拓展，而 mmap 尝试在堆栈之间找一块内存。

以下图为例，这是一个简单的内存模型

malloc_free_10.png

如果用户申请了一块比较大的内存，当前 top chunk 大小不足以容纳(并且没有超过 mmap 的阈值)，就会调用 sYSMALLOc 尝试拓展当前 heap。这里要介绍一个指针 _edate，它被定义在 glibc 中，指向当前进程数据段的最高地址，当拓展 heap 的时候，会调 brk 这个系统调用，例如连续分配两个大小为 0x7800 的堆块，调用 brk 之后如图

malloc_free_11.png

所以 brk 的大致原理就是抬高 _edata 指针，来拓展当前的 heap。

当用户申请的 chunk 大小超过 mmap 阈值，会直接调用 mmap 来分配堆块，例如申请一个大小为 0x22000 的堆块，mmap 之后如图
malloc_free_12.png

free 的时候也是一样，如果 free mmap 的区域，ptmalloc 会直接将内存返回给系统，但是当 free chunk1 的时候，由于 _edata 指针指向数据段的最高地址，而最高地址还有一个 chunk2 正在被使用，这时不能收缩堆。而当 chunk2 也被 free 之后，1 2 两个 chunk 会自动合并，_edata 指针也就可以收缩了，chunk1 和 2 组成的一块内存会被归还操作系统。

free

前面分析了 malloc 以及几个附加函数，下面就要进入到 free 函数了。

操作系统的内存不是无限的，程序使用 malloc 向操作系统申请内存，不能一直占据不放，当这些内存不再使用的时候，需要使用 free 函数进行释放，以保证整个系统的正常运行。

简单的理解一下，free 函数所执行的操作其实可以视为 malloc 函数的逆过程，malloc 从缓冲区或者操作系统中拿取空间，而 free 则负责将这些空间放回缓冲区或者操作系统。

public_fREe

此函数是 free 的外壳函数，所处理的问题和多线程有关，free 的核心函数是 __int_free

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void
public_fREe(Void_t* mem)
{
  mstate ar_ptr;
  mchunkptr p;                          /* chunk corresponding to mem */

  void (*hook) (__malloc_ptr_t, __const __malloc_ptr_t)
    = force_reg (__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 HAVE_MMAP
  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;
      }
    munmap_chunk(p);
    return;
  }
#endif

  ar_ptr = arena_for_chunk(p);
#ifdef ATOMIC_FASTBINS
  _int_free(ar_ptr, p, 0);
#else
# if THREAD_STATS
  if(!mutex_trylock(&ar_ptr->mutex))
    ++(ar_ptr->stat_lock_direct);
  else {
    (void)mutex_lock(&ar_ptr->mutex);
    ++(ar_ptr->stat_lock_wait);
  }
# else
  (void)mutex_lock(&ar_ptr->mutex);
# endif
  _int_free(ar_ptr, p);
  (void)mutex_unlock(&ar_ptr->mutex);
#endif
}

__int_free

和 malloc 一样，free 函数的核心代码是 __int_free，可以在 malloc.c 中找到。

函数开头首先定义了一些局部变量，摘录如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void
#ifdef ATOMIC_FASTBINS
_int_free(mstate av, mchunkptr p, int have_lock)
#else
_int_free(mstate av, mchunkptr p)
#endif
{
  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;
#ifdef ATOMIC_FASTBINS
  int locked = 0;
#endif
    
  size = chunksize(p);

依旧是那些很常用的变量，这里就不详细介绍了。

__int_free 函数主要有两个参数，一是指向 arena 的指针 av，二是传入的 chunk 指针，代码首先使用 chunksize 计算出当前 chunk 的大小，然后是一些安全检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 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:
#ifdef ATOMIC_FASTBINS
      if (! have_lock && locked)
	(void)mutex_unlock(&av->mutex);
#endif
      malloc_printerr (check_action, errstr, chunk2mem(p));
      return;
    }
  /* We know that each chunk is at least MINSIZE bytes in size.  */
  if (__builtin_expect (size < MINSIZE, 0))
    {
      errstr = "free(): invalid size";
      goto errout;
    }
  check_inuse_chunk(av, p);

这段代码检查了 chunk 的 size 是否发生了溢出，堆块的地址要对齐，并且堆块的 size 不能小于最小值。

接下来会首先判断当前 chunk 是否属于 fastbin，因为 fastbin 是分配速度最快的缓冲区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*
    If eligible, place chunk on a fastbin so it can be found
    and used quickly in malloc.
  */

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())  // 判断 chunk 的 size 是否属于 fastbin 范围内

#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 (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0)) // 安全检查，当前 chunk 的 next chunk size 不能小于 2 * SIZE_SZ，并且不能大于此时的内存分配总量。
      {
#ifdef ATOMIC_FASTBINS
	/* 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;
	      }))
#endif
	  {
	    errstr = "free(): invalid next size (fast)";
	    goto errout;
	  }
#ifdef ATOMIC_FASTBINS
	if (! have_lock)
	  {
	    (void)mutex_unlock(&av->mutex);
	    locked = 0;
	  }
#endif
      }

    if (__builtin_expect (perturb_byte, 0))
      free_perturb (chunk2mem(p), size - SIZE_SZ);

    set_fastchunks(av);    // 将 chunk 的标志位置位
    unsigned int idx = fastbin_index(size);    // 计算当前 chunk 在链表中的 index
    fb = &fastbin (av, idx);   // 根据 index 获取链表头结点指针

#ifdef ATOMIC_FASTBINS
    mchunkptr fd;
    mchunkptr old = *fb;
    unsigned int old_idx = ~0u;
    do
      {
	/* Another simple check: make sure 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;
	  }
	if (old != NULL)
	  old_idx = fastbin_index(chunksize(old));
	p->fd = fd = old;
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, fd)) != fd);

    if (fd != NULL && __builtin_expect (old_idx != idx, 0))
      {
	errstr = "invalid fastbin entry (free)";
	goto errout;
      }
#else
    /* Another simple check: make sure the top of the bin is not the
       record we are going to add (i.e., double free).  */
    if (__builtin_expect (*fb == p, 0))    // 当前链表的第一个堆块不能是正要插入的堆块，防止 double free 的发生
      {
	errstr = "double free or corruption (fasttop)";
	goto errout;
      }
    if (*fb != NULL
	&& __builtin_expect (fastbin_index(chunksize(*fb)) != idx, 0)) // 如果当前链表不为空，但是第一个堆块的 size 不符合此链表的大小，说明某处发生了错误
      {
	errstr = "invalid fastbin entry (free)";
	goto errout;
      }

    p->fd = *fb;  // 如果以上检查都正常，就将当前 chunk 插入到 fastbin 中
    *fb = p;
#endif
  }

这部分代码比较简单，实现的功能是将属于 fastbin 的 chunk 插入到 fastbin 对应的链表中去，当 free 一个属于 fastbin 的 chunk 时，会首先检查这个 chunk 的下一个 chunk 的 size 是否正确，这也就是为什么在一些 pwn 题中伪造 fastbin chunk 的时候要一并伪造好下一个 chunk 的结构。

接着会获取 chunk 在 fastbin 中的 index，并且检查这条链表是否合法，如果链表不为空会判断第一个堆块是否属于当前链表，如果不是，说明发生了异常。另外还会判断正要插入的 chunk 是不是已经是当前链表的第一个堆块，如果是的话，说明发生了 double free(注意：这里仅仅检查了链表的第一个堆块，而没有遍历所有堆块，这就是 fastbin double free 能够成功的关键原因！)。

如果上面这些检查都没有问题，就会把 chunk 插入到对应的 fastbin 链表中，注意 fastbin 是从头部插入，而 malloc 也是从头部取出。另外，代码中涉及到了 ATOMIC_FASTBIN 优化的问题，它的机制之前已经简要介绍过，利用 lock-free 基础实现对 fastbin 链表的操作，我们这里就不去深究了。

上面的流程可以用这张图片表示
malloc_free_13.png

如果待 free 的堆块不属于 fastbin ，那么就会进入到下一段逻辑，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/*
    Consolidate other non-mmapped chunks as they arrive.
  */

  else if (!chunk_is_mmapped(p)) {   // 如果 chunk 不是通过 mmap 分配的
#ifdef ATOMIC_FASTBINS
    if (! have_lock) {
# if THREAD_STATS
      if(!mutex_trylock(&av->mutex))
	++(av->stat_lock_direct);
      else {
	(void)mutex_lock(&av->mutex);
	++(av->stat_lock_wait);
      }
# else
      (void)mutex_lock(&av->mutex);
# endif
      locked = 1;
    }
#endif

    nextchunk = chunk_at_offset(p, size);    // 找到当前 chunk 的下一个 chunk

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__builtin_expect (p == av->top, 0))  // 如果传入 free 函数的 chunk 指针指向 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))  // 判断 next chunk 是否超出 arena 的边界
      {
	errstr = "double free or corruption (out)";
	goto errout;
      }
    /* Or whether the block is actually not marked used.  */
    if (__builtin_expect (!prev_inuse(nextchunk), 0))  // 判断 next chunk 的 p_inuse 位是否已经被标记(正常情况下一定被标记)
      {
	errstr = "double free or corruption (!prev)";
	goto errout;
      }

    nextsize = chunksize(nextchunk);  // 取出 next chunk 的 size
    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (nextsize >= av->system_mem, 0))  // size 必须满足要求
      {
	errstr = "free(): invalid next size (normal)";
	goto errout;
      }

    if (__builtin_expect (perturb_byte, 0))  
      free_perturb (chunk2mem(p), size - SIZE_SZ);

    /* consolidate backward */
    if (!prev_inuse(p)) {    // 判断前一个堆块是否为空闲，如果是，则尝试进行合并
      prevsize = p->prev_size;
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(p, bck, fwd);   // 注意这里使用了 unlink 操作
    }

    if (nextchunk != av->top) {  // 如果后一个堆块不是 top
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

      /* consolidate forward */
      if (!nextinuse) {    // 判断后一个堆块是否处于空闲状态
	unlink(nextchunk, bck, fwd);  // 依旧是 unlink 操作，和后一个 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 (__builtin_expect (fwd->bk != bck, 0))
	{
	  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 插入到 unsorted bin 中，如果合并后的 chunk 属于 large chunk，会将 fd_nextsize 和 bk_nextsize 进行清空，因为这两个字段在 unsorted bin 中无用

    /*
      If the chunk borders the current high end of memory,
      consolidate into top
    */

    else {   // 如果 free 的 chunk 正好位于 top chunk 上方，就直接和 top 合并，这一点在 pwn 题中比较重要
      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) {  // 如果经过合并的堆块大小超过了 FASTBIN_CONSOLIDATION_THRESHOLD 阈值(64 KB)
      if (have_fastchunks(av))    // 如果此时 fastbin 链表不为空，就会调用 consolidate 合并 fastbin 中的 chunk
	malloc_consolidate(av); // 调用 consolidate，将 fastbin chunk 合并到 unsorted bin

      if (av == &main_arena) {   // 如果当前分配区是主分配区
#ifndef MORECORE_CANNOT_TRIM 
	if ((unsigned long)(chunksize(av->top)) >= 
	    (unsigned long)(mp_.trim_threshold))   // 如果当前 top chunk 大小大于 heap 的收缩阈值(可以结合上面的 brk 图示理解)，就会调用 sYSTRIm 收缩 heap
	  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));    // 如果当前分配区不是主分配区，就调用 heap_trim 收缩 sub_heap

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

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

上面一段代码比较长，但是实现的功能很简单，如果代码能够执行到这里，说明用户想要 free 的 chunk 大小不属于 fastbin，此时 ptmalloc 会分别判断当前 chunk 物理相邻的堆块是否空闲，如果是，就会调用 unlink 将这些堆块从它们的链表中卸下，然后和当前 chunk 合并，如果和 top chunk 紧邻，就会和 top chunk 进行合并。

当 chunk 的合并完成之后，合并出来的 chunk 很有可能会很大(之前已经申请和释放了许多 chunk)，如果这个 chunk 大小超出了 FASTBIN_CONSOLIDATION_THRESHOLD 阈值，并且 fastbin 中还有堆块，那就会调用 consolidate 合并 fastbin 中的 chunk。

在合并操作完成之后，还会判断当前分配区是不是主分配区，如果是，并且 top chunk 的大小已经超过了 heap 的收缩阈值，就调用 sYSTRIm 收缩 heap，不是主分配区，也会使用 heap_trim 来收缩 sub_heap.

以上是待 free chunk 不是由 mmap 分配的情况，如果是由 mmap 分配的堆块，会调用函数 munmap_chunk

1
2
3
4
5
else {
#if HAVE_MMAP
    munmap_chunk (p);
#endif
  }

这个函数主要用来回收 mmap 分配的空间。

结合这张图片理解
malloc_free_14.png

sYSTRIm

这个函数可以视为 sYSMALLOc 函数的逆过程，负责将内存返还给操作系统。

摘录 ptmalloc 的注释如下

1
2
3
4
5
6
sYSTRIm is an inverse of sorts to sYSMALLOc.  It gives memory back
  to the system (via negative arguments to sbrk) if there is unused
  memory at the `high' end of the malloc pool. It is called
  automatically by free() when top space exceeds the trim
  threshold. It is also called by the public malloc_trim routine.  It
  returns 1 if it actually released any memory, else 0.

函数的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#if __STD_C
static int sYSTRIm(size_t pad, mstate av)
#else
static int sYSTRIm(pad, av) size_t pad; mstate av;
#endif
{
  long  top_size;        /* Amount of top-most memory */
  long  extra;           /* Amount to release */
  long  released;        /* Amount actually released */
  char* current_brk;     /* address returned by pre-check sbrk call */
  char* new_brk;         /* address returned by post-check sbrk call */
  size_t pagesz;

  pagesz = mp_.pagesize;  //获取一内存页的大小
  top_size = chunksize(av->top);  // 获取 topchunk 的 size

  /* Release in pagesize units, keeping at least one page */
  extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz; // 计算 top chunk 中最大可释放的整数页的数量

  if (extra > 0) {

    /*
      Only proceed if end of memory is where we last set it.
      This avoids problems if there were foreign sbrk calls.
    */
    current_brk = (char*)(MORECORE(0));  // 获取 brk 的值
    if (current_brk == (char*)(av->top) + top_size) { // 如果和此时 top chunk 的结束地址相同，说明可以执行 heap 收缩

      /*
	Attempt to release memory. We ignore MORECORE return value,
	and instead call again to find out where new end of memory is.
	This avoids problems if first call releases less than we asked,
	of if failure somehow altered brk value. (We could still
	encounter problems if it altered brk in some very bad way,
	but the only thing we can do is adjust anyway, which will cause
	some downstream failure.)
      */

      MORECORE(-extra);  // 调用 sbrk 释放内存
      /* Call the `morecore' hook if necessary.  */
      void (*hook) (void) = force_reg (__after_morecore_hook);
      if (__builtin_expect (hook != NULL, 0))
	(*hook) ();   // 执行 more_hook (能否成为新的攻击点呢？)
      new_brk = (char*)(MORECORE(0));

      if (new_brk != (char*)MORECORE_FAILURE) {
	released = (long)(current_brk - new_brk);

	if (released != 0) {
	  /* Success. Adjust top. */
	  av->system_mem -= released;
	  set_head(av->top, (top_size - released) | PREV_INUSE);
	  check_malloc_state(av);
	  return 1;
	}
      }
    }
  }
  return 0;
}

这个函数的流程也是比较简单的，就不再赘述了。
malloc_free_15.png

unlink 是由一个独立的宏实现的，它的主要功能就是将一个空闲的 chunk 从它的链表中卸下来，以便于和其他 chunk 进行合并，Unlink 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Take a chunk off a bin list */
#define unlink(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); \
  else {                                                               \
    FD->bk = BK;                                                       \
    BK->fd = FD;                                                       \
    if (!in_smallbin_range (P->size)				       \
	&& __builtin_expect (P->fd_nextsize != NULL, 0)) {	       \
      assert (P->fd_nextsize->bk_nextsize == P);		       \
      assert (P->bk_nextsize->fd_nextsize == P);		       \
      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;		       \
      }								       \
    }								       \
  }                                                                    \
}

其中最为关键的代码如下

1
2
FD->bk = BK;                                                       \
BK->fd = FD;

利用 unlink 的攻击实际上利用的就是这两句代码，如果我们能够控制某个 chunk 的 bk 和 fd，并且能够绕过一些验证，那么就可以完成一次 unlink 攻击，但是这不是本文讨论的重点，网络上有很多大牛详细解析了 unlink 攻击的原理，大家可以自行搜索学习。

总结一下

至此我们通过 glibc 的源代码大致分析了一下 ptmalloc 中的 malloc 和 free 两个常用函数，由于堆溢出经常出现在一些 CTF 比赛中，所以从根源上理解这些东西对于我们深入学习和掌握堆溢出是很有帮助的，ptmalloc 非常注重性能，但是所谓有得必有失，注重性能的代价就是安全性不高，和 windows 的堆管理策略相比可谓小巫见大巫了。

ptmalloc 中还有几个与内存分配相关的函数如 realloc 等，但是它们的核心思想都是依托现有的缓冲区，尽量减少向操作系统申请内存的次数，以达到提高程序执行效率的目的。

Reference

华庭 《Glibc 内存管理 Ptmalloc2 源代码分析》

cloudburst ptmalloc flow chart

http://www.cnblogs.com/zhaoyl/p/3820852.html

  • Title: glibc 中的 malloc 与 free 概述 (二)
  • Author: Catalpa
  • Created at : 2019-03-15 00:00:00
  • Updated at : 2024-10-17 08:49:15
  • Link: https://wzt.ac.cn/2019/03/15/glibc_analyse2/
  • License: This work is licensed under CC BY-SA 4.0.
On this page
glibc 中的 malloc 与 free 概述 (二)
  1. malloc 中的 consolidate
  2. sYSMALLOc
  3. malloc 几个细节
  4. free
  5. public_fREe
  6. __int_free
  7. sYSTRIm
  8. Unlink
  9. 总结一下
  10. Reference