michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jspropertytree.h"
michael@0: 
michael@0: #include "jscntxt.h"
michael@0: #include "jsgc.h"
michael@0: #include "jstypes.h"
michael@0: 
michael@0: #include "vm/Shape.h"
michael@0: 
michael@0: #include "jsgcinlines.h"
michael@0: 
michael@0: #include "vm/Shape-inl.h"
michael@0: 
michael@0: using namespace js;
michael@0: 
michael@0: inline HashNumber
michael@0: ShapeHasher::hash(const Lookup &l)
michael@0: {
michael@0:     return l.hash();
michael@0: }
michael@0: 
michael@0: inline bool
michael@0: ShapeHasher::match(const Key k, const Lookup &l)
michael@0: {
michael@0:     return k->matches(l);
michael@0: }
michael@0: 
michael@0: Shape *
michael@0: PropertyTree::newShape(ExclusiveContext *cx)
michael@0: {
michael@0:     Shape *shape = js_NewGCShape(cx);
michael@0:     if (!shape)
michael@0:         js_ReportOutOfMemory(cx);
michael@0:     return shape;
michael@0: }
michael@0: 
michael@0: static KidsHash *
michael@0: HashChildren(Shape *kid1, Shape *kid2)
michael@0: {
michael@0:     KidsHash *hash = js_new<KidsHash>();
michael@0:     if (!hash || !hash->init(2)) {
michael@0:         js_delete(hash);
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     JS_ALWAYS_TRUE(hash->putNew(kid1, kid1));
michael@0:     JS_ALWAYS_TRUE(hash->putNew(kid2, kid2));
michael@0:     return hash;
michael@0: }
michael@0: 
michael@0: bool
michael@0: PropertyTree::insertChild(ExclusiveContext *cx, Shape *parent, Shape *child)
michael@0: {
michael@0:     JS_ASSERT(!parent->inDictionary());
michael@0:     JS_ASSERT(!child->parent);
michael@0:     JS_ASSERT(!child->inDictionary());
michael@0:     JS_ASSERT(child->compartment() == parent->compartment());
michael@0:     JS_ASSERT(cx->isInsideCurrentCompartment(this));
michael@0: 
michael@0:     KidsPointer *kidp = &parent->kids;
michael@0: 
michael@0:     if (kidp->isNull()) {
michael@0:         child->setParent(parent);
michael@0:         kidp->setShape(child);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (kidp->isShape()) {
michael@0:         Shape *shape = kidp->toShape();
michael@0:         JS_ASSERT(shape != child);
michael@0:         JS_ASSERT(!shape->matches(child));
michael@0: 
michael@0:         KidsHash *hash = HashChildren(shape, child);
michael@0:         if (!hash) {
michael@0:             js_ReportOutOfMemory(cx);
michael@0:             return false;
michael@0:         }
michael@0:         kidp->setHash(hash);
michael@0:         child->setParent(parent);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (!kidp->toHash()->putNew(child, child)) {
michael@0:         js_ReportOutOfMemory(cx);
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     child->setParent(parent);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: Shape::removeChild(Shape *child)
michael@0: {
michael@0:     JS_ASSERT(!child->inDictionary());
michael@0:     JS_ASSERT(child->parent == this);
michael@0: 
michael@0:     KidsPointer *kidp = &kids;
michael@0: 
michael@0:     if (kidp->isShape()) {
michael@0:         JS_ASSERT(kidp->toShape() == child);
michael@0:         kidp->setNull();
michael@0:         child->parent = nullptr;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     KidsHash *hash = kidp->toHash();
michael@0:     JS_ASSERT(hash->count() >= 2);      /* otherwise kidp->isShape() should be true */
michael@0: 
michael@0:     hash->remove(child);
michael@0:     child->parent = nullptr;
michael@0: 
michael@0:     if (hash->count() == 1) {
michael@0:         /* Convert from HASH form back to SHAPE form. */
michael@0:         KidsHash::Range r = hash->all();
michael@0:         Shape *otherChild = r.front();
michael@0:         JS_ASSERT((r.popFront(), r.empty()));    /* No more elements! */
michael@0:         kidp->setShape(otherChild);
michael@0:         js_delete(hash);
michael@0:     }
michael@0: }
michael@0: 
michael@0: Shape *
michael@0: PropertyTree::getChild(ExclusiveContext *cx, Shape *parentArg, StackShape &unrootedChild)
michael@0: {
michael@0:     RootedShape parent(cx, parentArg);
michael@0:     JS_ASSERT(parent);
michael@0: 
michael@0:     Shape *existingShape = nullptr;
michael@0: 
michael@0:     /*
michael@0:      * The property tree has extremely low fan-out below its root in
michael@0:      * popular embeddings with real-world workloads. Patterns such as
michael@0:      * defining closures that capture a constructor's environment as
michael@0:      * getters or setters on the new object that is passed in as
michael@0:      * |this| can significantly increase fan-out below the property
michael@0:      * tree root -- see bug 335700 for details.
michael@0:      */
michael@0:     KidsPointer *kidp = &parent->kids;
michael@0:     if (kidp->isShape()) {
michael@0:         Shape *kid = kidp->toShape();
michael@0:         if (kid->matches(unrootedChild))
michael@0:         existingShape = kid;
michael@0:     } else if (kidp->isHash()) {
michael@0:         if (KidsHash::Ptr p = kidp->toHash()->lookup(unrootedChild))
michael@0:         existingShape = *p;
michael@0:     } else {
michael@0:         /* If kidp->isNull(), we always insert. */
michael@0:     }
michael@0: 
michael@0: #ifdef JSGC_INCREMENTAL
michael@0:     if (existingShape) {
michael@0:         JS::Zone *zone = existingShape->zone();
michael@0:         if (zone->needsBarrier()) {
michael@0:             /*
michael@0:              * We need a read barrier for the shape tree, since these are weak
michael@0:              * pointers.
michael@0:              */
michael@0:             Shape *tmp = existingShape;
michael@0:             MarkShapeUnbarriered(zone->barrierTracer(), &tmp, "read barrier");
michael@0:             JS_ASSERT(tmp == existingShape);
michael@0:         } else if (zone->isGCSweeping() && !existingShape->isMarked() &&
michael@0:                    !existingShape->arenaHeader()->allocatedDuringIncremental)
michael@0:         {
michael@0:             /*
michael@0:              * The shape we've found is unreachable and due to be finalized, so
michael@0:              * remove our weak reference to it and don't use it.
michael@0:              */
michael@0:             JS_ASSERT(parent->isMarked());
michael@0:             parent->removeChild(existingShape);
michael@0:             existingShape = nullptr;
michael@0:         }
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     if (existingShape)
michael@0:         return existingShape;
michael@0: 
michael@0:     RootedGeneric<StackShape*> child(cx, &unrootedChild);
michael@0: 
michael@0:     Shape *shape = newShape(cx);
michael@0:     if (!shape)
michael@0:         return nullptr;
michael@0: 
michael@0:     new (shape) Shape(*child, parent->numFixedSlots());
michael@0: 
michael@0:     if (!insertChild(cx, parent, shape))
michael@0:         return nullptr;
michael@0: 
michael@0:     return shape;
michael@0: }
michael@0: 
michael@0: Shape *
michael@0: PropertyTree::lookupChild(ThreadSafeContext *cx, Shape *parent, const StackShape &child)
michael@0: {
michael@0:     /* Keep this in sync with the logic of getChild above. */
michael@0:     Shape *shape = nullptr;
michael@0: 
michael@0:     JS_ASSERT(parent);
michael@0: 
michael@0:     KidsPointer *kidp = &parent->kids;
michael@0:     if (kidp->isShape()) {
michael@0:         Shape *kid = kidp->toShape();
michael@0:         if (kid->matches(child))
michael@0:             shape = kid;
michael@0:     } else if (kidp->isHash()) {
michael@0:         if (KidsHash::Ptr p = kidp->toHash()->readonlyThreadsafeLookup(child))
michael@0:             shape = *p;
michael@0:     } else {
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0: #if defined(JSGC_INCREMENTAL) && defined(DEBUG)
michael@0:     if (shape) {
michael@0:         JS::Zone *zone = shape->arenaHeader()->zone;
michael@0:         JS_ASSERT(!zone->needsBarrier());
michael@0:         JS_ASSERT(!(zone->isGCSweeping() && !shape->isMarked() &&
michael@0:                     !shape->arenaHeader()->allocatedDuringIncremental));
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     return shape;
michael@0: }
michael@0: 
michael@0: void
michael@0: Shape::sweep()
michael@0: {
michael@0:     if (inDictionary())
michael@0:         return;
michael@0: 
michael@0:     /*
michael@0:      * We detach the child from the parent if the parent is reachable.
michael@0:      *
michael@0:      * Note that due to incremental sweeping, the parent pointer may point
michael@0:      * to the original reachable parent, or it may point to a new live
michael@0:      * object allocated in the same cell that used to hold the parent.
michael@0:      *
michael@0:      * There are three cases:
michael@0:      *
michael@0:      * Case 1: parent is not marked - parent is unreachable, may have been
michael@0:      *         finalized, and the cell may subsequently have been
michael@0:      *         reallocated to a compartment that is not being marked (cells
michael@0:      *         are marked when allocated in a compartment that is currenly
michael@0:      *         being marked by the collector).
michael@0:      *
michael@0:      * Case 2: parent is marked and is in a different compartment - parent
michael@0:      *         has been freed and reallocated to compartment that was being
michael@0:      *         marked.
michael@0:      *
michael@0:      * Case 3: parent is marked and is in the same compartment - parent is
michael@0:      *         stil reachable and we need to detach from it.
michael@0:      */
michael@0:     if (parent && parent->isMarked() && parent->compartment() == compartment())
michael@0:         parent->removeChild(this);
michael@0: }
michael@0: 
michael@0: void
michael@0: Shape::finalize(FreeOp *fop)
michael@0: {
michael@0:     if (!inDictionary() && kids.isHash())
michael@0:         fop->delete_(kids.toHash());
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: 
michael@0: void
michael@0: KidsPointer::checkConsistency(Shape *aKid) const
michael@0: {
michael@0:     if (isShape()) {
michael@0:         JS_ASSERT(toShape() == aKid);
michael@0:     } else {
michael@0:         JS_ASSERT(isHash());
michael@0:         KidsHash *hash = toHash();
michael@0:         KidsHash::Ptr ptr = hash->lookup(aKid);
michael@0:         JS_ASSERT(*ptr == aKid);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: Shape::dump(JSContext *cx, FILE *fp) const
michael@0: {
michael@0:     /* This is only used from gdb, so allowing GC here would just be confusing. */
michael@0:     gc::AutoSuppressGC suppress(cx);
michael@0: 
michael@0:     jsid propid = this->propid();
michael@0: 
michael@0:     JS_ASSERT(!JSID_IS_VOID(propid));
michael@0: 
michael@0:     if (JSID_IS_INT(propid)) {
michael@0:         fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid));
michael@0:     } else {
michael@0:         JSLinearString *str;
michael@0:         if (JSID_IS_ATOM(propid)) {
michael@0:             str = JSID_TO_ATOM(propid);
michael@0:         } else {
michael@0:             JS_ASSERT(JSID_IS_OBJECT(propid));
michael@0:             Value v = IdToValue(propid);
michael@0:             JSString *s = ToStringSlow<NoGC>(cx, v);
michael@0:             fputs("object ", fp);
michael@0:             str = s ? s->ensureLinear(cx) : nullptr;
michael@0:         }
michael@0:         if (!str)
michael@0:             fputs("<error>", fp);
michael@0:         else
michael@0:             FileEscapedString(fp, str, '"');
michael@0:     }
michael@0: 
michael@0:     fprintf(fp, " g/s %p/%p slot %d attrs %x ",
michael@0:             JS_FUNC_TO_DATA_PTR(void *, base()->rawGetter),
michael@0:             JS_FUNC_TO_DATA_PTR(void *, base()->rawSetter),
michael@0:             hasSlot() ? slot() : -1, attrs);
michael@0: 
michael@0:     if (attrs) {
michael@0:         int first = 1;
michael@0:         fputs("(", fp);
michael@0: #define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(&(" " #display)[first], fp), first = 0
michael@0:         DUMP_ATTR(ENUMERATE, enumerate);
michael@0:         DUMP_ATTR(READONLY, readonly);
michael@0:         DUMP_ATTR(PERMANENT, permanent);
michael@0:         DUMP_ATTR(GETTER, getter);
michael@0:         DUMP_ATTR(SETTER, setter);
michael@0:         DUMP_ATTR(SHARED, shared);
michael@0: #undef  DUMP_ATTR
michael@0:         fputs(") ", fp);
michael@0:     }
michael@0: 
michael@0:     fprintf(fp, "flags %x ", flags);
michael@0:     if (flags) {
michael@0:         int first = 1;
michael@0:         fputs("(", fp);
michael@0: #define DUMP_FLAG(name, display) if (flags & name) fputs(&(" " #display)[first], fp), first = 0
michael@0:         DUMP_FLAG(IN_DICTIONARY, in_dictionary);
michael@0: #undef  DUMP_FLAG
michael@0:         fputs(") ", fp);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: Shape::dumpSubtree(JSContext *cx, int level, FILE *fp) const
michael@0: {
michael@0:     if (!parent) {
michael@0:         JS_ASSERT(level == 0);
michael@0:         JS_ASSERT(JSID_IS_EMPTY(propid_));
michael@0:         fprintf(fp, "class %s emptyShape\n", getObjectClass()->name);
michael@0:     } else {
michael@0:         fprintf(fp, "%*sid ", level, "");
michael@0:         dump(cx, fp);
michael@0:     }
michael@0: 
michael@0:     if (!kids.isNull()) {
michael@0:         ++level;
michael@0:         if (kids.isShape()) {
michael@0:             Shape *kid = kids.toShape();
michael@0:             JS_ASSERT(kid->parent == this);
michael@0:             kid->dumpSubtree(cx, level, fp);
michael@0:         } else {
michael@0:             const KidsHash &hash = *kids.toHash();
michael@0:             for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) {
michael@0:                 Shape *kid = range.front();
michael@0: 
michael@0:                 JS_ASSERT(kid->parent == this);
michael@0:                 kid->dumpSubtree(cx, level, fp);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: #endif