[pdb] Introduce an MsfBuilder class for laying out PDB files

[zturner]

Summary

As we get further with writing PDB files, we run into the issue of needing to lay out the PDB file, generate a valid super block, and generate the directory and stream sizes array. Previously this was easy because we we were just reading in a PDB, and writing exactly the same directory and super block out. But now that we're trying to write only some of a particular stream, it means that the size of the stream we output is different from the size of the original stream. This in turn leads to different number of pages being used, which means a different stream directory, and possibly even the stream directory itself using a different number of blocks as before.

So we introduce an MsfBuilder class here. You create one, add a bunch of streams to it of the size you want, optionally giving it hints about what blocks you want a particular stream to occupy, and then it handles layout at the end. A bunch of unit tests are added to verify functionality.

I separated this out from a larger patch which actually updates the rest of the codebase to use this, and with my other patch I have confirmed that this class does produce a valid Msf layout.

[zturner]

Update some comments.

[amccarth]

Looks pretty good overall. I have a few suggestions/questions.

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

18

The inconsistent capitalization of initialisms seems unfortunate. PDB but Msf.

39

Some comments describing these members would be nice. I'd expect something like addStream to return something like an index or handle to refer to that new stream. What's the difference between the two versions (with and without Blocks)?

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

31

I think you meant "addresses" (plural).

109

Are pages and blocks the same thing? Maybe blocks are ranges of pages. It seems Idx is used for both stream indexes and page/block indexes.

144

I think this comment would be better in the header by the declaration of the method, as it explains the difference between the two addStreams, which users of the API care about.

The funny line break also makes me wonder if you left out some words.

222

"should was" ?

224

Is there a reason why you're specifying (global) ::memcpy rather than std::memcpy?

lib/DebugInfo/PDB/Raw/MsfCommon.cpp

19

::memcmp for consistency with ::memcpys you put elsewhere?

[zturner]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

39

There's two use cases I had in mind. One is you're building a PDB from scratch. You don't care what blocks a stream lies on, you just want the builder to figure it out. That's where you use the overload with no block list.

The other use case is you're editing a PDB. You load up one from disk, make some edits to it, and write it back out. This second use case is how I'm doing the Pdb <-> Yaml round-tripping, but it will be useful down the line when we want to integrate this into the linker. In this use case, you want to change the layout of the PDB as little as possible. If a stream used to take up blocks 10, 11, and 12, it should still *try* to take up blocks 10, 11, and 12. As long as you don't make any edits to the stream, that should still be possible. But if you remove a record or add a record, the stream extents could change.

When you call this overload, the builder does all of this. If it can use exactly the same set of blocks, it will. If you add data it will keep the blocks you specified but add some new ones. If you remove data it will keep the first N blocks you specified, but free up the other ones.

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

31

I actually meant address singular. The "block map address" is one 32-bit integer.

109

Yes

144

The funny line breaks happen when you clang-format a multi-line comment where one line went past 80 characters. I always miss a few when going over a CL after clang-formatting.

[amccarth]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

39

OK, great answer. A short version of that in the comments would probably help someone trying to figure out how to use this interface.

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

31

Ah, I read it as "super block address" and "block map address."

[ruiu]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

34

What's the use case of reset()? You can create as many instances of this class as you want, so wouldn't it be easier to make it a non-reusable class?

68

Which member contains streams' actual data?

Ahh, so this class is to constructs only the MSF header, and stream data is managed separately outside of this class. Is this correct? So it seems that you'd use this class to create a MSF directory, obtain a Layout object, and write each stream as the returned layout. Not sure how you would handle actual file writing, but this is probably just out of scope of this patch.

lib/DebugInfo/PDB/Raw/MsfCommon.cpp

23–38

These two tests seem to do basically the same thing. You can remove the former check.

unittests/DebugInfo/PDB/MsfBuilderTest.cpp

150

of of

[zturner]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

34

build() calls reset() after it's done to invalidate the entire structure so you have to start over. It would be nice if you could call build(), make one or two simple changes, then call build() again, but it's a little bit tricky for technical reasons, so for now I'm just having build() invalidate it.

68

Correct, this is only to generate in-memory objects that describe the layout of an MSF. I have some file writing in other patches but I didn't want to submit it all at once. But the short version is you create a PDBFileBuilder which will contain an MsfBuilder, then add streams to the MsfBuilder, then make some edits using the PDBFileBuilder (like setting fields from the individual streams to a different value).

