Post

[glibc 2.23] ptmalloc2 분석(1)

Posted
By hogbal 64 min read

개요

시스템 해킹을 heap 공격기법은 공부했지만, malloc과 free 함수의 오픈소스도 분석하면 좋을 것 같아서 glibc 2.23 버전부터 소스코드를 토대로 분석하고자 합니다. 해당 포스터를 읽기 위해 heap에 대해서 어느정도 알 고 있어야 이해가 가능합니다!

malloc 분석

__libc_malloc

__libc_malloc 함수는 다음과 같은 구조를 가지고 있습니다.

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

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

  if (ar_ptr != NULL)
    (void) mutex_unlock (&ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}
libc_hidden_def (__libc_malloc)

atomic_forced_read

해당 함수는 매크로로 아래와 같이 선언되어 있습니다.

1
2
3
4
5

#ifndef atomic_forced_read
# define atomic_forced_read(x) \
  ({ __typeof (x) __x; __asm ("" : "=r" (__x) : "0" (x)); __x; })
#endif

인자로 넘어온 변수와 같은 자료형으로 __x 변수를 선언한뒤, 인자로 넘어온 x의 값을 읽어 __x 변수에 저장합니다.

1
2
3
4

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 함수에서 위의 부분은 hook 변수에 __malloc_hook의 값을 가져오고 해당 값이 0이 아니라면 hook 변수에 들어있는 주소를 실행하게 됩니다. 이 때, 함수의 인자는 malloc 함수에 전달되는 첫번째 인자인 bytes 입니다.

arena_get

해당 함수 또한 매크로로 아래와 같이 선언되어 있습니다.

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

#define arena_get(ptr, size) do {             \
      ptr = thread_arena;						          \
      arena_lock (ptr, size);						      \
  } while (0)
  
#define arena_lock(ptr, size) do {					   \
      if (ptr && !arena_is_corrupt (ptr))			 \
        (void) mutex_lock (&ptr->mutex);			 \
      else								                     \
        ptr = arena_get2 ((size), NULL);			 \
  } while (0)
  
#define arena_is_corrupt(A)	(((A)->flags & ARENA_CORRUPTION_BIT))

반복문으로 arena_lock 함수를 호출하고, arena_lock 함수는 arena_is_corrupt 함수의 결과가 거짓이라면 arena_get2 함수를 호출합니다.

💡 여기서 arena_is_corrupt 결과가 거짓이라는 것은 적합하지 않는 영역을 참조할 경우 발생하게 됩니다.

arena_get2 함수는 다음과 같습니다.

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

static mstate
internal_function
arena_get2 (size_t size, mstate avoid_arena)
{
  mstate a;

  static size_t narenas_limit;

  a = get_free_list ();
  if (a == NULL)
    {
      /* Nothing immediately available, so generate a new arena.  */
      if (narenas_limit == 0)
        {
          if (mp_.arena_max != 0)
            narenas_limit = mp_.arena_max;
          else if (narenas > mp_.arena_test)
            {
              int n = __get_nprocs ();

              if (n >= 1)
                narenas_limit = NARENAS_FROM_NCORES (n);
              else
                /* We have no information about the system.  Assume two
                   cores.  */
                narenas_limit = NARENAS_FROM_NCORES (2);
            }
        }
    repeat:;
      size_t n = narenas;
      /* NB: the following depends on the fact that (size_t)0 - 1 is a
         very large number and that the underflow is OK.  If arena_max
         is set the value of arena_test is irrelevant.  If arena_test
         is set but narenas is not yet larger or equal to arena_test
         narenas_limit is 0.  There is no possibility for narenas to
         be too big for the test to always fail since there is not
         enough address space to create that many arenas.  */
      if (__glibc_unlikely (n <= narenas_limit - 1))
        {
          if (catomic_compare_and_exchange_bool_acq (&narenas, n + 1, n))
            goto repeat;
          a = _int_new_arena (size);
	  if (__glibc_unlikely (a == NULL))
            catomic_decrement (&narenas);
        }
      else
        a = reused_arena (avoid_arena);
    }
  return a;
}

위의 함수를 간략하게 요약하면, 메모리 할당을 관리하는 데 사용되며 새로운 arena를 생성하거나 기존의 arena를 재활용하는 역할을 수행하게 됩니다. 반환값은 arena 주소 입니다.

💡 따라서, __libc_malloc 함수에서 arena_get 함수를 통해 첫번째 인자인 ar_ptr 변수에 arena의 주소를 담게 됩니다.

_int_malloc

해당 함수가 malloc에서 많은 처리를 하는 함수입니다. 여기서 흔히 알고있는 로직을 처리하게 됩니다. 함수의 내용이 너무 많아서 부분별로 설명드리겠습니다. 전체 코드는 링크를 확인하시면 좋을 것 같습니다.

  1. nb 변수 값 할당
