[pdb/lld] Write a valid FPM

[zturner]

Summary

Prior to this patch, we did not emit a free page map to the PDB. Instead, we just wrote 0 bytes for the free page map. Since an a free page map represents a minimum of BlockSize * 8 blocks, this had the effect of saying that every PDB is a minimum of 4096*8*4096 = 134,217,728 bytes. This had undesirable side effects when re-linking our PDB with MSVC, which would output a PDB of slightly above the aforementioned size.

The fix for this is to simply write the actual bits of the FPM to appropriate block, but it is not quite that simple. Since one block of FPM data can only describe the state of 4096*8 = 32,768 blocks, supporting PDBs larger than this requires extra magic. To handle this, blocks of the form {1,2} + k * BlockSize are reserved and should not be allocated to any other type of PDB data. The FPM itself can then be viewed as a stream over the blocks {1 + 4096*0, 1 + 4096*1, 1 + 4096*2, ...} or {2 + 4096*0, 2 + 4096*1, 2 + 4096*2, ...} depending on the value of SuperBlock->FreeBlockMapBlock.

So we need some extra complexity that when allocating blocks from a stream, we check if the MSF file requires growing to vend the requested blocks. If it does, then we look to see if the growth would allocated blocks with the aforementioned indices, and if so we mark them as used in the FPM so that they will not be vended by the block allocator.

But that's not all! Another source of trickiness is in the fact that not all FPM blocks are even used. For example, if a PDB file has 5000 blocks, and SuperBlock->FreeBlockMapBlock == 1 , then blocks 1, 2, 4097, and 4098 are FPM blocks but only block 1 is allocated. And from block 1, only 625 bytes are needed. But blocks 2, 4097, and 4098 still need to be initialized to 0xFF, as do the extraneous bytes of block 1. Getting this to work invisibly while allowing the user of the API to see only those bytes of the FPM that describe actual blocks required some finesse.

[rnk]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

115 ↗

