[bitc-dev] BitC 0.20: Unboxed unions, references, and GC

Jonathan S. Shapiro shap at eros-os.org
Sat Mar 13 00:25:15 PST 2010

Bjarne Steensgaard recently asked me a question about BitC unboxed unions
that revealed a design problem. I'ld appreciate thoughts about whether the
fixes I see are acceptable, or if not, whether we should drop the language
feature that raises the problem.

The problem arises from the interaction of two facts, and is amplified by a

   1. GC may be concurrent (if it is cooperative, then there is no issue)
   2. GC operates at the semantic level of memory words, not objects
   3. GC may be relocating

The first fact means that we must consider concurrency hazards between the
GC and the program. If we update the tag first then the implied pointer
types are incorrec. If we update the pointers first then the implied pointer
types are once again incorrect. The second fact means that we can't rely on
application-level locking to solve the problem; we need a resolution that is
fairly low-level in the runtime layer. The third fact means that one or two
"obvious" solutions do not work.

If the GC is concurrent, then so far as I can see there are only two
solutions for this problem:

   - Reserve an update lock bit in the tag field, or some comparable form of
   concurrency control mechanism (this is one variant of the solution Bjarne
   - Use a "zero; retag; rewrite" protocol. That is: zero the old references
   while the old tag is still in force, update the tag, and then copy the new

There is some incentive for concurent collectors to be implemented in
wait-free fashion, which tends to favor the second approach.

Does anybody see another design option to consider here?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20100313/57546eb5/attachment.html 

More information about the bitc-dev mailing list