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