Heap - glibc 2.23 (3)

Heap - glibc 2.23 (_int_malloc)

---

_int_malloc

1. _int_malloc

static void *
_int_malloc (mstate av, size_t bytes)

• mstate av : 아레나를 가리키는 포인터이다.
• size_t bytes : 사용자가 malloc(byte)를 통해 요청한 순수한 메모리 크기이다.

  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its 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;

요청 및 청크 관련

• nb(normalized bytes) : 사용자 요청 bytes에 헤더 크기와 정렬 패딩을 더한 실제 내부 청크 크기이다.
• victim : bin에서 꺼내온 ‘희생자’, 할당 후보가 되는 청크를 가리키는 포인터이다.
• size : victim의 청크 크기를 임시로 저장한다.

bin 관련

• idx : nb 크기에 해당하는 fastbinsY 또는 bins 배열의 인덱스를 저장한다.
• bin : bins 배열 내의 특정 bin의 헤드를 가리키는 포인터이다.
• victim_index : Unsorted bin에서 청크를 꺼내 정렬할 때, 청크가 들어가야 할 bin의 인덱스를 저장한다.

청크 분할(split) 관련

• remainder : 큰 victim 청크를 nb만큼 잘라내고 남은 나머지 부분을 가리키는 포인터
• remainder_size : remainder 청크의 크기를 저장한다.

binmap 탐색 관련

• block, bit, map : large bin을 탐색할 때 binmap을 효율적으로 순회하기 위한 변수들이다

기타

• fwd, bck : 이중 연결 리스트에서 청크를 연결하거나 해제(unlink)할 때 사용하는 임시 포인터이다.
• errstr : 오류가 발생했을 때 오류 메시지를 저장하기 위한 변수이다.

 

초기화 및 예외처리 코드

checked_request2size (bytes, nb);

• checked_request2size : 사용자가 요청한 bytes를 내부 청크 크기 nb 로 변환한다.

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

• if (__glibc_unlikely (av == NULL)) : 아레나가 없는 예외 상황을 처리한다.
• sysmalloc (nb, av) : 아레나가 없기 때문에 운영체제로부터 직접 메모리를 가져오는 sysmalloc 함수를 사용한다.
• alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채운다.
• return p : sysmalloc이 성공적으로 메모리를 받아오면 그 주소를 반환하고 함수를 종료한다.
  
  

fastbin 확인 로직

1. 진입 조건

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))

• checked_request2size를 통해 계산된 내부 청크 크기 nb가 get_max_fast(fastbin이 처리하는 최대 크기) 이하인지 확인한다.

 

2. fastbin에서 청크 꺼내기

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

