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