unittests/DebugInfo/MSF/MSFBuilderTest.cpp

   1 //===- MSFBuilderTest.cpp  Tests manipulation of MSF stream metadata ------===//
   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/MSF/MSFBuilder.h"
  10 #include "llvm/DebugInfo/MSF/MSFCommon.h"
  11 #include "llvm/Testing/Support/Error.h"
  12
  13 #include "gmock/gmock-matchers.h"
  14 #include "gmock/gmock.h"
  15 #include "gtest/gtest.h"
  16
  17 using namespace llvm;
  18 using namespace llvm::msf;
  19 using namespace testing;
  20
  21 namespace {
  22 class MSFBuilderTest : public testing::Test {
  23 protected:
  24   void initializeSimpleSuperBlock(msf::SuperBlock &SB) {
  25     initializeSuperBlock(SB);
  26     SB.NumBlocks = 1000;
  27     SB.NumDirectoryBytes = 8192;
  28   }
  29
  30   void initializeSuperBlock(msf::SuperBlock &SB) {
  31     ::memset(&SB, 0, sizeof(SB));
  32
  33     ::memcpy(SB.MagicBytes, msf::Magic, sizeof(msf::Magic));
  34     SB.FreeBlockMapBlock = 1;
  35     SB.BlockMapAddr = 1;
  36     SB.BlockSize = 4096;
  37     SB.NumDirectoryBytes = 0;
  38     SB.NumBlocks = 2; // one for the Super Block, one for the directory
  39   }
  40
  41   BumpPtrAllocator Allocator;
  42 };
  43 } // namespace
  44
  45 TEST_F(MSFBuilderTest, ValidateSuperBlockAccept) {
  46   // Test that a known good super block passes validation.
  47   SuperBlock SB;
  48   initializeSuperBlock(SB);
  49
  50   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Succeeded());
  51 }
  52
  53 TEST_F(MSFBuilderTest, ValidateSuperBlockReject) {
  54   // Test that various known problems cause a super block to be rejected.
  55   SuperBlock SB;
  56   initializeSimpleSuperBlock(SB);
  57
  58   // Mismatched magic
  59   SB.MagicBytes[0] = 8;
  60   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Failed());
  61   initializeSimpleSuperBlock(SB);
  62
  63   // Block 0 is reserved for super block, can't be occupied by the block map
  64   SB.BlockMapAddr = 0;
  65   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Failed());
  66   initializeSimpleSuperBlock(SB);
  67
  68   // Block sizes have to be powers of 2.
  69   SB.BlockSize = 3120;
  70   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Failed());
  71   initializeSimpleSuperBlock(SB);
  72
  73   // The directory itself has a maximum size.
  74   SB.NumDirectoryBytes = SB.BlockSize * SB.BlockSize / 4;
  75   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Succeeded());
  76   SB.NumDirectoryBytes = SB.NumDirectoryBytes + 4;
  77   EXPECT_THAT_ERROR(msf::validateSuperBlock(SB), Failed());
  78 }
  79
  80 TEST_F(MSFBuilderTest, TestUsedBlocksMarkedAsUsed) {
  81   // Test that when assigning a stream to a known list of blocks, the blocks
  82   // are correctly marked as used after adding, but no other incorrect blocks
  83   // are accidentally marked as used.
  84
  85   std::vector<uint32_t> Blocks = {4, 5, 6, 7, 8, 9, 10, 11, 12};
  86   // Allocate some extra blocks at the end so we can verify that they're free
  87   // after the initialization.
  88   uint32_t NumBlocks = msf::getMinimumBlockCount() + Blocks.size() + 10;
  89   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096, NumBlocks);
  90   ASSERT_THAT_EXPECTED(ExpectedMsf, Succeeded());
  91   auto &Msf = *ExpectedMsf;
  92
  93   EXPECT_THAT_EXPECTED(Msf.addStream(Blocks.size() * 4096, Blocks),
  94                        Succeeded());
  95
  96   for (auto B : Blocks) {
  97     EXPECT_FALSE(Msf.isBlockFree(B));
  98   }
  99
 100   uint32_t FreeBlockStart = Blocks.back() + 1;
 101   for (uint32_t I = FreeBlockStart; I < NumBlocks; ++I) {
 102     EXPECT_TRUE(Msf.isBlockFree(I));
 103   }
 104 }
 105
 106 TEST_F(MSFBuilderTest, TestAddStreamNoDirectoryBlockIncrease) {
 107   // Test that adding a new stream correctly updates the directory.  This only
 108   // tests the case where the directory *DOES NOT* grow large enough that it
 109   // crosses a Block boundary.
 110   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 111   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 112   auto &Msf = *ExpectedMsf;
 113
 114   auto ExpectedL1 = Msf.generateLayout();
 115   EXPECT_THAT_EXPECTED(ExpectedL1, Succeeded());
 116   MSFLayout &L1 = *ExpectedL1;
 117
 118   auto OldDirBlocks = L1.DirectoryBlocks;
 119   EXPECT_EQ(1U, OldDirBlocks.size());
 120
 121   auto ExpectedMsf2 = MSFBuilder::create(Allocator, 4096);
 122   EXPECT_THAT_EXPECTED(ExpectedMsf2, Succeeded());
 123   auto &Msf2 = *ExpectedMsf2;
 124
 125   EXPECT_THAT_EXPECTED(Msf2.addStream(4000), Succeeded());
 126   EXPECT_EQ(1U, Msf2.getNumStreams());
 127   EXPECT_EQ(4000U, Msf2.getStreamSize(0));
 128   auto Blocks = Msf2.getStreamBlocks(0);
 129   EXPECT_EQ(1U, Blocks.size());
 130
 131   auto ExpectedL2 = Msf2.generateLayout();
 132   EXPECT_THAT_EXPECTED(ExpectedL2, Succeeded());
 133   MSFLayout &L2 = *ExpectedL2;
 134   auto NewDirBlocks = L2.DirectoryBlocks;
 135   EXPECT_EQ(1U, NewDirBlocks.size());
 136 }
 137
 138 TEST_F(MSFBuilderTest, TestAddStreamWithDirectoryBlockIncrease) {
 139   // Test that adding a new stream correctly updates the directory.  This only
 140   // tests the case where the directory *DOES* grow large enough that it
 141   // crosses a Block boundary.  This is because the newly added stream occupies
 142   // so many Blocks that need to be indexed in the directory that the directory
 143   // crosses a Block boundary.
 144   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 145   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 146   auto &Msf = *ExpectedMsf;
 147
 148   EXPECT_THAT_EXPECTED(Msf.addStream(4096 * 4096 / sizeof(uint32_t)),
 149                        Succeeded());
 150
 151   auto ExpectedL1 = Msf.generateLayout();
 152   EXPECT_THAT_EXPECTED(ExpectedL1, Succeeded());
 153   MSFLayout &L1 = *ExpectedL1;
 154   auto DirBlocks = L1.DirectoryBlocks;
 155   EXPECT_EQ(2U, DirBlocks.size());
 156 }
 157
 158 TEST_F(MSFBuilderTest, TestGrowStreamNoBlockIncrease) {
 159   // Test growing an existing stream by a value that does not affect the number
 160   // of blocks it occupies.
 161   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 162   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 163   auto &Msf = *ExpectedMsf;
 164
 165   EXPECT_THAT_EXPECTED(Msf.addStream(1024), Succeeded());
 166   EXPECT_EQ(1024U, Msf.getStreamSize(0));
 167   auto OldStreamBlocks = Msf.getStreamBlocks(0);
 168   EXPECT_EQ(1U, OldStreamBlocks.size());
 169
 170   EXPECT_THAT_ERROR(Msf.setStreamSize(0, 2048), Succeeded());
 171   EXPECT_EQ(2048U, Msf.getStreamSize(0));
 172   auto NewStreamBlocks = Msf.getStreamBlocks(0);
 173   EXPECT_EQ(1U, NewStreamBlocks.size());
 174
 175   EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
 176 }
 177
 178 TEST_F(MSFBuilderTest, TestGrowStreamWithBlockIncrease) {
 179   // Test that growing an existing stream to a value large enough that it causes
 180   // the need to allocate new Blocks to the stream correctly updates the
 181   // stream's
 182   // block list.
 183   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 184   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 185   auto &Msf = *ExpectedMsf;
 186
 187   EXPECT_THAT_EXPECTED(Msf.addStream(2048), Succeeded());
 188   EXPECT_EQ(2048U, Msf.getStreamSize(0));
 189   std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
 190   EXPECT_EQ(1U, OldStreamBlocks.size());
 191
 192   EXPECT_THAT_ERROR(Msf.setStreamSize(0, 6144), Succeeded());
 193   EXPECT_EQ(6144U, Msf.getStreamSize(0));
 194   std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
 195   EXPECT_EQ(2U, NewStreamBlocks.size());
 196
 197   EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
 198   EXPECT_NE(NewStreamBlocks[0], NewStreamBlocks[1]);
 199 }
 200
 201 TEST_F(MSFBuilderTest, TestShrinkStreamNoBlockDecrease) {
 202   // Test that shrinking an existing stream by a value that does not affect the
 203   // number of Blocks it occupies makes no changes to stream's block list.
 204   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 205   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 206   auto &Msf = *ExpectedMsf;
 207
 208   EXPECT_THAT_EXPECTED(Msf.addStream(2048), Succeeded());
 209   EXPECT_EQ(2048U, Msf.getStreamSize(0));
 210   std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
 211   EXPECT_EQ(1U, OldStreamBlocks.size());
 212
 213   EXPECT_THAT_ERROR(Msf.setStreamSize(0, 1024), Succeeded());
 214   EXPECT_EQ(1024U, Msf.getStreamSize(0));
 215   std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
 216   EXPECT_EQ(1U, NewStreamBlocks.size());
 217
 218   EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
 219 }
 220
 221 TEST_F(MSFBuilderTest, TestShrinkStreamWithBlockDecrease) {
 222   // Test that shrinking an existing stream to a value large enough that it
 223   // causes the need to deallocate new Blocks to the stream correctly updates
 224   // the stream's block list.
 225   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 226   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 227   auto &Msf = *ExpectedMsf;
 228
 229   EXPECT_THAT_EXPECTED(Msf.addStream(6144), Succeeded());
 230   EXPECT_EQ(6144U, Msf.getStreamSize(0));
 231   std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
 232   EXPECT_EQ(2U, OldStreamBlocks.size());
 233
 234   EXPECT_THAT_ERROR(Msf.setStreamSize(0, 2048), Succeeded());
 235   EXPECT_EQ(2048U, Msf.getStreamSize(0));
 236   std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
 237   EXPECT_EQ(1U, NewStreamBlocks.size());
 238
 239   EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
 240 }
 241
 242 TEST_F(MSFBuilderTest, TestRejectReusedStreamBlock) {
 243   // Test that attempting to add a stream and assigning a block that is already
 244   // in use by another stream fails.
 245   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 246   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 247   auto &Msf = *ExpectedMsf;
 248
 249   EXPECT_THAT_EXPECTED(Msf.addStream(6144), Succeeded());
 250
 251   std::vector<uint32_t> Blocks = {2, 3};
 252   EXPECT_THAT_EXPECTED(Msf.addStream(6144, Blocks), Failed());
 253 }
 254
 255 TEST_F(MSFBuilderTest, TestBlockCountsWhenAddingStreams) {
 256   // Test that when adding multiple streams, the number of used and free Blocks
 257   // allocated to the MSF file are as expected.
 258   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 259   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 260   auto &Msf = *ExpectedMsf;
 261
 262   // one for the super block, one for the directory block map
 263   uint32_t NumUsedBlocks = Msf.getNumUsedBlocks();
 264   EXPECT_EQ(msf::getMinimumBlockCount(), NumUsedBlocks);
 265   EXPECT_EQ(0U, Msf.getNumFreeBlocks());
 266
 267   const uint32_t StreamSizes[] = {4000, 6193, 189723};
 268   for (int I = 0; I < 3; ++I) {
 269     EXPECT_THAT_EXPECTED(Msf.addStream(StreamSizes[I]), Succeeded());
 270     NumUsedBlocks += bytesToBlocks(StreamSizes[I], 4096);
 271     EXPECT_EQ(NumUsedBlocks, Msf.getNumUsedBlocks());
 272     EXPECT_EQ(0U, Msf.getNumFreeBlocks());
 273   }
 274 }
 275
 276 TEST_F(MSFBuilderTest, BuildMsfLayout) {
 277   // Test that we can generate an MSFLayout structure from a valid layout
 278   // specification.
 279   auto ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 280   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 281   auto &Msf = *ExpectedMsf;
 282
 283   const uint32_t StreamSizes[] = {4000, 6193, 189723};
 284   uint32_t ExpectedNumBlocks = msf::getMinimumBlockCount();
 285   for (int I = 0; I < 3; ++I) {
 286     EXPECT_THAT_EXPECTED(Msf.addStream(StreamSizes[I]), Succeeded());
 287     ExpectedNumBlocks += bytesToBlocks(StreamSizes[I], 4096);
 288   }
 289   ++ExpectedNumBlocks; // The directory itself should use 1 block
 290
 291   auto ExpectedLayout = Msf.generateLayout();
 292   EXPECT_THAT_EXPECTED(ExpectedLayout, Succeeded());
 293   MSFLayout &L = *ExpectedLayout;
 294   EXPECT_EQ(4096U, L.SB->BlockSize);
 295   EXPECT_EQ(ExpectedNumBlocks, L.SB->NumBlocks);
 296
 297   EXPECT_EQ(1U, L.DirectoryBlocks.size());
 298
 299   EXPECT_EQ(3U, L.StreamMap.size());
 300   EXPECT_EQ(3U, L.StreamSizes.size());
 301   for (int I = 0; I < 3; ++I) {
 302     EXPECT_EQ(StreamSizes[I], L.StreamSizes[I]);
 303     uint32_t ExpectedNumBlocks = bytesToBlocks(StreamSizes[I], 4096);
 304     EXPECT_EQ(ExpectedNumBlocks, L.StreamMap[I].size());
 305   }
 306 }
 307
 308 TEST_F(MSFBuilderTest, UseDirectoryBlockHint) {
 309   Expected<MSFBuilder> ExpectedMsf = MSFBuilder::create(
 310       Allocator, 4096, msf::getMinimumBlockCount() + 1, false);
 311   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 312   auto &Msf = *ExpectedMsf;
 313
 314   uint32_t B = msf::getFirstUnreservedBlock();
 315   EXPECT_THAT_ERROR(Msf.setDirectoryBlocksHint({B + 1}), Succeeded());
 316   EXPECT_THAT_EXPECTED(Msf.addStream(2048, {B + 2}), Succeeded());
 317
 318   auto ExpectedLayout = Msf.generateLayout();
 319   EXPECT_THAT_EXPECTED(ExpectedLayout, Succeeded());
 320   MSFLayout &L = *ExpectedLayout;
 321   EXPECT_EQ(msf::getMinimumBlockCount() + 2, L.SB->NumBlocks);
 322   EXPECT_EQ(1U, L.DirectoryBlocks.size());
 323   EXPECT_EQ(1U, L.StreamMap[0].size());
 324
 325   EXPECT_EQ(B + 1, L.DirectoryBlocks[0]);
 326   EXPECT_EQ(B + 2, L.StreamMap[0].front());
 327 }
 328
 329 TEST_F(MSFBuilderTest, DirectoryBlockHintInsufficient) {
 330   Expected<MSFBuilder> ExpectedMsf =
 331       MSFBuilder::create(Allocator, 4096, msf::getMinimumBlockCount() + 2);
 332   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 333   auto &Msf = *ExpectedMsf;
 334   uint32_t B = msf::getFirstUnreservedBlock();
 335   EXPECT_THAT_ERROR(Msf.setDirectoryBlocksHint({B + 1}), Succeeded());
 336
 337   uint32_t Size = 4096 * 4096 / 4;
 338   EXPECT_THAT_EXPECTED(Msf.addStream(Size), Succeeded());
 339
 340   auto ExpectedLayout = Msf.generateLayout();
 341   EXPECT_THAT_EXPECTED(ExpectedLayout, Succeeded());
 342   MSFLayout &L = *ExpectedLayout;
 343   EXPECT_EQ(2U, L.DirectoryBlocks.size());
 344   EXPECT_EQ(B + 1, L.DirectoryBlocks[0]);
 345 }
 346
 347 TEST_F(MSFBuilderTest, DirectoryBlockHintOverestimated) {
 348   Expected<MSFBuilder> ExpectedMsf =
 349       MSFBuilder::create(Allocator, 4096, msf::getMinimumBlockCount() + 2);
 350   EXPECT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 351   auto &Msf = *ExpectedMsf;
 352
 353   uint32_t B = msf::getFirstUnreservedBlock();
 354   EXPECT_THAT_ERROR(Msf.setDirectoryBlocksHint({B + 1, B + 2}), Succeeded());
 355
 356   ASSERT_THAT_EXPECTED(Msf.addStream(2048), Succeeded());
 357
 358   auto ExpectedLayout = Msf.generateLayout();
 359   ASSERT_THAT_EXPECTED(ExpectedLayout, Succeeded());
 360   MSFLayout &L = *ExpectedLayout;
 361   EXPECT_EQ(1U, L.DirectoryBlocks.size());
 362   EXPECT_EQ(B + 1, L.DirectoryBlocks[0]);
 363 }
 364
 365 TEST_F(MSFBuilderTest, StreamDoesntUseFpmBlocks) {
 366   Expected<MSFBuilder> ExpectedMsf = MSFBuilder::create(Allocator, 4096);
 367   ASSERT_THAT_EXPECTED(ExpectedMsf, Succeeded());
 368   auto &Msf = *ExpectedMsf;
 369
 370   // A block is 4096 bytes, and every 4096 blocks we have 2 reserved FPM blocks.
 371   // By creating add a stream that spans 4096*4096*3 bytes, we ensure that we
 372   // cross over a couple of reserved FPM blocks, and that none of them are
 373   // allocated to the stream.
 374   constexpr uint32_t StreamSize = 4096 * 4096 * 3;
 375   Expected<uint32_t> SN = Msf.addStream(StreamSize);
 376   ASSERT_THAT_EXPECTED(SN, Succeeded());
 377
 378   auto ExpectedLayout = Msf.generateLayout();
 379   ASSERT_THAT_EXPECTED(ExpectedLayout, Succeeded());
 380   MSFLayout &L = *ExpectedLayout;
 381   auto BlocksRef = L.StreamMap[*SN];
 382   std::vector<uint32_t> Blocks(BlocksRef.begin(), BlocksRef.end());
 383   EXPECT_EQ(StreamSize, L.StreamSizes[*SN]);
 384
 385   for (uint32_t I = 0; I <= 3; ++I) {
 386     // Pages from both FPMs are always allocated.
 387     EXPECT_FALSE(L.FreePageMap.test(2 + I * 4096));
 388     EXPECT_FALSE(L.FreePageMap.test(1 + I * 4096));
 389   }
 390
 391   for (uint32_t I = 1; I <= 3; ++I) {
 392     EXPECT_THAT(Blocks, Not(Contains(1 + I * 4096)));
 393     EXPECT_THAT(Blocks, Not(Contains(2 + I * 4096)));
 394   }
 395 }