Separated string lifetime bits from character buffer state bits
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 23 Oct 2011 07:21:19 +0000 (07:21 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 23 Oct 2011 07:21:19 +0000 (07:21 +0000)
https://bugs.webkit.org/show_bug.cgi?id=70673

Source/JavaScriptCore:

Reviewed by Anders Carlsson.

Moved the static/immortal bit into the bottom bit of the refcount, and
moved all other bits into the high bits of the hash code.

This is the first step toward a new Characters/PassString class, and it
makes ref/deref slightly more efficient.

* create_hash_table:
* wtf/StringHasher.h:
(WTF::StringHasher::hash): Tweaked the string hashing function to leave
the top bits clear, so they can be used as flags.

Fixed some small differences between the PERL copy of this function and
the C++ copy of this function, which could have in theory caused subtle
crashes.

* wtf/text/StringImpl.cpp:
(WTF::StringImpl::sharedBuffer):
(WTF::StringImpl::createWithTerminatingNullCharacter):
* wtf/text/StringImpl.h:
(WTF::StringImpl::StringImpl):
(WTF::StringImpl::cost): Renamed s_refCountFlagShouldReportedCost to
s_didReportExtraCost, since the original name was both self-contradictory
and used as a double-negative.

(WTF::StringImpl::isIdentifier):
(WTF::StringImpl::setIsIdentifier):
(WTF::StringImpl::hasTerminatingNullCharacter):
(WTF::StringImpl::isAtomic):
(WTF::StringImpl::setIsAtomic):
(WTF::StringImpl::setHash):
(WTF::StringImpl::rawHash):
(WTF::StringImpl::hasHash):
(WTF::StringImpl::existingHash):
(WTF::StringImpl::hash):
(WTF::StringImpl::hasOneRef):
(WTF::StringImpl::ref):
(WTF::StringImpl::deref):
(WTF::StringImpl::bufferOwnership):
(WTF::StringImpl::isStatic): Moved the static/immortal bit into the bottom
bit of the refcount. Now, all lifetime information lives in the refcount
field. Moved the other bits into the hash code field.

Source/WebCore:

Reviewed by Anders Carlsson.

* bindings/scripts/CodeGeneratorJS.pm:
(GenerateHashValue): Updated for string hashing changes in JavaScriptCore.

LayoutTests:

Reviewed by Anders Carlsson.

These tests depended on non-deterministic effects of hash order, so I
had to update them:

* fast/dom/prototype-inheritance-2-expected.txt: Updated for slightly
different order of discovering properties.

* fast/js/delete-syntax-expected.txt:
* fast/js/script-tests/delete-syntax.js: Updated not to depend on iteration
order, since that's not what this test is about.

* http/tests/inspector/inspector-test.js: Updated not to depend on
global function iteration order. This test setup is pretty spaghetti.
I think I avoided making it even more spaghetti.

* inspector/storage-panel-dom-storage-expected.txt: Updated for changed
iteration order.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@98199 268f45cc-cd09-0410-ab3c-d52691b4dbfc

13 files changed:
LayoutTests/ChangeLog
LayoutTests/fast/dom/prototype-inheritance-2-expected.txt
LayoutTests/fast/js/delete-syntax-expected.txt
LayoutTests/fast/js/script-tests/delete-syntax.js
LayoutTests/http/tests/inspector/inspector-test.js
LayoutTests/inspector/storage-panel-dom-storage-expected.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/create_hash_table
Source/JavaScriptCore/wtf/StringHasher.h
Source/JavaScriptCore/wtf/text/StringImpl.cpp
Source/JavaScriptCore/wtf/text/StringImpl.h
Source/WebCore/ChangeLog
Source/WebCore/bindings/scripts/CodeGeneratorJS.pm

index 0819a4d..227dc2e 100644 (file)
@@ -1,3 +1,27 @@
+2011-10-21  Geoffrey Garen  <ggaren@apple.com>
+
+        Separated string lifetime bits from character buffer state bits
+        https://bugs.webkit.org/show_bug.cgi?id=70673
+
+        Reviewed by Anders Carlsson.
+        
+        These tests depended on non-deterministic effects of hash order, so I
+        had to update them:
+
+        * fast/dom/prototype-inheritance-2-expected.txt: Updated for slightly
+        different order of discovering properties.
+
+        * fast/js/delete-syntax-expected.txt:
+        * fast/js/script-tests/delete-syntax.js: Updated not to depend on iteration
+        order, since that's not what this test is about.
+
+        * http/tests/inspector/inspector-test.js: Updated not to depend on
+        global function iteration order. This test setup is pretty spaghetti.
+        I think I avoided making it even more spaghetti.
+
+        * inspector/storage-panel-dom-storage-expected.txt: Updated for changed
+        iteration order.
+
 2011-10-22  Benjamin Poulain  <benjamin@webkit.org>
 
         Make relayout-nested-positioned-elements-crash.html more reliable
index 8db2b24..e5e7a0f 100644 (file)
@@ -168,26 +168,26 @@ PASS MediaListConstructor from inner.document.forms.testForm.0.ownerDocument.sty
 PASS MediaListPrototype from inner.document.forms.testForm.0.ownerDocument.styleSheets.0.media.__proto__
 PASS MemoryInfo from inner.document.forms.testForm.0.ownerDocument.defaultView.console.memory
 PASS MemoryInfoPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.console.memory.__proto__
-PASS MimeType from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.0
-PASS MimeTypeArray from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes
-PASS MimeTypeArrayConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.constructor
-PASS MimeTypeArrayPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.__proto__
-PASS MimeTypeConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.0.constructor
-PASS MimeTypePrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.0.__proto__
+PASS MimeType from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes.0
+PASS MimeTypeArray from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes
+PASS MimeTypeArrayConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes.constructor
+PASS MimeTypeArrayPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes.__proto__
+PASS MimeTypeConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes.0.constructor
+PASS MimeTypePrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.mimeTypes.0.__proto__
 PASS NamedNodeMap from inner.document.forms.testForm.0.parentNode.attributes
-PASS Navigator from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation
-PASS NavigatorPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.__proto__
+PASS Navigator from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator
+PASS NavigatorPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.__proto__
 PASS NodeList from inner.document.forms.testForm
 PASS NodeListConstructor from inner.document.forms.testForm.constructor
 PASS NodeListPrototype from inner.document.forms.testForm.__proto__
-PASS NodePrototype from inner.document.forms.testForm.0.attributes.0.__proto__.__proto__
+PASS NodePrototype from inner.document.forms.testForm.0.ownerDocument.__proto__.__proto__.__proto__
 PASS Object from inner.document.location.__proto__.__proto__
-PASS Plugin from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.0.enabledPlugin
-PASS PluginArray from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.plugins
-PASS PluginArrayConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.plugins.constructor
-PASS PluginArrayPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.plugins.__proto__
-PASS PluginConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.plugins.0.constructor
-PASS PluginPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.clientInformation.mimeTypes.0.enabledPlugin.__proto__
+PASS Plugin from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins.5
+PASS PluginArray from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins
+PASS PluginArrayConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins.constructor
+PASS PluginArrayPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins.__proto__
+PASS PluginConstructor from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins.0.constructor
+PASS PluginPrototype from inner.document.forms.testForm.0.ownerDocument.defaultView.navigator.plugins.5.__proto__
 PASS RGBColor from inner.getComputedStyle(inner.document.body).getPropertyCSSValue(fill).rgbColor
 PASS RGBColorConstructor from inner.getComputedStyle(inner.document.body).getPropertyCSSValue(fill).rgbColor.constructor
 PASS RGBColorPrototype from inner.getComputedStyle(inner.document.body).getPropertyCSSValue(fill).rgbColor.__proto__
@@ -213,9 +213,9 @@ PASS StyleSheetPrototype from inner.document.forms.testForm.0.ownerDocument.styl
 PASS Text from inner.document.forms.testForm.0.parentNode.lastElementChild.previousElementSibling.firstChild
 PASS TextConstructor from inner.document.forms.testForm.0.attributes.0.lastChild.constructor
 PASS TextPrototype from inner.document.forms.testForm.0.attributes.0.lastChild.__proto__
-PASS TimeRanges from inner.document.forms.testForm.0.previousElementSibling.played
-PASS TimeRangesConstructor from inner.document.forms.testForm.0.previousElementSibling.played.constructor
-PASS TimeRangesPrototype from inner.document.forms.testForm.0.previousElementSibling.played.__proto__
+PASS TimeRanges from inner.document.forms.testForm.0.previousElementSibling.seekable
+PASS TimeRangesConstructor from inner.document.forms.testForm.0.previousElementSibling.seekable.constructor
+PASS TimeRangesPrototype from inner.document.forms.testForm.0.previousElementSibling.seekable.__proto__
 PASS ValidityState from inner.document.forms.testForm.0.0.validity
 PASS ValidityStatePrototype from inner.document.forms.testForm.0.0.validity.__proto__
 PASS WebKitCSSKeyframeRule from inner.document.getElementById("dummyStyle").sheet.cssRules.6.0
@@ -225,6 +225,8 @@ PASS WebKitCSSKeyframesRule from inner.document.getElementById("dummyStyle").she
 PASS WebKitCSSKeyframesRuleConstructor from inner.document.getElementById("dummyStyle").sheet.cssRules.6.constructor
 PASS WebKitCSSKeyframesRulePrototype from inner.document.getElementById("dummyStyle").sheet.cssRules.6.__proto__
 Never found Audio
+Never found AudioContext
+Never found AudioPannerNode
 Never found Blob
 Never found CDATASection
 Never found CSSRule
@@ -438,6 +440,7 @@ Never found SVGViewElement
 Never found SharedWorker
 Never found StyleSheet
 Never found TextMetrics
+Never found WebKitCSSFilterValue
 Never found WebKitCSSMatrix
 Never found WebKitCSSTransformValue
 Never found WebKitPoint
index bae23c0..42ae10d 100644 (file)
@@ -29,7 +29,7 @@ PASS Math.tan is null
 PASS RegExp.prototype.compile is regExpPrototypeCompile
 PASS RegExp.prototype.exec is undefined
 PASS RegExp.prototype.test is null
-PASS String(Object.getOwnPropertyNames(Object.prototype)) is "constructor,valueOf,__lookupGetter__,toLocaleString,__defineGetter__,hasOwnProperty,propertyIsEnumerable,toString,__lookupSetter__,isPrototypeOf"
+PASS Object.getOwnPropertyNames(Object.prototype).indexOf('__defineSetter__') is -1
 PASS successfullyParsed is true
 
 TEST COMPLETE
index 1f69016..a2a2805 100644 (file)
@@ -70,7 +70,7 @@ shouldBe("RegExp.prototype.test", "null");
 
 // Check that once a property is deleted its name is removed from the property name array.
 delete Object.prototype.__defineSetter__;
-shouldBe("String(Object.getOwnPropertyNames(Object.prototype))", '"constructor,valueOf,__lookupGetter__,toLocaleString,__defineGetter__,hasOwnProperty,propertyIsEnumerable,toString,__lookupSetter__,isPrototypeOf"');
+shouldBe("Object.getOwnPropertyNames(Object.prototype).indexOf('__defineSetter__')", "-1");
 
 var successfullyParsed = true;
 
index e6d07e3..5cdca25 100644 (file)
@@ -438,9 +438,9 @@ function runTest(enableWatchDogWhileDebugging)
         }
     }
 
