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
dumpStatistics()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
Structure(JSValue prototype,const TypeInfo & typeInfo,unsigned anonymousSlotCount)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
~Structure()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
startIgnoringLeaks()196 void Structure::startIgnoringLeaks()
197 {
198 #ifndef NDEBUG
199 shouldIgnoreLeaks = true;
200 #endif
201 }
202
stopIgnoringLeaks()203 void Structure::stopIgnoringLeaks()
204 {
205 #ifndef NDEBUG
206 shouldIgnoreLeaks = false;
207 #endif
208 }
209
isPowerOf2(unsigned v)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
nextPowerOf2(unsigned v)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
sizeForKeyCount(size_t keyCount)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
materializePropertyMap()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
growPropertyStorageCapacity()284 void Structure::growPropertyStorageCapacity()
285 {
286 if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
287 m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
288 else
289 m_propertyStorageCapacity *= 2;
290 }
291
despecifyDictionaryFunction(const Identifier & propertyName)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
addPropertyTransitionToExistingStructure(Structure * structure,const Identifier & propertyName,unsigned attributes,JSCell * specificValue,size_t & offset)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
addPropertyTransition(Structure * structure,const Identifier & propertyName,unsigned attributes,JSCell * specificValue,size_t & offset)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
removePropertyTransition(Structure * structure,const Identifier & propertyName,size_t & offset)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
changePrototypeTransition(Structure * structure,JSValue prototype)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
despecifyFunctionTransition(Structure * structure,const Identifier & replaceFunction)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
getterSetterTransition(Structure * structure)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
toDictionaryTransition(Structure * structure,DictionaryKind kind)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
toCacheableDictionaryTransition(Structure * structure)508 PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure)
509 {
510 return toDictionaryTransition(structure, CachedDictionaryKind);
511 }
512
toUncacheableDictionaryTransition(Structure * structure)513 PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure)
514 {
515 return toDictionaryTransition(structure, UncachedDictionaryKind);
516 }
517
flattenDictionaryStructure(JSObject * object)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
addPropertyWithoutTransition(const Identifier & propertyName,unsigned attributes,JSCell * specificValue)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
removePropertyWithoutTransition(const Identifier & propertyName)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
~PropertyMapStatisticsExitLogger()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
checkConsistency()620 inline void Structure::checkConsistency()
621 {
622 }
623
624 #endif
625
copyPropertyTable()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
get(const UString::Rep * rep,unsigned & attributes,JSCell * & specificValue)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
despecifyFunction(const Identifier & propertyName)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
despecifyAllFunctions()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
put(const Identifier & propertyName,unsigned attributes,JSCell * specificValue)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
hasTransition(UString::Rep * rep,unsigned attributes)853 bool Structure::hasTransition(UString::Rep* rep, unsigned attributes)
854 {
855 return table.hasTransition(make_pair(rep, attributes));
856 }
857
remove(const Identifier & propertyName)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
insertIntoPropertyMapHashTable(const PropertyMapEntry & entry)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
createPropertyMapHashTable()967 void Structure::createPropertyMapHashTable()
968 {
969 ASSERT(sizeForKeyCount(7) == newTableSize);
970 createPropertyMapHashTable(newTableSize);
971 }
972
createPropertyMapHashTable(unsigned newTableSize)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
expandPropertyMapHashTable()987 void Structure::expandPropertyMapHashTable()
988 {
989 ASSERT(m_propertyTable);
990 rehashPropertyMapHashTable(m_propertyTable->size * 2);
991 }
992
rehashPropertyMapHashTable()993 void Structure::rehashPropertyMapHashTable()
994 {
995 ASSERT(m_propertyTable);
996 ASSERT(m_propertyTable->size);
997 rehashPropertyMapHashTable(m_propertyTable->size);
998 }
999
rehashPropertyMapHashTable(unsigned newTableSize)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
comparePropertyMapEntryIndices(const void * a,const void * b)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
getPropertyNames(PropertyNameArray & propertyNames,EnumerationMode mode)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
checkConsistency()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