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