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 // postfix_evaluator-inl.h: Postfix (reverse Polish) notation expression
32 // evaluator.
33 //
34 // Documentation in postfix_evaluator.h.
35 //
36 // Author: Mark Mentovai
37
38 #ifndef PROCESSOR_POSTFIX_EVALUATOR_INL_H__
39 #define PROCESSOR_POSTFIX_EVALUATOR_INL_H__
40
41 #include "processor/postfix_evaluator.h"
42
43 #include <stdio.h>
44
45 #include <sstream>
46
47 #include "google_breakpad/processor/memory_region.h"
48 #include "processor/logging.h"
49
50 namespace google_breakpad {
51
52 using std::istringstream;
53 using std::ostringstream;
54
55
56 // A small class used in Evaluate to make sure to clean up the stack
57 // before returning failure.
58 class AutoStackClearer {
59 public:
AutoStackClearer(vector<string> * stack)60 explicit AutoStackClearer(vector<string>* stack) : stack_(stack) {}
~AutoStackClearer()61 ~AutoStackClearer() { stack_->clear(); }
62
63 private:
64 vector<string>* stack_;
65 };
66
67
68 template<typename ValueType>
EvaluateToken(const string & token,const string & expression,DictionaryValidityType * assigned)69 bool PostfixEvaluator<ValueType>::EvaluateToken(
70 const string& token,
71 const string& expression,
72 DictionaryValidityType* assigned) {
73 // There are enough binary operations that do exactly the same thing
74 // (other than the specific operation, of course) that it makes sense
75 // to share as much code as possible.
76 enum BinaryOperation {
77 BINARY_OP_NONE = 0,
78 BINARY_OP_ADD,
79 BINARY_OP_SUBTRACT,
80 BINARY_OP_MULTIPLY,
81 BINARY_OP_DIVIDE_QUOTIENT,
82 BINARY_OP_DIVIDE_MODULUS,
83 BINARY_OP_ALIGN
84 };
85
86 BinaryOperation operation = BINARY_OP_NONE;
87 if (token == "+")
88 operation = BINARY_OP_ADD;
89 else if (token == "-")
90 operation = BINARY_OP_SUBTRACT;
91 else if (token == "*")
92 operation = BINARY_OP_MULTIPLY;
93 else if (token == "/")
94 operation = BINARY_OP_DIVIDE_QUOTIENT;
95 else if (token == "%")
96 operation = BINARY_OP_DIVIDE_MODULUS;
97 else if (token == "@")
98 operation = BINARY_OP_ALIGN;
99
100 if (operation != BINARY_OP_NONE) {
101 // Get the operands.
102 ValueType operand1 = ValueType();
103 ValueType operand2 = ValueType();
104 if (!PopValues(&operand1, &operand2)) {
105 BPLOG(ERROR) << "Could not PopValues to get two values for binary "
106 "operation " << token << ": " << expression;
107 return false;
108 }
109
110 // Perform the operation.
111 ValueType result;
112 switch (operation) {
113 case BINARY_OP_ADD:
114 result = operand1 + operand2;
115 break;
116 case BINARY_OP_SUBTRACT:
117 result = operand1 - operand2;
118 break;
119 case BINARY_OP_MULTIPLY:
120 result = operand1 * operand2;
121 break;
122 case BINARY_OP_DIVIDE_QUOTIENT:
123 result = operand1 / operand2;
124 break;
125 case BINARY_OP_DIVIDE_MODULUS:
126 result = operand1 % operand2;
127 break;
128 case BINARY_OP_ALIGN:
129 result =
130 operand1 & (static_cast<ValueType>(-1) ^ (operand2 - 1));
131 break;
132 case BINARY_OP_NONE:
133 // This will not happen, but compilers will want a default or
134 // BINARY_OP_NONE case.
135 BPLOG(ERROR) << "Not reached!";
136 return false;
137 break;
138 }
139
140 // Save the result.
141 PushValue(result);
142 } else if (token == "^") {
143 // ^ for unary dereference. Can't dereference without memory.
144 if (!memory_) {
145 BPLOG(ERROR) << "Attempt to dereference without memory: " <<
146 expression;
147 return false;
148 }
149
150 ValueType address;
151 if (!PopValue(&address)) {
152 BPLOG(ERROR) << "Could not PopValue to get value to derefence: " <<
153 expression;
154 return false;
155 }
156
157 ValueType value;
158 if (!memory_->GetMemoryAtAddress(address, &value)) {
159 BPLOG(ERROR) << "Could not dereference memory at address " <<
160 HexString(address) << ": " << expression;
161 return false;
162 }
163
164 PushValue(value);
165 } else if (token == "=") {
166 // = for assignment.
167 ValueType value;
168 if (!PopValue(&value)) {
169 BPLOG(INFO) << "Could not PopValue to get value to assign: " <<
170 expression;
171 return false;
172 }
173
174 // Assignment is only meaningful when assigning into an identifier.
175 // The identifier must name a variable, not a constant. Variables
176 // begin with '$'.
177 string identifier;
178 if (PopValueOrIdentifier(NULL, &identifier) != POP_RESULT_IDENTIFIER) {
179 BPLOG(ERROR) << "PopValueOrIdentifier returned a value, but an "
180 "identifier is needed to assign " <<
181 HexString(value) << ": " << expression;
182 return false;
183 }
184 if (identifier.empty() || identifier[0] != '$') {
185 BPLOG(ERROR) << "Can't assign " << HexString(value) << " to " <<
186 identifier << ": " << expression;
187 return false;
188 }
189
190 (*dictionary_)[identifier] = value;
191 if (assigned)
192 (*assigned)[identifier] = true;
193 } else {
194 // The token is not an operator, it's a literal value or an identifier.
195 // Push it onto the stack as-is. Use push_back instead of PushValue
196 // because PushValue pushes ValueType as a string, but token is already
197 // a string.
198 stack_.push_back(token);
199 }
200 return true;
201 }
202
203 template<typename ValueType>
EvaluateInternal(const string & expression,DictionaryValidityType * assigned)204 bool PostfixEvaluator<ValueType>::EvaluateInternal(
205 const string& expression,
206 DictionaryValidityType* assigned) {
207 // Tokenize, splitting on whitespace.
208 istringstream stream(expression);
209 string token;
210 while (stream >> token) {
211 // Normally, tokens are whitespace-separated, but occasionally, the
212 // assignment operator is smashed up against the next token, i.e.
213 // $T0 $ebp 128 + =$eip $T0 4 + ^ =$ebp $T0 ^ =
214 // This has been observed in program strings produced by MSVS 2010 in LTO
215 // mode.
216 if (token.size() > 1 && token[0] == '=') {
217 if (!EvaluateToken("=", expression, assigned)) {
218 return false;
219 }
220
221 if (!EvaluateToken(token.substr(1), expression, assigned)) {
222 return false;
223 }
224 } else if (!EvaluateToken(token, expression, assigned)) {
225 return false;
226 }
227 }
228
229 return true;
230 }
231
232 template<typename ValueType>
Evaluate(const string & expression,DictionaryValidityType * assigned)233 bool PostfixEvaluator<ValueType>::Evaluate(const string& expression,
234 DictionaryValidityType* assigned) {
235 // Ensure that the stack is cleared before returning.
236 AutoStackClearer clearer(&stack_);
237
238 if (!EvaluateInternal(expression, assigned))
239 return false;
240
241 // If there's anything left on the stack, it indicates incomplete execution.
242 // This is a failure case. If the stack is empty, evalution was complete
243 // and successful.
244 if (stack_.empty())
245 return true;
246
247 BPLOG(ERROR) << "Incomplete execution: " << expression;
248 return false;
249 }
250
251 template<typename ValueType>
EvaluateForValue(const string & expression,ValueType * result)252 bool PostfixEvaluator<ValueType>::EvaluateForValue(const string& expression,
253 ValueType* result) {
254 // Ensure that the stack is cleared before returning.
255 AutoStackClearer clearer(&stack_);
256
257 if (!EvaluateInternal(expression, NULL))
258 return false;
259
260 // A successful execution should leave exactly one value on the stack.
261 if (stack_.size() != 1) {
262 BPLOG(ERROR) << "Expression yielded bad number of results: "
263 << "'" << expression << "'";
264 return false;
265 }
266
267 return PopValue(result);
268 }
269
270 template<typename ValueType>
271 typename PostfixEvaluator<ValueType>::PopResult
PopValueOrIdentifier(ValueType * value,string * identifier)272 PostfixEvaluator<ValueType>::PopValueOrIdentifier(
273 ValueType* value, string* identifier) {
274 // There needs to be at least one element on the stack to pop.
275 if (!stack_.size())
276 return POP_RESULT_FAIL;
277
278 string token = stack_.back();
279 stack_.pop_back();
280
281 // First, try to treat the value as a literal. Literals may have leading
282 // '-' sign, and the entire remaining string must be parseable as
283 // ValueType. If this isn't possible, it can't be a literal, so treat it
284 // as an identifier instead.
285 //
286 // Some versions of the libstdc++, the GNU standard C++ library, have
287 // stream extractors for unsigned integer values that permit a leading
288 // '-' sign (6.0.13); others do not (6.0.9). Since we require it, we
289 // handle it explicitly here.
290 istringstream token_stream(token);
291 ValueType literal = ValueType();
292 bool negative;
293 if (token_stream.peek() == '-') {
294 negative = true;
295 token_stream.get();
296 } else {
297 negative = false;
298 }
299 if (token_stream >> literal && token_stream.peek() == EOF) {
300 if (value) {
301 *value = literal;
302 }
303 if (negative)
304 *value = -*value;
305 return POP_RESULT_VALUE;
306 } else {
307 if (identifier) {
308 *identifier = token;
309 }
310 return POP_RESULT_IDENTIFIER;
311 }
312 }
313
314
315 template<typename ValueType>
PopValue(ValueType * value)316 bool PostfixEvaluator<ValueType>::PopValue(ValueType* value) {
317 ValueType literal = ValueType();
318 string token;
319 PopResult result;
320 if ((result = PopValueOrIdentifier(&literal, &token)) == POP_RESULT_FAIL) {
321 return false;
322 } else if (result == POP_RESULT_VALUE) {
323 // This is the easy case.
324 *value = literal;
325 } else { // result == POP_RESULT_IDENTIFIER
326 // There was an identifier at the top of the stack. Resolve it to a
327 // value by looking it up in the dictionary.
328 typename DictionaryType::const_iterator iterator =
329 dictionary_->find(token);
330 if (iterator == dictionary_->end()) {
331 // The identifier wasn't found in the dictionary. Don't imply any
332 // default value, just fail.
333 BPLOG(INFO) << "Identifier " << token << " not in dictionary";
334 return false;
335 }
336
337 *value = iterator->second;
338 }
339
340 return true;
341 }
342
343
344 template<typename ValueType>
PopValues(ValueType * value1,ValueType * value2)345 bool PostfixEvaluator<ValueType>::PopValues(ValueType* value1,
346 ValueType* value2) {
347 return PopValue(value2) && PopValue(value1);
348 }
349
350
351 template<typename ValueType>
PushValue(const ValueType & value)352 void PostfixEvaluator<ValueType>::PushValue(const ValueType& value) {
353 ostringstream token_stream;
354 token_stream << value;
355 stack_.push_back(token_stream.str());
356 }
357
358
359 } // namespace google_breakpad
360
361
362 #endif // PROCESSOR_POSTFIX_EVALUATOR_INL_H__
363