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