[msf] Make Fpm reader and writer use MappedBlockStream

[zturner]

Summary

MappedBlockStream can work with any sequence of block data where the ordering is specified by a list of block numbers. This is true even in the case of split FPMs. So here we add support for creating a MappedBlockStream representing the Fpm so we can just read it in one single operation. This is also nice because we have to read/write the Fpm from multiple places, so this allows us to centralize all the logic to make sure we aren't reproducing the split interval logic in many locations.

For some reason, this also seems to fix a bug. I no longer show any orphaned pages on larger PDBs.

[ruiu]

LGTM

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

 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;
 }
 
+inline uint32_t getFpmIntervalLength(const MSFLayout &L) {
+  return L.SB->BlockSize;
+}
+
+inline uint32_t getNumFpmIntervals(const MSFLayout &L) {
+  uint32_t Length = getFpmIntervalLength(L);
+  return llvm::alignTo(L.SB->NumBlocks, Length) / Length;
+}
+
+inline uint32_t getFullFpmByteSize(const MSFLayout &L) {
+  return llvm::alignTo(L.SB->NumBlocks, 8) / 8;
+}
+
 Error validateSuperBlock(const SuperBlock &SB);
 } // namespace msf
 } // namespace llvm
 
 #endif // LLVM_DEBUGINFO_MSF_MSFCOMMON_H

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

 //===- MSFStreamLayout.h - Describes the layout of a stream -----*- 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_MSF_MSFSTREAMLAYOUT_H
 #define LLVM_DEBUGINFO_MSF_MSFSTREAMLAYOUT_H
 
-#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/Endian.h"
 
 #include <cstdint>
+#include <vector>
 
 namespace llvm {
 namespace msf {
 
 /// \brief Describes the layout of a stream in an MSF layout.  A "stream" here
 /// is defined as any logical unit of data which may be arranged inside the MSF
 /// file as a sequence of (possibly discontiguous) blocks.  When we want to read
 /// from a particular MSF Stream, we fill out a stream layout structure and the
 /// reader uses it to determine which blocks in the underlying MSF file contain
 /// the data, so that it can be pieced together in the right order.
 class MSFStreamLayout {
 public:
   uint32_t Length;
-  ArrayRef<support::ulittle32_t> Blocks;
+  std::vector<support::ulittle32_t> Blocks;
 };
 } // namespace msf
 } // namespace llvm
 
 #endif // LLVM_DEBUGINFO_MSF_MSFSTREAMLAYOUT_H

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

 /// the case of a standard MSF Stream, the layout of the stream's blocks
 /// is described by the MSF "directory", but in the case of the directory
 /// itself, the layout is described by an array at a fixed location within
 /// the MSF.  MappedBlockStream provides methods for reading from and writing
 /// to one of these streams transparently, as if it were a contiguous sequence
 /// of bytes.
 class MappedBlockStream : public ReadableStream {
   friend class WritableMappedBlockStream;
-
 public:
   static std::unique_ptr<MappedBlockStream>
   createStream(uint32_t BlockSize, uint32_t NumBlocks,
                const MSFStreamLayout &Layout, const ReadableStream &MsfData);
 
   static std::unique_ptr<MappedBlockStream>
   createIndexedStream(const MSFLayout &Layout, const ReadableStream &MsfData,
                       uint32_t StreamIndex);
 
   static std::unique_ptr<MappedBlockStream>
+  createFpmStream(const MSFLayout &Layout, const ReadableStream &MsfData);
+
+  static std::unique_ptr<MappedBlockStream>
   createDirectoryStream(const MSFLayout &Layout, const ReadableStream &MsfData);
 
   Error readBytes(uint32_t Offset, uint32_t Size,
                   ArrayRef<uint8_t> &Buffer) const override;
   Error readLongestContiguousChunk(uint32_t Offset,
                                    ArrayRef<uint8_t> &Buffer) const override;
 
   uint32_t getLength() const override;
public:
 
   static std::unique_ptr<WritableMappedBlockStream>
   createIndexedStream(const MSFLayout &Layout, const WritableStream &MsfData,
                       uint32_t StreamIndex);
 
   static std::unique_ptr<WritableMappedBlockStream>
   createDirectoryStream(const MSFLayout &Layout, const WritableStream &MsfData);
 
+  static std::unique_ptr<WritableMappedBlockStream>
+  createFpmStream(const MSFLayout &Layout, const WritableStream &MsfData);
+
   Error readBytes(uint32_t Offset, uint32_t Size,
                   ArrayRef<uint8_t> &Buffer) const override;
   Error readLongestContiguousChunk(uint32_t Offset,
                                    ArrayRef<uint8_t> &Buffer) const override;
   uint32_t getLength() const override;
 
   Error writeBytes(uint32_t Offset, ArrayRef<uint8_t> Buffer) const override;
 

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

 template <typename Base> class MappedBlockStreamImpl : public Base {
 public:
   template <typename... Args>
   MappedBlockStreamImpl(Args &&... Params)
       : Base(std::forward<Args>(Params)...) {}
 };
 }
 
