rvkhunLab

Write about System Hacking

0%

malloc (glibc-2.23)

Posted on Edited on In
  • glibc-2.23 malloc 분석

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

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
#define PREV_INUSE 0x1
#define prev_inuse(p)       ((p)->size & PREV_INUSE)
// 이전 chunk 사용여부 확인

#define IS_MMAPPED 0x2
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)	
// mmap 할당 여부 확인

#define NON_MAIN_ARENA 0x4
#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)	
// main_arena 여부 확인

#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)	
// 3가지 flag를 or 연산

#define chunksize(p)         ((p)->size & ~(SIZE_BITS))		
// flag값을 제외한 실제 chunk 크기 확인

#define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
// 다음 chunk = 현재chunk + 현재chunk 크기  

#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
// 이전 chunk = 현재chunk - 이전chunk 크기

#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))
// chunk에 s를 더한 주소

#define inuse(p)							      
  ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
// 다음 chunk의 prev_inuse 값을 확인

#define set_inuse(p)							      
  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
// 다음 chunk의 prev_inuse 값을 1로 set

#define clear_inuse(p)							      
  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
// 다음 chunk의 prev_inuse 값을 0으로 set
  
#define inuse_bit_at_offset(p, s)					      
  (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
// chunk + s의 prev_inuse 값을 확인 

#define set_inuse_bit_at_offset(p, s)					      
  (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
// chunk + s의 prev_inuse 값을 1로 set

#define clear_inuse_bit_at_offset(p, s)					      
  (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
// chunk +s의 prev_inuse 값을 0으로 set

1
2
3
4
5
6
7
8
9
10
11
12
13
#define bin_at(m, i)
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			     
             - offsetof (struct malloc_chunk, fd))
// m(arena)의 i(indx)의 bin의 주소를 저장
// 이때, 이 bin을 fd, bk를 가진 chunk로서 사용하기 위해 - 0x10 한 값을 저장한다.

#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
// bins[]에서 다음 bin을 가져온다.

#define first(b)     ((b)->fd)
// 해당 binlist의 첫번째 chunk (가장 마지막으로 free된 chunk)
#define last(b)      ((b)->bk)
// 해당 binlist의 마지막 chunk (가장 먼저 free된 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
#define unlink(AV, P, BK, FD)     (P는 이전에 해제된 chunk의 주소)(밑에 수정)
// binlist에서 chunk 제거
{                                            
    FD = P->fd;					// FD = 현재 chunk의 fd (다음 chunk)
    BK = P->bk;					// BK = 현재 chunk의 bk (이전 chunk)			     
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))
    // 다음 chunk의 bk(이전)이 현재 chunk가 아니거나, 
    // 이전 chunk의 fd(다음)이 현재 chunk가 아니면
      malloc_printerr (check_action, "corrupted double-linked list", P, AV);
    // "corrupted double-linked list" exception 발생
    else {								     
        FD->bk = BK;			// 다음 chunk->bk = 현재 chunk->bk				     
        BK->fd = FD;			// 이전 chunk->fd = 현재 chunk->fd
        if (!in_smallbin_range (P->size)	
        // 현재 chunk의 크기가 smallbin 범위에 해당하지 않고 (즉, large bin일 때)
            && __builtin_expect (P->fd_nextsize != NULL, 0)){	
            // 현재 chunk의 fd_nextsize가 NULL이 아니면, (fd_nextsize, bk_nextsize 처리)
	    if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)
        // 다음 크기 chunk의 bk_nextsize(이전)이 현재 chunk가 아니거나,
		|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) 
        // 이전 크기 chunk의 fd_nextsize(다음)이 현재 chunk가 아니면,
	      malloc_printerr (check_action,				     
			       "corrupted double-linked list (not small)",    
			       P, AV);
          // "corrupted double-linked list (not small)" exception 발생
            if (FD->fd_nextsize == NULL) {
            // 다음 chunk의 fd_nextsize가 NULL이고, 
                if (P->fd_nextsize == P)
                // 현재 chunk의 fd_nextsize가 자기자신이면,
                  FD->fd_nextsize = FD->bk_nextsize = FD;
                  // 다음 chunk의 fd_nextsize, bk_nextsize를 자기자신으로,
                else {							      
                    FD->fd_nextsize = P->fd_nextsize;
                    // 현재 chunk의 다음 크기 chunk를 다음 chunk의 다음 크기 chunk로
                    FD->bk_nextsize = P->bk_nextsize;
                    // 현재 chunk의 이전 크기 chunk를 다음 chunk의 이전 크기 chunk로
                    P->fd_nextsize->bk_nextsize = FD;
                    // 다음 chunk를 현재 chunk의 다음 크기 chunk의 이전 크기 chunk로
                    P->bk_nextsize->fd_nextsize = FD;
                    // 다음 chunk를 현재 chunk의 이전 크기 chunk의 다음 크기 chunk로
                  }							      
              } else { // 다음 chunk의 fd_nextsize가 NULL이 아니라면,
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;		
                // 원래대로 복구
              }								      
          }								      
      }									      
}

