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