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 | |
23 | namespace llvm { |
24 | namespace 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). |
48 | class LazyRandomTypeCollection : public TypeCollection { |
49 | using PartialOffsetArray = FixedStreamArray<TypeIndexOffset>; |
50 | |
51 | struct CacheEntry { |
52 | CVType Type; |
53 | uint32_t Offset; |
54 | StringRef Name; |
55 | }; |
56 | |
57 | public: |
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 | |
82 | private: |
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 | |