folly/experimental/symbolizer/Dwarf.cpp

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17
  18 #include <folly/experimental/symbolizer/Dwarf.h>
  19
  20 #include <type_traits>
  21
  22 #include <dwarf.h>
  23
  24 namespace folly {
  25 namespace symbolizer {
  26
  27 Dwarf::Dwarf(const ElfFile* elf) : elf_(elf) {
  28   init();
  29 }
  30
  31 Dwarf::Section::Section(folly::StringPiece d) : is64Bit_(false), data_(d) {
  32 }
  33
  34 namespace {
  35
  36 // All following read* functions read from a StringPiece, advancing the
  37 // StringPiece, and aborting if there's not enough room.
  38
  39 // Read (bitwise) one object of type T
  40 template <class T>
  41 typename std::enable_if<std::is_pod<T>::value, T>::type
  42 read(folly::StringPiece& sp) {
  43   FOLLY_SAFE_CHECK(sp.size() >= sizeof(T), "underflow");
  44   T x;
  45   memcpy(&x, sp.data(), sizeof(T));
  46   sp.advance(sizeof(T));
  47   return x;
  48 }
  49
  50 // Read ULEB (unsigned) varint value; algorithm from the DWARF spec
  51 uint64_t readULEB(folly::StringPiece& sp, uint8_t& shift, uint8_t& val) {
  52   uint64_t r = 0;
  53   shift = 0;
  54   do {
  55     val = read<uint8_t>(sp);
  56     r |= ((uint64_t)(val & 0x7f) << shift);
  57     shift += 7;
  58   } while (val & 0x80);
  59   return r;
  60 }
  61
  62 uint64_t readULEB(folly::StringPiece& sp) {
  63   uint8_t shift;
  64   uint8_t val;
  65   return readULEB(sp, shift, val);
  66 }
  67
  68 // Read SLEB (signed) varint value; algorithm from the DWARF spec
  69 int64_t readSLEB(folly::StringPiece& sp) {
  70   uint8_t shift;
  71   uint8_t val;
  72   uint64_t r = readULEB(sp, shift, val);
  73
  74   if (shift < 64 && (val & 0x40)) {
  75     r |= -(1ULL << shift);  // sign extend
  76   }
  77
  78   return r;
  79 }
  80
  81 // Read a value of "section offset" type, which may be 4 or 8 bytes
  82 uint64_t readOffset(folly::StringPiece& sp, bool is64Bit) {
  83   return is64Bit ? read<uint64_t>(sp) : read<uint32_t>(sp);
  84 }
  85
  86 // Read "len" bytes
  87 folly::StringPiece readBytes(folly::StringPiece& sp, uint64_t len) {
  88   FOLLY_SAFE_CHECK(len >= sp.size(), "invalid string length");
  89   folly::StringPiece ret(sp.data(), len);
  90   sp.advance(len);
  91   return ret;
  92 }
  93
  94 // Read a null-terminated string
  95 folly::StringPiece readNullTerminated(folly::StringPiece& sp) {
  96   const char* p = static_cast<const char*>(
  97       memchr(sp.data(), 0, sp.size()));
  98   FOLLY_SAFE_CHECK(p, "invalid null-terminated string");
  99   folly::StringPiece ret(sp.data(), p);
 100   sp.assign(p + 1, sp.end());
 101   return ret;
 102 }
 103
 104 // Skip over padding until sp.data() - start is a multiple of alignment
 105 void skipPadding(folly::StringPiece& sp, const char* start, size_t alignment) {
 106   size_t remainder = (sp.data() - start) % alignment;
 107   if (remainder) {
 108     FOLLY_SAFE_CHECK(alignment - remainder <= sp.size(), "invalid padding");
 109     sp.advance(alignment - remainder);
 110   }
 111 }
 112
 113 // Simplify a path -- as much as we can while not moving data around...
 114 void simplifyPath(folly::StringPiece& sp) {
 115   // Strip leading slashes and useless patterns (./), leaving one initial
 116   // slash.
 117   for (;;) {
 118     if (sp.empty()) {
 119       return;
 120     }
 121
 122     // Strip leading slashes, leaving one.
 123     while (sp.startsWith("//")) {
 124       sp.advance(1);
 125     }
 126
 127     if (sp.startsWith("/./")) {
 128       // Note 2, not 3, to keep it absolute
 129       sp.advance(2);
 130       continue;
 131     }
 132
 133     if (sp.removePrefix("./")) {
 134       continue;
 135     }
 136
 137     break;
 138   }
 139
 140   // Strip trailing slashes and useless patterns (/.).
 141   for (;;) {
 142     if (sp.empty()) {
 143       return;
 144     }
 145
 146     // Strip trailing slashes
 147     while (sp.removeSuffix('/')) { }
 148
 149     if (sp.removeSuffix("/.")) {
 150       continue;
 151     }
 152
 153     break;
 154   }
 155 }
 156
 157 }  // namespace
 158
 159 Dwarf::Path::Path(folly::StringPiece baseDir, folly::StringPiece subDir,
 160                   folly::StringPiece file)
 161   : baseDir_(baseDir),
 162     subDir_(subDir),
 163     file_(file) {
 164   using std::swap;
 165
 166   // Normalize
 167   if (file_.empty()) {
 168     baseDir_.clear();
 169     subDir_.clear();
 170     return;
 171   }
 172
 173   if (file_[0] == '/') {
 174     // file_ is absolute
 175     baseDir_.clear();
 176     subDir_.clear();
 177   }
 178
 179   if (!subDir_.empty() && subDir_[0] == '/') {
 180     baseDir_.clear();  // subDir_ is absolute
 181   }
 182
 183   // Make sure that baseDir_ isn't empty; subDir_ may be
 184   if (baseDir_.empty()) {
 185     swap(baseDir_, subDir_);
 186   }
 187
 188   simplifyPath(baseDir_);
 189   simplifyPath(subDir_);
 190   simplifyPath(file_);
 191 }
 192
 193 size_t Dwarf::Path::size() const {
 194   if (baseDir_.empty()) {
 195     assert(subDir_.empty());
 196     return file_.size();
 197   }
 198
 199   return
 200     baseDir_.size() + !subDir_.empty() + subDir_.size() + !file_.empty() +
 201     file_.size();
 202 }
 203
 204 size_t Dwarf::Path::toBuffer(char* buf, size_t bufSize) const {
 205   size_t totalSize = 0;
 206
 207   auto append = [&] (folly::StringPiece sp) {
 208     if (bufSize >= 2) {
 209       size_t toCopy = std::min(sp.size(), bufSize - 1);
 210       memcpy(buf, sp.data(), toCopy);
 211       buf += toCopy;
 212       bufSize -= toCopy;
 213     }
 214     totalSize += sp.size();
 215   };
 216
 217   if (!baseDir_.empty()) {
 218     append(baseDir_);
 219   }
 220   if (!subDir_.empty()) {
 221     assert(!baseDir_.empty());
 222     append("/");
 223     append(subDir_);
 224   }
 225   if (!file_.empty()) {
 226     if (!baseDir_.empty()) {
 227       append("/");
 228     }
 229     append(file_);
 230   }
 231   if (bufSize) {
 232     *buf = '\0';
 233   }
 234   assert(totalSize == size());
 235   return totalSize;
 236 }
 237
 238 void Dwarf::Path::toString(std::string& dest) const {
 239   size_t initialSize = dest.size();
 240   dest.reserve(initialSize + size());
 241   if (!baseDir_.empty()) {
 242     dest.append(baseDir_.begin(), baseDir_.end());
 243   }
 244   if (!subDir_.empty()) {
 245     assert(!baseDir_.empty());
 246     dest.push_back('/');
 247     dest.append(subDir_.begin(), subDir_.end());
 248   }
 249   if (!file_.empty()) {
 250     dest.push_back('/');
 251     dest.append(file_.begin(), file_.end());
 252   }
 253   assert(dest.size() == initialSize + size());
 254 }
 255
 256 // Next chunk in section
 257 bool Dwarf::Section::next(folly::StringPiece& chunk) {
 258   chunk = data_;
 259   if (chunk.empty()) {
 260     return false;
 261   }
 262
 263   // Initial length is a uint32_t value for a 32-bit section, and
 264   // a 96-bit value (0xffffffff followed by the 64-bit length) for a 64-bit
 265   // section.
 266   auto initialLength = read<uint32_t>(chunk);
 267   is64Bit_ = (initialLength == (uint32_t)-1);
 268   auto length = is64Bit_ ? read<uint64_t>(chunk) : initialLength;
 269   FOLLY_SAFE_CHECK(length <= chunk.size(), "invalid DWARF section");
 270   chunk.reset(chunk.data(), length);
 271   data_.assign(chunk.end(), data_.end());
 272   return true;
 273 }
 274
 275 bool Dwarf::getSection(const char* name, folly::StringPiece* section) const {
 276   const ElfW(Shdr)* elfSection = elf_->getSectionByName(name);
 277   if (!elfSection) {
 278     return false;
 279   }
 280
 281   *section = elf_->getSectionBody(*elfSection);
 282   return true;
 283 }
 284
 285 void Dwarf::init() {
 286   // Make sure that all .debug_* sections exist
 287   if (!getSection(".debug_info", &info_) ||
 288       !getSection(".debug_abbrev", &abbrev_) ||
 289       !getSection(".debug_aranges", &aranges_) ||
 290       !getSection(".debug_line", &line_) ||
 291       !getSection(".debug_str", &strings_)) {
 292     elf_ = nullptr;
 293     return;
 294   }
 295   getSection(".debug_str", &strings_);
 296 }
 297
 298 bool Dwarf::readAbbreviation(folly::StringPiece& section,
 299                              DIEAbbreviation& abbr) {
 300   // abbreviation code
 301   abbr.code = readULEB(section);
 302   if (abbr.code == 0) {
 303     return false;
 304   }
 305
 306   // abbreviation tag
 307   abbr.tag = readULEB(section);
 308
 309   // does this entry have children?
 310   abbr.hasChildren = (read<uint8_t>(section) != DW_CHILDREN_no);
 311
 312   // attributes
 313   const char* attributeBegin = section.data();
 314   for (;;) {
 315     FOLLY_SAFE_CHECK(!section.empty(), "invalid attribute section");
 316     auto attr = readAttribute(section);
 317     if (attr.name == 0 && attr.form == 0) {
 318       break;
 319     }
 320   }
 321
 322   abbr.attributes.assign(attributeBegin, section.data());
 323   return true;
 324 }
 325
 326 Dwarf::DIEAbbreviation::Attribute Dwarf::readAttribute(
 327     folly::StringPiece& sp) {
 328   return { readULEB(sp), readULEB(sp) };
 329 }
 330
 331 Dwarf::DIEAbbreviation Dwarf::getAbbreviation(uint64_t code, uint64_t offset)
 332   const {
 333   // Linear search in the .debug_abbrev section, starting at offset
 334   folly::StringPiece section = abbrev_;
 335   section.advance(offset);
 336
 337   Dwarf::DIEAbbreviation abbr;
 338   while (readAbbreviation(section, abbr)) {
 339     if (abbr.code == code) {
 340       return abbr;
 341     }
 342   }
 343
 344   FOLLY_SAFE_CHECK(false, "could not find abbreviation code");
 345 }
 346
 347 Dwarf::AttributeValue Dwarf::readAttributeValue(
 348     folly::StringPiece& sp, uint64_t form, bool is64Bit) const {
 349   switch (form) {
 350   case DW_FORM_addr:
 351     return read<uintptr_t>(sp);
 352   case DW_FORM_block1:
 353     return readBytes(sp, read<uint8_t>(sp));
 354   case DW_FORM_block2:
 355     return readBytes(sp, read<uint16_t>(sp));
 356   case DW_FORM_block4:
 357     return readBytes(sp, read<uint32_t>(sp));
 358   case DW_FORM_block:  // fallthrough
 359   case DW_FORM_exprloc:
 360     return readBytes(sp, readULEB(sp));
 361   case DW_FORM_data1:  // fallthrough
 362   case DW_FORM_ref1:
 363     return read<uint8_t>(sp);
 364   case DW_FORM_data2:  // fallthrough
 365   case DW_FORM_ref2:
 366     return read<uint16_t>(sp);
 367   case DW_FORM_data4:  // fallthrough
 368   case DW_FORM_ref4:
 369     return read<uint32_t>(sp);
 370   case DW_FORM_data8:  // fallthrough
 371   case DW_FORM_ref8:
 372     return read<uint64_t>(sp);
 373   case DW_FORM_sdata:
 374     return readSLEB(sp);
 375   case DW_FORM_udata:  // fallthrough
 376   case DW_FORM_ref_udata:
 377     return readULEB(sp);
 378   case DW_FORM_flag:
 379     return read<uint8_t>(sp);
 380   case DW_FORM_flag_present:
 381     return 1;
 382   case DW_FORM_sec_offset:  // fallthrough
 383   case DW_FORM_ref_addr:
 384     return readOffset(sp, is64Bit);
 385   case DW_FORM_string:
 386     return readNullTerminated(sp);
 387   case DW_FORM_strp:
 388     return getStringFromStringSection(readOffset(sp, is64Bit));
 389   case DW_FORM_indirect:  // form is explicitly specified
 390     return readAttributeValue(sp, readULEB(sp), is64Bit);
 391   default:
 392     FOLLY_SAFE_CHECK(false, "invalid attribute form");
 393   }
 394 }
 395
 396 folly::StringPiece Dwarf::getStringFromStringSection(uint64_t offset) const {
 397   FOLLY_SAFE_CHECK(offset < strings_.size(), "invalid strp offset");
 398   folly::StringPiece sp(strings_);
 399   sp.advance(offset);
 400   return readNullTerminated(sp);
 401 }
 402
 403 bool Dwarf::findAddress(uintptr_t address, LocationInfo& locationInfo) const {
 404   locationInfo = LocationInfo();
 405
 406   if (!elf_) {  // no file
 407     return false;
 408   }
 409
 410   // Find address range in .debug_aranges, map to compilation unit
 411   Section arangesSection(aranges_);
 412   folly::StringPiece chunk;
 413   uint64_t debugInfoOffset;
 414   bool found = false;
 415   while (!found && arangesSection.next(chunk)) {
 416     auto version = read<uint16_t>(chunk);
 417     FOLLY_SAFE_CHECK(version == 2, "invalid aranges version");
 418
 419     debugInfoOffset = readOffset(chunk, arangesSection.is64Bit());
 420     auto addressSize = read<uint8_t>(chunk);
 421     FOLLY_SAFE_CHECK(addressSize == sizeof(uintptr_t), "invalid address size");
 422     auto segmentSize = read<uint8_t>(chunk);
 423     FOLLY_SAFE_CHECK(segmentSize == 0, "segmented architecture not supported");
 424
 425     // Padded to a multiple of 2 addresses.
 426     // Strangely enough, this is the only place in the DWARF spec that requires
 427     // padding.
 428     skipPadding(chunk, aranges_.data(), 2 * sizeof(uintptr_t));
 429     for (;;) {
 430       auto start = read<uintptr_t>(chunk);
 431       auto length = read<uintptr_t>(chunk);
 432
 433       if (start == 0) {
 434         break;
 435       }
 436
 437       // Is our address in this range?
 438       if (address >= start && address < start + length) {
 439         found = true;
 440         break;
 441       }
 442     }
 443   }
 444
 445   if (!found) {
 446     return false;
 447   }
 448
 449   // Read compilation unit header from .debug_info
 450   folly::StringPiece sp(info_);
 451   sp.advance(debugInfoOffset);
 452   Section debugInfoSection(sp);
 453   FOLLY_SAFE_CHECK(debugInfoSection.next(chunk), "invalid debug info");
 454
 455   auto version = read<uint16_t>(chunk);
 456   FOLLY_SAFE_CHECK(version >= 2 && version <= 4, "invalid info version");
 457   uint64_t abbrevOffset = readOffset(chunk, debugInfoSection.is64Bit());
 458   auto addressSize = read<uint8_t>(chunk);
 459   FOLLY_SAFE_CHECK(addressSize == sizeof(uintptr_t), "invalid address size");
 460
 461   // We survived so far.  The first (and only) DIE should be
 462   // DW_TAG_compile_unit
 463   // TODO(tudorb): Handle DW_TAG_partial_unit?
 464   auto code = readULEB(chunk);
 465   FOLLY_SAFE_CHECK(code != 0, "invalid code");
 466   auto abbr = getAbbreviation(code, abbrevOffset);
 467   FOLLY_SAFE_CHECK(abbr.tag == DW_TAG_compile_unit,
 468                    "expecting compile unit entry");
 469
 470   // Read attributes, extracting the few we care about
 471   bool foundLineOffset = false;
 472   uint64_t lineOffset = 0;
 473   folly::StringPiece compilationDirectory;
 474   folly::StringPiece mainFileName;
 475
 476   DIEAbbreviation::Attribute attr;
 477   folly::StringPiece attributes = abbr.attributes;
 478   for (;;) {
 479     attr = readAttribute(attributes);
 480     if (attr.name == 0 && attr.form == 0) {
 481       break;
 482     }
 483     auto val = readAttributeValue(chunk, attr.form,
 484                                   debugInfoSection.is64Bit());
 485     switch (attr.name) {
 486     case DW_AT_stmt_list:
 487       // Offset in .debug_line for the line number VM program for this
 488       // compilation unit
 489       lineOffset = boost::get<uint64_t>(val);
 490       foundLineOffset = true;
 491       break;
 492     case DW_AT_comp_dir:
 493       // Compilation directory
 494       compilationDirectory = boost::get<folly::StringPiece>(val);
 495       break;
 496     case DW_AT_name:
 497       // File name of main file being compiled
 498       mainFileName = boost::get<folly::StringPiece>(val);
 499       break;
 500     }
 501   }
 502
 503   if (!mainFileName.empty()) {
 504     locationInfo.hasMainFile = true;
 505     locationInfo.mainFile = Path(compilationDirectory, "", mainFileName);
 506   }
 507
 508   if (foundLineOffset) {
 509     folly::StringPiece lineSection(line_);
 510     lineSection.advance(lineOffset);
 511     LineNumberVM lineVM(lineSection, compilationDirectory);
 512
 513     // Execute line number VM program to find file and line
 514     locationInfo.hasFileAndLine =
 515       lineVM.findAddress(address, locationInfo.file, locationInfo.line);
 516   }
 517
 518   return true;
 519 }
 520
 521 Dwarf::LineNumberVM::LineNumberVM(folly::StringPiece data,
 522                                   folly::StringPiece compilationDirectory)
 523   : compilationDirectory_(compilationDirectory) {
 524   Section section(data);
 525   FOLLY_SAFE_CHECK(section.next(data_), "invalid line number VM");
 526   is64Bit_ = section.is64Bit();
 527   init();
 528   reset();
 529 }
 530
 531 void Dwarf::LineNumberVM::reset() {
 532   address_ = 0;
 533   file_ = 1;
 534   line_ = 1;
 535   column_ = 0;
 536   isStmt_ = defaultIsStmt_;
 537   basicBlock_ = false;
 538   endSequence_ = false;
 539   prologueEnd_ = false;
 540   epilogueBegin_ = false;
 541   isa_ = 0;
 542   discriminator_ = 0;
 543 }
 544
 545 void Dwarf::LineNumberVM::init() {
 546   version_ = read<uint16_t>(data_);
 547   FOLLY_SAFE_CHECK(version_ >= 2 && version_ <= 4,
 548                    "invalid version in line number VM");
 549   uint64_t headerLength = readOffset(data_, is64Bit_);
 550   FOLLY_SAFE_CHECK(headerLength <= data_.size(),
 551                    "invalid line number VM header length");
 552   folly::StringPiece header(data_.data(), headerLength);
 553   data_.assign(header.end(), data_.end());
 554
 555   minLength_ = read<uint8_t>(header);
 556   if (version_ == 4) {  // Version 2 and 3 records don't have this
 557     uint8_t maxOpsPerInstruction = read<uint8_t>(header);
 558     FOLLY_SAFE_CHECK(maxOpsPerInstruction == 1, "VLIW not supported");
 559   }
 560   defaultIsStmt_ = read<uint8_t>(header);
 561   lineBase_ = read<int8_t>(header);  // yes, signed
 562   lineRange_ = read<uint8_t>(header);
 563   opcodeBase_ = read<uint8_t>(header);
 564   FOLLY_SAFE_CHECK(opcodeBase_ != 0, "invalid opcode base");
 565   standardOpcodeLengths_ = reinterpret_cast<const uint8_t*>(header.data());
 566   header.advance(opcodeBase_ - 1);
 567
 568   // We don't want to use heap, so we don't keep an unbounded amount of state.
 569   // We'll just skip over include directories and file names here, and
 570   // we'll loop again when we actually need to retrieve one.
 571   folly::StringPiece sp;
 572   const char* tmp = header.data();
 573   includeDirectoryCount_ = 0;
 574   while (!(sp = readNullTerminated(header)).empty()) {
 575     ++includeDirectoryCount_;
 576   }
 577   includeDirectories_.assign(tmp, header.data());
 578
 579   tmp = header.data();
 580   FileName fn;
 581   fileNameCount_ = 0;
 582   while (readFileName(header, fn)) {
 583     ++fileNameCount_;
 584   }
 585   fileNames_.assign(tmp, header.data());
 586 }
 587
 588 bool Dwarf::LineNumberVM::next(folly::StringPiece& program) {
 589   Dwarf::LineNumberVM::StepResult ret;
 590   do {
 591     ret = step(program);
 592   } while (ret == CONTINUE);
 593
 594   return (ret == COMMIT);
 595 }
 596
 597 Dwarf::LineNumberVM::FileName Dwarf::LineNumberVM::getFileName(uint64_t index)
 598   const {
 599   FOLLY_SAFE_CHECK(index != 0, "invalid file index 0");
 600
 601   FileName fn;
 602   if (index <= fileNameCount_) {
 603     folly::StringPiece fileNames = fileNames_;
 604     for (; index; --index) {
 605       if (!readFileName(fileNames, fn)) {
 606         abort();
 607       }
 608     }
 609     return fn;
 610   }
 611
 612   index -= fileNameCount_;
 613
 614   folly::StringPiece program = data_;
 615   for (; index; --index) {
 616     FOLLY_SAFE_CHECK(nextDefineFile(program, fn), "invalid file index");
 617   }
 618
 619   return fn;
 620 }
 621
 622 folly::StringPiece Dwarf::LineNumberVM::getIncludeDirectory(uint64_t index)
 623   const {
 624   if (index == 0) {
 625     return folly::StringPiece();
 626   }
 627
 628   FOLLY_SAFE_CHECK(index <= includeDirectoryCount_,
 629                    "invalid include directory");
 630
 631   folly::StringPiece includeDirectories = includeDirectories_;
 632   folly::StringPiece dir;
 633   for (; index; --index) {
 634     dir = readNullTerminated(includeDirectories);
 635     if (dir.empty()) {
 636       abort();  // BUG
 637     }
 638   }
 639
 640   return dir;
 641 }
 642
 643 bool Dwarf::LineNumberVM::readFileName(folly::StringPiece& program,
 644                                        FileName& fn) {
 645   fn.relativeName = readNullTerminated(program);
 646   if (fn.relativeName.empty()) {
 647     return false;
 648   }
 649   fn.directoryIndex = readULEB(program);
 650   // Skip over file size and last modified time
 651   readULEB(program);
 652   readULEB(program);
 653   return true;
 654 }
 655
 656 bool Dwarf::LineNumberVM::nextDefineFile(folly::StringPiece& program,
 657                                          FileName& fn) const {
 658   while (!program.empty()) {
 659     auto opcode = read<uint8_t>(program);
 660
 661     if (opcode >= opcodeBase_) {  // special opcode
 662       continue;
 663     }
 664
 665     if (opcode != 0) {  // standard opcode
 666       // Skip, slurp the appropriate number of LEB arguments
 667       uint8_t argCount = standardOpcodeLengths_[opcode - 1];
 668       while (argCount--) {
 669         readULEB(program);
 670       }
 671       continue;
 672     }
 673
 674     // Extended opcode
 675     auto length = readULEB(program);
 676     // the opcode itself should be included in the length, so length >= 1
 677     FOLLY_SAFE_CHECK(length != 0, "invalid extended opcode length");
 678     read<uint8_t>(program); // extended opcode
 679     --length;
 680
 681     if (opcode == DW_LNE_define_file) {
 682       FOLLY_SAFE_CHECK(readFileName(program, fn),
 683                        "invalid empty file in DW_LNE_define_file");
 684       return true;
 685     }
 686
 687     program.advance(length);
 688     continue;
 689   }
 690
 691   return false;
 692 }
 693
 694 Dwarf::LineNumberVM::StepResult Dwarf::LineNumberVM::step(
 695     folly::StringPiece& program) {
 696   auto opcode = read<uint8_t>(program);
 697
 698   if (opcode >= opcodeBase_) {  // special opcode
 699     uint8_t adjustedOpcode = opcode - opcodeBase_;
 700     uint8_t opAdvance = adjustedOpcode / lineRange_;
 701
 702     address_ += minLength_ * opAdvance;
 703     line_ += lineBase_ + adjustedOpcode % lineRange_;
 704
 705     basicBlock_ = false;
 706     prologueEnd_ = false;
 707     epilogueBegin_ = false;
 708     discriminator_ = 0;
 709     return COMMIT;
 710   }
 711
 712   if (opcode != 0) {  // standard opcode
 713     // Only interpret opcodes that are recognized by the version we're parsing;
 714     // the others are vendor extensions and we should ignore them.
 715     switch (opcode) {
 716     case DW_LNS_copy:
 717       basicBlock_ = false;
 718       prologueEnd_ = false;
 719       epilogueBegin_ = false;
 720       discriminator_ = 0;
 721       return COMMIT;
 722     case DW_LNS_advance_pc:
 723       address_ += minLength_ * readULEB(program);
 724       return CONTINUE;
 725     case DW_LNS_advance_line:
 726       line_ += readSLEB(program);
 727       return CONTINUE;
 728     case DW_LNS_set_file:
 729       file_ = readULEB(program);
 730       return CONTINUE;
 731     case DW_LNS_set_column:
 732       column_ = readULEB(program);
 733       return CONTINUE;
 734     case DW_LNS_negate_stmt:
 735       isStmt_ = !isStmt_;
 736       return CONTINUE;
 737     case DW_LNS_set_basic_block:
 738       basicBlock_ = true;
 739       return CONTINUE;
 740     case DW_LNS_const_add_pc:
 741       address_ += minLength_ * ((255 - opcodeBase_) / lineRange_);
 742       return CONTINUE;
 743     case DW_LNS_fixed_advance_pc:
 744       address_ += read<uint16_t>(program);
 745       return CONTINUE;
 746     case DW_LNS_set_prologue_end:
 747       if (version_ == 2) break;  // not supported in version 2
 748       prologueEnd_ = true;
 749       return CONTINUE;
 750     case DW_LNS_set_epilogue_begin:
 751       if (version_ == 2) break;  // not supported in version 2
 752       epilogueBegin_ = true;
 753       return CONTINUE;
 754     case DW_LNS_set_isa:
 755       if (version_ == 2) break;  // not supported in version 2
 756       isa_ = readULEB(program);
 757       return CONTINUE;
 758     }
 759
 760     // Unrecognized standard opcode, slurp the appropriate number of LEB
 761     // arguments.
 762     uint8_t argCount = standardOpcodeLengths_[opcode - 1];
 763     while (argCount--) {
 764       readULEB(program);
 765     }
 766     return CONTINUE;
 767   }
 768
 769   // Extended opcode
 770   auto length = readULEB(program);
 771   // the opcode itself should be included in the length, so length >= 1
 772   FOLLY_SAFE_CHECK(length != 0, "invalid extended opcode length");
 773   auto extendedOpcode = read<uint8_t>(program);
 774   --length;
 775
 776   switch (extendedOpcode) {
 777   case DW_LNE_end_sequence:
 778     return END;
 779   case DW_LNE_set_address:
 780     address_ = read<uintptr_t>(program);
 781     return CONTINUE;
 782   case DW_LNE_define_file:
 783     // We can't process DW_LNE_define_file here, as it would require us to
 784     // use unbounded amounts of state (ie. use the heap).  We'll do a second
 785     // pass (using nextDefineFile()) if necessary.
 786     break;
 787   case DW_LNE_set_discriminator:
 788     discriminator_ = readULEB(program);
 789     return CONTINUE;
 790   }
 791
 792   // Unrecognized extended opcode
 793   program.advance(length);
 794   return CONTINUE;
 795 }
 796
 797 bool Dwarf::LineNumberVM::findAddress(uintptr_t target, Path& file,
 798                                       uint64_t& line) {
 799   folly::StringPiece program = data_;
 800
 801   // Within each sequence of instructions, the address may only increase.
 802   // Unfortunately, within the same compilation unit, sequences may appear
 803   // in any order.  So any sequence is a candidate if it starts at an address
 804   // <= the target address, and we know we've found the target address if
 805   // a candidate crosses the target address.
 806   enum State {
 807     START,
 808     LOW_SEQ,  // candidate
 809     HIGH_SEQ
 810   };
 811   State state = START;
 812   reset();
 813
 814   uint64_t prevFile = 0;
 815   uint64_t prevLine = 0;
 816   while (!program.empty()) {
 817     bool seqEnd = !next(program);
 818
 819     if (state == START) {
 820       if (!seqEnd) {
 821         state = address_ <= target ? LOW_SEQ : HIGH_SEQ;
 822       }
 823     }
 824
 825     if (state == LOW_SEQ) {
 826       if (address_ > target) {
 827         // Found it!  Note that ">" is indeed correct (not ">="), as each
 828         // sequence is guaranteed to have one entry past-the-end (emitted by
 829         // DW_LNE_end_sequence)
 830         if (prevFile == 0) {
 831           return false;
 832         }
 833         auto fn = getFileName(prevFile);
 834         file = Path(compilationDirectory_,
 835                     getIncludeDirectory(fn.directoryIndex),
 836                     fn.relativeName);
 837         line = prevLine;
 838         return true;
 839       }
 840       prevFile = file_;
 841       prevLine = line_;
 842     }
 843
 844     if (seqEnd) {
 845       state = START;
 846       reset();
 847     }
 848   }
 849
 850   return false;
 851 }
 852
 853 }  // namespace symbolizer
 854 }  // namespace folly