ProcessEdgesWork must die

[wks]

TL;DR: There is no common way of processing edges. ProcessEdgesWork is not really common. It is only common to full-heap tracing GC. What's worse, the current stack-scanning API (Scanning::scan_xxxx_root) depends on this trait.

And ProcessEdgesBase must die, too.

TODO list

• Convert ProcessEdgesWork into a concrete work packet for tracing.
  • (dependency) Remove trace: impl TransitiveClosure from trace_object. Remove TransitiveClosure param from Space::trace_object and Scanning::scan_object #559
• Change the stack-scanning API to not depend on ProcessEdgesWork. Decouple root scanning from ProcessEdgesWork. #598

Problem

There is nothing in common among edge-processing work packets.

From the name ProcessEdgesWork, we infer that it represents a work packet that processes edges. But, seriously, what's in common for all work packets that process edges? Nothing.

Currently, ProcessEdgesWork has several algorithms or abstract methods built-in:

1. Load from an edge, call trace_object, and (optionally) store back to the edge.
2. Collect all nodes that have been enqueued by trace_object, and create (and optionally execute) a ScanObjects work packet.

Are they common to all work packets that process edges? Well, they are, for common stop-the-world full-heap tracing GC. All such GC algorithms, including MarkSweep, MarkCompact, SemiSpace, Immix, GenCopy, GenImmix (that is, everything we have in the current master branch), do tracing like this.

1. Nursery GC customises the trace_object. It only traces objects in the nursery. Currently, GenNurseryProcessEdges is the only hand-written plan-specific ProcessEdgesWork implementation.
2. Non-tracing GC algorithms may apply inc/dec to objects pointed by the edges, but does not do trace_object and enqueuing, and certainly not recursively scanning objects and processing edges beyond them.

The stack-scanning interface is tightly coupled with ProcessEdgesWork.

The Scanning::scan_xxxxx_root methods take a <E: ProcessEdgesWork> type parameter. The VM is supposed to create work packets that implements ProcessEdgesWork. Given that ProcessEdgesWork is not general enough, this can be harmful for GC algorithms that does not match what the current ProcessEdgesWork is designed for.

The following snippet is from https://github.com/wenyuzhao/mmtk-core/blob/lxr-merge/src/util/cm.rs#L206

pub struct CMImmixCollectRootEdges<VM: VMBinding> {
    base: ProcessEdgesBase<VM>,
}

impl<VM: VMBinding> ProcessEdgesWork for CMImmixCollectRootEdges<VM> {
    type VM = VM;
    const OVERWRITE_REFERENCE: bool = false;
    const RC_ROOTS: bool = true;
    const SCAN_OBJECTS_IMMEDIATELY: bool = true;

    fn new(edges: Vec<Address>, roots: bool, mmtk: &'static MMTK<VM>) -> Self {
        debug_assert!(roots);
        let base = ProcessEdgesBase::new(edges, roots, mmtk);
        Self { base }
    }

    fn trace_object(&mut self, _object: ObjectReference) -> ObjectReference {
        unreachable!()
    }

    #[inline]
    fn process_edges(&mut self) {
        debug_assert!(crate::args::CONCURRENT_MARKING);
        if !self.edges.is_empty() {
            let mut roots = vec![];
            for e in &self.edges {
                roots.push(unsafe { e.load() })
            }
            let w = ImmixConcurrentTraceObjects::<VM>::new(roots, self.mmtk());
            self.mmtk().scheduler.postpone(w);
        }
    }
}

From the code snippet above, we observe that:

1. self.base is completely unused. CMImmixCollectRootEdges implements ProcessEdgesWork for the sole reason that it needs to be passed to root-scanning functions.
2. The behaviour of CMImmixCollectRootEdges does not fit the design of ProcessEdgesWork. The trace_object function is left unimplemented!() because CMImmixCollectRootEdges does not trace objects at all. It does not flush the object buffer base.node, either.

What should we do?

We should convert the current ProcessEdgesWork trait into a concrete work packet. The behaviour of trace_object may differ according to the strategy of delegating trace_object to the appropriate space. We can choose from

1. PlanTraceObject
2. SFT
3. trace the nursery only (generational collectors)

We can parameterise the work packet (using generics and/or data parameters) to customise the strategy.

We should also change the root-scanning API to decouple it from ProcessEdgesWork. The goal is, stack-scanning interface should only present to the mmtk-core lists of edges. Concretely, the edges can be

• mutable edges: root edges (stack slots, global variables) that holds references that can be updates if the GC moves the object.
• immutable edges: root edges that cannot be changed due to conservative scanning or VM limitations.

The root-scanning API must not dictate what kind of work packets mmtk-core should create to handle the root edges. Particularly, the API should not force the work packets created for handling those root edges implement the ProcessEdgesWork trait. The kind of work packets should be decided by the plan. As a result, CMImmixCollectRootEdges should not need to implement ProcessEdgesWork, or embed ProcessEdgesBase inside it, because the stack-scanning API no longer require it.

There is some proof-of-concept work going on: #598 From the code, we see it is easier to refactor ProcessEdgesWork before fixing the root-scanning API, or to do the two refactoring at the same time.

Dependencies

It will be easier if we remove the trace: impl TransitiveClosure parameter from trace_object first. Currently, this trace: impl TransitiveClosure parameter forms a two-way dependency between ProcessEdgesWork and trace_object, because trace_object will call back to ProcessEdgesWork::process_node. See #559