/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Pretenuring.
 *
 * Some kinds of GC cells can be allocated in either the nursery or the tenured
 * heap. The pretenuring system decides where to allocate such cells based on
 * their expected lifetime with the aim of minimising total collection time.
 *
 * Lifetime is predicted based on data gathered about the cells' allocation
 * site. This data is gathered in the middle JIT tiers, after code has stopped
 * executing in the interpreter and before we generate fully optimized code.
 */

#ifndef gc_Pretenuring_h
#define gc_Pretenuring_h

#include <algorithm>

#include "gc/AllocKind.h"
#include "js/TypeDecls.h"

class JS_PUBLIC_API JSTracer;

namespace JS {
enum class GCReason;
}  // namespace JS

namespace js::gc {

struct AllocSiteFilter;
class GCRuntime;
class PretenuringNursery;

// Number of trace kinds supportd by the nursery. These are arranged at the
// start of JS::TraceKind.
static constexpr size_t NurseryTraceKinds = 4;

// The number of nursery allocations at which to pay attention to an allocation
// site. This must be large enough to ensure we have enough information to infer
// the lifetime and also large enough to avoid pretenuring low volume allocation
// sites.
static constexpr size_t NormalSiteAttentionThreshold = 200;
static constexpr size_t UnknownSiteAttentionThreshold = 30000;

enum class CatchAllAllocSite { Unknown, Optimized };

// Information about an allocation site.
//
// Nursery cells contain a pointer to one of these in their cell header (stored
// before the cell). The site can relate to either a specific JS bytecode
// instruction, a specific WebAssembly type, or can be a catch-all instance for
// unknown sites or JS JIT optimized code.
class AllocSite {
 public:
  enum class Kind : uint32_t {
    Normal = 0,
    Unknown = 1,
    Optimized = 2,
    Missing = 3,
    Tenuring = 4,
  };
  enum class State : uint32_t { Unknown = 0, LongLived = 1, ShortLived = 2 };

  // We can convert between state and heap by extracting a single bit.
  static constexpr int32_t LONG_LIVED_BIT = 1;
  static_assert((uint32_t(State::Unknown) & LONG_LIVED_BIT) ==
                uint32_t(Heap::Default));
  static_assert((uint32_t(State::LongLived) & LONG_LIVED_BIT) ==
                uint32_t(Heap::Tenured));
  static_assert((uint32_t(State::ShortLived) & LONG_LIVED_BIT) ==
                uint32_t(Heap::Default));

 private:
  JS::Zone* zone_ = nullptr;

  // Word storing JSScript pointer and site state.
  //
  // The script pointer is the script that owns this allocation site, a special
  // sentinel script for wasm sites, or null for unknown sites. This is used
  // when we need to invalidate the script.
  uintptr_t scriptAndState = uintptr_t(State::Unknown);
  static constexpr uintptr_t STATE_MASK = BitMask(2);

  // Next pointer forming a linked list of sites which will have reached the
  // allocation threshold and will be processed at the end of the next nursery
  // collection.
  AllocSite* nextNurseryAllocated = nullptr;

  // Bytecode offset of this allocation site. Only valid if hasScript().
  // Note that the offset does not need to correspond with the script stored in
  // this AllocSite, because if we're doing trial-inlining, the script will be
  // the outer script and the pc offset can be in an inlined script.
  uint32_t pcOffset_ : 29;
  static constexpr uint32_t InvalidPCOffset = Bit(29) - 1;

  uint32_t kind_ : 3;

  // Number of nursery allocations at this site since it was last processed by
  // processSite().
  uint32_t nurseryAllocCount = 0;

  // Number of nursery allocations at this site that were promoted since it was
  // last processed by processSite().
  uint32_t nurseryPromotedCount : 24;

  // Number of times the script has been invalidated.
  uint32_t invalidationCount : 4;

  // The trace kind of the allocation. Only kinds up to NurseryTraceKinds are
  // allowed.
  uint32_t traceKind_ : 4;

  static AllocSite* const EndSentinel;

  // Sentinel script for wasm sites.
  static JSScript* const WasmScript;

  friend class PretenuringZone;
  friend class PretenuringNursery;

  uintptr_t rawScript() const { return scriptAndState & ~STATE_MASK; }

