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