malloc 튜토리얼

malloc을 하나 작성해 보고, 기존 프로그램과 함께 어떻게 동작하는지 살펴보자!

이 글은 Marwan Burelle의 이 튜토리얼을 읽은 뒤에 내가 한 일을(앉아서 직접 구현을 써 본 것) 좀 더 확장해서 설명한 것이다. 그래서 단계는 꽤 비슷할 것이다. 구현상의 주요 차이는 내 버전이 더 단순하고 메모리 단편화에 더 취약하다는 점이다. 설명 방식 면에서는 내 스타일이 훨씬 더 캐주얼하다.

이 튜토리얼은 포인터가 무엇인지 알고 있고, C를 충분히 알아서 *ptr이 포인터를 역참조(dereference)한다는 것, ptr->foo가 (*ptr).foo를 의미한다는 것, malloc이 동적으로 공간을 할당하는 데 쓰인다는 것, 그리고 연결 리스트(linked list) 개념에 익숙하다고 가정한다. C 기초 입문용으로는 Pointers on C가 내가 좋아하는 책 중 하나다. 이 코드를 한 번에 보고 싶다면 여기에 있다.

서론은 이쯤 하고, malloc의 함수 시그니처는 다음과 같다.

void *malloc(size_t size);

입력으로 바이트 수를 받고, 그 크기의 메모리 블록을 가리키는 포인터를 반환한다.

이를 구현하는 방법은 여러 가지가 있다. 여기서는 임의로 sbrk를 사용하기로 하자. OS는 프로세스에 대해 스택과 힙 공간을 예약하고, sbrk는 우리가 힙을 조작할 수 있게 해 준다. sbrk(0)는 현재 힙의 맨 위(top)를 가리키는 포인터를 반환한다. sbrk(foo)는 힙 크기를 foo만큼 증가시키고, 이전의 힙 top을 가리키는 포인터를 반환한다.

정말 단순한 malloc을 구현하고 싶다면, 다음처럼 할 수 있다.

#include <assert.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

void *malloc(size_t size) {
  void *p = sbrk(0);
  void *request = sbrk(size);
  if (request == (void*) -1) {
    return NULL; // sbrk 실패.
  } else {
    assert(p == request); // 스레드 안전하지 않음.
    return p;
  }
}

프로그램이 malloc에 공간을 요청하면, malloc은 sbrk에게 힙 크기를 늘리라고 요청하고 새로 생긴 힙 영역의 시작 주소를 반환한다. 기술적으로는 malloc(0)이 NULL을 반환하거나, free에 넘겨도 문제를 일으키지 않는 다른 포인터를 반환해야 한다는 조건이 빠져 있지만, 대체로 동작한다.

그런데 free는 어떻게 동작할까? free의 프로토타입은

void free(void *ptr);

free가 이전에 malloc이 반환했던 포인터를 받으면, 해당 공간을 해제해야 한다. 하지만 우리 malloc이 할당한 포인터를 받았을 때, 그 포인터에 해당하는 블록의 크기가 얼마인지 알 방법이 없다. 그 정보는 어디에 저장해야 할까? 동작하는 malloc이 있다면 추가로 malloc해서 거기에 저장할 수도 있겠지만, malloc이 공간을 예약하려고 malloc을 호출해야 하는 상황이 되어 문제가 생긴다.

이를 우회하는 흔한 트릭은, 반환할 포인터 바로 아래(앞쪽)에 우리가 숨겨 둔 공간에 메모리 영역에 대한 메타 정보를 저장하는 것이다. 예를 들어 현재 힙 top이 0x1000이고 0x400 바이트를 요청한다고 하자. 현재 malloc은 sbrk로 0x400 바이트를 요청하고 0x1000을 반환한다. 대신 블록 정보를 저장하기 위해 예컨대 0x10 바이트를 남겨 둔다면, malloc은 sbrk로 0x410 바이트를 요청하고 0x1010을 반환하여 0x10 바이트의 메타정보 블록을 malloc을 호출한 코드로부터 숨길 수 있다.