-    var initializationFunctions = [];
+    var initializationFunctions = [ String(initialize_InspectorTest) ];
     for (var name in window) {
-        if (name.indexOf("initialize_") === 0 && typeof window[name] === "function")
+        if (name.indexOf("initialize_") === 0 && typeof window[name] === "function" && name !== "initialize_InspectorTest")
             initializationFunctions.push(window[name].toString());
     }
     var parameters = ["[" + initializationFunctions + "]", test, completeTestCallId];
index a6d825b..de96cbc 100644 (file)
@@ -4,8 +4,8 @@ Populated local and session storage
 Did show: Local storage
 Did show: Session storage
 Local storage content: 
-KeyValuea0=value0, a6=value6, a8=value8, a4=value4, a2=value2, a1=value1, resource-history{}a9=value9, a3=value3, a7=value7, a5=value5
+KeyValueresource-history{}a4=value4, a0=value0, a2=value2, a7=value7, a9=value9, a5=value5, a8=value8, a1=value1, a3=value3, a6=value6
 Session storage content: 
-KeyValueb5=value15, b4=value14, b3=value13, b6=value16, b7=value17, b0=value10, b9=value19, b8=value18, b2=value12, b1=value11
+KeyValueb4=value14, b3=value13, b0=value10, b9=value19, b5=value15, b6=value16, b7=value17, b8=value18, b1=value11, b2=value12
 DONE
 
