395963 - ActionMonkey: Make incremental GC thread-safe under MMGC_THREADSAFE

Status: VERIFIED WONTFIX

(Tamarin Graveyard :: Garbage Collection (mmGC), defect)

Description

[Jason Orendorff [:jorendorff]]

See bug 395962 for more about MMGC_THREADSAFE.

See https://mail.mozilla.org/pipermail/tamarin-devel/2007-August/000017.html for more about how incremental GC will interact with the request model.

Comment 1

[Jason Orendorff [:jorendorff]]

This is not a Stage 1 goal.

I have some half-baked thoughts on this that I might as well post here.  (Warning:  Not a lot of this will make sense unless you already know about the request model and how we're going to use it to implement MMGC_THREADSAFE mode in the *non*-incremental case.)

Incremental GC introduces two new activities to the range of stuff we need to coordinate across threads:  incremental marking and write barrier hits.  Incremental marking will run under the same stop-the-world locking scheme as non-incremental GC does in MMGC_THREADSAFE mode.  Write barriers are trickier. 

We have to make sure that write barriers (1) don't race with each other and (2) don't race with allocation.

We have to worry about allocation because multiple (8 or 16) allocations share the same word of per-object bits.  If one thread allocates an object, and simultaneously another thread enqueues a neighboring object (because of a write barrier hit), both threads will be racing to update the same word of bits.

We don't have to worry about write barrier hits racing with GCAlloc::Sweep(), because Sweep can only happen when !gc->marking and write barriers can only happen when gc->marking.

I'm open to suggestions.  The easiest thing would be to make write barrier hits obtain the gc lock.  Slow.  Another possibility is to lean hard on atomic operations, but I'm told this is bad news too.

Comment 2

[Jason Orendorff [:jorendorff]]

A third possibility is to use a whole byte of bits per object, and change the code from accessing whole words to accessing individual bytes.  I'll try and show that this is safe when any threads are in requests:

* For not-in-use objects, only allocation will touch the bits, and only while the calling thread is holding the gc-wide lock.

* For in-use (allocated) objects, the only operation by threads in requests that modifies that object's bits is to set the refresh bit, so threads can race without problems.

A fourth possibility is to put the Queued bits (the bits write barriers could touch) someplace away from the bits allocation could touch.  It's OK for writes to the kQueued bits to clobber one another occasionally.

A fifth possibility, proposed by treilly, is just to remove the Queued bit.  Then every write barrier hit would re-queue the white object to be marked. bsmedberg promises to write a stress test to bury me if I do that.  Maybe I can queue up write barrier hits in a (per-thread) hash-set instead of a flat array; that will prevent the queue from growing.

Comment 3

[Jason Orendorff [:jorendorff]]

Oops, "the refresh bit" in comment 2 should say "the queued bit".  Don't know where that came from.

I like that third possibility the best, even if it does waste 4 bits per object.  The painful parts are: depending on the CPU to guarantee that byte writes are immune to stale reads and won't clobber adjacent bytes.  And then depending on the compiler to emit byte reads and writes, not word reads and writes.  (There's nothing in the C or C++ standard that holds the compiler to this.  Graydon insists depending on that kind of thing is a non-starter, and that we should use inline assembly for that part.  Fine by me.)

The other thing Graydon suggested was:  first make it work, then make it work fast.  Sounds good to me.  So I'll do this the horrible way in this bug (heavyweight locking!) and I'll tune it afterwards.  The tuning still falls in the scope of AM Stage 2; it'll be a new bug that blocks bug 412518.

;-) With any luck, by the time I get around to that, jasone will have written the new grand unified allocator for us already.  If so, I'll have less work to do, and jasone will look even *more* brilliant due to the stunning performance increase.  Win-win!

Comment 4

[Gábor Stefanik]

Wontfix?! Did Mozilla's goals/plans change? Or was it/will it be fixed in another bug? In that case, it should be either Worksforme or a duplicate of the bug where it was fixed.