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