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