Bug 729940 - Part 2: Stop using crappy hash functions in the js engine. r=bhackett
authorJustin Lebar <justin.lebar@gmail.com>
Sun, 04 Mar 2012 13:49:41 -0500
changeset 88433 bfbe72a6251d86339b9301e529d4bc00fe1905cb
parent 88432 939fd023e9a48df3419e94a1bfa268c306e22a39
child 88434 d75775dfc565a340e2ab4ece2d3e89d17729552a
push id157
push userMs2ger@gmail.com
push dateWed, 07 Mar 2012 19:27:10 +0000
reviewersbhackett
bugs729940
milestone13.0a1
Bug 729940 - Part 2: Stop using crappy hash functions in the js engine. r=bhackett
js/src/jsatom.h
js/src/jsdhash.cpp
js/src/jshash.cpp
js/src/jsinfer.cpp
js/src/jsinferinlines.h
js/src/jsobj.cpp
js/src/jsobjinlines.h
js/src/jspropertycache.h
js/src/jsscope.cpp
js/src/jsscopeinlines.h
js/src/jswatchpoint.cpp
js/xpconnect/src/XPCMaps.cpp
--- a/js/src/jsatom.h
+++ b/js/src/jsatom.h
@@ -46,16 +46,17 @@
 #include "jsapi.h"
 #include "jsprvtd.h"
 #include "jshash.h"
 #include "jspubtd.h"
 #include "jslock.h"
 
 #include "gc/Barrier.h"
 #include "js/HashTable.h"
+#include "mozilla/HashFunctions.h"
 
 struct JSIdArray {
     int length;
     js::HeapId vector[1];    /* actually, length jsid words */
 };
 
 /* Engine-internal extensions of jsid */
 
