Home

Awesome

crates.io docs.rs Build Status

gc-arena

This repo is home to the gc-arena crate, which provides Rust with garbage collected arenas and a means of safely interacting with them.

The gc-arena crate, along with its helper crate gc-arena-derive, provides allocation with safe, incremental, exact, cycle-detecting garbage collection within a closed "arena". There are two techniques at play that make this system sound:

In other words, the gc-arena crate does not retrofit Rust with a globally accessible garbage collector, rather it only allows for limited garbage collection in isolated garbage collected arenas. All garbage collected pointers must forever live inside only this arena, and pointers from different arenas are prevented from being stored in the wrong arena.

See this blog post for a more in-depth tour of the crate's design. It is quite dense, but it explains everything necessary to fully understand the machinery used in the included linked list example.

Use cases

This crate was developed primarily as a means of writing VMs for garbage collected languages in safe Rust, but there are probably many more uses than just this.

Current status and TODOs

Basically usable and safe! It is used by the Adobe Flash Player emulator Ruffle for its ActionScript VM as well as some other projects (like my own stackless Lua runtime piccolo, for which the crate was originally designed)

The collection algorithm is an incremental mark-and-sweep algorithm very similar to the one in PUC-Rio Lua, and is optimized primarily for low pause time. During mutation, allocation "debt" is accumulated, and this "debt" determines the amount of work that the next call to Arena::collect will do.

The pointers held in arenas (spelled Gc<'gc, T>) are zero-cost raw pointers. They implement Copy and are pointer sized, and no bookkeeping at all is done during mutation.

Some notable current limitations:

Prior Art

The ideas here are mostly not mine. Much of the user-facing design is borrowed heavily from rust-gc, and the idea of using "generativity" comes from You can't spell trust without Rust. The design of the actual garbage collection system itself borrows heavily from the incremental mark-and-sweep collector in Lua 5.4.

License

Everything in this repository is licensed under either of:

at your option.