rvkhunLab

Write about System Hacking

0%

free (glibc-2.23)

Posted on Edited on In Views: 33
  • glibc-2.23 free 분석

source : https://github.com/andigena/glibc-2.23-0ubuntu3/blob/master/malloc/malloc.c

__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
40
41
42
43
44
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;
    }
    // __free_hook 함수가 설정되어있으면 해당 함수 실행

  if (mem == 0)                              /* free(0) has no effect */
    return;
    // free인자가 0일경우 종료 

  p = mem2chunk (mem);
  // chunk의 header 주소를 p에 저장
  if (chunk_is_mmapped (p))   			/* release mmapped memory. */
  // chunk에 is_mmapped flag가 설정되어있다면 아래 방식으로 해제 (분석중..)
    {
      /* 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);
      // munmap_chunk 함수 호출
      return;
    }

  ar_ptr = arena_for_chunk (p);
  // ar_ptr에 chunk의 메모리를 비워야 하는 부분을 저장
  _int_free (ar_ptr, p, 0);
  // _int_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
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
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  INTERNAL_SIZE_T size;        // 특정 chunk의 size
  mfastbinptr *fb;             // 해제와 연관된 fastbin index
  mchunkptr nextchunk;         // 다음 index의 chunk
  INTERNAL_SIZE_T nextsize;    // 특정 chunk의 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;
  int locked = 0;

  size = chunksize (p);
  // size에 할당을 해제할 chunk(p)의 size를 저장
  
  /* 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))
      // chunk의 크기를 음수로 바꿔 chunk의 주소랑 비교,
      // 만약 작거나, 해제하려는 chunk가 align이 되지 않을 경우
    {
      errstr = "free(): invalid pointer";
      // "free(): invalid pointer" exception 발생
    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)))
  // size가 chunk의 최소크기 보다 작거나, align되지 않을 경우
    {
      errstr = "free(): invalid size";
      // "free(): invaild size" exception 발생
      goto errout;
    }

  check_inuse_chunk(av, p);
  // 전달받은 chunk의 다음 chunk의 prev_inuse flag를 확인

  /*
    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 ())
  // size가 fastbin 크기일 경우

#if TRIM_FASTBINS
// TRIM_FASTBINS가 set되어 있을경우 해당 조건 추가
// TRIM_FASTBINS가 set되지 않을경우 해당 조건을 추가하지 않고 진행
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
      // chunk의 다음 chunk가 topchunk가 아니면  
      // (topchunk 바로 위에 있는 fastbin size chunk는 건드리지 않는다)
#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의 다음 chunk의 크기가 최소 크기보다 작거나, 최대 크기보다 클경우
      {
      
	/* 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;
	      }))
      // __libc_free부터 넘겨받은 have_lock이 설정되어 있거나,
      // 다음 chunk size가 최소 크기보다 작거나, system_mem보다 크면
	  {
	    errstr = "free(): invalid next size (fast)";
        // "free(): invalid next size (fast)" exception 발생
	    goto errout;
	  }
	if (! have_lock)
    // have_lock이 설정되어있지 않으면
	  {
	    (void)mutex_unlock(&av->mutex);
        // mutex_unlock 
	    locked = 0; 
	  }
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    // 해당 chunk free

    set_fastchunks(av);
    // 현재 arena에 FASTCHUNKS_BIT 설정
    unsigned int idx = fastbin_index(size);
    // size에 대한 fastbin index 저장
    fb = &fastbin (av, idx);
    // index에 맞는 fastbin 저장
    // idx에는 fastbinY의 index가 저장, fb에는 index의 bin list가 저장 

    /* 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))
    // old = 이전에 해제한 포인터, p = 현재 해제할 포인터
    // old == p 라면 
	  {
	    errstr = "double free or corruption (fasttop)";
        // "double free or corruption (fasttop)" exception 발생
	    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)
    // have_lock이 설정되어있고, 이전에 해제한 chunk가 있다면(old가 NULL이 아니라면)
	  old_idx = fastbin_index(chunksize(old));
      // old_idx에 old 크기에 맞는 fast bin index 저장
	p->fd = old2 = old;
    // 현재 해제할 chunk의 fd와 old2에 이전에 해제한 chunk(old) 저장
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
    // if(*fb == old2) {*fb = p; return old2;}가 될 때까지 반복.
    // 해제 요청을 받은 chunk를 fast bin에 넣는 작업

    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
    // have_lock이 설정되어있고, old가 NULL이 아니고, old_idx와 idx가 다르면
      {
	errstr = "invalid fastbin entry (free)";
    // "invalid fastbin entry (free)" exception 발생
	goto errout;
      }
  }
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/*
    Consolidate other non-mmapped chunks as they arrive.
*/

  else if (!chunk_is_mmapped(p)) {
  // 해제할 chunk의 is_mmapped flag가 설정되어 있지 않으면,
    if (! have_lock) {
    // have_lock이 set되어 있지 않다면,
      (void)mutex_lock(&av->mutex);
      locked = 1;
    }

    nextchunk = chunk_at_offset(p, size);
    // nextchunk에 해제할 chunk의 다음 chunk 저장

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__glibc_unlikely (p == av->top))
    // 해제할 chunk가 top chunk 이면
      {
	errstr = "double free or corruption (top)";
	goto errout;
    // "double free or corruption(top)" exception 발생
      }
    /* 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))
    // 해제하려는 chunk의 크기만큼 뒤에 heap이 존재하는지 확인. 만약 없다면,
      {
	errstr = "double free or corruption (out)";
	goto errout;
    // "double free or corruption(out)" exception 발생 
      }
    /* Or whether the block is actually not marked used.  */
    if (__glibc_unlikely (!prev_inuse(nextchunk)))
    // 해제하려는 다음 chunk의 prev_inuse가 설정되어 있지 않다면 
      {
	errstr = "double free or corruption (!prev)";
	goto errout;
    // "double free or corruption (!prev)" exception 발생
      }

    nextsize = chunksize(nextchunk);
    // 해제할 chunk의 다음 chunk의 크기를 nextsize에 저장
    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (nextsize >= av->system_mem, 0))
    // nextchunk의 크기가 최소 크기보다 작거나, system_mem보다 크면
      {
	errstr = "free(): invalid next size (normal)";
	goto errout;
    // "free(): invalid next size(normal)" exeception 발생
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
    // 해제할 chunk를 free

    /* consolidate backward */
    if (!prev_inuse(p)) {
    // 해제할 chunk의 이전 chunk가 사용 중 이지 않을 경우
      prevsize = p->prev_size;
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);
      // 이전 chunk와 병합
    }

    if (nextchunk != av->top) {
    // 해제할 chunk의 다음 chunk가 topchunk가 아닐 경우
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
      // 해제할 chunk의 다음 chunk의 다음 chunk의 prev_inuse flag를 저장

      /* consolidate forward */
      if (!nextinuse) {
      // 만약 해제할 chunk의 다음 chunk가 사용중이 아니라면,
	unlink(av, nextchunk, bck, fwd);
	size += nextsize;
      } else
	clear_inuse_bit_at_offset(nextchunk, 0);
    // 다음 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.
      */

      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);
      // unsorted bin에 해제한 chunk 추가
    }

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

    else { //해제할 chunk 다음 chunk가 top chunk인 경우
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
      // topchunk와 병합
    }

    /*
      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)
    // size가 FASTBIN 임계값 보다 크고
    {
      if (have_fastchunks(av))
      // fastbin이 존재하면
	malloc_consolidate(av);
    // fastbin 병합

      if (av == &main_arena) 
      // main_arena라면,
      {
#ifndef MORECORE_CANNOT_TRIM
	if ((unsigned long)(chunksize(av->top)) >=
	    (unsigned long)(mp_.trim_threshold))
        // topchunk 크기가 trim 임계값보다 크면
	  systrim(mp_.top_pad, av);
      // systrim 호출
#endif
      } else {
      // main_arena가 아니라면
	/* 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);
    // heap_trim 호출
      }
    }

    if (! have_lock) {
      assert (locked);
      (void)mutex_unlock(&av->mutex);
    }
  }
  /*
    If the chunk was allocated via mmap, release via munmap().
  */

  else {
  // is_mmap flag가 설정되어있으면,
    munmap_chunk (p);
    // munmap_chunk 함수 호출
  }
}

free 함수 호출 순서 : libc_free() -> int_free() -> systrim() or heap_trim() or munmap_chunk()

  1. libc_free() 함수에서 mmap으로 할당된 메모리인지 확인한 후, 맞을 경우 munmap_chunk() 함수를 통해 메모리 해제
  2. 아닌 경우, 해제하고자 하는 chunk가 속한 Arena의 포인터를 획득한 후, int_free() 함수 호출
  3. chunk를 해제한 후, 크기에 맞는 bin을 찾아 저장하고 top chunk와 병합을 할 수 있다면 병합 수행
  4. 병합된 top chunk가 너무 커서 Arena의 크기를 넘어선 경우, top chunk의 크기를 줄이기 위해 systrim() 함수 호출
  5. 문제가 없다면, heap_trim() 함수 호출
  6. mmap으로 할당된 chunk라면 munmap_chunk()를 호출

1

Reference