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/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 }