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"
11 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
12 #include "llvm/DebugInfo/MSF/MSFError.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 
32 static const uint32_t kDefaultFreePageMap = kFreePageMap0Block;
33 static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
34 
35 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
36                        BumpPtrAllocator &Allocator)
37     : Allocator(Allocator), IsGrowable(CanGrow),
38       FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
39       MininumBlocks(MinBlockCount), BlockMapAddr(kDefaultBlockMapAddr),
40       FreeBlocks(MinBlockCount, true) {
41   FreeBlocks[kSuperBlockBlock] = false;
42   FreeBlocks[kFreePageMap0Block] = false;
43   FreeBlocks[kFreePageMap1Block] = false;
44   FreeBlocks[BlockMapAddr] = false;
45 }
46 
47 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
48                                         uint32_t BlockSize,
49                                         uint32_t MinBlockCount, bool CanGrow) {
50   if (!isValidBlockSize(BlockSize))
51     return make_error<MSFError>(msf_error_code::invalid_format,
52                                 "The requested block size is unsupported");
53 
54   return MSFBuilder(BlockSize,
55                     std::max(MinBlockCount, msf::getMinimumBlockCount()),
56                     CanGrow, Allocator);
57 }
58 
59 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
60   if (Addr == BlockMapAddr)
61     return Error::success();
62 
63   if (Addr >= FreeBlocks.size()) {
64     if (!IsGrowable)
65       return make_error<MSFError>(msf_error_code::insufficient_buffer,
66                                   "Cannot grow the number of blocks");
67     FreeBlocks.resize(Addr + 1, true);
68   }
69 
70   if (!isBlockFree(Addr))
71     return make_error<MSFError>(
72         msf_error_code::block_in_use,
73         "Requested block map address is already in use");
74   FreeBlocks[BlockMapAddr] = true;
75   FreeBlocks[Addr] = false;
76   BlockMapAddr = Addr;
77   return Error::success();
78 }
79 
80 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
81 
82 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
83 
84 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
85   for (auto B : DirectoryBlocks)
86     FreeBlocks[B] = true;
87   for (auto B : DirBlocks) {
88     if (!isBlockFree(B)) {
89       return make_error<MSFError>(msf_error_code::unspecified,
90                                   "Attempt to reuse an allocated block");
91     }
92     FreeBlocks[B] = false;
93   }
94 
95   DirectoryBlocks = DirBlocks;
96   return Error::success();
97 }
98 
99 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
100                                  MutableArrayRef<uint32_t> Blocks) {
101   if (NumBlocks == 0)
102     return Error::success();
103 
104   uint32_t NumFreeBlocks = FreeBlocks.count();
105   if (NumFreeBlocks < NumBlocks) {
106     if (!IsGrowable)
107       return make_error<MSFError>(msf_error_code::insufficient_buffer,
108                                   "There are no free Blocks in the file");
109     uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
110     uint32_t OldBlockCount = FreeBlocks.size();
111     uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
112     uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
113     FreeBlocks.resize(NewBlockCount, true);
114     // If we crossed over an fpm page, we actually need to allocate 2 extra
115     // blocks for each FPM group crossed and mark both blocks from the group as
116     // used.  We may not actually use them since there are many more FPM blocks
117     // present than are required to represent all blocks in a given PDB, but we
118     // need to make sure they aren't allocated to a stream or something else.
119     // At the end when committing the PDB, we'll go through and mark the
120     // extraneous ones unused.
121     while (NextFpmBlock < NewBlockCount) {
122       NewBlockCount += 2;
123       FreeBlocks.resize(NewBlockCount, true);
124       FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
125       NextFpmBlock += BlockSize;
126     }
127   }
128 
129   int I = 0;
130   int Block = FreeBlocks.find_first();
131   do {
132     assert(Block != -1 && "We ran out of Blocks!");
133 
134     uint32_t NextBlock = static_cast<uint32_t>(Block);
135     Blocks[I++] = NextBlock;
136     FreeBlocks.reset(NextBlock);
137     Block = FreeBlocks.find_next(Block);
138   } while (--NumBlocks > 0);
139   return Error::success();
140 }
141 
142 uint32_t MSFBuilder::getNumUsedBlocks() const {
143   return getTotalBlockCount() - getNumFreeBlocks();
144 }
145 
146 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
147 
148 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
149 
150 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
151 
152 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
153                                          ArrayRef<uint32_t> Blocks) {
154   // Add a new stream mapped to the specified blocks.  Verify that the specified
155   // blocks are both necessary and sufficient for holding the requested number
156   // of bytes, and verify that all requested blocks are free.
157   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
158   if (ReqBlocks != Blocks.size())
159     return make_error<MSFError>(
160         msf_error_code::invalid_format,
161         "Incorrect number of blocks for requested stream size");
162   for (auto Block : Blocks) {
163     if (Block >= FreeBlocks.size())
164       FreeBlocks.resize(Block + 1, true);
165 
166     if (!FreeBlocks.test(Block))
167       return make_error<MSFError>(
168           msf_error_code::unspecified,
169           "Attempt to re-use an already allocated block");
170   }
171   // Mark all the blocks occupied by the new stream as not free.
172   for (auto Block : Blocks) {
173     FreeBlocks.reset(Block);
174   }
175   StreamData.push_back(std::make_pair(Size, Blocks));
176   return StreamData.size() - 1;
177 }
178 
179 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
180   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
181   std::vector<uint32_t> NewBlocks;
182   NewBlocks.resize(ReqBlocks);
183   if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
184     return std::move(EC);
185   StreamData.push_back(std::make_pair(Size, NewBlocks));
186   return StreamData.size() - 1;
187 }
188 
189 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
190   uint32_t OldSize = getStreamSize(Idx);
191   if (OldSize == Size)
192     return Error::success();
193 
194   uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
195   uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
196 
197   if (NewBlocks > OldBlocks) {
198     uint32_t AddedBlocks = NewBlocks - OldBlocks;
199     // If we're growing, we have to allocate new Blocks.
200     std::vector<uint32_t> AddedBlockList;
201     AddedBlockList.resize(AddedBlocks);
202     if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
203       return EC;
204     auto &CurrentBlocks = StreamData[Idx].second;
205     CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
206                          AddedBlockList.end());
207   } else if (OldBlocks > NewBlocks) {
208     // For shrinking, free all the Blocks in the Block map, update the stream
209     // data, then shrink the directory.
210     uint32_t RemovedBlocks = OldBlocks - NewBlocks;
211     auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
212     auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
213     for (auto P : RemovedBlockList)
214       FreeBlocks[P] = true;
215     StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
216   }
217 
218   StreamData[Idx].first = Size;
219   return Error::success();
220 }
221 
222 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
223 
224 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
225   return StreamData[StreamIdx].first;
226 }
227 
228 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
229   return StreamData[StreamIdx].second;
230 }
231 
232 uint32_t MSFBuilder::computeDirectoryByteSize() const {
233   // The directory has the following layout, where each item is a ulittle32_t:
234   //    NumStreams
235   //    StreamSizes[NumStreams]
236   //    StreamBlocks[NumStreams][]
237   uint32_t Size = sizeof(ulittle32_t);             // NumStreams
238   Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
239   for (const auto &D : StreamData) {
240     uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
241     assert(ExpectedNumBlocks == D.second.size() &&
242            "Unexpected number of blocks");
243     Size += ExpectedNumBlocks * sizeof(ulittle32_t);
244   }
245   return Size;
246 }
247 
248 static void finalizeFpmBlockStatus(uint32_t B, ArrayRef<ulittle32_t> &FpmBlocks,
249                                    BitVector &Fpm) {
250   if (FpmBlocks.empty() || FpmBlocks.front() != B) {
251     Fpm.set(B);
252     return;
253   }
254 
255   // If the next block in the actual layout is this block, it should *not* be
256   // free.
257   assert(!Fpm.test(B));
258   FpmBlocks = FpmBlocks.drop_front();
259 }
260 
261 Expected<MSFLayout> MSFBuilder::build() {
262   SuperBlock *SB = Allocator.Allocate<SuperBlock>();
263   MSFLayout L;
264   L.SB = SB;
265 
266   std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
267   SB->BlockMapAddr = BlockMapAddr;
268   SB->BlockSize = BlockSize;
269   SB->NumDirectoryBytes = computeDirectoryByteSize();
270   SB->FreeBlockMapBlock = FreePageMap;
271   SB->Unknown1 = Unknown1;
272 
273   uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
274   if (NumDirectoryBlocks > DirectoryBlocks.size()) {
275     // Our hint wasn't enough to satisfy the entire directory.  Allocate
276     // remaining pages.
277     std::vector<uint32_t> ExtraBlocks;
278     uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
279     ExtraBlocks.resize(NumExtraBlocks);
280     if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
281       return std::move(EC);
282     DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
283                            ExtraBlocks.end());
284   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
285     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
286     for (auto B :
287          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
288       FreeBlocks[B] = true;
289     DirectoryBlocks.resize(NumDirectoryBlocks);
290   }
291 
292   // Don't set the number of blocks in the file until after allocating Blocks
293   // for the directory, since the allocation might cause the file to need to
294   // grow.
295   SB->NumBlocks = FreeBlocks.size();
296 
297   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
298   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
299                             DirBlocks);
300   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
301 
302   // The stream sizes should be re-allocated as a stable pointer and the stream
303   // map should have each of its entries allocated as a separate stable pointer.
304   if (!StreamData.empty()) {
305     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
306     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
307     L.StreamMap.resize(StreamData.size());
308     for (uint32_t I = 0; I < StreamData.size(); ++I) {
309       Sizes[I] = StreamData[I].first;
310       ulittle32_t *BlockList =
311           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
312       std::uninitialized_copy_n(StreamData[I].second.begin(),
313                                 StreamData[I].second.size(), BlockList);
314       L.StreamMap[I] =
315           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
316     }
317   }
318 
319   // FPM blocks occur in pairs at every `BlockLength` interval.  While blocks of
320   // this form are reserved for FPM blocks, not all blocks of this form will
321   // actually be needed for FPM data because there are more blocks of this form
322   // than are required to represent a PDB file with a given number of blocks.
323   // So we need to find out which blocks are *actually* going to be real FPM
324   // blocks, then mark the reset of the reserved blocks as unallocated.
325   MSFStreamLayout FpmLayout = msf::getFpmStreamLayout(L, true);
326   auto FpmBlocks = makeArrayRef(FpmLayout.Blocks);
327   for (uint32_t B = kFreePageMap0Block; B < SB->NumBlocks;
328        B += msf::getFpmIntervalLength(L)) {
329     finalizeFpmBlockStatus(B, FpmBlocks, FreeBlocks);
330     finalizeFpmBlockStatus(B + 1, FpmBlocks, FreeBlocks);
331   }
332   L.FreePageMap = FreeBlocks;
333 
334   return L;
335 }
336