Rust의 GC를 직접 구현해보자

서론

Rust는 GC가 없는 언어입니다. 하지만 지난 글에서 살펴보았듯이 Rust에서도 GC가 필요한 경우가 있습니다. 그래서 이번 글에서는 Rust에서 GC를 직접 구현해보려고 합니다.

GC 구조 설계

Rust는 ownership 시스템으로 인해 GC를 구현하는 것이 까다롭습니다. C/C++ 등의 언어에서는 단순히 포인터를 사용하면 되지만 Rust에서는 포인터를 사용할 때마다 ownership을 고려해야 합니다. 물론 unsafe를 사용하면 ownership을 고려하지 않고도 포인터를 사용할 수 있지만, 이번 글에서는 unsafe를 최대한 사용하지 않고 GC를 구현해보려고 합니다.

Rust에서 GC를 구현하기 위해서는 다음과 같은 구조가 필요합니다.

그럼 각 부분을 어떻게 구현할지 살펴보겠습니다.

먼저, allocated memory는 GcInner라는 구조체를 통해 관리를 해줄 수 있습니다.

struct GcInner<T: ?Sized + 'static> {
    mark: bool,
    count: usize,
    value: T,
}

가장 간단한 Mark & Sweep 알고리즘을 이용해 GC를 구현할 것이기 때문에, mark 필드를 통해 mark 여부를 표시하고, count 필드를 통해 reference count를 관리합니다. count 필드는 현재 몇 개의 reference가 자신을 가리키고 있는지 저장하여 이 노드가 루트에 존재하는지 여부를 나타냅니다. 그래서 count가 0이 되면 그 노드는 루트가 아니게 됩니다. ?Sized + 'static인 이유는 잠시 뒤에 알아봅시다.

그럼 이러한 GcInner를 GlobalGc를 통해서 관리해보겠습니다.

struct GlobalGc {
    objects: Vec<NonNull<GcInner<dyn Trace>>>,
    color: bool,
}

objects는 GcInner를 저장하는 벡터입니다. NonNull는 Null이 아닌 포인터를 나타내는 구조체입니다. GcInner를 가리키는 포인터가 됩니다. 그리고 우리는 다양한 타입을 가지고 있는 노드를 저장해야 하기 때문에 GcInner<dyn Trace>로 저장합니다. dyn Trace는 내부 타입이 Trace 트레이트를 구현하고 있음을 나타냅니다. 또한 dyn Trace는 ?Sized이기 때문에 GcInner의 value 필드가 ?Sized이어야 합니다. color는 mark 여부를 표시하기 위한 필드입니다. 현재 color에 맞춰 mark를 표시하고, mark가 끝나면 color를 반전시킵니다.

그런데 GlobalGc는 전역 변수로 들어가야 합니다. 그래야 코드의 어디서든 GC를 사용할 수 있기 때문입니다. 하지만 Rust에서는 전역 변수를 사용할 수 없습니다. 정확히는 전역 변수를 사용할 수 없는 것이 아니라, 전역 변수를 사용하기 위해서는 unsafe를 사용해야 합니다. 그래서 이를 이미 구현해놓은 thread_local을 사용하겠습니다.

thread_local! {
    static LOCAL_GC: RefCell<GlobalGc> = RefCell::new(GlobalGc {
        objects: Vec::new(),
        color: false,
    });
}

이제 다음과 같이 코드를 작성하면 전역 변수처럼 사용할 수 있습니다.

LOCAL_GC.with(|gc| {
    // ...
});

이렇게 전역변수처럼 사용할 수 있으니 GcInner의 value 필드는 'static이 되어야 합니다. 이제, 앞서 나온 Trace trait를 살펴보겠습니다.

pub trait Trace {
    fn trace(&self, ctx: &GcCtx);
}

Trace는 trace 메서드를 가지고 있습니다. Garbage Collector는 이 메서드를 통해 노드의 reference를 탐색합니다. 사용자가 정의한 구조체에는 어떻게 Gc 노드가 정의되어 있을지 모르기 때문에 사용자가 직접 trace 메서드를 구현해야 합니다. 이를 자동으로 구현해주는 derive 매크로를 만들 수도 있지만, 이번 글에서는 생략하겠습니다. 궁금하신 분들은 이 글을 참고해주세요.

GcCtx는 GC가 노드의 reference를 탐색할 때 사용하는 구조체입니다.

struct GcCtx {
    color: bool,
}

GcCtx는 GlobalGc의 color 필드와 동일한 역할을 합니다. GcCtx는 순회하면서 GcInner의 mark 필드를 color로 설정합니다. 그래서 우리는 순회를 하는 함수가 필요합니다.

