Rust용 가비지 컬렉터 dumpster가 공개됐다

언어가 Rust처럼 진화하는 현상을 ‘게의 집게발화’라고 한다면, Rust가 Java처럼 진화하는 건 뭐라고 불러야 할까? 카페인화일까?

이번 여름에는 시간을 보낼 여유가 꽤 있었다. 더운 여름날 실내에 앉아 메모리 안전을 표방하는 언어의 코어 덤프를 들여다보는 것보다 나은 일이 있을까? 다른 소프트웨어의 메모리 할당을 관리하는 가비지 컬렉터를 만들었다. 흥미로운 점은 가비지 컬렉션을 없애도록 설계됐고 이를 제대로 구현하는 데 필요한 기능도 많지 않은 Rust로, Rust를 위한 가비지 컬렉터를 만들었다는 것이다. 게다가 비교적 적은 타협만으로 작동하게 했으며, 그 과정을 아래에서 자세히 설명한다.

읽는 것보다 결과물이 궁금하다면 GitHub 저장소에서 소스 코드를 확인하거나 crates.io에서 내려받을 수 있다.

배경

Rust와 표준 라이브러리의 세부 사항을 잘 안다면 이 부분은 건너뛰어도 된다.

Rust 메모리 모델의 핵심은 아핀 타입과 빌림 검사기다. 값은 한 번에 하나의 식별자에만 바인딩될 수 있으며, 빌림(참조)은 참조 대상이 바인딩된 범위보다 오래 살아남을 수 없다.

다음 코드는 유효하지 않다.

let x = vec![1, 2, 3];
let y = x;
println!("{x:?}"); // compile error - x has already been moved

보통은 위 예에서 y = &x처럼 바인딩을 빌려 문제를 해결한다. 하지만 어떤 바인딩이 가장 오래 살아남을지 모르는 상황에서 힙에 할당된 값을 공유해야 할 때도 많다. 이 문제를 해결하는 방법이 가비지 컬렉션을 통한 공유 소유권이다.

Rust 표준 라이브러리에는 간단한 참조 카운팅 가비지 컬렉터 두 가지가 있다. 단일 스레드용 Rc와 원자적으로 카운트를 관리하는 Arc다. 두 유형은 각각 힙 할당에 참조 카운트를 유지한다. 대부분의 경우 잘 작동하지만 순환 참조는 처리하지 못한다. 내부 가변성과 결합하면 이 한계는 쉽게 드러난다.

use std::{cell::OnceCell, rc::Rc};
struct Foo(OnceCell<Rc<Foo>>);

let x = Rc::new(Foo(OnceCell::new()));
x.0.set(Rc::clone(&x));
// My foo has a reference to itself. It can never be freed!

그래서 가비지 컬렉터를 만드는 일이 실제 직업이 된다. 참조 카운터만으로 충분했다면 오라클에서 일하는 사람들 가운데 여럿은 일자리를 잃었을 것이다.

설계 방향

Rc, Arc와 비슷한 API를 가진 Gc 자료구조를 만들고 싶었다. 거의 모든 데이터 유형을 담을 수 있으면서도 순환 참조를 찾아 수집해야 한다.

활용할 수 있는 수단은 몇 가지다.

• Drop: Rust의 복사 불가능한 모든 데이터 유형은 Drop 트레이트를 구현해 값이 버려질 때마다 실행할 코드를 지정할 수 있다. Gc에 Drop을 구현하면 할당이 더는 접근할 수 없게 되는 시점을 추론할 정보를 얻을 수 있다.
• 트레이트: Gc에 담을 데이터가 반드시 구현해야 하는 트레이트를 만들 수 있다. 여기서는 이를 Collectable이라고 부르겠다. 단점도 크다. dumpster보다 상위에 있는 라이브러리는 이 트레이트를 구현할 수 없다. 하지만 필요한 대가다.

이 도구들만큼이나 만만치 않은 문제도 있다.

• 감지할 수 없는 이동. Rust에서 값이 이동할 때 값 자체가 그 사실을 감지할 방법은 없다. OnMove 같은 트레이트로 이동할 때마다 함수를 호출할 수 있다면 Gc가 다른 Gc 안으로 이동해 루트에서 끊기는 상황을 알아내 단순한 마크-스윕 컬렉터를 만들 수 있을 것이다. 하지만 그러려면 C++의 복사 생성자를 다시 발명해야 한다.
• 크기가 가변인 데이터. Gc가 ?Sized 유형도 저장할 수 있게 하기로 했다. 라이브러리 이용자에게 더 유연한 선택지를 주고(Gc<[T]> 같은 유형도 가능하다) 싶었기 때문이다.
• 유형 소거. 일반적인 Rust 프로그램에서 제네릭은 단형화를 통해 구현되며 런타임에는 유형 정보가 남지 않는다. 따라서 사전 맥락 없이 할당을 정리하기가 어렵다.

이 두 가지 도구만으로도 거의 모든 데이터 유형을 담을 수 있는 컬렉터를 만들 수 있다.

접근성 판단 알고리즘

스택을 실제로 훑지 않고 Gc에 접근할 수 있는지 확인해야 한다. 그래프 이론 용어를 빌려 몇 가지를 정의하겠다.

• 할당 그래프 𝐺=(𝑉,𝐸,𝑟)는 진입 차수가 0인 루트 노드 𝑟∈𝑉를 가진 방향 그래프다.
• 할당 그래프의 노드 𝑣는 𝑟에서 𝑣까지 경로가 있을 때, 그리고 그때에만 접근 가능하다고 한다.