1. idx = fastbin_index (nb) : nb 크기에 해당하는 fastbin의 인덱스를 계산한다.
2. mfastbinptr *fb = &fastbin (av, idx) : fastbin 리스트의 시작점 주소를 fb에 저장한다.
3. do - while : 안전하게 리스트의 첫번째 청크를 꺼내는 로직이다.
   • victim = pp : 현재 리스트의 첫 번째 청크를 victim 으로 설정한다.
   • if (victim == NULL) : 만약 bin이 비어있다면 victim이 NULL 이므로 즉시 루프를 탈출한다.
   • while ((pp = catomic_ …. != victim) : compare_and_exchange 연산을 통해 리스트의 시작점(fb)을 첫 번째 청크의 다음 청크 victim→fb로 바꾸려고 시도한다.

 

3. 보안 검사

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

• if (victim !=0) : victim 청크를 확보했다면 이 청크가 유효한지 최종적으로 검사한다.
• fastbin_index (chunksize (victim)) != idx : 꺼내온 victim 청크의 크기를 다시 계산하고 이 청크가 원래 있던 bin의 인덱스와 일치하는지 확인한다.

 

4. 성공 및 반환

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

• check_remalloced_chunk : 디버깅용 검사 매크로이다
• void *p = chunk2mem (victim) : 청크의 시작주소 victim에서 헤더 크기만큼 뒤로 이동해서 사용자에게 실제로 돌려줄 메모리 영역의 주소 p를 계산한다.
• alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채워넣는다.
• return p : 사용자에게 메모리 주소 p를 반환하고 함수를 종료한다.

 

smallbin 확인 로직

1. 진입 조건

if (in_smallbin_range (nb))

• nb가 small bin 크기 범위 내에 있는지 확인한다.

 

2. bin에서 청크 꺼내기

      idx = smallbin_index (nb);
      bin = bin_at (av, idx);
      
      if ((victim = last (bin)) != bin)

• idx = smallbin_index (nb) : nb 크기에 맞는 smallbin의 인덱스를 계산한다.
• bin = bin_at (av, idx) : 해당 인덱스의 bin 헤드 주소를 bin 포인터에 저장한다.
• if ((victim = last (bin)) != bin) : bin이 비어있지 않은지 확인한다.
  • bin이 비어있으면 last(bin)은 bin의 헤드 자신을 반환하기 때문에 victim == bin이 되어 if 블록에 들어가지 않는다.

 

3. 예외 처리 : 초기화되지 않은 bin

					if (victim == 0) /* initialization check */
            malloc_consolidate (av);
          else
            {
              bck = victim->bk;

• if (victim == 0) : bin이 초기화되지 않았거나 손상되었을 가능성을 확인한다.
  • malloc_consolidate : fastbin을 모두 병합하고 bin이 초기화 되지 않았다면 초기화 한다.
• else : victim이 유효한 청크일 때 실행된다.
  • smallbin은 삽입은 헤드 제거는 테일 원칙으로 동작하여 FIFO 처럼 동작한다.

 

4. 청크 분리 및 반환

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

• if (__glibc_unlikely (bck->fd != victim)) : 이중 연결 리스트의 무결성을 검사한다.
• set_inuse_bit_at_offset (victim, nb) : victim 청크 바로 다음 청크의 PREV_INUSE 비트를 1로 설정한다.
• bin->bk = bck; bck->fd = bin : victim을 bin에서 분리한다.
• victim->size |= NON_MAIN_ARENA : 쓰레드 아레나 청크일 경우 A 비트를 설정한다.

 

Unsorted bin 확인 로직

1. 사전 작업

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

• fastbin과 smallbin에서 청크를 찾지 못했고 사용자 요청이 Large 크기일 때 실행된다.
• idx = largebin_index (nb) : Largebin의 인덱스를 미리 계산하여 idx 변수에 저장한다.
• if (have_fastchunks (av)) : FASTCHUNKS_BIT 플래그를 확인하여 아레나에 fastbin 청크가 존재하는지 검사한다.
  • malloc_consolidate (av) : fastbin에 청크가 있다면 malloc_consolidate 함수를 호출하여 unsorted bin으로 옮기는 작업을 한다.

 

2. Unsorted bin 순회 루프 진입

  for (;; )
    {
      int iters = 0;
      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);

for (;; ) 루프

• 대부분의 경우 한 번만 실행되지만 malloc의 모든 탐색이 실패하여 top chunk마저 부족할 때, malloc_consolidate 한 뒤 탐색을 다시 시작한다. → 이 때 이 루프가 실행된다.
• int iters = 0 : iters 변수는 무한 루프 방지용 카운터이다.

while 루프

• while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
  • unsorted_chunks(av) : unsorted bin의 헤드를 가리킨다.
  • ->bk : unsorted bin은 이중 연결 리스트로 이 코드는 리스트의 맨 뒤에서부터 청크를 꺼낸다.
  • victim : 꺼내온 변수를 victim에 저장한다.
  • != unsorted_chunks (av) : 리스트가 비어있지 않은 동안 루프를 계속 실행한다.
• bck = victim->bk : victim을 리스트에서 제거하기 전에 그 다음 처리할 청크의 주소를 bck에 미리 저장한다.
• if (__builtin_expect … ) : victim 청크의 size 필드가 유효한 범위 내에 있는지 무결성 검사를 한다.
• size = chunksize (victim) : victim 헤더에서 순수한 크기 값을 읽어와 size에 저장한다.

 

3. last_remainder 확인 (Best fit 처리 로직)

          if (in_smallbin_range (nb) &&
              bck == unsorted_chunks (av) &&
              victim == av->last_remainder &&
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
            {
              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;
            }
           

 

1. 진입 조건

• in_smallbin_range (nb) : 사용자 요청(nb)이 smallbin 크기여야 한다.
• bck == unsorted_chunks (av) : victim이 unsorted bin의 유일한 청크여야 한다.
• victim == av->last_remainder : unsorted bin의 유일한 청크가 last_remainder여야 한다.
• (size) > (nb + MINSIZE) : victim의 size가 nb를 만족시키고도 남는 조각이 MINSIZE이상이 될 만큼 충분히 커야 한다.

2. 청크 분할 및 처리

• remainder_size = size - nb : 요청 크기를 제외한 나머지 부분의 크기를 계산한다.
• remainder = chunk_at_offset (victim, nb) : victim의 시작 주소에서 nb만큼 떨어진 곳을 remainder 청크의 시작점으로 지정한다.
• unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder
  • unsorted bin을 비우고 remainder 청크를 unsorted bin의 유일한 청크로 넣는다
  • 아레나의 last_remainder 포인터도 새로운 remainder를 가리키도록 업데이트 한다.
• set_head (victim, … ) : 사용자에게 반활될 victim의 헤더는 요청된 크기 nb와 사용 중 플래그를 담아 설정한다.
• set_head, set_foot : remainder는 새로운 free 청크이기 때문에 그 header와 footer에 remainder_size를 기록한다.

 

4. Exact Fit 처리 로직

          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);
          
          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;
            }

1. victim을 unsorted bin에서 분리

• unsorted_chunks (av)->bk = bck : unsorted bin의 헤드가 victim 대신 bck를 가리키게 한다.
• bck->fd = unsorted_chunks (av) : bck가 victim 대신 헤드를 가리키게 한다.

2. Exact fit

• if (size == nb) : size는 victim의 실제 크기로 victim이 nb랑 일치하는지 확인한다.
• set_inuse_bit_at_offset (victim, size) : victim을 사용중으로 표시한다.
• victim->size |= NON_MAIN_ARENA : 만약 쓰레드 아레나라면, victim의 size 필드에 A 비트를 설정한다.
• check_malloced_chunk (av, victim, nb) : 청크의 유효성을 검사한다.
• void *p = chunk2mem (victim) : victim을 사용자에게 반환할 메모리 포인터 p로 변경한다.

 

5. 목적지 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;

• if (in_smallbin_range (size) : smallbin으로 보낼 경우
  • victim_index = smallbin_index (size) : size에 해당하는 smallbin 인덱스를 계산하여 victim_index에 저장한다.
  • bck = bin_at (av, victim_index) : bin_at 매크로를 이용해 해당 victim_index에 위치한 bin의 헤드 주소를 가져온다.
  • fwd = bck->fd : 해당 bin의 헤드(bck)가 가리키는 첫 번째 청크의 주소를 fwd에 저장한다.
• else : Large bin으로 보낼 경우
  • victim_index = largebin_index (size) : size에 해당하는 large bin의 인덱스 번호를 계산하여 victim_index에 저장한다.
  • bck = bin_at (av, victim_index) : victim_index에 위치한 bin의 헤드 주소를 bck에 저장한다.
  • fwd = bck->fd : 해당 bin의 첫 번째 청크 주소를 fwd에 저장한다.

 

6. Largebin 정렬 삽입

              if (fwd != bck)
                {
                  size |= PREV_INUSE;
                  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)
                        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;
            }

• if (fwd != bck) : Largebin이 비어있지 않은지 확인한다.
  • if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) victim의 크기(size)가 bin의 마지막 청크(bck→bk)보다도 작은지 확인한다.
    • victim은 리스트의 맨 뒤가 되고 포인터를 리스트의 끝으로 조정한 뒤 fd_nextsize, bk_nextsize 리스트에도 연결한다.
  • else: victim이 중간에 들어가야 하는 경우이다.
    • while 루프는 fd_nextsize에서 victim보다 크기가 작거나 같은 청크를 빠르게 찾는다.
    • if (size == fwd→size) : 만약 같은 크기의 청크가 있다면 항상 두 번째 위치에 삽입하여 첫 노드를 nextsize 리스트의 앵커로 유지한다.
    • else : 다른 크기라면 fwd 앞에 삽입되어야 하기 때문에 fd_nextsize, bk_nextsize 포인터를 정교하게 조작한다.
    • bck = fwd->bk : 삽입될 위치의 이전 노드를 bck에 정확히 설정한다.
