Parse PDB Name Hash Table

[zturner]

Summary

PDB has a lot of similar data structures.  We already have code
for parsing a Name Map, but PDB seems to have a different but
very similar structure that is a hash table.  This is the
beginning of code needed in order to parse the name hash table,
but it is not yet complete.  It parses the basic metadata of
the hash table, the bucket array, and the names buffer, but
doesn't use any of these fields yet as the data structure
requires a non-trivial amount of work to understand.

The parsing code here corresponds to the `NMT` data structure in
the reference implementation, while `NameMap` corresponds to
the `NMTNI` data structure.

[zturner]

I actually managed to figure out the rest of this, so we can now dump all the strings from it as well, and I added tests in llvm-pdbdump to verify.

[zturner]

I had inadvertently written up the V2 hashing algorithm and used it in the case of a V1 header while we were claiming to not support V2. So now I add the V1 hashing function, and remove the version check, supporting both V1 and V2 hash algorithms.

[zturner]

Get rid of the duff's device. I imagine the compiler is pretty good at optimizing this, and it's hard to understand. It should be much more obvious how this version works, and it's equivalent.

[majnemer]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

37–57

Could we make this a simple for-loop and let the compiler unroll it?

99

Hash is a uint32_t, does % 0xFFFFFFFF actually do anything?

154

Returning -1 isn't a great interface, who is supposed to call getIndexForString ?

[majnemer]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

27

Shouldn't this be a size_t ?

38–58

Heh, you just addressed this right as I wrote this comment.

[zturner]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

27

Yea probably.

99

Honestly I don't think so, but I was wondering about the case where the formula there results in precisely 0xFFFFFFFF. Upon closer inspection though, I don't think that's even possible, because 0xFFFFFFFF-1013904223 = 3281063072, which isn't divisible by 5. And

154

I think I can return 0 here instead. 0 looks to be not a valid name index. Technically a name index is not actually an index but rather an offset into the names buffer, which you get by indexing the indices array. offset 0 in the buffer appears to always be a null character.

[zturner]

Address review comments.

[zturner]

I also changed the terminology everywhere from Index to ID so that people don't get confused and think they can iterate over all the names in a for loop.

[majnemer]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

132

If we are going to use 0 as our sentinel, can we assert that NameIndex isn't 0?

[zturner]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

132

I think it would be better to just skip over 0 values. If the number of buckets is larger than the number of strings (because say you added a string and then removed it) then you could have 0 values in the IDs array. So I should probably fix getStringForID to check for an ID of 0 and also fix getIDForString to skip the entry if it finds a 0 id.

[zturner]

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

132

So another option, is that it seems like Indicies[0] == 0, and NamesBuffer[0] is the sentinel string. So my hypothesis is that the correct thing to do is treat whatever is in Indices[0] as the "invalid ID". So if I return IDs[0] here, and then check for IDs[0] in getStringForID, that should work and at least not be hardcoded.

include/llvm/DebugInfo/PDB/Raw/DbiStream.h

 #include "llvm/DebugInfo/PDB/Raw/ByteStream.h"
 #include "llvm/DebugInfo/PDB/Raw/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Raw/ModInfo.h"
+#include "llvm/DebugInfo/PDB/Raw/NameHashTable.h"
 #include "llvm/DebugInfo/PDB/Raw/RawConstants.h"
 #include "llvm/Support/Endian.h"
 

   MappedBlockStream Stream;
 
   std::vector<ModuleInfoEx> ModuleInfos;
+  NameHashTable ECNames;
 
   ByteStream ModInfoSubstream;
   ByteStream SecContrSubstream;

include/llvm/DebugInfo/PDB/Raw/NameHashTable.h

