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