diff -r 000000000000 -r 6474c204b198 js/src/jspropertytree.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jspropertytree.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,373 @@ +/* -*- 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 "jscntxt.h" +#include "jsgc.h" +#include "jstypes.h" + +#include "vm/Shape.h" + +#include "jsgcinlines.h" + +#include "vm/Shape-inl.h" + +using namespace js; + +inline HashNumber +ShapeHasher::hash(const Lookup &l) +{ + return l.hash(); +} + +inline bool +ShapeHasher::match(const Key k, const Lookup &l) +{ + return k->matches(l); +} + +Shape * +PropertyTree::newShape(ExclusiveContext *cx) +{ + Shape *shape = js_NewGCShape(cx); + if (!shape) + js_ReportOutOfMemory(cx); + return shape; +} + +static KidsHash * +HashChildren(Shape *kid1, Shape *kid2) +{ + KidsHash *hash = js_new(); + if (!hash || !hash->init(2)) { + js_delete(hash); + return nullptr; + } + + JS_ALWAYS_TRUE(hash->putNew(kid1, kid1)); + JS_ALWAYS_TRUE(hash->putNew(kid2, kid2)); + return hash; +} + +bool +PropertyTree::insertChild(ExclusiveContext *cx, Shape *parent, Shape *child) +{ + JS_ASSERT(!parent->inDictionary()); + JS_ASSERT(!child->parent); + JS_ASSERT(!child->inDictionary()); + JS_ASSERT(child->compartment() == parent->compartment()); + JS_ASSERT(cx->isInsideCurrentCompartment(this)); + + KidsPointer *kidp = &parent->kids; + + if (kidp->isNull()) { + child->setParent(parent); + kidp->setShape(child); + return true; + } + + if (kidp->isShape()) { + Shape *shape = kidp->toShape(); + JS_ASSERT(shape != child); + JS_ASSERT(!shape->matches(child)); + + KidsHash *hash = HashChildren(shape, child); + if (!hash) { + js_ReportOutOfMemory(cx); + return false; + } + kidp->setHash(hash); + child->setParent(parent); + return true; + } + + if (!kidp->toHash()->putNew(child, child)) { + js_ReportOutOfMemory(cx); + return false; + } + + child->setParent(parent); + return true; +} + +void +Shape::removeChild(Shape *child) +{ + JS_ASSERT(!child->inDictionary()); + JS_ASSERT(child->parent == this); + + KidsPointer *kidp = &kids; + + if (kidp->isShape()) { + JS_ASSERT(kidp->toShape() == child); + kidp->setNull(); + child->parent = nullptr; + return; + } + + KidsHash *hash = kidp->toHash(); + JS_ASSERT(hash->count() >= 2); /* otherwise kidp->isShape() should be true */ + + hash->remove(child); + child->parent = nullptr; + + if (hash->count() == 1) { + /* Convert from HASH form back to SHAPE form. */ + KidsHash::Range r = hash->all(); + Shape *otherChild = r.front(); + JS_ASSERT((r.popFront(), r.empty())); /* No more elements! */ + kidp->setShape(otherChild); + js_delete(hash); + } +} + +Shape * +PropertyTree::getChild(ExclusiveContext *cx, Shape *parentArg, StackShape &unrootedChild) +{ + RootedShape parent(cx, parentArg); + JS_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(unrootedChild)) + existingShape = kid; + } else if (kidp->isHash()) { + if (KidsHash::Ptr p = kidp->toHash()->lookup(unrootedChild)) + existingShape = *p; + } else { + /* If kidp->isNull(), we always insert. */ + } + +#ifdef JSGC_INCREMENTAL + if (existingShape) { + JS::Zone *zone = existingShape->zone(); + if (zone->needsBarrier()) { + /* + * We need a read barrier for the shape tree, since these are weak + * pointers. + */ + Shape *tmp = existingShape; + MarkShapeUnbarriered(zone->barrierTracer(), &tmp, "read barrier"); + JS_ASSERT(tmp == existingShape); + } else if (zone->isGCSweeping() && !existingShape->isMarked() && + !existingShape->arenaHeader()->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. + */ + JS_ASSERT(parent->isMarked()); + parent->removeChild(existingShape); + existingShape = nullptr; + } + } +#endif + + if (existingShape) + return existingShape; + + RootedGeneric child(cx, &unrootedChild); + + Shape *shape = newShape(cx); + if (!shape) + return nullptr; + + new (shape) Shape(*child, parent->numFixedSlots()); + + if (!insertChild(cx, parent, shape)) + return nullptr; + + return shape; +} + +Shape * +PropertyTree::lookupChild(ThreadSafeContext *cx, Shape *parent, const StackShape &child) +{ + /* Keep this in sync with the logic of getChild above. */ + Shape *shape = nullptr; + + JS_ASSERT(parent); + + KidsPointer *kidp = &parent->kids; + if (kidp->isShape()) { + Shape *kid = kidp->toShape(); + if (kid->matches(child)) + shape = kid; + } else if (kidp->isHash()) { + if (KidsHash::Ptr p = kidp->toHash()->readonlyThreadsafeLookup(child)) + shape = *p; + } else { + return nullptr; + } + +#if defined(JSGC_INCREMENTAL) && defined(DEBUG) + if (shape) { + JS::Zone *zone = shape->arenaHeader()->zone; + JS_ASSERT(!zone->needsBarrier()); + JS_ASSERT(!(zone->isGCSweeping() && !shape->isMarked() && + !shape->arenaHeader()->allocatedDuringIncremental)); + } +#endif + + return shape; +} + +void +Shape::sweep() +{ + if (inDictionary()) + return; + + /* + * We detach the child from the parent if the parent is reachable. + * + * Note that due to incremental sweeping, the parent pointer may point + * to the original reachable parent, or it may point to a new live + * object allocated in the same cell that used to hold the parent. + * + * There are three cases: + * + * Case 1: parent is not marked - parent is unreachable, may have been + * finalized, and the cell may subsequently have been + * reallocated to a compartment that is not being marked (cells + * are marked when allocated in a compartment that is currenly + * being marked by the collector). + * + * Case 2: parent is marked and is in a different compartment - parent + * has been freed and reallocated to compartment that was being + * marked. + * + * Case 3: parent is marked and is in the same compartment - parent is + * stil reachable and we need to detach from it. + */ + if (parent && parent->isMarked() && parent->compartment() == compartment()) + parent->removeChild(this); +} + +void +Shape::finalize(FreeOp *fop) +{ + if (!inDictionary() && kids.isHash()) + fop->delete_(kids.toHash()); +} + +#ifdef DEBUG + +void +KidsPointer::checkConsistency(Shape *aKid) const +{ + if (isShape()) { + JS_ASSERT(toShape() == aKid); + } else { + JS_ASSERT(isHash()); + KidsHash *hash = toHash(); + KidsHash::Ptr ptr = hash->lookup(aKid); + JS_ASSERT(*ptr == aKid); + } +} + +void +Shape::dump(JSContext *cx, FILE *fp) const +{ + /* This is only used from gdb, so allowing GC here would just be confusing. */ + gc::AutoSuppressGC suppress(cx); + + jsid propid = this->propid(); + + JS_ASSERT(!JSID_IS_VOID(propid)); + + if (JSID_IS_INT(propid)) { + fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid)); + } else { + JSLinearString *str; + if (JSID_IS_ATOM(propid)) { + str = JSID_TO_ATOM(propid); + } else { + JS_ASSERT(JSID_IS_OBJECT(propid)); + Value v = IdToValue(propid); + JSString *s = ToStringSlow(cx, v); + fputs("object ", fp); + str = s ? s->ensureLinear(cx) : nullptr; + } + if (!str) + fputs("", fp); + else + FileEscapedString(fp, str, '"'); + } + + fprintf(fp, " g/s %p/%p slot %d attrs %x ", + JS_FUNC_TO_DATA_PTR(void *, base()->rawGetter), + JS_FUNC_TO_DATA_PTR(void *, base()->rawSetter), + 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(JSContext *cx, int level, FILE *fp) const +{ + if (!parent) { + JS_ASSERT(level == 0); + JS_ASSERT(JSID_IS_EMPTY(propid_)); + fprintf(fp, "class %s emptyShape\n", getObjectClass()->name); + } else { + fprintf(fp, "%*sid ", level, ""); + dump(cx, fp); + } + + if (!kids.isNull()) { + ++level; + if (kids.isShape()) { + Shape *kid = kids.toShape(); + JS_ASSERT(kid->parent == this); + kid->dumpSubtree(cx, level, fp); + } else { + const KidsHash &hash = *kids.toHash(); + for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) { + Shape *kid = range.front(); + + JS_ASSERT(kid->parent == this); + kid->dumpSubtree(cx, level, fp); + } + } + } +} + +#endif