Glibc realloc function procedure analysis

glibc2.32 source code: malloc.c - realloc part

Wrapper:

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
void *
__libc_realloc (void *oldmem, size_t bytes)
{
  mstate ar_ptr;
  INTERNAL_SIZE_T nb;         /* padded request size */

  void *newp;             /* chunk to return */

  /* exec hook function if exist */
  void *(*hook) (void *, size_t, const void *) =
    atomic_forced_read (__realloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));

  /* realloc size == 0 equal to call free() */
#if REALLOC_ZERO_BYTES_FREES
  if (bytes == 0 && oldmem != NULL)
    {
      __libc_free (oldmem); return 0;
    }
#endif

  /* realloc of null is supposed to be same as malloc */
  if (oldmem == 0)
    return __libc_malloc (bytes);

  /* chunk corresponding to oldmem */
  const mchunkptr oldp = mem2chunk (oldmem);
  /* its size */
  const INTERNAL_SIZE_T oldsize = chunksize (oldp);

  if (chunk_is_mmapped (oldp))
    ar_ptr = NULL;
  else
    {
      MAYBE_INIT_TCACHE ();
      ar_ptr = arena_for_chunk (oldp);
    }
	/* do some check */
  	// ...
    }

  /* if chunk is mmapped */
  if (chunk_is_mmapped (oldp))
    {
      /* ... 
      	... */
    }

  if (SINGLE_THREAD_P)
    {
      newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
      assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
	      ar_ptr == arena_for_chunk (mem2chunk (newp)));

      return newp;
    }

  __libc_lock_lock (ar_ptr->mutex);

  newp = _int_realloc (ar_ptr, oldp, oldsize, nb);

/* ...... */
  return newp;
}

基本流程：

  • 如果realloc的size为零，等于调用free
  • 如果传入的地址为空，完全等价于malloc
  • 否则，进入真正的_int_realloc

_int_realloc function:

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

void*
_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
	     INTERNAL_SIZE_T nb)
{
  mchunkptr        newp;            /* chunk to return */
  INTERNAL_SIZE_T  newsize;         /* its size */
  void*          newmem;          /* corresponding user mem */

  mchunkptr        next;            /* next contiguous chunk after oldp */

  mchunkptr        remainder;       /* extra space at end of newp */
  unsigned long    remainder_size;  /* its size */

  /* oldmem size */
  if (__builtin_expect (chunksize_nomask (oldp) <= 2 * SIZE_SZ, 0)
      || __builtin_expect (oldsize >= av->system_mem, 0))
    malloc_printerr ("realloc(): invalid old size");

  check_inuse_chunk (av, oldp);

  /* All callers already filter out mmap'ed chunks.  */
  assert (!chunk_is_mmapped (oldp));

  next = chunk_at_offset (oldp, oldsize);
  INTERNAL_SIZE_T nextsize = chunksize (next);
  if (__builtin_expect (chunksize_nomask (next) <= 2 * SIZE_SZ, 0)
      || __builtin_expect (nextsize >= av->system_mem, 0))
    malloc_printerr ("realloc(): invalid next size");

  if ((unsigned long) (oldsize) >= (unsigned long) (nb))
    {
      /* already big enough; split below */
      newp = oldp;
      newsize = oldsize;
    }

  else
    {
      /* Try to expand forward into top */
      if (next == av->top &&
          (unsigned long) (newsize = oldsize + nextsize) >=
          (unsigned long) (nb + MINSIZE))
        {
          set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
          av->top = chunk_at_offset (oldp, nb);
          set_head (av->top, (newsize - nb) | PREV_INUSE);
          check_inuse_chunk (av, oldp);
          return chunk2mem (oldp);
        }

      /* Try to expand forward into next chunk;  split off remainder below */
      else if (next != av->top &&
               !inuse (next) &&
               (unsigned long) (newsize = oldsize + nextsize) >=
               (unsigned long) (nb))
        {
          newp = oldp;
          unlink_chunk (av, next);
        }

      /* allocate, copy, free */
      else
        {
          newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
          if (newmem == 0)
            return 0; /* propagate failure */

          newp = mem2chunk (newmem);
          newsize = chunksize (newp);

          /*
             Avoid copy if newp is next chunk after oldp.
           */
          if (newp == next)
            {
              newsize += oldsize;
              newp = oldp;
            }
          else
            {
	      memcpy (newmem, chunk2mem (oldp), oldsize - SIZE_SZ);
              _int_free (av, oldp, 1);
              check_inuse_chunk (av, newp);
              return chunk2mem (newp);
            }
        }
    }

  /* If possible, free extra space in old or extended chunk */

  assert ((unsigned long) (newsize) >= (unsigned long) (nb));

  remainder_size = newsize - nb;

  if (remainder_size < MINSIZE)   /* not enough extra to split off */
    {
      set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
      set_inuse_bit_at_offset (newp, newsize);
    }
  else   /* split remainder */
    {
      remainder = chunk_at_offset (newp, nb);
      set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
      set_head (remainder, remainder_size | PREV_INUSE |
                (av != &main_arena ? NON_MAIN_ARENA : 0));
      /* Mark remainder as inuse so free() won't complain */
      set_inuse_bit_at_offset (remainder, remainder_size);
      _int_free (av, remainder, 1);
    }

  check_inuse_chunk (av, newp);
  return chunk2mem (newp);
}

