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