776583 - GC: Make the post barrier verifier green in the interpreter in the shell

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Terrence Cole [:terrence]]

Now that we have a reliable and relatively fast post barrier verifier, we can relatively easily make the interpreter generational GC safe.

Comment 1

[Terrence Cole [:terrence]]

Attachment: v2: prior versions were attached to 764962

Comment 2

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

Comment on attachment 644994 [details] [diff] [review]
v2: prior versions were attached to 764962

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

This looks pretty good. Sorry it took me so long to get to. I'd like to see another version to see if the hash table post barriers can be unified into one function.

::: js/src/gc/Barrier-inl.h
@@ +166,5 @@
>  inline void
>  HeapValue::writeBarrierPost(JSCompartment *comp, const Value &value, Value *addr)
>  {
>  #ifdef JSGC_GENERATIONAL
> +    if (value.isMarkable()) {

No braces.

@@ +248,5 @@
>  inline void
>  RelocatableValue::post(JSCompartment *comp)
>  {
>  #ifdef JSGC_GENERATIONAL
> +    if (value.isMarkable()) {

No braces.

@@ +371,5 @@
> +
> +    bool match(void *location) {
> +        if (owner->isDenseArray()) {
> +            uint32_t len = owner->getDenseArrayInitializedLength();
> +            for (uint32_t i = JS_MIN(start, len - 1); i < JS_MIN(end, len); ++i) {

Please use |len| in both cases. Also, js::Min is better than JS_MIN.

@@ +377,5 @@
> +                    return true;
> +            }
> +            return false;
> +        }
> +        for (uint32_t i = start; i < end; ++i) {

This needs to be bounds-checked against slotSpan(). Otherwise we could have false matches.

@@ +378,5 @@
> +            }
> +            return false;
> +        }
> +        for (uint32_t i = start; i < end; ++i) {
> +            if (owner->getSlotAddressUnchecked(i) == location)

Why unchecked?

@@ +389,5 @@
> +        /* Apply forwarding, if we have already visited owner. */
> +        IsObjectMarked(&owner);
> +        if (owner->isDenseArray()) {
> +            uint32_t len = owner->getDenseArrayInitializedLength();
> +            for (uint32_t i = JS_MIN(start, len - 1); i < JS_MIN(end, len); ++i)

Same comment here.

::: js/src/jsproxy.cpp
@@ +1512,1 @@
>              JS_ASSERT(p->value.get() == ObjectValue(*obj));

Your new one seems better to me.

::: js/src/jsscope.h
@@ +458,5 @@
>      friend struct js::StackBaseShape;
>  
>    protected:
>      HeapPtrBaseShape    base_;
> +    EncapsulatedId      propid_;

I don't understand this change. Why does propid_ not need a post barrier?

::: js/src/vm/Debugger.cpp
@@ +656,5 @@
>      return true;
>  }
>  
> +void
> +Debugger::debuggeeWriteBarrierPost(JSCompartment *comp, JSObject *key)

Would it be possible to create some sort of templated function that took a compartment, a hashtable, and a key, and it added it to the store buffer? Then you could eliminate a number of these methods.

@@ +659,5 @@
> +void
> +Debugger::debuggeeWriteBarrierPost(JSCompartment *comp, JSObject *key)
> +{
> +#ifdef JSGC_GENERATIONAL
> +    typedef gc::HashKeyRef<ObjectWeakMap, EncapsulatedPtrObject> WeakObjectMapRef;

I'm not sure what's Weak here.

::: js/src/vm/ObjectImpl-inl.h
@@ +224,5 @@
> +js::ObjectImpl::initCrossCompartmentSlot(uint32_t slot, const js::Value &value)
> +{
> +    MOZ_ASSERT(getSlot(slot).isUndefined() || getSlot(slot).isMagic(JS_ARRAY_HOLE));
> +    MOZ_ASSERT(slotInRange(slot));
> +    if (value.isObject() && compartment() != value.toObject().compartment()) {

It seems like we have to worry about strings, too. You should use isMarkable and toGCThing. Same for the assertions above here.

@@ +225,5 @@
> +{
> +    MOZ_ASSERT(getSlot(slot).isUndefined() || getSlot(slot).isMagic(JS_ARRAY_HOLE));
> +    MOZ_ASSERT(slotInRange(slot));
> +    if (value.isObject() && compartment() != value.toObject().compartment()) {
> +        getSlotAddressUnchecked(slot)->init(value.toObject().compartment(), this->asObjectPtr(),

I think you should be able to use getSlotRef here instead of getSlotAddressUnchecked.

@@ +228,5 @@
> +    if (value.isObject() && compartment() != value.toObject().compartment()) {
> +        getSlotAddressUnchecked(slot)->init(value.toObject().compartment(), this->asObjectPtr(),
> +                                            slot, value);
> +    } else {
> +        initSlotUnchecked(slot, value);

I think you should be able to use initSlot here.

@@ +354,3 @@
>  {
> +#ifdef JSGC_GENERATIONAL
> +    if (uintptr_t(*loc) < 32)

This will never happen.

::: js/src/vm/ScopeObject.cpp
@@ +1528,5 @@
> +void
> +DebugScopes::proxiedScopesWriteBarrierPost(JSCompartment *comp, ScopeObject *key)
> +{
> +#ifdef JSGC_GENERATIONAL
> +    typedef gc::HashKeyRef<ObjectWeakMap, ScopeObject *> WeakObjectMapRef;

The Weak name here also doesn't make sense.

@@ +1529,5 @@
> +DebugScopes::proxiedScopesWriteBarrierPost(JSCompartment *comp, ScopeObject *key)
> +{
> +#ifdef JSGC_GENERATIONAL
> +    typedef gc::HashKeyRef<ObjectWeakMap, ScopeObject *> WeakObjectMapRef;
> +    if ((key && comp->gcNursery.isInside(key)))

Too many parens here.

::: js/src/vm/String-inl.h
@@ +37,5 @@
>  inline void
>  JSString::writeBarrierPost(JSString *str, void *addr)
>  {
> +#ifdef JSGC_GENERATIONAL
> +    if (uintptr_t(str) < 32)

This can just be a null check.

Comment 3

[Terrence Cole [:terrence]]

(In reply to Bill McCloskey (:billm) from comment #2)
> @@ +377,5 @@
> > +                    return true;
> > +            }
> > +            return false;
> > +        }
> > +        for (uint32_t i = start; i < end; ++i) {
> 
> This needs to be bounds-checked against slotSpan(). Otherwise we could have
> false matches.
> 
> @@ +378,5 @@
> > +            }
> > +            return false;
> > +        }
> > +        for (uint32_t i = start; i < end; ++i) {
> > +            if (owner->getSlotAddressUnchecked(i) == location)
> 
> Why unchecked?

I think because it skips the bounds che... *facepalm*.
 
> ::: js/src/jsscope.h
> @@ +458,5 @@
> >      friend struct js::StackBaseShape;
> >  
> >    protected:
> >      HeapPtrBaseShape    base_;
> > +    EncapsulatedId      propid_;
> 
> I don't understand this change. Why does propid_ not need a post barrier?

I should have documented this, because now that it's been a few months I'm not entirely sure.  I _believe_ that it is because propid_ is always an atom.

> ::: js/src/vm/Debugger.cpp
> @@ +656,5 @@
> >      return true;
> >  }
> >  
> > +void
> > +Debugger::debuggeeWriteBarrierPost(JSCompartment *comp, JSObject *key)
> 
> Would it be possible to create some sort of templated function that took a
> compartment, a hashtable, and a key, and it added it to the store buffer?
> Then you could eliminate a number of these methods.

Excellent idea!  I did not think that 3/4 of our users would end up being so similar.  I implemented watchpoint first: the odd one of the bunch.  In any case, the template works wonderfully.  I've added it to gc/Barrier.h, since it's a barrier, and gc/StoreBuffer.h is entirely surrounded by #ifdef JS_GCGENERATIONAL.

> @@ +659,5 @@
> > +void
> > +Debugger::debuggeeWriteBarrierPost(JSCompartment *comp, JSObject *key)
> > +{
> > +#ifdef JSGC_GENERATIONAL
> > +    typedef gc::HashKeyRef<ObjectWeakMap, EncapsulatedPtrObject> WeakObjectMapRef;
> 
> I'm not sure what's Weak here.

My copy editing skills and the type of the map we are referencing into.  It would be clearer as ObjectWeakMapRef -- I'm not sure why I reversed the word ordering.
 
> ::: js/src/vm/ScopeObject.cpp
> @@ +1528,5 @@
> > +void
> > +DebugScopes::proxiedScopesWriteBarrierPost(JSCompartment *comp, ScopeObject *key)
> > +{
> > +#ifdef JSGC_GENERATIONAL
> > +    typedef gc::HashKeyRef<ObjectWeakMap, ScopeObject *> WeakObjectMapRef;
> 
> The Weak name here also doesn't make sense.

Same underlying map type.  Both gone now in any case.

Re-running jit-tests with after rebasing and applying review feedback and it looks like there is only one new failure: looking into it now.

Comment 4

[Terrence Cole [:terrence]]

Right, so I tracked down the one failure: it was a simple C++ thinko.  In StoreBuffer::coalesceForVerification, we call MonoTypeBuffer::accumulateEdges, which calls the method |this->compact()|: I forgot to declare this as virtual, so we did not call the specialized RelocatableMonoTypeBuffer::compact.  This was causing us not to remove tagged pointers.

The presence of the tagged pointers was not the problem: we only call inNursery() on the tagged pointer.  The problem is that when we dereference the pointer we hit memory that was shifted or deleted.  We crash (or not) based on whether what is there happens to look like a GCThing, which (sometimes) asserts when we try to convert it to a pointer if the bottom bits are set.

I have identified three problems:
1) Missing virtual keyword.
2) inNursery should assert that the thing we are checking is not tagged.
3) (unrelated) When we coalesce we should check for overflow first.  On overflow, we set the overflow bit on the compartment and set pos=base.  This works fine for non-relocatable buffers, but for relocatable buffers it could lead to more removes than puts, which will trigger an assertion during compactRemoved.

Comment 5

[Terrence Cole [:terrence]]

Sadly, looks like (2) is inviable because JSRope::flatten rewrites the rope object inline into a different type of string.  The pointer that was |right| in the rope becomes |capacity| in the flat string, making the target side of the edge not a pointer.  Our assertion then triggers because the "pointer" looks tagged for odd-sized string.

This is annoying, but I don't think it is particularly dangerous, as long as we check that all pointer targets point to a real, correctly aligned thing before we move the target.  This could be problematic if we move to a bump-allocated nursery.

Bill, does this seem right, or should we maybe make the store buffer for the manual barriers on ropes relocatable so we can delete these entries when we transform the rope inline?

Comment 6

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

(In reply to Terrence Cole [:terrence] from comment #5)
> Bill, does this seem right, or should we maybe make the store buffer for the
> manual barriers on ropes relocatable so we can delete these entries when we
> transform the rope inline?

I prefer this solution--relocating the pointers when we flatten.

Comment 7

[Terrence Cole [:terrence]]

Attachment: v3: Applied feedback round 1.

The templatized barrier is much cleaner.

Comment 8

[Terrence Cole [:terrence]]

Comment on attachment 651503 [details] [diff] [review]
v3: Applied feedback round 1.

Sorry, midaired with your comment.  I will fix it and try to add back the assertion.

Comment 9

[Terrence Cole [:terrence]]

Attachment: v4: Ensuring no non-pointer targets.

Try run is up at:
https://tbpl.mozilla.org/?tree=Try&rev=4239dface5b0

This turned out to be a bit more involved than I thought.  In order to safely add this assert I needed to fix ropes, shape getter/setter, and setPrivate.  

I've added a strong assertion to setPrivate and the new setPrivateGCThing that the passed pointer is or is not in the GC heap.  The JS_SetPrivate usages all appear to be for non-gcthing pointers.  I wasn't 100% sure about was the one in js/xpconnect/src/dombindings.cpp, but the try run should tell us if I guessed correctly.

Comment 10

[Terrence Cole [:terrence]]

Attachment: v5: Made the assertions a zeal mode.

Turns out Env is a typedef for JSObject.  New try run (with setPrivate checks forced on) is up at:
https://tbpl.mozilla.org/?tree=Try&rev=1cd00a9ae271

Comment 11

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

Comment on attachment 652144 [details] [diff] [review]
v5: Made the assertions a zeal mode.

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

Sorry, one more round. I want to see the rope changes and the rekey stuff.

::: js/src/builtin/TestingFunctions.cpp
@@ +789,5 @@
>  "    9: Incremental GC in two slices: 1) mark all 2) new marking and finish\n"
>  "   10: Incremental GC in multiple slices\n"
>  "   11: Verify post write barriers between instructions\n"
>  "   12: Verify post write barriers between paints\n"
> +"   13: Verify js::ObjectImpl::setPrivate usage\n"

I doubt we'll use this mode very often. It would be easier to add the assertion manually when you want to test it.

::: js/src/gc/Barrier-inl.h
@@ +390,5 @@
> +        if (owner->isDenseArray()) {
> +            uint32_t len = owner->getDenseArrayInitializedLength();
> +            for (uint32_t i = Min(start, len); i < Min(end, len); ++i)
> +                gc::MarkValueRoot(trc, &const_cast<Value &>(owner->getDenseArrayElement(i)),
> +                                  "array slot");

Could you use MarkArraySlots for this?

@@ +393,5 @@
> +                gc::MarkValueRoot(trc, &const_cast<Value &>(owner->getDenseArrayElement(i)),
> +                                  "array slot");
> +            return;
> +        }
> +        MarkObjectSlots(trc, owner, start, end - start);

I think you need to handle the case where start or end are out of bounds.

::: js/src/gc/Barrier.h
@@ +242,5 @@
>          JS_ASSERT(!IsPoisonedPtr<T>(v));
> +        if (v) {
> +            this->value = v;
> +            post();
> +        } else {

You can convert this to
  } else if (this->value) {
and drop the condition below. It's a bit cleaner.

@@ +258,5 @@
>          JS_ASSERT(!IsPoisonedPtr<T>(v.value));
> +        if (v.value) {
> +            this->value = v.value;
> +            post();
> +        } else {

Same here.

@@ +468,5 @@
>  inline void
> +SlotRangeWriteBarrierPost(JSCompartment *comp, JSObject *obj, uint32_t start, uint32_t count);
> +
> +/*
> + * This is a post barrier for HashTables who's key can be moved during a GC.

who's -> whose

::: js/src/gc/Marking.cpp
@@ +310,4 @@
>          MarkInternal(trc, &obj);
>          *id = OBJECT_TO_JSID(obj);
> +    } else {
> +        JS_SET_TRACING_LOCATION(trc, NULL);

Can you explain (and comment) why this is needed? I think you told me, but I forgot.

::: js/src/jsapi.cpp
@@ +4641,1 @@
>          ida = JS_Enumerate(cx, obj);

The rooting looks kinda broken here, but that's not something to be fixed in this patch. In particular we have an AssertRootingUnnecessary on the stack while calling JS_Enumerate, which can GC.

::: js/src/jsgc.h
@@ +639,3 @@
>      void waitBackgroundSweepEnd();
>  
> +    /* Must be called without the GC lock taken. */

Thanks for fixing these :-).

::: js/src/jstypedarray.cpp
@@ +1292,5 @@
>           * private data rather than a slot, to avoid alignment restrictions
>           * on private Values.
>           */
> +        obj->initPrivate(buffer->dataPointer() + byteOffset);
> +        TypedArrayPrivateWriteBarrierPost(obj, buffer, byteOffset);

Could you have a single function that sets the private and invokes the barrier?

::: js/src/jswatchpoint.cpp
@@ +53,5 @@
> +WatchpointWriteBarrierPost(JSCompartment *comp, WatchpointMap::Map *map, const WatchKey &key,
> +                           const Watchpoint &val)
> +{
> +#ifdef JSGC_GENERATIONAL
> +    if (comp->gcStoreBuffer.isEnabled() &&

I don't understand why you check isEnabled here but not in the other barriers.

@@ +165,5 @@
>          jsid keyId(entry.key.id.get());
>          bool objectIsLive = IsObjectMarked(&keyObj);
>          if (objectIsLive || entry.value.held) {
>              if (!objectIsLive) {
> +                JS_SET_TRACING_LOCATION(trc, (void *)&entry.key.object);

Could you fix the rekeyFront issue as we discussed?

::: js/src/vm/ObjectImpl-inl.h
@@ +221,5 @@
>  js::ObjectImpl::setSlot(uint32_t slot, const js::Value &value)
>  {
>      MOZ_ASSERT(slotInRange(slot));
> +    MOZ_ASSERT_IF(value.isMarkable() && !IsInAtomsCompartment(value),
> +                  compartment() == ValueCompartment(value));

I think it would be better to have a single function like this:

static bool
IsValueInCompartment(js::Value v, JSCompartment *comp)
{
    if (!v.isMarkable())
        return true;
    JSCompartment *vcomp = ValueCompartment(v);
    return vcomp == comp->rt->atomsCompartment || vcomp == comp;
}

Then you can just assert IsValueInCompartment(value, compartment()) here.

@@ +231,5 @@
>  {
>      MOZ_ASSERT(getSlot(slot).isUndefined() || getSlot(slot).isMagic(JS_ARRAY_HOLE));
>      MOZ_ASSERT(slotInRange(slot));
> +    MOZ_ASSERT_IF(value.isMarkable() && !IsInAtomsCompartment(value),
> +                  compartment() == ValueCompartment(value));

and here.

@@ +240,5 @@
> +js::ObjectImpl::initCrossCompartmentSlot(uint32_t slot, const js::Value &value)
> +{
> +    MOZ_ASSERT(getSlot(slot).isUndefined() || getSlot(slot).isMagic(JS_ARRAY_HOLE));
> +    MOZ_ASSERT(slotInRange(slot));
> +    if (value.isMarkable() && !IsInAtomsCompartment(value) && compartment() != ValueCompartment(value))

Can't this condition simply be value.isMarkable()?

::: js/src/vm/String.cpp
@@ +204,5 @@
>              left.d.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
>              left.d.s.u2.base = (JSLinearString *)this;  /* will be true on exit */
>              JSString::writeBarrierPost(left.d.s.u2.base, &left.d.s.u2.base);
> +            RopeWriteBarrierPostRemove(comp, &str->d.u1.left);
> +            RopeWriteBarrierPostRemove(comp, &str->d.s.u2.right);

Mixing together the two kinds of barriers seems scary to me. Can we use the relocatable buffer for all pointers that live inside JSStrings? I think that would make this code clearer.

Comment 12

[Terrence Cole [:terrence]]

Attachment: v6

(In reply to Bill McCloskey (:billm) from comment #11)
> ::: js/src/jsapi.cpp
> @@ +4641,1 @@
> >          ida = JS_Enumerate(cx, obj);
> 
> The rooting looks kinda broken here, but that's not something to be fixed in
> this patch. In particular we have an AssertRootingUnnecessary on the stack
> while calling JS_Enumerate, which can GC.

I just went ahead and fixed it: I've already rewritten the rest of the function.
 
> ::: js/src/jswatchpoint.cpp
> @@ +53,5 @@
> > +WatchpointWriteBarrierPost(JSCompartment *comp, WatchpointMap::Map *map, const WatchKey &key,
> > +                           const Watchpoint &val)
> > +{
> > +#ifdef JSGC_GENERATIONAL
> > +    if (comp->gcStoreBuffer.isEnabled() &&
> 
> I don't understand why you check isEnabled here but not in the other
> barriers.

Premature optimization.  Killed.
 
> ::: js/src/vm/String.cpp
> @@ +204,5 @@
> >              left.d.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
> >              left.d.s.u2.base = (JSLinearString *)this;  /* will be true on exit */
> >              JSString::writeBarrierPost(left.d.s.u2.base, &left.d.s.u2.base);
> > +            RopeWriteBarrierPostRemove(comp, &str->d.u1.left);
> > +            RopeWriteBarrierPostRemove(comp, &str->d.s.u2.right);
> 
> Mixing together the two kinds of barriers seems scary to me. Can we use the
> relocatable buffer for all pointers that live inside JSStrings? I think that
> would make this code clearer.

The relocatable buffer has the potential to be significantly slower.  Again, premature optimization.

Comment 13

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

Comment on attachment 652266 [details] [diff] [review]
v6

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

The const_casts are kinda gross, but let's figure out how to fix that in another bug. I don't want to hold this up any longer.

::: js/src/jstypedarrayinlines.h
@@ +181,5 @@
> +InitTypedArrayDataPointer(JSObject *obj, ArrayBufferObject *buffer, size_t byteOffset)
> +{
> +    /*
> +     * N.B. The base of the array's data is stored in the object's
> +     * private data rather than a slot, to avoid alignment restrictions

No comma needed.

::: js/src/jsweakmap.h
@@ +190,5 @@
>  
>      void sweep(JSTracer *trc) {
>          /* Remove all entries whose keys remain unmarked. */
>          for (Enum e(*this); !e.empty(); e.popFront()) {
> +            if (!gc::IsMarked(const_cast<Key *>(&e.front().key)))

I think this one can stay as-is.

Comment 14

[Terrence Cole [:terrence]]

(In reply to Bill McCloskey (:billm) from comment #13)
> The const_casts are kinda gross, but let's figure out how to fix that in
> another bug. I don't want to hold this up any longer.

It is ugly, but to be fair, we *are* writing to a hashtable key in-place.  A const cast is probably a good signal for the absolute insanity occurring there.

One last try run to ensure that I didn't miss anything important hacking on both the marking and hashtable code, at the same time:
https://tbpl.mozilla.org/?tree=Try&rev=15ab37bf3fc5

Comment 15

[Terrence Cole [:terrence]]

Whoops, forgot to qref:
https://tbpl.mozilla.org/?tree=Try&rev=7bc7723f2a07

Comment 16

[Terrence Cole [:terrence]]

Green try run at:
https://tbpl.mozilla.org/?tree=Try&rev=c9fabd7f1fe5

Pushed to inbound at:
https://hg.mozilla.org/integration/mozilla-inbound/rev/258f0a5ed7f5

Comment 21

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/258f0a5ed7f5

Comment 22

[Ginn Chen]

In Debugger.cpp, void Debugger::markKeysInCompartment(JSTracer *tracer)

   23.56 -    typedef HashMap<HeapPtrObject, HeapPtrObject, DefaultHasher<HeapPtrObject>, RuntimeAllocPolicy>
   23.57 -        ObjectMap;
   23.58 -    const ObjectMap &objStorage = objects;
   23.59 -    for (ObjectMap::Range r = objStorage.all(); !r.empty(); r.popFront()) {
   23.60 -        const HeapPtrObject &key = r.front().key;
   23.61 +    ObjectWeakMap::Base &objStorage = objects;
   23.62 +    for (ObjectWeakMap::Base::Range r = objStorage.all(); !r.empty(); r.popFront()) {
   23.63 +        const EncapsulatedPtrObject key = r.front().key;
   23.64          HeapPtrObject tmp(key);
   23.65          gc::MarkObject(tracer, &tmp, "cross-compartment WeakMap key");
   23.66          JS_ASSERT(tmp == key);
   23.67      }

Should it be "const EncapsulatedPtrObject &key = r.front().key;" like the other 2 places below?

Comment 23

[Terrence Cole [:terrence]]

Ultimately it's going to need more fixing than that: notice the assertion.  Once we start moving objects we're going to want to update the key inline.  For now it doesn't really matter: we don't move and the assertion will ensure that code gets rewritten when we do.