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