1

checked_request2size (bytes, nb);

인자로 전달되는 할당되는 메모리 크기를 의미하는 bytes 변수가 전달되게 됩니다. 여기서 checked_request2size 함수는 다음과 같습니다.

1
2
3
4
5
6

#define checked_request2size(req, sz)        \
  if (REQUEST_OUT_OF_RANGE (req)) {					 \
      __set_errno (ENOMEM);						       \
      return 0;								               \
    }									                       \
  (sz) = request2size (req);

checked_request2size 함수에서 입력받은 크기에 대해서 패딩을 추가해서 사이즈를 조절한 뒤, nb 변수에 저장되게 됩니다.

  1. arena를 사용하지 않을 경우

이후, arena를 사용하지 않는 다면 아래의 로직이 실행되게 됩니다.

1
2
3
4
5
6
7
8
9

/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
				alloc_perturb (p, bytes);
      return p;
    }

sysmalloc 함수가 호출되어 주소가 할당되고 반환되지만, 대부분의 glibc에서 arena를 사용하기 떄문에 간단하게 넘어가겠습니다.

  1. fastbin 크기의 chunk를 할당할 경우

다음 로직으로 fastbin을 사용할 경우 아래의 로직이 실행됩니다. 아래의 로직을 순서대로 설명드리겠습니다.

💡 glibc 2.23에서 tcache의 개념이 없기 때문에 해당 순서로 실행이 됩니다.

1
2
3
4
5

#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

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

/*
   If the size qualifies as a fastbin, first check corresponding bin.
   This code is safe to execute even if av is not yet initialized, so we
   can try it without checking, which saves some time on this fast path.
 */

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
  {
    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx);
    mchunkptr pp = *fb;
    do
      {
        victim = pp;
        if (victim == NULL)
          break;
      }
    while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
           != victim);
    if (victim != 0)
      {
        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;
          }
        check_remalloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }
  }

우선 아래의 부분에서 fastbin_index 함수를 통해서 fastbin의 인덱스를 가져와서 idx 변수에 저장합니다. 이렇게 저장된 idx 변수와 arena 주소가 저장되어있는 av 변수가 인자로 들어가서 fastbin 함수가 실행되며 fastbin의 주소를 가져와서 fb 변수에 저장합니다.

1
2
3

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

이후 가져온 fastbin 주소에 대해서 반복문을 돌면서 pp 변수와 victim 변수의 값이 같지 않을 경우 fd가 NULL인 부분까지 반복하게 됩니다.

1
2
3
4
5
6
7
8

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

💡 여기서 “pp 변수와 victim 변수의 값이 같지 않을 경우”와 같은 로직이 있는 경우, 무한 반복문을 막기 위해서 존재한다고 생각했습니다.

이후, victim 변수의 값이 0이 아니면 아래의 로직이 실행됩니다. 여기서 위의 반복문으로 찾은 주소가 fastbin_index 함수로 다시 들어가게 되고 반환깂이 idx와 다르다면 에러가 발생하게 됩니다.

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

if (victim != 0)
  {
    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;
      }
    check_remalloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }

만약 에러가 발생하지 않는다면, check_remalloced_chunk 함수를 통해서 해당 영역의 chunk를 검사합니다. 해당 함수는 아래와 같습니다.

1

# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)

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

static void
do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
  INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);

  if (!chunk_is_mmapped (p))
    {
      assert (av == arena_for_chunk (p));
      if (chunk_non_main_arena (p))
        assert (av != &main_arena);
      else
        assert (av == &main_arena);
    }

  do_check_inuse_chunk (av, p);

  /* Legal size ... */
  assert ((sz & MALLOC_ALIGN_MASK) == 0);
  assert ((unsigned long) (sz) >= MINSIZE);
  /* ... and alignment */
  assert (aligned_OK (chunk2mem (p)));
  /* chunk is less than MINSIZE more than request */
  assert ((long) (sz) - (long) (s) >= 0);
  assert ((long) (sz) - (long) (s + MINSIZE) < 0);
}

정상적인 chunk인 경우 malloc의 반환값이 chunk의 data 영역을 가르키기 때문에 해당 영역을 가르키기 위한 chunk2mem 함수를 호출하여 변수 p에 반환값을 저장합니다.

1

#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))

이후, 반환되기 전에 마지막으로 alloc_perturb 함수가 호출되게 됩니다. 다만 조건문에서 사용되는 perturb_byte 변수의 기본 값이 0이기 때문에 작동하는 일이 거의 없습니다.

1
2
3
4
5
6
7
8

static int perturb_byte;

