DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (4a108e94d3e2)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
/* -*- 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.

  explicit 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