Issues with `TraceKind`

[qinsoon]

We currently use TraceKind (a u8 value) to decouple plan, work packets, and the tracing function in the policy. Basically, a plan creates work packets that carry TraceKind const values. The policy trace objects according to the TraceKind value.

The benefits from this design

1. It decouples plan, work packets and policies. Work packets are general and can be used for multiple plans. Policies are unaware of the plan, and only trace objects according to the TraceKind. In Java MMTk, a plan directly calls to the tracing function in the policies, which no longer works for MMTk core.
2. TraceKind is a const generic parameter, and the Rust compiler can specialize code based on the const. Thus it introduces no overhead.

TraceKind values

Global

255 - DEFAULT_TRACE
254 - TRACE_KIND_TRANSITIVE_PIN

Plan specific

Mark Compact: 0 - TRACE_KIND_MARK, 1 - TRACE_KIND_FORWARD
Immix: 0 - TRACE_KIND_FAST, 1 - TRACE_KIND_DEFRAG

Issues

Conflict of plan specific values

If we use mark compact along with an Immix space, the same TraceKind value will be interpreted differently by each policy. E.g. 0 is marking trace for mark compact, and also the fast trace for Immix. This causes unintended behavior.

Cross product of TraceKind among policies

To solve the previous issue, we could use different values for plan specific TraceKind, such as 0 - TRACE_KIND_MC_MARK, 1 - TRACE_KIND_MC_FORWARD, 2 - TRACE_KIND_IX_FAST, 3 - TRACE_KIND_IX_DEFRAG. This leads to an unreasonable situation that Immix needs to know what to do in a mark compact marking trace.

TraceKind is skipped in some cases

For sticky immix's nursery GC (GenNurseryProcessEdges), we use DEFAULT_TRACE, but Immix does not have code in its tracing function to deal with DEFAULT_TRACE. Instead, GenNurseryProcessEdges calls functions in the plan which specifically calls tracing functions in the policies. This causes confusion.

TraceKind cannot not solely decide the tracing behavior.

The function may_move_objects<const KIND: TraceKind>() -> bool is implemented for each policy, and only uses TraceKind to determine whether the policy may move objects in a trace. When we have two Immix spaces, one for moving, and one for non moving, this function no longer works -- we need information from the space instance to know whether it will move objects or not. Though we can conservatively state that the policy may move objects even if the instance does not really move objects, this causes confusion as well.

Solution

We should remove plan-specific traces, and only have a few defined general TraceKind, and each policy needs to know what to do for such cases. E.g.

TraceKind	Immix	MarkCompact
default	non moving	marking
exhaustive	defrag/moving if the instance allows moving	fall back to default
nursery	not reachable -- handled specifically	not reachable
secondary	fall back to default	forwarding
transitive pinning	non moving	panic

may_move_objects needs to take a self paramter, or conservatively states that it may move objects if it is uncertain.

[k-sareen]

Another problem with TraceKind is that currently Rust requires const generics to be evaluated at compile-time, so we can't use trait/generic constants here. And another further problem is that when I was trying to specialize the code for tracing objects, I just wanted to store function pointers in a table, but the existence of the many generic type-parameters and const generics made that very very difficult.

[qinsoon]

Another problem with TraceKind is that currently Rust requires const generics to be evaluated at compile-time, so we can't use trait/generic constants here.

Yeah that's true. It would be nice if we can use struct or enum as const generics.

I just wanted to store function pointers in a table, but the existence of the many generic type-parameters and const generics made that very very difficult.

We use generics to push the cost to compile-time. We may be able to have a more general but slower version of the functions without certain generics, and do dynamic dispatch at run-time.

[wks]

Another problem with TraceKind is that currently Rust requires const generics to be evaluated at compile-time, so we can't use trait/generic constants here.

Yeah that's true. It would be nice if we can use struct or enum as const generics.

Alternatively we can require each space to implement several methods, including

impl Space for Xxx {
    fn trace_object_default(...) { ... }
    fn trace_object_exhaustive(...) { ... }
    fn trace_object_nursery(...) { ... }
    ...
}