index bf60430..bfde0b9 100644 (file)
@@ -1,3 +1,52 @@
+2011-10-21  Geoffrey Garen  <ggaren@apple.com>
+
+        Separated string lifetime bits from character buffer state bits
+        https://bugs.webkit.org/show_bug.cgi?id=70673
+
+        Reviewed by Anders Carlsson.
+        
+        Moved the static/immortal bit into the bottom bit of the refcount, and
+        moved all other bits into the high bits of the hash code.
+        
+        This is the first step toward a new Characters/PassString class, and it
+        makes ref/deref slightly more efficient.
+
+        * create_hash_table:
+        * wtf/StringHasher.h:
+        (WTF::StringHasher::hash): Tweaked the string hashing function to leave
+        the top bits clear, so they can be used as flags.
+        
+        Fixed some small differences between the PERL copy of this function and
+        the C++ copy of this function, which could have in theory caused subtle
+        crashes.
+
+        * wtf/text/StringImpl.cpp:
+        (WTF::StringImpl::sharedBuffer):
+        (WTF::StringImpl::createWithTerminatingNullCharacter):
+        * wtf/text/StringImpl.h:
+        (WTF::StringImpl::StringImpl):
+        (WTF::StringImpl::cost): Renamed s_refCountFlagShouldReportedCost to
+        s_didReportExtraCost, since the original name was both self-contradictory
+        and used as a double-negative.
+
+        (WTF::StringImpl::isIdentifier):
+        (WTF::StringImpl::setIsIdentifier):
+        (WTF::StringImpl::hasTerminatingNullCharacter):
+        (WTF::StringImpl::isAtomic):
+        (WTF::StringImpl::setIsAtomic):
+        (WTF::StringImpl::setHash):
+        (WTF::StringImpl::rawHash):
+        (WTF::StringImpl::hasHash):
+        (WTF::StringImpl::existingHash):
+        (WTF::StringImpl::hash):
+        (WTF::StringImpl::hasOneRef):
+        (WTF::StringImpl::ref):
+        (WTF::StringImpl::deref):
+        (WTF::StringImpl::bufferOwnership):
+        (WTF::StringImpl::isStatic): Moved the static/immortal bit into the bottom
+        bit of the refcount. Now, all lifetime information lives in the refcount
+        field. Moved the other bits into the hash code field.
+
 2011-10-21  Filip Pizlo  <fpizlo@apple.com>
 
         DFG inlining sometimes fails to reset constant references
