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