Non-null slots (Edge) that don't contain object references, either.

[wks]

TL;DR: If a slot can hold things other than valid references and 0 (usually represent null), the current ProcessEdgesWork implementations cannot support it. But it is necessary for VMs that use tagged reference, such as CRuby. To solve the problem, we need to

• Let ProcessEdgesWork::process_edge return immediately if a slot (Edge) reports it holds null, or
• Add a method Edge::update(updater: FnOnce(ObjectReference) -> Option<ObjectReference>) so that the VM binding implement it and decide whether to call trace_object depending on whether the slot actually holds an object reference.
• (Optional) Remove ObjectReference::NULL because there is no uniform way to represent null references. Enforce that ObjectReference is always valid, and use Option<ObjectReference> for nullable object reference.

Problem: tagged references

In Ruby, a slot holds a tagged reference. It can store small integers, special values (such as true, false and nil), etc. in addition to valid object references. And, in fact, nil is not represented as numerical 0. It is represented as 4, and false is represented as 0. Other values (such as small integers) have bit tags such that the last three bits are not all 0.

OK with object-enqueuing

Previously, the Ruby VM only uses Scanning::scan_object_and_trace_edges, and bypassed Edge completely. Because the loading, tracing and storing is totally implemented by the binding, there is no problem handling slots that hold non-reference values. The following code snippet is an excerpt from my work-in-progress mmtk-ruby binding that traces an array in a loop.

    fn scan_and_trace_array_slice<OT: ObjectTracer>( // called by `scan_object_and_trace_edges`
        array_begin: Address,
        array_len: usize,
        object_tracer: &mut OT, // Provides the `trace_object` method
    ) {
        for index in 0..array_len {
            let elem_addr = array_begin.add(index * SIZEOF_VALUE);
            let elem = unsafe { elem_addr.load::<usize>() }; // Load from the slot, done in the binding
            let ruby_value = VALUE(elem);
            if !my_special_const_p(ruby_value) { // Test it the slot holds a "special constant" (i.e. not an object reference)
                let objref = ObjectReference::from(ruby_value);
                let new_objref = object_tracer.trace_object(objref); // Call trace_object only if it holds object reference.
                if new_objref != objref {
                    unsafe { elem_addr.store(new_objref) } // Stor into the slot, done in the binding.
                }
            }
        }
    }

Not working with slot-enqueuing

Recently I am working on supporting slices (basically an array of slots), and a slice can be iterated to get each slot (as Edge). Then I am facing a problem.

When scanning an object, we enqueue slots (Edge) or slices (MemorySlice). The point is, we don't load from the slots or slices when scanning.

Binding code:

// In the binding
imemo_mmtk_objbuf => { // Scanning the underlying buffer of an array.
    let objbuf_ptr = ruby_value.as_mut_ptr::<IMemoObjBuf>();

    // Compute the beginning and the end
    let len = unsafe { (*objbuf_ptr).capa };
    let begin = unsafe { Address::from_mut_ptr(&mut (*objbuf_ptr).ary as *mut _) };
    let end = begin + len * BYTES_IN_ADDRESS;

    // Make a slice
    let slice = RubyMemorySlice::from(begin..end);

    // Give it to mmtk-core.  Note that we haven't loaded from any slots.
    edge_visitor.visit_slice(slice);
}

The MMTk core will simply iterate through the slice (MemorySlice) and get individual slots (Edge). The processing of each slot is the same as the status quo.

// In mmtk-core
pub trait ProcessEdgesWork:
    Send + 'static + Sized + DerefMut + Deref<Target = ProcessEdgesBase<Self::VM>>
{
    fn process_edge(&mut self, slot: EdgeOf<Self>) {
        let object = slot.load();
        let new_object = self.trace_object(object);
        if Self::OVERWRITE_REFERENCE {
            slot.store(new_object);
        }
    }
}

ProcessEdgesWork simply does load-trace-store for each Edge.

Note that

• process_edge calls self.trace_object(object) immediately after slot.load(), without checking whether object is null or not.
• The trace_object methods of PlanProcessEdges and each concrete space check if object is null or not. But if it is null, those implementations simply return the original object reference. Also note that in MMTk core, an ObjectReference is defined to be null if its value is 0.
• process_edge calls slot.store() regardless of whether it called the trace_object of any concrete space or not. It is a property of the concrete implementation of ProcessEdgesWork. In other words, it blindly writes to the slot regardless of whether object is null or not.

This works for VMs where a slot either holds a valid object reference or null (represented as 0). OpenJDK is one such VM, and it works without problem.

But for Ruby, it is a problem. In Ruby, a slot that holds 0 represents false, and nil is represented as 4. Other non-reference values have non-zero values, too. So it is impossible for the process_edges function shown above to distinguish between slots that hold object references and slots that don't.

The binding can tell mmtk-core whether a slot holds an object reference by returning 0 from Edge::load.

impl Edge for RubyEdge {
    fn load(&self) -> ObjectReference {
        let value = unsafe { self.addr.load::<VALUE>() };

        if my_special_const_p(value) { // If it is a special const (not object reference),
            return ObjectReference::NULL; // then return 0.
        }

        value.into() // Otherwise return the object reference
    }

    fn store(&self, object: ObjectReference) {
        if object.is_null() {
            panic!("Attempt to write null reference to Ruby slot.  Note: nil is 4");
        }
        unsafe {
            self.addr.store::<ObjectReference>(object);
        }
    }
}

