Line data Source code
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 :
29 10138 : static void error(Error &&EC) {
30 : assert(!static_cast<bool>(EC));
31 10138 : if (EC)
32 0 : consumeError(std::move(EC));
33 10138 : }
34 :
35 516 : LazyRandomTypeCollection::LazyRandomTypeCollection(uint32_t RecordCountHint)
36 516 : : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
37 1032 : PartialOffsetArray()) {}
38 :
39 750 : LazyRandomTypeCollection::LazyRandomTypeCollection(
40 : const CVTypeArray &Types, uint32_t RecordCountHint,
41 750 : PartialOffsetArray PartialOffsets)
42 2250 : : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
43 750 : Records.resize(RecordCountHint);
44 750 : }
45 :
46 0 : LazyRandomTypeCollection::LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
47 0 : uint32_t RecordCountHint)
48 0 : : LazyRandomTypeCollection(RecordCountHint) {
49 0 : }
50 :
51 0 : LazyRandomTypeCollection::LazyRandomTypeCollection(StringRef Data,
52 0 : uint32_t RecordCountHint)
53 : : LazyRandomTypeCollection(
54 0 : makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
55 0 : }
56 :
57 3 : LazyRandomTypeCollection::LazyRandomTypeCollection(const CVTypeArray &Types,
58 3 : uint32_t NumRecords)
59 6 : : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
60 :
61 107 : void LazyRandomTypeCollection::reset(BinaryStreamReader &Reader,
62 : uint32_t RecordCountHint) {
63 107 : Count = 0;
64 214 : PartialOffsets = PartialOffsetArray();
65 :
66 107 : error(Reader.readArray(Types, Reader.bytesRemaining()));
67 :
68 : // Clear and then resize, to make sure existing data gets destroyed.
69 107 : Records.clear();
70 107 : Records.resize(RecordCountHint);
71 107 : }
72 :
73 102 : void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
74 102 : BinaryStreamReader Reader(Data, support::little);
75 102 : reset(Reader, RecordCountHint);
76 102 : }
77 :
78 0 : void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
79 : uint32_t RecordCountHint) {
80 0 : BinaryStreamReader Reader(Data, support::little);
81 0 : reset(Reader, RecordCountHint);
82 0 : }
83 :
84 2 : uint32_t LazyRandomTypeCollection::getOffsetOfType(TypeIndex Index) {
85 2 : error(ensureTypeExists(Index));
86 : assert(contains(Index));
87 :
88 4 : return Records[Index.toArrayIndex()].Offset;
89 : }
90 :
91 10029 : CVType LazyRandomTypeCollection::getType(TypeIndex Index) {
92 10029 : auto EC = ensureTypeExists(Index);
93 10029 : error(std::move(EC));
94 : assert(contains(Index));
95 :
96 10029 : return Records[Index.toArrayIndex()].Type;
97 : }
98 :
99 71 : Optional<CVType> LazyRandomTypeCollection::tryGetType(TypeIndex Index) {
100 142 : if (auto EC = ensureTypeExists(Index)) {
101 0 : consumeError(std::move(EC));
102 : return None;
103 : }
104 :
105 : assert(contains(Index));
106 71 : return Records[Index.toArrayIndex()].Type;
107 : }
108 :
109 7706 : StringRef LazyRandomTypeCollection::getTypeName(TypeIndex Index) {
110 7706 : if (Index.isNoneType() || Index.isSimple())
111 750 : 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 13912 : if (auto EC = ensureTypeExists(Index)) {
118 22 : consumeError(std::move(EC));
119 22 : return "<unknown UDT>";
120 : }
121 :
122 : uint32_t I = Index.toArrayIndex();
123 6934 : ensureCapacityFor(Index);
124 13868 : if (Records[I].Name.data() == nullptr) {
125 2988 : StringRef Result = NameStorage.save(computeTypeName(*this, Index));
126 5976 : Records[I].Name = Result;
127 : }
128 13868 : return Records[I].Name;
129 : }
130 :
131 23435 : bool LazyRandomTypeCollection::contains(TypeIndex Index) {
132 23435 : if (Index.isSimple() || Index.isNoneType())
133 0 : return false;
134 :
135 46870 : if (Records.size() <= Index.toArrayIndex())
136 : return false;
137 23415 : if (!Records[Index.toArrayIndex()].Type.valid())
138 365 : return false;
139 : return true;
140 : }
141 :
142 5 : uint32_t LazyRandomTypeCollection::size() { return Count; }
143 :
144 22816 : uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
145 :
146 23313 : Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
147 23313 : if (contains(TI))
148 : return Error::success();
149 :
150 327 : return visitRangeForType(TI);
151 : }
152 :
153 11356 : void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
154 11356 : uint32_t MinSize = Index.toArrayIndex() + 1;
155 :
156 11356 : if (MinSize <= capacity())
157 : return;
158 :
159 68 : uint32_t NewCapacity = MinSize * 3 / 2;
160 :
161 : assert(NewCapacity > capacity());
162 68 : Records.resize(NewCapacity);
163 : }
164 :
165 327 : Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
166 85 : if (PartialOffsets.empty())
167 242 : return fullScanForType(TI);
168 :
169 172 : auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
170 : [](TypeIndex Value, const TypeIndexOffset &IO) {
171 : return Value < IO.Type;
172 85 : });
173 :
174 : assert(Next != PartialOffsets.begin());
175 170 : auto Prev = std::prev(Next);
176 :
177 85 : TypeIndex TIB = Prev->Type;
178 85 : 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 60 : if (Next == PartialOffsets.end()) {
189 48 : TIE = TypeIndex::fromArrayIndex(capacity());
190 : } else {
191 10 : TIE = Next->Type;
192 : }
193 :
194 58 : visitRange(TIB, Prev->Offset, TIE);
195 : return Error::success();
196 : }
197 :
198 137 : Optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
199 137 : TypeIndex TI = TypeIndex::fromArrayIndex(0);
200 274 : if (auto EC = ensureTypeExists(TI)) {
201 2 : consumeError(std::move(EC));
202 : return None;
203 : }
204 : return TI;
205 : }
206 :
207 6118 : 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 12236 : if (auto EC = ensureTypeExists(Prev + 1)) {
212 272 : consumeError(std::move(EC));
213 : return None;
214 : }
215 :
216 11964 : return Prev + 1;
217 : }
218 :
219 242 : Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
220 : assert(PartialOffsets.empty());
221 :
222 242 : TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
223 242 : auto Begin = Types.begin();
224 :
225 242 : 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 258 : uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
235 129 : CurrentTI = LargestTypeIndex + 1;
236 258 : Begin = Types.at(Offset);
237 : ++Begin;
238 : }
239 :
240 : auto End = Types.end();
241 4606 : while (Begin != End) {
242 4364 : ensureCapacityFor(CurrentTI);
243 8728 : LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
244 : auto Idx = CurrentTI.toArrayIndex();
245 4364 : Records[Idx].Type = *Begin;
246 4364 : Records[Idx].Offset = Begin.offset();
247 4364 : ++Count;
248 : ++Begin;
249 : ++CurrentTI;
250 : }
251 242 : if (CurrentTI <= TI) {
252 : return make_error<CodeViewError>("Type Index does not exist!");
253 : }
254 : return Error::success();
255 : }
256 :
257 58 : void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
258 : TypeIndex End) {
259 58 : auto RI = Types.at(BeginOffset);
260 : assert(RI != Types.end());
261 :
262 58 : ensureCapacityFor(End);
263 4041 : while (Begin != End) {
264 7856 : LargestTypeIndex = std::max(LargestTypeIndex, Begin);
265 : auto Idx = Begin.toArrayIndex();
266 3983 : Records[Idx].Type = *RI;
267 3983 : Records[Idx].Offset = RI.offset();
268 3983 : ++Count;
269 : ++Begin;
270 : ++RI;
271 : }
272 58 : }
|
