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: 31 RuntimeDyldCheckerExprEval(const RuntimeDyldCheckerImpl &Checker, 32 raw_ostream &ErrStream) 33 : Checker(Checker) {} 34 35 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; 82 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: 99 EvalResult() : Value(0), ErrorMsg("") {} 100 EvalResult(uint64_t Value) : Value(Value), ErrorMsg("") {} 101 EvalResult(std::string ErrorMsg) 102 : Value(0), ErrorMsg(std::move(ErrorMsg)) {} 103 uint64_t getValue() const { return Value; } 104 bool hasError() const { return ErrorMsg != ""; } 105 const std::string &getErrorMsg() const { return ErrorMsg; } 106 107 private: 108 uint64_t Value; 109 std::string ErrorMsg; 110 }; 111 112 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 130 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 146 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 153 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 185 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. 207 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. 222 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. 289 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. 327 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 372 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. 412 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. 451 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. 469 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. 485 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. 505 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. 547 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> 587 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> 631 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 665 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 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 689 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 700 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 731 bool RuntimeDyldCheckerImpl::isSymbolValid(StringRef Symbol) const { 732 if (getRTDyld().getSymbol(Symbol)) 733 return true; 734 return !!getRTDyld().Resolver.findSymbol(Symbol); 735 } 736 737 uint64_t RuntimeDyldCheckerImpl::getSymbolLocalAddr(StringRef Symbol) const { 738 return static_cast<uint64_t>( 739 reinterpret_cast<uintptr_t>(getRTDyld().getSymbolLocalAddress(Symbol))); 740 } 741 742 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 748 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> 758 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 789 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 812 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 851 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 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 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 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 914 RuntimeDyldChecker::~RuntimeDyldChecker() {} 915 916 RuntimeDyld& RuntimeDyldChecker::getRTDyld() { 917 return Impl->RTDyld; 918 } 919 920 const RuntimeDyld& RuntimeDyldChecker::getRTDyld() const { 921 return Impl->RTDyld; 922 } 923 924 bool RuntimeDyldChecker::check(StringRef CheckExpr) const { 925 return Impl->check(CheckExpr); 926 } 927 928 bool RuntimeDyldChecker::checkAllRulesInBuffer(StringRef RulePrefix, 929 MemoryBuffer *MemBuf) const { 930 return Impl->checkAllRulesInBuffer(RulePrefix, MemBuf); 931 } 932 933 std::pair<uint64_t, std::string> 934 RuntimeDyldChecker::getSectionAddr(StringRef FileName, StringRef SectionName, 935 bool LocalAddress) { 936 return Impl->getSectionAddr(FileName, SectionName, LocalAddress); 937 } 938