Structure should be more methodical about the relationship between m_offset and m_pro...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 16 Feb 2013 05:31:00 +0000 (05:31 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 16 Feb 2013 05:31:00 +0000 (05:31 +0000)
https://bugs.webkit.org/show_bug.cgi?id=109978

Reviewed by Mark Hahnenberg.

Allegedly, the previous relationship was that either m_propertyTable or m_offset
would be set, and if m_propertyTable was not set you could rebuild it.  In reality,
we would sometimes "reset" both: some transitions wouldn't set m_offset, and other
transitions would clear the previous structure's m_propertyTable.  So, in a
structure transition chain of A->B->C you could have:

A transitions to B: B doesn't copy m_offset but does copy m_propertyTable, because
    that seemed like a good idea at the time (this was a common idiom in the code).
B transitions to C: C steals B's m_propertyTable, leaving B with neither a
    m_propertyTable nor a m_offset.

Then we would ask for the size of the property storage of B and get the answer
"none".  That's not good.

Now, there is a new relationship, which, hopefully, should fix things: m_offset is
always set and always refers to the maximum offset ever used by the property table.
From this, you can infer both the inline and out-of-line property size, and
capacity.  This is accomplished by having PropertyTable::add() take a
PropertyOffset reference, which must be Structure::m_offset.  It will update this
offset.  As well, all transitions now copy m_offset.  And we frequently assert
(using RELEASE_ASSERT) that the m_offset matches what m_propertyTable would tell
you.  Hence if you ever modify the m_propertyTable, you'll also update the offset.
If you ever copy the property table, you'll also copy the offset.  Life should be
good, I think.

* runtime/PropertyMapHashTable.h:
(JSC::PropertyTable::add):
* runtime/Structure.cpp:
(JSC::Structure::materializePropertyMap):
(JSC::Structure::addPropertyTransition):
(JSC::Structure::removePropertyTransition):
(JSC::Structure::changePrototypeTransition):
(JSC::Structure::despecifyFunctionTransition):
(JSC::Structure::attributeChangeTransition):
(JSC::Structure::toDictionaryTransition):
(JSC::Structure::sealTransition):
(JSC::Structure::freezeTransition):
(JSC::Structure::preventExtensionsTransition):
(JSC::Structure::nonPropertyTransition):
(JSC::Structure::flattenDictionaryStructure):
(JSC::Structure::checkConsistency):
(JSC::Structure::putSpecificValue):
(JSC::Structure::createPropertyMap):
(JSC::PropertyTable::checkConsistency):
* runtime/Structure.h:
(JSC):
(JSC::Structure::putWillGrowOutOfLineStorage):
(JSC::Structure::outOfLineCapacity):
(JSC::Structure::outOfLineSize):
(JSC::Structure::isEmpty):
(JSC::Structure::materializePropertyMapIfNecessary):
(JSC::Structure::materializePropertyMapIfNecessaryForPinning):
(Structure):
(JSC::Structure::checkOffsetConsistency):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/PropertyMapHashTable.h
Source/JavaScriptCore/runtime/Structure.cpp
Source/JavaScriptCore/runtime/Structure.h

index 0c3acff..926275d 100644 (file)
@@ -1,3 +1,65 @@
+2013-02-15  Filip Pizlo  <fpizlo@apple.com>
+
+        Structure should be more methodical about the relationship between m_offset and m_propertyTable
+        https://bugs.webkit.org/show_bug.cgi?id=109978
+
+        Reviewed by Mark Hahnenberg.
+        
+        Allegedly, the previous relationship was that either m_propertyTable or m_offset
+        would be set, and if m_propertyTable was not set you could rebuild it.  In reality,
+        we would sometimes "reset" both: some transitions wouldn't set m_offset, and other
+        transitions would clear the previous structure's m_propertyTable.  So, in a
+        structure transition chain of A->B->C you could have:
+
+        A transitions to B: B doesn't copy m_offset but does copy m_propertyTable, because
+            that seemed like a good idea at the time (this was a common idiom in the code).
+        B transitions to C: C steals B's m_propertyTable, leaving B with neither a
+            m_propertyTable nor a m_offset.
+
+        Then we would ask for the size of the property storage of B and get the answer
+        "none".  That's not good.
+
+        Now, there is a new relationship, which, hopefully, should fix things: m_offset is
+        always set and always refers to the maximum offset ever used by the property table.
+        From this, you can infer both the inline and out-of-line property size, and
+        capacity.  This is accomplished by having PropertyTable::add() take a
+        PropertyOffset reference, which must be Structure::m_offset.  It will update this
+        offset.  As well, all transitions now copy m_offset.  And we frequently assert
+        (using RELEASE_ASSERT) that the m_offset matches what m_propertyTable would tell
+        you.  Hence if you ever modify the m_propertyTable, you'll also update the offset.
+        If you ever copy the property table, you'll also copy the offset.  Life should be
+        good, I think.
+
+        * runtime/PropertyMapHashTable.h:
+        (JSC::PropertyTable::add):
+        * runtime/Structure.cpp:
+        (JSC::Structure::materializePropertyMap):
+        (JSC::Structure::addPropertyTransition):
+        (JSC::Structure::removePropertyTransition):
+        (JSC::Structure::changePrototypeTransition):
+        (JSC::Structure::despecifyFunctionTransition):
+        (JSC::Structure::attributeChangeTransition):
+        (JSC::Structure::toDictionaryTransition):
+        (JSC::Structure::sealTransition):
+        (JSC::Structure::freezeTransition):
+        (JSC::Structure::preventExtensionsTransition):
+        (JSC::Structure::nonPropertyTransition):
+        (JSC::Structure::flattenDictionaryStructure):
+        (JSC::Structure::checkConsistency):
+        (JSC::Structure::putSpecificValue):
+        (JSC::Structure::createPropertyMap):
+        (JSC::PropertyTable::checkConsistency):
+        * runtime/Structure.h:
+        (JSC):
+        (JSC::Structure::putWillGrowOutOfLineStorage):
+        (JSC::Structure::outOfLineCapacity):
+        (JSC::Structure::outOfLineSize):
+        (JSC::Structure::isEmpty):
+        (JSC::Structure::materializePropertyMapIfNecessary):
+        (JSC::Structure::materializePropertyMapIfNecessaryForPinning):
+        (Structure):
+        (JSC::Structure::checkOffsetConsistency):
+
 2013-02-15  Martin Robinson  <mrobinson@igalia.com>
 
         [GTK] Spread the gyp build files throughout the tree
index 966c199..2422c5b 100644 (file)
@@ -157,7 +157,8 @@ public:
     find_iterator find(const KeyType&);
     find_iterator findWithString(const KeyType&);
     // Add a value to the table
-    std::pair<find_iterator, bool> add(const ValueType& entry);
+    enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
+    std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
     // Remove a value from the table.
     void remove(const find_iterator& iter);
     void remove(const KeyType& key);
@@ -389,12 +390,14 @@ inline PropertyTable::find_iterator PropertyTable::findWithString(const KeyType&
     }
 }
 
-inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry)
+inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
 {
     // Look for a value with a matching key already in the array.
     find_iterator iter = find(entry.key);
-    if (iter.first)
+    if (iter.first) {
+        RELEASE_ASSERT(iter.first->offset <= offset);
         return std::make_pair(iter, false);
+    }
 
     // Ref the key
     entry.key->ref();
@@ -413,6 +416,12 @@ inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const Va
     *iter.first = entry;
 
     ++m_keyCount;
+    
+    if (offsetEffect == PropertyOffsetMayChange)
+        offset = std::max(offset, entry.offset);
+    else
+        RELEASE_ASSERT(offset >= entry.offset);
+    
     return std::make_pair(iter, true);
 }
 
index 8650a7f..6160232 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.
+ * Copyright (C) 2008, 2009, 2013 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -256,13 +256,15 @@ void Structure::materializePropertyMap(JSGlobalData& globalData)
     if (!m_propertyTable)
         createPropertyMap(numberOfSlotsForLastOffset(m_offset, m_inlineCapacity));
 
-    for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
+    for (ptrdiff_t i = structures.size() - 1; i >= 0; --i) {
         structure = structures[i];
         if (!structure->m_nameInPrevious)
             continue;
         PropertyMapEntry entry(globalData, this, structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get());
-        m_propertyTable->add(entry);
+        m_propertyTable->add(entry, m_offset, PropertyTable::PropertyOffsetMustNotChange);
     }
+    
+    checkOffsetConsistency();
 }
 
 inline size_t nextOutOfLineStorageCapacity(size_t currentCapacity)
@@ -371,6 +373,7 @@ Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure*
     transition->m_specificValueInPrevious.setMayBeNull(globalData, transition, specificValue);
 
     if (structure->m_propertyTable) {
+        structure->checkOffsetConsistency();
         if (structure->m_isPinnedPropertyTable)
             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
         else
@@ -381,12 +384,14 @@ Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure*
         else
             transition->createPropertyMap();
     }
+    transition->m_offset = structure->m_offset;
 
     offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
 
-    transition->m_offset = offset;
     checkOffset(transition->m_offset, transition->inlineCapacity());
     structure->m_transitionTable.add(globalData, transition);
+    transition->checkOffsetConsistency();
+    structure->checkOffsetConsistency();
     return transition;
 }
 
