# Collaborative Asynchronous Cross-GC Garbage Collection

The following is an algorithm that enables multiple independent garbage collectors to share cross-references into each others' heaps and still ensure that cycles get collected (provided each garbage collector works correctly).
The basic premise is that, while each garbage collector is independent, all cross-references are centrally managed.
The cross-reference manager uses epochs to slowly determine when cross-references are no longer reachable, and the expectation is that the independent garbage collectors will each run many times within an epoch.
This can be viewed as essentially adding a generation that is collectively shared across the independent garbage collectors, and the algorithm has many of the pros and cons of generational garbage collection.

## The Model

Every time a cross-reference between independent garbage collectors is created, it is registered with the cross-reference manager and conceptually split into an out-reference in one heap and an in-reference in another heap.
The cross-reference manager then tracks reachability of cross-references within epochs, relying on the independent garbage collectors to propagate reachability information using an extra color.
That is, in addition to "black" and "white" denoting "reachable from root" and "unreachable" respectively, the algorithm also relies on a "grey" color denoting "reachable from another cross-reference".

### Independent Garbage Collectors

The cross-reference manager tracks the collection of in-references for each independent garbage collector.
Each time an independent garbage collector runs, it enumerates through this collection, treating them as roots into its own heap.
However, whereas its own "local" roots are necessarily "black" roots, in-reference roots can also be "white" (meaning they can be cleaned up) and "grey".
At the start of the run, the garbage collector records the observed color of each in-reference and updates the colors of its internal structures appropriately (with black superseding grey).
At the end of the run, the garbage collector updates the colors of its out-references registered with cross-reference manager.
Then, finally, it indicates to the cross-reference manager that its local roots have been processed *and* specifies the color each in-reference was observed at (which is important because the cross-reference manager might have concurrently updated the color of the in-reference due to new information from another garbage collector).

This means that, at any point after the local roots have been processed, then the color of the out-references is an overapproximation of their reachability from the local roots and the in-references.
The collaborative algorithm is sound so long as just this invariant is maintained, granting a lot of flexibility in how the independent garbage collector does its part.

## The Algorithm

Notice that should an in-reference of a heap become "black", the next run of that heap's garbage collector will propagate that reachability information to the out-references.
The various garbage collectors will run at various times and with various frequencies, but each time they will propagate reachability information between cross-references.
The question is how to take advantage of that propagation.

To that end, the cross-reference manager uses epochs.
At the start of an epoch, all "black" in-references are marked as "grey", the local roots of all heaps are considered to be unprocessed, and all out-references are cleared of any marking.
Then the independent garbage collectors do their work, with the cross-reference manager making sure colors are updated monotonically: "black" and "white" cross-references are never made "grey" (although "black" can become "white" if an independent garbage collector notices its out-reference is no longer needed).
When an independent garbage collector indicates all its local roots have been processed, then all unmarked out-references are marked "white".
After local roots of a heap have been processed, any newly created cross-references into that heap are marked "black".
Each time an independent garbage collector indicates the color at which an in-reference has been processed, the cross-reference manager records the color (again updating it monotonically).

Supposing each independent garbage collector is productive (i.e. given enough time to run and actually update the out-references appropriately), eventually the cross-reference manager will be able to observe a point where all in-references have been processed according to their actual color.
Once that happens, all "grey" cross-references are made "white", and a new epoch is started.

## Guarantees

This algorithm is sound in that cross-references will be made "white" only if it is unreachable.
This algorithm is complete in that cross-references will be kept at the end of an epoch only if it was reachable from a local root at the start of the epoch; thus all unreachable references will eventually be cleaned up provided all independent garbage collectors are given enough time to propogate color information.
Both of these guarantees assume all the independent garbage collectors are implemented correctly.

## Faulty Garbage Collectors

An independent garbage collector can be faulty in one of three ways:
1. It can violate the coloring invariant.
2. It can overapproximate reachability.
3. It can fail to eventually propagate color information even when given reasonable time.

In the first case, the thing it has an out-reference to might get cleaned up in the target heap, which will cause a later attempt to access the associated resource to fail, hurting only the application with the faulty garbage collector.
The second case is inevitable, which is why even garbage-collected languages can have memory leaks; the collaborative algorithm will be only as precise as its constituents.
In the third case, the cross-reference manager can use some heuristic to identify insufficiently unproductive garbage collectors and simply mark all of their out-referenences as "black" in order to clean up at least the references that are not reachable from the unproductive garbage collectors; this essentially falls back to the current worst-case scenario where all out-references in WebAssembly tables are considered to be roots (provided the instance is reachable).