[pdb] Don't verify TPI hash values up front

[zturner]

Summary

Verifying the hash values requires iterating every type record before the user even tries to access the first type record.

In the dumper, for example, this leads to all records being iterated twice. Once to verify the hashes, which the dumper has no control over, and again to actually dump them. It's expensive twice because each instance deserializes the entire record from scratch. In a large PDB file I tested with, I gave up after 5 minutes of just trying to verify hashes, and it hadn't even finished the first loop yet.

If we raise the verification outside of the TpiStream class and leave it up to the user, we can just add the TpiHashVerifier visitor to the same pipeline, so they can be verified at the same time as we dump them, with only a single walk of the type list.

This still won't address the fact that even doing it once is slow, but at least it reduces the number of full O(n) scans of the type record list from 2 to 1.

llvm/include/llvm/DebugInfo/PDB/Native/TpiStream.h

TpiStream(const PDBFile &File,
             std::unique_ptr<msf::MappedBlockStream> Stream);
   ~TpiStream();
   Error reload();
 
   PdbRaw_TpiVer getTpiVersion() const;
 
   uint32_t TypeIndexBegin() const;
   uint32_t TypeIndexEnd() const;
-  uint32_t NumTypeRecords() const;
+  uint32_t getNumTypeRecords() const;
   uint16_t getTypeHashStreamIndex() const;
   uint16_t getTypeHashStreamAuxIndex() const;
 
   uint32_t getHashKeySize() const;
-  uint32_t NumHashBuckets() const;
+  uint32_t getNumHashBuckets() const;
   FixedStreamArray<support::ulittle32_t> getHashValues() const;
   FixedStreamArray<TypeIndexOffset> getTypeIndexOffsets() const;
   HashTable &getHashAdjusters();
 
   codeview::CVTypeRange types(bool *HadError) const;
 
   Error commit();
 
 private:
-  Error verifyHashValues();
-
   const PDBFile &Pdb;
   std::unique_ptr<msf::MappedBlockStream> Stream;
 
   codeview::CVTypeArray TypeRecords;
 
   std::unique_ptr<BinaryStream> HashStream;
   FixedStreamArray<support::ulittle32_t> HashValues;
   FixedStreamArray<TypeIndexOffset> TypeIndexOffsets;
   HashTable HashAdjusters;
 
   const TpiStreamHeader *Header;
 };
 }
 }
 
 #endif

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

 using namespace llvm::pdb;
 
 TpiStream::TpiStream(const PDBFile &File,
                      std::unique_ptr<MappedBlockStream> Stream)
     : Pdb(File), Stream(std::move(Stream)) {}
 
 TpiStream::~TpiStream() = default;
 
-// Verifies that a given type record matches with a given hash value.
-// Currently we only verify SRC_LINE records.
-Error TpiStream::verifyHashValues() {
-  TpiHashVerifier Verifier(HashValues, Header->NumHashBuckets);
-  TypeDeserializer Deserializer;
-
-  TypeVisitorCallbackPipeline Pipeline;
-  Pipeline.addCallbackToPipeline(Deserializer);
-  Pipeline.addCallbackToPipeline(Verifier);
-
-  CVTypeVisitor Visitor(Pipeline);
-  return Visitor.visitTypeStream(TypeRecords);
-}
-
 Error TpiStream::reload() {
   BinaryStreamReader Reader(*Stream);
 
   if (Reader.bytesRemaining() < sizeof(TpiStreamHeader))
     return make_error<RawError>(raw_error_code::corrupt_file,
                                 "TPI Stream does not contain a header.");
 
   if (Reader.readObject(Header))
if (Header->HashStreamIndex != kInvalidStreamIndex) {
 
     auto HS = MappedBlockStream::createIndexedStream(
         Pdb.getMsfLayout(), Pdb.getMsfBuffer(), Header->HashStreamIndex);
     BinaryStreamReader HSR(*HS);
 
     // There should be a hash value for every type record, or no hashes at all.
     uint32_t NumHashValues =
         Header->HashValueBuffer.Length / sizeof(ulittle32_t);
-    if (NumHashValues != NumTypeRecords() && NumHashValues != 0)
+    if (NumHashValues != getNumTypeRecords() && NumHashValues != 0)
       return make_error<RawError>(
           raw_error_code::corrupt_file,
           "TPI hash count does not match with the number of type records.");
     HSR.setOffset(Header->HashValueBuffer.Off);
     if (auto EC = HSR.readArray(HashValues, NumHashValues))
       return EC;
     std::vector<ulittle32_t> HashValueList;
     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);
       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 (NumHashValues > 0)
-      if (auto EC = verifyHashValues())
-        return EC;
   }
 
   return Error::success();
 }
 
 PdbRaw_TpiVer TpiStream::getTpiVersion() const {
   uint32_t Value = Header->Version;
   return static_cast<PdbRaw_TpiVer>(Value);
 }
 
 uint32_t TpiStream::TypeIndexBegin() const { return Header->TypeIndexBegin; }
 
 uint32_t TpiStream::TypeIndexEnd() const { return Header->TypeIndexEnd; }
 
