js/src/gc/Pretenuring.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 /*
   8  * Pretenuring.
   9  *
  10  * Some kinds of GC cells can be allocated in either the nursery or the tenured
  11  * heap. The pretenuring system decides where to allocate such cells based on
  12  * their expected lifetime with the aim of minimising total collection time.
  13  *
  14  * Lifetime is predicted based on data gathered about the cells' allocation
  15  * site. This data is gathered in the middle JIT tiers, after code has stopped
  16  * executing in the interpreter and before we generate fully optimized code.
  17  */
  18
  19 #ifndef gc_Pretenuring_h
  20 #define gc_Pretenuring_h
  21
  22 #include <algorithm>
  23
  24 #include "gc/AllocKind.h"
  25 #include "js/TypeDecls.h"
  26
  27 class JS_PUBLIC_API JSTracer;
  28
  29 namespace JS {
  30 enum class GCReason;
  31 }  // namespace JS
  32
  33 namespace js::gc {
  34
  35 class GCRuntime;
  36 class PretenuringNursery;
  37
  38 // Number of trace kinds supportd by the nursery. These are arranged at the
  39 // start of JS::TraceKind.
  40 static constexpr size_t NurseryTraceKinds = 3;
  41
  42 enum class CatchAllAllocSite { Unknown, Optimized };
  43
  44 // Information about an allocation site.
  45 //
  46 // Nursery cells contain a pointer to one of these in their cell header (stored
  47 // before the cell). The site can relate to either a specific JS bytecode
  48 // instruction, a specific WebAssembly type, or can be a catch-all instance for
  49 // unknown sites or JS JIT optimized code.
  50 class AllocSite {
  51  public:
  52   enum class State : uint32_t { ShortLived = 0, Unknown = 1, LongLived = 2 };
  53
  54   // The JIT depends on being able to tell the states apart by checking a single
  55   // bit.
  56   static constexpr int32_t LONG_LIVED_BIT = int32_t(State::LongLived);
  57   static_assert((LONG_LIVED_BIT & int32_t(State::Unknown)) == 0);
  58   static_assert((AllocSite::LONG_LIVED_BIT & int32_t(State::ShortLived)) == 0);
  59
  60  private:
  61   JS::Zone* zone_ = nullptr;
  62
  63   // Word storing JSScript pointer and site state.
  64   //
  65   // The script pointer is the script that owns this allocation site, a special
  66   // sentinel script for wasm sites, or null for unknown sites. This is used
  67   // when we need to invalidate the script.
  68   uintptr_t scriptAndState = uintptr_t(State::Unknown);
  69   static constexpr uintptr_t STATE_MASK = BitMask(2);
  70
  71   // Next pointer forming a linked list of sites at which nursery allocation
  72   // happened since the last nursery collection.
  73   AllocSite* nextNurseryAllocated = nullptr;
  74
  75   // Number of nursery allocations at this site since last nursery collection.
  76   uint32_t nurseryAllocCount = 0;
  77
  78   // Number of nursery allocations that survived. Used during collection.
  79   uint32_t nurseryTenuredCount : 24;
  80
  81   // Number of times the script has been invalidated.
  82   uint32_t invalidationCount : 4;
  83
  84   // The trace kind of the allocation. Only kinds up to NurseryTraceKinds are
  85   // allowed.
  86   uint32_t traceKind_ : 4;
  87
  88   static AllocSite* const EndSentinel;
  89
  90   // Sentinel script for wasm sites.
  91   static JSScript* const WasmScript;
  92
  93   friend class PretenuringZone;
  94   friend class PretenuringNursery;
  95
  96   uintptr_t rawScript() const { return scriptAndState & ~STATE_MASK; }
  97
  98  public:
  99   AllocSite() : nurseryTenuredCount(0), invalidationCount(0), traceKind_(0) {}
 100
 101   // Create a dummy site to use for unknown allocations.
 102   explicit AllocSite(JS::Zone* zone, JS::TraceKind kind)
 103       : zone_(zone),
 104         nurseryTenuredCount(0),
 105         invalidationCount(0),
 106         traceKind_(uint32_t(kind)) {
 107     MOZ_ASSERT(traceKind_ < NurseryTraceKinds);
 108   }
 109
 110   // Create a site for an opcode in the given script.
 111   AllocSite(JS::Zone* zone, JSScript* script, JS::TraceKind kind)
 112       : AllocSite(zone, kind) {
 113     MOZ_ASSERT(script != WasmScript);
 114     setScript(script);
 115   }
 116
 117   void initUnknownSite(JS::Zone* zone, JS::TraceKind kind) {
 118     MOZ_ASSERT(!zone_ && scriptAndState == uintptr_t(State::Unknown));
 119     zone_ = zone;
 120     nurseryTenuredCount = 0;
 121     invalidationCount = 0;
 122     traceKind_ = uint32_t(kind);
 123     MOZ_ASSERT(traceKind_ < NurseryTraceKinds);
 124   }
 125
 126   // Initialize a site to be a wasm site.
 127   void initWasm(JS::Zone* zone) {
 128     MOZ_ASSERT(!zone_ && scriptAndState == uintptr_t(State::Unknown));
 129     zone_ = zone;
 130     setScript(WasmScript);
 131     nurseryTenuredCount = 0;
 132     invalidationCount = 0;
 133     traceKind_ = uint32_t(JS::TraceKind::Object);
 134   }
 135
 136   JS::Zone* zone() const { return zone_; }
 137
 138   JS::TraceKind traceKind() const { return JS::TraceKind(traceKind_); }
 139
 140   State state() const { return State(scriptAndState & STATE_MASK); }
 141
 142   // Whether this site has a script associated with it. This is not true if
 143   // this site is for a wasm site.
 144   bool hasScript() const { return rawScript() != uintptr_t(WasmScript); }
 145   JSScript* script() const {
 146     MOZ_ASSERT(hasScript());
 147     return reinterpret_cast<JSScript*>(rawScript());
 148   }
 149
 150   // Whether this site is not an unknown or optimized site.
 151   bool isNormal() const { return rawScript() != 0; }
 152
 153   enum class Kind : uint32_t { Normal, Unknown, Optimized };
 154   Kind kind() const;
 155
 156   bool isInAllocatedList() const { return nextNurseryAllocated; }
 157
 158   // Whether allocations at this site should be allocated in the nursery or the
 159   // tenured heap.
 160   Heap initialHeap() const {
 161     return state() == State::LongLived ? Heap::Tenured : Heap::Default;
 162   }
 163
 164   bool hasNurseryAllocations() const {
 165     return nurseryAllocCount != 0 || nurseryTenuredCount != 0;
 166   }
 167   void resetNurseryAllocations() {
 168     nurseryAllocCount = 0;
 169     nurseryTenuredCount = 0;
 170   }
 171
 172   uint32_t incAllocCount() { return ++nurseryAllocCount; }
 173   uint32_t* nurseryAllocCountAddress() { return &nurseryAllocCount; }
 174
 175   void incTenuredCount() {
 176     // The nursery is not large enough for this to overflow.
 177     nurseryTenuredCount++;
 178     MOZ_ASSERT(nurseryTenuredCount != 0);
 179   }
 180
 181   size_t allocCount() const {
 182     return std::max(nurseryAllocCount, nurseryTenuredCount);
 183   }
 184
 185   void updateStateOnMinorGC(double promotionRate);
 186
 187   // Reset the state to 'Unknown' unless we have reached the invalidation limit
 188   // for this site. Return whether the state was reset.
 189   bool maybeResetState();
 190
 191   bool invalidationLimitReached() const;
 192   bool invalidateScript(GCRuntime* gc);
 193
 194   void trace(JSTracer* trc);
 195
 196   static void printInfoHeader(JS::GCReason reason, double promotionRate);
 197   static void printInfoFooter(size_t sitesCreated, size_t sitesActive,
 198                               size_t sitesPretenured, size_t sitesInvalidated);
 199   void printInfo(bool hasPromotionRate, double promotionRate,
 200                  bool wasInvalidated) const;
 201
 202   static constexpr size_t offsetOfScriptAndState() {
 203     return offsetof(AllocSite, scriptAndState);
 204   }
 205   static constexpr size_t offsetOfNurseryAllocCount() {
 206     return offsetof(AllocSite, nurseryAllocCount);
 207   }
 208   static constexpr size_t offsetOfNextNurseryAllocated() {
 209     return offsetof(AllocSite, nextNurseryAllocated);
 210   }
 211
 212  private:
 213   void setScript(JSScript* newScript) {
 214     MOZ_ASSERT((uintptr_t(newScript) & STATE_MASK) == 0);
 215     scriptAndState = uintptr_t(newScript) | uintptr_t(state());
 216   }
 217
 218   void setState(State newState) {
 219     MOZ_ASSERT((uintptr_t(newState) & ~STATE_MASK) == 0);
 220     scriptAndState = rawScript() | uintptr_t(newState);
 221   }
 222
 223   const char* stateName() const;
 224 };
 225
 226 // Pretenuring information stored per zone.
 227 class PretenuringZone {
 228  public:
 229   // Catch-all allocation site instance used when the actual site is unknown, or
 230   // when optimized JIT code allocates a GC thing that's not handled by the
 231   // pretenuring system.
 232   AllocSite unknownAllocSites[NurseryTraceKinds];
 233
 234   // Catch-all allocation instance used by optimized JIT code when allocating GC
 235   // things that are handled by the pretenuring system.  Allocation counts are
 236   // not recorded by optimized JIT code.
 237   AllocSite optimizedAllocSite;
 238
 239   // Count of tenured cell allocations made between each major collection and
 240   // how many survived.
 241   uint32_t allocCountInNewlyCreatedArenas = 0;
 242   uint32_t survivorCountInNewlyCreatedArenas = 0;
 243
 244   // Count of successive collections that had a low young tenured survival
 245   // rate. Used to discard optimized code if we get the pretenuring decision
 246   // wrong.
 247   uint32_t lowYoungTenuredSurvivalCount = 0;
 248
 249   // Count of successive nursery collections that had a high survival rate for
 250   // objects allocated by optimized code. Used to discard optimized code if we
 251   // get the pretenuring decision wrong.
 252   uint32_t highNurserySurvivalCount = 0;
 253
 254   // Total allocation count by trace kind (ignoring optimized
 255   // allocations). Calculated during nursery collection.
 256   uint32_t nurseryAllocCounts[NurseryTraceKinds] = {0};
 257
 258   explicit PretenuringZone(JS::Zone* zone)
 259       : optimizedAllocSite(zone, JS::TraceKind::Object) {
 260     for (uint32_t i = 0; i < NurseryTraceKinds; i++) {
 261       unknownAllocSites[i].initUnknownSite(zone, JS::TraceKind(i));
 262     }
 263   }
 264
 265   AllocSite& unknownAllocSite(JS::TraceKind kind) {
 266     size_t i = size_t(kind);
 267     MOZ_ASSERT(i < NurseryTraceKinds);
 268     return unknownAllocSites[i];
 269   }
 270
 271   void clearCellCountsInNewlyCreatedArenas() {
 272     allocCountInNewlyCreatedArenas = 0;
 273     survivorCountInNewlyCreatedArenas = 0;
 274   }
 275   void updateCellCountsInNewlyCreatedArenas(uint32_t allocCount,
 276                                             uint32_t survivorCount) {
 277     allocCountInNewlyCreatedArenas += allocCount;
 278     survivorCountInNewlyCreatedArenas += survivorCount;
 279   }
 280
 281   bool calculateYoungTenuredSurvivalRate(double* rateOut);
 282
 283   void noteLowYoungTenuredSurvivalRate(bool lowYoungSurvivalRate);
 284   void noteHighNurserySurvivalRate(bool highNurserySurvivalRate);
 285
 286   // Recovery: if code behaviour change we may need to reset allocation site
 287   // state and invalidate JIT code.
 288   bool shouldResetNurseryAllocSites();
 289   bool shouldResetPretenuredAllocSites();
 290
 291   uint32_t& nurseryAllocCount(JS::TraceKind kind) {
 292     size_t i = size_t(kind);
 293     MOZ_ASSERT(i < NurseryTraceKinds);
 294     return nurseryAllocCounts[i];
 295   }
 296   uint32_t nurseryAllocCount(JS::TraceKind kind) const {
 297     return const_cast<PretenuringZone*>(this)->nurseryAllocCount(kind);
 298   }
 299 };
 300
 301 // Pretenuring information stored as part of the the GC nursery.
 302 class PretenuringNursery {
 303   gc::AllocSite* allocatedSites;
 304
 305   size_t allocSitesCreated = 0;
 306
 307   uint32_t totalAllocCount_ = 0;
 308
 309  public:
 310   PretenuringNursery() : allocatedSites(AllocSite::EndSentinel) {}
 311
 312   bool hasAllocatedSites() const {
 313     return allocatedSites != AllocSite::EndSentinel;
 314   }
 315
 316   bool canCreateAllocSite();
 317   void noteAllocSiteCreated() { allocSitesCreated++; }
 318
 319   void insertIntoAllocatedList(AllocSite* site) {
 320     MOZ_ASSERT(!site->isInAllocatedList());
 321     site->nextNurseryAllocated = allocatedSites;
 322     allocatedSites = site;
 323   }
 324
 325   size_t doPretenuring(GCRuntime* gc, JS::GCReason reason,
 326                        bool validPromotionRate, double promotionRate,
 327                        bool reportInfo, size_t reportThreshold);
 328
 329   void maybeStopPretenuring(GCRuntime* gc);
 330
 331   uint32_t totalAllocCount() const { return totalAllocCount_; }
 332
 333   void* addressOfAllocatedSites() { return &allocatedSites; }
 334
 335  private:
 336   void processSite(GCRuntime* gc, AllocSite* site, size_t& sitesActive,
 337                    size_t& sitesPretenured, size_t& sitesInvalidated,
 338                    bool reportInfo, size_t reportThreshold);
 339   void processCatchAllSite(AllocSite* site, bool reportInfo,
 340                            size_t reportThreshold);
 341   void updateAllocCounts(AllocSite* site);
 342 };
 343
 344 }  // namespace js::gc
 345
 346 #endif /* gc_Pretenuring_h */