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