Refuse

An easy-to-use, incremental, multi-threaded garbage collector for Rust.

//! A basic usage example demonstrating the garbage collector.
use refuse::{CollectionGuard, Ref, Root};

let guard = CollectionGuard::acquire();
// Allocate a vec![Ref(1), Ref(2), Ref(3)].
let values: Vec<Ref<u32>> = (1..=3).map(|value| Ref::new(value, &guard)).collect();
let values = Root::new(values, &guard);
drop(guard);

// Manually execute the garbage collector. Our data will not be freed,
// since `values` is a "root" reference.
refuse::collect();

// Root references allow direct access to their data, even when a
// `CollectionGuard` isn't held.
let (one, two, three) = (values[0], values[1], values[2]);

// Accessing the data contained in a `Ref` requires a guard, however.
let mut guard = CollectionGuard::acquire();
assert_eq!(one.load(&guard), Some(&1));
assert_eq!(two.load(&guard), Some(&2));
assert_eq!(three.load(&guard), Some(&3));

// Dropping our root will allow the collector to free our `Ref`s.
drop(values);
guard.collect();
assert_eq!(one.load(&guard), None);

As the version number indicates, this crate is in early development. No semver compatibility will be provided until 0.1.0.

Motivation

While working on Muse, @Ecton recognized the need for garbage collection to prevent untrusted scripts from uncontrollably leaking memory. After surveying the landscape, he didn't find any that would easily incorporate into his vision for the language. As far as he can tell, the design choices of this collector are different than any existing collector in Rust.

Design

This crate exposes a completely safe API for an incremental, multi-threaded, tracing garbage collector in Rust.

Tracing garbage collectors can be implemented in various ways to identify the "roots" of known memory so that they can trace from the roots through all necessary references to determine which memory allocations can be freed.

This crate exposes a Root<T> type which behaves similarly to an Arc<T> but automatically becomes a root for the collector. Root<T> implements Deref<Target = T>, allowing access to the underlying data even while the collector is running.

The Ref<T> type implements Copy and does not provide direct access to the underlying data. To get a reference to the underlying data, a weak reference must be upgraded using a CollectionGuard. The returned reference is tied to the guard, which prevents collection from running while any guards are held.

A CollectionGuard is needed to:

• Allocate a new Root<T> or Ref<T>
• Load an &T from a Ref<T>

Safety

This crate has safety comments next to each usage of unsafe, and passes Miri tests when provided the flags:

MIRIFLAGS="-Zmiri-permissive-provenance -Zmiri-ignore-leaks" cargo +nightly miri test

• -Zmiri-permissive-provenance: parking_lot internally casts a usize to a pointer, which breaks pointer provenance rules. Pointer provinence is currently only an experimental model, and nothing this collector is using from parking_lot couldn't be implemented in a fashion that honors pointer provinence. Thus, this library's author consider's this an implementation detail that can be ignored.

• -Zmiri-ignore-leaks: This crate spawns a global collector thread that never shuts down. Miri detects that the main thread does not wait for spawned threads to shut down and warns about this potential memory leak. When a thread is shut down and all of its data is no longer reachable, the thread storage will be cleaned up. However, the collector never shuts down and assumes that new threads could still be spawned at any given time.

  Additionally, on some platforms the main thread's thread-local storage may not be cleaned up when the main thread exits according to LocalKey's documentation

This crate exposes a safe API that guarantees no undefined behavior can be triggered by incorrectly using the API or implementing the Collectable trait incorrectly. Incorrect usage of this crate can lead to deadlocks and memory leaks. Specifically:

• Reference cycles between Root<T>'s will lead to leaks just as Arc<T>'s will.
• If a Root<T> uses locking for interior mutability, holding a lock without a collector guard can cause the garbage collector to block until the lock is released. This escalates from a pause to a deadlock if the lock can't be released without acquiring a collection guard. All locks should be acquired and dropped only while a CollectorGuard is acquired.

What's left

• Finalizers: Currently Drop is executed, but there's no way to attach behavior to run before the object is dropped.
• More advanced algorithm: The current algorithm employed is the naive mark-and-sweep. It performs well for smaller sets, but will become slower as the memory sets grow larger. Other algorithms may be considered, but the current naive algorithm is probably suitable for its application (Muse).

Benchmarks

Benchmarking is hard. These benchmarks aren't adequate. These numbers are from executing benches/timings.rs, which compares allocating 100,000 32-byte values, comparing the time it takes to allocate each Arc<[u8; 32]>, Root<[u8;32]>, and Ref<[u8; 32]>. The measurements are the amount of time it takes for an individual allocation. These results are from running on a Ryzen 3700X.

1 thread

Label	avg	min	max	stddev	out%
Arc	47.39ns	20.00ns	8.680us	153.2ns	0.010%
Ref	58.94ns	30.00ns	286.1us	1.191us	0.002%
Root	84.67ns	40.00ns	138.6us	1.537us	0.001%

4 threads

Label	avg	min	max	stddev	out%
Arc	47.55ns	20.00ns	8.670us	144.1ns	0.010%
Ref	76.43ns	30.00ns	320.4us	2.428us	0.000%
Root	152.8ns	40.00ns	155.6us	2.740us	0.001%

8 threads

Label	avg	min	max	stddev	out%
Arc	54.60ns	20.00ns	16.60us	159.1ns	0.010%
Ref	99.02ns	30.00ns	586.0us	3.690us	0.000%
Root	302.6ns	40.00ns	721.7us	5.727us	0.002%

16 threads

Label	avg	min	max	stddev	out%
Arc	58.38ns	20.00ns	920.9us	862.5ns	0.000%
Ref	211.1ns	30.00ns	1.216ms	10.41us	0.000%
Root	675.6ns	40.00ns	1.565ms	16.42us	0.002%

32 threads

Label	avg	min	max	stddev	out%
Arc	68.82ns	20.00ns	2.491ms	1.680us	0.000%
Ref	425.8ns	30.00ns	3.121ms	21.73us	0.000%
Root	1.538us	40.00ns	2.724ms	33.31us	0.002%

Author's Benchmark Summary

In these benchmarks, 100 allocations are collected into a pre-allocated Vec. The Vec is cleared, and then the process is repeated 1,000 total times yielding 100,000 total allocations.

In both the Root and Ref benchmarks, explicit calls to CollectorGuard::yield_to_collector() are placed after the Vec is cleared. The measurements include time waiting for the incremental garbage collector to run during these yield points.

The CPU that is executing the benchmarks listed above has 16 cores. As the numbers in the benchmarks show, the closer the CPU is to being fully saturated, the more garbage collection impacts the performance.

There are plenty of opportunities to improve the performance, but incremental garbage collection requires pausing all threads briefly to perform the collection. These pauses are generally short when there are few active threads, but when many threads are active, the pauses can be significant.