Changeset 183624 in webkit

Timestamp:

Apr 30, 2015 1:37:51 AM (9 years ago)

Author:

Yusuke Suzuki

Message:

Use the default hash value for Symbolized StringImpl
​https://bugs.webkit.org/show_bug.cgi?id=144347

Reviewed by Darin Adler.

Source/JavaScriptCore:

Before this patch, symbolized StringImpl* has a special hash value
to avoid the hash collision with the other normal StringImpl*.
I guess that it is introduced when private symbols are introduced.
However, it prevents using symbolized StringImpl* in the other place
For example, using it as WTFString cause a problem because of its special hash value.

When only using private symbols, they are not exposed to the outside of JSC,
so we can handle it carefully. But now, it's extended to symbols.
So I think storing a special hash value in StringImpl* causes an error.

To avoid this, I propose using the usual hash value in symbolized StringImpl*.
And to provide significantly different hash value when using it as symbol,
store the additional hash value in symbolized StringImpl*. It is used when
the hash value is required by IdentifierRepHash.

• runtime/Identifier.h:

(JSC::IdentifierRepHash::hash):

• runtime/Lookup.h:

(JSC::HashTable::entry):

• runtime/PropertyMapHashTable.h:

(JSC::PropertyTable::find):
(JSC::PropertyTable::get):

• runtime/Structure.cpp:

(JSC::PropertyTable::checkConsistency):

Source/WTF:

Use a default hash value calculation for symbolized StringImpl.

• wtf/text/StringImpl.cpp:

(WTF::StringImpl::createSymbol):

• wtf/text/StringImpl.h:

(WTF::StringImpl::StringImpl):
(WTF::StringImpl::symbolAwareHash):
(WTF::StringImpl::existingSymbolAwareHash):
(WTF::StringImpl::hashForSymbol):

• wtf/text/StringStatics.cpp:

(WTF::StringImpl::nextHashForSymbol):
(WTF::StringImpl::hashAndFlagsForSymbol): Deleted.

Location:

trunk/Source

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/runtime/Identifier.h (modified) (1 diff)
• JavaScriptCore/runtime/Lookup.h (modified) (1 diff)
• JavaScriptCore/runtime/PropertyMapHashTable.h (modified) (5 diffs)
• JavaScriptCore/runtime/Structure.cpp (modified) (2 diffs)
• WTF/ChangeLog (modified) (1 diff)
• WTF/wtf/text/StringImpl.cpp (modified) (1 diff)
• WTF/wtf/text/StringImpl.h (modified) (7 diffs)
• WTF/wtf/text/StringStatics.cpp (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2015-04-30  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        Use the default hash value for Symbolized StringImpl
+        https://bugs.webkit.org/show_bug.cgi?id=144347
+
+        Reviewed by Darin Adler.
+
+        Before this patch, symbolized StringImpl* has a special hash value
+        to avoid the hash collision with the other normal StringImpl*.
+        I guess that it is introduced when private symbols are introduced.
+        However, it prevents using symbolized StringImpl* in the other place
+        For example, using it as WTFString cause a problem because of its special hash value.
+
+        When only using private symbols, they are not exposed to the outside of JSC,
+        so we can handle it carefully. But now, it's extended to symbols.
+        So I think storing a special hash value in StringImpl* causes an error.
+
+        To avoid this, I propose using the usual hash value in symbolized StringImpl*.
+        And to provide significantly different hash value when using it as symbol,
+        store the additional hash value in symbolized StringImpl*. It is used when
+        the hash value is required by IdentifierRepHash.
+
+        * runtime/Identifier.h:
+        (JSC::IdentifierRepHash::hash):
+        * runtime/Lookup.h:
+        (JSC::HashTable::entry):
+        * runtime/PropertyMapHashTable.h:
+        (JSC::PropertyTable::find):
+        (JSC::PropertyTable::get):
+        * runtime/Structure.cpp:
+        (JSC::PropertyTable::checkConsistency):
+
 2015-04-29  Benjamin Poulain  <bpoulain@apple.com>
 

trunk/Source/JavaScriptCore/runtime/Identifier.h

@@ -281 +281 @@
 
 struct IdentifierRepHash : PtrHash<RefPtr<StringImpl>> {
-    static unsigned hash(const RefPtr<StringImpl>& key) { return key->existingHash(); }
-    static unsigned hash(StringImpl* key) { return key->existingHash(); }
+    static unsigned hash(const RefPtr<StringImpl>& key) { return key->existingSymbolAwareHash(); }
+    static unsigned hash(StringImpl* key) { return key->existingSymbolAwareHash(); }
 };
 

trunk/Source/JavaScriptCore/runtime/Lookup.h

@@ -104 +104 @@
         ASSERT(keys);
 
-        int indexEntry = impl->existingHash() & indexMask;
+        int indexEntry = IdentifierRepHash::hash(impl) & indexMask;
         int valueIndex = index[indexEntry].value;
         if (valueIndex == -1)

trunk/Source/JavaScriptCore/runtime/PropertyMapHashTable.h

@@ -272 +272 @@
     ASSERT(key);
     ASSERT(key->isAtomic() || key->isSymbol());
-    unsigned hash = key->existingHash();
+    unsigned hash = IdentifierRepHash::hash(key);
     unsigned step = 0;
 
@@ -287 +287 @@
 
         if (!step)
-            step = WTF::doubleHash(key->existingHash()) | 1;
+            step = WTF::doubleHash(IdentifierRepHash::hash(key)) | 1;
 
 #if DUMP_PROPERTYMAP_STATS
@@ -295 +295 @@
 #if DUMP_PROPERTYMAP_COLLISIONS
         dataLog("PropertyTable collision for ", key, " (", hash, ") with step ", step, "\n");
-        dataLog("Collided with ", table()[entryIndex - 1].key, "(", table()[entryIndex - 1].key->existingHash(), ")\n");
+        dataLog("Collided with ", table()[entryIndex - 1].key, "(", IdentifierRepHash::hash(table()[entryIndex - 1].key), ")\n");
 #endif
 
@@ -310 +310 @@
         return nullptr;
 
-    unsigned hash = key->existingHash();
+    unsigned hash = IdentifierRepHash::hash(key);
     unsigned step = 0;
 
@@ -329 +329 @@
 
         if (!step)
-            step = WTF::doubleHash(key->existingHash()) | 1;
+            step = WTF::doubleHash(IdentifierRepHash::hash(key)) | 1;
         hash += step;
     }

