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