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/NativeObject-inl.h"
18 #include "vm/Shape-inl.h"
19
20 using namespace js;
21 using namespace js::gc;
22
23 using mozilla::DebugOnly;
24
25 inline HashNumber
hash(const Lookup & l)26 ShapeHasher::hash(const Lookup& l)
27 {
28 return l.hash();
29 }
30
31 inline bool
match(const Key k,const Lookup & l)32 ShapeHasher::match(const Key k, const Lookup& l)
33 {
34 return k->matches(l);
35 }
36
37 static KidsHash*
HashChildren(Shape * kid1,Shape * kid2)38 HashChildren(Shape* kid1, Shape* kid2)
39 {
40 KidsHash* hash = js_new<KidsHash>();
41 if (!hash || !hash->init(2)) {
42 js_delete(hash);
43 return nullptr;
44 }
45
46 hash->putNewInfallible(StackShape(kid1), kid1);
47 hash->putNewInfallible(StackShape(kid2), kid2);
48 return hash;
49 }
50
51 bool
insertChild(ExclusiveContext * cx,Shape * parent,Shape * child)52 PropertyTree::insertChild(ExclusiveContext* cx, Shape* parent, Shape* child)
53 {
54 MOZ_ASSERT(!parent->inDictionary());
55 MOZ_ASSERT(!child->parent);
56 MOZ_ASSERT(!child->inDictionary());
57 MOZ_ASSERT(child->zone() == parent->zone());
58 MOZ_ASSERT(cx->zone() == zone_);
59
60 KidsPointer* kidp = &parent->kids;
61
62 if (kidp->isNull()) {
63 child->setParent(parent);
64 kidp->setShape(child);
65 return true;
66 }
67
68 if (kidp->isShape()) {
69 Shape* shape = kidp->toShape();
70 MOZ_ASSERT(shape != child);
71 MOZ_ASSERT(!shape->matches(child));
72
73 KidsHash* hash = HashChildren(shape, child);
74 if (!hash) {
75 ReportOutOfMemory(cx);
76 return false;
77 }
78 kidp->setHash(hash);
79 child->setParent(parent);
80 return true;
81 }
82
83 if (!kidp->toHash()->putNew(StackShape(child), child)) {
84 ReportOutOfMemory(cx);
85 return false;
86 }
87
88 child->setParent(parent);
89 return true;
90 }
91
92 void
removeChild(Shape * child)93 Shape::removeChild(Shape* child)
94 {
95 MOZ_ASSERT(!child->inDictionary());
96 MOZ_ASSERT(child->parent == this);
97
98 KidsPointer* kidp = &kids;
99
100 if (kidp->isShape()) {
101 MOZ_ASSERT(kidp->toShape() == child);
102 kidp->setNull();
103 child->parent = nullptr;
104 return;
105 }
106
107 KidsHash* hash = kidp->toHash();
108 MOZ_ASSERT(hash->count() >= 2); /* otherwise kidp->isShape() should be true */
109
110 #ifdef DEBUG
111 size_t oldCount = hash->count();
112 #endif
113
114 hash->remove(StackShape(child));
115 child->parent = nullptr;
116
117 MOZ_ASSERT(hash->count() == oldCount - 1);
118
119 if (hash->count() == 1) {
120 /* Convert from HASH form back to SHAPE form. */
121 KidsHash::Range r = hash->all();
122 Shape* otherChild = r.front();
123 MOZ_ASSERT((r.popFront(), r.empty())); /* No more elements! */
124 kidp->setShape(otherChild);
125 js_delete(hash);
126 }
127 }
128
129 Shape*
getChild(ExclusiveContext * cx,Shape * parentArg,Handle<StackShape> child)130 PropertyTree::getChild(ExclusiveContext* cx, Shape* parentArg, Handle<StackShape> child)
131 {
132 RootedShape parent(cx, parentArg);
133 MOZ_ASSERT(parent);
134
135 Shape* existingShape = nullptr;
136
137 /*
138 * The property tree has extremely low fan-out below its root in
139 * popular embeddings with real-world workloads. Patterns such as
140 * defining closures that capture a constructor's environment as
141 * getters or setters on the new object that is passed in as
142 * |this| can significantly increase fan-out below the property
143 * tree root -- see bug 335700 for details.
144 */
145 KidsPointer* kidp = &parent->kids;
146 if (kidp->isShape()) {
147 Shape* kid = kidp->toShape();
148 if (kid->matches(child))
149 existingShape = kid;
150 } else if (kidp->isHash()) {
151 if (KidsHash::Ptr p = kidp->toHash()->lookup(child))
152 existingShape = *p;
153 } else {
154 /* If kidp->isNull(), we always insert. */
155 }
156
157 if (existingShape) {
158 JS::Zone* zone = existingShape->zone();
159 if (zone->needsIncrementalBarrier()) {
160 /*
161 * We need a read barrier for the shape tree, since these are weak
162 * pointers.
163 */
164 Shape* tmp = existingShape;
165 TraceManuallyBarrieredEdge(zone->barrierTracer(), &tmp, "read barrier");
166 MOZ_ASSERT(tmp == existingShape);
167 } else if (zone->isGCSweeping() && !existingShape->isMarked() &&
168 !existingShape->arena()->allocatedDuringIncremental)
169 {
170 /*
171 * The shape we've found is unreachable and due to be finalized, so
172 * remove our weak reference to it and don't use it.
173 */
174 MOZ_ASSERT(parent->isMarked());
175 parent->removeChild(existingShape);
176 existingShape = nullptr;
177 } else if (existingShape->isMarked(gc::GRAY)) {
178 UnmarkGrayShapeRecursively(existingShape);
179 }
180 }
181
182 if (existingShape)
183 return existingShape;
184
185 Shape* shape = Shape::new_(cx, child, parent->numFixedSlots());
186 if (!shape)
187 return nullptr;
188
189 if (!insertChild(cx, parent, shape))
190 return nullptr;
191
192 return shape;
193 }
194
195 void
sweep()196 Shape::sweep()
197 {
198 /*
199 * We detach the child from the parent if the parent is reachable.
200 *
201 * This test depends on shape arenas not being freed until after we finish
202 * incrementally sweeping them. If that were not the case the parent pointer
203 * could point to a marked cell that had been deallocated and then
204 * reallocated, since allocating a cell in a zone that is being marked will
205 * set the mark bit for that cell.
206 */
207 if (parent && parent->isMarked()) {
208 if (inDictionary()) {
209 if (parent->listp == &parent)
210 parent->listp = nullptr;
211 } else {
212 parent->removeChild(this);
213 }
214 }
215 }
216
217 void
finalize(FreeOp * fop)218 Shape::finalize(FreeOp* fop)
219 {
220 if (!inDictionary() && kids.isHash())
221 fop->delete_(kids.toHash());
222 }
223
224 void
fixupDictionaryShapeAfterMovingGC()225 Shape::fixupDictionaryShapeAfterMovingGC()
226 {
227 if (!listp)
228 return;
229
230 // The listp field either points to the parent field of the next shape in
231 // the list if there is one. Otherwise if this shape is the last in the
232 // list then it points to the shape_ field of the object the list is for.
233 // We can tell which it is because the base shape is owned if this is the
234 // last property and not otherwise.
235 bool listpPointsIntoShape = !MaybeForwarded(base())->isOwned();
236
237 #ifdef DEBUG
238 // Check that we got this right by interrogating the arena.
239 // We use a fake cell pointer for this: it might not point to the beginning
240 // of a cell, but will point into the right arena and will have the right
241 // alignment.
242 Cell* cell = reinterpret_cast<Cell*>(uintptr_t(listp) & ~CellMask);
243 AllocKind kind = TenuredCell::fromPointer(cell)->getAllocKind();
244 MOZ_ASSERT_IF(listpPointsIntoShape, IsShapeAllocKind(kind));
245 MOZ_ASSERT_IF(!listpPointsIntoShape, IsObjectAllocKind(kind));
246 #endif
247
248 if (listpPointsIntoShape) {
249 // listp points to the parent field of the next shape.
250 Shape* next = reinterpret_cast<Shape*>(uintptr_t(listp) - offsetof(Shape, parent));
251 if (gc::IsForwarded(next))
252 listp = &gc::Forwarded(next)->parent;
253 } else {
254 // listp points to the shape_ field of an object.
255 JSObject* last = reinterpret_cast<JSObject*>(uintptr_t(listp) - ShapedObject::offsetOfShape());
256 if (gc::IsForwarded(last))
257 listp = &gc::Forwarded(last)->as<NativeObject>().shape_;
258 }
259 }
260
261 void
fixupShapeTreeAfterMovingGC()262 Shape::fixupShapeTreeAfterMovingGC()
263 {
264 if (kids.isNull())
265 return;
266
267 if (kids.isShape()) {
268 if (gc::IsForwarded(kids.toShape()))
269 kids.setShape(gc::Forwarded(kids.toShape()));
270 return;
271 }
272
273 MOZ_ASSERT(kids.isHash());
274 KidsHash* kh = kids.toHash();
275 for (KidsHash::Enum e(*kh); !e.empty(); e.popFront()) {
276 Shape* key = e.front();
277 if (IsForwarded(key))
278 key = Forwarded(key);
279
280 BaseShape* base = key->base();
281 if (IsForwarded(base))
282 base = Forwarded(base);
283 UnownedBaseShape* unowned = base->unowned();
284 if (IsForwarded(unowned))
285 unowned = Forwarded(unowned);
286
287 GetterOp getter = key->getter();
288 if (key->hasGetterObject())
289 getter = GetterOp(MaybeForwarded(key->getterObject()));
290
291 SetterOp setter = key->setter();
292 if (key->hasSetterObject())
293 setter = SetterOp(MaybeForwarded(key->setterObject()));
294
295 StackShape lookup(unowned,
296 const_cast<Shape*>(key)->propidRef(),
297 key->slotInfo & Shape::SLOT_MASK,
298 key->attrs,
299 key->flags);
300 lookup.updateGetterSetter(getter, setter);
301 e.rekeyFront(lookup, key);
302 }
303 }
304
305 void
fixupAfterMovingGC()306 Shape::fixupAfterMovingGC()
307 {
308 if (inDictionary())
309 fixupDictionaryShapeAfterMovingGC();
310 else
311 fixupShapeTreeAfterMovingGC();
312 }
313
314 void
fixupGetterSetterForBarrier(JSTracer * trc)315 Shape::fixupGetterSetterForBarrier(JSTracer* trc)
316 {
317 if (!hasGetterValue() && !hasSetterValue())
318 return;
319
320 JSObject* priorGetter = asAccessorShape().getterObj;
321 JSObject* priorSetter = asAccessorShape().setterObj;
322 if (!priorGetter && !priorSetter)
323 return;
324
325 JSObject* postGetter = priorGetter;
326 JSObject* postSetter = priorSetter;
327 if (priorGetter)
328 TraceManuallyBarrieredEdge(trc, &postGetter, "getterObj");
329 if (priorSetter)
330 TraceManuallyBarrieredEdge(trc, &postSetter, "setterObj");
331 if (priorGetter == postGetter && priorSetter == postSetter)
332 return;
333
334 if (parent && !parent->inDictionary() && parent->kids.isHash()) {
335 // Relocating the getterObj or setterObj will have changed our location
336 // in our parent's KidsHash, so take care to update it. We must do this
337 // before we update the shape itself, since the shape is used to match
338 // the original entry in the hash set.
339
340 StackShape original(this);
341 StackShape updated(this);
342 updated.rawGetter = reinterpret_cast<GetterOp>(postGetter);
343 updated.rawSetter = reinterpret_cast<SetterOp>(postSetter);
344
345 KidsHash* kh = parent->kids.toHash();
346 MOZ_ALWAYS_TRUE(kh->rekeyAs(original, updated, this));
347 }
348
349 asAccessorShape().getterObj = postGetter;
350 asAccessorShape().setterObj = postSetter;
351
352 MOZ_ASSERT_IF(parent && !parent->inDictionary() && parent->kids.isHash(),
353 parent->kids.toHash()->has(StackShape(this)));
354 }
355
356 #ifdef DEBUG
357
358 void
checkConsistency(Shape * aKid) const359 KidsPointer::checkConsistency(Shape* aKid) const
360 {
361 if (isShape()) {
362 MOZ_ASSERT(toShape() == aKid);
363 } else {
364 MOZ_ASSERT(isHash());
365 KidsHash* hash = toHash();
366 KidsHash::Ptr ptr = hash->lookup(StackShape(aKid));
367 MOZ_ASSERT(*ptr == aKid);
368 }
369 }
370
371 void
dump(FILE * fp) const372 Shape::dump(FILE* fp) const
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
dumpSubtree(int level,FILE * fp) const421 Shape::dumpSubtree(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(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(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(level, fp);
445 }
446 }
447 }
448 }
449
450 #endif
451