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