ptmalloc源码学习（三）

发表于

ptmalloc源码学习第三篇，free的过程，以及unlink和malloc_consolidate这两个常用的宏。

说明：本篇文章的所有源码均来自glibc-2.29，主要是arena.c和malloc.c这两个源文件。

__libc_free

检查free_hook

首先检查是否有自定义的free_hook，与malloc_hook类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void
__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))
    {
      (*hook)(mem, RETURN_ADDRESS (0));
      return;
    }

检查是否为空

然后检查释放的内存是否为NULL，因为free(0)没有意义。

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

检查是否mmap分配

检查free的这块内存是否由mmap分配得到，如果开启mmap分配阈值动态调整机制，空闲chunk大小超过mmap的分配阈值但小于默认最大收缩阈值，会进行分配阈值和收缩阈值的调整，分配阈值调整为该chunk大小，收缩阈值调整为当前chunk大小的2倍，然后释放该chunk。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
  }

tcache初始化

检查tcache是否初始化，这个在malloc中有分析，不再赘述，然后调用_int_free。

1
2
3
4
5
  MAYBE_INIT_TCACHE ();

  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);
}

_int_free

临时变量

同样，首先定义了用到的临时变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
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 */

  size = chunksize (p);

几个检查

首先进行几个检查，首先检查chunk的起始地址是否对齐以及是否大于 -size，然后检查空闲chunk的size是否大于MINSIZE以及size是否对齐；最后检查该chunk的iuse位，防止发生double free。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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))
  malloc_printerr ("free(): invalid pointer");
/* 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)))
  malloc_printerr ("free(): invalid size");

check_inuse_chunk(av, p);

有tcache

检查是否有tcache，如果存在tcache，找到对应大小的tcache链表，遍历该链表，并将其与目标chunk进行比较，如果相等则说明tcache中已经存在该chunk，此时再释放该chunk就发生了double free。如果没有找到且链表未满，则将其插入到该链表中，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
#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size); //根据chunk大小计算tcache索引
    if (tcache != NULL && tc_idx < mp_.tcache_bins)
      {
	/* Check to see if it's already in the tcache.  */
	tcache_entry *e = (tcache_entry *) chunk2mem (p); 

	/* This test succeeds on double free.  However, we don't 100%
	   trust it (it also matches random payload data at a 1 in
	   2^<size_t> chance), so verify it's not an unlikely
	   coincidence before aborting.  */
	if (__glibc_unlikely (e->key == tcache))
	  {
	    tcache_entry *tmp;
	    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
	    for (tmp = tcache->entries[tc_idx];
		 tmp;
		 tmp = tmp->next)
	      if (tmp == e)
		malloc_printerr ("free(): double free detected in tcache 2");
	    /* If we get here, it was a coincidence.  We've wasted a
	       few cycles, but don't abort.  */
	  }

	if (tcache->counts[tc_idx] < mp_.tcache_count)
	  {
	    tcache_put (p, tc_idx);
	    return;
	  }
      }
  }
#endif

fastbin

