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