/ elib / distrib / captp

CapTP: Distributed Acyclic Garbage Collection

Of course, we must not only build inter-vat references when they're needed, we must tear them down when they're no longer needed. If we did a perfect job of this, we would call it Distributed Garbage Collection (DGC). However, for various reasons, we have currently decided only to implement Distributed Acyclic Garbage Collection (DAGC). The distinction is that the former will collect an unreferenced inter-vat loop of objects while the latter will not. The advantage of taking this low road is that garbage collection can proceed by separate uncoordinated local interactions, with no global analysis. Of course, the disadvantage is that we leek live distributed cycles. At such a time as this proves to be a significant problem, we will revisit the issue of implementing a full Distributed Garbage Collector.

Two-Vat DAGC

It turns out that the same pair of dichotomies -- outgoing vs incoming and allocate vs obey -- also modularize the issue of tearing down remote references. Only the side that has the arrowtail can find out (by finalization from his local intra-vat garbage collector) that there is no longer any local interest in using the tail of that reference. This does not necessarily mean it's safe to drop the reference! Only the side that allocated the reference can determine when it's safe to deallocate it, but it does so based on the signal from the side holding the outgoing end of the reference.

For the Questions table these are one and the same. The side that allocated the reference is the side that hold the outgoing end, so the entry can be deallocated as soon as local finalization informs us of lack of local interest. A signal is then sent to the Answers table which follows suit. For more details, see GCAnswerOp.

For the other tables, the information that might result in a deallocation comes from a finalization signal by the local garbage collector on the Imports table side. The Imports table can only provide information about this occurence, but, because of a race-condition hazard, only the Exprorts table can make the decision to deallocate. Strangely, there's no reason to inform the Imports table when this decision does get made, and this protocol does not. Rather, having deallocated, the Exports table is now free to re-allocate, and the Imports table follows suit when this happens. For more details, see GCExportOp.

Three-Vat DAGC

For issues in three-vat garbage collection, see Vine.