how malloc work

Aug 7, 2025 · Dreamhack

#Introduction#Glibc

드디어 malloc에 대해 자세히 다뤄보자.

C
__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));
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);

  MAYBE_INIT_TCACHE ();

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
	      &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

  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)
    __libc_lock_unlock (ar_ptr->mutex);

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

malloc/malloc.c 에 있는 정석 코드이다.

주요 부분을 살펴보면

C
void *victim;

우리가 받는 청크 주소를 libc에서는 victim 이라고 부른다.

C
 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으로 control flow가 이동하는 것을 알 수 있다.

C
#if USE_TCACHE
  size_t tbytes;
  checked_request2size (bytes, tbytes);   // 요청→내부 크기(nb)로 패딩
  size_t tc_idx = csize2tidx (tbytes);    // 크기를 tcache 인덱스로 변환

  MAYBE_INIT_TCACHE ();                   // 스레드별 tcache 초기화

  if (tc_idx < mp_.tcache_bins
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);         // ★ 가장 빠른 경로
    }
#endif

역시 tcache!! 빠르게 tcache에 대해 분석을 해보자면,

  1. checked_request2size
    • 사용자 요청 bytes를 내부 size_t 정렬(16 바이트) + 메타데이터 추가해 tbytes 생성.
    • 단언(overflow 체크) 포함.
  2. csize2tidx
    • tbytes를 8/16 바이트 단위 “bin 인덱스”로 환산. 예: 0x20 → 0. ( tcachebins[0x0] 이라는 말임 첫번째 bins가 0x20 크기인 얘들을 다루니깐 )
  3. MAYBE_INIT_TCACHE()
    • 현재 스레드의 tcache 구조체가 NULL이면 한 번만 mmap()으로 얻어 초기화.
  4. tc_idx 값이 mp_.tcache_bins 값보다 작고 ( 즉, 해당 크기를 tcache_bins 에서 다루고 있고 ) 리스트 머리가 NULL이 아니면 tcache_get()으로 꺼내서 즉시 반환.

    (여기까지는 락·시스템콜·경합 없음)

통과 못 하면 → 다음 단계로.

이제 tcache로 얻는데 실패했으면, 아레나로 얻을 차례이다.

해당글을 읽고 오면 편하다.

C
if (SINGLE_THREAD_P)
  {
    victim = _int_malloc (&main_arena, bytes);
    /* 방어용 assert … */
    return victim;
  }

먼저, 프러세스가 싱글 스레드 일때,

  • SINGLE_THREAD_P 매크로: libc.threads.c에서 __libc_multiple_threads 변수 확인
    • 메인 프로그램이 아직 pthread_create()를 호출한 적 없을 때 true
  • 이 경우 글로벌 main_arena 하나에만 접근하므로 락 불필요 → 가장 단순·빠름
  • victim을 얻기 위해 내부 할당 루틴 _int_malloc() 호출함
C
arena_get (ar_ptr, bytes);      // 6-1
victim = _int_malloc (ar_ptr, bytes);

if (!victim && ar_ptr != NULL)  // 6-2
  {
    ar_ptr = arena_get_retry (ar_ptr, bytes);
    victim = _int_malloc (ar_ptr, bytes);
  }

if (ar_ptr != NULL)
  __libc_lock_unlock (ar_ptr->mutex);  // 6-3

arena_get()

첫번째,현재 스레드가 이미 소유한 arena 있으면 그것을 리턴
두번째없으면, arena 리스트에서 빈(할당량 여유) arena를 락 걸어 가져오기
세번째그래도 없으면 mmap()으로 새 arena(≈ heapsize 64 KiB) 생성

만약 이제 얻었으면,

C
victim = _int_malloc (ar_ptr, bytes);

해당 아레나 객체를 가지고 malloc을 실행한다.

arena_get_retry

arena_get() 에서 실패했을때, 반드시 성공 할 수 있는 객체를 가져오는 것이다.

자, 그럼 결국 Arena 객체를 가지고 _int_malloc 함수를 실행하는 것을 알 수 있으니 해당 함수를 분석을 해보자면

C
checked_request2size (bytes, nb);

먼저, 0x10 크기로 사용자의 요청크기를 정규화한다.

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

아레나가 할당이 안되어 있다면, sysmalloc 으로

2. FASTBIN & TCACHE ― 가장 빠른 경로 ( 크기가 작을때 ≤ 0x80 B )

C
if ((unsigned long)nb <= get_max_fast()) { … }
  1. fastbin_index(nb) → 크기를 0~9 번호로 매핑 (0x20, 0x30, … 0x80).
  2. fb = &fastbin(av, idx) 가져오기.
  3. 단일 스레드면 간단히 *fb = victim->fd; 다중 스레드는
C
catomic_compare_and_exchange_val_acq(fb, victim->fd, victim);

로 CAS.

CAS란?

Compare And Swap(또는 Compare-And-Exchange, CAS) 으로 fastbin에서 다중스레드 일때 다른 스레드간 경합이 일어날 수 있는데 이때 뮤텍스를 사용하기 보다는 CAS라는 간단한 매크로로 이를 해결

즉, 내가 fastbin에서 받아온 값이 내가 예상한 값 ( 원래 얻었어야 하는 값 → 경합이 일어나면 바뀜 ) 과 같으면 사용하겠다 이말임

  1. 가져온 victim 무결성 검사(chunksize, fd 역참조).
  2. TCACHE 존재 & 해당 bin이 비면, fastbin 안에 남은 청크들을 빈 틈까지 tcache_put().

성공하면 chunk2mem(victim) 후 즉시 반환 → O(1), 락 없음.