 public:
  static constexpr uint32_t EnvSitePCOffset = InvalidPCOffset - 1;
  static constexpr uint32_t MaxValidPCOffset = EnvSitePCOffset - 1;

  // Default constructor. Clients must call one of the init methods afterwards.
  AllocSite()
      : pcOffset_(InvalidPCOffset),
        kind_(uint32_t(Kind::Unknown)),
        nurseryPromotedCount(0),
        invalidationCount(0),
        traceKind_(0) {}

  // Create a site for an opcode in the given script.
  AllocSite(JS::Zone* zone, JSScript* script, uint32_t pcOffset,
            JS::TraceKind traceKind, Kind siteKind = Kind::Normal)
      : zone_(zone),
        pcOffset_(pcOffset),
        kind_(uint32_t(siteKind)),
        nurseryPromotedCount(0),
        invalidationCount(0),
        traceKind_(uint32_t(traceKind)) {
    MOZ_ASSERT(pcOffset <= MaxValidPCOffset || pcOffset == EnvSitePCOffset);
    MOZ_ASSERT(pcOffset_ == pcOffset);
    setScript(script);
  }

  ~AllocSite() {
    MOZ_ASSERT(!isInAllocatedList());
    MOZ_ASSERT(nurseryAllocCount < NormalSiteAttentionThreshold);
    MOZ_ASSERT(nurseryPromotedCount < NormalSiteAttentionThreshold);
  }

  void initUnknownSite(JS::Zone* zone, JS::TraceKind traceKind) {
    assertUninitialized();
    zone_ = zone;
    traceKind_ = uint32_t(traceKind);
    MOZ_ASSERT(traceKind_ < NurseryTraceKinds);
  }

  void initOptimizedSite(JS::Zone* zone) {
    assertUninitialized();
    zone_ = zone;
    kind_ = uint32_t(Kind::Optimized);
  }

  void initTenuringSite(JS::Zone* zone) {
    assertUninitialized();
    zone_ = zone;
    scriptAndState = uintptr_t(State::LongLived);
    kind_ = uint32_t(Kind::Tenuring);
  }

  // Initialize a site to be a wasm site.
  void initWasm(JS::Zone* zone) {
    assertUninitialized();
    zone_ = zone;
    kind_ = uint32_t(Kind::Normal);
    setScript(WasmScript);
    traceKind_ = uint32_t(JS::TraceKind::Object);
  }

  void assertUninitialized() {
#ifdef DEBUG
    MOZ_ASSERT(!zone_);
    MOZ_ASSERT(isUnknown());
    MOZ_ASSERT(scriptAndState == uintptr_t(State::Unknown));
    MOZ_ASSERT(nurseryPromotedCount == 0);
    MOZ_ASSERT(invalidationCount == 0);
#endif
  }

  static void staticAsserts();

  JS::Zone* zone() const { return zone_; }

  JS::TraceKind traceKind() const { return JS::TraceKind(traceKind_); }

  State state() const { return State(scriptAndState & STATE_MASK); }

  // Whether this site has a script associated with it. This is not true if
  // this site is for a wasm site.
  bool hasScript() const {
    return rawScript() && rawScript() != uintptr_t(WasmScript);
  }
  JSScript* script() const {
    MOZ_ASSERT(hasScript());
    return reinterpret_cast<JSScript*>(rawScript());
  }

  uint32_t pcOffset() const {
    MOZ_ASSERT(hasScript());
    MOZ_ASSERT(pcOffset_ != InvalidPCOffset);
    return pcOffset_;
  }

  bool isNormal() const { return kind() == Kind::Normal; }
  bool isUnknown() const { return kind() == Kind::Unknown; }
  bool isOptimized() const { return kind() == Kind::Optimized; }
  bool isMissing() const { return kind() == Kind::Missing; }
  bool isTenuring() const { return kind() == Kind::Tenuring; }

  Kind kind() const {
    MOZ_ASSERT((Kind(kind_) == Kind::Normal || Kind(kind_) == Kind::Missing) ==
               (rawScript() != 0));
    return Kind(kind_);
  }

  bool isInAllocatedList() const { return nextNurseryAllocated; }

  // Whether allocations at this site should be allocated in the nursery or the
  // tenured heap.
  Heap initialHeap() const {
    Heap heap = Heap(uint32_t(state()) & LONG_LIVED_BIT);
    MOZ_ASSERT_IF(isTenuring(), heap == Heap::Tenured);
    MOZ_ASSERT_IF(!isTenuring() && !isNormal(), heap == Heap::Default);
    return heap;
  }

