ptmalloc malloc 구현 분석: 동적 메모리 할당의 내부 동작

동적 메모리 할당의 기초

C 언어에서 malloc()과 free()는 런타임 시점에 힙 영역에서 메모리를 할당하고 해제하는 핵심 함수입니다. 언어 사양상 이 함수들이 수행해야 하는 역할은 명확하지만, 그 내부 구현 방식은 특정 메모리 할당기(memory allocator)에 의해 결정됩니다. 예를 들어, 이미 해제된 메모리 영역을 접근하면 미정의 동작(undefined behavior)이 발생하는데, 그 결과는 사용 중인 할당기의 알고리즘에 따라 달라질 수 있습니다.

ptmalloc 개요

glibc에서 기본으로 제공하는 메모리 할당기인 ptmalloc은 malloc(), free() 등의 함수를 구현하여 프로세스의 동적 메모리 관리를 담당합니다. 멀티스레드 환경에서도 효율적인 성능을 내기 위해 설계되었으며, "arena"라는 개념을 도입해 스레드 간 경합을 최소화합니다.

가상 메모리 구조

32비트 리눅스 프로세스의 전형적인 가상 주소 공간 배치는 다음과 같습니다:

  • 스택(stack): 고주소에서 저주소 방향으로 확장
  • 힙(heap): 저주소에서 고주소 방향으로 확장
  • mmap 영역: 고주소에서 저주소 방향으로 확장

힙과 스택 사이의 넓은 공백 영역은 런타임에 brk() 또는 mmap() 시스템 콜을 통해 동적으로 확보되는 메모리 공간입니다.

시스템 인터페이스

ptmalloc은 두 가지 주요 시스템 인터페이스를 활용합니다:

  • brk/sbrk: 힙 영역의 경계를 조정하여 연속적인 메모리를 확보합니다. 소규모 할당에 적합하며, 일반적으로 '도매' 확보에 해당합니다.
  • mmap: 파일이나 익명 메모리를 가상 주소 공간에 매핑합니다. 대규모 할당(일반적으로 128KB 초과) 시 사용되며, 독립적인 페이지 단위로 관리됩니다.

메모리 블록 구조: Chunk

ptmalloc은 모든 할당된 및 해제된 메모리 블록을 chunk라는 단위로 관리합니다. 각 chunk는 다음과 같은 헤더 정보를 포함합니다:

struct malloc_chunk {
  size_t      prev_size;  // 이전 청크 크기 (이전 청크가 비어 있을 때만 유효)
  size_t      size;       // 현재 청크 크기 및 상태 플래그
  struct malloc_chunk* fd;     // 다음 빈 청크 (비어 있을 때)
  struct malloc_chunk* bk;     // 이전 빈 청크 (비어 있을 때)
  // large bin 전용
  struct malloc_chunk* fd_nextsize;
  struct malloc_chunk* bk_nextsize;
};

size 필드의 하위 3비트는 특수한 의미를 갖습니다:

  • PREV_INUSE (P): 이전 청크가 사용 중인지 여부
  • MAPPED (M): mmap을 통해 할당된 청크인지 여부
  • NON_MAIN_ARENA (N): 주 할당 영역(main arena) 외부에서 할당되었는지 여부

빈 청크 관리: Bins

해제된 청크들은 재사용을 위해 다양한 bin 구조에 저장됩니다. 총 128개의 bin이 있으며, 크기와 접근 패턴에 따라 다음과 같이 분류됩니다:

Fastbins

  • 크기 범위: 16바이트 ~ 80바이트 (64비트 기준)
  • 구조: 단방향 LIFO 스택 (단일 연결 리스트)
  • 특징: 병합(merging) 없음, 가장 빠른 접근 속도

Unsorted Bin

  • 구조: 이중 연결 순환 리스트
  • 기능: 최근 해제된 청크들을 임시 보관. 이후 _int_malloc 실행 시 적절한 small 또는 large bin으로 이동됩니다.

Small Bins

  • 청크 수: 62개
  • 크기 범위: 16바이트 간격으로 증가 (최대 약 512바이트)
  • 구조: 이중 연결 순환 리스트, FIFO 정책

Large Bins

  • 청크 수: 63개
  • 크기 범위: 512바이트 이상, 크기에 따라 그룹화
  • 구조: 이중 연결 리스트, fd_nextsize와 bk_nextsize를 통해 근접 크기 탐색 최적화

할당 로직: _int_malloc 분석

실제 메모리 할당의 핵심은 _int_malloc 함수에 있습니다. 호출 흐름은 다음과 같습니다:

__libc_malloc()
└──> ptmalloc_init() (최초 한 번 초기화)
└──> _int_malloc()

주요 단계

  1. arena 선택: 현재 스레드에 맞는 arena를 획득합니다. 메인 스레드는 main_arena를, 나머지는 non_main_arena를 사용할 수 있습니다.
  2. Fastbins 검색: 요청 크기가 fastbin 범위 내에 있으면, 해당 bin에서 최상위 청크를 LIFO 방식으로 반환합니다.
  3. Small bins 검색: 요청이 smallbin 범위에 속하면, 해당 bin의 마지막 청크를 제거하고 반환합니다. 이때 이중 연결 리스트 무결성 검사를 수행합니다.
  4. Unsorted bin 처리: unsorted bin에서 청크를 하나씩 꺼내 요청 크기와 비교합니다.
    • 정확히 일치하면 바로 반환
    • 크면 분할 후 나머지를 last_remainder로 설정
    • 불일치하면 적절한 small/large bin으로 이동
  5. Large bins 검색: 요청보다 크거나 같은 청크를 찾고, 필요 시 분할하여 남은 부분을 unsorted bin에 삽입합니다.
  6. Top chunk 할당: 위 단계에서 실패하면 top chunk에서 직접 분할합니다. 충분하지 않으면 sysmalloc을 호출해 OS로부터 추가 메모리를 확보합니다.

Fastbin 병합: malloc_consolidate

large chunk 할당 요청 시, fastbins 내의 청크들이 인접한 빈 청크들과 병합되어 unsorted bin으로 이동됩니다. 병합 과정은 다음과 같습니다:

  1. 각 fastbin을 순회하며 청크를 추출
  2. 이전 청크가 비어 있으면 통합 (unlink)
  3. 다음 청크가 top chunk가 아니면서 비어 있으면 통합
  4. 병합된 청크를 unsorted bin에 삽입

Arena와 멀티스레딩

ptmalloc은 스레드 간 경합을 줄이기 위해 여러 arena를 사용합니다:

  • Main Arena: 프로세스당 하나만 존재하며, 힙과 mmap 영역 모두 접근 가능
  • Thread Arenas: 각 스레드가 독립적인 arena를 가질 수 있음
  • 최대 arena 수:
    • 32비트: 2 × CPU 코어 수 + 1
    • 64비트: 8 × CPU 코어 수 + 1

새 스레드가 생성되면, 사용 가능한 arena를 순회하며 잠금이 없는 것을 찾아 할당받습니다.

정리: 할당 우선순위

전체 할당 흐름은 다음과 같은 우선순위를 따릅니다:

Fastbins → Small bins → Unsorted bin → Large bins → Top chunk → sysmalloc(mmap/brk)

이 구조는 빈번한 소규모 할당에 대해 높은 캐시 지역성을 제공하며, 시스템 콜 호출을 최소화함으로써 성능을 극대화합니다.

태그: ptmalloc glibc Malloc memory allocation heap management

6월 21일 17:45에 게시됨

인기 태그

©2026 괴물 클럽