1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef vm_PropMap_h
8 #define vm_PropMap_h
9
10 #include "mozilla/Array.h"
11 #include "mozilla/Maybe.h"
12
13 #include "gc/Barrier.h"
14 #include "gc/Cell.h"
15 #include "js/TypeDecls.h"
16 #include "js/UbiNode.h"
17 #include "vm/JSAtom.h"
18 #include "vm/ObjectFlags.h"
19 #include "vm/PropertyInfo.h"
20 #include "vm/PropertyKey.h"
21 #include "vm/SymbolType.h"
22
23 // [SMDOC] Property Maps
24 //
25 // Property maps are used to store information about native object properties.
26 // Each property map represents an ordered list of (PropertyKey, PropertyInfo)
27 // tuples.
28 //
29 // Each property map can store up to 8 properties (see PropMap::Capacity). To
30 // store more than eight properties, multiple maps must be linked together with
31 // the |previous| pointer.
32 //
33 // Shapes and Property Maps
34 // ------------------------
35 // Native object shapes represent property information as a (PropMap*, length)
36 // tuple. When there are no properties yet, the shape's map will be nullptr and
37 // the length is zero.
38 //
39 // For example, consider the following objects:
40 //
41 // o1 = {x: 1, y: 2}
42 // o2 = {x: 3, y: 4, z: 5}
43 //
44 // This is stored as follows:
45 //
46 // +-------------+ +--------------+ +-------------------+
47 // | JSObject o1 | | Shape S1 | | PropMap M1 |
48 // |-------------+ +--------------+ +-------------------+
49 // | shape: S1 -+---> | map: M1 -+--+> | key 0: x (slot 0) |
50 // | slot 0: 1 | | mapLength: 2 | | | key 1: y (slot 1) |
51 // | slot 1: 2 | +--------------+ | | key 2: z (slot 2) |
52 // +-------------+ | | ... |
53 // | +-------------------+
54 // |
55 // +-------------+ +--------------+ |
56 // | JSObject o2 | | Shape S2 | |
57 // |-------------+ +--------------+ |
58 // | shape: S2 -+---> | map: M1 -+--+
59 // | slot 0: 3 | | mapLength: 3 |
60 // | slot 1: 4 | +--------------+
61 // | slot 2: 5 |
62 // +-------------+
63 //
64 // There's a single map M1 shared by shapes S1 and S2. Shape S1 includes only
65 // the first two properties and shape S2 includes all three properties.
66 //
67 // Class Hierarchy
68 // ---------------
69 // Property maps have the following C++ class hierarchy:
70 //
71 // PropMap (abstract)
72 // |
73 // +-- SharedPropMap (abstract)
74 // | |
75 // | +-- CompactPropMap
76 // | |
77 // | +-- NormalPropMap
78 // |
79 // +-- DictionaryPropMap
80 //
81 // * PropMap: base class. It has a flags word and an array of PropertyKeys.
82 //
83 // * SharedPropMap: base class for all shared property maps. See below for more
84 // information on shared maps.
85 //
86 // * CompactPropMap: a shared map that stores its information more compactly
87 // than the other maps. It saves four words by not storing a
88 // PropMapTable, previous pointer, and by using a more compact
89 // PropertyInfo type for slot numbers that fit in one byte.
90 //
91 // * NormalPropMap: a shared map, used when CompactPropMap can't be used.
92 //
93 // * DictionaryPropMap: an unshared map (used by a single object/shape). See
94 // below for more information on dictionary maps.
95 //
96 // Secondary hierarchy
97 // -------------------
98 // NormalPropMap and DictionaryPropMap store property information in the same
99 // way. This means property lookups don't have to distinguish between these two
100 // types. This is represented with a second class hierarchy:
101 //
102 // PropMap (abstract)
103 // |
104 // +-- CompactPropMap
105 // |
106 // +-- LinkedPropMap (NormalPropMap or DictionaryPropMap)
107 //
108 // Property lookup and property iteration are very performance sensitive and use
109 // this Compact vs Linked "view" so that they don't have to handle the three map
110 // types separately.
111 //
112 // LinkedPropMap also stores the PropMapTable and a pointer to the |previous|
113 // map. Compact maps don't have these fields.
114 //
115 // To summarize these map types:
116 //
117 // +-------------------+-------------+--------+
118 // | Concrete type | Shared/tree | Linked |
119 // +-------------------+-------------+--------+
120 // | CompactPropMap | yes | no |
121 // | NormalPropMap | yes | yes |
122 // | DictionaryPropMap | no | yes |
123 // +-------------------+-------------+--------+
124 //
125 // PropMapTable
126 // ------------
127 // Finding the PropertyInfo for a particular PropertyKey requires a linear
128 // search if the map is small. For larger maps we can create a PropMapTable, a
129 // hash table that maps from PropertyKey to PropMap + index, to speed up
130 // property lookups.
131 //
132 // To save memory, property map tables can be discarded on GC and recreated when
133 // needed. AutoKeepPropMapTables can be used to avoid discarding tables in a
134 // particular zone. Methods to access a PropMapTable take either an
135 // AutoCheckCannotGC or AutoKeepPropMapTables argument, to help ensure tables
136 // are not purged while we're using them.
137 //
138 // Shared Property Maps
139 // --------------------
140 // Shared property maps can be shared per-Zone by objects with the same property
141 // keys, flags, and slot numbers. To make this work, shared maps form a tree:
142 //
143 // - Each Zone has a table that maps from first PropertyKey + PropertyInfo to
144 // a SharedPropMap that begins with that property. This is used to lookup the
145 // the map to use when adding the first property.
146 // See ShapeZone::initialPropMaps.
147 //
148 // - When adding a property other than the first one, the property is stored in
149 // the next entry of the same map when possible. If the map is full or the
150 // next entry already stores a different property, a child map is created and
151 // linked to the parent map.
152 //
153 // For example, imagine we want to create these objects:
154 //
155 // o1 = {x: 1, y: 2, z: 3}
156 // o2 = {x: 1, y: 2, foo: 4}
157 //
158 // This will result in the following maps being created:
159 //
160 // +---------------------+ +---------------------+
161 // | SharedPropMap M1 | | SharedPropMap M2 |
162 // +---------------------+ +---------------------+
163 // | Child M2 (index 1) -+--> | Parent M1 (index 1) |
164 // +---------------------+ +---------------------+
165 // | 0: x | | 0: x |
166 // | 1: y | | 1: y |
167 // | 2: z | | 2: foo |
168 // | ... | | ... |
169 // +---------------------+ +---------------------+
170 //
171 // M1 is the map used for initial property "x". Properties "y" and "z" can be
172 // stored inline. When later adding "foo" following "y", the map has to be
173 // forked: a child map M2 is created and M1 remembers this transition at
174 // property index 1 so that M2 will be used the next time properties "x", "y",
175 // and "foo" are added to an object.
176 //
177 // Shared maps contain a TreeData struct that stores the parent and children
178 // links for the SharedPropMap tree. The parent link is a tagged pointer that
179 // stores both the parent map and the property index of the last used property
180 // in the parent map before the branch. The children are stored similarly: the
181 // parent map can store a single child map and index, or a set of children.
182 // See SharedChildrenPtr.
183 //
184 // Looking up a child map can then be done based on the index of the last
185 // property in the parent map and the new property's key and flags. So for the
186 // example above, the lookup key for M1 => M2 is (index 1, "foo", <flags>).
187 //
188 // Note: shared maps can have both a |previous| map and a |parent| map. They are
189 // equal when the previous map was full, but can be different maps when
190 // branching in the middle of a map like in the example above: M2 has parent M1
191 // but does not have a |previous| map (because it only has three properties).
192 //
193 // Dictionary Property Maps
194 // ------------------------
195 // Certain operations can't be implemented (efficiently) for shared property
196 // maps, for example changing or deleting a property other than the last one.
197 // When this happens the map is copied as a DictionaryPropMap.
198 //
199 // Dictionary maps are unshared so can be mutated in place (after generating a
200 // new shape for the object).
201 //
202 // Unlike shared maps, dictionary maps can have holes between two property keys
203 // after removing a property. When there are more holes than properties, the
204 // map is compacted. See DictionaryPropMap::maybeCompact.
205
206 namespace js {
207
208 enum class IntegrityLevel;
209
210 class DictionaryPropMap;
211 class SharedPropMap;
212 class LinkedPropMap;
213 class CompactPropMap;
214 class NormalPropMap;
215
216 // Template class for storing a PropMap* and a property index as tagged pointer.
217 template <typename T>
218 class MapAndIndex {
219 uintptr_t data_ = 0;
220
221 static constexpr uintptr_t IndexMask = 0b111;
222
223 public:
224 MapAndIndex() = default;
225
MapAndIndex(const T * map,uint32_t index)226 MapAndIndex(const T* map, uint32_t index) : data_(uintptr_t(map) | index) {
227 MOZ_ASSERT((uintptr_t(map) & IndexMask) == 0);
228 MOZ_ASSERT(index <= IndexMask);
229 }
MapAndIndex(uintptr_t data)230 explicit MapAndIndex(uintptr_t data) : data_(data) {}
231
setNone()232 void setNone() { data_ = 0; }
233
isNone()234 bool isNone() const { return data_ == 0; }
235
raw()236 uintptr_t raw() const { return data_; }
maybeMap()237 T* maybeMap() const { return reinterpret_cast<T*>(data_ & ~IndexMask); }
238
index()239 uint32_t index() const {
240 MOZ_ASSERT(!isNone());
241 return data_ & IndexMask;
242 }
map()243 T* map() const {
244 MOZ_ASSERT(!isNone());
245 return maybeMap();
246 }
247
248 inline PropertyInfo propertyInfo() const;
249
250 bool operator==(const MapAndIndex<T>& other) const {
251 return data_ == other.data_;
252 }
253 bool operator!=(const MapAndIndex<T>& other) const {
254 return !operator==(other);
255 }
256 } JS_HAZ_GC_POINTER;
257 using PropMapAndIndex = MapAndIndex<PropMap>;
258 using SharedPropMapAndIndex = MapAndIndex<SharedPropMap>;
259
260 struct SharedChildrenHasher;
261 using SharedChildrenSet =
262 HashSet<SharedPropMapAndIndex, SharedChildrenHasher, SystemAllocPolicy>;
263
264 // Children of shared maps. This is either:
265 //
266 // - None (no children)
267 // - SingleMapAndIndex (one child map, including the property index of the last
268 // property before the branch)
269 // - SharedChildrenSet (multiple children)
270 //
271 // Because SingleMapAndIndex use all bits, this relies on the HasChildrenSet
272 // flag in the map to distinguish the latter two cases.
273 class SharedChildrenPtr {
274 uintptr_t data_ = 0;
275
276 public:
isNone()277 bool isNone() const { return data_ == 0; }
setNone()278 void setNone() { data_ = 0; }
279
setSingleChild(SharedPropMapAndIndex child)280 void setSingleChild(SharedPropMapAndIndex child) { data_ = child.raw(); }
setChildrenSet(SharedChildrenSet * set)281 void setChildrenSet(SharedChildrenSet* set) { data_ = uintptr_t(set); }
282
toSingleChild()283 SharedPropMapAndIndex toSingleChild() const {
284 MOZ_ASSERT(!isNone());
285 return SharedPropMapAndIndex(data_);
286 }
287
toChildrenSet()288 SharedChildrenSet* toChildrenSet() const {
289 MOZ_ASSERT(!isNone());
290 return reinterpret_cast<SharedChildrenSet*>(data_);
291 }
292 } JS_HAZ_GC_POINTER;
293
294 // Ensures no property map tables are purged in the current zone.
295 class MOZ_RAII AutoKeepPropMapTables {
296 JSContext* cx_;
297 bool prev_;
298
299 public:
300 void operator=(const AutoKeepPropMapTables&) = delete;
301 AutoKeepPropMapTables(const AutoKeepPropMapTables&) = delete;
302 explicit inline AutoKeepPropMapTables(JSContext* cx);
303 inline ~AutoKeepPropMapTables();
304 };
305
306 // Hash table to optimize property lookups on larger maps. This maps from
307 // PropertyKey to PropMapAndIndex.
308 class PropMapTable {
309 struct Hasher {
310 using Key = PropMapAndIndex;
311 using Lookup = PropertyKey;
312 static MOZ_ALWAYS_INLINE HashNumber hash(PropertyKey key);
313 static MOZ_ALWAYS_INLINE bool match(PropMapAndIndex, PropertyKey key);
314 };
315
316 // Small lookup cache. This has a hit rate of 30-60% on most workloads and is
317 // a lot faster than the full HashSet lookup.
318 struct CacheEntry {
319 PropertyKey key;
320 PropMapAndIndex result;
321 };
322 static constexpr uint32_t NumCacheEntries = 2;
323 CacheEntry cacheEntries_[NumCacheEntries];
324
325 using Set = HashSet<PropMapAndIndex, Hasher, SystemAllocPolicy>;
326 Set set_;
327
setCacheEntry(PropertyKey key,PropMapAndIndex entry)328 void setCacheEntry(PropertyKey key, PropMapAndIndex entry) {
329 for (uint32_t i = 0; i < NumCacheEntries; i++) {
330 if (cacheEntries_[i].key == key) {
331 cacheEntries_[i].result = entry;
332 return;
333 }
334 }
335 }
lookupInCache(PropertyKey key,PropMapAndIndex * result)336 bool lookupInCache(PropertyKey key, PropMapAndIndex* result) const {
337 for (uint32_t i = 0; i < NumCacheEntries; i++) {
338 if (cacheEntries_[i].key == key) {
339 *result = cacheEntries_[i].result;
340 #ifdef DEBUG
341 auto p = lookupRaw(key);
342 MOZ_ASSERT(*result == (p ? *p : PropMapAndIndex()));
343 #endif
344 return true;
345 }
346 }
347 return false;
348 }
addToCache(PropertyKey key,Set::Ptr p)349 void addToCache(PropertyKey key, Set::Ptr p) {
350 for (uint32_t i = NumCacheEntries - 1; i > 0; i--) {
351 cacheEntries_[i] = cacheEntries_[i - 1];
352 MOZ_ASSERT(cacheEntries_[i].key != key);
353 }
354 cacheEntries_[0].key = key;
355 cacheEntries_[0].result = p ? *p : PropMapAndIndex();
356 }
357
358 public:
359 using Ptr = Set::Ptr;
360
361 PropMapTable() = default;
362 ~PropMapTable() = default;
363
entryCount()364 uint32_t entryCount() const { return set_.count(); }
365
366 // This counts the PropMapTable object itself (which must be heap-allocated)
367 // and its HashSet.
sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf)368 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
369 return mallocSizeOf(this) + set_.shallowSizeOfExcludingThis(mallocSizeOf);
370 }
371
372 // init() is fallible and reports OOM to the context.
373 bool init(JSContext* cx, LinkedPropMap* map);
374
375 MOZ_ALWAYS_INLINE PropMap* lookup(PropMap* map, uint32_t mapLength,
376 PropertyKey key, uint32_t* index);
377
lookupRaw(PropertyKey key)378 Set::Ptr lookupRaw(PropertyKey key) const { return set_.lookup(key); }
379
add(JSContext * cx,PropertyKey key,PropMapAndIndex entry)380 bool add(JSContext* cx, PropertyKey key, PropMapAndIndex entry) {
381 if (!set_.putNew(key, entry)) {
382 ReportOutOfMemory(cx);
383 return false;
384 }
385 setCacheEntry(key, entry);
386 return true;
387 }
388
purgeCache()389 void purgeCache() {
390 for (uint32_t i = 0; i < NumCacheEntries; i++) {
391 cacheEntries_[i] = CacheEntry();
392 }
393 }
394
remove(Ptr ptr)395 void remove(Ptr ptr) {
396 set_.remove(ptr);
397 purgeCache();
398 }
399
replaceEntry(Ptr ptr,PropertyKey key,PropMapAndIndex newEntry)400 void replaceEntry(Ptr ptr, PropertyKey key, PropMapAndIndex newEntry) {
401 MOZ_ASSERT(*ptr != newEntry);
402 set_.replaceKey(ptr, key, newEntry);
403 setCacheEntry(key, newEntry);
404 }
405
406 void trace(JSTracer* trc);
407 #ifdef JSGC_HASH_TABLE_CHECKS
408 void checkAfterMovingGC();
409 #endif
410 };
411
412 class PropMap : public gc::TenuredCellWithFlags {
413 public:
414 // Number of properties that can be stored in each map. This must be small
415 // enough so that every index fits in a tagged PropMap* pointer (MapAndIndex).
416 static constexpr size_t Capacity = 8;
417
418 protected:
419 static_assert(gc::CellFlagBitsReservedForGC == 3,
420 "PropMap must reserve enough bits for Cell");
421
422 enum Flags {
423 // Set if this is a CompactPropMap.
424 IsCompactFlag = 1 << 3,
425
426 // Set if this map has a non-null previous map pointer. Never set for
427 // compact maps because they don't have a previous field.
428 HasPrevFlag = 1 << 4,
429
430 // Set if this is a DictionaryPropMap.
431 IsDictionaryFlag = 1 << 5,
432
433 // Set if this map can have a table. Never set for compact maps. Always set
434 // for dictionary maps.
435 CanHaveTableFlag = 1 << 6,
436
437 // If set, this SharedPropMap has a SharedChildrenSet. Else it either has no
438 // children or a single child. See SharedChildrenPtr. Never set for
439 // dictionary maps.
440 HasChildrenSetFlag = 1 << 7,
441
442 // If set, this SharedPropMap was once converted to dictionary mode. This is
443 // only used for heuristics. Never set for dictionary maps.
444 HadDictionaryConversionFlag = 1 << 8,
445
446 // For SharedPropMap this stores the number of previous maps, clamped to
447 // NumPreviousMapsMax. This is used for heuristics.
448 NumPreviousMapsMax = 0x7f,
449 NumPreviousMapsShift = 9,
450 NumPreviousMapsMask = NumPreviousMapsMax << NumPreviousMapsShift,
451 };
452
453 // Flags word, stored in the cell header. Note that this hides the
454 // Cell::flags() method.
flags()455 uintptr_t flags() const { return headerFlagsField(); }
456
457 mozilla::Array<GCPtr<PropertyKey>, Capacity> keys_;
458
459 PropMap() = default;
460
461 public:
isCompact()462 bool isCompact() const { return flags() & IsCompactFlag; }
isLinked()463 bool isLinked() const { return !isCompact(); }
isDictionary()464 bool isDictionary() const { return flags() & IsDictionaryFlag; }
isShared()465 bool isShared() const { return !isDictionary(); }
isNormal()466 bool isNormal() const { return isShared() && !isCompact(); }
467
hasPrevious()468 bool hasPrevious() const { return flags() & HasPrevFlag; }
canHaveTable()469 bool canHaveTable() const { return flags() & CanHaveTableFlag; }
470
471 inline CompactPropMap* asCompact();
472 inline const CompactPropMap* asCompact() const;
473
474 inline LinkedPropMap* asLinked();
475 inline const LinkedPropMap* asLinked() const;
476
477 inline NormalPropMap* asNormal();
478 inline const NormalPropMap* asNormal() const;
479
480 inline SharedPropMap* asShared();
481 inline const SharedPropMap* asShared() const;
482
483 inline DictionaryPropMap* asDictionary();
484 inline const DictionaryPropMap* asDictionary() const;
485
hasKey(uint32_t index)486 bool hasKey(uint32_t index) const { return !keys_[index].isVoid(); }
getKey(uint32_t index)487 PropertyKey getKey(uint32_t index) const { return keys_[index]; }
488
489 uint32_t approximateEntryCount() const;
490
491 #ifdef DEBUG
492 void dump(js::GenericPrinter& out) const;
493 void dump() const;
494 void checkConsistency(NativeObject* obj) const;
495 #endif
496
497 void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
498 size_t* children, size_t* tables) const;
499
500 inline PropertyInfo getPropertyInfo(uint32_t index) const;
501
getPropertyInfoWithKey(uint32_t index)502 PropertyInfoWithKey getPropertyInfoWithKey(uint32_t index) const {
503 return PropertyInfoWithKey(getPropertyInfo(index), getKey(index));
504 }
505
506 MOZ_ALWAYS_INLINE PropMap* lookupLinear(uint32_t mapLength, PropertyKey key,
507 uint32_t* index);
508
509 MOZ_ALWAYS_INLINE PropMap* lookupPure(uint32_t mapLength, PropertyKey key,
510 uint32_t* index);
511
512 MOZ_ALWAYS_INLINE PropMap* lookup(JSContext* cx, uint32_t mapLength,
513 PropertyKey key, uint32_t* index);
514
515 static inline bool lookupForRemove(JSContext* cx, PropMap* map,
516 uint32_t mapLength, PropertyKey key,
517 const AutoKeepPropMapTables& keep,
518 PropMap** propMap, uint32_t* propIndex,
519 PropMapTable** table,
520 PropMapTable::Ptr* ptr);
521
522 static const JS::TraceKind TraceKind = JS::TraceKind::PropMap;
523
524 void traceChildren(JSTracer* trc);
525 };
526
527 class SharedPropMap : public PropMap {
528 friend class PropMap;
529
530 protected:
531 // Shared maps are stored in a tree structure. Each shared map has a TreeData
532 // struct linking the map to its parent and children. Initial maps (the ones
533 // stored in ShapeZone's initialPropMaps table) don't have a parent.
534 struct TreeData {
535 SharedChildrenPtr children;
536 SharedPropMapAndIndex parent;
537
setParentTreeData538 void setParent(SharedPropMap* map, uint32_t index) {
539 parent = SharedPropMapAndIndex(map, index);
540 }
541 };
542
543 private:
544 static SharedPropMap* create(JSContext* cx, Handle<SharedPropMap*> prev,
545 HandleId id, PropertyInfo prop);
546 static SharedPropMap* createInitial(JSContext* cx, HandleId id,
547 PropertyInfo prop);
548 static SharedPropMap* clone(JSContext* cx, Handle<SharedPropMap*> map,
549 uint32_t length);
550
551 inline void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop);
552
553 static bool addPropertyInternal(JSContext* cx,
554 MutableHandle<SharedPropMap*> map,
555 uint32_t* mapLength, HandleId id,
556 PropertyInfo prop);
557
558 bool addChild(JSContext* cx, SharedPropMapAndIndex child, HandleId id,
559 PropertyInfo prop);
560 SharedPropMap* lookupChild(uint32_t length, HandleId id, PropertyInfo prop);
561
562 protected:
initNumPreviousMaps(uint32_t value)563 void initNumPreviousMaps(uint32_t value) {
564 MOZ_ASSERT((flags() >> NumPreviousMapsShift) == 0);
565 // Clamp to NumPreviousMapsMax. This is okay because this value is only used
566 // for heuristics.
567 if (value > NumPreviousMapsMax) {
568 value = NumPreviousMapsMax;
569 }
570 setHeaderFlagBits(value << NumPreviousMapsShift);
571 }
572
hasChildrenSet()573 bool hasChildrenSet() const { return flags() & HasChildrenSetFlag; }
setHasChildrenSet()574 void setHasChildrenSet() { setHeaderFlagBits(HasChildrenSetFlag); }
clearHasChildrenSet()575 void clearHasChildrenSet() { clearHeaderFlagBits(HasChildrenSetFlag); }
576
setHadDictionaryConversion()577 void setHadDictionaryConversion() {
578 setHeaderFlagBits(HadDictionaryConversionFlag);
579 }
580
581 public:
582 // Heuristics used when adding a property via NativeObject::addProperty and
583 // friends:
584 //
585 // * If numPreviousMaps >= NumPrevMapsForAddConsiderDictionary, consider
586 // converting the object to a dictionary object based on other heuristics.
587 //
588 // * If numPreviousMaps >= NumPrevMapsForAddAlwaysDictionary, always convert
589 // the object to a dictionary object.
590 static constexpr size_t NumPrevMapsConsiderDictionary = 32;
591 static constexpr size_t NumPrevMapsAlwaysDictionary = 100;
592
593 static_assert(NumPrevMapsConsiderDictionary < NumPreviousMapsMax);
594 static_assert(NumPrevMapsAlwaysDictionary < NumPreviousMapsMax);
595
596 // The number of properties that can definitely be added to an object without
597 // triggering dictionary mode conversion in NativeObject::addProperty.
598 static constexpr size_t MaxPropsForNonDictionary =
599 NumPrevMapsConsiderDictionary * Capacity;
600
601 bool isDictionary() const = delete;
602 bool isShared() const = delete;
603 SharedPropMap* asShared() = delete;
604 const SharedPropMap* asShared() const = delete;
605
hadDictionaryConversion()606 bool hadDictionaryConversion() const {
607 return flags() & HadDictionaryConversionFlag;
608 }
609
numPreviousMaps()610 uint32_t numPreviousMaps() const {
611 uint32_t val = (flags() & NumPreviousMapsMask) >> NumPreviousMapsShift;
612 MOZ_ASSERT_IF(hasPrevious(), val > 0);
613 return val;
614 }
615
616 MOZ_ALWAYS_INLINE bool shouldConvertToDictionaryForAdd() const;
617
618 void fixupAfterMovingGC();
619 inline void sweep(JSFreeOp* fop);
620 inline void finalize(JSFreeOp* fop);
621
622 static inline void getPrevious(MutableHandle<SharedPropMap*> map,
623 uint32_t* mapLength);
624
matchProperty(uint32_t index,PropertyKey key,PropertyInfo prop)625 bool matchProperty(uint32_t index, PropertyKey key, PropertyInfo prop) const {
626 return getKey(index) == key && getPropertyInfo(index) == prop;
627 }
628
629 inline TreeData& treeDataRef();
630 inline const TreeData& treeDataRef() const;
631
632 void removeChild(JSFreeOp* fop, SharedPropMap* child);
633
lastUsedSlot(uint32_t mapLength)634 uint32_t lastUsedSlot(uint32_t mapLength) const {
635 return getPropertyInfo(mapLength - 1).maybeSlot();
636 }
637
638 // Number of slots required for objects with this map/mapLength.
slotSpan(const JSClass * clasp,const SharedPropMap * map,uint32_t mapLength)639 static uint32_t slotSpan(const JSClass* clasp, const SharedPropMap* map,
640 uint32_t mapLength) {
641 MOZ_ASSERT(clasp->isNativeObject());
642 uint32_t numReserved = JSCLASS_RESERVED_SLOTS(clasp);
643 if (!map) {
644 MOZ_ASSERT(mapLength == 0);
645 return numReserved;
646 }
647 uint32_t lastSlot = map->lastUsedSlot(mapLength);
648 if (lastSlot == SHAPE_INVALID_SLOT) {
649 // The object only has custom data properties.
650 return numReserved;
651 }
652 // Some builtin objects store properties in reserved slots. Make sure the
653 // slot span >= numReserved. See addPropertyInReservedSlot.
654 return std::max(lastSlot + 1, numReserved);
655 }
656
indexOfNextProperty(uint32_t index)657 static uint32_t indexOfNextProperty(uint32_t index) {
658 MOZ_ASSERT(index < PropMap::Capacity);
659 return (index + 1) % PropMap::Capacity;
660 }
661
662 // Add a new property to this map. Returns the new map/mapLength, slot number,
663 // and object flags.
664 static bool addProperty(JSContext* cx, const JSClass* clasp,
665 MutableHandle<SharedPropMap*> map,
666 uint32_t* mapLength, HandleId id, PropertyFlags flags,
667 ObjectFlags* objectFlags, uint32_t* slot);
668
669 // Like addProperty, but for when the slot number is a reserved slot. A few
670 // builtin objects use this for initial properties.
671 static bool addPropertyInReservedSlot(JSContext* cx, const JSClass* clasp,
672 MutableHandle<SharedPropMap*> map,
673 uint32_t* mapLength, HandleId id,
674 PropertyFlags flags, uint32_t slot,
675 ObjectFlags* objectFlags);
676
677 // Like addProperty, but for when the caller already knows the slot number to
678 // use (or wants to assert this exact slot number is used).
679 static bool addPropertyWithKnownSlot(JSContext* cx, const JSClass* clasp,
680 MutableHandle<SharedPropMap*> map,
681 uint32_t* mapLength, HandleId id,
682 PropertyFlags flags, uint32_t slot,
683 ObjectFlags* objectFlags);
684
685 // Like addProperty, but for adding a custom data property.
686 static bool addCustomDataProperty(JSContext* cx, const JSClass* clasp,
687 MutableHandle<SharedPropMap*> map,
688 uint32_t* mapLength, HandleId id,
689 PropertyFlags flags,
690 ObjectFlags* objectFlags);
691
692 // Freeze or seal all properties by creating a new shared map. Returns the new
693 // map and object flags.
694 static bool freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
695 const JSClass* clasp,
696 MutableHandle<SharedPropMap*> map,
697 uint32_t mapLength,
698 ObjectFlags* objectFlags);
699
700 // Create a new dictionary map as copy of this map.
701 static DictionaryPropMap* toDictionaryMap(JSContext* cx,
702 Handle<SharedPropMap*> map,
703 uint32_t length);
704 };
705
706 class CompactPropMap final : public SharedPropMap {
707 mozilla::Array<CompactPropertyInfo, Capacity> propInfos_;
708 TreeData treeData_;
709
710 friend class PropMap;
711 friend class SharedPropMap;
712 friend class DictionaryPropMap;
713
CompactPropMap(PropertyKey key,PropertyInfo prop)714 CompactPropMap(PropertyKey key, PropertyInfo prop) {
715 setHeaderFlagBits(IsCompactFlag);
716 initProperty(0, key, prop);
717 }
718
CompactPropMap(CompactPropMap * orig,uint32_t length)719 CompactPropMap(CompactPropMap* orig, uint32_t length) {
720 setHeaderFlagBits(IsCompactFlag);
721 for (uint32_t i = 0; i < length; i++) {
722 keys_[i].init(orig->keys_[i]);
723 propInfos_[i] = orig->propInfos_[i];
724 }
725 }
726
initProperty(uint32_t index,PropertyKey key,PropertyInfo prop)727 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
728 MOZ_ASSERT(!hasKey(index));
729 keys_[index].init(key);
730 propInfos_[index] = CompactPropertyInfo(prop);
731 }
732
treeDataRef()733 TreeData& treeDataRef() { return treeData_; }
treeDataRef()734 const TreeData& treeDataRef() const { return treeData_; }
735
736 public:
737 bool isDictionary() const = delete;
738 bool isShared() const = delete;
739 bool isCompact() const = delete;
740 bool isNormal() const = delete;
741 bool isLinked() const = delete;
742 CompactPropMap* asCompact() = delete;
743 const CompactPropMap* asCompact() const = delete;
744
getPropertyInfo(uint32_t index)745 PropertyInfo getPropertyInfo(uint32_t index) const {
746 MOZ_ASSERT(hasKey(index));
747 return PropertyInfo(propInfos_[index]);
748 }
749 };
750
751 // Layout shared by NormalPropMap and DictionaryPropMap.
752 class LinkedPropMap final : public PropMap {
753 friend class PropMap;
754 friend class SharedPropMap;
755 friend class NormalPropMap;
756 friend class DictionaryPropMap;
757
758 struct Data {
759 GCPtr<PropMap*> previous;
760 PropMapTable* table = nullptr;
761 mozilla::Array<PropertyInfo, Capacity> propInfos;
762
DataData763 explicit Data(PropMap* prev) : previous(prev) {}
764 };
765 Data data_;
766
767 bool createTable(JSContext* cx);
768 void handOffTableTo(LinkedPropMap* next);
769
770 public:
771 bool isCompact() const = delete;
772 bool isLinked() const = delete;
773 LinkedPropMap* asLinked() = delete;
774 const LinkedPropMap* asLinked() const = delete;
775
previous()776 PropMap* previous() const { return data_.previous; }
777
hasTable()778 bool hasTable() const { return data_.table != nullptr; }
779
maybeTable(JS::AutoCheckCannotGC & nogc)780 PropMapTable* maybeTable(JS::AutoCheckCannotGC& nogc) const {
781 return data_.table;
782 }
ensureTable(JSContext * cx,const JS::AutoCheckCannotGC & nogc)783 PropMapTable* ensureTable(JSContext* cx, const JS::AutoCheckCannotGC& nogc) {
784 if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) {
785 return nullptr;
786 }
787 return data_.table;
788 }
ensureTable(JSContext * cx,const AutoKeepPropMapTables & keep)789 PropMapTable* ensureTable(JSContext* cx, const AutoKeepPropMapTables& keep) {
790 if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) {
791 return nullptr;
792 }
793 return data_.table;
794 }
795
796 void purgeTable(JSFreeOp* fop);
797
purgeTableCache()798 void purgeTableCache() {
799 if (data_.table) {
800 data_.table->purgeCache();
801 }
802 }
803
804 #ifdef DEBUG
805 bool canSkipMarkingTable();
806 #endif
807
getPropertyInfo(uint32_t index)808 PropertyInfo getPropertyInfo(uint32_t index) const {
809 MOZ_ASSERT(hasKey(index));
810 return data_.propInfos[index];
811 }
812 };
813
814 class NormalPropMap final : public SharedPropMap {
815 friend class PropMap;
816 friend class SharedPropMap;
817 friend class DictionaryPropMap;
818
819 LinkedPropMap::Data linkedData_;
820 TreeData treeData_;
821
NormalPropMap(SharedPropMap * prev,PropertyKey key,PropertyInfo prop)822 NormalPropMap(SharedPropMap* prev, PropertyKey key, PropertyInfo prop)
823 : linkedData_(prev) {
824 if (prev) {
825 setHeaderFlagBits(HasPrevFlag);
826 initNumPreviousMaps(prev->numPreviousMaps() + 1);
827 if (prev->hasPrevious()) {
828 setHeaderFlagBits(CanHaveTableFlag);
829 }
830 }
831 initProperty(0, key, prop);
832 }
833
NormalPropMap(NormalPropMap * orig,uint32_t length)834 NormalPropMap(NormalPropMap* orig, uint32_t length)
835 : linkedData_(orig->previous()) {
836 if (orig->hasPrevious()) {
837 setHeaderFlagBits(HasPrevFlag);
838 }
839 if (orig->canHaveTable()) {
840 setHeaderFlagBits(CanHaveTableFlag);
841 }
842 initNumPreviousMaps(orig->numPreviousMaps());
843 for (uint32_t i = 0; i < length; i++) {
844 initProperty(i, orig->getKey(i), orig->getPropertyInfo(i));
845 }
846 }
847
initProperty(uint32_t index,PropertyKey key,PropertyInfo prop)848 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
849 MOZ_ASSERT(!hasKey(index));
850 keys_[index].init(key);
851 linkedData_.propInfos[index] = prop;
852 }
853
854 bool isDictionary() const = delete;
855 bool isShared() const = delete;
856 bool isCompact() const = delete;
857 bool isNormal() const = delete;
858 bool isLinked() const = delete;
859 NormalPropMap* asNormal() = delete;
860 const NormalPropMap* asNormal() const = delete;
861
previous()862 SharedPropMap* previous() const {
863 return static_cast<SharedPropMap*>(linkedData_.previous.get());
864 }
865
treeDataRef()866 TreeData& treeDataRef() { return treeData_; }
treeDataRef()867 const TreeData& treeDataRef() const { return treeData_; }
868
staticAsserts()869 static void staticAsserts() {
870 static_assert(offsetof(NormalPropMap, linkedData_) ==
871 offsetof(LinkedPropMap, data_));
872 }
873 };
874
875 class DictionaryPropMap final : public PropMap {
876 friend class PropMap;
877 friend class SharedPropMap;
878
879 LinkedPropMap::Data linkedData_;
880
881 // SHAPE_INVALID_SLOT or head of slot freelist in owning dictionary-mode
882 // object.
883 uint32_t freeList_ = SHAPE_INVALID_SLOT;
884
885 // Number of holes for removed properties in this and previous maps. Used by
886 // compacting heuristics.
887 uint32_t holeCount_ = 0;
888
DictionaryPropMap(DictionaryPropMap * prev,PropertyKey key,PropertyInfo prop)889 DictionaryPropMap(DictionaryPropMap* prev, PropertyKey key, PropertyInfo prop)
890 : linkedData_(prev) {
891 setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag |
892 (prev ? HasPrevFlag : 0));
893 initProperty(0, key, prop);
894 }
895
896 template <typename T>
DictionaryPropMap(T * orig,uint32_t length)897 DictionaryPropMap(T* orig, uint32_t length) : linkedData_(nullptr) {
898 static_assert(std::is_same_v<T, CompactPropMap> ||
899 std::is_same_v<T, NormalPropMap>);
900 setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag);
901 for (uint32_t i = 0; i < length; i++) {
902 initProperty(i, orig->getKey(i), orig->getPropertyInfo(i));
903 }
904 }
905
initProperty(uint32_t index,PropertyKey key,PropertyInfo prop)906 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
907 MOZ_ASSERT(!hasKey(index));
908 keys_[index].init(key);
909 linkedData_.propInfos[index] = prop;
910 }
911
initPrevious(DictionaryPropMap * prev)912 void initPrevious(DictionaryPropMap* prev) {
913 MOZ_ASSERT(prev);
914 linkedData_.previous.init(prev);
915 setHeaderFlagBits(HasPrevFlag);
916 }
clearPrevious()917 void clearPrevious() {
918 linkedData_.previous = nullptr;
919 clearHeaderFlagBits(HasPrevFlag);
920 }
921
clearProperty(uint32_t index)922 void clearProperty(uint32_t index) { keys_[index] = PropertyKey::Void(); }
923
924 static void skipTrailingHoles(MutableHandle<DictionaryPropMap*> map,
925 uint32_t* mapLength);
926
927 void handOffLastMapStateTo(DictionaryPropMap* newLast);
928
incHoleCount()929 void incHoleCount() { holeCount_++; }
decHoleCount()930 void decHoleCount() {
931 MOZ_ASSERT(holeCount_ > 0);
932 holeCount_--;
933 }
934 static void maybeCompact(JSContext* cx, MutableHandle<DictionaryPropMap*> map,
935 uint32_t* mapLength);
936
937 public:
938 bool isDictionary() const = delete;
939 bool isShared() const = delete;
940 bool isCompact() const = delete;
941 bool isNormal() const = delete;
942 bool isLinked() const = delete;
943 DictionaryPropMap* asDictionary() = delete;
944 const DictionaryPropMap* asDictionary() const = delete;
945
fixupAfterMovingGC()946 void fixupAfterMovingGC() {}
947 inline void finalize(JSFreeOp* fop);
948
previous()949 DictionaryPropMap* previous() const {
950 return static_cast<DictionaryPropMap*>(linkedData_.previous.get());
951 }
952
freeList()953 uint32_t freeList() const { return freeList_; }
setFreeList(uint32_t slot)954 void setFreeList(uint32_t slot) { freeList_ = slot; }
955
getPropertyInfo(uint32_t index)956 PropertyInfo getPropertyInfo(uint32_t index) const {
957 MOZ_ASSERT(hasKey(index));
958 return linkedData_.propInfos[index];
959 }
960
961 // Add a new property to this map. Returns the new map/mapLength and object
962 // flags. The caller is responsible for generating a new dictionary shape.
963 static bool addProperty(JSContext* cx, const JSClass* clasp,
964 MutableHandle<DictionaryPropMap*> map,
965 uint32_t* mapLength, HandleId id, PropertyFlags flags,
966 uint32_t slot, ObjectFlags* objectFlags);
967
968 // Remove the property referenced by the table pointer. Returns the new
969 // map/mapLength. The caller is responsible for generating a new dictionary
970 // shape.
971 static void removeProperty(JSContext* cx,
972 MutableHandle<DictionaryPropMap*> map,
973 uint32_t* mapLength, PropMapTable* table,
974 PropMapTable::Ptr& ptr);
975
976 // Turn all sparse elements into dense elements. The caller is responsible
977 // for checking all sparse elements are plain data properties and must
978 // generate a new shape for the object.
979 static void densifyElements(JSContext* cx,
980 MutableHandle<DictionaryPropMap*> map,
981 uint32_t* mapLength, NativeObject* obj);
982
983 // Freeze or seal all properties in this map. Returns the new object flags.
984 // The caller is responsible for generating a new shape for the object.
985 void freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
986 const JSClass* clasp, uint32_t mapLength,
987 ObjectFlags* objectFlags);
988
989 // Change a property's slot number and/or flags and return the new object
990 // flags. The caller is responsible for generating a new shape.
991 void changeProperty(JSContext* cx, const JSClass* clasp, uint32_t index,
992 PropertyFlags flags, uint32_t slot,
993 ObjectFlags* objectFlags);
994
995 // Like changeProperty, but doesn't change the slot number.
changePropertyFlags(JSContext * cx,const JSClass * clasp,uint32_t index,PropertyFlags flags,ObjectFlags * objectFlags)996 void changePropertyFlags(JSContext* cx, const JSClass* clasp, uint32_t index,
997 PropertyFlags flags, ObjectFlags* objectFlags) {
998 uint32_t slot = getPropertyInfo(index).maybeSlot();
999 changeProperty(cx, clasp, index, flags, slot, objectFlags);
1000 }
1001
staticAsserts()1002 static void staticAsserts() {
1003 static_assert(offsetof(DictionaryPropMap, linkedData_) ==
1004 offsetof(LinkedPropMap, data_));
1005 }
1006 };
1007
asCompact()1008 inline CompactPropMap* PropMap::asCompact() {
1009 MOZ_ASSERT(isCompact());
1010 return static_cast<CompactPropMap*>(this);
1011 }
asCompact()1012 inline const CompactPropMap* PropMap::asCompact() const {
1013 MOZ_ASSERT(isCompact());
1014 return static_cast<const CompactPropMap*>(this);
1015 }
asLinked()1016 inline LinkedPropMap* PropMap::asLinked() {
1017 MOZ_ASSERT(isLinked());
1018 return static_cast<LinkedPropMap*>(this);
1019 }
asLinked()1020 inline const LinkedPropMap* PropMap::asLinked() const {
1021 MOZ_ASSERT(isLinked());
1022 return static_cast<const LinkedPropMap*>(this);
1023 }
asNormal()1024 inline NormalPropMap* PropMap::asNormal() {
1025 MOZ_ASSERT(isNormal());
1026 return static_cast<NormalPropMap*>(this);
1027 }
asNormal()1028 inline const NormalPropMap* PropMap::asNormal() const {
1029 MOZ_ASSERT(isNormal());
1030 return static_cast<const NormalPropMap*>(this);
1031 }
asShared()1032 inline SharedPropMap* PropMap::asShared() {
1033 MOZ_ASSERT(isShared());
1034 return static_cast<SharedPropMap*>(this);
1035 }
asShared()1036 inline const SharedPropMap* PropMap::asShared() const {
1037 MOZ_ASSERT(isShared());
1038 return static_cast<const SharedPropMap*>(this);
1039 }
asDictionary()1040 inline DictionaryPropMap* PropMap::asDictionary() {
1041 MOZ_ASSERT(isDictionary());
1042 return static_cast<DictionaryPropMap*>(this);
1043 }
asDictionary()1044 inline const DictionaryPropMap* PropMap::asDictionary() const {
1045 MOZ_ASSERT(isDictionary());
1046 return static_cast<const DictionaryPropMap*>(this);
1047 }
1048
getPropertyInfo(uint32_t index)1049 inline PropertyInfo PropMap::getPropertyInfo(uint32_t index) const {
1050 return isCompact() ? asCompact()->getPropertyInfo(index)
1051 : asLinked()->getPropertyInfo(index);
1052 }
1053
treeDataRef()1054 inline SharedPropMap::TreeData& SharedPropMap::treeDataRef() {
1055 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
1056 }
1057
treeDataRef()1058 inline const SharedPropMap::TreeData& SharedPropMap::treeDataRef() const {
1059 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
1060 }
1061
initProperty(uint32_t index,PropertyKey key,PropertyInfo prop)1062 inline void SharedPropMap::initProperty(uint32_t index, PropertyKey key,
1063 PropertyInfo prop) {
1064 if (isCompact()) {
1065 asCompact()->initProperty(index, key, prop);
1066 } else {
1067 asNormal()->initProperty(index, key, prop);
1068 }
1069 }
1070
1071 template <typename T>
propertyInfo()1072 inline PropertyInfo MapAndIndex<T>::propertyInfo() const {
1073 MOZ_ASSERT(!isNone());
1074 return map()->getPropertyInfo(index());
1075 }
1076
hash(PropertyKey key)1077 MOZ_ALWAYS_INLINE HashNumber PropMapTable::Hasher::hash(PropertyKey key) {
1078 return HashPropertyKey(key);
1079 }
match(PropMapAndIndex entry,PropertyKey key)1080 MOZ_ALWAYS_INLINE bool PropMapTable::Hasher::match(PropMapAndIndex entry,
1081 PropertyKey key) {
1082 MOZ_ASSERT(entry.map()->hasKey(entry.index()));
1083 return entry.map()->getKey(entry.index()) == key;
1084 }
1085
1086 // Hash policy for SharedPropMap children.
1087 struct SharedChildrenHasher {
1088 using Key = SharedPropMapAndIndex;
1089
1090 struct Lookup {
1091 PropertyKey key;
1092 PropertyInfo prop;
1093 uint8_t index;
1094
LookupSharedChildrenHasher::Lookup1095 Lookup(PropertyKey key, PropertyInfo prop, uint8_t index)
1096 : key(key), prop(prop), index(index) {}
LookupSharedChildrenHasher::Lookup1097 Lookup(PropertyInfoWithKey prop, uint8_t index)
1098 : key(prop.key()), prop(prop), index(index) {}
1099 };
1100
hashSharedChildrenHasher1101 static HashNumber hash(const Lookup& l) {
1102 HashNumber hash = HashPropertyKey(l.key);
1103 return mozilla::AddToHash(hash, l.prop.toRaw(), l.index);
1104 }
matchSharedChildrenHasher1105 static bool match(SharedPropMapAndIndex k, const Lookup& l) {
1106 SharedPropMap* map = k.map();
1107 uint32_t index = k.index();
1108 uint32_t newIndex = SharedPropMap::indexOfNextProperty(index);
1109 return index == l.index && map->matchProperty(newIndex, l.key, l.prop);
1110 }
1111 };
1112
1113 } // namespace js
1114
1115 // JS::ubi::Nodes can point to PropMaps; they're js::gc::Cell instances
1116 // with no associated compartment.
1117 namespace JS {
1118 namespace ubi {
1119
1120 template <>
1121 class Concrete<js::PropMap> : TracerConcrete<js::PropMap> {
1122 protected:
Concrete(js::PropMap * ptr)1123 explicit Concrete(js::PropMap* ptr) : TracerConcrete<js::PropMap>(ptr) {}
1124
1125 public:
construct(void * storage,js::PropMap * ptr)1126 static void construct(void* storage, js::PropMap* ptr) {
1127 new (storage) Concrete(ptr);
1128 }
1129
1130 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1131
typeName()1132 const char16_t* typeName() const override { return concreteTypeName; }
1133 static const char16_t concreteTypeName[];
1134 };
1135
1136 } // namespace ubi
1137 } // namespace JS
1138
1139 #endif // vm_PropMap_h
1140