Bug 1338894 - Rewrite NurseryAwareHashMap to speed up WrapperMap sweeping. r=jonco draft
authorJan de Mooij <jdemooij@mozilla.com>
Mon, 13 Feb 2017 19:11:19 +0100
changeset 485882 851f59b0ea7ec3c03a6dde04403d64a1d3caa4fc
parent 485881 558c361c937aaca034f7d10f12a7e48b41b2d793
child 485883 defc9f9bee5e1305b970be57c80345b3b3633105
push id45870
push userbmo:kechen@mozilla.com
push dateFri, 17 Feb 2017 09:36:54 +0000
reviewersjonco
bugs1338894
milestone54.0a1
Bug 1338894 - Rewrite NurseryAwareHashMap to speed up WrapperMap sweeping. r=jonco
js/src/gc/NurseryAwareHashMap.h
js/src/jsapi.cpp
js/src/jscompartment.cpp
js/src/jscompartment.h
js/src/proxy/CrossCompartmentWrapper.cpp
js/src/vm/Debugger.cpp
--- a/js/src/gc/NurseryAwareHashMap.h
+++ b/js/src/gc/NurseryAwareHashMap.h
@@ -65,101 +65,171 @@ class UnsafeBareReadBarriered : public R
 template <typename Key,
           typename Value,
           typename HashPolicy = DefaultHasher<Key>,
           typename AllocPolicy = TempAllocPolicy>
 class NurseryAwareHashMap
 {
     using BarrieredValue = detail::UnsafeBareReadBarriered<Value>;
     using MapType = GCRekeyableHashMap<Key, BarrieredValue, HashPolicy, AllocPolicy>;
-    MapType map;
+
+    // Contains entries that have a nursery-allocated key or value (or both).
+    MapType nurseryMap_;
 
-    // Keep a list of all keys for which JS::GCPolicy<Key>::isTenured is false.
-    // This lets us avoid a full traveral of the map on each minor GC, keeping
-    // the minor GC times proportional to the nursery heap size.
-    Vector<Key, 0, AllocPolicy> nurseryEntries;
+    // All entries in this map have a tenured key and value.
+    MapType tenuredMap_;
+
+    // Keys and values usually have the same lifetime (for the WrapperMap we
+    // ensure this when we allocate the wrapper object). If this flag is set,
+    // it means nurseryMap_ contains a tenured key with a nursery allocated
+    // value.
+    bool nurseryMapContainsTenuredKeys_;
 
   public:
     using Lookup = typename MapType::Lookup;
-    using Ptr = typename MapType::Ptr;
-    using Range = typename MapType::Range;
+
+    class Ptr {
+        friend class NurseryAwareHashMap;
+
+        typename MapType::Ptr ptr_;
+        bool isNurseryMap_;
+
+      public:
+        Ptr(typename MapType::Ptr ptr, bool isNurseryMap)
+          : ptr_(ptr), isNurseryMap_(isNurseryMap)
+        {}
 
-    explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy()) : map(a) {}
+        const typename MapType::Entry& operator*() const { return *ptr_; }
+        const typename MapType::Entry* operator->() const { return &*ptr_; }
+
+        bool found() const { return ptr_.found(); }
+        explicit operator bool() const { return bool(ptr_); }
+    };
 
-    MOZ_MUST_USE bool init(uint32_t len = 16) { return map.init(len); }
+    explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy())
+      : nurseryMap_(a), tenuredMap_(a), nurseryMapContainsTenuredKeys_(false)
+    {}
+
+    MOZ_MUST_USE bool init(uint32_t len = 16) {
+        return nurseryMap_.init(len) && tenuredMap_.init(len);
+    }
+
+    bool empty() const { return nurseryMap_.empty() && tenuredMap_.empty(); }
 
