lib/DebugInfo/DWARF/DWARFUnitIndex.cpp

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