1 files changed, 381 insertions, 0 deletions

diff --git a/contrib/llvm-project/llvm/lib/DebugInfo/MSF/MSFBuilder.cpp b/contrib/llvm-project/llvm/lib/DebugInfo/MSF/MSFBuilder.cpp
new file mode 100644
index 000000000000..c6fe764ab7e0
--- /dev/null
+++ b/contrib/llvm-project/llvm/lib/DebugInfo/MSF/MSFBuilder.cpp
@@ -0,0 +1,381 @@
+//===- MSFBuilder.cpp -----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/MSF/MSFBuilder.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/DebugInfo/MSF/MSFError.h"
+#include "llvm/DebugInfo/MSF/MappedBlockStream.h"
+#include "llvm/Support/BinaryByteStream.h"
+#include "llvm/Support/BinaryStreamWriter.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileOutputBuffer.h"
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <cstring>
+#include <memory>
+#include <utility>
+#include <vector>
+
+using namespace llvm;
+using namespace llvm::msf;
+using namespace llvm::support;
+
+static const uint32_t kSuperBlockBlock = 0;
+static const uint32_t kFreePageMap0Block = 1;
+static const uint32_t kFreePageMap1Block = 2;
+static const uint32_t kNumReservedPages = 3;
+
+static const uint32_t kDefaultFreePageMap = kFreePageMap1Block;
+static const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
+
+MSFBuilder::MSFBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
+                       BumpPtrAllocator &Allocator)
+    : Allocator(Allocator), IsGrowable(CanGrow),
+      FreePageMap(kDefaultFreePageMap), BlockSize(BlockSize),
+      BlockMapAddr(kDefaultBlockMapAddr), FreeBlocks(MinBlockCount, true) {
+  FreeBlocks[kSuperBlockBlock] = false;
+  FreeBlocks[kFreePageMap0Block] = false;
+  FreeBlocks[kFreePageMap1Block] = false;
+  FreeBlocks[BlockMapAddr] = false;
+}
+
+Expected<MSFBuilder> MSFBuilder::create(BumpPtrAllocator &Allocator,
+                                        uint32_t BlockSize,
+                                        uint32_t MinBlockCount, bool CanGrow) {
+  if (!isValidBlockSize(BlockSize))
+    return make_error<MSFError>(msf_error_code::invalid_format,
+                                "The requested block size is unsupported");
+
+  return MSFBuilder(BlockSize,
+                    std::max(MinBlockCount, msf::getMinimumBlockCount()),
+                    CanGrow, Allocator);
+}
+
+Error MSFBuilder::setBlockMapAddr(uint32_t Addr) {
+  if (Addr == BlockMapAddr)
+    return Error::success();
+
+  if (Addr >= FreeBlocks.size()) {
+    if (!IsGrowable)
+      return make_error<MSFError>(msf_error_code::insufficient_buffer,
+                                  "Cannot grow the number of blocks");
+    FreeBlocks.resize(Addr + 1, true);
+  }
+
+  if (!isBlockFree(Addr))
+    return make_error<MSFError>(
+        msf_error_code::block_in_use,
+        "Requested block map address is already in use");
+  FreeBlocks[BlockMapAddr] = true;
+  FreeBlocks[Addr] = false;
+  BlockMapAddr = Addr;
+  return Error::success();
+}
+
+void MSFBuilder::setFreePageMap(uint32_t Fpm) { FreePageMap = Fpm; }
+
+void MSFBuilder::setUnknown1(uint32_t Unk1) { Unknown1 = Unk1; }
+
+Error MSFBuilder::setDirectoryBlocksHint(ArrayRef<uint32_t> DirBlocks) {
+  for (auto B : DirectoryBlocks)
+    FreeBlocks[B] = true;
+  for (auto B : DirBlocks) {
+    if (!isBlockFree(B)) {
+      return make_error<MSFError>(msf_error_code::unspecified,
+                                  "Attempt to reuse an allocated block");
+    }
+    FreeBlocks[B] = false;
+  }
+
+  DirectoryBlocks = DirBlocks;
+  return Error::success();
+}
+
+Error MSFBuilder::allocateBlocks(uint32_t NumBlocks,
+                                 MutableArrayRef<uint32_t> Blocks) {
+  if (NumBlocks == 0)
+    return Error::success();
+
+  uint32_t NumFreeBlocks = FreeBlocks.count();
+  if (NumFreeBlocks < NumBlocks) {
+    if (!IsGrowable)
+      return make_error<MSFError>(msf_error_code::insufficient_buffer,
+                                  "There are no free Blocks in the file");
+    uint32_t AllocBlocks = NumBlocks - NumFreeBlocks;
+    uint32_t OldBlockCount = FreeBlocks.size();
+    uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
+    uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
+    FreeBlocks.resize(NewBlockCount, true);
+    // If we crossed over an fpm page, we actually need to allocate 2 extra
+    // blocks for each FPM group crossed and mark both blocks from the group as
+    // used.  FPM blocks are marked as allocated regardless of whether or not
+    // they ultimately describe the status of blocks in the file.  This means
+    // that not only are extraneous blocks at the end of the main FPM marked as
+    // allocated, but also blocks from the alternate FPM are always marked as
+    // allocated.
+    while (NextFpmBlock < NewBlockCount) {
+      NewBlockCount += 2;
+      FreeBlocks.resize(NewBlockCount, true);
+      FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
+      NextFpmBlock += BlockSize;
+    }
+  }
+
+  int I = 0;
+  int Block = FreeBlocks.find_first();
+  do {
+    assert(Block != -1 && "We ran out of Blocks!");
+
+    uint32_t NextBlock = static_cast<uint32_t>(Block);
+    Blocks[I++] = NextBlock;
+    FreeBlocks.reset(NextBlock);
+    Block = FreeBlocks.find_next(Block);
+  } while (--NumBlocks > 0);
+  return Error::success();
+}
+
+uint32_t MSFBuilder::getNumUsedBlocks() const {
+  return getTotalBlockCount() - getNumFreeBlocks();
+}
+
+uint32_t MSFBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); }
+
+uint32_t MSFBuilder::getTotalBlockCount() const { return FreeBlocks.size(); }
+
+bool MSFBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; }
+
+Expected<uint32_t> MSFBuilder::addStream(uint32_t Size,
+                                         ArrayRef<uint32_t> Blocks) {
+  // Add a new stream mapped to the specified blocks.  Verify that the specified
+  // blocks are both necessary and sufficient for holding the requested number
+  // of bytes, and verify that all requested blocks are free.
+  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
+  if (ReqBlocks != Blocks.size())
+    return make_error<MSFError>(
+        msf_error_code::invalid_format,
+        "Incorrect number of blocks for requested stream size");
+  for (auto Block : Blocks) {
+    if (Block >= FreeBlocks.size())
+      FreeBlocks.resize(Block + 1, true);
+
+    if (!FreeBlocks.test(Block))
+      return make_error<MSFError>(
+          msf_error_code::unspecified,
+          "Attempt to re-use an already allocated block");
+  }
+  // Mark all the blocks occupied by the new stream as not free.
+  for (auto Block : Blocks) {
+    FreeBlocks.reset(Block);
+  }
+  StreamData.push_back(std::make_pair(Size, Blocks));
+  return StreamData.size() - 1;
+}
+
+Expected<uint32_t> MSFBuilder::addStream(uint32_t Size) {
+  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
+  std::vector<uint32_t> NewBlocks;
+  NewBlocks.resize(ReqBlocks);
+  if (auto EC = allocateBlocks(ReqBlocks, NewBlocks))
+    return std::move(EC);
+  StreamData.push_back(std::make_pair(Size, NewBlocks));
+  return StreamData.size() - 1;
+}
+
+Error MSFBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
+  uint32_t OldSize = getStreamSize(Idx);
+  if (OldSize == Size)
+    return Error::success();
+
+  uint32_t NewBlocks = bytesToBlocks(Size, BlockSize);
+  uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize);
+
+  if (NewBlocks > OldBlocks) {
+    uint32_t AddedBlocks = NewBlocks - OldBlocks;
+    // If we're growing, we have to allocate new Blocks.
+    std::vector<uint32_t> AddedBlockList;
+    AddedBlockList.resize(AddedBlocks);
+    if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList))
+      return EC;
+    auto &CurrentBlocks = StreamData[Idx].second;
+    CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(),
+                         AddedBlockList.end());
+  } else if (OldBlocks > NewBlocks) {
+    // For shrinking, free all the Blocks in the Block map, update the stream
+    // data, then shrink the directory.
+    uint32_t RemovedBlocks = OldBlocks - NewBlocks;
+    auto CurrentBlocks = ArrayRef<uint32_t>(StreamData[Idx].second);
+    auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks);
+    for (auto P : RemovedBlockList)
+      FreeBlocks[P] = true;
+    StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks);
+  }
+
+  StreamData[Idx].first = Size;
+  return Error::success();
+}
+
+uint32_t MSFBuilder::getNumStreams() const { return StreamData.size(); }
+
+uint32_t MSFBuilder::getStreamSize(uint32_t StreamIdx) const {
+  return StreamData[StreamIdx].first;
+}
+
+ArrayRef<uint32_t> MSFBuilder::getStreamBlocks(uint32_t StreamIdx) const {
+  return StreamData[StreamIdx].second;
+}
+
+uint32_t MSFBuilder::computeDirectoryByteSize() const {
+  // The directory has the following layout, where each item is a ulittle32_t:
+  //    NumStreams
+  //    StreamSizes[NumStreams]
+  //    StreamBlocks[NumStreams][]
+  uint32_t Size = sizeof(ulittle32_t);             // NumStreams
+  Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes
+  for (const auto &D : StreamData) {
+    uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize);
+    assert(ExpectedNumBlocks == D.second.size() &&
+           "Unexpected number of blocks");
+    Size += ExpectedNumBlocks * sizeof(ulittle32_t);
+  }
+  return Size;
+}
+
+Expected<MSFLayout> MSFBuilder::generateLayout() {
+  SuperBlock *SB = Allocator.Allocate<SuperBlock>();
+  MSFLayout L;
+  L.SB = SB;
+
+  std::memcpy(SB->MagicBytes, Magic, sizeof(Magic));
+  SB->BlockMapAddr = BlockMapAddr;
+  SB->BlockSize = BlockSize;
+  SB->NumDirectoryBytes = computeDirectoryByteSize();
+  SB->FreeBlockMapBlock = FreePageMap;
+  SB->Unknown1 = Unknown1;
+
+  uint32_t NumDirectoryBlocks = bytesToBlocks(SB->NumDirectoryBytes, BlockSize);
+  if (NumDirectoryBlocks > DirectoryBlocks.size()) {
+    // Our hint wasn't enough to satisfy the entire directory.  Allocate
+    // remaining pages.
+    std::vector<uint32_t> ExtraBlocks;
+    uint32_t NumExtraBlocks = NumDirectoryBlocks - DirectoryBlocks.size();
+    ExtraBlocks.resize(NumExtraBlocks);
+    if (auto EC = allocateBlocks(NumExtraBlocks, ExtraBlocks))
+      return std::move(EC);
+    DirectoryBlocks.insert(DirectoryBlocks.end(), ExtraBlocks.begin(),
+                           ExtraBlocks.end());
+  } else if (NumDirectoryBlocks < DirectoryBlocks.size()) {
+    uint32_t NumUnnecessaryBlocks = DirectoryBlocks.size() - NumDirectoryBlocks;
+    for (auto B :
+         ArrayRef<uint32_t>(DirectoryBlocks).drop_back(NumUnnecessaryBlocks))
+      FreeBlocks[B] = true;
+    DirectoryBlocks.resize(NumDirectoryBlocks);
+  }
+
+  // Don't set the number of blocks in the file until after allocating Blocks
+  // for the directory, since the allocation might cause the file to need to
+  // grow.
+  SB->NumBlocks = FreeBlocks.size();
+
+  ulittle32_t *DirBlocks = Allocator.Allocate<ulittle32_t>(NumDirectoryBlocks);
+  std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks,
+                            DirBlocks);
+  L.DirectoryBlocks = ArrayRef<ulittle32_t>(DirBlocks, NumDirectoryBlocks);
+
+  // The stream sizes should be re-allocated as a stable pointer and the stream
+  // map should have each of its entries allocated as a separate stable pointer.
+  if (!StreamData.empty()) {
+    ulittle32_t *Sizes = Allocator.Allocate<ulittle32_t>(StreamData.size());
+    L.StreamSizes = ArrayRef<ulittle32_t>(Sizes, StreamData.size());
+    L.StreamMap.resize(StreamData.size());
+    for (uint32_t I = 0; I < StreamData.size(); ++I) {
+      Sizes[I] = StreamData[I].first;
+      ulittle32_t *BlockList =
+          Allocator.Allocate<ulittle32_t>(StreamData[I].second.size());
+      std::uninitialized_copy_n(StreamData[I].second.begin(),
+                                StreamData[I].second.size(), BlockList);
+      L.StreamMap[I] =
+          ArrayRef<ulittle32_t>(BlockList, StreamData[I].second.size());
+    }
+  }
+
+  L.FreePageMap = FreeBlocks;
+
+  return L;
+}
+
+static void commitFpm(WritableBinaryStream &MsfBuffer, const MSFLayout &Layout,
+                      BumpPtrAllocator &Allocator) {
+  auto FpmStream =
+      WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
+
+  // We only need to create the alt fpm stream so that it gets initialized.
+  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
+                                             true);
+
+  uint32_t BI = 0;
+  BinaryStreamWriter FpmWriter(*FpmStream);
+  while (BI < Layout.SB->NumBlocks) {
+    uint8_t ThisByte = 0;
+    for (uint32_t I = 0; I < 8; ++I) {
+      bool IsFree =
+          (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
+      uint8_t Mask = uint8_t(IsFree) << I;
+      ThisByte |= Mask;
+      ++BI;
+    }
+    cantFail(FpmWriter.writeObject(ThisByte));
+  }
+  assert(FpmWriter.bytesRemaining() == 0);
+}
+
+Expected<FileBufferByteStream> MSFBuilder::commit(StringRef Path,
+                                                  MSFLayout &Layout) {
+  Expected<MSFLayout> L = generateLayout();
+  if (!L)
+    return L.takeError();
+
+  Layout = std::move(*L);
+
+  uint64_t FileSize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
+  auto OutFileOrError = FileOutputBuffer::create(Path, FileSize);
+  if (auto EC = OutFileOrError.takeError())
+    return std::move(EC);
+
+  FileBufferByteStream Buffer(std::move(*OutFileOrError),
+                              llvm::support::little);
+  BinaryStreamWriter Writer(Buffer);
+
+  if (auto EC = Writer.writeObject(*Layout.SB))
+    return std::move(EC);
+
+  commitFpm(Buffer, Layout, Allocator);
+
+  uint32_t BlockMapOffset =
+      msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
+  Writer.setOffset(BlockMapOffset);
+  if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
+    return std::move(EC);
+
+  auto DirStream = WritableMappedBlockStream::createDirectoryStream(
+      Layout, Buffer, Allocator);
+  BinaryStreamWriter DW(*DirStream);
+  if (auto EC = DW.writeInteger<uint32_t>(Layout.StreamSizes.size()))
+    return std::move(EC);
+
+  if (auto EC = DW.writeArray(Layout.StreamSizes))
+    return std::move(EC);
+
+  for (const auto &Blocks : Layout.StreamMap) {
+    if (auto EC = DW.writeArray(Blocks))
+      return std::move(EC);
+  }
+
+  return std::move(Buffer);
+}