Distributed collection of cycles between vats

[mhofman]

What is the Problem Being Solved?

It's possible to create distributed reference cycles. At its simplest most conceptual form, some exported distributed object Alice holds in its state the imported presence of Bob, which itself hold a reference to Alice in its own state in Bob's vat.

Because exported objects are held strongly by a vat until the vat has been notified that no other vat can reach the object, the local garbage collector cannot claim the imported presence held by the exported object.

To be able to claim the distributed cycles, the local garbage collectors need to collaborate: a vat needs to be able to identify that an imported presence is solely rooted in a set of exported objects, with no other local retaining path to them, and this only if the exported objects are not themselves directly reachable. While I have a design for this kind of garbage collection insight, it requires new APIs beyond what is achievable with with WeakRef / FinalizationRegistry, and changes to the engine's garbage collection logic.

One place where we could collect cycles without engine insight is for virtual objects. Since those are serialized, we can identify the retaining paths, and know when both representatives and presences are finalized. A variation of this is with virtual WeakMap where a presence is only held in the value of a WeakMap for which the key is just recognizable (WeakMap are akin to joined references where the tuple of the WeakMap instance and the key together hold onto the value).

Description of the Design

In both cases, a new / extended syscall is necessary for the vat to inform the outside world that the reachability of an imported reference is solely dependent on a set of exports, none of which are currently reachable locally.

From this information the kernel can reconstruct the distributed object graph, perform cycle detection, and deliver the appropriate dropExports to vats. I do not have concrete ideas on how to extend this pattern to captp, but it's probably along the lines of introducing the machines corresponding to the exported and imported objects, and delegate the collection to them, all that while protecting against re-introduction.

Security Considerations

We need to avoid making a collection decision if there is a possibility that the exported object may be re-introduced to the program, for example through a pending delivery on the object, or because it was stored in a reachable virtual collection.

Test Plan

This definitely requires some tests.

[mhofman]

From the kernel's point of view, a vref is either reachable, merely recognizable or fully retired by a vat. When a vat collects its garbage, it may find that some vrefs are no longer reachable and inform the kernel: drop if they are still recognizable, or retire if the vat does not associate any information to the vrefs. We will explore what objects should be considered recognizable, and how the kernel can perform one shot garbage collection of recognizable vrefs, and ultimately collect cycles.

What is a Recognizable Object

Let's look a little closer at the definitions of reachable and recognizable. Conceptually, recognizable means that the vat has the object somewhere in its object graph, aka it can positively compare its identity to objects in its graph and take an execution path that depends on the object's identity. Reachable is a when an object identity can be observed by the vat's execution using only the objects at the root of the object graph. While conceptually a reachable object is also recognizable, we will use recognizable to denote otherwise non-reachable objects.

Currently, the only objects identified as recognizable are objects held as a WeakMap or WeakSet key. However by looking at the definition above, we realize that objects in the value side of a WeakMap could also be merely recognizable if they are not reachable, aka if the only path to observing the object's identity is through the WeakMap and the key is only recognizable, but not otherwise reachable. Similarly an exported object is merely recognizable if it's exported but the vat's program can no longer reach it without the object being re-introduced in a delivery.

This means that merely recognizable objects are all the objects which can only be observed by using one or more recognizable objects.

Recognizable Root Set

In a single vat system where objects are not exported, there are no merely recognizable objects. When a set of objects becomes merely recognizable, they are in fact unreachable. As such we can focus on objects that participate in the distributed system, with local objects being just paths or edges from one distributed object to another. A recognizable vref denotes a distributed object that is merely recognizable by the vat.

As we've seen, some recognizable vrefs are not recognizable on their own, but only through other recognizable vrefs. Any recognizable vref that allows the observation of a recognizable object is said to be part of its root set. The re-introduction to the vat of a recognizable vref causes all objects which have that vref in their recognizable root set to become immediately reachable again, along with itself of course.

For a recognizable vref used as a WeakMap or WeakSet key, the vref is itself in its own root set, since it's the observation of its object identity that influences the program. WeakMaps actually create a "join" in reachability of values: if an exported vref A contains a WeakMap which associates vref C to the vref key B, then the root for C contains the tuple [A,B]. If either A or B becomes retired, so does C (if no other root exist in C's set).

We can then consider that a recognizable root set is a list of tuples. Most tuples are of size 1, and each vref used as a WeakMap key on the path from the root adds an element to the tuple. If any vref of a tuple becomes retired, the tuple can be removed from the recognizable root set. If the recognizable root set becomes empty, the object becomes retired for that vat.

Distributed Garbage Collection

When a vat finds that a vref transitions from reachable to recognizable, it informs the kernel by dropping the vref. Currently, recognizable vrefs are only the ones used solely as WeakMap or WeakSet key, which in the model above corresponds to vrefs with only themselves in their recognizable root set.

By extending the drop syscall with the content of the recognizable root set, the kernel becomes able to not only retire the vref itself when it is no longer reachable in other vats, but also inform the vat about any vref that it will no longer be able to recognize. For example if an exported virtual object solely hold onto an imported reference D, and the exported virtual object is retired, the kernel can inform the vat that its usage of the import D is also retired.

This ability of the kernel to identify transitively retired import is what allows it to perform one shot collections. In the previous example, if no other vats has D as a reachable import, then the kernel can inform the vat exporting D that it is now retired.

The recognizable root set of a vref is in effect the list of distributed edges pointing at that recognizable vref. By combining this list of edges, the kernel can reconstruct a partial distributed object graph sufficient for distributed garbage collection. It's partial because the leaf nodes are only the recognizable exported objects, and non-leaf nodes are only the objects parts of the recognizable root sets. This allows the kernel to trace from the root nodes that are reachable, mark all the vrefs that could be re-introduced, and thus detect any nodes that can be retired, even if these nodes are part of a distributed cycle of recognizable objects.