이렇게 하면 블록을 free할 수는 있다. 그런데 그다음은? OS에서 받은 힙 영역은 연속적(contiguous)이어야 하므로, 중간에 있는 메모리 블록을 OS에 그대로 반환할 수 없다. 새로 해제된 영역 위에 있는 모든 것을 아래로 복사해서 구멍을 메운 다음 끝에서 공간을 반환하겠다고 해도, 힙을 가리키는 포인터를 가진 모든 코드에 “포인터를 조정하라”고 알릴 방법이 없다.

대신, OS에 반환하지는 않고 해당 블록이 free되었다고 표시해 두면 이후 malloc 호출이 그 블록을 재사용할 수 있다. 하지만 그러려면 각 블록의 메타 정보를 접근할 수 있어야 한다. 이를 위한 해법은 다양하지만, 여기서는 단순함을 위해 단일 연결 리스트 하나를 사용하기로 하자.

그러면 각 블록마다 대략 이런 구조체가 필요하다.

struct block_meta {
  size_t size;
  struct block_meta *next;
  int free;
  int magic; // 디버깅 용도. TODO: 비디버그 모드에서는 제거.
};

#define META_SIZE sizeof(struct block_meta)

블록 크기, free 여부, 다음 블록이 무엇인지 알아야 한다. 여기에 디버깅을 위한 매직 넘버가 있는데 꼭 필요하진 않다. 임의의 값으로 설정해 두면, 어떤 코드가 마지막으로 이 구조체를 수정했는지 쉽게 파악할 수 있다.

연결 리스트의 head도 필요하다.

void *global_base = NULL;

malloc은 가능하면 free 공간을 재사용하고, 재사용할 수 없을 때만 새로 할당하도록 하고 싶다. 연결 리스트 구조가 있으니, free 블록이 있는지 확인하고 반환하는 건 간단하다. 어떤 크기의 요청이 오면, 리스트를 순회하면서 충분히 큰 free 블록이 있는지 찾는다.

struct block_meta *find_free_block(struct block_meta **last, size_t size) {
  struct block_meta *current = global_base;
  while (current && !(current->free && current->size >= size)) {
    *last = current;
    current = current->next;
  }
  return current;
}

free 블록을 못 찾으면, sbrk로 OS에 공간을 요청하고 새 블록을 연결 리스트 끝에 붙여야 한다.

struct block_meta *request_space(struct block_meta* last, size_t size) {
  struct block_meta *block;
  block = sbrk(0);
  void *request = sbrk(size + META_SIZE);
  assert((void*)block == request); // 스레드 안전하지 않음.
  if (request == (void*) -1) {
    return NULL; // sbrk 실패.
  }

  if (last) { // 첫 요청에서는 NULL.
    last->next = block;
  }
  block->size = size;
  block->next = NULL;
  block->free = 0;
  block->magic = 0x12345678;
  return block;
}

원래 구현과 마찬가지로 sbrk로 공간을 요청한다. 다만 구조체를 저장할 추가 공간을 더 요청하고, 구조체의 필드들을 적절히 설정한다.

이제 기존 free 공간을 확인하는 헬퍼와 공간을 요청하는 헬퍼가 있으니, malloc은 단순해진다. global_base가 NULL이면 공간을 요청하고 base 포인터를 새 블록으로 설정한다. NULL이 아니면 기존 공간을 재사용할 수 있는지 확인한다. 가능하면 재사용하고, 아니면 새 공간을 요청해 사용한다.

void *malloc(size_t size) {
  struct block_meta *block;
  // TODO: size 정렬?

  if (size <= 0) {
    return NULL;
  }

  if (!global_base) { // 첫 호출.
    block = request_space(NULL, size);
    if (!block) {
      return NULL;
    }
    global_base = block;
  } else {
    struct block_meta *last = global_base;
    block = find_free_block(&last, size);
    if (!block) { // free 블록을 찾지 못함.
      block = request_space(last, size);
      if (!block) {
        return NULL;
      }
    } else {      // free 블록을 찾음
      // TODO: 여기서 블록 분할을 고려.
      block->free = 0;
      block->magic = 0x77777777;
    }
  }

  return(block+1);
}

