LLVM  7.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 
10 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/Support/Endian.h"
14 #include "llvm/Support/Error.h"
15 #include <algorithm>
16 #include <cassert>
17 #include <cstdint>
18 #include <cstring>
19 #include <memory>
20 #include <utility>
21 #include <vector>
22 
23 using namespace llvm;
24 using namespace llvm::msf;
25 using namespace llvm::support;
26 
27 static const uint32_t kSuperBlockBlock = 0;
28 static const uint32_t kFreePageMap0Block = 1;
29 static const uint32_t kFreePageMap1Block = 2;
30 static const uint32_t kNumReservedPages = 3;
31 
34 
35 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
37  : Allocator(Allocator), IsGrowable(CanGrow),
38  FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
39  BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
40  FreeBlocks[kSuperBlockBlock] = false;
41  FreeBlocks[kFreePageMap0Block] = false;
42  FreeBlocks[kFreePageMap1Block] = false;
43  FreeBlocks[BlockMapAddr] = false;
44 }
45 
48  uint32_t MinBlockCount, bool CanGrow) {
49  if (!isValidBlockSize(BlockSize))
50  return make_error<MSFError>(msf_error_code::invalid_format,
51  "The requested block size is unsupported");
52 
53  return MSFBuilder(BlockSize,
54  std::max(MinBlockCount, msf::getMinimumBlockCount()),
55  CanGrow, Allocator);
56 }
57 
59  if (Addr == BlockMapAddr)
60  return Error::success();
61 
62  if (Addr >= FreeBlocks.size()) {
63  if (!IsGrowable)
64  return make_error<MSFError>(msf_error_code::insufficient_buffer,
65  "Cannot grow the number of blocks");
66  FreeBlocks.resize(Addr + 1, true);
67  }
68 
69  if (!isBlockFree(Addr))
70  return make_error<MSFError>(
72  "Requested block map address is already in use");
73  FreeBlocks[BlockMapAddr] = true;
74  FreeBlocks[Addr] = false;
75  BlockMapAddr = Addr;
76  return Error::success();
77 }
78 
79 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
80 
81 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
82 
84  for (auto B : DirectoryBlocks)
85  FreeBlocks[B] = true;
86  for (auto B : DirBlocks) {
87  if (!isBlockFree(B)) {
88  return make_error<MSFError>(msf_error_code::unspecified,
89  "Attempt to reuse an allocated block");
90  }
91  FreeBlocks[B] = false;
92  }
93 
94  DirectoryBlocks = DirBlocks;
95  return Error::success();
96 }
97 
98 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
100  if (NumBlocks == 0)
101  return Error::success();
102 
103  uint32_t NumFreeBlocks = FreeBlocks.count();
104  if (NumFreeBlocks < NumBlocks) {
105  if (!IsGrowable)
106  return make_error<MSFError>(msf_error_code::insufficient_buffer,
107  "There are no free Blocks in the file");
108  uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
109  uint32_t OldBlockCount = FreeBlocks.size();
110  uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
111  uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
112  FreeBlocks.resize(NewBlockCount, true);
113  // If we crossed over an fpm page, we actually need to allocate 2 extra
114  // blocks for each FPM group crossed and mark both blocks from the group as
115  // used. FPM blocks are marked as allocated regardless of whether or not
116  // they ultimately describe the status of blocks in the file. This means
117  // that not only are extraneous blocks at the end of the main FPM marked as
118  // allocated, but also blocks from the alternate FPM are always marked as
119  // allocated.
120  while (NextFpmBlock < NewBlockCount) {
121  NewBlockCount += 2;
122  FreeBlocks.resize(NewBlockCount, true);
123  FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
124  NextFpmBlock += BlockSize;
125  }
126  }
127 
128  int I = 0;
129  int Block = FreeBlocks.find_first();
130  do {
131  assert(Block != -1 && "We ran out of Blocks!");
132 
133  uint32_t NextBlock = static_cast<uint32_t>(Block);
134  Blocks[I++] = NextBlock;
135  FreeBlocks.reset(NextBlock);
136  Block = FreeBlocks.find_next(Block);
137  } while (--NumBlocks > 0);
138  return Error::success();
139 }
140 
143 }
144 
145 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
146 
147 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
148 
149 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
150 
152  ArrayRef<uint32_t> Blocks) {
153  // Add a new stream mapped to the specified blocks. Verify that the specified
154  // blocks are both necessary and sufficient for holding the requested number
155  // of bytes, and verify that all requested blocks are free.
156  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
157  if (ReqBlocks != Blocks.size())
158  return make_error<MSFError>(
160  "Incorrect number of blocks for requested stream size");
161  for (auto Block : Blocks) {
162  if (Block >= FreeBlocks.size())
163  FreeBlocks.resize(Block + 1, true);
164 
165  if (!FreeBlocks.test(Block))
166  return make_error<MSFError>(
168  "Attempt to re-use an already allocated block");
169  }
170  // Mark all the blocks occupied by the new stream as not free.
171  for (auto Block : Blocks) {
172  FreeBlocks.reset(Block);
173  }
174  StreamData.push_back(std::make_pair(Size, Blocks));
175  return StreamData.size() - 1;
176 }
177 
179  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
180  std::vector<uint32_t> NewBlocks;
181  NewBlocks.resize(ReqBlocks);
182  if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
183  return std::move(EC);
184  StreamData.push_back(std::make_pair(Size, NewBlocks));
185  return StreamData.size() - 1;
186 }
187 
189  uint32_t OldSize = getStreamSize(Idx);
190  if (OldSize == Size)
191  return Error::success();
192 
193  uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
194  uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
195 
196  if (NewBlocks > OldBlocks) {
197  uint32_t AddedBlocks = NewBlocks - OldBlocks;
198  // If we're growing, we have to allocate new Blocks.
199  std::vector<uint32_t> AddedBlockList;
200  AddedBlockList.resize(AddedBlocks);
201  if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
202  return EC;
203  auto &CurrentBlocks = StreamData[Idx].second;
204  CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
205  AddedBlockList.end());
206  } else if (OldBlocks > NewBlocks) {
207  // For shrinking, free all the Blocks in the Block map, update the stream
208  // data, then shrink the directory.
209  uint32_t RemovedBlocks = OldBlocks - NewBlocks;
210  auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
211  auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
212  for (auto P : RemovedBlockList)
213  FreeBlocks[P] = true;
214  StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
215  }
216 
217  StreamData[Idx].first = Size;
218  return Error::success();
219 }
220 
221 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
222 
224  return StreamData[StreamIdx].first;
225 }
226 
228  return StreamData[StreamIdx].second;
229 }
230 
231 uint32_t MSFBuilder::computeDirectoryByteSize() const {
232  // The directory has the following layout, where each item is a ulittle32_t:
233  // NumStreams
234  // StreamSizes[NumStreams]
235  // StreamBlocks[NumStreams][]
236  uint32_t Size = sizeof(ulittle32_t); // NumStreams
237  Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
238  for (const auto &D : StreamData) {
239  uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
240  assert(ExpectedNumBlocks == D.second.size() &&
241  "Unexpected number of blocks");
242  Size += ExpectedNumBlocks * sizeof(ulittle32_t);
243  }
244  return Size;
245 }
246 
248  SuperBlock *SB = Allocator.Allocate<SuperBlock>();
249  MSFLayout L;
250  L.SB = SB;
251 
252  std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
253  SB->BlockMapAddr = BlockMapAddr;
254  SB->BlockSize = BlockSize;
255  SB->NumDirectoryBytes = computeDirectoryByteSize();
256  SB->FreeBlockMapBlock = FreePageMap;
257  SB->Unknown1 = Unknown1;
258 
259  uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
260  if (NumDirectoryBlocks > DirectoryBlocks.size()) {
261  // Our hint wasn't enough to satisfy the entire directory. Allocate
262  // remaining pages.
263  std::vector<uint32_t> ExtraBlocks;
264  uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
265  ExtraBlocks.resize(NumExtraBlocks);
266  if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
267  return std::move(EC);
268  DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
269  ExtraBlocks.end());
270  } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
271  uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
272  for (auto B :
273  ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
274  FreeBlocks[B] = true;
275  DirectoryBlocks.resize(NumDirectoryBlocks);
276  }
277 
278  // Don't set the number of blocks in the file until after allocating Blocks
279  // for the directory, since the allocation might cause the file to need to
280  // grow.
281  SB->NumBlocks = FreeBlocks.size();
282 
283  ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
284  std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
285  DirBlocks);
286  L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
287 
288  // The stream sizes should be re-allocated as a stable pointer and the stream
289  // map should have each of its entries allocated as a separate stable pointer.
290  if (!StreamData.empty()) {
291  ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
292  L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
293  L.StreamMap.resize(StreamData.size());
294  for (uint32_t I = 0; I < StreamData.size(); ++I) {
295  Sizes[I] = StreamData[I].first;
296  ulittle32_t *BlockList =
297  Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
298  std::uninitialized_copy_n(StreamData[I].second.begin(),
299  StreamData[I].second.size(), BlockList);
300  L.StreamMap[I] =
301  ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
302  }
303  }
304 
305  L.FreePageMap = FreeBlocks;
306 
307  return L;
308 }
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:79
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static const uint32_t kFreePageMap0Block
Definition: MSFBuilder.cpp:28
Error setBlockMapAddr(uint32_t Addr)
Request the block map to be at a specific block address.
Definition: MSFBuilder.cpp:58
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:677
static const uint32_t kNumReservedPages
Definition: MSFBuilder.cpp:30
static const uint32_t kDefaultFreePageMap
Definition: MSFBuilder.cpp:32
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:145
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
static const uint32_t kSuperBlockBlock
Definition: MSFBuilder.cpp:27
Error setDirectoryBlocksHint(ArrayRef< uint32_t > DirBlocks)
Definition: MSFBuilder.cpp:83
support::ulittle32_t BlockSize
Definition: MSFCommon.h:37
uint32_t getNumUsedBlocks() const
Get the total number of blocks that will be allocated to actual data in this MSF file.
Definition: MSFBuilder.cpp:141
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:147
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:140
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:214
bool isBlockFree(uint32_t Idx) const
Check whether a particular block is allocated or free.
Definition: MSFBuilder.cpp:149
BitVector & reset()
Definition: BitVector.h:439
static const char Magic[]
Definition: MSFCommon.h:24
Expected< MSFLayout > build()
Finalize the layout and build the headers and structures that describe the MSF layout and can be writ...
Definition: MSFBuilder.cpp:247
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:223
Error setStreamSize(uint32_t Idx, uint32_t Size)
Update the size of an existing stream.
Definition: MSFBuilder.cpp:188
static const int BlockSize
Definition: TarWriter.cpp:34
static const uint32_t kDefaultBlockMapAddr
Definition: MSFBuilder.cpp:33
Basic Register Allocator
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:173
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:151
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Basic Alias true
uint32_t getNumStreams() const
Get the total number of streams in the MSF layout.
Definition: MSFBuilder.cpp:221
uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize)
Definition: MSFCommon.h:109
static const uint32_t kFreePageMap1Block
Definition: MSFBuilder.cpp:29
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:81
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:170
ArrayRef< uint32_t > getStreamBlocks(uint32_t StreamIdx) const
Get the list of blocks allocated to a particular stream.
Definition: MSFBuilder.cpp:227
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
support::ulittle32_t FreeBlockMapBlock
Definition: MSFCommon.h:39
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
bool isValidBlockSize(uint32_t Size)
Definition: MSFCommon.h:91
const SuperBlock * SB
Definition: MSFCommon.h:65
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:45
support::ulittle32_t NumBlocks
Definition: MSFCommon.h:43