803376 - Stop doing TRANSPLANT GCs

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

First, some background on the problem...

When we run an incremental GC, the set of objects that end up being retained is roughly "anything reachable when the GC started" as well as "anything allocated during the GC". Some of these objects may be unreachable by the time the GC ends, but we tolerate that because they're guaranteed to be collected in the next GC.

However, brain transplants can cause us to fail to collect an object even when it was unreachable at the start of the GC, which is bad. Consider the following sequence of events:
1. Start incremental GC. Assume that compartment A has no reachable objects at this time. Compartments B and C are live.
2. We do a brain transplant of the outer window object from compartment B to compartment C. Assume that compartment A had a cross-compartment wrapper pointing to the outer window object in B.
3. To handle the wrapper in A, we create a new wrapper pointing to C's outer window and we swap it on top of the old outer window wrapper in A.
4. The newly-allocated wrapper in A (soon to be swapped) starts out marked because we're in the middle of an incremental GC.
5. When we continue the incremental GC, we mark everything reachable from the marked wrapper, which includes the inner window object of compartment A. From there, tons of other stuff is usually reachable.

The end result of this is that doing a brain transplant during an incremental GC causes lots of stuff to be uncollectable when it otherwise could have been collected. A long time ago, I fixed this by immediately finishing any ongoing incremental GC before doing a transplant.

However, the current fix is really killing GC performance. When we finish a GC early, all the remaining work that would have been spread over many slices now must be done at once. Empirically, I have pause time data collected across a small set of users with my gc-collector addon. When I look at the worst GC pauses, maybe 3/4 of them are caused by brain transplants. We desperately need to eliminate these transplant GCs, at least in the common case.

I've tried a number of different possible solutions to this bug. One idea was to somehow avoid marking the new wrapper object when it's created by detecting that we're in the middle of a transplant. That would be really complicated, though. Besides the marking that's done when the new wrapper is created, we also execute several read barriers during hashtable lookups while creating the objects. There's also a write barrier during JSObject::swap. All these would have to be changed to check a flag or something, which would be very ugly because these paths are deep in the JS engine.

I also was thinking that some sort of nuking could solve the problem--maybe there's a way that we could eliminate the reference to the outer window when we nuked the compartment. That way we wouldn't need to do any brain transplants after nuking the window. However, that ran into all sorts of problems with web compatibility.

The fix I've come up with is to directly overwrite the existing wrapper during a transplant, rather than creating a new one and then swapping. This turns out to be pretty easy to do. We need a facility for overwriting an existing wrapper with a new handler and a new target (which is pretty much what JSObject::swap does, but in an odd way). Then we can pass the existing wrapper to the XPConnect wrap hook, and it can re-use it. No GC barriers are invoked along the way, and no objects are allocated.

Comment 1

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: allow change slots that point to other compartments

Right now we don't have a way to change a slot that points into another compartment. This patch adds that ability.

Comment 2

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: patch to reuse existing wrappers when possible

This is the main patch. It allows an existing wrapper to be passed to JSCompartment::wrap for reuse. If it decides to reuse it, JSCompartment::wrap will pass it down to the xpconnect wrap hook, which can then overwrite its slots.

Comment 3

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: handle read barrier while remapping wrappers

There's a separate problem here, which is that the cross-compartment wrapper map has a read barrier on it. When we read a wrapper out of it during transplantation, we automatically mark that wrapper. This patch skips the read barrier.

However, if we happened to GC with JS_TransplantObject on the stack, then we could collect a wrapper that's being operated on. So basically we want to say:
- don't mark wrappers if a transplant happen while an incremental GC is in progress
- but *do* mark them if the GC ends while JS_TransplantObject is on the stack

This patch adds a special kind of auto-rooter for wrappers that causes them to be marked every GC slice, rather than just the first one.

Comment 4

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: remove the TRANSPLANT GCs

This patch actually kills off the GCs!

Comment 5

[Terrence Cole [:terrence]]

Comment on attachment 673041 [details] [diff] [review]
allow change slots that point to other compartments

Review of attachment 673041 [details] [diff] [review]:
-----------------------------------------------------------------

Yup.

Comment 6

[Luke Wagner [:luke]]

