1 //===- LazyRandomTypeCollection.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/CodeView/LazyRandomTypeCollection.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/None.h"
12 #include "llvm/ADT/StringExtras.h"
13 #include "llvm/ADT/StringRef.h"
14 #include "llvm/DebugInfo/CodeView/CodeViewError.h"
15 #include "llvm/DebugInfo/CodeView/RecordName.h"
16 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
17 #include "llvm/Support/BinaryStreamReader.h"
18 #include "llvm/Support/Endian.h"
19 #include "llvm/Support/Error.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <cstdint>
23 #include <iterator>
24
25 using namespace llvm;
26 using namespace llvm::codeview;
27
error(Error && EC)28 static void error(Error &&EC) {
29 assert(!static_cast<bool>(EC));
30 if (EC)
31 consumeError(std::move(EC));
32 }
33
LazyRandomTypeCollection(uint32_t RecordCountHint)34 LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
35 : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
36 PartialOffsetArray()) {}
37
LazyRandomTypeCollection(const CVTypeArray & Types,uint32_t RecordCountHint,PartialOffsetArray PartialOffsets)38 LazyRandomTypeCollection::LazyRandomTypeCollection(
39 const CVTypeArray &Types, uint32_t RecordCountHint,
40 PartialOffsetArray PartialOffsets)
41 : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
42 Records.resize(RecordCountHint);
43 }
44
LazyRandomTypeCollection(ArrayRef<uint8_t> Data,uint32_t RecordCountHint)45 LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
46 uint32_t RecordCountHint)
47 : LazyRandomTypeCollection(RecordCountHint) {
48 }
49
LazyRandomTypeCollection(StringRef Data,uint32_t RecordCountHint)50 LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
51 uint32_t RecordCountHint)
52 : LazyRandomTypeCollection(
53 makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
54 }
55
LazyRandomTypeCollection(const CVTypeArray & Types,uint32_t NumRecords)56 LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
57 uint32_t NumRecords)
58 : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
59
reset(BinaryStreamReader & Reader,uint32_t RecordCountHint)60 void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
61 uint32_t RecordCountHint) {
62 Count = 0;
63 PartialOffsets = PartialOffsetArray();
64
65 error(Reader.readArray(Types, Reader.bytesRemaining()));
66
67 // Clear and then resize, to make sure existing data gets destroyed.
68 Records.clear();
69 Records.resize(RecordCountHint);
70 }
71
reset(StringRef Data,uint32_t RecordCountHint)72 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
73 BinaryStreamReader Reader(Data, support::little);
74 reset(Reader, RecordCountHint);
75 }
76
reset(ArrayRef<uint8_t> Data,uint32_t RecordCountHint)77 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
78 uint32_t RecordCountHint) {
79 BinaryStreamReader Reader(Data, support::little);
80 reset(Reader, RecordCountHint);
81 }
82
getOffsetOfType(TypeIndex Index)83 uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
84 error(ensureTypeExists(Index));
85 assert(contains(Index));
86
87 return Records[Index.toArrayIndex()].Offset;
88 }
89
getType(TypeIndex Index)90 CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
91 assert(!Index.isSimple());
92
93 auto EC = ensureTypeExists(Index);
94 error(std::move(EC));
95 assert(contains(Index));
96
97 return Records[Index.toArrayIndex()].Type;
98 }
99
tryGetType(TypeIndex Index)100 Optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
101 if (Index.isSimple())
102 return None;
103
104 if (auto EC = ensureTypeExists(Index)) {
105 consumeError(std::move(EC));
106 return None;
107 }
108
109 assert(contains(Index));
110 return Records[Index.toArrayIndex()].Type;
111 }
112
getTypeName(TypeIndex Index)113 StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
114 if (Index.isNoneType() || Index.isSimple())
115 return TypeIndex::simpleTypeName(Index);
116
117 // Try to make sure the type exists. Even if it doesn't though, it may be
118 // because we're dumping a symbol stream with no corresponding type stream
119 // present, in which case we still want to be able to print <unknown UDT>
120 // for the type names.
121 if (auto EC = ensureTypeExists(Index)) {
122 consumeError(std::move(EC));
123 return "<unknown UDT>";
124 }
125
126 uint32_t I = Index.toArrayIndex();
127 ensureCapacityFor(Index);
128 if (Records[I].Name.data() == nullptr) {
129 StringRef Result = NameStorage.save(computeTypeName(*this, Index));
130 Records[I].Name = Result;
131 }
132 return Records[I].Name;
133 }
134
contains(TypeIndex Index)135 bool LazyRandomTypeCollection::contains(TypeIndex Index) {
136 if (Index.isSimple() || Index.isNoneType())
137 return false;
138
139 if (Records.size() <= Index.toArrayIndex())
140 return false;
141 if (!Records[Index.toArrayIndex()].Type.valid())
142 return false;
143 return true;
144 }
145
size()146 uint32_t LazyRandomTypeCollection::size() { return Count; }
147
capacity()148 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
149
ensureTypeExists(TypeIndex TI)150 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
151 if (contains(TI))
152 return Error::success();
153
154 return visitRangeForType(TI);
155 }
156
ensureCapacityFor(TypeIndex Index)157 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
158 assert(!Index.isSimple());
159 uint32_t MinSize = Index.toArrayIndex() + 1;
160
161 if (MinSize <= capacity())
162 return;
163
164 uint32_t NewCapacity = MinSize * 3 / 2;
165
166 assert(NewCapacity > capacity());
167 Records.resize(NewCapacity);
168 }
169
visitRangeForType(TypeIndex TI)170 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
171 assert(!TI.isSimple());
172 if (PartialOffsets.empty())
173 return fullScanForType(TI);
174
175 auto Next = llvm::upper_bound(PartialOffsets, TI,
176 [](TypeIndex Value, const TypeIndexOffset &IO) {
177 return Value < IO.Type;
178 });
179
180 assert(Next != PartialOffsets.begin());
181 auto Prev = std::prev(Next);
182
183 TypeIndex TIB = Prev->Type;
184 if (contains(TIB)) {
185 // They've asked us to fetch a type index, but the entry we found in the
186 // partial offsets array has already been visited. Since we visit an entire
187 // block every time, that means this record should have been previously
188 // discovered. Ultimately, this means this is a request for a non-existent
189 // type index.
190 return make_error<CodeViewError>("Invalid type index");
191 }
192
193 TypeIndex TIE;
194 if (Next == PartialOffsets.end()) {
195 TIE = TypeIndex::fromArrayIndex(capacity());
196 } else {
197 TIE = Next->Type;
198 }
199
200 visitRange(TIB, Prev->Offset, TIE);
201 return Error::success();
202 }
203
getFirst()204 Optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
205 TypeIndex TI = TypeIndex::fromArrayIndex(0);
206 if (auto EC = ensureTypeExists(TI)) {
207 consumeError(std::move(EC));
208 return None;
209 }
210 return TI;
211 }
212
getNext(TypeIndex Prev)213 Optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
214 // We can't be sure how long this type stream is, given that the initial count
215 // given to the constructor is just a hint. So just try to make sure the next
216 // record exists, and if anything goes wrong, we must be at the end.
217 if (auto EC = ensureTypeExists(Prev + 1)) {
218 consumeError(std::move(EC));
219 return None;
220 }
221
222 return Prev + 1;
223 }
224
fullScanForType(TypeIndex TI)225 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
226 assert(!TI.isSimple());
227 assert(PartialOffsets.empty());
228
229 TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
230 auto Begin = Types.begin();
231
232 if (Count > 0) {
233 // In the case of type streams which we don't know the number of records of,
234 // it's possible to search for a type index triggering a full scan, but then
235 // later additional records are added since we didn't know how many there
236 // would be until we did a full visitation, then you try to access the new
237 // type triggering another full scan. To avoid this, we assume that if the
238 // database has some records, this must be what's going on. We can also
239 // assume that this index must be larger than the largest type index we've
240 // visited, so we start from there and scan forward.
241 uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
242 CurrentTI = LargestTypeIndex + 1;
243 Begin = Types.at(Offset);
244 ++Begin;
245 }
246
247 auto End = Types.end();
248 while (Begin != End) {
249 ensureCapacityFor(CurrentTI);
250 LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
251 auto Idx = CurrentTI.toArrayIndex();
252 Records[Idx].Type = *Begin;
253 Records[Idx].Offset = Begin.offset();
254 ++Count;
255 ++Begin;
256 ++CurrentTI;
257 }
258 if (CurrentTI <= TI) {
259 return make_error<CodeViewError>("Type Index does not exist!");
260 }
261 return Error::success();
262 }
263
visitRange(TypeIndex Begin,uint32_t BeginOffset,TypeIndex End)264 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
265 TypeIndex End) {
266 auto RI = Types.at(BeginOffset);
267 assert(RI != Types.end());
268
269 ensureCapacityFor(End);
270 while (Begin != End) {
271 LargestTypeIndex = std::max(LargestTypeIndex, Begin);
272 auto Idx = Begin.toArrayIndex();
273 Records[Idx].Type = *RI;
274 Records[Idx].Offset = RI.offset();
275 ++Count;
276 ++Begin;
277 ++RI;
278 }
279 }
280
replaceType(TypeIndex & Index,CVType Data,bool Stabilize)281 bool LazyRandomTypeCollection::replaceType(TypeIndex &Index, CVType Data,
282 bool Stabilize) {
283 llvm_unreachable("Method cannot be called");
284 }
285