Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1235 insertions, 0 deletions

diff --git a/js/src/jit/JitcodeMap.h b/js/src/jit/JitcodeMap.h
new file mode 100644
index 0000000000..f25bf22299
--- /dev/null
+++ b/js/src/jit/JitcodeMap.h
@@ -0,0 +1,1235 @@
+/* -*- 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/. */
+
+#ifndef jit_JitcodeMap_h
+#define jit_JitcodeMap_h
+
+#include "mozilla/Assertions.h"  // MOZ_ASSERT, MOZ_ASSERT_IF, MOZ_CRASH
+
+#include <stddef.h>  // size_t
+#include <stdint.h>  // uint8_t, uint32_t, uint64_t
+
+#include "jit/CompactBuffer.h"  // CompactBufferReader, CompactBufferWriter
+#include "jit/shared/Assembler-shared.h"  // CodeOffset
+#include "js/AllocPolicy.h"               // SystemAllocPolicy
+#include "js/TypeDecls.h"                 // jsbytecode
+#include "js/Vector.h"                    // Vector
+#include "vm/BytecodeLocation.h"          // BytecodeLocation
+
+class JSScript;
+class JSTracer;
+struct JSRuntime;
+class JSScript;
+
+namespace JS {
+class Zone;
+}  // namespace JS
+
+namespace js {
+
+class GCMarker;
+
+namespace jit {
+
+class InlineScriptTree;
+
+/*
+ * The Ion jitcode map implements tables to allow mapping from addresses in ion
+ * jitcode to the list of (JSScript*, jsbytecode*) pairs that are implicitly
+ * active in the frame at that point in the native code.
+ *
+ * To represent this information efficiently, a multi-level table is used.
+ *
+ * At the top level, a global splay-tree of JitcodeGlobalEntry describings the
+ * mapping for each individual IonCode script generated by compiles.  The
+ * entries are ordered by their nativeStartAddr.
+ *
+ * Every entry in the table is of fixed size, but there are different entry
+ * types, distinguished by the kind field.
+ */
+
+class JitcodeGlobalTable;
+class JitcodeIonTable;
+class JitcodeRegionEntry;
+
+class JitcodeGlobalEntry;
+
+struct NativeToBytecode {
+  CodeOffset nativeOffset;
+  InlineScriptTree* tree;
+  jsbytecode* pc;
+};
+
+class JitcodeSkiplistTower {
+ public:
+  static const unsigned MAX_HEIGHT = 32;
+
+ private:
+  uint8_t height_;
+  bool isFree_;
+  JitcodeGlobalEntry* ptrs_[1];
+
+ public:
+  explicit JitcodeSkiplistTower(unsigned height)
+      : height_(height), isFree_(false) {
+    MOZ_ASSERT(height >= 1 && height <= MAX_HEIGHT);
+    clearPtrs();
+  }
+
+  unsigned height() const { return height_; }
+
+  JitcodeGlobalEntry** ptrs(unsigned level) { return ptrs_; }
+
+  JitcodeGlobalEntry* next(unsigned level) const {
+    MOZ_ASSERT(!isFree_);
+    MOZ_ASSERT(level < height());
+    return ptrs_[level];
+  }
+  void setNext(unsigned level, JitcodeGlobalEntry* entry) {
+    MOZ_ASSERT(!isFree_);
+    MOZ_ASSERT(level < height());
+    ptrs_[level] = entry;
+  }
+
+  //
+  // When stored in a free-list, towers use 'ptrs_[0]' to store a
+  // pointer to the next tower.  In this context only, 'ptrs_[0]'
+  // may refer to a |JitcodeSkiplistTower*| instead of a
+  // |JitcodeGlobalEntry*|.
+  //
+
+  void addToFreeList(JitcodeSkiplistTower** freeList) {
+    JitcodeSkiplistTower* nextFreeTower = *freeList;
+    MOZ_ASSERT_IF(nextFreeTower,
+                  nextFreeTower->isFree_ && nextFreeTower->height() == height_);
+    ptrs_[0] = (JitcodeGlobalEntry*)nextFreeTower;
+    isFree_ = true;
+    *freeList = this;
+  }
+
+  static JitcodeSkiplistTower* PopFromFreeList(
+      JitcodeSkiplistTower** freeList) {
+    if (!*freeList) {
+      return nullptr;
+    }
+
+    JitcodeSkiplistTower* tower = *freeList;
+    MOZ_ASSERT(tower->isFree_);
+    JitcodeSkiplistTower* nextFreeTower =
+        (JitcodeSkiplistTower*)tower->ptrs_[0];
+    tower->clearPtrs();
+    tower->isFree_ = false;
+    *freeList = nextFreeTower;
+    return tower;
+  }
+
+  static size_t CalculateSize(unsigned height) {
+    MOZ_ASSERT(height >= 1);
+    return sizeof(JitcodeSkiplistTower) +
+           (sizeof(JitcodeGlobalEntry*) * (height - 1));
+  }
+
+ private:
+  void clearPtrs() {
+    for (unsigned i = 0; i < height_; i++) {
+      ptrs_[0] = nullptr;
+    }
+  }
+};
+
+class JitcodeGlobalEntry {
+  friend class JitcodeGlobalTable;
+
+ public:
+  enum Kind {
+    INVALID = 0,
+    Ion,
+    Baseline,
+    BaselineInterpreter,
+    Dummy,
+    Query,
+    LIMIT
+  };
+  static_assert(LIMIT <= 8);
+
+  typedef Vector<BytecodeLocation, 0, SystemAllocPolicy> BytecodeLocationVector;
+
+  struct BaseEntry {
+    static const uint64_t kNoSampleInBuffer = UINT64_MAX;
+
+    JitCode* jitcode_;
+    void* nativeStartAddr_;
+    void* nativeEndAddr_;
+    // If this entry is referenced from the profiler buffer, this is the
+    // position where the most recent sample that references it starts.
+    // Otherwise set to kNoSampleInBuffer.
+    uint64_t samplePositionInBuffer_;
+    Kind kind_ : 7;
+
+    void init() {
+      jitcode_ = nullptr;
+      nativeStartAddr_ = nullptr;
+      nativeEndAddr_ = nullptr;
+      samplePositionInBuffer_ = kNoSampleInBuffer;
+      kind_ = INVALID;
+    }
+
+    void init(Kind kind, JitCode* code, void* nativeStartAddr,
+              void* nativeEndAddr) {
+      MOZ_ASSERT_IF(kind != Query, code);
+      MOZ_ASSERT(nativeStartAddr);
+      MOZ_ASSERT(nativeEndAddr);
+      MOZ_ASSERT(kind > INVALID && kind < LIMIT);
+      jitcode_ = code;
+      nativeStartAddr_ = nativeStartAddr;
+      nativeEndAddr_ = nativeEndAddr;
+      samplePositionInBuffer_ = kNoSampleInBuffer;
+      kind_ = kind;
+    }
+
+    void setSamplePositionInBuffer(uint64_t bufferWritePos) {
+      samplePositionInBuffer_ = bufferWritePos;
+    }
+    void setAsExpired() { samplePositionInBuffer_ = kNoSampleInBuffer; }
+    bool isSampled(uint64_t bufferRangeStart) {
+      if (samplePositionInBuffer_ == kNoSampleInBuffer) {
+        return false;
+      }
+      return bufferRangeStart <= samplePositionInBuffer_;
+    }
+
+    Kind kind() const { return kind_; }
+    JitCode* jitcode() const { return jitcode_; }
+    void* nativeStartAddr() const { return nativeStartAddr_; }
+    void* nativeEndAddr() const { return nativeEndAddr_; }
+
+    bool startsBelowPointer(void* ptr) const {
+      return ((uint8_t*)nativeStartAddr()) <= ((uint8_t*)ptr);
+    }
+    bool endsAbovePointer(void* ptr) const {
+      return ((uint8_t*)nativeEndAddr()) > ((uint8_t*)ptr);
+    }
+    bool containsPointer(void* ptr) const {
+      return startsBelowPointer(ptr) && endsAbovePointer(ptr);
+    }
+
+    bool traceJitcode(JSTracer* trc);
+    bool isJitcodeMarkedFromAnyThread(JSRuntime* rt);
+  };
+
+  struct IonEntry : public BaseEntry {
+    // regionTable_ points to the start of the region table within the
+    // packed map for compile represented by this entry.  Since the
+    // region table occurs at the tail of the memory region, this pointer
+    // points somewhere inside the region memory space, and not to the start
+    // of the memory space.
+    JitcodeIonTable* regionTable_;
+
+    struct ScriptNamePair {
+      JSScript* script;
+      char* str;
+    };
+
+    struct SizedScriptList {
+      uint32_t size;
+      ScriptNamePair pairs[1];
+      SizedScriptList(uint32_t sz, JSScript** scrs, char** strs) : size(sz) {
+        for (uint32_t i = 0; i < size; i++) {
+          pairs[i].script = scrs[i];
+          pairs[i].str = strs[i];
+        }
+      }
+
+      static uint32_t AllocSizeFor(uint32_t nscripts) {
+        return sizeof(SizedScriptList) +
+               ((nscripts - 1) * sizeof(ScriptNamePair));
+      }
+    };
+
+    SizedScriptList* scriptList_;
+
+    void init(JitCode* code, void* nativeStartAddr, void* nativeEndAddr,
+              SizedScriptList* scriptList, JitcodeIonTable* regionTable) {
+      MOZ_ASSERT(scriptList);
+      MOZ_ASSERT(regionTable);
+      BaseEntry::init(Ion, code, nativeStartAddr, nativeEndAddr);
+      regionTable_ = regionTable;
+      scriptList_ = scriptList;
+    }
+
+    SizedScriptList* sizedScriptList() const { return scriptList_; }
+
+    unsigned numScripts() const { return scriptList_->size; }
+
+    JSScript* getScript(unsigned idx) const {
+      MOZ_ASSERT(idx < numScripts());
+      return sizedScriptList()->pairs[idx].script;
+    }
+
+    const char* getStr(unsigned idx) const {
+      MOZ_ASSERT(idx < numScripts());
+      return sizedScriptList()->pairs[idx].str;
+    }
+
+    void destroy();
+
+    JitcodeIonTable* regionTable() const { return regionTable_; }
+
+    int scriptIndex(JSScript* script) const {
+      unsigned count = numScripts();
+      for (unsigned i = 0; i < count; i++) {
+        if (getScript(i) == script) {
+          return i;
+        }
+      }
+      return -1;
+    }
+
+    void* canonicalNativeAddrFor(void* ptr) const;
+
+    [[nodiscard]] bool callStackAtAddr(void* ptr,
+                                       BytecodeLocationVector& results,
+                                       uint32_t* depth) const;
+
+    uint32_t callStackAtAddr(void* ptr, const char** results,
+                             uint32_t maxResults) const;
+
+    uint64_t lookupRealmID(void* ptr) const;
+
+    bool trace(JSTracer* trc);
+    void sweepChildren();
+    bool isMarkedFromAnyThread(JSRuntime* rt);
+  };
+
+  struct BaselineEntry : public BaseEntry {
+    JSScript* script_;
+    const char* str_;
+
+    // Last location that caused Ion to abort compilation and the reason
+    // therein, if any. Only actionable aborts are tracked. Internal
+    // errors like OOMs are not.
+    jsbytecode* ionAbortPc_;
+    const char* ionAbortMessage_;
+
+    void init(JitCode* code, void* nativeStartAddr, void* nativeEndAddr,
+              JSScript* script, const char* str) {
+      MOZ_ASSERT(script != nullptr);
+      BaseEntry::init(Baseline, code, nativeStartAddr, nativeEndAddr);
+      script_ = script;
+      str_ = str;
+    }
+
+    JSScript* script() const { return script_; }
+
+    const char* str() const { return str_; }
+
+    void trackIonAbort(jsbytecode* pc, const char* message);
+
+    bool hadIonAbort() const {
+      MOZ_ASSERT(!ionAbortPc_ || ionAbortMessage_);
+      return ionAbortPc_ != nullptr;
+    }
+
+    void destroy();
+
+    void* canonicalNativeAddrFor(void* ptr) const;
+
+    [[nodiscard]] bool callStackAtAddr(void* ptr,
+                                       BytecodeLocationVector& results,
+                                       uint32_t* depth) const;
+
+    uint32_t callStackAtAddr(void* ptr, const char** results,
+                             uint32_t maxResults) const;
+
+    uint64_t lookupRealmID() const;
+
+    bool trace(JSTracer* trc);
+    void sweepChildren();
+    bool isMarkedFromAnyThread(JSRuntime* rt);
+  };
+
+  struct BaselineInterpreterEntry : public BaseEntry {
+    void init(JitCode* code, void* nativeStartAddr, void* nativeEndAddr) {
+      BaseEntry::init(BaselineInterpreter, code, nativeStartAddr,
+                      nativeEndAddr);
+    }
+
+    void destroy() {}
+
+    void* canonicalNativeAddrFor(void* ptr) const;
+
+    [[nodiscard]] bool callStackAtAddr(void* ptr,
+                                       BytecodeLocationVector& results,
+                                       uint32_t* depth) const;
+
+    uint32_t callStackAtAddr(void* ptr, const char** results,
+                             uint32_t maxResults) const;
+
+    uint64_t lookupRealmID() const;
+  };
+
+  // Dummy entries are created for jitcode generated when profiling is not
+  // turned on, so that they have representation in the global table if they are
+  // on the stack when profiling is enabled.
+  struct DummyEntry : public BaseEntry {
+    void init(JitCode* code, void* nativeStartAddr, void* nativeEndAddr) {
+      BaseEntry::init(Dummy, code, nativeStartAddr, nativeEndAddr);
+    }
+
+    void destroy() {}
+
+    void* canonicalNativeAddrFor(JSRuntime* rt, void* ptr) const {
+      return nullptr;
+    }
+
+    [[nodiscard]] bool callStackAtAddr(JSRuntime* rt, void* ptr,
+                                       BytecodeLocationVector& results,
+                                       uint32_t* depth) const {
+      return true;
+    }
+
+    uint32_t callStackAtAddr(JSRuntime* rt, void* ptr, const char** results,
+                             uint32_t maxResults) const {
+      return 0;
+    }
+
+    uint64_t lookupRealmID() const { return 0; }
+  };
+
+  // QueryEntry is never stored in the table, just used for queries
+  // where an instance of JitcodeGlobalEntry is required to do tree
+  // lookups.
+  struct QueryEntry : public BaseEntry {
+    void init(void* addr) { BaseEntry::init(Query, nullptr, addr, addr); }
+    uint8_t* addr() const {
+      return reinterpret_cast<uint8_t*>(nativeStartAddr());
+    }
+    void destroy() {}
+  };
+
+ private:
+  JitcodeSkiplistTower* tower_;
+
+  union {
+    // Shadowing BaseEntry instance to allow access to base fields
+    // and type extraction.
+    BaseEntry base_;
+
+    // The most common entry type: describing jitcode generated by
+    // Ion main-line code.
+    IonEntry ion_;
+
+    // Baseline jitcode.
+    BaselineEntry baseline_;
+
+    // BaselineInterpreter code.
+    BaselineInterpreterEntry baselineInterpreter_;
+
+    // Dummy entries.
+    DummyEntry dummy_;
+
+    // When doing queries on the SplayTree for particular addresses,
+    // the query addresses are representd using a QueryEntry.
+    QueryEntry query_;
+  };
+
+ public:
+  JitcodeGlobalEntry() : tower_(nullptr) { base_.init(); }
+
+  explicit JitcodeGlobalEntry(const IonEntry& ion) : JitcodeGlobalEntry() {
+    ion_ = ion;
+  }
+
+  explicit JitcodeGlobalEntry(const BaselineEntry& baseline)
+      : JitcodeGlobalEntry() {
+    baseline_ = baseline;
+  }
+
+  explicit JitcodeGlobalEntry(const BaselineInterpreterEntry& baselineInterp)
+      : JitcodeGlobalEntry() {
+    baselineInterpreter_ = baselineInterp;
+  }
+
+  explicit JitcodeGlobalEntry(const DummyEntry& dummy) : JitcodeGlobalEntry() {
+    dummy_ = dummy;
+  }
+
+  explicit JitcodeGlobalEntry(const QueryEntry& query) : JitcodeGlobalEntry() {
+    query_ = query;
+  }
+
+  static JitcodeGlobalEntry MakeQuery(void* ptr) {
+    QueryEntry query;
+    query.init(ptr);
+    return JitcodeGlobalEntry(query);
+  }
+
+  void destroy() {
+    switch (kind()) {
+      case Ion:
+        ionEntry().destroy();
+        break;
+      case Baseline:
+        baselineEntry().destroy();
+        break;
+      case BaselineInterpreter:
+        baselineInterpreterEntry().destroy();
+        break;
+      case Dummy:
+        dummyEntry().destroy();
+        break;
+      case Query:
+        queryEntry().destroy();
+        break;
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+  }
+
+  JitCode* jitcode() const { return baseEntry().jitcode(); }
+  void* nativeStartAddr() const { return base_.nativeStartAddr(); }
+  void* nativeEndAddr() const { return base_.nativeEndAddr(); }
+
+  void setSamplePositionInBuffer(uint64_t samplePositionInBuffer) {
+    baseEntry().setSamplePositionInBuffer(samplePositionInBuffer);
+  }
+  void setAsExpired() { baseEntry().setAsExpired(); }
+  bool isSampled(uint64_t bufferRangeStart) {
+    return baseEntry().isSampled(bufferRangeStart);
+  }
+
+  bool startsBelowPointer(void* ptr) const {
+    return base_.startsBelowPointer(ptr);
+  }
+  bool endsAbovePointer(void* ptr) const { return base_.endsAbovePointer(ptr); }
+  bool containsPointer(void* ptr) const { return base_.containsPointer(ptr); }
+
+  bool overlapsWith(const JitcodeGlobalEntry& entry) const {
+    // Catch full containment of |entry| within |this|, and partial overlaps.
+    if (containsPointer(entry.nativeStartAddr()) ||
+        containsPointer(entry.nativeEndAddr())) {
+      return true;
+    }
+
+    // Catch full containment of |this| within |entry|.
+    if (startsBelowPointer(entry.nativeEndAddr()) &&
+        endsAbovePointer(entry.nativeStartAddr())) {
+      return true;
+    }
+
+    return false;
+  }
+
+  Kind kind() const { return base_.kind(); }
+
+  bool isValid() const { return (kind() > INVALID) && (kind() < LIMIT); }
+  bool isIon() const { return kind() == Ion; }
+  bool isBaseline() const { return kind() == Baseline; }
+  bool isBaselineInterpreter() const { return kind() == BaselineInterpreter; }
+  bool isDummy() const { return kind() == Dummy; }
+  bool isQuery() const { return kind() == Query; }
+
+  BaseEntry& baseEntry() {
+    MOZ_ASSERT(isValid());
+    return base_;
+  }
+  IonEntry& ionEntry() {
+    MOZ_ASSERT(isIon());
+    return ion_;
+  }
+  BaselineEntry& baselineEntry() {
+    MOZ_ASSERT(isBaseline());
+    return baseline_;
+  }
+  BaselineInterpreterEntry& baselineInterpreterEntry() {
+    MOZ_ASSERT(isBaselineInterpreter());
+    return baselineInterpreter_;
+  }
+  DummyEntry& dummyEntry() {
+    MOZ_ASSERT(isDummy());
+    return dummy_;
+  }
+  QueryEntry& queryEntry() {
+    MOZ_ASSERT(isQuery());
+    return query_;
+  }
+
+  const BaseEntry& baseEntry() const {
+    MOZ_ASSERT(isValid());
+    return base_;
+  }
+  const IonEntry& ionEntry() const {
+    MOZ_ASSERT(isIon());
+    return ion_;
+  }
+  const BaselineEntry& baselineEntry() const {
+    MOZ_ASSERT(isBaseline());
+    return baseline_;
+  }
+  const BaselineInterpreterEntry& baselineInterpreterEntry() const {
+    MOZ_ASSERT(isBaselineInterpreter());
+    return baselineInterpreter_;
+  }
+  const DummyEntry& dummyEntry() const {
+    MOZ_ASSERT(isDummy());
+    return dummy_;
+  }
+  const QueryEntry& queryEntry() const {
+    MOZ_ASSERT(isQuery());
+    return query_;
+  }
+
+  void* canonicalNativeAddrFor(JSRuntime* rt, void* ptr) const {
+    switch (kind()) {
+      case Ion:
+        return ionEntry().canonicalNativeAddrFor(ptr);
+      case Baseline:
+        return baselineEntry().canonicalNativeAddrFor(ptr);
+      case Dummy:
+        return dummyEntry().canonicalNativeAddrFor(rt, ptr);
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+    return nullptr;
+  }
+
+  // Read the inline call stack at a given point in the native code and append
+  // into the given vector.  Innermost (script,pc) pair will be appended first,
+  // and outermost appended last.
+  //
+  // Returns false on memory failure.
+  [[nodiscard]] bool callStackAtAddr(JSRuntime* rt, void* ptr,
+                                     BytecodeLocationVector& results,
+                                     uint32_t* depth) const {
+    switch (kind()) {
+      case Ion:
+        return ionEntry().callStackAtAddr(ptr, results, depth);
+      case Baseline:
+        return baselineEntry().callStackAtAddr(ptr, results, depth);
+      case BaselineInterpreter:
+        return baselineInterpreterEntry().callStackAtAddr(ptr, results, depth);
+      case Dummy:
+        return dummyEntry().callStackAtAddr(rt, ptr, results, depth);
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+    return false;
+  }
+
+  uint32_t callStackAtAddr(JSRuntime* rt, void* ptr, const char** results,
+                           uint32_t maxResults) const {
+    switch (kind()) {
+      case Ion:
+        return ionEntry().callStackAtAddr(ptr, results, maxResults);
+      case Baseline:
+        return baselineEntry().callStackAtAddr(ptr, results, maxResults);
+      case BaselineInterpreter:
+        return baselineInterpreterEntry().callStackAtAddr(ptr, results,
+                                                          maxResults);
+      case Dummy:
+        return dummyEntry().callStackAtAddr(rt, ptr, results, maxResults);
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+    return false;
+  }
+
+  uint64_t lookupRealmID(JSRuntime* rt, void* ptr) const {
+    switch (kind()) {
+      case Ion:
+        return ionEntry().lookupRealmID(ptr);
+      case Baseline:
+        return baselineEntry().lookupRealmID();
+      case Dummy:
+        return dummyEntry().lookupRealmID();
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+  }
+
+  // Figure out the number of the (JSScript*, jsbytecode*) pairs that are active
+  // at this location.
+  uint32_t lookupInlineCallDepth(void* ptr);
+
+  // Compare two global entries.
+  static int compare(const JitcodeGlobalEntry& ent1,
+                     const JitcodeGlobalEntry& ent2);
+  int compareTo(const JitcodeGlobalEntry& other) {
+    return compare(*this, other);
+  }
+
+  Zone* zone() { return baseEntry().jitcode()->zone(); }
+
+  bool trace(JSTracer* trc) {
+    bool tracedAny = baseEntry().traceJitcode(trc);
+    switch (kind()) {
+      case Ion:
+        tracedAny |= ionEntry().trace(trc);
+        break;
+      case Baseline:
+        tracedAny |= baselineEntry().trace(trc);
+        break;
+      case BaselineInterpreter:
+      case Dummy:
+        break;
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+    return tracedAny;
+  }
+
+  void sweepChildren(JSRuntime* rt) {
+    switch (kind()) {
+      case Ion:
+        ionEntry().sweepChildren();
+        break;
+      case Baseline:
+        baselineEntry().sweepChildren();
+        break;
+      case BaselineInterpreter:
+      case Dummy:
+        break;
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+  }
+
+  bool isMarkedFromAnyThread(JSRuntime* rt) {
+    if (!baseEntry().isJitcodeMarkedFromAnyThread(rt)) {
+      return false;
+    }
+    switch (kind()) {
+      case Ion:
+        return ionEntry().isMarkedFromAnyThread(rt);
+      case Baseline:
+        return baselineEntry().isMarkedFromAnyThread(rt);
+      case Dummy:
+        break;
+      default:
+        MOZ_CRASH("Invalid JitcodeGlobalEntry kind.");
+    }
+    return true;
+  }
+
+  //
+  // When stored in a free-list, entries use 'tower_' to store a
+  // pointer to the next entry.  In this context only, 'tower_'
+  // may refer to a |JitcodeGlobalEntry*| instead of a
+  // |JitcodeSkiplistTower*|.
+  //
+
+  void addToFreeList(JitcodeGlobalEntry** freeList) {
+    MOZ_ASSERT(!isValid());
+
+    JitcodeGlobalEntry* nextFreeEntry = *freeList;
+    MOZ_ASSERT_IF(nextFreeEntry, !nextFreeEntry->isValid());
+
+    tower_ = (JitcodeSkiplistTower*)nextFreeEntry;
+    *freeList = this;
+  }
+
+  static JitcodeGlobalEntry* PopFromFreeList(JitcodeGlobalEntry** freeList) {
+    if (!*freeList) {
+      return nullptr;
+    }
+
+    JitcodeGlobalEntry* entry = *freeList;
+    MOZ_ASSERT(!entry->isValid());
+    JitcodeGlobalEntry* nextFreeEntry = (JitcodeGlobalEntry*)entry->tower_;
+    entry->tower_ = nullptr;
+    *freeList = nextFreeEntry;
+    return entry;
+  }
+};
+
+/*
+ * Global table of JitcodeGlobalEntry values sorted by native address range.
+ */
+class JitcodeGlobalTable {
+ private:
+  static const size_t LIFO_CHUNK_SIZE = 16 * 1024;
+
+  LifoAlloc alloc_;
+  JitcodeGlobalEntry* freeEntries_;
+  uint32_t rand_;
+  uint32_t skiplistSize_;
+
+  JitcodeGlobalEntry* startTower_[JitcodeSkiplistTower::MAX_HEIGHT];
+  JitcodeSkiplistTower* freeTowers_[JitcodeSkiplistTower::MAX_HEIGHT];
+
+ public:
+  JitcodeGlobalTable()
+      : alloc_(LIFO_CHUNK_SIZE),
+        freeEntries_(nullptr),
+        rand_(0),
+        skiplistSize_(0) {
+    for (unsigned i = 0; i < JitcodeSkiplistTower::MAX_HEIGHT; i++) {
+      startTower_[i] = nullptr;
+    }
+    for (unsigned i = 0; i < JitcodeSkiplistTower::MAX_HEIGHT; i++) {
+      freeTowers_[i] = nullptr;
+    }
+  }
+  ~JitcodeGlobalTable() = default;
+
+  bool empty() const { return skiplistSize_ == 0; }
+
+  JitcodeGlobalEntry* lookup(void* ptr) { return lookupInternal(ptr); }
+
+  const JitcodeGlobalEntry* lookupForSampler(void* ptr, JSRuntime* rt,
+                                             uint64_t samplePosInBuffer);
+
+  [[nodiscard]] bool addEntry(const JitcodeGlobalEntry::IonEntry& entry) {
+    return addEntry(JitcodeGlobalEntry(entry));
+  }
+  [[nodiscard]] bool addEntry(const JitcodeGlobalEntry::BaselineEntry& entry) {
+    return addEntry(JitcodeGlobalEntry(entry));
+  }
+  [[nodiscard]] bool addEntry(
+      const JitcodeGlobalEntry::BaselineInterpreterEntry& entry) {
+    return addEntry(JitcodeGlobalEntry(entry));
+  }
+  [[nodiscard]] bool addEntry(const JitcodeGlobalEntry::DummyEntry& entry) {
+    return addEntry(JitcodeGlobalEntry(entry));
+  }
+
+  void removeEntry(JitcodeGlobalEntry& entry, JitcodeGlobalEntry** prevTower);
+  void releaseEntry(JitcodeGlobalEntry& entry, JitcodeGlobalEntry** prevTower,
+                    JSRuntime* rt);
+
+  void setAllEntriesAsExpired();
+  [[nodiscard]] bool markIteratively(GCMarker* marker);
+  void traceWeak(JSRuntime* rt, JSTracer* trc);
+
+ private:
+  [[nodiscard]] bool addEntry(const JitcodeGlobalEntry& entry);
+
+  JitcodeGlobalEntry* lookupInternal(void* ptr);
+
+  // Initialize towerOut such that towerOut[i] (for i in [0, MAX_HEIGHT-1])
+  // is a JitcodeGlobalEntry that is sorted to be <query, whose successor at
+  // level i is either null, or sorted to be >= query.
+  //
+  // If entry with the given properties does not exist for level i, then
+  // towerOut[i] is initialized to nullptr.
+  void searchInternal(const JitcodeGlobalEntry& query,
+                      JitcodeGlobalEntry** towerOut);
+
+  JitcodeGlobalEntry* searchAtHeight(unsigned level, JitcodeGlobalEntry* start,
+                                     const JitcodeGlobalEntry& query);
+
+  // Calculate next random tower height.
+  unsigned generateTowerHeight();
+
+  JitcodeSkiplistTower* allocateTower(unsigned height);
+  JitcodeGlobalEntry* allocateEntry();
+
+#ifdef DEBUG
+  void verifySkiplist();
+#else
+  void verifySkiplist() {}
+#endif
+
+ public:
+  class Range {
+   protected:
+    JitcodeGlobalTable& table_;
+    JitcodeGlobalEntry* cur_;
+
+   public:
+    explicit Range(JitcodeGlobalTable& table)
+        : table_(table), cur_(table.startTower_[0]) {}
+
+    JitcodeGlobalEntry* front() const {
+      MOZ_ASSERT(!empty());
+      return cur_;
+    }
+
+    bool empty() const { return !cur_; }
+
+    void popFront() {
+      MOZ_ASSERT(!empty());
+      cur_ = cur_->tower_->next(0);
+    }
+  };
+
+  // An enumerator class that can remove entries as it enumerates. If this
+  // functionality is not needed, use Range instead.
+  class Enum : public Range {
+    JSRuntime* rt_;
+    JitcodeGlobalEntry* next_;
+    JitcodeGlobalEntry* prevTower_[JitcodeSkiplistTower::MAX_HEIGHT];
+
+   public:
+    Enum(JitcodeGlobalTable& table, JSRuntime* rt);
+
+    void popFront();
+    void removeFront();
+  };
+};
+
+// clang-format off
+/*
+ * Container class for main jitcode table.
+ * The Region table's memory is structured as follows:
+ *
+ *      +------------------------------------------------+   |
+ *      |  Region 1 Run                                  |   |
+ *      |------------------------------------------------|   |
+ *      |  Region 2 Run                                  |   |
+ *      |                                                |   |
+ *      |                                                |   |
+ *      |------------------------------------------------|   |
+ *      |  Region 3 Run                                  |   |
+ *      |                                                |   |
+ *      |------------------------------------------------|   |-- Payload
+ *      |                                                |   |
+ *      |               ...                              |   |
+ *      |                                                |   |
+ *      |------------------------------------------------|   |
+ *      |  Region M Run                                  |   |
+ *      |                                                |   |
+ *      +================================================+ <- RegionTable pointer points here
+ *      | uint23_t numRegions = M                        |   |
+ *      +------------------------------------------------+   |
+ *      | Region 1                                       |   |
+ *      |   uint32_t entryOffset = size(Payload)         |   |
+ *      +------------------------------------------------+   |
+ *      |                                                |   |-- Table
+ *      |   ...                                          |   |
+ *      |                                                |   |
+ *      +------------------------------------------------+   |
+ *      | Region M                                       |   |
+ *      |   uint32_t entryOffset                         |   |
+ *      +------------------------------------------------+   |
+ *
+ * The region table is composed of two sections: a tail section that contains a table of
+ * fixed-size entries containing offsets into the the head section, and a head section that
+ * holds a sequence of variable-sized runs.  The table in the tail section serves to
+ * locate the variable-length encoded structures in the head section.
+ *
+ * The entryOffsets in the table indicate the bytes offset to subtract from the regionTable
+ * pointer to arrive at the encoded region in the payload.
+ *
+ *
+ * Variable-length entries in payload
+ * ----------------------------------
+ * The entryOffsets in the region table's fixed-sized entries refer to a location within the
+ * variable-length payload section.  This location contains a compactly encoded "run" of
+ * mappings.
+ *
+ * Each run starts by describing the offset within the native code it starts at, and the
+ * sequence of (JSScript*, jsbytecode*) pairs active at that site.  Following that, there
+ * are a number of variable-length entries encoding (nativeOffsetDelta, bytecodeOffsetDelta)
+ * pairs for the run.
+ *
+ *      VarUint32 nativeOffset;
+ *          - The offset from nativeStartAddr in the global table entry at which
+ *            the jitcode for this region starts.
+ *
+ *      Uint8_t scriptDepth;
+ *          - The depth of inlined scripts for this region.
+ *
+ *      List<VarUint32> inlineScriptPcStack;
+ *          - We encode (2 * scriptDepth) VarUint32s here.  Each pair of uint32s are taken
+ *            as an index into the scriptList in the global table entry, and a pcOffset
+ *            respectively.
+ *
+ *      List<NativeAndBytecodeDelta> deltaRun;
+ *          - The rest of the entry is a deltaRun that stores a series of variable-length
+ *            encoded NativeAndBytecodeDelta datums.
+ */
+// clang-format on
+class JitcodeRegionEntry {
+ private:
+  static const unsigned MAX_RUN_LENGTH = 100;
+
+ public:
+  static void WriteHead(CompactBufferWriter& writer, uint32_t nativeOffset,
+                        uint8_t scriptDepth);
+  static void ReadHead(CompactBufferReader& reader, uint32_t* nativeOffset,
+                       uint8_t* scriptDepth);
+
+  static void WriteScriptPc(CompactBufferWriter& writer, uint32_t scriptIdx,
+                            uint32_t pcOffset);
+  static void ReadScriptPc(CompactBufferReader& reader, uint32_t* scriptIdx,
+                           uint32_t* pcOffset);
+
+  static void WriteDelta(CompactBufferWriter& writer, uint32_t nativeDelta,
+                         int32_t pcDelta);
+  static void ReadDelta(CompactBufferReader& reader, uint32_t* nativeDelta,
+                        int32_t* pcDelta);
+
+  // Given a pointer into an array of NativeToBytecode (and a pointer to the end
+  // of the array), compute the number of entries that would be consume by
+  // outputting a run starting at this one.
+  static uint32_t ExpectedRunLength(const NativeToBytecode* entry,
+                                    const NativeToBytecode* end);
+
+  // Write a run, starting at the given NativeToBytecode entry, into the given
+  // buffer writer.
+  [[nodiscard]] static bool WriteRun(CompactBufferWriter& writer,
+                                     JSScript** scriptList,
+                                     uint32_t scriptListSize,
+                                     uint32_t runLength,
+                                     const NativeToBytecode* entry);
+
+  // Delta Run entry formats are encoded little-endian:
+  //
+  //  byte 0
+  //  NNNN-BBB0
+  //      Single byte format.  nativeDelta in [0, 15], pcDelta in [0, 7]
+  //
+  static const uint32_t ENC1_MASK = 0x1;
+  static const uint32_t ENC1_MASK_VAL = 0x0;
+
+  static const uint32_t ENC1_NATIVE_DELTA_MAX = 0xf;
+  static const unsigned ENC1_NATIVE_DELTA_SHIFT = 4;
+
+  static const uint32_t ENC1_PC_DELTA_MASK = 0x0e;
+  static const int32_t ENC1_PC_DELTA_MAX = 0x7;
+  static const unsigned ENC1_PC_DELTA_SHIFT = 1;
+
+  //  byte 1    byte 0
+  //  NNNN-NNNN BBBB-BB01
+  //      Two-byte format.  nativeDelta in [0, 255], pcDelta in [0, 63]
+  //
+  static const uint32_t ENC2_MASK = 0x3;
+  static const uint32_t ENC2_MASK_VAL = 0x1;
+
+  static const uint32_t ENC2_NATIVE_DELTA_MAX = 0xff;
+  static const unsigned ENC2_NATIVE_DELTA_SHIFT = 8;
+
+  static const uint32_t ENC2_PC_DELTA_MASK = 0x00fc;
+  static const int32_t ENC2_PC_DELTA_MAX = 0x3f;
+  static const unsigned ENC2_PC_DELTA_SHIFT = 2;
+
+  //  byte 2    byte 1    byte 0
+  //  NNNN-NNNN NNNB-BBBB BBBB-B011
+  //      Three-byte format.  nativeDelta in [0, 2047], pcDelta in [-512, 511]
+  //
+  static const uint32_t ENC3_MASK = 0x7;
+  static const uint32_t ENC3_MASK_VAL = 0x3;
+
+  static const uint32_t ENC3_NATIVE_DELTA_MAX = 0x7ff;
+  static const unsigned ENC3_NATIVE_DELTA_SHIFT = 13;
+
+  static const uint32_t ENC3_PC_DELTA_MASK = 0x001ff8;
+  static const int32_t ENC3_PC_DELTA_MAX = 0x1ff;
+  static const int32_t ENC3_PC_DELTA_MIN = -ENC3_PC_DELTA_MAX - 1;
+  static const unsigned ENC3_PC_DELTA_SHIFT = 3;
+
+  //  byte 3    byte 2    byte 1    byte 0
+  //  NNNN-NNNN NNNN-NNNN BBBB-BBBB BBBB-B111
+  //      Three-byte format.  nativeDelta in [0, 65535],
+  //                          pcDelta in [-4096, 4095]
+  static const uint32_t ENC4_MASK = 0x7;
+  static const uint32_t ENC4_MASK_VAL = 0x7;
+
+  static const uint32_t ENC4_NATIVE_DELTA_MAX = 0xffff;
+  static const unsigned ENC4_NATIVE_DELTA_SHIFT = 16;
+
+  static const uint32_t ENC4_PC_DELTA_MASK = 0x0000fff8;
+  static const int32_t ENC4_PC_DELTA_MAX = 0xfff;
+  static const int32_t ENC4_PC_DELTA_MIN = -ENC4_PC_DELTA_MAX - 1;
+  static const unsigned ENC4_PC_DELTA_SHIFT = 3;
+
+  static bool IsDeltaEncodeable(uint32_t nativeDelta, int32_t pcDelta) {
+    return (nativeDelta <= ENC4_NATIVE_DELTA_MAX) &&
+           (pcDelta >= ENC4_PC_DELTA_MIN) && (pcDelta <= ENC4_PC_DELTA_MAX);
+  }
+
+ private:
+  const uint8_t* data_;
+  const uint8_t* end_;
+
+  // Unpacked state from jitcode entry.
+  uint32_t nativeOffset_;
+  uint8_t scriptDepth_;
+  const uint8_t* scriptPcStack_;
+  const uint8_t* deltaRun_;
+
+  void unpack();
+
+ public:
+  JitcodeRegionEntry(const uint8_t* data, const uint8_t* end)
+      : data_(data),
+        end_(end),
+        nativeOffset_(0),
+        scriptDepth_(0),
+        scriptPcStack_(nullptr),
+        deltaRun_(nullptr) {
+    MOZ_ASSERT(data_ < end_);
+    unpack();
+    MOZ_ASSERT(scriptPcStack_ < end_);
+    MOZ_ASSERT(deltaRun_ <= end_);
+  }
+
+  uint32_t nativeOffset() const { return nativeOffset_; }
+  uint32_t scriptDepth() const { return scriptDepth_; }
+
+  class ScriptPcIterator {
+   private:
+    const uint8_t* start_;
+    const uint8_t* end_;
+#ifdef DEBUG
+    uint32_t count_;
+#endif
+    uint32_t idx_;
+    const uint8_t* cur_;
+
+   public:
+    ScriptPcIterator(const uint8_t* start, const uint8_t* end, uint32_t count)
+        : start_(start),
+          end_(end),
+#ifdef DEBUG
+          count_(count),
+#endif
+          idx_(0),
+          cur_(start_) {
+    }
+
+    bool hasMore() const {
+      MOZ_ASSERT((idx_ == count_) == (cur_ == end_));
+      MOZ_ASSERT((idx_ < count_) == (cur_ < end_));
+      return cur_ < end_;
+    }
+
+    void readNext(uint32_t* scriptIdxOut, uint32_t* pcOffsetOut) {
+      MOZ_ASSERT(scriptIdxOut);
+      MOZ_ASSERT(pcOffsetOut);
+      MOZ_ASSERT(hasMore());
+
+      CompactBufferReader reader(cur_, end_);
+      ReadScriptPc(reader, scriptIdxOut, pcOffsetOut);
+
+      cur_ = reader.currentPosition();
+      MOZ_ASSERT(cur_ <= end_);
+
+      idx_++;
+      MOZ_ASSERT_IF(idx_ == count_, cur_ == end_);
+    }
+
+    void reset() {
+      idx_ = 0;
+      cur_ = start_;
+    }
+  };
+
+  ScriptPcIterator scriptPcIterator() const {
+    // End of script+pc sequence is the start of the delta run.
+    return ScriptPcIterator(scriptPcStack_, deltaRun_, scriptDepth_);
+  }
+
+  class DeltaIterator {
+   private:
+    const uint8_t* start_;
+    const uint8_t* end_;
+    const uint8_t* cur_;
+
+   public:
+    DeltaIterator(const uint8_t* start, const uint8_t* end)
+        : start_(start), end_(end), cur_(start) {}
+
+    bool hasMore() const {
+      MOZ_ASSERT(cur_ <= end_);
+      return cur_ < end_;
+    }
+
+    void readNext(uint32_t* nativeDeltaOut, int32_t* pcDeltaOut) {
+      MOZ_ASSERT(nativeDeltaOut != nullptr);
+      MOZ_ASSERT(pcDeltaOut != nullptr);
+
+      MOZ_ASSERT(hasMore());
+
+      CompactBufferReader reader(cur_, end_);
+      ReadDelta(reader, nativeDeltaOut, pcDeltaOut);
+
+      cur_ = reader.currentPosition();
+      MOZ_ASSERT(cur_ <= end_);
+    }
+
+    void reset() { cur_ = start_; }
+  };
+  DeltaIterator deltaIterator() const { return DeltaIterator(deltaRun_, end_); }
+
+  uint32_t findPcOffset(uint32_t queryNativeOffset,
+                        uint32_t startPcOffset) const;
+};
+
+class JitcodeIonTable {
+ private:
+  /* Variable length payload section "below" here. */
+  uint32_t numRegions_;
+  uint32_t regionOffsets_[1];
+
+  const uint8_t* payloadEnd() const {
+    return reinterpret_cast<const uint8_t*>(this);
+  }
+
+ public:
+  explicit JitcodeIonTable(uint32_t numRegions) : numRegions_(numRegions) {
+    for (uint32_t i = 0; i < numRegions; i++) {
+      regionOffsets_[i] = 0;
+    }
+  }
+
+  [[nodiscard]] bool makeIonEntry(JSContext* cx, JitCode* code,
+                                  uint32_t numScripts, JSScript** scripts,
+                                  JitcodeGlobalEntry::IonEntry& out);
+
+  uint32_t numRegions() const { return numRegions_; }
+
+  uint32_t regionOffset(uint32_t regionIndex) const {
+    MOZ_ASSERT(regionIndex < numRegions());
+    return regionOffsets_[regionIndex];
+  }
+
+  JitcodeRegionEntry regionEntry(uint32_t regionIndex) const {
+    const uint8_t* regionStart = payloadEnd() - regionOffset(regionIndex);
+    const uint8_t* regionEnd = payloadEnd();
+    if (regionIndex < numRegions_ - 1) {
+      regionEnd -= regionOffset(regionIndex + 1);
+    }
+    return JitcodeRegionEntry(regionStart, regionEnd);
+  }
+
+  bool regionContainsOffset(uint32_t regionIndex, uint32_t nativeOffset) {
+    MOZ_ASSERT(regionIndex < numRegions());
+
+    JitcodeRegionEntry ent = regionEntry(regionIndex);
+    if (nativeOffset < ent.nativeOffset()) {
+      return false;
+    }
+
+    if (regionIndex == numRegions_ - 1) {
+      return true;
+    }
+
+    return nativeOffset < regionEntry(regionIndex + 1).nativeOffset();
+  }
+
+  uint32_t findRegionEntry(uint32_t offset) const;
+
+  const uint8_t* payloadStart() const {
+    // The beginning of the payload the beginning of the first region are the
+    // same.
+    return payloadEnd() - regionOffset(0);
+  }
+
+  [[nodiscard]] static bool WriteIonTable(CompactBufferWriter& writer,
+                                          JSScript** scriptList,
+                                          uint32_t scriptListSize,
+                                          const NativeToBytecode* start,
+                                          const NativeToBytecode* end,
+                                          uint32_t* tableOffsetOut,
+                                          uint32_t* numRegionsOut);
+};
+
+}  // namespace jit
+}  // namespace js
+
+#endif /* jit_JitcodeMap_h */