js/src/gc/Pretenuring.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sw=2 et tw=80:
   3  *
   4  * This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   6  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   7
   8 #include "gc/Pretenuring.h"
   9
  10 #include "mozilla/Sprintf.h"
  11
  12 #include "gc/GCInternals.h"
  13 #include "gc/PublicIterators.h"
  14 #include "jit/Invalidation.h"
  15
  16 #include "gc/PrivateIterators-inl.h"
  17 #include "vm/JSScript-inl.h"
  18
  19 using namespace js;
  20 using namespace js::gc;
  21
  22 // The number of nursery allocations at which to pay attention to an allocation
  23 // site. This must be large enough to ensure we have enough information to infer
  24 // the lifetime and also large enough to avoid pretenuring low volume allocation
  25 // sites.
  26 static constexpr size_t AllocSiteAttentionThreshold = 500;
  27
  28 // The maximum number of alloc sites to create between each minor
  29 // collection. Stop tracking allocation after this limit is reached. This
  30 // prevents unbounded time traversing the list during minor GC.
  31 static constexpr size_t MaxAllocSitesPerMinorGC = 500;
  32
  33 // The maximum number of times to invalidate JIT code for a site. After this we
  34 // leave the site's state as Unknown and don't pretenure allocations.
  35 // Note we use 4 bits to store the invalidation count.
  36 static constexpr size_t MaxInvalidationCount = 5;
  37
  38 // The minimum number of allocated cells needed to determine the survival rate
  39 // of cells in newly created arenas.
  40 static constexpr size_t MinCellsRequiredForSurvivalRate = 100;
  41
  42 // The young survival rate below which a major collection is determined to have
  43 // a low young survival rate.
  44 static constexpr double LowYoungSurvivalThreshold = 0.05;
  45
  46 // The number of consecutive major collections with a low young survival rate
  47 // that must occur before recovery is attempted.
  48 static constexpr size_t LowYoungSurvivalCountBeforeRecovery = 2;
  49
  50 // The proportion of the nursery that must be tenured above which a minor
  51 // collection may be determined to have a high nursery survival rate.
  52 static constexpr double HighNurserySurvivalPromotionThreshold = 0.6;
  53
  54 // The number of nursery allocations made by optimized JIT code that must be
  55 // tenured above which a minor collection may be determined to have a high
  56 // nursery survival rate.
  57 static constexpr size_t HighNurserySurvivalOptimizedAllocThreshold = 10000;
  58
  59 // The number of consecutive minor collections with a high nursery survival rate
  60 // that must occur before recovery is attempted.
  61 static constexpr size_t HighNurserySurvivalCountBeforeRecovery = 2;
  62
  63 AllocSite* const AllocSite::EndSentinel = reinterpret_cast<AllocSite*>(1);
  64 JSScript* const AllocSite::WasmScript =
  65     reinterpret_cast<JSScript*>(AllocSite::STATE_MASK + 1);
  66
  67 static bool SiteBasedPretenuringEnabled = true;
  68
  69 JS_PUBLIC_API void JS::SetSiteBasedPretenuringEnabled(bool enable) {
  70   SiteBasedPretenuringEnabled = enable;
  71 }
  72
  73 bool PretenuringNursery::canCreateAllocSite() {
  74   MOZ_ASSERT(allocSitesCreated <= MaxAllocSitesPerMinorGC);
  75   return SiteBasedPretenuringEnabled &&
  76          allocSitesCreated < MaxAllocSitesPerMinorGC;
  77 }
  78
  79 size_t PretenuringNursery::doPretenuring(GCRuntime* gc, JS::GCReason reason,
  80                                          bool validPromotionRate,
  81                                          double promotionRate, bool reportInfo,
  82                                          size_t reportThreshold) {
  83   size_t sitesActive = 0;
  84   size_t sitesPretenured = 0;
  85   size_t sitesInvalidated = 0;
  86   size_t zonesWithHighNurserySurvival = 0;
  87
  88   // Zero allocation counts.
  89   totalAllocCount_ = 0;
  90   for (ZonesIter zone(gc, SkipAtoms); !zone.done(); zone.next()) {
  91     for (auto& count : zone->pretenuring.nurseryAllocCounts) {
  92       count = 0;
  93     }
  94   }
  95
  96   // Check whether previously optimized code has changed its behaviour and
  97   // needs to be recompiled so that it can pretenure its allocations.
  98   if (validPromotionRate) {
  99     for (ZonesIter zone(gc, SkipAtoms); !zone.done(); zone.next()) {
 100       bool highNurserySurvivalRate =
 101           promotionRate > HighNurserySurvivalPromotionThreshold &&
 102           zone->optimizedAllocSite()->nurseryTenuredCount >=
 103               HighNurserySurvivalOptimizedAllocThreshold;
 104       zone->pretenuring.noteHighNurserySurvivalRate(highNurserySurvivalRate);
 105       if (highNurserySurvivalRate) {
 106         zonesWithHighNurserySurvival++;
 107       }
 108     }
 109   }
 110
 111   if (reportInfo) {
 112     AllocSite::printInfoHeader(reason, promotionRate);
 113   }
 114
 115   AllocSite* site = allocatedSites;
 116   allocatedSites = AllocSite::EndSentinel;
 117   while (site != AllocSite::EndSentinel) {
 118     AllocSite* next = site->nextNurseryAllocated;
 119     site->nextNurseryAllocated = nullptr;
 120
 121     MOZ_ASSERT_IF(site->isNormal(),
 122                   site->nurseryAllocCount >= site->nurseryTenuredCount);
 123
 124     if (site->isNormal()) {
 125       processSite(gc, site, sitesActive, sitesPretenured, sitesInvalidated,
 126                   reportInfo, reportThreshold);
 127     }
 128
 129     site = next;
 130   }
 131
 132   // Catch-all sites don't end up on the list if they are only used from
 133   // optimized JIT code, so process them here.
 134   for (ZonesIter zone(gc, SkipAtoms); !zone.done(); zone.next()) {
 135     for (auto& site : zone->pretenuring.unknownAllocSites) {
 136       processCatchAllSite(&site, reportInfo, reportThreshold);
 137     }
 138     processCatchAllSite(zone->optimizedAllocSite(), reportInfo,
 139                         reportThreshold);
 140   }
 141
 142   if (reportInfo) {
 143     AllocSite::printInfoFooter(allocSitesCreated, sitesActive, sitesPretenured,
 144                                sitesInvalidated);
 145     if (zonesWithHighNurserySurvival) {
 146       fprintf(stderr, "  %zu zones with high nursery survival rate\n",
 147               zonesWithHighNurserySurvival);
 148     }
 149   }
 150
 151   allocSitesCreated = 0;
 152
 153   return sitesPretenured;
 154 }
 155
 156 void PretenuringNursery::processSite(GCRuntime* gc, AllocSite* site,
 157                                      size_t& sitesActive,
 158                                      size_t& sitesPretenured,
 159                                      size_t& sitesInvalidated, bool reportInfo,
 160                                      size_t reportThreshold) {
 161   sitesActive++;
 162
 163   updateAllocCounts(site);
 164
 165   bool hasPromotionRate = false;
 166   double promotionRate = 0.0;
 167   bool wasInvalidated = false;
 168   if (site->nurseryAllocCount > AllocSiteAttentionThreshold) {
 169     promotionRate =
 170         double(site->nurseryTenuredCount) / double(site->nurseryAllocCount);
 171     hasPromotionRate = true;
 172
 173     AllocSite::State prevState = site->state();
 174     site->updateStateOnMinorGC(promotionRate);
 175     AllocSite::State newState = site->state();
 176
 177     if (prevState == AllocSite::State::Unknown &&
 178         newState == AllocSite::State::LongLived) {
 179       sitesPretenured++;
 180
 181       // We can optimize JIT code before we realise that a site should be
 182       // pretenured. Make sure we invalidate any existing optimized code.
 183       if (site->hasScript()) {
 184         wasInvalidated = site->invalidateScript(gc);
 185         if (wasInvalidated) {
 186           sitesInvalidated++;
 187         }
 188       }
 189     }
 190   }
 191
 192   if (reportInfo && site->allocCount() >= reportThreshold) {
 193     site->printInfo(hasPromotionRate, promotionRate, wasInvalidated);
 194   }
 195
 196   site->resetNurseryAllocations();
 197 }
 198
 199 void PretenuringNursery::processCatchAllSite(AllocSite* site, bool reportInfo,
 200                                              size_t reportThreshold) {
 201   if (!site->hasNurseryAllocations()) {
 202     return;
 203   }
 204
 205   updateAllocCounts(site);
 206
 207   if (reportInfo && site->allocCount() >= reportThreshold) {
 208     site->printInfo(false, 0.0, false);
 209   }
 210
 211   site->resetNurseryAllocations();
 212 }
 213
 214 void PretenuringNursery::updateAllocCounts(AllocSite* site) {
 215   JS::TraceKind kind = site->traceKind();
 216   totalAllocCount_ += site->nurseryAllocCount;
 217   PretenuringZone& zone = site->zone()->pretenuring;
 218   zone.nurseryAllocCount(kind) += site->nurseryAllocCount;
 219 }
 220
 221 bool AllocSite::invalidateScript(GCRuntime* gc) {
 222   CancelOffThreadIonCompile(script());
 223
 224   if (!script()->hasIonScript()) {
 225     return false;
 226   }
 227
 228   if (invalidationLimitReached()) {
 229     MOZ_ASSERT(state() == State::Unknown);
 230     return false;
 231   }
 232
 233   invalidationCount++;
 234   if (invalidationLimitReached()) {
 235     setState(State::Unknown);
 236   }
 237
 238   JSContext* cx = gc->rt->mainContextFromOwnThread();
 239   jit::Invalidate(cx, script(),
 240                   /* resetUses = */ false,
 241                   /* cancelOffThread = */ true);
 242   return true;
 243 }
 244
 245 bool AllocSite::invalidationLimitReached() const {
 246   MOZ_ASSERT(invalidationCount <= MaxInvalidationCount);
 247   return invalidationCount == MaxInvalidationCount;
 248 }
 249
 250 void PretenuringNursery::maybeStopPretenuring(GCRuntime* gc) {
 251   for (GCZonesIter zone(gc); !zone.done(); zone.next()) {
 252     double rate;
 253     if (zone->pretenuring.calculateYoungTenuredSurvivalRate(&rate)) {
 254       bool lowYoungSurvivalRate = rate < LowYoungSurvivalThreshold;
 255       zone->pretenuring.noteLowYoungTenuredSurvivalRate(lowYoungSurvivalRate);
 256     }
 257   }
 258 }
 259
 260 AllocSite::Kind AllocSite::kind() const {
 261   if (isNormal()) {
 262     return Kind::Normal;
 263   }
 264
 265   if (this == zone()->optimizedAllocSite()) {
 266     return Kind::Optimized;
 267   }
 268
 269   MOZ_ASSERT(this == zone()->unknownAllocSite(traceKind()));
 270   return Kind::Unknown;
 271 }
 272
 273 void AllocSite::updateStateOnMinorGC(double promotionRate) {
 274   // The state changes based on whether the promotion rate is deemed high
 275   // (greater that 90%):
 276   //
 277   //                      high                          high
 278   //               ------------------>           ------------------>
 279   //   ShortLived                       Unknown                        LongLived
 280   //               <------------------           <------------------
 281   //                      !high                         !high
 282   //
 283   // The nursery is used to allocate if the site's state is Unknown or
 284   // ShortLived. There are no direct transition between ShortLived and LongLived
 285   // to avoid pretenuring sites that we've recently observed being short-lived.
 286
 287   if (invalidationLimitReached()) {
 288     MOZ_ASSERT(state() == State::Unknown);
 289     return;
 290   }
 291
 292   bool highPromotionRate = promotionRate >= 0.9;
 293
 294   switch (state()) {
 295     case State::Unknown:
 296       if (highPromotionRate) {
 297         setState(State::LongLived);
 298       } else {
 299         setState(State::ShortLived);
 300       }
 301       break;
 302
 303     case State::ShortLived: {
 304       if (highPromotionRate) {
 305         setState(State::Unknown);
 306       }
 307       break;
 308     }
 309
 310     case State::LongLived: {
 311       if (!highPromotionRate) {
 312         setState(State::Unknown);
 313       }
 314       break;
 315     }
 316   }
 317 }
 318
 319 bool AllocSite::maybeResetState() {
 320   if (invalidationLimitReached()) {
 321     MOZ_ASSERT(state() == State::Unknown);
 322     return false;
 323   }
 324
 325   invalidationCount++;
 326   setState(State::Unknown);
 327   return true;
 328 }
 329
 330 void AllocSite::trace(JSTracer* trc) {
 331   if (JSScript* s = script()) {
 332     TraceManuallyBarrieredEdge(trc, &s, "AllocSite script");
 333     if (s != script()) {
 334       setScript(s);
 335     }
 336   }
 337 }
 338
 339 bool PretenuringZone::calculateYoungTenuredSurvivalRate(double* rateOut) {
 340   MOZ_ASSERT(allocCountInNewlyCreatedArenas >=
 341              survivorCountInNewlyCreatedArenas);
 342   if (allocCountInNewlyCreatedArenas < MinCellsRequiredForSurvivalRate) {
 343     return false;
 344   }
 345
 346   *rateOut = double(survivorCountInNewlyCreatedArenas) /
 347              double(allocCountInNewlyCreatedArenas);
 348   return true;
 349 }
 350
 351 void PretenuringZone::noteLowYoungTenuredSurvivalRate(
 352     bool lowYoungSurvivalRate) {
 353   if (lowYoungSurvivalRate) {
 354     lowYoungTenuredSurvivalCount++;
 355   } else {
 356     lowYoungTenuredSurvivalCount = 0;
 357   }
 358 }
 359
 360 void PretenuringZone::noteHighNurserySurvivalRate(
 361     bool highNurserySurvivalRate) {
 362   if (highNurserySurvivalRate) {
 363     highNurserySurvivalCount++;
 364   } else {
 365     highNurserySurvivalCount = 0;
 366   }
 367 }
 368
 369 bool PretenuringZone::shouldResetNurseryAllocSites() {
 370   bool shouldReset =
 371       highNurserySurvivalCount >= HighNurserySurvivalCountBeforeRecovery;
 372   if (shouldReset) {
 373     highNurserySurvivalCount = 0;
 374   }
 375   return shouldReset;
 376 }
 377
 378 bool PretenuringZone::shouldResetPretenuredAllocSites() {
 379   bool shouldReset =
 380       lowYoungTenuredSurvivalCount >= LowYoungSurvivalCountBeforeRecovery;
 381   if (shouldReset) {
 382     lowYoungTenuredSurvivalCount = 0;
 383   }
 384   return shouldReset;
 385 }
 386
 387 /* static */
 388 void AllocSite::printInfoHeader(JS::GCReason reason, double promotionRate) {
 389   fprintf(stderr,
 390           "Pretenuring info after %s minor GC with %4.1f%% promotion rate:\n",
 391           ExplainGCReason(reason), promotionRate * 100.0);
 392 }
 393
 394 /* static */
 395 void AllocSite::printInfoFooter(size_t sitesCreated, size_t sitesActive,
 396                                 size_t sitesPretenured,
 397                                 size_t sitesInvalidated) {
 398   fprintf(stderr,
 399           "  %zu alloc sites created, %zu active, %zu pretenured, %zu "
 400           "invalidated\n",
 401           sitesCreated, sitesActive, sitesPretenured, sitesInvalidated);
 402 }
 403
 404 void AllocSite::printInfo(bool hasPromotionRate, double promotionRate,
 405                           bool wasInvalidated) const {
 406   // Zone.
 407   fprintf(stderr, "  %p %p", this, zone());
 408
 409   // Script, or which kind of catch-all site this is.
 410   if (!hasScript()) {
 411     fprintf(stderr, " %16s",
 412             kind() == Kind::Optimized
 413                 ? "optimized"
 414                 : (kind() == Kind::Normal ? "normal" : "unknown"));
 415   } else {
 416     fprintf(stderr, " %16p", script());
 417   }
 418
 419   // Nursery allocation count, missing for optimized sites.
 420   char buffer[16] = {'\0'};
 421   if (kind() != Kind::Optimized) {
 422     SprintfLiteral(buffer, "%8" PRIu32, nurseryAllocCount);
 423   }
 424   fprintf(stderr, " %8s", buffer);
 425
 426   // Nursery tenure count.
 427   fprintf(stderr, " %8" PRIu32, nurseryTenuredCount);
 428
 429   // Promotion rate, if there were enough allocations.
 430   buffer[0] = '\0';
 431   if (hasPromotionRate) {
 432     SprintfLiteral(buffer, "%5.1f%%", std::min(1.0, promotionRate) * 100);
 433   }
 434   fprintf(stderr, " %6s", buffer);
 435
 436   // Current state for sites associated with a script.
 437   const char* state = isNormal() ? stateName() : "";
 438   fprintf(stderr, " %10s", state);
 439
 440   // Whether the associated script was invalidated.
 441   if (wasInvalidated) {
 442     fprintf(stderr, " invalidated");
 443   }
 444
 445   fprintf(stderr, "\n");
 446 }
 447
 448 const char* AllocSite::stateName() const {
 449   switch (state()) {
 450     case State::ShortLived:
 451       return "ShortLived";
 452     case State::Unknown:
 453       return "Unknown";
 454     case State::LongLived:
 455       return "LongLived";
 456   }
 457
 458   MOZ_CRASH("Unknown state");
 459 }