Bug 1196847 - Part 2: Implement a cell hasher that uses unique id based hashes; r=jonco
authorTerrence Cole <terrence@mozilla.com>
Wed, 26 Aug 2015 14:51:35 -0700
changeset 296725 74608aa063b909315f4bf6c86c749ab1bb0c7bc5
parent 296724 cca86cd156cf57a2d7bbbc103a4cd0ec92b03f05
child 296726 5091c26998398c1fc59e14c325d63946a3ee2df8
push id5880
push userarmenzg@mozilla.com
push dateMon, 28 Sep 2015 13:39:44 +0000
reviewersjonco
bugs1196847
milestone44.0a1
Bug 1196847 - Part 2: Implement a cell hasher that uses unique id based hashes; r=jonco
js/public/HashTable.h
js/src/gc/Barrier.cpp
js/src/gc/Barrier.h
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -735,16 +735,17 @@ class HashTableEntry
     }
 
     void swap(HashTableEntry* other) {
         mozilla::Swap(keyHash, other->keyHash);
         mozilla::Swap(mem, other->mem);
     }
 
     T& get() { MOZ_ASSERT(isLive()); return *mem.addr(); }
+    NonConstT& getMutable() { MOZ_ASSERT(isLive()); return *mem.addr(); }
 
     bool isFree() const    { return keyHash == sFreeKey; }
     void clearLive()       { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); }
     void clear()           { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; }
     bool isRemoved() const { return keyHash == sRemovedKey; }
     void removeLive()      { MOZ_ASSERT(isLive()); keyHash = sRemovedKey; mem.addr()->~T(); }
     bool isLive() const    { return isLiveHash(keyHash); }
     void setCollision()               { MOZ_ASSERT(isLive()); keyHash |= sCollisionBit; }
@@ -974,16 +975,26 @@ class HashTable : private AllocPolicy
             table_.remove(*this->cur);
             removed = true;
 #ifdef JS_DEBUG
             this->validEntry = false;
             this->mutationCount = table_.mutationCount;
 #endif
         }
 