By doing this, we no longer need type args.

I just wanted to store function pointers in a table, but the existence of the many generic type-parameters and const generics made that very very difficult.

We use generics to push the cost to compile-time. We may be able to have a more general but slower version of the functions without certain generics, and do dynamic dispatch at run-time.

We can instead store &'static dyn Space in the SFT.

p.s. I wonder how OpenJDK dispatches the tracing to different spaces (or if it has multiple spaces at all) because OpenJDK's GC is not really slow (in terms of the quality of implementation, not GC algorithms).

[wks]

Oh by the way, can we bring back the TraceLocal from JikesRVM? I think that's just the solution we need. Each GC use a different kind of TraceLocal for all the traceObject calls in the current GC. For example, there are ImmixTraceLocal and ImmixDefragTraceLocal. There are GenNurseryTraceLocal and GenMatureTraceLocal.

What's preventing us from using TraceLocal? I vaguely remember we eliminated TraceLocal in favor for the work packets system. But I think they are orthogonal. We can still have ImmixTraceLocal and ImmixDefragTraceLocal, but during a normal GC, all ProcessEdgesWork work packets reference (or integrate) ImmixTraceLocal instances, while during defrag GC, they reference (or integrate) ImmixDefragTraceLocal instances.

[k-sareen]

p.s. I wonder how OpenJDK dispatches the tracing to different spaces (or if it has multiple spaces at all) because OpenJDK's GC is not really slow (in terms of the quality of implementation, not GC algorithms).

I think even if they have multiple spaces, their basic operations don't change based on the space, i.e. they will always have a mark-bit they will check/mark, etc. I may be wrong, but that's what I recalled looking at ParallelGC a while ago. Plus they usually don't have multiple spaces anyway. See this function that checks if a pointer exists in a heap. I can only find it being used in assertions. They avoid using it for performance critical code.

[wks]

Let me answer my question. There is one TraceLocal implementation per (Plan, TraceKind). It doesn't solve the cross product problem of trace kinds and policies. In JikesRVM, each subclass of TraceLocal only cares about the "main" spaces of a plan. For example, ImmixDefragTraceLocal, overrides the tracing behavior of the ImmixSpace, but relies on super.traceObject (TraceLocal.traceObject) to handle all other spaces, including LOS, code space, non-moving space, etc.

Our SFT is a per-space table, and is by nature a 2-dimensional dispatch table that maps (chunk, TraceKind) pair to a concrete function, more concretely,

Address─────►Chunk────►Space────┐                      
                                ├────►concrete function
TraceKind───────────────────────┘                      

Except currently our SFT cannot handle multiple different trace kinds. But it is easy to refactor once we globally fix the trace kinds.

[wks]

The function may_move_objects() -> bool is implemented for each policy, and only uses TraceKind to determine whether the policy may move objects in a trace.

Maybe we can just remove may_move_object because it is only used in one case, i.e. in PlanProcessEdges::process_slot.

    fn process_slot(&mut self, slot: SlotOf<Self>) {
        let Some(object) = slot.load() else {
            // Skip slots that are not holding an object reference.
            return;
        };
        let new_object = self.trace_object(object);
        if P::may_move_objects::<KIND>() && new_object != object {
            slot.store(new_object);
        }
    }

It was intended as an optimization so that we don't need to compare the return value of trace_object against the existing value in the slot if we know the plan never moves an object. I have a feeling that comparing two local variables won't cost that much. However, if we let may_move_objects ask every space in a plan in order to get the precise information, it will cost way more. In other words, precise information doesn't really help.

[k-sareen]

We can instead store &'static dyn Space in the SFT.

I tried to do this as well. This would still store a u128 into the SFT. Not ideal given we know that the u128 implementation of the SFT is inefficient.

[qinsoon]

We decided that we want to do work packet specialization, i.e. creating work packets that only include objects for a certain policy. In that case, we do not need generalized work packets, and we don't need TraceKind.