folly/experimental/symbolizer/Dwarf.cpp

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