diff -r 000000000000 -r 6474c204b198 js/src/vm/Shape.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/vm/Shape.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,1852 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * 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/DebugOnly.h" +#include "mozilla/MathAlgorithms.h" +#include "mozilla/PodOperations.h" + +#include "jsatom.h" +#include "jscntxt.h" +#include "jshashutil.h" +#include "jsobj.h" + +#include "js/HashTable.h" + +#include "jscntxtinlines.h" +#include "jsobjinlines.h" + +#include "vm/ObjectImpl-inl.h" +#include "vm/Runtime-inl.h" + +using namespace js; +using namespace js::gc; + +using mozilla::CeilingLog2Size; +using mozilla::DebugOnly; +using mozilla::PodZero; +using mozilla::RotateLeft; + +bool +ShapeTable::init(ThreadSafeContext *cx, Shape *lastProp) +{ + /* + * Either we're creating a table for a large scope that was populated + * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or + * JSOP_SETPROP; or else calloc failed at least once already. In any + * event, let's try to grow, overallocating to hold at least twice the + * current population. + */ + uint32_t sizeLog2 = CeilingLog2Size(2 * entryCount); + if (sizeLog2 < MIN_SIZE_LOG2) + sizeLog2 = MIN_SIZE_LOG2; + + /* + * Use rt->calloc_ for memory accounting and overpressure handling + * without OOM reporting. See ShapeTable::change. + */ + entries = (Shape **) cx->calloc_(sizeOfEntries(JS_BIT(sizeLog2))); + if (!entries) + return false; + + hashShift = HASH_BITS - sizeLog2; + for (Shape::Range r(lastProp); !r.empty(); r.popFront()) { + Shape &shape = r.front(); + JS_ASSERT(cx->isThreadLocal(&shape)); + Shape **spp = search(shape.propid(), true); + + /* + * Beware duplicate args and arg vs. var conflicts: the youngest shape + * (nearest to lastProp) must win. See bug 600067. + */ + if (!SHAPE_FETCH(spp)) + SHAPE_STORE_PRESERVING_COLLISION(spp, &shape); + } + return true; +} + +void +Shape::removeFromDictionary(ObjectImpl *obj) +{ + JS_ASSERT(inDictionary()); + JS_ASSERT(obj->inDictionaryMode()); + JS_ASSERT(listp); + + JS_ASSERT(obj->shape_->inDictionary()); + JS_ASSERT(obj->shape_->listp == &obj->shape_); + + if (parent) + parent->listp = listp; + *listp = parent; + listp = nullptr; +} + +void +Shape::insertIntoDictionary(HeapPtrShape *dictp) +{ + // Don't assert inDictionaryMode() here because we may be called from + // JSObject::toDictionaryMode via JSObject::newDictionaryShape. + JS_ASSERT(inDictionary()); + JS_ASSERT(!listp); + + JS_ASSERT_IF(*dictp, (*dictp)->inDictionary()); + JS_ASSERT_IF(*dictp, (*dictp)->listp == dictp); + JS_ASSERT_IF(*dictp, compartment() == (*dictp)->compartment()); + + setParent(dictp->get()); + if (parent) + parent->listp = &parent; + listp = (HeapPtrShape *) dictp; + *dictp = this; +} + +bool +Shape::makeOwnBaseShape(ThreadSafeContext *cx) +{ + JS_ASSERT(!base()->isOwned()); + JS_ASSERT(cx->isThreadLocal(this)); + assertSameCompartmentDebugOnly(cx, compartment()); + + BaseShape *nbase = js_NewGCBaseShape(cx); + if (!nbase) + return false; + + new (nbase) BaseShape(StackBaseShape(this)); + nbase->setOwned(base()->toUnowned()); + + this->base_ = nbase; + + return true; +} + +void +Shape::handoffTableTo(Shape *shape) +{ + JS_ASSERT(inDictionary() && shape->inDictionary()); + + if (this == shape) + return; + + JS_ASSERT(base()->isOwned() && !shape->base()->isOwned()); + + BaseShape *nbase = base(); + + JS_ASSERT_IF(shape->hasSlot(), nbase->slotSpan() > shape->slot()); + + this->base_ = nbase->baseUnowned(); + nbase->adoptUnowned(shape->base()->toUnowned()); + + shape->base_ = nbase; +} + +/* static */ bool +Shape::hashify(ThreadSafeContext *cx, Shape *shape) +{ + JS_ASSERT(!shape->hasTable()); + + if (!shape->ensureOwnBaseShape(cx)) + return false; + + ShapeTable *table = cx->new_(shape->entryCount()); + if (!table) + return false; + + if (!table->init(cx, shape)) { + js_free(table); + return false; + } + + shape->base()->setTable(table); + return true; +} + +/* + * Double hashing needs the second hash code to be relatively prime to table + * size, so we simply make hash2 odd. + */ +#define HASH1(hash0,shift) ((hash0) >> (shift)) +#define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1) + +Shape ** +ShapeTable::search(jsid id, bool adding) +{ + js::HashNumber hash0, hash1, hash2; + int sizeLog2; + Shape *stored, *shape, **spp, **firstRemoved; + uint32_t sizeMask; + + JS_ASSERT(entries); + JS_ASSERT(!JSID_IS_EMPTY(id)); + + /* Compute the primary hash address. */ + hash0 = HashId(id); + hash1 = HASH1(hash0, hashShift); + spp = entries + hash1; + + /* Miss: return space for a new entry. */ + stored = *spp; + if (SHAPE_IS_FREE(stored)) + return spp; + + /* Hit: return entry. */ + shape = SHAPE_CLEAR_COLLISION(stored); + if (shape && shape->propidRaw() == id) + return spp; + + /* Collision: double hash. */ + sizeLog2 = HASH_BITS - hashShift; + hash2 = HASH2(hash0, sizeLog2, hashShift); + sizeMask = JS_BITMASK(sizeLog2); + +#ifdef DEBUG + uintptr_t collision_flag = SHAPE_COLLISION; +#endif + + /* Save the first removed entry pointer so we can recycle it if adding. */ + if (SHAPE_IS_REMOVED(stored)) { + firstRemoved = spp; + } else { + firstRemoved = nullptr; + if (adding && !SHAPE_HAD_COLLISION(stored)) + SHAPE_FLAG_COLLISION(spp, shape); +#ifdef DEBUG + collision_flag &= uintptr_t(*spp) & SHAPE_COLLISION; +#endif + } + + for (;;) { + hash1 -= hash2; + hash1 &= sizeMask; + spp = entries + hash1; + + stored = *spp; + if (SHAPE_IS_FREE(stored)) + return (adding && firstRemoved) ? firstRemoved : spp; + + shape = SHAPE_CLEAR_COLLISION(stored); + if (shape && shape->propidRaw() == id) { + JS_ASSERT(collision_flag); + return spp; + } + + if (SHAPE_IS_REMOVED(stored)) { + if (!firstRemoved) + firstRemoved = spp; + } else { + if (adding && !SHAPE_HAD_COLLISION(stored)) + SHAPE_FLAG_COLLISION(spp, shape); +#ifdef DEBUG + collision_flag &= uintptr_t(*spp) & SHAPE_COLLISION; +#endif + } + } + + /* NOTREACHED */ + return nullptr; +} + +bool +ShapeTable::change(int log2Delta, ThreadSafeContext *cx) +{ + JS_ASSERT(entries); + + /* + * Grow, shrink, or compress by changing this->entries. + */ + int oldlog2 = HASH_BITS - hashShift; + int newlog2 = oldlog2 + log2Delta; + uint32_t oldsize = JS_BIT(oldlog2); + uint32_t newsize = JS_BIT(newlog2); + Shape **newTable = (Shape **) cx->calloc_(sizeOfEntries(newsize)); + if (!newTable) + return false; + + /* Now that we have newTable allocated, update members. */ + hashShift = HASH_BITS - newlog2; + removedCount = 0; + Shape **oldTable = entries; + entries = newTable; + + /* Copy only live entries, leaving removed and free ones behind. */ + for (Shape **oldspp = oldTable; oldsize != 0; oldspp++) { + Shape *shape = SHAPE_FETCH(oldspp); + JS_ASSERT(cx->isThreadLocal(shape)); + if (shape) { + Shape **spp = search(shape->propid(), true); + JS_ASSERT(SHAPE_IS_FREE(*spp)); + *spp = shape; + } + oldsize--; + } + + /* Finally, free the old entries storage. */ + js_free(oldTable); + return true; +} + +bool +ShapeTable::grow(ThreadSafeContext *cx) +{ + JS_ASSERT(needsToGrow()); + + uint32_t size = capacity(); + int delta = removedCount < size >> 2; + + if (!change(delta, cx) && entryCount + removedCount == size - 1) { + js_ReportOutOfMemory(cx); + return false; + } + return true; +} + +/* static */ Shape * +Shape::replaceLastProperty(ExclusiveContext *cx, StackBaseShape &base, + TaggedProto proto, HandleShape shape) +{ + JS_ASSERT(!shape->inDictionary()); + + if (!shape->parent) { + /* Treat as resetting the initial property of the shape hierarchy. */ + AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots()); + return EmptyShape::getInitialShape(cx, base.clasp, proto, + base.parent, base.metadata, kind, + base.flags & BaseShape::OBJECT_FLAG_MASK); + } + + UnownedBaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return nullptr; + + StackShape child(shape); + child.base = nbase; + + return cx->compartment()->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 */ Shape * +JSObject::getChildPropertyOnDictionary(ThreadSafeContext *cx, JS::HandleObject obj, + HandleShape parent, js::StackShape &child) +{ + /* + * Shared properties have no slot, but slot_ will reflect that of parent. + * Unshared properties allocate a slot here but may lose it due to a + * JS_ClearScope call. + */ + if (!child.hasSlot()) { + child.setSlot(parent->maybeSlot()); + } else { + if (child.hasMissingSlot()) { + uint32_t slot; + if (!allocSlot(cx, obj, &slot)) + return nullptr; + 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. + */ + JS_ASSERT(obj->inDictionaryMode() || + parent->hasMissingSlot() || + child.slot() == parent->maybeSlot() + 1 || + (parent->maybeSlot() + 1 < JSSLOT_FREE(obj->getClass()) && + child.slot() == JSSLOT_FREE(obj->getClass()))); + } + } + + RootedShape shape(cx); + + if (obj->inDictionaryMode()) { + JS_ASSERT(parent == obj->lastProperty()); + RootedGeneric childRoot(cx, &child); + shape = js_NewGCShape(cx); + if (!shape) + return nullptr; + if (childRoot->hasSlot() && childRoot->slot() >= obj->lastProperty()->base()->slotSpan()) { + if (!JSObject::setSlotSpan(cx, obj, childRoot->slot() + 1)) + return nullptr; + } + shape->initDictionaryShape(*childRoot, obj->numFixedSlots(), &obj->shape_); + } + + return shape; +} + +/* static */ Shape * +JSObject::getChildProperty(ExclusiveContext *cx, + HandleObject obj, HandleShape parent, StackShape &unrootedChild) +{ + RootedGeneric child(cx, &unrootedChild); + RootedShape shape(cx, getChildPropertyOnDictionary(cx, obj, parent, *child)); + + if (!obj->inDictionaryMode()) { + shape = cx->compartment()->propertyTree.getChild(cx, parent, *child); + if (!shape) + return nullptr; + //JS_ASSERT(shape->parent == parent); + //JS_ASSERT_IF(parent != lastProperty(), parent == lastProperty()->parent); + if (!JSObject::setLastProperty(cx, obj, shape)) + return nullptr; + } + + return shape; +} + +/* static */ Shape * +JSObject::lookupChildProperty(ThreadSafeContext *cx, + HandleObject obj, HandleShape parent, StackShape &unrootedChild) +{ + RootedGeneric child(cx, &unrootedChild); + JS_ASSERT(cx->isThreadLocal(obj)); + + RootedShape shape(cx, getChildPropertyOnDictionary(cx, obj, parent, *child)); + + if (!obj->inDictionaryMode()) { + shape = cx->compartment_->propertyTree.lookupChild(cx, parent, *child); + if (!shape) + return nullptr; + if (!JSObject::setLastProperty(cx, obj, shape)) + return nullptr; + } + + return shape; +} + +bool +js::ObjectImpl::toDictionaryMode(ThreadSafeContext *cx) +{ + JS_ASSERT(!inDictionaryMode()); + + /* We allocate the shapes from cx->compartment(), so make sure it's right. */ + JS_ASSERT(cx->isInsideCurrentCompartment(this)); + + /* + * This function is thread safe as long as the object is thread local. It + * does not modify the shared shapes, and only allocates newly allocated + * (and thus also thread local) shapes. + */ + JS_ASSERT(cx->isThreadLocal(this)); + + uint32_t span = slotSpan(); + + Rooted self(cx, this); + + /* + * 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, lastProperty()); + while (shape) { + JS_ASSERT(!shape->inDictionary()); + + Shape *dprop = js_NewGCShape(cx); + if (!dprop) { + js_ReportOutOfMemory(cx); + return false; + } + + HeapPtrShape *listp = dictionaryShape + ? &dictionaryShape->parent + : (HeapPtrShape *) root.address(); + + StackShape child(shape); + dprop->initDictionaryShape(child, self->numFixedSlots(), listp); + + JS_ASSERT(!dprop->hasTable()); + dictionaryShape = dprop; + shape = shape->previous(); + } + + if (!Shape::hashify(cx, root)) { + js_ReportOutOfMemory(cx); + return false; + } + + JS_ASSERT((Shape **) root->listp == root.address()); + root->listp = &self->shape_; + self->shape_ = root; + + JS_ASSERT(self->inDictionaryMode()); + root->base()->setSlotSpan(span); + + return true; +} + +/* + * Normalize stub getter and setter values for faster is-stub testing in the + * SHAPE_CALL_[GS]ETTER macros. + */ +static inline bool +NormalizeGetterAndSetter(JSObject *obj, + jsid id, unsigned attrs, unsigned flags, + PropertyOp &getter, + StrictPropertyOp &setter) +{ + if (setter == JS_StrictPropertyStub) { + JS_ASSERT(!(attrs & JSPROP_SETTER)); + setter = nullptr; + } + if (getter == JS_PropertyStub) { + JS_ASSERT(!(attrs & JSPROP_GETTER)); + getter = nullptr; + } + + return true; +} + +/* static */ Shape * +JSObject::addProperty(ExclusiveContext *cx, HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags, bool allowDictionary) +{ + JS_ASSERT(!JSID_IS_VOID(id)); + + bool extensible; + if (!JSObject::isExtensible(cx, obj, &extensible)) + return nullptr; + if (!extensible) { + if (cx->isJSContext()) + obj->reportNotExtensible(cx->asJSContext()); + return nullptr; + } + + NormalizeGetterAndSetter(obj, id, attrs, flags, getter, setter); + + Shape **spp = nullptr; + if (obj->inDictionaryMode()) + spp = obj->lastProperty()->table().search(id, true); + + return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, + flags, spp, allowDictionary); +} + +static bool +ShouldConvertToDictionary(JSObject *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; +} + +template +static inline UnownedBaseShape * +GetOrLookupUnownedBaseShape(typename ExecutionModeTraits::ExclusiveContextType cx, + StackBaseShape &base) +{ + if (mode == ParallelExecution) + return BaseShape::lookupUnowned(cx, base); + return BaseShape::getUnowned(cx->asExclusiveContext(), base); +} + +template +/* static */ Shape * +JSObject::addPropertyInternal(typename ExecutionModeTraits::ExclusiveContextType cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags, Shape **spp, + bool allowDictionary) +{ + JS_ASSERT(cx->isThreadLocal(obj)); + JS_ASSERT_IF(!allowDictionary, !obj->inDictionaryMode()); + + AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter); + + /* + * The code below deals with either converting obj to dictionary mode or + * growing an object that's already in dictionary mode. Either way, + * dictionray operations are safe if thread local. + */ + ShapeTable *table = nullptr; + if (!obj->inDictionaryMode()) { + bool stableSlot = + (slot == SHAPE_INVALID_SLOT) || + obj->lastProperty()->hasMissingSlot() || + (slot == obj->lastProperty()->maybeSlot() + 1); + JS_ASSERT_IF(!allowDictionary, stableSlot); + if (allowDictionary && + (!stableSlot || ShouldConvertToDictionary(obj))) + { + if (!obj->toDictionaryMode(cx)) + return nullptr; + table = &obj->lastProperty()->table(); + spp = table->search(id, true); + } + } else { + table = &obj->lastProperty()->table(); + if (table->needsToGrow()) { + if (!table->grow(cx)) + return nullptr; + spp = table->search(id, true); + JS_ASSERT(!SHAPE_FETCH(spp)); + } + } + + JS_ASSERT(!!table == !!spp); + + /* Find or create a property tree node labeled by our arguments. */ + RootedShape shape(cx); + { + RootedShape last(cx, obj->lastProperty()); + + uint32_t index; + bool indexed = js_IdIsIndex(id, &index); + + Rooted nbase(cx); + if (last->base()->matchesGetterSetter(getter, setter) && !indexed) { + nbase = last->base()->unowned(); + } else { + StackBaseShape base(last->base()); + base.updateGetterSetter(attrs, getter, setter); + if (indexed) + base.flags |= BaseShape::INDEXED; + nbase = GetOrLookupUnownedBaseShape(cx, base); + if (!nbase) + return nullptr; + } + + StackShape child(nbase, id, slot, attrs, flags); + shape = getOrLookupChildProperty(cx, obj, last, child); + } + + if (shape) { + JS_ASSERT(shape == obj->lastProperty()); + + if (table) { + /* Store the tree node pointer in the table entry for id. */ + SHAPE_STORE_PRESERVING_COLLISION(spp, static_cast(shape)); + ++table->entryCount; + + /* Pass the table along to the new last property, namely shape. */ + JS_ASSERT(&shape->parent->table() == table); + shape->parent->handoffTableTo(shape); + } + + obj->checkShapeConsistency(); + return shape; + } + + obj->checkShapeConsistency(); + return nullptr; +} + +template /* static */ Shape * +JSObject::addPropertyInternal(ExclusiveContext *cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags, Shape **spp, + bool allowDictionary); +template /* static */ Shape * +JSObject::addPropertyInternal(ForkJoinContext *cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags, Shape **spp, + bool allowDictionary); + +JSObject * +js::NewReshapedObject(JSContext *cx, HandleTypeObject type, JSObject *parent, + gc::AllocKind allocKind, HandleShape shape, NewObjectKind newKind) +{ + RootedObject res(cx, NewObjectWithType(cx, type, parent, allocKind, newKind)); + if (!res) + return nullptr; + + if (shape->isEmptyShape()) + return res; + + /* Get all the ids in the object, in order. */ + js::AutoIdVector ids(cx); + { + for (unsigned i = 0; i <= shape->slot(); i++) { + if (!ids.append(JSID_VOID)) + return nullptr; + } + Shape *nshape = shape; + while (!nshape->isEmptyShape()) { + ids[nshape->slot()] = nshape->propid(); + nshape = nshape->previous(); + } + } + + /* Construct the new shape, without updating type information. */ + RootedId id(cx); + RootedShape newShape(cx, res->lastProperty()); + for (unsigned i = 0; i < ids.length(); i++) { + id = ids[i]; + JS_ASSERT(!res->nativeContains(cx, id)); + + uint32_t index; + bool indexed = js_IdIsIndex(id, &index); + + Rooted nbase(cx, newShape->base()->unowned()); + if (indexed) { + StackBaseShape base(nbase); + base.flags |= BaseShape::INDEXED; + nbase = GetOrLookupUnownedBaseShape(cx, base); + if (!nbase) + return nullptr; + } + + StackShape child(nbase, id, i, JSPROP_ENUMERATE, 0); + newShape = cx->compartment()->propertyTree.getChild(cx, newShape, child); + if (!newShape) + return nullptr; + if (!JSObject::setLastProperty(cx, res, newShape)) + return nullptr; + } + + return res; +} + +/* + * Check and adjust the new attributes for the shape to make sure that our + * slot access optimizations are sound. It is responsibility of the callers to + * enforce all restrictions from ECMA-262 v5 8.12.9 [[DefineOwnProperty]]. + */ +static inline bool +CheckCanChangeAttrs(ThreadSafeContext *cx, JSObject *obj, Shape *shape, unsigned *attrsp) +{ + if (shape->configurable()) + return true; + + /* A permanent property must stay permanent. */ + *attrsp |= JSPROP_PERMANENT; + + /* Reject attempts to remove a slot from the permanent data property. */ + if (shape->isDataDescriptor() && shape->hasSlot() && + (*attrsp & (JSPROP_GETTER | JSPROP_SETTER | JSPROP_SHARED))) + { + if (cx->isJSContext()) + obj->reportNotConfigurable(cx->asJSContext(), shape->propid()); + return false; + } + + return true; +} + +template +/* static */ Shape * +JSObject::putProperty(typename ExecutionModeTraits::ExclusiveContextType cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, unsigned flags) +{ + JS_ASSERT(cx->isThreadLocal(obj)); + JS_ASSERT(!JSID_IS_VOID(id)); + +#ifdef DEBUG + if (obj->is()) { + ArrayObject *arr = &obj->as(); + uint32_t index; + if (js_IdIsIndex(id, &index)) + JS_ASSERT(index < arr->length() || arr->lengthIsWritable()); + } +#endif + + NormalizeGetterAndSetter(obj, id, attrs, flags, getter, setter); + + AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter); + + /* + * Search for id in order to claim its entry if table has been allocated. + * + * Note that we can only try to claim an entry in a table that is thread + * local. An object may be thread local *without* its shape being thread + * local. The only thread local objects that *also* have thread local + * shapes are dictionaries that were allocated/converted thread + * locally. Only for those objects we can try to claim an entry in its + * shape table. + */ + Shape **spp; + RootedShape shape(cx, (mode == ParallelExecution + ? Shape::searchThreadLocal(cx, obj->lastProperty(), id, &spp, + cx->isThreadLocal(obj->lastProperty())) + : Shape::search(cx->asExclusiveContext(), obj->lastProperty(), id, + &spp, true))); + if (!shape) { + /* + * You can't add properties to a non-extensible object, but you can change + * attributes of properties in such objects. + */ + bool extensible; + + if (mode == ParallelExecution) { + if (obj->is()) + return nullptr; + extensible = obj->nonProxyIsExtensible(); + } else { + if (!JSObject::isExtensible(cx->asExclusiveContext(), obj, &extensible)) + return nullptr; + } + + if (!extensible) { + if (cx->isJSContext()) + obj->reportNotExtensible(cx->asJSContext()); + return nullptr; + } + + return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags, + spp, true); + } + + /* Property exists: search must have returned a valid *spp. */ + JS_ASSERT_IF(spp, !SHAPE_IS_REMOVED(*spp)); + + if (!CheckCanChangeAttrs(cx, obj, shape, &attrs)) + return nullptr; + + /* + * 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->hasSlot(); + uint32_t oldSlot = shape->maybeSlot(); + if (!(attrs & JSPROP_SHARED) && slot == SHAPE_INVALID_SLOT && hadSlot) + slot = oldSlot; + + Rooted nbase(cx); + { + uint32_t index; + bool indexed = js_IdIsIndex(id, &index); + StackBaseShape base(obj->lastProperty()->base()); + base.updateGetterSetter(attrs, getter, setter); + if (indexed) + base.flags |= BaseShape::INDEXED; + nbase = GetOrLookupUnownedBaseShape(cx, base); + 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, flags)) + return shape; + + /* + * Overwriting a non-last property requires switching to dictionary mode. + * The shape tree is shared immutable, and we can't removeProperty and then + * addPropertyInternal because a failure under add would lose data. + */ + if (shape != obj->lastProperty() && !obj->inDictionaryMode()) { + if (!obj->toDictionaryMode(cx)) + return nullptr; + spp = obj->lastProperty()->table().search(shape->propid(), false); + shape = SHAPE_FETCH(spp); + } + + JS_ASSERT_IF(shape->hasSlot() && !(attrs & JSPROP_SHARED), 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 = obj->replaceWithNewEquivalentShape(cx, shape); + if (!shape) + return nullptr; + if (!updateLast && !obj->generateOwnShape(cx)) + return nullptr; + + /* FIXME bug 593129 -- slot allocation and JSObject *this must move out of here! */ + if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED)) { + if (!allocSlot(cx, obj, &slot)) + return nullptr; + } + + if (updateLast) + shape->base()->adoptUnowned(nbase); + else + shape->base_ = nbase; + + JS_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED); + + shape->setSlot(slot); + shape->attrs = uint8_t(attrs); + shape->flags = flags | 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. + */ + StackBaseShape base(obj->lastProperty()->base()); + base.updateGetterSetter(attrs, getter, setter); + + UnownedBaseShape *nbase = GetOrLookupUnownedBaseShape(cx, base); + if (!nbase) + return nullptr; + + JS_ASSERT(shape == obj->lastProperty()); + + /* Find or create a property tree node labeled by our arguments. */ + StackShape child(nbase, id, slot, attrs, flags); + RootedShape parent(cx, shape->parent); + Shape *newShape = getOrLookupChildProperty(cx, obj, parent, child); + + if (!newShape) { + obj->checkShapeConsistency(); + return nullptr; + } + + shape = newShape; + } + + /* + * Can't fail now, so free the previous incarnation's slot if the new shape + * has no slot. But we do not need to free oldSlot (and must not, as trying + * to will botch an assertion in JSObject::freeSlot) if the new last + * property (shape here) has a slotSpan that does not cover it. + */ + if (hadSlot && !shape->hasSlot()) { + if (oldSlot < obj->slotSpan()) + obj->freeSlot(oldSlot); + /* Note: The optimization based on propertyRemovals is only relevant to the main thread. */ + if (cx->isJSContext()) + ++cx->asJSContext()->runtime()->propertyRemovals; + } + + obj->checkShapeConsistency(); + + return shape; +} + +template /* static */ Shape * +JSObject::putProperty(ExclusiveContext *cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags); +template /* static */ Shape * +JSObject::putProperty(ForkJoinContext *cx, + HandleObject obj, HandleId id, + PropertyOp getter, StrictPropertyOp setter, + uint32_t slot, unsigned attrs, + unsigned flags); + +template +/* static */ Shape * +JSObject::changeProperty(typename ExecutionModeTraits::ExclusiveContextType cx, + HandleObject obj, HandleShape shape, unsigned attrs, + unsigned mask, PropertyOp getter, StrictPropertyOp setter) +{ + JS_ASSERT(cx->isThreadLocal(obj)); + JS_ASSERT(obj->nativeContainsPure(shape)); + + attrs |= shape->attrs & mask; + JS_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED); + + /* Allow only shared (slotless) => unshared (slotful) transition. */ + JS_ASSERT(!((attrs ^ shape->attrs) & JSPROP_SHARED) || + !(attrs & JSPROP_SHARED)); + + if (mode == ParallelExecution) { + if (!types::IsTypePropertyIdMarkedNonData(obj, shape->propid())) + return nullptr; + } else { + types::MarkTypePropertyNonData(cx->asExclusiveContext(), obj, shape->propid()); + } + + if (getter == JS_PropertyStub) + getter = nullptr; + if (setter == JS_StrictPropertyStub) + setter = nullptr; + + if (!CheckCanChangeAttrs(cx, obj, shape, &attrs)) + return nullptr; + + if (shape->attrs == attrs && shape->getter() == getter && shape->setter() == setter) + return shape; + + /* + * Let JSObject::putProperty handle this |overwriting| case, including + * the conservation of shape->slot (if it's valid). We must not call + * removeProperty because it will free an allocated shape->slot, and + * putProperty won't re-allocate it. + */ + RootedId propid(cx, shape->propid()); + Shape *newShape = putProperty(cx, obj, propid, getter, setter, + shape->maybeSlot(), attrs, shape->flags); + + obj->checkShapeConsistency(); + return newShape; +} + +template /* static */ Shape * +JSObject::changeProperty(ExclusiveContext *cx, + HandleObject obj, HandleShape shape, + unsigned attrs, unsigned mask, + PropertyOp getter, StrictPropertyOp setter); +template /* static */ Shape * +JSObject::changeProperty(ForkJoinContext *cx, + HandleObject obj, HandleShape shape, + unsigned attrs, unsigned mask, + PropertyOp getter, StrictPropertyOp setter); + +bool +JSObject::removeProperty(ExclusiveContext *cx, jsid id_) +{ + RootedId id(cx, id_); + RootedObject self(cx, this); + + Shape **spp; + RootedShape shape(cx, Shape::search(cx, lastProperty(), id, &spp)); + if (!shape) + return true; + + /* + * If shape is not the last property added, or the last property cannot + * be removed, switch to dictionary mode. + */ + if (!self->inDictionaryMode() && (shape != self->lastProperty() || !self->canRemoveLastProperty())) { + if (!self->toDictionaryMode(cx)) + return false; + spp = self->lastProperty()->table().search(shape->propid(), false); + shape = SHAPE_FETCH(spp); + } + + /* + * 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 (self->inDictionaryMode()) { + spare = js_NewGCShape(cx); + if (!spare) + return false; + new (spare) Shape(shape->base()->unowned(), 0); + if (shape == self->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, self->lastProperty()->parent); + StackBaseShape base(self->lastProperty()->base()); + base.updateGetterSetter(previous->attrs, previous->getter(), previous->setter()); + BaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return false; + previous->base_ = nbase; + } + } + + /* If shape has a slot, free its slot number. */ + if (shape->hasSlot()) { + self->freeSlot(shape->slot()); + if (cx->isJSContext()) + ++cx->asJSContext()->runtime()->propertyRemovals; + } + + /* + * 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 (self->inDictionaryMode()) { + ShapeTable &table = self->lastProperty()->table(); + + if (SHAPE_HAD_COLLISION(*spp)) { + *spp = SHAPE_REMOVED; + ++table.removedCount; + --table.entryCount; + } else { + *spp = nullptr; + --table.entryCount; + +#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 = self->lastProperty(); + for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent) + JS_ASSERT_IF(aprop != shape, self->nativeContains(cx, aprop)); +#endif + } + + { + /* Remove shape from its non-circular doubly linked list. */ + Shape *oldLastProp = self->lastProperty(); + shape->removeFromDictionary(self); + + /* Hand off table from the old to new last property. */ + oldLastProp->handoffTableTo(self->lastProperty()); + } + + /* Generate a new shape for the object, infallibly. */ + JS_ALWAYS_TRUE(self->generateOwnShape(cx, 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(-1, cx); + } 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. + */ + JS_ASSERT(shape == self->lastProperty()); + self->removeLastProperty(cx); + } + + self->checkShapeConsistency(); + return true; +} + +/* static */ void +JSObject::clear(JSContext *cx, HandleObject obj) +{ + RootedShape shape(cx, obj->lastProperty()); + JS_ASSERT(obj->inDictionaryMode() == shape->inDictionary()); + + while (shape->parent) { + shape = shape->parent; + JS_ASSERT(obj->inDictionaryMode() == shape->inDictionary()); + } + JS_ASSERT(shape->isEmptyShape()); + + if (obj->inDictionaryMode()) + shape->listp = &obj->shape_; + + JS_ALWAYS_TRUE(JSObject::setLastProperty(cx, obj, shape)); + + ++cx->runtime()->propertyRemovals; + obj->checkShapeConsistency(); +} + +/* static */ bool +JSObject::rollbackProperties(ExclusiveContext *cx, HandleObject obj, uint32_t slotSpan) +{ + /* + * Remove properties from this object until it has a matching slot span. + * The object cannot have escaped in a way which would prevent safe + * removal of the last properties. + */ + JS_ASSERT(!obj->inDictionaryMode() && slotSpan <= obj->slotSpan()); + while (true) { + if (obj->lastProperty()->isEmptyShape()) { + JS_ASSERT(slotSpan == 0); + break; + } else { + uint32_t slot = obj->lastProperty()->slot(); + if (slot < slotSpan) + break; + JS_ASSERT(obj->getSlot(slot).isUndefined()); + } + if (!obj->removeProperty(cx, obj->lastProperty()->propid())) + return false; + } + + return true; +} + +Shape * +ObjectImpl::replaceWithNewEquivalentShape(ThreadSafeContext *cx, Shape *oldShape, Shape *newShape) +{ + JS_ASSERT(cx->isThreadLocal(this)); + JS_ASSERT(cx->isThreadLocal(oldShape)); + JS_ASSERT(cx->isInsideCurrentCompartment(oldShape)); + JS_ASSERT_IF(oldShape != lastProperty(), + inDictionaryMode() && + ((cx->isExclusiveContext() + ? nativeLookup(cx->asExclusiveContext(), oldShape->propidRef()) + : nativeLookupPure(oldShape->propidRef())) == oldShape)); + + ObjectImpl *self = this; + + if (!inDictionaryMode()) { + Rooted selfRoot(cx, self); + RootedShape newRoot(cx, newShape); + if (!toDictionaryMode(cx)) + return nullptr; + oldShape = selfRoot->lastProperty(); + self = selfRoot; + newShape = newRoot; + } + + if (!newShape) { + Rooted selfRoot(cx, self); + RootedShape oldRoot(cx, oldShape); + newShape = js_NewGCShape(cx); + if (!newShape) + return nullptr; + new (newShape) Shape(oldRoot->base()->unowned(), 0); + self = selfRoot; + oldShape = oldRoot; + } + + ShapeTable &table = self->lastProperty()->table(); + Shape **spp = oldShape->isEmptyShape() + ? nullptr + : table.search(oldShape->propidRef(), false); + + /* + * Splice the new shape into the same position as the old shape, preserving + * enumeration order (see bug 601399). + */ + StackShape nshape(oldShape); + newShape->initDictionaryShape(nshape, self->numFixedSlots(), oldShape->listp); + + JS_ASSERT(newShape->parent == oldShape); + oldShape->removeFromDictionary(self); + + if (newShape == self->lastProperty()) + oldShape->handoffTableTo(newShape); + + if (spp) + SHAPE_STORE_PRESERVING_COLLISION(spp, newShape); + return newShape; +} + +bool +JSObject::shadowingShapeChange(ExclusiveContext *cx, const Shape &shape) +{ + return generateOwnShape(cx); +} + +/* static */ bool +JSObject::clearParent(JSContext *cx, HandleObject obj) +{ + return setParent(cx, obj, NullPtr()); +} + +/* static */ bool +JSObject::setParent(JSContext *cx, HandleObject obj, HandleObject parent) +{ + if (parent && !parent->setDelegate(cx)) + return false; + + if (obj->inDictionaryMode()) { + StackBaseShape base(obj->lastProperty()); + base.parent = parent; + UnownedBaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return false; + + obj->lastProperty()->base()->adoptUnowned(nbase); + return true; + } + + Shape *newShape = Shape::setObjectParent(cx, parent, obj->getTaggedProto(), obj->shape_); + if (!newShape) + return false; + + obj->shape_ = newShape; + return true; +} + +/* static */ Shape * +Shape::setObjectParent(ExclusiveContext *cx, JSObject *parent, TaggedProto proto, Shape *last) +{ + if (last->getObjectParent() == parent) + return last; + + StackBaseShape base(last); + base.parent = parent; + + RootedShape lastRoot(cx, last); + return replaceLastProperty(cx, base, proto, lastRoot); +} + +/* static */ bool +JSObject::setMetadata(JSContext *cx, HandleObject obj, HandleObject metadata) +{ + if (obj->inDictionaryMode()) { + StackBaseShape base(obj->lastProperty()); + base.metadata = metadata; + UnownedBaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return false; + + obj->lastProperty()->base()->adoptUnowned(nbase); + return true; + } + + Shape *newShape = Shape::setObjectMetadata(cx, metadata, obj->getTaggedProto(), obj->shape_); + if (!newShape) + return false; + + obj->shape_ = newShape; + return true; +} + +/* static */ Shape * +Shape::setObjectMetadata(JSContext *cx, JSObject *metadata, TaggedProto proto, Shape *last) +{ + if (last->getObjectMetadata() == metadata) + return last; + + StackBaseShape base(last); + base.metadata = metadata; + + RootedShape lastRoot(cx, last); + return replaceLastProperty(cx, base, proto, lastRoot); +} + +/* static */ bool +js::ObjectImpl::preventExtensions(JSContext *cx, Handle obj) +{ +#ifdef DEBUG + bool extensible; + if (!JSObject::isExtensible(cx, obj, &extensible)) + return false; + MOZ_ASSERT(extensible, + "Callers must ensure |obj| is extensible before calling " + "preventExtensions"); +#endif + + if (Downcast(obj)->is()) { + RootedObject object(cx, obj->asObjectPtr()); + return js::Proxy::preventExtensions(cx, object); + } + + RootedObject self(cx, obj->asObjectPtr()); + + /* + * Force lazy properties to be resolved by iterating over the objects' own + * properties. + */ + AutoIdVector props(cx); + if (!js::GetPropertyNames(cx, self, JSITER_HIDDEN | JSITER_OWNONLY, &props)) + return false; + + /* + * Convert all dense elements to sparse properties. This will shrink the + * initialized length and capacity of the object to zero and ensure that no + * new dense elements can be added without calling growElements(), which + * checks isExtensible(). + */ + if (self->isNative() && !JSObject::sparsifyDenseElements(cx, self)) + return false; + + return self->setFlag(cx, BaseShape::NOT_EXTENSIBLE, GENERATE_SHAPE); +} + +bool +js::ObjectImpl::setFlag(ExclusiveContext *cx, /*BaseShape::Flag*/ uint32_t flag_, + GenerateShape generateShape) +{ + BaseShape::Flag flag = (BaseShape::Flag) flag_; + + if (lastProperty()->getObjectFlags() & flag) + return true; + + Rooted self(cx, this); + + if (inDictionaryMode()) { + if (generateShape == GENERATE_SHAPE && !generateOwnShape(cx)) + return false; + StackBaseShape base(self->lastProperty()); + base.flags |= flag; + UnownedBaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return false; + + self->lastProperty()->base()->adoptUnowned(nbase); + return true; + } + + Shape *newShape = + Shape::setObjectFlag(cx, flag, self->getTaggedProto(), self->lastProperty()); + if (!newShape) + return false; + + self->shape_ = newShape; + return true; +} + +bool +js::ObjectImpl::clearFlag(ExclusiveContext *cx, /*BaseShape::Flag*/ uint32_t flag) +{ + JS_ASSERT(inDictionaryMode()); + JS_ASSERT(lastProperty()->getObjectFlags() & flag); + + RootedObject self(cx, this->asObjectPtr()); + + StackBaseShape base(self->lastProperty()); + base.flags &= ~flag; + UnownedBaseShape *nbase = BaseShape::getUnowned(cx, base); + if (!nbase) + return false; + + self->lastProperty()->base()->adoptUnowned(nbase); + return true; +} + +/* static */ Shape * +Shape::setObjectFlag(ExclusiveContext *cx, BaseShape::Flag flag, TaggedProto proto, Shape *last) +{ + if (last->getObjectFlags() & flag) + return last; + + StackBaseShape base(last); + base.flags |= flag; + + RootedShape lastRoot(cx, last); + return replaceLastProperty(cx, base, proto, lastRoot); +} + +/* static */ inline HashNumber +StackBaseShape::hash(const StackBaseShape *base) +{ + HashNumber hash = base->flags; + hash = RotateLeft(hash, 4) ^ (uintptr_t(base->clasp) >> 3); + hash = RotateLeft(hash, 4) ^ (uintptr_t(base->parent) >> 3); + hash = RotateLeft(hash, 4) ^ (uintptr_t(base->metadata) >> 3); + hash = RotateLeft(hash, 4) ^ uintptr_t(base->rawGetter); + hash = RotateLeft(hash, 4) ^ uintptr_t(base->rawSetter); + return hash; +} + +/* static */ inline bool +StackBaseShape::match(UnownedBaseShape *key, const StackBaseShape *lookup) +{ + return key->flags == lookup->flags + && key->clasp_ == lookup->clasp + && key->parent == lookup->parent + && key->metadata == lookup->metadata + && key->rawGetter == lookup->rawGetter + && key->rawSetter == lookup->rawSetter; +} + +void +StackBaseShape::trace(JSTracer *trc) +{ + if (parent) { + gc::MarkObjectRoot(trc, (JSObject**)&parent, + "StackBaseShape parent"); + } + if (metadata) { + gc::MarkObjectRoot(trc, (JSObject**)&metadata, + "StackBaseShape metadata"); + } + if ((flags & BaseShape::HAS_GETTER_OBJECT) && rawGetter) { + gc::MarkObjectRoot(trc, (JSObject**)&rawGetter, + "StackBaseShape getter"); + } + if ((flags & BaseShape::HAS_SETTER_OBJECT) && rawSetter) { + gc::MarkObjectRoot(trc, (JSObject**)&rawSetter, + "StackBaseShape setter"); + } +} + +/* static */ UnownedBaseShape* +BaseShape::getUnowned(ExclusiveContext *cx, StackBaseShape &base) +{ + BaseShapeSet &table = cx->compartment()->baseShapes; + + if (!table.initialized() && !table.init()) + return nullptr; + + DependentAddPtr p(cx, table, &base); + if (p) + return *p; + + RootedGeneric root(cx, &base); + + BaseShape *nbase_ = js_NewGCBaseShape(cx); + if (!nbase_) + return nullptr; + + new (nbase_) BaseShape(*root); + + UnownedBaseShape *nbase = static_cast(nbase_); + + if (!p.add(cx, table, root, nbase)) + return nullptr; + + return nbase; +} + +/* static */ UnownedBaseShape * +BaseShape::lookupUnowned(ThreadSafeContext *cx, const StackBaseShape &base) +{ + BaseShapeSet &table = cx->compartment_->baseShapes; + + if (!table.initialized()) + return nullptr; + + BaseShapeSet::Ptr p = table.readonlyThreadsafeLookup(&base); + return *p; +} + +void +BaseShape::assertConsistency() +{ +#ifdef DEBUG + if (isOwned()) { + UnownedBaseShape *unowned = baseUnowned(); + JS_ASSERT(hasGetterObject() == unowned->hasGetterObject()); + JS_ASSERT(hasSetterObject() == unowned->hasSetterObject()); + JS_ASSERT_IF(hasGetterObject(), getterObject() == unowned->getterObject()); + JS_ASSERT_IF(hasSetterObject(), setterObject() == unowned->setterObject()); + JS_ASSERT(getObjectParent() == unowned->getObjectParent()); + JS_ASSERT(getObjectMetadata() == unowned->getObjectMetadata()); + JS_ASSERT(getObjectFlags() == unowned->getObjectFlags()); + } +#endif +} + +void +JSCompartment::sweepBaseShapeTable() +{ + gcstats::AutoPhase ap(runtimeFromMainThread()->gcStats, + gcstats::PHASE_SWEEP_TABLES_BASE_SHAPE); + + if (baseShapes.initialized()) { + for (BaseShapeSet::Enum e(baseShapes); !e.empty(); e.popFront()) { + UnownedBaseShape *base = e.front(); + if (IsBaseShapeAboutToBeFinalized(&base)) + e.removeFront(); + } + } +} + +void +BaseShape::finalize(FreeOp *fop) +{ + if (table_) { + fop->delete_(table_); + table_ = nullptr; + } +} + +inline +InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto(nullptr) +{ +} + +inline +InitialShapeEntry::InitialShapeEntry(const ReadBarriered &shape, TaggedProto proto) + : shape(shape), proto(proto) +{ +} + +inline InitialShapeEntry::Lookup +InitialShapeEntry::getLookup() const +{ + return Lookup(shape->getObjectClass(), proto, shape->getObjectParent(), shape->getObjectMetadata(), + shape->numFixedSlots(), shape->getObjectFlags()); +} + +/* static */ inline HashNumber +InitialShapeEntry::hash(const Lookup &lookup) +{ + HashNumber hash = uintptr_t(lookup.clasp) >> 3; + hash = RotateLeft(hash, 4) ^ + (uintptr_t(lookup.hashProto.toWord()) >> 3); + hash = RotateLeft(hash, 4) ^ + (uintptr_t(lookup.hashParent) >> 3) ^ + (uintptr_t(lookup.hashMetadata) >> 3); + return hash + lookup.nfixed; +} + +/* static */ inline bool +InitialShapeEntry::match(const InitialShapeEntry &key, const Lookup &lookup) +{ + const Shape *shape = *key.shape.unsafeGet(); + return lookup.clasp == shape->getObjectClass() + && lookup.matchProto.toWord() == key.proto.toWord() + && lookup.matchParent == shape->getObjectParent() + && lookup.matchMetadata == shape->getObjectMetadata() + && lookup.nfixed == shape->numFixedSlots() + && lookup.baseFlags == shape->getObjectFlags(); +} + +#ifdef JSGC_GENERATIONAL + +/* + * This class is used to add a post barrier on the initialShapes set, as the key + * is calculated based on several objects which may be moved by generational GC. + */ +class InitialShapeSetRef : public BufferableRef +{ + InitialShapeSet *set; + const Class *clasp; + TaggedProto proto; + JSObject *parent; + JSObject *metadata; + size_t nfixed; + uint32_t objectFlags; + + public: + InitialShapeSetRef(InitialShapeSet *set, + const Class *clasp, + TaggedProto proto, + JSObject *parent, + JSObject *metadata, + size_t nfixed, + uint32_t objectFlags) + : set(set), + clasp(clasp), + proto(proto), + parent(parent), + metadata(metadata), + nfixed(nfixed), + objectFlags(objectFlags) + {} + + void mark(JSTracer *trc) { + TaggedProto priorProto = proto; + JSObject *priorParent = parent; + JSObject *priorMetadata = metadata; + if (proto.isObject()) + Mark(trc, reinterpret_cast(&proto), "initialShapes set proto"); + if (parent) + Mark(trc, &parent, "initialShapes set parent"); + if (metadata) + Mark(trc, &metadata, "initialShapes set metadata"); + if (proto == priorProto && parent == priorParent && metadata == priorMetadata) + return; + + /* Find the original entry, which must still be present. */ + InitialShapeEntry::Lookup lookup(clasp, priorProto, + priorParent, parent, + priorMetadata, metadata, + nfixed, objectFlags); + InitialShapeSet::Ptr p = set->lookup(lookup); + JS_ASSERT(p); + + /* Update the entry's possibly-moved proto, and ensure lookup will still match. */ + InitialShapeEntry &entry = const_cast(*p); + entry.proto = proto; + lookup.matchProto = proto; + + /* Rekey the entry. */ + set->rekeyAs(lookup, + InitialShapeEntry::Lookup(clasp, proto, parent, metadata, nfixed, objectFlags), + *p); + } +}; + +#ifdef JS_GC_ZEAL +void +JSCompartment::checkInitialShapesTableAfterMovingGC() +{ + if (!initialShapes.initialized()) + return; + + /* + * 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. + */ + JS::shadow::Runtime *rt = JS::shadow::Runtime::asShadowRuntime(runtimeFromMainThread()); + for (InitialShapeSet::Enum e(initialShapes); !e.empty(); e.popFront()) { + InitialShapeEntry entry = e.front(); + TaggedProto proto = entry.proto; + Shape *shape = entry.shape.get(); + + JS_ASSERT_IF(proto.isObject(), !IsInsideNursery(rt, proto.toObject())); + JS_ASSERT(!IsInsideNursery(rt, shape->getObjectParent())); + JS_ASSERT(!IsInsideNursery(rt, shape->getObjectMetadata())); + + InitialShapeEntry::Lookup lookup(shape->getObjectClass(), + proto, + shape->getObjectParent(), + shape->getObjectMetadata(), + shape->numFixedSlots(), + shape->getObjectFlags()); + InitialShapeSet::Ptr ptr = initialShapes.lookup(lookup); + JS_ASSERT(ptr.found() && &*ptr == &e.front()); + } +} +#endif + +#endif + +/* static */ Shape * +EmptyShape::getInitialShape(ExclusiveContext *cx, const Class *clasp, TaggedProto proto, + JSObject *parent, JSObject *metadata, + size_t nfixed, uint32_t objectFlags) +{ + JS_ASSERT_IF(proto.isObject(), cx->isInsideCurrentCompartment(proto.toObject())); + JS_ASSERT_IF(parent, cx->isInsideCurrentCompartment(parent)); + + InitialShapeSet &table = cx->compartment()->initialShapes; + + if (!table.initialized() && !table.init()) + return nullptr; + + typedef InitialShapeEntry::Lookup Lookup; + DependentAddPtr + p(cx, table, Lookup(clasp, proto, parent, metadata, nfixed, objectFlags)); + if (p) + return p->shape; + + Rooted protoRoot(cx, proto); + RootedObject parentRoot(cx, parent); + RootedObject metadataRoot(cx, metadata); + + StackBaseShape base(cx, clasp, parent, metadata, objectFlags); + Rooted nbase(cx, BaseShape::getUnowned(cx, base)); + if (!nbase) + return nullptr; + + Shape *shape = cx->compartment()->propertyTree.newShape(cx); + if (!shape) + return nullptr; + new (shape) EmptyShape(nbase, nfixed); + + Lookup lookup(clasp, protoRoot, parentRoot, metadataRoot, nfixed, objectFlags); + if (!p.add(cx, table, lookup, InitialShapeEntry(shape, protoRoot))) + return nullptr; + +#ifdef JSGC_GENERATIONAL + if (cx->hasNursery()) { + if ((protoRoot.isObject() && cx->nursery().isInside(protoRoot.toObject())) || + cx->nursery().isInside(parentRoot.get()) || + cx->nursery().isInside(metadataRoot.get())) + { + InitialShapeSetRef ref( + &table, clasp, protoRoot, parentRoot, metadataRoot, nfixed, objectFlags); + cx->asJSContext()->runtime()->gcStoreBuffer.putGeneric(ref); + } + } +#endif + + return shape; +} + +/* static */ Shape * +EmptyShape::getInitialShape(ExclusiveContext *cx, const Class *clasp, TaggedProto proto, + JSObject *parent, JSObject *metadata, + AllocKind kind, uint32_t objectFlags) +{ + return getInitialShape(cx, clasp, proto, parent, metadata, GetGCKindSlots(kind, clasp), objectFlags); +} + +void +NewObjectCache::invalidateEntriesForShape(JSContext *cx, HandleShape shape, HandleObject proto) +{ + const Class *clasp = shape->getObjectClass(); + + gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots()); + if (CanBeFinalizedInBackground(kind, clasp)) + kind = GetBackgroundAllocKind(kind); + + Rooted global(cx, &shape->getObjectParent()->global()); + Rooted type(cx, cx->getNewType(clasp, proto.get())); + + EntryIndex entry; + if (lookupGlobal(clasp, global, kind, &entry)) + PodZero(&entries[entry]); + if (!proto->is() && lookupProto(clasp, proto, kind, &entry)) + PodZero(&entries[entry]); + if (lookupType(type, kind, &entry)) + PodZero(&entries[entry]); +} + +/* static */ void +EmptyShape::insertInitialShape(ExclusiveContext *cx, HandleShape shape, HandleObject proto) +{ + InitialShapeEntry::Lookup lookup(shape->getObjectClass(), TaggedProto(proto), + shape->getObjectParent(), shape->getObjectMetadata(), + shape->numFixedSlots(), shape->getObjectFlags()); + + InitialShapeSet::Ptr p = cx->compartment()->initialShapes.lookup(lookup); + JS_ASSERT(p); + + InitialShapeEntry &entry = const_cast(*p); + + /* The new shape had better be rooted at the old one. */ +#ifdef DEBUG + Shape *nshape = shape; + while (!nshape->isEmptyShape()) + nshape = nshape->previous(); + JS_ASSERT(nshape == entry.shape); +#endif + + entry.shape = shape.get(); + + /* + * 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 the main + * thread, as it will not use the new object cache for allocations. + */ + if (cx->isJSContext()) { + JSContext *ncx = cx->asJSContext(); + ncx->runtime()->newObjectCache.invalidateEntriesForShape(ncx, shape, proto); + } +} + +void +JSCompartment::sweepInitialShapeTable() +{ + gcstats::AutoPhase ap(runtimeFromMainThread()->gcStats, + gcstats::PHASE_SWEEP_TABLES_INITIAL_SHAPE); + + if (initialShapes.initialized()) { + for (InitialShapeSet::Enum e(initialShapes); !e.empty(); e.popFront()) { + const InitialShapeEntry &entry = e.front(); + Shape *shape = entry.shape; + JSObject *proto = entry.proto.raw(); + if (IsShapeAboutToBeFinalized(&shape) || (entry.proto.isObject() && IsObjectAboutToBeFinalized(&proto))) { + e.removeFront(); + } else { +#ifdef DEBUG + DebugOnly parent = shape->getObjectParent(); + JS_ASSERT(!parent || !IsObjectAboutToBeFinalized(&parent)); + JS_ASSERT(parent == shape->getObjectParent()); +#endif + if (shape != entry.shape || proto != entry.proto.raw()) { + InitialShapeEntry newKey(shape, proto); + e.rekeyFront(newKey.getLookup(), newKey); + } + } + } + } +} + +void +AutoRooterGetterSetter::Inner::trace(JSTracer *trc) +{ + if ((attrs & JSPROP_GETTER) && *pgetter) + gc::MarkObjectRoot(trc, (JSObject**) pgetter, "AutoRooterGetterSetter getter"); + if ((attrs & JSPROP_SETTER) && *psetter) + gc::MarkObjectRoot(trc, (JSObject**) psetter, "AutoRooterGetterSetter setter"); +}