(On Diff #109390)

Can you refactor this alignTo(X, Y) / Y pattern into a helper like divideRoundUp or divideCeil? The usual way to do that is (X + Y - 1) / Y. alignTo does stuff we don't need.

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

158 ↗

(On Diff #109390)

Why not make this part of MSFBuilder? This doesn't use any PDBFileBuilder state, just an MSFLayout.

167–169 ↗

(On Diff #109390)

Why do you need to recreate the stream and writer?

[zturner]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

115 ↗

(On Diff #109390)

Yea I can add that.

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

158 ↗

(On Diff #109390)

MSFBuilder doesn't actually write any bytes, it just returns some bookeeping information (specifically, an MSFLayout structure) that describe the the MSF. It might be worth doing some refactoring and changing MSFBuilder::build() to MSFBuilder::commit() and write the super block, stream directory, and other MSF specific stuff, but I'd rather do that separately. PDBFileBuilder::commit() already writes all of that other MSF specific stuff anyway, so we might as well be consistent.

167–169 ↗

(On Diff #109390)

The stream doesn't have methods to update its length, so we need a new stream, and the writer doesn't have a method to set the stream to a new stream.

[zturner]

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

167–169 ↗

(On Diff #109390)

BTW, the cost of "making a new stream" is not high. Nothing is really happening other than allocating a stream object and setting some of its fields. So we're wasting one (small) heap allocated object, but there's no copying or anything going on.

[rnk]

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

167–169 ↗

(On Diff #109390)

Are you sure? createFpmStream above seems to initialize the stream to 0xFF, so it's probably like a 4K memset at least.

[zturner]

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

167–169 ↗

(On Diff #109390)

Ahh, you are right. I was confusing this code with code somewhere else. This line shouldn't be here. I used to have the initialization to 0xFF code here, so there was code to read the long version and then the short version. Then I sunk all that code into the createFpmStream method and didn't clean up properly here. Nice catch.

[zturner]

Updated from suggestions.

[rnk]

lgtm

llvm/trunk/include/llvm/DebugInfo/MSF/MSFCommon.h

 public:
   uint32_t Length;
   std::vector<support::ulittle32_t> Blocks;
 };
 
 /// \brief Determine the layout of the FPM stream, given the MSF layout.  An FPM
 /// stream spans 1 or more blocks, each at equally spaced intervals throughout
 /// the file.
-MSFStreamLayout getFpmStreamLayout(const MSFLayout &Msf);
+MSFStreamLayout getFpmStreamLayout(const MSFLayout &Msf,
+                                   bool IncludeUnusedFpmData = false,
+                                   bool AltFpm = false);
 
 inline bool isValidBlockSize(uint32_t Size) {
   switch (Size) {
   case 512:
   case 1024:
   case 2048:
   case 4096:
     return true;
   }
   return false;
 }
 
 // Super Block, Fpm0, Fpm1, and Block Map
 inline uint32_t getMinimumBlockCount() { return 4; }
 
 // Super Block, Fpm0, and Fpm1 are reserved.  The Block Map, although required
 // need not be at block 3.
 inline uint32_t getFirstUnreservedBlock() { return 3; }
 
 inline uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize) {
-  return alignTo(NumBytes, BlockSize) / BlockSize;
+  return divideCeil(NumBytes, BlockSize);
 }
 
 inline uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize) {
   return BlockNumber * BlockSize;
 }
 
 inline uint32_t getFpmIntervalLength(const MSFLayout &L) {
   return L.SB->BlockSize;
 }
 
-inline uint32_t getNumFpmIntervals(const MSFLayout &L) {
-  uint32_t Length = getFpmIntervalLength(L);
-  return alignTo(L.SB->NumBlocks, Length) / Length;
-}
-
-inline uint32_t getFullFpmByteSize(const MSFLayout &L) {
-  return alignTo(L.SB->NumBlocks, 8) / 8;
+inline uint32_t getNumFpmIntervals(const MSFLayout &L,
+                                   bool IncludeUnusedFpmData = false) {
+  if (IncludeUnusedFpmData)
+    return divideCeil(L.SB->NumBlocks, L.SB->BlockSize);
+
+  // We want the minimum number of intervals required, where each interval can
+  // represent BlockSize * 8 blocks.
+  return divideCeil(L.SB->NumBlocks, 8 * L.SB->BlockSize);
 }
 
 Error validateSuperBlock(const SuperBlock &SB);
 
 } // end namespace msf
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_MSF_MSFCOMMON_H

llvm/trunk/include/llvm/DebugInfo/MSF/MappedBlockStream.h

public:
 
   static std::unique_ptr<WritableMappedBlockStream>
   createDirectoryStream(const MSFLayout &Layout,
                         WritableBinaryStreamRef MsfData,
                         BumpPtrAllocator &Allocator);
 
   static std::unique_ptr<WritableMappedBlockStream>
   createFpmStream(const MSFLayout &Layout, WritableBinaryStreamRef MsfData,
-                  BumpPtrAllocator &Allocator);
+                  BumpPtrAllocator &Allocator, bool AltFpm = false);
 
   support::endianness getEndian() const override {
     return support::little;
   }
 
   Error readBytes(uint32_t Offset, uint32_t Size,
                   ArrayRef<uint8_t> &Buffer) override;
   Error readLongestContiguousChunk(uint32_t Offset,

llvm/trunk/include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h

public:
   Error commit(StringRef Filename);
 
   Expected<uint32_t> getNamedStreamIndex(StringRef Name) const;
   Error addNamedStream(StringRef Name, uint32_t Size);
 
 private:
   Expected<msf::MSFLayout> finalizeMsfLayout();
 
+  void commitFpm(WritableBinaryStream &MsfBuffer, const msf::MSFLayout &Layout);
+
   BumpPtrAllocator &Allocator;
 
   std::unique_ptr<msf::MSFBuilder> Msf;
   std::unique_ptr<InfoStreamBuilder> Info;
   std::unique_ptr<DbiStreamBuilder> Dbi;
   std::unique_ptr<GlobalsStreamBuilder> Globals;
   std::unique_ptr<PublicsStreamBuilder> Publics;
   std::unique_ptr<TpiStreamBuilder> Tpi;

llvm/trunk/include/llvm/Support/MathExtras.h

 
 /// Returns the next integer (mod 2**64) that is greater than or equal to
 /// \p Value and is a multiple of \c Align. \c Align must be non-zero.
 template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
   static_assert(Align != 0u, "Align must be non-zero");
   return (Value + Align - 1) / Align * Align;
 }
 
+/// Returns the integer ceil(Numerator / Denominator).
+inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
+  return alignTo(Numerator, Denominator) / Denominator;
+}
+
 /// \c alignTo for contexts where a constant expression is required.
 /// \sa alignTo
 ///
 /// \todo FIXME: remove when \c constexpr becomes really \c constexpr
 template <uint64_t Align>
 struct AlignTo {
   static_assert(Align != 0u, "Align must be non-zero");
   template <uint64_t Value>

llvm/trunk/lib/DebugInfo/MSF/MSFBuilder.cpp

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);
+    uint32_t OldBlockCount = FreeBlocks.size();
+    uint32_t NewBlockCount = AllocBlocks + OldBlockCount;
+    uint32_t NextFpmBlock = alignTo(OldBlockCount, BlockSize) + 1;
+    FreeBlocks.resize(NewBlockCount, true);
+    // If we crossed over an fpm page, we actually need to allocate 2 extra
+    // blocks for each FPM group crossed and mark both blocks from the group as
+    // used.  We may not actually use them since there are many more FPM blocks
+    // present than are required to represent all blocks in a given PDB, but we
+    // need to make sure they aren't allocated to a stream or something else.
+    // At the end when committing the PDB, we'll go through and mark the
+    // extraneous ones unused.
+    while (NextFpmBlock < NewBlockCount) {
+      NewBlockCount += 2;
+      FreeBlocks.resize(NewBlockCount, true);
+      FreeBlocks.reset(NextFpmBlock, NextFpmBlock + 2);
+      NextFpmBlock += BlockSize;
+    }
   }
 
   int I = 0;
   int Block = FreeBlocks.find_first();
   do {
     assert(Block != -1 && "We ran out of Blocks!");
 
     uint32_t NextBlock = static_cast<uint32_t>(Block);
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;
 }
 
+static void finalizeFpmBlockStatus(uint32_t B, ArrayRef<ulittle32_t> &FpmBlocks,
+                                   BitVector &Fpm) {
+  if (FpmBlocks.empty() || FpmBlocks.front() != B) {
+    Fpm.set(B);
+    return;
+  }
+
+  // If the next block in the actual layout is this block, it should *not* be
+  // free.
+  assert(!Fpm.test(B));
+  FpmBlocks = FpmBlocks.drop_front();
+}
+
 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;
for (uint32_t I = 0; I < StreamData.size(); ++I) {
           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());
     }
   }
 
+  // FPM blocks occur in pairs at every `BlockLength` interval.  While blocks of
+  // this form are reserved for FPM blocks, not all blocks of this form will
+  // actually be needed for FPM data because there are more blocks of this form
+  // than are required to represent a PDB file with a given number of blocks.
+  // So we need to find out which blocks are *actually* going to be real FPM
+  // blocks, then mark the reset of the reserved blocks as unallocated.
+  MSFStreamLayout FpmLayout = msf::getFpmStreamLayout(L, true);
+  auto FpmBlocks = makeArrayRef(FpmLayout.Blocks);
+  for (uint32_t B = kFreePageMap0Block; B < SB->NumBlocks;
+       B += msf::getFpmIntervalLength(L)) {
+    finalizeFpmBlockStatus(B, FpmBlocks, FreeBlocks);
+    finalizeFpmBlockStatus(B + 1, FpmBlocks, FreeBlocks);
+  }
+  L.FreePageMap = FreeBlocks;
+
   return L;
 }