+        NonConstT& mutableFront() {
+            MOZ_ASSERT(!this->empty());
+#ifdef JS_DEBUG
+            MOZ_ASSERT(this->validEntry);
+            MOZ_ASSERT(this->generation == this->Range::table_->generation());
+            MOZ_ASSERT(this->mutationCount == this->Range::table_->mutationCount);
+#endif
+            return this->cur->getMutable();
+        }
+
         // Removes the |front()| element and re-inserts it into the table with
         // a new key at the new Lookup position.  |front()| is invalid after
         // this operation until the next call to |popFront()|.
         void rekeyFront(const Lookup& l, const Key& k) {
             MOZ_ASSERT(&k != &HashPolicy::getKey(this->cur->get()));
             Ptr p(*this->cur, table_);
             table_.rekeyWithoutRehash(p, l, k);
             rekeyed = true;
--- a/js/src/gc/Barrier.cpp
+++ b/js/src/gc/Barrier.cpp
@@ -5,17 +5,19 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "gc/Barrier.h"
 
 #include "jscompartment.h"
 #include "jsobj.h"
 
 #include "gc/Zone.h"
+#include "js/HashTable.h"
 #include "js/Value.h"
+#include "vm/ScopeObject.h"
 #include "vm/Symbol.h"
 
 #ifdef DEBUG
 
 bool
 js::HeapSlot::preconditionForSet(NativeObject* owner, Kind kind, uint32_t slot)
 {
     return kind == Slot
@@ -97,8 +99,61 @@ JS::HeapObjectPostBarrier(JSObject** obj
 }
 
 JS_PUBLIC_API(void)
 JS::HeapValuePostBarrier(JS::Value* valuep, const Value& prev, const Value& next)
 {
     MOZ_ASSERT(valuep);
     js::InternalGCMethods<JS::Value>::postBarrier(valuep, prev, next);
 }
+
+template <typename T>
+/* static */ js::HashNumber
+js::MovableCellHasher<T>::hash(const Lookup& l)
+{
+    if (!l)
+        return 0;
+
+    // We have to access the zone from-any-thread here: a worker thread may be
+    // cloning a self-hosted object from the main-thread-runtime-owned self-
+    // hosting zone into the off-main-thread runtime. The zone's uid lock will
+    // protect against multiple workers doing this simultaneously.
+    MOZ_ASSERT(CurrentThreadCanAccessZone(l->zoneFromAnyThread()) ||
+               l->zoneFromAnyThread()->isSelfHostingZone());
+
+    js::HashNumber hn;
+    if (!l->zoneFromAnyThread()->getHashCode(l, &hn))
+        js::CrashAtUnhandlableOOM("failed to get a stable hash code");
+    return hn;
+}
+
+template <typename T>
+/* static */ bool
+js::MovableCellHasher<T>::match(const Key& k, const Lookup& l)
+{
+    // Return true if both are null or false if only one is null.
+    if (!k)
+        return !l;
+    if (!l)
+        return false;
+
+    MOZ_ASSERT(k);
+    MOZ_ASSERT(l);
+    MOZ_ASSERT(CurrentThreadCanAccessZone(l->zoneFromAnyThread()) ||
+               l->zoneFromAnyThread()->isSelfHostingZone());
+
+    Zone* zone = k->zoneFromAnyThread();
+    if (zone != l->zoneFromAnyThread())
+        return false;
+    MOZ_ASSERT(zone->hasUniqueId(k));
+    MOZ_ASSERT(zone->hasUniqueId(l));
+
+    // Since both already have a uid (from hash), the get is infallible.
+    uint64_t uidK, uidL;
+    MOZ_ALWAYS_TRUE(zone->getUniqueId(k, &uidK));
+    MOZ_ALWAYS_TRUE(zone->getUniqueId(l, &uidL));
+    return uidK == uidL;
+}
+
+template struct js::MovableCellHasher<JSObject*>;
+template struct js::MovableCellHasher<js::GlobalObject*>;
+template struct js::MovableCellHasher<js::SavedFrame*>;
+template struct js::MovableCellHasher<js::ScopeObject*>;
--- a/js/src/gc/Barrier.h
+++ b/js/src/gc/Barrier.h
@@ -688,16 +688,41 @@ class ImmutableTenuredPtr
         MOZ_ASSERT(ptr->isTenured());
         value = ptr;
     }
 
     T get() const { return value; }
     const T* address() { return &value; }
 };
 
+// Provide hash codes for Cell kinds that may be relocated and, thus, not have
+// a stable address to use as the base for a hash code. Instead of the address,
+// this hasher uses Cell::getUniqueId to provide exact matches and as a base
+// for generating hash codes.
+//
+// Note: this hasher, like PointerHasher can "hash" a nullptr. While a nullptr
+// would not likely be a useful key, there are some cases where being able to
+// hash a nullptr is useful, either on purpose or because of bugs:
+// (1) existence checks where the key may happen to be null and (2) some
+// aggregate Lookup kinds embed a JSObject* that is frequently null and do not
+// null test before dispatching to the hasher.
+template <typename T>
+struct MovableCellHasher
+{
+    static_assert(mozilla::IsBaseOf<JSObject, typename mozilla::RemovePointer<T>::Type>::value,
+                  "MovableCellHasher's T must be a Cell type that may move");
+
+    using Key = T;
+    using Lookup = T;
+
+    static HashNumber hash(const Lookup& l);
+    static bool match(const Key& k, const Lookup& l);
+    static void rekey(Key& k, const Key& newKey) { k = newKey; }
+};
+
 /* Useful for hashtables with a HeapPtr as key. */
 template <class T>
 struct HeapPtrHasher
 {
     typedef HeapPtr<T> Key;
     typedef T Lookup;
 
     static HashNumber hash(Lookup obj) { return DefaultHasher<T>::hash(obj); }