Line data Source code
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 : /* JS symbol tables. */
8 :
9 : #include "vm/Shape-inl.h"
10 :
11 : #include "mozilla/DebugOnly.h"
12 : #include "mozilla/MathAlgorithms.h"
13 : #include "mozilla/PodOperations.h"
14 :
15 : #include "jsatom.h"
16 : #include "jscntxt.h"
17 : #include "jshashutil.h"
18 : #include "jsobj.h"
19 :
20 : #include "gc/Policy.h"
21 : #include "js/HashTable.h"
22 :
23 : #include "jscntxtinlines.h"
24 : #include "jscompartmentinlines.h"
25 : #include "jsobjinlines.h"
26 :
27 : #include "vm/Caches-inl.h"
28 : #include "vm/NativeObject-inl.h"
29 :
30 : using namespace js;
31 : using namespace js::gc;
32 :
33 : using mozilla::CeilingLog2Size;
34 : using mozilla::DebugOnly;
35 : using mozilla::PodZero;
36 : using mozilla::RotateLeft;
37 :
38 : using JS::AutoCheckCannotGC;
39 :
40 : Shape* const ShapeTable::Entry::SHAPE_REMOVED = (Shape*)ShapeTable::Entry::SHAPE_COLLISION;
41 :
42 : bool
43 2716 : ShapeTable::init(JSContext* cx, Shape* lastProp)
44 : {
45 2716 : uint32_t sizeLog2 = CeilingLog2Size(entryCount_);
46 2716 : uint32_t size = JS_BIT(sizeLog2);
47 2716 : if (entryCount_ >= size - (size >> 2))
48 1700 : sizeLog2++;
49 2716 : if (sizeLog2 < MIN_SIZE_LOG2)
50 65 : sizeLog2 = MIN_SIZE_LOG2;
51 :
52 2716 : size = JS_BIT(sizeLog2);
53 2716 : entries_ = cx->pod_calloc<Entry>(size);
54 2716 : if (!entries_)
55 0 : return false;
56 :
57 2716 : MOZ_ASSERT(sizeLog2 <= HASH_BITS);
58 2716 : hashShift_ = HASH_BITS - sizeLog2;
59 :
60 66952 : for (Shape::Range<NoGC> r(lastProp); !r.empty(); r.popFront()) {
61 64236 : Shape& shape = r.front();
62 64236 : Entry& entry = searchUnchecked<MaybeAdding::Adding>(shape.propid());
63 :
64 : /*
65 : * Beware duplicate args and arg vs. var conflicts: the youngest shape
66 : * (nearest to lastProp) must win. See bug 600067.
67 : */
68 64236 : if (!entry.shape())
69 64236 : entry.setPreservingCollision(&shape);
70 : }
71 :
72 2716 : MOZ_ASSERT(capacity() == size);
73 2716 : MOZ_ASSERT(size >= MIN_SIZE);
74 2716 : MOZ_ASSERT(!needsToGrow());
75 2716 : return true;
76 : }
77 :
78 : void
79 5311 : Shape::removeFromDictionary(NativeObject* obj)
80 : {
81 5311 : MOZ_ASSERT(inDictionary());
82 5311 : MOZ_ASSERT(obj->inDictionaryMode());
83 5311 : MOZ_ASSERT(listp);
84 :
85 5311 : MOZ_ASSERT(obj->shape_->inDictionary());
86 5311 : MOZ_ASSERT(obj->shape_->listp == &obj->shape_);
87 :
88 5311 : if (parent)
89 5249 : parent->listp = listp;
90 5311 : *listp = parent;
91 5311 : listp = nullptr;
92 :
93 5311 : obj->shape_->clearCachedBigEnoughForShapeTable();
94 5311 : }
95 :
96 : void
97 22311 : Shape::insertIntoDictionary(GCPtrShape* dictp)
98 : {
99 : // Don't assert inDictionaryMode() here because we may be called from
100 : // JSObject::toDictionaryMode via JSObject::newDictionaryShape.
101 22311 : MOZ_ASSERT(inDictionary());
102 22311 : MOZ_ASSERT(!listp);
103 :
104 22311 : MOZ_ASSERT_IF(*dictp, (*dictp)->inDictionary());
105 22311 : MOZ_ASSERT_IF(*dictp, (*dictp)->listp == dictp);
106 22311 : MOZ_ASSERT_IF(*dictp, zone() == (*dictp)->zone());
107 :
108 22311 : setParent(dictp->get());
109 22311 : if (parent)
110 7595 : parent->listp = &parent;
111 22311 : listp = (GCPtrShape*) dictp;
112 22311 : *dictp = this;
113 22311 : }
114 :
115 : bool
116 2716 : Shape::makeOwnBaseShape(JSContext* cx)
117 : {
118 2716 : MOZ_ASSERT(!base()->isOwned());
119 2716 : MOZ_ASSERT(cx->zone() == zone());
120 :
121 2716 : BaseShape* nbase = Allocate<BaseShape, NoGC>(cx);
122 2716 : if (!nbase)
123 0 : return false;
124 :
125 2716 : new (nbase) BaseShape(StackBaseShape(this));
126 2716 : nbase->setOwned(base()->toUnowned());
127 :
128 2716 : this->base_ = nbase;
129 :
130 2716 : return true;
131 : }
132 :
133 : void
134 7378 : Shape::handoffTableTo(Shape* shape)
135 : {
136 7378 : MOZ_ASSERT(inDictionary() && shape->inDictionary());
137 :
138 7378 : if (this == shape)
139 379 : return;
140 :
141 6999 : MOZ_ASSERT(base()->isOwned() && !shape->base()->isOwned());
142 :
143 6999 : BaseShape* nbase = base();
144 :
145 6999 : MOZ_ASSERT_IF(shape->hasSlot(), nbase->slotSpan() > shape->slot());
146 :
147 6999 : this->base_ = nbase->baseUnowned();
148 6999 : nbase->adoptUnowned(shape->base()->toUnowned());
149 :
150 6999 : shape->base_ = nbase;
151 : }
152 :
153 : /* static */ bool
154 2716 : Shape::hashify(JSContext* cx, Shape* shape)
155 : {
156 2716 : MOZ_ASSERT(!shape->hasTable());
157 :
158 2716 : if (!shape->ensureOwnBaseShape(cx))
159 0 : return false;
160 :
161 2716 : ShapeTable* table = cx->new_<ShapeTable>(shape->entryCount());
162 2716 : if (!table)
163 0 : return false;
164 :
165 2716 : if (!table->init(cx, shape)) {
166 0 : js_free(table);
167 0 : return false;
168 : }
169 :
170 2716 : shape->base()->setTable(table);
171 2716 : return true;
172 : }
173 :
174 : bool
175 64 : ShapeTable::change(JSContext* cx, int log2Delta)
176 : {
177 64 : MOZ_ASSERT(entries_);
178 64 : MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1);
179 :
180 : /*
181 : * Grow, shrink, or compress by changing this->entries_.
182 : */
183 64 : uint32_t oldLog2 = HASH_BITS - hashShift_;
184 64 : uint32_t newLog2 = oldLog2 + log2Delta;
185 64 : uint32_t oldSize = JS_BIT(oldLog2);
186 64 : uint32_t newSize = JS_BIT(newLog2);
187 64 : Entry* newTable = cx->maybe_pod_calloc<Entry>(newSize);
188 64 : if (!newTable)
189 0 : return false;
190 :
191 : /* Now that we have newTable allocated, update members. */
192 64 : MOZ_ASSERT(newLog2 <= HASH_BITS);
193 64 : hashShift_ = HASH_BITS - newLog2;
194 64 : removedCount_ = 0;
195 64 : Entry* oldTable = entries_;
196 64 : entries_ = newTable;
197 :
198 : /* Copy only live entries, leaving removed and free ones behind. */
199 128 : AutoCheckCannotGC nogc;
200 3548 : for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) {
201 3484 : if (Shape* shape = oldEntry->shape()) {
202 2564 : Entry& entry = search<MaybeAdding::Adding>(shape->propid(), nogc);
203 2564 : MOZ_ASSERT(entry.isFree());
204 2564 : entry.setShape(shape);
205 : }
206 3484 : oldSize--;
207 : }
208 :
209 64 : MOZ_ASSERT(capacity() == newSize);
210 :
211 : /* Finally, free the old entries storage. */
212 64 : js_free(oldTable);
213 64 : return true;
214 : }
215 :
216 : bool
217 61 : ShapeTable::grow(JSContext* cx)
218 : {
219 61 : MOZ_ASSERT(needsToGrow());
220 :
221 61 : uint32_t size = capacity();
222 61 : int delta = removedCount_ < (size >> 2);
223 :
224 61 : MOZ_ASSERT(entryCount_ + removedCount_ <= size - 1);
225 :
226 61 : if (!change(cx, delta)) {
227 0 : if (entryCount_ + removedCount_ == size - 1) {
228 0 : ReportOutOfMemory(cx);
229 0 : return false;
230 : }
231 : }
232 :
233 61 : return true;
234 : }
235 :
236 : void
237 0 : ShapeTable::trace(JSTracer* trc)
238 : {
239 0 : for (size_t i = 0; i < capacity(); i++) {
240 0 : Entry& entry = getEntry(i);
241 0 : Shape* shape = entry.shape();
242 0 : if (shape) {
243 0 : TraceManuallyBarrieredEdge(trc, &shape, "ShapeTable shape");
244 0 : if (shape != entry.shape())
245 0 : entry.setPreservingCollision(shape);
246 : }
247 : }
248 0 : }
249 :
250 : #ifdef JSGC_HASH_TABLE_CHECKS
251 :
252 : void
253 0 : ShapeTable::checkAfterMovingGC()
254 : {
255 0 : for (size_t i = 0; i < capacity(); i++) {
256 0 : Entry& entry = getEntry(i);
257 0 : Shape* shape = entry.shape();
258 0 : if (shape)
259 0 : CheckGCThingAfterMovingGC(shape);
260 : }
261 0 : }
262 :
263 : #endif
264 :
265 : /* static */ Shape*
266 10037 : Shape::replaceLastProperty(JSContext* cx, StackBaseShape& base,
267 : TaggedProto proto, HandleShape shape)
268 : {
269 10037 : MOZ_ASSERT(!shape->inDictionary());
270 :
271 10037 : if (!shape->parent) {
272 : /* Treat as resetting the initial property of the shape hierarchy. */
273 8142 : AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
274 16284 : return EmptyShape::getInitialShape(cx, base.clasp, proto, kind,
275 16284 : base.flags & BaseShape::OBJECT_FLAG_MASK);
276 : }
277 :
278 1895 : UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
279 1895 : if (!nbase)
280 0 : return nullptr;
281 :
282 3790 : Rooted<StackShape> child(cx, StackShape(shape));
283 1895 : child.setBase(nbase);
284 :
285 1895 : return cx->zone()->propertyTree().getChild(cx, shape->parent, child);
286 : }
287 :
288 : /*
289 : * Get or create a property-tree or dictionary child property of |parent|,
290 : * which must be lastProperty() if inDictionaryMode(), else parent must be
291 : * one of lastProperty() or lastProperty()->parent.
292 : */
293 : /* static */ MOZ_ALWAYS_INLINE Shape*
294 117460 : NativeObject::getChildProperty(JSContext* cx,
295 : HandleNativeObject obj, HandleShape parent,
296 : MutableHandle<StackShape> child)
297 : {
298 : /*
299 : * Shared properties have no slot, but slot_ will reflect that of parent.
300 : * Unshared properties allocate a slot here but may lose it due to a
301 : * JS_ClearScope call.
302 : */
303 117460 : if (!child.hasSlot()) {
304 15150 : child.setSlot(parent->maybeSlot());
305 : } else {
306 102310 : if (child.hasMissingSlot()) {
307 : uint32_t slot;
308 102182 : if (obj->inDictionaryMode()) {
309 1957 : if (!allocDictionarySlot(cx, obj, &slot))
310 0 : return nullptr;
311 : } else {
312 100225 : slot = obj->slotSpan();
313 100225 : MOZ_ASSERT(slot >= JSSLOT_FREE(obj->getClass()));
314 : // Objects with many properties are converted to dictionary
315 : // mode, so we can't overflow SHAPE_MAXIMUM_SLOT here.
316 100225 : MOZ_ASSERT(slot < JSSLOT_FREE(obj->getClass()) + PropertyTree::MAX_HEIGHT);
317 100225 : MOZ_ASSERT(slot < SHAPE_MAXIMUM_SLOT);
318 : }
319 102182 : child.setSlot(slot);
320 : } else {
321 : /*
322 : * Slots can only be allocated out of order on objects in
323 : * dictionary mode. Otherwise the child's slot must be after the
324 : * parent's slot (if it has one), because slot number determines
325 : * slot span for objects with that shape. Usually child slot
326 : * *immediately* follows parent slot, but there may be a slot gap
327 : * when the object uses some -- but not all -- of its reserved
328 : * slots to store properties.
329 : */
330 128 : MOZ_ASSERT(obj->inDictionaryMode() ||
331 : parent->hasMissingSlot() ||
332 : child.slot() == parent->maybeSlot() + 1 ||
333 : (parent->maybeSlot() + 1 < JSSLOT_FREE(obj->getClass()) &&
334 : child.slot() == JSSLOT_FREE(obj->getClass())));
335 : }
336 : }
337 :
338 117460 : if (obj->inDictionaryMode()) {
339 2665 : MOZ_ASSERT(parent == obj->lastProperty());
340 2665 : Shape* shape = child.isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
341 2665 : if (!shape)
342 0 : return nullptr;
343 2665 : if (child.hasSlot() && child.slot() >= obj->lastProperty()->base()->slotSpan()) {
344 0 : if (!obj->setSlotSpan(cx, child.slot() + 1)) {
345 0 : new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
346 0 : return nullptr;
347 : }
348 : }
349 2665 : shape->initDictionaryShape(child, obj->numFixedSlots(), &obj->shape_);
350 2665 : return shape;
351 : }
352 :
353 114795 : Shape* shape = cx->zone()->propertyTree().inlinedGetChild(cx, parent, child);
354 114795 : if (!shape)
355 0 : return nullptr;
356 : //MOZ_ASSERT(shape->parent == parent);
357 : //MOZ_ASSERT_IF(parent != lastProperty(), parent == lastProperty()->parent);
358 114795 : if (!obj->setLastProperty(cx, shape))
359 0 : return nullptr;
360 114795 : return shape;
361 : }
362 :
363 : /* static */ bool
364 947 : js::NativeObject::toDictionaryMode(JSContext* cx, HandleNativeObject obj)
365 : {
366 947 : MOZ_ASSERT(!obj->inDictionaryMode());
367 947 : MOZ_ASSERT(cx->isInsideCurrentCompartment(obj));
368 :
369 947 : uint32_t span = obj->slotSpan();
370 :
371 : // Clone the shapes into a new dictionary list. Don't update the last
372 : // property of this object until done, otherwise a GC triggered while
373 : // creating the dictionary will get the wrong slot span for this object.
374 1894 : RootedShape root(cx);
375 1894 : RootedShape dictionaryShape(cx);
376 :
377 1894 : RootedShape shape(cx, obj->lastProperty());
378 32273 : while (shape) {
379 15663 : MOZ_ASSERT(!shape->inDictionary());
380 :
381 15663 : Shape* dprop = shape->isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
382 15663 : if (!dprop) {
383 0 : ReportOutOfMemory(cx);
384 0 : return false;
385 : }
386 :
387 15663 : GCPtrShape* listp = dictionaryShape ? &dictionaryShape->parent : nullptr;
388 15663 : StackShape child(shape);
389 15663 : dprop->initDictionaryShape(child, obj->numFixedSlots(), listp);
390 :
391 15663 : if (!dictionaryShape)
392 947 : root = dprop;
393 :
394 15663 : MOZ_ASSERT(!dprop->hasTable());
395 15663 : dictionaryShape = dprop;
396 15663 : shape = shape->previous();
397 : }
398 :
399 947 : if (!Shape::hashify(cx, root)) {
400 0 : ReportOutOfMemory(cx);
401 0 : return false;
402 : }
403 :
404 953 : if (IsInsideNursery(obj) &&
405 6 : !cx->nursery().queueDictionaryModeObjectToSweep(obj))
406 : {
407 0 : ReportOutOfMemory(cx);
408 0 : return false;
409 : }
410 :
411 947 : MOZ_ASSERT(root->listp == nullptr);
412 947 : root->listp = &obj->shape_;
413 947 : obj->shape_ = root;
414 :
415 947 : MOZ_ASSERT(obj->inDictionaryMode());
416 947 : root->base()->setSlotSpan(span);
417 :
418 947 : return true;
419 : }
420 :
421 : static bool
422 114332 : ShouldConvertToDictionary(NativeObject* obj)
423 : {
424 : /*
425 : * Use a lower limit if this object is likely a hashmap (SETELEM was used
426 : * to set properties).
427 : */
428 114332 : if (obj->hadElementsAccess())
429 209 : return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT_WITH_ELEMENTS_ACCESS;
430 114123 : return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT;
431 : }
432 :
433 : static MOZ_ALWAYS_INLINE UnownedBaseShape*
434 126757 : GetBaseShapeForNewShape(JSContext* cx, HandleShape last, HandleId id)
435 : {
436 : uint32_t index;
437 126757 : bool indexed = IdIsIndex(id, &index);
438 126757 : bool interestingSymbol = JSID_IS_SYMBOL(id) && JSID_TO_SYMBOL(id)->isInterestingSymbol();
439 :
440 126757 : if (MOZ_LIKELY(!indexed && !interestingSymbol))
441 125847 : return last->base()->unowned();
442 :
443 910 : StackBaseShape base(last->base());
444 910 : if (indexed)
445 98 : base.flags |= BaseShape::INDEXED;
446 812 : else if (interestingSymbol)
447 812 : base.flags |= BaseShape::HAS_INTERESTING_SYMBOL;
448 910 : return BaseShape::getUnowned(cx, base);
449 : }
450 :
451 : /* static */ Shape*
452 117308 : NativeObject::addPropertyInternal(JSContext* cx,
453 : HandleNativeObject obj, HandleId id,
454 : GetterOp getter, SetterOp setter,
455 : uint32_t slot, unsigned attrs,
456 : unsigned flags, ShapeTable::Entry* entry,
457 : bool allowDictionary, const AutoKeepShapeTables& keep)
458 : {
459 117308 : MOZ_ASSERT_IF(!allowDictionary, !obj->inDictionaryMode());
460 117308 : MOZ_ASSERT(getter != JS_PropertyStub);
461 117308 : MOZ_ASSERT(setter != JS_StrictPropertyStub);
462 :
463 234616 : AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
464 :
465 : /*
466 : * The code below deals with either converting obj to dictionary mode or
467 : * growing an object that's already in dictionary mode. Either way,
468 : * dictionray operations are safe if thread local.
469 : */
470 117308 : ShapeTable* table = nullptr;
471 117308 : if (!obj->inDictionaryMode()) {
472 : bool stableSlot =
473 73 : (slot == SHAPE_INVALID_SLOT) ||
474 114656 : obj->lastProperty()->hasMissingSlot() ||
475 114656 : (slot == obj->lastProperty()->maybeSlot() + 1);
476 114648 : MOZ_ASSERT_IF(!allowDictionary, stableSlot);
477 228986 : if (allowDictionary &&
478 228664 : (!stableSlot || ShouldConvertToDictionary(obj)))
479 : {
480 6 : if (!toDictionaryMode(cx, obj))
481 0 : return nullptr;
482 6 : table = obj->lastProperty()->maybeTable(keep);
483 6 : entry = &table->search<MaybeAdding::Adding>(id, keep);
484 : }
485 : } else {
486 2659 : table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
487 2659 : if (!table)
488 0 : return nullptr;
489 2659 : if (table->needsToGrow()) {
490 61 : if (!table->grow(cx))
491 0 : return nullptr;
492 61 : entry = &table->search<MaybeAdding::Adding>(id, keep);
493 61 : MOZ_ASSERT(!entry->shape());
494 : }
495 : }
496 :
497 117308 : MOZ_ASSERT(!!table == !!entry);
498 :
499 : /* Find or create a property tree node labeled by our arguments. */
500 234616 : RootedShape shape(cx);
501 : {
502 234616 : RootedShape last(cx, obj->lastProperty());
503 234616 : Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, last, id));
504 117308 : if (!nbase)
505 0 : return nullptr;
506 :
507 234616 : Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs, flags));
508 117308 : child.updateGetterSetter(getter, setter);
509 117308 : shape = getChildProperty(cx, obj, last, &child);
510 : }
511 :
512 117308 : if (shape) {
513 117308 : MOZ_ASSERT(shape == obj->lastProperty());
514 :
515 117308 : if (table) {
516 : /* Store the tree node pointer in the table entry for id. */
517 2665 : entry->setPreservingCollision(shape);
518 2665 : table->incEntryCount();
519 :
520 : /* Pass the table along to the new last property, namely shape. */
521 2665 : MOZ_ASSERT(shape->parent->maybeTable(keep) == table);
522 2665 : shape->parent->handoffTableTo(shape);
523 : }
524 :
525 117308 : obj->checkShapeConsistency();
526 117308 : return shape;
527 : }
528 :
529 0 : obj->checkShapeConsistency();
530 0 : return nullptr;
531 : }
532 :
533 : Shape*
534 20 : js::ReshapeForAllocKind(JSContext* cx, Shape* shape, TaggedProto proto,
535 : gc::AllocKind allocKind)
536 : {
537 : // Compute the number of fixed slots with the new allocation kind.
538 20 : size_t nfixed = gc::GetGCKindSlots(allocKind, shape->getObjectClass());
539 :
540 : // Get all the ids in the shape, in order.
541 40 : js::AutoIdVector ids(cx);
542 : {
543 80 : for (unsigned i = 0; i < shape->slotSpan(); i++) {
544 60 : if (!ids.append(JSID_VOID))
545 0 : return nullptr;
546 : }
547 20 : Shape* nshape = shape;
548 140 : while (!nshape->isEmptyShape()) {
549 60 : ids[nshape->slot()].set(nshape->propid());
550 60 : nshape = nshape->previous();
551 : }
552 : }
553 :
554 : // Construct the new shape, without updating type information.
555 40 : RootedId id(cx);
556 40 : RootedShape newShape(cx, EmptyShape::getInitialShape(cx, shape->getObjectClass(),
557 40 : proto, nfixed, shape->getObjectFlags()));
558 20 : if (!newShape)
559 0 : return nullptr;
560 :
561 80 : for (unsigned i = 0; i < ids.length(); i++) {
562 60 : id = ids[i];
563 :
564 120 : Rooted<UnownedBaseShape*> nbase(cx, GetBaseShapeForNewShape(cx, newShape, id));
565 60 : if (!nbase)
566 0 : return nullptr;
567 :
568 120 : Rooted<StackShape> child(cx, StackShape(nbase, id, i, JSPROP_ENUMERATE, 0));
569 60 : newShape = cx->zone()->propertyTree().getChild(cx, newShape, child);
570 60 : if (!newShape)
571 0 : return nullptr;
572 : }
573 :
574 20 : return newShape;
575 : }
576 :
577 : /*
578 : * Check and adjust the new attributes for the shape to make sure that our
579 : * slot access optimizations are sound. It is responsibility of the callers to
580 : * enforce all restrictions from ECMA-262 v5 8.12.9 [[DefineOwnProperty]].
581 : */
582 : static inline bool
583 9389 : CheckCanChangeAttrs(JSContext* cx, JSObject* obj, Shape* shape, unsigned* attrsp)
584 : {
585 9389 : if (shape->configurable())
586 9334 : return true;
587 :
588 : /* A permanent property must stay permanent. */
589 55 : *attrsp |= JSPROP_PERMANENT;
590 :
591 : /* Reject attempts to remove a slot from the permanent data property. */
592 110 : if (shape->isDataDescriptor() && shape->hasSlot() &&
593 55 : (*attrsp & (JSPROP_GETTER | JSPROP_SETTER | JSPROP_SHARED)))
594 : {
595 0 : if (!cx->helperThread())
596 0 : JSObject::reportNotConfigurable(cx, shape->propid());
597 0 : return false;
598 : }
599 :
600 55 : return true;
601 : }
602 :
603 : /* static */ Shape*
604 9389 : NativeObject::putProperty(JSContext* cx, HandleNativeObject obj, HandleId id,
605 : GetterOp getter, SetterOp setter, uint32_t slot, unsigned attrs,
606 : unsigned flags)
607 : {
608 9389 : MOZ_ASSERT(!JSID_IS_VOID(id));
609 9389 : MOZ_ASSERT(getter != JS_PropertyStub);
610 9389 : MOZ_ASSERT(setter != JS_StrictPropertyStub);
611 :
612 : #ifdef DEBUG
613 9389 : if (obj->is<ArrayObject>()) {
614 0 : ArrayObject* arr = &obj->as<ArrayObject>();
615 : uint32_t index;
616 0 : if (IdIsIndex(id, &index))
617 0 : MOZ_ASSERT(index < arr->length() || arr->lengthIsWritable());
618 : }
619 : #endif
620 :
621 18778 : AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
622 :
623 : /*
624 : * Search for id in order to claim its entry if table has been allocated.
625 : *
626 : * Note that we can only try to claim an entry in a table that is thread
627 : * local. An object may be thread local *without* its shape being thread
628 : * local. The only thread local objects that *also* have thread local
629 : * shapes are dictionaries that were allocated/converted thread
630 : * locally. Only for those objects we can try to claim an entry in its
631 : * shape table.
632 : */
633 18778 : AutoKeepShapeTables keep(cx);
634 : ShapeTable::Entry* entry;
635 18778 : RootedShape shape(cx);
636 18778 : if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
637 9389 : shape.address(), &entry))
638 : {
639 0 : return nullptr;
640 : }
641 :
642 9389 : if (!shape) {
643 : /*
644 : * You can't add properties to a non-extensible object, but you can change
645 : * attributes of properties in such objects.
646 : */
647 0 : MOZ_ASSERT(obj->nonProxyIsExtensible());
648 :
649 0 : return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags,
650 0 : entry, true, keep);
651 : }
652 :
653 : /* Property exists: search must have returned a valid entry. */
654 9389 : MOZ_ASSERT_IF(entry, !entry->isRemoved());
655 :
656 9389 : if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
657 0 : return nullptr;
658 :
659 : /*
660 : * If the caller wants to allocate a slot, but doesn't care which slot,
661 : * copy the existing shape's slot into slot so we can match shape, if all
662 : * other members match.
663 : */
664 9389 : bool hadSlot = shape->hasSlot();
665 9389 : uint32_t oldSlot = shape->maybeSlot();
666 9389 : if (!(attrs & JSPROP_SHARED) && slot == SHAPE_INVALID_SLOT && hadSlot)
667 9175 : slot = oldSlot;
668 :
669 18778 : Rooted<UnownedBaseShape*> nbase(cx);
670 : {
671 18778 : RootedShape shape(cx, obj->lastProperty());
672 9389 : nbase = GetBaseShapeForNewShape(cx, shape, id);
673 9389 : if (!nbase)
674 0 : return nullptr;
675 : }
676 :
677 : /*
678 : * Now that we've possibly preserved slot, check whether all members match.
679 : * If so, this is a redundant "put" and we can return without more work.
680 : */
681 9389 : if (shape->matchesParamsAfterId(nbase, slot, attrs, flags, getter, setter))
682 8313 : return shape;
683 :
684 : /*
685 : * Overwriting a non-last property requires switching to dictionary mode.
686 : * The shape tree is shared immutable, and we can't removeProperty and then
687 : * addPropertyInternal because a failure under add would lose data.
688 : */
689 1076 : if (shape != obj->lastProperty() && !obj->inDictionaryMode()) {
690 342 : if (!toDictionaryMode(cx, obj))
691 0 : return nullptr;
692 342 : ShapeTable* table = obj->lastProperty()->maybeTable(keep);
693 342 : MOZ_ASSERT(table);
694 342 : entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
695 342 : shape = entry->shape();
696 : }
697 :
698 1076 : MOZ_ASSERT_IF(shape->hasSlot() && !(attrs & JSPROP_SHARED), shape->slot() == slot);
699 :
700 1076 : if (obj->inDictionaryMode()) {
701 : /*
702 : * Updating some property in a dictionary-mode object. Create a new
703 : * shape for the existing property, and also generate a new shape for
704 : * the last property of the dictionary (unless the modified property
705 : * is also the last property).
706 : */
707 924 : bool updateLast = (shape == obj->lastProperty());
708 924 : bool accessorShape = getter || setter || (attrs & (JSPROP_GETTER | JSPROP_SETTER));
709 2772 : shape = NativeObject::replaceWithNewEquivalentShape(cx, obj, shape, nullptr,
710 1848 : accessorShape);
711 924 : if (!shape)
712 0 : return nullptr;
713 924 : if (!updateLast && !NativeObject::generateOwnShape(cx, obj))
714 0 : return nullptr;
715 :
716 : /*
717 : * FIXME bug 593129 -- slot allocation and NativeObject *this must move
718 : * out of here!
719 : */
720 924 : if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED)) {
721 0 : if (!allocDictionarySlot(cx, obj, &slot))
722 0 : return nullptr;
723 : }
724 :
725 924 : if (updateLast)
726 326 : shape->base()->adoptUnowned(nbase);
727 : else
728 598 : shape->base_ = nbase;
729 :
730 924 : MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
731 :
732 924 : shape->setSlot(slot);
733 924 : shape->attrs = uint8_t(attrs);
734 924 : shape->flags = flags | Shape::IN_DICTIONARY | (accessorShape ? Shape::ACCESSOR_SHAPE : 0);
735 924 : if (shape->isAccessorShape()) {
736 117 : AccessorShape& accShape = shape->asAccessorShape();
737 117 : accShape.rawGetter = getter;
738 117 : accShape.rawSetter = setter;
739 117 : GetterSetterWriteBarrierPost(&accShape);
740 : } else {
741 807 : MOZ_ASSERT(!getter);
742 807 : MOZ_ASSERT(!setter);
743 : }
744 : } else {
745 : /*
746 : * Updating the last property in a non-dictionary-mode object. Find an
747 : * alternate shared child of the last property's previous shape.
748 : */
749 152 : StackBaseShape base(obj->lastProperty()->base());
750 :
751 152 : UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
752 152 : if (!nbase)
753 0 : return nullptr;
754 :
755 152 : MOZ_ASSERT(shape == obj->lastProperty());
756 :
757 : /* Find or create a property tree node labeled by our arguments. */
758 304 : Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs, flags));
759 152 : child.updateGetterSetter(getter, setter);
760 304 : RootedShape parent(cx, shape->parent);
761 152 : Shape* newShape = getChildProperty(cx, obj, parent, &child);
762 :
763 152 : if (!newShape) {
764 0 : obj->checkShapeConsistency();
765 0 : return nullptr;
766 : }
767 :
768 152 : shape = newShape;
769 : }
770 :
771 : /*
772 : * Can't fail now, so free the previous incarnation's slot if the new shape
773 : * has no slot. But we do not need to free oldSlot (and must not, as trying
774 : * to will botch an assertion in JSObject::freeSlot) if the new last
775 : * property (shape here) has a slotSpan that does not cover it.
776 : */
777 1076 : if (hadSlot && !shape->hasSlot()) {
778 23 : if (oldSlot < obj->slotSpan())
779 16 : obj->freeSlot(cx, oldSlot);
780 : /* Note: The optimization based on propertyRemovals is only relevant to the active thread. */
781 23 : if (!cx->helperThread())
782 23 : ++cx->propertyRemovals;
783 : }
784 :
785 1076 : obj->checkShapeConsistency();
786 :
787 1076 : return shape;
788 : }
789 :
790 : /* static */ Shape*
791 0 : NativeObject::changeProperty(JSContext* cx, HandleNativeObject obj, HandleShape shape,
792 : unsigned attrs, GetterOp getter, SetterOp setter)
793 : {
794 0 : MOZ_ASSERT(obj->containsPure(shape));
795 0 : MOZ_ASSERT(getter != JS_PropertyStub);
796 0 : MOZ_ASSERT(setter != JS_StrictPropertyStub);
797 0 : MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
798 :
799 : /* Allow only shared (slotless) => unshared (slotful) transition. */
800 0 : MOZ_ASSERT(!((attrs ^ shape->attrs) & JSPROP_SHARED) ||
801 : !(attrs & JSPROP_SHARED));
802 :
803 0 : MarkTypePropertyNonData(cx, obj, shape->propid());
804 :
805 0 : if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
806 0 : return nullptr;
807 :
808 0 : if (shape->attrs == attrs && shape->getter() == getter && shape->setter() == setter)
809 0 : return shape;
810 :
811 : /*
812 : * Let JSObject::putProperty handle this |overwriting| case, including
813 : * the conservation of shape->slot (if it's valid). We must not call
814 : * removeProperty because it will free an allocated shape->slot, and
815 : * putProperty won't re-allocate it.
816 : */
817 0 : RootedId propid(cx, shape->propid());
818 0 : Shape* newShape = putProperty(cx, obj, propid, getter, setter,
819 0 : shape->maybeSlot(), attrs, shape->flags);
820 :
821 0 : obj->checkShapeConsistency();
822 0 : return newShape;
823 : }
824 :
825 : /* static */ bool
826 420 : NativeObject::removeProperty(JSContext* cx, HandleNativeObject obj, jsid id_)
827 : {
828 840 : RootedId id(cx, id_);
829 :
830 840 : AutoKeepShapeTables keep(cx);
831 : ShapeTable::Entry* entry;
832 840 : RootedShape shape(cx);
833 420 : if (!Shape::search(cx, obj->lastProperty(), id, keep, shape.address(), &entry))
834 0 : return false;
835 :
836 420 : if (!shape)
837 0 : return true;
838 :
839 : /*
840 : * If shape is not the last property added, or the last property cannot
841 : * be removed, switch to dictionary mode.
842 : */
843 420 : if (!obj->inDictionaryMode() && (shape != obj->lastProperty() || !obj->canRemoveLastProperty())) {
844 110 : if (!toDictionaryMode(cx, obj))
845 0 : return false;
846 110 : ShapeTable* table = obj->lastProperty()->maybeTable(keep);
847 110 : MOZ_ASSERT(table);
848 110 : entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
849 110 : shape = entry->shape();
850 : }
851 :
852 : /*
853 : * If in dictionary mode, get a new shape for the last property after the
854 : * removal. We need a fresh shape for all dictionary deletions, even of
855 : * the last property. Otherwise, a shape could replay and caches might
856 : * return deleted DictionaryShapes! See bug 595365. Do this before changing
857 : * the object or table, so the remaining removal is infallible.
858 : */
859 840 : RootedShape spare(cx);
860 420 : if (obj->inDictionaryMode()) {
861 : /* For simplicity, always allocate an accessor shape for now. */
862 381 : spare = Allocate<AccessorShape>(cx);
863 381 : if (!spare)
864 0 : return false;
865 381 : new (spare) Shape(shape->base()->unowned(), 0);
866 381 : if (shape == obj->lastProperty()) {
867 : /*
868 : * Get an up to date unowned base shape for the new last property
869 : * when removing the dictionary's last property. Information in
870 : * base shapes for non-last properties may be out of sync with the
871 : * object's state.
872 : */
873 4 : RootedShape previous(cx, obj->lastProperty()->parent);
874 2 : StackBaseShape base(obj->lastProperty()->base());
875 2 : BaseShape* nbase = BaseShape::getUnowned(cx, base);
876 2 : if (!nbase)
877 0 : return false;
878 2 : previous->base_ = nbase;
879 : }
880 : }
881 :
882 : /* If shape has a slot, free its slot number. */
883 420 : if (shape->hasSlot()) {
884 25 : obj->freeSlot(cx, shape->slot());
885 25 : if (!cx->helperThread())
886 25 : ++cx->propertyRemovals;
887 : }
888 :
889 : /*
890 : * A dictionary-mode object owns mutable, unique shapes on a non-circular
891 : * doubly linked list, hashed by lastProperty()->table. So we can edit the
892 : * list and hash in place.
893 : */
894 420 : if (obj->inDictionaryMode()) {
895 381 : ShapeTable* table = obj->lastProperty()->maybeTable(keep);
896 381 : MOZ_ASSERT(table);
897 :
898 381 : if (entry->hadCollision()) {
899 139 : entry->setRemoved();
900 139 : table->decEntryCount();
901 139 : table->incRemovedCount();
902 : } else {
903 242 : entry->setFree();
904 242 : table->decEntryCount();
905 :
906 : #ifdef DEBUG
907 : /*
908 : * Check the consistency of the table but limit the number of
909 : * checks not to alter significantly the complexity of the
910 : * delete in debug builds, see bug 534493.
911 : */
912 242 : Shape* aprop = obj->lastProperty();
913 9919 : for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent)
914 9677 : MOZ_ASSERT_IF(aprop != shape, obj->contains(cx, aprop));
915 : #endif
916 : }
917 :
918 : {
919 : /* Remove shape from its non-circular doubly linked list. */
920 381 : Shape* oldLastProp = obj->lastProperty();
921 381 : shape->removeFromDictionary(obj);
922 :
923 : /* Hand off table from the old to new last property. */
924 381 : oldLastProp->handoffTableTo(obj->lastProperty());
925 : }
926 :
927 : /* Generate a new shape for the object, infallibly. */
928 381 : JS_ALWAYS_TRUE(NativeObject::generateOwnShape(cx, obj, spare));
929 :
930 : /* Consider shrinking table if its load factor is <= .25. */
931 381 : uint32_t size = table->capacity();
932 381 : if (size > ShapeTable::MIN_SIZE && table->entryCount() <= size >> 2)
933 3 : (void) table->change(cx, -1);
934 : } else {
935 : /*
936 : * Non-dictionary-mode shape tables are shared immutables, so all we
937 : * need do is retract the last property and we'll either get or else
938 : * lazily make via a later hashify the exact table for the new property
939 : * lineage.
940 : */
941 39 : MOZ_ASSERT(shape == obj->lastProperty());
942 39 : obj->removeLastProperty(cx);
943 : }
944 :
945 420 : obj->checkShapeConsistency();
946 420 : return true;
947 : }
948 :
949 : /* static */ void
950 0 : NativeObject::clear(JSContext* cx, HandleNativeObject obj)
951 : {
952 0 : Shape* shape = obj->lastProperty();
953 0 : MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
954 :
955 0 : while (shape->parent) {
956 0 : shape = shape->parent;
957 0 : MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
958 : }
959 0 : MOZ_ASSERT(shape->isEmptyShape());
960 :
961 0 : if (obj->inDictionaryMode())
962 0 : shape->listp = &obj->shape_;
963 :
964 0 : JS_ALWAYS_TRUE(obj->setLastProperty(cx, shape));
965 :
966 0 : if (!cx->helperThread())
967 0 : ++cx->propertyRemovals;
968 0 : obj->checkShapeConsistency();
969 0 : }
970 :
971 : /* static */ bool
972 0 : NativeObject::rollbackProperties(JSContext* cx, HandleNativeObject obj, uint32_t slotSpan)
973 : {
974 : /*
975 : * Remove properties from this object until it has a matching slot span.
976 : * The object cannot have escaped in a way which would prevent safe
977 : * removal of the last properties.
978 : */
979 0 : MOZ_ASSERT(!obj->inDictionaryMode() && slotSpan <= obj->slotSpan());
980 : while (true) {
981 0 : if (obj->lastProperty()->isEmptyShape()) {
982 0 : MOZ_ASSERT(slotSpan == 0);
983 0 : break;
984 : } else {
985 0 : uint32_t slot = obj->lastProperty()->slot();
986 0 : if (slot < slotSpan)
987 0 : break;
988 : }
989 0 : if (!NativeObject::removeProperty(cx, obj, obj->lastProperty()->propid()))
990 0 : return false;
991 0 : }
992 :
993 0 : return true;
994 : }
995 :
996 : /* static */ Shape*
997 4930 : NativeObject::replaceWithNewEquivalentShape(JSContext* cx, HandleNativeObject obj,
998 : Shape* oldShape, Shape* newShape, bool accessorShape)
999 : {
1000 4930 : MOZ_ASSERT(cx->isInsideCurrentZone(oldShape));
1001 4930 : MOZ_ASSERT_IF(oldShape != obj->lastProperty(),
1002 : obj->inDictionaryMode() && obj->lookup(cx, oldShape->propidRef()) == oldShape);
1003 :
1004 4930 : if (!obj->inDictionaryMode()) {
1005 978 : RootedShape newRoot(cx, newShape);
1006 489 : if (!toDictionaryMode(cx, obj))
1007 0 : return nullptr;
1008 489 : oldShape = obj->lastProperty();
1009 489 : newShape = newRoot;
1010 : }
1011 :
1012 4930 : if (!newShape) {
1013 9098 : RootedShape oldRoot(cx, oldShape);
1014 13402 : newShape = (oldShape->isAccessorShape() || accessorShape)
1015 9098 : ? Allocate<AccessorShape>(cx)
1016 4288 : : Allocate<Shape>(cx);
1017 4549 : if (!newShape)
1018 0 : return nullptr;
1019 4549 : new (newShape) Shape(oldRoot->base()->unowned(), 0);
1020 4549 : oldShape = oldRoot;
1021 : }
1022 :
1023 9860 : AutoCheckCannotGC nogc;
1024 4930 : ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, nogc);
1025 4930 : if (!table)
1026 0 : return nullptr;
1027 :
1028 4930 : ShapeTable::Entry* entry = oldShape->isEmptyShape()
1029 9798 : ? nullptr
1030 9798 : : &table->search<MaybeAdding::NotAdding>(oldShape->propidRef(), nogc);
1031 :
1032 : /*
1033 : * Splice the new shape into the same position as the old shape, preserving
1034 : * enumeration order (see bug 601399).
1035 : */
1036 4930 : StackShape nshape(oldShape);
1037 4930 : newShape->initDictionaryShape(nshape, obj->numFixedSlots(), oldShape->listp);
1038 :
1039 4930 : MOZ_ASSERT(newShape->parent == oldShape);
1040 4930 : oldShape->removeFromDictionary(obj);
1041 :
1042 4930 : if (newShape == obj->lastProperty())
1043 4332 : oldShape->handoffTableTo(newShape);
1044 :
1045 4930 : if (entry)
1046 4868 : entry->setPreservingCollision(newShape);
1047 4930 : return newShape;
1048 : }
1049 :
1050 : /* static */ bool
1051 2937 : NativeObject::shadowingShapeChange(JSContext* cx, HandleNativeObject obj, const Shape& shape)
1052 : {
1053 2937 : return generateOwnShape(cx, obj);
1054 : }
1055 :
1056 : /* static */ bool
1057 13498 : JSObject::setFlags(JSContext* cx, HandleObject obj, BaseShape::Flag flags,
1058 : GenerateShape generateShape)
1059 : {
1060 13498 : if (obj->hasAllFlags(flags))
1061 3433 : return true;
1062 :
1063 10065 : if (obj->isNative() && obj->as<NativeObject>().inDictionaryMode()) {
1064 28 : if (generateShape == GENERATE_SHAPE) {
1065 28 : if (!NativeObject::generateOwnShape(cx, obj.as<NativeObject>()))
1066 0 : return false;
1067 : }
1068 28 : StackBaseShape base(obj->as<NativeObject>().lastProperty());
1069 28 : base.flags |= flags;
1070 28 : UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
1071 28 : if (!nbase)
1072 0 : return false;
1073 :
1074 28 : obj->as<NativeObject>().lastProperty()->base()->adoptUnowned(nbase);
1075 28 : return true;
1076 : }
1077 :
1078 10037 : Shape* existingShape = obj->ensureShape(cx);
1079 10037 : if (!existingShape)
1080 0 : return false;
1081 :
1082 10037 : Shape* newShape = Shape::setObjectFlags(cx, flags, obj->taggedProto(), existingShape);
1083 10037 : if (!newShape)
1084 0 : return false;
1085 :
1086 : // The success of the |JSObject::ensureShape| call above means that |obj|
1087 : // can be assumed to have a shape.
1088 10037 : obj->as<ShapedObject>().setShape(newShape);
1089 :
1090 10037 : return true;
1091 : }
1092 :
1093 : /* static */ bool
1094 0 : NativeObject::clearFlag(JSContext* cx, HandleNativeObject obj, BaseShape::Flag flag)
1095 : {
1096 0 : MOZ_ASSERT(obj->inDictionaryMode());
1097 :
1098 0 : MOZ_ASSERT(obj->lastProperty()->getObjectFlags() & flag);
1099 :
1100 0 : StackBaseShape base(obj->lastProperty());
1101 0 : base.flags &= ~flag;
1102 0 : UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
1103 0 : if (!nbase)
1104 0 : return false;
1105 :
1106 0 : obj->lastProperty()->base()->adoptUnowned(nbase);
1107 0 : return true;
1108 : }
1109 :
1110 : /* static */ Shape*
1111 10037 : Shape::setObjectFlags(JSContext* cx, BaseShape::Flag flags, TaggedProto proto, Shape* last)
1112 : {
1113 10037 : if ((last->getObjectFlags() & flags) == flags)
1114 0 : return last;
1115 :
1116 10037 : StackBaseShape base(last);
1117 10037 : base.flags |= flags;
1118 :
1119 20074 : RootedShape lastRoot(cx, last);
1120 10037 : return replaceLastProperty(cx, base, proto, lastRoot);
1121 : }
1122 :
1123 : inline
1124 4734 : BaseShape::BaseShape(const StackBaseShape& base)
1125 4734 : : clasp_(base.clasp),
1126 4734 : flags(base.flags),
1127 : slotSpan_(0),
1128 : unowned_(nullptr),
1129 14202 : table_(nullptr)
1130 : {
1131 4734 : }
1132 :
1133 : /* static */ void
1134 7353 : BaseShape::copyFromUnowned(BaseShape& dest, UnownedBaseShape& src)
1135 : {
1136 7353 : dest.clasp_ = src.clasp_;
1137 7353 : dest.slotSpan_ = src.slotSpan_;
1138 7353 : dest.unowned_ = &src;
1139 7353 : dest.flags = src.flags | OWNED_SHAPE;
1140 7353 : }
1141 :
1142 : inline void
1143 7353 : BaseShape::adoptUnowned(UnownedBaseShape* other)
1144 : {
1145 : // This is a base shape owned by a dictionary object, update it to reflect the
1146 : // unowned base shape of a new last property.
1147 7353 : MOZ_ASSERT(isOwned());
1148 :
1149 7353 : uint32_t span = slotSpan();
1150 :
1151 7353 : BaseShape::copyFromUnowned(*this, *other);
1152 7353 : setSlotSpan(span);
1153 :
1154 7353 : assertConsistency();
1155 7353 : }
1156 :
1157 : /* static */ UnownedBaseShape*
1158 15117 : BaseShape::getUnowned(JSContext* cx, StackBaseShape& base)
1159 : {
1160 15117 : auto& table = cx->zone()->baseShapes();
1161 :
1162 15116 : if (!table.initialized() && !table.init()) {
1163 0 : ReportOutOfMemory(cx);
1164 0 : return nullptr;
1165 : }
1166 :
1167 15116 : auto p = MakeDependentAddPtr(cx, table, base);
1168 15117 : if (p)
1169 13099 : return *p;
1170 :
1171 2018 : BaseShape* nbase_ = Allocate<BaseShape>(cx);
1172 2018 : if (!nbase_)
1173 0 : return nullptr;
1174 :
1175 2018 : new (nbase_) BaseShape(base);
1176 :
1177 2018 : UnownedBaseShape* nbase = static_cast<UnownedBaseShape*>(nbase_);
1178 :
1179 2018 : if (!p.add(cx, table, base, nbase))
1180 0 : return nullptr;
1181 :
1182 2018 : return nbase;
1183 : }
1184 :
1185 : void
1186 7762 : BaseShape::assertConsistency()
1187 : {
1188 : #ifdef DEBUG
1189 7762 : if (isOwned()) {
1190 7633 : UnownedBaseShape* unowned = baseUnowned();
1191 7633 : MOZ_ASSERT(getObjectFlags() == unowned->getObjectFlags());
1192 : }
1193 : #endif
1194 7762 : }
1195 :
1196 : void
1197 32 : BaseShape::traceChildren(JSTracer* trc)
1198 : {
1199 32 : traceChildrenSkipShapeTable(trc);
1200 32 : traceShapeTable(trc);
1201 32 : }
1202 :
1203 : void
1204 409 : BaseShape::traceChildrenSkipShapeTable(JSTracer* trc)
1205 : {
1206 409 : if (isOwned())
1207 280 : TraceEdge(trc, &unowned_, "base");
1208 :
1209 409 : assertConsistency();
1210 409 : }
1211 :
1212 : void
1213 32 : BaseShape::traceShapeTable(JSTracer* trc)
1214 : {
1215 64 : AutoCheckCannotGC nogc;
1216 32 : if (ShapeTable* table = maybeTable(nogc))
1217 0 : table->trace(trc);
1218 32 : }
1219 :
1220 : #ifdef DEBUG
1221 : bool
1222 377 : BaseShape::canSkipMarkingShapeTable(Shape* lastShape)
1223 : {
1224 : // Check that every shape in the shape table will be marked by marking
1225 : // |lastShape|.
1226 :
1227 754 : AutoCheckCannotGC nogc;
1228 377 : ShapeTable* table = maybeTable(nogc);
1229 377 : if (!table)
1230 97 : return true;
1231 :
1232 280 : uint32_t count = 0;
1233 10811 : for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) {
1234 10531 : Shape* shape = &r.front();
1235 10531 : ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(shape->propid(), nogc);
1236 10531 : if (entry.isLive())
1237 10531 : count++;
1238 : }
1239 :
1240 280 : return count == table->entryCount();
1241 : }
1242 : #endif
1243 :
1244 : #ifdef JSGC_HASH_TABLE_CHECKS
1245 :
1246 : void
1247 0 : Zone::checkBaseShapeTableAfterMovingGC()
1248 : {
1249 0 : if (!baseShapes().initialized())
1250 0 : return;
1251 :
1252 0 : for (auto r = baseShapes().all(); !r.empty(); r.popFront()) {
1253 0 : UnownedBaseShape* base = r.front().unbarrieredGet();
1254 0 : CheckGCThingAfterMovingGC(base);
1255 :
1256 0 : BaseShapeSet::Ptr ptr = baseShapes().lookup(base);
1257 0 : MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front());
1258 : }
1259 : }
1260 :
1261 : #endif // JSGC_HASH_TABLE_CHECKS
1262 :
1263 : void
1264 0 : BaseShape::finalize(FreeOp* fop)
1265 : {
1266 0 : if (table_) {
1267 0 : fop->delete_(table_);
1268 0 : table_ = nullptr;
1269 : }
1270 0 : }
1271 :
1272 : inline
1273 : InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto()
1274 : {
1275 : }
1276 :
1277 : inline
1278 11215 : InitialShapeEntry::InitialShapeEntry(Shape* shape, const Lookup::ShapeProto& proto)
1279 11215 : : shape(shape), proto(proto)
1280 : {
1281 11215 : }
1282 :
1283 : #ifdef JSGC_HASH_TABLE_CHECKS
1284 :
1285 : void
1286 0 : Zone::checkInitialShapesTableAfterMovingGC()
1287 : {
1288 0 : if (!initialShapes().initialized())
1289 0 : return;
1290 :
1291 : /*
1292 : * Assert that the postbarriers have worked and that nothing is left in
1293 : * initialShapes that points into the nursery, and that the hash table
1294 : * entries are discoverable.
1295 : */
1296 0 : for (auto r = initialShapes().all(); !r.empty(); r.popFront()) {
1297 0 : InitialShapeEntry entry = r.front();
1298 0 : JSProtoKey protoKey = entry.proto.key();
1299 0 : TaggedProto proto = entry.proto.proto().unbarrieredGet();
1300 0 : Shape* shape = entry.shape.unbarrieredGet();
1301 :
1302 0 : CheckGCThingAfterMovingGC(shape);
1303 0 : if (proto.isObject())
1304 0 : CheckGCThingAfterMovingGC(proto.toObject());
1305 :
1306 : using Lookup = InitialShapeEntry::Lookup;
1307 : Lookup lookup(shape->getObjectClass(),
1308 0 : Lookup::ShapeProto(protoKey, proto),
1309 : shape->numFixedSlots(),
1310 0 : shape->getObjectFlags());
1311 0 : InitialShapeSet::Ptr ptr = initialShapes().lookup(lookup);
1312 0 : MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &r.front());
1313 : }
1314 : }
1315 :
1316 : #endif // JSGC_HASH_TABLE_CHECKS
1317 :
1318 : Shape*
1319 5252 : EmptyShape::new_(JSContext* cx, Handle<UnownedBaseShape*> base, uint32_t nfixed)
1320 : {
1321 5252 : Shape* shape = Allocate<Shape>(cx);
1322 5252 : if (!shape) {
1323 0 : ReportOutOfMemory(cx);
1324 0 : return nullptr;
1325 : }
1326 :
1327 5252 : new (shape) EmptyShape(base, nfixed);
1328 5252 : return shape;
1329 : }
1330 :
1331 : MOZ_ALWAYS_INLINE HashNumber
1332 47465 : ShapeHasher::hash(const Lookup& l)
1333 : {
1334 47465 : return l.hash();
1335 : }
1336 :
1337 : MOZ_ALWAYS_INLINE bool
1338 13596 : ShapeHasher::match(const Key k, const Lookup& l)
1339 : {
1340 13596 : return k->matches(l);
1341 : }
1342 :
1343 : static KidsHash*
1344 2095 : HashChildren(Shape* kid1, Shape* kid2)
1345 : {
1346 2095 : KidsHash* hash = js_new<KidsHash>();
1347 2095 : if (!hash || !hash->init(2)) {
1348 0 : js_delete(hash);
1349 0 : return nullptr;
1350 : }
1351 :
1352 2095 : hash->putNewInfallible(StackShape(kid1), kid1);
1353 2095 : hash->putNewInfallible(StackShape(kid2), kid2);
1354 2095 : return hash;
1355 : }
1356 :
1357 : bool
1358 72596 : PropertyTree::insertChild(JSContext* cx, Shape* parent, Shape* child)
1359 : {
1360 72596 : MOZ_ASSERT(!parent->inDictionary());
1361 72596 : MOZ_ASSERT(!child->parent);
1362 72596 : MOZ_ASSERT(!child->inDictionary());
1363 72596 : MOZ_ASSERT(child->zone() == parent->zone());
1364 72597 : MOZ_ASSERT(cx->zone() == zone_);
1365 :
1366 72597 : KidsPointer* kidp = &parent->kids;
1367 :
1368 72597 : if (kidp->isNull()) {
1369 62163 : child->setParent(parent);
1370 62163 : kidp->setShape(child);
1371 62163 : return true;
1372 : }
1373 :
1374 10435 : if (kidp->isShape()) {
1375 2095 : Shape* shape = kidp->toShape();
1376 2095 : MOZ_ASSERT(shape != child);
1377 2095 : MOZ_ASSERT(!shape->matches(child));
1378 :
1379 2095 : KidsHash* hash = HashChildren(shape, child);
1380 2095 : if (!hash) {
1381 0 : ReportOutOfMemory(cx);
1382 0 : return false;
1383 : }
1384 2095 : kidp->setHash(hash);
1385 2095 : child->setParent(parent);
1386 2095 : return true;
1387 : }
1388 :
1389 8340 : if (!kidp->toHash()->putNew(StackShape(child), child)) {
1390 0 : ReportOutOfMemory(cx);
1391 0 : return false;
1392 : }
1393 :
1394 8340 : child->setParent(parent);
1395 8340 : return true;
1396 : }
1397 :
1398 : void
1399 0 : Shape::removeChild(Shape* child)
1400 : {
1401 0 : MOZ_ASSERT(!child->inDictionary());
1402 0 : MOZ_ASSERT(child->parent == this);
1403 :
1404 0 : KidsPointer* kidp = &kids;
1405 :
1406 0 : if (kidp->isShape()) {
1407 0 : MOZ_ASSERT(kidp->toShape() == child);
1408 0 : kidp->setNull();
1409 0 : child->parent = nullptr;
1410 0 : return;
1411 : }
1412 :
1413 0 : KidsHash* hash = kidp->toHash();
1414 0 : MOZ_ASSERT(hash->count() >= 2); /* otherwise kidp->isShape() should be true */
1415 :
1416 : #ifdef DEBUG
1417 0 : size_t oldCount = hash->count();
1418 : #endif
1419 :
1420 0 : hash->remove(StackShape(child));
1421 0 : child->parent = nullptr;
1422 :
1423 0 : MOZ_ASSERT(hash->count() == oldCount - 1);
1424 :
1425 0 : if (hash->count() == 1) {
1426 : /* Convert from HASH form back to SHAPE form. */
1427 0 : KidsHash::Range r = hash->all();
1428 0 : Shape* otherChild = r.front();
1429 0 : MOZ_ASSERT((r.popFront(), r.empty())); /* No more elements! */
1430 0 : kidp->setShape(otherChild);
1431 0 : js_delete(hash);
1432 : }
1433 : }
1434 :
1435 : MOZ_ALWAYS_INLINE Shape*
1436 148184 : PropertyTree::inlinedGetChild(JSContext* cx, Shape* parent, Handle<StackShape> child)
1437 : {
1438 148184 : MOZ_ASSERT(parent);
1439 :
1440 148184 : Shape* existingShape = nullptr;
1441 :
1442 : /*
1443 : * The property tree has extremely low fan-out below its root in
1444 : * popular embeddings with real-world workloads. Patterns such as
1445 : * defining closures that capture a constructor's environment as
1446 : * getters or setters on the new object that is passed in as
1447 : * |this| can significantly increase fan-out below the property
1448 : * tree root -- see bug 335700 for details.
1449 : */
1450 148184 : KidsPointer* kidp = &parent->kids;
1451 148184 : if (kidp->isShape()) {
1452 65030 : Shape* kid = kidp->toShape();
1453 65030 : if (kid->matches(child))
1454 62935 : existingShape = kid;
1455 83157 : } else if (kidp->isHash()) {
1456 20994 : if (KidsHash::Ptr p = kidp->toHash()->lookup(child))
1457 12654 : existingShape = *p;
1458 : } else {
1459 : /* If kidp->isNull(), we always insert. */
1460 : }
1461 :
1462 148187 : if (existingShape) {
1463 75589 : JS::Zone* zone = existingShape->zone();
1464 75589 : if (zone->needsIncrementalBarrier()) {
1465 : /*
1466 : * We need a read barrier for the shape tree, since these are weak
1467 : * pointers.
1468 : */
1469 1059 : Shape* tmp = existingShape;
1470 1059 : TraceManuallyBarrieredEdge(zone->barrierTracer(), &tmp, "read barrier");
1471 1059 : MOZ_ASSERT(tmp == existingShape);
1472 1059 : return existingShape;
1473 : }
1474 74530 : if (!zone->isGCSweepingOrCompacting() ||
1475 0 : !IsAboutToBeFinalizedUnbarriered(&existingShape))
1476 : {
1477 74530 : if (existingShape->isMarkedGray())
1478 0 : UnmarkGrayShapeRecursively(existingShape);
1479 74529 : return existingShape;
1480 : }
1481 : /*
1482 : * The shape we've found is unreachable and due to be finalized, so
1483 : * remove our weak reference to it and don't use it.
1484 : */
1485 0 : MOZ_ASSERT(parent->isMarkedAny());
1486 0 : parent->removeChild(existingShape);
1487 : }
1488 :
1489 145196 : RootedShape parentRoot(cx, parent);
1490 72598 : Shape* shape = Shape::new_(cx, child, parentRoot->numFixedSlots());
1491 72596 : if (!shape)
1492 0 : return nullptr;
1493 :
1494 72596 : if (!insertChild(cx, parentRoot, shape))
1495 0 : return nullptr;
1496 :
1497 72598 : return shape;
1498 : }
1499 :
1500 : Shape*
1501 33391 : PropertyTree::getChild(JSContext* cx, Shape* parent, Handle<StackShape> child)
1502 : {
1503 33391 : return inlinedGetChild(cx, parent, child);
1504 : }
1505 :
1506 : void
1507 0 : Shape::sweep()
1508 : {
1509 : /*
1510 : * We detach the child from the parent if the parent is reachable.
1511 : *
1512 : * This test depends on shape arenas not being freed until after we finish
1513 : * incrementally sweeping them. If that were not the case the parent pointer
1514 : * could point to a marked cell that had been deallocated and then
1515 : * reallocated, since allocating a cell in a zone that is being marked will
1516 : * set the mark bit for that cell.
1517 : */
1518 0 : if (parent && parent->isMarkedAny()) {
1519 0 : if (inDictionary()) {
1520 0 : if (parent->listp == &parent)
1521 0 : parent->listp = nullptr;
1522 : } else {
1523 0 : parent->removeChild(this);
1524 : }
1525 : }
1526 0 : }
1527 :
1528 : void
1529 0 : Shape::finalize(FreeOp* fop)
1530 : {
1531 0 : if (!inDictionary() && kids.isHash())
1532 0 : fop->delete_(kids.toHash());
1533 0 : }
1534 :
1535 : void
1536 0 : Shape::fixupDictionaryShapeAfterMovingGC()
1537 : {
1538 0 : if (!listp)
1539 0 : return;
1540 :
1541 : // The listp field either points to the parent field of the next shape in
1542 : // the list if there is one. Otherwise if this shape is the last in the
1543 : // list then it points to the shape_ field of the object the list is for.
1544 : // We can tell which it is because the base shape is owned if this is the
1545 : // last property and not otherwise.
1546 0 : bool listpPointsIntoShape = !MaybeForwarded(base())->isOwned();
1547 :
1548 : #ifdef DEBUG
1549 : // Check that we got this right by interrogating the arena.
1550 : // We use a fake cell pointer for this: it might not point to the beginning
1551 : // of a cell, but will point into the right arena and will have the right
1552 : // alignment.
1553 0 : Cell* cell = reinterpret_cast<Cell*>(uintptr_t(listp) & ~CellAlignMask);
1554 0 : AllocKind kind = TenuredCell::fromPointer(cell)->getAllocKind();
1555 0 : MOZ_ASSERT_IF(listpPointsIntoShape, IsShapeAllocKind(kind));
1556 0 : MOZ_ASSERT_IF(!listpPointsIntoShape, IsObjectAllocKind(kind));
1557 : #endif
1558 :
1559 0 : if (listpPointsIntoShape) {
1560 : // listp points to the parent field of the next shape.
1561 0 : Shape* next = reinterpret_cast<Shape*>(uintptr_t(listp) - offsetof(Shape, parent));
1562 0 : if (gc::IsForwarded(next))
1563 0 : listp = &gc::Forwarded(next)->parent;
1564 : } else {
1565 : // listp points to the shape_ field of an object.
1566 0 : JSObject* last = reinterpret_cast<JSObject*>(uintptr_t(listp) - ShapedObject::offsetOfShape());
1567 0 : if (gc::IsForwarded(last))
1568 0 : listp = &gc::Forwarded(last)->as<NativeObject>().shape_;
1569 : }
1570 : }
1571 :
1572 : void
1573 0 : Shape::fixupShapeTreeAfterMovingGC()
1574 : {
1575 0 : if (kids.isNull())
1576 0 : return;
1577 :
1578 0 : if (kids.isShape()) {
1579 0 : if (gc::IsForwarded(kids.toShape()))
1580 0 : kids.setShape(gc::Forwarded(kids.toShape()));
1581 0 : return;
1582 : }
1583 :
1584 0 : MOZ_ASSERT(kids.isHash());
1585 0 : KidsHash* kh = kids.toHash();
1586 0 : for (KidsHash::Enum e(*kh); !e.empty(); e.popFront()) {
1587 0 : Shape* key = e.front();
1588 0 : if (IsForwarded(key))
1589 0 : key = Forwarded(key);
1590 :
1591 0 : BaseShape* base = key->base();
1592 0 : if (IsForwarded(base))
1593 0 : base = Forwarded(base);
1594 0 : UnownedBaseShape* unowned = base->unowned();
1595 0 : if (IsForwarded(unowned))
1596 0 : unowned = Forwarded(unowned);
1597 :
1598 0 : GetterOp getter = key->getter();
1599 0 : if (key->hasGetterObject())
1600 0 : getter = GetterOp(MaybeForwarded(key->getterObject()));
1601 :
1602 0 : SetterOp setter = key->setter();
1603 0 : if (key->hasSetterObject())
1604 0 : setter = SetterOp(MaybeForwarded(key->setterObject()));
1605 :
1606 : StackShape lookup(unowned,
1607 0 : const_cast<Shape*>(key)->propidRef(),
1608 0 : key->slotInfo & Shape::SLOT_MASK,
1609 0 : key->attrs,
1610 0 : key->flags);
1611 0 : lookup.updateGetterSetter(getter, setter);
1612 0 : e.rekeyFront(lookup, key);
1613 : }
1614 : }
1615 :
1616 : void
1617 0 : Shape::fixupAfterMovingGC()
1618 : {
1619 0 : if (inDictionary())
1620 0 : fixupDictionaryShapeAfterMovingGC();
1621 : else
1622 0 : fixupShapeTreeAfterMovingGC();
1623 0 : }
1624 :
1625 : void
1626 3129 : Shape::fixupGetterSetterForBarrier(JSTracer* trc)
1627 : {
1628 3129 : if (!hasGetterValue() && !hasSetterValue())
1629 34 : return;
1630 :
1631 3129 : JSObject* priorGetter = asAccessorShape().getterObj;
1632 3129 : JSObject* priorSetter = asAccessorShape().setterObj;
1633 3129 : if (!priorGetter && !priorSetter)
1634 0 : return;
1635 :
1636 3129 : JSObject* postGetter = priorGetter;
1637 3129 : JSObject* postSetter = priorSetter;
1638 3129 : if (priorGetter)
1639 3094 : TraceManuallyBarrieredEdge(trc, &postGetter, "getterObj");
1640 3129 : if (priorSetter)
1641 175 : TraceManuallyBarrieredEdge(trc, &postSetter, "setterObj");
1642 3129 : if (priorGetter == postGetter && priorSetter == postSetter)
1643 34 : return;
1644 :
1645 3095 : if (parent && !parent->inDictionary() && parent->kids.isHash()) {
1646 : // Relocating the getterObj or setterObj will have changed our location
1647 : // in our parent's KidsHash, so take care to update it. We must do this
1648 : // before we update the shape itself, since the shape is used to match
1649 : // the original entry in the hash set.
1650 :
1651 471 : StackShape original(this);
1652 471 : StackShape updated(this);
1653 471 : updated.rawGetter = reinterpret_cast<GetterOp>(postGetter);
1654 471 : updated.rawSetter = reinterpret_cast<SetterOp>(postSetter);
1655 :
1656 471 : KidsHash* kh = parent->kids.toHash();
1657 471 : MOZ_ALWAYS_TRUE(kh->rekeyAs(original, updated, this));
1658 : }
1659 :
1660 3095 : asAccessorShape().getterObj = postGetter;
1661 3095 : asAccessorShape().setterObj = postSetter;
1662 :
1663 3095 : MOZ_ASSERT_IF(parent && !parent->inDictionary() && parent->kids.isHash(),
1664 : parent->kids.toHash()->has(StackShape(this)));
1665 : }
1666 :
1667 : #ifdef DEBUG
1668 :
1669 : void
1670 0 : KidsPointer::checkConsistency(Shape* aKid) const
1671 : {
1672 0 : if (isShape()) {
1673 0 : MOZ_ASSERT(toShape() == aKid);
1674 : } else {
1675 0 : MOZ_ASSERT(isHash());
1676 0 : KidsHash* hash = toHash();
1677 0 : KidsHash::Ptr ptr = hash->lookup(StackShape(aKid));
1678 0 : MOZ_ASSERT(*ptr == aKid);
1679 : }
1680 0 : }
1681 :
1682 : void
1683 0 : Shape::dump(FILE* fp) const
1684 : {
1685 0 : jsid propid = this->propid();
1686 :
1687 0 : MOZ_ASSERT(!JSID_IS_VOID(propid));
1688 :
1689 0 : if (JSID_IS_INT(propid)) {
1690 0 : fprintf(fp, "[%ld]", (long) JSID_TO_INT(propid));
1691 0 : } else if (JSID_IS_ATOM(propid)) {
1692 0 : if (JSLinearString* str = JSID_TO_ATOM(propid))
1693 0 : FileEscapedString(fp, str, '"');
1694 : else
1695 0 : fputs("<error>", fp);
1696 : } else {
1697 0 : MOZ_ASSERT(JSID_IS_SYMBOL(propid));
1698 0 : JSID_TO_SYMBOL(propid)->dump(fp);
1699 : }
1700 :
1701 0 : fprintf(fp, " g/s %p/%p slot %d attrs %x ",
1702 : JS_FUNC_TO_DATA_PTR(void*, getter()),
1703 : JS_FUNC_TO_DATA_PTR(void*, setter()),
1704 0 : hasSlot() ? slot() : -1, attrs);
1705 :
1706 0 : if (attrs) {
1707 0 : int first = 1;
1708 0 : fputs("(", fp);
1709 : #define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(&(" " #display)[first], fp), first = 0
1710 0 : DUMP_ATTR(ENUMERATE, enumerate);
1711 0 : DUMP_ATTR(READONLY, readonly);
1712 0 : DUMP_ATTR(PERMANENT, permanent);
1713 0 : DUMP_ATTR(GETTER, getter);
1714 0 : DUMP_ATTR(SETTER, setter);
1715 0 : DUMP_ATTR(SHARED, shared);
1716 : #undef DUMP_ATTR
1717 0 : fputs(") ", fp);
1718 : }
1719 :
1720 0 : fprintf(fp, "flags %x ", flags);
1721 0 : if (flags) {
1722 0 : int first = 1;
1723 0 : fputs("(", fp);
1724 : #define DUMP_FLAG(name, display) if (flags & name) fputs(&(" " #display)[first], fp), first = 0
1725 0 : DUMP_FLAG(IN_DICTIONARY, in_dictionary);
1726 : #undef DUMP_FLAG
1727 0 : fputs(") ", fp);
1728 : }
1729 0 : }
1730 :
1731 : void
1732 0 : Shape::dumpSubtree(int level, FILE* fp) const
1733 : {
1734 0 : if (!parent) {
1735 0 : MOZ_ASSERT(level == 0);
1736 0 : MOZ_ASSERT(JSID_IS_EMPTY(propid_));
1737 0 : fprintf(fp, "class %s emptyShape\n", getObjectClass()->name);
1738 : } else {
1739 0 : fprintf(fp, "%*sid ", level, "");
1740 0 : dump(fp);
1741 : }
1742 :
1743 0 : if (!kids.isNull()) {
1744 0 : ++level;
1745 0 : if (kids.isShape()) {
1746 0 : Shape* kid = kids.toShape();
1747 0 : MOZ_ASSERT(kid->parent == this);
1748 0 : kid->dumpSubtree(level, fp);
1749 : } else {
1750 0 : const KidsHash& hash = *kids.toHash();
1751 0 : for (KidsHash::Range range = hash.all(); !range.empty(); range.popFront()) {
1752 0 : Shape* kid = range.front();
1753 :
1754 0 : MOZ_ASSERT(kid->parent == this);
1755 0 : kid->dumpSubtree(level, fp);
1756 : }
1757 : }
1758 : }
1759 0 : }
1760 :
1761 : #endif
1762 :
1763 : static bool
1764 22456 : IsOriginalProto(GlobalObject* global, JSProtoKey key, JSObject& proto)
1765 : {
1766 22456 : if (global->getPrototype(key) != ObjectValue(proto))
1767 16455 : return false;
1768 :
1769 6001 : if (key == JSProto_Object) {
1770 4814 : MOZ_ASSERT(proto.staticPrototypeIsImmutable(),
1771 : "proto should be Object.prototype, whose prototype is "
1772 : "immutable");
1773 4814 : MOZ_ASSERT(proto.staticPrototype() == nullptr,
1774 : "Object.prototype must have null prototype");
1775 4814 : return true;
1776 : }
1777 :
1778 : // Check that other prototypes still have Object.prototype as proto.
1779 1187 : JSObject* protoProto = proto.staticPrototype();
1780 1187 : if (!protoProto || global->getPrototype(JSProto_Object) != ObjectValue(*protoProto))
1781 0 : return false;
1782 :
1783 1187 : MOZ_ASSERT(protoProto->staticPrototypeIsImmutable(),
1784 : "protoProto should be Object.prototype, whose prototype is "
1785 : "immutable");
1786 1187 : MOZ_ASSERT(protoProto->staticPrototype() == nullptr,
1787 : "Object.prototype must have null prototype");
1788 1187 : return true;
1789 : }
1790 :
1791 : static JSProtoKey
1792 10382 : GetInitialShapeProtoKey(TaggedProto proto, JSContext* cx)
1793 : {
1794 10382 : if (proto.isObject() && proto.toObject()->hasStaticPrototype()) {
1795 9694 : GlobalObject* global = cx->global();
1796 9694 : JSObject& obj = *proto.toObject();
1797 9694 : MOZ_ASSERT(global == &obj.global());
1798 :
1799 9694 : if (IsOriginalProto(global, JSProto_Object, obj))
1800 4814 : return JSProto_Object;
1801 4880 : if (IsOriginalProto(global, JSProto_Function, obj))
1802 780 : return JSProto_Function;
1803 4100 : if (IsOriginalProto(global, JSProto_Array, obj))
1804 318 : return JSProto_Array;
1805 3782 : if (IsOriginalProto(global, JSProto_RegExp, obj))
1806 89 : return JSProto_RegExp;
1807 : }
1808 4381 : return JSProto_LIMIT;
1809 : }
1810 :
1811 : /* static */ Shape*
1812 142248 : EmptyShape::getInitialShape(JSContext* cx, const Class* clasp, TaggedProto proto,
1813 : size_t nfixed, uint32_t objectFlags)
1814 : {
1815 142248 : MOZ_ASSERT_IF(proto.isObject(), cx->isInsideCurrentCompartment(proto.toObject()));
1816 :
1817 142247 : auto& table = cx->zone()->initialShapes();
1818 :
1819 142249 : if (!table.initialized() && !table.init()) {
1820 0 : ReportOutOfMemory(cx);
1821 0 : return nullptr;
1822 : }
1823 :
1824 : using Lookup = InitialShapeEntry::Lookup;
1825 : auto protoPointer = MakeDependentAddPtr(cx, table,
1826 284497 : Lookup(clasp, Lookup::ShapeProto(proto),
1827 142249 : nfixed, objectFlags));
1828 142248 : if (protoPointer)
1829 131909 : return protoPointer->shape;
1830 :
1831 : // No entry for this proto. If the proto is one of a few common builtin
1832 : // prototypes, try to do a lookup based on the JSProtoKey, so we can share
1833 : // shapes across globals.
1834 20680 : Rooted<TaggedProto> protoRoot(cx, proto);
1835 10340 : Shape* shape = nullptr;
1836 10340 : bool insertKey = false;
1837 20680 : mozilla::Maybe<DependentAddPtr<InitialShapeSet>> keyPointer;
1838 :
1839 10340 : JSProtoKey key = GetInitialShapeProtoKey(protoRoot, cx);
1840 10340 : if (key != JSProto_LIMIT) {
1841 11926 : keyPointer.emplace(MakeDependentAddPtr(cx, table,
1842 11926 : Lookup(clasp, Lookup::ShapeProto(key),
1843 5963 : nfixed, objectFlags)));
1844 5963 : if (keyPointer.ref()) {
1845 5088 : shape = keyPointer.ref()->shape;
1846 5088 : MOZ_ASSERT(shape);
1847 : } else {
1848 875 : insertKey = true;
1849 : }
1850 : }
1851 :
1852 10340 : if (!shape) {
1853 5252 : StackBaseShape base(cx, clasp, objectFlags);
1854 10504 : Rooted<UnownedBaseShape*> nbase(cx, BaseShape::getUnowned(cx, base));
1855 5252 : if (!nbase)
1856 0 : return nullptr;
1857 :
1858 5252 : shape = EmptyShape::new_(cx, nbase, nfixed);
1859 5252 : if (!shape)
1860 0 : return nullptr;
1861 : }
1862 :
1863 10340 : Lookup::ShapeProto shapeProto(protoRoot);
1864 10340 : Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
1865 10340 : if (!protoPointer.add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
1866 0 : return nullptr;
1867 :
1868 : // Also add an entry based on the JSProtoKey, if needed.
1869 10340 : if (insertKey) {
1870 875 : Lookup::ShapeProto shapeProto(key);
1871 875 : Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
1872 875 : if (!keyPointer->add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
1873 0 : return nullptr;
1874 : }
1875 :
1876 10340 : return shape;
1877 : }
1878 :
1879 : /* static */ Shape*
1880 10978 : EmptyShape::getInitialShape(JSContext* cx, const Class* clasp, TaggedProto proto,
1881 : AllocKind kind, uint32_t objectFlags)
1882 : {
1883 10978 : return getInitialShape(cx, clasp, proto, GetGCKindSlots(kind, clasp), objectFlags);
1884 : }
1885 :
1886 : void
1887 16 : NewObjectCache::invalidateEntriesForShape(JSContext* cx, HandleShape shape, HandleObject proto)
1888 : {
1889 16 : const Class* clasp = shape->getObjectClass();
1890 :
1891 16 : gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
1892 16 : if (CanBeFinalizedInBackground(kind, clasp))
1893 16 : kind = GetBackgroundAllocKind(kind);
1894 :
1895 32 : RootedObjectGroup group(cx, ObjectGroup::defaultNewGroup(cx, clasp, TaggedProto(proto)));
1896 16 : if (!group) {
1897 0 : purge();
1898 0 : cx->recoverFromOutOfMemory();
1899 0 : return;
1900 : }
1901 :
1902 : EntryIndex entry;
1903 444 : for (CompartmentsInZoneIter comp(shape->zone()); !comp.done(); comp.next()) {
1904 428 : if (GlobalObject* global = comp->unsafeUnbarrieredMaybeGlobal()) {
1905 428 : if (lookupGlobal(clasp, global, kind, &entry))
1906 1 : PodZero(&entries[entry]);
1907 : }
1908 : }
1909 16 : if (!proto->is<GlobalObject>() && lookupProto(clasp, proto, kind, &entry))
1910 3 : PodZero(&entries[entry]);
1911 16 : if (lookupGroup(group, kind, &entry))
1912 0 : PodZero(&entries[entry]);
1913 : }
1914 :
1915 : /* static */ void
1916 42 : EmptyShape::insertInitialShape(JSContext* cx, HandleShape shape, HandleObject proto)
1917 : {
1918 : using Lookup = InitialShapeEntry::Lookup;
1919 84 : Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(TaggedProto(proto)),
1920 84 : shape->numFixedSlots(), shape->getObjectFlags());
1921 :
1922 42 : InitialShapeSet::Ptr p = cx->zone()->initialShapes().lookup(lookup);
1923 42 : MOZ_ASSERT(p);
1924 :
1925 42 : InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
1926 :
1927 : // The metadata callback can end up causing redundant changes of the initial shape.
1928 42 : if (entry.shape == shape)
1929 0 : return;
1930 :
1931 : // The new shape had better be rooted at the old one.
1932 : #ifdef DEBUG
1933 42 : Shape* nshape = shape;
1934 138 : while (!nshape->isEmptyShape())
1935 48 : nshape = nshape->previous();
1936 42 : MOZ_ASSERT(nshape == entry.shape);
1937 : #endif
1938 :
1939 42 : entry.shape = ReadBarrieredShape(shape);
1940 :
1941 : // For certain prototypes -- namely, those of various builtin classes,
1942 : // keyed by JSProtoKey |key| -- there are two entries: one for a lookup
1943 : // via |proto|, and one for a lookup via |key|. If this is such a
1944 : // prototype, also update the alternate |key|-keyed shape.
1945 42 : JSProtoKey key = GetInitialShapeProtoKey(TaggedProto(proto), cx);
1946 42 : if (key != JSProto_LIMIT) {
1947 76 : Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(key),
1948 76 : shape->numFixedSlots(), shape->getObjectFlags());
1949 38 : if (InitialShapeSet::Ptr p = cx->zone()->initialShapes().lookup(lookup)) {
1950 38 : InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
1951 38 : if (entry.shape != shape)
1952 38 : entry.shape = ReadBarrieredShape(shape);
1953 : }
1954 : }
1955 :
1956 : /*
1957 : * This affects the shape that will be produced by the various NewObject
1958 : * methods, so clear any cache entry referring to the old shape. This is
1959 : * not required for correctness: the NewObject must always check for a
1960 : * nativeEmpty() result and generate the appropriate properties if found.
1961 : * Clearing the cache entry avoids this duplicate regeneration.
1962 : *
1963 : * Clearing is not necessary when this context is running off
1964 : * thread, as it will not use the new object cache for allocations.
1965 : */
1966 42 : if (!cx->helperThread())
1967 16 : cx->caches().newObjectCache.invalidateEntriesForShape(cx, shape, proto);
1968 : }
1969 :
1970 : void
1971 0 : Zone::fixupInitialShapeTable()
1972 : {
1973 0 : if (!initialShapes().initialized())
1974 0 : return;
1975 :
1976 0 : for (InitialShapeSet::Enum e(initialShapes()); !e.empty(); e.popFront()) {
1977 : // The shape may have been moved, but we can update that in place.
1978 0 : Shape* shape = e.front().shape.unbarrieredGet();
1979 0 : if (IsForwarded(shape)) {
1980 0 : shape = Forwarded(shape);
1981 0 : e.mutableFront().shape.set(shape);
1982 : }
1983 0 : shape->updateBaseShapeAfterMovingGC();
1984 :
1985 : // If the prototype has moved we have to rekey the entry.
1986 0 : InitialShapeEntry entry = e.front();
1987 0 : if (entry.proto.proto().isObject() && IsForwarded(entry.proto.proto().toObject())) {
1988 0 : entry.proto.setProto(TaggedProto(Forwarded(entry.proto.proto().toObject())));
1989 : using Lookup = InitialShapeEntry::Lookup;
1990 : Lookup relookup(shape->getObjectClass(),
1991 0 : Lookup::ShapeProto(entry.proto),
1992 : shape->numFixedSlots(),
1993 0 : shape->getObjectFlags());
1994 0 : e.rekeyFront(relookup, entry);
1995 : }
1996 : }
1997 : }
1998 :
1999 : void
2000 2 : AutoRooterGetterSetter::Inner::trace(JSTracer* trc)
2001 : {
2002 2 : if ((attrs & JSPROP_GETTER) && *pgetter)
2003 2 : TraceRoot(trc, (JSObject**) pgetter, "AutoRooterGetterSetter getter");
2004 2 : if ((attrs & JSPROP_SETTER) && *psetter)
2005 0 : TraceRoot(trc, (JSObject**) psetter, "AutoRooterGetterSetter setter");
2006 2 : }
2007 :
2008 : JS::ubi::Node::Size
2009 0 : JS::ubi::Concrete<js::Shape>::size(mozilla::MallocSizeOf mallocSizeOf) const
2010 : {
2011 0 : Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
2012 :
2013 0 : AutoCheckCannotGC nogc;
2014 0 : if (ShapeTable* table = get().maybeTable(nogc))
2015 0 : size += table->sizeOfIncludingThis(mallocSizeOf);
2016 :
2017 0 : if (!get().inDictionary() && get().kids.isHash())
2018 0 : size += get().kids.toHash()->sizeOfIncludingThis(mallocSizeOf);
2019 :
2020 0 : return size;
2021 : }
2022 :
2023 : JS::ubi::Node::Size
2024 0 : JS::ubi::Concrete<js::BaseShape>::size(mozilla::MallocSizeOf mallocSizeOf) const
2025 : {
2026 0 : return js::gc::Arena::thingSize(get().asTenured().getAllocKind());
2027 : }
2028 :
2029 : void
2030 18 : PropertyResult::trace(JSTracer* trc)
2031 : {
2032 18 : if (isNativeProperty())
2033 12 : TraceRoot(trc, &shape_, "PropertyResult::shape_");
2034 27 : }
|