index dc5047e..4afbbe4 100755 (executable)
@@ -179,7 +179,6 @@ sub calcCompactHashSize()
 
 # Paul Hsieh's SuperFastHash
 # http://www.azillionmonkeys.com/qed/hash.html
-# Ported from UString..
 sub hashValue($) {
   my @chars = split(/ */, $_[0]);
 
@@ -207,7 +206,7 @@ sub hashValue($) {
   }
 
   # Handle end case
-  if ($rem !=0) {
+  if ($rem != 0) {
     $hash += ord($chars[$s]);
     $hash ^= (leftShift($hash, 11)% $EXP2_32);
     $hash += $hash >> 17;
@@ -221,11 +220,15 @@ sub hashValue($) {
   $hash += ($hash >> 15);
   $hash = $hash% $EXP2_32;
   $hash ^= (leftShift($hash, 10)% $EXP2_32);
-  
-  # this avoids ever returning a hash code of 0, since that is used to
-  # signal "hash not computed yet", using a value that is likely to be
-  # effectively the same as 0 when the low bits are masked
-  $hash = 0x80000000  if ($hash == 0);
+
+  # Save 6 bits for StringImpl to use as flags.
+  $hash = ($hash >> 6);
+
+  # This avoids ever returning a hash code of 0, since that is used to
+  # signal "hash not computed yet". Setting the high bit maintains
+  # reasonable fidelity to a hash code of 0 because it is likely to yield
+  # exactly 0 when hash lookup masks out the high bits.
+  $hash = (0x80000000 >> 6) if ($hash == 0);
 
   return $hash;
 }
index 5a2c36c..5d41b99 100644 (file)
@@ -31,8 +31,13 @@ static const unsigned stringHashingStartValue = 0x9e3779b9U;
 // Paul Hsieh's SuperFastHash
 // http://www.azillionmonkeys.com/qed/hash.html
 // char* data is interpreted as latin-encoded (zero extended to 16 bits).
+
+// NOTE: This class must stay in sync with the create_hash_table script in
+// JavaScriptCore and the CodeGeneratorJS.pm script in WebCore.
 class StringHasher {
 public:
+    static const unsigned flagCount = 6; // Save 6 bits for StringImpl to use as flags.
+
     inline StringHasher()
         : m_hash(stringHashingStartValue)
         , m_hasPendingCharacter(false)
@@ -76,14 +81,16 @@ public:
         result += result >> 15;
         result ^= result << 10;
 
-        // First bit is used in UStringImpl for m_isIdentifier.
-        result &= 0x7fffffff;
+        // Reserving the high bits for flags perserves most of the hash's value,
+        // since hash lookup typically masks out the high bits anyway.
+        result >>= flagCount;
 
         // This avoids ever returning a hash code of 0, since that is used to
-        // signal "hash not computed yet", using a value that is likely to be
-        // effectively the same as 0 when the low bits are masked.
+        // signal "hash not computed yet". Setting the high bit maintains
+        // reasonable fidelity to a hash code of 0 because it is likely to yield
+        // exactly 0 when hash lookup masks out the high bits.
         if (!result)
-            return 0x40000000;
+            result = 0x80000000 >> flagCount;
 
         return result;
     }
index aab3525..440e954 100644 (file)
@@ -168,7 +168,7 @@ SharedUChar* StringImpl::sharedBuffer()
     if (ownership == BufferOwned) {
         ASSERT(!m_sharedBuffer);
         m_sharedBuffer = SharedUChar::create(new SharableUChar(m_data)).leakRef();
-        m_refCountAndFlags = (m_refCountAndFlags & ~s_refCountMaskBufferOwnership) | BufferShared;
+        m_hashAndFlags = (m_hashAndFlags & ~s_hashMaskBufferOwnership) | BufferShared;
     }
 
     ASSERT(bufferOwnership() == BufferShared);
@@ -1156,8 +1156,7 @@ PassRefPtr<StringImpl> StringImpl::createWithTerminatingNullCharacter(const Stri
     memcpy(data, string.m_data, length * sizeof(UChar));
     data[length] = 0;
     terminatedString->m_length--;
-    terminatedString->m_hash = string.m_hash;
-    terminatedString->m_refCountAndFlags |= s_refCountFlagHasTerminatingNullCharacter;
+    terminatedString->m_hashAndFlags = (string.m_hashAndFlags & ~s_flagMask) | s_hashFlagHasTerminatingNullCharacter;
     return terminatedString.release();
 }
 
index 05f39ce..f1553bd 100644 (file)
@@ -83,13 +83,13 @@ private:
     // Used to construct static strings, which have an special refCount that can never hit zero.
     // This means that the static string will never be destroyed, which is important because
     // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
-    enum StaticStringConstructType { ConstructStaticString };
-    StringImpl(const UChar* characters, unsigned length, StaticStringConstructType)
-        : m_refCountAndFlags(s_refCountFlagStatic | s_refCountFlagIsIdentifier | BufferOwned)
+    enum ConstructStaticStringTag { ConstructStaticString };
+    StringImpl(const UChar* characters, unsigned length, ConstructStaticStringTag)
+        : m_refCount(s_refCountFlagIsStaticString)
         , m_length(length)
         , m_data(characters)
         , m_buffer(0)
-        , m_hash(0)
+        , m_hashAndFlags(s_hashFlagIsIdentifier | BufferOwned)
     {
         // Ensure that the hash is computed so that AtomicStringHash can call existingHash()
         // with impunity. The empty string is special because it is never entered into
@@ -99,11 +99,11 @@ private:
 
     // Create a normal string with internal storage (BufferInternal)
     StringImpl(unsigned length)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | BufferInternal)
+        : m_refCount(s_refCountIncrement)
         , m_length(length)
         , m_data(reinterpret_cast<const UChar*>(this + 1))
         , m_buffer(0)
-        , m_hash(0)
+        , m_hashAndFlags(BufferInternal)
     {
         ASSERT(m_data);
         ASSERT(m_length);
@@ -111,11 +111,11 @@ private:
 
     // Create a StringImpl adopting ownership of the provided buffer (BufferOwned)
     StringImpl(const UChar* characters, unsigned length)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | BufferOwned)
+        : m_refCount(s_refCountIncrement)
         , m_length(length)
         , m_data(characters)
         , m_buffer(0)
-        , m_hash(0)
+        , m_hashAndFlags(BufferOwned)
     {
         ASSERT(m_data);
         ASSERT(m_length);
@@ -123,11 +123,11 @@ private:
 
     // Used to create new strings that are a substring of an existing StringImpl (BufferSubstring)
     StringImpl(const UChar* characters, unsigned length, PassRefPtr<StringImpl> base)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | BufferSubstring)
+        : m_refCount(s_refCountIncrement)
         , m_length(length)
         , m_data(characters)
         , m_substringBuffer(base.leakRef())
-        , m_hash(0)
+        , m_hashAndFlags(BufferSubstring)
     {
         ASSERT(m_data);
         ASSERT(m_length);
@@ -136,25 +136,16 @@ private:
 
     // Used to construct new strings sharing an existing SharedUChar (BufferShared)
     StringImpl(const UChar* characters, unsigned length, PassRefPtr<SharedUChar> sharedBuffer)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | BufferShared)
+        : m_refCount(s_refCountIncrement)
         , m_length(length)
         , m_data(characters)
         , m_sharedBuffer(sharedBuffer.leakRef())
-        , m_hash(0)
+        , m_hashAndFlags(BufferShared)
     {
         ASSERT(m_data);
         ASSERT(m_length);
     }
 
-    // For use only by AtomicString's XXXTranslator helpers.
-    void setHash(unsigned hash)
-    {
-        ASSERT(!isStatic());
-        ASSERT(!m_hash);
-        ASSERT(hash == StringHasher::computeHash(m_data, m_length));
-        m_hash = hash;
-    }
-
 public:
     ~StringImpl();
 
@@ -217,7 +208,6 @@ public:
     }
     static PassRefPtr<StringImpl> adopt(StringBuffer&);
 
-    void ref() { m_refCountAndFlags += s_refCountIncrement; }
     unsigned length() const { return m_length; }
     SharedUChar* sharedBuffer();
     const UChar* characters() const { return m_data; }
@@ -228,41 +218,95 @@ public:
         if (bufferOwnership() == BufferSubstring)
             return m_substringBuffer->cost();
 
-        if (m_refCountAndFlags & s_refCountFlagShouldReportedCost) {
-            m_refCountAndFlags &= ~s_refCountFlagShouldReportedCost;
-            return m_length;
-        }
-        return 0;
+        if (m_hashAndFlags & s_hashFlagDidReportCost)
+            return 0;
+
+        m_hashAndFlags |= s_hashFlagDidReportCost;
+        return m_length;
     }
 
-    bool isIdentifier() const { return m_refCountAndFlags & s_refCountFlagIsIdentifier; }
+    bool isIdentifier() const { return m_hashAndFlags & s_hashFlagIsIdentifier; }
     void setIsIdentifier(bool isIdentifier)
     {
         ASSERT(!isStatic());
         if (isIdentifier)
-            m_refCountAndFlags |= s_refCountFlagIsIdentifier;
+            m_hashAndFlags |= s_hashFlagIsIdentifier;
         else
-            m_refCountAndFlags &= ~s_refCountFlagIsIdentifier;
+            m_hashAndFlags &= ~s_hashFlagIsIdentifier;
     }
 
-    bool hasTerminatingNullCharacter() const { return m_refCountAndFlags & s_refCountFlagHasTerminatingNullCharacter; }
+    bool hasTerminatingNullCharacter() const { return m_hashAndFlags & s_hashFlagHasTerminatingNullCharacter; }
 
-    bool isAtomic() const { return m_refCountAndFlags & s_refCountFlagIsAtomic; }
+    bool isAtomic() const { return m_hashAndFlags & s_hashFlagIsAtomic; }
     void setIsAtomic(bool isIdentifier)
     {
         ASSERT(!isStatic());
         if (isIdentifier)
-            m_refCountAndFlags |= s_refCountFlagIsAtomic;
+            m_hashAndFlags |= s_hashFlagIsAtomic;
         else
-            m_refCountAndFlags &= ~s_refCountFlagIsAtomic;
+            m_hashAndFlags &= ~s_hashFlagIsAtomic;
+    }
+
+private:
+    // The high bits of 'hash' are always empty, but we prefer to store our flags
+    // in the low bits because it makes them slightly more efficient to access.
+    // So, we shift left and right when setting and getting our hash code.
+    void setHash(unsigned hash) const
+    {
+        ASSERT(!hasHash());
+        ASSERT(hash == StringHasher::computeHash(m_data, m_length)); // Multiple clients assume that StringHasher is the canonical string hash function.
+        ASSERT(!(hash & (s_flagMask << (8 * sizeof(hash) - s_flagCount)))); // Verify that enough high bits are empty.
+        
+        hash <<= s_flagCount;
+        ASSERT(!(hash & m_hashAndFlags)); // Verify that enough low bits are empty after shift.
+        ASSERT(hash); // Verify that 0 is a valid sentinel hash value.
+
+        m_hashAndFlags |= hash; // Store hash with flags in low bits.
+    }
+
+    unsigned rawHash() const
+    {
+        return m_hashAndFlags >> s_flagCount;
+    }
+
+public:
+    bool hasHash() const
+    {
+        return rawHash() != 0;
     }
 
-    unsigned hash() const { if (!m_hash) m_hash = StringHasher::computeHash(m_data, m_length); return m_hash; }
-    unsigned existingHash() const { ASSERT(m_hash); return m_hash; }
-    bool hasHash() const { return m_hash; }
+    unsigned existingHash() const
+    {
+        ASSERT(hasHash());
+        return rawHash();
+    }
+
+    unsigned hash() const
+    {
+        if (!hasHash())
+            setHash(StringHasher::computeHash(m_data, m_length));
+        return existingHash();
+    }
+
+    inline bool hasOneRef() const
+    {
+        return m_refCount == s_refCountIncrement;
+    }
+
+    inline void ref()
+    {
+        m_refCount += s_refCountIncrement;
+    }
 
-    ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic))) delete this; }
-    ALWAYS_INLINE bool hasOneRef() const { return (m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic)) == s_refCountIncrement; }
+    inline void deref()
+    {
+        if (m_refCount == s_refCountIncrement) {
+            delete this;
+            return;
+        }
+
+        m_refCount -= s_refCountIncrement;
+    }
 
     static StringImpl* empty();
 
