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