Since my use case right now is editing a PDB (i.e. reading one in, making some changes, writing it back out), there's no code yet to generate one from scratch. But all the writing to disk and setting stream fields and serializing is working, so it should be easy to extend to generate a PDB from scratch.

[ruiu]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

34

I think what I was trying to say is to move the code from reset to the ctor if needed and remove the reset member function entirely. If a user wants to create two or more MSF headers, they can create multiple instances of MsfBuilder, so reset does not seem necessary.

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

27–28

I think this is a bit error-prone. Why don't you merge this with the ctor?

[zturner]

The reason I still kept reset is because without it, subsequent calls to
build will generate invalid layouts, which seemed unintuitive and error
prone. I can fix build() to support this, but it's kind of tricky. Even if
someone can create another builder they shouldn't be able to generate a bad
layout.

About initialize(), In earlier revisions this function could fail, so it
needed to return an Error. But I removed the ability for it to fail.
Although now that I think about it, I should probably validate the block
size.

[ruiu]

You can return an Error on second and subsequent calls of build(), no? I don't see a reason to allow users to call build() multiple times. If they want to create multiple MSF headers, they can simply create as many MsfBuilder instances they want, and call build() only once for each instance.

[zturner]

Yes I can have it return an error if it's already been called.

Calling it twice is useful for writing unit tests when you want to test
that 2 slightly different configurations differ in the expected way. But it
already doesn't work since it was difficult to do so in my current unit
tests i use 2 builders which are configured the same way except for one
thing.

In any case, having it return an Error on subsequent calls to build is
fine, I can do that

[ruiu]

By the way, did you figure out the format of the bitmap after the super block?

[zturner]

No, and this builder actually overwrites block 1 with the directory block
map by default. At some point we'll have to go through the ms code to try
to figure out block 1

[zturner]

Fix suggestions

[majnemer]

In D22308#483509, @zturner wrote:

No, and this builder actually overwrites block 1 with the directory block
map by default. At some point we'll have to go through the ms code to try
to figure out block 1

It's the free page map: https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L38

msf.cpp seems to contain much of the FPM manipulation code.

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

31–32

What do CanGrow and MinBlockCount mean?

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

26–27

Ditto.

[zturner]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

31–32

MinBlockCount means "assume I will have at least this many blocks in the PDB file". The reason this is useful is because when you want to modify an existing PDB, you want to keep the layout as stable as possible. So we will be calling addStream many times in succession and using the overload that takes a block list. But if you do this without specifying a MinBlockCount, then it will think you are trying to reference blocks that are outside the bounds of the entire file. For example, if you were to write this code:

msf.initialize(4096);
msf.addStream(29083, {7, 8, 9, 12, 14, 15, 16, 17});

addStream is going to complain that the file does not have space for that many blocks. It could try to help you out and grow the file automatically, and just say "well you asked for block 17, i'll just make sure there's at least enough blocks to be able to fit 17", but this seems awfully inefficient primarily because in the use case where you'll be doing this (i.e. you are reading in an existing PDB file), the super block already tells you exactly how many blocks the file has.

Even if we don't automatically grow the file here (and the current implementation doesn't), growing the file is still useful. If you want to create a new PDB from scratch, then you will use the overload of addStream() that does not take the block list, and in this case every single call to addStream() necessitates a grow.

Basically, CanGrow dictates what happens when the FreeBlocks bit vector has no entries. If it is true, we will resize the bit vector and make new blocks. If it is false, we return an error. We could actually get by without it and just always use behave as if CanGrow = true, but it seems useful as a way to prevent programming errors in cases where you know you are not adding any records or doing anything which should cause the PDB to get larger. I'm using false here for some unit tests, for example, because the test is intended to verify the internal block allocation behavior, and having it return an error if blocks are unexpectedly allocated is a useful diagnostic.

[majnemer]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

31–32

Can some of this get added to the header?

[zturner]

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

31–32

Sure

[ruiu]

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

28–29

So you don't like it, Zach?

[zturner]

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

28–29

You mean merging it with the constructor? The problem is that it's possible to pass an invalid block size, so I didn't want to make it possible to construct an instance of an MsfBuilder with an incorrect block size. If you use the constructor, there is no way to pass the error back to the user. I could make an enum for the block size, but I wasn't convinced that was better.

[ruiu]

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

28–29

You could make the ctor private and instead provide a static member function (say, create) which verifies all parameters and then call the constructor. In this way you can return an error or a new instance.

[zturner]

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

28–29

