[pdb] Correctly parse hash adjusters table

[zturner]

Summary

This is not a list of pairs, it is a hash table data structure. We now correctly parse this out. It's hard to write a test for this, because doing so would require we have a PDB with hash adjusters, and they are only generated in the case of collisions, which typically require a very large PDB.

I plan to do some follow-up analysis and see if I can manually create some types that will collide by examining the collisions of a large PDB and carefully choosing some types. If that is successful, I can construct a minimal PDB with collisions and add a test case for them. In the meantime, here is a sample of the output when run against a very large PDB that does have collisions.

Adjusters [
  {
    Type: llvm::SmallVectorStorage<llvm::cl::OptionEnumValue,4>
    TI: 0x4DBA
  }
  {
    Type: llvm::SmallVectorStorage<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,2>
    TI: 0x3C97
  }
  {
    Type: llvm::SmallVectorTemplateCommon<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,void>
    TI: 0x3D12
  }
  {
    Type: llvm::SmallVectorStorage<char,32>
    TI: 0x4305
  }
  {
    Type: llvm::ErrorOr<llvm::sys::fs::space_info>
    TI: 0x4302
  }
  {
    Type: llvm::SmallVectorStorage<char,260>
    TI: 0x30D0
  }
  {
    Type: llvm::SmallVectorStorage<void *,4>
    TI: 0x46FC
  }
  {
    Type: llvm::SmallVectorTemplateCommon<wchar_t,void>
    TI: 0x2E90
  }
  {
    Type: llvm::SmallVectorStorage<char,64>
    TI: 0x30A6
  }

[inglorion]

lgtm. Let's get this in and revisit testing once we have a better understanding of what the adjusters are used for.

[ruiu]

LGTM

llvm/trunk/include/llvm/DebugInfo/PDB/Raw/TpiStream.h

 //===- TpiStream.cpp - PDB Type Info (TPI) Stream 2 Access ------*- 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_PDBTPISTREAM_H
 #define LLVM_DEBUGINFO_PDB_RAW_PDBTPISTREAM_H
 
 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
 #include "llvm/DebugInfo/MSF/StreamArray.h"
 #include "llvm/DebugInfo/PDB/PDBTypes.h"
+#include "llvm/DebugInfo/PDB/Raw/HashTable.h"
 #include "llvm/DebugInfo/PDB/Raw/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Raw/RawTypes.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 namespace msf {
public:
   uint32_t NumTypeRecords() const;
   uint16_t getTypeHashStreamIndex() const;
   uint16_t getTypeHashStreamAuxIndex() const;
 
   uint32_t getHashKeySize() const;
   uint32_t NumHashBuckets() const;
   msf::FixedStreamArray<support::ulittle32_t> getHashValues() const;
   msf::FixedStreamArray<TypeIndexOffset> getTypeIndexOffsets() const;
-  msf::FixedStreamArray<TypeIndexOffset> getHashAdjustments() const;
+  HashTable &getHashAdjusters();
 
   iterator_range<codeview::CVTypeArray::Iterator> types(bool *HadError) const;
 
   Error commit();
 
 private:
   Error verifyHashValues();
 
   const PDBFile &Pdb;
   std::unique_ptr<msf::MappedBlockStream> Stream;
 
   codeview::CVTypeArray TypeRecords;
 
   std::unique_ptr<msf::ReadableStream> HashStream;
   msf::FixedStreamArray<support::ulittle32_t> HashValues;
   msf::FixedStreamArray<TypeIndexOffset> TypeIndexOffsets;
-  msf::FixedStreamArray<TypeIndexOffset> HashAdjustments;
+  HashTable HashAdjusters;
 
   const TpiStreamHeader *Header;
 };
 }
 }
 
 #endif

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

for (auto I : HashValues)
       HashValueList.push_back(I);
 
     HSR.setOffset(Header->IndexOffsetBuffer.Off);
     uint32_t NumTypeIndexOffsets =
         Header->IndexOffsetBuffer.Length / sizeof(TypeIndexOffset);
     if (auto EC = HSR.readArray(TypeIndexOffsets, NumTypeIndexOffsets))
       return EC;
 
+    if (Header->HashAdjBuffer.Length > 0) {
       HSR.setOffset(Header->HashAdjBuffer.Off);
-    uint32_t NumHashAdjustments =
-        Header->HashAdjBuffer.Length / sizeof(TypeIndexOffset);
-    if (auto EC = HSR.readArray(HashAdjustments, NumHashAdjustments))
+      if (auto EC = HashAdjusters.load(HSR))
         return EC;
+    }
 
     HashStream = std::move(HS);
 
     // TPI hash table is a parallel array for the type records.
     // Verify that the hash values match with type records.
     if (auto EC = verifyHashValues())
       return EC;
   }
