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
init(ExclusiveContext * cx,Shape * lastProp)43 ShapeTable::init(ExclusiveContext* cx, Shape* lastProp)
44 {
45 uint32_t sizeLog2 = CeilingLog2Size(entryCount_);
46 uint32_t size = JS_BIT(sizeLog2);
47 if (entryCount_ >= size - (size >> 2))
48 sizeLog2++;
49 if (sizeLog2 < MIN_SIZE_LOG2)
50 sizeLog2 = MIN_SIZE_LOG2;
51
52 size = JS_BIT(sizeLog2);
53 entries_ = cx->pod_calloc<Entry>(size);
54 if (!entries_)
55 return false;
56
57 MOZ_ASSERT(sizeLog2 <= HASH_BITS);
58 hashShift_ = HASH_BITS - sizeLog2;
59
60 for (Shape::Range<NoGC> r(lastProp); !r.empty(); r.popFront()) {
61 Shape& shape = r.front();
62 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 if (!entry.shape())
69 entry.setPreservingCollision(&shape);
70 }
71
72 MOZ_ASSERT(capacity() == size);
73 MOZ_ASSERT(size >= MIN_SIZE);
74 MOZ_ASSERT(!needsToGrow());
75 return true;
76 }
77
78 void
removeFromDictionary(NativeObject * obj)79 Shape::removeFromDictionary(NativeObject* obj)
80 {
81 MOZ_ASSERT(inDictionary());
82 MOZ_ASSERT(obj->inDictionaryMode());
83 MOZ_ASSERT(listp);
84
85 MOZ_ASSERT(obj->shape_->inDictionary());
86 MOZ_ASSERT(obj->shape_->listp == &obj->shape_);
87
88 if (parent)
89 parent->listp = listp;
90 *listp = parent;
91 listp = nullptr;
92
93 obj->shape_->clearCachedBigEnoughForShapeTable();
94 }
95
96 void
insertIntoDictionary(GCPtrShape * dictp)97 Shape::insertIntoDictionary(GCPtrShape* dictp)
98 {
99 // Don't assert inDictionaryMode() here because we may be called from
100 // JSObject::toDictionaryMode via JSObject::newDictionaryShape.
101 MOZ_ASSERT(inDictionary());
102 MOZ_ASSERT(!listp);
103
104 MOZ_ASSERT_IF(*dictp, (*dictp)->inDictionary());
105 MOZ_ASSERT_IF(*dictp, (*dictp)->listp == dictp);
106 MOZ_ASSERT_IF(*dictp, zone() == (*dictp)->zone());
107
108 setParent(dictp->get());
109 if (parent)
110 parent->listp = &parent;
111 listp = (GCPtrShape*) dictp;
112 *dictp = this;
113 }
114
115 bool
makeOwnBaseShape(ExclusiveContext * cx)116 Shape::makeOwnBaseShape(ExclusiveContext* cx)
117 {
118 MOZ_ASSERT(!base()->isOwned());
119 MOZ_ASSERT(cx->zone() == zone());
120
121 BaseShape* nbase = Allocate<BaseShape, NoGC>(cx);
122 if (!nbase)
123 return false;
124
125 new (nbase) BaseShape(StackBaseShape(this));
126 nbase->setOwned(base()->toUnowned());
127
128 this->base_ = nbase;
129
130 return true;
131 }
132
133 void
handoffTableTo(Shape * shape)134 Shape::handoffTableTo(Shape* shape)
135 {
136 MOZ_ASSERT(inDictionary() && shape->inDictionary());
137
138 if (this == shape)
139 return;
140
141 MOZ_ASSERT(base()->isOwned() && !shape->base()->isOwned());
142
143 BaseShape* nbase = base();
144
145 MOZ_ASSERT_IF(shape->hasSlot(), nbase->slotSpan() > shape->slot());
146
147 this->base_ = nbase->baseUnowned();
148 nbase->adoptUnowned(shape->base()->toUnowned());
149
150 shape->base_ = nbase;
151 }
152
153 /* static */ bool
hashify(ExclusiveContext * cx,Shape * shape)154 Shape::hashify(ExclusiveContext* cx, Shape* shape)
155 {
156 MOZ_ASSERT(!shape->hasTable());
157
158 if (!shape->ensureOwnBaseShape(cx))
159 return false;
160
161 ShapeTable* table = cx->new_<ShapeTable>(shape->entryCount());
162 if (!table)
163 return false;
164
165 if (!table->init(cx, shape)) {
166 js_free(table);
167 return false;
168 }
169
170 shape->base()->setTable(table);
171 return true;
172 }
173
174 /*
175 * Double hashing needs the second hash code to be relatively prime to table
176 * size, so we simply make hash2 odd.
177 */
178 static HashNumber
Hash1(HashNumber hash0,uint32_t shift)179 Hash1(HashNumber hash0, uint32_t shift)
180 {
181 return hash0 >> shift;
182 }
183
184 static HashNumber
Hash2(HashNumber hash0,uint32_t log2,uint32_t shift)185 Hash2(HashNumber hash0, uint32_t log2, uint32_t shift)
186 {
187 return ((hash0 << log2) >> shift) | 1;
188 }
189
190 template<MaybeAdding Adding>
191 ShapeTable::Entry&
searchUnchecked(jsid id)192 ShapeTable::searchUnchecked(jsid id)
193 {
194 MOZ_ASSERT(entries_);
195 MOZ_ASSERT(!JSID_IS_EMPTY(id));
196
197 /* Compute the primary hash address. */
198 HashNumber hash0 = HashId(id);
199 HashNumber hash1 = Hash1(hash0, hashShift_);
200 Entry* entry = &getEntry(hash1);
201
202 /* Miss: return space for a new entry. */
203 if (entry->isFree())
204 return *entry;
205
206 /* Hit: return entry. */
207 Shape* shape = entry->shape();
208 if (shape && shape->propidRaw() == id)
209 return *entry;
210
211 /* Collision: double hash. */
212 uint32_t sizeLog2 = HASH_BITS - hashShift_;
213 HashNumber hash2 = Hash2(hash0, sizeLog2, hashShift_);
214 uint32_t sizeMask = JS_BITMASK(sizeLog2);
215
216 /* Save the first removed entry pointer so we can recycle it if adding. */
217 Entry* firstRemoved;
218 if (Adding == MaybeAdding::Adding) {
219 if (entry->isRemoved()) {
220 firstRemoved = entry;
221 } else {
222 firstRemoved = nullptr;
223 if (!entry->hadCollision())
224 entry->flagCollision();
225 }
226 }
227
228 #ifdef DEBUG
229 bool collisionFlag = true;
230 if (!entry->isRemoved())
231 collisionFlag = entry->hadCollision();
232 #endif
233
234 while (true) {
235 hash1 -= hash2;
236 hash1 &= sizeMask;
237 entry = &getEntry(hash1);
238
239 if (entry->isFree())
240 return (Adding == MaybeAdding::Adding && firstRemoved) ? *firstRemoved : *entry;
241
242 shape = entry->shape();
243 if (shape && shape->propidRaw() == id) {
244 MOZ_ASSERT(collisionFlag);
245 return *entry;
246 }
247
248 if (Adding == MaybeAdding::Adding) {
249 if (entry->isRemoved()) {
250 if (!firstRemoved)
251 firstRemoved = entry;
252 } else {
253 if (!entry->hadCollision())
254 entry->flagCollision();
255 }
256 }
257
258 #ifdef DEBUG
259 if (!entry->isRemoved())
260 collisionFlag &= entry->hadCollision();
261 #endif
262 }
263
264 MOZ_CRASH("Shape::search failed to find an expected entry.");
265 }
266
267 template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::Adding>(jsid id);
268 template ShapeTable::Entry& ShapeTable::searchUnchecked<MaybeAdding::NotAdding>(jsid id);
269
270 bool
change(ExclusiveContext * cx,int log2Delta)271 ShapeTable::change(ExclusiveContext* cx, int log2Delta)
272 {
273 MOZ_ASSERT(entries_);
274 MOZ_ASSERT(-1 <= log2Delta && log2Delta <= 1);
275
276 /*
277 * Grow, shrink, or compress by changing this->entries_.
278 */
279 uint32_t oldLog2 = HASH_BITS - hashShift_;
280 uint32_t newLog2 = oldLog2 + log2Delta;
281 uint32_t oldSize = JS_BIT(oldLog2);
282 uint32_t newSize = JS_BIT(newLog2);
283 Entry* newTable = cx->maybe_pod_calloc<Entry>(newSize);
284 if (!newTable)
285 return false;
286
287 /* Now that we have newTable allocated, update members. */
288 MOZ_ASSERT(newLog2 <= HASH_BITS);
289 hashShift_ = HASH_BITS - newLog2;
290 removedCount_ = 0;
291 Entry* oldTable = entries_;
292 entries_ = newTable;
293
294 /* Copy only live entries, leaving removed and free ones behind. */
295 AutoCheckCannotGC nogc;
296 for (Entry* oldEntry = oldTable; oldSize != 0; oldEntry++) {
297 if (Shape* shape = oldEntry->shape()) {
298 Entry& entry = search<MaybeAdding::Adding>(shape->propid(), nogc);
299 MOZ_ASSERT(entry.isFree());
300 entry.setShape(shape);
301 }
302 oldSize--;
303 }
304
305 MOZ_ASSERT(capacity() == newSize);
306
307 /* Finally, free the old entries storage. */
308 js_free(oldTable);
309 return true;
310 }
311
312 bool
grow(ExclusiveContext * cx)313 ShapeTable::grow(ExclusiveContext* cx)
314 {
315 MOZ_ASSERT(needsToGrow());
316
317 uint32_t size = capacity();
318 int delta = removedCount_ < (size >> 2);
319
320 MOZ_ASSERT(entryCount_ + removedCount_ <= size - 1);
321
322 if (!change(cx, delta)) {
323 if (entryCount_ + removedCount_ == size - 1) {
324 ReportOutOfMemory(cx);
325 return false;
326 }
327 }
328
329 return true;
330 }
331
332 void
trace(JSTracer * trc)333 ShapeTable::trace(JSTracer* trc)
334 {
335 for (size_t i = 0; i < capacity(); i++) {
336 Entry& entry = getEntry(i);
337 Shape* shape = entry.shape();
338 if (shape) {
339 TraceManuallyBarrieredEdge(trc, &shape, "ShapeTable shape");
340 if (shape != entry.shape())
341 entry.setPreservingCollision(shape);
342 }
343 }
344 }
345
346 #ifdef JSGC_HASH_TABLE_CHECKS
347
348 void
checkAfterMovingGC()349 ShapeTable::checkAfterMovingGC()
350 {
351 for (size_t i = 0; i < capacity(); i++) {
352 Entry& entry = getEntry(i);
353 Shape* shape = entry.shape();
354 if (shape)
355 CheckGCThingAfterMovingGC(shape);
356 }
357 }
358
359 #endif
360
361 /* static */ Shape*
replaceLastProperty(ExclusiveContext * cx,StackBaseShape & base,TaggedProto proto,HandleShape shape)362 Shape::replaceLastProperty(ExclusiveContext* cx, StackBaseShape& base,
363 TaggedProto proto, HandleShape shape)
364 {
365 MOZ_ASSERT(!shape->inDictionary());
366
367 if (!shape->parent) {
368 /* Treat as resetting the initial property of the shape hierarchy. */
369 AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
370 return EmptyShape::getInitialShape(cx, base.clasp, proto, kind,
371 base.flags & BaseShape::OBJECT_FLAG_MASK);
372 }
373
374 UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
375 if (!nbase)
376 return nullptr;
377
378 Rooted<StackShape> child(cx, StackShape(shape));
379 child.setBase(nbase);
380
381 return cx->zone()->propertyTree.getChild(cx, shape->parent, child);
382 }
383
384 /*
385 * Get or create a property-tree or dictionary child property of |parent|,
386 * which must be lastProperty() if inDictionaryMode(), else parent must be
387 * one of lastProperty() or lastProperty()->parent.
388 */
389 /* static */ Shape*
getChildPropertyOnDictionary(ExclusiveContext * cx,HandleNativeObject obj,HandleShape parent,MutableHandle<StackShape> child)390 NativeObject::getChildPropertyOnDictionary(ExclusiveContext* cx, HandleNativeObject obj,
391 HandleShape parent, MutableHandle<StackShape> child)
392 {
393 /*
394 * Shared properties have no slot, but slot_ will reflect that of parent.
395 * Unshared properties allocate a slot here but may lose it due to a
396 * JS_ClearScope call.
397 */
398 if (!child.hasSlot()) {
399 child.setSlot(parent->maybeSlot());
400 } else {
401 if (child.hasMissingSlot()) {
402 uint32_t slot;
403 if (!allocSlot(cx, obj, &slot))
404 return nullptr;
405 child.setSlot(slot);
406 } else {
407 /*
408 * Slots can only be allocated out of order on objects in
409 * dictionary mode. Otherwise the child's slot must be after the
410 * parent's slot (if it has one), because slot number determines
411 * slot span for objects with that shape. Usually child slot
412 * *immediately* follows parent slot, but there may be a slot gap
413 * when the object uses some -- but not all -- of its reserved
414 * slots to store properties.
415 */
416 MOZ_ASSERT(obj->inDictionaryMode() ||
417 parent->hasMissingSlot() ||
418 child.slot() == parent->maybeSlot() + 1 ||
419 (parent->maybeSlot() + 1 < JSSLOT_FREE(obj->getClass()) &&
420 child.slot() == JSSLOT_FREE(obj->getClass())));
421 }
422 }
423
424 RootedShape shape(cx);
425
426 if (obj->inDictionaryMode()) {
427 MOZ_ASSERT(parent == obj->lastProperty());
428 shape = child.isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
429 if (!shape)
430 return nullptr;
431 if (child.hasSlot() && child.slot() >= obj->lastProperty()->base()->slotSpan()) {
432 if (!obj->setSlotSpan(cx, child.slot() + 1)) {
433 new (shape) Shape(obj->lastProperty()->base()->unowned(), 0);
434 return nullptr;
435 }
436 }
437 shape->initDictionaryShape(child, obj->numFixedSlots(), &obj->shape_);
438 }
439
440 return shape;
441 }
442
443 /* static */ Shape*
getChildProperty(ExclusiveContext * cx,HandleNativeObject obj,HandleShape parent,MutableHandle<StackShape> child)444 NativeObject::getChildProperty(ExclusiveContext* cx,
445 HandleNativeObject obj, HandleShape parent,
446 MutableHandle<StackShape> child)
447 {
448 Shape* shape = getChildPropertyOnDictionary(cx, obj, parent, child);
449
450 if (!obj->inDictionaryMode()) {
451 shape = cx->zone()->propertyTree.getChild(cx, parent, child);
452 if (!shape)
453 return nullptr;
454 //MOZ_ASSERT(shape->parent == parent);
455 //MOZ_ASSERT_IF(parent != lastProperty(), parent == lastProperty()->parent);
456 if (!obj->setLastProperty(cx, shape))
457 return nullptr;
458 }
459
460 return shape;
461 }
462
463 bool
toDictionaryMode(ExclusiveContext * cx)464 js::NativeObject::toDictionaryMode(ExclusiveContext* cx)
465 {
466 MOZ_ASSERT(!inDictionaryMode());
467 MOZ_ASSERT(cx->isInsideCurrentCompartment(this));
468
469 uint32_t span = slotSpan();
470
471 Rooted<NativeObject*> self(cx, this);
472
473 // Clone the shapes into a new dictionary list. Don't update the last
474 // property of this object until done, otherwise a GC triggered while
475 // creating the dictionary will get the wrong slot span for this object.
476 RootedShape root(cx);
477 RootedShape dictionaryShape(cx);
478
479 RootedShape shape(cx, lastProperty());
480 while (shape) {
481 MOZ_ASSERT(!shape->inDictionary());
482
483 Shape* dprop = shape->isAccessorShape() ? Allocate<AccessorShape>(cx) : Allocate<Shape>(cx);
484 if (!dprop) {
485 ReportOutOfMemory(cx);
486 return false;
487 }
488
489 GCPtrShape* listp = dictionaryShape ? &dictionaryShape->parent : nullptr;
490 StackShape child(shape);
491 dprop->initDictionaryShape(child, self->numFixedSlots(), listp);
492
493 if (!dictionaryShape)
494 root = dprop;
495
496 MOZ_ASSERT(!dprop->hasTable());
497 dictionaryShape = dprop;
498 shape = shape->previous();
499 }
500
501 if (!Shape::hashify(cx, root)) {
502 ReportOutOfMemory(cx);
503 return false;
504 }
505
506 if (IsInsideNursery(self) &&
507 !cx->asJSContext()->gc.nursery.queueDictionaryModeObjectToSweep(self))
508 {
509 ReportOutOfMemory(cx);
510 return false;
511 }
512
513 MOZ_ASSERT(root->listp == nullptr);
514 root->listp = &self->shape_;
515 self->shape_ = root;
516
517 MOZ_ASSERT(self->inDictionaryMode());
518 root->base()->setSlotSpan(span);
519
520 return true;
521 }
522
523 /* static */ Shape*
addProperty(ExclusiveContext * cx,HandleNativeObject obj,HandleId id,GetterOp getter,SetterOp setter,uint32_t slot,unsigned attrs,unsigned flags,bool allowDictionary)524 NativeObject::addProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleId id,
525 GetterOp getter, SetterOp setter, uint32_t slot, unsigned attrs,
526 unsigned flags, bool allowDictionary)
527 {
528 MOZ_ASSERT(!JSID_IS_VOID(id));
529 MOZ_ASSERT(getter != JS_PropertyStub);
530 MOZ_ASSERT(setter != JS_StrictPropertyStub);
531
532 bool extensible;
533 if (!IsExtensible(cx, obj, &extensible))
534 return nullptr;
535 if (!extensible) {
536 if (cx->isJSContext())
537 obj->reportNotExtensible(cx->asJSContext());
538 return nullptr;
539 }
540
541 AutoKeepShapeTables keep(cx);
542 ShapeTable::Entry* entry = nullptr;
543 if (obj->inDictionaryMode()) {
544 ShapeTable* table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
545 if (!table)
546 return nullptr;
547 entry = &table->search<MaybeAdding::Adding>(id, keep);
548 }
549
550 return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags, entry,
551 allowDictionary, keep);
552 }
553
554 static bool
ShouldConvertToDictionary(NativeObject * obj)555 ShouldConvertToDictionary(NativeObject* obj)
556 {
557 /*
558 * Use a lower limit if this object is likely a hashmap (SETELEM was used
559 * to set properties).
560 */
561 if (obj->hadElementsAccess())
562 return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT_WITH_ELEMENTS_ACCESS;
563 return obj->lastProperty()->entryCount() >= PropertyTree::MAX_HEIGHT;
564 }
565
566 /* static */ Shape*
addPropertyInternal(ExclusiveContext * cx,HandleNativeObject obj,HandleId id,GetterOp getter,SetterOp setter,uint32_t slot,unsigned attrs,unsigned flags,ShapeTable::Entry * entry,bool allowDictionary,const AutoKeepShapeTables & keep)567 NativeObject::addPropertyInternal(ExclusiveContext* cx,
568 HandleNativeObject obj, HandleId id,
569 GetterOp getter, SetterOp setter,
570 uint32_t slot, unsigned attrs,
571 unsigned flags, ShapeTable::Entry* entry,
572 bool allowDictionary, const AutoKeepShapeTables& keep)
573 {
574 MOZ_ASSERT_IF(!allowDictionary, !obj->inDictionaryMode());
575 MOZ_ASSERT(getter != JS_PropertyStub);
576 MOZ_ASSERT(setter != JS_StrictPropertyStub);
577
578 AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
579
580 /*
581 * The code below deals with either converting obj to dictionary mode or
582 * growing an object that's already in dictionary mode. Either way,
583 * dictionray operations are safe if thread local.
584 */
585 ShapeTable* table = nullptr;
586 if (!obj->inDictionaryMode()) {
587 bool stableSlot =
588 (slot == SHAPE_INVALID_SLOT) ||
589 obj->lastProperty()->hasMissingSlot() ||
590 (slot == obj->lastProperty()->maybeSlot() + 1);
591 MOZ_ASSERT_IF(!allowDictionary, stableSlot);
592 if (allowDictionary &&
593 (!stableSlot || ShouldConvertToDictionary(obj)))
594 {
595 if (!obj->toDictionaryMode(cx))
596 return nullptr;
597 table = obj->lastProperty()->maybeTable(keep);
598 entry = &table->search<MaybeAdding::Adding>(id, keep);
599 }
600 } else {
601 table = obj->lastProperty()->ensureTableForDictionary(cx, keep);
602 if (!table)
603 return nullptr;
604 if (table->needsToGrow()) {
605 if (!table->grow(cx))
606 return nullptr;
607 entry = &table->search<MaybeAdding::Adding>(id, keep);
608 MOZ_ASSERT(!entry->shape());
609 }
610 }
611
612 MOZ_ASSERT(!!table == !!entry);
613
614 /* Find or create a property tree node labeled by our arguments. */
615 RootedShape shape(cx);
616 {
617 RootedShape last(cx, obj->lastProperty());
618
619 uint32_t index;
620 bool indexed = IdIsIndex(id, &index);
621
622 Rooted<UnownedBaseShape*> nbase(cx);
623 if (!indexed) {
624 nbase = last->base()->unowned();
625 } else {
626 StackBaseShape base(last->base());
627 base.flags |= BaseShape::INDEXED;
628 nbase = BaseShape::getUnowned(cx, base);
629 if (!nbase)
630 return nullptr;
631 }
632
633 Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs, flags));
634 child.updateGetterSetter(getter, setter);
635 shape = getChildProperty(cx, obj, last, &child);
636 }
637
638 if (shape) {
639 MOZ_ASSERT(shape == obj->lastProperty());
640
641 if (table) {
642 /* Store the tree node pointer in the table entry for id. */
643 entry->setPreservingCollision(shape);
644 table->incEntryCount();
645
646 /* Pass the table along to the new last property, namely shape. */
647 MOZ_ASSERT(shape->parent->maybeTable(keep) == table);
648 shape->parent->handoffTableTo(shape);
649 }
650
651 obj->checkShapeConsistency();
652 return shape;
653 }
654
655 obj->checkShapeConsistency();
656 return nullptr;
657 }
658
659 Shape*
ReshapeForAllocKind(JSContext * cx,Shape * shape,TaggedProto proto,gc::AllocKind allocKind)660 js::ReshapeForAllocKind(JSContext* cx, Shape* shape, TaggedProto proto,
661 gc::AllocKind allocKind)
662 {
663 // Compute the number of fixed slots with the new allocation kind.
664 size_t nfixed = gc::GetGCKindSlots(allocKind, shape->getObjectClass());
665
666 // Get all the ids in the shape, in order.
667 js::AutoIdVector ids(cx);
668 {
669 for (unsigned i = 0; i < shape->slotSpan(); i++) {
670 if (!ids.append(JSID_VOID))
671 return nullptr;
672 }
673 Shape* nshape = shape;
674 while (!nshape->isEmptyShape()) {
675 ids[nshape->slot()].set(nshape->propid());
676 nshape = nshape->previous();
677 }
678 }
679
680 // Construct the new shape, without updating type information.
681 RootedId id(cx);
682 RootedShape newShape(cx, EmptyShape::getInitialShape(cx, shape->getObjectClass(),
683 proto, nfixed, shape->getObjectFlags()));
684 if (!newShape)
685 return nullptr;
686
687 for (unsigned i = 0; i < ids.length(); i++) {
688 id = ids[i];
689
690 uint32_t index;
691 bool indexed = IdIsIndex(id, &index);
692
693 Rooted<UnownedBaseShape*> nbase(cx, newShape->base()->unowned());
694 if (indexed) {
695 StackBaseShape base(nbase);
696 base.flags |= BaseShape::INDEXED;
697 nbase = BaseShape::getUnowned(cx, base);
698 if (!nbase)
699 return nullptr;
700 }
701
702 Rooted<StackShape> child(cx, StackShape(nbase, id, i, JSPROP_ENUMERATE, 0));
703 newShape = cx->zone()->propertyTree.getChild(cx, newShape, child);
704 if (!newShape)
705 return nullptr;
706 }
707
708 return newShape;
709 }
710
711 /*
712 * Check and adjust the new attributes for the shape to make sure that our
713 * slot access optimizations are sound. It is responsibility of the callers to
714 * enforce all restrictions from ECMA-262 v5 8.12.9 [[DefineOwnProperty]].
715 */
716 static inline bool
CheckCanChangeAttrs(ExclusiveContext * cx,JSObject * obj,Shape * shape,unsigned * attrsp)717 CheckCanChangeAttrs(ExclusiveContext* cx, JSObject* obj, Shape* shape, unsigned* attrsp)
718 {
719 if (shape->configurable())
720 return true;
721
722 /* A permanent property must stay permanent. */
723 *attrsp |= JSPROP_PERMANENT;
724
725 /* Reject attempts to remove a slot from the permanent data property. */
726 if (shape->isDataDescriptor() && shape->hasSlot() &&
727 (*attrsp & (JSPROP_GETTER | JSPROP_SETTER | JSPROP_SHARED)))
728 {
729 if (cx->isJSContext())
730 obj->reportNotConfigurable(cx->asJSContext(), shape->propid());
731 return false;
732 }
733
734 return true;
735 }
736
737 /* static */ Shape*
putProperty(ExclusiveContext * cx,HandleNativeObject obj,HandleId id,GetterOp getter,SetterOp setter,uint32_t slot,unsigned attrs,unsigned flags)738 NativeObject::putProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleId id,
739 GetterOp getter, SetterOp setter, uint32_t slot, unsigned attrs,
740 unsigned flags)
741 {
742 MOZ_ASSERT(!JSID_IS_VOID(id));
743 MOZ_ASSERT(getter != JS_PropertyStub);
744 MOZ_ASSERT(setter != JS_StrictPropertyStub);
745
746 #ifdef DEBUG
747 if (obj->is<ArrayObject>()) {
748 ArrayObject* arr = &obj->as<ArrayObject>();
749 uint32_t index;
750 if (IdIsIndex(id, &index))
751 MOZ_ASSERT(index < arr->length() || arr->lengthIsWritable());
752 }
753 #endif
754
755 AutoRooterGetterSetter gsRoot(cx, attrs, &getter, &setter);
756
757 /*
758 * Search for id in order to claim its entry if table has been allocated.
759 *
760 * Note that we can only try to claim an entry in a table that is thread
761 * local. An object may be thread local *without* its shape being thread
762 * local. The only thread local objects that *also* have thread local
763 * shapes are dictionaries that were allocated/converted thread
764 * locally. Only for those objects we can try to claim an entry in its
765 * shape table.
766 */
767 AutoKeepShapeTables keep(cx);
768 ShapeTable::Entry* entry;
769 RootedShape shape(cx);
770 if (!Shape::search<MaybeAdding::Adding>(cx, obj->lastProperty(), id, keep,
771 shape.address(), &entry))
772 {
773 return nullptr;
774 }
775
776 if (!shape) {
777 /*
778 * You can't add properties to a non-extensible object, but you can change
779 * attributes of properties in such objects.
780 */
781 bool extensible;
782
783 if (!IsExtensible(cx, obj, &extensible))
784 return nullptr;
785
786 if (!extensible) {
787 if (cx->isJSContext())
788 obj->reportNotExtensible(cx->asJSContext());
789 return nullptr;
790 }
791
792 return addPropertyInternal(cx, obj, id, getter, setter, slot, attrs, flags,
793 entry, true, keep);
794 }
795
796 /* Property exists: search must have returned a valid entry. */
797 MOZ_ASSERT_IF(entry, !entry->isRemoved());
798
799 if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
800 return nullptr;
801
802 /*
803 * If the caller wants to allocate a slot, but doesn't care which slot,
804 * copy the existing shape's slot into slot so we can match shape, if all
805 * other members match.
806 */
807 bool hadSlot = shape->hasSlot();
808 uint32_t oldSlot = shape->maybeSlot();
809 if (!(attrs & JSPROP_SHARED) && slot == SHAPE_INVALID_SLOT && hadSlot)
810 slot = oldSlot;
811
812 Rooted<UnownedBaseShape*> nbase(cx);
813 {
814 uint32_t index;
815 bool indexed = IdIsIndex(id, &index);
816 StackBaseShape base(obj->lastProperty()->base());
817 if (indexed)
818 base.flags |= BaseShape::INDEXED;
819 nbase = BaseShape::getUnowned(cx, base);
820 if (!nbase)
821 return nullptr;
822 }
823
824 /*
825 * Now that we've possibly preserved slot, check whether all members match.
826 * If so, this is a redundant "put" and we can return without more work.
827 */
828 if (shape->matchesParamsAfterId(nbase, slot, attrs, flags, getter, setter))
829 return shape;
830
831 /*
832 * Overwriting a non-last property requires switching to dictionary mode.
833 * The shape tree is shared immutable, and we can't removeProperty and then
834 * addPropertyInternal because a failure under add would lose data.
835 */
836 if (shape != obj->lastProperty() && !obj->inDictionaryMode()) {
837 if (!obj->toDictionaryMode(cx))
838 return nullptr;
839 ShapeTable* table = obj->lastProperty()->maybeTable(keep);
840 MOZ_ASSERT(table);
841 entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
842 shape = entry->shape();
843 }
844
845 MOZ_ASSERT_IF(shape->hasSlot() && !(attrs & JSPROP_SHARED), shape->slot() == slot);
846
847 if (obj->inDictionaryMode()) {
848 /*
849 * Updating some property in a dictionary-mode object. Create a new
850 * shape for the existing property, and also generate a new shape for
851 * the last property of the dictionary (unless the modified property
852 * is also the last property).
853 */
854 bool updateLast = (shape == obj->lastProperty());
855 bool accessorShape = getter || setter || (attrs & (JSPROP_GETTER | JSPROP_SETTER));
856 shape = obj->replaceWithNewEquivalentShape(cx, shape, nullptr, accessorShape);
857 if (!shape)
858 return nullptr;
859 if (!updateLast && !obj->generateOwnShape(cx))
860 return nullptr;
861
862 /*
863 * FIXME bug 593129 -- slot allocation and NativeObject *this must move
864 * out of here!
865 */
866 if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED)) {
867 if (!allocSlot(cx, obj, &slot))
868 return nullptr;
869 }
870
871 if (updateLast)
872 shape->base()->adoptUnowned(nbase);
873 else
874 shape->base_ = nbase;
875
876 MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
877
878 shape->setSlot(slot);
879 shape->attrs = uint8_t(attrs);
880 shape->flags = flags | Shape::IN_DICTIONARY | (accessorShape ? Shape::ACCESSOR_SHAPE : 0);
881 if (shape->isAccessorShape()) {
882 AccessorShape& accShape = shape->asAccessorShape();
883 accShape.rawGetter = getter;
884 accShape.rawSetter = setter;
885 GetterSetterWriteBarrierPost(&accShape);
886 } else {
887 MOZ_ASSERT(!getter);
888 MOZ_ASSERT(!setter);
889 }
890 } else {
891 /*
892 * Updating the last property in a non-dictionary-mode object. Find an
893 * alternate shared child of the last property's previous shape.
894 */
895 StackBaseShape base(obj->lastProperty()->base());
896
897 UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
898 if (!nbase)
899 return nullptr;
900
901 MOZ_ASSERT(shape == obj->lastProperty());
902
903 /* Find or create a property tree node labeled by our arguments. */
904 Rooted<StackShape> child(cx, StackShape(nbase, id, slot, attrs, flags));
905 child.updateGetterSetter(getter, setter);
906 RootedShape parent(cx, shape->parent);
907 Shape* newShape = getChildProperty(cx, obj, parent, &child);
908
909 if (!newShape) {
910 obj->checkShapeConsistency();
911 return nullptr;
912 }
913
914 shape = newShape;
915 }
916
917 /*
918 * Can't fail now, so free the previous incarnation's slot if the new shape
919 * has no slot. But we do not need to free oldSlot (and must not, as trying
920 * to will botch an assertion in JSObject::freeSlot) if the new last
921 * property (shape here) has a slotSpan that does not cover it.
922 */
923 if (hadSlot && !shape->hasSlot()) {
924 if (oldSlot < obj->slotSpan())
925 obj->freeSlot(cx, oldSlot);
926 /* Note: The optimization based on propertyRemovals is only relevant to the main thread. */
927 if (cx->isJSContext())
928 ++cx->asJSContext()->runtime()->propertyRemovals;
929 }
930
931 obj->checkShapeConsistency();
932
933 return shape;
934 }
935
936 /* static */ Shape*
changeProperty(ExclusiveContext * cx,HandleNativeObject obj,HandleShape shape,unsigned attrs,GetterOp getter,SetterOp setter)937 NativeObject::changeProperty(ExclusiveContext* cx, HandleNativeObject obj, HandleShape shape,
938 unsigned attrs, GetterOp getter, SetterOp setter)
939 {
940 MOZ_ASSERT(obj->containsPure(shape));
941 MOZ_ASSERT(getter != JS_PropertyStub);
942 MOZ_ASSERT(setter != JS_StrictPropertyStub);
943 MOZ_ASSERT_IF(attrs & (JSPROP_GETTER | JSPROP_SETTER), attrs & JSPROP_SHARED);
944
945 /* Allow only shared (slotless) => unshared (slotful) transition. */
946 MOZ_ASSERT(!((attrs ^ shape->attrs) & JSPROP_SHARED) ||
947 !(attrs & JSPROP_SHARED));
948
949 MarkTypePropertyNonData(cx, obj, shape->propid());
950
951 if (!CheckCanChangeAttrs(cx, obj, shape, &attrs))
952 return nullptr;
953
954 if (shape->attrs == attrs && shape->getter() == getter && shape->setter() == setter)
955 return shape;
956
957 /*
958 * Let JSObject::putProperty handle this |overwriting| case, including
959 * the conservation of shape->slot (if it's valid). We must not call
960 * removeProperty because it will free an allocated shape->slot, and
961 * putProperty won't re-allocate it.
962 */
963 RootedId propid(cx, shape->propid());
964 Shape* newShape = putProperty(cx, obj, propid, getter, setter,
965 shape->maybeSlot(), attrs, shape->flags);
966
967 obj->checkShapeConsistency();
968 return newShape;
969 }
970
971 bool
removeProperty(ExclusiveContext * cx,jsid id_)972 NativeObject::removeProperty(ExclusiveContext* cx, jsid id_)
973 {
974 RootedId id(cx, id_);
975 RootedNativeObject self(cx, this);
976
977 AutoKeepShapeTables keep(cx);
978 ShapeTable::Entry* entry;
979 RootedShape shape(cx);
980 if (!Shape::search(cx, lastProperty(), id, keep, shape.address(), &entry))
981 return false;
982
983 if (!shape)
984 return true;
985
986 /*
987 * If shape is not the last property added, or the last property cannot
988 * be removed, switch to dictionary mode.
989 */
990 if (!self->inDictionaryMode() && (shape != self->lastProperty() || !self->canRemoveLastProperty())) {
991 if (!self->toDictionaryMode(cx))
992 return false;
993 ShapeTable* table = self->lastProperty()->maybeTable(keep);
994 MOZ_ASSERT(table);
995 entry = &table->search<MaybeAdding::NotAdding>(shape->propid(), keep);
996 shape = entry->shape();
997 }
998
999 /*
1000 * If in dictionary mode, get a new shape for the last property after the
1001 * removal. We need a fresh shape for all dictionary deletions, even of
1002 * the last property. Otherwise, a shape could replay and caches might
1003 * return deleted DictionaryShapes! See bug 595365. Do this before changing
1004 * the object or table, so the remaining removal is infallible.
1005 */
1006 RootedShape spare(cx);
1007 if (self->inDictionaryMode()) {
1008 /* For simplicity, always allocate an accessor shape for now. */
1009 spare = Allocate<AccessorShape>(cx);
1010 if (!spare)
1011 return false;
1012 new (spare) Shape(shape->base()->unowned(), 0);
1013 if (shape == self->lastProperty()) {
1014 /*
1015 * Get an up to date unowned base shape for the new last property
1016 * when removing the dictionary's last property. Information in
1017 * base shapes for non-last properties may be out of sync with the
1018 * object's state.
1019 */
1020 RootedShape previous(cx, self->lastProperty()->parent);
1021 StackBaseShape base(self->lastProperty()->base());
1022 BaseShape* nbase = BaseShape::getUnowned(cx, base);
1023 if (!nbase)
1024 return false;
1025 previous->base_ = nbase;
1026 }
1027 }
1028
1029 /* If shape has a slot, free its slot number. */
1030 if (shape->hasSlot()) {
1031 self->freeSlot(cx, shape->slot());
1032 if (cx->isJSContext())
1033 ++cx->asJSContext()->runtime()->propertyRemovals;
1034 }
1035
1036 /*
1037 * A dictionary-mode object owns mutable, unique shapes on a non-circular
1038 * doubly linked list, hashed by lastProperty()->table. So we can edit the
1039 * list and hash in place.
1040 */
1041 if (self->inDictionaryMode()) {
1042 ShapeTable* table = self->lastProperty()->maybeTable(keep);
1043 MOZ_ASSERT(table);
1044
1045 if (entry->hadCollision()) {
1046 entry->setRemoved();
1047 table->decEntryCount();
1048 table->incRemovedCount();
1049 } else {
1050 entry->setFree();
1051 table->decEntryCount();
1052
1053 #ifdef DEBUG
1054 /*
1055 * Check the consistency of the table but limit the number of
1056 * checks not to alter significantly the complexity of the
1057 * delete in debug builds, see bug 534493.
1058 */
1059 Shape* aprop = self->lastProperty();
1060 for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent)
1061 MOZ_ASSERT_IF(aprop != shape, self->contains(cx, aprop));
1062 #endif
1063 }
1064
1065 {
1066 /* Remove shape from its non-circular doubly linked list. */
1067 Shape* oldLastProp = self->lastProperty();
1068 shape->removeFromDictionary(self);
1069
1070 /* Hand off table from the old to new last property. */
1071 oldLastProp->handoffTableTo(self->lastProperty());
1072 }
1073
1074 /* Generate a new shape for the object, infallibly. */
1075 JS_ALWAYS_TRUE(self->generateOwnShape(cx, spare));
1076
1077 /* Consider shrinking table if its load factor is <= .25. */
1078 uint32_t size = table->capacity();
1079 if (size > ShapeTable::MIN_SIZE && table->entryCount() <= size >> 2)
1080 (void) table->change(cx, -1);
1081 } else {
1082 /*
1083 * Non-dictionary-mode shape tables are shared immutables, so all we
1084 * need do is retract the last property and we'll either get or else
1085 * lazily make via a later hashify the exact table for the new property
1086 * lineage.
1087 */
1088 MOZ_ASSERT(shape == self->lastProperty());
1089 self->removeLastProperty(cx);
1090 }
1091
1092 self->checkShapeConsistency();
1093 return true;
1094 }
1095
1096 /* static */ void
clear(ExclusiveContext * cx,HandleNativeObject obj)1097 NativeObject::clear(ExclusiveContext* cx, HandleNativeObject obj)
1098 {
1099 Shape* shape = obj->lastProperty();
1100 MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
1101
1102 while (shape->parent) {
1103 shape = shape->parent;
1104 MOZ_ASSERT(obj->inDictionaryMode() == shape->inDictionary());
1105 }
1106 MOZ_ASSERT(shape->isEmptyShape());
1107
1108 if (obj->inDictionaryMode())
1109 shape->listp = &obj->shape_;
1110
1111 JS_ALWAYS_TRUE(obj->setLastProperty(cx, shape));
1112
1113 if (cx->isJSContext())
1114 ++cx->asJSContext()->runtime()->propertyRemovals;
1115 obj->checkShapeConsistency();
1116 }
1117
1118 /* static */ bool
rollbackProperties(ExclusiveContext * cx,HandleNativeObject obj,uint32_t slotSpan)1119 NativeObject::rollbackProperties(ExclusiveContext* cx, HandleNativeObject obj, uint32_t slotSpan)
1120 {
1121 /*
1122 * Remove properties from this object until it has a matching slot span.
1123 * The object cannot have escaped in a way which would prevent safe
1124 * removal of the last properties.
1125 */
1126 MOZ_ASSERT(!obj->inDictionaryMode() && slotSpan <= obj->slotSpan());
1127 while (true) {
1128 if (obj->lastProperty()->isEmptyShape()) {
1129 MOZ_ASSERT(slotSpan == 0);
1130 break;
1131 } else {
1132 uint32_t slot = obj->lastProperty()->slot();
1133 if (slot < slotSpan)
1134 break;
1135 }
1136 if (!obj->removeProperty(cx, obj->lastProperty()->propid()))
1137 return false;
1138 }
1139
1140 return true;
1141 }
1142
1143 Shape*
replaceWithNewEquivalentShape(ExclusiveContext * cx,Shape * oldShape,Shape * newShape,bool accessorShape)1144 NativeObject::replaceWithNewEquivalentShape(ExclusiveContext* cx, Shape* oldShape, Shape* newShape,
1145 bool accessorShape)
1146 {
1147 MOZ_ASSERT(cx->isInsideCurrentZone(oldShape));
1148 MOZ_ASSERT_IF(oldShape != lastProperty(),
1149 inDictionaryMode() && lookup(cx, oldShape->propidRef()) == oldShape);
1150
1151 NativeObject* self = this;
1152
1153 if (!inDictionaryMode()) {
1154 RootedNativeObject selfRoot(cx, self);
1155 RootedShape newRoot(cx, newShape);
1156 if (!toDictionaryMode(cx))
1157 return nullptr;
1158 oldShape = selfRoot->lastProperty();
1159 self = selfRoot;
1160 newShape = newRoot;
1161 }
1162
1163 if (!newShape) {
1164 RootedNativeObject selfRoot(cx, self);
1165 RootedShape oldRoot(cx, oldShape);
1166 newShape = (oldShape->isAccessorShape() || accessorShape)
1167 ? Allocate<AccessorShape>(cx)
1168 : Allocate<Shape>(cx);
1169 if (!newShape)
1170 return nullptr;
1171 new (newShape) Shape(oldRoot->base()->unowned(), 0);
1172 self = selfRoot;
1173 oldShape = oldRoot;
1174 }
1175
1176 AutoCheckCannotGC nogc;
1177 ShapeTable* table = self->lastProperty()->ensureTableForDictionary(cx, nogc);
1178 if (!table)
1179 return nullptr;
1180
1181 ShapeTable::Entry* entry = oldShape->isEmptyShape()
1182 ? nullptr
1183 : &table->search<MaybeAdding::NotAdding>(oldShape->propidRef(), nogc);
1184
1185 /*
1186 * Splice the new shape into the same position as the old shape, preserving
1187 * enumeration order (see bug 601399).
1188 */
1189 StackShape nshape(oldShape);
1190 newShape->initDictionaryShape(nshape, self->numFixedSlots(), oldShape->listp);
1191
1192 MOZ_ASSERT(newShape->parent == oldShape);
1193 oldShape->removeFromDictionary(self);
1194
1195 if (newShape == self->lastProperty())
1196 oldShape->handoffTableTo(newShape);
1197
1198 if (entry)
1199 entry->setPreservingCollision(newShape);
1200 return newShape;
1201 }
1202
1203 bool
shadowingShapeChange(ExclusiveContext * cx,const Shape & shape)1204 NativeObject::shadowingShapeChange(ExclusiveContext* cx, const Shape& shape)
1205 {
1206 return generateOwnShape(cx);
1207 }
1208
1209 bool
setFlags(ExclusiveContext * cx,BaseShape::Flag flags,GenerateShape generateShape)1210 JSObject::setFlags(ExclusiveContext* cx, BaseShape::Flag flags, GenerateShape generateShape)
1211 {
1212 if (hasAllFlags(flags))
1213 return true;
1214
1215 RootedObject self(cx, this);
1216
1217 Shape* existingShape = self->ensureShape(cx);
1218 if (!existingShape)
1219 return false;
1220
1221 if (isNative() && as<NativeObject>().inDictionaryMode()) {
1222 if (generateShape == GENERATE_SHAPE && !as<NativeObject>().generateOwnShape(cx))
1223 return false;
1224 StackBaseShape base(self->as<NativeObject>().lastProperty());
1225 base.flags |= flags;
1226 UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
1227 if (!nbase)
1228 return false;
1229
1230 self->as<NativeObject>().lastProperty()->base()->adoptUnowned(nbase);
1231 return true;
1232 }
1233
1234 Shape* newShape = Shape::setObjectFlags(cx, flags, self->taggedProto(), existingShape);
1235 if (!newShape)
1236 return false;
1237
1238 // The success of the |JSObject::ensureShape| call above means that |self|
1239 // can be assumed to have a shape.
1240 self->as<ShapedObject>().setShape(newShape);
1241
1242 return true;
1243 }
1244
1245 bool
clearFlag(ExclusiveContext * cx,BaseShape::Flag flag)1246 NativeObject::clearFlag(ExclusiveContext* cx, BaseShape::Flag flag)
1247 {
1248 MOZ_ASSERT(inDictionaryMode());
1249
1250 RootedNativeObject self(cx, &as<NativeObject>());
1251 MOZ_ASSERT(self->lastProperty()->getObjectFlags() & flag);
1252
1253 StackBaseShape base(self->lastProperty());
1254 base.flags &= ~flag;
1255 UnownedBaseShape* nbase = BaseShape::getUnowned(cx, base);
1256 if (!nbase)
1257 return false;
1258
1259 self->lastProperty()->base()->adoptUnowned(nbase);
1260 return true;
1261 }
1262
1263 /* static */ Shape*
setObjectFlags(ExclusiveContext * cx,BaseShape::Flag flags,TaggedProto proto,Shape * last)1264 Shape::setObjectFlags(ExclusiveContext* cx, BaseShape::Flag flags, TaggedProto proto, Shape* last)
1265 {
1266 if ((last->getObjectFlags() & flags) == flags)
1267 return last;
1268
1269 StackBaseShape base(last);
1270 base.flags |= flags;
1271
1272 RootedShape lastRoot(cx, last);
1273 return replaceLastProperty(cx, base, proto, lastRoot);
1274 }
1275
1276 /* static */ inline HashNumber
hash(const Lookup & lookup)1277 StackBaseShape::hash(const Lookup& lookup)
1278 {
1279 HashNumber hash = lookup.flags;
1280 hash = RotateLeft(hash, 4) ^ (uintptr_t(lookup.clasp) >> 3);
1281 return hash;
1282 }
1283
1284 /* static */ inline bool
match(ReadBarriered<UnownedBaseShape * > key,const Lookup & lookup)1285 StackBaseShape::match(ReadBarriered<UnownedBaseShape*> key, const Lookup& lookup)
1286 {
1287 return key.unbarrieredGet()->flags == lookup.flags &&
1288 key.unbarrieredGet()->clasp_ == lookup.clasp;
1289 }
1290
1291 inline
BaseShape(const StackBaseShape & base)1292 BaseShape::BaseShape(const StackBaseShape& base)
1293 : clasp_(base.clasp),
1294 flags(base.flags),
1295 slotSpan_(0),
1296 unowned_(nullptr),
1297 table_(nullptr)
1298 {
1299 }
1300
1301 /* static */ void
copyFromUnowned(BaseShape & dest,UnownedBaseShape & src)1302 BaseShape::copyFromUnowned(BaseShape& dest, UnownedBaseShape& src)
1303 {
1304 dest.clasp_ = src.clasp_;
1305 dest.slotSpan_ = src.slotSpan_;
1306 dest.unowned_ = &src;
1307 dest.flags = src.flags | OWNED_SHAPE;
1308 }
1309
1310 inline void
adoptUnowned(UnownedBaseShape * other)1311 BaseShape::adoptUnowned(UnownedBaseShape* other)
1312 {
1313 // This is a base shape owned by a dictionary object, update it to reflect the
1314 // unowned base shape of a new last property.
1315 MOZ_ASSERT(isOwned());
1316
1317 uint32_t span = slotSpan();
1318
1319 BaseShape::copyFromUnowned(*this, *other);
1320 setSlotSpan(span);
1321
1322 assertConsistency();
1323 }
1324
1325 /* static */ UnownedBaseShape*
getUnowned(ExclusiveContext * cx,StackBaseShape & base)1326 BaseShape::getUnowned(ExclusiveContext* cx, StackBaseShape& base)
1327 {
1328 auto& table = cx->zone()->baseShapes;
1329
1330 if (!table.initialized() && !table.init()) {
1331 ReportOutOfMemory(cx);
1332 return nullptr;
1333 }
1334
1335 auto p = MakeDependentAddPtr(cx, table, base);
1336 if (p)
1337 return *p;
1338
1339 BaseShape* nbase_ = Allocate<BaseShape>(cx);
1340 if (!nbase_)
1341 return nullptr;
1342
1343 new (nbase_) BaseShape(base);
1344
1345 UnownedBaseShape* nbase = static_cast<UnownedBaseShape*>(nbase_);
1346
1347 if (!p.add(cx, table, base, nbase))
1348 return nullptr;
1349
1350 return nbase;
1351 }
1352
1353 void
assertConsistency()1354 BaseShape::assertConsistency()
1355 {
1356 #ifdef DEBUG
1357 if (isOwned()) {
1358 UnownedBaseShape* unowned = baseUnowned();
1359 MOZ_ASSERT(getObjectFlags() == unowned->getObjectFlags());
1360 }
1361 #endif
1362 }
1363
1364 void
traceChildren(JSTracer * trc)1365 BaseShape::traceChildren(JSTracer* trc)
1366 {
1367 traceChildrenSkipShapeTable(trc);
1368 traceShapeTable(trc);
1369 }
1370
1371 void
traceChildrenSkipShapeTable(JSTracer * trc)1372 BaseShape::traceChildrenSkipShapeTable(JSTracer* trc)
1373 {
1374 if (isOwned())
1375 TraceEdge(trc, &unowned_, "base");
1376
1377 assertConsistency();
1378 }
1379
1380 void
traceShapeTable(JSTracer * trc)1381 BaseShape::traceShapeTable(JSTracer* trc)
1382 {
1383 AutoCheckCannotGC nogc;
1384 if (ShapeTable* table = maybeTable(nogc))
1385 table->trace(trc);
1386 }
1387
1388 #ifdef DEBUG
1389 bool
canSkipMarkingShapeTable(Shape * lastShape)1390 BaseShape::canSkipMarkingShapeTable(Shape* lastShape)
1391 {
1392 // Check that every shape in the shape table will be marked by marking
1393 // |lastShape|.
1394
1395 AutoCheckCannotGC nogc;
1396 ShapeTable* table = maybeTable(nogc);
1397 if (!table)
1398 return true;
1399
1400 uint32_t count = 0;
1401 for (Shape::Range<NoGC> r(lastShape); !r.empty(); r.popFront()) {
1402 Shape* shape = &r.front();
1403 ShapeTable::Entry& entry = table->search<MaybeAdding::NotAdding>(shape->propid(), nogc);
1404 if (entry.isLive())
1405 count++;
1406 }
1407
1408 return count == table->entryCount();
1409 }
1410 #endif
1411
1412 #ifdef JSGC_HASH_TABLE_CHECKS
1413
1414 void
checkBaseShapeTableAfterMovingGC()1415 Zone::checkBaseShapeTableAfterMovingGC()
1416 {
1417 if (!baseShapes.initialized())
1418 return;
1419
1420 for (decltype(baseShapes)::Enum e(baseShapes); !e.empty(); e.popFront()) {
1421 UnownedBaseShape* base = e.front().unbarrieredGet();
1422 CheckGCThingAfterMovingGC(base);
1423
1424 BaseShapeSet::Ptr ptr = baseShapes.lookup(base);
1425 MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
1426 }
1427 }
1428
1429 #endif // JSGC_HASH_TABLE_CHECKS
1430
1431 void
finalize(FreeOp * fop)1432 BaseShape::finalize(FreeOp* fop)
1433 {
1434 if (table_) {
1435 fop->delete_(table_);
1436 table_ = nullptr;
1437 }
1438 }
1439
1440 inline
InitialShapeEntry()1441 InitialShapeEntry::InitialShapeEntry() : shape(nullptr), proto()
1442 {
1443 }
1444
1445 inline
InitialShapeEntry(Shape * shape,const Lookup::ShapeProto & proto)1446 InitialShapeEntry::InitialShapeEntry(Shape* shape, const Lookup::ShapeProto& proto)
1447 : shape(shape), proto(proto)
1448 {
1449 }
1450
1451 /* static */ inline HashNumber
hash(const Lookup & lookup)1452 InitialShapeEntry::hash(const Lookup& lookup)
1453 {
1454 return (RotateLeft(uintptr_t(lookup.clasp) >> 3, 4) ^ lookup.proto.hashCode()) +
1455 lookup.nfixed;
1456 }
1457
1458 /* static */ inline bool
match(const InitialShapeEntry & key,const Lookup & lookup)1459 InitialShapeEntry::match(const InitialShapeEntry& key, const Lookup& lookup)
1460 {
1461 const Shape* shape = key.shape.unbarrieredGet();
1462 return lookup.clasp == shape->getObjectClass()
1463 && lookup.nfixed == shape->numFixedSlots()
1464 && lookup.baseFlags == shape->getObjectFlags()
1465 && lookup.proto.match(key.proto);
1466 }
1467
1468 #ifdef JSGC_HASH_TABLE_CHECKS
1469
1470 void
checkInitialShapesTableAfterMovingGC()1471 Zone::checkInitialShapesTableAfterMovingGC()
1472 {
1473 if (!initialShapes.initialized())
1474 return;
1475
1476 /*
1477 * Assert that the postbarriers have worked and that nothing is left in
1478 * initialShapes that points into the nursery, and that the hash table
1479 * entries are discoverable.
1480 */
1481 for (decltype(initialShapes)::Enum e(initialShapes); !e.empty(); e.popFront()) {
1482 InitialShapeEntry entry = e.front();
1483 JSProtoKey protoKey = entry.proto.key();
1484 TaggedProto proto = entry.proto.proto().unbarrieredGet();
1485 Shape* shape = entry.shape.unbarrieredGet();
1486
1487 CheckGCThingAfterMovingGC(shape);
1488 if (proto.isObject())
1489 CheckGCThingAfterMovingGC(proto.toObject());
1490
1491 using Lookup = InitialShapeEntry::Lookup;
1492 Lookup lookup(shape->getObjectClass(),
1493 Lookup::ShapeProto(protoKey, proto),
1494 shape->numFixedSlots(),
1495 shape->getObjectFlags());
1496 InitialShapeSet::Ptr ptr = initialShapes.lookup(lookup);
1497 MOZ_RELEASE_ASSERT(ptr.found() && &*ptr == &e.front());
1498 }
1499 }
1500
1501 #endif // JSGC_HASH_TABLE_CHECKS
1502
1503 Shape*
new_(ExclusiveContext * cx,Handle<UnownedBaseShape * > base,uint32_t nfixed)1504 EmptyShape::new_(ExclusiveContext* cx, Handle<UnownedBaseShape*> base, uint32_t nfixed)
1505 {
1506 Shape* shape = Allocate<Shape>(cx);
1507 if (!shape) {
1508 ReportOutOfMemory(cx);
1509 return nullptr;
1510 }
1511
1512 new (shape) EmptyShape(base, nfixed);
1513 return shape;
1514 }
1515
1516 static bool
IsOriginalProto(GlobalObject * global,JSProtoKey key,JSObject & proto)1517 IsOriginalProto(GlobalObject* global, JSProtoKey key, JSObject& proto)
1518 {
1519 if (global->getPrototype(key) != ObjectValue(proto))
1520 return false;
1521
1522 if (key == JSProto_Object) {
1523 MOZ_ASSERT(proto.staticPrototypeIsImmutable(),
1524 "proto should be Object.prototype, whose prototype is "
1525 "immutable");
1526 MOZ_ASSERT(proto.staticPrototype() == nullptr,
1527 "Object.prototype must have null prototype");
1528 return true;
1529 }
1530
1531 // Check that other prototypes still have Object.prototype as proto.
1532 JSObject* protoProto = proto.staticPrototype();
1533 if (!protoProto || global->getPrototype(JSProto_Object) != ObjectValue(*protoProto))
1534 return false;
1535
1536 MOZ_ASSERT(protoProto->staticPrototypeIsImmutable(),
1537 "protoProto should be Object.prototype, whose prototype is "
1538 "immutable");
1539 MOZ_ASSERT(protoProto->staticPrototype() == nullptr,
1540 "Object.prototype must have null prototype");
1541 return true;
1542 }
1543
1544 static JSProtoKey
GetInitialShapeProtoKey(TaggedProto proto,ExclusiveContext * cx)1545 GetInitialShapeProtoKey(TaggedProto proto, ExclusiveContext* cx)
1546 {
1547 if (proto.isObject() && proto.toObject()->hasStaticPrototype()) {
1548 GlobalObject* global = cx->global();
1549 JSObject& obj = *proto.toObject();
1550 MOZ_ASSERT(global == &obj.global());
1551
1552 if (IsOriginalProto(global, JSProto_Object, obj))
1553 return JSProto_Object;
1554 if (IsOriginalProto(global, JSProto_Function, obj))
1555 return JSProto_Function;
1556 if (IsOriginalProto(global, JSProto_Array, obj))
1557 return JSProto_Array;
1558 if (IsOriginalProto(global, JSProto_RegExp, obj))
1559 return JSProto_RegExp;
1560 }
1561 return JSProto_LIMIT;
1562 }
1563
1564 /* static */ Shape*
getInitialShape(ExclusiveContext * cx,const Class * clasp,TaggedProto proto,size_t nfixed,uint32_t objectFlags)1565 EmptyShape::getInitialShape(ExclusiveContext* cx, const Class* clasp, TaggedProto proto,
1566 size_t nfixed, uint32_t objectFlags)
1567 {
1568 MOZ_ASSERT_IF(proto.isObject(), cx->isInsideCurrentCompartment(proto.toObject()));
1569
1570 auto& table = cx->zone()->initialShapes;
1571
1572 if (!table.initialized() && !table.init()) {
1573 ReportOutOfMemory(cx);
1574 return nullptr;
1575 }
1576
1577 using Lookup = InitialShapeEntry::Lookup;
1578 auto protoPointer = MakeDependentAddPtr(cx, table,
1579 Lookup(clasp, Lookup::ShapeProto(proto),
1580 nfixed, objectFlags));
1581 if (protoPointer)
1582 return protoPointer->shape;
1583
1584 // No entry for this proto. If the proto is one of a few common builtin
1585 // prototypes, try to do a lookup based on the JSProtoKey, so we can share
1586 // shapes across globals.
1587 Rooted<TaggedProto> protoRoot(cx, proto);
1588 Shape* shape = nullptr;
1589 bool insertKey = false;
1590 mozilla::Maybe<DependentAddPtr<decltype(cx->zone()->initialShapes)>> keyPointer;
1591
1592 JSProtoKey key = GetInitialShapeProtoKey(protoRoot, cx);
1593 if (key != JSProto_LIMIT) {
1594 keyPointer.emplace(MakeDependentAddPtr(cx, table,
1595 Lookup(clasp, Lookup::ShapeProto(key),
1596 nfixed, objectFlags)));
1597 if (keyPointer.ref()) {
1598 shape = keyPointer.ref()->shape;
1599 MOZ_ASSERT(shape);
1600 } else {
1601 insertKey = true;
1602 }
1603 }
1604
1605 if (!shape) {
1606 StackBaseShape base(cx, clasp, objectFlags);
1607 Rooted<UnownedBaseShape*> nbase(cx, BaseShape::getUnowned(cx, base));
1608 if (!nbase)
1609 return nullptr;
1610
1611 shape = EmptyShape::new_(cx, nbase, nfixed);
1612 if (!shape)
1613 return nullptr;
1614 }
1615
1616 Lookup::ShapeProto shapeProto(protoRoot);
1617 Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
1618 if (!protoPointer.add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
1619 return nullptr;
1620
1621 // Also add an entry based on the JSProtoKey, if needed.
1622 if (insertKey) {
1623 Lookup::ShapeProto shapeProto(key);
1624 Lookup lookup(clasp, shapeProto, nfixed, objectFlags);
1625 if (!keyPointer->add(cx, table, lookup, InitialShapeEntry(shape, shapeProto)))
1626 return nullptr;
1627 }
1628
1629 return shape;
1630 }
1631
1632 /* static */ Shape*
getInitialShape(ExclusiveContext * cx,const Class * clasp,TaggedProto proto,AllocKind kind,uint32_t objectFlags)1633 EmptyShape::getInitialShape(ExclusiveContext* cx, const Class* clasp, TaggedProto proto,
1634 AllocKind kind, uint32_t objectFlags)
1635 {
1636 return getInitialShape(cx, clasp, proto, GetGCKindSlots(kind, clasp), objectFlags);
1637 }
1638
1639 void
invalidateEntriesForShape(JSContext * cx,HandleShape shape,HandleObject proto)1640 NewObjectCache::invalidateEntriesForShape(JSContext* cx, HandleShape shape, HandleObject proto)
1641 {
1642 const Class* clasp = shape->getObjectClass();
1643
1644 gc::AllocKind kind = gc::GetGCObjectKind(shape->numFixedSlots());
1645 if (CanBeFinalizedInBackground(kind, clasp))
1646 kind = GetBackgroundAllocKind(kind);
1647
1648 RootedObjectGroup group(cx, ObjectGroup::defaultNewGroup(cx, clasp, TaggedProto(proto)));
1649 if (!group) {
1650 purge();
1651 cx->recoverFromOutOfMemory();
1652 return;
1653 }
1654
1655 EntryIndex entry;
1656 for (CompartmentsInZoneIter comp(shape->zone()); !comp.done(); comp.next()) {
1657 if (GlobalObject* global = comp->unsafeUnbarrieredMaybeGlobal()) {
1658 if (lookupGlobal(clasp, global, kind, &entry))
1659 PodZero(&entries[entry]);
1660 }
1661 }
1662 if (!proto->is<GlobalObject>() && lookupProto(clasp, proto, kind, &entry))
1663 PodZero(&entries[entry]);
1664 if (lookupGroup(group, kind, &entry))
1665 PodZero(&entries[entry]);
1666 }
1667
1668 /* static */ void
insertInitialShape(ExclusiveContext * cx,HandleShape shape,HandleObject proto)1669 EmptyShape::insertInitialShape(ExclusiveContext* cx, HandleShape shape, HandleObject proto)
1670 {
1671 using Lookup = InitialShapeEntry::Lookup;
1672 Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(TaggedProto(proto)),
1673 shape->numFixedSlots(), shape->getObjectFlags());
1674
1675 InitialShapeSet::Ptr p = cx->zone()->initialShapes.lookup(lookup);
1676 MOZ_ASSERT(p);
1677
1678 InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
1679
1680 // The metadata callback can end up causing redundant changes of the initial shape.
1681 if (entry.shape == shape)
1682 return;
1683
1684 // The new shape had better be rooted at the old one.
1685 #ifdef DEBUG
1686 Shape* nshape = shape;
1687 while (!nshape->isEmptyShape())
1688 nshape = nshape->previous();
1689 MOZ_ASSERT(nshape == entry.shape);
1690 #endif
1691
1692 entry.shape = ReadBarrieredShape(shape);
1693
1694 // For certain prototypes -- namely, those of various builtin classes,
1695 // keyed by JSProtoKey |key| -- there are two entries: one for a lookup
1696 // via |proto|, and one for a lookup via |key|. If this is such a
1697 // prototype, also update the alternate |key|-keyed shape.
1698 JSProtoKey key = GetInitialShapeProtoKey(TaggedProto(proto), cx);
1699 if (key != JSProto_LIMIT) {
1700 Lookup lookup(shape->getObjectClass(), Lookup::ShapeProto(key),
1701 shape->numFixedSlots(), shape->getObjectFlags());
1702 if (InitialShapeSet::Ptr p = cx->zone()->initialShapes.lookup(lookup)) {
1703 InitialShapeEntry& entry = const_cast<InitialShapeEntry&>(*p);
1704 if (entry.shape != shape)
1705 entry.shape = ReadBarrieredShape(shape);
1706 }
1707 }
1708
1709 /*
1710 * This affects the shape that will be produced by the various NewObject
1711 * methods, so clear any cache entry referring to the old shape. This is
1712 * not required for correctness: the NewObject must always check for a
1713 * nativeEmpty() result and generate the appropriate properties if found.
1714 * Clearing the cache entry avoids this duplicate regeneration.
1715 *
1716 * Clearing is not necessary when this context is running off the main
1717 * thread, as it will not use the new object cache for allocations.
1718 */
1719 if (cx->isJSContext()) {
1720 JSContext* ncx = cx->asJSContext();
1721 ncx->caches.newObjectCache.invalidateEntriesForShape(ncx, shape, proto);
1722 }
1723 }
1724
1725 void
fixupInitialShapeTable()1726 Zone::fixupInitialShapeTable()
1727 {
1728 if (!initialShapes.initialized())
1729 return;
1730
1731 for (decltype(initialShapes)::Enum e(initialShapes); !e.empty(); e.popFront()) {
1732 // The shape may have been moved, but we can update that in place.
1733 Shape* shape = e.front().shape.unbarrieredGet();
1734 if (IsForwarded(shape)) {
1735 shape = Forwarded(shape);
1736 e.mutableFront().shape.set(shape);
1737 }
1738 shape->updateBaseShapeAfterMovingGC();
1739
1740 // If the prototype has moved we have to rekey the entry.
1741 InitialShapeEntry entry = e.front();
1742 if (entry.proto.proto().isObject() && IsForwarded(entry.proto.proto().toObject())) {
1743 entry.proto.setProto(TaggedProto(Forwarded(entry.proto.proto().toObject())));
1744 using Lookup = InitialShapeEntry::Lookup;
1745 Lookup relookup(shape->getObjectClass(),
1746 Lookup::ShapeProto(entry.proto),
1747 shape->numFixedSlots(),
1748 shape->getObjectFlags());
1749 e.rekeyFront(relookup, entry);
1750 }
1751 }
1752 }
1753
1754 void
trace(JSTracer * trc)1755 AutoRooterGetterSetter::Inner::trace(JSTracer* trc)
1756 {
1757 if ((attrs & JSPROP_GETTER) && *pgetter)
1758 TraceRoot(trc, (JSObject**) pgetter, "AutoRooterGetterSetter getter");
1759 if ((attrs & JSPROP_SETTER) && *psetter)
1760 TraceRoot(trc, (JSObject**) psetter, "AutoRooterGetterSetter setter");
1761 }
1762
1763 JS::ubi::Node::Size
size(mozilla::MallocSizeOf mallocSizeOf) const1764 JS::ubi::Concrete<js::Shape>::size(mozilla::MallocSizeOf mallocSizeOf) const
1765 {
1766 Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1767
1768 AutoCheckCannotGC nogc;
1769 if (ShapeTable* table = get().maybeTable(nogc))
1770 size += table->sizeOfIncludingThis(mallocSizeOf);
1771
1772 if (!get().inDictionary() && get().kids.isHash())
1773 size += get().kids.toHash()->sizeOfIncludingThis(mallocSizeOf);
1774
1775 return size;
1776 }
1777
1778 JS::ubi::Node::Size
size(mozilla::MallocSizeOf mallocSizeOf) const1779 JS::ubi::Concrete<js::BaseShape>::size(mozilla::MallocSizeOf mallocSizeOf) const
1780 {
1781 return js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1782 }
1783