llvm/lib/DebugInfo/MSF/MappedBlockStream.cpp

   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(); }