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/DebugInfo/PDB/Native/RawTypes.h" 16 #include "llvm/Support/Allocator.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 using namespace llvm::pdb; 26 27 namespace llvm { 28 namespace codeview { 29 inline bool operator==(const ArrayRecord &R1, const ArrayRecord &R2) { 30 if (R1.ElementType != R2.ElementType) 31 return false; 32 if (R1.IndexType != R2.IndexType) 33 return false; 34 if (R1.Name != R2.Name) 35 return false; 36 if (R1.Size != R2.Size) 37 return false; 38 return true; 39 } 40 inline bool operator!=(const ArrayRecord &R1, const ArrayRecord &R2) { 41 return !(R1 == R2); 42 } 43 44 inline bool operator==(const CVType &R1, const CVType &R2) { 45 if (R1.RecordData != R2.RecordData) 46 return false; 47 return true; 48 } 49 inline bool operator!=(const CVType &R1, const CVType &R2) { 50 return !(R1 == R2); 51 } 52 } 53 } 54 55 namespace llvm { 56 template <> struct BinaryItemTraits<CVType> { 57 static size_t length(const CVType &Item) { return Item.length(); } 58 static ArrayRef<uint8_t> bytes(const CVType &Item) { return Item.data(); } 59 }; 60 } 61 62 namespace { 63 64 class MockCallbacks : public TypeVisitorCallbacks { 65 public: 66 virtual Error visitTypeBegin(CVType &CVR, TypeIndex Index) { 67 Indices.push_back(Index); 68 return Error::success(); 69 } 70 virtual Error visitKnownRecord(CVType &CVR, ArrayRecord &AR) { 71 VisitedRecords.push_back(AR); 72 RawRecords.push_back(CVR); 73 return Error::success(); 74 } 75 76 uint32_t count() const { 77 assert(Indices.size() == RawRecords.size()); 78 assert(Indices.size() == VisitedRecords.size()); 79 return Indices.size(); 80 } 81 std::vector<TypeIndex> Indices; 82 std::vector<CVType> RawRecords; 83 std::vector<ArrayRecord> VisitedRecords; 84 }; 85 86 class RandomAccessVisitorTest : public testing::Test { 87 public: 88 RandomAccessVisitorTest() {} 89 90 static void SetUpTestCase() { 91 GlobalState = std::make_unique<GlobalTestState>(); 92 93 AppendingTypeTableBuilder Builder(GlobalState->Allocator); 94 95 uint32_t Offset = 0; 96 for (int I = 0; I < 11; ++I) { 97 ArrayRecord AR(TypeRecordKind::Array); 98 AR.ElementType = TypeIndex::Int32(); 99 AR.IndexType = TypeIndex::UInt32(); 100 AR.Size = I; 101 std::string Name; 102 raw_string_ostream Stream(Name); 103 Stream << "Array [" << I << "]"; 104 AR.Name = GlobalState->Strings.save(Stream.str()); 105 GlobalState->Records.push_back(AR); 106 GlobalState->Indices.push_back(Builder.writeLeafType(AR)); 107 108 CVType Type(Builder.records().back()); 109 GlobalState->TypeVector.push_back(Type); 110 111 GlobalState->AllOffsets.push_back( 112 {GlobalState->Indices.back(), ulittle32_t(Offset)}); 113 Offset += Type.length(); 114 } 115 116 GlobalState->ItemStream.setItems(GlobalState->TypeVector); 117 GlobalState->TypeArray = VarStreamArray<CVType>(GlobalState->ItemStream); 118 } 119 120 static void TearDownTestCase() { GlobalState.reset(); } 121 122 void SetUp() override { 123 TestState = std::make_unique<PerTestState>(); 124 } 125 126 void TearDown() override { TestState.reset(); } 127 128 protected: 129 bool ValidateDatabaseRecord(LazyRandomTypeCollection &Types, uint32_t Index) { 130 TypeIndex TI = TypeIndex::fromArrayIndex(Index); 131 if (!Types.contains(TI)) 132 return false; 133 if (GlobalState->TypeVector[Index] != Types.getType(TI)) 134 return false; 135 return true; 136 } 137 138 bool ValidateVisitedRecord(uint32_t VisitationOrder, 139 uint32_t GlobalArrayIndex) { 140 TypeIndex TI = TypeIndex::fromArrayIndex(GlobalArrayIndex); 141 if (TI != TestState->Callbacks.Indices[VisitationOrder]) 142 return false; 143 144 if (GlobalState->TypeVector[TI.toArrayIndex()] != 145 TestState->Callbacks.RawRecords[VisitationOrder]) 146 return false; 147 148 if (GlobalState->Records[TI.toArrayIndex()] != 149 TestState->Callbacks.VisitedRecords[VisitationOrder]) 150 return false; 151 152 return true; 153 } 154 155 struct GlobalTestState { 156 GlobalTestState() : Strings(Allocator), ItemStream(llvm::support::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>(Size); 184 MutableArrayRef<uint8_t> Bytes(Buffer, Size); 185 Storage = MutableBinaryByteStream(Bytes, support::little); 186 BinaryStreamWriter Writer(Storage); 187 for (const auto I : Indices) 188 consumeError(Writer.writeObject(GlobalState->AllOffsets[I])); 189 190 BinaryStreamReader Reader(Storage); 191 FixedStreamArray<TypeIndexOffset> Result; 192 consumeError(Reader.readArray(Result, 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(GlobalState->Stream, {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(I); 214 CVType T = Types.getType(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 (auto I : enumerate(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(GlobalState->Stream, {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(I); 243 CVType T = Types.getType(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 (auto I : enumerate(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(GlobalState->Stream, {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(I); 272 CVType T = Types.getType(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 (auto &I : enumerate(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(GlobalState->Stream, {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(I); 303 CVType T = Types.getType(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 (auto I : enumerate(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(GlobalState->Stream, {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(I); 333 CVType T = Types.getType(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 (auto &I : enumerate(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(0); 359 Class.FieldList = TypeIndex::fromArrayIndex(0); 360 Class.VTableShape = TypeIndex::fromArrayIndex(0); 361 TypeIndex IndexZero = Builder.writeLeafType(Class); 362 363 // TypeIndex 1 refers to type index 0. 364 ModifierRecord Modifier(TypeRecordKind::Modifier); 365 Modifier.ModifiedType = TypeIndex::fromArrayIndex(0); 366 Modifier.Modifiers = ModifierOptions::Const; 367 TypeIndex IndexOne = Builder.writeLeafType(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::support::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({IndexZero, ulittle32_t(0u)}); 386 TIO.push_back({IndexOne, 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::support::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(IndexOne); 397 EXPECT_EQ("const FooClass", Name); 398 } 399