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/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, returns 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 (hexadecimal 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 cantFail(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 Optional<uint64_t>
 865 RuntimeDyldCheckerImpl::getSectionLoadAddress(void *LocalAddress) const {
 866   for (auto &S : getRTDyld().Sections) {
 867     if (S.getAddress() == LocalAddress)
 868       return S.getLoadAddress();
 869   }
 870   return Optional<uint64_t>();
 871 }
 872
 873 void RuntimeDyldCheckerImpl::registerSection(
 874     StringRef FilePath, unsigned SectionID) {
 875   StringRef FileName = sys::path::filename(FilePath);
 876   const SectionEntry &Section = getRTDyld().Sections[SectionID];
 877   StringRef SectionName = Section.getName();
 878
 879   Stubs[FileName][SectionName].SectionID = SectionID;
 880 }
 881
 882 void RuntimeDyldCheckerImpl::registerStubMap(
 883     StringRef FilePath, unsigned SectionID,
 884     const RuntimeDyldImpl::StubMap &RTDyldStubs) {
 885   StringRef FileName = sys::path::filename(FilePath);
 886   const SectionEntry &Section = getRTDyld().Sections[SectionID];
 887   StringRef SectionName = Section.getName();
 888
 889   Stubs[FileName][SectionName].SectionID = SectionID;
 890
 891   for (auto &StubMapEntry : RTDyldStubs) {
 892     std::string SymbolName = "";
 893
 894     if (StubMapEntry.first.SymbolName)
 895       SymbolName = StubMapEntry.first.SymbolName;
 896     else {
 897       // If this is a (Section, Offset) pair, do a reverse lookup in the
 898       // global symbol table to find the name.
 899       for (auto &GSTEntry : getRTDyld().GlobalSymbolTable) {
 900         const auto &SymInfo = GSTEntry.second;
 901         if (SymInfo.getSectionID() == StubMapEntry.first.SectionID &&
 902             SymInfo.getOffset() ==
 903               static_cast<uint64_t>(StubMapEntry.first.Offset)) {
 904           SymbolName = GSTEntry.first();
 905           break;
 906         }
 907       }
 908     }
 909
 910     if (SymbolName != "")
 911       Stubs[FileName][SectionName].StubOffsets[SymbolName] =
 912         StubMapEntry.second;
 913   }
 914 }
 915
 916 RuntimeDyldChecker::RuntimeDyldChecker(RuntimeDyld &RTDyld,
 917                                        MCDisassembler *Disassembler,
 918                                        MCInstPrinter *InstPrinter,
 919                                        raw_ostream &ErrStream)
 920     : Impl(make_unique<RuntimeDyldCheckerImpl>(RTDyld, Disassembler,
 921                                                InstPrinter, ErrStream)) {}
 922
 923 RuntimeDyldChecker::~RuntimeDyldChecker() {}
 924
 925 RuntimeDyld& RuntimeDyldChecker::getRTDyld() {
 926   return Impl->RTDyld;
 927 }
 928
 929 const RuntimeDyld& RuntimeDyldChecker::getRTDyld() const {
 930   return Impl->RTDyld;
 931 }
 932
 933 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
 934   return Impl->check(CheckExpr);
 935 }
 936
 937 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
 938                                                MemoryBuffer *MemBuf) const {
 939   return Impl->checkAllRulesInBuffer(RulePrefix, MemBuf);
 940 }
 941
 942 std::pair<uint64_t, std::string>
 943 RuntimeDyldChecker::getSectionAddr(StringRef FileName, StringRef SectionName,
 944                                    bool LocalAddress) {
 945   return Impl->getSectionAddr(FileName, SectionName, LocalAddress);
 946 }
 947
 948 Optional<uint64_t>
 949 RuntimeDyldChecker::getSectionLoadAddress(void *LocalAddress) const {
 950   return Impl->getSectionLoadAddress(LocalAddress);
 951 }