folly/experimental/symbolizer/Dwarf.h

   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 // DWARF record parser
  18
  19 #ifndef FOLLY_EXPERIMENTAL_SYMBOLIZER_DWARF_H_
  20 #define FOLLY_EXPERIMENTAL_SYMBOLIZER_DWARF_H_
  21
  22 #include <boost/variant.hpp>
  23
  24 #include "folly/experimental/symbolizer/Elf.h"
  25 #include "folly/Range.h"
  26
  27 namespace facebook {
  28 namespace symbolizer {
  29
  30 /**
  31  * DWARF record parser.
  32  *
  33  * We only implement enough DWARF functionality to convert from PC address
  34  * to file and line number information.
  35  *
  36  * This means (although they're not part of the public API of this class), we
  37  * can parse Debug Information Entries (DIEs), abbreviations, attributes (of
  38  * all forms), and we can interpret bytecode for the line number VM.
  39  *
  40  * We can interpret DWARF records of version 2, 3, or 4, although we don't
  41  * actually support many of the version 4 features (such as VLIW, multiple
  42  * operations per instruction)
  43  *
  44  * Note that the DWARF record parser does not allocate heap memory at all
  45  * during normal operation (it might in the error case, as throwing exceptions
  46  * uses the heap).  This is on purpose: you can use the parser from
  47  * memory-constrained situations (such as an exception handler for
  48  * std::out_of_memory)  If it weren't for this requirement, some things would
  49  * be much simpler: the Path class would be unnecessary and would be replaced
  50  * with a std::string; the list of file names in the line number VM would be
  51  * kept as a vector of strings instead of re-executing the program to look for
  52  * DW_LNE_define_file instructions, etc.
  53  */
  54 class Dwarf {
  55   // Note that Dwarf uses (and returns) StringPiece a lot.
  56   // The StringPieces point within sections in the ELF file, and so will
  57   // be live for as long as the passed-in ElfFile is live.
  58  public:
  59   /** Create a DWARF parser around an ELF file. */
  60   explicit Dwarf(const ElfFile* elf);
  61
  62   /**
  63    * Represent a file path a s collection of three parts (base directory,
  64    * subdirectory, and file).
  65    */
  66   class Path {
  67    public:
  68     Path() { }
  69
  70     Path(folly::StringPiece baseDir, folly::StringPiece subDir,
  71          folly::StringPiece file);
  72
  73     folly::StringPiece baseDir() const { return baseDir_; };
  74     folly::StringPiece subDir() const { return subDir_; }
  75     folly::StringPiece file() const { return file_; }
  76
  77     size_t size() const;
  78
  79     /**
  80      * Copy the Path to a buffer of size bufSize.
  81      *
  82      * toBuffer behaves like snprintf: It will always null-terminate the
  83      * buffer (so it will copy at most bufSize-1 bytes), and it will return
  84      * the number of bytes that would have been written if there had been
  85      * enough room, so, if toBuffer returns a value >= bufSize, the output
  86      * was truncated.
  87      */
  88     size_t toBuffer(char* buf, size_t bufSize) const;
  89
  90     void toString(std::string& dest) const;
  91     std::string toString() const {
  92       std::string s;
  93       toString(s);
  94       return s;
  95     }
  96
  97     // TODO(tudorb): Implement operator==, operator!=; not as easy as it
  98     // seems as the same path can be represented in multiple ways
  99    private:
 100     folly::StringPiece baseDir_;
 101     folly::StringPiece subDir_;
 102     folly::StringPiece file_;
 103   };
 104
 105   struct LocationInfo {
 106     LocationInfo() : hasMainFile(false), hasFileAndLine(false), line(0) { }
 107
 108     bool hasMainFile;
 109     Path mainFile;
 110
 111     bool hasFileAndLine;
 112     Path file;
 113     uint64_t line;
 114   };
 115
 116   /** Find the file and line number information corresponding to address */
 117   bool findAddress(uintptr_t address, LocationInfo& info) const;
 118
 119  private:
 120   void init();
 121
 122   const ElfFile* elf_;
 123
 124   // DWARF section made up of chunks, each prefixed with a length header.
 125   // The length indicates whether the chunk is DWARF-32 or DWARF-64, which
 126   // guides interpretation of "section offset" records.
 127   // (yes, DWARF-32 and DWARF-64 sections may coexist in the same file)
 128   class Section {
 129    public:
 130     Section() : is64Bit_(false) { }
 131
 132     explicit Section(folly::StringPiece d);
 133
 134     // Return next chunk, if any; the 4- or 12-byte length was already
 135     // parsed and isn't part of the chunk.
 136     bool next(folly::StringPiece& chunk);
 137
 138     // Is the current chunk 64 bit?
 139     bool is64Bit() const { return is64Bit_; }
 140
 141    private:
 142     // Yes, 32- and 64- bit sections may coexist.  Yikes!
 143     bool is64Bit_;
 144     folly::StringPiece data_;
 145   };
 146
 147   // Abbreviation for a Debugging Information Entry.
 148   struct DIEAbbreviation {
 149     uint64_t code;
 150     uint64_t tag;
 151     bool hasChildren;
 152
 153     struct Attribute {
 154       uint64_t name;
 155       uint64_t form;
 156     };
 157
 158     folly::StringPiece attributes;
 159   };
 160
 161   // Interpreter for the line number bytecode VM
 162   class LineNumberVM {
 163    public:
 164     LineNumberVM(folly::StringPiece data,
 165                  folly::StringPiece compilationDirectory);
 166
 167     bool findAddress(uintptr_t address, Path& file, uint64_t& line);
 168
 169    private:
 170     void init();
 171     void reset();
 172
 173     // Execute until we commit one new row to the line number matrix
 174     bool next(folly::StringPiece& program);
 175     enum StepResult {
 176       CONTINUE,  // Continue feeding opcodes
 177       COMMIT,    // Commit new <address, file, line> tuple
 178       END,       // End of sequence
 179     };
 180     // Execute one opcode
 181     StepResult step(folly::StringPiece& program);
 182
 183     struct FileName {
 184       folly::StringPiece relativeName;
 185       // 0 = current compilation directory
 186       // otherwise, 1-based index in the list of include directories
 187       uint64_t directoryIndex;
 188     };
 189     // Read one FileName object, advance sp
 190     static bool readFileName(folly::StringPiece& sp, FileName& fn);
 191
 192     // Get file name at given index; may be in the initial table
 193     // (fileNames_) or defined using DW_LNE_define_file (and we reexecute
 194     // enough of the program to find it, if so)
 195     FileName getFileName(uint64_t index) const;
 196
 197     // Get include directory at given index
 198     folly::StringPiece getIncludeDirectory(uint64_t index) const;
 199
 200     // Execute opcodes until finding a DW_LNE_define_file and return true;
 201     // return file at the end.
 202     bool nextDefineFile(folly::StringPiece& program, FileName& fn) const;
 203
 204     // Initialization
 205     bool is64Bit_;
 206     folly::StringPiece data_;
 207     folly::StringPiece compilationDirectory_;
 208
 209     // Header
 210     uint16_t version_;
 211     uint8_t minLength_;
 212     bool defaultIsStmt_;
 213     int8_t lineBase_;
 214     uint8_t lineRange_;
 215     uint8_t opcodeBase_;
 216     const uint8_t* standardOpcodeLengths_;
 217
 218     folly::StringPiece includeDirectories_;
 219     size_t includeDirectoryCount_;
 220
 221     folly::StringPiece fileNames_;
 222     size_t fileNameCount_;
 223
 224     // State machine registers
 225     uint64_t address_;
 226     uint64_t file_;
 227     uint64_t line_;
 228     uint64_t column_;
 229     bool isStmt_;
 230     bool basicBlock_;
 231     bool endSequence_;
 232     bool prologueEnd_;
 233     bool epilogueBegin_;
 234     uint64_t isa_;
 235     uint64_t discriminator_;
 236   };
 237
 238   // Read an abbreviation from a StringPiece, return true if at end; advance sp
 239   static bool readAbbreviation(folly::StringPiece& sp, DIEAbbreviation& abbr);
 240
 241   // Get abbreviation corresponding to a code, in the chunk starting at
 242   // offset in the .debug_abbrev section
 243   DIEAbbreviation getAbbreviation(uint64_t code, uint64_t offset) const;
 244
 245   // Read one attribute <name, form> pair, advance sp; returns <0, 0> at end.
 246   static DIEAbbreviation::Attribute readAttribute(folly::StringPiece& sp);
 247
 248   // Read one attribute value, advance sp
 249   typedef boost::variant<uint64_t, folly::StringPiece> AttributeValue;
 250   AttributeValue readAttributeValue(
 251       folly::StringPiece& sp,
 252       uint64_t form,
 253       bool is64Bit) const;
 254
 255   // Get an ELF section by name, return true if found
 256   bool getSection(const char* name, folly::StringPiece* section) const;
 257
 258   // Get a string from the .debug_str section
 259   folly::StringPiece getStringFromStringSection(uint64_t offset) const;
 260
 261   folly::StringPiece info_;       // .debug_info
 262   folly::StringPiece abbrev_;     // .debug_abbrev
 263   folly::StringPiece aranges_;    // .debug_aranges
 264   folly::StringPiece line_;       // .debug_line
 265   folly::StringPiece strings_;    // .debug_str
 266 };
 267
 268 inline std::ostream& operator<<(std::ostream& out, const Dwarf::Path& path) {
 269   return out << path.toString();
 270 }
 271
 272 }  // namespace symbolizer
 273 }  // namespace facebook
 274
 275 #endif /* FOLLY_EXPERIMENTAL_SYMBOLIZER_DWARF_H_ */
 276