+//===- NameHashTable.h - PDB Name Hash Table --------------------*- 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_NAMEHASHTABLE_H
+#define LLVM_DEBUGINFO_PDB_RAW_NAMEHASHTABLE_H
+
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/DebugInfo/PDB/Raw/ByteStream.h"
+
+#include <stdint.h>
+#include <utility>
+
+namespace llvm {
+namespace pdb {
+class StreamReader;
+class NameHashTable {
+public:
+  NameHashTable();
+
+  std::error_code load(StreamReader &Stream);
+
+  uint32_t getNameCount() const { return NameCount; }
+  uint32_t getHashVersion() const { return HashVersion; }
+  uint32_t getSignature() const { return Signature; }
+
+  StringRef getStringForID(uint32_t ID) const;
+  uint32_t getIDForString(StringRef Str) const;
+
+  ArrayRef<uint32_t> name_ids() const;
+
+private:
+  ByteStream NamesBuffer;
+  std::vector<uint32_t> IDs;
+  uint32_t Signature;
+  uint32_t HashVersion;
+  uint32_t NameCount;
+  uint32_t HashCount;
+};
+}
+}
+
+#endif

include/llvm/DebugInfo/PDB/Raw/StreamReader.h

     return readBytes(Buffer);
   }
 
+  template <typename T> std::error_code readArray(MutableArrayRef<T> Array) {
+    MutableArrayRef<uint8_t> Casted(reinterpret_cast<uint8_t*>(Array.data()), Array.size() * sizeof(T));
+    return readBytes(Casted);
+  }
+
   void setOffset(uint32_t Off) { Offset = Off; }
   uint32_t getOffset() const { return Offset; }
   uint32_t getLength() const { return Stream.getLength(); }

lib/DebugInfo/PDB/CMakeLists.txt

   Raw/PDBFile.cpp
   Raw/DbiStream.cpp
   Raw/InfoStream.cpp
+  Raw/NameHashTable.cpp
   Raw/NameMap.cpp
   Raw/RawSession.cpp
   Raw/StreamReader.cpp)

lib/DebugInfo/PDB/Raw/DbiStream.cpp

 #include "llvm/DebugInfo/PDB/Raw/DbiStream.h"
 #include "llvm/DebugInfo/PDB/Raw/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Raw/ModInfo.h"
+#include "llvm/DebugInfo/PDB/Raw/NameHashTable.h"
 #include "llvm/DebugInfo/PDB/Raw/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Raw/RawConstants.h"
 #include "llvm/DebugInfo/PDB/Raw/StreamReader.h"

   if (Reader.bytesRemaining() > 0)
     return std::make_error_code(std::errc::illegal_byte_sequence);
 
+  StreamReader ECReader(ECSubstream);
+  ECNames.load(ECReader);
+
   return std::error_code();
 }
 

lib/DebugInfo/PDB/Raw/NameHashTable.cpp

