Bumping gaia.json for 1 gaia revision(s) a=gaia-bump

[gecko.git] / tools / profiler / LulDwarf.cpp

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */

// Copyright (c) 2010 Google Inc. All Rights Reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// CFI reader author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>

// Implementation of dwarf2reader::LineInfo, dwarf2reader::CompilationUnit,
// and dwarf2reader::CallFrameInfo. See dwarf2reader.h for details.

// This file is derived from the following files in
// toolkit/crashreporter/google-breakpad:
//   src/common/dwarf/bytereader.cc
//   src/common/dwarf/dwarf2reader.cc
//   src/common/dwarf_cfi_to_module.cc

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <map>
#include <stack>
#include <string>

#include "mozilla/Assertions.h"

#include "LulCommonExt.h"
#include "LulDwarfInt.h"

// Set this to 1 for verbose logging
#define DEBUG_DWARF 0


namespace lul {

using std::string;

ByteReader::ByteReader(enum Endianness endian)
    :offset_reader_(NULL), address_reader_(NULL), endian_(endian),
     address_size_(0), offset_size_(0),
     have_section_base_(), have_text_base_(), have_data_base_(),
     have_function_base_() { }

ByteReader::~ByteReader() { }

void ByteReader::SetOffsetSize(uint8 size) {
  offset_size_ = size;
  MOZ_ASSERT(size == 4 || size == 8);
  if (size == 4) {
    this->offset_reader_ = &ByteReader::ReadFourBytes;
  } else {
    this->offset_reader_ = &ByteReader::ReadEightBytes;
  }
}

void ByteReader::SetAddressSize(uint8 size) {
  address_size_ = size;
  MOZ_ASSERT(size == 4 || size == 8);
  if (size == 4) {
    this->address_reader_ = &ByteReader::ReadFourBytes;
  } else {
    this->address_reader_ = &ByteReader::ReadEightBytes;
  }
}

uint64 ByteReader::ReadInitialLength(const char* start, size_t* len) {
  const uint64 initial_length = ReadFourBytes(start);
  start += 4;

  // In DWARF2/3, if the initial length is all 1 bits, then the offset
  // size is 8 and we need to read the next 8 bytes for the real length.
  if (initial_length == 0xffffffff) {
    SetOffsetSize(8);
    *len = 12;
    return ReadOffset(start);
  } else {
    SetOffsetSize(4);
    *len = 4;
  }
  return initial_length;
}

bool ByteReader::ValidEncoding(DwarfPointerEncoding encoding) const {
  if (encoding == DW_EH_PE_omit) return true;
  if (encoding == DW_EH_PE_aligned) return true;
  if ((encoding & 0x7) > DW_EH_PE_udata8)
    return false;
  if ((encoding & 0x70) > DW_EH_PE_funcrel)
    return false;
  return true;
}

bool ByteReader::UsableEncoding(DwarfPointerEncoding encoding) const {
  switch (encoding & 0x70) {
    case DW_EH_PE_absptr:  return true;
    case DW_EH_PE_pcrel:   return have_section_base_;
    case DW_EH_PE_textrel: return have_text_base_;
    case DW_EH_PE_datarel: return have_data_base_;
    case DW_EH_PE_funcrel: return have_function_base_;
    default:               return false;
  }
}

uint64 ByteReader::ReadEncodedPointer(const char *buffer,
                                      DwarfPointerEncoding encoding,
                                      size_t *len) const {
  // UsableEncoding doesn't approve of DW_EH_PE_omit, so we shouldn't
  // see it here.
  MOZ_ASSERT(encoding != DW_EH_PE_omit);

  // The Linux Standards Base 4.0 does not make this clear, but the
  // GNU tools (gcc/unwind-pe.h; readelf/dwarf.c; gdb/dwarf2-frame.c)
  // agree that aligned pointers are always absolute, machine-sized,
  // machine-signed pointers.
  if (encoding == DW_EH_PE_aligned) {
    MOZ_ASSERT(have_section_base_);

    // We don't need to align BUFFER in *our* address space. Rather, we
    // need to find the next position in our buffer that would be aligned
    // when the .eh_frame section the buffer contains is loaded into the
    // program's memory. So align assuming that buffer_base_ gets loaded at
    // address section_base_, where section_base_ itself may or may not be
    // aligned.

    // First, find the offset to START from the closest prior aligned
    // address.
    uint64 skew = section_base_ & (AddressSize() - 1);
    // Now find the offset from that aligned address to buffer.
    uint64 offset = skew + (buffer - buffer_base_);
    // Round up to the next boundary.
    uint64 aligned = (offset + AddressSize() - 1) & -AddressSize();
    // Convert back to a pointer.
    const char *aligned_buffer = buffer_base_ + (aligned - skew);
    // Finally, store the length and actually fetch the pointer.
    *len = aligned_buffer - buffer + AddressSize();
    return ReadAddress(aligned_buffer);
  }

  // Extract the value first, ignoring whether it's a pointer or an
  // offset relative to some base.
  uint64 offset;
  switch (encoding & 0x0f) {
    case DW_EH_PE_absptr:
      // DW_EH_PE_absptr is weird, as it is used as a meaningful value for
      // both the high and low nybble of encoding bytes. When it appears in
      // the high nybble, it means that the pointer is absolute, not an
      // offset from some base address. When it appears in the low nybble,
      // as here, it means that the pointer is stored as a normal
      // machine-sized and machine-signed address. A low nybble of
      // DW_EH_PE_absptr does not imply that the pointer is absolute; it is
      // correct for us to treat the value as an offset from a base address
      // if the upper nybble is not DW_EH_PE_absptr.
      offset = ReadAddress(buffer);
      *len = AddressSize();
      break;

    case DW_EH_PE_uleb128:
      offset = ReadUnsignedLEB128(buffer, len);
      break;

    case DW_EH_PE_udata2:
      offset = ReadTwoBytes(buffer);
      *len = 2;
      break;

    case DW_EH_PE_udata4:
      offset = ReadFourBytes(buffer);
      *len = 4;
      break;

    case DW_EH_PE_udata8:
      offset = ReadEightBytes(buffer);
      *len = 8;
      break;

    case DW_EH_PE_sleb128:
      offset = ReadSignedLEB128(buffer, len);
      break;

    case DW_EH_PE_sdata2:
      offset = ReadTwoBytes(buffer);
      // Sign-extend from 16 bits.
      offset = (offset ^ 0x8000) - 0x8000;
      *len = 2;
      break;

    case DW_EH_PE_sdata4:
      offset = ReadFourBytes(buffer);
      // Sign-extend from 32 bits.
      offset = (offset ^ 0x80000000ULL) - 0x80000000ULL;
      *len = 4;
      break;

    case DW_EH_PE_sdata8:
      // No need to sign-extend; this is the full width of our type.
      offset = ReadEightBytes(buffer);
      *len = 8;
      break;

    default:
      abort();
  }

  // Find the appropriate base address.
  uint64 base;
  switch (encoding & 0x70) {
    case DW_EH_PE_absptr:
      base = 0;
      break;

    case DW_EH_PE_pcrel:
      MOZ_ASSERT(have_section_base_);
      base = section_base_ + (buffer - buffer_base_);
      break;

    case DW_EH_PE_textrel:
      MOZ_ASSERT(have_text_base_);
      base = text_base_;
      break;

    case DW_EH_PE_datarel:
      MOZ_ASSERT(have_data_base_);
      base = data_base_;
      break;

    case DW_EH_PE_funcrel:
      MOZ_ASSERT(have_function_base_);
      base = function_base_;
      break;

    default:
      abort();
  }

  uint64 pointer = base + offset;

  // Remove inappropriate upper bits.
  if (AddressSize() == 4)
    pointer = pointer & 0xffffffff;
  else
    MOZ_ASSERT(AddressSize() == sizeof(uint64));

  return pointer;
}


// A DWARF rule for recovering the address or value of a register, or
// computing the canonical frame address. There is one subclass of this for
// each '*Rule' member function in CallFrameInfo::Handler.
//
// It's annoying that we have to handle Rules using pointers (because
// the concrete instances can have an arbitrary size). They're small,
// so it would be much nicer if we could just handle them by value
// instead of fretting about ownership and destruction.
//
// It seems like all these could simply be instances of std::tr1::bind,
// except that we need instances to be EqualityComparable, too.
//
// This could logically be nested within State, but then the qualified names
// get horrendous.
class CallFrameInfo::Rule {
 public:
  virtual ~Rule() { }

  // Tell HANDLER that, at ADDRESS in the program, REGISTER can be
  // recovered using this rule. If REGISTER is kCFARegister, then this rule
  // describes how to compute the canonical frame address. Return what the
  // HANDLER member function returned.
  virtual bool Handle(Handler *handler,
                      uint64 address, int register) const = 0;