__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
32
33
34
35
36
37
38
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));
    // __malloc_hook 포인터가 지정되어 있을 시 hook 함수 실행

  arena_get (ar_ptr, bytes);
  // ar_ptr에 heap영역으로 사용할 arena 주소를 저장 후 arena에 mutext_lock 설정

  victim = _int_malloc (ar_ptr, bytes);
  // _int_malloc 함수 호출, victim = 할당된 chunk 주소

  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)
  // ar_ptr이 NULL이 아니면
    (void) mutex_unlock (&ar_ptr->mutex);
    // arena에 mutex_unlock 설정

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
 
  return victim;
  // 할당된 chunk 주소 반환
}

_int_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
static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;           // 요청한 size + header
  unsigned int idx;             // 할당에 연관된 bin의 index
  mbinptr bin;                  // 할당에 연관된 bin

  mchunkptr victim;             // 특정 bin에서 할당 가능 여부를 검사중이거나 선택중인 chunk
  INTERNAL_SIZE_T size;         // 특정 chunk의 크기
  int victim_index;             // 특정 chunk의 bin의 index

  mchunkptr remainder;          // 분리되고 남은 remainder
  unsigned long remainder_size; // remainder의 size

  unsigned int block;           /* bit map traverser */
  unsigned int bit;             /* bit map traverser */
  unsigned int map;             /* current word of binmap */

  mchunkptr fwd;                /* misc temp for linking */
  mchunkptr bck;                /* misc temp for linking */

  const char *errstr = NULL;

  checked_request2size (bytes, nb);
  // bytes: 요청한 동적 할당 크기를 -> nb: header + align된 memory 크기로 변환
