Line data Source code
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 :
39 126 : MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
40 126 : BumpPtrAllocator &Allocator)
41 : : Allocator(Allocator), IsGrowable(CanGrow),
42 : FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
43 126 : BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
44 : FreeBlocks[kSuperBlockBlock] = false;
45 : FreeBlocks[kFreePageMap0Block] = false;
46 : FreeBlocks[kFreePageMap1Block] = false;
47 126 : FreeBlocks[BlockMapAddr] = false;
48 126 : }
49 :
50 126 : 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 252 : return MSFBuilder(BlockSize,
58 252 : std::max(MinBlockCount, msf::getMinimumBlockCount()),
59 : CanGrow, Allocator);
60 : }
61 :
62 0 : Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
63 0 : if (Addr == BlockMapAddr)
64 : return Error::success();
65 :
66 0 : if (Addr >= FreeBlocks.size()) {
67 0 : if (!IsGrowable)
68 : return make_error<MSFError>(msf_error_code::insufficient_buffer,
69 : "Cannot grow the number of blocks");
70 0 : FreeBlocks.resize(Addr + 1, true);
71 : }
72 :
73 0 : 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 0 : FreeBlocks[BlockMapAddr] = true;
78 : FreeBlocks[Addr] = false;
79 0 : BlockMapAddr = Addr;
80 : return Error::success();
81 : }
82 :
83 0 : void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
84 :
85 0 : void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
86 :
87 3 : Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
88 3 : for (auto B : DirectoryBlocks)
89 : FreeBlocks[B] = true;
90 7 : for (auto B : DirBlocks) {
91 4 : 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 6 : DirectoryBlocks = DirBlocks;
99 : return Error::success();
100 : }
101 :
102 2015 : Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
103 : MutableArrayRef<uint32_t> Blocks) {
104 2015 : if (NumBlocks == 0)
105 : return Error::success();
106 :
107 : uint32_t NumFreeBlocks = FreeBlocks.count();
108 1348 : if (NumFreeBlocks < NumBlocks) {
109 1348 : if (!IsGrowable)
110 : return make_error<MSFError>(msf_error_code::insufficient_buffer,
111 : "There are no free Blocks in the file");
112 1348 : uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
113 : uint32_t OldBlockCount = FreeBlocks.size();
114 1348 : uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
115 1348 : uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
116 1348 : 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 1351 : while (NextFpmBlock < NewBlockCount) {
125 3 : NewBlockCount += 2;
126 3 : FreeBlocks.resize(NewBlockCount, true);
127 3 : FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
128 3 : NextFpmBlock += BlockSize;
129 : }
130 : }
131 :
132 : int I = 0;
133 1348 : int Block = FreeBlocks.find_first();
134 : do {
135 : assert(Block != -1 && "We ran out of Blocks!");
136 :
137 15829 : uint32_t NextBlock = static_cast<uint32_t>(Block);
138 17177 : Blocks[I++] = NextBlock;
139 : FreeBlocks.reset(NextBlock);
140 : Block = FreeBlocks.find_next(Block);
141 15829 : } while (--NumBlocks > 0);
142 : return Error::success();
143 : }
144 :
145 4 : uint32_t MSFBuilder::getNumUsedBlocks() const {
146 4 : return getTotalBlockCount() - getNumFreeBlocks();
147 : }
148 :
149 8 : uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
150 :
151 4 : uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
152 :
153 46 : bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
154 :
155 3 : 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 3 : uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
161 3 : 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 13 : for (auto Block : Blocks) {
166 11 : if (Block >= FreeBlocks.size())
167 1 : FreeBlocks.resize(Block + 1, true);
168 :
169 11 : 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 12 : for (auto Block : Blocks) {
176 : FreeBlocks.reset(Block);
177 : }
178 2 : StreamData.push_back(std::make_pair(Size, Blocks));
179 4 : return StreamData.size() - 1;
180 : }
181 :
182 1456 : Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
183 2912 : uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
184 : std::vector<uint32_t> NewBlocks;
185 1456 : NewBlocks.resize(ReqBlocks);
186 1456 : if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
187 : return std::move(EC);
188 1456 : StreamData.push_back(std::make_pair(Size, NewBlocks));
189 2912 : return StreamData.size() - 1;
190 : }
191 :
192 556 : Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
193 556 : uint32_t OldSize = getStreamSize(Idx);
194 556 : if (OldSize == Size)
195 : return Error::success();
196 :
197 445 : uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
198 445 : uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
199 :
200 445 : if (NewBlocks > OldBlocks) {
201 442 : uint32_t AddedBlocks = NewBlocks - OldBlocks;
202 : // If we're growing, we have to allocate new Blocks.
203 : std::vector<uint32_t> AddedBlockList;
204 442 : AddedBlockList.resize(AddedBlocks);
205 442 : if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
206 : return EC;
207 884 : auto &CurrentBlocks = StreamData[Idx].second;
208 : CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
209 442 : AddedBlockList.end());
210 3 : } 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 1 : uint32_t RemovedBlocks = OldBlocks - NewBlocks;
214 1 : auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
215 : auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
216 2 : for (auto P : RemovedBlockList)
217 : FreeBlocks[P] = true;
218 2 : StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
219 : }
220 :
221 890 : StreamData[Idx].first = Size;
222 : return Error::success();
223 : }
224 :
225 2 : uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
226 :
227 565 : uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
228 1130 : return StreamData[StreamIdx].first;
229 : }
230 :
231 9 : ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
232 18 : return StreamData[StreamIdx].second;
233 : }
234 :
235 119 : 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 238 : Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
242 1568 : for (const auto &D : StreamData) {
243 1449 : uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
244 : assert(ExpectedNumBlocks == D.second.size() &&
245 : "Unexpected number of blocks");
246 1449 : Size += ExpectedNumBlocks * sizeof(ulittle32_t);
247 : }
248 119 : return Size;
249 : }
250 :
251 119 : Expected<MSFLayout> MSFBuilder::generateLayout() {
252 119 : SuperBlock *SB = Allocator.Allocate<SuperBlock>();
253 119 : MSFLayout L;
254 119 : L.SB = SB;
255 :
256 119 : std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
257 119 : SB->BlockMapAddr = BlockMapAddr;
258 119 : SB->BlockSize = BlockSize;
259 119 : SB->NumDirectoryBytes = computeDirectoryByteSize();
260 119 : SB->FreeBlockMapBlock = FreePageMap;
261 119 : SB->Unknown1 = Unknown1;
262 :
263 238 : uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
264 238 : 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 117 : uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
269 117 : ExtraBlocks.resize(NumExtraBlocks);
270 117 : if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
271 : return std::move(EC);
272 : DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
273 234 : ExtraBlocks.end());
274 2 : } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
275 1 : uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
276 2 : for (auto B :
277 2 : ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
278 : FreeBlocks[B] = true;
279 1 : 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 119 : SB->NumBlocks = FreeBlocks.size();
286 :
287 119 : ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
288 : std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
289 : DirBlocks);
290 119 : 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 119 : if (!StreamData.empty()) {
295 118 : ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
296 118 : L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
297 118 : L.StreamMap.resize(StreamData.size());
298 3134 : for (uint32_t I = 0; I < StreamData.size(); ++I) {
299 1449 : Sizes[I] = StreamData[I].first;
300 : ulittle32_t *BlockList =
301 1449 : Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
302 1449 : std::uninitialized_copy_n(StreamData[I].second.begin(),
303 1449 : StreamData[I].second.size(), BlockList);
304 2898 : L.StreamMap[I] =
305 1449 : ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
306 : }
307 : }
308 :
309 119 : L.FreePageMap = FreeBlocks;
310 :
311 : return L;
312 : }
313 :
314 111 : static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
315 : BumpPtrAllocator &Allocator) {
316 : auto FpmStream =
317 111 : WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
318 :
319 : // We only need to create the alt fpm stream so that it gets initialized.
320 222 : WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
321 : true);
322 :
323 : uint32_t BI = 0;
324 111 : BinaryStreamWriter FpmWriter(*FpmStream);
325 756 : while (BI < Layout.SB->NumBlocks) {
326 267 : uint8_t ThisByte = 0;
327 2403 : for (uint32_t I = 0; I < 8; ++I) {
328 : bool IsFree =
329 2136 : (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
330 2136 : uint8_t Mask = uint8_t(IsFree) << I;
331 2136 : ThisByte |= Mask;
332 2136 : ++BI;
333 : }
334 267 : cantFail(FpmWriter.writeObject(ThisByte));
335 : }
336 : assert(FpmWriter.bytesRemaining() == 0);
337 111 : }
338 :
339 111 : Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
340 : MSFLayout &Layout) {
341 222 : Expected<MSFLayout> L = generateLayout();
342 111 : if (!L)
343 : return L.takeError();
344 :
345 111 : Layout = std::move(*L);
346 :
347 111 : uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
348 222 : auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
349 111 : if (auto EC = OutFileOrError.takeError())
350 : return std::move(EC);
351 :
352 : FileBufferByteStream Buffer(std::move(*OutFileOrError),
353 111 : llvm::support::little);
354 111 : BinaryStreamWriter Writer(Buffer);
355 :
356 222 : if (auto EC = Writer.writeObject(*Layout.SB))
357 : return std::move(EC);
358 :
359 111 : commitFpm(Buffer, Layout, Allocator);
360 :
361 : uint32_t BlockMapOffset =
362 444 : msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
363 : Writer.setOffset(BlockMapOffset);
364 222 : if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
365 : return std::move(EC);
366 :
367 : auto DirStream = WritableMappedBlockStream::createDirectoryStream(
368 222 : Layout, Buffer, Allocator);
369 111 : BinaryStreamWriter DW(*DirStream);
370 222 : if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
371 : return std::move(EC);
372 :
373 222 : if (auto EC = DW.writeArray(Layout.StreamSizes))
374 : return std::move(EC);
375 :
376 1551 : for (const auto &Blocks : Layout.StreamMap) {
377 2880 : if (auto EC = DW.writeArray(Blocks))
378 : return std::move(EC);
379 : }
380 :
381 : return std::move(Buffer);
382 : }
|
