LLVM  6.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. We may not actually use them since there are many more FPM blocks
116  // present than are required to represent all blocks in a given PDB, but we
117  // need to make sure they aren't allocated to a stream or something else.
118  // At the end when committing the PDB, we'll go through and mark the
119  // extraneous ones unused.
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  BitVector &Fpm) {
249  if (FpmBlocks.empty() || FpmBlocks.front() != B) {
250  Fpm.set(B);
251  return;
252  }
253 
254  // If the next block in the actual layout is this block, it should *not* be
255  // free.
256  assert(!Fpm.test(B));
257  FpmBlocks = FpmBlocks.drop_front();
258 }
259 
261  SuperBlock *SB = Allocator.Allocate<SuperBlock>();
262  MSFLayout L;
263  L.SB = SB;
264 
265  std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
266  SB->BlockMapAddr = BlockMapAddr;
267  SB->BlockSize = BlockSize;
268  SB->NumDirectoryBytes = computeDirectoryByteSize();
269  SB->FreeBlockMapBlock = FreePageMap;
270  SB->Unknown1 = Unknown1;
271 
272  uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
273  if (NumDirectoryBlocks > DirectoryBlocks.size()) {
274  // Our hint wasn't enough to satisfy the entire directory. Allocate
275  // remaining pages.
276  std::vector<uint32_t> ExtraBlocks;
277  uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
278  ExtraBlocks.resize(NumExtraBlocks);
279  if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
280  return std::move(EC);
281  DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
282  ExtraBlocks.end());
283  } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
284  uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
285  for (auto B :
286  ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
287  FreeBlocks[B] = true;
288  DirectoryBlocks.resize(NumDirectoryBlocks);
289  }
290 
291  // Don't set the number of blocks in the file until after allocating Blocks
292  // for the directory, since the allocation might cause the file to need to
293  // grow.
294  SB->NumBlocks = FreeBlocks.size();
295 
296  ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
297  std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
298  DirBlocks);
299  L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
300 
301  // The stream sizes should be re-allocated as a stable pointer and the stream
302  // map should have each of its entries allocated as a separate stable pointer.
303  if (!StreamData.empty()) {
304  ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
305  L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
306  L.StreamMap.resize(StreamData.size());
307  for (uint32_t I = 0; I < StreamData.size(); ++I) {
308  Sizes[I] = StreamData[I].first;
309  ulittle32_t *BlockList =
310  Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
311  std::uninitialized_copy_n(StreamData[I].second.begin(),
312  StreamData[I].second.size(), BlockList);
313  L.StreamMap[I] =
314  ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
315  }
316  }
317 
318  // FPM blocks occur in pairs at every `BlockLength` interval. While blocks of
319  // this form are reserved for FPM blocks, not all blocks of this form will
320  // actually be needed for FPM data because there are more blocks of this form
321  // than are required to represent a PDB file with a given number of blocks.
322  // So we need to find out which blocks are *actually* going to be real FPM
323  // blocks, then mark the reset of the reserved blocks as unallocated.
324  MSFStreamLayout FpmLayout = msf::getFpmStreamLayout(L, true);
325  auto FpmBlocks = makeArrayRef(FpmLayout.Blocks);
326  for (uint32_t B = kFreePageMap0Block; B < SB->NumBlocks;
328  finalizeFpmBlockStatus(B, FpmBlocks, FreeBlocks);
329  finalizeFpmBlockStatus(B + 1, FpmBlocks, FreeBlocks);
330  }
331  L.FreePageMap = FreeBlocks;
332 
333  return L;
334 }
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:152
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
BitVector & set()
Definition: BitVector.h:398
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:93
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
Describes the layout of a stream in an MSF layout.
Definition: MSFCommon.h:68
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
MSFStreamLayout getFpmStreamLayout(const MSFLayout &Msf, bool IncludeUnusedFpmData=false, bool AltFpm=false)
Determine the layout of the FPM stream, given the MSF layout.
Definition: MSFCommon.cpp:63
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
uint32_t getFpmIntervalLength(const MSFLayout &L)
Definition: MSFCommon.h:107
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
static void finalizeFpmBlockStatus(uint32_t B, ArrayRef< ulittle32_t > &FpmBlocks, BitVector &Fpm)
Definition: MSFBuilder.cpp:247
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:138
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:212
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:260
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:99
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:81
const SuperBlock * SB
Definition: MSFCommon.h:55
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:45
support::ulittle32_t NumBlocks
Definition: MSFCommon.h:43
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144