include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

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