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