LCOV - code coverage report
Current view: top level - lib/DebugInfo/MSF - MappedBlockStream.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 181 196 92.3 %
Date: 2017-09-14 15:23:50 Functions: 25 29 86.2 %
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        1960 : template <typename Base> class MappedBlockStreamImpl : public Base {
      31             : public:
      32             :   template <typename... Args>
      33        1962 :   MappedBlockStreamImpl(Args &&... Params)
      34        6673 :       : 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          54 :                         std::min(I1.second, I2.second));
      44             : }
      45             : 
      46        1962 : MappedBlockStream::MappedBlockStream(uint32_t BlockSize,
      47             :                                      const MSFStreamLayout &Layout,
      48             :                                      BinaryStreamRef MsfData,
      49        1962 :                                      BumpPtrAllocator &Allocator)
      50             :     : BlockSize(BlockSize), StreamLayout(Layout), MsfData(MsfData),
      51        7848 :       Allocator(Allocator) {}
      52             : 
      53         205 : std::unique_ptr<MappedBlockStream> MappedBlockStream::createStream(
      54             :     uint32_t BlockSize, const MSFStreamLayout &Layout, BinaryStreamRef MsfData,
      55             :     BumpPtrAllocator &Allocator) {
      56         410 :   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
      57         410 :       BlockSize, Layout, MsfData, Allocator);
      58             : }
      59             : 
      60         787 : 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        1574 :   MSFStreamLayout SL;
      65        3935 :   SL.Blocks = Layout.StreamMap[StreamIndex];
      66        2361 :   SL.Length = Layout.StreamSizes[StreamIndex];
      67        2361 :   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
      68        2361 :       Layout.SB->BlockSize, SL, MsfData, Allocator);
      69             : }
      70             : 
      71             : std::unique_ptr<MappedBlockStream>
      72          97 : MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
      73             :                                          BinaryStreamRef MsfData,
      74             :                                          BumpPtrAllocator &Allocator) {
      75         194 :   MSFStreamLayout SL;
      76         388 :   SL.Blocks = Layout.DirectoryBlocks;
      77         194 :   SL.Length = Layout.SB->NumDirectoryBytes;
      78         388 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
      79             : }
      80             : 
      81             : std::unique_ptr<MappedBlockStream>
      82          97 : MappedBlockStream::createFpmStream(const MSFLayout &Layout,
      83             :                                    BinaryStreamRef MsfData,
      84             :                                    BumpPtrAllocator &Allocator) {
      85         194 :   MSFStreamLayout SL(getFpmStreamLayout(Layout));
      86         388 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
      87             : }
      88             : 
      89       21401 : 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       64203 :   if (auto EC = checkOffset(Offset, Size))
      93           0 :     return EC;
      94             : 
      95       21401 :   if (tryReadContiguously(Offset, Size, Buffer))
      96       64119 :     return Error::success();
      97             : 
      98          28 :   auto CacheIter = CacheMap.find(Offset);
      99          84 :   if (CacheIter != CacheMap.end()) {
     100             :     // Try to find an alloc that was large enough for this request.
     101          33 :     for (auto &Entry : CacheIter->second) {
     102          12 :       if (Entry.size() >= Size) {
     103           6 :         Buffer = Entry.slice(0, Size);
     104           9 :         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          79 :   for (auto &CacheItem : CacheMap) {
     113          10 :     Interval RequestExtent = std::make_pair(Offset, Offset + Size);
     114             : 
     115             :     // We already checked this one on the fast path above.
     116           5 :     if (CacheItem.first == Offset)
     117           7 :       continue;
     118             :     // If the initial extent of the cached item is beyond the ending extent
     119             :     // of the request, there is no overlap.
     120           2 :     if (CacheItem.first >= Offset + Size)
     121           0 :       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           4 :     if (CacheItem.second.empty())
     126           0 :       continue;
     127             : 
     128           4 :     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           6 :         std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size());
     133           2 :     if (RequestExtent.first >= CachedExtent.first + CachedExtent.second)
     134           0 :       continue;
     135             : 
     136           2 :     Interval Intersection = intersect(CachedExtent, RequestExtent);
     137             :     // Only use this if the entire request extent is contained in the cached
     138             :     // extent.
     139           2 :     if (Intersection != RequestExtent)
     140           1 :       continue;
     141             : 
     142             :     uint32_t CacheRangeOffset =
     143           1 :         AbsoluteDifference(CachedExtent.first, Intersection.first);
     144           2 :     Buffer = CachedAlloc.slice(CacheRangeOffset, Size);
     145           3 :     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          24 :   uint8_t *WriteBuffer = static_cast<uint8_t *>(Allocator.Allocate(Size, 8));
     153          96 :   if (auto EC = readBytes(Offset, MutableArrayRef<uint8_t>(WriteBuffer, Size)))
     154           0 :     return EC;
     155             : 
     156          72 :   if (CacheIter != CacheMap.end()) {
     157           3 :     CacheIter->second.emplace_back(WriteBuffer, Size);
     158             :   } else {
     159          42 :     std::vector<CacheEntry> List;
     160          21 :     List.emplace_back(WriteBuffer, Size);
     161          84 :     CacheMap.insert(std::make_pair(Offset, List));
     162             :   }
     163          24 :   Buffer = ArrayRef<uint8_t>(WriteBuffer, Size);
     164          72 :   return Error::success();
     165             : }
     166             : 
     167        3856 : 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       11568 :   if (auto EC = checkOffset(Offset, 1))
     171           0 :     return EC;
     172             : 
     173        3856 :   uint32_t First = Offset / BlockSize;
     174        3856 :   uint32_t Last = First;
     175             : 
     176       10448 :   while (Last < getNumBlocks() - 1) {
     177       33125 :     if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1)
     178             :       break;
     179             :     ++Last;
     180             :   }
     181             : 
     182        3856 :   uint32_t OffsetInFirstBlock = Offset % BlockSize;
     183        3856 :   uint32_t BytesFromFirstBlock = BlockSize - OffsetInFirstBlock;
     184        3856 :   uint32_t BlockSpan = Last - First + 1;
     185        3856 :   uint32_t ByteSpan = BytesFromFirstBlock + (BlockSpan - 1) * BlockSize;
     186             : 
     187        3856 :   ArrayRef<uint8_t> BlockData;
     188       15424 :   uint32_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize);
     189       11568 :   if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData))
     190           0 :     return EC;
     191             : 
     192        7712 :   BlockData = BlockData.drop_front(OffsetInFirstBlock);
     193        3856 :   Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan);
     194       11568 :   return Error::success();
     195             : }
     196             : 
     197       66723 : uint32_t MappedBlockStream::getLength() { return StreamLayout.Length; }
     198             : 
     199       21401 : bool MappedBlockStream::tryReadContiguously(uint32_t Offset, uint32_t Size,
     200             :                                             ArrayRef<uint8_t> &Buffer) {
     201       21401 :   if (Size == 0) {
     202         380 :     Buffer = ArrayRef<uint8_t>();
     203         380 :     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       21021 :   uint32_t BlockNum = Offset / BlockSize;
     211       21021 :   uint32_t OffsetInBlock = Offset % BlockSize;
     212       42042 :   uint32_t BytesFromFirstBlock = std::min(Size, BlockSize - OffsetInBlock);
     213             :   uint32_t NumAdditionalBlocks =
     214       42042 :       alignTo(Size - BytesFromFirstBlock, BlockSize) / BlockSize;
     215             : 
     216       21021 :   uint32_t RequiredContiguousBlocks = NumAdditionalBlocks + 1;
     217       42042 :   uint32_t E = StreamLayout.Blocks[BlockNum];
     218       42098 :   for (uint32_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) {
     219       63315 :     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       20993 :   ArrayRef<uint8_t> BlockData;
     229       41986 :   uint32_t FirstBlockAddr = StreamLayout.Blocks[BlockNum];
     230       41986 :   uint32_t MsfOffset = blockToOffset(FirstBlockAddr, BlockSize);
     231       62979 :   if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData)) {
     232           0 :     consumeError(std::move(EC));
     233           0 :     return false;
     234             :   }
     235       41986 :   BlockData = BlockData.drop_front(OffsetInBlock);
     236       20993 :   Buffer = ArrayRef<uint8_t>(BlockData.data(), Size);
     237       20993 :   return true;
     238             : }
     239             : 
     240          24 : Error MappedBlockStream::readBytes(uint32_t Offset,
     241             :                                    MutableArrayRef<uint8_t> Buffer) {
     242          24 :   uint32_t BlockNum = Offset / BlockSize;
     243          24 :   uint32_t OffsetInBlock = Offset % BlockSize;
     244             : 
     245             :   // Make sure we aren't trying to read beyond the end of the stream.
     246          72 :   if (auto EC = checkOffset(Offset, Buffer.size()))
     247           0 :     return EC;
     248             : 
     249          24 :   uint32_t BytesLeft = Buffer.size();
     250          24 :   uint32_t BytesWritten = 0;
     251          24 :   uint8_t *WriteBuffer = Buffer.data();
     252         130 :   while (BytesLeft > 0) {
     253         318 :     uint32_t StreamBlockAddr = StreamLayout.Blocks[BlockNum];
     254             : 
     255         106 :     ArrayRef<uint8_t> BlockData;
     256         212 :     uint32_t Offset = blockToOffset(StreamBlockAddr, BlockSize);
     257         318 :     if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData))
     258           0 :       return EC;
     259             : 
     260         106 :     const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock;
     261         212 :     uint32_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock);
     262         106 :     ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk);
     263             : 
     264         106 :     BytesWritten += BytesInChunk;
     265         106 :     BytesLeft -= BytesInChunk;
     266         106 :     ++BlockNum;
     267         106 :     OffsetInBlock = 0;
     268             :   }
     269             : 
     270          72 :   return Error::success();
     271             : }
     272             : 
     273           0 : void MappedBlockStream::invalidateCache() { CacheMap.shrink_and_clear(); }
     274             : 
     275        6984 : 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       13968 :   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           7 :     if (Offset + Data.size() < MapEntry.first)
     285           0 :       continue;
     286          46 :     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          18 :       if (MapEntry.first + Alloc.size() < Offset)
     290           2 :         continue;
     291             : 
     292             :       // If we get here, they are guaranteed to overlap.
     293          48 :       Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
     294             :       Interval CachedInterval =
     295          48 :           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          16 :       auto Intersection = intersect(WriteInterval, CachedInterval);
     299             :       assert(Intersection.first <= Intersection.second);
     300             : 
     301          16 :       uint32_t Length = Intersection.second - Intersection.first;
     302             :       uint32_t SrcOffset =
     303          16 :           AbsoluteDifference(WriteInterval.first, Intersection.first);
     304             :       uint32_t DestOffset =
     305          16 :           AbsoluteDifference(CachedInterval.first, Intersection.first);
     306          32 :       ::memcpy(Alloc.data() + DestOffset, Data.data() + SrcOffset, Length);
     307             :     }
     308             :   }
     309        6984 : }
     310             : 
     311         970 : WritableMappedBlockStream::WritableMappedBlockStream(
     312             :     uint32_t BlockSize, const MSFStreamLayout &Layout,
     313         970 :     WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
     314             :     : ReadInterface(BlockSize, Layout, MsfData, Allocator),
     315        3880 :       WriteInterface(MsfData) {}
     316             : 
     317             : std::unique_ptr<WritableMappedBlockStream>
     318         970 : WritableMappedBlockStream::createStream(uint32_t BlockSize,
     319             :                                         const MSFStreamLayout &Layout,
     320             :                                         WritableBinaryStreamRef MsfData,
     321             :                                         BumpPtrAllocator &Allocator) {
     322        1940 :   return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
     323        1940 :       BlockSize, Layout, MsfData, Allocator);
     324             : }
     325             : 
     326             : std::unique_ptr<WritableMappedBlockStream>
     327         658 : 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        1316 :   MSFStreamLayout SL;
     333        3290 :   SL.Blocks = Layout.StreamMap[StreamIndex];
     334        1974 :   SL.Length = Layout.StreamSizes[StreamIndex];
     335        2632 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
     336             : }
     337             : 
     338             : std::unique_ptr<WritableMappedBlockStream>
     339          60 : WritableMappedBlockStream::createDirectoryStream(
     340             :     const MSFLayout &Layout, WritableBinaryStreamRef MsfData,
     341             :     BumpPtrAllocator &Allocator) {
     342         120 :   MSFStreamLayout SL;
     343         240 :   SL.Blocks = Layout.DirectoryBlocks;
     344         120 :   SL.Length = Layout.SB->NumDirectoryBytes;
     345         240 :   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
     346             : }
     347             : 
     348             : std::unique_ptr<WritableMappedBlockStream>
     349         122 : 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         244 :   MSFStreamLayout MinLayout(getFpmStreamLayout(Layout, false, AltFpm));
     361             : 
     362         244 :   MSFStreamLayout FullLayout(getFpmStreamLayout(Layout, true, AltFpm));
     363             :   auto Result =
     364         488 :       createStream(Layout.SB->BlockSize, FullLayout, MsfData, Allocator);
     365         122 :   if (!Result)
     366             :     return Result;
     367         366 :   std::vector<uint8_t> InitData(Layout.SB->BlockSize, 0xFF);
     368         244 :   BinaryStreamWriter Initializer(*Result);
     369         378 :   while (Initializer.bytesRemaining() > 0)
     370         384 :     cantFail(Initializer.writeBytes(InitData));
     371         366 :   return createStream(Layout.SB->BlockSize, MinLayout, MsfData, Allocator);
     372             : }
     373             : 
     374          17 : Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
     375             :                                            ArrayRef<uint8_t> &Buffer) {
     376          17 :   return ReadInterface.readBytes(Offset, Size, Buffer);
     377             : }
     378             : 
     379          34 : Error WritableMappedBlockStream::readLongestContiguousChunk(
     380             :     uint32_t Offset, ArrayRef<uint8_t> &Buffer) {
     381          34 :   return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
     382             : }
     383             : 
     384       14884 : uint32_t WritableMappedBlockStream::getLength() {
     385       14884 :   return ReadInterface.getLength();
     386             : }
     387             : 
     388        6986 : 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       20956 :   if (auto EC = checkOffset(Offset, Buffer.size()))
     392           4 :     return EC;
     393             : 
     394        6984 :   uint32_t BlockNum = Offset / getBlockSize();
     395        6984 :   uint32_t OffsetInBlock = Offset % getBlockSize();
     396             : 
     397        6984 :   uint32_t BytesLeft = Buffer.size();
     398        6984 :   uint32_t BytesWritten = 0;
     399       13912 :   while (BytesLeft > 0) {
     400       27712 :     uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
     401             :     uint32_t BytesToWriteInChunk =
     402       13856 :         std::min(BytesLeft, getBlockSize() - OffsetInBlock);
     403             : 
     404        6928 :     const uint8_t *Chunk = Buffer.data() + BytesWritten;
     405       13856 :     ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
     406       13856 :     uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
     407        6928 :     MsfOffset += OffsetInBlock;
     408       20784 :     if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
     409           0 :       return EC;
     410             : 
     411        6928 :     BytesLeft -= BytesToWriteInChunk;
     412        6928 :     BytesWritten += BytesToWriteInChunk;
     413        6928 :     ++BlockNum;
     414        6928 :     OffsetInBlock = 0;
     415             :   }
     416             : 
     417        6984 :   ReadInterface.fixCacheAfterWrite(Offset, Buffer);
     418             : 
     419       20952 :   return Error::success();
     420             : }
     421             : 
     422           0 : Error WritableMappedBlockStream::commit() { return WriteInterface.commit(); }

Generated by: LCOV version 1.13