Ahh, yea actually that's not a bad idea. Thanks for the suggestion!

[zturner]

Make the constructor private and change Error initialize() to static Error create()

[ruiu]

LGTM

include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h

+//===- MSFBuilder.h - MSF Directory & Metadata Builder ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_PDB_RAW_MSFBUILDER_H
+#define LLVM_DEBUGINFO_PDB_RAW_MSFBUILDER_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+
+#include "llvm/DebugInfo/PDB/Raw/MsfCommon.h"
+#include "llvm/DebugInfo/PDB/Raw/PDBFile.h"
+
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/Error.h"
+
+#include <utility>
+#include <vector>
+
+namespace llvm {
+namespace pdb {
+class MsfBuilder {
+public:
+  explicit MsfBuilder(BumpPtrAllocator &Allocator);
+  Error initialize(uint32_t BlockSize, uint32_t MinBlockCount = 0,
+                   bool CanGrow = true);
+
+  /// Request the block map to be at a specific block address.  This is useful
+  /// when editing a PDB and you want the layout to be as stable as possible.
+  Error setBlockMapAddr(uint32_t Addr);
+
+  /// Add a stream to the MSF file with the given size, occupying the given
+  /// list of blocks.  This is useful when reading a PDB file and you want a
+  /// particular stream to occupy the original set of blocks.  If the given
+  /// blocks are already allocated, or if the number of blocks specified is
+  /// incorrect for the given stream size, this function will return an Error.
+  Error addStream(uint32_t Size, ArrayRef<uint32_t> Blocks);
+
+  /// Add a stream to the MSF file with the given size, occupying any available
+  /// blocks that the builder decides to use.  This is useful when building a
+  /// new PDB file from scratch and you don't care what blocks a stream occupies
+  /// but you just want it to work.
+  Error addStream(uint32_t Size);
+
+  /// Update the size of an existing stream.  This will allocate or deallocate
+  /// blocks as needed to match the requested size.  This can fail if `CanGrow`
+  /// was set to false when initializing the `MsfBuilder`.
+  Error setStreamSize(uint32_t Idx, uint32_t Size);
+
+  /// Get the total number of streams in the MSF layout.  This should return 1
+  /// for every call to `addStream`.
+  uint32_t getNumStreams() const;
+
+  /// Get the size of a stream by index.
+  uint32_t getStreamSize(uint32_t StreamIdx) const;
+
+  /// Get the list of blocks allocated to a particular stream.
+  ArrayRef<uint32_t> getStreamBlocks(uint32_t StreamIdx) const;
+
+  /// Get the total number of blocks that will be allocated to actual data in
+  /// this MSF file.
+  uint32_t getNumUsedBlocks() const;
+
+  /// Get the total number of blocks that exist in the MSF file but are not
+  /// allocated to any valid data.
+  uint32_t getNumFreeBlocks() const;
+
+  /// Get the total number of blocks in the MSF file.  In practice this is equal
+  /// to `getNumUsedBlocks() + getNumFreeBlocks()`.
+  uint32_t getTotalBlockCount() const;
+
+  /// Check whether a particular block is allocated or free.
+  bool isBlockFree(uint32_t Idx) const;
+
+  /// Finalize the layout and build the headers and structures that describe the
+  /// MSF layout and can be written directly to the MSF file.
+  Expected<msf::Layout> build();
+
+private:
+  Error allocateBlocks(uint32_t NumBlocks, MutableArrayRef<uint32_t> Blocks);
+  uint32_t computeDirectoryByteSize() const;
+
+  typedef std::vector<uint32_t> BlockList;
+
+  BumpPtrAllocator &Allocator;
+
+  bool IsInitialized = false;
+  bool IsGrowable = false;
+  uint32_t BlockSize = 0;
+  uint32_t MininumBlocks = 0;
+  uint32_t BlockMapAddr;
+  std::vector<uint32_t> DirectoryBlocks;
+  BitVector FreeBlocks;
+  std::vector<std::pair<uint32_t, BlockList>> StreamData;
+};
+}
+}
+
+#endif

include/llvm/DebugInfo/PDB/Raw/MsfCommon.h