static void
alloc_perturb (char *p, size_t n)
{
  if (__glibc_unlikely (perturb_byte))
    memset (p, perturb_byte ^ 0xff, n);
}
  1. smallbin 크기의 chunk를 할당할 경우

만약 smallbin을 사용할 경우 아래의 로직이 실행되게 됩니다.

1
2
3
4
5
6
7
8
9

#define last(b)      ((b)->bk)

#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3)) \
   + SMALLBIN_CORRECTION)
   
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

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

if (in_smallbin_range (nb))
  {
    idx = smallbin_index (nb);
    bin = bin_at (av, idx);

  if ((victim = last (bin)) != bin)
      {
        if (victim == 0) /* initialization check */
          malloc_consolidate (av);
        else
          {
            bck = victim->bk;
						if (__glibc_unlikely (bck->fd != victim))
              {
                errstr = "malloc(): smallbin double linked list corrupted";
                goto errout;
              }
            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;
          }
      }
  }

fastbin과 비슷하게 smallbin_index 함수를 통해 idx 변수를 초기화합니다. 그리고 bin_at 함수를 통해 bin의 주소를 가져옵니다.

1
2

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

이후, victim 변수에 last 함수를 통해 bin의 마지막 주소를 저장하고 그 값이 bin 변수의 값과 다르다면 if문이 실행됩니다.

1

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

만약 위의 조건문이 True라서 실행이 되다가 victim 변수가 0이라면 malloc_consolidate 함수를 호출하여 초기화를 진행합니다(5번 이후에 해당 함수를 설명드리겠습니다). 0이 아니라면 새로 할당하는 chunk에 대해서 흔히 알고있는 smallbin과 관련된 초기화를 진행하고 주소를 반환하게 됩니다.

💡 해당 로직에서 smallbin에서 double link가 되어있는지 검증하는 로직이 존재합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
  {
    errstr = "malloc(): smallbin double linked list corrupted";
    goto errout;
  }
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;
  1. largebin크기의 chunk를 할당할 경우

fastbin도 아니고 smallbin도 아닐 경우 아래의 로직이 실행됩니다.

💡 여기서 로직이 간단한 이유는 else 문 아래에서 더 많은 처리를 하게 됩니다. 만약, fastbin과 smallbin 영역이지만 할당받을 청크가 없더라도 else 문 아래의 로직까지 가게 됩니다.

1

#define have_fastchunks(M)     (((M)->flags & FASTCHUNKS_BIT) == 0)

1
2
3
4
5
6

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

만약 have_fastchunks 함수의 결과가 True라면 malloc_consolidate 함수가 호출됩니다. malloc_consolidate 함수는 다음과 같습니다.

💡 해당 함수를 통해 사용되지 않는 chunk를 병합하면서 단편화를 해결할 수 있습니다.

1

#define clear_fastchunks(M)    catomic_or (&(M)->flags, FASTCHUNKS_BIT)

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

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

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

    maxfb = &fastbin (av, NFASTBINS - 1);
    fb = &fastbin (av, 0);
    do {
      p = atomic_exchange_acq (fb, 0);
      if (p != 0) {
				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(av, p, bck, fwd);
				  }
			
				  if (nextchunk != av->top) {
				    nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
			
				    if (!nextinuse) {
				      size += nextsize;
				      unlink(av, nextchunk, bck, fwd);
				    } else
				      clear_inuse_bit_at_offset(nextchunk, 0);
			
				    first_unsorted = unsorted_bin->fd;
				    unsorted_bin->fd = p;
				    first_unsorted->bk = p;
			
				    if (!in_smallbin_range (size)) {
				      p->fd_nextsize = NULL;
				      p->bk_nextsize = NULL;
				    }
			
				    set_head(p, size | PREV_INUSE);
				    p->bk = unsorted_bin;
				    p->fd = first_unsorted;
				    set_foot(p, size);
				  }
			
				  else {
				    size += nextsize;
				    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);
  }
}

우선 get_max_fast 함수의 결과가 0이 아닐 경우 clear_fastchunks 함수를 통해 arena의 flags를 변경합니다. 그리고 unsorted_bin의 주소와 fastbin의 주소를 가져옵니다.

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

clear_fastchunks(av);

unsorted_bin = unsorted_chunks(av);

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

maxfb = &fastbin (av, NFASTBINS - 1);
fb = &fastbin (av, 0);

이후, 아래의 로직이 실행되면서 사용되지 않는 chunk의 합병이 진행되게 됩니다. fastbin 리스트를 반복하며 작동하고 fastbin 리스트 안에 chunk의 끝까지 병합을 진행하게 됩니다. 만약 사용되지 않는 chunk라면 unlink 함수를 통해 연결을 해제하고 다음 chunk가 top을 가리키고 있는지에 따라 다른 동작을 하게 됩니다.

