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