@@ -398,6 +403,7 @@ Structure* Structure::removePropertyTransition(JSGlobalData& globalData, Structu
 
     offset = transition->remove(propertyName);
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -407,12 +413,12 @@ Structure* Structure::changePrototypeTransition(JSGlobalData& globalData, Struct
 
     transition->m_prototype.set(globalData, transition, prototype);
 
-    // Don't set m_offset, as one can not transition to this.
-
     structure->materializePropertyMapIfNecessary(globalData);
     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
+    transition->m_offset = structure->m_offset;
     transition->pin();
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -423,10 +429,9 @@ Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Stru
 
     ++transition->m_specificFunctionThrashCount;
 
-    // Don't set m_offset, as one can not transition to this.
-
     structure->materializePropertyMapIfNecessary(globalData);
     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
+    transition->m_offset = structure->m_offset;
     transition->pin();
 
     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
@@ -436,6 +441,7 @@ Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Stru
         ASSERT_UNUSED(removed, removed);
     }
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -444,10 +450,9 @@ Structure* Structure::attributeChangeTransition(JSGlobalData& globalData, Struct
     if (!structure->isUncacheableDictionary()) {
         Structure* transition = create(globalData, structure);
 
-        // Don't set m_offset, as one can not transition to this.
-
         structure->materializePropertyMapIfNecessary(globalData);
         transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
+        transition->m_offset = structure->m_offset;
         transition->pin();
         
         structure = transition;
@@ -458,6 +463,7 @@ Structure* Structure::attributeChangeTransition(JSGlobalData& globalData, Struct
     ASSERT(entry);
     entry->attributes = attributes;
 
+    structure->checkOffsetConsistency();
     return structure;
 }
 
@@ -469,9 +475,11 @@ Structure* Structure::toDictionaryTransition(JSGlobalData& globalData, Structure
 
     structure->materializePropertyMapIfNecessary(globalData);
     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
+    transition->m_offset = structure->m_offset;
     transition->m_dictionaryKind = kind;
     transition->pin();
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -496,6 +504,7 @@ Structure* Structure::sealTransition(JSGlobalData& globalData, Structure* struct
             iter->attributes |= DontDelete;
     }
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -513,6 +522,7 @@ Structure* Structure::freezeTransition(JSGlobalData& globalData, Structure* stru
             iter->attributes |= iter->attributes & Accessor ? DontDelete : (DontDelete | ReadOnly);
     }
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -525,9 +535,11 @@ Structure* Structure::preventExtensionsTransition(JSGlobalData& globalData, Stru
 
     structure->materializePropertyMapIfNecessary(globalData);
     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
+    transition->m_offset = structure->m_offset;
     transition->m_preventExtensions = true;
     transition->pin();
 
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -560,6 +572,7 @@ Structure* Structure::nonPropertyTransition(JSGlobalData& globalData, Structure*
     checkOffset(transition->m_offset, transition->inlineCapacity());
     
     if (structure->m_propertyTable) {
+        structure->checkOffsetConsistency();
         if (structure->m_isPinnedPropertyTable)
             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
         else
@@ -572,6 +585,7 @@ Structure* Structure::nonPropertyTransition(JSGlobalData& globalData, Structure*
     }
     
     structure->m_transitionTable.add(globalData, transition);
+    transition->checkOffsetConsistency();
     return transition;
 }
 
@@ -615,6 +629,7 @@ bool Structure::isFrozen(JSGlobalData& globalData)
 
 Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObject* object)
 {
+    checkOffsetConsistency();
     ASSERT(isDictionary());
     if (isUncacheableDictionary()) {
         ASSERT(m_propertyTable);
@@ -629,7 +644,7 @@ Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObj
         PropertyTable::iterator end = m_propertyTable->end();
         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter, ++i) {
             values[i] = object->getDirect(iter->offset);
-            iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
+            m_offset = iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
         }
         
         // Copies in our values to their compacted locations.
@@ -637,6 +652,7 @@ Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObj
             object->putDirect(globalData, offsetForPropertyNumber(i, m_inlineCapacity), values[i]);
 
         m_propertyTable->clearDeletedOffsets();
+        checkOffsetConsistency();
     }
 
     m_dictionaryKind = NoneDictionaryKind;
@@ -714,6 +730,7 @@ PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 
 inline void Structure::checkConsistency()
 {
+    checkOffsetConsistency();
 }
 
 #endif
@@ -786,8 +803,8 @@ PropertyOffset Structure::putSpecificValue(JSGlobalData& globalData, PropertyNam
 
     PropertyOffset newOffset = m_propertyTable->nextOffset(m_inlineCapacity);
 
-    m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue));
-
+    m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue), m_offset, PropertyTable::PropertyOffsetMayChange);
+    
     checkConsistency();
     return newOffset;
 }
@@ -820,7 +837,6 @@ void Structure::createPropertyMap(unsigned capacity)
 
     checkConsistency();
     m_propertyTable = adoptPtr(new PropertyTable(capacity));
-    checkConsistency();
 }
 
 void Structure::getPropertyNamesFromStructure(JSGlobalData& globalData, PropertyNameArray& propertyNames, EnumerationMode mode)
