Heterogenous Garbage Collection

Robert O'Callahan, March 23, 2001

The Problem

There are many different strategies for managing memory. In modern software systems, we frequently encounter multiple subsystems sharing an address space, with memory references crossing address spaces, and we would like each subsystem to be able to use its own memory management strategy. To date this problem has been solved in one of two ways: by imposing a reference counting discipline on all subsystems, or by having all subsystems use a shared tracing GC implementation. The first approach gives some flexibility to the subsystems but makes it impossible to reliably collect cycles that span subsystems. The second approach makes it very difficult for subsystems to use their preferred style of memory management.

A Solution

I propose a method for heterogenous garbage collection. Each subsystem manages a portion of the address space. We maintain a map from virtual memory regions to subsystems. We periodically perform "global mark and sweep" to reclaim dead objects. The global algorithm treats each subsystem as a black box implementing a certain interface, described below. Each subsystem is free to collect memory in its own way; copying GC, incremental GC, distributed GC, conservative GC and even reference counting are all allowed.

interface Subsystem {
    /* Begin a global GC phase. */
    void BeginGlobalGC();

    /* Get the next external object reference held by this subsystem.
       Return null if no more object references are held. */
    ptr GetNextExternalReference();

    /* Mark an object as referenced by another subsystem. */
    void MarkObject(ptr p);

    /* Notify that an object has been marked live. Used to keep track of weak
       references. */
    void NotifyObjectMarked(ptr p);

    /* All unmarked objects are unreachable. Move them to finalization queue
       if necessary. */
    void DoFinalization();

    /* End the global GC phase; all dead objects can be reclaimed,
       and any weak references referring to dead objects (i.e.,
       objects for which we never saw a NotifyObjectMarked) can be dropped */
    void SweepGlobalGC();
}

The code for the global algorithm is as follows:

MarkExternals() {
    boolean done = false;
    while (!done) {
        done = true;
        for each subsystem S {
            ptr p;
            while (true) {
                p = S.GetNextExternalReference();
                if (p == null) break;
                done = false;
                S2 = subsystem for p;
                S2.MarkObject(p);
                for each subsystem S2 { S2.NotifyObjectMarked(p); }
            }
        }
    }
}

GlobalGC() {
    for each subsystem S { S.BeginGlobalGC(); }
    MarkExternals();
    for each subsystem S { S.DoFinalization(); }
    MarkExternals();
    for each subsystem S { S.SweepGlobalGC(); }
}

Obviously, a real implementation would need to optimize by reducing unnecessary notifications, batching notificiations, etc.

There are several ways one could implement a subsystem:

• Mark and sweep GC (conservative or exact): This should be obvious.
• Copying GC: This should be obvious too.
• Reference counting: Maintain a list of all objects referenced by some other subsystem (the Export-list), and all external objects this subsystem references (the Import-list). The Export-list can be rebuilt during global GC and maintained between GC phases by proxy code. We keep the reference count incremented for all objects on the Export-list, so during DoFinalization any objects that left the Export-list during the phase have their reference counts decremented; zero-reference objects are reincremented and moved to a finalization queue where they can be removed and destroyed later. The Import-list is maintained by proxy code that responds to AddRef/Release calls on proxy objects. The Import-list can be treated as a root set, so GetNextExternalReference will iterate through the Import-list. All this work can be done by proxy code wrapping an opaque object system (e.g., COM).

  This approach means that cycles passing through reference counting spaces won't be collected, but there's not much anyone can do about that.

• Custom: Subsystems are free to implement custom tracing code. For example, we could have a dedicated cache subsystem that we know doesn't have to be traced because it's all binary data. Or we could have subsystems dedicated to other data structures with specific tracing behavior that we implement.

Concurrent or incremental collectors fit into this framework, as long as we prohibit direct access to object contents from other subsystems. They just can't discard objects that are reachable from external references until the global GC phase occurs. We can even run local GC more often than the global GC if we want, as long as we can synchronize with calls into the collecting subsystem while GC is running.

Rather than deal with reentrancy issues, I have just assumed that any data structure traversal will be implemented by the subsystems using some sort of coroutines. This should work out reasonably well since a lot of GC algorithms use an explicit stack or else have tricks like pointer reversal to avoid having an explicit stack.

This scheme allows subsystems to implement very general weak reference schemes, for example weak hash tables.

Threading Issues

The global algorithm is meant to be executed synchronously and all other threads must be stopped. (The algorithm could easily be parallelized, however, since each subsystem operation can only affect the state of that subsystem.) If heavily-used subsystems use incremental GC or just run their own GC periodically, we shouldn't have to run global GC too often.