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