[PDB] Fix hash function used to write /src/headerblock

[thakis]

Summary

lld-link used to write PDB files that DIA couldn't recover natvis
files from if:

• The global strings table was > 64kiB
• There were at least 3 natvis files

The cause was that the hash function for the /src/headerblock stream
was incorrect: It needs to be truncated to 16 bit.

If the global strings table was <= 64kiB, truncating to 16 bit is a
no-op, so this wasn't needed for small programs.

If there are only 1 or 2 natvis files, then the growth strategy in
HashTable::grow() would mean the hash table would have 2 buckets (for 1
natvis file) or 4 buckets (for 4 natvis files), and since the hash
function is used modulo number of buckets, and since 2 and 4 divide
0x10000, the missing % 0x10000 is a no-op there too. For 3 natvis
files, the hash table grows to 6 buckets, which has a factor that's not
common with 0x10000 and the difference starts to matter.

Fixes PR41626.

[zturner]

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

29–35

IIUC, this shouldn't be specific to /src/headerblock right? Because this StringTableHashTraits is used for the entire string table. This means the comment is overly specific as it's referring to /src/headerblock from code that ultimately doesn't really have anything to do with /src/headerblock.

It also means that changing this will probably affect lots of other things that are subtle and hard to test. So be on the lookout for other weird failures.

[rnk]

lgtm

Initially I thought "we should change the return type of pdb::hashStringV1, but after studying the pdb code more, I see that sometimes the full 32-bit string hash is used, and sometimes only the 16-bit hash is used. I guess we just have to be careful and truncate wherever it seems necessary.

[thomasanderson]

lgtm!

[thakis]

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

29–35

From what I understand, InjectedSourceTable is the only thing using this StringTableHashTraits: http://llvm-cs.pcc.me.uk/include/llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h/rStringTableHashTraits

Is that not the case?

[zturner]

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

29–35

If that's the case, then there's nothing to worry about. Thanks for double checking though.

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

Error load(BinaryStreamReader &Stream) {
     if (Present.count() != H->Size)
       return make_error<RawError>(raw_error_code::corrupt_file,
                                   "Present bit vector does not match size!");
 
     if (auto EC = readSparseBitVector(Stream, Deleted))
       return EC;
     if (Present.intersects(Deleted))
       return make_error<RawError>(raw_error_code::corrupt_file,
-                                  "Present bit vector interesects deleted!");
+                                  "Present bit vector intersects deleted!");
 
     for (uint32_t P : Present) {
       if (auto EC = Stream.readInteger(Buckets[P].first))
         return EC;
       const ValueT *Value;
       if (auto EC = Stream.readObject(Value))
         return EC;
       Buckets[P].second = *Value;

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

 NamedStreamMapTraits::NamedStreamMapTraits(NamedStreamMap &NS) : NS(&NS) {}
 
 uint16_t NamedStreamMapTraits::hashLookupKey(StringRef S) const {
   // In the reference implementation, this uses
   // HASH Hasher<ULONG*, USHORT*>::hashPbCb(PB pb, size_t cb, ULONG ulMod).
   // Here, the type HASH is a typedef of unsigned short.
   // ** It is not a bug that we truncate the result of hashStringV1, in fact
   //    it is a bug if we do not! **
+  // See NMTNI::hash() in the reference implementation.
   return static_cast<uint16_t>(hashStringV1(S));
 }
 
 StringRef NamedStreamMapTraits::storageKeyToLookupKey(uint32_t Offset) const {
   return NS->getString(Offset);
 }
 
 uint32_t NamedStreamMapTraits::lookupKeyToStorageKey(StringRef S) {

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

 using namespace llvm::support;
 using namespace llvm::support::endian;
 using namespace llvm::pdb;
 
 StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
     : Table(&Table) {}
 
 uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
-  return Table->getIdForString(S);
+  // The reference implementation doesn't include code for /src/headerblock
+  // handling, but it can only read natvis entries lld's PDB files if
+  // this hash function truncates the hash to 16 bit.
+  // PDB/include/misc.h in the reference implementation has a hashSz() function
+  // that returns an unsigned short, that seems what's being used for
+  // /src/headerblock.
+  return static_cast<uint16_t>(Table->getIdForString(S));
 }
 
 StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
   return Table->getStringForId(Offset);
 }
 
 uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
   return Table->insert(S);

llvm/unittests/DebugInfo/PDB/StringTableBuilderTest.cpp

 #include "llvm/Testing/Support/Error.h"
 
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace llvm::pdb;
 using namespace llvm::support;
 
-namespace {
-class StringTableBuilderTest : public ::testing::Test {};
-}
-
-TEST_F(StringTableBuilderTest, Simple) {
+TEST(StringTableBuilderTest, Simple) {
   // Create /names table contents.
   PDBStringTableBuilder Builder;
 
   // This test case is carefully constructed to ensure that at least one
   // string gets bucketed into slot 0, *and* to ensure that at least one
   // has a hash collision at the end of the bucket list so it has to
   // wrap around.
   uint32_t FooID = Builder.insert("foo");
TEST(StringTableBuilderTest, Simple) {
 
   EXPECT_THAT_EXPECTED(Table.getIDForString("foo"), HasValue(FooID));
   EXPECT_THAT_EXPECTED(Table.getIDForString("bar"), HasValue(BarID));
   EXPECT_THAT_EXPECTED(Table.getIDForString("baz"), HasValue(BazID));
   EXPECT_THAT_EXPECTED(Table.getIDForString("buzz"), HasValue(BuzzID));
   EXPECT_THAT_EXPECTED(Table.getIDForString("bazz"), HasValue(BazzID));
   EXPECT_THAT_EXPECTED(Table.getIDForString("barr"), HasValue(BarrID));
 }
+
+TEST(StringTableHashTraitsTest, Simple) {
+  PDBStringTableBuilder Builder;
+
+  // Create more than 64kiB of dummy entries.
+  for (int i = 0; i < 320; ++i) {
+    std::string aaaaa = std::string(220, 'a') + std::to_string(i);
+    Builder.insert(aaaaa);
+  }
+
+  std::string S = "foo.natvis";
+  uint32_t Pos = Builder.insert(S);
+
+  EXPECT_GT(Pos, 0xFFFFu);
+
+  StringTableHashTraits Traits(Builder);
+  EXPECT_LE(Traits.hashLookupKey(S), 0xFFFFu);
+}