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 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 CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(), 209 AddedBlockList.end()); 210 } 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 uint32_t RemovedBlocks = OldBlocks - NewBlocks; 214 auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second); 215 auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks); 216 for (auto P : RemovedBlockList) 217 FreeBlocks[P] = true; 218 StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks); 219 } 220 221 StreamData[Idx].first = Size; 222 return Error::success(); 223 } 224 225 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); } 226 227 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const { 228 return StreamData[StreamIdx].first; 229 } 230 231 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const { 232 return StreamData[StreamIdx].second; 233 } 234 235 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 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes 242 for (const auto &D : StreamData) { 243 uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize); 244 assert(ExpectedNumBlocks == D.second.size() && 245 "Unexpected number of blocks"); 246 Size += ExpectedNumBlocks * sizeof(ulittle32_t); 247 } 248 return Size; 249 } 250 251 Expected<MSFLayout> MSFBuilder::generateLayout() { 252 SuperBlock *SB = Allocator.Allocate<SuperBlock>(); 253 MSFLayout L; 254 L.SB = SB; 255 256 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic)); 257 SB->BlockMapAddr = BlockMapAddr; 258 SB->BlockSize = BlockSize; 259 SB->NumDirectoryBytes = computeDirectoryByteSize(); 260 SB->FreeBlockMapBlock = FreePageMap; 261 SB->Unknown1 = Unknown1; 262 263 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize); 264 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 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size(); 269 ExtraBlocks.resize(NumExtraBlocks); 270 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks)) 271 return std::move(EC); 272 DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(), 273 ExtraBlocks.end()); 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 Blocks 283 // for the directory, since the allocation might cause the file to need to 284 // grow. 285 SB->NumBlocks = FreeBlocks.size(); 286 287 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks); 288 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks, 289 DirBlocks); 290 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 if (!StreamData.empty()) { 295 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size()); 296 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size()); 297 L.StreamMap.resize(StreamData.size()); 298 for (uint32_t I = 0; I < StreamData.size(); ++I) { 299 Sizes[I] = StreamData[I].first; 300 ulittle32_t *BlockList = 301 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size()); 302 std::uninitialized_copy_n(StreamData[I].second.begin(), 303 StreamData[I].second.size(), BlockList); 304 L.StreamMap[I] = 305 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size()); 306 } 307 } 308 309 L.FreePageMap = FreeBlocks; 310 311 return L; 312 } 313 314 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, 315 BumpPtrAllocator &Allocator) { 316 auto FpmStream = 317 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator); 318 319 // We only need to create the alt fpm stream so that it gets initialized. 320 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator, 321 true); 322 323 uint32_t BI = 0; 324 BinaryStreamWriter FpmWriter(*FpmStream); 325 while (BI < Layout.SB->NumBlocks) { 326 uint8_t ThisByte = 0; 327 for (uint32_t I = 0; I < 8; ++I) { 328 bool IsFree = 329 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true; 330 uint8_t Mask = uint8_t(IsFree) << I; 331 ThisByte |= Mask; 332 ++BI; 333 } 334 cantFail(FpmWriter.writeObject(ThisByte)); 335 } 336 assert(FpmWriter.bytesRemaining() == 0); 337 } 338 339 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path, 340 MSFLayout &Layout) { 341 Expected<MSFLayout> L = generateLayout(); 342 if (!L) 343 return L.takeError(); 344 345 Layout = std::move(*L); 346 347 uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks; 348 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize); 349 if (auto EC = OutFileOrError.takeError()) 350 return std::move(EC); 351 352 FileBufferByteStream Buffer(std::move(*OutFileOrError), 353 llvm::support::little); 354 BinaryStreamWriter Writer(Buffer); 355 356 if (auto EC = Writer.writeObject(*Layout.SB)) 357 return std::move(EC); 358 359 commitFpm(Buffer, Layout, Allocator); 360 361 uint32_t BlockMapOffset = 362 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize); 363 Writer.setOffset(BlockMapOffset); 364 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks)) 365 return std::move(EC); 366 367 auto DirStream = WritableMappedBlockStream::createDirectoryStream( 368 Layout, Buffer, Allocator); 369 BinaryStreamWriter DW(*DirStream); 370 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size())) 371 return std::move(EC); 372 373 if (auto EC = DW.writeArray(Layout.StreamSizes)) 374 return std::move(EC); 375 376 for (const auto &Blocks : Layout.StreamMap) { 377 if (auto EC = DW.writeArray(Blocks)) 378 return std::move(EC); 379 } 380 381 return std::move(Buffer); 382 } 383