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