diff options
Diffstat (limited to 'js/src/vm/PropMap.cpp')
| -rw-r--r-- | js/src/vm/PropMap.cpp | 1233 |
1 files changed, 1233 insertions, 0 deletions
diff --git a/js/src/vm/PropMap.cpp b/js/src/vm/PropMap.cpp new file mode 100644 index 0000000000..851880f3e6 --- /dev/null +++ b/js/src/vm/PropMap.cpp @@ -0,0 +1,1233 @@ +/* -*- 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/. */ + +#include "vm/PropMap-inl.h" + +#include "gc/Allocator.h" +#include "gc/HashUtil.h" +#include "js/GCVector.h" +#include "vm/JSObject.h" + +#include "gc/GCContext-inl.h" +#include "gc/Marking-inl.h" +#include "vm/ObjectFlags-inl.h" + +using namespace js; + +void PropMap::addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf, + size_t* children, size_t* tables) const { + if (isShared() && asShared()->hasChildrenSet()) { + auto* set = asShared()->treeDataRef().children.toChildrenSet(); + *children += set->shallowSizeOfIncludingThis(mallocSizeOf); + } + if (canHaveTable() && asLinked()->hasTable()) { + *tables += asLinked()->data_.table->sizeOfIncludingThis(mallocSizeOf); + } +} + +// static +SharedPropMap* SharedPropMap::create(JSContext* cx, Handle<SharedPropMap*> prev, + HandleId id, PropertyInfo prop) { + // If the first property has a slot number <= MaxSlotNumber, all properties + // added later will have a slot number <= CompactPropertyInfo::MaxSlotNumber + // so we can use a CompactPropMap. + static constexpr size_t MaxFirstSlot = + CompactPropertyInfo::MaxSlotNumber - (PropMap::Capacity - 1); + + if (!prev && prop.maybeSlot() <= MaxFirstSlot) { + return cx->newCell<CompactPropMap>(id, prop); + } + + return cx->newCell<NormalPropMap>(prev, id, prop); +} + +// static +SharedPropMap* SharedPropMap::createInitial(JSContext* cx, HandleId id, + PropertyInfo prop) { + // Lookup or create a shared map based on the first property. + + using Lookup = InitialPropMapHasher::Lookup; + + auto& table = cx->zone()->shapeZone().initialPropMaps; + + auto p = MakeDependentAddPtr(cx, table, Lookup(id, prop)); + if (p) { + return *p; + } + + SharedPropMap* result = create(cx, /* prev = */ nullptr, id, prop); + if (!result) { + return nullptr; + } + + Lookup lookup(id, prop); + if (!p.add(cx, table, lookup, result)) { + return nullptr; + } + + return result; +} + +// static +SharedPropMap* SharedPropMap::clone(JSContext* cx, Handle<SharedPropMap*> map, + uint32_t length) { + MOZ_ASSERT(length > 0); + + if (map->isCompact()) { + Rooted<CompactPropMap*> prev(cx, map->asCompact()); + return cx->newCell<CompactPropMap>(prev, length); + } + + Rooted<NormalPropMap*> prev(cx, map->asNormal()); + return cx->newCell<NormalPropMap>(prev, length); +} + +// static +DictionaryPropMap* SharedPropMap::toDictionaryMap(JSContext* cx, + Handle<SharedPropMap*> map, + uint32_t length) { + // Starting at the last map, clone each shared map to a new dictionary map. + + Rooted<DictionaryPropMap*> lastDictMap(cx); + Rooted<DictionaryPropMap*> nextDictMap(cx); + + Rooted<SharedPropMap*> sharedMap(cx, map); + uint32_t sharedLength = length; + while (true) { + sharedMap->setHadDictionaryConversion(); + + DictionaryPropMap* dictMap; + if (sharedMap->isCompact()) { + Rooted<CompactPropMap*> prev(cx, sharedMap->asCompact()); + dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength); + } else { + Rooted<NormalPropMap*> prev(cx, sharedMap->asNormal()); + dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength); + } + if (!dictMap) { + return nullptr; + } + + if (!lastDictMap) { + lastDictMap = dictMap; + } + + if (nextDictMap) { + nextDictMap->initPrevious(dictMap); + } + nextDictMap = dictMap; + + if (!sharedMap->hasPrevious()) { + break; + } + sharedMap = sharedMap->asNormal()->previous(); + sharedLength = PropMap::Capacity; + } + + return lastDictMap; +} + +static MOZ_ALWAYS_INLINE SharedPropMap* PropMapChildReadBarrier( + SharedPropMap* parent, SharedPropMap* child) { + JS::Zone* zone = child->zone(); + if (zone->needsIncrementalBarrier()) { + // We need a read barrier for the map tree, since these are weak + // pointers. + ReadBarrier(child); + return child; + } + + if (MOZ_UNLIKELY(zone->isGCSweeping() && + IsAboutToBeFinalizedUnbarriered(child))) { + // The map we've found is unreachable and due to be finalized, so + // remove our weak reference to it and don't use it. + MOZ_ASSERT(parent->isMarkedAny()); + parent->removeChild(zone->runtimeFromMainThread()->gcContext(), child); + return nullptr; + } + + // We don't yield to the mutator when the zone is in this state so we don't + // need to account for it here. + MOZ_ASSERT(!zone->isGCCompacting()); + + return child; +} + +SharedPropMap* SharedPropMap::lookupChild(uint32_t length, HandleId id, + PropertyInfo prop) { + MOZ_ASSERT(length > 0); + + SharedChildrenPtr children = treeDataRef().children; + if (children.isNone()) { + return nullptr; + } + + if (!hasChildrenSet()) { + SharedPropMapAndIndex prevChild = children.toSingleChild(); + if (prevChild.index() == length - 1) { + SharedPropMap* child = prevChild.map(); + uint32_t newPropIndex = indexOfNextProperty(length - 1); + if (child->matchProperty(newPropIndex, id, prop)) { + return PropMapChildReadBarrier(this, child); + } + } + return nullptr; + } + + SharedChildrenSet* set = children.toChildrenSet(); + SharedChildrenHasher::Lookup lookup(id, prop, length - 1); + if (auto p = set->lookup(lookup)) { + MOZ_ASSERT(p->index() == length - 1); + SharedPropMap* child = p->map(); + return PropMapChildReadBarrier(this, child); + } + return nullptr; +} + +bool SharedPropMap::addChild(JSContext* cx, SharedPropMapAndIndex child, + HandleId id, PropertyInfo prop) { + SharedPropMap* childMap = child.map(); + +#ifdef DEBUG + // If the parent map was full, the child map must have the parent as + // |previous| map. Else, the parent and child have the same |previous| map. + if (childMap->hasPrevious()) { + if (child.index() == PropMap::Capacity - 1) { + MOZ_ASSERT(childMap->asLinked()->previous() == this); + } else { + MOZ_ASSERT(childMap->asLinked()->previous() == asLinked()->previous()); + } + } else { + MOZ_ASSERT(!hasPrevious()); + } +#endif + + SharedChildrenPtr& childrenRef = treeDataRef().children; + + if (childrenRef.isNone()) { + childrenRef.setSingleChild(child); + childMap->treeDataRef().setParent(this, child.index()); + return true; + } + + SharedChildrenHasher::Lookup lookup(id, prop, child.index()); + + if (hasChildrenSet()) { + if (!childrenRef.toChildrenSet()->putNew(lookup, child)) { + ReportOutOfMemory(cx); + return false; + } + } else { + auto hash = MakeUnique<SharedChildrenSet>(); + if (!hash || !hash->reserve(2)) { + ReportOutOfMemory(cx); + return false; + } + SharedPropMapAndIndex firstChild = childrenRef.toSingleChild(); + SharedPropMap* firstChildMap = firstChild.map(); + uint32_t firstChildIndex = indexOfNextProperty(firstChild.index()); + SharedChildrenHasher::Lookup lookupFirst( + firstChildMap->getPropertyInfoWithKey(firstChildIndex), + firstChild.index()); + hash->putNewInfallible(lookupFirst, firstChild); + hash->putNewInfallible(lookup, child); + + childrenRef.setChildrenSet(hash.release()); + setHasChildrenSet(); + AddCellMemory(this, sizeof(SharedChildrenSet), MemoryUse::PropMapChildren); + } + + childMap->treeDataRef().setParent(this, child.index()); + return true; +} + +// static +bool SharedPropMap::addProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, ObjectFlags* objectFlags, + uint32_t* slot) { + MOZ_ASSERT(!flags.isCustomDataProperty()); + + *slot = SharedPropMap::slotSpan(clasp, map, *mapLength); + + if (MOZ_UNLIKELY(*slot > SHAPE_MAXIMUM_SLOT)) { + ReportAllocationOverflow(cx); + return false; + } + + *objectFlags = + GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx); + + PropertyInfo prop = PropertyInfo(flags, *slot); + return addPropertyInternal(cx, map, mapLength, id, prop); +} + +// static +bool SharedPropMap::addPropertyInReservedSlot( + JSContext* cx, const JSClass* clasp, MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags) { + MOZ_ASSERT(!flags.isCustomDataProperty()); + + MOZ_ASSERT(slot < JSCLASS_RESERVED_SLOTS(clasp)); + MOZ_ASSERT_IF(map, map->lastUsedSlot(*mapLength) < slot); + + *objectFlags = + GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx); + + PropertyInfo prop = PropertyInfo(flags, slot); + return addPropertyInternal(cx, map, mapLength, id, prop); +} + +// static +bool SharedPropMap::addPropertyWithKnownSlot(JSContext* cx, + const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags) { + MOZ_ASSERT(!flags.isCustomDataProperty()); + + if (MOZ_UNLIKELY(slot < JSCLASS_RESERVED_SLOTS(clasp))) { + return addPropertyInReservedSlot(cx, clasp, map, mapLength, id, flags, slot, + objectFlags); + } + + MOZ_ASSERT(slot == SharedPropMap::slotSpan(clasp, map, *mapLength)); + MOZ_RELEASE_ASSERT(slot <= SHAPE_MAXIMUM_SLOT); + + *objectFlags = + GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx); + + PropertyInfo prop = PropertyInfo(flags, slot); + return addPropertyInternal(cx, map, mapLength, id, prop); +} + +// static +bool SharedPropMap::addCustomDataProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, + ObjectFlags* objectFlags) { + MOZ_ASSERT(flags.isCustomDataProperty()); + + // Custom data properties don't have a slot. Copy the last property's slot + // number to simplify the implementation of SharedPropMap::slotSpan. + uint32_t slot = map ? map->lastUsedSlot(*mapLength) : SHAPE_INVALID_SLOT; + + *objectFlags = + GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx); + + PropertyInfo prop = PropertyInfo(flags, slot); + return addPropertyInternal(cx, map, mapLength, id, prop); +} + +// static +bool SharedPropMap::addPropertyInternal(JSContext* cx, + MutableHandle<SharedPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyInfo prop) { + if (!map) { + // Adding the first property. + MOZ_ASSERT(*mapLength == 0); + map.set(SharedPropMap::createInitial(cx, id, prop)); + if (!map) { + return false; + } + *mapLength = 1; + return true; + } + + MOZ_ASSERT(*mapLength > 0); + + if (*mapLength < PropMap::Capacity) { + // Use the next map entry if possible. + if (!map->hasKey(*mapLength)) { + if (map->canHaveTable()) { + JS::AutoCheckCannotGC nogc; + if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) { + if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) { + return false; + } + } + } + map->initProperty(*mapLength, id, prop); + *mapLength += 1; + return true; + } + if (map->matchProperty(*mapLength, id, prop)) { + *mapLength += 1; + return true; + } + + // The next entry can't be used so look up or create a child map. The child + // map is a clone of this map up to mapLength, with the new property stored + // as the next entry. + + if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) { + map.set(child); + *mapLength += 1; + return true; + } + + SharedPropMap* child = SharedPropMap::clone(cx, map, *mapLength); + if (!child) { + return false; + } + child->initProperty(*mapLength, id, prop); + + SharedPropMapAndIndex childEntry(child, *mapLength - 1); + if (!map->addChild(cx, childEntry, id, prop)) { + return false; + } + + map.set(child); + *mapLength += 1; + return true; + } + + // This map is full so look up or create a child map. + MOZ_ASSERT(*mapLength == PropMap::Capacity); + + if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) { + map.set(child); + *mapLength = 1; + return true; + } + + SharedPropMap* child = SharedPropMap::create(cx, map, id, prop); + if (!child) { + return false; + } + + SharedPropMapAndIndex childEntry(child, PropMap::Capacity - 1); + if (!map->addChild(cx, childEntry, id, prop)) { + return false; + } + + // As an optimization, pass the table to the new child map, unless adding the + // property to it OOMs. Measurements indicate this gets rid of a large number + // of PropMapTable allocations because we don't need to create a second table + // when the parent map won't be used again as last map. + if (map->canHaveTable()) { + JS::AutoCheckCannotGC nogc; + if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) { + // Trigger a pre-barrier on the parent map to appease the pre-barrier + // verifier, because edges from the table are disappearing (even though + // these edges are strictly redundant with the |previous| maps). + gc::PreWriteBarrier(map.get()); + if (table->add(cx, id, PropMapAndIndex(child, 0))) { + map->asLinked()->handOffTableTo(child->asLinked()); + } else { + cx->recoverFromOutOfMemory(); + } + } + } + + map.set(child); + *mapLength = 1; + return true; +} + +static PropertyFlags ComputeFlagsForSealOrFreeze(PropertyKey key, + PropertyFlags flags, + IntegrityLevel level) { + // Private fields are not visible to SetIntegrityLevel. + if (key.isSymbol() && key.toSymbol()->isPrivateName()) { + return flags; + } + + // Make all properties non-configurable; if freezing, make data properties + // read-only. + flags.clearFlag(PropertyFlag::Configurable); + if (level == IntegrityLevel::Frozen && flags.isDataDescriptor()) { + flags.clearFlag(PropertyFlag::Writable); + } + + return flags; +} + +// static +bool SharedPropMap::freezeOrSealProperties(JSContext* cx, IntegrityLevel level, + const JSClass* clasp, + MutableHandle<SharedPropMap*> map, + uint32_t mapLength, + ObjectFlags* objectFlags) { + // Add all maps to a Vector so we can iterate over them in reverse order + // (property definition order). + JS::RootedVector<SharedPropMap*> maps(cx); + { + SharedPropMap* curMap = map; + while (true) { + if (!maps.append(curMap)) { + return false; + } + if (!curMap->hasPrevious()) { + break; + } + curMap = curMap->asNormal()->previous(); + } + } + + // Build a new SharedPropMap by adding each property with the changed + // attributes. + Rooted<SharedPropMap*> newMap(cx); + uint32_t newMapLength = 0; + + Rooted<PropertyKey> key(cx); + Rooted<SharedPropMap*> curMap(cx); + + for (size_t i = maps.length(); i > 0; i--) { + curMap = maps[i - 1]; + uint32_t len = (i == 1) ? mapLength : PropMap::Capacity; + + for (uint32_t j = 0; j < len; j++) { + key = curMap->getKey(j); + PropertyInfo prop = curMap->getPropertyInfo(j); + PropertyFlags flags = + ComputeFlagsForSealOrFreeze(key, prop.flags(), level); + + if (prop.isCustomDataProperty()) { + if (!addCustomDataProperty(cx, clasp, &newMap, &newMapLength, key, + flags, objectFlags)) { + return false; + } + } else { + if (!addPropertyWithKnownSlot(cx, clasp, &newMap, &newMapLength, key, + flags, prop.slot(), objectFlags)) { + return false; + } + } + } + } + + map.set(newMap); + MOZ_ASSERT(newMapLength == mapLength); + return true; +} + +void LinkedPropMap::handOffTableTo(LinkedPropMap* next) { + MOZ_ASSERT(hasTable()); + MOZ_ASSERT(!next->hasTable()); + + next->data_.table = data_.table; + data_.table = nullptr; + + // Note: for tables currently only sizeof(PropMapTable) is tracked. + RemoveCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable); + AddCellMemory(next, sizeof(PropMapTable), MemoryUse::PropMapTable); +} + +void DictionaryPropMap::handOffLastMapStateTo(DictionaryPropMap* newLast) { + // A dictionary object's last map contains the table, slot freeList, and + // holeCount. These fields always have their initial values for non-last maps. + + MOZ_ASSERT(this != newLast); + + if (asLinked()->hasTable()) { + asLinked()->handOffTableTo(newLast->asLinked()); + } + + MOZ_ASSERT(newLast->freeList_ == SHAPE_INVALID_SLOT); + newLast->freeList_ = freeList_; + freeList_ = SHAPE_INVALID_SLOT; + + MOZ_ASSERT(newLast->holeCount_ == 0); + newLast->holeCount_ = holeCount_; + holeCount_ = 0; +} + +// static +bool DictionaryPropMap::addProperty(JSContext* cx, const JSClass* clasp, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, HandleId id, + PropertyFlags flags, uint32_t slot, + ObjectFlags* objectFlags) { + MOZ_ASSERT(map); + + *objectFlags = + GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx); + PropertyInfo prop = PropertyInfo(flags, slot); + + if (*mapLength < PropMap::Capacity) { + JS::AutoCheckCannotGC nogc; + if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) { + if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) { + return false; + } + } + map->initProperty(*mapLength, id, prop); + *mapLength += 1; + return true; + } + + DictionaryPropMap* newMap = cx->newCell<DictionaryPropMap>(map, id, prop); + if (!newMap) { + return false; + } + + JS::AutoCheckCannotGC nogc; + if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) { + if (!table->add(cx, id, PropMapAndIndex(newMap, 0))) { + return false; + } + } + + MOZ_ASSERT(newMap->previous() == map); + map->handOffLastMapStateTo(newMap); + + map.set(newMap); + *mapLength = 1; + return true; +} + +void DictionaryPropMap::changeProperty(JSContext* cx, const JSClass* clasp, + uint32_t index, PropertyFlags flags, + uint32_t slot, + ObjectFlags* objectFlags) { + MOZ_ASSERT(hasKey(index)); + *objectFlags = GetObjectFlagsForNewProperty(clasp, *objectFlags, + getKey(index), flags, cx); + linkedData_.propInfos[index] = PropertyInfo(flags, slot); +} + +void DictionaryPropMap::freezeOrSealProperties(JSContext* cx, + IntegrityLevel level, + const JSClass* clasp, + uint32_t mapLength, + ObjectFlags* objectFlags) { + DictionaryPropMap* curMap = this; + do { + for (uint32_t i = 0; i < mapLength; i++) { + if (!curMap->hasKey(i)) { + continue; + } + PropertyKey key = curMap->getKey(i); + PropertyFlags flags = curMap->getPropertyInfo(i).flags(); + flags = ComputeFlagsForSealOrFreeze(key, flags, level); + curMap->changePropertyFlags(cx, clasp, i, flags, objectFlags); + } + curMap = curMap->previous(); + mapLength = PropMap::Capacity; + } while (curMap); +} + +// static +void DictionaryPropMap::skipTrailingHoles(MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength) { + // After removing a property, rewind map/mapLength so that the last property + // is not a hole. This ensures accessing the last property of a map can always + // be done without checking for holes. + + while (true) { + MOZ_ASSERT(*mapLength > 0); + do { + if (map->hasKey(*mapLength - 1)) { + return; + } + map->decHoleCount(); + *mapLength -= 1; + } while (*mapLength > 0); + + if (!map->previous()) { + // The dictionary map is empty, return the initial map with mapLength 0. + MOZ_ASSERT(*mapLength == 0); + MOZ_ASSERT(map->holeCount_ == 0); + return; + } + + map->handOffLastMapStateTo(map->previous()); + map.set(map->previous()); + *mapLength = PropMap::Capacity; + } +} + +// static +void DictionaryPropMap::removeProperty(JSContext* cx, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, PropMapTable* table, + PropMapTable::Ptr& ptr) { + MOZ_ASSERT(map); + MOZ_ASSERT(*mapLength > 0); + + JS::AutoCheckCannotGC nogc; + MOZ_ASSERT(map->asLinked()->maybeTable(nogc) == table); + + bool removingLast = (map == ptr->map() && *mapLength - 1 == ptr->index()); + ptr->map()->asDictionary()->clearProperty(ptr->index()); + map->incHoleCount(); + table->remove(ptr); + + if (removingLast) { + skipTrailingHoles(map, mapLength); + } + maybeCompact(cx, map, mapLength); +} + +// static +void DictionaryPropMap::densifyElements(JSContext* cx, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength, + NativeObject* obj) { + MOZ_ASSERT(map); + MOZ_ASSERT(*mapLength > 0); + + JS::AutoCheckCannotGC nogc; + PropMapTable* table = map->asLinked()->maybeTable(nogc); + + DictionaryPropMap* currentMap = map; + uint32_t currentLen = *mapLength; + do { + for (uint32_t i = 0; i < currentLen; i++) { + PropertyKey key = currentMap->getKey(i); + uint32_t index; + if (!IdIsIndex(key, &index)) { + continue; + } + + // The caller must have checked all sparse elements are plain data + // properties. + PropertyInfo prop = currentMap->getPropertyInfo(i); + MOZ_ASSERT(prop.flags() == PropertyFlags::defaultDataPropFlags); + + uint32_t slot = prop.slot(); + Value value = obj->getSlot(slot); + obj->setDenseElement(index, value); + obj->freeDictionarySlot(slot); + + if (table) { + PropMapTable::Ptr p = table->lookupRaw(key); + MOZ_ASSERT(p); + table->remove(p); + } + + currentMap->clearProperty(i); + map->incHoleCount(); + } + currentMap = currentMap->previous(); + currentLen = PropMap::Capacity; + } while (currentMap); + + skipTrailingHoles(map, mapLength); + maybeCompact(cx, map, mapLength); +} + +void DictionaryPropMap::maybeCompact(JSContext* cx, + MutableHandle<DictionaryPropMap*> map, + uint32_t* mapLength) { + // If there are no holes, there's nothing to compact. + if (map->holeCount_ == 0) { + return; + } + + JS::AutoCheckCannotGC nogc; + PropMapTable* table = map->asLinked()->ensureTable(cx, nogc); + if (!table) { + // Compacting is optional so just return. + cx->recoverFromOutOfMemory(); + return; + } + + // Heuristic: only compact if the number of holes >= the number of (non-hole) + // entries. + if (map->holeCount_ < table->entryCount()) { + return; + } + + // Add all dictionary maps to a Vector so that we can iterate over them in + // reverse order (property definition order). If appending to the Vector OOMs, + // just return because compacting is optional. + Vector<DictionaryPropMap*, 32, SystemAllocPolicy> maps; + for (DictionaryPropMap* curMap = map; curMap; curMap = curMap->previous()) { + if (!maps.append(curMap)) { + return; + } + } + + // Use two cursors: readMapCursor/readIndexCursor iterates over all properties + // starting at the first one, to search for the next non-hole entry. + // writeMapCursor/writeIndexCursor is used to write all non-hole keys. + // + // At the start of the loop, these cursors point to the next property slot to + // read/write. + + size_t readMapCursorVectorIndex = maps.length() - 1; + DictionaryPropMap* readMapCursor = maps[readMapCursorVectorIndex]; + uint32_t readIndexCursor = 0; + + size_t writeMapCursorVectorIndex = readMapCursorVectorIndex; + DictionaryPropMap* writeMapCursor = readMapCursor; + uint32_t writeIndexCursor = 0; + + mozilla::DebugOnly<uint32_t> numHoles = 0; + + while (true) { + if (readMapCursor->hasKey(readIndexCursor)) { + // Found a non-hole entry, copy it to its new position and update the + // PropMapTable to point to this new entry. Only do this if the read and + // write positions are different from each other. + if (readMapCursor != writeMapCursor || + readIndexCursor != writeIndexCursor) { + PropertyKey key = readMapCursor->getKey(readIndexCursor); + auto p = table->lookupRaw(key); + MOZ_ASSERT(p); + MOZ_ASSERT(p->map() == readMapCursor); + MOZ_ASSERT(p->index() == readIndexCursor); + + writeMapCursor->setKey(writeIndexCursor, key); + writeMapCursor->linkedData_.propInfos[writeIndexCursor] = + readMapCursor->linkedData_.propInfos[readIndexCursor]; + + PropMapAndIndex newEntry(writeMapCursor, writeIndexCursor); + table->replaceEntry(p, key, newEntry); + } + // Advance the write cursor. + writeIndexCursor++; + if (writeIndexCursor == PropMap::Capacity) { + MOZ_ASSERT(writeMapCursorVectorIndex > 0); + writeMapCursorVectorIndex--; + writeMapCursor = maps[writeMapCursorVectorIndex]; + writeIndexCursor = 0; + } + } else { + numHoles++; + } + // Advance the read cursor. If there are no more maps to read from, we're + // done. + readIndexCursor++; + if (readIndexCursor == PropMap::Capacity) { + if (readMapCursorVectorIndex == 0) { + break; + } + readMapCursorVectorIndex--; + readMapCursor = maps[readMapCursorVectorIndex]; + readIndexCursor = 0; + } + } + + // Sanity check: the read cursor skipped holes between properties and holes + // at the end of the last map (these are not included in holeCount_). + MOZ_ASSERT(map->holeCount_ + (PropMap::Capacity - *mapLength) == numHoles); + + // The write cursor points to the next available slot. If this is at the start + // of a new map, use the previous map (which must be full) instead. + if (writeIndexCursor == 0 && writeMapCursor->previous()) { + writeMapCursor = writeMapCursor->previous(); + *mapLength = PropMap::Capacity; + } else { + *mapLength = writeIndexCursor; + } + + // Ensure the last map does not have any keys in [mapLength, Capacity). + for (uint32_t i = *mapLength; i < PropMap::Capacity; i++) { + writeMapCursor->clearProperty(i); + } + + if (writeMapCursor != map) { + map->handOffLastMapStateTo(writeMapCursor); + map.set(writeMapCursor); + } + map->holeCount_ = 0; + + MOZ_ASSERT(*mapLength <= PropMap::Capacity); + MOZ_ASSERT_IF(*mapLength == 0, !map->previous()); + MOZ_ASSERT_IF(!map->previous(), table->entryCount() == *mapLength); +} + +void SharedPropMap::fixupAfterMovingGC() { + SharedChildrenPtr& childrenRef = treeDataRef().children; + if (childrenRef.isNone()) { + return; + } + + if (!hasChildrenSet()) { + SharedPropMapAndIndex child = childrenRef.toSingleChild(); + if (gc::IsForwarded(child.map())) { + child = SharedPropMapAndIndex(gc::Forwarded(child.map()), child.index()); + childrenRef.setSingleChild(child); + } + return; + } + + SharedChildrenSet* set = childrenRef.toChildrenSet(); + for (SharedChildrenSet::Enum e(*set); !e.empty(); e.popFront()) { + SharedPropMapAndIndex child = e.front(); + if (IsForwarded(child.map())) { + child = SharedPropMapAndIndex(Forwarded(child.map()), child.index()); + e.mutableFront() = child; + } + } +} + +void SharedPropMap::removeChild(JS::GCContext* gcx, SharedPropMap* child) { + SharedPropMapAndIndex& parentRef = child->treeDataRef().parent; + MOZ_ASSERT(parentRef.map() == this); + + uint32_t index = parentRef.index(); + parentRef.setNone(); + + SharedChildrenPtr& childrenRef = treeDataRef().children; + MOZ_ASSERT(!childrenRef.isNone()); + + if (!hasChildrenSet()) { + MOZ_ASSERT(childrenRef.toSingleChild().map() == child); + MOZ_ASSERT(childrenRef.toSingleChild().index() == index); + childrenRef.setNone(); + return; + } + + SharedChildrenSet* set = childrenRef.toChildrenSet(); + { + uint32_t nextIndex = SharedPropMap::indexOfNextProperty(index); + SharedChildrenHasher::Lookup lookup( + child->getPropertyInfoWithKey(nextIndex), index); + auto p = set->lookup(lookup); + MOZ_ASSERT(p, "Child must be in children set"); + set->remove(p); + } + + MOZ_ASSERT(set->count() >= 1); + + if (set->count() == 1) { + // Convert from set form back to single child form. + SharedChildrenSet::Range r = set->all(); + SharedPropMapAndIndex remainingChild = r.front(); + childrenRef.setSingleChild(remainingChild); + clearHasChildrenSet(); + gcx->delete_(this, set, MemoryUse::PropMapChildren); + } +} + +void LinkedPropMap::purgeTable(JS::GCContext* gcx) { + MOZ_ASSERT(hasTable()); + gcx->delete_(this, data_.table, MemoryUse::PropMapTable); + data_.table = nullptr; +} + +uint32_t PropMap::approximateEntryCount() const { + // Returns a number that's guaranteed to tbe >= the exact number of properties + // in this map (including previous maps). This is used to reserve space in the + // HashSet when allocating a table for this map. + + const PropMap* map = this; + uint32_t count = 0; + JS::AutoCheckCannotGC nogc; + while (true) { + if (!map->hasPrevious()) { + return count + PropMap::Capacity; + } + if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) { + return count + table->entryCount(); + } + count += PropMap::Capacity; + map = map->asLinked()->previous(); + } +} + +bool PropMapTable::init(JSContext* cx, LinkedPropMap* map) { + if (!set_.reserve(map->approximateEntryCount())) { + ReportOutOfMemory(cx); + return false; + } + + PropMap* curMap = map; + while (true) { + for (uint32_t i = 0; i < PropMap::Capacity; i++) { + if (curMap->hasKey(i)) { + PropertyKey key = curMap->getKey(i); + set_.putNewInfallible(key, PropMapAndIndex(curMap, i)); + } + } + if (!curMap->hasPrevious()) { + break; + } + curMap = curMap->asLinked()->previous(); + } + + return true; +} + +void PropMapTable::trace(JSTracer* trc) { + purgeCache(); + + for (Set::Enum e(set_); !e.empty(); e.popFront()) { + PropMap* map = e.front().map(); + TraceManuallyBarrieredEdge(trc, &map, "PropMapTable map"); + if (map != e.front().map()) { + e.mutableFront() = PropMapAndIndex(map, e.front().index()); + } + } +} + +#ifdef JSGC_HASH_TABLE_CHECKS +void PropMapTable::checkAfterMovingGC() { + for (Set::Enum e(set_); !e.empty(); e.popFront()) { + PropMap* map = e.front().map(); + MOZ_ASSERT(map); + CheckGCThingAfterMovingGC(map); + + PropertyKey key = map->getKey(e.front().index()); + MOZ_RELEASE_ASSERT(!key.isVoid()); + + auto p = lookupRaw(key); + MOZ_RELEASE_ASSERT(p.found() && *p == e.front()); + } +} +#endif + +#ifdef DEBUG +bool LinkedPropMap::canSkipMarkingTable() { + if (!hasTable()) { + return true; + } + + PropMapTable* table = data_.table; + uint32_t count = 0; + + PropMap* map = this; + while (true) { + for (uint32_t i = 0; i < Capacity; i++) { + if (map->hasKey(i)) { + PropertyKey key = map->getKey(i); + PropMapTable::Ptr p = table->readonlyThreadsafeLookup(key); + MOZ_ASSERT(*p == PropMapAndIndex(map, i)); + count++; + } + } + if (!map->hasPrevious()) { + break; + } + map = map->asLinked()->previous(); + } + + return count == table->entryCount(); +} +#endif + +bool LinkedPropMap::createTable(JSContext* cx) { + MOZ_ASSERT(canHaveTable()); + MOZ_ASSERT(!hasTable()); + + UniquePtr<PropMapTable> table = cx->make_unique<PropMapTable>(); + if (!table) { + return false; + } + + if (!table->init(cx, this)) { + return false; + } + + data_.table = table.release(); + // TODO: The contents of PropMapTable is not currently tracked, only the + // object itself. + AddCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable); + return true; +} + +#ifdef DEBUG +void PropMap::dump(js::GenericPrinter& out) const { + out.printf("map @ 0x%p\n", this); + out.printf("previous: 0x%p\n", + hasPrevious() ? asLinked()->previous() : nullptr); + + if (canHaveTable()) { + out.printf("table: 0x%p\n", asLinked()->data_.table); + } else { + out.printf("table: (too small for table)\n"); + } + + if (isShared()) { + out.printf("type: shared\n"); + out.printf(" compact: %s\n", isCompact() ? "yes" : "no"); + SharedPropMapAndIndex parent = asShared()->treeDataRef().parent; + if (parent.isNone()) { + out.printf(" parent: (none)\n"); + } else { + out.printf(" parent: 0x%p [%u]\n", parent.map(), parent.index()); + } + } else { + const DictionaryPropMap* dictMap = asDictionary(); + out.printf("type: dictionary\n"); + out.printf(" freeList: %u\n", dictMap->freeList_); + out.printf(" holeCount: %u\n", dictMap->holeCount_); + } + + out.printf("properties:\n"); + for (uint32_t i = 0; i < Capacity; i++) { + out.printf(" %u: ", i); + + if (!hasKey(i)) { + out.printf("(empty)\n"); + continue; + } + + PropertyKey key = getKey(i); + if (key.isInt()) { + out.printf("[%d]", key.toInt()); + } else if (key.isAtom()) { + EscapedStringPrinter(out, key.toAtom(), '"'); + } else { + MOZ_ASSERT(key.isSymbol()); + key.toSymbol()->dump(out); + } + + PropertyInfo prop = getPropertyInfo(i); + out.printf(" slot %u flags 0x%x ", prop.maybeSlot(), prop.flags().toRaw()); + + if (!prop.flags().isEmpty()) { + bool first = true; + auto dumpFlag = [&](PropertyFlag flag, const char* name) { + if (!prop.flags().hasFlag(flag)) { + return; + } + if (!first) { + out.putChar(' '); + } + out.put(name); + first = false; + }; + out.putChar('('); + dumpFlag(PropertyFlag::Enumerable, "enumerable"); + dumpFlag(PropertyFlag::Configurable, "configurable"); + dumpFlag(PropertyFlag::Writable, "writable"); + dumpFlag(PropertyFlag::AccessorProperty, "accessor"); + dumpFlag(PropertyFlag::CustomDataProperty, "custom-data"); + out.putChar(')'); + } + out.putChar('\n'); + } +} + +void PropMap::dump() const { + Fprinter out(stderr); + dump(out); +} + +void PropMap::checkConsistency(NativeObject* obj) const { + const uint32_t mapLength = obj->shape()->propMapLength(); + MOZ_ASSERT(mapLength <= PropMap::Capacity); + + JS::AutoCheckCannotGC nogc; + if (isDictionary()) { + // Check dictionary slot free list. + for (uint32_t fslot = asDictionary()->freeList(); + fslot != SHAPE_INVALID_SLOT; + fslot = obj->getSlot(fslot).toPrivateUint32()) { + MOZ_ASSERT(fslot < obj->slotSpan()); + } + + auto* table = asLinked()->maybeTable(nogc); + const DictionaryPropMap* curMap = asDictionary(); + uint32_t numHoles = 0; + do { + // Some fields must only be set for the last dictionary map. + if (curMap != this) { + MOZ_ASSERT(!curMap->asLinked()->hasTable()); + MOZ_ASSERT(curMap->holeCount_ == 0); + MOZ_ASSERT(curMap->freeList_ == SHAPE_INVALID_SLOT); + } + + for (uint32_t i = 0; i < PropMap::Capacity; i++) { + if (!curMap->hasKey(i)) { + if (curMap != this || i < mapLength) { + numHoles++; + } + continue; + } + + // The last dictionary map must only have keys up to mapLength. + MOZ_ASSERT_IF(curMap == this, i < mapLength); + + PropertyInfo prop = curMap->getPropertyInfo(i); + MOZ_ASSERT_IF(prop.hasSlot(), prop.slot() < obj->slotSpan()); + + // All properties must be in the table. + if (table) { + PropertyKey key = curMap->getKey(i); + auto p = table->lookupRaw(key); + MOZ_ASSERT(p->map() == curMap); + MOZ_ASSERT(p->index() == i); + } + } + curMap = curMap->previous(); + } while (curMap); + + MOZ_ASSERT(asDictionary()->holeCount_ == numHoles); + return; + } + + MOZ_ASSERT(mapLength > 0); + + const SharedPropMap* curMap = asShared(); + auto* table = + curMap->canHaveTable() ? curMap->asLinked()->maybeTable(nogc) : nullptr; + + // Shared maps without a previous map never have a table. + MOZ_ASSERT_IF(!curMap->hasPrevious(), !curMap->canHaveTable()); + + const SharedPropMap* nextMap = nullptr; + mozilla::Maybe<uint32_t> nextSlot; + while (true) { + // Verify numPreviousMaps is set correctly. + MOZ_ASSERT_IF(nextMap && nextMap->numPreviousMaps() != NumPreviousMapsMax, + curMap->numPreviousMaps() + 1 == nextMap->numPreviousMaps()); + MOZ_ASSERT(curMap->hasPrevious() == (curMap->numPreviousMaps() > 0)); + + // If a previous map also has a table, it must have fewer entries than the + // last map's table. + if (table && curMap != this && curMap->canHaveTable()) { + if (auto* table2 = curMap->asLinked()->maybeTable(nogc)) { + MOZ_ASSERT(table2->entryCount() < table->entryCount()); + } + } + + for (int32_t i = PropMap::Capacity - 1; i >= 0; i--) { + uint32_t index = uint32_t(i); + + // Only the last map can have holes, for entries following mapLength. + if (!curMap->hasKey(index)) { + MOZ_ASSERT(index > 0); + MOZ_ASSERT(curMap == this); + MOZ_ASSERT(index >= mapLength); + continue; + } + + // Check slot numbers are within slot span and never decreasing. + PropertyInfo prop = curMap->getPropertyInfo(i); + if (prop.hasSlot()) { + MOZ_ASSERT_IF((curMap != this || index < mapLength), + prop.slot() < obj->slotSpan()); + MOZ_ASSERT_IF(nextSlot.isSome(), *nextSlot >= prop.slot()); + nextSlot = mozilla::Some(prop.slot()); + } + + // All properties must be in the table. + if (table) { + PropertyKey key = curMap->getKey(index); + auto p = table->lookupRaw(key); + MOZ_ASSERT(p->map() == curMap); + MOZ_ASSERT(p->index() == index); + } + } + + if (!curMap->hasPrevious()) { + break; + } + nextMap = curMap; + curMap = curMap->asLinked()->previous()->asShared(); + } +} +#endif // DEBUG + +JS::ubi::Node::Size JS::ubi::Concrete<PropMap>::size( + mozilla::MallocSizeOf mallocSizeOf) const { + Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind()); + size_t children = 0; + size_t tables = 0; + get().addSizeOfExcludingThis(mallocSizeOf, &children, &tables); + return size + children + tables; +} |