Rust 기능을 끔찍하게 오용해서 포인터 수프에 대해 증명 가능한 메모리 안전성과 트레이싱 가비지 컬렉션을 제공하는 이야기.
Rust 기능을 끔찍하게 오용해서 포인터 수프에 대해 증명 가능한 메모리 안전성과 트레이싱 가비지 컬렉션을 제공하기.
2026-04-22
정오표: 발표 슬라이드와 이 블로그 글에는 평소보다 훨씬 많은 오타와 사소한 코드 오류가 들어갔습니다. 완전히 잠을 못 잤던 탓이라고 하겠습니다! 제가 말하려는 핵심을 방해하지 않도록, 발견하는 대로 고치고 있습니다. 여기에 링크된 슬라이드와 영상판 슬라이드(언제 올라오든)가 서로 다르다면, 여기 있는 슬라이드가 더 정확하니 제가 그걸 썼다고 생각해 주세요 :) 이렇게 늦게 바로잡게 되어 죄송합니다!
이 글은 제가 4월 22일 첫 TokioConf에서 발표하는 내용의 텍스트 버전입니다. 저는 이런 발표를 먼저 거의 평범한 블로그 글 형태로 써 두는 편인데, 산문으로 먼저 정리하는 것이 준비에 도움이 되기 때문입니다.
발표를 보고 계시면서 함께 따라오고 싶으신 분들을 위해 슬라이드 링크도 여기에 넣어 두었고, 영상 버전이 준비되면 그것도 링크할 예정입니다.
발표 주제를 고를 때마다 저는 늘 서로 충돌하는 두 목표 사이에서 고민하게 됩니다.
이 둘 중 어느 쪽도 나쁜 전략은 아니지만, 이번 발표/글은 거의 전적으로 두 번째 목표의 사례입니다. 저는 최근 Rust 언어의 매우 이상한 한 구석에서 살고 있었고, 그 경험을 중심으로 발표를 구성하기로 했습니다.
이번 발표는 Tokio Conf에 어울리지 않아 보일 수도 있는 주제, 적어도 겉으로 보기에는 안전한 Rust에서의 가비지 컬렉션과 VM에 관한 이야기입니다. 발표에 두 번째 접근을 택했으니, 제가 최근에 진짜 네트워크 코드를 많이 쓰지 않았다는 현실도 마주해야 합니다 ¯(ツ)/¯ (게다가 제가 쓰는 네트워크 코드는 늘 비디오 게임 중심이라, Tokio가 실제로 주로 쓰이는 분야와는 좀 다릅니다). 하지만 그보다도 지난 몇 달 동안 저는 Kong(TokioConf의 스폰서 중 하나입니다!)과 바로 이 주제 를 함께 작업해 왔습니다. 그들은 자신들의 네트워크 규칙 엔진을 위해 작고, 격리되어 있고, 안전한 Rust VM을 설계하는 일을 제가 돕도록 계약했습니다. 그러니 적어도 조금은 주제에 맞는다고 주장할 수 있겠죠! 하지만 결국 중요한 건, 이게 제가 해 온 일이고, 제가 뭔가 흥미로운 말을 할 가능성이라도 있는 주제라는 점입니다. 그래서 이게 제 발표입니다.
흥미롭게 읽어 주시길 바랍니다!
여기서는 제 다른 작업이나 발표, 이전 블로그 글들에 대한 사전 지식이 없다고 가정하겠습니다. 그래서 예전에 이야기했던 것들도 분명 일부 다시 다룰 예정입니다.
꽤 오래전, 저는 안전한 Rust에 트레이싱 가비지 컬렉션을 통합하려는 집착이 있었습니다.
저만 그랬던 것은 결코 아니었지만, 아마도 저는 두 가지 아주 구체적이고 공격적인 핵심 목표를 동시에 가진 거의 유일한 사람이었을지도 모릅니다.
Gc 포인터 자체 가 *const T를 감싼 투명한 래퍼이면서 Copy이고, 따라서 할당과 수집 단계에 당연히 피할 수 없는 오버헤드가 있더라도 포인터 자체의 비용은 raw pointer와 정확히 같아야 한다는 것입니다.저는 대체로 이것에 실패했다 고 생각하며, 일반적인 경우에 이 일을 하려면 아직 존재하지 않는 언어 차원의 지원이 사실상 필수 라는 결론에 이르렀습니다. 하지만 그렇게까지 심하게 실패한 것은 아니었나 봅니다. 이 문제를 해결하려는 제 최선의 시도인 gc-arena[2]Ruffle에서 사용되기 시작한 이후, gc-arena에는 Ruffle 개발자들의 아주 핵심적인 기여가 많이 들어갔습니다. 제가 전부 혼자 해낸 것처럼 공을 독차지하려는 것은 아닙니다! 는 지금 수백만 명이 사용하는 두 프로젝트에서 쓰이고 있습니다. 브라우저 기반 플래시 에뮬레이터인 Ruffle은 ActionScript VM에 gc-arena를 사용하고 있고, Fields of Mistria는 다음 릴리스에서 제 프로젝트 fabricator를 사용합니다. 이 프로젝트는 GameMaker 대체 런타임이며, 역시 gc-arena를 사용합니다.[3]실제로 무슨 일이 있었냐면, 제가 실제로 해결한 문제(즉, GC “컨텍스트” 안에서 어떤 Rust 코드도 “활성” 상태가 아닐 때만 가비지 컬렉션을 수행하는 것)는 게임에 딱 맞았다는 것입니다. 게임(그리고 Ruffle은 사실상 게임 엔진입니다)은 한 프레임 중간에 가비지 컬렉션을 할 필요가 거의 없고, 코드도(코루틴 같은 특별한 것들을 제외하면) 한 프레임보다 더 오래 실행되지 않기 때문입니다. 이것은 “내가 해결할 수 있는 다른 문제를 갖고 있는 건 아닐까?”의 훌륭한 사례로 봐야 합니다.
이건 분명 자랑이기도 하지만, 그보다 더 중요한 건 저 자신과 몇몇 소수의 사람들이 거의 아무도 Rust와 연결 지어 생각하지 않는 극도로 이상한 생태계 안에 있다는 사실을 깨달았다는 점입니다. 이건 제 시도만의 특수한 문제가 아닙니다(물론 저는 이 경우를 가장 잘 압니다). 하지만 Rust에서 안전한 가비지 컬렉션을 해결하려면 거의 예외 없이 타입 트릭이나 lifetime 트릭, 혹은 겉에서 보면 미친 것 같은 코딩 패턴이 필요합니다. 아래 예시들을 이해할 필요는 없지만, 실제 상용 프로젝트[4]Fields of Mistria 는 저는 거리낌 없이 사랑하는 작품이고, 엄청나게 혜자인 게임이며, 포근한 농장 게임을 좋아하신다면 꼭 해 보셔야 합니다. 에서 실제로 돈 받고 팔리는 코드가 이렇다는 걸 보세요...
// 대체 `ctx`는 뭐야?
let methods = Gc::new(&ctx, DsGridMethods);
// 대체 `unsize!`는 뭐야? 왜 문법이 따로 있어?
let methods_ptr = gc_arena::unsize!(methods => dyn vm::UserDataMethods<'gc>);
이것도...
// 대체 `Rootable![_]` 매크로는 뭐야, **타입**으로 평가된다고?
// 매크로 안의 '_는 또 뭐야?
let methods = ctx.singleton::<Rootable![DsGridMethodsSingleton<'_>]>().0;
let ud = vm::UserData::new::<Rootable![DsGrid<'_>]>(&ctx, self);
ud.set_methods(&ctx, Some(methods));
이것도...
// 좋아, downcasting은 이해해. `downcast_write`는 아마...
// `downcast_mut` 같은 거겠지? `&mut T`를 반환하나? 아니라고? 전혀 다른,
// 이해 불가능한 GC 전문용어라고? `&'gc barrier::Write<T>`?
let ds_list = DsList::downcast_write(&ctx, ud).unwrap();
// 또다시, 대체 barrier는 뭐야? 왜 이건 매크로여야 해? 이 문법은 또 뭐고?
// 왜??
let inner = barrier::field!(ds_list, DsList, inner);
// 좋아, 이 부분은 대충 이해했어. 그런데 *unlocking*은 또 뭐야?
let mut vec = inner.unlock().borrow_mut();
이건 너무 과하게 설계된, “내 똑똑함이 내 발목을 잡는” 스타일의 코드라서, 이렇게 쓸 아주아주 타당한 이유가 없다면 당신을 해고시킬[5]혹은 somehow TokioConf에 초대할 수도 있는 종류의 코드입니다.
그런데도... 이런 코드는 거의 해독 불가능한데도, 지금 이 순간 실제 세계의 어느 정도 인기 있는 두 프로젝트 안에 존재합니다. 저는 이것을 Rust 프로그램이 맞닥뜨릴 수 있는 문제 공간에 잘 이해되지 않은 구석이 있다는 신호로 받아들이고, 더 많은 사람들에게 이 공간을 소개할 좋은 시점이라고 생각합니다. 제 생각에는 안전한 Rust에서 더 단순해야 마땅한데 전혀 그렇지 않은 흥미로운 프로그램 부류가 많이 있습니다. 그리고 Rust처럼 보이지만 실은 낯선 피진 언어 같은 느낌의 방식으로 프로그래밍하는 정신적 부담이 있더라도, 그것이 오히려 현실적으로 가장 나은 선택지 일 수도 있습니다.
내 개인적인 지옥을 더 많은 사람에게 소개하면, 덜 괴롭지 않을까?
하지만 걱정하지 마세요. 이 글은 사실 gc-arena의 구체적인 설계나 제가 방금 보여 준 대부분의 내용 자체에 관한 글은 아닙니다.[6]정말 관심 있다면 여기서부터 시작하세요. 진짜 핵심은 Rust에서 가비지 컬렉션을 다루는 일이, 최소한 사용자 코드 곳곳에 unsafe {}와 *const T를 깔아놓고 싶지 않다면, 엄청나게 어렵다 는 점을 보여 주는 것이었습니다. 사실 이 글은 주로 가비지 컬렉션 자체에 대한 글도 아닙니다. 오히려 충분히 오래 Rust를 써 본 사람이라면 누구나 수도 없이 부딪혔을 이 단순하고 짜증 나는 진실을 다루는 이야기입니다.
Rust는 순환 포인터를 다루는 데 정말 약하다.[7]논쟁적인 주장이라는 건 압니다.
이것이 이번 발표의 중심 아이디어이며, 현재 Rust에서 이 현실을 다루는 여러 방법을 탐구하는 것입니다.
물론 이 글에는 사실상 Rust라는 언어의 현재 상태에 대한 푸념이 꽤 많이 들어갈 텐데, 이것을 적절한 맥락에 놓는 것이 중요합니다. 제가 불평할 때, 그것은 완전히 안전한 Rust 인터페이스로 달성 가능한 것에 대한 불평입니다. 그리고 제가 설명할 문제 집합에 대해서는, 증명 가능한 메모리 안전성을 원한다면 Rust가 사실상 유일한 선택지 나 다름없습니다.
프로그래밍 언어는 아주 거칠게 나누면 포인터[8]여기서 “포인터”라고 할 때 제 뜻은 엄밀히는 Rust 용어로 포인터 또는 참조입니다. 즉, 언어가 어떤 값을 다른 곳에서 “가리키게” 하는 모든 수단을 뜻합니다. 와 포인터 안전성을 다루는 방식에 따라 세 부류로 나뉩니다.
Drop 진영: 안전한 Rust, Swift, 이론상의 C++이 목록의 2번을 본 거의 모든 사람은 즉시 “가비지 컬렉션 언어”를 떠올릴 것이고, 틀린 건 아닙니다. 하지만 계속 가기 전에, 이 해법의 공간을 생각하는 방식과 아주 관련이 깊은, 어쩌면 논쟁적일지도 모를 말을 하나 하고 싶습니다.
소유권과 Drop 역시 가비지 컬렉션의 한 형태다.
이건 물론 정의의 문제이지만, 저는 이 정의가 가장 자연스럽다고 생각합니다. 사용자가 메모리를 수동으로 해제하도록 강제하지 않는 모든 언어는 어떤 방식으로든 그 메모리를 자동으로 해제해야 하며, 보통 “가비지 컬렉션”이라는 이름은 메모리를 자동으로 해제하는 시스템 전반을 가리키는 데 쓰입니다. 저는 이것이 전혀 이상하게 느껴질 이유가 없다고 생각합니다.[9]Drop과 Rc를 그저 또 다른 종류의 가비지 컬렉션이라고 부르는 것은 GC 문헌에서 흔한 주장처럼 보이는데, 저도 여기에 동의합니다.
이 렌즈로 보면 Rust가 왜 순환 포인터를 다루는 데 약한지 즉시 보입니다. 안전한 Rust는 메모리 안전해야 하고 포인터(참조)가 dangling이 아님을 증명해야 하는데, 유일한 가비지 컬렉션 체계가 소유권 기반이고, 순환 포인터는 정의상 명확한 소유 관계를 갖지 않기 때문입니다. 따라서 Rust는 그것들을 자동으로 가비지 컬렉션할 수 없어야 합니다! 그러므로 가능한 모든 순환 포인터는 정확히 같은 시간 동안 살아야 하거나(&'static T), 아니면 가비지 컬렉션이 자동이 아니어서 컴파일러가 안전성을 증명할 수 없어야 합니다(포인터는 raw pointer여야 하고 수동으로 해제되어야 합니다).
Rust를 쓰는 사람은 거의 모두 이 사실을 아주 빨리 알게 됩니다.[10]그리고 보통 이 발견은 경멸적으로 “borrow checker와 싸운다”라고 불립니다. 제가 새롭게 제시하는 것은 아마 이 문제를 다른 언어와의 관계 속에서 보는 관점 정도일 겁니다. Rust는 소유권과 자동 drop을 가지고 있고, 대부분의 다른 안전한 언어는 대신 도달 가능성 의 개념을 가지며, 객체가 도달 불가능 해지면 해제됩니다. Rust는 시스템 프로그래밍에서 더 폭넓게 유용한 것을 택했습니다. 즉, 도달 가능성을 통한 사이클 처리 능력을 희생하는 대가로 “결정적” drop을 택한 것입니다. 이것은 성능이 예측 가능하고, 런타임 요구사항이 최소이며, 정적으로 알려진 drop 시점에서 비사소하거나 핵심적인 동작을 수행할 수 있게 해 줍니다.
이제 제가 최근 작업해 온 프로젝트들을 생각해 보면, 왜 제가 Rust의 이 불편한 현실과 씨름할 수밖에 없었는지는 분명합니다. 그 프로젝트들은 Rust를 사용해 “도달 가능성” 진영에 속하는 언어를 안전하게 구현 하고 있었기 때문입니다.
이제는 거의 밈이 되다시피 했지만, Rust로 연결 리스트를 만드는 것은 어렵습니다. 다음은 Lua로 만든 순환 연결 리스트입니다.
-- Lua에서의 순환 연결 리스트 예시
local a = {}
local b = {}
local c = {}
-- 그냥 이렇게... `next` 포인터를 설정하면 끝이라고?
a.next = b
b.next = c
c.next = a
-- 이제 노드들은 이렇게 생겼다. 쉽다!
--
-- [a] -> [b] -> [c]
-- ^ |
-- | |
-- +-------------+
이건 아주 쉽게 됩니다. 그리고 이런 종류의 사이클은 실제 Lua 코드(그리고 Python, Ruby, Javascript, 심지어 Java 에서도...)에 널리 퍼져 있습니다. 문자 그대로 연결 리스트인 경우는 거의 없더라도 말이죠. 그렇다면 Rust는 이걸 도대체 어떻게 다뤄야 할까요? 이런 “도달 가능성” 언어를 해석하는 Rust 인터프리터 어딘가에서는, 반드시 이 자료 구조를 Rust 내부 자료 구조로 표현할 수 있어야 합니다.
제가 앞에서 말한 내용을 고려하면, 이것은 안전하게는 불가능해야 합니다. 그리고 최소한 도달 불가능한 포인터를 언젠가 삭제 하고 싶다면, 일반적인 &'a T로 이것을 하는 것은 (일반적인 경우) 건전하게는 불가능합니다. 나중에 다른 종류의 특수 포인터와 사악한 트릭을 사용해서 이 문제를 다루는 방법은 다룰 예정입니다.
지금 당장은 crates.io만 훑어봐도 순환 그래프 구조를 처리할 수 있는 Rust 코드가 분명 존재하고, 그리고 확실히 그 대다수는 이를 위해 고급 lifetime 트릭이나 bacon-rajan 식의 순환 Rc를 사용하지 않습니다. 먼저 Rust에서 이 문제를 다루는 (압도적으로) 가장 흔한 방법부터 이야기해 봅시다...
보통 Rust를 처음 배울 때 어느 시점에 순환 참조가 필요해 보이는 문제를 만나고, 결국 borrow check 오류를 보게 됩니다. 대개 사람들은 연결 리스트 같은 교과서적 예제로 이 문제를 처음 겪지는 않습니다(그걸 직접 구현하며 배우는 경우는 예외입니다). 보통은 사실 다른 방식으로 해결 가능한 문제를 먼저 만납니다. 어떤 경우에는 더 좋은 방식일 수도 있고, 어떤 경우에는 그냥 다른 방식일 수도 있고, 어떤 경우에는 조금 더 짜증 나는 방식일 수도 있습니다. 그리고 시간이 지나면서 Rust의 소유권 시스템을 더 잘 체화하게 되죠.
하지만 결국은 어떤 종류로든 순환 참조가 정말 필요한 문제를 만나게 됩니다. 문맥만 보고는 “역참조”가 무엇인지 항상 알 수 없는 경우도 있고, 객체들이 진짜 비구조적인 순환 그래프 안에 있어서 명백한 소유 관계가 전혀 없는 경우도 있고, 다른 선택지가 없는 경우도 있습니다.
그리고 결국은 이 문제를 푸는 올바른 방법이 Vec와 인덱스를 사용해서 그래프를 인코딩하는 것이라는 사실을 알게 됩니다(혹은 누군가가 그렇게 알려 줍니다). 이건 솔직히 정말 훌륭한 해결책입니다. 특히 문제 자체가 그 외에는 단순할 때 말이죠! 만약 모든 “노드”가 하나의 Rust 타입으로 표현될 수 있고, 그리고 그래프 구조를 대체로 한 번 만들고 나서 작은 동적 삽입/삭제를 많이 하지 않는다면, 그냥 노드들을 Vec에 push하고 그 Vec 인덱스를 “포인터”로 쓰면 끝입니다! 사실상 필요한 변화는 “포인터 컨텍스트” 비슷한 것(기저 저장 Vec에 대한 접근)을 계속 넘겨야 한다는 점과, node.field가 nodes[node_idx].field로 바뀐다는 문법적 변화뿐입니다.
아주 작은 예제를, 약간의 보조 API와 함께 봅시다...
이 절에서는 단순화를 위해 단일 타입 의 할당만 다룹니다. 여러 타입을 할당하는 것으로 확장하는 것은
HashMap<TypeId, Box<dyn Any>>와 downcasting 같은 것을 쓰면 비교적 곧바로 할 수 있습니다.
// Vec 안의 슬롯을 위한 할당기.
struct SlotAlloc<T> {
slots: Vec<T>,
}
impl<T> SlotAlloc<T> {
// 새로운 슬롯을 할당하고 `slots` vec에 push한 뒤, 그 인덱스를 반환!
// 단순함의 화신.
fn alloc(&mut self, value: T) -> usize { ... }
// 할당된 인덱스로 값을 가져오기.
fn get(&self, index: usize) -> &T { ... }
fn get_mut(&mut self, index: usize) -> &mut T { ... }
}
이런 식으로 Vec를 사용할 때, 저는 우리가 Vec를 배열이라기보다 할당기 처럼 사용한다고 말하고 싶습니다. SlotAlloc::alloc이 반환하는 실제 값이 무엇인지는, 보통 할당기가 돌려주는 정확한 주소 자체를 별로 신경 쓰지 않는 것과 같은 의미에서, 그다지 중요하지 않습니다.[11]네 네, 프로세서는 메모리 지역성을 좋아하고 캐시도 있고 prefetch도 있고 다 압니다. 제가 말하는 건 그게 아닙니다 <3 모든 슬롯의 위치를 뒤섞고 인덱스 “포인터”만 업데이트해도, 우리가 실행하는 알고리즘은 본질적으로 변하지 않을 것입니다.
이 말은 허무하게 들릴 수도 있고, 너무나도 당연하게 들릴 수도 있습니다.[12]만약 그렇다면, 적어도 제가 이미 예상하신 곳이 아닌 데로 가고 있기를 바랍니다(혹은 둘 다). 하지만 저는 이 기법을 이렇게 생각해 보셨으면 합니다. 포인터 (usize 인덱스) + 어떤 종류의 컨텍스트 (소유자인 SlotAlloc) 말입니다. 이런 식의 사고는 이것을 안전한 내장 참조, raw pointer 같은 다른 종류의 포인터와 비교 평가하는 데 도움이 됩니다.
먼저 좋은 점부터 보겠습니다. 무엇보다 단순함에서는 usize를 이길 수 있는 게 없습니다! Copy이고, 직렬화 할 수도 있고, “분할된 메모리”를 쓰고 있으므로 네이티브 포인터 크기(usize)를 쓰거나 주소 공간을 줄여(u32 / u16)도 됩니다. 또 아주 중요한 점은, 실제 참조와 달리 usize는 참조 대상이 Sync가 아니더라도 절대 !Send가 되지 않는다는 것입니다. 그래서 실제 참조를 쓰면 불가능할 수도 있는 상황에서도 컨테이너 전체를 Send로 만들 수 있습니다이 점은 중요하고, 나중에 다시 나옵니다! 원하신다면 왜 이것이 참인지 아주 조심스럽게 생각해 보세요. 이 부분은 안전하게 해결하기가 거의 불가능할 수도 있고, 건전성을 위해 반드시 인덱스 기반 전략을 쓰게 만들 수도 있습니다.
이제 나쁜 점을 보겠습니다. 우선 일반 포인터와 비교했을 때 몇 가지 불편함이 있습니다.
우리 “포인터”의 나쁜 성질은 실제 기계 포인터를 쓸 때 생기는 문제와 굉장히 비슷합니다. 먼저, 모든 할당 전략과 마찬가지로, 아예 해제만 하지 않으면 사실상 무엇이든 잘 돌아갑니다! SlotAlloc을 항목 해제가 가능하도록 확장하는 일은 충분히 간단합니다. 슬롯 타입을 Option<T>로 바꾸고 free list를 유지하면 됩니다...
// Vec 안의 슬롯을 위한 할당기.
struct SlotAlloc<T> {
slots: Vec<Option<T>>,
free_list: Vec<usize>,
}
impl<T> SlotAlloc<T> {
// 새로운 값을 할당. `free_list`에 비어 있는 인덱스가 있다면 그것을
// 사용하고, 아니면 새 값을 push한다. 어느 쪽이든 배정된 슬롯의
// 인덱스를 반환한다.
fn alloc(&mut self, value: T) -> usize { ... }
// 이 슬롯을 `None`으로 만들고 free list에 추가한다.
fn free(&mut self, index: usize) { ... }
// 할당된 인덱스로 값을 가져온다. 해제된 `index`가 주어지면 panic!
fn get(&self, index: usize) -> &T { ... }
fn get_mut(&mut self, index: usize) -> &mut T { ... }
}
하지만 물론 이것은 자동으로 아무것도 해제해 주지 않을 뿐만 아니라, 우리 “포인터”를 “해제”하는 순간 전형적인 use after free 버그가 생길 수 있습니다! 부주의하게 인덱스를 해제한 뒤 그 해제된 인덱스에 접근하면, 해제된 메모리를 잘못 사용하는 결과(None을 unwrap하는 것)가 됩니다. 물론 이 경우에는 UB 대신 결정적인 panic 이 나므로 수십억 배는 낫지만, 그래도 메모리를 자동으로 관리하는 것보다는 훨씬 덜 유용합니다.
둘째로 ABA 문제라는 것이 있습니다. 포인터 비유로 보면 이것 역시 “use after free”의 한 종류지만, panic보다 훨씬 더 나쁩니다. 아직 살아 있는 참조가 남아 있는데 실수로 인덱스를 해제한 다음, 다른 값을 할당했더니 우연히 같은 인덱스를 다시 받는다면, 그 “죽은” 인덱스에 대한 접근은 성공할 뿐 아니라 사실상 임의의 유효한 값 을 돌려주게 됩니다. 운이 나쁘면 Heartbleed 같은 수준으로까지도 나빠질 수 있습니다. 기대한 데이터 대신 전혀 다른 임의의 데이터를 오류 없이 읽고, 그걸 잘못된 상대에게 노출할 수도 있는 것이죠.
셋째 문제도 있습니다. SlotAlloc 할당기가 둘 이상 있으면 우리의 메모리는 “세그먼트”로 나뉩니다. 물론 이것 자체가 문제는 아닙니다. 오히려 이렇게 “주소 공간”을 나누는 것이 유용한 기능처럼 보이기도 합니다. 하지만 사용자가 포인터의 세그먼트를 혼동 할 수 있게 됩니다. 한 SlotAlloc 인스턴스에서 다른 SlotAlloc 인스턴스로 데이터를 가져오는 과정에서, 어떤 인덱스가 어느 인스턴스에 속하는지 헷갈리면, 운이 좋으면 panic이고, 운이 나쁘면 우리가 피하려 했던 “UB는 아니지만 거의 비슷한 것”을 맞게 됩니다.
이 문제들을 가능한 한 많이 해결해 봅시다.
먼저 ABA 문제부터 다뤄 봅시다.
꽤 잘 알려진 아이디어[14]사실 이건 제 2018 RustConf 발표에서도 이야기한 적이 있습니다. 인 “세대 인덱스(generational indexes)”가 있습니다. 아이디어는 아주 단순합니다. SlotAlloc 구조의 각 슬롯마다 “세대(generation)”라는 별도 카운터를 둡니다. 그리고 항목이 삭제 될 때마다 그 슬롯의 generation을 증가시킵니다. 할당 시 반환되는 “인덱스”는 단순 슬롯 인덱스와, 할당 당시의 세대를 함께 담는 새로운 타입이 됩니다. 전체 그림은 대략 이렇습니다...
// Vec 안의 슬롯을 위한 할당기.
struct SlotAlloc<T> {
slots: Vec<Slot<T>>,
free_list: Vec<usize>,
}
// `SlotAlloc` 내부의 슬롯.
struct Slot<T> {
// 슬롯이 해제될 때마다 `generation`이 증가한다.
generation: u32,
value: Option<T>,
}
// `SlotAlloc` 안의 추상적인 “인덱스”.
#[derive(Copy, Clone)]
struct Index {
// `slots` vec 안의 인덱스.
slot: u32,
// 할당 당시의 세대.
generation: u32,
}
impl<T> SlotAlloc<T> {
// 새 값을 할당한다. `free_list`에 비어 있는 슬롯이 있다면 그 슬롯에
// 값을 배정하고, *세대를 증가시킨다*.
//
// 그렇지 않으면 `slots` vec 끝에 `generation`이 0인 새 슬롯을 만들고
// 값을 넣는다.
//
// 반환되는 `Index`는 배정된 `slot`과 그 슬롯의 `generation`을 함께
// 담는다.
fn alloc(&mut self, value: T) -> Index { ... }
// 이 인덱스가 가리키는 슬롯을 `None`으로 만들고 free list에 추가한다.
//
// `index.generation`이 현재 슬롯 세대와 같지 않으면 panic한다. 이건
// double free이기 때문이다!
fn free(&mut self, index: Index) { ... }
// 할당된 인덱스로 값을 가져온다.
//
// `index.slot`의 값이 해제되었거나 `index.generation`이 현재 슬롯 세대와
// 다르면 이 메서드들은 panic한다.
//
// 이는 직접적인 UAF와 ABA 문제 둘 다를 막아 준다.
fn get(&self, index: Index) -> &T { ... }
fn get_mut(&mut self, index: Index) -> &mut T { ... }
}
불행히도 삭제된 인덱스에 접근했을 때 생기는 오류(panic이든 뭐든)를 정적으로 막는 간단한 방법은 없습니다. 하지만 ABA 문제를 세대로 해결하면, 여기서 더는 무엇도 “이름만 다른 UB”처럼 느껴지지는 않습니다. 유효한 Index가 SlotAlloc 안에 있으면 올바른 값을 받고, 유효하지 않으면 panic을 받을 뿐입니다.
인덱스를 잘못된 SlotAlloc[15]“세그먼트”에 사용하는 문제도, 제가 이 비유를 끝날 때쯤 여러분이 질려 버리길 바라고 있어서 계속 이 단어를 쓰고 있지만 <3, 똑같이 쉽게 해결할 수 있습니다. 각 SlotAlloc에 고유 ID를 부여하고, 그 ID를 Index의 일부로 돌려준 뒤 접근 시 확인하면 됩니다. 그러면 Index는 이렇게 생길 수 있습니다...
struct SlotAlloc {
// 무작위로 생성한 ID 값.
alloc_id: u32,
...
}
struct Slot<T> { ... }
struct Index {
// 부모 `SlotAlloc`의 ID
alloc_id: u32,
...
}
impl<T> SlotAlloc<T> {
// 무작위 `alloc_id`를 가진 새 `SlotAlloc`을 반환.
fn new() -> SlotAlloc<T> { ... }
fn alloc(&mut self, value: T) -> Index { ... }
// 이제 `free`, `get`, `get_mut`은 모두 `index.alloc_id`가 일치하지 않아도
// panic한다. 그 말은 곧 다른 `SlotAlloc`이 만든 인덱스라는 뜻이다.
fn free(&mut self, index: Index) { ... }
fn get(&self, index: Index) -> &T { ... }
fn get_mut(&mut self, index: Index) -> &mut T { ... }
}
이제 원래 SlotAlloc 설계에서 나열했던 문제들은 거의 다 해결된 셈입니다. 적어도 가능한 모든 오류는 런타임 에 검사되어 결정적으로 panic합니다. 우리가 피하려고 했던 “좀 UB 같은” 동작은 더 이상 없습니다!
심지어 이건 단일 Rust 타입에 대한 꽤 정상적인 할당기처럼 보이기까지 합니다. SlotAlloc은 그냥 할당기처럼 동작하는데, *mut T 대신 Index를 돌려줄 뿐입니다. 오류가 일어날 수 없도록 만들지는 못했지만, 적어도 어떤 오류도 조용히 지나갈 수는 없게 했습니다. Vec 인덱스를 이렇게까지 밀어붙일 수 있다는 건 꽤 멋집니다!
요약하자면, 우리는 어떤 “세그먼트”(SlotAlloc) 안으로 들어가는 일종의 “특수 포인터”(Index)를 가지고 있고, 이 포인터는 세그먼트 식별자(alloc_id), 세그먼트 안의 실제 포인터(slot), 그리고 어떤 alloc 호출이 이 “포인터”를 만들었는지를 알려 주는 일종의 출처 값(generation)을 담고 있습니다.
이 세 조각 각각에 비트 수를 마음대로 정할 수 있습니다. 우리의 TypedIdx에 아주 그럴듯하고 상징적인 수의 비트 를 각 부분에 배정해서 메모리에 이렇게 놓아 봅시다...
[------arena ID (32 bits)------][-----generation (32 bits)-----]
[------------------------slot (64 bits)------------------------]
이제 wikipedia article의 CHERI(Capability Hardware Enhanced RISC Instructions) 항목에서 가져온 이 그림을 봐 주세요:
CHERI는 포인터에 metadata 를 붙여서 올바르게 사용되도록 보장하고, 잘못 사용되면 반드시 “trap”되도록(오류 처리기를 호출하도록) 해서 UB를 막는 굉장히 멋진 하드웨어 capability system입니다.[16]제가 여기서 하는 설명이 그 가치를 제대로 반영하지 못한다는 건 너무나 명백해서 굳이 말할 필요도 없습니다.
물론... CHERI가 generational indexing과 같다고 말하는 건 엄청나게 우스꽝스럽다는 걸 저도 압니다...[17]그냥 하드웨어 가속된 generational indexing이죠! 하지만 두 개의 유사성은 어딘가 시사하는 바가 있습니다.[18]제발 이해해 주세요. 제가 이걸 문자 그대로 진짜로 같다고 생각하는 건 아닙니다. CHERI가 하드웨어 수준의 유효성 강제, bounds checking, data race 방지(수정: 아닌 것 같네요?), 그리고 15년간의 연구를 포함한다는 것도 압니다. 이건 밈입니다. 여기서 핵심은 우리가 만든 시스템이, 정상적인 하드웨어 포인터와 꽤 비슷하지만 안전한 것이라는 점입니다. 실제 UB의 의미에서도 안전하고, 또 우리가 말한 “내부적 UB 유사 동작”의 의미에서도 안전합니다. 그러니 이런 걸 만들려면 비슷한 해법 지형을 바라보게 되는 것이 자연스럽습니다.
이 절의 핵심은, 올바른 시각으로 보면, (안전한) Rust에 더 강력한 포인터가 없을 때 “Vec와 인덱스를 쓰자”는 해법이 놀랍도록 많이 Rust가 강제하는 제한 없는 포인터를 통째로 다시 발명하는 것과 비슷하다는 점을 보여 주는 것입니다. 저는 이게 나쁘다고 말하는 게 아닙니다! 컴파일러가 강제하는 정확성과 런타임 정확성 사이에 스펙트럼이 존재하는 것은 좋은 일입니다.[19]만약 CHERI가 널리 배포되어 있다면, 플랫폼에 따라 자유롭고 값싸게 공유할 수 있고 수동으로 해제도 가능하지만 UB 대신 trap 을 보장하는 CheriPtr<T> 같은 타입이 Rust에 생기는 것도 상상할 수 있습니다. 하지만 우리는 이 상황을 냉정하게 봐야 합니다. 이런 모든 수준의 상황은 raw pointer와 UB보다는 분명히 낫습니다.[20]개인적 경험상 slotmap 같은 것의 generational indexing만 있어도 구세주가 될 수 있고, 거기서 멈춰도 정말 훌륭한 경우가 많습니다. 대충 90%의 경우에는, 늘 잘 됩니다. 하지만 그렇다고 해서 모두가 해법 찾기를 거기서 멈춰야 하는 건 아닙니다.
좋습니다. 이제 포인터와 비슷한 인덱스 해법이 가능하다는 것은 봤지만, 그것이 (여러 면에서 raw pointer와 마찬가지로) 이상적이지는 않다는 것도 봤습니다. 더 나은 방법이 있을까요?
물론 진짜 Rust 참조(&'a T)는 어떤 Vec 인덱스나 raw pointer보다 낫고, 보통은 어떤 “smart” pointer보다도 낫습니다. 그렇다면 Rust에서 실제 순환 참조를 가진 자료 구조를 만드는 것이 아예 가능한지부터 봅시다.
놀랍게도, 그건 가능할 뿐 아니라 비교적 쉽기까지 합니다! 아까 Lua 예시에서 봤던 것을 참고해 Rust로 연결 리스트를 만들어 봅시다.
우리의 Node 타입은 이렇게 생길 수 있습니다...
// 연결 리스트의 노드에 대한 단순한 예시.
struct Node<'a> {
value: String,
next: Cell<Option<&'a Node<'a>>>,
}
impl<'a> Node<'a> {
fn new(value: String) -> Node<'a> {
Node {
next: Cell::new(None),
value,
}
}
fn next(&self) -> Option<&'a Node<'a>> {
self.next.get()
}
fn set_next(&self, node: Option<&'a Node<'a>>) {
self.next.set(node)
}
}
그리고 이렇게 사용할 수 있습니다...
// `bumpalo` 크레이트의 bump allocator.
let bump = bumpalo::Bump::new();
// 여기서 반환되는 각 노드는 참조이며, 그 참조는 `bump` allocator 자체의
// lifetime을 가진다.
let a = bump.alloc(Node::new("1".to_owned()));
let b = bump.alloc(Node::new("2".to_owned()));
let c = bump.alloc(Node::new("3".to_owned()));
// 따라서 `next` 노드 포인터를 설정해서 각 노드 안의 'a lifetime이
// `Bump::alloc`이 반환한 참조의 lifetime과 같아지도록 만들 수 있다.
//
// `Bump::alloc`이 반환하는 참조들의 lifetime은 모두 같으므로, 각 `Node`
// 인스턴스의 'a lifetime도 모두 같아지고, *바로 그것* 때문에 이것이 가능한
// 것이다. 이것이 순환적이라는 사실은 Rust가 이 lifetime들이 모두 동일하다고
// 판단했다는 점에 인코딩되어 있다.
//
// 이는 *반드시* 그래야 한다. 모든 노드가 (직접적으로든 간접적으로든) 다른
// 모든 노드를 참조하므로, 이들은 *정확히 같은 시간 동안* 살아야 한다.
a.set_next(Some(b));
b.set_next(Some(c));
c.set_next(Some(a));
이렇게 쉽다면, 도대체 이 블로그 글은 뭘 말하려는 걸까요?
이 해법에는 몇 가지 문제가 있습니다. 첫 번째, 눈에 띄는 문제는 노드 타입들이 bump를 빌리는 lifetime을 사용하고 있으므로 bump, a, b, c 전체를 다른 곳으로 쉽게 이동 시킬 수 없다는 점입니다. 하지만 이건 해결 불가능한 문제는 아닙니다. self_cell 같은 것을 쓰면 allocator와 그 allocator가 할당한 것들을 함께 이동시킬 수 있습니다.
하지만 훨씬 더 큰 문제가 있습니다. 건전성을 유지하려면, 이 Node들은 하나도 drop되어서는 안 된다 는 점입니다. bumpalo를 조금이라도 써 보셨다면 이미 겪어 보셨을 사실이며, 이것은 Bump documentation 맨 위에도 적혀 있습니다. 왜 이것이 건전성에 필요할까요? 예를 들어 우리가 이런 Drop 구현을 갖고 있다고 해 봅시다...
impl<'a> Drop for Node<'a> {
fn drop(&mut self) {
println!("dropping node with value {:?}", self.value);
if let Some(next) = self.next() {
println!("next value {:?}", next.value);
}
}
}
우리 노드 a, b, c는 모두 next 포인터가 설정되어 있으니, 각자의 Drop 구현은 자기 값과 다음 값 둘 다 출력할 것입니다. 그런데 a, b, c는 어떤 순서로 drop되어야 할까요? 어떤 순서를 고르더라도 UB가 아닌 유효한 순서는 없습니다! 만약 a를 먼저 drop하면, a가 소유한 String 값이 drop되고, 그 후 b와 c의 drop 구현이 그 값에 접근해서 UAF를 일으킬 수 있습니다. 어떤 노드를 먼저 골라도 사정은 같습니다.
생각해 보면 아주 분명한 이야기이고, 바로 이것이 bumpalo가 그런 API를 제공할 수 없는 이유 그 자체 입니다. 사실 bumpalo 없이도 같은 연결 리스트를 만드는 동등한 방법이 있습니다.
let a = Box::leak(Node::new("1".to_owned()));
let b = Box::leak(Node::new("2".to_owned()));
let c = Box::leak(Node::new("3".to_owned()));
이 역시 반환된 할당들의 lifetime이 모두 같기 때문에 동작합니다. 다만 이번에는 그 lifetime이 'static일 뿐입니다!
왜 Vec 기반 해법에서는 이런 drop 문제가 나타나지 않을까요? 답은 꽤 분명합니다. 우리는 진짜 포인터를 저장한 것이 아니라, 그 “컨텍스트” 타입인 SlotAlloc에 접근할 수 있을 때만 의미가 있는 “포인터”를 저장했기 때문입니다. 그런데 Drop trait의 구조상 우리는 SlotAlloc에 접근할 수 없기 때문에, 이 문제는 애초에 등장조차 하지 않았습니다!
SlotAlloc에서 했던 것처럼 노드를 수동으로 삭제할 수는 없을까요? 지금 상태로는, MaybeDangling 없이는 어떤 Node도 수동으로 drop하는 것이 실제로 불가능하다고 저는 생각합니다(가능한 순서가 전혀 없기 때문입니다). 참조를 MaybeDangling이나 내부 raw pointer 같은 래퍼로 감싸면 노드 제거를 허용하는 해법이 있을지도 모르지만, 안전한 인터페이스로 이를 어떻게 가능하게 할지, 또 도달 불가능한 노드만 drop되도록 어떻게 보장할지는 전혀 자명하지 않습니다.
게다가 더 나쁜 점도 있습니다! Cell<T>는 T가 Send라면 Send입니다. Cell<T> 자체를 다른 스레드로 보내는 것은 전혀 unsafe하지 않습니다. unsafe한 것은 &Cell<T>를 다른 스레드로 보내는 것입니다. Cell 자체에는 업데이트에 대한 스레드 안전성이 없기 때문에 Cell<_>는 언제나 !Sync입니다. 그런데 안타깝게도 위의 Node 타입은 안에 다른 Node에 대한 참조를 갖고 있으므로 역시 !Send가 됩니다. 그 결과 전체 구조도 !Send가 됩니다.
struct RefNode<'a> {
value: String,
// `Cell<T>` 때문에 RefNode는 `Sync`가 될 수 없고, 그 결과 `&'a
// RefNode<'a>`는 `!Send`가 되므로, `RefNode`도 `Send`가 될 수 없다.
next: Cell<Option<&'a Node<'a>>>,
}
struct IdxNode {
value: String,
// raw reference 대신 인덱스를 쓰면 이 문제는 완전히 사라진다.
// `IdxNode`는 `Send`이고, 그것들의 네트워크도 역시 `Send`다.
next: Cell<Option<NodeIdx>>,
}
비록 이 시도가 제약이 많지만, 더 나은 해법을 위해 중요한 힌트를 하나 줍니다...
어떤 순환 참조 집합에 속한 모든 참조는 동일한 lifetime을 가져야 한다.
Rust에서 이런 것이 직접 가능 하다는 점, 그리고 비록 non-'static이지만 같은 lifetime을 가져야 하는 객체 그래프를 Rust가 적어도 이 경우는 처리할 수 있어 보인다는 점은 사실 꽤 고무적입니다. 이 제약들을 어떻게든 완화할 방법이 있을까요? 인덱스 해법에는 이런 문제가 없었으니, 거기서 영감을 얻을 수 없는지 다시 생각해 봅시다.
for<'a>는 Rust에서 가장 멋진 기능이다사실 우리의 인덱스 해법은 장점이 정말 많았습니다! 주된 단점은 잠재적인 성능 문제를 제외하면, 인덱스가 컴파일 시점이 아니라 런타임 에 검사된다는 점입니다. 이는 이상한 일이 아닙니다. 보통 Rust 코드에서 슬라이스에 인덱싱할 때도 안전을 위해 런타임 bounds check가 들어가니까요. 그래서 이게 큰 문제가 아닌 것처럼 보일 수도 있습니다. 하지만 우리는 인덱스를 일종의 포인터로 사용하고 있습니다... &'a T나 Rc<T>나 Arc<T>가 런타임에 dangling 여부 검사를 받아야 하는 것은 분명히 아니죠!
아까 Vec 인덱스에는 런타임 검사가 일반적이라고 했는데, 그건 사실이지만 반드시 그래야 하는 것은 아닙니다. Rust에는 여러 용도 중 하나로, bounds check 없는 안전한 인덱싱을 가능하게 하는 기법이 실제로 있습니다! 이는 “generativity”라는 타입 성질을 이용하며, Rust에 이런 타입이 사실상 우연히 존재한다는 점을 처음 설명한 것은 Gankra의 master's thesis였습니다.
타입의 “generativity”란 일종의 제한된 dependent type처럼 동작하게 하는 성질입니다. 즉, 런타임에 어떤 코드가 실행될 때마다 그 코드 위치에서 마치 새로운 타입이 런타임에 생성되는 것처럼 보이며, 그렇게 생성된 타입은 같은 코드의 다른 실행이 만들어낸 다른 생성 타입들과 구별됩니다.
물론 실제로 그런 일이 문자 그대로 일어나는 것은 아닙니다. Rust 프로그램에는 런타임 타입 개념이 없습니다. 하지만 lifetime과 borrow checker를 사용하면 Rust에서도 이런 성질을 가질 수 있습니다! 함수 파라미터에 HRTB(Higher Ranked Trait Bound)를 지정하면, 이 함수가 어떤 가능한 lifetime에 대해서도 동작해야 한다고 선언할 수 있습니다. 이렇게 말이죠:
fn generate_a_lifetime(f: impl for<'a> Fn(&'a ())) {
f(&());
}
이건 사실 Rust 코드에서 꽤 흔한 패턴이지만, 이미 우리가 원하는 것에 꽤 가깝습니다. Rust borrow checker는 정책상 함수 경계를 넘나들지 않습니다. 따라서 주어진 callback 본문 안에서는, callback 함수가 어떤 가능한 'a에 대해서도 동작해야 한다고 선언했기 때문에, borrow checker는 'a가 실제로 무엇인지 거의 알지 못합니다. 마치 f가 호출될 때 그 호출을 위해 완전히 새롭고 유일한 lifetime a를 받는 것처럼 보이는데, 바로 이 성질이 우리가 원하는 것입니다! 사실 Rust lifetime에는 subtyping 이 있기만 하지 않았다면, 이것만으로도 완전한 generativity 예제가 되었을 겁니다. 예를 들어...
generate_a_lifetime(|a| {
generate_a_lifetime(|mut b| {
// `a`의 타입은 `&'a ()` 같은 것이고 `b`의 타입은 `&'b ()` 같은 것인데,
// 우리는 'a와 'b가 완전히 다른 두 타입이길 원한다. 그런데 이 코드는
// 타입 체크를 통과한다! 문제는 `&'a ()` 타입이 lifetime 'a에 대해
// *covariant*라서 *짧게 줄일 수* 있다는 점이다.
b = a;
});
})
그러니 Rust lifetime의 subtyping 을 없앨 수 있다면, 그 lifetime을 사용하는 타입에 완전한 generativity를 부여할 수 있습니다. 그리고 다행히 'a lifetime에 대해 invariant 한 타입을 만들면 정말 그렇게 할 수 있습니다.
// mutable한 타입은 언제나 자신이 담는 데이터에 대해 invariant하므로 `Cell<T>`는
// `T`에 대해 invariant다. `T` 안에 lifetime 'a를 사용하면 결과 타입도 항상
// 'a에 대해 invariant가 되고, 따라서 다른 lifetime과 아무 subtyping 관계도
// 갖지 않게 된다.
type Id<'id> = PhantomData<Cell<&'id ()>>;
fn generate_an_id(f: impl for<'a> Fn(Id<'a>)) {
// 여기서 전달하는 `Id`의 “실제” lifetime이 무엇인지는 사실 *중요하지
// 않다* 는 점을 강조하기 위한 코드다. 안전성은 callback이 갖는
// *보장된 무지* 에서 나온다. borrow checker가 함수 경계 너머의 정보를
// 사용하지 않기 때문이다.
let id: Id<'static> = PhantomData;
f(id);
}
generate_an_id(|mut a| {
generate_an_id(|mut b| {
// 어느 쪽 문장도 동작하지 않는다. `Id<'a>` 안의 lifetime 'a는 다른
// 것과 맞추기 위해 늘리거나 줄일 수 없다. 이것이 바로 우리가 원하는
// 성질이다! 덤으로 이제 `Id<'a>`를 thread local storage 같은 것에
// 넣는 것도 불가능하므로, `Id<'a>` 타입이 callback 밖으로 *탈출* 할 수
// 없다는 것도 알 수 있다.
//
// a = b;
// b = a;
});
});
성공입니다. 이제 generativity 성질을 가진 Id<'a> 타입을 얻었습니다!
그렇다면 이게 무슨 이득이 있을까요? 자세한 내용은 논문을 보시면 되지만, 핵심은 Rust가 복사 가능한 Id를 만들고, 나중에 어떤 Id가 원래 Id의 복사본인지 컴파일 시점에 검증할 수 있게 된다는 점입니다. 이것으로 bounds check 없는 완전히 안전한 인덱싱을 제공할 수 있습니다. 예제를 봅시다[21]링크한 논문에서 거의 그대로 가져온 것입니다 ...
// invariant branding ID.
type Id<'id> = PhantomData<Cell<&'id ()>>;
// 슬라이스와 고유 타입 `Id`를 결합한 래퍼.
struct Array<'arr, 'id, T> {
array: &'arr [T],
_id: Id<'id>,
}
// 같은 `Id`를 가진 `Array`에 대한 *신뢰할 수 있는* in-bounds 인덱스.
struct Index<'id> {
idx: usize,
_id: Id<'id>,
}
impl<'arr, 'id, T> Array<'arr, 'id, T> {
fn len(&self) -> usize { ... }
// `idx`가 `self.len()`보다 작으면 `Index<'id>`를 반환.
fn verify(&self, idx: usize) -> Option<Index<'id>> { ... }
// 이 메서드 내부에는 bounds checking이 필요 없다! 올바른 `Id`를 가진
// `Index`가 오직 *이 인스턴스* 의 `Self::verify`를 호출해서만 생성될 수
// 있다는 것만 알면, 그것은 내부 슬라이스 범위 안에 반드시 있다는 뜻이다.
fn get(&self, idx: Index<'id>) -> &T { ... }
}
// 슬라이스로부터 `Array`를 만들고, 검사된 인덱싱 “컨텍스트” 안에서 방문한다.
fn make_array<'arr, T>(
array: &'arr [T],
f: for<'id> impl FnOnce(Array<'arr, 'id, T>)
) { ... }
그리고 사용은 이렇게 합니다...
make_array(&[1, 2, 3, 4, 5], |array| {
// raw index를 검증할 때는 bounds check가 필요하다.
let idx = array.verify(4).unwrap();
// 하지만 그 인덱스를 사용하는 데는 필요 없다! 우리의 `Id` 타입 덕분에,
// `idx` 값은 *반드시* 그걸 생성한 `array`에서 나온 것임을 알 수 있기
// 때문이다.
dbg!(array.get(idx));
make_array(&[1, 2, 3], |array2| {
// 이건 타입 체크가 되지 않는다. `array`의 `Id`와 `array2`의 `Id`가
// 같지 않기 때문이다.
//
// let _ = array2.get(idx);
})
});
이 단순한 예제만 보면 조금 우스울 수 있지만, 실제로 유용한 흥미로운 방식으로 이 기법을 활용하는 것은 충분히 상상할 수 있고, 실제로 이를 위한 crate도 있습니다. 그런데 만약 이 기법을 써서 아까의 인덱싱 시스템에 컴파일 시점 안전성을 더한다면 어떨까요?
정리해 보면, 원래 인덱싱 시스템에는 런타임 정확성 문제의 주요 원천이 두 가지 있었습니다. 1) use after free / ABA 문제, 2) 서로 다른 arena 간 인덱스 혼동입니다. generativity가 arena 혼동을 막는 데 어떻게 쓰일 수 있는지는 적어도 겉으로는 꽤 분명합니다. Id 타입으로 Index에 “brand”를 찍으면, 올바른 SlotAlloc에서 반환된 Index만 그 SlotAlloc에 인덱싱하는 데 쓸 수 있습니다. 앞의 예제와 거의 같습니다(다만 callback 바깥 에 NodeIdx를 저장하는 복잡성은 일단 건너뛰고요. 그건 곧 다룰 겁니다).
즉, 한 가지 잠재적 정확성 문제는 컴파일 시점에 해결됩니다. 그렇다면 다른 문제는 어떨까요? 우리의 문제는 순환 참조 의 해법을 찾는 것이었지만, 사실 이것을 런타임의 일부로 허용하는 언어들이 하는 일은 도달 가능성 판단 입니다. 수동 삭제를 허용한다면 수동 검사를 피하는 것은 현실적으로 불가능합니다. 적어도 도움이 되는 방식으로는요[22]그래프 전체를 스캔해서 유효성을 검사할 수도 있겠지만, 그렇다면 왜 수동 검사를 하죠? . 만약 somehow 도달 가능성 을 자동으로 판단해서 더 이상 도달 가능하지 않은 노드를 삭제할 수 있다면, 적어도 그 작업을 하는 코드 밖에서는, 삭제된 Index를 관찰하는 것 자체를 불가능하게 만들 수 있습니다! 심지어 generational indexing 자체도 없앨 수 있겠죠!
아직 이것이 가능하다고 증명한 것은 아니지만, 아주 유망한 실마리입니다! 다음 절에서는 이 아이디어를 끝까지 밀어붙여, 순환 참조를 다루는 실제 동작 시스템을 만들어 볼 것입니다. 도달 불가능한 참조의 자동 삭제까지 포함해서요.
이제 더 큰 해법 공간을 탐색하던 흐름에서 잠깐 벗어나, 지금까지 이야기한 모든 것을 위한 구체적인 해법을 하나 파고들어 봅시다. 네, 실제 트레이싱 가비지 컬렉션까지 포함해서요. 내부적으로는 인덱스를 사용하는 가비지 컬렉션 시스템의 개요를 잡아 볼 것이고, 출발점은 앞서의 SlotAlloc 예제와 비슷합니다.
SlotAlloc절과 마찬가지로, 단순화를 위해 여기서도 단일 타입만 다룹니다. 이 경우 이 설계를 여러 타입으로 확장하는 방법은 전혀 자명하지 않습니다. 그러니 가능하다는 것만 일단 믿어 주세요!
우리는 내려야 할 결정이 많지만, 지금까지 정한 것들을 바탕으로 적어도 Index에 대응하는 것이 어떤 모습이어야 하는지는 알 수 있습니다. 모든 작업이 끝났을 때 더 적절한 이름이길 바라며 이것을 Gc라고 부르겠습니다. 위에서 썼던 Id 타입도 계속 사용하겠습니다...
// invariant branding ID.
type Id<'gc> = PhantomData<Cell<&'gc ()>>;
// sound하고 검사 없는 인덱싱에 기반한 `Arena` 안의 “포인터”.
#[derive(Copy, Clone)]
struct Gc<'gc> {
// 미리 예고해 두자. arena ID도 generation도 필요 없을 것이다!
index: usize,
_id: Id<'gc>,
}
저장 방식도 첫 번째 SlotAlloc 시도와 같은, 가장 단순한 최소한의 것을 택하겠습니다.
struct Arena {
slots: Vec<Option<T>>,
free_list: Vec<usize>,
}
좋습니다. 그런데 아직 인터페이스가 어떻게 생겨야 할지 정해야 합니다. branding Id를 담은 타입을 넘겨주는 접근자를 하나 두고, 그 위에 몇 가지 메서드를 추가해 봅시다...
type Id<'gc> = ...;
struct Gc<'gc> { ... }
struct Arena<T> {
// 실제 데이터를 담는 것은 `ArenaCtx`.
ctx: ArenaCtx<'static, T>,
}
impl<T> Arena<T> {
// 이것은 앞서 검사된 인덱싱 예제의 `make_array` 함수와 비슷하다. 내부에는
// `ArenaCtx`로 표현되는 “컨텍스트”가 있고, 이 컨텍스트는 이 메서드가
// 호출될 때마다 매번 고유하다.
fn enter<F, R>(&mut self, f: F) -> R
where F: for<'gc> FnOnce(&mut ArenaCtx<'gc, T>) -> R
{
// 검사된 인덱싱 예제와 마찬가지로, 여기서 구체적인 lifetime 'gc 자체는
// 사실 중요하지 않다. 중요한 것은 그 lifetime에 대한 지식이 없다는 점.
f(&mut self.ctx)
}
}
// `Arena::enter`가 전달해 주는, arena에 접근할 수 있는 핸들.
struct ArenaCtx<'gc, T> {
slots: Vec<Option<T>>,
free_list: Vec<usize>,
_id: Id<'gc>,
}
impl<'gc, T> ArenaCtx<'gc, T> {
// 새 값을 할당하고 `Gc` 인덱스를 반환.
fn alloc(&mut self, value: T) -> Gc<'gc> { ... }
// 인덱스로 값에 접근. 여기로 전달되는 어떤 `Gc`도 branding `Id` 덕분에
// 반드시 *같은* 인스턴스의 `ArenaCtx::alloc`에서 반환된 것임이 확실하다!
// panic을 일으키는 방식으로 사용할 수 없도록 컴파일 시점에 보장할 수
// 있어야 한다!
fn get(&self, gc: Gc<'gc>) -> &T { ... }
fn get_mut(&mut self, gc: Gc<'gc>) -> &mut T { ... }
}
이건 실제로 동작합니다. 다만 실전에서는 좀 미완성처럼 느껴집니다. 가장 큰 문제는 전체 설계가 Gc<'gc> 인덱스가 Arena::enter 호출 바깥으로 탈출하지 못하게 만든다는 점입니다. 검사된 인덱싱 예제와 마찬가지로, 정확성을 보장하는 branding Id 타입이 바로 Arena::enter에 의해 정의되기 때문입니다. 그런데 Arena::enter 안팎으로 아무것도 넣거나 뺄 수 없다면, 각 호출은 완전히 독립적이 되어 버리고, 우리가 원하는 만큼 유용하지 않습니다.
또 다른 문제는 T 타입입니다. 구체적인 T 타입은 바깥에서 정하는데, 예를 들어 아까 연결 리스트 예시에 이걸 사용하고 싶다고 해 봅시다...
// `Gc` 인덱스를 담는 연결 리스트 노드.
struct Node<'gc> {
next: Cell<Option<Gc<'gc>>>,
value: String,
}
// 이런 식의 `Arena`를 실제로는 만들 수 없다. `Arena`는 `Gc` 포인터를 담는
// 어떤 것도 할당할 수 없기 때문이다. 그 `Gc` 포인터들은 모두 “brand”가
// 찍혀 있어야 하고, 그 branding은 `Arena::enter`에서 오지만, 우리는 아직
// 그 안에 들어가지 않았다. 결국 `Gc` 인덱스를 전혀 담지 않는 값만 할당할 수
// 있는데, 그건 별로 유용하지 않다!
type NodeArena = Arena<Node<'_>>;
지금 상태로는 정말로 안 됩니다. 우리가 고르는 T는 어떤 Gc 값도 가질 수 없기 때문입니다. 이 문제에 해법이 있을까요?
두 번째 문제부터 먼저 해결해 봅시다. somehow 'static 버전의 Node, 이를테면 ArenaNode 같은 것을 만들고, 이 타입이 branding lifetime 'gc에 맞는 Node<'gc>를 생산 할 수 있다면, 적어도 Arena<T>의 T가 무엇인지 정의할 수는 있습니다. 특정 concrete type 하나에 대한 코드만 쓰고 싶지는 않으니, 이를 위한 trait을 만들고, 다행히 GAT(Generic Associated Types)을 사용해서 이 non-'static 타입을 “생산”할 수 있습니다.
// `Arena`가 저장할 어떤 타입이든 이것을 구현해야 한다.
trait ArenaType {
// GAT를 사용할 수 있다! 올바른 brand를 가진 타입을 참조해야 할 일이
// 생기면, 이 associated type을 참조하고 원하는 brand lifetime을 넣으면
// 된다.
type Value<'gc>;
}
이제 위의 Arena 타입을 이 새 trait을 사용하도록 바꿔 봅시다.
type Id<'gc> = ...;
struct Gc<'gc> { ... }
// 이제는 `T` 타입 파라미터 대신, `A: ArenaType`을 받는다는 것을 안다.
struct Arena<A: ArenaType> {
ctx: ArenaCtx<'static, A>,
}
struct ArenaCtx<'gc, A: ArenaType> {
slots: Vec<Option<A::Value<'gc>>>,
free_list: Vec<usize>,
_id: Id<'gc>,
}
// 그다음 모든 메서드를 그냥 `A`를 받도록 바꾸면 된다. 이건 실제로 될 것
// 같다!
impl<A: ArenaType> Arena<A> {
fn enter<F, R>(&mut self, f: F) -> R
where F: for<'gc> FnOnce(&mut ArenaCtx<'gc, A>) -> R
{
f(&mut self.ctx)
}
}
impl<'gc, A: ArenaType> ArenaCtx<'gc, A> {
fn alloc(&mut self, value: A::Value<'gc>) -> Gc<'gc> { ... }
fn get(&self, gc: Gc<'gc>) -> &A::Value<'gc> { ... }
fn get_mut(&mut self, gc: Gc<'gc>) -> &mut A::Value<'gc> { ... }
}
그리고 약간의 boilerplate는 필요하지만, 이제 Node<'gc> 타입에 이것을 쓸 수 있을 것 같습니다.
struct Node<'gc> { ... }
// `ArenaType`을 구현하는 대리 타입으로 빈 타입을 하나 사용하자. 귀엽게
// `Node<'static>`에 직접 `ArenaType`을 구현해도 되지만, 이쪽이 좀 더
// 명확하다.
struct ArenaNode;
impl ArenaType for ArenaNode {
// 마법! 이제 실제 `Node<'gc>` 타입을 생산할 수 있다.
type Value<'gc> = Node<'gc>;
}
// 이제 드디어 노드용 arena 타입을 정의할 수 있다!
type ArenaOfNodes = Arena<ArenaNode>;
이건 실제로 됩니다! 이제 적어도 Arena::enter 본문 안에서는 Arena를 사용해 노드를 할당할 수 있고, 그 타입들 안에 branding된 Id가 들어 있는 경우도 완전히 할당할 수 있습니다.
흥미로운 점은 Arena의 slots 타입에 그냥 'static을 써도 모든 것이 잘 돌아간다는 사실입니다. 검사된 인덱싱 시스템이 적절한 for<'gc> callback 경계만 있으면 Id에 대해 어떤 실제 lifetime 이든 사용할 수 있다는 점이 큰 도움이 됩니다.
이제 Arena::enter 바깥에 값을 가리키는 어떤 포인터를 저장하는 문제를 해결해야 합니다. 그렇지 않으면 arena는 여전히 별로 유용하지 않습니다. 하지만 희망적인 단서는 있습니다. 이제 우리는 arena “안쪽” 타입(Node<'gc>)을 'static인 것(ArenaNode)으로 지칭 할 수 있게 되었기 때문입니다.
사실 Gc<'gc> 타입에서 의미 있는 부분은 오직 index뿐입니다. 그럼 그냥 Gc에서 raw index를 꺼내고, raw index로부터 Gc를 다시 만드는 방법을 제공하면 되지 않을까요?
impl<'gc, A: ArenaType> ArenaCtx<'gc, A> {
fn alloc(&mut self, value: A::Value<'gc>) -> Gc<'gc> { ... }
fn get(&self, gc: Gc<'gc>) -> &A::Value<'gc> { ... }
fn get_mut(&mut self, gc: Gc<'gc>) -> &mut A::Value<'gc> { ... }
// brand가 찍힌 `Gc` 인덱스에서 일반 인덱스를 꺼낸다.
fn gc_to_index(self, gc: Gc<'gc>) -> usize { ... }
// 일반 인덱스를 다시 brand가 찍힌 `Gc` 인덱스로 바꾼다.
//
// `index`가 유효하게 할당된 값을 가리키지 않으면 `None`을 반환한다.
fn index_to_gc(self, index: usize) -> Option<Gc<'gc>> { ... }
}
이건 실제로 됩니다! 이제 이것을 어떻게 사용해 마침내 연결 리스트를 만드는지 봅시다...
struct Node<'gc> { ... }
impl ArenaType for ArenaNode { ... }
impl<'gc> Node<'gc> {
fn new(value: String) -> Self { ... }
fn next(&self) -> Option<Gc<'gc>> { ... }
fn set_next(&self, next: Option<Gc<'gc>>) { ... }
}
// 이렇게 사용할 수 있다...
let arena = Arena::<ArenaNode>::new();
// `a` 노드에 대한 “root” 값을 하나 정한다.
let a_root: usize = arena.enter(|ctx| {
let a = ctx.alloc(Node::new("1".to_owned()));
let b = ctx.alloc(Node::new("2".to_owned()));
let c = ctx.alloc(Node::new("3".to_owned()));
a.set_next(Some(b));
b.set_next(Some(c));
c.set_next(Some(a));
ctx.gc_to_index(a)
});
// 이제 arena를 빠져나온 뒤에도 다시 들어가서 `root`를 되살릴 수 있다!
arena.enter(|ctx| {
let a = ctx.index_to_gc(a_root).unwrap();
let b = a.next().unwrap();
let c = b.next().unwrap();
});
다시 평범한 usize 인덱스를 들고 다녀야 한다는 점은 조금 우울하지만, 적어도 내부 구조에는 실패 가능한 인덱스가 없습니다! 특히 arena 바깥에서 필요한 “root” 수가 상대적으로 적다면, 예를 들어 그래프의 루트 노드가 하나뿐인 경우라면, 이건 꽤 큰 개선입니다.
아직 끝난 것은 아니지만 거의 다 왔습니다. 이것을 완성하려면 딱 한 가지 가 더 필요합니다. 바로 실제 트레이싱 가비지 컬렉션입니다!
우리가 바깥에서 Arena에 대해 하고 싶은 일은 대략 이런 것입니다...
impl<A: ArenaType> Arena<A> {
// 마법처럼 somehow, 도달 불가능한 모든 값을 제거한다.
//
// 무엇을 도달 가능하다고 볼 것인가? 그건 우리가 *root set*을 어떻게
// 정하느냐에 달려 있다. 그리고 우리가 원하는 것은 이 root set으로부터
// 도달할 수 없는 모든 것을 제거하는 것이다. 그냥 모든 root를 넘기자!
fn collect(&mut self, roots: impl IntoIterator<Item = usize>) { ... }
}
꽤 단순한 API죠! 이걸 하려면 당연히 저장된 값들에 대해 무언가 알아야 합니다. 그렇지 않으면 Arena가 어떻게 a에서 b에 도달하고 b에서 c에 도달한다는 걸 알겠습니까? 이를 위해 ArenaType trait에 메서드 하나를 추가하고, 보조 trait 하나를 새로 만들겠습니다.
// 저장된 `Gc` 포인터를 추적하기 위한 보조 trait
trait Visitor<'gc> {
fn visit(&mut self, gc: Gc<'gc>);
}
trait ArenaType {
type Value<'gc>;
// 이 메서드 구현은 보유 중인 모든 `Gc<'gc>` 포인터를 방문해서
// `visitor.visit(gc)`를 호출해야 한다.
fn trace<'gc, V: Visitor<'gc>>(this: Self::Value<'gc>, visitor: &mut V);
}
이제 남은 조각들의 간단한 개요를 보겠습니다...
impl ArenaType for ArenaNode {
type Value<'gc> = Node<'gc>;
fn trace<'gc, V: Visitor<'gc>>(this: Node<'gc>, trace: &mut V) {
// 우리 사용자 코드는 이것만 하면 된다!
if let Some(next) = self.next.get() {
visitor.visit(next);
}
}
}
impl<A: ArenaType> Arena<A> {
...
fn collect(&mut self, roots: impl IntoIterator<Item = usize>) {
let queue: Vec<usize> = roots.into_iter().collect();
let visited: HashSet<usize> = HashSet::new();
// 자세한 구현은 여기서 일일이 따라가진 않겠다. 우리가 하는 일은 아주
// 표준적인 “mark-and-sweep”이기 때문이다. `roots` 집합에서 시작해서
// 각각에 대해 `A::trace`를 호출한다. 이를 위해 `Visitor` 보조 trait
// 구현이 필요하고, 그 구현은 `A::trace`가 방문한 모든 `Gc`를 `queue`에
// push해야 한다.
//
// `Gc`가 방문될 때마다 그 인덱스를 `visited` 집합에 넣는다.
//
// 마지막으로 `visited` 집합에 *없 는* 모든 노드를 “해제”해서 값을
// `None`으로 만들고, 그 인덱스를 free list에 넣는다. 그러면 끝!
}
}
후우, 이번엔 정말 여기까지입니다! 안전한 코드만으로 만들 수 있는 원시적이지만 (그래도 완전한!) 트레이싱 가비지 컬렉션을 만들었습니다.
이제 남은 잘못될 수 있는 부분은 세 가지입니다...
usize 인덱스라서 서로 섞이거나 잘못 저장될 수 있다.ArenaType::trace 메서드가 올바르게 구현되었다는 가정하에 Gc<'gc> 인덱스 접근이 panic을 일으키는 것은 불가능해야 한다.하지만 이건 정말, 정말로 괜찮은 무언가에 굉장히 가까워졌습니다! 이 절에서 한 일은 최소 기능을 갖춘 gc-arena 스타일 가비지 컬렉션 인터페이스 의 핵심 부품을 전부 만드는 것이었습니다. 이런 스타일의 GC 핵심 아이디어를 이해하는 데 필요한 거의 모든 조각이 정말 여기 다 들어 있습니다... 단 하나의 새로운 꼬임만 빼고요.
Gc<'gc>에 포인터를 저장하면 어떨까요?
이제 설계를 몇 군데만 더 바꾸면, 적어도 바깥에서 보기에 는 gc-arena 같은 수집기와 거의 기능 대등한 곳까지 갈 수 있습니다.
이제부터는 세부사항이 더 지저분하고, 내부 구현도 그렇게 중요하지 않기 때문에 설명 속도가 조금 빨라집니다.
우선, root가 평범한 usize라는 점도 별로고, Arena::collect를 호출할 때마다 root를 직접 기억해서 넘겨야 한다는 점도 별로입니다. 이건 사실 handle type 을 사용하면 꽤 쉽게 해결됩니다.
struct ArenaRoots<A: ArenaType> {
roots: Vec<Weak<InnerRoot<A>>>,
}
// `usize` 대신 `Arc`를 감싼 무언가를 나눠 주자. 그러면 `Arena::collect`에서
// root를 일일이 나열할 필요 없이 순회할 수 있고, 동시에 `InnerRoot`에
// 식별자 데이터를 넣어서 잘못된 `Arena`와 함께 `Root`가 사용되면 런타임에
// panic하게 만들 수도 있다.
struct Root<A: ArenaType>(Arc<InnerRoot<A>>);
impl<A: ArenaType> Arena<A> {
...
// 더는 root를 명시적으로 나열할 필요가 없다!
fn collect(&mut self) { ... }
}
impl<'gc, A: ArenaType> ArenaCtx<'gc, A> {
...
fn gc_to_root(self, gc: Gc<'gc>) -> Root<A> { ... }
// 주어진 `root`가 같은 *Arena* 의 `gc_to_root`에서 만들어진 것이 아니면
// panic한다. 다만 다른 `Arena::enter` 호출에서 만들어진 것은 괜찮다!
fn root_to_gc(self, root: &Root<A>) -> Option<Gc<'gc>> { ... }
}
이건 실제로 꽤 쉽고, 우리가 나열한 부정확성 원천 중 적어도 하나를 해결합니다. 안타깝게도 정확한 root가 정확한 arena와 함께 사용된다는 것을 정적으로 보장할 현실적인 방법은 없습니다. 그래도 충분히 가치 있습니다! 이런 종류의 가비지 컬렉션 시스템을 실제로 다뤄 보면, 외부 포인터보다 내부 포인터가 훨씬 더 많고, 심지어 엄청나게 많은 내부 값에 대해 외부 root가 하나뿐 인 경우도 흔합니다.
사용성 측면에서 남은 가장 큰 문제는 여전히 단일 타입 T만 할당할 수 있다는 점입니다. 하지만 이것 역시 완전히, 심지어 안전하게도 해결 가능합니다!
Rust에서 가비지 컬렉션을 안전하게 구현하는 방법에 관한 fitzgen의 정말 훌륭한 blog post를 꼭 읽어 보세요. 그의 설계는 대체로 우리가 지금까지 개요를 그린 설계의 훨씬 더 나은 버전이며, 여러 할당 타입을 지원하고 generativity 트릭은 사용하지 않습니다. 완전히 안전한 tracing GC가 가능하다는 것을 실제로 구조적으로 증명한 사람이 바로 그입니다.
하지만 우리는 raw index를 사용한 다형 타입 할당을 설명하려 하지는 않을 겁니다. 대신 지금까지 설계에 가장 큰 변화를 줘 보겠습니다. 사실 그동안 이렇게 돌아온 진짜 이유를 설명해 주는 변화이기도 합니다. Gc<'gc>를 인덱스 에서 포인터 로 바꾸겠습니다. 새 Gc 타입은 이렇게 생깁니다...
// raw pointer를 감싼 단순한 투명 래퍼.
#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
ptr: NonNull<T>,
_id: Id<'gc>,
}
그리고 (Arena가 어떻게 여러 타입을 할당하는지는 자세히 설명하지 않고) 여러 타입을 할당할 수 있게 하겠습니다. 이 변경 후 전체 API의 개요를 한 번에 봅시다. ArenaType trait에도 몇 가지 곁다리 변경이 필요합니다.
// branding type.
type Id<'gc> = ...;
// raw pointer를 감싼 단순한 투명 래퍼.
#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
ptr: NonNull<T>,
_id: Id<'gc>,
}
// tracing을 위한 보조 trait.
trait Visitor<'gc> {
fn visit<T: Trace>(&mut self, gc: Gc<'gc, T>);
}
// 새 trait! 이것은 원래 `ArenaType` trait의 `trace` 메서드와 정확히 같지만,
// 이제 `Arena`가 내부적으로 여러 타입을 저장하므로 분리되어야 한다.
//
// 그리고 이것은 *unsafe* 하다! 이제 raw pointer를 다루기 때문에, 이 메서드가
// 보유 중인 포인터 하나라도 *놓치면* 수집 시 그것을 삭제해 버리고 dangling이
// 되게 만들기 때문이다!
unsafe trait Trace<'gc> {
fn trace<V: Visitor<'gc>>(this: Self::Value<'gc>, visitor: &mut V);
}
// 이 trait은 다시, 주어진 `'gc` lifetime에 대한 `Value`를 생산하는 방법으로만
// 돌아간다.
trait ArenaType {
// arena가 저장하는 실제 값, 어떤 'gc lifetime이든.
type Value<'gc>: Trace<'gc>;
}
// 어떤 `Arena` 안으로 들어가는 “root” handle. bare type에 'gc lifetime을 붙인
// 것이 아니라 `ArenaType` projection type을 써야 한다는 점에 주목.
struct Root<A: ArenaType> { ... }
// 이제 `Arena`는 무타입이다! 안에서 어떤 타입이든 할당할 수 있다. 내부 저장이
// 어떻게 생겼는지는 *건너뛴다*. 전체 예시를 보고 싶다면 `gc-arena` 내부 구현을
// 참고하면 된다.
struct Arena {
ctx: ArenaCtx<'static>,
}
struct ArenaCtx<'gc> {
...
_id: Id<'gc>,
}
impl Arena {
fn enter<F, R>(&mut self, f: F) -> R
where F: for<'gc> FnOnce(&mut ArenaCtx<'gc>) -> R
{ ... }
}
impl<'gc> ArenaCtx<'gc> {
// 아까 함수들의 typed variant...
// `alloc`은 `&mut self` 대신 `&self`를 받도록 바꿨다. 이제 unsafe를 쓰고
// 있으므로 내부적으로 가변인 allocator(혹은 그냥 시스템 allocator)를
// 사용하는 것이 큰 문제가 아니기 때문이다.
//
// 또한 `Send` bound를 추가했다. 그 이유는 곧 설명한다.
fn alloc<T: Trace + Send>(&self, value: T) -> Gc<'gc, T> { ... }
// 지금까지 컴파일 시점 안전성을 위해 쌓아 온 모든 작업 덕분에,
// `ArenaCtx::get`와 `ArenaCtx::get_mut`는 *검사 없는 raw pointer deref*
// 로 구현될 수 있어야 한다.
//
// branding 시스템과 다른 건전성 논리가 제대로 작동한다고 믿어야 하지만,
// 그렇다면 `Gc`는 *`&T`보다 더 비싸지 않다*. 이건 정말 엄청나게 멋지다!
fn get<T>(&self, gc: Gc<'gc, T>) -> &T { ... }
fn get_mut<T>(&mut self, gc: Gc<'gc, T>) -> &mut T { ... }
// 이 메서드들은 이제 좀 더 기묘하다. `gc_to_root`를 호출할 때는 언제나
// 어떤 *projection* 타입 `A`를 직접 적어 주어야, `T`의 “lifetimeless”한
// 버전을 얻을 수 있다.
fn gc_to_root<A: ArenaType>(self, gc: Gc<'gc, A::Value<'gc>>) -> Root<A> { ... }
fn root_to_gc<A: ArenaType>(self, root: &Root<A>) -> Option<Gc<'gc, A::Value<'gc>>> { ... }
}
후우! 이것이 드디어 branded pointer GC인 gc-arena 스타일 실제 설계의 핵심입니다.
사실 실제
gc-arena설계는 이것보다 더 복잡하기도 하고, 또 완전히 이렇게 좋지는 않기도 합니다.gc-arena는 ergonomic을 위해 약간 다른 트레이드오프를 하고, incremental collection을 지원하기 때문에 write barrier 같은 추가 복잡성이 많이 들어갑니다.
gc-arena가 raw pointer를 가능한 한 최대한 사용하려는 목표를 갖고 있지 않았다면, 굳이 “generativity”로 우회할 필요도 없었을 것입니다. raw pointer를 사용한 이 설계가 동작할 수 있게 만드는 진짜 핵심은, “generativity”를 사용해 포인터 접근의 거의 전부 를 증명 가능하게 안전하게 만드는 이 아이디어입니다.
이 설계는 현재 gc-arena 설계보다 약간 더 낫기까지 합니다. 아주 섬뜩해 보일 수 있는 일을 하나 해 보죠. 하지만 정말 sound합니다.
// raw pointer를 감싼 단순한 투명 래퍼.
#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
ptr: NonNull<T>,
_id: Id<'gc>,
}
// 좋아, `T`에 아무 *bound* 도 없는데 어떻게 sound할 수 있지?
//
// 음, 우리의 API는 원래 `Gc`가 단순한 *인덱스* 였던 다른 설계에서 물려받은
// 것이다. `Gc`가 포인터를 저장하게 바뀐 뒤에도 `ops::Deref` 같은 것은 전혀
// 추가하지 않았다는 점에 주목하자!
//
// 우리는 여전히 `Gc` 값을 인덱스를 쓰듯이 사용하고 있다. `usize` 인덱스는
// Vec에 인덱싱하기 전까지는 그 자체로 할 수 있는 일이 없기 때문에 `Send`와
// `Sync`가 될 수 있는데, 보기엔 수상해도 여기서도 똑같은 논리가 적용된다!
//
// `Gc`는 `ArenaCtx::get` 같은 것을 호출하기 전까지는 완전히 inert하다. 그러니
// `Arena`와 `ArenaCtx`로 무엇을 할 수 있는지만 제대로 통제하면 `Gc`를 안전하게
// `Send`와 `Sync`로 만들 수 있다!
unsafe impl<'gc, T> Send for Gc<'gc, T> {}
unsafe impl<'gc, T> Sync for Gc<'gc, T> {}
이제 이것을 연결 리스트 예제에 사용해서 왜 이게 멋진 기능인지 보여 줍시다.[23]현재 gc-arena에는 사실 없는 기능입니다. 또한 gc-arena에서 가져온 다른 기능도 하나 보여 주겠습니다. 자세한 설명은 생략하지만, Trace는 구현이 워낙 기계적인 trait이라 proc-macro로 자동 구현할 수 있어서, 사용자에게 더는 어떤 unsafe 코드도 쓰게 하지 않아도 됩니다!
// `Trace`를 자동으로 derive하는 proc-macro를 만들 수 있다! `Option`이나
// `Cell` 같은 표준 타입이 `Trace`를 구현하고 있기만 하면, `Clone`이나
// `Serialize` 같은 trait의 자동 구현과 같은 전략을 사용할 수 있어 unsafe
// 코드를 전혀 작성하지 않아도 된다!
#[derive(Trace)]
struct Node<'gc> {
next: Cell<Option<Gc<'gc, Node<'gc>>>>,
value: String,
}
struct ArenaNode;
impl ArenaType for ArenaNode {
type Value<'gc> = Node<'gc>;
}
impl<'gc> Node<'gc> {
fn new(value: String) -> Self { ... }
fn next(&self) -> Option<Gc<'gc, Node<'gc>>> { ... }
fn set_next(&self, next: Option<Gc<'gc, Node<'gc>>>) { ... }
}
let arena = Arena::new();
// 예전처럼 값을 arena에 넣을 수 있다...
let a_root: usize = arena.enter(|ctx| {
let a = ctx.alloc(Node::new("1".to_owned()));
let b = ctx.alloc(Node::new("2".to_owned()));
let c = ctx.alloc(Node::new("3".to_owned()));
a.set_next(Some(b));
b.set_next(Some(c));
c.set_next(Some(a));
// `a`에 대한 root를 만들 수 있지만, 안타깝게도 projection type을 직접
// 적어 주어야 한다.
ctx.gc_to_root::<ArenaNode>(a)
});
이제 우리는 둘 다 'static인 arena와 a_root를 갖게 되었습니다. 원할 때마다 arena 안으로 “enter”해서 저장해 둔 non-'static 실제 Node<'gc> 값들을 다시 꺼낼 수 있지만, “나오고” 나면 손에 남는 타입은 전부 'static입니다! 순환 포인터 네트워크 전체를 통째로 이동할 수 있게 된 것이죠. 멋지지 않나요?
그런데 이 설계에서 더 좋은 점이 뭔지 아십니까? Arena와 Root 둘 다 Send를 구현할 수 있다는 것입니다!
바로 이것 때문에 우리는 Gc가 Send가 되도록 그렇게 애썼던 겁니다... Cell은 Send, Option은 Send, Gc도 Send이므로 Node 값도 Send입니다! 그래서 ArenaCtx::alloc의 T: Trace + Send에 그 추가 Send bound를 반드시 넣어야 하는 것이기도 합니다. Arena의 내부 저장 구조가 실제로 어떻게 생겼는지는 말하지 않았지만, Arena 자체도 Send라면 내부적으로는 Box<dyn Trace + Send> 비슷한 것을 들고 있어야 하므로, 그 bound가 꼭 필요합니다.
이것이 이 전체 설계의 진짜 논리이고, 여기서 한 조각만 빼도 모든 것이 무너집니다. Gc가 Deref를 구현하게 만들면, T가 Sync가 아니면 Gc는 Send를 구현할 수 없게 됩니다. 그런데 Node 같은 T는 Cell을 담고 있으므로 Sync일 수 없습니다. 그래서 Gc는 “인덱스”처럼 행동해야 합니다. 그래야 Arena라는 “감옥” 안에 Sync가 아니라 Send만인 것들을 가둘 수 있습니다.
아까 raw 순환 참조로 시도했던 것을 기억하시나요? 이건 움직이는 부품이 훨씬 많기는 해도, 근본적으로 그것보다 더 강력한 설계입니다. 사실 이것은 일종의 별도의, 더 기묘한 self-borrowing처럼 보이기까지 합니다. 다른 self-borrowing 해법들처럼 모든 것이 “정지 상태에서는 'static인” 상자 안에 들어가 있지만, 그보다 더 나아가, 전염성 있는 !Send 없이도 안전한 포인터 네트워크(참조 같은 것)를 가질 수 있는 방법입니다.
이건 정말 유용하고, Rust 세계 안에서도 이런 힘을 주는 방식은 꽤 독특합니다!
제가 설명한 이 설계는 아주 멋진 패턴이지만, 여기까지 오기 위해 거쳐야 하는 단계들이 정말 너무 이상해서 예전에는 이것을 제가 생각하는 올바른 방식 으로 설명하기가 늘 어려웠습니다.
이번에는 다른 접근을 시도해 봤습니다. Rust가 본래 잘하는 것, 즉 Vec와 인덱스에서 출발 해서, 거기서부터 빠른 포인터에 기반한 자기 참조 네트워크 전체로 이동하는 설계를 설명하려고 한 것입니다.
정말로 gc-arena 스타일 GC 설계란 결국
“Vec + indexing” + “tracing GC” + “checked indexing”
그 이상도 이하도 아닙니다.
정적으로 검증된 인덱스는 거의 안전한 포인터와 같습니다. 차이는 포인터 오프셋이 없다는 것뿐입니다!
Rust 전반에 깔린 다른 문제들 중에도, 최소한 형태상 gc-arena와 같은 모양 의 해법을 가질 수 있는 것들이 있습니다. 예를 들어 우리의 연결 리스트가 순환이 아니고 Gc 대신 Rc를 쓸 수 있다고 합시다... Rust는 Rc 네트워크를 스레드 간에 보낼 수 없다 는 걸 알고 있는데, 흥미롭게도 Gc 네트워크는 apparently 보낼 수 있습니다?
어떤 값들의 집합을 “감옥”에 가두고, 감옥 밖으로 나와서도 감옥 전체만 한 번에 이동할 수 있다는 것만 보장되면 sound한 작업을 할 수 있게 만드는 아이디어는, 실현하기는 다소 어렵지만 매우 매력적인 Rust의 특성처럼 보입니다.
제가 gc-arena를 시작했을 때는 몹시 원대한, 꽤나 오만한 목표가 있었습니다. Rust와 가비지 컬렉션의 통합 문제를 해결 할 수 있기를 바랐던 것이죠. 하지만 이제는 그렇게 하지 못했다는 생각이 듭니다. gc-arena 스타일 설계의 큰 한계 때문입니다. Arena::enter 같은 메서드 안에서는 어떤 가비지 컬렉션도 일어날 수 없다는 점 말입니다.
예전에는 이걸 사실상 이 접근을 극도로 틈새적인 것으로 만드는 제약이라고 생각했지만, 지금은 꼭 그렇게까지는 아니라고 생각합니다.[24]모든 문제에 맞는 것은 여전히 아닙니다. 코드가 무기한 실행되게 하면서도 이런 스타일의 GC를 유지하는 런타임을 구현하는 건 상당히 어렵습니다.
아무 “systems programmer”나 한 명 붙잡고 프로그램에 GC를 추가하는 것에 대해 어떻게 생각하는지 물어보면, 거의 틀림없이 이런 표정을 지을 겁니다:
୧(๑•̀ᗝ•́)૭
그다음 프로그램 안에 GC가 천 개 있었으면 좋겠냐고 물어보면, 저는 아마 대부분이 더 나쁘게 반응할 거라고 장담 합니다! 가비지 컬렉터 하나도 싫은데, 천 개면 천 배는 더 나빠야 한다고 느끼겠죠!
제 생각에 이건 근본적으로 잘못된 직관입니다. Rust의 가비지 컬렉터 해법들 중 많은 것들(하지만 전부는 아닙니다! safe-gc를 보고 있습니다)은 가비지 컬렉션 언어 에서 볼 수 있는 종류의 수집기처럼 동작하는 컬렉터를 만들려 합니다. 즉, 한 번에 전체 프로세스에 작동하거나, 적어도 시스템 Thread 전체에 작동하는 종류죠.[25]매끄럽게 통합된
근본적으로, tracing GC는 GC 문헌에서 말하듯이 live set 크기에 비례하는 런타임을 가질 수밖에 없습니다. 완전히 incremental한 GC라면 괜찮을 수도 있지만, 어떤 세대를 스캔하기 위해 stop-the-world가 필요한 모든 GC는(그리고 이것은 최첨단 generational GC 대부분에 해당합니다) 그 세대의 live set 크기에 비례하는 비용을 반드시 치르게 됩니다.
그런데 tail latency가 매우 낮은 것으로 유명한 언어가 뭔지 아십니까? Erlang 입니다. 그리고 그 주된 이유 중 하나는, GC가 하나 가 아니라 여러 개, Erlang 프로세스마다 하나씩 따로 있다는 점입니다경량이고 엄격히 격리된 thread 같은 것입니다. 어떤 프로세스가 힙을 많이 사용하더라도, 그것이 다른 프로세스를 방해하지 않으므로 P99 pause time이 아주 낮게 유지됩니다.
사람들은 흔히 시스템 프로그래밍 언어를 “GC가 없다”는 말로 구분하지만, 저는 그게 완전히, 철저히 거꾸로라고 생각합니다. GC는 어디에나 있습니다. Rc + Drop이 GC냐 아니냐 논쟁을 어떻게 보든 간에, 심지어 tracing GC조차도 the Linux kernel 안에도 있습니다.
여기서 아주 이상하고, 어쩌면 논쟁적인 말을 하나 하겠습니다:
시스템 프로그래밍 언어란, 동시에 얼마든지 많은 가비지 컬렉터를 둘 수 있는 언어다.
저는 안전한 가비지 컬렉션 인터페이스가 일반적인 안전한 순환 포인터 표현과 잠재적으로 떼려야 뗄 수 없이 얽혀 있다고 생각합니다. 그리고 제 꿈의 시스템 프로그래밍 언어는, (안전하게!) 원할 때마다 a la carte 로 GC를 통합할 수 있어야 한다고 생각합니다. 또한 GC는 시스템 프로그래밍에 있어 일종의 빠져 있는 자료 구조 라고도 생각합니다.
우리가 보여 준 것처럼 이것은 오늘날 Rust에서도 가능하지만, 당연히 그 이점을 얻기까지는 여전히 꽤 많은 고통이 따릅니다. 하지만 때로는 증명 가능한 안전성이 정말로 그 고통의 값을 합니다.
tracing GC 오류는 여러분이 겪게 될 가장 나쁜 종류의 UB 버그들 가운데 하나입니다. 흔히 잘못해서 도달 불가능하다고 판단된 객체나 누락된 “barrier”[27]여기서는 다루지 않은, gc-arena처럼 concurrent 한 GC를 가지는 복잡성의 일부입니다. 와 관련되고, 크래시는 진짜 논리적 버그가 있는 곳과 공간적으로도 시간적으로도 완전히 동떨어진 지점에서, 심지어 다음 GC 사이클 전체가 돌 때까지도 나타나지 않을 수 있습니다.
저는 (gc-arena 자체를 개발하는 경우를 제외하면, 이것은 정말 사실입니다) gc-arena를 사용하면서 GC 버그를 겪어 본 적이 한 번도 없습니다. 저는 Ruffle 핵심 개발자 중 한 명에게도 이 점을 물어봤는데, 그들의 판단으로는 Ruffle 전체 역사에서 이런 경우가 세 번 정도 있었던 것 같습니다[28]혹은, 그들이 찾아낼 수 있었던 만큼은요 . 하나는 gc-arena가 과도한 정렬이 필요한 구조체를 제대로 할당하지 못했던 경우였고(이건 가비지 컬렉션과는 아무 상관이 없습니다), 나머지 두 경우는 누락된 필드를 가진 오래된 unsafe impl Collect {}[29]gc-arena에서 Trace trait에 해당하는 이름이 Collect입니다. 였습니다. 물론 마지막 두 경우도 잠재적으로 심각하고 디버깅하기 어렵지만, 요점은 gc-arena에서 Collect를 수동 구현해야 하는 일 자체가 정말 드물다 는 것이고, 바로 그 점 때문에 Ruffle은 그렇지 않았을 때보다 훨씬 적은 엔지니어링 노력으로 추적을 마칠 수 있었다는 것입니다!
시스템 프로그래밍 언어에 안전한 가비지 컬렉션을 통합할 수 있다는 건 다른 이점도 있습니다. 예를 들어 Fields of Mistria에서 fabricator VM은 이미 GMS2보다 충분히 빠르지만, 사실 그것이 NPC Studio에 생사가 걸린 문제는 아닙니다. 진짜 큰 점은 Rust 코드가 fabricator 값의 내부 자료 구조 전체에 직접 그리고 안전하게 접근할 수 있고, 동시에 그 자체가 안전하게 가비지 컬렉션되는 값을 직접 생성할 수도 있다는 것입니다! 이 말은 곧, 어느 순간에도 스크립트 코드 안에 갇히지 않는다 는 뜻입니다. 거의 모든 스크립트 코드를 Rust로 대체할 수 있고, 작은 내부 루프 수준에 이르기까지(물론 Rust 호출 오버헤드는 본질적으로 남지만, 꽤 낮습니다!) GML 일부를 Rust로 다시 쓰면 언제나 더 빨라질 것입니다. 이런 건 스크립트 언어 FFI 경계에서는 꽤 드문 일입니다!
제가 여러분더러 당장 나가서 제 크레이트를 쓰라고 설득하려는 것은 아닙니다. 이 글은 광고가 아닙니다.[30]그리고 솔직히 말하면, 저는 crate maintainer로서 꽤 형편없는 편입니다.
제가 여기서 하려고 한 것은, 제가 왜 Rust의 이렇게 미친 구석에 있게 되었는지, 어떻게 여기까지 왔는지, 왜 여기에 있을 필요가 있었는지, 그리고 이 구석이 사실 충분히 탐험되지 않았다고 생각하는 이유를 설명하는 것이었습니다. 제 발표가 누군가에게 이 분야에 대한 흥미를 불러일으켜서, 저보다 더 잘 이 설계를 바탕으로 가비지 컬렉션 라이브러리를 쓰게 만들고, 그 사람이 실제로 그렇게 한다면, 저는 그 라이브러리를 기쁘게 사용하고 정말로 너무나 행복할 것입니다.
Rust 안에도, 그리고 솔직히 모든 시스템 프로그래밍 전반에도, 더 쉽게 통합 가능한 “그저 좀 화려한 자료 구조로서의 GC”를 위한 자리가 있다고 생각합니다. 그래야 올바른 작업에 올바른 알고리즘을 고를 수 있고, 누군가가 이미 내려 버린 전역적인 시스템 결정 과 씨름하지 않아도 됩니다. 저는 이것이야말로 시스템 프로그래밍의 본질 같은 것이라고 생각합니다!
읽어 주셔서 감사합니다!