diff options
Diffstat (limited to '')
| -rw-r--r-- | js/src/vm/Shape.cpp | 2224 |
1 files changed, 2224 insertions, 0 deletions
diff --git a/js/src/vm/Shape.cpp b/js/src/vm/Shape.cpp new file mode 100644 index 0000000000..406af24c3a --- /dev/null +++ b/js/src/vm/Shape.cpp @@ -0,0 +1,2224 @@ +/* -*- 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/. */ + +/* JS symbol tables. */ + +#include "vm/Shape-inl.h" + +#include "mozilla/MathAlgorithms.h" +#include "mozilla/PodOperations.h" + +#include "gc/FreeOp.h" +#include "gc/HashUtil.h" +#include "gc/Policy.h" +#include "gc/PublicIterators.h" +#include "js/HashTable.h" +#include "js/UniquePtr.h" +#include "util/Text.h" +#include "vm/JSAtom.h" +#include "vm/JSContext.h" +#include "vm/JSObject.h" + +#include "vm/Caches-inl.h" +#include "vm/JSContext-inl.h" +#include "vm/JSObject-inl.h" +#include "vm/NativeObject-inl.h" +#include "vm/Realm-inl.h" + +using namespace js; + +using mozilla::CeilingLog2Size; +using mozilla::PodZero; + +using JS::AutoCheckCannotGC; + +Shape* const ShapeTable::Entry::SHAPE_REMOVED = + (Shape*)ShapeTable::Entry::SHAPE_COLLISION; + +bool ShapeIC::init(JSContext* cx) { + size_ = MAX_SIZE; + entries_.reset(cx->pod_calloc<Entry>(size_)); + return (!entries_) ? false : true; +} + +bool ShapeTable::init(JSContext* cx, Shape* lastProp) { + uint32_t sizeLog2 = CeilingLog2Size(entryCount_); + uint32_t size = Bit(sizeLog2); + if (entryCount_ >= size - (size >> 2)) { + sizeLog2++; + } + if (sizeLog2 < MIN_SIZE_LOG2) { + sizeLog2 = MIN_SIZE_LOG2; + } + + size = Bit(sizeLog2); + entries_.reset(cx->pod_calloc<Entry>(size)); + if (!entries_) { + return false; + } + + MOZ_ASSERT(sizeLog2 <= HASH_BITS); + hashShift_ = HASH_BITS - sizeLog2; + + for (Shape::Range<NoGC> r(lastProp); !r.empty(); r.popFront()) { + Shape& shape = r.front(); + Entry& entry = searchUnchecked<MaybeAdding::Adding>(shape.propid()); + + /* + * Beware duplicate args and arg vs. var conflicts: the youngest shape + * (nearest to lastProp) must win. See bug 600067. + */ + if (!entry.shape()) { + entry.setPreservingCollision(&shape); + } + } + + MOZ_ASSERT(capacity() == size); + MOZ_ASSERT(size >= MIN_SIZE); + MOZ_ASSERT(!needsToGrow()); + return true; +} + +void Shape::removeFromDictionary(NativeObject* obj) { + MOZ_ASSERT(inDictionary()); + MOZ_ASSERT(obj->inDictionaryMode()); + MOZ_ASSERT(!dictNext.isNone()); + + MOZ_ASSERT(obj->shape()->inDictionary()); + MOZ_ASSERT(obj->shape()->dictNext.toObject() == obj); + + if (parent) { + parent->setDictionaryNextPtr(dictNext); + } + *dictNext.prevPtr() = parent; + clearDictionaryNextPtr(); + + obj->shape()->clearCachedBigEnoughForShapeTable(); +} + +void Shape::insertIntoDictionaryBefore(DictionaryShapeLink next) { + // Don't assert inDictionaryMode() here because we may be called from + // NativeObject::toDictionaryMode via Shape::initDictionaryShape. + MOZ_ASSERT(inDictionary()); + MOZ_ASSERT(dictNext.isNone()); + + Shape* prev = *next.prevPtr(); + +#ifdef DEBUG + if (prev) { + MOZ_ASSERT(prev->inDictionary()); + MOZ_ASSERT(prev->dictNext == next); + MOZ_ASSERT(zone() == prev->zone()); + } +#endif + + setParent(prev); + if (parent) { + parent->setNextDictionaryShape(this); + } + + setDictionaryNextPtr(next); + *dictNext.prevPtr() = this; +} + +bool Shape::makeOwnBaseShape(JSContext* cx) { + MOZ_ASSERT(!base()->isOwned()); + MOZ_ASSERT(cx->zone() == zone()); + + BaseShape* nbase = Allocate<BaseShape, NoGC>(cx); + if (!nbase) { + return false; + } + + new (nbase) BaseShape(StackBaseShape(this)); + nbase->setOwned(base()->toUnowned()); + + setBase(nbase); + + return true; +} + +void Shape::handoffTableTo(Shape* shape) { + MOZ_ASSERT(inDictionary() && shape->inDictionary()); + + if (this == shape) { + return; + } + + MOZ_ASSERT(base()->isOwned() && !shape->base()->isOwned()); + + BaseShape* nbase = base(); + + setBase(nbase->baseUnowned()); + nbase->adoptUnowned(shape->base()->toUnowned()); + + shape->setBase(nbase); +} + +/* static */ +bool Shape::hashify(JSContext* cx, Shape* shape) { + MOZ_ASSERT(!shape->hasTable()); + + if (!shape->ensureOwnBaseShape(cx)) { + return false; + } + + UniquePtr<ShapeTable> table = + cx->make_unique<ShapeTable>(shape->entryCount()); + if (!table) { + return false; + } + + if (!table->init(cx, shape)) { + return false; + } + + BaseShape* base = shape->base(); + base->maybePurgeCache(cx->defaultFreeOp()); + base->setTable(table.release()); + // TODO: The contents of ShapeTable is not currently tracked, only the object + // itself. + AddCellMemory(base, sizeof(ShapeTable), MemoryUse::ShapeCache); + return true; +} + +void ShapeCachePtr::maybePurgeCache(JSFreeOp* fop, BaseShape* base) { + if (isTable()) { + ShapeTable* table = getTablePointer(); + if (table->freeList() == SHAPE_INVALID_SLOT) { + fop->delete_(base, getTablePointer(), MemoryUse::ShapeCache); + p = 0; + } + } else if (isIC()) { + fop->delete_<ShapeIC>(base, getICPointer(), MemoryUse::ShapeCache); + p = 0; + } +} + +/* static */ +bool Shape::cachify(JSContext* cx, Shape* shape) { + MOZ_ASSERT(!shape->hasTable() && !shape->hasIC()); + + if (!shape->ensureOwnBaseShape(cx)) { + return false; + } + + UniquePtr<ShapeIC> ic = cx->make_unique<ShapeIC>(); + if (!ic) { + return false; + } + + if (!ic->init(cx)) { + return false; + } + + shape->base()->setIC(ic.release()); + AddCellMemory(shape->base(), sizeof(ShapeIC), MemoryUse::ShapeCache); + return true; +} + +bool ShapeTable::change(JSContext* cx, int log2Delta) { + MOZ_ASSERT(entries_); + MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1); + + /* + * Grow, shrink, or compress by changing this->entries_. + */ + uint32_t oldLog2 = HASH_BITS - hashShift_; + uint32_t newLog2 = oldLog2 + log2Delta; + uint32_t oldSize = Bit(oldLog2); + uint32_t newSize = Bit(newLog2); + Entry* newTable = cx->maybe_pod_calloc<Entry>(newSize); + if (!newTable) { + return false; + } + + /* Now that we have newTable allocated, update members. */ + MOZ_ASSERT(newLog2 <= HASH_BITS); + hashShift_ = HASH_BITS - newLog2; + removedCount_ = 0; + Entry* oldTable = entries_.release(); + entries_.reset(newTable); + + /* Copy only live entries, leaving removed and free ones behind. */ + AutoCheckCannotGC nogc; + for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) { + if (Shape* shape = oldEntry->shape()) { + Entry& entry = search<MaybeAdding::Adding>(shape->propid(), nogc); + MOZ_ASSERT(entry.isFree()); + entry.setShape(shape); + } + oldSize--; + } + + MOZ_ASSERT(capacity() == newSize); + + /* Finally, free the old entries storage. */ + js_free(oldTable); + return true; +} + +bool ShapeTable::grow(JSContext* cx) { + MOZ_ASSERT(needsToGrow()); + + uint32_t size = capacity(); + int delta = removedCount_ < (size >> 2); + + MOZ_ASSERT(entryCount_ + removedCount_ <= size - 1); + + if (!change(cx, delta)) { + if (entryCount_ + removedCount_ == size - 1) { + ReportOutOfMemory(cx); + return false; + } + } + + return true; +} + +void ShapeCachePtr::trace(JSTracer* trc) { + if (isIC()) { + getICPointer()->trace(trc); + } else if (isTable()) { + getTablePointer()->trace(trc); + } +} + +void ShapeIC::trace(JSTracer* trc) { + for (size_t i = 0; i < entryCount(); i++) { + Entry& entry = entries_[i]; + if (entry.shape_) { + TraceManuallyBarrieredEdge(trc, &entry.shape_, "ShapeIC shape"); + } + } +} + +void ShapeTable::trace(JSTracer* trc) { + for (size_t i = 0; i < capacity(); i++) { + Entry& entry = getEntry(i); + Shape* shape = entry.shape(); + if (shape) { + TraceManuallyBarrieredEdge(trc, &shape, "ShapeTable shape"); + if (shape != entry.shape()) { + entry.setPreservingCollision(shape); + } + } + } +} + +inline void ShapeCachePtr::destroy(JSFreeOp* fop, BaseShape* base) { + if (isTable()) { + fop->delete_(base, getTablePointer(), MemoryUse::ShapeCache); + } else if (isIC()) { + fop->delete_(base, getICPointer(), MemoryUse::ShapeCache); + } + p = 0; +} + +#ifdef JSGC_HASH_TABLE_CHECKS + +void ShapeCachePtr::checkAfterMovingGC() { + if (isIC()) { + getICPointer()->checkAfterMovingGC(); + } else if (isTable()) { + getTablePointer()->checkAfterMovingGC(); + } +} + +void ShapeIC::checkAfterMovingGC() { + for (size_t i = 0; i < entryCount(); i++) { + Entry& entry = entries_[i]; + Shape* shape = entry.shape_; + if (shape) { + CheckGCThingAfterMovingGC(shape); + } + } +} + +void ShapeTable::checkAfterMovingGC() { + for (size_t i = 0; i < capacity(); i++) { + Entry& entry = getEntry(i); + Shape* shape = entry.shape(); + if (shape) { + CheckGCThingAfterMovingGC(shape); + } + } +} + +#endif + +/* static */ +Shape* Shape::replaceLastProperty(JSContext* cx, StackBaseShape& base, + TaggedProto proto, HandleShape shape) { + MOZ_ASSERT(!shape->inDictionary()); + + if (!shape->parent) { + /* Treat as resetting the initial property of the shape hierarchy. */ + gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots()); + return EmptyShape::getInitialShape( + cx, base.clasp, proto, kind, base.flags & BaseShape::OBJECT_FLAG_MASK); + } + + UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base); + if (!nbase) { + return nullptr; + } + + Rooted<StackShape> child(cx, StackShape(shape)); + child.setBase(nbase); + + return cx->zone()->propertyTree().getChild(cx, shape->parent, child); +} + +/* + * Get or create a property-tree or dictionary child property of |parent|, + * which must be lastProperty() if inDictionaryMode(), else parent must be + * one of lastProperty() or lastProperty()->parent. + */ +/* static */ MOZ_ALWAYS_INLINE Shape* NativeObject::getChildDataProperty( + JSContext* cx, HandleNativeObject obj, HandleShape parent, + MutableHandle<StackShape> child) { + MOZ_ASSERT(child.isDataProperty()); + + if (child.hasMissingSlot()) { + uint32_t slot; + if (obj->inDictionaryMode()) { + if (!allocDictionarySlot(cx, obj, &slot)) { + return nullptr; + } + } else { + slot = obj->slotSpan(); + MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass())); + // Objects with many properties are converted to dictionary + // mode, so we can't overflow SHAPE_MAXIMUM_SLOT here. + MOZ_ASSERT(slot < + JSSLOT_FREE(obj->getClass()) + PropertyTree::MAX_HEIGHT); + MOZ_ASSERT(slot < SHAPE_MAXIMUM_SLOT); + } + child.setSlot(slot); + } else { + /* + * Slots can only be allocated out of order on objects in + * dictionary mode. Otherwise the child's slot must be after the + * parent's slot (if it has one), because slot number determines + * slot span for objects with that shape. Usually child slot + * *immediately* follows parent slot, but there may be a slot gap + * when the object uses some -- but not all -- of its reserved + * slots to store properties. + */ + MOZ_ASSERT(obj->inDictionaryMode() || parent->hasMissingSlot() || + child.slot() == parent->maybeSlot() + 1 || + (parent->maybeSlot() + 1 < JSSLOT_FREE(obj->getClass()) && + child.slot() == JSSLOT_FREE(obj->getClass()))); + } + + if (obj->inDictionaryMode()) { + MOZ_ASSERT(parent == obj->lastProperty()); + Shape* shape = Allocate<Shape>(cx); + if (!shape) { + return nullptr; + } + if (child.slot() >= obj->slotSpan()) { + if (!obj->ensureSlotsForDictionaryObject(cx, child.slot() + 1)) { + new (shape) Shape(obj->lastProperty()->base()->unowned(), 0); + return nullptr; + } + } + shape->initDictionaryShape(child, obj->numFixedSlots(), + DictionaryShapeLink(obj)); + return shape; + } + + Shape* shape = cx->zone()->propertyTree().inlinedGetChild(cx, parent, child); + if (!shape) { + return nullptr; + } + + MOZ_ASSERT(shape->parent == parent); + MOZ_ASSERT_IF(parent != obj->lastProperty(), + parent == obj->lastProperty()->parent); + + if (!obj->setLastProperty(cx, shape)) { + return nullptr; + } + return shape; +} + +/* static */ MOZ_ALWAYS_INLINE Shape* NativeObject::getChildAccessorProperty( + JSContext* cx, HandleNativeObject obj, HandleShape parent, + MutableHandle<StackShape> child) { + MOZ_ASSERT(!child.isDataProperty()); + + // Accessor properties have no slot, but slot_ will reflect that of parent. + child.setSlot(parent->maybeSlot()); + + if (obj->inDictionaryMode()) { + MOZ_ASSERT(parent == obj->lastProperty()); + Shape* shape = Allocate<AccessorShape>(cx); + if (!shape) { + return nullptr; + } + shape->initDictionaryShape(child, obj->numFixedSlots(), + DictionaryShapeLink(obj)); + return shape; + } + + Shape* shape = cx->zone()->propertyTree().inlinedGetChild(cx, parent, child); + if (!shape) { + return nullptr; + } + + MOZ_ASSERT(shape->parent == parent); + MOZ_ASSERT_IF(parent != obj->lastProperty(), + parent == obj->lastProperty()->parent); + + if (!obj->setLastProperty(cx, shape)) { + return nullptr; + } + return shape; +} + +/* static */ +bool js::NativeObject::toDictionaryMode(JSContext* cx, HandleNativeObject obj) { + MOZ_ASSERT(!obj->inDictionaryMode()); + MOZ_ASSERT(cx->isInsideCurrentCompartment(obj)); + + uint32_t span = obj->slotSpan(); + + // Clone the shapes into a new dictionary list. Don't update the last + // property of this object until done, otherwise a GC triggered while + // creating the dictionary will get the wrong slot span for this object. + RootedShape root(cx); + RootedShape dictionaryShape(cx); + + RootedShape shape(cx, obj->lastProperty()); + while (shape) { + MOZ_ASSERT(!shape->inDictionary()); + + Shape* dprop = shape->isAccessorShape() ? Allocate<AccessorShape>(cx) + : Allocate<Shape>(cx); + if (!dprop) { + ReportOutOfMemory(cx); + return false; + } + + DictionaryShapeLink next; + if (dictionaryShape) { + next.setShape(dictionaryShape); + } + StackShape child(shape); + dprop->initDictionaryShape(child, obj->numFixedSlots(), next); + + if (!dictionaryShape) { + root = dprop; + } + + MOZ_ASSERT(!dprop->hasTable()); + dictionaryShape = dprop; + shape = shape->previous(); + } + + if (!Shape::hashify(cx, root)) { + ReportOutOfMemory(cx); + return false; + } + + if (IsInsideNursery(obj) && + !cx->nursery().queueDictionaryModeObjectToSweep(obj)) { + ReportOutOfMemory(cx); + return false; + } + + MOZ_ASSERT(root->dictNext.isNone()); + root->setDictionaryObject(obj); + obj->setShape(root); + + MOZ_ASSERT(obj->inDictionaryMode()); + obj->setDictionaryModeSlotSpan(span); + + return true; +} + +static bool ShouldConvertToDictionary(NativeObject* obj) { + /* + * Use a lower limit if this object is likely a hashmap (SETELEM was used + * to set properties). + */ + if (obj->hadElementsAccess()) { + return obj->lastProperty()->entryCount() >= + PropertyTree::MAX_HEIGHT_WITH_ELEMENTS_ACCESS; + } + return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT; +} + +static MOZ_ALWAYS_INLINE UnownedBaseShape* GetBaseShapeForNewShape( + JSContext* cx, HandleShape last, HandleId id) { + uint32_t index; + bool indexed = IdIsIndex(id, &index); + bool interestingSymbol = + JSID_IS_SYMBOL(id) && JSID_TO_SYMBOL(id)->isInterestingSymbol(); + + if (MOZ_LIKELY(!indexed && !interestingSymbol)) { + return last->base()->unowned(); + } + + StackBaseShape base(last->base()); + if (indexed) { + base.flags |= BaseShape::INDEXED; + } else if (interestingSymbol) { + base.flags |= BaseShape::HAS_INTERESTING_SYMBOL; + } + return BaseShape::getUnowned(cx, base); +} + +namespace js { + +class MOZ_RAII AutoCheckShapeConsistency { +#ifdef DEBUG + HandleNativeObject obj_; +#endif + + public: + explicit AutoCheckShapeConsistency(HandleNativeObject obj) +#ifdef DEBUG + : obj_(obj) +#endif + { + } + +#ifdef DEBUG + ~AutoCheckShapeConsistency() { obj_->checkShapeConsistency(); } +#endif +}; + +} // namespace js + +/* static */ MOZ_ALWAYS_INLINE bool +NativeObject::maybeConvertToOrGrowDictionaryForAdd( + JSContext* cx, HandleNativeObject obj, HandleId id, ShapeTable** table, + ShapeTable::Entry** entry, const AutoKeepShapeCaches& keep) { + MOZ_ASSERT(!!*table == !!*entry); + + // The code below deals with either converting obj to dictionary mode or + // growing an object that's already in dictionary mode. + if (!obj->inDictionaryMode()) { + if (!ShouldConvertToDictionary(obj)) { + return true; + } + if (!toDictionaryMode(cx, obj)) { + return false; + } + *table = obj->lastProperty()->maybeTable(keep); + } else { + if (!(*table)->needsToGrow()) { + return true; + } + if (!(*table)->grow(cx)) { + return false; + } + } + + *entry = &(*table)->search<MaybeAdding::Adding>(id, keep); + MOZ_ASSERT(!(*entry)->shape()); + return true; +} + +MOZ_ALWAYS_INLINE void Shape::updateDictionaryTable( + ShapeTable* table, ShapeTable::Entry* entry, + const AutoKeepShapeCaches& keep) { + MOZ_ASSERT(table); + MOZ_ASSERT(entry); + MOZ_ASSERT(inDictionary()); + + // Store this Shape in the table entry. + entry->setPreservingCollision(this); + table->incEntryCount(); + + // Pass the table along to the new last property, namely *this. + MOZ_ASSERT(parent->maybeTable(keep) == table); + parent->handoffTableTo(this); +} + +static void AssertValidPropertyOp(NativeObject* obj, GetterOp getter, + SetterOp setter, unsigned attrs) { + // We only support PropertyOp accessors on ArrayObject and ArgumentsObject + // and we don't want to add more of these properties (bug 1404885). + +#ifdef DEBUG + if ((getter && !(attrs & JSPROP_GETTER)) || + (setter && !(attrs & JSPROP_SETTER))) { + MOZ_ASSERT(obj->is<ArrayObject>() || obj->is<ArgumentsObject>()); + } +#endif +} + +/* static */ +Shape* NativeObject::addAccessorPropertyInternal( + JSContext* cx, HandleNativeObject obj, HandleId id, GetterOp getter, + SetterOp setter, unsigned attrs, ShapeTable* table, + ShapeTable::Entry* entry, const AutoKeepShapeCaches& keep) { + AutoCheckShapeConsistency check(obj); + AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter); + + AssertValidPropertyOp(obj, getter, setter, attrs); + + if (!maybeConvertToOrGrowDictionaryForAdd(cx, obj, id, &table, &entry, + keep)) { + return nullptr; + } + + // Find or create a property tree node labeled by our arguments. + RootedShape shape(cx); + { + RootedShape last(cx, obj->lastProperty()); + Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, last, id)); + if (!nbase) { + return nullptr; + } + + Rooted<StackShape> child(cx, + StackShape(nbase, id, SHAPE_INVALID_SLOT, attrs)); + child.updateGetterSetter(getter, setter); + shape = getChildAccessorProperty(cx, obj, last, &child); + if (!shape) { + return nullptr; + } + } + + MOZ_ASSERT(shape == obj->lastProperty()); + + if (table) { + shape->updateDictionaryTable(table, entry, keep); + } + + return shape; +} + +/* static */ +Shape* NativeObject::addDataPropertyInternal(JSContext* cx, + HandleNativeObject obj, + HandleId id, uint32_t slot, + unsigned attrs, ShapeTable* table, + ShapeTable::Entry* entry, + const AutoKeepShapeCaches& keep) { + AutoCheckShapeConsistency check(obj); + + // The slot, if any, must be a reserved slot. + MOZ_ASSERT(slot == SHAPE_INVALID_SLOT || + slot < JSCLASS_RESERVED_SLOTS(obj->getClass())); + + if (!maybeConvertToOrGrowDictionaryForAdd(cx, obj, id, &table, &entry, + keep)) { + return nullptr; + } + + // Find or create a property tree node labeled by our arguments. + RootedShape shape(cx); + { + RootedShape last(cx, obj->lastProperty()); + Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, last, id)); + if (!nbase) { + return nullptr; + } + + Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs)); + shape = getChildDataProperty(cx, obj, last, &child); + if (!shape) { + return nullptr; + } + } + + MOZ_ASSERT(shape == obj->lastProperty()); + + if (table) { + shape->updateDictionaryTable(table, entry, keep); + } + + return shape; +} + +static MOZ_ALWAYS_INLINE Shape* PropertyTreeReadBarrier(JSContext* cx, + Shape* parent, + Shape* shape) { + JS::Zone* zone = shape->zone(); + if (zone->needsIncrementalBarrier()) { + // We need a read barrier for the shape tree, since these are weak + // pointers. + Shape* tmp = shape; + TraceManuallyBarrieredEdge(zone->barrierTracer(), &tmp, "read barrier"); + MOZ_ASSERT(tmp == shape); + return shape; + } + + if (MOZ_LIKELY(!zone->isGCSweepingOrCompacting() || + !IsAboutToBeFinalizedUnbarriered(&shape))) { + if (shape->isMarkedGray()) { + UnmarkGrayShapeRecursively(shape); + } + return shape; + } + + // The shape 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(cx->defaultFreeOp(), shape); + + return nullptr; +} + +/* static */ +Shape* NativeObject::addEnumerableDataProperty(JSContext* cx, + HandleNativeObject obj, + HandleId id) { + // Like addProperty(Internal), but optimized for the common case of adding a + // new enumerable data property. + + AutoCheckShapeConsistency check(obj); + + // Fast path for non-dictionary shapes with a single child. + do { + AutoCheckCannotGC nogc; + + Shape* lastProperty = obj->lastProperty(); + if (lastProperty->inDictionary()) { + break; + } + + ShapeChildren* childp = &lastProperty->children; + if (!childp->isSingleShape()) { + break; + } + + Shape* child = childp->toSingleShape(); + MOZ_ASSERT(!child->inDictionary()); + + if (child->propidRaw() != id || child->isAccessorShape() || + child->attributes() != JSPROP_ENUMERATE || + child->base()->unowned() != lastProperty->base()->unowned()) { + break; + } + + MOZ_ASSERT(child->isDataProperty()); + + child = PropertyTreeReadBarrier(cx, lastProperty, child); + if (!child) { + break; + } + + if (!obj->setLastProperty(cx, child)) { + return nullptr; + } + return child; + } while (0); + + AutoKeepShapeCaches keep(cx); + ShapeTable* table = nullptr; + ShapeTable::Entry* entry = nullptr; + + if (!obj->inDictionaryMode()) { + if (MOZ_UNLIKELY(ShouldConvertToDictionary(obj))) { + if (!toDictionaryMode(cx, obj)) { + return nullptr; + } + table = obj->lastProperty()->maybeTable(keep); + entry = &table->search<MaybeAdding::Adding>(id, keep); + } + } else { + table = obj->lastProperty()->ensureTableForDictionary(cx, keep); + if (!table) { + return nullptr; + } + if (table->needsToGrow()) { + if (!table->grow(cx)) { + return nullptr; + } + } + entry = &table->search<MaybeAdding::Adding>(id, keep); + MOZ_ASSERT(!entry->shape()); + } + + MOZ_ASSERT(!!table == !!entry); + + /* Find or create a property tree node labeled by our arguments. */ + RootedShape last(cx, obj->lastProperty()); + UnownedBaseShape* nbase = GetBaseShapeForNewShape(cx, last, id); + if (!nbase) { + return nullptr; + } + + Shape* shape; + if (obj->inDictionaryMode()) { + uint32_t slot; + if (!allocDictionarySlot(cx, obj, &slot)) { + return nullptr; + } + + Rooted<StackShape> child(cx, StackShape(nbase, id, slot, JSPROP_ENUMERATE)); + + MOZ_ASSERT(last == obj->lastProperty()); + shape = Allocate<Shape>(cx); + if (!shape) { + return nullptr; + } + if (slot >= obj->slotSpan()) { + if (MOZ_UNLIKELY(!obj->ensureSlotsForDictionaryObject(cx, slot + 1))) { + new (shape) Shape(obj->lastProperty()->base()->unowned(), 0); + return nullptr; + } + } + shape->initDictionaryShape(child, obj->numFixedSlots(), + DictionaryShapeLink(obj)); + } else { + uint32_t slot = obj->slotSpan(); + MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass())); + // Objects with many properties are converted to dictionary + // mode, so we can't overflow SHAPE_MAXIMUM_SLOT here. + MOZ_ASSERT(slot < JSSLOT_FREE(obj->getClass()) + PropertyTree::MAX_HEIGHT); + MOZ_ASSERT(slot < SHAPE_MAXIMUM_SLOT); + + Rooted<StackShape> child(cx, StackShape(nbase, id, slot, JSPROP_ENUMERATE)); + shape = cx->zone()->propertyTree().inlinedGetChild(cx, last, child); + if (!shape) { + return nullptr; + } + if (!obj->setLastProperty(cx, shape)) { + return nullptr; + } + } + + MOZ_ASSERT(shape == obj->lastProperty()); + + if (table) { + shape->updateDictionaryTable(table, entry, keep); + } + + return shape; +} + +/* + * Assert some invariants that should hold when changing properties. It's the + * responsibility of the callers to ensure these hold. + */ +static void AssertCanChangeAttrs(Shape* shape, unsigned attrs) { +#ifdef DEBUG + if (shape->configurable()) { + return; + } + + /* A permanent property must stay permanent. */ + MOZ_ASSERT(attrs & JSPROP_PERMANENT); + + /* Reject attempts to remove a slot from the permanent data property. */ + MOZ_ASSERT_IF(shape->isDataProperty(), + !(attrs & (JSPROP_GETTER | JSPROP_SETTER))); +#endif +} + +static void AssertValidArrayIndex(NativeObject* obj, jsid id) { +#ifdef DEBUG + if (obj->is<ArrayObject>()) { + ArrayObject* arr = &obj->as<ArrayObject>(); + uint32_t index; + if (IdIsIndex(id, &index)) { + MOZ_ASSERT(index < arr->length() || arr->lengthIsWritable()); + } + } +#endif +} + +/* static */ +bool NativeObject::maybeToDictionaryModeForPut(JSContext* cx, + HandleNativeObject obj, + MutableHandleShape shape) { + // Overwriting a non-last property requires switching to dictionary mode. + // The shape tree is shared immutable, and we can't removeProperty and then + // addAccessorPropertyInternal because a failure under add would lose data. + + if (shape == obj->lastProperty() || obj->inDictionaryMode()) { + return true; + } + + if (!toDictionaryMode(cx, obj)) { + return false; + } + + AutoCheckCannotGC nogc; + ShapeTable* table = obj->lastProperty()->maybeTable(nogc); + MOZ_ASSERT(table); + shape.set( + table->search<MaybeAdding::NotAdding>(shape->propid(), nogc).shape()); + return true; +} + +/* static */ +Shape* NativeObject::putDataProperty(JSContext* cx, HandleNativeObject obj, + HandleId id, unsigned attrs) { + MOZ_ASSERT(!JSID_IS_VOID(id)); + + AutoCheckShapeConsistency check(obj); + AssertValidArrayIndex(obj, id); + + // Search for id in order to claim its entry if table has been allocated. + AutoKeepShapeCaches keep(cx); + RootedShape shape(cx); + { + ShapeTable* table; + ShapeTable::Entry* entry; + if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep, + shape.address(), &table, &entry)) { + return nullptr; + } + + if (!shape) { + MOZ_ASSERT( + obj->isExtensible() || + (JSID_IS_INT(id) && obj->containsDenseElement(JSID_TO_INT(id))), + "Can't add new property to non-extensible object"); + return addDataPropertyInternal(cx, obj, id, SHAPE_INVALID_SLOT, attrs, + table, entry, keep); + } + + // Property exists: search must have returned a valid entry. + MOZ_ASSERT_IF(entry, !entry->isRemoved()); + } + + AssertCanChangeAttrs(shape, attrs); + + // If the caller wants to allocate a slot, but doesn't care which slot, + // copy the existing shape's slot into slot so we can match shape, if all + // other members match. + bool hadSlot = shape->isDataProperty(); + uint32_t oldSlot = shape->maybeSlot(); + uint32_t slot = hadSlot ? oldSlot : SHAPE_INVALID_SLOT; + + Rooted<UnownedBaseShape*> nbase(cx); + { + RootedShape shape(cx, obj->lastProperty()); + nbase = GetBaseShapeForNewShape(cx, shape, id); + if (!nbase) { + return nullptr; + } + } + + // Now that we've possibly preserved slot, check whether all members match. + // If so, this is a redundant "put" and we can return without more work. + if (shape->matchesParamsAfterId(nbase, slot, attrs, nullptr, nullptr)) { + return shape; + } + + if (!maybeToDictionaryModeForPut(cx, obj, &shape)) { + return nullptr; + } + + MOZ_ASSERT_IF(shape->isDataProperty(), shape->slot() == slot); + + if (obj->inDictionaryMode()) { + // Updating some property in a dictionary-mode object. Create a new + // shape for the existing property, and also generate a new shape for + // the last property of the dictionary (unless the modified property + // is also the last property). + bool updateLast = (shape == obj->lastProperty()); + shape = NativeObject::replaceWithNewEquivalentShape( + cx, obj, shape, nullptr, + /* accessorShape = */ false); + if (!shape) { + return nullptr; + } + if (!updateLast && !NativeObject::generateOwnShape(cx, obj)) { + return nullptr; + } + + if (slot == SHAPE_INVALID_SLOT) { + if (!allocDictionarySlot(cx, obj, &slot)) { + return nullptr; + } + } + + if (updateLast) { + shape->base()->adoptUnowned(nbase); + } else { + shape->setBase(nbase); + } + + shape->setSlot(slot); + shape->attrs = uint8_t(attrs); + shape->immutableFlags &= ~Shape::ACCESSOR_SHAPE; + shape->immutableFlags |= Shape::IN_DICTIONARY; + } else { + // Updating the last property in a non-dictionary-mode object. Find an + // alternate shared child of the last property's previous shape. + + MOZ_ASSERT(shape == obj->lastProperty()); + + // Find or create a property tree node labeled by our arguments. + Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs)); + RootedShape parent(cx, shape->parent); + shape = getChildDataProperty(cx, obj, parent, &child); + if (!shape) { + return nullptr; + } + } + + MOZ_ASSERT(shape->isDataProperty()); + return shape; +} + +/* static */ +Shape* NativeObject::putAccessorProperty(JSContext* cx, HandleNativeObject obj, + HandleId id, GetterOp getter, + SetterOp setter, unsigned attrs) { + MOZ_ASSERT(!JSID_IS_VOID(id)); + + AutoCheckShapeConsistency check(obj); + AssertValidArrayIndex(obj, id); + AssertValidPropertyOp(obj, getter, setter, attrs); + + AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter); + + // Search for id in order to claim its entry if table has been allocated. + AutoKeepShapeCaches keep(cx); + RootedShape shape(cx); + { + ShapeTable* table; + ShapeTable::Entry* entry; + if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep, + shape.address(), &table, &entry)) { + return nullptr; + } + + if (!shape) { + MOZ_ASSERT( + obj->isExtensible() || + (JSID_IS_INT(id) && obj->containsDenseElement(JSID_TO_INT(id))), + "Can't add new property to non-extensible object"); + return addAccessorPropertyInternal(cx, obj, id, getter, setter, attrs, + table, entry, keep); + } + + // Property exists: search must have returned a valid entry. + MOZ_ASSERT_IF(entry, !entry->isRemoved()); + } + + AssertCanChangeAttrs(shape, attrs); + + bool hadSlot = shape->isDataProperty(); + uint32_t oldSlot = shape->maybeSlot(); + + Rooted<UnownedBaseShape*> nbase(cx); + { + RootedShape shape(cx, obj->lastProperty()); + nbase = GetBaseShapeForNewShape(cx, shape, id); + if (!nbase) { + return nullptr; + } + } + + // Check whether all members match. If so, this is a redundant "put" and we + // can return without more work. + if (shape->matchesParamsAfterId(nbase, SHAPE_INVALID_SLOT, attrs, getter, + setter)) { + return shape; + } + + if (!maybeToDictionaryModeForPut(cx, obj, &shape)) { + return nullptr; + } + + if (obj->inDictionaryMode()) { + // Updating some property in a dictionary-mode object. Create a new + // shape for the existing property, and also generate a new shape for + // the last property of the dictionary (unless the modified property + // is also the last property). + bool updateLast = (shape == obj->lastProperty()); + shape = + NativeObject::replaceWithNewEquivalentShape(cx, obj, shape, nullptr, + /* accessorShape = */ true); + if (!shape) { + return nullptr; + } + if (!updateLast && !NativeObject::generateOwnShape(cx, obj)) { + return nullptr; + } + + if (updateLast) { + shape->base()->adoptUnowned(nbase); + } else { + shape->setBase(nbase); + } + + shape->setSlot(SHAPE_INVALID_SLOT); + shape->attrs = uint8_t(attrs); + shape->immutableFlags |= Shape::IN_DICTIONARY | Shape::ACCESSOR_SHAPE; + + AccessorShape& accShape = shape->asAccessorShape(); + accShape.rawGetter = getter; + accShape.rawSetter = setter; + GetterSetterPostWriteBarrier(&accShape); + } else { + // Updating the last property in a non-dictionary-mode object. Find an + // alternate shared child of the last property's previous shape. + + MOZ_ASSERT(shape == obj->lastProperty()); + + // Find or create a property tree node labeled by our arguments. + Rooted<StackShape> child(cx, + StackShape(nbase, id, SHAPE_INVALID_SLOT, attrs)); + child.updateGetterSetter(getter, setter); + RootedShape parent(cx, shape->parent); + shape = getChildAccessorProperty(cx, obj, parent, &child); + if (!shape) { + return nullptr; + } + } + + // Can't fail now, so free the previous incarnation's slot. But we do not + // need to free oldSlot (and must not, as trying to will botch an assertion + // in NativeObject::freeSlot) if the new last property (shape here) has a + // slotSpan that does not cover it. + if (hadSlot && oldSlot < obj->slotSpan()) { + obj->freeSlot(cx, oldSlot); + } + + MOZ_ASSERT(!shape->isDataProperty()); + return shape; +} + +/* static */ +Shape* NativeObject::changeProperty(JSContext* cx, HandleNativeObject obj, + HandleShape shape, unsigned attrs, + GetterOp getter, SetterOp setter) { + MOZ_ASSERT(obj->containsPure(shape)); + + AutoCheckShapeConsistency check(obj); + + /* Allow only shared (slotless) => unshared (slotful) transition. */ +#ifdef DEBUG + bool needSlot = Shape::isDataProperty(attrs, getter, setter); + MOZ_ASSERT_IF(shape->isDataProperty() != needSlot, needSlot); +#endif + + AssertCanChangeAttrs(shape, attrs); + + if (shape->attrs == attrs && shape->getter() == getter && + shape->setter() == setter) { + return shape; + } + + RootedId propid(cx, shape->propid()); + return putAccessorProperty(cx, obj, propid, getter, setter, attrs); +} + +/* static */ +bool NativeObject::removeProperty(JSContext* cx, HandleNativeObject obj, + jsid id_) { + RootedId id(cx, id_); + + AutoKeepShapeCaches keep(cx); + ShapeTable* table; + ShapeTable::Entry* entry; + RootedShape shape(cx); + if (!Shape::search(cx, obj->lastProperty(), id, keep, shape.address(), &table, + &entry)) { + return false; + } + + if (!shape) { + return true; + } + + /* + * If shape is not the last property added, or the last property cannot + * be removed, switch to dictionary mode. + */ + if (!obj->inDictionaryMode() && + (shape != obj->lastProperty() || !obj->canRemoveLastProperty())) { + if (!toDictionaryMode(cx, obj)) { + return false; + } + table = obj->lastProperty()->maybeTable(keep); + MOZ_ASSERT(table); + entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep); + shape = entry->shape(); + } + + /* + * If in dictionary mode, get a new shape for the last property after the + * removal. We need a fresh shape for all dictionary deletions, even of + * the last property. Otherwise, a shape could replay and caches might + * return deleted DictionaryShapes! See bug 595365. Do this before changing + * the object or table, so the remaining removal is infallible. + */ + RootedShape spare(cx); + if (obj->inDictionaryMode()) { + /* For simplicity, always allocate an accessor shape for now. */ + spare = Allocate<AccessorShape>(cx); + if (!spare) { + return false; + } + new (spare) Shape(shape->base()->unowned(), 0); + if (shape == obj->lastProperty()) { + /* + * Get an up to date unowned base shape for the new last property + * when removing the dictionary's last property. Information in + * base shapes for non-last properties may be out of sync with the + * object's state. + */ + RootedShape previous(cx, obj->lastProperty()->parent); + StackBaseShape base(obj->lastProperty()->base()); + BaseShape* nbase = BaseShape::getUnowned(cx, base); + if (!nbase) { + return false; + } + previous->setBase(nbase); + } + } + + /* If shape has a slot, free its slot number. */ + if (shape->isDataProperty()) { + obj->freeSlot(cx, shape->slot()); + } + + /* + * A dictionary-mode object owns mutable, unique shapes on a non-circular + * doubly linked list, hashed by lastProperty()->table. So we can edit the + * list and hash in place. + */ + if (obj->inDictionaryMode()) { + MOZ_ASSERT(obj->lastProperty()->maybeTable(keep) == table); + + if (entry->hadCollision()) { + entry->setRemoved(); + table->decEntryCount(); + table->incRemovedCount(); + } else { + entry->setFree(); + table->decEntryCount(); + +#ifdef DEBUG + /* + * Check the consistency of the table but limit the number of + * checks not to alter significantly the complexity of the + * delete in debug builds, see bug 534493. + */ + Shape* aprop = obj->lastProperty(); + for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent) { + MOZ_ASSERT_IF(aprop != shape, obj->contains(cx, aprop)); + } +#endif + } + + { + /* Remove shape from its non-circular doubly linked list. */ + Shape* oldLastProp = obj->lastProperty(); + shape->removeFromDictionary(obj); + + /* Hand off table from the old to new last property. */ + oldLastProp->handoffTableTo(obj->lastProperty()); + } + + /* Generate a new shape for the object, infallibly. */ + MOZ_ALWAYS_TRUE(NativeObject::generateOwnShape(cx, obj, spare)); + + /* Consider shrinking table if its load factor is <= .25. */ + uint32_t size = table->capacity(); + if (size > ShapeTable::MIN_SIZE && table->entryCount() <= size >> 2) { + (void)table->change(cx, -1); + } + } else { + /* + * Non-dictionary-mode shape tables are shared immutables, so all we + * need do is retract the last property and we'll either get or else + * lazily make via a later hashify the exact table for the new property + * lineage. + */ + MOZ_ASSERT(shape == obj->lastProperty()); + obj->removeLastProperty(cx); + } + + obj->checkShapeConsistency(); + return true; +} + +/* static */ +Shape* NativeObject::replaceWithNewEquivalentShape(JSContext* cx, + HandleNativeObject obj, + Shape* oldShape, + Shape* newShape, + bool accessorShape) { + MOZ_ASSERT(cx->isInsideCurrentZone(oldShape)); + MOZ_ASSERT_IF(oldShape != obj->lastProperty(), + obj->inDictionaryMode() && + obj->lookup(cx, oldShape->propidRef()) == oldShape); + + if (!obj->inDictionaryMode()) { + RootedShape newRoot(cx, newShape); + if (!toDictionaryMode(cx, obj)) { + return nullptr; + } + oldShape = obj->lastProperty(); + newShape = newRoot; + } + + if (!newShape) { + RootedShape oldRoot(cx, oldShape); + newShape = (oldShape->isAccessorShape() || accessorShape) + ? Allocate<AccessorShape>(cx) + : Allocate<Shape>(cx); + if (!newShape) { + return nullptr; + } + new (newShape) Shape(oldRoot->base()->unowned(), 0); + oldShape = oldRoot; + } + + AutoCheckCannotGC nogc; + ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, nogc); + if (!table) { + return nullptr; + } + + ShapeTable::Entry* entry = + oldShape->isEmptyShape() + ? nullptr + : &table->search<MaybeAdding::NotAdding>(oldShape->propidRef(), nogc); + + /* + * Splice the new shape into the same position as the old shape, preserving + * enumeration order (see bug 601399). + */ + StackShape nshape(oldShape); + newShape->initDictionaryShape(nshape, obj->numFixedSlots(), + oldShape->dictNext); + + MOZ_ASSERT(newShape->parent == oldShape); + oldShape->removeFromDictionary(obj); + + if (newShape == obj->lastProperty()) { + oldShape->handoffTableTo(newShape); + } + + if (entry) { + entry->setPreservingCollision(newShape); + } + return newShape; +} + +/* static */ +bool JSObject::setFlags(JSContext* cx, HandleObject obj, BaseShape::Flag flags, + GenerateShape generateShape) { + MOZ_ASSERT(cx->compartment() == obj->compartment()); + + if (obj->hasAllFlags(flags)) { + return true; + } + + Shape* existingShape = obj->shape(); + if (!existingShape) { + return false; + } + + if (obj->isNative() && obj->as<NativeObject>().inDictionaryMode()) { + if (generateShape == GENERATE_SHAPE) { + if (!NativeObject::generateOwnShape(cx, obj.as<NativeObject>())) { + return false; + } + } + StackBaseShape base(obj->as<NativeObject>().lastProperty()); + base.flags |= flags; + UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base); + if (!nbase) { + return false; + } + + obj->as<NativeObject>().lastProperty()->base()->adoptUnowned(nbase); + return true; + } + + Shape* newShape = + Shape::setObjectFlags(cx, flags, obj->taggedProto(), existingShape); + if (!newShape) { + return false; + } + + obj->as<JSObject>().setShape(newShape); + return true; +} + +/* static */ +bool NativeObject::clearFlag(JSContext* cx, HandleNativeObject obj, + BaseShape::Flag flag) { + MOZ_ASSERT(obj->lastProperty()->getObjectFlags() & flag); + + if (!obj->inDictionaryMode()) { + if (!toDictionaryMode(cx, obj)) { + return false; + } + } + + StackBaseShape base(obj->lastProperty()); + base.flags &= ~flag; + UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base); + if (!nbase) { + return false; + } + + obj->lastProperty()->base()->adoptUnowned(nbase); + return true; +} + +/* static */ +Shape* Shape::setObjectFlags(JSContext* cx, BaseShape::Flag flags, + TaggedProto proto, Shape* last) { + if ((last->getObjectFlags() & flags) == flags) { + return last; + } + + StackBaseShape base(last); + base.flags |= flags; + + RootedShape lastRoot(cx, last); + return replaceLastProperty(cx, base, proto, lastRoot); +} + +inline BaseShape::BaseShape(const StackBaseShape& base) + : TenuredCellWithNonGCPointer(base.clasp), + flags(base.flags), + unowned_(nullptr) {} + +/* static */ +void BaseShape::copyFromUnowned(BaseShape& dest, UnownedBaseShape& src) { + dest.setHeaderPtr(src.clasp()); + dest.unowned_ = &src; + dest.flags = src.flags | OWNED_SHAPE; +} + +inline void BaseShape::adoptUnowned(UnownedBaseShape* other) { + // This is a base shape owned by a dictionary object, update it to reflect the + // unowned base shape of a new last property. + MOZ_ASSERT(isOwned()); + + BaseShape::copyFromUnowned(*this, *other); + + assertConsistency(); +} + +/* static */ +UnownedBaseShape* BaseShape::getUnowned(JSContext* cx, StackBaseShape& base) { + auto& table = cx->zone()->baseShapes(); + + auto p = MakeDependentAddPtr(cx, table, base); + if (p) { + return *p; + } + + BaseShape* nbase_ = Allocate<BaseShape>(cx); + if (!nbase_) { + return nullptr; + } + + new (nbase_) BaseShape(base); + + UnownedBaseShape* nbase = static_cast<UnownedBaseShape*>(nbase_); + + if (!p.add(cx, table, base, nbase)) { + return nullptr; + } + + return nbase; +} + +void BaseShape::assertConsistency() { +#ifdef DEBUG + if (isOwned()) { + UnownedBaseShape* unowned = baseUnowned(); + MOZ_ASSERT(getObjectFlags() == unowned->getObjectFlags()); + } +#endif +} + +void BaseShape::traceChildren(JSTracer* trc) { + traceChildrenSkipShapeCache(trc); + traceShapeCache(trc); +} + +void BaseShape::traceChildrenSkipShapeCache(JSTracer* trc) { + if (isOwned()) { + TraceEdge(trc, &unowned_, "base"); + } + + assertConsistency(); +} + +void BaseShape::traceShapeCache(JSTracer* trc) { + AutoCheckCannotGC nogc; + cache_.trace(trc); +} + +#ifdef DEBUG +bool BaseShape::canSkipMarkingShapeCache(Shape* lastShape) { + // Check that every shape in the shape table will be marked by marking + // |lastShape|. + AutoCheckCannotGC nogc; + ShapeCachePtr cache = getCache(nogc); + if (!cache.isTable()) { + return true; + } + + uint32_t count = 0; + for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) { + Shape* shape = &r.front(); + ShapeTable::Entry& entry = + cache.getTablePointer()->search<MaybeAdding::NotAdding>(shape->propid(), + nogc); + if (entry.isLive()) { + count++; + } + } + + return count == cache.getTablePointer()->entryCount(); +} +#endif + +#ifdef JSGC_HASH_TABLE_CHECKS + +void Zone::checkBaseShapeTableAfterMovingGC() { + for (auto r = baseShapes().all(); !r.empty(); r.popFront()) { + UnownedBaseShape* base = r.front().unbarrieredGet(); + CheckGCThingAfterMovingGC(base); + + BaseShapeSet::Ptr ptr = baseShapes().lookup(base); + MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front()); + } +} + +#endif // JSGC_HASH_TABLE_CHECKS + +void BaseShape::finalize(JSFreeOp* fop) { + if (cache_.isInitialized()) { + cache_.destroy(fop, this); + } +} + +inline InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto() {} + +inline InitialShapeEntry::InitialShapeEntry(Shape* shape, + const TaggedProto& proto) + : shape(shape), proto(proto) {} + +#ifdef JSGC_HASH_TABLE_CHECKS + +void Zone::checkInitialShapesTableAfterMovingGC() { + /* + * Assert that the postbarriers have worked and that nothing is left in + * initialShapes that points into the nursery, and that the hash table + * entries are discoverable. + */ + for (auto r = initialShapes().all(); !r.empty(); r.popFront()) { + InitialShapeEntry entry = r.front(); + TaggedProto proto = entry.proto.unbarrieredGet(); + Shape* shape = entry.shape.unbarrieredGet(); + + CheckGCThingAfterMovingGC(shape); + if (proto.isObject()) { + CheckGCThingAfterMovingGC(proto.toObject()); + } + + using Lookup = InitialShapeEntry::Lookup; + Lookup lookup(shape->getObjectClass(), proto, shape->numFixedSlots(), + shape->getObjectFlags()); + InitialShapeSet::Ptr ptr = initialShapes().lookup(lookup); + MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front()); + } +} + +#endif // JSGC_HASH_TABLE_CHECKS + +Shape* EmptyShape::new_(JSContext* cx, Handle<UnownedBaseShape*> base, + uint32_t nfixed) { + Shape* shape = Allocate<Shape>(cx); + if (!shape) { + ReportOutOfMemory(cx); + return nullptr; + } + + new (shape) EmptyShape(base, nfixed); + return shape; +} + +MOZ_ALWAYS_INLINE HashNumber ShapeHasher::hash(const Lookup& l) { + return l.hash(); +} + +MOZ_ALWAYS_INLINE bool ShapeHasher::match(const Key k, const Lookup& l) { + return k->matches(l); +} + +static ShapeSet* MakeShapeSet(Shape* child1, Shape* child2) { + auto hash = MakeUnique<ShapeSet>(); + if (!hash || !hash->reserve(2)) { + return nullptr; + } + + hash->putNewInfallible(StackShape(child1), child1); + hash->putNewInfallible(StackShape(child2), child2); + return hash.release(); +} + +bool PropertyTree::insertChild(JSContext* cx, Shape* parent, Shape* child) { + MOZ_ASSERT(!parent->inDictionary()); + MOZ_ASSERT(!child->parent); + MOZ_ASSERT(!child->inDictionary()); + MOZ_ASSERT(child->zone() == parent->zone()); + MOZ_ASSERT(cx->zone() == zone_); + + ShapeChildren* childp = &parent->children; + + if (childp->isNone()) { + child->setParent(parent); + childp->setSingleShape(child); + return true; + } + + if (childp->isSingleShape()) { + Shape* shape = childp->toSingleShape(); + MOZ_ASSERT(shape != child); + MOZ_ASSERT(!shape->matches(child)); + + ShapeSet* hash = MakeShapeSet(shape, child); + if (!hash) { + ReportOutOfMemory(cx); + return false; + } + childp->setShapeSet(hash); + AddCellMemory(parent, sizeof(ShapeSet), MemoryUse::ShapeChildren); + child->setParent(parent); + return true; + } + + if (!childp->toShapeSet()->putNew(StackShape(child), child)) { + ReportOutOfMemory(cx); + return false; + } + + child->setParent(parent); + return true; +} + +void Shape::removeChild(JSFreeOp* fop, Shape* child) { + MOZ_ASSERT(!child->inDictionary()); + MOZ_ASSERT(child->parent == this); + + ShapeChildren* childp = &children; + + if (childp->isSingleShape()) { + MOZ_ASSERT(childp->toSingleShape() == child); + childp->setNone(); + child->parent = nullptr; + return; + } + + // There must be at least two shapes in a set otherwise + // childp->isSingleShape() should be true. + ShapeSet* set = childp->toShapeSet(); + MOZ_ASSERT(set->count() >= 2); + +#ifdef DEBUG + size_t oldCount = set->count(); +#endif + + set->remove(StackShape(child)); + child->parent = nullptr; + + MOZ_ASSERT(set->count() == oldCount - 1); + + if (set->count() == 1) { + // Convert from set form back to single shape form. + ShapeSet::Range r = set->all(); + Shape* otherChild = r.front(); + MOZ_ASSERT((r.popFront(), r.empty())); // No more elements! + childp->setSingleShape(otherChild); + fop->delete_(this, set, MemoryUse::ShapeChildren); + } +} + +MOZ_ALWAYS_INLINE Shape* PropertyTree::inlinedGetChild( + JSContext* cx, Shape* parent, Handle<StackShape> childSpec) { + MOZ_ASSERT(parent); + + Shape* existingShape = nullptr; + + /* + * The property tree has extremely low fan-out below its root in + * popular embeddings with real-world workloads. Patterns such as + * defining closures that capture a constructor's environment as + * getters or setters on the new object that is passed in as + * |this| can significantly increase fan-out below the property + * tree root -- see bug 335700 for details. + */ + ShapeChildren* childp = &parent->children; + if (childp->isSingleShape()) { + Shape* child = childp->toSingleShape(); + if (child->matches(childSpec)) { + existingShape = child; + } + } else if (childp->isShapeSet()) { + if (ShapeSet::Ptr p = childp->toShapeSet()->lookup(childSpec)) { + existingShape = *p; + } + } else { + /* If childp->isNone(), we always insert. */ + } + + if (existingShape) { + existingShape = PropertyTreeReadBarrier(cx, parent, existingShape); + if (existingShape) { + return existingShape; + } + } + + RootedShape parentRoot(cx, parent); + Shape* shape = Shape::new_(cx, childSpec, parentRoot->numFixedSlots()); + if (!shape) { + return nullptr; + } + + if (!insertChild(cx, parentRoot, shape)) { + return nullptr; + } + + return shape; +} + +Shape* PropertyTree::getChild(JSContext* cx, Shape* parent, + Handle<StackShape> child) { + return inlinedGetChild(cx, parent, child); +} + +void Shape::sweep(JSFreeOp* fop) { + /* + * We detach the child from the parent if the parent is reachable. + * + * This test depends on shape arenas not being freed until after we finish + * incrementally sweeping them. If that were not the case the parent pointer + * could point to a marked cell that had been deallocated and then + * reallocated, since allocating a cell in a zone that is being marked will + * set the mark bit for that cell. + */ + + MOZ_ASSERT(zone()->isGCSweeping()); + MOZ_ASSERT_IF(parent, parent->zone() == zone()); + + if (parent && parent->isMarkedAny()) { + if (inDictionary()) { + if (parent->dictNext == DictionaryShapeLink(this)) { + parent->dictNext.setNone(); + } + } else { + parent->removeChild(fop, this); + } + } +} + +void Shape::finalize(JSFreeOp* fop) { + if (!inDictionary() && children.isShapeSet()) { + fop->delete_(this, children.toShapeSet(), MemoryUse::ShapeChildren); + } +} + +void Shape::fixupDictionaryShapeAfterMovingGC() { + if (dictNext.isShape()) { + Shape* shape = dictNext.toShape(); + if (gc::IsForwarded(shape)) { + dictNext.setShape(gc::Forwarded(shape)); + } + } else if (dictNext.isObject()) { + JSObject* obj = dictNext.toObject(); + if (gc::IsForwarded(obj)) { + dictNext.setObject(gc::Forwarded(obj)); + } + } else { + MOZ_ASSERT(dictNext.isNone()); + } +} + +void Shape::fixupShapeTreeAfterMovingGC() { + if (children.isNone()) { + return; + } + + if (children.isSingleShape()) { + if (gc::IsForwarded(children.toSingleShape())) { + children.setSingleShape(gc::Forwarded(children.toSingleShape())); + } + return; + } + + MOZ_ASSERT(children.isShapeSet()); + ShapeSet* set = children.toShapeSet(); + for (ShapeSet::Enum e(*set); !e.empty(); e.popFront()) { + Shape* key = MaybeForwarded(e.front()); + BaseShape* base = MaybeForwarded(key->base()); + UnownedBaseShape* unowned = MaybeForwarded(base->unowned()); + + GetterOp getter = key->getter(); + if (key->hasGetterObject()) { + getter = GetterOp(MaybeForwarded(key->getterObject())); + } + + SetterOp setter = key->setter(); + if (key->hasSetterObject()) { + setter = SetterOp(MaybeForwarded(key->setterObject())); + } + + StackShape lookup(unowned, const_cast<Shape*>(key)->propidRef(), + key->immutableFlags & Shape::SLOT_MASK, key->attrs); + lookup.updateGetterSetter(getter, setter); + e.rekeyFront(lookup, key); + } +} + +void Shape::fixupAfterMovingGC() { + if (inDictionary()) { + fixupDictionaryShapeAfterMovingGC(); + } else { + fixupShapeTreeAfterMovingGC(); + } +} + +void NurseryShapesRef::trace(JSTracer* trc) { + auto& shapes = zone_->nurseryShapes(); + for (auto shape : shapes) { + shape->fixupGetterSetterForBarrier(trc); + } + shapes.clearAndFree(); +} + +void Shape::fixupGetterSetterForBarrier(JSTracer* trc) { + if (!hasGetterValue() && !hasSetterValue()) { + return; + } + + JSObject* priorGetter = asAccessorShape().getterObj; + JSObject* priorSetter = asAccessorShape().setterObj; + if (!priorGetter && !priorSetter) { + return; + } + + JSObject* postGetter = priorGetter; + JSObject* postSetter = priorSetter; + if (priorGetter) { + TraceManuallyBarrieredEdge(trc, &postGetter, "getterObj"); + } + if (priorSetter) { + TraceManuallyBarrieredEdge(trc, &postSetter, "setterObj"); + } + if (priorGetter == postGetter && priorSetter == postSetter) { + return; + } + + if (parent && !parent->inDictionary() && parent->children.isShapeSet()) { + // Relocating the getterObj or setterObj will have changed our location in + // our parent's ShapeSet, so take care to update it. We must do this before + // we update the shape itself, since the shape is used to match the original + // entry in the hash set. + + StackShape original(this); + StackShape updated(this); + updated.rawGetter = reinterpret_cast<GetterOp>(postGetter); + updated.rawSetter = reinterpret_cast<SetterOp>(postSetter); + + ShapeSet* set = parent->children.toShapeSet(); + MOZ_ALWAYS_TRUE(set->rekeyAs(original, updated, this)); + } + + asAccessorShape().getterObj = postGetter; + asAccessorShape().setterObj = postSetter; + + MOZ_ASSERT_IF( + parent && !parent->inDictionary() && parent->children.isShapeSet(), + parent->children.toShapeSet()->has(StackShape(this))); +} + +#ifdef DEBUG + +void ShapeChildren::checkHasChild(Shape* child) const { + if (isSingleShape()) { + MOZ_ASSERT(toSingleShape() == child); + } else { + MOZ_ASSERT(isShapeSet()); + ShapeSet* set = toShapeSet(); + ShapeSet::Ptr ptr = set->lookup(StackShape(child)); + MOZ_ASSERT(*ptr == child); + } +} + +void Shape::dump(js::GenericPrinter& out) const { + jsid propid = this->propid(); + + MOZ_ASSERT(!JSID_IS_VOID(propid)); + + if (JSID_IS_INT(propid)) { + out.printf("[%ld]", (long)JSID_TO_INT(propid)); + } else if (JSID_IS_ATOM(propid)) { + if (JSLinearString* str = JSID_TO_ATOM(propid)) { + EscapedStringPrinter(out, str, '"'); + } else { + out.put("<error>"); + } + } else { + MOZ_ASSERT(JSID_IS_SYMBOL(propid)); + JSID_TO_SYMBOL(propid)->dump(out); + } + + out.printf(" g/s %p/%p slot %d attrs %x ", + JS_FUNC_TO_DATA_PTR(void*, getter()), + JS_FUNC_TO_DATA_PTR(void*, setter()), + isDataProperty() ? int32_t(slot()) : -1, attrs); + + if (attrs) { + int first = 1; + out.putChar('('); +# define DUMP_ATTR(name, display) \ + if (attrs & JSPROP_##name) out.put(&(" " #display)[first]), first = 0 + DUMP_ATTR(ENUMERATE, enumerate); + DUMP_ATTR(READONLY, readonly); + DUMP_ATTR(PERMANENT, permanent); + DUMP_ATTR(GETTER, getter); + DUMP_ATTR(SETTER, setter); +# undef DUMP_ATTR + out.putChar(')'); + } + + out.printf("immutableFlags %x ", immutableFlags); + if (immutableFlags) { + int first = 1; + out.putChar('('); +# define DUMP_FLAG(name, display) \ + if (immutableFlags & name) out.put(&(" " #display)[first]), first = 0 + DUMP_FLAG(IN_DICTIONARY, in_dictionary); +# undef DUMP_FLAG + out.putChar(')'); + } +} + +void Shape::dump() const { + Fprinter out(stderr); + dump(out); +} + +void Shape::dumpSubtree(int level, js::GenericPrinter& out) const { + if (!parent) { + MOZ_ASSERT(level == 0); + MOZ_ASSERT(JSID_IS_EMPTY(propid_)); + out.printf("class %s emptyShape\n", getObjectClass()->name); + } else { + out.printf("%*sid ", level, ""); + dump(out); + } + + if (!children.isNone()) { + ++level; + if (children.isSingleShape()) { + Shape* child = children.toSingleShape(); + MOZ_ASSERT(child->parent == this); + child->dumpSubtree(level, out); + } else { + const ShapeSet& set = *children.toShapeSet(); + for (ShapeSet::Range range = set.all(); !range.empty(); + range.popFront()) { + Shape* child = range.front(); + + MOZ_ASSERT(child->parent == this); + child->dumpSubtree(level, out); + } + } + } +} + +#endif + +/* static */ +Shape* EmptyShape::getInitialShape(JSContext* cx, const JSClass* clasp, + TaggedProto proto, size_t nfixed, + uint32_t objectFlags) { + MOZ_ASSERT_IF(proto.isObject(), + cx->isInsideCurrentCompartment(proto.toObject())); + + auto& table = cx->zone()->initialShapes(); + + using Lookup = InitialShapeEntry::Lookup; + auto protoPointer = + MakeDependentAddPtr(cx, table, Lookup(clasp, proto, nfixed, objectFlags)); + if (protoPointer) { + return protoPointer->shape; + } + + Rooted<TaggedProto> protoRoot(cx, proto); + StackBaseShape base(clasp, objectFlags); + Rooted<UnownedBaseShape*> nbase(cx, BaseShape::getUnowned(cx, base)); + if (!nbase) { + return nullptr; + } + + RootedShape shape(cx, EmptyShape::new_(cx, nbase, nfixed)); + if (!shape) { + return nullptr; + } + + Lookup lookup(clasp, protoRoot, nfixed, objectFlags); + if (!protoPointer.add(cx, table, lookup, + InitialShapeEntry(shape, protoRoot))) { + return nullptr; + } + + return shape; +} + +/* static */ +Shape* EmptyShape::getInitialShape(JSContext* cx, const JSClass* clasp, + TaggedProto proto, gc::AllocKind kind, + uint32_t objectFlags) { + return getInitialShape(cx, clasp, proto, GetGCKindSlots(kind, clasp), + objectFlags); +} + +void NewObjectCache::invalidateEntriesForShape(JSContext* cx, HandleShape shape, + HandleObject proto) { + const JSClass* clasp = shape->getObjectClass(); + + gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots()); + if (CanChangeToBackgroundAllocKind(kind, clasp)) { + kind = ForegroundToBackgroundAllocKind(kind); + } + + RootedObjectGroup group( + cx, ObjectGroup::defaultNewGroup(cx, clasp, TaggedProto(proto))); + if (!group) { + purge(); + cx->recoverFromOutOfMemory(); + return; + } + + EntryIndex entry; + for (RealmsInZoneIter realm(shape->zone()); !realm.done(); realm.next()) { + if (GlobalObject* global = realm->unsafeUnbarrieredMaybeGlobal()) { + if (lookupGlobal(clasp, global, kind, &entry)) { + PodZero(&entries[entry]); + } + } + } + if (!proto->is<GlobalObject>() && lookupProto(clasp, proto, kind, &entry)) { + PodZero(&entries[entry]); + } + if (lookupGroup(group, kind, &entry)) { + PodZero(&entries[entry]); + } +} + +/* static */ +void EmptyShape::insertInitialShape(JSContext* cx, HandleShape shape, + HandleObject proto) { + using Lookup = InitialShapeEntry::Lookup; + Lookup lookup(shape->getObjectClass(), TaggedProto(proto), + shape->numFixedSlots(), shape->getObjectFlags()); + + InitialShapeSet::Ptr p = cx->zone()->initialShapes().lookup(lookup); + MOZ_ASSERT(p); + + InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p); + + // The metadata callback can end up causing redundant changes of the initial + // shape. + if (entry.shape == shape) { + return; + } + + // The new shape had better be rooted at the old one. +#ifdef DEBUG + Shape* nshape = shape; + while (!nshape->isEmptyShape()) { + nshape = nshape->previous(); + } + MOZ_ASSERT(nshape == entry.shape); +#endif + + entry.shape = WeakHeapPtrShape(shape); + + /* + * This affects the shape that will be produced by the various NewObject + * methods, so clear any cache entry referring to the old shape. This is + * not required for correctness: the NewObject must always check for a + * nativeEmpty() result and generate the appropriate properties if found. + * Clearing the cache entry avoids this duplicate regeneration. + * + * Clearing is not necessary when this context is running off + * thread, as it will not use the new object cache for allocations. + */ + if (!cx->isHelperThreadContext()) { + cx->caches().newObjectCache.invalidateEntriesForShape(cx, shape, proto); + } +} + +void Zone::fixupInitialShapeTable() { + for (InitialShapeSet::Enum e(initialShapes()); !e.empty(); e.popFront()) { + // The shape may have been moved, but we can update that in place. + Shape* shape = e.front().shape.unbarrieredGet(); + if (IsForwarded(shape)) { + shape = Forwarded(shape); + e.mutableFront().shape.set(shape); + } + shape->updateBaseShapeAfterMovingGC(); + + // If the prototype has moved we have to rekey the entry. + InitialShapeEntry entry = e.front(); + // Use unbarrieredGet() to prevent triggering read barrier while collecting. + const TaggedProto& proto = entry.proto.unbarrieredGet(); + if (proto.isObject() && IsForwarded(proto.toObject())) { + entry.proto = TaggedProto(Forwarded(proto.toObject())); + using Lookup = InitialShapeEntry::Lookup; + Lookup relookup(shape->getObjectClass(), proto, shape->numFixedSlots(), + shape->getObjectFlags()); + e.rekeyFront(relookup, entry); + } + } +} + +void AutoRooterGetterSetter::Inner::trace(JSTracer* trc) { + if ((attrs & JSPROP_GETTER) && *pgetter) { + TraceRoot(trc, (JSObject**)pgetter, "AutoRooterGetterSetter getter"); + } + if ((attrs & JSPROP_SETTER) && *psetter) { + TraceRoot(trc, (JSObject**)psetter, "AutoRooterGetterSetter setter"); + } +} + +JS::ubi::Node::Size JS::ubi::Concrete<js::Shape>::size( + mozilla::MallocSizeOf mallocSizeOf) const { + Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind()); + + AutoCheckCannotGC nogc; + if (ShapeTable* table = get().maybeTable(nogc)) { + size += table->sizeOfIncludingThis(mallocSizeOf); + } + + if (!get().inDictionary() && get().children.isShapeSet()) { + size += + get().children.toShapeSet()->shallowSizeOfIncludingThis(mallocSizeOf); + } + + return size; +} + +JS::ubi::Node::Size JS::ubi::Concrete<js::BaseShape>::size( + mozilla::MallocSizeOf mallocSizeOf) const { + return js::gc::Arena::thingSize(get().asTenured().getAllocKind()); +} + +void PropertyResult::trace(JSTracer* trc) { + if (isNativeProperty()) { + TraceRoot(trc, &shape_, "PropertyResult::shape_"); + } +} |