Alkyne 언어를 위해 설계한 단순하면서도 현실적인 가비지 컬렉터와 메모리 할당기를 소개합니다. 고정 크기 블록·프리 리스트·분할/병합·슬랩과 같은 전형적 기법을 바탕으로, 페이지 디스크립터(Pd) 배열, 리움(ream) 단위의 페이지 관리, 마크-스윕(즉시 아포칼립스 최적화 포함), 프리 리스트 재구성 등 핵심 아이디어를 단계적으로 설명합니다.
Alkyne은 몇 해 전 제가 구성 블롭을 생성하기 위해 만든 스크립팅 언어입니다. 인터프리터는 ARC2로 메모리를 관리하는 단순한 AST 워커1라 꽤 느리고, 저는 점차 새 평가 엔진을 작성하고 있습니다.
이 글은 Alkyne 자체에 대한 것이 아닙니다(그건 다음에). 지금은 제가 이를 위해 작성한 GC3에 대한 메모를 남기고, 더 일반적으로는 메모리 할당기(특히 GC와 공모하고 싶은 종류)에 대한 입문을 제공하려 합니다.
이 글은 포인터와 시스템 콜 같은 로우레벨 프로그래밍의 기초에 익숙한 분들을 대상으로 합니다. Alkyne의 GC는 단순하면서도 적절한 성능을 갖도록 설계되었습니다. 즉, 설계에는 할당기에서 흔히 보이는 “전형(트로프)”은 모두 담되, 까다로운 요소는 배제했습니다.
이 글을 통해 할당기나 GC가 처음인 독자들이 이러한 트로프와 현대 할당기에서의 역할을 이해하길 바랍니다.
이 글의 여러 초안에 피드백을 주신 James Farrell, Manish Goregaokar, Matt Kulukundis, JeanHeyd Meneide, Skye Thompson, Paul Wankadia께 감사드립니다. 제대로 쓰기가 정말 어려웠어요. :)
Alkyne GC는 매우 특정한 문제를 해결하며, 덕분에 실제로 해야 할 일을 제한할 수 있습니다. Alkyne은 JavaScript처럼 “임베더블” 언어이므로 힙이 커질 의도가 없습니다. 사실 메모리 사용 최적화를 위해 32비트 포인터(4GB 주소 공간)를 쓰는 것이 이상적입니다.
힙은 임의로 큰 할당(리스트용)과 8바이트만큼 작은 할당(플로트용4)을 모두 처리할 수 있어야 합니다. 할당은 적당히 빨라야 하지만, 힙이 작으므로 힙 전체를 걷는 것은 충분히 허용됩니다.
고정 크기 힙을 관리할 것이므로, 운영체제에 mmap() 시스템 콜로 그 크기의 연속 블록을 처음부터 달라고 하면 됩니다. Alkyne 포인터는 이 거대한 할당 내부의 32비트 오프셋일 뿐이며, 힙의 베이스 주소를 더하고 빼는 것으로 실제 CPU 포인터로 변환할 수 있습니다.
4GB Heap
+-------------------------------------------------+
| x |
+-------------------------------------------------+
^ ^
base base + ptr_to_x
Plaintext
운영체제가 실제로 4GB 메모리를 예약해두지는 않습니다. 시스템 페이지(4KB)를 한 번에 하나씩만 할당합니다. 힙의 특정 페이지에 처음으로 읽기/쓰기를 하면, 그때서야 OS가 물리 RAM을 찾아 매핑합니다5.
이후로는 이 고정 크기 힙을 다루며, 어디서 왔는지는 깊이 따지지 않겠습니다. 우리의 목적을 위해 이건 사실상 Box<[u8]>와 동일하지만, 운영체제에서 얻은 메모리라는 점을 명확히 하려고 Heap<[u8]>라고 부르겠습니다(명확히 하자면, 이 글의 논의는 거대한 Box<[u8]>에도 똑같이 적용됩니다).
Alkyne 언어는 스레드를 지원하지 않으므로 동시성을 배제할 수 있습니다. 이는 해결해야 할 문제를 크게 줄여 줍니다. 최신 할당기와 가비지 컬렉터 다수는 본질적으로 격렬한 동시성을 띠며, 불행히도 한 편의 글로 다루기엔 너무 고급 주제입니다. 아래에 더 화려한 GC에 대한 링크를 남깁니다.
가비지 컬렉터를 만들려면 먼저 할당기가 필요합니다. 시스템 힙을 페이지 소스로 “그냥”6 쓸 수도 있겠지만, 대부분의 가비지 컬렉터는 할당기와 공모합니다. 서로 유사한 자료구조를 쓰고 싶어 하기 때문입니다. 따라서 GC를 만든다면 할당기도 함께 만드는 것이 낫습니다.
할당기, 즉 “메모리 힙”(최소 힙으로 불리는 전혀 다른, 그러나 정말 사악한 자료구조와 혼동하지 마세요)은 다양한 크기의 할당 요청을 처리합니다. 이는 관리되는 힙에서 런타임까지 알 수 없는 생애를 갖는 고유한 공간 임대이며, _객체_라고도 부릅니다. 힙은 범용 오브젝트 풀로 볼 수도 있습니다.
힙의 가장 일반적인 API는 다음과 같습니다:
trait Allocator {
// 이 할당기가 관리하는 *유일한 포인터*를 반환합니다.
// 요청한 크기만큼, 그리고 원하는 정렬에 맞는 메모리를
// 가리키도록 합니다.
//
// 실패 시 null을 반환합니다.
unsafe fn alloc(&mut self, size: usize, align: usize) -> *mut u8;
// `Alloc`이 반환한 포인터를 해제합니다. 최대 한 번만 호출해야 합니다.
unsafe fn free(&mut self, ptr: *mut u8);
}
Rust
원래 예시는 C++로 작성했는데, 접근성이 더 낫다고 느끼기도 했습니다(ㅋㅋ). 하지만 Alkyne 자체가 Rust로 쓰였으니, 이야기 흐름에 더 잘 맞도록 Rust로 바꾸었습니다.
이건 “malloc” 스타일 API이며, 사실 꽤 결함이 있습니다. 이상적으로는 Rust의 Allocator처럼 크기 및 정렬을 할당과 해제 함수 모두에 제공하는 방식이 낫습니다.
불행히도7, 이는 정렬을 설명해야 함을 의미합니다.
“정렬(alignment)”은 포인터의 다소 귀찮은 속성입니다. 포인터의 주소가 N(항상 2의 거듭제곱)으로 나누어떨어지면 N바이트 정렬이라고 합니다. 포인터가 가리키는 대상의 자연 정렬에 맞게 정렬되어 있으면 “잘 정렬됨”(혹은 그냥 “정렬됨”)이라 합니다. 정수의 경우 보통 크기와 동일하고, 구조체는 해당 구조체의 필드들 중 최대 정렬에 맞습니다.
포인터에 연산을 수행하려면 그것이 정렬되어 있어야 합니다8. 귀찮게도 이는 약간의 수학을 요구합니다. 구체적으로 다음 세 함수가 필요합니다:
/// `ptr`이 주어진 정렬에 맞는지 확인합니다.
fn is_aligned(ptr: Int, align: usize) -> bool {
ptr & (align - 1) == 0
}
/// `ptr`을 `align`의 배수로 내림 정렬합니다.
fn align_down(ptr: Int, align: usize) -> Int {
ptr & !(align - 1)
}
/// `ptr`을 `align`의 배수로 올림 정렬합니다.
fn align_up(ptr: Int, align: usize) -> Int {
// (이건 매번 찾아봅니다. >_>)
align_down(ptr + align - 1, align)
}
/// `ptr`을 정렬하려면 얼마나 더해야 하는지 계산합니다.
fn misalign(ptr: Int, align: usize) -> usize {
align_up(ptr, align) - ptr
}
Rust
(연습: 이 공식들을 증명해 보세요.)
이후 글에서는 이 세 함수를 원하는 정수 타입(원시 포인터 포함, 포인터는 provenance를 가진 특수한 정수일 뿐)이면 언제든 쓸 수 있다고 가정합니다.
또한 힙 전체를 담은 Heap<[u8]>는 무한히 정렬된 것으로 취급하겠습니다. 즉, 포인터로서 모든 의미 있는 정렬에 맞습니다(즉, 페이지 정렬, 항상 4KB). (일반적인 Box<[u8]>의 경우는 참이 아닙니다.)
메모리 할당은 사실 아주 쉽습니다. _아레나(arenas)_는 할당기 계보 중 가장 간결하고도 강력합니다. 그냥 메모리를 해제하지 않기 때문입니다.
즉, 할당은 지금까지 할당되지 않은 메모리가 어디까지인지 가리키는 커서를 증가시키는 것뿐입니다.
+-------------------------------------------------+
| Allocated | Free |
+-------------------------------------------------+
^
cursor
Plaintext
우리 할당기는 return ptr++;만큼이나 단순합니다.
코드로 구현하는 것도 간단합니다:
struct Arena {
heap: Heap<[u8]>,
cursor: usize,
}
impl Allocator for Arena {
unsafe fn alloc(&mut self, size: usize, align: usize) -> *mut u8 {
// 정렬된 포인터를 얻으려면 약간의 "정렬 패딩"을 태워야 합니다.
// 정렬은 이렇게 귀찮습니다.
let needed = size + misalign(self.heap.as_ptr(), align);
// 메모리가 남았는지 확인합니다.
if self.heap.len() - self.cursor < needed {
return ptr::null_mut();
}
// 커서를 전진시키고, 할당된 구간의 끝을 잘라 냅니다.
self.cursor += needed;
&mut self.heap[self.cursor - size] as *mut u8;
}
unsafe fn free(&mut self, ptr: *mut u8) {
// ayy lmao
}
}
Rust
아레나는 매우 단순하지만, 쓸모가 없는 건 아닙니다! “세션” 컨텍스트 동안 존재하는 데이터를 담기에 좋습니다. 예컨대 많은 계산을 하고 종료하는 소프트웨어(컴파일러), 혹은 클라이언트 요청을 처리하며 요청 동안만 살아 있는 데이터가 많은 소프트웨어(웹 서버) 등이 그렇습니다.
하지만 장기 실행 시스템에는 좋지 않습니다. 객체를 재활용하지 않으면 결국 힙이 고갈됩니다.
이걸 제대로 만들기는 의외로 어렵습니다[출처 필요]. 이것이 할당기의 “근본 정리”입니다:
할당기의 “근본 정리”
메모리를 나눠 주는 건 쉽다. 반복해서 나눠 주는 게 어렵다.
다행히 지난 50년간 우리는 이 문제를 대부분 풀어 왔습니다. 할당기 설계는 꽤 복잡해질 수 있습니다.
이제 다양한 요청을 처리할 수 있도록 할당기에 점차적으로 기능을 추가해 보겠습니다. 이를 위해 네 가지 흔한 할당기 기능을 구현합니다:
이 네 가지는 대부분의 현대 할당기에서 어떤 형태로든 등장합니다.
첫 번째로 해야 할 일은 최소 크기의 고정 크기 블록 단위로 다루는 것입니다. malloc()에 1바이트를 요청해도 대부분의 시스템에서는 아마 8바이트 정도를 줄 것입니다. 아무도 1바이트만 요청하지 않으니, 조용히 올려 잡아도 신경 쓰지 않습니다. (또한 Alkyne의 힙 객체 최소 크기는 어차피 8바이트입니다.)
블록은 편리합니다. 사용자 데이터 앞에 헤더를 두고 블록별 메타데이터를 저장할 수 있기 때문입니다:
#[repr(C)]
struct Block {
header: Header,
data: [u8; BLOCK_SIZE],
}
Rust
블록을 재사용할 수 있도록 최근에 해제된 블록의 캐시를 유지합니다. 가장 쉬운 방법은 스택을 쓰는 것입니다. 이제 힙은 바이트 배열이 아니라 Block들로 이루어져 있음을 주의하세요.
저장소를 할당할 때 먼저 스택을 확인합니다. 스택이 비어 있으면 아레나로 돌아가 커서를 증가시킵니다. 해제 시에는 블록을 스택에 푸시하여 다음 alloc() 호출에서 반환할 수 있게 합니다.
struct BlockCache {
heap: Heap<[Block]>,
cursor: usize,
free_stack: Vec<*mut Block>,
}
impl Allocator for BlockCache {
unsafe fn alloc(&mut self, size: usize, align: usize) -> *mut u8 {
// 요청 크기가 너무 크지 않은지 확인합니다. 정렬은 신경 쓸 필요 없습니다.
// 각 블록은 힙 자체처럼 무한히 정렬되었다고 보면 됩니다.
if size > BLOCK_SIZE {
return ptr::null_mut();
}
// 스택에서 블록을 꺼내 반환을 시도합니다.
if let Some(block) = self.free_stack.pop() {
return &mut *block.data as *mut u8;
}
// 아레나 모드로 폴백합니다.
if self.cursor == self.heap.len() {
return ptr::null_mut();
}
self.cursor += 1;
&mut self.heap[self.cursor].data as *mut u8
}
unsafe fn free(&mut self, ptr: *mut u8) {
// 포인터 뺄셈으로 블록의 시작을 찾습니다.
let block = ptr.sub(size_of::<Header>()) as *mut Block;
self.free_stack.push(block);
}
}
Rust
이 할당기는 문제가 있습니다. 시스템 할당기에 의존한다는 점입니다! Heap은 OS에서 직접 왔지만, Vec은 malloc()(또는 유사한 것)과 대화합니다. 또한 꽤 큰 오버헤드가 생깁니다. 해제될수록 벡터가 커져야 하므로, 크기 조정 중 free()에서 긴 정지가 발생할 수 있습니다.
중간자를 잘라내면 이런 오버헤드를 더 통제할 수 있습니다.
물론, “프리 스택”은 아무도 들어본 적이 없습니다. 모두 프리 리스트를 씁니다! 프리 리스트는 캐시 아이디어를 _침투형 연결 리스트(intrusive linked list)_로 구현한 것입니다.
연결 리스트는 이런 자료구조입니다:
enum Node<T> {
Nil,
Cons(Box<(T, Node<T>)>),
// ^~~ oops I allocated again
}
Rust
이 구조도 노드를 저장할 할당기가 필요하다는 같은 문제가 있습니다. 침투형 리스트는 요소에 노드를 _포함_시킴으로써 이를 피합니다. 앞서 비워 둔 Header가 그 완벽한 자리가 됩니다:
struct Header {
/// 이 블록이 소속된 리스트에서의 다음/이전 블록 포인터.
next: *mut Block,
prev: *mut Block,
}
Rust
특히 우리는 이중 연결 리스트를 원합니다. 이중 연결 리스트는 어떤 요소든 리스트를 걷지 않고 제거할 수 있다는 성질이 있습니다.
list.root
|
v
+-> Block--------------------------+
| | next | null | data data data |
| +------------------------------+
+-----/------+
/ |
v |
+-> Block--------------------------+
| | next | prev | data data data |
| +------------------------------+
+-----/------+
/ |
v |
+-> Block--------------------------+
| | next | prev | data data data |
| +------------------------------+
+-----/------+
/ |
v |
Block--------------------------+
| null | prev | data data data |
+------------------------------+
Plaintext
또한 블록 리스트의 루트 노드를 보관하는 List 컨테이너 타입을 도입해 컨테이너 같은 API를 제공합니다. 이 타입은 다음과 같습니다:
struct List {
/// 루트는 사실 희생(sacrificial) 블록입니다. 리스트 중간 블록을
/// unlink할 수 있도록 존재합니다. 리스트의 “첫” 요소에서 unlink()를
/// 호출할 때 자신을 대체할 선행자가 필요하기 때문입니다.
root: *mut Block,
}
impl List {
/// 블록을 리스트에 푸시합니다.
unsafe fn push(&mut self, block: *mut Block) {
let block = &mut *block;
let root = &mut *self.root;
if !root.header.next.is_null() {
let first = &mut *root.header.next;
block.header.next = first;
first.header.prev = block;
}
root.header.next = block;
block.header.prev = root;
}
/// 리스트의 첫 요소를 얻습니다(있다면).
unsafe fn first(&mut self) -> Option<&mut Block> {
let root = &mut *self.root;
root.header.next.as_mut()
}
}
Rust
또한 블록이 어떤 리스트에 속해 있는지, 그렇다면 그 리스트에서 제거하는 기능도 가능하게 해야 합니다.
impl Block {
/// 이 블록이 어떤 리스트의 일부인지 확인합니다.
fn is_linked(&self) -> bool {
// prev 링크만 항상 존재합니다. next는 리스트의 마지막 요소에서는
// null입니다. 희생 노드는 prev가 non-null이 되는 일이 없으며,
// unlink될 수 없습니다.
!self.header.prev.is_null()
}
/// 이 링크된 블록을 속한 리스트에서 제거합니다.
fn unlink(&mut self) {
assert!(self.is_linked());
if !self.header.next.is_null() {
let next = &mut *self.header.next;
next.header.prev = self.header.prev;
}
// 이게 희생 노드가 필요한 이유입니다.
let prev = &mut *self.header.prev;
prev.header.next = self.header.next;
self.header.prev = ptr::null_mut();
self.header.next = ptr::null_mut();
}
}
Rust
이 추상화를 사용해 BlockCache를 FreeList로 업그레이드할 수 있습니다. free_stack을 free_list로 이름만 바꾸고, 한 줄만 변경하면 됩니다:
- if let Some(block) = self.free_stack.pop() {
+ if let Some(block) = self.free_list.first() {
+ block.unlink();
return &mut *block.data as *mut u8;
}
Rust
캡슐화 만세!
이것은 아주 초기의 malloc() 설계로, K&R C 책에 묘사된 것과 유사합니다. 하지만 큰 맹점이 있습니다. 고정된 크기까지의 블록만 제공할 수 있다는 점입니다! 또한 꽤 낭비이기도 합니다. 모든 할당이 같은 크기의 블록으로 제공되기 때문입니다. 최대 요청 크기를 키울수록 alloc(8)은 더 낭비적이 됩니다.
다음 단계는 블록 분할/병합 체계를 사용하는 것입니다. 버디 시스템 같은 방식이 있습니다. Alkyne은 정확히 버디 시스템을 쓰지는 않지만 비슷한 것을 합니다.
Alkyne은 고정 크기 블록을 사용하지 않습니다. 많은 할당기처럼, 메타데이터를 유지하는 최소 단위로 “페이지”를 정의합니다. Alkyne은 페이지를 4KB로 정의하지만, 다른 선택도 가능합니다. TCMalloc은 8KB 페이지를 씁니다.
Alkyne에서는 페이지들이 모여 연속적이고 가변 크기의 _림(ream)_을 이룹니다(말장난입니다). 이 림이 블록을 대신합니다.
병합과 분할을 하면 림의 시작에 헤더를 두기 어려우므로, Alkyne은 모든 헤더를 거대한 배열 어딘가에 따로 둡니다. 각 페이지는 페이지 디스크립터, 또는 Pd라 불리는 고유의 “헤더”를 가집니다.
페이지 디스크립터 배열은 힙의 시작에 있고, 실제 페이지는 그 뒤를 잇습니다. 이 배열의 최대 크기를 계산할 수 있고, 이를 통해 배열의 끝 위치를 미리 구해둘 수 있습니다.
현재 각 Pd는 자신이 설명하는 4KB에 더해 32바이트입니다. 4GB를 32 + 4K로 나누면 약 400만 페이지(정확히 4,067,203)가 나옵니다. 다음 페이지 경계로 올림하면, 페이지는 Heap<[u8]> 베이스 주소 뒤 4KB 경계 기준 127,102번째에서 시작하고, 오프셋으로는 0x7c1f400 바이트입니다.
모두를 거대한 배열에 넣는 것은 매우 유용합니다. GC가 힙의 _모든 할당_을 쉽게 찾을 수 있기 때문입니다. Pd 배열만 순회하면 됩니다!
그래서, 우리의 힙은 다음과 같습니다:
+---------------------------------------+ <-- mmap(2)'d region base
| Pd | Pd | Pd | Pd | Pd | Pd | Pd | Pd | \
+---------------------------------------+ |--- Page Descriptors
| Pd | Pd | Pd | Pd | Pd | Pd | Pd | Pd | | for every page we can
+---------------------------------------+ | ever allocate.
: ... : |
+---------------------------------------+ |
| Pd | Pd | Pd | Pd | Pd | Pd | Pd | Pd | /
+---------------------------------------+ <-- Heap base address
| Page 0 | \ = region + 0x7c1f400
| | |
| | |--- 4K pages corresponding
+---------------------------------------+ | to the Pds above.
| Page 1 | | (not to scale)
| | |
| | |
+---------------------------------------+ |
: ... | |
+---------------------------------------+ |
| Page N | |
| | |
| | /
+---------------------------------------+
(not to scale by a factor of about 4)
Plaintext
각각의 작은 Pd는 대략 다음과 같습니다:
#[repr(C)]
struct Pd {
gc_bits: u64,
prev: Option<u32>,
next: Option<u32>,
len: u16,
class: SizeClass,
// More fields...
}
Rust
prev와 next는 프리 리스트에 쓰이는 침투형 연결 리스트 포인터이지만, 이제는 Pd 배열에 대한 인덱스입니다. 다른 필드들은 여기서와 다음 트로프에서 사용됩니다.
페이지 내부 포인터가 주어지면 페이지 경계로 align_down()하고(페이지 베이스), 힙 베이스 기준 페이지의 인덱스를 계산한 다음 Pd 배열을 인덱싱하여 해당 Pd를 얻을 수 있습니다. 이 과정은 역으로도 가능하므로, 포인터와 Pd 간 전환이 매우 쉽습니다.
여기서는 다루지 않겠지만, Alkyne은 실제로
Pd포인터를Heap에 대한 참조도 함께 담은 특수PdRef타입으로 감쌉니다. 덕분에is_linked(),unlink(),data()같은 함수를 직접 구현할 수 있습니다.구현은 대부분 보일러플레이트이므로 생략합니다.
하나의 거대한 프리 리스트가 모든 림을 담습니다. 림은 첫 페이지의 디스크립터를 사용해 모든 메타데이터를 추적합니다. 프리 리스트의 리스트 포인터도 여기에 있습니다. len 필드는 림에 추가로 몇 개의 페이지가 있는지도 추적합니다. gc_bits는 페이지가 사용 중이면 1, 아니면 0입니다.
연속된 N개의 페이지를 프리 림 리스트에서 할당하려면:
어떤 의미에서 각 림은 더 작은 림을 할당하는 아레나입니다. 그렇게 잘라낸 림은 본래 림으로 “해제”될 수 없습니다. 대신 림을 해제하려면 메인 프리 리스트에 그냥 되돌려 둡니다.
만약 프리 림이 바닥나면, 다시 아레나로 돌아가 큰 Pd 배열의 다음 초기화되지 않은 Pd를 초기화합니다.
struct ReamAlloc {
heap: Heap<[Page]>,
cursor: usize,
free_list: List,
}
/// 최대 크기의 Pd 배열 끝까지의 오프셋.
/// 미리 계산할 수 있습니다.
const PAGES_START: usize = ...;
impl Allocator for ReamAlloc {
unsafe fn alloc(&mut self, size: usize, align: usize) -> *mut u8 {
// 정렬은 신경 쓸 필요 없습니다. 페이지 경계에서만 할당합니다.
let page_count = align_up(size, 4096) / 4096;
// 충분히 큰 첫 페이지를 리스트에서 찾습니다.
// (`List`를 이터러블하게 만드는 건 쉬운 연습입니다.)
for pd in &mut self.list {
if pd.len < page_count - 1 {
continue
}
if pd.len == page_count - 1 {
// 분할할 필요가 없습니다.
pd.unlink();
return pd.data();
}
// 포인터 업데이트를 피하려고 *끝*을 잘라낼 수 있습니다.
let new_ream = pd.add(page_count);
new_ream.len = page_count - 1;
pd.len -= page_count;
return new_ream.data();
}
// 새로운 림을 할당합니다. 이것도 아레나의 더 많은 반복입니다.
}
unsafe fn free(&mut self, ptr: *mut u8) {
// 이 페이지 포인터에 해당하는 Pd를 찾습니다.
// 사용자가 잘못된 포인터를 주지 않는 한 항상 림의 첫 Pd입니다.
let pd = Pd::from_ptr(ptr);
self.free_list.push(pd);
}
}
Rust
여기엔 문제가 있습니다. 시간이 지남에 따라 림은 줄어들기만 하고 다시 커지지 않아, 결국 단일 페이지만 남게 됩니다.
이를 고치려면 림을 병합할 수 있어야 합니다(Alkyne에는 아직 미구현). 따라서:
// `reams()`는 `Pd` 배열을 `len`을 사용해 각 번마다 다음 림으로
// 건너뛰며 순회하는 이터레이터를 반환합니다.
for pd in self.reams() {
if pd.gc_bits != 0 { continue }
loop {
let next = pd.add(pd.len + 1);
if next.gc_bits != 0 { break }
next.unlink();
pd.len += next.len + 1;
}
}
Rust
두 번째 림의 Pd에는 아무 것도 할 필요가 없습니다. 첫 번째 림에 흡수되면서 무효화됩니다. 힙을 걷을 때는 어차피 림의 길이를 사용해 현재 무효인 Pd를 건너뛰어야 합니다.
병합 가능한 림을 찾는 방법은 두 가지입니다. 위처럼 힙 전체를 순회하거나, 림을 해제할 때 이전/다음 림이 병합 가능인지 확인합니다(이전 림을 찾으려면 림의 첫 및 마지막 Pd에 길이를 저장해야 함).
어떤 병합 전략을 쓰느냐는, 우리가 일반적인 malloc-유형 힙을 구현하느냐 아니면 가비지 컬렉터를 구현하느냐에 달려 있습니다. malloc의 경우 해제 시 병합이 더 낫지만, Alkyne의 GC에는 한 번에 병합하는 편이 더 맞습니다(곧 이유를 보게 됩니다).
_슬랩 할당기_는 단일 타입의 객체만을 할당하는 특수 할당기입니다. 커널에서 자주 쓰이는, 흔히 사용하는 객체 풀로 인기가 많습니다. 슬랩 할당기의 요점은, 모든 것이 같은 크기이므로 _분할/병합을 구현할 필요가 없다_는 것입니다. 위의 BlockCache는 사실 매우 원시적인 슬랩 할당기입니다.
우리의 Pd 배열도 일종의 슬랩 할당기와 비슷합니다. 가변 크기 블록과 섞는 대신, 서로 빈틈 없이 함께 배치되어 있고, 전체 페이지가 오로지 Pd들을 위해서만 할당됩니다.
Alkyne의 페이지 할당기는 4K보다 작은 페이지는 할당할 수 없으며, 더 작게 만들수록 Pd의 상대적 오버헤드가 커집니다. 관리 작업을 줄이기 위해, 작은 객체는 _사이즈 클래스_로 슬랩 할당합니다.
사이즈 클래스란 페이지보다 작은 객체에 대해 Alkyne이 할당하는 표준 크기입니다. 그 외 크기는 다음 사이즈 클래스로 올림됩니다. 같은 크기의 객체만을 담는 페이지를 통째로 할당하며, 이를 작은 객체 페이지 혹은 간단히 _슬랩_이라고 부릅니다. 사이즈 클래스는 Pd의 class 필드로 추적합니다.
각 사이즈 클래스는 그 크기의 부분 채워진 슬랩들에 대한 자체 프리 리스트를 가집니다. 슬랩에서는 gc_bits 필드가 페이지의 어떤 슬롯이 현재 사용 중인지 추적하는 비트셋이 되어, 작은 객체의 오버헤드를 객체당 한 비트 남짓으로 줄입니다!
아래 도표에서, 32비트 리틀엔디언 비트셋의 설정된 비트는 슬랩(축척 무시!)에서 고양이 좋아하는 사용자에 의해 세 글자 단어가 채워진 슬롯을 나타냅니다.
Pd--------------------------------------------+
| gc_bits: 0b01010011111010100110000010101011 |
+---------------------------------------------+
Page--------------------------------------------+
| cat | ink | | hat | | jug | | fig |
+-----------------------------------------------+
| | | | | | zip | net | |
+-----------------------------------------------+
| | aid | | yes | | war | cat | van |
+-----------------------------------------------+
| can | cat | | | rat | | urn | |
+-----------------------------------------------+
Plaintext
이제 객체 할당은 조금 복잡해졌지만, 작은 객체에 대해서는 정말 짧은 빠른 경로가 생겼습니다:
(!gc_bits).count_trailing_zeros()로 다음 가용 슬롯을 찾고, 그 비트를 설정합니다.
c. page_addr + slab_slot_size * slot을 반환합니다.작은 객체 할당은 매우 빠릅니다. 슬랩 프리 리스트가 비어 있지 않다면, 항상 gc_bits에서 바로 채울 수 있는 자리가 있기 때문입니다. 비트셋에서 빈자리 찾기는 (대부분의 하드웨어에서 not과 ctz 또는 동등 연산으로) 몇 개의 명령이면 됩니다.
Alkyne은 새 슬랩으로 바꿀 단일 자유 페이지를 빠르게 찾기 위해 단일 자유 페이지 전용 프리 리스트를 따로 유지합니다. 이는 큰 림에서 단일 페이지를 할당해야 하는 필요를 줄여 단편화를 제한합니다.
Alkyne의 사이즈 클래스는 8(가장 작은 객체)에서 2048까지의 2의 거듭제곱입니다. 8, 16, 32 클래스의 경우 페이지당 64개를 초과하는 슬롯이 생기므로, 페이지 자체에서 최대 56바이트를 써서 gc_bits를 확장합니다. 8바이트 페이지는 전체 512개 대신 505개 객체만 담을 수 있어, 오버헤드는 1%입니다.
이제 직접 해제는 까다로워졌습니다. 크기를 선험적으로 알 수 없기 때문입니다.
Pd를 얻습니다.class를 보고 사이즈 클래스를 찾고, 페이지 내 원래 포인터의 오프셋으로 슬롯 인덱스를 구합니다.gc_bits에서 그 슬롯의 인덱스를 클리어합니다.이 시점에서 페이지가 방금 부분 채워짐이 되었는지, 비었는지 알 수 있고, 올바른 프리 리스트로 옮기면 됩니다.
사이즈 클래스는 중요한 할당기 최적화입니다. TCMalloc은 이를 극한까지 끌어 올립니다. 이 상수들은 프로파일링 데이터를 바탕으로 한 미친 스크립트로 생성됩니다.
GC 부분으로 넘어가기 전에, 여기까지 배운 것을 정리해 보겠습니다.
멋진 점은 이러한 트릭 대부분이 상당히 독립적이라는 것입니다. 초기 초안에 피드백을 주며 Matt Kulukundis가 이 훌륭한 강연을 공유해 주었는데, 단순한 것들을 조합해 복잡한 할당기를 만드는 법을 설명하고, 우리가 다룬 많은 트로프를 함께 다룹니다. 할당기에 대한 이 관점은 제게 상당한 깨달음을 주었습니다.
좋은 할당기는 단 하나의 전략만 쓰지 않습니다. 여러 전략을 사용하고, 예상 워크로드에 따라 가장 적합한 것을 고릅니다. 예를 들어 Alkyne은 작은 객체를 많이 할당할 것으로 기대합니다. 슬랩 페이지는 원래 플로트 객체 전용이었지만, 모든 작은 객체를 슬랩 할당으로 만들면 코드가 훨씬 단순해졌습니다.
사이즈 클래스 자체도 깊은 주제입니다. TCMalloc은 Google의 플릿에서 수집한 GWP 원격 측정으로 수많은 튜닝 파라미터를 결정하며, 우스꽝스럽게 큰 사이즈 클래스 테이블도 포함합니다.
이제 꽤 탄탄한 할당기가 생겼습니다. 이제, free 함수를 없애 봅시다.
가비지 컬렉션은 수동 메모리 관리와 매우 다릅니다. 해제를 일괄적으로 하며, 사용자로부터의 신호 없이 진행됩니다. free() 호출은 없습니다. 대신 사용자가 눈치채지 못할(즉, 사용자가 아직 도달 가능한 포인터를 몰래 해제해 use-after-free 버그를 일으키지 않을) free() 호출을 우리가 대신 어떤 것까지 할 수 있는지 알아내야 합니다. 가능한 빨리 해야 합니다.
Alkyne은 “트레이싱 GC”입니다. 트레이싱 GC는 알려진 도달 가능 객체의 루트 집합으로부터 “오브젝트 그래프”를 걷습니다. 객체 a가 주어지면, 객체 안의 데이터 중 GC 포인터임을 아는 것들을 _추적(trace)_합니다. 오브젝트 그래프에서, a로부터 GC 포인터 추적을 반복해 b에 도달할 수 있으면 b는 a로부터 도달 가능하다고 합니다.
Alkyne은 흔히 “마크-스윕”이라 불리는 두 단계 과정으로 가비지 컬렉션을 구현합니다.
_마킹(marking)_은 스택에 있는 값 같은 정의상 도달 가능한 값들의 집합으로부터 그래프 전체를 순회하고, 방문한 각 객체를 기록하는 것입니다. 그렇게 표시되지 않은 모든 객체는 확실히 도달 불가능하므로 회수할 수 있습니다. 이 회수를 _스윕(sweeping)_이라 합니다.
Alkyne은 이 절차의 순서를 약간 뒤집습니다. 먼저 “스윕”하고 그 다음 마크합니다. 즉 모든 값을 죽은 것으로 표시한 다음, 그래프를 걷으며 각 블록을 살아 있다고 표시합니다. 그런 다음 프리 리스트를 새 표시 상태에 맞게 재구축하여 블록을 다시 할당할 수 있게 합니다. 이를 “마크하고 스윕하지 않기(mark and don’t sweep)”라고 부르기도 하지만, 프리 리스트를 고치는 것 자체가 사실상 스윕 단계입니다.
마킹과 스윕! (위키백과, CC0 제공)
Alkyne은 “세상 정지(stop-the-world, STW)” GC입니다. 힙을 청소하는 동안 프로그램 실행을 모두 멈춰야 합니다. 이걸 하지 않는 GC도 만들 수 있습니다(현대 HotSpot GC는 세상을 멈추는 일이 드물다고 알고 있습니다). 하지만 매우 어렵습니다. 대부분의 GC는 어느 정도는 세상을 멈춥니다.
여기서 다루지 않은 한 가지는 언제 스윕할지입니다. 더 복잡하고 다소 손대중인 튜닝 주제로, Go가 하는 방식을 참고하도록 하겠습니다.
개별 객체를 섬세하게 해제하는 것은 꽤 어렵지만, 초토화는 매우 쉽습니다. 이를 위해 전체 Pd 배열을 걷고(유용하다고 했죠!), 모든 gc_bits를 날려버립니다. 그러면 모든 포인터가 댕글링처럼 보이는 망가진 힙 상태가 됩니다. 이것이 “아마겟돈”입니다.
이를 고치려면, 죽였으면 안 되는 객체를 “부활”시켜야 합니다(앗). 루트는 Alkyne 인터프리터 스택11에 있는 객체들입니다. 객체를 표시하기 위해, 그 포인터를 페이지-Pd 대응관계로 Pd로 바꾸고, “할당” 표시를 하여 살아 있음을 표시합니다.
그 다음, Alkyne 객체의 힙 레이아웃에 대한 우리의 지식12을 사용해 힙의 다른 객체로 가는 포인터를 찾습니다(예를 들어, 인터프리터는 자신이 리스트를 보고 있음을 알고 있으며, 내부의 리스트 원소들(대개 포인터)을 그냥 찾을 수 있습니다). 객체 안으로 추적했을 때 이미 할당 표시가 되어 있으면, 재귀하지 않습니다. 사이클에서 무한 재귀하는 일을 방지합니다.
여기서는 코드 예시를 주기가 조금 어렵습니다. GC의 “마크” 부분이 인터프리터 코드와 섞여 있어서, 보여줄 것이 많지 않기 때문입니다. :(
이 과정을 마치면, 도달 가능한 모든 객체는 다시 살아 있게 되고, 도달하지 못한 것은 그대로 죽은 상태로 남습니다.
(Alkyne은 현재 이 최적화를 하지 않지만, 정말 해야 합니다.)
모든 비트를 뒤집는 대신, 0과 1 중 어느 쪽이 “살아 있음”을 의미하는지에 대한 전역 _관례_를 뒤집습니다. 즉 전역 bool로 현재 어느 쪽이 살아 있는지를 나타내고, 스윕마다 이를 번갈아 가며 바꿉니다. 따라서 모든 살아 있는 객체를 죽이는 작업이 단일 연산이 됩니다.
이 최적화는 프리 리스트에 있는 객체의 할당 비트를 읽지 않고, 할당 시에만 “살아 있음” 값으로 덮어쓰는 경우에 동작합니다. 그러면 갑자기 모든 죽은 객체가 살아 있는 것으로 바뀌어도 눈치채지 못합니다. 단, 슬랩으로 할당된 작은 객체에는 적용되지 않습니다. 페이지가 부분적으로 할당/해제된 혼합 상태일 수 있기 때문입니다.
이 최적화는 페이지에 “살아 있는 객체가 하나라도 있는지”를 추적하는 두 번째 비트를 추가함으로써 여전히 적용할 수 있습니다. 동일한 관례를 사용합니다. 이렇게 하면 작은 객체의 할당 비트 초기화(클리어)를 페이지 방문 시점으로 지연할 수 있으며, 이때 페이지 전체를 살아 있음으로 표시합니다.
방문되지 않은(즉, 여전히 죽은 것으로 표시된) 페이지는 여느 때처럼 회수하면 됩니다. 할당 비트는 무시합니다.
이 시점에서 이제 포인터가 댕글링 상태는 아니지만, 새로 비게 된 페이지들이 속해야 할 프리 리스트에 들어가 있지 않을 수 있습니다. 이를 고치려면 모든 Pd를 순회하며, 가득 차지 않은 것들을 제자리에 넣으면 됩니다. 이것이 일종의, 그러나 완전하진 않은 스윕 단계입니다.
코드가 설명보다 간단합니다:
for pd in self.reams() {
if pd.gc_bits == 0 {
pd.unlink();
if pd.len == 0 {
unsafe { self.page_free_list.push(pd) }
} else {
unsafe { self.ream_free_list.push(pd) }
}
} else if pd.is_full() {
// GC가 부분 채워진 리스트를 가득 채울 수는 없으니,
// 옮길 필요가 없습니다.
} else {
// 비어 있지 않고, 가득 차지도 않은 리스트는 림일 수 없습니다.
debug_assert!(pd.class != SizeClass::Ream);
pd.unlink();
unsafe {
self.slab_free_lists[pd.class].push(pd)
}
}
}
Rust
물론, 이는 마킹 중에 부분적으로 비거나 비게 된 페이지뿐만 아니라 다른 페이지도 재배치할 수 있습니다. “즉시 아포칼립스” 최적화를 사용하더라도, 이 단계는 여전히 모든 Pd를 점검하고 프리 리스트를 수정해야 합니다.
그러나 이는 전적으로 별도의 단계입니다. 이전 마크 단계에서 살아남지 못한 페이지를 찾는 것만 합니다. 즉, 사용자 코드를 두 단계 사이에 실행할 수 있어 레이턴시를 줄입니다. 만약 힙 전체를 스윕하는 비용이 매우 크다면, 마크 단계보다 덜 자주 실행할 수도 있습니다13.
이 단계는 림 병합을 하기에 아주 좋은 기회이기도 합니다. 어차피 모든 페이지를 점검하니까요. 이것이 병합 전략이 일반 malloc()/free() 할당기가 아닌 GC의 할당기가 되려는 목적에 따라 달라지는 이유입니다.
…이게 전부입니다! 이것이 가비지 컬렉션입니다. 할당기에서 블록의 배치를 완전히 소유하는 설정 덕분에, 힙의 객체를 추적하는 데 필요한 메모리를 크게 줄이면서도 마크/스윕 단계를 간결하게 유지할 수 있습니다. 가비지 컬렉터는 다른 자료구조와 마찬가지입니다. 실제 연산을 빠르게 하기 위해, 불변식에 많은 복잡성을 밀어 넣는 것이죠.
Alkyne의 GC는 제가 너무 머리 싸매고 싶지 않아서(물론 결과적으로는 많이 했지만 ㅋㅋ) 매우 단순하게 설계되었습니다. GC 레이아웃은 수개월 동안 제 머릿속을 맴돌던 완전히 다른 이야기이며, 여기에 설명되어 있습니다. 그 선택들이 GC 자체의 설계에도 영향을 주었습니다.
아직 최적화할 것이 많지만, 정말 단순하면서도 현실적인 GC 설계이고, 꽤 만족스럽습니다!
Alkyne은 파이널라이저도 제공하지 않습니다. 파이널라이저는 GC판 소멸자입니다. GC가 객체를 죽었다고 선언한 뒤 호출됩니다. 파이널라이저는 그 본성상 GC를 크게 복잡하게 만듭니다. 호출 순서가 정해져 있지 않고, 깨진 GC 상태를 관찰할 수 있으며, (멀티스레드 GC에서 GC 일시정지 중에 실행되도록 구현했다면) 전체 프로그램을 멈출 수도 있습니다. 아니면, 인자로 좀비를 받아 탈출할 수 없게 만들거나, 더 나쁘게는 탈출하면 반드시 부활시켜야 할 수도 있습니다!
파이널라이저가 서로 의존하면, 아예 실행할 수 없습니다. ARC 사이클을 끊을 수 없는 것과 같은 이유입니다. ARC의 이 약점은 전지적 GC의 주요 장점 중 하나입니다.
Java의 Object.finalize() 문서는 거짓말, 새빨간 거짓말, 유령 이야기로 이뤄진 장벽 같은 텍스트입니다.
저는 (이 글을 쓰기 전주에) Go에도 파이널라이저가 있고, 비슷하게 저주받았다는 것을 알았습니다. Go는 Java보다는 좀 더 점잖게 동작합니다(파이널라이저가 값 단위이고, 파이널라이저가 달린 객체는 무조건 부활시켜 좀비 문제를 피함).
여기 제가 흥미롭고 읽을 가치가 있다고 생각하는 다른 할당기들을 소개합니다. 일부는 Alkyne 설계에 영감을 주었습니다.
TCMalloc은 Google의 미친 스레드 캐싱 할당기입니다. 정말 빠르고 멋집니다. 제가 Google에서 일하므로 편향이 있을 수 있습니다. 하지만 라딕스 트리를 씁니다! 라딕스 트리는 멋져요!!!
Go는 가비지 컬렉터가 있으며, 잘 알려진 성능 특성을 갖지만 이동 같은 과격한 최적화를 하지 않고, 세상 정지형 점증적 GC입니다.
Oilpan은 크로니움 렌더러의 GC(DOM 엘리먼트용)입니다. 사실 C++ 위에 접붙여졌고, 그 결과 GC의 미묘함을 반영하는 아주 복잡한 API를 갖고 있습니다.
libboehm은 Hans Boehm이 작성한 또 다른 C/C++ GC입니다. Boehm은 동시성 분야 세계 정상급 전문가 중 한 명입니다.
Orinoco는 JavaScript 힙을 위한 V8의 GC(즉, 크로니움의 또 다른 GC)입니다. 이는 세대별(generational) 또는 _이동(moving) GC_로, 포인터를 업데이트하며 사물을 옮겨가며 시간이 지남에 따라 힙을 디프래그할 수 있습니다. 또한 단명 객체 전용 서브-GC도 별도로 있습니다.
Mesh는 mmap(2)의 영리한 사용을 통해 콤팩트화(compacting)를 수행할 수 있는 비-GC 할당기입니다.
upb_Arena는 프리 리스트를 사용해 아레나를 서로 융합(fuse)할 수 있게 하는 아레나 할당기입니다. μpb Protobuf 런타임의 일부입니다.
다시 말해, 구문 트리를 따라 재귀를 사용하며, 프로그램을 바이트코드로 컴파일하는 더 효율적인 접근 대신 이를 택합니다.↩
자동 참조 카운팅(Automatic Reference Counting)은 모든 힙 할당에 현재 자신을 가리키는 포인터 수를 담는 카운터를 두는 자동 메모리 관리 기법입니다. 포인터가 스코프를 벗어나면 카운터를 감소시키고, 0이 되면 메모리를 해제합니다.
Python과 Swift는 핵심 메모리 관리 전략으로 이를 사용하며, C++과 Rust에서는 각각 std::shared_ptr<T>와 Arc<T> 타입을 통해 제공합니다.↩
약간 곁길로 새지만, Alkyne은 “NaN 박싱”을 하지 않습니다. 이는 Spidermonkey 같은 일부 JavaScript 런타임에서 쓰는 기법으로, 동적 타입 값을 일반 플로트 또는 64비트 IEEE 754 시그널링 NaN의 가수부에 숨긴 포인터로 표현합니다.
Alkyne은 대신 V8의 Smi 포인터 압축 같은 것을 사용하므로, 힙 값은 8바이트가 아니라 4바이트입니다. 스택(완전히 다른 표현을 사용)을 제외한 비-Smi 값은 리스트나 객체의 원소로만 존재할 수 있습니다. Alkyne의 슬랩 할당기 설계(아래 설명)는 모든 플로트가 각자 작은 할당에 존재함으로써 생기는 오버헤드를 최소화하는 데 주력합니다.↩
운영체제 할당기는 가상 메모리 매핑을 다뤄야 하므로 조금 더 까다로울 수 있지만, 그건 다른 때의 주제입니다.↩
예상하셨겠지만, 이 겁표시는 중요한 의미를 담고 있습니다.↩
초안에서 이 부분을 빼보려 했지만 실패했습니다. 정렬을 신경 쓰지 않아도 된다면 얼마나 많은 것이 단순해질지…↩
네네, 대부분의 아키텍처가 비정렬 로드/스토어를 견딜 수 있지만, 컴파일러는 그렇지 않다고 생각하길 좋아합니다.↩
Boutique는 프랑스어로 provenance라는 뜻입니다.↩
현재 Alkyne의 최대 림 크기는 꽤 작습니다. 더 나은 접근은 힙 전체를 시작 시 하나의 거대한 림으로 취급하고, 이를 프리 리스트의 맨 아래에 두는 것입니다.↩
GC 용어로 흔히 “스택 루트(stack roots)”라고 부릅니다.↩
인터프리터는 그냥 이걸 알고 GC에 적절히 지시할 수 있습니다.
어떤 트레이싱 GC에서도, 컴파일러나 인터프리터는 타입의 레이아웃을 잘 이해하고 있어 각 타입에 맞는 적절한 트레이싱 코드를 생성해야 합니다.
이 때문에 GC를 비-GC 언어에 접붙이는 것이 사소하지 않습니다. 하지만 사람들이 실제로 해오긴 했습니다. libboehm과 Oilpan은 이것이 어떻게 가능한지 보여주는 좋은(때로는 논쟁적인) 예입니다.↩