각 노드를 하나의 할당이라고 생각하고, Gc를 통하지 않는 모든 데이터는 가상의 루트 할당에 속한다고 보자. 각 Gc는 두 할당을 연결하는 간선이다. 그래프 이론상의 의미에서 할당에 접근할 수 있다면 프로그램에서도 여전히 그 할당에 접근할 가능성이 있다. 접근할 수 없다면 안전하게 해제할 수 있다. 노드의 진입 차수는 해당 할당의 참조 카운트와 정확히 같다.

루트가 아닌 노드 𝑛의 접근 여부를 판별하는 절차는 다음과 같다.

• 𝑛의 모든 자손 집합 𝑊를 찾는다. 𝑊에 속한 노드를 정점으로 하고 𝑊 안의 간선을 보존하는 부분 그래프 𝐻를 만든다.
• 𝐻에서의 진입 차수가 𝐺에서의 진입 차수와 다른 노드의 집합 𝐴⊆𝑊를 찾는다.
• 𝐴의 각 노드와 그 자손을 접근 가능한 것으로 표시한다.
• 𝑛이 표시됐을 때, 그리고 그때에만 𝑛을 접근 가능한 것으로 판정한다.

의사 코드로 쓰면 다음과 같다.

def is_accessible(n):
 counts = {n: n.indegree()}
 for (_, m) in n.edges():
 dfs(m, counts)

 reachable = set()
 for (a, count) in counts:
 if count != 0:
 mark(a, reachable)

 return n in reachable

def dfs(n, counts):
 if n not in counts.keys():
 counts[n] = n.indegree()
 for (_, m) in n.edges():
 dfs(m, counts)

 counts[n] -= 1

def mark(a, reachable):
 if a not in reachable:
 reachable.add(a)
 for (_, b) in a.edges():
 mark(b, reachable)

is_accessible의 실행 시간은 𝑂(|𝑉|+|𝐸|)다.

참조 카운팅에 단계를 더하다

단일 스레드용 Gc는 Rc와 비슷하게 작동하되 몇 가지 세부 사항이 다르다. 먼저 Gc와 그 포인터가 가리키는 할당 GcBox를 정의한다.

pub struct Gc<T: ?Sized> {
 ptr: NonNull<GcBox<T>>
}

#[repr(C)]
struct GcBox<T: ?Sized> {
 ref_count: Cell<usize>,
 value: T
}

Gc의 Drop 동작에 연결하면 작동하게 만들 수 있다.

impl<T: ?Sized> Drop for Gc<T> {
 fn drop(&mut self) {
 let box_ref = unsafe { self.ptr.as_ref() };
 match box_ref.ref_count.get() {
 0 => (),
 n => {
 box_ref.ref_count.set(n - 1);
 if n == 1 || !is_accessible(box_ref) {
 box_ref.ref_count.set(0);
 unsafe {
 drop_in_place(addr_of_mut!(ptr.as_mut().value));
 dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));
 }
 }
 }
 }
 }
}

영리한 생각이라고 여겨 참조 카운트가 0인 상태를 할당을 정리하는 중이라는 표시로 사용했다. 이중 해제를 막기 위해서다.

하지만 문제가 있다. is_accessible은 어떻게 구현해야 할까?

트레이트를 활용한 방법

is_accessible 의사 코드는 노드에서 뻗어나가는 간선 집합에 접근해야 했다. 쉽지 않은 일이다. C로 작성한다면 힙 할당을 훑어 다른 할당을 가리키는 포인터처럼 보이는 데이터를 찾을 수 있다. Rust에서는 가비지 컬렉션 대상 유형에 작은 제약을 추가해 더 정확하게 처리할 수 있다.

가비지 컬렉터만으로도 충분하지 않으니 Java에서 방문자 패턴까지 가져오겠다. 가비지 컬렉션 대상 값이 모두 Collectable 트레이트를 구현하도록 하고, 그 트레이트가 방문자(Visitor)를 가비지 컬렉션 대상 필드 각각에 전달하게 한다.

pub struct Gc<T: Collectable + ?Sized> {
 // same as before ...
}

pub trait Collectable {
 fn accept<V: Visitor>(&self, visitor: &mut V);
}

pub trait Visitor {
 fn visit_gc<T: Collectable + ?Sized>(&mut self, gc: &Gc<T>);
}

예를 들어 배열은 각 요소의 accept를 호출하도록 구현할 수 있다.

impl<T: Collectable> Collectable for [T] {
 fn accept<V: Visitor>(&self, visitor: &mut V) {
 self.iter().for_each(|elem| elem.accept(visitor));
 }
}

이제 할당에 방문자를 적용해 각 할당에서 나가는 간선을 찾을 수 있다. dfs 단계용 방문자와 mark 단계용 방문자, 두 가지를 작성했다.

Collectable을 객체 안전하게 만들고 싶었지만 그러려면 Visitor도 객체 안전해야 한다. 그러면 모든 가비지 컬렉터를 Gc<dyn Collectable>로 변환할 수 있어야 하는데, 이는 나이틀리에서만 가능하다. 따라서 안정 버전용 크레이트를 만들 수 없게 된다.

묶음 해제

