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