@@ -896,6 +912,7 @@ bool Structure::prototypeChainMayInterceptStoreTo(JSGlobalData& globalData, Prop
 
 void PropertyTable::checkConsistency()
 {
+    checkOffsetConsistency();
     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
     ASSERT(m_indexMask);
     ASSERT(m_indexSize == m_indexMask + 1);
index 8f42078..628461f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, 2009, 2012 Apple Inc. All rights reserved.
+ * Copyright (C) 2008, 2009, 2012, 2013 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -110,6 +110,8 @@ namespace JSC {
         bool didTransition() const { return m_didTransition; }
         bool putWillGrowOutOfLineStorage()
         {
+            checkOffsetConsistency();
+            
             ASSERT(outOfLineCapacity() >= outOfLineSize());
             
             if (!m_propertyTable) {
@@ -187,6 +189,8 @@ namespace JSC {
 
         unsigned outOfLineCapacity() const
         {
+            ASSERT(checkOffsetConsistency());
+            
             unsigned outOfLineSize = this->outOfLineSize();
 
             if (!outOfLineSize)
@@ -201,14 +205,9 @@ namespace JSC {
         }
         unsigned outOfLineSize() const
         {
+            ASSERT(checkOffsetConsistency());
             ASSERT(structure()->classInfo() == &s_info);
-            if (m_propertyTable) {
-                unsigned totalSize = m_propertyTable->propertyStorageSize();
-                unsigned inlineCapacity = this->inlineCapacity();
-                if (totalSize < inlineCapacity)
-                    return 0;
-                return totalSize - inlineCapacity;
-            }
+            
             return numberOfOutOfLineSlotsForLastOffset(m_offset);
         }
         bool hasInlineStorage() const
@@ -221,17 +220,10 @@ namespace JSC {
         }
         unsigned inlineSize() const
         {
-            unsigned result;
-            if (m_propertyTable)
-                result = m_propertyTable->propertyStorageSize();
-            else
-                result = m_offset + 1;
-            return std::min<unsigned>(result, m_inlineCapacity);
+            return std::min<unsigned>(m_offset + 1, m_inlineCapacity);
         }
         unsigned totalStorageSize() const
         {
-            if (m_propertyTable)
-                return m_propertyTable->propertyStorageSize();
             return numberOfSlotsForLastOffset(m_offset, m_inlineCapacity);
         }
         unsigned totalStorageCapacity() const
@@ -248,8 +240,6 @@ namespace JSC {
         }
         PropertyOffset lastValidOffset() const
         {
-            if (m_propertyTable)
-                return offsetForPropertyNumber(m_propertyTable->propertyStorageSize() - 1, m_inlineCapacity);
             return m_offset;
         }
         bool isValidOffset(PropertyOffset offset) const
@@ -281,8 +271,7 @@ namespace JSC {
         
         bool isEmpty() const
         {
-            if (m_propertyTable)
-                return m_propertyTable->isEmpty();
+            ASSERT(checkOffsetConsistency());
             return !JSC::isValidOffset(m_offset);
         }
 
@@ -405,12 +394,14 @@ namespace JSC {
         void materializePropertyMapIfNecessary(JSGlobalData& globalData)
         {
             ASSERT(structure()->classInfo() == &s_info);
+            ASSERT(checkOffsetConsistency());
             if (!m_propertyTable && previousID())
                 materializePropertyMap(globalData);
         }
         void materializePropertyMapIfNecessaryForPinning(JSGlobalData& globalData)
         {
             ASSERT(structure()->classInfo() == &s_info);
+            checkOffsetConsistency();
             if (!m_propertyTable)
                 materializePropertyMap(globalData);
         }
@@ -453,6 +444,20 @@ namespace JSC {
             ASSERT(typeInfo().structureHasRareData());
             return static_cast<StructureRareData*>(m_previousOrRareData.get());
         }
+        
+        ALWAYS_INLINE bool checkOffsetConsistency() const
+        {
+            if (!m_propertyTable) {
+                ASSERT(!m_isPinnedPropertyTable);
+                return true;
+            }
+            
+            RELEASE_ASSERT(numberOfSlotsForLastOffset(m_offset, m_inlineCapacity) == m_propertyTable->propertyStorageSize());
+            unsigned totalSize = m_propertyTable->propertyStorageSize();
+            RELEASE_ASSERT((totalSize < inlineCapacity() ? 0 : totalSize - inlineCapacity()) == numberOfOutOfLineSlotsForLastOffset(m_offset));
+            
+            return true;
+        }
 
         void allocateRareData(JSGlobalData&);
         void cloneRareDataFrom(JSGlobalData&, const Structure*);