如果没有开启tcache或者tcache数量已满，考虑fastbin。如果chunk在fastbin范围内，且与top chunk不相邻，则插入到对应bin的头部。不修改chunk的inuse位。

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
#if TRIM_FASTBINS
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)  //如果当前chunk与top chunk不相邻
#endif
      ) {
    
    //下一个chunk的大小不小于2*SIZE_SZ，且不能大于system_mem，一般为132KB，否则就报错
    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))
      {
	bool fail = true;
	/* We might not have a lock at this point and concurrent modifications
	   of system_mem might result in a false positive.  Redo the test after
	   getting the lock.  */
	if (!have_lock)
	  {
	    __libc_lock_lock (av->mutex);
	    fail = (chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem);
	    __libc_lock_unlock (av->mutex);
	  }

	if (fail)
	  malloc_printerr ("free(): invalid next size (fast)");
      }

    //将chunk的数据域设置为 perturb_byte，一般是0
    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    atomic_store_relaxed (&av->have_fastchunks, true);
    unsigned int idx = fastbin_index(size); //根据大小获取fastbin的索引
    fb = &fastbin (av, idx); //获取头指针fb

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    //使用原子操作将p插入到链表头部
    mchunkptr old = *fb, old2;

    if (SINGLE_THREAD_P)
      {
	/* Check that the top of the bin is not the record we are going to
	   add (i.e., double free).  */
  //检查是否发生了double free
	if (__builtin_expect (old == p, 0))
	  malloc_printerr ("double free or corruption (fasttop)");
	p->fd = old;
	*fb = p;
      }
    else
      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))
	    malloc_printerr ("double free or corruption (fasttop)");
	  p->fd = old2 = old;
	}
      while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
	     != old2);

    /* 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
       allocated again.  */
    //检查fastbin头指针的size插入前后是否一致
    if (have_lock && old != NULL
	&& __builtin_expect (fastbin_index (chunksize (old)) != idx, 0))
      malloc_printerr ("invalid fastbin entry (free)");
  }

合并非mmap的空闲chunk

获得锁

首先获得锁，计算它的下一个相邻的chunk，进行轻量级的检查。

