1  // -*- mode: C++ -*-
  2  
  3  // Copyright 2010 Google LLC
  4  //
  5  // Redistribution and use in source and binary forms, with or without
  6  // modification, are permitted provided that the following conditions are
  7  // met:
  8  //
  9  //     * Redistributions of source code must retain the above copyright
 10  // notice, this list of conditions and the following disclaimer.
 11  //     * Redistributions in binary form must reproduce the above
 12  // copyright notice, this list of conditions and the following disclaimer
 13  // in the documentation and/or other materials provided with the
 14  // distribution.
 15  //     * Neither the name of Google LLC nor the names of its
 16  // contributors may be used to endorse or promote products derived from
 17  // this software without specific prior written permission.
 18  //
 19  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 20  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 21  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 22  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 23  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 24  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 25  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 26  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 27  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 28  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 29  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 30  
 31  // Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
 32  
 33  // cfi_frame_info.h: Define the CFIFrameInfo class, which holds the
 34  // set of 'STACK CFI'-derived register recovery rules that apply at a
 35  // given instruction.
 36  
 37  #ifndef PROCESSOR_CFI_FRAME_INFO_H_
 38  #define PROCESSOR_CFI_FRAME_INFO_H_
 39  
 40  #include <map>
 41  #include <string>
 42  
 43  #include "common/using_std_string.h"
 44  #include "google_breakpad/common/breakpad_types.h"
 45  
 46  namespace google_breakpad {
 47  
 48  using std::map;
 49  
 50  class MemoryRegion;
 51  
 52  // A set of rules for recovering the calling frame's registers'
 53  // values, when the PC is at a given address in the current frame's
 54  // function. See the description of 'STACK CFI' records at:
 55  //
 56  // https://chromium.googlesource.com/breakpad/breakpad/+/master/docs/symbol_files.md
 57  //
 58  // To prepare an instance of CFIFrameInfo for use at a given
 59  // instruction, first populate it with the rules from the 'STACK CFI
 60  // INIT' record that covers that instruction, and then apply the
 61  // changes given by the 'STACK CFI' records up to our instruction's
 62  // address. Then, use the FindCallerRegs member function to apply the
 63  // rules to the callee frame's register values, yielding the caller
 64  // frame's register values.
 65  class CFIFrameInfo {
 66   public:
 67    // A map from register names onto values.
 68    template<typename ValueType> class RegisterValueMap: 
 69      public map<string, ValueType> { };
 70  
 71    // Set the expression for computing a call frame address, return
 72    // address, or register's value. At least the CFA rule and the RA
 73    // rule must be set before calling FindCallerRegs.
 74    void SetCFARule(const string& expression) { cfa_rule_ = expression; }
 75    void SetRARule(const string& expression)  { ra_rule_ = expression; }
 76    void SetRegisterRule(const string& register_name, const string& expression) {
 77      register_rules_[register_name] = expression;
 78    }
 79  
 80    // Compute the values of the calling frame's registers, according to
 81    // this rule set. Use ValueType in expression evaluation; this
 82    // should be uint32_t on machines with 32-bit addresses, or
 83    // uint64_t on machines with 64-bit addresses.
 84    //
 85    // Return true on success, false otherwise.
 86    //
 87    // MEMORY provides access to the contents of the stack. REGISTERS is
 88    // a dictionary mapping the names of registers whose values are
 89    // known in the current frame to their values. CALLER_REGISTERS is
 90    // populated with the values of the recoverable registers in the
 91    // frame that called the current frame.
 92    //
 93    // In addition, CALLER_REGISTERS[".ra"] will be the return address,
 94    // and CALLER_REGISTERS[".cfa"] will be the call frame address.
 95    // These may be helpful in computing the caller's PC and stack
 96    // pointer, if their values are not explicitly specified.
 97    template<typename ValueType>
 98    bool FindCallerRegs(const RegisterValueMap<ValueType>& registers,
 99                        const MemoryRegion& memory,
100                        RegisterValueMap<ValueType>* caller_registers) const;
101  
102    // Serialize the rules in this object into a string in the format
103    // of STACK CFI records.
104    string Serialize() const;
105  
106   private:
107  
108    // A map from register names onto evaluation rules. 
109    typedef map<string, string> RuleMap;
110  
111    // In this type, a "postfix expression" is an expression of the sort
112    // interpreted by google_breakpad::PostfixEvaluator.
113  
114    // A postfix expression for computing the current frame's CFA (call
115    // frame address). The CFA is a reference address for the frame that
116    // remains unchanged throughout the frame's lifetime. You should
117    // evaluate this expression with a dictionary initially populated
118    // with the values of the current frame's known registers.
119    string cfa_rule_;
120  
121    // The following expressions should be evaluated with a dictionary
122    // initially populated with the values of the current frame's known
123    // registers, and with ".cfa" set to the result of evaluating the
124    // cfa_rule expression, above.
125  
126    // A postfix expression for computing the current frame's return
127    // address. 
128    string ra_rule_;
129  
130    // For a register named REG, rules[REG] is a postfix expression
131    // which leaves the value of REG in the calling frame on the top of
132    // the stack. You should evaluate this expression
133    RuleMap register_rules_;
134  };
135  
136  // A parser for STACK CFI-style rule sets.
137  // This may seem bureaucratic: there's no legitimate run-time reason
138  // to use a parser/handler pattern for this, as it's not a likely
139  // reuse boundary. But doing so makes finer-grained unit testing
140  // possible.
141  class CFIRuleParser {
142   public:
143  
144    class Handler {
145     public:
146      Handler() { }
147      virtual ~Handler() { }
148  
149      // The input specifies EXPRESSION as the CFA/RA computation rule.
150      virtual void CFARule(const string& expression) = 0;
151      virtual void RARule(const string& expression) = 0;
152  
153      // The input specifies EXPRESSION as the recovery rule for register NAME.
154      virtual void RegisterRule(const string& name, const string& expression) = 0;
155    };
156      
157    // Construct a parser which feeds its results to HANDLER.
158    CFIRuleParser(Handler* handler) : handler_(handler) { }
159  
160    // Parse RULE_SET as a set of CFA computation and RA/register
161    // recovery rules, as appearing in STACK CFI records. Report the
162    // results of parsing by making the appropriate calls to handler_.
163    // Return true if parsing was successful, false otherwise.
164    bool Parse(const string& rule_set);
165  
166   private:
167    // Report any accumulated rule to handler_
168    bool Report();
169  
170    // The handler to which the parser reports its findings.
171    Handler* handler_;
172  
173    // Working data.
174    string name_, expression_;
175  };
176  
177  // A handler for rule set parsing that populates a CFIFrameInfo with
178  // the results.
179  class CFIFrameInfoParseHandler: public CFIRuleParser::Handler {
180   public:
181    // Populate FRAME_INFO with the results of parsing.
182    CFIFrameInfoParseHandler(CFIFrameInfo* frame_info)
183        : frame_info_(frame_info) { }
184  
185    void CFARule(const string& expression);
186    void RARule(const string& expression);
187    void RegisterRule(const string& name, const string& expression);
188  
189   private:
190    CFIFrameInfo* frame_info_;
191  };
192  
193  // A utility class template for simple 'STACK CFI'-driven stack walkers.
194  // Given a CFIFrameInfo instance, a table describing the architecture's
195  // register set, and a context holding the last frame's registers, an
196  // instance of this class can populate a new context with the caller's
197  // registers.
198  //
199  // This class template doesn't use any internal knowledge of CFIFrameInfo
200  // or the other stack walking structures; it just uses the public interface
201  // of CFIFrameInfo to do the usual things. But the logic it handles should
202  // be common to many different architectures' stack walkers, so wrapping it
203  // up in a class should allow the walkers to share code.
204  //
205  // RegisterType should be the type of this architecture's registers, either
206  // uint32_t or uint64_t. RawContextType should be the raw context
207  // structure type for this architecture.
208  template <typename RegisterType, class RawContextType>
209  class SimpleCFIWalker {
210   public:
211    // A structure describing one architecture register.
212    struct RegisterSet {
213      // The register name, as it appears in STACK CFI rules.
214      const char* name;
215  
216      // An alternate name that the register's value might be found
217      // under in a register value dictionary, or NULL. When generating
218      // names, prefer NAME to this value. It's common to list ".cfa" as
219      // an alternative name for the stack pointer, and ".ra" as an
220      // alternative name for the instruction pointer.
221      const char* alternate_name;
222  
223      // True if the callee is expected to preserve the value of this
224      // register. If this flag is true for some register R, and the STACK
225      // CFI records provide no rule to recover R, then SimpleCFIWalker
226      // assumes that the callee has not changed R's value, and the caller's
227      // value for R is that currently in the callee's context.
228      bool callee_saves;
229  
230      // The ContextValidity flag representing the register's presence.
231      int validity_flag;
232  
233      // A pointer to the RawContextType member that holds the
234      // register's value.
235      RegisterType RawContextType::*context_member;
236    };
237  
238    // Create a simple CFI-based frame walker, given a description of the
239    // architecture's register set. REGISTER_MAP is an array of
240    // RegisterSet structures; MAP_SIZE is the number of elements in the
241    // array.
242    SimpleCFIWalker(const RegisterSet* register_map, size_t map_size)
243        : register_map_(register_map), map_size_(map_size) { }
244  
245    // Compute the calling frame's raw context given the callee's raw
246    // context.
247    //
248    // Given:
249    //
250    // - MEMORY, holding the stack's contents,
251    // - CFI_FRAME_INFO, describing the called function,
252    // - CALLEE_CONTEXT, holding the called frame's registers, and
253    // - CALLEE_VALIDITY, indicating which registers in CALLEE_CONTEXT are valid,
254    //
255    // fill in CALLER_CONTEXT with the caller's register values, and set
256    // CALLER_VALIDITY to indicate which registers are valid in
257    // CALLER_CONTEXT. Return true on success, or false on failure.
258    bool FindCallerRegisters(const MemoryRegion& memory,
259                             const CFIFrameInfo& cfi_frame_info,
260                             const RawContextType& callee_context,
261                             int callee_validity,
262                             RawContextType* caller_context,
263                             int* caller_validity) const;
264  
265   private:
266    const RegisterSet* register_map_;
267    size_t map_size_;
268  };
269  
270  }  // namespace google_breakpad
271  
272  #include "cfi_frame_info-inl.h"
273  
274  #endif  // PROCESSOR_CFI_FRAME_INFO_H_