js/src/jit/JitcodeMap.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 #ifndef jit_JitcodeMap_h
   8 #define jit_JitcodeMap_h
   9
  10 #include "mozilla/Assertions.h"  // MOZ_ASSERT, MOZ_ASSERT_IF, MOZ_CRASH
  11
  12 #include <stddef.h>  // size_t
  13 #include <stdint.h>  // uint8_t, uint32_t, uint64_t
  14
  15 #include "ds/AvlTree.h"         // AvlTree
  16 #include "jit/CompactBuffer.h"  // CompactBufferReader, CompactBufferWriter
  17 #include "jit/shared/Assembler-shared.h"  // CodeOffset
  18 #include "js/AllocPolicy.h"               // SystemAllocPolicy
  19 #include "js/TypeDecls.h"                 // jsbytecode
  20 #include "js/Vector.h"                    // Vector
  21 #include "vm/BytecodeLocation.h"          // BytecodeLocation
  22
  23 class JSScript;
  24 class JSTracer;
  25 struct JSRuntime;
  26
  27 namespace JS {
  28 class Zone;
  29 }  // namespace JS
  30
  31 namespace js {
  32
  33 class GCMarker;
  34
  35 namespace jit {
  36
  37 class InlineScriptTree;
  38
  39 /*
  40  * The jitcode map implements tables to allow mapping from addresses in jitcode
  41  * to the list of (JSScript*, jsbytecode*) pairs that are implicitly active in
  42  * the frame at that point in the native code.
  43  *
  44  * To represent this information efficiently, a multi-level table is used.
  45  *
  46  * At the top level, a global AVL-tree of JitcodeGlobalEntry describing the
  47  * mapping for each individual JitCode generated by compiles.  The entries are
  48  * ordered by their nativeStartAddr.
  49  *
  50  * Every entry in the table is of fixed size, but there are different entry
  51  * types, distinguished by the kind field.
  52  */
  53
  54 class JitcodeGlobalTable;
  55 class JitcodeIonTable;
  56 class JitcodeRegionEntry;
  57
  58 struct NativeToBytecode {
  59   CodeOffset nativeOffset;
  60   InlineScriptTree* tree;
  61   jsbytecode* pc;
  62 };
  63
  64 // Describes range [start, end) of JIT-generated code.
  65 class JitCodeRange {
  66  protected:
  67   void* const nativeStartAddr_;
  68   void* const nativeEndAddr_;
  69
  70  public:
  71   JitCodeRange(void* start, void* end)
  72       : nativeStartAddr_(start), nativeEndAddr_(end) {
  73     MOZ_ASSERT(start < end);
  74   }
  75
  76   // Comparator used by the AvlTree.
  77   static int compare(const JitCodeRange* r1, const JitCodeRange* r2) {
  78     // JitCodeRange includes 'start' but excludes 'end'.
  79     if (r1->nativeEndAddr_ <= r2->nativeStartAddr_) {
  80       return -1;
  81     }
  82     if (r1->nativeStartAddr_ >= r2->nativeEndAddr_) {
  83       return 1;
  84     }
  85     return 0;
  86   }
  87
  88   void* nativeStartAddr() const { return nativeStartAddr_; }
  89   void* nativeEndAddr() const { return nativeEndAddr_; }
  90
  91   bool containsPointer(void* ptr) const {
  92     return nativeStartAddr() <= ptr && ptr < nativeEndAddr();
  93   }
  94 };
  95
  96 typedef Vector<BytecodeLocation, 0, SystemAllocPolicy> BytecodeLocationVector;
  97
  98 class IonEntry;
  99 class IonICEntry;
 100 class BaselineEntry;
 101 class BaselineInterpreterEntry;
 102 class DummyEntry;
 103
 104 // Base class for all entries.
 105 class JitcodeGlobalEntry : public JitCodeRange {
 106  protected:
 107   JitCode* jitcode_;
 108   // If this entry is referenced from the profiler buffer, this is the
 109   // position where the most recent sample that references it starts.
 110   // Otherwise set to kNoSampleInBuffer.
 111   static const uint64_t kNoSampleInBuffer = UINT64_MAX;
 112   uint64_t samplePositionInBuffer_ = kNoSampleInBuffer;
 113
 114  public:
 115   enum class Kind : uint8_t {
 116     Ion,
 117     IonIC,
 118     Baseline,
 119     BaselineInterpreter,
 120     Dummy
 121   };
 122
 123  protected:
 124   Kind kind_;
 125
 126   JitcodeGlobalEntry(Kind kind, JitCode* code, void* nativeStartAddr,
 127                      void* nativeEndAddr)
 128       : JitCodeRange(nativeStartAddr, nativeEndAddr),
 129         jitcode_(code),
 130         kind_(kind) {
 131     MOZ_ASSERT(code);
 132     MOZ_ASSERT(nativeStartAddr);
 133     MOZ_ASSERT(nativeEndAddr);
 134   }
 135
 136   // Protected destructor to ensure this is called through DestroyPolicy.
 137   ~JitcodeGlobalEntry() = default;
 138
 139   JitcodeGlobalEntry(const JitcodeGlobalEntry& other) = delete;
 140   void operator=(const JitcodeGlobalEntry& other) = delete;
 141
 142  public:
 143   struct DestroyPolicy {
 144     void operator()(JitcodeGlobalEntry* entry);
 145   };
 146
 147   void setSamplePositionInBuffer(uint64_t bufferWritePos) {
 148     samplePositionInBuffer_ = bufferWritePos;
 149   }
 150   void setAsExpired() { samplePositionInBuffer_ = kNoSampleInBuffer; }
 151   bool isSampled(uint64_t bufferRangeStart) {
 152     if (samplePositionInBuffer_ == kNoSampleInBuffer) {
 153       return false;
 154     }
 155     return bufferRangeStart <= samplePositionInBuffer_;
 156   }
 157
 158   Kind kind() const { return kind_; }
 159   bool isIon() const { return kind() == Kind::Ion; }
 160   bool isIonIC() const { return kind() == Kind::IonIC; }
 161   bool isBaseline() const { return kind() == Kind::Baseline; }
 162   bool isBaselineInterpreter() const {
 163     return kind() == Kind::BaselineInterpreter;
 164   }
 165   bool isDummy() const { return kind() == Kind::Dummy; }
 166
 167   inline const IonEntry& asIon() const;
 168   inline const IonICEntry& asIonIC() const;
 169   inline const BaselineEntry& asBaseline() const;
 170   inline const BaselineInterpreterEntry& asBaselineInterpreter() const;
 171   inline const DummyEntry& asDummy() const;
 172
 173   inline IonEntry& asIon();
 174   inline IonICEntry& asIonIC();
 175   inline BaselineEntry& asBaseline();
 176   inline BaselineInterpreterEntry& asBaselineInterpreter();
 177   inline DummyEntry& asDummy();
 178
 179   JitCode* jitcode() const { return jitcode_; }
 180   JitCode** jitcodePtr() { return &jitcode_; }
 181   Zone* zone() const { return jitcode()->zone(); }
 182
 183   bool traceJitcode(JSTracer* trc);
 184   bool isJitcodeMarkedFromAnyThread(JSRuntime* rt);
 185
 186   bool trace(JSTracer* trc);
 187   void traceWeak(JSTracer* trc);
 188   uint64_t lookupRealmID(JSRuntime* rt, void* ptr) const;
 189   void* canonicalNativeAddrFor(JSRuntime* rt, void* ptr) const;
 190
 191   // Read the inline call stack at a given point in the native code and append
 192   // into the given vector.  Innermost (script,pc) pair will be appended first,
 193   // and outermost appended last.
 194   //
 195   // Returns false on memory failure.
 196   [[nodiscard]] bool callStackAtAddr(JSRuntime* rt, void* ptr,
 197                                      BytecodeLocationVector& results,
 198                                      uint32_t* depth) const;
 199   uint32_t callStackAtAddr(JSRuntime* rt, void* ptr, const char** results,
 200                            uint32_t maxResults) const;
 201 };
 202
 203 using UniqueJitcodeGlobalEntry =
 204     UniquePtr<JitcodeGlobalEntry, JitcodeGlobalEntry::DestroyPolicy>;
 205
 206 template <typename T, typename... Args>
 207 inline UniqueJitcodeGlobalEntry MakeJitcodeGlobalEntry(JSContext* cx,
 208                                                        Args&&... args) {
 209   UniqueJitcodeGlobalEntry res(js_new<T>(std::forward<Args>(args)...));
 210   if (!res) {
 211     ReportOutOfMemory(cx);
 212   }
 213   return res;
 214 }
 215
 216 class IonEntry : public JitcodeGlobalEntry {
 217  public:
 218   struct ScriptNamePair {
 219     JSScript* script;
 220     UniqueChars str;
 221     ScriptNamePair(JSScript* script, UniqueChars str)
 222         : script(script), str(std::move(str)) {}
 223   };
 224   using ScriptList = Vector<ScriptNamePair, 2, SystemAllocPolicy>;
 225
 226  private:
 227   ScriptList scriptList_;
 228
 229   // regionTable_ points to the start of the region table within the
 230   // packed map for compile represented by this entry.  Since the
 231   // region table occurs at the tail of the memory region, this pointer
 232   // points somewhere inside the region memory space, and not to the start
 233   // of the memory space.
 234   const JitcodeIonTable* regionTable_;
 235
 236  public:
 237   IonEntry(JitCode* code, void* nativeStartAddr, void* nativeEndAddr,
 238            ScriptList&& scriptList, JitcodeIonTable* regionTable)
 239       : JitcodeGlobalEntry(Kind::Ion, code, nativeStartAddr, nativeEndAddr),
 240         scriptList_(std::move(scriptList)),
 241         regionTable_(regionTable) {
 242     MOZ_ASSERT(regionTable);
 243   }
 244
 245   ~IonEntry();
 246
 247   ScriptList& scriptList() { return scriptList_; }
 248
 249   size_t numScripts() const { return scriptList_.length(); }
 250
 251   JSScript* getScript(unsigned idx) const {
 252     MOZ_ASSERT(idx < numScripts());
 253     return scriptList_[idx].script;
 254   }
 255
 256   const char* getStr(unsigned idx) const {
 257     MOZ_ASSERT(idx < numScripts());
 258     return scriptList_[idx].str.get();
 259   }
 260
 261   const JitcodeIonTable* regionTable() const { return regionTable_; }
 262
 263   void* canonicalNativeAddrFor(void* ptr) const;
 264
 265   [[nodiscard]] bool callStackAtAddr(void* ptr, BytecodeLocationVector& results,
 266                                      uint32_t* depth) const;
 267
 268   uint32_t callStackAtAddr(void* ptr, const char** results,
 269                            uint32_t maxResults) const;
 270
 271   uint64_t lookupRealmID(void* ptr) const;
 272
 273   bool trace(JSTracer* trc);
 274   void traceWeak(JSTracer* trc);
 275 };
 276
 277 class IonICEntry : public JitcodeGlobalEntry {
 278   // Address for this IC in the IonScript code. Most operations on IonICEntry
 279   // use this to forward to the IonEntry.
 280   void* rejoinAddr_;
 281
 282  public:
 283   IonICEntry(JitCode* code, void* nativeStartAddr, void* nativeEndAddr,
 284              void* rejoinAddr)
 285       : JitcodeGlobalEntry(Kind::IonIC, code, nativeStartAddr, nativeEndAddr),
 286         rejoinAddr_(rejoinAddr) {
 287     MOZ_ASSERT(rejoinAddr_);
 288   }
 289
 290   void* rejoinAddr() const { return rejoinAddr_; }
 291
 292   void* canonicalNativeAddrFor(void* ptr) const;
 293
 294   [[nodiscard]] bool callStackAtAddr(JSRuntime* rt, void* ptr,
 295                                      BytecodeLocationVector& results,
 296                                      uint32_t* depth) const;
 297
 298   uint32_t callStackAtAddr(JSRuntime* rt, void* ptr, const char** results,
 299                            uint32_t maxResults) const;
 300
 301   uint64_t lookupRealmID(JSRuntime* rt, void* ptr) const;
 302
 303   bool trace(JSTracer* trc);
 304   void traceWeak(JSTracer* trc);
 305 };
 306
 307 class BaselineEntry : public JitcodeGlobalEntry {
 308   JSScript* script_;
 309   UniqueChars str_;
 310
 311  public:
 312   BaselineEntry(JitCode* code, void* nativeStartAddr, void* nativeEndAddr,
 313                 JSScript* script, UniqueChars str)
 314       : JitcodeGlobalEntry(Kind::Baseline, code, nativeStartAddr,
 315                            nativeEndAddr),
 316         script_(script),
 317         str_(std::move(str)) {
 318     MOZ_ASSERT(script_);
 319     MOZ_ASSERT(str_);
 320   }
 321
 322   JSScript* script() const { return script_; }
 323
 324   const char* str() const { return str_.get(); }
 325
 326   void* canonicalNativeAddrFor(void* ptr) const;
 327
 328   [[nodiscard]] bool callStackAtAddr(void* ptr, BytecodeLocationVector& results,
 329                                      uint32_t* depth) const;
 330
 331   uint32_t callStackAtAddr(void* ptr, const char** results,
 332                            uint32_t maxResults) const;
 333
 334   uint64_t lookupRealmID() const;
 335
 336   bool trace(JSTracer* trc);
 337   void traceWeak(JSTracer* trc);
 338 };
 339
 340 class BaselineInterpreterEntry : public JitcodeGlobalEntry {
 341  public:
 342   BaselineInterpreterEntry(JitCode* code, void* nativeStartAddr,
 343                            void* nativeEndAddr)
 344       : JitcodeGlobalEntry(Kind::BaselineInterpreter, code, nativeStartAddr,
 345                            nativeEndAddr) {}
 346
 347   void* canonicalNativeAddrFor(void* ptr) const;
 348
 349   [[nodiscard]] bool callStackAtAddr(void* ptr, BytecodeLocationVector& results,
 350                                      uint32_t* depth) const;
 351
 352   uint32_t callStackAtAddr(void* ptr, const char** results,
 353                            uint32_t maxResults) const;
 354
 355   uint64_t lookupRealmID() const;
 356 };
 357
 358 // Dummy entries are created for jitcode generated when profiling is not
 359 // turned on, so that they have representation in the global table if they are
 360 // on the stack when profiling is enabled.
 361 class DummyEntry : public JitcodeGlobalEntry {
 362  public:
 363   DummyEntry(JitCode* code, void* nativeStartAddr, void* nativeEndAddr)
 364       : JitcodeGlobalEntry(Kind::Dummy, code, nativeStartAddr, nativeEndAddr) {}
 365
 366   void* canonicalNativeAddrFor(JSRuntime* rt, void* ptr) const {
 367     return nullptr;
 368   }
 369
 370   [[nodiscard]] bool callStackAtAddr(JSRuntime* rt, void* ptr,
 371                                      BytecodeLocationVector& results,
 372                                      uint32_t* depth) const {
 373     return true;
 374   }
 375
 376   uint32_t callStackAtAddr(JSRuntime* rt, void* ptr, const char** results,
 377                            uint32_t maxResults) const {
 378     return 0;
 379   }
 380
 381   uint64_t lookupRealmID() const { return 0; }
 382 };
 383
 384 inline const IonEntry& JitcodeGlobalEntry::asIon() const {
 385   MOZ_ASSERT(isIon());
 386   return *static_cast<const IonEntry*>(this);
 387 }
 388
 389 inline const IonICEntry& JitcodeGlobalEntry::asIonIC() const {
 390   MOZ_ASSERT(isIonIC());
 391   return *static_cast<const IonICEntry*>(this);
 392 }
 393
 394 inline const BaselineEntry& JitcodeGlobalEntry::asBaseline() const {
 395   MOZ_ASSERT(isBaseline());
 396   return *static_cast<const BaselineEntry*>(this);
 397 }
 398
 399 inline const BaselineInterpreterEntry&
 400 JitcodeGlobalEntry::asBaselineInterpreter() const {
 401   MOZ_ASSERT(isBaselineInterpreter());
 402   return *static_cast<const BaselineInterpreterEntry*>(this);
 403 }
 404
 405 inline const DummyEntry& JitcodeGlobalEntry::asDummy() const {
 406   MOZ_ASSERT(isDummy());
 407   return *static_cast<const DummyEntry*>(this);
 408 }
 409
 410 inline IonEntry& JitcodeGlobalEntry::asIon() {
 411   MOZ_ASSERT(isIon());
 412   return *static_cast<IonEntry*>(this);
 413 }
 414
 415 inline IonICEntry& JitcodeGlobalEntry::asIonIC() {
 416   MOZ_ASSERT(isIonIC());
 417   return *static_cast<IonICEntry*>(this);
 418 }
 419
 420 inline BaselineEntry& JitcodeGlobalEntry::asBaseline() {
 421   MOZ_ASSERT(isBaseline());
 422   return *static_cast<BaselineEntry*>(this);
 423 }
 424
 425 inline BaselineInterpreterEntry& JitcodeGlobalEntry::asBaselineInterpreter() {
 426   MOZ_ASSERT(isBaselineInterpreter());
 427   return *static_cast<BaselineInterpreterEntry*>(this);
 428 }
 429
 430 inline DummyEntry& JitcodeGlobalEntry::asDummy() {
 431   MOZ_ASSERT(isDummy());
 432   return *static_cast<DummyEntry*>(this);
 433 }
 434
 435 // Global table of JitcodeGlobalEntry entries.
 436 class JitcodeGlobalTable {
 437  private:
 438   // Vector containing (and owning) all entries. This is unsorted and used for
 439   // iterating over all entries, because the AvlTree currently doesn't support
 440   // modifications while iterating.
 441   using EntryVector = Vector<UniqueJitcodeGlobalEntry, 0, SystemAllocPolicy>;
 442   EntryVector entries_;
 443
 444   // AVL tree containing all entries in the Vector above. This is used to
 445   // efficiently look up the entry corresponding to a native code address.
 446   using EntryTree = AvlTree<JitCodeRange*, JitCodeRange>;
 447   static const size_t LIFO_CHUNK_SIZE = 16 * 1024;
 448   LifoAlloc alloc_;
 449   EntryTree tree_;
 450
 451  public:
 452   JitcodeGlobalTable() : alloc_(LIFO_CHUNK_SIZE), tree_(&alloc_) {}
 453
 454   bool empty() const {
 455     MOZ_ASSERT(entries_.empty() == tree_.empty());
 456     return entries_.empty();
 457   }
 458
 459   JitcodeGlobalEntry* lookup(void* ptr) { return lookupInternal(ptr); }
 460
 461   const JitcodeGlobalEntry* lookupForSampler(void* ptr, JSRuntime* rt,
 462                                              uint64_t samplePosInBuffer);
 463
 464   [[nodiscard]] bool addEntry(UniqueJitcodeGlobalEntry entry);
 465
 466   void setAllEntriesAsExpired();
 467   [[nodiscard]] bool markIteratively(GCMarker* marker);
 468   void traceWeak(JSRuntime* rt, JSTracer* trc);
 469
 470  private:
 471   JitcodeGlobalEntry* lookupInternal(void* ptr);
 472 };
 473
 474 // clang-format off
 475 /*
 476  * Container class for main jitcode table.
 477  * The Region table's memory is structured as follows:
 478  *
 479  *      +------------------------------------------------+   |
 480  *      |  Region 1 Run                                  |   |
 481  *      |------------------------------------------------|   |
 482  *      |  Region 2 Run                                  |   |
 483  *      |                                                |   |
 484  *      |                                                |   |
 485  *      |------------------------------------------------|   |
 486  *      |  Region 3 Run                                  |   |
 487  *      |                                                |   |
 488  *      |------------------------------------------------|   |-- Payload
 489  *      |                                                |   |
 490  *      |               ...                              |   |
 491  *      |                                                |   |
 492  *      |------------------------------------------------|   |
 493  *      |  Region M Run                                  |   |
 494  *      |                                                |   |
 495  *      +================================================+ <- RegionTable pointer points here
 496  *      | uint23_t numRegions = M                        |   |
 497  *      +------------------------------------------------+   |
 498  *      | Region 1                                       |   |
 499  *      |   uint32_t entryOffset = size(Payload)         |   |
 500  *      +------------------------------------------------+   |
 501  *      |                                                |   |-- Table
 502  *      |   ...                                          |   |
 503  *      |                                                |   |
 504  *      +------------------------------------------------+   |
 505  *      | Region M                                       |   |
 506  *      |   uint32_t entryOffset                         |   |
 507  *      +------------------------------------------------+   |
 508  *
 509  * The region table is composed of two sections: a tail section that contains a table of
 510  * fixed-size entries containing offsets into the the head section, and a head section that
 511  * holds a sequence of variable-sized runs.  The table in the tail section serves to
 512  * locate the variable-length encoded structures in the head section.
 513  *
 514  * The entryOffsets in the table indicate the bytes offset to subtract from the regionTable
 515  * pointer to arrive at the encoded region in the payload.
 516  *
 517  *
 518  * Variable-length entries in payload
 519  * ----------------------------------
 520  * The entryOffsets in the region table's fixed-sized entries refer to a location within the
 521  * variable-length payload section.  This location contains a compactly encoded "run" of
 522  * mappings.
 523  *
 524  * Each run starts by describing the offset within the native code it starts at, and the
 525  * sequence of (JSScript*, jsbytecode*) pairs active at that site.  Following that, there
 526  * are a number of variable-length entries encoding (nativeOffsetDelta, bytecodeOffsetDelta)
 527  * pairs for the run.
 528  *
 529  *      VarUint32 nativeOffset;
 530  *          - The offset from nativeStartAddr in the global table entry at which
 531  *            the jitcode for this region starts.
 532  *
 533  *      Uint8_t scriptDepth;
 534  *          - The depth of inlined scripts for this region.
 535  *
 536  *      List<VarUint32> inlineScriptPcStack;
 537  *          - We encode (2 * scriptDepth) VarUint32s here.  Each pair of uint32s are taken
 538  *            as an index into the scriptList in the global table entry, and a pcOffset
 539  *            respectively.
 540  *
 541  *      List<NativeAndBytecodeDelta> deltaRun;
 542  *          - The rest of the entry is a deltaRun that stores a series of variable-length
 543  *            encoded NativeAndBytecodeDelta datums.
 544  */
 545 // clang-format on
 546 class JitcodeRegionEntry {
 547  private:
 548   static const unsigned MAX_RUN_LENGTH = 100;
 549
 550  public:
 551   static void WriteHead(CompactBufferWriter& writer, uint32_t nativeOffset,
 552                         uint8_t scriptDepth);
 553   static void ReadHead(CompactBufferReader& reader, uint32_t* nativeOffset,
 554                        uint8_t* scriptDepth);
 555
 556   static void WriteScriptPc(CompactBufferWriter& writer, uint32_t scriptIdx,
 557                             uint32_t pcOffset);
 558   static void ReadScriptPc(CompactBufferReader& reader, uint32_t* scriptIdx,
 559                            uint32_t* pcOffset);
 560
 561   static void WriteDelta(CompactBufferWriter& writer, uint32_t nativeDelta,
 562                          int32_t pcDelta);
 563   static void ReadDelta(CompactBufferReader& reader, uint32_t* nativeDelta,
 564                         int32_t* pcDelta);
 565
 566   // Given a pointer into an array of NativeToBytecode (and a pointer to the end
 567   // of the array), compute the number of entries that would be consume by
 568   // outputting a run starting at this one.
 569   static uint32_t ExpectedRunLength(const NativeToBytecode* entry,
 570                                     const NativeToBytecode* end);
 571
 572   // Write a run, starting at the given NativeToBytecode entry, into the given
 573   // buffer writer.
 574   [[nodiscard]] static bool WriteRun(CompactBufferWriter& writer,
 575                                      const IonEntry::ScriptList& scriptList,
 576                                      uint32_t runLength,
 577                                      const NativeToBytecode* entry);
 578
 579   // Delta Run entry formats are encoded little-endian:
 580   //
 581   //  byte 0
 582   //  NNNN-BBB0
 583   //      Single byte format.  nativeDelta in [0, 15], pcDelta in [0, 7]
 584   //
 585   static const uint32_t ENC1_MASK = 0x1;
 586   static const uint32_t ENC1_MASK_VAL = 0x0;
 587
 588   static const uint32_t ENC1_NATIVE_DELTA_MAX = 0xf;
 589   static const unsigned ENC1_NATIVE_DELTA_SHIFT = 4;
 590
 591   static const uint32_t ENC1_PC_DELTA_MASK = 0x0e;
 592   static const int32_t ENC1_PC_DELTA_MAX = 0x7;
 593   static const unsigned ENC1_PC_DELTA_SHIFT = 1;
 594
 595   //  byte 1    byte 0
 596   //  NNNN-NNNN BBBB-BB01
 597   //      Two-byte format.  nativeDelta in [0, 255], pcDelta in [0, 63]
 598   //
 599   static const uint32_t ENC2_MASK = 0x3;
 600   static const uint32_t ENC2_MASK_VAL = 0x1;
 601
 602   static const uint32_t ENC2_NATIVE_DELTA_MAX = 0xff;
 603   static const unsigned ENC2_NATIVE_DELTA_SHIFT = 8;
 604
 605   static const uint32_t ENC2_PC_DELTA_MASK = 0x00fc;
 606   static const int32_t ENC2_PC_DELTA_MAX = 0x3f;
 607   static const unsigned ENC2_PC_DELTA_SHIFT = 2;
 608
 609   //  byte 2    byte 1    byte 0
 610   //  NNNN-NNNN NNNB-BBBB BBBB-B011
 611   //      Three-byte format.  nativeDelta in [0, 2047], pcDelta in [-512, 511]
 612   //
 613   static const uint32_t ENC3_MASK = 0x7;
 614   static const uint32_t ENC3_MASK_VAL = 0x3;
 615
 616   static const uint32_t ENC3_NATIVE_DELTA_MAX = 0x7ff;
 617   static const unsigned ENC3_NATIVE_DELTA_SHIFT = 13;
 618
 619   static const uint32_t ENC3_PC_DELTA_MASK = 0x001ff8;
 620   static const int32_t ENC3_PC_DELTA_MAX = 0x1ff;
 621   static const int32_t ENC3_PC_DELTA_MIN = -ENC3_PC_DELTA_MAX - 1;
 622   static const unsigned ENC3_PC_DELTA_SHIFT = 3;
 623
 624   //  byte 3    byte 2    byte 1    byte 0
 625   //  NNNN-NNNN NNNN-NNNN BBBB-BBBB BBBB-B111
 626   //      Three-byte format.  nativeDelta in [0, 65535],
 627   //                          pcDelta in [-4096, 4095]
 628   static const uint32_t ENC4_MASK = 0x7;
 629   static const uint32_t ENC4_MASK_VAL = 0x7;
 630
 631   static const uint32_t ENC4_NATIVE_DELTA_MAX = 0xffff;
 632   static const unsigned ENC4_NATIVE_DELTA_SHIFT = 16;
 633
 634   static const uint32_t ENC4_PC_DELTA_MASK = 0x0000fff8;
 635   static const int32_t ENC4_PC_DELTA_MAX = 0xfff;
 636   static const int32_t ENC4_PC_DELTA_MIN = -ENC4_PC_DELTA_MAX - 1;
 637   static const unsigned ENC4_PC_DELTA_SHIFT = 3;
 638
 639   static bool IsDeltaEncodeable(uint32_t nativeDelta, int32_t pcDelta) {
 640     return (nativeDelta <= ENC4_NATIVE_DELTA_MAX) &&
 641            (pcDelta >= ENC4_PC_DELTA_MIN) && (pcDelta <= ENC4_PC_DELTA_MAX);
 642   }
 643
 644  private:
 645   const uint8_t* data_;
 646   const uint8_t* end_;
 647
 648   // Unpacked state from jitcode entry.
 649   uint32_t nativeOffset_;
 650   uint8_t scriptDepth_;
 651   const uint8_t* scriptPcStack_;
 652   const uint8_t* deltaRun_;
 653
 654   void unpack();
 655
 656  public:
 657   JitcodeRegionEntry(const uint8_t* data, const uint8_t* end)
 658       : data_(data),
 659         end_(end),
 660         nativeOffset_(0),
 661         scriptDepth_(0),
 662         scriptPcStack_(nullptr),
 663         deltaRun_(nullptr) {
 664     MOZ_ASSERT(data_ < end_);
 665     unpack();
 666     MOZ_ASSERT(scriptPcStack_ < end_);
 667     MOZ_ASSERT(deltaRun_ <= end_);
 668   }
 669
 670   uint32_t nativeOffset() const { return nativeOffset_; }
 671   uint32_t scriptDepth() const { return scriptDepth_; }
 672
 673   class ScriptPcIterator {
 674    private:
 675     const uint8_t* start_;
 676     const uint8_t* end_;
 677 #ifdef DEBUG
 678     uint32_t count_;
 679 #endif
 680     uint32_t idx_;
 681     const uint8_t* cur_;
 682
 683    public:
 684     ScriptPcIterator(const uint8_t* start, const uint8_t* end, uint32_t count)
 685         : start_(start),
 686           end_(end),
 687 #ifdef DEBUG
 688           count_(count),
 689 #endif
 690           idx_(0),
 691           cur_(start_) {
 692     }
 693
 694     bool hasMore() const {
 695       MOZ_ASSERT((idx_ == count_) == (cur_ == end_));
 696       MOZ_ASSERT((idx_ < count_) == (cur_ < end_));
 697       return cur_ < end_;
 698     }
 699
 700     void readNext(uint32_t* scriptIdxOut, uint32_t* pcOffsetOut) {
 701       MOZ_ASSERT(scriptIdxOut);
 702       MOZ_ASSERT(pcOffsetOut);
 703       MOZ_ASSERT(hasMore());
 704
 705       CompactBufferReader reader(cur_, end_);
 706       ReadScriptPc(reader, scriptIdxOut, pcOffsetOut);
 707
 708       cur_ = reader.currentPosition();
 709       MOZ_ASSERT(cur_ <= end_);
 710
 711       idx_++;
 712       MOZ_ASSERT_IF(idx_ == count_, cur_ == end_);
 713     }
 714
 715     void reset() {
 716       idx_ = 0;
 717       cur_ = start_;
 718     }
 719   };
 720
 721   ScriptPcIterator scriptPcIterator() const {
 722     // End of script+pc sequence is the start of the delta run.
 723     return ScriptPcIterator(scriptPcStack_, deltaRun_, scriptDepth_);
 724   }
 725
 726   class DeltaIterator {
 727    private:
 728     const uint8_t* start_;
 729     const uint8_t* end_;
 730     const uint8_t* cur_;
 731
 732    public:
 733     DeltaIterator(const uint8_t* start, const uint8_t* end)
 734         : start_(start), end_(end), cur_(start) {}
 735
 736     bool hasMore() const {
 737       MOZ_ASSERT(cur_ <= end_);
 738       return cur_ < end_;
 739     }
 740
 741     void readNext(uint32_t* nativeDeltaOut, int32_t* pcDeltaOut) {
 742       MOZ_ASSERT(nativeDeltaOut != nullptr);
 743       MOZ_ASSERT(pcDeltaOut != nullptr);
 744
 745       MOZ_ASSERT(hasMore());
 746
 747       CompactBufferReader reader(cur_, end_);
 748       ReadDelta(reader, nativeDeltaOut, pcDeltaOut);
 749
 750       cur_ = reader.currentPosition();
 751       MOZ_ASSERT(cur_ <= end_);
 752     }
 753
 754     void reset() { cur_ = start_; }
 755   };
 756   DeltaIterator deltaIterator() const { return DeltaIterator(deltaRun_, end_); }
 757
 758   uint32_t findPcOffset(uint32_t queryNativeOffset,
 759                         uint32_t startPcOffset) const;
 760 };
 761
 762 class JitcodeIonTable {
 763  private:
 764   /* Variable length payload section "below" here. */
 765   uint32_t numRegions_;
 766   uint32_t regionOffsets_[1];
 767
 768   const uint8_t* payloadEnd() const {
 769     return reinterpret_cast<const uint8_t*>(this);
 770   }
 771
 772  public:
 773   JitcodeIonTable() = delete;
 774
 775   uint32_t numRegions() const { return numRegions_; }
 776
 777   uint32_t regionOffset(uint32_t regionIndex) const {
 778     MOZ_ASSERT(regionIndex < numRegions());
 779     return regionOffsets_[regionIndex];
 780   }
 781
 782   JitcodeRegionEntry regionEntry(uint32_t regionIndex) const {
 783     const uint8_t* regionStart = payloadEnd() - regionOffset(regionIndex);
 784     const uint8_t* regionEnd = payloadEnd();
 785     if (regionIndex < numRegions_ - 1) {
 786       regionEnd -= regionOffset(regionIndex + 1);
 787     }
 788     return JitcodeRegionEntry(regionStart, regionEnd);
 789   }
 790
 791   uint32_t findRegionEntry(uint32_t offset) const;
 792
 793   const uint8_t* payloadStart() const {
 794     // The beginning of the payload the beginning of the first region are the
 795     // same.
 796     return payloadEnd() - regionOffset(0);
 797   }
 798
 799   [[nodiscard]] static bool WriteIonTable(
 800       CompactBufferWriter& writer, const IonEntry::ScriptList& scriptList,
 801       const NativeToBytecode* start, const NativeToBytecode* end,
 802       uint32_t* tableOffsetOut, uint32_t* numRegionsOut);
 803 };
 804
 805 }  // namespace jit
 806 }  // namespace js
 807
 808 #endif /* jit_JitcodeMap_h */