Garbage Collection Without Unsafe Code

Nick Fitzgerald, who works on Wasmtime and Cranelift, wrote a small Rust GC library called safe-gc and then wrote up why it contains no unsafe — not in the public API, not in the internals. The post is interesting less as a GC tutorial than as a worked example of using API shape to push whole categories of bug out of the reachable state space.

The core trick: index, don't deref

Most Rust GC libraries expose something like a Gc<T> that you can call .deref() on. That is where the unsafe always ends up hiding: returning a &T from a pointer whose lifetime the borrow checker can't see forces the library to assert a lifetime the compiler can't verify.

safe-gc sidesteps this. Gc<T> is not a deref-able pointer. To read the object, you index into the heap:

let value = &heap[&gc_ref];

Now the borrow checker sees a perfectly ordinary Index impl on a perfectly ordinary struct. The &T that comes back is tied to the &Heap that the index call borrowed, exactly as it would be for any Vec<T>. There is nothing to fake, because there is no lifetime being smuggled through a raw pointer.

Everything downstream flows from this: the GC algorithm gets to work on plain Rust data structures with plain Rust ownership rules.

Two reference types

Gc<T> — cheap, Copy, does not root. Safe to hold inside other GC objects or during code that can't trigger collection.
Root<T> — roots its target, not Copy, Drop's side effect unroots. Required to hold a reference across code that can allocate and therefore collect.

Rooting is a runtime operation (updates a roots table), not a type-system one. The type system's contribution is forcing the user to pick between the two kinds of reference at construction time, which makes the rooting discipline local rather than global.

Heap as `HashMap<TypeId, Box<dyn ArenaObject>>`

The heap is one arena per concrete type:

pub struct Heap {
    arenas: HashMap<TypeId, Box<dyn ArenaObject>>,
}

Each Arena<T> is a Vec<Slot<T>> with a FreeList<T> on the side. No manual memory management, no pointer arithmetic — allocation is "pop from the free list or push to the Vec."

The upshot is that the collector's state is ordinary Rust data. Vec, HashMap, Box<dyn Trait>. When the mark phase wants to record that a slot is live, it flips a bit in the arena; when the sweep phase wants to free a slot, it runs drop and pushes its index onto the free list. None of this needs unsafe.

Mark-and-sweep, chosen because copying failed

Fitzgerald's first attempt was a copying collector. He abandoned it after running into what he describes as an unresolvable borrowing conflict: forwarding-pointer updates want mutable access to the entire from-space, but the traversal is already holding a projection into a specific arena. Mark-and-sweep avoided this — objects don't move, so nothing needs to write back into the old location.

The switch took about thirty minutes. This is the kind of design pivot that only shows up when you're constrained to work within a type system that refuses to let you handwave — the copying collector is perfectly implementable with unsafe, which is why every other Rust GC library uses one.

The actual algorithm is unremarkable: per-arena mark stacks, fixed-point loop draining them, sweep that drops unreachable slots and returns them to the free list. Arenas reserve extra capacity when free space drops below 25%.

Safety properties that fall out for free

Finalizers can't resurrect or use-after-free. Drop::drop receives &mut self but no &Heap, and the only way to read a Gc<T> is through &Heap. So a destructor literally cannot touch any other GC object. The footgun that motivates every other language's "don't use finalizers" advice just isn't reachable here.

Trace doesn't need to be unsafe. In a conventional GC, forgetting to trace an edge causes live objects to be freed, which causes reads through their pointers to become UB. In safe-gc, forgetting to trace an edge means a live object gets freed, its slot gets reused, and later indexing still returns valid memory — either the object is still there, you get a panic, or you observe ABA reuse. All three are memory-safe, so Trace stays a safe trait.

Dangling Gc<T> is logically wrong, not UB. Holding a Gc<T> across a collection it shouldn't have survived gives one of: the object happens to still be alive (silent bug), the slot is empty and you panic, or ABA (someone else got that slot). Generation counters can upgrade ABA to a panic. None of the outcomes corrupt memory.

Why this is interesting beyond Rust

The pattern generalizes. Any time you have an abstraction that fundamentally violates a language's safety rules (GC, arenas, self-referential structures, cyclic graphs), the usual move is to wrap unsafe under a carefully-audited API. Fitzgerald's move is to change the API shape so the operations the language doesn't allow aren't expressible. You pay with syntax — heap[&gc] instead of *gc — and you pay with some flexibility the copying-GC path would have given you, and in exchange the implementation collapses to ordinary safe Rust.

It's the same move as "newtype wrapper with no public constructor," scaled up to an entire runtime subsystem.

pointer-provenance — the other direction: carefully specifying what pointers carry so that seemingly-reasonable compiler rewrites remain valid. Safe-gc avoids the whole question by not having raw pointers.
simplified-model-of-fil-c — memory safety retrofitted to C/C++ via runtime capability checks. A different point in the "what do you give up to get safety" space.
arena-allocation — the same index-not-pointer move: generational arenas hand out integer indices instead of &T to sidestep the borrow-checker and use-after-free at once.
garbage-collection-handbook — the survey to read next if the algorithm side is what interested you: mark-sweep, copying, generational, and the low-pause concurrent collectors, with the tradeoffs Fitzgerald ran into stated in their general form.
safe-gc — the crate itself.