[ tor-browser ].git.dasho

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