근데 이런 생각이 들 수 있음, 왜 자꾸 tcache 얘기가 나오지?

→ tcache 넣어놔야 다음에 락 없이 바로 가져올 수 있으니깐 미리 해놓는 거임

① fastbin (≤ 0x80 B)최소 크기 + 최근에 free 된 청크가 들어옴 → CAS 1회면 획득● 정해진 10개 크기● 메타데이터 검사만 하면 끝
② smallbin (0x90 ~ 0x400 B)크기별 전용 큐. 헤드/테일 포인터만 갱신하면 됨 → O(1)● arena 락 1회 필요
③ unsorted binfastbin 합치거나, 큰 청크 split/free 직후 임시 대기열 → 루프 돌며 크기·정렬 확인

3. SMALLBIN 고정 크기 할당 ( 크기가 적당히 클때 주로 0x90 ~ 0x400 )

C
if (in_smallbin_range(nb)) { … }
  • idx = smallbin_index(nb) (size/8 − 2), bin = bin_at(av, idx)
  • 해당 bin tail(LIFO)인 last(bin)을 꺼내 exact-fit.
  • 머리 지정이므로 정렬·탐색 비용 0.
  • 꺼낸 뒤에 같은 크기 청크가 더 있으면 필요량만큼 TCACHE에 적재.

fastbin → smallbin으로 “승격”된 청크들 + 병합(consolidate) 결과가 여기서 소모된다.

4. 대형 요청 준비 – fastbin 전체 병합

C
else { idx = largebin_index(nb);
       if (av->have_fastchunks) malloc_consolidate(av); }
  • nb > 0x400(64-bit 기준)이라면 fragmentation 방지를 위해 먼저 모든 fastbin을 unsorted bin으로 병합.
  • 이후 과정에서 largebin/unsorted가 true best-fit을 결정.

5. UNSORTED BIN 1차 스캔 (가장 복잡)

C
  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;

for문으로 계속 돌면서 스캔함 그리고 적당한 크기를 찾으면, tcache나 small bin large bin으로 보냄

6. 정규 BIN 탐색 이제 다시 정규 bin을 탐색하거나 tcache로 보냈으면 tcache에서 가져옴

7. TOP CHUNK / 시스템 메모리 요청

C
victim = av->top; size = chunksize(victim);
자세한 코드
C
    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;
      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 (atomic_load_relaxed (&av->have_fastchunks))
        {
          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;
        }
    }
  1. size ≥ nb + MINSIZE → top을 잘라서 remainder를 새 top으로.
  2. else if av->have_fastchunks → malloc_consolidate() 후 bin 탐색 다시. 좀더 자세히 말하면, fastbin에 청크가 있으면 인접 자유 청크와 병합시켜서 unsorted bin 에 넣는다. 이후 small,large로 승진시킨다. 이걸 다시한번 써보겠다고 bin 탐색을 다시하는 것
  3. 계속 부족하면 sysmalloc() 호출 →
    • nb ≥ mmap_threshold ⇒ mmap() 대형 청크
    • 아니면 sbrk()로 힙 확장.

다음과 같다. 여기서 중요한게 나오는데 사이즈가 top chunk에서 때어올 수 없을 정도로 크고 즉, mmap_threshold 보다 크면 heap 영역이 아닌 mmap으로 anon 영역을 가져온다는 것.

이 주소로 libc의 주소를 유추할 수 도 있다. 자세한 건 다음 글에 있다.

sysmalloc() 함수가 _int_malloc 함수 안에 2번 호출되는데 다음과 같다.

1. arena 자체가 아직 없음  (프로세스 첫 할당·신규 스레드인데 arena 풀도 바닥)c if (av == NULL) return sysmalloc(nb, av);
2. 현재 arena 의 top도 부족하고  fastbin 병합을 해봐도 해결 불가c p = sysmalloc(nb, av); (루프 맨 끝)

그리고 해당 함수 안에서는

내부 의사결정 : mmap() vs brk() 1. nb ≥ mp_.mmap_threshold (초기값 128 KiB, 동적 조정 가능) → 익명 mmap() 으로 독립 블록 할당 • 반환 chunk는 헤더에 IS_MMAPPED 플래그가 켜짐 → free()시 무조건 munmap()

2. 작은 요청 → 현재 arena 가 main_arena 이면 sbrk()(데이터 세그먼트 확장) → 다른 arena 면 mmap() 으로 heap fragment 하나 받아 arena 전용 힙으로 사용 • 새로 받아온 메모리 일부는 “새 top chunk”로, 나머지는 일반 chunk 로 즉시 돌려줌

  • *즉, “크기가 크면 무조건 mmap, 작으면 힙(brk) 연장”**이 기본 정책입니다. 단, 다중 arena에서는 작은 요청도 mmap 로 갈 수 있어요.

추가 내용 what is main_arena ( main arena )

맨처음 생성된 arena를 말함. sbrk 권한을 가지고 있음

당연하겠지만, 서로 다른 arena 끼지는 안에 객체 내용 ( bins , top ) 등이 다름

그럼 언제 새로운 arena를 만드냐면,

멀티스레드 프로그램에서, 내 스레드가 쓸만한 arena(잠금이 풀려 있고 남는 공간도 있는)가 당장 없을 때   → arena_get() 함수가 new_arena()를 호출해 mmap()으로 64 KiB±짜리 힙 블록을 받아 새 malloc_state 구조체를 초기화한다. 단, 이미 만든 arena 수가 MALLOC_ARENA_MAX(또는 glibc tunable arena_max) 상한에 도달하면 새로 만들지 못하고, 기존 arena가 잠금 해제되기를 기다린다.