+//===- MsfCommon.h - 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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEBUGINFO_PDB_RAW_MSFCOMMON_H
+#define LLVM_DEBUGINFO_PDB_RAW_MSFCOMMON_H
+
+#include "llvm/ADT/ArrayRef.h"
+
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MathExtras.h"
+
+#include <vector>
+
+namespace llvm {
+namespace pdb {
+namespace msf {
+static const char Magic[] = {'M',  'i',  'c',    'r', 'o', 's',  'o',  'f',
+                             't',  ' ',  'C',    '/', 'C', '+',  '+',  ' ',
+                             'M',  'S',  'F',    ' ', '7', '.',  '0',  '0',
+                             '\r', '\n', '\x1a', 'D', 'S', '\0', '\0', '\0'};
+
+// The superblock is overlaid at the beginning of the file (offset 0).
+// It starts with a magic header and is followed by information which
+// describes the layout of the file system.
+struct SuperBlock {
+  char MagicBytes[sizeof(Magic)];
+  // The file system is split into a variable number of fixed size elements.
+  // These elements are referred to as blocks.  The size of a block may vary
+  // from system to system.
+  support::ulittle32_t BlockSize;
+  // This field's purpose is not yet known.
+  support::ulittle32_t Unknown0;
+  // This contains the number of blocks resident in the file system.  In
+  // practice, NumBlocks * BlockSize is equivalent to the size of the PDB
+  // file.
+  support::ulittle32_t NumBlocks;
+  // This contains the number of bytes which make up the directory.
+  support::ulittle32_t NumDirectoryBytes;
+  // This field's purpose is not yet known.
+  support::ulittle32_t Unknown1;
+  // This contains the block # of the block map.
+  support::ulittle32_t BlockMapAddr;
+};
+
+struct Layout {
+  SuperBlock *SB;
+  ArrayRef<support::ulittle32_t> DirectoryBlocks;
+  ArrayRef<support::ulittle32_t> StreamSizes;
+  std::vector<ArrayRef<support::ulittle32_t>> StreamMap;
+};
+
+inline bool isValidBlockSize(uint32_t Size) {
+  switch (Size) {
+  case 512:
+  case 1024:
+  case 2048:
+  case 4096:
+    return true;
+  }
+  return false;
+}
+
+inline uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize) {
+  return alignTo(NumBytes, BlockSize) / BlockSize;
+}
+
+inline uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize) {
+  return BlockNumber * BlockSize;
+}
+
+Error validateSuperBlock(const SuperBlock &SB);
+}
+}
+}
+
+#endif

lib/DebugInfo/PDB/CMakeLists.txt

   Raw/MappedBlockStream.cpp
   Raw/ModInfo.cpp
   Raw/ModStream.cpp
+  Raw/MsfBuilder.cpp
+  Raw/MsfCommon.cpp
   Raw/NameHashTable.cpp
   Raw/NameMap.cpp
   Raw/PDBFile.cpp

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