+//===- NameHashTable.cpp - PDB Name Hash Table ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/PDB/Raw/NameHashTable.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/DebugInfo/PDB/Raw/ByteStream.h"
+#include "llvm/DebugInfo/PDB/Raw/StreamReader.h"
+#include "llvm/Support/Endian.h"
+
+using namespace llvm;
+using namespace llvm::support;
+using namespace llvm::pdb;
+
+typedef uint32_t *PUL;
+typedef uint16_t *PUS;
+
+static inline uint32_t HashStringV1(StringRef Str) {
+  uint32_t Result = 0;
+  uint32_t Size = Str.size();
+
+  ArrayRef<ulittle32_t> Longs(reinterpret_cast<const ulittle32_t *>(Str.data()),
+                              Size / 4);
+
+  for (auto Value : Longs)
+    Result ^= Value;
+
+  const uint8_t *Remainder = reinterpret_cast<const uint8_t *>(Longs.end());
+  uint32_t RemainderSize = Size - Longs.size() * 4;
+
+  // Maximum of 3 bytes left.  Hash a 2 byte word if possible, then hash the
+  // possibly remaining 1 byte.
+  if (RemainderSize >= 2) {
+    Result ^= *reinterpret_cast<const ulittle16_t *>(Remainder);
+    Remainder += 2;
+    RemainderSize -= 2;
+  }
+
+  // hash possible odd byte
+  if (RemainderSize == 1) {
+    Result ^= *(Remainder++);
+  }
+
+  const uint32_t toLowerMask = 0x20202020;
+  Result |= toLowerMask;
+  Result ^= (Result >> 11);
+
+  return Result ^ (Result >> 16);
+}
+
+static inline uint32_t HashStringV2(StringRef Str) {
+  uint32_t Hash = 0xb170a1bf;
+
+  ArrayRef<char> Buffer(Str.begin(), Str.end());
+
+  ArrayRef<ulittle32_t> Items(
+      reinterpret_cast<const ulittle32_t *>(Buffer.data()),
+      Buffer.size() / sizeof(ulittle32_t));
+  for (ulittle32_t Item : Items) {
+    Hash += Item;
+    Hash += (Hash << 10);
+    Hash ^= (Hash >> 6);
+  }
+  Buffer = Buffer.slice(Items.size() * sizeof(ulittle32_t));
+  for (uint8_t Item : Buffer) {
+    Hash += Item;
+    Hash += (Hash << 10);
+    Hash ^= (Hash >> 6);
+  }
+
+  return Hash * 1664525L + 1013904223L;
+}
+
+NameHashTable::NameHashTable()
+    : Signature(0), HashVersion(0), NameCount(0), HashCount(0) {}
+
+std::error_code NameHashTable::load(StreamReader &Stream) {
+  struct Header {
+    support::ulittle32_t Signature;
+    support::ulittle32_t HashVersion;
+    support::ulittle32_t ByteSize;
+  };
+
+  Header H;
+  Stream.readObject(&H);
+  if (H.Signature != 0xEFFEEFFE)
+    return std::make_error_code(std::errc::illegal_byte_sequence);
+  if (H.HashVersion != 1 && H.HashVersion != 2)
+    return std::make_error_code(std::errc::not_supported);
+
+  Signature = H.Signature;
+  HashVersion = H.HashVersion;
+  NamesBuffer.initialize(Stream, H.ByteSize);
+
+  Stream.readInteger(HashCount);
+  std::vector<support::ulittle32_t> BucketArray(HashCount);
+  Stream.readArray<support::ulittle32_t>(BucketArray);
+  IDs.assign(BucketArray.begin(), BucketArray.end());
+
+  if (Stream.bytesRemaining() < sizeof(support::ulittle32_t))
+    return std::make_error_code(std::errc::illegal_byte_sequence);
+
+  Stream.readInteger(NameCount);
+  return std::error_code();
+}
+
+StringRef NameHashTable::getStringForID(uint32_t ID) const {
+  const uint8_t *Start = NamesBuffer.data().data();
+  return StringRef(reinterpret_cast<const char *>(Start + ID));
+}
+
+uint32_t NameHashTable::getIDForString(StringRef Str) const {
+  uint32_t Hash = (HashVersion == 1) ? HashStringV1(Str) : HashStringV2(Str);
+  size_t Count = IDs.size();
+  uint32_t Start = Hash % Count;
+  for (size_t I = 0; I < Count; ++I) {
+    uint32_t Index = (Start + I) % Count;
+    if (Index >= IDs.size())
+      continue;
+
+    uint32_t NameIndex = IDs[Index];
+    StringRef S = getStringForID(NameIndex);
+    if (S == Str)
+      return NameIndex;
+  }
+  return 0; // 0 is an invalid name index
+}
+
+ArrayRef<uint32_t> NameHashTable::name_ids() const {
+  return ArrayRef<uint32_t>(IDs).slice(1, NameCount);
+}

test/DebugInfo/PDB/pdbdump-headers.test

 ; EMPTY:      NameStream: 13
 ; EMPTY-NEXT: NameStreamSignature: effeeffe
 ; EMPTY-NEXT: NameStreamVersion: 1
