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