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