1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/processor/postfix_evaluator-inl.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,421 @@
1.4 +// -*- mode: c++ -*-
1.5 +
1.6 +// Copyright (c) 2010 Google Inc.
1.7 +// All rights reserved.
1.8 +//
1.9 +// Redistribution and use in source and binary forms, with or without
1.10 +// modification, are permitted provided that the following conditions are
1.11 +// met:
1.12 +//
1.13 +// * Redistributions of source code must retain the above copyright
1.14 +// notice, this list of conditions and the following disclaimer.
1.15 +// * Redistributions in binary form must reproduce the above
1.16 +// copyright notice, this list of conditions and the following disclaimer
1.17 +// in the documentation and/or other materials provided with the
1.18 +// distribution.
1.19 +// * Neither the name of Google Inc. nor the names of its
1.20 +// contributors may be used to endorse or promote products derived from
1.21 +// this software without specific prior written permission.
1.22 +//
1.23 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.24 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.25 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.26 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.27 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.28 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.29 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.30 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.31 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.32 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.33 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.34 +
1.35 +// postfix_evaluator-inl.h: Postfix (reverse Polish) notation expression
1.36 +// evaluator.
1.37 +//
1.38 +// Documentation in postfix_evaluator.h.
1.39 +//
1.40 +// Author: Mark Mentovai
1.41 +
1.42 +#ifndef PROCESSOR_POSTFIX_EVALUATOR_INL_H__
1.43 +#define PROCESSOR_POSTFIX_EVALUATOR_INL_H__
1.44 +
1.45 +#include "processor/postfix_evaluator.h"
1.46 +
1.47 +#include <stdio.h>
1.48 +
1.49 +#include <sstream>
1.50 +
1.51 +#include "google_breakpad/processor/memory_region.h"
1.52 +#include "common/logging.h"
1.53 +
1.54 +namespace google_breakpad {
1.55 +
1.56 +using std::istringstream;
1.57 +using std::ostringstream;
1.58 +
1.59 +
1.60 +// A small class used in Evaluate to make sure to clean up the stack
1.61 +// before returning failure.
1.62 +template<typename ValueType>
1.63 +class AutoStackClearer {
1.64 + public:
1.65 + explicit AutoStackClearer(vector<StackElem<ValueType> > *stack)
1.66 + : stack_(stack) {}
1.67 + ~AutoStackClearer() { stack_->clear(); }
1.68 +
1.69 + private:
1.70 + vector<StackElem<ValueType> > *stack_;
1.71 +};
1.72 +
1.73 +
1.74 +template<typename ValueType>
1.75 +bool PostfixEvaluator<ValueType>::EvaluateToken(
1.76 + const string &token,
1.77 + const string &expression,
1.78 + DictionaryValidityType *assigned) {
1.79 + // There are enough binary operations that do exactly the same thing
1.80 + // (other than the specific operation, of course) that it makes sense
1.81 + // to share as much code as possible.
1.82 + enum BinaryOperation {
1.83 + BINARY_OP_NONE = 0,
1.84 + BINARY_OP_ADD,
1.85 + BINARY_OP_SUBTRACT,
1.86 + BINARY_OP_MULTIPLY,
1.87 + BINARY_OP_DIVIDE_QUOTIENT,
1.88 + BINARY_OP_DIVIDE_MODULUS,
1.89 + BINARY_OP_ALIGN
1.90 + };
1.91 +
1.92 + BinaryOperation operation = BINARY_OP_NONE;
1.93 + if (token == "+")
1.94 + operation = BINARY_OP_ADD;
1.95 + else if (token == "-")
1.96 + operation = BINARY_OP_SUBTRACT;
1.97 + else if (token == "*")
1.98 + operation = BINARY_OP_MULTIPLY;
1.99 + else if (token == "/")
1.100 + operation = BINARY_OP_DIVIDE_QUOTIENT;
1.101 + else if (token == "%")
1.102 + operation = BINARY_OP_DIVIDE_MODULUS;
1.103 + else if (token == "@")
1.104 + operation = BINARY_OP_ALIGN;
1.105 +
1.106 + if (operation != BINARY_OP_NONE) {
1.107 + // Get the operands.
1.108 + ValueType operand1 = ValueType();
1.109 + ValueType operand2 = ValueType();
1.110 + if (!PopValues(&operand1, &operand2)) {
1.111 + BPLOG(ERROR) << "Could not PopValues to get two values for binary "
1.112 + "operation " << token << ": " << expression;
1.113 + return false;
1.114 + }
1.115 +
1.116 + // Perform the operation.
1.117 + ValueType result;
1.118 + switch (operation) {
1.119 + case BINARY_OP_ADD:
1.120 + result = operand1 + operand2;
1.121 + break;
1.122 + case BINARY_OP_SUBTRACT:
1.123 + result = operand1 - operand2;
1.124 + break;
1.125 + case BINARY_OP_MULTIPLY:
1.126 + result = operand1 * operand2;
1.127 + break;
1.128 + case BINARY_OP_DIVIDE_QUOTIENT:
1.129 + result = operand1 / operand2;
1.130 + break;
1.131 + case BINARY_OP_DIVIDE_MODULUS:
1.132 + result = operand1 % operand2;
1.133 + break;
1.134 + case BINARY_OP_ALIGN:
1.135 + result =
1.136 + operand1 & (static_cast<ValueType>(-1) ^ (operand2 - 1));
1.137 + break;
1.138 + case BINARY_OP_NONE:
1.139 + // This will not happen, but compilers will want a default or
1.140 + // BINARY_OP_NONE case.
1.141 + BPLOG(ERROR) << "Not reached!";
1.142 + return false;
1.143 + break;
1.144 + }
1.145 +
1.146 + // Save the result.
1.147 + PushValue(result);
1.148 + } else if (token == "^") {
1.149 + // ^ for unary dereference. Can't dereference without memory.
1.150 + if (!memory_) {
1.151 + BPLOG(ERROR) << "Attempt to dereference without memory: " <<
1.152 + expression;
1.153 + return false;
1.154 + }
1.155 +
1.156 + ValueType address;
1.157 + if (!PopValue(&address)) {
1.158 + BPLOG(ERROR) << "Could not PopValue to get value to dereference: " <<
1.159 + expression;
1.160 + return false;
1.161 + }
1.162 +
1.163 + ValueType value;
1.164 + if (!memory_->GetMemoryAtAddress(address, &value)) {
1.165 + BPLOG(ERROR) << "Could not dereference memory at address " <<
1.166 + HexString(address) << ": " << expression;
1.167 + return false;
1.168 + }
1.169 +
1.170 + PushValue(value);
1.171 + } else if (token == "=") {
1.172 + // = for assignment.
1.173 + ValueType value;
1.174 + if (!PopValue(&value)) {
1.175 + BPLOG(INFO) << "Could not PopValue to get value to assign: " <<
1.176 + expression;
1.177 + return false;
1.178 + }
1.179 +
1.180 + // Assignment is only meaningful when assigning into an identifier.
1.181 + // The identifier must name a variable, not a constant. Variables
1.182 + // begin with '$'.
1.183 + const UniqueString* identifier;
1.184 + if (PopValueOrIdentifier(NULL, &identifier) != POP_RESULT_IDENTIFIER) {
1.185 + BPLOG(ERROR) << "PopValueOrIdentifier returned a value, but an "
1.186 + "identifier is needed to assign " <<
1.187 + HexString(value) << ": " << expression;
1.188 + return false;
1.189 + }
1.190 + if (identifier == ustr__empty() || Index(identifier,0) != '$') {
1.191 + BPLOG(ERROR) << "Can't assign " << HexString(value) << " to " <<
1.192 + identifier << ": " << expression;
1.193 + return false;
1.194 + }
1.195 +
1.196 + dictionary_->set(identifier, value);
1.197 + if (assigned)
1.198 + assigned->set(identifier, true);
1.199 + } else {
1.200 + // Push it onto the stack as-is, but first convert it either to a
1.201 + // ValueType (if a literal) or to a UniqueString* (if an identifier).
1.202 + //
1.203 + // First, try to treat the value as a literal. Literals may have leading
1.204 + // '-' sign, and the entire remaining string must be parseable as
1.205 + // ValueType. If this isn't possible, it can't be a literal, so treat it
1.206 + // as an identifier instead.
1.207 + //
1.208 + // Some versions of the libstdc++, the GNU standard C++ library, have
1.209 + // stream extractors for unsigned integer values that permit a leading
1.210 + // '-' sign (6.0.13); others do not (6.0.9). Since we require it, we
1.211 + // handle it explicitly here.
1.212 + istringstream token_stream(token);
1.213 + ValueType literal = ValueType();
1.214 + bool negative = false;
1.215 + if (token_stream.peek() == '-') {
1.216 + negative = true;
1.217 + token_stream.get();
1.218 + }
1.219 + if (token_stream >> literal && token_stream.peek() == EOF) {
1.220 + PushValue(negative ? (-literal) : literal);
1.221 + } else {
1.222 + PushIdentifier(ToUniqueString(token));
1.223 + }
1.224 + }
1.225 + return true;
1.226 +}
1.227 +
1.228 +template<typename ValueType>
1.229 +bool PostfixEvaluator<ValueType>::EvaluateInternal(
1.230 + const string &expression,
1.231 + DictionaryValidityType *assigned) {
1.232 + // Tokenize, splitting on whitespace.
1.233 + istringstream stream(expression);
1.234 + string token;
1.235 + while (stream >> token) {
1.236 + // Normally, tokens are whitespace-separated, but occasionally, the
1.237 + // assignment operator is smashed up against the next token, i.e.
1.238 + // $T0 $ebp 128 + =$eip $T0 4 + ^ =$ebp $T0 ^ =
1.239 + // This has been observed in program strings produced by MSVS 2010 in LTO
1.240 + // mode.
1.241 + if (token.size() > 1 && token[0] == '=') {
1.242 + if (!EvaluateToken("=", expression, assigned)) {
1.243 + return false;
1.244 + }
1.245 +
1.246 + if (!EvaluateToken(token.substr(1), expression, assigned)) {
1.247 + return false;
1.248 + }
1.249 + } else if (!EvaluateToken(token, expression, assigned)) {
1.250 + return false;
1.251 + }
1.252 + }
1.253 +
1.254 + return true;
1.255 +}
1.256 +
1.257 +template<typename ValueType>
1.258 +bool PostfixEvaluator<ValueType>::Evaluate(const Module::Expr& expr,
1.259 + DictionaryValidityType* assigned) {
1.260 + // The expression is being exevaluated only for its side effects. Skip
1.261 + // expressions that denote values only.
1.262 + if (expr.how_ != Module::kExprPostfix) {
1.263 + BPLOG(ERROR) << "Can't evaluate for side-effects: " << expr;
1.264 + return false;
1.265 + }
1.266 +
1.267 + // Ensure that the stack is cleared before returning.
1.268 + AutoStackClearer<ValueType> clearer(&stack_);
1.269 +
1.270 + if (!EvaluateInternal(expr.postfix_, assigned))
1.271 + return false;
1.272 +
1.273 + // If there's anything left on the stack, it indicates incomplete execution.
1.274 + // This is a failure case. If the stack is empty, evalution was complete
1.275 + // and successful.
1.276 + if (stack_.empty())
1.277 + return true;
1.278 +
1.279 + BPLOG(ERROR) << "Incomplete execution: " << expr;
1.280 + return false;
1.281 +}
1.282 +
1.283 +template<typename ValueType>
1.284 +bool PostfixEvaluator<ValueType>::EvaluateForValue(const Module::Expr& expr,
1.285 + ValueType* result) {
1.286 + switch (expr.how_) {
1.287 +
1.288 + // Postfix expression. Give to the evaluator and return the
1.289 + // one-and-only stack element that should be left over.
1.290 + case Module::kExprPostfix: {
1.291 + // Ensure that the stack is cleared before returning.
1.292 + AutoStackClearer<ValueType> clearer(&stack_);
1.293 +
1.294 + if (!EvaluateInternal(expr.postfix_, NULL))
1.295 + return false;
1.296 +
1.297 + // A successful execution should leave exactly one value on the stack.
1.298 + if (stack_.size() != 1) {
1.299 + BPLOG(ERROR) << "Expression yielded bad number of results: "
1.300 + << "'" << expr << "'";
1.301 + return false;
1.302 + }
1.303 +
1.304 + return PopValue(result);
1.305 + }
1.306 +
1.307 + // Simple-form expressions
1.308 + case Module::kExprSimple:
1.309 + case Module::kExprSimpleMem: {
1.310 + // Look up the base value
1.311 + bool found = false;
1.312 + ValueType v = dictionary_->get(&found, expr.ident_);
1.313 + if (!found) {
1.314 + // The identifier wasn't found in the dictionary. Don't imply any
1.315 + // default value, just fail.
1.316 + static uint64_t n_complaints = 0; // This isn't threadsafe.
1.317 + n_complaints++;
1.318 + if (is_power_of_2(n_complaints)) {
1.319 + BPLOG(INFO) << "Identifier " << FromUniqueString(expr.ident_)
1.320 + << " not in dictionary (kExprSimple{Mem})"
1.321 + << " (shown " << n_complaints << " times)";
1.322 + }
1.323 + return false;
1.324 + }
1.325 +
1.326 + // Form the sum
1.327 + ValueType sum = v + (int64_t)expr.offset_;
1.328 +
1.329 + // and dereference if necessary
1.330 + if (expr.how_ == Module::kExprSimpleMem) {
1.331 + ValueType derefd;
1.332 + if (!memory_ || !memory_->GetMemoryAtAddress(sum, &derefd)) {
1.333 + return false;
1.334 + }
1.335 + *result = derefd;
1.336 + } else {
1.337 + *result = sum;
1.338 + }
1.339 + return true;
1.340 + }
1.341 +
1.342 + default:
1.343 + return false;
1.344 + }
1.345 +}
1.346 +
1.347 +
1.348 +template<typename ValueType>
1.349 +typename PostfixEvaluator<ValueType>::PopResult
1.350 +PostfixEvaluator<ValueType>::PopValueOrIdentifier(
1.351 + ValueType *value, const UniqueString** identifier) {
1.352 + // There needs to be at least one element on the stack to pop.
1.353 + if (!stack_.size())
1.354 + return POP_RESULT_FAIL;
1.355 +
1.356 + StackElem<ValueType> el = stack_.back();
1.357 + stack_.pop_back();
1.358 +
1.359 + if (el.isValue) {
1.360 + if (value)
1.361 + *value = el.u.val;
1.362 + return POP_RESULT_VALUE;
1.363 + } else {
1.364 + if (identifier)
1.365 + *identifier = el.u.ustr;
1.366 + return POP_RESULT_IDENTIFIER;
1.367 + }
1.368 +}
1.369 +
1.370 +
1.371 +template<typename ValueType>
1.372 +bool PostfixEvaluator<ValueType>::PopValue(ValueType *value) {
1.373 + ValueType literal = ValueType();
1.374 + const UniqueString* token;
1.375 + PopResult result;
1.376 + if ((result = PopValueOrIdentifier(&literal, &token)) == POP_RESULT_FAIL) {
1.377 + return false;
1.378 + } else if (result == POP_RESULT_VALUE) {
1.379 + // This is the easy case.
1.380 + *value = literal;
1.381 + } else { // result == POP_RESULT_IDENTIFIER
1.382 + // There was an identifier at the top of the stack. Resolve it to a
1.383 + // value by looking it up in the dictionary.
1.384 + bool found = false;
1.385 + ValueType v = dictionary_->get(&found, token);
1.386 + if (!found) {
1.387 + // The identifier wasn't found in the dictionary. Don't imply any
1.388 + // default value, just fail.
1.389 + BPLOG(INFO) << "Identifier " << FromUniqueString(token)
1.390 + << " not in dictionary";
1.391 + return false;
1.392 + }
1.393 +
1.394 + *value = v;
1.395 + }
1.396 +
1.397 + return true;
1.398 +}
1.399 +
1.400 +
1.401 +template<typename ValueType>
1.402 +bool PostfixEvaluator<ValueType>::PopValues(ValueType *value1,
1.403 + ValueType *value2) {
1.404 + return PopValue(value2) && PopValue(value1);
1.405 +}
1.406 +
1.407 +
1.408 +template<typename ValueType>
1.409 +void PostfixEvaluator<ValueType>::PushValue(const ValueType &value) {
1.410 + StackElem<ValueType> el(value);
1.411 + stack_.push_back(el);
1.412 +}
1.413 +
1.414 +template<typename ValueType>
1.415 +void PostfixEvaluator<ValueType>::PushIdentifier(const UniqueString* str) {
1.416 + StackElem<ValueType> el(str);
1.417 + stack_.push_back(el);
1.418 +}
1.419 +
1.420 +
1.421 +} // namespace google_breakpad
1.422 +
1.423 +
1.424 +#endif // PROCESSOR_POSTFIX_EVALUATOR_INL_H__
