120
|
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"
|
121
|
11 #include "llvm/ADT/ArrayRef.h"
|
|
12 #include "llvm/ADT/STLExtras.h"
|
120
|
13 #include "llvm/DebugInfo/MSF/MSFCommon.h"
|
121
|
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>
|
120
|
24
|
|
25 using namespace llvm;
|
|
26 using namespace llvm::msf;
|
|
27
|
|
28 namespace {
|
121
|
29
|
120
|
30 template <typename Base> class MappedBlockStreamImpl : public Base {
|
|
31 public:
|
|
32 template <typename... Args>
|
|
33 MappedBlockStreamImpl(Args &&... Params)
|
|
34 : Base(std::forward<Args>(Params)...) {}
|
|
35 };
|
121
|
36
|
|
37 } // end anonymous namespace
|
120
|
38
|
121
|
39 using Interval = std::pair<uint32_t, uint32_t>;
|
120
|
40
|
|
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
|
121
|
46 MappedBlockStream::MappedBlockStream(uint32_t BlockSize,
|
120
|
47 const MSFStreamLayout &Layout,
|
121
|
48 BinaryStreamRef MsfData,
|
|
49 BumpPtrAllocator &Allocator)
|
|
50 : BlockSize(BlockSize), StreamLayout(Layout), MsfData(MsfData),
|
|
51 Allocator(Allocator) {}
|
120
|
52
|
121
|
53 std::unique_ptr<MappedBlockStream> MappedBlockStream::createStream(
|
|
54 uint32_t BlockSize, const MSFStreamLayout &Layout, BinaryStreamRef MsfData,
|
|
55 BumpPtrAllocator &Allocator) {
|
120
|
56 return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
|
121
|
57 BlockSize, Layout, MsfData, Allocator);
|
120
|
58 }
|
|
59
|
121
|
60 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");
|
120
|
64 MSFStreamLayout SL;
|
|
65 SL.Blocks = Layout.StreamMap[StreamIndex];
|
|
66 SL.Length = Layout.StreamSizes[StreamIndex];
|
|
67 return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
|
121
|
68 Layout.SB->BlockSize, SL, MsfData, Allocator);
|
120
|
69 }
|
|
70
|
|
71 std::unique_ptr<MappedBlockStream>
|
|
72 MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
|
121
|
73 BinaryStreamRef MsfData,
|
|
74 BumpPtrAllocator &Allocator) {
|
120
|
75 MSFStreamLayout SL;
|
|
76 SL.Blocks = Layout.DirectoryBlocks;
|
|
77 SL.Length = Layout.SB->NumDirectoryBytes;
|
121
|
78 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
|
120
|
79 }
|
|
80
|
|
81 std::unique_ptr<MappedBlockStream>
|
|
82 MappedBlockStream::createFpmStream(const MSFLayout &Layout,
|
121
|
83 BinaryStreamRef MsfData,
|
|
84 BumpPtrAllocator &Allocator) {
|
|
85 MSFStreamLayout SL(getFpmStreamLayout(Layout));
|
|
86 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
|
120
|
87 }
|
|
88
|
|
89 Error MappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
|
121
|
90 ArrayRef<uint8_t> &Buffer) {
|
120
|
91 // Make sure we aren't trying to read beyond the end of the stream.
|
121
|
92 if (auto EC = checkOffset(Offset, Size))
|
|
93 return EC;
|
120
|
94
|
|
95 if (tryReadContiguously(Offset, Size, Buffer))
|
|
96 return Error::success();
|
|
97
|
|
98 auto CacheIter = CacheMap.find(Offset);
|
|
99 if (CacheIter != CacheMap.end()) {
|
|
100 // Try to find an alloc that was large enough for this request.
|
|
101 for (auto &Entry : CacheIter->second) {
|
|
102 if (Entry.size() >= Size) {
|
|
103 Buffer = Entry.slice(0, Size);
|
|
104 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 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 // If the initial extent of the cached item is beyond the ending extent
|
|
119 // of the request, there is no overlap.
|
|
120 if (CacheItem.first >= Offset + Size)
|
|
121 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 if (CacheItem.second.empty())
|
|
126 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 Interval CachedExtent =
|
|
132 std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size());
|
|
133 if (RequestExtent.first >= CachedExtent.first + CachedExtent.second)
|
|
134 continue;
|
|
135
|
|
136 Interval Intersection = intersect(CachedExtent, RequestExtent);
|
|
137 // Only use this if the entire request extent is contained in the cached
|
|
138 // extent.
|
|
139 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 // 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.
|
121
|
152 uint8_t *WriteBuffer = static_cast<uint8_t *>(Allocator.Allocate(Size, 8));
|
120
|
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 } else {
|
|
159 std::vector<CacheEntry> List;
|
|
160 List.emplace_back(WriteBuffer, Size);
|
|
161 CacheMap.insert(std::make_pair(Offset, List));
|
|
162 }
|
|
163 Buffer = ArrayRef<uint8_t>(WriteBuffer, Size);
|
|
164 return Error::success();
|
|
165 }
|
|
166
|
121
|
167 Error MappedBlockStream::readLongestContiguousChunk(uint32_t Offset,
|
|
168 ArrayRef<uint8_t> &Buffer) {
|
120
|
169 // Make sure we aren't trying to read beyond the end of the stream.
|
121
|
170 if (auto EC = checkOffset(Offset, 1))
|
|
171 return EC;
|
|
172
|
120
|
173 uint32_t First = Offset / BlockSize;
|
|
174 uint32_t Last = First;
|
|
175
|
121
|
176 while (Last < getNumBlocks() - 1) {
|
120
|
177 if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1)
|
|
178 break;
|
|
179 ++Last;
|
|
180 }
|
|
181
|
|
182 uint32_t OffsetInFirstBlock = Offset % BlockSize;
|
|
183 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 uint32_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize);
|
|
189 if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData))
|
|
190 return EC;
|
|
191
|
|
192 BlockData = BlockData.drop_front(OffsetInFirstBlock);
|
|
193 Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan);
|
|
194 return Error::success();
|
|
195 }
|
|
196
|
121
|
197 uint32_t MappedBlockStream::getLength() { return StreamLayout.Length; }
|
120
|
198
|
|
199 bool MappedBlockStream::tryReadContiguously(uint32_t Offset, uint32_t Size,
|
121
|
200 ArrayRef<uint8_t> &Buffer) {
|
120
|
201 if (Size == 0) {
|
|
202 Buffer = ArrayRef<uint8_t>();
|
|
203 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 uint32_t BlockNum = Offset / BlockSize;
|
|
211 uint32_t OffsetInBlock = Offset % BlockSize;
|
|
212 uint32_t BytesFromFirstBlock = std::min(Size, BlockSize - OffsetInBlock);
|
|
213 uint32_t NumAdditionalBlocks =
|
121
|
214 alignTo(Size - BytesFromFirstBlock, BlockSize) / BlockSize;
|
120
|
215
|
|
216 uint32_t RequiredContiguousBlocks = NumAdditionalBlocks + 1;
|
|
217 uint32_t E = StreamLayout.Blocks[BlockNum];
|
|
218 for (uint32_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) {
|
|
219 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 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 }
|
|
235 BlockData = BlockData.drop_front(OffsetInBlock);
|
|
236 Buffer = ArrayRef<uint8_t>(BlockData.data(), Size);
|
|
237 return true;
|
|
238 }
|
|
239
|
|
240 Error MappedBlockStream::readBytes(uint32_t Offset,
|
121
|
241 MutableArrayRef<uint8_t> Buffer) {
|
120
|
242 uint32_t BlockNum = Offset / BlockSize;
|
|
243 uint32_t OffsetInBlock = Offset % BlockSize;
|
|
244
|
|
245 // Make sure we aren't trying to read beyond the end of the stream.
|
121
|
246 if (auto EC = checkOffset(Offset, Buffer.size()))
|
|
247 return EC;
|
120
|
248
|
|
249 uint32_t BytesLeft = Buffer.size();
|
|
250 uint32_t BytesWritten = 0;
|
|
251 uint8_t *WriteBuffer = Buffer.data();
|
|
252 while (BytesLeft > 0) {
|
|
253 uint32_t StreamBlockAddr = StreamLayout.Blocks[BlockNum];
|
|
254
|
|
255 ArrayRef<uint8_t> BlockData;
|
|
256 uint32_t Offset = blockToOffset(StreamBlockAddr, BlockSize);
|
|
257 if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData))
|
|
258 return EC;
|
|
259
|
|
260 const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock;
|
|
261 uint32_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock);
|
|
262 ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk);
|
|
263
|
|
264 BytesWritten += BytesInChunk;
|
|
265 BytesLeft -= BytesInChunk;
|
|
266 ++BlockNum;
|
|
267 OffsetInBlock = 0;
|
|
268 }
|
|
269
|
|
270 return Error::success();
|
|
271 }
|
|
272
|
|
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 // Compute the overlapping range and update the cache entry, so any
|
|
280 // outstanding buffers are automatically updated.
|
|
281 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 // 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 continue;
|
|
291
|
|
292 // If we get here, they are guaranteed to overlap.
|
|
293 Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
|
|
294 Interval CachedInterval =
|
|
295 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 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 }
|
|
308 }
|
|
309 }
|
|
310
|
|
311 WritableMappedBlockStream::WritableMappedBlockStream(
|
121
|
312 uint32_t BlockSize, const MSFStreamLayout &Layout,
|
|
313 WritableBinaryStreamRef MsfData, BumpPtrAllocator &Allocator)
|
|
314 : ReadInterface(BlockSize, Layout, MsfData, Allocator),
|
120
|
315 WriteInterface(MsfData) {}
|
|
316
|
|
317 std::unique_ptr<WritableMappedBlockStream>
|
121
|
318 WritableMappedBlockStream::createStream(uint32_t BlockSize,
|
120
|
319 const MSFStreamLayout &Layout,
|
121
|
320 WritableBinaryStreamRef MsfData,
|
|
321 BumpPtrAllocator &Allocator) {
|
120
|
322 return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
|
121
|
323 BlockSize, Layout, MsfData, Allocator);
|
120
|
324 }
|
|
325
|
|
326 std::unique_ptr<WritableMappedBlockStream>
|
|
327 WritableMappedBlockStream::createIndexedStream(const MSFLayout &Layout,
|
121
|
328 WritableBinaryStreamRef MsfData,
|
|
329 uint32_t StreamIndex,
|
|
330 BumpPtrAllocator &Allocator) {
|
|
331 assert(StreamIndex < Layout.StreamMap.size() && "Invalid stream index");
|
120
|
332 MSFStreamLayout SL;
|
|
333 SL.Blocks = Layout.StreamMap[StreamIndex];
|
|
334 SL.Length = Layout.StreamSizes[StreamIndex];
|
121
|
335 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
|
120
|
336 }
|
|
337
|
|
338 std::unique_ptr<WritableMappedBlockStream>
|
|
339 WritableMappedBlockStream::createDirectoryStream(
|
121
|
340 const MSFLayout &Layout, WritableBinaryStreamRef MsfData,
|
|
341 BumpPtrAllocator &Allocator) {
|
120
|
342 MSFStreamLayout SL;
|
|
343 SL.Blocks = Layout.DirectoryBlocks;
|
|
344 SL.Length = Layout.SB->NumDirectoryBytes;
|
121
|
345 return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
|
120
|
346 }
|
|
347
|
|
348 std::unique_ptr<WritableMappedBlockStream>
|
|
349 WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout,
|
121
|
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 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 return Result;
|
|
367 std::vector<uint8_t> InitData(Layout.SB->BlockSize, 0xFF);
|
|
368 BinaryStreamWriter Initializer(*Result);
|
|
369 while (Initializer.bytesRemaining() > 0)
|
|
370 cantFail(Initializer.writeBytes(InitData));
|
|
371 return createStream(Layout.SB->BlockSize, MinLayout, MsfData, Allocator);
|
120
|
372 }
|
|
373
|
|
374 Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
|
121
|
375 ArrayRef<uint8_t> &Buffer) {
|
120
|
376 return ReadInterface.readBytes(Offset, Size, Buffer);
|
|
377 }
|
|
378
|
|
379 Error WritableMappedBlockStream::readLongestContiguousChunk(
|
121
|
380 uint32_t Offset, ArrayRef<uint8_t> &Buffer) {
|
120
|
381 return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
|
|
382 }
|
|
383
|
121
|
384 uint32_t WritableMappedBlockStream::getLength() {
|
120
|
385 return ReadInterface.getLength();
|
|
386 }
|
|
387
|
|
388 Error WritableMappedBlockStream::writeBytes(uint32_t Offset,
|
121
|
389 ArrayRef<uint8_t> Buffer) {
|
120
|
390 // Make sure we aren't trying to write beyond the end of the stream.
|
121
|
391 if (auto EC = checkOffset(Offset, Buffer.size()))
|
|
392 return EC;
|
120
|
393
|
|
394 uint32_t BlockNum = Offset / getBlockSize();
|
|
395 uint32_t OffsetInBlock = Offset % getBlockSize();
|
|
396
|
|
397 uint32_t BytesLeft = Buffer.size();
|
|
398 uint32_t BytesWritten = 0;
|
|
399 while (BytesLeft > 0) {
|
|
400 uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
|
|
401 uint32_t BytesToWriteInChunk =
|
|
402 std::min(BytesLeft, getBlockSize() - OffsetInBlock);
|
|
403
|
|
404 const uint8_t *Chunk = Buffer.data() + BytesWritten;
|
|
405 ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
|
|
406 uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
|
|
407 MsfOffset += OffsetInBlock;
|
|
408 if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
|
|
409 return EC;
|
|
410
|
|
411 BytesLeft -= BytesToWriteInChunk;
|
|
412 BytesWritten += BytesToWriteInChunk;
|
|
413 ++BlockNum;
|
|
414 OffsetInBlock = 0;
|
|
415 }
|
|
416
|
|
417 ReadInterface.fixCacheAfterWrite(Offset, Buffer);
|
|
418
|
|
419 return Error::success();
|
|
420 }
|
|
421
|
121
|
422 Error WritableMappedBlockStream::commit() { return WriteInterface.commit(); }
|