lib/DebugInfo/MSF/MappedBlockStream.cpp

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