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