간단한 세미스페이스 컬렉터 — wingolog

안녕하세요, 해크폴크 여러분. 오늘 글은 세미스페이스 컬렉터에 관한 이야기입니다. 이게 무엇인지는 많은 분이 알고 계시겠지만, 주석을 곁들인 구현을 직접 본 분은 그리 많지 않을 수 있으니 한번 해봅시다.

요약하자면, 세미스페이스 컬렉터는 한 덩어리 메모리를 크기가 같은 두 절반(스페이스)으로 나눕니다. 이름하여 _fromspace_와 _tospace_입니다. 할당은 tospace의 한쪽 끝에서 다른 쪽 끝으로 선형적으로 진행됩니다. tospace가 가득 차면 스페이스를 _flip_합니다: tospace가 fromspace가 되고, fromspace가 tospace가 됩니다. 컬렉터는 루트 객체 집합에서 시작하여 fromspace에 있는 모든 살아 있는 데이터를 tospace로 복사합니다(이름의 유래가 여기서 옵니다: from the fromspace to the tospace). 복사가 끝나면, 그다음 할당은 새 tospace에서 진행됩니다.

실제로 GC를 만들 때는 여러 측면에서 매개화되는데, 그중 하나가 GC 사용자가 객체를 어떻게 표현할지입니다. 예시로, 첫 번째 워드에 태그를 넣는 간단한 스킴을 보겠습니다:

struct gc_obj {
  union {
    uintptr_t tag;
    struct gc_obj *forwarded; // GC 용
  };
  uintptr_t payload[0];
};

시스템의 모든 코드를 GC 코드와 사용자 코드로 나눌 것입니다. GC의 사용자는 객체가 어떻게 표현되는지 정의합니다. 사용자 코드가 객체의 타입을 알고 싶을 때는 첫 번째 워드를 보고 태그를 확인합니다. 그런데 보시다시피 GC도 사용자 객체의 표현에 대해 요구사항이 있습니다: forwarded 멤버도 있어야 하죠.

static const uintptr_t NOT_FORWARDED_BIT = 1;
int is_forwarded(struct gc_obj *obj) {
  return (obj->tag & NOT_FORWARDED_BIT) == 1;
}
void* forwarded(struct gc_obj *obj) { 
  return obj->forwarded;
}
void forward(struct gc_obj *from, struct gc_obj *to) {
  from->forwarded = to;
}

forwarded는 _포워딩 포인터_입니다. GC가 객체를 fromspace에서 tospace로 복사할 때, fromspace에 있던 옛 사본의 첫 워드를 새 주소로 덮어씁니다. 이사해서 우편을 옛 주소에서 새 주소로 포워딩하는 것과 비슷합니다.

GC와 사용자 사이에는 계약이 있는데, 사용자는 자신의 객체 첫 워드에 항상 NOT_FORWARDED_BIT를 설정하기로 동의합니다. 이 비트는 객체가 포워드되었는지 아닌지를 GC가 검사하는 방법입니다. 할당은 보통 8바이트 같은 2의 거듭제곱 경계에 정렬되므로, 포워딩 포인터의 하위 비트는 결코 1로 설정되지 않습니다.

struct gc_heap;

// 사용자가 구현해야 함:
size_t heap_object_size(struct gc_obj *obj);
size_t trace_heap_object(struct gc_obj *obj, struct gc_heap *heap,
                         void (*visit)(struct gc_obj **field,
                                       struct gc_heap *heap));
size_t trace_roots(struct gc_heap *heap,
                   void (*visit)(struct gc_obj **field,
                                 struct gc_heap *heap));