앞의 Drop 구현을 대략 살펴보면 is_accessible 호출은 존재하는 Gc의 총개수에 비례하는 선형 시간에 실행된다. 따라서 drop도 선형 시간이라고 생각할 수 있지만, drop_in_place가 다른 Gc의 drop을 다시 호출할 수 있어 정리 작업이 2차 시간으로 늘어날 수 있다. 이는 받아들일 수 없다. 첫 번째 is_accessible 호출에서 원래 할당을 기준으로 다른 할당의 접근 가능 여부를 이미 모두 판별했기 때문이다. 처음 해제할 할당에 접근할 수 없다면 그 할당이 참조하는 할당도 모두 접근할 수 없어야 한다.

정리할 수 없는 할당을 모두 찾은 뒤 한 번에 해제하면 표시 작업을 줄일 수 있다. 참조 그래프를 한 차례 더 순회해 파괴할 할당의 포인터와 각 할당의 drop 구현을 기록한다. 그런 다음 찾은 접근 불가능한 할당을 한꺼번에 해제한다.

마지막 문제가 남는다. 해제되는 값이 소유한 각 Gc도 대상 할당의 참조 카운트를 조작하려 할 수 있다. 그러면 정의되지 않은 동작이 생기거나, 그보다 더 나쁘게는 코드가 느려질 수 있다. 컴퓨터 과학의 모든 문제는 상태를 더 추가하거나 간접 참조를 더하면 해결할 수 있다. 이번에는 상태를 추가한다. COLLECTING이라는 스레드 로컬 값을 만든다.

묶음 해제 중에는 COLLECTING을 true로 설정한다. 그 상태에서 Gc의 drop을 호출하면 참조 카운트를 변경하지 않고 아무 작업도 하지 않는다. 아직 접근 가능한 할당으로 나가는 간선을 처리하기 위해 최종 정리 전 순회를 한 번 더 수행한다.

대략적인 코드는 다음과 같다.

thread_local! {
 static COLLECTING: Cell<bool> = Cell::new(false);
}

impl<T: Collectable + ?Sized> Drop for Gc<T> {
 fn drop(&mut self) {
 if COLLECTING.with(Cell::get) { return; }
 let box_ref = unsafe { self.ptr.as_ref() };
 match box_ref.ref_count.get() {
 0 => (),
 1 => {
 box_ref.ref_count.set(0);
 unsafe {
 drop_in_place(addr_of_mut!(ptr.as_mut().value));
 dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));
 }
 }
 n => {
 box_ref.ref_count.set(n - 1);
 unsafe { collect(self.ptr) };
 }
 }
 }
}

collect는 할당이 접근 가능한지 확인하고 필요하면 묶음 정리를 수행하는 함수다. 이를 구현하기 전에 문제가 하나 더 있다. 의사 코드에서는 각 할당을 counts의 키로 저장하고 이웃 할당에 접근해야 한다. 이를 위해 유형 소거를 조금 사용해야 한다. 자세한 설명은 생략하겠지만 두 가지가 필요하다.

• 할당 포인터를 해시 맵의 키로 저장한다.
• 작업에 필요한 유형 정보를 사용해 저장된 포인터를 복원한다.

Rust의 제약 때문에 두 작업은 서로 양립할 수 없다. 출처(provenance) 문제로 포인터의 원시 데이터를 비교하는 것은 정의되지 않은 동작이므로, 포인터의 유형 정보를 지운 뒤 해시 맵의 키로 쓸 수 없다. 그렇다고 할당의 첫 바이트를 가리키는 포인터만 사용할 수도 없다. 할당의 크기가 ?Sized일 수 있기 때문이다.

그래서 구현에는 유형 정보가 지워진 포인터가 두 종류 있다. 비교에 쓸 얇은 포인터와 모든 유형의 포인터를 복원할 수 있는 두꺼운 포인터다.

struct AllocationId(NonNull<Cell<usize>>); // used as a key in hash-maps
struct ErasedPtr([usize; 2]); // used as a reconstructible pointer to the allocation

그런 다음 dfs와 mark처럼 할당의 유형 정보를 알아야 하는 함수는 함수 포인터로 불투명하게 저장할 수 있다. 호출할 때 ErasedPtr을 유형 정보와 함께 “복원”한다.

다음은 dfs 구현에 활용하는 예다.

unsafe fn dfs<T: Collectable + ?Sized>(
 ptr: ErasedPtr,
 counts: &mut HashMap<AllocationId, usize>
) {
 struct DfsVisitor<'a> {
 counts: &'a mut HashMap<AllocationId, usize>,
 }

 impl Visitor for DfsVisitor<'_> {
 fn visit_gc<U>(&mut self, gc: &Gc<U>) {
 let id = AllocationId::new(gc.ptr);

 if counts.insert(id, unsafe { gc.ptr.as_ref().ref_count.get() }) {
 (**gc).accept(self);
 }

 *counts.get_mut(&id).unwrap() -= 1;
 }
 }
 // pretend that `specify` converts the pointer back into NonNull<T>
 let specified = ptr.specify::<T>();
 specified.as_ref().accept(&mut DfsVisitor { counts });
}

collect의 구현은 길고 정리 알고리즘의 최종 개정판도 아니므로 여기에 싣지 않겠다. 이 방법으로 묶음 해제를 구현할 수 있었고 drop() 호출은 선형 시간에 끝난다.

상각하기

참조 연산을 𝑂(1) 시간에 처리해야 한다고? 요즘 프로그래머들은 왜 이렇게 까다로운가?

