llvm/unittests/DebugInfo/CodeView/RandomAccessVisitorTest.cpp

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