C에 익숙하지 않은 사람을 위해 설명하자면, block+1을 반환하는 이유는 block_meta 뒤의 영역을 가리키는 포인터를 반환하고 싶기 때문이다. block은 struct block_meta 타입 포인터이므로, +1은 주소를 sizeof(struct block_meta)만큼 증가시킨다.

만약 free 없는 malloc만 원했다면 처음의 훨씬 간단한 malloc로 충분했을 것이다. 그러니 free를 작성해 보자! free가 해야 할 주된 일은 ->free를 설정하는 것이다.

코드 여러 곳에서 구조체 주소를 얻어야 하니, 함수로 정의하자.

struct block_meta *get_block_ptr(void *ptr) {
  return (struct block_meta*)ptr - 1;
}

이제 free는 다음과 같다.

void free(void *ptr) {
  if (!ptr) {
    return;
  }

  // TODO: 블록 분할을 구현한 뒤 블록 병합을 고려.
  struct block_meta* block_ptr = get_block_ptr(ptr);
  assert(block_ptr->free == 0);
  assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
  block_ptr->free = 1;
  block_ptr->magic = 0x55555555;
}

->free를 설정하는 것 외에도, NULL 포인터로 free를 호출하는 건 유효하므로 NULL 체크가 필요하다. 또한 free는 임의의 주소나 이미 free된 블록에 호출되면 안 되므로, 그런 일은 일어나지 않는다고 assert로 가정할 수 있다.

assert는 반드시 필요하진 않지만, 디버깅을 훨씬 쉽게 만들어 주는 경우가 많다. 실제로 내가 이 코드를 작성할 때 assert가 없었다면 조용한 데이터 손상으로 이어졌을 버그가 있었다. 하지만 assert에서 바로 터졌고, 덕분에 디버깅이 아주 쉬웠다.

이제 malloc과 free가 있으니 커스텀 메모리 할당기로 프로그램을 작성할 수 있다! 하지만 기존 코드에 이 할당기를 끼워 넣으려면 realloc과 calloc도 구현해야 한다. calloc은 메모리를 0으로 초기화하는 malloc일 뿐이니, 먼저 realloc을 보자. realloc은 malloc/calloc/realloc으로 얻은 메모리 블록의 크기를 조정해야 한다.

realloc의 함수 프로토타입은

void *realloc(void *ptr, size_t size)

realloc에 NULL 포인터를 넘기면 malloc처럼 동작해야 한다. 이전에 malloc된 포인터를 넘기면, 새 크기가 이전보다 작을 때는 공간을 줄여야 하고, 새 크기가 더 클 때는 더 큰 공간을 할당한 뒤 기존 데이터를 복사해야 한다.

크기가 줄어들 때 실제로 리사이즈하지 않고 아무것도 free하지 않아도 프로그램은 동작하겠지만, 크기가 늘어날 때 더 큰 공간을 할당하는 것은 반드시 해야 한다. 그러니 그것부터 하자.

void *realloc(void *ptr, size_t size) {
  if (!ptr) {
    // NULL ptr. realloc은 malloc처럼 동작해야 함.
    return malloc(size);
  }

  struct block_meta* block_ptr = get_block_ptr(ptr);
  if (block_ptr->size >= size) {
    // 충분한 공간이 있음. split을 구현하면 일부를 free할 수 있음.
    return ptr;
  }

  // 진짜 realloc이 필요함. 새 공간을 malloc하고 기존 공간을 free.
  // 그 다음 기존 데이터를 새 공간으로 복사.
  void *new_ptr;
  new_ptr = malloc(size);
  if (!new_ptr) {
    return NULL; // TODO: 실패 시 errno 설정.
  }
  memcpy(new_ptr, ptr, block_ptr->size);
  free(ptr);
  return new_ptr;
}

