Generalise edges

[wks]

TL;DR: An edge may not be just *mut ObjectReference.

• With CompressedOops, it can be *mut u32;
• In Julia, it can be {pointer: *mut ObjectPointer, offset: usize};
• In Ruby, the VM calls the GC with the field value, and the GC returns the new field value, so an edge is virtual.

We generalise edges into a EdgeShape trait with two methods: load and store. mmtk-core only depends on these two abstract operations, and the VM defines the concrete representation of edges.

Problem

An edge is a reference field. An edge holds a reference to an object (can be null). Edges can be in an object, on the stack, or in other locations.

Currently, MMTk Core assumes an edge is a memory slot of the size of ObjectReference (word sized). For example, the following snippet is from mmtk-core:

    #[inline]
    fn process_edge(&mut self, slot: Address) {
        let object = unsafe { slot.load::<ObjectReference>() };
        let new_object = self.trace_object(object);
        if Self::OVERWRITE_REFERENCE {
            unsafe { slot.store(new_object) };
        }
    }

Here slot is just an address. When loading, it assumes the slot holds a word-sized data, and is directly interpreted as an ObjectReference. When storing, the new ObjectReference is written into the slot.

This is not general enough. In VMs, an edge may not be simply a memory slot that holds an ObjectReference.

Compressed oops

OpenJDK supports "compressed oops". On 64-bit systems, the JVM can limit the heap size to 32GB and require 8-byte alignment so that a pointer to an object only has 32 effective bits (See: https://www.baeldung.com/jvm-compressed-oops). By doing this, each object reference only occupies 32 bits of space instead of 64 bits. The VM becomes more space-efficient at the cost of some computation overhead.

• Loading an object reference from a slot that holds a compressed pointer needs bit operation: objref = ((*compressedOop) << 3).
• Storing an object reference into such a slot also needs bit operation: *compressedOop = objref >> 3 (assuming bits in objref[63..35] are all zero).

Julia: pointer with offset

Sometimes a Julia array may hold a pointer to the middle of its underlying buffer, and record the offset from the beginning of the buffer to the pointer. This is convenient for the "soft deletion" of elements in the beginning of the array (See JuliaLang/julia#43056).

A simplified version of it is shown below:

struct IntArray {
    int *buffer;
    int offset;

    IntArray(size_t sz): buffer(new int[sz]), offset(0) {}
    ~IntArray() { delete buffer - offset; }
    void delete_begin(size_t n) { buffer += n; offset += n; }
    int get(size_t n) { return buffer[n]; }
    void set(size_t n, int v) { buffer[n] = v; }
};

In this case, if we load from the buffer field, we get the pointer to the middle of the buffer. But

1. The GC expects a pointer to the beginning of the allocated buffer in order to trace it.
2. If the GC moved the buffer, it shall update the buffer field. But it needs to preserve the offset, so buffer still points to the same offset of the allocated buffer after the GC, and the application must not be aware of GC happening.

Ruby: user-supplied mark and compact functions

In Ruby, an object can be defined by a C extension. The C program defines the object layout, and the programmer provides a C function to scan the object and, optionally, update the field if the GC moves the object.

struct Foo {
    Bar unrelated_field;
    VALUE field1;
    VALUE field2;
};

void foo_dcompact(struct Foo *obj) {
    obj->field1 = rb_gc_location(obj->field1);
    obj->field2 = rb_gc_location(obj->field2);
}

The code above is provided by third-party C extensions which we cannot control. Because of this, even if we can re-implement rb_gc_location for MMTk, the GC doesn't get the address of the field. It only gets the value held in the field. The GC cannot directly store into the field, either. It needs to return the new value to the C code (foo_dcompact in the example above) so it can assign it back to the field.

EdgeShape trait

pub trait EdgeShape {
    fn load(&self) -> ObjectReference;
    fn store(&self, object: ObjectReference);
}

The EdgeShape trait above provides an abstraction of the representation of edges. The mmtk-core only expects it to implement the load and the store methods. For example, the code in ProcessEdgesWork still works even though it does not know the concrete implementation of ES: EdgeShape.

    type ES: EdgeShape;

    #[inline]
    fn process_edge(&mut self, slot: Self::ES) {
        let object = unsafe { slot.load() };
        let new_object = self.trace_object(object);
        if Self::OVERWRITE_REFERENCE {
            unsafe { slot.store(new_object) };
        }
    }

The concrete representation is off-loaded to the VM bindings.

The simplest implementation just holds a pointer to an ObjectReference field. It needs to be loaded and stored atomically for parallel GC.

pub struct SimpleEdge {
    slot_addr: *mut Atomic<ObjectReference>,
}

impl EdgeShape for SimpleEdge {
    fn load(&self) -> ObjectReference {
        unsafe { (*self.slot_addr).load(atomic::Ordering::Relaxed) }
    }

    fn store(&self, object: ObjectReference) {
        unsafe { (*self.slot_addr).store(object, atomic::Ordering::Relaxed) }
    }
}

Compressed oops

We can add bit operations in the implementation of EdgeShape to support Compressed OOPs.

pub struct CompressedOopEdge {
    slot_addr: *mut Atomic<u32>,
}

impl EdgeShape for CompressedOopEdge {
    fn load(&self) -> ObjectReference {
        let compressed = unsafe { (*self.slot_addr).load(atomic::Ordering::Relaxed) };
        let expanded = (compressed as usize) << 3;
        unsafe { Address::from_usize(expanded).to_object_reference() }
    }

    fn store(&self, object: ObjectReference) {
        let expanded = object.to_address().as_usize();
        let compressed = (expanded >> 3) as u32;
        unsafe { (*self.slot_addr).store(compressed, atomic::Ordering::Relaxed) }
    }
}

Julia-style offset edge

Similarly we can embed the offset in the edge, and compute the object reference from the address held in the slot.

pub struct OffsetEdge {
    slot_addr: *mut Atomic<Address>,
    offset: usize,
}

impl EdgeShape for CompressedOopEdge {
    fn load(&self) -> ObjectReference {
        let middle = unsafe { (*self.slot_addr).load(atomic::Ordering::Relaxed) };
        let begin = middle - self.offset;
        unsafe { begin.to_object_reference() }
    }

    fn store(&self, object: ObjectReference) {
        let begin = object.to_address();
        let middle = begin + self.offset;
        unsafe { (*self.slot_addr).store(middle, atomic::Ordering::Relaxed) }
    }
}

Ruby-style call-back edge

This is a bit tricky. Introducing a special edge alone cannot solve the problem. But we can still represent it as an edge, and use the edge struct to temporarily hold the new value.

pub struct ValueEdge {
    value: ObjectReference,
    new_value: &mut ObjectReference,
}

impl EdgeShape for ValueEdge {
    fn load(&self) -> ObjectReference {
        self.value
    }

    fn store(&self, object: ObjectReference) {
        *self.new_value = object
    }
}

Then we can implement the rb_gc_location function like this:

pub fn rb_gc_location(obj: ObjectReference) -> ObjectReference {
    let mut new_value = obj;
    let edge = ValueEdge { value: obj, new_value: &mut new_value };
    process_edges_work.process_edge(edge);
    new_value
}

But probably we should directly call trace_object instead. The problem is, this edge is only usable during this function call (and Ruby's lifetime mechanism clearly identifies that new_value does not live long enough for the process_edges_work work packet which may be scheduled on a worker at any time in the future). I think we need a different work packet, probably named ProcessNodesWork, to support Ruby.