• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- RuntimeDyldChecker.cpp - RuntimeDyld tester framework --*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ExecutionEngine/RuntimeDyldChecker.h"
11 #include "RuntimeDyldCheckerImpl.h"
12 #include "RuntimeDyldImpl.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/MC/MCContext.h"
15 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
16 #include "llvm/MC/MCInst.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:
RuntimeDyldCheckerExprEval(const RuntimeDyldCheckerImpl & Checker,raw_ostream & ErrStream)31   RuntimeDyldCheckerExprEval(const RuntimeDyldCheckerImpl &Checker,
32                              raw_ostream &ErrStream)
33       : Checker(Checker) {}
34 
evaluate(StringRef Expr) const35   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;
ParseContextllvm::RuntimeDyldCheckerExprEval::ParseContext82     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:
EvalResult()99     EvalResult() : Value(0), ErrorMsg("") {}
EvalResult(uint64_t Value)100     EvalResult(uint64_t Value) : Value(Value), ErrorMsg("") {}
EvalResult(std::string ErrorMsg)101     EvalResult(std::string ErrorMsg)
102         : Value(0), ErrorMsg(std::move(ErrorMsg)) {}
getValue() const103     uint64_t getValue() const { return Value; }
hasError() const104     bool hasError() const { return ErrorMsg != ""; }
getErrorMsg() const105     const std::string &getErrorMsg() const { return ErrorMsg; }
106 
107   private:
108     uint64_t Value;
109     std::string ErrorMsg;
110   };
111 
getTokenForError(StringRef Expr) const112   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 
unexpectedToken(StringRef TokenStart,StringRef SubExpr,StringRef ErrText) const130   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 
handleError(StringRef Expr,const EvalResult & R) const146   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 
parseBinOpToken(StringRef Expr) const153   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 
computeBinOpResult(BinOpToken Op,const EvalResult & LHSResult,const EvalResult & RHSResult) const185   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.
parseSymbol(StringRef Expr) const207   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, retuns a pair containing the value of the operand, plus
221   // the expression remaining to be evaluated.
evalDecodeOperand(StringRef Expr) const222   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.
evalNextPC(StringRef Expr,ParseContext PCtx) const289   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.
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.
evalStubAddr(StringRef Expr,ParseContext PCtx) const327   std::pair<EvalResult, StringRef> evalStubAddr(StringRef Expr,
328                                                 ParseContext PCtx) 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 FileName;
336     size_t ComaIdx = RemainingExpr.find(',');
337     FileName = 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 SectionName;
346     std::tie(SectionName, 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     StringRef Symbol;
354     std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
355 
356     if (!RemainingExpr.startswith(")"))
357       return std::make_pair(
358           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
359     RemainingExpr = RemainingExpr.substr(1).ltrim();
360 
361     uint64_t StubAddr;
362     std::string ErrorMsg = "";
363     std::tie(StubAddr, ErrorMsg) = Checker.getStubAddrFor(
364         FileName, SectionName, Symbol, PCtx.IsInsideLoad);
365 
366     if (ErrorMsg != "")
367       return std::make_pair(EvalResult(ErrorMsg), "");
368 
369     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
370   }
371 
evalSectionAddr(StringRef Expr,ParseContext PCtx) const372   std::pair<EvalResult, StringRef> evalSectionAddr(StringRef Expr,
373                                                    ParseContext PCtx) const {
374     if (!Expr.startswith("("))
375       return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
376     StringRef RemainingExpr = Expr.substr(1).ltrim();
377 
378     // Handle file-name specially, as it may contain characters that aren't
379     // legal for symbols.
380     StringRef FileName;
381     size_t ComaIdx = RemainingExpr.find(',');
382     FileName = RemainingExpr.substr(0, ComaIdx).rtrim();
383     RemainingExpr = RemainingExpr.substr(ComaIdx).ltrim();
384 
385     if (!RemainingExpr.startswith(","))
386       return std::make_pair(
387           unexpectedToken(RemainingExpr, Expr, "expected ','"), "");
388     RemainingExpr = RemainingExpr.substr(1).ltrim();
389 
390     StringRef SectionName;
391     std::tie(SectionName, RemainingExpr) = parseSymbol(RemainingExpr);
392 
393     if (!RemainingExpr.startswith(")"))
394       return std::make_pair(
395           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
396     RemainingExpr = RemainingExpr.substr(1).ltrim();
397 
398     uint64_t StubAddr;
399     std::string ErrorMsg = "";
400     std::tie(StubAddr, ErrorMsg) = Checker.getSectionAddr(
401         FileName, SectionName, PCtx.IsInsideLoad);
402 
403     if (ErrorMsg != "")
404       return std::make_pair(EvalResult(ErrorMsg), "");
405 
406     return std::make_pair(EvalResult(StubAddr), RemainingExpr);
407   }
408 
409   // Evaluate an identiefer expr, which may be a symbol, or a call to
410   // one of the builtin functions: get_insn_opcode or get_insn_length.
411   // Return the result, plus the expression remaining to be parsed.
evalIdentifierExpr(StringRef Expr,ParseContext PCtx) const412   std::pair<EvalResult, StringRef> evalIdentifierExpr(StringRef Expr,
413                                                       ParseContext PCtx) const {
414     StringRef Symbol;
415     StringRef RemainingExpr;
416     std::tie(Symbol, RemainingExpr) = parseSymbol(Expr);
417 
418     // Check for builtin function calls.
419     if (Symbol == "decode_operand")
420       return evalDecodeOperand(RemainingExpr);
421     else if (Symbol == "next_pc")
422       return evalNextPC(RemainingExpr, PCtx);
423     else if (Symbol == "stub_addr")
424       return evalStubAddr(RemainingExpr, PCtx);
425     else if (Symbol == "section_addr")
426       return evalSectionAddr(RemainingExpr, PCtx);
427 
428     if (!Checker.isSymbolValid(Symbol)) {
429       std::string ErrMsg("No known address for symbol '");
430       ErrMsg += Symbol;
431       ErrMsg += "'";
432       if (Symbol.startswith("L"))
433         ErrMsg += " (this appears to be an assembler local label - "
434                   " perhaps drop the 'L'?)";
435 
436       return std::make_pair(EvalResult(ErrMsg), "");
437     }
438 
439     // The value for the symbol depends on the context we're evaluating in:
440     // Inside a load this is the address in the linker's memory, outside a
441     // load it's the address in the target processes memory.
442     uint64_t Value = PCtx.IsInsideLoad ? Checker.getSymbolLocalAddr(Symbol)
443                                        : Checker.getSymbolRemoteAddr(Symbol);
444 
445     // Looks like a plain symbol reference.
446     return std::make_pair(EvalResult(Value), RemainingExpr);
447   }
448 
449   // Parse a number (hexadecimal or decimal) and return a (string, string)
450   // pair representing the number and the expression remaining to be parsed.
parseNumberString(StringRef Expr) const451   std::pair<StringRef, StringRef> parseNumberString(StringRef Expr) const {
452     size_t FirstNonDigit = StringRef::npos;
453     if (Expr.startswith("0x")) {
454       FirstNonDigit = Expr.find_first_not_of("0123456789abcdefABCDEF", 2);
455       if (FirstNonDigit == StringRef::npos)
456         FirstNonDigit = Expr.size();
457     } else {
458       FirstNonDigit = Expr.find_first_not_of("0123456789");
459       if (FirstNonDigit == StringRef::npos)
460         FirstNonDigit = Expr.size();
461     }
462     return std::make_pair(Expr.substr(0, FirstNonDigit),
463                           Expr.substr(FirstNonDigit));
464   }
465 
466   // Evaluate a constant numeric expression (hexidecimal or decimal) and
467   // return a pair containing the result, and the expression remaining to be
468   // evaluated.
evalNumberExpr(StringRef Expr) const469   std::pair<EvalResult, StringRef> evalNumberExpr(StringRef Expr) const {
470     StringRef ValueStr;
471     StringRef RemainingExpr;
472     std::tie(ValueStr, RemainingExpr) = parseNumberString(Expr);
473 
474     if (ValueStr.empty() || !isdigit(ValueStr[0]))
475       return std::make_pair(
476           unexpectedToken(RemainingExpr, RemainingExpr, "expected number"), "");
477     uint64_t Value;
478     ValueStr.getAsInteger(0, Value);
479     return std::make_pair(EvalResult(Value), RemainingExpr);
480   }
481 
482   // Evaluate an expression of the form "(<expr>)" and return a pair
483   // containing the result of evaluating <expr>, plus the expression
484   // remaining to be parsed.
evalParensExpr(StringRef Expr,ParseContext PCtx) const485   std::pair<EvalResult, StringRef> evalParensExpr(StringRef Expr,
486                                                   ParseContext PCtx) const {
487     assert(Expr.startswith("(") && "Not a parenthesized expression");
488     EvalResult SubExprResult;
489     StringRef RemainingExpr;
490     std::tie(SubExprResult, RemainingExpr) =
491         evalComplexExpr(evalSimpleExpr(Expr.substr(1).ltrim(), PCtx), PCtx);
492     if (SubExprResult.hasError())
493       return std::make_pair(SubExprResult, "");
494     if (!RemainingExpr.startswith(")"))
495       return std::make_pair(
496           unexpectedToken(RemainingExpr, Expr, "expected ')'"), "");
497     RemainingExpr = RemainingExpr.substr(1).ltrim();
498     return std::make_pair(SubExprResult, RemainingExpr);
499   }
500 
501   // Evaluate an expression in one of the following forms:
502   //   *{<number>}<expr>
503   // Return a pair containing the result, plus the expression remaining to be
504   // parsed.
evalLoadExpr(StringRef Expr) const505   std::pair<EvalResult, StringRef> evalLoadExpr(StringRef Expr) const {
506     assert(Expr.startswith("*") && "Not a load expression");
507     StringRef RemainingExpr = Expr.substr(1).ltrim();
508 
509     // Parse read size.
510     if (!RemainingExpr.startswith("{"))
511       return std::make_pair(EvalResult("Expected '{' following '*'."), "");
512     RemainingExpr = RemainingExpr.substr(1).ltrim();
513     EvalResult ReadSizeExpr;
514     std::tie(ReadSizeExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
515     if (ReadSizeExpr.hasError())
516       return std::make_pair(ReadSizeExpr, RemainingExpr);
517     uint64_t ReadSize = ReadSizeExpr.getValue();
518     if (ReadSize < 1 || ReadSize > 8)
519       return std::make_pair(EvalResult("Invalid size for dereference."), "");
520     if (!RemainingExpr.startswith("}"))
521       return std::make_pair(EvalResult("Missing '}' for dereference."), "");
522     RemainingExpr = RemainingExpr.substr(1).ltrim();
523 
524     // Evaluate the expression representing the load address.
525     ParseContext LoadCtx(true);
526     EvalResult LoadAddrExprResult;
527     std::tie(LoadAddrExprResult, RemainingExpr) =
528         evalComplexExpr(evalSimpleExpr(RemainingExpr, LoadCtx), LoadCtx);
529 
530     if (LoadAddrExprResult.hasError())
531       return std::make_pair(LoadAddrExprResult, "");
532 
533     uint64_t LoadAddr = LoadAddrExprResult.getValue();
534 
535     return std::make_pair(
536         EvalResult(Checker.readMemoryAtAddr(LoadAddr, ReadSize)),
537         RemainingExpr);
538   }
539 
540   // Evaluate a "simple" expression. This is any expression that _isn't_ an
541   // un-parenthesized binary expression.
542   //
543   // "Simple" expressions can be optionally bit-sliced. See evalSlicedExpr.
544   //
545   // Returns a pair containing the result of the evaluation, plus the
546   // expression remaining to be parsed.
evalSimpleExpr(StringRef Expr,ParseContext PCtx) const547   std::pair<EvalResult, StringRef> evalSimpleExpr(StringRef Expr,
548                                                   ParseContext PCtx) const {
549     EvalResult SubExprResult;
550     StringRef RemainingExpr;
551 
552     if (Expr.empty())
553       return std::make_pair(EvalResult("Unexpected end of expression"), "");
554 
555     if (Expr[0] == '(')
556       std::tie(SubExprResult, RemainingExpr) = evalParensExpr(Expr, PCtx);
557     else if (Expr[0] == '*')
558       std::tie(SubExprResult, RemainingExpr) = evalLoadExpr(Expr);
559     else if (isalpha(Expr[0]) || Expr[0] == '_')
560       std::tie(SubExprResult, RemainingExpr) = evalIdentifierExpr(Expr, PCtx);
561     else if (isdigit(Expr[0]))
562       std::tie(SubExprResult, RemainingExpr) = evalNumberExpr(Expr);
563     else
564       return std::make_pair(
565           unexpectedToken(Expr, Expr,
566                           "expected '(', '*', identifier, or number"), "");
567 
568     if (SubExprResult.hasError())
569       return std::make_pair(SubExprResult, RemainingExpr);
570 
571     // Evaluate bit-slice if present.
572     if (RemainingExpr.startswith("["))
573       std::tie(SubExprResult, RemainingExpr) =
574           evalSliceExpr(std::make_pair(SubExprResult, RemainingExpr));
575 
576     return std::make_pair(SubExprResult, RemainingExpr);
577   }
578 
579   // Evaluate a bit-slice of an expression.
580   // A bit-slice has the form "<expr>[high:low]". The result of evaluating a
581   // slice is the bits between high and low (inclusive) in the original
582   // expression, right shifted so that the "low" bit is in position 0 in the
583   // result.
584   // Returns a pair containing the result of the slice operation, plus the
585   // expression remaining to be parsed.
586   std::pair<EvalResult, StringRef>
evalSliceExpr(const std::pair<EvalResult,StringRef> & Ctx) const587   evalSliceExpr(const std::pair<EvalResult, StringRef> &Ctx) const {
588     EvalResult SubExprResult;
589     StringRef RemainingExpr;
590     std::tie(SubExprResult, RemainingExpr) = Ctx;
591 
592     assert(RemainingExpr.startswith("[") && "Not a slice expr.");
593     RemainingExpr = RemainingExpr.substr(1).ltrim();
594 
595     EvalResult HighBitExpr;
596     std::tie(HighBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
597 
598     if (HighBitExpr.hasError())
599       return std::make_pair(HighBitExpr, RemainingExpr);
600 
601     if (!RemainingExpr.startswith(":"))
602       return std::make_pair(
603           unexpectedToken(RemainingExpr, RemainingExpr, "expected ':'"), "");
604     RemainingExpr = RemainingExpr.substr(1).ltrim();
605 
606     EvalResult LowBitExpr;
607     std::tie(LowBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
608 
609     if (LowBitExpr.hasError())
610       return std::make_pair(LowBitExpr, RemainingExpr);
611 
612     if (!RemainingExpr.startswith("]"))
613       return std::make_pair(
614           unexpectedToken(RemainingExpr, RemainingExpr, "expected ']'"), "");
615     RemainingExpr = RemainingExpr.substr(1).ltrim();
616 
617     unsigned HighBit = HighBitExpr.getValue();
618     unsigned LowBit = LowBitExpr.getValue();
619     uint64_t Mask = ((uint64_t)1 << (HighBit - LowBit + 1)) - 1;
620     uint64_t SlicedValue = (SubExprResult.getValue() >> LowBit) & Mask;
621     return std::make_pair(EvalResult(SlicedValue), RemainingExpr);
622   }
623 
624   // Evaluate a "complex" expression.
625   // Takes an already evaluated subexpression and checks for the presence of a
626   // binary operator, computing the result of the binary operation if one is
627   // found. Used to make arithmetic expressions left-associative.
628   // Returns a pair containing the ultimate result of evaluating the
629   // expression, plus the expression remaining to be evaluated.
630   std::pair<EvalResult, StringRef>
evalComplexExpr(const std::pair<EvalResult,StringRef> & LHSAndRemaining,ParseContext PCtx) const631   evalComplexExpr(const std::pair<EvalResult, StringRef> &LHSAndRemaining,
632                   ParseContext PCtx) const {
633     EvalResult LHSResult;
634     StringRef RemainingExpr;
635     std::tie(LHSResult, RemainingExpr) = LHSAndRemaining;
636 
637     // If there was an error, or there's nothing left to evaluate, return the
638     // result.
639     if (LHSResult.hasError() || RemainingExpr == "")
640       return std::make_pair(LHSResult, RemainingExpr);
641 
642     // Otherwise check if this is a binary expressioan.
643     BinOpToken BinOp;
644     std::tie(BinOp, RemainingExpr) = parseBinOpToken(RemainingExpr);
645 
646     // If this isn't a recognized expression just return.
647     if (BinOp == BinOpToken::Invalid)
648       return std::make_pair(LHSResult, RemainingExpr);
649 
650     // This is a recognized bin-op. Evaluate the RHS, then evaluate the binop.
651     EvalResult RHSResult;
652     std::tie(RHSResult, RemainingExpr) = evalSimpleExpr(RemainingExpr, PCtx);
653 
654     // If there was an error evaluating the RHS, return it.
655     if (RHSResult.hasError())
656       return std::make_pair(RHSResult, RemainingExpr);
657 
658     // This is a binary expression - evaluate and try to continue as a
659     // complex expr.
660     EvalResult ThisResult(computeBinOpResult(BinOp, LHSResult, RHSResult));
661 
662     return evalComplexExpr(std::make_pair(ThisResult, RemainingExpr), PCtx);
663   }
664 
decodeInst(StringRef Symbol,MCInst & Inst,uint64_t & Size) const665   bool decodeInst(StringRef Symbol, MCInst &Inst, uint64_t &Size) const {
666     MCDisassembler *Dis = Checker.Disassembler;
667     StringRef SectionMem = Checker.getSubsectionStartingAt(Symbol);
668     ArrayRef<uint8_t> SectionBytes(
669         reinterpret_cast<const uint8_t *>(SectionMem.data()),
670         SectionMem.size());
671 
672     MCDisassembler::DecodeStatus S =
673         Dis->getInstruction(Inst, Size, SectionBytes, 0, nulls(), nulls());
674 
675     return (S == MCDisassembler::Success);
676   }
677 };
678 }
679 
RuntimeDyldCheckerImpl(RuntimeDyld & RTDyld,MCDisassembler * Disassembler,MCInstPrinter * InstPrinter,raw_ostream & ErrStream)680 RuntimeDyldCheckerImpl::RuntimeDyldCheckerImpl(RuntimeDyld &RTDyld,
681                                                MCDisassembler *Disassembler,
682                                                MCInstPrinter *InstPrinter,
683                                                raw_ostream &ErrStream)
684     : RTDyld(RTDyld), Disassembler(Disassembler), InstPrinter(InstPrinter),
685       ErrStream(ErrStream) {
686   RTDyld.Checker = this;
687 }
688 
check(StringRef CheckExpr) const689 bool RuntimeDyldCheckerImpl::check(StringRef CheckExpr) const {
690   CheckExpr = CheckExpr.trim();
691   DEBUG(dbgs() << "RuntimeDyldChecker: Checking '" << CheckExpr << "'...\n");
692   RuntimeDyldCheckerExprEval P(*this, ErrStream);
693   bool Result = P.evaluate(CheckExpr);
694   (void)Result;
695   DEBUG(dbgs() << "RuntimeDyldChecker: '" << CheckExpr << "' "
696                << (Result ? "passed" : "FAILED") << ".\n");
697   return Result;
698 }
699 
checkAllRulesInBuffer(StringRef RulePrefix,MemoryBuffer * MemBuf) const700 bool RuntimeDyldCheckerImpl::checkAllRulesInBuffer(StringRef RulePrefix,
701                                                    MemoryBuffer *MemBuf) const {
702   bool DidAllTestsPass = true;
703   unsigned NumRules = 0;
704 
705   const char *LineStart = MemBuf->getBufferStart();
706 
707   // Eat whitespace.
708   while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
709     ++LineStart;
710 
711   while (LineStart != MemBuf->getBufferEnd() && *LineStart != '\0') {
712     const char *LineEnd = LineStart;
713     while (LineEnd != MemBuf->getBufferEnd() && *LineEnd != '\r' &&
714            *LineEnd != '\n')
715       ++LineEnd;
716 
717     StringRef Line(LineStart, LineEnd - LineStart);
718     if (Line.startswith(RulePrefix)) {
719       DidAllTestsPass &= check(Line.substr(RulePrefix.size()));
720       ++NumRules;
721     }
722 
723     // Eat whitespace.
724     LineStart = LineEnd;
725     while (LineStart != MemBuf->getBufferEnd() && std::isspace(*LineStart))
726       ++LineStart;
727   }
728   return DidAllTestsPass && (NumRules != 0);
729 }
730 
isSymbolValid(StringRef Symbol) const731 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const {
732   if (getRTDyld().getSymbol(Symbol))
733     return true;
734   return !!getRTDyld().Resolver.findSymbol(Symbol);
735 }
736 
getSymbolLocalAddr(StringRef Symbol) const737 uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const {
738   return static_cast<uint64_t>(
739       reinterpret_cast<uintptr_t>(getRTDyld().getSymbolLocalAddress(Symbol)));
740 }
741 
getSymbolRemoteAddr(StringRef Symbol) const742 uint64_t RuntimeDyldCheckerImpl::getSymbolRemoteAddr(StringRef Symbol) const {
743   if (auto InternalSymbol = getRTDyld().getSymbol(Symbol))
744     return InternalSymbol.getAddress();
745   return getRTDyld().Resolver.findSymbol(Symbol).getAddress();
746 }
747 
readMemoryAtAddr(uint64_t SrcAddr,unsigned Size) const748 uint64_t RuntimeDyldCheckerImpl::readMemoryAtAddr(uint64_t SrcAddr,
749                                                   unsigned Size) const {
750   uintptr_t PtrSizedAddr = static_cast<uintptr_t>(SrcAddr);
751   assert(PtrSizedAddr == SrcAddr && "Linker memory pointer out-of-range.");
752   uint8_t *Src = reinterpret_cast<uint8_t*>(PtrSizedAddr);
753   return getRTDyld().readBytesUnaligned(Src, Size);
754 }
755 
756 
757 std::pair<const RuntimeDyldCheckerImpl::SectionAddressInfo*, std::string>
findSectionAddrInfo(StringRef FileName,StringRef SectionName) const758 RuntimeDyldCheckerImpl::findSectionAddrInfo(StringRef FileName,
759                                             StringRef SectionName) const {
760 
761   auto SectionMapItr = Stubs.find(FileName);
762   if (SectionMapItr == Stubs.end()) {
763     std::string ErrorMsg = "File '";
764     ErrorMsg += FileName;
765     ErrorMsg += "' not found. ";
766     if (Stubs.empty())
767       ErrorMsg += "No stubs registered.";
768     else {
769       ErrorMsg += "Available files are:";
770       for (const auto& StubEntry : Stubs) {
771         ErrorMsg += " '";
772         ErrorMsg += StubEntry.first;
773         ErrorMsg += "'";
774       }
775     }
776     ErrorMsg += "\n";
777     return std::make_pair(nullptr, ErrorMsg);
778   }
779 
780   auto SectionInfoItr = SectionMapItr->second.find(SectionName);
781   if (SectionInfoItr == SectionMapItr->second.end())
782     return std::make_pair(nullptr,
783                           ("Section '" + SectionName + "' not found in file '" +
784                            FileName + "'\n").str());
785 
786   return std::make_pair(&SectionInfoItr->second, std::string(""));
787 }
788 
getSectionAddr(StringRef FileName,StringRef SectionName,bool IsInsideLoad) const789 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getSectionAddr(
790     StringRef FileName, StringRef SectionName, bool IsInsideLoad) const {
791 
792   const SectionAddressInfo *SectionInfo = nullptr;
793   {
794     std::string ErrorMsg;
795     std::tie(SectionInfo, ErrorMsg) =
796       findSectionAddrInfo(FileName, SectionName);
797     if (ErrorMsg != "")
798       return std::make_pair(0, ErrorMsg);
799   }
800 
801   unsigned SectionID = SectionInfo->SectionID;
802   uint64_t Addr;
803   if (IsInsideLoad)
804     Addr = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(
805         getRTDyld().Sections[SectionID].getAddress()));
806   else
807     Addr = getRTDyld().Sections[SectionID].getLoadAddress();
808 
809   return std::make_pair(Addr, std::string(""));
810 }
811 
getStubAddrFor(StringRef FileName,StringRef SectionName,StringRef SymbolName,bool IsInsideLoad) const812 std::pair<uint64_t, std::string> RuntimeDyldCheckerImpl::getStubAddrFor(
813     StringRef FileName, StringRef SectionName, StringRef SymbolName,
814     bool IsInsideLoad) const {
815 
816   const SectionAddressInfo *SectionInfo = nullptr;
817   {
818     std::string ErrorMsg;
819     std::tie(SectionInfo, ErrorMsg) =
820       findSectionAddrInfo(FileName, SectionName);
821     if (ErrorMsg != "")
822       return std::make_pair(0, ErrorMsg);
823   }
824 
825   unsigned SectionID = SectionInfo->SectionID;
826   const StubOffsetsMap &SymbolStubs = SectionInfo->StubOffsets;
827   auto StubOffsetItr = SymbolStubs.find(SymbolName);
828   if (StubOffsetItr == SymbolStubs.end())
829     return std::make_pair(0,
830                           ("Stub for symbol '" + SymbolName + "' not found. "
831                            "If '" + SymbolName + "' is an internal symbol this "
832                            "may indicate that the stub target offset is being "
833                            "computed incorrectly.\n").str());
834 
835   uint64_t StubOffset = StubOffsetItr->second;
836 
837   uint64_t Addr;
838   if (IsInsideLoad) {
839     uintptr_t SectionBase = reinterpret_cast<uintptr_t>(
840         getRTDyld().Sections[SectionID].getAddress());
841     Addr = static_cast<uint64_t>(SectionBase) + StubOffset;
842   } else {
843     uint64_t SectionBase = getRTDyld().Sections[SectionID].getLoadAddress();
844     Addr = SectionBase + StubOffset;
845   }
846 
847   return std::make_pair(Addr, std::string(""));
848 }
849 
850 StringRef
getSubsectionStartingAt(StringRef Name) const851 RuntimeDyldCheckerImpl::getSubsectionStartingAt(StringRef Name) const {
852   RTDyldSymbolTable::const_iterator pos =
853       getRTDyld().GlobalSymbolTable.find(Name);
854   if (pos == getRTDyld().GlobalSymbolTable.end())
855     return StringRef();
856   const auto &SymInfo = pos->second;
857   uint8_t *SectionAddr = getRTDyld().getSectionAddress(SymInfo.getSectionID());
858   return StringRef(reinterpret_cast<const char *>(SectionAddr) +
859                        SymInfo.getOffset(),
860                    getRTDyld().Sections[SymInfo.getSectionID()].getSize() -
861                        SymInfo.getOffset());
862 }
863 
registerSection(StringRef FilePath,unsigned SectionID)864 void RuntimeDyldCheckerImpl::registerSection(
865     StringRef FilePath, unsigned SectionID) {
866   StringRef FileName = sys::path::filename(FilePath);
867   const SectionEntry &Section = getRTDyld().Sections[SectionID];
868   StringRef SectionName = Section.getName();
869 
870   Stubs[FileName][SectionName].SectionID = SectionID;
871 }
872 
registerStubMap(StringRef FilePath,unsigned SectionID,const RuntimeDyldImpl::StubMap & RTDyldStubs)873 void RuntimeDyldCheckerImpl::registerStubMap(
874     StringRef FilePath, unsigned SectionID,
875     const RuntimeDyldImpl::StubMap &RTDyldStubs) {
876   StringRef FileName = sys::path::filename(FilePath);
877   const SectionEntry &Section = getRTDyld().Sections[SectionID];
878   StringRef SectionName = Section.getName();
879 
880   Stubs[FileName][SectionName].SectionID = SectionID;
881 
882   for (auto &StubMapEntry : RTDyldStubs) {
883     std::string SymbolName = "";
884 
885     if (StubMapEntry.first.SymbolName)
886       SymbolName = StubMapEntry.first.SymbolName;
887     else {
888       // If this is a (Section, Offset) pair, do a reverse lookup in the
889       // global symbol table to find the name.
890       for (auto &GSTEntry : getRTDyld().GlobalSymbolTable) {
891         const auto &SymInfo = GSTEntry.second;
892         if (SymInfo.getSectionID() == StubMapEntry.first.SectionID &&
893             SymInfo.getOffset() ==
894               static_cast<uint64_t>(StubMapEntry.first.Offset)) {
895           SymbolName = GSTEntry.first();
896           break;
897         }
898       }
899     }
900 
901     if (SymbolName != "")
902       Stubs[FileName][SectionName].StubOffsets[SymbolName] =
903         StubMapEntry.second;
904   }
905 }
906 
RuntimeDyldChecker(RuntimeDyld & RTDyld,MCDisassembler * Disassembler,MCInstPrinter * InstPrinter,raw_ostream & ErrStream)907 RuntimeDyldChecker::RuntimeDyldChecker(RuntimeDyld &RTDyld,
908                                        MCDisassembler *Disassembler,
909                                        MCInstPrinter *InstPrinter,
910                                        raw_ostream &ErrStream)
911     : Impl(make_unique<RuntimeDyldCheckerImpl>(RTDyld, Disassembler,
912                                                InstPrinter, ErrStream)) {}
913 
~RuntimeDyldChecker()914 RuntimeDyldChecker::~RuntimeDyldChecker() {}
915 
getRTDyld()916 RuntimeDyld& RuntimeDyldChecker::getRTDyld() {
917   return Impl->RTDyld;
918 }
919 
getRTDyld() const920 const RuntimeDyld& RuntimeDyldChecker::getRTDyld() const {
921   return Impl->RTDyld;
922 }
923 
check(StringRef CheckExpr) const924 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
925   return Impl->check(CheckExpr);
926 }
927 
checkAllRulesInBuffer(StringRef RulePrefix,MemoryBuffer * MemBuf) const928 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
929                                                MemoryBuffer *MemBuf) const {
930   return Impl->checkAllRulesInBuffer(RulePrefix, MemBuf);
931 }
932 
933 std::pair<uint64_t, std::string>
getSectionAddr(StringRef FileName,StringRef SectionName,bool LocalAddress)934 RuntimeDyldChecker::getSectionAddr(StringRef FileName, StringRef SectionName,
935                                    bool LocalAddress) {
936   return Impl->getSectionAddr(FileName, SectionName, LocalAddress);
937 }
938