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 <cstdint>
18
19using namespace llvm;
20
21namespace {
22
23enum 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.
37constexpr bool isKnownV5SectionID(uint32_t ID) {
38 return ID >= DW_SECT_INFO && ID <= DW_SECT_RNGLISTS &&
39 ID != DW_SECT_EXT_TYPES;
40}
41
42uint32_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
68DWARFSectionKind llvm::deserializeSectionKind(uint32_t Value,
69 unsigned IndexVersion) {
70 if (IndexVersion == 5)
71 return isKnownV5SectionID(ID: 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
92bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
93 uint64_t *OffsetPtr) {
94 const uint64_t BeginOffset = *OffsetPtr;
95 if (!IndexData.isValidOffsetForDataOfSize(offset: *OffsetPtr, length: 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(offset_ptr: OffsetPtr);
102 if (Version != 2) {
103 *OffsetPtr = BeginOffset;
104 Version = IndexData.getU16(offset_ptr: OffsetPtr);
105 if (Version != 5)
106 return false;
107 *OffsetPtr += 2; // Skip padding.
108 }
109 NumColumns = IndexData.getU32(offset_ptr: OffsetPtr);
110 NumUnits = IndexData.getU32(offset_ptr: OffsetPtr);
111 NumBuckets = IndexData.getU32(offset_ptr: OffsetPtr);
112 return true;
113}
114
115void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
116 OS << formatv(Fmt: "version = {0}, units = {1}, slots = {2}\n\n", Vals: Version,
117 Vals: NumUnits, Vals: NumBuckets);
118}
119
120bool DWARFUnitIndex::parse(DataExtractor IndexData) {
121 bool b = parseImpl(IndexData);
122 if (!b) {
123 // Make sure we don't try to dump anything
124 Header.NumBuckets = 0;
125 // Release any partially initialized data.
126 ColumnKinds.reset();
127 Rows.reset();
128 }
129 return b;
130}
131
132bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
133 uint64_t Offset = 0;
134 if (!Header.parse(IndexData, OffsetPtr: &Offset))
135 return false;
136
137 // Fix InfoColumnKind: in DWARFv5, type units are in .debug_info.dwo.
138 if (Header.Version == 5)
139 InfoColumnKind = DW_SECT_INFO;
140
141 if (!IndexData.isValidOffsetForDataOfSize(
142 offset: Offset, length: Header.NumBuckets * (8 + 4) +
143 (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
144 return false;
145
146 Rows = std::make_unique<Entry[]>(num: Header.NumBuckets);
147 auto Contribs =
148 std::make_unique<Entry::SectionContribution *[]>(num: Header.NumUnits);
149 ColumnKinds = std::make_unique<DWARFSectionKind[]>(num: Header.NumColumns);
150 RawSectionIds = std::make_unique<uint32_t[]>(num: Header.NumColumns);
151
152 // Read Hash Table of Signatures
153 for (unsigned i = 0; i != Header.NumBuckets; ++i)
154 Rows[i].Signature = IndexData.getU64(offset_ptr: &Offset);
155
156 // Read Parallel Table of Indexes
157 for (unsigned i = 0; i != Header.NumBuckets; ++i) {
158 auto Index = IndexData.getU32(offset_ptr: &Offset);
159 if (!Index)
160 continue;
161 Rows[i].Index = this;
162 Rows[i].Contributions =
163 std::make_unique<Entry::SectionContribution[]>(num: Header.NumColumns);
164 Contribs[Index - 1] = Rows[i].Contributions.get();
165 }
166
167 // Read the Column Headers
168 for (unsigned i = 0; i != Header.NumColumns; ++i) {
169 RawSectionIds[i] = IndexData.getU32(offset_ptr: &Offset);
170 ColumnKinds[i] = deserializeSectionKind(Value: RawSectionIds[i], IndexVersion: Header.Version);
171 if (ColumnKinds[i] == InfoColumnKind) {
172 if (InfoColumn != -1)
173 return false;
174 InfoColumn = i;
175 }
176 }
177
178 if (InfoColumn == -1)
179 return false;
180
181 // Read Table of Section Offsets
182 for (unsigned i = 0; i != Header.NumUnits; ++i) {
183 auto *Contrib = Contribs[i];
184 for (unsigned i = 0; i != Header.NumColumns; ++i)
185 Contrib[i].setOffset(IndexData.getU32(offset_ptr: &Offset));
186 }
187
188 // Read Table of Section Sizes
189 for (unsigned i = 0; i != Header.NumUnits; ++i) {
190 auto *Contrib = Contribs[i];
191 for (unsigned i = 0; i != Header.NumColumns; ++i)
192 Contrib[i].setLength(IndexData.getU32(offset_ptr: &Offset));
193 }
194
195 return true;
196}
197
198StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
199 switch (DS) {
200#define HANDLE_DW_SECT(ID, NAME) \
201 case DW_SECT_##NAME: \
202 return #NAME;
203#include "llvm/BinaryFormat/Dwarf.def"
204 case DW_SECT_EXT_TYPES:
205 return "TYPES";
206 case DW_SECT_EXT_LOC:
207 return "LOC";
208 case DW_SECT_EXT_MACINFO:
209 return "MACINFO";
210 case DW_SECT_EXT_unknown:
211 return StringRef();
212 }
213 llvm_unreachable("Unknown DWARFSectionKind");
214}
215
216void DWARFUnitIndex::dump(raw_ostream &OS) const {
217 if (!*this)
218 return;
219
220 Header.dump(OS);
221 OS << "Index Signature ";
222 for (unsigned i = 0; i != Header.NumColumns; ++i) {
223 DWARFSectionKind Kind = ColumnKinds[i];
224 StringRef Name = getColumnHeader(DS: Kind);
225 if (!Name.empty())
226 OS << ' '
227 << left_justify(Str: Name,
228 Width: Kind == DWARFSectionKind::DW_SECT_INFO ? 40 : 24);
229 else
230 OS << formatv(Fmt: " Unknown: {0,-15}", Vals&: RawSectionIds[i]);
231 }
232 OS << "\n----- ------------------";
233 for (unsigned i = 0; i != Header.NumColumns; ++i) {
234 DWARFSectionKind Kind = ColumnKinds[i];
235 if (Kind == DWARFSectionKind::DW_SECT_INFO ||
236 Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)
237 OS << " ----------------------------------------";
238 else
239 OS << " ------------------------";
240 }
241 OS << '\n';
242 for (unsigned i = 0; i != Header.NumBuckets; ++i) {
243 auto &Row = Rows[i];
244 if (auto *Contribs = Row.Contributions.get()) {
245 OS << formatv(Fmt: "{0,5} {1:x16} ", Vals: i + 1, Vals&: Row.Signature);
246 for (unsigned i = 0; i != Header.NumColumns; ++i) {
247 auto &Contrib = Contribs[i];
248 DWARFSectionKind Kind = ColumnKinds[i];
249 if (Kind == DWARFSectionKind::DW_SECT_INFO ||
250 Kind == DWARFSectionKind::DW_SECT_EXT_TYPES)
251 OS << formatv(Fmt: "[{0:x16}, {1:x16}) ", Vals: Contrib.getOffset(),
252 Vals: Contrib.getOffset() + Contrib.getLength());
253 else
254 OS << formatv(Fmt: "[{0:x8}, {1:x8}) ", Vals: Contrib.getOffset32(),
255 Vals: Contrib.getOffset32() + Contrib.getLength32());
256 }
257 OS << '\n';
258 }
259 }
260}
261
262const DWARFUnitIndex::Entry::SectionContribution *
263DWARFUnitIndex::Entry::getContribution(DWARFSectionKind Sec) const {
264 uint32_t i = 0;
265 for (; i != Index->Header.NumColumns; ++i)
266 if (Index->ColumnKinds[i] == Sec)
267 return &Contributions[i];
268 return nullptr;
269}
270
271DWARFUnitIndex::Entry::SectionContribution &
272DWARFUnitIndex::Entry::getContribution() {
273 return Contributions[Index->InfoColumn];
274}
275
276const DWARFUnitIndex::Entry::SectionContribution *
277DWARFUnitIndex::Entry::getContribution() const {
278 return &Contributions[Index->InfoColumn];
279}
280
281const DWARFUnitIndex::Entry *
282DWARFUnitIndex::getFromOffset(uint64_t Offset) const {
283 if (OffsetLookup.empty()) {
284 for (uint32_t i = 0; i != Header.NumBuckets; ++i)
285 if (Rows[i].Contributions)
286 OffsetLookup.push_back(x: &Rows[i]);
287 llvm::sort(C&: OffsetLookup, Comp: [&](Entry *E1, Entry *E2) {
288 return E1->Contributions[InfoColumn].getOffset() <
289 E2->Contributions[InfoColumn].getOffset();
290 });
291 }
292 auto I = partition_point(Range&: OffsetLookup, P: [&](Entry *E2) {
293 return E2->Contributions[InfoColumn].getOffset() <= Offset;
294 });
295 if (I == OffsetLookup.begin())
296 return nullptr;
297 --I;
298 const auto *E = *I;
299 const auto &InfoContrib = E->Contributions[InfoColumn];
300 if ((InfoContrib.getOffset() + InfoContrib.getLength()) <= Offset)
301 return nullptr;
302 return E;
303}
304
305const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
306 uint64_t Mask = Header.NumBuckets - 1;
307
308 auto H = S & Mask;
309 auto HP = ((S >> 32) & Mask) | 1;
310 // The spec says "while 0 is a valid hash value, the row index in a used slot
311 // will always be non-zero". Loop until we find a match or an empty slot.
312 while (Rows[H].getSignature() != S && Rows[H].Index != nullptr)
313 H = (H + HP) & Mask;
314
315 // If the slot is empty, we don't care whether the signature matches (it could
316 // be zero and still match the zeros in the empty slot).
317 if (Rows[H].Index == nullptr)
318 return nullptr;
319
320 return &Rows[H];
321}
322