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.
isKnownV5SectionID(uint32_t ID)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
serializeSectionKind(DWARFSectionKind Kind,unsigned IndexVersion)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
deserializeSectionKind(uint32_t Value,unsigned IndexVersion)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
parse(DataExtractor IndexData,uint64_t * OffsetPtr)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
dump(raw_ostream & OS) const114 void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
115 OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets);
116 }
117
parse(DataExtractor IndexData)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
parseImpl(DataExtractor IndexData)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
getColumnHeader(DWARFSectionKind DS)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
dump(raw_ostream & OS) const214 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 *
getContribution(DWARFSectionKind Sec) const247 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 *
getContribution() const256 DWARFUnitIndex::Entry::getContribution() const {
257 return &Contributions[Index->InfoColumn];
258 }
259
260 const DWARFUnitIndex::Entry *
getFromOffset(uint32_t Offset) const261 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
getFromHash(uint64_t S) const284 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