다행히 가비지 컬렉션 작업을 평균적으로 𝑂(1) 시간에 끝내는 방법은 어렵지 않다. collect를 직접 호출하지 않고 접근할 수 없을 가능성이 있는 할당을 ‘더러운’ 할당 집합에 넣는다. 코드에서는 이 집합을 dumpster라고 부른다. 할당이 |𝐸|번 버려질 때마다 dumpster 전체를 순회해 𝑂(|𝐸|) 시간에 수집한다. 모든 할당에 걸쳐 상각하면 기술적으로 𝑂(1)이다. 배열 기반 리스트를 유용하게 만들고 2008년 금융 위기를 일으킨 것과 같은 계산상의 마술이다.

작업을 조금 줄이려면 할당에 접근할 때(역참조하거나 복제할 때 등) 그 할당이 접근 가능하다는 사실이 확인됐으므로 해당 할당을 같은 더러운 집합에서 빼면 된다.

동시 실행 지원

지금까지 설명한 가비지 컬렉터는 단일 스레드용이며 스레드 로컬 가비지 컬렉션 값만 저장할 수 있다. 쓸 만한 코드는 결국 동시 실행을 지원해야 한다고 들었으니 더 나은 방법이 필요하다. 다행히 한 번에 하나의 스레드만 수집한다는 전제 아래 이 알고리즘은 큰 노력 없이 동시 실행을 지원하도록 만들 수 있다.

하지만 수집 스레드가 하나뿐이어도 까다로운 동시성 문제가 생길 수 있다. 할당 𝑎와 𝑏, 가상의 루트 할당 𝑟이 있고, 𝑎는 𝑟에서만 접근 가능하며 𝑏는 𝑎에서만 접근 가능하다고 하자.

𝑎에서 시작하는 깊이 우선 탐색을 한다고 하자. 먼저 counts에 𝑎의 미처리 참조가 1개라고 기록한다. 이어서 𝑎의 자식인 𝑏를 살펴보려는 순간, 다른 악의적인 스레드가 𝑏를 수정해 𝑏에서 𝑎로 돌아오는 역참조를 추가한다.

깊이 우선 탐색은 𝑎로 돌아와 미처리 참조 수를 줄이고 𝑎와 𝑏로 들어오는 참조를 모두 확인했다고 판단할 수 있다. 그러면 가비지 컬렉터는 𝑎와 𝑏의 할당을 해제한다. 힙을 가리키는 유효하지 않은 참조가 남아 잠재적으로 해제 후 사용이나 다른 심각한 메모리 오류가 발생한다.

동시성 문제 해결

가장 간단한 해결책은 Gc와 관련된 모든 작업에서 전역 뮤텍스를 획득하도록 해 전체를 하나의 큰 잠금으로 감싸는 것이다. 그러면 동시성 버그는 막을 수 있지만 속도가 터무니없이 느려진다.

가능하면 전체 할당이 아니라 일부 할당만 상호 배제하면 좋겠다. 이 동시성 문제를 자세히 보면 다른 스레드가 부분 그래프 𝐻를 수정하는 동안 해당 그래프와 상호작용할 때만 잘못된 결과가 나온다. 해결책은 각 Gc에 특별한 숫자를 붙이는 것이다. 이를 수집 태그라고 부르겠다.

먼저 전역 원자 정수 COLLECTING_TAG를 추가한다.

static COLLECTING_TAG: AtomicUsize = AtomicUsize::new(0);

새 Gc를 만들거나 복제할 때마다 현재 COLLECTING_TAG 값을 태그로 붙인다.

// this new `Gc` type is intended to be `Sync`.

pub struct Gc<T: Collectable + Send + Sync + ?Sized> {
 ptr: NonNull<GcBox<T>>,
 tag: AtomicUsize,
}

impl <T: Collectable + Send + Sync + ?Sized> Gc<T> {
 pub fn new(x: T) -> Gc<T> {
 // (other bookkeeping hidden)

 Gc {
 ptr: /* initialization of GcBox<T> */,
 tag: COLLECTING_TAG.load(Ordering::Relaxed),
 }
 }
}

그다음 수집을 시작할 때 dfs를 호출하기 직전에 값을 증가시킨다.

fn collect() {
 COLLECTING_TAG.fetch_add(1, Ordering::Relaxed);
 // carry on with DFS and such
}

마지막으로 dfs 과정에서 Gc를 만날 때 태그를 확인한다. 태그가 현재 COLLECTING_TAG 값과 같다면 dfs가 시작된 뒤 생성된 Gc다. 이 경우 Gc를 발견한 위치는 접근 가능해야 하므로 해당 위치를 접근 가능한 것으로 표시할 수 있다. 간선을 두 번 방문하는 상황을 막기 위해(예상치 못한 동작이 일어날 수 있다) 방문한 간선의 태그도 COLLECTING_TAG 값으로 갱신한다.

문제가 있던 예로 돌아가 보자. 𝑎는 𝑏를 가리키고 𝑟은 𝑎를 가리킨다. 모든 Gc의 태그가 0이라고 하자. dfs가 시작되면 COLLECTING_TAG가 1로 증가한다. 따라서 악의적인 스레드가 새로 만든 참조에는 1이 붙는다.

이제 dfs가 𝑏에서 𝑎로 이어지는 간선을 방문할 때 태그가 1인 참조를 확인한다. 따라서 𝑏와 𝑎 모두 접근 가능하다고 판단한다. 실수로 너무 일찍 해제할 일이 없다.

참조를 옮기는 문제

