Bug 843907 - Move MapObject and SetObject's key to manual post-barriers; r=jorendorff
authorTerrence Cole <terrence@mozilla.com>
Thu, 21 Feb 2013 17:36:38 -0800
changeset 126989 4e4530c957087c04c50136e203a37ebc71eb8550
parent 126988 81d4bd15053dc7cc2e51b517e21becce51e0c9d3
child 126990 d493e9a3a96cdccfa660f7168d75c78b9cdccfaf
push id25775
push usertcole@mozilla.com
push dateWed, 03 Apr 2013 00:10:43 +0000
treeherdermozilla-inbound@4e4530c95708 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs843907
milestone23.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 843907 - Move MapObject and SetObject's key to manual post-barriers; r=jorendorff
js/src/builtin/MapObject.cpp
js/src/builtin/MapObject.h
js/src/gc/RootMarking.cpp
js/src/jit-test/tests/collections/Map-Set-moving-gc.js
js/src/jsobjinlines.h
--- a/js/src/builtin/MapObject.cpp
+++ b/js/src/builtin/MapObject.cpp
@@ -224,44 +224,32 @@ class OrderedHashTable
      * Remove all entries.
      *
      * Returns false on OOM, leaving the OrderedHashTable and any live Ranges
      * in the old state.
      *
      * The effect on live Ranges is the same as removing all entries; in
      * particular, those Ranges are still live and will see any entries added
      * after a successful clear().
-     *
-     * The DoNotCallDestructors specialization is for use during a GC when the
-     * OrderedHashTable contains pointers to GC things in other arenas. Since
-     * it is invalid to touch objects in other arenas during sweeping, we need
-     * to not trigger destructors on the pointers contained in the table in
-     * this case.
      */
-    enum CallDestructors {
-        DoNotCallDtors = false,
-        DoCallDtors = true
-    };
-    bool clear(CallDestructors callDestructors = DoCallDtors) {
+    bool clear() {
         if (dataLength != 0) {
             Data **oldHashTable = hashTable;
             Data *oldData = data;
             uint32_t oldDataLength = dataLength;
 
             hashTable = NULL;
             if (!init()) {
                 // init() only mutates members on success; see comment above.
                 hashTable = oldHashTable;
                 return false;
             }
 
             alloc.free_(oldHashTable);
-            if (callDestructors)
-                destroyData(oldData, oldDataLength);
-            alloc.free_(oldData);
+            freeData(oldData, oldDataLength);
             for (Range *r = ranges; r; r = r->next)
                 r->onClear();
         }
 
         MOZ_ASSERT(hashTable);
         MOZ_ASSERT(data);
         MOZ_ASSERT(dataLength == 0);
         MOZ_ASSERT(liveCount == 0);
@@ -495,16 +483,59 @@ class OrderedHashTable
             MOZ_ASSERT(e == &ht.data[i]);
 #endif
             Ops::setKey(ht.data[i].element, k);
         }
     };
 
     Range all() { return Range(*this); }
 
