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