The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

 /* vim: set ts=8 sts=2 et sw=2 tw=80: */

 /* This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #ifndef LulMainInt_h

 #define LulMainInt_h

 #include "LulPlatformMacros.h"

 #include <vector>

 #include "mozilla/Assertions.h"

 // This file is provides internal interface inside LUL.  If you are an

 // end-user of LUL, do not include it in your code.  The end-user

 // interface is in LulMain.h.

 namespace lul {

 ////////////////////////////////////////////////////////////////

 // DW_REG_ constants                                          //

 ////////////////////////////////////////////////////////////////

 // These are the Dwarf CFI register numbers, as (presumably) defined

 // in the ELF ABI supplements for each architecture.

 enum DW_REG_NUMBER {

   // No real register has this number.  It's convenient to be able to

   // treat the CFA (Canonical Frame Address) as "just another

   // register", though.

   DW_REG_CFA = -1,

 #if defined(LUL_ARCH_arm)

   // ARM registers

   DW_REG_ARM_R7  = 7,

   DW_REG_ARM_R11 = 11,

   DW_REG_ARM_R12 = 12,

   DW_REG_ARM_R13 = 13,

   DW_REG_ARM_R14 = 14,

   DW_REG_ARM_R15 = 15,

 #elif defined(LUL_ARCH_x64)

   // Because the X86 (32 bit) and AMD64 (64 bit) summarisers are

   // combined, a merged set of register constants is needed.

   DW_REG_INTEL_XBP = 6,

   DW_REG_INTEL_XSP = 7,

   DW_REG_INTEL_XIP = 16,

 #elif defined(LUL_ARCH_x86)

   DW_REG_INTEL_XBP = 5,

   DW_REG_INTEL_XSP = 4,

   DW_REG_INTEL_XIP = 8,

 #else

 # error "Unknown arch"

 #endif

 };

 ////////////////////////////////////////////////////////////////

 // LExpr                                                      //

 ////////////////////////////////////////////////////////////////

 // An expression -- very primitive.  Denotes either "register +

 // offset" or a dereferenced version of the same.  So as to allow

 // convenient handling of Dwarf-derived unwind info, the register may

 // also denote the CFA.  A large number of these need to be stored, so

 // we ensure it fits into 8 bytes.  See comment below on RuleSet to

 // see how expressions fit into the bigger picture.

 struct LExpr {

   // Denotes an expression with no value.

   LExpr()

     : mHow(UNKNOWN)

     , mReg(0)

     , mOffset(0)

   {}

   // Denotes any expressible expression.

   LExpr(uint8_t how, int16_t reg, int32_t offset)

     : mHow(how)

     , mReg(reg)

     , mOffset(offset)

   {}

   // Change the offset for an expression that references memory.

   LExpr add_delta(long delta)

   {

     MOZ_ASSERT(mHow == NODEREF);

     // If this is a non-debug build and the above assertion would have

     // failed, at least return LExpr() so that the machinery that uses

     // the resulting expression fails in a repeatable way.

     return (mHow == NODEREF) ? LExpr(mHow, mReg, mOffset+delta)

                              : LExpr(); // Gone bad

   }

   // Dereference an expression that denotes a memory address.

   LExpr deref()

   {

     MOZ_ASSERT(mHow == NODEREF);

     // Same rationale as for add_delta().

     return (mHow == NODEREF) ? LExpr(DEREF, mReg, mOffset)

                              : LExpr(); // Gone bad

   }

   // Representation of expressions.  If |mReg| is DW_REG_CFA (-1) then

   // it denotes the CFA.  All other allowed values for |mReg| are

   // nonnegative and are DW_REG_ values.

   enum { UNKNOWN=0, // This LExpr denotes no value.

          NODEREF,   // Value is  (mReg + mOffset).

          DEREF };   // Value is *(mReg + mOffset).

   uint8_t mHow;    // UNKNOWN, NODEREF or DEREF

   int16_t mReg;    // A DW_REG_ value

   int32_t mOffset; // 32-bit signed offset should be more than enough.

 };

 static_assert(sizeof(LExpr) <= 8, "LExpr size changed unexpectedly");

 ////////////////////////////////////////////////////////////////

 // RuleSet                                                    //

 ////////////////////////////////////////////////////////////////

 // This is platform-dependent.  For some address range, describes how

 // to recover the CFA and then how to recover the registers for the

 // previous frame.

 //

 // The set of LExprs contained in a given RuleSet describe a DAG which

 // says how to compute the caller's registers ("new registers") from

 // the callee's registers ("old registers").  The DAG can contain a

 // single internal node, which is the value of the CFA for the callee.

 // It would be possible to construct a DAG that omits the CFA, but

 // including it makes the summarisers simpler, and the Dwarf CFI spec

 // has the CFA as a central concept.

 //

 // For this to make sense, |mCfaExpr| can't have

 // |mReg| == DW_REG_CFA since we have no previous value for the CFA.

 // All of the other |Expr| fields can -- and usually do -- specify

 // |mReg| == DW_REG_CFA.

 //

 // With that in place, the unwind algorithm proceeds as follows.

 //

 // (0) Initially: we have values for the old registers, and a memory

 //     image.

 //

 // (1) Compute the CFA by evaluating |mCfaExpr|.  Add the computed

 //     value to the set of "old registers".

 //

 // (2) Compute values for the registers by evaluating all of the other

 //     |Expr| fields in the RuleSet.  These can depend on both the old

 //     register values and the just-computed CFA.

 //

 // If we are unwinding without computing a CFA, perhaps because the

 // RuleSets are derived from EXIDX instead of Dwarf, then

 // |mCfaExpr.mHow| will be LExpr::UNKNOWN, so the computed value will

 // be invalid -- that is, TaggedUWord() -- and so any attempt to use

 // that will result in the same value.  But that's OK because the

 // RuleSet would make no sense if depended on the CFA but specified no

 // way to compute it.

 //

 // A RuleSet is not allowed to cover zero address range.  Having zero

 // length would break binary searching in SecMaps and PriMaps.

 class RuleSet {

 public:

   RuleSet();

   void   Print(void(*aLog)(const char*));

   // Find the LExpr* for a given DW_REG_ value in this class.

   LExpr* ExprForRegno(DW_REG_NUMBER aRegno);

   uintptr_t mAddr;

   uintptr_t mLen;

   // How to compute the CFA.

   LExpr  mCfaExpr;

   // How to compute caller register values.  These may reference the

   // value defined by |mCfaExpr|.

 #if defined(LUL_ARCH_x64) || defined(LUL_ARCH_x86)

   LExpr  mXipExpr; // return address

   LExpr  mXspExpr;

   LExpr  mXbpExpr;

 #elif defined(LUL_ARCH_arm)

   LExpr  mR15expr; // return address

   LExpr  mR14expr;

   LExpr  mR13expr;

   LExpr  mR12expr;

   LExpr  mR11expr;

   LExpr  mR7expr;

 #else

 #   error "Unknown arch"

 #endif

 };

 ////////////////////////////////////////////////////////////////

 // SecMap                                                     //

 ////////////////////////////////////////////////////////////////

 // A SecMap may have zero address range, temporarily, whilst RuleSets

 // are being added to it.  But adding a zero-range SecMap to a PriMap

 // will make it impossible to maintain the total order of the PriMap

 // entries, and so that can't be allowed to happen.

 class SecMap {

 public:

   // These summarise the contained mRuleSets, in that they give

   // exactly the lowest and highest addresses that any of the entries

   // in this SecMap cover.  Hence invariants:

   //

   // mRuleSets is nonempty

   //    <=> mSummaryMinAddr <= mSummaryMaxAddr

   //        && mSummaryMinAddr == mRuleSets[0].mAddr

   //        && mSummaryMaxAddr == mRuleSets[#rulesets-1].mAddr

   //                              + mRuleSets[#rulesets-1].mLen - 1;

   //

   // This requires that no RuleSet has zero length.

   //

   // mRuleSets is empty

   //    <=> mSummaryMinAddr > mSummaryMaxAddr

   //

   // This doesn't constrain mSummaryMinAddr and mSummaryMaxAddr uniquely,

   // so let's use mSummaryMinAddr == 1 and mSummaryMaxAddr == 0 to denote

   // this case.

   SecMap(void(*aLog)(const char*));

   ~SecMap();

   // Binary search mRuleSets to find one that brackets |ia|, or nullptr

   // if none is found.  It's not allowable to do this until PrepareRuleSets

   // has been called first.

   RuleSet* FindRuleSet(uintptr_t ia);

   // Add a RuleSet to the collection.  The rule is copied in.  Calling

   // this makes the map non-searchable.

   void AddRuleSet(RuleSet* rs);

   // Prepare the map for searching.  Also, remove any rules for code

   // address ranges which don't fall inside [start, +len).  |len| may

   // not be zero.

   void PrepareRuleSets(uintptr_t start, size_t len);

   bool IsEmpty();

   size_t Size() { return mRuleSets.size(); }

   // The min and max addresses of the addresses in the contained

   // RuleSets.  See comment above for invariants.

   uintptr_t mSummaryMinAddr;

   uintptr_t mSummaryMaxAddr;

 private:

   // False whilst adding entries; true once it is safe to call FindRuleSet.

   // Transition (false->true) is caused by calling PrepareRuleSets().

   bool mUsable;

   // A vector of RuleSets, sorted, nonoverlapping (post Prepare()).

   std::vector<RuleSet> mRuleSets;

   // A logging sink, for debugging.

   void (*mLog)(const char*);

 };

 } // namespace lul

 #endif // ndef LulMainInt_h