만약 다음 chunk가 top이 아니라면 unsorted_bin에 병합된 chunk가 들어가고 top인 경우 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
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

do {
  p = atomic_exchange_acq (fb, 0);
  if (p != 0) {
		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(av, p, bck, fwd);
		  }
	
		  if (nextchunk != av->top) {
		    nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
	
		    if (!nextinuse) {
		      size += nextsize;
		      unlink(av, nextchunk, bck, fwd);
		    } else
		      clear_inuse_bit_at_offset(nextchunk, 0);
	
		    first_unsorted = unsorted_bin->fd;
		    unsorted_bin->fd = p;
		    first_unsorted->bk = p;
	
		    if (!in_smallbin_range (size)) {
		      p->fd_nextsize = NULL;
		      p->bk_nextsize = NULL;
		    }
	
		    set_head(p, size | PREV_INUSE);
		    p->bk = unsorted_bin;
		    p->fd = first_unsorted;
		    set_foot(p, size);
		  }
	
		  else {
		    size += nextsize;
		    set_head(p, size | PREV_INUSE);
		    av->top = p;
		  }
	
		} while ( (p = nextp) != 0);
	
  }
} while (fb++ != maxfb);

만약 get_max_fast 함수의 값이 0이라면 아래의 로직이 실행됩니다.

1
2

malloc_init_state(av);
check_malloc_state(av);

malloc_init_state 함수는 다음과 같습니다. 함수의 이름 처럼 기본적인 초기화를 진행하게 됩니다. 그리고 check_malloc_state 함수에서 do_check_malloc_state 함수를 호출하며 초기화가 정상적으로 진행되었는지 검증을 진행합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static void
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;

  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;
    }

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  av->flags |= FASTCHUNKS_BIT;

  av->top = initial_top (av);
}
  1. 앞서 할당하지 못한 chunk 할당 - unsorted_bin

첫번째로 할당하지 못했던 chunk를 unsorted_bin에서 찾아서 할당하게 됩니다. 해당 로직은 아래와 같습니다.

💡 앞에서 할당하지 못한 경우 malloc_consolidate 함수를 통해 chunk가 병합되면서 unsorted_bin에 들어가기 때문에 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
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

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
  {
    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);
    size = chunksize (victim);

    /*
       If a small request, try to use last remainder if it is the
       only chunk in unsorted bin.  This helps promote locality for
       runs of consecutive small requests. This is the only
       exception to best-fit, and applies only when there is
       no exact fit for a small chunk.
     */

    if (in_smallbin_range (nb) &&
        bck == unsorted_chunks (av) &&
        victim == av->last_remainder &&
        (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
      {
        /* split and reattach remainder */
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks (av);
        if (!in_smallbin_range (remainder_size))
          {
            remainder->fd_nextsize = NULL;
            remainder->bk_nextsize = NULL;
          }

        set_head (victim, nb | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE);
        set_foot (remainder, remainder_size);

        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }

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

    /* Take now instead of binning if exact fit */

    if (size == nb)
      {
        set_inuse_bit_at_offset (victim, size);
        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;
      }

    /* place chunk in bin */

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

        /* maintain large bins in sorted order */
        if (fwd != bck)
          {
            /* Or with inuse bit to speed comparisons */
            size |= PREV_INUSE;
            /* if smaller than smallest, bypass loop below */
            assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
            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;
              }
            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);
                  }

                if ((unsigned long) size == (unsigned long) fwd->size)
                  /* Always insert in the second position.  */
                  fwd = fwd->fd;
                else
                  {
                    victim->fd_nextsize = fwd;
                    victim->bk_nextsize = fwd->bk_nextsize;
                    fwd->bk_nextsize = victim;
                    victim->bk_nextsize->fd_nextsize = victim;
                  }
                bck = fwd->bk;
              }
          }
        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;

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

위의 로직중 첫번째로 할당하려는 크기가 smallbin 크기이고 bck가 unsorted_chunks (av)와 같고 현재 victim 변수가 last_remainder와 같고 unsorted_bin에 할당하려는 크기보다 큰 chunk가 존재하는 경우 아래의 조건문이 실행됩니다.

해당 로직에서 할당하려는 chunk와 남은 크기의 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

