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