포인터에 태그를 붙이는 것만으로 모든 동시성 버그를 막을 수 있기를 바라겠지만, 안타깝게도 충분하지 않다. 예를 들어 할당 𝑥에 자기 자신을 가리킬 수 있는 선택적 참조 두 개가 있다고 하자.

struct X {
 x1: Mutex<Option<Gc<X>>>,
 x2: Mutex<Option<Gc<X>>>,
}

예시를 시작할 때 𝑥 안에서 자기 자신을 가리키는 Gc는 하나뿐이고, Gc를 담을 수 있는 나머지 슬롯은 비어 있다. 𝑥는 루트 할당 𝑟에서 직접 접근할 수 있고, 기존 참조의 태그는 모두 0이다. 설명을 쉽게 하려고 첫 번째 슬롯을 나타내는 화살표는 실선, 두 번째 슬롯은 점선으로 표시하겠다.

이제 𝑥에서 dfs를 시작한다.

• COLLECTING_TAG를 1로 증가시킨다.
• dfs는 𝑥의 미처리 참조가 시작 시점에 2개라고 기록한다.
• dfs가 𝑥의 첫 번째 슬롯을 방문해 현재 있는 자기 참조에 태그를 붙인다. 𝑥의 미처리 참조는 1개가 된다.
• 악의적인 스레드가 끼어들어 먼저 𝑥의 첫 번째 슬롯에 있는 Gc를 𝑟로 옮긴다. 그런 다음 원래 𝑟과 𝑥를 연결하던 Gc를 𝑥의 두 번째 슬롯으로 옮긴다. fn do_evil(r_to_x: Gc<X>) { let z = std::mem::take(&mut *r_to_x.x1.lock().unwrap()); *z.x2.lock().unwrap() = r_to_x; }
• dfs가 계속 진행해 𝑥의 두 번째 슬롯을 방문한다. 𝑥를 가리키는 또 다른 참조를 보고 미처리 참조 수를 0으로 줄인다.
• dfs는 미처리 조상 참조가 있는 𝑥의 조상을 찾지 못했으므로 𝑥를 해제한다. 하지만 𝑥는 여전히 접근 가능하다.

이 문제는 꽤 오랫동안 해결하지 못했다. 다른 스레드가 할당을 가리키는 모든 Gc를 이리저리 옮겨 탐색을 속이는 일을 막을 수 없어 보였다. 다행히 방법이 있다. 모든 Gc에 태그를 붙이는 방법이 앞서 효과를 냈으므로 이번에는 모든 할당에 태그를 붙인다.

#[repr(C)]
struct GcBox<T: Collectable + Send + Sync + ?Sized> {
 ref_count: AtomicUsize,
 tag: AtomicUsize,
 value: T
}

Gc를 역참조할 때마다 할당의 태그를 현재 COLLECTING_TAG 값으로 갱신한다.

impl<T: Collectable + Send + Sync + ?Sized> std::ops::Deref for GcBox<T> {
 type Target = T;

 fn deref(&self) -> &Self::Target {
 let box_ref: &GcBox<T> = unsafe { self.ptr.as_ref() };
 box_ref.tag.store(COLLECTING_TAG.load(Ordering::Acquire), Ordering::Release);
 &box_ref.value
 }
}

dfs가 할당의 태그와 COLLECTING_TAG가 같은 것을 발견하면 해당 할당에 접근했다는 뜻이고, 따라서 그 할당은 접근 가능한 상태다. 위 예에서 악의적인 스레드가 참조를 뒤섞으려면 Gc를 역참조해야 한다. 그러면 탐색에 그 사실이 알려져 너무 이른 해제를 막는다.

실제로 이 방법으로 동시 실행 중에도 dfs가 할당을 접근 불가능한 것으로 잘못 표시하지 않는다는 점을 보일 수 있다. 글이 이미 상당히 길어졌으므로 증명은 개략적으로만 제시하겠다.

정리: dfs는 할당을 접근 불가능한 것으로 잘못 표시하지 않는다.

증명:

• dfs가 시작된 뒤 생성된 Gc를 만나면 참조 대상이 접근 가능하다는 사실을 알 수 있다.
• (1)에 따라 dfs가 할당 𝑎를 접근 불가능하다고 표시했다면, 𝑎를 가리키는 Gc 가운데 dfs 시작 전에 존재했던 것만 방문했을 것이다.
• (2)를 약하게 표현하면, dfs가 𝑎를 접근 불가능하다고 표시했다면 𝑎의 참조 카운트를 기록했을 때 존재하던 Gc만 방문했을 것이다.
• dfs는 Gc가 루트 할당 𝑟에서 다른 할당으로 이어지는 동안에는 해당 Gc를 방문하지 않는다.
• dfs가 어떤 할당을 접근 불가능하다고 표시하려면 참조 카운트를 기록한 시점에 그 할당을 가리키던 모든 Gc를 방문해야 한다.
• (4)와 (5)에 따르면 𝑎가 접근 불가능하다고 표시되려면, 𝑟과 𝑎를 연결하던 모든 Gc가 어느 시점에는 𝑟이 아닌 다른 노드와 𝑎를 연결하도록 옮겨졌어야 한다.
• (6)에 따라 dfs가 𝑎를 처음 방문한 때와 마지막 방문한 때 사이에 𝑟과 𝑎를 가리키는 Gc를 빌리는 수명 'x는 존재할 수 없다.
• dfs가 𝑎 안으로 마지막으로 이동한 Gc는 𝑟과 𝑎를 가리키는 Gc를 빌린 상태에서 이동했어야 한다. 이 빌림의 수명을 'y라고 하자.
• 마지막 이동 이후에도 'y가 지속되므로 dfs가 𝑎를 가리키는 모든 Gc를 방문한 뒤까지 임의로 연장할 수 있다.
• (7)에 따라 'y는 dfs가 𝑎를 처음 방문하기 전에는 존재할 수 없다. 그러므로 𝑎가 잘못 접근 불가능한 것으로 표시됐다면 'y 수명의 빌림을 만들기 위해 𝑎를 가리키는 Gc를 역참조했어야 한다.
• dfs가 𝑎를 가리키는 Gc를 마지막으로 방문하기 전에 역참조가 일어났다면, dfs는 𝑎의 태그가 바뀐 것을 확인했을 것이다. 따라서 할당이 접근 불가능한 것으로 잘못 표시됐다면 접근 가능한 것으로 표시됐어야 한다. 그러므로 dfs가 할당을 접근 불가능한 것으로 잘못 표시하는 일은 없다. 증명 끝.

