This repo is home to the
gc-arena crate, which provide Rust with garbage
collected arenas and a means of safely interacting with them.
gc-arena crate, along with its helper crate
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 therefore
unsafe, but it can safely be implemented by procedural
macro, and the
gc-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 single
mutate 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 this
mutate 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.
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.
Currently this crate is still pretty WIP, but is basically usable and safe.
The collection algorithm is an incremental mark-and-sweep algorithm very similar
to the one in PUC-Rio Lua 5.3, 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.
Copy and are pointer sized, and no bookkeeping at all is done
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
Unsize coercion, but allocating space for arbitrarily sized DSTs is
currently pretty weird.
There is currently no system for object finalization. This is not terribly
difficult to implement, depending on the system, but it would require picking
a particular set of edge-case finalization behavior. Implementing
a type held inside a
Gc ofc still works as normal though, so the actual need
for genuine "finalization" is unclear.
A harder to solve limitation is that there is currently no system 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.
Another limitiation is that 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
The crate is currently pretty light on documentation and examples.
Everything in this repository is licensed under either of:
at your option.