Cabbage Collector - 직접 GC 구현해보기 (with Rust)

#Rust

한번 간단하게나마 GC 시스템을 구현해봤다.
구현 알고리즘은 순진하고 초기적인 형태의 Mark and Sweep다.

https://github.com/myyrakle/cabbage_collector/tree/v0.1.0

전제

GC도 제대로 만들려면 끝도 없기 때문에, 로직과 코드의 단순성을 위해 최소한의 부분만 구현해본다.
그래서

메모리 풀링과 컴팩션이 없고
싱글스레드 환경만 고려했으며
GC가 동시적으로 실행되지 않고
GC를 수동으로 트리거하며
부모-자식 간의 연결도 수동으로 한다.

내부 객체 구조 설계

먼저 실제 객체 단위를 정의해보겠다.

data_ptr는 동적할당된 포인터의 실제 주소 정수값이 들어갈 필드고, layout은 객체의 할당과 해제를 통제하기 위한 보조 값이다.
marked가 마크앤스윕 처리를 위한 마크 필드고, is_root는 root인 경우를 식별하기 위해 둔 상태값이다.
그리고 각 객체가 가진 자식 객체 참조를 관리하기 위해서 child_objects 필드를 추가했다. 저걸 통해서 쭉쭉 내려가면서 실제 참조 여부를 검증하려 한다.

객체의 할당 부분은 적당히 구현했다.

Box로 객체를 생성한 다음에 into_raw로 강제로 누수시켰다.
저래야 자동으로 할당이 해제되지 않고 raw 포인터로 leak돼서 내 마음대로 통제할 수 있다.

이 시점부터는 통제할 수 없는 폭주기관차가 되기 때문에, 잘 처리해야 한다.
의도적으로 여기에서는 raw 포인터를 주로 사용했다. 안전한 형태로도 구현하지 못할 것은 없지만, 오히려 코드가 더 복잡해지고, 성능 손실도 약간 존재할 수 있어서 배제했다.

할당 해제 부분은 특별한 부분은 없다.

지금은 없는데 추후에는 객체에 정의된 drop 함수도 호출할 수 있게 하려고 한다.
물론 이 시점에는 객체에 대한 타입 정보가 없어서 구현하기가 좀 애매하긴 하다만...
생각을 좀 해봐야 할 것 같다.

그리고, 객체의 전반적인 관리를 위한 객체 풀이 있어야 한다. 그러려면 전역변수는 거의 필수다.
전역변수의 남발은 Rust의 경영철학에는 잘 맞지 않는 부분이지만, 어쩔 수 없다.

실제 GC 탐색을 위한 root 목록 값이 있고, 그냥 전체 객체 목록을 관리하고 할당해제하기 위한 all_objects 필드도 따로 뒀다.
root값은 양쪽 필드에 다 포함될 수 있고, non-root 값들은 all_objects에만 포함될 것이다.

실사용 객체 타입 설계

내부 객체와는 별도로 사용자 측면에서 사용할 일종의 스마트 포인터도 필요하다.
이건 값이 clone으로 얕은 복사가 될 경우 같은 객체를 가리켜야 한다.

필드 자체는 단순하게 잡았다.
유의할 점은, 여기다가 지속되어야 하는 값을 넣어서는 안된다는 것이다. 이 래퍼 객체의 생사와 별개로 실제 객체의 수명을 우리가 직접 관리해야하기 때문이다.

여기다 의미있는걸 넣으면 변수가 스코프를 벗어나자마자 할당해제돼서 끔찍한 UB가 발생할 것이다.

그리고 조금 난감한 문제가 하나 있는데, root와 root가 아닌 것을 구분하거나 객체 아래에 다른 객체가 소속되는 것을 라이브러리 설계 수준에서 감지하기 좀 어렵다는 것이다.
언어 수준에서는 이런걸 구분하는게 어렵지 않다만, 그냥 구조체나 함수 수준에서는 이런걸 알 수가 없다.

그래서 여기서는 그냥 단순화해서 수동으로 생성하고 부모-자식도 명시하도록만 해뒀다.