contrib/llvm/lib/DebugInfo/DWARF/DWARFUnitIndex.cpp

   1 //===- DWARFUnitIndex.cpp -------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/ADT/StringRef.h"
  13 #include "llvm/Support/ErrorHandling.h"
  14 #include "llvm/Support/Format.h"
  15 #include "llvm/Support/raw_ostream.h"
  16 #include <cinttypes>
  17 #include <cstdint>
  18
  19 using namespace llvm;
  20
  21 bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
  22                                    uint32_t *OffsetPtr) {
  23   if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))
  24     return false;
  25   Version = IndexData.getU32(OffsetPtr);
  26   NumColumns = IndexData.getU32(OffsetPtr);
  27   NumUnits = IndexData.getU32(OffsetPtr);
  28   NumBuckets = IndexData.getU32(OffsetPtr);
  29   return Version <= 2;
  30 }
  31
  32 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
  33   OS << format("version = %u slots = %u\n\n", Version, NumBuckets);
  34 }
  35
  36 bool DWARFUnitIndex::parse(DataExtractor IndexData) {
  37   bool b = parseImpl(IndexData);
  38   if (!b) {
  39     // Make sure we don't try to dump anything
  40     Header.NumBuckets = 0;
  41     // Release any partially initialized data.
  42     ColumnKinds.reset();
  43     Rows.reset();
  44   }
  45   return b;
  46 }
  47
  48 bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
  49   uint32_t Offset = 0;
  50   if (!Header.parse(IndexData, &Offset))
  51     return false;
  52
  53   if (!IndexData.isValidOffsetForDataOfSize(
  54           Offset, Header.NumBuckets * (8 + 4) +
  55                       (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
  56     return false;
  57
  58   Rows = llvm::make_unique<Entry[]>(Header.NumBuckets);
  59   auto Contribs =
  60       llvm::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);
  61   ColumnKinds = llvm::make_unique<DWARFSectionKind[]>(Header.NumColumns);
  62
  63   // Read Hash Table of Signatures
  64   for (unsigned i = 0; i != Header.NumBuckets; ++i)
  65     Rows[i].Signature = IndexData.getU64(&Offset);
  66
  67   // Read Parallel Table of Indexes
  68   for (unsigned i = 0; i != Header.NumBuckets; ++i) {
  69     auto Index = IndexData.getU32(&Offset);
  70     if (!Index)
  71       continue;
  72     Rows[i].Index = this;
  73     Rows[i].Contributions =
  74         llvm::make_unique<Entry::SectionContribution[]>(Header.NumColumns);
  75     Contribs[Index - 1] = Rows[i].Contributions.get();
  76   }
  77
  78   // Read the Column Headers
  79   for (unsigned i = 0; i != Header.NumColumns; ++i) {
  80     ColumnKinds[i] = static_cast<DWARFSectionKind>(IndexData.getU32(&Offset));
  81     if (ColumnKinds[i] == InfoColumnKind) {
  82       if (InfoColumn != -1)
  83         return false;
  84       InfoColumn = i;
  85     }
  86   }
  87
  88   if (InfoColumn == -1)
  89     return false;
  90
  91   // Read Table of Section Offsets
  92   for (unsigned i = 0; i != Header.NumUnits; ++i) {
  93     auto *Contrib = Contribs[i];
  94     for (unsigned i = 0; i != Header.NumColumns; ++i)
  95       Contrib[i].Offset = IndexData.getU32(&Offset);
  96   }
  97
  98   // Read Table of Section Sizes
  99   for (unsigned i = 0; i != Header.NumUnits; ++i) {
 100     auto *Contrib = Contribs[i];
 101     for (unsigned i = 0; i != Header.NumColumns; ++i)
 102       Contrib[i].Length = IndexData.getU32(&Offset);
 103   }
 104
 105   return true;
 106 }
 107
 108 StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
 109 #define CASE(DS)                                                               \
 110   case DW_SECT_##DS:                                                           \
 111     return #DS;
 112   switch (DS) {
 113     CASE(INFO);
 114     CASE(TYPES);
 115     CASE(ABBREV);
 116     CASE(LINE);
 117     CASE(LOC);
 118     CASE(STR_OFFSETS);
 119     CASE(MACINFO);
 120     CASE(MACRO);
 121   }
 122   llvm_unreachable("unknown DWARFSectionKind");
 123 }
 124
 125 void DWARFUnitIndex::dump(raw_ostream &OS) const {
 126   if (!*this)
 127     return;
 128
 129   Header.dump(OS);
 130   OS << "Index Signature         ";
 131   for (unsigned i = 0; i != Header.NumColumns; ++i)
 132     OS << ' ' << left_justify(getColumnHeader(ColumnKinds[i]), 24);
 133   OS << "\n----- ------------------";
 134   for (unsigned i = 0; i != Header.NumColumns; ++i)
 135     OS << " ------------------------";
 136   OS << '\n';
 137   for (unsigned i = 0; i != Header.NumBuckets; ++i) {
 138     auto &Row = Rows[i];
 139     if (auto *Contribs = Row.Contributions.get()) {
 140       OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
 141       for (unsigned i = 0; i != Header.NumColumns; ++i) {
 142         auto &Contrib = Contribs[i];
 143         OS << format("[0x%08x, 0x%08x) ", Contrib.Offset,
 144                      Contrib.Offset + Contrib.Length);
 145       }
 146       OS << '\n';
 147     }
 148   }
 149 }
 150
 151 const DWARFUnitIndex::Entry::SectionContribution *
 152 DWARFUnitIndex::Entry::getOffset(DWARFSectionKind Sec) const {
 153   uint32_t i = 0;
 154   for (; i != Index->Header.NumColumns; ++i)
 155     if (Index->ColumnKinds[i] == Sec)
 156       return &Contributions[i];
 157   return nullptr;
 158 }
 159
 160 const DWARFUnitIndex::Entry::SectionContribution *
 161 DWARFUnitIndex::Entry::getOffset() const {
 162   return &Contributions[Index->InfoColumn];
 163 }
 164
 165 const DWARFUnitIndex::Entry *
 166 DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
 167   if (OffsetLookup.empty()) {
 168     for (uint32_t i = 0; i != Header.NumBuckets; ++i)
 169       if (Rows[i].Contributions)
 170         OffsetLookup.push_back(&Rows[i]);
 171     llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
 172       return E1->Contributions[InfoColumn].Offset <
 173              E2->Contributions[InfoColumn].Offset;
 174     });
 175   }
 176   auto I =
 177       llvm::upper_bound(OffsetLookup, Offset, [&](uint32_t Offset, Entry *E2) {
 178         return Offset < E2->Contributions[InfoColumn].Offset;
 179       });
 180   if (I == OffsetLookup.begin())
 181     return nullptr;
 182   --I;
 183   const auto *E = *I;
 184   const auto &InfoContrib = E->Contributions[InfoColumn];
 185   if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
 186     return nullptr;
 187   return E;
 188 }
 189
 190 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
 191   uint64_t Mask = Header.NumBuckets - 1;
 192
 193   auto H = S & Mask;
 194   auto HP = ((S >> 32) & Mask) | 1;
 195   while (Rows[H].getSignature() != S && Rows[H].getSignature() != 0)
 196     H = (H + HP) & Mask;
 197
 198   if (Rows[H].getSignature() != S)
 199     return nullptr;
 200
 201   return &Rows[H];
 202 }