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