+static void initializeFpmStreamLayout(const MSFLayout &Layout,
+                                      MSFStreamLayout &FpmLayout) {
+  uint32_t NumFpmIntervals = msf::getNumFpmIntervals(Layout);
+  support::ulittle32_t FpmBlock = Layout.SB->FreeBlockMapBlock;
+  assert(FpmBlock == 1 || FpmBlock == 2);
+  while (NumFpmIntervals > 0) {
+    FpmLayout.Blocks.push_back(FpmBlock);
+    FpmBlock += msf::getFpmIntervalLength(Layout);
+    --NumFpmIntervals;
+  }
+  FpmLayout.Length = msf::getFullFpmByteSize(Layout);
+}
+
 typedef std::pair<uint32_t, uint32_t> Interval;
 static Interval intersect(const Interval &I1, const Interval &I2) {
   return std::make_pair(std::max(I1.first, I2.first),
                         std::min(I1.second, I2.second));
 }
 
 MappedBlockStream::MappedBlockStream(uint32_t BlockSize, uint32_t NumBlocks,
                                      const MSFStreamLayout &Layout,

 MappedBlockStream::createDirectoryStream(const MSFLayout &Layout,
                                          const ReadableStream &MsfData) {
   MSFStreamLayout SL;
   SL.Blocks = Layout.DirectoryBlocks;
   SL.Length = Layout.SB->NumDirectoryBytes;
   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
 }
 
+std::unique_ptr<MappedBlockStream>
+MappedBlockStream::createFpmStream(const MSFLayout &Layout,
+                                   const ReadableStream &MsfData) {
+  MSFStreamLayout SL;
+  initializeFpmStreamLayout(Layout, SL);
+  return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
 Error MappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
                                    ArrayRef<uint8_t> &Buffer) const {
   // Make sure we aren't trying to read beyond the end of the stream.
   if (Size > StreamLayout.Length)
     return make_error<MSFError>(msf_error_code::insufficient_buffer);
   if (Offset > StreamLayout.Length - Size)
     return make_error<MSFError>(msf_error_code::insufficient_buffer);
 

 WritableMappedBlockStream::createDirectoryStream(
     const MSFLayout &Layout, const WritableStream &MsfData) {
   MSFStreamLayout SL;
   SL.Blocks = Layout.DirectoryBlocks;
   SL.Length = Layout.SB->NumDirectoryBytes;
   return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
 }
 
+std::unique_ptr<WritableMappedBlockStream>
+WritableMappedBlockStream::createFpmStream(const MSFLayout &Layout,
+                                           const WritableStream &MsfData) {
+  MSFStreamLayout SL;
+  initializeFpmStreamLayout(Layout, SL);
+  return createStream(Layout.SB->BlockSize, Layout.SB->NumBlocks, SL, MsfData);
+}
+
 Error WritableMappedBlockStream::readBytes(uint32_t Offset, uint32_t Size,
                                            ArrayRef<uint8_t> &Buffer) const {
   return ReadInterface.readBytes(Offset, Size, Buffer);
 }
 
 Error WritableMappedBlockStream::readLongestContiguousChunk(
     uint32_t Offset, ArrayRef<uint8_t> &Buffer) const {
   return ReadInterface.readLongestContiguousChunk(Offset, Buffer);

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

Error PDBFile::parseFileHeaders() {
 
   if (Buffer->getLength() % SB->BlockSize != 0)
     return make_error<RawError>(raw_error_code::corrupt_file,
                                 "File size is not a multiple of block size");
   ContainerLayout.SB = SB;
 
   // Initialize Free Page Map.
   ContainerLayout.FreePageMap.resize(SB->NumBlocks);
-  ArrayRef<uint8_t> FpmBytes;
   // The Fpm exists either at block 1 or block 2 of the MSF.  However, this
   // allows for a maximum of getBlockSize() * 8 blocks bits in the Fpm, and
   // thusly an equal number of total blocks in the file.  For a block size
   // of 4KiB (very common), this would yield 32KiB total blocks in file, for a
   // maximum file size of 32KiB * 4KiB = 128MiB.  Obviously this won't do, so
   // the Fpm is split across the file at `getBlockSize()` intervals.  As a
   // result, every block whose index is of the form |{1,2} + getBlockSize() * k|
   // for any non-negative integer k is an Fpm block.  In theory, we only really
   // need to reserve blocks of the form |{1,2} + getBlockSize() * 8 * k|, but
   // 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
-
-  uint32_t BlocksPerSection = getBlockSize();
-  uint64_t FpmBlockOffset = SB->FreeBlockMapBlock;
-  uint32_t BlocksRemaining = getBlockCount();
-  for (uint32_t SI = 0; BlocksRemaining > 0; ++SI) {
-    uint32_t FpmFileOffset = FpmBlockOffset * getBlockSize();
-
-    if (auto EC = Buffer->readBytes(FpmFileOffset, getBlockSize(), FpmBytes))
-      return EC;
-
-    uint32_t BlocksThisSection = std::min(BlocksRemaining, BlocksPerSection);
-    for (uint32_t I = 0; I < BlocksThisSection; ++I) {
-      uint32_t BI = I + BlocksPerSection * SI;
-
-      if (FpmBytes[I / 8] & (1 << (I % 8)))
+  auto FpmStream = MappedBlockStream::createFpmStream(ContainerLayout, *Buffer);
+  StreamReader FpmReader(*FpmStream);
+  ArrayRef<uint8_t> FpmBytes;
+  if (auto EC = FpmReader.readBytes(FpmBytes,
+                                    msf::getFullFpmByteSize(ContainerLayout)))
+  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;
+      --BlocksRemaining;
+      ++BI;
     }
-    BlocksRemaining -= BlocksThisSection;
-    FpmBlockOffset += BlocksPerSection;
   }
 
   Reader.setOffset(getBlockMapOffset());
   if (auto EC = Reader.readArray(ContainerLayout.DirectoryBlocks,
                                  getNumDirectoryBlocks()))
     return EC;
 
   return Error::success();

llvm/trunk/tools/llvm-pdbdump/LLVMOutputStyle.cpp

Error LLVMOutputStyle::dumpFreePageMap() {
   // Start with used pages instead of free pages because
   // the number of free pages is far larger than used pages.
   BitVector FPM = File.getMsfLayout().FreePageMap;
 
   PageStats PS(FPM);
 
   recordKnownUsedPage(PS, 0); // MSF Super Block
 
-  uint32_t BlocksPerSection = File.getBlockSize();
-  uint32_t NumSections =
-      llvm::alignTo(File.getBlockCount(), BlocksPerSection) / BlocksPerSection;
+  uint32_t BlocksPerSection = msf::getFpmIntervalLength(File.getMsfLayout());
+  uint32_t NumSections = msf::getNumFpmIntervals(File.getMsfLayout());
   for (uint32_t I = 0; I < NumSections; ++I) {
     uint32_t Fpm0 = 1 + BlocksPerSection * I;
     // 2 Fpm blocks spaced at `getBlockSize()` block intervals
     recordKnownUsedPage(PS, Fpm0);
     recordKnownUsedPage(PS, Fpm0 + 1);
   }
 
   recordKnownUsedPage(PS, File.getBlockMapIndex()); // Stream Table