Home | History | Annotate | Line # | Download | only in DWARF 
      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 }
    301