[PDB] Make our PDBs look more like MS PDBs.

When investigating bugs in PDB generation, the first step is
often to do the same link with link.exe and then compare PDBs.

But comparing PDBs is hard because two completely different byte
sequences can both be correct, so it hampers the investigation when
you also have to spend time figuring out not just which bytes are
different, but also if the difference is meaningful.

This patch fixes a couple of cases related to string table emission,
hash table emission, and the order in which we emit strings that
makes more of our bytes the same as the bytes generated by MS PDBs.

Differential Revision: https://reviews.llvm.org/D44810

llvm-svn: 328348

7 files changed, 146 insertions, 47 deletions

diff --git a/llvm/lib/DebugInfo/CodeView/DebugStringTableSubsection.cpp b/llvm/lib/DebugInfo/CodeView/DebugStringTableSubsection.cpp
index c731b68625c..127868005de 100644
--- a/llvm/lib/DebugInfo/CodeView/DebugStringTableSubsection.cpp
+++ b/llvm/lib/DebugInfo/CodeView/DebugStringTableSubsection.cpp
@@ -86,6 +86,15 @@ Error DebugStringTableSubsection::commit(BinaryStreamWriter &Writer) const {
 
 uint32_t DebugStringTableSubsection::size() const { return StringToId.size(); }
 
+std::vector<uint32_t> DebugStringTableSubsection::sortedIds() const {
+  std::vector<uint32_t> Result;
+  Result.reserve(IdToString.size());
+  for (const auto &Entry : IdToString)
+    Result.push_back(Entry.first);
+  std::sort(Result.begin(), Result.end());
+  return Result;
+}
+
 uint32_t DebugStringTableSubsection::getIdForString(StringRef S) const {
   auto Iter = StringToId.find(S);
   assert(Iter != StringToId.end());
diff --git a/llvm/lib/DebugInfo/PDB/Native/DbiStreamBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/DbiStreamBuilder.cpp
index c96553ff9b1..f17e0815ccf 100644
--- a/llvm/lib/DebugInfo/PDB/Native/DbiStreamBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/DbiStreamBuilder.cpp
@@ -27,7 +27,7 @@ using namespace llvm::pdb;
 DbiStreamBuilder::DbiStreamBuilder(msf::MSFBuilder &Msf)
     : Msf(Msf), Allocator(Msf.getAllocator()), Age(1), BuildNumber(0),
       PdbDllVersion(0), PdbDllRbld(0), Flags(0), MachineType(PDB_Machine::x86),
-      Header(nullptr), DbgStreams((int)DbgHeaderType::Max) {}
+      Header(nullptr) {}
 
 DbiStreamBuilder::~DbiStreamBuilder() {}
 
@@ -63,15 +63,8 @@ void DbiStreamBuilder::setPublicsStreamIndex(uint32_t Index) {
 
 Error DbiStreamBuilder::addDbgStream(pdb::DbgHeaderType Type,
                                      ArrayRef<uint8_t> Data) {
-  if (DbgStreams[(int)Type].StreamNumber != kInvalidStreamIndex)
-    return make_error<RawError>(raw_error_code::duplicate_entry,
-                                "The specified stream type already exists");
-  auto ExpectedIndex = Msf.addStream(Data.size());
-  if (!ExpectedIndex)
-    return ExpectedIndex.takeError();
-  uint32_t Index = std::move(*ExpectedIndex);
-  DbgStreams[(int)Type].Data = Data;
-  DbgStreams[(int)Type].StreamNumber = Index;
+  DbgStreams[(int)Type].emplace();
+  DbgStreams[(int)Type]->Data = Data;
   return Error::success();
 }
 
@@ -266,6 +259,15 @@ Error DbiStreamBuilder::finalize() {
 }
 
 Error DbiStreamBuilder::finalizeMsfLayout() {
+  for (auto &S : DbgStreams) {
+    if (!S.hasValue())
+      continue;
+    auto ExpectedIndex = Msf.addStream(S->Data.size());
+    if (!ExpectedIndex)
+      return ExpectedIndex.takeError();
+    S->StreamNumber = *ExpectedIndex;
+  }
+
   for (auto &MI : ModiList) {
     if (auto EC = MI->finalizeMsfLayout())
       return EC;
@@ -375,17 +377,23 @@ Error DbiStreamBuilder::commit(const msf::MSFLayout &Layout,
   if (auto EC = ECNamesBuilder.commit(Writer))
     return EC;
 
-  for (auto &Stream : DbgStreams)
-    if (auto EC = Writer.writeInteger(Stream.StreamNumber))
+  for (auto &Stream : DbgStreams) {
+    uint16_t StreamNumber = kInvalidStreamIndex;
+    if (Stream.hasValue())
+      StreamNumber = Stream->StreamNumber;
+    if (auto EC = Writer.writeInteger(StreamNumber))
       return EC;
+  }
 
   for (auto &Stream : DbgStreams) {
-    if (Stream.StreamNumber == kInvalidStreamIndex)
+    if (!Stream.hasValue())
       continue;
+    assert(Stream->StreamNumber != kInvalidStreamIndex);
+
     auto WritableStream = WritableMappedBlockStream::createIndexedStream(
-        Layout, MsfBuffer, Stream.StreamNumber, Allocator);
+        Layout, MsfBuffer, Stream->StreamNumber, Allocator);
     BinaryStreamWriter DbgStreamWriter(*WritableStream);
-    if (auto EC = DbgStreamWriter.writeArray(Stream.Data))
+    if (auto EC = DbgStreamWriter.writeArray(Stream->Data))
       return EC;
   }
 
diff --git a/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp
index e84f25dfeef..63d63c1e054 100644
--- a/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp
@@ -150,14 +150,14 @@ Error GSIStreamBuilder::finalizeMsfLayout() {
   PSH->finalizeBuckets(PSHZero);
   GSH->finalizeBuckets(GSHZero);
 
-  Expected<uint32_t> Idx = Msf.addStream(calculatePublicsHashStreamSize());
+  Expected<uint32_t> Idx = Msf.addStream(calculateGlobalsHashStreamSize());
   if (!Idx)
     return Idx.takeError();
-  PSH->StreamIndex = *Idx;
-  Idx = Msf.addStream(calculateGlobalsHashStreamSize());
+  GSH->StreamIndex = *Idx;
+  Idx = Msf.addStream(calculatePublicsHashStreamSize());
   if (!Idx)
     return Idx.takeError();
-  GSH->StreamIndex = *Idx;
+  PSH->StreamIndex = *Idx;
 
   uint32_t RecordBytes =
       GSH->calculateRecordByteSize() + PSH->calculateRecordByteSize();
diff --git a/llvm/lib/DebugInfo/PDB/Native/InfoStreamBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/InfoStreamBuilder.cpp
index a20b45111cf..54d6835f112 100644
--- a/llvm/lib/DebugInfo/PDB/Native/InfoStreamBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/InfoStreamBuilder.cpp
@@ -73,5 +73,6 @@ Error InfoStreamBuilder::commit(const msf::MSFLayout &Layout,
     if (auto EC = Writer.writeEnum(E))
       return EC;
   }
+  assert(Writer.bytesRemaining() == 0);
   return Error::success();
 }
diff --git a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
index 6076b10c5c9..a4eaed90837 100644
--- a/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/NamedStreamMap.cpp
@@ -47,7 +47,7 @@ uint32_t NamedStreamMapTraits::lookupKeyToStorageKey(StringRef S) {
 }
 
 NamedStreamMap::NamedStreamMap()
-    : HashTraits(*this), OffsetIndexMap(HashTraits) {}
+    : HashTraits(*this), OffsetIndexMap(1, HashTraits) {}
 
 Error NamedStreamMap::load(BinaryStreamReader &Stream) {
   uint32_t StringBufferSize;
diff --git a/llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
index 1cb890ff799..38bba9eb730 100644
--- a/llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp
@@ -80,11 +80,20 @@ GSIStreamBuilder &PDBFileBuilder::getGsiBuilder() {
   return *Gsi;
 }
 
-Error PDBFileBuilder::addNamedStream(StringRef Name, uint32_t Size) {
+Expected<uint32_t> PDBFileBuilder::allocateNamedStream(StringRef Name,
+                                                       uint32_t Size) {
   auto ExpectedStream = Msf->addStream(Size);
-  if (!ExpectedStream)
-    return ExpectedStream.takeError();
-  NamedStreams.set(Name, *ExpectedStream);
+  if (ExpectedStream)
+    NamedStreams.set(Name, *ExpectedStream);
+  return ExpectedStream;
+}
+
+Error PDBFileBuilder::addNamedStream(StringRef Name, StringRef Data) {
+  Expected<uint32_t> ExpectedIndex = allocateNamedStream(Name, Data.size());
+  if (!ExpectedIndex)
+    return ExpectedIndex.takeError();
+  assert(NamedStreamData.count(*ExpectedIndex) == 0);
+  NamedStreamData[*ExpectedIndex] = Data;
   return Error::success();
 }
 
@@ -101,35 +110,41 @@ Expected<msf::MSFLayout> PDBFileBuilder::finalizeMsfLayout() {
 
   uint32_t StringsLen = Strings.calculateSerializedSize();
 
-  if (auto EC = addNamedStream("/names", StringsLen))
-    return std::move(EC);
-  if (auto EC = addNamedStream("/LinkInfo", 0))
-    return std::move(EC);
+  Expected<uint32_t> SN = allocateNamedStream("/LinkInfo", 0);
+  if (!SN)
+    return SN.takeError();
 
-  if (Info) {
-    if (auto EC = Info->finalizeMsfLayout())
-      return std::move(EC);
-  }
-  if (Dbi) {
-    if (auto EC = Dbi->finalizeMsfLayout())
+  if (Gsi) {
+    if (auto EC = Gsi->finalizeMsfLayout())
       return std::move(EC);
+    if (Dbi) {
+      Dbi->setPublicsStreamIndex(Gsi->getPublicsStreamIndex());
+      Dbi->setGlobalsStreamIndex(Gsi->getGlobalsStreamIndex());
+      Dbi->setSymbolRecordStreamIndex(Gsi->getRecordStreamIdx());
+    }
   }
   if (Tpi) {
     if (auto EC = Tpi->finalizeMsfLayout())
       return std::move(EC);
   }
+  if (Dbi) {
+    if (auto EC = Dbi->finalizeMsfLayout())
+      return std::move(EC);
+  }
+  SN = allocateNamedStream("/names", StringsLen);
+  if (!SN)
+    return SN.takeError();
+
   if (Ipi) {
     if (auto EC = Ipi->finalizeMsfLayout())
       return std::move(EC);
   }
-  if (Gsi) {
-    if (auto EC = Gsi->finalizeMsfLayout())
+
+  // Do this last, since it relies on the named stream map being complete, and
+  // that can be updated by previous steps in the finalization.
+  if (Info) {
+    if (auto EC = Info->finalizeMsfLayout())
       return std::move(EC);
-    if (Dbi) {
-      Dbi->setPublicsStreamIndex(Gsi->getPublicsStreamIndex());
-      Dbi->setGlobalsStreamIndex(Gsi->getGlobalsStreamIndex());
-      Dbi->setSymbolRecordStreamIndex(Gsi->getRecordStreamIdx());
-    }
   }
 
   return Msf->build();
@@ -219,6 +234,17 @@ Error PDBFileBuilder::commit(StringRef Filename) {
   if (auto EC = Strings.commit(NSWriter))
     return EC;
 
+  for (const auto &NSE : NamedStreamData) {
+    if (NSE.second.empty())
+      continue;
+
+    auto NS = WritableMappedBlockStream::createIndexedStream(
+        Layout, Buffer, NSE.first, Allocator);
+    BinaryStreamWriter NSW(*NS);
+    if (auto EC = NSW.writeBytes(arrayRefFromStringRef(NSE.second)))
+      return EC;
+  }
+
   if (Info) {
     if (auto EC = Info->commit(Layout, Buffer))
       return EC;
diff --git a/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
index 5020423f6ff..0975d9efc39 100644
--- a/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
+++ b/llvm/lib/DebugInfo/PDB/Native/PDBStringTableBuilder.cpp
@@ -15,6 +15,8 @@
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 
+#include <map>
+
 using namespace llvm;
 using namespace llvm::msf;
 using namespace llvm::support;
@@ -33,13 +35,66 @@ StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
   return Strings.getStringForId(Id);
 }
 
+// This is a precomputed list of Buckets given the specified number of
+// strings.  Matching the reference algorithm exactly is not strictly
+// necessary for correctness, but it helps when comparing LLD's PDBs with
+// Microsoft's PDBs so as to eliminate superfluous differences.
+static std::map<uint32_t, uint32_t> StringsToBuckets = {
+    {1, 2},
+    {2, 4},
+    {4, 7},
+    {6, 11},
+    {9, 17},
+    {13, 26},
+    {20, 40},
+    {31, 61},
+    {46, 92},
+    {70, 139},
+    {105, 209},
+    {157, 314},
+    {236, 472},
+    {355, 709},
+    {532, 1064},
+    {799, 1597},
+    {1198, 2396},
+    {1798, 3595},
+    {2697, 5393},
+    {4045, 8090},
+    {6068, 12136},
+    {9103, 18205},
+    {13654, 27308},
+    {20482, 40963},
+    {30723, 61445},
+    {46084, 92168},
+    {69127, 138253},
+    {103690, 207380},
+    {155536, 311071},
+    {233304, 466607},
+    {349956, 699911},
+    {524934, 1049867},
+    {787401, 1574801},
+    {1181101, 2362202},
+    {1771652, 3543304},
+    {2657479, 5314957},
+    {3986218, 7972436},
+    {5979328, 11958655},
+    {8968992, 17937983},
+    {13453488, 26906975},
+    {20180232, 40360463},
+    {30270348, 60540695},
+    {45405522, 90811043},
+    {68108283, 136216565},
+    {102162424, 204324848},
+    {153243637, 306487273},
+    {229865455, 459730910},
+    {344798183, 689596366},
+    {517197275, 1034394550},
+    {775795913, 1551591826}};
+
 static uint32_t computeBucketCount(uint32_t NumStrings) {
-  // The /names stream is basically an on-disk open-addressing hash table.
-  // Hash collisions are resolved by linear probing. We cannot make
-  // utilization 100% because it will make the linear probing extremely
-  // slow. But lower utilization wastes disk space. As a reasonable
-  // load factor, we choose 80%. We need +1 because slot 0 is reserved.
-  return (NumStrings + 1) * 1.25;
+  auto Entry = StringsToBuckets.lower_bound(NumStrings);
+  assert(Entry != StringsToBuckets.end());
+  return Entry->second;
 }
 
 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {