1 //===--- RuntimeDyldChecker.cpp - RuntimeDyld tester framework --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ExecutionEngine/RuntimeDyldChecker.h"
11 #include "llvm/MC/MCContext.h"
12 #include "llvm/MC/MCDisassembler.h"
13 #include "llvm/MC/MCInst.h"
14 #include "llvm/Support/StringRefMemoryObject.h"
15 #include "RuntimeDyldImpl.h"
18 #define DEBUG_TYPE "rtdyld"
24 // Helper class that implements the language evaluated by RuntimeDyldChecker.
25 class RuntimeDyldCheckerExprEval {
28 RuntimeDyldCheckerExprEval(const RuntimeDyldChecker &Checker,
29 llvm::raw_ostream &ErrStream)
30 : Checker(Checker), ErrStream(ErrStream) {}
32 bool evaluate(StringRef Expr) const {
33 // Expect equality expression of the form 'LHS = RHS'.
35 size_t EQIdx = Expr.find('=');
38 StringRef LHSExpr = Expr.substr(0, EQIdx).rtrim();
39 StringRef RemainingExpr;
41 std::tie(LHSResult, RemainingExpr) =
42 evalComplexExpr(evalSimpleExpr(LHSExpr));
43 if (LHSResult.hasError())
44 return handleError(Expr, LHSResult);
45 if (RemainingExpr != "")
46 return handleError(Expr, unexpectedToken(RemainingExpr, LHSExpr, ""));
49 StringRef RHSExpr = Expr.substr(EQIdx + 1).ltrim();
51 std::tie(RHSResult, RemainingExpr) =
52 evalComplexExpr(evalSimpleExpr(RHSExpr));
53 if (RHSResult.hasError())
54 return handleError(Expr, RHSResult);
55 if (RemainingExpr != "")
56 return handleError(Expr, unexpectedToken(RemainingExpr, RHSExpr, ""));
58 if (LHSResult.getValue() != RHSResult.getValue()) {
59 ErrStream << "Expression '" << Expr << "' is false: "
60 << format("0x%lx", LHSResult.getValue()) << " != "
61 << format("0x%lx", RHSResult.getValue()) << "\n";
68 const RuntimeDyldChecker &Checker;
69 llvm::raw_ostream &ErrStream;
71 enum class BinOpToken : unsigned { Invalid, Add, Sub, BitwiseAnd,
72 BitwiseOr, ShiftLeft, ShiftRight };
77 : Value(0), ErrorMsg("") {}
78 EvalResult(uint64_t Value)
79 : Value(Value), ErrorMsg("") {}
80 EvalResult(std::string ErrorMsg)
81 : Value(0), ErrorMsg(ErrorMsg) {}
82 uint64_t getValue() const { return Value; }
83 bool hasError() const { return ErrorMsg != ""; }
84 const std::string& getErrorMsg() const { return ErrorMsg; }
90 StringRef getTokenForError(StringRef Expr) const {
94 StringRef Token, Remaining;
96 std::tie(Token, Remaining) = parseSymbol(Expr);
97 else if (isdigit(Expr[0]))
98 std::tie(Token, Remaining) = parseNumberString(Expr);
101 if (Expr.startswith("<<") || Expr.startswith(">>"))
103 Token = Expr.substr(0, TokLen);
108 EvalResult unexpectedToken(StringRef TokenStart,
110 StringRef ErrText) const {
111 std::string ErrorMsg("Encountered unexpected token '");
112 ErrorMsg += getTokenForError(TokenStart);
114 ErrorMsg += "' while parsing subexpression '";
122 return EvalResult(std::move(ErrorMsg));
125 bool handleError(StringRef Expr, const EvalResult &R) const {
126 assert(R.hasError() && "Not an error result.");
127 ErrStream << "Error evaluating expression '" << Expr << "': "
128 << R.getErrorMsg() << "\n";
132 std::pair<BinOpToken, StringRef> parseBinOpToken(StringRef Expr) const {
134 return std::make_pair(BinOpToken::Invalid, "");
136 // Handle the two 2-character tokens.
137 if (Expr.startswith("<<"))
138 return std::make_pair(BinOpToken::ShiftLeft,
139 Expr.substr(2).ltrim());
140 if (Expr.startswith(">>"))
141 return std::make_pair(BinOpToken::ShiftRight,
142 Expr.substr(2).ltrim());
144 // Handle one-character tokens.
147 default: return std::make_pair(BinOpToken::Invalid, Expr);
148 case '+': Op = BinOpToken::Add; break;
149 case '-': Op = BinOpToken::Sub; break;
150 case '&': Op = BinOpToken::BitwiseAnd; break;
151 case '|': Op = BinOpToken::BitwiseOr; break;
154 return std::make_pair(Op, Expr.substr(1).ltrim());
157 EvalResult computeBinOpResult(BinOpToken Op, const EvalResult &LHSResult,
158 const EvalResult &RHSResult) const {
160 default: llvm_unreachable("Tried to evaluate unrecognized operation.");
161 case BinOpToken::Add:
162 return EvalResult(LHSResult.getValue() + RHSResult.getValue());
163 case BinOpToken::Sub:
164 return EvalResult(LHSResult.getValue() - RHSResult.getValue());
165 case BinOpToken::BitwiseAnd:
166 return EvalResult(LHSResult.getValue() & RHSResult.getValue());
167 case BinOpToken::BitwiseOr:
168 return EvalResult(LHSResult.getValue() | RHSResult.getValue());
169 case BinOpToken::ShiftLeft:
170 return EvalResult(LHSResult.getValue() << RHSResult.getValue());
171 case BinOpToken::ShiftRight:
172 return EvalResult(LHSResult.getValue() >> RHSResult.getValue());
176 // Parse a symbol and return a (string, string) pair representing the symbol
177 // name and expression remaining to be parsed.
178 std::pair<StringRef, StringRef> parseSymbol(StringRef Expr) const {
179 size_t FirstNonSymbol =
180 Expr.find_first_not_of("0123456789"
181 "abcdefghijklmnopqrstuvwxyz"
182 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
184 return std::make_pair(Expr.substr(0, FirstNonSymbol),
185 Expr.substr(FirstNonSymbol).ltrim());
188 // Evaluate a call to decode_operand. Decode the instruction operand at the
189 // given symbol and get the value of the requested operand.
190 // Returns an error if the instruction cannot be decoded, or the requested
191 // operand is not an immediate.
192 // On success, retuns a pair containing the value of the operand, plus
193 // the expression remaining to be evaluated.
194 std::pair<EvalResult, StringRef> evalDecodeOperand(StringRef Expr) const {
195 if (!Expr.startswith("("))
196 return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
197 StringRef RemainingExpr = Expr.substr(1).ltrim();
199 std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
201 if (!Checker.checkSymbolIsValidForLoad(Symbol))
202 return std::make_pair(EvalResult(("Cannot decode unknown symbol '" +
203 Symbol + "'").str()),
206 if (!RemainingExpr.startswith(","))
207 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
210 RemainingExpr = RemainingExpr.substr(1).ltrim();
212 EvalResult OpIdxExpr;
213 std::tie(OpIdxExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
214 if (OpIdxExpr.hasError())
215 return std::make_pair(OpIdxExpr, "");
217 if (!RemainingExpr.startswith(")"))
218 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
221 RemainingExpr = RemainingExpr.substr(1).ltrim();
225 if (!decodeInst(Symbol, Inst, Size))
226 return std::make_pair(EvalResult(("Couldn't decode instruction at '" +
227 Symbol + "'").str()),
230 unsigned OpIdx = OpIdxExpr.getValue();
231 if (OpIdx >= Inst.getNumOperands())
232 return std::make_pair(EvalResult(("Invalid operand index '" +
233 std::to_string(OpIdx) +
234 " for instruction '" + Symbol +
235 ". Instruction has only " +
236 std::to_string(Inst.getNumOperands())
237 + " operands.").str()),
240 const MCOperand &Op = Inst.getOperand(OpIdx);
242 std::string InstrString;
243 raw_string_ostream InstrStringStream(InstrString);
244 Inst.dump_pretty(InstrStringStream,
245 Checker.Disassembler->getContext().getAsmInfo(),
246 Checker.InstPrinter);
247 return std::make_pair(EvalResult(("Operand '" + std::to_string(OpIdx) +
248 "' of instruction '" + Symbol +
249 "' is not an immediate.\n"
250 "Instruction is:\n " +
251 InstrStringStream.str()).str()),
255 return std::make_pair(EvalResult(Op.getImm()), RemainingExpr);
258 // Evaluate a call to next_pc. Decode the instruction at the given
259 // symbol and return the following program counter..
260 // Returns an error if the instruction cannot be decoded.
261 // On success, returns a pair containing the next PC, plus the length of the
262 // expression remaining to be evaluated.
263 std::pair<EvalResult, StringRef> evalNextPC(StringRef Expr) const {
264 if (!Expr.startswith("("))
265 return std::make_pair(unexpectedToken(Expr, Expr, "expected '('"), "");
266 StringRef RemainingExpr = Expr.substr(1).ltrim();
268 std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
270 if (!Checker.checkSymbolIsValidForLoad(Symbol))
271 return std::make_pair(EvalResult(("Cannot decode unknown symbol '"
272 + Symbol + "'").str()),
275 if (!RemainingExpr.startswith(")"))
276 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
279 RemainingExpr = RemainingExpr.substr(1).ltrim();
283 if (!decodeInst(Symbol, Inst, Size))
284 return std::make_pair(EvalResult(("Couldn't decode instruction at '" +
285 Symbol + "'").str()),
287 uint64_t NextPC = Checker.getSymbolAddress(Symbol) + Size;
289 return std::make_pair(EvalResult(NextPC), RemainingExpr);
292 // Evaluate an identiefer expr, which may be a symbol, or a call to
293 // one of the builtin functions: get_insn_opcode or get_insn_length.
294 // Return the result, plus the expression remaining to be parsed.
295 std::pair<EvalResult, StringRef> evalIdentifierExpr(StringRef Expr) const {
297 StringRef RemainingExpr;
298 std::tie(Symbol, RemainingExpr) = parseSymbol(Expr);
300 // Check for builtin function calls.
301 if (Symbol == "decode_operand")
302 return evalDecodeOperand(RemainingExpr);
303 else if (Symbol == "next_pc")
304 return evalNextPC(RemainingExpr);
306 // Looks like a plain symbol reference.
307 return std::make_pair(EvalResult(Checker.getSymbolAddress(Symbol)),
311 // Parse a number (hexadecimal or decimal) and return a (string, string)
312 // pair representing the number and the expression remaining to be parsed.
313 std::pair<StringRef, StringRef> parseNumberString(StringRef Expr) const {
314 size_t FirstNonDigit = StringRef::npos;
315 if (Expr.startswith("0x")) {
316 FirstNonDigit = Expr.find_first_not_of("0123456789abcdefABCDEF", 2);
317 if (FirstNonDigit == StringRef::npos)
318 FirstNonDigit = Expr.size();
320 FirstNonDigit = Expr.find_first_not_of("0123456789");
321 if (FirstNonDigit == StringRef::npos)
322 FirstNonDigit = Expr.size();
324 return std::make_pair(Expr.substr(0, FirstNonDigit),
325 Expr.substr(FirstNonDigit));
328 // Evaluate a constant numeric expression (hexidecimal or decimal) and
329 // return a pair containing the result, and the expression remaining to be
331 std::pair<EvalResult, StringRef> evalNumberExpr(StringRef Expr) const {
333 StringRef RemainingExpr;
334 std::tie(ValueStr, RemainingExpr) = parseNumberString(Expr);
336 if (ValueStr.empty() || !isdigit(ValueStr[0]))
337 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
341 ValueStr.getAsInteger(0, Value);
342 return std::make_pair(EvalResult(Value), RemainingExpr);
345 // Evaluate an expression of the form "(<expr>)" and return a pair
346 // containing the result of evaluating <expr>, plus the expression
347 // remaining to be parsed.
348 std::pair<EvalResult, StringRef> evalParensExpr(StringRef Expr) const {
349 assert(Expr.startswith("(") && "Not a parenthesized expression");
350 EvalResult SubExprResult;
351 StringRef RemainingExpr;
352 std::tie(SubExprResult, RemainingExpr) =
353 evalComplexExpr(evalSimpleExpr(Expr.substr(1).ltrim()));
354 if (SubExprResult.hasError())
355 return std::make_pair(SubExprResult, "");
356 if (!RemainingExpr.startswith(")"))
357 return std::make_pair(unexpectedToken(RemainingExpr, Expr,
360 RemainingExpr = RemainingExpr.substr(1).ltrim();
361 return std::make_pair(SubExprResult, RemainingExpr);
364 // Evaluate an expression in one of the following forms:
365 // *{<number>}<symbol>
366 // *{<number>}(<symbol> + <number>)
367 // *{<number>}(<symbol> - <number>)
368 // Return a pair containing the result, plus the expression remaining to be
370 std::pair<EvalResult, StringRef> evalLoadExpr(StringRef Expr) const {
371 assert(Expr.startswith("*") && "Not a load expression");
372 StringRef RemainingExpr = Expr.substr(1).ltrim();
374 if (!RemainingExpr.startswith("{"))
375 return std::make_pair(EvalResult("Expected '{' following '*'."), "");
376 RemainingExpr = RemainingExpr.substr(1).ltrim();
377 EvalResult ReadSizeExpr;
378 std::tie(ReadSizeExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
379 if (ReadSizeExpr.hasError())
380 return std::make_pair(ReadSizeExpr, RemainingExpr);
381 uint64_t ReadSize = ReadSizeExpr.getValue();
382 if (ReadSize < 1 || ReadSize > 8)
383 return std::make_pair(EvalResult("Invalid size for dereference."), "");
384 if (!RemainingExpr.startswith("}"))
385 return std::make_pair(EvalResult("Missing '}' for dereference."), "");
386 RemainingExpr = RemainingExpr.substr(1).ltrim();
388 // Check for '(symbol +/- constant)' form.
389 bool SymbolPlusConstant = false;
390 if (RemainingExpr.startswith("(")) {
391 SymbolPlusConstant = true;
392 RemainingExpr = RemainingExpr.substr(1).ltrim();
397 std::tie(Symbol, RemainingExpr) = parseSymbol(RemainingExpr);
399 if (!Checker.checkSymbolIsValidForLoad(Symbol))
400 return std::make_pair(EvalResult(("Cannot dereference unknown symbol '"
401 + Symbol + "'").str()),
404 // Set up defaut offset.
407 // Handle "+/- constant)" portion if necessary.
408 if (SymbolPlusConstant) {
409 char OpChar = RemainingExpr[0];
410 if (OpChar != '+' && OpChar != '-')
411 return std::make_pair(EvalResult("Invalid operator in load address."),
413 RemainingExpr = RemainingExpr.substr(1).ltrim();
415 EvalResult OffsetExpr;
416 std::tie(OffsetExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
418 Offset = (OpChar == '+') ?
419 OffsetExpr.getValue() : -1 * OffsetExpr.getValue();
421 if (!RemainingExpr.startswith(")"))
422 return std::make_pair(EvalResult("Missing ')' in load address."),
425 RemainingExpr = RemainingExpr.substr(1).ltrim();
428 return std::make_pair(
429 EvalResult(Checker.readMemoryAtSymbol(Symbol, Offset, ReadSize)),
433 // Evaluate a "simple" expression. This is any expression that _isn't_ an
434 // un-parenthesized binary expression.
436 // "Simple" expressions can be optionally bit-sliced. See evalSlicedExpr.
438 // Returns a pair containing the result of the evaluation, plus the
439 // expression remaining to be parsed.
440 std::pair<EvalResult, StringRef> evalSimpleExpr(StringRef Expr) const {
441 EvalResult SubExprResult;
442 StringRef RemainingExpr;
445 return std::make_pair(EvalResult("Unexpected end of expression"), "");
448 std::tie(SubExprResult, RemainingExpr) = evalParensExpr(Expr);
449 else if (Expr[0] == '*')
450 std::tie(SubExprResult, RemainingExpr) = evalLoadExpr(Expr);
451 else if (isalpha(Expr[0]))
452 std::tie(SubExprResult, RemainingExpr) = evalIdentifierExpr(Expr);
453 else if (isdigit(Expr[0]))
454 std::tie(SubExprResult, RemainingExpr) = evalNumberExpr(Expr);
456 if (SubExprResult.hasError())
457 return std::make_pair(SubExprResult, RemainingExpr);
459 // Evaluate bit-slice if present.
460 if (RemainingExpr.startswith("["))
461 std::tie(SubExprResult, RemainingExpr) =
462 evalSliceExpr(std::make_pair(SubExprResult, RemainingExpr));
464 return std::make_pair(SubExprResult, RemainingExpr);
467 // Evaluate a bit-slice of an expression.
468 // A bit-slice has the form "<expr>[high:low]". The result of evaluating a
469 // slice is the bits between high and low (inclusive) in the original
470 // expression, right shifted so that the "low" bit is in position 0 in the
472 // Returns a pair containing the result of the slice operation, plus the
473 // expression remaining to be parsed.
474 std::pair<EvalResult, StringRef> evalSliceExpr(
475 std::pair<EvalResult, StringRef> Ctx) const{
476 EvalResult SubExprResult;
477 StringRef RemainingExpr;
478 std::tie(SubExprResult, RemainingExpr) = Ctx;
480 assert(RemainingExpr.startswith("[") && "Not a slice expr.");
481 RemainingExpr = RemainingExpr.substr(1).ltrim();
483 EvalResult HighBitExpr;
484 std::tie(HighBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
486 if (HighBitExpr.hasError())
487 return std::make_pair(HighBitExpr, RemainingExpr);
489 if (!RemainingExpr.startswith(":"))
490 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
493 RemainingExpr = RemainingExpr.substr(1).ltrim();
495 EvalResult LowBitExpr;
496 std::tie(LowBitExpr, RemainingExpr) = evalNumberExpr(RemainingExpr);
498 if (LowBitExpr.hasError())
499 return std::make_pair(LowBitExpr, RemainingExpr);
501 if (!RemainingExpr.startswith("]"))
502 return std::make_pair(unexpectedToken(RemainingExpr, RemainingExpr,
505 RemainingExpr = RemainingExpr.substr(1).ltrim();
507 unsigned HighBit = HighBitExpr.getValue();
508 unsigned LowBit = LowBitExpr.getValue();
509 uint64_t Mask = ((uint64_t)1 << (HighBit - LowBit + 1)) - 1;
510 uint64_t SlicedValue = (SubExprResult.getValue() >> LowBit) & Mask;
511 return std::make_pair(EvalResult(SlicedValue), RemainingExpr);
514 // Evaluate a "complex" expression.
515 // Takes an already evaluated subexpression and checks for the presence of a
516 // binary operator, computing the result of the binary operation if one is
517 // found. Used to make arithmetic expressions left-associative.
518 // Returns a pair containing the ultimate result of evaluating the
519 // expression, plus the expression remaining to be evaluated.
520 std::pair<EvalResult, StringRef> evalComplexExpr(
521 std::pair<EvalResult, StringRef> Ctx) const {
522 EvalResult LHSResult;
523 StringRef RemainingExpr;
524 std::tie(LHSResult, RemainingExpr) = Ctx;
526 // If there was an error, or there's nothing left to evaluate, return the
528 if (LHSResult.hasError() || RemainingExpr == "")
529 return std::make_pair(LHSResult, RemainingExpr);
531 // Otherwise check if this is a binary expressioan.
533 std::tie(BinOp, RemainingExpr) = parseBinOpToken(RemainingExpr);
535 // If this isn't a recognized expression just return.
536 if (BinOp == BinOpToken::Invalid)
537 return std::make_pair(LHSResult, RemainingExpr);
539 // This is a recognized bin-op. Evaluate the RHS, then evaluate the binop.
540 EvalResult RHSResult;
541 std::tie(RHSResult, RemainingExpr) = evalSimpleExpr(RemainingExpr);
543 // If there was an error evaluating the RHS, return it.
544 if (RHSResult.hasError())
545 return std::make_pair(RHSResult, RemainingExpr);
547 // This is a binary expression - evaluate and try to continue as a
549 EvalResult ThisResult(computeBinOpResult(BinOp, LHSResult, RHSResult));
551 return evalComplexExpr(std::make_pair(ThisResult, RemainingExpr));
554 bool decodeInst(StringRef Symbol, MCInst &Inst, uint64_t &Size) const {
555 MCDisassembler *Dis = Checker.Disassembler;
556 StringRef SectionMem = Checker.getSubsectionStartingAt(Symbol);
557 StringRefMemoryObject SectionBytes(SectionMem, 0);
559 MCDisassembler::DecodeStatus S =
560 Dis->getInstruction(Inst, Size, SectionBytes, 0, nulls(), nulls());
562 return (S == MCDisassembler::Success);
569 bool RuntimeDyldChecker::check(StringRef CheckExpr) const {
570 CheckExpr = CheckExpr.trim();
571 DEBUG(llvm::dbgs() << "RuntimeDyldChecker: Checking '" << CheckExpr
573 RuntimeDyldCheckerExprEval P(*this, ErrStream);
574 bool Result = P.evaluate(CheckExpr);
576 DEBUG(llvm::dbgs() << "RuntimeDyldChecker: '" << CheckExpr << "' "
577 << (Result ? "passed" : "FAILED") << ".\n");
581 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix,
582 MemoryBuffer* MemBuf) const {
583 bool DidAllTestsPass = true;
584 unsigned NumRules = 0;
586 const char *LineStart = MemBuf->getBufferStart();
589 while (LineStart != MemBuf->getBufferEnd() &&
590 std::isspace(*LineStart))
593 while (LineStart != MemBuf->getBufferEnd() && *LineStart != '\0') {
594 const char *LineEnd = LineStart;
595 while (LineEnd != MemBuf->getBufferEnd() &&
596 *LineEnd != '\r' && *LineEnd != '\n')
599 StringRef Line(LineStart, LineEnd - LineStart);
600 if (Line.startswith(RulePrefix)) {
601 DidAllTestsPass &= check(Line.substr(RulePrefix.size()));
607 while (LineStart != MemBuf->getBufferEnd() &&
608 std::isspace(*LineStart))
611 return DidAllTestsPass && (NumRules != 0);
614 bool RuntimeDyldChecker::checkSymbolIsValidForLoad(StringRef Symbol) const {
615 return RTDyld.getSymbolAddress(Symbol) != nullptr;
618 uint64_t RuntimeDyldChecker::getSymbolAddress(StringRef Symbol) const {
619 return RTDyld.getAnySymbolRemoteAddress(Symbol);
622 uint64_t RuntimeDyldChecker::readMemoryAtSymbol(StringRef Symbol,
624 unsigned Size) const {
625 uint8_t *Src = RTDyld.getSymbolAddress(Symbol);
627 memcpy(&Result, Src + Offset, Size);
631 StringRef RuntimeDyldChecker::getSubsectionStartingAt(StringRef Name) const {
632 RuntimeDyldImpl::SymbolTableMap::const_iterator pos =
633 RTDyld.GlobalSymbolTable.find(Name);
634 if (pos == RTDyld.GlobalSymbolTable.end())
636 RuntimeDyldImpl::SymbolLoc Loc = pos->second;
637 uint8_t *SectionAddr = RTDyld.getSectionAddress(Loc.first);
638 return StringRef(reinterpret_cast<const char*>(SectionAddr) + Loc.second,
639 RTDyld.Sections[Loc.first].Size - Loc.second);