  bool hasNurseryAllocations() const {
    return nurseryAllocCount != 0 || nurseryPromotedCount != 0;
  }
  void resetNurseryAllocations() {
    nurseryAllocCount = 0;
    nurseryPromotedCount = 0;
  }

  uint32_t incAllocCount() { return ++nurseryAllocCount; }
  uint32_t* nurseryAllocCountAddress() { return &nurseryAllocCount; }

  void incPromotedCount() {
    // The nursery is not large enough for this to overflow.
    nurseryPromotedCount++;
    MOZ_ASSERT(nurseryPromotedCount != 0);
  }

  size_t allocCount() const {
    return std::max(nurseryAllocCount, nurseryPromotedCount);
  }

  // Called for every active alloc site after minor GC.
  enum SiteResult { NoChange, WasPretenured, WasPretenuredAndInvalidated };
  SiteResult processSite(GCRuntime* gc, size_t attentionThreshold,
                         const AllocSiteFilter& reportFilter);
  void processMissingSite(const AllocSiteFilter& reportFilter);
  void processCatchAllSite(const AllocSiteFilter& reportFilter);

  void updateStateOnMinorGC(double promotionRate);

  // Reset the state to 'Unknown' unless we have reached the invalidation limit
  // for this site. Return whether the state was reset.
  bool maybeResetState();

  bool invalidationLimitReached() const;
  bool invalidateScript(GCRuntime* gc);

  void trace(JSTracer* trc);
  bool traceWeak(JSTracer* trc);
  bool needsSweep(JSTracer* trc) const;

  static void printInfoHeader(GCRuntime* gc, JS::GCReason reason,
                              double promotionRate);
  static void printInfoFooter(size_t sitesCreated, size_t sitesActive,
                              size_t sitesPretenured, size_t sitesInvalidated);
  void printInfo(bool hasPromotionRate, double promotionRate,
                 bool wasInvalidated) const;

  static constexpr size_t offsetOfScriptAndState() {
    return offsetof(AllocSite, scriptAndState);
  }
  static constexpr size_t offsetOfNurseryAllocCount() {
    return offsetof(AllocSite, nurseryAllocCount);
  }
  static constexpr size_t offsetOfNextNurseryAllocated() {
    return offsetof(AllocSite, nextNurseryAllocated);
  }

 private:
  void setScript(JSScript* newScript) {
    MOZ_ASSERT((uintptr_t(newScript) & STATE_MASK) == 0);
    scriptAndState = uintptr_t(newScript) | uintptr_t(state());
  }

  void setState(State newState) {
    MOZ_ASSERT((uintptr_t(newState) & ~STATE_MASK) == 0);
    scriptAndState = rawScript() | uintptr_t(newState);
  }

  const char* stateName() const;
};

// Pretenuring information stored per zone.
class PretenuringZone {
 public:
  // Catch-all allocation site instance used when the actual site is unknown, or
  // when optimized JIT code allocates a GC thing that's not handled by the
  // pretenuring system.
  AllocSite unknownAllocSites[NurseryTraceKinds];

  // Catch-all allocation instance used by optimized JIT code when allocating GC
  // things that are handled by the pretenuring system.  Allocation counts are
  // not recorded by optimized JIT code.
  AllocSite optimizedAllocSite;

  // Alloc Site which always tenure allocates. Used to avoid type punning
  // when JIT-compiling for the Realm local allocation site.
  AllocSite tenuringAllocSite;

  // Allocation sites used for nursery cells promoted to the next nursery
  // generation that didn't come from optimized alloc sites.
  AllocSite promotedAllocSites[NurseryTraceKinds];

  // Count of tenured cell allocations made between each major collection and
  // how many survived.
  uint32_t allocCountInNewlyCreatedArenas = 0;
  uint32_t survivorCountInNewlyCreatedArenas = 0;

  // Count of successive collections that had a low young tenured survival
  // rate. Used to discard optimized code if we get the pretenuring decision
  // wrong.
  uint32_t lowYoungTenuredSurvivalCount = 0;