  // Equality on rules. We use these to decide which rules we need
  // to report after a DW_CFA_restore_state instruction.
  virtual bool operator==(const Rule &rhs) const = 0;

  bool operator!=(const Rule &rhs) const { return ! (*this == rhs); }

  // Return a pointer to a copy of this rule.
  virtual Rule *Copy() const = 0;

  // If this is a base+offset rule, change its base register to REG.
  // Otherwise, do nothing. (Ugly, but required for DW_CFA_def_cfa_register.)
  virtual void SetBaseRegister(unsigned reg) { }

  // If this is a base+offset rule, change its offset to OFFSET. Otherwise,
  // do nothing. (Ugly, but required for DW_CFA_def_cfa_offset.)
  virtual void SetOffset(long long offset) { }

  // A RTTI workaround, to make it possible to implement equality
  // comparisons on classes derived from this one.
  enum CFIRTag {
    CFIR_UNDEFINED_RULE,
    CFIR_SAME_VALUE_RULE,
    CFIR_OFFSET_RULE,
    CFIR_VAL_OFFSET_RULE,
    CFIR_REGISTER_RULE,
    CFIR_EXPRESSION_RULE,
    CFIR_VAL_EXPRESSION_RULE
  };

  // Produce the tag that identifies the child class of this object.
  virtual CFIRTag getTag() const = 0;
};

// Rule: the value the register had in the caller cannot be recovered.
class CallFrameInfo::UndefinedRule: public CallFrameInfo::Rule {
 public:
  UndefinedRule() { }
  ~UndefinedRule() { }
  CFIRTag getTag() const { return CFIR_UNDEFINED_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->UndefinedRule(address, reg);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_UNDEFINED_RULE) return false;
    return true;
  }
  Rule *Copy() const { return new UndefinedRule(*this); }
};

// Rule: the register's value is the same as that it had in the caller.
class CallFrameInfo::SameValueRule: public CallFrameInfo::Rule {
 public:
  SameValueRule() { }
  ~SameValueRule() { }
  CFIRTag getTag() const { return CFIR_SAME_VALUE_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->SameValueRule(address, reg);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_SAME_VALUE_RULE) return false;
    return true;
  }
  Rule *Copy() const { return new SameValueRule(*this); }
};

// Rule: the register is saved at OFFSET from BASE_REGISTER.  BASE_REGISTER
// may be CallFrameInfo::Handler::kCFARegister.
class CallFrameInfo::OffsetRule: public CallFrameInfo::Rule {
 public:
  OffsetRule(int base_register, long offset)
      : base_register_(base_register), offset_(offset) { }
  ~OffsetRule() { }
  CFIRTag getTag() const { return CFIR_OFFSET_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->OffsetRule(address, reg, base_register_, offset_);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_OFFSET_RULE) return false;
    const OffsetRule *our_rhs = static_cast<const OffsetRule *>(&rhs);
    return (base_register_ == our_rhs->base_register_ &&
            offset_ == our_rhs->offset_);
  }
  Rule *Copy() const { return new OffsetRule(*this); }
  // We don't actually need SetBaseRegister or SetOffset here, since they
  // are only ever applied to CFA rules, for DW_CFA_def_cfa_offset, and it
  // doesn't make sense to use OffsetRule for computing the CFA: it
  // computes the address at which a register is saved, not a value.
 private:
  int base_register_;
  long offset_;
};

// Rule: the value the register had in the caller is the value of
// BASE_REGISTER plus offset. BASE_REGISTER may be
// CallFrameInfo::Handler::kCFARegister.
class CallFrameInfo::ValOffsetRule: public CallFrameInfo::Rule {
 public:
  ValOffsetRule(int base_register, long offset)
      : base_register_(base_register), offset_(offset) { }
  ~ValOffsetRule() { }
  CFIRTag getTag() const { return CFIR_VAL_OFFSET_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->ValOffsetRule(address, reg, base_register_, offset_);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_VAL_OFFSET_RULE) return false;
    const ValOffsetRule *our_rhs = static_cast<const ValOffsetRule *>(&rhs);
    return (base_register_ == our_rhs->base_register_ &&
            offset_ == our_rhs->offset_);
  }
  Rule *Copy() const { return new ValOffsetRule(*this); }
  void SetBaseRegister(unsigned reg) { base_register_ = reg; }
  void SetOffset(long long offset) { offset_ = offset; }
 private:
  int base_register_;
  long offset_;
};

// Rule: the register has been saved in another register REGISTER_NUMBER_.
class CallFrameInfo::RegisterRule: public CallFrameInfo::Rule {
 public:
  explicit RegisterRule(int register_number)
      : register_number_(register_number) { }
  ~RegisterRule() { }
  CFIRTag getTag() const { return CFIR_REGISTER_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->RegisterRule(address, reg, register_number_);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_REGISTER_RULE) return false;
    const RegisterRule *our_rhs = static_cast<const RegisterRule *>(&rhs);
    return (register_number_ == our_rhs->register_number_);
  }
  Rule *Copy() const { return new RegisterRule(*this); }
 private:
  int register_number_;
};

// Rule: EXPRESSION evaluates to the address at which the register is saved.
class CallFrameInfo::ExpressionRule: public CallFrameInfo::Rule {
 public:
  explicit ExpressionRule(const string &expression)
      : expression_(expression) { }
  ~ExpressionRule() { }
  CFIRTag getTag() const { return CFIR_EXPRESSION_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->ExpressionRule(address, reg, expression_);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_EXPRESSION_RULE) return false;
    const ExpressionRule *our_rhs = static_cast<const ExpressionRule *>(&rhs);
    return (expression_ == our_rhs->expression_);
  }
  Rule *Copy() const { return new ExpressionRule(*this); }
 private:
  string expression_;
};

// Rule: EXPRESSION evaluates to the previous value of the register.
class CallFrameInfo::ValExpressionRule: public CallFrameInfo::Rule {
 public:
  explicit ValExpressionRule(const string &expression)
      : expression_(expression) { }
  ~ValExpressionRule() { }
  CFIRTag getTag() const { return CFIR_VAL_EXPRESSION_RULE; }
  bool Handle(Handler *handler, uint64 address, int reg) const {
    return handler->ValExpressionRule(address, reg, expression_);
  }
  bool operator==(const Rule &rhs) const {
    if (rhs.getTag() != CFIR_VAL_EXPRESSION_RULE) return false;
    const ValExpressionRule *our_rhs =
        static_cast<const ValExpressionRule *>(&rhs);
    return (expression_ == our_rhs->expression_);
  }
  Rule *Copy() const { return new ValExpressionRule(*this); }
 private:
  string expression_;
};

// A map from register numbers to rules.
class CallFrameInfo::RuleMap {
 public:
  RuleMap() : cfa_rule_(NULL) { }
  RuleMap(const RuleMap &rhs) : cfa_rule_(NULL) { *this = rhs; }
  ~RuleMap() { Clear(); }

  RuleMap &operator=(const RuleMap &rhs);

  // Set the rule for computing the CFA to RULE. Take ownership of RULE.
  void SetCFARule(Rule *rule) { delete cfa_rule_; cfa_rule_ = rule; }

  // Return the current CFA rule. Unlike RegisterRule, this RuleMap retains
  // ownership of the rule. We use this for DW_CFA_def_cfa_offset and
  // DW_CFA_def_cfa_register, and for detecting references to the CFA before
  // a rule for it has been established.
  Rule *CFARule() const { return cfa_rule_; }

  // Return the rule for REG, or NULL if there is none. The caller takes
  // ownership of the result.
  Rule *RegisterRule(int reg) const;

  // Set the rule for computing REG to RULE. Take ownership of RULE.
  void SetRegisterRule(int reg, Rule *rule);

  // Make all the appropriate calls to HANDLER as if we were changing from
  // this RuleMap to NEW_RULES at ADDRESS. We use this to implement
  // DW_CFA_restore_state, where lots of rules can change simultaneously.
  // Return true if all handlers returned true; otherwise, return false.
  bool HandleTransitionTo(Handler *handler, uint64 address,
                          const RuleMap &new_rules) const;

 private:
  // A map from register numbers to Rules.
  typedef std::map<int, Rule *> RuleByNumber;

  // Remove all register rules and clear cfa_rule_.
  void Clear();

  // The rule for computing the canonical frame address. This RuleMap owns
  // this rule.
  Rule *cfa_rule_;

  // A map from register numbers to postfix expressions to recover
  // their values. This RuleMap owns the Rules the map refers to.
  RuleByNumber registers_;
};

