Home | History | Annotate | Download | only in processor 
      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 
     51 namespace google_breakpad {
     52 
     53 using std::istringstream;
     54 using std::ostringstream;
     55 
     56 
     57 // A small class used in Evaluate to make sure to clean up the stack
     58 // before returning failure.
     59 class 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 
     69 template<typename ValueType>
     70 bool 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 
    204 template<typename ValueType>
    205 bool 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 
    233 template<typename ValueType>
    234 bool 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 
    252 template<typename ValueType>
    253 bool 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 
    271 template<typename ValueType>
    272 typename PostfixEvaluator<ValueType>::PopResult
    273 PostfixEvaluator<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 
    316 template<typename ValueType>
    317 bool 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 
    345 template<typename ValueType>
    346 bool PostfixEvaluator<ValueType>::PopValues(ValueType *value1,
    347                                             ValueType *value2) {
    348   return PopValue(value2) && PopValue(value1);
    349 }
    350 
    351 
    352 template<typename ValueType>
    353 void 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