diff options
Diffstat (limited to 'js/src/vm/PropMap.h')
| -rw-r--r-- | js/src/vm/PropMap.h | 1197 |
1 files changed, 1197 insertions, 0 deletions
diff --git a/js/src/vm/PropMap.h b/js/src/vm/PropMap.h new file mode 100644 index 0000000000..17792cdfe7 --- /dev/null +++ b/js/src/vm/PropMap.h @@ -0,0 +1,1197 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef vm_PropMap_h +#define vm_PropMap_h + +#include "gc/Barrier.h" +#include "gc/Cell.h" +#include "js/TypeDecls.h" +#include "js/UbiNode.h" +#include "js/Utility.h" // JS::UniqueChars +#include "vm/ObjectFlags.h" +#include "vm/PropertyInfo.h" +#include "vm/PropertyKey.h" + +// [SMDOC] Property Maps +// +// Property maps are used to store information about native object properties. +// Each property map represents an ordered list of (PropertyKey, PropertyInfo) +// tuples. +// +// Each property map can store up to 8 properties (see PropMap::Capacity). To +// store more than eight properties, multiple maps must be linked together with +// the |previous| pointer. +// +// Shapes and Property Maps +// ------------------------ +// Native object shapes represent property information as a (PropMap*, length) +// tuple. When there are no properties yet, the shape's map will be nullptr and +// the length is zero. +// +// For example, consider the following objects: +// +// o1 = {x: 1, y: 2} +// o2 = {x: 3, y: 4, z: 5} +// +// This is stored as follows: +// +// +-------------+ +--------------+ +-------------------+ +// | JSObject o1 | | Shape S1 | | PropMap M1 | +// |-------------+ +--------------+ +-------------------+ +// | shape: S1 -+---> | map: M1 -+--+> | key 0: x (slot 0) | +// | slot 0: 1 | | mapLength: 2 | | | key 1: y (slot 1) | +// | slot 1: 2 | +--------------+ | | key 2: z (slot 2) | +// +-------------+ | | ... | +// | +-------------------+ +// | +// +-------------+ +--------------+ | +// | JSObject o2 | | Shape S2 | | +// |-------------+ +--------------+ | +// | shape: S2 -+---> | map: M1 -+--+ +// | slot 0: 3 | | mapLength: 3 | +// | slot 1: 4 | +--------------+ +// | slot 2: 5 | +// +-------------+ +// +// There's a single map M1 shared by shapes S1 and S2. Shape S1 includes only +// the first two properties and shape S2 includes all three properties. +// +// Class Hierarchy +// --------------- +// Property maps have the following C++ class hierarchy: +// +// PropMap (abstract) +// | +// +-- SharedPropMap (abstract) +// | | +// | +-- CompactPropMap +// | | +// | +-- NormalPropMap +// | +// +-- DictionaryPropMap +// +// * PropMap: base class. It has a flags word and an array of PropertyKeys. +// +// * SharedPropMap: base class for all shared property maps. See below for more +// information on shared maps. +// +// * CompactPropMap: a shared map that stores its information more compactly +// than the other maps. It saves four words by not storing a +// PropMapTable, previous pointer, and by using a more compact +// PropertyInfo type for slot numbers that fit in one byte. +// +// * NormalPropMap: a shared map, used when CompactPropMap can't be used. +// +// * DictionaryPropMap: an unshared map (used by a single object/shape). See +// below for more information on dictionary maps. +// +// Secondary hierarchy +// ------------------- +// NormalPropMap and DictionaryPropMap store property information in the same +// way. This means property lookups don't have to distinguish between these two +// types. This is represented with a second class hierarchy: +// +// PropMap (abstract) +// | +// +-- CompactPropMap +// | +// +-- LinkedPropMap (NormalPropMap or DictionaryPropMap) +// +// Property lookup and property iteration are very performance sensitive and use +// this Compact vs Linked "view" so that they don't have to handle the three map +// types separately. +// +// LinkedPropMap also stores the PropMapTable and a pointer to the |previous| +// map. Compact maps don't have these fields. +// +// To summarize these map types: +// +// +-------------------+-------------+--------+ +// | Concrete type | Shared/tree | Linked | +// +-------------------+-------------+--------+ +// | CompactPropMap | yes | no | +// | NormalPropMap | yes | yes | +// | DictionaryPropMap | no | yes | +// +-------------------+-------------+--------+ +// +// PropMapTable +// ------------ +// Finding the PropertyInfo for a particular PropertyKey requires a linear +// search if the map is small. For larger maps we can create a PropMapTable, a +// hash table that maps from PropertyKey to PropMap + index, to speed up +// property lookups. +// +// To save memory, property map tables can be discarded on GC and recreated when +// needed. AutoKeepPropMapTables can be used to avoid discarding tables in a +// particular zone. Methods to access a PropMapTable take either an +// AutoCheckCannotGC or AutoKeepPropMapTables argument, to help ensure tables +// are not purged while we're using them. +// +// Shared Property Maps +// -------------------- +// Shared property maps can be shared per-Zone by objects with the same property +// keys, flags, and slot numbers. To make this work, shared maps form a tree: +// +// - Each Zone has a table that maps from first PropertyKey + PropertyInfo to +// a SharedPropMap that begins with that property. This is used to lookup the +// the map to use when adding the first property. +// See ShapeZone::initialPropMaps. +// +// - When adding a property other than the first one, the property is stored in +// the next entry of the same map when possible. If the map is full or the +// next entry already stores a different property, a child map is created and +// linked to the parent map. +// +// For example, imagine we want to create these objects: +// +// o1 = {x: 1, y: 2, z: 3} +// o2 = {x: 1, y: 2, foo: 4} +// +// This will result in the following maps being created: +// +// +---------------------+ +---------------------+ +// | SharedPropMap M1 | | SharedPropMap M2 | +// +---------------------+ +---------------------+ +// | Child M2 (index 1) -+--> | Parent M1 (index 1) | +// +---------------------+ +---------------------+ +// | 0: x | | 0: x | +// | 1: y | | 1: y | +// | 2: z | | 2: foo | +// | ... | | ... | +// +---------------------+ +---------------------+ +// +// M1 is the map used for initial property "x". Properties "y" and "z" can be +// stored inline. When later adding "foo" following "y", the map has to be +// forked: a child map M2 is created and M1 remembers this transition at +// property index 1 so that M2 will be used the next time properties "x", "y", +// and "foo" are added to an object. +// +// Shared maps contain a TreeData struct that stores the parent and children +// links for the SharedPropMap tree. The parent link is a tagged pointer that +// stores both the parent map and the property index of the last used property +// in the parent map before the branch. The children are stored similarly: the +// parent map can store a single child map and index, or a set of children. +// See SharedChildrenPtr. +// +// Looking up a child map can then be done based on the index of the last +// property in the parent map and the new property's key and flags. So for the +// example above, the lookup key for M1 => M2 is (index 1, "foo", <flags>). +// +// Note: shared maps can have both a |previous| map and a |parent| map. They are +// equal when the previous map was full, but can be different maps when +// branching in the middle of a map like in the example above: M2 has parent M1 +// but does not have a |previous| map (because it only has three properties). +// +// Dictionary Property Maps +// ------------------------ +// Certain operations can't be implemented (efficiently) for shared property +// maps, for example changing or deleting a property other than the last one. +// When this happens the map is copied as a DictionaryPropMap. +// +// Dictionary maps are unshared so can be mutated in place (after generating a +// new shape for the object). +// +// Unlike shared maps, dictionary maps can have holes between two property keys +// after removing a property. When there are more holes than properties, the +// map is compacted. See DictionaryPropMap::maybeCompact. + +namespace js { + +enum class IntegrityLevel; + +class DictionaryPropMap; +class SharedPropMap; +class LinkedPropMap; +class CompactPropMap; +class NormalPropMap; + +class JS_PUBLIC_API GenericPrinter; +class JSONPrinter; + +// Template class for storing a PropMap* and a property index as tagged pointer. +template <typename T> +class MapAndIndex { + uintptr_t data_ = 0; + + static constexpr uintptr_t IndexMask = 0b111; + + public: + MapAndIndex() = default; + + MapAndIndex(const T* map, uint32_t index) : data_(uintptr_t(map) | index) { + MOZ_ASSERT((uintptr_t(map) & IndexMask) == 0); + MOZ_ASSERT(index <= IndexMask); + } + explicit MapAndIndex(uintptr_t data) : data_(data) {} + + void setNone() { data_ = 0; } + + bool isNone() const { return data_ == 0; } + + uintptr_t raw() const { return data_; } + T* maybeMap() const { return reinterpret_cast<T*>(data_ & ~IndexMask); } + + uint32_t index() const { + MOZ_ASSERT(!isNone()); + return data_ & IndexMask; + } + T* map() const { + MOZ_ASSERT(!isNone()); + return maybeMap(); + } + + inline PropertyInfo propertyInfo() const; + + bool operator==(const MapAndIndex<T>& other) const { + return data_ == other.data_; + } + bool operator!=(const MapAndIndex<T>& other) const { + return !operator==(other); + } +} JS_HAZ_GC_POINTER; +using PropMapAndIndex = MapAndIndex<PropMap>; +using SharedPropMapAndIndex = MapAndIndex<SharedPropMap>; + +struct SharedChildrenHasher; +using SharedChildrenSet = + HashSet<SharedPropMapAndIndex, SharedChildrenHasher, SystemAllocPolicy>; + +// Children of shared maps. This is either: +// +// - None (no children) +// - SingleMapAndIndex (one child map, including the property index of the last +// property before the branch) +// - SharedChildrenSet (multiple children) +// +// Because SingleMapAndIndex use all bits, this relies on the HasChildrenSet +// flag in the map to distinguish the latter two cases. +class SharedChildrenPtr { + uintptr_t data_ = 0; + + public: + bool isNone() const { return data_ == 0; } + void setNone() { data_ = 0; } + + void setSingleChild(SharedPropMapAndIndex child) { data_ = child.raw(); } + void setChildrenSet(SharedChildrenSet* set) { data_ = uintptr_t(set); } + + SharedPropMapAndIndex toSingleChild() const { + MOZ_ASSERT(!isNone()); + return SharedPropMapAndIndex(data_); + } + + SharedChildrenSet* toChildrenSet() const { + MOZ_ASSERT(!isNone()); + return reinterpret_cast<SharedChildrenSet*>(data_); + } +} JS_HAZ_GC_POINTER; + +// Ensures no property map tables are purged in the current zone. +class MOZ_RAII AutoKeepPropMapTables { + JSContext* cx_; + bool prev_; + + public: + void operator=(const AutoKeepPropMapTables&) = delete; + AutoKeepPropMapTables(const AutoKeepPropMapTables&) = delete; + explicit inline AutoKeepPropMapTables(JSContext* cx); + inline ~AutoKeepPropMapTables(); +}; + +// Hash table to optimize property lookups on larger maps. This maps from +// PropertyKey to PropMapAndIndex. +class PropMapTable { + struct Hasher { + using Key = PropMapAndIndex; + using Lookup = PropertyKey; + static MOZ_ALWAYS_INLINE HashNumber hash(PropertyKey key); + static MOZ_ALWAYS_INLINE bool match(PropMapAndIndex, PropertyKey key); + }; + + // Small lookup cache. This has a hit rate of 30-60% on most workloads and is + // a lot faster than the full HashSet lookup. + struct CacheEntry { + PropertyKey key; + PropMapAndIndex result; + }; + static constexpr uint32_t NumCacheEntries = 2; + CacheEntry cacheEntries_[NumCacheEntries]; + + using Set = HashSet<PropMapAndIndex, Hasher, SystemAllocPolicy>; + Set set_; + + void setCacheEntry(PropertyKey key, PropMapAndIndex entry) { + for (uint32_t i = 0; i < NumCacheEntries; i++) { + if (cacheEntries_[i].key == key) { + cacheEntries_[i].result = entry; + return; + } + } + } + bool lookupInCache(PropertyKey key, PropMapAndIndex* result) const { + for (uint32_t i = 0; i < NumCacheEntries; i++) { + if (cacheEntries_[i].key == key) { + *result = cacheEntries_[i].result; +#ifdef DEBUG + auto p = lookupRaw(key); + MOZ_ASSERT(*result == (p ? *p : PropMapAndIndex())); +#endif + return true; + } + } + return false; + } + void addToCache(PropertyKey key, Set::Ptr p) { + for (uint32_t i = NumCacheEntries - 1; i > 0; i--) { + cacheEntries_[i] = cacheEntries_[i - 1]; + MOZ_ASSERT(cacheEntries_[i].key != key); + } + cacheEntries_[0].key = key; + cacheEntries_[0].result = p ? *p : PropMapAndIndex(); + } + + public: + using Ptr = Set::Ptr; + + PropMapTable() = default; + ~PropMapTable() = default; + + uint32_t entryCount() const { return set_.count(); } + + // This counts the PropMapTable object itself (which must be heap-allocated) + // and its HashSet. + size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const { + return mallocSizeOf(this) + set_.shallowSizeOfExcludingThis(mallocSizeOf); + } + + // init() is fallible and reports OOM to the context. + bool init(JSContext* cx, LinkedPropMap* map); + + MOZ_ALWAYS_INLINE PropMap* lookup(PropMap* map, uint32_t mapLength, + PropertyKey key, uint32_t* index); + + Set::Ptr lookupRaw(PropertyKey key) const { return set_.lookup(key); } +#ifdef DEBUG + Set::Ptr readonlyThreadsafeLookup(PropertyKey key) const { + return set_.readonlyThreadsafeLookup(key); + } +#endif + + bool add(JSContext* cx, PropertyKey key, PropMapAndIndex entry) { + if (!set_.putNew(key, entry)) { + ReportOutOfMemory(cx); + return false; + } + setCacheEntry(key, entry); + return true; + } + + void purgeCache() { + for (uint32_t i = 0; i < NumCacheEntries; i++) { + cacheEntries_[i] = CacheEntry(); + } + } + + void remove(Ptr ptr) { + set_.remove(ptr); + purgeCache(); + } + + void replaceEntry(Ptr ptr, PropertyKey key, PropMapAndIndex newEntry) { + MOZ_ASSERT(*ptr != newEntry); + set_.replaceKey(ptr, key, newEntry); + setCacheEntry(key, newEntry); + } + + void trace(JSTracer* trc); +#ifdef JSGC_HASH_TABLE_CHECKS + void checkAfterMovingGC(); +#endif +}; + +class PropMap : public gc::TenuredCellWithFlags { + public: + // Number of properties that can be stored in each map. This must be small + // enough so that every index fits in a tagged PropMap* pointer (MapAndIndex). + static constexpr size_t Capacity = 8; + + protected: + static_assert(gc::CellFlagBitsReservedForGC == 3, + "PropMap must reserve enough bits for Cell"); + + enum Flags { + // Set if this is a CompactPropMap. + IsCompactFlag = 1 << 3, + + // Set if this map has a non-null previous map pointer. Never set for + // compact maps because they don't have a previous field. + HasPrevFlag = 1 << 4, + + // Set if this is a DictionaryPropMap. + IsDictionaryFlag = 1 << 5, + + // Set if this map can have a table. Never set for compact maps. Always set + // for dictionary maps. + CanHaveTableFlag = 1 << 6, + + // If set, this SharedPropMap has a SharedChildrenSet. Else it either has no + // children or a single child. See SharedChildrenPtr. Never set for + // dictionary maps. + HasChildrenSetFlag = 1 << 7, + + // If set, this SharedPropMap was once converted to dictionary mode. This is + // only used for heuristics. Never set for dictionary maps. + HadDictionaryConversionFlag = 1 << 8, + + // For SharedPropMap this stores the number of previous maps, clamped to + // NumPreviousMapsMax. This is used for heuristics. + NumPreviousMapsMax = 0x7f, + NumPreviousMapsShift = 9, + NumPreviousMapsMask = NumPreviousMapsMax << NumPreviousMapsShift, + }; + + template <typename KnownF, typename UnknownF> + static void forEachPropMapFlag(uintptr_t flags, KnownF known, + UnknownF unknown); + + // Flags word, stored in the cell header. Note that this hides the + // Cell::flags() method. + uintptr_t flags() const { return headerFlagsField(); } + + private: + GCPtr<PropertyKey> keys_[Capacity]; + + protected: + PropMap() = default; + + void initKey(uint32_t index, PropertyKey key) { + MOZ_ASSERT(index < Capacity); + keys_[index].init(key); + } + void setKey(uint32_t index, PropertyKey key) { + MOZ_ASSERT(index < Capacity); + keys_[index] = key; + } + + public: + bool isCompact() const { return flags() & IsCompactFlag; } + bool isLinked() const { return !isCompact(); } + bool isDictionary() const { return flags() & IsDictionaryFlag; } + bool isShared() const { return !isDictionary(); } + bool isNormal() const { return isShared() && !isCompact(); } + + bool hasPrevious() const { return flags() & HasPrevFlag; } + bool canHaveTable() const { return flags() & CanHaveTableFlag; } + + inline CompactPropMap* asCompact(); + inline const CompactPropMap* asCompact() const; + + inline LinkedPropMap* asLinked(); + inline const LinkedPropMap* asLinked() const; + + inline NormalPropMap* asNormal(); + inline const NormalPropMap* asNormal() const; + + inline SharedPropMap* asShared(); + inline const SharedPropMap* asShared() const; + + inline DictionaryPropMap* asDictionary(); + inline const DictionaryPropMap* asDictionary() const; + + bool hasKey(uint32_t index) const { + MOZ_ASSERT(index < Capacity); + return !keys_[index].isVoid(); + } + PropertyKey getKey(uint32_t index) const { + MOZ_ASSERT(index < Capacity); + return keys_[index]; + } + + uint32_t approximateEntryCount() const; + +#if defined(DEBUG) || defined(JS_JITSPEW) + void dump() const; + void dump(js::GenericPrinter& out) const; + void dump(js::JSONPrinter& json) const; + + void dumpFields(js::JSONPrinter& json) const; + void dumpFieldsAt(js::JSONPrinter& json, uint32_t index) const; + void dumpDescriptorStringContentAt(js::GenericPrinter& out, + uint32_t index) const; + JS::UniqueChars getPropertyNameAt(uint32_t index) const; +#endif + +#ifdef DEBUG + void checkConsistency(NativeObject* obj) const; +#endif + + void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf, + size_t* children, size_t* tables) const; + + inline PropertyInfo getPropertyInfo(uint32_t index) const; + + PropertyInfoWithKey getPropertyInfoWithKey(uint32_t index) const { + return PropertyInfoWithKey(getPropertyInfo(index), getKey(index)); + } + + MOZ_ALWAYS_INLINE PropMap* lookupLinear(uint32_t mapLength, PropertyKey key, + uint32_t* index); + + MOZ_ALWAYS_INLINE PropMap* lookupPure(uint32_t mapLength, PropertyKey key, + uint32_t* index); + + MOZ_ALWAYS_INLINE PropMap* lookup(JSContext* cx, uint32_t mapLength, + PropertyKey key, uint32_t* index); + + static inline bool lookupForRemove(JSContext* cx, PropMap* map, + uint32_t mapLength, PropertyKey key, + const AutoKeepPropMapTables& keep, + PropMap** propMap, uint32_t* propIndex, + PropMapTable** table, + PropMapTable::Ptr* ptr); + + static const JS::TraceKind TraceKind = JS::TraceKind::PropMap; + + void traceChildren(JSTracer* trc); +}; + +class SharedPropMap : public PropMap { + friend class PropMap; + + protected: + // Shared maps are stored in a tree structure. Each shared map has a TreeData + // struct linking the map to its parent and children. Initial maps (the ones + // stored in ShapeZone's initialPropMaps table) don't have a parent. + struct TreeData { + SharedChildrenPtr children; + SharedPropMapAndIndex parent; + + void setParent(SharedPropMap* map, uint32_t index) { + parent = SharedPropMapAndIndex(map, index); + } + }; + + private: + static SharedPropMap* create(JSContext* cx, Handle<SharedPropMap*> prev, + HandleId id, PropertyInfo prop); + static SharedPropMap* createInitial(JSContext* cx, HandleId id, + PropertyInfo prop); + static SharedPropMap* clone(JSContext* cx, Handle<SharedPropMap*> map, + uint32_t length); + + inline void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop); + + static bool addPropertyInternal(JSContext* cx, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyInfo prop); + + bool addChild(JSContext* cx, SharedPropMapAndIndex child, HandleId id, + PropertyInfo prop); + SharedPropMap* lookupChild(uint32_t length, HandleId id, PropertyInfo prop); + + protected: + void initNumPreviousMaps(uint32_t value) { + MOZ_ASSERT((flags() >> NumPreviousMapsShift) == 0); + // Clamp to NumPreviousMapsMax. This is okay because this value is only used + // for heuristics. + if (value > NumPreviousMapsMax) { + value = NumPreviousMapsMax; + } + setHeaderFlagBits(value << NumPreviousMapsShift); + } + + bool hasChildrenSet() const { return flags() & HasChildrenSetFlag; } + void setHasChildrenSet() { setHeaderFlagBits(HasChildrenSetFlag); } + void clearHasChildrenSet() { clearHeaderFlagBits(HasChildrenSetFlag); } + + void setHadDictionaryConversion() { + setHeaderFlagBits(HadDictionaryConversionFlag); + } + + public: + // Heuristics used when adding a property via NativeObject::addProperty and + // friends: + // + // * If numPreviousMaps >= NumPrevMapsForAddConsiderDictionary, consider + // converting the object to a dictionary object based on other heuristics. + // + // * If numPreviousMaps >= NumPrevMapsForAddAlwaysDictionary, always convert + // the object to a dictionary object. + static constexpr size_t NumPrevMapsConsiderDictionary = 32; + static constexpr size_t NumPrevMapsAlwaysDictionary = 100; + + static_assert(NumPrevMapsConsiderDictionary < NumPreviousMapsMax); + static_assert(NumPrevMapsAlwaysDictionary < NumPreviousMapsMax); + + // The number of properties that can definitely be added to an object without + // triggering dictionary mode conversion in NativeObject::addProperty. + static constexpr size_t MaxPropsForNonDictionary = + NumPrevMapsConsiderDictionary * Capacity; + + bool isDictionary() const = delete; + bool isShared() const = delete; + SharedPropMap* asShared() = delete; + const SharedPropMap* asShared() const = delete; + + bool hadDictionaryConversion() const { + return flags() & HadDictionaryConversionFlag; + } + + uint32_t numPreviousMaps() const { + uint32_t val = (flags() & NumPreviousMapsMask) >> NumPreviousMapsShift; + MOZ_ASSERT_IF(hasPrevious(), val > 0); + return val; + } + + MOZ_ALWAYS_INLINE bool shouldConvertToDictionaryForAdd() const; + + void fixupAfterMovingGC(); + inline void sweep(JS::GCContext* gcx); + inline void finalize(JS::GCContext* gcx); + + static inline void getPrevious(MutableHandle<SharedPropMap*> map, + uint32_t* mapLength); + + bool matchProperty(uint32_t index, PropertyKey key, PropertyInfo prop) const { + return getKey(index) == key && getPropertyInfo(index) == prop; + } + + inline TreeData& treeDataRef(); + inline const TreeData& treeDataRef() const; + + void removeChild(JS::GCContext* gcx, SharedPropMap* child); + + uint32_t lastUsedSlot(uint32_t mapLength) const { + return getPropertyInfo(mapLength - 1).maybeSlot(); + } + + // Number of slots required for objects with this map/mapLength. + static uint32_t slotSpan(const JSClass* clasp, const SharedPropMap* map, + uint32_t mapLength) { + MOZ_ASSERT(clasp->isNativeObject()); + uint32_t numReserved = JSCLASS_RESERVED_SLOTS(clasp); + if (!map) { + MOZ_ASSERT(mapLength == 0); + return numReserved; + } + uint32_t lastSlot = map->lastUsedSlot(mapLength); + if (lastSlot == SHAPE_INVALID_SLOT) { + // The object only has custom data properties. + return numReserved; + } + // Some builtin objects store properties in reserved slots. Make sure the + // slot span >= numReserved. See addPropertyInReservedSlot. + return std::max(lastSlot + 1, numReserved); + } + + static uint32_t indexOfNextProperty(uint32_t index) { + MOZ_ASSERT(index < PropMap::Capacity); + return (index + 1) % PropMap::Capacity; + } + + // Add a new property to this map. Returns the new map/mapLength, slot number, + // and object flags. + static bool addProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, PropertyFlags flags, + ObjectFlags* objectFlags, uint32_t* slot); + + // Like addProperty, but for when the slot number is a reserved slot. A few + // builtin objects use this for initial properties. + static bool addPropertyInReservedSlot(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags); + + // Like addProperty, but for when the caller already knows the slot number to + // use (or wants to assert this exact slot number is used). + static bool addPropertyWithKnownSlot(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags); + + // Like addProperty, but for adding a custom data property. + static bool addCustomDataProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, + ObjectFlags* objectFlags); + + // Freeze or seal all properties by creating a new shared map. Returns the new + // map and object flags. + static bool freezeOrSealProperties(JSContext* cx, IntegrityLevel level, + const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t mapLength, + ObjectFlags* objectFlags); + + // Create a new dictionary map as copy of this map. + static DictionaryPropMap* toDictionaryMap(JSContext* cx, + Handle<SharedPropMap*> map, + uint32_t length); + +#if defined(DEBUG) || defined(JS_JITSPEW) + void dumpOwnFields(js::JSONPrinter& json) const; +#endif +}; + +class CompactPropMap final : public SharedPropMap { + CompactPropertyInfo propInfos_[Capacity]; + TreeData treeData_; + + friend class PropMap; + friend class SharedPropMap; + friend class DictionaryPropMap; + friend class js::gc::CellAllocator; + + CompactPropMap(JS::Handle<PropertyKey> key, PropertyInfo prop) { + setHeaderFlagBits(IsCompactFlag); + initProperty(0, key, prop); + } + + CompactPropMap(JS::Handle<CompactPropMap*> orig, uint32_t length) { + setHeaderFlagBits(IsCompactFlag); + for (uint32_t i = 0; i < length; i++) { + initKey(i, orig->getKey(i)); + propInfos_[i] = orig->propInfos_[i]; + } + } + + void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) { + MOZ_ASSERT(!hasKey(index)); + initKey(index, key); + propInfos_[index] = CompactPropertyInfo(prop); + } + + TreeData& treeDataRef() { return treeData_; } + const TreeData& treeDataRef() const { return treeData_; } + + public: + bool isDictionary() const = delete; + bool isShared() const = delete; + bool isCompact() const = delete; + bool isNormal() const = delete; + bool isLinked() const = delete; + CompactPropMap* asCompact() = delete; + const CompactPropMap* asCompact() const = delete; + + PropertyInfo getPropertyInfo(uint32_t index) const { + MOZ_ASSERT(hasKey(index)); + return PropertyInfo(propInfos_[index]); + } +}; + +// Layout shared by NormalPropMap and DictionaryPropMap. +class LinkedPropMap final : public PropMap { + friend class PropMap; + friend class SharedPropMap; + friend class NormalPropMap; + friend class DictionaryPropMap; + + struct Data { + GCPtr<PropMap*> previous; + PropMapTable* table = nullptr; + PropertyInfo propInfos[Capacity]; + + explicit Data(PropMap* prev) : previous(prev) {} + }; + Data data_; + + bool createTable(JSContext* cx); + void handOffTableTo(LinkedPropMap* next); + + public: + bool isCompact() const = delete; + bool isLinked() const = delete; + LinkedPropMap* asLinked() = delete; + const LinkedPropMap* asLinked() const = delete; + + PropMap* previous() const { return data_.previous; } + + bool hasTable() const { return data_.table != nullptr; } + + PropMapTable* maybeTable(JS::AutoCheckCannotGC& nogc) const { + return data_.table; + } + PropMapTable* ensureTable(JSContext* cx, const JS::AutoCheckCannotGC& nogc) { + if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) { + return nullptr; + } + return data_.table; + } + PropMapTable* ensureTable(JSContext* cx, const AutoKeepPropMapTables& keep) { + if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) { + return nullptr; + } + return data_.table; + } + + void purgeTable(JS::GCContext* gcx); + + void purgeTableCache() { + if (data_.table) { + data_.table->purgeCache(); + } + } + +#ifdef DEBUG + bool canSkipMarkingTable(); +#endif + + PropertyInfo getPropertyInfo(uint32_t index) const { + MOZ_ASSERT(hasKey(index)); + return data_.propInfos[index]; + } + +#if defined(DEBUG) || defined(JS_JITSPEW) + void dumpOwnFields(js::JSONPrinter& json) const; +#endif +}; + +class NormalPropMap final : public SharedPropMap { + friend class PropMap; + friend class SharedPropMap; + friend class DictionaryPropMap; + friend class js::gc::CellAllocator; + + LinkedPropMap::Data linkedData_; + TreeData treeData_; + + NormalPropMap(JS::Handle<SharedPropMap*> prev, PropertyKey key, + PropertyInfo prop) + : linkedData_(prev) { + if (prev) { + setHeaderFlagBits(HasPrevFlag); + initNumPreviousMaps(prev->numPreviousMaps() + 1); + if (prev->hasPrevious()) { + setHeaderFlagBits(CanHaveTableFlag); + } + } + initProperty(0, key, prop); + } + + NormalPropMap(JS::Handle<NormalPropMap*> orig, uint32_t length) + : linkedData_(orig->previous()) { + if (orig->hasPrevious()) { + setHeaderFlagBits(HasPrevFlag); + } + if (orig->canHaveTable()) { + setHeaderFlagBits(CanHaveTableFlag); + } + initNumPreviousMaps(orig->numPreviousMaps()); + for (uint32_t i = 0; i < length; i++) { + initProperty(i, orig->getKey(i), orig->getPropertyInfo(i)); + } + } + + void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) { + MOZ_ASSERT(!hasKey(index)); + initKey(index, key); + linkedData_.propInfos[index] = prop; + } + + bool isDictionary() const = delete; + bool isShared() const = delete; + bool isCompact() const = delete; + bool isNormal() const = delete; + bool isLinked() const = delete; + NormalPropMap* asNormal() = delete; + const NormalPropMap* asNormal() const = delete; + + SharedPropMap* previous() const { + return static_cast<SharedPropMap*>(linkedData_.previous.get()); + } + + TreeData& treeDataRef() { return treeData_; } + const TreeData& treeDataRef() const { return treeData_; } + + static void staticAsserts() { + static_assert(offsetof(NormalPropMap, linkedData_) == + offsetof(LinkedPropMap, data_)); + } +}; + +class DictionaryPropMap final : public PropMap { + friend class PropMap; + friend class SharedPropMap; + friend class js::gc::CellAllocator; + + LinkedPropMap::Data linkedData_; + + // SHAPE_INVALID_SLOT or head of slot freelist in owning dictionary-mode + // object. + uint32_t freeList_ = SHAPE_INVALID_SLOT; + + // Number of holes for removed properties in this and previous maps. Used by + // compacting heuristics. + uint32_t holeCount_ = 0; + + DictionaryPropMap(JS::Handle<DictionaryPropMap*> prev, PropertyKey key, + PropertyInfo prop) + : linkedData_(prev) { + setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag | + (prev ? HasPrevFlag : 0)); + initProperty(0, key, prop); + } + + DictionaryPropMap(JS::Handle<NormalPropMap*> orig, uint32_t length) + : linkedData_(nullptr) { + setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag); + for (uint32_t i = 0; i < length; i++) { + initProperty(i, orig->getKey(i), orig->getPropertyInfo(i)); + } + } + + DictionaryPropMap(JS::Handle<CompactPropMap*> orig, uint32_t length) + : linkedData_(nullptr) { + setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag); + for (uint32_t i = 0; i < length; i++) { + initProperty(i, orig->getKey(i), orig->getPropertyInfo(i)); + } + } + + void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) { + MOZ_ASSERT(!hasKey(index)); + initKey(index, key); + linkedData_.propInfos[index] = prop; + } + + void initPrevious(DictionaryPropMap* prev) { + MOZ_ASSERT(prev); + linkedData_.previous.init(prev); + setHeaderFlagBits(HasPrevFlag); + } + void clearPrevious() { + linkedData_.previous = nullptr; + clearHeaderFlagBits(HasPrevFlag); + } + + void clearProperty(uint32_t index) { setKey(index, PropertyKey::Void()); } + + static void skipTrailingHoles(MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength); + + void handOffLastMapStateTo(DictionaryPropMap* newLast); + + void incHoleCount() { holeCount_++; } + void decHoleCount() { + MOZ_ASSERT(holeCount_ > 0); + holeCount_--; + } + static void maybeCompact(JSContext* cx, MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength); + + public: + bool isDictionary() const = delete; + bool isShared() const = delete; + bool isCompact() const = delete; + bool isNormal() const = delete; + bool isLinked() const = delete; + DictionaryPropMap* asDictionary() = delete; + const DictionaryPropMap* asDictionary() const = delete; + + void fixupAfterMovingGC() {} + inline void finalize(JS::GCContext* gcx); + + DictionaryPropMap* previous() const { + return static_cast<DictionaryPropMap*>(linkedData_.previous.get()); + } + + uint32_t freeList() const { return freeList_; } + void setFreeList(uint32_t slot) { freeList_ = slot; } + + PropertyInfo getPropertyInfo(uint32_t index) const { + MOZ_ASSERT(hasKey(index)); + return linkedData_.propInfos[index]; + } + + // Add a new property to this map. Returns the new map/mapLength and object + // flags. The caller is responsible for generating a new dictionary shape. + static bool addProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, HandleId id, PropertyFlags flags, + uint32_t slot, ObjectFlags* objectFlags); + + // Remove the property referenced by the table pointer. Returns the new + // map/mapLength. The caller is responsible for generating a new dictionary + // shape. + static void removeProperty(JSContext* cx, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, PropMapTable* table, + PropMapTable::Ptr& ptr); + + // Turn all sparse elements into dense elements. The caller is responsible + // for checking all sparse elements are plain data properties and must + // generate a new shape for the object. + static void densifyElements(JSContext* cx, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, NativeObject* obj); + + // Freeze or seal all properties in this map. Returns the new object flags. + // The caller is responsible for generating a new shape for the object. + void freezeOrSealProperties(JSContext* cx, IntegrityLevel level, + const JSClass* clasp, uint32_t mapLength, + ObjectFlags* objectFlags); + + // Change a property's slot number and/or flags and return the new object + // flags. The caller is responsible for generating a new shape. + void changeProperty(JSContext* cx, const JSClass* clasp, uint32_t index, + PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags); + + // Like changeProperty, but doesn't change the slot number. + void changePropertyFlags(JSContext* cx, const JSClass* clasp, uint32_t index, + PropertyFlags flags, ObjectFlags* objectFlags) { + uint32_t slot = getPropertyInfo(index).maybeSlot(); + changeProperty(cx, clasp, index, flags, slot, objectFlags); + } + + static void staticAsserts() { + static_assert(offsetof(DictionaryPropMap, linkedData_) == + offsetof(LinkedPropMap, data_)); + } + +#if defined(DEBUG) || defined(JS_JITSPEW) + void dumpOwnFields(js::JSONPrinter& json) const; +#endif +}; + +inline CompactPropMap* PropMap::asCompact() { + MOZ_ASSERT(isCompact()); + return static_cast<CompactPropMap*>(this); +} +inline const CompactPropMap* PropMap::asCompact() const { + MOZ_ASSERT(isCompact()); + return static_cast<const CompactPropMap*>(this); +} +inline LinkedPropMap* PropMap::asLinked() { + MOZ_ASSERT(isLinked()); + return static_cast<LinkedPropMap*>(this); +} +inline const LinkedPropMap* PropMap::asLinked() const { + MOZ_ASSERT(isLinked()); + return static_cast<const LinkedPropMap*>(this); +} +inline NormalPropMap* PropMap::asNormal() { + MOZ_ASSERT(isNormal()); + return static_cast<NormalPropMap*>(this); +} +inline const NormalPropMap* PropMap::asNormal() const { + MOZ_ASSERT(isNormal()); + return static_cast<const NormalPropMap*>(this); +} +inline SharedPropMap* PropMap::asShared() { + MOZ_ASSERT(isShared()); + return static_cast<SharedPropMap*>(this); +} +inline const SharedPropMap* PropMap::asShared() const { + MOZ_ASSERT(isShared()); + return static_cast<const SharedPropMap*>(this); +} +inline DictionaryPropMap* PropMap::asDictionary() { + MOZ_ASSERT(isDictionary()); + return static_cast<DictionaryPropMap*>(this); +} +inline const DictionaryPropMap* PropMap::asDictionary() const { + MOZ_ASSERT(isDictionary()); + return static_cast<const DictionaryPropMap*>(this); +} + +inline PropertyInfo PropMap::getPropertyInfo(uint32_t index) const { + return isCompact() ? asCompact()->getPropertyInfo(index) + : asLinked()->getPropertyInfo(index); +} + +inline SharedPropMap::TreeData& SharedPropMap::treeDataRef() { + return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef(); +} + +inline const SharedPropMap::TreeData& SharedPropMap::treeDataRef() const { + return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef(); +} + +inline void SharedPropMap::initProperty(uint32_t index, PropertyKey key, + PropertyInfo prop) { + if (isCompact()) { + asCompact()->initProperty(index, key, prop); + } else { + asNormal()->initProperty(index, key, prop); + } +} + +template <typename T> +inline PropertyInfo MapAndIndex<T>::propertyInfo() const { + MOZ_ASSERT(!isNone()); + return map()->getPropertyInfo(index()); +} + +MOZ_ALWAYS_INLINE HashNumber PropMapTable::Hasher::hash(PropertyKey key) { + return HashPropertyKey(key); +} +MOZ_ALWAYS_INLINE bool PropMapTable::Hasher::match(PropMapAndIndex entry, + PropertyKey key) { + MOZ_ASSERT(entry.map()->hasKey(entry.index())); + return entry.map()->getKey(entry.index()) == key; +} + +// Hash policy for SharedPropMap children. +struct SharedChildrenHasher { + using Key = SharedPropMapAndIndex; + + struct Lookup { + PropertyKey key; + PropertyInfo prop; + uint8_t index; + + Lookup(PropertyKey key, PropertyInfo prop, uint8_t index) + : key(key), prop(prop), index(index) {} + Lookup(PropertyInfoWithKey prop, uint8_t index) + : key(prop.key()), prop(prop), index(index) {} + }; + + static HashNumber hash(const Lookup& l) { + HashNumber hash = HashPropertyKey(l.key); + return mozilla::AddToHash(hash, l.prop.toRaw(), l.index); + } + static bool match(SharedPropMapAndIndex k, const Lookup& l) { + SharedPropMap* map = k.map(); + uint32_t index = k.index(); + uint32_t newIndex = SharedPropMap::indexOfNextProperty(index); + return index == l.index && map->matchProperty(newIndex, l.key, l.prop); + } +}; + +} // namespace js + +// JS::ubi::Nodes can point to PropMaps; they're js::gc::Cell instances +// with no associated compartment. +namespace JS { +namespace ubi { + +template <> +class Concrete<js::PropMap> : TracerConcrete<js::PropMap> { + protected: + explicit Concrete(js::PropMap* ptr) : TracerConcrete<js::PropMap>(ptr) {} + + public: + static void construct(void* storage, js::PropMap* ptr) { + new (storage) Concrete(ptr); + } + + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +} // namespace ubi +} // namespace JS + +#endif // vm_PropMap_h |