By doing this, mmtk-core will see either a valid object reference or a null pointer represented as 0, but not any other tagged non-reference values. However, this is not enough, because ProcessEdgesWork::process_edge will unconditionally store to the slot. If the slot holds any non-reference value, the slot.store(new_object) invocation will overwrite the slot with 0. In Ruby, this bug will manifest as some slots mysteriously become false while it previously holds other values, such as small integers.

Solutions

Simple workaround

One simple workaround is letting ProcessEdgesWork::process_edge ignore null references. That is, if the reference is null, don't call store, or preferrably don't even call trace_object at all.

    fn process_edge(&mut self, slot: EdgeOf<Self>) {
        let object = slot.load();
        if object.is_null() { // If `slot.load()` returns null,
            return; // return immediately.
        }
        let new_object = self.trace_object(object);
        if Self::OVERWRITE_REFERENCE {
            slot.store(new_object);
        }
    }

And we should extend the contract of Edge::load() so that the VM binding is allowed to return ObjectReference::NULL when the slot actually holds a meaningful non-reference value, such as a tagged small integer.

Add an Edge::update method

Another solution is adding a method Edge::update. The semantics is updating the slot with a callback. If the slot doesn't hold a reference, Edge::update (implemented by the binding) won't call trace_object (implemented by mmtk-core) in the first place. With this method available, ProcessEdgesWork::process_edge will call Edge::update instead of calling Edge::load and Edge::store, separately. MMTk-core can provide a default implementation of Edge::update that is based on load and store, so that existing bindings don't need to be changed.

pub trait Edge: Copy + Send + Debug + PartialEq + Eq + Hash {
    // ... load and store defined here

    fn update<F>(&self, updater: F)
    where F: FnOnce(ObjectReference) -> Option<ObjectReference> {
        // The default implementation
        let object = self.load();
        if object.is_null() {
            return; // Return immediately if it is null.  But the VM can override this method to return if it holds a small integer, too.
        }
        let maybe_new_object = updater(object); // Call the updater, implemented by mmtk-core
        if let Some(new_object) = maybe_new_object {
            self.store(new_object); // Call `store` only if the `updater` chooses to store.
        }
    }
}

And ProcessEdgesWork::process_edge will call the updater instead.

    fn process_edge(&mut self, slot: EdgeOf<Self>) {
        slot.update(|object| {
            debug_assert_ne!(object, ObjectReference::NULL); // If the updater is called, it is guaranteed not to be null.
            let new_object = self.trace_object(object);
            if Self::OVERWRITE_REFERENCE {
                Some(new_object) // Choose to store
            } else {
                None // Choose not to store
            }
        });
    }

For Ruby, it will work as well as ignoring ObjectReference::NULL returned from slot.load(). For other VMs where slots hold object references together with a tag, the update method will have an advantage. It can cache the tag obtained from the load, and re-apply the tag before storing the updated object reference into the slot. With separated load and store calls, however, the store operation will need to load from the slot again to retrieve the tag, because MMTk-core assumes ObjectReference is an address to somewhere in the object, and is not aware of tags.

Removing ObjectReference::NULL

One aggressive refactoring we may do is removing ObjectReference::NULL, and require all ObjectReference in mmtk-core to be valid (i.e. not null). Reasons are:

• Not all languages have null pointers. For example:
  • Haskell: a functional language with explicit Maybe type
  • Python: None is a proper object
• Even if a language does, there is no common way to represent null pointers. For example:
  • CRuby: nil is 4, false is 0
• And reference slots may hold tagged non-reference values which shouldn't be scanned, either. For example:
  • CRuby: a VALUE type (alias of unsigned long) can hold object reference, small integer, true, false, nil, symbols, etc.
  • V8: a variable can hold an object reference or a small integer (SMI)

From MMTk core's point of view, a slot either holds an object reference or not. If it does not, MMTk core should simply skip it.

In Rust, the type to represent the absence of something is Option<T>. We should use Option<ObjectReference> in places where there may or may not be an object reference, such as the return value of Edge::load(), and the result of ObjectReference::get_forwarded_object (which already returns Option<ObjectReference>).

We can further require ObjectReference to be non-null, which is reasonable because no valid object can be allocated at zero address or any very low address. Then ObjectReference can be backed by std::num::NonZeroUsize instead of usize, so that Option<ObjectReference> will have the same layout as Option<NonZeroUsize> which has the same size as usize. See: https://doc.rust-lang.org/std/num/struct.NonZeroUsize.html and https://doc.rust-lang.org/std/option/index.html#representation

Then no space needs to check for NULL reference in any of the trace_object methods because it is guaranteed to be non-null in the first place. Actually they shouldn't check for null even for now, because the dispatcher (SFT or the if-else chain derived from PlanTraceObject) will not dispatch null to any spaces.

There is only one case where references need to be cleared during GC. It is when processing weak references and finalizers. But those clearing operations should be VM-specific. Currently it is implemented by ReferenceGlue::clear_referent which is VM-specific, anyway.

Since this is not a trivial workaround, we need to discuss though this in the group as a design question.

[wks]

The old issue #626 proposed a function fn decode_tagged_reference(tls: VMWorkerThread, object: ObjectReference) -> Option<ObjectReference>, which attempted to solve the same problem. It is equivalent to letting Edge::load return ObjectReference::NULL to indicate that the slot doesn't contain an actual object reference.