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