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