Sandro
On 19/10/2013 10:09 AM, Jonathan S. Shapiro wrote:
I had previously assumed that objects could not be shared across threads until they are tenured. That is pretty clearly wrong. If mutators run concurrently, it's pretty easy to construct a reference from one nursery to another. I want to walk through this case and make sure that I understand it.*Deferred RC vs. Local Nursery Collection* * *I was hopeful that each thread might be able to collect its local heap without halting other threads (perhaps with algorithm changes). Here is the scenario that troubles me. There is probably a simpler way to construct it:1. Thread A creates an object O. The object is initially marked N (new). 2. A reference to O is stored into tenured object T. During this store: 1. T is logged 2. T is marked M (reference stores need not be counted) 3. ref(O) is stored somewhere in T 3. Note that the RC field of O is still zero. 4. Thread B loads ref(O) into a root. Root references are deferred, so O.RC is still zero. This reference can get copied around B's nursery all day without producing any count events. 5. /Somebody/ (doesn't matter who) overwrites the ref(O) in T, such that T no longer references O. 6. O ceases to be reachable from A's root set (A drops the reference) 7. A now collects its nurseryN.B. that step [7] assumes concurrency between mutators and collectors. I was hopeful that /limited/ concurrency - specifically for nursery clearing - might be possible. Unfortunately:* There is no evidence from A's point of view that O is live * The intermediate object T no longer holds a reference to O * B olds a reference to O, but this is invisible to A unless we want to admit a cross-thread coordination here.I don't really think that logging the in-bound pointer into the nursery helps. That would be enough to tell us to integrate O, but by the time we integrate O the reference into nursery(A) may be gone.The heart of the problem is the independent collections of the nurseries. *Islands in the Nursery (Lumps in the Baby Mattress?)* * *It gets worse. So now we have an object O in nursery A, and we have ref(O) in nursery B. Thread A collects, migrating O to tenured space. And now we have two problems:* How do we notice that we need to leave a forwarding object if B's references are deferred? * If we /do/ leave a forwarding object, then we end up with islands stuck in A's nursery * We /really/ don't want to page fault in A's nursery, so using page protections as a barrier method is unattractive... *Does Locking Help?* * *One thing we could possibly do here is rely on locking. If we have multiple threads accessing an object for writing /correctly,/ then each thread in turn needs to take a lock on the object. We could make it the case that /releasing/ a lock on a dirty object requires that the object first be integrated. That will get is an RC bump on O initially, but it's still possible for ref(O) to be overwritten in T and then integrated, causing ref(O) to be dropped.So no, I don't think we can rely on locking for this. And in a way that's a relief, since relying on that would make code that used atomic updates problematic.Sigh. For the moment I'm temporarily stumped. I suspect that the shape of a solution may emerge if I re-read the C4, Chicken, and Stopless papers. There's nothing in deferred RC that makes this inherently more complicated than those collectors, excepting only that you need to run the deferred counting process at some point._______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
smime.p7s
Description: S/MIME Cryptographic Signature
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
