Rename `is_reachable` and `is_live`

[wks]

TL;DR:

• "Is reachable" and "is live" are wrong questions to ask during tracing, and what ObjectReference::is_reachable() really does is querying whether an object has been reached during tracing. We need better questions and better function names.
• In StickyImmix, object.is_reachable() returns true if object is mature and we haven't reached it. This is wrong and should be fixed.

Problem

As I was writing the finalization and weak references chapter of the porting guide, I realized that the word "reachable" may not be meaningful during tracing.

We say an object is "reachable" if there is a path from roots to that object. We can even define "strongly/softly/weakly/phantomly reachable" if there are soft/weak/phantom references. But all those definitions of reachability are about the state of an object in an object graph. If an object is strongly reachable, it is always strongly reachable before, during or after a GC. The reachability only changes if the mutator mutates the object graph.

But during tracing, what we really care about is whether an object has been reached. MMTk-core processes weak references and finalizers in two ways

1. Using the old API, we run the strong Closure, then SoftRefClosure, then WeakRefClosure, then FinalRefClosure, then PhantomRefClosure.
2. Using the new API, we run the strong Closure, then we run Scanning::process_weak_ref multiple time, each processing a different weak reference strength.

In either way, after a previous closure is finished, we ask "Is this object already reached in previous closures?", and we ask this by calling ObjectReference::is_reachable(). Note that this question is different from "Is this object softly/weakly/phantomly reachable?".

• During tracing, the state of object.is_reachable() changes as we gradually trace through one reference after another, but
• whether an object is softly/weakly/phantomly reachable only depends on the shape of the object graph, and MMTk only knows this after each level of transitive closure is complete.

The current method ObjectReference::is_reachable() actually returns whether an object is reached. It answers the question we want to ask (i.e. whether the object is reached), but the method name is_reachable() is wrong.

Similarly, ObjectReference::is_live() is also wrong. The life and death of objects is not determined until the end of all tracing stages.

New names

ObjectReference::is_reachable() should be renamed ObjectReference::is_reached().

• Scope: It can be called during tracing, i.e. from the TPinningClosure to the VMRefClosure work buckets.
• Semantics: It returns true if an object has been traced (i.e. reached by trace_object) in this GC since tracing started.

ObjectReference::is_live() should be renamed ObjectReference::is_retained().

• Scope: Same as is_reached.
• Semantics: It returns true if either is_reached() returns true, or the GC will retain this object for other reasons, for example,
  • The object is in the immortal space. (No. It is not safe to keep a weak reference to an un-reached object even if it is in the immortal space. See below)
  • The object is in the mature space during a nursery GC.

Which to call when handling weak references, is_reached or is_retained?

It should be is_retained(). Suppose there is an old object o1, and a young WeakReference named y1 which weakly references o1. During a nursery GC, we will not trace o1 because it is in the mature space. This means o1 will not be reached during this nursery GC. However, because nursery GCs never reclaim old objects (i.e. they assume old objects are all alive), the weak reference y1 must not be cleared. In fact, a path from root to o1 may exist, going through multiple mature objects before reaching o1. So o1 can be alive according to the object graph even though we don't trace it.

On the contrary, is_reached() shall return false if we didn't trace the old object.

However, the current implementation of ObjectReference::is_reachable() simply calls SFT::is_reachable() which in turn calls SFT::is_live(). For StickyImmix SFT::is_live() checks the mark bit which is always set for mature objects (hence the name "sticky"). So object.is_reachable() will still return true if object is a mature object, which is technically wrong! We should make the semantics clear and suggest not to use is_reachable (or the renamed is_reached) for weak reference processing.

How do we implement is_reached for StickyImmix?

With sticky mark bits, StickyImmix cannot distinguish between (1) old objects retained in previous nursery GCs and (2) young objects just marked during the current GC. If we have to distinguish between them, we may need a different metadata bit. But that seems unnecessary.

If it is unnecessary to ask "whether an object is reached during the current GC", we may delete the is_reachable() method, and keep is_alive() (and rename it to is_retained()).

Are objects in the immortal space always live (or retained)?

Not really. Although we never reclaim any space from the ImmortalSpace, we can't assume all objects in the ImmortalSpace are live.

Suppose the plan is SemiSpace and each GC moves every single object in the two copy spaces. If an object o1 in the ImmortalSpace has a reference to an object o2 in the from-space, then the field needs to be traced and forwarded so that it will continue to reference the same object in the to-space. This will only happen if o1 is reachable from root.

On the contrary, if o1 is not reachable from root, it will not be traced, and it will not be scanned, and its fields will not be forwarded. Then o1 will contain dangling pointers. If we keep a weak reference to o1, mutators may convert it to a strong reference and see dangling pointers. This will crash!

So the current is_live() for ImmortalSpace that always returns true is not suitable for weak reference processing. The current implementation of is_reachable() for ImmortalSpace, on the other hand, returns true only if the object is reached. That's correct w.r.t. weak reference processing.

But then is_retained() will not be a perfect name because we never reclaim any objects in the immortal space. In this sense, all objects in the ImmortalSpace are "retained" (although not all objects in the ImmortalSpace are in good shape).

[wks]