-    bool empty() const { return map.empty(); }
-    Ptr lookup(const Lookup& l) const { return map.lookup(l); }
-    void remove(Ptr p) { map.remove(p); }
-    Range all() const { return map.all(); }
-    struct Enum : public MapType::Enum {
-        explicit Enum(NurseryAwareHashMap& namap) : MapType::Enum(namap.map) {}
+    Ptr lookup(const Lookup& l) const {
+        if (JS::GCPolicy<Key>::isTenured(l)) {
+            // If we find the key in the tenuredMap_, we're done. If we don't
+            // find it there and we know nurseryMap_ contains tenured keys
+            // (hopefully uncommon), we have to try nurseryMap_ as well.
+            typename MapType::Ptr p = tenuredMap_.lookup(l);
+            if (p || !nurseryMapContainsTenuredKeys_)
+                return Ptr(p, /* isNurseryMap = */ false);
+        }
+        return Ptr(nurseryMap_.lookup(l), /* isNurseryMap = */ true);
+    }
+
+    void remove(Ptr p) {
+        if (p.isNurseryMap_)
+            nurseryMap_.remove(p.ptr_);
+        else
+            tenuredMap_.remove(p.ptr_);
+    }
+
+    class Enum {
+        // First iterate over the nursery map. When nurseryEnum_ becomes
+        // empty() we switch to tenuredEnum_.
+        typename MapType::Enum nurseryEnum_;
+        typename MapType::Enum tenuredEnum_;
+
+        const typename MapType::Enum& currentEnum() const {
+            return nurseryEnum_.empty() ? tenuredEnum_ : nurseryEnum_;
+        }
+        typename MapType::Enum& currentEnum() {
+            return nurseryEnum_.empty() ? tenuredEnum_ : nurseryEnum_;
+        }
+
+      public:
+        explicit Enum(NurseryAwareHashMap& namap)
+          : nurseryEnum_(namap.nurseryMap_), tenuredEnum_(namap.tenuredMap_)
+        {}
+
+        typename MapType::Entry& front() const { return currentEnum().front(); }
+        void popFront() { currentEnum().popFront(); }
+        void removeFront() { currentEnum().removeFront(); }
+
+        bool empty() const { return nurseryEnum_.empty() && tenuredEnum_.empty(); }
     };
+
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
-        return map.sizeOfExcludingThis(mallocSizeOf);
+        size_t size = nurseryMap_.sizeOfExcludingThis(mallocSizeOf);
+        size += tenuredMap_.sizeOfExcludingThis(mallocSizeOf);
+        return size;
     }
     size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