• else : largebin이 비어있었다면, victim이 유일한 청크가 되기 때문에 fd_nextsize와 bk_nextsize가 자기 자신을 가리키도록 한다.

앵커?

---

앵커는 nextsize 리스트에서 각 크기 그룹을 대표하는 기준점 역할을 하는 첫 번째 청크를 의미한다.

 

7. 최종 연결 작업

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

• mark_bin (av, victim_index) : victim이 들어갈 bin이 비어있지 않다고 binmap을 1로 표시한다.
• victim->bk = bck; victim->fd = fwd : victim의 포인터들이 자신의 이전 노드(bck)와 다음 노드(fwd)를 가리키게 한다.
• fwd->bk = victim; bck->fd = victim : bck와 fwd가 victim을 가리키게 한다.

 

8. 무한 루프 방지 장치

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

• #define MAX_ITERS 10000 : 최대 반복 횟수를 10000으로 정의한다.
• if (++iters >= MAX_ITERS) : 루프의 반복 횟수가 10000에 도달했는지 확인한다.
  • break : 반복 횟수가 10000에 도달했다면 while루프를 강제로 탈출한다.

 

Largebin 탐색 및 분할

large bin에서 malloc은 현재 bin의 가장 큰 청크가 요청보다 큰 지 확인한 후 가장 작은 그룹(bk_nextsize)부터 위로 올라오며 요청 크기(nb) 이상의 최소 청크를 찾는다.

