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 } 396