1//===- MSFBuilder.cpp -----------------------------------------------------===//
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/ADT/ArrayRef.h"
11#include "llvm/DebugInfo/MSF/MSFError.h"
12#include "llvm/DebugInfo/MSF/MappedBlockStream.h"
13#include "llvm/Support/BinaryByteStream.h"
14#include "llvm/Support/BinaryStreamWriter.h"
15#include "llvm/Support/Endian.h"
16#include "llvm/Support/Error.h"
17#include "llvm/Support/FileOutputBuffer.h"
18#include "llvm/Support/FormatVariadic.h"
19#include "llvm/Support/TimeProfiler.h"
20#include <algorithm>
21#include <cassert>
22#include <cstdint>
23#include <cstring>
24#include <memory>
25#include <utility>
26#include <vector>
27
28using namespace llvm;
29using namespace llvm::msf;
30using namespace llvm::support;
31
32static const uint32_t kSuperBlockBlock = 0;
33static const uint32_t kFreePageMap0Block = 1;
34static const uint32_t kFreePageMap1Block = 2;
35static const uint32_t kNumReservedPages = 3;
36
37static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
38static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
39
40MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
41 BumpPtrAllocator &Allocator)
42 : Allocator(Allocator), IsGrowable(CanGrow),
43 FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
44 BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
45 FreeBlocks[kSuperBlockBlock] = false;
46 FreeBlocks[kFreePageMap0Block] = false;
47 FreeBlocks[kFreePageMap1Block] = false;
48 FreeBlocks[BlockMapAddr] = false;
49}
50
51Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
52 uint32_t BlockSize,
53 uint32_t MinBlockCount, bool CanGrow) {
54 if (!isValidBlockSize(Size: BlockSize))
55 return make_error<MSFError>(Args: msf_error_code::invalid_format,
56 Args: "The requested block size is unsupported");
57
58 return MSFBuilder(BlockSize,
59 std::max(a: MinBlockCount, b: msf::getMinimumBlockCount()),
60 CanGrow, Allocator);
61}
62
63Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
64 if (Addr == BlockMapAddr)
65 return Error::success();
66
67 if (Addr >= FreeBlocks.size()) {
68 if (!IsGrowable)
69 return make_error<MSFError>(Args: msf_error_code::insufficient_buffer,
70 Args: "Cannot grow the number of blocks");
71 FreeBlocks.resize(N: Addr + 1, t: true);
72 }
73
74 if (!isBlockFree(Idx: Addr))
75 return make_error<MSFError>(
76 Args: msf_error_code::block_in_use,
77 Args: "Requested block map address is already in use");
78 FreeBlocks[BlockMapAddr] = true;
79 FreeBlocks[Addr] = false;
80 BlockMapAddr = Addr;
81 return Error::success();
82}
83
84void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
85
86void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
87
88Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
89 for (auto B : DirectoryBlocks)
90 FreeBlocks[B] = true;
91 for (auto B : DirBlocks) {
92 if (!isBlockFree(Idx: B)) {
93 return make_error<MSFError>(Args: msf_error_code::unspecified,
94 Args: "Attempt to reuse an allocated block");
95 }
96 FreeBlocks[B] = false;
97 }
98
99 DirectoryBlocks = DirBlocks;
100 return Error::success();
101}
102
103Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
104 MutableArrayRef<uint32_t> Blocks) {
105 if (NumBlocks == 0)
106 return Error::success();
107
108 uint32_t NumFreeBlocks = FreeBlocks.count();
109 if (NumFreeBlocks < NumBlocks) {
110 if (!IsGrowable)
111 return make_error<MSFError>(Args: msf_error_code::insufficient_buffer,
112 Args: "There are no free Blocks in the file");
113 uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
114 uint32_t OldBlockCount = FreeBlocks.size();
115 uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
116 uint32_t NextFpmBlock = alignTo(Value: OldBlockCount, Align: BlockSize) + 1;
117 FreeBlocks.resize(N: NewBlockCount, t: true);
118 // If we crossed over an fpm page, we actually need to allocate 2 extra
119 // blocks for each FPM group crossed and mark both blocks from the group as
120 // used. FPM blocks are marked as allocated regardless of whether or not
121 // they ultimately describe the status of blocks in the file. This means
122 // that not only are extraneous blocks at the end of the main FPM marked as
123 // allocated, but also blocks from the alternate FPM are always marked as
124 // allocated.
125 while (NextFpmBlock < NewBlockCount) {
126 NewBlockCount += 2;
127 FreeBlocks.resize(N: NewBlockCount, t: true);
128 FreeBlocks.reset(I: NextFpmBlock, E: NextFpmBlock + 2);
129 NextFpmBlock += BlockSize;
130 }
131 }
132
133 int I = 0;
134 int Block = FreeBlocks.find_first();
135 do {
136 assert(Block != -1 && "We ran out of Blocks!");
137
138 uint32_t NextBlock = static_cast<uint32_t>(Block);
139 Blocks[I++] = NextBlock;
140 FreeBlocks.reset(Idx: NextBlock);
141 Block = FreeBlocks.find_next(Prev: Block);
142 } while (--NumBlocks > 0);
143 return Error::success();
144}
145
146uint32_t MSFBuilder::getNumUsedBlocks() const {
147 return getTotalBlockCount() - getNumFreeBlocks();
148}
149
150uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
151
152uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
153
154bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
155
156Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
157 ArrayRef<uint32_t> Blocks) {
158 // Add a new stream mapped to the specified blocks. Verify that the specified
159 // blocks are both necessary and sufficient for holding the requested number
160 // of bytes, and verify that all requested blocks are free.
161 uint32_t ReqBlocks = bytesToBlocks(NumBytes: Size, BlockSize);
162 if (ReqBlocks != Blocks.size())
163 return make_error<MSFError>(
164 Args: msf_error_code::invalid_format,
165 Args: "Incorrect number of blocks for requested stream size");
166 for (auto Block : Blocks) {
167 if (Block >= FreeBlocks.size())
168 FreeBlocks.resize(N: Block + 1, t: true);
169
170 if (!FreeBlocks.test(Idx: Block))
171 return make_error<MSFError>(
172 Args: msf_error_code::unspecified,
173 Args: "Attempt to re-use an already allocated block");
174 }
175 // Mark all the blocks occupied by the new stream as not free.
176 for (auto Block : Blocks) {
177 FreeBlocks.reset(Idx: Block);
178 }
179 StreamData.push_back(x: std::make_pair(x&: Size, y&: Blocks));
180 return StreamData.size() - 1;
181}
182
183Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
184 uint32_t ReqBlocks = bytesToBlocks(NumBytes: Size, BlockSize);
185 std::vector<uint32_t> NewBlocks;
186 NewBlocks.resize(new_size: ReqBlocks);
187 if (auto EC = allocateBlocks(NumBlocks: ReqBlocks, Blocks: NewBlocks))
188 return std::move(EC);
189 StreamData.push_back(x: std::make_pair(x&: Size, y&: NewBlocks));
190 return StreamData.size() - 1;
191}
192
193Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
194 uint32_t OldSize = getStreamSize(StreamIdx: Idx);
195 if (OldSize == Size)
196 return Error::success();
197
198 uint32_t NewBlocks = bytesToBlocks(NumBytes: Size, BlockSize);
199 uint32_t OldBlocks = bytesToBlocks(NumBytes: OldSize, BlockSize);
200
201 if (NewBlocks > OldBlocks) {
202 uint32_t AddedBlocks = NewBlocks - OldBlocks;
203 // If we're growing, we have to allocate new Blocks.
204 std::vector<uint32_t> AddedBlockList;
205 AddedBlockList.resize(new_size: AddedBlocks);
206 if (auto EC = allocateBlocks(NumBlocks: AddedBlocks, Blocks: AddedBlockList))
207 return EC;
208 auto &CurrentBlocks = StreamData[Idx].second;
209 llvm::append_range(C&: CurrentBlocks, R&: AddedBlockList);
210 } else if (OldBlocks > NewBlocks) {
211 // For shrinking, free all the Blocks in the Block map, update the stream
212 // data, then shrink the directory.
213 uint32_t RemovedBlocks = OldBlocks - NewBlocks;
214 auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
215 auto RemovedBlockList = CurrentBlocks.drop_front(N: NewBlocks);
216 for (auto P : RemovedBlockList)
217 FreeBlocks[P] = true;
218 StreamData[Idx].second = CurrentBlocks.drop_back(N: RemovedBlocks);
219 }
220
221 StreamData[Idx].first = Size;
222 return Error::success();
223}
224
225uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
226
227uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
228 return StreamData[StreamIdx].first;
229}
230
231ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
232 return StreamData[StreamIdx].second;
233}
234
235uint32_t MSFBuilder::computeDirectoryByteSize() const {
236 // The directory has the following layout, where each item is a ulittle32_t:
237 // NumStreams
238 // StreamSizes[NumStreams]
239 // StreamBlocks[NumStreams][]
240 uint32_t Size = sizeof(ulittle32_t); // NumStreams
241 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
242 for (const auto &D : StreamData) {
243 uint32_t ExpectedNumBlocks = bytesToBlocks(NumBytes: D.first, BlockSize);
244 assert(ExpectedNumBlocks == D.second.size() &&
245 "Unexpected number of blocks");
246 Size += ExpectedNumBlocks * sizeof(ulittle32_t);
247 }
248 return Size;
249}
250
251Expected<MSFLayout> MSFBuilder::generateLayout() {
252 llvm::TimeTraceScope timeScope("MSF: Generate layout");
253
254 SuperBlock *SB = Allocator.Allocate<SuperBlock>();
255 MSFLayout L;
256 L.SB = SB;
257
258 std::memcpy(dest: SB->MagicBytes, src: Magic, n: sizeof(Magic));
259 SB->BlockMapAddr = BlockMapAddr;
260 SB->BlockSize = BlockSize;
261 SB->NumDirectoryBytes = computeDirectoryByteSize();
262 SB->FreeBlockMapBlock = FreePageMap;
263 SB->Unknown1 = Unknown1;
264
265 uint32_t NumDirectoryBlocks = bytesToBlocks(NumBytes: SB->NumDirectoryBytes, BlockSize);
266 if (NumDirectoryBlocks > DirectoryBlocks.size()) {
267 // Our hint wasn't enough to satisfy the entire directory. Allocate
268 // remaining pages.
269 std::vector<uint32_t> ExtraBlocks;
270 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
271 ExtraBlocks.resize(new_size: NumExtraBlocks);
272 if (auto EC = allocateBlocks(NumBlocks: NumExtraBlocks, Blocks: ExtraBlocks))
273 return std::move(EC);
274 llvm::append_range(C&: DirectoryBlocks, R&: ExtraBlocks);
275 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
276 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
277 for (auto B :
278 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(N: NumUnnecessaryBlocks))
279 FreeBlocks[B] = true;
280 DirectoryBlocks.resize(new_size: NumDirectoryBlocks);
281 }
282
283 // Don't set the number of blocks in the file until after allocating Blocks
284 // for the directory, since the allocation might cause the file to need to
285 // grow.
286 SB->NumBlocks = FreeBlocks.size();
287
288 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(Num: NumDirectoryBlocks);
289 std::uninitialized_copy_n(first: DirectoryBlocks.begin(), n: NumDirectoryBlocks,
290 result: DirBlocks);
291 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
292
293 // The stream sizes should be re-allocated as a stable pointer and the stream
294 // map should have each of its entries allocated as a separate stable pointer.
295 if (!StreamData.empty()) {
296 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(Num: StreamData.size());
297 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
298 L.StreamMap.resize(new_size: StreamData.size());
299 for (uint32_t I = 0; I < StreamData.size(); ++I) {
300 Sizes[I] = StreamData[I].first;
301 ulittle32_t *BlockList =
302 Allocator.Allocate<ulittle32_t>(Num: StreamData[I].second.size());
303 std::uninitialized_copy_n(first: StreamData[I].second.begin(),
304 n: StreamData[I].second.size(), result: BlockList);
305 L.StreamMap[I] =
306 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
307 }
308 }
309
310 L.FreePageMap = FreeBlocks;
311
312 return L;
313}
314
315static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
316 BumpPtrAllocator &Allocator) {
317 auto FpmStream =
318 WritableMappedBlockStream::createFpmStream(Layout, MsfData: MsfBuffer, Allocator);
319
320 // We only need to create the alt fpm stream so that it gets initialized.
321 WritableMappedBlockStream::createFpmStream(Layout, MsfData: MsfBuffer, Allocator,
322 AltFpm: true);
323
324 uint32_t BI = 0;
325 BinaryStreamWriter FpmWriter(*FpmStream);
326 while (BI < Layout.SB->NumBlocks) {
327 uint8_t ThisByte = 0;
328 for (uint32_t I = 0; I < 8; ++I) {
329 bool IsFree =
330 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(Idx: BI) : true;
331 uint8_t Mask = uint8_t(IsFree) << I;
332 ThisByte |= Mask;
333 ++BI;
334 }
335 cantFail(Err: FpmWriter.writeObject(Obj: ThisByte));
336 }
337 assert(FpmWriter.bytesRemaining() == 0);
338}
339
340Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
341 MSFLayout &Layout) {
342 llvm::TimeTraceScope timeScope("Commit MSF");
343
344 Expected<MSFLayout> L = generateLayout();
345 if (!L)
346 return L.takeError();
347
348 Layout = std::move(*L);
349
350 uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks;
351 // Ensure that the file size is under the limit for the specified block size.
352 if (FileSize > getMaxFileSizeFromBlockSize(Size: Layout.SB->BlockSize)) {
353 msf_error_code error_code = [](uint32_t BlockSize) {
354 switch (BlockSize) {
355 case 8192:
356 return msf_error_code::size_overflow_8192;
357 case 16384:
358 return msf_error_code::size_overflow_16384;
359 case 32768:
360 return msf_error_code::size_overflow_32768;
361 default:
362 return msf_error_code::size_overflow_4096;
363 }
364 }(Layout.SB->BlockSize);
365
366 return make_error<MSFError>(
367 Args&: error_code,
368 Args: formatv(Fmt: "File size {0,1:N} too large for current PDB page size {1}",
369 Vals&: FileSize, Vals: Layout.SB->BlockSize));
370 }
371
372 uint64_t NumDirectoryBlocks =
373 bytesToBlocks(NumBytes: Layout.SB->NumDirectoryBytes, BlockSize: Layout.SB->BlockSize);
374 uint64_t DirectoryBlockMapSize =
375 NumDirectoryBlocks * sizeof(support::ulittle32_t);
376 if (DirectoryBlockMapSize > Layout.SB->BlockSize) {
377 return make_error<MSFError>(Args: msf_error_code::stream_directory_overflow,
378 Args: formatv(Fmt: "The directory block map ({0} bytes) "
379 "doesn't fit in a block ({1} bytes)",
380 Vals&: DirectoryBlockMapSize,
381 Vals: Layout.SB->BlockSize));
382 }
383
384 auto OutFileOrError = FileOutputBuffer::create(FilePath: Path, Size: FileSize);
385 if (auto EC = OutFileOrError.takeError())
386 return std::move(EC);
387
388 FileBufferByteStream Buffer(std::move(*OutFileOrError),
389 llvm::endianness::little);
390 BinaryStreamWriter Writer(Buffer);
391
392 if (auto EC = Writer.writeObject(Obj: *Layout.SB))
393 return std::move(EC);
394
395 commitFpm(MsfBuffer&: Buffer, Layout, Allocator);
396
397 uint32_t BlockMapOffset =
398 msf::blockToOffset(BlockNumber: Layout.SB->BlockMapAddr, BlockSize: Layout.SB->BlockSize);
399 Writer.setOffset(BlockMapOffset);
400 if (auto EC = Writer.writeArray(Array: Layout.DirectoryBlocks))
401 return std::move(EC);
402
403 auto DirStream = WritableMappedBlockStream::createDirectoryStream(
404 Layout, MsfData: Buffer, Allocator);
405 BinaryStreamWriter DW(*DirStream);
406 if (auto EC = DW.writeInteger<uint32_t>(Value: Layout.StreamSizes.size()))
407 return std::move(EC);
408
409 if (auto EC = DW.writeArray(Array: Layout.StreamSizes))
410 return std::move(EC);
411
412 for (const auto &Blocks : Layout.StreamMap) {
413 if (auto EC = DW.writeArray(Array: Blocks))
414 return std::move(EC);
415 }
416
417 return std::move(Buffer);
418}
419