Garbage Collection Without Unsafe Code

Author: Nick Fitzgerald Date: February 6, 2024 URL: https://fitzgen.com/2024/02/06/safe-gc.html

Overview

This article documents the creation of safe-gc, a garbage collection library for Rust that contains zero unsafe code — neither in its API nor implementation. The author explores how this was achieved and discusses the design decisions that made it possible.

Core Design Principles

The key innovation enabling safety is the indexing mechanism. Rather than dereferencing Gc<T> pointers directly (as other GC libraries do), users must index into a Heap to access objects: heap[&gc_reference]. This respects Rust's borrowing rules and eliminates the need for unsafe pointer arithmetic.

Two Reference Types

The library distinguishes between two pointer types:

• Gc<T>: A copyable reference that doesn't prevent garbage collection. Should only be used within GC objects or when GC cannot occur.
• Root<T>: A non-copyable reference that "roots" objects, preventing their collection. Must be used for references held across potential GC-triggering operations.

Implementation Architecture

The Heap uses a type-indexed hash map structure:

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

Each Arena<T> contains a FreeList<T> backed by a Vec, avoiding unsafe pointer manipulation. Allocation uses a fast path (checking existing capacity) and slow path (triggering GC when needed).

Mark-and-Sweep Algorithm

The garbage collector implements three phases:

1. Mark Phase: Starting from root set entries, recursively mark all reachable objects across type boundaries using per-arena mark stacks.
2. Fixed-Point Loop: A two-level loop drains each arena's mark stack while any work remains.
3. Sweep Phase: Unreachable objects are dropped and their slots returned to free lists. Arenas reserve additional capacity if falling below 25% available space.

Safety Properties

The design prevents classic garbage collection footguns.

Finalizers Without Unsafe Traits

"Drop implementations simply do not have access to a Heap, which is required to deref GC pointers, so they cannot suffer from those finalization footguns."

Drop can be used safely because destructors cannot access GC objects — eliminating use-after-free and resurrection bugs.

Dangling Reference Handling

Using an unrooted Gc<T> across collection produces one of three safe outcomes:

1. The object remains alive anyway (hidden bug)
2. Accessing the freed slot triggers a panic
3. The slot contains a new object (ABA problem, could be upgraded to panic with generation counters)

All outcomes remain memory-safe; none cause corruption.

Why Not a Copying Collector?

The author initially attempted a copying collector with forwarding pointers but abandoned it due to borrowing conflicts in heterogeneous heaps. "When I decided to try mark-and-sweep, it only took me about half an hour to get an initial prototype working."

The fundamental issue: simultaneously needing mutable access to the entire from-space (for forwarding pointers) while already projecting into specific arenas creates borrowing violations that proved inelegant to resolve.

Trade-offs

The Trace trait remains safe to implement (not marked unsafe) because the indexing model prevents incorrect edge enumeration from causing memory unsafety — only logical errors result.

The performance is acknowledged as "not particularly high-performance," but the guarantee of safety makes the tradeoff worthwhile for certain use cases.

Conclusion

safe-gc demonstrates that unsafe-free garbage collection is feasible in Rust through careful API design that respects ownership semantics. The implementation proves by construction that the theoretical possibility is practical reality.