14 unstable releases (4 breaking)
0.5.3 | May 15, 2024 |
---|---|
0.5.1 | Apr 22, 2024 |
0.5.0 | Jan 1, 2024 |
0.4.0 | Oct 30, 2023 |
0.1.1 | May 11, 2019 |
#45 in #collect
4,178 downloads per month
Used in 14 crates
(2 directly)
19KB
212 lines
This repo is home to the gc-arena
crate, which provides Rust with garbage
collected arenas and a means of safely interacting with them.
gc-arena
The gc-arena
crate, along with its helper crate gc-arena-derive
, provides
safe allocation with cycle-detecting garbage collection within a closed "arena".
There are two techniques at play that make this system sound:
-
Garbage collected objects are traced using the
Collect
trait, which must be implemented correctly to ensure that all reachable objects are found. This trait is thereforeunsafe
, but it can safely be implemented by procedural macro, and thegc-arena-derive
provides such a safe procedural macro. -
In order for garbage collection to take place, the garbage collector must first have a list of "root" objects which are known to be reachable. In our case, the user of
gc-arena
chooses a single root object for the arena, but this is not sufficient for safe garbage collection. If garbage collection were to take place when there are garbage collected pointers anywhere on the Rust stack, such pointers would also need to be considered as "root" objects to prevent memory unsafety.gc-arena
solves this by strictly limiting where garbage collected pointers can be stored, and when they can be alive. The arena can only be accessed through a singlemutate
method which takes a callback, and all garbage collected pointers inside this callback are branded with an invariant lifetime which is unique to that single callback call. Thus, when outside of thismutate
method, the rust borrow checker ensures that it is not possible for garbage collected pointers to be alive anywhere on the stack, nor is it possible for them to have been smuggled outside of the arena's root object. Since all pointers can be proven to be reachable from the single root object, safe garbage collection can take place.
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.
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:
-
Allocating DSTs is currently somewhat painful due to limitations in Rust. It is possible to have
Gc
pointers to DSTs, and there is a replacement for unstableUnsize
coercion, but there is no support for directly allocating arbitrarily sized DSTs. -
There is no support at all for multi-threaded allocation and collection. The basic lifetime and safety techniques here would still work in an arena supporting multi-threading, but this crate does not support this. It is optimized for single threaded use and multiple, independent arenas.
-
The
Collect
trait does not provide a mechanism to move objects once they are allocated, so this limits the types of collectors that could be written. This is achievable but no work has been done towards this. -
The crate is currently pretty light on documentation and examples.
Prior Art
The ideas here are mostly not mine, much of the design is borrowed heavily from rust-gc, and the idea of using "generativity" comes from You can't spell trust without Rust.
License
Everything in this repository is licensed under either of:
- MIT license LICENSE-MIT or http://opensource.org/licenses/MIT
- Creative Commons CC0 1.0 Universal Public Domain Dedication LICENSE-CC0 or https://creativecommons.org/publicdomain/zero/1.0/
at your option.
Dependencies
~345–790KB
~18K SLoC