folly/experimental/symbolizer/Dwarf.cpp

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