pdbdump: Dump Free Page Map contents.

[ruiu]

Summary

This is a patch to dump the free page map.

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

49–52

Would SparseBitVector be a more appropriate API to use?

53–56

This will only read a single block right?
If the block size was 4 KB, would that mean that the FPM can only account for 128 MB?
This seems small.

Microsoft's code suggests that the FPM could span two blocks:
https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L222

[zturner]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

How about adding another field to the MsfLayout class called FreePageMap? You will need to set the value in MsfBuilder::build() before returning, and you will also need to set it in PDBFile::parseFileHeaders().

This way you wouldn't need to return an Expected<std::vector<uint32_t>> but rather a const BitVector&, and the reading / writing code would share the same common structures.

53–56

It doesn't span 2 pages. But it's *either* page 1 or page 2. Which one it is depends on the second field in the super block. But whichever one it is, it's only that 1 page.

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

I don't think that's right:
https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L172

53–56

Also:
https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L38

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

Hmm, but there is also:

In the interest of the on-disk size of the file, the FPM has been split across the file at regular intervals, with new intervals introduced as needed.

https://github.com/Microsoft/microsoft-pdb/blob/master/PDB/msf/msf.cpp#L49

[zturner]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

Yea, but read the very next line:

According to hdr.pnFpm, the first or the second free page map is valid.

What I'm not sure about is this line:

In the interest of the on-disk size of the file, the FPM has been split across the file at regular intervals, with new intervals introduced as needed

[ruiu]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

At least, the test PDB file I was using contains a seemingly valid FPM in FPM2, and FPM1 contents doesn't seem to make sense.

[zturner]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

Wait, I think I get it. As you deduced, the maximum number of a single page of bits can represent is BlockSize * 8. But the SuperBlock tells you exactly how many pages are in the file. If the number of pages in the SuperBlock are more than the number that can be represented by a single page of bits, then there will be a page in the middle of the file that "continues" the Free Page Map. It will probably be precisely the page with index BlockSize * 8

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

53–56

Yeah, that seems to match my reading of things. Would be good to check with a big pdb like chrome_child.

[ruiu]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

What is a bit annoying is that BitVector doesn't provide a way to map itself onto an existing bitmap, so I need to examine each bit and flip a bit in a BitVector. But, because the number of bits we have here is small anyways, it is probably okay to copy bit by bit. I'll try to add BitVector to MsfLayout.

[zturner]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

It seems like we could just add a new constructor to the BitVector class like this:

BitVector(BitWord *Buffer, uint32_t NumBits);

[ruiu]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

BitWord is an internal thing of BitVector, so it probably should be uint8_t * and NumBits, or ArrayRef<uint8_t>. I'll try to see if I can add a new constructor.

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

It already has BitVector::setBitsInMask.

[ruiu]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

I took a look at the function and noticed that it takes a pointer to uint32_t. So the endianess matters here, so I cannot use it for an array read from file (unless swapping bytes before passing it to setBitsInMask).

[majnemer]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

You could just loop and call setBitsInMask.

[ruiu]

• Move FPM to MsfLayout.
• Use BitVector to represent FPM.

[ruiu]

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

How?

[zturner]

In MsfBuilder::build(), can you set the value of FreePageMap before returning?

lib/DebugInfo/PDB/Raw/PDBFile.cpp

52

All we really want is a simple memset though. The function is already there init_words(), it's just private.

