LCOV - code coverage report
Current view: top level - lib/DebugInfo/CodeView - LazyRandomTypeCollection.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 104 118 88.1 %
Date: 2018-02-22 16:16:46 Functions: 20 23 87.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13