Bug 149432

Summary: GC should be concurrent
Product: WebKit Reporter: Filip Pizlo <fpizlo>
Component: JavaScriptCoreAssignee: Filip Pizlo <fpizlo>
Status: RESOLVED FIXED    
Severity: Normal CC: barraclough, benjamin, ggaren, mark.lam, mhahnenb, michal.kobylecki, msaboff, nrotem, oliver, ossy, saam, sam, webkit-bug-importer
Priority: P2 Keywords: InRadar
Version: Other   
Hardware: All   
OS: All   
Bug Depends on: 149433, 149586, 149635, 149654, 149852, 149936, 150217, 152045, 155479, 159658, 161581, 162006, 162309, 162316, 162318, 162319, 162790, 163337, 163343, 163562, 163734, 164282, 164421, 164422, 164454, 164783, 164788, 164791, 164805, 164823, 164940, 164990, 165638, 165643, 165712, 165735, 165758    
Bug Blocks: 165909    

Description Filip Pizlo 2015-09-21 16:33:13 PDT
Our GC is parallel and generational. That's great for throughput, but it's pretty bad for pause times. The JetStream/splay-latency test is one great example of how bad our pause times are.

We can make our GC incremental or even concurrent. The following things can be concurrent:

- Marking. We can use an incremental update barrier that re-greys anthracite objects as we store into them.
- Copying. We can use Baker's barrier at GetButterfly. We may be able to avoid using barriers if we load a butterfly only to load from it before any other side-effect.
- Sweeping of blocks that don't have destructors.
Comment 1 Radar WebKit Bug Importer 2015-09-21 16:36:34 PDT
<rdar://problem/22791740>
Comment 2 Mark Hahnenberg 2015-09-22 12:41:01 PDT
Exciting times!
Comment 3 Filip Pizlo 2015-09-29 13:44:41 PDT
One of the things that the concurrent marking will have to do is re-grey black objects.  We will say that an object becomes black as soon as it is popped off the mark stack and just before visitChildren() is called.

This means that we will have to have some way of indicating that an object has become black, and we will need some way of indicating when an object is no longer black.  This could be conservative, in the sense that if we sometimes think that a grey object is black, then that's OK - so long as we never think that a black object is grey.

I'm trying to figure out if m_gcData, which holds the NotMarked/Marked/MarkedAndRemembered enumeration, can be used to conservatively tell us if an object is black.  Re-greying a black object is quite a bit like "remembering" it.  The write barrier already says: if we do a store like o.f=v and o is marked but not remembered, then make it remembered and add it to the remembered set.  Adding it to the remembered set really means adding it to the mark stack.

The current algorithm for marking works like this:

Marking: if mark bit set, do nothing.  otherwise, set mark bit and set m_gcData to Marked and add to stack.
Remembering (i.e. GC barrier slow path): if Marked, change to MarkedAndRemembered and add to stack.
Visiting: remove from stack.

Then we change all MarkedAndRemembered objects to Marked at the end of GC.

This preserves the following invariants:

markBit = false, gcData = NotMarked, not on mark stack:                 white eden object
markBit = false, gcData = NotMarked, on mark stack:                     impossible (everything on the mark stack has a set mark bit or is remembered)
markBit = false, gcData = Marked, not on mark stack:                    white old space object during full collection
markBit = false, gcData = Marked, on mark stack:                        impossible (everything on the mark stack has a set mark bit or is remembered)
markBit = false, gcData = MarkedAndRemembered, not on mark stack:       impossible (to be remembered, we need to be in an eden collection and the object must have a sticky mark bit)
markBit = false, gcData = MarkedAndRemembered, on mark stack:           impossible (to be remembered, we need to be in an eden collection and the object must have a sticky mark bit)
markBit = true, gcData = NotMarked, not on mark stack:                  impossible (we set gcData to Marked when setting the mark bit)
markBit = true, gcData = NotMarked, on mark stack:                      impossible (we set gcData to Marked when setting the mark bit)
markBit = true, gcData = Marked, not on mark stack:                     black object in any space during any kind of collection
markBit = true, gcData = Marked, on mark stack:                         grey object in any space during any kind of collection
markBit = true, gcData = MarkedAndRemembered, not on mark stack:        black old space object during eden collection
markBit = true, gcData = MarkedAndRemembered, on mark stack:            grey old space object during eden collection

I'm current thinking that we could change this to say that a set mark bit and m_gcData==Marked means "black".  Then we could say that a set mark bit and m_gcData==MarkedAndRemembered means "grey".  Then we have the following operations:

Marking: if mark bit clear, do nothing.  otherwise, set mark bit and set m_gcData to MarkedAndRemembered and add to stack.
Remembering (i.e. GC barrier slow path): if Marked, change to MarkedAndRemembered and add to stack.
Visiting: remove from stack and set m_gcData to Marked.

We would not need any other pass to reset MarkedAndRemembered back to Marked, since visiting would do this.

I believe that this ensures that:

In between collections: marking isn't happening and we start with all previously surviving objects being Marked.  If we store to a Marked object, we make it MarkedAndRemembered and put it on the stack.

