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:

use safe_gc ::{ Collector , Gc , Trace }; // Define a GC-managed object. struct List { value : u32 , // GC-managed references to the next and previous links in the list. prev : Option < Gc < List >> , next : Option < Gc < List >> , } // Report GC edges to the collector. impl Trace for List { fn trace ( & self , collector : & mut Collector ) { if let Some ( prev ) = self .prev { collector .edge ( prev ); } if let Some ( next ) = self .next { collector .edge ( next ); } } }

This looks pretty similar to other GC libraries in Rust, although it could definitely benefit from an implementation of Trace for Option<T> and a derive(Trace) macro. The big difference from existing GC libraries is that Trace is safe to implement; more on this later.

Next, we create one or more Heap s to allocate our objects within. Each heap is independently garbage collected.

use safe_gc :: Heap ; let mut heap = Heap :: new ();

... continue reading