1. 진입 조건

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

          if ((victim = first (bin)) != bin &&
              (unsigned long) (victim->size) >= (unsigned long) (nb))

• if (!in_smallbin_range (nb)) : nb가 Large chunk 크기일 경우에만 실행된다.
• bin = bin_at (av, idx) : idx를 이용해 nb 크기에 가장 이상적인 largebin의 헤드 주소를 가져온다.
• if ((victim = first (bin)) != bin && (victim→size) ≥ (nb) : 탐색을 하기 전의 사전 검사
  • victim = first (bin)) != bin : 해당 bin이 비어있지 않은지 확인한다.
  • victim→size ≥ nb : first(bin)은 해당 bin에서 가장 큰 청크를 가리킨다. 가장 큰 청크가 nb보다 작으면 if 문 전체를 건너뛴다.

 

2. bk_nextsize를 이용한 탐색

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

• victim = victim->bk_nextsize : large bin은 내림차순으로 정렬되어 있기 때문에 가장 작은 청크부터 탐색하는 것이 효율적이다. bk_nextsize는 가장 작은 크기 그룹의 시작점으로 점프하는 포인터이다.
• while (… ) victim = victim->bk_nextsize : bk_nextsize : bk_nextsize 리스트를 따라 작은 크기에서 큰 크기 그룹으로 올라가며 탐색한다. victim의 크기가 nb보다 크거나 같아지는 순간 루프가 멈춘다.

 

3. 탐색 후 최적화

              if (victim != last (bin) && victim->size == victim->fd->size)
                victim = victim->fd;

• victim이 리스트의 기준점이고 바로 뒤에 같은 크기의 청크가 있다면 바로 뒤 청크를 victim으로 선택한다.

 

4. 청크 분할 또는 전체 사용

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

              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
                    victim->size |= NON_MAIN_ARENA;
                }
              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);
                }

• if (remainder_size < MINSIZE) : victim을 nb만큼 잘라내고 남는 조각이 너무 작아서 청크가 될 수 없는경우이다. 낭비를 막기 위해 victim 전체를 사용자에게 할당한다.
• else : 분할하고 남는 조각이 충분히 큰 경우이다.
  • remainder = chunk_at_offset (victim, nb) : 남는 조각을 remainder 청크로 만든다.
  • bck = unsorted_chunks (av) : remainder 청크를 다시 unsorted bin의 맨 앞에 넣는다.
  • set_head (victim, …) : 사용자에게 줄 victim 부분의 헤더 크기를 nb로 수정한다.
  • set_head (remainder, …); set_foot (remainder, …) : remainder가 유효한 free 청크가 되도록 헤더와 푸터를 설정한다.

 

5. 최종 반환

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

• check_malloced_chunk (av, victim, nb) : 할당될 청크의 유효성을 검사한다.
• p = chunk2mem (victim) : 헤더를 제외한 실제 사용자 데이터 영역의 시작 주소를 계산한다.
• alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채워넣는다.
• return p : 최종적으로 사용자에게 메모리 포인터 p를 반환한다.

 

더 큰 Large bin 확인 로직

1. 탐색 준비

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

