If carcinization happens when languages evolve to be more like Rust, then what do you call it when Rust evolves to be more like Java? Caffeination?

Over this summer, I’ve had a decent amount of time to kill. What better way to spend a beautiful hot summer than sitting inside, staring at core dumps in a supposedly memory-safe language? I built a garbage collector - in short, a piece of software that manages allocations for another, more exciting piece of software. The cool part: I made it in Rust, for Rust - a language designed to eliminate garbage collection and which provides few facilities for making it work properly. Not only that, I managed to make my garbage collector work with relatively few compromises, which I’ll describe in further detail lower down.

If you don’t like reading, don’t care about the journey to implement it, or just want to get a sales pitch for the final result, check out the source code on GitHub here. You can also download it directly from crates.io.

Background

If you’re familiar with the details of Rust and its standard library, feel free to skip this section.

The core backing behind Rust’s memory model is affine typing and the borrow checker. Values may only be bound to one identifier at a time, and borrows (a.k.a. references) may not outlive the scope binding their referent.

For example, the following code is invalid:

let x = vec![1, 2, 3];
let y = x;
println!("{x:?}"); // compile error - x has already been moved

Normally, we work around this by borrowing against a binding, such as by making y = &x in the example above. However, we often need to share some heap-allocated value without knowing which binding will live the longest. The solution to this problem is shared ownership via garbage collection.

Rust’s standard library offers two simple reference-counted garbage collectors: the single-threaded Rc and its atomically-indexed counterpart Arc. They operate by maintaining a reference count in each heap allocation. Under most circumstances, these work great, but they can’t handle cyclic references. Combined with interior mutability, it’s trivial to refute them.

use std::{cell::OnceCell, rc::Rc};
struct Foo(OnceCell<Rc<Foo>>);

let x = Rc::new(Foo(OnceCell::new()));
x.0.set(Rc::clone(&x));
// My foo has a reference to itself. It can never be freed!

This is why people actually get paid money to build garbage collectors. If using a reference counter were all you needed, a number of people working at Oracle would be out of a job.

Battle plan

We’d like to create some Gc data structure with a similar API to Rc and Arc, which can accept nearly any data type contained within, and still manage to detect and collect cycles.

We have a few weapons at our disposal:

• Drop: Every non-copiable data type in Rust can implement the Drop trait to ensure some code is called every time it is dropped. In our case, we can implement Drop for Gc to try to glean some knowledge about when an allocation becomes inaccessible.
• Traits: We can construct some trait (in our case, let’s call it Collectable) as a mandatory requirement to be contained in a Gc. Creating this trait has some major downsides (libraries upstream of dumpster can’t implement it) but it’s a necessary evil.

However, our formidable tools are matched by equally formidable challenges:

• Undetectable moves. When a value is moved in Rust, there is no way to detect that fact from within that value. If we had some sort of trait like OnMove which could allow for a function to be called every time it had moved, we could use it to detect when a Gc moved inside another Gc, making it unrooted, and allowing us to create a simple mark-sweep collector. At this rate, though, we would just reinvent C++’s copy constructors.
• Variable-sized data. I foolishly decided to make it so that Gc could store ?Sized types, which is more flexible for library users (enabling things like Gc<[T]>).
• Type erasure. In a typical Rust program, generics are implemented via monomorphization, and no type information is retained at runtime. This makes it harder to clean up an allocation without prior context.

With these two, relatively simple tools, we have enough to build a collector which can handle just about any data type inside.

My approach

We need to detect whether a Gc is reachable without actually scanning the stack. I’ll start with a few definitions, using graph-theoretical language.

1. An allocation graph is a directed graph with a root node whose indegree is zero.
2. A node in an allocation graph is said to be accessible if and only if there exists a path from to in the graph.

It should be clear to see why these definitions are useful to us. We can imagine each node being one allocation, pretending that all data not indirected through a Gc is part of an imaginary allocation for the root. Additionally, each Gc acts as an edge connecting two allocations. If an allocation is accessible in the graph-theoretical sense, it’s still possible for a program to reach it, and if not, it’s safe to free that allocation. Note that the indegree of a node is precisely equal to the reference count of its corresponding allocation.

