Home | History | Annotate | Download | only in RuntimeDyld 
      1 //===--- RuntimeDyldChecker.cpp - RuntimeDyld tester framework --*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #include "llvm/ExecutionEngine/RuntimeDyldChecker.h"
     11 #include "RuntimeDyldCheckerImpl.h"
     12 #include "RuntimeDyldImpl.h"
     13 #include "llvm/ADT/STLExtras.h"
     14 #include "llvm/MC/MCContext.h"
     15 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
     16 #include "llvm/MC/MCInst.h"
     17 #include "llvm/Support/Path.h"
     18 #include <cctype>
     19 #include <memory>
     20 #include <utility>
     21 
     22 #define DEBUG_TYPE "rtdyld"
     23 
     24 using namespace llvm;
     25 
     26 namespace llvm {
     27 
     28 // Helper class that implements the language evaluated by RuntimeDyldChecker.
     29 class RuntimeDyldCheckerExprEval {
     30 public:
     31   RuntimeDyldCheckerExprEval(const RuntimeDyldCheckerImpl &Checker,
     32                              raw_ostream &ErrStream)
     33       : Checker(Checker) {}
     34 
     35   bool evaluate(StringRef Expr) const {
     36     // Expect equality expression of the form 'LHS = RHS'.
     37     Expr = Expr.trim();
     38     size_t EQIdx = Expr.find('=');
     39 
     40     ParseContext OutsideLoad(false);
     41 
     42     // Evaluate LHS.
     43     StringRef LHSExpr = Expr.substr(0, EQIdx).rtrim();
     44     StringRef RemainingExpr;
     45     EvalResult LHSResult;
     46     std::tie(LHSResult, RemainingExpr) =
     47         evalComplexExpr(evalSimpleExpr(LHSExpr, OutsideLoad), OutsideLoad);
     48     if (LHSResult.hasError())
     49       return handleError(Expr, LHSResult);
     50     if (RemainingExpr != "")
     51       return handleError(Expr, unexpectedToken(RemainingExpr, LHSExpr, ""));
     52 
     53     // Evaluate RHS.
     54     StringRef RHSExpr = Expr.substr(EQIdx + 1).ltrim();
     55     EvalResult RHSResult;
     56     std::tie(RHSResult, RemainingExpr) =
     57         evalComplexExpr(evalSimpleExpr(RHSExpr, OutsideLoad), OutsideLoad);
     58     if (RHSResult.hasError())
     59       return handleError(Expr, RHSResult);
     60     if (RemainingExpr != "")
     61       return handleError(Expr, unexpectedToken(RemainingExpr, RHSExpr, ""));
     62 
     63     if (LHSResult.getValue() != RHSResult.getValue()) {
     64       Checker.ErrStream << "Expression '" << Expr << "' is false: "
     65                         << format("0x%" PRIx64, LHSResult.getValue())
     66                         << " != " << format("0x%" PRIx64, RHSResult.getValue())
     67                         << "\n";
     68       return false;
     69     }
     70     return true;
     71   }
     72 
     73 private:
     74   // RuntimeDyldCheckerExprEval requires some context when parsing exprs. In
     75   // particular, it needs to know whether a symbol is being evaluated in the
     76   // context of a load, in which case we want the linker's local address for
     77   // the symbol, or outside of a load, in which case we want the symbol's
     78   // address in the remote target.
     79 
     80   struct ParseContext {
     81     bool IsInsideLoad;
     82     ParseContext(bool IsInsideLoad) : IsInsideLoad(IsInsideLoad) {}
     83   };
     84 
     85   const RuntimeDyldCheckerImpl &Checker;
     86 
     87   enum class BinOpToken : unsigned {
     88     Invalid,
     89     Add,
     90     Sub,
     91     BitwiseAnd,
     92     BitwiseOr,
     93     ShiftLeft,
     94     ShiftRight
     95   };
     96 
     97   class EvalResult {
     98   public:
     99     EvalResult() : Value(0), ErrorMsg("") {}
    100     EvalResult(uint64_t Value) : Value(Value), ErrorMsg("") {}
    101     EvalResult(std::string ErrorMsg)
    102         : Value(0), ErrorMsg(std::move(ErrorMsg)) {}
    103     uint64_t getValue() const { return Value; }
    104     bool hasError() const { return ErrorMsg != ""; }
    105     const std::string &getErrorMsg() const { return ErrorMsg; }
    106 
    107   private:
    108     uint64_t Value;
    109     std::string ErrorMsg;
    110   };
    111 
    112   StringRef getTokenForError(StringRef Expr) const {
    113     if (Expr.empty())
    114       return "";
    115 
    116     StringRef Token, Remaining;
    117     if (isalpha(Expr[0]))
    118       std::tie(Token, Remaining) = parseSymbol(Expr);
    119     else if (isdigit(Expr[0]))
    120       std::tie(Token, Remaining) = parseNumberString(Expr);
    121     else {
    122       unsigned TokLen = 1;
    123       if (Expr.startswith("<<") || Expr.startswith(">>"))
    124         TokLen = 2;
    125       Token = Expr.substr(0, TokLen);
    126     }
    127     return Token;
    128   }
    129 
    130   EvalResult unexpectedToken(StringRef TokenStart, StringRef SubExpr,
    131                              StringRef ErrText) const {
    132     std::string ErrorMsg("Encountered unexpected token '");
    133     ErrorMsg += getTokenForError(TokenStart);
    134     if (SubExpr != "") {
    135       ErrorMsg += "' while parsing subexpression '";
    136       ErrorMsg += SubExpr;
    137     }
    138     ErrorMsg += "'";
    139     if (ErrText != "") {
    140       ErrorMsg += " ";
    141       ErrorMsg += ErrText;
    142     }
    143     return EvalResult(std::move(ErrorMsg));
    144   }
    145 
    146   bool handleError(StringRef Expr, const EvalResult &R) const {
    147     assert(R.hasError() && "Not an error result.");
    148     Checker.ErrStream << "Error evaluating expression '" << Expr
    149                       << "': " << R.getErrorMsg() << "\n";
    150     return false;
    151   }
    152 
    153   std::pair<BinOpToken, StringRef> parseBinOpToken(StringRef Expr) const {
    154     if (Expr.empty())
    155       return std::make_pair(BinOpToken::Invalid, "");
    156 
    157     // Handle the two 2-character tokens.
    158     if (Expr.startswith("<<"))
    159       return std::make_pair(BinOpToken::ShiftLeft, Expr.substr(2).ltrim());
    160     if (Expr.startswith(">>"))
    161       return std::make_pair(BinOpToken::ShiftRight, Expr.substr(2).ltrim());
    162 
    163     // Handle one-character tokens.
    164     BinOpToken Op;
    165     switch (Expr[0]) {
    166     default:
    167       return std::make_pair(BinOpToken::Invalid, Expr);
    168     case '+':
    169       Op = BinOpToken::Add;
    170       break;
    171     case '-':
    172       Op = BinOpToken::Sub;
    173       break;
    174     case '&':
    175       Op = BinOpToken::BitwiseAnd;
    176       break;
    177     case '|':
    178       Op = BinOpToken::BitwiseOr;
    179       break;
    180     }
    181 
    182     return std::make_pair(Op, Expr.substr(1).ltrim());
    183   }
    184 
    185   EvalResult computeBinOpResult(BinOpToken Op, const EvalResult &LHSResult,
    186                                 const EvalResult &RHSResult) const {
    187     switch (Op) {
    188     default:
    189       llvm_unreachable("Tried to evaluate unrecognized operation.");
    190     case BinOpToken::Add:
    191       return EvalResult(LHSResult.getValue() + RHSResult.getValue());
    192     case BinOpToken::Sub:
    193       return EvalResult(LHSResult.getValue() - RHSResult.getValue());
    194     case BinOpToken::BitwiseAnd:
    195       return EvalResult(LHSResult.getValue() & RHSResult.getValue());
    196     case BinOpToken::BitwiseOr:
    197       return EvalResult(LHSResult.getValue() | RHSResult.getValue());
    198     case BinOpToken::ShiftLeft:
    199       return EvalResult(LHSResult.getValue() << RHSResult.getValue());
    200     case BinOpToken::ShiftRight:
    201       return EvalResult(LHSResult.getValue() >> RHSResult.getValue());
    202     }
    203   }
    204 
    205   // Parse a symbol and return a (string, string) pair representing the symbol
    206   // name and expression remaining to be parsed.
    207   std::pair<StringRef, StringRef> parseSymbol(StringRef Expr) const {
    208     size_t FirstNonSymbol = Expr.find_first_not_of("0123456789"
    209                                                    "abcdefghijklmnopqrstuvwxyz"
    210                                                    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    211                                                    ":_.$");
    212     return std::make_pair(Expr.substr(0, FirstNonSymbol),
    213                           Expr.substr(FirstNonSymbol).ltrim());
    214   }
    215 
    216   // Evaluate a call to decode_operand. Decode the instruction operand at the
    217   // given symbol and get the value of the requested operand.
    218   // Returns an error if the instruction cannot be decoded, or the requested
    219   // operand is not an immediate.
    220   // On success, retuns a pair containing the value of the operand, plus
    221   // the expression remaining to be evaluated.
    222   std::pair<EvalResult, StringRef> evalDecodeOperand(StringRef Expr) const {
    223     if (!Expr.startswith("("))
    224       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
    225     StringRef RemainingExpr = Expr.substr(1).ltrim();
    226     StringRef Symbol;
    227     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
    228 
    229     if (!Checker.isSymbolValid(Symbol))
    230       return std::make_pair(
    231           EvalResult(("Cannot decode unknown symbol '" + Symbol + "'").str()),
    232           "");
    233 
    234     if (!RemainingExpr.startswith(","))
    235       return std::make_pair(
    236           unexpectedToken(RemainingExpr, RemainingExpr, "expected ','"), "");
    237     RemainingExpr = RemainingExpr.substr(1).ltrim();
    238 
    239     EvalResult OpIdxExpr;
    240     std::tie(OpIdxExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
    241     if (OpIdxExpr.hasError())
    242       return std::make_pair(OpIdxExpr, "");
    243 
    244     if (!RemainingExpr.startswith(")"))
    245       return std::make_pair(
    246           unexpectedToken(RemainingExpr, RemainingExpr, "expected ')'"), "");
    247     RemainingExpr = RemainingExpr.substr(1).ltrim();
    248 
    249     MCInst Inst;
    250     uint64_t Size;
    251     if (!decodeInst(Symbol, Inst, Size))
    252       return std::make_pair(
    253           EvalResult(("Couldn't decode instruction at '" + Symbol + "'").str()),
    254           "");
    255 
    256     unsigned OpIdx = OpIdxExpr.getValue();
    257     if (OpIdx >= Inst.getNumOperands()) {
    258       std::string ErrMsg;
    259       raw_string_ostream ErrMsgStream(ErrMsg);
    260       ErrMsgStream << "Invalid operand index '" << format("%i", OpIdx)
    261                    << "' for instruction '" << Symbol
    262                    << "'. Instruction has only "
    263                    << format("%i", Inst.getNumOperands())
    264                    << " operands.\nInstruction is:\n  ";
    265       Inst.dump_pretty(ErrMsgStream, Checker.InstPrinter);
    266       return std::make_pair(EvalResult(ErrMsgStream.str()), "");
    267     }
    268 
    269     const MCOperand &Op = Inst.getOperand(OpIdx);
    270     if (!Op.isImm()) {
    271       std::string ErrMsg;
    272       raw_string_ostream ErrMsgStream(ErrMsg);
    273       ErrMsgStream << "Operand '" << format("%i", OpIdx) << "' of instruction '"
    274                    << Symbol << "' is not an immediate.\nInstruction is:\n  ";
    275       Inst.dump_pretty(ErrMsgStream, Checker.InstPrinter);
    276 
    277       return std::make_pair(EvalResult(ErrMsgStream.str()), "");
    278     }
    279 
    280     return std::make_pair(EvalResult(Op.getImm()), RemainingExpr);
    281   }
    282 
    283   // Evaluate a call to next_pc.
    284   // Decode the instruction at the given symbol and return the following program
    285   // counter.
    286   // Returns an error if the instruction cannot be decoded.
    287   // On success, returns a pair containing the next PC, plus of the
    288   // expression remaining to be evaluated.
    289   std::pair<EvalResult, StringRef> evalNextPC(StringRef Expr,
    290                                               ParseContext PCtx) const {
    291     if (!Expr.startswith("("))
    292       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
    293     StringRef RemainingExpr = Expr.substr(1).ltrim();
    294     StringRef Symbol;
    295     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
    296 
    297     if (!Checker.isSymbolValid(Symbol))
    298       return std::make_pair(
    299           EvalResult(("Cannot decode unknown symbol '" + Symbol + "'").str()),
    300           "");
    301 
    302     if (!RemainingExpr.startswith(")"))
    303       return std::make_pair(
    304           unexpectedToken(RemainingExpr, RemainingExpr, "expected ')'"), "");
    305     RemainingExpr = RemainingExpr.substr(1).ltrim();
    306 
    307     MCInst Inst;
    308     uint64_t InstSize;
    309     if (!decodeInst(Symbol, Inst, InstSize))
    310       return std::make_pair(
    311           EvalResult(("Couldn't decode instruction at '" + Symbol + "'").str()),
    312           "");
    313 
    314     uint64_t SymbolAddr = PCtx.IsInsideLoad
    315                               ? Checker.getSymbolLocalAddr(Symbol)
    316                               : Checker.getSymbolRemoteAddr(Symbol);
    317     uint64_t NextPC = SymbolAddr + InstSize;
    318 
    319     return std::make_pair(EvalResult(NextPC), RemainingExpr);
    320   }
    321 
    322   // Evaluate a call to stub_addr.
    323   // Look up and return the address of the stub for the given
    324   // (<file name>, <section name>, <symbol name>) tuple.
    325   // On success, returns a pair containing the stub address, plus the expression
    326   // remaining to be evaluated.
    327   std::pair<EvalResult, StringRef> evalStubAddr(StringRef Expr,
    328                                                 ParseContext PCtx) const {
    329     if (!Expr.startswith("("))
    330       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
    331     StringRef RemainingExpr = Expr.substr(1).ltrim();
    332 
    333     // Handle file-name specially, as it may contain characters that aren't
    334     // legal for symbols.
    335     StringRef FileName;
    336     size_t ComaIdx = RemainingExpr.find(',');
    337     FileName = RemainingExpr.substr(0, ComaIdx).rtrim();
    338     RemainingExpr = RemainingExpr.substr(ComaIdx).ltrim();
    339 
    340     if (!RemainingExpr.startswith(","))
    341       return std::make_pair(
    342           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
    343     RemainingExpr = RemainingExpr.substr(1).ltrim();
    344 
    345     StringRef SectionName;
    346     std::tie(SectionName, RemainingExpr) = parseSymbol(RemainingExpr);
    347 
    348     if (!RemainingExpr.startswith(","))
    349       return std::make_pair(
    350           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
    351     RemainingExpr = RemainingExpr.substr(1).ltrim();
    352 
    353     StringRef Symbol;
    354     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
    355 
    356     if (!RemainingExpr.startswith(")"))
    357       return std::make_pair(
    358           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
    359     RemainingExpr = RemainingExpr.substr(1).ltrim();
    360 
    361     uint64_t StubAddr;
    362     std::string ErrorMsg = "";
    363     std::tie(StubAddr, ErrorMsg) = Checker.getStubAddrFor(
    364         FileName, SectionName, Symbol, PCtx.IsInsideLoad);
    365 
    366     if (ErrorMsg != "")
    367       return std::make_pair(EvalResult(ErrorMsg), "");
    368 
    369     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
    370   }
    371 
    372   std::pair<EvalResult, StringRef> evalSectionAddr(StringRef Expr,
    373                                                    ParseContext PCtx) const {
    374     if (!Expr.startswith("("))
    375       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
    376     StringRef RemainingExpr = Expr.substr(1).ltrim();
    377 
    378     // Handle file-name specially, as it may contain characters that aren't
    379     // legal for symbols.
    380     StringRef FileName;
    381     size_t ComaIdx = RemainingExpr.find(',');
    382     FileName = RemainingExpr.substr(0, ComaIdx).rtrim();
    383     RemainingExpr = RemainingExpr.substr(ComaIdx).ltrim();
    384 
    385     if (!RemainingExpr.startswith(","))
    386       return std::make_pair(
    387           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
    388     RemainingExpr = RemainingExpr.substr(1).ltrim();
    389 
    390     StringRef SectionName;
    391     std::tie(SectionName, RemainingExpr) = parseSymbol(RemainingExpr);
    392 
    393     if (!RemainingExpr.startswith(")"))
    394       return std::make_pair(
    395           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
    396     RemainingExpr = RemainingExpr.substr(1).ltrim();
    397 
    398     uint64_t StubAddr;
    399     std::string ErrorMsg = "";
    400     std::tie(StubAddr, ErrorMsg) = Checker.getSectionAddr(
    401         FileName, SectionName, PCtx.IsInsideLoad);
    402 
    403     if (ErrorMsg != "")
    404       return std::make_pair(EvalResult(ErrorMsg), "");
    405 
    406     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
    407   }
    408 
    409   // Evaluate an identiefer expr, which may be a symbol, or a call to
    410   // one of the builtin functions: get_insn_opcode or get_insn_length.
    411   // Return the result, plus the expression remaining to be parsed.
    412   std::pair<EvalResult, StringRef> evalIdentifierExpr(StringRef Expr,
    413                                                       ParseContext PCtx) const {
    414     StringRef Symbol;
    415     StringRef RemainingExpr;
    416     std::tie(Symbol, RemainingExpr) = parseSymbol(Expr);
    417 
    418     // Check for builtin function calls.
    419     if (Symbol == "decode_operand")
    420       return evalDecodeOperand(RemainingExpr);
    421     else if (Symbol == "next_pc")
    422       return evalNextPC(RemainingExpr, PCtx);
    423     else if (Symbol == "stub_addr")
    424       return evalStubAddr(RemainingExpr, PCtx);
    425     else if (Symbol == "section_addr")
    426       return evalSectionAddr(RemainingExpr, PCtx);
    427 
    428     if (!Checker.isSymbolValid(Symbol)) {
    429       std::string ErrMsg("No known address for symbol '");
    430       ErrMsg += Symbol;
    431       ErrMsg += "'";
    432       if (Symbol.startswith("L"))
    433         ErrMsg += " (this appears to be an assembler local label - "
    434                   " perhaps drop the 'L'?)";
    435 
    436       return std::make_pair(EvalResult(ErrMsg), "");
    437     }
    438 
    439     // The value for the symbol depends on the context we're evaluating in:
    440     // Inside a load this is the address in the linker's memory, outside a
    441     // load it's the address in the target processes memory.
    442     uint64_t Value = PCtx.IsInsideLoad ? Checker.getSymbolLocalAddr(Symbol)
    443                                        : Checker.getSymbolRemoteAddr(Symbol);
    444 
    445     // Looks like a plain symbol reference.
    446     return std::make_pair(EvalResult(Value), RemainingExpr);
    447   }
    448 
    449   // Parse a number (hexadecimal or decimal) and return a (string, string)
    450   // pair representing the number and the expression remaining to be parsed.
    451   std::pair<StringRef, StringRef> parseNumberString(StringRef Expr) const {
    452     size_t FirstNonDigit = StringRef::npos;
    453     if (Expr.startswith("0x")) {
    454       FirstNonDigit = Expr.find_first_not_of("0123456789abcdefABCDEF", 2);
    455       if (FirstNonDigit == StringRef::npos)
    456         FirstNonDigit = Expr.size();
    457     } else {
    458       FirstNonDigit = Expr.find_first_not_of("0123456789");
    459       if (FirstNonDigit == StringRef::npos)
    460         FirstNonDigit = Expr.size();
    461     }
    462     return std::make_pair(Expr.substr(0, FirstNonDigit),
    463                           Expr.substr(FirstNonDigit));
    464   }
    465 
    466   // Evaluate a constant numeric expression (hexidecimal or decimal) and
    467   // return a pair containing the result, and the expression remaining to be
    468   // evaluated.
    469   std::pair<EvalResult, StringRef> evalNumberExpr(StringRef Expr) const {
    470     StringRef ValueStr;
    471     StringRef RemainingExpr;
    472     std::tie(ValueStr, RemainingExpr) = parseNumberString(Expr);
    473 
    474     if (ValueStr.empty() || !isdigit(ValueStr[0]))
    475       return std::make_pair(
    476           unexpectedToken(RemainingExpr, RemainingExpr, "expected number"), "");
    477     uint64_t Value;
    478     ValueStr.getAsInteger(0, Value);
    479     return std::make_pair(EvalResult(Value), RemainingExpr);
    480   }
    481 
    482   // Evaluate an expression of the form "(<expr>)" and return a pair
    483   // containing the result of evaluating <expr>, plus the expression
    484   // remaining to be parsed.
    485   std::pair<EvalResult, StringRef> evalParensExpr(StringRef Expr,
    486                                                   ParseContext PCtx) const {
    487     assert(Expr.startswith("(") && "Not a parenthesized expression");
    488     EvalResult SubExprResult;
    489     StringRef RemainingExpr;
    490     std::tie(SubExprResult, RemainingExpr) =
    491         evalComplexExpr(evalSimpleExpr(Expr.substr(1).ltrim(), PCtx), PCtx);
    492     if (SubExprResult.hasError())
    493       return std::make_pair(SubExprResult, "");
    494     if (!RemainingExpr.startswith(")"))
    495       return std::make_pair(
    496           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
    497     RemainingExpr = RemainingExpr.substr(1).ltrim();
    498     return std::make_pair(SubExprResult, RemainingExpr);
    499   }
    500 
    501   // Evaluate an expression in one of the following forms:
    502   //   *{<number>}<expr>
    503   // Return a pair containing the result, plus the expression remaining to be
    504   // parsed.
    505   std::pair<EvalResult, StringRef> evalLoadExpr(StringRef Expr) const {
    506     assert(Expr.startswith("*") && "Not a load expression");
    507     StringRef RemainingExpr = Expr.substr(1).ltrim();
    508 
    509     // Parse read size.
    510     if (!RemainingExpr.startswith("{"))
    511       return std::make_pair(EvalResult("Expected '{' following '*'."), "");
    512     RemainingExpr = RemainingExpr.substr(1).ltrim();
    513     EvalResult ReadSizeExpr;
    514     std::tie(ReadSizeExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
    515     if (ReadSizeExpr.hasError())
    516       return std::make_pair(ReadSizeExpr, RemainingExpr);
    517     uint64_t ReadSize = ReadSizeExpr.getValue();
    518     if (ReadSize < 1 || ReadSize > 8)
    519       return std::make_pair(EvalResult("Invalid size for dereference."), "");
    520     if (!RemainingExpr.startswith("}"))
    521       return std::make_pair(EvalResult("Missing '}' for dereference."), "");
    522     RemainingExpr = RemainingExpr.substr(1).ltrim();
    523 
    524     // Evaluate the expression representing the load address.
    525     ParseContext LoadCtx(true);
    526     EvalResult LoadAddrExprResult;
    527     std::tie(LoadAddrExprResult, RemainingExpr) =
    528         evalComplexExpr(evalSimpleExpr(RemainingExpr, LoadCtx), LoadCtx);
    529 
    530     if (LoadAddrExprResult.hasError())
    531       return std::make_pair(LoadAddrExprResult, "");
    532 
    533     uint64_t LoadAddr = LoadAddrExprResult.getValue();
    534 
    535     return std::make_pair(
    536         EvalResult(Checker.readMemoryAtAddr(LoadAddr, ReadSize)),
    537         RemainingExpr);
    538   }
    539 
    540   // Evaluate a "simple" expression. This is any expression that _isn't_ an
    541   // un-parenthesized binary expression.
    542   //
    543   // "Simple" expressions can be optionally bit-sliced. See evalSlicedExpr.
    544   //
    545   // Returns a pair containing the result of the evaluation, plus the
    546   // expression remaining to be parsed.
    547   std::pair<EvalResult, StringRef> evalSimpleExpr(StringRef Expr,
    548                                                   ParseContext PCtx) const {
    549     EvalResult SubExprResult;
    550     StringRef RemainingExpr;
    551 
    552     if (Expr.empty())
    553       return std::make_pair(EvalResult("Unexpected end of expression"), "");
    554 
    555     if (Expr[0] == '(')
    556       std::tie(SubExprResult, RemainingExpr) = evalParensExpr(Expr, PCtx);
    557     else if (Expr[0] == '*')
    558       std::tie(SubExprResult, RemainingExpr) = evalLoadExpr(Expr);
    559     else if (isalpha(Expr[0]) || Expr[0] == '_')
    560       std::tie(SubExprResult, RemainingExpr) = evalIdentifierExpr(Expr, PCtx);
    561     else if (isdigit(Expr[0]))
    562       std::tie(SubExprResult, RemainingExpr) = evalNumberExpr(Expr);
    563     else
    564       return std::make_pair(
    565           unexpectedToken(Expr, Expr,
    566                           "expected '(', '*', identifier, or number"), "");
    567 
    568     if (SubExprResult.hasError())
    569       return std::make_pair(SubExprResult, RemainingExpr);
    570 
    571     // Evaluate bit-slice if present.
    572     if (RemainingExpr.startswith("["))
    573       std::tie(SubExprResult, RemainingExpr) =
    574           evalSliceExpr(std::make_pair(SubExprResult, RemainingExpr));
    575 
    576     return std::make_pair(SubExprResult, RemainingExpr);
    577   }
    578 
    579   // Evaluate a bit-slice of an expression.
    580   // A bit-slice has the form "<expr>[high:low]". The result of evaluating a
    581   // slice is the bits between high and low (inclusive) in the original
    582   // expression, right shifted so that the "low" bit is in position 0 in the
    583   // result.
    584   // Returns a pair containing the result of the slice operation, plus the
    585   // expression remaining to be parsed.
    586   std::pair<EvalResult, StringRef>
    587   evalSliceExpr(const std::pair<EvalResult, StringRef> &Ctx) const {
    588     EvalResult SubExprResult;
    589     StringRef RemainingExpr;
    590     std::tie(SubExprResult, RemainingExpr) = Ctx;
    591 
    592     assert(RemainingExpr.startswith("[") && "Not a slice expr.");
    593     RemainingExpr = RemainingExpr.substr(1).ltrim();
    594 
    595     EvalResult HighBitExpr;
    596     std::tie(HighBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
    597 
    598     if (HighBitExpr.hasError())
    599       return std::make_pair(HighBitExpr, RemainingExpr);
    600 
    601     if (!RemainingExpr.startswith(":"))
    602       return std::make_pair(
    603           unexpectedToken(RemainingExpr, RemainingExpr, "expected ':'"), "");
    604     RemainingExpr = RemainingExpr.substr(1).ltrim();
    605 
    606     EvalResult LowBitExpr;
    607     std::tie(LowBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
    608 
    609     if (LowBitExpr.hasError())
    610       return std::make_pair(LowBitExpr, RemainingExpr);
    611 
    612     if (!RemainingExpr.startswith("]"))
    613       return std::make_pair(
    614           unexpectedToken(RemainingExpr, RemainingExpr, "expected ']'"), "");
    615     RemainingExpr = RemainingExpr.substr(1).ltrim();
    616 
    617     unsigned HighBit = HighBitExpr.getValue();
    618     unsigned LowBit = LowBitExpr.getValue();
    619     uint64_t Mask = ((uint64_t)1 << (HighBit - LowBit + 1)) - 1;
    620     uint64_t SlicedValue = (SubExprResult.getValue() >> LowBit) & Mask;
    621     return std::make_pair(EvalResult(SlicedValue), RemainingExpr);
    622   }
    623 
    624   // Evaluate a "complex" expression.
    625   // Takes an already evaluated subexpression and checks for the presence of a
    626   // binary operator, computing the result of the binary operation if one is
    627   // found. Used to make arithmetic expressions left-associative.
    628   // Returns a pair containing the ultimate result of evaluating the
    629   // expression, plus the expression remaining to be evaluated.
    630   std::pair<EvalResult, StringRef>
    631   evalComplexExpr(const std::pair<EvalResult, StringRef> &LHSAndRemaining,
    632                   ParseContext PCtx) const {
    633     EvalResult LHSResult;
    634     StringRef RemainingExpr;
    635     std::tie(LHSResult, RemainingExpr) = LHSAndRemaining;
    636 
    637     // If there was an error, or there's nothing left to evaluate, return the
    638     // result.
    639     if (LHSResult.hasError() || RemainingExpr == "")
    640       return std::make_pair(LHSResult, RemainingExpr);
    641 
    642     // Otherwise check if this is a binary expressioan.
    643     BinOpToken BinOp;
    644     std::tie(BinOp, RemainingExpr) = parseBinOpToken(RemainingExpr);
    645 
    646     // If this isn't a recognized expression just return.
    647     if (BinOp == BinOpToken::Invalid)
    648       return std::make_pair(LHSResult, RemainingExpr);
    649 
    650     // This is a recognized bin-op. Evaluate the RHS, then evaluate the binop.
    651     EvalResult RHSResult;
    652     std::tie(RHSResult, RemainingExpr) = evalSimpleExpr(RemainingExpr, PCtx);
    653 
    654     // If there was an error evaluating the RHS, return it.
    655     if (RHSResult.hasError())
    656       return std::make_pair(RHSResult, RemainingExpr);
    657 
    658     // This is a binary expression - evaluate and try to continue as a
    659     // complex expr.
    660     EvalResult ThisResult(computeBinOpResult(BinOp, LHSResult, RHSResult));
    661 
    662     return evalComplexExpr(std::make_pair(ThisResult, RemainingExpr), PCtx);
    663   }
    664 
    665   bool decodeInst(StringRef Symbol, MCInst &Inst, uint64_t &Size) const {
    666     MCDisassembler *Dis = Checker.Disassembler;
    667     StringRef SectionMem = Checker.getSubsectionStartingAt(Symbol);
    668     ArrayRef<uint8_t> SectionBytes(
    669         reinterpret_cast<const uint8_t *>(SectionMem.data()),
    670         SectionMem.size());
    671 
    672     MCDisassembler::DecodeStatus S =
    673         Dis->getInstruction(Inst, Size, SectionBytes, 0, nulls(), nulls());
    674 
    675     return (S == MCDisassembler::Success);
    676   }
    677 };
    678 }
    679 
    680 RuntimeDyldCheckerImpl::RuntimeDyldCheckerImpl(RuntimeDyld &RTDyld,
    681                                                MCDisassembler *Disassembler,
    682                                                MCInstPrinter *InstPrinter,
    683                                                raw_ostream &ErrStream)
    684     : RTDyld(RTDyld), Disassembler(Disassembler), InstPrinter(InstPrinter),
    685       ErrStream(ErrStream) {
    686   RTDyld.Checker = this;
    687 }
    688 
    689 bool RuntimeDyldCheckerImpl::check(StringRef CheckExpr) const {
    690   CheckExpr = CheckExpr.trim();
    691   DEBUG(dbgs() << "RuntimeDyldChecker: Checking '" << CheckExpr << "'...\n");
    692   RuntimeDyldCheckerExprEval P(*this, ErrStream);
    693   bool Result = P.evaluate(CheckExpr);
    694   (void)Result;
    695   DEBUG(dbgs() << "RuntimeDyldChecker: '" << CheckExpr << "' "
    696                << (Result ? "passed" : "FAILED") << ".\n");
    697   return Result;
    698 }
    699 
    700 bool RuntimeDyldCheckerImpl::checkAllRulesInBuffer(StringRef RulePrefix,
    701                                                    MemoryBuffer *MemBuf) const {
    702   bool DidAllTestsPass = true;
    703   unsigned NumRules = 0;
    704 
    705   const char *LineStart = MemBuf->getBufferStart();
    706 
    707   // Eat whitespace.
    708   while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
    709     ++LineStart;
    710 
    711   while (LineStart != MemBuf->getBufferEnd() && *LineStart != '\0') {
    712     const char *LineEnd = LineStart;
    713     while (LineEnd != MemBuf->getBufferEnd() && *LineEnd != '\r' &&
    714            *LineEnd != '\n')
    715       ++LineEnd;
    716 
    717     StringRef Line(LineStart, LineEnd - LineStart);
    718     if (Line.startswith(RulePrefix)) {
    719       DidAllTestsPass &= check(Line.substr(RulePrefix.size()));
    720       ++NumRules;
    721     }
    722 
    723     // Eat whitespace.
    724     LineStart = LineEnd;
    725     while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
    726       ++LineStart;
    727   }
    728   return DidAllTestsPass && (NumRules != 0);
    729 }
    730 
    731 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const {
    732   if (getRTDyld().getSymbol(Symbol))
    733     return true;
    734   return !!getRTDyld().Resolver.findSymbol(Symbol);
    735 }
    736 
    737 uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const {
    738   return static_cast<uint64_t>(
    739       reinterpret_cast<uintptr_t>(getRTDyld().getSymbolLocalAddress(Symbol)));
    740 }
    741 
    742 uint64_t RuntimeDyldCheckerImpl::getSymbolRemoteAddr(StringRef Symbol) const {
    743   if (auto InternalSymbol = getRTDyld().getSymbol(Symbol))
    744     return InternalSymbol.getAddress();
    745   return getRTDyld().Resolver.findSymbol(Symbol).getAddress();
    746 }
    747 
    748 uint64_t RuntimeDyldCheckerImpl::readMemoryAtAddr(uint64_t SrcAddr,
    749                                                   unsigned Size) const {
    750   uintptr_t PtrSizedAddr = static_cast<uintptr_t>(SrcAddr);
    751   assert(PtrSizedAddr == SrcAddr && "Linker memory pointer out-of-range.");
    752   uint8_t *Src = reinterpret_cast<uint8_t*>(PtrSizedAddr);
    753   return getRTDyld().readBytesUnaligned(Src, Size);
    754 }
    755 
    756 
    757 std::pair<const RuntimeDyldCheckerImpl::SectionAddressInfo*, std::string>
    758 RuntimeDyldCheckerImpl::findSectionAddrInfo(StringRef FileName,
    759                                             StringRef SectionName) const {
    760 
    761   auto SectionMapItr = Stubs.find(FileName);
    762   if (SectionMapItr == Stubs.end()) {
    763     std::string ErrorMsg = "File '";
    764     ErrorMsg += FileName;
    765     ErrorMsg += "' not found. ";
    766     if (Stubs.empty())
    767       ErrorMsg += "No stubs registered.";
    768     else {
    769       ErrorMsg += "Available files are:";
    770       for (const auto& StubEntry : Stubs) {
    771         ErrorMsg += " '";
    772         ErrorMsg += StubEntry.first;
    773         ErrorMsg += "'";
    774       }
    775     }
    776     ErrorMsg += "\n";
    777     return std::make_pair(nullptr, ErrorMsg);
    778   }
    779 
    780   auto SectionInfoItr = SectionMapItr->second.find(SectionName);
    781   if (SectionInfoItr == SectionMapItr->second.end())
    782     return std::make_pair(nullptr,
    783                           ("Section '" + SectionName + "' not found in file '" +
    784                            FileName + "'\n").str());
    785 
    786   return std::make_pair(&SectionInfoItr->second, std::string(""));
    787 }
    788 
    789 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getSectionAddr(
    790     StringRef FileName, StringRef SectionName, bool IsInsideLoad) const {
    791 
    792   const SectionAddressInfo *SectionInfo = nullptr;
    793   {
    794     std::string ErrorMsg;
    795     std::tie(SectionInfo, ErrorMsg) =
    796       findSectionAddrInfo(FileName, SectionName);
    797     if (ErrorMsg != "")
    798       return std::make_pair(0, ErrorMsg);
    799   }
    800 
    801   unsigned SectionID = SectionInfo->SectionID;
    802   uint64_t Addr;
    803   if (IsInsideLoad)
    804     Addr = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(
    805         getRTDyld().Sections[SectionID].getAddress()));
    806   else
    807     Addr = getRTDyld().Sections[SectionID].getLoadAddress();
    808 
    809   return std::make_pair(Addr, std::string(""));
    810 }
    811 
    812 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getStubAddrFor(
    813     StringRef FileName, StringRef SectionName, StringRef SymbolName,
    814     bool IsInsideLoad) const {
    815 
    816   const SectionAddressInfo *SectionInfo = nullptr;
    817   {
    818     std::string ErrorMsg;
    819     std::tie(SectionInfo, ErrorMsg) =
    820       findSectionAddrInfo(FileName, SectionName);
    821     if (ErrorMsg != "")
    822       return std::make_pair(0, ErrorMsg);
    823   }
    824 
    825   unsigned SectionID = SectionInfo->SectionID;
    826   const StubOffsetsMap &SymbolStubs = SectionInfo->StubOffsets;
    827   auto StubOffsetItr = SymbolStubs.find(SymbolName);
    828   if (StubOffsetItr == SymbolStubs.end())
    829     return std::make_pair(0,
    830                           ("Stub for symbol '" + SymbolName + "' not found. "
    831                            "If '" + SymbolName + "' is an internal symbol this "
    832                            "may indicate that the stub target offset is being "
    833                            "computed incorrectly.\n").str());
    834 
    835   uint64_t StubOffset = StubOffsetItr->second;
    836 
    837   uint64_t Addr;
    838   if (IsInsideLoad) {
    839     uintptr_t SectionBase = reinterpret_cast<uintptr_t>(
    840         getRTDyld().Sections[SectionID].getAddress());
    841     Addr = static_cast<uint64_t>(SectionBase) + StubOffset;
    842   } else {
    843     uint64_t SectionBase = getRTDyld().Sections[SectionID].getLoadAddress();
    844     Addr = SectionBase + StubOffset;
    845   }
    846 
    847   return std::make_pair(Addr, std::string(""));
    848 }
    849 
    850 StringRef
    851 RuntimeDyldCheckerImpl::getSubsectionStartingAt(StringRef Name) const {
    852   RTDyldSymbolTable::const_iterator pos =
    853       getRTDyld().GlobalSymbolTable.find(Name);
    854   if (pos == getRTDyld().GlobalSymbolTable.end())
    855     return StringRef();
    856   const auto &SymInfo = pos->second;
    857   uint8_t *SectionAddr = getRTDyld().getSectionAddress(SymInfo.getSectionID());
    858   return StringRef(reinterpret_cast<const char *>(SectionAddr) +
    859                        SymInfo.getOffset(),
    860                    getRTDyld().Sections[SymInfo.getSectionID()].getSize() -
    861                        SymInfo.getOffset());
    862 }
    863 
    864 void RuntimeDyldCheckerImpl::registerSection(
    865     StringRef FilePath, unsigned SectionID) {
    866   StringRef FileName = sys::path::filename(FilePath);
    867   const SectionEntry &Section = getRTDyld().Sections[SectionID];
    868   StringRef SectionName = Section.getName();
    869 
    870   Stubs[FileName][SectionName].SectionID = SectionID;
    871 }
    872 
    873 void RuntimeDyldCheckerImpl::registerStubMap(
    874     StringRef FilePath, unsigned SectionID,
    875     const RuntimeDyldImpl::StubMap &RTDyldStubs) {
    876   StringRef FileName = sys::path::filename(FilePath);
    877   const SectionEntry &Section = getRTDyld().Sections[SectionID];
    878   StringRef SectionName = Section.getName();
    879 
    880   Stubs[FileName][SectionName].SectionID = SectionID;
    881 
    882   for (auto &StubMapEntry : RTDyldStubs) {
    883     std::string SymbolName = "";
    884 
    885     if (StubMapEntry.first.SymbolName)
    886       SymbolName = StubMapEntry.first.SymbolName;
    887     else {
    888       // If this is a (Section, Offset) pair, do a reverse lookup in the
    889       // global symbol table to find the name.
    890       for (auto &GSTEntry : getRTDyld().GlobalSymbolTable) {
    891         const auto &SymInfo = GSTEntry.second;
    892         if (SymInfo.getSectionID() == StubMapEntry.first.SectionID &&
    893             SymInfo.getOffset() ==
    894               static_cast<uint64_t>(StubMapEntry.first.Offset)) {
    895           SymbolName = GSTEntry.first();
    896           break;
    897         }
    898       }
    899     }
    900 
    901     if (SymbolName != "")
    902       Stubs[FileName][SectionName].StubOffsets[SymbolName] =
    903         StubMapEntry.second;
    904   }
    905 }
    906 
    907 RuntimeDyldChecker::RuntimeDyldChecker(RuntimeDyld &RTDyld,
    908                                        MCDisassembler *Disassembler,
    909                                        MCInstPrinter *InstPrinter,
    910                                        raw_ostream &ErrStream)
    911     : Impl(make_unique<RuntimeDyldCheckerImpl>(RTDyld, Disassembler,
    912                                                InstPrinter, ErrStream)) {}
    913 
    914 RuntimeDyldChecker::~RuntimeDyldChecker() {}
    915 
    916 RuntimeDyld& RuntimeDyldChecker::getRTDyld() {
    917   return Impl->RTDyld;
    918 }
    919 
    920 const RuntimeDyld& RuntimeDyldChecker::getRTDyld() const {
    921   return Impl->RTDyld;
    922 }
    923 
    924 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
    925   return Impl->check(CheckExpr);
    926 }
    927 
    928 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
    929                                                MemoryBuffer *MemBuf) const {
    930   return Impl->checkAllRulesInBuffer(RulePrefix, MemBuf);
    931 }
    932 
    933 std::pair<uint64_t, std::string>
    934 RuntimeDyldChecker::getSectionAddr(StringRef FileName, StringRef SectionName,
    935                                    bool LocalAddress) {
    936   return Impl->getSectionAddr(FileName, SectionName, LocalAddress);
    937 }
    938