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