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 
9 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/DebugInfo/MSF/MSFError.h"
12 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
13 #include "llvm/Support/BinaryByteStream.h"
14 #include "llvm/Support/BinaryStreamWriter.h"
15 #include "llvm/Support/Endian.h"
16 #include "llvm/Support/Error.h"
17 #include "llvm/Support/FileOutputBuffer.h"
18 #include "llvm/Support/FormatVariadic.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 
36 static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
37 static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
38 
39 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
40                        BumpPtrAllocator &Allocator)
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 
50 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
51                                         uint32_t BlockSize,
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 
62 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
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>(
75         msf_error_code::block_in_use,
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 
87 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
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 
145 uint32_t MSFBuilder::getNumUsedBlocks() const {
146   return getTotalBlockCount() - getNumFreeBlocks();
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 
155 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
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>(
163         msf_error_code::invalid_format,
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>(
171           msf_error_code::unspecified,
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 
182 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
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 
192 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
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     llvm::append_range(CurrentBlocks, AddedBlockList);
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 
226 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
227   return StreamData[StreamIdx].first;
228 }
229 
230 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
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 
250 Expected<MSFLayout> MSFBuilder::generateLayout() {
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     llvm::append_range(DirectoryBlocks, ExtraBlocks);
272   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
273     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
274     for (auto B :
275          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
276       FreeBlocks[B] = true;
277     DirectoryBlocks.resize(NumDirectoryBlocks);
278   }
279 
280   // Don't set the number of blocks in the file until after allocating Blocks
281   // for the directory, since the allocation might cause the file to need to
282   // grow.
283   SB->NumBlocks = FreeBlocks.size();
284 
285   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
286   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
287                             DirBlocks);
288   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
289 
290   // The stream sizes should be re-allocated as a stable pointer and the stream
291   // map should have each of its entries allocated as a separate stable pointer.
292   if (!StreamData.empty()) {
293     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
294     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
295     L.StreamMap.resize(StreamData.size());
296     for (uint32_t I = 0; I < StreamData.size(); ++I) {
297       Sizes[I] = StreamData[I].first;
298       ulittle32_t *BlockList =
299           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
300       std::uninitialized_copy_n(StreamData[I].second.begin(),
301                                 StreamData[I].second.size(), BlockList);
302       L.StreamMap[I] =
303           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
304     }
305   }
306 
307   L.FreePageMap = FreeBlocks;
308 
309   return L;
310 }
311 
312 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
313                       BumpPtrAllocator &Allocator) {
314   auto FpmStream =
315       WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
316 
317   // We only need to create the alt fpm stream so that it gets initialized.
318   WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
319                                              true);
320 
321   uint32_t BI = 0;
322   BinaryStreamWriter FpmWriter(*FpmStream);
323   while (BI < Layout.SB->NumBlocks) {
324     uint8_t ThisByte = 0;
325     for (uint32_t I = 0; I < 8; ++I) {
326       bool IsFree =
327           (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
328       uint8_t Mask = uint8_t(IsFree) << I;
329       ThisByte |= Mask;
330       ++BI;
331     }
332     cantFail(FpmWriter.writeObject(ThisByte));
333   }
334   assert(FpmWriter.bytesRemaining() == 0);
335 }
336 
337 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
338                                                   MSFLayout &Layout) {
339   Expected<MSFLayout> L = generateLayout();
340   if (!L)
341     return L.takeError();
342 
343   Layout = std::move(*L);
344 
345   uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks;
346   // Ensure that the file size is under the limit for the specified block size.
347   if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) {
348     msf_error_code error_code = [](uint32_t BlockSize) {
349       switch (BlockSize) {
350       case 8192:
351         return msf_error_code::size_overflow_8192;
352       case 16384:
353         return msf_error_code::size_overflow_16384;
354       case 32768:
355         return msf_error_code::size_overflow_32768;
356       default:
357         return msf_error_code::size_overflow_4096;
358       }
359     }(Layout.SB->BlockSize);
360 
361     return make_error<MSFError>(
362         error_code,
363         formatv("File size {0,1:N} too large for current PDB page size {1}",
364                 FileSize, Layout.SB->BlockSize));
365   }
366 
367   uint64_t NumDirectoryBlocks =
368       bytesToBlocks(Layout.SB->NumDirectoryBytes, Layout.SB->BlockSize);
369   uint64_t DirectoryBlockMapSize =
370       NumDirectoryBlocks * sizeof(support::ulittle32_t);
371   if (DirectoryBlockMapSize > Layout.SB->BlockSize) {
372     return make_error<MSFError>(msf_error_code::stream_directory_overflow,
373                                 formatv("The directory block map ({0} bytes) "
374                                         "doesn't fit in a block ({1} bytes)",
375                                         DirectoryBlockMapSize,
376                                         Layout.SB->BlockSize));
377   }
378 
379   auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
380   if (auto EC = OutFileOrError.takeError())
381     return std::move(EC);
382 
383   FileBufferByteStream Buffer(std::move(*OutFileOrError),
384                               llvm::support::little);
385   BinaryStreamWriter Writer(Buffer);
386 
387   if (auto EC = Writer.writeObject(*Layout.SB))
388     return std::move(EC);
389 
390   commitFpm(Buffer, Layout, Allocator);
391 
392   uint32_t BlockMapOffset =
393       msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
394   Writer.setOffset(BlockMapOffset);
395   if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
396     return std::move(EC);
397 
398   auto DirStream = WritableMappedBlockStream::createDirectoryStream(
399       Layout, Buffer, Allocator);
400   BinaryStreamWriter DW(*DirStream);
401   if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
402     return std::move(EC);
403 
404   if (auto EC = DW.writeArray(Layout.StreamSizes))
405     return std::move(EC);
406 
407   for (const auto &Blocks : Layout.StreamMap) {
408     if (auto EC = DW.writeArray(Blocks))
409       return std::move(EC);
410   }
411 
412   return std::move(Buffer);
413 }
414