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