LLVM 19.0.0git
MappedBlockStream.cpp
Go to the documentation of this file.
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
10#include "llvm/ADT/ArrayRef.h"
13#include "llvm/Support/Error.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 namespace
35
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
44 const MSFStreamLayout &Layout,
45 BinaryStreamRef MsfData,
46 BumpPtrAllocator &Allocator)
47 : BlockSize(BlockSize), StreamLayout(Layout), MsfData(MsfData),
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");
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>
70 BinaryStreamRef MsfData,
71 BumpPtrAllocator &Allocator) {
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>
80 BinaryStreamRef MsfData,
81 BumpPtrAllocator &Allocator) {
83 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
84}
85
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 most
107 // common scenario). Try to see if there is a buffer that starts at some
108 // 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 extent
116 // 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 append
121 // 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 of
127 // 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 cached
135 // 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 data
146 // into it, and return an ArrayRef to that. Do not touch existing pool
147 // allocations, as existing clients may be holding a pointer which must
148 // 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
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;
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
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 that
204 // all subsequent blocks are contiguous. For example, a 10k read with a 4k
205 // 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 drop
221 // bytes from the beginning so that the actual starting byte lines up with
222 // the requested starting byte. Then, since we know this is a contiguous
223 // cross-block span, explicitly resize the ArrayRef to cover the entire
224 // request length.
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
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
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 any
277 // outstanding buffers are automatically updated.
278 for (const auto &MapEntry : CacheMap) {
279 // If the end of the written extent precedes the beginning of the cached
280 // 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 written
285 // 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 overlapping
294 // 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
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>
316 const MSFStreamLayout &Layout,
318 BumpPtrAllocator &Allocator) {
319 return std::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
320 BlockSize, Layout, MsfData, Allocator);
321}
322
323std::unique_ptr<WritableMappedBlockStream>
326 uint32_t StreamIndex,
327 BumpPtrAllocator &Allocator) {
328 assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
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>
337 const MSFLayout &Layout, WritableBinaryStreamRef MsfData,
338 BumpPtrAllocator &Allocator) {
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>
348 BumpPtrAllocator &Allocator,
349 bool AltFpm) {
350 // We only want to give the user a stream containing the bytes of the FPM that
351 // are actually valid, but we want to initialize all of the bytes, even those
352 // that come from reserved FPM blocks where the entire block is unused. To do
353 // this, we first create the full layout, which gives us a stream with all
354 // bytes and all blocks, and initialize everything to 0xFF (all blocks in the
355 // file are unused). Then we create the minimal layout (which contains only a
356 // 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
372 ArrayRef<uint8_t> &Buffer) {
373 return ReadInterface.readBytes(Offset, Size, Buffer);
374}
375
378 return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
379}
380
382 return ReadInterface.getLength();
383}
384
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(); }
uint64_t Size
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
#define I(x, y, z)
Definition: MD5.cpp:58
static Interval intersect(const Interval &I1, const Interval &I2)
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const int BlockSize
Definition: TarWriter.cpp:33
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
const T * data() const
Definition: ArrayRef.h:162
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:195
BinaryStreamRef is to BinaryStream what ArrayRef is to an Array.
Error readBytes(uint64_t Offset, uint64_t Size, ArrayRef< uint8_t > &Buffer) const
Given an Offset into this StreamRef and a Size, return a reference to a buffer owned by the stream.
Provides write only access to a subclass of WritableBinaryStream.
uint64_t bytesRemaining() const
Error writeBytes(ArrayRef< uint8_t > Buffer)
Write the bytes specified in Buffer to the underlying stream.
Error checkOffsetForRead(uint64_t Offset, uint64_t DataSize)
Definition: BinaryStream.h:58
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
Lightweight error class with error context and mandatory checking.
Definition: Error.h:160
static ErrorSuccess success()
Create a success value.
Definition: Error.h:334
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
T * data() const
Definition: ArrayRef.h:354
Error writeBytes(uint64_t Offset, ArrayRef< uint8_t > Data) const
Given an Offset into this WritableBinaryStreamRef and some input data, writes the data to the underly...
Error commit()
For buffered streams, commits changes to the backing store.
Error checkOffsetForWrite(uint64_t Offset, uint64_t DataSize)
Definition: BinaryStream.h:88
Describes the layout of a stream in an MSF layout.
Definition: MSFCommon.h:77
std::vector< support::ulittle32_t > Blocks
Definition: MSFCommon.h:80
static std::unique_ptr< MappedBlockStream > createIndexedStream(const MSFLayout &Layout, BinaryStreamRef MsfData, uint32_t StreamIndex, BumpPtrAllocator &Allocator)
Error readBytes(uint64_t Offset, uint64_t Size, ArrayRef< uint8_t > &Buffer) override
Given an offset into the stream and a number of bytes, attempt to read the bytes and set the output A...
Error readLongestContiguousChunk(uint64_t Offset, ArrayRef< uint8_t > &Buffer) override
Given an offset into the stream, read as much as possible without copying any data.
static std::unique_ptr< MappedBlockStream > createStream(uint32_t BlockSize, const MSFStreamLayout &Layout, BinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
MappedBlockStream(uint32_t BlockSize, const MSFStreamLayout &StreamLayout, BinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
static std::unique_ptr< MappedBlockStream > createDirectoryStream(const MSFLayout &Layout, BinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
static std::unique_ptr< MappedBlockStream > createFpmStream(const MSFLayout &Layout, BinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
uint64_t getLength() override
Return the number of bytes of data in this stream.
static std::unique_ptr< WritableMappedBlockStream > createIndexedStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, uint32_t StreamIndex, BumpPtrAllocator &Allocator)
static std::unique_ptr< WritableMappedBlockStream > createStream(uint32_t BlockSize, const MSFStreamLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
Error commit() override
For buffered streams, commits changes to the backing store.
WritableMappedBlockStream(uint32_t BlockSize, const MSFStreamLayout &StreamLayout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
Error readBytes(uint64_t Offset, uint64_t Size, ArrayRef< uint8_t > &Buffer) override
Given an offset into the stream and a number of bytes, attempt to read the bytes and set the output A...
static std::unique_ptr< WritableMappedBlockStream > createFpmStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator, bool AltFpm=false)
static std::unique_ptr< WritableMappedBlockStream > createDirectoryStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
uint64_t getLength() override
Return the number of bytes of data in this stream.
const MSFStreamLayout & getStreamLayout() const
Error readLongestContiguousChunk(uint64_t Offset, ArrayRef< uint8_t > &Buffer) override
Given an offset into the stream, read as much as possible without copying any data.
Error writeBytes(uint64_t Offset, ArrayRef< uint8_t > Buffer) override
Attempt to write the given bytes into the stream at the desired offset.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize)
Definition: MSFCommon.h:135
MSFStreamLayout getFpmStreamLayout(const MSFLayout &Msf, bool IncludeUnusedFpmData=false, bool AltFpm=false)
Determine the layout of the FPM stream, given the MSF layout.
Definition: MSFCommon.cpp:62
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
@ Length
Definition: DWP.cpp:456
std::enable_if_t< std::is_unsigned_v< T >, T > AbsoluteDifference(T X, T Y)
Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result.
Definition: MathExtras.h:469
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:749
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:1041
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
ArrayRef< support::ulittle32_t > StreamSizes
Definition: MSFCommon.h:67
ArrayRef< support::ulittle32_t > DirectoryBlocks
Definition: MSFCommon.h:66
const SuperBlock * SB
Definition: MSFCommon.h:64
std::vector< ArrayRef< support::ulittle32_t > > StreamMap
Definition: MSFCommon.h:68
support::ulittle32_t BlockSize
Definition: MSFCommon.h:36
support::ulittle32_t NumDirectoryBytes
Definition: MSFCommon.h:44