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 <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 llvm::append_range(CurrentBlocks, AddedBlockList); 209 } else if (OldBlocks > NewBlocks) { 210 // For shrinking, free all the Blocks in the Block map, update the stream 211 // data, then shrink the directory. 212 uint32_t RemovedBlocks = OldBlocks - NewBlocks; 213 auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second); 214 auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks); 215 for (auto P : RemovedBlockList) 216 FreeBlocks[P] = true; 217 StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks); 218 } 219 220 StreamData[Idx].first = Size; 221 return Error::success(); 222 } 223 224 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); } 225 226 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const { 227 return StreamData[StreamIdx].first; 228 } 229 230 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const { 231 return StreamData[StreamIdx].second; 232 } 233 234 uint32_t MSFBuilder::computeDirectoryByteSize() const { 235 // The directory has the following layout, where each item is a ulittle32_t: 236 // NumStreams 237 // StreamSizes[NumStreams] 238 // StreamBlocks[NumStreams][] 239 uint32_t Size = sizeof(ulittle32_t); // NumStreams 240 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes 241 for (const auto &D : StreamData) { 242 uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize); 243 assert(ExpectedNumBlocks == D.second.size() && 244 "Unexpected number of blocks"); 245 Size += ExpectedNumBlocks * sizeof(ulittle32_t); 246 } 247 return Size; 248 } 249 250 Expected<MSFLayout> MSFBuilder::generateLayout() { 251 SuperBlock *SB = Allocator.Allocate<SuperBlock>(); 252 MSFLayout L; 253 L.SB = SB; 254 255 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic)); 256 SB->BlockMapAddr = BlockMapAddr; 257 SB->BlockSize = BlockSize; 258 SB->NumDirectoryBytes = computeDirectoryByteSize(); 259 SB->FreeBlockMapBlock = FreePageMap; 260 SB->Unknown1 = Unknown1; 261 262 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize); 263 if (NumDirectoryBlocks > DirectoryBlocks.size()) { 264 // Our hint wasn't enough to satisfy the entire directory. Allocate 265 // remaining pages. 266 std::vector<uint32_t> ExtraBlocks; 267 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size(); 268 ExtraBlocks.resize(NumExtraBlocks); 269 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks)) 270 return std::move(EC); 271 llvm::append_range(DirectoryBlocks, ExtraBlocks); 272 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) { 273 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks; 274 for (auto B : 275 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks)) 276 FreeBlocks[B] = true; 277 DirectoryBlocks.resize(NumDirectoryBlocks); 278 } 279 280 // Don't set the number of blocks in the file until after allocating Blocks 281 // for the directory, since the allocation might cause the file to need to 282 // grow. 283 SB->NumBlocks = FreeBlocks.size(); 284 285 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks); 286 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks, 287 DirBlocks); 288 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks); 289 290 // The stream sizes should be re-allocated as a stable pointer and the stream 291 // map should have each of its entries allocated as a separate stable pointer. 292 if (!StreamData.empty()) { 293 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size()); 294 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size()); 295 L.StreamMap.resize(StreamData.size()); 296 for (uint32_t I = 0; I < StreamData.size(); ++I) { 297 Sizes[I] = StreamData[I].first; 298 ulittle32_t *BlockList = 299 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size()); 300 std::uninitialized_copy_n(StreamData[I].second.begin(), 301 StreamData[I].second.size(), BlockList); 302 L.StreamMap[I] = 303 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size()); 304 } 305 } 306 307 L.FreePageMap = FreeBlocks; 308 309 return L; 310 } 311 312 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, 313 BumpPtrAllocator &Allocator) { 314 auto FpmStream = 315 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator); 316 317 // We only need to create the alt fpm stream so that it gets initialized. 318 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator, 319 true); 320 321 uint32_t BI = 0; 322 BinaryStreamWriter FpmWriter(*FpmStream); 323 while (BI < Layout.SB->NumBlocks) { 324 uint8_t ThisByte = 0; 325 for (uint32_t I = 0; I < 8; ++I) { 326 bool IsFree = 327 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true; 328 uint8_t Mask = uint8_t(IsFree) << I; 329 ThisByte |= Mask; 330 ++BI; 331 } 332 cantFail(FpmWriter.writeObject(ThisByte)); 333 } 334 assert(FpmWriter.bytesRemaining() == 0); 335 } 336 337 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path, 338 MSFLayout &Layout) { 339 Expected<MSFLayout> L = generateLayout(); 340 if (!L) 341 return L.takeError(); 342 343 Layout = std::move(*L); 344 345 uint64_t FileSize = uint64_t(Layout.SB->BlockSize) * Layout.SB->NumBlocks; 346 // Ensure that the file size is under the limit for the specified block size. 347 if (FileSize > getMaxFileSizeFromBlockSize(Layout.SB->BlockSize)) { 348 msf_error_code error_code = [](uint32_t BlockSize) { 349 switch (BlockSize) { 350 case 8192: 351 return msf_error_code::size_overflow_8192; 352 case 16384: 353 return msf_error_code::size_overflow_16384; 354 case 32768: 355 return msf_error_code::size_overflow_32768; 356 default: 357 return msf_error_code::size_overflow_4096; 358 } 359 }(Layout.SB->BlockSize); 360 361 return make_error<MSFError>( 362 error_code, 363 formatv("File size {0,1:N} too large for current PDB page size {1}", 364 FileSize, Layout.SB->BlockSize)); 365 } 366 367 uint64_t NumDirectoryBlocks = 368 bytesToBlocks(Layout.SB->NumDirectoryBytes, Layout.SB->BlockSize); 369 uint64_t DirectoryBlockMapSize = 370 NumDirectoryBlocks * sizeof(support::ulittle32_t); 371 if (DirectoryBlockMapSize > Layout.SB->BlockSize) { 372 return make_error<MSFError>(msf_error_code::stream_directory_overflow, 373 formatv("The directory block map ({0} bytes) " 374 "doesn't fit in a block ({1} bytes)", 375 DirectoryBlockMapSize, 376 Layout.SB->BlockSize)); 377 } 378 379 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize); 380 if (auto EC = OutFileOrError.takeError()) 381 return std::move(EC); 382 383 FileBufferByteStream Buffer(std::move(*OutFileOrError), 384 llvm::support::little); 385 BinaryStreamWriter Writer(Buffer); 386 387 if (auto EC = Writer.writeObject(*Layout.SB)) 388 return std::move(EC); 389 390 commitFpm(Buffer, Layout, Allocator); 391 392 uint32_t BlockMapOffset = 393 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize); 394 Writer.setOffset(BlockMapOffset); 395 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks)) 396 return std::move(EC); 397 398 auto DirStream = WritableMappedBlockStream::createDirectoryStream( 399 Layout, Buffer, Allocator); 400 BinaryStreamWriter DW(*DirStream); 401 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size())) 402 return std::move(EC); 403 404 if (auto EC = DW.writeArray(Layout.StreamSizes)) 405 return std::move(EC); 406 407 for (const auto &Blocks : Layout.StreamMap) { 408 if (auto EC = DW.writeArray(Blocks)) 409 return std::move(EC); 410 } 411 412 return std::move(Buffer); 413 } 414