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