LLVM 17.0.0git
MSFBuilder.cpp
Go to the documentation of this file.
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
10#include "llvm/ADT/ArrayRef.h"
15#include "llvm/Support/Endian.h"
16#include "llvm/Support/Error.h"
19#include <algorithm>
20#include <cassert>
21#include <cstdint>
22#include <cstring>
23#include <memory>
24#include <utility>
25#include <vector>
26
27using namespace llvm;
28using namespace llvm::msf;
29using namespace llvm::support;
30
31static const uint32_t kSuperBlockBlock = 0;
34static const uint32_t kNumReservedPages = 3;
35
38
39MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
40 BumpPtrAllocator &Allocator)
41 : Allocator(Allocator), IsGrowable(CanGrow),
43 BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
44 FreeBlocks[kSuperBlockBlock] = false;
45 FreeBlocks[kFreePageMap0Block] = false;
46 FreeBlocks[kFreePageMap1Block] = false;
47 FreeBlocks[BlockMapAddr] = false;
48}
49
52 uint32_t MinBlockCount, bool CanGrow) {
53 if (!isValidBlockSize(BlockSize))
54 return make_error<MSFError>(msf_error_code::invalid_format,
55 "The requested block size is unsupported");
56
57 return MSFBuilder(BlockSize,
58 std::max(MinBlockCount, msf::getMinimumBlockCount()),
59 CanGrow, Allocator);
60}
61
63 if (Addr == BlockMapAddr)
64 return Error::success();
65
66 if (Addr >= FreeBlocks.size()) {
67 if (!IsGrowable)
68 return make_error<MSFError>(msf_error_code::insufficient_buffer,
69 "Cannot grow the number of blocks");
70 FreeBlocks.resize(Addr + 1, true);
71 }
72
73 if (!isBlockFree(Addr))
74 return make_error<MSFError>(
76 "Requested block map address is already in use");
77 FreeBlocks[BlockMapAddr] = true;
78 FreeBlocks[Addr] = false;
79 BlockMapAddr = Addr;
80 return Error::success();
81}
82
83void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
84
85void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
86
88 for (auto B : DirectoryBlocks)
89 FreeBlocks[B] = true;
90 for (auto B : DirBlocks) {
91 if (!isBlockFree(B)) {
92 return make_error<MSFError>(msf_error_code::unspecified,
93 "Attempt to reuse an allocated block");
94 }
95 FreeBlocks[B] = false;
96 }
97
98 DirectoryBlocks = DirBlocks;
99 return Error::success();
100}
101
102Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
104 if (NumBlocks == 0)
105 return Error::success();
106
107 uint32_t NumFreeBlocks = FreeBlocks.count();
108 if (NumFreeBlocks < NumBlocks) {
109 if (!IsGrowable)
110 return make_error<MSFError>(msf_error_code::insufficient_buffer,
111 "There are no free Blocks in the file");
112 uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
113 uint32_t OldBlockCount = FreeBlocks.size();
114 uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
115 uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
116 FreeBlocks.resize(NewBlockCount, true);
117 // If we crossed over an fpm page, we actually need to allocate 2 extra
118 // blocks for each FPM group crossed and mark both blocks from the group as
119 // used. FPM blocks are marked as allocated regardless of whether or not
120 // they ultimately describe the status of blocks in the file. This means
121 // that not only are extraneous blocks at the end of the main FPM marked as
122 // allocated, but also blocks from the alternate FPM are always marked as
123 // allocated.
124 while (NextFpmBlock < NewBlockCount) {
125 NewBlockCount += 2;
126 FreeBlocks.resize(NewBlockCount, true);
127 FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
128 NextFpmBlock += BlockSize;
129 }
130 }
131
132 int I = 0;
133 int Block = FreeBlocks.find_first();
134 do {
135 assert(Block != -1 && "We ran out of Blocks!");
136
137 uint32_t NextBlock = static_cast<uint32_t>(Block);
138 Blocks[I++] = NextBlock;
139 FreeBlocks.reset(NextBlock);
140 Block = FreeBlocks.find_next(Block);
141 } while (--NumBlocks > 0);
142 return Error::success();
143}
144
147}
148
149uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
150
151uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
152
153bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
154
156 ArrayRef<uint32_t> Blocks) {
157 // Add a new stream mapped to the specified blocks. Verify that the specified
158 // blocks are both necessary and sufficient for holding the requested number
159 // of bytes, and verify that all requested blocks are free.
160 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
161 if (ReqBlocks != Blocks.size())
162 return make_error<MSFError>(
164 "Incorrect number of blocks for requested stream size");
165 for (auto Block : Blocks) {
166 if (Block >= FreeBlocks.size())
167 FreeBlocks.resize(Block + 1, true);
168
169 if (!FreeBlocks.test(Block))
170 return make_error<MSFError>(
172 "Attempt to re-use an already allocated block");
173 }
174 // Mark all the blocks occupied by the new stream as not free.
175 for (auto Block : Blocks) {
176 FreeBlocks.reset(Block);
177 }
178 StreamData.push_back(std::make_pair(Size, Blocks));
179 return StreamData.size() - 1;
180}
181
183 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
184 std::vector<uint32_t> NewBlocks;
185 NewBlocks.resize(ReqBlocks);
186 if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
187 return std::move(EC);
188 StreamData.push_back(std::make_pair(Size, NewBlocks));
189 return StreamData.size() - 1;
190}
191
193 uint32_t OldSize = getStreamSize(Idx);
194 if (OldSize == Size)
195 return Error::success();
196
197 uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
198 uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
199
200 if (NewBlocks > OldBlocks) {
201 uint32_t AddedBlocks = NewBlocks - OldBlocks;
202 // If we're growing, we have to allocate new Blocks.
203 std::vector<uint32_t> AddedBlockList;
204 AddedBlockList.resize(AddedBlocks);
205 if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
206 return EC;
207 auto &CurrentBlocks = StreamData[Idx].second;
208 llvm::append_range(CurrentBlocks, AddedBlockList);
209 } else if (OldBlocks > NewBlocks) {
210 // For shrinking, free all the Blocks in the Block map, update the stream
211 // data, then shrink the directory.
212 uint32_t RemovedBlocks = OldBlocks - NewBlocks;
213 auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
214 auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
215 for (auto P : RemovedBlockList)
216 FreeBlocks[P] = true;
217 StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
218 }
219
220 StreamData[Idx].first = Size;
221 return Error::success();
222}
223
224uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
225
227 return StreamData[StreamIdx].first;
228}
229
231 return StreamData[StreamIdx].second;
232}
233
234uint32_t MSFBuilder::computeDirectoryByteSize() const {
235 // The directory has the following layout, where each item is a ulittle32_t:
236 // NumStreams
237 // StreamSizes[NumStreams]
238 // StreamBlocks[NumStreams][]
239 uint32_t Size = sizeof(ulittle32_t); // NumStreams
240 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
241 for (const auto &D : StreamData) {
242 uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
243 assert(ExpectedNumBlocks == D.second.size() &&
244 "Unexpected number of blocks");
245 Size += ExpectedNumBlocks * sizeof(ulittle32_t);
246 }
247 return Size;
248}
249
251 SuperBlock *SB = Allocator.Allocate<SuperBlock>();
252 MSFLayout L;
253 L.SB = SB;
254
255 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
256 SB->BlockMapAddr = BlockMapAddr;
257 SB->BlockSize = BlockSize;
258 SB->NumDirectoryBytes = computeDirectoryByteSize();
259 SB->FreeBlockMapBlock = FreePageMap;
260 SB->Unknown1 = Unknown1;
261
262 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
263 if (NumDirectoryBlocks > DirectoryBlocks.size()) {
264 // Our hint wasn't enough to satisfy the entire directory. Allocate
265 // remaining pages.
266 std::vector<uint32_t> ExtraBlocks;
267 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
268 ExtraBlocks.resize(NumExtraBlocks);
269 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
270 return std::move(EC);
271 llvm::append_range(DirectoryBlocks, ExtraBlocks);
272 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
273 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
274 for (auto B :
275 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
276 FreeBlocks[B] = true;
277 DirectoryBlocks.resize(NumDirectoryBlocks);
278 }
279
280 // Don't set the number of blocks in the file until after allocating Blocks
281 // for the directory, since the allocation might cause the file to need to
282 // grow.
283 SB->NumBlocks = FreeBlocks.size();
284
285 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
286 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
287 DirBlocks);
288 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
289
290 // The stream sizes should be re-allocated as a stable pointer and the stream
291 // map should have each of its entries allocated as a separate stable pointer.
292 if (!StreamData.empty()) {
293 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
294 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
295 L.StreamMap.resize(StreamData.size());
296 for (uint32_t I = 0; I < StreamData.size(); ++I) {
297 Sizes[I] = StreamData[I].first;
298 ulittle32_t *BlockList =
299 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
300 std::uninitialized_copy_n(StreamData[I].second.begin(),
301 StreamData[I].second.size(), BlockList);
302 L.StreamMap[I] =
303 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
304 }
305 }
306
307 L.FreePageMap = FreeBlocks;
308
309 return L;
310}
311
312static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
313 BumpPtrAllocator &Allocator) {
314 auto FpmStream =
316
317 // We only need to create the alt fpm stream so that it gets initialized.
319 true);
320
321 uint32_t BI = 0;
322 BinaryStreamWriter FpmWriter(*FpmStream);
323 while (BI < Layout.SB->NumBlocks) {
324 uint8_t ThisByte = 0;
325 for (uint32_t I = 0; I < 8; ++I) {
326 bool IsFree =
327 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
328 uint8_t Mask = uint8_t(IsFree) << I;
329 ThisByte |= Mask;
330 ++BI;
331 }
332 cantFail(FpmWriter.writeObject(ThisByte));
333 }
334 assert(FpmWriter.bytesRemaining() == 0);
335}
336
338 MSFLayout &Layout) {
340 if (!L)
341 return L.takeError();
342
343 Layout = std::move(*L);
344
345 uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks;
346 // Ensure that the file size is under the limit for the specified block size.
347 if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) {
348 msf_error_code error_code = [](uint32_t BlockSize) {
349 switch (BlockSize) {
350 case 8192:
352 case 16384:
354 case 32768:
356 default:
358 }
359 }(Layout.SB->BlockSize);
360
361 return make_error<MSFError>(
362 error_code,
363 formatv("File size {0,1:N} too large for current PDB page size {1}",
364 FileSize, Layout.SB->BlockSize));
365 }
366
367 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
368 if (auto EC = OutFileOrError.takeError())
369 return std::move(EC);
370
371 FileBufferByteStream Buffer(std::move(*OutFileOrError),
373 BinaryStreamWriter Writer(Buffer);
374
375 if (auto EC = Writer.writeObject(*Layout.SB))
376 return std::move(EC);
377
378 commitFpm(Buffer, Layout, Allocator);
379
380 uint32_t BlockMapOffset =
382 Writer.setOffset(BlockMapOffset);
383 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
384 return std::move(EC);
385
387 Layout, Buffer, Allocator);
388 BinaryStreamWriter DW(*DirStream);
389 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
390 return std::move(EC);
391
392 if (auto EC = DW.writeArray(Layout.StreamSizes))
393 return std::move(EC);
394
395 for (const auto &Blocks : Layout.StreamMap) {
396 if (auto EC = DW.writeArray(Blocks))
397 return std::move(EC);
398 }
399
400 return std::move(Buffer);
401}
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
uint64_t Addr
uint64_t Size
#define I(x, y, z)
Definition: MD5.cpp:58
static const uint32_t kFreePageMap1Block
Definition: MSFBuilder.cpp:33
static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, BumpPtrAllocator &Allocator)
Definition: MSFBuilder.cpp:312
static const uint32_t kSuperBlockBlock
Definition: MSFBuilder.cpp:31
static const uint32_t kFreePageMap0Block
Definition: MSFBuilder.cpp:32
static const uint32_t kDefaultBlockMapAddr
Definition: MSFBuilder.cpp:37
static const uint32_t kNumReservedPages
Definition: MSFBuilder.cpp:34
static const uint32_t kDefaultFreePageMap
Definition: MSFBuilder.cpp:36
#define P(N)
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const int BlockSize
Definition: TarWriter.cpp:33
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
Provides write only access to a subclass of WritableBinaryStream.
Error writeArray(ArrayRef< T > Array)
Writes an array of objects of type T to the underlying stream, as if by using memcpy.
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
uint64_t bytesRemaining() const
void setOffset(uint64_t Off)
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
bool test(unsigned Idx) const
Definition: BitVector.h:454
BitVector & reset()
Definition: BitVector.h:385
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:293
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:155
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:301
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:152
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
static ErrorSuccess success()
Create a success value.
Definition: Error.h:330
Tagged union holding either a T or a Error.
Definition: Error.h:470
Error takeError()
Take ownership of the stored error.
Definition: Error.h:597
An implementation of WritableBinaryStream backed by an llvm FileOutputBuffer.
static Expected< std::unique_ptr< FileOutputBuffer > > create(StringRef FilePath, size_t Size, unsigned Flags=0)
Factory method to create an OutputBuffer object which manages a read/write buffer of the specified si...
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
A BinaryStream which can be read from as well as written to.
Definition: BinaryStream.h:73
uint32_t getNumStreams() const
Get the total number of streams in the MSF layout.
Definition: MSFBuilder.cpp:224
Error setBlockMapAddr(uint32_t Addr)
Request the block map to be at a specific block address.
Definition: MSFBuilder.cpp:62
ArrayRef< uint32_t > getStreamBlocks(uint32_t StreamIdx) const
Get the list of blocks allocated to a particular stream.
Definition: MSFBuilder.cpp:230
Error setDirectoryBlocksHint(ArrayRef< uint32_t > DirBlocks)
Definition: MSFBuilder.cpp:87
uint32_t getTotalBlockCount() const
Get the total number of blocks in the MSF file.
Definition: MSFBuilder.cpp:151
uint32_t getNumFreeBlocks() const
Get the total number of blocks that exist in the MSF file but are not allocated to any valid data.
Definition: MSFBuilder.cpp:149
Error setStreamSize(uint32_t Idx, uint32_t Size)
Update the size of an existing stream.
Definition: MSFBuilder.cpp:192
Expected< FileBufferByteStream > commit(StringRef Path, MSFLayout &Layout)
Write the MSF layout to the underlying file.
Definition: MSFBuilder.cpp:337
Expected< MSFLayout > generateLayout()
Finalize the layout and build the headers and structures that describe the MSF layout and can be writ...
Definition: MSFBuilder.cpp:250
bool isBlockFree(uint32_t Idx) const
Check whether a particular block is allocated or free.
Definition: MSFBuilder.cpp:153
void setFreePageMap(uint32_t Fpm)
Definition: MSFBuilder.cpp:83
uint32_t getStreamSize(uint32_t StreamIdx) const
Get the size of a stream by index.
Definition: MSFBuilder.cpp:226
static Expected< MSFBuilder > create(BumpPtrAllocator &Allocator, uint32_t BlockSize, uint32_t MinBlockCount=0, bool CanGrow=true)
Create a new MSFBuilder.
Definition: MSFBuilder.cpp:50
uint32_t getNumUsedBlocks() const
Get the total number of blocks that will be allocated to actual data in this MSF file.
Definition: MSFBuilder.cpp:145
void setUnknown1(uint32_t Unk1)
Definition: MSFBuilder.cpp:85
Expected< uint32_t > addStream(uint32_t Size, ArrayRef< uint32_t > Blocks)
Add a stream to the MSF file with the given size, occupying the given list of blocks.
Definition: MSFBuilder.cpp:155
static std::unique_ptr< WritableMappedBlockStream > createFpmStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator, bool AltFpm=false)
static std::unique_ptr< WritableMappedBlockStream > createDirectoryStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
uint32_t getMinimumBlockCount()
Definition: MSFCommon.h:125
uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize)
Definition: MSFCommon.h:135
uint64_t getMaxFileSizeFromBlockSize(uint32_t Size)
Given the specified block size, returns the maximum possible file size.
Definition: MSFCommon.h:111
bool isValidBlockSize(uint32_t Size)
Definition: MSFCommon.h:90
msf_error_code
Definition: MSFError.h:16
uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize)
Definition: MSFCommon.h:131
static const char Magic[]
Definition: MSFCommon.h:23
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:272
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:745
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
ArrayRef< support::ulittle32_t > StreamSizes
Definition: MSFCommon.h:67
ArrayRef< support::ulittle32_t > DirectoryBlocks
Definition: MSFCommon.h:66
const SuperBlock * SB
Definition: MSFCommon.h:64
BitVector FreePageMap
Definition: MSFCommon.h:65
std::vector< ArrayRef< support::ulittle32_t > > StreamMap
Definition: MSFCommon.h:68
support::ulittle32_t NumBlocks
Definition: MSFCommon.h:42
support::ulittle32_t BlockSize
Definition: MSFCommon.h:36
support::ulittle32_t Unknown1
Definition: MSFCommon.h:46
char MagicBytes[sizeof(Magic)]
Definition: MSFCommon.h:32
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:44
support::ulittle32_t BlockMapAddr
Definition: MSFCommon.h:48
support::ulittle32_t FreeBlockMapBlock
Definition: MSFCommon.h:38