• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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