1 | //===- llvm/unittest/DebugInfo/CodeView/RandomAccessVisitorTest.cpp -------===// |
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 | #include "llvm/DebugInfo/CodeView/AppendingTypeTableBuilder.h" |
10 | #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h" |
11 | #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h" |
12 | #include "llvm/DebugInfo/CodeView/TypeRecord.h" |
13 | #include "llvm/DebugInfo/CodeView/TypeRecordMapping.h" |
14 | #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h" |
15 | #include "llvm/Support/Allocator.h" |
16 | #include "llvm/Support/BinaryByteStream.h" |
17 | #include "llvm/Support/BinaryItemStream.h" |
18 | #include "llvm/Support/Error.h" |
19 | #include "llvm/Testing/Support/Error.h" |
20 | |
21 | #include "gtest/gtest.h" |
22 | |
23 | using namespace llvm; |
24 | using namespace llvm::codeview; |
25 | |
26 | namespace llvm { |
27 | namespace codeview { |
28 | inline bool operator==(const ArrayRecord &R1, const ArrayRecord &R2) { |
29 | if (R1.ElementType != R2.ElementType) |
30 | return false; |
31 | if (R1.IndexType != R2.IndexType) |
32 | return false; |
33 | if (R1.Name != R2.Name) |
34 | return false; |
35 | if (R1.Size != R2.Size) |
36 | return false; |
37 | return true; |
38 | } |
39 | inline bool operator!=(const ArrayRecord &R1, const ArrayRecord &R2) { |
40 | return !(R1 == R2); |
41 | } |
42 | |
43 | inline bool operator==(const CVType &R1, const CVType &R2) { |
44 | if (R1.RecordData != R2.RecordData) |
45 | return false; |
46 | return true; |
47 | } |
48 | inline bool operator!=(const CVType &R1, const CVType &R2) { |
49 | return !(R1 == R2); |
50 | } |
51 | } |
52 | } |
53 | |
54 | namespace llvm { |
55 | template <> struct BinaryItemTraits<CVType> { |
56 | static size_t length(const CVType &Item) { return Item.length(); } |
57 | static ArrayRef<uint8_t> bytes(const CVType &Item) { return Item.data(); } |
58 | }; |
59 | } |
60 | |
61 | namespace { |
62 | |
63 | class MockCallbacks : public TypeVisitorCallbacks { |
64 | public: |
65 | Error visitTypeBegin(CVType &CVR, TypeIndex Index) override { |
66 | Indices.push_back(x: Index); |
67 | return Error::success(); |
68 | } |
69 | Error visitKnownRecord(CVType &CVR, ArrayRecord &AR) override { |
70 | VisitedRecords.push_back(x: AR); |
71 | RawRecords.push_back(x: CVR); |
72 | return Error::success(); |
73 | } |
74 | |
75 | uint32_t count() const { |
76 | assert(Indices.size() == RawRecords.size()); |
77 | assert(Indices.size() == VisitedRecords.size()); |
78 | return Indices.size(); |
79 | } |
80 | std::vector<TypeIndex> Indices; |
81 | std::vector<CVType> RawRecords; |
82 | std::vector<ArrayRecord> VisitedRecords; |
83 | }; |
84 | |
85 | class RandomAccessVisitorTest : public testing::Test { |
86 | public: |
87 | RandomAccessVisitorTest() {} |
88 | |
89 | static void SetUpTestCase() { |
90 | GlobalState = std::make_unique<GlobalTestState>(); |
91 | |
92 | AppendingTypeTableBuilder Builder(GlobalState->Allocator); |
93 | |
94 | uint32_t Offset = 0; |
95 | for (int I = 0; I < 11; ++I) { |
96 | ArrayRecord AR(TypeRecordKind::Array); |
97 | AR.ElementType = TypeIndex::Int32(); |
98 | AR.IndexType = TypeIndex::UInt32(); |
99 | AR.Size = I; |
100 | std::string Name; |
101 | raw_string_ostream Stream(Name); |
102 | Stream << "Array [" << I << "]" ; |
103 | AR.Name = GlobalState->Strings.save(S: Stream.str()); |
104 | GlobalState->Records.push_back(x: AR); |
105 | GlobalState->Indices.push_back(x: Builder.writeLeafType(Record&: AR)); |
106 | |
107 | CVType Type(Builder.records().back()); |
108 | GlobalState->TypeVector.push_back(x: Type); |
109 | |
110 | GlobalState->AllOffsets.push_back( |
111 | x: {.Type: GlobalState->Indices.back(), .Offset: ulittle32_t(Offset)}); |
112 | Offset += Type.length(); |
113 | } |
114 | |
115 | GlobalState->ItemStream.setItems(GlobalState->TypeVector); |
116 | GlobalState->TypeArray = VarStreamArray<CVType>(GlobalState->ItemStream); |
117 | } |
118 | |
119 | static void TearDownTestCase() { GlobalState.reset(); } |
120 | |
121 | void SetUp() override { |
122 | TestState = std::make_unique<PerTestState>(); |
123 | } |
124 | |
125 | void TearDown() override { TestState.reset(); } |
126 | |
127 | protected: |
128 | bool ValidateDatabaseRecord(LazyRandomTypeCollection &Types, uint32_t Index) { |
129 | TypeIndex TI = TypeIndex::fromArrayIndex(Index); |
130 | if (!Types.contains(Index: TI)) |
131 | return false; |
132 | if (GlobalState->TypeVector[Index] != Types.getType(Index: TI)) |
133 | return false; |
134 | return true; |
135 | } |
136 | |
137 | bool ValidateVisitedRecord(uint32_t VisitationOrder, |
138 | uint32_t GlobalArrayIndex) { |
139 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: GlobalArrayIndex); |
140 | if (TI != TestState->Callbacks.Indices[VisitationOrder]) |
141 | return false; |
142 | |
143 | if (GlobalState->TypeVector[TI.toArrayIndex()] != |
144 | TestState->Callbacks.RawRecords[VisitationOrder]) |
145 | return false; |
146 | |
147 | if (GlobalState->Records[TI.toArrayIndex()] != |
148 | TestState->Callbacks.VisitedRecords[VisitationOrder]) |
149 | return false; |
150 | |
151 | return true; |
152 | } |
153 | |
154 | struct GlobalTestState { |
155 | GlobalTestState() |
156 | : Strings(Allocator), ItemStream(llvm::endianness::little) {} |
157 | |
158 | BumpPtrAllocator Allocator; |
159 | StringSaver Strings; |
160 | |
161 | std::vector<ArrayRecord> Records; |
162 | std::vector<TypeIndex> Indices; |
163 | std::vector<TypeIndexOffset> AllOffsets; |
164 | std::vector<CVType> TypeVector; |
165 | BinaryItemStream<CVType> ItemStream; |
166 | VarStreamArray<CVType> TypeArray; |
167 | |
168 | MutableBinaryByteStream Stream; |
169 | }; |
170 | |
171 | struct PerTestState { |
172 | FixedStreamArray<TypeIndexOffset> Offsets; |
173 | |
174 | MockCallbacks Callbacks; |
175 | }; |
176 | |
177 | FixedStreamArray<TypeIndexOffset> |
178 | createPartialOffsets(MutableBinaryByteStream &Storage, |
179 | std::initializer_list<uint32_t> Indices) { |
180 | |
181 | uint32_t Count = Indices.size(); |
182 | uint32_t Size = Count * sizeof(TypeIndexOffset); |
183 | uint8_t *Buffer = GlobalState->Allocator.Allocate<uint8_t>(Num: Size); |
184 | MutableArrayRef<uint8_t> Bytes(Buffer, Size); |
185 | Storage = MutableBinaryByteStream(Bytes, llvm::endianness::little); |
186 | BinaryStreamWriter Writer(Storage); |
187 | for (const auto I : Indices) |
188 | consumeError(Err: Writer.writeObject(Obj: GlobalState->AllOffsets[I])); |
189 | |
190 | BinaryStreamReader Reader(Storage); |
191 | FixedStreamArray<TypeIndexOffset> Result; |
192 | consumeError(Err: Reader.readArray(Array&: Result, NumItems: Count)); |
193 | return Result; |
194 | } |
195 | |
196 | static std::unique_ptr<GlobalTestState> GlobalState; |
197 | std::unique_ptr<PerTestState> TestState; |
198 | }; |
199 | |
200 | std::unique_ptr<RandomAccessVisitorTest::GlobalTestState> |
201 | RandomAccessVisitorTest::GlobalState; |
202 | } |
203 | |
204 | TEST_F(RandomAccessVisitorTest, MultipleVisits) { |
205 | TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {0, 8}); |
206 | LazyRandomTypeCollection Types(GlobalState->TypeArray, |
207 | GlobalState->TypeVector.size(), |
208 | TestState->Offsets); |
209 | |
210 | std::vector<uint32_t> IndicesToVisit = {5, 5, 5}; |
211 | |
212 | for (uint32_t I : IndicesToVisit) { |
213 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: I); |
214 | CVType T = Types.getType(Index: TI); |
215 | EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks), |
216 | Succeeded()); |
217 | } |
218 | |
219 | // [0,8) should be present |
220 | EXPECT_EQ(8u, Types.size()); |
221 | for (uint32_t I = 0; I < 8; ++I) |
222 | EXPECT_TRUE(ValidateDatabaseRecord(Types, I)); |
223 | |
224 | // 5, 5, 5 |
225 | EXPECT_EQ(3u, TestState->Callbacks.count()); |
226 | for (const auto &I : enumerate(First&: IndicesToVisit)) |
227 | EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value())); |
228 | } |
229 | |
230 | TEST_F(RandomAccessVisitorTest, DescendingWithinChunk) { |
231 | // Visit multiple items from the same "chunk" in reverse order. In this |
232 | // example, it's 7 then 4 then 2. At the end, all records from 0 to 7 should |
233 | // be known by the database, but only 2, 4, and 7 should have been visited. |
234 | TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {0, 8}); |
235 | |
236 | std::vector<uint32_t> IndicesToVisit = {7, 4, 2}; |
237 | |
238 | LazyRandomTypeCollection Types(GlobalState->TypeArray, |
239 | GlobalState->TypeVector.size(), |
240 | TestState->Offsets); |
241 | for (uint32_t I : IndicesToVisit) { |
242 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: I); |
243 | CVType T = Types.getType(Index: TI); |
244 | EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks), |
245 | Succeeded()); |
246 | } |
247 | |
248 | // [0, 7] |
249 | EXPECT_EQ(8u, Types.size()); |
250 | for (uint32_t I = 0; I < 8; ++I) |
251 | EXPECT_TRUE(ValidateDatabaseRecord(Types, I)); |
252 | |
253 | // 2, 4, 7 |
254 | EXPECT_EQ(3u, TestState->Callbacks.count()); |
255 | for (const auto &I : enumerate(First&: IndicesToVisit)) |
256 | EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value())); |
257 | } |
258 | |
259 | TEST_F(RandomAccessVisitorTest, AscendingWithinChunk) { |
260 | // * Visit multiple items from the same chunk in ascending order, ensuring |
261 | // that intermediate items are not visited. In the below example, it's |
262 | // 5 -> 6 -> 7 which come from the [4,8) chunk. |
263 | TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {0, 8}); |
264 | |
265 | std::vector<uint32_t> IndicesToVisit = {2, 4, 7}; |
266 | |
267 | LazyRandomTypeCollection Types(GlobalState->TypeArray, |
268 | GlobalState->TypeVector.size(), |
269 | TestState->Offsets); |
270 | for (uint32_t I : IndicesToVisit) { |
271 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: I); |
272 | CVType T = Types.getType(Index: TI); |
273 | EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks), |
274 | Succeeded()); |
275 | } |
276 | |
277 | // [0, 7] |
278 | EXPECT_EQ(8u, Types.size()); |
279 | for (uint32_t I = 0; I < 8; ++I) |
280 | EXPECT_TRUE(ValidateDatabaseRecord(Types, I)); |
281 | |
282 | // 2, 4, 7 |
283 | EXPECT_EQ(3u, TestState->Callbacks.count()); |
284 | for (const auto &I : enumerate(First&: IndicesToVisit)) |
285 | EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value())); |
286 | } |
287 | |
288 | TEST_F(RandomAccessVisitorTest, StopPrematurelyInChunk) { |
289 | // * Don't visit the last item in one chunk, ensuring that visitation stops |
290 | // at the record you specify, and the chunk is only partially visited. |
291 | // In the below example, this is tested by visiting 0 and 1 but not 2, |
292 | // all from the [0,3) chunk. |
293 | TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {0, 8}); |
294 | |
295 | std::vector<uint32_t> IndicesToVisit = {0, 1, 2}; |
296 | |
297 | LazyRandomTypeCollection Types(GlobalState->TypeArray, |
298 | GlobalState->TypeVector.size(), |
299 | TestState->Offsets); |
300 | |
301 | for (uint32_t I : IndicesToVisit) { |
302 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: I); |
303 | CVType T = Types.getType(Index: TI); |
304 | EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks), |
305 | Succeeded()); |
306 | } |
307 | |
308 | // [0, 8) should be visited. |
309 | EXPECT_EQ(8u, Types.size()); |
310 | for (uint32_t I = 0; I < 8; ++I) |
311 | EXPECT_TRUE(ValidateDatabaseRecord(Types, I)); |
312 | |
313 | // [0, 2] |
314 | EXPECT_EQ(3u, TestState->Callbacks.count()); |
315 | for (const auto &I : enumerate(First&: IndicesToVisit)) |
316 | EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value())); |
317 | } |
318 | |
319 | TEST_F(RandomAccessVisitorTest, InnerChunk) { |
320 | // Test that when a request comes from a chunk in the middle of the partial |
321 | // offsets array, that items from surrounding chunks are not visited or |
322 | // added to the database. |
323 | TestState->Offsets = createPartialOffsets(Storage&: GlobalState->Stream, Indices: {0, 4, 9}); |
324 | |
325 | std::vector<uint32_t> IndicesToVisit = {5, 7}; |
326 | |
327 | LazyRandomTypeCollection Types(GlobalState->TypeArray, |
328 | GlobalState->TypeVector.size(), |
329 | TestState->Offsets); |
330 | |
331 | for (uint32_t I : IndicesToVisit) { |
332 | TypeIndex TI = TypeIndex::fromArrayIndex(Index: I); |
333 | CVType T = Types.getType(Index: TI); |
334 | EXPECT_THAT_ERROR(codeview::visitTypeRecord(T, TI, TestState->Callbacks), |
335 | Succeeded()); |
336 | } |
337 | |
338 | // [4, 9) |
339 | EXPECT_EQ(5u, Types.size()); |
340 | for (uint32_t I = 4; I < 9; ++I) |
341 | EXPECT_TRUE(ValidateDatabaseRecord(Types, I)); |
342 | |
343 | // 5, 7 |
344 | EXPECT_EQ(2u, TestState->Callbacks.count()); |
345 | for (const auto &I : enumerate(First&: IndicesToVisit)) |
346 | EXPECT_TRUE(ValidateVisitedRecord(I.index(), I.value())); |
347 | } |
348 | |
349 | TEST_F(RandomAccessVisitorTest, CrossChunkName) { |
350 | AppendingTypeTableBuilder Builder(GlobalState->Allocator); |
351 | |
352 | // TypeIndex 0 |
353 | ClassRecord Class(TypeRecordKind::Class); |
354 | Class.Name = "FooClass" ; |
355 | Class.Options = ClassOptions::None; |
356 | Class.MemberCount = 0; |
357 | Class.Size = 4U; |
358 | Class.DerivationList = TypeIndex::fromArrayIndex(Index: 0); |
359 | Class.FieldList = TypeIndex::fromArrayIndex(Index: 0); |
360 | Class.VTableShape = TypeIndex::fromArrayIndex(Index: 0); |
361 | TypeIndex IndexZero = Builder.writeLeafType(Record&: Class); |
362 | |
363 | // TypeIndex 1 refers to type index 0. |
364 | ModifierRecord Modifier(TypeRecordKind::Modifier); |
365 | Modifier.ModifiedType = TypeIndex::fromArrayIndex(Index: 0); |
366 | Modifier.Modifiers = ModifierOptions::Const; |
367 | TypeIndex IndexOne = Builder.writeLeafType(Record&: Modifier); |
368 | |
369 | // set up a type stream that refers to the above two serialized records. |
370 | std::vector<CVType> TypeArray = { |
371 | {Builder.records()[0]}, |
372 | {Builder.records()[1]}, |
373 | }; |
374 | BinaryItemStream<CVType> ItemStream(llvm::endianness::little); |
375 | ItemStream.setItems(TypeArray); |
376 | VarStreamArray<CVType> TypeStream(ItemStream); |
377 | |
378 | // Figure out the byte offset of the second item. |
379 | auto ItemOneIter = TypeStream.begin(); |
380 | ++ItemOneIter; |
381 | |
382 | // Set up a partial offsets buffer that contains the first and second items |
383 | // in separate chunks. |
384 | std::vector<TypeIndexOffset> TIO; |
385 | TIO.push_back(x: {.Type: IndexZero, .Offset: ulittle32_t(0u)}); |
386 | TIO.push_back(x: {.Type: IndexOne, .Offset: ulittle32_t(ItemOneIter.offset())}); |
387 | ArrayRef<uint8_t> Buffer(reinterpret_cast<const uint8_t *>(TIO.data()), |
388 | TIO.size() * sizeof(TypeIndexOffset)); |
389 | |
390 | BinaryStreamReader Reader(Buffer, llvm::endianness::little); |
391 | FixedStreamArray<TypeIndexOffset> PartialOffsets; |
392 | ASSERT_THAT_ERROR(Reader.readArray(PartialOffsets, 2), Succeeded()); |
393 | |
394 | LazyRandomTypeCollection Types(TypeStream, 2, PartialOffsets); |
395 | |
396 | StringRef Name = Types.getTypeName(Index: IndexOne); |
397 | EXPECT_EQ("const FooClass" , Name); |
398 | } |
399 | |