impl GcCtx {
    pub fn mark<T: Trace + 'static>(&self, object: &Gc<T>) {
        let mut inner = object.inner.get();
        unsafe {
            if inner.as_ref().mark == self.color {
                return;
            }
            inner.as_mut().mark = self.color;
            inner.as_ref().value.trace(self);
        }
    }
}

mark 함수는 Gc 노드를 순회하면서 GcInner의 mark 필드를 color로 설정합니다.

이제 외부 API로 나오는 Gc 구조체를 살펴보겠습니다.

pub struct Gc<T: 'static> {
    inner: Cell<NonNull<GcInner<T>>>,
    root: Cell<bool>,
    marker: PhantomData<Rc<T>>,
}

Gc는 GcInner를 가리키는 포인터를 저장하는 inner 필드와, 루트 노드인지 여부를 저장하는 root 필드를 가지고 있습니다. 또한 marker는 컴파일러에게 이 노드가 T 타입의 reference를 가지고 있음을 알려줍니다.

그럼 이제 Gc를 생성하는 함수를 살펴보겠습니다.

impl<T: Trace> Gc<T> {
    pub fn new(value: T) -> Gc<T> {
        LOCAL_GC.with(|gc| {
            let mut gc = gc.borrow_mut();
            let inner = NonNull::from(Box::leak(Box::new(GcInner::new(value, gc.color))));
            gc.push(inner);
            Gc {
                inner: Cell::new(inner),
                root: Cell::new(true),
                marker: PhantomData,
            }
        })
    }
}

Gc는 GcInner를 생성하고, GcInner를 push 함수를 통해 GlobalGc에 추가합니다. Box는 Drop 트레이트를 구현하고 있기 때문에 Box가 스코프를 벗어나면 Drop이 호출되지만 우리는 이것을 막기 위해 Box::leak를 사용합니다. Box::leak는 Box를 &'static mut T로 변환합니다.

이제 세부적인 구현은 생략하고, 마지막으로 실제로 GC를 수행하는 collect 함수를 살펴보겠습니다.

impl GlobalGc {
    fn collect(&mut self) {
        self.color = !self.color;
        let ctx = GcCtx::new(self.color);

        for object in &mut self.objects {
            unsafe {
                if object.as_ref().count > 0 {
                    object.as_mut().mark = self.color;
                    object.as_ref().value.trace(&ctx);
                }
            }
        }

        let mut i = 0;
        while i < self.objects.len() {
            let object = self.objects[i];
            unsafe {
                if object.as_ref().count == 0 && object.as_ref().mark != self.color {
                    let t = self.objects.swap_remove(i);
                    drop(Box::from_raw(t.as_ptr()));
                } else {
                    i += 1;
                }
            }
        }
    }
}

collect 함수는 GcCtx를 생성하고, GcCtx를 통해 Gc 노드를 순회합니다. 알고리즘대로 Gc 노드를 순회하면서 mark 필드를 color로 설정합니다. 그리고 count가 0이고 mark가 color와 다른 노드는 swap_remove를 통해 제거합니다.

이제 이를 통해 GC를 수행하는 코드를 작성해보겠습니다.

#[derive(Clone)]
struct Node {
    id: usize,
    next: RefCell<Option<Gc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("drop {}", self.id);
    }
}

impl Trace for Node {
    fn trace(&self, ctx: &GcCtx) {
        if let Some(next) = self.next.borrow().as_ref() {
            ctx.mark(next)
        }
    }
}

fn main() {
    {
        // foo1 -> foo2 -> foo1
        let foo1 = Gc::new(Node {
            id: 0,
            next: RefCell::new(None),
        });
        let foo1_clone = foo1.clone();
        foo1_clone.unset_root();
        let foo2 = Gc::new(Node {
            id: 1,
            next: RefCell::new(Some(foo1_clone)),
        });
        foo2.unset_root();
        *foo1.next.borrow_mut() = Some(foo2);

        let _ = Gc::new(Node {
            id: 2,
            next: RefCell::new(None),
        });

        collect();
    }
    println!("---");
    collect();
}

위 코드는 싸이클을 하나 만들고 GC를 수행하는 코드입니다. 실행 결과는 다음과 같습니다.

drop 2
---
drop 0
drop 1

--- 전에는 아직 싸이클이 루트에서 접근이 가능하기 때문에 drop 2만 실행됩니다. 그리고 싸이클이 루트에서 접근이 불가능해지는 시점이 되면, GC는 싸이클을 제거합니다.

결론

이렇게 우리는 Rust에서 GC를 구현하는 방법을 알아보았습니다. 위 구현은 단일 쓰레드에서만 돌아가는 매우 간단한 예시로 실제 GC는 훨씬 복잡합니다. 전체 코드는 여기에서 확인할 수 있습니다.

Rust의 GC를 직접 구현해보자

서론

GC 구조 설계

결론

Massively Parallel Computation

그래프 채색 개론