LCOV - code coverage report
Current view: top level - lib/DebugInfo/MSF - MSFBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 149 159 93.7 %
Date: 2018-07-13 00:08:38 Functions: 18 21 85.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MSFBuilder.cpp -----------------------------------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/DebugInfo/MSF/MSFBuilder.h"
      11             : #include "llvm/ADT/ArrayRef.h"
      12             : #include "llvm/DebugInfo/MSF/MSFError.h"
      13             : #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
      14             : #include "llvm/Support/BinaryByteStream.h"
      15             : #include "llvm/Support/BinaryStreamWriter.h"
      16             : #include "llvm/Support/Endian.h"
      17             : #include "llvm/Support/Error.h"
      18             : #include "llvm/Support/FileOutputBuffer.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         105 : MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
      40         105 :                        BumpPtrAllocator &Allocator)
      41             :     : Allocator(Allocator), IsGrowable(CanGrow),
      42             :       FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
      43         105 :       BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
      44             :   FreeBlocks[kSuperBlockBlock] = false;
      45             :   FreeBlocks[kFreePageMap0Block] = false;
      46             :   FreeBlocks[kFreePageMap1Block] = false;
      47         105 :   FreeBlocks[BlockMapAddr] = false;
      48         105 : }
      49             : 
      50         105 : 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         315 :   return MSFBuilder(BlockSize,
      58         210 :                     std::max(MinBlockCount, msf::getMinimumBlockCount()),
      59             :                     CanGrow, Allocator);
      60             : }
      61             : 
      62           0 : Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
      63           0 :   if (Addr == BlockMapAddr)
      64             :     return Error::success();
      65             : 
      66           0 :   if (Addr >= FreeBlocks.size()) {
      67           0 :     if (!IsGrowable)
      68             :       return make_error<MSFError>(msf_error_code::insufficient_buffer,
      69             :                                   "Cannot grow the number of blocks");
      70           0 :     FreeBlocks.resize(Addr + 1, true);
      71             :   }
      72             : 
      73           0 :   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           0 :   FreeBlocks[BlockMapAddr] = true;
      78             :   FreeBlocks[Addr] = false;
      79           0 :   BlockMapAddr = Addr;
      80             :   return Error::success();
      81             : }
      82             : 
      83           0 : void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
      84             : 
      85           0 : void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
      86             : 
      87           3 : Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
      88           3 :   for (auto B : DirectoryBlocks)
      89             :     FreeBlocks[B] = true;
      90          11 :   for (auto B : DirBlocks) {
      91           4 :     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           6 :   DirectoryBlocks = DirBlocks;
      99             :   return Error::success();
     100             : }
     101             : 
     102        1624 : Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
     103             :                                  MutableArrayRef<uint32_t> Blocks) {
     104        1624 :   if (NumBlocks == 0)
     105             :     return Error::success();
     106             : 
     107             :   uint32_t NumFreeBlocks = FreeBlocks.count();
     108        1083 :   if (NumFreeBlocks < NumBlocks) {
     109        1083 :     if (!IsGrowable)
     110             :       return make_error<MSFError>(msf_error_code::insufficient_buffer,
     111             :                                   "There are no free Blocks in the file");
     112        1083 :     uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
     113             :     uint32_t OldBlockCount = FreeBlocks.size();
     114        1083 :     uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
     115        2166 :     uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
     116        1083 :     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        1089 :     while (NextFpmBlock < NewBlockCount) {
     125           3 :       NewBlockCount += 2;
     126           3 :       FreeBlocks.resize(NewBlockCount, true);
     127           3 :       FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
     128           3 :       NextFpmBlock += BlockSize;
     129             :     }
     130             :   }
     131             : 
     132             :   int I = 0;
     133        1083 :   int Block = FreeBlocks.find_first();
     134             :   do {
     135             :     assert(Block != -1 && "We ran out of Blocks!");
     136             : 
     137       15563 :     uint32_t NextBlock = static_cast<uint32_t>(Block);
     138       31126 :     Blocks[I++] = NextBlock;
     139             :     FreeBlocks.reset(NextBlock);
     140             :     Block = FreeBlocks.find_next(Block);
     141       15563 :   } while (--NumBlocks > 0);
     142             :   return Error::success();
     143             : }
     144             : 
     145           4 : uint32_t MSFBuilder::getNumUsedBlocks() const {
     146           4 :   return getTotalBlockCount() - getNumFreeBlocks();
     147             : }
     148             : 
     149          16 : uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
     150             : 
     151           4 : uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
     152             : 
     153          46 : bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
     154             : 
     155           3 : 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           3 :   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
     161           3 :   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          23 :   for (auto Block : Blocks) {
     166          11 :     if (Block >= FreeBlocks.size())
     167           1 :       FreeBlocks.resize(Block + 1, true);
     168             : 
     169          11 :     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          22 :   for (auto Block : Blocks) {
     176             :     FreeBlocks.reset(Block);
     177             :   }
     178           4 :   StreamData.push_back(std::make_pair(Size, Blocks));
     179           4 :   return StreamData.size() - 1;
     180             : }
     181             : 
     182        1170 : Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
     183        2340 :   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
     184             :   std::vector<uint32_t> NewBlocks;
     185        1170 :   NewBlocks.resize(ReqBlocks);
     186        2340 :   if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
     187             :     return std::move(EC);
     188        2340 :   StreamData.push_back(std::make_pair(Size, NewBlocks));
     189        2340 :   return StreamData.size() - 1;
     190             : }
     191             : 
     192         451 : Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
     193         451 :   uint32_t OldSize = getStreamSize(Idx);
     194         451 :   if (OldSize == Size)
     195             :     return Error::success();
     196             : 
     197         722 :   uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
     198         722 :   uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
     199             : 
     200         361 :   if (NewBlocks > OldBlocks) {
     201         358 :     uint32_t AddedBlocks = NewBlocks - OldBlocks;
     202             :     // If we're growing, we have to allocate new Blocks.
     203             :     std::vector<uint32_t> AddedBlockList;
     204         358 :     AddedBlockList.resize(AddedBlocks);
     205         716 :     if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
     206             :       return EC;
     207         716 :     auto &CurrentBlocks = StreamData[Idx].second;
     208         358 :     CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
     209         358 :                          AddedBlockList.end());
     210           3 :   } 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           1 :     uint32_t RemovedBlocks = OldBlocks - NewBlocks;
     214           1 :     auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
     215             :     auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
     216           3 :     for (auto P : RemovedBlockList)
     217             :       FreeBlocks[P] = true;
     218           4 :     StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
     219             :   }
     220             : 
     221         722 :   StreamData[Idx].first = Size;
     222             :   return Error::success();
     223             : }
     224             : 
     225           2 : uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
     226             : 
     227         460 : uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
     228         920 :   return StreamData[StreamIdx].first;
     229             : }
     230             : 
     231           9 : ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
     232          18 :   return StreamData[StreamIdx].second;
     233             : }
     234             : 
     235          98 : 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         196 :   Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
     242        1261 :   for (const auto &D : StreamData) {
     243        2326 :     uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
     244             :     assert(ExpectedNumBlocks == D.second.size() &&
     245             :            "Unexpected number of blocks");
     246        1163 :     Size += ExpectedNumBlocks * sizeof(ulittle32_t);
     247             :   }
     248          98 :   return Size;
     249             : }
     250             : 
     251          98 : Expected<MSFLayout> MSFBuilder::generateLayout() {
     252          98 :   SuperBlock *SB = Allocator.Allocate<SuperBlock>();
     253          98 :   MSFLayout L;
     254          98 :   L.SB = SB;
     255             : 
     256          98 :   std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
     257          98 :   SB->BlockMapAddr = BlockMapAddr;
     258          98 :   SB->BlockSize = BlockSize;
     259          98 :   SB->NumDirectoryBytes = computeDirectoryByteSize();
     260          98 :   SB->FreeBlockMapBlock = FreePageMap;
     261          98 :   SB->Unknown1 = Unknown1;
     262             : 
     263         294 :   uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
     264         196 :   if (NumDirectoryBlocks > DirectoryBlocks.size()) {
     265             :     // Our hint wasn't enough to satisfy the entire directory.  Allocate
     266             :     // remaining pages.
     267             :     std::vector<uint32_t> ExtraBlocks;
     268          96 :     uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
     269          96 :     ExtraBlocks.resize(NumExtraBlocks);
     270         192 :     if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
     271             :       return std::move(EC);
     272          96 :     DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
     273         192 :                            ExtraBlocks.end());
     274           2 :   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
     275           1 :     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
     276           2 :     for (auto B :
     277           3 :          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
     278             :       FreeBlocks[B] = true;
     279           1 :     DirectoryBlocks.resize(NumDirectoryBlocks);
     280             :   }
     281             : 
     282             :   // Don't set the number of blocks in the file until after allocating Blocks
     283             :   // for the directory, since the allocation might cause the file to need to
     284             :   // grow.
     285          98 :   SB->NumBlocks = FreeBlocks.size();
     286             : 
     287          98 :   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
     288             :   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
     289             :                             DirBlocks);
     290          98 :   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
     291             : 
     292             :   // The stream sizes should be re-allocated as a stable pointer and the stream
     293             :   // map should have each of its entries allocated as a separate stable pointer.
     294          98 :   if (!StreamData.empty()) {
     295          97 :     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
     296         194 :     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
     297          97 :     L.StreamMap.resize(StreamData.size());
     298        3683 :     for (uint32_t I = 0; I < StreamData.size(); ++I) {
     299        1163 :       Sizes[I] = StreamData[I].first;
     300             :       ulittle32_t *BlockList =
     301        1163 :           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
     302        1163 :       std::uninitialized_copy_n(StreamData[I].second.begin(),
     303        1163 :                                 StreamData[I].second.size(), BlockList);
     304        2326 :       L.StreamMap[I] =
     305        1163 :           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
     306             :     }
     307             :   }
     308             : 
     309          98 :   L.FreePageMap = FreeBlocks;
     310             : 
     311             :   return L;
     312             : }
     313             : 
     314          90 : static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
     315             :                       BumpPtrAllocator &Allocator) {
     316             :   auto FpmStream =
     317         180 :       WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
     318             : 
     319             :   // We only need to create the alt fpm stream so that it gets initialized.
     320         270 :   WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
     321             :                                              true);
     322             : 
     323             :   uint32_t BI = 0;
     324          90 :   BinaryStreamWriter FpmWriter(*FpmStream);
     325         831 :   while (BI < Layout.SB->NumBlocks) {
     326         217 :     uint8_t ThisByte = 0;
     327        3689 :     for (uint32_t I = 0; I < 8; ++I) {
     328             :       bool IsFree =
     329        3194 :           (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
     330        1736 :       uint8_t Mask = uint8_t(IsFree) << I;
     331        1736 :       ThisByte |= Mask;
     332        1736 :       ++BI;
     333             :     }
     334         217 :     cantFail(FpmWriter.writeObject(ThisByte));
     335             :   }
     336             :   assert(FpmWriter.bytesRemaining() == 0);
     337          90 : }
     338             : 
     339          90 : Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
     340             :                                                   MSFLayout &Layout) {
     341         180 :   Expected<MSFLayout> L = generateLayout();
     342          90 :   if (!L)
     343             :     return L.takeError();
     344             : 
     345          90 :   Layout = std::move(*L);
     346             : 
     347         180 :   uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
     348         180 :   auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
     349          90 :   if (auto EC = OutFileOrError.takeError())
     350             :     return std::move(EC);
     351             : 
     352             :   FileBufferByteStream Buffer(std::move(*OutFileOrError),
     353         180 :                               llvm::support::little);
     354          90 :   BinaryStreamWriter Writer(Buffer);
     355             : 
     356         180 :   if (auto EC = Writer.writeObject(*Layout.SB))
     357             :     return std::move(EC);
     358             : 
     359          90 :   commitFpm(Buffer, Layout, Allocator);
     360             : 
     361             :   uint32_t BlockMapOffset =
     362         360 :       msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
     363             :   Writer.setOffset(BlockMapOffset);
     364         180 :   if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
     365             :     return std::move(EC);
     366             : 
     367             :   auto DirStream = WritableMappedBlockStream::createDirectoryStream(
     368         180 :       Layout, Buffer, Allocator);
     369          90 :   BinaryStreamWriter DW(*DirStream);
     370         180 :   if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
     371             :     return std::move(EC);
     372             : 
     373         180 :   if (auto EC = DW.writeArray(Layout.StreamSizes))
     374             :     return std::move(EC);
     375             : 
     376        1244 :   for (const auto &Blocks : Layout.StreamMap) {
     377        2308 :     if (auto EC = DW.writeArray(Blocks))
     378             :       return std::move(EC);
     379             :   }
     380             : 
     381             :   return std::move(Buffer);
     382             : }

Generated by: LCOV version 1.13