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(); }
|
