mozglue/baseprofiler/lul/LulMainInt.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 LulMainInt_h
   8 #define LulMainInt_h
   9
  10 #include "PlatformMacros.h"
  11 #include "LulMain.h"  // for TaggedUWord
  12
  13 #include "mozilla/Assertions.h"
  14
  15 #include <string>
  16 #include <vector>
  17
  18 // This file is provides internal interface inside LUL.  If you are an
  19 // end-user of LUL, do not include it in your code.  The end-user
  20 // interface is in LulMain.h.
  21
  22 namespace lul {
  23
  24 using std::vector;
  25
  26 ////////////////////////////////////////////////////////////////
  27 // DW_REG_ constants                                          //
  28 ////////////////////////////////////////////////////////////////
  29
  30 // These are the Dwarf CFI register numbers, as (presumably) defined
  31 // in the ELF ABI supplements for each architecture.
  32
  33 enum DW_REG_NUMBER {
  34   // No real register has this number.  It's convenient to be able to
  35   // treat the CFA (Canonical Frame Address) as "just another
  36   // register", though.
  37   DW_REG_CFA = -1,
  38 #if defined(GP_ARCH_arm)
  39   // ARM registers
  40   DW_REG_ARM_R7 = 7,
  41   DW_REG_ARM_R11 = 11,
  42   DW_REG_ARM_R12 = 12,
  43   DW_REG_ARM_R13 = 13,
  44   DW_REG_ARM_R14 = 14,
  45   DW_REG_ARM_R15 = 15,
  46 #elif defined(GP_ARCH_arm64)
  47   // aarch64 registers
  48   DW_REG_AARCH64_X29 = 29,
  49   DW_REG_AARCH64_X30 = 30,
  50   DW_REG_AARCH64_SP = 31,
  51 #elif defined(GP_ARCH_amd64)
  52   // Because the X86 (32 bit) and AMD64 (64 bit) summarisers are
  53   // combined, a merged set of register constants is needed.
  54   DW_REG_INTEL_XBP = 6,
  55   DW_REG_INTEL_XSP = 7,
  56   DW_REG_INTEL_XIP = 16,
  57 #elif defined(GP_ARCH_x86)
  58   DW_REG_INTEL_XBP = 5,
  59   DW_REG_INTEL_XSP = 4,
  60   DW_REG_INTEL_XIP = 8,
  61 #elif defined(GP_ARCH_mips64)
  62   DW_REG_MIPS_SP = 29,
  63   DW_REG_MIPS_FP = 30,
  64   DW_REG_MIPS_PC = 34,
  65 #else
  66 #  error "Unknown arch"
  67 #endif
  68 };
  69
  70 ////////////////////////////////////////////////////////////////
  71 // PfxExpr                                                    //
  72 ////////////////////////////////////////////////////////////////
  73
  74 enum PfxExprOp {
  75   //             meaning of mOperand     effect on stack
  76   PX_Start,   // bool start-with-CFA?    start, with CFA on stack, or not
  77   PX_End,     // none                    stop; result is at top of stack
  78   PX_SImm32,  // int32                   push signed int32
  79   PX_DwReg,   // DW_REG_NUMBER           push value of the specified reg
  80   PX_Deref,   // none                    pop X ; push *X
  81   PX_Add,     // none                    pop X ; pop Y ; push Y + X
  82   PX_Sub,     // none                    pop X ; pop Y ; push Y - X
  83   PX_And,     // none                    pop X ; pop Y ; push Y & X
  84   PX_Or,      // none                    pop X ; pop Y ; push Y | X
  85   PX_CmpGES,  // none                    pop X ; pop Y ; push (Y >=s X) ? 1 : 0
  86   PX_Shl      // none                    pop X ; pop Y ; push Y << X
  87 };
  88
  89 struct PfxInstr {
  90   PfxInstr(PfxExprOp opcode, int32_t operand)
  91       : mOpcode(opcode), mOperand(operand) {}
  92   explicit PfxInstr(PfxExprOp opcode) : mOpcode(opcode), mOperand(0) {}
  93   bool operator==(const PfxInstr& other) const {
  94     return mOpcode == other.mOpcode && mOperand == other.mOperand;
  95   }
  96   PfxExprOp mOpcode;
  97   int32_t mOperand;
  98 };
  99
 100 static_assert(sizeof(PfxInstr) <= 8, "PfxInstr size changed unexpectedly");
 101
 102 // Evaluate the prefix expression whose PfxInstrs start at aPfxInstrs[start].
 103 // In the case of any mishap (stack over/underflow, running off the end of
 104 // the instruction vector, obviously malformed sequences),
 105 // return an invalid TaggedUWord.
 106 // RUNS IN NO-MALLOC CONTEXT
 107 TaggedUWord EvaluatePfxExpr(int32_t start, const UnwindRegs* aOldRegs,
 108                             TaggedUWord aCFA, const StackImage* aStackImg,
 109                             const vector<PfxInstr>& aPfxInstrs);
 110
 111 ////////////////////////////////////////////////////////////////
 112 // LExpr                                                      //
 113 ////////////////////////////////////////////////////////////////
 114
 115 // An expression -- very primitive.  Denotes either "register +
 116 // offset", a dereferenced version of the same, or a reference to a
 117 // prefix expression stored elsewhere.  So as to allow convenient
 118 // handling of Dwarf-derived unwind info, the register may also denote
 119 // the CFA.  A large number of these need to be stored, so we ensure
 120 // it fits into 8 bytes.  See comment below on RuleSet to see how
 121 // expressions fit into the bigger picture.
 122
 123 enum LExprHow {
 124   UNKNOWN = 0,  // This LExpr denotes no value.
 125   NODEREF,      // Value is  (mReg + mOffset).
 126   DEREF,        // Value is *(mReg + mOffset).
 127   PFXEXPR       // Value is EvaluatePfxExpr(secMap->mPfxInstrs[mOffset])
 128 };
 129
 130 inline static const char* NameOf_LExprHow(LExprHow how) {
 131   switch (how) {
 132     case UNKNOWN:
 133       return "UNKNOWN";
 134     case NODEREF:
 135       return "NODEREF";
 136     case DEREF:
 137       return "DEREF";
 138     case PFXEXPR:
 139       return "PFXEXPR";
 140     default:
 141       return "LExpr-??";
 142   }
 143 }
 144
 145 struct LExpr {
 146   // Denotes an expression with no value.
 147   LExpr() : mHow(UNKNOWN), mReg(0), mOffset(0) {}
 148
 149   // Denotes any expressible expression.
 150   LExpr(LExprHow how, int16_t reg, int32_t offset)
 151       : mHow(how), mReg(reg), mOffset(offset) {
 152     switch (how) {
 153       case UNKNOWN:
 154         MOZ_ASSERT(reg == 0 && offset == 0);
 155         break;
 156       case NODEREF:
 157         break;
 158       case DEREF:
 159         break;
 160       case PFXEXPR:
 161         MOZ_ASSERT(reg == 0 && offset >= 0);
 162         break;
 163       default:
 164         MOZ_ASSERT(0, "LExpr::LExpr: invalid how");
 165     }
 166   }
 167
 168   // Change the offset for an expression that references memory.
 169   LExpr add_delta(long delta) {
 170     MOZ_ASSERT(mHow == NODEREF);
 171     // If this is a non-debug build and the above assertion would have
 172     // failed, at least return LExpr() so that the machinery that uses
 173     // the resulting expression fails in a repeatable way.
 174     return (mHow == NODEREF) ? LExpr(mHow, mReg, mOffset + delta)
 175                              : LExpr();  // Gone bad
 176   }
 177
 178   // Dereference an expression that denotes a memory address.
 179   LExpr deref() {
 180     MOZ_ASSERT(mHow == NODEREF);
 181     // Same rationale as for add_delta().
 182     return (mHow == NODEREF) ? LExpr(DEREF, mReg, mOffset)
 183                              : LExpr();  // Gone bad
 184   }
 185
 186   // Print a rule for recovery of |aNewReg| whose recovered value
 187   // is this LExpr.
 188   std::string ShowRule(const char* aNewReg) const;
 189
 190   // Evaluate this expression, producing a TaggedUWord.  |aOldRegs|
 191   // holds register values that may be referred to by the expression.
 192   // |aCFA| holds the CFA value, if any, that applies.  |aStackImg|
 193   // contains a chuck of stack that will be consulted if the expression
 194   // references memory.  |aPfxInstrs| holds the vector of PfxInstrs
 195   // that will be consulted if this is a PFXEXPR.
 196   // RUNS IN NO-MALLOC CONTEXT
 197   TaggedUWord EvaluateExpr(const UnwindRegs* aOldRegs, TaggedUWord aCFA,
 198                            const StackImage* aStackImg,
 199                            const vector<PfxInstr>* aPfxInstrs) const;
 200
 201   // Representation of expressions.  If |mReg| is DW_REG_CFA (-1) then
 202   // it denotes the CFA.  All other allowed values for |mReg| are
 203   // nonnegative and are DW_REG_ values.
 204   LExprHow mHow : 8;
 205   int16_t mReg;     // A DW_REG_ value
 206   int32_t mOffset;  // 32-bit signed offset should be more than enough.
 207 };
 208
 209 static_assert(sizeof(LExpr) <= 8, "LExpr size changed unexpectedly");
 210
 211 ////////////////////////////////////////////////////////////////
 212 // RuleSet                                                    //
 213 ////////////////////////////////////////////////////////////////
 214
 215 // This is platform-dependent.  For some address range, describes how
 216 // to recover the CFA and then how to recover the registers for the
 217 // previous frame.
 218 //
 219 // The set of LExprs contained in a given RuleSet describe a DAG which
 220 // says how to compute the caller's registers ("new registers") from
 221 // the callee's registers ("old registers").  The DAG can contain a
 222 // single internal node, which is the value of the CFA for the callee.
 223 // It would be possible to construct a DAG that omits the CFA, but
 224 // including it makes the summarisers simpler, and the Dwarf CFI spec
 225 // has the CFA as a central concept.
 226 //
 227 // For this to make sense, |mCfaExpr| can't have
 228 // |mReg| == DW_REG_CFA since we have no previous value for the CFA.
 229 // All of the other |Expr| fields can -- and usually do -- specify
 230 // |mReg| == DW_REG_CFA.
 231 //
 232 // With that in place, the unwind algorithm proceeds as follows.
 233 //
 234 // (0) Initially: we have values for the old registers, and a memory
 235 //     image.
 236 //
 237 // (1) Compute the CFA by evaluating |mCfaExpr|.  Add the computed
 238 //     value to the set of "old registers".
 239 //
 240 // (2) Compute values for the registers by evaluating all of the other
 241 //     |Expr| fields in the RuleSet.  These can depend on both the old
 242 //     register values and the just-computed CFA.
 243 //
 244 // If we are unwinding without computing a CFA, perhaps because the
 245 // RuleSets are derived from EXIDX instead of Dwarf, then
 246 // |mCfaExpr.mHow| will be LExpr::UNKNOWN, so the computed value will
 247 // be invalid -- that is, TaggedUWord() -- and so any attempt to use
 248 // that will result in the same value.  But that's OK because the
 249 // RuleSet would make no sense if depended on the CFA but specified no
 250 // way to compute it.
 251 //
 252 // A RuleSet is not allowed to cover zero address range.  Having zero
 253 // length would break binary searching in SecMaps and PriMaps.
 254
 255 class RuleSet {
 256  public:
 257   RuleSet();
 258   void Print(void (*aLog)(const char*)) const;
 259
 260   // Find the LExpr* for a given DW_REG_ value in this class.
 261   LExpr* ExprForRegno(DW_REG_NUMBER aRegno);
 262
 263   uintptr_t mAddr;
 264   uintptr_t mLen;
 265   // How to compute the CFA.
 266   LExpr mCfaExpr;
 267   // How to compute caller register values.  These may reference the
 268   // value defined by |mCfaExpr|.
 269 #if defined(GP_ARCH_amd64) || defined(GP_ARCH_x86)
 270   LExpr mXipExpr;  // return address
 271   LExpr mXspExpr;
 272   LExpr mXbpExpr;
 273 #elif defined(GP_ARCH_arm)
 274   LExpr mR15expr;  // return address
 275   LExpr mR14expr;
 276   LExpr mR13expr;
 277   LExpr mR12expr;
 278   LExpr mR11expr;
 279   LExpr mR7expr;
 280 #elif defined(GP_ARCH_arm64)
 281   LExpr mX29expr;  // frame pointer register
 282   LExpr mX30expr;  // link register
 283   LExpr mSPexpr;
 284 #elif defined(GP_ARCH_mips64)
 285   LExpr mPCexpr;
 286   LExpr mFPexpr;
 287   LExpr mSPexpr;
 288 #else
 289 #  error "Unknown arch"
 290 #endif
 291 };
 292
 293 // Returns |true| for Dwarf register numbers which are members
 294 // of the set of registers that LUL unwinds on this target.
 295 static inline bool registerIsTracked(DW_REG_NUMBER reg) {
 296   switch (reg) {
 297 #if defined(GP_ARCH_amd64) || defined(GP_ARCH_x86)
 298     case DW_REG_INTEL_XBP:
 299     case DW_REG_INTEL_XSP:
 300     case DW_REG_INTEL_XIP:
 301       return true;
 302 #elif defined(GP_ARCH_arm)
 303     case DW_REG_ARM_R7:
 304     case DW_REG_ARM_R11:
 305     case DW_REG_ARM_R12:
 306     case DW_REG_ARM_R13:
 307     case DW_REG_ARM_R14:
 308     case DW_REG_ARM_R15:
 309       return true;
 310 #elif defined(GP_ARCH_arm64)
 311     case DW_REG_AARCH64_X29:
 312     case DW_REG_AARCH64_X30:
 313     case DW_REG_AARCH64_SP:
 314       return true;
 315 #elif defined(GP_ARCH_mips64)
 316     case DW_REG_MIPS_FP:
 317     case DW_REG_MIPS_SP:
 318     case DW_REG_MIPS_PC:
 319       return true;
 320 #else
 321 #  error "Unknown arch"
 322 #endif
 323     default:
 324       return false;
 325   }
 326 }
 327
 328 ////////////////////////////////////////////////////////////////
 329 // SecMap                                                     //
 330 ////////////////////////////////////////////////////////////////
 331
 332 // A SecMap may have zero address range, temporarily, whilst RuleSets
 333 // are being added to it.  But adding a zero-range SecMap to a PriMap
 334 // will make it impossible to maintain the total order of the PriMap
 335 // entries, and so that can't be allowed to happen.
 336
 337 class SecMap {
 338  public:
 339   // These summarise the contained mRuleSets, in that they give
 340   // exactly the lowest and highest addresses that any of the entries
 341   // in this SecMap cover.  Hence invariants:
 342   //
 343   // mRuleSets is nonempty
 344   //    <=> mSummaryMinAddr <= mSummaryMaxAddr
 345   //        && mSummaryMinAddr == mRuleSets[0].mAddr
 346   //        && mSummaryMaxAddr == mRuleSets[#rulesets-1].mAddr
 347   //                              + mRuleSets[#rulesets-1].mLen - 1;
 348   //
 349   // This requires that no RuleSet has zero length.
 350   //
 351   // mRuleSets is empty
 352   //    <=> mSummaryMinAddr > mSummaryMaxAddr
 353   //
 354   // This doesn't constrain mSummaryMinAddr and mSummaryMaxAddr uniquely,
 355   // so let's use mSummaryMinAddr == 1 and mSummaryMaxAddr == 0 to denote
 356   // this case.
 357
 358   explicit SecMap(void (*aLog)(const char*));
 359   ~SecMap();
 360
 361   // Binary search mRuleSets to find one that brackets |ia|, or nullptr
 362   // if none is found.  It's not allowable to do this until PrepareRuleSets
 363   // has been called first.
 364   RuleSet* FindRuleSet(uintptr_t ia);
 365
 366   // Add a RuleSet to the collection.  The rule is copied in.  Calling
 367   // this makes the map non-searchable.
 368   void AddRuleSet(const RuleSet* rs);
 369
 370   // Add a PfxInstr to the vector of such instrs, and return the index
 371   // in the vector.  Calling this makes the map non-searchable.
 372   uint32_t AddPfxInstr(PfxInstr pfxi);
 373
 374   // Returns the entire vector of PfxInstrs.
 375   const vector<PfxInstr>* GetPfxInstrs() { return &mPfxInstrs; }
 376
 377   // Prepare the map for searching.  Also, remove any rules for code
 378   // address ranges which don't fall inside [start, +len).  |len| may
 379   // not be zero.
 380   void PrepareRuleSets(uintptr_t start, size_t len);
 381
 382   bool IsEmpty();
 383
 384   size_t Size() { return mRuleSets.size(); }
 385
 386   size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
 387
 388   // The min and max addresses of the addresses in the contained
 389   // RuleSets.  See comment above for invariants.
 390   uintptr_t mSummaryMinAddr;
 391   uintptr_t mSummaryMaxAddr;
 392
 393  private:
 394   // False whilst adding entries; true once it is safe to call FindRuleSet.
 395   // Transition (false->true) is caused by calling PrepareRuleSets().
 396   bool mUsable;
 397
 398   // A vector of RuleSets, sorted, nonoverlapping (post Prepare()).
 399   vector<RuleSet> mRuleSets;
 400
 401   // A vector of PfxInstrs, which are referred to by the RuleSets.
 402   // These are provided as a representation of Dwarf expressions
 403   // (DW_CFA_val_expression, DW_CFA_expression, DW_CFA_def_cfa_expression),
 404   // are relatively expensive to evaluate, and and are therefore
 405   // expected to be used only occasionally.
 406   //
 407   // The vector holds a bunch of separate PfxInstr programs, each one
 408   // starting with a PX_Start and terminated by a PX_End, all
 409   // concatenated together.  When a RuleSet can't recover a value
 410   // using a self-contained LExpr, it uses a PFXEXPR whose mOffset is
 411   // the index in this vector of start of the necessary PfxInstr program.
 412   vector<PfxInstr> mPfxInstrs;
 413
 414   // A logging sink, for debugging.
 415   void (*mLog)(const char*);
 416 };
 417
 418 }  // namespace lul
 419
 420 #endif  // ndef LulMainInt_h