if (in_smallbin_range (nb) &&
    bck == unsorted_chunks (av) &&
    victim == av->last_remainder &&
    (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
  {
    /* split and reattach remainder */
    remainder_size = size - nb;
    remainder = chunk_at_offset (victim, nb);
    unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
    av->last_remainder = remainder;
    remainder->bk = remainder->fd = unsorted_chunks (av);
    if (!in_smallbin_range (remainder_size))
      {
        remainder->fd_nextsize = NULL;
        remainder->bk_nextsize = NULL;
      }

    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);
    set_foot (remainder, remainder_size);

    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }

만약 위의 경우가 아니라면 우선 unsorted_bin에서 제거하고 조건문에 따라 처리됩니다.

1
2
3

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

첫번째로 할당하려는 크기와 unsorted_bin에서 제거된 chunk의 크기가 동일하다면 아래의 로직이 실행되며 바로 주소가 반환되게 됩니다.

1
2
3
4
5
6
7
8
9
10

if (size == nb)
{
  set_inuse_bit_at_offset (victim, size);
  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;
}

두번째로 만약 할당하려는 크기가 아니고 unsorted_bin에서 제거된 chunk의 크기가 smallbin에 속한다면 아래의 로직이 실행되며 smallbin에 들어가게 됩니다.

1
2
3
4
5
6

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

마지막으로 만약 할당하려는 크기가 아니고 unsorted_bin에서 제거된 chunk의 크기가 largebin에 속한다면 아래의 로직이 실행되며 largebin에 들어가게 됩니다.

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

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

  /* maintain large bins in sorted order */
  if (fwd != bck)
    {
      /* Or with inuse bit to speed comparisons */
      size |= PREV_INUSE;
      /* if smaller than smallest, bypass loop below */
      assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
      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;
        }
      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);
            }

          if ((unsigned long) size == (unsigned long) fwd->size)
            /* Always insert in the second position.  */
            fwd = fwd->fd;
          else
            {
              victim->fd_nextsize = fwd;
              victim->bk_nextsize = fwd->bk_nextsize;
              fwd->bk_nextsize = victim;
              victim->bk_nextsize->fd_nextsize = victim;
            }
          bck = fwd->bk;
        }
    }
  else
    victim->fd_nextsize = victim->bk_nextsize = victim;
}

위의 로직이 끝난다면 마지막으로 정보를 업데이트하고 위의 과정을 반복하게 됩니다.

1
2
3
4
5
6
7
8
9

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

#define MAX_ITERS       10000
if (++iters >= MAX_ITERS)
  break;
  1. 앞서 할당하지 못한 chunk 할당 - largebin

만약 unsorted_bin에서 적절한 chunk를 찾지 못했다면 아래의 로직이 수행되면서 largebin에서 찾게 됩니다. largebin의 첫번째 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
59
60
61

if (!in_smallbin_range (nb))
  {
    bin = bin_at (av, idx);

    /* skip scan if empty or largest chunk is too small */
    if ((victim = first (bin)) != bin &&
        (unsigned long) (victim->size) >= (unsigned long) (nb))
      {
        victim = victim->bk_nextsize;
        while (((unsigned long) (size = chunksize (victim)) <
                (unsigned long) (nb)))
          victim = victim->bk_nextsize;

        /* Avoid removing the first entry for a size so that the skip
           list does not have to be rerouted.  */
        if (victim != last (bin) && victim->size == victim->fd->size)
          victim = victim->fd;

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

        /* Exhaust */
        if (remainder_size < MINSIZE)
          {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
              victim->size |= NON_MAIN_ARENA;
          }
        /* Split */
        else
          {
            remainder = chunk_at_offset (victim, nb);
            /* We cannot assume the unsorted list is empty and therefore
               have to perform a complete insert here.  */
            bck = unsorted_chunks (av);
            fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
              {
                errstr = "malloc(): corrupted unsorted chunks";
                goto errout;
              }
            remainder->bk = bck;
            remainder->fd = fwd;
            bck->fd = remainder;
            fwd->bk = remainder;
            if (!in_smallbin_range (remainder_size))
              {
                remainder->fd_nextsize = NULL;
                remainder->bk_nextsize = NULL;
              }
            set_head (victim, nb | PREV_INUSE |
                      (av != &main_arena ? NON_MAIN_ARENA : 0));
            set_head (remainder, remainder_size | PREV_INUSE);
            set_foot (remainder, remainder_size);
          }
        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }
  }

위의 로직에서 할당 받을 수 있는 가장 작은 chunk를 선택해서 unsorted_bin에서 할당하는 것 처럼 2개의 chunk로 나뉘어지게 되고 remainder_size에 따라 조건문이 수행됩니다.

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

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

/* Avoid removing the first entry for a size so that the skip
   list does not have to be rerouted.  */
if (victim != last (bin) && victim->size == victim->fd->size)
  victim = victim->fd;

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

만약 remainder_size가 MINSIZE보다 작다면 아래의 로직이 수행되는데 사용할 수 없는 크기이기 때문에 그냥 inuse bit를 설정해버리고 non_main_arena bit도 설정합니다.

1
2
3
4
5
6
7