이 증명은 다소 허술하지만 주의 깊은 독자가 세부 내용을 채울 수 있을 것이다. dfs가 할당을 접근 가능한 것으로 잘못 표시하지 않는다는 보완 증명은 독자에게 맡기겠다.

이 접근법의 정확성이 Rust의 빌림 검사 의미론에 전적으로 기대고 있다는 점도 흥미롭다. 전체 메커니즘이 Rust에 자연스럽게 어울리는 것 같다.

약한 참조가 중요하다

동시 실행에서 메모리 안전 문제를 일으킬 원인이 하나 더 있다. 전역 dumpster에 저장돼 있다는 이유로 할당이 해제될 때, 다른 스레드에서는 여전히 접근 가능할 수 있다. 다른 스레드의 메모리에서 그 할당을 참조하는 모든 항목을 없앴다고 보장할 수 없으니 문제가 해결되지 않은 것처럼 보인다.

하지만 상태를 더 추가하면 해결할 수 있다. Rc에서 아이디어를 빌려 널리 적용해 보겠다. 각 할당에 ‘약한’ 참조 카운트를 붙여 dumpster나 정리 스레드가 해당 할당을 참조하는 횟수를 기록한다. 기존 참조 카운트는 강한 참조 카운트라고 부르겠다.

#[repr(C)]
struct GcBox<T: Collectable + Send + Sync + ?Sized> {
 strong: AtomicUsize,
 weak: AtomicUsize,
 tag: AtomicUsize,
 value: T,
}

Gc의 마지막 강한 참조를 버릴 때는 약한 참조 카운트가 0이 아닌지 확인한다. 0이 아니라면 정리는 정리 스레드의 몫이다.

할당을 dumpster에서 꺼내 정리 절차를 실행하는 스레드가 버리려 할 때 약한 카운트를 줄인다. 강한 카운트와 약한 카운트가 모두 0인지 확인하고, 둘 다 0이면 그 스레드가 할당을 안전하게 파괴할 수 있다.

교착 상태

Gc<Mutex<()>>를 만들고 뮤텍스가 잠긴 상태에서 그 뮤텍스를 가리키는 Gc를 버린다고 하자.

let gc1 = Gc::new(Mutex::new(()));
let gc2 = gc1.clone();

let guard = gc1.lock()?;
drop(gc2); // suppose this triggers a cleanup
drop(guard);

참조 그래프를 순회하는 dfs 방문자는 뮤텍스를 방문하면서 잠금을 획득하려 할 것이다. 하지만 할당을 사용한 같은 스레드가 이미 그 뮤텍스의 가드를 보유하고 있으므로 심각한 교착 상태에 빠진다. 다행히 Mutex의 훌륭한 API 덕분에 뮤텍스 가드가 잡힌 할당은 여전히 접근 가능하다는 것을 안다. 따라서 잠금 획득에 실패하면 그 할당이 접근 가능하다는 즉각적인 증거로 삼을 수 있다.

이를 이용해 수집 대상 유형을 방문하는 작업이 실패할 수 있게 하고, 잠금 획득에 실패하면 방문도 실패하도록 하겠다.

pub trait Collectable {
 fn accept<V: Visitor>(&self, visitor: &mut V) -> Result<(), ()>;
}

pub trait Visitor {
 fn visit_gc<T: Collectable + ?Sized>(&mut self, gc: &Gc<T>) -> Result<(), ()>;
}

impl<T: Collectable + ?Sized> Collectable for Mutex<T> {
 fn accept<V: Visitor>(&self, visitor: &mut V) -> Result<(), ()> {
 // pretend poison errors don't exist
 self.try_lock().map_err(|_| ())?.accept(visitor);
 Ok(())
 }
}

여러 스레드가 나눠 쓰는 `dumpster`

여기까지 읽었다면 손으로 그린 그림을 감상해도 좋겠다.

이 가비지 컬렉터의 동시 성능을 떨어뜨리는 가장 큰 병목 가운데 하나는 Gc를 버릴 때마다 전역 dumpster에 접근하는 것이다. Mutex<HashMap>을 쓴다면 시스템의 병렬성이 거의 사라져 16코어 컴퓨터에 돈을 쓴 이유를 궁금해하게 될 것이다.

정상적인 사람이라면 동시성 해시 맵을 선택할 수 있다. Rust 구현이 여럿 있다. chashmap을 시도했지만 드물게 발생하는 패닉 버그 때문에 포기했다. 다음으로 dashmap을 시도했는데 잘 작동했지만 스레드 수가 늘수록 너무 느렸다.