• ++idx : largebin에서 청크를 찾지 못했으므로 인덱스를 1 증가시켜서 바로 다음으로 큰 bin부터 탐색을 시작한다.
• binmap 초기화
  • block = idx2block (idx) : idx가 binmap 배열의 몇번째 unsigned int에 해당하는지를 계산한다.
  • map = av->binmap[block] : 해당 block의 실제 비트값을 map 변수에 저장한다.
  • bit = idx2bit (idx) : 현재 idx가 map 내의 몇 번째 비트에 해당하는지 나타내는 비트 마스크를 계산한다.

 

2. binmap을 이용한 반복 탐색

       for (;; )
        {
          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;
            }

• for (;; ) : nb를 만족하는 청크를 찾거나 모든 bin을 다 확인해서 top chunk를 사용해야 할 때까지 계속된다.
  • if (bit > map || bit == 0) : 현재 map에서 더 이상 검사할 비트가 없을 때 실행된다.
    • do - while 루프 : binmap 배열의 다음 block으로 이동하며 0이 아닌 map을 찾을 때까지 매우 빠르게 스캔한다.
      • if (++block >= BINMAPSIZE) : 모든 bin을 다 확인했는데도 bin이 없다면 goto use_top을 통해 top chunk를 사용한다.
    • bin = bin_at (av, (block << BINMAPSHIFT)) : map을 찾으면 bin 포인터를 그 그룹의 첫 번째 bin으로 bit 마스크를 첫 번째 비트로 리셋하여 스캔을 준비한다.

 

3. block 내에서 비어있지 않은 bin 찾기

          while ((bit & map) == 0)
            {
              bin = next_bin (bin);
              bit <<= 1;
              assert (bit != 0);
            }

• while ((bit & map) == 0) : 비트 연산을 통해 현재 map에서 1로 설정된 비트를 찾을 때까지 bit를 왼쪽으로 시프트 연산을 한다.
• bin 포인터도 다음 bin으로 이동한다.

 

4. bin 처리 및 반환

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

• victim = last (bin) : binmap으로 찾은 비어있지 않은 bin에서 대략적으로 가장 오랫동안 사용되지 않은(LRU, Least Recently Used) 청크를 선택하는 동점 처리(tie-break) 규칙이다.
• if (victim == bin) : binmap 비트와 실제 bin 상태가 일치하지 않는 경우 binmap의 해당 비트를 0으로 수정하고 다음 bin으로 넘어간다.
• else : 사용할 청크를 찾았을 때이다.
  • 이후의 로직은 이전에 분석한 Large bin 탐색 및 분할 로직과 동일하다.

 

Top Chunk 사용

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

• use_top : 요청을 만족하는 free 청크를 전혀 찾지 못했을 때 도달하는 지점이다.

 

1. Top chunk 분할

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

• if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) : Top chunk의 크기가 요청된 크기 nb와 분할 후 남은 조각이 최소 크기의 합보다 크거나 같은지 확인한다.
  • remainder = chunk_at_offset (victim, nb) : 아레나의 top 포인터를 remainder의 시작 주소로 올린다.
  • av->top = remainder : 아레나의 top 포인터를 remainder의 시작 주소 위로 올린다.
  • set_head (victim, … ) : 사용자에게 반활될 victim의 헤더를 nb 크기로 설정하고 사용 중으로 표시한다.
  • set_head (remainder, … ) : 새로운 Top chunk가 된 remainder의 헤더를 남은 크기로 업데이트 한다.

 

2. 정리 및 재시도

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

• else if (have_fastchunks (av)) : fastbin에만 free청크가 남아있는 경우일 때에 동작한다.
  • malloc_consolidate (av) : fastbin에 흩어져 있는 모든 조각들을 병합하여 unsorted bin으로 옮긴다.
  • 이 블록이 끝난 후 코드는 바깥 for ( ; ; ) 루프의 처음으로 돌아가서 Unsorted bin부터 탐색을 다시한다.

 

3. 시스템 메모리 할당

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

• Top chunk도 부족하고, Fastbin을 정리해도 소용이 없는, 정말로 가용 메모리가 전혀 없는 상황이다.
  • void *p = sysmalloc (nb, av) : 운영체제에 직접 메모리를 요청하는 sysmalloc 함수를 호출한다.
  • 성공적으로 메모리를 받으면 그 주소를 실패하면 NULL을 반환한다.