+//===- MSFBuilder.cpp - MSF Directory & Metadata Builder --------*- 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/PDB/Raw/MsfBuilder.h"
+#include "llvm/DebugInfo/PDB/Raw/RawError.h"
+
+using namespace llvm;
+using namespace llvm::pdb;
+using namespace llvm::pdb::msf;
+using namespace llvm::support;
+
+namespace {
+const uint32_t kSuperBlockBlock = 0;
+const uint32_t kDefaultBlockMapAddr = 1;
+}
+
+MsfBuilder::MsfBuilder(BumpPtrAllocator &Allocator)
+    : Allocator(Allocator), BlockMapAddr(kDefaultBlockMapAddr) {}
+
+Error MsfBuilder::initialize(uint32_t BlockSize, uint32_t MinBlockCount,
+                             bool CanGrow) {
+  assert(!IsInitialized && "MsfBuilder is already initialized!");
+
+  if (!msf::isValidBlockSize(BlockSize))
+    return make_error<RawError>(raw_error_code::unspecified,
+                                "The requested block size is unsupported");
+
+  // The super block and block map address are not counted
+  this->BlockSize = BlockSize;
+  IsInitialized = true;
+  IsGrowable = CanGrow;
+  MininumBlocks = MinBlockCount + 2U;
+
+  FreeBlocks = BitVector(MininumBlocks, true);
+  FreeBlocks[kSuperBlockBlock] = false;
+  FreeBlocks[BlockMapAddr] = false;
+  StreamData.clear();
+  BlockMapAddr = kDefaultBlockMapAddr;
+  DirectoryBlocks.clear();
+  return Error::success();
+}
+
+Error MsfBuilder::setBlockMapAddr(uint32_t Addr) {
+  if (Addr == BlockMapAddr)
+    return Error::success();
+
+  if (Addr >= FreeBlocks.size()) {
+    if (!IsGrowable)
+      return make_error<RawError>(raw_error_code::unspecified,
+                                  "Cannot grow the number of blocks");
+    FreeBlocks.resize(Addr + 1);
+  }
+
+  if (!isBlockFree(Addr))
+    return make_error<RawError>(raw_error_code::unspecified,
+                                "Attempt to reuse an allocated block");
+  FreeBlocks[BlockMapAddr] = true;
+  FreeBlocks[Addr] = false;
+  BlockMapAddr = Addr;
+  return Error::success();
+}
+
+Error MsfBuilder::allocateBlocks(uint32_t NumBlocks,
+                                 MutableArrayRef<uint32_t> Blocks) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  if (NumBlocks == 0)
+    return Error::success();
+
+  uint32_t NumFreeBlocks = FreeBlocks.count();
+  if (NumFreeBlocks < NumBlocks) {
+    if (!IsGrowable)
+      return make_error<RawError>(raw_error_code::unspecified,
+                                  "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) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  // 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<RawError>(
+        raw_error_code::unspecified,
+        "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<RawError>(
+          raw_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) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  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) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  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<Layout> MsfBuilder::build() {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  Layout L;
+  L.SB = Allocator.Allocate<SuperBlock>();
+  std::memcpy(L.SB->MagicBytes, Magic, sizeof(Magic));
+  L.SB->BlockMapAddr = BlockMapAddr;
+  L.SB->BlockSize = BlockSize;
+  L.SB->NumDirectoryBytes = computeDirectoryByteSize();
+  L.SB->Unknown0 = 0;
+  L.SB->Unknown1 = 0;
+
+  uint32_t NumDirectoryBlocks =
+      bytesToBlocks(L.SB->NumDirectoryBytes, BlockSize);
+  // The directory blocks should be re-allocated as a stable pointer.
+  std::vector<uint32_t> DirectoryBlocks;
+  DirectoryBlocks.resize(NumDirectoryBlocks);
+  if (auto EC = allocateBlocks(NumDirectoryBlocks, DirectoryBlocks))
+    return std::move(EC);
+
+  // 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.
+  L.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());
+    }
+  }
+
+  IsInitialized = false;
+  return L;
+}

lib/DebugInfo/PDB/Raw/MsfCommon.cpp

+//===- 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/PDB/Raw/MsfCommon.h"
+#include "llvm/DebugInfo/PDB/Raw/RawError.h"
+
+using namespace llvm;
+using namespace llvm::pdb::msf;
+
+Error llvm::pdb::msf::validateSuperBlock(const SuperBlock &SB) {
+  // Check the magic bytes.
+  if (std::memcmp(SB.MagicBytes, Magic, sizeof(Magic)) != 0)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "MSF magic header doesn't match");
+
+  if (!isValidBlockSize(SB.BlockSize))
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "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<RawError>(raw_error_code::corrupt_file,
+                                "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<RawError>(raw_error_code::corrupt_file,
+                                "Too many directory blocks.");
+
+  if (SB.BlockMapAddr == 0)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Block 0 is reserved");
+
+  return Error::success();
+}

unittests/DebugInfo/PDB/CMakeLists.txt

 
 set(DebugInfoPDBSources
   MappedBlockStreamTest.cpp
+  MsfBuilderTest.cpp
   PDBApiTest.cpp
   )
 

unittests/DebugInfo/PDB/ErrorChecking.h

+//===- ErrorChecking.h - Helpers for verifying llvm::Errors -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_DEBUGINFO_PDB_ERRORCHECKING_H
+#define LLVM_UNITTESTS_DEBUGINFO_PDB_ERRORCHECKING_H
+
+#define EXPECT_NO_ERROR(Err)                                                   \
+  {                                                                            \
+    auto E = Err;                                                              \
+    EXPECT_FALSE(static_cast<bool>(E));                                        \
+    if (E)                                                                     \
+      consumeError(std::move(E));                                              \
+  }
+
+#define EXPECT_ERROR(Err)                                                      \
+  {                                                                            \
+    auto E = Err;                                                              \
+    EXPECT_TRUE(static_cast<bool>(E));                                         \
+    if (E)                                                                     \
+      consumeError(std::move(E));                                              \
+  }
+
+#define EXPECT_EXPECTED(Exp)                                                   \
+  {                                                                            \
+    auto E = Exp.takeError();                                                  \
+    EXPECT_FALSE(static_cast<bool>(E));                                        \
+    if (E) {                                                                   \
+      consumeError(std::move(E));                                              \
+      return;                                                                  \
+    }                                                                          \
+  }
+
+#define EXPECT_UNEXPECTED(Exp) EXPECT_ERROR(Err)
+
+#endif

unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp

 //
 //===----------------------------------------------------------------------===//
 
-#include <unordered_map>
+#include "ErrorChecking.h"
 
 #include "llvm/DebugInfo/CodeView/ByteStream.h"
 #include "llvm/DebugInfo/CodeView/StreamReader.h"

 #include "llvm/DebugInfo/PDB/Raw/MappedBlockStream.h"
 #include "gtest/gtest.h"
 
+#include <unordered_map>
+
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace llvm::pdb;
 
 namespace {
 
-#define EXPECT_NO_ERROR(Err)                                                   \
-  {                                                                            \
-    auto E = Err;                                                              \
-    EXPECT_FALSE(static_cast<bool>(E));                                        \
-    if (E)                                                                     \
-      consumeError(std::move(E));                                              \
-  }
-
-#define EXPECT_ERROR(Err)                                                      \
-  {                                                                            \
-    auto E = Err;                                                              \
-    EXPECT_TRUE(static_cast<bool>(E));                                         \
-    if (E)                                                                     \
-      consumeError(std::move(E));                                              \
-  }
-
 static const uint32_t BlocksAry[] = {0, 1, 2, 5, 4, 3, 6, 7, 8, 9};
 static uint8_t DataAry[] = {'A', 'B', 'C', 'F', 'E', 'D', 'G', 'H', 'I', 'J'};
 

unittests/DebugInfo/PDB/MsfBuilderTest.cpp

+//===- MsfBuilderTest.cpp  Tests manipulation of MSF stream metadata ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ErrorChecking.h"
+
+#include "llvm/DebugInfo/PDB/Raw/MsfBuilder.h"
+#include "llvm/DebugInfo/PDB/Raw/MsfCommon.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::pdb;
+using namespace llvm::pdb::msf;
+
+namespace {
+class MsfBuilderTest : public testing::Test {
+protected:
+  void initializeSimpleSuperBlock(msf::SuperBlock &SB) {
+    initializeSuperBlock(SB);
+    SB.NumBlocks = 1000;
+    SB.NumDirectoryBytes = 8192;
+  }
+
+  void initializeSuperBlock(msf::SuperBlock &SB) {
+    ::memset(&SB, 0, sizeof(SB));
+
+    ::memcpy(SB.MagicBytes, msf::Magic, sizeof(msf::Magic));
+    SB.BlockMapAddr = 1;
+    SB.BlockSize = 4096;
+    SB.NumDirectoryBytes = 0;
+    SB.NumBlocks = 2; // one for the Super Block, one for the directory
+  }
+
+  BumpPtrAllocator Allocator;
+};
+}
+
+TEST_F(MsfBuilderTest, ValidateSuperBlockAccept) {
+  // Test that a known good super block passes validation.
+  SuperBlock SB;
+  initializeSuperBlock(SB);
+
+  EXPECT_NO_ERROR(msf::validateSuperBlock(SB));
+}
+
+TEST_F(MsfBuilderTest, ValidateSuperBlockReject) {
+  // Test that various known problems cause a super block to be rejected.
+  SuperBlock SB;
+  initializeSimpleSuperBlock(SB);
+
+  // Mismatched magic
+  SB.MagicBytes[0] = 8;
+  EXPECT_ERROR(msf::validateSuperBlock(SB));
+  initializeSimpleSuperBlock(SB);
+
+  // Block 0 is reserved for super block, can't be occupied by the block map
+  SB.BlockMapAddr = 0;
+  EXPECT_ERROR(msf::validateSuperBlock(SB));
+  initializeSimpleSuperBlock(SB);
+
+  // Block sizes have to be powers of 2.
+  SB.BlockSize = 3120;
+  EXPECT_ERROR(msf::validateSuperBlock(SB));
+  initializeSimpleSuperBlock(SB);
+
+  // The directory itself has a maximum size.
+  SB.NumDirectoryBytes = SB.BlockSize * SB.BlockSize / 4;
+  EXPECT_NO_ERROR(msf::validateSuperBlock(SB));
+  SB.NumDirectoryBytes = SB.NumDirectoryBytes + 4;
+  EXPECT_ERROR(msf::validateSuperBlock(SB));
+}
+
+TEST_F(MsfBuilderTest, TestUsedBlocksMarkedAsUsed) {
+  // Test that when assigning a stream to a known list of blocks, the blocks
+  // are correctly marked as used after adding, but no other incorrect blocks
+  // are accidentally marked as used.
+  MsfBuilder Msf(Allocator);
+
+  std::vector<uint32_t> Blocks = {2, 3, 4, 5, 6, 7, 8, 9, 10};
+  // Allocate some extra blocks at the end so we can verify that they're free
+  // after the initialization.
+  EXPECT_NO_ERROR(Msf.initialize(4096, Blocks.size() + 10));
+
+  EXPECT_NO_ERROR(Msf.addStream(Blocks.size() * 4096, Blocks));
+
+  for (auto B : Blocks) {
+    EXPECT_FALSE(Msf.isBlockFree(B));
+  }
+  for (int I = 11; I < 21; ++I) {
+    EXPECT_TRUE(Msf.isBlockFree(I));
+  }
+}
+
+TEST_F(MsfBuilderTest, TestAddStreamNoDirectoryBlockIncrease) {
+  // Test that adding a new stream correctly updates the directory.  This only
+  // tests the case where the directory *DOES NOT* grow large enough that it
+  // crosses a Block boundary.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  auto ExpectedL1 = Msf.build();
+  EXPECT_EXPECTED(ExpectedL1);
+  Layout &L1 = *ExpectedL1;
+
+  auto OldDirBlocks = L1.DirectoryBlocks;
+  EXPECT_EQ(1, OldDirBlocks.size());
+
+  MsfBuilder Msf2(Allocator);
+  EXPECT_NO_ERROR(Msf2.initialize(4096));
+  EXPECT_NO_ERROR(Msf2.addStream(4000));
+  EXPECT_EQ(1, Msf2.getNumStreams());
+  EXPECT_EQ(4000, Msf2.getStreamSize(0));
+  auto Blocks = Msf2.getStreamBlocks(0);
+  EXPECT_EQ(1, Blocks.size());
+
+  auto ExpectedL2 = Msf2.build();
+  EXPECT_EXPECTED(ExpectedL2);
+  Layout &L2 = *ExpectedL2;
+  auto NewDirBlocks = L2.DirectoryBlocks;
+  EXPECT_EQ(1, NewDirBlocks.size());
+}
+
+TEST_F(MsfBuilderTest, TestAddStreamWithDirectoryBlockIncrease) {
+  // Test that adding a new stream correctly updates the directory.  This only
+  // tests the case where the directory *DOES* grow large enough that it
+  // crosses a Block boundary.  This is because the newly added stream occupies
+  // so many Blocks that need to be indexed in the directory that the directory
+  // crosses a Block boundary.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  EXPECT_NO_ERROR(Msf.addStream(4096 * 4096 / sizeof(uint32_t)));
+
+  auto ExpectedL1 = Msf.build();
+  EXPECT_EXPECTED(ExpectedL1);
+  Layout &L1 = *ExpectedL1;
+  auto DirBlocks = L1.DirectoryBlocks;
+  EXPECT_EQ(2, DirBlocks.size());
+}
+
+TEST_F(MsfBuilderTest, TestGrowStreamNoBlockIncrease) {
+  // Test growing an existing stream by a value that does not affect the number
+  // of blocks it occupies.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  EXPECT_NO_ERROR(Msf.addStream(1024));
+  EXPECT_EQ(Msf.getStreamSize(0), 1024);
+  auto OldStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, OldStreamBlocks.size());
+
+  EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048));
+  EXPECT_EQ(Msf.getStreamSize(0), 2048);
+  auto NewStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, NewStreamBlocks.size());
+
+  EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
+}
+
+TEST_F(MsfBuilderTest, TestGrowStreamWithBlockIncrease) {
+  // Test that growing an existing stream to a value large enough that it causes
+  // the need to allocate new Blocks to the stream correctly updates the
+  // stream's
+  // block list.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  EXPECT_NO_ERROR(Msf.addStream(2048));
+  EXPECT_EQ(Msf.getStreamSize(0), 2048);
+  std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, OldStreamBlocks.size());
+
+  EXPECT_NO_ERROR(Msf.setStreamSize(0, 6144));
+  EXPECT_EQ(Msf.getStreamSize(0), 6144);
+  std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(2, NewStreamBlocks.size());
+
+  EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
+  EXPECT_NE(NewStreamBlocks[0], NewStreamBlocks[1]);
+}
+
+TEST_F(MsfBuilderTest, TestShrinkStreamNoBlockDecrease) {
+  // Test that shrinking an existing stream by a value that does not affect the
+  // number of Blocks it occupies makes no changes to stream's block list.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  EXPECT_NO_ERROR(Msf.addStream(2048));
+  EXPECT_EQ(Msf.getStreamSize(0), 2048);
+  std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, OldStreamBlocks.size());
+
+  EXPECT_NO_ERROR(Msf.setStreamSize(0, 1024));
+  EXPECT_EQ(Msf.getStreamSize(0), 1024);
+  std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, NewStreamBlocks.size());
+
+  EXPECT_EQ(OldStreamBlocks, NewStreamBlocks);
+}
+
+TEST_F(MsfBuilderTest, TestShrinkStreamWithBlockDecrease) {
+  // Test that shrinking an existing stream to a value large enough that it
+  // causes the need to deallocate new Blocks to the stream correctly updates
+  // the stream's block list.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+
+  EXPECT_NO_ERROR(Msf.addStream(6144));
+  EXPECT_EQ(Msf.getStreamSize(0), 6144);
+  std::vector<uint32_t> OldStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(2, OldStreamBlocks.size());
+
+  EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048));
+  EXPECT_EQ(Msf.getStreamSize(0), 2048);
+  std::vector<uint32_t> NewStreamBlocks = Msf.getStreamBlocks(0);
+  EXPECT_EQ(1, NewStreamBlocks.size());
+
+  EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]);
+}
+
+TEST_F(MsfBuilderTest, TestRejectReusedStreamBlock) {
+  // Test that attempting to add a stream and assigning a block that is already
+  // in use by another stream fails.
+  MsfBuilder Msf(Allocator);
+
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  EXPECT_NO_ERROR(Msf.addStream(6144));
+
+  std::vector<uint32_t> Blocks = {2, 3};
+  EXPECT_ERROR(Msf.addStream(6144, Blocks));
+}
+
+TEST_F(MsfBuilderTest, TestBlockCountsWhenAddingStreams) {
+  // Test that when adding multiple streams, the number of used and free Blocks
+  // allocated to the MSF file are as expected.
+  MsfBuilder Msf(Allocator);
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+
+  // one for the super block, one for the directory block map
+  uint32_t NumUsedBlocks = Msf.getNumUsedBlocks();
+  EXPECT_EQ(2, NumUsedBlocks);
+  EXPECT_EQ(0, Msf.getNumFreeBlocks());
+
+  const uint32_t StreamSizes[] = {4000, 6193, 189723};
+  for (int I = 0; I < 3; ++I) {
+    EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I]));
+    NumUsedBlocks += bytesToBlocks(StreamSizes[I], 4096);
+    EXPECT_EQ(NumUsedBlocks, Msf.getNumUsedBlocks());
+    EXPECT_EQ(0, Msf.getNumFreeBlocks());
+  }
+}
+
+TEST_F(MsfBuilderTest, TestBuildMsfLayout) {
+  // Test that we can generate an Msf Layout structure from a valid layout
+  // specification.
+  MsfBuilder Msf(Allocator);
+  EXPECT_NO_ERROR(Msf.initialize(4096));
+  const uint32_t StreamSizes[] = {4000, 6193, 189723};
+  uint32_t ExpectedNumBlocks = 2;
+  for (int I = 0; I < 3; ++I) {
+    EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I]));
+    ExpectedNumBlocks += bytesToBlocks(StreamSizes[I], 4096);
+  }
+  ++ExpectedNumBlocks; // The directory itself should use 1 block
+
+  auto ExpectedLayout = Msf.build();
+  EXPECT_EXPECTED(ExpectedLayout);
+  Layout &L = *ExpectedLayout;
+  EXPECT_EQ(4096, L.SB->BlockSize);
+  EXPECT_EQ(ExpectedNumBlocks, L.SB->NumBlocks);
+
+  EXPECT_EQ(1, L.DirectoryBlocks.size());
+
+  EXPECT_EQ(3, L.StreamMap.size());
+  EXPECT_EQ(3, L.StreamSizes.size());
+  for (int I = 0; I < 3; ++I) {
+    EXPECT_EQ(StreamSizes[I], L.StreamSizes[I]);
+    uint32_t ExpectedNumBlocks = bytesToBlocks(StreamSizes[I], 4096);
+    EXPECT_EQ(ExpectedNumBlocks, L.StreamMap[I].size());
+  }
+}