-        return map.sizeOfIncludingThis(mallocSizeOf);
+        size_t size = nurseryMap_.sizeOfIncludingThis(mallocSizeOf);
+        size += tenuredMap_.sizeOfIncludingThis(mallocSizeOf);
+        return size;
+    }
+
+    MOZ_MUST_USE bool putNew(const Key& k, const Value& v) {
+        MOZ_ASSERT(!tenuredMap_.has(k));
+        MOZ_ASSERT(!nurseryMap_.has(k));
+
+        bool tenuredKey = JS::GCPolicy<Key>::isTenured(k);
+        if (tenuredKey && JS::GCPolicy<Value>::isTenured(v))
+            return tenuredMap_.putNew(k, v);
+
+        if (tenuredKey)
+            nurseryMapContainsTenuredKeys_ = true;
+
+        return nurseryMap_.putNew(k, v);
     }
 
     MOZ_MUST_USE bool put(const Key& k, const Value& v) {
-        auto p = map.lookupForAdd(k);
-        if (p) {
-            if (!JS::GCPolicy<Key>::isTenured(k) || !JS::GCPolicy<Value>::isTenured(v)) {
-                if (!nurseryEntries.append(k))
-                    return false;
-            }
-            p->value() = v;
-            return true;
-        }
-
-        bool ok = map.add(p, k, v);
-        if (!ok)
-            return false;
-
-        if (!JS::GCPolicy<Key>::isTenured(k) || !JS::GCPolicy<Value>::isTenured(v)) {
-            if (!nurseryEntries.append(k)) {
-                map.remove(k);
-                return false;
-            }
-        }
-
-        return true;
+        // For simplicity, just remove the entry and forward to putNew for now.
+        // Performance-sensitive callers should prefer putNew.
+        if (Ptr p = lookup(k))
+            remove(p);
+        return putNew(k, v);
     }
 
     void sweepAfterMinorGC(JSTracer* trc) {
-        for (auto& key : nurseryEntries) {
-            auto p = map.lookup(key);
-            if (!p)
-                continue;
+        for (typename MapType::Enum e(nurseryMap_); !e.empty(); e.popFront()) {
+            auto& key = e.front().key();
+            auto& value = e.front().value();
 
             // Drop the entry if the value is not marked.
-            if (JS::GCPolicy<BarrieredValue>::needsSweep(&p->value())) {
-                map.remove(key);
+            if (JS::GCPolicy<BarrieredValue>::needsSweep(&value))
                 continue;
-            }
 
-            // Update and relocate the key, if the value is still needed.
+            // Insert the key/value in the tenured map, if the value is still
+            // needed.
             //
-            // Note that this currently assumes that all Value will contain a
+            // Note that this currently assumes that each Value will contain a
             // strong reference to Key, as per its use as the
             // CrossCompartmentWrapperMap. We may need to make the following
             // behavior more dynamic if we use this map in other nursery-aware
             // contexts.
-            Key copy(key);
-            mozilla::DebugOnly<bool> sweepKey = JS::GCPolicy<Key>::needsSweep(&copy);
+
+            Key keyCopy(key);
+            mozilla::DebugOnly<bool> sweepKey = JS::GCPolicy<Key>::needsSweep(&keyCopy);
             MOZ_ASSERT(!sweepKey);
-            map.rekeyIfMoved(key, copy);
+
+            AutoEnterOOMUnsafeRegion oomUnsafe;
+            if (!tenuredMap_.putNew(keyCopy, value))
+                oomUnsafe.crash("NurseryAwareHashMap sweepAfterMinorGC");
         }
-        nurseryEntries.clear();
+
+        nurseryMap_.clear();
+        nurseryMapContainsTenuredKeys_ = false;
     }
 
     void sweep() {
-        MOZ_ASSERT(nurseryEntries.empty());
-        map.sweep();
+        MOZ_ASSERT(nurseryMap_.empty());
+        tenuredMap_.sweep();
     }
 };
 
 } // namespace js
 
 namespace JS {
 template <typename T>
 struct GCPolicy<js::detail::UnsafeBareReadBarriered<T>>
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -907,18 +907,21 @@ JS_TransplantObject(JSContext* cx, Handl
     if (origobj->compartment() != destination) {
         RootedObject newIdentityWrapper(cx, newIdentity);
         AutoCompartment ac(cx, origobj);
         if (!JS_WrapObject(cx, &newIdentityWrapper))
             MOZ_CRASH();
         MOZ_ASSERT(Wrapper::wrappedObject(newIdentityWrapper) == newIdentity);
         if (!JSObject::swap(cx, origobj, newIdentityWrapper))
             MOZ_CRASH();
-        if (!origobj->compartment()->putWrapper(cx, CrossCompartmentKey(newIdentity), origv))
+        if (!origobj->compartment()->putWrapperMaybeUpdate(cx, CrossCompartmentKey(newIdentity),
+                                                           origv))
+        {
             MOZ_CRASH();
+        }
     }
 
     // The new identity object might be one of several things. Return it to avoid
     // ambiguity.
     return newIdentity;
 }
 
 /*
--- a/js/src/jscompartment.cpp
+++ b/js/src/jscompartment.cpp
@@ -245,18 +245,33 @@ JSCompartment::checkWrapperMapAfterMovin
 
         WrapperMap::Ptr ptr = crossCompartmentWrappers.lookup(e.front().key());
         MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
     }
 }
 #endif
 
 bool
-JSCompartment::putWrapper(JSContext* cx, const CrossCompartmentKey& wrapped,
-                          const js::Value& wrapper)
+JSCompartment::putNewWrapper(JSContext* cx, const CrossCompartmentKey& wrapped,
+                             const js::Value& wrapper)
+{
+    MOZ_ASSERT(wrapped.is<JSString*>() == wrapper.isString());
+    MOZ_ASSERT_IF(!wrapped.is<JSString*>(), wrapper.isObject());
+
+    if (!crossCompartmentWrappers.putNew(wrapped, wrapper)) {
+        ReportOutOfMemory(cx);
+        return false;
+    }
+
+    return true;
+}
+
+bool
+JSCompartment::putWrapperMaybeUpdate(JSContext* cx, const CrossCompartmentKey& wrapped,
+                                     const js::Value& wrapper)
 {
     MOZ_ASSERT(wrapped.is<JSString*>() == wrapper.isString());
     MOZ_ASSERT_IF(!wrapped.is<JSString*>(), wrapper.isObject());
 
     if (!crossCompartmentWrappers.put(wrapped, wrapper)) {
         ReportOutOfMemory(cx);
         return false;
     }
@@ -337,17 +352,17 @@ JSCompartment::wrap(JSContext* cx, Mutab
         strp.set(p->value().get().toString());
         return true;
     }
 
     /* No dice. Make a copy, and cache it. */
     JSString* copy = CopyStringPure(cx, str);
     if (!copy)
         return false;
-    if (!putWrapper(cx, CrossCompartmentKey(key), StringValue(copy)))
+    if (!putNewWrapper(cx, CrossCompartmentKey(key), StringValue(copy)))
         return false;
 
     strp.set(copy);
     return true;
 }
 
 bool
 JSCompartment::getNonWrapperObjectForCurrentCompartment(JSContext* cx, MutableHandleObject obj)
