416 lines · 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-exception6//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 <utility>25#include <vector>26 27using namespace llvm;28using namespace llvm::msf;29using namespace llvm::support;30 31static const uint32_t kSuperBlockBlock = 0;32static const uint32_t kFreePageMap0Block = 1;33static const uint32_t kFreePageMap1Block = 2;34static const uint32_t kNumReservedPages = 3;35 36static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;37static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;38 39MSFBuilder::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 50Expected<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 62Error 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 83void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }84 85void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }86 87Error 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 102Error 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 extra118 // blocks for each FPM group crossed and mark both blocks from the group as119 // used. FPM blocks are marked as allocated regardless of whether or not120 // they ultimately describe the status of blocks in the file. This means121 // that not only are extraneous blocks at the end of the main FPM marked as122 // allocated, but also blocks from the alternate FPM are always marked as123 // 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 145uint32_t MSFBuilder::getNumUsedBlocks() const {146 return getTotalBlockCount() - getNumFreeBlocks();147}148 149uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }150 151uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }152 153bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }154 155Expected<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 specified158 // blocks are both necessary and sufficient for holding the requested number159 // 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 182Expected<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 192Error 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 stream211 // 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 224uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }225 226uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {227 return StreamData[StreamIdx].first;228}229 230ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {231 return StreamData[StreamIdx].second;232}233 234uint32_t MSFBuilder::computeDirectoryByteSize() const {235 // The directory has the following layout, where each item is a ulittle32_t:236 // NumStreams237 // StreamSizes[NumStreams]238 // StreamBlocks[NumStreams][]239 uint32_t Size = sizeof(ulittle32_t); // NumStreams240 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes241 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 250Expected<MSFLayout> MSFBuilder::generateLayout() {251 llvm::TimeTraceScope timeScope("MSF: Generate layout");252 253 SuperBlock *SB = Allocator.Allocate<SuperBlock>();254 MSFLayout L;255 L.SB = SB;256 257 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));258 SB->BlockMapAddr = BlockMapAddr;259 SB->BlockSize = BlockSize;260 SB->NumDirectoryBytes = computeDirectoryByteSize();261 SB->FreeBlockMapBlock = FreePageMap;262 SB->Unknown1 = Unknown1;263 264 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);265 if (NumDirectoryBlocks > DirectoryBlocks.size()) {266 // Our hint wasn't enough to satisfy the entire directory. Allocate267 // remaining pages.268 std::vector<uint32_t> ExtraBlocks;269 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();270 ExtraBlocks.resize(NumExtraBlocks);271 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))272 return std::move(EC);273 llvm::append_range(DirectoryBlocks, ExtraBlocks);274 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {275 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;276 for (auto B :277 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))278 FreeBlocks[B] = true;279 DirectoryBlocks.resize(NumDirectoryBlocks);280 }281 282 // Don't set the number of blocks in the file until after allocating Blocks283 // for the directory, since the allocation might cause the file to need to284 // grow.285 SB->NumBlocks = FreeBlocks.size();286 287 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);288 llvm::uninitialized_copy(DirectoryBlocks, DirBlocks);289 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);290 291 // The stream sizes should be re-allocated as a stable pointer and the stream292 // map should have each of its entries allocated as a separate stable pointer.293 if (!StreamData.empty()) {294 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());295 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());296 L.StreamMap.resize(StreamData.size());297 for (uint32_t I = 0; I < StreamData.size(); ++I) {298 Sizes[I] = StreamData[I].first;299 ulittle32_t *BlockList =300 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());301 llvm::uninitialized_copy(StreamData[I].second, 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 312static 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 337Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,338 MSFLayout &Layout) {339 llvm::TimeTraceScope timeScope("Commit MSF");340 341 Expected<MSFLayout> L = generateLayout();342 if (!L)343 return L.takeError();344 345 Layout = std::move(*L);346 347 uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks;348 // Ensure that the file size is under the limit for the specified block size.349 if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) {350 msf_error_code error_code = [](uint32_t BlockSize) {351 switch (BlockSize) {352 case 8192:353 return msf_error_code::size_overflow_8192;354 case 16384:355 return msf_error_code::size_overflow_16384;356 case 32768:357 return msf_error_code::size_overflow_32768;358 default:359 return msf_error_code::size_overflow_4096;360 }361 }(Layout.SB->BlockSize);362 363 return make_error<MSFError>(364 error_code,365 formatv("File size {0,1:N} too large for current PDB page size {1}",366 FileSize, Layout.SB->BlockSize));367 }368 369 uint64_t NumDirectoryBlocks =370 bytesToBlocks(Layout.SB->NumDirectoryBytes, Layout.SB->BlockSize);371 uint64_t DirectoryBlockMapSize =372 NumDirectoryBlocks * sizeof(support::ulittle32_t);373 if (DirectoryBlockMapSize > Layout.SB->BlockSize) {374 return make_error<MSFError>(msf_error_code::stream_directory_overflow,375 formatv("The directory block map ({0} bytes) "376 "doesn't fit in a block ({1} bytes)",377 DirectoryBlockMapSize,378 Layout.SB->BlockSize));379 }380 381 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);382 if (auto EC = OutFileOrError.takeError())383 return std::move(EC);384 385 FileBufferByteStream Buffer(std::move(*OutFileOrError),386 llvm::endianness::little);387 BinaryStreamWriter Writer(Buffer);388 389 if (auto EC = Writer.writeObject(*Layout.SB))390 return std::move(EC);391 392 commitFpm(Buffer, Layout, Allocator);393 394 uint32_t BlockMapOffset =395 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);396 Writer.setOffset(BlockMapOffset);397 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))398 return std::move(EC);399 400 auto DirStream = WritableMappedBlockStream::createDirectoryStream(401 Layout, Buffer, Allocator);402 BinaryStreamWriter DW(*DirStream);403 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))404 return std::move(EC);405 406 if (auto EC = DW.writeArray(Layout.StreamSizes))407 return std::move(EC);408 409 for (const auto &Blocks : Layout.StreamMap) {410 if (auto EC = DW.writeArray(Blocks))411 return std::move(EC);412 }413 414 return std::move(Buffer);415}416