@@ -351,24 +395,27 @@ private:
 
     static PassRefPtr<StringImpl> createStrippingNullCharactersSlowCase(const UChar*, unsigned length);
     
-    BufferOwnership bufferOwnership() const { return static_cast<BufferOwnership>(m_refCountAndFlags & s_refCountMaskBufferOwnership); }
-    bool isStatic() const { return m_refCountAndFlags & s_refCountFlagStatic; }
+    BufferOwnership bufferOwnership() const { return static_cast<BufferOwnership>(m_hashAndFlags & s_hashMaskBufferOwnership); }
+    bool isStatic() const { return m_refCount & s_refCountFlagIsStaticString; }
     template <class UCharPredicate> PassRefPtr<StringImpl> stripMatchedCharacters(UCharPredicate);
     template <class UCharPredicate> PassRefPtr<StringImpl> simplifyMatchedCharactersToSpace(UCharPredicate);
 
-    // The bottom 7 bits hold flags, the top 25 bits hold the ref count.
-    // When dereferencing StringImpls we check for the ref count AND the
-    // static bit both being zero - static strings are never deleted.
-    static const unsigned s_refCountMask = 0xFFFFFF80;
-    static const unsigned s_refCountIncrement = 0x80;
-    static const unsigned s_refCountFlagStatic = 0x40;
-    static const unsigned s_refCountFlagHasTerminatingNullCharacter = 0x20;
-    static const unsigned s_refCountFlagIsAtomic = 0x10;
-    static const unsigned s_refCountFlagShouldReportedCost = 0x8;
-    static const unsigned s_refCountFlagIsIdentifier = 0x4;
-    static const unsigned s_refCountMaskBufferOwnership = 0x3;
-
-    unsigned m_refCountAndFlags;
+    // The bottom bit in the ref count indicates a static (immortal) string.
+    static const unsigned s_refCountFlagIsStaticString = 0x1;
+    static const unsigned s_refCountIncrement = 0x2; // This allows us to ref / deref without disturbing the static string flag.
+
+    // The bottom 6 bits in the hash are flags.
+    static const unsigned s_flagCount = 6;
+    static const unsigned s_flagMask = (1u << s_flagCount) - 1;
+    COMPILE_ASSERT(s_flagCount == StringHasher::flagCount, StringHasher_reserves_enough_bits_for_StringImpl_flags);
+
+    static const unsigned s_hashFlagHasTerminatingNullCharacter = 1u << 5;
+    static const unsigned s_hashFlagIsAtomic = 1u << 4;
+    static const unsigned s_hashFlagDidReportCost = 1u << 3;
+    static const unsigned s_hashFlagIsIdentifier = 1u << 2;
+    static const unsigned s_hashMaskBufferOwnership = 1u | (1u << 1);
+
+    unsigned m_refCount;
     unsigned m_length;
     const UChar* m_data;
     union {
@@ -376,7 +423,7 @@ private:
         StringImpl* m_substringBuffer;
         SharedUChar* m_sharedBuffer;
     };