@@ -427,17 +442,17 @@ JSCompartment::getOrCreateWrapper(JSCont
     RootedObject wrapper(cx, wrap(cx, existing, obj));
     if (!wrapper)
         return false;
 
     // We maintain the invariant that the key in the cross-compartment wrapper
     // map is always directly wrapped by the value.
     MOZ_ASSERT(Wrapper::wrappedObject(wrapper) == &key.get().toObject());
 
-    if (!putWrapper(cx, CrossCompartmentKey(key), ObjectValue(*wrapper))) {
+    if (!putNewWrapper(cx, CrossCompartmentKey(key), ObjectValue(*wrapper))) {
         // Enforce the invariant that all cross-compartment wrapper object are
         // in the map by nuking the wrapper if we couldn't add it.
         // Unfortunately it's possible for the wrapper to still be marked if we
         // took this path, for example if the object metadata callback stashes a
         // reference to it.
         if (wrapper->is<CrossCompartmentWrapperObject>())
             NukeCrossCompartmentWrapper(cx, wrapper);
         return false;
--- a/js/src/jscompartment.h
+++ b/js/src/jscompartment.h
@@ -429,19 +429,16 @@ struct JSCompartment
 
   private:
     const js::AllocationMetadataBuilder *allocationMetadataBuilder;
 
     js::SavedStacks              savedStacks_;
 
     js::WrapperMap               crossCompartmentWrappers;
 
-    using CCKeyVector = mozilla::Vector<js::CrossCompartmentKey, 0, js::SystemAllocPolicy>;
-    CCKeyVector                  nurseryCCKeys;
-
     // The global environment record's [[VarNames]] list that contains all
     // names declared using FunctionDeclaration, GeneratorDeclaration, and
     // VariableDeclaration declarations in global code in this compartment.
     // Names are only removed from this list by a |delete IdentifierReference|
     // that successfully removes that global property.
     JS::GCHashSet<JSAtom*,
                   js::DefaultHasher<JSAtom*>,
                   js::SystemAllocPolicy> varNames_;
@@ -585,18 +582,20 @@ struct JSCompartment
     MOZ_MUST_USE inline bool wrap(JSContext* cx, JS::MutableHandleValue vp);
 
     MOZ_MUST_USE bool wrap(JSContext* cx, js::MutableHandleString strp);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandleObject obj);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandle<js::PropertyDescriptor> desc);
     MOZ_MUST_USE bool wrap(JSContext* cx, JS::MutableHandle<JS::GCVector<JS::Value>> vec);
     MOZ_MUST_USE bool rewrap(JSContext* cx, JS::MutableHandleObject obj, JS::HandleObject existing);
 
-    MOZ_MUST_USE bool putWrapper(JSContext* cx, const js::CrossCompartmentKey& wrapped,
-                                 const js::Value& wrapper);
+    MOZ_MUST_USE bool putNewWrapper(JSContext* cx, const js::CrossCompartmentKey& wrapped,
+                                    const js::Value& wrapper);
+    MOZ_MUST_USE bool putWrapperMaybeUpdate(JSContext* cx, const js::CrossCompartmentKey& wrapped,
+                                            const js::Value& wrapper);
 
     js::WrapperMap::Ptr lookupWrapper(const js::Value& wrapped) const {
         return crossCompartmentWrappers.lookup(js::CrossCompartmentKey(wrapped));
     }
 
     void removeWrapper(js::WrapperMap::Ptr p) {
         crossCompartmentWrappers.remove(p);
     }
--- a/js/src/proxy/CrossCompartmentWrapper.cpp
+++ b/js/src/proxy/CrossCompartmentWrapper.cpp
@@ -615,18 +615,21 @@ js::RemapWrapper(JSContext* cx, JSObject
 
     // Before swapping, this wrapper came out of wrap(), which enforces the
     // invariant that the wrapper in the map points directly to the key.
     MOZ_ASSERT(Wrapper::wrappedObject(wobj) == newTarget);
 
     // Update the entry in the compartment's wrapper map to point to the old
     // wrapper, which has now been updated (via reuse or swap).
     MOZ_ASSERT(wobj->is<WrapperObject>());
-    if (!wcompartment->putWrapper(cx, CrossCompartmentKey(newTarget), ObjectValue(*wobj)))
+    if (!wcompartment->putWrapperMaybeUpdate(cx, CrossCompartmentKey(newTarget),
+                                             ObjectValue(*wobj)))
+    {
         MOZ_CRASH();
+    }
 }
 
 // Remap all cross-compartment wrappers pointing to |oldTarget| to point to
 // |newTarget|. All wrappers are recomputed.
 JS_FRIEND_API(bool)
 js::RemapAllWrappersForObject(JSContext* cx, JSObject* oldTargetArg,
                               JSObject* newTargetArg)
 {
--- a/js/src/vm/Debugger.cpp
+++ b/js/src/vm/Debugger.cpp
@@ -1133,17 +1133,17 @@ Debugger::wrapEnvironment(JSContext* cx,
             return false;
 
         if (!p.add(cx, environments, env, envobj)) {
             NukeDebuggerWrapper(envobj);
             return false;
         }
 
         CrossCompartmentKey key(object, env, CrossCompartmentKey::DebuggerEnvironment);
-        if (!object->compartment()->putWrapper(cx, key, ObjectValue(*envobj))) {
+        if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*envobj))) {
             NukeDebuggerWrapper(envobj);
             environments.remove(env);
             return false;
         }
 
         result.set(envobj);
     }
 
