[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

32–33

What do CanGrow and MinBlockCount mean?

lib/DebugInfo/PDB/Raw/MsfBuilder.cpp

27–28

Ditto.

[zturner]

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

32–33

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

32–33

Can some of this get added to the header?

[zturner]

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

32–33

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);
+  void initialize(uint32_t PageSize, uint32_t MinPageCount = 0,
+                  bool CanGrow = true);
+  void reset();
+
+  Error setBlockMapAddr(uint32_t Addr);
+
+  Error addStream(uint32_t Size, ArrayRef<uint32_t> Blocks);
+  Error addStream(uint32_t Size);
+  Error setStreamSize(uint32_t Idx, uint32_t Size);
+
+  uint32_t getNumStreams() const;
+  uint32_t getStreamSize(uint32_t StreamIdx) const;
+  ArrayRef<uint32_t> getStreamBlocks(uint32_t StreamIdx) const;
+
+  uint32_t getNumUsedPages() const;
+  uint32_t getNumFreePages() const;
+  uint32_t getTotalPageCount() const;
+  bool isPageFree(uint32_t Idx) const;
+
+  Expected<msf::Layout> build();
+
+private:
+  Error allocatePages(uint32_t NumPages, MutableArrayRef<uint32_t> Pages);
+  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 FreePages;
+  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 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 kSuperBlockPage = 0;
+const uint32_t kDefaultBlockMapAddr = 1;
+}
+
+MsfBuilder::MsfBuilder(BumpPtrAllocator &Allocator)
+    : Allocator(Allocator), BlockMapAddr(kDefaultBlockMapAddr) {}
+
+void MsfBuilder::initialize(uint32_t PageSize, uint32_t MinPageCount,
+                            bool CanGrow) {
+  assert(!IsInitialized && "MsfBuilder is already initialized!");
+
+  // The super block and block map address are not counted
+  BlockSize = PageSize;
+  IsInitialized = true;
+  IsGrowable = CanGrow;
+  MininumBlocks = MinPageCount + 2U;
+
+  FreePages = BitVector(MininumBlocks, true);
+  FreePages[kSuperBlockPage] = false;
+  FreePages[BlockMapAddr] = false;
+}
+
+Error MsfBuilder::setBlockMapAddr(uint32_t Addr) {
+  if (Addr == BlockMapAddr)
+    return Error::success();
+
+  if (Addr >= FreePages.size()) {
+    if (!IsGrowable)
+      return make_error<RawError>(raw_error_code::unspecified,
+                                  "Cannot grow the number of blocks");
+    FreePages.resize(Addr + 1);
+  }
+
+  if (!isPageFree(Addr))
+    return make_error<RawError>(raw_error_code::unspecified,
+                                "Attempt to reuse an allocated block");
+  FreePages[BlockMapAddr] = true;
+  FreePages[Addr] = false;
+  BlockMapAddr = Addr;
+  return Error::success();
+}
+
+void MsfBuilder::reset() {
+  FreePages = BitVector();
+  BlockSize = 0;
+  MininumBlocks = 0;
+  IsGrowable = false;
+  IsInitialized = false;
+  BlockMapAddr = kDefaultBlockMapAddr;
+  StreamData.clear();
+}
+
+Error MsfBuilder::allocatePages(uint32_t NumPages,
+                                MutableArrayRef<uint32_t> Pages) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  if (NumPages == 0)
+    return Error::success();
+
+  uint32_t NumFreePages = FreePages.count();
+  if (NumFreePages < NumPages) {
+    if (!IsGrowable)
+      return make_error<RawError>(raw_error_code::unspecified,
+                                  "There are no free pages in the file");
+    uint32_t AllocPages = NumPages - NumFreePages;
+    FreePages.resize(AllocPages + FreePages.size(), true);
+  }
+
+  int I = 0;
+  int Page = FreePages.find_first();
+  do {
+    assert(Page != -1 && "We ran out of pages!");
+
+    uint32_t NextPage = static_cast<uint32_t>(Page);
+    Pages[I++] = NextPage;
+    FreePages.reset(NextPage);
+    Page = FreePages.find_next(Page);
+  } while (--NumPages > 0);
+  return Error::success();
+}
+
+uint32_t MsfBuilder::getNumUsedPages() const {
+  return getTotalPageCount() - getNumFreePages();
+}
+
+uint32_t MsfBuilder::getNumFreePages() const { return FreePages.count(); }
+
+uint32_t MsfBuilder::getTotalPageCount() const { return FreePages.size(); }
+
+bool MsfBuilder::isPageFree(uint32_t Idx) const { return FreePages[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 >= FreePages.size())
+      FreePages.resize(Block + 1, true);
+
+    if (!FreePages.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) {
+    FreePages.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!");
+
+  // Add a new stream of the specified size, but determine the blocks to map the
+  // stream to
+  // automatically.
+  uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize);
+  std::vector<uint32_t> NewPages;
+  NewPages.resize(ReqBlocks);
+  if (auto EC = allocatePages(ReqBlocks, NewPages))
+    return EC;
+  StreamData.push_back(std::make_pair(Size, NewPages));
+  return Error::success();
+}
+
+Error MsfBuilder::setStreamSize(uint32_t Idx, uint32_t Size) {
+  assert(IsInitialized && "Must call MsfBuilder::initialize!");
+
+  // If the size is the same, just return.  Otherwise we may need to shrink or
+  // grow the stream
+  // which could necessitate shrinking or growing the directory as well.
+  uint32_t OldSize = getStreamSize(Idx);
+  if (OldSize == Size)
+    return Error::success();
+
+  uint32_t NewPages = bytesToBlocks(Size, BlockSize);
+  uint32_t OldPages = bytesToBlocks(OldSize, BlockSize);
+
+  if (NewPages > OldPages) {
+    uint32_t AddedPages = NewPages - OldPages;
+    // If we're growing, we have to allocate new pages.
+    std::vector<uint32_t> AddedPageList;
+    AddedPageList.resize(AddedPages);
+    if (auto EC = allocatePages(AddedPages, AddedPageList))
+      return EC;
+    auto &CurrentPages = StreamData[Idx].second;
+    CurrentPages.insert(CurrentPages.end(), AddedPageList.begin(),
+                        AddedPageList.end());
+  } else if (OldPages > NewPages) {
+    // For shrinking, free all the pages in the page map, update the stream
+    // data, then shrink the directory.
+    uint32_t RemovedPages = OldPages - NewPages;
+    auto CurrentPages = ArrayRef<uint32_t>(StreamData[Idx].second);
+    auto RemovedPageList = CurrentPages.drop_front(NewPages);
+    for (auto P : RemovedPageList)
+      FreePages[P] = true;
+    StreamData[Idx].second = CurrentPages.drop_back(RemovedPages);
+  }
+
+  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;
+  // The super block should was already allocated, just set it.
+  L.SB = Allocator.Allocate<SuperBlock>();
+  ::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 = allocatePages(NumDirectoryBlocks, DirectoryBlocks))
+    return std::move(EC);
+
+  // Don't set the number of blocks in the file until after allocating pages for
+  // the directory, since the allocation might cause the file to need to grow.
+  L.SB->NumBlocks = FreePages.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());
+    }
+  }
+
+  reset();
+  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 (memcmp(SB.MagicBytes, Magic, sizeof(Magic)) != 0)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "MSF magic header doesn't match");
+
+  // We don't support blocksizes which aren't a multiple of four bytes.
+  if (SB.BlockSize % sizeof(support::ulittle32_t) != 0)
+    return make_error<RawError>(raw_error_code::corrupt_file,
+                                "Block size is not multiple of 4.");
+
+  switch (SB.BlockSize) {
+  case 512:
+  case 1024:
+  case 2048:
+  case 4096:
+    break;
+  default:
+    // An invalid block size suggests a corrupt PDB file.
+    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 a multiple of 4.
+  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 initializing an MsfBuilder with a list of directory blocks
+  // that the directory blocks are marked as used, but the other blocks are
+  // still marked as free.
+  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.
+  Msf.initialize(4096, Blocks.size() + 10);
+
+  EXPECT_NO_ERROR(Msf.addStream(Blocks.size() * 4096, Blocks));
+
+  for (auto B : Blocks) {
+    EXPECT_FALSE(Msf.isPageFree(B));
+  }
+  for (int I = 11; I < 21; ++I) {
+    EXPECT_TRUE(Msf.isPageFree(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 page boundary.
+  MsfBuilder Msf(Allocator);
+
+  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);
+  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 page boundary.  This is because the newly added stream occupies
+  // so many pages that need to be indexed in the directory.
+  // crosses a page boundary.
+  MsfBuilder Msf(Allocator);
+
+  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
+  // of pages it occupies.
+  MsfBuilder Msf(Allocator);
+
+  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, TestGrowStreamWithDirectoryBlockIncrease) {
+  // Test that growing an existing stream to a value large enough that it causes
+  // the
+  // need to allocate new pages to the stream correctly updates the directory.
+  MsfBuilder Msf(Allocator);
+
+  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 pages it occupies makes no changes to the directory or super block.
+  MsfBuilder Msf(Allocator);
+
+  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, TestShrinkStreamWithDirectoryBlockDecrease) {
+  // Test that shrinking an existing stream to a value large enough that it
+  // causes the
+  // need to deallocate new pages to the stream correctly updates the directory.
+  MsfBuilder Msf(Allocator);
+
+  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);
+
+  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, TestPageCountsWhenAddingStreams) {
+  MsfBuilder Msf(Allocator);
+  Msf.initialize(4096);
+
+  // one for the super block, one for the directory block map
+  uint32_t NumUsedPages = Msf.getNumUsedPages();
+  EXPECT_EQ(2, NumUsedPages);
+  EXPECT_EQ(0, Msf.getNumFreePages());
+
+  const uint32_t StreamSizes[] = {4000, 6193, 189723};
+  for (int I = 0; I < 3; ++I) {
+    EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I]));
+    NumUsedPages += bytesToBlocks(StreamSizes[I], 4096);
+    EXPECT_EQ(NumUsedPages, Msf.getNumUsedPages());
+    EXPECT_EQ(0, Msf.getNumFreePages());
+  }
+}
+
+TEST_F(MsfBuilderTest, TestBuildMsfLayout) {
+  // Test that we can generate an Msf Layout structure from a valid layout
+  // specification.
+  MsfBuilder Msf(Allocator);
+  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 ExpectedNumPages = bytesToBlocks(StreamSizes[I], 4096);
+    EXPECT_EQ(ExpectedNumPages, L.StreamMap[I].size());
+  }
+}