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