Write barrier for tagged references

[wks]

TL;DR: Edge::store is not suitable for write barrier. We need an alternative design.

Problem

Currently, the write barrier API and implementation assumes that the value to write into the slot is the object reference itself.

    fn object_reference_write(
        &mut self,
        src: ObjectReference,
        slot: VM::VMEdge,
        target: ObjectReference,
    ) {
        self.object_reference_write_pre(src, slot, target);
        slot.store(target);
        self.object_reference_write_post(src, slot, target);
    }

However, this is not true for VMs where slots that hold object references also have tag bits.

In V8, for example, if an object reference is 0x000002001234abc0, the actual value stored in the slot will be 0x000002001234abc1, with the lowest bit being 1 to indicate that this slot is holding a reference, not a small integer (SMI).

The Edge::store method is intended for forwarding the slot in copying GC. When forwarding, the Edge::store method should preserve the tag bits. Take V8 as an example. If the slot previously holds a strong reference, e.g. 0x000002001234abc1, its tag bits will be 0x000002001234abc1 & 0b11 which is 0b01. After forwarding the object, assume the object is moved to 0x000002005678def0, the new value will be 0x000002005678def0 | (0x000002001234abc1 & 0b11), which is 0x000002005678def1.

However, if the same algorithm is used for the slot.store in the write barrier, it will be a problem. If the slot used to hold a small integer of value 0x20 (32 in decimal), the actual value in the slot will be 0x40 (0x20 << 1). If we store an object reference 0x000002005678def0 to the slot, then it will attempt to store 0x000002005678def0 | (0x40 & 0b11) which is still 0x000002005678def0. Since the lowest bit is 0, V8 will think the slot holds a small integer 0x1002b3c6f78, which is wrong.

Another example is Lua. A Lua slot is a C struct with a tag and a union.

/*
** Union of all Lua values
*/
typedef union Value {
  struct GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
  /* not used, but may avoid warnings for uninitialized value */
  lu_byte ub;
} Value;

/*
** Tagged Values. This is the basic representation of values in Lua:
** an actual value plus a tag with its type.
*/
#define TValuefields	
typedef struct TValue {
  Value value_;
  lu_byte tt_
} TValue;

When forwarding a reference, the Edge::store method only needs to update value_.p; when executing a (full/subsuming) write barrier, it should update both value_.p and tt_.

The crux is, the store operation for updating a slot for forwarding reference is not the same as the store operation to mutate the object graph.

Solutions

One obvious way to solve the problem is calling object_reference_write_pre and object_reference_write_post separately, leaving the actual store operation to the VM.

Another way is leave part of the subsuming write barrier as a callback to a VM-supplied function so that the VM can customise store operation.

Any way, we need to mention in the documentation of Edge::store that it is intended to update the slot for forwarding.

[wks]

The LXR branch added some call sites of store. They are all for updating slots for forwarding the reference after trace_object.

[qinsoon]

In V8, for example, if an object reference is 0x000002001234abc0, the actual value stored in the slot will be 0x000002001234abc1, with the lowest bit being 1 to indicate that this slot is holding a reference, not a small integer (SMI).

In this example, shouldn't the object reference be ObjectReference(0x000002001234abc1)? MMTk will use methods in ObjectModel to get an actual address, and in those methods, the binding can remove the tag and return an address.

[wks]

In V8, for example, if an object reference is 0x000002001234abc0, the actual value stored in the slot will be 0x000002001234abc1, with the lowest bit being 1 to indicate that this slot is holding a reference, not a small integer (SMI).

In this example, shouldn't the object reference be ObjectReference(0x000002001234abc1)? MMTk will use methods in ObjectModel to get an actual address, and in those methods, the binding can remove the tag and return an address.

In my opinion, an ObjectReference seen by MMTk-core should be "an actual address". The tag bits belong to the slot, not the ObjectReference. The tag bits 0b01 indicate the slot is holding a reference, not a SMI. If the tag bits are 0b11, it means the slot is holding a weak reference. In this case, the ObjectReference is still 0x000002001234abc0, but because the slot is weak, the slot should be visited again after computing transitive closure, and the slot should be cleared if the object at 0x000002001234abc0 is not reachable.

[qinsoon]

In V8, for example, if an object reference is 0x000002001234abc0, the actual value stored in the slot will be 0x000002001234abc1, with the lowest bit being 1 to indicate that this slot is holding a reference, not a small integer (SMI).

In this example, shouldn't the object reference be ObjectReference(0x000002001234abc1)? MMTk will use methods in ObjectModel to get an actual address, and in those methods, the binding can remove the tag and return an address.

In my opinion, an ObjectReference seen by MMTk-core should be "an actual address". The tag bits belong to the slot, not the ObjectReference. The tag bits 0b01 indicate the slot is holding a reference, not a SMI. If the tag bits are 0b11, it means the slot is holding a weak reference. In this case, the ObjectReference is still 0x000002001234abc0, but because the slot is weak, the slot should be visited again after computing transitive closure, and the slot should be cleared if the object at 0x000002001234abc0 is not reachable.

I don't see it in that way. It is a tagged object reference. It is still an object reference, and the tag is a part of the object reference. Besides, ObjectReference is opaque to MMTk so it does not have to be 'an actual address'. MMTk only accesses it through methods implemented by the bindings, and the binding has flexibility about its definition on the object reference. However, I am not certain that the current code works properly in this way (e.g. if we compare equality of object reference, we may have issues).

Anyway, we can think about alternative design. We can define what an ObjectReference is. Whatever works and is simple would be fine.

[wks]

(e.g. if we compare equality of object reference, we may have issues).

Right. If we compare, for example, ObjectReference(0x000002001234abc1) == ObjectReference(0x000002001234abc3), it will be false under our current definition.

I don't think the current definition of ObjectReference (in the Rust code) is the only practical definition, but there are some axioms that every self-consistent definition of object reference must satisfy. One of them is that every object must have a unique ObjectReference because we often compare the equality of ObjectReference values, and we sometimes (e.g. Sanity GC) use ObjectReference as map keys. Therefore V8-style tagged pointer does not satisfy that axiom, but other kinds of tagged pointer may. I'll collect previous discussions and enumerate those axioms so that we may re-start the discussion in the future (maybe not the near future).

[qinsoon]

One of them is that every object must have a unique ObjectReference because we often compare the equality of ObjectReference values

You are right that our current code assumes there is a unique ObjectReference for each object. But be aware that the code may not be correct. If the conclusion is based on the current code, the conclusion may not be correct as well.

If we agree that we should not assume a unique ObjectReference, we should fix the code. Making a rule about ObjectReference based on the code does not seem to be a good idea.