이제 calloc으로 넘어가자. calloc은 포인터를 반환하기 전에 메모리를 0으로 지운다.

void *calloc(size_t nelem, size_t elsize) {
  size_t size = nelem * elsize; // TODO: 오버플로 체크.
  void *ptr = malloc(size);
  memset(ptr, 0, size);
  return ptr;
}

여기서는 nelem * elsize의 오버플로를 체크하지 않는데, 사실 스펙상 요구되는 사항이다. 여기의 코드는 “대충 얼추 돌아가는” 정도로만 최소한 작성한 것이다.

이제 “대충 얼추 돌아가는” 것이 있으니, 기존 프로그램과 함께 사용해 볼 수 있다(그리고 프로그램을 다시 컴파일할 필요도 없다)!

먼저 코드를 컴파일해야 한다. 리눅스에서는 대략 다음처럼 하면 된다.

clang -O0 -g -W -Wall -Wextra -shared -fPIC malloc.c -o malloc.so

-g는 디버그 심볼을 추가해서 gdb나 lldb로 코드를 볼 수 있게 해준다. -O0는 최적화를 끄므로 디버깅에 도움이 된다(변수가 최적화로 사라지는 일을 줄여준다). -W -Wall -Wextra는 추가 경고를 켠다. -shared -fPIC는 동적 링크를 가능하게 하는데, 이것이 우리가 기존 바이너리에 우리 코드를 주입할 수 있게 해준다!

Mac에서는 다음 같은 옵션이 필요하다.

clang -O0 -g -W -Wall -Wextra -dynamiclib malloc.c -o malloc.dylib

참고로 최근 OS X에서는 sbrk가 deprecated이다. 애플의 deprecated 정의는 좀 특이해서, 어떤 deprecated syscall은 심각하게 망가져 있기도 하다. 나는 이걸 Mac에서 제대로 테스트하지 않았으니, 이상한 실패가 나거나 그냥 동작하지 않을 수도 있다.

이제 리눅스에서 어떤 바이너리가 우리 malloc을 쓰게 하려면 LD_PRELOAD 환경 변수를 설정해야 한다. bash를 쓴다면 이렇게 하면 된다.

export LD_PRELOAD=/absolute/path/here/malloc.so

Mac이라면 다음을 원할 것이다.

export DYLD_INSERT_LIBRARIES=/absolute/path/here/malloc.so

모든 게 잘 되면 임의의 바이너리를 실행해도 정상 실행될 것이다(다만 조금 느릴 수 있다).

$ ls
Makefile  malloc.c  malloc.so  README.md  test  test-0  test-1  test-2  test-3  test-4

버그가 있으면 이런 걸 보게 될 수도 있다.

$ ls
Segmentation fault (core dumped)

디버깅

디버깅에 대해 이야기해 보자! 브레이크포인트 설정, 메모리 검사, 코드 스텝 실행 같은 디버거 사용에 익숙하다면 이 섹션은 건너뛰고 바로 연습문제로 가도 된다.

이 섹션은 여러분이 시스템에 gdb를 설치하는 방법 정도는 알아낼 수 있다고 가정한다. Mac이라면 lldb를 쓰고 명령을 적절히 바꾸면 된다. 어떤 버그를 만나게 될지 모르니, 여기서는 내가 일부러 버그를 몇 개 넣고 그것을 어떻게 추적하는지 보여주겠다.

우선 gdb가 세그폴트 없이 실행되게 해야 한다. ls가 세그폴트 나는데 gdb ls를 실행하면 gdb도 세그폴트 날 가능성이 높다. 이를 위한 래퍼를 만들 수도 있지만 gdb 자체가 지원한다. gdb를 시작한 다음 프로그램을 실행하기 전에 set environment LD_PRELOAD=./malloc.so를 실행하면, LD_PRELOAD가 평소처럼 적용된다.

$ gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) run
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7bd7dbd in free (ptr=0x0) at malloc.c:113
113       assert(block_ptr->free == 0);

