folly/experimental/symbolizer/Dwarf.cpp

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