+; EMPTY-NEXT: Name Count: 4
+; EMPTY-NEXT: Name: d:\src\llvm\test\debuginfo\pdb\inputs\predefined c++ attributes (compiler internal)
+; EMPTY-NEXT: Name:
+; EMPTY-NEXT: Name: d:\src\llvm\test\debuginfo\pdb\inputs\empty.cpp
+; EMPTY-NEXT: Name:
 
 ; EMPTY:      Dbi Version: 19990903
 ; EMPTY-NEXT: Age: 1

 BIG:      NameStream: 13
 BIG-NEXT: NameStreamSignature: effeeffe
 BIG-NEXT: NameStreamVersion: 1
+BIG-NEXT: Name Count: 92
+BIG-NEXT: Name: f:\dd\vctools\crt\vcruntime\inc\vcruntime_startup.h
+BIG-NEXT: Name: f:\dd\vctools\crt\vcstartup\src\misc\checkcfg.c
+BIG-NEXT: Name: f:\dd\vctools\langapi\include\isa_availability.h
+BIG-NEXT: Name:
+BIG-NEXT: Name: $T0 $ebp = $T2 $esp = $T1 .raSearchStart = $eip $T1 ^ = $ebp $T0 = $esp $T1 4 + =
+BIG-NEXT: Name:
+BIG-NEXT: Name: f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl
+BIG-NEXT: Name: $T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =  $20 $T0 40 - ^ =  $23 $T0 44 - ^ =  $24 $T0 48 - ^ =
+BIG-NEXT: Name: $T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =  $23 $T0 16 - ^ =  $24 $T0 20 - ^ =
 
 BIG:      Dbi Version: 19990903
 BIG-NEXT: Age: 1

tools/llvm-pdbdump/llvm-pdbdump.cpp

 #include "llvm/DebugInfo/PDB/Raw/InfoStream.h"
 #include "llvm/DebugInfo/PDB/Raw/MappedBlockStream.h"
 #include "llvm/DebugInfo/PDB/Raw/ModInfo.h"
+#include "llvm/DebugInfo/PDB/Raw/NameHashTable.h"
 #include "llvm/DebugInfo/PDB/Raw/PDBFile.h"
 #include "llvm/DebugInfo/PDB/Raw/RawSession.h"
 #include "llvm/DebugInfo/PDB/Raw/StreamReader.h"

                          cl::cat(FilterCategory));
 }
 
-
-static void reportError(StringRef Input, StringRef Message) {
-  if (Input == "-")
-    Input = "<stdin>";
-  errs() << Input << ": " << Message << "\n";
-  errs().flush();
-  exit(1);
-}
-
-static void reportError(StringRef Input, std::error_code EC) {
-  reportError(Input, EC.message());
-}
-
 static void dumpStructure(RawSession &RS) {
   PDBFile &File = RS.getPDBFile();
 

 
     outs() << "NameStream: " << NameStreamIndex << '\n';
 
-    // The name stream appears to start with a signature and version.
-    uint32_t NameStreamSignature;
-    Reader.readInteger(NameStreamSignature);
+    NameHashTable NameTable;
+    NameTable.load(Reader);
     outs() << "NameStreamSignature: ";
-    outs().write_hex(NameStreamSignature) << '\n';
-
-    uint32_t NameStreamVersion;
-    Reader.readInteger(NameStreamVersion);
-    outs() << "NameStreamVersion: " << NameStreamVersion << '\n';
-
-    // We only support this particular version of the name stream.
-    if (NameStreamSignature != 0xeffeeffe || NameStreamVersion != 1)
-      reportError("", std::make_error_code(std::errc::not_supported));
+    outs().write_hex(NameTable.getSignature()) << '\n';
+    outs() << "NameStreamVersion: " << NameTable.getHashVersion() << '\n';
+    outs() << "Name Count: " << NameTable.getNameCount() << '\n';
+    for (uint32_t ID : NameTable.name_ids()) {
+      outs() << "Name: " << NameTable.getStringForID(ID) << '\n';
+    }
   }
 
   DbiStream &DS = File.getPDBDbiStream();