VO bit and ImmortalSpace

[wks]

TL;DR: VO bits for dead objects in the ImmortalSpace are never cleared. This can lead to crash when using conservative stack scanning.

Problem

If an object is not reached (i.e. traced) during GC, it will not be scanned, and its references will not be forwarded during copying GC. Such objects are considered dead by other spaces, and their VO bits are cleared.

But objects in the ImmortalSpace still have VO bits even if they are not traced. Consequently, during the next GC, if a VM uses conservative stack scanning, and a value on the stack happens to be the address of an object, the stack scanner will consider it as a valid reference because of the VO bit. When the GC tries to scan the "dead immortal" object, it will follow dangling pointers and will crash.

Solutions

There are basically two solutions, namely (1) keeping immortal objects immortal, or (2) letting immortal objects die.

Keeping all objects in the ImmortalSpace alive

This will make all objects in the ImmortalSpace actually "immortal" as in English, i.e. live forever, never die. We will need a different definition of "live" as discussed in #1275 (comment). We also need to maintain an invariant: Any live object must contain only valid references to other objects (i.e. no dangling references). For the ImmortalSpace, it can be done in multiple ways.

Forcing all objects in the ImmortalSpace to be traced

If we always trace those objects, they will be scanned, and their reference fields will be updated.

There are two ways to do this:

1. MMTk-core maintains an internal root set that includes all objects allocated in the ImmortalSpace.
2. We force the VM binding to keep all objects in the ImmortalSpace in the root set, or to guarantee they are always strongly reachable.

Either way, if we trace all objects in the ImmortalSpace, they (and their children) will be really immortal. For copying GC, their reference fields will always be forwarded.

Method 1 is easier for the VM binding to use, but there will be more engineering required in mmtk-core, and run-time cost in post_alloc. We may also need to provide an API for the VM binding to look up the internal root set.

Method 2 imposes an overhead to the VM binding. But if they are really objects of global scope in the VM and live forever, the VM will keep references to those objects anyway. We may provide an internal root set like Method 1 to do sanity check in debug mode.

Letting the VM forward reference fields of objects in the ImmortalSpace

Instead of keeping all objects in the ImmortalSpace root-reachable, we only require the VM binding to forward the fields of objects in the ImmortalSpace. This can be done in multiple ways, too.

1. The VM binding shall give MMTk-core a list of slots in those objects as roots. That can be done by RootsWorkFactory::create_process_roots_work.
2. The VM binding shall give MMTk-core a list of objects in the ImmortalSpace that contain reference fields as if they were objects directly pointed by roots. This can be done by RootsWorkFactory::create_process_pinning_roots_work. "Pinning" doesn't matter because objects in the ImmortalSpace never moves anyway.
3. As proposed in Custom tracing unit/packet #1137, we provide a way to let the VM binding call trace_object directly on the values of those fields and let the VM binding update those fields.

If the current GC is non-moving (Plan::current_gc_may_move_object() == false), the VM binding needs to do nothing.

This seems to be the cheapest solution. But this requires the VM binding to know about this invariant.

Allow objects in the ImmortalSpace to die.

By doing this, objects in ImmortalSpace will still die, but MMTk simply never reclaim their spaces. But if we take this approach, we need to ensure VO bits are only set on reachable objects after GC. There are multiple ways to do this:

1. Do it like ImmixSpace, there can be two ways:
   a. Reconstructing the VO bits.
   b. Copying over from mark bits. Only usable when using side mark bits.
2. Unset VO bits for dead objects:
   a. Maintain a list of live objects in the ImmortalSpace. Traverse and unset VO bits of dead objects during Release.
   b. Linearly scan the VO bits and unset the VO bit if an object is dead.

It can be done similar to ImmixSpace because ImmixSpace also has lines or blocks that have dead objects but we don't reclaim their spaces.

If objects are usually large (i.e. if the ImmortalSpace is sparse), maintaining a list will be faster. Conversely, if objects are usually small (i.e. if the ImmortalSpace is dense), linear scanning is more efficient.

[wks]

From the result of today's meeting and some discussions in our Zulip channel, I edited this issue and added a section "Letting the VM forward reference fields of objects in the ImmortalSpace", which should be in line with @steveblackburn's suggestion.

[wks]

We can make CommonPlan::immortal optional. It is not provided by default, but if the VM needs it, it can be enabled by a Cargo feature. By doing this, we will force the user to read the documentation of that feature as well as the doc comment of ImmortalSpace. And we can give warnings to the user about dangling references and VO bits. We currently prefer the option of "letting the VM forward reference fields of objects in the ImmortalSpace", and we can emphasize that the VM binding is responsible to ensure there is no dangling pointer visible by the GC or the Mutator.