llvm/lib/DebugInfo/MSF/MSFBuilder.cpp

   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   if (FileSize > UINT32_MAX) {
 347     // FIXME: Changing the BinaryStream classes to use 64-bit numbers lets
 348     // us create PDBs larger than 4 GiB successfully. The file format is
 349     // block-based and as long as each stream is small enough, PDBs larger than
 350     // 4 GiB might work. Check if tools can handle these large PDBs, and if so
 351     // add support for writing them.
 352     return make_error<MSFError>(
 353         msf_error_code::size_overflow,
 354         formatv("File size would have been {0,1:N}", FileSize));
 355   }
 356
 357   auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
 358   if (auto EC = OutFileOrError.takeError())
 359     return std::move(EC);
 360
 361   FileBufferByteStream Buffer(std::move(*OutFileOrError),
 362                               llvm::support::little);
 363   BinaryStreamWriter Writer(Buffer);
 364
 365   if (auto EC = Writer.writeObject(*Layout.SB))
 366     return std::move(EC);
 367
 368   commitFpm(Buffer, Layout, Allocator);
 369
 370   uint32_t BlockMapOffset =
 371       msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
 372   Writer.setOffset(BlockMapOffset);
 373   if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
 374     return std::move(EC);
 375
 376   auto DirStream = WritableMappedBlockStream::createDirectoryStream(
 377       Layout, Buffer, Allocator);
 378   BinaryStreamWriter DW(*DirStream);
 379   if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
 380     return std::move(EC);
 381
 382   if (auto EC = DW.writeArray(Layout.StreamSizes))
 383     return std::move(EC);
 384
 385   for (const auto &Blocks : Layout.StreamMap) {
 386     if (auto EC = DW.writeArray(Blocks))
 387       return std::move(EC);
 388   }
 389
 390   return std::move(Buffer);
 391 }