예상대로 세그폴트가 났다. list로 세그폴트 근처 코드를 볼 수 있다.

(gdb) list
108     }
109
110     void free(void *ptr) {
111       // TODO: consider merging blocks once splitting blocks is implemented.
112       struct block_meta* block_ptr = get_block_ptr(ptr);
113       assert(block_ptr->free == 0);
114       assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
115       block_ptr->free = 1;
116       block_ptr->magic = 0x55555555;
117     }

그 다음 p(print)로 변수 상태를 볼 수 있다.

(gdb) p ptr
$6 = (void *) 0x0
(gdb) p block_ptr
$7 = (struct block_meta *) 0xffffffffffffffe8

ptr가 0, 즉 NULL이어서 문제가 난 것이다. NULL 체크를 빼먹었다.

이제 조금 더 어려운 버그를 보자. 예컨대 구조체를 다음처럼 바꾸기로 했다고 하자.

struct block_meta {
  size_t size;
  struct block_meta *next;
  int free;
  int magic;    // 디버깅 용도. TODO: 비디버그 모드에서는 제거.
  char data[1];
};

그리고 malloc에서 block+1 대신 block->data를 반환하되, 다른 변경은 하지 않았다. 구조체 끝을 가리키는 멤버를 하나 정의하고 그 포인터를 반환하는 것으로, 우리가 하던 것과 비슷해 보인다.

하지만 이 새 malloc을 쓰면 이런 일이 생긴다.

$ /bin/ls
Segmentation fault (core dumped)
gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) run

