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