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