0a3b2b96ab4207d69901568176c84cc31d6b0715
[lldb.git] / llvm / lib / DebugInfo / MSF / MappedBlockStream.cpp
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 template <typename Base> class MappedBlockStreamImpl : public Base {
22 public:
23   template <typename... Args>
24   MappedBlockStreamImpl(Args &&... Params)
25       : 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   return std::make_pair(std::max(I1.first, I2.first),
32                         std::min(I1.second, I2.second));
33 }
34
35 MappedBlockStream::MappedBlockStream(uint32_t BlockSize, uint32_t NumBlocks,
36                                      const MSFStreamLayout &Layout,
37                                      const ReadableStream &MsfData)
38     : BlockSize(BlockSize), NumBlocks(NumBlocks), StreamLayout(Layout),
39       MsfData(MsfData) {}
40
41 std::unique_ptr<MappedBlockStream>
42 MappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
43                                 const MSFStreamLayout &Layout,
44                                 const ReadableStream &MsfData) {
45   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
46       BlockSize, NumBlocks, Layout, MsfData);
47 }
48
49 std::unique_ptr<MappedBlockStream>
50 MappedBlockStream::createIndexedStream(const MSFLayout &Layout,
51                                        const ReadableStream &MsfData,
52                                        uint32_t StreamIndex) {
53   MSFStreamLayout SL;
54   SL.Blocks = Layout.StreamMap[StreamIndex];
55   SL.Length = Layout.StreamSizes[StreamIndex];
56   return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
57       Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
58 }
59
60 std::unique_ptr<MappedBlockStream>
61 MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
62                                          const ReadableStream &MsfData) {
63   MSFStreamLayout SL;
64   SL.Blocks = Layout.DirectoryBlocks;
65   SL.Length = Layout.SB->NumDirectoryBytes;
66   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
67 }
68
69 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   if (Size > StreamLayout.Length)
73     return make_error<MSFError>(msf_error_code::insufficient_buffer);
74   if (Offset > StreamLayout.Length - Size)
75     return make_error<MSFError>(msf_error_code::insufficient_buffer);
76
77   if (tryReadContiguously(Offset, Size, Buffer))
78     return Error::success();
79
80   auto CacheIter = CacheMap.find(Offset);
81   if (CacheIter != CacheMap.end()) {
82     // Try to find an alloc that was large enough for this request.
83     for (auto &Entry : CacheIter->second) {
84       if (Entry.size() >= Size) {
85         Buffer = Entry.slice(0, Size);
86         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   for (auto &CacheItem : CacheMap) {
95     Interval RequestExtent = std::make_pair(Offset, Offset + Size);
96
97     // We already checked this one on the fast path above.
98     if (CacheItem.first == Offset)
99       continue;
100     // If the initial extent of the cached item is beyond the ending extent
101     // of the request, there is no overlap.
102     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     if (CacheItem.second.empty())
108       continue;
109
110     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         std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size());
115     if (RequestExtent.first >= CachedExtent.first + CachedExtent.second)
116       continue;
117
118     Interval Intersection = intersect(CachedExtent, RequestExtent);
119     // Only use this if the entire request extent is contained in the cached
120     // extent.
121     if (Intersection != RequestExtent)
122       continue;
123
124     uint32_t CacheRangeOffset =
125         AbsoluteDifference(CachedExtent.first, Intersection.first);
126     Buffer = CachedAlloc.slice(CacheRangeOffset, Size);
127     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   uint8_t *WriteBuffer = static_cast<uint8_t *>(Pool.Allocate(Size, 8));
135   if (auto EC = readBytes(Offset, MutableArrayRef<uint8_t>(WriteBuffer, Size)))
136     return EC;
137
138   if (CacheIter != CacheMap.end()) {
139     CacheIter->second.emplace_back(WriteBuffer, Size);
140   } else {
141     std::vector<CacheEntry> List;
142     List.emplace_back(WriteBuffer, Size);
143     CacheMap.insert(std::make_pair(Offset, List));
144   }
145   Buffer = ArrayRef<uint8_t>(WriteBuffer, Size);
146   return Error::success();
147 }
148
149 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   if (Offset >= StreamLayout.Length)
153     return make_error<MSFError>(msf_error_code::insufficient_buffer);
154   uint32_t First = Offset / BlockSize;
155   uint32_t Last = First;
156
157   while (Last < NumBlocks - 1) {
158     if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1)
159       break;
160     ++Last;
161   }
162
163   uint32_t OffsetInFirstBlock = Offset % BlockSize;
164   uint32_t BytesFromFirstBlock = BlockSize - OffsetInFirstBlock;
165   uint32_t BlockSpan = Last - First + 1;
166   uint32_t ByteSpan = BytesFromFirstBlock + (BlockSpan - 1) * BlockSize;
167
168   ArrayRef<uint8_t> BlockData;
169   uint32_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize);
170   if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData))
171     return EC;
172
173   BlockData = BlockData.drop_front(OffsetInFirstBlock);
174   Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan);
175   return Error::success();
176 }
177
178 uint32_t MappedBlockStream::getLength() const { return StreamLayout.Length; }
179
180 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   uint32_t BlockNum = Offset / BlockSize;
188   uint32_t OffsetInBlock = Offset % BlockSize;
189   uint32_t BytesFromFirstBlock = std::min(Size, BlockSize - OffsetInBlock);
190   uint32_t NumAdditionalBlocks =
191       llvm::alignTo(Size - BytesFromFirstBlock, BlockSize) / BlockSize;
192
193   uint32_t RequiredContiguousBlocks = NumAdditionalBlocks + 1;
194   uint32_t E = StreamLayout.Blocks[BlockNum];
195   for (uint32_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) {
196     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   ArrayRef<uint8_t> BlockData;
206   uint32_t FirstBlockAddr = StreamLayout.Blocks[BlockNum];
207   uint32_t MsfOffset = blockToOffset(FirstBlockAddr, BlockSize);
208   if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData)) {
209     consumeError(std::move(EC));
210     return false;
211   }
212   BlockData = BlockData.drop_front(OffsetInBlock);
213   Buffer = ArrayRef<uint8_t>(BlockData.data(), Size);
214   return true;
215 }
216
217 Error MappedBlockStream::readBytes(uint32_t Offset,
218                                    MutableArrayRef<uint8_t> Buffer) const {
219   uint32_t BlockNum = Offset / BlockSize;
220   uint32_t OffsetInBlock = Offset % BlockSize;
221
222   // Make sure we aren't trying to read beyond the end of the stream.
223   if (Buffer.size() > StreamLayout.Length)
224     return make_error<MSFError>(msf_error_code::insufficient_buffer);
225   if (Offset > StreamLayout.Length - Buffer.size())
226     return make_error<MSFError>(msf_error_code::insufficient_buffer);
227
228   uint32_t BytesLeft = Buffer.size();
229   uint32_t BytesWritten = 0;
230   uint8_t *WriteBuffer = Buffer.data();
231   while (BytesLeft > 0) {
232     uint32_t StreamBlockAddr = StreamLayout.Blocks[BlockNum];
233
234     ArrayRef<uint8_t> BlockData;
235     uint32_t Offset = blockToOffset(StreamBlockAddr, BlockSize);
236     if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData))
237       return EC;
238
239     const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock;
240     uint32_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock);
241     ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk);
242
243     BytesWritten += BytesInChunk;
244     BytesLeft -= BytesInChunk;
245     ++BlockNum;
246     OffsetInBlock = 0;
247   }
248
249   return Error::success();
250 }
251
252 uint32_t MappedBlockStream::getNumBytesCopied() const {
253   return static_cast<uint32_t>(Pool.getBytesAllocated());
254 }
255
256 void MappedBlockStream::invalidateCache() { CacheMap.shrink_and_clear(); }
257
258 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   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     if (Offset + Data.size() < MapEntry.first)
268       continue;
269     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       if (MapEntry.first + Alloc.size() < Offset)
273         continue;
274
275       // If we get here, they are guaranteed to overlap.
276       Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
277       Interval CachedInterval =
278           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       uint32_t Length = Intersection.second - Intersection.first;
285       uint32_t SrcOffset =
286           AbsoluteDifference(WriteInterval.first, Intersection.first);
287       uint32_t DestOffset =
288           AbsoluteDifference(CachedInterval.first, Intersection.first);
289       ::memcpy(Alloc.data() + DestOffset, Data.data() + SrcOffset, Length);
290     }
291   }
292 }
293
294 WritableMappedBlockStream::WritableMappedBlockStream(
295     uint32_t BlockSize, uint32_t NumBlocks, const MSFStreamLayout &Layout,
296     const WritableStream &MsfData)
297     : ReadInterface(BlockSize, NumBlocks, Layout, MsfData),
298       WriteInterface(MsfData) {}
299
300 std::unique_ptr<WritableMappedBlockStream>
301 WritableMappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
302                                         const MSFStreamLayout &Layout,
303                                         const WritableStream &MsfData) {
304   return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
305       BlockSize, NumBlocks, Layout, MsfData);
306 }
307
308 std::unique_ptr<WritableMappedBlockStream>
309 WritableMappedBlockStream::createIndexedStream(const MSFLayout &Layout,
310                                                const WritableStream &MsfData,
311                                                uint32_t StreamIndex) {
312   MSFStreamLayout SL;
313   SL.Blocks = Layout.StreamMap[StreamIndex];
314   SL.Length = Layout.StreamSizes[StreamIndex];
315   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
316 }
317
318 std::unique_ptr<WritableMappedBlockStream>
319 WritableMappedBlockStream::createDirectoryStream(
320     const MSFLayout &Layout, const WritableStream &MsfData) {
321   MSFStreamLayout SL;
322   SL.Blocks = Layout.DirectoryBlocks;
323   SL.Length = Layout.SB->NumDirectoryBytes;
324   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
325 }
326
327 Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
328                                            ArrayRef<uint8_t> &Buffer) const {
329   return ReadInterface.readBytes(Offset, Size, Buffer);
330 }
331
332 Error WritableMappedBlockStream::readLongestContiguousChunk(
333     uint32_t Offset, ArrayRef<uint8_t> &Buffer) const {
334   return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
335 }
336
337 uint32_t WritableMappedBlockStream::getLength() const {
338   return ReadInterface.getLength();
339 }
340
341 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   if (Buffer.size() > getStreamLength())
345     return make_error<MSFError>(msf_error_code::insufficient_buffer);
346
347   if (Offset > getStreamLayout().Length - Buffer.size())
348     return make_error<MSFError>(msf_error_code::insufficient_buffer);
349
350   uint32_t BlockNum = Offset / getBlockSize();
351   uint32_t OffsetInBlock = Offset % getBlockSize();
352
353   uint32_t BytesLeft = Buffer.size();
354   uint32_t BytesWritten = 0;
355   while (BytesLeft > 0) {
356     uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
357     uint32_t BytesToWriteInChunk =
358         std::min(BytesLeft, getBlockSize() - OffsetInBlock);
359
360     const uint8_t *Chunk = Buffer.data() + BytesWritten;
361     ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
362     uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
363     MsfOffset += OffsetInBlock;
364     if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
365       return EC;
366
367     BytesLeft -= BytesToWriteInChunk;
368     BytesWritten += BytesToWriteInChunk;
369     ++BlockNum;
370     OffsetInBlock = 0;
371   }
372
373   ReadInterface.fixCacheAfterWrite(Offset, Buffer);
374
375   return Error::success();
376 }
377
378 Error WritableMappedBlockStream::commit() const {
379   return WriteInterface.commit();
380 }