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