diff options
Diffstat (limited to 'js/src/jspropertytree.cpp')
| -rw-r--r-- | js/src/jspropertytree.cpp | 450 |
1 files changed, 450 insertions, 0 deletions
diff --git a/js/src/jspropertytree.cpp b/js/src/jspropertytree.cpp new file mode 100644 index 000000000..f7581b970 --- /dev/null +++ b/js/src/jspropertytree.cpp @@ -0,0 +1,450 @@ +/* -*- 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/. */ + +#include "jspropertytree.h" + +#include "mozilla/DebugOnly.h" + +#include "jscntxt.h" +#include "jsgc.h" +#include "jstypes.h" + +#include "vm/Shape.h" + +#include "vm/NativeObject-inl.h" +#include "vm/Shape-inl.h" + +using namespace js; +using namespace js::gc; + +using mozilla::DebugOnly; + +inline HashNumber +ShapeHasher::hash(const Lookup& l) +{ + return l.hash(); +} + +inline bool +ShapeHasher::match(const Key k, const Lookup& l) +{ + return k->matches(l); +} + +static KidsHash* +HashChildren(Shape* kid1, Shape* kid2) +{ + KidsHash* hash = js_new<KidsHash>(); + if (!hash || !hash->init(2)) { + js_delete(hash); + return nullptr; + } + + hash->putNewInfallible(StackShape(kid1), kid1); + hash->putNewInfallible(StackShape(kid2), kid2); + return hash; +} + +bool +PropertyTree::insertChild(ExclusiveContext* 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_); + + KidsPointer* kidp = &parent->kids; + + if (kidp->isNull()) { + child->setParent(parent); + kidp->setShape(child); + return true; + } + + if (kidp->isShape()) { + Shape* shape = kidp->toShape(); + MOZ_ASSERT(shape != child); + MOZ_ASSERT(!shape->matches(child)); + + KidsHash* hash = HashChildren(shape, child); + if (!hash) { + ReportOutOfMemory(cx); + return false; + } + kidp->setHash(hash); + child->setParent(parent); + return true; + } + + if (!kidp->toHash()->putNew(StackShape(child), child)) { + ReportOutOfMemory(cx); + return false; + } + + child->setParent(parent); + return true; +} + +void +Shape::removeChild(Shape* child) +{ + MOZ_ASSERT(!child->inDictionary()); + MOZ_ASSERT(child->parent == this); + + KidsPointer* kidp = &kids; + + if (kidp->isShape()) { + MOZ_ASSERT(kidp->toShape() == child); + kidp->setNull(); + child->parent = nullptr; + return; + } + + KidsHash* hash = kidp->toHash(); + MOZ_ASSERT(hash->count() >= 2); /* otherwise kidp->isShape() should be true */ + +#ifdef DEBUG + size_t oldCount = hash->count(); +#endif + + hash->remove(StackShape(child)); + child->parent = nullptr; + + MOZ_ASSERT(hash->count() == oldCount - 1); + + if (hash->count() == 1) { + /* Convert from HASH form back to SHAPE form. */ + KidsHash::Range r = hash->all(); + Shape* otherChild = r.front(); + MOZ_ASSERT((r.popFront(), r.empty())); /* No more elements! */ + kidp->setShape(otherChild); + js_delete(hash); + } +} + +Shape* +PropertyTree::getChild(ExclusiveContext* cx, Shape* parentArg, Handle<StackShape> child) +{ + RootedShape parent(cx, parentArg); + 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. + */ + KidsPointer* kidp = &parent->kids; + if (kidp->isShape()) { + Shape* kid = kidp->toShape(); + if (kid->matches(child)) + existingShape = kid; + } else if (kidp->isHash()) { + if (KidsHash::Ptr p = kidp->toHash()->lookup(child)) + existingShape = *p; + } else { + /* If kidp->isNull(), we always insert. */ + } + + if (existingShape) { + JS::Zone* zone = existingShape->zone(); + if (zone->needsIncrementalBarrier()) { + /* + * We need a read barrier for the shape tree, since these are weak + * pointers. + */ + Shape* tmp = existingShape; + TraceManuallyBarrieredEdge(zone->barrierTracer(), &tmp, "read barrier"); + MOZ_ASSERT(tmp == existingShape); + } else if (zone->isGCSweeping() && !existingShape->isMarked() && + !existingShape->arena()->allocatedDuringIncremental) + { + /* + * 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->isMarked()); + parent->removeChild(existingShape); + existingShape = nullptr; + } else if (existingShape->isMarked(gc::GRAY)) { + UnmarkGrayShapeRecursively(existingShape); + } + } + + if (existingShape) + return existingShape; + + Shape* shape = Shape::new_(cx, child, parent->numFixedSlots()); + if (!shape) + return nullptr; + + if (!insertChild(cx, parent, shape)) + return nullptr; + + return shape; +} + +void +Shape::sweep() +{ + /* + * 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. + */ + if (parent && parent->isMarked()) { + if (inDictionary()) { + if (parent->listp == &parent) + parent->listp = nullptr; + } else { + parent->removeChild(this); + } + } +} + +void +Shape::finalize(FreeOp* fop) +{ + if (!inDictionary() && kids.isHash()) + fop->delete_(kids.toHash()); +} + +void +Shape::fixupDictionaryShapeAfterMovingGC() +{ + if (!listp) + return; + + // The listp field either points to the parent field of the next shape in + // the list if there is one. Otherwise if this shape is the last in the + // list then it points to the shape_ field of the object the list is for. + // We can tell which it is because the base shape is owned if this is the + // last property and not otherwise. + bool listpPointsIntoShape = !MaybeForwarded(base())->isOwned(); + +#ifdef DEBUG + // Check that we got this right by interrogating the arena. + // We use a fake cell pointer for this: it might not point to the beginning + // of a cell, but will point into the right arena and will have the right + // alignment. + Cell* cell = reinterpret_cast<Cell*>(uintptr_t(listp) & ~CellMask); + AllocKind kind = TenuredCell::fromPointer(cell)->getAllocKind(); + MOZ_ASSERT_IF(listpPointsIntoShape, IsShapeAllocKind(kind)); + MOZ_ASSERT_IF(!listpPointsIntoShape, IsObjectAllocKind(kind)); +#endif + + if (listpPointsIntoShape) { + // listp points to the parent field of the next shape. + Shape* next = reinterpret_cast<Shape*>(uintptr_t(listp) - offsetof(Shape, parent)); + if (gc::IsForwarded(next)) + listp = &gc::Forwarded(next)->parent; + } else { + // listp points to the shape_ field of an object. + JSObject* last = reinterpret_cast<JSObject*>(uintptr_t(listp) - ShapedObject::offsetOfShape()); + if (gc::IsForwarded(last)) + listp = &gc::Forwarded(last)->as<NativeObject>().shape_; + } +} + +void +Shape::fixupShapeTreeAfterMovingGC() +{ + if (kids.isNull()) + return; + + if (kids.isShape()) { + if (gc::IsForwarded(kids.toShape())) + kids.setShape(gc::Forwarded(kids.toShape())); + return; + } + + MOZ_ASSERT(kids.isHash()); + KidsHash* kh = kids.toHash(); + for (KidsHash::Enum e(*kh); !e.empty(); e.popFront()) { + Shape* key = e.front(); + if (IsForwarded(key)) + key = Forwarded(key); + + BaseShape* base = key->base(); + if (IsForwarded(base)) + base = Forwarded(base); + UnownedBaseShape* unowned = base->unowned(); + if (IsForwarded(unowned)) + unowned = Forwarded(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->slotInfo & Shape::SLOT_MASK, + key->attrs, + key->flags); + lookup.updateGetterSetter(getter, setter); + e.rekeyFront(lookup, key); + } +} + +void +Shape::fixupAfterMovingGC() +{ + if (inDictionary()) + fixupDictionaryShapeAfterMovingGC(); + else + fixupShapeTreeAfterMovingGC(); +} + +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->kids.isHash()) { + // Relocating the getterObj or setterObj will have changed our location + // in our parent's KidsHash, 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); + + KidsHash* kh = parent->kids.toHash(); + MOZ_ALWAYS_TRUE(kh->rekeyAs(original, updated, this)); + } + + asAccessorShape().getterObj = postGetter; + asAccessorShape().setterObj = postSetter; + + MOZ_ASSERT_IF(parent && !parent->inDictionary() && parent->kids.isHash(), + parent->kids.toHash()->has(StackShape(this))); +} + +#ifdef DEBUG + +void +KidsPointer::checkConsistency(Shape* aKid) const +{ + if (isShape()) { + MOZ_ASSERT(toShape() == aKid); + } else { + MOZ_ASSERT(isHash()); + KidsHash* hash = toHash(); + KidsHash::Ptr ptr = hash->lookup(StackShape(aKid)); + MOZ_ASSERT(*ptr == aKid); + } +} + +void +Shape::dump(FILE* fp) const +{ + jsid propid = this->propid(); + + MOZ_ASSERT(!JSID_IS_VOID(propid)); + + if (JSID_IS_INT(propid)) { + fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid)); + } else if (JSID_IS_ATOM(propid)) { + if (JSLinearString* str = JSID_TO_ATOM(propid)) + FileEscapedString(fp, str, '"'); + else + fputs("<error>", fp); + } else { + MOZ_ASSERT(JSID_IS_SYMBOL(propid)); + JSID_TO_SYMBOL(propid)->dump(fp); + } + + fprintf(fp, " g/s %p/%p slot %d attrs %x ", + JS_FUNC_TO_DATA_PTR(void*, getter()), + JS_FUNC_TO_DATA_PTR(void*, setter()), + hasSlot() ? slot() : -1, attrs); + + if (attrs) { + int first = 1; + fputs("(", fp); +#define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(&(" " #display)[first], fp), first = 0 + DUMP_ATTR(ENUMERATE, enumerate); + DUMP_ATTR(READONLY, readonly); + DUMP_ATTR(PERMANENT, permanent); + DUMP_ATTR(GETTER, getter); + DUMP_ATTR(SETTER, setter); + DUMP_ATTR(SHARED, shared); +#undef DUMP_ATTR + fputs(") ", fp); + } + + fprintf(fp, "flags %x ", flags); + if (flags) { + int first = 1; + fputs("(", fp); +#define DUMP_FLAG(name, display) if (flags & name) fputs(&(" " #display)[first], fp), first = 0 + DUMP_FLAG(IN_DICTIONARY, in_dictionary); +#undef DUMP_FLAG + fputs(") ", fp); + } +} + +void +Shape::dumpSubtree(int level, FILE* fp) const +{ + if (!parent) { + MOZ_ASSERT(level == 0); + MOZ_ASSERT(JSID_IS_EMPTY(propid_)); + fprintf(fp, "class %s emptyShape\n", getObjectClass()->name); + } else { + fprintf(fp, "%*sid ", level, ""); + dump(fp); + } + + if (!kids.isNull()) { + ++level; + if (kids.isShape()) { + Shape* kid = kids.toShape(); + MOZ_ASSERT(kid->parent == this); + kid->dumpSubtree(level, fp); + } else { + const KidsHash& hash = *kids.toHash(); + for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) { + Shape* kid = range.front(); + + MOZ_ASSERT(kid->parent == this); + kid->dumpSubtree(level, fp); + } + } + } +} + +#endif |