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 }
323