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