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