CallFrameInfo::RuleMap &CallFrameInfo::RuleMap::operator=(const RuleMap &rhs) {
  Clear();
  // Since each map owns the rules it refers to, assignment must copy them.
  if (rhs.cfa_rule_) cfa_rule_ = rhs.cfa_rule_->Copy();
  for (RuleByNumber::const_iterator it = rhs.registers_.begin();
       it != rhs.registers_.end(); it++)
    registers_[it->first] = it->second->Copy();
  return *this;
}

CallFrameInfo::Rule *CallFrameInfo::RuleMap::RegisterRule(int reg) const {
  MOZ_ASSERT(reg != Handler::kCFARegister);
  RuleByNumber::const_iterator it = registers_.find(reg);
  if (it != registers_.end())
    return it->second->Copy();
  else
    return NULL;
}

void CallFrameInfo::RuleMap::SetRegisterRule(int reg, Rule *rule) {
  MOZ_ASSERT(reg != Handler::kCFARegister);
  MOZ_ASSERT(rule);
  Rule **slot = &registers_[reg];
  delete *slot;
  *slot = rule;
}

bool CallFrameInfo::RuleMap::HandleTransitionTo(
    Handler *handler,
    uint64 address,
    const RuleMap &new_rules) const {
  // Transition from cfa_rule_ to new_rules.cfa_rule_.
  if (cfa_rule_ && new_rules.cfa_rule_) {
    if (*cfa_rule_ != *new_rules.cfa_rule_ &&
        !new_rules.cfa_rule_->Handle(handler, address, Handler::kCFARegister))
      return false;
  } else if (cfa_rule_) {
    // this RuleMap has a CFA rule but new_rules doesn't.
    // CallFrameInfo::Handler has no way to handle this --- and shouldn't;
    // it's garbage input. The instruction interpreter should have
    // detected this and warned, so take no action here.
  } else if (new_rules.cfa_rule_) {
    // This shouldn't be possible: NEW_RULES is some prior state, and
    // there's no way to remove entries.
    MOZ_ASSERT(0);
  } else {
    // Both CFA rules are empty.  No action needed.
  }

  // Traverse the two maps in order by register number, and report
  // whatever differences we find.
  RuleByNumber::const_iterator old_it = registers_.begin();
  RuleByNumber::const_iterator new_it = new_rules.registers_.begin();
  while (old_it != registers_.end() && new_it != new_rules.registers_.end()) {
    if (old_it->first < new_it->first) {
      // This RuleMap has an entry for old_it->first, but NEW_RULES
      // doesn't.
      //
      // This isn't really the right thing to do, but since CFI generally
      // only mentions callee-saves registers, and GCC's convention for
      // callee-saves registers is that they are unchanged, it's a good
      // approximation.
      if (!handler->SameValueRule(address, old_it->first))
        return false;
      old_it++;
    } else if (old_it->first > new_it->first) {
      // NEW_RULES has entry for new_it->first, but this RuleMap
      // doesn't. This shouldn't be possible: NEW_RULES is some prior
      // state, and there's no way to remove entries.
      MOZ_ASSERT(0);
    } else {
      // Both maps have an entry for this register. Report the new
      // rule if it is different.
      if (*old_it->second != *new_it->second &&
          !new_it->second->Handle(handler, address, new_it->first))
        return false;
      new_it++, old_it++;
    }
  }
  // Finish off entries from this RuleMap with no counterparts in new_rules.
  while (old_it != registers_.end()) {
    if (!handler->SameValueRule(address, old_it->first))
      return false;
    old_it++;
  }
  // Since we only make transitions from a rule set to some previously
  // saved rule set, and we can only add rules to the map, NEW_RULES
  // must have fewer rules than *this.
  MOZ_ASSERT(new_it == new_rules.registers_.end());

  return true;
}

// Remove all register rules and clear cfa_rule_.
void CallFrameInfo::RuleMap::Clear() {
  delete cfa_rule_;
  cfa_rule_ = NULL;
  for (RuleByNumber::iterator it = registers_.begin();
       it != registers_.end(); it++)
    delete it->second;
  registers_.clear();
}

// The state of the call frame information interpreter as it processes
// instructions from a CIE and FDE.
class CallFrameInfo::State {
 public:
  // Create a call frame information interpreter state with the given
  // reporter, reader, handler, and initial call frame info address.
  State(ByteReader *reader, Handler *handler, Reporter *reporter,
        uint64 address)
      : reader_(reader), handler_(handler), reporter_(reporter),
        address_(address), entry_(NULL), cursor_(NULL),
        saved_rules_(NULL) { }

  ~State() {
    if (saved_rules_)
      delete saved_rules_;
  }

  // Interpret instructions from CIE, save the resulting rule set for
  // DW_CFA_restore instructions, and return true. On error, report
  // the problem to reporter_ and return false.
  bool InterpretCIE(const CIE &cie);

  // Interpret instructions from FDE, and return true. On error,
  // report the problem to reporter_ and return false.
  bool InterpretFDE(const FDE &fde);

 private:
  // The operands of a CFI instruction, for ParseOperands.
  struct Operands {
    unsigned register_number;  // A register number.
    uint64 offset;             // An offset or address.
    long signed_offset;        // A signed offset.
    string expression;         // A DWARF expression.
  };

  // Parse CFI instruction operands from STATE's instruction stream as
  // described by FORMAT. On success, populate OPERANDS with the
  // results, and return true. On failure, report the problem and
  // return false.
  //
  // Each character of FORMAT should be one of the following:
  //
  //   'r'  unsigned LEB128 register number (OPERANDS->register_number)
  //   'o'  unsigned LEB128 offset          (OPERANDS->offset)
  //   's'  signed LEB128 offset            (OPERANDS->signed_offset)
  //   'a'  machine-size address            (OPERANDS->offset)
  //        (If the CIE has a 'z' augmentation string, 'a' uses the
  //        encoding specified by the 'R' argument.)
  //   '1'  a one-byte offset               (OPERANDS->offset)
  //   '2'  a two-byte offset               (OPERANDS->offset)
  //   '4'  a four-byte offset              (OPERANDS->offset)
  //   '8'  an eight-byte offset            (OPERANDS->offset)
  //   'e'  a DW_FORM_block holding a       (OPERANDS->expression)
  //        DWARF expression
  bool ParseOperands(const char *format, Operands *operands);

  // Interpret one CFI instruction from STATE's instruction stream, update
  // STATE, report any rule changes to handler_, and return true. On
  // failure, report the problem and return false.
  bool DoInstruction();

  // The following Do* member functions are subroutines of DoInstruction,
  // factoring out the actual work of operations that have several
  // different encodings.

  // Set the CFA rule to be the value of BASE_REGISTER plus OFFSET, and
  // return true. On failure, report and return false. (Used for
  // DW_CFA_def_cfa and DW_CFA_def_cfa_sf.)
  bool DoDefCFA(unsigned base_register, long offset);

  // Change the offset of the CFA rule to OFFSET, and return true. On
  // failure, report and return false. (Subroutine for
  // DW_CFA_def_cfa_offset and DW_CFA_def_cfa_offset_sf.)
  bool DoDefCFAOffset(long offset);

  // Specify that REG can be recovered using RULE, and return true. On
  // failure, report and return false.
  bool DoRule(unsigned reg, Rule *rule);

  // Specify that REG can be found at OFFSET from the CFA, and return true.
  // On failure, report and return false. (Subroutine for DW_CFA_offset,
  // DW_CFA_offset_extended, and DW_CFA_offset_extended_sf.)
  bool DoOffset(unsigned reg, long offset);

  // Specify that the caller's value for REG is the CFA plus OFFSET,
  // and return true. On failure, report and return false. (Subroutine
  // for DW_CFA_val_offset and DW_CFA_val_offset_sf.)
  bool DoValOffset(unsigned reg, long offset);

  // Restore REG to the rule established in the CIE, and return true. On
  // failure, report and return false. (Subroutine for DW_CFA_restore and
  // DW_CFA_restore_extended.)
  bool DoRestore(unsigned reg);

  // Return the section offset of the instruction at cursor. For use
  // in error messages.
  uint64 CursorOffset() { return entry_->offset + (cursor_ - entry_->start); }

  // Report that entry_ is incomplete, and return false. For brevity.
  bool ReportIncomplete() {
    reporter_->Incomplete(entry_->offset, entry_->kind);
    return false;
  }

  // For reading multi-byte values with the appropriate endianness.
  ByteReader *reader_;

  // The handler to which we should report the data we find.
  Handler *handler_;

  // For reporting problems in the info we're parsing.
  Reporter *reporter_;

  // The code address to which the next instruction in the stream applies.
  uint64 address_;

  // The entry whose instructions we are currently processing. This is
  // first a CIE, and then an FDE.
  const Entry *entry_;

  // The next instruction to process.
  const char *cursor_;

  // The current set of rules.
  RuleMap rules_;

