Updated at Feb 2, 2017

I have been following this repo, rust-gc for almost three months, during that time, my understanding of Rust language became better, but initially, I can’t understand the rust-gc’s code in a decent degree.

The problem is that, all the information I know about garbage collection is from tiny chapters in compiler book or introductory material of a big system’s GC part. As a result, although I can tell the basic algorithmic idea behind various GC strategies, I have no idea how to implement this for a language.

Finally, after more analysis, I know the key point of this library – “roots”.

Why “roots” are important?

The algorithm that rust-gc uses now is called “mark and sweep”, the simplest of all. Previously, I only focused on the “mark” and “sweep” part, but totally neglecting other aspects. Now I realize that, the core of problem is about “roots”.

First, what are “roots”? They are the objects that are directly accessible, without going through any references. In practice, the roots usually comprise static/global storage and thread-local storage (such as thread stacks), or even in the registers in a more realistic model. Here are some properties that a safe system should comply to:

  • All memory accessible from “roots” should be allocated, valid memory.
  • We can’t access more except for “roots” and pointed ones.

And for an efficient system, there are also:

  • Once some object is inaccessible from roots, it should be collected as soon as possible
  • Objects can be shared

The later one can be nasty in the concurrent GC and multi-thread context. But we will not address this in this post.

So, as a result, the most important thing in implementing such a system, is to determine:

  • When should an object become root?
  • When should an object be “unrooted”?

What are “roots”?

The global and static objects related to the on-heap allocation should be roots during the whole lifetime of the program.

For the local objects (I mean, the references to them have local lifetimes), they should be roots, and once out of lexical scope, they should be dropped and unrooted. However, it doesn’t necessarily mean that they will be deallocated.

On the other hand, we can divide the heap objects into two genres, roots and non-roots.

And for the objects reside on stack, they are certainly roots. But they are not garbage-collected. So we can transitively set the heap GCed object that it might refer to as the root.

Implementation

First, I will introduce the basic ideas, and then I will give a line-by-line analysis of related code in rust-gc.

Basic ideas

Apparently, we need to wrap the object allocated on heap with additional information, including reference count, and whether or not it is marked. RC will be used constantly, while mark flag will be used in the GC stage.

Beyond that, we need to wrap the wrapped object with another layer of abstraction on the language level. Specifying

  • how to borrow the value inside (immutably or mutably)
  • what will happen when it is out of scope
  • what will happen when we clone it, dereference it et cetera

rust-gc’s solution

NOTE: based on this version of rust-gc.

The most important modules are gc/src/gc.rs, gc/src/trace.rs, gc/src/lib.rs. The gc specifies the underlying structure and algorithmic details. The trace is a trait requiring specification of the recursively referencing structure. The lib defined language level Gc and GcCell structure and derivation for Clone, Deref etc.

gc – Global states

GC_STATE is the global state that we maintain. It is about the general memory layout of boxes space.

struct GcState {
    bytes_allocated: usize,
    threshold: usize,
    boxes_start: Option<Box<GcBox<Trace + 'static>>>,
    boxes_end: *mut Option<Box<GcBox<Trace + 'static>>>,
}

Note that the boxes region is used to contain the address to the real box, not the box itself. The GcBox allocation is still done by Rust’s allocator.

GC_SWEEPING indicated if we are in sweeping stage – which is dangerous, and any attempt to dereference will trigger a panic.

gc – wrapper structure

pub struct GcBoxHeader {
    roots: Cell<usize>, // number of roots
    next: Option<Box<GcBox<Trace + 'static>>>,
    marked: Cell<bool>,
}

pub struct GcBox<T: Trace + ?Sized + 'static> {
    header: GcBoxHeader,
    data: T,
}

