include/hermes/VM/HiddenClass.h (352 lines of code) (raw):

/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * This source code is licensed under the MIT license found in the * LICENSE file in the root directory of this source tree. */ #ifndef HERMES_VM_HIDDENCLASS_H #define HERMES_VM_HIDDENCLASS_H #include "hermes/Support/OptValue.h" #include "hermes/VM/ArrayStorage.h" #include "hermes/VM/DictPropertyMap.h" #include "hermes/VM/GCPointer-inline.h" #include "hermes/VM/PropertyDescriptor.h" #include "hermes/VM/SegmentedArray.h" #include "hermes/VM/WeakValueMap.h" #include <functional> #include "llvh/ADT/ArrayRef.h" namespace hermes { namespace vm { /// The storage type used for properties. Its size may be restricted depending /// on the current configuration, for example because it must fit in a single /// heap segment. using PropStorage = ArrayStorageSmall; /// The storage type used for large arrays that don't necessarily fit in a /// single heap segment. using BigStorage = SegmentedArray; /// Flags associated with a hidden class. struct ClassFlags { /// This class is in dictionary mode, meaning that adding and removing fields /// doesn't cause transitions but simply updates the property map. (We may /// still change hidden classes; see dictionaryNoCacheMode, below). uint8_t dictionaryMode : 1; /// If dictionaryMode is set, this indicates whether the hidden class can /// be used as the key in property caches. If we delete properties, or update /// properties, we create a new hidden class for the owning object /// (to invalidate any property caches referencing the old hidden /// class). We may decide to limit the number of hidden classes /// created this way (currently we allow just one). To do this, we /// set this property of the hidden class property, so that the new /// hidden class is never added to an property cache. uint8_t dictionaryNoCacheMode : 1; /// Set when we have index-like named properties (e.g. "0", "1", etc) defined /// using defineOwnProperty. Array accesses will have to check the named /// properties first. The absence of this flag is important as it indicates /// that named properties whose name is an integer index don't need to be /// searched for - they don't exist. uint8_t hasIndexLikeProperties : 1; /// All properties in this class are non-configurable. This flag can sometimes /// be set lazily, after we have checked whether all properties are non- /// configurable. uint8_t allNonConfigurable : 1; /// All properties in this class are both non-configurable and non-writable. /// It imples that \c allNonConfigurable is also set. /// This flag can sometimes be set lazily, after we have checked whether all /// properties are "read-only". uint8_t allReadOnly : 1; ClassFlags() { ::memset(this, 0, sizeof(*this)); } }; /// A "hidden class" describes a fixed set of properties, their property flags /// and the order that they were created in. It is logically immutable (unless /// it is in "dictionary mode", which is described below). /// /// Overview /// ======== /// Adding, deleting or updating a property of a "hidden class" is represented /// as a transition to a new "hidden class", which encodes the new state of the /// property set. We call the old class a "parent" and the new class a /// "child". Starting from a given parent class, its children and their /// children (etc...) form a tree. /// /// Each class contains a transition table from itself to its children, keyed on /// the new/updated property name (SymbolID) and the new/updated property flags /// that caused each child to be created. /// /// When a new empty JavaScript object is created, it is assigned an empty /// "root" hidden class. Adding a new property causes a transition from the /// root class to a new child class and the transition is recorded in the root /// class transition table. Adding a second property causes another class to /// be allocated and a transition to be recorded in its parent, and so on. /// When a second empty JavaScript object is created and the same properties /// are added in the same order, the existing classes will be found by looking /// up in each transition table. /// /// In this way, JavaScript objects which have the same properties added in the /// same order will end up having the same hidden class identifying their set /// of properties. That can decreases the memory dramatically (because we have /// only one set description per class instead of one per object) and can be /// used for caching property offsets and other attributes. /// /// Dictionary Mode /// =============== /// When more than a predefined number of properties are added (\c /// kDictionaryThreshold) or if a property is deleted, a new class is created /// without a parent and placed in "dictionary mode". In that mode the class /// is not shared - it belongs to exactly one object - and updates are done "in /// place" instead of creating new child classes. /// /// Property Maps /// ============= /// Conceptually every hidden class has a property map - a table mapping from /// a property name (SymbolID) to a property descriptor (slot + flags). /// /// In order to conserve memory, we create the property map associated with a /// class the first time it is needed. To delay creation further, if we are /// looking for a property for a "put-by-name" operation, we can avoid needing /// the map by looking for the property in the transition table first. Lastly, /// when we transition from a parent class to a child class, we "steal" the /// parent's property map and assign it to the child. /// /// The desired effect is that only "leaf" classes have property maps and normal /// property assignment doesn't create a map at all in the intermediate states /// (except the first time). class HiddenClass; namespace detail { /// Encode a transition from a hidden class to a child, keyed on the /// name of the property and its property flags. /// This is an internal type but has to be made public so we can define /// a llvh::DenseMapInfo<> trait for it. class Transition { public: SymbolID symbolID; PropertyFlags propertyFlags; /// An explicit constructor for creating DenseMap sentinel values. explicit Transition(SymbolID symbolID) : symbolID(symbolID), propertyFlags() {} Transition(SymbolID symbolID, PropertyFlags flags) : symbolID(symbolID), propertyFlags(flags) {} bool operator==(const Transition &a) const { return symbolID == a.symbolID && propertyFlags == a.propertyFlags; } }; /// A front for WeakValueMap<Transition, HiddenClass> that is space-optimized /// for the common case of 0 or 1 entry. See WeakValueMap for more details. class TransitionMap { public: ~TransitionMap() { if (isLarge()) delete large(); } /// Return true if there is an entry with the given key and a valid value. bool containsKey(const Transition &key, GC *gc) { return (smallKey_ == key && smallValue().isValid()) || (isLarge() && large()->containsKey(key)); } /// Look for key and return the value as Handle<T> if found or None if not. llvh::Optional<Handle<HiddenClass>> lookup(HandleRootOwner &runtime, GC *gc, const Transition &key) { if (smallKey_ == key) { return smallValue().get(runtime, gc); } else if (isLarge()) { return large()->lookup(runtime, gc, key); } else { return llvh::None; } } /// Insert a key/value into the map if the key is not already there. /// \return true if it was inserted, false if the key was already there. bool insertNew( Runtime &runtime, const Transition &key, Handle<HiddenClass> value) { assert( key.symbolID != SymbolID::empty() && "Should never insert an empty key"); if (smallKey_ == key && smallValue().isValid()) { return false; } // Need to hold the lock when mutating smallKey and smallValue. WeakRefLock lk{runtime.getHeap().weakRefMutex()}; if (isClean()) { smallKey_ = key; smallValue() = WeakRef<HiddenClass>(&runtime.getHeap(), value); return true; } if (!isLarge()) uncleanMakeLarge(runtime); return large()->insertNewLocked(&runtime.getHeap(), key, value); } /// Insert key/value into the map. Used by deserialization. void insertUnsafe(Runtime &runtime, const Transition &key, WeakRefSlot *ptr); /// Accepts every valid WeakRef in the map. void markWeakRefs(WeakRefAcceptor &acceptor) { if (isLarge()) { large()->markWeakRefs(acceptor); } else if (!isClean()) { acceptor.accept(smallValue()); } } /// \return estimated dynamically allocated memory owned by this map. size_t getMemorySize() const; /// \return true if the map is known to be empty. May have false negatives. bool isKnownEmpty() const { return isClean() || (isLarge() && large()->isKnownEmpty()); } /// Invoke \p callback on each (const) key and value. Values may be invalid. template <typename CallbackFunction> void forEachEntry(const CallbackFunction &callback) const { if (isLarge()) { large()->forEachEntry(callback); } else if (!isClean()) { callback(smallKey_, smallValue()); } } void snapshotAddNodes(GC *gc, HeapSnapshot &snap); void snapshotAddEdges(GC *gc, HeapSnapshot &snap); void snapshotUntrackMemory(GC *gc); private: /// Clean = no transition has been inserted since construction. bool isClean() const { return smallKey_.symbolID == SymbolID::empty(); } /// Large = allocated WeakValueMap contains any/all entries. bool isLarge() const { return smallKey_.symbolID == SymbolID::deleted(); } /// Expand to large mode, assuming already unclean. void uncleanMakeLarge(Runtime &runtime); /// Accessors for each union member after asserting it's active. WeakRef<HiddenClass> &smallValue() { assert(!isLarge()); return u.smallValue_; } const WeakRef<HiddenClass> &smallValue() const { assert(!isLarge()); return u.smallValue_; } WeakValueMap<Transition, HiddenClass> *large() const { assert(isLarge()); return u.large_; } Transition smallKey_{SymbolID::empty()}; union U { U() : smallValue_((WeakRefSlot *)nullptr) {} WeakRef<HiddenClass> smallValue_; WeakValueMap<Transition, HiddenClass> *large_; } u; }; } // namespace detail class HiddenClass final : public GCCell { friend void HiddenClassBuildMeta(const GCCell *cell, Metadata::Builder &mb); public: using Transition = detail::Transition; /// Adding more than this number of properties will switch to "dictionary /// mode". static constexpr unsigned kDictionaryThreshold = 64; static const VTable vt; static constexpr CellKind getCellKind() { return CellKind::HiddenClassKind; } static bool classof(const GCCell *cell) { return cell->getKind() == CellKind::HiddenClassKind; } /// Create a "root" hidden class - one that doesn't define any properties, but /// is a starting point for a hierarchy. static CallResult<HermesValue> createRoot(Runtime &runtime); /// \return true if this hidden class is guaranteed to be a leaf. /// It can return false negatives, so it should only be used for stats /// reporting and such. bool isKnownLeaf() const { return transitionMap_.isKnownEmpty(); } /// \return the number of own properties described by this hidden class. /// This corresponds to the size of the property map, if it is initialized. unsigned getNumProperties() const { return numProperties_; } /// \return true if this class is in "dictionary mode" - i.e. changes to it /// don't (normally) result in creation of new classes. bool isDictionary() const { return flags_.dictionaryMode; } /// \return true if this class is in "non-cacheable dictionary mode" /// - it is a dictionary, and the owning object has been modified in /// a way since becoming a dictionary that precludes inline caching /// (for example, a property has been deleted or updated). bool isDictionaryNoCache() const { assert( (!flags_.dictionaryNoCacheMode || flags_.dictionaryMode) && "dictionaryNoCacheMode should only be set if dictionaryMode is set."); return flags_.dictionaryNoCacheMode; } bool getHasIndexLikeProperties() const { return flags_.hasIndexLikeProperties; } /// \return The for-in cache if one has been set, otherwise nullptr. BigStorage *getForInCache(Runtime &runtime) const { return forInCache_.get(runtime); } void setForInCache(BigStorage *arr, Runtime &runtime) { forInCache_.set(runtime, arr, &runtime.getHeap()); } void clearForInCache(Runtime &runtime) { forInCache_.setNull(&runtime.getHeap()); } /// Reset the property map, unless this class is in dictionary mode. /// May be called by the GC for any HiddenClass not in a Handle. void clearPropertyMap(GC *gc) { if (!isDictionary()) propertyMap_.setNull(gc); } /// An opaque class representing a reference to a valid property in the /// property map. using PropertyPos = DictPropertyMap::PropertyPos; /// Call the supplied callback pass each property's \c SymbolID and \c /// NamedPropertyDescriptor as parameters. /// Obviously the callback shouldn't be doing naughty things like modifying /// the property map or creating new hidden classes (even implicitly). /// A marker for the current gcScope is obtained in the beginning and the /// scope is flushed after every callback. template <typename CallbackFunction> static void forEachProperty( Handle<HiddenClass> selfHandle, Runtime &runtime, const CallbackFunction &callback); /// Same as \p forEachProperty, but the callback cannot do any GC operations, /// such as allocating objects, modifying objects, or creating handles. /// \p forEachProperty is allowed to allocate, and thus can steal and cache /// the property map for the next query, so it is preferred. static void forEachPropertyNoAlloc( HiddenClass *self, PointerBase &base, std::function<void(SymbolID, NamedPropertyDescriptor)> callback); /// Same as forEachProperty() but the callback returns true to continue or /// false to stop immediately. /// A marker for the current gcScope is obtained in the beginning and the /// scope is flushed after every callback. /// \return false if the callback returned false, true otherwise. template <typename CallbackFunction> static bool forEachPropertyWhile( Handle<HiddenClass> selfHandle, Runtime &runtime, const CallbackFunction &callback); /// Look for a property in the property map. If the property is found, return /// a \c PropertyPos identifying it and store its descriptor in \p desc. /// \param expectedFlags if valid, we can search the transition table for this /// property with these precise flags. If found in the transition table, /// we don't need to create a property map. /// \return the "position" of the property, if found. static OptValue<PropertyPos> findProperty( PseudoHandle<HiddenClass> self, Runtime &runtime, SymbolID name, PropertyFlags expectedFlags, NamedPropertyDescriptor &desc); /// Same operation as \p findProperty, but does not do any allocations. /// This is slower than \p findProperty because it needs to traverse the full /// hidden class chain in the worst case. static llvh::Optional<NamedPropertyDescriptor> findPropertyNoAlloc(HiddenClass *self, PointerBase &base, SymbolID name); /// An optimistic fast path for \c findProperty(). If there is an allocated /// property map, this will return an OptValue containing either true or /// false. If there was no allocated property map, this returns llvh::None. If /// this fails by returning None, the "slow path", \c findProperty() itself, /// must be used. static OptValue<bool> tryFindPropertyFast( const HiddenClass *self, PointerBase &base, SymbolID name, NamedPropertyDescriptor &desc); /// Performs a very slow linear search for the specified property. This should /// only be used for debug tests where we don't want to allocate a property /// map because doing so would change the behavior. /// \return true if the property is defined, false otherwise. static bool debugIsPropertyDefined(HiddenClass *self, PointerBase &base, SymbolID name); /// Delete a property which we found earlier using \c findProperty. /// \return the resulting new class. static Handle<HiddenClass> deleteProperty( Handle<HiddenClass> selfHandle, Runtime &runtime, PropertyPos pos); /// Add a new property. It must not already exist. /// \return the resulting new class and the index of the new property. static CallResult<std::pair<Handle<HiddenClass>, SlotIndex>> addProperty( Handle<HiddenClass> selfHandle, Runtime &runtime, SymbolID name, PropertyFlags propertyFlags); /// Update an existing property's flags and return the resulting class. /// \param pos is the position of the property into the property map. static Handle<HiddenClass> updateProperty( Handle<HiddenClass> selfHandle, Runtime &runtime, PropertyPos pos, PropertyFlags newFlags); /// Mark all properties as non-configurable. /// \return the resulting class static Handle<HiddenClass> makeAllNonConfigurable( Handle<HiddenClass> selfHandle, Runtime &runtime); /// Mark all properties as non-writable and non-configurable. /// \return the resulting class static Handle<HiddenClass> makeAllReadOnly( Handle<HiddenClass> selfHandle, Runtime &runtime); /// Update the flags for the properties in the list \p props with \p /// flagsToClear and \p flagsToSet. If in dictionary mode, the properties are /// updated on the hidden class directly; otherwise, create a new dictionary /// hidden class as result. Updating the properties mutates the property map /// directly without creating transitions. /// \p flagsToClear and \p flagsToSet are masks for updating the property /// flags. /// \p props is a list of SymbolIDs for properties that need to be updated /// made read-only. It should contain a subset of properties in the hidden /// class, so the SymbolIDs won't get freed by gc. It can be llvh::None; if it /// is llvh::None, update every property. /// \return the resulting hidden class. static Handle<HiddenClass> updatePropertyFlagsWithoutTransitions( Handle<HiddenClass> selfHandle, Runtime &runtime, PropertyFlags flagsToClear, PropertyFlags flagsToSet, OptValue<llvh::ArrayRef<SymbolID>> props); /// Create a new class where the next slot is reserved, by calling addProperty /// with an internal property name. Only slots with index less than /// InternalProperty::NumAnonymousInternalProperties can be reserved. /// \param selfHandle must not be in dictionary mode. /// \return the resulting new class and the index of the reserved slot. static CallResult<std::pair<Handle<HiddenClass>, SlotIndex>> reserveSlot( Handle<HiddenClass> selfHandle, Runtime &runtime); /// \return true if all properties are non-configurable static bool areAllNonConfigurable( Handle<HiddenClass> selfHandle, Runtime &runtime); /// \return true if all properties are non-writable and non-configurable static bool areAllReadOnly(Handle<HiddenClass> selfHandle, Runtime &runtime); HiddenClass( Runtime &runtime, ClassFlags flags, Handle<HiddenClass> parent, SymbolID symbolID, PropertyFlags propertyFlags, unsigned numProperties) : symbolID_(symbolID), propertyFlags_(propertyFlags), flags_(flags), numProperties_(numProperties), parent_(runtime, *parent, &runtime.getHeap()) { assert(propertyFlags.isValid() && "propertyFlags must be valid"); } private: /// Allocate a new hidden class instance with the supplied parameters. static CallResult<HermesValue> create( Runtime &runtime, ClassFlags flags, Handle<HiddenClass> parent, SymbolID symbolID, PropertyFlags propertyFlags, unsigned numProperties); /// Create a copy of this \c HiddenClass and ensure that the copy is /// in dictionary mode. Requires that the current \C HiddenClass /// does not have the dictionaryNoCacheMode flag set; such /// dictionaries may not be copied. If the current class has a /// property map, it will be moved to the new class. Otherwise a new /// property map will be created for the new class. In either case, /// the current class will have no property map and the new class /// will have one. The \p noCache argument indicates whether the /// new dictionary \c HiddenClass's dictionaryNoCacheMode flag will /// be set. \return the new class. static Handle<HiddenClass> copyToNewDictionary( Handle<HiddenClass> selfHandle, Runtime &runtime, bool noCache = false); /// Add a new property pair (\p name and \p desc) to the property map (which /// must have been initialized). static ExecutionStatus addToPropertyMap( Handle<HiddenClass> selfHandle, Runtime &runtime, SymbolID name, NamedPropertyDescriptor desc); /// Construct a property map by walking back the chain of hidden classes and /// store it in \c propertyMap_. static void initializeMissingPropertyMap( Handle<HiddenClass> selfHandle, Runtime &runtime); /// Initialize the property map by transferring the parent's map to ourselves /// and adding a our property to it. It must only be called if we don't have a /// property map of our own but have a valid parent with a property map. static void stealPropertyMapFromParent( Handle<HiddenClass> selfHandle, Runtime &runtime); /// Free all non-GC managed resources associated with the object. static void _finalizeImpl(GCCell *cell, GC *gc); /// Mark all the weak references for an object. static void _markWeakImpl(GCCell *cell, WeakRefAcceptor &acceptor); /// \return the amount of non-GC memory being used by the given \p cell, which /// is assumed to be a HiddenClass. static size_t _mallocSizeImpl(GCCell *cell); static std::string _snapshotNameImpl(GCCell *cell, GC *gc); static void _snapshotAddEdgesImpl(GCCell *cell, GC *gc, HeapSnapshot &snap); static void _snapshotAddNodesImpl(GCCell *cell, GC *gc, HeapSnapshot &snap); private: /// The symbol that was added when transitioning to this hidden class. const GCSymbolID symbolID_; /// The flags of the added symbol. const PropertyFlags propertyFlags_; /// Flags associated with this hidden class. ClassFlags flags_{}; /// Total number of properties encoded in the entire chain from this class /// to the root. Note that some transitions do not introduce a new property, /// so this is not the same as the length of the transition chain. /// Before we enter "dictionary mode", this determines the offset of a new /// property. unsigned numProperties_; /// Optional property map of all properties defined by this hidden class. /// This includes \c symbolID_, \c parent_->symbolID_, \c /// parent_->parent_->symbolID_ and so on (in reverse order). /// It is constructed lazily when needed, or is "stolen" from the parent class /// when a transition is performed from the parent class to this one. /// /// NOTE: May be cleared by the GC for any HiddenClass not in a Handle. GCPointer<DictPropertyMap> propertyMap_{}; /// This hash table encodes the transitions from this class to child classes /// keyed on the property being added (or updated) and its flags. detail::TransitionMap transitionMap_; /// The parent hidden class which contains a transition from itself to this /// one keyed on \c symbolID_+propertyFlags_. It can be null if there is no /// parent. GCPointer<HiddenClass> parent_; /// Cache that contains for-in property names for objects of this class. /// Never used in dictionary mode. GCPointer<BigStorage> forInCache_{}; }; //===----------------------------------------------------------------------===// // HiddenClass inline methods. template <typename CallbackFunction> void HiddenClass::forEachProperty( Handle<HiddenClass> selfHandle, Runtime &runtime, const CallbackFunction &callback) { if (LLVM_UNLIKELY(!selfHandle->propertyMap_)) initializeMissingPropertyMap(selfHandle, runtime); return DictPropertyMap::forEachProperty( runtime.makeHandle(selfHandle->propertyMap_), runtime, callback); } template <typename CallbackFunction> bool HiddenClass::forEachPropertyWhile( Handle<HiddenClass> selfHandle, Runtime &runtime, const CallbackFunction &callback) { if (LLVM_UNLIKELY(!selfHandle->propertyMap_)) initializeMissingPropertyMap(selfHandle, runtime); return DictPropertyMap::forEachPropertyWhile( runtime.makeHandle(selfHandle->propertyMap_), runtime, callback); } inline OptValue<bool> HiddenClass::tryFindPropertyFast( const HiddenClass *self, PointerBase &base, SymbolID name, NamedPropertyDescriptor &desc) { if (LLVM_LIKELY(self->propertyMap_)) { auto found = DictPropertyMap::find(self->propertyMap_.getNonNull(base), name); if (LLVM_LIKELY(found)) { desc = DictPropertyMap::getDescriptorPair( self->propertyMap_.getNonNull(base), *found) ->second; } return found.hasValue(); } else if (self->numProperties_ == 0) { return false; } return llvh::None; } } // namespace vm } // namespace hermes // Enable using HiddenClass::Transition in DenseMap. namespace llvh { using namespace hermes::vm; template <> struct DenseMapInfo<HiddenClass::Transition> { static inline HiddenClass::Transition getEmptyKey() { return HiddenClass::Transition(SymbolID::empty()); } static inline HiddenClass::Transition getTombstoneKey() { return HiddenClass::Transition(SymbolID::deleted()); } static inline unsigned getHashValue(HiddenClass::Transition transition) { return transition.symbolID.unsafeGetRaw() ^ transition.propertyFlags._flags; } static inline bool isEqual( const HiddenClass::Transition &a, const HiddenClass::Transition &b) { return a == b; } }; } // namespace llvh #endif // HERMES_VM_HIDDENCLASS_H