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