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