其中在代码开始有一个check inuse chunk，主要是检查当前请求realloc的堆块，宏定义展开就是这个函数，拿出来看一下:

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
static void
do_check_inuse_chunk (mstate av, mchunkptr p)
{
  mchunkptr next;

  do_check_chunk (av, p);

  if (chunk_is_mmapped (p))
    return; /* mmapped chunks have no next/prev */

  /* Check whether it claims to be in use ... */
  assert (inuse (p));

  next = next_chunk (p);

  /* ... and is surrounded by OK chunks.
     Since more things can be checked with free chunks than inuse ones,
     if an inuse chunk borders them and debug is on, it's worth doing them.
   */
  if (!prev_inuse (p))
    {
      /* Note that we cannot even look at prev unless it is not inuse */
      mchunkptr prv = prev_chunk (p);
      assert (next_chunk (prv) == p);
      do_check_free_chunk (av, prv);
    }

  if (next == av->top)
    {
      assert (prev_inuse (next));
      assert (chunksize (next) >= MINSIZE);
    }
  else if (!inuse (next))
    do_check_free_chunk (av, next);
}

check流程：

  • 先调用check chunk，这个先不详细看了
  • check此堆块是不是在使用,如果是空闲状态会报错
  • 取next_chunk，如果前一个堆块是空闲的进入if，check前一个堆块后面是不是本堆块，当然了如果前一个堆块正在使用，就没必要check。
  • 然后如果下一个堆块是top chunk的话，check top chunk的preinuse位和size位
  • 如果下一个堆块不是top chunk且是空闲状态，check free chunk，和检查前一个空闲堆块一样调用do check free chunk

过了check之后要检查下一个chunk的size合法性即大于两倍的SIZE_SZ且小于av->system_mem，然后开始真正的realloc：

情况一：如果旧的size大于请求的新size，直接切，即先赋值newp = oldp; newsize = oldsize;然后remainder_size = newsize - nb;如果remainder能够成为一个新chunk(即大于chunk的MINSIZE)，就把它free掉，返回新的chunk内容地址（也就是原地址），不过chunk大小变小了。