TpiStream::getHashValues() const {
   return HashValues;
 }
 
 FixedStreamArray<TypeIndexOffset>
 TpiStream::getTypeIndexOffsets() const {
   return TypeIndexOffsets;
 }
 
-FixedStreamArray<TypeIndexOffset>
-TpiStream::getHashAdjustments() const {
-  return HashAdjustments;
-}
+HashTable &TpiStream::getHashAdjusters() { return HashAdjusters; }
 
 iterator_range<CVTypeArray::Iterator>
 TpiStream::types(bool *HadError) const {
   return make_range(TypeRecords.begin(HadError), TypeRecords.end());
 }
 
 Error TpiStream::commit() { return Error::success(); }

llvm/trunk/test/DebugInfo/PDB/pdbdump-headers.test

 ; EMPTY-NEXT:         0030: 04006E65 75747261 6C00F2F1 02150300  |..neutral.......|
 ; EMPTY-NEXT:         0040: 0500626F 746800F1                    |..both..|
 ; EMPTY-NEXT:       )
 ; EMPTY-NEXT:     }
 ; EMPTY:          Hash {
 ; EMPTY-NEXT:       Number of Hash Buckets: 262143
 ; EMPTY-NEXT:       Hash Key Size: 4
 ; EMPTY-NEXT:       Values: [205956, 163561, 59811, 208239, 16377, 247078, 194342, 254156, 194536, 167492, 185421, 119540, 261871, 198119, 48056, 251486, 134580, 148190, 113636, 53336, 55779, 220695, 198114, 148734, 81128, 60158, 217249, 174209, 159978, 249504, 141941, 238785, 6214, 94935, 151449, 135589, 73373, 96512, 254299, 17744, 239514, 173189, 130544, 204437, 238560, 144673, 115151, 197306, 256035, 101096, 231280, 52156, 48854, 170035, 177041, 102745, 16947, 183703, 98548, 35693, 171328, 203640, 139292, 49018, 43821, 202555, 165040, 215835, 142625, 52534, 44186, 103930, 110942, 17991, 213215]
-; EMPTY-NEXT:       Type Index Offsets: [{4096, 0}]
 ; EMPTY-NEXT:       Hash Adjustments: []
 ; EMPTY-NEXT:     }
