# Garbage Collection Without Unsafe Code

# 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:

```rust
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.