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