contrib/llvm/lib/DebugInfo/MSF/MSFBuilder.cpp

   1 //
   2 //                     The LLVM Compiler Infrastructure
   3 //
   4 // This file is distributed under the University of Illinois Open Source
   5 // License. See LICENSE.TXT for details.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/MSF/MSFBuilder.h"
  10 #include "llvm/DebugInfo/MSF/MSFError.h"
  11
  12 using namespace llvm;
  13 using namespace llvm::msf;
  14 using namespace llvm::support;
  15
  16 namespace {
  17 const uint32_t kSuperBlockBlock = 0;
  18 const uint32_t kFreePageMap0Block = 1;
  19 const uint32_t kFreePageMap1Block = 2;
  20 const uint32_t kNumReservedPages = 3;
  21
  22 const uint32_t kDefaultFreePageMap = kFreePageMap0Block;
  23 const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
  24 }
  25
  26 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
  27                        BumpPtrAllocator &Allocator)
  28     : Allocator(Allocator), IsGrowable(CanGrow),
  29       FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
  30       MininumBlocks(MinBlockCount), BlockMapAddr(kDefaultBlockMapAddr),
  31       FreeBlocks(MinBlockCount, true) {
  32   FreeBlocks[kSuperBlockBlock] = false;
  33   FreeBlocks[kFreePageMap0Block] = false;
  34   FreeBlocks[kFreePageMap1Block] = false;
  35   FreeBlocks[BlockMapAddr] = false;
  36 }
  37
  38 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
  39                                         uint32_t BlockSize,
  40                                         uint32_t MinBlockCount, bool CanGrow) {
  41   if (!isValidBlockSize(BlockSize))
  42     return make_error<MSFError>(msf_error_code::invalid_format,
  43                                 "The requested block size is unsupported");
  44
  45   return MSFBuilder(BlockSize,
  46                     std::max(MinBlockCount, msf::getMinimumBlockCount()),
  47                     CanGrow, Allocator);
  48 }
  49
  50 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
  51   if (Addr == BlockMapAddr)
  52     return Error::success();
  53
  54   if (Addr >= FreeBlocks.size()) {
  55     if (!IsGrowable)
  56       return make_error<MSFError>(msf_error_code::insufficient_buffer,
  57                                   "Cannot grow the number of blocks");
  58     FreeBlocks.resize(Addr + 1, true);
  59   }
  60
  61   if (!isBlockFree(Addr))
  62     return make_error<MSFError>(
  63         msf_error_code::block_in_use,
  64         "Requested block map address is already in use");
  65   FreeBlocks[BlockMapAddr] = true;
  66   FreeBlocks[Addr] = false;
  67   BlockMapAddr = Addr;
  68   return Error::success();
  69 }
  70
  71 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
  72
  73 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
  74
  75 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
  76   for (auto B : DirectoryBlocks)
  77     FreeBlocks[B] = true;
  78   for (auto B : DirBlocks) {
  79     if (!isBlockFree(B)) {
  80       return make_error<MSFError>(msf_error_code::unspecified,
  81                                   "Attempt to reuse an allocated block");
  82     }
  83     FreeBlocks[B] = false;
  84   }
  85
  86   DirectoryBlocks = DirBlocks;
  87   return Error::success();
  88 }
  89
  90 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
  91                                  MutableArrayRef<uint32_t> Blocks) {
  92   if (NumBlocks == 0)
  93     return Error::success();
  94
  95   uint32_t NumFreeBlocks = FreeBlocks.count();
  96   if (NumFreeBlocks < NumBlocks) {
  97     if (!IsGrowable)
  98       return make_error<MSFError>(msf_error_code::insufficient_buffer,
  99                                   "There are no free Blocks in the file");
 100     uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
 101     FreeBlocks.resize(AllocBlocks + FreeBlocks.size(), true);
 102   }
 103
 104   int I = 0;
 105   int Block = FreeBlocks.find_first();
 106   do {
 107     assert(Block != -1 && "We ran out of Blocks!");
 108
 109     uint32_t NextBlock = static_cast<uint32_t>(Block);
 110     Blocks[I++] = NextBlock;
 111     FreeBlocks.reset(NextBlock);
 112     Block = FreeBlocks.find_next(Block);
 113   } while (--NumBlocks > 0);
 114   return Error::success();
 115 }
 116
 117 uint32_t MSFBuilder::getNumUsedBlocks() const {
 118   return getTotalBlockCount() - getNumFreeBlocks();
 119 }
 120
 121 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
 122
 123 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
 124
 125 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
 126
 127 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
 128                                          ArrayRef<uint32_t> Blocks) {
 129   // Add a new stream mapped to the specified blocks.  Verify that the specified
 130   // blocks are both necessary and sufficient for holding the requested number
 131   // of bytes, and verify that all requested blocks are free.
 132   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
 133   if (ReqBlocks != Blocks.size())
 134     return make_error<MSFError>(
 135         msf_error_code::invalid_format,
 136         "Incorrect number of blocks for requested stream size");
 137   for (auto Block : Blocks) {
 138     if (Block >= FreeBlocks.size())
 139       FreeBlocks.resize(Block + 1, true);
 140
 141     if (!FreeBlocks.test(Block))
 142       return make_error<MSFError>(
 143           msf_error_code::unspecified,
 144           "Attempt to re-use an already allocated block");
 145   }
 146   // Mark all the blocks occupied by the new stream as not free.
 147   for (auto Block : Blocks) {
 148     FreeBlocks.reset(Block);
 149   }
 150   StreamData.push_back(std::make_pair(Size, Blocks));
 151   return StreamData.size() - 1;
 152 }
 153
 154 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
 155   uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
 156   std::vector<uint32_t> NewBlocks;
 157   NewBlocks.resize(ReqBlocks);
 158   if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
 159     return std::move(EC);
 160   StreamData.push_back(std::make_pair(Size, NewBlocks));
 161   return StreamData.size() - 1;
 162 }
 163
 164 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
 165   uint32_t OldSize = getStreamSize(Idx);
 166   if (OldSize == Size)
 167     return Error::success();
 168
 169   uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
 170   uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
 171
 172   if (NewBlocks > OldBlocks) {
 173     uint32_t AddedBlocks = NewBlocks - OldBlocks;
 174     // If we're growing, we have to allocate new Blocks.
 175     std::vector<uint32_t> AddedBlockList;
 176     AddedBlockList.resize(AddedBlocks);
 177     if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
 178       return EC;
 179     auto &CurrentBlocks = StreamData[Idx].second;
 180     CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
 181                          AddedBlockList.end());
 182   } else if (OldBlocks > NewBlocks) {
 183     // For shrinking, free all the Blocks in the Block map, update the stream
 184     // data, then shrink the directory.
 185     uint32_t RemovedBlocks = OldBlocks - NewBlocks;
 186     auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
 187     auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
 188     for (auto P : RemovedBlockList)
 189       FreeBlocks[P] = true;
 190     StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
 191   }
 192
 193   StreamData[Idx].first = Size;
 194   return Error::success();
 195 }
 196
 197 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
 198
 199 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
 200   return StreamData[StreamIdx].first;
 201 }
 202
 203 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
 204   return StreamData[StreamIdx].second;
 205 }
 206
 207 uint32_t MSFBuilder::computeDirectoryByteSize() const {
 208   // The directory has the following layout, where each item is a ulittle32_t:
 209   //    NumStreams
 210   //    StreamSizes[NumStreams]
 211   //    StreamBlocks[NumStreams][]
 212   uint32_t Size = sizeof(ulittle32_t);             // NumStreams
 213   Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
 214   for (const auto &D : StreamData) {
 215     uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
 216     assert(ExpectedNumBlocks == D.second.size() &&
 217            "Unexpected number of blocks");
 218     Size += ExpectedNumBlocks * sizeof(ulittle32_t);
 219   }
 220   return Size;
 221 }
 222
 223 Expected<MSFLayout> MSFBuilder::build() {
 224   SuperBlock *SB = Allocator.Allocate<SuperBlock>();
 225   MSFLayout L;
 226   L.SB = SB;
 227
 228   std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
 229   SB->BlockMapAddr = BlockMapAddr;
 230   SB->BlockSize = BlockSize;
 231   SB->NumDirectoryBytes = computeDirectoryByteSize();
 232   SB->FreeBlockMapBlock = FreePageMap;
 233   SB->Unknown1 = Unknown1;
 234
 235   uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
 236   if (NumDirectoryBlocks > DirectoryBlocks.size()) {
 237     // Our hint wasn't enough to satisfy the entire directory.  Allocate
 238     // remaining pages.
 239     std::vector<uint32_t> ExtraBlocks;
 240     uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
 241     ExtraBlocks.resize(NumExtraBlocks);
 242     if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
 243       return std::move(EC);
 244     DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
 245                            ExtraBlocks.end());
 246   } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
 247     uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
 248     for (auto B :
 249          ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
 250       FreeBlocks[B] = true;
 251     DirectoryBlocks.resize(NumDirectoryBlocks);
 252   }
 253
 254   // Don't set the number of blocks in the file until after allocating Blocks
 255   // for the directory, since the allocation might cause the file to need to
 256   // grow.
 257   SB->NumBlocks = FreeBlocks.size();
 258
 259   ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
 260   std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
 261                             DirBlocks);
 262   L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
 263
 264   // The stream sizes should be re-allocated as a stable pointer and the stream
 265   // map should have each of its entries allocated as a separate stable pointer.
 266   if (StreamData.size() > 0) {
 267     ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
 268     L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
 269     L.StreamMap.resize(StreamData.size());
 270     for (uint32_t I = 0; I < StreamData.size(); ++I) {
 271       Sizes[I] = StreamData[I].first;
 272       ulittle32_t *BlockList =
 273           Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
 274       std::uninitialized_copy_n(StreamData[I].second.begin(),
 275                                 StreamData[I].second.size(), BlockList);
 276       L.StreamMap[I] =
 277           ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
 278     }
 279   }
 280
 281   return L;
 282 }