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-exception 6 // 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 <memory> 25 #include <utility> 26 #include <vector> 27 28 using namespace llvm; 29 using namespace llvm::msf; 30 using namespace llvm::support; 31 32 static const uint32_t kSuperBlockBlock = 0; 33 static const uint32_t kFreePageMap0Block = 1; 34 static const uint32_t kFreePageMap1Block = 2; 35 static const uint32_t kNumReservedPages = 3; 36 37 static const uint32_t kDefaultFreePageMap = kFreePageMap1Block; 38 static const uint32_t kDefaultBlockMapAddr = kNumReservedPages; 39 40 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow, 41 BumpPtrAllocator &Allocator) 42 : Allocator(Allocator), IsGrowable(CanGrow), 43 FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize), 44 BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) { 45 FreeBlocks[kSuperBlockBlock] = false; 46 FreeBlocks[kFreePageMap0Block] = false; 47 FreeBlocks[kFreePageMap1Block] = false; 48 FreeBlocks[BlockMapAddr] = false; 49 } 50 51 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator, 52 uint32_t BlockSize, 53 uint32_t MinBlockCount, bool CanGrow) { 54 if (!isValidBlockSize(BlockSize)) 55 return make_error<MSFError>(msf_error_code::invalid_format, 56 "The requested block size is unsupported"); 57 58 return MSFBuilder(BlockSize, 59 std::max(MinBlockCount, msf::getMinimumBlockCount()), 60 CanGrow, Allocator); 61 } 62 63 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) { 64 if (Addr == BlockMapAddr) 65 return Error::success(); 66 67 if (Addr >= FreeBlocks.size()) { 68 if (!IsGrowable) 69 return make_error<MSFError>(msf_error_code::insufficient_buffer, 70 "Cannot grow the number of blocks"); 71 FreeBlocks.resize(Addr + 1, true); 72 } 73 74 if (!isBlockFree(Addr)) 75 return make_error<MSFError>( 76 msf_error_code::block_in_use, 77 "Requested block map address is already in use"); 78 FreeBlocks[BlockMapAddr] = true; 79 FreeBlocks[Addr] = false; 80 BlockMapAddr = Addr; 81 return Error::success(); 82 } 83 84 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; } 85 86 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; } 87 88 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) { 89 for (auto B : DirectoryBlocks) 90 FreeBlocks[B] = true; 91 for (auto B : DirBlocks) { 92 if (!isBlockFree(B)) { 93 return make_error<MSFError>(msf_error_code::unspecified, 94 "Attempt to reuse an allocated block"); 95 } 96 FreeBlocks[B] = false; 97 } 98 99 DirectoryBlocks = DirBlocks; 100 return Error::success(); 101 } 102 103 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks, 104 MutableArrayRef<uint32_t> Blocks) { 105 if (NumBlocks == 0) 106 return Error::success(); 107 108 uint32_t NumFreeBlocks = FreeBlocks.count(); 109 if (NumFreeBlocks < NumBlocks) { 110 if (!IsGrowable) 111 return make_error<MSFError>(msf_error_code::insufficient_buffer, 112 "There are no free Blocks in the file"); 113 uint32_t AllocBlocks = NumBlocks - NumFreeBlocks; 114 uint32_t OldBlockCount = FreeBlocks.size(); 115 uint32_t NewBlockCount = AllocBlocks + OldBlockCount; 116 uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1; 117 FreeBlocks.resize(NewBlockCount, true); 118 // If we crossed over an fpm page, we actually need to allocate 2 extra 119 // blocks for each FPM group crossed and mark both blocks from the group as 120 // used. FPM blocks are marked as allocated regardless of whether or not 121 // they ultimately describe the status of blocks in the file. This means 122 // that not only are extraneous blocks at the end of the main FPM marked as 123 // allocated, but also blocks from the alternate FPM are always marked as 124 // allocated. 125 while (NextFpmBlock < NewBlockCount) { 126 NewBlockCount += 2; 127 FreeBlocks.resize(NewBlockCount, true); 128 FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2); 129 NextFpmBlock += BlockSize; 130 } 131 } 132 133 int I = 0; 134 int Block = FreeBlocks.find_first(); 135 do { 136 assert(Block != -1 && "We ran out of Blocks!"); 137 138 uint32_t NextBlock = static_cast<uint32_t>(Block); 139 Blocks[I++] = NextBlock; 140 FreeBlocks.reset(NextBlock); 141 Block = FreeBlocks.find_next(Block); 142 } while (--NumBlocks > 0); 143 return Error::success(); 144 } 145 146 uint32_t MSFBuilder::getNumUsedBlocks() const { 147 return getTotalBlockCount() - getNumFreeBlocks(); 148 } 149 150 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); } 151 152 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); } 153 154 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; } 155 156 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size, 157 ArrayRef<uint32_t> Blocks) { 158 // Add a new stream mapped to the specified blocks. Verify that the specified 159 // blocks are both necessary and sufficient for holding the requested number 160 // of bytes, and verify that all requested blocks are free. 161 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize); 162 if (ReqBlocks != Blocks.size()) 163 return make_error<MSFError>( 164 msf_error_code::invalid_format, 165 "Incorrect number of blocks for requested stream size"); 166 for (auto Block : Blocks) { 167 if (Block >= FreeBlocks.size()) 168 FreeBlocks.resize(Block + 1, true); 169 170 if (!FreeBlocks.test(Block)) 171 return make_error<MSFError>( 172 msf_error_code::unspecified, 173 "Attempt to re-use an already allocated block"); 174 } 175 // Mark all the blocks occupied by the new stream as not free. 176 for (auto Block : Blocks) { 177 FreeBlocks.reset(Block); 178 } 179 StreamData.push_back(std::make_pair(Size, Blocks)); 180 return StreamData.size() - 1; 181 } 182 183 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) { 184 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize); 185 std::vector<uint32_t> NewBlocks; 186 NewBlocks.resize(ReqBlocks); 187 if (auto EC = allocateBlocks(ReqBlocks, NewBlocks)) 188 return std::move(EC); 189 StreamData.push_back(std::make_pair(Size, NewBlocks)); 190 return StreamData.size() - 1; 191 } 192 193 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) { 194 uint32_t OldSize = getStreamSize(Idx); 195 if (OldSize == Size) 196 return Error::success(); 197 198 uint32_t NewBlocks = bytesToBlocks(Size, BlockSize); 199 uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize); 200 201 if (NewBlocks > OldBlocks) { 202 uint32_t AddedBlocks = NewBlocks - OldBlocks; 203 // If we're growing, we have to allocate new Blocks. 204 std::vector<uint32_t> AddedBlockList; 205 AddedBlockList.resize(AddedBlocks); 206 if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList)) 207 return EC; 208 auto &CurrentBlocks = StreamData[Idx].second; 209 llvm::append_range(CurrentBlocks, AddedBlockList); 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 llvm::TimeTraceScope timeScope("MSF: Generate layout"); 253 254 SuperBlock *SB = Allocator.Allocate<SuperBlock>(); 255 MSFLayout L; 256 L.SB = SB; 257 258 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic)); 259 SB->BlockMapAddr = BlockMapAddr; 260 SB->BlockSize = BlockSize; 261 SB->NumDirectoryBytes = computeDirectoryByteSize(); 262 SB->FreeBlockMapBlock = FreePageMap; 263 SB->Unknown1 = Unknown1; 264 265 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize); 266 if (NumDirectoryBlocks > DirectoryBlocks.size()) { 267 // Our hint wasn't enough to satisfy the entire directory. Allocate 268 // remaining pages. 269 std::vector<uint32_t> ExtraBlocks; 270 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size(); 271 ExtraBlocks.resize(NumExtraBlocks); 272 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks)) 273 return std::move(EC); 274 llvm::append_range(DirectoryBlocks, ExtraBlocks); 275 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) { 276 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks; 277 for (auto B : 278 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks)) 279 FreeBlocks[B] = true; 280 DirectoryBlocks.resize(NumDirectoryBlocks); 281 } 282 283 // Don't set the number of blocks in the file until after allocating Blocks 284 // for the directory, since the allocation might cause the file to need to 285 // grow. 286 SB->NumBlocks = FreeBlocks.size(); 287 288 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks); 289 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks, 290 DirBlocks); 291 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks); 292 293 // The stream sizes should be re-allocated as a stable pointer and the stream 294 // map should have each of its entries allocated as a separate stable pointer. 295 if (!StreamData.empty()) { 296 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size()); 297 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size()); 298 L.StreamMap.resize(StreamData.size()); 299 for (uint32_t I = 0; I < StreamData.size(); ++I) { 300 Sizes[I] = StreamData[I].first; 301 ulittle32_t *BlockList = 302 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size()); 303 std::uninitialized_copy_n(StreamData[I].second.begin(), 304 StreamData[I].second.size(), BlockList); 305 L.StreamMap[I] = 306 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size()); 307 } 308 } 309 310 L.FreePageMap = FreeBlocks; 311 312 return L; 313 } 314 315 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, 316 BumpPtrAllocator &Allocator) { 317 auto FpmStream = 318 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator); 319 320 // We only need to create the alt fpm stream so that it gets initialized. 321 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator, 322 true); 323 324 uint32_t BI = 0; 325 BinaryStreamWriter FpmWriter(*FpmStream); 326 while (BI < Layout.SB->NumBlocks) { 327 uint8_t ThisByte = 0; 328 for (uint32_t I = 0; I < 8; ++I) { 329 bool IsFree = 330 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true; 331 uint8_t Mask = uint8_t(IsFree) << I; 332 ThisByte |= Mask; 333 ++BI; 334 } 335 cantFail(FpmWriter.writeObject(ThisByte)); 336 } 337 assert(FpmWriter.bytesRemaining() == 0); 338 } 339 340 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path, 341 MSFLayout &Layout) { 342 llvm::TimeTraceScope timeScope("Commit MSF"); 343 344 Expected<MSFLayout> L = generateLayout(); 345 if (!L) 346 return L.takeError(); 347 348 Layout = std::move(*L); 349 350 uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks; 351 // Ensure that the file size is under the limit for the specified block size. 352 if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) { 353 msf_error_code error_code = [](uint32_t BlockSize) { 354 switch (BlockSize) { 355 case 8192: 356 return msf_error_code::size_overflow_8192; 357 case 16384: 358 return msf_error_code::size_overflow_16384; 359 case 32768: 360 return msf_error_code::size_overflow_32768; 361 default: 362 return msf_error_code::size_overflow_4096; 363 } 364 }(Layout.SB->BlockSize); 365 366 return make_error<MSFError>( 367 error_code, 368 formatv("File size {0,1:N} too large for current PDB page size {1}", 369 FileSize, Layout.SB->BlockSize)); 370 } 371 372 uint64_t NumDirectoryBlocks = 373 bytesToBlocks(Layout.SB->NumDirectoryBytes, Layout.SB->BlockSize); 374 uint64_t DirectoryBlockMapSize = 375 NumDirectoryBlocks * sizeof(support::ulittle32_t); 376 if (DirectoryBlockMapSize > Layout.SB->BlockSize) { 377 return make_error<MSFError>(msf_error_code::stream_directory_overflow, 378 formatv("The directory block map ({0} bytes) " 379 "doesn't fit in a block ({1} bytes)", 380 DirectoryBlockMapSize, 381 Layout.SB->BlockSize)); 382 } 383 384 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize); 385 if (auto EC = OutFileOrError.takeError()) 386 return std::move(EC); 387 388 FileBufferByteStream Buffer(std::move(*OutFileOrError), 389 llvm::endianness::little); 390 BinaryStreamWriter Writer(Buffer); 391 392 if (auto EC = Writer.writeObject(*Layout.SB)) 393 return std::move(EC); 394 395 commitFpm(Buffer, Layout, Allocator); 396 397 uint32_t BlockMapOffset = 398 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize); 399 Writer.setOffset(BlockMapOffset); 400 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks)) 401 return std::move(EC); 402 403 auto DirStream = WritableMappedBlockStream::createDirectoryStream( 404 Layout, Buffer, Allocator); 405 BinaryStreamWriter DW(*DirStream); 406 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size())) 407 return std::move(EC); 408 409 if (auto EC = DW.writeArray(Layout.StreamSizes)) 410 return std::move(EC); 411 412 for (const auto &Blocks : Layout.StreamMap) { 413 if (auto EC = DW.writeArray(Blocks)) 414 return std::move(EC); 415 } 416 417 return std::move(Buffer); 418 } 419