For a single object, it is wrapped inside a GcBox. Note that we don’t maintain a global object list, instead, we use a next pointer to traverse all objects. And note the requirements over T, the underlying data. It must be traceable, i.e. it can enforce the rules on memory safety (no leak, no dangling) effectively. Beyond that, it must be sizable to be allocated on heap. The lifetime specifier 'static might be weird. But actually, it means that the T has a lifetime not constrained by scope. So we will manage the validity of reference by ourselves. Lifetime specifier is the purely static with no runtime semantics.

gc – algorithm

The three important components of “mark & sweep” algorithm – allocation, annotation and collection.

  • allocation
pub fn new(value: T) -> NonZero<*mut GcBox<T>> {
    GC_STATE.with(|_st| {
        let mut st = _st.borrow_mut();

		 // make sure enough memory is available
        if st.bytes_allocated > st.threshold {
            collect_garbage(&mut *st); // Make more space

            if st.bytes_allocated as f64 > st.threshold as f64 * USED_SPACE_RATIO  {
                st.threshold = (st.bytes_allocated as f64 / USED_SPACE_RATIO) as usize
            }
        }

		// It is pointed in current scope, so `roots` is 1
        let mut gcbox = Box::new(GcBox {
            header: GcBoxHeader {
                roots: Cell::new(1),
                marked: Cell::new(false),
                next: None,
            },
            data: value,
        });

		// got raw pointer
        let gcbox_ptr = unsafe { NonZero::new(&mut *gcbox as *mut _) };

		// Append to the boxes region
        let next_boxes_end = &mut gcbox.header.next as *mut _;
        if st.boxes_end.is_null() {
            st.boxes_end = next_boxes_end;
            st.boxes_start = Some(gcbox);
        } else {
            unsafe {
                *st.boxes_end = Some(gcbox);
            }
            st.boxes_end = next_boxes_end;
        }

        // We allocated some bytes! Let's record it
        st.bytes_allocated += mem::size_of::<GcBox<T>>();

        // Return the pointer to the newly allocated data
        gcbox_ptr
    })
}
  • annotation
/// Mark and trace recursively, use in GC stage
pub unsafe fn trace_inner(&self) {
    let marked = self.header.marked.get();
    if !marked {
        self.header.marked.set(true);
        self.data.trace();
    }
}

/// Increase the root count on this GcBox, used in running time
pub unsafe fn root_inner(&self) {
    self.header.roots.set(self.header.roots.get() + 1);
}

/// Decrease the root count on this GcBox, used in running time
pub unsafe fn unroot_inner(&self) {
    self.header.roots.set(self.header.roots.get() - 1);
}
  • collection
fn collect_garbage(st: &mut GcState) {
    let mut next_node = &mut st.boxes_start
        as *mut Option<Box<GcBox<Trace + 'static>>>;

> To root or 
    while let Some(ref mut node) = *unsafe { &mut *next_node } {
        {
            let header = node.header_mut();
            next_node = &mut header.next as *mut _;

            // If it doesn't have roots - we can abort now
            if header.roots.get() == 0 { continue }
        }
        // We trace in a different scope such that node isn't
        // mutably borrowed anymore
        unsafe { node.trace_inner(); }
    }

    GC_SWEEPING.with(|collecting| collecting.set(true));

    let mut next_node = &mut st.boxes_start
        as *mut Option<Box<GcBox<Trace + 'static>>>;

    // Sweep
    while let Some(ref mut node) = *unsafe { &mut *next_node } {
        let size = node.size_of();
        let header = node.header_mut();

        if header.marked.get() {
            // This node has already been marked - we're done!
            header.marked.set(false);
            next_node = &mut header.next;
        } else {
            // The node wasn't marked - we need to delete it
            st.bytes_allocated -= size;
            let mut tmp = None;
            mem::swap(&mut tmp, &mut header.next);
            mem::swap(&mut tmp, unsafe { &mut *next_node });

            // At this point, the node is destroyed if it exists due to tmp dropping
        }
    }

    // Update the end pointer to point to the correct location
    st.boxes_end = next_node;

    // XXX This should probably be done with some kind of finally guard
    GC_SWEEPING.with(|collecting| collecting.set(false));
}