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