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 nursery
N.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
