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