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
17using namespace llvm;
18using namespace llvm::msf;
19using namespace testing;
20
21namespace {
22class MSFBuilderTest : public testing::Test {
23protected:
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(s: &SB, c: 0, n: sizeof(SB));
32
33 ::memcpy(dest: SB.MagicBytes, src: msf::Magic, n: 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
45TEST_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
53TEST_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
80TEST_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, BlockSize: 4096, MinBlockCount: 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
106TEST_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, BlockSize: 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, BlockSize: 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(StreamIdx: 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
138TEST_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, BlockSize: 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
158TEST_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, BlockSize: 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(StreamIdx: 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(StreamIdx: 0);
173 EXPECT_EQ(1U, NewStreamBlocks.size());
174
175 EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
176}
177
178TEST_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, BlockSize: 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(StreamIdx: 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(StreamIdx: 0);
195 EXPECT_EQ(2U, NewStreamBlocks.size());
196
197 EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
198 EXPECT_NE(NewStreamBlocks[0], NewStreamBlocks[1]);
199}
200
201TEST_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, BlockSize: 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(StreamIdx: 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(StreamIdx: 0);
216 EXPECT_EQ(1U, NewStreamBlocks.size());
217
218 EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
219}
220
221TEST_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, BlockSize: 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(StreamIdx: 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(StreamIdx: 0);
237 EXPECT_EQ(1U, NewStreamBlocks.size());
238
239 EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
240}
241
242TEST_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, BlockSize: 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
255TEST_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, BlockSize: 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(NumBytes: StreamSizes[I], BlockSize: 4096);
271 EXPECT_EQ(NumUsedBlocks, Msf.getNumUsedBlocks());
272 EXPECT_EQ(0U, Msf.getNumFreeBlocks());
273 }
274}
275
276TEST_F(MSFBuilderTest, BuildMsfLayout) {
277 // Test that we can generate an MSFLayout structure from a valid layout
278 // specification.
279 auto ExpectedMsf = MSFBuilder::create(Allocator, BlockSize: 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(NumBytes: StreamSizes[I], BlockSize: 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(NumBytes: StreamSizes[I], BlockSize: 4096);
304 EXPECT_EQ(ExpectedNumBlocks, L.StreamMap[I].size());
305 }
306}
307
308TEST_F(MSFBuilderTest, UseDirectoryBlockHint) {
309 Expected<MSFBuilder> ExpectedMsf = MSFBuilder::create(
310 Allocator, BlockSize: 4096, MinBlockCount: msf::getMinimumBlockCount() + 1, CanGrow: 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
329TEST_F(MSFBuilderTest, DirectoryBlockHintInsufficient) {
330 Expected<MSFBuilder> ExpectedMsf =
331 MSFBuilder::create(Allocator, BlockSize: 4096, MinBlockCount: 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
347TEST_F(MSFBuilderTest, DirectoryBlockHintOverestimated) {
348 Expected<MSFBuilder> ExpectedMsf =
349 MSFBuilder::create(Allocator, BlockSize: 4096, MinBlockCount: 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
365TEST_F(MSFBuilderTest, StreamDoesntUseFpmBlocks) {
366 Expected<MSFBuilder> ExpectedMsf = MSFBuilder::create(Allocator, BlockSize: 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(Size: 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

source code of llvm/unittests/DebugInfo/MSF/MSFBuilderTest.cpp