hphp/tools/debug-parser/dwarfstate.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #pragma once
  18
  19 #include "hphp/util/assertions.h"
  20
  21 #include <folly/Demangle.h>
  22 #include <folly/Format.h>
  23 #include <folly/Memory.h>
  24 #include <folly/ScopeGuard.h>
  25 #include <folly/String.h>
  26 #include <folly/container/F14Map.h>
  27 #include <folly/portability/Unistd.h>
  28 #include <folly/experimental/symbolizer/Elf.h>
  29
  30 #include <atomic>
  31 #include <functional>
  32 #include <stdexcept>
  33 #include <string>
  34 #include <thread>
  35 #include <vector>
  36
  37 #include <dwarf.h>
  38
  39 namespace debug_parser {
  40
  41 ////////////////////////////////////////////////////////////////////////////////
  42
  43 /*
  44  * Thrown if there's an issue while parsing dwarf debug information.
  45  */
  46 struct DwarfStateException: std::runtime_error {
  47   using std::runtime_error::runtime_error;
  48 };
  49
  50 struct GlobalOff {
  51   GlobalOff(uint64_t off, bool isInfo) : m_value{off * 2 + (isInfo ? 1 : 0)} {
  52     assert(offset() == off);
  53   }
  54   GlobalOff(int64_t off, bool isInfo) :
  55       GlobalOff{ static_cast<uint64_t>(off), isInfo } {}
  56
  57   static GlobalOff fromRaw(uint64_t raw) {
  58     return GlobalOff{raw};
  59   }
  60   uint64_t offset() const { return m_value >> 1; }
  61   bool isInfo() const { return m_value & 1; }
  62   uint64_t raw() const { return m_value; }
  63
  64   friend GlobalOff operator+(GlobalOff a, size_t b) {
  65     return {a.offset() + b, a.isInfo()};
  66   }
  67   friend bool operator<(GlobalOff a, GlobalOff b) {
  68     // we want all the debug_types to sort before all the debug_infos
  69     if ((a.m_value ^ b.m_value) & 1) {
  70       return (a.m_value & 1);
  71     }
  72     return a.m_value < b.m_value;
  73   }
  74   friend bool operator==(GlobalOff a, GlobalOff b) {
  75     return a.raw() == b.raw();
  76   }
  77   friend bool operator>(GlobalOff a, GlobalOff b) { return b < a; }
  78   friend bool operator<=(GlobalOff a, GlobalOff b) { return !(a > b); }
  79   friend bool operator>=(GlobalOff a, GlobalOff b) { return !(a < b); }
  80   friend bool operator!=(GlobalOff a, GlobalOff b) { return !(a == b); }
  81   struct Hash {
  82     size_t hash(GlobalOff a) const {
  83       return std::hash<uint64_t>{}(a.raw());
  84     }
  85     bool equal(GlobalOff a, GlobalOff b) const {
  86       return a == b;
  87     }
  88     size_t operator()(GlobalOff a) const { return hash(a); }
  89   };
  90 private:
  91   explicit GlobalOff(uint64_t raw) : m_value{raw} {}
  92   uint64_t m_value;
  93 };
  94
  95 struct AbbrevMap {
  96   void build(folly::StringPiece debug_abbrev);
  97
  98   static uint64_t readOne(folly::StringPiece& section,
  99                           uint64_t &tag, bool &hasChildren,
 100                           folly::StringPiece& attrs);
 101
 102   std::vector<uint64_t> abbrev_vec;
 103   // map from offset to abbrev_vec index
 104   folly::F14FastMap<uint64_t, uint64_t> abbrev_map;
 105 };
 106
 107 struct DwarfState {
 108   using Sig8Map = folly::F14FastMap<uint64_t, GlobalOff>;
 109
 110   explicit DwarfState(std::string filename);
 111   DwarfState(const DwarfState&) = delete;
 112   DwarfState(DwarfState&&) = delete;
 113   ~DwarfState();
 114
 115   DwarfState& operator=(const DwarfState&) = delete;
 116   DwarfState& operator=(DwarfState&&) = delete;
 117
 118   /*
 119    * A top level chunk in the .debug_info or .debug_types section.
 120    *
 121    * Contains a compilation-unit, or type-unit, and all its children.
 122    *
 123    * section + offset + size points at the start of the next context.
 124    */
 125   struct Context {
 126     const char* section;
 127     uint64_t offset;
 128     uint64_t size;
 129     bool is64Bit;
 130     bool isInfo;
 131     uint8_t version;
 132     uint8_t addrSize;
 133     uint64_t abbrevOffset;
 134     uint64_t typeSignature;
 135     uint64_t typeOffset;
 136     uint64_t firstDie;
 137   };
 138
 139   struct Die {
 140     const Context* context;
 141     // offset within context->section
 142     uint64_t offset;
 143     uint64_t code;
 144     uint64_t tag;
 145     // convenience copy from the context.
 146     bool is64Bit;
 147     bool hasChildren;
 148     // offset from start to first attribute
 149     uint8_t attrOffset;
 150     // if we know where the next sibling is (eg via DW_AT_sibling), and
 151     // it fits in uint32_t, the delta we need to add to offset to get
 152     // there; otherwise zero.
 153     uint32_t siblingDelta;
 154     // if we know where the next die is, and it fits in uint32_t, this
 155     // is the delta we need to add to offset to get there; otherwise zero.
 156     // if there are no children, this will be the same as sibling.
 157     uint32_t nextDieDelta;
 158     folly::StringPiece attributes;
 159   };
 160
 161   struct AttributeSpec {
 162     uint64_t name{};
 163     uint64_t form{};
 164
 165     explicit operator bool() const {
 166       return name || form;
 167     }
 168   };
 169
 170   struct Attribute : AttributeSpec {
 171     Attribute(AttributeSpec spec, Die* die, folly::StringPiece sp) :
 172         AttributeSpec{spec}, die{die}, attrValue{sp} {}
 173     Die* die;
 174     folly::StringPiece attrValue;
 175   };
 176
 177   using Dwarf_Half = uint16_t;
 178   struct Dwarf_Loc {
 179     Dwarf_Half lr_atom;
 180     uint64_t lr_number;
 181     uint64_t lr_number2;
 182     uint64_t lr_offset;
 183   };
 184   struct Dwarf_Ranges {
 185     static auto constexpr kSelection = uintptr_t(-1);
 186
 187     uintptr_t dwr_addr1;
 188     uintptr_t dwr_addr2;
 189   };
 190
 191   Context getContextAtOffset(GlobalOff off) const;
 192   Die getDieAtOffset(const Context* context, GlobalOff off) const;
 193   Die getNextSibling(Die* die) const;
 194   Dwarf_Half getTag(Die* die) const;
 195   std::string tagToString(Dwarf_Half tag) const;
 196   std::string getDIEName(Die* die) const;
 197   GlobalOff getDIEOffset(Die* die) const;
 198   Dwarf_Half getAttributeType(Attribute* attr) const;
 199   std::string attributeTypeToString(Dwarf_Half type) const;
 200   Dwarf_Half getAttributeForm(Attribute* attr) const;
 201   std::string attributeFormToString(Dwarf_Half form) const;
 202   std::string opToString(Dwarf_Half form) const;
 203   std::string getAttributeValueString(Attribute* attr) const;
 204   folly::StringPiece getAttributeValueStringPiece(Attribute* attr) const;
 205   bool getAttributeValueFlag(Attribute* attr) const;
 206   uint64_t getAttributeValueUData(Attribute* attr) const;
 207   int64_t getAttributeValueSData(Attribute* attr) const;
 208   uintptr_t getAttributeValueAddr(Attribute* attr) const;
 209   GlobalOff getAttributeValueRef(Attribute* attr) const;
 210   uint64_t getAttributeValueSig8(Attribute* attr) const;
 211   std::vector<Dwarf_Loc> getAttributeValueExprLoc(Attribute* attr) const;
 212   std::vector<Dwarf_Ranges> getRanges(Attribute* attr) const;
 213
 214   // Get a string from the .debug_str section
 215   folly::StringPiece getStringFromStringSection(uint64_t offset) const;
 216
 217   template <typename F> void forEachContext(F&& f, bool isInfo) const;
 218   template <typename F> void forEachContextParallel(F&& f, bool isInfo,
 219                                                     int num_threads) const;
 220   template <typename F> void forEachChild(Die* die, F&& f) const;
 221   template <typename F> void forEachAttribute(Die* die, F&& f) const;
 222   template <typename F> void forEachCompilationUnit(F&& f) const;
 223   template <typename F> void forEachTopLevelUnit(F&& f, bool isInfo) const;
 224   template <typename F> void forEachTopLevelUnitParallel(F&& f, bool isInfo,
 225                                                          int num_threads) const;
 226   template <typename F> auto onDIEAtOffset(GlobalOff offset, F&& f) const ->
 227     decltype(f(std::declval<Die*>()));
 228   template <typename F> auto onDIEAtContextOffset(
 229       GlobalOff contextOff, F&& f) const ->
 230     decltype(f(std::declval<Die*>()));
 231
 232   static AttributeSpec readAttributeSpec(folly::StringPiece&);
 233   static Attribute readAttribute(Die* die, AttributeSpec spec,
 234                                  folly::StringPiece& sp);
 235
 236   // Read (bitwise) one object of type T
 237   template <class T>
 238   static typename std::enable_if<std::is_pod<T>::value, T>::type read(
 239       folly::StringPiece& sp) {
 240     assert(sp.size() >= sizeof(T));
 241     T x;
 242     memcpy(&x, sp.data(), sizeof(T));
 243     sp.advance(sizeof(T));
 244     return x;
 245   }
 246 private:
 247   AbbrevMap abbrevMap;
 248   Sig8Map sig8_map;
 249   std::vector<uint64_t> cuContextOffsets;
 250   std::vector<uint64_t> tuContextOffsets;
 251
 252   folly::symbolizer::ElfFile elf;
 253   folly::StringPiece debug_info;
 254   folly::StringPiece debug_types;
 255   folly::StringPiece debug_abbrev;
 256   folly::StringPiece debug_str;
 257   folly::StringPiece debug_ranges;
 258
 259   // Read a value of "section offset" type, which may be 4 or 8 bytes
 260   static uint64_t readOffset(folly::StringPiece& sp, bool is64Bit) {
 261     return is64Bit ? read<uint64_t>(sp) : read<uint32_t>(sp);
 262   }
 263
 264   static void updateDelta(uint32_t& delta, uint64_t value) {
 265     if (value != static_cast<uint32_t>(value)) {
 266       assertx(!delta);
 267       return;
 268     }
 269     if (!delta) {
 270       delta = value;
 271       return;
 272     }
 273     assertx(delta == value);
 274   }
 275
 276   void init();
 277 };
 278
 279 using Dwarf_Die = DwarfState::Die*;
 280 using Dwarf_Context = DwarfState::Context*;
 281 using Dwarf_Attribute = DwarfState::Attribute*;
 282
 283 /*
 284  * Iterate over all children of this DIE, calling the given callable for
 285  * each. Iteration is stopped early if any of the calls return false.
 286  */
 287 template <typename F>
 288 void DwarfState::forEachChild(Dwarf_Die die, F&& f) const {
 289   if (!die->hasChildren) return;
 290
 291   if (!die->nextDieDelta) {
 292     forEachAttribute(die, [] (Dwarf_Attribute) { return true; });
 293     assert(die->nextDieDelta);
 294   }
 295
 296   auto sibling = getDieAtOffset(
 297       die->context, { die->offset + die->nextDieDelta, die->context->isInfo }
 298   );
 299   while (sibling.code) {
 300     if (!f(&sibling)) return;
 301     sibling = getNextSibling(&sibling);
 302   }
 303
 304   // sibling is a dummy die whose offset is to the code 0 marking the
 305   // end of the children. Need to add one to get the offset of the
 306   // next die
 307   updateDelta(die->siblingDelta, sibling.offset + 1 - die->offset);
 308 }
 309
 310 /*
 311  * Iterate over all attributes of the given DIE, calling the given callable for
 312  * each. Iteration is stopped early if any of the calls return false.
 313  */
 314 template <typename F>
 315 void DwarfState::forEachAttribute(Dwarf_Die die, F&& f) const {
 316   auto attrs = die->attributes;
 317   auto values = folly::StringPiece {
 318     die->context->section + die->offset + die->attrOffset,
 319     die->context->section + die->context->offset + die->context->size
 320   };
 321   while (auto const aspec = readAttributeSpec(attrs)) {
 322     auto attr = readAttribute(die, aspec, values);
 323     if (!die->siblingDelta && attr.name == DW_AT_sibling) {
 324       updateDelta(die->siblingDelta,
 325                   getAttributeValueRef(&attr).offset() - die->offset);
 326       if (!die->hasChildren) {
 327         assert(!die->nextDieDelta || die->nextDieDelta == die->siblingDelta);
 328         die->nextDieDelta = die->siblingDelta;
 329       }
 330     }
 331     if (!f(&attr)) return;
 332   }
 333
 334   updateDelta(die->nextDieDelta,
 335               values.data() - die->context->section - die->offset);
 336   if (!die->hasChildren) {
 337     assertx(!die->siblingDelta || die->siblingDelta == die->nextDieDelta);
 338     die->siblingDelta = die->nextDieDelta;
 339   }
 340 }
 341
 342 /*
 343  * Iterate over all the contexts in the file, calling the given
 344  * callable for each.
 345  */
 346 template <typename F>
 347 void DwarfState::forEachContext(F&& f, bool isInfo) const {
 348   auto const section = isInfo ? debug_info : debug_types;
 349   auto sp = section;
 350   while (!sp.empty()) {
 351     auto context = getContextAtOffset(
 352         { sp.data() - section.data(), isInfo }
 353     );
 354     sp.advance(context.size);
 355     f(&context);
 356   }
 357 }
 358
 359 /*
 360  * Iterate over all the contexts in the file, calling the given
 361  * callable for each in parellel. The function f must be thread safe.
 362  */
 363 template <typename F>
 364 void DwarfState::forEachContextParallel(F&& f, bool isInfo,
 365                                         int num_threads) const {
 366   if (num_threads <= 1) return forEachContext(f, isInfo);
 367
 368   std::vector<GlobalOff> offsets;
 369
 370   forEachContext([&] (Dwarf_Context context) {
 371     offsets.push_back({ context->offset, isInfo });
 372   }, isInfo);
 373
 374   std::atomic<size_t> index{0};
 375
 376   std::vector<std::thread> workers;
 377   for (auto worker = size_t{0}; worker < num_threads; ++worker) {
 378     workers.push_back(std::thread([&] {
 379       while (true) {
 380         const size_t kChunkSize = 50;
 381         auto start = index.fetch_add(kChunkSize, std::memory_order_relaxed);
 382         if (start >= offsets.size()) break;
 383         for (auto i = start;
 384              i < start + kChunkSize && i < offsets.size();
 385              ++i) {
 386           auto context = getContextAtOffset(offsets[i]);
 387           f(&context);
 388         }
 389       }
 390     }));
 391   }
 392   for (auto& t : workers) t.join();
 393 }
 394
 395 /*
 396  * Iterate over all the compilation-units in the file, calling the given
 397  * callable for each.
 398  */
 399 template <typename F>
 400 void DwarfState::forEachTopLevelUnitParallel(F&& f, bool isInfo,
 401                                              int num_threads) const {
 402   forEachContextParallel(
 403     [&] (Dwarf_Context context) {
 404       auto die = getDieAtOffset(context, { context->firstDie, isInfo });
 405       f(&die);
 406     },
 407     isInfo,
 408     num_threads
 409   );
 410 }
 411
 412 template <typename F>
 413 void DwarfState::forEachTopLevelUnit(F&& f, bool isInfo) const {
 414   forEachTopLevelUnitParallel(f, isInfo, 1);
 415 }
 416
 417 template <typename F> void DwarfState::forEachCompilationUnit(F&& f) const {
 418   forEachTopLevelUnit(std::forward<F>(f), true);
 419 }
 420
 421 /*
 422  * Load the DIE at the given offset, and call the given callable on it,
 423  * returning whatever the callable returns.
 424  */
 425 template <typename F> auto DwarfState::onDIEAtOffset(GlobalOff offset,
 426                                                      F&& f) const ->
 427   decltype(f(std::declval<Dwarf_Die>())) {
 428
 429   auto const& contextOffsets = offset.isInfo() ?
 430     cuContextOffsets : tuContextOffsets;
 431   auto it = std::upper_bound(
 432       contextOffsets.begin(), contextOffsets.end(), offset.offset());
 433   assertx(it != contextOffsets.begin());
 434   auto const contextOffset = *--it;
 435   auto const context = getContextAtOffset({ contextOffset, offset.isInfo() });
 436
 437   auto die = getDieAtOffset(&context, offset);
 438   return f(&die);
 439 }
 440
 441 template <typename F>
 442 auto DwarfState::onDIEAtContextOffset(GlobalOff offset, F&& f) const ->
 443   decltype(f(std::declval<Dwarf_Die>())) {
 444
 445   auto context = getContextAtOffset(offset);
 446   auto die = getDieAtOffset(&context, { context.firstDie, context.isInfo });
 447   return f(&die);
 448 }
 449
 450 ////////////////////////////////////////////////////////////////////////////////
 451
 452 }
 453
 454 ////////////////////////////////////////////////////////////////////////////////
 455
 456 namespace folly {
 457 template<> class FormatValue<debug_parser::GlobalOff> {
 458  public:
 459   explicit FormatValue(debug_parser::GlobalOff val) : m_val(val) {}
 460
 461   template<typename Callback>
 462   void format(FormatArg& arg, Callback& cb) const {
 463     format_value::formatString(folly::sformat("{}:{}",
 464                                               m_val.offset(),
 465                                               m_val.isInfo() ? 1 : 0),
 466                                arg, cb);
 467   }
 468
 469  private:
 470   debug_parser::GlobalOff m_val;
 471 };
 472 }
 473
 474 namespace std {
 475 template<>
 476 struct hash<debug_parser::GlobalOff> : debug_parser::GlobalOff::Hash {};
 477 }
 478
 479 ////////////////////////////////////////////////////////////////////////////////