trunk/Source/JavaScriptCore/runtime/Structure.cpp

@@ -1163 +1163 @@
             continue;
         ++nonEmptyEntryCount;
-        unsigned i = rep->existingHash();
+        unsigned i = IdentifierRepHash::hash(rep);
         unsigned k = 0;
         unsigned entryIndex;
@@ -1172 +1172 @@
                 break;
             if (k == 0)
-                k = 1 | doubleHash(rep->existingHash());
+                k = 1 | doubleHash(IdentifierRepHash::hash(rep));
             i += k;
         }

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2015-04-30  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        Use the default hash value for Symbolized StringImpl
+        https://bugs.webkit.org/show_bug.cgi?id=144347
+
+        Reviewed by Darin Adler.
+
+        Use a default hash value calculation for symbolized StringImpl.
+
+        * wtf/text/StringImpl.cpp:
+        (WTF::StringImpl::createSymbol):
+        * wtf/text/StringImpl.h:
+        (WTF::StringImpl::StringImpl):
+        (WTF::StringImpl::symbolAwareHash):
+        (WTF::StringImpl::existingSymbolAwareHash):
+        (WTF::StringImpl::hashForSymbol):
+        * wtf/text/StringStatics.cpp:
+        (WTF::StringImpl::nextHashForSymbol):
+        (WTF::StringImpl::hashAndFlagsForSymbol): Deleted.
+
 2015-04-29  Alexey Proskuryakov  <ap@apple.com>
 

trunk/Source/WTF/wtf/text/StringImpl.cpp

@@ -299 +299 @@
     // 2. the pointer to the owner string
     // 3. the pointer to the symbol registry
-    StringImpl* stringImpl = static_cast<StringImpl*>(fastMalloc(allocationSize<StringImpl*>(2)));
+    // 4. the placeholder for symbol aware hash value (allocated size is pointer size, but only 4 bytes are used)
+    StringImpl* stringImpl = static_cast<StringImpl*>(fastMalloc(allocationSize<StringImpl*>(3)));
     if (rep->is8Bit())
         return adoptRef(*new (NotNull, stringImpl) StringImpl(CreateSymbol, rep->m_data8, rep->length(), ownerRep));

