LLVM  8.0.0svn
MSFBuilder.cpp
Go to the documentation of this file.
1 //===- MSFBuilder.cpp -----------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/Support/Endian.h"
17 #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 
27 using namespace llvm;
28 using namespace llvm::msf;
29 using namespace llvm::support;
30 
31 static const uint32_t kSuperBlockBlock = 0;
32 static const uint32_t kFreePageMap0Block = 1;
33 static const uint32_t kFreePageMap1Block = 2;
34 static const uint32_t kNumReservedPages = 3;
35 
38 
39 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
41  : Allocator(Allocator), IsGrowable(CanGrow),
42  FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
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 
83 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
84 
85 void 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 
102 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
103  MutableArrayRef<uint32_t> Blocks) {
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 
149 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
150 
151 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
152 
153 bool 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  CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
209  AddedBlockList.end());
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(NewBlocks);
216  for (auto P : RemovedBlockList)
217  FreeBlocks[P] = true;
218  StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
219  }
220 
221  StreamData[Idx].first = Size;
222  return Error::success();
223 }
224 
225 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
226 
228  return StreamData[StreamIdx].first;
229 }
230 
232  return StreamData[StreamIdx].second;
233 }
234 
235 uint32_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(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 
252  SuperBlock *SB = Allocator.Allocate<SuperBlock>();
253  MSFLayout L;
254  L.SB = SB;
255 
256  std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
257  SB->BlockMapAddr = BlockMapAddr;
258  SB->BlockSize = BlockSize;
259  SB->NumDirectoryBytes = computeDirectoryByteSize();
260  SB->FreeBlockMapBlock = FreePageMap;
261  SB->Unknown1 = Unknown1;
262 
263  uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
264  if (NumDirectoryBlocks > DirectoryBlocks.size()) {
265  // Our hint wasn't enough to satisfy the entire directory. Allocate
266  // remaining pages.
267  std::vector<uint32_t> ExtraBlocks;
268  uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
269  ExtraBlocks.resize(NumExtraBlocks);
270  if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
271  return std::move(EC);
272  DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
273  ExtraBlocks.end());
274  } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
275  uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
276  for (auto B :
277  ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
278  FreeBlocks[B] = true;
279  DirectoryBlocks.resize(NumDirectoryBlocks);
280  }
281 
282  // Don't set the number of blocks in the file until after allocating Blocks
283  // for the directory, since the allocation might cause the file to need to
284  // grow.
285  SB->NumBlocks = FreeBlocks.size();
286 
287  ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
288  std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
289  DirBlocks);
290  L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
291 
292  // The stream sizes should be re-allocated as a stable pointer and the stream
293  // map should have each of its entries allocated as a separate stable pointer.
294  if (!StreamData.empty()) {
295  ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
296  L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
297  L.StreamMap.resize(StreamData.size());
298  for (uint32_t I = 0; I < StreamData.size(); ++I) {
299  Sizes[I] = StreamData[I].first;
300  ulittle32_t *BlockList =
301  Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
302  std::uninitialized_copy_n(StreamData[I].second.begin(),
303  StreamData[I].second.size(), BlockList);
304  L.StreamMap[I] =
305  ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
306  }
307  }
308 
309  L.FreePageMap = FreeBlocks;
310 
311  return L;
312 }
313 
314 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
315  BumpPtrAllocator &Allocator) {
316  auto FpmStream =
317  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
318 
319  // We only need to create the alt fpm stream so that it gets initialized.
320  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
321  true);
322 
323  uint32_t BI = 0;
324  BinaryStreamWriter FpmWriter(*FpmStream);
325  while (BI < Layout.SB->NumBlocks) {
326  uint8_t ThisByte = 0;
327  for (uint32_t I = 0; I < 8; ++I) {
328  bool IsFree =
329  (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
330  uint8_t Mask = uint8_t(IsFree) << I;
331  ThisByte |= Mask;
332  ++BI;
333  }
334  cantFail(FpmWriter.writeObject(ThisByte));
335  }
336  assert(FpmWriter.bytesRemaining() == 0);
337 }
338 
340  MSFLayout &Layout) {
342  if (!L)
343  return L.takeError();
344 
345  Layout = std::move(*L);
346 
347  uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
348  auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
349  if (auto EC = OutFileOrError.takeError())
350  return std::move(EC);
351 
352  FileBufferByteStream Buffer(std::move(*OutFileOrError),
354  BinaryStreamWriter Writer(Buffer);
355 
356  if (auto EC = Writer.writeObject(*Layout.SB))
357  return std::move(EC);
358 
359  commitFpm(Buffer, Layout, Allocator);
360 
361  uint32_t BlockMapOffset =
362  msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
363  Writer.setOffset(BlockMapOffset);
364  if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
365  return std::move(EC);
366 
368  Layout, Buffer, Allocator);
369  BinaryStreamWriter DW(*DirStream);
370  if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
371  return std::move(EC);
372 
373  if (auto EC = DW.writeArray(Layout.StreamSizes))
374  return std::move(EC);
375 
376  for (const auto &Blocks : Layout.StreamMap) {
377  if (auto EC = DW.writeArray(Blocks))
378  return std::move(EC);
379  }
380 
381  return std::move(Buffer);
382 }
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:372
char MagicBytes[sizeof(Magic)]
Definition: MSFCommon.h:33
void setFreePageMap(uint32_t Fpm)
Definition: MSFBuilder.cpp:83
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:704
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:24
static const uint32_t kFreePageMap0Block
Definition: MSFBuilder.cpp:32
Error setBlockMapAddr(uint32_t Addr)
Request the block map to be at a specific block address.
Definition: MSFBuilder.cpp:62
uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize)
Definition: MSFCommon.h:113
bool test(unsigned Idx) const
Definition: BitVector.h:502
uint32_t getMinimumBlockCount()
Definition: MSFCommon.h:103
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:685
block Block Frequency true
Error takeError()
Take ownership of the stored error.
Definition: Error.h:553
Expected< MSFLayout > generateLayout()
Finalize the layout and build the headers and structures that describe the MSF layout and can be writ...
Definition: MSFBuilder.cpp:251
static const uint32_t kNumReservedPages
Definition: MSFBuilder.cpp:34
static const uint32_t kDefaultFreePageMap
Definition: MSFBuilder.cpp:36
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:332
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:340
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
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
static const uint32_t kSuperBlockBlock
Definition: MSFBuilder.cpp:31
Error setDirectoryBlocksHint(ArrayRef< uint32_t > DirBlocks)
Definition: MSFBuilder.cpp:87
support::ulittle32_t BlockSize
Definition: MSFCommon.h:37
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:314
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
support::ulittle32_t BlockMapAddr
Definition: MSFCommon.h:49
#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:291
uint32_t getTotalBlockCount() const
Get the total number of blocks in the MSF file.
Definition: MSFBuilder.cpp:151
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:271
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
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:215
bool isBlockFree(uint32_t Idx) const
Check whether a particular block is allocated or free.
Definition: MSFBuilder.cpp:153
BitVector & reset()
Definition: BitVector.h:439
Provides write only access to a subclass of WritableBinaryStream.
static const char Magic[]
Definition: MSFCommon.h:24
Error writeInteger(T Value)
Write the integer Value to the underlying stream in the specified endianness.
support::ulittle32_t Unknown1
Definition: MSFCommon.h:47
uint32_t getStreamSize(uint32_t StreamIdx) const
Get the size of a stream by index.
Definition: MSFBuilder.cpp:227
uint32_t bytesRemaining() const
Error setStreamSize(uint32_t Idx, uint32_t Size)
Update the size of an existing stream.
Definition: MSFBuilder.cpp:192
static const int BlockSize
Definition: TarWriter.cpp:34
static const uint32_t kDefaultBlockMapAddr
Definition: MSFBuilder.cpp:37
Basic Register Allocator
static ErrorSuccess success()
Create a success value.
Definition: Error.h:327
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:173
ArrayRef< support::ulittle32_t > DirectoryBlocks
Definition: MSFCommon.h:67
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:155
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:339
BitVector FreePageMap
Definition: MSFCommon.h:66
void setOffset(uint32_t Off)
uint32_t getNumStreams() const
Get the total number of streams in the MSF layout.
Definition: MSFBuilder.cpp:225
uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize)
Definition: MSFCommon.h:109
static const uint32_t kFreePageMap1Block
Definition: MSFBuilder.cpp:33
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:188
#define I(x, y, z)
Definition: MD5.cpp:58
void setUnknown1(uint32_t Unk1)
Definition: MSFBuilder.cpp:85
uint32_t Size
Definition: Profile.cpp:47
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:170
std::vector< ArrayRef< support::ulittle32_t > > StreamMap
Definition: MSFCommon.h:69
ArrayRef< uint32_t > getStreamBlocks(uint32_t StreamIdx) const
Get the list of blocks allocated to a particular stream.
Definition: MSFBuilder.cpp:231
ArrayRef< support::ulittle32_t > StreamSizes
Definition: MSFCommon.h:68
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
support::ulittle32_t FreeBlockMapBlock
Definition: MSFCommon.h:39
Lightweight error class with error context and mandatory checking.
Definition: Error.h:158
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:81
bool isValidBlockSize(uint32_t Size)
Definition: MSFCommon.h:91
An implementation of WritableBinaryStream backed by an llvm FileOutputBuffer.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const SuperBlock * SB
Definition: MSFCommon.h:65
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:45
support::ulittle32_t NumBlocks
Definition: MSFCommon.h:43
A BinaryStream which can be read from as well as written to.
Definition: BinaryStream.h:74