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 CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(), 208 AddedBlockList.end()); 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 DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(), 272 ExtraBlocks.end()); 273 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) { 274 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks; 275 for (auto B : 276 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks)) 277 FreeBlocks[B] = true; 278 DirectoryBlocks.resize(NumDirectoryBlocks); 279 } 280 281 // Don't set the number of blocks in the file until after allocating Blocks 282 // for the directory, since the allocation might cause the file to need to 283 // grow. 284 SB->NumBlocks = FreeBlocks.size(); 285 286 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks); 287 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks, 288 DirBlocks); 289 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks); 290 291 // The stream sizes should be re-allocated as a stable pointer and the stream 292 // map should have each of its entries allocated as a separate stable pointer. 293 if (!StreamData.empty()) { 294 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size()); 295 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size()); 296 L.StreamMap.resize(StreamData.size()); 297 for (uint32_t I = 0; I < StreamData.size(); ++I) { 298 Sizes[I] = StreamData[I].first; 299 ulittle32_t *BlockList = 300 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size()); 301 std::uninitialized_copy_n(StreamData[I].second.begin(), 302 StreamData[I].second.size(), BlockList); 303 L.StreamMap[I] = 304 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size()); 305 } 306 } 307 308 L.FreePageMap = FreeBlocks; 309 310 return L; 311 } 312 313 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout, 314 BumpPtrAllocator &Allocator) { 315 auto FpmStream = 316 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator); 317 318 // We only need to create the alt fpm stream so that it gets initialized. 319 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator, 320 true); 321 322 uint32_t BI = 0; 323 BinaryStreamWriter FpmWriter(*FpmStream); 324 while (BI < Layout.SB->NumBlocks) { 325 uint8_t ThisByte = 0; 326 for (uint32_t I = 0; I < 8; ++I) { 327 bool IsFree = 328 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true; 329 uint8_t Mask = uint8_t(IsFree) << I; 330 ThisByte |= Mask; 331 ++BI; 332 } 333 cantFail(FpmWriter.writeObject(ThisByte)); 334 } 335 assert(FpmWriter.bytesRemaining() == 0); 336 } 337 338 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path, 339 MSFLayout &Layout) { 340 Expected<MSFLayout> L = generateLayout(); 341 if (!L) 342 return L.takeError(); 343 344 Layout = std::move(*L); 345 346 uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks; 347 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize); 348 if (auto EC = OutFileOrError.takeError()) 349 return std::move(EC); 350 351 FileBufferByteStream Buffer(std::move(*OutFileOrError), 352 llvm::support::little); 353 BinaryStreamWriter Writer(Buffer); 354 355 if (auto EC = Writer.writeObject(*Layout.SB)) 356 return std::move(EC); 357 358 commitFpm(Buffer, Layout, Allocator); 359 360 uint32_t BlockMapOffset = 361 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize); 362 Writer.setOffset(BlockMapOffset); 363 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks)) 364 return std::move(EC); 365 366 auto DirStream = WritableMappedBlockStream::createDirectoryStream( 367 Layout, Buffer, Allocator); 368 BinaryStreamWriter DW(*DirStream); 369 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size())) 370 return std::move(EC); 371 372 if (auto EC = DW.writeArray(Layout.StreamSizes)) 373 return std::move(EC); 374 375 for (const auto &Blocks : Layout.StreamMap) { 376 if (auto EC = DW.writeArray(Blocks)) 377 return std::move(EC); 378 } 379 380 return std::move(Buffer); 381 } 382