include/llvm/DebugInfo/Msf/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_MSF_MSFCOMMON_H
 #define LLVM_DEBUGINFO_MSF_MSFCOMMON_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MathExtras.h"
 
 #include <vector>
 
 namespace llvm {
struct SuperBlock {
   support::ulittle32_t Unknown1;
   // This contains the block # of the block map.
   support::ulittle32_t BlockMapAddr;
 };
 
 struct MsfLayout {
   MsfLayout() : SB(nullptr) {}
   const SuperBlock *SB;
+  BitVector FreePageMap;
   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:

lib/DebugInfo/PDB/Raw/PDBFile.cpp

 PDBFile::~PDBFile() {}
 
 uint32_t PDBFile::getBlockSize() const { return ContainerLayout.SB->BlockSize; }
 
 uint32_t PDBFile::getFreeBlockMapBlock() const {
   return ContainerLayout.SB->FreeBlockMapBlock;
 }
 
 uint32_t PDBFile::getBlockCount() const {
   return ContainerLayout.SB->NumBlocks;
 }
 
 uint32_t PDBFile::getNumDirectoryBytes() const {
   return ContainerLayout.SB->NumDirectoryBytes;
 }
 
 uint32_t PDBFile::getBlockMapIndex() const {
   return ContainerLayout.SB->BlockMapAddr;
 }
 
 uint32_t PDBFile::getUnknown1() const { return ContainerLayout.SB->Unknown1; }
 
 uint32_t PDBFile::getNumDirectoryBlocks() const {
   return msf::bytesToBlocks(ContainerLayout.SB->NumDirectoryBytes,
Error PDBFile::setBlockData(uint32_t BlockIndex, uint32_t Offset,
                             ArrayRef<uint8_t> Data) const {
   return make_error<RawError>(raw_error_code::not_writable,
                               "PDBFile is immutable");
 }
 
 Error PDBFile::parseFileHeaders() {
   StreamReader Reader(*Buffer);
 
+  // Initialize SB.
   const msf::SuperBlock *SB = nullptr;
   if (auto EC = Reader.readObject(SB)) {
     consumeError(std::move(EC));
     return make_error<RawError>(raw_error_code::corrupt_file,
                                 "Does not contain superblock");
   }
 
   if (auto EC = msf::validateSuperBlock(*SB))
     return EC;
 
   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(getBlockSize() * 8);
+  uint64_t FPMOffset = SB->FreeBlockMapBlock * getBlockSize();
+  ArrayRef<uint8_t> FPMBlock;
+  if (auto EC = Buffer->readBytes(FPMOffset, getBlockSize(), FPMBlock))
+    return EC;
+  for (uint32_t I = 0, E = getBlockSize() * 8; I != E; ++I)
+    if (FPMBlock[I / 8] & (1 << (I % 8)))
+      ContainerLayout.FreePageMap[I] = true;
+
   Reader.setOffset(getBlockMapOffset());
   if (auto EC = Reader.readArray(ContainerLayout.DirectoryBlocks,
                                  getNumDirectoryBlocks()))
     return EC;
 
   return Error::success();
 }
 

test/DebugInfo/PDB/pdbdump-headers.test

 ; RUN: llvm-pdbdump raw -headers -tpi-records -tpi-record-bytes -module-syms \
 ; RUN:              -sym-record-bytes -publics -module-files -stream-name=/names \
 ; RUN:              -stream-summary -stream-blocks -ipi-records -ipi-record-bytes \
 ; RUN:              -section-contribs -section-map -section-headers -line-info \
-; RUN:              -tpi-hash -fpo %p/Inputs/empty.pdb | FileCheck -check-prefix=EMPTY %s
+; RUN:              -tpi-hash -fpo -fpm %p/Inputs/empty.pdb | FileCheck -check-prefix=EMPTY %s
 ; RUN: llvm-pdbdump raw -all %p/Inputs/empty.pdb | FileCheck -check-prefix=ALL %s
 ; RUN: llvm-pdbdump raw -headers -stream-name=/names -modules -module-files \
 ; RUN:              %p/Inputs/big-read.pdb | FileCheck -check-prefix=BIG %s
 ; RUN: not llvm-pdbdump raw -headers %p/Inputs/bad-block-size.pdb 2>&1 | FileCheck -check-prefix=BAD-BLOCK-SIZE %s
 
 ; EMPTY:      FileHeaders {
 ; EMPTY-NEXT:   BlockSize: 4096
 ; EMPTY-NEXT:   FreeBlockMap: 2

 ; EMPTY-NEXT:   Stream 10: [Section Header Data] (160 bytes)
 ; EMPTY-NEXT:   Stream 11: [New FPO Data] (32 bytes)
 ; EMPTY-NEXT:   Stream 12: [Module "d:\src\llvm\test\DebugInfo\PDB\Inputs\empty.obj"] (308 bytes)
 ; EMPTY-NEXT:   Stream 13: [Named Stream "/names"] (239 bytes)
 ; EMPTY-NEXT:   Stream 14: [Module "* Linker *"] (520 bytes)
 ; EMPTY-NEXT:   Stream 15: [TPI Hash] (308 bytes)
 ; EMPTY-NEXT:   Stream 16: [IPI Hash] (68 bytes)
 ; EMPTY-NEXT: ]
+; EMPTY-NEXT: Used Page Map: [0, 1, 2, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
 ; EMPTY-NEXT: StreamBlocks [
 ; EMPTY-NEXT:   Stream 0: [8]
 ; EMPTY-NEXT:   Stream 1: [19]
 ; EMPTY-NEXT:   Stream 2: [18, 17]
 ; EMPTY-NEXT:   Stream 3: [14]
 ; EMPTY-NEXT:   Stream 4: [20]
 ; EMPTY-NEXT:   Stream 5: []
 ; EMPTY-NEXT:   Stream 6: [11]

 ; ALL:   Stream 10: [Section Header Data] (160 bytes)
 ; ALL:   Stream 11: [New FPO Data] (32 bytes)
 ; ALL:   Stream 12: [Module "d:\src\llvm\test\DebugInfo\PDB\Inputs\empty.obj"] (308 bytes)
 ; ALL:   Stream 13: [Named Stream "/names"] (239 bytes)
 ; ALL:   Stream 14: [Module "* Linker *"] (520 bytes)
 ; ALL:   Stream 15: [TPI Hash] (308 bytes)
 ; ALL:   Stream 16: [IPI Hash] (68 bytes)
 ; ALL: ]
+; ALL: Used Page Map: [0, 1, 2, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
 ; ALL: StreamBlocks [
 ; ALL:   Stream 0: [8]
 ; ALL:   Stream 1: [19]
 ; ALL:   Stream 2: [18, 17]
 ; ALL:   Stream 3: [14]
 ; ALL:   Stream 4: [20]
 ; ALL:   Stream 5: []
 ; ALL:   Stream 6: [11]

tools/llvm-pdbdump/LLVMOutputStyle.h

 public:
   LLVMOutputStyle(PDBFile &File);
 
   Error dump() override;
 
 private:
   Error dumpFileHeaders();
   Error dumpStreamSummary();
+  Error dumpFreePageMap();
   Error dumpStreamBlocks();
   Error dumpStreamData();
   Error dumpInfoStream();
   Error dumpNamedStream();
   Error dumpTpiStream(uint32_t StreamIdx);
   Error dumpDbiStream();
   Error dumpSectionContribs();
   Error dumpSectionMap();

tools/llvm-pdbdump/LLVMOutputStyle.cpp

 
 Error LLVMOutputStyle::dump() {
   if (auto EC = dumpFileHeaders())
     return EC;
 
   if (auto EC = dumpStreamSummary())
     return EC;
 
+  if (auto EC = dumpFreePageMap())
+    return EC;
+
   if (auto EC = dumpStreamBlocks())
     return EC;
 
   if (auto EC = dumpStreamData())
     return EC;
 
   if (auto EC = dumpInfoStream())
     return EC;
if (!Ipi)
     consumeError(Ipi.takeError());
   if (!Info)
     consumeError(Info.takeError());
 
   P.flush();
   return Error::success();
 }
 
+Error LLVMOutputStyle::dumpFreePageMap() {
+  if (!opts::raw::DumpFreePageMap)
+    return Error::success();
+  const BitVector &FPM = File.getMsfLayout().FreePageMap;
+
+  std::vector<uint32_t> Vec;
+  for (uint32_t I = 0, E = FPM.size(); I != E; ++I)
+    if (!FPM[I])
+      Vec.push_back(I);
+
+  // Prints out used pages instead of free pages because
+  // the number of free pages is far larger than used pages.
+  P.printList("Used Page Map", Vec);
+  return Error::success();
+}
+
 Error LLVMOutputStyle::dumpStreamBlocks() {
   if (!opts::raw::DumpStreamBlocks)
     return Error::success();
 
   ListScope L(P, "StreamBlocks");
   uint32_t StreamCount = File.getNumStreams();
   for (uint32_t StreamIdx = 0; StreamIdx < StreamCount; ++StreamIdx) {
     std::string Name("Stream ");

tools/llvm-pdbdump/llvm-pdbdump.h

 extern llvm::cl::list<std::string> IncludeSymbols;
 extern llvm::cl::list<std::string> IncludeCompilands;
 }
 
 namespace raw {
 extern llvm::cl::opt<bool> DumpHeaders;
 extern llvm::cl::opt<bool> DumpStreamBlocks;
 extern llvm::cl::opt<bool> DumpStreamSummary;
+extern llvm::cl::opt<bool> DumpFreePageMap;
 extern llvm::cl::opt<bool> DumpTpiHash;
 extern llvm::cl::opt<bool> DumpTpiRecordBytes;
 extern llvm::cl::opt<bool> DumpTpiRecords;
 extern llvm::cl::opt<bool> DumpIpiRecords;
 extern llvm::cl::opt<bool> DumpIpiRecordBytes;
 extern llvm::cl::opt<std::string> DumpStreamDataIdx;
 extern llvm::cl::opt<std::string> DumpStreamDataName;
 extern llvm::cl::opt<bool> DumpModules;

tools/llvm-pdbdump/llvm-pdbdump.cpp

 cl::opt<bool> DumpHeaders("headers", cl::desc("dump PDB headers"),
                           cl::cat(MsfOptions), cl::sub(RawSubcommand));
 cl::opt<bool> DumpStreamBlocks("stream-blocks",
                                cl::desc("dump PDB stream blocks"),
                                cl::cat(MsfOptions), cl::sub(RawSubcommand));
 cl::opt<bool> DumpStreamSummary("stream-summary",
                                 cl::desc("dump summary of the PDB streams"),
                                 cl::cat(MsfOptions), cl::sub(RawSubcommand));
+cl::opt<bool> DumpFreePageMap("fpm", cl::desc("dump free page bitmap"),
+                              cl::cat(MsfOptions), cl::sub(RawSubcommand));
 
 // TYPE OPTIONS
 cl::opt<bool>
     DumpTpiRecords("tpi-records",
                    cl::desc("dump CodeView type records from TPI stream"),
                    cl::cat(TypeOptions), cl::sub(RawSubcommand));
 cl::opt<bool> DumpTpiRecordBytes(
     "tpi-record-bytes",
int main(int argc_, const char *argv_[]) {
   if ((opts::PdbToYamlSubcommand || opts::RawSubcommand) && opts::raw::RawAll) {
     opts::raw::DumpHeaders = true;
     opts::raw::DumpModules = true;
     opts::raw::DumpModuleFiles = true;
     opts::raw::DumpModuleSyms = true;
     opts::raw::DumpPublics = true;
     opts::raw::DumpSectionHeaders = true;
     opts::raw::DumpStreamSummary = true;
+    opts::raw::DumpFreePageMap = true;
     opts::raw::DumpStreamBlocks = true;
     opts::raw::DumpTpiRecords = true;
     opts::raw::DumpTpiHash = true;
     opts::raw::DumpIpiRecords = true;
     opts::raw::DumpSectionMap = true;
     opts::raw::DumpSectionContribs = true;
     opts::raw::DumpLineInfo = true;
     opts::raw::DumpFpo = true;