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
18using namespace llvm;
19
20bool DWARFUnitIndex::Header::parse(DataExtractor IndexData,
21                                   uint64_t *OffsetPtr) {
22  if (!IndexData.isValidOffsetForDataOfSize(*OffsetPtr, 16))
23    return false;
24  Version = IndexData.getU32(OffsetPtr);
25  NumColumns = IndexData.getU32(OffsetPtr);
26  NumUnits = IndexData.getU32(OffsetPtr);
27  NumBuckets = IndexData.getU32(OffsetPtr);
28  return Version <= 2;
29}
30
31void DWARFUnitIndex::Header::dump(raw_ostream &OS) const {
32  OS << format("version = %u slots = %u\n\n", Version, NumBuckets);
33}
34
35bool DWARFUnitIndex::parse(DataExtractor IndexData) {
36  bool b = parseImpl(IndexData);
37  if (!b) {
38    // Make sure we don't try to dump anything
39    Header.NumBuckets = 0;
40    // Release any partially initialized data.
41    ColumnKinds.reset();
42    Rows.reset();
43  }
44  return b;
45}
46
47bool DWARFUnitIndex::parseImpl(DataExtractor IndexData) {
48  uint64_t Offset = 0;
49  if (!Header.parse(IndexData, &Offset))
50    return false;
51
52  if (!IndexData.isValidOffsetForDataOfSize(
53          Offset, Header.NumBuckets * (8 + 4) +
54                      (2 * Header.NumUnits + 1) * 4 * Header.NumColumns))
55    return false;
56
57  Rows = std::make_unique<Entry[]>(Header.NumBuckets);
58  auto Contribs =
59      std::make_unique<Entry::SectionContribution *[]>(Header.NumUnits);
60  ColumnKinds = std::make_unique<DWARFSectionKind[]>(Header.NumColumns);
61
62  // Read Hash Table of Signatures
63  for (unsigned i = 0; i != Header.NumBuckets; ++i)
64    Rows[i].Signature = IndexData.getU64(&Offset);
65
66  // Read Parallel Table of Indexes
67  for (unsigned i = 0; i != Header.NumBuckets; ++i) {
68    auto Index = IndexData.getU32(&Offset);
69    if (!Index)
70      continue;
71    Rows[i].Index = this;
72    Rows[i].Contributions =
73        std::make_unique<Entry::SectionContribution[]>(Header.NumColumns);
74    Contribs[Index - 1] = Rows[i].Contributions.get();
75  }
76
77  // Read the Column Headers
78  for (unsigned i = 0; i != Header.NumColumns; ++i) {
79    ColumnKinds[i] = static_cast<DWARFSectionKind>(IndexData.getU32(&Offset));
80    if (ColumnKinds[i] == InfoColumnKind) {
81      if (InfoColumn != -1)
82        return false;
83      InfoColumn = i;
84    }
85  }
86
87  if (InfoColumn == -1)
88    return false;
89
90  // Read Table of Section Offsets
91  for (unsigned i = 0; i != Header.NumUnits; ++i) {
92    auto *Contrib = Contribs[i];
93    for (unsigned i = 0; i != Header.NumColumns; ++i)
94      Contrib[i].Offset = IndexData.getU32(&Offset);
95  }
96
97  // Read Table of Section Sizes
98  for (unsigned i = 0; i != Header.NumUnits; ++i) {
99    auto *Contrib = Contribs[i];
100    for (unsigned i = 0; i != Header.NumColumns; ++i)
101      Contrib[i].Length = IndexData.getU32(&Offset);
102  }
103
104  return true;
105}
106
107StringRef DWARFUnitIndex::getColumnHeader(DWARFSectionKind DS) {
108#define CASE(DS)                                                               \
109  case DW_SECT_##DS:                                                           \
110    return #DS;
111  switch (DS) {
112    CASE(INFO);
113    CASE(TYPES);
114    CASE(ABBREV);
115    CASE(LINE);
116    CASE(LOC);
117    CASE(STR_OFFSETS);
118    CASE(MACINFO);
119    CASE(MACRO);
120  }
121  llvm_unreachable("unknown DWARFSectionKind");
122}
123
124void DWARFUnitIndex::dump(raw_ostream &OS) const {
125  if (!*this)
126    return;
127
128  Header.dump(OS);
129  OS << "Index Signature         ";
130  for (unsigned i = 0; i != Header.NumColumns; ++i)
131    OS << ' ' << left_justify(getColumnHeader(ColumnKinds[i]), 24);
132  OS << "\n----- ------------------";
133  for (unsigned i = 0; i != Header.NumColumns; ++i)
134    OS << " ------------------------";
135  OS << '\n';
136  for (unsigned i = 0; i != Header.NumBuckets; ++i) {
137    auto &Row = Rows[i];
138    if (auto *Contribs = Row.Contributions.get()) {
139      OS << format("%5u 0x%016" PRIx64 " ", i + 1, Row.Signature);
140      for (unsigned i = 0; i != Header.NumColumns; ++i) {
141        auto &Contrib = Contribs[i];
142        OS << format("[0x%08x, 0x%08x) ", Contrib.Offset,
143                     Contrib.Offset + Contrib.Length);
144      }
145      OS << '\n';
146    }
147  }
148}
149
150const DWARFUnitIndex::Entry::SectionContribution *
151DWARFUnitIndex::Entry::getOffset(DWARFSectionKind Sec) const {
152  uint32_t i = 0;
153  for (; i != Index->Header.NumColumns; ++i)
154    if (Index->ColumnKinds[i] == Sec)
155      return &Contributions[i];
156  return nullptr;
157}
158
159const DWARFUnitIndex::Entry::SectionContribution *
160DWARFUnitIndex::Entry::getOffset() const {
161  return &Contributions[Index->InfoColumn];
162}
163
164const DWARFUnitIndex::Entry *
165DWARFUnitIndex::getFromOffset(uint32_t Offset) const {
166  if (OffsetLookup.empty()) {
167    for (uint32_t i = 0; i != Header.NumBuckets; ++i)
168      if (Rows[i].Contributions)
169        OffsetLookup.push_back(&Rows[i]);
170    llvm::sort(OffsetLookup, [&](Entry *E1, Entry *E2) {
171      return E1->Contributions[InfoColumn].Offset <
172             E2->Contributions[InfoColumn].Offset;
173    });
174  }
175  auto I = partition_point(OffsetLookup, [&](Entry *E2) {
176    return E2->Contributions[InfoColumn].Offset <= Offset;
177  });
178  if (I == OffsetLookup.begin())
179    return nullptr;
180  --I;
181  const auto *E = *I;
182  const auto &InfoContrib = E->Contributions[InfoColumn];
183  if ((InfoContrib.Offset + InfoContrib.Length) <= Offset)
184    return nullptr;
185  return E;
186}
187
188const DWARFUnitIndex::Entry *DWARFUnitIndex::getFromHash(uint64_t S) const {
189  uint64_t Mask = Header.NumBuckets - 1;
190
191  auto H = S & Mask;
192  auto HP = ((S >> 32) & Mask) | 1;
193  while (Rows[H].getSignature() != S && Rows[H].getSignature() != 0)
194    H = (H + HP) & Mask;
195
196  if (Rows[H].getSignature() != S)
197    return nullptr;
198
199  return &Rows[H];
200}
201