/* Exhaust */
if (remainder_size < MINSIZE)
  {
    set_inuse_bit_at_offset (victim, size);
    if (av != &main_arena)
      victim->size |= NON_MAIN_ARENA;
  }

또는 remainder_size가 MINSIZE보다 크거나 같다면 아래의 로직이 실행됩니다.

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

else
  {
    remainder = chunk_at_offset (victim, nb);
    /* We cannot assume the unsorted list is empty and therefore
       have to perform a complete insert here.  */
    bck = unsorted_chunks (av);
    fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
      {
        errstr = "malloc(): corrupted unsorted chunks";
        goto errout;
      }
    remainder->bk = bck;
    remainder->fd = fwd;
    bck->fd = remainder;
    fwd->bk = remainder;
    if (!in_smallbin_range (remainder_size))
      {
        remainder->fd_nextsize = NULL;
        remainder->bk_nextsize = NULL;
      }
    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);
    set_foot (remainder, remainder_size);
  }

위 로직에서 다시 remainder chunk가 unsorted_bin에 들어가게 됩니다.

💡 해당 로직에서 연결리스트에 대해서 검증(fwd->bk != bck)을 진행하게 됩니다.

이후, 다음과 같이 주소값을 설정하고 반환하게 됩니다.

1
2
3
4

check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
  1. 앞서 할당하지 못한 chunk 할당 - binmap

위의 2개에서도 할당하지 못했다면 binmap에서 할당하게 됩니다. 해당 로직은 다음과 같습니다. 해당 로직에서 할당할 수 있는 chunk가 있을 만한 곳에 대해 탐색하면서 BINMAPSIZE를 넘어가기 전에 찾게 된다면 할당하고 넘어간다면 use_top으로 분기하게 됩니다.

💡 여기서 할당하는 과정은 위에서 설명한것과 유사하기 때문에 넘어가겠습니다.

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

++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);

for (;; )
  {
    /* Skip rest of block if there are no more set bits in this block.  */
    if (bit > map || bit == 0)
      {
        do
          {
            if (++block >= BINMAPSIZE) /* out of bins */
              goto use_top;
          }
        while ((map = av->binmap[block]) == 0);

        bin = bin_at (av, (block << BINMAPSHIFT));
        bit = 1;
      }

    /* Advance to bin with set bit. There must be one. */
    while ((bit & map) == 0)
      {
        bin = next_bin (bin);
        bit <<= 1;
        assert (bit != 0);
      }

    /* Inspect the bin. It is likely to be non-empty */
    victim = last (bin);

    /*  If a false alarm (empty bin), clear the bit. */
    if (victim == bin)
      {
        av->binmap[block] = map &= ~bit; /* Write through */
        bin = next_bin (bin);
        bit <<= 1;
      }

    else
      {
        size = chunksize (victim);

        /*  We know the first chunk in this bin is big enough to use. */
        assert ((unsigned long) (size) >= (unsigned long) (nb));

        remainder_size = size - nb;

        /* unlink */
        unlink (av, victim, bck, fwd);

        /* Exhaust */
        if (remainder_size < MINSIZE)
          {
            set_inuse_bit_at_offset (victim, size);
            if (av != &main_arena)
              victim->size |= NON_MAIN_ARENA;
          }

        /* Split */
        else
          {
            remainder = chunk_at_offset (victim, nb);

            /* We cannot assume the unsorted list is empty and therefore
               have to perform a complete insert here.  */
            bck = unsorted_chunks (av);
            fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
              {
                errstr = "malloc(): corrupted unsorted chunks 2";
                goto errout;
              }
            remainder->bk = bck;
            remainder->fd = fwd;
            bck->fd = remainder;
            fwd->bk = remainder;

            /* advertise as last remainder */
            if (in_smallbin_range (nb))
              av->last_remainder = remainder;
            if (!in_smallbin_range (remainder_size))
              {
                remainder->fd_nextsize = NULL;
                remainder->bk_nextsize = NULL;
              }
            set_head (victim, nb | PREV_INUSE |
                      (av != &main_arena ? NON_MAIN_ARENA : 0));
            set_head (remainder, remainder_size | PREV_INUSE);
            set_foot (remainder, remainder_size);
          }
        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }
  }
  1. 앞서 할당하지 못한 chunk 할당 - use_top

위의 모든 과정에서 할당하지 못했다면 아래의 로직과 같이 arena의 top에서 할당하게 됩니다.

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

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

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

  /* When we are using atomic ops to free fast chunks we can get
     here for all block sizes.  */
  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);
    }

  /*
     Otherwise, relay to handle system-dependent cases
   */
  else
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