Program received signal SIGSEGV, Segmentation fault.
_IO_vfprintf_internal (s=s@entry=0x7fffff7ff5f0, format=format@entry=0x7ffff7567370 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", ap=ap@entry=0x7fffff7ff718) at vfprintf.c:1332
1332    vfprintf.c: No such file or directory.
1327    in vfprintf.c

지난번 에러만큼 친절하지는 않다. assert가 실패한 것은 보이지만, gdb가 assert 실패 시 출력하려고 호출되는 printf 함수 안으로 들어가 버린다. 그런데 그 printf 함수도 우리 버그 있는 malloc을 쓰고, 그 과정에서 또 터진다!

여기서 할 수 있는 한 가지는 ap를 조사해서 assert가 무엇을 출력하려 했는지 보는 것이다.

(gdb) p *ap
$4 = {gp_offset = 16, fp_offset = 48, overflow_arg_area = 0x7fffff7ff7f0, reg_save_area = 0x7fffff7ff730}

이건 잘 작동한다. 계속 파고들어서 어떤 내용이 출력되려 했는지 알아내고 그 방식으로 실패 원인을 찾을 수 있다. 다른 해결책으로는 malloc을 쓰지 않는 커스텀 assert를 작성하거나, assert가 우리 malloc을 쓰지 않도록 하는 적절한 훅을 사용하는 방법도 있다.

하지만 이 경우엔 코드에 assert가 몇 개 없다는 걸 알고 있다. 멀티스레드 프로그램에서 쓰지 말라는 malloc 내부 assert 하나, 그리고 free에서 잘못된 것을 해제하지 않는지 확인하는 assert 두 개. 먼저 free를 보자. 브레이크포인트를 설정한다.

$ gdb /bin/ls
(gdb) set environment LD_PRELOAD=./malloc.so
(gdb) break free
Breakpoint 1 at 0x400530
(gdb) run /bin/ls

Breakpoint 1, free (ptr=0x61c270) at malloc.c:112
112       if (!ptr) {

아직 block_ptr가 설정되지 않았지만, s로 몇 번 스텝 실행해서 설정된 뒤 값을 보면 된다.

(gdb) s
(gdb) s
(gdb) s
free (ptr=0x61c270) at malloc.c:118
118       assert(block_ptr->free == 0);
(gdb) p/x *block_ptr
$11 = {size = 0, next = 0x78, free = 0, magic = 0, data = ""}

p 대신 p/x를 써서 16진수로 보이게 했다. magic이 0인데, free하려는 유효한 구조체라면 0일 수가 없다. get_block_ptr가 잘못된 오프셋을 반환하는 걸까? ptr이 있으니 다른 오프셋들을 바로 확인할 수 있다. ptr는 void *이므로, gdb가 결과를 해석할 수 있게 캐스팅해야 한다.

(gdb) p sizeof(struct block_meta)
$12 = 32
(gdb) p/x *(struct block_meta*)(ptr-32)
$13 = {size = 0x0, next = 0x78, free = 0x0, magic = 0x0, data = {0x0}}
(gdb) p/x *(struct block_meta*)(ptr-28)
$14 = {size = 0x7800000000, next = 0x0, free = 0x0, magic = 0x0, data = {0x78}}
(gdb) p/x *(struct block_meta*)(ptr-24)
$15 = {size = 0x78, next = 0x0, free = 0x0, magic = 0x12345678, data = {0x6e}}

사용하던 주소에서 조금 더 뒤로 물러서면, 올바른 오프셋이 32가 아니라 24라는 것을 알 수 있다. 구조체는 패딩이 들어가서 sizeof(struct block_meta)가 32가 되기 때문이다. 마지막 유효 멤버가 24에 있어도 말이다. 그 여분 공간을 없애려면 get_block_ptr를 고쳐야 한다.

이걸로 디버깅 섹션은 끝!

연습문제

개인적으로 이런 건 연습을 해보지 않으면 잘 머리에 남지 않아서, 관심 있는 사람을 위해 몇 가지 연습문제를 남긴다.

1. malloc은 “모든 내장 타입에 대해 적절히 정렬된(suitably aligned) 포인터”를 반환해야 한다. 우리의 malloc은 그렇게 하고 있는가? 그렇다면 왜 그런가? 아니라면 정렬을 고쳐라. “모든 내장 타입”은 C 기준으로 대체로 8바이트까지라고 보면 된다(SSE/AVX 타입은 내장 타입이 아님).

2. 기존 블록을 재사용하는데 필요한 것보다 큰 블록을 그대로 쓰면 낭비가 심하다. 필요한 최소 공간만 쓰도록 블록을 분할(split)하는 함수를 구현하라.

3. 2를 한 뒤, 랜덤한 크기로 malloc/free를 많이 반복하면 작은 블록들이 많이 생겨서 작은 요청에만 재사용 가능해진다. 인접한 free 블록들을 병합(merge)해서 연속된 free 블록은 하나의 블록으로 합쳐지게 하라.

4. 기존 코드의 버그를 찾아라! 많이 테스트하지 않았으니, “대충 얼추” 동작한다 해도 버그가 있을 것이 확실하다.

자료

위에서 언급했듯이 Marwan Burelle의 튜토리얼이 있다.

리눅스의 메모리 관리에 대해 더 알고 싶다면 Gustavo Duarte의 이 글을 보라.

현실의 malloc 구현이 어떻게 동작하는지 더 보려면 dlmalloc과 tcmalloc이 모두 훌륭한 읽을거리다. 나는 jemalloc 코드는 아직 읽어보지 않았고, 이해하기가 좀 더 어렵다고 들었지만, 가장 널리 쓰이는 고성능 malloc 구현이기도 하다.

디버깅에 도움이 되는 도구로 Address Sanitizer는 정말 훌륭하다. 스레드 안전한 버전을 작성하고 싶다면, Thread Sanitizer도 좋은 도구다.

Matias Garcia Isaia 덕분에 이 글의 스페인어 번역도 있다.

감사의 말

sbrk를 설명하기 위해 이미지 하나를 사용할 수 있게 해 준 Gustavo Duarte에게 감사한다. 또한 Ian Whitlock, Danielle Sucher, Nathan Kurz, "tedu", @chozu@fedi.absturztau.be, David Farrel에게도 코멘트/교정/토론에 대해 감사한다. 이 글에서(글이든 코드든) 다른 버그를 발견하면 알려 달라.