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 "llvm/Support/TimeProfiler.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <cstdint>
23 #include <cstring>
24 #include <memory>
25 #include <utility>
26 #include <vector>
27 
28 using namespace llvm;
29 using namespace llvm::msf;
30 using namespace llvm::support;
31 
32 static const uint32_t kSuperBlockBlock = 0;
33 static const uint32_t kFreePageMap0Block = 1;
34 static const uint32_t kFreePageMap1Block = 2;
35 static const uint32_t kNumReservedPages = 3;
36 
37 static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
38 static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
39 
40 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
41                        BumpPtrAllocator &Allocator)
42     : Allocator(Allocator), IsGrowable(CanGrow),
43       FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
44       BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
45   FreeBlocks[kSuperBlockBlock] = false;
46   FreeBlocks[kFreePageMap0Block] = false;
47   FreeBlocks[kFreePageMap1Block] = false;
48   FreeBlocks[BlockMapAddr] = false;
49 }
50 
51 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
52                                         uint32_t BlockSize,
53                                         uint32_t MinBlockCount, bool CanGrow) {
54   if (!isValidBlockSize(BlockSize))
55     return make_error<MSFError>(msf_error_code::invalid_format,
56                                 "The requested block size is unsupported");
57 
58   return MSFBuilder(BlockSize,
59                     std::max(MinBlockCount, msf::getMinimumBlockCount()),
60                     CanGrow, Allocator);
61 }
62 
63 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
64   if (Addr == BlockMapAddr)
65     return Error::success();
66 
67   if (Addr >= FreeBlocks.size()) {
68     if (!IsGrowable)
69       return make_error<MSFError>(msf_error_code::insufficient_buffer,
70                                   "Cannot grow the number of blocks");
71     FreeBlocks.resize(Addr + 1, true);
72   }
73 
74   if (!isBlockFree(Addr))
75     return make_error<MSFError>(
76         msf_error_code::block_in_use,
77         "Requested block map address is already in use");
78   FreeBlocks[BlockMapAddr] = true;
79   FreeBlocks[Addr] = false;
80   BlockMapAddr = Addr;
81   return Error::success();
82 }
83 
84 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
85 
86 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
87 
88 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
89   for (auto B : DirectoryBlocks)
90     FreeBlocks[B] = true;
91   for (auto B : DirBlocks) {
92     if (!isBlockFree(B)) {
93       return make_error<MSFError>(msf_error_code::unspecified,
94                                   "Attempt to reuse an allocated block");
95     }
96     FreeBlocks[B] = false;
97   }
98 
99   DirectoryBlocks = DirBlocks;
100   return Error::success();
101 }
102 
103 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
104                                  MutableArrayRef<uint32_t> Blocks) {
105   if (NumBlocks == 0)
106     return Error::success();
107 
108   uint32_t NumFreeBlocks = FreeBlocks.count();
109   if (NumFreeBlocks < NumBlocks) {
110     if (!IsGrowable)
111       return make_error<MSFError>(msf_error_code::insufficient_buffer,
112                                   "There are no free Blocks in the file");
113     uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
114     uint32_t OldBlockCount = FreeBlocks.size();
115     uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
116     uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
117     FreeBlocks.resize(NewBlockCount, true);
118     // If we crossed over an fpm page, we actually need to allocate 2 extra
119     // blocks for each FPM group crossed and mark both blocks from the group as
120     // used.  FPM blocks are marked as allocated regardless of whether or not
121     // they ultimately describe the status of blocks in the file.  This means
122     // that not only are extraneous blocks at the end of the main FPM marked as
123     // allocated, but also blocks from the alternate FPM are always marked as
124     // allocated.
125     while (NextFpmBlock < NewBlockCount) {
126       NewBlockCount += 2;
127       FreeBlocks.resize(NewBlockCount, true);
128       FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
129       NextFpmBlock += BlockSize;
130     }
131   }
132 
133   int I = 0;
134   int Block = FreeBlocks.find_first();
135   do {
136     assert(Block != -1 && "We ran out of Blocks!");
137 
138     uint32_t NextBlock = static_cast<uint32_t>(Block);
139     Blocks[I++] = NextBlock;
140     FreeBlocks.reset(NextBlock);
141     Block = FreeBlocks.find_next(Block);
142   } while (--NumBlocks > 0);
143   return Error::success();
144 }
145 
146 uint32_t MSFBuilder::getNumUsedBlocks() const {
147   return getTotalBlockCount() - getNumFreeBlocks();
148 }
149 
150 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
151 
152 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
153 
154 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
155 
156 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
157                                          ArrayRef<uint32_t> Blocks) {
158   // Add a new stream mapped to the specified blocks.  Verify that the specified
159   // blocks are both necessary and sufficient for holding the requested number
160   // of bytes, and verify that all requested blocks are free.
161   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
162   if (ReqBlocks != Blocks.size())
163     return make_error<MSFError>(
164         msf_error_code::invalid_format,
165         "Incorrect number of blocks for requested stream size");
166   for (auto Block : Blocks) {
167     if (Block >= FreeBlocks.size())
168       FreeBlocks.resize(Block + 1, true);
169 
170     if (!FreeBlocks.test(Block))
171       return make_error<MSFError>(
172           msf_error_code::unspecified,
173           "Attempt to re-use an already allocated block");
174   }
175   // Mark all the blocks occupied by the new stream as not free.
176   for (auto Block : Blocks) {
177     FreeBlocks.reset(Block);
178   }
179   StreamData.push_back(std::make_pair(Size, Blocks));
180   return StreamData.size() - 1;
181 }
182 
183 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
184   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
185   std::vector<uint32_t> NewBlocks;
186   NewBlocks.resize(ReqBlocks);
187   if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
188     return std::move(EC);
189   StreamData.push_back(std::make_pair(Size, NewBlocks));
190   return StreamData.size() - 1;
191 }
192 
193 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
194   uint32_t OldSize = getStreamSize(Idx);
195   if (OldSize == Size)
196     return Error::success();
197 
198   uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
199   uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
200 
201   if (NewBlocks > OldBlocks) {
202     uint32_t AddedBlocks = NewBlocks - OldBlocks;
203     // If we're growing, we have to allocate new Blocks.
204     std::vector<uint32_t> AddedBlockList;
205     AddedBlockList.resize(AddedBlocks);
206     if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
207       return EC;
208     auto &CurrentBlocks = StreamData[Idx].second;
209     llvm::append_range(CurrentBlocks, AddedBlockList);
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 
227 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
228   return StreamData[StreamIdx].first;
229 }
230 
231 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
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 
251 Expected<MSFLayout> MSFBuilder::generateLayout() {
252   llvm::TimeTraceScope timeScope("MSF: Generate layout");
253 
254   SuperBlock *SB = Allocator.Allocate<SuperBlock>();
255   MSFLayout L;
256   L.SB = SB;
257 
258   std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
259   SB->BlockMapAddr = BlockMapAddr;
260   SB->BlockSize = BlockSize;
261   SB->NumDirectoryBytes = computeDirectoryByteSize();
262   SB->FreeBlockMapBlock = FreePageMap;
263   SB->Unknown1 = Unknown1;
264 
265   uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
266   if (NumDirectoryBlocks > DirectoryBlocks.size()) {
267     // Our hint wasn't enough to satisfy the entire directory.  Allocate
268     // remaining pages.
269     std::vector<uint32_t> ExtraBlocks;
270     uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
271     ExtraBlocks.resize(NumExtraBlocks);
272     if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
273       return std::move(EC);
274     llvm::append_range(DirectoryBlocks, ExtraBlocks);
275   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
276     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
277     for (auto B :
278          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
279       FreeBlocks[B] = true;
280     DirectoryBlocks.resize(NumDirectoryBlocks);
281   }
282 
283   // Don't set the number of blocks in the file until after allocating Blocks
284   // for the directory, since the allocation might cause the file to need to
285   // grow.
286   SB->NumBlocks = FreeBlocks.size();
287 
288   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
289   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
290                             DirBlocks);
291   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
292 
293   // The stream sizes should be re-allocated as a stable pointer and the stream
294   // map should have each of its entries allocated as a separate stable pointer.
295   if (!StreamData.empty()) {
296     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
297     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
298     L.StreamMap.resize(StreamData.size());
299     for (uint32_t I = 0; I < StreamData.size(); ++I) {
300       Sizes[I] = StreamData[I].first;
301       ulittle32_t *BlockList =
302           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
303       std::uninitialized_copy_n(StreamData[I].second.begin(),
304                                 StreamData[I].second.size(), BlockList);
305       L.StreamMap[I] =
306           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
307     }
308   }
309 
310   L.FreePageMap = FreeBlocks;
311 
312   return L;
313 }
314 
315 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
316                       BumpPtrAllocator &Allocator) {
317   auto FpmStream =
318       WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
319 
320   // We only need to create the alt fpm stream so that it gets initialized.
321   WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
322                                              true);
323 
324   uint32_t BI = 0;
325   BinaryStreamWriter FpmWriter(*FpmStream);
326   while (BI < Layout.SB->NumBlocks) {
327     uint8_t ThisByte = 0;
328     for (uint32_t I = 0; I < 8; ++I) {
329       bool IsFree =
330           (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
331       uint8_t Mask = uint8_t(IsFree) << I;
332       ThisByte |= Mask;
333       ++BI;
334     }
335     cantFail(FpmWriter.writeObject(ThisByte));
336   }
337   assert(FpmWriter.bytesRemaining() == 0);
338 }
339 
340 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
341                                                   MSFLayout &Layout) {
342   llvm::TimeTraceScope timeScope("Commit MSF");
343 
344   Expected<MSFLayout> L = generateLayout();
345   if (!L)
346     return L.takeError();
347 
348   Layout = std::move(*L);
349 
350   uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks;
351   // Ensure that the file size is under the limit for the specified block size.
352   if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) {
353     msf_error_code error_code = [](uint32_t BlockSize) {
354       switch (BlockSize) {
355       case 8192:
356         return msf_error_code::size_overflow_8192;
357       case 16384:
358         return msf_error_code::size_overflow_16384;
359       case 32768:
360         return msf_error_code::size_overflow_32768;
361       default:
362         return msf_error_code::size_overflow_4096;
363       }
364     }(Layout.SB->BlockSize);
365 
366     return make_error<MSFError>(
367         error_code,
368         formatv("File size {0,1:N} too large for current PDB page size {1}",
369                 FileSize, Layout.SB->BlockSize));
370   }
371 
372   uint64_t NumDirectoryBlocks =
373       bytesToBlocks(Layout.SB->NumDirectoryBytes, Layout.SB->BlockSize);
374   uint64_t DirectoryBlockMapSize =
375       NumDirectoryBlocks * sizeof(support::ulittle32_t);
376   if (DirectoryBlockMapSize > Layout.SB->BlockSize) {
377     return make_error<MSFError>(msf_error_code::stream_directory_overflow,
378                                 formatv("The directory block map ({0} bytes) "
379                                         "doesn't fit in a block ({1} bytes)",
380                                         DirectoryBlockMapSize,
381                                         Layout.SB->BlockSize));
382   }
383 
384   auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
385   if (auto EC = OutFileOrError.takeError())
386     return std::move(EC);
387 
388   FileBufferByteStream Buffer(std::move(*OutFileOrError),
389                               llvm::endianness::little);
390   BinaryStreamWriter Writer(Buffer);
391 
392   if (auto EC = Writer.writeObject(*Layout.SB))
393     return std::move(EC);
394 
395   commitFpm(Buffer, Layout, Allocator);
396 
397   uint32_t BlockMapOffset =
398       msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
399   Writer.setOffset(BlockMapOffset);
400   if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
401     return std::move(EC);
402 
403   auto DirStream = WritableMappedBlockStream::createDirectoryStream(
404       Layout, Buffer, Allocator);
405   BinaryStreamWriter DW(*DirStream);
406   if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
407     return std::move(EC);
408 
409   if (auto EC = DW.writeArray(Layout.StreamSizes))
410     return std::move(EC);
411 
412   for (const auto &Blocks : Layout.StreamMap) {
413     if (auto EC = DW.writeArray(Blocks))
414       return std::move(EC);
415   }
416 
417   return std::move(Buffer);
418 }
419