  // The set of rules established by the CIE, used by DW_CFA_restore
  // and DW_CFA_restore_extended. We set this after interpreting the
  // CIE's instructions.
  RuleMap cie_rules_;

  // A stack of saved states, for DW_CFA_remember_state and
  // DW_CFA_restore_state.
  std::stack<RuleMap>* saved_rules_;
};

bool CallFrameInfo::State::InterpretCIE(const CIE &cie) {
  entry_ = &cie;
  cursor_ = entry_->instructions;
  while (cursor_ < entry_->end)
    if (!DoInstruction())
      return false;
  // Note the rules established by the CIE, for use by DW_CFA_restore
  // and DW_CFA_restore_extended.
  cie_rules_ = rules_;
  return true;
}

bool CallFrameInfo::State::InterpretFDE(const FDE &fde) {
  entry_ = &fde;
  cursor_ = entry_->instructions;
  while (cursor_ < entry_->end)
    if (!DoInstruction())
      return false;
  return true;
}

bool CallFrameInfo::State::ParseOperands(const char *format,
                                         Operands *operands) {
  size_t len;
  const char *operand;

  for (operand = format; *operand; operand++) {
    size_t bytes_left = entry_->end - cursor_;
    switch (*operand) {
      case 'r':
        operands->register_number = reader_->ReadUnsignedLEB128(cursor_, &len);
        if (len > bytes_left) return ReportIncomplete();
        cursor_ += len;
        break;

      case 'o':
        operands->offset = reader_->ReadUnsignedLEB128(cursor_, &len);
        if (len > bytes_left) return ReportIncomplete();
        cursor_ += len;
        break;

      case 's':
        operands->signed_offset = reader_->ReadSignedLEB128(cursor_, &len);
        if (len > bytes_left) return ReportIncomplete();
        cursor_ += len;
        break;

      case 'a':
        operands->offset =
          reader_->ReadEncodedPointer(cursor_, entry_->cie->pointer_encoding,
                                      &len);
        if (len > bytes_left) return ReportIncomplete();
        cursor_ += len;
        break;

      case '1':
        if (1 > bytes_left) return ReportIncomplete();
        operands->offset = static_cast<unsigned char>(*cursor_++);
        break;

      case '2':
        if (2 > bytes_left) return ReportIncomplete();
        operands->offset = reader_->ReadTwoBytes(cursor_);
        cursor_ += 2;
        break;

      case '4':
        if (4 > bytes_left) return ReportIncomplete();
        operands->offset = reader_->ReadFourBytes(cursor_);
        cursor_ += 4;
        break;

      case '8':
        if (8 > bytes_left) return ReportIncomplete();
        operands->offset = reader_->ReadEightBytes(cursor_);
        cursor_ += 8;
        break;

      case 'e': {
        size_t expression_length = reader_->ReadUnsignedLEB128(cursor_, &len);
        if (len > bytes_left || expression_length > bytes_left - len)
          return ReportIncomplete();
        cursor_ += len;
        operands->expression = string(cursor_, expression_length);
        cursor_ += expression_length;
        break;
      }

      default:
        MOZ_ASSERT(0);
    }
  }

  return true;
}

bool CallFrameInfo::State::DoInstruction() {
  CIE *cie = entry_->cie;
  Operands ops;

  // Our entry's kind should have been set by now.
  MOZ_ASSERT(entry_->kind != kUnknown);

  // We shouldn't have been invoked unless there were more
  // instructions to parse.
  MOZ_ASSERT(cursor_ < entry_->end);

  unsigned opcode = *cursor_++;
  if ((opcode & 0xc0) != 0) {
    switch (opcode & 0xc0) {
      // Advance the address.
      case DW_CFA_advance_loc: {
        size_t code_offset = opcode & 0x3f;
        address_ += code_offset * cie->code_alignment_factor;
        break;
      }

      // Find a register at an offset from the CFA.
      case DW_CFA_offset:
        if (!ParseOperands("o", &ops) ||
            !DoOffset(opcode & 0x3f, ops.offset * cie->data_alignment_factor))
          return false;
        break;

      // Restore the rule established for a register by the CIE.
      case DW_CFA_restore:
        if (!DoRestore(opcode & 0x3f)) return false;
        break;

      // The 'if' above should have excluded this possibility.
      default:
        MOZ_ASSERT(0);
    }

    // Return here, so the big switch below won't be indented.
    return true;
  }

  switch (opcode) {
    // Set the address.
    case DW_CFA_set_loc:
      if (!ParseOperands("a", &ops)) return false;
      address_ = ops.offset;
      break;

    // Advance the address.
    case DW_CFA_advance_loc1:
      if (!ParseOperands("1", &ops)) return false;
      address_ += ops.offset * cie->code_alignment_factor;
      break;

    // Advance the address.
    case DW_CFA_advance_loc2:
      if (!ParseOperands("2", &ops)) return false;
      address_ += ops.offset * cie->code_alignment_factor;
      break;

    // Advance the address.
    case DW_CFA_advance_loc4:
      if (!ParseOperands("4", &ops)) return false;
      address_ += ops.offset * cie->code_alignment_factor;
      break;

    // Advance the address.
    case DW_CFA_MIPS_advance_loc8:
      if (!ParseOperands("8", &ops)) return false;
      address_ += ops.offset * cie->code_alignment_factor;
      break;

    // Compute the CFA by adding an offset to a register.
    case DW_CFA_def_cfa:
      if (!ParseOperands("ro", &ops) ||
          !DoDefCFA(ops.register_number, ops.offset))
        return false;
      break;

    // Compute the CFA by adding an offset to a register.
    case DW_CFA_def_cfa_sf:
      if (!ParseOperands("rs", &ops) ||
          !DoDefCFA(ops.register_number,
                    ops.signed_offset * cie->data_alignment_factor))
        return false;
      break;

    // Change the base register used to compute the CFA.
    case DW_CFA_def_cfa_register: {
      Rule *cfa_rule = rules_.CFARule();
      if (!cfa_rule) {
        reporter_->NoCFARule(entry_->offset, entry_->kind, CursorOffset());
        return false;
      }
      if (!ParseOperands("r", &ops)) return false;
      cfa_rule->SetBaseRegister(ops.register_number);
      if (!cfa_rule->Handle(handler_, address_, Handler::kCFARegister))
        return false;
      break;
    }

    // Change the offset used to compute the CFA.
    case DW_CFA_def_cfa_offset:
      if (!ParseOperands("o", &ops) ||
          !DoDefCFAOffset(ops.offset))
        return false;
      break;

    // Change the offset used to compute the CFA.
    case DW_CFA_def_cfa_offset_sf:
      if (!ParseOperands("s", &ops) ||
          !DoDefCFAOffset(ops.signed_offset * cie->data_alignment_factor))
        return false;
      break;

    // Specify an expression whose value is the CFA.
    case DW_CFA_def_cfa_expression: {
      if (!ParseOperands("e", &ops))
        return false;
      Rule *rule = new ValExpressionRule(ops.expression);
      rules_.SetCFARule(rule);
      if (!rule->Handle(handler_, address_, Handler::kCFARegister))
        return false;
      break;
    }

    // The register's value cannot be recovered.
    case DW_CFA_undefined: {
      if (!ParseOperands("r", &ops) ||
          !DoRule(ops.register_number, new UndefinedRule()))
        return false;
      break;
    }

    // The register's value is unchanged from its value in the caller.
    case DW_CFA_same_value: {
      if (!ParseOperands("r", &ops) ||
          !DoRule(ops.register_number, new SameValueRule()))
        return false;
      break;
    }

    // Find a register at an offset from the CFA.
    case DW_CFA_offset_extended:
      if (!ParseOperands("ro", &ops) ||
          !DoOffset(ops.register_number,
                    ops.offset * cie->data_alignment_factor))
        return false;
      break;

    // The register is saved at an offset from the CFA.
    case DW_CFA_offset_extended_sf:
      if (!ParseOperands("rs", &ops) ||
          !DoOffset(ops.register_number,
                    ops.signed_offset * cie->data_alignment_factor))
        return false;
      break;

    // The register is saved at an offset from the CFA.
    case DW_CFA_GNU_negative_offset_extended:
      if (!ParseOperands("ro", &ops) ||
          !DoOffset(ops.register_number,
                    -ops.offset * cie->data_alignment_factor))
        return false;
      break;

    // The register's value is the sum of the CFA plus an offset.
    case DW_CFA_val_offset:
      if (!ParseOperands("ro", &ops) ||
          !DoValOffset(ops.register_number,
                       ops.offset * cie->data_alignment_factor))
        return false;
      break;

    // The register's value is the sum of the CFA plus an offset.
    case DW_CFA_val_offset_sf:
      if (!ParseOperands("rs", &ops) ||
          !DoValOffset(ops.register_number,
                       ops.signed_offset * cie->data_alignment_factor))
        return false;
      break;

    // The register has been saved in another register.
    case DW_CFA_register: {
      if (!ParseOperands("ro", &ops) ||
          !DoRule(ops.register_number, new RegisterRule(ops.offset)))
        return false;
      break;
    }

    // An expression yields the address at which the register is saved.
    case DW_CFA_expression: {
      if (!ParseOperands("re", &ops) ||
          !DoRule(ops.register_number, new ExpressionRule(ops.expression)))
        return false;
      break;
    }

    // An expression yields the caller's value for the register.
    case DW_CFA_val_expression: {
      if (!ParseOperands("re", &ops) ||
          !DoRule(ops.register_number, new ValExpressionRule(ops.expression)))
        return false;
      break;
    }

    // Restore the rule established for a register by the CIE.
    case DW_CFA_restore_extended:
      if (!ParseOperands("r", &ops) ||
          !DoRestore( ops.register_number))
        return false;
      break;

    // Save the current set of rules on a stack.
    case DW_CFA_remember_state:
      if (!saved_rules_) {
        saved_rules_ = new std::stack<RuleMap>();
      }
      saved_rules_->push(rules_);
      break;

    // Pop the current set of rules off the stack.
    case DW_CFA_restore_state: {
      if (!saved_rules_ || saved_rules_->empty()) {
        reporter_->EmptyStateStack(entry_->offset, entry_->kind,
                                   CursorOffset());
        return false;
      }
      const RuleMap &new_rules = saved_rules_->top();
      if (rules_.CFARule() && !new_rules.CFARule()) {
        reporter_->ClearingCFARule(entry_->offset, entry_->kind,
                                   CursorOffset());
        return false;
      }
      rules_.HandleTransitionTo(handler_, address_, new_rules);
      rules_ = new_rules;
      saved_rules_->pop();
      break;
    }

    // No operation.  (Padding instruction.)
    case DW_CFA_nop:
      break;

    // A SPARC register window save: Registers 8 through 15 (%o0-%o7)
    // are saved in registers 24 through 31 (%i0-%i7), and registers
    // 16 through 31 (%l0-%l7 and %i0-%i7) are saved at CFA offsets
    // (0-15 * the register size). The register numbers must be
    // hard-coded. A GNU extension, and not a pretty one.
    case DW_CFA_GNU_window_save: {
      // Save %o0-%o7 in %i0-%i7.
      for (int i = 8; i < 16; i++)
        if (!DoRule(i, new RegisterRule(i + 16)))
          return false;
      // Save %l0-%l7 and %i0-%i7 at the CFA.
      for (int i = 16; i < 32; i++)
        // Assume that the byte reader's address size is the same as
        // the architecture's register size. !@#%*^ hilarious.
        if (!DoRule(i, new OffsetRule(Handler::kCFARegister,
                                      (i - 16) * reader_->AddressSize())))
          return false;
      break;
    }

    // I'm not sure what this is. GDB doesn't use it for unwinding.
    case DW_CFA_GNU_args_size:
      if (!ParseOperands("o", &ops)) return false;
      break;

    // An opcode we don't recognize.
    default: {
      reporter_->BadInstruction(entry_->offset, entry_->kind, CursorOffset());
      return false;
    }
  }

  return true;
}

