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