How GC in unsafe loxido works

ceronman/loxido: Rust implementation of the Lox programming language.

How to allocate object

let bar = gc.alloc(LoxString::from_string("bar".to_owned()));

LoxString::from_string and GcObject implementation. They are staraightforward.

pub struct LoxString {
    pub header: GcObject,
    pub s: String,
    pub hash: usize,
}

impl LoxString {
    pub fn from_string(s: String) -> Self {
        let hash = LoxString::hash_string(&s);
        LoxString {
            header: GcObject::new(ObjectType::LoxString),
            s,
            hash,
    }
__snip__
pub struct GcObject {
    marked: bool,
    next: Option<NonNull<GcObject>>,
    obj_type: ObjectType,
}

Gc::alloc should be doing the trick. I added a comment for each line.

    pub fn alloc<T: Display + 'static>(&mut self, object: T) -> GcRef<T> {
        unsafe {
            // Alloc object in heap.
            let boxed = Box::new(object);
            // Get raw pointer from Box::into_raw.
            // pointer is NonNull<T>.
            let pointer = NonNull::new_unchecked(Box::into_raw(boxed));
            // This assumes &T has GcObject as the first field with the exact sae alignhment.
            let mut header: NonNull<GcObject> = mem::transmute(pointer.as_ref());
            // Gc.first is linked list of GcObject(=header).
            header.as_mut().next = self.first.take();
            // The newly allocated one becomes head of the linked list.
            self.first = Some(header);
            // GcRef is a struct with one field pointer: NonNull<T>.
            GcRef { pointer }
        }
    }

Mark

Adding my comments inline.

fn mark_roots(&mut self) {
        // Mark VM stack.
        for &value in &self.stack[0..self.stack_len()] {
            self.gc.mark_value(value);
        }
        // Mark call frames.
        for frame in &self.frames[..self.frame_count] {
            self.gc.mark_object(frame.closure)
        }

        for &upvalue in &self.open_upvalues {
            self.gc.mark_object(upvalue);
        }

        self.gc.mark_table(&self.globals);
        self.gc.mark_object(self.init_string);
    }

Trace

mark_object pushes in-use objects to grey_stack. blacken_object marks recursively in objects. Unlike Rust GC this doesn't have Trace trait. So in blacken_object it should enum all GcRef field.

    fn trace_references(&mut self) {
        while let Some(pointer) = self.grey_stack.pop() {
            self.blacken_object(pointer);
        }
    }

Sweep

if the object is not marked release the object from heap.

    fn sweep(&mut self) {
        let mut previous: Option<NonNull<GcObject>> = None;
        let mut current: Option<NonNull<GcObject>> = self.first;
        while let Some(mut object) = current {
            unsafe {
                let object_ptr = object.as_mut();
                current = object_ptr.next;
                if object_ptr.marked {
                    object_ptr.marked = false;
                    previous = Some(object);
                } else {
                    if let Some(mut previous) = previous {
                        previous.as_mut().next = object_ptr.next
                    } else {
                        self.first = object_ptr.next
                    }
                    Box::from_raw(object_ptr);
                }
            }
        }
    }