DebugInfo/CodeView/LazyRandomTypeCollection.h

0001 //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
0010 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
0011
0012 #include "llvm/ADT/ArrayRef.h"
0013 #include "llvm/ADT/StringRef.h"
0014 #include "llvm/DebugInfo/CodeView/TypeCollection.h"
0015 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
0016 #include "llvm/Support/Allocator.h"
0017 #include "llvm/Support/BinaryStreamArray.h"
0018 #include "llvm/Support/Error.h"
0019 #include "llvm/Support/StringSaver.h"
0020 #include <cstdint>
0021 #include <vector>
0022
0023 namespace llvm {
0024 namespace codeview {
0025
0026 /// Provides amortized O(1) random access to a CodeView type stream.
0027 /// Normally to access a type from a type stream, you must know its byte
0028 /// offset into the type stream, because type records are variable-lengthed.
0029 /// However, this is not the way we prefer to access them.  For example, given
0030 /// a symbol record one of the fields may be the TypeIndex of the symbol's
0031 /// type record.  Or given a type record such as an array type, there might
0032 /// be a TypeIndex for the element type.  Sequential access is perfect when
0033 /// we're just dumping every entry, but it's very poor for real world usage.
0034 ///
0035 /// Type streams in PDBs contain an additional field which is a list of pairs
0036 /// containing indices and their corresponding offsets, roughly every ~8KB of
0037 /// record data.  This general idea need not be confined to PDBs though.  By
0038 /// supplying such an array, the producer of a type stream can allow the
0039 /// consumer much better access time, because the consumer can find the nearest
0040 /// index in this array, and do a linear scan forward only from there.
0041 ///
0042 /// LazyRandomTypeCollection implements this algorithm, but additionally goes
0043 /// one step further by caching offsets of every record that has been visited at
0044 /// least once.  This way, even repeated visits of the same record will never
0045 /// require more than one linear scan.  For a type stream of N elements divided
0046 /// into M chunks of roughly equal size, this yields a worst case lookup time
0047 /// of O(N/M) and an amortized time of O(1).
0048 class LazyRandomTypeCollection : public TypeCollection {
0049   using PartialOffsetArray = FixedStreamArray<TypeIndexOffset>;
0050
0051   struct CacheEntry {
0052     CVType Type;
0053     uint32_t Offset;
0054     StringRef Name;
0055   };
0056
0057 public:
0058   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
0059   LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
0060   LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
0061   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
0062                            PartialOffsetArray PartialOffsets);
0063   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
0064
0065   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
0066   void reset(StringRef Data, uint32_t RecordCountHint);
0067   void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
0068
0069   uint32_t getOffsetOfType(TypeIndex Index);
0070
0071   std::optional<CVType> tryGetType(TypeIndex Index);
0072
0073   CVType getType(TypeIndex Index) override;
0074   StringRef getTypeName(TypeIndex Index) override;
0075   bool contains(TypeIndex Index) override;
0076   uint32_t size() override;
0077   uint32_t capacity() override;
0078   std::optional<TypeIndex> getFirst() override;
0079   std::optional<TypeIndex> getNext(TypeIndex Prev) override;
0080   bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
0081
0082 private:
0083   Error ensureTypeExists(TypeIndex Index);
0084   void ensureCapacityFor(TypeIndex Index);
0085
0086   Error visitRangeForType(TypeIndex TI);
0087   Error fullScanForType(TypeIndex TI);
0088   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
0089
0090   /// Number of actual records.
0091   uint32_t Count = 0;
0092
0093   /// The largest type index which we've visited.
0094   TypeIndex LargestTypeIndex = TypeIndex::None();
0095
0096   BumpPtrAllocator Allocator;
0097   StringSaver NameStorage;
0098
0099   /// The type array to allow random access visitation of.
0100   CVTypeArray Types;
0101
0102   std::vector<CacheEntry> Records;
0103
0104   /// An array of index offsets for the given type stream, allowing log(N)
0105   /// lookups of a type record by index.  Similar to KnownOffsets but only
0106   /// contains offsets for some type indices, some of which may not have
0107   /// ever been visited.
0108   PartialOffsetArray PartialOffsets;
0109 };
0110
0111 } // end namespace codeview
0112 } // end namespace llvm
0113
0114 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H