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