情况二：如果请求的size大于原来的size，流程稍微复杂一点：

  • 如果下一个堆块是top chunk的话并且old size+top chunk size大于请求的chunk大小，也就是说剩余的topchunk大小可以补足原来的chunk以满足请求,切top chunk即可，并返回原地址。
  • 如果下一个堆块不是top chunk且下一个堆块是空闲的，并且加上当前堆块的大小能够满足请求的大小，调用unlink_chunk(av, next);放在后面分析
  • 如果不是以上两种情况，也就是说当前堆块的连续后面没有可用的空闲内存，此时就会调用malloc，让allocator调用malloc(request_size - MALLOC_ALIGN_MASK)，但是malloc有可能返回的是旧堆块的连续下一块内存（不是已经过了第二个if么，为什么还会malloc到地址连续的空闲堆块呢？这不矛盾吗wtf），这种情况下还是会把这俩合并，剩余的切割，然后返回给用户。如果新堆块不是连续的，则copy原来的数据过去，返回新的堆块内存，并把原来的堆块释放掉。

最后来看看unlink_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
/* Take a chunk off a bin list.  */
static void
unlink_chunk (mstate av, mchunkptr p)
{
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;

  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");

  fd->bk = bk;
  bk->fd = fd;
  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    {
      if (p->fd_nextsize->bk_nextsize != p
	  || p->bk_nextsize->fd_nextsize != p)
	malloc_printerr ("corrupted double-linked list (not small)");

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

传入参数的是next堆块指针，首先会检查size和presize是否匹配；然后检查双向链表完整性（也就是说，只针对于bin中的空闲chunk？realloc不会考虑tcache?），check完就执行unlink，而且如果是largebin的话会复杂一点。

Poc:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    void *a,*b,*c,*d;
    void *cache[7];

    a = malloc(0x100);
    b = malloc(0x160);

    for(int i=0;i<7;i++)
        cache[i] = malloc(0x160);

    for (int i=0;i<7;i++)
        free(cache[i]);

    free(b); //unsortedbin
    malloc(0x200); // consolidate unsortedbin
    sleep(0);


    d = realloc(a,0x160);
    sleep(0);
    return 0;
}

before realloc:

1
2
3
4
5
6
7
8
9
10
11
12
13
pwndbg> par
addr                prev                size                 status              fd                bk
0x555555559000      0x0                 0x290                Used                None              None
0x555555559290      0x0                 0x110                Used                None              None
0x5555555593a0      0x0                 0x170                Freed     0x7ffff7fa5d40    0x7ffff7fa5d40
0x555555559510      0x170               0x170                Freed                0x0              None
0x555555559680      0x0                 0x170                Freed     0x555555559520              None
0x5555555597f0      0x0                 0x170                Freed     0x555555559690              None
0x555555559960      0x0                 0x170                Freed     0x555555559800              None
0x555555559ad0      0x0                 0x170                Freed     0x555555559970              None
0x555555559c40      0x0                 0x170                Freed     0x555555559ae0              None
0x555555559db0      0x0                 0x170                Freed     0x555555559c50              None
0x555555559f20      0x0                 0x210                Used                None              None

after realloc:

1
2
3
4
5
6
7
8
9
10
11
12
13
pwndbg> par
addr                prev                size                 status              fd                bk
0x555555559000      0x0                 0x290                Used                None              None
0x555555559290      0x0                 0x170                Used                None              None
0x555555559400      0x0                 0x110                Freed                0x0              None
0x555555559510      0x170               0x170                Freed                0x0              None
0x555555559680      0x0                 0x170                Freed     0x555555559520              None
0x5555555597f0      0x0                 0x170                Freed     0x555555559690              None
0x555555559960      0x0                 0x170                Freed     0x555555559800              None
0x555555559ad0      0x0                 0x170                Freed     0x555555559970              None
0x555555559c40      0x0                 0x170                Freed     0x555555559ae0              None
0x555555559db0      0x0                 0x170                Freed     0x555555559c50              None
0x555555559f20      0x0                 0x210                Used                None              None

总结一下：

一般情况realloc不会合并前面的空闲堆块，一般向下寻找可用的堆块，如果找不到就去malloc新的然后copy、free。

另外，realloc有两个会调用free的地方，一是realloc(addr,0)的时候，等价于free；二是申请比原来小的size，会把剩下的那部分free掉，无论是合并新的堆块还是申请的size，只要new size大于request size都要切割（如果能够满足切割成最小堆块或更大的话），会通过free释放。