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 void Structure::dumpStatistics() 83 { 84 #if DUMP_STRUCTURE_ID_STATISTICS 85 unsigned numberLeaf = 0; 86 unsigned numberUsingSingleSlot = 0; 87 unsigned numberSingletons = 0; 88 unsigned numberWithPropertyMaps = 0; 89 unsigned totalPropertyMapsSize = 0; 90 91 HashSet<Structure*>::const_iterator end = liveStructureSet.end(); 92 for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) { 93 Structure* structure = *it; 94 if (structure->m_usingSingleTransitionSlot) { 95 if (!structure->m_transitions.singleTransition) 96 ++numberLeaf; 97 else 98 ++numberUsingSingleSlot; 99 100 if (!structure->m_previous && !structure->m_transitions.singleTransition) 101 ++numberSingletons; 102 } 103 104 if (structure->m_propertyTable) { 105 ++numberWithPropertyMaps; 106 totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size); 107 if (structure->m_propertyTable->deletedOffsets) 108 totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned)); 109 } 110 } 111 112 printf("Number of live Structures: %d\n", liveStructureSet.size()); 113 printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot); 114 printf("Number of Structures that are leaf nodes: %d\n", numberLeaf); 115 printf("Number of Structures that singletons: %d\n", numberSingletons); 116 printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps); 117 118 printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure))); 119 printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize); 120 printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size())); 121 #else 122 printf("Dumping Structure statistics is not enabled.\n"); 123 #endif 124 } 125 126 Structure::Structure(JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount) 127 : m_typeInfo(typeInfo) 128 , m_prototype(prototype) 129 , m_specificValueInPrevious(0) 130 , m_propertyTable(0) 131 , m_propertyStorageCapacity(JSObject::inlineStorageCapacity) 132 , m_offset(noOffset) 133 , m_dictionaryKind(NoneDictionaryKind) 134 , m_isPinnedPropertyTable(false) 135 , m_hasGetterSetterProperties(false) 136 , m_attributesInPrevious(0) 137 , m_specificFunctionThrashCount(0) 138 , m_anonymousSlotCount(anonymousSlotCount) 139 { 140 ASSERT(m_prototype); 141 ASSERT(m_prototype.isObject() || m_prototype.isNull()); 142 143 #ifndef NDEBUG 144 #if ENABLE(JSC_MULTIPLE_THREADS) 145 MutexLocker protect(ignoreSetMutex); 146 #endif 147 if (shouldIgnoreLeaks) 148 ignoreSet.add(this); 149 else 150 structureCounter.increment(); 151 #endif 152 153 #if DUMP_STRUCTURE_ID_STATISTICS 154 liveStructureSet.add(this); 155 #endif 156 } 157 158 Structure::~Structure() 159 { 160 if (m_previous) { 161 ASSERT(m_nameInPrevious); 162 m_previous->table.remove(make_pair(m_nameInPrevious.get(), m_attributesInPrevious), m_specificValueInPrevious); 163 164 } 165 166 if (m_enumerationCache) 167 m_enumerationCache->setCachedStructure(0); 168 169 if (m_propertyTable) { 170 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 171 for (unsigned i = 1; i <= entryCount; i++) { 172 if (UString::Rep* key = m_propertyTable->entries()[i].key) 173 key->deref(); 174 } 175 176 delete m_propertyTable->deletedOffsets; 177 fastFree(m_propertyTable); 178 } 179 180 #ifndef NDEBUG 181 #if ENABLE(JSC_MULTIPLE_THREADS) 182 MutexLocker protect(ignoreSetMutex); 183 #endif 184 HashSet<Structure*>::iterator it = ignoreSet.find(this); 185 if (it != ignoreSet.end()) 186 ignoreSet.remove(it); 187 else 188 structureCounter.decrement(); 189 #endif 190 191 #if DUMP_STRUCTURE_ID_STATISTICS 192 liveStructureSet.remove(this); 193 #endif 194 } 195 196 void Structure::startIgnoringLeaks() 197 { 198 #ifndef NDEBUG 199 shouldIgnoreLeaks = true; 200 #endif 201 } 202 203 void Structure::stopIgnoringLeaks() 204 { 205 #ifndef NDEBUG 206 shouldIgnoreLeaks = false; 207 #endif 208 } 209 210 static bool isPowerOf2(unsigned v) 211 { 212 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html 213 214 return !(v & (v - 1)) && v; 215 } 216 217 static unsigned nextPowerOf2(unsigned v) 218 { 219 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html 220 // Devised by Sean Anderson, Sepember 14, 2001 221 222 v--; 223 v |= v >> 1; 224 v |= v >> 2; 225 v |= v >> 4; 226 v |= v >> 8; 227 v |= v >> 16; 228 v++; 229 230 return v; 231 } 232 233 static unsigned sizeForKeyCount(size_t keyCount) 234 { 235 if (keyCount == notFound) 236 return newTableSize; 237 238 if (keyCount < 8) 239 return newTableSize; 240 241 if (isPowerOf2(keyCount)) 242 return keyCount * 4; 243 244 return nextPowerOf2(keyCount) * 2; 245 } 246 247 void Structure::materializePropertyMap() 248 { 249 ASSERT(!m_propertyTable); 250 251 Vector<Structure*, 8> structures; 252 structures.append(this); 253 254 Structure* structure = this; 255 256 // Search for the last Structure with a property table. 257 while ((structure = structure->previousID())) { 258 if (structure->m_isPinnedPropertyTable) { 259 ASSERT(structure->m_propertyTable); 260 ASSERT(!structure->m_previous); 261 262 m_propertyTable = structure->copyPropertyTable(); 263 break; 264 } 265 266 structures.append(structure); 267 } 268 269 if (!m_propertyTable) 270 createPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); 271 else { 272 if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size) 273 rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above. 274 } 275 276 for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) { 277 structure = structures[i]; 278 structure->m_nameInPrevious->ref(); 279 PropertyMapEntry entry(structure->m_nameInPrevious.get(), m_anonymousSlotCount + structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious, ++m_propertyTable->lastIndexUsed); 280 insertIntoPropertyMapHashTable(entry); 281 } 282 } 283 284 void Structure::growPropertyStorageCapacity() 285 { 286 if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity) 287 m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity; 288 else 289 m_propertyStorageCapacity *= 2; 290 } 291 292 void Structure::despecifyDictionaryFunction(const Identifier& propertyName) 293 { 294 const UString::Rep* rep = propertyName._ustring.rep(); 295 296 materializePropertyMapIfNecessary(); 297 298 ASSERT(isDictionary()); 299 ASSERT(m_propertyTable); 300 301 unsigned i = rep->existingHash(); 302 303 #if DUMP_PROPERTYMAP_STATS 304 ++numProbes; 305 #endif 306 307 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 308 ASSERT(entryIndex != emptyEntryIndex); 309 310 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 311 m_propertyTable->entries()[entryIndex - 1].specificValue = 0; 312 return; 313 } 314 315 #if DUMP_PROPERTYMAP_STATS 316 ++numCollisions; 317 #endif 318 319 unsigned k = 1 | doubleHash(rep->existingHash()); 320 321 while (1) { 322 i += k; 323 324 #if DUMP_PROPERTYMAP_STATS 325 ++numRehashes; 326 #endif 327 328 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 329 ASSERT(entryIndex != emptyEntryIndex); 330 331 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 332 m_propertyTable->entries()[entryIndex - 1].specificValue = 0; 333 return; 334 } 335 } 336 } 337 338 PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset) 339 { 340 ASSERT(!structure->isDictionary()); 341 ASSERT(structure->typeInfo().type() == ObjectType); 342 343 if (Structure* existingTransition = structure->table.get(make_pair(propertyName.ustring().rep(), attributes), specificValue)) { 344 ASSERT(existingTransition->m_offset != noOffset); 345 offset = existingTransition->m_offset + existingTransition->m_anonymousSlotCount; 346 ASSERT(offset >= structure->m_anonymousSlotCount); 347 ASSERT(structure->m_anonymousSlotCount == existingTransition->m_anonymousSlotCount); 348 return existingTransition; 349 } 350 351 return 0; 352 } 353 354 PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset) 355 { 356 ASSERT(!structure->isDictionary()); 357 ASSERT(structure->typeInfo().type() == ObjectType); 358 ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset)); 359 360 if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 361 specificValue = 0; 362 363 if (structure->transitionCount() > s_maxTransitionLength) { 364 RefPtr<Structure> transition = toCacheableDictionaryTransition(structure); 365 ASSERT(structure != transition); 366 offset = transition->put(propertyName, attributes, specificValue); 367 ASSERT(offset >= structure->m_anonymousSlotCount); 368 ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount); 369 if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) 370 transition->growPropertyStorageCapacity(); 371 return transition.release(); 372 } 373 374 RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount()); 375 376 transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain; 377 transition->m_previous = structure; 378 transition->m_nameInPrevious = propertyName.ustring().rep(); 379 transition->m_attributesInPrevious = attributes; 380 transition->m_specificValueInPrevious = specificValue; 381 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; 382 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; 383 transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; 384 transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; 385 386 if (structure->m_propertyTable) { 387 if (structure->m_isPinnedPropertyTable) 388 transition->m_propertyTable = structure->copyPropertyTable(); 389 else { 390 transition->m_propertyTable = structure->m_propertyTable; 391 structure->m_propertyTable = 0; 392 } 393 } else { 394 if (structure->m_previous) 395 transition->materializePropertyMap(); 396 else 397 transition->createPropertyMapHashTable(); 398 } 399 400 offset = transition->put(propertyName, attributes, specificValue); 401 ASSERT(offset >= structure->m_anonymousSlotCount); 402 ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount); 403 if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) 404 transition->growPropertyStorageCapacity(); 405 406 transition->m_offset = offset - structure->m_anonymousSlotCount; 407 ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount()); 408 structure->table.add(make_pair(propertyName.ustring().rep(), attributes), transition.get(), specificValue); 409 return transition.release(); 410 } 411 412 PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset) 413 { 414 ASSERT(!structure->isUncacheableDictionary()); 415 416 RefPtr<Structure> transition = toUncacheableDictionaryTransition(structure); 417 418 offset = transition->remove(propertyName); 419 ASSERT(offset >= structure->m_anonymousSlotCount); 420 ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount); 421 422 return transition.release(); 423 } 424 425 PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValue prototype) 426 { 427 RefPtr<Structure> transition = create(prototype, structure->typeInfo(), structure->anonymousSlotCount()); 428 429 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; 430 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; 431 transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; 432 transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; 433 434 // Don't set m_offset, as one can not transition to this. 435 436 structure->materializePropertyMapIfNecessary(); 437 transition->m_propertyTable = structure->copyPropertyTable(); 438 transition->m_isPinnedPropertyTable = true; 439 440 ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount()); 441 return transition.release(); 442 } 443 444 PassRefPtr<Structure> Structure::despecifyFunctionTransition(Structure* structure, const Identifier& replaceFunction) 445 { 446 ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount); 447 RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount()); 448 449 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; 450 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; 451 transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; 452 transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount + 1; 453 454 // Don't set m_offset, as one can not transition to this. 455 456 structure->materializePropertyMapIfNecessary(); 457 transition->m_propertyTable = structure->copyPropertyTable(); 458 transition->m_isPinnedPropertyTable = true; 459 460 if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 461 transition->despecifyAllFunctions(); 462 else { 463 bool removed = transition->despecifyFunction(replaceFunction); 464 ASSERT_UNUSED(removed, removed); 465 } 466 467 ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount()); 468 return transition.release(); 469 } 470 471 PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure) 472 { 473 RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount()); 474 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; 475 transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties; 476 transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; 477 transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; 478 479 // Don't set m_offset, as one can not transition to this. 480 481 structure->materializePropertyMapIfNecessary(); 482 transition->m_propertyTable = structure->copyPropertyTable(); 483 transition->m_isPinnedPropertyTable = true; 484 485 ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount()); 486 return transition.release(); 487 } 488 489 PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure, DictionaryKind kind) 490 { 491 ASSERT(!structure->isUncacheableDictionary()); 492 493 RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount()); 494 transition->m_dictionaryKind = kind; 495 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; 496 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; 497 transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; 498 transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; 499 500 structure->materializePropertyMapIfNecessary(); 501 transition->m_propertyTable = structure->copyPropertyTable(); 502 transition->m_isPinnedPropertyTable = true; 503 504 ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount()); 505 return transition.release(); 506 } 507 508 PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure) 509 { 510 return toDictionaryTransition(structure, CachedDictionaryKind); 511 } 512 513 PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure) 514 { 515 return toDictionaryTransition(structure, UncachedDictionaryKind); 516 } 517 518 PassRefPtr<Structure> Structure::flattenDictionaryStructure(JSObject* object) 519 { 520 ASSERT(isDictionary()); 521 if (isUncacheableDictionary()) { 522 ASSERT(m_propertyTable); 523 Vector<PropertyMapEntry*> sortedPropertyEntries(m_propertyTable->keyCount); 524 PropertyMapEntry** p = sortedPropertyEntries.data(); 525 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 526 for (unsigned i = 1; i <= entryCount; i++) { 527 if (m_propertyTable->entries()[i].key) 528 *p++ = &m_propertyTable->entries()[i]; 529 } 530 size_t propertyCount = p - sortedPropertyEntries.data(); 531 qsort(sortedPropertyEntries.data(), propertyCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices); 532 sortedPropertyEntries.resize(propertyCount); 533 534 // We now have the properties currently defined on this object 535 // in the order that they are expected to be in, but we need to 536 // reorder the storage, so we have to copy the current values out 537 Vector<JSValue> values(propertyCount); 538 unsigned anonymousSlotCount = m_anonymousSlotCount; 539 for (unsigned i = 0; i < propertyCount; i++) { 540 PropertyMapEntry* entry = sortedPropertyEntries[i]; 541 values[i] = object->getDirectOffset(entry->offset); 542 // Update property table to have the new property offsets 543 entry->offset = anonymousSlotCount + i; 544 entry->index = i; 545 } 546 547 // Copy the original property values into their final locations 548 for (unsigned i = 0; i < propertyCount; i++) 549 object->putDirectOffset(anonymousSlotCount + i, values[i]); 550 551 if (m_propertyTable->deletedOffsets) { 552 delete m_propertyTable->deletedOffsets; 553 m_propertyTable->deletedOffsets = 0; 554 } 555 } 556 557 m_dictionaryKind = NoneDictionaryKind; 558 return this; 559 } 560 561 size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue) 562 { 563 ASSERT(!m_enumerationCache); 564 565 if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 566 specificValue = 0; 567 568 materializePropertyMapIfNecessary(); 569 570 m_isPinnedPropertyTable = true; 571 572 size_t offset = put(propertyName, attributes, specificValue); 573 ASSERT(offset >= m_anonymousSlotCount); 574 if (propertyStorageSize() > propertyStorageCapacity()) 575 growPropertyStorageCapacity(); 576 return offset; 577 } 578 579 size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName) 580 { 581 ASSERT(isUncacheableDictionary()); 582 ASSERT(!m_enumerationCache); 583 584 materializePropertyMapIfNecessary(); 585 586 m_isPinnedPropertyTable = true; 587 size_t offset = remove(propertyName); 588 ASSERT(offset >= m_anonymousSlotCount); 589 return offset; 590 } 591 592 #if DUMP_PROPERTYMAP_STATS 593 594 static int numProbes; 595 static int numCollisions; 596 static int numRehashes; 597 static int numRemoves; 598 599 struct PropertyMapStatisticsExitLogger { 600 ~PropertyMapStatisticsExitLogger(); 601 }; 602 603 static PropertyMapStatisticsExitLogger logger; 604 605 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger() 606 { 607 printf("\nJSC::PropertyMap statistics\n\n"); 608 printf("%d probes\n", numProbes); 609 printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes); 610 printf("%d rehashes\n", numRehashes); 611 printf("%d removes\n", numRemoves); 612 } 613 614 #endif 615 616 static const unsigned deletedSentinelIndex = 1; 617 618 #if !DO_PROPERTYMAP_CONSTENCY_CHECK 619 620 inline void Structure::checkConsistency() 621 { 622 } 623 624 #endif 625 626 PropertyMapHashTable* Structure::copyPropertyTable() 627 { 628 if (!m_propertyTable) 629 return 0; 630 631 size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size); 632 PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize)); 633 memcpy(newTable, m_propertyTable, tableSize); 634 635 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 636 for (unsigned i = 1; i <= entryCount; ++i) { 637 if (UString::Rep* key = newTable->entries()[i].key) 638 key->ref(); 639 } 640 641 // Copy the deletedOffsets vector. 642 if (m_propertyTable->deletedOffsets) 643 newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets); 644 645 return newTable; 646 } 647 648 size_t Structure::get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue) 649 { 650 materializePropertyMapIfNecessary(); 651 if (!m_propertyTable) 652 return notFound; 653 654 unsigned i = rep->existingHash(); 655 656 #if DUMP_PROPERTYMAP_STATS 657 ++numProbes; 658 #endif 659 660 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 661 if (entryIndex == emptyEntryIndex) 662 return notFound; 663 664 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 665 attributes = m_propertyTable->entries()[entryIndex - 1].attributes; 666 specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue; 667 ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount); 668 return m_propertyTable->entries()[entryIndex - 1].offset; 669 } 670 671 #if DUMP_PROPERTYMAP_STATS 672 ++numCollisions; 673 #endif 674 675 unsigned k = 1 | doubleHash(rep->existingHash()); 676 677 while (1) { 678 i += k; 679 680 #if DUMP_PROPERTYMAP_STATS 681 ++numRehashes; 682 #endif 683 684 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 685 if (entryIndex == emptyEntryIndex) 686 return notFound; 687 688 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 689 attributes = m_propertyTable->entries()[entryIndex - 1].attributes; 690 specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue; 691 ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount); 692 return m_propertyTable->entries()[entryIndex - 1].offset; 693 } 694 } 695 } 696 697 bool Structure::despecifyFunction(const Identifier& propertyName) 698 { 699 ASSERT(!propertyName.isNull()); 700 701 materializePropertyMapIfNecessary(); 702 if (!m_propertyTable) 703 return false; 704 705 UString::Rep* rep = propertyName._ustring.rep(); 706 707 unsigned i = rep->existingHash(); 708 709 #if DUMP_PROPERTYMAP_STATS 710 ++numProbes; 711 #endif 712 713 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 714 if (entryIndex == emptyEntryIndex) 715 return false; 716 717 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 718 ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue); 719 m_propertyTable->entries()[entryIndex - 1].specificValue = 0; 720 return true; 721 } 722 723 #if DUMP_PROPERTYMAP_STATS 724 ++numCollisions; 725 #endif 726 727 unsigned k = 1 | doubleHash(rep->existingHash()); 728 729 while (1) { 730 i += k; 731 732 #if DUMP_PROPERTYMAP_STATS 733 ++numRehashes; 734 #endif 735 736 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 737 if (entryIndex == emptyEntryIndex) 738 return false; 739 740 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 741 ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue); 742 m_propertyTable->entries()[entryIndex - 1].specificValue = 0; 743 return true; 744 } 745 } 746 } 747 748 void Structure::despecifyAllFunctions() 749 { 750 materializePropertyMapIfNecessary(); 751 if (!m_propertyTable) 752 return; 753 754 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 755 for (unsigned i = 1; i <= entryCount; ++i) 756 m_propertyTable->entries()[i].specificValue = 0; 757 } 758 759 size_t Structure::put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue) 760 { 761 ASSERT(!propertyName.isNull()); 762 ASSERT(get(propertyName) == notFound); 763 764 checkConsistency(); 765 766 if (attributes & DontEnum) 767 m_hasNonEnumerableProperties = true; 768 769 UString::Rep* rep = propertyName._ustring.rep(); 770 771 if (!m_propertyTable) 772 createPropertyMapHashTable(); 773 774 // FIXME: Consider a fast case for tables with no deleted sentinels. 775 776 unsigned i = rep->existingHash(); 777 unsigned k = 0; 778 bool foundDeletedElement = false; 779 unsigned deletedElementIndex = 0; // initialize to make the compiler happy 780 781 #if DUMP_PROPERTYMAP_STATS 782 ++numProbes; 783 #endif 784 785 while (1) { 786 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 787 if (entryIndex == emptyEntryIndex) 788 break; 789 790 if (entryIndex == deletedSentinelIndex) { 791 // If we find a deleted-element sentinel, remember it for use later. 792 if (!foundDeletedElement) { 793 foundDeletedElement = true; 794 deletedElementIndex = i; 795 } 796 } 797 798 if (k == 0) { 799 k = 1 | doubleHash(rep->existingHash()); 800 #if DUMP_PROPERTYMAP_STATS 801 ++numCollisions; 802 #endif 803 } 804 805 i += k; 806 807 #if DUMP_PROPERTYMAP_STATS 808 ++numRehashes; 809 #endif 810 } 811 812 // Figure out which entry to use. 813 unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2; 814 if (foundDeletedElement) { 815 i = deletedElementIndex; 816 --m_propertyTable->deletedSentinelCount; 817 818 // Since we're not making the table bigger, we can't use the entry one past 819 // the end that we were planning on using, so search backwards for the empty 820 // slot that we can use. We know it will be there because we did at least one 821 // deletion in the past that left an entry empty. 822 while (m_propertyTable->entries()[--entryIndex - 1].key) { } 823 } 824 825 // Create a new hash table entry. 826 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; 827 828 // Create a new hash table entry. 829 rep->ref(); 830 m_propertyTable->entries()[entryIndex - 1].key = rep; 831 m_propertyTable->entries()[entryIndex - 1].attributes = attributes; 832 m_propertyTable->entries()[entryIndex - 1].specificValue = specificValue; 833 m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed; 834 835 unsigned newOffset; 836 if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) { 837 newOffset = m_propertyTable->deletedOffsets->last(); 838 m_propertyTable->deletedOffsets->removeLast(); 839 } else 840 newOffset = m_propertyTable->keyCount + m_anonymousSlotCount; 841 m_propertyTable->entries()[entryIndex - 1].offset = newOffset; 842 843 ASSERT(newOffset >= m_anonymousSlotCount); 844 ++m_propertyTable->keyCount; 845 846 if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size) 847 expandPropertyMapHashTable(); 848 849 checkConsistency(); 850 return newOffset; 851 } 852 853 bool Structure::hasTransition(UString::Rep* rep, unsigned attributes) 854 { 855 return table.hasTransition(make_pair(rep, attributes)); 856 } 857 858 size_t Structure::remove(const Identifier& propertyName) 859 { 860 ASSERT(!propertyName.isNull()); 861 862 checkConsistency(); 863 864 UString::Rep* rep = propertyName._ustring.rep(); 865 866 if (!m_propertyTable) 867 return notFound; 868 869 #if DUMP_PROPERTYMAP_STATS 870 ++numProbes; 871 ++numRemoves; 872 #endif 873 874 // Find the thing to remove. 875 unsigned i = rep->existingHash(); 876 unsigned k = 0; 877 unsigned entryIndex; 878 UString::Rep* key = 0; 879 while (1) { 880 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 881 if (entryIndex == emptyEntryIndex) 882 return notFound; 883 884 key = m_propertyTable->entries()[entryIndex - 1].key; 885 if (rep == key) 886 break; 887 888 if (k == 0) { 889 k = 1 | doubleHash(rep->existingHash()); 890 #if DUMP_PROPERTYMAP_STATS 891 ++numCollisions; 892 #endif 893 } 894 895 i += k; 896 897 #if DUMP_PROPERTYMAP_STATS 898 ++numRehashes; 899 #endif 900 } 901 902 // Replace this one element with the deleted sentinel. Also clear out 903 // the entry so we can iterate all the entries as needed. 904 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex; 905 906 size_t offset = m_propertyTable->entries()[entryIndex - 1].offset; 907 ASSERT(offset >= m_anonymousSlotCount); 908 909 key->deref(); 910 m_propertyTable->entries()[entryIndex - 1].key = 0; 911 m_propertyTable->entries()[entryIndex - 1].attributes = 0; 912 m_propertyTable->entries()[entryIndex - 1].specificValue = 0; 913 m_propertyTable->entries()[entryIndex - 1].offset = 0; 914 915 if (!m_propertyTable->deletedOffsets) 916 m_propertyTable->deletedOffsets = new Vector<unsigned>; 917 m_propertyTable->deletedOffsets->append(offset); 918 919 ASSERT(m_propertyTable->keyCount >= 1); 920 --m_propertyTable->keyCount; 921 ++m_propertyTable->deletedSentinelCount; 922 923 if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size) 924 rehashPropertyMapHashTable(); 925 926 checkConsistency(); 927 return offset; 928 } 929 930 void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry) 931 { 932 ASSERT(m_propertyTable); 933 ASSERT(entry.offset >= m_anonymousSlotCount); 934 unsigned i = entry.key->existingHash(); 935 unsigned k = 0; 936 937 #if DUMP_PROPERTYMAP_STATS 938 ++numProbes; 939 #endif 940 941 while (1) { 942 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 943 if (entryIndex == emptyEntryIndex) 944 break; 945 946 if (k == 0) { 947 k = 1 | doubleHash(entry.key->existingHash()); 948 #if DUMP_PROPERTYMAP_STATS 949 ++numCollisions; 950 #endif 951 } 952 953 i += k; 954 955 #if DUMP_PROPERTYMAP_STATS 956 ++numRehashes; 957 #endif 958 } 959 960 unsigned entryIndex = m_propertyTable->keyCount + 2; 961 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; 962 m_propertyTable->entries()[entryIndex - 1] = entry; 963 964 ++m_propertyTable->keyCount; 965 } 966 967 void Structure::createPropertyMapHashTable() 968 { 969 ASSERT(sizeForKeyCount(7) == newTableSize); 970 createPropertyMapHashTable(newTableSize); 971 } 972 973 void Structure::createPropertyMapHashTable(unsigned newTableSize) 974 { 975 ASSERT(!m_propertyTable); 976 ASSERT(isPowerOf2(newTableSize)); 977 978 checkConsistency(); 979 980 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize))); 981 m_propertyTable->size = newTableSize; 982 m_propertyTable->sizeMask = newTableSize - 1; 983 984 checkConsistency(); 985 } 986 987 void Structure::expandPropertyMapHashTable() 988 { 989 ASSERT(m_propertyTable); 990 rehashPropertyMapHashTable(m_propertyTable->size * 2); 991 } 992 993 void Structure::rehashPropertyMapHashTable() 994 { 995 ASSERT(m_propertyTable); 996 ASSERT(m_propertyTable->size); 997 rehashPropertyMapHashTable(m_propertyTable->size); 998 } 999 1000 void Structure::rehashPropertyMapHashTable(unsigned newTableSize) 1001 { 1002 ASSERT(m_propertyTable); 1003 ASSERT(isPowerOf2(newTableSize)); 1004 1005 checkConsistency(); 1006 1007 PropertyMapHashTable* oldTable = m_propertyTable; 1008 1009 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize))); 1010 m_propertyTable->size = newTableSize; 1011 m_propertyTable->sizeMask = newTableSize - 1; 1012 1013 unsigned lastIndexUsed = 0; 1014 unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount; 1015 for (unsigned i = 1; i <= entryCount; ++i) { 1016 if (oldTable->entries()[i].key) { 1017 lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed); 1018 insertIntoPropertyMapHashTable(oldTable->entries()[i]); 1019 } 1020 } 1021 m_propertyTable->lastIndexUsed = lastIndexUsed; 1022 m_propertyTable->deletedOffsets = oldTable->deletedOffsets; 1023 1024 fastFree(oldTable); 1025 1026 checkConsistency(); 1027 } 1028 1029 int comparePropertyMapEntryIndices(const void* a, const void* b) 1030 { 1031 unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index; 1032 unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index; 1033 if (ia < ib) 1034 return -1; 1035 if (ia > ib) 1036 return +1; 1037 return 0; 1038 } 1039 1040 void Structure::getPropertyNames(PropertyNameArray& propertyNames, EnumerationMode mode) 1041 { 1042 materializePropertyMapIfNecessary(); 1043 if (!m_propertyTable) 1044 return; 1045 1046 if (m_propertyTable->keyCount < tinyMapThreshold) { 1047 PropertyMapEntry* a[tinyMapThreshold]; 1048 int i = 0; 1049 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 1050 for (unsigned k = 1; k <= entryCount; k++) { 1051 ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[k].attributes & DontEnum)); 1052 if (m_propertyTable->entries()[k].key && (!(m_propertyTable->entries()[k].attributes & DontEnum) || (mode == IncludeDontEnumProperties))) { 1053 PropertyMapEntry* value = &m_propertyTable->entries()[k]; 1054 int j; 1055 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j) 1056 a[j + 1] = a[j]; 1057 a[j + 1] = value; 1058 ++i; 1059 } 1060 } 1061 if (!propertyNames.size()) { 1062 for (int k = 0; k < i; ++k) 1063 propertyNames.addKnownUnique(a[k]->key); 1064 } else { 1065 for (int k = 0; k < i; ++k) 1066 propertyNames.add(a[k]->key); 1067 } 1068 1069 return; 1070 } 1071 1072 // Allocate a buffer to use to sort the keys. 1073 Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount); 1074 1075 // Get pointers to the enumerable entries in the buffer. 1076 PropertyMapEntry** p = sortedEnumerables.data(); 1077 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 1078 for (unsigned i = 1; i <= entryCount; i++) { 1079 if (m_propertyTable->entries()[i].key && (!(m_propertyTable->entries()[i].attributes & DontEnum) || (mode == IncludeDontEnumProperties))) 1080 *p++ = &m_propertyTable->entries()[i]; 1081 } 1082 1083 size_t enumerableCount = p - sortedEnumerables.data(); 1084 // Sort the entries by index. 1085 qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices); 1086 sortedEnumerables.resize(enumerableCount); 1087 1088 // Put the keys of the sorted entries into the list. 1089 if (!propertyNames.size()) { 1090 for (size_t i = 0; i < sortedEnumerables.size(); ++i) 1091 propertyNames.addKnownUnique(sortedEnumerables[i]->key); 1092 } else { 1093 for (size_t i = 0; i < sortedEnumerables.size(); ++i) 1094 propertyNames.add(sortedEnumerables[i]->key); 1095 } 1096 } 1097 1098 #if DO_PROPERTYMAP_CONSTENCY_CHECK 1099 1100 void Structure::checkConsistency() 1101 { 1102 if (!m_propertyTable) 1103 return; 1104 1105 ASSERT(m_propertyTable->size >= newTableSize); 1106 ASSERT(m_propertyTable->sizeMask); 1107 ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1); 1108 ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask)); 1109 1110 ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2); 1111 ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4); 1112 1113 ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2); 1114 1115 unsigned indexCount = 0; 1116 unsigned deletedIndexCount = 0; 1117 for (unsigned a = 0; a != m_propertyTable->size; ++a) { 1118 unsigned entryIndex = m_propertyTable->entryIndices[a]; 1119 if (entryIndex == emptyEntryIndex) 1120 continue; 1121 if (entryIndex == deletedSentinelIndex) { 1122 ++deletedIndexCount; 1123 continue; 1124 } 1125 ASSERT(entryIndex > deletedSentinelIndex); 1126 ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount); 1127 ++indexCount; 1128 1129 for (unsigned b = a + 1; b != m_propertyTable->size; ++b) 1130 ASSERT(m_propertyTable->entryIndices[b] != entryIndex); 1131 } 1132 ASSERT(indexCount == m_propertyTable->keyCount); 1133 ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount); 1134 1135 ASSERT(m_propertyTable->entries()[0].key == 0); 1136 1137 unsigned nonEmptyEntryCount = 0; 1138 for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) { 1139 ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[c].attributes & DontEnum)); 1140 UString::Rep* rep = m_propertyTable->entries()[c].key; 1141 ASSERT(m_propertyTable->entries()[c].offset >= m_anonymousSlotCount); 1142 if (!rep) 1143 continue; 1144 ++nonEmptyEntryCount; 1145 unsigned i = rep->existingHash(); 1146 unsigned k = 0; 1147 unsigned entryIndex; 1148 while (1) { 1149 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 1150 ASSERT(entryIndex != emptyEntryIndex); 1151 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 1152 break; 1153 if (k == 0) 1154 k = 1 | doubleHash(rep->existingHash()); 1155 i += k; 1156 } 1157 ASSERT(entryIndex == c + 1); 1158 } 1159 1160 ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount); 1161 } 1162 1163 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK 1164 1165 } // namespace JSC 1166