bool CallFrameInfo::State::DoDefCFA(unsigned base_register, long offset) {
  Rule *rule = new ValOffsetRule(base_register, offset);
  rules_.SetCFARule(rule);
  return rule->Handle(handler_, address_, Handler::kCFARegister);
}

bool CallFrameInfo::State::DoDefCFAOffset(long offset) {
  Rule *cfa_rule = rules_.CFARule();
  if (!cfa_rule) {
    reporter_->NoCFARule(entry_->offset, entry_->kind, CursorOffset());
    return false;
  }
  cfa_rule->SetOffset(offset);
  return cfa_rule->Handle(handler_, address_, Handler::kCFARegister);
}

bool CallFrameInfo::State::DoRule(unsigned reg, Rule *rule) {
  rules_.SetRegisterRule(reg, rule);
  return rule->Handle(handler_, address_, reg);
}

bool CallFrameInfo::State::DoOffset(unsigned reg, long offset) {
  if (!rules_.CFARule()) {
    reporter_->NoCFARule(entry_->offset, entry_->kind, CursorOffset());
    return false;
  }
  return DoRule(reg,
                new OffsetRule(Handler::kCFARegister, offset));
}

bool CallFrameInfo::State::DoValOffset(unsigned reg, long offset) {
  if (!rules_.CFARule()) {
    reporter_->NoCFARule(entry_->offset, entry_->kind, CursorOffset());
    return false;
  }
  return DoRule(reg,
                new ValOffsetRule(Handler::kCFARegister, offset));
}

bool CallFrameInfo::State::DoRestore(unsigned reg) {
  // DW_CFA_restore and DW_CFA_restore_extended don't make sense in a CIE.
  if (entry_->kind == kCIE) {
    reporter_->RestoreInCIE(entry_->offset, CursorOffset());
    return false;
  }
  Rule *rule = cie_rules_.RegisterRule(reg);
  if (!rule) {
    // This isn't really the right thing to do, but since CFI generally
    // only mentions callee-saves registers, and GCC's convention for
    // callee-saves registers is that they are unchanged, it's a good
    // approximation.
    rule = new SameValueRule();
  }
  return DoRule(reg, rule);
}

bool CallFrameInfo::ReadEntryPrologue(const char *cursor, Entry *entry) {
  const char *buffer_end = buffer_ + buffer_length_;

  // Initialize enough of ENTRY for use in error reporting.
  entry->offset = cursor - buffer_;
  entry->start = cursor;
  entry->kind = kUnknown;
  entry->end = NULL;

  // Read the initial length. This sets reader_'s offset size.
  size_t length_size;
  uint64 length = reader_->ReadInitialLength(cursor, &length_size);
  if (length_size > size_t(buffer_end - cursor))
    return ReportIncomplete(entry);
  cursor += length_size;

  // In a .eh_frame section, a length of zero marks the end of the series
  // of entries.
  if (length == 0 && eh_frame_) {
    entry->kind = kTerminator;
    entry->end = cursor;
    return true;
  }

  // Validate the length.
  if (length > size_t(buffer_end - cursor))
    return ReportIncomplete(entry);

  // The length is the number of bytes after the initial length field;
  // we have that position handy at this point, so compute the end
  // now. (If we're parsing 64-bit-offset DWARF on a 32-bit machine,
  // and the length didn't fit in a size_t, we would have rejected it
  // above.)
  entry->end = cursor + length;

  // Parse the next field: either the offset of a CIE or a CIE id.
  size_t offset_size = reader_->OffsetSize();
  if (offset_size > size_t(entry->end - cursor)) return ReportIncomplete(entry);
  entry->id = reader_->ReadOffset(cursor);

  // Don't advance cursor past id field yet; in .eh_frame data we need
  // the id's position to compute the section offset of an FDE's CIE.

  // Now we can decide what kind of entry this is.
  if (eh_frame_) {
    // In .eh_frame data, an ID of zero marks the entry as a CIE, and
    // anything else is an offset from the id field of the FDE to the start
    // of the CIE.
    if (entry->id == 0) {
      entry->kind = kCIE;
    } else {
      entry->kind = kFDE;
      // Turn the offset from the id into an offset from the buffer's start.
      entry->id = (cursor - buffer_) - entry->id;
    }
  } else {
    // In DWARF CFI data, an ID of ~0 (of the appropriate width, given the
    // offset size for the entry) marks the entry as a CIE, and anything
    // else is the offset of the CIE from the beginning of the section.
    if (offset_size == 4)
      entry->kind = (entry->id == 0xffffffff) ? kCIE : kFDE;
    else {
      MOZ_ASSERT(offset_size == 8);
      entry->kind = (entry->id == 0xffffffffffffffffULL) ? kCIE : kFDE;
    }
  }

  // Now advance cursor past the id.
   cursor += offset_size;

  // The fields specific to this kind of entry start here.
  entry->fields = cursor;

  entry->cie = NULL;

  return true;
}