  // Count of successive nursery collections that had a high survival rate for
  // objects allocated by optimized code. Used to discard optimized code if we
  // get the pretenuring decision wrong.
  uint32_t highNurserySurvivalCount = 0;

  // Total promotion count by trace kind. Calculated during nursery collection.
  uint32_t nurseryPromotedCounts[NurseryTraceKinds] = {0};

  explicit PretenuringZone(JS::Zone* zone) {
    for (uint32_t i = 0; i < NurseryTraceKinds; i++) {
      unknownAllocSites[i].initUnknownSite(zone, JS::TraceKind(i));
      promotedAllocSites[i].initUnknownSite(zone, JS::TraceKind(i));
    }
    optimizedAllocSite.initOptimizedSite(zone);
    tenuringAllocSite.initTenuringSite(zone);
  }

  AllocSite& unknownAllocSite(JS::TraceKind kind) {
    size_t i = size_t(kind);
    MOZ_ASSERT(i < NurseryTraceKinds);
    return unknownAllocSites[i];
  }

  AllocSite& promotedAllocSite(JS::TraceKind kind) {
    size_t i = size_t(kind);
    MOZ_ASSERT(i < NurseryTraceKinds);
    return promotedAllocSites[i];
  }

  void clearCellCountsInNewlyCreatedArenas() {
    allocCountInNewlyCreatedArenas = 0;
    survivorCountInNewlyCreatedArenas = 0;
  }
  void updateCellCountsInNewlyCreatedArenas(uint32_t allocCount,
                                            uint32_t survivorCount) {
    allocCountInNewlyCreatedArenas += allocCount;
    survivorCountInNewlyCreatedArenas += survivorCount;
  }

  bool calculateYoungTenuredSurvivalRate(double* rateOut);

  void noteLowYoungTenuredSurvivalRate(bool lowYoungSurvivalRate);
  void noteHighNurserySurvivalRate(bool highNurserySurvivalRate);

  // Recovery: if code behaviour change we may need to reset allocation site
  // state and invalidate JIT code.
  bool shouldResetNurseryAllocSites();
  bool shouldResetPretenuredAllocSites();

  uint32_t nurseryPromotedCount(JS::TraceKind kind) const {
    size_t i = size_t(kind);
    MOZ_ASSERT(i < std::size(nurseryPromotedCounts));
    return nurseryPromotedCounts[i];
  }
};

// Pretenuring information stored as part of the the GC nursery.
class PretenuringNursery {
  AllocSite* allocatedSites;

  size_t allocSitesCreated = 0;

  uint32_t totalAllocCount_ = 0;

 public:
  PretenuringNursery() : allocatedSites(AllocSite::EndSentinel) {}

  bool hasAllocatedSites() const {
    return allocatedSites != AllocSite::EndSentinel;
  }

  bool canCreateAllocSite();
  void noteAllocSiteCreated() { allocSitesCreated++; }

  void insertIntoAllocatedList(AllocSite* site) {
    MOZ_ASSERT(!site->isInAllocatedList());
    site->nextNurseryAllocated = allocatedSites;
    allocatedSites = site;
  }

  size_t doPretenuring(GCRuntime* gc, JS::GCReason reason,
                       bool validPromotionRate, double promotionRate,
                       const AllocSiteFilter& reportFilter);

  void maybeStopPretenuring(GCRuntime* gc);

  uint32_t totalAllocCount() const { return totalAllocCount_; }

  void* addressOfAllocatedSites() { return &allocatedSites; }

 private:
  void updateTotalAllocCounts(AllocSite* site);
};

// Describes which alloc sites to report on, if any.
struct AllocSiteFilter {
  size_t allocThreshold = 0;
  uint8_t siteKindMask = 0;
  uint8_t traceKindMask = 0;
  uint8_t stateMask = 0;
  bool enabled = false;

  bool matches(const AllocSite& site) const;

  static bool readFromString(const char* string, AllocSiteFilter* filter);
};

#ifdef JS_GC_ZEAL

// To help discover good places to add allocation sites, automatically create an
// allocation site for an allocation that didn't supply one.
AllocSite* GetOrCreateMissingAllocSite(JSContext* cx, JSScript* script,
                                       uint32_t pcOffset,
                                       JS::TraceKind traceKind);

#endif  // JS_GC_ZEAL

}  // namespace js::gc

#endif /* gc_Pretenuring_h */