trunk/Source/WTF/wtf/text/StringImpl.h

@@ -300 +300 @@
         , m_length(length)
         , m_data8(characters)
-        , m_hashAndFlags(hashAndFlagsForSymbol(s_hashFlag8BitBuffer | StringSymbol | BufferSubstring))
+        , m_hashAndFlags(s_hashFlag8BitBuffer | StringSymbol | BufferSubstring)
     {
         ASSERT(is8Bit());
@@ -308 +308 @@
         substringBuffer() = base.leakRef();
         symbolRegistry() = nullptr;
+        hashForSymbol() = nextHashForSymbol();
 
         STRING_STATS_ADD_8BIT_STRING2(m_length, true);
@@ -317 +318 @@
         , m_length(length)
         , m_data16(characters)
-        , m_hashAndFlags(hashAndFlagsForSymbol(StringSymbol | BufferSubstring))
+        , m_hashAndFlags(StringSymbol | BufferSubstring)
     {
         ASSERT(!is8Bit());
@@ -325 +326 @@
         substringBuffer() = base.leakRef();
         symbolRegistry() = nullptr;
+        hashForSymbol() = nextHashForSymbol();
 
         STRING_STATS_ADD_16BIT_STRING2(m_length, true);
@@ -561 +563 @@
         return hashSlowCase();
     }
-    
+
+    unsigned symbolAwareHash() const
+    {
+        if (isSymbol())
+            return hashForSymbol();
+        return hash();
+    }
+
+    unsigned existingSymbolAwareHash() const
+    {
+        if (isSymbol())
+            return hashForSymbol();
+        return existingHash();
+    }
+
     bool isStatic() const { return m_refCount & s_refCountFlagIsStaticString; }
 
@@ -781 +797 @@
     }
 
+    const unsigned& hashForSymbol() const
+    {
+        return const_cast<StringImpl*>(this)->hashForSymbol();
+    }
+
+    unsigned& hashForSymbol()
+    {
+        ASSERT(isSymbol());
+        return *reinterpret_cast<unsigned*>((tailPointer<SymbolRegistry*>() + 2));
+    }
+
 private:
     bool requiresCopy() const
@@ -847 +874 @@
     template <typename CharType> static Ref<StringImpl> createInternal(const CharType*, unsigned);
     WTF_EXPORT_PRIVATE NEVER_INLINE unsigned hashSlowCase() const;
-    WTF_EXPORT_PRIVATE static unsigned hashAndFlagsForSymbol(unsigned flags);
+    WTF_EXPORT_PRIVATE static unsigned nextHashForSymbol();
 
     // The bottom bit in the ref count indicates a static (immortal) string.

trunk/Source/WTF/wtf/text/StringStatics.cpp

@@ -48 +48 @@
 }
 
-// Set the hash early, so that all symbol StringImpls have a hash,
-// and don't use the normal hashing algorithm - the unique nature of these
-// keys means that we don't need them to match any other string (in fact,
-// that's exactly the oposite of what we want!), and the normal hash would
-// lead to lots of conflicts.
-unsigned StringImpl::hashAndFlagsForSymbol(unsigned flags)
+// In addition to the normal hash value, store specialized hash value for
+// symbolized StringImpl*. And don't use the normal hash value for symbolized
+// StringImpl* when they are treated as Identifiers. Unique nature of these
+// symbolized StringImpl* keys means that we don't need them to match any other
+// string (in fact, that's exactly the oposite of what we want!), and the
+// normal hash would lead to lots of conflicts.
+unsigned StringImpl::nextHashForSymbol()
 {
-    static unsigned s_nextHashAndFlagsForSymbol = 0;
-    s_nextHashAndFlagsForSymbol += 1 << s_flagCount;
-    s_nextHashAndFlagsForSymbol |= 1 << 31;
-    unsigned flagsForSymbol = ((flags & s_flagMask) & (~s_hashMaskStringKind)) | StringSymbol;
-    return s_nextHashAndFlagsForSymbol | flagsForSymbol;
+    static unsigned s_nextHashForSymbol = 0;
+    s_nextHashForSymbol += 1 << s_flagCount;
+    s_nextHashForSymbol |= 1 << 31;
+    return s_nextHashForSymbol;
 }