bool CallFrameInfo::ReadCIEFields(CIE *cie) {
  const char *cursor = cie->fields;
  size_t len;

  MOZ_ASSERT(cie->kind == kCIE);

  // Prepare for early exit.
  cie->version = 0;
  cie->augmentation.clear();
  cie->code_alignment_factor = 0;
  cie->data_alignment_factor = 0;
  cie->return_address_register = 0;
  cie->has_z_augmentation = false;
  cie->pointer_encoding = DW_EH_PE_absptr;
  cie->instructions = 0;

  // Parse the version number.
  if (cie->end - cursor < 1)
    return ReportIncomplete(cie);
  cie->version = reader_->ReadOneByte(cursor);
  cursor++;

  // If we don't recognize the version, we can't parse any more fields of the
  // CIE. For DWARF CFI, we handle versions 1 through 3 (there was never a
  // version 2 of CFI data). For .eh_frame, we handle versions 1 and 3 as well;
  // the difference between those versions seems to be the same as for
  // .debug_frame.
  if (cie->version < 1 || cie->version > 3) {
    reporter_->UnrecognizedVersion(cie->offset, cie->version);
    return false;
  }

  const char *augmentation_start = cursor;
  const void *augmentation_end =
      memchr(augmentation_start, '\0', cie->end - augmentation_start);
  if (! augmentation_end) return ReportIncomplete(cie);
  cursor = static_cast<const char *>(augmentation_end);
  cie->augmentation = string(augmentation_start,
                                  cursor - augmentation_start);
  // Skip the terminating '\0'.
  cursor++;

  // Is this CFI augmented?
  if (!cie->augmentation.empty()) {
    // Is it an augmentation we recognize?
    if (cie->augmentation[0] == DW_Z_augmentation_start) {
      // Linux C++ ABI 'z' augmentation, used for exception handling data.
      cie->has_z_augmentation = true;
    } else {
      // Not an augmentation we recognize. Augmentations can have arbitrary
      // effects on the form of rest of the content, so we have to give up.
      reporter_->UnrecognizedAugmentation(cie->offset, cie->augmentation);
      return false;
    }
  }

  // Parse the code alignment factor.
  cie->code_alignment_factor = reader_->ReadUnsignedLEB128(cursor, &len);
  if (size_t(cie->end - cursor) < len) return ReportIncomplete(cie);
  cursor += len;

  // Parse the data alignment factor.
  cie->data_alignment_factor = reader_->ReadSignedLEB128(cursor, &len);
  if (size_t(cie->end - cursor) < len) return ReportIncomplete(cie);
  cursor += len;

  // Parse the return address register. This is a ubyte in version 1, and
  // a ULEB128 in version 3.
  if (cie->version == 1) {
    if (cursor >= cie->end) return ReportIncomplete(cie);
    cie->return_address_register = uint8(*cursor++);
  } else {
    cie->return_address_register = reader_->ReadUnsignedLEB128(cursor, &len);
    if (size_t(cie->end - cursor) < len) return ReportIncomplete(cie);
    cursor += len;
  }

  // If we have a 'z' augmentation string, find the augmentation data and
  // use the augmentation string to parse it.
  if (cie->has_z_augmentation) {
    uint64_t data_size = reader_->ReadUnsignedLEB128(cursor, &len);
    if (size_t(cie->end - cursor) < len + data_size)
      return ReportIncomplete(cie);
    cursor += len;
    const char *data = cursor;
    cursor += data_size;
    const char *data_end = cursor;

    cie->has_z_lsda = false;
    cie->has_z_personality = false;
    cie->has_z_signal_frame = false;

    // Walk the augmentation string, and extract values from the
    // augmentation data as the string directs.
    for (size_t i = 1; i < cie->augmentation.size(); i++) {
      switch (cie->augmentation[i]) {
        case DW_Z_has_LSDA:
          // The CIE's augmentation data holds the language-specific data
          // area pointer's encoding, and the FDE's augmentation data holds
          // the pointer itself.
          cie->has_z_lsda = true;
          // Fetch the LSDA encoding from the augmentation data.
          if (data >= data_end) return ReportIncomplete(cie);
          cie->lsda_encoding = DwarfPointerEncoding(*data++);
          if (!reader_->ValidEncoding(cie->lsda_encoding)) {
            reporter_->InvalidPointerEncoding(cie->offset, cie->lsda_encoding);
            return false;
          }
          // Don't check if the encoding is usable here --- we haven't
          // read the FDE's fields yet, so we're not prepared for
          // DW_EH_PE_funcrel, although that's a fine encoding for the
          // LSDA to use, since it appears in the FDE.
          break;

        case DW_Z_has_personality_routine:
          // The CIE's augmentation data holds the personality routine
          // pointer's encoding, followed by the pointer itself.
          cie->has_z_personality = true;
          // Fetch the personality routine pointer's encoding from the
          // augmentation data.
          if (data >= data_end) return ReportIncomplete(cie);
          cie->personality_encoding = DwarfPointerEncoding(*data++);
          if (!reader_->ValidEncoding(cie->personality_encoding)) {
            reporter_->InvalidPointerEncoding(cie->offset,
                                              cie->personality_encoding);
            return false;
          }
          if (!reader_->UsableEncoding(cie->personality_encoding)) {
            reporter_->UnusablePointerEncoding(cie->offset,
                                               cie->personality_encoding);
            return false;
          }
          // Fetch the personality routine's pointer itself from the data.
          cie->personality_address =
            reader_->ReadEncodedPointer(data, cie->personality_encoding,
                                        &len);
          if (len > size_t(data_end - data))
            return ReportIncomplete(cie);
          data += len;
          break;

        case DW_Z_has_FDE_address_encoding:
          // The CIE's augmentation data holds the pointer encoding to use
          // for addresses in the FDE.
          if (data >= data_end) return ReportIncomplete(cie);
          cie->pointer_encoding = DwarfPointerEncoding(*data++);
          if (!reader_->ValidEncoding(cie->pointer_encoding)) {
            reporter_->InvalidPointerEncoding(cie->offset,
                                              cie->pointer_encoding);
            return false;
          }
          if (!reader_->UsableEncoding(cie->pointer_encoding)) {
            reporter_->UnusablePointerEncoding(cie->offset,
                                               cie->pointer_encoding);
            return false;
          }
          break;

        case DW_Z_is_signal_trampoline:
          // Frames using this CIE are signal delivery frames.
          cie->has_z_signal_frame = true;
          break;

        default:
          // An augmentation we don't recognize.
          reporter_->UnrecognizedAugmentation(cie->offset, cie->augmentation);
          return false;
      }
    }
  }

  // The CIE's instructions start here.
  cie->instructions = cursor;

  return true;
}

bool CallFrameInfo::ReadFDEFields(FDE *fde) {
  const char *cursor = fde->fields;
  size_t size;

  fde->address = reader_->ReadEncodedPointer(cursor, fde->cie->pointer_encoding,
                                             &size);
  if (size > size_t(fde->end - cursor))
    return ReportIncomplete(fde);
  cursor += size;
  reader_->SetFunctionBase(fde->address);

  // For the length, we strip off the upper nybble of the encoding used for
  // the starting address.
  DwarfPointerEncoding length_encoding =
    DwarfPointerEncoding(fde->cie->pointer_encoding & 0x0f);
  fde->size = reader_->ReadEncodedPointer(cursor, length_encoding, &size);
  if (size > size_t(fde->end - cursor))
    return ReportIncomplete(fde);
  cursor += size;

  // If the CIE has a 'z' augmentation string, then augmentation data
  // appears here.
  if (fde->cie->has_z_augmentation) {
    uint64_t data_size = reader_->ReadUnsignedLEB128(cursor, &size);
    if (size_t(fde->end - cursor) < size + data_size)
      return ReportIncomplete(fde);
    cursor += size;

    // In the abstract, we should walk the augmentation string, and extract
    // items from the FDE's augmentation data as we encounter augmentation
    // string characters that specify their presence: the ordering of items
    // in the augmentation string determines the arrangement of values in
    // the augmentation data.
    //
    // In practice, there's only ever one value in FDE augmentation data
    // that we support --- the LSDA pointer --- and we have to bail if we
    // see any unrecognized augmentation string characters. So if there is
    // anything here at all, we know what it is, and where it starts.
    if (fde->cie->has_z_lsda) {
      // Check whether the LSDA's pointer encoding is usable now: only once
      // we've parsed the FDE's starting address do we call reader_->
      // SetFunctionBase, so that the DW_EH_PE_funcrel encoding becomes
      // usable.
      if (!reader_->UsableEncoding(fde->cie->lsda_encoding)) {
        reporter_->UnusablePointerEncoding(fde->cie->offset,
                                           fde->cie->lsda_encoding);
        return false;
      }

      fde->lsda_address =
        reader_->ReadEncodedPointer(cursor, fde->cie->lsda_encoding, &size);
      if (size > data_size)
        return ReportIncomplete(fde);
      // Ideally, we would also complain here if there were unconsumed
      // augmentation data.
    }

    cursor += data_size;
  }

  // The FDE's instructions start after those.
  fde->instructions = cursor;

  return true;
}

