js/src/vm/Caches.h

   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 #ifndef vm_Caches_h
   8 #define vm_Caches_h
   9
  10 #include "mozilla/Array.h"
  11 #include "mozilla/MathAlgorithms.h"
  12 #include "mozilla/Maybe.h"
  13 #include "mozilla/MruCache.h"
  14 #include "mozilla/TemplateLib.h"
  15 #include "mozilla/UniquePtr.h"
  16
  17 #include "frontend/ScopeBindingCache.h"
  18 #include "gc/Tracer.h"
  19 #include "js/RootingAPI.h"
  20 #include "js/TypeDecls.h"
  21 #include "vm/JSScript.h"
  22 #include "vm/Shape.h"
  23 #include "vm/StencilCache.h"  // js::DelazificationCache
  24 #include "vm/StringType.h"
  25
  26 namespace js {
  27
  28 struct EvalCacheEntry {
  29   JSLinearString* str;
  30   JSScript* script;
  31   JSScript* callerScript;
  32   jsbytecode* pc;
  33
  34   // We sweep this cache after a nursery collection to update entries with
  35   // string keys that have been tenured.
  36   //
  37   // The entire cache is purged on a major GC, so we don't need to sweep it
  38   // then.
  39   bool traceWeak(JSTracer* trc) {
  40     MOZ_ASSERT(trc->kind() == JS::TracerKind::MinorSweeping);
  41     return TraceManuallyBarrieredWeakEdge(trc, &str, "EvalCacheEntry::str");
  42   }
  43 };
  44
  45 struct EvalCacheLookup {
  46   explicit EvalCacheLookup(JSContext* cx) : str(cx), callerScript(cx) {}
  47   Rooted<JSLinearString*> str;
  48   RootedScript callerScript;
  49   MOZ_INIT_OUTSIDE_CTOR jsbytecode* pc;
  50 };
  51
  52 struct EvalCacheHashPolicy {
  53   using Lookup = EvalCacheLookup;
  54
  55   static HashNumber hash(const Lookup& l);
  56   static bool match(const EvalCacheEntry& entry, const EvalCacheLookup& l);
  57 };
  58
  59 using EvalCache =
  60     GCHashSet<EvalCacheEntry, EvalCacheHashPolicy, SystemAllocPolicy>;
  61
  62 class MegamorphicCacheEntry {
  63   // Receiver object's shape.
  64   Shape* shape_ = nullptr;
  65
  66   // The atom or symbol property being accessed.
  67   PropertyKey key_;
  68
  69   // Slot offset and isFixedSlot flag of the data property.
  70   TaggedSlotOffset slotOffset_;
  71
  72   // This entry is valid iff the generation matches the cache's generation.
  73   uint16_t generation_ = 0;
  74
  75   // Number of hops on the proto chain to get to the holder object. If this is
  76   // zero, the property exists on the receiver object. It can also be one of
  77   // the sentinel values indicating a missing property lookup.
  78   uint8_t numHops_ = 0;
  79
  80   friend class MegamorphicCache;
  81
  82  public:
  83   static constexpr uint8_t MaxHopsForDataProperty = UINT8_MAX - 2;
  84   static constexpr uint8_t NumHopsForMissingProperty = UINT8_MAX - 1;
  85   static constexpr uint8_t NumHopsForMissingOwnProperty = UINT8_MAX;
  86
  87   void init(Shape* shape, PropertyKey key, uint16_t generation, uint8_t numHops,
  88             TaggedSlotOffset slotOffset) {
  89     shape_ = shape;
  90     key_ = key;
  91     slotOffset_ = slotOffset;
  92     generation_ = generation;
  93     numHops_ = numHops;
  94     MOZ_ASSERT(numHops_ == numHops, "numHops must fit in numHops_");
  95   }
  96   bool isMissingProperty() const {
  97     return numHops_ == NumHopsForMissingProperty;
  98   }
  99   bool isMissingOwnProperty() const {
 100     return numHops_ == NumHopsForMissingOwnProperty;
 101   }
 102   bool isDataProperty() const { return numHops_ <= MaxHopsForDataProperty; }
 103   uint16_t numHops() const {
 104     MOZ_ASSERT(isDataProperty());
 105     return numHops_;
 106   }
 107   TaggedSlotOffset slotOffset() const {
 108     MOZ_ASSERT(isDataProperty());
 109     return slotOffset_;
 110   }
 111
 112   static constexpr size_t offsetOfShape() {
 113     return offsetof(MegamorphicCacheEntry, shape_);
 114   }
 115
 116   static constexpr size_t offsetOfKey() {
 117     return offsetof(MegamorphicCacheEntry, key_);
 118   }
 119
 120   static constexpr size_t offsetOfGeneration() {
 121     return offsetof(MegamorphicCacheEntry, generation_);
 122   }
 123
 124   static constexpr size_t offsetOfSlotOffset() {
 125     return offsetof(MegamorphicCacheEntry, slotOffset_);
 126   }
 127
 128   static constexpr size_t offsetOfNumHops() {
 129     return offsetof(MegamorphicCacheEntry, numHops_);
 130   }
 131 };
 132
 133 // [SMDOC] Megamorphic Property Lookup Cache (MegamorphicCache)
 134 //
 135 // MegamorphicCache is a data structure used to speed up megamorphic property
 136 // lookups from JIT code. The same cache is currently used for both GetProp and
 137 // HasProp (in, hasOwnProperty) operations.
 138 //
 139 // This is implemented as a fixed-size array of entries. Lookups are performed
 140 // based on the receiver object's Shape + PropertyKey. If found in the cache,
 141 // the result of a lookup represents either:
 142 //
 143 // * A data property on the receiver or on its proto chain (stored as number of
 144 //   'hops' up the proto chain + the slot of the data property).
 145 //
 146 // * A missing property on the receiver or its proto chain.
 147 //
 148 // * A missing property on the receiver, but it might exist on the proto chain.
 149 //   This lets us optimize hasOwnProperty better.
 150 //
 151 // Collisions are handled by simply overwriting the previous entry stored in the
 152 // slot. This is sufficient to achieve a high hit rate on typical web workloads
 153 // while ensuring cache lookups are always fast and simple.
 154 //
 155 // Lookups always check the receiver object's shape (ensuring the properties and
 156 // prototype are unchanged). Because the cache also caches lookups on the proto
 157 // chain, Watchtower is used to invalidate the cache when prototype objects are
 158 // mutated. This is done by incrementing the cache's generation counter to
 159 // invalidate all entries.
 160 //
 161 // The cache is also invalidated on each major GC.
 162 class MegamorphicCache {
 163  public:
 164   using Entry = MegamorphicCacheEntry;
 165
 166   static constexpr size_t NumEntries = 1024;
 167   static constexpr uint8_t ShapeHashShift1 =
 168       mozilla::tl::FloorLog2<alignof(Shape)>::value;
 169   static constexpr uint8_t ShapeHashShift2 =
 170       ShapeHashShift1 + mozilla::tl::FloorLog2<NumEntries>::value;
 171
 172   static_assert(mozilla::IsPowerOfTwo(alignof(Shape)) &&
 173                     mozilla::IsPowerOfTwo(NumEntries),
 174                 "FloorLog2 is exact because alignof(Shape) and NumEntries are "
 175                 "both powers of two");
 176
 177  private:
 178   mozilla::Array<Entry, NumEntries> entries_;
 179
 180   // Generation counter used to invalidate all entries.
 181   uint16_t generation_ = 0;
 182
 183   // NOTE: this logic is mirrored in MacroAssembler::emitMegamorphicCacheLookup
 184   Entry& getEntry(Shape* shape, PropertyKey key) {
 185     static_assert(mozilla::IsPowerOfTwo(NumEntries),
 186                   "NumEntries must be a power-of-two for fast modulo");
 187     uintptr_t hash = uintptr_t(shape) >> ShapeHashShift1;
 188     hash ^= uintptr_t(shape) >> ShapeHashShift2;
 189     hash += HashAtomOrSymbolPropertyKey(key);
 190     return entries_[hash % NumEntries];
 191   }
 192
 193  public:
 194   void bumpGeneration() {
 195     generation_++;
 196     if (generation_ == 0) {
 197       // Generation overflowed. Invalidate the whole cache.
 198       for (size_t i = 0; i < NumEntries; i++) {
 199         entries_[i].shape_ = nullptr;
 200       }
 201     }
 202   }
 203   bool lookup(Shape* shape, PropertyKey key, Entry** entryp) {
 204     Entry& entry = getEntry(shape, key);
 205     *entryp = &entry;
 206     return (entry.shape_ == shape && entry.key_ == key &&
 207             entry.generation_ == generation_);
 208   }
 209   void initEntryForMissingProperty(Entry* entry, Shape* shape,
 210                                    PropertyKey key) {
 211     entry->init(shape, key, generation_, Entry::NumHopsForMissingProperty,
 212                 TaggedSlotOffset());
 213   }
 214   void initEntryForMissingOwnProperty(Entry* entry, Shape* shape,
 215                                       PropertyKey key) {
 216     entry->init(shape, key, generation_, Entry::NumHopsForMissingOwnProperty,
 217                 TaggedSlotOffset());
 218   }
 219   void initEntryForDataProperty(Entry* entry, Shape* shape, PropertyKey key,
 220                                 size_t numHops, TaggedSlotOffset slotOffset) {
 221     if (numHops > Entry::MaxHopsForDataProperty) {
 222       return;
 223     }
 224     entry->init(shape, key, generation_, numHops, slotOffset);
 225   }
 226
 227   static constexpr size_t offsetOfEntries() {
 228     return offsetof(MegamorphicCache, entries_);
 229   }
 230
 231   static constexpr size_t offsetOfGeneration() {
 232     return offsetof(MegamorphicCache, generation_);
 233   }
 234 };
 235
 236 class MegamorphicSetPropCacheEntry {
 237   Shape* beforeShape_ = nullptr;
 238   Shape* afterShape_ = nullptr;
 239
 240   // The atom or symbol property being accessed.
 241   PropertyKey key_;
 242
 243   // Slot offset and isFixedSlot flag of the data property.
 244   TaggedSlotOffset slotOffset_;
 245
 246   // If slots need to be grown, this is the new capacity we need.
 247   uint16_t newCapacity_ = 0;
 248
 249   // This entry is valid iff the generation matches the cache's generation.
 250   uint16_t generation_ = 0;
 251
 252   friend class MegamorphicSetPropCache;
 253
 254  public:
 255   void init(Shape* beforeShape, Shape* afterShape, PropertyKey key,
 256             uint16_t generation, TaggedSlotOffset slotOffset,
 257             uint16_t newCapacity) {
 258     beforeShape_ = beforeShape;
 259     afterShape_ = afterShape;
 260     key_ = key;
 261     slotOffset_ = slotOffset;
 262     newCapacity_ = newCapacity;
 263     generation_ = generation;
 264   }
 265   TaggedSlotOffset slotOffset() const { return slotOffset_; }
 266   Shape* afterShape() const { return afterShape_; }
 267
 268   static constexpr size_t offsetOfShape() {
 269     return offsetof(MegamorphicSetPropCacheEntry, beforeShape_);
 270   }
 271   static constexpr size_t offsetOfAfterShape() {
 272     return offsetof(MegamorphicSetPropCacheEntry, afterShape_);
 273   }
 274
 275   static constexpr size_t offsetOfKey() {
 276     return offsetof(MegamorphicSetPropCacheEntry, key_);
 277   }
 278
 279   static constexpr size_t offsetOfNewCapacity() {
 280     return offsetof(MegamorphicSetPropCacheEntry, newCapacity_);
 281   }
 282
 283   static constexpr size_t offsetOfGeneration() {
 284     return offsetof(MegamorphicSetPropCacheEntry, generation_);
 285   }
 286
 287   static constexpr size_t offsetOfSlotOffset() {
 288     return offsetof(MegamorphicSetPropCacheEntry, slotOffset_);
 289   }
 290 };
 291
 292 class MegamorphicSetPropCache {
 293  public:
 294   using Entry = MegamorphicSetPropCacheEntry;
 295   // We can get more hits if we increase this, but this seems to be around
 296   // the sweet spot where we are getting most of the hits we would get with
 297   // an infinitely sized cache
 298   static constexpr size_t NumEntries = 1024;
 299   static constexpr uint8_t ShapeHashShift1 =
 300       mozilla::tl::FloorLog2<alignof(Shape)>::value;
 301   static constexpr uint8_t ShapeHashShift2 =
 302       ShapeHashShift1 + mozilla::tl::FloorLog2<NumEntries>::value;
 303
 304   static_assert(mozilla::IsPowerOfTwo(alignof(Shape)) &&
 305                     mozilla::IsPowerOfTwo(NumEntries),
 306                 "FloorLog2 is exact because alignof(Shape) and NumEntries are "
 307                 "both powers of two");
 308
 309  private:
 310   mozilla::Array<Entry, NumEntries> entries_;
 311
 312   // Generation counter used to invalidate all entries.
 313   uint16_t generation_ = 0;
 314
 315   Entry& getEntry(Shape* beforeShape, PropertyKey key) {
 316     static_assert(mozilla::IsPowerOfTwo(NumEntries),
 317                   "NumEntries must be a power-of-two for fast modulo");
 318     uintptr_t hash = uintptr_t(beforeShape) >> ShapeHashShift1;
 319     hash ^= uintptr_t(beforeShape) >> ShapeHashShift2;
 320     hash += HashAtomOrSymbolPropertyKey(key);
 321     return entries_[hash % NumEntries];
 322   }
 323
 324  public:
 325   void bumpGeneration() {
 326     generation_++;
 327     if (generation_ == 0) {
 328       // Generation overflowed. Invalidate the whole cache.
 329       for (size_t i = 0; i < NumEntries; i++) {
 330         entries_[i].beforeShape_ = nullptr;
 331       }
 332     }
 333   }
 334   void set(Shape* beforeShape, Shape* afterShape, PropertyKey key,
 335            TaggedSlotOffset slotOffset, uint32_t newCapacity) {
 336     uint16_t newSlots = (uint16_t)newCapacity;
 337     if (newSlots != newCapacity) {
 338       return;
 339     }
 340     Entry& entry = getEntry(beforeShape, key);
 341     entry.init(beforeShape, afterShape, key, generation_, slotOffset, newSlots);
 342   }
 343
 344 #ifdef DEBUG
 345   bool lookup(Shape* beforeShape, PropertyKey key, Entry** entryp) {
 346     Entry& entry = getEntry(beforeShape, key);
 347     *entryp = &entry;
 348     return (entry.beforeShape_ == beforeShape && entry.key_ == key &&
 349             entry.generation_ == generation_);
 350   }
 351 #endif
 352
 353   static constexpr size_t offsetOfEntries() {
 354     return offsetof(MegamorphicSetPropCache, entries_);
 355   }
 356
 357   static constexpr size_t offsetOfGeneration() {
 358     return offsetof(MegamorphicSetPropCache, generation_);
 359   }
 360 };
 361
 362 // Cache for AtomizeString, mapping JSString* or JS::Latin1Char* to the
 363 // corresponding JSAtom*. The cache has three different optimizations:
 364 //
 365 // * The two most recent lookups are cached. This has a hit rate of 30-65% on
 366 //   typical web workloads.
 367 //
 368 // * MruCache is used for short JS::Latin1Char strings.
 369 //
 370 // * For longer strings, there's also a JSLinearString* => JSAtom* HashMap,
 371 //   because hashing the string characters repeatedly can be slow.
 372 //   This map is also used by nursery GC to de-duplicate strings to atoms.
 373 //
 374 // This cache is purged on minor and major GC.
 375 class StringToAtomCache {
 376  public:
 377   struct LastLookup {
 378     JSString* string = nullptr;
 379     JSAtom* atom = nullptr;
 380
 381     static constexpr size_t offsetOfString() {
 382       return offsetof(LastLookup, string);
 383     }
 384
 385     static constexpr size_t offsetOfAtom() {
 386       return offsetof(LastLookup, atom);
 387     }
 388   };
 389   static constexpr size_t NumLastLookups = 2;
 390
 391   struct AtomTableKey {
 392     explicit AtomTableKey(const JS::Latin1Char* str, size_t len)
 393         : string_(str), length_(len) {
 394       hash_ = mozilla::HashString(string_, length_);
 395     }
 396
 397     const JS::Latin1Char* string_;
 398     size_t length_;
 399     uint32_t hash_;
 400   };
 401
 402  private:
 403   struct RopeAtomCache
 404       : public mozilla::MruCache<AtomTableKey, JSAtom*, RopeAtomCache> {
 405     static HashNumber Hash(const AtomTableKey& key) { return key.hash_; }
 406     static bool Match(const AtomTableKey& key, const JSAtom* val) {
 407       JS::AutoCheckCannotGC nogc;
 408       return val->length() == key.length_ &&
 409              EqualChars(key.string_, val->latin1Chars(nogc), key.length_);
 410     }
 411   };
 412   using Map =
 413       HashMap<JSString*, JSAtom*, PointerHasher<JSString*>, SystemAllocPolicy>;
 414   Map map_;
 415   mozilla::Array<LastLookup, NumLastLookups> lastLookups_;
 416   RopeAtomCache ropeCharCache_;
 417
 418  public:
 419   // Don't use the HashMap for short strings. Hashing them is less expensive.
 420   // But the length needs to long enough to cover common identifiers in React.
 421   static constexpr size_t MinStringLength = 39;
 422
 423   JSAtom* lookupInMap(JSString* s) const {
 424     MOZ_ASSERT(s->inStringToAtomCache());
 425     MOZ_ASSERT(s->length() >= MinStringLength);
 426
 427     auto p = map_.lookup(s);
 428     JSAtom* atom = p ? p->value() : nullptr;
 429     return atom;
 430   }
 431
 432   MOZ_ALWAYS_INLINE JSAtom* lookup(JSString* s) const {
 433     MOZ_ASSERT(!s->isAtom());
 434     for (const LastLookup& entry : lastLookups_) {
 435       if (entry.string == s) {
 436         return entry.atom;
 437       }
 438     }
 439
 440     if (!s->inStringToAtomCache()) {
 441       MOZ_ASSERT(!map_.lookup(s));
 442       return nullptr;
 443     }
 444
 445     return lookupInMap(s);
 446   }
 447
 448   MOZ_ALWAYS_INLINE JSAtom* lookupWithRopeChars(
 449       const JS::Latin1Char* str, size_t len,
 450       mozilla::Maybe<AtomTableKey>& key) {
 451     MOZ_ASSERT(len < MinStringLength);
 452     key.emplace(str, len);
 453     if (auto p = ropeCharCache_.Lookup(key.value())) {
 454       return p.Data();
 455     }
 456     return nullptr;
 457   }
 458
 459   static constexpr size_t offsetOfLastLookups() {
 460     return offsetof(StringToAtomCache, lastLookups_);
 461   }
 462
 463   void maybePut(JSString* s, JSAtom* atom, mozilla::Maybe<AtomTableKey>& key) {
 464     if (key.isSome()) {
 465       ropeCharCache_.Put(key.value(), atom);
 466     }
 467
 468     for (size_t i = NumLastLookups - 1; i > 0; i--) {
 469       lastLookups_[i] = lastLookups_[i - 1];
 470     }
 471     lastLookups_[0].string = s;
 472     lastLookups_[0].atom = atom;
 473
 474     if (s->length() < MinStringLength) {
 475       return;
 476     }
 477     if (!map_.putNew(s, atom)) {
 478       return;
 479     }
 480     s->setInStringToAtomCache();
 481   }
 482
 483   void purge() {
 484     map_.clearAndCompact();
 485     for (LastLookup& entry : lastLookups_) {
 486       entry.string = nullptr;
 487       entry.atom = nullptr;
 488     }
 489
 490     ropeCharCache_.Clear();
 491   }
 492 };
 493
 494 class RuntimeCaches {
 495  public:
 496   MegamorphicCache megamorphicCache;
 497   UniquePtr<MegamorphicSetPropCache> megamorphicSetPropCache;
 498   UncompressedSourceCache uncompressedSourceCache;
 499   EvalCache evalCache;
 500   StringToAtomCache stringToAtomCache;
 501
 502   // Delazification: Cache binding for runtime objects which are used during
 503   // delazification to quickly resolve NameLocation of bindings without linearly
 504   // iterating over the list of bindings.
 505   frontend::RuntimeScopeBindingCache scopeCache;
 506
 507   void sweepAfterMinorGC(JSTracer* trc) { evalCache.traceWeak(trc); }
 508 #ifdef JSGC_HASH_TABLE_CHECKS
 509   void checkEvalCacheAfterMinorGC();
 510 #endif
 511
 512   void purgeForCompaction() {
 513     evalCache.clear();
 514     stringToAtomCache.purge();
 515     megamorphicCache.bumpGeneration();
 516     if (megamorphicSetPropCache) {
 517       // MegamorphicSetPropCache can be null if we failed out of
 518       // JSRuntime::init. We will then try to destroy the runtime which will
 519       // do a GC and land us here.
 520       megamorphicSetPropCache->bumpGeneration();
 521     }
 522     scopeCache.purge();
 523   }
 524
 525   void purgeStencils() {
 526     DelazificationCache& cache = DelazificationCache::getSingleton();
 527     cache.clearAndDisable();
 528   }
 529
 530   void purge() {
 531     purgeForCompaction();
 532     uncompressedSourceCache.purge();
 533     purgeStencils();
 534   }
 535 };
 536
 537 }  // namespace js
 538
 539 #endif /* vm_Caches_h */