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