Summary: | GC should be concurrent | ||
---|---|---|---|
Product: | WebKit | Reporter: | Filip Pizlo <fpizlo> |
Component: | JavaScriptCore | Assignee: | 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
Exciting times! 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 > Marking: if mark bit clear, do nothing.
I think you meant "Marking: if mark bit is set, do nothing."
Sounds good to me. (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! 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. 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. As of https://trac.webkit.org/changeset/206555, JSC is barrier-ready for concurrent GC. 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! It's now possible to run the concurrent GC by doing --useConcurrentGC=true. It'll probably crash for anything non-trivial. The GC is now concurrent on X86-64 and ARM64. I'm just polishing off the last weird bugs. The concurrent GC is now enabled on x86_64 and ARM64! See https://trac.webkit.org/changeset/209827 |