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 12 #include <iterator> 13 #include <new> 14 15 #include "frontend/SourceNotes.h" // SrcNote 16 #include "gc/Tracer.h" 17 #include "js/RootingAPI.h" 18 #include "js/TypeDecls.h" 19 #include "js/UniquePtr.h" 20 #include "util/Memory.h" 21 #include "vm/ArrayObject.h" 22 #include "vm/JSAtom.h" 23 #include "vm/JSObject.h" 24 #include "vm/JSScript.h" 25 #include "vm/NativeObject.h" 26 #include "vm/StencilCache.h" // js::StencilCache 27 28 namespace js { 29 30 /* 31 * GetSrcNote cache to avoid O(n^2) growth in finding a source note for a 32 * given pc in a script. We use the script->code pointer to tag the cache, 33 * instead of the script address itself, so that source notes are always found 34 * by offset from the bytecode with which they were generated. 35 */ 36 struct GSNCache { 37 typedef HashMap<jsbytecode*, const SrcNote*, PointerHasher<jsbytecode*>, 38 SystemAllocPolicy> 39 Map; 40 41 jsbytecode* code; 42 Map map; 43 GSNCacheGSNCache44 GSNCache() : code(nullptr) {} 45 46 void purge(); 47 }; 48 49 struct EvalCacheEntry { 50 JSLinearString* str; 51 JSScript* script; 52 JSScript* callerScript; 53 jsbytecode* pc; 54 55 // We sweep this cache after a nursery collection to update entries with 56 // string keys that have been tenured. 57 // 58 // The entire cache is purged on a major GC, so we don't need to sweep it 59 // then. traceWeakEvalCacheEntry60 bool traceWeak(JSTracer* trc) { 61 MOZ_ASSERT(trc->kind() == JS::TracerKind::MinorSweeping); 62 return TraceManuallyBarrieredWeakEdge(trc, &str, "EvalCacheEntry::str"); 63 } 64 }; 65 66 struct EvalCacheLookup { EvalCacheLookupEvalCacheLookup67 explicit EvalCacheLookup(JSContext* cx) : str(cx), callerScript(cx) {} 68 RootedLinearString str; 69 RootedScript callerScript; 70 MOZ_INIT_OUTSIDE_CTOR jsbytecode* pc; 71 }; 72 73 struct EvalCacheHashPolicy { 74 using Lookup = EvalCacheLookup; 75 76 static HashNumber hash(const Lookup& l); 77 static bool match(const EvalCacheEntry& entry, const EvalCacheLookup& l); 78 }; 79 80 using EvalCache = 81 GCHashSet<EvalCacheEntry, EvalCacheHashPolicy, SystemAllocPolicy>; 82 83 // [SMDOC] Megamorphic Property Lookup Cache (MegamorphicCache) 84 // 85 // MegamorphicCache is a data structure used to speed up megamorphic property 86 // lookups from JIT code. The same cache is currently used for both GetProp and 87 // HasProp (in, hasOwnProperty) operations. 88 // 89 // This is implemented as a fixed-size array of entries. Lookups are performed 90 // based on the receiver object's Shape + PropertyKey. If found in the cache, 91 // the result of a lookup represents either: 92 // 93 // * A data property on the receiver or on its proto chain (stored as number of 94 // 'hops' up the proto chain + the slot of the data property). 95 // 96 // * A missing property on the receiver or its proto chain. 97 // 98 // * A missing property on the receiver, but it might exist on the proto chain. 99 // This lets us optimize hasOwnProperty better. 100 // 101 // Collisions are handled by simply overwriting the previous entry stored in the 102 // slot. This is sufficient to achieve a high hit rate on typical web workloads 103 // while ensuring cache lookups are always fast and simple. 104 // 105 // Lookups always check the receiver object's shape (ensuring the properties and 106 // prototype are unchanged). Because the cache also caches lookups on the proto 107 // chain, Watchtower is used to invalidate the cache when prototype objects are 108 // mutated. This is done by incrementing the cache's generation counter to 109 // invalidate all entries. 110 // 111 // The cache is also invalidated on each major GC. 112 class MegamorphicCache { 113 public: 114 class Entry { 115 // Receiver object's shape. 116 Shape* shape_ = nullptr; 117 118 // The atom or symbol property being accessed. 119 PropertyKey key_; 120 121 // This entry is valid iff the generation matches the cache's generation. 122 uint16_t generation_ = 0; 123 124 // Slot number of the data property. 125 static constexpr size_t MaxSlotNumber = UINT16_MAX; 126 uint16_t slot_ = 0; 127 128 // Number of hops on the proto chain to get to the holder object. If this is 129 // zero, the property exists on the receiver object. It can also be one of 130 // the sentinel values indicating a missing property lookup. 131 static constexpr size_t MaxHopsForDataProperty = UINT8_MAX - 2; 132 static constexpr size_t NumHopsForMissingProperty = UINT8_MAX - 1; 133 static constexpr size_t NumHopsForMissingOwnProperty = UINT8_MAX; 134 uint8_t numHops_ = 0; 135 136 friend class MegamorphicCache; 137 138 public: init(Shape * shape,PropertyKey key,uint16_t generation,uint8_t numHops,uint16_t slot)139 void init(Shape* shape, PropertyKey key, uint16_t generation, 140 uint8_t numHops, uint16_t slot) { 141 shape_ = shape; 142 key_ = key; 143 generation_ = generation; 144 slot_ = slot; 145 numHops_ = numHops; 146 MOZ_ASSERT(slot_ == slot, "slot must fit in slot_"); 147 MOZ_ASSERT(numHops_ == numHops, "numHops must fit in numHops_"); 148 } isMissingProperty()149 bool isMissingProperty() const { 150 return numHops_ == NumHopsForMissingProperty; 151 } isMissingOwnProperty()152 bool isMissingOwnProperty() const { 153 return numHops_ == NumHopsForMissingOwnProperty; 154 } isDataProperty()155 bool isDataProperty() const { return numHops_ <= MaxHopsForDataProperty; } numHops()156 uint16_t numHops() const { 157 MOZ_ASSERT(isDataProperty()); 158 return numHops_; 159 } slot()160 uint16_t slot() const { 161 MOZ_ASSERT(isDataProperty()); 162 return slot_; 163 } 164 }; 165 166 private: 167 static constexpr size_t NumEntries = 1024; 168 mozilla::Array<Entry, NumEntries> entries_; 169 170 // Generation counter used to invalidate all entries. 171 uint16_t generation_ = 0; 172 getEntry(Shape * shape,PropertyKey key)173 Entry& getEntry(Shape* shape, PropertyKey key) { 174 static_assert(mozilla::IsPowerOfTwo(NumEntries), 175 "NumEntries must be a power-of-two for fast modulo"); 176 uintptr_t hash = (uintptr_t(shape) ^ (uintptr_t(shape) >> 13)) + 177 HashAtomOrSymbolPropertyKey(key); 178 return entries_[hash % NumEntries]; 179 } 180 181 public: bumpGeneration()182 void bumpGeneration() { 183 generation_++; 184 if (generation_ == 0) { 185 // Generation overflowed. Invalidate the whole cache. 186 for (size_t i = 0; i < NumEntries; i++) { 187 entries_[i].shape_ = nullptr; 188 } 189 } 190 } lookup(Shape * shape,PropertyKey key,Entry ** entryp)191 bool lookup(Shape* shape, PropertyKey key, Entry** entryp) { 192 Entry& entry = getEntry(shape, key); 193 *entryp = &entry; 194 return (entry.shape_ == shape && entry.key_ == key && 195 entry.generation_ == generation_); 196 } initEntryForMissingProperty(Entry * entry,Shape * shape,PropertyKey key)197 void initEntryForMissingProperty(Entry* entry, Shape* shape, 198 PropertyKey key) { 199 entry->init(shape, key, generation_, Entry::NumHopsForMissingProperty, 0); 200 } initEntryForMissingOwnProperty(Entry * entry,Shape * shape,PropertyKey key)201 void initEntryForMissingOwnProperty(Entry* entry, Shape* shape, 202 PropertyKey key) { 203 entry->init(shape, key, generation_, Entry::NumHopsForMissingOwnProperty, 204 0); 205 } initEntryForDataProperty(Entry * entry,Shape * shape,PropertyKey key,size_t numHops,uint32_t slot)206 void initEntryForDataProperty(Entry* entry, Shape* shape, PropertyKey key, 207 size_t numHops, uint32_t slot) { 208 if (slot > Entry::MaxSlotNumber || 209 numHops > Entry::MaxHopsForDataProperty) { 210 return; 211 } 212 entry->init(shape, key, generation_, numHops, slot); 213 } 214 }; 215 216 // Cache for AtomizeString, mapping JSLinearString* to the corresponding 217 // JSAtom*. Also used by nursery GC to de-duplicate strings to atoms. 218 // Purged on minor and major GC. 219 class StringToAtomCache { 220 using Map = HashMap<JSLinearString*, JSAtom*, PointerHasher<JSLinearString*>, 221 SystemAllocPolicy>; 222 Map map_; 223 224 public: 225 // Don't use the cache for short strings. Hashing them is less expensive. 226 static constexpr size_t MinStringLength = 30; 227 lookup(JSLinearString * s)228 JSAtom* lookup(JSLinearString* s) { 229 MOZ_ASSERT(!s->isAtom()); 230 if (!s->inStringToAtomCache()) { 231 MOZ_ASSERT(!map_.lookup(s)); 232 return nullptr; 233 } 234 235 MOZ_ASSERT(s->length() >= MinStringLength); 236 237 auto p = map_.lookup(s); 238 JSAtom* atom = p ? p->value() : nullptr; 239 MOZ_ASSERT_IF(atom, EqualStrings(s, atom)); 240 return atom; 241 } 242 maybePut(JSLinearString * s,JSAtom * atom)243 void maybePut(JSLinearString* s, JSAtom* atom) { 244 MOZ_ASSERT(!s->isAtom()); 245 if (s->length() < MinStringLength) { 246 return; 247 } 248 if (!map_.putNew(s, atom)) { 249 return; 250 } 251 s->setInStringToAtomCache(); 252 } 253 purge()254 void purge() { map_.clearAndCompact(); } 255 }; 256 257 class RuntimeCaches { 258 public: 259 MegamorphicCache megamorphicCache; 260 GSNCache gsnCache; 261 UncompressedSourceCache uncompressedSourceCache; 262 EvalCache evalCache; 263 StringToAtomCache stringToAtomCache; 264 265 // This cache is used to store the result of delazification compilations which 266 // might be happening off-thread. The main-thread will concurrently read the 267 // content of this cache to avoid delazification, or fallback on running the 268 // delazification on the main-thread. 269 // 270 // Main-thread results are not stored in the StencilCache as there is no other 271 // consumer. 272 StencilCache delazificationCache; 273 sweepAfterMinorGC(JSTracer * trc)274 void sweepAfterMinorGC(JSTracer* trc) { evalCache.traceWeak(trc); } 275 #ifdef JSGC_HASH_TABLE_CHECKS 276 void checkEvalCacheAfterMinorGC(); 277 #endif 278 purgeForCompaction()279 void purgeForCompaction() { 280 evalCache.clear(); 281 stringToAtomCache.purge(); 282 megamorphicCache.bumpGeneration(); 283 } 284 purgeStencils()285 void purgeStencils() { delazificationCache.clearAndDisable(); } 286 purge()287 void purge() { 288 purgeForCompaction(); 289 gsnCache.purge(); 290 uncompressedSourceCache.purge(); 291 purgeStencils(); 292 } 293 }; 294 295 } // namespace js 296 297 #endif /* vm_Caches_h */ 298