js/src/vm/PropMap.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "vm/PropMap-inl.h"
   8
   9 #include "gc/HashUtil.h"
  10 #include "js/GCVector.h"
  11 #include "vm/JSObject.h"
  12
  13 #include "gc/GCContext-inl.h"
  14 #include "gc/Marking-inl.h"
  15 #include "vm/JSContext-inl.h"
  16 #include "vm/ObjectFlags-inl.h"
  17
  18 using namespace js;
  19
  20 void PropMap::addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
  21                                      size_t* children, size_t* tables) const {
  22   if (isShared() && asShared()->hasChildrenSet()) {
  23     auto* set = asShared()->treeDataRef().children.toChildrenSet();
  24     *children += set->shallowSizeOfIncludingThis(mallocSizeOf);
  25   }
  26   if (canHaveTable() && asLinked()->hasTable()) {
  27     *tables += asLinked()->data_.table->sizeOfIncludingThis(mallocSizeOf);
  28   }
  29 }
  30
  31 // static
  32 SharedPropMap* SharedPropMap::create(JSContext* cx, Handle<SharedPropMap*> prev,
  33                                      HandleId id, PropertyInfo prop) {
  34   // If the first property has a slot number <= MaxSlotNumber, all properties
  35   // added later will have a slot number <= CompactPropertyInfo::MaxSlotNumber
  36   // so we can use a CompactPropMap.
  37   static constexpr size_t MaxFirstSlot =
  38       CompactPropertyInfo::MaxSlotNumber - (PropMap::Capacity - 1);
  39
  40   if (!prev && prop.maybeSlot() <= MaxFirstSlot) {
  41     return cx->newCell<CompactPropMap>(id, prop);
  42   }
  43
  44   return cx->newCell<NormalPropMap>(prev, id, prop);
  45 }
  46
  47 // static
  48 SharedPropMap* SharedPropMap::createInitial(JSContext* cx, HandleId id,
  49                                             PropertyInfo prop) {
  50   // Lookup or create a shared map based on the first property.
  51
  52   using Lookup = InitialPropMapHasher::Lookup;
  53
  54   auto& table = cx->zone()->shapeZone().initialPropMaps;
  55
  56   auto p = MakeDependentAddPtr(cx, table, Lookup(id, prop));
  57   if (p) {
  58     return *p;
  59   }
  60
  61   SharedPropMap* result = create(cx, /* prev = */ nullptr, id, prop);
  62   if (!result) {
  63     return nullptr;
  64   }
  65
  66   Lookup lookup(id, prop);
  67   if (!p.add(cx, table, lookup, result)) {
  68     return nullptr;
  69   }
  70
  71   return result;
  72 }
  73
  74 // static
  75 SharedPropMap* SharedPropMap::clone(JSContext* cx, Handle<SharedPropMap*> map,
  76                                     uint32_t length) {
  77   MOZ_ASSERT(length > 0);
  78
  79   if (map->isCompact()) {
  80     Rooted<CompactPropMap*> prev(cx, map->asCompact());
  81     return cx->newCell<CompactPropMap>(prev, length);
  82   }
  83
  84   Rooted<NormalPropMap*> prev(cx, map->asNormal());
  85   return cx->newCell<NormalPropMap>(prev, length);
  86 }
  87
  88 // static
  89 DictionaryPropMap* SharedPropMap::toDictionaryMap(JSContext* cx,
  90                                                   Handle<SharedPropMap*> map,
  91                                                   uint32_t length) {
  92   // Starting at the last map, clone each shared map to a new dictionary map.
  93
  94   Rooted<DictionaryPropMap*> lastDictMap(cx);
  95   Rooted<DictionaryPropMap*> nextDictMap(cx);
  96
  97   Rooted<SharedPropMap*> sharedMap(cx, map);
  98   uint32_t sharedLength = length;
  99   while (true) {
 100     sharedMap->setHadDictionaryConversion();
 101
 102     DictionaryPropMap* dictMap;
 103     if (sharedMap->isCompact()) {
 104       Rooted<CompactPropMap*> prev(cx, sharedMap->asCompact());
 105       dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength);
 106     } else {
 107       Rooted<NormalPropMap*> prev(cx, sharedMap->asNormal());
 108       dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength);
 109     }
 110     if (!dictMap) {
 111       return nullptr;
 112     }
 113
 114     if (!lastDictMap) {
 115       lastDictMap = dictMap;
 116     }
 117
 118     if (nextDictMap) {
 119       nextDictMap->initPrevious(dictMap);
 120     }
 121     nextDictMap = dictMap;
 122
 123     if (!sharedMap->hasPrevious()) {
 124       break;
 125     }
 126     sharedMap = sharedMap->asNormal()->previous();
 127     sharedLength = PropMap::Capacity;
 128   }
 129
 130   return lastDictMap;
 131 }
 132
 133 static MOZ_ALWAYS_INLINE SharedPropMap* PropMapChildReadBarrier(
 134     SharedPropMap* parent, SharedPropMap* child) {
 135   JS::Zone* zone = child->zone();
 136   if (zone->needsIncrementalBarrier()) {
 137     // We need a read barrier for the map tree, since these are weak
 138     // pointers.
 139     ReadBarrier(child);
 140     return child;
 141   }
 142
 143   if (MOZ_UNLIKELY(zone->isGCSweeping() &&
 144                    IsAboutToBeFinalizedUnbarriered(child))) {
 145     // The map we've found is unreachable and due to be finalized, so
 146     // remove our weak reference to it and don't use it.
 147     MOZ_ASSERT(parent->isMarkedAny());
 148     parent->removeChild(zone->runtimeFromMainThread()->gcContext(), child);
 149     return nullptr;
 150   }
 151
 152   // We don't yield to the mutator when the zone is in this state so we don't
 153   // need to account for it here.
 154   MOZ_ASSERT(!zone->isGCCompacting());
 155
 156   return child;
 157 }
 158
 159 SharedPropMap* SharedPropMap::lookupChild(uint32_t length, HandleId id,
 160                                           PropertyInfo prop) {
 161   MOZ_ASSERT(length > 0);
 162
 163   SharedChildrenPtr children = treeDataRef().children;
 164   if (children.isNone()) {
 165     return nullptr;
 166   }
 167
 168   if (!hasChildrenSet()) {
 169     SharedPropMapAndIndex prevChild = children.toSingleChild();
 170     if (prevChild.index() == length - 1) {
 171       SharedPropMap* child = prevChild.map();
 172       uint32_t newPropIndex = indexOfNextProperty(length - 1);
 173       if (child->matchProperty(newPropIndex, id, prop)) {
 174         return PropMapChildReadBarrier(this, child);
 175       }
 176     }
 177     return nullptr;
 178   }
 179
 180   SharedChildrenSet* set = children.toChildrenSet();
 181   SharedChildrenHasher::Lookup lookup(id, prop, length - 1);
 182   if (auto p = set->lookup(lookup)) {
 183     MOZ_ASSERT(p->index() == length - 1);
 184     SharedPropMap* child = p->map();
 185     return PropMapChildReadBarrier(this, child);
 186   }
 187   return nullptr;
 188 }
 189
 190 bool SharedPropMap::addChild(JSContext* cx, SharedPropMapAndIndex child,
 191                              HandleId id, PropertyInfo prop) {
 192   SharedPropMap* childMap = child.map();
 193
 194 #ifdef DEBUG
 195   // If the parent map was full, the child map must have the parent as
 196   // |previous| map. Else, the parent and child have the same |previous| map.
 197   if (childMap->hasPrevious()) {
 198     if (child.index() == PropMap::Capacity - 1) {
 199       MOZ_ASSERT(childMap->asLinked()->previous() == this);
 200     } else {
 201       MOZ_ASSERT(childMap->asLinked()->previous() == asLinked()->previous());
 202     }
 203   } else {
 204     MOZ_ASSERT(!hasPrevious());
 205   }
 206 #endif
 207
 208   SharedChildrenPtr& childrenRef = treeDataRef().children;
 209
 210   if (childrenRef.isNone()) {
 211     childrenRef.setSingleChild(child);
 212     childMap->treeDataRef().setParent(this, child.index());
 213     return true;
 214   }
 215
 216   SharedChildrenHasher::Lookup lookup(id, prop, child.index());
 217
 218   if (hasChildrenSet()) {
 219     if (!childrenRef.toChildrenSet()->putNew(lookup, child)) {
 220       ReportOutOfMemory(cx);
 221       return false;
 222     }
 223   } else {
 224     auto hash = MakeUnique<SharedChildrenSet>();
 225     if (!hash || !hash->reserve(2)) {
 226       ReportOutOfMemory(cx);
 227       return false;
 228     }
 229     SharedPropMapAndIndex firstChild = childrenRef.toSingleChild();
 230     SharedPropMap* firstChildMap = firstChild.map();
 231     uint32_t firstChildIndex = indexOfNextProperty(firstChild.index());
 232     SharedChildrenHasher::Lookup lookupFirst(
 233         firstChildMap->getPropertyInfoWithKey(firstChildIndex),
 234         firstChild.index());
 235     hash->putNewInfallible(lookupFirst, firstChild);
 236     hash->putNewInfallible(lookup, child);
 237
 238     childrenRef.setChildrenSet(hash.release());
 239     setHasChildrenSet();
 240     AddCellMemory(this, sizeof(SharedChildrenSet), MemoryUse::PropMapChildren);
 241   }
 242
 243   childMap->treeDataRef().setParent(this, child.index());
 244   return true;
 245 }
 246
 247 // static
 248 bool SharedPropMap::addProperty(JSContext* cx, const JSClass* clasp,
 249                                 MutableHandle<SharedPropMap*> map,
 250                                 uint32_t* mapLength, HandleId id,
 251                                 PropertyFlags flags, ObjectFlags* objectFlags,
 252                                 uint32_t* slot) {
 253   MOZ_ASSERT(!flags.isCustomDataProperty());
 254
 255   *slot = SharedPropMap::slotSpan(clasp, map, *mapLength);
 256
 257   if (MOZ_UNLIKELY(*slot > SHAPE_MAXIMUM_SLOT)) {
 258     ReportAllocationOverflow(cx);
 259     return false;
 260   }
 261
 262   *objectFlags =
 263       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 264
 265   PropertyInfo prop = PropertyInfo(flags, *slot);
 266   return addPropertyInternal(cx, map, mapLength, id, prop);
 267 }
 268
 269 // static
 270 bool SharedPropMap::addPropertyInReservedSlot(
 271     JSContext* cx, const JSClass* clasp, MutableHandle<SharedPropMap*> map,
 272     uint32_t* mapLength, HandleId id, PropertyFlags flags, uint32_t slot,
 273     ObjectFlags* objectFlags) {
 274   MOZ_ASSERT(!flags.isCustomDataProperty());
 275
 276   MOZ_ASSERT(slot < JSCLASS_RESERVED_SLOTS(clasp));
 277   MOZ_ASSERT_IF(map, map->lastUsedSlot(*mapLength) < slot);
 278
 279   *objectFlags =
 280       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 281
 282   PropertyInfo prop = PropertyInfo(flags, slot);
 283   return addPropertyInternal(cx, map, mapLength, id, prop);
 284 }
 285
 286 // static
 287 bool SharedPropMap::addPropertyWithKnownSlot(JSContext* cx,
 288                                              const JSClass* clasp,
 289                                              MutableHandle<SharedPropMap*> map,
 290                                              uint32_t* mapLength, HandleId id,
 291                                              PropertyFlags flags, uint32_t slot,
 292                                              ObjectFlags* objectFlags) {
 293   MOZ_ASSERT(!flags.isCustomDataProperty());
 294
 295   if (MOZ_UNLIKELY(slot < JSCLASS_RESERVED_SLOTS(clasp))) {
 296     return addPropertyInReservedSlot(cx, clasp, map, mapLength, id, flags, slot,
 297                                      objectFlags);
 298   }
 299
 300   MOZ_ASSERT(slot == SharedPropMap::slotSpan(clasp, map, *mapLength));
 301   MOZ_RELEASE_ASSERT(slot <= SHAPE_MAXIMUM_SLOT);
 302
 303   *objectFlags =
 304       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 305
 306   PropertyInfo prop = PropertyInfo(flags, slot);
 307   return addPropertyInternal(cx, map, mapLength, id, prop);
 308 }
 309
 310 // static
 311 bool SharedPropMap::addCustomDataProperty(JSContext* cx, const JSClass* clasp,
 312                                           MutableHandle<SharedPropMap*> map,
 313                                           uint32_t* mapLength, HandleId id,
 314                                           PropertyFlags flags,
 315                                           ObjectFlags* objectFlags) {
 316   MOZ_ASSERT(flags.isCustomDataProperty());
 317
 318   // Custom data properties don't have a slot. Copy the last property's slot
 319   // number to simplify the implementation of SharedPropMap::slotSpan.
 320   uint32_t slot = map ? map->lastUsedSlot(*mapLength) : SHAPE_INVALID_SLOT;
 321
 322   *objectFlags =
 323       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 324
 325   PropertyInfo prop = PropertyInfo(flags, slot);
 326   return addPropertyInternal(cx, map, mapLength, id, prop);
 327 }
 328
 329 // static
 330 bool SharedPropMap::addPropertyInternal(JSContext* cx,
 331                                         MutableHandle<SharedPropMap*> map,
 332                                         uint32_t* mapLength, HandleId id,
 333                                         PropertyInfo prop) {
 334   if (!map) {
 335     // Adding the first property.
 336     MOZ_ASSERT(*mapLength == 0);
 337     map.set(SharedPropMap::createInitial(cx, id, prop));
 338     if (!map) {
 339       return false;
 340     }
 341     *mapLength = 1;
 342     return true;
 343   }
 344
 345   MOZ_ASSERT(*mapLength > 0);
 346
 347   if (*mapLength < PropMap::Capacity) {
 348     // Use the next map entry if possible.
 349     if (!map->hasKey(*mapLength)) {
 350       if (map->canHaveTable()) {
 351         JS::AutoCheckCannotGC nogc;
 352         if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 353           if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) {
 354             return false;
 355           }
 356         }
 357       }
 358       map->initProperty(*mapLength, id, prop);
 359       *mapLength += 1;
 360       return true;
 361     }
 362     if (map->matchProperty(*mapLength, id, prop)) {
 363       *mapLength += 1;
 364       return true;
 365     }
 366
 367     // The next entry can't be used so look up or create a child map. The child
 368     // map is a clone of this map up to mapLength, with the new property stored
 369     // as the next entry.
 370
 371     if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) {
 372       map.set(child);
 373       *mapLength += 1;
 374       return true;
 375     }
 376
 377     SharedPropMap* child = SharedPropMap::clone(cx, map, *mapLength);
 378     if (!child) {
 379       return false;
 380     }
 381     child->initProperty(*mapLength, id, prop);
 382
 383     SharedPropMapAndIndex childEntry(child, *mapLength - 1);
 384     if (!map->addChild(cx, childEntry, id, prop)) {
 385       return false;
 386     }
 387
 388     map.set(child);
 389     *mapLength += 1;
 390     return true;
 391   }
 392
 393   // This map is full so look up or create a child map.
 394   MOZ_ASSERT(*mapLength == PropMap::Capacity);
 395
 396   if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) {
 397     map.set(child);
 398     *mapLength = 1;
 399     return true;
 400   }
 401
 402   SharedPropMap* child = SharedPropMap::create(cx, map, id, prop);
 403   if (!child) {
 404     return false;
 405   }
 406
 407   SharedPropMapAndIndex childEntry(child, PropMap::Capacity - 1);
 408   if (!map->addChild(cx, childEntry, id, prop)) {
 409     return false;
 410   }
 411
 412   // As an optimization, pass the table to the new child map, unless adding the
 413   // property to it OOMs. Measurements indicate this gets rid of a large number
 414   // of PropMapTable allocations because we don't need to create a second table
 415   // when the parent map won't be used again as last map.
 416   if (map->canHaveTable()) {
 417     JS::AutoCheckCannotGC nogc;
 418     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 419       // Trigger a pre-barrier on the parent map to appease the pre-barrier
 420       // verifier, because edges from the table are disappearing (even though
 421       // these edges are strictly redundant with the |previous| maps).
 422       gc::PreWriteBarrier(map.get());
 423       if (table->add(cx, id, PropMapAndIndex(child, 0))) {
 424         map->asLinked()->handOffTableTo(child->asLinked());
 425       } else {
 426         cx->recoverFromOutOfMemory();
 427       }
 428     }
 429   }
 430
 431   map.set(child);
 432   *mapLength = 1;
 433   return true;
 434 }
 435
 436 static PropertyFlags ComputeFlagsForSealOrFreeze(PropertyKey key,
 437                                                  PropertyFlags flags,
 438                                                  IntegrityLevel level) {
 439   // Private fields are not visible to SetIntegrityLevel.
 440   if (key.isSymbol() && key.toSymbol()->isPrivateName()) {
 441     return flags;
 442   }
 443
 444   // Make all properties non-configurable; if freezing, make data properties
 445   // read-only.
 446   flags.clearFlag(PropertyFlag::Configurable);
 447   if (level == IntegrityLevel::Frozen && flags.isDataDescriptor()) {
 448     flags.clearFlag(PropertyFlag::Writable);
 449   }
 450
 451   return flags;
 452 }
 453
 454 // static
 455 bool SharedPropMap::freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
 456                                            const JSClass* clasp,
 457                                            MutableHandle<SharedPropMap*> map,
 458                                            uint32_t mapLength,
 459                                            ObjectFlags* objectFlags) {
 460   // Add all maps to a Vector so we can iterate over them in reverse order
 461   // (property definition order).
 462   JS::RootedVector<SharedPropMap*> maps(cx);
 463   {
 464     SharedPropMap* curMap = map;
 465     while (true) {
 466       if (!maps.append(curMap)) {
 467         return false;
 468       }
 469       if (!curMap->hasPrevious()) {
 470         break;
 471       }
 472       curMap = curMap->asNormal()->previous();
 473     }
 474   }
 475
 476   // Build a new SharedPropMap by adding each property with the changed
 477   // attributes.
 478   Rooted<SharedPropMap*> newMap(cx);
 479   uint32_t newMapLength = 0;
 480
 481   Rooted<PropertyKey> key(cx);
 482   Rooted<SharedPropMap*> curMap(cx);
 483
 484   for (size_t i = maps.length(); i > 0; i--) {
 485     curMap = maps[i - 1];
 486     uint32_t len = (i == 1) ? mapLength : PropMap::Capacity;
 487
 488     for (uint32_t j = 0; j < len; j++) {
 489       key = curMap->getKey(j);
 490       PropertyInfo prop = curMap->getPropertyInfo(j);
 491       PropertyFlags flags =
 492           ComputeFlagsForSealOrFreeze(key, prop.flags(), level);
 493
 494       if (prop.isCustomDataProperty()) {
 495         if (!addCustomDataProperty(cx, clasp, &newMap, &newMapLength, key,
 496                                    flags, objectFlags)) {
 497           return false;
 498         }
 499       } else {
 500         if (!addPropertyWithKnownSlot(cx, clasp, &newMap, &newMapLength, key,
 501                                       flags, prop.slot(), objectFlags)) {
 502           return false;
 503         }
 504       }
 505     }
 506   }
 507
 508   map.set(newMap);
 509   MOZ_ASSERT(newMapLength == mapLength);
 510   return true;
 511 }
 512
 513 void LinkedPropMap::handOffTableTo(LinkedPropMap* next) {
 514   MOZ_ASSERT(hasTable());
 515   MOZ_ASSERT(!next->hasTable());
 516
 517   next->data_.table = data_.table;
 518   data_.table = nullptr;
 519
 520   // Note: for tables currently only sizeof(PropMapTable) is tracked.
 521   RemoveCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable);
 522   AddCellMemory(next, sizeof(PropMapTable), MemoryUse::PropMapTable);
 523 }
 524
 525 void DictionaryPropMap::handOffLastMapStateTo(DictionaryPropMap* newLast) {
 526   // A dictionary object's last map contains the table, slot freeList, and
 527   // holeCount. These fields always have their initial values for non-last maps.
 528
 529   MOZ_ASSERT(this != newLast);
 530
 531   if (asLinked()->hasTable()) {
 532     asLinked()->handOffTableTo(newLast->asLinked());
 533   }
 534
 535   MOZ_ASSERT(newLast->freeList_ == SHAPE_INVALID_SLOT);
 536   newLast->freeList_ = freeList_;
 537   freeList_ = SHAPE_INVALID_SLOT;
 538
 539   MOZ_ASSERT(newLast->holeCount_ == 0);
 540   newLast->holeCount_ = holeCount_;
 541   holeCount_ = 0;
 542 }
 543
 544 // static
 545 bool DictionaryPropMap::addProperty(JSContext* cx, const JSClass* clasp,
 546                                     MutableHandle<DictionaryPropMap*> map,
 547                                     uint32_t* mapLength, HandleId id,
 548                                     PropertyFlags flags, uint32_t slot,
 549                                     ObjectFlags* objectFlags) {
 550   MOZ_ASSERT(map);
 551
 552   *objectFlags =
 553       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 554   PropertyInfo prop = PropertyInfo(flags, slot);
 555
 556   if (*mapLength < PropMap::Capacity) {
 557     JS::AutoCheckCannotGC nogc;
 558     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 559       if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) {
 560         return false;
 561       }
 562     }
 563     map->initProperty(*mapLength, id, prop);
 564     *mapLength += 1;
 565     return true;
 566   }
 567
 568   DictionaryPropMap* newMap = cx->newCell<DictionaryPropMap>(map, id, prop);
 569   if (!newMap) {
 570     return false;
 571   }
 572
 573   JS::AutoCheckCannotGC nogc;
 574   if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 575     if (!table->add(cx, id, PropMapAndIndex(newMap, 0))) {
 576       return false;
 577     }
 578   }
 579
 580   MOZ_ASSERT(newMap->previous() == map);
 581   map->handOffLastMapStateTo(newMap);
 582
 583   map.set(newMap);
 584   *mapLength = 1;
 585   return true;
 586 }
 587
 588 void DictionaryPropMap::changeProperty(JSContext* cx, const JSClass* clasp,
 589                                        uint32_t index, PropertyFlags flags,
 590                                        uint32_t slot,
 591                                        ObjectFlags* objectFlags) {
 592   MOZ_ASSERT(hasKey(index));
 593   *objectFlags = GetObjectFlagsForNewProperty(clasp, *objectFlags,
 594                                               getKey(index), flags, cx);
 595   linkedData_.propInfos[index] = PropertyInfo(flags, slot);
 596 }
 597
 598 void DictionaryPropMap::freezeOrSealProperties(JSContext* cx,
 599                                                IntegrityLevel level,
 600                                                const JSClass* clasp,
 601                                                uint32_t mapLength,
 602                                                ObjectFlags* objectFlags) {
 603   DictionaryPropMap* curMap = this;
 604   do {
 605     for (uint32_t i = 0; i < mapLength; i++) {
 606       if (!curMap->hasKey(i)) {
 607         continue;
 608       }
 609       PropertyKey key = curMap->getKey(i);
 610       PropertyFlags flags = curMap->getPropertyInfo(i).flags();
 611       flags = ComputeFlagsForSealOrFreeze(key, flags, level);
 612       curMap->changePropertyFlags(cx, clasp, i, flags, objectFlags);
 613     }
 614     curMap = curMap->previous();
 615     mapLength = PropMap::Capacity;
 616   } while (curMap);
 617 }
 618
 619 // static
 620 void DictionaryPropMap::skipTrailingHoles(MutableHandle<DictionaryPropMap*> map,
 621                                           uint32_t* mapLength) {
 622   // After removing a property, rewind map/mapLength so that the last property
 623   // is not a hole. This ensures accessing the last property of a map can always
 624   // be done without checking for holes.
 625
 626   while (true) {
 627     MOZ_ASSERT(*mapLength > 0);
 628     do {
 629       if (map->hasKey(*mapLength - 1)) {
 630         return;
 631       }
 632       map->decHoleCount();
 633       *mapLength -= 1;
 634     } while (*mapLength > 0);
 635
 636     if (!map->previous()) {
 637       // The dictionary map is empty, return the initial map with mapLength 0.
 638       MOZ_ASSERT(*mapLength == 0);
 639       MOZ_ASSERT(map->holeCount_ == 0);
 640       return;
 641     }
 642
 643     map->handOffLastMapStateTo(map->previous());
 644     map.set(map->previous());
 645     *mapLength = PropMap::Capacity;
 646   }
 647 }
 648
 649 // static
 650 void DictionaryPropMap::removeProperty(JSContext* cx,
 651                                        MutableHandle<DictionaryPropMap*> map,
 652                                        uint32_t* mapLength, PropMapTable* table,
 653                                        PropMapTable::Ptr& ptr) {
 654   MOZ_ASSERT(map);
 655   MOZ_ASSERT(*mapLength > 0);
 656
 657   JS::AutoCheckCannotGC nogc;
 658   MOZ_ASSERT(map->asLinked()->maybeTable(nogc) == table);
 659
 660   bool removingLast = (map == ptr->map() && *mapLength - 1 == ptr->index());
 661   ptr->map()->asDictionary()->clearProperty(ptr->index());
 662   map->incHoleCount();
 663   table->remove(ptr);
 664
 665   if (removingLast) {
 666     skipTrailingHoles(map, mapLength);
 667   }
 668   maybeCompact(cx, map, mapLength);
 669 }
 670
 671 // static
 672 void DictionaryPropMap::densifyElements(JSContext* cx,
 673                                         MutableHandle<DictionaryPropMap*> map,
 674                                         uint32_t* mapLength,
 675                                         NativeObject* obj) {
 676   MOZ_ASSERT(map);
 677   MOZ_ASSERT(*mapLength > 0);
 678
 679   JS::AutoCheckCannotGC nogc;
 680   PropMapTable* table = map->asLinked()->maybeTable(nogc);
 681
 682   DictionaryPropMap* currentMap = map;
 683   uint32_t currentLen = *mapLength;
 684   do {
 685     for (uint32_t i = 0; i < currentLen; i++) {
 686       PropertyKey key = currentMap->getKey(i);
 687       uint32_t index;
 688       if (!IdIsIndex(key, &index)) {
 689         continue;
 690       }
 691
 692       // The caller must have checked all sparse elements are plain data
 693       // properties.
 694       PropertyInfo prop = currentMap->getPropertyInfo(i);
 695       MOZ_ASSERT(prop.flags() == PropertyFlags::defaultDataPropFlags);
 696
 697       uint32_t slot = prop.slot();
 698       Value value = obj->getSlot(slot);
 699       obj->setDenseElement(index, value);
 700       obj->freeDictionarySlot(slot);
 701
 702       if (table) {
 703         PropMapTable::Ptr p = table->lookupRaw(key);
 704         MOZ_ASSERT(p);
 705         table->remove(p);
 706       }
 707
 708       currentMap->clearProperty(i);
 709       map->incHoleCount();
 710     }
 711     currentMap = currentMap->previous();
 712     currentLen = PropMap::Capacity;
 713   } while (currentMap);
 714
 715   skipTrailingHoles(map, mapLength);
 716   maybeCompact(cx, map, mapLength);
 717 }
 718
 719 void DictionaryPropMap::maybeCompact(JSContext* cx,
 720                                      MutableHandle<DictionaryPropMap*> map,
 721                                      uint32_t* mapLength) {
 722   // If there are no holes, there's nothing to compact.
 723   if (map->holeCount_ == 0) {
 724     return;
 725   }
 726
 727   JS::AutoCheckCannotGC nogc;
 728   PropMapTable* table = map->asLinked()->ensureTable(cx, nogc);
 729   if (!table) {
 730     // Compacting is optional so just return.
 731     cx->recoverFromOutOfMemory();
 732     return;
 733   }
 734
 735   // Heuristic: only compact if the number of holes >= the number of (non-hole)
 736   // entries.
 737   if (map->holeCount_ < table->entryCount()) {
 738     return;
 739   }
 740
 741   // Add all dictionary maps to a Vector so that we can iterate over them in
 742   // reverse order (property definition order). If appending to the Vector OOMs,
 743   // just return because compacting is optional.
 744   Vector<DictionaryPropMap*, 32, SystemAllocPolicy> maps;
 745   for (DictionaryPropMap* curMap = map; curMap; curMap = curMap->previous()) {
 746     if (!maps.append(curMap)) {
 747       return;
 748     }
 749   }
 750
 751   // Use two cursors: readMapCursor/readIndexCursor iterates over all properties
 752   // starting at the first one, to search for the next non-hole entry.
 753   // writeMapCursor/writeIndexCursor is used to write all non-hole keys.
 754   //
 755   // At the start of the loop, these cursors point to the next property slot to
 756   // read/write.
 757
 758   size_t readMapCursorVectorIndex = maps.length() - 1;
 759   DictionaryPropMap* readMapCursor = maps[readMapCursorVectorIndex];
 760   uint32_t readIndexCursor = 0;
 761
 762   size_t writeMapCursorVectorIndex = readMapCursorVectorIndex;
 763   DictionaryPropMap* writeMapCursor = readMapCursor;
 764   uint32_t writeIndexCursor = 0;
 765
 766   mozilla::DebugOnly<uint32_t> numHoles = 0;
 767
 768   while (true) {
 769     if (readMapCursor->hasKey(readIndexCursor)) {
 770       // Found a non-hole entry, copy it to its new position and update the
 771       // PropMapTable to point to this new entry. Only do this if the read and
 772       // write positions are different from each other.
 773       if (readMapCursor != writeMapCursor ||
 774           readIndexCursor != writeIndexCursor) {
 775         PropertyKey key = readMapCursor->getKey(readIndexCursor);
 776         auto p = table->lookupRaw(key);
 777         MOZ_ASSERT(p);
 778         MOZ_ASSERT(p->map() == readMapCursor);
 779         MOZ_ASSERT(p->index() == readIndexCursor);
 780
 781         writeMapCursor->setKey(writeIndexCursor, key);
 782         writeMapCursor->linkedData_.propInfos[writeIndexCursor] =
 783             readMapCursor->linkedData_.propInfos[readIndexCursor];
 784
 785         PropMapAndIndex newEntry(writeMapCursor, writeIndexCursor);
 786         table->replaceEntry(p, key, newEntry);
 787       }
 788       // Advance the write cursor.
 789       writeIndexCursor++;
 790       if (writeIndexCursor == PropMap::Capacity) {
 791         MOZ_ASSERT(writeMapCursorVectorIndex > 0);
 792         writeMapCursorVectorIndex--;
 793         writeMapCursor = maps[writeMapCursorVectorIndex];
 794         writeIndexCursor = 0;
 795       }
 796     } else {
 797       numHoles++;
 798     }
 799     // Advance the read cursor. If there are no more maps to read from, we're
 800     // done.
 801     readIndexCursor++;
 802     if (readIndexCursor == PropMap::Capacity) {
 803       if (readMapCursorVectorIndex == 0) {
 804         break;
 805       }
 806       readMapCursorVectorIndex--;
 807       readMapCursor = maps[readMapCursorVectorIndex];
 808       readIndexCursor = 0;
 809     }
 810   }
 811
 812   // Sanity check: the read cursor skipped holes between properties and holes
 813   // at the end of the last map (these are not included in holeCount_).
 814   MOZ_ASSERT(map->holeCount_ + (PropMap::Capacity - *mapLength) == numHoles);
 815
 816   // The write cursor points to the next available slot. If this is at the start
 817   // of a new map, use the previous map (which must be full) instead.
 818   if (writeIndexCursor == 0 && writeMapCursor->previous()) {
 819     writeMapCursor = writeMapCursor->previous();
 820     *mapLength = PropMap::Capacity;
 821   } else {
 822     *mapLength = writeIndexCursor;
 823   }
 824
 825   // Ensure the last map does not have any keys in [mapLength, Capacity).
 826   for (uint32_t i = *mapLength; i < PropMap::Capacity; i++) {
 827     writeMapCursor->clearProperty(i);
 828   }
 829
 830   if (writeMapCursor != map) {
 831     map->handOffLastMapStateTo(writeMapCursor);
 832     map.set(writeMapCursor);
 833   }
 834   map->holeCount_ = 0;
 835
 836   MOZ_ASSERT(*mapLength <= PropMap::Capacity);
 837   MOZ_ASSERT_IF(*mapLength == 0, !map->previous());
 838   MOZ_ASSERT_IF(!map->previous(), table->entryCount() == *mapLength);
 839 }
 840
 841 void SharedPropMap::fixupAfterMovingGC() {
 842   SharedChildrenPtr& childrenRef = treeDataRef().children;
 843   if (childrenRef.isNone()) {
 844     return;
 845   }
 846
 847   if (!hasChildrenSet()) {
 848     SharedPropMapAndIndex child = childrenRef.toSingleChild();
 849     if (gc::IsForwarded(child.map())) {
 850       child = SharedPropMapAndIndex(gc::Forwarded(child.map()), child.index());
 851       childrenRef.setSingleChild(child);
 852     }
 853     return;
 854   }
 855
 856   SharedChildrenSet* set = childrenRef.toChildrenSet();
 857   for (SharedChildrenSet::Enum e(*set); !e.empty(); e.popFront()) {
 858     SharedPropMapAndIndex child = e.front();
 859     if (IsForwarded(child.map())) {
 860       child = SharedPropMapAndIndex(Forwarded(child.map()), child.index());
 861       e.mutableFront() = child;
 862     }
 863   }
 864 }
 865
 866 void SharedPropMap::removeChild(JS::GCContext* gcx, SharedPropMap* child) {
 867   SharedPropMapAndIndex& parentRef = child->treeDataRef().parent;
 868   MOZ_ASSERT(parentRef.map() == this);
 869
 870   uint32_t index = parentRef.index();
 871   parentRef.setNone();
 872
 873   SharedChildrenPtr& childrenRef = treeDataRef().children;
 874   MOZ_ASSERT(!childrenRef.isNone());
 875
 876   if (!hasChildrenSet()) {
 877     MOZ_ASSERT(childrenRef.toSingleChild().map() == child);
 878     MOZ_ASSERT(childrenRef.toSingleChild().index() == index);
 879     childrenRef.setNone();
 880     return;
 881   }
 882
 883   SharedChildrenSet* set = childrenRef.toChildrenSet();
 884   {
 885     uint32_t nextIndex = SharedPropMap::indexOfNextProperty(index);
 886     SharedChildrenHasher::Lookup lookup(
 887         child->getPropertyInfoWithKey(nextIndex), index);
 888     auto p = set->lookup(lookup);
 889     MOZ_ASSERT(p, "Child must be in children set");
 890     set->remove(p);
 891   }
 892
 893   MOZ_ASSERT(set->count() >= 1);
 894
 895   if (set->count() == 1) {
 896     // Convert from set form back to single child form.
 897     SharedChildrenSet::Range r = set->all();
 898     SharedPropMapAndIndex remainingChild = r.front();
 899     childrenRef.setSingleChild(remainingChild);
 900     clearHasChildrenSet();
 901     gcx->delete_(this, set, MemoryUse::PropMapChildren);
 902   }
 903 }
 904
 905 void LinkedPropMap::purgeTable(JS::GCContext* gcx) {
 906   MOZ_ASSERT(hasTable());
 907   gcx->delete_(this, data_.table, MemoryUse::PropMapTable);
 908   data_.table = nullptr;
 909 }
 910
 911 uint32_t PropMap::approximateEntryCount() const {
 912   // Returns a number that's guaranteed to tbe >= the exact number of properties
 913   // in this map (including previous maps). This is used to reserve space in the
 914   // HashSet when allocating a table for this map.
 915
 916   const PropMap* map = this;
 917   uint32_t count = 0;
 918   JS::AutoCheckCannotGC nogc;
 919   while (true) {
 920     if (!map->hasPrevious()) {
 921       return count + PropMap::Capacity;
 922     }
 923     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 924       return count + table->entryCount();
 925     }
 926     count += PropMap::Capacity;
 927     map = map->asLinked()->previous();
 928   }
 929 }
 930
 931 bool PropMapTable::init(JSContext* cx, LinkedPropMap* map) {
 932   if (!set_.reserve(map->approximateEntryCount())) {
 933     ReportOutOfMemory(cx);
 934     return false;
 935   }
 936
 937   PropMap* curMap = map;
 938   while (true) {
 939     for (uint32_t i = 0; i < PropMap::Capacity; i++) {
 940       if (curMap->hasKey(i)) {
 941         PropertyKey key = curMap->getKey(i);
 942         set_.putNewInfallible(key, PropMapAndIndex(curMap, i));
 943       }
 944     }
 945     if (!curMap->hasPrevious()) {
 946       break;
 947     }
 948     curMap = curMap->asLinked()->previous();
 949   }
 950
 951   return true;
 952 }
 953
 954 void PropMapTable::trace(JSTracer* trc) {
 955   purgeCache();
 956
 957   for (Set::Enum e(set_); !e.empty(); e.popFront()) {
 958     PropMap* map = e.front().map();
 959     TraceManuallyBarrieredEdge(trc, &map, "PropMapTable map");
 960     if (map != e.front().map()) {
 961       e.mutableFront() = PropMapAndIndex(map, e.front().index());
 962     }
 963   }
 964 }
 965
 966 #ifdef JSGC_HASH_TABLE_CHECKS
 967 void PropMapTable::checkAfterMovingGC() {
 968   for (Set::Enum e(set_); !e.empty(); e.popFront()) {
 969     PropMap* map = e.front().map();
 970     MOZ_ASSERT(map);
 971     CheckGCThingAfterMovingGC(map);
 972
 973     PropertyKey key = map->getKey(e.front().index());
 974     MOZ_RELEASE_ASSERT(!key.isVoid());
 975
 976     auto p = lookupRaw(key);
 977     MOZ_RELEASE_ASSERT(p.found() && *p == e.front());
 978   }
 979 }
 980 #endif
 981
 982 #ifdef DEBUG
 983 bool LinkedPropMap::canSkipMarkingTable() {
 984   if (!hasTable()) {
 985     return true;
 986   }
 987
 988   PropMapTable* table = data_.table;
 989   uint32_t count = 0;
 990
 991   PropMap* map = this;
 992   while (true) {
 993     for (uint32_t i = 0; i < Capacity; i++) {
 994       if (map->hasKey(i)) {
 995         PropertyKey key = map->getKey(i);
 996         PropMapTable::Ptr p = table->readonlyThreadsafeLookup(key);
 997         MOZ_ASSERT(*p == PropMapAndIndex(map, i));
 998         count++;
 999       }
1000     }
1001     if (!map->hasPrevious()) {
1002       break;
1003     }
1004     map = map->asLinked()->previous();
1005   }
1006
1007   return count == table->entryCount();
1008 }
1009 #endif
1010
1011 bool LinkedPropMap::createTable(JSContext* cx) {
1012   MOZ_ASSERT(canHaveTable());
1013   MOZ_ASSERT(!hasTable());
1014
1015   UniquePtr<PropMapTable> table = cx->make_unique<PropMapTable>();
1016   if (!table) {
1017     return false;
1018   }
1019
1020   if (!table->init(cx, this)) {
1021     return false;
1022   }
1023
1024   data_.table = table.release();
1025   // TODO: The contents of PropMapTable is not currently tracked, only the
1026   // object itself.
1027   AddCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable);
1028   return true;
1029 }
1030
1031 #ifdef DEBUG
1032 void PropMap::dump(js::GenericPrinter& out) const {
1033   out.printf("map @ 0x%p\n", this);
1034   out.printf("previous: 0x%p\n",
1035              hasPrevious() ? asLinked()->previous() : nullptr);
1036
1037   if (canHaveTable()) {
1038     out.printf("table: 0x%p\n", asLinked()->data_.table);
1039   } else {
1040     out.printf("table: (too small for table)\n");
1041   }
1042
1043   if (isShared()) {
1044     out.printf("type: shared\n");
1045     out.printf("  compact: %s\n", isCompact() ? "yes" : "no");
1046     SharedPropMapAndIndex parent = asShared()->treeDataRef().parent;
1047     if (parent.isNone()) {
1048       out.printf("  parent: (none)\n");
1049     } else {
1050       out.printf("  parent: 0x%p [%u]\n", parent.map(), parent.index());
1051     }
1052   } else {
1053     const DictionaryPropMap* dictMap = asDictionary();
1054     out.printf("type: dictionary\n");
1055     out.printf("  freeList: %u\n", dictMap->freeList_);
1056     out.printf("  holeCount: %u\n", dictMap->holeCount_);
1057   }
1058
1059   out.printf("properties:\n");
1060   for (uint32_t i = 0; i < Capacity; i++) {
1061     out.printf("  %u: ", i);
1062
1063     if (!hasKey(i)) {
1064       out.printf("(empty)\n");
1065       continue;
1066     }
1067
1068     PropertyKey key = getKey(i);
1069     if (key.isInt()) {
1070       out.printf("[%d]", key.toInt());
1071     } else if (key.isAtom()) {
1072       EscapedStringPrinter(out, key.toAtom(), '"');
1073     } else {
1074       MOZ_ASSERT(key.isSymbol());
1075       key.toSymbol()->dump(out);
1076     }
1077
1078     PropertyInfo prop = getPropertyInfo(i);
1079     out.printf(" slot %u flags 0x%x ", prop.maybeSlot(), prop.flags().toRaw());
1080
1081     if (!prop.flags().isEmpty()) {
1082       bool first = true;
1083       auto dumpFlag = [&](PropertyFlag flag, const char* name) {
1084         if (!prop.flags().hasFlag(flag)) {
1085           return;
1086         }
1087         if (!first) {
1088           out.putChar(' ');
1089         }
1090         out.put(name);
1091         first = false;
1092       };
1093       out.putChar('(');
1094       dumpFlag(PropertyFlag::Enumerable, "enumerable");
1095       dumpFlag(PropertyFlag::Configurable, "configurable");
1096       dumpFlag(PropertyFlag::Writable, "writable");
1097       dumpFlag(PropertyFlag::AccessorProperty, "accessor");
1098       dumpFlag(PropertyFlag::CustomDataProperty, "custom-data");
1099       out.putChar(')');
1100     }
1101     out.putChar('\n');
1102   }
1103 }
1104
1105 void PropMap::dump() const {
1106   Fprinter out(stderr);
1107   dump(out);
1108 }
1109
1110 void PropMap::checkConsistency(NativeObject* obj) const {
1111   const uint32_t mapLength = obj->shape()->propMapLength();
1112   MOZ_ASSERT(mapLength <= PropMap::Capacity);
1113
1114   JS::AutoCheckCannotGC nogc;
1115   if (isDictionary()) {
1116     // Check dictionary slot free list.
1117     for (uint32_t fslot = asDictionary()->freeList();
1118          fslot != SHAPE_INVALID_SLOT;
1119          fslot = obj->getSlot(fslot).toPrivateUint32()) {
1120       MOZ_ASSERT(fslot < obj->slotSpan());
1121     }
1122
1123     auto* table = asLinked()->maybeTable(nogc);
1124     const DictionaryPropMap* curMap = asDictionary();
1125     uint32_t numHoles = 0;
1126     do {
1127       // Some fields must only be set for the last dictionary map.
1128       if (curMap != this) {
1129         MOZ_ASSERT(!curMap->asLinked()->hasTable());
1130         MOZ_ASSERT(curMap->holeCount_ == 0);
1131         MOZ_ASSERT(curMap->freeList_ == SHAPE_INVALID_SLOT);
1132       }
1133
1134       for (uint32_t i = 0; i < PropMap::Capacity; i++) {
1135         if (!curMap->hasKey(i)) {
1136           if (curMap != this || i < mapLength) {
1137             numHoles++;
1138           }
1139           continue;
1140         }
1141
1142         // The last dictionary map must only have keys up to mapLength.
1143         MOZ_ASSERT_IF(curMap == this, i < mapLength);
1144
1145         PropertyInfo prop = curMap->getPropertyInfo(i);
1146         MOZ_ASSERT_IF(prop.hasSlot(), prop.slot() < obj->slotSpan());
1147
1148         // All properties must be in the table.
1149         if (table) {
1150           PropertyKey key = curMap->getKey(i);
1151           auto p = table->lookupRaw(key);
1152           MOZ_ASSERT(p->map() == curMap);
1153           MOZ_ASSERT(p->index() == i);
1154         }
1155       }
1156       curMap = curMap->previous();
1157     } while (curMap);
1158
1159     MOZ_ASSERT(asDictionary()->holeCount_ == numHoles);
1160     return;
1161   }
1162
1163   MOZ_ASSERT(mapLength > 0);
1164
1165   const SharedPropMap* curMap = asShared();
1166   auto* table =
1167       curMap->canHaveTable() ? curMap->asLinked()->maybeTable(nogc) : nullptr;
1168
1169   // Shared maps without a previous map never have a table.
1170   MOZ_ASSERT_IF(!curMap->hasPrevious(), !curMap->canHaveTable());
1171
1172   const SharedPropMap* nextMap = nullptr;
1173   mozilla::Maybe<uint32_t> nextSlot;
1174   while (true) {
1175     // Verify numPreviousMaps is set correctly.
1176     MOZ_ASSERT_IF(nextMap && nextMap->numPreviousMaps() != NumPreviousMapsMax,
1177                   curMap->numPreviousMaps() + 1 == nextMap->numPreviousMaps());
1178     MOZ_ASSERT(curMap->hasPrevious() == (curMap->numPreviousMaps() > 0));
1179
1180     // If a previous map also has a table, it must have fewer entries than the
1181     // last map's table.
1182     if (table && curMap != this && curMap->canHaveTable()) {
1183       if (auto* table2 = curMap->asLinked()->maybeTable(nogc)) {
1184         MOZ_ASSERT(table2->entryCount() < table->entryCount());
1185       }
1186     }
1187
1188     for (int32_t i = PropMap::Capacity - 1; i >= 0; i--) {
1189       uint32_t index = uint32_t(i);
1190
1191       // Only the last map can have holes, for entries following mapLength.
1192       if (!curMap->hasKey(index)) {
1193         MOZ_ASSERT(index > 0);
1194         MOZ_ASSERT(curMap == this);
1195         MOZ_ASSERT(index >= mapLength);
1196         continue;
1197       }
1198
1199       // Check slot numbers are within slot span and never decreasing.
1200       PropertyInfo prop = curMap->getPropertyInfo(i);
1201       if (prop.hasSlot()) {
1202         MOZ_ASSERT_IF((curMap != this || index < mapLength),
1203                       prop.slot() < obj->slotSpan());
1204         MOZ_ASSERT_IF(nextSlot.isSome(), *nextSlot >= prop.slot());
1205         nextSlot = mozilla::Some(prop.slot());
1206       }
1207
1208       // All properties must be in the table.
1209       if (table) {
1210         PropertyKey key = curMap->getKey(index);
1211         auto p = table->lookupRaw(key);
1212         MOZ_ASSERT(p->map() == curMap);
1213         MOZ_ASSERT(p->index() == index);
1214       }
1215     }
1216
1217     if (!curMap->hasPrevious()) {
1218       break;
1219     }
1220     nextMap = curMap;
1221     curMap = curMap->asLinked()->previous()->asShared();
1222   }
1223 }
1224 #endif  // DEBUG
1225
1226 JS::ubi::Node::Size JS::ubi::Concrete<PropMap>::size(
1227     mozilla::MallocSizeOf mallocSizeOf) const {
1228   Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1229   size_t children = 0;
1230   size_t tables = 0;
1231   get().addSizeOfExcludingThis(mallocSizeOf, &children, &tables);
1232   return size + children + tables;
1233 }