Garbage Collection Without Unsafe Code

Many people, including myself, have implemented garbage collection (GC) libraries for Rust. Manish Goregaokar wrote up a fantastic survey of this space a few years ago. These libraries aim to provide a safe API for their users to consume: an unsafe-free interface which soundly encapsulates and hides the library’s internal unsafe code. The one exception is their mechanism to enumerate the outgoing GC edges of user-defined GC types, since failure to enumerate all edges can lead the collector to believe that an object is unreachable and collect it, despite the fact that the user still has a reference to the reclaimed object, leading to use-after-free bugs. This functionality is generally exposed as an unsafe trait for the user to implement because it is the user’s responsibility, not the library’s, to uphold this particular critical safety invariant.

However, despite providing safe interfaces, all of these libraries make extensive use of unsafe code in their internal implementations. I’ve always believed it was possible to write a garbage collection library without any unsafe code, and no one I’ve asserted this to has disagreed, but there has never been a proof by construction.

So, finally, I created the safe-gc crate: a garbage collection library for Rust with zero unsafe code. No unsafe in the API. No unsafe in the implementation. It even has a forbid(unsafe_code) pragma at the top.

That said, safe-gc is not a particularly high-performance garbage collector.

Using safe-gc

To use safe-gc, first we define our GC-managed types, using Gc<T> to define references to other GC-managed objects, and implement the Trace trait to report each of those GC edges to the collector. The big difference from existing GC libraries is that Trace is safe to implement.

Next, we create one or more Heaps to allocate our objects within. Each heap is independently garbage collected. Rather than deref’ing Gc<T> pointers directly, we must index into the Heap to access the referenced T object. This contrasts with other GC libraries and is the key that unlocks safe-gc’s lack of unsafe code, allowing the implementation to abide by Rust’s ownership and borrowing discipline.

There are actually two types for indexing into Heaps to access GC objects: Gc<T>, which is Copy and does not root its referenced object, and Root<T>, which does root its associated object, preventing it from being reclaimed.

Peeking Under the Hood

A safe_gc::Heap is more similar to an arena newtype over a Vec than an engineered heap. Its main storage is a hash map from std::any::TypeId to uniform arenas of the associated type. This lets us ultimately use Vec as the storage for heap-allocated objects, and we don’t need to do any unsafe pointer arithmetic.

safe-gc implements simple mark-and-sweep garbage collection. We begin by resetting the mark bits for each arena. Next we begin the mark phase. This starts by iterating over each root and then setting its mark bit and enqueuing it in the mark stack. The mark phase continues by marking everything transitively reachable from those roots in a fixed-point loop. What is kind of unusual is that we don’t have a single mark stack; each Arena<T> holds only a single type of object and knows how to trace its objects.