-    mutable unsigned m_hash;
+    mutable unsigned m_hashAndFlags;
 };
 
 bool equal(const StringImpl*, const StringImpl*);
index 2b3780c..266b723 100755 (executable)
@@ -1,3 +1,13 @@
+2011-10-22  Geoffrey Garen  <ggaren@apple.com>
+
+        Separated string lifetime bits from character buffer state bits
+        https://bugs.webkit.org/show_bug.cgi?id=70673
+
+        Reviewed by Anders Carlsson.
+
+        * bindings/scripts/CodeGeneratorJS.pm:
+        (GenerateHashValue): Updated for string hashing changes in JavaScriptCore.
+
 2011-10-22  Pratik Solanki  <psolanki@apple.com>
 
         HTTPBodyStream in NSURLRequest gets lost when using CFNetwork loader
index b832064..c474acb 100644 (file)
@@ -3038,7 +3038,8 @@ sub GenerateHashTable
     push(@implContent, "static JSC_CONST_HASHTABLE HashTable $name = { $compactSize, $compactSizeMask, $nameEntries, 0 };\n");
 }
 
-# Internal helper
+# Paul Hsieh's SuperFastHash
+# http://www.azillionmonkeys.com/qed/hash.html
 sub GenerateHashValue
 {
     my $object = shift;
@@ -3048,16 +3049,16 @@ sub GenerateHashValue
     # This hash is designed to work on 16-bit chunks at a time. But since the normal case
     # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
     # were 16-bit chunks, which should give matching results
-
+    
     my $EXP2_32 = 4294967296;
-
+    
     my $hash = 0x9e3779b9;
     my $l    = scalar @chars; #I wish this was in Ruby --- Maks
     my $rem  = $l & 1;
     $l = $l >> 1;
-
+    
     my $s = 0;
-
+    
     # Main loop
     for (; $l > 0; $l--) {
         $hash   += ord($chars[$s]);
@@ -3067,14 +3068,14 @@ sub GenerateHashValue
         $hash += $hash >> 11;
         $hash %= $EXP2_32;
     }
-
+    
     # Handle end case
     if ($rem != 0) {
         $hash += ord($chars[$s]);
         $hash ^= (leftShift($hash, 11)% $EXP2_32);
         $hash += $hash >> 17;
     }
-
+    
     # Force "avalanching" of final 127 bits
     $hash ^= leftShift($hash, 3);
     $hash += ($hash >> 5);
@@ -3083,12 +3084,16 @@ sub GenerateHashValue
     $hash += ($hash >> 15);
     $hash = $hash% $EXP2_32;
     $hash ^= (leftShift($hash, 10)% $EXP2_32);
-
-    # this avoids ever returning a hash code of 0, since that is used to
-    # signal "hash not computed yet", using a value that is likely to be
-    # effectively the same as 0 when the low bits are masked
-    $hash = 0x80000000 if ($hash == 0);
-
+    
+    # Save 6 bits for StringImpl to use as flags.
+    $hash = ($hash >> 6);
+    
+    # This avoids ever returning a hash code of 0, since that is used to
+    # signal "hash not computed yet". Setting the high bit maintains
+    # reasonable fidelity to a hash code of 0 because it is likely to yield
+    # exactly 0 when hash lookup masks out the high bits.
+    $hash = (0x80000000 >> 6) if ($hash == 0);
+    
     return $hash;
 }