Line data    Source code

       1             : //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
       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             : #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
      11             : #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
      12             : 
      13             : #include "llvm/ADT/ArrayRef.h"
      14             : #include "llvm/ADT/Optional.h"
      15             : #include "llvm/ADT/StringRef.h"
      16             : #include "llvm/DebugInfo/CodeView/TypeCollection.h"
      17             : #include "llvm/DebugInfo/CodeView/TypeIndex.h"
      18             : #include "llvm/DebugInfo/CodeView/TypeRecord.h"
      19             : #include "llvm/Support/Allocator.h"
      20             : #include "llvm/Support/BinaryStreamArray.h"
      21             : #include "llvm/Support/Error.h"
      22             : #include "llvm/Support/StringSaver.h"
      23             : #include <cstdint>
      24             : #include <vector>
      25             : 
      26             : namespace llvm {
      27             : namespace codeview {
      28             : 
      29             : /// Provides amortized O(1) random access to a CodeView type stream.
      30             : /// Normally to access a type from a type stream, you must know its byte
      31             : /// offset into the type stream, because type records are variable-lengthed.
      32             : /// However, this is not the way we prefer to access them.  For example, given
      33             : /// a symbol record one of the fields may be the TypeIndex of the symbol's
      34             : /// type record.  Or given a type record such as an array type, there might
      35             : /// be a TypeIndex for the element type.  Sequential access is perfect when
      36             : /// we're just dumping every entry, but it's very poor for real world usage.
      37             : ///
      38             : /// Type streams in PDBs contain an additional field which is a list of pairs
      39             : /// containing indices and their corresponding offsets, roughly every ~8KB of
      40             : /// record data.  This general idea need not be confined to PDBs though.  By
      41             : /// supplying such an array, the producer of a type stream can allow the
      42             : /// consumer much better access time, because the consumer can find the nearest
      43             : /// index in this array, and do a linear scan forward only from there.
      44             : ///
      45             : /// LazyRandomTypeCollection implements this algorithm, but additionally goes
      46             : /// one step further by caching offsets of every record that has been visited at
      47             : /// least once.  This way, even repeated visits of the same record will never
      48             : /// require more than one linear scan.  For a type stream of N elements divided
      49             : /// into M chunks of roughly equal size, this yields a worst case lookup time
      50             : /// of O(N/M) and an amortized time of O(1).
      51             : class LazyRandomTypeCollection : public TypeCollection {
      52             :   using PartialOffsetArray = FixedStreamArray<TypeIndexOffset>;
      53             : 
      54        9151 :   struct CacheEntry {
      55             :     CVType Type;
      56             :     uint32_t Offset;
      57             :     StringRef Name;
      58             :   };
      59             : 
      60             : public:
      61             :   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
      62             :   LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
      63             :   LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
      64             :   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
      65             :                            PartialOffsetArray PartialOffsets);
      66             :   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
      67             : 
      68             :   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
      69             :   void reset(StringRef Data, uint32_t RecordCountHint);
      70             :   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
      71             : 
      72             :   uint32_t getOffsetOfType(TypeIndex Index);
      73             : 
      74             :   Optional<CVType> tryGetType(TypeIndex Index);
      75             : 
      76             :   CVType getType(TypeIndex Index) override;
      77             :   StringRef getTypeName(TypeIndex Index) override;
      78             :   bool contains(TypeIndex Index) override;
      79             :   uint32_t size() override;
      80             :   uint32_t capacity() override;
      81             :   Optional<TypeIndex> getFirst() override;
      82             :   Optional<TypeIndex> getNext(TypeIndex Prev) override;
      83             : 
      84             : private:
      85             :   Error ensureTypeExists(TypeIndex Index);
      86             :   void ensureCapacityFor(TypeIndex Index);
      87             : 
      88             :   Error visitRangeForType(TypeIndex TI);
      89             :   Error fullScanForType(TypeIndex TI);
      90             :   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
      91             : 
      92             :   /// Number of actual records.
      93             :   uint32_t Count = 0;
      94             : 
      95             :   /// The largest type index which we've visited.
      96             :   TypeIndex LargestTypeIndex = TypeIndex::None();
      97             : 
      98             :   BumpPtrAllocator Allocator;
      99             :   StringSaver NameStorage;
     100             : 
     101             :   /// The type array to allow random access visitation of.
     102             :   CVTypeArray Types;
     103             : 
     104             :   std::vector<CacheEntry> Records;
     105             : 
     106             :   /// An array of index offsets for the given type stream, allowing log(N)
     107             :   /// lookups of a type record by index.  Similar to KnownOffsets but only
     108             :   /// contains offsets for some type indices, some of which may not have
     109             :   /// ever been visited.
     110             :   PartialOffsetArray PartialOffsets;
     111             : };
     112             : 
     113             : } // end namespace codeview
     114             : } // end namespace llvm
     115             : 
     116             : #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H