1
2
3
4
5
6
7
8
9
10
else if (!chunk_is_mmapped(p)) {

  /* If we're single-threaded, don't lock the arena.  */
  if (SINGLE_THREAD_P)
    have_lock = true;

  if (!have_lock)
    __libc_lock_lock (av->mutex);

  nextchunk = chunk_at_offset(p, 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
   /* Lightweight tests: check whether the block is already the
      top block.  */
   //检查当前free的chunk是否为top chunk
   if (__glibc_unlikely (p == av->top))
     malloc_printerr ("double free or corruption (top)");
   
   //检查nextchunk是否超过了当前分配区的边界
   /* 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))
malloc_printerr ("double free or corruption (out)");
   
   //检查当前free的chunk的inuse位是否为1，如果不是则说明该chunk已经是一个freed chunk，发生了double free.
   /* Or whether the block is actually not marked used.  */
   if (__glibc_unlikely (!prev_inuse(nextchunk)))
     malloc_printerr ("double free or corruption (!prev)");
   
   //检查下一个chunk的大小是否大于MINSIZE，是否超过system_mem
   nextsize = chunksize(nextchunk);
   if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
     malloc_printerr ("free(): invalid next size (normal)");
   
   //将当前要释放的chunk的数据域进行perturb_byte填充，通常是清0
   free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

后向合并（前一个chunk）

先考虑低物理地址的chunk，也就是进行前一个chunk的合并。

1
2
3
4
5
6
7
8
9
10
11
/* consolidate backward */
if (!prev_inuse(p)) { //如果前一个chunk是空闲状态
  prevsize = prev_size (p); //计算前一个chunk的size
  size += prevsize; //合并后的size
  p = chunk_at_offset(p, -((long) prevsize));  //p指向前一个chunk

  //检查前一个chunk的size是否与prevsize相等，避免fake chunk
  if (__glibc_unlikely (chunksize(p) != prevsize)) 
    malloc_printerr ("corrupted size vs. prev_size while consolidating");
  unlink_chunk (av, p); 
}

前向合并（后一个chunk）

后一个chunk不是top chunk

如果后一个chunk不是top chunk，且处于空闲状态，将其与p合并，并插入到unsorted bin的头部。

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
   if (nextchunk != av->top) { //如果后一个chunk不是top chunk
     /* get and clear inuse bit */
     nextinuse = inuse_bit_at_offset(nextchunk, nextsize); //获取nextchunk的inuse位的值

     /* consolidate forward */
     if (!nextinuse) { //后一个chunk处于空闲状态
unlink_chunk (av, nextchunk); //将nextchunk进行解链
size += nextsize;  //合并后的size
     } else
clear_inuse_bit_at_offset(nextchunk, 0); //如果nextchunk不是空闲chunk，则将该chunk的prev_inuse位置0，标志它的前一个chunk即p是空闲chunk

     /*
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.
     */
     //合并后的chunk插入到unsorted bin的头部
     bck = unsorted_chunks(av); //unsorted bin的头指针
     fwd = bck->fd;     
     //检查后插入到链表头部
     if (__glibc_unlikely (fwd->bk != bck))  
malloc_printerr ("free(): corrupted unsorted chunks");
     p->fd = fwd; 
     p->bk = bck;
     //如果是largebin，则清空nextsize域
     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是top chunk

如果目标chunk与top chunk相邻，则将其与top chunk合并，并更新其size域。

1
2
3
4
5
6
7
8
9
10
11
12

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

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

fastbin的合并

判断合并后的size是否超过FASTBIN_CONSOLIDATION_THRESHOLD，默认为64KB，如果超过则进行fastbin的合并，遍历fastbin的chunk，并将bin中相邻的空闲chunk进行合并，合并后的chunk插入到unsorted bin中，fastbin清空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   /*
     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 (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate(av);

top chunk的收缩

判断top chunk是否超过mmap的收缩阈值，收缩后free函数结束退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
      if (av == &main_arena) {  //当前分配区是主分配区
#ifndef MORECORE_CANNOT_TRIM
  //超过mmap的收缩阈值，默认为128KB
	if ((unsigned long)(chunksize(av->top)) >=
	    (unsigned long)(mp_.trim_threshold))
	  systrim(mp_.top_pad, av); //top chunk的收缩，但最开始分配的128KB不会归还给系统
#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); //进行sub_heap的收缩，如果top chunk是整个sub_heap，会把整个sub_heap都归还系统
      }
    }

    if (!have_lock)
      __libc_lock_unlock (av->mutex);
  }

释放mmap的chunk

如果chunk不是fastbin范围内，且是mmap的chunk，就调用munmap进行释放，free函数结束，退出。

1
2
3
4
  else {
    munmap_chunk (p);
  }
}

unlink

将chunk从一个双向链表中取出，p是目标chunk，如果是largebin，还要涉及到nextsize的解链。

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
/* Take a chunk off a bin list.  */
static void
unlink_chunk (mstate av, mchunkptr p)
{
  //首先检查当前chunk的size是否与p后一个chunk的prev_size相等，因为p是freed chunk，所以有两个地方记录其size
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");

  mchunkptr fd = p->fd; 
  mchunkptr bk = p->bk;
  
  //检查p->fd->bk是否为p，p->bk->fd是否为p，防止篡改freed chunk的fd和bk
  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");
  
  
  fd->bk = bk; //将p的下一个chunk的bk指向p的前一个chunk
  bk->fd = fd; //将p的前一个chunk的fd指向p的后一个chunk，记为nextchunk

  //解链的p是largebin，且p的nextsize不为空，如果为空则说明p的前一个chunk与p的大小相同，不需要修改nextsize
  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    {
      //检查p的后一个chunk的bk_nextsize是否指向p，p的前一个chunk的fd_nextsize是否指向p，类似于fd和bk的检查
      if (p->fd_nextsize->bk_nextsize != p
	  || p->bk_nextsize->fd_nextsize != p)
	malloc_printerr ("corrupted double-linked list (not small)");
  
      //如果p的后一个chunk的nextsize域为空，有两种情况：
      //1.p的后一个chunk与p大小相同
      //2.在nextsize链表中只有p一个chunk
      if (fd->fd_nextsize == NULL)
	{
	  if (p->fd_nextsize == p)  //只有p一个chunk
	    fd->fd_nextsize = fd->bk_nextsize = fd;  
	  else
	    {
	      fd->fd_nextsize = p->fd_nextsize;  //将p的nextchunk的fd_nextsize指向p的fd_nextsize
	      fd->bk_nextsize = p->bk_nextsize;  //将p的nextchunk的bk_nextsize指向p的bk_nextsize
	      p->fd_nextsize->bk_nextsize = fd;  //在nextsize链表中，将p的fd的bk_nextsize指向p的nextchunk
	      p->bk_nextsize->fd_nextsize = fd;  //在nextsize链表中，将p的bk的fd_nextsize指向p的nextchunk
	    }
	}
      else
	{  //p的后一个chunk与p大小不同，类似于fd和bk的解链
	  p->fd_nextsize->bk_nextsize = p->bk_nextsize; 
	  p->bk_nextsize->fd_nextsize = p->fd_nextsize;
	}
    }
}

malloc_consolidate

该函数将遍历fastbin中的chunk，对相邻的空闲chunk进行合并，首先尝试与前一个chunk进行合并，如果该chunk与top chunk相邻，则继续与top chunk合并；否则尝试与后一个chunk合并，合并后将chunk其插入到unsorted bin中。

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

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

  atomic_store_relaxed (&av->have_fastchunks, false);

  unsorted_bin = unsorted_chunks(av); //unsorted bin的头指针

  /*
    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.
  */
  //遍历fastbins
  maxfb = &fastbin (av, NFASTBINS - 1); 
  fb = &fastbin (av, 0); //fb是每个bin的头指针
  do {
    p = atomic_exchange_acq (fb, NULL); //p是每个bin中的chunk
    if (p != 0) { //遍历bin中的每个chunk
      do {
	{
    //检查chunk与bin的size是否一致
	  unsigned int idx = fastbin_index (chunksize (p)); 
	  if ((&fastbin (av, idx)) != fb)
	    malloc_printerr ("malloc_consolidate(): invalid chunk size");
	}

	check_inuse_chunk(av, p);
	nextp = p->fd; //获取p的后一个chunk

	/* Slightly streamlined version of consolidation code in free() */
	size = chunksize (p);
	nextchunk = chunk_at_offset(p, size);
	nextsize = chunksize(nextchunk);

	if (!prev_inuse(p)) { //如果p的前一个chunk是空闲chunk
	  prevsize = prev_size (p);
	  size += prevsize;
	  p = chunk_at_offset(p, -((long) prevsize)); //p指向前一个chunk
	  if (__glibc_unlikely (chunksize(p) != prevsize))  //检查前一个chunk的size
	    malloc_printerr ("corrupted size vs. prev_size in fastbins");
	  unlink_chunk (av, p); //将前一个chunk解链
	}

	if (nextchunk != av->top) { //如果p的后一个chunk不是top chunk
	  nextinuse = inuse_bit_at_offset(nextchunk, nextsize); 

	  if (!nextinuse) { //p的后一个chunk是空闲chunk
	    size += nextsize;
	    unlink_chunk (av, nextchunk); //对后一个chunk进行解链
	  } else
	    clear_inuse_bit_at_offset(nextchunk, 0); 
    
    //将合并后的chunk插入到unsorted bin的头部
	  first_unsorted = unsorted_bin->fd; //获取unsorted bin的第一个chunk
	  unsorted_bin->fd = p; //将unsorted bin的头指针指向p
	  first_unsorted->bk = p; //将第一个chunk的bk指向p

    //如果是largebin，则清空nextsize域
	  if (!in_smallbin_range (size)) {
	    p->fd_nextsize = NULL;
	    p->bk_nextsize = NULL;
	  }
    
    //设置size域
	  set_head(p, size | PREV_INUSE);
	  p->bk = unsorted_bin;  //将p的bk指向unsorted bin的头指针
	  p->fd = first_unsorted; //将p的fd指向unsorted bin原来的第一个chunk
	  set_foot(p, size);
	}

	else {  //p与top chunk相邻，与top chunk进行合并
	  size += nextsize;
	  set_head(p, size | PREV_INUSE);
	  av->top = p;
	}

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

    }
  } while (fb++ != maxfb);
}

参考

https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/implementation/free-zh/
《glibc内存管理ptmalloc源代码分析@华庭》