I’ll roughly outline our approach to determining whether some node ![](data:image/svg+xml,%3Csvg%20class%3D%22typst-doc%22%20viewBox%3D%220%200%2034.782222222222224%2021.878999999999998%22%20width%3D%2234.782222222222224pt%22%20height%3D%2221.878999999999998pt%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Axlink%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxlink%22%20xmlns%3Ah5%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxhtml%22%3E%0A%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%200%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-group%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g408F7439671D13D30238DBD3DBFA44FF%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2811.41111111111111%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23gFFB7823686D721352D68D2B74D6CB2B4%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2815.02511111111111%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g4E71F0CDA1F935173A3F2992F7E9EA0E%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2828.750222222222224%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g41CC67971ED921AC60A433A4485B8464%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3Cdefs%20id%3D%22glyph%22%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g408F7439671D13D30238DBD3DBFA44FF%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%206.981%201.781%20C%206.682%200.754%206.2530003%200.234%205.7200003%200.234%20C%205.551%200.234%205.46%200.36400002%205.46%200.611%20C%205.46%200.79300004%205.538%201.092%205.6940002%201.495%20C%206.214%202.9120002%206.474%203.848%206.474%204.329%20C%206.474%205.2390003%205.863%205.7460003%204.953%205.7460003%20C%204.186%205.7460003%203.523%205.408%202.99%204.719%20C%202.8860002%205.291%202.431%205.7460003%201.768%205.7460003%20C%201.04%205.7460003%200.754%205.07%200.572%204.485%20C%200.442%204.0690002%200.377%203.822%200.377%203.7310002%20C%200.377%203.614%200.442%203.549%200.58500004%203.549%20C%200.65000004%203.549%200.689%203.562%200.72800004%203.588%20C%200.79300004%203.7050002%200.832%203.796%200.845%203.887%20C%201.079%204.875%201.378%205.369%201.7290001%205.369%20C%201.963%205.369%202.08%205.1870003%202.08%204.823%20C%202.08%204.6540003%202.015%204.303%201.872%203.77%20L%201.131%200.819%20C%201.092%200.65000004%201.014%200.312%201.014%200.24700001%20C%201.014%20-0.013%201.1570001%20-0.143%201.4430001%20-0.143%20C%201.69%20-0.143%201.872%20-0.013%201.963%200.24700001%20C%201.9890001%200.312%202.0670002%200.637%202.21%201.196%20L%202.483%202.3530002%20L%202.8730001%203.835%20C%203.016%204.1340003%203.237%204.433%203.51%204.745%20C%203.887%205.1610003%204.355%205.369%204.914%205.369%20C%205.343%205.369%205.551%205.083%205.551%204.524%20C%205.551%204.03%205.278%203.042%204.719%201.5600001%20C%204.6280003%201.326%204.589%201.131%204.589%200.962%20C%204.589%200.32500002%205.07%20-0.143%205.6940002%20-0.143%20C%206.2660003%20-0.143%206.721%200.18200001%207.046%200.832%20C%207.293%201.352%207.4230003%201.7030001%207.4230003%201.872%20C%207.4230003%201.9890001%207.3580003%202.0540001%207.215%202.0540001%20C%207.176%202.0540001%206.981%201.937%206.981%201.781%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22gFFB7823686D721352D68D2B74D6CB2B4%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%202.496%204.875%20C%202.496%205.2650003%202.197%205.603%201.807%205.603%20C%201.417%205.603%201.118%205.2650003%201.118%204.875%20C%201.118%204.485%201.417%204.1470003%201.807%204.1470003%20C%202.197%204.1470003%202.496%204.485%202.496%204.875%20Z%20M%202.496%200.72800004%20C%202.496%201.118%202.197%201.4560001%201.807%201.4560001%20C%201.417%201.4560001%201.118%201.118%201.118%200.72800004%20C%201.118%200.338%201.417%200%201.807%200%20C%202.197%200%202.496%200.338%202.496%200.72800004%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g4E71F0CDA1F935173A3F2992F7E9EA0E%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%209.074%202.3140001%20L%205.044%202.3140001%20L%205.7200003%204.186%20L%209.074%204.186%20C%209.282001%204.186%209.386001%204.29%209.386001%204.498%20C%209.386001%204.7060003%209.282001%204.81%209.074%204.81%20L%205.954%204.81%20L%207.488%209.074%20C%207.514%209.113%207.527%209.139%207.527%209.178%20C%207.527%209.386001%207.4230003%209.49%207.215%209.49%20C%207.046%209.49%206.955%209.425%206.9160004%209.282001%20L%205.291%204.81%20L%201.04%204.81%20C%200.832%204.81%200.72800004%204.7060003%200.72800004%204.498%20C%200.72800004%204.29%200.832%204.186%201.04%204.186%20L%205.07%204.186%20L%204.394%202.3140001%20L%201.04%202.3140001%20C%200.832%202.3140001%200.72800004%202.21%200.72800004%202.002%20C%200.72800004%201.794%200.832%201.69%201.04%201.69%20L%204.16%201.69%20L%202.6130002%20-2.5740001%20C%202.6000001%20-2.6000001%202.6000001%20-2.639%202.6000001%20-2.678%20C%202.6000001%20-2.8860002%202.704%20-2.99%202.9120002%20-2.99%20C%203.068%20-2.99%203.1590002%20-2.925%203.198%20-2.782%20L%204.823%201.69%20L%209.074%201.69%20C%209.282001%201.69%209.386001%201.794%209.386001%202.002%20C%209.386001%202.158%209.243%202.3140001%209.074%202.3140001%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g41CC67971ED921AC60A433A4485B8464%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%205.668%204.862%20C%205.668%205.408%205.135%205.7460003%204.563%205.7460003%20C%203.926%205.7460003%203.3930001%205.447%202.951%204.836%20C%202.821%205.343%202.379%205.7460003%201.768%205.7460003%20C%201.235%205.7460003%200.845%205.33%200.572%204.485%20C%200.442%204.056%200.377%203.809%200.377