LLVM  9.0.0svn
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"
18 #include <algorithm>
19 #include <cassert>
20 #include <cstdint>
21 #include <cstring>
22 #include <memory>
23 #include <utility>
24 #include <vector>
25 
26 using namespace llvm;
27 using namespace llvm::msf;
28 using namespace llvm::support;
29 
30 static const uint32_t kSuperBlockBlock = 0;
31 static const uint32_t kFreePageMap0Block = 1;
32 static const uint32_t kFreePageMap1Block = 2;
33 static const uint32_t kNumReservedPages = 3;
34 
37 
38 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
40  : Allocator(Allocator), IsGrowable(CanGrow),
41  FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
42  BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
43  FreeBlocks[kSuperBlockBlock] = false;
44  FreeBlocks[kFreePageMap0Block] = false;
45  FreeBlocks[kFreePageMap1Block] = false;
46  FreeBlocks[BlockMapAddr] = false;
47 }
48 
51  uint32_t MinBlockCount, bool CanGrow) {
52  if (!isValidBlockSize(BlockSize))
53  return make_error<MSFError>(msf_error_code::invalid_format,
54  "The requested block size is unsupported");
55 
56  return MSFBuilder(BlockSize,
57  std::max(MinBlockCount, msf::getMinimumBlockCount()),
58  CanGrow, Allocator);
59 }
60 
62  if (Addr == BlockMapAddr)
63  return Error::success();
64 
65  if (Addr >= FreeBlocks.size()) {
66  if (!IsGrowable)
67  return make_error<MSFError>(msf_error_code::insufficient_buffer,
68  "Cannot grow the number of blocks");
69  FreeBlocks.resize(Addr + 1, true);
70  }
71 
72  if (!isBlockFree(Addr))
73  return make_error<MSFError>(
75  "Requested block map address is already in use");
76  FreeBlocks[BlockMapAddr] = true;
77  FreeBlocks[Addr] = false;
78  BlockMapAddr = Addr;
79  return Error::success();
80 }
81 
82 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
83 
84 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
85 
87  for (auto B : DirectoryBlocks)
88  FreeBlocks[B] = true;
89  for (auto B : DirBlocks) {
90  if (!isBlockFree(B)) {
91  return make_error<MSFError>(msf_error_code::unspecified,
92  "Attempt to reuse an allocated block");
93  }
94  FreeBlocks[B] = false;
95  }
96 
97  DirectoryBlocks = DirBlocks;
98  return Error::success();
99 }
100 
101 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
102  MutableArrayRef<uint32_t> Blocks) {
103  if (NumBlocks == 0)
104  return Error::success();
105 
106  uint32_t NumFreeBlocks = FreeBlocks.count();
107  if (NumFreeBlocks < NumBlocks) {
108  if (!IsGrowable)
109  return make_error<MSFError>(msf_error_code::insufficient_buffer,
110  "There are no free Blocks in the file");
111  uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
112  uint32_t OldBlockCount = FreeBlocks.size();
113  uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
114  uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
115  FreeBlocks.resize(NewBlockCount, true);
116  // If we crossed over an fpm page, we actually need to allocate 2 extra
117  // blocks for each FPM group crossed and mark both blocks from the group as
118  // used. FPM blocks are marked as allocated regardless of whether or not
119  // they ultimately describe the status of blocks in the file. This means
120  // that not only are extraneous blocks at the end of the main FPM marked as
121  // allocated, but also blocks from the alternate FPM are always marked as
122  // allocated.
123  while (NextFpmBlock < NewBlockCount) {
124  NewBlockCount += 2;
125  FreeBlocks.resize(NewBlockCount, true);
126  FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
127  NextFpmBlock += BlockSize;
128  }
129  }
130 
131  int I = 0;
132  int Block = FreeBlocks.find_first();
133  do {
134  assert(Block != -1 && "We ran out of Blocks!");
135 
136  uint32_t NextBlock = static_cast<uint32_t>(Block);
137  Blocks[I++] = NextBlock;
138  FreeBlocks.reset(NextBlock);
139  Block = FreeBlocks.find_next(Block);
140  } while (--NumBlocks > 0);
141  return Error::success();
142 }
143 
146 }
147 
148 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
149 
150 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
151 
152 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
153 
155  ArrayRef<uint32_t> Blocks) {
156  // Add a new stream mapped to the specified blocks. Verify that the specified
157  // blocks are both necessary and sufficient for holding the requested number
158  // of bytes, and verify that all requested blocks are free.
159  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
160  if (ReqBlocks != Blocks.size())
161  return make_error<MSFError>(
163  "Incorrect number of blocks for requested stream size");
164  for (auto Block : Blocks) {
165  if (Block >= FreeBlocks.size())
166  FreeBlocks.resize(Block + 1, true);
167 
168  if (!FreeBlocks.test(Block))
169  return make_error<MSFError>(
171  "Attempt to re-use an already allocated block");
172  }
173  // Mark all the blocks occupied by the new stream as not free.
174  for (auto Block : Blocks) {
175  FreeBlocks.reset(Block);
176  }
177  StreamData.push_back(std::make_pair(Size, Blocks));
178  return StreamData.size() - 1;
179 }
180 
182  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
183  std::vector<uint32_t> NewBlocks;
184  NewBlocks.resize(ReqBlocks);
185  if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
186  return std::move(EC);
187  StreamData.push_back(std::make_pair(Size, NewBlocks));
188  return StreamData.size() - 1;
189 }
190 
192  uint32_t OldSize = getStreamSize(Idx);
193  if (OldSize == Size)
194  return Error::success();
195 
196  uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
197  uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
198 
199  if (NewBlocks > OldBlocks) {
200  uint32_t AddedBlocks = NewBlocks - OldBlocks;
201  // If we're growing, we have to allocate new Blocks.
202  std::vector<uint32_t> AddedBlockList;
203  AddedBlockList.resize(AddedBlocks);
204  if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
205  return EC;
206  auto &CurrentBlocks = StreamData[Idx].second;
207  CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
208  AddedBlockList.end());
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 
224 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
225 
227  return StreamData[StreamIdx].first;
228 }
229 
231  return StreamData[StreamIdx].second;
232 }
233 
234 uint32_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  DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
272  ExtraBlocks.end());
273  } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
274  uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
275  for (auto B :
276  ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
277  FreeBlocks[B] = true;
278  DirectoryBlocks.resize(NumDirectoryBlocks);
279  }
280 
281  // Don't set the number of blocks in the file until after allocating Blocks
282  // for the directory, since the allocation might cause the file to need to
283  // grow.
284  SB->NumBlocks = FreeBlocks.size();
285 
286  ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
287  std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
288  DirBlocks);
289  L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
290 
291  // The stream sizes should be re-allocated as a stable pointer and the stream
292  // map should have each of its entries allocated as a separate stable pointer.
293  if (!StreamData.empty()) {
294  ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
295  L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
296  L.StreamMap.resize(StreamData.size());
297  for (uint32_t I = 0; I < StreamData.size(); ++I) {
298  Sizes[I] = StreamData[I].first;
299  ulittle32_t *BlockList =
300  Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
301  std::uninitialized_copy_n(StreamData[I].second.begin(),
302  StreamData[I].second.size(), BlockList);
303  L.StreamMap[I] =
304  ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
305  }
306  }
307 
308  L.FreePageMap = FreeBlocks;
309 
310  return L;
311 }
312 
313 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
314  BumpPtrAllocator &Allocator) {
315  auto FpmStream =
316  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
317 
318  // We only need to create the alt fpm stream so that it gets initialized.
319  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
320  true);
321 
322  uint32_t BI = 0;
323  BinaryStreamWriter FpmWriter(*FpmStream);
324  while (BI < Layout.SB->NumBlocks) {
325  uint8_t ThisByte = 0;
326  for (uint32_t I = 0; I < 8; ++I) {
327  bool IsFree =
328  (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
329  uint8_t Mask = uint8_t(IsFree) << I;
330  ThisByte |= Mask;
331  ++BI;
332  }
333  cantFail(FpmWriter.writeObject(ThisByte));
334  }
335  assert(FpmWriter.bytesRemaining() == 0);
336 }
337 
339  MSFLayout &Layout) {
341  if (!L)
342  return L.takeError();
343 
344  Layout = std::move(*L);
345 
346  uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
347  auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
348  if (auto EC = OutFileOrError.takeError())
349  return std::move(EC);
350 
351  FileBufferByteStream Buffer(std::move(*OutFileOrError),
353  BinaryStreamWriter Writer(Buffer);
354 
355  if (auto EC = Writer.writeObject(*Layout.SB))
356  return std::move(EC);
357 
358  commitFpm(Buffer, Layout, Allocator);
359 
360  uint32_t BlockMapOffset =
361  msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
362  Writer.setOffset(BlockMapOffset);
363  if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
364  return std::move(EC);
365 
367  Layout, Buffer, Allocator);
368  BinaryStreamWriter DW(*DirStream);
369  if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
370  return std::move(EC);
371 
372  if (auto EC = DW.writeArray(Layout.StreamSizes))
373  return std::move(EC);
374 
375  for (const auto &Blocks : Layout.StreamMap) {
376  if (auto EC = DW.writeArray(Blocks))
377  return std::move(EC);
378  }
379 
380  return std::move(Buffer);
381 }
Error writeObject(const T &Obj)
Writes the object Obj to the underlying stream, as if by using memcpy.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:371
char MagicBytes[sizeof(Magic)]
Definition: MSFCommon.h:32
void setFreePageMap(uint32_t Fpm)
Definition: MSFBuilder.cpp:82
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:703
static std::unique_ptr< WritableMappedBlockStream > createDirectoryStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static const uint32_t kFreePageMap0Block
Definition: MSFBuilder.cpp:31
Error setBlockMapAddr(uint32_t Addr)
Request the block map to be at a specific block address.
Definition: MSFBuilder.cpp:61
uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize)
Definition: MSFCommon.h:112
bool test(unsigned Idx) const
Definition: BitVector.h:501
uint32_t getMinimumBlockCount()
Definition: MSFCommon.h:102
unsigned second
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:684
block Block Frequency true
Error takeError()
Take ownership of the stored error.
Definition: Error.h:552
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
static const uint32_t kNumReservedPages
Definition: MSFBuilder.cpp:33
static const uint32_t kDefaultFreePageMap
Definition: MSFBuilder.cpp:35
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:331
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:339
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:148
Tagged union holding either a T or a Error.
Definition: CachePruning.h:22
static const uint32_t kSuperBlockBlock
Definition: MSFBuilder.cpp:30
Error setDirectoryBlocksHint(ArrayRef< uint32_t > DirBlocks)
Definition: MSFBuilder.cpp:86
support::ulittle32_t BlockSize
Definition: MSFCommon.h:36
Error writeArray(ArrayRef< T > Array)
Writes an array of objects of type T to the underlying stream, as if by using memcpy.
static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, BumpPtrAllocator &Allocator)
Definition: MSFBuilder.cpp:313
uint32_t getNumUsedBlocks() const
Get the total number of blocks that will be allocated to actual data in this MSF file.
Definition: MSFBuilder.cpp:144
support::ulittle32_t BlockMapAddr
Definition: MSFCommon.h:48
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:290
uint32_t getTotalBlockCount() const
Get the total number of blocks in the MSF file.
Definition: MSFBuilder.cpp:150
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:274
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:214
bool isBlockFree(uint32_t Idx) const
Check whether a particular block is allocated or free.
Definition: MSFBuilder.cpp:152
BitVector & reset()
Definition: BitVector.h:438
Provides write only access to a subclass of WritableBinaryStream.
static const char Magic[]
Definition: MSFCommon.h:23
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
support::ulittle32_t Unknown1
Definition: MSFCommon.h:46
uint32_t getStreamSize(uint32_t StreamIdx) const
Get the size of a stream by index.
Definition: MSFBuilder.cpp:226
uint32_t bytesRemaining() const
Error setStreamSize(uint32_t Idx, uint32_t Size)
Update the size of an existing stream.
Definition: MSFBuilder.cpp:191
static const int BlockSize
Definition: TarWriter.cpp:33
static const uint32_t kDefaultBlockMapAddr
Definition: MSFBuilder.cpp:36
Basic Register Allocator
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:172
ArrayRef< support::ulittle32_t > DirectoryBlocks
Definition: MSFCommon.h:66
static std::unique_ptr< WritableMappedBlockStream > createFpmStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator, bool AltFpm=false)
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:154
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Expected< FileBufferByteStream > commit(StringRef Path, MSFLayout &Layout)
Write the MSF layout to the underlying file.
Definition: MSFBuilder.cpp:338
BitVector FreePageMap
Definition: MSFCommon.h:65
void setOffset(uint32_t Off)
uint32_t getNumStreams() const
Get the total number of streams in the MSF layout.
Definition: MSFBuilder.cpp:224
uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize)
Definition: MSFCommon.h:108
static const uint32_t kFreePageMap1Block
Definition: MSFBuilder.cpp:32
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:187
#define I(x, y, z)
Definition: MD5.cpp:58
void setUnknown1(uint32_t Unk1)
Definition: MSFBuilder.cpp:84
uint32_t Size
Definition: Profile.cpp:46
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:169
std::vector< ArrayRef< support::ulittle32_t > > StreamMap
Definition: MSFCommon.h:68
ArrayRef< uint32_t > getStreamBlocks(uint32_t StreamIdx) const
Get the list of blocks allocated to a particular stream.
Definition: MSFBuilder.cpp:230
ArrayRef< support::ulittle32_t > StreamSizes
Definition: MSFCommon.h:67
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
support::ulittle32_t FreeBlockMapBlock
Definition: MSFCommon.h:38
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
bool isValidBlockSize(uint32_t Size)
Definition: MSFCommon.h:90
An implementation of WritableBinaryStream backed by an llvm FileOutputBuffer.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const SuperBlock * SB
Definition: MSFCommon.h:64
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:44
support::ulittle32_t NumBlocks
Definition: MSFCommon.h:42
A BinaryStream which can be read from as well as written to.
Definition: BinaryStream.h:73