핵심 문제는 자료구조를 동시에 갱신하면 느려진다는 것이다. 잘게 나눈 잠금을 사용하는 이른바 ‘동시성’ 자료구조도 항상 경합 오버헤드가 생긴다. 동시성으로 인한 속도 저하를 피하는 최선의 방법은 작업을 동시에 하지 않는 것이다. 각 스레드가 자체 dumpster를 갖게 하고, 정리할 할당을 모아 두는 전역 집합을 ‘쓰레기차’라고 부르면 해결할 수 있다. 다른 할당을 더러운 것으로 표시할 때 현재 스레드의 dumpster가 휴리스틱 기준으로 가득 찼는지 확인한다. 가득 찼다면 해당 스레드의 dumpster에 있는 할당을 쓰레기차로 옮긴다. 전체 절차의 의사 코드는 다음과 같다.

dumpster = set() # local to this thread
garbage_truck = mutex(set()) # global to all threads

def mark_dirty(allocation):
 dumpster.add(allocation)
 if is_full(dumpster):
 garbage_truck.lock()
 for trash_bag in dumpster:
 garbage_truck.add(trash_bag)
 garbage_truck.unlock()
 dumpster = set()

is_full이 충분히 드물게 true를 반환한다면 쓰레기차를 두고 생기는 경합은 거의 없다. 따라서 동시성 오버헤드가 크게 줄고 성능을 얻을 수 있다.

얼마나 빠를까?

간단히 말하면 이 가비지 컬렉터는 꽤 빠르게 작동한다.

최종적으로 두 가지 가비지 컬렉터 구현을 만들었다. 하나는 스레드 로컬이라 동시성 문제를 피하고, 다른 하나는 성능을 일부 희생하는 대신 동시 실행을 안전하게 지원하며 다양한 기능을 갖췄다. once_cell의 API를 참고해 전자는 크레이트의 unsync 모듈에, 후자는 sync 모듈에 뒀다.

비교를 위해 찾을 수 있는 가비지 컬렉터를 모았다. dumpster와 API가 비슷하고, crates.io에 게시됐으며, 실제로 작동하는 것만 골랐다.

dumpster와 비슷한 API가 없는 구현은 제외했다. 이들을 다루는 벤치마크 하네스를 만드는 일이 번거로웠기 때문이다. 충분히 꼼꼼하지 못했다고 생각한다면 직접 벤치마크해도 좋다. 순환 참조를 수집하지 않는 Rc와 Arc도 포함했다. 가비지 컬렉터의 최소 성능을 가늠할 만한 기준이기 때문이다.

조사 과정에서 bacon-rajan-cc는 자체적으로 수집을 시작하지 않는다는 사실도 확인했다. 공정한 비교를 위해 dumpster의 두 가비지 컬렉터 각각에 자동 수집을 시작하지 않는 버전도 추가했다. 이 버전에는 ‘manual’이라는 표시를 붙였다. 마지막으로 gcmodule은 극도로 많은 할당을 수집할 때 스택 오버플로가 발생하고 때때로 세그멘테이션 오류도 일으켜 벤치마크에서 제외했다.

벤치마크는 가능한 한 단순하게 했다. 많은 할당이 반복문에서 서로에 대한 참조를 무작위로 추가하고 제거하며, 새 할당을 만들고 기존 할당을 버리도록 했다. 무작위 오차를 고려해 각 가비지 컬렉터에서 100회씩, 100만 번의 작업을 실행했다. 각 작업은 참조 생성 또는 삭제다.

먼저 모든 가비지 컬렉터의 순수 단일 스레드 성능을 측정했다. 실행 시간의 빈도 분포를 바이올린 플롯으로 나타냈다.

이 플롯에서 알 수 있는 것은 shredder가 느리다는 점 정도다. 더 자세히 보기 위해 shredder를 목록에서 빼고 비교했다.

dumpster의 unsync 구현은 괜찮은 위치에 있다. 순환 참조를 감지하지 않는 할당기와 bacon-rajan-cc만 더 빠르다. bacon-rajan-cc는 오버헤드가 매우 적고 성능이 좋다.

동시 실행 버전의 가비지 컬렉터가 단일 스레드 버전보다 훨씬 느린 데에는 두 가지 주요 이유가 있다고 본다. 첫째, 할당을 스레드 로컬 dumpster에서 전역 쓰레기차로 옮기는 데 시간이 걸린다. 둘째, 동시 환경에서 dfs 작업은 동시성 버그를 막기 위해 보통 별도의 힙 할당 구조체에 현재 할당의 자식 집합을 기록해야 한다. 첫 번째 문제로 인한 손실은 줄일 수 있지만 두 번째 문제는 다루기 어렵다.

자동 수집을 사용할 때 동시 실행 버전이 훨씬 느린 이유는 테스트 하네스 때문일 수도 있다고 추측한다. 현재 테스트를 반복문에서 모두 실행한다. 따라서 단일 스레드 벤치마크가 멀티스레드 벤치마크 직후 실행되면서 멀티스레드 쪽의 쓰레기를 정리해야 할 수 있다.

이제 멀티스레드 벤치마크 결과를 보자.

비교할 수 있었던 다른 동시 실행 가비지 컬렉터는 shredder뿐이었는데, 결과를 보면 경쟁 상대가 되지 못한 듯하다.