GC와 사용자 간의 계약은 실제로 메모리 관리 시스템에서 가장 중요한 세부 중 하나입니다. GC 저자로서, 구현을 바꿀 자유를 지키기 위해 노출 인터페이스를 가능한 한 최소화하고 싶을 것입니다. 그렇다고 GC-사용자 인터페이스의 표면적이 최소 한도 아래로 내려갈 수는 없습니다. 예컨대 객체 할당의 핫 패스를 인라인할 수 있어야 하죠. 또한, 여기에서 보듯이, GC가 필요로 하지만 보통 사용자가 구현하는 연산들이 있습니다: 객체의 크기 계산, 그 참조를 추적하기, 루트 참조 추적 등이 그것입니다. 만약 GC 설계의 이 측면에 관심이 있다면, 지난 20년 동안 이 영역을 생산적으로 탐구해 온 MMTk(https://mmtk.io/)를 꼭 살펴보시길 권합니다.

struct gc_heap {
  uintptr_t hp;
  uintptr_t limit;
  uintptr_t from_space;
  uintptr_t to_space;
  size_t size;
};

이제 GC 구현으로 들어갑니다. 할당 핫 패스를 어떻게 인라인할지라는 부분을 제외하면, 여기의 내용은 사용자에게 노출될 필요가 없습니다. 위에서 세미스페이스 힙이 무엇인지 기본 정의를 했고, 아래에서 수집과 할당을 구현하겠습니다.

static uintptr_t align(uintptr_t val, uintptr_t alignment) {
  return (val + alignment - 1) & ~(alignment - 1);
}
static uintptr_t align_size(uintptr_t size) {
  return align(size, sizeof(uintptr_t));
}

모든 할당기는 어떤 최소 정렬 단위를 갖는데, 보통 대상 언어의 ABI 정렬보다 크거나 같은 2의 거듭제곱입니다. 대개 워드 한두 개입니다. 여기서는 한 워드(4 또는 8바이트)를 사용합니다.

struct gc_heap* make_heap(size_t size) {
  size = align(size, getpagesize());
  struct gc_heap *heap = malloc(sizeof(struct gc_heap));
  void *mem = mmap(NULL, size, PROT_READ|PROT_WRITE,
                   MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
  heap->to_space = heap->hp = (uintptr_t) mem;
  heap->from_space = heap->limit = space->hp + size / 2;
  heap->size = size;
  return heap;
}

힙을 만드는 일은 그저 큰 메모리를 한 덩어리 요청한 뒤, 그것을 반으로 나누는 것입니다. 이 공간을 어떻게 얻느냐는 플랫폼마다 다릅니다. 여기서는 mmap을 사용하고, 또한 struct gc_heap 메타데이터를 위해 플랫폼의 malloc도 사용합니다. 물론 mmap과 malloc이 둘 다 성공했는지 확인하고 싶을 겁니다 :)

struct gc_obj* copy(struct gc_heap *heap, struct gc_obj *obj) {
  size_t size = heap_object_size(obj);
  struct gc_obj *new_obj = (struct gc_obj*)heap->hp;
  memcpy(new_obj, obj, size);
  forward(obj, new_obj);
  heap->hp += align_size(size);
  return new_obj;
}

void flip(struct gc_heap *heap) {
  heap->hp = heap->from_space;
  heap->from_space = heap->to_space;
  heap->to_space = heap->hp;
  heap->limit = heap->hp + heap->size / 2;
}  

void visit_field(struct gc_obj **field, struct gc_heap *heap) {
  struct gc_obj *from = *field;
  struct gc_obj *to =
    is_forwarded(from) ? forwarded(from) : copy(heap, from);
  *field = to;
}

void collect(struct gc_heap *heap) {
  flip(heap);
  uintptr_t scan = heap->hp;
  trace_roots(heap, visit_field);
  while(scan < heap->hp) {
    struct gc_obj *obj = scan;
    scan += align_size(trace_heap_object(obj, heap, visit_field));
  }
}

여기에 실제 세미스페이스 수집 알고리즘이 있습니다! 아주 작은 코드지만, 이에 대해 사람들이 수많은 글을 썼죠. 사실 할 말이 많습니다—여기에서 다 하기는 어렵지만요.

개인적으로 세미스페이스 컬렉터의 가장 흥미로운 측면은 소위 “체니(Cheney) 스캐닝 알고리즘”이라고 생각합니다. visit_field에서 아직 추적되지 않은 객체를 보면, 그것을 tospace로 copy()만 하고 실제로 그 필드를 들여다보지는 않습니다. 대신 collect는 아직 추적되지 않은 복사된 객체가 들어 있는 tospace의 구간을 추적합니다. 즉 [scan, heap->hp) 범위에 있는 것들이죠. 체니 스캔은 이 공간을 훑어가며 scan을 앞으로 옮기고, 필요하면 더 많은 객체를 복사하여 heap->hp를 늘립니다. 그리고 ‘추적이 필요한’ 구간이 빌 때까지 계속됩니다. 추가 메모리가 전혀 필요 없는 꽤 깔끔한 해법입니다.

inline struct gc_obj* allocate(struct gc_heap *heap, size_t size) {
retry:
  uintptr_t addr = heap->hp;
  uintptr_t new_hp = align_size(addr + size);
  if (heap->limit < new_hp) {
    collect(heap);
    if (heap->limit - heap->hp < size) {
      fprintf(stderr, "out of memory\n");
      abort();
    }
    goto retry;
  }
  heap->hp = new_hp;
  return (struct gc_obj*)addr;
}

마지막으로, 할당기입니다: 애초에 우리가 GC를 갖는 이유죠. 빠른 경로는 단지 heap->hp를 반환하고, 다음 할당이 heap->hp + size를 반환하도록 상태를 준비합니다. 느린 경로는 collect()를 호출한 뒤 재시도합니다.

자, 이게 세미스페이스 컬렉터입니다. 다음에는 다시 에페메론에 관한 몇 가지 노트를 가지고 찾아오겠습니다. 그때까지, 즐거운 가비지 연휴 시즌 보내세요!