@@ -1220,17 +1220,17 @@ Debugger::wrapDebuggeeObject(JSContext* 
 
         if (!p.add(cx, objects, obj, dobj)) {
             NukeDebuggerWrapper(dobj);
             return false;
         }
 
         if (obj->compartment() != object->compartment()) {
             CrossCompartmentKey key(object, obj, CrossCompartmentKey::DebuggerObject);
-            if (!object->compartment()->putWrapper(cx, key, ObjectValue(*dobj))) {
+            if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*dobj))) {
                 NukeDebuggerWrapper(dobj);
                 objects.remove(obj);
                 ReportOutOfMemory(cx);
                 return false;
             }
         }
 
         result.set(dobj);
@@ -5516,17 +5516,17 @@ Debugger::wrapVariantReferent(JSContext*
         if (!wrapper)
             return nullptr;
 
         if (!p.add(cx, map, untaggedReferent, wrapper)) {
             NukeDebuggerWrapper(wrapper);
             return nullptr;
         }
 
-        if (!object->compartment()->putWrapper(cx, key, ObjectValue(*wrapper))) {
+        if (!object->compartment()->putNewWrapper(cx, key, ObjectValue(*wrapper))) {
             NukeDebuggerWrapper(wrapper);
             map.remove(untaggedReferent);
             ReportOutOfMemory(cx);
             return nullptr;
         }
 
     }