1/*
2 * Copyright (C) 2004-2019 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB. If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20
21#pragma once
22
23#include "JSExportMacros.h"
24#include "PropertyOffset.h"
25#include "Structure.h"
26#include "WriteBarrier.h"
27#include <wtf/HashTable.h>
28#include <wtf/MathExtras.h>
29#include <wtf/Vector.h>
30#include <wtf/text/AtomStringImpl.h>
31
32
33#define DUMP_PROPERTYMAP_STATS 0
34#define DUMP_PROPERTYMAP_COLLISIONS 0
35
36#define PROPERTY_MAP_DELETED_ENTRY_KEY ((UniquedStringImpl*)1)
37
38namespace JSC {
39
40#if DUMP_PROPERTYMAP_STATS
41
42struct PropertyMapHashTableStats {
43 std::atomic<unsigned> numFinds;
44 std::atomic<unsigned> numCollisions;
45 std::atomic<unsigned> numLookups;
46 std::atomic<unsigned> numLookupProbing;
47 std::atomic<unsigned> numAdds;
48 std::atomic<unsigned> numRemoves;
49 std::atomic<unsigned> numRehashes;
50 std::atomic<unsigned> numReinserts;
51};
52
53JS_EXPORT_PRIVATE extern PropertyMapHashTableStats* propertyMapHashTableStats;
54
55#endif
56
57inline bool isPowerOf2(unsigned v)
58{
59 return hasOneBitSet(v);
60}
61
62inline unsigned nextPowerOf2(unsigned v)
63{
64 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
65 // Devised by Sean Anderson, Sepember 14, 2001
66
67 v--;
68 v |= v >> 1;
69 v |= v >> 2;
70 v |= v >> 4;
71 v |= v >> 8;
72 v |= v >> 16;
73 v++;
74
75 return v;
76}
77
78class PropertyTable final : public JSCell {
79
80 // This is the implementation for 'iterator' and 'const_iterator',
81 // used for iterating over the table in insertion order.
82 template<typename T>
83 class ordered_iterator {
84 public:
85 ordered_iterator<T>& operator++()
86 {
87 m_valuePtr = skipDeletedEntries(m_valuePtr + 1, m_endValuePtr);
88 return *this;
89 }
90
91 bool operator==(const ordered_iterator<T>& other)
92 {
93 return m_valuePtr == other.m_valuePtr;
94 }
95
96 bool operator!=(const ordered_iterator<T>& other)
97 {
98 return m_valuePtr != other.m_valuePtr;
99 }
100
101 T& operator*()
102 {
103 return *m_valuePtr;
104 }
105
106 T* operator->()
107 {
108 return m_valuePtr;
109 }
110
111 ordered_iterator(T* valuePtr, T* endValuePtr)
112 : m_valuePtr(valuePtr)
113 , m_endValuePtr(endValuePtr)
114 {
115 }
116
117 private:
118 T* m_valuePtr;
119 T* m_endValuePtr;
120 };
121
122public:
123 typedef JSCell Base;
124 static constexpr unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal;
125
126 template<typename CellType, SubspaceAccess>
127 static IsoSubspace* subspaceFor(VM& vm)
128 {
129 return &vm.propertyTableSpace;
130 }
131
132 static constexpr bool needsDestruction = true;
133 static void destroy(JSCell*);
134
135 DECLARE_EXPORT_INFO;
136
137 static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
138 {
139 return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
140 }
141
142 typedef UniquedStringImpl* KeyType;
143 typedef PropertyMapEntry ValueType;
144
145 // The in order iterator provides overloaded * and -> to access the Value at the current position.
146 typedef ordered_iterator<ValueType> iterator;
147 typedef ordered_iterator<const ValueType> const_iterator;
148
149 // The find_iterator is a pair of a pointer to a Value* an the entry in the index.
150 // If 'find' does not find an entry then iter.first will be 0, and iter.second will
151 // give the point in m_index where an entry should be inserted.
152 typedef std::pair<ValueType*, unsigned> find_iterator;
153
154 // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
155 static PropertyTable* create(VM&, unsigned initialCapacity);
156 static PropertyTable* clone(VM&, const PropertyTable&);
157 static PropertyTable* clone(VM&, unsigned initialCapacity, const PropertyTable&);
158 ~PropertyTable();
159
160 // Ordered iteration methods.
161 iterator begin();
162 iterator end();
163 const_iterator begin() const;
164 const_iterator end() const;
165
166 // Find a value in the table.
167 find_iterator find(const KeyType&);
168 ValueType* get(const KeyType&);
169 // Add a value to the table
170 enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
171 std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
172 // Remove a value from the table.
173 void remove(const find_iterator& iter);
174 void remove(const KeyType& key);
175
176 // Returns the number of values in the hashtable.
177 unsigned size() const;
178
179 // Checks if there are any values in the hashtable.
180 bool isEmpty() const;
181
182 // Number of slots in the property storage array in use, included deletedOffsets.
183 unsigned propertyStorageSize() const;
184
185 // Used to maintain a list of unused entries in the property storage.
186 void clearDeletedOffsets();
187 bool hasDeletedOffset();
188 PropertyOffset getDeletedOffset();
189 void addDeletedOffset(PropertyOffset);
190
191 PropertyOffset nextOffset(PropertyOffset inlineCapacity);
192
193 // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
194 PropertyTable* copy(VM&, unsigned newCapacity);
195
196#ifndef NDEBUG
197 size_t sizeInMemory();
198 void checkConsistency();
199#endif
200
201 static ptrdiff_t offsetOfIndexSize() { return OBJECT_OFFSETOF(PropertyTable, m_indexSize); }
202 static ptrdiff_t offsetOfIndexMask() { return OBJECT_OFFSETOF(PropertyTable, m_indexMask); }
203 static ptrdiff_t offsetOfIndex() { return OBJECT_OFFSETOF(PropertyTable, m_index); }
204
205 static constexpr unsigned EmptyEntryIndex = 0;
206
207private:
208 PropertyTable(VM&, unsigned initialCapacity);
209 PropertyTable(VM&, const PropertyTable&);
210 PropertyTable(VM&, unsigned initialCapacity, const PropertyTable&);
211
212 PropertyTable(const PropertyTable&);
213 // Used to insert a value known not to be in the table, and where we know capacity to be available.
214 void reinsert(const ValueType& entry);
215
216 // Rehash the table. Used to grow, or to recover deleted slots.
217 void rehash(unsigned newCapacity);
218
219 // The capacity of the table of values is half of the size of the index.
220 unsigned tableCapacity() const;
221
222 // We keep an extra deleted slot after the array to make iteration work,
223 // and to use for deleted values. Index values into the array are 1-based,
224 // so this is tableCapacity() + 1.
225 // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
226 // values array is actually 9 long (the 9th used for the deleted value/
227 // iteration guard). The 8 valid entries are numbered 1..8, so the
228 // deleted index is 9 (0 being reserved for empty).
229 unsigned deletedEntryIndex() const;
230
231 // Used in iterator creation/progression.
232 template<typename T>
233 static T* skipDeletedEntries(T* valuePtr, T* endValuePtr);
234
235 // The table of values lies after the hash index.
236 ValueType* table();
237 const ValueType* table() const;
238
239 ValueType* tableEnd() { return table() + usedCount(); }
240 const ValueType* tableEnd() const { return table() + usedCount(); }
241
242 // total number of used entries in the values array - by either valid entries, or deleted ones.
243 unsigned usedCount() const;
244
245 // The size in bytes of data needed for by the table.
246 size_t dataSize();
247
248 // Calculates the appropriate table size (rounds up to a power of two).
249 static unsigned sizeForCapacity(unsigned capacity);
250
251 // Check if capacity is available.
252 bool canInsert();
253
254 unsigned m_indexSize;
255 unsigned m_indexMask;
256 unsigned* m_index;
257 unsigned m_keyCount;
258 unsigned m_deletedCount;
259 std::unique_ptr<Vector<PropertyOffset>> m_deletedOffsets;
260
261 static constexpr unsigned MinimumTableSize = 16;
262};
263
264inline PropertyTable::iterator PropertyTable::begin()
265{
266 auto* tableEnd = this->tableEnd();
267 return iterator(skipDeletedEntries(table(), tableEnd), tableEnd);
268}
269
270inline PropertyTable::iterator PropertyTable::end()
271{
272 auto* tableEnd = this->tableEnd();
273 return iterator(tableEnd, tableEnd);
274}
275
276inline PropertyTable::const_iterator PropertyTable::begin() const
277{
278 auto* tableEnd = this->tableEnd();
279 return const_iterator(skipDeletedEntries(table(), tableEnd), tableEnd);
280}
281
282inline PropertyTable::const_iterator PropertyTable::end() const
283{
284 auto* tableEnd = this->tableEnd();
285 return const_iterator(tableEnd, tableEnd);
286}
287
288inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
289{
290 ASSERT(key);
291 ASSERT(key->isAtom() || key->isSymbol());
292 unsigned hash = IdentifierRepHash::hash(key);
293
294#if DUMP_PROPERTYMAP_STATS
295 ++propertyMapHashTableStats->numFinds;
296#endif
297
298 while (true) {
299 unsigned entryIndex = m_index[hash & m_indexMask];
300 if (entryIndex == EmptyEntryIndex)
301 return std::make_pair((ValueType*)0, hash & m_indexMask);
302 if (key == table()[entryIndex - 1].key)
303 return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
304
305#if DUMP_PROPERTYMAP_STATS
306 ++propertyMapHashTableStats->numCollisions;
307#endif
308
309#if DUMP_PROPERTYMAP_COLLISIONS
310 dataLog("PropertyTable collision for ", key, " (", hash, ")\n");
311 dataLog("Collided with ", table()[entryIndex - 1].key, "(", IdentifierRepHash::hash(table()[entryIndex - 1].key), ")\n");
312#endif
313
314 hash++;
315 }
316}
317
318inline PropertyTable::ValueType* PropertyTable::get(const KeyType& key)
319{
320 ASSERT(key);
321 ASSERT(key->isAtom() || key->isSymbol());
322
323 if (!m_keyCount)
324 return nullptr;
325
326 unsigned hash = IdentifierRepHash::hash(key);
327
328#if DUMP_PROPERTYMAP_STATS
329 ++propertyMapHashTableStats->numLookups;
330#endif
331
332 while (true) {
333 unsigned entryIndex = m_index[hash & m_indexMask];
334 if (entryIndex == EmptyEntryIndex)
335 return nullptr;
336 if (key == table()[entryIndex - 1].key)
337 return &table()[entryIndex - 1];
338
339#if DUMP_PROPERTYMAP_STATS
340 ++propertyMapHashTableStats->numLookupProbing;
341#endif
342
343 hash++;
344 }
345}
346
347inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
348{
349 // Look for a value with a matching key already in the array.
350 find_iterator iter = find(entry.key);
351 if (iter.first) {
352 RELEASE_ASSERT(iter.first->offset <= offset);
353 return std::make_pair(iter, false);
354 }
355
356#if DUMP_PROPERTYMAP_STATS
357 ++propertyMapHashTableStats->numAdds;
358#endif
359
360 // Ref the key
361 entry.key->ref();
362
363 // ensure capacity is available.
364 if (!canInsert()) {
365 rehash(m_keyCount + 1);
366 iter = find(entry.key);
367 ASSERT(!iter.first);
368 }
369
370 // Allocate a slot in the hashtable, and set the index to reference this.
371 unsigned entryIndex = usedCount() + 1;
372 m_index[iter.second] = entryIndex;
373 iter.first = &table()[entryIndex - 1];
374 *iter.first = entry;
375
376 ++m_keyCount;
377
378 if (offsetEffect == PropertyOffsetMayChange)
379 offset = std::max(offset, entry.offset);
380 else
381 RELEASE_ASSERT(offset >= entry.offset);
382
383 return std::make_pair(iter, true);
384}
385
386inline void PropertyTable::remove(const find_iterator& iter)
387{
388 // Removing a key that doesn't exist does nothing!
389 if (!iter.first)
390 return;
391
392#if DUMP_PROPERTYMAP_STATS
393 ++propertyMapHashTableStats->numRemoves;
394#endif
395
396 // Replace this one element with the deleted sentinel. Also clear out
397 // the entry so we can iterate all the entries as needed.
398 m_index[iter.second] = deletedEntryIndex();
399 iter.first->key->deref();
400 iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
401
402 ASSERT(m_keyCount >= 1);
403 --m_keyCount;
404 ++m_deletedCount;
405
406 if (m_deletedCount * 4 >= m_indexSize)
407 rehash(m_keyCount);
408}
409
410inline void PropertyTable::remove(const KeyType& key)
411{
412 remove(find(key));
413}
414
415// returns the number of values in the hashtable.
416inline unsigned PropertyTable::size() const
417{
418 return m_keyCount;
419}
420
421inline bool PropertyTable::isEmpty() const
422{
423 return !m_keyCount;
424}
425
426inline unsigned PropertyTable::propertyStorageSize() const
427{
428 return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
429}
430
431inline void PropertyTable::clearDeletedOffsets()
432{
433 m_deletedOffsets = nullptr;
434}
435
436inline bool PropertyTable::hasDeletedOffset()
437{
438 return m_deletedOffsets && !m_deletedOffsets->isEmpty();
439}
440
441inline PropertyOffset PropertyTable::getDeletedOffset()
442{
443 PropertyOffset offset = m_deletedOffsets->last();
444 m_deletedOffsets->removeLast();
445 return offset;
446}
447
448inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
449{
450 if (!m_deletedOffsets)
451 m_deletedOffsets = makeUnique<Vector<PropertyOffset>>();
452 m_deletedOffsets->append(offset);
453}
454
455inline PropertyOffset PropertyTable::nextOffset(PropertyOffset inlineCapacity)
456{
457 if (hasDeletedOffset())
458 return getDeletedOffset();
459
460 return offsetForPropertyNumber(size(), inlineCapacity);
461}
462
463inline PropertyTable* PropertyTable::copy(VM& vm, unsigned newCapacity)
464{
465 ASSERT(newCapacity >= m_keyCount);
466
467 // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
468 // save rehashing all keys.
469 if (sizeForCapacity(newCapacity) == m_indexSize)
470 return PropertyTable::clone(vm, *this);
471 return PropertyTable::clone(vm, newCapacity, *this);
472}
473
474#ifndef NDEBUG
475inline size_t PropertyTable::sizeInMemory()
476{
477 size_t result = sizeof(PropertyTable) + dataSize();
478 if (m_deletedOffsets)
479 result += (m_deletedOffsets->capacity() * sizeof(PropertyOffset));
480 return result;
481}
482#endif
483
484inline void PropertyTable::reinsert(const ValueType& entry)
485{
486#if DUMP_PROPERTYMAP_STATS
487 ++propertyMapHashTableStats->numReinserts;
488#endif
489
490 // Used to insert a value known not to be in the table, and where
491 // we know capacity to be available.
492 ASSERT(canInsert());
493 find_iterator iter = find(entry.key);
494 ASSERT(!iter.first);
495
496 unsigned entryIndex = usedCount() + 1;
497 m_index[iter.second] = entryIndex;
498 table()[entryIndex - 1] = entry;
499
500 ++m_keyCount;
501}
502
503inline void PropertyTable::rehash(unsigned newCapacity)
504{
505#if DUMP_PROPERTYMAP_STATS
506 ++propertyMapHashTableStats->numRehashes;
507#endif
508
509 unsigned* oldEntryIndices = m_index;
510 iterator iter = this->begin();
511 iterator end = this->end();
512
513 m_indexSize = sizeForCapacity(newCapacity);
514 m_indexMask = m_indexSize - 1;
515 m_keyCount = 0;
516 m_deletedCount = 0;
517 m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
518
519 for (; iter != end; ++iter) {
520 ASSERT(canInsert());
521 reinsert(*iter);
522 }
523
524 fastFree(oldEntryIndices);
525}
526
527inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
528
529inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
530
531template<typename T>
532inline T* PropertyTable::skipDeletedEntries(T* valuePtr, T* endValuePtr)
533{
534 while (valuePtr < endValuePtr && valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
535 ++valuePtr;
536 return valuePtr;
537}
538
539inline PropertyTable::ValueType* PropertyTable::table()
540{
541 // The table of values lies after the hash index.
542 return reinterpret_cast<ValueType*>(m_index + m_indexSize);
543}
544
545inline const PropertyTable::ValueType* PropertyTable::table() const
546{
547 // The table of values lies after the hash index.
548 return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
549}
550
551inline unsigned PropertyTable::usedCount() const
552{
553 // Total number of used entries in the values array - by either valid entries, or deleted ones.
554 return m_keyCount + m_deletedCount;
555}
556
557inline size_t PropertyTable::dataSize()
558{
559 // The size in bytes of data needed for by the table.
560 return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
561}
562
563inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
564{
565 if (capacity < MinimumTableSize / 2)
566 return MinimumTableSize;
567 return nextPowerOf2(capacity + 1) * 2;
568}
569
570inline bool PropertyTable::canInsert()
571{
572 return usedCount() < tableCapacity();
573}
574
575} // namespace JSC
576