우선 첫번째 조건문을 보면 할당하려는 사이즈와 MINSIZE의 합이 top의 크기보다 작거나 같을 경우 아래의 로직이 실행되며 새롭게 top이 생성되고 할당되게 됩니다.

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

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 chunk가 있다면 아래의 로직이 실행됩니다. 해당 로직에서 한번더 fastbin의 해제된 chunk들을 병합하게 되고 idx 변수의 값을 수정한 뒤 다시 처음부터 반복문이 시작되게 됩니다.

1
2
3
4
5
6
7
8
9

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

마지막으로 위의 2가지 조건을 전부 달성하지 못할 경우 아래의 조건을 실행하게 됩니다. 해당 로직에서 sysmalloc 함수를 호출해서 할당받게 됩니다.

1
2
3
4
5
6
7

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

즉, 다음과 같은 순서로 할당이 되게 됩니다.

  1. nb 변수 값 할당
  2. arena를 사용하지 않을 경우
  3. fastbin 크기의 chunk를 할당할 경우
  4. smallbin 크기의 chunk를 할당할 경우
  5. largebin 크기의 chunk를 할당할 경우
  6. 앞서 할당하지 못한 chunk 할당 - unsorted_bin
  7. 앞서 할당하지 못한 chunk 할당 - largebin
  8. 앞서 할당하지 못한 chunk 할당 - binmap
  9. 앞서 할당하지 못한 chunk 할당 - use_top
  10. 6번 부터 위 과정 반복

__libc_malloc 마무리

위의 로직이 끝나게 된다면 _int_malloc 함수의 반환값인 주소를 검증하고 __libc_malloc 함수가 종료되게 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

victim = _int_malloc (ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena
   before.  */
if (!victim && ar_ptr != NULL)
  {
    LIBC_PROBE (memory_malloc_retry, 1, bytes);
    ar_ptr = arena_get_retry (ar_ptr, bytes);
    victim = _int_malloc (ar_ptr, bytes);
  }

if (ar_ptr != NULL)
  (void) mutex_unlock (&ar_ptr->mutex);

assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
        ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim;

free 분석

__libc_free

free함수가 실행되면 __libc_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

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 */
      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;
          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);
}
libc_hidden_def (__libc_free)

__libc_malloc 함수와 같이 __free_hook 변수의 값을 hook 변수에 넣고, 값이 존재할 경우 실행하게됩니다. 이 때 첫번째 인자는 free 함수에 들어가는 첫번째 인자인 mem 변수가 들어가게됩니다. 이후, 해당 영역이 mmap 함수로 할당되었을 경우 아래의 로직이 실행됩니다.

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

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;
        LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
                    mp_.mmap_threshold, mp_.trim_threshold);
      }
    munmap_chunk (p);
    return;
  }

만약, mmap으로 할당된 영역이 아니라면 arena 주소를 저장하고 _int_free 함수가 실행됩니다.

1
2

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

_int_free

해당 함수가 실질적으로 할당한 영역을 free하는 부분입니다. 코드가 길기때문에 순차적으로 설명드리겠습니다.

우선, 해당 chunk의 크기를 size 변수에 저장한뒤 해제하려는 chunk 주소가 유효한지, 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

  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)
        (void) mutex_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);
  1. fastbin 크기의 chunk를 해제할 경우

위의 검증을 다 성공적으로 했다면, 첫번째로 size가 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

  /*
    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 ())

#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))
      {
			/* 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;
			      }))
			  {
			    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);

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

위의 로직에서 have_lock 변수는 해당 함수의 인자로 넘어오는데 0으로 넘어오기 때문에 lock을 하지 않고 진행하게 됩니다. 해당 부분은 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    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))
      {
			/* 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;
			      }))
			  {
			    errstr = "free(): invalid next size (fast)";
			    goto errout;
			  }
				if (! have_lock)
			  {
			    (void)mutex_unlock(&av->mutex);
			    locked = 0;
			  }
      }

이후, 아래와 같이 fastbin에서 해제를 위한 변수들의 값들을 초기화합니다.

1
2
3
4
5
6
7
8
9

    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;

그리고 fastbin을 해제하기 위해 다음의 반복문이 실행됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

위의 do-while문에서 해제할 chunk의 fd를 조절하게 되고 만약, old와 p 포인터의 값이 같으면 double free bug 취약점이 발생하기 때문에 검증하고 있는 것을 확인할 수 있습니다. 또한, 에러를 막기위한 예외처리도 되어있는 것을 확인할 수 있습니다.

  1. mmap으로 할당된 chunk가 아닌 경우

다음으로 fastbin에 해당하는 크기도아니고 mmap 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
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

  /*
    Consolidate other non-mmapped chunks as they arrive.
  */

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

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    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 (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);

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

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

      /* consolidate forward */
      if (!nextinuse) {
	unlink(av, nextchunk, bck, fwd);
	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);
    }

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

    /*
      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);
      (void)mutex_unlock(&av->mutex);
    }
  }

위의 과정중 처음으로 실행되는 로직은 아래와 같이 검증을 진행하는 부분입니다.

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

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

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    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 (nextchunk->size <= 2 * SIZE_SZ, 0)
		|| __builtin_expect (nextsize >= av->system_mem, 0))
    {
			errstr = "free(): invalid next size (normal)";
			goto errout;
    }

검증 과정은 총 4가지가 있는데 아래와 같은 검증이 존재합니다.

  • 해제하려는 영역이 arena의 top인 경우
  • 해제하려는 영역이 arena의 top을 벗어나는 경우
  • 해제하려는 영역이 사용되고 있지 않은 영역인 경우
  • 해제하려는 영역의 다음 블록 크기가 너무 작거나 시스템 메모리모다 큰 경우

위의 검증을 통과하게 된다면 해제를 위한 로직이 실행되게 됩니다. 첫번째로 해제하려는 chunk의 이전 chunk가 사용되지 않는다면 병합하게 됩니다.

1
2
3
4
5
6
7

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

그리고 nextchunk가 arena의 top이 아니라면 아래의 로직이 실행됩니다.

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

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

      /* consolidate forward */
      if (!nextinuse) {
				unlink(av, nextchunk, bck, fwd);
				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);
    }

