이번에 malloc을 구현하는 과제를 시작했다. 메모리 할당자를 구현하려면 고려해야할 부분들이 정말 많다(메모리 절약, 메모리 단편화 최소화, 속도, 지역성, 오류감지 등). 구현하기 앞서 glibc malloc이 어떻게 구현되어 있는지 궁금해서 찾아보았고 알게된 내용들을 정리하고자 한다.

ptmalloc2

리눅스 초기에는 dlmalloc을 사용했었다. dlmalloc은 둘 이상의 스레드가 동시에 호출할 경우 메모리가 공유 되었기 때문에 하나의 스레드만 임계 영역에 진입할 수 있었다. 따라서 퍼포먼스가 저하되는 문제가 있었다. ptmalloc2는 스레드마다 별도의 힙 영역을 유지함으로써 이러한 문제를 해결했고 리눅스의 기본 메모리 할당자가 되었다.

큰 틀을 이해하기 위해 전체적인 구조를 먼저 알아보겠습니다.

Chunk

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

ptmalloc2는 힙을 여러 개의 청크로 나누어 관리한다. 청크는 메타 데이터를 담고 있는 헤더와 유저 데이터로 구성된다.

prev_size는 인접한 Free Chunk의 크기이다. 청크를 병합하는 과정에서 이전 청크를 찾는데 사용된다. 만약 인접한 청크가 사용중이면 이 필드가 유저 데이터를 저장하기 위해 사용될 수 있다. mchunk_size는 헤더와 유저 데이터를 모두 포함한 해당 청크의 크기이다. 64bit 시스템에서 모든 청크들은 16바이트 정렬되므로 mchunk_size 필드의 하위 4bit는 사용되지 않는다. 따라서, ptmalloc2는 하위 3비트를 플래그 값으로 사용한다. 세 가지 플래그는 다음과 같이 정의된다.

• flags
  • PREV_INUSE(P): 인접한 이전 청크가 사용중일 때 사용
  • IS_MMAPPED(M): mmap()으로 할당된 청크일 때 사용
  • NON_MAIN_ARENA(A): 청크가 non-main arena에서 할당된 청크일 때 사용

fd(Forward pointer),bk(Backword pointer) fd_nextsize,bk_nextsize는 Free Chunk일 경우에만 사용된다.fd는 다음 Free Chunk의 주소를 가지고 bk는 이전 Free Chunk의 주소를 가진다. fd_nextsize,bk_nextsize는 large chunk인 경우에만 사용된다. large chunk들은 저장될 때 크기 순으로 내림차순 정렬되는데 이 때 사용된다.

Bin

빈은 Free Chunk들이 저장되는 곳이다. ptmalloc2는 할당 요청이 들어오면 빈에서 적절한 청크를 찾아 빠르게 재할당한다. ptmalloc2에는 128개의 빈이 정의되어 있으며 이 중 62개는 small bin, 63개는 large bin, 1개는 unsorted bin으로 사용되고, 나머지 2개는 사용되지 않는다.

Fast bin

단방향 연결리스트로 구성되고 LIFO를 사용한다. 64비트에서 포함되는 청크 크기는 32, 48, 64, 80, 96, 112, 128이며 16바이트 단위로 총 7개의 fast bin이 있다.

작은 크기의 청크들은 빈번하게 할당 및 해제 되는 경향이 있어 이들을 빠르게 하는 것이 전체적인 성능에 있어 중요하다. fast bin 범위 밖의 모든 Free Chunk들은 범위에 맞는 bin에 들어가기 전에 이후에 설명할 unsorted bin에 먼저 들어가게 되는데, 이 과정에서 인접한 청크와 병합이 일어난다. 또한 unsorted bin에 있는 Free Chunk들이 재사용 되기 위해서는 탐색을 통해 각 범위에 맞는 bin으로 분류해줘야 한다.fast bin 범위의 청크들은 unsorted bin에 포함되지 않고 바로 분류되기 때문에 다른 범위에 청크들보다 더 빠르게 할당 및 해제될 수 있다.

하지만, 인접한 청크와 병합을 하지 않으면 memory fragmentation이 발생할 수 있다. 따라서, ptmalloc2는 요청 청크 크기가 small bin 범위 밖이면 모든 fast bin청크들을 병합시켜 하나의 큰 청크로 만든다. 이 것은 큰 크기의 메모리 요청을 받으면 당분간 작은 크기의 요청이 없을 것이라고 예상할 수 있기 때문이다. ptmalloc2는 이러한 방식으로 memory fragmentation을 줄이면서, 작은 크기의 청크들을 빠르게 재사용하고 해제한다.

