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