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
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(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(*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
115void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
116  OS << format("version = %u, units = %u, slots = %u\n\n", Version, NumUnits, NumBuckets);
117}
118
119bool 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
131bool 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
197StringRef 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
215void 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
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(&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
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