llvm/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/DataExtractor.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 namespace {
  22
  23 enum class DWARFSectionKindV2 {
  24   DW_SECT_INFO = 1,
  25   DW_SECT_TYPES = 2,
  26   DW_SECT_ABBREV = 3,
  27   DW_SECT_LINE = 4,
  28   DW_SECT_LOC = 5,
  29   DW_SECT_STR_OFFSETS = 6,
  30   DW_SECT_MACINFO = 7,
  31   DW_SECT_MACRO = 8,
  32 };
  33
  34 } // namespace
  35
  36 // Return true if the section identifier is defined in the DWARFv5 standard.
  37 constexpr bool isKnownV5SectionID(uint32_t ID) {
  38   return ID >= DW_SECT_INFO && ID <= DW_SECT_RNGLISTS &&
  39          ID != DW_SECT_EXT_TYPES;
  40 }
  41
  42 uint32_t llvm::serializeSectionKind(DWARFSectionKind Kind,
  43                                     unsigned IndexVersion) {
  44   if (IndexVersion == 5) {
  45     assert(isKnownV5SectionID(Kind));
  46     return static_cast<uint32_t>(Kind);
  47   }
  48   assert(IndexVersion == 2);
  49   switch (Kind) {
  50 #define CASE(S,T) \
  51   case DW_SECT_##S: \
  52     return static_cast<uint32_t>(DWARFSectionKindV2::DW_SECT_##T)
  53   CASE(INFO, INFO);
  54   CASE(EXT_TYPES, TYPES);
  55   CASE(ABBREV, ABBREV);
  56   CASE(LINE, LINE);
  57   CASE(EXT_LOC, LOC);
  58   CASE(STR_OFFSETS, STR_OFFSETS);
  59   CASE(EXT_MACINFO, MACINFO);
  60   CASE(MACRO, MACRO);
  61 #undef CASE
  62   default:
  63     // All other section kinds have no corresponding values in v2 indexes.
  64     llvm_unreachable("Invalid DWARFSectionKind");
  65   }
  66 }
  67
  68 DWARFSectionKind llvm::deserializeSectionKind(uint32_t Value,
  69                                               unsigned IndexVersion) {
  70   if (IndexVersion == 5)
  71     return isKnownV5SectionID(Value)
  72                ? static_cast<DWARFSectionKind>(Value)
  73                : DW_SECT_EXT_unknown;
  74   assert(IndexVersion == 2);
  75   switch (static_cast<DWARFSectionKindV2>(Value)) {
  76 #define CASE(S,T) \
  77   case DWARFSectionKindV2::DW_SECT_##S: \
  78     return DW_SECT_##T
  79   CASE(INFO, INFO);
  80   CASE(TYPES, EXT_TYPES);
  81   CASE(ABBREV, ABBREV);
  82   CASE(LINE, LINE);
  83   CASE(LOC, EXT_LOC);
  84   CASE(STR_OFFSETS, STR_OFFSETS);
  85   CASE(MACINFO, EXT_MACINFO);
  86   CASE(MACRO, MACRO);
  87 #undef CASE
  88   }
  89   return DW_SECT_EXT_unknown;
  90 }
  91
  92 bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
  93                                    uint64_t *OffsetPtr) {
  94   const uint64_t BeginOffset = *OffsetPtr;
  95   if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))
  96     return false;
  97   // GCC Debug Fission defines the version as an unsigned 32-bit field
  98   // with value of 2, https://gcc.gnu.org/wiki/DebugFissionDWP.
  99   // DWARFv5 defines the same space as an uhalf version field with value of 5
 100   // and a 2 bytes long padding, see Section 7.3.5.3.
 101   Version = IndexData.getU32(OffsetPtr);
 102   if (Version != 2) {
 103     *OffsetPtr = BeginOffset;
 104     Version = IndexData.getU16(OffsetPtr);
 105     if (Version != 5)
 106       return false;
 107     *OffsetPtr += 2; // Skip padding.
 108   }
 109   NumColumns = IndexData.getU32(OffsetPtr);
 110   NumUnits = IndexData.getU32(OffsetPtr);
 111   NumBuckets = IndexData.getU32(OffsetPtr);
 112   return true;
 113 }
 114
 115 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
 116   OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets);
 117 }
 118
 119 bool DWARFUnitIndex::parse(DataExtractor IndexData) {
 120   bool b = parseImpl(IndexData);
 121   if (!b) {
 122     // Make sure we don't try to dump anything
 123     Header.NumBuckets = 0;
 124     // Release any partially initialized data.
 125     ColumnKinds.reset();
 126     Rows.reset();
 127   }
 128   return b;
 129 }
 130
 131 bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
 132   uint64_t Offset = 0;
 133   if (!Header.parse(IndexData, &Offset))
 134     return false;
 135
 136   // Fix InfoColumnKind: in DWARFv5, type units are in .debug_info.dwo.
 137   if (Header.Version == 5)
 138     InfoColumnKind = DW_SECT_INFO;
 139
 140   if (!IndexData.isValidOffsetForDataOfSize(
 141           Offset, Header.NumBuckets * (8 + 4) +
 142                       (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
 143     return false;
 144
 145   Rows = std::make_unique<Entry[]>(Header.NumBuckets);
 146   auto Contribs =
 147       std::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);
 148   ColumnKinds = std::make_unique<DWARFSectionKind[]>(Header.NumColumns);
 149   RawSectionIds = std::make_unique<uint32_t[]>(Header.NumColumns);
 150
 151   // Read Hash Table of Signatures
 152   for (unsigned i = 0; i != Header.NumBuckets; ++i)
 153     Rows[i].Signature = IndexData.getU64(&Offset);
 154
 155   // Read Parallel Table of Indexes
 156   for (unsigned i = 0; i != Header.NumBuckets; ++i) {
 157     auto Index = IndexData.getU32(&Offset);
 158     if (!Index)
 159       continue;
 160     Rows[i].Index = this;
 161     Rows[i].Contributions =
 162         std::make_unique<Entry::SectionContribution[]>(Header.NumColumns);
 163     Contribs[Index - 1] = Rows[i].Contributions.get();
 164   }
 165
 166   // Read the Column Headers
 167   for (unsigned i = 0; i != Header.NumColumns; ++i) {
 168     RawSectionIds[i] = IndexData.getU32(&Offset);
 169     ColumnKinds[i] = deserializeSectionKind(RawSectionIds[i], Header.Version);
 170     if (ColumnKinds[i] == InfoColumnKind) {
 171       if (InfoColumn != -1)
 172         return false;
 173       InfoColumn = i;
 174     }
 175   }
 176
 177   if (InfoColumn == -1)
 178     return false;
 179
 180   // Read Table of Section Offsets
 181   for (unsigned i = 0; i != Header.NumUnits; ++i) {
 182     auto *Contrib = Contribs[i];
 183     for (unsigned i = 0; i != Header.NumColumns; ++i)
 184       Contrib[i].setOffset(IndexData.getU32(&Offset));
 185   }
 186
 187   // Read Table of Section Sizes
 188   for (unsigned i = 0; i != Header.NumUnits; ++i) {
 189     auto *Contrib = Contribs[i];
 190     for (unsigned i = 0; i != Header.NumColumns; ++i)
 191       Contrib[i].setLength(IndexData.getU32(&Offset));
 192   }
 193
 194   return true;
 195 }
 196
 197 StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
 198   switch (DS) {
 199 #define HANDLE_DW_SECT(ID, NAME)                                               \
 200   case DW_SECT_##NAME:                                                         \
 201     return #NAME;
 202 #include "llvm/BinaryFormat/Dwarf.def"
 203   case DW_SECT_EXT_TYPES:
 204     return "TYPES";
 205   case DW_SECT_EXT_LOC:
 206     return "LOC";
 207   case DW_SECT_EXT_MACINFO:
 208     return "MACINFO";
 209   case DW_SECT_EXT_unknown:
 210     return StringRef();
 211   }
 212   llvm_unreachable("Unknown DWARFSectionKind");
 213 }
 214
 215 void DWARFUnitIndex::dump(raw_ostream &OS) const {
 216   if (!*this)
 217     return;
 218
 219   Header.dump(OS);
 220   OS << "Index Signature         ";
 221   for (unsigned i = 0; i != Header.NumColumns; ++i) {
 222     DWARFSectionKind Kind = ColumnKinds[i];
 223     StringRef Name = getColumnHeader(Kind);
 224     if (!Name.empty())
 225       OS << ' '
 226          << left_justify(Name,
 227                          Kind == DWARFSectionKind::DW_SECT_INFO ? 40 : 24);
 228     else
 229       OS << format(" Unknown: %-15" PRIu32, RawSectionIds[i]);
 230   }
 231   OS << "\n----- ------------------";
 232   for (unsigned i = 0; i != Header.NumColumns; ++i) {
 233     DWARFSectionKind Kind = ColumnKinds[i];
 234     if (Kind == DWARFSectionKind::DW_SECT_INFO ||
 235         Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)
 236       OS << " ----------------------------------------";
 237     else
 238       OS << " ------------------------";
 239   }
 240   OS << '\n';
 241   for (unsigned i = 0; i != Header.NumBuckets; ++i) {
 242     auto &Row = Rows[i];
 243     if (auto *Contribs = Row.Contributions.get()) {
 244       OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
 245       for (unsigned i = 0; i != Header.NumColumns; ++i) {
 246         auto &Contrib = Contribs[i];
 247         DWARFSectionKind Kind = ColumnKinds[i];
 248         if (Kind == DWARFSectionKind::DW_SECT_INFO ||
 249             Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)
 250           OS << format("[0x%016" PRIx64 ", 0x%016" PRIx64 ") ",
 251                        Contrib.getOffset(),
 252                        Contrib.getOffset() + Contrib.getLength());
 253         else
 254           OS << format("[0x%08" PRIx32 ", 0x%08" PRIx32 ") ",
 255                        Contrib.getOffset32(),
 256                        Contrib.getOffset32() + Contrib.getLength32());
 257       }
 258       OS << '\n';
 259     }
 260   }
 261 }
 262
 263 const DWARFUnitIndex::Entry::SectionContribution *
 264 DWARFUnitIndex::Entry::getContribution(DWARFSectionKind Sec) const {
 265   uint32_t i = 0;
 266   for (; i != Index->Header.NumColumns; ++i)
 267     if (Index->ColumnKinds[i] == Sec)
 268       return &Contributions[i];
 269   return nullptr;
 270 }
 271
 272 DWARFUnitIndex::Entry::SectionContribution &
 273 DWARFUnitIndex::Entry::getContribution() {
 274   return Contributions[Index->InfoColumn];
 275 }
 276
 277 const DWARFUnitIndex::Entry::SectionContribution *
 278 DWARFUnitIndex::Entry::getContribution() const {
 279   return &Contributions[Index->InfoColumn];
 280 }
 281
 282 const DWARFUnitIndex::Entry *
 283 DWARFUnitIndex::getFromOffset(uint64_t Offset) const {
 284   if (OffsetLookup.empty()) {
 285     for (uint32_t i = 0; i != Header.NumBuckets; ++i)
 286       if (Rows[i].Contributions)
 287         OffsetLookup.push_back(&Rows[i]);
 288     llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
 289       return E1->Contributions[InfoColumn].getOffset() <
 290              E2->Contributions[InfoColumn].getOffset();
 291     });
 292   }
 293   auto I = partition_point(OffsetLookup, [&](Entry *E2) {
 294     return E2->Contributions[InfoColumn].getOffset() <= Offset;
 295   });
 296   if (I == OffsetLookup.begin())
 297     return nullptr;
 298   --I;
 299   const auto *E = *I;
 300   const auto &InfoContrib = E->Contributions[InfoColumn];
 301   if ((InfoContrib.getOffset() + InfoContrib.getLength()) <= Offset)
 302     return nullptr;
 303   return E;
 304 }
 305
 306 const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
 307   uint64_t Mask = Header.NumBuckets - 1;
 308
 309   auto H = S & Mask;
 310   auto HP = ((S >> 32) & Mask) | 1;
 311   // The spec says "while 0 is a valid hash value, the row index in a used slot
 312   // will always be non-zero". Loop until we find a match or an empty slot.
 313   while (Rows[H].getSignature() != S && Rows[H].Index != nullptr)
 314     H = (H + HP) & Mask;
 315
 316   // If the slot is empty, we don't care whether the signature matches (it could
 317   // be zero and still match the zeros in the empty slot).
 318   if (Rows[H].Index == nullptr)
 319     return nullptr;
 320
 321   return &Rows[H];
 322 }