Comment on attachment 673048 [details] [diff] [review]
handle read barrier while remapping wrappers

Review of attachment 673048 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jswrapper.cpp
@@ +1167,5 @@
>      JS_ASSERT_IF(origTarget != newTarget, !pmap.has(ObjectValue(*newTarget)));
>  
>      // The old value should still be in the cross-compartment wrapper map, and
>      // the lookup should return wobj.
> +    JS_ASSERT(&pmap.lookup(origv)->value.unsafeGet()->toObject() == wobj);

It seems like, for us not to lose your transplant operation, we require all code on the transplant path to be very careful to not mark things.  Is there a strong assertion we can make?  Something like: if we are doing a transplant, and an incremental gc is in progress, see what objects are marked and, make sure that we don't mark any new ones by the end of the transplant, except in those cases where we can't use the new in-place transplant... or something :)  Without some assert that "we don't mark new stuff in here", I can see us regressing this when someone who isn't you waltzes into the code.

Another option might be to create a mochitest that exercises some pathological igc+transplant behavior, something that would definitely blow up if you don't have this optimization.  That sounds perhaps even better if we can make it not be flaky.

@@ +1216,5 @@
>          if (WrapperMap::Ptr wp = pmap.lookup(origv)) {
> +            // We found a wrapper. Remember and root it. We use unsafeGet() here
> +            // to avoid invoking a read barrier on the wrapper, which may be
> +            // dead. If there is an incremental GC while this function is on
> +            // stack, the AutoWrapperVector will ensure that it gets marked.

How about a little more explanation of why we want to avoid the read barrier.  It would be nice if that extended abstract in comment 0 appeared somewhere in the code as a comment and perhaps this comment could refer to it?

Comment 7

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Yeah, I've been thinking of writing a jsapi-test that would do some transplantation and then make sure that nothing got marked.

I like the idea of a mochitests, but I think it would be hard to make it blow up without it taking a long time to run normally.

I'm also considering adding an assertion that if a compartment has no incoming edges and nothing rooting its objects, then it will get collected in the next GC. However, that might be a little flaky, so I want to be careful with it. Maybe I'll test it on tryserver a few times.

Comment 8

[Andrew McCreight [:mccr8]]

Looking at Telemetry, with idle-daily and Application Version set to 19, about 13% of GCs are non-incremental.  Only about 0.32% of all GCs are TRANSPLANT.  Though these numbers don't really seem consistent to me, as I don't see 13% of GC reasons there for non-incremental types of GCs.

Comment 9

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Telemetry records a GC reason for every slice, which isn't very useful here. If your GC has 100 slices, and the first 99 are for REFRESH and the last one is for TRANSPLANT, then it would show up as 1% TRANSPLANT.

The 13% number is per-GC, I think. But 13% is pretty bad.

Comment 10

[Andrew McCreight [:mccr8]]

Ah, right, that makes sense! So the right thing to do is to figure out for each reason whether it indicates a non-incremental GC and then break it down by that. I may do that to take a break while reading these patches.

Oddly, if you don't specify 19, the number for non-incremental jumps to 25%.  I guess there's a lot of data in there from people on 15.  I hope there aren't that many people on Nightly 15 still...

Comment 11

[Bobby Holley (:bholley)]

Comment on attachment 673042 [details] [diff] [review]
patch to reuse existing wrappers when possible

Review of attachment 673042 [details] [diff] [review]:
-----------------------------------------------------------------

In general, this stuff needs more liberal commenting, especially some references to your heroic description in comment 0. I've pointed out a couple of places, but please just go through and generously describe what's going on.

r=bholley with comments addressed.

::: js/src/jsapi.cpp
@@ +1606,5 @@
>          JS_ASSERT(Wrapper::wrappedObject(newIdentityWrapper) == newIdentity);
> +        if (newIdentityWrapper != origobj) {
> +            if (!origobj->swap(cx, newIdentityWrapper))
> +                MOZ_CRASH();
> +        }

This is extremely tricky, and could use some serious commenting. Explain that it's valid to reuse the wrapper here because we were about to swap the guts anyway, so we actually want any existing consumers of the wrapper to see the new reference. Furthermore, explain that the wrap() implementation might decide to veto the reuse for various reasons, so we still need to do the identity check and potentially call swap().

::: js/src/jsapi.h
@@ +2019,5 @@
>   * Callback used to ask the embedding for the cross compartment wrapper handler
>   * that implements the desired prolicy for this kind of object in the
> + * destination compartment. |obj| is the object to be wrapped. If |existing| is
> + * non-NULL, it will point to an existing wrapper object that should be re-used
> + * if possible.

Add a comment here explaining what 'if possible' means. Specifically, what preconditions exist for |existing|, and what factors determine whether |existing| will be used.

::: js/src/jscompartment.cpp
@@ +191,4 @@
>  {
>      JS_ASSERT(cx->compartment == this);
> +    JS_ASSERT_IF(existing, existing->compartment() == cx->compartment);
> +    JS_ASSERT_IF(existing, vp->isObject());

Maybe assert that it's a wrapper, too?

::: js/src/jsproxy.cpp
@@ +3164,5 @@
> +    JS_ASSERT(obj->getTaggedProto().isLazy());
> +    JS_ASSERT(!handler->isOuterWindow());
> +
> +    obj->setSlot(JSSLOT_PROXY_HANDLER, PrivateValue(handler));
> +    obj->setCrossCompartmentSlot(JSSLOT_PROXY_PRIVATE, priv);

This seems wrong to me. PROXY_PRIVATE only has cross-compartment semantics if the proxy is a wrapper with the CROSS_COMPARTMENT flag.

::: js/src/jswrapper.cpp
@@ +1188,5 @@
> +        // update the entry in the compartment's wrapper map to point
> +        // to the old wrapper.
> +        if (!wobj->swap(cx, tobj))
> +            return false;
> +    }

Again, please explain what's going on here in more detail.

Comment 12

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: wrapper rooting, v2

The assertions I added to look for dead compartments that don't get collected identified some more places where read barriers were hurting us. So this patch adds some more uses of unsafeGet() and AutoWrapperVector.

I changed the comments to refer to a larger comment that I've added to jsgc.cpp. Since this comment is now copied in a few places, I wanted to keep it short.

Comment 13

[Luke Wagner [:luke]]

Comment on attachment 679017 [details] [diff] [review]
wrapper rooting, v2

Review of attachment 679017 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jswrapper.cpp
@@ +1161,5 @@
>              if (k.kind != CrossCompartmentKey::ObjectWrapper)
>                  continue;
>  
>              // Filter by target compartment.
> +            Value wrapper = *e.front().value.unsafeGet();

Perhaps copy your comment here too?

What if, instead of explaining the situation at each use site you add a new function (that just forwards to unsafeGet) whose name gives some indication and you put the comment on that function.  A good name escapes me atm, but seems like it would be justified in being long.  This would also make it more greppable.

Comment 14

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: add back TRANSPLANT GCs

After some thought, I've decided it's better to go the strictest possible route with respect to dead compartments not being collected, even in uncommon cases. This ensures that we never have pathological behavior, and it also makes it easier to design assertions to ensure we don't regress. This patch adds back some TRANSPLANT GCs to cover some corner cases where we do marking during a brain transplant. The next patch adds a bunch of assertions that ensure that all dead compartments are collected.

The basic premise of this patch is to identify paths during transplant where we might mark in dead compartments. If we take any of those paths, then we will force a fresh, non-incremental GC at the end of the transplant.

To do this, we need to be able to distinguish "dead" compartments from live ones, and we need to do so cheaply. In the assertion patch, dead-ness is computed by looking for incoming wrappers, which is expensive. This patch instead decides based on whether the compartment has been nuked yet, which seems to work well.

The main criteria for whether this patch works are:
1. Are the new TRANSPLANT GCs rare?
2. Does the patch avoid assertions (the ones that will appear in the upcoming patch).

The GCs do seem quite rare, based on tryserver results and a run of membench. And it has avoided asserting over several try runs.

I also added an extra condition in JSCompartment::wrap that determines whether we'll reuse a given wrapper. I realized that we don't want to reuse a wrapper if it formerly pointed to a dead compartment, since our write barrier scheme would cause that compartment to be marked when overwriting the wrapper. So in that case it's better to create a new wrapper.

Comment 15

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: assert all dead compartments are collected

This patch adds the assertions mentioned above. There's a big comment partway through that should explain everything.

Comment 16

[Luke Wagner [:luke]]

Comment on attachment 679433 [details] [diff] [review]
add back TRANSPLANT GCs

Review of attachment 679433 [details] [diff] [review]:
-----------------------------------------------------------------

Nice!  I like the upcoming assertion, and using nuking was a great idea.

Comment 17

[Luke Wagner [:luke]]

Comment on attachment 679435 [details] [diff] [review]
assert all dead compartments are collected

Review of attachment 679435 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jscompartment.h
@@ +286,5 @@
> +    /*
> +     * These flags help us to discover if a compartment that shouldn't be alive
> +     * manages to outlive a GC.
> +     */
> +    mozilla::DebugOnly<bool>     scheduledForDestruction;

You might want to reference the big beefy comment in jsgc.cpp.

::: js/src/jsgc.cpp
@@ +3404,5 @@
> +     * flag is false. The maybeAlive flag is set if:
> +     *   (1) the compartment has incoming cross-compartment edges, or
> +     *   (2) an object in the compartment was marked during root marking, either
> +     *       as a black root or a gray root.
> +     * If the maybeAlive is false, then we set the scheduledForDestruction flag.

"If the maybeAlive flag is false"

@@ +3422,5 @@
> +     * dead compartments are difficult to avoid. We detect such cases (via the
> +     * gcObjectsMarkedInNukedCompartment counter) and redo any ongoing GCs after
> +     * the JS_TransplantObject function has finished. This ensures that the dead
> +     * compartments will be cleaned up. See AutoMarkInNukedCompartment and
> +     * AutoTransplantGC for details.

One thing that might help the reader (who got here after hitting one of the scheduledForDestruction asserts) is to mention that AutoMarkInNukedCompartment temporarily sets scheduledForDestruction to false.

@@ +3427,5 @@
> +     */
> +
> +    /* Set the maybeAlive flag based on cross-compartment edges. */
> +    for (CompartmentsIter c(rt); !c.done(); c.next()) {
> +        for (WrapperMap::Enum e(c->crossCompartmentWrappers); !e.empty(); e.popFront()) {

I think you can just use Range here; Enum is Range + the ability to remove elements.

Comment 18

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e8a05026a175
https://hg.mozilla.org/integration/mozilla-inbound/rev/b2876ba6c0cd
https://hg.mozilla.org/integration/mozilla-inbound/rev/31262478deb7
https://hg.mozilla.org/integration/mozilla-inbound/rev/912a4721564f
https://hg.mozilla.org/integration/mozilla-inbound/rev/83fe0193339b
https://hg.mozilla.org/integration/mozilla-inbound/rev/34791dac914c

Comment 19

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Oops, I messed up. The landing of:
    https://hg.mozilla.org/integration/mozilla-inbound/rev/83fe0193339b
actually is part of bug 809295.

Comment 20

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I backed out the last part of this since the assertion was failing occasionally.

https://hg.mozilla.org/integration/mozilla-inbound/rev/7dbb863bed7c

Comment 21

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: patch to fix assertions from previous landing

I'm fixing these based on the stack traces from tinderbox logs. Unfortunately, I can't find a set of assertions that will make these trigger consistently.

The explanation for the swap case is that swapping may need to allocate new shapes if the objects have different numbers of fixed slots.

The nuke one is a little awful. There used to be an AutoMarkInDeadCompartment there to handle the case where a wrapper that points into a dead compartment is being nuked. However, there are some wrappers that have an Xray holder that is stored in the EXTRA+0 slot, and that is in the same compartment as the wrapper. So if we nuke a wrapper in a dead compartment with an Xray holder, we will overwrite the pointer to the Xray holder, triggering a write barrier on it. Yuck.

Comment 22

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ff655e6f934c

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/e8a05026a175
https://hg.mozilla.org/mozilla-central/rev/b2876ba6c0cd
https://hg.mozilla.org/mozilla-central/rev/31262478deb7
https://hg.mozilla.org/mozilla-central/rev/912a4721564f

Comment 24

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/ff655e6f934c