domenic at domenicdenicola.com (2013-11-17T17:54:18.545Z)
there's a distributed race condition that's fixed by the use of importCount. Fixing it using post-mortem finalization creates a local race condition which is fixed by this test, not if the proxy is *still* alive, but if a new proxy has been installed as its reincarnation. For background, see [Two-Vat DAGC](http://www.erights.org/elib/distrib/captp/dagc.html) and [CapTP Ops: DeliverOp](http://www.erights.org/elib/distrib/captp/DeliverOp.html). Kenton Varda is implementing [a high performance adaptation of CapTP](https://github.com/kentonv/capnproto/blob/master/c++/src/capnp/rpc.capnp) as part of [Cap'n Proto](http://kentonv.github.io/capnproto/). (Kenton did Google's protobufs 2 and open sourced them before leaving Google to do this successor.) This CapTP-in-Cap'n Proto has essentially the same distributed gc logic for coping with the distributed race conditions, but in its C++ bindings, relies on local manual collection rather than observation of local GC, so it doesn't have the same local race condition. The distributed race condition is that VatA notices (by finalization of the proxy) that it has dropped all local references to its bobProxy for VatB's Bob object. So VatA sends a GCExportOp(i, importCount) (in original CapTP terminology) to VatB. However, in the meantime, a message from VatB to VatA contains a reference to VatB's Bob. When it serializes the references to Bob, it sees that Bob is already registered in its VatB-to-VatA exports table at index i, so it serializes the reference as an ImportDesc(i). (When it sends Bob the first time it sends a NewFarDesc instead.) The GCExportOp(i, importCount) from VatA-to-VatB might cross on the wire with the ImportDesc(i) from VatB to VatA, which is the distributed race condition issue. The solution is that every time VatB sends an ImportDesc(i) to VatA, it increments exportCount[i] in its VatB to VatA export table. Everytime VatA unserializes an ImportDesc(i), it calls the Import(i) function at http://wiki.ecmascript.org/doku.php?id=strawman:weak_references#distributed_acyclic_garbage_collection, which increments importCount[i] and returns a valid proxy registered in is VatA-from-VatB imports table at i. If the existing proxy still exists, it uses that one. Otherwise it creates a new one. When VatB receiver the GCExportOp(i, importCount) from VatA, it decrements its exportCount by that amount. If its exportCount reaches 0, then it knows it can null out entry i in its exports table, enabling local collection of Bob if there are no other local uses. Otherwise, it knows that it needs to keep Bob registered as exports[i]. The local race condition is that VatA's local GC might have collected bobProxy, therefore nulling out the proxyRef, and scheduled a notification of the handler that would send the GCExportOp. However, already queued on VatA ahead of the notification of the handler is the processing of the ImportDesc from VatB, so that gets processed first, creating a successor proxy at imports[i]. Finally, when the handler does get notified, it needs to check if such a successor has already been installed and is still alive. I know this is complex, but after many years of looking at it, I don't know how to make it any simpler. Consider this a challenge ;). (OTOH, after many years of use, I've come to have high confidence in it.) The Dec Src Network Object system has similar solutions to many of these distributed race condition problems. But they had a very different model of local concurrency (shared state concurrency with Tony Hoare monitors IIRC), so they had different local race condition problems.
Hi David, there's a distributed race condition that's fixed by the use of importCount. Fixing it using post-mortem finalization creates a local race condition which is fixed by this test, not if the proxy is *still* alive, but if a new proxy has been installed as its reincarnation. For background, see <http://www.erights.org/elib/distrib/captp/dagc.html> and <http://www.erights.org/elib/distrib/captp/DeliverOp.html>. Kenton Varda is implementing a high performance adaptation of CapTP < https://github.com/kentonv/capnproto/blob/master/c++/src/capnp/rpc.capnp> as part of Cap'n Proto <http://kentonv.github.io/capnproto/>. (Kenton did Google's protobufs 2 and open sourced them before leaving Google to do this successor.) This CapTP-in-Cap'n Proto has essentially the same distributed gc logic for coping with the distributed race conditions, but in its C++ bindings, relies on local manual collection rather than observation of local GC, so it doesn't have the same local race condition. The distributed race condition is that VatA notices (by finalization of the proxy) that it has dropped all local references to its bobProxy for VatB's Bob object. So VatA sends a GCExportOp(i, importCount) (in original CapTP terminology) to VatB. However, in the meantime, a message from VatB to VatA contains a reference to VatB's Bob. When it serializes the references to Bob, it sees that Bob is already registered in its VatB-to-VatA exports table at index i, so it serializes the reference as an ImportDesc(i). (When it sends Bob the first time it sends a NewFarDesc instead.) The GCExportOp(i, importCount) from VatA-to-VatB might cross on the wire with the ImportDesc(i) from VatB to VatA, which is the distributed race condition issue. The solution is that every time VatB sends an ImportDesc(i) to VatA, it increments exportCount[i] in its VatB to VatA export table. Everytime VatA unserializes an ImportDesc(i), it calls the Import(i) function at < http://wiki.ecmascript.org/doku.php?id=strawman:weak_references#distributed_acyclic_garbage_collection>, which increments importCount[i] and returns a valid proxy registered in is VatA-from-VatB imports table at i. If the existing proxy still exists, it uses that one. Otherwise it creates a new one. When VatB receiver the GCExportOp(i, importCount) from VatA, it decrements its exportCount by that amount. If its exportCount reaches 0, then it knows it can null out entry i in its exports table, enabling local collection of Bob if there are no other local uses. Otherwise, it knows that it needs to keep Bob registered as exports[i]. The local race condition is that VatA's local GC might have collected bobProxy, therefore nulling out the proxyRef, and scheduled a notification of the handler that would send the GCExportOp. However, already queued on VatA ahead of the notification of the handler is the processing of the ImportDesc from VatB, so that gets processed first, creating a successor proxy at imports[i]. Finally, when the handler does get notified, it needs to check if such a successor has already been installed and is still alive. I know this is complex, but after many years of looking at it, I don't know how to make it any simpler. Consider this a challenge ;). (OTOH, after many years of use, I've come to have high confidence in it.) The Dec Src Network Object system has similar solutions to many of these distributed race condition problems. But they had a very different model of local concurrency (shared state concurrency with Tony Hoare monitors IIRC), so they had different local race condition problems. On Fri, Nov 8, 2013 at 4:49 PM, David Bruant <bruant.d at gmail.com> wrote: > Le 08/11/2013 20:35, Mark S. Miller a écrit : > > Please try -- such experiments are interesting. >> > I am :-) > > > But even if this experiment is successful, I hope and expect that we'll >> have weakrefs and post-mortem finalization in ES7. They are needed for many >> other things, such as distributed acyclic garbage collection (as in >> adapting the CapTP ideas to distributed JS). >> > yes... > Speaking of which, could you explain the use of proxyRef.get from the > related example? [1] > At least in the executor function, I don't understand how the object could > be still alive and why the call is needed. > > David > > [1] http://wiki.ecmascript.org/doku.php?id=strawman:weak_ > references#distributed_acyclic_garbage_collection > -- Cheers, --MarkM -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20131108/e2cecf0e/attachment-0001.html>