1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jspropertytree.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,373 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jspropertytree.h"
1.11 +
1.12 +#include "jscntxt.h"
1.13 +#include "jsgc.h"
1.14 +#include "jstypes.h"
1.15 +
1.16 +#include "vm/Shape.h"
1.17 +
1.18 +#include "jsgcinlines.h"
1.19 +
1.20 +#include "vm/Shape-inl.h"
1.21 +
1.22 +using namespace js;
1.23 +
1.24 +inline HashNumber
1.25 +ShapeHasher::hash(const Lookup &l)
1.26 +{
1.27 + return l.hash();
1.28 +}
1.29 +
1.30 +inline bool
1.31 +ShapeHasher::match(const Key k, const Lookup &l)
1.32 +{
1.33 + return k->matches(l);
1.34 +}
1.35 +
1.36 +Shape *
1.37 +PropertyTree::newShape(ExclusiveContext *cx)
1.38 +{
1.39 + Shape *shape = js_NewGCShape(cx);
1.40 + if (!shape)
1.41 + js_ReportOutOfMemory(cx);
1.42 + return shape;
1.43 +}
1.44 +
1.45 +static KidsHash *
1.46 +HashChildren(Shape *kid1, Shape *kid2)
1.47 +{
1.48 + KidsHash *hash = js_new<KidsHash>();
1.49 + if (!hash || !hash->init(2)) {
1.50 + js_delete(hash);
1.51 + return nullptr;
1.52 + }
1.53 +
1.54 + JS_ALWAYS_TRUE(hash->putNew(kid1, kid1));
1.55 + JS_ALWAYS_TRUE(hash->putNew(kid2, kid2));
1.56 + return hash;
1.57 +}
1.58 +
1.59 +bool
1.60 +PropertyTree::insertChild(ExclusiveContext *cx, Shape *parent, Shape *child)
1.61 +{
1.62 + JS_ASSERT(!parent->inDictionary());
1.63 + JS_ASSERT(!child->parent);
1.64 + JS_ASSERT(!child->inDictionary());
1.65 + JS_ASSERT(child->compartment() == parent->compartment());
1.66 + JS_ASSERT(cx->isInsideCurrentCompartment(this));
1.67 +
1.68 + KidsPointer *kidp = &parent->kids;
1.69 +
1.70 + if (kidp->isNull()) {
1.71 + child->setParent(parent);
1.72 + kidp->setShape(child);
1.73 + return true;
1.74 + }
1.75 +
1.76 + if (kidp->isShape()) {
1.77 + Shape *shape = kidp->toShape();
1.78 + JS_ASSERT(shape != child);
1.79 + JS_ASSERT(!shape->matches(child));
1.80 +
1.81 + KidsHash *hash = HashChildren(shape, child);
1.82 + if (!hash) {
1.83 + js_ReportOutOfMemory(cx);
1.84 + return false;
1.85 + }
1.86 + kidp->setHash(hash);
1.87 + child->setParent(parent);
1.88 + return true;
1.89 + }
1.90 +
1.91 + if (!kidp->toHash()->putNew(child, child)) {
1.92 + js_ReportOutOfMemory(cx);
1.93 + return false;
1.94 + }
1.95 +
1.96 + child->setParent(parent);
1.97 + return true;
1.98 +}
1.99 +
1.100 +void
1.101 +Shape::removeChild(Shape *child)
1.102 +{
1.103 + JS_ASSERT(!child->inDictionary());
1.104 + JS_ASSERT(child->parent == this);
1.105 +
1.106 + KidsPointer *kidp = &kids;
1.107 +
1.108 + if (kidp->isShape()) {
1.109 + JS_ASSERT(kidp->toShape() == child);
1.110 + kidp->setNull();
1.111 + child->parent = nullptr;
1.112 + return;
1.113 + }
1.114 +
1.115 + KidsHash *hash = kidp->toHash();
1.116 + JS_ASSERT(hash->count() >= 2); /* otherwise kidp->isShape() should be true */
1.117 +
1.118 + hash->remove(child);
1.119 + child->parent = nullptr;
1.120 +
1.121 + if (hash->count() == 1) {
1.122 + /* Convert from HASH form back to SHAPE form. */
1.123 + KidsHash::Range r = hash->all();
1.124 + Shape *otherChild = r.front();
1.125 + JS_ASSERT((r.popFront(), r.empty())); /* No more elements! */
1.126 + kidp->setShape(otherChild);
1.127 + js_delete(hash);
1.128 + }
1.129 +}
1.130 +
1.131 +Shape *
1.132 +PropertyTree::getChild(ExclusiveContext *cx, Shape *parentArg, StackShape &unrootedChild)
1.133 +{
1.134 + RootedShape parent(cx, parentArg);
1.135 + JS_ASSERT(parent);
1.136 +
1.137 + Shape *existingShape = nullptr;
1.138 +
1.139 + /*
1.140 + * The property tree has extremely low fan-out below its root in
1.141 + * popular embeddings with real-world workloads. Patterns such as
1.142 + * defining closures that capture a constructor's environment as
1.143 + * getters or setters on the new object that is passed in as
1.144 + * |this| can significantly increase fan-out below the property
1.145 + * tree root -- see bug 335700 for details.
1.146 + */
1.147 + KidsPointer *kidp = &parent->kids;
1.148 + if (kidp->isShape()) {
1.149 + Shape *kid = kidp->toShape();
1.150 + if (kid->matches(unrootedChild))
1.151 + existingShape = kid;
1.152 + } else if (kidp->isHash()) {
1.153 + if (KidsHash::Ptr p = kidp->toHash()->lookup(unrootedChild))
1.154 + existingShape = *p;
1.155 + } else {
1.156 + /* If kidp->isNull(), we always insert. */
1.157 + }
1.158 +
1.159 +#ifdef JSGC_INCREMENTAL
1.160 + if (existingShape) {
1.161 + JS::Zone *zone = existingShape->zone();
1.162 + if (zone->needsBarrier()) {
1.163 + /*
1.164 + * We need a read barrier for the shape tree, since these are weak
1.165 + * pointers.
1.166 + */
1.167 + Shape *tmp = existingShape;
1.168 + MarkShapeUnbarriered(zone->barrierTracer(), &tmp, "read barrier");
1.169 + JS_ASSERT(tmp == existingShape);
1.170 + } else if (zone->isGCSweeping() && !existingShape->isMarked() &&
1.171 + !existingShape->arenaHeader()->allocatedDuringIncremental)
1.172 + {
1.173 + /*
1.174 + * The shape we've found is unreachable and due to be finalized, so
1.175 + * remove our weak reference to it and don't use it.
1.176 + */
1.177 + JS_ASSERT(parent->isMarked());
1.178 + parent->removeChild(existingShape);
1.179 + existingShape = nullptr;
1.180 + }
1.181 + }
1.182 +#endif
1.183 +
1.184 + if (existingShape)
1.185 + return existingShape;
1.186 +
1.187 + RootedGeneric<StackShape*> child(cx, &unrootedChild);
1.188 +
1.189 + Shape *shape = newShape(cx);
1.190 + if (!shape)
1.191 + return nullptr;
1.192 +
1.193 + new (shape) Shape(*child, parent->numFixedSlots());
1.194 +
1.195 + if (!insertChild(cx, parent, shape))
1.196 + return nullptr;
1.197 +
1.198 + return shape;
1.199 +}
1.200 +
1.201 +Shape *
1.202 +PropertyTree::lookupChild(ThreadSafeContext *cx, Shape *parent, const StackShape &child)
1.203 +{
1.204 + /* Keep this in sync with the logic of getChild above. */
1.205 + Shape *shape = nullptr;
1.206 +
1.207 + JS_ASSERT(parent);
1.208 +
1.209 + KidsPointer *kidp = &parent->kids;
1.210 + if (kidp->isShape()) {
1.211 + Shape *kid = kidp->toShape();
1.212 + if (kid->matches(child))
1.213 + shape = kid;
1.214 + } else if (kidp->isHash()) {
1.215 + if (KidsHash::Ptr p = kidp->toHash()->readonlyThreadsafeLookup(child))
1.216 + shape = *p;
1.217 + } else {
1.218 + return nullptr;
1.219 + }
1.220 +
1.221 +#if defined(JSGC_INCREMENTAL) && defined(DEBUG)
1.222 + if (shape) {
1.223 + JS::Zone *zone = shape->arenaHeader()->zone;
1.224 + JS_ASSERT(!zone->needsBarrier());
1.225 + JS_ASSERT(!(zone->isGCSweeping() && !shape->isMarked() &&
1.226 + !shape->arenaHeader()->allocatedDuringIncremental));
1.227 + }
1.228 +#endif
1.229 +
1.230 + return shape;
1.231 +}
1.232 +
1.233 +void
1.234 +Shape::sweep()
1.235 +{
1.236 + if (inDictionary())
1.237 + return;
1.238 +
1.239 + /*
1.240 + * We detach the child from the parent if the parent is reachable.
1.241 + *
1.242 + * Note that due to incremental sweeping, the parent pointer may point
1.243 + * to the original reachable parent, or it may point to a new live
1.244 + * object allocated in the same cell that used to hold the parent.
1.245 + *
1.246 + * There are three cases:
1.247 + *
1.248 + * Case 1: parent is not marked - parent is unreachable, may have been
1.249 + * finalized, and the cell may subsequently have been
1.250 + * reallocated to a compartment that is not being marked (cells
1.251 + * are marked when allocated in a compartment that is currenly
1.252 + * being marked by the collector).
1.253 + *
1.254 + * Case 2: parent is marked and is in a different compartment - parent
1.255 + * has been freed and reallocated to compartment that was being
1.256 + * marked.
1.257 + *
1.258 + * Case 3: parent is marked and is in the same compartment - parent is
1.259 + * stil reachable and we need to detach from it.
1.260 + */
1.261 + if (parent && parent->isMarked() && parent->compartment() == compartment())
1.262 + parent->removeChild(this);
1.263 +}
1.264 +
1.265 +void
1.266 +Shape::finalize(FreeOp *fop)
1.267 +{
1.268 + if (!inDictionary() && kids.isHash())
1.269 + fop->delete_(kids.toHash());
1.270 +}
1.271 +
1.272 +#ifdef DEBUG
1.273 +
1.274 +void
1.275 +KidsPointer::checkConsistency(Shape *aKid) const
1.276 +{
1.277 + if (isShape()) {
1.278 + JS_ASSERT(toShape() == aKid);
1.279 + } else {
1.280 + JS_ASSERT(isHash());
1.281 + KidsHash *hash = toHash();
1.282 + KidsHash::Ptr ptr = hash->lookup(aKid);
1.283 + JS_ASSERT(*ptr == aKid);
1.284 + }
1.285 +}
1.286 +
1.287 +void
1.288 +Shape::dump(JSContext *cx, FILE *fp) const
1.289 +{
1.290 + /* This is only used from gdb, so allowing GC here would just be confusing. */
1.291 + gc::AutoSuppressGC suppress(cx);
1.292 +
1.293 + jsid propid = this->propid();
1.294 +
1.295 + JS_ASSERT(!JSID_IS_VOID(propid));
1.296 +
1.297 + if (JSID_IS_INT(propid)) {
1.298 + fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid));
1.299 + } else {
1.300 + JSLinearString *str;
1.301 + if (JSID_IS_ATOM(propid)) {
1.302 + str = JSID_TO_ATOM(propid);
1.303 + } else {
1.304 + JS_ASSERT(JSID_IS_OBJECT(propid));
1.305 + Value v = IdToValue(propid);
1.306 + JSString *s = ToStringSlow<NoGC>(cx, v);
1.307 + fputs("object ", fp);
1.308 + str = s ? s->ensureLinear(cx) : nullptr;
1.309 + }
1.310 + if (!str)
1.311 + fputs("<error>", fp);
1.312 + else
1.313 + FileEscapedString(fp, str, '"');
1.314 + }
1.315 +
1.316 + fprintf(fp, " g/s %p/%p slot %d attrs %x ",
1.317 + JS_FUNC_TO_DATA_PTR(void *, base()->rawGetter),
1.318 + JS_FUNC_TO_DATA_PTR(void *, base()->rawSetter),
1.319 + hasSlot() ? slot() : -1, attrs);
1.320 +
1.321 + if (attrs) {
1.322 + int first = 1;
1.323 + fputs("(", fp);
1.324 +#define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(&(" " #display)[first], fp), first = 0
1.325 + DUMP_ATTR(ENUMERATE, enumerate);
1.326 + DUMP_ATTR(READONLY, readonly);
1.327 + DUMP_ATTR(PERMANENT, permanent);
1.328 + DUMP_ATTR(GETTER, getter);
1.329 + DUMP_ATTR(SETTER, setter);
1.330 + DUMP_ATTR(SHARED, shared);
1.331 +#undef DUMP_ATTR
1.332 + fputs(") ", fp);
1.333 + }
1.334 +
1.335 + fprintf(fp, "flags %x ", flags);
1.336 + if (flags) {
1.337 + int first = 1;
1.338 + fputs("(", fp);
1.339 +#define DUMP_FLAG(name, display) if (flags & name) fputs(&(" " #display)[first], fp), first = 0
1.340 + DUMP_FLAG(IN_DICTIONARY, in_dictionary);
1.341 +#undef DUMP_FLAG
1.342 + fputs(") ", fp);
1.343 + }
1.344 +}
1.345 +
1.346 +void
1.347 +Shape::dumpSubtree(JSContext *cx, int level, FILE *fp) const
1.348 +{
1.349 + if (!parent) {
1.350 + JS_ASSERT(level == 0);
1.351 + JS_ASSERT(JSID_IS_EMPTY(propid_));
1.352 + fprintf(fp, "class %s emptyShape\n", getObjectClass()->name);
1.353 + } else {
1.354 + fprintf(fp, "%*sid ", level, "");
1.355 + dump(cx, fp);
1.356 + }
1.357 +
1.358 + if (!kids.isNull()) {
1.359 + ++level;
1.360 + if (kids.isShape()) {
1.361 + Shape *kid = kids.toShape();
1.362 + JS_ASSERT(kid->parent == this);
1.363 + kid->dumpSubtree(cx, level, fp);
1.364 + } else {
1.365 + const KidsHash &hash = *kids.toHash();
1.366 + for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) {
1.367 + Shape *kid = range.front();
1.368 +
1.369 + JS_ASSERT(kid->parent == this);
1.370 + kid->dumpSubtree(cx, level, fp);
1.371 + }
1.372 + }
1.373 + }
1.374 +}
1.375 +
1.376 +#endif
