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
47namespace google_breakpad {
48
49using std::map;
50
51class 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// https://chromium.googlesource.com/breakpad/breakpad/+/master/docs/symbol_files.md
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.
66class 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.
75 void SetCFARule(const string& expression) { cfa_rule_ = expression; }
76 void SetRARule(const string& expression) { ra_rule_ = 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.
142class CFIRuleParser {
143 public:
144
145 class Handler {
146 public:
147 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.
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.
180class CFIFrameInfoParseHandler: public CFIRuleParser::Handler {
181 public:
182 // Populate FRAME_INFO with the results of parsing.
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.
209template <typename RegisterType, class RawContextType>
210class 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.
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