bool CallFrameInfo::Start() {
  const char *buffer_end = buffer_ + buffer_length_;
  const char *cursor;
  bool all_ok = true;
  const char *entry_end;
  bool ok;

  // Traverse all the entries in buffer_, skipping CIEs and offering
  // FDEs to the handler.
  for (cursor = buffer_; cursor < buffer_end;
       cursor = entry_end, all_ok = all_ok && ok) {
    FDE fde;

    // Make it easy to skip this entry with 'continue': assume that
    // things are not okay until we've checked all the data, and
    // prepare the address of the next entry.
    ok = false;

    // Read the entry's prologue.
    if (!ReadEntryPrologue(cursor, &fde)) {
      if (!fde.end) {
        // If we couldn't even figure out this entry's extent, then we
        // must stop processing entries altogether.
        all_ok = false;
        break;
      }
      entry_end = fde.end;
      continue;
    }

    // The next iteration picks up after this entry.
    entry_end = fde.end;

    // Did we see an .eh_frame terminating mark?
    if (fde.kind == kTerminator) {
      // If there appears to be more data left in the section after the
      // terminating mark, warn the user. But this is just a warning;
      // we leave all_ok true.
      if (fde.end < buffer_end) reporter_->EarlyEHTerminator(fde.offset);
      break;
    }

    // In this loop, we skip CIEs. We only parse them fully when we
    // parse an FDE that refers to them. This limits our memory
    // consumption (beyond the buffer itself) to that needed to
    // process the largest single entry.
    if (fde.kind != kFDE) {
      ok = true;
      continue;
    }

    // Validate the CIE pointer.
    if (fde.id > buffer_length_) {
      reporter_->CIEPointerOutOfRange(fde.offset, fde.id);
      continue;
    }

    CIE cie;

    // Parse this FDE's CIE header.
    if (!ReadEntryPrologue(buffer_ + fde.id, &cie))
      continue;
    // This had better be an actual CIE.
    if (cie.kind != kCIE) {
      reporter_->BadCIEId(fde.offset, fde.id);
      continue;
    }
    if (!ReadCIEFields(&cie))
      continue;

    // We now have the values that govern both the CIE and the FDE.
    cie.cie = &cie;
    fde.cie = &cie;

    // Parse the FDE's header.
    if (!ReadFDEFields(&fde))
      continue;

    // Call Entry to ask the consumer if they're interested.
    if (!handler_->Entry(fde.offset, fde.address, fde.size,
                         cie.version, cie.augmentation,
                         cie.return_address_register)) {
      // The handler isn't interested in this entry. That's not an error.
      ok = true;
      continue;
    }

    if (cie.has_z_augmentation) {
      // Report the personality routine address, if we have one.
      if (cie.has_z_personality) {
        if (!handler_
            ->PersonalityRoutine(cie.personality_address,
                                 IsIndirectEncoding(cie.personality_encoding)))
          continue;
      }

      // Report the language-specific data area address, if we have one.
      if (cie.has_z_lsda) {
        if (!handler_
            ->LanguageSpecificDataArea(fde.lsda_address,
                                       IsIndirectEncoding(cie.lsda_encoding)))
          continue;
      }

      // If this is a signal-handling frame, report that.
      if (cie.has_z_signal_frame) {
        if (!handler_->SignalHandler())
          continue;
      }
    }

    // Interpret the CIE's instructions, and then the FDE's instructions.
    State state(reader_, handler_, reporter_, fde.address);
    ok = state.InterpretCIE(cie) && state.InterpretFDE(fde);

    // Tell the ByteReader that the function start address from the
    // FDE header is no longer valid.
    reader_->ClearFunctionBase();

    // Report the end of the entry.
    handler_->End();
  }

  return all_ok;
}

const char *CallFrameInfo::KindName(EntryKind kind) {
  if (kind == CallFrameInfo::kUnknown)
    return "entry";
  else if (kind == CallFrameInfo::kCIE)
    return "common information entry";
  else if (kind == CallFrameInfo::kFDE)
    return "frame description entry";
  else {
    MOZ_ASSERT (kind == CallFrameInfo::kTerminator);
    return ".eh_frame sequence terminator";
  }
}

bool CallFrameInfo::ReportIncomplete(Entry *entry) {
  reporter_->Incomplete(entry->offset, entry->kind);
  return false;
}

void CallFrameInfo::Reporter::Incomplete(uint64 offset,
                                         CallFrameInfo::EntryKind kind) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI %s at offset 0x%llx in '%s': entry ends early\n",
           filename_.c_str(), CallFrameInfo::KindName(kind), offset,
           section_.c_str());
  log_(buf);
}

void CallFrameInfo::Reporter::EarlyEHTerminator(uint64 offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI at offset 0x%llx in '%s': saw end-of-data marker"
           " before end of section contents\n",
           filename_.c_str(), offset, section_.c_str());
  log_(buf);
}

void CallFrameInfo::Reporter::CIEPointerOutOfRange(uint64 offset,
                                                   uint64 cie_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI frame description entry at offset 0x%llx in '%s':"
           " CIE pointer is out of range: 0x%llx\n",
           filename_.c_str(), offset, section_.c_str(), cie_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::BadCIEId(uint64 offset, uint64 cie_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI frame description entry at offset 0x%llx in '%s':"
           " CIE pointer does not point to a CIE: 0x%llx\n",
           filename_.c_str(), offset, section_.c_str(), cie_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::UnrecognizedVersion(uint64 offset, int version) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI frame description entry at offset 0x%llx in '%s':"
           " CIE specifies unrecognized version: %d\n",
           filename_.c_str(), offset, section_.c_str(), version);
  log_(buf);
}

void CallFrameInfo::Reporter::UnrecognizedAugmentation(uint64 offset,
                                                       const string &aug) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI frame description entry at offset 0x%llx in '%s':"
           " CIE specifies unrecognized augmentation: '%s'\n",
           filename_.c_str(), offset, section_.c_str(), aug.c_str());
  log_(buf);
}

void CallFrameInfo::Reporter::InvalidPointerEncoding(uint64 offset,
                                                     uint8 encoding) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI common information entry at offset 0x%llx in '%s':"
           " 'z' augmentation specifies invalid pointer encoding: 0x%02x\n",
           filename_.c_str(), offset, section_.c_str(), encoding);
  log_(buf);
}

void CallFrameInfo::Reporter::UnusablePointerEncoding(uint64 offset,
                                                      uint8 encoding) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI common information entry at offset 0x%llx in '%s':"
           " 'z' augmentation specifies a pointer encoding for which"
           " we have no base address: 0x%02x\n",
           filename_.c_str(), offset, section_.c_str(), encoding);
  log_(buf);
}

void CallFrameInfo::Reporter::RestoreInCIE(uint64 offset, uint64 insn_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI common information entry at offset 0x%llx in '%s':"
           " the DW_CFA_restore instruction at offset 0x%llx"
           " cannot be used in a common information entry\n",
           filename_.c_str(), offset, section_.c_str(), insn_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::BadInstruction(uint64 offset,
                                             CallFrameInfo::EntryKind kind,
                                             uint64 insn_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI %s at offset 0x%llx in section '%s':"
           " the instruction at offset 0x%llx is unrecognized\n",
           filename_.c_str(), CallFrameInfo::KindName(kind),
           offset, section_.c_str(), insn_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::NoCFARule(uint64 offset,
                                        CallFrameInfo::EntryKind kind,
                                        uint64 insn_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI %s at offset 0x%llx in section '%s':"
           " the instruction at offset 0x%llx assumes that a CFA rule has"
           " been set, but none has been set\n",
           filename_.c_str(), CallFrameInfo::KindName(kind), offset,
           section_.c_str(), insn_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::EmptyStateStack(uint64 offset,
                                              CallFrameInfo::EntryKind kind,
                                              uint64 insn_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI %s at offset 0x%llx in section '%s':"
           " the DW_CFA_restore_state instruction at offset 0x%llx"
           " should pop a saved state from the stack, but the stack is empty\n",
           filename_.c_str(), CallFrameInfo::KindName(kind), offset,
           section_.c_str(), insn_offset);
  log_(buf);
}

void CallFrameInfo::Reporter::ClearingCFARule(uint64 offset,
                                              CallFrameInfo::EntryKind kind,
                                              uint64 insn_offset) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "%s: CFI %s at offset 0x%llx in section '%s':"
           " the DW_CFA_restore_state instruction at offset 0x%llx"
           " would clear the CFA rule in effect\n",
           filename_.c_str(), CallFrameInfo::KindName(kind), offset,
           section_.c_str(), insn_offset);
  log_(buf);
}


