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