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