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