llvm/trunk/lib/DebugInfo/MSF/MSFCommon.cpp

Error llvm::msf::validateSuperBlock(const SuperBlock &SB) {
   if (SB.FreeBlockMapBlock != 1 && SB.FreeBlockMapBlock != 2)
     return make_error<MSFError>(
         msf_error_code::invalid_format,
         "The free block map isn't at block 1 or block 2.");
 
   return Error::success();
 }
 
-MSFStreamLayout llvm::msf::getFpmStreamLayout(const MSFLayout &Msf) {
+MSFStreamLayout llvm::msf::getFpmStreamLayout(const MSFLayout &Msf,
+                                              bool IncludeUnusedFpmData,
+                                              bool AltFpm) {
   MSFStreamLayout FL;
-  uint32_t NumFpmIntervals = getNumFpmIntervals(Msf);
+  uint32_t NumFpmIntervals = getNumFpmIntervals(Msf, IncludeUnusedFpmData);
   support::ulittle32_t FpmBlock = Msf.SB->FreeBlockMapBlock;
   assert(FpmBlock == 1 || FpmBlock == 2);
-  while (NumFpmIntervals > 0) {
+  if (AltFpm) {
+    // If they requested the alternate FPM, then 2 becomes 1 and 1 becomes 2.
+    FpmBlock = 3U - FpmBlock;
+  }
+  for (uint32_t I = 0; I < NumFpmIntervals; ++I) {
     FL.Blocks.push_back(FpmBlock);
     FpmBlock += msf::getFpmIntervalLength(Msf);
-    --NumFpmIntervals;
   }
-  FL.Length = getFullFpmByteSize(Msf);
+
+  if (IncludeUnusedFpmData)
+    FL.Length = NumFpmIntervals * Msf.SB->BlockSize;
+  else
+    FL.Length = divideCeil(Msf.SB->NumBlocks, 8);
 
   return FL;
 }

llvm/trunk/lib/DebugInfo/MSF/MappedBlockStream.cpp

 //===- 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/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
+#include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstring>
 #include <utility>
WritableMappedBlockStream::createDirectoryStream(
   SL.Blocks = Layout.DirectoryBlocks;
   SL.Length = Layout.SB->NumDirectoryBytes;
   return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
 }
 
 std::unique_ptr<WritableMappedBlockStream>
 WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout,
                                            WritableBinaryStreamRef MsfData,
-                                           BumpPtrAllocator &Allocator) {
-  MSFStreamLayout SL(getFpmStreamLayout(Layout));
-  return createStream(Layout.SB->BlockSize, SL, MsfData, Allocator);
+                                           BumpPtrAllocator &Allocator,
+                                           bool AltFpm) {
+  // We only want to give the user a stream containing the bytes of the FPM that
+  // are actually valid, but we want to initialize all of the bytes, even those
+  // that come from reserved FPM blocks where the entire block is unused.  To do
+  // this, we first create the full layout, which gives us a stream with all
+  // bytes and all blocks, and initialize everything to 0xFF (all blocks in the
+  // file are unused).  Then we create the minimal layout (which contains only a
+  // subset of the bytes previously initialized), and return that to the user.
+  MSFStreamLayout MinLayout(getFpmStreamLayout(Layout, false, AltFpm));
+
+  MSFStreamLayout FullLayout(getFpmStreamLayout(Layout, true, AltFpm));
+  auto Result =
+      createStream(Layout.SB->BlockSize, FullLayout, MsfData, Allocator);
+  if (!Result)
+    return Result;
+  std::vector<uint8_t> InitData(Layout.SB->BlockSize, 0xFF);
+  BinaryStreamWriter Initializer(*Result);
+  while (Initializer.bytesRemaining() > 0)
+    cantFail(Initializer.writeBytes(InitData));
+  return createStream(Layout.SB->BlockSize, MinLayout, MsfData, Allocator);
 }
 
 Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
                                            ArrayRef<uint8_t> &Buffer) {
   return ReadInterface.readBytes(Offset, Size, Buffer);
 }
 
 Error WritableMappedBlockStream::readLongestContiguousChunk(

llvm/trunk/lib/DebugInfo/PDB/Native/PDBFile.cpp

Error PDBFile::parseFileHeaders() {
   // current versions of the MSF format already expect the Fpm to be arranged
   // at getBlockSize() intervals, so we have to be compatible.
   // See the function fpmPn() for more information:
   // https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L489
   auto FpmStream =
       MappedBlockStream::createFpmStream(ContainerLayout, *Buffer, Allocator);
   BinaryStreamReader FpmReader(*FpmStream);
   ArrayRef<uint8_t> FpmBytes;
-  if (auto EC = FpmReader.readBytes(FpmBytes,
-                                    msf::getFullFpmByteSize(ContainerLayout)))
+  if (auto EC = FpmReader.readBytes(FpmBytes, FpmReader.bytesRemaining()))
     return EC;
   uint32_t BlocksRemaining = getBlockCount();
   uint32_t BI = 0;
   for (auto Byte : FpmBytes) {
     uint32_t BlocksThisByte = std::min(BlocksRemaining, 8U);
     for (uint32_t I = 0; I < BlocksThisByte; ++I) {
       if (Byte & (1 << I))
         ContainerLayout.FreePageMap[BI] = true;

llvm/trunk/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

 
 Expected<uint32_t> PDBFileBuilder::getNamedStreamIndex(StringRef Name) const {
   uint32_t SN = 0;
   if (!NamedStreams.get(Name, SN))
     return llvm::make_error<pdb::RawError>(raw_error_code::no_stream);
   return SN;
 }
 
+void PDBFileBuilder::commitFpm(WritableBinaryStream &MsfBuffer,
+                               const MSFLayout &Layout) {
+  auto FpmStream =
+      WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator);
+
+  // We only need to create the alt fpm stream so that it gets initialized.
+  WritableMappedBlockStream::createFpmStream(Layout, MsfBuffer, Allocator,
+                                             true);
+
+  uint32_t BI = 0;
+  BinaryStreamWriter FpmWriter(*FpmStream);
+  while (BI < Layout.SB->NumBlocks) {
+    uint8_t ThisByte = 0;
+    for (uint32_t I = 0; I < 8; ++I) {
+      bool IsFree =
+          (BI < Layout.SB->NumBlocks) ? Layout.FreePageMap.test(BI) : true;
+      uint8_t Mask = uint8_t(IsFree) << I;
+      ThisByte |= Mask;
+      ++BI;
+    }
+    cantFail(FpmWriter.writeObject(ThisByte));
+  }
+  assert(FpmWriter.bytesRemaining() == 0);
+}
+
 Error PDBFileBuilder::commit(StringRef Filename) {
   assert(!Filename.empty());
   auto ExpectedLayout = finalizeMsfLayout();
   if (!ExpectedLayout)
     return ExpectedLayout.takeError();
   auto &Layout = *ExpectedLayout;
 
   uint64_t Filesize = Layout.SB->BlockSize * Layout.SB->NumBlocks;
   auto OutFileOrError = FileOutputBuffer::create(Filename, Filesize);
   if (OutFileOrError.getError())
     return llvm::make_error<pdb::GenericError>(generic_error_code::invalid_path,
                                                Filename);
   FileBufferByteStream Buffer(std::move(*OutFileOrError),
                               llvm::support::little);
   BinaryStreamWriter Writer(Buffer);
 
   if (auto EC = Writer.writeObject(*Layout.SB))
     return EC;
+
+  commitFpm(Buffer, Layout);
+
   uint32_t BlockMapOffset =
       msf::blockToOffset(Layout.SB->BlockMapAddr, Layout.SB->BlockSize);
   Writer.setOffset(BlockMapOffset);
   if (auto EC = Writer.writeArray(Layout.DirectoryBlocks))
     return EC;
 
   auto DirStream = WritableMappedBlockStream::createDirectoryStream(
       Layout, Buffer, Allocator);

llvm/trunk/test/DebugInfo/PDB/write-fpm.test

+; RUN: llvm-pdbutil yaml2pdb -pdb=%t.pdb %p/Inputs/one-symbol.yaml
+; RUN: llvm-pdbutil bytes -fpm %t.pdb | FileCheck %s
+
+
+CHECK:                             Free Page Map
+CHECK-NEXT: ============================================================
+CHECK-NEXT: Block 1 (
+CHECK-NEXT:   1000: 04F8FFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF  |................................|
+CHECK-NEXT:   1020: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF  |................................|
+CHECK:        1FE0: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF  |................................|
+CHECK:      )

llvm/trunk/unittests/DebugInfo/MSF/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   DebugInfoMSF
   )
 
 set(DebugInfoMSFSources
   MappedBlockStreamTest.cpp
   MSFBuilderTest.cpp
+  MSFCommonTest.cpp
   )
 
 add_llvm_unittest(DebugInfoMSFTests
   ${DebugInfoMSFSources}
   )
 
 target_link_libraries(DebugInfoMSFTests LLVMTestingSupport)

llvm/trunk/unittests/DebugInfo/MSF/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 "llvm/DebugInfo/MSF/MSFBuilder.h"
 #include "llvm/DebugInfo/MSF/MSFCommon.h"
 #include "llvm/Testing/Support/Error.h"
 
+#include "gmock/gmock-matchers.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace llvm::msf;
+using namespace testing;
 
 namespace {
 class MSFBuilderTest : public testing::Test {
 protected:
   void initializeSimpleSuperBlock(msf::SuperBlock &SB) {
     initializeSuperBlock(SB);
     SB.NumBlocks = 1000;
     SB.NumDirectoryBytes = 8192;
TEST_F(MSFBuilderTest, DirectoryBlockHintOverestimated) {
   ASSERT_THAT_EXPECTED(Msf.addStream(2048), Succeeded());
 
   auto ExpectedLayout = Msf.build();
   ASSERT_THAT_EXPECTED(ExpectedLayout, Succeeded());
   MSFLayout &L = *ExpectedLayout;
   EXPECT_EQ(1U, L.DirectoryBlocks.size());
   EXPECT_EQ(B + 1, L.DirectoryBlocks[0]);
 }
+
+TEST_F(MSFBuilderTest, StreamDoesntUseFpmBlocks) {
+  Expected<MSFBuilder> ExpectedMsf = MSFBuilder::create(Allocator, 4096);
+  ASSERT_THAT_EXPECTED(ExpectedMsf, Succeeded());
+  auto &Msf = *ExpectedMsf;
+
+  // A block is 4096 bytes, and every 4096 blocks we have 2 reserved FPM blocks.
+  // By creating add a stream that spans 4096*4096*3 bytes, we ensure that we
+  // cross over a couple of reserved FPM blocks, and that none of them are
+  // allocated to the stream.
+  constexpr uint32_t StreamSize = 4096 * 4096 * 3;
+  Expected<uint32_t> SN = Msf.addStream(StreamSize);
+  ASSERT_THAT_EXPECTED(SN, Succeeded());
+
+  auto ExpectedLayout = Msf.build();
+  ASSERT_THAT_EXPECTED(ExpectedLayout, Succeeded());
+  MSFLayout &L = *ExpectedLayout;
+  auto BlocksRef = L.StreamMap[*SN];
+  std::vector<uint32_t> Blocks(BlocksRef.begin(), BlocksRef.end());
+  EXPECT_EQ(StreamSize, L.StreamSizes[*SN]);
+
+  for (uint32_t I = 0; I <= 3; ++I) {
+    // Pages from the regular FPM are allocated, while pages from the alt fpm
+    // are free.
+    EXPECT_FALSE(L.FreePageMap.test(1 + I * 4096));
+    EXPECT_TRUE(L.FreePageMap.test(2 + I * 4096));
+  }
+
+  for (uint32_t I = 1; I <= 3; ++I) {
+    EXPECT_THAT(Blocks, Not(Contains(1 + I * 4096)));
+    EXPECT_THAT(Blocks, Not(Contains(2 + I * 4096)));
+  }
+}

llvm/trunk/unittests/DebugInfo/MSF/MSFCommonTest.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 "llvm/DebugInfo/MSF/MSFCommon.h"
+#include "llvm/Testing/Support/Error.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::msf;
+
+TEST(MSFCommonTest, BytesToBlocks) {
+  EXPECT_EQ(0ULL, bytesToBlocks(0, 4096));
+  EXPECT_EQ(1ULL, bytesToBlocks(12, 4096));
+  EXPECT_EQ(1ULL, bytesToBlocks(4096, 4096));
+  EXPECT_EQ(2ULL, bytesToBlocks(4097, 4096));
+  EXPECT_EQ(2ULL, bytesToBlocks(600, 512));
+}
+
+TEST(MSFCommonTest, FpmIntervals) {
+  SuperBlock SB;
+  SB.FreeBlockMapBlock = 1;
+  SB.BlockSize = 4096;
+
+  MSFLayout L;
+  L.SB = &SB;
+
+  SB.NumBlocks = 12;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, false));
+  SB.NumBlocks = SB.BlockSize;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, false));
+  SB.NumBlocks = SB.BlockSize + 1;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, false));
+  SB.NumBlocks = SB.BlockSize * 8;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, false));
+  SB.NumBlocks = SB.BlockSize * 8 + 1;
+  EXPECT_EQ(2u, getNumFpmIntervals(L, false));
+
+  SB.NumBlocks = 12;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, true));
+  SB.NumBlocks = SB.BlockSize;
+  EXPECT_EQ(1u, getNumFpmIntervals(L, true));
+  SB.NumBlocks = SB.BlockSize + 1;
+  EXPECT_EQ(2u, getNumFpmIntervals(L, true));
+  SB.NumBlocks = SB.BlockSize * 8;
+  EXPECT_EQ(8u, getNumFpmIntervals(L, true));
+  SB.NumBlocks = SB.BlockSize * 8 + 1;
+  EXPECT_EQ(9u, getNumFpmIntervals(L, true));
+}
+
+TEST(MSFCommonTest, FpmStreamLayout) {
+  SuperBlock SB;
+  MSFLayout L;
+  L.SB = &SB;
+  SB.FreeBlockMapBlock = 1;
+
+  // Each FPM block has 4096 bytes for a maximum of 4096*8 allocation states.
+  SB.BlockSize = 4096;
+
+  // 1. When we're not including unused FPM data, the length of the FPM stream
+  //    should be only long enough to contain 1 bit for each block.
+
+  // 1a. When the PDB has <= 4096*8 blocks, there should only be one FPM block.
+  SB.NumBlocks = 8000;
+  MSFStreamLayout SL = getFpmStreamLayout(L, false, false);
+  EXPECT_EQ(1000u, SL.Length);
+  EXPECT_EQ(1u, SL.Blocks.size());
+  EXPECT_EQ(SB.FreeBlockMapBlock, SL.Blocks.front());
+
+  SL = getFpmStreamLayout(L, false, true);
+  EXPECT_EQ(1000u, SL.Length);
+  EXPECT_EQ(1u, SL.Blocks.size());
+  EXPECT_EQ(3u - SB.FreeBlockMapBlock, SL.Blocks.front());
+
+  // 1b. When the PDB has > 4096*8 blocks, there should be multiple FPM blocks.
+  SB.NumBlocks = SB.BlockSize * 8 + 1;
+  SL = getFpmStreamLayout(L, false, false);
+  EXPECT_EQ(SB.BlockSize + 1, SL.Length);
+  EXPECT_EQ(2u, SL.Blocks.size());
+  EXPECT_EQ(SB.FreeBlockMapBlock, SL.Blocks[0]);
+  EXPECT_EQ(SB.FreeBlockMapBlock + SB.BlockSize, SL.Blocks[1]);
+
+  SL = getFpmStreamLayout(L, false, true);
+  EXPECT_EQ(SB.BlockSize + 1, SL.Length);
+  EXPECT_EQ(2u, SL.Blocks.size());
+  EXPECT_EQ(3u - SB.FreeBlockMapBlock, SL.Blocks[0]);
+  EXPECT_EQ(3u - SB.FreeBlockMapBlock + SB.BlockSize, SL.Blocks[1]);
+
+  // 2. When we are including unused FPM data, there should be one FPM block
+  //    at every BlockSize interval in the file, even if entire FPM blocks are
+  //    unused.
+  SB.NumBlocks = SB.BlockSize * 8 + 1;
+  SL = getFpmStreamLayout(L, true, false);
+  EXPECT_EQ(SB.BlockSize * 9, SL.Length);
+  EXPECT_EQ(9u, SL.Blocks.size());
+  for (int I = 0; I < 9; ++I)
+    EXPECT_EQ(I * SB.BlockSize + SB.FreeBlockMapBlock, SL.Blocks[I]);
+}

