contrib/llvm/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
  12 #include "llvm/DebugInfo/MSF/IMSFFile.h"
  13 #include "llvm/DebugInfo/MSF/MSFCommon.h"
  14 #include "llvm/DebugInfo/MSF/MSFStreamLayout.h"
  15 #include "llvm/Support/BinaryStreamError.h"
  16
  17 using namespace llvm;
  18 using namespace llvm::msf;
  19
  20 namespace {
  21 template <typename Base> class MappedBlockStreamImpl : public Base {
  22 public:
  23   template <typename... Args>
  24   MappedBlockStreamImpl(Args &&... Params)
  25       : Base(std::forward<Args>(Params)...) {}
  26 };
  27 }
  28
  29 static void initializeFpmStreamLayout(const MSFLayout &Layout,
  30                                       MSFStreamLayout &FpmLayout) {
  31   uint32_t NumFpmIntervals = msf::getNumFpmIntervals(Layout);
  32   support::ulittle32_t FpmBlock = Layout.SB->FreeBlockMapBlock;
  33   assert(FpmBlock == 1 || FpmBlock == 2);
  34   while (NumFpmIntervals > 0) {
  35     FpmLayout.Blocks.push_back(FpmBlock);
  36     FpmBlock += msf::getFpmIntervalLength(Layout);
  37     --NumFpmIntervals;
  38   }
  39   FpmLayout.Length = msf::getFullFpmByteSize(Layout);
  40 }
  41
  42 typedef std::pair<uint32_t, uint32_t> Interval;
  43 static Interval intersect(const Interval &I1, const Interval &I2) {
  44   return std::make_pair(std::max(I1.first, I2.first),
  45                         std::min(I1.second, I2.second));
  46 }
  47
  48 MappedBlockStream::MappedBlockStream(uint32_t BlockSize, uint32_t NumBlocks,
  49                                      const MSFStreamLayout &Layout,
  50                                      BinaryStreamRef MsfData)
  51     : BlockSize(BlockSize), NumBlocks(NumBlocks), StreamLayout(Layout),
  52       MsfData(MsfData) {}
  53
  54 std::unique_ptr<MappedBlockStream>
  55 MappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
  56                                 const MSFStreamLayout &Layout,
  57                                 BinaryStreamRef MsfData) {
  58   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
  59       BlockSize, NumBlocks, Layout, MsfData);
  60 }
  61
  62 std::unique_ptr<MappedBlockStream> MappedBlockStream::createIndexedStream(
  63     const MSFLayout &Layout, BinaryStreamRef MsfData, uint32_t StreamIndex) {
  64   assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
  65   MSFStreamLayout SL;
  66   SL.Blocks = Layout.StreamMap[StreamIndex];
  67   SL.Length = Layout.StreamSizes[StreamIndex];
  68   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
  69       Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
  70 }
  71
  72 std::unique_ptr<MappedBlockStream>
  73 MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
  74                                          BinaryStreamRef MsfData) {
  75   MSFStreamLayout SL;
  76   SL.Blocks = Layout.DirectoryBlocks;
  77   SL.Length = Layout.SB->NumDirectoryBytes;
  78   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
  79 }
  80
  81 std::unique_ptr<MappedBlockStream>
  82 MappedBlockStream::createFpmStream(const MSFLayout &Layout,
  83                                    BinaryStreamRef MsfData) {
  84   MSFStreamLayout SL;
  85   initializeFpmStreamLayout(Layout, SL);
  86   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
  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 = checkOffset(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 *>(Pool.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 = checkOffset(Offset, 1))
 171     return EC;
 172
 173   uint32_t First = Offset / BlockSize;
 174   uint32_t Last = First;
 175
 176   while (Last < NumBlocks - 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       llvm::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 = checkOffset(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 uint32_t MappedBlockStream::getNumBytesCopied() const {
 274   return static_cast<uint32_t>(Pool.getBytesAllocated());
 275 }
 276
 277 void MappedBlockStream::invalidateCache() { CacheMap.shrink_and_clear(); }
 278
 279 void MappedBlockStream::fixCacheAfterWrite(uint32_t Offset,
 280                                            ArrayRef<uint8_t> Data) const {
 281   // If this write overlapped a read which previously came from the pool,
 282   // someone may still be holding a pointer to that alloc which is now invalid.
 283   // Compute the overlapping range and update the cache entry, so any
 284   // outstanding buffers are automatically updated.
 285   for (const auto &MapEntry : CacheMap) {
 286     // If the end of the written extent precedes the beginning of the cached
 287     // extent, ignore this map entry.
 288     if (Offset + Data.size() < MapEntry.first)
 289       continue;
 290     for (const auto &Alloc : MapEntry.second) {
 291       // If the end of the cached extent precedes the beginning of the written
 292       // extent, ignore this alloc.
 293       if (MapEntry.first + Alloc.size() < Offset)
 294         continue;
 295
 296       // If we get here, they are guaranteed to overlap.
 297       Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
 298       Interval CachedInterval =
 299           std::make_pair(MapEntry.first, MapEntry.first + Alloc.size());
 300       // If they overlap, we need to write the new data into the overlapping
 301       // range.
 302       auto Intersection = intersect(WriteInterval, CachedInterval);
 303       assert(Intersection.first <= Intersection.second);
 304
 305       uint32_t Length = Intersection.second - Intersection.first;
 306       uint32_t SrcOffset =
 307           AbsoluteDifference(WriteInterval.first, Intersection.first);
 308       uint32_t DestOffset =
 309           AbsoluteDifference(CachedInterval.first, Intersection.first);
 310       ::memcpy(Alloc.data() + DestOffset, Data.data() + SrcOffset, Length);
 311     }
 312   }
 313 }
 314
 315 WritableMappedBlockStream::WritableMappedBlockStream(
 316     uint32_t BlockSize, uint32_t NumBlocks, const MSFStreamLayout &Layout,
 317     WritableBinaryStreamRef MsfData)
 318     : ReadInterface(BlockSize, NumBlocks, Layout, MsfData),
 319       WriteInterface(MsfData) {}
 320
 321 std::unique_ptr<WritableMappedBlockStream>
 322 WritableMappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
 323                                         const MSFStreamLayout &Layout,
 324                                         WritableBinaryStreamRef MsfData) {
 325   return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
 326       BlockSize, NumBlocks, Layout, MsfData);
 327 }
 328
 329 std::unique_ptr<WritableMappedBlockStream>
 330 WritableMappedBlockStream::createIndexedStream(const MSFLayout &Layout,
 331                                                WritableBinaryStreamRef MsfData,
 332                                                uint32_t StreamIndex) {
 333   assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
 334   MSFStreamLayout SL;
 335   SL.Blocks = Layout.StreamMap[StreamIndex];
 336   SL.Length = Layout.StreamSizes[StreamIndex];
 337   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
 338 }
 339
 340 std::unique_ptr<WritableMappedBlockStream>
 341 WritableMappedBlockStream::createDirectoryStream(
 342     const MSFLayout &Layout, WritableBinaryStreamRef MsfData) {
 343   MSFStreamLayout SL;
 344   SL.Blocks = Layout.DirectoryBlocks;
 345   SL.Length = Layout.SB->NumDirectoryBytes;
 346   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
 347 }
 348
 349 std::unique_ptr<WritableMappedBlockStream>
 350 WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout,
 351                                            WritableBinaryStreamRef MsfData) {
 352   MSFStreamLayout SL;
 353   initializeFpmStreamLayout(Layout, SL);
 354   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
 355 }
 356
 357 Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
 358                                            ArrayRef<uint8_t> &Buffer) {
 359   return ReadInterface.readBytes(Offset, Size, Buffer);
 360 }
 361
 362 Error WritableMappedBlockStream::readLongestContiguousChunk(
 363     uint32_t Offset, ArrayRef<uint8_t> &Buffer) {
 364   return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
 365 }
 366
 367 uint32_t WritableMappedBlockStream::getLength() {
 368   return ReadInterface.getLength();
 369 }
 370
 371 Error WritableMappedBlockStream::writeBytes(uint32_t Offset,
 372                                             ArrayRef<uint8_t> Buffer) {
 373   // Make sure we aren't trying to write beyond the end of the stream.
 374   if (auto EC = checkOffset(Offset, Buffer.size()))
 375     return EC;
 376
 377   uint32_t BlockNum = Offset / getBlockSize();
 378   uint32_t OffsetInBlock = Offset % getBlockSize();
 379
 380   uint32_t BytesLeft = Buffer.size();
 381   uint32_t BytesWritten = 0;
 382   while (BytesLeft > 0) {
 383     uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
 384     uint32_t BytesToWriteInChunk =
 385         std::min(BytesLeft, getBlockSize() - OffsetInBlock);
 386
 387     const uint8_t *Chunk = Buffer.data() + BytesWritten;
 388     ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
 389     uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
 390     MsfOffset += OffsetInBlock;
 391     if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
 392       return EC;
 393
 394     BytesLeft -= BytesToWriteInChunk;
 395     BytesWritten += BytesToWriteInChunk;
 396     ++BlockNum;
 397     OffsetInBlock = 0;
 398   }
 399
 400   ReadInterface.fixCacheAfterWrite(Offset, Buffer);
 401
 402   return Error::success();
 403 }
 404
 405 Error WritableMappedBlockStream::commit() { return WriteInterface.commit(); }