Trace - Understanding Rust GC

Goal

I want to understand how Rust GC work to see if I can use it in my Scheme VM interpreter to be written in Rust.

How to use

GC-ed objects should implement Trace and Finalize. You should use Gc::new instead of Box::new to allocate objects in heap. Here is an example from the official document.

let x = Gc::new(1_u8);
let y = Gc::new(Box::new(Gc::new(1_u8)));

#[derive(Trace, Finalize)]
struct Foo {
    a: Gc<u8>,
    b: u8
}

let z = Gc::new(Foo {a: x.clone(), b: 1})

What is Gc<Foo>?

z variable above is Gc<Foo> type. You can access fields of Foo like z.a. But why? It doesn't have z field in it. Because it implements Deref Trait Rust compiler can take care of it.

impl<T: Trace + ?Sized> Deref for Gc<T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &T {
        &self.inner().value()
    }
}

The definition of the struct GC<T> as follows. It has only 2 fields.

pub struct Gc<T: Trace + ?Sized + 'static> {
    ptr_root: Cell<NonNull<GcBox<T>>>,
    marker: PhantomData<Rc<T>>,
}

Trace Trait

Per Designing a GC in Rust - In Pursuit of Laziness the purpose of trace is a way of walking the fields of a given object and finding inner Gc<T> fields. For example if you have one GC<T> object, you should be able to find all GC<T> fields or inner fields by the tracing.

Let's look into the Trace trait. I'm not sure what root and unroot are doing yet. We'll get back to here later.

/// The Trace trait, which needs to be implemented on garbage-collected objects.
pub unsafe trait Trace: Finalize {
    /// Marks all contained `Gc`s.
    unsafe fn trace(&self);

    /// Increments the root-count of all contained `Gc`s.
    unsafe fn root(&self);

    /// Decrements the root-count of all contained `Gc`s.
    unsafe fn unroot(&self);

    /// Runs Finalize::finalize() on this object and all
    /// contained subobjects
    fn finalize_glue(&self);
}

Here is one Trace implementation of for 'static lifetime struct.

unsafe impl<T: ?Sized> Trace for &'static T {
    unsafe_empty_trace!();
}

unsafe_empty_trace! is a macro which has no-op trace, root and unroot method. This makes sense because 'static lifetime indicates that the data pointed to by the reference lives for the entire lifetime of the running program. So we don't event need to track or sweep. Let's look at one more example. This is the trace for an array. I would guess this is marking all elements in the array. Let's confirm.

unsafe impl<T: Trace, const N: usize> Trace for [T; N] {
    custom_trace!(this, {
        for v in this {
            mark(v);
        }
    });
}

custom_trace! is implemented as follows. It defines inline mark method and call it in the $body.

/// This rule implements the trace method.
///
/// You define a `this` parameter name and pass in a body, which should call `mark` on every
/// traceable element inside the body. The mark implementation will automatically delegate to the
/// correct method on the argument. 
#[macro_export]
macro_rules! custom_trace {
    ($this:ident, $body:expr) => {
        #[inline]
        unsafe fn trace(&self) {
            #[inline]
            unsafe fn mark<T: $crate::Trace + ?Sized>(it: &T) {
                $crate::Trace::trace(it);
            }
            let $this = self;
            $body
        }

I think $crate::Trace::trace(it); is calling trace() for Gc<T> but not 100% sure.

unsafe impl<T: Trace + ?Sized> Trace for Gc<T> {
    #[inline]
    unsafe fn trace(&self) {
        self.inner().trace_inner();
    }

Then it calls trace_inner() for GcBox.

    /// Marks this `GcBox` and marks through its data.
    pub(crate) unsafe fn trace_inner(&self) {
        let marked = self.header.marked.get();
        if !marked {
            self.header.marked.set(true);
            self.data.trace();
        }
    }

Remember that GcBox is the raw pointer allocated in Gc::new and stored in ptr_root.

    pub fn new(value: T) -> Self {
        assert!(mem::align_of::<GcBox<T>>() > 1);

        unsafe {
            // Allocate the memory for the object
            let ptr = GcBox::new(value);

            // When we create a Gc<T>, all pointers which have been moved to the
            // heap no longer need to be rooted, so we unroot them.
            (*ptr.as_ptr()).value().unroot();
            let gc = Gc {
                ptr_root: Cell::new(NonNull::new_unchecked(ptr.as_ptr())),
                marker: PhantomData,
            };

Let's quickly look at GcBox definition.

pub(crate) struct GcBoxHeader {
    // XXX This is horribly space inefficient - not sure if we care
    // We are using a word word bool - there is a full 63 bits of unused data :(
    // XXX: Should be able to store marked in the high bit of roots?
    roots: Cell<usize>,
    next: Option<NonNull<GcBox<dyn Trace>>>,
    marked: Cell<bool>,
}

#[repr(C)] // to justify the layout computation in Gc::from_raw
pub(crate) struct GcBox<T: Trace + ?Sized + 'static> {
    header: GcBoxHeader,
    data: T,
}

Okay. Now I have better understanding. The trace method just set marked=true which means the ptr is in use. By the way who is calling the trace method and when? The answer is collect_garbage => GcBox::trace_inner() => trace. This is exciting! We're so close to the core of the gc. Let's look at collect_garbage.

/// Collects garbage.
fn collect_garbage(st: &mut GcState) {
__snip__

    unsafe fn mark(head: &mut Option<NonNull<GcBox<dyn Trace>>>) -> Vec<Unmarked> {
        // Walk the tree, tracing and marking the nodes
        let mut mark_head = *head;
        while let Some(node) = mark_head {

__snip__
    unsafe {
        let unmarked = mark(&mut st.boxes_start);
        if unmarked.is_empty() {
            return;
        }

Now we know GcState.boxes_start is the actual starting point of mark and it recursively marks GC<T> objects. My next question is who's setting up boxes_start? The answer is it is done in GcBox::new whenever it allocates new GcBox, it maintains a link list of GcBox and set it to boxes_start.

            let gcbox = Box::into_raw(Box::new(GcBox {
                header: GcBoxHeader {
                    roots: Cell::new(1),
                    marked: Cell::new(false),
                    next: st.boxes_start.take(),
                },
                data: value,
            }));

            st.boxes_start = Some(unsafe { NonNull::new_unchecked(gcbox) });

And finally GcState is a thread local object as follows. So GcState is a kind of global variable which is local to a thread.

// The garbage collector's internal state.
thread_local!(static GC_STATE: RefCell<GcState> = RefCell::new(GcState {
    bytes_allocated: 0,
    threshold: INITIAL_THRESHOLD,
    boxes_start: None,
}));

Summary of Trace (Mark)

  • GC-ed object should implement Trace trait.
  • The trace method should recursively call trace method for inner objects.
  • In mark phase the gc calls trace for GcBox::newed objects.

Next: Finalize, Sweep, root and unroot - Understanding Rust GC - higepon blog.