1
2
3
4
5
6
7
8
9
10
11
12
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from mmap.  */
 
  if (__glibc_unlikely (av == NULL))
  // 사용가능한 arena가 없으면, (av = arena pointer) 
    {
      void *p = sysmalloc (nb, av);
      // sysmalloc(->mmap)으로 chunk 할당
      if (p != NULL)
	alloc_perturb (p, bytes);
      return p;
      // 할당된 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
/*   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 ()))
  // nb가 global_max_fast보다 작거나 같을 경우 (fastbin에 포함될 경우)
    {
      idx = fastbin_index (nb);
      // fastbin에서 nb크기의 index를 idx에 저장
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp = *fb;
      // av->fastbinsY배열의 idx의 첫번째 chunk의 주소를 pp에 저장.
      do
        {
          victim = pp;
          if (victim == NULL)
            break;
        }
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
             != victim);
      // victim(pp)가 NULL일 경우 (알맞은 free chunk가 없는 경우) break;
    
      if (victim != 0)
        {
          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0)) 
          // 할당을 요청한 chunk(victim)의 크기가 fastbin과 일치하지 않으면
          // "fastbin dup bypass"
            {
              errstr = "malloc(): memory corruption (fast)";
            errout:
              malloc_printerr (check_action, errstr, chunk2mem (victim), av);
              return NULL;
              // "malloc() : memory corruption (fast)" exception 발생
            }
          check_remalloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
          // 할당된 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
/*
     If a small request, check regular bin.  Since these "smallbins"
     hold one size each, no searching within bins is necessary.
     (For a large request, we need to wait until unsorted chunks are
     processed to find best fit. But for small ones, fits are exact
     anyway, so we can check now, which is faster.)
*/

  if (in_smallbin_range (nb))
  // nb가 smallbin_range에 있으면 (smallbin일 경우)
    {
      idx = smallbin_index (nb);
      // idx에 해당 크기의 smallbin 인덱스를 저장
      bin = bin_at (av, idx);
      // bin에 av->bin의 idx에 해당하는 small bin 주소 저장

      if ((victim = last (bin)) != bin)
      // victim에 bin의 마지막 chunk(bin->bk)를 저장 (LIFO-last in first out)
      // victim이 NULL인 경우, malloc함수가 최초로 실행된 것
      // victim이 bin인 경우, 해당 bin은 비어있는 것
        {
          if (victim == 0) /* initialization check */
          // victim이 NULL인 경우,
            malloc_consolidate (av);
            // malloc_consolidate 함수 호출 (존재하는 fastbin 병합)
          else 
            {
              bck = victim->bk;
	if (__glibc_unlikely (bck->fd != victim))
    // bck->fd = victim->bk->fd 가 자기 자신(victim)이 아닐경우
                {
                  errstr = "malloc(): smallbin double linked list corrupted";
                  goto errout;
                  // "malloc(): smallbin double linked list corrupted" exception 발생
                }
              set_inuse_bit_at_offset (victim, nb);
              // victim의 물리적으로 위치한 다음 chunk(victim+nb)의 inuse flag를 1로 set
              bin->bk = bck;
              // bin의 마지막 chunk를 victim->bk로 설정
              bck->fd = bin;
              // victim->bk->fd를 bin으로 설정
              // bin에서 victim 제거 과정 (double linked list)

              if (av != &main_arena)
              // av가 main_arena가 아니라면
                victim->size |= NON_MAIN_ARENA;
                // victim에 NON_MAIN_ARENA flag 설정
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
              // 할당된 chunk 주소 리턴
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
     If this is a large request, consolidate fastbins before continuing.
     While it might look excessive to kill all fastbins before
     even seeing if there is space available, this avoids
     fragmentation problems normally associated with fastbins.
     Also, in practice, programs tend to have runs of either small or
     large requests, but less often mixtures, so consolidation is not
     invoked all that often in most programs. And the programs that
     it is called frequently in otherwise tend to fragment.
*/
  else
    {
      idx = largebin_index (nb);
      // largebin인 경우
      if (have_fastchunks (av))
      // av에 fastchunk가 있으면,
        malloc_consolidate (av);
        // malloc_consolidate 함수 호출 (존재하는 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
/*
     Process recently freed or remaindered chunks, taking one only if
     it is exact fit, or, if this a small request, the chunk is remainder from
     the most recent non-exact fit.  Place other traversed chunks in
     bins.  Note that this step is the only place in any routine where
     chunks are placed in bins.
     The outer loop here is needed because we might not realize until
     near the end of malloc that we should have consolidated, so must
     do so and retry. This happens at most once, and only when we would
     otherwise need to expand memory to service a "small" request.
*/

  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
      // unsorted bin list의 마지막 chunk를 victim에 저장
        {
          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);
        // victim->size가 특정 범위를 벗어나면 "malloc(): memory corruption" exception 발생
          size = chunksize (victim);
        // size에 flag를 제외한 크기 저장
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
if (in_smallbin_range (nb) &&
            bck == unsorted_chunks (av) &&
            victim == av->last_remainder &&
            (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
  // smallbin 사이즈이고,  unsorted bin의 맨 마지막 chunk이고,
  // last_remainder chunk이며, chunk의 size가 nb + 최소크기보다 크면, 
          {
            /* split and reattach remainder */
            // 해당 chunk를 두 개의 chunk로 split
            remainder_size = size - nb;
            // remainder_size = chunk의 size - 요청한 크기 nb
            remainder = chunk_at_offset (victim, nb);
            // remainder = victim + nb 위치, remainder_chunk를 split 하기 위한 offset
            unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
            // unsorted bin에 remainder 저장
            av->last_remainder = remainder;
            // last_remainder 업데이트
            remainder->bk = remainder->fd = unsorted_chunks (av);
            // remainder의 bk, fd에 unsorted_chunk 포인터 저장 (use memory leak)
            if (!in_smallbin_range (remainder_size))
            // remainder_size가 largebin 크기 라면,
              {
                remainder->fd_nextsize = NULL;
                remainder->bk_nextsize = NULL;
                // fd_nextsize, bk_nextsize 초기화
              }

            set_head (victim, nb | PREV_INUSE |
                      (av != &main_arena ? NON_MAIN_ARENA : 0));
            // victim->size에 nb | PREV_INUSE | NON_MAIN_ARENA 한 값을 set
            set_head (remainder, remainder_size | PREV_INUSE);
            // remainder->size에 remainder_size | PREV_INUSE 한 값을 set
            set_foot (remainder, remainder_size);
            // remainder의 물리적 다음 chunk의 prev_size를 remainder_size로 set

            check_malloced_chunk (av, victim, nb);
            void *p = chunk2mem (victim);
            alloc_perturb (p, bytes);
            return p;
            // 할당된 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
/* remove from unsorted list */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);
          // (확인중인 index) victim을 unlink함  

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

          if (size == nb)
          // 요청한 크기와 victim의 크기가 같을 경우
            {
              set_inuse_bit_at_offset (victim, size);
              // victim의 물리적 다음 chunk의 size에 prev_inuse flag set
              if (av != &main_arena)
                victim->size |= NON_MAIN_ARENA;
     // main_arena가 아니라면 victim의 물리적 다음 chunk의 size에 NON_MAIN_ARENA flag set
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
              // 할당된 chunk 주소 리턴
            }

          /* place chunk in bin */
   // 남아있는 bin을 크기에 맞춰 smallbin, largebin으로 보내는 작업
          if (in_smallbin_range (size))
          // size가 smallbin 크기이면,
            {
              victim_index = smallbin_index (size);
              // victim_index에 size에 해당하는 smallbin binlist의 index 저장
              bck = bin_at (av, victim_index);
              // binlist에서 index에 해당하는 bin 주소를 bck에 저장
              fwd = bck->fd;
              // fwd에 bck->fd 저장 
            }
          else //size가 largebin 크기이면,
            {
              victim_index = largebin_index (size);
              // victim_index에 size에 해당하는 largebin binlist의 index 저장
              bck = bin_at (av, victim_index);
              // binlist에서 index에 해당하는 bin 주소를 bck에 저장
              fwd = bck->fd;
              // fwd에 bck->fd 저장

              /* maintain large bins in sorted order */
              if (fwd != bck)
              // bck->fd != bck (해당 large bin list가 비어있지 않으면)
                {
                  /* Or with inuse bit to speed comparisons */
                  size |= PREV_INUSE;
                  // size에 PREV_INUSE flag를 set
                  /* if smaller than smallest, bypass loop below */
                  assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
                  // bck->bk->size에 NON_MAIN_ARENA flag가 설정되어있을 경우 종료
                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
                  // victim의 크기가 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;
                      // victim을 해당 double linked list에 삽입
                    }
                  else // victim의 크기가 bck->bk->size보다 클 경우
                    {
                      assert ((fwd->size & NON_MAIN_ARENA) == 0);
                      // fwd->size에 NON_MAIN_ARENA flag가 설정되어 있으면 종료
                      while ((unsigned long) size < fwd->size)
                      // victim의 size가 fwd->size보다 같거나 클 때 까지
                        {
                          fwd = fwd->fd_nextsize;
                          assert ((fwd->size & NON_MAIN_ARENA) == 0);
                          // 해당 작업을 반복
                          // 크기 순으로 정렬되는 large bin에 victim이 추가될 위치 찾는 작업
                        }

                      if ((unsigned long) size == (unsigned long) fwd->size)
                      // victim의 size와 fwd->size가 같다면
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;
                        // fwd에 fwd->fd 저장, 다음 위치 index를 불러옴
                      else
                      // victim의 size와 fwd->size가 같지 않다면
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                          // list에 victim 추가 
                        }
                      bck = fwd->bk;
                      // bck에 fwd->bk 저장
                    }
                }
              else // large bin이 비어있으면
                victim->fd_nextsize = victim->bk_nextsize = victim;
                // victim의 fd_nextsize, bk_nextsize를 자기자신으로
            }

          mark_bin (av, victim_index);
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;
          // victim을 크기에 맞는 smallbin/largebin에 추가

#define MAX_ITERS       10000
          if (++iters >= MAX_ITERS)
            break;
        }
        // 이 과정을 최대 10000회 반복
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
/*
         If a large request, scan through the chunks of current bin in
         sorted order to find smallest that fits.  Use the skip list for this.
*/

      if (!in_smallbin_range (nb))
      // 요청한 크기 nb가 largebin 크기라면,
        {
          bin = bin_at (av, idx);
          // largebin에서 해당 크기의 index에 위치한 bin 주소를 저장

          /* skip scan if empty or largest chunk is too small */
          if ((victim = first (bin)) != bin &&
              (unsigned long) (victim->size) >= (unsigned long) (nb))
   // 만약 largebin이 비어있지 않고, largebin의 첫번째 chunk의 size가 nb보다 크거나 같으면
            {
              victim = victim->bk_nextsize;
              // largebin 에서 크기가 가장 작은 chunk를 저장
              // 만약 largebin에 자기 자신만 있으면 bk_nextsize은 자기 자신을 가리킴
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb)))
                      // victim의 크기가 요청한 크기보다 커질 때 까지 
                victim = victim->bk_nextsize;
		// 해당 작업 반복 (해당 large bin 뒤에서부터 앞으로 scan해서 적절한 chunk 찾기
              /* 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이 large bin의 마지막 chunk가 아니고, 
              // victim의 크기가 victim의 다음 chunk의 크기와 같으면
                victim = victim->fd;
				// victim에 victim의 다음 chunk 저장
              remainder_size = size - nb;
              // remainder_size에 chunk의 size - 요청한 크기 nb 값을 저장
              unlink (av, victim, bck, fwd);
			  // largebin에서 victim을 unlink
              /* Exhaust */
              if (remainder_size < MINSIZE)
              // remainder_size가 MINSIZE보다 작으면,
                {
                  set_inuse_bit_at_offset (victim, size);
                  // victim의 다음 chunk (remainder_chunk)의 PREV_INUSE flag 1로 set
                  if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                    // remainder_chunk의 NON_MAIN_ARENA flag set
                }
              /* Split */
              else // remainder_size가 MINSIZE보다 같거나 크면,
                {
                  remainder = chunk_at_offset (victim, nb);
                  // remainder에 remainder_chunk의 주소 저장
                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  // unsorted bin의 주소를 bck에 저장
                  fwd = bck->fd;
                  // fwd에 unsroted bin->fd 저장
	  if (__glibc_unlikely (fwd->bk != bck))
                    {
                      errstr = "malloc(): corrupted unsorted chunks";
                      goto errout;
                    }
        // bck->fd->bk != bck 일 경우 "malloc(): corrupted unsorted chunks" exception
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  // remainder를 unsorted bin 맨 앞에 추가
                  if (!in_smallbin_range (remainder_size))
                  // remainder_size가 largebin 크기일 경우
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                      // fd_nextsize, bk_nextsize를 초기화
                    }
                  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);
                  // split된 victim의 PREV_INUSE,NON_MAIN_ARENA flag set
                  // remainder의 flag set
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
              // 할당된 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
// 나중에
/*
         Search for a chunk by scanning bins, starting with next largest
         bin. This search is strictly by best-fit; i.e., the smallest
         (with ties going to approximately the least recently used) chunk
         that fits is selected.
         The bitmap avoids needing to check that most blocks are nonempty.
         The particular case of skipping all bins during warm-up phases
         when no chunks have been returned yet is faster than it might look.
*/

      ++idx;
      bin = bin_at (av, idx);
      // idx에 해당하는 bin 주소 저장
      block = idx2block (idx);
      // block = (idx >> 5)
      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)
          // 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
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
use_top:
/*
         If large enough, split off the chunk bordering the end of memory
         (held in av->top). Note that this is in accord with the best-fit
         search rule.  In effect, av->top is treated as larger (and thus
         less well fitting) than any other available chunk since it can
         be extended to be as large as necessary (up to system
         limitations).
         We require that av->top always exists (i.e., has size >=
         MINSIZE) after initialization, so if it would otherwise be
         exhausted by current request, it is replenished. (The main
         reason for ensuring it exists is that we may need MINSIZE space
         to put in fenceposts in sysmalloc.)
*/

      victim = av->top;
      // victim에 해당 arena의 top chunk의 포인터 저장
      size = chunksize (victim);
	  // size = top chunk size
      if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
      // top chunk size가  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;
          // 할당된 chunk 의 주소 리턴
        }

      /* When we are using atomic ops to free fast chunks we can get
         here for all block sizes.  */
      else if (have_fastchunks (av)) 
      // 현재 arena의 malloc_state에 FASTCHUNK_BIT이 설정되어 있을 경우 
        {
          malloc_consolidate (av);
          // malloc_conslidate 함수를 호출하여 freed fast bin size chunk를 병합
          /* restore original bin index */
          if (in_smallbin_range (nb))
          // nb가 smallbin 크기면,
            idx = smallbin_index (nb);
            // smallbin index 저장
          else // large bin 이라면 
            idx = largebin_index (nb);
            // largebin index 저장
        }

      /*
         Otherwise, relay to handle system-dependent cases
       */
      else // topchunk size가 nb+MINSIZE보다 작고, FASTCHUNK_BIT도 SET되지 않았으면,
        {
          void *p = sysmalloc (nb, av);
          // sysmalloc을 통해 메모리 할당
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
          // 할당된 chunk 주소 리턴
        }
    }
}

malloc 함수 호출 순서 : libc_malloc() -> int_malloc() -> sysmalloc()

  1. libc_malloc() 함수에서 사용하는 Thread에 맞게 Arena를 설정한 후, int_malloc() 함수 호출
  2. int_malloc() 함수에서는 재사용할 수 있는 bin을 탐색하여 재할당하고, 마땅한 bin이 없다면 top chunk에서 분리해서 할당
  3. top chunk가 요청한 크기보다 작은 경우, sysmalloc() 함수 호출
  4. sysmalloc() 함수를 통해 시스템에 메모리를 요청해서 top chunk의 크기를 확장하고 대체
    ※ sysmalloc() 함수는 기존의 영역을 해제한 후, 새로 할당함

1

Reference