+    /*
+     * Change the value of the given key.
+     *
+     * This calls Ops::hash on both the current key and the new key.
+     * Ops::hash on the current key must return the same hash code as
+     * when the entry was added to the table.
+     */
+    void rekeyOneEntry(const Key &current, const Key &newKey, const T &element) {
+        if (current == newKey)
+            return;
+
+        Data *entry = lookup(current, prepareHash(current));
+        if (!entry)
+            return;
+
+        HashNumber oldHash = prepareHash(current) >> hashShift;
+        HashNumber newHash = prepareHash(newKey) >> hashShift;
+
+        entry->element = element;
+
+        // Remove this entry from its old hash chain. (If this crashes
+        // reading NULL, it would mean we did not find this entry on
+        // the hash chain where we expected it. That probably means the
+        // key's hash code changed since it was inserted, breaking the
+        // hash code invariant.)
+        Data **ep = &hashTable[oldHash];
+        while (*ep != entry)
+            ep = &(*ep)->chain;
+        *ep = entry->chain;
+
+        // Add it to the new hash chain. We could just insert it at the
+        // beginning of the chain. Instead, we do a bit of work to
+        // preserve the invariant that hash chains always go in reverse
+        // insertion order (descending memory order). No code currently
+        // depends on this invariant, so it's fine to kill it if
+        // needed.
+        ep = &hashTable[newHash];
+        while (*ep && *ep > entry)
+            ep = &(*ep)->chain;
+        entry->chain = *ep;
+        *ep = entry;
+    }
+
   private:
     /* Logarithm base 2 of the number of buckets in the hash table initially. */
     static uint32_t initialBucketsLog2() { return 1; }
     static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); }
 
     /*
      * The maximum load factor (mean number of entries per bucket).
      * It is an invariant that
@@ -697,18 +728,24 @@ class OrderedHashMap
     bool init()                                     { return impl.init(); }
     uint32_t count() const                          { return impl.count(); }
     bool has(const Key &key) const                  { return impl.has(key); }
     Range all()                                     { return impl.all(); }
     const Entry *get(const Key &key) const          { return impl.get(key); }
     Entry *get(const Key &key)                      { return impl.get(key); }
     bool put(const Key &key, const Value &value)    { return impl.put(Entry(key, value)); }
     bool remove(const Key &key, bool *foundp)       { return impl.remove(key, foundp); }
-    bool clear()                                    { return impl.clear(Impl::DoCallDtors); }
-    bool clearWithoutCallingDestructors()           { return impl.clear(Impl::DoNotCallDtors); }
+    bool clear()                                    { return impl.clear(); }
+
+    void rekeyOneEntry(const Key &current, const Key &newKey) {
+        const Entry *e = get(current);
+        if (!e)
+            return;
+        return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value));
+    }
 };
 
 template <class T, class OrderedHashPolicy, class AllocPolicy>
 class OrderedHashSet
 {
   private:
     struct SetOps : OrderedHashPolicy
     {
@@ -725,30 +762,33 @@ class OrderedHashSet
 
     OrderedHashSet(AllocPolicy ap = AllocPolicy()) : impl(ap) {}
     bool init()                                     { return impl.init(); }
     uint32_t count() const                          { return impl.count(); }
     bool has(const T &value) const                  { return impl.has(value); }
     Range all()                                     { return impl.all(); }
     bool put(const T &value)                        { return impl.put(value); }
     bool remove(const T &value, bool *foundp)       { return impl.remove(value, foundp); }
-    bool clear()                                    { return impl.clear(Impl::DoCallDtors); }
-    bool clearWithoutCallingDestructors()           { return impl.clear(Impl::DoNotCallDtors); }
+    bool clear()                                    { return impl.clear(); }
+
+    void rekeyOneEntry(const T &current, const T &newKey) {
+        return impl.rekeyOneEntry(current, newKey, newKey);
+    }
 };
 
 }  // namespace js
 
 
 /*** HashableValue *******************************************************************************/
 
 bool
 HashableValue::setValue(JSContext *cx, const Value &v)
 {
     if (v.isString()) {
-        // Atomize so that hash() and equals() are fast and infallible.
+        // Atomize so that hash() and operator==() are fast and infallible.
         JSString *str = AtomizeString<CanGC>(cx, v.toString(), DoNotInternAtom);
         if (!str)
             return false;
         value = StringValue(str);
     } else if (v.isDouble()) {
         double d = v.toDouble();
         int32_t i;
         if (MOZ_DOUBLE_IS_INT32(d, &i)) {
@@ -774,17 +814,17 @@ HashableValue::hash() const
 {
     // HashableValue::setValue normalizes values so that the SameValue relation
     // on HashableValues is the same as the == relationship on
     // value.data.asBits.
     return value.asRawBits();
 }
 
 bool
-HashableValue::equals(const HashableValue &other) const
+HashableValue::operator==(const HashableValue &other) const
 {
     // Two HashableValues are equal if they have equal bits.
     bool b = (value.asRawBits() == other.value.asRawBits());
 
 #ifdef DEBUG
     bool same;
     JS_ASSERT(SameValue(NULL, value, other.value, &same));
     JS_ASSERT(same == b);
@@ -1065,23 +1105,58 @@ MapObject::mark(JSTracer *trc, RawObject
     if (ValueMap *map = obj->asMap().getData()) {
         for (ValueMap::Range r = map->all(); !r.empty(); r.popFront()) {
             MarkKey(r, r.front().key, trc);
             gc::MarkValue(trc, &r.front().value, "value");
         }
     }
 }
 
+#ifdef JSGC_GENERATIONAL
+template <typename TableType>
+class OrderedHashTableRef : public gc::BufferableRef
+{
+    TableType *table;
+    HashableValue key;
+
+  public:
+    OrderedHashTableRef(TableType *t, const HashableValue &k) : table(t), key(k) {}
+
+    bool match(void *location) {
+        if (!table->has(key))
+            return false;
+        for (typename TableType::Range r = table->all(); !r.empty(); r.popFront()) {
+            if ((void*)&r.front() == location)
+                return true;
+        }
+        return false;
+    }
+
+    void mark(JSTracer *trc) {
+        HashableValue prior = key;
+        key = key.mark(trc);
+        table->rekeyOneEntry(prior, key);
+    }
+};
+#endif
+
+template <typename TableType>
+static void
+WriteBarrierPost(JSRuntime *rt, TableType *table, const HashableValue &key)
+{
+#ifdef JSGC_GENERATIONAL
+    rt->gcStoreBuffer.putGeneric(OrderedHashTableRef<TableType>(table, key));
+#endif
+}
+
 void
 MapObject::finalize(FreeOp *fop, RawObject obj)
 {
-    if (ValueMap *map = obj->asMap().getData()) {
-        map->clearWithoutCallingDestructors();
+    if (ValueMap *map = obj->asMap().getData())
         fop->delete_(map);
-    }
 }
 
 JSBool
 MapObject::construct(JSContext *cx, unsigned argc, Value *vp)
 {
     Rooted<JSObject*> obj(cx, NewBuiltinClassInstance(cx, &class_));
     if (!obj)
         return false;
@@ -1116,16 +1191,17 @@ MapObject::construct(JSContext *cx, unsi
             if (!JSObject::getElement(cx, pairobj, pairobj, 1, &val))
                 return false;
 
             RelocatableValue rval(val);
             if (!map->put(hkey, rval)) {
                 js_ReportOutOfMemory(cx);
                 return false;
             }
+            WriteBarrierPost(cx->runtime, map, hkey);
         }
         if (!iter.close())
             return false;
     }
 
     args.rval().setObject(*obj);
     return true;
 }
@@ -1210,21 +1286,22 @@ MapObject::has(JSContext *cx, unsigned a
 
 bool
 MapObject::set_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(MapObject::is(args.thisv()));
 
     ValueMap &map = extract(args);
     ARG0_KEY(cx, args, key);
-    RelocatableValue rval(args.length() > 1 ? args[1] : UndefinedValue());
+    RelocatableValue rval(args.get(1));
     if (!map.put(key, rval)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
+    WriteBarrierPost(cx->runtime, &map, key);
     args.rval().setUndefined();
     return true;
 }
 
 JSBool
 MapObject::set(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
@@ -1523,20 +1600,18 @@ SetObject::mark(JSTracer *trc, RawObject
             MarkKey(r, r.front(), trc);
     }
 }
 
 void
 SetObject::finalize(FreeOp *fop, RawObject obj)
 {
     SetObject *setobj = static_cast<SetObject *>(obj);
-    if (ValueSet *set = setobj->getData()) {
-        set->clearWithoutCallingDestructors();
+    if (ValueSet *set = setobj->getData())
         fop->delete_(set);
-    }
 }
 
 JSBool
 SetObject::construct(JSContext *cx, unsigned argc, Value *vp)
 {
     Rooted<JSObject*> obj(cx, NewBuiltinClassInstance(cx, &class_));
     if (!obj)
         return false;
@@ -1557,16 +1632,17 @@ SetObject::construct(JSContext *cx, unsi
             HashableValue key;
             HashableValue::AutoRooter hkeyRoot(cx, &key);
             if (!key.setValue(cx, iter.value()))
                 return false;
             if (!set->put(key)) {
                 js_ReportOutOfMemory(cx);
                 return false;
             }
+            WriteBarrierPost(cx->runtime, set, key);
         }
         if (!iter.close())
             return false;
     }
 
     args.rval().setObject(*obj);
     return true;
 }
@@ -1627,16 +1703,17 @@ SetObject::add_impl(JSContext *cx, CallA
     JS_ASSERT(is(args.thisv()));
 
     ValueSet &set = extract(args);
     ARG0_KEY(cx, args, key);
     if (!set.put(key)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
+    WriteBarrierPost(cx->runtime, &set, key);
     args.rval().setUndefined();
     return true;
 }
 
 JSBool
 SetObject::add(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
--- a/js/src/builtin/MapObject.h
+++ b/js/src/builtin/MapObject.h
@@ -27,26 +27,26 @@ namespace js {
  */
 class HashableValue {
     EncapsulatedValue value;
 
   public:
     struct Hasher {
         typedef HashableValue Lookup;
         static HashNumber hash(const Lookup &v) { return v.hash(); }
-        static bool match(const HashableValue &k, const Lookup &l) { return k.equals(l); }
+        static bool match(const HashableValue &k, const Lookup &l) { return k == l; }
         static bool isEmpty(const HashableValue &v) { return v.value.isMagic(JS_HASH_KEY_EMPTY); }
         static void makeEmpty(HashableValue *vp) { vp->value = MagicValue(JS_HASH_KEY_EMPTY); }
     };
 
     HashableValue() : value(UndefinedValue()) {}
 
     bool setValue(JSContext *cx, const Value &v);
     HashNumber hash() const;
-    bool equals(const HashableValue &other) const;
+    bool operator==(const HashableValue &other) const;
     HashableValue mark(JSTracer *trc) const;
     Value get() const { return value.get(); }
 
     class AutoRooter : private AutoGCRooter
     {
       public:
         explicit AutoRooter(JSContext *cx, HashableValue *v_
                             MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
--- a/js/src/gc/RootMarking.cpp
+++ b/js/src/gc/RootMarking.cpp
@@ -11,16 +11,17 @@
 
 #include "jsapi.h"
 #include "jscntxt.h"
 #include "jsgc.h"
 #include "jsonparser.h"
 #include "jsprf.h"
 #include "jswatchpoint.h"
 
+#include "builtin/MapObject.h"
 #include "frontend/Parser.h"
 #include "gc/GCInternals.h"
 #include "gc/Marking.h"
 #ifdef JS_ION
 # include "ion/IonMacroAssembler.h"
 # include "ion/IonFrameIterator.h"
 #endif
 #include "js/HashTable.h"
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-Set-moving-gc.js
@@ -0,0 +1,16 @@
+var m = new Map;
+var s = new Set;
+
+var A = [];
+for (var i = 0; i < 1024; ++i) {
+    var key = {i:i};
+    m.set(key, i);
+    s.add(key);
+    A.push(key);
+}
+gc();
+for (var i in A) {
+    var key = A[i];
+    assertEq(m.has(key), true);
+    assertEq(s.has(key), true);
+}
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -19,17 +19,16 @@
 #include "jsobj.h"
 #include "jsprobes.h"
 #include "jspropertytree.h"
 #include "jsproxy.h"
 #include "jsstr.h"
 #include "jstypedarray.h"
 #include "jswrapper.h"
 
-#include "builtin/MapObject.h"
 #include "builtin/Iterator-inl.h"
 #include "gc/Barrier.h"
 #include "gc/Marking.h"
 #include "js/MemoryMetrics.h"
 #include "js/RootingAPI.h"
 #include "js/TemplateLib.h"
 #include "vm/BooleanObject.h"
 #include "vm/GlobalObject.h"