다음 청크가 사용중인지 확인하고 사용하지 않는다면 병합을 합니다. 그리고 만약 사용하고 있다면 다음 청크의 prev_inuse bit를 0로 변경합니다. 그리고 해제하려는 chunk를 unsorted_bin에 넣기 위해 값을 셋팅한뒤 해제하려는 영역이 largebin에 속한다면 fd_nextsize, bk_nextsize도 NULL로 초기화합니다. 이후, check_free_chunk 함수로 정상적으로 free가 되었는지 확인합니다.

다음으로, 만약 해제하려는 chunk의 다음 chunk가 arena의 top이라면 아래의 로직이 실행됩니다.

1
2
3
4
5
6

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

위의 로직이 실행되면 해제하려는 chunk가 arena의 top에 병합되게 됩니다. 이후, mmap으로 할당된 chunk가 아니라면 다음 chunk가 top인지 상관없이 아래의 로직이 실행되게 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    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);
      (void)mutex_unlock(&av->mutex);
    }

위의 로직에서 fastbin에 chunk가 존재한다면 malloc_consolidate 함수를 통해 병합이 이루어지게되고 현재 arena가 main_arena라면 top의 사이즈를 조절하는 검증을 수행합니다. 그리고 main_arena가 아니라도 arena의 top 크기를 조절합니다. 그리고 have_lock의 변수를 확인하고 lock을 해제합니다.

  1. mmap으로 할당된 chunk

mmap으로 할당된 chunk는 아래와 같은 로직이 실행됩니다.

1
2
3

  else {
    munmap_chunk (p);
  }

간단하게 munmap_chunk 함수가 실행되는 것을 확인할 수 있습니다.

_int_free 마무리

즉, _int_free 함수는 다음과 같은 조건으로 나뉘어서 chunk가 해제되고 적절한 bin에 들어가게 됩니다.

  1. fastbin인 경우
  2. mmap으로 할당된 chunk가 아닌경우
  3. mmap으로 할당된 chunk인 경우

보호기법

glibc 2.23 버전에서 보호기법은 다음과 같은 곳에 걸려있습니다.

  • fastbin 크기의 chunk를 해제하는 과정에서 double free bug를 방지하기 위해 존재합니다.
  • fastbin 크기의 chunk, mmap으로 할당한 chunk가 아닌 경우 해제하려는 영역이 arena의 top인 경우
  • fastbin 크기의 chunk, mmap으로 할당한 chunk가 아닌 경우 해제하려는 영역이 arena의 top을 벗어나는 경우
  • fastbin 크기의 chunk, mmap으로 할당한 chunk가 아닌 경우 해제하려는 영역이 사용되고 있지 않은 영역인 경우
  • fastbin 크기의 chunk, mmap으로 할당한 chunk가 아닌 경우 해제하려는 영역의 다음 블록 크기가 너무 작거나 시스템 메모리모다 큰 경우

결론

glibc 2.23이 현재 linux에서 메모리 관리를 하는 시작점이기 때문에 해당 버전으로 분석을 진행하였습니다. 향후, 버전이 업그레이드될 때마다 생기는 개념 및 보호기법에 대해서 계속해서 포스터를 작성하겠습니다.

pwnable
glibc free malloc glibc 2.23
This post is licensed under CC BY 4.0 by the author.