michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "LulMain.h"
michael@0: 
michael@0: #include <string.h>
michael@0: #include <stdlib.h>
michael@0: #include <stdio.h>
michael@0: 
michael@0: #include <algorithm>  // std::sort
michael@0: #include <string>
michael@0: 
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/ArrayUtils.h"
michael@0: #include "mozilla/MemoryChecking.h"
michael@0: 
michael@0: #include "LulCommonExt.h"
michael@0: #include "LulElfExt.h"
michael@0: 
michael@0: #include "LulMainInt.h"
michael@0: 
michael@0: // Set this to 1 for verbose logging
michael@0: #define DEBUG_MAIN 0
michael@0: 
michael@0: 
michael@0: namespace lul {
michael@0: 
michael@0: using std::string;
michael@0: using std::vector;
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // AutoLulRWLocker                                            //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // This is a simple RAII class that manages acquisition and release of
michael@0: // LulRWLock reader-writer locks.
michael@0: 
michael@0: class AutoLulRWLocker {
michael@0: public:
michael@0:   enum AcqMode { FOR_READING, FOR_WRITING };
michael@0:   AutoLulRWLocker(LulRWLock* aRWLock, AcqMode mode)
michael@0:     : mRWLock(aRWLock)
michael@0:   {
michael@0:     if (mode == FOR_WRITING) {
michael@0:       aRWLock->WrLock();
michael@0:     } else {
michael@0:       aRWLock->RdLock();
michael@0:     }
michael@0:   }
michael@0:   ~AutoLulRWLocker()
michael@0:   {
michael@0:     mRWLock->Unlock();
michael@0:   }
michael@0: 
michael@0: private:
michael@0:   LulRWLock* mRWLock;
michael@0: };
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // RuleSet                                                    //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static const char* 
michael@0: NameOf_DW_REG(int16_t aReg)
michael@0: {
michael@0:   switch (aReg) {
michael@0:     case DW_REG_CFA:       return "cfa";
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:     case DW_REG_INTEL_XBP: return "xbp";
michael@0:     case DW_REG_INTEL_XSP: return "xsp";
michael@0:     case DW_REG_INTEL_XIP: return "xip";
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:     case DW_REG_ARM_R7:    return "r7";
michael@0:     case DW_REG_ARM_R11:   return "r11";
michael@0:     case DW_REG_ARM_R12:   return "r12";
michael@0:     case DW_REG_ARM_R13:   return "r13";
michael@0:     case DW_REG_ARM_R14:   return "r14";
michael@0:     case DW_REG_ARM_R15:   return "r15";
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0:     default: return "???";
michael@0:   }
michael@0: }
michael@0: 
michael@0: static string
michael@0: ShowRule(const char* aNewReg, LExpr aExpr)
michael@0: {
michael@0:   char buf[64];
michael@0:   string res = string(aNewReg) + "=";
michael@0:   switch (aExpr.mHow) {
michael@0:     case LExpr::UNKNOWN:
michael@0:       res += "Unknown";
michael@0:       break;
michael@0:     case LExpr::NODEREF:
michael@0:       sprintf(buf, "%s+%d", NameOf_DW_REG(aExpr.mReg), (int)aExpr.mOffset);
michael@0:       res += buf;
michael@0:       break;
michael@0:     case LExpr::DEREF:
michael@0:       sprintf(buf, "*(%s+%d)", NameOf_DW_REG(aExpr.mReg), (int)aExpr.mOffset);
michael@0:       res += buf;
michael@0:       break;
michael@0:     default:
michael@0:       res += "???";
michael@0:       break;
michael@0:   }
michael@0:   return res;
michael@0: }
michael@0: 
michael@0: void
michael@0: RuleSet::Print(void(*aLog)(const char*))
michael@0: {
michael@0:   char buf[96];
michael@0:   sprintf(buf, "[%llx .. %llx]: let ",
michael@0:           (unsigned long long int)mAddr,
michael@0:           (unsigned long long int)(mAddr + mLen - 1));
michael@0:   string res = string(buf);
michael@0:   res += ShowRule("cfa", mCfaExpr);
michael@0:   res += " in";
michael@0:   // For each reg we care about, print the recovery expression.
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:   res += ShowRule(" RA", mXipExpr);
michael@0:   res += ShowRule(" SP", mXspExpr);
michael@0:   res += ShowRule(" BP", mXbpExpr);
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:   res += ShowRule(" R15", mR15expr);
michael@0:   res += ShowRule(" R7",  mR7expr);
michael@0:   res += ShowRule(" R11", mR11expr);
michael@0:   res += ShowRule(" R12", mR12expr);
michael@0:   res += ShowRule(" R13", mR13expr);
michael@0:   res += ShowRule(" R14", mR14expr);
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0:   aLog(res.c_str());
michael@0: }
michael@0: 
michael@0: LExpr*
michael@0: RuleSet::ExprForRegno(DW_REG_NUMBER aRegno) {
michael@0:   switch (aRegno) {
michael@0:     case DW_REG_CFA: return &mCfaExpr;
michael@0: #   if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:     case DW_REG_INTEL_XIP: return &mXipExpr;
michael@0:     case DW_REG_INTEL_XSP: return &mXspExpr;
michael@0:     case DW_REG_INTEL_XBP: return &mXbpExpr;
michael@0: #   elif defined(LUL_ARCH_arm)
michael@0:     case DW_REG_ARM_R15:   return &mR15expr;
michael@0:     case DW_REG_ARM_R14:   return &mR14expr;
michael@0:     case DW_REG_ARM_R13:   return &mR13expr;
michael@0:     case DW_REG_ARM_R12:   return &mR12expr;
michael@0:     case DW_REG_ARM_R11:   return &mR11expr;
michael@0:     case DW_REG_ARM_R7:    return &mR7expr;
michael@0: #   else
michael@0: #     error "Unknown arch"
michael@0: #   endif
michael@0:     default: return nullptr;
michael@0:   }
michael@0: }
michael@0: 
michael@0: RuleSet::RuleSet()
michael@0: {
michael@0:   mAddr = 0;
michael@0:   mLen  = 0;
michael@0:   // The only other fields are of type LExpr and those are initialised
michael@0:   // by LExpr::LExpr().
michael@0: }
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // SecMap                                                     //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // See header file LulMainInt.h for comments about invariants.
michael@0: 
michael@0: SecMap::SecMap(void(*aLog)(const char*))
michael@0:   : mSummaryMinAddr(1)
michael@0:   , mSummaryMaxAddr(0)
michael@0:   , mUsable(true)
michael@0:   , mLog(aLog)
michael@0: {}
michael@0: 
michael@0: SecMap::~SecMap() {
michael@0:   mRuleSets.clear();
michael@0: }
michael@0: 
michael@0: RuleSet*
michael@0: SecMap::FindRuleSet(uintptr_t ia) {
michael@0:   // Binary search mRuleSets to find one that brackets |ia|.
michael@0:   // lo and hi need to be signed, else the loop termination tests
michael@0:   // don't work properly.  Note that this works correctly even when
michael@0:   // mRuleSets.size() == 0.
michael@0: 
michael@0:   // Can't do this until the array has been sorted and preened.
michael@0:   MOZ_ASSERT(mUsable);
michael@0: 
michael@0:   long int lo = 0;
michael@0:   long int hi = (long int)mRuleSets.size() - 1;
michael@0:   while (true) {
michael@0:     // current unsearched space is from lo to hi, inclusive.
michael@0:     if (lo > hi) {
michael@0:       // not found
michael@0:       return nullptr;
michael@0:     }
michael@0:     long int  mid         = lo + ((hi - lo) / 2);
michael@0:     RuleSet*  mid_ruleSet = &mRuleSets[mid];
michael@0:     uintptr_t mid_minAddr = mid_ruleSet->mAddr;
michael@0:     uintptr_t mid_maxAddr = mid_minAddr + mid_ruleSet->mLen - 1;
michael@0:     if (ia < mid_minAddr) { hi = mid-1; continue; }
michael@0:     if (ia > mid_maxAddr) { lo = mid+1; continue; }
michael@0:     MOZ_ASSERT(mid_minAddr <= ia && ia <= mid_maxAddr);
michael@0:     return mid_ruleSet;
michael@0:   }
michael@0:   // NOTREACHED
michael@0: }
michael@0: 
michael@0: // Add a RuleSet to the collection.  The rule is copied in.  Calling
michael@0: // this makes the map non-searchable.
michael@0: void
michael@0: SecMap::AddRuleSet(RuleSet* rs) {
michael@0:   mUsable = false;
michael@0:   mRuleSets.push_back(*rs);
michael@0: }
michael@0: 
michael@0: 
michael@0: static bool
michael@0: CmpRuleSetsByAddrLE(const RuleSet& rs1, const RuleSet& rs2) {
michael@0:   return rs1.mAddr < rs2.mAddr;
michael@0: }
michael@0: 
michael@0: // Prepare the map for searching.  Completely remove any which don't
michael@0: // fall inside the specified range [start, +len).
michael@0: void
michael@0: SecMap::PrepareRuleSets(uintptr_t aStart, size_t aLen)
michael@0: {
michael@0:   if (mRuleSets.empty()) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   MOZ_ASSERT(aLen > 0);
michael@0:   if (aLen == 0) {
michael@0:     // This should never happen.
michael@0:     mRuleSets.clear();
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   // Sort by start addresses.
michael@0:   std::sort(mRuleSets.begin(), mRuleSets.end(), CmpRuleSetsByAddrLE);
michael@0: 
michael@0:   // Detect any entry not completely contained within [start, +len).
michael@0:   // Set its length to zero, so that the next pass will remove it.
michael@0:   for (size_t i = 0; i < mRuleSets.size(); ++i) {
michael@0:     RuleSet* rs = &mRuleSets[i];
michael@0:     if (rs->mLen > 0 &&
michael@0:         (rs->mAddr < aStart || rs->mAddr + rs->mLen > aStart + aLen)) {
michael@0:       rs->mLen = 0;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Iteratively truncate any overlaps and remove any zero length
michael@0:   // entries that might result, or that may have been present
michael@0:   // initially.  Unless the input is seriously screwy, this is
michael@0:   // expected to iterate only once.
michael@0:   while (true) {
michael@0:     size_t i;
michael@0:     size_t n = mRuleSets.size();
michael@0:     size_t nZeroLen = 0;
michael@0: 
michael@0:     if (n == 0) {
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     for (i = 1; i < n; ++i) {
michael@0:       RuleSet* prev = &mRuleSets[i-1];
michael@0:       RuleSet* here = &mRuleSets[i];
michael@0:       MOZ_ASSERT(prev->mAddr <= here->mAddr);
michael@0:       if (prev->mAddr + prev->mLen > here->mAddr) {
michael@0:         prev->mLen = here->mAddr - prev->mAddr;
michael@0:       }
michael@0:       if (prev->mLen == 0)
michael@0:         nZeroLen++;
michael@0:     }
michael@0: 
michael@0:     if (mRuleSets[n-1].mLen == 0) {
michael@0:       nZeroLen++;
michael@0:     }
michael@0: 
michael@0:     // At this point, the entries are in-order and non-overlapping.
michael@0:     // If none of them are zero-length, we are done.
michael@0:     if (nZeroLen == 0) {
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     // Slide back the entries to remove the zero length ones.
michael@0:     size_t j = 0;  // The write-point.
michael@0:     for (i = 0; i < n; ++i) {
michael@0:       if (mRuleSets[i].mLen == 0) {
michael@0:         continue;
michael@0:       }
michael@0:       if (j != i) mRuleSets[j] = mRuleSets[i];
michael@0:       ++j;
michael@0:     }
michael@0:     MOZ_ASSERT(i == n);
michael@0:     MOZ_ASSERT(nZeroLen <= n);
michael@0:     MOZ_ASSERT(j == n - nZeroLen);
michael@0:     while (nZeroLen > 0) {
michael@0:       mRuleSets.pop_back();
michael@0:       nZeroLen--;
michael@0:     }
michael@0: 
michael@0:     MOZ_ASSERT(mRuleSets.size() == j);
michael@0:   }
michael@0: 
michael@0:   size_t n = mRuleSets.size();
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   // Do a final check on the rules: their address ranges must be
michael@0:   // ascending, non overlapping, non zero sized.
michael@0:   if (n > 0) {
michael@0:     MOZ_ASSERT(mRuleSets[0].mLen > 0);
michael@0:     for (size_t i = 1; i < n; ++i) {
michael@0:       RuleSet* prev = &mRuleSets[i-1];
michael@0:       RuleSet* here = &mRuleSets[i];
michael@0:       MOZ_ASSERT(prev->mAddr < here->mAddr);
michael@0:       MOZ_ASSERT(here->mLen > 0);
michael@0:       MOZ_ASSERT(prev->mAddr + prev->mLen <= here->mAddr);
michael@0:     }
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   // Set the summary min and max address values.
michael@0:   if (n == 0) {
michael@0:     // Use the values defined in comments in the class declaration.
michael@0:     mSummaryMinAddr = 1;
michael@0:     mSummaryMaxAddr = 0;
michael@0:   } else {
michael@0:     mSummaryMinAddr = mRuleSets[0].mAddr;
michael@0:     mSummaryMaxAddr = mRuleSets[n-1].mAddr + mRuleSets[n-1].mLen - 1;
michael@0:   }
michael@0:   char buf[150];
michael@0:   snprintf(buf, sizeof(buf),
michael@0:            "PrepareRuleSets: %d entries, smin/smax 0x%llx, 0x%llx\n",
michael@0:            (int)n, (unsigned long long int)mSummaryMinAddr,
michael@0:                    (unsigned long long int)mSummaryMaxAddr);
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   mLog(buf);
michael@0: 
michael@0:   // Is now usable for binary search.
michael@0:   mUsable = true;
michael@0: 
michael@0:   if (0) {
michael@0:     mLog("\nRulesets after preening\n");
michael@0:     for (size_t i = 0; i < mRuleSets.size(); ++i) {
michael@0:       mRuleSets[i].Print(mLog);
michael@0:       mLog("\n");
michael@0:     }
michael@0:     mLog("\n");
michael@0:   }
michael@0: }
michael@0: 
michael@0: bool SecMap::IsEmpty() {
michael@0:   return mRuleSets.empty();
michael@0: }
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // SegArray                                                   //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // A SegArray holds a set of address ranges that together exactly
michael@0: // cover an address range, with no overlaps or holes.  Each range has
michael@0: // an associated value, which in this case has been specialised to be
michael@0: // a simple boolean.  The representation is kept to minimal canonical
michael@0: // form in which adjacent ranges with the same associated value are
michael@0: // merged together.  Each range is represented by a |struct Seg|.
michael@0: //
michael@0: // SegArrays are used to keep track of which parts of the address
michael@0: // space are known to contain instructions.
michael@0: class SegArray {
michael@0: 
michael@0:  public:
michael@0:   void add(uintptr_t lo, uintptr_t hi, bool val) {
michael@0:     if (lo > hi) {
michael@0:       return;
michael@0:     }
michael@0:     split_at(lo);
michael@0:     if (hi < UINTPTR_MAX) {
michael@0:       split_at(hi+1);
michael@0:     }
michael@0:     std::vector<Seg>::size_type iLo, iHi, i;
michael@0:     iLo = find(lo);
michael@0:     iHi = find(hi);
michael@0:     for (i = iLo; i <= iHi; ++i) {
michael@0:       mSegs[i].val = val;
michael@0:     }
michael@0:     preen();
michael@0:   }
michael@0: 
michael@0:   bool getBoundingCodeSegment(/*OUT*/uintptr_t* rx_min,
michael@0:                               /*OUT*/uintptr_t* rx_max, uintptr_t addr) {
michael@0:     std::vector<Seg>::size_type i = find(addr);
michael@0:     if (!mSegs[i].val) {
michael@0:       return false;
michael@0:     }
michael@0:     *rx_min = mSegs[i].lo;
michael@0:     *rx_max = mSegs[i].hi;
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   SegArray() {
michael@0:     Seg s(0, UINTPTR_MAX, false);
michael@0:     mSegs.push_back(s);
michael@0:   }
michael@0: 
michael@0:  private:
michael@0:   struct Seg {
michael@0:     Seg(uintptr_t lo, uintptr_t hi, bool val) : lo(lo), hi(hi), val(val) {}
michael@0:     uintptr_t lo;
michael@0:     uintptr_t hi;
michael@0:     bool val;
michael@0:   };
michael@0: 
michael@0:   void preen() {
michael@0:     for (std::vector<Seg>::iterator iter = mSegs.begin();
michael@0:          iter < mSegs.end()-1;
michael@0:          ++iter) {
michael@0:       if (iter[0].val != iter[1].val) {
michael@0:         continue;
michael@0:       }
michael@0:       iter[0].hi = iter[1].hi;
michael@0:       mSegs.erase(iter+1);
michael@0:       // Back up one, so as not to miss an opportunity to merge
michael@0:       // with the entry after this one.
michael@0:       --iter;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   std::vector<Seg>::size_type find(uintptr_t a) {
michael@0:     long int lo = 0;
michael@0:     long int hi = (long int)mSegs.size();
michael@0:     while (true) {
michael@0:       // The unsearched space is lo .. hi inclusive.
michael@0:       if (lo > hi) {
michael@0:         // Not found.  This can't happen.
michael@0:         return (std::vector<Seg>::size_type)(-1);
michael@0:       }
michael@0:       long int  mid    = lo + ((hi - lo) / 2);
michael@0:       uintptr_t mid_lo = mSegs[mid].lo;
michael@0:       uintptr_t mid_hi = mSegs[mid].hi;
michael@0:       if (a < mid_lo) { hi = mid-1; continue; }
michael@0:       if (a > mid_hi) { lo = mid+1; continue; }
michael@0:       return (std::vector<Seg>::size_type)mid;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void split_at(uintptr_t a) {
michael@0:     std::vector<Seg>::size_type i = find(a);
michael@0:     if (mSegs[i].lo == a) {
michael@0:       return;
michael@0:     }
michael@0:     mSegs.insert( mSegs.begin()+i+1, mSegs[i] );
michael@0:     mSegs[i].hi = a-1;
michael@0:     mSegs[i+1].lo = a;
michael@0:   }
michael@0: 
michael@0:   void show() {
michael@0:     printf("<< %d entries:\n", (int)mSegs.size());
michael@0:     for (std::vector<Seg>::iterator iter = mSegs.begin();
michael@0:          iter < mSegs.end();
michael@0:          ++iter) {
michael@0:       printf("  %016llx  %016llx  %s\n",
michael@0:              (unsigned long long int)(*iter).lo,
michael@0:              (unsigned long long int)(*iter).hi,
michael@0:              (*iter).val ? "true" : "false");
michael@0:     }
michael@0:     printf(">>\n");
michael@0:   }
michael@0: 
michael@0:   std::vector<Seg> mSegs;
michael@0: };
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // PriMap                                                     //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: class PriMap {
michael@0:  public:
michael@0:   PriMap(void (*aLog)(const char*))
michael@0:     : mLog(aLog)
michael@0:   {}
michael@0: 
michael@0:   ~PriMap() {
michael@0:     for (std::vector<SecMap*>::iterator iter = mSecMaps.begin();
michael@0:          iter != mSecMaps.end();
michael@0:          ++iter) {
michael@0:       delete *iter;
michael@0:     }
michael@0:     mSecMaps.clear();
michael@0:   }
michael@0: 
michael@0:   // This can happen with the global lock held for reading.
michael@0:   RuleSet* Lookup(uintptr_t ia) {
michael@0:     SecMap* sm = FindSecMap(ia);
michael@0:     return sm ? sm->FindRuleSet(ia) : nullptr;
michael@0:   }
michael@0: 
michael@0:   // Add a secondary map.  No overlaps allowed w.r.t. existing
michael@0:   // secondary maps.  Global lock must be held for writing.
michael@0:   void AddSecMap(SecMap* aSecMap) {
michael@0:     // We can't add an empty SecMap to the PriMap.  But that's OK
michael@0:     // since we'd never be able to find anything in it anyway.
michael@0:     if (aSecMap->IsEmpty()) {
michael@0:       return;
michael@0:     }
michael@0: 
michael@0:     // Iterate through the SecMaps and find the right place for this
michael@0:     // one.  At the same time, ensure that the in-order
michael@0:     // non-overlapping invariant is preserved (and, generally, holds).
michael@0:     // FIXME: this gives a cost that is O(N^2) in the total number of
michael@0:     // shared objects in the system.  ToDo: better.
michael@0:     MOZ_ASSERT(aSecMap->mSummaryMinAddr <= aSecMap->mSummaryMaxAddr);
michael@0: 
michael@0:     size_t num_secMaps = mSecMaps.size();
michael@0:     uintptr_t i;
michael@0:     for (i = 0; i < num_secMaps; ++i) {
michael@0:       SecMap* sm_i = mSecMaps[i];
michael@0:       MOZ_ASSERT(sm_i->mSummaryMinAddr <= sm_i->mSummaryMaxAddr);
michael@0:       if (aSecMap->mSummaryMinAddr < sm_i->mSummaryMaxAddr) {
michael@0:         // |aSecMap| needs to be inserted immediately before mSecMaps[i].
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0:     MOZ_ASSERT(i <= num_secMaps);
michael@0:     if (i == num_secMaps) {
michael@0:       // It goes at the end.
michael@0:       mSecMaps.push_back(aSecMap);
michael@0:     } else {
michael@0:       std::vector<SecMap*>::iterator iter = mSecMaps.begin() + i;
michael@0:       mSecMaps.insert(iter, aSecMap);
michael@0:     }
michael@0:     char buf[100];
michael@0:     snprintf(buf, sizeof(buf), "AddSecMap: now have %d SecMaps\n",
michael@0:              (int)mSecMaps.size());
michael@0:     buf[sizeof(buf)-1] = 0;
michael@0:     mLog(buf);
michael@0:   }
michael@0: 
michael@0:   // Remove and delete any SecMaps in the mapping, that intersect
michael@0:   // with the specified address range.
michael@0:   void RemoveSecMapsInRange(uintptr_t avma_min, uintptr_t avma_max) {
michael@0:     MOZ_ASSERT(avma_min <= avma_max);
michael@0:     size_t num_secMaps = mSecMaps.size();
michael@0:     if (num_secMaps > 0) {
michael@0:       intptr_t i;
michael@0:       // Iterate from end to start over the vector, so as to ensure
michael@0:       // that the special case where |avma_min| and |avma_max| denote
michael@0:       // the entire address space, can be completed in time proportional
michael@0:       // to the number of elements in the map.
michael@0:       for (i = (intptr_t)num_secMaps-1; i >= 0; i--) {
michael@0:         SecMap* sm_i = mSecMaps[i];
michael@0:         if (sm_i->mSummaryMaxAddr < avma_min ||
michael@0:             avma_max < sm_i->mSummaryMinAddr) {
michael@0:           // There's no overlap.  Move on.
michael@0:           continue;
michael@0:         }
michael@0:         // We need to remove mSecMaps[i] and slide all those above it
michael@0:         // downwards to cover the hole.
michael@0:         mSecMaps.erase(mSecMaps.begin() + i);
michael@0:         delete sm_i;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Return the number of currently contained SecMaps.
michael@0:   size_t CountSecMaps() {
michael@0:     return mSecMaps.size();
michael@0:   }
michael@0: 
michael@0:   // Assess heuristically whether the given address is an instruction
michael@0:   // immediately following a call instruction.  The caller is required
michael@0:   // to hold the global lock for reading.
michael@0:   bool MaybeIsReturnPoint(TaggedUWord aInstrAddr, SegArray* aSegArray) {
michael@0:     if (!aInstrAddr.Valid()) {
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     uintptr_t ia = aInstrAddr.Value();
michael@0: 
michael@0:     // Assume that nobody would be crazy enough to put code in the
michael@0:     // first or last page.
michael@0:     if (ia < 4096 || ((uintptr_t)(-ia)) < 4096) {
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     // See if it falls inside a known r-x mapped area.  Poking around
michael@0:     // outside such places risks segfaulting.
michael@0:     uintptr_t insns_min, insns_max;
michael@0:     bool b = aSegArray->getBoundingCodeSegment(&insns_min, &insns_max, ia);
michael@0:     if (!b) {
michael@0:       // no code (that we know about) at this address
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     // |ia| falls within an r-x range.  So we can
michael@0:     // safely poke around in [insns_min, insns_max].
michael@0: 
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:     // Is the previous instruction recognisably a CALL?  This is
michael@0:     // common for the 32- and 64-bit versions, except for the
michael@0:     // simm32(%rip) case, which is 64-bit only.
michael@0:     //
michael@0:     // For all other cases, the 64 bit versions are either identical
michael@0:     // to the 32 bit versions, or have an optional extra leading REX.W
michael@0:     // byte (0x41).  Since the extra 0x41 is optional we have to
michael@0:     // ignore it, with the convenient result that the same matching
michael@0:     // logic works for both 32- and 64-bit cases.
michael@0: 
michael@0:     uint8_t* p = (uint8_t*)ia;
michael@0: #   if defined(LUL_ARCH_x64)
michael@0:     // CALL simm32(%rip)  == FF15 simm32
michael@0:     if (ia - 6 >= insns_min && p[-6] == 0xFF && p[-5] == 0x15) {
michael@0:       return true;
michael@0:     }
michael@0: #   endif
michael@0:     // CALL rel32  == E8 rel32  (both 32- and 64-bit)
michael@0:     if (ia - 5 >= insns_min && p[-5] == 0xE8) {
michael@0:       return true;
michael@0:     }
michael@0:     // CALL *%eax .. CALL *%edi  ==   FFD0 ..   FFD7  (32-bit)
michael@0:     // CALL *%rax .. CALL *%rdi  ==   FFD0 ..   FFD7  (64-bit)
michael@0:     // CALL *%r8  .. CALL *%r15  == 41FFD0 .. 41FFD7  (64-bit)
michael@0:     if (ia - 2 >= insns_min &&
michael@0:         p[-2] == 0xFF && p[-1] >= 0xD0 && p[-1] <= 0xD7) {
michael@0:       return true;
michael@0:     }
michael@0:     // Almost all of the remaining cases that occur in practice are
michael@0:     // of the form CALL *simm8(reg) or CALL *simm32(reg).
michael@0:     //
michael@0:     // 64 bit cases:
michael@0:     //
michael@0:     // call  *simm8(%rax)         FF50   simm8
michael@0:     // call  *simm8(%rcx)         FF51   simm8
michael@0:     // call  *simm8(%rdx)         FF52   simm8
michael@0:     // call  *simm8(%rbx)         FF53   simm8
michael@0:     // call  *simm8(%rsp)         FF5424 simm8
michael@0:     // call  *simm8(%rbp)         FF55   simm8
michael@0:     // call  *simm8(%rsi)         FF56   simm8
michael@0:     // call  *simm8(%rdi)         FF57   simm8
michael@0:     //
michael@0:     // call  *simm8(%r8)        41FF50   simm8
michael@0:     // call  *simm8(%r9)        41FF51   simm8
michael@0:     // call  *simm8(%r10)       41FF52   simm8
michael@0:     // call  *simm8(%r11)       41FF53   simm8
michael@0:     // call  *simm8(%r12)       41FF5424 simm8
michael@0:     // call  *simm8(%r13)       41FF55   simm8
michael@0:     // call  *simm8(%r14)       41FF56   simm8
michael@0:     // call  *simm8(%r15)       41FF57   simm8
michael@0:     //
michael@0:     // call  *simm32(%rax)        FF90   simm32
michael@0:     // call  *simm32(%rcx)        FF91   simm32
michael@0:     // call  *simm32(%rdx)        FF92   simm32
michael@0:     // call  *simm32(%rbx)        FF93   simm32
michael@0:     // call  *simm32(%rsp)        FF9424 simm32
michael@0:     // call  *simm32(%rbp)        FF95   simm32
michael@0:     // call  *simm32(%rsi)        FF96   simm32
michael@0:     // call  *simm32(%rdi)        FF97   simm32
michael@0:     //
michael@0:     // call  *simm32(%r8)       41FF90   simm32
michael@0:     // call  *simm32(%r9)       41FF91   simm32
michael@0:     // call  *simm32(%r10)      41FF92   simm32
michael@0:     // call  *simm32(%r11)      41FF93   simm32
michael@0:     // call  *simm32(%r12)      41FF9424 simm32
michael@0:     // call  *simm32(%r13)      41FF95   simm32
michael@0:     // call  *simm32(%r14)      41FF96   simm32
michael@0:     // call  *simm32(%r15)      41FF97   simm32
michael@0:     //
michael@0:     // 32 bit cases:
michael@0:     //
michael@0:     // call  *simm8(%eax)         FF50   simm8
michael@0:     // call  *simm8(%ecx)         FF51   simm8
michael@0:     // call  *simm8(%edx)         FF52   simm8
michael@0:     // call  *simm8(%ebx)         FF53   simm8
michael@0:     // call  *simm8(%esp)         FF5424 simm8
michael@0:     // call  *simm8(%ebp)         FF55   simm8
michael@0:     // call  *simm8(%esi)         FF56   simm8
michael@0:     // call  *simm8(%edi)         FF57   simm8
michael@0:     //
michael@0:     // call  *simm32(%eax)        FF90   simm32
michael@0:     // call  *simm32(%ecx)        FF91   simm32
michael@0:     // call  *simm32(%edx)        FF92   simm32
michael@0:     // call  *simm32(%ebx)        FF93   simm32
michael@0:     // call  *simm32(%esp)        FF9424 simm32
michael@0:     // call  *simm32(%ebp)        FF95   simm32
michael@0:     // call  *simm32(%esi)        FF96   simm32
michael@0:     // call  *simm32(%edi)        FF97   simm32
michael@0:     if (ia - 3 >= insns_min &&
michael@0:         p[-3] == 0xFF &&
michael@0:         (p[-2] >= 0x50 && p[-2] <= 0x57 && p[-2] != 0x54)) {
michael@0:       // imm8 case, not including %esp/%rsp
michael@0:       return true;
michael@0:     }
michael@0:     if (ia - 4 >= insns_min &&
michael@0:         p[-4] == 0xFF && p[-3] == 0x54 && p[-2] == 0x24) {
michael@0:       // imm8 case for %esp/%rsp
michael@0:       return true;
michael@0:     }
michael@0:     if (ia - 6 >= insns_min &&
michael@0:         p[-6] == 0xFF &&
michael@0:         (p[-5] >= 0x90 && p[-5] <= 0x97 && p[-5] != 0x94)) {
michael@0:       // imm32 case, not including %esp/%rsp
michael@0:       return true;
michael@0:     }
michael@0:     if (ia - 7 >= insns_min &&
michael@0:         p[-7] == 0xFF && p[-6] == 0x94 && p[-5] == 0x24) {
michael@0:       // imm32 case for %esp/%rsp
michael@0:       return true;
michael@0:     }
michael@0: 
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:     if (ia & 1) {
michael@0:       uint16_t w0 = 0, w1 = 0;
michael@0:       // The return address has its lowest bit set, indicating a return
michael@0:       // to Thumb code.
michael@0:       ia &= ~(uintptr_t)1;
michael@0:       if (ia - 2 >= insns_min && ia - 1 <= insns_max) {
michael@0:         w1 = *(uint16_t*)(ia - 2);
michael@0:       }
michael@0:       if (ia - 4 >= insns_min && ia - 1 <= insns_max) {
michael@0:         w0 = *(uint16_t*)(ia - 4);
michael@0:       }
michael@0:       // Is it a 32-bit Thumb call insn?
michael@0:       // BL  simm26 (Encoding T1)
michael@0:       if ((w0 & 0xF800) == 0xF000 && (w1 & 0xC000) == 0xC000) {
michael@0:         return true;
michael@0:       }
michael@0:       // BLX simm26 (Encoding T2)
michael@0:       if ((w0 & 0xF800) == 0xF000 && (w1 & 0xC000) == 0xC000) {
michael@0:         return true;
michael@0:       }
michael@0:       // Other possible cases:
michael@0:       // (BLX Rm, Encoding T1).
michael@0:       // BLX Rm (encoding T1, 16 bit, inspect w1 and ignore w0.)
michael@0:       // 0100 0111 1 Rm 000
michael@0:     } else {
michael@0:       // Returning to ARM code.
michael@0:       uint32_t a0 = 0;
michael@0:       if ((ia & 3) == 0 && ia - 4 >= insns_min && ia - 1 <= insns_max) {
michael@0:         a0 = *(uint32_t*)(ia - 4);
michael@0:       }
michael@0:       // Leading E forces unconditional only -- fix.  It could be
michael@0:       // anything except F, which is the deprecated NV code.
michael@0:       // BL simm26 (Encoding A1)
michael@0:       if ((a0 & 0xFF000000) == 0xEB000000) {
michael@0:         return true;
michael@0:       }
michael@0:       // Other possible cases:
michael@0:       // BLX simm26 (Encoding A2)
michael@0:       //if ((a0 & 0xFE000000) == 0xFA000000)
michael@0:       //  return true;
michael@0:       // BLX (register) (A1): BLX <c> <Rm>
michael@0:       // cond 0001 0010 1111 1111 1111 0011 Rm
michael@0:       // again, cond can be anything except NV (0xF)
michael@0:     }
michael@0: 
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0: 
michael@0:     // Not an insn we recognise.
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:  private:
michael@0:   // FindSecMap's caller must hold the global lock for reading or writing.
michael@0:   SecMap* FindSecMap(uintptr_t ia) {
michael@0:     // Binary search mSecMaps to find one that brackets |ia|.
michael@0:     // lo and hi need to be signed, else the loop termination tests
michael@0:     // don't work properly.
michael@0:     long int lo = 0;
michael@0:     long int hi = (long int)mSecMaps.size() - 1;
michael@0:     while (true) {
michael@0:       // current unsearched space is from lo to hi, inclusive.
michael@0:       if (lo > hi) {
michael@0:         // not found
michael@0:         return nullptr;
michael@0:       }
michael@0:       long int  mid         = lo + ((hi - lo) / 2);
michael@0:       SecMap*   mid_secMap  = mSecMaps[mid];
michael@0:       uintptr_t mid_minAddr = mid_secMap->mSummaryMinAddr;
michael@0:       uintptr_t mid_maxAddr = mid_secMap->mSummaryMaxAddr;
michael@0:       if (ia < mid_minAddr) { hi = mid-1; continue; }
michael@0:       if (ia > mid_maxAddr) { lo = mid+1; continue; }
michael@0:       MOZ_ASSERT(mid_minAddr <= ia && ia <= mid_maxAddr);
michael@0:       return mid_secMap;
michael@0:     }
michael@0:     // NOTREACHED
michael@0:   }
michael@0: 
michael@0:  private:
michael@0:   // sorted array of per-object ranges, non overlapping, non empty
michael@0:   std::vector<SecMap*> mSecMaps;
michael@0: 
michael@0:   // a logging sink, for debugging.
michael@0:   void (*mLog)(const char*);
michael@0: };
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // CFICache                                                   //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // This is the thread-local cache.  It maps individual insn AVMAs to
michael@0: // the associated CFI record, which live in LUL::mPriMap.
michael@0: //
michael@0: // The cache is a direct map hash table indexed by address.
michael@0: // It has to distinguish 3 cases:
michael@0: //
michael@0: // (1) .mRSet == (RuleSet*)0  ==> cache slot not in use
michael@0: // (2) .mRSet == (RuleSet*)1  ==> slot in use, no RuleSet avail
michael@0: // (3) .mRSet >  (RuleSet*)1  ==> slot in use, RuleSet* available
michael@0: //
michael@0: // Distinguishing between (2) and (3) is important, because if we look
michael@0: // up an address in LUL::mPriMap and find there is no RuleSet, then
michael@0: // that fact needs to cached here, so as to avoid potentially
michael@0: // expensive repeat lookups.
michael@0: 
michael@0: // A CFICacheEntry::mRSet value of zero indicates that the slot is not
michael@0: // in use, and a value of one indicates that the slot is in use but
michael@0: // there is no RuleSet available.
michael@0: #define ENTRY_NOT_IN_USE      ((RuleSet*)0)
michael@0: #define NO_RULESET_AVAILABLE  ((RuleSet*)1)
michael@0: 
michael@0: class CFICache {
michael@0:  public:
michael@0: 
michael@0:   CFICache(PriMap* aPriMap) {
michael@0:     Invalidate();
michael@0:     mPriMap = aPriMap;
michael@0:   }
michael@0: 
michael@0:   void Invalidate() {
michael@0:     for (int i = 0; i < N_ENTRIES; ++i) {
michael@0:       mCache[i].mAVMA = 0;
michael@0:       mCache[i].mRSet = ENTRY_NOT_IN_USE;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   RuleSet* Lookup(uintptr_t ia) {
michael@0:     uintptr_t hash = ia % (uintptr_t)N_ENTRIES;
michael@0:     CFICacheEntry* ce = &mCache[hash];
michael@0:     if (ce->mAVMA == ia) {
michael@0:       // The cache has an entry for |ia|.  Interpret it.
michael@0:       if (ce->mRSet > NO_RULESET_AVAILABLE) {
michael@0:         // There's a RuleSet.  So return it.
michael@0:         return ce->mRSet;
michael@0:       }
michael@0:       if (ce->mRSet == NO_RULESET_AVAILABLE) {
michael@0:         // There's no RuleSet for this address.  Don't update
michael@0:         // the cache, since we might get queried again.
michael@0:         return nullptr;
michael@0:       }
michael@0:       // Otherwise, the slot is not in use.  Fall through to
michael@0:       // the 'miss' case.
michael@0:     }
michael@0: 
michael@0:     // The cache entry is for some other address, or is not in use.
michael@0:     // Update it.  If it can be found in the priMap then install it
michael@0:     // as-is.  Else put NO_RULESET_AVAILABLE in, so as to indicate
michael@0:     // there's no info for this address.
michael@0:     RuleSet* fallback  = mPriMap->Lookup(ia);
michael@0:     mCache[hash].mAVMA = ia;
michael@0:     mCache[hash].mRSet = fallback ? fallback : NO_RULESET_AVAILABLE;
michael@0:     return fallback;
michael@0:   }
michael@0: 
michael@0:  private:
michael@0:   // This should be a prime number.
michael@0:   static const int N_ENTRIES = 509;
michael@0: 
michael@0:   // See comment above for the meaning of these entries.
michael@0:   struct CFICacheEntry {
michael@0:     uintptr_t mAVMA; // AVMA of the associated instruction
michael@0:     RuleSet*  mRSet; // RuleSet* for the instruction
michael@0:   };
michael@0:   CFICacheEntry mCache[N_ENTRIES];
michael@0: 
michael@0:   // Need to have a pointer to the PriMap, so as to be able
michael@0:   // to service misses.
michael@0:   PriMap* mPriMap;
michael@0: };
michael@0: 
michael@0: #undef ENTRY_NOT_IN_USE
michael@0: #undef NO_RULESET_AVAILABLE
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // LUL                                                        //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: LUL::LUL(void (*aLog)(const char*))
michael@0: {
michael@0:   mRWlock = new LulRWLock();
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0:   mLog = aLog;
michael@0:   mPriMap = new PriMap(aLog);
michael@0:   mSegArray = new SegArray();
michael@0: }
michael@0: 
michael@0: 
michael@0: LUL::~LUL()
michael@0: {
michael@0:   // The auto-locked section must have its own scope, so that the
michael@0:   // unlock is performed before the mRWLock is deleted.
michael@0:   {
michael@0:     AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0:     for (std::map<pthread_t,CFICache*>::iterator iter = mCaches.begin();
michael@0:          iter != mCaches.end();
michael@0:          ++iter) {
michael@0:       delete iter->second;
michael@0:     }
michael@0:     delete mPriMap;
michael@0:     delete mSegArray;
michael@0:     mLog = nullptr;
michael@0:   }
michael@0:   // Now we don't hold the lock.  Hence it is safe to delete it.
michael@0:   delete mRWlock;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: LUL::RegisterUnwinderThread()
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0: 
michael@0:   pthread_t me = pthread_self();
michael@0:   CFICache* cache = new CFICache(mPriMap);
michael@0: 
michael@0:   std::pair<std::map<pthread_t,CFICache*>::iterator, bool> res
michael@0:     = mCaches.insert(std::pair<pthread_t,CFICache*>(me, cache));
michael@0:   // "this thread is not already registered"
michael@0:   MOZ_ASSERT(res.second); // "new element was inserted"
michael@0:   // Using mozilla::DebugOnly to declare |res| leads to compilation error
michael@0:   (void)res.second;
michael@0: }
michael@0: 
michael@0: void
michael@0: LUL::NotifyAfterMap(uintptr_t aRXavma, size_t aSize,
michael@0:                     const char* aFileName, const void* aMappedImage)
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0: 
michael@0:   mLog(":\n");
michael@0:   char buf[200];
michael@0:   snprintf(buf, sizeof(buf), "NotifyMap %llx %llu %s\n",
michael@0:            (unsigned long long int)aRXavma, (unsigned long long int)aSize,
michael@0:            aFileName);
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   mLog(buf);
michael@0: 
michael@0:   InvalidateCFICaches();
michael@0: 
michael@0:   // Ignore obviously-stupid notifications.
michael@0:   if (aSize > 0) {
michael@0: 
michael@0:     // Here's a new mapping, for this object.
michael@0:     SecMap* smap = new SecMap(mLog);
michael@0: 
michael@0:     // Read CFI or EXIDX unwind data into |smap|.
michael@0:     if (!aMappedImage) {
michael@0:       (void)lul::ReadSymbolData(
michael@0:               string(aFileName), std::vector<string>(), smap,
michael@0:               (void*)aRXavma, mLog);
michael@0:     } else {
michael@0:       (void)lul::ReadSymbolDataInternal(
michael@0:               (const uint8_t*)aMappedImage,
michael@0:               string(aFileName), std::vector<string>(), smap,
michael@0:               (void*)aRXavma, mLog);
michael@0:     }
michael@0: 
michael@0:     mLog("NotifyMap .. preparing entries\n");
michael@0: 
michael@0:     smap->PrepareRuleSets(aRXavma, aSize);
michael@0: 
michael@0:     snprintf(buf, sizeof(buf),
michael@0:              "NotifyMap got %lld entries\n", (long long int)smap->Size());
michael@0:     buf[sizeof(buf)-1] = 0;
michael@0:     mLog(buf);
michael@0: 
michael@0:     // Add it to the primary map (the top level set of mapped objects).
michael@0:     mPriMap->AddSecMap(smap);
michael@0: 
michael@0:     // Tell the segment array about the mapping, so that the stack
michael@0:     // scan and __kernel_syscall mechanisms know where valid code is.
michael@0:     mSegArray->add(aRXavma, aRXavma + aSize - 1, true);
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: LUL::NotifyExecutableArea(uintptr_t aRXavma, size_t aSize)
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0: 
michael@0:   mLog(":\n");
michael@0:   char buf[200];
michael@0:   snprintf(buf, sizeof(buf), "NotifyExecutableArea %llx %llu\n",
michael@0:            (unsigned long long int)aRXavma, (unsigned long long int)aSize);
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   mLog(buf);
michael@0: 
michael@0:   InvalidateCFICaches();
michael@0: 
michael@0:   // Ignore obviously-stupid notifications.
michael@0:   if (aSize > 0) {
michael@0:     // Tell the segment array about the mapping, so that the stack
michael@0:     // scan and __kernel_syscall mechanisms know where valid code is.
michael@0:     mSegArray->add(aRXavma, aRXavma + aSize - 1, true);
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: LUL::NotifyBeforeUnmap(uintptr_t aRXavmaMin, uintptr_t aRXavmaMax)
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0: 
michael@0:   mLog(":\n");
michael@0:   char buf[100];
michael@0:   snprintf(buf, sizeof(buf), "NotifyUnmap %016llx-%016llx\n",
michael@0:            (unsigned long long int)aRXavmaMin,
michael@0:            (unsigned long long int)aRXavmaMax);
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   mLog(buf);
michael@0: 
michael@0:   MOZ_ASSERT(aRXavmaMin <= aRXavmaMax);
michael@0: 
michael@0:   InvalidateCFICaches();
michael@0: 
michael@0:   // Remove from the primary map, any secondary maps that intersect
michael@0:   // with the address range.  Also delete the secondary maps.
michael@0:   mPriMap->RemoveSecMapsInRange(aRXavmaMin, aRXavmaMax);
michael@0: 
michael@0:   // Tell the segment array that the address range no longer
michael@0:   // contains valid code.
michael@0:   mSegArray->add(aRXavmaMin, aRXavmaMax, false);
michael@0: 
michael@0:   snprintf(buf, sizeof(buf), "NotifyUnmap: now have %d SecMaps\n",
michael@0:            (int)mPriMap->CountSecMaps());
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   mLog(buf);
michael@0: }
michael@0: 
michael@0: 
michael@0: size_t
michael@0: LUL::CountMappings()
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_WRITING);
michael@0:   return mPriMap->CountSecMaps();
michael@0: }
michael@0: 
michael@0: 
michael@0: static
michael@0: TaggedUWord DerefTUW(TaggedUWord aAddr, StackImage* aStackImg)
michael@0: {
michael@0:   if (!aAddr.Valid()) {
michael@0:     return TaggedUWord();
michael@0:   }
michael@0:   if (aAddr.Value() < aStackImg->mStartAvma) {
michael@0:     return TaggedUWord();
michael@0:   }
michael@0:   if (aAddr.Value() + sizeof(uintptr_t) > aStackImg->mStartAvma
michael@0:                                           + aStackImg->mLen) {
michael@0:     return TaggedUWord();
michael@0:   }
michael@0:   return TaggedUWord(*(uintptr_t*)(aStackImg->mContents + aAddr.Value()
michael@0:                                    - aStackImg->mStartAvma));
michael@0: }
michael@0: 
michael@0: static
michael@0: TaggedUWord EvaluateReg(int16_t aReg, UnwindRegs* aOldRegs, TaggedUWord aCFA)
michael@0: {
michael@0:   switch (aReg) {
michael@0:     case DW_REG_CFA:       return aCFA;
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:     case DW_REG_INTEL_XBP: return aOldRegs->xbp;
michael@0:     case DW_REG_INTEL_XSP: return aOldRegs->xsp;
michael@0:     case DW_REG_INTEL_XIP: return aOldRegs->xip;
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:     case DW_REG_ARM_R7:    return aOldRegs->r7;
michael@0:     case DW_REG_ARM_R11:   return aOldRegs->r11;
michael@0:     case DW_REG_ARM_R12:   return aOldRegs->r12;
michael@0:     case DW_REG_ARM_R13:   return aOldRegs->r13;
michael@0:     case DW_REG_ARM_R14:   return aOldRegs->r14;
michael@0:     case DW_REG_ARM_R15:   return aOldRegs->r15;
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0:     default: MOZ_ASSERT(0); return TaggedUWord();
michael@0:   }
michael@0: }
michael@0: 
michael@0: static
michael@0: TaggedUWord EvaluateExpr(LExpr aExpr, UnwindRegs* aOldRegs,
michael@0:                          TaggedUWord aCFA, StackImage* aStackImg)
michael@0: {
michael@0:   switch (aExpr.mHow) {
michael@0:     case LExpr::UNKNOWN:
michael@0:       return TaggedUWord();
michael@0:     case LExpr::NODEREF: {
michael@0:       TaggedUWord tuw = EvaluateReg(aExpr.mReg, aOldRegs, aCFA);
michael@0:       tuw.Add(TaggedUWord((intptr_t)aExpr.mOffset));
michael@0:       return tuw;
michael@0:     }
michael@0:     case LExpr::DEREF: {
michael@0:       TaggedUWord tuw = EvaluateReg(aExpr.mReg, aOldRegs, aCFA);
michael@0:       tuw.Add(TaggedUWord((intptr_t)aExpr.mOffset));
michael@0:       return DerefTUW(tuw, aStackImg);
michael@0:     }
michael@0:     default:
michael@0:       MOZ_ASSERT(0);
michael@0:       return TaggedUWord();
michael@0:   }
michael@0: }
michael@0: 
michael@0: static
michael@0: void UseRuleSet(/*MOD*/UnwindRegs* aRegs,
michael@0:                 StackImage* aStackImg, RuleSet* aRS)
michael@0: {
michael@0:   // Take a copy of regs, since we'll need to refer to the old values
michael@0:   // whilst computing the new ones.
michael@0:   UnwindRegs old_regs = *aRegs;
michael@0: 
michael@0:   // Mark all the current register values as invalid, so that the
michael@0:   // caller can see, on our return, which ones have been computed
michael@0:   // anew.  If we don't even manage to compute a new PC value, then
michael@0:   // the caller will have to abandon the unwind.
michael@0:   // FIXME: Create and use instead: aRegs->SetAllInvalid();
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:   aRegs->xbp = TaggedUWord();
michael@0:   aRegs->xsp = TaggedUWord();
michael@0:   aRegs->xip = TaggedUWord();
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:   aRegs->r7  = TaggedUWord();
michael@0:   aRegs->r11 = TaggedUWord();
michael@0:   aRegs->r12 = TaggedUWord();
michael@0:   aRegs->r13 = TaggedUWord();
michael@0:   aRegs->r14 = TaggedUWord();
michael@0:   aRegs->r15 = TaggedUWord();
michael@0: #else
michael@0: #  error "Unsupported arch"
michael@0: #endif
michael@0: 
michael@0:   // This is generally useful.
michael@0:   const TaggedUWord inval = TaggedUWord();
michael@0: 
michael@0:   // First, compute the CFA.
michael@0:   TaggedUWord cfa = EvaluateExpr(aRS->mCfaExpr, &old_regs,
michael@0:                                  inval/*old cfa*/, aStackImg);
michael@0: 
michael@0:   // If we didn't manage to compute the CFA, well .. that's ungood,
michael@0:   // but keep going anyway.  It'll be OK provided none of the register
michael@0:   // value rules mention the CFA.  In any case, compute the new values
michael@0:   // for each register that we're tracking.
michael@0: 
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:   aRegs->xbp = EvaluateExpr(aRS->mXbpExpr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->xsp = EvaluateExpr(aRS->mXspExpr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->xip = EvaluateExpr(aRS->mXipExpr, &old_regs, cfa, aStackImg);
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:   aRegs->r7  = EvaluateExpr(aRS->mR7expr,  &old_regs, cfa, aStackImg);
michael@0:   aRegs->r11 = EvaluateExpr(aRS->mR11expr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->r12 = EvaluateExpr(aRS->mR12expr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->r13 = EvaluateExpr(aRS->mR13expr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->r14 = EvaluateExpr(aRS->mR14expr, &old_regs, cfa, aStackImg);
michael@0:   aRegs->r15 = EvaluateExpr(aRS->mR15expr, &old_regs, cfa, aStackImg);
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0: 
michael@0:   // We're done.  Any regs for which we didn't manage to compute a
michael@0:   // new value will now be marked as invalid.
michael@0: }
michael@0: 
michael@0: void
michael@0: LUL::Unwind(/*OUT*/uintptr_t* aFramePCs,
michael@0:             /*OUT*/uintptr_t* aFrameSPs,
michael@0:             /*OUT*/size_t* aFramesUsed, 
michael@0:             /*OUT*/size_t* aScannedFramesAcquired,
michael@0:             size_t aFramesAvail,
michael@0:             size_t aScannedFramesAllowed,
michael@0:             UnwindRegs* aStartRegs, StackImage* aStackImg)
michael@0: {
michael@0:   AutoLulRWLocker lock(mRWlock, AutoLulRWLocker::FOR_READING);
michael@0: 
michael@0:   pthread_t me = pthread_self();
michael@0:   std::map<pthread_t, CFICache*>::iterator iter = mCaches.find(me);
michael@0: 
michael@0:   if (iter == mCaches.end()) {
michael@0:     // The calling thread is not registered for unwinding.
michael@0:     MOZ_CRASH();
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   CFICache* cache = iter->second;
michael@0:   MOZ_ASSERT(cache);
michael@0: 
michael@0:   // Do unwindery, possibly modifying |cache|.
michael@0: 
michael@0:   /////////////////////////////////////////////////////////
michael@0:   // BEGIN UNWIND
michael@0: 
michael@0:   *aFramesUsed = 0;
michael@0: 
michael@0:   UnwindRegs  regs          = *aStartRegs;
michael@0:   TaggedUWord last_valid_sp = TaggedUWord();
michael@0: 
michael@0:   // Stack-scan control
michael@0:   unsigned int n_scanned_frames      = 0;  // # s-s frames recovered so far
michael@0:   static const int NUM_SCANNED_WORDS = 50; // max allowed scan length
michael@0: 
michael@0:   while (true) {
michael@0: 
michael@0:     if (DEBUG_MAIN) {
michael@0:       char buf[300];
michael@0:       mLog("\n");
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:       snprintf(buf, sizeof(buf),
michael@0:                "LoopTop: rip %d/%llx  rsp %d/%llx  rbp %d/%llx\n",
michael@0:                (int)regs.xip.Valid(), (unsigned long long int)regs.xip.Value(),
michael@0:                (int)regs.xsp.Valid(), (unsigned long long int)regs.xsp.Value(),
michael@0:                (int)regs.xbp.Valid(), (unsigned long long int)regs.xbp.Value());
michael@0:       buf[sizeof(buf)-1] = 0;
michael@0:       mLog(buf);
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:       snprintf(buf, sizeof(buf),
michael@0:                "LoopTop: r15 %d/%llx  r7 %d/%llx  r11 %d/%llx"
michael@0:                "  r12 %d/%llx  r13 %d/%llx  r14 %d/%llx\n",
michael@0:                (int)regs.r15.Valid(), (unsigned long long int)regs.r15.Value(),
michael@0:                (int)regs.r7.Valid(),  (unsigned long long int)regs.r7.Value(),
michael@0:                (int)regs.r11.Valid(), (unsigned long long int)regs.r11.Value(),
michael@0:                (int)regs.r12.Valid(), (unsigned long long int)regs.r12.Value(),
michael@0:                (int)regs.r13.Valid(), (unsigned long long int)regs.r13.Value(),
michael@0:                (int)regs.r14.Valid(), (unsigned long long int)regs.r14.Value());
michael@0:       buf[sizeof(buf)-1] = 0;
michael@0:       mLog(buf);
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0:     }
michael@0: 
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:     TaggedUWord ia = regs.xip;
michael@0:     TaggedUWord sp = regs.xsp;
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:     TaggedUWord ia = (*aFramesUsed == 0 ? regs.r15 : regs.r14);
michael@0:     TaggedUWord sp = regs.r13;
michael@0: #else
michael@0: # error "Unsupported arch"
michael@0: #endif
michael@0: 
michael@0:     if (*aFramesUsed >= aFramesAvail) {
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     // If we don't have a valid value for the PC, give up.
michael@0:     if (!ia.Valid()) {
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     // If this is the innermost frame, record the SP value, which
michael@0:     // presumably is valid.  If this isn't the innermost frame, and we
michael@0:     // have a valid SP value, check that its SP value isn't less that
michael@0:     // the one we've seen so far, so as to catch potential SP value
michael@0:     // cycles.
michael@0:     if (*aFramesUsed == 0) {
michael@0:       last_valid_sp = sp;
michael@0:     } else {
michael@0:       MOZ_ASSERT(last_valid_sp.Valid());
michael@0:       if (sp.Valid()) {
michael@0:         if (sp.Value() < last_valid_sp.Value()) {
michael@0:           // Hmm, SP going in the wrong direction.  Let's stop.
michael@0:           break;
michael@0:         }
michael@0:         // Remember where we got to.
michael@0:         last_valid_sp = sp;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     // For the innermost frame, the IA value is what we need.  For all
michael@0:     // other frames, it's actually the return address, so back up one
michael@0:     // byte so as to get it into the calling instruction.
michael@0:     aFramePCs[*aFramesUsed] = ia.Value() - (*aFramesUsed == 0 ? 0 : 1);
michael@0:     aFrameSPs[*aFramesUsed] = sp.Valid() ? sp.Value() : 0;
michael@0:     (*aFramesUsed)++;
michael@0: 
michael@0:     // Find the RuleSet for the current IA, if any.  This will also
michael@0:     // query the backing (secondary) maps if it isn't found in the
michael@0:     // thread-local cache.
michael@0: 
michael@0:     // If this isn't the innermost frame, back up into the calling insn.
michael@0:     if (*aFramesUsed > 1) {
michael@0:       ia.Add(TaggedUWord((uintptr_t)(-1)));
michael@0:     }
michael@0: 
michael@0:     RuleSet* ruleset = cache->Lookup(ia.Value());
michael@0:     if (DEBUG_MAIN) {
michael@0:       char buf[100];
michael@0:       snprintf(buf, sizeof(buf), "ruleset for 0x%llx = %p\n",
michael@0:                (unsigned long long int)ia.Value(), ruleset);
michael@0:       buf[sizeof(buf)-1] = 0;
michael@0:       mLog(buf);
michael@0:     }
michael@0: 
michael@0:     /////////////////////////////////////////////
michael@0:     ////
michael@0:     // On 32 bit x86-linux, syscalls are often done via the VDSO
michael@0:     // function __kernel_vsyscall, which doesn't have a corresponding
michael@0:     // object that we can read debuginfo from.  That effectively kills
michael@0:     // off all stack traces for threads blocked in syscalls.  Hence
michael@0:     // special-case by looking at the code surrounding the program
michael@0:     // counter.
michael@0:     //
michael@0:     // 0xf7757420 <__kernel_vsyscall+0>:	push   %ecx
michael@0:     // 0xf7757421 <__kernel_vsyscall+1>:	push   %edx
michael@0:     // 0xf7757422 <__kernel_vsyscall+2>:	push   %ebp
michael@0:     // 0xf7757423 <__kernel_vsyscall+3>:	mov    %esp,%ebp
michael@0:     // 0xf7757425 <__kernel_vsyscall+5>:	sysenter
michael@0:     // 0xf7757427 <__kernel_vsyscall+7>:	nop
michael@0:     // 0xf7757428 <__kernel_vsyscall+8>:	nop
michael@0:     // 0xf7757429 <__kernel_vsyscall+9>:	nop
michael@0:     // 0xf775742a <__kernel_vsyscall+10>:	nop
michael@0:     // 0xf775742b <__kernel_vsyscall+11>:	nop
michael@0:     // 0xf775742c <__kernel_vsyscall+12>:	nop
michael@0:     // 0xf775742d <__kernel_vsyscall+13>:	nop
michael@0:     // 0xf775742e <__kernel_vsyscall+14>:	int    $0x80
michael@0:     // 0xf7757430 <__kernel_vsyscall+16>:	pop    %ebp
michael@0:     // 0xf7757431 <__kernel_vsyscall+17>:	pop    %edx
michael@0:     // 0xf7757432 <__kernel_vsyscall+18>:	pop    %ecx
michael@0:     // 0xf7757433 <__kernel_vsyscall+19>:	ret
michael@0:     //
michael@0:     // In cases where the sampled thread is blocked in a syscall, its
michael@0:     // program counter will point at "pop %ebp".  Hence we look for
michael@0:     // the sequence "int $0x80; pop %ebp; pop %edx; pop %ecx; ret", and
michael@0:     // the corresponding register-recovery actions are:
michael@0:     //    new_ebp = *(old_esp + 0)
michael@0:     //    new eip = *(old_esp + 12)
michael@0:     //    new_esp = old_esp + 16
michael@0:     //
michael@0:     // It may also be the case that the program counter points two
michael@0:     // nops before the "int $0x80", viz, is __kernel_vsyscall+12, in
michael@0:     // the case where the syscall has been restarted but the thread
michael@0:     // hasn't been rescheduled.  The code below doesn't handle that;
michael@0:     // it could easily be made to.
michael@0:     //
michael@0: #if defined(LUL_PLAT_x86_android) || defined(LUL_PLAT_x86_linux)
michael@0:     if (!ruleset && *aFramesUsed == 1 && ia.Valid() && sp.Valid()) {
michael@0:       uintptr_t insns_min, insns_max;
michael@0:       uintptr_t eip = ia.Value();
michael@0:       bool b = mSegArray->getBoundingCodeSegment(&insns_min, &insns_max, eip);
michael@0:       if (b && eip - 2 >= insns_min && eip + 3 <= insns_max) {
michael@0:         uint8_t* eipC = (uint8_t*)eip;
michael@0:         if (eipC[-2] == 0xCD && eipC[-1] == 0x80 && eipC[0] == 0x5D &&
michael@0:             eipC[1] == 0x5A && eipC[2] == 0x59 && eipC[3] == 0xC3) {
michael@0:           TaggedUWord sp_plus_0  = sp;
michael@0:           TaggedUWord sp_plus_12 = sp;
michael@0:           TaggedUWord sp_plus_16 = sp;
michael@0:           sp_plus_12.Add(TaggedUWord(12));
michael@0:           sp_plus_16.Add(TaggedUWord(16));
michael@0:           TaggedUWord new_ebp = DerefTUW(sp_plus_0, aStackImg);
michael@0:           TaggedUWord new_eip = DerefTUW(sp_plus_12, aStackImg);
michael@0:           TaggedUWord new_esp = sp_plus_16;
michael@0:           if (new_ebp.Valid() && new_eip.Valid() && new_esp.Valid()) {
michael@0:             regs.xbp = new_ebp;
michael@0:             regs.xip = new_eip;
michael@0:             regs.xsp = new_esp;
michael@0:             continue;
michael@0:           }
michael@0:         }
michael@0:       }
michael@0:     }
michael@0: #endif
michael@0:     ////
michael@0:     /////////////////////////////////////////////
michael@0: 
michael@0:     // So, do we have a ruleset for this address?  If so, use it now.
michael@0:     if (ruleset) {
michael@0: 
michael@0:       if (DEBUG_MAIN) {
michael@0:         ruleset->Print(mLog); mLog("\n");
michael@0:       }
michael@0:       // Use the RuleSet to compute the registers for the previous
michael@0:       // frame.  |regs| is modified in-place.
michael@0:       UseRuleSet(&regs, aStackImg, ruleset);
michael@0: 
michael@0:     } else {
michael@0: 
michael@0:       // There's no RuleSet for the specified address, so see if
michael@0:       // it's possible to get anywhere by stack-scanning.
michael@0: 
michael@0:       // Use stack scanning frugally.
michael@0:       if (n_scanned_frames++ >= aScannedFramesAllowed) {
michael@0:         break;
michael@0:       }
michael@0: 
michael@0:       // We can't scan the stack without a valid, aligned stack pointer.
michael@0:       if (!sp.IsAligned()) {
michael@0:         break;
michael@0:       }
michael@0: 
michael@0:       bool scan_succeeded = false;
michael@0:       for (int i = 0; i < NUM_SCANNED_WORDS; ++i) {
michael@0:         TaggedUWord aWord = DerefTUW(sp, aStackImg);
michael@0:         // aWord is something we fished off the stack.  It should be
michael@0:         // valid, unless we overran the stack bounds.
michael@0:         if (!aWord.Valid()) {
michael@0:           break;
michael@0:         }
michael@0: 
michael@0:         // Now, does aWord point inside a text section and immediately
michael@0:         // after something that looks like a call instruction?
michael@0:         if (mPriMap->MaybeIsReturnPoint(aWord, mSegArray)) {
michael@0:           // Yes it does.  Update the unwound registers heuristically,
michael@0:           // using the same schemes as Breakpad does.
michael@0:           scan_succeeded = true;
michael@0:           (*aScannedFramesAcquired)++;
michael@0: 
michael@0: #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)
michael@0:           // The same logic applies for the 32- and 64-bit cases.
michael@0:           // Register names of the form xsp etc refer to (eg) esp in
michael@0:           // the 32-bit case and rsp in the 64-bit case.
michael@0: #         if defined(LUL_ARCH_x64)
michael@0:           const int wordSize = 8;
michael@0: #         else
michael@0:           const int wordSize = 4;
michael@0: #         endif
michael@0:           // The return address -- at XSP -- will have been pushed by
michael@0:           // the CALL instruction.  So the caller's XSP value
michael@0:           // immediately before and after that CALL instruction is the
michael@0:           // word above XSP.
michael@0:           regs.xsp = sp;
michael@0:           regs.xsp.Add(TaggedUWord(wordSize));
michael@0: 
michael@0:           // aWord points at the return point, so back up one byte
michael@0:           // to put it in the calling instruction.
michael@0:           regs.xip = aWord;
michael@0:           regs.xip.Add(TaggedUWord((uintptr_t)(-1)));
michael@0: 
michael@0:           // Computing a new value from the frame pointer is more tricky.
michael@0:           if (regs.xbp.Valid() &&
michael@0:               sp.Valid() && regs.xbp.Value() == sp.Value() - wordSize) {
michael@0:             // One possibility is that the callee begins with the standard
michael@0:             // preamble "push %xbp; mov %xsp, %xbp".  In which case, the
michael@0:             // (1) caller's XBP value will be at the word below XSP, and
michael@0:             // (2) the current (callee's) XBP will point at that word:
michael@0:             regs.xbp = DerefTUW(regs.xbp, aStackImg);
michael@0:           } else if (regs.xbp.Valid() &&
michael@0:                      sp.Valid() && regs.xbp.Value() >= sp.Value() + wordSize) {
michael@0:             // If that didn't work out, maybe the callee didn't change
michael@0:             // XBP, so it still holds the caller's value.  For that to
michael@0:             // be plausible, XBP will need to have a value at least
michael@0:             // higher than XSP since that holds the purported return
michael@0:             // address.  In which case do nothing, since XBP already
michael@0:             // holds the "right" value.
michael@0:           } else {
michael@0:             // Mark XBP as invalid, so that subsequent unwind iterations
michael@0:             // don't assume it holds valid data.
michael@0:             regs.xbp = TaggedUWord();
michael@0:           }
michael@0: 
michael@0:           // Move on to the next word up the stack
michael@0:           sp.Add(TaggedUWord(wordSize));
michael@0: 
michael@0: #elif defined(LUL_ARCH_arm)
michael@0:           // Set all registers to be undefined, except for SP(R13) and
michael@0:           // PC(R15).
michael@0: 
michael@0:           // aWord points either at the return point, if returning to
michael@0:           // ARM code, or one insn past the return point if returning
michael@0:           // to Thumb code.  In both cases, aWord-2 is guaranteed to
michael@0:           // fall within the calling instruction.
michael@0:           regs.r15 = aWord;
michael@0:           regs.r15.Add(TaggedUWord((uintptr_t)(-2)));
michael@0: 
michael@0:           // Make SP be the word above the location where the return
michael@0:           // address was found.
michael@0:           regs.r13 = sp;
michael@0:           regs.r13.Add(TaggedUWord(4));
michael@0: 
michael@0:           // All other regs are undefined.
michael@0:           regs.r7 = regs.r11 = regs.r12 = regs.r14 = TaggedUWord();
michael@0: 
michael@0:           // Move on to the next word up the stack
michael@0:           sp.Add(TaggedUWord(4));
michael@0: 
michael@0: #else
michael@0: # error "Unknown plat"
michael@0: #endif
michael@0: 
michael@0:           break;
michael@0:         }
michael@0: 
michael@0:       } // for (int i = 0; i < NUM_SCANNED_WORDS; i++)
michael@0: 
michael@0:       // We tried to make progress by scanning the stack, but failed.
michael@0:       // So give up -- fall out of the top level unwind loop.
michael@0:       if (!scan_succeeded) {
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:   } // top level unwind loop
michael@0: 
michael@0:   // END UNWIND
michael@0:   /////////////////////////////////////////////////////////
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: LUL::InvalidateCFICaches()
michael@0: {
michael@0:   // NB: the caller must hold m_rwl for writing.
michael@0: 
michael@0:   // FIXME: this could get expensive.  Use a bool to remember when the
michael@0:   // caches have been invalidated and hence avoid duplicate invalidations.
michael@0:   for (std::map<pthread_t,CFICache*>::iterator iter = mCaches.begin();
michael@0:        iter != mCaches.end();
michael@0:        ++iter) {
michael@0:     iter->second->Invalidate();
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////
michael@0: // LUL Unit Testing                                           //
michael@0: ////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static const int LUL_UNIT_TEST_STACK_SIZE = 16384;
michael@0: 
michael@0: // This function is innermost in the test call sequence.  It uses LUL
michael@0: // to unwind, and compares the result with the sequence specified in
michael@0: // the director string.  These need to agree in order for the test to
michael@0: // pass.  In order not to screw up the results, this function needs
michael@0: // to have a not-very big stack frame, since we're only presenting
michael@0: // the innermost LUL_UNIT_TEST_STACK_SIZE bytes of stack to LUL, and
michael@0: // that chunk unavoidably includes the frame for this function.
michael@0: //
michael@0: // This function must not be inlined into its callers.  Doing so will
michael@0: // cause the expected-vs-actual backtrace consistency checking to
michael@0: // fail.  Prints summary results to |aLUL|'s logging sink and also
michael@0: // returns a boolean indicating whether or not the test passed.
michael@0: static __attribute__((noinline))
michael@0: bool GetAndCheckStackTrace(LUL* aLUL, const char* dstring)
michael@0: {
michael@0:   // Get hold of the current unwind-start registers.
michael@0:   UnwindRegs startRegs;
michael@0:   memset(&startRegs, 0, sizeof(startRegs));
michael@0: #if defined(LUL_PLAT_x64_linux)
michael@0:   volatile uintptr_t block[3];
michael@0:   MOZ_ASSERT(sizeof(block) == 24);
michael@0:   __asm__ __volatile__(
michael@0:     "leaq 0(%%rip), %%r15"   "\n\t"
michael@0:     "movq %%r15, 0(%0)"      "\n\t"
michael@0:     "movq %%rsp, 8(%0)"      "\n\t"
michael@0:     "movq %%rbp, 16(%0)"     "\n"
michael@0:     : : "r"(&block[0]) : "memory", "r15"
michael@0:   );
michael@0:   startRegs.xip = TaggedUWord(block[0]);
michael@0:   startRegs.xsp = TaggedUWord(block[1]);
michael@0:   startRegs.xbp = TaggedUWord(block[2]);
michael@0:   const uintptr_t REDZONE_SIZE = 128;
michael@0:   uintptr_t start = block[1] - REDZONE_SIZE;
michael@0: #elif defined(LUL_PLAT_x86_linux) || defined(LUL_PLAT_x86_android)
michael@0:   volatile uintptr_t block[3];
michael@0:   MOZ_ASSERT(sizeof(block) == 12);
michael@0:   __asm__ __volatile__(
michael@0:     ".byte 0xE8,0x00,0x00,0x00,0x00"/*call next insn*/  "\n\t"
michael@0:     "popl %%edi"             "\n\t"
michael@0:     "movl %%edi, 0(%0)"      "\n\t"
michael@0:     "movl %%esp, 4(%0)"      "\n\t"
michael@0:     "movl %%ebp, 8(%0)"      "\n"
michael@0:     : : "r"(&block[0]) : "memory", "edi"
michael@0:   );
michael@0:   startRegs.xip = TaggedUWord(block[0]);
michael@0:   startRegs.xsp = TaggedUWord(block[1]);
michael@0:   startRegs.xbp = TaggedUWord(block[2]);
michael@0:   const uintptr_t REDZONE_SIZE = 0;
michael@0:   uintptr_t start = block[1] - REDZONE_SIZE;
michael@0: #elif defined(LUL_PLAT_arm_android)
michael@0:   volatile uintptr_t block[6];
michael@0:   MOZ_ASSERT(sizeof(block) == 24);
michael@0:   __asm__ __volatile__(
michael@0:     "mov r0, r15"            "\n\t"
michael@0:     "str r0,  [%0, #0]"      "\n\t"
michael@0:     "str r14, [%0, #4]"      "\n\t"
michael@0:     "str r13, [%0, #8]"      "\n\t"
michael@0:     "str r12, [%0, #12]"     "\n\t"
michael@0:     "str r11, [%0, #16]"     "\n\t"
michael@0:     "str r7,  [%0, #20]"     "\n"
michael@0:     : : "r"(&block[0]) : "memory", "r0"
michael@0:   );
michael@0:   startRegs.r15 = TaggedUWord(block[0]);
michael@0:   startRegs.r14 = TaggedUWord(block[1]);
michael@0:   startRegs.r13 = TaggedUWord(block[2]);
michael@0:   startRegs.r12 = TaggedUWord(block[3]);
michael@0:   startRegs.r11 = TaggedUWord(block[4]);
michael@0:   startRegs.r7  = TaggedUWord(block[5]);
michael@0:   const uintptr_t REDZONE_SIZE = 0;
michael@0:   uintptr_t start = block[1] - REDZONE_SIZE;
michael@0: #else
michael@0: # error "Unsupported platform"
michael@0: #endif
michael@0: 
michael@0:   // Get hold of the innermost LUL_UNIT_TEST_STACK_SIZE bytes of the
michael@0:   // stack.
michael@0:   uintptr_t end = start + LUL_UNIT_TEST_STACK_SIZE;
michael@0:   uintptr_t ws  = sizeof(void*);
michael@0:   start &= ~(ws-1);
michael@0:   end   &= ~(ws-1);
michael@0:   uintptr_t nToCopy = end - start;
michael@0:   if (nToCopy > lul::N_STACK_BYTES) {
michael@0:     nToCopy = lul::N_STACK_BYTES;
michael@0:   }
michael@0:   MOZ_ASSERT(nToCopy <= lul::N_STACK_BYTES);
michael@0:   StackImage* stackImg = new StackImage();
michael@0:   stackImg->mLen       = nToCopy;
michael@0:   stackImg->mStartAvma = start;
michael@0:   if (nToCopy > 0) {
michael@0:     MOZ_MAKE_MEM_DEFINED((void*)start, nToCopy);
michael@0:     memcpy(&stackImg->mContents[0], (void*)start, nToCopy);
michael@0:   }
michael@0: 
michael@0:   // Unwind it.
michael@0:   const int MAX_TEST_FRAMES = 64;
michael@0:   uintptr_t framePCs[MAX_TEST_FRAMES];
michael@0:   uintptr_t frameSPs[MAX_TEST_FRAMES];
michael@0:   size_t framesAvail = mozilla::ArrayLength(framePCs);
michael@0:   size_t framesUsed  = 0;
michael@0:   size_t scannedFramesAllowed = 0;
michael@0:   size_t scannedFramesAcquired = 0;
michael@0:   aLUL->Unwind( &framePCs[0], &frameSPs[0],
michael@0:                 &framesUsed, &scannedFramesAcquired,
michael@0:                 framesAvail, scannedFramesAllowed,
michael@0:                 &startRegs, stackImg );
michael@0: 
michael@0:   delete stackImg;
michael@0: 
michael@0:   //if (0) {
michael@0:   //  // Show what we have.
michael@0:   //  fprintf(stderr, "Got %d frames:\n", (int)framesUsed);
michael@0:   //  for (size_t i = 0; i < framesUsed; i++) {
michael@0:   //    fprintf(stderr, "  [%2d]   SP %p   PC %p\n",
michael@0:   //            (int)i, (void*)frameSPs[i], (void*)framePCs[i]);
michael@0:   //  }
michael@0:   //  fprintf(stderr, "\n");
michael@0:   //}
michael@0: 
michael@0:   // Check to see if there's a consistent binding between digits in
michael@0:   // the director string ('1' .. '8') and the PC values acquired by
michael@0:   // the unwind.  If there isn't, the unwinding has failed somehow.
michael@0:   uintptr_t binding[8];  // binding for '1' .. binding for '8'
michael@0:   memset((void*)binding, 0, sizeof(binding));
michael@0: 
michael@0:   // The general plan is to work backwards along the director string
michael@0:   // and forwards along the framePCs array.  Doing so corresponds to
michael@0:   // working outwards from the innermost frame of the recursive test set.
michael@0:   const char* cursor = dstring;
michael@0: 
michael@0:   // Find the end.  This leaves |cursor| two bytes past the first
michael@0:   // character we want to look at -- see comment below.
michael@0:   while (*cursor) cursor++;
michael@0: 
michael@0:   // Counts the number of consistent frames.
michael@0:   size_t nConsistent = 0;
michael@0: 
michael@0:   // Iterate back to the start of the director string.  The starting
michael@0:   // points are a bit complex.  We can't use framePCs[0] because that
michael@0:   // contains the PC in this frame (above).  We can't use framePCs[1]
michael@0:   // because that will contain the PC at return point in the recursive
michael@0:   // test group (TestFn[1-8]) for their call "out" to this function,
michael@0:   // GetAndCheckStackTrace.  Although LUL will compute a correct
michael@0:   // return address, that will not be the same return address as for a
michael@0:   // recursive call out of the the function to another function in the
michael@0:   // group.  Hence we can only start consistency checking at
michael@0:   // framePCs[2].
michael@0:   //
michael@0:   // To be consistent, then, we must ignore the last element in the
michael@0:   // director string as that corresponds to framePCs[1].  Hence the
michael@0:   // start points are: framePCs[2] and the director string 2 bytes
michael@0:   // before the terminating zero.
michael@0:   //
michael@0:   // Also as a result of this, the number of consistent frames counted
michael@0:   // will always be one less than the length of the director string
michael@0:   // (not including its terminating zero).
michael@0:   size_t frameIx;
michael@0:   for (cursor = cursor-2, frameIx = 2;
michael@0:        cursor >= dstring && frameIx < framesUsed;
michael@0:        cursor--, frameIx++) {
michael@0:     char      c  = *cursor;
michael@0:     uintptr_t pc = framePCs[frameIx];
michael@0:     // If this doesn't hold, the director string is ill-formed.
michael@0:     MOZ_ASSERT(c >= '1' && c <= '8');
michael@0:     int n = ((int)c) - ((int)'1');
michael@0:     if (binding[n] == 0) {
michael@0:       // There's no binding for |c| yet, so install |pc| and carry on.
michael@0:       binding[n] = pc;
michael@0:       nConsistent++;
michael@0:       continue;
michael@0:     }
michael@0:     // There's a pre-existing binding for |c|.  Check it's consistent.
michael@0:     if (binding[n] != pc) {
michael@0:       // Not consistent.  Give up now.
michael@0:       break;
michael@0:     }
michael@0:     // Consistent.  Keep going.
michael@0:     nConsistent++;
michael@0:   }
michael@0: 
michael@0:   // So, did we succeed?
michael@0:   bool passed = nConsistent+1 == strlen(dstring);
michael@0: 
michael@0:   // Show the results.
michael@0:   char buf[200];
michael@0:   snprintf(buf, sizeof(buf), "LULUnitTest:   dstring = %s\n", dstring);
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   aLUL->mLog(buf);
michael@0:   snprintf(buf, sizeof(buf),
michael@0:            "LULUnitTest:     %d consistent, %d in dstring: %s\n",
michael@0:            (int)nConsistent, (int)strlen(dstring),
michael@0:            passed ? "PASS" : "FAIL");
michael@0:   buf[sizeof(buf)-1] = 0;
michael@0:   aLUL->mLog(buf);
michael@0: 
michael@0:   return passed;
michael@0: }
michael@0: 
michael@0: 
michael@0: // Macro magic to create a set of 8 mutually recursive functions with
michael@0: // varying frame sizes.  These will recurse amongst themselves as
michael@0: // specified by |strP|, the directory string, and call
michael@0: // GetAndCheckStackTrace when the string becomes empty, passing it the
michael@0: // original value of the string.  This checks the result, printing
michael@0: // results on |aLUL|'s logging sink, and also returns a boolean
michael@0: // indicating whether or not the results are acceptable (correct).
michael@0: 
michael@0: #define DECL_TEST_FN(NAME) \
michael@0:   bool NAME(LUL* aLUL, const char* strPorig, const char* strP);
michael@0: 
michael@0: #define GEN_TEST_FN(NAME, FRAMESIZE) \
michael@0:   bool NAME(LUL* aLUL, const char* strPorig, const char* strP) { \
michael@0:     volatile char space[FRAMESIZE]; \
michael@0:     memset((char*)&space[0], 0, sizeof(space)); \
michael@0:     if (*strP == '\0') { \
michael@0:       /* We've come to the end of the director string. */ \
michael@0:       /* Take a stack snapshot. */ \
michael@0:       return GetAndCheckStackTrace(aLUL, strPorig); \
michael@0:     } else { \
michael@0:       /* Recurse onwards.  This is a bit subtle.  The obvious */ \
michael@0:       /* thing to do here is call onwards directly, from within the */ \
michael@0:       /* arms of the case statement.  That gives a problem in that */ \
michael@0:       /* there will be multiple return points inside each function when */ \
michael@0:       /* unwinding, so it will be difficult to check for consistency */ \
michael@0:       /* against the director string.  Instead, we make an indirect */ \
michael@0:       /* call, so as to guarantee that there is only one call site */ \
michael@0:       /* within each function.  This does assume that the compiler */ \
michael@0:       /* won't transform it back to the simple direct-call form. */ \
michael@0:       /* To discourage it from doing so, the call is bracketed with */ \
michael@0:       /* __asm__ __volatile__ sections so as to make it not-movable. */ \
michael@0:       bool (*nextFn)(LUL*, const char*, const char*) = NULL; \
michael@0:       switch (*strP) { \
michael@0:         case '1': nextFn = TestFn1; break; \
michael@0:         case '2': nextFn = TestFn2; break; \
michael@0:         case '3': nextFn = TestFn3; break; \
michael@0:         case '4': nextFn = TestFn4; break; \
michael@0:         case '5': nextFn = TestFn5; break; \
michael@0:         case '6': nextFn = TestFn6; break; \
michael@0:         case '7': nextFn = TestFn7; break; \
michael@0:         case '8': nextFn = TestFn8; break; \
michael@0:         default:  nextFn = TestFn8; break; \
michael@0:       } \
michael@0:       __asm__ __volatile__("":::"cc","memory"); \
michael@0:       bool passed = nextFn(aLUL, strPorig, strP+1); \
michael@0:       __asm__ __volatile__("":::"cc","memory"); \
michael@0:       return passed; \
michael@0:     } \
michael@0:   }
michael@0: 
michael@0: // The test functions are mutually recursive, so it is necessary to
michael@0: // declare them before defining them.
michael@0: DECL_TEST_FN(TestFn1)
michael@0: DECL_TEST_FN(TestFn2)
michael@0: DECL_TEST_FN(TestFn3)
michael@0: DECL_TEST_FN(TestFn4)
michael@0: DECL_TEST_FN(TestFn5)
michael@0: DECL_TEST_FN(TestFn6)
michael@0: DECL_TEST_FN(TestFn7)
michael@0: DECL_TEST_FN(TestFn8)
michael@0: 
michael@0: GEN_TEST_FN(TestFn1, 123)
michael@0: GEN_TEST_FN(TestFn2, 456)
michael@0: GEN_TEST_FN(TestFn3, 789)
michael@0: GEN_TEST_FN(TestFn4, 23)
michael@0: GEN_TEST_FN(TestFn5, 47)
michael@0: GEN_TEST_FN(TestFn6, 117)
michael@0: GEN_TEST_FN(TestFn7, 1)
michael@0: GEN_TEST_FN(TestFn8, 99)
michael@0: 
michael@0: 
michael@0: // This starts the test sequence going.  Call here to generate a
michael@0: // sequence of calls as directed by the string |dstring|.  The call
michael@0: // sequence will, from its innermost frame, finish by calling
michael@0: // GetAndCheckStackTrace() and passing it |dstring|.
michael@0: // GetAndCheckStackTrace() will unwind the stack, check consistency
michael@0: // of those results against |dstring|, and print a pass/fail message
michael@0: // to aLUL's logging sink.  It also updates the counters in *aNTests
michael@0: // and aNTestsPassed.
michael@0: __attribute__((noinline)) void
michael@0: TestUnw(/*OUT*/int* aNTests, /*OUT*/int*aNTestsPassed,
michael@0:         LUL* aLUL, const char* dstring)
michael@0: {
michael@0:   // Ensure that the stack has at least this much space on it.  This
michael@0:   // makes it safe to saw off the top LUL_UNIT_TEST_STACK_SIZE bytes
michael@0:   // and hand it to LUL.  Safe in the sense that no segfault can
michael@0:   // happen because the stack is at least this big.  This is all
michael@0:   // somewhat dubious in the sense that a sufficiently clever compiler
michael@0:   // (clang, for one) can figure out that space[] is unused and delete
michael@0:   // it from the frame.  Hence the somewhat elaborate hoop jumping to
michael@0:   // fill it up before the call and to at least appear to use the
michael@0:   // value afterwards.
michael@0:   int i;
michael@0:   volatile char space[LUL_UNIT_TEST_STACK_SIZE];
michael@0:   for (i = 0; i < LUL_UNIT_TEST_STACK_SIZE; i++) {
michael@0:     space[i] = (char)(i & 0x7F);
michael@0:   }
michael@0: 
michael@0:   // Really run the test.
michael@0:   bool passed = TestFn1(aLUL, dstring, dstring);
michael@0: 
michael@0:   // Appear to use space[], by visiting the value to compute some kind
michael@0:   // of checksum, and then (apparently) using the checksum.
michael@0:   int sum = 0;
michael@0:   for (i = 0; i < LUL_UNIT_TEST_STACK_SIZE; i++) {
michael@0:     // If this doesn't fool LLVM, I don't know what will.
michael@0:     sum += space[i] - 3*i;
michael@0:   }
michael@0:   __asm__ __volatile__("" : : "r"(sum));
michael@0: 
michael@0:   // Update the counters.
michael@0:   (*aNTests)++;
michael@0:   if (passed) {
michael@0:     (*aNTestsPassed)++;
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: RunLulUnitTests(/*OUT*/int* aNTests, /*OUT*/int*aNTestsPassed, LUL* aLUL)
michael@0: {
michael@0:   aLUL->mLog(":\n");
michael@0:   aLUL->mLog("LULUnitTest: BEGIN\n");
michael@0:   *aNTests = *aNTestsPassed = 0;
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL, "11111111");
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL, "11222211");
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL, "111222333");
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL, "1212121231212331212121212121212");
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL, "31415827271828325332173258");
michael@0:   TestUnw(aNTests, aNTestsPassed, aLUL,
michael@0:           "123456781122334455667788777777777777777777777");
michael@0:   aLUL->mLog("LULUnitTest: END\n");
michael@0:   aLUL->mLog(":\n");
michael@0: }
michael@0: 
michael@0: 
michael@0: } // namespace lul