folly/experimental/symbolizer/Dwarf.cpp

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