During a collection: if we store to an object that is MarkedAndRemembered, then we know that it must be on the mark stack, so we don't need to do anything. If we store to an object that is Marked, then we know that it is not on the mark stack, so we change it to MarkedAndRemembered and put it on the mark stack.

The new invariants become:

markBit = false, gcData = NotMarked, not on mark stack:                 white eden object
markBit = false, gcData = NotMarked, on mark stack:                     impossible
markBit = false, gcData = Marked, not on mark stack:                    white old space object during full collection
markBit = false, gcData = Marked, on mark stack:                        impossible (everything on the mark stack has a set mark bit)
markBit = false, gcData = MarkedAndRemembered, not on mark stack:       impossible (to be remembered, we must have set the mark bit previously)
markBit = false, gcData = MarkedAndRemembered, on mark stack:           impossible (to be remembered, we must have set the mark bit previously)
markBit = true, gcData = NotMarked, not on mark stack:                  impossible (we set gcData to MarkedAndRemembered when setting the mark bit)
markBit = true, gcData = NotMarked, on mark stack:                      impossible (we set gcData to MarkedAndRemembered when setting the mark bit)
markBit = true, gcData = Marked, not on mark stack:                     black object in any space during any kind of collection
markBit = true, gcData = Marked, on mark stack:                         impossible (we set gcData to MarkedAndRemembered when putting an object on the mark stack)
markBit = true, gcData = MarkedAndRemembered, not on mark stack:        impossible (we set gcData to Marked when removing an object from the mark stack)
markBit = true, gcData = MarkedAndRemembered, on mark stack:            grey object in any space during any kind of collection
Comment 4 Geoffrey Garen 2015-09-29 14:00:53 PDT
> Marking: if mark bit clear, do nothing.

I think you meant "Marking: if mark bit is set, do nothing."
Comment 5 Geoffrey Garen 2015-09-29 14:07:47 PDT
Sounds good to me.
Comment 6 Filip Pizlo 2015-09-29 15:56:13 PDT
(In reply to comment #4)
> > Marking: if mark bit clear, do nothing.
> 
> I think you meant "Marking: if mark bit is set, do nothing."

Yup!
Comment 7 Filip Pizlo 2015-09-29 20:35:32 PDT
I found a reason why resetting MarkedAndRemembered back to Marked just before visitChildren() won't quite work: during an eden collection, we need to remember if an object is old during visitChildren() because SlotVisitor::copyLater() will use that information.

Interestingly, just as copyLater() avoids copying the backing store for old objects, we want it to avoid copying the backing store for objects that get revisited because of a GC barrier.

This means we want to distinguish between MarkedAndRemembered due to a barrier and MarkedAndRemembered due to normal marking.
Comment 8 Filip Pizlo 2016-03-14 17:34:02 PDT
I think that the correct approach here is to remove copying from our GC.  I don't like how expensive the copy barrier is, and I don't know how to make it cheaper.  On the other hand, I doubt we will lose much if we allocate butterflies in the MS heap.
Comment 9 Filip Pizlo 2016-09-28 14:59:03 PDT
As of https://trac.webkit.org/changeset/206555, JSC is barrier-ready for concurrent GC.
Comment 10 Filip Pizlo 2016-10-27 13:12:03 PDT
I'm now working on one of the most exciting parts of making the GC concurrent.  In bug 163562, I have a patch that puts almost the whole GC in a separate thread.  This thread stops the world for all major GC activity, so the GC isn't actually concurrent.  But that bug addresses a bunch of big issues:

- It implements safepointing, including the notion of releasing heap access (which totally unblocks the GC when JSC is not in use), polling for the GC (when JSC is running and the GC needs it to stop), and runloop integration (if you don't release heap access but your runloop sleeps, the GC will proceed as if you released heap access).

- It implements a ticket-based GC scheduling system.  By default, all of our GC requests are now asynchronous, except for some corner-case debugging stuff.  This means that when you request the GC, it doesn't happen immediately - it just tells the GC thread to wake up.  There is also a synchronous GC request system that painstakingly emulates legacy behavior: you're guaranteed to get at least one GC of the kind you requested, start to finish, while you are blocked waiting for it.

- It makes WebCore weak reference callbacks happy with being called on a thread.

Once that patch is done, making the GC concurrent will largely be a matter of just moving the GC thread's stopTheWorld()/resumeTheWorld() calls around so that the world is not stopped during marking.  So much fun!
Comment 11 Filip Pizlo 2016-11-14 17:54:23 PST
It's now possible to run the concurrent GC by doing --useConcurrentGC=true.

It'll probably crash for anything non-trivial.
Comment 12 Filip Pizlo 2016-12-13 11:11:57 PST
The GC is now concurrent on X86-64 and ARM64.

I'm just polishing off the last weird bugs.
Comment 13 Filip Pizlo 2016-12-15 12:16:55 PST
The concurrent GC is now enabled on x86_64 and ARM64!

See https://trac.webkit.org/changeset/209827