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
28using namespace llvm;
29using namespace llvm::msf;
30using namespace llvm::support;
31
32static const uint32_t kSuperBlockBlock = 0;
33static const uint32_t kFreePageMap0Block = 1;
34static const uint32_t kFreePageMap1Block = 2;
35static const uint32_t kNumReservedPages = 3;
36
37static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
38static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
39
40MSFBuilder::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
51Expected<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
63Error 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
84void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
85
86void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
87
88Error 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
103Error 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
146uint32_t MSFBuilder::getNumUsedBlocks() const {
147  return getTotalBlockCount() - getNumFreeBlocks();
148}
149
150uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
151
152uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
153
154bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
155
156Expected<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
183Expected<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
193Error 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
225uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
226
227uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
228  return StreamData[StreamIdx].first;
229}
230
231ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
232  return StreamData[StreamIdx].second;
233}
234
235uint32_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
251Expected<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
315static 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
340Expected<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