Small bin

원형 양방향 연결 리스트로 구성되고 FIFO를 사용한다. 64비트에서 포함되는 청크 크기는 32~1008바이트이며 16바이트 단위로 총 62개의 small bin이 있다.

small bin 범위의 청크의 해제 요청이 들어오면, 인접한 청크의 PREV_INUSE 플래그를 확인하고, Free Chunk인 경우, 병합해서 unsorted bin에 추가된다.

Large bin

원형 양방향 연결 리스트로 구성되고 64비트에서 1024바이트 이상의 크기를 갖는 청크들이 포함되며 총 63개의 large bin이 있다. fast bin, small bin과 달리 단일 bin에 일정 범위 안에 크기를 갖는 청크들을 모두 포함한다.

범위 안의 다양한 크기의 청크들이 포함되기 때문에, 요청 청크 크기와 가장 비슷한 청크를 꺼내서 할당한다. 이 과정을 효율적으로 하기 위해 large bin의 청크들은 크기 내림차순으로 정렬된다. small bin과 마찬가지로, 인접한 청크가 있다면 병합된다.

Unsorted bin

원형 양방향 리스트로 구성되고 FIFO를 사용하며 하나의 빈만 존재한다.

unsorted bin을 사용하는 이유는 무엇일까? 프로그램들은 한번에 여러 청크들을 연속적으로 해제하는 경우가 많다. 해제된 청크들을 매번 해당 범위의 빈으로 분류하게 되면 퍼포먼스 저하가 심할 것이다. ptmalloc2는 성능을 위해, fast bin 범위 밖의 청크들이 해제되면 우선 unsorted bin에 추가한다.

각 범위의 bin으로 분류되는 작업은 유저가 요청한 크기의 청크가 fast bin, small bin에 없어 unsorted bin을 탐색해야할 때 일어난다. 유저가 요청한 크기의 청크가 있는지 순차 탐색하면서 일치하지 않는 청크는 small bin, large bin으로 분류하고 일치하는 청크를 찾으면 그 청크를 반환한다.

128KB보다 큰 메모리 요청

크기가 128KB 이상인 요청이 들어오면 새 메모리를 매핑하기 위해 mmap을 호출하고 해당 메모리에서 청크를 할당한다. 이 청크는 bin에 포함되지 않으며, IS_MMAPPED 플래그가 설정된다. 해제 요청이 들어오면 munmap을 통해 해제한다.

Top chunk

top chunk는 arena 상단에 있는 청크이며 빈에 포함되지 않는다. 모든 bins에 적당한 청크가 없는 경우 top chunk를 사용한다. top chunk의 크기가 요청 크기보다 큰 경우, top chunk는 알맞은 크기의 청크와 나머지 청크로 분할되어 나머지 청크는 새로운 top chunk가 된다.

top chunk의 크기가 요청 크기보다 작은 경우, ptmalloc2는 내부 함수인 sysmalloc을 호출하여 top chunk의 크기를 늘리거나 새로운 힙 영역을 할당한다.

Arena

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

arena는 앞에서 언급한 빈들이 포함되는 malloc_state 구조체를 타입으로 갖는 변수이다. ptmalloc2는 멀티 스레딩 환경에서 race condition을 방지하기 위해 arena에 뮤텍스를 사용한다. 하지만 만약 arena가 모든 스레드 사이에서 공유된다면 하나의 스레드만 임계 구역에 진입할 수 있으므로 퍼포먼스 저하가 심할 것이 분명하다.

따라서, 속도를 위해 스레드당 별도의 arena를 사용한다. 다만 arena의 최대 갯수를 제한하고 있기 때문에 그보다 많은 스레드를 생성할 경우 더 이상 arena를 생성할 수 없다. 따라서, 이런 경우에 추가된 스레드는 존재하는 arena 중에서 가장 마지막에 접근된 arena를 공유하여 사용한다.

malloc sequence

할당 과정을 간단하게 요약하면 아래와 같다.

