tools/profiler/core/EHABIStackWalk.cpp

   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 /*
   8  * This is an implementation of stack unwinding according to a subset
   9  * of the ARM Exception Handling ABI, as described in:
  10  *   http://infocenter.arm.com/help/topic/com.arm.doc.ihi0038a/IHI0038A_ehabi.pdf
  11  *
  12  * This handles only the ARM-defined "personality routines" (chapter
  13  * 9), and don't track the value of FP registers, because profiling
  14  * needs only chain of PC/SP values.
  15  *
  16  * Because the exception handling info may not be accurate for all
  17  * possible places where an async signal could occur (e.g., in a
  18  * prologue or epilogue), this bounds-checks all stack accesses.
  19  *
  20  * This file uses "struct" for structures in the exception tables and
  21  * "class" otherwise.  We should avoid violating the C++11
  22  * standard-layout rules in the former.
  23  */
  24
  25 #include "EHABIStackWalk.h"
  26
  27 #include "SharedLibraries.h"
  28 #include "platform.h"
  29
  30 #include "mozilla/Atomics.h"
  31 #include "mozilla/Attributes.h"
  32 #include "mozilla/DebugOnly.h"
  33 #include "mozilla/EndianUtils.h"
  34
  35 #include <algorithm>
  36 #include <elf.h>
  37 #include <stdint.h>
  38 #include <vector>
  39 #include <string>
  40
  41 #ifndef PT_ARM_EXIDX
  42 #  define PT_ARM_EXIDX 0x70000001
  43 #endif
  44
  45 namespace mozilla {
  46
  47 struct PRel31 {
  48   uint32_t mBits;
  49   bool topBit() const { return mBits & 0x80000000; }
  50   uint32_t value() const { return mBits & 0x7fffffff; }
  51   int32_t offset() const { return (static_cast<int32_t>(mBits) << 1) >> 1; }
  52   const void* compute() const {
  53     return reinterpret_cast<const char*>(this) + offset();
  54   }
  55
  56  private:
  57   PRel31(const PRel31& copied) = delete;
  58   PRel31() = delete;
  59 };
  60
  61 struct EHEntry {
  62   PRel31 startPC;
  63   PRel31 exidx;
  64
  65  private:
  66   EHEntry(const EHEntry& copied) = delete;
  67   EHEntry() = delete;
  68 };
  69
  70 class EHState {
  71   // Note that any core register can be used as a "frame pointer" to
  72   // influence the unwinding process, so this must track all of them.
  73   uint32_t mRegs[16];
  74
  75  public:
  76   bool unwind(const EHEntry* aEntry, const void* stackBase);
  77   uint32_t& operator[](int i) { return mRegs[i]; }
  78   const uint32_t& operator[](int i) const { return mRegs[i]; }
  79   explicit EHState(const mcontext_t&);
  80 };
  81
  82 enum { R_SP = 13, R_LR = 14, R_PC = 15 };
  83
  84 class EHTable {
  85   uint32_t mStartPC;
  86   uint32_t mEndPC;
  87   uint32_t mBaseAddress;
  88   const EHEntry* mEntriesBegin;
  89   const EHEntry* mEntriesEnd;
  90   std::string mName;
  91
  92  public:
  93   EHTable(const void* aELF, size_t aSize, const std::string& aName);
  94   const EHEntry* lookup(uint32_t aPC) const;
  95   bool isValid() const { return mEntriesEnd != mEntriesBegin; }
  96   const std::string& name() const { return mName; }
  97   uint32_t startPC() const { return mStartPC; }
  98   uint32_t endPC() const { return mEndPC; }
  99   uint32_t baseAddress() const { return mBaseAddress; }
 100 };
 101
 102 class EHAddrSpace {
 103   std::vector<uint32_t> mStarts;
 104   std::vector<EHTable> mTables;
 105   static mozilla::Atomic<const EHAddrSpace*> sCurrent;
 106
 107  public:
 108   explicit EHAddrSpace(const std::vector<EHTable>& aTables);
 109   const EHTable* lookup(uint32_t aPC) const;
 110   static void Update();
 111   static const EHAddrSpace* Get();
 112 };
 113
 114 void EHABIStackWalkInit() { EHAddrSpace::Update(); }
 115
 116 size_t EHABIStackWalk(const mcontext_t& aContext, void* stackBase, void** aSPs,
 117                       void** aPCs, const size_t aNumFrames) {
 118   const EHAddrSpace* space = EHAddrSpace::Get();
 119   EHState state(aContext);
 120   size_t count = 0;
 121
 122   while (count < aNumFrames) {
 123     uint32_t pc = state[R_PC], sp = state[R_SP];
 124
 125     // ARM instructions are always aligned to 2 or 4 bytes.
 126     // The last bit of the pc / lr indicates ARM or Thumb mode.
 127     // We're only interested in the instruction address, so we mask off that
 128     // bit.
 129     constexpr uint32_t instrAddrMask = ~1;
 130     uint32_t instrAddress = pc & instrAddrMask;
 131
 132     aPCs[count] = reinterpret_cast<void*>(instrAddress);
 133     aSPs[count] = reinterpret_cast<void*>(sp);
 134     count++;
 135
 136     if (!space) break;
 137     // TODO: cache these lookups.  Binary-searching libxul is
 138     // expensive (possibly more expensive than doing the actual
 139     // unwind), and even a small cache should help.
 140     const EHTable* table = space->lookup(pc);
 141     if (!table) break;
 142     const EHEntry* entry = table->lookup(pc);
 143     if (!entry) break;
 144     if (!state.unwind(entry, stackBase)) break;
 145   }
 146
 147   return count;
 148 }
 149
 150 class EHInterp {
 151  public:
 152   // Note that stackLimit is exclusive and stackBase is inclusive
 153   // (i.e, stackLimit < SP <= stackBase), following the convention
 154   // set by the AAPCS spec.
 155   EHInterp(EHState& aState, const EHEntry* aEntry, uint32_t aStackLimit,
 156            uint32_t aStackBase)
 157       : mState(aState),
 158         mStackLimit(aStackLimit),
 159         mStackBase(aStackBase),
 160         mNextWord(0),
 161         mWordsLeft(0),
 162         mFailed(false) {
 163     const PRel31& exidx = aEntry->exidx;
 164     uint32_t firstWord;
 165
 166     if (exidx.mBits == 1) {  // EXIDX_CANTUNWIND
 167       mFailed = true;
 168       return;
 169     }
 170     if (exidx.topBit()) {
 171       firstWord = exidx.mBits;
 172     } else {
 173       mNextWord = reinterpret_cast<const uint32_t*>(exidx.compute());
 174       firstWord = *mNextWord++;
 175     }
 176
 177     switch (firstWord >> 24) {
 178       case 0x80:  // short
 179         mWord = firstWord << 8;
 180         mBytesLeft = 3;
 181         break;
 182       case 0x81:
 183       case 0x82:  // long; catch descriptor size ignored
 184         mWord = firstWord << 16;
 185         mBytesLeft = 2;
 186         mWordsLeft = (firstWord >> 16) & 0xff;
 187         break;
 188       default:
 189         // unknown personality
 190         mFailed = true;
 191     }
 192   }
 193
 194   bool unwind();
 195
 196  private:
 197   // TODO: GCC has been observed not CSEing repeated reads of
 198   // mState[R_SP] with writes to mFailed between them, suggesting that
 199   // it hasn't determined that they can't alias and is thus missing
 200   // optimization opportunities.  So, we may want to flatten EHState
 201   // into this class; this may also make the code simpler.
 202   EHState& mState;
 203   uint32_t mStackLimit;
 204   uint32_t mStackBase;
 205   const uint32_t* mNextWord;
 206   uint32_t mWord;
 207   uint8_t mWordsLeft;
 208   uint8_t mBytesLeft;
 209   bool mFailed;
 210
 211   enum {
 212     I_ADDSP = 0x00,  // 0sxxxxxx (subtract if s)
 213     M_ADDSP = 0x80,
 214     I_POPMASK = 0x80,  // 1000iiii iiiiiiii (if any i set)
 215     M_POPMASK = 0xf0,
 216     I_MOVSP = 0x90,  // 1001nnnn
 217     M_MOVSP = 0xf0,
 218     I_POPN = 0xa0,  // 1010lnnn
 219     M_POPN = 0xf0,
 220     I_FINISH = 0xb0,    // 10110000
 221     I_POPLO = 0xb1,     // 10110001 0000iiii (if any i set)
 222     I_ADDSPBIG = 0xb2,  // 10110010 uleb128
 223     I_POPFDX = 0xb3,    // 10110011 sssscccc
 224     I_POPFDX8 = 0xb8,   // 10111nnn
 225     M_POPFDX8 = 0xf8,
 226     // "Intel Wireless MMX" extensions omitted.
 227     I_POPFDD = 0xc8,  // 1100100h sssscccc
 228     M_POPFDD = 0xfe,
 229     I_POPFDD8 = 0xd0,  // 11010nnn
 230     M_POPFDD8 = 0xf8
 231   };
 232
 233   uint8_t next() {
 234     if (mBytesLeft == 0) {
 235       if (mWordsLeft == 0) {
 236         return I_FINISH;
 237       }
 238       mWordsLeft--;
 239       mWord = *mNextWord++;
 240       mBytesLeft = 4;
 241     }
 242     mBytesLeft--;
 243     mWord = (mWord << 8) | (mWord >> 24);  // rotate
 244     return mWord;
 245   }
 246
 247   uint32_t& vSP() { return mState[R_SP]; }
 248   uint32_t* ptrSP() { return reinterpret_cast<uint32_t*>(vSP()); }
 249
 250   void checkStackBase() {
 251     if (vSP() > mStackBase) mFailed = true;
 252   }
 253   void checkStackLimit() {
 254     if (vSP() <= mStackLimit) mFailed = true;
 255   }
 256   void checkStackAlign() {
 257     if ((vSP() & 3) != 0) mFailed = true;
 258   }
 259   void checkStack() {
 260     checkStackBase();
 261     checkStackLimit();
 262     checkStackAlign();
 263   }
 264
 265   void popRange(uint8_t first, uint8_t last, uint16_t mask) {
 266     bool hasSP = false;
 267     uint32_t tmpSP;
 268     if (mask == 0) mFailed = true;
 269     for (uint8_t r = first; r <= last; ++r) {
 270       if (mask & 1) {
 271         if (r == R_SP) {
 272           hasSP = true;
 273           tmpSP = *ptrSP();
 274         } else
 275           mState[r] = *ptrSP();
 276         vSP() += 4;
 277         checkStackBase();
 278         if (mFailed) return;
 279       }
 280       mask >>= 1;
 281     }
 282     if (hasSP) {
 283       vSP() = tmpSP;
 284       checkStack();
 285     }
 286   }
 287 };
 288
 289 bool EHState::unwind(const EHEntry* aEntry, const void* stackBasePtr) {
 290   // The unwinding program cannot set SP to less than the initial value.
 291   uint32_t stackLimit = mRegs[R_SP] - 4;
 292   uint32_t stackBase = reinterpret_cast<uint32_t>(stackBasePtr);
 293   EHInterp interp(*this, aEntry, stackLimit, stackBase);
 294   return interp.unwind();
 295 }
 296
 297 bool EHInterp::unwind() {
 298   mState[R_PC] = 0;
 299   checkStack();
 300   while (!mFailed) {
 301     uint8_t insn = next();
 302 #if DEBUG_EHABI_UNWIND
 303     LOG("unwind insn = %02x", (unsigned)insn);
 304 #endif
 305     // Try to put the common cases first.
 306
 307     // 00xxxxxx: vsp = vsp + (xxxxxx << 2) + 4
 308     // 01xxxxxx: vsp = vsp - (xxxxxx << 2) - 4
 309     if ((insn & M_ADDSP) == I_ADDSP) {
 310       uint32_t offset = ((insn & 0x3f) << 2) + 4;
 311       if (insn & 0x40) {
 312         vSP() -= offset;
 313         checkStackLimit();
 314       } else {
 315         vSP() += offset;
 316         checkStackBase();
 317       }
 318       continue;
 319     }
 320
 321     // 10100nnn: Pop r4-r[4+nnn]
 322     // 10101nnn: Pop r4-r[4+nnn], r14
 323     if ((insn & M_POPN) == I_POPN) {
 324       uint8_t n = (insn & 0x07) + 1;
 325       bool lr = insn & 0x08;
 326       uint32_t* ptr = ptrSP();
 327       vSP() += (n + (lr ? 1 : 0)) * 4;
 328       checkStackBase();
 329       for (uint8_t r = 4; r < 4 + n; ++r) mState[r] = *ptr++;
 330       if (lr) mState[R_LR] = *ptr++;
 331       continue;
 332     }
 333
 334     // 1011000: Finish
 335     if (insn == I_FINISH) {
 336       if (mState[R_PC] == 0) {
 337         mState[R_PC] = mState[R_LR];
 338         // Non-standard change (bug 916106): Prevent the caller from
 339         // re-using LR.  Since the caller is by definition not a leaf
 340         // routine, it will have to restore LR from somewhere to
 341         // return to its own caller, so we can safely zero it here.
 342         // This makes a difference only if an error in unwinding
 343         // (e.g., caused by starting from within a prologue/epilogue)
 344         // causes us to load a pointer to a leaf routine as LR; if we
 345         // don't do something, we'll go into an infinite loop of
 346         // "returning" to that same function.
 347         mState[R_LR] = 0;
 348       }
 349       return true;
 350     }
 351
 352     // 1001nnnn: Set vsp = r[nnnn]
 353     if ((insn & M_MOVSP) == I_MOVSP) {
 354       vSP() = mState[insn & 0x0f];
 355       checkStack();
 356       continue;
 357     }
 358
 359     // 11001000 sssscccc: Pop VFP regs D[16+ssss]-D[16+ssss+cccc] (as FLDMFDD)
 360     // 11001001 sssscccc: Pop VFP regs D[ssss]-D[ssss+cccc] (as FLDMFDD)
 361     if ((insn & M_POPFDD) == I_POPFDD) {
 362       uint8_t n = (next() & 0x0f) + 1;
 363       // Note: if the 16+ssss+cccc > 31, the encoding is reserved.
 364       // As the space is currently unused, we don't try to check.
 365       vSP() += 8 * n;
 366       checkStackBase();
 367       continue;
 368     }
 369
 370     // 11010nnn: Pop VFP regs D[8]-D[8+nnn] (as FLDMFDD)
 371     if ((insn & M_POPFDD8) == I_POPFDD8) {
 372       uint8_t n = (insn & 0x07) + 1;
 373       vSP() += 8 * n;
 374       checkStackBase();
 375       continue;
 376     }
 377
 378     // 10110010 uleb128: vsp = vsp + 0x204 + (uleb128 << 2)
 379     if (insn == I_ADDSPBIG) {
 380       uint32_t acc = 0;
 381       uint8_t shift = 0;
 382       uint8_t byte;
 383       do {
 384         if (shift >= 32) return false;
 385         byte = next();
 386         acc |= (byte & 0x7f) << shift;
 387         shift += 7;
 388       } while (byte & 0x80);
 389       uint32_t offset = 0x204 + (acc << 2);
 390       // The calculations above could have overflowed.
 391       // But the one we care about is this:
 392       if (vSP() + offset < vSP()) mFailed = true;
 393       vSP() += offset;
 394       // ...so that this is the only other check needed:
 395       checkStackBase();
 396       continue;
 397     }
 398
 399     // 1000iiii iiiiiiii (i not all 0): Pop under masks {r15-r12}, {r11-r4}
 400     if ((insn & M_POPMASK) == I_POPMASK) {
 401       popRange(4, 15, ((insn & 0x0f) << 8) | next());
 402       continue;
 403     }
 404
 405     // 1011001 0000iiii (i not all 0): Pop under mask {r3-r0}
 406     if (insn == I_POPLO) {
 407       popRange(0, 3, next() & 0x0f);
 408       continue;
 409     }
 410
 411     // 10110011 sssscccc: Pop VFP regs D[ssss]-D[ssss+cccc] (as FLDMFDX)
 412     if (insn == I_POPFDX) {
 413       uint8_t n = (next() & 0x0f) + 1;
 414       vSP() += 8 * n + 4;
 415       checkStackBase();
 416       continue;
 417     }
 418
 419     // 10111nnn: Pop VFP regs D[8]-D[8+nnn] (as FLDMFDX)
 420     if ((insn & M_POPFDX8) == I_POPFDX8) {
 421       uint8_t n = (insn & 0x07) + 1;
 422       vSP() += 8 * n + 4;
 423       checkStackBase();
 424       continue;
 425     }
 426
 427     // unhandled instruction
 428 #ifdef DEBUG_EHABI_UNWIND
 429     LOG("Unhandled EHABI instruction 0x%02x", insn);
 430 #endif
 431     mFailed = true;
 432   }
 433   return false;
 434 }
 435
 436 bool operator<(const EHTable& lhs, const EHTable& rhs) {
 437   return lhs.startPC() < rhs.startPC();
 438 }
 439
 440 // Async signal unsafe.
 441 EHAddrSpace::EHAddrSpace(const std::vector<EHTable>& aTables)
 442     : mTables(aTables) {
 443   std::sort(mTables.begin(), mTables.end());
 444   DebugOnly<uint32_t> lastEnd = 0;
 445   for (std::vector<EHTable>::iterator i = mTables.begin(); i != mTables.end();
 446        ++i) {
 447     MOZ_ASSERT(i->startPC() >= lastEnd);
 448     mStarts.push_back(i->startPC());
 449     lastEnd = i->endPC();
 450   }
 451 }
 452
 453 const EHTable* EHAddrSpace::lookup(uint32_t aPC) const {
 454   ptrdiff_t i = (std::upper_bound(mStarts.begin(), mStarts.end(), aPC) -
 455                  mStarts.begin()) -
 456                 1;
 457
 458   if (i < 0 || aPC >= mTables[i].endPC()) return 0;
 459   return &mTables[i];
 460 }
 461
 462 const EHEntry* EHTable::lookup(uint32_t aPC) const {
 463   MOZ_ASSERT(aPC >= mStartPC);
 464   if (aPC >= mEndPC) return nullptr;
 465
 466   const EHEntry* begin = mEntriesBegin;
 467   const EHEntry* end = mEntriesEnd;
 468   MOZ_ASSERT(begin < end);
 469   if (aPC < reinterpret_cast<uint32_t>(begin->startPC.compute()))
 470     return nullptr;
 471
 472   while (end - begin > 1) {
 473 #ifdef EHABI_UNWIND_MORE_ASSERTS
 474     if ((end - 1)->startPC.compute() < begin->startPC.compute()) {
 475       MOZ_CRASH("unsorted exidx");
 476     }
 477 #endif
 478     const EHEntry* mid = begin + (end - begin) / 2;
 479     if (aPC < reinterpret_cast<uint32_t>(mid->startPC.compute()))
 480       end = mid;
 481     else
 482       begin = mid;
 483   }
 484   return begin;
 485 }
 486
 487 #if MOZ_LITTLE_ENDIAN()
 488 static const unsigned char hostEndian = ELFDATA2LSB;
 489 #elif MOZ_BIG_ENDIAN()
 490 static const unsigned char hostEndian = ELFDATA2MSB;
 491 #else
 492 #  error "No endian?"
 493 #endif
 494
 495 // Async signal unsafe: std::vector::reserve, std::string copy ctor.
 496 EHTable::EHTable(const void* aELF, size_t aSize, const std::string& aName)
 497     : mStartPC(~0),  // largest uint32_t
 498       mEndPC(0),
 499       mEntriesBegin(nullptr),
 500       mEntriesEnd(nullptr),
 501       mName(aName) {
 502   const uint32_t fileHeaderAddr = reinterpret_cast<uint32_t>(aELF);
 503
 504   if (aSize < sizeof(Elf32_Ehdr)) return;
 505
 506   const Elf32_Ehdr& file = *(reinterpret_cast<Elf32_Ehdr*>(fileHeaderAddr));
 507   if (memcmp(&file.e_ident[EI_MAG0], ELFMAG, SELFMAG) != 0 ||
 508       file.e_ident[EI_CLASS] != ELFCLASS32 ||
 509       file.e_ident[EI_DATA] != hostEndian ||
 510       file.e_ident[EI_VERSION] != EV_CURRENT || file.e_machine != EM_ARM ||
 511       file.e_version != EV_CURRENT)
 512     // e_flags?
 513     return;
 514
 515   MOZ_ASSERT(file.e_phoff + file.e_phnum * file.e_phentsize <= aSize);
 516   const Elf32_Phdr *exidxHdr = 0, *zeroHdr = 0;
 517   for (unsigned i = 0; i < file.e_phnum; ++i) {
 518     const Elf32_Phdr& phdr = *(reinterpret_cast<Elf32_Phdr*>(
 519         fileHeaderAddr + file.e_phoff + i * file.e_phentsize));
 520     if (phdr.p_type == PT_ARM_EXIDX) {
 521       exidxHdr = &phdr;
 522     } else if (phdr.p_type == PT_LOAD) {
 523       if (phdr.p_offset == 0) {
 524         zeroHdr = &phdr;
 525       }
 526       if (phdr.p_flags & PF_X) {
 527         mStartPC = std::min(mStartPC, phdr.p_vaddr);
 528         mEndPC = std::max(mEndPC, phdr.p_vaddr + phdr.p_memsz);
 529       }
 530     }
 531   }
 532   if (!exidxHdr) return;
 533   if (!zeroHdr) return;
 534   mBaseAddress = fileHeaderAddr - zeroHdr->p_vaddr;
 535   mStartPC += mBaseAddress;
 536   mEndPC += mBaseAddress;
 537   mEntriesBegin =
 538       reinterpret_cast<const EHEntry*>(mBaseAddress + exidxHdr->p_vaddr);
 539   mEntriesEnd = reinterpret_cast<const EHEntry*>(
 540       mBaseAddress + exidxHdr->p_vaddr + exidxHdr->p_memsz);
 541 }
 542
 543 mozilla::Atomic<const EHAddrSpace*> EHAddrSpace::sCurrent(nullptr);
 544
 545 // Async signal safe; can fail if Update() hasn't returned yet.
 546 const EHAddrSpace* EHAddrSpace::Get() { return sCurrent; }
 547
 548 // Collect unwinding information from loaded objects.  Calls after the
 549 // first have no effect.  Async signal unsafe.
 550 void EHAddrSpace::Update() {
 551   const EHAddrSpace* space = sCurrent;
 552   if (space) return;
 553
 554   SharedLibraryInfo info = SharedLibraryInfo::GetInfoForSelf();
 555   std::vector<EHTable> tables;
 556
 557   for (size_t i = 0; i < info.GetSize(); ++i) {
 558     const SharedLibrary& lib = info.GetEntry(i);
 559     // FIXME: This isn't correct if the start address isn't p_offset 0, because
 560     // the start address will not point at the file header. But this is worked
 561     // around by magic number checks in the EHTable constructor.
 562     EHTable tab(reinterpret_cast<const void*>(lib.GetStart()),
 563                 lib.GetEnd() - lib.GetStart(), lib.GetDebugPath());
 564     if (tab.isValid()) tables.push_back(tab);
 565   }
 566   space = new EHAddrSpace(tables);
 567
 568   if (!sCurrent.compareExchange(nullptr, space)) {
 569     delete space;
 570     space = sCurrent;
 571   }
 572 }
 573
 574 EHState::EHState(const mcontext_t& context) {
 575 #ifdef linux
 576   mRegs[0] = context.arm_r0;
 577   mRegs[1] = context.arm_r1;
 578   mRegs[2] = context.arm_r2;
 579   mRegs[3] = context.arm_r3;
 580   mRegs[4] = context.arm_r4;
 581   mRegs[5] = context.arm_r5;
 582   mRegs[6] = context.arm_r6;
 583   mRegs[7] = context.arm_r7;
 584   mRegs[8] = context.arm_r8;
 585   mRegs[9] = context.arm_r9;
 586   mRegs[10] = context.arm_r10;
 587   mRegs[11] = context.arm_fp;
 588   mRegs[12] = context.arm_ip;
 589   mRegs[13] = context.arm_sp;
 590   mRegs[14] = context.arm_lr;
 591   mRegs[15] = context.arm_pc;
 592 #else
 593 #  error "Unhandled OS for ARM EHABI unwinding"
 594 #endif
 595 }
 596
 597 }  // namespace mozilla