LCOV - code coverage report
Current view: top level - lib/DebugInfo/MSF - MSFBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 117 127 92.1 %
Date: 2018-06-17 00:07:59 Functions: 16 19 84.2 %
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/ADT/ArrayRef.h"
      11             : #include "llvm/DebugInfo/MSF/MSFBuilder.h"
      12             : #include "llvm/DebugInfo/MSF/MSFError.h"
      13             : #include "llvm/Support/Endian.h"
      14             : #include "llvm/Support/Error.h"
      15             : #include <algorithm>
      16             : #include <cassert>
      17             : #include <cstdint>
      18             : #include <cstring>
      19             : #include <memory>
      20             : #include <utility>
      21             : #include <vector>
      22             : 
      23             : using namespace llvm;
      24             : using namespace llvm::msf;
      25             : using namespace llvm::support;
      26             : 
      27             : static const uint32_t kSuperBlockBlock = 0;
      28             : static const uint32_t kFreePageMap0Block = 1;
      29             : static const uint32_t kFreePageMap1Block = 2;
      30             : static const uint32_t kNumReservedPages = 3;
      31             : 
      32             : static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
      33             : static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
      34             : 
      35         105 : MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
      36         105 :                        BumpPtrAllocator &Allocator)
      37             :     : Allocator(Allocator), IsGrowable(CanGrow),
      38             :       FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
      39         105 :       BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
      40             :   FreeBlocks[kSuperBlockBlock] = false;
      41             :   FreeBlocks[kFreePageMap0Block] = false;
      42             :   FreeBlocks[kFreePageMap1Block] = false;
      43         105 :   FreeBlocks[BlockMapAddr] = false;
      44         105 : }
      45             : 
      46         105 : Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
      47             :                                         uint32_t BlockSize,
      48             :                                         uint32_t MinBlockCount, bool CanGrow) {
      49             :   if (!isValidBlockSize(BlockSize))
      50             :     return make_error<MSFError>(msf_error_code::invalid_format,
      51             :                                 "The requested block size is unsupported");
      52             : 
      53         315 :   return MSFBuilder(BlockSize,
      54         210 :                     std::max(MinBlockCount, msf::getMinimumBlockCount()),
      55             :                     CanGrow, Allocator);
      56             : }
      57             : 
      58           0 : Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
      59           0 :   if (Addr == BlockMapAddr)
      60             :     return Error::success();
      61             : 
      62           0 :   if (Addr >= FreeBlocks.size()) {
      63           0 :     if (!IsGrowable)
      64             :       return make_error<MSFError>(msf_error_code::insufficient_buffer,
      65             :                                   "Cannot grow the number of blocks");
      66           0 :     FreeBlocks.resize(Addr + 1, true);
      67             :   }
      68             : 
      69           0 :   if (!isBlockFree(Addr))
      70             :     return make_error<MSFError>(
      71             :         msf_error_code::block_in_use,
      72             :         "Requested block map address is already in use");
      73           0 :   FreeBlocks[BlockMapAddr] = true;
      74             :   FreeBlocks[Addr] = false;
      75           0 :   BlockMapAddr = Addr;
      76             :   return Error::success();
      77             : }
      78             : 
      79           0 : void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
      80             : 
      81           0 : void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
      82             : 
      83           3 : Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
      84           3 :   for (auto B : DirectoryBlocks)
      85             :     FreeBlocks[B] = true;
      86          11 :   for (auto B : DirBlocks) {
      87           4 :     if (!isBlockFree(B)) {
      88             :       return make_error<MSFError>(msf_error_code::unspecified,
      89             :                                   "Attempt to reuse an allocated block");
      90             :     }
      91             :     FreeBlocks[B] = false;
      92             :   }
      93             : 
      94           6 :   DirectoryBlocks = DirBlocks;
      95             :   return Error::success();
      96             : }
      97             : 
      98        1624 : Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
      99             :                                  MutableArrayRef<uint32_t> Blocks) {
     100        1624 :   if (NumBlocks == 0)
     101             :     return Error::success();
     102             : 
     103             :   uint32_t NumFreeBlocks = FreeBlocks.count();
     104        1083 :   if (NumFreeBlocks < NumBlocks) {
     105        1083 :     if (!IsGrowable)
     106             :       return make_error<MSFError>(msf_error_code::insufficient_buffer,
     107             :                                   "There are no free Blocks in the file");
     108        1083 :     uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
     109             :     uint32_t OldBlockCount = FreeBlocks.size();
     110        1083 :     uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
     111        2166 :     uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
     112        1083 :     FreeBlocks.resize(NewBlockCount, true);
     113             :     // If we crossed over an fpm page, we actually need to allocate 2 extra
     114             :     // blocks for each FPM group crossed and mark both blocks from the group as
     115             :     // used.  FPM blocks are marked as allocated regardless of whether or not
     116             :     // they ultimately describe the status of blocks in the file.  This means
     117             :     // that not only are extraneous blocks at the end of the main FPM marked as
     118             :     // allocated, but also blocks from the alternate FPM are always marked as
     119             :     // allocated.
     120        1089 :     while (NextFpmBlock < NewBlockCount) {
     121           3 :       NewBlockCount += 2;
     122           3 :       FreeBlocks.resize(NewBlockCount, true);
     123           3 :       FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
     124           3 :       NextFpmBlock += BlockSize;
     125             :     }
     126             :   }
     127             : 
     128             :   int I = 0;
     129        1083 :   int Block = FreeBlocks.find_first();
     130             :   do {
     131             :     assert(Block != -1 && "We ran out of Blocks!");
     132             : 
     133       15563 :     uint32_t NextBlock = static_cast<uint32_t>(Block);
     134       31126 :     Blocks[I++] = NextBlock;
     135             :     FreeBlocks.reset(NextBlock);
     136             :     Block = FreeBlocks.find_next(Block);
     137       15563 :   } while (--NumBlocks > 0);
     138             :   return Error::success();
     139             : }
     140             : 
     141           4 : uint32_t MSFBuilder::getNumUsedBlocks() const {
     142           4 :   return getTotalBlockCount() - getNumFreeBlocks();
     143             : }
     144             : 
     145          16 : uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
     146             : 
     147           4 : uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
     148             : 
     149          46 : bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
     150             : 
     151           3 : Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
     152             :                                          ArrayRef<uint32_t> Blocks) {
     153             :   // Add a new stream mapped to the specified blocks.  Verify that the specified
     154             :   // blocks are both necessary and sufficient for holding the requested number
     155             :   // of bytes, and verify that all requested blocks are free.
     156           3 :   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
     157           3 :   if (ReqBlocks != Blocks.size())
     158             :     return make_error<MSFError>(
     159             :         msf_error_code::invalid_format,
     160             :         "Incorrect number of blocks for requested stream size");
     161          23 :   for (auto Block : Blocks) {
     162          11 :     if (Block >= FreeBlocks.size())
     163           1 :       FreeBlocks.resize(Block + 1, true);
     164             : 
     165          11 :     if (!FreeBlocks.test(Block))
     166             :       return make_error<MSFError>(
     167             :           msf_error_code::unspecified,
     168             :           "Attempt to re-use an already allocated block");
     169             :   }
     170             :   // Mark all the blocks occupied by the new stream as not free.
     171          22 :   for (auto Block : Blocks) {
     172             :     FreeBlocks.reset(Block);
     173             :   }
     174           4 :   StreamData.push_back(std::make_pair(Size, Blocks));
     175           4 :   return StreamData.size() - 1;
     176             : }
     177             : 
     178        1170 : Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
     179        2340 :   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
     180             :   std::vector<uint32_t> NewBlocks;
     181        1170 :   NewBlocks.resize(ReqBlocks);
     182        2340 :   if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
     183             :     return std::move(EC);
     184        2340 :   StreamData.push_back(std::make_pair(Size, NewBlocks));
     185        2340 :   return StreamData.size() - 1;
     186             : }
     187             : 
     188         451 : Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
     189         451 :   uint32_t OldSize = getStreamSize(Idx);
     190         451 :   if (OldSize == Size)
     191             :     return Error::success();
     192             : 
     193         722 :   uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
     194         722 :   uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
     195             : 
     196         361 :   if (NewBlocks > OldBlocks) {
     197         358 :     uint32_t AddedBlocks = NewBlocks - OldBlocks;
     198             :     // If we're growing, we have to allocate new Blocks.
     199             :     std::vector<uint32_t> AddedBlockList;
     200         358 :     AddedBlockList.resize(AddedBlocks);
     201         716 :     if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
     202             :       return EC;
     203         716 :     auto &CurrentBlocks = StreamData[Idx].second;
     204         358 :     CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
     205         358 :                          AddedBlockList.end());
     206           3 :   } else if (OldBlocks > NewBlocks) {
     207             :     // For shrinking, free all the Blocks in the Block map, update the stream
     208             :     // data, then shrink the directory.
     209           1 :     uint32_t RemovedBlocks = OldBlocks - NewBlocks;
     210           1 :     auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
     211             :     auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
     212           3 :     for (auto P : RemovedBlockList)
     213             :       FreeBlocks[P] = true;
     214           4 :     StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
     215             :   }
     216             : 
     217         722 :   StreamData[Idx].first = Size;
     218             :   return Error::success();
     219             : }
     220             : 
     221           2 : uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
     222             : 
     223         460 : uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
     224         920 :   return StreamData[StreamIdx].first;
     225             : }
     226             : 
     227           9 : ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
     228          18 :   return StreamData[StreamIdx].second;
     229             : }
     230             : 
     231          98 : uint32_t MSFBuilder::computeDirectoryByteSize() const {
     232             :   // The directory has the following layout, where each item is a ulittle32_t:
     233             :   //    NumStreams
     234             :   //    StreamSizes[NumStreams]
     235             :   //    StreamBlocks[NumStreams][]
     236             :   uint32_t Size = sizeof(ulittle32_t);             // NumStreams
     237         196 :   Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
     238        1261 :   for (const auto &D : StreamData) {
     239        2326 :     uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
     240             :     assert(ExpectedNumBlocks == D.second.size() &&
     241             :            "Unexpected number of blocks");
     242        1163 :     Size += ExpectedNumBlocks * sizeof(ulittle32_t);
     243             :   }
     244          98 :   return Size;
     245             : }
     246             : 
     247          98 : Expected<MSFLayout> MSFBuilder::build() {
     248          98 :   SuperBlock *SB = Allocator.Allocate<SuperBlock>();
     249          98 :   MSFLayout L;
     250          98 :   L.SB = SB;
     251             : 
     252          98 :   std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
     253          98 :   SB->BlockMapAddr = BlockMapAddr;
     254          98 :   SB->BlockSize = BlockSize;
     255          98 :   SB->NumDirectoryBytes = computeDirectoryByteSize();
     256          98 :   SB->FreeBlockMapBlock = FreePageMap;
     257          98 :   SB->Unknown1 = Unknown1;
     258             : 
     259         294 :   uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
     260         196 :   if (NumDirectoryBlocks > DirectoryBlocks.size()) {
     261             :     // Our hint wasn't enough to satisfy the entire directory.  Allocate
     262             :     // remaining pages.
     263             :     std::vector<uint32_t> ExtraBlocks;
     264          96 :     uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
     265          96 :     ExtraBlocks.resize(NumExtraBlocks);
     266         192 :     if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
     267             :       return std::move(EC);
     268          96 :     DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
     269         192 :                            ExtraBlocks.end());
     270           2 :   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
     271           1 :     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
     272           2 :     for (auto B :
     273           3 :          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
     274             :       FreeBlocks[B] = true;
     275           1 :     DirectoryBlocks.resize(NumDirectoryBlocks);
     276             :   }
     277             : 
     278             :   // Don't set the number of blocks in the file until after allocating Blocks
     279             :   // for the directory, since the allocation might cause the file to need to
     280             :   // grow.
     281          98 :   SB->NumBlocks = FreeBlocks.size();
     282             : 
     283          98 :   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
     284             :   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
     285             :                             DirBlocks);
     286          98 :   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
     287             : 
     288             :   // The stream sizes should be re-allocated as a stable pointer and the stream
     289             :   // map should have each of its entries allocated as a separate stable pointer.
     290          98 :   if (!StreamData.empty()) {
     291          97 :     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
     292         194 :     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
     293          97 :     L.StreamMap.resize(StreamData.size());
     294        3683 :     for (uint32_t I = 0; I < StreamData.size(); ++I) {
     295        1163 :       Sizes[I] = StreamData[I].first;
     296             :       ulittle32_t *BlockList =
     297        1163 :           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
     298        1163 :       std::uninitialized_copy_n(StreamData[I].second.begin(),
     299        1163 :                                 StreamData[I].second.size(), BlockList);
     300        2326 :       L.StreamMap[I] =
     301        1163 :           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
     302             :     }
     303             :   }
     304             : 
     305          98 :   L.FreePageMap = FreeBlocks;
     306             : 
     307             :   return L;
     308             : }

Generated by: LCOV version 1.13