1. 유저가 요청한 사이즈를 청크 사이즈로 조정한다(헤더 사이즈를 추가하고 MINSIZE 이상 이면서 MALLOC_ALIGNMENT 배수인 사이즈)
2. fast bin 범위 안의 사이즈인지 체크한다. 맞다면 fast bin에서 적절한 Free Chunk가 있는지 찾는다. 있다면 반환된다.
3. fast bin 범위 밖이거나 fast bin에 적절한 Free Chunk가 없다면 small bin 범위인지 체크한다. 맞다면 small bin에서 적절한 Free Chunk가 있는지 찾는다. 있다면 반환된다.
4. 이 시점에서 요청 청크 사이즈가 small bin보다 크면 arena의 have_fastchunks 필드를 사용하여 fast bin에 청크가 있는지 확인하고 있다면 모든 청크를 병합하여 하나의 청크로 만든다. 이 청크는 unsorted bin의 맨 앞에 추가된다.
5. unsorted bin의 모든 청크를 탐색한다. 이 과정에서 각 청크들은 요청을 만족시키는 적절한 청크를 찾을 때까지 각 범위에 해당하는 bin으로 분류된다.
   • 단, 요청 청크 사이즈가 small bin 범위 안에 있고, 현재 청크가 last remainder chunk이자 unsorted bin에 있는 유일한 청크이고, (요청 청크 사이즈 + MINSIZE) > 현재 청크인 경우, 현재 청크는 유저에게 반환할 청크와 나머지 청크 두 개로 분할된다. 나머지 청크는 새로운 last remainder chunk가 된다.
6. unsorted bin에는 적절한 청크가 없었다. 이제 요청 청크 사이즈가 large bin 범위인지 체크한다. 맞다면 large bin을 사용한다.
   • large bin은 크기 내림차순 정렬된다고 위에서 언급했었다. 우선 large bin의 가장 앞에 있는 청크의 크기(가장 큰 청크)와 요청 청크 사이즈를 비교한다. 만약 요청 청크 사이즈가 더 작다면, bk_nextsize 필드를 사용해서 large bin의 가장 작은 청크부터 탐색한다. 요청 청크 사이즈 이상인 청크가 있으면 멈춘다.
   • large bin은 범위 안에 다양한 크기의 청크들이 포함된다고 했었다. 찾은 청크가 요청 청크 사이즈보다 클 수 있다. 만약 (찾은 청크 사이즈 - 요청 청크사이즈) >= MINSIZE이면 요청 청크사이즈와 나머지 청크로 분할하고 나머지 청크를 unsorted bin에 추가한다. (찾은 청크 사이즈 - 요청 청크사이즈) < MINSIZE이면 분할하지않고 그대로 유저에게 반환한다.
7. 이제 요청 청크 사이즈에 딱 맞는 청크를 찾지 못했으므로 bins의 index를 증가시켜 더 큰 크기의 사용가능한 청크가 있는지 찾는다.
   • 이 과정에서 arena의 binmap을 사용하여 비어있지 않은 빈중에 가장 작은 크기의 빈을 빠르게 찾을 수 있다.
   • 찾은 청크는 요청 청크 사이즈보다 크다. 만약 (찾은 청크 사이즈 - 요청 청크 사이즈) >= MINSIZE이면 유저에게 반환할 청크와 나머지 청크로 분할된다. 나머지 청크는 unsorted bin에 추가된다. 단, 요청 청크 사이즈가 small bin 범위 안쪽이면 나머지 청크는 추가로 last remainder chunk가 된다. (찾은 청크 사이즈 - 요청 청크 사이즈) < MINSIZE이면 분할되지 않고 그대로 반환된다.
8. 모든 bin을 탐색했음에도 찾지 못했다면 top chunk가 사용된다.
   • 만약, top chunk size >= (요청 청크 사이즈 + MINSIZE)이면 유저 반환 청크와 나머지 청크로 분할된다. 나머지 청크는 새로운 top chunk가 된다.
   • 그렇지 않은 경우, 먼저 arena의 have_fastchunks 필드를 사용해서 fast bin에 청크가 있는지 확인한다. 있다면, 병합하고 위의 5번 과정을 다시 시작한다.
   • fast bin에 청크가 없는 경우, sysmalloc을 호출하여 메모리를 할당하고 유저 반환 청크와 나머지 청크로 분할한 후, 나머지 청크를 새로운 top chunk로 설정한다.

arena의 last_remainder는 Spatial Locality을 만족시키기 위해 사용된다. 7번 과정에서 small bin 범위 안의 요청에서 분할된 청크를 last remainder chunk에 보관해놓고, 이후에 다시 small bin 범위 안의 요청이 들어왔을 때 last remainder chunk에서 분할해서 반환해주면 청크들은 서로 인접하게 된다.

mallopt

mallopt으로 파라미터를 설정해서 malloc의 동작 방식을 수정할 수 있다.

https://man7.org/linux/man-pages/man3/mallopt.3.html