llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldChecker.cpp

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