llvm/lib/DebugInfo/CodeView/LazyRandomTypeCollection.cpp

   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, llvm::endianness::little);
  73   reset(Reader, RecordCountHint);
  74 }
  75
  76 void LazyRandomTypeCollection::reset(ArrayRef<uint8_t> Data,
  77                                      uint32_t RecordCountHint) {
  78   BinaryStreamReader Reader(Data, llvm::endianness::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 }