1 //===- MappedBlockStream.cpp - Reads stream data from an MSF file ---------===// 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/MappedBlockStream.h" 10 #include "llvm/ADT/ArrayRef.h" 11 #include "llvm/DebugInfo/MSF/MSFCommon.h" 12 #include "llvm/Support/BinaryStreamWriter.h" 13 #include "llvm/Support/Error.h" 14 #include "llvm/Support/MathExtras.h" 15 #include <algorithm> 16 #include <cassert> 17 #include <cstdint> 18 #include <cstring> 19 #include <utility> 20 #include <vector> 21 22 using namespace llvm; 23 using namespace llvm::msf; 24 25 namespace { 26 27 template <typename Base> class MappedBlockStreamImpl : public Base { 28 public: 29 template <typename... Args> 30 MappedBlockStreamImpl(Args &&... Params) 31 : Base(std::forward<Args>(Params)...) {} 32 }; 33 34 } // end anonymous namespace 35 36 using Interval = std::pair<uint64_t, uint64_t>; 37 38 static Interval intersect(const Interval &I1, const Interval &I2) { 39 return std::make_pair(std::max(I1.first, I2.first), 40 std::min(I1.second, I2.second)); 41 } 42 43 MappedBlockStream::MappedBlockStream(uint32_t BlockSize, 44 const MSFStreamLayout &Layout, 45 BinaryStreamRef MsfData, 46 BumpPtrAllocator &Allocator) 47 : BlockSize(BlockSize), StreamLayout(Layout), MsfData(MsfData), 48 Allocator(Allocator) {} 49 50 std::unique_ptr<MappedBlockStream> MappedBlockStream::createStream( 51 uint32_t BlockSize, const MSFStreamLayout &Layout, BinaryStreamRef MsfData, 52 BumpPtrAllocator &Allocator) { 53 return std::make_unique<MappedBlockStreamImpl<MappedBlockStream>>( 54 BlockSize, Layout, MsfData, Allocator); 55 } 56 57 std::unique_ptr<MappedBlockStream> MappedBlockStream::createIndexedStream( 58 const MSFLayout &Layout, BinaryStreamRef MsfData, uint32_t StreamIndex, 59 BumpPtrAllocator &Allocator) { 60 assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index"); 61 MSFStreamLayout SL; 62 SL.Blocks = Layout.StreamMap[StreamIndex]; 63 SL.Length = Layout.StreamSizes[StreamIndex]; 64 return std::make_unique<MappedBlockStreamImpl<MappedBlockStream>>( 65 Layout.SB->BlockSize, SL, MsfData, Allocator); 66 } 67 68 std::unique_ptr<MappedBlockStream> 69 MappedBlockStream::createDirectoryStream(const MSFLayout &Layout, 70 BinaryStreamRef MsfData, 71 BumpPtrAllocator &Allocator) { 72 MSFStreamLayout SL; 73 SL.Blocks = Layout.DirectoryBlocks; 74 SL.Length = Layout.SB->NumDirectoryBytes; 75 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator); 76 } 77 78 std::unique_ptr<MappedBlockStream> 79 MappedBlockStream::createFpmStream(const MSFLayout &Layout, 80 BinaryStreamRef MsfData, 81 BumpPtrAllocator &Allocator) { 82 MSFStreamLayout SL(getFpmStreamLayout(Layout)); 83 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator); 84 } 85 86 Error MappedBlockStream::readBytes(uint64_t Offset, uint64_t Size, 87 ArrayRef<uint8_t> &Buffer) { 88 // Make sure we aren't trying to read beyond the end of the stream. 89 if (auto EC = checkOffsetForRead(Offset, Size)) 90 return EC; 91 92 if (tryReadContiguously(Offset, Size, Buffer)) 93 return Error::success(); 94 95 auto CacheIter = CacheMap.find(Offset); 96 if (CacheIter != CacheMap.end()) { 97 // Try to find an alloc that was large enough for this request. 98 for (auto &Entry : CacheIter->second) { 99 if (Entry.size() >= Size) { 100 Buffer = Entry.slice(0, Size); 101 return Error::success(); 102 } 103 } 104 } 105 106 // We couldn't find a buffer that started at the correct offset (the most 107 // common scenario). Try to see if there is a buffer that starts at some 108 // other offset but overlaps the desired range. 109 for (auto &CacheItem : CacheMap) { 110 Interval RequestExtent = std::make_pair(Offset, Offset + Size); 111 112 // We already checked this one on the fast path above. 113 if (CacheItem.first == Offset) 114 continue; 115 // If the initial extent of the cached item is beyond the ending extent 116 // of the request, there is no overlap. 117 if (CacheItem.first >= Offset + Size) 118 continue; 119 120 // We really only have to check the last item in the list, since we append 121 // in order of increasing length. 122 if (CacheItem.second.empty()) 123 continue; 124 125 auto CachedAlloc = CacheItem.second.back(); 126 // If the initial extent of the request is beyond the ending extent of 127 // the cached item, there is no overlap. 128 Interval CachedExtent = 129 std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size()); 130 if (RequestExtent.first >= CachedExtent.first + CachedExtent.second) 131 continue; 132 133 Interval Intersection = intersect(CachedExtent, RequestExtent); 134 // Only use this if the entire request extent is contained in the cached 135 // extent. 136 if (Intersection != RequestExtent) 137 continue; 138 139 uint64_t CacheRangeOffset = 140 AbsoluteDifference(CachedExtent.first, Intersection.first); 141 Buffer = CachedAlloc.slice(CacheRangeOffset, Size); 142 return Error::success(); 143 } 144 145 // Otherwise allocate a large enough buffer in the pool, memcpy the data 146 // into it, and return an ArrayRef to that. Do not touch existing pool 147 // allocations, as existing clients may be holding a pointer which must 148 // not be invalidated. 149 uint8_t *WriteBuffer = static_cast<uint8_t *>(Allocator.Allocate(Size, 8)); 150 if (auto EC = readBytes(Offset, MutableArrayRef<uint8_t>(WriteBuffer, Size))) 151 return EC; 152 153 if (CacheIter != CacheMap.end()) { 154 CacheIter->second.emplace_back(WriteBuffer, Size); 155 } else { 156 std::vector<CacheEntry> List; 157 List.emplace_back(WriteBuffer, Size); 158 CacheMap.insert(std::make_pair(Offset, List)); 159 } 160 Buffer = ArrayRef<uint8_t>(WriteBuffer, Size); 161 return Error::success(); 162 } 163 164 Error MappedBlockStream::readLongestContiguousChunk(uint64_t Offset, 165 ArrayRef<uint8_t> &Buffer) { 166 // Make sure we aren't trying to read beyond the end of the stream. 167 if (auto EC = checkOffsetForRead(Offset, 1)) 168 return EC; 169 170 uint64_t First = Offset / BlockSize; 171 uint64_t Last = First; 172 173 while (Last < getNumBlocks() - 1) { 174 if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1) 175 break; 176 ++Last; 177 } 178 179 uint64_t OffsetInFirstBlock = Offset % BlockSize; 180 uint64_t BytesFromFirstBlock = BlockSize - OffsetInFirstBlock; 181 uint64_t BlockSpan = Last - First + 1; 182 uint64_t ByteSpan = BytesFromFirstBlock + (BlockSpan - 1) * BlockSize; 183 184 ArrayRef<uint8_t> BlockData; 185 uint64_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize); 186 if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData)) 187 return EC; 188 189 BlockData = BlockData.drop_front(OffsetInFirstBlock); 190 Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan); 191 return Error::success(); 192 } 193 194 uint64_t MappedBlockStream::getLength() { return StreamLayout.Length; } 195 196 bool MappedBlockStream::tryReadContiguously(uint64_t Offset, uint64_t Size, 197 ArrayRef<uint8_t> &Buffer) { 198 if (Size == 0) { 199 Buffer = ArrayRef<uint8_t>(); 200 return true; 201 } 202 // Attempt to fulfill the request with a reference directly into the stream. 203 // This can work even if the request crosses a block boundary, provided that 204 // all subsequent blocks are contiguous. For example, a 10k read with a 4k 205 // block size can be filled with a reference if, from the starting offset, 206 // 3 blocks in a row are contiguous. 207 uint64_t BlockNum = Offset / BlockSize; 208 uint64_t OffsetInBlock = Offset % BlockSize; 209 uint64_t BytesFromFirstBlock = std::min(Size, BlockSize - OffsetInBlock); 210 uint64_t NumAdditionalBlocks = 211 alignTo(Size - BytesFromFirstBlock, BlockSize) / BlockSize; 212 213 uint64_t RequiredContiguousBlocks = NumAdditionalBlocks + 1; 214 uint64_t E = StreamLayout.Blocks[BlockNum]; 215 for (uint64_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) { 216 if (StreamLayout.Blocks[I + BlockNum] != E) 217 return false; 218 } 219 220 // Read out the entire block where the requested offset starts. Then drop 221 // bytes from the beginning so that the actual starting byte lines up with 222 // the requested starting byte. Then, since we know this is a contiguous 223 // cross-block span, explicitly resize the ArrayRef to cover the entire 224 // request length. 225 ArrayRef<uint8_t> BlockData; 226 uint64_t FirstBlockAddr = StreamLayout.Blocks[BlockNum]; 227 uint64_t MsfOffset = blockToOffset(FirstBlockAddr, BlockSize); 228 if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData)) { 229 consumeError(std::move(EC)); 230 return false; 231 } 232 BlockData = BlockData.drop_front(OffsetInBlock); 233 Buffer = ArrayRef<uint8_t>(BlockData.data(), Size); 234 return true; 235 } 236 237 Error MappedBlockStream::readBytes(uint64_t Offset, 238 MutableArrayRef<uint8_t> Buffer) { 239 uint64_t BlockNum = Offset / BlockSize; 240 uint64_t OffsetInBlock = Offset % BlockSize; 241 242 // Make sure we aren't trying to read beyond the end of the stream. 243 if (auto EC = checkOffsetForRead(Offset, Buffer.size())) 244 return EC; 245 246 uint64_t BytesLeft = Buffer.size(); 247 uint64_t BytesWritten = 0; 248 uint8_t *WriteBuffer = Buffer.data(); 249 while (BytesLeft > 0) { 250 uint64_t StreamBlockAddr = StreamLayout.Blocks[BlockNum]; 251 252 ArrayRef<uint8_t> BlockData; 253 uint64_t Offset = blockToOffset(StreamBlockAddr, BlockSize); 254 if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData)) 255 return EC; 256 257 const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock; 258 uint64_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock); 259 ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk); 260 261 BytesWritten += BytesInChunk; 262 BytesLeft -= BytesInChunk; 263 ++BlockNum; 264 OffsetInBlock = 0; 265 } 266 267 return Error::success(); 268 } 269 270 void MappedBlockStream::invalidateCache() { CacheMap.shrink_and_clear(); } 271 272 void MappedBlockStream::fixCacheAfterWrite(uint64_t Offset, 273 ArrayRef<uint8_t> Data) const { 274 // If this write overlapped a read which previously came from the pool, 275 // someone may still be holding a pointer to that alloc which is now invalid. 276 // Compute the overlapping range and update the cache entry, so any 277 // outstanding buffers are automatically updated. 278 for (const auto &MapEntry : CacheMap) { 279 // If the end of the written extent precedes the beginning of the cached 280 // extent, ignore this map entry. 281 if (Offset + Data.size() < MapEntry.first) 282 continue; 283 for (const auto &Alloc : MapEntry.second) { 284 // If the end of the cached extent precedes the beginning of the written 285 // extent, ignore this alloc. 286 if (MapEntry.first + Alloc.size() < Offset) 287 continue; 288 289 // If we get here, they are guaranteed to overlap. 290 Interval WriteInterval = std::make_pair(Offset, Offset + Data.size()); 291 Interval CachedInterval = 292 std::make_pair(MapEntry.first, MapEntry.first + Alloc.size()); 293 // If they overlap, we need to write the new data into the overlapping 294 // range. 295 auto Intersection = intersect(WriteInterval, CachedInterval); 296 assert(Intersection.first <= Intersection.second); 297 298 uint64_t Length = Intersection.second - Intersection.first; 299 uint64_t SrcOffset = 300 AbsoluteDifference(WriteInterval.first, Intersection.first); 301 uint64_t DestOffset = 302 AbsoluteDifference(CachedInterval.first, Intersection.first); 303 ::memcpy(Alloc.data() + DestOffset, Data.data() + SrcOffset, Length); 304 } 305 } 306 } 307 308 WritableMappedBlockStream::WritableMappedBlockStream( 309 uint32_t BlockSize, const MSFStreamLayout &Layout, 310 WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator) 311 : ReadInterface(BlockSize, Layout, MsfData, Allocator), 312 WriteInterface(MsfData) {} 313 314 std::unique_ptr<WritableMappedBlockStream> 315 WritableMappedBlockStream::createStream(uint32_t BlockSize, 316 const MSFStreamLayout &Layout, 317 WritableBinaryStreamRef MsfData, 318 BumpPtrAllocator &Allocator) { 319 return std::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>( 320 BlockSize, Layout, MsfData, Allocator); 321 } 322 323 std::unique_ptr<WritableMappedBlockStream> 324 WritableMappedBlockStream::createIndexedStream(const MSFLayout &Layout, 325 WritableBinaryStreamRef MsfData, 326 uint32_t StreamIndex, 327 BumpPtrAllocator &Allocator) { 328 assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index"); 329 MSFStreamLayout SL; 330 SL.Blocks = Layout.StreamMap[StreamIndex]; 331 SL.Length = Layout.StreamSizes[StreamIndex]; 332 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator); 333 } 334 335 std::unique_ptr<WritableMappedBlockStream> 336 WritableMappedBlockStream::createDirectoryStream( 337 const MSFLayout &Layout, WritableBinaryStreamRef MsfData, 338 BumpPtrAllocator &Allocator) { 339 MSFStreamLayout SL; 340 SL.Blocks = Layout.DirectoryBlocks; 341 SL.Length = Layout.SB->NumDirectoryBytes; 342 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator); 343 } 344 345 std::unique_ptr<WritableMappedBlockStream> 346 WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout, 347 WritableBinaryStreamRef MsfData, 348 BumpPtrAllocator &Allocator, 349 bool AltFpm) { 350 // We only want to give the user a stream containing the bytes of the FPM that 351 // are actually valid, but we want to initialize all of the bytes, even those 352 // that come from reserved FPM blocks where the entire block is unused. To do 353 // this, we first create the full layout, which gives us a stream with all 354 // bytes and all blocks, and initialize everything to 0xFF (all blocks in the 355 // file are unused). Then we create the minimal layout (which contains only a 356 // subset of the bytes previously initialized), and return that to the user. 357 MSFStreamLayout MinLayout(getFpmStreamLayout(Layout, false, AltFpm)); 358 359 MSFStreamLayout FullLayout(getFpmStreamLayout(Layout, true, AltFpm)); 360 auto Result = 361 createStream(Layout.SB->BlockSize, FullLayout, MsfData, Allocator); 362 if (!Result) 363 return Result; 364 std::vector<uint8_t> InitData(Layout.SB->BlockSize, 0xFF); 365 BinaryStreamWriter Initializer(*Result); 366 while (Initializer.bytesRemaining() > 0) 367 cantFail(Initializer.writeBytes(InitData)); 368 return createStream(Layout.SB->BlockSize, MinLayout, MsfData, Allocator); 369 } 370 371 Error WritableMappedBlockStream::readBytes(uint64_t Offset, uint64_t Size, 372 ArrayRef<uint8_t> &Buffer) { 373 return ReadInterface.readBytes(Offset, Size, Buffer); 374 } 375 376 Error WritableMappedBlockStream::readLongestContiguousChunk( 377 uint64_t Offset, ArrayRef<uint8_t> &Buffer) { 378 return ReadInterface.readLongestContiguousChunk(Offset, Buffer); 379 } 380 381 uint64_t WritableMappedBlockStream::getLength() { 382 return ReadInterface.getLength(); 383 } 384 385 Error WritableMappedBlockStream::writeBytes(uint64_t Offset, 386 ArrayRef<uint8_t> Buffer) { 387 // Make sure we aren't trying to write beyond the end of the stream. 388 if (auto EC = checkOffsetForWrite(Offset, Buffer.size())) 389 return EC; 390 391 uint64_t BlockNum = Offset / getBlockSize(); 392 uint64_t OffsetInBlock = Offset % getBlockSize(); 393 394 uint64_t BytesLeft = Buffer.size(); 395 uint64_t BytesWritten = 0; 396 while (BytesLeft > 0) { 397 uint64_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum]; 398 uint64_t BytesToWriteInChunk = 399 std::min(BytesLeft, getBlockSize() - OffsetInBlock); 400 401 const uint8_t *Chunk = Buffer.data() + BytesWritten; 402 ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk); 403 uint64_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize()); 404 MsfOffset += OffsetInBlock; 405 if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData)) 406 return EC; 407 408 BytesLeft -= BytesToWriteInChunk; 409 BytesWritten += BytesToWriteInChunk; 410 ++BlockNum; 411 OffsetInBlock = 0; 412 } 413 414 ReadInterface.fixCacheAfterWrite(Offset, Buffer); 415 416 return Error::success(); 417 } 418 419 Error WritableMappedBlockStream::commit() { return WriteInterface.commit(); } 420