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