@@ -168,19 +169,21 @@ extern const char *
 js_AtomToPrintableString(JSContext *cx, JSAtom *atom, JSAutoByteString *bytes);
 
 namespace js {
 
 /* Compute a hash function from chars/length. */
 inline uint32_t
 HashChars(const jschar *chars, size_t length)
 {
+    // We could call mozilla::HashString here, but that isn't inlined.
+
     uint32_t h = 0;
-    for (; length; chars++, length--)
-        h = JS_ROTATE_LEFT32(h, 4) ^ *chars;
+    for (size_t i = 0; i < length; i++)
+        h = mozilla::AddToHash(h, chars[i]);
     return h;
 }
 
 class AtomStateEntry
 {
     uintptr_t bits;
 
     static const uintptr_t NO_TAG_MASK = uintptr_t(-1) - 1;
--- a/js/src/jsdhash.cpp
+++ b/js/src/jsdhash.cpp
@@ -43,16 +43,17 @@
  *
  * Try to keep this file in sync with xpcom/glue/pldhash.cpp.
  */
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "jsdhash.h"
 #include "jsutil.h"
+#include "mozilla/HashFunctions.h"
 
 using namespace js;
 
 #ifdef JS_DHASHMETER
 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
 #  include "nsTraceMalloc.h"
 # endif
 # define METER(x)       x
@@ -120,23 +121,17 @@ JS_PUBLIC_API(void)
 JS_DHashFreeTable(JSDHashTable *table, void *ptr)
 {
     UnwantedForeground::free_(ptr);
 }
 
 JS_PUBLIC_API(JSDHashNumber)
 JS_DHashStringKey(JSDHashTable *table, const void *key)
 {
-    JSDHashNumber h;
-    const unsigned char *s;
-
-    h = 0;
-    for (s = (const unsigned char *) key; *s != '\0'; s++)
-        h = JS_ROTATE_LEFT32(h, 4) ^ *s;
-    return h;
+    return mozilla::HashString(static_cast<const char*>(key));
 }
 
 JS_PUBLIC_API(JSDHashNumber)
 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
 {
     return (JSDHashNumber)(uintptr_t)key >> 2;
 }
 
--- a/js/src/jshash.cpp
+++ b/js/src/jshash.cpp
@@ -40,16 +40,17 @@
 /*
  * PR hash table package.
  */
 #include <stdlib.h>
 #include <string.h>
 #include "jstypes.h"
 #include "jsutil.h"
 #include "jshash.h"
+#include "mozilla/HashFunctions.h"
 
 using namespace js;
 
 /* Compute the number of buckets in ht */
 #define NBUCKETS(ht)    JS_BIT(JS_HASH_BITS - (ht)->shift)
 
 /* The smallest table has 16 buckets */
 #define MINBUCKETSLOG2  4
@@ -456,22 +457,16 @@ JS_HashTableDump(JSHashTable *ht, JSHash
     JS_HashTableDumpMeter(ht, dump, fp);
 #endif
     return count;
 }
 
 JS_PUBLIC_API(JSHashNumber)
 JS_HashString(const void *key)
 {
-    JSHashNumber h;
-    const unsigned char *s;
-
-    h = 0;
-    for (s = (const unsigned char *)key; *s; s++)
-        h = JS_ROTATE_LEFT32(h, 4) ^ *s;
-    return h;
+    return mozilla::HashString(static_cast<const char*>(key));
 }
 
 JS_PUBLIC_API(int)
 JS_CompareValues(const void *v1, const void *v2)
 {
     return v1 == v2;
 }
--- a/js/src/jsinfer.cpp
+++ b/js/src/jsinfer.cpp
@@ -2522,17 +2522,17 @@ struct types::ArrayTableKey
 
     ArrayTableKey()
         : type(Type::UndefinedType()), proto(NULL)
     {}
 
     typedef ArrayTableKey Lookup;
 
     static inline uint32_t hash(const ArrayTableKey &v) {
-        return (uint32_t) (v.type.raw() ^ ((uint32_t)(size_t)v.proto >> 2));
+        return HashGeneric(v.type.raw(), v.proto);
     }
 
     static inline bool match(const ArrayTableKey &v1, const ArrayTableKey &v2) {
         return v1.type == v2.type && v1.proto == v2.proto;
     }
 };
 
 void
@@ -2610,19 +2610,20 @@ struct types::ObjectTableKey
     jsid *ids;
     uint32_t nslots;
     uint32_t nfixed;
     JSObject *proto;
 
     typedef JSObject * Lookup;
 
     static inline uint32_t hash(JSObject *obj) {
-        return (uint32_t) (JSID_BITS(obj->lastProperty()->propid().get()) ^
-                         obj->slotSpan() ^ obj->numFixedSlots() ^
-                         ((uint32_t)(size_t)obj->getProto() >> 2));
+        return HashGeneric(JSID_BITS(obj->lastProperty()->propid().get()),
+                           obj->slotSpan(),
+                           obj->numFixedSlots(),
+                           obj->getProto());
     }
 
     static inline bool match(const ObjectTableKey &v, JSObject *obj) {
         if (obj->slotSpan() != v.nslots ||
             obj->numFixedSlots() != v.nfixed ||
             obj->getProto() != v.proto) {
             return false;
         }
--- a/js/src/jsinferinlines.h
+++ b/js/src/jsinferinlines.h
@@ -41,16 +41,17 @@
 
 #include "jsarray.h"
 #include "jsanalyze.h"
 #include "jscompartment.h"
 #include "jsgcmark.h"
 #include "jsinfer.h"
 #include "jsprf.h"
 #include "vm/GlobalObject.h"
+#include "mozilla/HashFunctions.h"
 
 #include "vm/Stack-inl.h"
 
 #ifndef jsinferinlines_h___
 #define jsinferinlines_h___
 
 /////////////////////////////////////////////////////////////////////
 // Types
@@ -530,17 +531,18 @@ struct AllocationSiteKey {
 
     static const uint32_t OFFSET_LIMIT = (1 << 23);
 
     AllocationSiteKey() { PodZero(this); }
 
     typedef AllocationSiteKey Lookup;
 
     static inline uint32_t hash(AllocationSiteKey key) {
-        return uint32_t(size_t(key.script->code + key.offset)) ^ key.kind;
+        return mozilla::HashGeneric(uint32_t(size_t(key.script->code + key.offset)),
+                                    key.kind);
     }
 
     static inline bool match(const AllocationSiteKey &a, const AllocationSiteKey &b) {
         return a.script == b.script && a.offset == b.offset && a.kind == b.kind;
     }
 };
 
 /* static */ inline TypeObject *
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -40,16 +40,17 @@
 
 /*
  * JS object implementation.
  */
 #include <stdlib.h>
 #include <string.h>
 
 #include "mozilla/Util.h"
+#include "mozilla/HashFunctions.h"
 
 #include "jstypes.h"
 #include "jsutil.h"
 #include "jshash.h"
 #include "jsdhash.h"
 #include "jsprf.h"
 #include "jsapi.h"
 #include "jsarray.h"
@@ -752,19 +753,18 @@ EvalCacheHash(JSContext *cx, JSLinearStr
 {
     const jschar *s = str->chars();
     size_t n = str->length();
 
     if (n > 100)
         n = 100;
     uint32_t h;
     for (h = 0; n; s++, n--)
-        h = JS_ROTATE_LEFT32(h, 4) ^ *s;
-
-    h *= JS_GOLDEN_RATIO;
+        h = mozilla::AddToHash(h, *s);
+
     h >>= 32 - JS_EVAL_CACHE_SHIFT;
     return &cx->compartment->evalCache[h];
 }
 
 static JS_ALWAYS_INLINE JSScript *
 EvalCacheLookup(JSContext *cx, JSLinearString *str, StackFrame *caller, unsigned staticLevel,
                 JSPrincipals *principals, JSObject &scopeobj, JSScript **bucket)
 {
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -1552,23 +1552,22 @@ class AutoPropertyDescriptorRooter : pri
     }
 
     friend void AutoGCRooter::trace(JSTracer *trc);
 };
 
 inline bool
 NewObjectCache::lookup(Class *clasp, gc::Cell *key, gc::AllocKind kind, EntryIndex *pentry)
 {
-    uintptr_t hash = (uintptr_t(clasp) ^ uintptr_t(key)) + kind;
+    uintptr_t hash = mozilla::HashGeneric(clasp, key, kind);
     *pentry = hash % js::ArrayLength(entries);
 
     Entry *entry = &entries[*pentry];
 
-    /* N.B. Lookups with the same clasp/key but different kinds map to different entries. */
-    return (entry->clasp == clasp && entry->key == key);
+    return (entry->clasp == clasp && entry->key == key && entry->kind == kind);
 }
 
 inline bool
 NewObjectCache::lookupProto(Class *clasp, JSObject *proto, gc::AllocKind kind, EntryIndex *pentry)
 {
     JS_ASSERT(!proto->isGlobal());
     return lookup(clasp, proto, kind, pentry);
 }
--- a/js/src/jspropertycache.h
+++ b/js/src/jspropertycache.h
@@ -39,16 +39,17 @@
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef jspropertycache_h___
 #define jspropertycache_h___
 
 #include "jsapi.h"
 #include "jsprvtd.h"
 #include "jstypes.h"
+#include "mozilla/HashFunctions.h"
 
 #include "vm/String.h"
 
 namespace js {
 
 /*
  * Property cache with structurally typed capabilities for invalidation, for
  * polymorphic callsite method/get/set speedups.  For details, see
@@ -172,17 +173,17 @@ class PropertyCache
     PropertyCache() {
         PodZero(this);
     }
     
   private:
     static inline uintptr_t
     hash(jsbytecode *pc, const Shape *kshape)
     {
-        return (((uintptr_t(pc) >> SIZE_LOG2) ^ uintptr_t(pc) ^ ((uintptr_t)kshape >> 3)) & MASK);
+        return mozilla::HashGeneric(pc, kshape) & MASK;
     }
 
     static inline bool matchShape(JSContext *cx, JSObject *obj, uint32_t shape);
 
     PropertyName *
     fullTest(JSContext *cx, jsbytecode *pc, JSObject **objp,
              JSObject **pobjp, PropertyCacheEntry *entry);
 
--- a/js/src/jsscope.cpp
+++ b/js/src/jsscope.cpp
@@ -1259,22 +1259,19 @@ Shape::setObjectFlag(JSContext *cx, Base
     base.flags |= flag;
 
     return replaceLastProperty(cx, base, proto, last);
 }
 
 /* static */ inline HashNumber
 StackBaseShape::hash(const StackBaseShape *base)
 {
-    JSDHashNumber hash = base->flags;
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ (uintptr_t(base->clasp) >> 3);
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ (uintptr_t(base->parent) >> 3);
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ uintptr_t(base->rawGetter);
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ uintptr_t(base->rawSetter);
-    return hash;
+    JSDHashNumber hash = HashGeneric(base->flags);
+    return AddToHash(hash, base->clasp, base->parent,
+                             base->rawGetter, base->rawSetter);
 }
 
 /* static */ inline bool
 StackBaseShape::match(UnownedBaseShape *key, const StackBaseShape *lookup)
 {
     return key->flags == lookup->flags
         && key->clasp == lookup->clasp
         && key->parent == lookup->parent
@@ -1396,20 +1393,18 @@ Bindings::setParent(JSContext *cx, JSObj
         return false;
     self->lastBinding = newShape;
     return true;
 }
 
 /* static */ inline HashNumber
 InitialShapeEntry::hash(const Lookup &lookup)
 {
-    JSDHashNumber hash = uintptr_t(lookup.clasp) >> 3;
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ (uintptr_t(lookup.proto) >> 3);
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ (uintptr_t(lookup.parent) >> 3);
-    return hash + lookup.nfixed;
+    JSDHashNumber hash = HashGeneric(lookup.clasp, lookup.proto, lookup.parent);
+    return AddToHash(hash, lookup.nfixed);
 }
 
 /* static */ inline bool
 InitialShapeEntry::match(const InitialShapeEntry &key, const Lookup &lookup)
 {
     return lookup.clasp == key.shape->getObjectClass()
         && lookup.proto == key.proto
         && lookup.parent == key.shape->getObjectParent()
--- a/js/src/jsscopeinlines.h
+++ b/js/src/jsscopeinlines.h
@@ -234,25 +234,19 @@ Shape::Shape(UnownedBaseShape *base, uin
 {
     JS_ASSERT(base);
     kids.setNull();
 }
 
 inline JSDHashNumber
 StackShape::hash() const
 {
-    JSDHashNumber hash = uintptr_t(base);
-
-    /* Accumulate from least to most random so the low bits are most random. */
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ (flags & Shape::PUBLIC_FLAGS);
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ attrs;
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ shortid;
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ slot_;
-    hash = JS_ROTATE_LEFT32(hash, 4) ^ JSID_BITS(propid);
-    return hash;
+    return AddToHash(HashGeneric(base),
+                     flags & Shape::PUBLIC_FLAGS, attrs,
+                     shortid, slot_, JSID_BITS(propid));
 }
 
 inline bool
 Shape::matches(const js::Shape *other) const
 {
     return propid_.get() == other->propid_.get() &&
            matchesParamsAfterId(other->base(), other->maybeSlot(), other->attrs,
                                 other->flags, other->shortid_);
--- a/js/src/jswatchpoint.cpp
+++ b/js/src/jswatchpoint.cpp
@@ -36,24 +36,26 @@
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "jswatchpoint.h"
 #include "jsatom.h"
 #include "jsgcmark.h"
 #include "jsobjinlines.h"
+#include "mozilla/HashFunctions.h"
 
 using namespace js;
 using namespace js::gc;
 
 inline HashNumber
 DefaultHasher<WatchKey>::hash(const Lookup &key)
 {
-    return DefaultHasher<JSObject *>::hash(key.object.get()) ^ HashId(key.id.get());
+    return mozilla::HashGeneric(DefaultHasher<JSObject *>::hash(key.object.get()),
+                                HashId(key.id.get()));
 }
 
 class AutoEntryHolder {
     typedef WatchpointMap::Map Map;
     Map &map;
     Map::Ptr p;
     uint32_t gen;
     WatchKey key;
--- a/js/xpconnect/src/XPCMaps.cpp
+++ b/js/xpconnect/src/XPCMaps.cpp
@@ -38,16 +38,19 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 /* Private maps (hashtables). */
 
 #include "xpcprivate.h"
 
 #include "jshash.h"
+#include "mozilla/HashFunctions.h"
+
+using namespace mozilla;
 
 /***************************************************************************/
 // static shared...
 
 // Note this is returning the bit pattern of the first part of the nsID, not
 // the pointer to the nsID.
 
 static JSDHashNumber
@@ -83,33 +86,31 @@ HashNativeKey(JSDHashTable *table, const
     } else {
         Set      = (XPCNativeSet*) Key;
         Addition = nsnull;
         Position = 0;
     }
 
     if (!Set) {
         NS_ASSERTION(Addition, "bad key");
-        // This would be an XOR like below.
-        // But "0 ^ x == x". So it does not matter.
-        h = (JSHashNumber) NS_PTR_TO_INT32(Addition) >> 2;
+        h = AddToHash(h, Addition);
     } else {
         XPCNativeInterface** Current = Set->GetInterfaceArray();
         PRUint16 count = Set->GetInterfaceCount();
         if (Addition) {
             count++;
             for (PRUint16 i = 0; i < count; i++) {
                 if (i == Position)
-                    h ^= (JSHashNumber) NS_PTR_TO_INT32(Addition) >> 2;
+                    h = AddToHash(h, Addition);
                 else
-                    h ^= (JSHashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2;
+                    h = AddToHash(h, *(Current++));
             }
         } else {
             for (PRUint16 i = 0; i < count; i++)
-                h ^= (JSHashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2;
+                h = AddToHash(h, *(Current++));
         }
     }
 
     return h;
 }
 
 /***************************************************************************/
 // implement JSObject2WrappedJSMap...
@@ -548,20 +549,18 @@ XPCNativeScriptableSharedMap::Entry::Has
 
     XPCNativeScriptableShared* obj =
         (XPCNativeScriptableShared*) key;
 
     // hash together the flags and the classname string, ignore the interfaces
     // bitmap since it's very rare that it's different when flags and classname
     // are the same.
 
-    h = (JSDHashNumber) obj->GetFlags();
-    for (s = (const unsigned char*) obj->GetJSClass()->name; *s != '\0'; s++)
-        h = JS_ROTATE_LEFT32(h, 4) ^ *s;
-    return h;
+    h = HashGeneric(obj->GetFlags());
+    return AddToHash(h, HashString(obj->GetJSClass()->name));
 }
 
 JSBool
 XPCNativeScriptableSharedMap::Entry::Match(JSDHashTable *table,
                                            const JSDHashEntryHdr *entry,
                                            const void *key)
 {
     XPCNativeScriptableShared* obj1 =