contrib/llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp

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