const unsigned int DwarfCFIToModule::RegisterNames::I386() {
  /*
   8 "$eax", "$ecx", "$edx", "$ebx", "$esp", "$ebp", "$esi", "$edi",
   3 "$eip", "$eflags", "$unused1",
   8 "$st0", "$st1", "$st2", "$st3", "$st4", "$st5", "$st6", "$st7",
   2 "$unused2", "$unused3",
   8 "$xmm0", "$xmm1", "$xmm2", "$xmm3", "$xmm4", "$xmm5", "$xmm6", "$xmm7",
   8 "$mm0", "$mm1", "$mm2", "$mm3", "$mm4", "$mm5", "$mm6", "$mm7",
   3 "$fcw", "$fsw", "$mxcsr",
   8 "$es", "$cs", "$ss", "$ds", "$fs", "$gs", "$unused4", "$unused5",
   2 "$tr", "$ldtr"
  */
  return 8 + 3 + 8 + 2 + 8 + 8 + 3 + 8 + 2;
}

const unsigned int DwarfCFIToModule::RegisterNames::X86_64() {
  /*
   8 "$rax", "$rdx", "$rcx", "$rbx", "$rsi", "$rdi", "$rbp", "$rsp",
   8 "$r8",  "$r9",  "$r10", "$r11", "$r12", "$r13", "$r14", "$r15",
   1 "$rip",
   8 "$xmm0","$xmm1","$xmm2", "$xmm3", "$xmm4", "$xmm5", "$xmm6", "$xmm7",
   8 "$xmm8","$xmm9","$xmm10","$xmm11","$xmm12","$xmm13","$xmm14","$xmm15",
   8 "$st0", "$st1", "$st2", "$st3", "$st4", "$st5", "$st6", "$st7",
   8 "$mm0", "$mm1", "$mm2", "$mm3", "$mm4", "$mm5", "$mm6", "$mm7",
   1 "$rflags",
   8 "$es", "$cs", "$ss", "$ds", "$fs", "$gs", "$unused1", "$unused2",
   4 "$fs.base", "$gs.base", "$unused3", "$unused4",
   2 "$tr", "$ldtr",
   3 "$mxcsr", "$fcw", "$fsw"
  */
  return 8 + 8 + 1 + 8 + 8 + 8 + 8 + 1 + 8 + 4 + 2 + 3;
}

// Per ARM IHI 0040A, section 3.1
const unsigned int DwarfCFIToModule::RegisterNames::ARM() {
  /*
   8 "r0",  "r1",  "r2",  "r3",  "r4",  "r5",  "r6",  "r7",
   8 "r8",  "r9",  "r10", "r11", "r12", "sp",  "lr",  "pc",
   8 "f0",  "f1",  "f2",  "f3",  "f4",  "f5",  "f6",  "f7",
   8 "fps", "cpsr", "",   "",    "",    "",    "",    "",
   8 "",    "",    "",    "",    "",    "",    "",    "",
   8 "",    "",    "",    "",    "",    "",    "",    "",
   8 "",    "",    "",    "",    "",    "",    "",    "",
   8 "",    "",    "",    "",    "",    "",    "",    "",
   8 "s0",  "s1",  "s2",  "s3",  "s4",  "s5",  "s6",  "s7",
   8 "s8",  "s9",  "s10", "s11", "s12", "s13", "s14", "s15",
   8 "s16", "s17", "s18", "s19", "s20", "s21", "s22", "s23",
   8 "s24", "s25", "s26", "s27", "s28", "s29", "s30", "s31",
   8 "f0",  "f1",  "f2",  "f3",  "f4",  "f5",  "f6",  "f7"
  */
  return 13 * 8;
}

bool DwarfCFIToModule::Entry(size_t offset, uint64 address, uint64 length,
                             uint8 version, const string &augmentation,
                             unsigned return_address) {
  if (DEBUG_DWARF)
    printf("LUL.DW DwarfCFIToModule::Entry 0x%llx,+%lld\n", address, length);

  summ_->Entry(address, length);

  // If dwarf2reader::CallFrameInfo can handle this version and
  // augmentation, then we should be okay with that, so there's no
  // need to check them here.

  // Get ready to collect entries.
  return_address_ = return_address;

  // Breakpad STACK CFI records must provide a .ra rule, but DWARF CFI
  // may not establish any rule for .ra if the return address column
  // is an ordinary register, and that register holds the return
  // address on entry to the function. So establish an initial .ra
  // rule citing the return address register.
  if (return_address_ < num_dw_regs_) {
    summ_->Rule(address, return_address_, return_address, 0, false);
  }

  return true;
}

const UniqueString* DwarfCFIToModule::RegisterName(int i) {
  if (i < 0) {
    MOZ_ASSERT(i == kCFARegister);
    return ustr__ZDcfa();
  }
  unsigned reg = i;
  if (reg == return_address_)
    return ustr__ZDra();

  char buf[30];
  sprintf(buf, "dwarf_reg_%u", reg);
  return ToUniqueString(buf);
}

bool DwarfCFIToModule::UndefinedRule(uint64 address, int reg) {
  reporter_->UndefinedNotSupported(entry_offset_, RegisterName(reg));
  // Treat this as a non-fatal error.
  return true;
}

bool DwarfCFIToModule::SameValueRule(uint64 address, int reg) {
  if (DEBUG_DWARF)
    printf("LUL.DW  0x%llx: old r%d = Same\n", address, reg);
  // reg + 0
  summ_->Rule(address, reg, reg, 0, false);
  return true;
}

bool DwarfCFIToModule::OffsetRule(uint64 address, int reg,
                                  int base_register, long offset) {
  if (DEBUG_DWARF)
    printf("LUL.DW  0x%llx: old r%d = *(r%d + %ld)\n",
           address, reg, base_register, offset);
  // *(base_register + offset)
  summ_->Rule(address, reg, base_register, offset, true);
  return true;
}

bool DwarfCFIToModule::ValOffsetRule(uint64 address, int reg,
                                     int base_register, long offset) {
  if (DEBUG_DWARF)
    printf("LUL.DW  0x%llx: old r%d = r%d + %ld\n",
           address, reg, base_register, offset);
  // base_register + offset
  summ_->Rule(address, reg, base_register, offset, false);
  return true;
}

bool DwarfCFIToModule::RegisterRule(uint64 address, int reg,
                                    int base_register) {
  if (DEBUG_DWARF)
    printf("LUL.DW  0x%llx: old r%d = r%d\n", address, reg, base_register);
  // base_register + 0
  summ_->Rule(address, reg, base_register, 0, false);
  return true;
}

bool DwarfCFIToModule::ExpressionRule(uint64 address, int reg,
                                      const string &expression) {
  reporter_->ExpressionsNotSupported(entry_offset_, RegisterName(reg));
  // Treat this as a non-fatal error.
  return true;
}

bool DwarfCFIToModule::ValExpressionRule(uint64 address, int reg,
                                         const string &expression) {
  reporter_->ExpressionsNotSupported(entry_offset_, RegisterName(reg));
  // Treat this as a non-fatal error.
  return true;
}

bool DwarfCFIToModule::End() {
  //module_->AddStackFrameEntry(entry_);
  if (DEBUG_DWARF)
    printf("LUL.DW DwarfCFIToModule::End()\n");
  summ_->End();
  return true;
}

void DwarfCFIToModule::Reporter::UndefinedNotSupported(
    size_t offset,
    const UniqueString* reg) {
  char buf[300];
  snprintf(buf, sizeof(buf),
           "DwarfCFIToModule::Reporter::UndefinedNotSupported()\n");
  log_(buf);
  //BPLOG(INFO) << file_ << ", section '" << section_
  //  << "': the call frame entry at offset 0x"
  //  << std::setbase(16) << offset << std::setbase(10)
  //  << " sets the rule for register '" << FromUniqueString(reg)
  //  << "' to 'undefined', but the Breakpad symbol file format cannot "
  //  << " express this";
}

// FIXME: move this somewhere sensible
static bool is_power_of_2(uint64_t n)
{
  int i, nSetBits = 0;
  for (i = 0; i < 8*(int)sizeof(n); i++) {
    if ((n & ((uint64_t)1) << i) != 0)
      nSetBits++;
  }
  return nSetBits <= 1;
}

void DwarfCFIToModule::Reporter::ExpressionsNotSupported(
    size_t offset,
    const UniqueString* reg) {
  static uint64_t n_complaints = 0; // This isn't threadsafe
  n_complaints++;
  if (!is_power_of_2(n_complaints))
    return;
  char buf[300];
  snprintf(buf, sizeof(buf),
           "DwarfCFIToModule::Reporter::"
           "ExpressionsNotSupported(shown %llu times)\n",
           (unsigned long long int)n_complaints);
  log_(buf);
  //BPLOG(INFO) << file_ << ", section '" << section_
  //  << "': the call frame entry at offset 0x"
  //  << std::setbase(16) << offset << std::setbase(10)
  //  << " uses a DWARF expression to describe how to recover register '"
  //  << FromUniqueString(reg) << "', but this translator cannot yet "
  //  << "translate DWARF expressions to Breakpad postfix expressions (shown "
  //  << n_complaints << " times)";
}

} // namespace lul