We discussed this topic in the meeting today. We acknowledged that there is a difference between "reached" and "reachable". The actual reachability can only be determined by a full-heap tracing, which is impractical for a light-weight API call like ObjectReference::is_reachable(). What the current is_reachable() really returns is a conservative estimation of reachability. Specifically, generational GCs, estimate that all objects in the mature space are reachable. What's worse, a reference from a dead old object to a young object will promote the young object even if both the old and the young objects are dead. (This can happen if the mutator added such a reference then deleted another reference to make the old object unreachable, and the old object holds the only reference to the young object.) This is known as nepotism.

Because of this, is_reachable may be more accurately described as "is assumed to be reachable". But we think the name is_reachable is OK, as long as we add some documents to clarify its actual behavior.

We also acknowledge the problem of dead objects in ImmortalSpace, and that it is unsafe to keep a (strong or weak) reference to an object that hold un-forwarded references. But the ImmortalSpace is a well-known concept in GC.

We realized there is a bug involving the ImmortalSpace and the VO bit. If an object is unreachable, it will not be scanned and its references will not be forwarded. But its VO bit remains. During the next GC, the conservative stack scanner will look at the VO bits. If a value on the stack happens to be the address of a dead immortal object (well, that sounds odd), GC will attempt to trace it and follow its references. Because its references are outdated, the GC will crash. One possible solution is to copy the side mark bits over to the VO bits, or reconstruct the VO bits from scratch, just like the ImmixSpace.

[wks]

What does "live" and "reachable" mean?

According to the GC Handbook, an object is live if it will be accessed at some time in the future execution of the mutator. Of course this is undecidable. And reachability is defined by the existence of a path from root to the object following references. But the GC Handbook also acknowledges that people tend to use live and dead interchangeably with reachable and unreachable, and garbage as a synonym of unreachable.

The JikesRVM MMTk also has isReachable and isLive, and has the same semantics as the Rust mmtk-core. isReachable is the same as isLive, with ImmortalSpace being the only exception. ImmortalSpace.isLive always returns true in JikesRVM MMTk. This behavior does not satisfy the definition of either "live" or "reachable" in the GC Handbook.

In JikesRVM, the doc comments say:

• Space.isLive: Is the object in this space alive?
• Space.isReachable: Has the object in this space been reached during the current collection. This is used for GC Tracing.
• TraceLocal.isLive: Is the specified object live?
• TraceLocal.isReachable: Is the specified object reachable? Used for GC Trace
• ImmortalSpace.isLive: (no doc comment)
• ImmortalSpace.isReachable: Returns if the object in question is currently thought to be reachable. This is done by comparing the mark bit to the current mark state. For the immortal collector reachable and live are different, making this method necessary.

isReachable seems to mean what we described as "reached", plus objects that are "thought to be reachable" by the space. This gives generational plans room for interpreting the "thought to be" and conservatively return true for unreachable mature objects and their young children.

There is no further explanation of what "alive" or "live" mean. From the Git history, the immortal space has been always returning true since the very beginning, and there is no description of why. I think it was a mistake by the initial developers who took it for granted that objects in the immortal space are immortal, which, in English, means being alive forever.

In JikesRVM, ReferenceProcessor.processReference uses isLive to determine if it should forward or clear a WeakReference. In Rust MMTk, ReferenceProcessor::process_reference uses is_live, too. This makes mmtk-core's built-in ReferenceProcessor vulnerable to this problem.

But why it has been fine for JikesRVM for so long?

In JikesRVM, the ImmortalSpace seems to be only used in two cases:

1. In NoGC. This is not a problem because GC never happens.
2. In VMSpace. This is not a problem either because the VMSpace either treats all objects in the VMSpace as directly reachable from roots, or treats all fields of all objects in the VMSpace as roots. This keeps all fields forwarded.

The constant ALLOC_IMMORTAL exists (equivalent to the AllocationSemantics::Immortal in the Rust MMTk), but it is not used anywhere! This means unless any researcher is hacking JikesRVM and deliberately allocate some objects using the ALLOC_IMMORTAL selector, the Space.immortalSpace will always be empty.

But the Rust MMTk provides CommonPlan::immortal and AllocationSemantics::Immortal as part of the public API. This means some VM bindings may deliberately use the immortal space. Julia is one example.

How should we document is_reachable?

I think three things need to be highlighted.

1. We should emphasize that is_reachable doesn't return the actual root-reachability. is_reachable is conservative, and may return true for objects that are not actually reachable from roots, but the plan or policy think it is reachable. This allows mature objects to return true.
2. There is an invariant: for all objects where is_reachable return true, their fields must have been fully forwarded by the end of the GC. This is for the safety of retaining weak references. Specifically, generational plans maintain this invariant by updating old objects in the remembered set.
3. is_reachable is callable from the start of tracing (TPinningClosure) to the end of reference processing (VMRefClosure). The behavior is plan-specific outside that time frame (including mutator time) because different plans may choose to clear the mark bits or forwarding bits at the end of the GC.

What about is_live?

It should be deprecated because it doesn't return whether an object is live (as defined in the GC Handbook). It doesn't even return whether an object is reachable! Specifically, it is wrong to say objects in the immortal space is always live.

All current use cases in mmtk-core and bindings should be changed to is_reachable.

[wks]

After thinking about this problem, I think we don't need to rename is_reachable (just need to clarify), and we can remove is_live. I rewrote the issue in #1275

For the VO bit problem, I made a dedicated issue #1274

I am closing this issue now.