-uint32_t TpiStream::NumTypeRecords() const {
+uint32_t TpiStream::getNumTypeRecords() const {
   return TypeIndexEnd() - TypeIndexBegin();
 }
 
 uint16_t TpiStream::getTypeHashStreamIndex() const {
   return Header->HashStreamIndex;
 }
 
 uint16_t TpiStream::getTypeHashStreamAuxIndex() const {
   return Header->HashAuxStreamIndex;
 }
 
-uint32_t TpiStream::NumHashBuckets() const { return Header->NumHashBuckets; }
+uint32_t TpiStream::getNumHashBuckets() const { return Header->NumHashBuckets; }
 uint32_t TpiStream::getHashKeySize() const { return Header->HashKeySize; }
 
 FixedStreamArray<support::ulittle32_t> TpiStream::getHashValues() const {
   return HashValues;
 }
 
 FixedStreamArray<TypeIndexOffset> TpiStream::getTypeIndexOffsets() const {
   return TypeIndexOffsets;

llvm/tools/llvm-pdbdump/LLVMOutputStyle.cpp

 #include "llvm/DebugInfo/PDB/Native/EnumTables.h"
 #include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
 #include "llvm/DebugInfo/PDB/Native/ISectionContribVisitor.h"
 #include "llvm/DebugInfo/PDB/Native/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Native/ModuleDebugStream.h"
 #include "llvm/DebugInfo/PDB/Native/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Native/PublicsStream.h"
 #include "llvm/DebugInfo/PDB/Native/RawError.h"
+#include "llvm/DebugInfo/PDB/Native/TpiHashing.h"
 #include "llvm/DebugInfo/PDB/Native/TpiStream.h"
 #include "llvm/DebugInfo/PDB/PDBExtras.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/FormatVariadic.h"
 
 #include <unordered_map>
 
Error LLVMOutputStyle::dumpTpiStream(uint32_t StreamIdx) {
   if (!Tpi)
     return Tpi.takeError();
 
   std::unique_ptr<DictScope> StreamScope;
   std::unique_ptr<ListScope> RecordScope;
 
   StreamScope = llvm::make_unique<DictScope>(P, Label);
   P.printNumber(VerLabel, Tpi->getTpiVersion());
-  P.printNumber("Record count", Tpi->NumTypeRecords());
+  P.printNumber("Record count", Tpi->getNumTypeRecords());
 
   Optional<TypeDatabase> &StreamDB = (StreamIdx == StreamTPI) ? TypeDB : ItemDB;
 
   std::vector<std::unique_ptr<TypeVisitorCallbacks>> Visitors;
 
   Visitors.push_back(make_unique<TypeDeserializer>());
   if (!StreamDB.hasValue()) {
     StreamDB.emplace();
for (auto Type : Tpi->types(&HadError)) {
     T.setIndex(T.getIndex() + 1);
   }
   if (HadError)
     return make_error<RawError>(raw_error_code::corrupt_file,
                                 "TPI stream contained corrupt record");
 
   if (DumpTpiHash) {
     DictScope DD(P, "Hash");
-    P.printNumber("Number of Hash Buckets", Tpi->NumHashBuckets());
+    P.printNumber("Number of Hash Buckets", Tpi->getNumHashBuckets());
     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;
Error LLVMOutputStyle::buildTypeDatabase(uint32_t SN) {
 
   auto &DB = (SN == StreamIPI) ? ItemDB : TypeDB;
 
   if (DB.hasValue())
     return Error::success();
 
   DB.emplace();
 
+  auto Tpi =
+      (SN == StreamTPI) ? File.getPDBTpiStream() : File.getPDBIpiStream();
+
+  if (!Tpi)
+    return Tpi.takeError();
+
   TypeVisitorCallbackPipeline Pipeline;
   TypeDeserializer Deserializer;
   TypeDatabaseVisitor DBV(*DB);
   Pipeline.addCallbackToPipeline(Deserializer);
   Pipeline.addCallbackToPipeline(DBV);
 
-  auto Tpi =
-      (SN == StreamTPI) ? File.getPDBTpiStream() : File.getPDBIpiStream();
-  if (!Tpi)
-    return Tpi.takeError();
+  auto HashValues = Tpi->getHashValues();
+  std::unique_ptr<TpiHashVerifier> HashVerifier;
+  if (!HashValues.empty()) {
+    HashVerifier =
+        make_unique<TpiHashVerifier>(HashValues, Tpi->getNumHashBuckets());
+    Pipeline.addCallbackToPipeline(*HashVerifier);
+  }
 
   CVTypeVisitor Visitor(Pipeline);
   return Visitor.visitTypeStream(Tpi->types(nullptr));
 }
 
 Error LLVMOutputStyle::dumpDbiStream() {
   bool DumpModules = opts::raw::DumpModules || opts::raw::DumpModuleSyms ||
                      opts::raw::DumpModuleFiles || opts::raw::DumpLineInfo;