llvm/trunk/unittests/DebugInfo/MSF/MappedBlockStreamTest.cpp

 #include "llvm/DebugInfo/MSF/IMSFFile.h"
 #include "llvm/DebugInfo/MSF/MSFError.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/BinaryStreamRef.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Testing/Support/Error.h"
 
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <unordered_map>
 
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::support;
 
DiscontiguousStream F(Blocks, Data);
     ::memset(DataBytes.data(), 0, 10);
     EXPECT_THAT_ERROR(Writer.writeCString(Str[0]), Succeeded());
     EXPECT_THAT_ERROR(Reader.readCString(Str[1]), Succeeded());
     EXPECT_EQ(Str[0], Str[1]);
   }
 
   EXPECT_EQ(Str[0], Str[1]);
 }
+} // namespace
+
+MATCHER_P3(BlockIsFilledWith, Layout, BlockIndex, Byte, "succeeded") {
+  uint64_t Offset = msf::blockToOffset(BlockIndex, Layout.SB->BlockSize);
+  ArrayRef<uint8_t> BufferRef = makeArrayRef(arg);
+  BufferRef = BufferRef.slice(Offset, Layout.SB->BlockSize);
+  return llvm::all_of(BufferRef, [this](uint8_t B) { return B == Byte; });
+}
+
+namespace {
+TEST(MappedBlockStreamTest, CreateFpmStream) {
+  BumpPtrAllocator Allocator;
+  SuperBlock SB;
+  MSFLayout L;
+  L.SB = &SB;
+
+  SB.FreeBlockMapBlock = 1;
+  SB.BlockSize = 4096;
+
+  constexpr uint32_t NumFileBlocks = 4096 * 4;
+
+  std::vector<uint8_t> MsfBuffer(NumFileBlocks * SB.BlockSize);
+  MutableBinaryByteStream MsfStream(MsfBuffer, llvm::support::little);
+
+  SB.NumBlocks = NumFileBlocks;
+  auto FpmStream =
+      WritableMappedBlockStream::createFpmStream(L, MsfStream, Allocator);
+  // 4096 * 4 / 8 = 2048 bytes of FPM data is needed to describe 4096 * 4
+  // blocks.  This translates to 1 FPM block.
+  EXPECT_EQ(2048u, FpmStream->getLength());
+  EXPECT_EQ(1u, FpmStream->getStreamLayout().Blocks.size());
+  EXPECT_EQ(1u, FpmStream->getStreamLayout().Blocks[0]);
+  // All blocks from FPM1 should be 1 initialized, and all blocks from FPM2
+  // should be 0 initialized (since we requested the main FPM, not the alt FPM)
+  for (int I = 0; I < 4; ++I) {
+    EXPECT_THAT(MsfBuffer, BlockIsFilledWith(L, 1 + I * SB.BlockSize, 0xFF));
+    EXPECT_THAT(MsfBuffer, BlockIsFilledWith(L, 2 + I * SB.BlockSize, 0));
+  }
+
+  ::memset(MsfBuffer.data(), 0, MsfBuffer.size());
+  FpmStream =
+      WritableMappedBlockStream::createFpmStream(L, MsfStream, Allocator, true);
+  // 4096 * 4 / 8 = 2048 bytes of FPM data is needed to describe 4096 * 4
+  // blocks.  This translates to 1 FPM block.
+  EXPECT_EQ(2048u, FpmStream->getLength());
+  EXPECT_EQ(1u, FpmStream->getStreamLayout().Blocks.size());
+  EXPECT_EQ(2u, FpmStream->getStreamLayout().Blocks[0]);
+  // All blocks from FPM2 should be 1 initialized, and all blocks from FPM1
+  // should be 0 initialized (since we requested the alt FPM, not the main FPM)
+  for (int I = 0; I < 4; ++I) {
+    EXPECT_THAT(MsfBuffer, BlockIsFilledWith(L, 1 + I * SB.BlockSize, 0));
+    EXPECT_THAT(MsfBuffer, BlockIsFilledWith(L, 2 + I * SB.BlockSize, 0xFF));
+  }
+}
 
 } // end anonymous namespace