js/src/jspropertytree.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sts=4 et sw=4 tw=99:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "jspropertytree.h"
   8
   9 #include "mozilla/DebugOnly.h"
  10
  11 #include "jscntxt.h"
  12 #include "jsgc.h"
  13 #include "jstypes.h"
  14
  15 #include "vm/Shape.h"
  16
  17 #include "jsgcinlines.h"
  18
  19 #include "vm/Shape-inl.h"
  20
  21 using namespace js;
  22 using namespace js::gc;
  23
  24 using mozilla::DebugOnly;
  25
  26 inline HashNumber
  27 ShapeHasher::hash(const Lookup& l)
  28 {
  29     return l.hash();
  30 }
  31
  32 inline bool
  33 ShapeHasher::match(const Key k, const Lookup& l)
  34 {
  35     return k->matches(l);
  36 }
  37
  38 static KidsHash*
  39 HashChildren(Shape* kid1, Shape* kid2)
  40 {
  41     KidsHash* hash = js_new<KidsHash>();
  42     if (!hash || !hash->init(2)) {
  43         js_delete(hash);
  44         return nullptr;
  45     }
  46
  47     JS_ALWAYS_TRUE(hash->putNew(StackShape(kid1), kid1));
  48     JS_ALWAYS_TRUE(hash->putNew(StackShape(kid2), kid2));
  49     return hash;
  50 }
  51
  52 bool
  53 PropertyTree::insertChild(ExclusiveContext* cx, Shape* parent, Shape* child)
  54 {
  55     MOZ_ASSERT(!parent->inDictionary());
  56     MOZ_ASSERT(!child->parent);
  57     MOZ_ASSERT(!child->inDictionary());
  58     MOZ_ASSERT(child->compartment() == parent->compartment());
  59     MOZ_ASSERT(cx->isInsideCurrentCompartment(this));
  60
  61     KidsPointer* kidp = &parent->kids;
  62
  63     if (kidp->isNull()) {
  64         child->setParent(parent);
  65         kidp->setShape(child);
  66         return true;
  67     }
  68
  69     if (kidp->isShape()) {
  70         Shape* shape = kidp->toShape();
  71         MOZ_ASSERT(shape != child);
  72         MOZ_ASSERT(!shape->matches(child));
  73
  74         KidsHash* hash = HashChildren(shape, child);
  75         if (!hash) {
  76             js_ReportOutOfMemory(cx);
  77             return false;
  78         }
  79         kidp->setHash(hash);
  80         child->setParent(parent);
  81         return true;
  82     }
  83
  84     if (!kidp->toHash()->putNew(StackShape(child), child)) {
  85         js_ReportOutOfMemory(cx);
  86         return false;
  87     }
  88
  89     child->setParent(parent);
  90     return true;
  91 }
  92
  93 void
  94 Shape::removeChild(Shape* child)
  95 {
  96     MOZ_ASSERT(!child->inDictionary());
  97     MOZ_ASSERT(child->parent == this);
  98
  99     KidsPointer* kidp = &kids;
 100
 101     if (kidp->isShape()) {
 102         MOZ_ASSERT(kidp->toShape() == child);
 103         kidp->setNull();
 104         child->parent = nullptr;
 105         return;
 106     }
 107
 108     KidsHash* hash = kidp->toHash();
 109     MOZ_ASSERT(hash->count() >= 2);      /* otherwise kidp->isShape() should be true */
 110
 111 #ifdef DEBUG
 112     size_t oldCount = hash->count();
 113 #endif
 114
 115     hash->remove(StackShape(child));
 116     child->parent = nullptr;
 117
 118     MOZ_ASSERT(hash->count() == oldCount - 1);
 119
 120     if (hash->count() == 1) {
 121         /* Convert from HASH form back to SHAPE form. */
 122         KidsHash::Range r = hash->all();
 123         Shape* otherChild = r.front();
 124         MOZ_ASSERT((r.popFront(), r.empty()));    /* No more elements! */
 125         kidp->setShape(otherChild);
 126         js_delete(hash);
 127     }
 128 }
 129
 130 Shape*
 131 PropertyTree::getChild(ExclusiveContext* cx, Shape* parentArg, StackShape& unrootedChild)
 132 {
 133     RootedShape parent(cx, parentArg);
 134     MOZ_ASSERT(parent);
 135
 136     Shape* existingShape = nullptr;
 137
 138     /*
 139      * The property tree has extremely low fan-out below its root in
 140      * popular embeddings with real-world workloads. Patterns such as
 141      * defining closures that capture a constructor's environment as
 142      * getters or setters on the new object that is passed in as
 143      * |this| can significantly increase fan-out below the property
 144      * tree root -- see bug 335700 for details.
 145      */
 146     KidsPointer* kidp = &parent->kids;
 147     if (kidp->isShape()) {
 148         Shape* kid = kidp->toShape();
 149         if (kid->matches(unrootedChild))
 150             existingShape = kid;
 151     } else if (kidp->isHash()) {
 152         if (KidsHash::Ptr p = kidp->toHash()->lookup(unrootedChild))
 153             existingShape = *p;
 154     } else {
 155         /* If kidp->isNull(), we always insert. */
 156     }
 157
 158     if (existingShape) {
 159         JS::Zone* zone = existingShape->zone();
 160         if (zone->needsIncrementalBarrier()) {
 161             /*
 162              * We need a read barrier for the shape tree, since these are weak
 163              * pointers.
 164              */
 165             Shape* tmp = existingShape;
 166             MarkShapeUnbarriered(zone->barrierTracer(), &tmp, "read barrier");
 167             MOZ_ASSERT(tmp == existingShape);
 168         } else if (zone->isGCSweeping() && !existingShape->isMarked() &&
 169                    !existingShape->arenaHeader()->allocatedDuringIncremental)
 170         {
 171             /*
 172              * The shape we've found is unreachable and due to be finalized, so
 173              * remove our weak reference to it and don't use it.
 174              */
 175             MOZ_ASSERT(parent->isMarked());
 176             parent->removeChild(existingShape);
 177             existingShape = nullptr;
 178         } else if (existingShape->isMarked(gc::GRAY)) {
 179             UnmarkGrayShapeRecursively(existingShape);
 180         }
 181     }
 182
 183     if (existingShape)
 184         return existingShape;
 185
 186     Shape* shape = Shape::new_(cx, unrootedChild, parent->numFixedSlots());
 187     if (!shape)
 188         return nullptr;
 189
 190     if (!insertChild(cx, parent, shape))
 191         return nullptr;
 192
 193     return shape;
 194 }
 195
 196 void
 197 Shape::sweep()
 198 {
 199     if (inDictionary())
 200         return;
 201
 202     /*
 203      * We detach the child from the parent if the parent is reachable.
 204      *
 205      * Note that due to incremental sweeping, the parent pointer may point
 206      * to the original reachable parent, or it may point to a new live
 207      * object allocated in the same cell that used to hold the parent.
 208      *
 209      * There are three cases:
 210      *
 211      * Case 1: parent is not marked - parent is unreachable, may have been
 212      *         finalized, and the cell may subsequently have been
 213      *         reallocated to a compartment that is not being marked (cells
 214      *         are marked when allocated in a compartment that is currenly
 215      *         being marked by the collector).
 216      *
 217      * Case 2: parent is marked and is in a different compartment - parent
 218      *         has been freed and reallocated to compartment that was being
 219      *         marked.
 220      *
 221      * Case 3: parent is marked and is in the same compartment - parent is
 222      *         stil reachable and we need to detach from it.
 223      */
 224     if (parent && parent->isMarked() && parent->compartment() == compartment())
 225         parent->removeChild(this);
 226 }
 227
 228 void
 229 Shape::finalize(FreeOp* fop)
 230 {
 231     if (!inDictionary() && kids.isHash())
 232         fop->delete_(kids.toHash());
 233 }
 234
 235 #ifdef JSGC_COMPACTING
 236
 237 void
 238 Shape::fixupDictionaryShapeAfterMovingGC()
 239 {
 240     if (!listp)
 241         return;
 242
 243     // It's possible that this shape is unreachable and that listp points to the
 244     // location of a dead object in the nursery, in which case we should never
 245     // touch it again.
 246     if (IsInsideNursery(reinterpret_cast<Cell*>(listp))) {
 247         listp = nullptr;
 248         return;
 249     }
 250
 251     MOZ_ASSERT(!IsInsideNursery(reinterpret_cast<Cell*>(listp)));
 252     AllocKind kind = TenuredCell::fromPointer(listp)->getAllocKind();
 253     MOZ_ASSERT(kind == FINALIZE_SHAPE ||
 254                kind == FINALIZE_ACCESSOR_SHAPE ||
 255                kind <= FINALIZE_OBJECT_LAST);
 256     if (kind == FINALIZE_SHAPE || kind == FINALIZE_ACCESSOR_SHAPE) {
 257         // listp points to the parent field of the next shape.
 258         Shape* next = reinterpret_cast<Shape*>(uintptr_t(listp) -
 259                                                 offsetof(Shape, parent));
 260         listp = &gc::MaybeForwarded(next)->parent;
 261     } else {
 262         // listp points to the shape_ field of an object.
 263         JSObject* last = reinterpret_cast<JSObject*>(uintptr_t(listp) -
 264                                                       offsetof(JSObject, shape_));
 265         listp = &gc::MaybeForwarded(last)->shape_;
 266     }
 267 }
 268
 269 void
 270 Shape::fixupShapeTreeAfterMovingGC()
 271 {
 272     if (kids.isNull())
 273         return;
 274
 275     if (kids.isShape()) {
 276         if (gc::IsForwarded(kids.toShape()))
 277             kids.setShape(gc::Forwarded(kids.toShape()));
 278         return;
 279     }
 280
 281     MOZ_ASSERT(kids.isHash());
 282     KidsHash* kh = kids.toHash();
 283     for (KidsHash::Enum e(*kh); !e.empty(); e.popFront()) {
 284         Shape* key = e.front();
 285         if (IsForwarded(key))
 286             key = Forwarded(key);
 287
 288         BaseShape* base = key->base();
 289         if (IsForwarded(base))
 290             base = Forwarded(base);
 291         UnownedBaseShape* unowned = base->unowned();
 292         if (IsForwarded(unowned))
 293             unowned = Forwarded(unowned);
 294
 295         PropertyOp getter = key->getter();
 296         if (key->hasGetterObject())
 297             getter = PropertyOp(MaybeForwarded(key->getterObject()));
 298
 299         StrictPropertyOp setter = key->setter();
 300         if (key->hasSetterObject())
 301             setter = StrictPropertyOp(MaybeForwarded(key->setterObject()));
 302
 303         StackShape lookup(unowned,
 304                           const_cast<Shape*>(key)->propidRef(),
 305                           key->slotInfo & Shape::SLOT_MASK,
 306                           key->attrs,
 307                           key->flags);
 308         lookup.updateGetterSetter(getter, setter);
 309         e.rekeyFront(lookup, key);
 310     }
 311 }
 312
 313 void
 314 Shape::fixupAfterMovingGC()
 315 {
 316     if (inDictionary())
 317         fixupDictionaryShapeAfterMovingGC();
 318     else
 319         fixupShapeTreeAfterMovingGC();
 320 }
 321
 322 #endif // JSGC_COMPACTING
 323
 324 void
 325 ShapeGetterSetterRef::mark(JSTracer* trc)
 326 {
 327     // Update the current shape's entry in the parent KidsHash table if needed.
 328     // This is necessary as the computed hash includes the getter/setter
 329     // pointers.
 330
 331     JSObject* obj = *objp;
 332     JSObject* prior = obj;
 333     if (!prior)
 334         return;
 335
 336     trc->setTracingLocation(&*prior);
 337     gc::Mark(trc, &obj, "AccessorShape getter or setter");
 338     if (obj == *objp)
 339         return;
 340
 341     Shape* parent = shape->parent;
 342     if (shape->inDictionary() || !parent->kids.isHash()) {
 343         *objp = obj;
 344         return;
 345     }
 346
 347     KidsHash* kh = parent->kids.toHash();
 348     kh->remove(StackShape(shape));
 349     *objp = obj;
 350     MOZ_ALWAYS_TRUE(kh->putNew(StackShape(shape), shape));
 351 }
 352
 353 #ifdef DEBUG
 354
 355 void
 356 KidsPointer::checkConsistency(Shape* aKid) const
 357 {
 358     if (isShape()) {
 359         MOZ_ASSERT(toShape() == aKid);
 360     } else {
 361         MOZ_ASSERT(isHash());
 362         KidsHash* hash = toHash();
 363         KidsHash::Ptr ptr = hash->lookup(StackShape(aKid));
 364         MOZ_ASSERT(*ptr == aKid);
 365     }
 366 }
 367
 368 void
 369 Shape::dump(JSContext* cx, FILE* fp) const
 370 {
 371     /* This is only used from gdb, so allowing GC here would just be confusing. */
 372     gc::AutoSuppressGC suppress(cx);
 373
 374     jsid propid = this->propid();
 375
 376     MOZ_ASSERT(!JSID_IS_VOID(propid));
 377
 378     if (JSID_IS_INT(propid)) {
 379         fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid));
 380     } else if (JSID_IS_ATOM(propid)) {
 381         if (JSLinearString* str = JSID_TO_ATOM(propid))
 382             FileEscapedString(fp, str, '"');
 383         else
 384             fputs("<error>", fp);
 385     } else {
 386         MOZ_ASSERT(JSID_IS_SYMBOL(propid));
 387         JSID_TO_SYMBOL(propid)->dump(fp);
 388     }
 389
 390     fprintf(fp, " g/s %p/%p slot %d attrs %x ",
 391             JS_FUNC_TO_DATA_PTR(void*, getter()),
 392             JS_FUNC_TO_DATA_PTR(void*, setter()),
 393             hasSlot() ? slot() : -1, attrs);
 394
 395     if (attrs) {
 396         int first = 1;
 397         fputs("(", fp);
 398 #define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(&(" " #display)[first], fp), first = 0
 399         DUMP_ATTR(ENUMERATE, enumerate);
 400         DUMP_ATTR(READONLY, readonly);
 401         DUMP_ATTR(PERMANENT, permanent);
 402         DUMP_ATTR(GETTER, getter);
 403         DUMP_ATTR(SETTER, setter);
 404         DUMP_ATTR(SHARED, shared);
 405 #undef  DUMP_ATTR
 406         fputs(") ", fp);
 407     }
 408
 409     fprintf(fp, "flags %x ", flags);
 410     if (flags) {
 411         int first = 1;
 412         fputs("(", fp);
 413 #define DUMP_FLAG(name, display) if (flags & name) fputs(&(" " #display)[first], fp), first = 0
 414         DUMP_FLAG(IN_DICTIONARY, in_dictionary);
 415 #undef  DUMP_FLAG
 416         fputs(") ", fp);
 417     }
 418 }
 419
 420 void
 421 Shape::dumpSubtree(JSContext* cx, int level, FILE* fp) const
 422 {
 423     if (!parent) {
 424         MOZ_ASSERT(level == 0);
 425         MOZ_ASSERT(JSID_IS_EMPTY(propid_));
 426         fprintf(fp, "class %s emptyShape\n", getObjectClass()->name);
 427     } else {
 428         fprintf(fp, "%*sid ", level, "");
 429         dump(cx, fp);
 430     }
 431
 432     if (!kids.isNull()) {
 433         ++level;
 434         if (kids.isShape()) {
 435             Shape* kid = kids.toShape();
 436             MOZ_ASSERT(kid->parent == this);
 437             kid->dumpSubtree(cx, level, fp);
 438         } else {
 439             const KidsHash& hash = *kids.toHash();
 440             for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) {
 441                 Shape* kid = range.front();
 442
 443                 MOZ_ASSERT(kid->parent == this);
 444                 kid->dumpSubtree(cx, level, fp);
 445             }
 446         }
 447     }
 448 }
 449
 450 #endif