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