safe-gc

Rust-крейт, реализующий кучу со сборкой мусора без единой строчки unsafe-кода - ни в публичном API, ни внутри. Написан Ником Фицджеральдом (Wasmtime, Cranelift) в качестве доказательства того, что продуманное проектирование API способно заменить unsafe даже в области, которая исторически считалась одним из последних его убежищ.

Как это устроено

Куча устроена как HashMap<TypeId, Box<dyn ArenaObject>>, по одной арене на каждый конкретный тип. Каждая арена - это Vec слотов плюс free list. Ссылки бывают двух видов:

• Gc<T> - Copy, дешёвый, не создаёт корень. Безопасен в коде, который не запускает сборку мусора.
• Root<T> - закреплённый корень, не Copy, Drop убирает корень. Необходим для ссылок, удерживаемых во время аллокаций.

Разыменовать (deref) ни один из этих типов напрямую нельзя. Чтобы прочитать объект, к нему обращаются через индексацию самой кучи:

let h: Heap = Heap::new();
let r: Root<Foo> = h.alloc(Foo { ... });
let v: &Foo = &h[&r];

В этом и заключается вся гарантия безопасности. Поскольку доступ идёт через Index/IndexMut к куче, время жизни возвращаемой ссылки привязано к заимствованию самой кучи - здесь работают стандартные правила Rust, и для их выражения unsafe не нужен.

Сборщик реализован по алгоритму mark-and-sweep. Фицджеральд сначала попытался сделать копирующий сборщик, но бросил эту затею: обновление forwarding-указателей не удавалось выразить либо без unsafe, либо без конфликтов заимствования, которые он не смог разрешить в гетерогенной куче. Mark-and-sweep сложился примерно за полчаса, поскольку в нём ничего не нужно перемещать.

Базовый пример

use safe_gc::{Heap, Trace, Collector, Gc, Root};

struct Node {
    value: i32,
    next: Option<Gc<Node>>,
}

impl Trace for Node {
    fn trace(&self, collector: &mut Collector) {
        if let Some(next) = &self.next {
            collector.edge(next);
        }
    }
}

let mut heap = Heap::new();
let tail: Root<Node> = heap.alloc(Node { value: 2, next: None });
let head: Root<Node> = heap.alloc(Node {
    value: 1,
    next: Some(tail.unrooted()),
});

Trace - безопасный типаж (safe trait): ошибка в его реализации приведёт к логическим багам (объекты освободятся раньше времени), но не к нарушению безопасности памяти, так как обращение по висячему Gc<T> либо попадёт в ещё живой слот, либо вызовет панику, либо столкнётся с переиспользованием слота (ABA).

Ограничения

• Это не высокопроизводительный сборщик. Арены, free list'ы, stop-the-world mark-and-sweep.
• Арены под каждый тип означают, что в гетерогенных графах приходится платить за диспетчеризацию на каждом ребре.
• Нет поколенческой или инкрементальной сборки.
• API с индексацией более многословен, чем *gc_ptr - каждое чтение проходит через кучу.

Когда использовать

Интерпретаторы, среды выполнения DSL или встроенные скриптовые движки, где нужна семантика сборки мусора, требуется работа в окружениях с #![forbid(unsafe_code)] и нет необходимости в пропускной способности production-уровня JVM. Саму статью также стоит прочитать как упражнение по доказательству безопасности через проектирование API, независимо от того, понадобится ли когда-нибудь этот крейт.

Репозиторий

github.com/fitzgen/safe-gc - Apache-2.0 OR MIT. См. конспект статьи с обоснованием архитектурных решений.