Revert "[msf] Rename Msf to MSF."

This reverts commit 4d1557ffac41e079bcb1abbcf04f512474dcd6fe.

llvm-svn: 277194
diff --git a/llvm/lib/DebugInfo/Msf/CMakeLists.txt b/llvm/lib/DebugInfo/Msf/CMakeLists.txt
new file mode 100644
index 0000000..5342c54
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/CMakeLists.txt
@@ -0,0 +1,10 @@
+add_llvm_library(LLVMDebugInfoMsf
+  MappedBlockStream.cpp
+  MsfBuilder.cpp
+  MsfCommon.cpp
+  MsfError.cpp
+  StreamReader.cpp
+  StreamWriter.cpp
+  ADDITIONAL_HEADER_DIRS
+  "${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/MSF"
+  )
diff --git a/llvm/lib/DebugInfo/Msf/LLVMBuild.txt b/llvm/lib/DebugInfo/Msf/LLVMBuild.txt
new file mode 100644
index 0000000..4598c43
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/LLVMBuild.txt
@@ -0,0 +1,22 @@
+;===- ./lib/DebugInfo/Msf/LLVMBuild.txt -------------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = DebugInfoMsf
+parent = DebugInfo
+required_libraries = Support
diff --git a/llvm/lib/DebugInfo/Msf/MappedBlockStream.cpp b/llvm/lib/DebugInfo/Msf/MappedBlockStream.cpp
new file mode 100644
index 0000000..7d5be88
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/MappedBlockStream.cpp
@@ -0,0 +1,380 @@
+//===- MappedBlockStream.cpp - Reads stream data from an MSF file ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/MappedBlockStream.h"
+
+#include "llvm/DebugInfo/Msf/IMsfFile.h"
+#include "llvm/DebugInfo/Msf/MsfCommon.h"
+#include "llvm/DebugInfo/Msf/MsfError.h"
+#include "llvm/DebugInfo/Msf/MsfStreamLayout.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+namespace {
+template <typename Base> class MappedBlockStreamImpl : public Base {
+public:
+  template <typename... Args>
+  MappedBlockStreamImpl(Args &&... Params)
+      : Base(std::forward<Args>(Params)...) {}
+};
+}
+
+typedef std::pair<uint32_t, uint32_t> Interval;
+static Interval intersect(const Interval &I1, const Interval &I2) {
+  return std::make_pair(std::max(I1.first, I2.first),
+                        std::min(I1.second, I2.second));
+}
+
+MappedBlockStream::MappedBlockStream(uint32_t BlockSize, uint32_t NumBlocks,
+                                     const MsfStreamLayout &Layout,
+                                     const ReadableStream &MsfData)
+    : BlockSize(BlockSize), NumBlocks(NumBlocks), StreamLayout(Layout),
+      MsfData(MsfData) {}
+
+std::unique_ptr<MappedBlockStream>
+MappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
+                                const MsfStreamLayout &Layout,
+                                const ReadableStream &MsfData) {
+  return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
+      BlockSize, NumBlocks, Layout, MsfData);
+}
+
+std::unique_ptr<MappedBlockStream>
+MappedBlockStream::createIndexedStream(const MsfLayout &Layout,
+                                       const ReadableStream &MsfData,
+                                       uint32_t StreamIndex) {
+  MsfStreamLayout SL;
+  SL.Blocks = Layout.StreamMap[StreamIndex];
+  SL.Length = Layout.StreamSizes[StreamIndex];
+  return llvm::make_unique<MappedBlockStreamImpl<MappedBlockStream>>(
+      Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
+std::unique_ptr<MappedBlockStream>
+MappedBlockStream::createDirectoryStream(const MsfLayout &Layout,
+                                         const ReadableStream &MsfData) {
+  MsfStreamLayout SL;
+  SL.Blocks = Layout.DirectoryBlocks;
+  SL.Length = Layout.SB->NumDirectoryBytes;
+  return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
+Error MappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
+                                   ArrayRef<uint8_t> &Buffer) const {
+  // Make sure we aren't trying to read beyond the end of the stream.
+  if (Size > StreamLayout.Length)
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+  if (Offset > StreamLayout.Length - Size)
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+
+  if (tryReadContiguously(Offset, Size, Buffer))
+    return Error::success();
+
+  auto CacheIter = CacheMap.find(Offset);
+  if (CacheIter != CacheMap.end()) {
+    // Try to find an alloc that was large enough for this request.
+    for (auto &Entry : CacheIter->second) {
+      if (Entry.size() >= Size) {
+        Buffer = Entry.slice(0, Size);
+        return Error::success();
+      }
+    }
+  }
+
+  // We couldn't find a buffer that started at the correct offset (the most
+  // common scenario).  Try to see if there is a buffer that starts at some
+  // other offset but overlaps the desired range.
+  for (auto &CacheItem : CacheMap) {
+    Interval RequestExtent = std::make_pair(Offset, Offset + Size);
+
+    // We already checked this one on the fast path above.
+    if (CacheItem.first == Offset)
+      continue;
+    // If the initial extent of the cached item is beyond the ending extent
+    // of the request, there is no overlap.
+    if (CacheItem.first >= Offset + Size)
+      continue;
+
+    // We really only have to check the last item in the list, since we append
+    // in order of increasing length.
+    if (CacheItem.second.empty())
+      continue;
+
+    auto CachedAlloc = CacheItem.second.back();
+    // If the initial extent of the request is beyond the ending extent of
+    // the cached item, there is no overlap.
+    Interval CachedExtent =
+        std::make_pair(CacheItem.first, CacheItem.first + CachedAlloc.size());
+    if (RequestExtent.first >= CachedExtent.first + CachedExtent.second)
+      continue;
+
+    Interval Intersection = intersect(CachedExtent, RequestExtent);
+    // Only use this if the entire request extent is contained in the cached
+    // extent.
+    if (Intersection != RequestExtent)
+      continue;
+
+    uint32_t CacheRangeOffset =
+        AbsoluteDifference(CachedExtent.first, Intersection.first);
+    Buffer = CachedAlloc.slice(CacheRangeOffset, Size);
+    return Error::success();
+  }
+
+  // Otherwise allocate a large enough buffer in the pool, memcpy the data
+  // into it, and return an ArrayRef to that.  Do not touch existing pool
+  // allocations, as existing clients may be holding a pointer which must
+  // not be invalidated.
+  uint8_t *WriteBuffer = static_cast<uint8_t *>(Pool.Allocate(Size, 8));
+  if (auto EC = readBytes(Offset, MutableArrayRef<uint8_t>(WriteBuffer, Size)))
+    return EC;
+
+  if (CacheIter != CacheMap.end()) {
+    CacheIter->second.emplace_back(WriteBuffer, Size);
+  } else {
+    std::vector<CacheEntry> List;
+    List.emplace_back(WriteBuffer, Size);
+    CacheMap.insert(std::make_pair(Offset, List));
+  }
+  Buffer = ArrayRef<uint8_t>(WriteBuffer, Size);
+  return Error::success();
+}
+
+Error MappedBlockStream::readLongestContiguousChunk(
+    uint32_t Offset, ArrayRef<uint8_t> &Buffer) const {
+  // Make sure we aren't trying to read beyond the end of the stream.
+  if (Offset >= StreamLayout.Length)
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+  uint32_t First = Offset / BlockSize;
+  uint32_t Last = First;
+
+  while (Last < NumBlocks - 1) {
+    if (StreamLayout.Blocks[Last] != StreamLayout.Blocks[Last + 1] - 1)
+      break;
+    ++Last;
+  }
+
+  uint32_t OffsetInFirstBlock = Offset % BlockSize;
+  uint32_t BytesFromFirstBlock = BlockSize - OffsetInFirstBlock;
+  uint32_t BlockSpan = Last - First + 1;
+  uint32_t ByteSpan = BytesFromFirstBlock + (BlockSpan - 1) * BlockSize;
+
+  ArrayRef<uint8_t> BlockData;
+  uint32_t MsfOffset = blockToOffset(StreamLayout.Blocks[First], BlockSize);
+  if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData))
+    return EC;
+
+  BlockData = BlockData.drop_front(OffsetInFirstBlock);
+  Buffer = ArrayRef<uint8_t>(BlockData.data(), ByteSpan);
+  return Error::success();
+}
+
+uint32_t MappedBlockStream::getLength() const { return StreamLayout.Length; }
+
+bool MappedBlockStream::tryReadContiguously(uint32_t Offset, uint32_t Size,
+                                            ArrayRef<uint8_t> &Buffer) const {
+  // Attempt to fulfill the request with a reference directly into the stream.
+  // This can work even if the request crosses a block boundary, provided that
+  // all subsequent blocks are contiguous.  For example, a 10k read with a 4k
+  // block size can be filled with a reference if, from the starting offset,
+  // 3 blocks in a row are contiguous.
+  uint32_t BlockNum = Offset / BlockSize;
+  uint32_t OffsetInBlock = Offset % BlockSize;
+  uint32_t BytesFromFirstBlock = std::min(Size, BlockSize - OffsetInBlock);
+  uint32_t NumAdditionalBlocks =
+      llvm::alignTo(Size - BytesFromFirstBlock, BlockSize) / BlockSize;
+
+  uint32_t RequiredContiguousBlocks = NumAdditionalBlocks + 1;
+  uint32_t E = StreamLayout.Blocks[BlockNum];
+  for (uint32_t I = 0; I < RequiredContiguousBlocks; ++I, ++E) {
+    if (StreamLayout.Blocks[I + BlockNum] != E)
+      return false;
+  }
+
+  // Read out the entire block where the requested offset starts.  Then drop
+  // bytes from the beginning so that the actual starting byte lines up with
+  // the requested starting byte.  Then, since we know this is a contiguous
+  // cross-block span, explicitly resize the ArrayRef to cover the entire
+  // request length.
+  ArrayRef<uint8_t> BlockData;
+  uint32_t FirstBlockAddr = StreamLayout.Blocks[BlockNum];
+  uint32_t MsfOffset = blockToOffset(FirstBlockAddr, BlockSize);
+  if (auto EC = MsfData.readBytes(MsfOffset, BlockSize, BlockData)) {
+    consumeError(std::move(EC));
+    return false;
+  }
+  BlockData = BlockData.drop_front(OffsetInBlock);
+  Buffer = ArrayRef<uint8_t>(BlockData.data(), Size);
+  return true;
+}
+
+Error MappedBlockStream::readBytes(uint32_t Offset,
+                                   MutableArrayRef<uint8_t> Buffer) const {
+  uint32_t BlockNum = Offset / BlockSize;
+  uint32_t OffsetInBlock = Offset % BlockSize;
+
+  // Make sure we aren't trying to read beyond the end of the stream.
+  if (Buffer.size() > StreamLayout.Length)
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+  if (Offset > StreamLayout.Length - Buffer.size())
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+
+  uint32_t BytesLeft = Buffer.size();
+  uint32_t BytesWritten = 0;
+  uint8_t *WriteBuffer = Buffer.data();
+  while (BytesLeft > 0) {
+    uint32_t StreamBlockAddr = StreamLayout.Blocks[BlockNum];
+
+    ArrayRef<uint8_t> BlockData;
+    uint32_t Offset = blockToOffset(StreamBlockAddr, BlockSize);
+    if (auto EC = MsfData.readBytes(Offset, BlockSize, BlockData))
+      return EC;
+
+    const uint8_t *ChunkStart = BlockData.data() + OffsetInBlock;
+    uint32_t BytesInChunk = std::min(BytesLeft, BlockSize - OffsetInBlock);
+    ::memcpy(WriteBuffer + BytesWritten, ChunkStart, BytesInChunk);
+
+    BytesWritten += BytesInChunk;
+    BytesLeft -= BytesInChunk;
+    ++BlockNum;
+    OffsetInBlock = 0;
+  }
+
+  return Error::success();
+}
+
+uint32_t MappedBlockStream::getNumBytesCopied() const {
+  return static_cast<uint32_t>(Pool.getBytesAllocated());
+}
+
+void MappedBlockStream::invalidateCache() { CacheMap.shrink_and_clear(); }
+
+void MappedBlockStream::fixCacheAfterWrite(uint32_t Offset,
+                                           ArrayRef<uint8_t> Data) const {
+  // If this write overlapped a read which previously came from the pool,
+  // someone may still be holding a pointer to that alloc which is now invalid.
+  // Compute the overlapping range and update the cache entry, so any
+  // outstanding buffers are automatically updated.
+  for (const auto &MapEntry : CacheMap) {
+    // If the end of the written extent precedes the beginning of the cached
+    // extent, ignore this map entry.
+    if (Offset + Data.size() < MapEntry.first)
+      continue;
+    for (const auto &Alloc : MapEntry.second) {
+      // If the end of the cached extent precedes the beginning of the written
+      // extent, ignore this alloc.
+      if (MapEntry.first + Alloc.size() < Offset)
+        continue;
+
+      // If we get here, they are guaranteed to overlap.
+      Interval WriteInterval = std::make_pair(Offset, Offset + Data.size());
+      Interval CachedInterval =
+          std::make_pair(MapEntry.first, MapEntry.first + Alloc.size());
+      // If they overlap, we need to write the new data into the overlapping
+      // range.
+      auto Intersection = intersect(WriteInterval, CachedInterval);
+      assert(Intersection.first <= Intersection.second);
+
+      uint32_t Length = Intersection.second - Intersection.first;
+      uint32_t SrcOffset =
+          AbsoluteDifference(WriteInterval.first, Intersection.first);
+      uint32_t DestOffset =
+          AbsoluteDifference(CachedInterval.first, Intersection.first);
+      ::memcpy(Alloc.data() + DestOffset, Data.data() + SrcOffset, Length);
+    }
+  }
+}
+
+WritableMappedBlockStream::WritableMappedBlockStream(
+    uint32_t BlockSize, uint32_t NumBlocks, const MsfStreamLayout &Layout,
+    const WritableStream &MsfData)
+    : ReadInterface(BlockSize, NumBlocks, Layout, MsfData),
+      WriteInterface(MsfData) {}
+
+std::unique_ptr<WritableMappedBlockStream>
+WritableMappedBlockStream::createStream(uint32_t BlockSize, uint32_t NumBlocks,
+                                        const MsfStreamLayout &Layout,
+                                        const WritableStream &MsfData) {
+  return llvm::make_unique<MappedBlockStreamImpl<WritableMappedBlockStream>>(
+      BlockSize, NumBlocks, Layout, MsfData);
+}
+
+std::unique_ptr<WritableMappedBlockStream>
+WritableMappedBlockStream::createIndexedStream(const MsfLayout &Layout,
+                                               const WritableStream &MsfData,
+                                               uint32_t StreamIndex) {
+  MsfStreamLayout SL;
+  SL.Blocks = Layout.StreamMap[StreamIndex];
+  SL.Length = Layout.StreamSizes[StreamIndex];
+  return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
+std::unique_ptr<WritableMappedBlockStream>
+WritableMappedBlockStream::createDirectoryStream(
+    const MsfLayout &Layout, const WritableStream &MsfData) {
+  MsfStreamLayout SL;
+  SL.Blocks = Layout.DirectoryBlocks;
+  SL.Length = Layout.SB->NumDirectoryBytes;
+  return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
+Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
+                                           ArrayRef<uint8_t> &Buffer) const {
+  return ReadInterface.readBytes(Offset, Size, Buffer);
+}
+
+Error WritableMappedBlockStream::readLongestContiguousChunk(
+    uint32_t Offset, ArrayRef<uint8_t> &Buffer) const {
+  return ReadInterface.readLongestContiguousChunk(Offset, Buffer);
+}
+
+uint32_t WritableMappedBlockStream::getLength() const {
+  return ReadInterface.getLength();
+}
+
+Error WritableMappedBlockStream::writeBytes(uint32_t Offset,
+                                            ArrayRef<uint8_t> Buffer) const {
+  // Make sure we aren't trying to write beyond the end of the stream.
+  if (Buffer.size() > getStreamLength())
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+
+  if (Offset > getStreamLayout().Length - Buffer.size())
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+
+  uint32_t BlockNum = Offset / getBlockSize();
+  uint32_t OffsetInBlock = Offset % getBlockSize();
+
+  uint32_t BytesLeft = Buffer.size();
+  uint32_t BytesWritten = 0;
+  while (BytesLeft > 0) {
+    uint32_t StreamBlockAddr = getStreamLayout().Blocks[BlockNum];
+    uint32_t BytesToWriteInChunk =
+        std::min(BytesLeft, getBlockSize() - OffsetInBlock);
+
+    const uint8_t *Chunk = Buffer.data() + BytesWritten;
+    ArrayRef<uint8_t> ChunkData(Chunk, BytesToWriteInChunk);
+    uint32_t MsfOffset = blockToOffset(StreamBlockAddr, getBlockSize());
+    MsfOffset += OffsetInBlock;
+    if (auto EC = WriteInterface.writeBytes(MsfOffset, ChunkData))
+      return EC;
+
+    BytesLeft -= BytesToWriteInChunk;
+    BytesWritten += BytesToWriteInChunk;
+    ++BlockNum;
+    OffsetInBlock = 0;
+  }
+
+  ReadInterface.fixCacheAfterWrite(Offset, Buffer);
+
+  return Error::success();
+}
+
+Error WritableMappedBlockStream::commit() const {
+  return WriteInterface.commit();
+}
diff --git a/llvm/lib/DebugInfo/Msf/MsfBuilder.cpp b/llvm/lib/DebugInfo/Msf/MsfBuilder.cpp
new file mode 100644
index 0000000..0128264
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/MsfBuilder.cpp
@@ -0,0 +1,279 @@
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/MsfBuilder.h"
+#include "llvm/DebugInfo/Msf/MsfError.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+using namespace llvm::support;
+
+namespace {
+const uint32_t kSuperBlockBlock = 0;
+const uint32_t kFreePageMap0Block = 1;
+const uint32_t kFreePageMap1Block = 2;
+const uint32_t kNumReservedPages = 3;
+
+const uint32_t kDefaultBlockMapAddr = kNumReservedPages;
+}
+
+MsfBuilder::MsfBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow,
+                       BumpPtrAllocator &Allocator)
+    : Allocator(Allocator), IsGrowable(CanGrow), BlockSize(BlockSize),
+      MininumBlocks(MinBlockCount), 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);
+  }
+
+  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;
+    FreeBlocks.resize(AllocBlocks + FreeBlocks.size(), true);
+  }
+
+  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]; }
+
+Error 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 Error::success();
+}
+
+Error 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 EC;
+  StreamData.push_back(std::make_pair(Size, NewBlocks));
+  return Error::success();
+}
+
+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::build() {
+  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.size() > 0) {
+    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());
+    }
+  }
+
+  return L;
+}
diff --git a/llvm/lib/DebugInfo/Msf/MsfCommon.cpp b/llvm/lib/DebugInfo/Msf/MsfCommon.cpp
new file mode 100644
index 0000000..e22087f
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/MsfCommon.cpp
@@ -0,0 +1,48 @@
+//===- MsfCommon.cpp - Common types and functions for MSF files -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/MsfCommon.h"
+#include "llvm/DebugInfo/Msf/MsfError.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+Error llvm::msf::validateSuperBlock(const SuperBlock &SB) {
+  // Check the magic bytes.
+  if (std::memcmp(SB.MagicBytes, Magic, sizeof(Magic)) != 0)
+    return make_error<MsfError>(msf_error_code::invalid_format,
+                                "MSF magic header doesn't match");
+
+  if (!isValidBlockSize(SB.BlockSize))
+    return make_error<MsfError>(msf_error_code::invalid_format,
+                                "Unsupported block size.");
+
+  // We don't support directories whose sizes aren't a multiple of four bytes.
+  if (SB.NumDirectoryBytes % sizeof(support::ulittle32_t) != 0)
+    return make_error<MsfError>(msf_error_code::invalid_format,
+                                "Directory size is not multiple of 4.");
+
+  // The number of blocks which comprise the directory is a simple function of
+  // the number of bytes it contains.
+  uint64_t NumDirectoryBlocks =
+      bytesToBlocks(SB.NumDirectoryBytes, SB.BlockSize);
+
+  // The directory, as we understand it, is a block which consists of a list of
+  // block numbers.  It is unclear what would happen if the number of blocks
+  // couldn't fit on a single block.
+  if (NumDirectoryBlocks > SB.BlockSize / sizeof(support::ulittle32_t))
+    return make_error<MsfError>(msf_error_code::invalid_format,
+                                "Too many directory blocks.");
+
+  if (SB.BlockMapAddr == 0)
+    return make_error<MsfError>(msf_error_code::invalid_format,
+                                "Block 0 is reserved");
+
+  return Error::success();
+}
diff --git a/llvm/lib/DebugInfo/Msf/MsfError.cpp b/llvm/lib/DebugInfo/Msf/MsfError.cpp
new file mode 100644
index 0000000..246beb9
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/MsfError.cpp
@@ -0,0 +1,70 @@
+//===- MsfError.cpp - Error extensions for Msf files ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/MsfError.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/ManagedStatic.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+namespace {
+// FIXME: This class is only here to support the transition to llvm::Error. It
+// will be removed once this transition is complete. Clients should prefer to
+// deal with the Error value directly, rather than converting to error_code.
+class MsfErrorCategory : public std::error_category {
+public:
+  const char *name() const LLVM_NOEXCEPT override { return "llvm.msf"; }
+
+  std::string message(int Condition) const override {
+    switch (static_cast<msf_error_code>(Condition)) {
+    case msf_error_code::unspecified:
+      return "An unknown error has occurred.";
+    case msf_error_code::insufficient_buffer:
+      return "The buffer is not large enough to read the requested number of "
+             "bytes.";
+    case msf_error_code::not_writable:
+      return "The specified stream is not writable.";
+    case msf_error_code::no_stream:
+      return "The specified stream does not exist.";
+    case msf_error_code::invalid_format:
+      return "The data is in an unexpected format.";
+    case msf_error_code::block_in_use:
+      return "The block is already in use.";
+    }
+    llvm_unreachable("Unrecognized msf_error_code");
+  }
+};
+} // end anonymous namespace
+
+static ManagedStatic<MsfErrorCategory> Category;
+
+char MsfError::ID = 0;
+
+MsfError::MsfError(msf_error_code C) : MsfError(C, "") {}
+
+MsfError::MsfError(const std::string &Context)
+    : MsfError(msf_error_code::unspecified, Context) {}
+
+MsfError::MsfError(msf_error_code C, const std::string &Context) : Code(C) {
+  ErrMsg = "Msf Error: ";
+  std::error_code EC = convertToErrorCode();
+  if (Code != msf_error_code::unspecified)
+    ErrMsg += EC.message() + "  ";
+  if (!Context.empty())
+    ErrMsg += Context;
+}
+
+void MsfError::log(raw_ostream &OS) const { OS << ErrMsg << "\n"; }
+
+const std::string &MsfError::getErrorMessage() const { return ErrMsg; }
+
+std::error_code MsfError::convertToErrorCode() const {
+  return std::error_code(static_cast<int>(Code), *Category);
+}
diff --git a/llvm/lib/DebugInfo/Msf/StreamReader.cpp b/llvm/lib/DebugInfo/Msf/StreamReader.cpp
new file mode 100644
index 0000000..1c7e835
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/StreamReader.cpp
@@ -0,0 +1,93 @@
+//===- StreamReader.cpp - Reads bytes and objects from a stream -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/StreamReader.h"
+
+#include "llvm/DebugInfo/Msf/MsfError.h"
+#include "llvm/DebugInfo/Msf/StreamRef.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+StreamReader::StreamReader(ReadableStreamRef S) : Stream(S), Offset(0) {}
+
+Error StreamReader::readLongestContiguousChunk(ArrayRef<uint8_t> &Buffer) {
+  if (auto EC = Stream.readLongestContiguousChunk(Offset, Buffer))
+    return EC;
+  Offset += Buffer.size();
+  return Error::success();
+}
+
+Error StreamReader::readBytes(ArrayRef<uint8_t> &Buffer, uint32_t Size) {
+  if (auto EC = Stream.readBytes(Offset, Size, Buffer))
+    return EC;
+  Offset += Size;
+  return Error::success();
+}
+
+Error StreamReader::readInteger(uint16_t &Dest) {
+  const support::ulittle16_t *P;
+  if (auto EC = readObject(P))
+    return EC;
+  Dest = *P;
+  return Error::success();
+}
+
+Error StreamReader::readInteger(uint32_t &Dest) {
+  const support::ulittle32_t *P;
+  if (auto EC = readObject(P))
+    return EC;
+  Dest = *P;
+  return Error::success();
+}
+
+Error StreamReader::readZeroString(StringRef &Dest) {
+  uint32_t Length = 0;
+  // First compute the length of the string by reading 1 byte at a time.
+  uint32_t OriginalOffset = getOffset();
+  const char *C;
+  do {
+    if (auto EC = readObject(C))
+      return EC;
+    if (*C != '\0')
+      ++Length;
+  } while (*C != '\0');
+  // Now go back and request a reference for that many bytes.
+  uint32_t NewOffset = getOffset();
+  setOffset(OriginalOffset);
+
+  ArrayRef<uint8_t> Data;
+  if (auto EC = readBytes(Data, Length))
+    return EC;
+  Dest = StringRef(reinterpret_cast<const char *>(Data.begin()), Data.size());
+
+  // Now set the offset back to where it was after we calculated the length.
+  setOffset(NewOffset);
+  return Error::success();
+}
+
+Error StreamReader::readFixedString(StringRef &Dest, uint32_t Length) {
+  ArrayRef<uint8_t> Bytes;
+  if (auto EC = readBytes(Bytes, Length))
+    return EC;
+  Dest = StringRef(reinterpret_cast<const char *>(Bytes.begin()), Bytes.size());
+  return Error::success();
+}
+
+Error StreamReader::readStreamRef(ReadableStreamRef &Ref) {
+  return readStreamRef(Ref, bytesRemaining());
+}
+
+Error StreamReader::readStreamRef(ReadableStreamRef &Ref, uint32_t Length) {
+  if (bytesRemaining() < Length)
+    return make_error<MsfError>(msf_error_code::insufficient_buffer);
+  Ref = Stream.slice(Offset, Length);
+  Offset += Length;
+  return Error::success();
+}
diff --git a/llvm/lib/DebugInfo/Msf/StreamWriter.cpp b/llvm/lib/DebugInfo/Msf/StreamWriter.cpp
new file mode 100644
index 0000000..40bc0394
--- /dev/null
+++ b/llvm/lib/DebugInfo/Msf/StreamWriter.cpp
@@ -0,0 +1,78 @@
+//===- StreamWrite.cpp - Writes bytes and objects to a stream -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/Msf/StreamWriter.h"
+
+#include "llvm/DebugInfo/Msf/MsfError.h"
+#include "llvm/DebugInfo/Msf/StreamReader.h"
+#include "llvm/DebugInfo/Msf/StreamRef.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+StreamWriter::StreamWriter(WritableStreamRef S) : Stream(S), Offset(0) {}
+
+Error StreamWriter::writeBytes(ArrayRef<uint8_t> Buffer) {
+  if (auto EC = Stream.writeBytes(Offset, Buffer))
+    return EC;
+  Offset += Buffer.size();
+  return Error::success();
+}
+
+Error StreamWriter::writeInteger(uint16_t Int) {
+  return writeObject(support::ulittle16_t(Int));
+}
+
+Error StreamWriter::writeInteger(uint32_t Int) {
+  return writeObject(support::ulittle32_t(Int));
+}
+
+Error StreamWriter::writeZeroString(StringRef Str) {
+  if (auto EC = writeFixedString(Str))
+    return EC;
+  if (auto EC = writeObject('\0'))
+    return EC;
+
+  return Error::success();
+}
+
+Error StreamWriter::writeFixedString(StringRef Str) {
+  ArrayRef<uint8_t> Bytes(Str.bytes_begin(), Str.bytes_end());
+  if (auto EC = Stream.writeBytes(Offset, Bytes))
+    return EC;
+
+  Offset += Str.size();
+  return Error::success();
+}
+
+Error StreamWriter::writeStreamRef(ReadableStreamRef Ref) {
+  if (auto EC = writeStreamRef(Ref, Ref.getLength()))
+    return EC;
+  // Don't increment Offset here, it is done by the overloaded call to
+  // writeStreamRef.
+  return Error::success();
+}
+
+Error StreamWriter::writeStreamRef(ReadableStreamRef Ref, uint32_t Length) {
+  Ref = Ref.slice(0, Length);
+
+  StreamReader SrcReader(Ref);
+  // This is a bit tricky.  If we just call readBytes, we are requiring that it
+  // return us the entire stream as a contiguous buffer.  For large streams this
+  // will allocate a huge amount of space from the pool.  Instead, iterate over
+  // each contiguous chunk until we've consumed the entire stream.
+  while (SrcReader.bytesRemaining() > 0) {
+    ArrayRef<uint8_t> Chunk;
+    if (auto EC = SrcReader.readLongestContiguousChunk(Chunk))
+      return EC;
+    if (auto EC = writeBytes(Chunk))
+      return EC;
+  }
+  return Error::success();
+}