dumpster는 스레드 수가 늘어날수록 기대만큼 매끄럽게 확장되지는 않는다. 그래도 스레드 수가 증가하면 성능이 실제로 좋아진다는 점은 다행이다. 다만 스레드 하나에서 둘로 늘어나는 구간은 예외다. Arc보다 겨우 3배 느린 것은 꽤 괜찮은 성과라고 생각한다. 이 프로젝트를 돈을 받고 한 것도 아니기 때문이다. 동시 상황의 고성능 컴퓨팅 전문가가 아니므로 더 최적화하려면 무작위 시도를 해 보고 나아지는지 확인하는 모험이 될 가능성이 크다. 이 접근법을 최적화할 아이디어가 있다면 알려 달라. 이메일 주소는 ‘About’ 페이지에 있다.

마무리

지난 몇 달 동안 처음부터 Rust용 가비지 컬렉터를 만들었다. 직접 고안한 새롭다고 할 만한 알고리즘을 구현해 단일 스레드와 멀티스레드 환경에서 작동하게 했고, 성능도 실제로 괜찮다는 점을 보였다.

크레이트 구현은 crates.io에 공개돼 누구나 내려받을 수 있다. 라이선스는 GNU GPLv3다.

게시물을 검토하고, 좋지 않은 질문에 답해 주고, 거의 두 달 동안 이어진 장황한 이야기를 들어 준 Wisha, Charlie, Shreyas에게 감사한다.

덧붙이는 이야기

앞의 이야기에는 넣기 어려웠지만 흥미로웠던 점을 몇 가지 덧붙인다.

좋았던 나쁜 아이디어들

이 글에서 본 최종적인 해결책은 처음 생각과 상당히 다르다. 특히 동시성 문제를 해결하려던 초기 아이디어는 거의 모두 실패했다. 간단히 되짚어 보면 다음과 같다.

• dfs를 실행하는 동안 모든 할당의 참조 카운트를 Mutex로 감싸고 잠근다.
• usize 전체를 더하는 대신 가장 낮은 비트에만 태그를 붙여 Gc의 공간을 절약한다.
• 모든 것을 동적 디스패치로 만들어 Java와 비슷한 객체를 구현한다.
• 각 스레드에서 할당을 직접 정리한다.
• 할당을 직접 버리는 대신 참조 카운트를 영리하게 줄인다.

나이틀리의 유용한 기능

Rc와 다른 포인터 유형은 Rust 컴파일러의 나이틀리 기능을 사용하면서 안정 버전 프로젝트에서도 쓸 수 있다는 점에서 어느 정도 ‘특별 대우’를 받는다. dumpster에는 그런 혜택이 없다.

모든 가비지 컬렉터에 CoerceUnsized를 조건 없이 구현하고 싶지만, 아직 안정 버전에서는 불가능하다.

마찬가지로 엄격한 출처(strict provenance)가 구현되기 전까지는 안정 버전 크레이트에서 두꺼운 포인터의 주소 부분을 조작할 방법이 없다. 따라서 하위 비트 태그를 활용해 공간을 최적화할 방법을 찾더라도 나이틀리 기능이 필요해 사용할 수 없다.

`Gc<dyn T>`를 만드는 다른 방법

Gc를 크기가 정해지지 않은 유형으로 강제 변환할 수 없어서 accept의 함수 시그니처상 Collectable을 객체 안전하게 만들 수 없다. 그러면 Visitor도 객체 안전해야 하고, visit 연산도 객체 안전해야 한다.

다른 접근법도 생각해 봤다. Visitor를 하나의 구체적인 유형으로 만들면 Collectable은 쉽게 객체 안전해진다. 대신 현재 방문자 구현 다섯 개를 같은 구조체에 저장해야 한다. 그러면 유형 안전성의 장점 상당 부분을 잃고 런타임 비용이 커진다. 그 방법은 그다지 마음에 들지 않는다.

Miri는 훌륭하다

cargo miri가 없었다면 이 프로젝트를 끝내지 못했을 것이다. 아직 모른다면 지금 내려받아 모든 Rust 프로젝트에서 실행해 보라. 안전하지 않은 코드를 디버깅하는 데 정말 훌륭하다. 다른 언어에도 쓸 수 있으면 좋겠다. C를 쓸 때 valgrind는 Miri를 대신하기에 부족하다.

테스트와 디버깅

초기에는 손으로 작성한 테스트가 몇 개뿐이었다. 처음 문제가 된 참조 그래프는 다음과 같았다.

여러 순환이 있는 단순 그래프를 테스트하고 나자 새로운 테스트를 만들기 어려워졌다. 그래서 벤치마크와 같은 방식으로 퍼징을 사용했다. 참조를 무작위로 생성한 다음 제대로 정리되는지 확인했다.

하지만 퍼징 테스트 결과를 디버깅하는 일은 정말 힘들었다. 문제의 원인을 찾는 과정이 끔찍해 작업을 편하게 해 줄 조잡한 도구를 만들었다. 결국 테스트 실행 중 특정 시점의 참조 그래프를 출력하고 시각화해 문제를 추측하기로 했다. 하지만 동시 실행 구현에서는 무언가를 출력하는 것만으로 프로그램의 실행 동작이 달라질 수 있다. 문제의 원인이 항상 분명한 것도 아니다. 수천 번의 작업이 끝난 뒤에야 발생하는 버그가 하나 있었는데, 그때의 참조 그래프는 다음과 같았다.

위 그래프는 벤치마크와 같은 방식으로 가비지 컬렉터를 퍼징해 만들었다.