LCOV - code coverage report
Current view: top level - lib/DebugInfo/MSF - MappedBlockStream.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 157 161 97.5 %
Date: 2018-10-20 13:21:21 Functions: 23 25 92.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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           0 : template <typename Base> class MappedBlockStreamImpl : public Base {
      31             : public:
      32             :   template <typename... Args>
      33        3170 :   MappedBlockStreamImpl(Args &&... Params)
      34        6340 :       : Base(std::forward<Args>(Params)...) {}
      35        1782 : };
      36        3564 : 
      37        1123 : } // end anonymous namespace
      38        2246 : 
      39         265 : using Interval = std::pair<uint32_t, uint32_t>;
      40         530 : 
      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           2 :                                      BumpPtrAllocator &Allocator)
      50             :     : BlockSize(BlockSize), StreamLayout(Layout), MsfData(MsfData),
      51             :       Allocator(Allocator) {}
      52        3170 : 
      53             : std::unique_ptr<MappedBlockStream> MappedBlockStream::createStream(
      54             :     uint32_t BlockSize, const MSFStreamLayout &Layout, BinaryStreamRef MsfData,
      55        3170 :     BumpPtrAllocator &Allocator) {
      56             :   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
      57        6340 :       BlockSize, Layout, MsfData, Allocator);
      58             : }
      59         265 : 
      60             : std::unique_ptr<MappedBlockStream> MappedBlockStream::createIndexedStream(
      61             :     const MSFLayout &Layout, BinaryStreamRef MsfData, uint32_t StreamIndex,
      62             :     BumpPtrAllocator &Allocator) {
      63         265 :   assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
      64             :   MSFStreamLayout SL;
      65             :   SL.Blocks = Layout.StreamMap[StreamIndex];
      66        1123 :   SL.Length = Layout.StreamSizes[StreamIndex];
      67             :   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
      68             :       Layout.SB->BlockSize, SL, MsfData, Allocator);
      69             : }
      70             : 
      71        2246 : std::unique_ptr<MappedBlockStream>
      72        1123 : MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
      73             :                                          BinaryStreamRef MsfData,
      74        1123 :                                          BumpPtrAllocator &Allocator) {
      75             :   MSFStreamLayout SL;
      76             :   SL.Blocks = Layout.DirectoryBlocks;
      77             :   SL.Length = Layout.SB->NumDirectoryBytes;
      78         127 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
      79             : }
      80             : 
      81             : std::unique_ptr<MappedBlockStream>
      82         127 : MappedBlockStream::createFpmStream(const MSFLayout &Layout,
      83         254 :                                    BinaryStreamRef MsfData,
      84         381 :                                    BumpPtrAllocator &Allocator) {
      85             :   MSFStreamLayout SL(getFpmStreamLayout(Layout));
      86             :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
      87             : }
      88         127 : 
      89             : Error MappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
      90             :                                    ArrayRef<uint8_t> &Buffer) {
      91         127 :   // Make sure we aren't trying to read beyond the end of the stream.
      92         381 :   if (auto EC = checkOffsetForRead(Offset, Size))
      93             :     return EC;
      94             : 
      95      110260 :   if (tryReadContiguously(Offset, Size, Buffer))
      96             :     return Error::success();
      97             : 
      98      220520 :   auto CacheIter = CacheMap.find(Offset);
      99             :   if (CacheIter != CacheMap.end()) {
     100             :     // Try to find an alloc that was large enough for this request.
     101      110260 :     for (auto &Entry : CacheIter->second) {
     102             :       if (Entry.size() >= Size) {
     103             :         Buffer = Entry.slice(0, Size);
     104          41 :         return Error::success();
     105          41 :       }
     106             :     }
     107          17 :   }
     108          14 : 
     109           5 :   // 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          40 :     // If the initial extent of the cached item is beyond the ending extent
     119           5 :     // of the request, there is no overlap.
     120             :     if (CacheItem.first >= Offset + Size)
     121             :       continue;
     122           5 : 
     123           4 :     // 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           2 :       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           2 :     Interval CachedExtent =
     132             :         std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size());
     133             :     if (RequestExtent.first >= CachedExtent.first + CachedExtent.second)
     134           2 :       continue;
     135             : 
     136             :     Interval Intersection = intersect(CachedExtent, RequestExtent);
     137             :     // Only use this if the entire request extent is contained in the cached
     138           2 :     // extent.
     139           2 :     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           1 :   // into it, and return an ArrayRef to that.  Do not touch existing pool
     150           2 :   // 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          35 :   } else {
     159          70 :     std::vector<CacheEntry> List;
     160             :     List.emplace_back(WriteBuffer, Size);
     161             :     CacheMap.insert(std::make_pair(Offset, List));
     162          35 :   }
     163           3 :   Buffer = ArrayRef<uint8_t>(WriteBuffer, Size);
     164             :   return Error::success();
     165             : }
     166          32 : 
     167          64 : Error MappedBlockStream::readLongestContiguousChunk(uint32_t Offset,
     168             :                                                     ArrayRef<uint8_t> &Buffer) {
     169          35 :   // 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        3968 :   uint32_t First = Offset / BlockSize;
     174             :   uint32_t Last = First;
     175             : 
     176        7936 :   while (Last < getNumBlocks() - 1) {
     177             :     if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1)
     178             :       break;
     179        3968 :     ++Last;
     180             :   }
     181             : 
     182       10560 :   uint32_t OffsetInFirstBlock = Offset % BlockSize;
     183       19875 :   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        3968 :   uint32_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize);
     189        3968 :   if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData))
     190        3968 :     return EC;
     191        3968 : 
     192             :   BlockData = BlockData.drop_front(OffsetInFirstBlock);
     193        3968 :   Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan);
     194        7936 :   return Error::success();
     195        7936 : }
     196             : 
     197             : uint32_t MappedBlockStream::getLength() { return StreamLayout.Length; }
     198        3968 : 
     199        3968 : bool MappedBlockStream::tryReadContiguously(uint32_t Offset, uint32_t Size,
     200             :                                             ArrayRef<uint8_t> &Buffer) {
     201             :   if (Size == 0) {
     202             :     Buffer = ArrayRef<uint8_t>();
     203      258261 :     return true;
     204             :   }
     205      110260 :   // 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      110260 :   // all subsequent blocks are contiguous.  For example, a 10k read with a 4k
     208         444 :   // block size can be filled with a reference if, from the starting offset,
     209         444 :   // 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      109816 :   uint32_t RequiredContiguousBlocks = NumAdditionalBlocks + 1;
     217      109816 :   uint32_t E = StreamLayout.Blocks[BlockNum];
     218      109816 :   for (uint32_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) {
     219             :     if (StreamLayout.Blocks[I + BlockNum] != E)
     220      109816 :       return false;
     221             :   }
     222      109816 : 
     223      109816 :   // Read out the entire block where the requested offset starts.  Then drop
     224      219691 :   // bytes from the beginning so that the actual starting byte lines up with
     225      219832 :   // 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      109775 :   }
     235             :   BlockData = BlockData.drop_front(OffsetInBlock);
     236      109775 :   Buffer = ArrayRef<uint8_t>(BlockData.data(), Size);
     237      219550 :   return true;
     238           0 : }
     239             : 
     240             : Error MappedBlockStream::readBytes(uint32_t Offset,
     241      109775 :                                    MutableArrayRef<uint8_t> Buffer) {
     242      109775 :   uint32_t BlockNum = Offset / BlockSize;
     243      109775 :   uint32_t OffsetInBlock = Offset % BlockSize;
     244             : 
     245             :   // Make sure we aren't trying to read beyond the end of the stream.
     246          35 :   if (auto EC = checkOffsetForRead(Offset, Buffer.size()))
     247             :     return EC;
     248          35 : 
     249          35 :   uint32_t BytesLeft = Buffer.size();
     250             :   uint32_t BytesWritten = 0;
     251             :   uint8_t *WriteBuffer = Buffer.data();
     252          70 :   while (BytesLeft > 0) {
     253             :     uint32_t StreamBlockAddr = StreamLayout.Blocks[BlockNum];
     254             : 
     255          35 :     ArrayRef<uint8_t> BlockData;
     256             :     uint32_t Offset = blockToOffset(StreamBlockAddr, BlockSize);
     257             :     if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData))
     258         163 :       return EC;
     259         128 : 
     260             :     const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock;
     261         128 :     uint32_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock);
     262         128 :     ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk);
     263         256 : 
     264             :     BytesWritten += BytesInChunk;
     265             :     BytesLeft -= BytesInChunk;
     266         128 :     ++BlockNum;
     267         128 :     OffsetInBlock = 0;
     268         128 :   }
     269             : 
     270         128 :   return Error::success();
     271         128 : }
     272         128 : 
     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           0 :   // Compute the overlapping range and update the cache entry, so any
     280             :   // outstanding buffers are automatically updated.
     281       13100 :   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       13107 :       // 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           7 :         continue;
     291             : 
     292          25 :       // If we get here, they are guaranteed to overlap.
     293             :       Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
     294             :       Interval CachedInterval =
     295          18 :           std::make_pair(MapEntry.first, MapEntry.first + Alloc.size());
     296           2 :       // 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          16 :     }
     308             :   }
     309          16 : }
     310             : 
     311          16 : WritableMappedBlockStream::WritableMappedBlockStream(
     312          32 :     uint32_t BlockSize, const MSFStreamLayout &Layout,
     313             :     WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
     314             :     : ReadInterface(BlockSize, Layout, MsfData, Allocator),
     315       13100 :       WriteInterface(MsfData) {}
     316             : 
     317        1782 : std::unique_ptr<WritableMappedBlockStream>
     318             : WritableMappedBlockStream::createStream(uint32_t BlockSize,
     319        1782 :                                         const MSFStreamLayout &Layout,
     320             :                                         WritableBinaryStreamRef MsfData,
     321        3564 :                                         BumpPtrAllocator &Allocator) {
     322             :   return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
     323             :       BlockSize, Layout, MsfData, Allocator);
     324        1782 : }
     325             : 
     326             : std::unique_ptr<WritableMappedBlockStream>
     327             : WritableMappedBlockStream::createIndexedStream(const MSFLayout &Layout,
     328             :                                                WritableBinaryStreamRef MsfData,
     329        1782 :                                                uint32_t StreamIndex,
     330             :                                                BumpPtrAllocator &Allocator) {
     331             :   assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
     332             :   MSFStreamLayout SL;
     333        1215 :   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        2430 : WritableMappedBlockStream::createDirectoryStream(
     340        2430 :     const MSFLayout &Layout, WritableBinaryStreamRef MsfData,
     341        3645 :     BumpPtrAllocator &Allocator) {
     342             :   MSFStreamLayout SL;
     343             :   SL.Blocks = Layout.DirectoryBlocks;
     344             :   SL.Length = Layout.SB->NumDirectoryBytes;
     345         111 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
     346             : }
     347             : 
     348             : std::unique_ptr<WritableMappedBlockStream>
     349         111 : WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout,
     350         222 :                                            WritableBinaryStreamRef MsfData,
     351         333 :                                            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         224 :   // 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         224 :     return Result;
     367             :   std::vector<uint8_t> InitData(Layout.SB->BlockSize, 0xFF);
     368         224 :   BinaryStreamWriter Initializer(*Result);
     369             :   while (Initializer.bytesRemaining() > 0)
     370         672 :     cantFail(Initializer.writeBytes(InitData));
     371         224 :   return createStream(Layout.SB->BlockSize, MinLayout, MsfData, Allocator);
     372             : }
     373         448 : 
     374         224 : Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
     375         454 :                                            ArrayRef<uint8_t> &Buffer) {
     376         460 :   return ReadInterface.readBytes(Offset, Size, Buffer);
     377         672 : }
     378             : 
     379             : Error WritableMappedBlockStream::readLongestContiguousChunk(
     380          17 :     uint32_t Offset, ArrayRef<uint8_t> &Buffer) {
     381             :   return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
     382          17 : }
     383             : 
     384             : uint32_t WritableMappedBlockStream::getLength() {
     385          34 :   return ReadInterface.getLength();
     386             : }
     387          34 : 
     388             : Error WritableMappedBlockStream::writeBytes(uint32_t Offset,
     389             :                                             ArrayRef<uint8_t> Buffer) {
     390       27877 :   // Make sure we aren't trying to write beyond the end of the stream.
     391       27877 :   if (auto EC = checkOffsetForWrite(Offset, Buffer.size()))
     392             :     return EC;
     393             : 
     394       13102 :   uint32_t BlockNum = Offset / getBlockSize();
     395             :   uint32_t OffsetInBlock = Offset % getBlockSize();
     396             : 
     397       26204 :   uint32_t BytesLeft = Buffer.size();
     398             :   uint32_t BytesWritten = 0;
     399             :   while (BytesLeft > 0) {
     400       13100 :     uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
     401       13100 :     uint32_t BytesToWriteInChunk =
     402             :         std::min(BytesLeft, getBlockSize() - OffsetInBlock);
     403       13100 : 
     404             :     const uint8_t *Chunk = Buffer.data() + BytesWritten;
     405       25909 :     ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
     406       12809 :     uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
     407             :     MsfOffset += OffsetInBlock;
     408       12809 :     if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
     409             :       return EC;
     410       12809 : 
     411       12809 :     BytesLeft -= BytesToWriteInChunk;
     412       12809 :     BytesWritten += BytesToWriteInChunk;
     413       12809 :     ++BlockNum;
     414       25618 :     OffsetInBlock = 0;
     415             :   }
     416             : 
     417       12809 :   ReadInterface.fixCacheAfterWrite(Offset, Buffer);
     418       12809 : 
     419       12809 :   return Error::success();
     420             : }
     421             : 
     422             : Error WritableMappedBlockStream::commit() { return WriteInterface.commit(); }

Generated by: LCOV version 1.13