1 //===- MSFBuilder.cpp -----------------------------------------------------===//
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/MSFBuilder.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/DebugInfo/MSF/MSFError.h"
13 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
14 #include "llvm/Support/BinaryByteStream.h"
15 #include "llvm/Support/BinaryStreamWriter.h"
16 #include "llvm/Support/Endian.h"
17 #include "llvm/Support/Error.h"
18 #include "llvm/Support/FileOutputBuffer.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <cstdint>
22 #include <cstring>
23 #include <memory>
24 #include <utility>
25 #include <vector>
26
27 using namespace llvm;
28 using namespace llvm::msf;
29 using namespace llvm::support;
30
31 static const uint32_t kSuperBlockBlock = 0;
32 static const uint32_t kFreePageMap0Block = 1;
33 static const uint32_t kFreePageMap1Block = 2;
34 static const uint32_t kNumReservedPages = 3;
35
36 static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
37 static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
38
MSFBuilder(uint32_t BlockSize,uint32_t MinBlockCount,bool CanGrow,BumpPtrAllocator & Allocator)39 MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
40 BumpPtrAllocator &Allocator)
41 : Allocator(Allocator), IsGrowable(CanGrow),
42 FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
43 BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
44 FreeBlocks[kSuperBlockBlock] = false;
45 FreeBlocks[kFreePageMap0Block] = false;
46 FreeBlocks[kFreePageMap1Block] = false;
47 FreeBlocks[BlockMapAddr] = false;
48 }
49
create(BumpPtrAllocator & Allocator,uint32_t BlockSize,uint32_t MinBlockCount,bool CanGrow)50 Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
51 uint32_t BlockSize,
52 uint32_t MinBlockCount, bool CanGrow) {
53 if (!isValidBlockSize(BlockSize))
54 return make_error<MSFError>(msf_error_code::invalid_format,
55 "The requested block size is unsupported");
56
57 return MSFBuilder(BlockSize,
58 std::max(MinBlockCount, msf::getMinimumBlockCount()),
59 CanGrow, Allocator);
60 }
61
setBlockMapAddr(uint32_t Addr)62 Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
63 if (Addr == BlockMapAddr)
64 return Error::success();
65
66 if (Addr >= FreeBlocks.size()) {
67 if (!IsGrowable)
68 return make_error<MSFError>(msf_error_code::insufficient_buffer,
69 "Cannot grow the number of blocks");
70 FreeBlocks.resize(Addr + 1, true);
71 }
72
73 if (!isBlockFree(Addr))
74 return make_error<MSFError>(
75 msf_error_code::block_in_use,
76 "Requested block map address is already in use");
77 FreeBlocks[BlockMapAddr] = true;
78 FreeBlocks[Addr] = false;
79 BlockMapAddr = Addr;
80 return Error::success();
81 }
82
setFreePageMap(uint32_t Fpm)83 void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
84
setUnknown1(uint32_t Unk1)85 void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
86
setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks)87 Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
88 for (auto B : DirectoryBlocks)
89 FreeBlocks[B] = true;
90 for (auto B : DirBlocks) {
91 if (!isBlockFree(B)) {
92 return make_error<MSFError>(msf_error_code::unspecified,
93 "Attempt to reuse an allocated block");
94 }
95 FreeBlocks[B] = false;
96 }
97
98 DirectoryBlocks = DirBlocks;
99 return Error::success();
100 }
101
allocateBlocks(uint32_t NumBlocks,MutableArrayRef<uint32_t> Blocks)102 Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
103 MutableArrayRef<uint32_t> Blocks) {
104 if (NumBlocks == 0)
105 return Error::success();
106
107 uint32_t NumFreeBlocks = FreeBlocks.count();
108 if (NumFreeBlocks < NumBlocks) {
109 if (!IsGrowable)
110 return make_error<MSFError>(msf_error_code::insufficient_buffer,
111 "There are no free Blocks in the file");
112 uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
113 uint32_t OldBlockCount = FreeBlocks.size();
114 uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
115 uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
116 FreeBlocks.resize(NewBlockCount, true);
117 // If we crossed over an fpm page, we actually need to allocate 2 extra
118 // blocks for each FPM group crossed and mark both blocks from the group as
119 // used. FPM blocks are marked as allocated regardless of whether or not
120 // they ultimately describe the status of blocks in the file. This means
121 // that not only are extraneous blocks at the end of the main FPM marked as
122 // allocated, but also blocks from the alternate FPM are always marked as
123 // allocated.
124 while (NextFpmBlock < NewBlockCount) {
125 NewBlockCount += 2;
126 FreeBlocks.resize(NewBlockCount, true);
127 FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
128 NextFpmBlock += BlockSize;
129 }
130 }
131
132 int I = 0;
133 int Block = FreeBlocks.find_first();
134 do {
135 assert(Block != -1 && "We ran out of Blocks!");
136
137 uint32_t NextBlock = static_cast<uint32_t>(Block);
138 Blocks[I++] = NextBlock;
139 FreeBlocks.reset(NextBlock);
140 Block = FreeBlocks.find_next(Block);
141 } while (--NumBlocks > 0);
142 return Error::success();
143 }
144
getNumUsedBlocks() const145 uint32_t MSFBuilder::getNumUsedBlocks() const {
146 return getTotalBlockCount() - getNumFreeBlocks();
147 }
148
getNumFreeBlocks() const149 uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
150
getTotalBlockCount() const151 uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
152
isBlockFree(uint32_t Idx) const153 bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
154
addStream(uint32_t Size,ArrayRef<uint32_t> Blocks)155 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
156 ArrayRef<uint32_t> Blocks) {
157 // Add a new stream mapped to the specified blocks. Verify that the specified
158 // blocks are both necessary and sufficient for holding the requested number
159 // of bytes, and verify that all requested blocks are free.
160 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
161 if (ReqBlocks != Blocks.size())
162 return make_error<MSFError>(
163 msf_error_code::invalid_format,
164 "Incorrect number of blocks for requested stream size");
165 for (auto Block : Blocks) {
166 if (Block >= FreeBlocks.size())
167 FreeBlocks.resize(Block + 1, true);
168
169 if (!FreeBlocks.test(Block))
170 return make_error<MSFError>(
171 msf_error_code::unspecified,
172 "Attempt to re-use an already allocated block");
173 }
174 // Mark all the blocks occupied by the new stream as not free.
175 for (auto Block : Blocks) {
176 FreeBlocks.reset(Block);
177 }
178 StreamData.push_back(std::make_pair(Size, Blocks));
179 return StreamData.size() - 1;
180 }
181
addStream(uint32_t Size)182 Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
183 uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
184 std::vector<uint32_t> NewBlocks;
185 NewBlocks.resize(ReqBlocks);
186 if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
187 return std::move(EC);
188 StreamData.push_back(std::make_pair(Size, NewBlocks));
189 return StreamData.size() - 1;
190 }
191
setStreamSize(uint32_t Idx,uint32_t Size)192 Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
193 uint32_t OldSize = getStreamSize(Idx);
194 if (OldSize == Size)
195 return Error::success();
196
197 uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
198 uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
199
200 if (NewBlocks > OldBlocks) {
201 uint32_t AddedBlocks = NewBlocks - OldBlocks;
202 // If we're growing, we have to allocate new Blocks.
203 std::vector<uint32_t> AddedBlockList;
204 AddedBlockList.resize(AddedBlocks);
205 if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
206 return EC;
207 auto &CurrentBlocks = StreamData[Idx].second;
208 CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
209 AddedBlockList.end());
210 } else if (OldBlocks > NewBlocks) {
211 // For shrinking, free all the Blocks in the Block map, update the stream
212 // data, then shrink the directory.
213 uint32_t RemovedBlocks = OldBlocks - NewBlocks;
214 auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
215 auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
216 for (auto P : RemovedBlockList)
217 FreeBlocks[P] = true;
218 StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
219 }
220
221 StreamData[Idx].first = Size;
222 return Error::success();
223 }
224
getNumStreams() const225 uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
226
getStreamSize(uint32_t StreamIdx) const227 uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
228 return StreamData[StreamIdx].first;
229 }
230
getStreamBlocks(uint32_t StreamIdx) const231 ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
232 return StreamData[StreamIdx].second;
233 }
234
computeDirectoryByteSize() const235 uint32_t MSFBuilder::computeDirectoryByteSize() const {
236 // The directory has the following layout, where each item is a ulittle32_t:
237 // NumStreams
238 // StreamSizes[NumStreams]
239 // StreamBlocks[NumStreams][]
240 uint32_t Size = sizeof(ulittle32_t); // NumStreams
241 Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
242 for (const auto &D : StreamData) {
243 uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
244 assert(ExpectedNumBlocks == D.second.size() &&
245 "Unexpected number of blocks");
246 Size += ExpectedNumBlocks * sizeof(ulittle32_t);
247 }
248 return Size;
249 }
250
generateLayout()251 Expected<MSFLayout> MSFBuilder::generateLayout() {
252 SuperBlock *SB = Allocator.Allocate<SuperBlock>();
253 MSFLayout L;
254 L.SB = SB;
255
256 std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
257 SB->BlockMapAddr = BlockMapAddr;
258 SB->BlockSize = BlockSize;
259 SB->NumDirectoryBytes = computeDirectoryByteSize();
260 SB->FreeBlockMapBlock = FreePageMap;
261 SB->Unknown1 = Unknown1;
262
263 uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
264 if (NumDirectoryBlocks > DirectoryBlocks.size()) {
265 // Our hint wasn't enough to satisfy the entire directory. Allocate
266 // remaining pages.
267 std::vector<uint32_t> ExtraBlocks;
268 uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
269 ExtraBlocks.resize(NumExtraBlocks);
270 if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
271 return std::move(EC);
272 DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
273 ExtraBlocks.end());
274 } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
275 uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
276 for (auto B :
277 ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
278 FreeBlocks[B] = true;
279 DirectoryBlocks.resize(NumDirectoryBlocks);
280 }
281
282 // Don't set the number of blocks in the file until after allocating Blocks
283 // for the directory, since the allocation might cause the file to need to
284 // grow.
285 SB->NumBlocks = FreeBlocks.size();
286
287 ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
288 std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
289 DirBlocks);
290 L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
291
292 // The stream sizes should be re-allocated as a stable pointer and the stream
293 // map should have each of its entries allocated as a separate stable pointer.
294 if (!StreamData.empty()) {
295 ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
296 L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
297 L.StreamMap.resize(StreamData.size());
298 for (uint32_t I = 0; I < StreamData.size(); ++I) {
299 Sizes[I] = StreamData[I].first;
300 ulittle32_t *BlockList =
301 Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
302 std::uninitialized_copy_n(StreamData[I].second.begin(),
303 StreamData[I].second.size(), BlockList);
304 L.StreamMap[I] =
305 ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
306 }
307 }
308
309 L.FreePageMap = FreeBlocks;
310
311 return L;
312 }
313
commitFpm(WritableBinaryStream & MsfBuffer,const MSFLayout & Layout,BumpPtrAllocator & Allocator)314 static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
315 BumpPtrAllocator &Allocator) {
316 auto FpmStream =
317 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
318
319 // We only need to create the alt fpm stream so that it gets initialized.
320 WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
321 true);
322
323 uint32_t BI = 0;
324 BinaryStreamWriter FpmWriter(*FpmStream);
325 while (BI < Layout.SB->NumBlocks) {
326 uint8_t ThisByte = 0;
327 for (uint32_t I = 0; I < 8; ++I) {
328 bool IsFree =
329 (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
330 uint8_t Mask = uint8_t(IsFree) << I;
331 ThisByte |= Mask;
332 ++BI;
333 }
334 cantFail(FpmWriter.writeObject(ThisByte));
335 }
336 assert(FpmWriter.bytesRemaining() == 0);
337 }
338
commit(StringRef Path,MSFLayout & Layout)339 Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
340 MSFLayout &Layout) {
341 Expected<MSFLayout> L = generateLayout();
342 if (!L)
343 return L.takeError();
344
345 Layout = std::move(*L);
346
347 uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
348 auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
349 if (auto EC = OutFileOrError.takeError())
350 return std::move(EC);
351
352 FileBufferByteStream Buffer(std::move(*OutFileOrError),
353 llvm::support::little);
354 BinaryStreamWriter Writer(Buffer);
355
356 if (auto EC = Writer.writeObject(*Layout.SB))
357 return std::move(EC);
358
359 commitFpm(Buffer, Layout, Allocator);
360
361 uint32_t BlockMapOffset =
362 msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
363 Writer.setOffset(BlockMapOffset);
364 if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
365 return std::move(EC);
366
367 auto DirStream = WritableMappedBlockStream::createDirectoryStream(
368 Layout, Buffer, Allocator);
369 BinaryStreamWriter DW(*DirStream);
370 if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
371 return std::move(EC);
372
373 if (auto EC = DW.writeArray(Layout.StreamSizes))
374 return std::move(EC);
375
376 for (const auto &Blocks : Layout.StreamMap) {
377 if (auto EC = DW.writeArray(Blocks))
378 return std::move(EC);
379 }
380
381 return std::move(Buffer);
382 }
383