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 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 117