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(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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
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, 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 | |
308 | TEST_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 | |
329 | TEST_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 | |
347 | TEST_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 | |
365 | TEST_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 | |