+; EMPTY-NEXT:     TypeIndexOffsets [
+; EMPTY-NEXT:       Index: 0x1000, Offset: 0
+; EMPTY-NEXT:     ]
 ; EMPTY:        Type Info Stream (IPI) {
 ; EMPTY-NEXT:     IPI Version: 20040203
 ; EMPTY-NEXT:     Record count: 15
 ; EMPTY-NEXT:     Records [
 ; EMPTY-NEXT:       {
 ; EMPTY-NEXT:         UdtModSourceLine (0x104B) {
 ; EMPTY-NEXT:           TypeLeafKind: LF_UDT_MOD_SRC_LINE (0x1607)
 ; EMPTY-NEXT:           UDT: __vc_attributes::threadingAttribute (0x100B)

 ; EMPTY-NEXT:           SourceFile: <unknown simple type> (0x1)
 ; EMPTY-NEXT:           LineNumber: 108
 ; EMPTY-NEXT:           Module: 1
 ; EMPTY-NEXT:         }
 ; EMPTY-NEXT:         Bytes (
 ; EMPTY-NEXT:           0000: 42100000 01000000 6C000000 0100F2F1  |B.......l.......|
 ; EMPTY-NEXT:         )
 ; EMPTY-NEXT:       }
-; EMPTY:          Hash {
-; EMPTY-NEXT:       Number of Hash Buckets: 262143
-; EMPTY-NEXT:       Hash Key Size: 4
-; EMPTY-NEXT:       Values: [7186, 7198, 7180, 7191, 7201, 7241, 7249, 80727, 154177, 75189, 253662, 193467, 222705, 186099, 257108]
-; EMPTY-NEXT:       Type Index Offsets: [{4096, 0}]
-; EMPTY-NEXT:       Hash Adjustments: []
-; EMPTY-NEXT:     }
+; EMPTY:          TypeIndexOffsets [
+; EMPTY-NEXT:       Index: 0x1000, Offset: 0
+; EMPTY-NEXT:     ]
 ; EMPTY:      DBI Stream {
 ; EMPTY-NEXT:   Dbi Version: 19990903
 ; EMPTY-NEXT:   Age: 1
 ; EMPTY-NEXT:   Incremental Linking: Yes
 ; EMPTY-NEXT:   Has CTypes: No
 ; EMPTY-NEXT:   Is Stripped: No
 ; EMPTY-NEXT:   Machine Type: x86
 ; EMPTY-NEXT:   Symbol Record Stream Index: 8

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

Error LLVMOutputStyle::dumpInfoStream() {
   return Error::success();
 }
 
 static void printTypeIndexOffset(raw_ostream &OS,
                                  const TypeIndexOffset &TIOff) {
   OS << "{" << TIOff.Type.getIndex() << ", " << TIOff.Offset << "}";
 }
 
-static void dumpTpiHash(ScopedPrinter &P, TpiStream &Tpi) {
-  if (!opts::raw::DumpTpiHash)
-    return;
-  DictScope DD(P, "Hash");
-  P.printNumber("Number of Hash Buckets", Tpi.NumHashBuckets());
-  P.printNumber("Hash Key Size", Tpi.getHashKeySize());
-  P.printList("Values", Tpi.getHashValues());
-  P.printList("Type Index Offsets", Tpi.getTypeIndexOffsets(),
-              printTypeIndexOffset);
-  P.printList("Hash Adjustments", Tpi.getHashAdjustments(),
-              printTypeIndexOffset);
+namespace {
+class RecordBytesVisitor : public TypeVisitorCallbacks {
+public:
+  explicit RecordBytesVisitor(ScopedPrinter &P) : P(P) {}
+
+  Error visitTypeEnd(CVType &Record) override {
+    P.printBinaryBlock("Bytes", Record.content());
+    return Error::success();
+  }
+
+private:
+  ScopedPrinter &P;
+};
 }
 
 Error LLVMOutputStyle::dumpTpiStream(uint32_t StreamIdx) {
   assert(StreamIdx == StreamTPI || StreamIdx == StreamIPI);
 
   bool DumpRecordBytes = false;
   bool DumpRecords = false;
+  bool DumpTpiHash = false;
   StringRef Label;
   StringRef VerLabel;
   if (StreamIdx == StreamTPI) {
     if (!File.hasPDBTpiStream()) {
       P.printString("Type Info Stream (TPI) not present");
       return Error::success();
     }
     DumpRecordBytes = opts::raw::DumpTpiRecordBytes;
     DumpRecords = opts::raw::DumpTpiRecords;
+    DumpTpiHash = opts::raw::DumpTpiHash;
     Label = "Type Info Stream (TPI)";
     VerLabel = "TPI Version";
   } else if (StreamIdx == StreamIPI) {
     if (!File.hasPDBIpiStream()) {
       P.printString("Type Info Stream (IPI) not present");
       return Error::success();
     }
     DumpRecordBytes = opts::raw::DumpIpiRecordBytes;
     DumpRecords = opts::raw::DumpIpiRecords;
     Label = "Type Info Stream (IPI)";
     VerLabel = "IPI Version";
   }
-  if (!DumpRecordBytes && !DumpRecords && !opts::raw::DumpModuleSyms)
+  if (!DumpRecordBytes && !DumpRecords && !DumpTpiHash &&
+      !opts::raw::DumpModuleSyms)
     return Error::success();
 
+  bool IsSilentDatabaseBuild = !DumpRecordBytes && !DumpRecords && !DumpTpiHash;
+
   auto Tpi = (StreamIdx == StreamTPI) ? File.getPDBTpiStream()
                                       : File.getPDBIpiStream();
   if (!Tpi)
     return Tpi.takeError();
 
-  // Even if the user doesn't want to dump type records, we still need to
-  // iterate them in order to build the type database. So when they want to
-  // dump symbols but not types, don't stick a dumper on the end, just build
-  // the type database.
+  std::unique_ptr<DictScope> StreamScope;
+  std::unique_ptr<ListScope> RecordScope;
+
+  if (!IsSilentDatabaseBuild) {
+    StreamScope = llvm::make_unique<DictScope>(P, Label);
+    P.printNumber(VerLabel, Tpi->getTpiVersion());
+    P.printNumber("Record count", Tpi->NumTypeRecords());
+  }
+
   TypeDatabaseVisitor DBV(TypeDB);
   CompactTypeDumpVisitor CTDV(TypeDB, &P);
   TypeDumpVisitor TDV(TypeDB, &P, false);
+  RecordBytesVisitor RBV(P);
   TypeDeserializer Deserializer;
+
+  // We always need to deserialize and add it to the type database.  This is
+  // true if even if we're not dumping anything, because we could need the
+  // type database for the purposes of dumping symbols.
   TypeVisitorCallbackPipeline Pipeline;
   Pipeline.addCallbackToPipeline(Deserializer);
   Pipeline.addCallbackToPipeline(DBV);
 
-  CVTypeVisitor Visitor(Pipeline);
-
-  if (DumpRecords || DumpRecordBytes) {
-    DictScope D(P, Label);
-
-    P.printNumber(VerLabel, Tpi->getTpiVersion());
-    P.printNumber("Record count", Tpi->NumTypeRecords());
-    ListScope L(P, "Records");
-
-    bool HadError = false;
+  // If we're in dump mode, add a dumper with the appropriate detail level.
+  if (DumpRecords) {
     if (opts::raw::CompactRecords)
       Pipeline.addCallbackToPipeline(CTDV);
     else
       Pipeline.addCallbackToPipeline(TDV);
+  }
+  if (DumpRecordBytes)
+    Pipeline.addCallbackToPipeline(RBV);
 
-    for (auto Type : Tpi->types(&HadError)) {
-      std::unique_ptr<DictScope> Scope;
-      if (!opts::raw::CompactRecords)
-        Scope.reset(new DictScope(P, ""));
+  CVTypeVisitor Visitor(Pipeline);
+
+  if (DumpRecords || DumpRecordBytes)
+    RecordScope = llvm::make_unique<ListScope>(P, "Records");
+
+  bool HadError = false;
+
+  TypeIndex T(TypeIndex::FirstNonSimpleIndex);
+    std::unique_ptr<DictScope> OneRecordScope;
+
+    if ((DumpRecords || DumpRecordBytes) && !opts::raw::CompactRecords)
+      OneRecordScope = llvm::make_unique<DictScope>(P, "");
 
-      if (DumpRecords) {
-        if (auto EC = Visitor.visitTypeRecord(Type))
-          return EC;
-      }
-
-      if (DumpRecordBytes)
-        P.printBinaryBlock("Bytes", Type.content());
-    }
-    dumpTpiHash(P, *Tpi);
-    if (HadError)
-      return make_error<RawError>(raw_error_code::corrupt_file,
-                                  "TPI stream contained corrupt record");
-    {
-      ListScope L(P, "TypeIndexOffsets");
-      for (const auto &IO : Tpi->getTypeIndexOffsets()) {
-        P.printString(formatv("Index: {0:x}, Offset: {1:N}", IO.Type.getIndex(),
-                              (uint32_t)IO.Offset)
-                          .str());
-      }
-    }
+
+  if (DumpTpiHash) {
+    DictScope DD(P, "Hash");
+    P.printNumber("Number of Hash Buckets", Tpi->NumHashBuckets());
+    P.printNumber("Hash Key Size", Tpi->getHashKeySize());
+    P.printList("Values", Tpi->getHashValues());
+
+    ListScope LHA(P, "Adjusters");
+    auto ExpectedST = File.getStringTable();
+    if (!ExpectedST)
+      return ExpectedST.takeError();
+    const auto &ST = *ExpectedST;
+    for (const auto &E : Tpi->getHashAdjusters()) {
+      DictScope DHA(P);
+      StringRef Name = ST.getStringForID(E.first);
+      P.printString("Type", Name);
+      P.printHex("TI", E.second);
+    }
+  }
+
+  if (!IsSilentDatabaseBuild) {
 
-  } else if (opts::raw::DumpModuleSyms) {
-
-    bool HadError = false;
-    for (auto Type : Tpi->types(&HadError)) {
-      if (auto EC = Visitor.visitTypeRecord(Type))
-        return EC;
-    }
-
-    dumpTpiHash(P, *Tpi);
-    if (HadError)
-      return make_error<RawError>(raw_error_code::corrupt_file,
-                                  "TPI stream contained corrupt record");
-  }
   P.flush();
   return Error::success();
 }
 
 Error LLVMOutputStyle::dumpDbiStream() {
   bool DumpModules = opts::raw::DumpModules || opts::raw::DumpModuleSyms ||
                      opts::raw::DumpModuleFiles || opts::raw::DumpLineInfo;
   if (!opts::raw::DumpHeaders && !DumpModules)