How are memory references located in a moving garbage collection implementation?

Question

In a moving Garbage Collector, it is imperative that a precise method of distinguishing between which values on the stack and heap are references, and which are immediate values. This is a detail that seems to be glossed over in most of the literature I have read on garbage collection.

I have investigated whether assigning some preamble to each stackframe would work, for example, describing each argument before it is called. But surely all this does is move the problem to an upper level of indirecton. How does one then distinguish the preamble from the stack frame when traversing it for immediate values or references during a GC cycle?

Could somebody explain how this is implemented in the real world?

Here is an example program of this problem using a first class function lexical closure and a diagram of its stack frame and and parent's environment located on the heap:

An example program

def foo(x) = {
    def bar(y,z) = {
        return x + y + z
    }
    return bar
}


def main() = {
    let makeBar = foo(1)
    makeBar(2,3)
}

Bar's stackframe at point of invocation:

In this example, bar's stack frame has a local variable, x, which is a pointer to a value on the heap, where as the arguments y and z are immediate integer values.

I read that Objective CAML uses a tag bit for each value placed on the stack which prefixes each value. Allowing a binary ref-or-imm check to be made on each value during a GC cycle. But this can have some unwanted side-effects. Integers are restricted to 31 bit and dynamic code generation for primitive calculations would need to be adjusted to compensate for this. In short - it feels a bit too dirty. There must be a more elegant solution.

Is it possible to know, and access this information statically? Such as passing the type information to the garbage collector somehow?

Answer 1

Could somebody explain how this is implemented in the real world?

There are several possible approaches

• conservative stack scanning. everything is treated as a potential pointer. this causes a GC to be imprecise. Imprecise scanning prevents objects from being relocated, which in turn prevents or complicates the implementation of semi-space/compacting GCs.
• mark bits as you have mentioned. this can be considered slightly-less-conservative scanning, but it is still imprecise
• the compiler retains knowledge of the exact stack layout, i.e. where pointers are located, at any given time. Since this can change from instruction to instruction and pointers can also reside in registers this would be very complex.
  As a simplification it is only done for specific points at which all threads can cooperatively hand over control to the GC with a known stack layout when a GC is requested by another thread. This is called a safepoint (explained below).
• other mechanisms might be possible, e.g. partitioning the stack into reference and non-reference entries and always ensuring that enregistered references are also somewhere on the stack, but i don't know how practical that approach is

Gil Tene has a nice, albeit mostly JVM-specific explanation of what a safepoint is, so i'll quote the relevant parts here:

Here is a collection of statement about "what is a safepoint" that attempt to be both correct and somewhat precise:

1. A thread can be at a safepoint or not be at a safepoint. When at a safepoint, the thread's representation of it's Java machine state is well described, and can be safely manipulated and observed by other threads in the JVM. When not at a safepoint, the thread's representation of the java machine state will NOT be manipulated by other threads in the JVM. [Note that other threads do not manipulate a thread's actual logical machine state, just it's representation of that state. A simple example of changing the representation of machine state is changing the virtual addresss that a java reference stack variable points to as a result of relocating that object. The logical state of the reference variable is not affected by this change, as the reference still refers to the same object, and two references variable referring to the same object will still be logically equal to each other even if they temporarily point to different virtual addresses].

[...]

7. All [practical] JVMs apply some highly efficient mechanism for frequently crossing safepoint opportunities, where the thread does not actually enter a safepoint unless someone else indicates the need to do so. E.g. most call sites and loop backedges in generated code will include some sort of safepoint polling sequence that amounts to "do I need to go to a safepoint now?". Many HotSpot variants (OpenJDK and Oracle JDK) currently use a simple global "go to safepoint" indicator in the form of a page that is protected when a safepoint is needed, and unprotected otherwise. The safepoint polling for this mechanism amounts to a load from a fixed address in that page. If the load traps with a SEGV, the thread knows it needs to go to enter a safepoint. Zing uses a different, per-thread go-to-safepoint indicator of similar efficiency.

[...]