1 /*

     2  * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions

     6  * are met:

     7  * 1. Redistributions of source code must retain the above copyright

     8  *    notice, this list of conditions and the following disclaimer.

     9  * 2. Redistributions in binary form must reproduce the above copyright

    10  *    notice, this list of conditions and the following disclaimer in the

    11  *    documentation and/or other materials provided with the distribution.

    12  *

    13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

    14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

    17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

    21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

    24  */

    25 

    26 #include "config.h"

    27 #include "Structure.h"

    28 

    29 #include "Identifier.h"

    30 #include "JSObject.h"

    31 #include "JSPropertyNameIterator.h"

    32 #include "Lookup.h"

    33 #include "PropertyNameArray.h"

    34 #include "StructureChain.h"

    35 #include <wtf/RefCountedLeakCounter.h>

    36 #include <wtf/RefPtr.h>

    37 

    38 #if ENABLE(JSC_MULTIPLE_THREADS)

    39 #include <wtf/Threading.h>

    40 #endif

    41 

    42 #define DUMP_STRUCTURE_ID_STATISTICS 0

    43 

    44 #ifndef NDEBUG

    45 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0

    46 #else

    47 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0

    48 #endif

    49 

    50 using namespace std;

    51 using namespace WTF;

    52 

    53 namespace JSC {

    54 

    55 // Choose a number for the following so that most property maps are smaller,

    56 // but it's not going to blow out the stack to allocate this number of pointers.

    57 static const int smallMapThreshold = 1024;

    58 

    59 // The point at which the function call overhead of the qsort implementation

    60 // becomes small compared to the inefficiency of insertion sort.

    61 static const unsigned tinyMapThreshold = 20;

    62 

    63 static const unsigned newTableSize = 16;

    64 

    65 #ifndef NDEBUG

    66 static WTF::RefCountedLeakCounter structureCounter("Structure");

    67 

    68 #if ENABLE(JSC_MULTIPLE_THREADS)

    69 static Mutex& ignoreSetMutex = *(new Mutex);

    70 #endif

    71 

    72 static bool shouldIgnoreLeaks;

    73 static HashSet<Structure*>& ignoreSet = *(new HashSet<Structure*>);

    74 #endif

    75 

    76 #if DUMP_STRUCTURE_ID_STATISTICS

    77 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);

    78 #endif

    79 

    80 static int comparePropertyMapEntryIndices(const void* a, const void* b);

    81 

    82 inline void Structure::setTransitionTable(TransitionTable* table)

    83 {

    84     ASSERT(m_isUsingSingleSlot);

    85 #ifndef NDEBUG

    86     setSingleTransition(0);

    87 #endif

    88     m_isUsingSingleSlot = false;

    89     m_transitions.m_table = table;

    90     // This implicitly clears the flag that indicates we're using a single transition

    91     ASSERT(!m_isUsingSingleSlot);

    92 }

    93 

    94 // The contains and get methods accept imprecise matches, so if an unspecialised transition exists

    95 // for the given key they will consider that transition to be a match.  If a specialised transition

    96 // exists and it matches the provided specificValue, get will return the specific transition.

    97 inline bool Structure::transitionTableContains(const StructureTransitionTableHash::Key& key, JSCell* specificValue)

    98 {

    99     if (m_isUsingSingleSlot) {

   100         Structure* existingTransition = singleTransition();

   101         return existingTransition && existingTransition->m_nameInPrevious.get() == key.first

   102                && existingTransition->m_attributesInPrevious == key.second

   103                && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0);

   104     }

   105     TransitionTable::iterator find = transitionTable()->find(key);

   106     if (find == transitionTable()->end())

   107         return false;

   108 

   109     return find->second.first || find->second.second->transitionedFor(specificValue);

   110 }

   111 

   112 inline Structure* Structure::transitionTableGet(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const

   113 {

   114     if (m_isUsingSingleSlot) {

   115         Structure* existingTransition = singleTransition();

   116         if (existingTransition && existingTransition->m_nameInPrevious.get() == key.first

   117             && existingTransition->m_attributesInPrevious == key.second

   118             && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0))

   119             return existingTransition;

   120         return 0;

   121     }

   122 

   123     Transition transition = transitionTable()->get(key);

   124     if (transition.second && transition.second->transitionedFor(specificValue))

   125         return transition.second;

   126     return transition.first;

   127 }

   128 

   129 inline bool Structure::transitionTableHasTransition(const StructureTransitionTableHash::Key& key) const

   130 {

   131     if (m_isUsingSingleSlot) {

   132         Structure* transition = singleTransition();

   133         return transition && transition->m_nameInPrevious == key.first

   134         && transition->m_attributesInPrevious == key.second;

   135     }

   136     return transitionTable()->contains(key);

   137 }

   138 

   139 inline void Structure::transitionTableRemove(const StructureTransitionTableHash::Key& key, JSCell* specificValue)

   140 {

   141     if (m_isUsingSingleSlot) {

   142         ASSERT(transitionTableContains(key, specificValue));

   143         setSingleTransition(0);

   144         return;

   145     }

   146     TransitionTable::iterator find = transitionTable()->find(key);

   147     if (!specificValue)

   148         find->second.first = 0;

   149     else

   150         find->second.second = 0;

   151     if (!find->second.first && !find->second.second)

   152         transitionTable()->remove(find);

   153 }

   154 

   155 inline void Structure::transitionTableAdd(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue)

   156 {

   157     if (m_isUsingSingleSlot) {

   158         if (!singleTransition()) {

   159             setSingleTransition(structure);

   160             return;

   161         }

   162         Structure* existingTransition = singleTransition();

   163         TransitionTable* transitionTable = new TransitionTable;

   164         setTransitionTable(transitionTable);

   165         if (existingTransition)

   166             transitionTableAdd(std::make_pair(existingTransition->m_nameInPrevious.get(), existingTransition->m_attributesInPrevious), existingTransition, existingTransition->m_specificValueInPrevious);

   167     }

   168     if (!specificValue) {

   169         TransitionTable::iterator find = transitionTable()->find(key);

   170         if (find == transitionTable()->end())

   171             transitionTable()->add(key, Transition(structure, static_cast<Structure*>(0)));

   172         else

   173             find->second.first = structure;

   174     } else {

   175         // If we're adding a transition to a specific value, then there cannot be

   176         // an existing transition

   177         ASSERT(!transitionTable()->contains(key));

   178         transitionTable()->add(key, Transition(static_cast<Structure*>(0), structure));

   179     }

   180 }

   181 

   182 void Structure::dumpStatistics()

   183 {

   184 #if DUMP_STRUCTURE_ID_STATISTICS

   185     unsigned numberLeaf = 0;

   186     unsigned numberUsingSingleSlot = 0;

   187     unsigned numberSingletons = 0;

   188     unsigned numberWithPropertyMaps = 0;

   189     unsigned totalPropertyMapsSize = 0;

   190 

   191     HashSet<Structure*>::const_iterator end = liveStructureSet.end();

   192     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {

   193         Structure* structure = *it;

   194         if (structure->m_usingSingleTransitionSlot) {

   195             if (!structure->m_transitions.singleTransition)

   196                 ++numberLeaf;

   197             else

   198                 ++numberUsingSingleSlot;

   199 

   200            if (!structure->m_previous && !structure->m_transitions.singleTransition)

   201                 ++numberSingletons;

   202         }

   203 

   204         if (structure->m_propertyTable) {

   205             ++numberWithPropertyMaps;

   206             totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size);

   207             if (structure->m_propertyTable->deletedOffsets)

   208                 totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned)); 

   209         }

   210     }

   211 

   212     printf("Number of live Structures: %d\n", liveStructureSet.size());

   213     printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);

   214     printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);

   215     printf("Number of Structures that singletons: %d\n", numberSingletons);

   216     printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);

   217 

   218     printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));

   219     printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);

   220     printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));

   221 #else

   222     printf("Dumping Structure statistics is not enabled.\n");

   223 #endif

   224 }

   225 

   226 Structure::Structure(JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount)

   227     : m_typeInfo(typeInfo)

   228     , m_prototype(prototype)

   229     , m_specificValueInPrevious(0)

   230     , m_propertyTable(0)

   231     , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)

   232     , m_offset(noOffset)

   233     , m_dictionaryKind(NoneDictionaryKind)

   234     , m_isPinnedPropertyTable(false)

   235     , m_hasGetterSetterProperties(false)

   236     , m_attributesInPrevious(0)

   237     , m_specificFunctionThrashCount(0)

   238     , m_anonymousSlotCount(anonymousSlotCount)

   239     , m_isUsingSingleSlot(true)

   240 {

   241     m_transitions.m_singleTransition = 0;

   242 

   243     ASSERT(m_prototype);

   244     ASSERT(m_prototype.isObject() || m_prototype.isNull());

   245 

   246 #ifndef NDEBUG

   247 #if ENABLE(JSC_MULTIPLE_THREADS)

   248     MutexLocker protect(ignoreSetMutex);

   249 #endif

   250     if (shouldIgnoreLeaks)

   251         ignoreSet.add(this);

   252     else

   253         structureCounter.increment();

   254 #endif

   255 

   256 #if DUMP_STRUCTURE_ID_STATISTICS

   257     liveStructureSet.add(this);

   258 #endif

   259 }

   260 

   261 Structure::~Structure()

   262 {

   263     if (m_previous) {

   264         ASSERT(m_nameInPrevious);

   265         m_previous->transitionTableRemove(make_pair(m_nameInPrevious.get(), m_attributesInPrevious), m_specificValueInPrevious);

   266 

   267     }

   268     ASSERT(!m_enumerationCache.hasDeadObject());

   269 

   270     if (m_propertyTable) {

   271         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;

   272         for (unsigned i = 1; i <= entryCount; i++) {

   273             if (UString::Rep* key = m_propertyTable->entries()[i].key)

   274                 key->deref();

   275         }

   276 

   277         delete m_propertyTable->deletedOffsets;

   278         fastFree(m_propertyTable);

   279     }

   280 

   281     if (!m_isUsingSingleSlot)

   282         delete transitionTable();

   283 

   284 #ifndef NDEBUG

   285 #if ENABLE(JSC_MULTIPLE_THREADS)

   286     MutexLocker protect(ignoreSetMutex);

   287 #endif

   288     HashSet<Structure*>::iterator it = ignoreSet.find(this);

   289     if (it != ignoreSet.end())

   290         ignoreSet.remove(it);

   291     else

   292         structureCounter.decrement();

   293 #endif

   294 

   295 #if DUMP_STRUCTURE_ID_STATISTICS

   296     liveStructureSet.remove(this);

   297 #endif

   298 }

   299 

   300 void Structure::startIgnoringLeaks()

   301 {

   302 #ifndef NDEBUG

   303     shouldIgnoreLeaks = true;

   304 #endif

   305 }

   306 

   307 void Structure::stopIgnoringLeaks()

   308 {

   309 #ifndef NDEBUG

   310     shouldIgnoreLeaks = false;

   311 #endif

   312 }

   313 

   314 static bool isPowerOf2(unsigned v)

   315 {

   316     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html

   317     

   318     return !(v & (v - 1)) && v;

   319 }

   320 

   321 static unsigned nextPowerOf2(unsigned v)

   322 {

   323     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html

   324     // Devised by Sean Anderson, Sepember 14, 2001

   325 

   326     v--;

   327     v |= v >> 1;

   328     v |= v >> 2;

   329     v |= v >> 4;

   330     v |= v >> 8;

   331     v |= v >> 16;

   332     v++;

   333 

   334     return v;

   335 }

   336 

   337 static unsigned sizeForKeyCount(size_t keyCount)

   338 {

   339     if (keyCount == notFound)

   340         return newTableSize;

   341 

   342     if (keyCount < 8)

   343         return newTableSize;

   344 

   345     if (isPowerOf2(keyCount))

   346         return keyCount * 4;

   347 

   348     return nextPowerOf2(keyCount) * 2;

   349 }

   350 

   351 void Structure::materializePropertyMap()

   352 {

   353     ASSERT(!m_propertyTable);

   354 

   355     Vector<Structure*, 8> structures;

   356     structures.append(this);

   357 

   358     Structure* structure = this;

   359 

   360     // Search for the last Structure with a property table. 

   361     while ((structure = structure->previousID())) {

   362         if (structure->m_isPinnedPropertyTable) {

   363             ASSERT(structure->m_propertyTable);

   364             ASSERT(!structure->m_previous);

   365 

   366             m_propertyTable = structure->copyPropertyTable();

   367             break;

   368         }

   369 

   370         structures.append(structure);

   371     }

   372 

   373     if (!m_propertyTable)

   374         createPropertyMapHashTable(sizeForKeyCount(m_offset + 1));

   375     else {

   376         if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size)

   377             rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above. 

   378     }

   379 

   380     for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {

   381         structure = structures[i];

   382         structure->m_nameInPrevious->ref();

   383         PropertyMapEntry entry(structure->m_nameInPrevious.get(), m_anonymousSlotCount + structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious, ++m_propertyTable->lastIndexUsed);

   384         insertIntoPropertyMapHashTable(entry);

   385     }

   386 }

   387 

   388 void Structure::growPropertyStorageCapacity()

   389 {

   390     if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)

   391         m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;

   392     else

   393         m_propertyStorageCapacity *= 2;

   394 }

   395 

   396 void Structure::despecifyDictionaryFunction(const Identifier& propertyName)

   397 {

   398     const UString::Rep* rep = propertyName._ustring.rep();

   399 

   400     materializePropertyMapIfNecessary();

   401 

   402     ASSERT(isDictionary());

   403     ASSERT(m_propertyTable);

   404 

   405     unsigned i = rep->existingHash();

   406 

   407 #if DUMP_PROPERTYMAP_STATS

   408     ++numProbes;

   409 #endif

   410 

   411     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   412     ASSERT(entryIndex != emptyEntryIndex);

   413 

   414     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   415         m_propertyTable->entries()[entryIndex - 1].specificValue = 0;

   416         return;

   417     }

   418 

   419 #if DUMP_PROPERTYMAP_STATS

   420     ++numCollisions;

   421 #endif

   422 

   423     unsigned k = 1 | doubleHash(rep->existingHash());

   424 

   425     while (1) {

   426         i += k;

   427 

   428 #if DUMP_PROPERTYMAP_STATS

   429         ++numRehashes;

   430 #endif

   431 

   432         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   433         ASSERT(entryIndex != emptyEntryIndex);

   434 

   435         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   436             m_propertyTable->entries()[entryIndex - 1].specificValue = 0;

   437             return;

   438         }

   439     }

   440 }

   441 

   442 PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)

   443 {

   444     ASSERT(!structure->isDictionary());

   445     ASSERT(structure->typeInfo().type() == ObjectType);

   446 

   447     if (Structure* existingTransition = structure->transitionTableGet(make_pair(propertyName.ustring().rep(), attributes), specificValue)) {

   448         ASSERT(existingTransition->m_offset != noOffset);

   449         offset = existingTransition->m_offset + existingTransition->m_anonymousSlotCount;

   450         ASSERT(offset >= structure->m_anonymousSlotCount);

   451         ASSERT(structure->m_anonymousSlotCount == existingTransition->m_anonymousSlotCount);

   452         return existingTransition;

   453     }

   454 

   455     return 0;

   456 }

   457 

   458 PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)

   459 {

   460     ASSERT(!structure->isDictionary());

   461     ASSERT(structure->typeInfo().type() == ObjectType);

   462     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));

   463     

   464     if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)

   465         specificValue = 0;

   466 

   467     if (structure->transitionCount() > s_maxTransitionLength) {

   468         RefPtr<Structure> transition = toCacheableDictionaryTransition(structure);

   469         ASSERT(structure != transition);

   470         offset = transition->put(propertyName, attributes, specificValue);

   471         ASSERT(offset >= structure->m_anonymousSlotCount);

   472         ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);

   473         if (transition->propertyStorageSize() > transition->propertyStorageCapacity())

   474             transition->growPropertyStorageCapacity();

   475         return transition.release();

   476     }

   477 

   478     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount());

   479 

   480     transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;

   481     transition->m_previous = structure;

   482     transition->m_nameInPrevious = propertyName.ustring().rep();

   483     transition->m_attributesInPrevious = attributes;

   484     transition->m_specificValueInPrevious = specificValue;

   485     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;

   486     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;

   487     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;

   488     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;

   489 

   490     if (structure->m_propertyTable) {

   491         if (structure->m_isPinnedPropertyTable)

   492             transition->m_propertyTable = structure->copyPropertyTable();

   493         else {

   494             transition->m_propertyTable = structure->m_propertyTable;

   495             structure->m_propertyTable = 0;

   496         }

   497     } else {

   498         if (structure->m_previous)

   499             transition->materializePropertyMap();

   500         else

   501             transition->createPropertyMapHashTable();

   502     }

   503 

   504     offset = transition->put(propertyName, attributes, specificValue);

   505     ASSERT(offset >= structure->m_anonymousSlotCount);

   506     ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);

   507     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())

   508         transition->growPropertyStorageCapacity();

   509 

   510     transition->m_offset = offset - structure->m_anonymousSlotCount;

   511     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());

   512     structure->transitionTableAdd(make_pair(propertyName.ustring().rep(), attributes), transition.get(), specificValue);

   513     return transition.release();

   514 }

   515 

   516 PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset)

   517 {

   518     ASSERT(!structure->isUncacheableDictionary());

   519 

   520     RefPtr<Structure> transition = toUncacheableDictionaryTransition(structure);

   521 

   522     offset = transition->remove(propertyName);

   523     ASSERT(offset >= structure->m_anonymousSlotCount);

   524     ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);

   525 

   526     return transition.release();

   527 }

   528 

   529 PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValue prototype)

   530 {

   531     RefPtr<Structure> transition = create(prototype, structure->typeInfo(), structure->anonymousSlotCount());

   532 

   533     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;

   534     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;

   535     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;

   536     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;

   537 

   538     // Don't set m_offset, as one can not transition to this.

   539 

   540     structure->materializePropertyMapIfNecessary();

   541     transition->m_propertyTable = structure->copyPropertyTable();

   542     transition->m_isPinnedPropertyTable = true;

   543     

   544     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());

   545     return transition.release();

   546 }

   547 

   548 PassRefPtr<Structure> Structure::despecifyFunctionTransition(Structure* structure, const Identifier& replaceFunction)

   549 {

   550     ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);

   551     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount());

   552 

   553     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;

   554     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;

   555     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;

   556     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount + 1;

   557 

   558     // Don't set m_offset, as one can not transition to this.

   559 

   560     structure->materializePropertyMapIfNecessary();

   561     transition->m_propertyTable = structure->copyPropertyTable();

   562     transition->m_isPinnedPropertyTable = true;

   563 

   564     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)

   565         transition->despecifyAllFunctions();

   566     else {

   567         bool removed = transition->despecifyFunction(replaceFunction);

   568         ASSERT_UNUSED(removed, removed);

   569     }

   570     

   571     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());

   572     return transition.release();

   573 }

   574 

   575 PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure)

   576 {

   577     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount());

   578     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;

   579     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;

   580     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;

   581     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;

   582 

   583     // Don't set m_offset, as one can not transition to this.

   584 

   585     structure->materializePropertyMapIfNecessary();

   586     transition->m_propertyTable = structure->copyPropertyTable();

   587     transition->m_isPinnedPropertyTable = true;

   588     

   589     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());

   590     return transition.release();

   591 }

   592 

   593 PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure, DictionaryKind kind)

   594 {

   595     ASSERT(!structure->isUncacheableDictionary());

   596     

   597     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount());

   598     transition->m_dictionaryKind = kind;

   599     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;

   600     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;

   601     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;

   602     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;

   603     

   604     structure->materializePropertyMapIfNecessary();

   605     transition->m_propertyTable = structure->copyPropertyTable();

   606     transition->m_isPinnedPropertyTable = true;

   607     

   608     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());

   609     return transition.release();

   610 }

   611 

   612 PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure)

   613 {

   614     return toDictionaryTransition(structure, CachedDictionaryKind);

   615 }

   616 

   617 PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure)

   618 {

   619     return toDictionaryTransition(structure, UncachedDictionaryKind);

   620 }

   621 

   622 PassRefPtr<Structure> Structure::flattenDictionaryStructure(JSObject* object)

   623 {

   624     ASSERT(isDictionary());

   625     if (isUncacheableDictionary()) {

   626         ASSERT(m_propertyTable);

   627         Vector<PropertyMapEntry*> sortedPropertyEntries(m_propertyTable->keyCount);

   628         PropertyMapEntry** p = sortedPropertyEntries.data();

   629         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;

   630         for (unsigned i = 1; i <= entryCount; i++) {

   631             if (m_propertyTable->entries()[i].key)

   632                 *p++ = &m_propertyTable->entries()[i];

   633         }

   634         size_t propertyCount = p - sortedPropertyEntries.data();

   635         qsort(sortedPropertyEntries.data(), propertyCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);

   636         sortedPropertyEntries.resize(propertyCount);

   637 

   638         // We now have the properties currently defined on this object

   639         // in the order that they are expected to be in, but we need to

   640         // reorder the storage, so we have to copy the current values out

   641         Vector<JSValue> values(propertyCount);

   642         unsigned anonymousSlotCount = m_anonymousSlotCount;

   643         for (unsigned i = 0; i < propertyCount; i++) {

   644             PropertyMapEntry* entry = sortedPropertyEntries[i];

   645             values[i] = object->getDirectOffset(entry->offset);

   646             // Update property table to have the new property offsets

   647             entry->offset = anonymousSlotCount + i;

   648             entry->index = i;

   649         }

   650         

   651         // Copy the original property values into their final locations

   652         for (unsigned i = 0; i < propertyCount; i++)

   653             object->putDirectOffset(anonymousSlotCount + i, values[i]);

   654 

   655         if (m_propertyTable->deletedOffsets) {

   656             delete m_propertyTable->deletedOffsets;

   657             m_propertyTable->deletedOffsets = 0;

   658         }

   659     }

   660 

   661     m_dictionaryKind = NoneDictionaryKind;

   662     return this;

   663 }

   664 

   665 size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)

   666 {

   667     ASSERT(!m_enumerationCache);

   668 

   669     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)

   670         specificValue = 0;

   671 

   672     materializePropertyMapIfNecessary();

   673 

   674     m_isPinnedPropertyTable = true;

   675 

   676     size_t offset = put(propertyName, attributes, specificValue);

   677     ASSERT(offset >= m_anonymousSlotCount);

   678     if (propertyStorageSize() > propertyStorageCapacity())

   679         growPropertyStorageCapacity();

   680     return offset;

   681 }

   682 

   683 size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName)

   684 {

   685     ASSERT(isUncacheableDictionary());

   686     ASSERT(!m_enumerationCache);

   687 

   688     materializePropertyMapIfNecessary();

   689 

   690     m_isPinnedPropertyTable = true;

   691     size_t offset = remove(propertyName);

   692     ASSERT(offset >= m_anonymousSlotCount);

   693     return offset;

   694 }

   695 

   696 #if DUMP_PROPERTYMAP_STATS

   697 

   698 static int numProbes;

   699 static int numCollisions;

   700 static int numRehashes;

   701 static int numRemoves;

   702 

   703 struct PropertyMapStatisticsExitLogger {

   704     ~PropertyMapStatisticsExitLogger();

   705 };

   706 

   707 static PropertyMapStatisticsExitLogger logger;

   708 

   709 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()

   710 {

   711     printf("\nJSC::PropertyMap statistics\n\n");

   712     printf("%d probes\n", numProbes);

   713     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);

   714     printf("%d rehashes\n", numRehashes);

   715     printf("%d removes\n", numRemoves);

   716 }

   717 

   718 #endif

   719 

   720 static const unsigned deletedSentinelIndex = 1;

   721 

   722 #if !DO_PROPERTYMAP_CONSTENCY_CHECK

   723 

   724 inline void Structure::checkConsistency()

   725 {

   726 }

   727 

   728 #endif

   729 

   730 PropertyMapHashTable* Structure::copyPropertyTable()

   731 {

   732     if (!m_propertyTable)

   733         return 0;

   734 

   735     size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);

   736     PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));

   737     memcpy(newTable, m_propertyTable, tableSize);

   738 

   739     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;

   740     for (unsigned i = 1; i <= entryCount; ++i) {

   741         if (UString::Rep* key = newTable->entries()[i].key)

   742             key->ref();

   743     }

   744 

   745     // Copy the deletedOffsets vector.

   746     if (m_propertyTable->deletedOffsets)

   747         newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets);

   748 

   749     return newTable;

   750 }

   751 

   752 size_t Structure::get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue)

   753 {

   754     materializePropertyMapIfNecessary();

   755     if (!m_propertyTable)

   756         return notFound;

   757 

   758     unsigned i = rep->existingHash();

   759 

   760 #if DUMP_PROPERTYMAP_STATS

   761     ++numProbes;

   762 #endif

   763 

   764     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   765     if (entryIndex == emptyEntryIndex)

   766         return notFound;

   767 

   768     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   769         attributes = m_propertyTable->entries()[entryIndex - 1].attributes;

   770         specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;

   771         ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount);

   772         return m_propertyTable->entries()[entryIndex - 1].offset;

   773     }

   774 

   775 #if DUMP_PROPERTYMAP_STATS

   776     ++numCollisions;

   777 #endif

   778 

   779     unsigned k = 1 | doubleHash(rep->existingHash());

   780 

   781     while (1) {

   782         i += k;

   783 

   784 #if DUMP_PROPERTYMAP_STATS

   785         ++numRehashes;

   786 #endif

   787 

   788         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   789         if (entryIndex == emptyEntryIndex)

   790             return notFound;

   791 

   792         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   793             attributes = m_propertyTable->entries()[entryIndex - 1].attributes;

   794             specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;

   795             ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount);

   796             return m_propertyTable->entries()[entryIndex - 1].offset;

   797         }

   798     }

   799 }

   800 

   801 bool Structure::despecifyFunction(const Identifier& propertyName)

   802 {

   803     ASSERT(!propertyName.isNull());

   804 

   805     materializePropertyMapIfNecessary();

   806     if (!m_propertyTable)

   807         return false;

   808 

   809     UString::Rep* rep = propertyName._ustring.rep();

   810 

   811     unsigned i = rep->existingHash();

   812 

   813 #if DUMP_PROPERTYMAP_STATS

   814     ++numProbes;

   815 #endif

   816 

   817     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   818     if (entryIndex == emptyEntryIndex)

   819         return false;

   820 

   821     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   822         ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);

   823         m_propertyTable->entries()[entryIndex - 1].specificValue = 0;

   824         return true;

   825     }

   826 

   827 #if DUMP_PROPERTYMAP_STATS

   828     ++numCollisions;

   829 #endif

   830 

   831     unsigned k = 1 | doubleHash(rep->existingHash());

   832 

   833     while (1) {

   834         i += k;

   835 

   836 #if DUMP_PROPERTYMAP_STATS

   837         ++numRehashes;

   838 #endif

   839 

   840         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   841         if (entryIndex == emptyEntryIndex)

   842             return false;

   843 

   844         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {

   845             ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);

   846             m_propertyTable->entries()[entryIndex - 1].specificValue = 0;

   847             return true;

   848         }

   849     }

   850 }

   851 

   852 void Structure::despecifyAllFunctions()

   853 {

   854     materializePropertyMapIfNecessary();

   855     if (!m_propertyTable)

   856         return;

   857     

   858     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;

   859     for (unsigned i = 1; i <= entryCount; ++i)

   860         m_propertyTable->entries()[i].specificValue = 0;

   861 }

   862 

   863 size_t Structure::put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)

   864 {

   865     ASSERT(!propertyName.isNull());

   866     ASSERT(get(propertyName) == notFound);

   867 

   868     checkConsistency();

   869 

   870     if (attributes & DontEnum)

   871         m_hasNonEnumerableProperties = true;

   872 

   873     UString::Rep* rep = propertyName._ustring.rep();

   874 

   875     if (!m_propertyTable)

   876         createPropertyMapHashTable();

   877 

   878     // FIXME: Consider a fast case for tables with no deleted sentinels.

   879 

   880     unsigned i = rep->existingHash();

   881     unsigned k = 0;

   882     bool foundDeletedElement = false;

   883     unsigned deletedElementIndex = 0; // initialize to make the compiler happy

   884 

   885 #if DUMP_PROPERTYMAP_STATS

   886     ++numProbes;

   887 #endif

   888 

   889     while (1) {

   890         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   891         if (entryIndex == emptyEntryIndex)

   892             break;

   893 

   894         if (entryIndex == deletedSentinelIndex) {

   895             // If we find a deleted-element sentinel, remember it for use later.

   896             if (!foundDeletedElement) {

   897                 foundDeletedElement = true;

   898                 deletedElementIndex = i;

   899             }

   900         }

   901 

   902         if (k == 0) {

   903             k = 1 | doubleHash(rep->existingHash());

   904 #if DUMP_PROPERTYMAP_STATS

   905             ++numCollisions;

   906 #endif

   907         }

   908 

   909         i += k;

   910 

   911 #if DUMP_PROPERTYMAP_STATS

   912         ++numRehashes;

   913 #endif

   914     }

   915 

   916     // Figure out which entry to use.

   917     unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;

   918     if (foundDeletedElement) {

   919         i = deletedElementIndex;

   920         --m_propertyTable->deletedSentinelCount;

   921 

   922         // Since we're not making the table bigger, we can't use the entry one past

   923         // the end that we were planning on using, so search backwards for the empty

   924         // slot that we can use. We know it will be there because we did at least one

   925         // deletion in the past that left an entry empty.

   926         while (m_propertyTable->entries()[--entryIndex - 1].key) { }

   927     }

   928 

   929     // Create a new hash table entry.

   930     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;

   931 

   932     // Create a new hash table entry.

   933     rep->ref();

   934     m_propertyTable->entries()[entryIndex - 1].key = rep;

   935     m_propertyTable->entries()[entryIndex - 1].attributes = attributes;

   936     m_propertyTable->entries()[entryIndex - 1].specificValue = specificValue;

   937     m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;

   938 

   939     unsigned newOffset;

   940     if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) {

   941         newOffset = m_propertyTable->deletedOffsets->last();

   942         m_propertyTable->deletedOffsets->removeLast();

   943     } else

   944         newOffset = m_propertyTable->keyCount + m_anonymousSlotCount;

   945     m_propertyTable->entries()[entryIndex - 1].offset = newOffset;

   946     

   947     ASSERT(newOffset >= m_anonymousSlotCount);

   948     ++m_propertyTable->keyCount;

   949 

   950     if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)

   951         expandPropertyMapHashTable();

   952 

   953     checkConsistency();

   954     return newOffset;

   955 }

   956 

   957 bool Structure::hasTransition(UString::Rep* rep, unsigned attributes)

   958 {

   959     return transitionTableHasTransition(make_pair(rep, attributes));

   960 }

   961 

   962 size_t Structure::remove(const Identifier& propertyName)

   963 {

   964     ASSERT(!propertyName.isNull());

   965 

   966     checkConsistency();

   967 

   968     UString::Rep* rep = propertyName._ustring.rep();

   969 

   970     if (!m_propertyTable)

   971         return notFound;

   972 

   973 #if DUMP_PROPERTYMAP_STATS

   974     ++numProbes;

   975     ++numRemoves;

   976 #endif

   977 

   978     // Find the thing to remove.

   979     unsigned i = rep->existingHash();

   980     unsigned k = 0;

   981     unsigned entryIndex;

   982     UString::Rep* key = 0;

   983     while (1) {

   984         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   985         if (entryIndex == emptyEntryIndex)

   986             return notFound;

   987 

   988         key = m_propertyTable->entries()[entryIndex - 1].key;

   989         if (rep == key)

   990             break;

   991 

   992         if (k == 0) {

   993             k = 1 | doubleHash(rep->existingHash());

   994 #if DUMP_PROPERTYMAP_STATS

   995             ++numCollisions;

   996 #endif

   997         }

   998 

   999         i += k;

  1000 

  1001 #if DUMP_PROPERTYMAP_STATS

  1002         ++numRehashes;

  1003 #endif

  1004     }

  1005 

  1006     // Replace this one element with the deleted sentinel. Also clear out

  1007     // the entry so we can iterate all the entries as needed.

  1008     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;

  1009 

  1010     size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;

  1011     ASSERT(offset >= m_anonymousSlotCount);

  1012 

  1013     key->deref();

  1014     m_propertyTable->entries()[entryIndex - 1].key = 0;

  1015     m_propertyTable->entries()[entryIndex - 1].attributes = 0;

  1016     m_propertyTable->entries()[entryIndex - 1].specificValue = 0;

  1017     m_propertyTable->entries()[entryIndex - 1].offset = 0;

  1018 

  1019     if (!m_propertyTable->deletedOffsets)

  1020         m_propertyTable->deletedOffsets = new Vector<unsigned>;

  1021     m_propertyTable->deletedOffsets->append(offset);

  1022 

  1023     ASSERT(m_propertyTable->keyCount >= 1);

  1024     --m_propertyTable->keyCount;

  1025     ++m_propertyTable->deletedSentinelCount;

  1026 

  1027     if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)

  1028         rehashPropertyMapHashTable();

  1029 

  1030     checkConsistency();

  1031     return offset;

  1032 }

  1033 

  1034 void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)

  1035 {

  1036     ASSERT(m_propertyTable);

  1037     ASSERT(entry.offset >= m_anonymousSlotCount);

  1038     unsigned i = entry.key->existingHash();

  1039     unsigned k = 0;

  1040 

  1041 #if DUMP_PROPERTYMAP_STATS

  1042     ++numProbes;

  1043 #endif

  1044 

  1045     while (1) {

  1046         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

  1047         if (entryIndex == emptyEntryIndex)

  1048             break;

  1049 

  1050         if (k == 0) {

  1051             k = 1 | doubleHash(entry.key->existingHash());

  1052 #if DUMP_PROPERTYMAP_STATS

  1053             ++numCollisions;

  1054 #endif

  1055         }

  1056 

  1057         i += k;

  1058 

  1059 #if DUMP_PROPERTYMAP_STATS

  1060         ++numRehashes;

  1061 #endif

  1062     }

  1063 

  1064     unsigned entryIndex = m_propertyTable->keyCount + 2;

  1065     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;

  1066     m_propertyTable->entries()[entryIndex - 1] = entry;

  1067 

  1068     ++m_propertyTable->keyCount;

  1069 }

  1070 

  1071 void Structure::createPropertyMapHashTable()

  1072 {

  1073     ASSERT(sizeForKeyCount(7) == newTableSize);

  1074     createPropertyMapHashTable(newTableSize);

  1075 }

  1076 

  1077 void Structure::createPropertyMapHashTable(unsigned newTableSize)

  1078 {

  1079     ASSERT(!m_propertyTable);

  1080     ASSERT(isPowerOf2(newTableSize));

  1081 

  1082     checkConsistency();

  1083 

  1084     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));

  1085     m_propertyTable->size = newTableSize;

  1086     m_propertyTable->sizeMask = newTableSize - 1;

  1087 

  1088     checkConsistency();

  1089 }

  1090 

  1091 void Structure::expandPropertyMapHashTable()

  1092 {

  1093     ASSERT(m_propertyTable);

  1094     rehashPropertyMapHashTable(m_propertyTable->size * 2);

  1095 }

  1096 

  1097 void Structure::rehashPropertyMapHashTable()

  1098 {

  1099     ASSERT(m_propertyTable);

  1100     ASSERT(m_propertyTable->size);

  1101     rehashPropertyMapHashTable(m_propertyTable->size);

  1102 }

  1103 

  1104 void Structure::rehashPropertyMapHashTable(unsigned newTableSize)

  1105 {

  1106     ASSERT(m_propertyTable);

  1107     ASSERT(isPowerOf2(newTableSize));

  1108 

  1109     checkConsistency();

  1110 

  1111     PropertyMapHashTable* oldTable = m_propertyTable;

  1112 

  1113     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));

  1114     m_propertyTable->size = newTableSize;

  1115     m_propertyTable->sizeMask = newTableSize - 1;

  1116 

  1117     unsigned lastIndexUsed = 0;

  1118     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;

  1119     for (unsigned i = 1; i <= entryCount; ++i) {

  1120         if (oldTable->entries()[i].key) {

  1121             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);

  1122             insertIntoPropertyMapHashTable(oldTable->entries()[i]);

  1123         }

  1124     }

  1125     m_propertyTable->lastIndexUsed = lastIndexUsed;

  1126     m_propertyTable->deletedOffsets = oldTable->deletedOffsets;

  1127 

  1128     fastFree(oldTable);

  1129 

  1130     checkConsistency();

  1131 }

  1132 

  1133 int comparePropertyMapEntryIndices(const void* a, const void* b)

  1134 {

  1135     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;